Object-Oriented Programming
Operating Systems
Lecture 5a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Evaluation of scheduling algorithms
Deterministic evaluation
Probabilistic evaluation
Queueing models
Little’s Law
Stochastic evaluation
Simulation models
1
Today
Process Synchronisation
Inter-Process Communication
Race conditions
Communication models
Critical section
Software vs. Hardware solutions
Condition synchronisation
2
Inter-Process Communication
Context
Processes:
share data and resources
cooperate to work on common tasks
There is a need to synchronise activities, i.e. coordinate:
access to shared data and resources
sequences of operations of different processes
3
Problem: Race conditions lead to inconsistent results because of
how the execution of instructions may interleave
Race Conditions
Example
4
Process 1:
x++;
MOV A, x
ADD A, 1
MOV x, A
Process 2:
x–;
MOV B, x
SUB B, 1
MOV x, B
Possible interleaved execution:
MOV A, x MOV A, x MOV B, x
ADD A, 1 MOV B, x SUB B, 1
MOV x, A SUB B, 1 MOV A, x
MOV B, x MOV x, B ADD A, 1
SUB B, 1 ADD A, 1 MOV x, A
MOV x, B MOV x, A MOV x, B
xold xold + 1 xold – 1
Communication Models
Mechanisms
Shared memory:
Commonly accessible memory region
Requires synchronisation!
Message passing (MP):
send and receive messages
Synchronisation is implicit!
Support by operating system kernel, e.g.
POSIX SHM, Pipes, RPC, Sockets, MPI, …
5
Critical Section
Mutual exclusion:
Only one of the processes should execute
in its critical section at any point in time.
Entry and exit of critical sections must
be coordinated.
6
Process 1:
entry protocol
x++;
exit protocol
Process 2:
entry protocol
x–;
exit protocol
Critical section
Critical Section
Any solution must ensure the following:
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.
7
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
8
Software solutions
Classical algorithms
Dekker / Peterson
Assume two processes P0 and P1 alternate execution
(can be generalised to any number of processes)
Assume atomic read and write
Synchronisation over shared variables (e.g. turn, flag)
Busy waiting:
while (condition) {
/* do nothing */
}
9
Software solutions
Idea 1: Turns
Assume i , j ∈ {0,1} i ≠ j
Shared variable:
int turn;
Process Pi
10
do {
// …
while (turn != i) {
/* do nothing */
}
/* critical section */
turn = j;
// …
}
while (!done)
Mutual exclusion: Yes
But: If one process finishes, the
other one remains blocked forever.
Software solutions
Idea 2: Flags
Shared variables:
boolean flag[2] = {false, false};
Process Pi
11
do {
// …
while (flag[j]) {
/* do nothing */
}
flag[i] = true;
/* critical section */
flag[i] = false;
// …
}
while (!done)
If one process finishes the other one can continue.
But mutual exclusion not guaranteed!
Software solutions
Idea 3: Flag first, then wait
Shared variables:
boolean flag[2] = {false, false};
Process Pi
12
do {
// …
flag[i] = true;
while (flag[j]) {
/* do nothing */
}
/* critical section */
flag[i] = false;
// …
}
while (!done)
Mutual exclusion: Yes
Possible deadlock
Software solutions
Idea 4: Wait and try again
13
do {
// …
flag[i] = true;
while (flag[j]) {
flag[i] = false;
// wait a little…
flag[i] = true;
}
/* critical section */
flag[i] = false;
// …
}
while (!done)
Mutual exclusion: Yes
Possible livelock
Software solutions
Dekker’s algorithm
flag request to enter
turn determines which one enters
the critical section first
14
do {
// …
flag[i] = true;
while (flag[j]) {
flag[i] = false;
while (turn == j) {
/* do nothing */
}
flag[i] = true;
}
/* critical section */
turn = j;
flag[i] = false;
// …
}
while (!done)
Mutual exclusion: Yes!
Deadlocks prevented: Yes!
Starvation prevented: Yes!
Software solutions
Peterson’s algorithm
More elegant implementation
of Dekker’s algorithm
Shared variables:
boolean flag[2] = {false, false};
Process Pi
15
do {
// …
flag[i] = true;
turn = j;
while (flag[j] && turn == j) {
/* do nothing */
}
/* critical section */
flag[i] = false;
// …
}
while (!done)
Hardware-Supported Solutions
Interrupt disabling
Protect low-level instruction sequences in kernel
Suitable for user processes?
Suitable in multi-core processors?
More powerful instructions
Test-and-set, compare-and-swap, compare-and-exchange
Rationale: Two or more operations that are executed atomically
16
Hardware-Supported Solutions
Test-and-Set
An instruction that performs the
following atomically:
17
_Bool testandset(_Bool *b) {
if(!*b) {
*b = 1;
return 1;
}
return 0;
}
do {
// …
while (!testandset(&b)) {
/* do nothing */
}
/* critical section */
b=0;
// …
}
while (!done)
Usage:
Shared variable _Bool b;
Condition Synchronisation
Ensure processes perform actions in desired order
Example: data transfer from process P1 to P2
P1 writes to shared memory, P2 reads it
Goal: avoid duplication or loss of data
E.g. using wait() and notify() in Java:
18
do {
newdata = generate();
if(init)
init = false;
else
data.wait();
data = newdata // critical
data.notify();
}
while (true)
do {
data.wait();
readdata = data // critical
data.notify();
process(readata);
}
while (true)
Summary
Inter-Process Communication (IPC)
Communicate information from one
process to another
Avoid conflicts and inconsistencies
when accessing shared data and
resources (race conditions)
Coordinate the sequencing of
operations
Communication Models
Shared Memory
Message Passing
19
Synchronisation of Critical Sections
Mutual exclusion, making progress &
preventing starvation
Software and hardware-supp. solutions
Condition synchronisation
Sequencing of process instructions
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 2.3 & 2.5
Silberschatz et al., Operating System Concepts
Chapter 3.4 – 3.6, Chapter 6
https://docs.oracle.com/javase/tutorial/essential/concurrency/index.html
20
https://docs.oracle.com/javase/tutorial/essential/concurrency/index.html
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
21
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation