CONCURRENT PROCESSES

 Crosch's Law (1940's)

The cost of a computer in a given technology is directly proportional to the square root of its speed. 

Limit to the computing power: (speed of the light Argument)

1. speed of light: 3 ´ 10⁸ msec in vacuum.
2. signal transmission speed in silicon: 3 ´ 10⁷ msec.

Consider a chip with 3 cm. diameter (3 ´ 10^-2 m):

It propagates a signal in 10^-9 sec.

This is a limit to computing speed if we do sequential computing. So, we need parallel or concurrent computation to speed things up. Parallel computation is achieved by having more than one processor operating simultaneously, in solving a problem. In concurrent processing, there is a single processor, with more than one process active at a time.

The Critical Section Problem

Consider a system with a number of sequential processes running asynchronously sharing some data. Each process has a portion of code: a critical section, in which it accesses shared data.

If we let more than one process to execute in their critical sections, we shall have updating problems.

Example:

p1 reads variable A (A = 50)

p2 updates variable A ( A = 20)

p1 writes A+10 into A (A = 60)

p2 reads variable A (60 instead of 20)

Solution: Allow only one process to execute in its critical section at a time. (mutual exclusion)

Therefore, design a protocol to achieve mutual exclusion.

Dijkstra's Constraints

No assumptions may be made concerning the hardware instructions or the number of processors the hardware supports. However, it is assumed that the primitive machine language instructions (load, store, compare, etc.,..) are executed atomically. If two primitive machine language instructions are executed simultaneously, then the result is equivalent to their sequential execution in an unknown order.

1. No assumptions may be made on the relative speeds of the n processes executing in the system.
2. When a process is in its non-critical section (non-CS) of code, it may not prevent other processes from entering their own critical sections (CS).
3. When a decision must be made to admit one of a number of candidate processes to its CS, the decision cannot be postponed indefinitely.
4. So, we shall try to develop protocols to solve the CS problem and our solutions will not violate Dijkstra's constraints.

Consider two processes executing simultaneously:

begin

{ shared variable declarations }

{ initializations }

parbegin

p0 ; p1 } means, execute p0 and p1 in parallel

parend;

end.

Every process p_i will have the following general structure:

process pi

{ local variable declarations }

begin

repeat

{ CS entry code }

CS

{ CS exit code }

non-CS

until false

end;

In the coming part of this chapter, a number of algorithms proposed as a solution to the CS problem shall be discussed. For simplicity, only two processes, p0 and p1 shall be considered to be existing in the system, unless it is stated otherwise.

Algorithm - 1:

Let the processes share a common integer variable turn, which is 0 or 1. If turn = 1, p1 is allowed to execute in its CS. Otherwise, p0 is allowed to execute in its CS.

{ for p1 }

repeat

while turn <> 1 do ;

CS

turn := 0;

non-CS

until false;

This algorithm ensures that only one process at a time is in its CS (mutual exclusion). However, it violates Dijkstra's constraint-3, because it requires strict alternation of processes in the execution of the CS.

Example:

turn = 0 and p1 wants to execute its CS.

It can't do so, even though p0 may not want to execute in its CS at that time.

Algorithm-2:

Algorithm-1 failed to remember the state of each process. It could only remember which process is allowed to enter its CS next. Now, replace turn with the following shared variable :

type flagarray: array [0..1] of boolean;

var flag: flagarray;

Initially set all elements of flag to false.

If flag [i]=true, then process pi is executing its CS.

{ for p1 }

repeat

while flag [0] do ;

flag [1]:= true ;

CS

flag [1]:= false ;

non-CS

until false;

This algorithm does not ensure that only one process at a time will be executing is CS.

Example:

• p0 executes while, finds that flag[1] = false
• p1 executes while, finds that flag[0] = false
• p0 sets flag[0] = true, and enters its CS
• p1 sets flag[1] = true, and enters its CS.

Now, p0 and p1 are both in their CS's ...

Algorithm - 3 :

{ for p1 }

repeat

flag [1]:= true ;

while flag [0] do ;

CS

flag [1]:= false ;

non-CS

until false;

This algorithm ensures mutual exclusion, but violates constraint - 4.

For example,

p0 sets flag[0] to true,

p1 sets flag[1] to true. => deadlock !...

Dekker's Algorithm:

Use two shared variables:

var turn: integer; (is either 0 or 1)

flag: array [0..1] of boolean;

initialize flag [0] = flag [1] = false,

turn is either initialized to 0 or 1.

{ for p1 }

repeat

flag [1]:= true

