Object-Oriented Programming
Operating Systems
Lecture 5b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Process Synchronisation
Inter-Process Communication
Race conditions
Communication models
Critical section
Software vs. Hardware solutions
Condition synchronisation
1
Today
Process Synchronisation
Critical Sections
Common application problems:
Producer-Consumer
Readers-Writers (Lab next week)
Synchronisation primitives:
Mutex, Semaphore, Monitor, Condition Variable, . . .
Transactional Memory
Message Passing
2
Recap: Synchronisation
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?
3
Recap: 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.
4
Process 1:
entry protocol
x++;
exit protocol
Process 2:
entry protocol
x–;
exit protocol
Critical section
Recap: Critical Section 5
Where is the critical section?
Recap: Critical Section 6
Token-controlled
synchronisation
Recap: Critical Section solutions
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
7
Bakery algorithm (Leslie Lamport 1974)
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
8
Bakery algorithm (Leslie Lamport 1974)
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)
9
do {
choosing[i] = true;
number[i]=1+max(number[0],…,number[n-1]);
choosing[i]=false;
for(intj=0;j