Process Synchronization

Outline of this lecture

In this lecture, we will discuss the following:

• Background
• The Critical-Section Problem
• Solutions to the Critical-Section Problem
• Classical Problems of Synchronization

• To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data
• To present both software and hardware solutions of the critical-section problem
• To examine several classical process-synchronization problems
• To explore several tools that are used to solve process synchronization problems

Race condition

• Shared-memory solution to bounded-buffer problem (see lecture 4) has a race condition on the class data count.
• A situation where several processes access and manipulate the same data concurrently, and the outcome of the execution depends on the particular order in which access takes place.
• Two or more processes reading and writing some shared data and final result depends on who runs precisely when.
• To prevent race conditions, concurrent processes must be synchronized

The Critical Section (CS) Problem

• CS is the part of process code that manipulates shared data or resources.
• Execution of the CS should be mutually exclusive - If a process is in its CS, then no other process can be in the same CS.
• Each process must request permission to enter the CS in entry section, may follow critical section with exit section, then remainder section.
• The Critical section problem is to design a protocol that the processes can use to cooperate.

Solution to the Critical Section Problem must meet three

conditions...

1. Mutual Exclusion. If process Pi is executing in its critical section,

then no other processes can be executing in their critical sections.

2.

Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical sections, then only those processes that are not executing in their RS can participate in the decision on which will enter its CS next, & this selection cannot be postponed indefinitely.

1. Bounded Waiting. A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. This bound prevents Starvation

Types of Solutions

• Software solutions
  • algorithms who ’ s correctness does not rely on any other assumptions (OS or hardware)
• Hardware solutions
  • rely on special machine instructions
• Operating System solutions
  • provide special functions and data structures to the programmer

• Good algorithmic description of solving the problem
• Two process solution
• Assume that the load and store instructions are atomic; that is, cannot be interrupted
• The two processes share two variables:
  • int turn;
  • Boolean flag[2]
• The variable turn indicates whose turn it is to enter the critical section
• The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process is P i ready!

i

do {

flag[i] = true //process Pi is ready to enter its CS

;

turn = j; //process Pj is allowed to execute in its CS while (flag[j] && turn == j);

critical section

flag[i] = false;

remainder section

} while (true);



Provable that

1.

Mutual exclusion is preserved (

the value of turn can be either i or j but cannot be both)

2.

Progress requirement is satisfied (A process cannot immediately re-enter the critical section if the other process has set its flag to true)

3.

