Synchronization Problems

Synchronization

The concept of semaphores as used in computer synchronization is due to the Dutch computer scientist Edsgar Dijkstra. 

A semaphore is an integer with a difference. Well, actually a few differences.

• You set the value of the integer when you create it, but can never access the value directly after that; you must use one of the semaphore functions to adjust it, and you cannot ask for the current value.
• There are semaphore functions to increment or decrement the value of the integer by one.
• Decrementing is a (possibly) blocking function. If the resulting semaphore value is negative, the calling thread or process is blocked, and cannot continue until some other thread or process increments it.
• Incrementing the semaphore when it is negative causes one (and only one) of the threads blocked by this semaphore to become unblocked and runnable.

Increment

Dijkstra called this function V(); it is also called signal, unlock, leave or release.

Decrement

Dijkstra called this function P(); it is also called wait, lock, enter, or get.

Implementation

The easiest way for me to think of semaphores is, of course, with code. Here is a little pseudo-code that may help.

typedef struct sem {   int value;   other_stuff } *Sem; 

Types of Synchronization Problems

By now, you've see three types of synchronization mechanisms:

• locks (implemented at pthread_mutex_* under pthreads)
• monitors (implemented as pthread_cond_* under pthreads)
• semaphores

Signalling

On common problem, sometimes termed signalling, that occurs frequently is one in which one thread must complete some portion of work before another thread is allowed to proceed. This synchronization pattern usually occurs as a result of thread-based modularity. That is, you often want to write threads to solve specific, self-contained tasks and you need threads doing different tasks to work together (perhaps in sequence) to solve some problem.

Rendezvous

The parallel processing folks have a concept of a barrier, which is a point that all threads have to reach before any can proceed. The two-thread simplified version is called a rendezvous. It's just a matter of signalling both ways. Here, we'll need two semaphores, both initialized to zero.

The Bounded Buffer Problem

The last time we were looking at mutexes, the problem was a bit more complicated than this, though. We were doing the printer simulation, and we had several mutexes and condition variables. Can semaphores do that? They can indeed. We'll use two of the mutex patterns discussed above, one to protect the head of the queue and one to protect the tail. We'll avoid the condition variable entirely by using semaphores directly to keep track of how many empty queue slots are empty and how many are full. Accordingly we won't need to keep the count of the number of entries in the queue, at least not explicitly.

So, what are the lessons?

• First, when multiple threads or processes access multiple resources exclusively, you must worry about deadlock.
• Second, you must worry about starvation, and the only way to prevent starvation is to enforce that all threads/processes get unblocked every now and then. This can be using a global queue, as in solution #6, or some other ordering strategy, as in solutions #7 and #8. Sometimes you have to be less aggressive about preventing starvation (as in solution #8) in order to get both good performance, and no starvation.
• Third, often you have to worry about treating all threads equally, so that no one thread gets more resources than the others due to your synchronization protocol. This was the problem with the asymmetric solution (#4).

The Kthreads Library

Kthreads is a relatively simple, non-preemptive threads library that we will be using to implement our operating system later in the labs. For our purposes, it has an advantage over pthreads because it works in the debugger and because it will not interfere with the simulator (making your development life easier). It's also simple enough to understand, and therefore makes for a good teaching tool.