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 PowCoder代写 加微信 powcoder

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: Dekker’s 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: Peterson’s 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 Dekker’s and Peterson’s 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 Solutions Interrupt Elevation  Processes give up the CPU either o voluntary: sleep, perform I/O, terminate, etc., or o 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 CAS compare-and-swap (IBM 370) exchange (x86)  The Test-and-Set Instruction test-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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com