Processes and Processors in Distributed Systems

Threads,
system model,
processor allocation,
scheduling in distributed systems
Load balancing and
sharing approach,
fault tolerance,
Real time distributed systems,
Process migration and related issues

1. Distributed Operating
Systems
Processes and Processors in Distributed Systems
Sandeep Kumar Poonia
Head of Dept. CS/IT
B.E., M.Tech., UGC-NET
LM-IAENG, LM-IACSIT,LM-CSTA, LM-AIRCC, LM-SCIEI, AM-UACEE

2. Processes and processors in distributed systems
Threads,
system model,
processor allocation,
scheduling in distributed systems
Load balancing and
sharing approach,
fault tolerance,
Real time distributed systems,
Process migration and related issues
Sandeep Kumar Poonia, Jagannath University, Jaipur

3. InmosttraditionalOS,eachprocesshasan
addressspaceandasinglethreadofcontrol.
Itisdesirabletohavemultiplethreadsofcontrol
sharingoneaddressspacebutrunninginquasi-
parallel.
Sandeep Kumar Poonia, Jagannath University, Jaipur

4. Introduction to threads
Threadisalightweightedprocess.
Theanalogy:threadistoprocessasprocessisto
machine.
•Eachthreadrunsstrictlysequentiallyandhasits
ownprogramcounterandstacktokeeptrackof
whereitis.
•ThreadssharetheCPUjustasprocessesdo:first
onethreadruns,thenanotherdoes.
•Threadscancreatechildthreadsandcanblock
waitingforsystemcallstocomplete.
Sandeep Kumar Poonia, Jagannath University, Jaipur

5. Allthreadshaveexactlythesameaddressspace.They
sharecodesection,datasection,andOSresources(open
files&signals).Theysharethesameglobalvariables.One
threadcanread,write,orevencompletelywipeout
anotherthread’sstack.
Threadscanbeinanyoneofseveralstates:running,
blocked,ready,orterminated.
Sandeep Kumar Poonia, Jagannath University, Jaipur
Introduction to threads

6. Thereisnoprotectionbetweenthreads:
(1)itisimpossible
(2)itshouldnotbenecessary:aprocessisalwaysowned
byasingleuser,whohascreatedmultiplethreadssothat
theycancooperate,notfight.
Inadditiontosharinganaddressspaceallthreadsshare:
Setofopenfiles
Childprocesses
TimersandSignalsetc.
Sandeep Kumar Poonia, Jagannath University, Jaipur
Introduction to threads

7. Threads
Sandeep Kumar Poonia, Jagannath University, Jaipur
Computer
Computer

8. Thread usage
Sandeep Kumar Poonia, Jagannath University, Jaipur
Mailbox
Request for
work arrives
Kernel
Shared
block
cache
File server processDispatcher thread
Worker
thread
Dispatcher/worker model
Team model
Pipeline model

9. Advantages of using threads
1.Usefulforclients:ifaclientwantsafiletobe
replicatedonmultipleservers,itcanhaveonethread
talktoeachserver.
2.Handlesignals,suchasinterruptsfromthekeyboard.
Insteadoflettingthesignalinterrupttheprocess,one
threadisdedicatedfulltimetowaitingforsignals.
3.Producer-consumerproblemsareeasiertoimplement
usingthreadsbecausethreadscanshareacommon
buffer.
4.Itispossibleforthreadsinasingleaddressspaceto
runinparallel,ondifferentCPUs.
Sandeep Kumar Poonia, Jagannath University, Jaipur

10. Design Issues for Threads Packages
Asetofprimitives(e.g.librarycalls)availableto
theuserrelatingtothreadsiscalledathread
package.
Staticthread:thechoiceofhowmanythreads
therewillbeismadewhentheprogramis
writtenorwhenitiscompiled.Eachthreadis
allocatedafixedstack.Thisapproachissimple,
butinflexible.
Dynamicthread:allowthreadstobecreated
anddestroyedon-the-flyduringexecution.
Sandeep Kumar Poonia, Jagannath University, Jaipur

