A race condition occurs when two (or more) processes are about to perform some action. Depending on the exact timing, one or other goes first. If one of the processes goes first, everything works, but if another one goes first, an error, possibly fatal, occurs.

Imagine two processes both accessing x, which is initially 10.

We must prevent interleaving sections of code that need to be atomic with respect to each other. That is, the conflicting sections need mutual exclusion. If process A is executing its critical section, it excludes process B from executing its critical section. Conversely if process B is executing is critical section, it excludes process A from executing its critical section.

Requirements for a critical section implementation.

The operating system can choose not to preempt itself. That is, we do not preempt system processes (if the OS is client server) or processes running in system mode (if the OS is self service). Forbidding preemption for system processes would prevent the problem above where x x+1 not being atomic crashed the printer spooler if the spooler is part of the OS.

But simply forbidding preemption while in system mode is not sufficient.

Does not work if the system has several processors.

Software solutions for two processes

Initially P1wants=P2wants=false

Code for P1 Code for P2

Loop forever { Loop forever {

P1wants = true ENTRY P2wants = true

while (P2wants) {} ENTRY while (P1wants) {}

critical-section critical-section

P1wants = false EXIT P2wants = false

non-critical-section } non-critical-section }

Explain why this works.

But it is wrong! Why? (in case P1wants = P2wants = true then deadlock occurs)

Let's try again. The trouble was that setting want before the loop permitted us to get stuck. We had them in the wrong order!

Initially P1wants=P2wants=false

Code for P1 Code for P2

Loop forever { Loop forever {

while (P2wants) {} ENTRY while (P1wants) {}

P1wants = true ENTRY P2wants = true

critical-section critical-section

P1wants = false EXIT P2wants = false

non-critical-section } non-critical-section }

Explain why this works.

But it is wrong again! Why? (both processes may enter the CS)

So let's be polite and really take turns. None of this wanting stuff.

Initially turn=1

Code for P1 Code for P2

Loop forever { Loop forever {

while (turn = 2) {} while (turn = 1) {}

critical-section critical-section

turn = 2 turn = 1

non-critical-section } non-critical-section }

This one forces alternation, so is not general enough. Specifically, it does not satisfy condition three, which requires that no process in its non-critical section can stop another process from entering its critical section. With alternation, if one process is in its non-critical section (NCS) then the other can enter the CS once but not again.

