代写 data structure algorithm html Java socket concurrency operating system software security Operating Systems Lecture 5a

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