11. Mutex
Ifmultiplethreadswanttoaccesstheshared
buffer,amutexisused.Amutexcanbelockedor
unlocked.
Mutexesarelikebinarysemaphores:0or1.
Lock:ifamutexisalreadylocked,thethreadwillbeblocked.
Unlock:unlocksamutex.Ifoneormorethreadsarewaitingon
themutex,exactlyoneofthemisreleased.Therestcontinueto
wait.
Trylock:ifthemutexislocked,Trylockdoesnotblockthethread.
Instead,itreturnsastatuscodeindicatingfailure.
Sandeep Kumar Poonia, Jagannath University, Jaipur

12. Implementing a threads package
Implementing threads in user space
Sandeep Kumar Poonia, Jagannath University, Jaipur

13. Advantage
User-levelthreadspackagecanbeimplementedonan
operatingsystemthatdoesnotsupportthreads.For
example,theUNIXsystem.
Thethreadsrunontopofaruntimesystem,whichisa
collectionofproceduresthatmanagethreads.The
runtimesystemdoesthethreadswitch.Storetheold
environmentandloadthenewone.Itismuchfasterthan
trappingtothekernel.
User-levelthreadsscalewell.Kernelthreadsrequire
sometablespaceandstackspaceinthekernel,which
canbeaproblemifthereareaverylargenumberof
threads.
Sandeep Kumar Poonia, Jagannath University, Jaipur

14. Disadvantage
Blockingsystemcallsaredifficulttoimplement.Lettingonethread
makeasystemcallthatwillblockthethreadwillstopallthethreads.
Pagefaults.Ifathreadcausesapagefaults,thekerneldoesnotknow
aboutthethreads.Itwillblocktheentireprocessuntilthepagehas
beenfetched,eventhoughotherthreadsmightberunnable.
Ifathreadstartsrunning,nootherthreadinthatprocesswilleverrun
unlessthefirstthreadvoluntarilygivesuptheCPU.
FortheapplicationsthatareessentiallyCPUboundandrarelyblock,
thereisnopointofusingthreads.Becausethreadsaremostusefulif
onethreadisblocked,thenanotherthreadcanbeused.
Sandeep Kumar Poonia, Jagannath University, Jaipur

15. Implementing threads in the kernel
Sandeep Kumar Poonia, Jagannath University, Jaipur

16. Thekernelknowsaboutandmanagesthethreads.No
runtimesystemisneeded.Whenathreadwantstocreate
anewthreadordestroyanexistingthread,itmakesa
kernelcall,whichthendoesthecreationand
destruction.
Tomanageallthethreads,thekernelhasonetableper
processwithoneentryperthread.
Whenathreadblocks,thekernelcanruneitheranother
threadfromthesameprocessorathreadfroma
differentprocess.
Sandeep Kumar Poonia, Jagannath University, Jaipur

17. Scheduler Activations
Scheduleractivationscombinetheadvantageofuser
threads(goodperformance)andkernelthreads.
Thegoalsofthescheduleractivationaretomimicthe
functionalityofkernelthreads,butwiththebetter
performanceandgreaterflexibilityusuallyassociated
withthreadspackagesimplementedinuserspace.
Efficiencyisachievedbyavoidingunnecessarytransitions
betweenuserandkernelspace.Ifathreadblocks,the
user-spaceruntimesystemcanscheduleanewoneby
itself.
Sandeep Kumar Poonia, Jagannath University, Jaipur

18. Disadvantage:
Upcallfrom the kernel to the runtime system violates the
structure in the layered system.
Sandeep Kumar Poonia, Jagannath University, Jaipur

19. System Models
Theworkstationmodel:
thesystemconsistsofworkstationsscatteredthroughout
abuildingorcampusandconnectedbyahigh-speed
LAN.
Thesystemsinwhichworkstationshavelocaldisksare
calleddiskfulworkstations.Otherwise,diskless
workstations.
Sandeep Kumar Poonia, Jagannath University, Jaipur

20. Why diskless workstation?
Iftheworkstationsarediskless,thefilesystemmustbe
implementedbyoneormoreremotefileservers.
Disklessworkstationsarecheaper.
Easeofinstallingnewreleaseofprogramonseveral
serversthanonhundredsofmachines.Backupand
hardwaremaintenanceisalsosimpler.
Disklessdoesnothavefansandnoises.
Disklessprovidessymmetryandflexibility.Youcanuse
anymachineandaccessyourfilesbecauseallthefilesare
intheserver.
Sandeep Kumar Poonia, Jagannath University, Jaipur