while flag [0] do

if turn = 0 then

begin

flag [1]:= false

while turn = 0 do ;

flag [1]:= true

end

CS

turn:=0

flag [1]:= false

non-CS

until false

Dekker's algorithm satisfies the mutual exclusion condition and it also guarantees that mutual blocking cannot occur. (Dijkstra's constraints 3 and 4 are valid).

Now, add a fifth constraint to Dijkstra's constraints :

1. (fairness, or bounded waiting) After a process makes a request to enter its CS, there must be a limit on the number of times the other processes are allowed to enter their CS's, before that request is granted.

The first algorithm to satisfy all these 5 constraints was developed by Donald Knuth in 1966. (limit = 2n turns). Then, in 1967, DeBruijn reduced the limit to n**2 turns, and finally, in 1972, Eisenberg and McGuire developed the following algorithm which reduced the limit to n-1 turns.

Eisenberg and Mc Guire's algorithm:

var turn : 0..n-1;

flag : array [0...n-1] of (idle, want-in, in-cs);

initialize all flag[i] as idle,

initial value of turn is immaterial.

{ for pi of n processes }

repeat

repeat

flag[i] := want-in;

j := turn;

while j <> i do

if flag[j] <> idle then j := turn

else j := j + 1 mod n;

flag[i] := in-CS;

j:=0;

while ( (j < n) and ((j=i) or (flag[j] <> in-CS)) ) do

j := j + 1;

until ( (j >= n) and ((turn = i) or (flag[turn] = idle)) );

turn := i;

CS

j := turn + 1 mod n;

while ( (j <> turn) and (flag[j] = idle) ) do

j := j + 1 mod n;

turn := j;

flag[i] := idle;

non-CS;

until false;

Bakery algorithm: (Lamport,1974)

Each process receives a number depending on its creation time. Upon a request, the process with the lowest number is served next.

This algorithm is actually developed for a distributed environment. So, it does not guarantee that two processes do not receive the same number. In case of a tie, the process with the lowest name is served first. (process names are unique).

Shared data structures:

var choosing: array [0..n-1] of boolean;

number : array [0..n-1] of integer;

initially: all entries of choosing are false

number = 0

notation : (i) (a,b) < (c,d) if a < c,

or if a = c and b < d

(ii) max (a0, a1, a2, ... , an-1) is k such that

k >= ai ; for i=0,1,...,n-1

{ for pi of n processes }

repeat

choosing[i]:=true;

number[i]:=max (number[0],number [1],...number[n-1])+1;

choosing[i]:=false;

for j=0 to n-1 do

begin

while choosing[j] do ;

while number[j] <> 0 and

(number[j],j) < (number[i],i) do ;

end;

CS

number[i] := 0 ;

non-CS

until false;

Special Hardware Instructions for the CS Problem:

1. Test-and-set (modify) the contents of a memory word,
2. Swap the contents of two memory words. ( in one memory cycle)

These operations are assumed to be atomically executed. (in one machine cycle).

1. Test-and-set

var lock: boolean ; (global)

initialize lock:=false;

{for pi}

repeat

while test-and-set(lock) do ;

CS

lock := false;

non-CS

until false;

2. Swap

Again, use lock as a global boolean variable, initialized to false.

{ for pi }

var key: boolean ;

begin

repeat

key:=true;

repeat

swap (lock,key);

until (key = false);

CS

lock:=false;

non-CS

until false;

SEMAPHORES

Semaphores are synchronization tools introduced by Dijkstra (1965). A semaphore is an integer variable that can only be accessed through two atomic operations: P(s) and V(s).

P (s):

while (S < = 0) do ;

S := S-1 ;

V (s):

S := S+1 ;

If two processes try to execute P (s) or V (s) simultaneously, these operations will be executed sequentially in an arbitrary order.

Using semaphores for the CS problem (n-processes):

mutex is a global semaphore variable

initialize mutex:=1

{ for pi }

repeat

P(mutex) ;

CS

V(mutex) ;

non-CS

until false;

Using semaphores for synchronization:

Example: Consider two concurrent processes: p1, p2. We require that statement s2 of p2 will be executed after statement s1 of p1. Let p1 and p2 share a common semaphore 'synch', initialized to 0.

p1 : ----- p2 : -----

----- -----

----- -----

s1; -----

V(sync); P(sync);

----- s2;

----- -----

Classical Process Synchronization Problems:

1. The Bounded Buffer Problem:

Assume there are n buffers capable of holding one item. Process producer will produce full buffers, process consumer will consume these buffers.

