Operating Systems Lecture 5a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Evaluation of scheduling algorithms
Deterministic evaluation
Probabilistic evaluation Queueing models
Little’s Law
Stochastic evaluation Simulation models
Today 2 Process Synchronisation
Inter-Process Communication Race conditions
Communication models
Critical section
Software vs. Hardware solutions Condition synchronisation
Inter-Process Communication 3 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
Problem: Race conditions lead to inconsistent results because of how the execution of instructions may interleave
Race Conditions
4
Example
Process 1:
x++;
MOV A, x
ADD A, 1
MOV x, A
Possible interleaved execution:
MOV A,x ADD A,1 MOV x,A MOV B,x SUB B,1 MOV x,B
xold
MOV A, x
MOV B, x SUBB,1 MOV x, B ADD A, 1 MOV x, A
xold + 1
MOV B, x SUB B, 1 MOVA,x ADD A, 1 MOV x, A MOV x, B
xold – 1
Process 2:
x–;
MOV B, x SUB B, 1 MOV x, B
Communication Models 5 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, …
Critical Section 6
Process 1:
entry protocol
x++;
exit protocol
Critical section
Process 2:
entry protocol
x–;
exit protocol
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.
Critical Section 7 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.
Solutions 8 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
Software solutions 9 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 */
}
Software solutions 10 Idea 1: Turns
Assume i , j ∈ {0,1} i ≠ j Shared variable:
int turn;
Process Pi
Mutual exclusion: Yes
But: If one process finishes, the other one remains blocked forever.
do {
// …
while (turn != i) { /* do nothing */
}
/* critical section */ turn = j;
// …
}
while (!done)
Software solutions 11 Idea 2: Flags
Shared variables:
boolean flag[2] = {false, false};
Process Pi
If one process finishes the other one can continue. But mutual exclusion not guaranteed!
do {
// …
while (flag[j]) { /* do nothing */
}
flag[i] = true;
/* critical section */ flag[i] = false;
// …
}
while (!done)
Software solutions 12 Idea 3: Flag first, then wait
Shared variables:
boolean flag[2] = {false, false};
Process Pi
Mutual exclusion: Yes Possible deadlock
do {
// …
flag[i] = true;
while (flag[j]) { /* do nothing */
}
/* critical section */ flag[i] = false;
// …
}
while (!done)
Software solutions 13 Idea 4: Wait and try again
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 14 Dekker’s algorithm
flag request to enter
turn determines which one enters
the critical section first
Mutual exclusion: Yes! Deadlocks prevented: Yes! Starvation prevented: Yes!
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)
Software solutions 15 Peterson’s algorithm
More elegant implementation of Dekker’s algorithm
Shared variables:
boolean flag[2] = {false, false};
Process Pi
do {
// …
flag[i] = true;
turn = j;
while (flag[j] && turn == j) {
/* do nothing */
}
/* critical section */
flag[i] = false;
// …
}
while (!done)
Hardware-Supported Solutions 16
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
Hardware-Supported Solutions 17 Test-and-Set
An instruction that performs the following atomically:
Usage:
Shared variable _Bool b;
_Bool testandset(_Bool *b) {
if(!*b) {
*b = 1;
return 1; }
return 0; }
do { // …
while (!testandset(&b)) { /* do nothing */
}
/* critical section */ b=0;
// …
}
while (!done)
Condition Synchronisation 18 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:
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
19
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
Synchronisation of Critical Sections
Mutual exclusion, making progress & preventing starvation
Software and hardware-supp. solutions Condition synchronisation
Sequencing of process instructions
Read 20 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
Next Lecture
21
Introduction
Operating System Architectures Processes
Threads – Programming
Process Scheduling – Evaluation Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation