10,
Process synchronization (concurrently) ( ) => critical section ( ) / =>, A, B /
Race condition int counter; Process A { counter++; } Process B { counter ;.. } counter++ register1 = counter register1 = register1 + 1 counter= register1 counter register2 = counter register2 = register2-1 counter = register2
Race condition When initially count = 5 S0: PA register1 = counter (register1 = 5) S1: PA register1 = register1+1 (register1 = 6) S2: PB register2 = counter (register2 = 5) S3: PB register2 = register2-1 (register2 =4) S4: PA counter = register1 (counter = 6) S5: PB counter = register2 (counter = 4)
Critical section problem => wait
Critical section
Solution to critical section problem Mutual exclusion Progress remainder section CS, Bounded waiting A,,, A =>
Peterson s solution For two processes int turn; boolean flag[2]; turn: CS? flag: flag[i] = true, i CS
Algorithm for process Pi do { flag[i] = true; turn = j; // process j CS while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true);, turn=i, turn=j, turn =>, turn => CS (flag[i], flag[j] true ) => mutual exclusion CS flag[] false, while() CS => progress, bounded-waiting
Peterson s solution Pi do { flag[i] = true; turn = j; while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true); Pj do { flag[j] = true; turn = i; while (flag[i] && turn == i); critical section flag[j] = false; remainder section } while (true);
Synchronization Hardware support for CS code Protecting CS via locks Uniprocessor system Multiprocessor system hardware =>? => atomic operation => API while (test_and_set(&lock)) ; //do nothing // critical section lock test_and_set => atomic
Bounded-waiting mutual exclusion with test_and_set do { waiting[i] = true; key = true; while (waiting[i] && key) key = test_and_set(&lock); waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j!= i) &&!waiting[j]) j = (j + 1) % n; if (j == i) else lock = false; waiting[j] = false; /* remainder section */ } while (true); process queue CS waiting[j] = false (lock )., CS (if (j ==i)) lock waiting[] true => mutual exclusion, progress, bounded-waiting
Mutex locks (test_and_set) acquire(), release() Atomic via hardware implementation Busy waiting Spinlock
Mutex locks acquire() { while (!available) } ; /* busy wait */ available = false;; release() { } available = true; do { acquire lock critical section release lock remainder section } while (true);
Semaphore Busy waiting S: semaphore variable, integer Counting semaphore: S >= 0 Binary semaphore: S = 0 or 1 wait(), signal() Should be implemented atomically wait() signal() - wait() CS semaphore list semaphore list wait signal() semaphore list ready
Semaphore P1 and P2 that require S1 to happen before S2 P1: S1; signal(synch); P2: wait(synch); S2;
Semaphore 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 and Starvation Let S and Q be two semaphore initialized to 1 P0: wait(s); wait(q); signal(s); signal(q); P1: wait(q); wait(s); signal(q); signal(s); P0 wait(s), P1 signal(s), P1 wait(q) P0 signal(q) => Deadlock!!
Classic problems of synchronization Bounded-buffer problem Readers and writers problem Dining philosophers problem
Bounded-buffer problem n item mutex: 1, full: 0, => empty empty: n, => full The structure of the producer process The structure of the consumer process do {... /* produce an item in next_produced */... wait(empty); wait(mutex);... /* add next produced to the buffer */... signal(mutex); signal(full); } while (true); do { wait(full); wait(mutex);... /* remove an item from buffer to next_consumed */... signal(mutex); signal(empty);... /* consume the item in next consumed */... } while (true);
Readers-writers problem concurrent process ( ) Readers - Writers - reader writer starvation Shared data Data set Semaphore rw_mutex: 1, writer Semaphore mutex: 1, read_count Integer read_count: 0
Readers-writers problem writer CS writer reader CS reader writer writer The structure of a writer process do { writer reader CS wait(rw mutex);... /* writing is performed */... signal(rw mutex); } while (true); The structure of a reader process do { wait(mutex); read_count++; if (read count == 1) wait(rw mutex); signal(mutex);... /* reading is performed */... wait(mutex); read count--; if (read count == 0) signal(rw mutex); signal(mutex); } while (true); - read_count 1 reader writer CS (wait(rw_mutex)) - read_count 1 reader CS - read_count 0 CS reader,, writer
Dining-philosophers problem : 6-14? Deadlock, 4
Monitor High-level abstraction Java, C# procedure => Monitor Monitor monitor monitor-name { // shared variable declarations procedure P1() { } procedure P2() { } procedure P3() { } initialization_code () { } }
Monitor
condition variables Monitor condition x; x.wait(), x.signal()
Monitor x
Monitor Solution to dining-philosophers monitor DiningPhilosophers { enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i]!= EATING) self [i].wait; } test(i) HUNGRY void putdown (int i) { state[i] = THINKING; // test left and right neighbors 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 () ; }, } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; }
Each processor i Monitor DiningPhilosophers.pickup(i); EAT DiningPhilosophers.putdown(i) Monitor deadlock,, starvation? HW #4
Pthread #include <pthread.h> pthread mutex_t mutex; pthread mutex_init(&mutex, NULL); pthread mutex_lock(&mutex); pthread mutex_unlock(&mutex); #include <semaphore.h> sem_t sem; sem_init(&sem, 0, 1); sem_wait(&sem); sem_post(&sem);
HW #5 P.347 2