There is no information on the relative speeds of processes.

Devise a protocol which will allow these processes to run concurrently. A common buffer pool is needed, whose elements (buffers) will be filled / emptied by producer / consumer.

The consumer should not try to consume items which have not been produced yet. [i.e., the consumer cannot consume empty buffers.]

The producer should not to try put items into full buffers.

Solution:

Use three semaphores:

mutex : for mutual exclusion in accesses to buffer pool.

empty : counts the number of empty buffers.

full : counts the number of full buffers.

program bounded-buffer;

type item = ...;

semaphore = ...;

var

buffer: array [0...n-1] of item;

nextprod, nextcons: item;

mutex, empty, full: semaphore ;

begin {program}

full:=0 ; }

empty:=n ; } initialization

mutex:=1 ; }

parbegin

process producer;

begin

repeat

[ produce an item in nextprod ]

P(empty);

P(mutex);

[ CS : add nextprod to buffer ]

V(mutex);

V(full);

until false;

end; {producer}

process consumer;

begin

repeat

P(full);

P(mutex);

[ CS : get an item from buffer into nextcons ]

V(mutex);

V(empty);

[ consume the item in nextcons ]

until false;

end; {consumer}

parend;

end. {program}

2. The Readers/Writers Problem :

A data object is shared among several concurrent processes. Some processes only read this common data object. We shall call these processes: readers. Other processes read and write the common data. We shall call them writers.

If two or more readers read the common data simultaneously, there is no problem. However, if one writer accesses the common data simultaneously with another process, we will have problems.

Example: common data object: a bank account (BA) initially: 5000 TL.

p1 : writer : wants to add 10.000 TL.

p2 : writer : wants to add 20.000 TL.

Consider the following sequence of operations :

p1 reads BA into local variable x. (x=5000)

p2 reads BA into local variable y. (y=5000)

p1 adds 10.000 to x. (x=15.000)

p1 copies x into BA. (BA=15.000)

p2 adds 20.000 to y. (y=25.000)

p2 copies y into BA. (BA=25.000)

Finally, BA becomes 25.000 instead of 35.000!

For correct solution, writes will have exclusive access to common data.

A solution shall be given for the first r/w problem :

No reader will be kept waiting unless a writer has already obtained permission to use the common data exclusively. So, no reader should wait for other readers to finish simply because a writer is waiting.

Note that, this may cause a starvation of writes.

program readers-writers;

{mutex is for updating readercount}

{wrt is for mutual exclusion of writes. Also used by first/last reader that enters/exits its CS }

var mutex,wrt: semaphore;

readcount: integer ;

begin {program}

mutex:=1 ;

write:=1 ;

readcount:=0 ;

parbegin

process reader ;

begin

P(mutex) ;

readcount := readcount + 1 ;

if readcount=1 then P (wrt);

V(mutex) ;

[ CS : do the "reading"]

P(mutex);

readcount := readcount-1;

if readcount = 0 then V(wrt);

V(mutex);

end;

process writer;

begin

P(wrt);

[CS: do the "writing"]

V(wrt);

end;

parend ;

end.

3. The Dining Philosophers Problem : [Dijkstra,1965]

This problem is a good representative of a large class of concurrency control problems. Five philosophers spend their lives thinking and eating in a room.

From time to time a philosopher gets hungry. He tires to pick up the two chopsticks that are on his right and his left. A philosopher that picks both chopsticks successfully (one at a time) starts eating. Without releasing his chopsticks.

A philosopher may only pick up one chopstick at a time.

When a philosopher finishes eating, he puts down both of his chopsticks to their original position and he starts thinking again.

The following solution shall ensure that no deadlock will occur. (philosophers will not die of hunger...!) One semaphore shall be used for each chopstick.

program dining-philosophers;

var chopstick: array [0..4] of semaphore ;

begin {program}

for i:=0 to 4 do chopstick [i]:= 1 ;

parbegin

{ here we shall have 5 processes one for each philosopher [0..4] }

process philosopher-i ;

begin

repeat

P(chopstick [i]);

P(chopstick [i+1 mod 5]);

[ CS : "eat"]

V(chopstick [i]);

V(chopstick [i+1 mod 5]);

[ non-CS : "think"]

until false

end;

.....

This solution guarantees that no two neighbors are eating simultaneously, however it may cause a deadlock. Suppose all 5 philosophers become hungry at the same time and they all grab their left chopstick. Now, no one may grab his right chopstick ® deadlock!

One solution that avoids deadlock can be developed by allowing a philosopher to pick up chopsticks only if both are available.

