Computer Operating System - Chapter 6: Synchronization Tools

Nội dung text: Computer Operating System - Chapter 6: Synchronization Tools

1. Chapter 6: Outline ! Background ! The Critical-Section Problem ! Peterson’s Solution ! Hardware Support for Synchronization ! Mutex Locks ! Semaphores ! Monitors ! Liveness ! Evaluation Operating System Concepts 2 Silberschatz, Galvin and Gagne ©2018
2. Background ! Processes can execute concurrently (or in parallel) " May be interrupted at any time, partially completing execution ! Concurrent access to shared data may result in data inconsistency ! Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes ! Illustration of the problem: #define BUFFER_SIZE 8 " Suppose that we wanted to provide /* 8 buffers */ a solution to the consumer- producer problem that fills all the typedef struct { buffers. We can do so by having an . . . integer counter that keeps track of } item; item buffer[BUFFER_SIZE]; the number of full buffers. Initially, counter is set to 0. It is incremented int in = 0; by the producer after it adds a new int out = 0; item to the buffer and is int counter = 0; decremented by the consumer after it consumes an item from the buffer Operating System Concepts 4 Silberschatz, Galvin and Gagne ©2018
3. Consumer while (true) { while (counter == 0) ; /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE;/* pointer out from buffer */ counter ; /* consume the item in next_consumed */ } Operating System Concepts 6 Silberschatz, Galvin and Gagne ©2018
4. Race Condition (Cont.) ! 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! Operating System Concepts 8 Silberschatz, Galvin and Gagne ©2018
5. Critical Section (CS) ! General structure of the process Pi Operating System Concepts 10 Silberschatz, Galvin and Gagne ©2018
6. Critical-Section Handling in OS ! Two approaches depending on if kernel is preemptive or non- preemptive " Preemptive – allows preemption of process when running in kernel mode " Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU 4 Essentially free of race conditions in kernel mode Operating System Concepts 12 Silberschatz, Galvin and Gagne ©2018
7. Algorithm for Process Pi while (true){ flag[i] = true; turn = j; while (flag[j] && turn == j) ; /* do nothing */ /* critical section */ flag[i] = false; /* remainder section */ } Operating System Concepts 14 Silberschatz, Galvin and Gagne ©2018
8. Remarks on 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! Operating System Concepts 16 Silberschatz, Galvin and Gagne ©2018
9. Example of Peterson’s Solution ! 100 is the expected output. ! However, the operations for Thread 2 may be reordered: flag = true; x = 100; ! If this occurs, the output may be 0! ! The effects of instruction reordering in Peterson’s Solution ! This allows both processes to be in their critical section at the same time! Operating System Concepts 18 Silberschatz, Galvin and Gagne ©2018
10. Memory Barriers ! Memory model is the memory guarantee that a computer architecture makes to application programs. ! 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. ! A memory barrier is an instruction that forces any change in memory to be propagated (made visible) to all other processors. Operating System Concepts 20 Silberschatz, Galvin and Gagne ©2018
11. Hardware Instructions ! Special hardware instructions that allow us to either test-and-modify the content of a word, or to swap the contents of two words atomically (uninterruptedly.) " Test-and-Set() instruction " Compare-and-Swap() instruction Operating System Concepts 22 Silberschatz, Galvin and Gagne ©2018
12. Solution using test_and_set() ! Shared Boolean variable lock, initialized to false ! Solution: do { while (test_and_set(&lock)) ; /* do nothing */ /* critical section */ lock = false; /* remainder section */ } while (true); Operating System Concepts 24 Silberschatz, Galvin and Gagne ©2018
13. Solution using compare_and_swap ! Shared integer lock initialized to 0; ! Solution: while (true){ while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ /* critical section */ lock = 0; /* remainder section */ } Operating System Concepts 26 Silberschatz, Galvin and Gagne ©2018
14. Atomic Variables ! Typically, instructions such as compare-and-swap are used as building blocks for other synchronization tools. ! One tool is an atomic variable that provides atomic (uninterruptible) updates on basic data types such as Integers and Booleans. ! For example, the increment() operation on the atomic variable sequence ensures sequence is incremented without interruption: increment(&sequence); Operating System Concepts 28 Silberschatz, Galvin and Gagne ©2018
15. 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 ! Protect a critical section by first acquire() a lock then release() the lock " Boolean variable indicating if lock is available or not ! Calls to acquire() and release() must be atomic " Usually implemented via hardware atomic instructions such as compare- and-swap ! But this solution requires busy waiting " This lock therefore called a spinlock Operating System Concepts 30 Silberschatz, Galvin and Gagne ©2018
16. Mutex Lock Definitions 4 acquire() { while (!available) ; /* busy wait */ available = false;; } 4 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 Operating System Concepts 32 Silberschatz, Galvin and Gagne ©2018
17. Semaphore Usage ! Counting semaphore – integer value can range over an unrestricted domain ! Binary semaphore – integer value can range only between 0 and 1 " Same as a mutex lock " Can solve various synchronization problems ! Can implement a counting semaphore S as a binary semaphore P1: ! Consider P1 and P2 that require S1 to happen before S2 S1; signal(synch); " Create a semaphore “synch” initialized to 0 P2: wait(synch); S2; Operating System Concepts 34 Silberschatz, Galvin and Gagne ©2018
18. Semaphore Implementation with no Busy waiting ! With each semaphore there is an associated waiting queue ! Each entry in a waiting queue has two data items: " value (of type integer) " pointer to next record in the list ! Two operations: " block – place the process invoking the operation on the appropriate waiting queue " wakeup – remove one of processes in the waiting queue and place it in the ready queue typedef struct { int value; struct process *list; } semaphore; Operating System Concepts 36 Silberschatz, Galvin and Gagne ©2018
19. Problems with Semaphores ! Incorrect use of semaphore operations: " signal(mutex) . wait(mutex) " wait(mutex) signal(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. Operating System Concepts 38 Silberschatz, Galvin and Gagne ©2018
20. Schematic View of a Monitor Operating System Concepts 40 Silberschatz, Galvin and Gagne ©2018
21. Monitor with Condition Variables Operating System Concepts 42 Silberschatz, Galvin and Gagne ©2018
22. Monitor Implementation using Semaphores ! Variables semaphore mutex; /*(initially = 1)*/ semaphore next; /*(initially = 0)*/ int next_count = 0; ! Each function F will be replaced by wait(mutex); body of F; if (next_count > 0) signal(next) else signal(mutex); ! Mutual exclusion within a monitor is ensured Operating System Concepts 44 Silberschatz, Galvin and Gagne ©2018
23. Monitor Implementation (Cont.) ! The operation x.signal() can be implemented as: if (x_count > 0) { next_count++; signal(x_sem); wait(next); next_count ; } Operating System Concepts 46 Silberschatz, Galvin and Gagne ©2018
24. Single Resource allocation ! Allocate a single resource among competing processes using priority numbers that specify the maximum time a process plans to use the resource R.acquire(t); access the resurce; R.release; ! Where R is an instance of type ResourceAllocator Operating System Concepts 48 Silberschatz, Galvin and Gagne ©2018
25. 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 at the beginning of this chapter ! 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 Operating System Concepts 50 Silberschatz, Galvin and Gagne ©2018
26. Liveness (Cont.) Other forms of deadlock: ! Starvation – indefinite blocking " A process may never be removed from the semaphore queue in which it is suspended ! Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higher-priority process " Solved via priority-inheritance protocol Operating System Concepts 52 Silberschatz, Galvin and Gagne ©2018
27. Summary ! A race condition occurs when processes have concurrent access to shared data and the final result depends on the particular order in which concurrent accesses occur. Race conditions can result in corrupted values of shared data. ! A critical section is a section of code where shared data may be manipulated and a possible race condition may occur. The critical- section problem is to design a protocol whereby processes can synchronize their activity to cooperatively share data. ! A solution to the critical-section problem must satisfy the following three requirements: (1) mutual exclusion, (2) progress, and (3) bounded waiting. Mutual exclusion ensures that only one process at a time is active in its critical section. Progress ensures that programs will cooperatively determine what process will next enter its critical section. Bounded waiting limits how much time a program will wait before it can enter its critical section. Operating System Concepts 54 Silberschatz, Galvin and Gagne ©2018
28. Summary (Cont.) ! A monitor is an abstract data type that provides a high-level form of process synchronization. A monitor uses condition variables that allow processes to wait for certain conditions to become true and to signal one another when conditions have been set to true. ! Solutions to the critical-section problem may suffer from liveness problems, including deadlock. ! The various tools that can be used to solve the critical-section problem as well as to synchronize the activity of processes can be evaluated under varying levels of contention. Some tools work better under certain contention loads than others. Operating System Concepts 56 Silberschatz, Galvin and Gagne ©2018