Tom Herbert, CTO, July 22, 2024
Inevitably, any discussion about parallelism will get around to synchronization. Two threads executing parallel may access a shared resource, have some portion of processing that must be done in order, or may have some other dependencies between threads. Basically, some portion of processing between the two threads, a critical region if you will, must be serialized. The mechanism to orchestrate this and keep everything sane is called synchronization.
The problem
Traditionally, mutexes or locks are used for synchronization. The basic idea is that before entering a critical region a thread obtains a mutex, and when exiting the critical region the thread releases the mutexes. When a thread has obtained the mutex for the critical region, no other thread can execute in the critical region. Atomic operations facilitate mutexes, and they are general purpose.
Anyone who's worked with mutexes knows that deadlock is always lurking in the shadows. Deadlock lock happens when two threads are waiting on each other indefinitely. For instance, if Thread 1 has acquired Mutex A and is waiting for Mutex B, and Thread 2 has acquired Mutex B and is waiting for Mutex A– then both threads are blocked indefinitely. Deadlock has been a concern since day one of parallelism (for instance see the Dining Philosophers problem). So the question is often asked: “Can we create a deadlock free synchronization mechanism?”.
Dependencies to the rescue!
Let's consider synchronization for network processing. In network processing, all processing is ordered– for instance, received packets are processed in order, and protocol layers with a packet are processed in order (e.g. Ethernet is processed before IP which is processed before TCP). This ordering property is a useful constraint that enables us to define a novel synchronization mechanism for network processing, or more generally serial data processing, called dependencies.
Dependencies is based on strict order of processing threads. Assuming all threads in the system are ordered, then a thread may be dependent on processing in an upstream thread, but a thread is never dependent on processing in a downstream thread. So the dependencies mechanism can be defined by wait points and resolve points. A wait point is a point in the code path of a thread at which execution cannot proceed until the dependency has been resolved by upstream threads. A resolve point is a point in the code path of a thread at which processing has been done to satisfy a dependency in downstream threads.
The diagram below illustrates the operation of wait point and resolve points in dependency synchronization.
Example of dependencies synchronization. Big yellow circles are threads that are ordered left to right. There are two dependencies: the blue circle and the red diamond one. Solid circles and diamonds are resolve points, hollow circles and diamonds are wait points
Dependencies example
The diagram below shows a simple example of a dependency between IPv4 and TCP processing. In TCP some processing is stateless and some processing is stateful. Stateless processing, including validating the TCP checksum and computing the 4-tuple hash for connection lookup, can be done concurrently with IPv4 processing since there are no dependencies on stateless processing. On the other hand, stateful processing, such as updating the PCB (Protocol Control Block), can only be done once IP processing has validated the packet. To support this, we can define an IPhdr_valid dependency as suggested in the figure below. A wait point for the dependency is in the TCP code before updating the PCB, and a resolve point in the IP code after the packet is validated.
Example of IPhdr_valid dependency. The wait point is indicated by a hollow circle, and the resolve point by a solid circle, and the red shaded area indicates the critical region.
The punchline
If we create a dependency graph with some combination of wait point and resolve points, like in the example at the top of the page, we see that there are no circular dependencies or cycles in the graph. This is due to unidirectional properties of dependencies, and it leads to the salient and provable property of dependencies:
Deadlock is impossible with dependencies
So, this answers the question about whether a deadlock free synchronization mechanism is possible. The reader might note that it’s a restricted solution that assumes strict order processing semantics. Yes, that’s true– dependencies is a domain specific solution, not a general solution. However, the domain we’re talking about is pretty expansive that includes network processing and other use cases as well.
In addition to being deadlock free, dependencies have some nice corollary properties that minimize the overheads of synchronization and parallelism. We’ll talk about that in our next blog, and dive into some details about how dependencies work and are implemented.
SiPanda
SiPanda was created to rethink the network datapath and bring both flexibility and wire-speed performance at scale to networking infrastructure. The SiPanda architecture enables data center infrastructure operators and application architects to build solutions for cloud service providers to edge compute (5G) that don’t require the compromises inherent in today’s network solutions. For more information, please visit www.sipanda.io. If you want to find out more about PANDA, you can email us at panda@sipanda.io. IP described here is covered by patent USPTO 12,026,546 and other patents pending.
Kommentarer