Processes can execute concurrently ????Returns the original value of passed parameter "value" 3. That is, the swap takes place only under this condition. 5.22 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Solution using compare_and_swap Shared integer "lock" initialized to 0; Solution: do { while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing / / critical section / lock = 0; / remainder section */ } while (true); 5.23 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition int compare _and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == expected) value = new_value; return temp; } ... lock = 0; do { while (compare_and_swap(&lock, 0, 1) != 0) ; / do nothing / / critical section / lock = 0; / remainder section */ } while (true); Solution using compare_and_swap lock value 0 expected 0 new_value 1 temp P0 0 1 Animated by Sarah Al-Shareef (C) 2018 5.24 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition int compare _and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == expected) value = new_value; return temp; } ... lock = 0; do { while (compare_and_swap(&lock, 0, 1) != 0) ; / do nothing / / critical section / lock = 0; / remainder section / } while (true); Solution using compare_and_swap lock value 0 expected 0 new_value 1 temp P0 0 1 P1 Animated by Sarah Al-Shareef (C) 2018 1 5.25 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition 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 (mutual exclusion 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 One disadvantage of this solution: it requires busy waiting While the process is in CS, any other process tries to enter must loop continuously in the call to acquire() Busy waiting wastes CPU cycles.Solved via priority-inheritance protocol5.18 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition 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); 5.19 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Solution using test_and_set() boolean test_and_set (boolean *target) { boolean rv = *target; target = TRUE; return rv: } ... lock = false; do { while (test_and_set(&lock)) /wait/ ; / critical section / lock = false; / remainder section */ } while (true); lock rv target P0 Animated by Sarah Al-Shareef (C) 2018 5.20 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Solution using test_and_set() boolean test_and_set (boolean *target) { boolean rv = *target; target = TRUE; return rv: } ... lock = false; do { while (test_and_set(&lock)) /wait/ ; / critical section / lock = false; / remainder section */ } while (true); lock rv target P0 P1 Animated by Sarah Al-Shareef (C) 2018 5.21 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition 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.Originally called P() and V() Definition of the wait() operation wait(S) { while (S <= 0) ; // busy wait S--; } Definition of the signal() operation signal(S) { S++; } In Java: wait(S) = S.acquire() signal(S) = S.release() 5.28 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Deadlock and Starvation Deadlock Starvation Priority inversion 5.29 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Deadlock and Starvation 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 P0 P1 wait(S); wait(Q); wait(Q); wait(S); ... ... signal(S); signal(Q); signal(Q); signal(S); Starvation - indefinite blocking A process may never be removed from the semaphore queue in which it is suspended (Usually happened with LIFO queues).5.26 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition acquire() { while (!available) ; / busy wait */ available = false;; } release() { available = true; } do { acquire lock critical section release lock remainder section } while (true); acquire() and release() 5.27 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Semaphore Synchronization tool that provides more sophisticated ways (than Mutex locks) for process to synchronize their activities.5.3 Silberschatz, Galvin and Gagne (C)2013 Operating System Concepts - 9th Edition Illustration of the problem: Suppose that we wanted to provide a solution to the consumer-producer problem that fills all the buffers.Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes ?????Semaphore S - integer variable Can only be accessed via two indivisible (atomic) operations wait() and signal() ?It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer.May be interrupted at any time, partially completing execution ??We can do so by having an integer counterthat keeps track of the number of full buffers.Set the variable "value" the value of the passed parameter "new_value" but only if "value"

"expected".Concurrent access to shared data may result in data inconsistency ??Executed atomically 2.Priority Inversion - Scheduling problem when lower-priority process holds a lock needed by higher-priority process.Initially, counter is set to 0.This lock therefore called a spinlock.Because the process spins while waiting until the lock is available.Happens in systems with more than 2 priorities.???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????.??????????????????????????????????????????????????????????????????????????????????????.?????????????????????????????????????????????0 ?????????????????????????.???????????????????????????????????????????????????????????????????????????????????????????

Processes can execute concurrently
يمكن تنفيذ العمليات في وقت واحد
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
يتطلب الحفاظ على اتساق البيانات آليات لضمان التنفيذ المنظم للعمليات المتعاونة
5.3 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Illustration of the problem:
Suppose that we wanted to provide a solution to the consumer-producer
problem that fills all the buffers. We can do so by having an integer
counterthat keeps track of the number of full buffers. Initially, counter
is set to 0. It is incremented by the producer after it produces a new buffer
and is decremented by the consumer after it consumes a buffer.
. نفترض أننا أردنا تقديم حل لمشكلة المستهلك والمنتج الذي يملأ جميع المخازن المؤقتة
لك من يمكننا القيام بذ
. خلال وجود عداد صحيح يتتبع عدد المخازن المؤقتة الكاملة
0 في البداية، يتم ضبط العداد على
.
ويتم
زيادته من قبل المنتج بعد أن ينتج مخزنًا مؤقتًا جديدًا ويتم إنقاصه من قبل المستهلك بعد أن يستهل
ك المخزن
المؤقت
5.4 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Producer
while (true) {
/* produce an item in next produced /
while (counter == BUFFER_SIZE) ;
/ do nothing /
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
5.5 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Consumer
while (true) {
while (counter == 0)
; / do nothing /
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/ consume the item in next consumed */
}
5.6 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Race Condition
counter++ could be implemented as
register1 = counter
register1 = register1 + 1
counter = register1
counter-- could be implemented as
register2 = counter
register2 = register2 - 1
counter = register2
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}
Race condition:
Several processes access
and manipulate the same data
concurrently and the outcome
depends on the order in which
the access takes place.
5.7 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Critical Section Problem
Consider system of n processes {p0, p1, … pn-1}
Each process has critical section segment of code
Process may be changing common variables, updating
table, writing file, etc
When one process in critical section, no other may be in
its critical section
Critical section problem is to design protocol to solve this
Each process must ask permission to enter critical section in
entry section, may follow critical section with exit section,
then remainder section
5.8 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Critical Section
General structure of process Pi
Request permission to
enter the critical section
One process is allowed
To execute this section
The remaining of the
code
Notify the system that
it finished processing in
the critical section.
5.9 Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
Solution to Critical-Section Problem

