[SOLVED] CS CMPUT 379 (E.S. Elmallah)

Process Synchronization
See chapter 5 in [SGG 9/E]
1. The critical section problem
2. A look back at history: algorithmic solutions

Copyright By Assignmentchef assignmentchef

3. Hardware based solutions
4. Synchronization primitives: semaphores and mutexes
5. Synchronization frameworks: monitors
6. Classic synchronization problems
CMPUT 379 (E.S. Elmallah)
1. The Critical Section Problem
Today we will examine a fundamental problem in concurrent processing.
Unix processes provide a very polished environment (with a high degree of independence and protection), hence, not very suitable for exposing some basic problems.
So, for a moment, set Unix processes aside: think of a more rudimentary environment (e.g., a simple implementation of threads).
CMPUT 379 (E.S. Elmallah)

(a) declare some global variables (b) execute some initializations (c) schedule to execute in parallel: P1() {local variables + code}
P2() {local variables + code}
Pn() {local variables + code}
(d) wait until all are done (e) do more computations
Our discussion uses the following simple environment of concurrency:
o Protection is granted for local variables only.
o Make no assumption about the relative speed of processes.
CMPUT 379 (E.S. Elmallah)
Example:
o What is the output: 10 , 500 , or a random number?
o A: either 10 or 500. Why?
o the memory interlock property: memory is not interrupted during a single write (read) cycle.
o Holds true even in a multiprocessor system
o DMA can steal memory cycles from the CPU (but
nothing can interrupt basic memory cycles).
CMPUT 379 (E.S. Elmallah)
int i= 10; P1(void) {print i; } P2(void) {i= 500; }

A critical section is a code segment that uses a shared variable .
A race condition arises when the outcome depends on the speed of processes; the computation becomes time critical .
The above calls for solving a synchronization problem.
CMPUT 379 (E.S. Elmallah)
How to fix?
Provide a mechanism to guarantee mutually exclusive access to critical sections.
A possible abstraction:
mutexBegin() allows one process at a time to access the critical section; forces the rest to wait.
mutexEnd() wakes up any waiting processes to enter the critical section.
CMPUT 379 (E.S. Elmallah)
mutexBegin();
access to shared variables
mutexEnd();

Issues to Discuss
What constitutes a good solution?
Can we implement mutexBegin()/End() algorithmically (i.e., relying only on memory interlock and busy-wait loops)? How?
What hardware features simplify the solution?
What useful synchronization primitives one can devise?
CMPUT 379 (E.S. Elmallah)
What Constitutes a Good Solution?
Must guarantee mutual exclusion,
achieve good concurrency: if a critical section is
available, any ready process can gain access to it o Progress condition: see textbook
achieve fair waiting among processes o Bounded waiting: see textbook
avoid deadlocks
CMPUT 379 (E.S. Elmallah)

