CSCI402 - Operating Systems

Today's Lecture

Too Much Milk

How do we ensure that 2 (or more) roommates living together don't both go out and buy milk on the same day? On a computer we need 3 mechanisms to ensure this happens. People can just stick a note on the refrigerator saying they went to get milk.

• Synchronization: We must use atomic operations to ensure threads cooperate correctly.
• Mutual Exclusion: Ensure that only one thread can execute at a time in a special section of their code (called the critical section).
• Lock: Prevents someone from doing something. Like a lock on your bicycle prevents someone from taking your bike (hopefully).

First Solution: Notes

Requirements

• Never more than 1 person buys milk.
• Someone buys milk if milk is needed

Constraint

Only load and store operations are atomic. Any other operation, like an IF, can be interrupted.

Basis for Solution

• Leave a note (kind of like a lock)
• Remove note (release the lock)
• Don't buy milk if there's a note (wait to see what happens)

Pseudocode

if (noMilk) {
    if (noNote) {
        leave Note; //atomic operation
        buy Milk;
        remove Note;  //atomic
    }
}

The problem with th is solution is that both people can get past the check for noNote and get swithced out of the CPU. Thus, they can both leave notes and both go get milk. This violates our first requirement that only 1 person buys milk. However, it does satisfy the second requirement that someone buys milk if it is needed.

Second Solution: Labelled Notes

In this solution, each thread leaves its own note that is identified in some way with the thread. Thread A will leave noteA and Thread B will leave noteB. This way we can tell who left a note.

// Thread A
leave noteA
if (noNoteB) {
    if (noMilk) 
        buy Milk
}

remove noteA


// Thread B
leave noteB
if (noNoteA) {
    if (noMilk)
        buy Milk
}
remove noteB

The problem with this solution is that both threads can again leave notes. But since the check for whether a note exists is done afterwards, both threads can see that there is a note and nothing will happen. This is called starvation and violates requirement 2 that someone buys milk when it is needed.

Third Solution: Tailored Code for Each Thread

To solve the problem that occurred in Solution 2, we will tailor the code between the 2 threads. Up to now both threads have had essentially the same code.

// Thread A
leave noteA
if ( noNoteB) {
   if (noMilk)
        buy Milk
}

// Thread B
leave noteB
while (noteA)
    do nothing

if (noMilk)
    buy Milk

remove noteB

This solutions works. But each thread has different code, making this a very complicated solution for multiple threads. Also, while B is waiting, it is consuming CPU time. We call this busy waiting.

Better Way to do this Kind of Problem

Use the hardware to help out. There is no reason we have to do everything in software. We can create higher-level primitives in the hardware. In addition, we can build higher-level programming abstrations on the new primitives provided by the hardware. This can provide the following capabilities for manipulating locks:
Lock::Acquire() - waits until lock is free and then gets it when available
Lock::Release() - does both an unlock and wakes up a waiting process/thread

There are two requirements that we must have is that (1) the lock operations are atomic and (2) only one thread can get the lock at a time.

Fourth Solution: Much Better

The pseudocode looks like this:

//Same code for all threads
lock->Acquire();  //must be atomic
if (noMilk)
    buy Milk;

lock->Release();  //must also be atomic

Thus, we must first get the lock, which can only happen if no one else is either checking if there is milk, or is actually buying milk. Once we get the lock, we first check if there is milk. If there is, we don't do anything. If there isn't any milk, we go buy some.

Implementing Mutual Exclusion

As we mentioned above in the 'Too Much Milk' example, there are 3 requirements that we must satisfy if we want to successfully share information/resources. One of these requirements is Mutual Exclusion. Mutual exclusion's job is to ensure that two or more threads are not trying to share a resource (like a printer) that shouldn't be shared. Mutual exclusion says that if someone is using a resource, no one else can use that resource until it is released. Mutual Exclusion is typically implemented through some type of a locking mechanism. Once a thread has a lock, no one else is allowed to have the same lock.

To implement mutual exclusion successfully, there are 2 requirements:

• Hardware support for synchronization
• Higher-level program abstractions (so we don't have to program everything at the application level)

The types of low-level atomic operations provided by computer hardware are: load/store, interrupt disable (by the OS) and test&set. The higher-level atomic operations that are typically used are: locks, semaphores, monitors, and send&receive.

Load and Store Operations Only Available

Load and Store is one of the hardware atomic operations that essentially all computers provide. We found in the 'Too Much Milk' case that if you only have hardware support for load and store operations, your application code for threads becomes complex because each thread requires different code to ensure proper synchronization. With only 2 threads this is not much of a problem, but imagine if you had 10 threads, or more!

Locks and Context Switching Done in Hardware

As a counter to the previous synchronization where only load and store operations are atomic, we could put locks and context switching in the hardware. This would make synchronization between threads little more than a system call.

The problem with this method is that it places too much burden on the hardware. You end up making your hardware complex (just like the complex software program discussed above) and slow. We need a compromise through a balance of what the hardware can do well and what software programs can do for us.

Disable Interrupts

One way to ensure that the critical section in a thread is not interrupted, is hang a 'Do Not Disturb' sign around our thread. This disallows the OS from switching us out of the CPU when interrupts are disabled. This also allows us to do multiple operations in a non-interruptible sequence, in essence simulating atomic operations.

However, user processes/threads are not allowed to directly disable interrupts. If they were, a malicious user could disable interrupts and put their thread into an infinite loop, essentially locking up the computer. Because of this, user processes must ask the OS to disable interrupts. Because the OS has control of the interrupt enabling/disabling, there is a way out if something goes wrong.

Implementing Locks by Disabling Interrupts

We can use the ability to disable and reenable interrupts to implement a locking mechanism. We have a shared variable that we will use as a "locking variable". Whenever we are reading or writing this variable, we will disable interrupts. This will ensure that only one thread can read/write our locking variable at a time.

class Lock {
    int value = FREE;  //Our locking variable
}

Lock::Acquire() {
    disable interrupts
    while ( value != FREE) {
//      We must enable interrupts at this point, or the thread the currently has the 
//      lock will never be allowed back into the CPU to release it.
        enable interrupts

//      We must disable interrupts again before we check whether value is FREE or not
//      in the next iteration of the while loop.
        disable interrupts
    }

    value = BUSY;
    enable interrupts
}

Lock::Release() {
    disable interrupts
    value = FREE;
    enable interupts
}

The mechanism above works, but it requires each process trying to acquire the lock to constantly check if it is available. This is called busy waiting. In addition, this logic won't work on a multi-processor as interrupts are only disabled on the processor executing the thread. The other processors would still be able to read/write our lock variable, which we cannot allow to ensure proper operation.

Atomic Read-Modify-Write Instructions

One way around the multi-processor problems with disabling interrupts is to have a hardware-assisted atomic operation that:

• Reads a value from memory into a register
• Writes a new value back to the memory address.

Examples of Read-Modify-Write Instructions

• Test&set (most computers): Reads a value and writes a 1 back to memory.
• exchange (x86 CPUs): Swaps a value between a register and memory
• compare&swap (Motorola 68000 series): Read's a value. If the value matches another value in a register, do an exchange between the first register and the memory location referenced.
• Load linked and conditional store (R4000, Alpha): Reads a value in one instruction. Then do some operations, when a store operation occurs, hardware checks for a modified value, if no change has been made in the memory location, the next instruction is executed. If a change has been made in the memory location (typically validated by a "dirty bit" in the page table), the instruction forces a restart.

Implementing Locks with Test&Set

Test&Set reads a location in memory, sets the lock value to 1 and returns the value read. The code looks like this:

//Initial value for lock is 0

Lock::Acquire() {
    while (test&set(value) == 1 ) {
//      while the value is 1, someone else has the lock (because locking process sets it to 1)
//      once the value is not 1 anymore, we have the lock (setting it to 1, by definition)

        do whatever we want
    }
}

Lock::Release() {
    value = 0;
}

The problem with this apparently simple configuration is that it is still busy waiting. We really want to be able to wait to get a lock without having to constantly check to see if it is available.

Locks Using Interrupt Disable Without Busy Waiting

To eliminate busy waiting, we need some mechanism to make waiting threads go to sleep and some way to wake a sleeping thread up when the lock is available. Look at the code shown below for one way to do this.

Lock::Acquire() {
    disable interrupts
    if ( value == BUSY ) {
        put thread on queue of waiting threads
        go to sleep
    }
    else {
        value = BUSY;  //Got the lock
    }

    enable interrupts
}

Lock::Release() {
    disable interrupts
    if anyone on the lock wait queue {
        take 1 waiting thread off
        put the thread on the READY queue
    }
    else {
         value = FREE;  //No one waiting, just make lock variable available
    }

    enable interrupts
}

When does Acquire reenable interrupts when wanting to go to sleep?

• Before putting the thread on the wait queue?
  If we do this, then the Lock::Release() can check the wait queue, but the thread who wants to go to sleep might not actually be asleep, yet.
• After putting the thread on the wait queue, but before going to sleep?
  In this case, the Release operation would put a waiting thread on the READY queue. However, the thread may not have gone to sleep yet, so it is already on the READY queue. When the thread finally gets to execute again, it puts itself to sleep, but now there is no one to wake it up!

What to do? In Nachos, interrupts are disabled when you call Thread::sleep() and it is the responsibility of the next thread to reenable interrupts. This is fine for the Nachos environment, but it won't work in the real world. We will see later various ways to achieve this. The safest is to have the 2 operations (going to sleep and reenabling interrupts to be an atomic operation.

Locks Using Test&Set With Minimal Busy Waiting

Another alternative is to use the hardware provided test&set mechanism. There is no way to eliminate busy waiting altogether, but you only busy wait to atomically check the lock value. If the lock is busy, you give up the CPU. The Acquire and Release methods are shown below:

Lock:;Acquire() {
    while (test&set(guard)) {
        if ( value != FREE ) {
            put thread on the waiting thread queue
            go to sleep and set guard to 0  //allows someone else to have the lock
        }
        else {
            value = BUSY;
            guard = 0;
        }
    }
}

Lock::Release() {
    while (test&set(guard) ) {
        if anyone on wait queue {
            take 1 waiting thread off
            put it on the READY queue
        }
        else {
            value = FREE;  //no one waiting
        }

        guard = 0;
    }
}

Semaphores

Semaphores are a generalized version of the sleep/wakeup mechanism we have been discussing. In addition to the sleep/wakeup, semaphores save some state information allowing them to be used for more than just sleep or wakeup.

Dijksta (1965) came up with semaphores and they are used in Unix for interprocess communication. Semaphores have a positive integer value; they are not allowed to have a negative value. They can be 0.

Semaphores Support 2 Operations

• semaphore->V (Up in the book)
• semaphore->P (Down in the book)

Semaphores Have 2 Uses

Mutual Exclusion

In this case, the semaphore starts with a value of 1. Before entering a critical section, a DOWN operation is executed (setting the semaphore to 0, if not already 0). After leaving the critical section, you perform an UP operation. It looks like this:

    semaphore->Down();
//  critical section
    semaphore->Up();

Scheduling Constraints

Semaphores provide a way for a thread to wait for something (like a resource). In these cases, it is typical that the semaphore value begins with 0.

Producer-Consumer with a Bounded Buffer

Let's go through an example that utilizes both capabilities of semaphores. In this example, a Producer puts items into a buffer that has a fixed size (bounded). A Consumer takes items out of the buffer.

Bad Solution: Operate in Lock Step

In this implementation, we force the Producer and Consumer to take turns. The Producer is required to run first and it cannot run again until the Consumer has run one time.

This is a bad solution because as long as the buffer is not full, we should be able to have the Producer add an item, irrespective of what the Consumer is doing. Conversely, the Consumer should be able to remove an item from the buffer, as long as there is one there. Forcing them to take turns lowers the overall throughput, in general.

Correctness Constraints

We have the following 3 correctness constraints to ensure that we get maximum throughput from our buffer.

1. The Consumer waits for the Producer to fill buffers, if the buffer is empty.
2. The Producer waits for the Consumer to empty buffers, if all buffers are full.
3. Only one thread can manipulate the buffer queue at a time.

Constraints 1 and 2 are Scheduling Constraints that control when the Producer or the Consumer can execute. Constraint 3 is our Mutual Exclusion constraint that ensures we don't mess up somewhere.

To keep everything working properly, we will use a separate semaphore for each constraint.

fullBuffers  //Consumer's constraint
emptyBuffers //producer's constraint
mutex        //mutual exclusion

Example: Coke Machine

The idea is that the Coke woman cannot add more Coke to the machine when it is full. Also, people cannot get Coke out of the machine if it is empty (no guarantee you get your money back). The code for this is shown below.

// Initial values for semaphores
fullBuffers = 0;
emptyBuffers = 10:  //Can have 10 cans of Coke in the machine
mutex = 1;

Producer() {
    emptyBuffers.Down();  //Always do a Down before entering critical section
    mutex.Down();

    put 1 Coke in the machine

    mutex.Up();
    fullBuffers.Up();  //And an Up after exiting
}

Consumer() {
    fullBuffers.Down();
    mutex.Down();

    take 1 Coke out

    mutex.Up();
    emptyBuffers.Up();
}

Now for the questions:

• Why do we do a Down on emptyBuffers for the Producer and fullBuffers for the Consumer before we do a Down on mutex? What would happen if we switched them around?
  Remember that semaphores go to sleep if they cannot perform their operation. If we do a mutex.Down first and get the lock, if we cannot do a Down on emptyBuffers, we are stuck. We have the mutual exclusion lock, but have gone to sleep waiting for an empty buffer. The Consumer will not be able to get a Coke because we have the mutual exclusion lock. This is why we must "leave a note" that we are going to add/remove Coke before we disallow anyone else from doing the same.
• Why don't we use a single semaphore for how many buffers are in use, or not in use?
  If we just had a semaphore called bufferState, the Producer would do an UP first before its mutex.Down and the Consumer would do a DOWN first before its mutex.Down. The problem could arise that the Producer does an UP and before it is able to grab the mutex lock, it gets rolled out of the CPU. If this was the first item added to the machine, a Consumer could come along and think there was a Coke in the machine, when the Producer hasn't actually put one in, yet. That is why we need 2 separate semaphores.
• What happens to our code if we have more than one Producer or Consumer?
  Nothing at all. The logic will work with any number of Producers or Consumers. That is one of the reasons that semaphores are attractive, even with the problems they have that we will discuss later.