1. Mutual Exclusion - If process Pi is executing in its critical
   section, then no other processes can be executing in their
   critical sections


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
   If some thread T is not in the critical section, then T cannot
   prevent some other thread S from entering the critical
   section.


3. Bounded Waiting - A bound must exist on the number of
   times that other processes are allowed to 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
   5.10 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Peterson’s Solution
   It is a software-based solution.
   Good algorithmic description of solving the problem
   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[2]
   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!
   5.11 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Algorithm for Process Pi
   do {
   flag[i] = true;
   turn = j;
   while (flag[j] && turn = = j);
   critical section
   flag[i] = false;
   remainder section
   } while (true);
   Indicates if Pi is ready to
   Enter the CS.
   Indicates whose turn to
   enter the CS.
   Wait if the other process
   is ready & it is its turn.
   Only enter here if turn=i
   or flag[j]=false
   (Mutual exclusion)
   When Pi exits CS, change
   its ready flag to false.
   To indicate it’s done.
   i = current process
   j = the other process
   5.12 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Algorithm for Process Pi
   do {
   flag[i] = true;
   turn = j;
   while (flag[j] && turn = = j);
   critical section
   flag[i] = false;
   remainder section
   } while (true);
   0 1
   turn
   flag
   P0
   1
   i = current process
   j = the other process
   Animated by Sarah Al-Shareef © 2018
   5.13 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Algorithm for Process Pi
   do {
   flag[i] = true;
   turn = j;
   while (flag[j] && turn = = j);
   critical section
   flag[i] = false;
   remainder section
   } while (true);
   0 1
   turn
   flag
   P0
   1
   P1
   0
   i = current process
   j = the other process
   Animated by Sarah Al-Shareef © 2018
   5.14 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Peterson’s Solution (Cont.)
   Provable that the three CS requirement are met:


4. Mutual exclusion is preserved
   Pi enters CS only if:
   either flag[j] = false or turn = i


5. Progress requirement is satisfied