The first example violated rule 4 (the whole system blocked). The second example violated rule 1 (both in the critical section. The third example violated rule 3 (one process in the NCS stopped another from entering its CS).

In fact, it took years (way back when) to find a correct solution. Many earlier “solutions” were found and several were published, but all were wrong. The first correct solution was found by a mathematician named Dekker, who combined the ideas of turn and wants. The basic idea is that you take turns when there is contention, but when there is no contention, the requesting process can enter. It is very clever, but I am skipping it (I cover it when I teach distributed operating systems in V22.0480 or G22.2251). Subsequently, algorithms with better fairness properties were found (e.g., no task has to wait for another task to enter the CS twice).

What follows is Peterson's solution, which also combines turn and wants to force alternation only when there is contention. When Peterson's solution was published, it was a surprise to see such a simple soluntion. In fact Peterson gave a solution for any number of processes. A proof that the algorithm satisfies our properties (including a strong fairness condition) for any number of processes can be found in Operating Systems Review Jan 1990, pp. 18-22.

Initially P1wants=P2wants=false and turn=1

Code for P1 Code for P2

Loop forever { Loop forever {

P1wants = true P2wants = true

turn = 2 turn = 1

while (P2wants and turn=2) {} while (P1wants and turn=1) {}

critical-section critical-section

P1wants = false P2wants = false

non-critical-section non-critical-section

}}

Hardware assist (test and set)

TAS(b), where b is a binary variable, ATOMICALLY sets b = true and returns the OLD value of b.

Of course it would be silly to return the new value of b since we know the new value is true.

The word atomically means that the two actions performed by TAS(x) (testing, i.e., returning the old value of x and setting, i.e., assigning true to x) are inseparable. Specifically it is not possible for two concurrent TAS(x) operations to both return false (unless there is also another concurrent statement that sets x to false).

With TAS available implementing a critical section for any number of processes is trivial.

loop forever {

while (TAS(s)) {} ENTRY

CS

s = false EXIT

NCS

}

Remark: Tanenbaum does both busy waiting (as above) and blocking (process switching) solutions. We will only do busy waiting, which is easier. Sleep and Wakeup are the simplest blocking primitives. Sleep voluntarily blocks the process and wakeup unblocks a sleeping process. We will not cover these.

Question: Explain the difference between busy waiting and blocking process synchronization.

Remark: Tannenbaum use the term semaphore only for blocking solutions. I will use the term for our busy waiting solutions. Others call our solutions spin locks.

P and V and Semaphores

The entry code is often called P and the exit code V. Thus the critical section problem is to write P and V so that

loop forever

P

critical-section

V

non-critical-section

satisfies

Note that I use indenting carefully and hence do not need (and sometimes omit) the braces {} used in languages like C or java.

A binary semaphore abstracts the TAS solution we gave for the critical section problem.

where finding S=open and setting S<--closed is atomic

The above code is not real, i.e., it is not an implementation of P. It is, instead, a definition of the effect P is to have.

To repeat: for any number of processes, the critical section problem can be solved by

loop forever

P(S)

CS

V(S)

NCS

The only specific solution we have seen for an arbitrary number of processes is the one just above with P(S) implemented via test and set.

Remark: Peterson's solution requires each process to know its processor number. The TAS soluton does not. Moreover the definition of P and V does not permit use of the processor number. Thus, strictly speaking Peterson did not provide an implementation of P and V. He did solve the critical section problem.

To solve other coordination problems we want to extend binary semaphores.

Both of the shortcomings can be overcome by not restricting ourselves to a binary variable, but instead define a generalized or counting semaphore.

where finding S>0 and decrementing S is atomic

These counting semaphores can solve what I call the semi-critical-section problem, where you premit up to k processes in the section. When k=1 we have the original critical-section problem.

initially S=k

loop forever

P(S)

SCS <== semi-critical-section

V(S)

NCS

Producer-consumer problem

Initially e=k, f=0 (counting semaphore); b=open (binary semaphore)

Producer Consumer

loop forever loop forever

produce-item P(f)

P(e) P(b); take item from buf; V(b)

P(b); add item to buf; V(b) V(e)

V(f) consume-item

Unfortunately, it is rare to find hardware that implements P & V directly (or messages, or monitors). They all involve some sort of scheduling and it is not clear that scheduling stuff belongs in hardware (layering). Thus semaphores must be built up in software using some lower-level synchronization primitive provided by hardware.

Need a simple way of doing mutual exclusion in order to implement P's and V's. We could use atomic reads and writes, as in "too much milk" problem, but these are very clumsy.

Uniprocessor solution: Disable interrupts.

class semaphore {
    private int count;

    public semaphore (int init)
    {
        count = init;
    }

    public void P ()
    {
        while (1) {
              Disable interrupts;
              if (count > 0) {
                   count--;
                   Enable interrupts;
              } else {
                   Enable interrupts;
              }
        }
    }

    public void V ()
    {
        Disable interrupts;
        count++;
        Enable interrupts;
    }
}

What is wrong with this code?

Multiprocessor solution:

Step 1: when P fails, put process to sleep; on V just wake up everybody, processes all try P again.

Step 2: label each process with semaphore it's waiting for, then just wakeup relevant processes.

Step 3: just wakeup a single process.

Step 4: add a queue of waiting processes to the semaphore. On failed P, add to queue. On V, remove from queue.

Why can we get away with only removing one process from queue at a time?

There are several tradeoffs implicit here: how many processes in the system, how much queuing on semaphores, storage requirements, etc. The most important thing is to avoid busy-waiting.

Is it "busy-waiting" if we use the solution in step 1 above?

What do we do in a multiprocessor to implement P's and V's? Cannot just turn off interrupts to get low-level mutual exclusion.

In a multiprocessor, there must be busy-waiting at some level: cannot go to sleep if do not have mutual exclusion.

Most machines provide some sort of atomic read- modify-write instruction. Read existing value, store back in one atomic operation.

Using test and set for mutual exclusion: It is like a binary semaphore in reverse, except that it does not include waiting. 1 means someone else is already using it, 0 means it is OK to proceed. Definition of test and set prevents two processes from getting a 0->1 transition simultaneously.

Test and set is tricky to use. Using test and set to implement semaphores: For each semaphore, keep a test-and-set integer in addition to the semaphore integer and the queue of waiting processes.

class semaphore {
    private int t;
    private int count;
    private queue q;
        
    public semaphore(int init)
    {
        t = 0;
        count = init;
        q = new queue();
    }

    public void P()
    {
        Disable interrupts;
        while (TAS(t) != 0) { /* just spin */ };
        if (count > 0) {
            count--;
            t = 0;
            Enable interrupts;
            return;
        }
        Add process to q;
        t = 0;
        Enable interrupts;
        Redispatch;
    }

    public V()
    {
        Disable interrupts;
        while (TAS(t) != 0) { /* just spin */ };
        if (q == empty) {
            count++;
        } else {
            Remove first process from q;
            Wake it up;
        }
        t = 0;
        Enable interrupts;
    }
}

Why do we still have to disable interrupts in addition to using test and set?

Important point: implement some mechanism once, very carefully. Then always write programs that use that mechanism. Layering is very important.

Remark: Whereas we use the term semaphore to mean binary semaphore and explicitly say generalized or counting semaphore for the positive integer version, Tanenbaum uses semaphore for the positive integer solution and mutex for the binary version. Also, as indicated above, for Tanenbaum semaphore/mutex implies a blocking primitive; whereas I use binary/counting semaphore for both busy-waiting and blocking implementations. Finally, remember that in this course we are studying only busy-waiting solutions.

Monitors are a high-level data abstraction tool combining three features:

They are especially convenient for synchronization involving lots of state.

Existing implementations of monitors are embedded in programming languages. Best existing implementations are the Java programming language from Sun and the Mesa language from Xerox.

There is one binary semaphore associated with each monitor, mutual exclusion is implicit: P on entry to any routine, V on exit. This synchronization is automatically done by the compiler (because he makes automatic calls to the OS), and the programmer does not seem them. They come for free when the programmer declares a module to be a monitor.

Monitors are a higher-level concept than P and V. They are easier and safer to use, but less flexible, at least in raw form as above.

Probably the best implementation is in the Mesa language, which extends the simple model above with several additions to increase the flexibility and efficiency.

Do an example: implement a producer/consumer pair.

The "classic" Hoare-style monitor (using C++ style syntax):

class QueueHandler {

    private:
        static int BUFFSIZE = 200;
        int first;
        int last;
        int buff[BUFFSIZE];
        condition full;
        condition empty;

	int ModIncr(int v) {
	    return (v+1)%BUFFSIZE;
	}

    public:
        void QueueHandler (int);
        void AddToQueue (int);
        int RemoveFromQueue ();
    };



    void
    QueueHandler::QueueHandler (int val)
    {
	first = last = 0;
    }

    void
    QueueHandler::AddToQueue (int val) {
    {
	while (ModIncr(last) == first) {
	    full.wait();
	}
	buff[last] = val;
	last = ModIncr(last);
	empty.notify();
    }

    int
    QueueHandler::RemoveFromQueue ();
    {
	while (first == last) {
	    empty.wait();
	}
	int ret = buff[first];
	first = ModIncr(first);
	full.notify();
	return ret;
    }

Java only allows one condition variable (implicit) per object. Here is the same solution in Java:

class QueueHandler {

        final static int BUFFSIZE = 200;
        private int first;
        private int last;
        private int buff[BUFFSIZE];


        private int ModIncr(int v) {
            return (v+1)%BUFFSIZE;
        }

        public QueueHandler (int val)
        {
            first = last = 0;
        }

        public synchronized void AddToQueue (int val) {
        {
            while (ModIncr(last) == first) {
                try { wait(); }
                catch (InterruptedException e) {}
            }
            buff[last] = val;
            last = ModIncr(last);
            notify();
        }

        public synchronized int RemoveFromQueue ();
        {
            while (first == last) {
                try { wait(); }
                catch (InterruptedException e) {}
            }
            int ret = buff[first];
            first = ModIncr(first);
            notify();
            return ret;
        }

Condition variables: things to wait on. Two types: (1) classic Hoare/Mesa condition variables and (2) Java condition variables.

Hoare/Mesa condition variables:

Java condition variables:

Show how wait and notify solve the semaphore implementation problem. Mention that they can be used to implement any scheduling mechanism at all. How do wait and notify compare to P and V?

Do the readers' and writers' problem with monitors.

Summary:

Up until now, discussion has been about communication using shared data. Messages provide for communication without shared data. One process or the other owns the data, never two at the same time.

Message = a piece of information that is passed from one process to another.

Mailbox = a place where messages are stored between the time they are sent and the time they are received.

Operations:

Figure 1

There are two general styles of message communication:

Figure 2

Figure 3

Producer & consumer example:

Note that buffer recycling is implicit, whereas it was explicit in the semaphore implementation.

Client & Server example:

Note that this looks a lot like a procedure call&return. Explain the various analogs between procedure calls and message operations:

Why use messages?

Which are more powerful, messages or monitors?

Message systems vary along several dimensions:

What happens with rendezvous protocols and conditional operations?

How would the following systems fall into the above classifications?

Until now we have talked about processes, from now on we will talk about resources, the things operated upon by processes. Resources range from cpu time to disk space to channel I/O time.

Resources fall into two classes:

OS makes two related kinds of decisions about resources:

Processes may be in any one of three general scheduling states:

There are two parts to CPU scheduling:

This is an example of policy/mechanism separation.

Goals for Scheduling Disciplines

There are some curious interactions between scheduling and synchronization. A classic problem caused by this interaction was first observed in 1979 but Butler Lampson and David Redell at Xerox.

Suppose that you have three processes:

And suppose that you have the following critical section, S:

S: mutex.P()

. . .

. . .

mutex.V()

The three processes execute as follows:

So, what's going wrong here? To really understand this situation, you should try to work out the example for yourself, before continuing to read.

As a result, P2 running (at medium priority) is blocking P1 (at highest priority) from running. This example is not an academic one. Many designers of real-time systems, where priority can be crucial, have stumbled over issue. You can read the original paper by Lampson and Redell to see their suggestion for handling the situation.