QUESTIONS

1. A counting semaphore pair allows the P and V primitives to operate on two counting semaphores simultaneously. It may be useful for getting and releasing two resources in one atomic operation. The P primitive for a counting semaphore pair can be defined as follows:

p(s1,s2): while (s1<=0)or(s2<=0) do (*nothing*);

s1:=s1-1;

s2:=s2-1;

Show how a counting semaphore pair can be implemented using binary semaphores and regular P(s) and V(s) primitives.

2. Using binary semaphores and P and V operations,

a. Present an incorrect solution to the critical section problem that will cause a deadlock involving only one process.

b. Present an incorrect solution to the critical section problem that will cause a deadlock involving at least two processes.

c. consider the following processes executing concurrently:

P1 P2 P3

-------------- -------------- --------------

repeat repeat repeat

statement a statement e statement h

statement b statement f statement i

statement c statement g until false

statement d until false

until false

Give a solution to synchronize P1, P2 and P3 such that the following order of execution across the statements are is satisfied:

statement a before statement f, statement e before statement h,

statement g before statement c, statement g before statement i.

3. The second readers/writers problem is defined as follows: 'A reader can enter its critical section only if there is no writer process executing, and there is no writer process waiting.' Device a concurrent solution for the second readers/writers problem. That is, define the shared variables and semaphores needed for your solution, and write the general structure for:

a. a reader process, b. a writer process, c. the initialization code.

Write a comment for each statement in your solution.

4. Assume that there are two process P1 and P2 executing on processors Pi and Pj in a distributed system. P1 and P2 are synchronized with a binary semaphore 'flag':

P1 P2

------------- ------------

... ...

statement a statement c

V(flag) P(flag)

statement b statement d

... ...

a. What is the resulting order of execution among statements a, b, c, and d with above code?

Now assume that p(flag) is implemented as [ wait until you receive a 'proceed on flag' message from a process executing on any processor], and V(flag) is implemented as a [send a 'proceed on flag' message to all processors].

b. Is there any danger of violating the order of execution of part a. with this implementation.

c. If two or more processes use this implementation of P and V primitives in accessing shared data, is there any danger of violating the mutual exclusion condition ?

d. Is there any danger of deadlocks in this implementation?

5. Consider a concurrent system with two processes p1 and p2, and two binary semaphores s1 and s2.

a. Explain why the following use of binary semaphores s1 and s2 may create a deadlock.

p1 p2

------------ --------------

P(s1) P(s2)

[use device_1] [use device_2]

P(s2) P(s1)

[use device_2] [use device_1]

b. A conditional atomic P operation (CP) an a binary semaphore (sb) is defined as follows:

if sb>=1) then CP(sb):=true

else CP(sb):=false;

Using this CP operation, rewrite the code for p1 and p2 in part a so that there will be no deadlock.

6. Present a correct solution for concurrent bounded buffer problem assuming there are two buffers, buffer A and buffer B available each of size n. Assume you are given procedures which add an item to a buffer, and remove an item from a buffer, given the buffer name explicitly. Give the structure of the consumer, and the producer processes, and the initialization code. Clearly explain the need for every semaphore variable and shared variable you use in your solution.

7. Suppose we have a computer system with n processes sharing 3 identical printers. One process may use only one printer at a time. In order to use a printer, a process should call procedure "request_printer(p)". This procedure allocates any available printer to the calling process, and returns the allocated printer's id in variable p. If no printers are available, the requesting printer is blocked, and it waits until one becomes available. When a process is finished with printer p, it calls procedure "release_printer(p)".

Write procedures request_printer(p) and release_printer(p) in Pascal, for this system, using semaphores.

8. It is claimed that the following code for producer and consumer processes is a correct solution for the bounded buffer problem :

producer consumer

repeat repeat

... produce item ... P(mutex)

P(mutex) P(full)

P(empty) ... remove item ...

... add item to buffer ... V(mutex)

V(mutex) V(empty)

V(full) ... consume item ...

until false until false

Is this solution deadlock-free? If yes, prove your answer by using any deadlock detection algorithm you wish. If no, modify it so that it becomes deadlock-free.

9. A street vendor prepares cheese potatoes according to the following rule:

1. Baked potatoes should be ready;
2. Grated cheese should be ready;
3. When there are n customers waiting (n=0,1,.. ), up to n+1 cheese potatoes may be prepared.

Write concurrent processes that use only semaphores to control concurrent processes

a. Potato_baker, which bakes 4 potatoes at a time and should run until out_of_potato

