程序代写代做代考 compiler algorithm CO2017 — Week 2 — Sharing resources among concurrent processes

CO2017 — Week 2 — Sharing resources among concurrent processes

CO2017 — Week 2 — Sharing resources among

concurrent processes

Dr Gilbert Laycock (gtl1)

2017–01–30

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 1 / 28

Recap

Recap

Abstract notion of process (and thread)

Potential to take advantage of concurrent programming:

Fully utilise CPU while some processes are blocked
Fully utilise multi-CPU systems
Some problems easier to solve with parallel reasoning
Some problems inherently non-deterministic

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 2 / 28

Recap

Overview

1 Inter-process communication

2 Critical regions and mutual exclusion
3 Possible solutions

Disabling interrupts
Access in turns; Peterson’s algorithm
Semaphores

4 Note that in this discussion we use process and thread
interchangeably.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 3 / 28

Shared resources Inter-process Communication

InterProcess Communication

Processes need to communicate, e.g. in a shell pipeline.

But, with concurrent operation, there are issues with

passing messages between processes;
safe sharing of resources;
correct sequencing in the presence of dependencies.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 4 / 28

Shared resources Example: shared print spool

Hazards of using shared resources

Programs often use shared resources, e.g:

Send/receive data to/from the same device (printer; etc.);
Use the same file or a block of RAM (variable; object attribute;
etc.) to store data.

The role of the OS is to avoid incorrect operation of programs due
to shared resource clashes.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 5 / 28

Shared resources Example: shared print spool

A shared resource: printer spooler

E.g. we want to ensure that files are printed one after another and
not, say, one page of one file, the next page of a different file.

Printer spool: a place on a disk organised into a number of
consecutive slots

Each process that wants to print a file

detects the first unoccupied slot;
stores the file name in the slot.

The printer manager periodically examines the slots and sends
the files to print.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 6 / 28

Shared resources Example: shared print spool

Scenario of a clash

Processes P1 and P2 are simultaneously running and both want
to print their files.

Process P1 detects the first unoccupied slot in the spooler
directory (slot 6 say) and then a context switch occurs

Process P2 resumes and detects that slot 6 is free, writes its file
name there and then a context switch occurs.

Process P1 resumes again: it writes its file name to slot 6 (erasing
the record of P2).

P2’s file will never be printed.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 7 / 28

Shared resources Race conditions

Race conditions

Race conditions are situations when two or more processes are
reading or writing some shared data and the result depends on
the order of execution.

A race condition occurred in the example because of combination
of two circumstances:

Process P1 was interrupted during the use of the shared resource.
Process P2 used the shared resource while P1 was interrupted.

To prevent the race condition happen, at least one of the
circumstances should be avoided.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 8 / 28

First approaches to synchronisation

Avoiding race conditions

A critical region is part of the program where shared memory is
accessed. Successful synchronisation requires:

Mutual Exclusion: no two processes should be in their critical
region at the same time.

Progress: no process running outside the critical region may
block other processes.

Bounded wait: each processes should enter its critical region
eventually.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 9 / 28

First approaches to synchronisation Disabling interrupts

Disabling interrupts: the method

At the hardware level, processors have instructions that
effectively disable all interrupts

A process accessing a shared resource can act as follows
1 Disable all interrupts
2 Access the shared resource
3 Re-enable interrupts

The absence of interrupts ensures that the process is not
interrupted while it accesses the shared resource.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 10 / 28

First approaches to synchronisation Disabling interrupts

Disabling interrupts: has it helped?

Disabling interrupts achieves mutual exclusion.

But

Disabling interrupts prevents any other processes running even if
it does not need the shared resource.

The strategy is non-preemptive.

So neither progress nor bounded wait is assured.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 11 / 28

First approaches to synchronisation Access in turns

Access in turns: Overview

A preemptive scheduling policy is needed.

Assume for simplicity that there are only two processes (P0 and
P1) running

The resource is associated with a shared variable “turn” that can
take values 0 or 1.

P0 accesses the resources only if (turn == 0); P1 accesses it
only if (turn == 1).

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 12 / 28

First approaches to synchronisation Access in turns

Access in turns: The algorithm

Algorithm for P0 Algorithm for P1

while(turn == 1) {} ; while(turn == 0) {} ;

Access the resource; Access the resource;

turn = 1; turn = 0;

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 13 / 28

First approaches to synchronisation Access in turns

How does the mechanism work?

Assume turn = 0

If P1 wants to access the resource it will be busy waiting (in the
empty while loop).

When P0 finishes using the resource it assigns turn = 1
enabling P1 to proceed.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 14 / 28

First approaches to synchronisation Access in turns

Disadvantage: useless busy waiting

If it is not its turn, a process cannot start using the resource even
if the other process is not interested.

So performing the while loop wastes CPU time.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 15 / 28

First approaches to synchronisation Peterson’s Algorithm

Towards Peterson’s algorithm

Keep track of which processes are interested in accessing the
critical region.

Assume we have only two processes, P0 and P1.

Each process uses a Boolean flag[pid] to express interest in
entering their critical section.

Both flag[0] and flag[1] are initialised to false.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 16 / 28

First approaches to synchronisation Peterson’s Algorithm