21. Advantage:lowcost,easyhardwareandsoftware
maintenance,symmetryandflexibility.
Disadvantage:heavynetworkusage;fileserversmay
becomebottlenecks.
Sandeep Kumar Poonia, Jagannath University, Jaipur

22. Diskfulworkstations
Thedisksinthediskfulworkstationareusedinone
ofthefourways:
1.Pagingandtemporaryfiles(temporaryfilesgeneratedbythe
compilerpasses).
Advantage:reducesnetworkloadoverdisklesscase
Disadvantage:highercostduetolargenumberofdisksneeded
2.Paging,temporaryfiles,andsystembinaries(binary
executableprogramssuchasthecompilers,texteditors,and
electronicmailhandlers).
Advantage:reducesnetworkloadevenmore
Disadvantage:highercost;additionalcomplexityofupdatingthebinaries
Sandeep Kumar Poonia, Jagannath University, Jaipur

23. 3.Paging,temporaryfiles,systembinaries,andfilecaching
(downloadthefilefromtheserverandcacheitinthelocaldisk.
Canmakemodificationsandwriteback.Problemiscache
coherence).
Advantage:stilllowernetworkload;reducesloadonfileserversas
well
Disadvantage:highercost;cacheconsistencyproblems
4.Completelocalfilesystem(lownetworktrafficbutsharingis
difficult).
Advantage:hardlyanynetworkload;eliminatesneedforfileservers
Disadvantage:lossoftransparency
Sandeep Kumar Poonia, Jagannath University, Jaipur

24. Sandeep Kumar Poonia, Jagannath University, Jaipur

25. Using Idle Workstation
Theearliestattempttouseidleworkstationsis
command:
rshmachinecommand
Thefirstargumentnamesamachineandthe
secondnamesacommandtorun.
Sandeep Kumar Poonia, Jagannath University, Jaipur

26. Flaws
1)User has to tell which machine to use.
2)The program executes in a different environment than the
local one.
3) Maybe log in to an idle machine with many processes.
Sandeep Kumar Poonia, Jagannath University, Jaipur

27. What is an idle workstation?
Ifnoonehastouchedthekeyboardormouseforseveralminutes
andnouser-initiatedprocessesarerunning,theworkstationcan
besaidtobeidle.
Thealgorithmsusedtolocateidleworkstationscanbedivided
intotwocategories:
serverdriven--ifaserverisidle,itregistersinregistryfileor
broadcaststoeverymachine.
clientdriven--theclientbroadcastsarequestaskingforthe
specificmachinethatitneedsandwaitforthereply.
Sandeep Kumar Poonia, Jagannath University, Jaipur

28. A registry-based algorithm for finding &
using idle workstation
Sandeep Kumar Poonia, Jagannath University, Jaipur

29. How to run the process remotely?
To start with, it needs the same view of the file system, the
same working directory, and the same environment
variables.
Some system calls can be done remotely but some can not.
For example, read from keyboard and write to the screen
can never be carried out on remote machine. (All system
calls that query the state of machine)
Some must be done remotely, such as the UNIX system calls
SBRK (adjust the size of the data segment), NICE (set CPU
scheduling priority), and PROFIL (enable profiling of the
program counter).
Sandeep Kumar Poonia, Jagannath University, Jaipur

30. The processor pool model
A processor pool is a rack full of CPUs in the machine
room, which can be dynamically allocated to users on
demand.
Sandeep Kumar Poonia, Jagannath University, Jaipur

31. Why processor pool?
Input rate λ, process rate µ. mean response time T=1/(µ-
λ).
If there are n processors, each with input rate λand process
rate µ.
If we put them together, input rate will be nλand process
rate will be nµ. Mean response time will be T
1=1/(nµ-
nλ)=T/n.
Sandeep Kumar Poonia, Jagannath University, Jaipur
User generate a total of λ
request/sec

32. Example
Considerafileserverthatishandling50
request/sec(µ)
Butgetonly40request/sec(λ)
TheMeanResponsetime?
Ifλgoto0(noload)
Whatwillberesponsetime?
Sandeep Kumar Poonia, Jagannath University, Jaipur