6. Bounded-waiting requirement is met
   5.15 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Synchronization Hardware
   Many systems provide hardware support for implementing the
   critical section code.
   All solutions below based on idea of locking
   Protecting critical regions via locks
   Uniprocessors – could disable interrupts
   Currently running code would execute without preemption
   Generally too inefficient on multiprocessor systems
    Operating systems using this not broadly scalable
   Modern machines provide special atomic hardware instructions
    Atomic = non-interruptible
   Either test memory word and set value
   Or swap contents of two memory words
   5.16 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Solution to Critical-section Problem Using Locks
   do {
   acquire lock
   critical section
   release lock
   remainder section
   } while (TRUE);
   5.17 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   test_and_set Instruction
   Definition:
   boolean test_and_set (boolean *target)
   {
   boolean rv = *target;
   *target = TRUE;
   return rv:
   }


7. Executed atomically


8. Returns the original value of passed parameter


9. Set the new value of passed parameter to “TRUE”
   .
   5.18 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   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);
   5.19 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Solution using test_and_set()
   boolean test_and_set (boolean *target)
   {
   boolean rv = *target;
   target = TRUE;
   return rv:
   }
   ...
   lock = false;
   do {
   while (test_and_set(&lock))
   /wait/ ;
   / critical section /
   lock = false;
   / remainder section */
   } while (true);
   lock
   rv
   target
   P0
   Animated by Sarah Al-Shareef © 2018
   5.20 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   Solution using test_and_set()
   boolean test_and_set (boolean *target)
   {
   boolean rv = *target;
   target = TRUE;
   return rv:
   }
   ...
   lock = false;
   do {
   while (test_and_set(&lock))
   /wait/ ;
   / critical section /
   lock = false;
   / remainder section */
   } while (true);
   lock
   rv
   target
   P0
   P1
   Animated by Sarah Al-Shareef © 2018
   5.21 Silberschatz, Galvin and Gagne ©2013
   Operating System Concepts – 9th Edition
   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;
   }


10. Executed atomically


11. Returns the original value of passed parameter “value”


12. Set the variable “value” the value of the passed parameter “new_value”
    but only if “value”
    ==
    “expected”. That is, the swap takes place only under
    this condition.
    5.22 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    Solution using compare_and_swap
    Shared integer “lock” initialized to 0;
    Solution:
    do {
    while (compare_and_swap(&lock, 0, 1) != 0)
    ; /* do nothing /
    / critical section /
    lock = 0;
    / remainder section */
    } while (true);
    5.23 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    int compare _and_swap(int *value, int expected, int new_value)
    {
    int temp = *value;
    if (*value == expected)
    value = new_value;
    return temp;
    }
    ...
    lock = 0;
    do {
    while (compare_and_swap(&lock, 0, 1) != 0)
    ; / do nothing /
    / critical section /
    lock = 0;
    / remainder section */
    } while (true);
    Solution using compare_and_swap
    lock
    value
    0
    expected 0
    new_value 1
    temp
    P0
    0
    1
    Animated by Sarah Al-Shareef © 2018
    5.24 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    int compare _and_swap(int *value, int expected, int new_value)
    {
    int temp = *value;
    if (*value == expected)
    value = new_value;
    return temp;
    }
    ...
    lock = 0;
    do {
    while (compare_and_swap(&lock, 0, 1) != 0)
    ; / do nothing /
    / critical section /
    lock = 0;
    / remainder section /
    } while (true);
    Solution using compare_and_swap
    lock
    value
    0
    expected 0
    new_value 1
    temp
    P0
    0
    1
    P1
    Animated by Sarah Al-Shareef © 2018
    1
    5.25 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    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 (mutual exclusion 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
    One disadvantage of this solution: it requires busy waiting
    While the process is in CS, any other process tries to enter must
    loop continuously in the call to acquire()
    Busy waiting wastes CPU cycles.
    This lock therefore called a spinlock.
    Because the process spins while waiting until the lock is
    available.
    5.26 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    acquire() {
    while (!available)
    ; / busy wait */
    available = false;;
    }
    release() {
    available = true;
    }
    do {
    acquire lock
    critical section
    release lock
    remainder section
    } while (true);
    acquire() and release()
    5.27 Silberschatz, Galvin and Gagne ©2013
    Operating System Concepts – 9th Edition
    Semaphore
    Synchronization tool that provides more sophisticated ways (than Mutex locks)
    for process 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