2. A look back at history: algorithmic solutions
Attempt #1: (symmetric code)
Does it work?
int available= 1;
P1 (void) { for ( ; ; ) {
mutexBegin ( );
mutexEnd( );
P2 (void) { for ( ; ; ) {
mutexBegin ( );
mutexEnd( );
mutexBegin() : wait until (available == 1) available= 0;
mutexEnd(): available= 1;
CMPUT 379 (E.S. Elmallah)
Attempt #2: (asymmetric code)
Guarantees mutual exclusion; awful concurrency; fair waiting
int turn= 1;
P1 (void) {
#define my_turn 1 #define his_turn 2
for ( ; ; ) { mutexBegin ( );
mutexEnd( ); }
P2 (void) {
#define my_turn 2 #define his_turn 1
for ( ; ; ) { mutexBegin ( );
mutexEnd( ); }
mutexBegin() : wait until (turn == my turn) mutexEnd() : turn = his turn;
CMPUT 379 (E.S. Elmallah)

Attempt #3: (asymmetric code)
Guarantees mutual exclusion; both processes may block
int trying[2];
P0 (void) { for ( ; ; ) {
mutexBegin (0);
mutexEnd (0);
P1 (void) { for ( ; ; ) {
mutexBegin (1);
mutexEnd (1);
mutexBegin (i) : trying[i]= 1;
wait until the other is not trying
( i.e., trying[i+1 (mod 2)] == 0 ) mutexEnd(i) : trying[i]= 0;
CMPUT 379 (E.S. Elmallah)
Attempt #4: As in #3, except:
mutexBegin(i) : trying[i]= 1;
while (the other is trying) {
mutexEnd(i) :
trying[i]= 0;
wait for a random time; trying[i]= 1;
trying[i]= 0;
Expectation?
CMPUT 379 (E.S. Elmallah)

Attempt #5: Dekkers Algorithm [ 1965]
int turn= 1, trying[2];
P1 (void) {
#define my_turn 1 #define his_turn 2 for ( ; ; ) { }
P2 (void) {
#define my_turn 2 #define his_turn 1 for ( ; ; ) { }
mutexBegin(i) :
mutexEnd(i) :
trying[i]= 1;
while (the other is trying)
if (turn == his turn) { trying[i]= 0;
wait until it is my turn; trying[i]= 1;
turn= his turn;
trying[i]= 0;
CMPUT 379 (E.S. Elmallah)
Attempt #6: Petersons Algorithm [1981] int turn= 1, trying[2];
P1 (void) {
#define my_turn 1 #define his_turn 2 for ( ; ; ) { }
P2 (void) {
#define my_turn 2 #define his_turn 1 for ( ; ; ) { }
mutexBegin(i) : trying[i]= 1; turn= his_turn;
wait until (the other is not trying || it is my turn);
mutexEnd(i) : trying[i]= 0;
CMPUT 379 (E.S. Elmallah)

Both Dekkers and Petersons Algorithms can be generalized to N processes, but N must be known a priori, and the algorithms become complicated.
CMPUT 379 (E.S. Elmallah)
The Bakery Algorithm [Lamport 1974]
o Solves the problem for N processes, with a limit on the waiting time before entering the critical section.
Global vars: mutexBegin(i) :
int choosing[N], number[N]; choosing[i]= true;
number[i]= 1 + the max. chosen number; choosing[i]= false;
for (j= 0; j < N; j++) {wait until (Pj is not choosing); wait until (number[j] == 0 ||(number[i],i) < (number[j],j)) }number[i]= 0;CMPUT 379 (E.S. Elmallah)mutexEnd(i) : Exercises:o What if one (or more) number[.] overflows? o What if we omit the first wait statement?CMPUT 379 (E.S. Elmallah) 3. Hardware Based SolutionsInterrupt Elevation Processes give up the CPU eithero voluntary: sleep, perform I/O, terminate, etc., oro involuntary: e.g., a timer interrupts at the end of a time slice So, raising the interrupt level can be used to avoid context switching during a critical section. The solution is simple, and scales to n processes, but uses privileged instructions.CMPUT 379 (E.S. Elmallah)Atomic Read-Modify-Write Instructions Examples: o CAScompare-and-swap (IBM 370) exchange (x86) The Test-and-Set Instructiontest-and-set (Motorola 68K)Syntax: TAS Size: byte Description:
1. the current value of the operand is tested and the N and the Z flags are set accordingly.
2. the high order bit of the operand is set. Remark: uses a special read-modify-write bus cycle.
CMPUT 379 (E.S. Elmallah)
A typical use:
wait: tas sem_available
move.b
# the critical section
# the critical section #0, sem_available
sem_available: .skip 1
So, TAS solves the critical section problem for any number of processes
CMPUT 379 (E.S. Elmallah)

4. Synchronization Primitives
A primitive is a simple programming feature that can be used without knowing the exact implementation.
Typical synchronization primitives: semaphores [Dijkstra 65], critical regions [Hoare 72], lock/unlock, monitors [Hoare 7x, Hansen 7x], etc.
CMPUT 379 (E.S. Elmallah)
Semaphores: Basic Concept
Semaphores [binary, busy waiting]
A small integer S, used by two indivisible operations:
o P(S ): wait until S > 0 and then subtract 1 from S; [P for PROBEREN (probe/test)]
o V(S): Add 1 to S; wake up one of the waiting processes
[V for VERHOGEN (release, or make higher)]
Wealsousewait(S)andsignal(S)torefertoP(S),and
V(S), respectively.
Busy waiting (aka spinlock): implement wait() by looping continuously until the semaphore is released.
CMPUT 379 (E.S. Elmallah)

Semaphores [counting, busy waiting]
Usage: controlling a resource consisting of a finite number of instances
May be defined as:
o P(S): wait until S > 0; subtract 1 from S;
o V(S): Add 1 to S; wake up one of the waiting processes;
CMPUT 379 (E.S. Elmallah)
semaphore mutex= 1; wait (&mutex);
access critical data; signal (&mutex);
Exercises:
o Implement a counting semaphore using a binary
semaphore.
o Implement wait( ) and signal( ) using TAS( ) .
o Implement a non busy waiting semaphore using TAS( ) .
In conclusion (pros[+ve] and cons[-ve]):
o [+ve] semaphores are simple constructs,
o [ve] their use is not enforced, but is by convention only, and
o [ve] the above definitions do not allow a test for busy without a commitment to blocking.
CMPUT 379 (E.S. Elmallah)

Case Studies
In Unix, APIs exist for
o Mutexes: binary semaphores
o Semaphores: counting semaphores
POSIX Semaphores
See the manual pages (man sem_overview)
Typically used by multiple threads within one process.
#include
int sem_init(sem t *sem, int pshared, unsigned int value);
Initializes sem to value
pshared=0 means that sem is not shared between
processes.
CMPUT 379 (E.S. Elmallah)
int sem_wait (sem_t *sem);
The calling thread blocks until the count in the semaphore > 0, then atomically decrement it.
int sem_post (sem t *sem);
Atomically increment sem by 1. When any threads is blocked on the semaphore, one of them is unblocked.
See also Mutexes in the Pthreads API ([APUE 3/E], Section 11.6)
CMPUT 379 (E.S. Elmallah)

System V IPC
Provide a unified interface to 3 types of facilities: message queues, semaphores, and shared memory segments
Each IPC facility (e.g., a particular semaphore) is known to the kernel by an ID number (an integer)
Once created, a facility has read/write permissions for owner, group, and others
Highlights of the semaphores API: o older than POSIX semaphores
CMPUT 379 (E.S. Elmallah)
o create an array of semaphores:
#include
#include
int semget (key_t KEY, int NSEMS, int SEMFLG);
Creates an array of NSEMS semaphores in the kernel with properties defined by SEMFLG; returns a semaphore SEMID.
CMPUT 379 (E.S. Elmallah)

o perform operations:
int semop (int SEMID, struct sembuf *SOPS, size_t NSOPS);
SOPS is a pointer to an array of structures; each structure contains (among other things), an operation to be performed.
A +ve integer increments the semaphore by that amount A ve integer decrements the semaphore; by default, an
attempt to set a negative value blocks
A zero value means to wait for the semaphore value to reach zero
Other APIs
Solaris Condition Variables, Read-Write Locks CMPUT 379 (E.S. Elmallah)
5. Synchronization frameworks: Monitors
Monitors encapsulate: shared data , initialization code, entry procedures , and condition variables .
o Rule: At most one process inside the monitor
CMPUT 379 (E.S. Elmallah)

Monitors provide a block/wakeup facility as follows:
o Waiting for a condition variable (say x): Upon entering, a procedure finds x false
a procedure executes x.wait()
o Waking up a process waiting for condition x :
if a process enters the monitor and finds x is true then it
sends a signal to x s queue a process executes x.signal()
CMPUT 379 (E.S. Elmallah)
Question: What if P5 executes x.signal( ) :
o Does P3 execute immediately, and P5 waits under
waiting signalers? Or
o Does P3 wait until P5 leaves the monitor?
o Note: the situation may change if P5 is permitted to continue working.
Exercise:
o How does Concurrent Pascal deal with the above
o Implement a monitor with condition variables using semaphores.
CMPUT 379 (E.S. Elmallah)

6. Classical Synchronization Problems
Recall, criteria for good solutions
o Mutual Exclusion, progress, deadlocks, starvation
The Bounded-Buffer Problem
o Shared Variables: a finite buffer
o Processes: producers and consumers
(a) no lost items, no corrupt writes,
(b) producers wait if buffer is full, and (c) consumers wait if buffer is empty
CMPUT 379 (E.S. Elmallah)
The Readers and Writers Problem
o Shared Variables: an infinite buffer o Processes: readers and writers
(a) is as above, and either
(b ) readers wait only if a writer is active, or
(b ) readers may read only if no writer is waiting
CMPUT 379 (E.S. Elmallah)

The Dining-Philosophers Problem
o Shared Variables: chopsticks
o Processes: philosophers {thinking, hungry, eating}
(a) Need two chopsticks to eat (pick one at a time) (b) Put down chopsticks when finished
CMPUT 379 (E.S. Elmallah)
The Cigarette-Smokers Problem
o Shared Variables: tobacco, paper, and matches o Processes: agent, and 3 smokers
(a) The agent has an infinite supply of all ingredients
(b) Each smoker has exactly one of the ingredients
(c) The agent puts two ingredients on a table, the smoker who have the remaining ingredient makes a cigarette, signaling the agent on completion
The Sleeping
CMPUT 379 (E.S. Elmallah)

A Monitor Based Solution to the Dining-Philosophers
CMPUT 379 (E.S. Elmallah)
monitor dining_philosophers {
int state[5]; // THINKING, HUNGRY, EATING condition self[5];
void pickup (int i) {
state[i]= HUNGRY; test(i);
If (state[i] != EATING) self[i].wait(); }
void putdown (int i)
{ state[i]= THINKING; test ( (i+4)%5 ); test ( (i+1)%5 ); }
void test (int i) {
if (state[(i+4)%5] != EATING && state[i] == HUNGRY &&
state[ (i+1)%5 ] != EATING)
{ state[i]= EATING; self[i].signal(); }
void init () { for(i=0; i <= 4; i++) state[i]= THINKING; }CMPUT 379 (E.S. Elmallah) CS: assignmentchef QQ: 1823890830 Email: [email protected]