b. Cheese_grater, grates a single portion cheese at a time and should run until out_of_chese

c. Cheese_potato_vendor, prepares one cheese potato at a time,

d. Customer_arrival

Do not forget to indicate the initial values of the semaphores.

10. In a multiprogramming environment, n processes are sharing 2 tape drives. A process may use one tape drive at a time. A process which needs a tape drive calls the procedure "request-tape(t)" which allocates a drive, if available, to the calling process and returns the id. of the allocated tape drive in variable t. If none of the drives are available, the requesting process waits until one becomes available. When a process is finished with drive t, it calls procedure "release_tape(t)".

Write the procedures request_tape and release_tape in pascal using semaphores.

11. In the IsBank, METU, there is a single customer queue, and four bank servers.

Customer Queue Bank Servers

o o o o

o o o o /I\ o /I\ o /I\ o /I\

/I\ /I\ /I\ /I\=====/I\=====/I\=====/I\=====

/ \ / \ / \ / \=====/ \=====/ \=====/ \=====

Write concurrent processes that use only semaphores to control concurrent processes

a. customer queue

b. bank servers

Do not forget to indicate the initial values of the semaphores.

12. Two processes P1 and P2 are being executed concurrently on a single processor system. the code for P1 and P2 is given as:

P1 P2

-------------------- ---------------------

process P1 process P2

begin begin

repeat repeat

[CS-1 entry code] [CS-2 entry code]

CS-1 CS-2

[CS-1 exit code] [CS-2 exit code]

until false until false

end end

The program structure is:

program ...

[global declarations]

begin

[initializations]

end

parbegin

[ p1 ]

[p2]

parend

a. Write the CS entry and exit codes for p1 and p2 using semaphores, and P and V operations satisfy the following condition: 'p1 will be executed exactly once after p2 is executed exactly once' (i.e. init | p2 | p1 | p2 | p1 | p2 | p1 | ....). show the initial code as well.

b. Repeat part a. for the following condition: 'p1 will be executed exactly once, after p2 is executed exactly three times.' (i.e. init | p2 | p2 | p2 | p1 | p2 | p2 | p1 | ...)

13. What are the key issues of concurrent processing, explain them

14. Five dining philosophers are in the graduation ball of the university. Again the menu is rice to be eaten by chopsticks. However here they spend their time also for dancing in addition to thinking and eating. Thinking and eating are activities performed while sitting. They are sitting around a table having five plates and one chopstick between each plate.

From time to time a philosopher gets hungry. He tries to pick up the two chopsticks that are on his right and on his left. A philosopher that picks both chopsticks successfully, starts eating without releasing his chopsticks. A philosopher may only pick up one chopstick at a time. When a philosopher finishes eating he puts down both of his chopsticks to their original position and he starts thinking again.

There are two ladies in the ballroom who are always willing to dance with the philosophers, and they never let more than four philosophers to be sitting at the same time. They may invite a philosopher to dance only if he is not eating , but he is thinking. A philosopher cannot deny the invitation of a lady if he is thinking.

Write concurrent processes for philosophers and ladies, that use semaphores to control synchronization over critical section code. Discuss deadlock and starvation issues, and propose deadlock-free and nonstarving solutions if possible.

15. Assuming that the semaphore values are set to: mutex=1, clean=1, dirty=0,

a. Find an execution order of the statements of the master and slave processes causing deadlock:

master slave .

m1: P(mutex) s1: P(mutex)

m2: P(clean) s2: P(dirty)

m3: {drink} s3: {wash}

m4: V(dirty) s4: V(clean)

m5: V(mutex) s5: V(mutex)

b. How can you overcome this deadlock possibility with no change on the initial values?

16. Our five philosophers in the coffee room have realized that it is not easy to wash dishes. So they have decided to have a servant. Furthermore they bought some more cups. Now they have 3 cups, 1 pot and a servant. All the cups are clean initially and pot is full of coffee. The philosophers either drink coffee or chat. To drink coffee, a philosopher should grab a clean cup, and have to wait the servant to pour some coffee in it. Then he drinks the coffee and puts empty cup on the table. On the other hand, the servant is responsible from washing it if there is any dirty cup, pouring coffee if there is any philosopher has grabbed a cup. The servant is filling the pot if the coffee in the pot have been finished, so assume the coffee in the pot is infinity. Write concurrent procedures for the philosophers and the wash-cup, pour-coffee of the servant by using semaphores such that it should be deadlock free and any process in non-critical section should not cause any other process to wait unneccessarily.