Synchronization

Sources of concurrency

• • multiple processes

  • one process with multiple threads

  • multiple physical processors

  • network

The critical section problem

Given two more more processes (or threads) which share a resource (e.g., variable or device), we must often synchronize their activity.

Must satisfy to one degree or another the concepts of mutual exclusion, progress, and bounded waiting.

Example: consider only two processes

critical section (<cs>): instructions which access shared resource

We must establish mutual exclusion: no two processes can be in their <cs> at the same time.

process producer { while (true) { while (count == BUFFER_SIZE); ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; } }

process consumer { while (true) { while (count == 0); --count; item = buffer[out]; out = (out - 1) % BUFFER_SIZE; } }

Assume count = 5 and both producer and consumer execute the statements ++count and --count.

Results? count could be set to 4, 5, or 6 (but only 5 is correct).

reg_1 = count reg_1 = reg_1 + 1 count = reg_1 reg_2 = count reg_2 = reg_2 - 1 count = reg_2

principle of atomicity

t_0: producer executes reg_1 = count [reg_1 = 5] t_1: producer executes reg_1 = reg_1 + 1 [reg_1 = 6] t_2: consumer executes reg_2 = count [reg_2 = 5] t_3: consumer executes reg_2 = reg_2 - 1 [reg_2 = 4] t_4: producer executes count = reg_1 [count = 6] t_5: consumer executes count = reg_2 [count = 4]

race condition: a situation where multiple processes access and manipulate the same data concurrently and the outcome of the execution depends on the order in which the instructions execute.

Operating system kernel code itself can have race conditions.

preemptive vs. nonpreemptive kernels

This is called the critical section problem.

A solution must satisfy three requirements:

• • mutual exclusion: only one process may execute its critical section at once.

  • progress: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes not executing in their remainder sections can participate in the decision on which process will enter its critical section next, and this decision cannot be postponed indefinitely.

  • bounded waiting: this is a limit on the number of times other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted.

Basic idea in synchronization: need locks in one form or another

• • while (true) // entry section; acquire lock // critical section // exit section; release lock // remainder section }

Three primitive solutions to the critical section problem

