EECS 3221 Synchronization Tools PDF

Synchronization Tools Dr. Ruba Al Omari EECS 3221 – Operating Systems Fundamentals Reference  The lecture notes in this course are based on the textbook.  Unless otherwise specified, all the figures, tables, code examples, and content are from the textbook: Operating System Concepts...

Synchronization Tools Dr. Ruba Al Omari EECS 3221 – Operating Systems Fundamentals Reference  The lecture notes in this course are based on the textbook.  Unless otherwise specified, all the figures, tables, code examples, and content are from the textbook: Operating System Concepts, 10th Edition, by Silberschatz, Gagne, & Galvin, published by Wiley Where we are…  Overview  Introduction  Operating System Structures  Process Management  Processes  Threads and Concurrency  CPU Scheduling  Process Synchronization  Synchronization Tools  Synchronization Examples  Deadlocks  Memory Management  Main Memory  Virtual Memory  Storage Management  Security and Protection Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Background  We've already seen that processes can execute concurrently or in parallel.  May be interrupted at any time, partially completing execution. Background  Concurrent access to shared data may result in data inconsistency.  Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating.  A process that can affect or be affected by other processes executing in the system.  Race Condition  A situation in which several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place. Image Source: https://en.wikipedia.org/wiki/Race_condition Race Condition Example  Processes P0 and P1 are creating child processes using the fork()system call.  Race condition on kernel variable next_available_pid which represents the next available process identifier (pid).  Unless there is mutual exclusion, the same pid could be assigned to two different processes! Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Critical-Section Problem  Consider a system of n processes {p0, p1, … pn-1}  Each process has a critical section segment of code:  Process may be accessing and updating data (common variables, updating table, writing file,…) that is shared with at least one other process.  When one process is in its critical section, no other may be in its critical section.  Critical section problem is to design a protocol to solve this. Critical-Section Problem  Each process must ask permission to enter its critical section in entry section, may follow critical section with exit section, then remainder section. General Structure of Process Pi Solution to Critical-Section Problem  Any solution should have the following three conditions: 1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections. Solution to Critical-Section Problem  Any solution should have the following three conditions: 2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Solution to Critical-Section Problem /2  Any solution should have the following three conditions: 3. Bounded Waiting - A bound (limit) must exist on the number of times that other processes can enter their critical sections after a process has made a request to enter its critical section and before that request is granted:  Assume that each process executes at a nonzero speed.  No assumption concerning relative speed of the n processes. Critical-Section in Single Core  The critical-section problem could be simply solved in a single- core environment:  If we could prevent interrupts from occurring while a shared variable was being modified.  Unfortunately, this solution is not as feasible in a multiprocessor environments. Why?  System efficiency decreases dramatically as all processors will be disabled. Critical-Section Handling in OS  Two general approaches depending on if the kernel is preemptive or non- preemptive: 1. Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU.  Essentially free of race conditions in kernel mode as only one process is active in the kernel at a time. 2. Preemptive – allows preemption of process while it is running in kernel mode.  Must be carefully designed to ensure that shared kernel data are free from race conditions. Critical-Section Handling in OS Preemptive kernels are especially difficult to design for SMP architectures, why?  In these environments it is possible for two kernel-mode processes to run simultaneously on different CPU cores.  Why, then, would anyone favor a preemptive kernel over a non-preemptive one?  More responsive! Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Software-Based Approaches to CS  Software approaches can be implemented for concurrent processes that execute on a single-processor or a multiprocessor machine with shared main memory.  A classic software base solution to the critical solution problem is Peterson’s Solution.  Dekker’s Algorithm  Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming.  It allows two threads to share a single-use resource without conflict, using only shared memory for communication. https://en.wikipedia.org/wiki/Theodorus_Dekker & https://staff.fnwi.uva.nl/t.j.dekker/ https://en.wikipedia.org/wiki/Edsger_W._Dijkstra Dekker’s Algorithm – 1 Attempt st  Any attempt at mutual exclusion must rely on some fundamental exclusion mechanism in the hardware:  Only one access to a memory location can be made at a time.  We reserve a global memory location labelled turn that is shared between the two processes: int turn;  Dekker’s Algorithm – 1 Attempt st  A process (P0 or P1) wishing to execute its critical section first examines the contents of turn:  If turn = the number of the process, then the process may proceed to its critical section.  Otherwise, it is forced to wait (busy waiting, or spin waiting).  Is mutual exclusion guaranteed?  Yes  So, what is the problem? Source: Operating Systems: Internals and Design Principles, 9th Edition, by William Stalling Dekker’s Algorithm – 1 Attempt - Drawbacks st  Processes must strictly alternate in their use of their critical section.  The pace of execution is dictated by the slower of the two processes. Your turn P1 I know, thank you P0 I need to use the CS It’s still my turn Then use it! I am not ready yet! P0 P1 Dekker’s Algorithm – 1 Attempt - Drawbacks st  If one process fails, the other process is permanently blocked.  This is true whether a process fails in its critical section or outside of it. Something went Is it my turn? wrong and I can’t I’m busy waiting… exit the CS and Is it my turn?  change the turn I’m spin waiting… flag! Is it my turn? P0 P1 Dekker’s Algorithm – 2 Attempt nd  Each process should have its own key (flag) to the critical section so that if one fails, the other can still access its critical section.  Each process may examine the other’s flag but may not alter it.  The two processes share a Boolean vector flag Dekker’s Algorithm – 2 Attempt - Drawbacks nd  What problems may occur? Is mutual exclusion guaranteed?  If a process fails inside its critical section or after setting its flag to true just before entering its critical section, then the other process is permanently blocked. Dekker’s Algorithm – 2 Attempt - Drawbacks nd  Does not even guarantee mutual exclusion: 1. P0 executes the while statement and finds flagset to false 2. P1 executes the while statement and finds flagset to false 3. P0 sets flag to true and enters its critical section 4. P1 sets flag to true and enters its critical section  Because both processes are now in their critical sections, the program is incorrect. Dekker’s Algorithm – 3 Attempt rd  Because a process can change its state after the other process has checked it but before the other process can enter its critical section, the 2nd attempt failed.  Fix this problem with a simple interchange of the two statements.  Is mutual Exclusion guaranteed?  Yes Dekker’s Algorithm – 3 Attempt - Drawbacks rd  If both processes set their flags to true before either has executed the while statement, then each will think that the other has entered its critical section, causing deadlock. P0: Flag(0) = True P1: Flag(1) = True I have to wait, Flag(1) = True I have to wait, Flag(0) = True Dekker’s Algorithm – 4 Attempt th  Each process sets its flag to indicate its desire to enter its critical section, but is prepared to reset the flag to defer to the other process.  Is mutual exclusion guaranteed?  Yes Dekker’s Algorithm – 4 Attempt - Drawbacks th  Consider the following sequence of events: 1. P0 sets flag to true. 2. P1 sets flag to true. 3. P0 checks flag. 4. P1 checks flag. 5. P0 sets flag to false. 6. P1 sets flag to false. 7. P0 sets flag to true. 8. P1 sets flag to true.  This condition is referred to as livelock.  Won’t sustain for a long time but possible scenario! Dekker’s Algorithm – Correct Solution boolean flag; int turn;  When P0 wants to enter its critical section: while (true) { 1. It sets its flag to true. flag[i] = true; 2. It then checks the flag of P1. while (flag[j]) { 3. If that is false, P0 may immediately enter its critical if (turn == j) { section. flag[i] = false; while (turn == j) 4. Otherwise, P0 consults turn. ; 5. If P0 finds that turn= 0, then it knows that it is its flag[i] = true; } turn to insist and periodically checks P1’s flag. }  P1 will at some point note that it is its turn to defer and set its flag to false, allowing P0 to proceed.  After P0 has used its critical section: turn = j; flag[i] = false;  Sets turn=1 to transfer the right to insist to P1, and  It sets its flag to false to free the critical section. }  Dekker’s Algorithm – Correct Solution Source: Operating Systems: Internals and Design Principles, 9th Edition, by William Stalling Peterson’s Solution  Dekker’s algorithm solves the mutual exclusion problem, but with a rather complex program that is difficult to follow.  So comes Peterson who provides a simple, elegant algorithm for mutual exclusion.  It allows two processes to share a single-use resource without conflict, using only shared memory for communication.  It is kind of rewriting Dekkers algorithm. Peterson’s Solution  Two process solution.  Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted.  The two processes share two variables:  int turn;  boolean flag  The variable turn indicates whose turn it is to enter the critical section.  The flag array is used to indicate if a process is ready to enter the critical section.  flag[i]=true implies that process Pi is ready! Algorithm for Process Pi  To enter the critical section, process Pi first sets flag[i]=true and then sets turn=j (i.e., if the other process wishes to enter the critical section, it can do so). while (true){ flag[i] = true; turn = j; while (flag[j] && turn = = j) ; flag[i] = false; } Peterson’s Solution  Meets Critical-Section requirements : 1. Mutual exclusion is preserved Pi enters CS only if: either flag[j]=false or turn=i 2. Progress requirement is satisfied. 3. Bounded-waiting requirement is met. Peterson’s Solution  Although useful for demonstrating an algorithm, Peterson’s Solution is not guaranteed to work on modern architectures.  Understanding why it will not work is also useful for better understanding race conditions.  To improve performance, processors and/or compilers may reorder operations that have no dependencies.  For single-threaded this is ok as the result will always be the same.  For multithreaded the reordering may produce inconsistent or unexpected results! Modern Architecture Example  Two threads share flag and x variables: boolean flag = false; int x = 0;  100 is the expected output.  Thread 1 performs  However, the operations for Thread 2 may be while (!flag) reordered: ; flag = true; print x x = 100;  Thread 2 performs  If this occurs, what would be the output? x = 100;  The output will be 0! flag = true;  What is the expected output?  Peterson’s Solution Revisited  The effects of instruction reordering in Peterson’s Solution allows both processes to be in their critical section at the same time! Original Reordered while (true){ while (true){ flag[i] = true; turn = j; turn = j; flag[i] = true; while (flag[j] && turn = = j) while (flag[j] && turn = = j) ; ; flag[i] = false; flag[i] = false; } } Peterson’s Solution Revisited while (true){ turn = j;  Process 0: turn = 1; flag[i] = true;  Process 1: turn = 0; while (flag[j] && turn = = j) ;  Process 1: flag = true;  Process 1: while(flag && turn==0) // terminates, flag[i] = false; since flag==false  Process 1: enter critical section 1 }  Process 0: flag = true;  Process 0: while(flag && turn==1) // terminates, since turn==0  Process 0: enter critical section 0 Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Hardware Support for Synchronization  Many systems provide hardware support for implementing the critical section code.  We will look at two forms of hardware support: 1. Memory Barrier (aka memory fences) 2. Hardware Instructions Memory Model  How a computer architecture determines what memory guarantees it will provide to an application program is known as its memory model.  Memory models may be either:  Strongly ordered – where a memory modification of one processor is immediately visible to all other processors.  Weakly ordered – where a memory modification of one processor may not be immediately visible to all other processors. Memory Barrier  A memory barrier is an instruction that forces any change in memory to be propagated (made visible) to all other processors in the system.  Even if instructions were reordered, the memory barrier ensures that the store operations are completed in memory and visible to other processors before future load or store operations are performed. Memory Barrier Example  We could add a memory barrier to the following instructions to ensure Thread 1 outputs 100:  Thread 1 now performs while (!flag) memory_barrier(); print x  Thread 2 now performs x = 100; memory_barrier(); flag = true  For Thread 1 we are guaranteed that the value of flag is loaded before the value of x.  For Thread 2 we ensure that the assignment to x occurs before the assignment flag. Hardware Instructions  Many modern computer systems provide special hardware instructions that allow us to test and modify a word atomically— that is, as one uninterruptible unit:  test_and_set() instruction.  compare_and_swap() instruction. test_and_set Instruction  Definition: boolean test_and_set (boolean *target) { boolean rv = *target; *target = true; return rv: }  Properties: 1. Executed atomically. 2. If two test_and_set() instructions are executed simultaneously (each on a different core), they will be executed sequentially in some arbitrary order. 3. Returns the original value of the passed parameter. 4. Set the new value of the passed parameter to true. Solution using test_and_set  Shared Boolean variable lock, initialized to false  Solution: do { while (test_and_set(&lock)) ; lock = false; } while (true); Mutual-exclusion implementation with test_and_set(). Compare_and_swap Instruction  Definition: int compare_and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == expected) *value = new_value; return temp; } 1.Executed atomically. 2.Returns the original value of the passed parameter value. 3.Set the variable value the value of the passed parameter new_value but only if *value == expected is true. That is, the swap takes place only under this condition. Solution using compare_and_swap  Shared integer lock initialized to 0;  Solution: while (true){ while (compare_and_swap(&lock, 0, 1) != 0) ; lock = 0; } Mutual exclusion with the compare_and_swap() instruction. Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Mutex Locks  Previous solutions are complicated and generally inaccessible to application programmers.  OS designers build software tools to solve critical section problem.  Simplest is mutex lock. Solution to CS Problem Using Mutex Locks  A Mutex is a Boolean variable indicating if lock is available or not. while (true) { acquire lock  Protect a critical section by: critical section  First acquire() a lock  Then release()the lock release lock remainder section  Calls to acquire() and release() must be } atomic.  Usually implemented via hardware atomic instructions such as compare-and-swap. Mutex Locks acquire() { while (!available) ; available = false; } release() { available = true; }  These two functions must be implemented atomically.  Both test_and_set and compare_and_swap can be used to implement these functions. Mutex Locks Drawback  This solution requires busy waiting:  While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().  This lock therefore is called a spinlock:  If a lock is to be held for a short duration, one thread can “spin” on one processing core while another thread performs its critical section on another core. How Short is “Short Duration”?  Waiting on a lock requires two context switches:  A context switch to move the thread to the waiting state  A second context switch to restore the waiting thread once the lock becomes available  The general rule is to use a spinlock if the lock will be held for a duration of less than two context switches. Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Semaphores  Basic Idea: Two or more processes can cooperate by means of simple signals, such that a process can be forced to stop at a specified place until it has received a specific signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. Semaphores  Synchronization tool that provides more sophisticated ways (than Mutex locks) for processes to synchronize their activities.  A semaphore S is an integer variable, that can only be accessed via two atomic operations: 1) wait(): decrements the semaphore value.  Originally called P(), from the Dutch proberen, “to test”, semWait() 2) signal(): increments the semaphore value  Originally called V(), from verhogen, “to increment”, semSignal() wait() and signal()  Definition of the wait() operation wait(S) { while (S value--; if (S->value < 0) { add this process to S->list; sleep(); } } signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } Semaphores Usage Example Processes Accessing Shared Resource Protected by a Semaphore The Strength of a Semaphore  A strong semaphore uses a queue (FIFO) of blocked processes. The process unblocked is the one in the queue for the longest time.  A weak semaphore uses a set of blocked processes. The process unblocked is unpredictable. Process Starvation?!? Problems with Semaphores  Incorrect use of semaphore operations:  signal(mutex) …. wait(mutex)  wait(mutex) … wait(mutex)  Omitting of wait (mutex) and/or signal (mutex)  These – and others – are examples of what can occur when semaphores and other synchronization tools are used incorrectly.  In these cases, either mutual exclusion is violated, or the process will permanently block. Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors Monitors  A high-level abstraction that provides a convenient and effective mechanism for process synchronization.  A monitor type presents a set of programmer-defined operations that are provided with mutual exclusion within the monitor.  Implemented in a number of programming languages including Java. Monitors  The local data variables are accessible only by the monitor’s procedures and not by any external procedure.  A process enters the monitor by invoking one of its procedures.  Only one process may be executing in the monitor at a time. monitor monitor-name { // shared variable declarations function P1 (…) { …. } function P2 (…) { …. } function Pn (…) { …. } initialization code (…) { … } } Monitor Implementation Using Semaphores  Variables semaphore mutex mutex = 1  Each procedure P is replaced by wait(mutex); … body of P; … signal(mutex);  Mutual exclusion within a monitor is ensured Condition Variables  However, the monitor construct, as defined so far, is not sufficiently powerful for modeling some synchronization schemes.  Programmers could use the condition variables to extend the functionalities of a monitor.  condition x, y;  Two operations are allowed on a condition variable:  x.wait()– a process that invokes the operation is suspended until x.signal()  x.signal()– resumes one of processes (if any) that invoked x.wait()  If no x.wait() on the variable, then it has no effect on the variable Monitor with Condition Variables Liveness  Processes may have to wait indefinitely while trying to acquire a synchronization tool such as a mutex lock or semaphore.  Waiting indefinitely violates the progress and bounded-waiting criteria discussed earlier.  Liveness refers to a set of properties that a system must satisfy to ensure processes make progress.  Indefinite waiting is an example of a liveness failure.  Examples: infinite loop, busy waiting loop, a deadlock. Liveness  Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes  Let S and Q be two semaphores initialized to 1 Liveness  Consider if P0 executes wait(S) and P1 wait(Q). When P0 executes wait(Q), it must wait until P1 executes signal(Q)  However, P1 is waiting until P0 execute signal(S).  Since these signal() operations will never be executed, P0 and P1 are deadlocked. Topics  Background  The Critical-Section Problem  Software Approaches  Hardware Support for Synchronization  OS & Programming Languages Approaches:  Mutex Locks  Semaphores  Monitors