Operating System Concepts - PDF

The 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...

The 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; } ▪ Properties Executed atomically Returns the original value of passed parameter value 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. Operating System Concepts – 10 th Edition 6.11 Silberschatz, Galvin and Gagne ©2018  Solution using compare_and_swap ▪ Shared integer lock initialized to 0; ▪ Solution: while (true){ while (compare_and_swap(&lock, 0, 1) != 0) ; lock = 0; } ▪ Does it solve the critical-section problem? Operating System Concepts – 10 th Edition 6.12 Silberschatz, Galvin and Gagne ©2018  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: Let sequence be an atomic variable Let increment() be operation on the atomic variable sequence The Command: increment(&sequence); ensures sequence is incremented without interruption: Operating System Concepts – 10 th Edition 6.13 Silberschatz, Galvin and Gagne ©2018  Atomic Variables ▪ The increment() function can be implemented as follows: void increment(atomic_int *v) { int temp; do { temp = *v; } while (temp != (compare_and_swap(v,temp,temp+1)); } Operating System Concepts – 10 th Edition 6.14 Silberschatz, Galvin and Gagne ©2018  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 Boolean variable indicating if lock is available or not ▪ Protect a critical section by First acquire() a lock Then release() the lock ▪ Calls to acquire() and release() must be atomic Usually implemented via hardware atomic instructions such as compare-and-swap. Operating System Concepts – 10 th Edition 6.15 Silberschatz, Galvin and Gagne ©2018  Solution to CS Problem Using Mutex Locks while (true) { acquire lock critical section release lock remainder section } Operating System Concepts – 10 th Edition 6.16 Silberschatz, Galvin and Gagne ©2018  Semaphore ▪ Synchronization tool that provides more sophisticated ways (than Mutex locks) for processes to synchronize their activities. ▪ Semaphore S – integer variable ▪ Can only be accessed via two indivisible (atomic) operations wait() and signal()  Originally called P() and V() ▪ Definition of the wait() operation wait(S) { while (S