Process Synchronization

Chapter 6 Process Synchronization Cooperating Process process that can affect or be affected by other processes directly share a logical address space (threads) be allowed to share data via files or messages concurrent access to shared data may result in data inconsistency Race Condition Multiple processes access and manipulate a variable counter concurrently Outcome depends upon the particular order in which the access takes place Process Synchronization & Coordination Critical Section Implementation do { Entry Section Critical Section Exit Section Remainder Section } while(true); Operating System Critical Sections (Race Conditions) Updating kernel data structures Open Files List Memory Allocation Structures Active Process Lists Inactive Process Lists Interrupt Handling Preemptive Kernels allows a process to be preempted while running in kernel mode may be subjected to race conditions difficult to design & implement in SMP highly desired in Real-Time Systems Non-preemptive Kernels does not allow a process to be preempted while running in kernel mode process will run until it o exits kernel mode o blocks o voluntarily yields control of the CPU not subject to race conditions Critical Section Requirements Mutual Exclusion o only one process may be in its critical section the decision does not Progress wait for all processes to o no process is in its critical section complete executing their o one or more processes wants to enter its critical section remainder section code o only those processes not in their remainder sections can decide which process can enter its critical section o the decision cannot be postponed indefinitely Bounded Waiting o there is a bound on the number of times other processes may enter their critical sections after a process has made a request to enter its critical section Peterson’s Solution == software solution fails because of pipelines & parallel instruction streams Synchronization Hardware Atomic Hardware Instructions 1. TestAndSet(&lock); Hardware Definition boolean TestAndSet( boolean *target ); { boolean rv = *target; *target = TRUE; return rv; } fails the bounded waiting requirement rv FALSE P0 do { while(TestAndSet(&lock)); Software Implementation lock = false; do { while(TestAndSet(&lock)); // critical section lock = FALSE; // remainder section }while(TRUE); // critical section lock = FALSE; // remainder section lock FALSE TRUE }while(TRUE); Effect: lock = FALSE; executes TestAndSet(&lock); P0 gains access to its critical section; lock = TRUE; P1 executes TestAndSet(&lock); P1 hangs in the while(TestAndSet(&lock)) loop, i.e., spin cycle since (lock == TRUE) until P0 exits its critical section P1 do { while(TestAndSet(&lock)); // critical section lock = FALSE; // remainder section }while(TRUE); 2. Swap(&lock, &key) Hardware Definition void Swap(boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp; } fails the bounded waiting requirement Software Implementation do { key = TRUE; while(key == TRUE) Swap(&lock, &key); // critical section lock = FALSE; // remainder section }while(TRUE); P0 boolean key; do { key = TRUE; while(key == TRUE) Swap(&lock, &key); // critical section lock = FALSE; // remainder section }while(TRUE); P1 boolean key; do { key = TRUE; while(key == TRUE) Swap(&lock, &key); // critical section lock = FALSE; // remainder section }while(TRUE); P0 key TRUE FALSE P1 key lock FALSE FALSE TRUE P0 executes key = TRUE; P0 executes while(key == TRUE) and then P0 executes Swap(&lock, &key); P0 executes in its critical section P1 executes key = TRUE; P1 executes while(key == TRUE) and spinlocks because its key is FALSE P0 executes lock = FALSE;  P1 executes Swap(&lock, &key); 3. TestAndSet(&lock) Software Implementation which satisfies Mutual Exclusion, Progress, & Bounded Waiting Pi for , i.e., there are n+1 processes lock = FALSE; waiting[i] = FALSE; Pi boolean key = FALSE; do { waiting[i] = TRUE; key = TRUE; while(waiting[i] && key) key = TestAndSet(&lock); waiting[i] = FALSE; // critical section j = (i+1)%n; while((j != i) && !waiting[j]) j = (j+1)%n; if(j == i) lock = FALSE; else waiting[j] = FALSE; // remainder section }while(TRUE); P0 boolean key = FALSE; do { waiting[0] = TRUE; key = TRUE; while(waiting[0] && key) key = TestAndSet(&lock); waiting[0] = FALSE; // critical section j = 1; while((j != i) && !waiting[j]) j = (j+1)%2; if(j == 0) lock = FALSE; else waiting[j] = FALSE; // remainder section }while(TRUE); lock = true key = TestAndSet(&lock);  key == true && lock == true lock = false key = TestAndSet(&lock);  key == false && lock == true lock FALSE TRUE waiting 0 1 FALSE FALSE TRUE TRUE FALSE TRUE 2 FALSE P1 Pi boolean key = FALSE; do { waiting[1] = TRUE; key = TRUE; while(waiting[1] && key) key = TestAndSet(&lock); waiting[1] = FALSE; // critical section j = 2; while((j != 1) && !waiting[j]) j = (j+1)%2; if(j == 1) lock = FALSE; else waiting[j] = FALSE; // remainder section }while(TRUE); boolean key = FALSE; do { waiting[i] = TRUE; key = TRUE; while(waiting[i] && key) key = TestAndSet(&lock); waiting[i] = FALSE; // critical section j = 0; while((j != i) && !waiting[j]) j = (j+1)%2; if(j == 2) lock = FALSE; else waiting[j] = FALSE; // remainder section }while(TRUE); P0 starts waiting[0] = TRUE, P0 key = TRUE P0 enters the while loop and executes TestAndSet(&lock)  lock = TRUE && key = FALSE && waiting[0] = FALSE P0 drops thru the loop and enters its critical section P1 starts waiting[1] = TRUE, P1 key = TRUE P1 drops thru while loop and executes TestAndSet(&lock)  lock = TRUE && key = TRUE  P1 hangs in the while loop Pi enters Critical Section only if waiting[i] == false; or key == false; Semaphores API construct – implementation via synchronization hardware S: semaphore – integer variable directly initialized, i.e., assignment statement accessed only via atomic operations o wait( ) – proberen (P) “to test” o signal( ) – verhofen (V) “to increment” Definition -- wait( ) wait(S) { while (S <= 0 ); S- -; } Definition -- signal(S) atomic operations signal(S) { S++; } Counting Semaphore – unrestricted domain Binary Semaphore domain restricted to [0, 1] Mutex Locks – Binary Semaphores – provide Mutual Exclusion critical section – multiple processes  control access to a given resource Pi : processes 0 < i < n+1 consisting of n instances mutex mx = n; gain access to a resource, process executes wait(mx); releasing resource, process executes signal(mx); mx == 0  no resources available Synchronization Process P1 with statement S1 Process P2 with statement S2 synchronize statements: S1 must execute before S2 mutex synch = 0; Busy Waiting S1; signal(synch); wait(synch); S2; CPU cycles that could have been spend doing productive work are wasted processing waits Spinlock – multiprocessor systems – no context switch One thread can spin on one processor while another thread performs a critical section on another processor Blocking process finds mutex mx <= 0  process executes block( ) operation, i.e., o block( ) places process on queue associated with the mutex mx o process state is changed to the waiting state scheduler selects another process to execute executing process executes signal( ) operation process at head of wait queue is restarted with a wakeup( ) operation reawakened process is placed in the ready queue Blocking Semaphore typedef struct { int value; struct process *list; }semaphore; semaphore S; block( ) & wakeup( ) are basic system calls, they must also be atomic, i.e., must not be interruptible single processor: disable interrupts multiprocessor: spinlock wait(semaphore *S) { S  value- -; if ( S  value < 0 ) { // add the calling process to S  list; block( ); } } linked list of process control blocks signal(semaphore *S) { S  value++; if(S  value <= 0) { // remove a process, P, from S  list; wakeup(P); } } The proper use of semaphores is under the control of each individual programmer – one error and the system fails Starvation linked list is a LIFO queue, i.e., stack Deadlocks P0 wait(S); wait(Q); | signal(S); signal(Q); P1 wait(Q); wait(S); | signal(Q); signal(S); resource acquisition and release Priority Inversion higher priority process blocked by lower priority process modifying kernel data Priority Inheritance Protocol processes accessing resources which are controlled by a higher priority, e.g., kernel resources, inherit the higher priority until they have finished Monitor ADT (class-object) construct that encapsulates the proper sequences of wait( ) and signal( ) to ensure correct usage of semaphores monitor may contain multiple (user) procedures monitor ensures that only one procedure will be active at any one time condition variables condition x; condition operations wait( ) & signal( ) o process P0 invokes x.wait( );  P0 suspended until another process P1 issues x.signal( ) x.signal( ) resumes exactly one suspended process if there are no suspended processes, x.signal( ) has no effect signal( ) used in semaphores always has an effect process P1 issues x.signal( )  P0 resumes o P1 waits until P0 leaves the monitor signal & wait o P1 waits for another condition o P0 waits until P1 leaves the monitor signal & continue o P0 waits for another condition Dining-Philosophers Monitor monitor dp { enum {THINKING, HUNGRY, EATING} state[5];  possible states condition self[5];  provides a wait condition 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); } philosopher can only pickup the chopsticks if both of them are available; else changes condition to waiting when philosopher is finished eating, both chopsticks must be released; then a check is made as to philosophers on both the left and right sides of the relinquisher who may have requested access to the chopsticks void test(int i) { if ((state[(i + 4)%5] != EATING) && (state[ i ] == HUNGRY) && ((state[(i + 1)%5] != EATING) { state[ i ] = EATING; self[ i ].signal( ); } } Determines if the philosophers on either side of the requester are using the chopsticks; if not, the test returns the state of EATING to the requester, in effect, it allocates the chopsticks to the requester initialization_code( ) { for (int i = 0; i < 5; i++)state[ i ] = THINKING; } } Usage dp.pickup( i ); … // Philosopher i eats until full … dp.putdown( i ); Implementing a Monitor using Semaphores see Silberschatz pages 250-252 Java Monitors java.util.concurrency synchronized methods – lock acquisition lock’s entry set – set of threads waiting for the lock to become available wait( ) & notify( ) i.e., signal( ) semaphores, condition variables, mutex locks public class SimpleClass { … public synchronized void safeMethod( ) { … } … } SimpleClass sc = new SimpleClass( ); In order to execute sc.safeMethod( ) the thread on which object sc is running must own the lock; lock is available  calling thread becomes the owner of the lock if the lock is owned by another thread, the sc.safeMethod( ) thread blocks and is put on the entry set for the lock thread exits the method  lock is made available & a thread from the entry set is selected as the new owner of the lock Solaris semaphores (long code segments) condition variables (long code segments) adaptive mutex (short code segments) o standard semaphore – spinlock o data locked o lock held by thread running on another CPU, spin until released o thread holding lock is not running, blocks until awakened by lock release reader-writer locks (long code segments) turnstile o list of threads waiting to acquire  adaptive mutex  reader-writer lock o is a queue structure holding threads blocked on a lock turnstile acquisition o each synchronized object with a thread blocked on a lock requires its own turnstile o each kernel thread has a turnstile o the kernel turnstile on which the first thread blocks becomes the turnstile for the synchronized object  subsequent threads blocking on this same lock will be added to the same kernel turnstile o thread releases the lock  releasing object is ASSIGNED A NEW THREAD from a free turnstile list maintained by the kernel  kernel selects a new owner of the lock from the thread’s turnstile o priority-inheritance protocol  lower-priority thread currently holds a lock  higher-priority thread is currently blocked on the same lock  lower-priority thread acquires the priority of the higher-priority thread until it releases the lock Windows XP multithreaded kernel supports Real-Time processes multiple processors Kernel Threads UNIPROCESSOR SYSTEMS kernel thread accesses a global resource  disables all interrupt handlers with access to that resource MULTIPROCESSOR SYSTEMS kernel thread naccesses a global resource  uses spinlocks to protect access to that resource  ensures that threads holding spinlocks are not preempted User Threads Dispatcher Objects Signaled State o object is available; o thread will not block when acquiring the object Nonsignaled State o object is not available; o thread will block when attempting to acquire the object synchronizes threads by using o mutexes o semaphores o events o timers Events notify waiting threads that a desired condition has occurred Times notify thread(s) that a specified time interval has expired Actions thread blocks on a nonsignaled dispatcher object o thread state changes to waiting o thread is placed on a wait queue for that object dispatcher object changes state to signaled o if there are threads in the object’s wait queue, the kernel moves thread(s) to the ready state; if the queue is for  an Event Object  kernel moves all threads waiting for that event  a Mutex  kernel moves one thread to the ready state thread attempts to acquire a mutex dispatcher object in a nonsignaled state; thread is suspended and placed in a wait queue for the mutex object; another thread releases the mutex lock; thread at the front of the mutex queue has its state changed to ready and it acquires the mutex lock Linux (starting with Version 2.6) pre-emptive kernel Kernel Threads Spinlocks Semaphores Reader-Writer Spinlocks Reader-Writer Semaphores SYMMETRIC MULTIPROCESSOR SYSTEMS  acquiring/releasing short duration spinlocks UNIPROCESSOR SYSTEMS  enabling/disabling kernel preemption  preempt_disable( )  preempt_enable( )  kernel-mode task is holding a lock  kernel is not preemptible task  thread-info structure  preempt_count – number of locks held by the task  lock acquired  preempt_count ++;  lock released  preempt_count - -;  preempt_count > 0  not safe to preempt kernel  no outstanding call to preempt && preempt_count == 0  safe to preempt Pthreads API Mutex Locks o pthread_mutex_t first_mutex; o pthread_mutex_t second_mutex; o pthread_mutex_init (&first_mutex, NULL); o pthread_mutex_init (&second_mutex, NULL); o pthread_mutex_acquire( ); o pthread_mutex_lock( ); o pthread_mutex_unlock( ); Condition Variables Read-Write Locks Spinlocks – not all versions may be portable POSIX SEM Semaphores