Incorrect attempt

This does not work. Why?
Algorithm for P0 Algorithm for P1

flag[0] = true; flag[1] = true;
while(flag[1]) {} ; while(flag[0]) {} ;
// access resource // access resource
… …

flag[0] = false; flag[1] = false;

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 17 / 28

First approaches to synchronisation Peterson’s Algorithm

Peterson’s algorithm

Keeps track of which processes are interested in accessing the
critical region.

Assume we have only two processes, P0 and P1.

Each process uses a Boolean flag[pid] to express interest in
entering the critical section.

Both flag[0] and flag[1] are initialised to false.

To avoid a deadlock, the process that starts the entry protocol
last is allowed to proceed to the critical section first.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 18 / 28

First approaches to synchronisation Peterson’s Algorithm

Peterson’s algorithm

flag[0] = false; flag[1] = false;

Algorithm for P0 Algorithm for P1

flag[0] = true; flag[1] = true;
turn = 1; turn = 0;
while(flag[1] && while(flag[0] &&

turn==1) {} ; turn==0) {} ;
// access resource // access resource
… …
flag[0] = false; flag[1] = false;

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 19 / 28

First approaches to synchronisation Busy waiting

Busy waiting in Peterson’s algorithm

The while loop in Peterson’s algorithm performs busy waiting

However, waiting is performed only if the other process is
interested in accessing the resource

Compare with the busy waiting required by the access in turns
method

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 20 / 28

First approaches to synchronisation Busy waiting

Informal Justification of correctness

1 If only P0 wants to access the resource. Then P0 can proceed to
the critical section because flag[1] = false.
And vice versa if only P1 wants the resource.

2 If both processes want to access the resource, then both flag[0]
and flag[1] are true.

3 Suppose that P1 is the last to modify turn, i.e. turn == 0.

4 Then P1 will busy-wait while P0 will enter the critical region.

5 And vice versa if P0 happens to be the last to set turn.

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 21 / 28

First approaches to synchronisation Problems with Peterson’s solution

Problems with Peterson’s Solution

The entry/exit protocols are directly programmed using busy-waiting

Busy-waiting protocols are difficult to design, understand, generalise,
and analyse

No separation between variables used for synchronisation and
“normal” variables

So, they are often error-prone and inefficient

Modern compilers and processors make it very difficult to make naïve
assumptions about the order statements are executed

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 22 / 28

Semaphores

Motivation for Semaphores

It would be much simpler to write entry/exit protocols using single
statements, e.g.

GETSEMAPHORE;
critical section;
RELEASESEMAPHORE;
non-critical section

We want to encourage the processor to context switch away from a
blocked process to another process (i.e. no busy waiting)

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 23 / 28

Semaphores Example of semaphores

Synchronisation in Railway Traffic

Railway traffic is synchronised as below:

A railway semaphore is used to signal whether the track ahead is clear or
not
As a train proceeds, semaphores are set and cleared
Railway semaphores are mechanisms that ensure mutually exclusive
occupancy of critical sections of track

Semaphores in concurrent programs are similar:

They provide a basic signalling mechanism to implement mutual
exclusion and condition synchronisation

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 24 / 28

Semaphores Definition of semaphore

Definition of Semaphore

Semaphores were introduced by Dijkstra (1968)

A semaphore is an integer variable that takes only non-negative values
(representing the quantity of a resource available)

Only two operations are permitted on a semaphore s:

Wait(s) (or P(s) for Prolaag – to “try to reduce” s):

If s > 0 then decrement s
else block the calling process

Signal(s) (or V(s) for Verhogen – to inscrease s):

If processes are blocked on s then unblock one
else increment s

Semaphores are often implemented efficiently with hardware facilities
and in the kernel of OSs by block-waiting

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 25 / 28

Semaphores Definition of semaphore

Remarks on Semaphores

Wait() and Signal() need to be implemented as synchronizedmethods

Wait() should wait until the semaphore value becomes > 0

Signal() should release other processes waiting on the semaphore

Wait() and Signal() use block-waiting rather than busy-waiting. A
blocked process uses no CPU time.

If a semaphore only takes 0 or 1, it is called binary; otherwise, called
general (or counting)

Need to ensure that the initial value is ≥ 0 and overflow should not
occur by increment

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 26 / 28

Semaphores Definition of semaphore

Simple semaphore example

Semaphore s = new Semaphore(1);

Algorithm for Process 0 Algorithm for Process 1

Wait(s); Wait(s);
// access resource // access resource
… …
Signal(s); Signal(s);

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 27 / 28

Summary

Summary

Processes (or threads) need to communicate/share resources

Concurrent processes can result in race conditions in access to
critical region

Various (low level) strategies to avoid the problems and achieve

mutual exclusion
progress
bounded wait

Considered: Disable interrupts; access in turns; Peterson’s
method; Semaphores

gtl1–R895 W2L2 — Concurrently shared resources 2017–01–30 28 / 28

Shared resources
Inter-process Communication
Example: shared print spool
Race conditions

First approaches to synchronisation
Disabling interrupts
Access in turns
Peterson’s Algorithm
Busy waiting
Problems with Peterson’s solution

Semaphores
Example of semaphores
Definition of semaphore