Computer Operating System - Chapter 7: Synchronization Examples

Nội dung text: Computer Operating System - Chapter 7: Synchronization Examples

1. Chapter 7: Synchronization Examples ! Explain the bounded-buffer, readers-writers, and dining philosophers synchronization problems ! Describe the tools used by Linux and Windows to solve synchronization problems ! Illustrate how POSIX and Java can be used to solve process synchronization problems Operating System Concepts 2 Silberschatz, Galvin and Gagne ©2018
2. Bounded-Buffer Problem ! n buffers, each can hold one item ! Semaphore mutex initialized to the value 1 ! Semaphore full initialized to the value 0 ! Semaphore empty initialized to the value n Operating System Concepts 4 Silberschatz, Galvin and Gagne ©2018
3. Bounded Buffer Problem (Cont.) ! The structure of the consumer process while (true) { wait(full); wait(mutex); /* remove an item from buffer to next_consumed */ signal(mutex); signal(empty); /* consume the item in next consumed */ } Operating System Concepts 6 Silberschatz, Galvin and Gagne ©2018
4. Readers-Writers Problem (Cont.) ! The structure of a writer process while (true) { wait(rw_mutex); /* writing is performed */ signal(rw_mutex); } Operating System Concepts 8 Silberschatz, Galvin and Gagne ©2018
5. Readers-Writers Problem Variations ! First variation – no reader kept waiting unless writer has permission to use shared object ! Second variation – once writer is ready, it performs the write ASAP ! Both may have starvation leading to even more variations ! Problem is solved on some systems by kernel providing reader-writer locks Operating System Concepts 10 Silberschatz, Galvin and Gagne ©2018
6. Dining-Philosophers Problem Algorithm ! Semaphore Solution ! The structure of Philosopher i: while (true){ wait (chopstick[i] ); wait (chopStick[ (i + 1) % 5] ); /* eat for awhile */ signal (chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); /* think for awhile */ } ! What is the problem with this algorithm? Operating System Concepts 12 Silberschatz, Galvin and Gagne ©2018
7. Solution to Dining Philosophers (Cont.) 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; } } Operating System Concepts 14 Silberschatz, Galvin and Gagne ©2018
8. Kernel Synchronization - Windows ! Uses interrupt masks to protect access to global resources on uniprocessor systems ! Uses spinlocks on multiprocessor systems " Spinlocking-thread will never be preempted ! Also provides dispatcher objects user-land which may act mutexes, semaphores, events, and timers " Events 4 An event acts much like a condition variable " Timers notify one or more thread when time expired " Dispatcher objects either signaled-state (object available) or non-signaled state (thread will block) Operating System Concepts 16 Silberschatz, Galvin and Gagne ©2018
9. Linux Synchronization ! Linux: " Prior to kernel Version 2.6, disables interrupts to implement short critical sections " Version 2.6 and later, fully preemptive ! Linux provides: " Semaphores " atomic integers " spinlocks " reader-writer versions of both ! On single-CPU system, spinlocks replaced by enabling and disabling kernel preemption Operating System Concepts 18 Silberschatz, Galvin and Gagne ©2018
10. POSIX Synchronization ! POSIX API provides " mutex locks " semaphores " condition variable ! Widely used on UNIX, Linux, and macOS Operating System Concepts 20 Silberschatz, Galvin and Gagne ©2018
11. POSIX Semaphores ! POSIX provides two versions – named and unnamed ! Named semaphores can be used by unrelated processes, unnamed cannot Operating System Concepts 22 Silberschatz, Galvin and Gagne ©2018
12. POSIX Unnamed Semaphores ! Creating an initializing the semaphore: ! Acquiring and releasing the semaphore: Operating System Concepts 24 Silberschatz, Galvin and Gagne ©2018
13. POSIX Condition Variables ! Thread waiting for the condition a == b to become true: ! Thread signaling another thread waiting on the condition variable: Operating System Concepts 26 Silberschatz, Galvin and Gagne ©2018
14. Java Monitors ! Every Java object has associated with it a single lock. ! If a method is declared as synchronized, a calling thread must own the lock for the object. ! If the lock is owned by another thread, the calling thread must wait for the lock until it is released. ! Locks are released when the owning thread exits the synchronized method. Operating System Concepts 28 Silberschatz, Galvin and Gagne ©2018
15. Java Synchronization ! A thread that tries to acquire an unavailable lock is placed in the object’s entry set: Operating System Concepts 30 Silberschatz, Galvin and Gagne ©2018
16. Java Synchronization ! A thread typically calls wait() when it is waiting for a condition to become true. ! How does a thread get notified? ! When a thread calls notify(): 1. An arbitrary thread T is selected from the wait set 2. T is moved from the wait set to the entry set 3. Set the state of T from blocked to runnable. ! T can now compete for the lock to check if the condition it was waiting for is now true. Operating System Concepts 32 Silberschatz, Galvin and Gagne ©2018
17. Bounded Buffer – Java Synchronization Operating System Concepts 34 Silberschatz, Galvin and Gagne ©2018
18. Java Semaphores ! Constructor: ! Usage: Operating System Concepts 36 Silberschatz, Galvin and Gagne ©2018
19. Java Condition Variables ! Example: " Five threads numbered 0 4 " Shared variable turn indicating which thread’s turn it is. " Thread calls doWork() when it wishes to do some work. (But it may only do work if it is their turn. " If not their turn, wait " If their turn, do some work for awhile " When completed, notify the thread whose turn is next. ! Necessary data structures: Operating System Concepts 38 Silberschatz, Galvin and Gagne ©2018
20. Alternative Approaches ! Transactional Memory ! OpenMP ! Functional Programming Languages Operating System Concepts 40 Silberschatz, Galvin and Gagne ©2018
21. OpenMP ! OpenMP is a set of compiler directives and API that support parallel programming. void update(int value) { #pragma omp critical { count += value } } ! The code contained within the #pragma omp critical directive is treated as a critical section and performed atomically. Operating System Concepts 42 Silberschatz, Galvin and Gagne ©2018
22. Summary ! Classic problems of process synchronization include the bounded- buffer, readers–writers, and dining-philosophers problems. Solutions to these problems can be developed using the tools presented in Chapter 6, including mutex locks, semaphores, monitors, and condition variables. ! Windows uses dispatcher objects as well as events to implement process synchronization tools. ! Linux uses a variety of approaches to protect against race conditions, including atomic variables, spinlocks, and mutex locks. ! The POSIX API provides mutex locks, semaphores, and condition variables. POSIX provides two forms of semaphores: named and unnamed. Several unrelated processes can easily access the same named semaphore by sim- ply referring to its name. Unnamed semaphores cannot be shared as easily, and require placing the semaphore in a region of shared memory. Operating System Concepts 44 Silberschatz, Galvin and Gagne ©2018
23. End of Chapter 7 Operating System Concepts Silberschatz, Galvin and Gagne ©2018