程序代写代做代考 kernel c/c++ algorithm Chapter 7: Synchronization Examples

Chapter 7: Synchronization Examples
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018

Classical Problems of Synchronization
 Classical problems used to test newly-proposed synchronization schemes
 Bounded-Buffer Problem
 Readers and Writers Problem  Dining-Philosophers Problem
Operating System Concepts – 10th Edition 7.2 Silberschatz, Galvin and Gagne ©2018

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 – 10th Edition 7.3 Silberschatz, Galvin and Gagne ©2018

}
Bounded Buffer Problem (Cont.)
 The structure of the producer process while (true) {

/* produce an item in next_produced */

wait(empty);
wait(mutex);

/* add next produced to the buffer */

signal(mutex);
signal(full);
Operating System Concepts – 10th Edition 7.4 Silberschatz, Galvin and Gagne ©2018

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 – 10th Edition 7.5 Silberschatz, Galvin and Gagne ©2018

Readers-Writers Problem
 A data set is shared among a number of concurrent processes
 Readers – only read the data set; they do not perform any updates  Writers – can both read and write
 Problem – allow multiple readers to read at the same time
 Only one single writer can access the shared data at the same time
 Several variations of how readers and writers are considered – all involve some form of priorities
 Shared Data  Data set
 Semaphore rw_mutex initialized to 1  Semaphore mutex initialized to 1
 Integer read_count initialized to 0
Operating System Concepts – 10th Edition 7.6 Silberschatz, Galvin and Gagne ©2018

}
Readers-Writers Problem (Cont.)
 The structure of a writer process while (true) {
wait(rw_mutex);

/* writing is performed */

signal(rw_mutex);
Operating System Concepts – 10th Edition 7.7 Silberschatz, Galvin and Gagne ©2018

Readers-Writers Problem (Cont.)
 The structure of a reader process
while (true){
wait(mutex);
}
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);

/* reading is performed */

wait(mutex);
read count–;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
Operating System Concepts – 10th Edition 7.8 Silberschatz, Galvin and Gagne ©2018

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 – 10th Edition 7.9 Silberschatz, Galvin and Gagne ©2018

Dining-Philosophers Problem
 Philosophers spend their lives alternating thinking and eating  Don’t interact with their neighbors, occasionally try to pick up 2
chopsticks (one at a time) to eat from bowl
 Need both to eat, then release both when done
 In the case of 5 philosophers  Shared data
 Bowl of rice (data set)
 Semaphore chopstick [5] initialized to 1
Operating System Concepts – 10th Edition 7.10 Silberschatz, Galvin and Gagne ©2018

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 – 10th Edition 7.11 Silberschatz, Galvin and Gagne ©2018

Monitor Solution to Dining Philosophers
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
}
test(i);
if (state[i] != EATING) self[i].wait;
void putdown (int i) {
state[i] = THINKING;
}
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
Operating System Concepts – 10th Edition 7.12 Silberschatz, Galvin and Gagne ©2018

}
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 – 10th Edition 7.13 Silberschatz, Galvin and Gagne ©2018 Solution to Dining Philosophers (Cont.)  Each philosopher i invokes the operations pickup() and putdown() in the following sequence: DiningPhilosophers.pickup(i); /** EAT **/ DiningPhilosophers.putdown(i);  No deadlock, but starvation is possible Operating System Concepts – 10th Edition 7.14 Silberschatz, Galvin and Gagne ©2018  Linux provides:  Semaphores Linux Synchronization  Linux:  Prior to kernel Version 2.6, disables interrupts to implement short critical sections  Version 2.6 and later, fully preemptive  atomic integers  spinlocks  reader-writer versions of both  On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption Operating System Concepts – 10th Edition 7.15 Silberschatz, Galvin and Gagne ©2018  Consider the variables atomic_t counter; int value; Linux Synchronization  Atomic variables atomic_t is the type for atomic integer Operating System Concepts – 10th Edition 7.16 Silberschatz, Galvin and Gagne ©2018  POSIX API provides  mutex locks  semaphores POSIX Synchronization  condition variable  Widely used on UNIX, Linux, and macOS Operating System Concepts – 10th Edition 7.17 Silberschatz, Galvin and Gagne ©2018 POSIX Mutex Locks  Creating and initializing the lock  Acquiring and releasing the lock Operating System Concepts – 10th Edition 7.18 Silberschatz, Galvin and Gagne ©2018 POSIX Semaphores  POSIX provides two versions – named and unnamed.  Named semaphores can be used by unrelated processes.  Unnamed semaphores can only be used by related processes which share an address space such as children processes created by a parent process using the fork command; or threads that belong to a same process. Operating System Concepts – 10th Edition 7.19 Silberschatz, Galvin and Gagne ©2018 POSIX Named Semaphores  Creating an initializing the semaphore:  Another process can access the semaphore by referring to its name SEM.  Acquiring and releasing the semaphore: Operating System Concepts – 10th Edition 7.20 Silberschatz, Galvin and Gagne ©2018 POSIX Unnamed Semaphores  Creating an initializing the semaphore:  Acquiring and releasing the semaphore: Operating System Concepts – 10th Edition 7.21 Silberschatz, Galvin and Gagne ©2018 POSIX Condition Variables  Since POSIX is typically used in C/C++ and these languages do not provide a monitor, POSIX condition variables are associated with a POSIX mutex lock to provide mutual exclusion: Creating and initializing the condition variable: Operating System Concepts – 10th Edition 7.22 Silberschatz, Galvin and Gagne ©2018 POSIX Condition Variables  The mutex lock associated with the condition variable must be locked before pthread_cond_wait() can be called. Calling pthread_cond_wait() releases the mutex lock, allowing another thread to change shared data and possibly signal the waiting thread Example: Thread waiting for the condition a == b to become true: Thread signaling another thread waiting on the condition variable: Operating System Concepts – 10th Edition 7.23 Silberschatz, Galvin and Gagne ©2018 End of Chapter 7 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018