程序代写代做代考 file system data structure html algorithm concurrency kernel Java Operating Systems Lecture 5a

Operating Systems Lecture 5a
Dr Ronald Grau School of Engineering and Informatics Spring term 2020

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 SUB B, 1 MOVx,B ADD A, 1 MOV x, A
xold + 1
MOV B, x SUB B, 1 MOV A, x ADDA,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 – continued
 Deadlocks
 Memory Management  File Systems
 Input / Output
 Security