Bounded-waiting requirement is met (a process will not wait longer than one turn

Drawbacks of Software Solutions

• Complicated to program
• Processes that are requesting to enter in their critical section are busy waiting (consuming processor time needlessly)
• If CS are long, it would be more efficient to block processes that are waiting (just as if they had requested I/O).

• Many systems provide hardware support for critical section code
• All solutions below based on idea of locking
  • Protecting critical regions via locks
  • Design of locks can be sophisticated
• Uniprocessors – could disable interrupts
  • Currently running code would execute without preemption
  • Generally too inefficient on multiprocessor systems (must tell all CPUs)
    • Operating systems using this not broadly scalable
• Modern machines provide special atomic hardware instructions: Atomic = non-interruptable
  • Two types:
    • test memory word and set value
    • swap contents of two memory words

Definition:

boolean test_and_set (boolean *target) { boolean rv = *target; *target = TRUE; return rv: }

Executed atomically

1.

2.

Returns the original value of passed parameter

3.

Set the new value of passed parameter to “ TRUE ”

.

• Shared boolean variable lock, initialized to FALSE
• Solution: do { while (test_and_set(&lock))

; /* do nothing */ /* critical section */ lock = false; /* remainder section */ } while (true);

• Definition: void Swap (boolean *a, boolean *b)

{ boolean temp = *a; *a = *b; *b = temp:

}

• Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key
• Solution: do { key = TRUE; while (key == TRUE)

Swap (&lock, &key ); // critical section lock = FALSE; // remainder section } while (TRUE);

• Synchronization tool that does not require busy waiting.
• Semaphore S – integer variable
• can only be accessed via two indivisible (atomic) operations
• Two standard operations modify S: wait and signal
  • Originally called and V P
• Less complicated wait (S) { while (S <= 0) ; // busy wait S--; } signal (S) { S++; }

• Must guarantee that no two processes can execute wait and signal on the same semaphore at the same time
• Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section
  • Could now have busy waiting in critical section implementation
    • But implementation code is short
    • Little busy waiting if critical section rarely occupied
• Note that applications may spend lots of time in critical sections and therefore this is not a good solution

• With each semaphore there is an associated waiting queue
• Each entry in a waiting queue has two data items:
  • value (of type integer)
  • pointer to next record in the list
• Two operations:
  • block – place the process invoking the operation on the appropriate waiting queue
  • wakeup – remove one of processes in the waiting queue and place it in the ready queue

typedef struct{ int value; struct process *list; } semaphore; wait(semaphore *S) { S->value--; if (S->value < 0) { add this process to S->list; block; } } signal(semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(P); }

• Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
• Let and be two semaphores initialized to 1 S Q P P 0 1 wait (S); wait (Q); wait (Q); wait (S); . . . . signal (S); signal (Q); signal (Q); signal (S);
• Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
• When P0 executes Wait(Q), it must wait until P1 executes Signal (Q) and when P1 executes Wait(S) ), it must wait until P0 executes Signal(S) .

Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

• n buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0
• Semaphore empty initialized to the value n BUFFER

• The structure of the producer process do {

...

/* produce an item in next_produced */

...

wait(empty); //

synchronize the use of the bounded buffer

wait(mutex); //

protect the CS for a shared value

...

/* add next produced to the buffer */

...

signal(mutex); signal(full); } while (true);

 The structure of the consumer process do { wait(full); wait(mutex); ...

/* remove an item from buffer to next_consumed */

...

signal(mutex); signal(empty); ...

/* consume the item in next consumed */

...

• The structure of a reader process do { wait(mutex); // Mutex protects READCOUNT from all the READERS read count++; if (read count == 1) // 1 st reader captures rw mutex for all readers wait(rw mutex); signal(mutex);

...

/* reading is performed */

... wait(mutex);

read count--; if (read count == 0)

signal(rw mutex); signal(mutex); } while (true);

• Each philosopher is a process
• One semaphore per chopstick:
  • chopstick: array[0..4] of semaphores initialized to 1 do { wait (chopstick[i] ); wait (chopStick[ (i + 1) % 5] ); // eat signal (chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think } while (TRUE);
• Deadlock if each philosopher start by picking his left chopstick

• semaphores provide a powerful tool for enforcing mutual exclusion and coordinate processes
• But wait(S) and signal(S) are scattered among several processes. Hence, difficult to understand their effects
• Usage must be correct in all the processes
• Incorrect use of semaphore operations:
  • signal (mutex) ... . wait (mutex)
  • wait (mutex) ... wait (mutex)
  • Omitting of wait (mutex) or signal (mutex) (or both)
• Deadlock and starvation

• Are high-level language constructs that provide equivalent functionality to that of semaphores but are easier to control.
• But not powerful enough to model some synchronization schemes monitor monitor-name { // shared variable declarations procedure P1 (... ) { ... . } ... Procedure defined within the monitor procedure Pn (... ) { ...... } can access only those variables declared locally within the monitor Initialization code (... .) { ... } ... } } Syntax of a monitor

Operating System Solutions: Monitors

• Is a software module containing:
  • one or more procedures
  • an initialization sequence
  • local data variables
• Characteristics:
  • local variables accessible only by monitor ’ s procedures
  • a process enters the monitor by invoking one of its procedures
  • only one process can be in the monitor at any given time

Condition

• The monitor construct is not sufficiently powerful for modeling some synchronization schemes-→ need to define additional mechanisms.
• These mechanisms are provided by the condition construct.
• A programmer who needs to write a tailor-made synchronization scheme can define one or more variable of type condition:
• condition x, y;
• Two operations on a condition variable:
  • x.wait – a process that invokes the operation is suspended.
  • x.signal – resumes one suspended processes (if any) that invoked x.wait
    • If no x.wait on the variable, then it has no effect on the variable

• If process P invokes x.signal, with Q in x.wait state, what should happen next?
  • If Q is resumed, then P (signaling process) must wait
• Options include
  • Signal and wait
    • P waits until Q leaves monitor or waits for another condition
  • Signal and continue – Q waits until P leaves the monitor or waits for another condition
  • Both have pros and cons – language implementer can decide
  • Implemented in other languages including Mesa, C#, Java

void test (int i) { if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING;

self[i].signal;

} }

initialization_code {

for (int i = 0; i < 5; i++) state[i] = THINKING; }

}

Process Synchronization Conclusion

• A variety of methods exist, and each method has different variations.
• The most commonly used are semaphores and monitors.
• Monitors are the easiest to use, closest to programmer ’ s needs.
• The simpler mechanisms can be used to implement more sophisticated ones.
• No mechanism prevents in principle deadlocks, starvation, or busy waiting but more sophisticated mechanisms make it easier to avoid them.