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
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