Operating Systems Lecture 5b
Dr Ronald Grau School of Engineering and Informatics Spring term 2020
Previously 1 Process Synchronisation
Inter-Process Communication Race conditions
Communication models
Critical section
Software vs. Hardware solutions Condition synchronisation
Recap: Synchronisation 2 Questions
What are mechanisms with which processes can communicate with each other? Which problem can occur when processes communicate via shared memory? What is mutual exclusion?
What is busy waiting?
What is condition synchronisation?
What is an example of a hardware-supported synchronisation primitive?
Today 3 Process Synchronisation
Critical Sections
Common application problems: Producer-Consumer
Readers-Writers (Lab 6)
Synchronisation primitives:
Mutex, Semaphore, Monitor, Condition Variable, . . . Transactional Memory
Message Passing
Recap: Critical Section 4
Process 1:
entry protocol
x++;
exit protocol
Critical section
Mutual exclusion: If a process is executing in its critical section, then other processes must not execute in their critical section.
Progress (Prevent deadlock): If no process is executing in its critical section and some processes wish to enter their critical sections, then the selection of which process may enter cannot be postponed indefinitely.
Bounded waiting (Prevent starvation): If a process wishes to enter the critical section then only a bounded number of processes may enter the critical section before it.
Process 2:
entry protocol
x–;
exit protocol
Recap: Critical Section 5 Where is the critical section?
Recap: Critical Section 6
Token-controlled synchronisation
Recap: Critical Section solutions 7 Software
Assume atomicity of read and write operations Hardware-supported
More powerful instructions (e.g. test-and-set) Higher-level APIs
Wrap low-level primitives into library: Semaphores, monitors, condition variables, etc
Thread-safe data structures:
Blocking queues, synchronised maps, etc
Bakery algorithm (Leslie Lamport 1974) 8 How does it work?
Customers draw a ticket as they arrive
The ticket has a number that indicates when it is the customer’s turn to be served
When translated to operating systems, the processes are the customers
Bakery algorithm (Leslie Lamport 1974) 9
We have n processes
Shared variables: boolean[n] choosing; int[n] number;
There is a chance that tickets may have the same number
if number == 0 for any process, then that process does not request entering the critical section (already in it)
Instead of keeping busy waiting, the current thread can also yield the CPU to the next thread (Cooperative multithreading)
do {
choosing[i] = true; number[i]=1+max(number[0],…,number[n-1]); choosing[i]=false;
for(intj=0;j