33. A hybrid model
Apossiblecompromiseistoprovideeachuser
withapersonalworkstationandtohavea
processorpoolinaddition.
Forthehybridmodel,evenifyoucannotgetany
processorfromtheprocessorpool,atleastyou
havetheworkstationtodothework.
Sandeep Kumar Poonia, Jagannath University, Jaipur

34. Processor Allocation
Determinewhichprocessisassignedtowhich
processor.Alsocalledloaddistribution.
Twocategories:
Staticloaddistribution-nonmigratory,once
allocated,cannotmove,nomatterhow
overloadedthemachineis.
Dynamicloaddistribution-migratory,canmove
eveniftheexecutionstarted.Butalgorithmis
complex.
Sandeep Kumar Poonia, Jagannath University, Jaipur

35. The goals of allocation
1Maximize CPU utilization
2Minimize mean response time/ Minimize response ratio
Response ratio-the amount of time it takes to run a process on some
machine, divided by how long it would take on some unloaded
benchmark processor. E.g. a 1-sec job that takes 5 sec. The ratio is
5/1.
Sandeep Kumar Poonia, Jagannath University, Jaipur

36. Design issues for processor allocation
algorithms
Deterministic versus heuristic algorithms
Centralized versus distributed algorithms
Optimal versus suboptimal algorithms
Local versus global algorithms
Sender-initiated versus receiver-initiated algorithms
Sandeep Kumar Poonia, Jagannath University, Jaipur

37. How to measure a processor is overloaded or
underloaded?
1Counttheprocessesinthemachine?Notaccurate
becauseeventhemachineisidletherearesomedaemons
running.
2Countonlytherunningorreadytorunprocesses?Not
accuratebecausesomedaemonsjustwakeupandcheck
toseeifthereisanythingtorun,afterthat,theygoto
sleep.Thatputsasmallloadonthesystem.
3CheckthefractionoftimetheCPUisbusyusingtime
interrupts.NotaccuratebecausewhenCPUisbusyit
sometimesdisableinterrupts.
Sandeep Kumar Poonia, Jagannath University, Jaipur

38. Howtodealwithoverhead?
AproperalgorithmshouldtakeintoaccounttheCPUtime,
memoryusage,andnetworkbandwidthconsumedbythe
processorallocationalgorithmitself.
Howtocalculatecomplexity?
Ifanalgorithmperformsalittlebetterthanothersbutrequires
muchcompleximplementation,betterusethesimpleone.
Howtodealwithstability?
Problemscanariseifthestateofthemachineisnotstableyet,
stillintheprocessofupdating.
Sandeep Kumar Poonia, Jagannath University, Jaipur

39. Load distribution based on precedence
graph
Sandeep Kumar Poonia, Jagannath University, Jaipur
2
1
4
4
2
1
1 1
2
2
T1
T2
T3 T4
T5
T1
T2
T3
T4
T5
Time
1
2
P1 P2

40. Sandeep Kumar Poonia, Jagannath University, Jaipur
d d
T2
T3
T1
T1T1
T2T3
T1
T2
T3
T1
T2
T3
d

41. Two Optimal Scheduling Algorithms
The precedence graph is a tree
Sandeep Kumar Poonia, Jagannath University, Jaipur
T1 T2
T3 T4
T5
T6
T7
T8
T9
T10
T11
T12
T13
1
2
3
4
5T1 T2 T3
T4 T5 T7
T6 T9 T10
T8 T12
T11
T13

42. There are only two processors
Sandeep Kumar Poonia, Jagannath University, Jaipur
11 7
4
10
2
6
1 3
9
5
8
T9
T10
T11
T7 T8
T6
T4 T5
T1
T2
T3
T9 T10
T7 T8
T11 T6
T5 T4
T3 T2
T1

43. A graph-theoretic deterministic
algorithm
Sandeep Kumar Poonia, Jagannath University, Jaipur
A B C D
E F
G H I
3
6
4
3
2
4
1
2
5
5
8
2 3
4
12
E F
H4
3
1
2
12
A B C D
G I
8 5
54
2
Total network traffic: 2+4+3+4+2+8+5+2
=30
Total network traffic: 3+2+4+4+3+5+5+2
= 28