Distributed Computing - Concurrent Processing

·????? Nature of Concurrent Processes

o?? The “Scheduler”

·????? Properties of Concurrent Syste Safety and Liveness

·????? Nature of Concurrent Processes

o?? The “Scheduler”

·?????-Properties of Concurrent Systems

o?? Safety and Liveness

-Proving Correctness

§? Proof by induction: Mutual Exclusion

·????? Type of Interaction

o?? Synchronisation & Communication

·????? Control: Process States

·????? Use of Virtual Machines and the OS

·????? Processes run and call for ‘Resources’:

-E.g. I/O devices, memory areas

-Resources may be shareable, non-shareable or dedicated

-A non-shareable resources cannot be accessed by two processes at once

-E.g. a data block should be unavailable to another process while it is being updated

·????? A process attempting to read it, must wait, or do something else

·????? The scheduler selects processes to run depending on any or all of:

o?? Time

-Each process is allowed a ‘time-slice’, and switching takes place N millseconds

o?? Resources

-The scheduler will ‘suspend’ a process wishing to us a non-available resource, and select another

o?? Priority

§? The scheduler may pre-mpt a low priotity process if one of higher priority can run

·????? Concurrency properties

o?? Safety properties must always be true:

- I.e. “Nothing bad will ever happen”

-For example

·????? At most one process will ever access a non-shareable resource at one time: Mutual Exclusion

·????? A non-terminating process will never wait for an event that will never happen: Absence of deadlock

-?? Liveness properties require that certain conditions will eventually become true:

§? E.g. a request will eventually be services

§? Liveness implies ‘absence of starvation’ e.g. any request will eventually be accepted in spite of a higher priority requests

§? A generally desirable property is ‘Fairness’ – a request will be services provided they request continuously (weak) or even if they request transiently (strong) – requests will be services before other later request (strongest fairness)

? ?

·????? How to realise safety mutual exclusion and why concurrent access of a flag does not work and why semaphores work!??

First attempt at mutual exclusion

Try a flag, set and reset to control access

Agent A:????????????????????????????????????????????? ??????????????????????????????????? Agent B:

·????? While (Flag = Busy ) do nothing ??????????????????????????????? While (Flag = Busy ) do nothing

·????? Flag := Busy??????????????????????????????????????????????????????????????? Flag := Busy ?

·????? Agent A reserves the seat????????????????????????????????????????? Agent A reserves the seat

·????? Flag := Not Busy???????????????????????????????????????????????????????? Flag := Not Busy

·????? Concurrent access to a flag

o?? The ‘Flag’ attempt fails:????????

§? Simultaneous access to a flag by both agents means they both see it is not Busy

§? So they can both gain access to their ‘Critical Sections’ Simultaneously

§? The problem is the separation of the test and setting operations on the flag.

·????? The operations are not ‘atomic’ or ‘indivisible’

·????? Semaphores – Developed by Dijkstra (1965)

o?? An elegant and effective solution for a pre- and post protocols for concurrent systems

o?? A non- negative integer (like a flag), but limited to two ‘indivisible’ operations:

§? Wait and signal

o?? Operations on Semephores

o?? Indivisible operations

o?? Testing and setting of ‘s’ restricted to one process at a time by locking out others – allowing mutual exclusion on Critical Sections

?-?????? Signal (s)

Lock???????????????????????????? )

??????????? S:=s+1???????????? ) indivisible

Unlock???????????????????????? )

-?????? Wait (s)

Lock???????????????????????????????????????????????????? )

??????????? If s:=0 THEN Unlock; TryAgain;)

??????????? ELSE s:=s-1????????????????????????????? )?????????

Unlock???????????????????????????????????????????????? )

?

Lock / unlock operations work satisfactorily for a single processor system

·????? Semaphore and Mutual Exclusion

o?? Semaphore called e.g. ‘mutex’

o?? Initial value = 1 (to avoid deadlock)

Agent A booking Seychelles?????????????????????????? Agent B Booking Seychelles

?.. ..

This Code??????? Wait (mutex)????????????????????????????????????????????????? wait(mutex)

Is ‘Critical ?????????????????? if seat is free, consult client?????????????????????????? waiting

Section’?????????????????????? Agent A reserves the seat

??????????????????????? Signal(mutex)

Wait succeeds ?- ‘Critical

??????????????????????? ? .. section’

No seats available

??????????????????????????????????????????????????????????????????????????????????????????????? Signal (mutex)???????????????????????

??????????????????????????????????????????????????????????????????????????????????? Recommend Slough

·????? Semaphores and Synchronisation

?

One way synchronization

A:???????????????????????????????? <-- Ready = --> ???????????????????????????????? B:

?

Wait (ready)

?Wait

??????????????????????????????????????????????????????????????????????????????????? Bottle Available

?????Fill the bottle? ??????????????????????? <-- ???????????????? ? Signal (ready )

·????? Semaphore Handshaking

A:???????????????????????????????????????????????????????????????????????????????????????????? B:

??????????????????????????????????????????????????????????????????????????????????????????????? Bottle available

??????????????????????????????????????????????????????????????????????????????????? <--?????? Signal (ready)

Wait(ready)? <----

Fill the bottle

??????????????????????????????????????????????????????????????????????????????????? -->?????? wait(done)

Signal (done)? -->????????????????????????????????????????????????????? ??????????? Go back and??????????????????????????????????????? ??????????????????????? ??????????????????????????????????????????????? ??????????? get another one

·????? The producer- consumer

?

Process A produces a block of data

Process B consumes all the data in one go

A:???????????????????????????????? <-- ready = 1 -->?????????????????????? B:

Generate data??????????????????dataOK = 0

Wait (ready)?????????????????????????????????????????????????????????????? wait (dataOK)

??????????? Write to ???????????????????????????????????????????????????????????????????? read the

??????????? Shared ??????????????????????????????????????????????????????????????????????? Shared

??????????? Memory????????????????????????????????????????????????????????????????????? memory?????????

Signal (dataOK)????????????????????????????????????????????????????????? Signal (ready)

??????????????????????????????????????????????????????????????????????????????????? Consume data

I hope this has been informative on some of the key considerations in distributed computing.