• • disable interrupts during execution of <cs>

    • process p_i { while (true) { // disable interrupts (a system call) // critical section // enable interrupts (a system call) // remainder section } }

      • degrades efficiency

      • not possible multiprocessor systems

  • hardware instructions (e.g., test-and-set and swap)

  • Peterson's solution

Hardware instructions

two new instructions, both versions of a read-modify-write instruction

• • test and set

    • boolean test-and-set (boolean* target) { boolean temp = *target; *target = true; return temp; } boolean occupied = false; while (true) { while (test-and-set (&occupied)); // critical section occupied = false; // remainder section }

  • problems? starvation

  • swap

    • void swap (boolean* x, boolean *y) { boolean temp = *x; *x = *y; *y = temp; } boolean occupied = false; boolean p_i_must_wait = true; while (true) { do swap (&p_i_must_wait, &occupied); while (p_i_must_wait); // critical section p_i_must_wait = true; occupied = false; // remainder section }

Peterson's Solution

shared data: int turn; boolean flag[2]; process p_i { while (true) { flag[i] = true; // I am ready to enter my <cs> turn = j; // but I give p_j priority // as long as p_j wants access and it is p_j's turn, I do no-op while (flag[j] && turn == j); // critical section // I am no longer in my <cs> flag[i] = false; // remainder section; } } process p_j { while (true) { flag[j] = true; // I am ready to enter my <cs> turn = i; // but I give p_i priority // as long as p_i wants access and it is p_i's turn, I do no-op while (flag[i] && turn == i); // critical section // I am no longer in my <cs> flag[j] = false; // remainder section; } }

Peterson's solution guarantees mutual exclusion, progress, and bounded waiting.

What is the problem with Peterson's solution?

busy waiting: the waiting process wastes CPU cycles; in a uniprocessor system, the process waits until its quantum expires

High-level synchronization solutions

(which rely on primitive solutions)

• • semaphores

  • monitors

Types of solutions (low-level vs. high-level)

• • low-level

    • • disable interrupts (will not work in a multiprocessor system)

      • hardware instructions

        • • test and set instruction

          • swap instruction

  • high-level

    • • semaphores

      • monitors (and condition variables)

Types of solutions (hardware vs. software)

• • hardware

    • • disable interrupts (will not work in a multiprocessor system)

      • hardware instructions

        • • test and set instruction

          • swap instruction

  • software

    • • Peterson's solution

      • semaphores

      • monitors (and condition variables)

References

Semaphores

Hardware solutions are complex for an application programmer to use.

To improve on this, we define a semaphore as an abstract data type whose operations are limited to:

• • initialization

  • acquire(); also called wait(s) or P(s)

  • release(); also called signal(s) or V(s)

definitions of acquire and release:

• • acquire() { while (value <= 0); value--; }

  • release() { value++; }

requirements

• • modifications to the semaphore value must be atomic

  • testing of semaphore value in acquire must be atomic

  • how can we guarantee these requirements?

Uses of semaphores

Using a binary semaphore for mutual exclusion:

Semaphore s = new Semaphore(1); s.acquire(); // critical section s.release(); // remainder section

Semaphores can also be used for many specific synchronization situations. If stmt1 in p₀ must execute before stmt2 in p2, then initialize a semaphore s to 0 (see Order.java):

Semaphore s=0; process p0 { stmt1; s.release(); } process p1 { s.acquire(); stmt2; }

The n-process critical section problem is solved by sharing one semaphore. If you initialize mutex to 5, then only 5 processes could execute their <cs> at once; it is flexible (see SemEx.java).

New defintions of acquire and release

What is the problem with the definitions of release() and acquire() above? busy waiting (i.e., the waiting process uses unproductive CPU cycles).

Spinlock: a semaphore busy waiting; it spins waiting for a lock.

In a uniprocessor system, its waits until its time slice expires.

A modification: define a waiting list L for each semaphore.

Now we define acquire() and release() as:

• • acquire() { value--; if (value < 0) { // add this process to list // block; } } release() { value++; if (value <= 0) { // remove process p from list // wakeup(p); } }

wakeup and block are basic OS system calls.

A semaphore value can now become negative, which indicates how many processes are waiting (e.g., if a semaphore value is -5, then 5 processes are waiting on that semaphore).

Semaphore a = new Semaphore(1, true); // makes the semaphore 'fair'

Two ways of waiting:

• • busy waiting: process which does the busy waiting first does not necessarily get to execute their <cs> first

  • queue: process which goes on the blocked queue first gets to execute their <cs> first.

Again, modifications to the semaphore value must be atomic, and testing of semaphore value in acquire must be atomic.

How to solve this ciritical section problem?

• • in a uniprocessor system

    • • disable interrupts, or

      • use any of the techniques presented above

        • • hardware instructions

          • Peterson's solution

  • in a multiprocessor environment, use techniques above

We have simply moved busy waiting to the <cs>s of the application programs, and limited busy waiting to the <cs> of the acquire() and release() operations.

Deadlock

Improper use of semaphores with wait queues can cause deadlock.

Deadlock means a group of processes are all waiting for each other for some event.

For example (the following system has the potential for deadlock; see Deadlock.java):

Semaphore s=1, q=1 process p0 { s.acquire(); q.acquire(); ... s.release(); q.release(); } process p1 { q.acquire(); s.acquire(); ... q.release(); s.release(); }

If p₀ executes S.acquire(), then p₁ executes Q.acquire(), the processes become deadlocked.

Solution:

Semaphore s=1, q=1; process p0 { // order matters a great deal on the waits q.acquire(); s.acquire(); ... // order does not matter that much on the signals s.release(); q.release(); } process p1 { // order matters a great deal on the waits q.acquire(); s.acquire(); ... // order does not matter that much on the signals q.release(); s.release(); }

Contrast deadlock with livelock, where a thread continuously attempts an action which fails.

Types of semaphores

• • binary semaphore (sometimes called a mutex lock): integer value can range only over 0 and 1

  • counting semaphore: integer value can range over an unrestricted domain

Semaphore type can be an issue of implementation, or simple how a semaphore is used.

Binary semaphores can be simpler to implement depending on hardware support.

Counting semaphores can be implemented using binary semaphores

Example

References

Classical probems of synchronization

• • The Bounded Buffer Problem (also called the The Producer-Consumer Problem)

• The Readers-Writers Problem

• The Dining Philosophers Problem

These problems are used to test nearly every newly proposed synchronization scheme or primitive.

The Bounded Buffer Problem

Consider:

• • a buffer which can store n items

  • a producer process which creates the items (1 at a time)

  • a consumer process which processes them (1 at a time)

A producer cannot produce unless there is an empty buffer slot to fill.

A consumer cannot consume unless there is at least one produced item.

Semaphore empty=N, full=0, mutex=1; process producer { while (true) { empty.acquire(); mutex.acquire(); // produce mutex.release(); full.release(); } } process consumer { while (true) { full.acquire(); mutex.acquire(); // consume mutex.release(); empty.release(); }

The semaphore mutex provides mutual exclusion for access to the buffer.

What are the semaphores empty and full used for?

The Readers-Writers Problem

A data item such as a file is shared among several processes.

Each process is classified as either a reader or writer.

Multiple readers may access the file simultaneously.

A writer must have exclusive access (i.e., cannot share with either a reader or another writer).

A solution gives priority to either readers or writers.

• • readers' priority: no reader is kept waiting unless a writer has already obtained permission to access the database

  • writers' priority: if a writer is waiting to access the database, no new readers can start reading

A solution to either version may cause starvation

• • in the readers' priority version, writers may starve

  • in the writers' priority version, readers may starve

A semaphore solution to the readers' priority version (without addressing starvation):

Semaphore mutex = 1; Semaphore db = 1; int readerCount = 0; process writer { db.acquire(); // write db.release(); } process reader { // protecting readerCount mutex.acquire(); ++readerCount; if (readerCount == 1) db.acquire(); mutex.release(); // read // protecting readerCount mutex.acquire(); --readerCount; if (readerCount == 0) db.release; mutex.release(); }

readerCount is a <cs> over which we must maintain control and we use mutex to do so.

Self-study: address starvation in this solution, and then develop a writers' priority semaphore solution, and then address starvation in it.

The Dining Philosophers Problem

n philosophers sit around a table thinking and eating. When a philosopher thinks she does not interact with her colleagues. Periodically, a philosopher gets hungry and tries to pick up the chopstick on his left and on his right. A philosopher may only pick up one chopstick at a time and, obviously, cannot pick up a chopstick already in the hand of neighbor philosopher.

The dining philosophers problems is an example of a large class or concurrency control problems; it is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner.

A semaphore solution:

// represent each chopstick with a semaphore Semaphore chopstick[] = new Semaphore[5]; // all = 1 initially process philosopher_i { while (true) { // pick up left chopstick chopstick[i].acquire(); // pick up right chopstick chopstick[(i+1) % 5].acquire(); // eat // put down left chopstick chopstick[i].release(); // put down right chopstick chopstick[(i+1) % 5].release(); // think } }

This solution guarantees no two neighboring philosophers eat simultaneously, but has the possibility of creating a deadlock (how so?).

Self-study: develop a deadlock-free semaphore solution.

Play the what if scenario game with all of these problems.

Uses of semaphores

Semaphores can be used for more than simply protecting a critical section.

• • protecting acccess to a critical section (e.g., db in the R/W problem)

  • as a mutex lock (e.g., to protect the shared variables used in solving a probem such as readerCount above)

  • to protect a relationship (e.g., empty and full as used in the P/C problem)

  • to support atomicity (e.g., you pickup either both chopsticks as the same time or neither, you cannot pickup just one)

References