OS_Unit_II_Ch3 Process and CPU Scheduling

This ppt covers following topics,
Process Concept
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server Systems

1. Process and CPU
Scheduling
Unit_II
Chap_3

2. Contents
Process Concept
Process Scheduling
Operations on Processes
Interprocess Communication
Examples of IPC Systems
Communication in Client-Server
Systems

3. Objectives
Tointroducethenotionofaprocess--a
programinexecution,whichformsthe
basisofallcomputation
Todescribethevariousfeaturesof
processes,includingscheduling,
creationand termination,and
communication
Toexploreinterprocesscommunication
usingsharedmemoryandmessage
passing
Todescribecommunicationinclient-
serversystems

4. Process Concept
Anoperatingsystemexecutesa
varietyofprograms:
◦Batchsystem–jobs
◦Time-sharedsystems–userprograms
ortasks
Process–aprograminexecution;
processexecutionmustprogress
insequentialfashion

5. Process Concept (Cont.)
Programispassiveentitystoredon
disk(executablefile),processis
active
oProgrambecomesprocesswhen
executablefileloadedintomemory
Memory

6. Oneprogramcanbeseveralprocesses
◦Considermultipleusersexecutingthesameprogram

7. The program code, also called text section
Currentactivityincludingprogram
counter,processorregisters
Stackcontainingtemporarydata
Functionparameters,returnaddresses,
localvariables
Datasectioncontainingglobalvariables
Heapcontainingmemorydynamically
allocatedduringruntime
Multiple parts
Process in Memory

8. Process States
As a process executes, it changes
◦new:The process is being created
◦running:Instructions are being executed
◦waiting:The process is waiting for some event to
occur
◦ready:The process is waiting to be assigned to a
processor
◦terminated:The process has finished execution
state

9. Diagram of Process State

10. Process Control Block (PCB)
Information associated with each
process
(also called task control block)
Process state –running, waiting,
etc
Program counter –location of
instruction to next execute
CPU registers –contents of all
process-centric registers
CPU scheduling information-
priorities, scheduling queue
pointers
Memory-management information –
memory allocated to the process
Accounting information –CPU
used, clock time elapsed since
start, time limits
I/O status information –I/O devices
allocated to process, list of open
files

11. CPU Switch From Process to
Process

12. Threads
Sofar,processhasasinglethreadof
execution
Considerhavingmultipleprogram
countersperprocess
◦Multiplelocationscanexecuteatonce
Multiplethreadsofcontrol→threads
Mustthenhavestorageforthread
details,multipleprogramcountersin
PCB
Seenextchapter

13. Process Scheduling
MaximizeCPUuse,quicklyswitch
processesontoCPUfortimesharing
Processschedulerselectsamong
availableprocessesfornextexecutionon
CPU
Maintainsschedulingqueues of
processes
◦Jobqueue–setofallprocessesinthe
system
◦Readyqueue–setofallprocessesresidingin
mainmemory,readyandwaitingtoexecute
◦Devicequeues–setofprocesseswaitingfor
anI/Odevice
◦Processesmigrateamongthevariousqueues

14. Ready Queue And Various I/O Device Queues

15. Representation of Process Scheduling
Queuing diagram represents queues, resources, flows

16. Schedulers
1. Short-term scheduler (or CPU scheduler)–selects which
process should be executed next and allocates CPU
◦Sometimes the only scheduler in a system
◦Short-term scheduler is invoked frequently (milliseconds) (must be
fast)
II. Long-term scheduler (or job scheduler)–selects which
processes should be brought into the ready queue
◦Long-term scheduler is invoked infrequently (seconds, minutes) 
(may be slow)
◦The long-term scheduler controls the degree of multiprogramming
Processes can be described as either:
◦I/O-bound process–spends more time doing I/O than computations,
many short CPU bursts
◦CPU-bound process –spends more time doing computations; few
very long CPU bursts
Long-term scheduler strives for good process mix

17. Addition of Medium Term
Scheduling
III. Medium-term scheduler can be added if degree of multiple
programming needs to decrease
Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping

18. Multitasking in Mobile Systems
Somemobilesystems(e.g.,earlyversionofiOS)allow
onlyoneprocesstorun,otherssuspended
Duetoscreenrealestate,userinterfacelimitsiOS
providesfora
◦Singleforegroundprocess-controlledviauserinterface
◦Multiplebackgroundprocesses–inmemory,running,butnot
onthedisplay,andwithlimits
◦Limitsincludesingle,shorttask,receivingnotificationof
events,specificlong-runningtaskslikeaudioplayback
Androidrunsforegroundandbackground,withfewerlimits
◦Backgroundprocessusesaservicetoperformtasks
◦Servicecankeeprunningevenifbackgroundprocessis
suspended
◦Servicehasnouserinterface,smallmemoryuse

19. Context Switch
WhenCPUswitchestoanotherprocess,the
systemmustsavethestateoftheoldprocess
andloadthesavedstateforthenewprocessvia
acontextswitch
ContextofaprocessrepresentedinthePCB
Context-switchtimeisoverhead;thesystem
doesnousefulworkwhileswitching
◦ThemorecomplextheOSandthePCBthelonger
thecontextswitch
Timedependentonhardwaresupport
◦Somehardwareprovidesmultiplesetsofregisters
perCPUmultiplecontextsloadedatonce

20. Theprocessofsavingthe
statusofan interrupted
processandloadingthestatus
ofthescheduledprocessis
known as
ContextSwitching.
Whenarunningprocessis
interruptedandtheOS
assignsanotherprocessand
transferscontroltoit,itis
known as
ProcessSwitching.

21. Contents
Process Concept
Process Scheduling
Operations on Processes
InterprocessCommunication
Examples of IPC Systems
Communication in Client-Server
Systems

22. Operations on Processes
System must provide mechanisms for:
process creation,
process termination,
and so on as detailed next

23. Process Creation
Parentprocesscreatechildrenprocesses,
which,inturncreateotherprocesses,forminga
treeofprocesses
Generally,processidentifiedandmanagedviaa
processidentifier(pid)
Resourcesharingoptions
Parentandchildrenshareallresources
Childrensharesubsetofparent’sresources
Parentandchildsharenoresources
Executionoptions
Parentandchildrenexecuteconcurrently
Parentwaitsuntilchildrenterminate

24. A Tree of Processes on a typical
Solaris

25. A Tree of Processes in Linuxinit
pid = 1
sshd
pid = 3028
login
pid = 8415
kthreadd
pid = 2
sshd
pid = 3610
pdflush
pid = 200
khelper
pid = 6
tcsch
pid = 4005
emacs
pid = 9204
bash
pid = 8416
ps
pid = 9298

26. Process Creation (Cont.)
Address space
◦Child duplicate of parent
◦Child has a program loaded into it
UNIX examples
◦fork()system call creates new process
◦exec()system call used after a fork()to replace the
process’memory space with a new program

27. Process Termination
Processexecuteslaststatementandthenasksthe
operatingsystemtodeleteitusingtheexit()
systemcall.
◦Returnsstatusdatafromchildtoparent(viawait())
◦Process’resourcesaredeallocatedbyoperatingsystem
Parentmayterminatetheexecutionofchildren
processesusingtheabort()systemcall.Some
reasonsfordoingso:
◦Childhasexceededallocatedresources
◦Taskassignedtochildisnolongerrequired
◦Theparentisexitingandtheoperatingsystemsdoesnot
allowachildtocontinueifitsparentterminates

28. Process Termination cont..
Someoperatingsystemsdonotallowchildtoexistsifitsparent
hasterminated.Ifaprocessterminates,thenallitschildrenmust
alsobeterminated.
◦cascadingtermination.Allchildren,grandchildren,etc.are
terminated.
◦Theterminationisinitiatedbytheoperatingsystem.
Theparentprocessmaywaitforterminationofachildprocess
byusingthewait()systemcall.Thecallreturnsstatus
informationandthepidoftheterminatedprocess
pid=wait(&status);
Ifnoparentwaiting(didnotinvokewait())processisazombie
Ifparentterminatedwithoutinvokingwait,processisan
orphan

29. AZombieprocessordefunctprocessisaprocess
thathascompletedexecution(viaexitsystemcall)
butstillhasanentryintheprocesstable.Itisa
processinthe“Terminatedstate”.
Thisoccursforchildprocesses,wheretheprocess
tableentryisstillneededtoallowtheparentprocess
toreaditschild’sexitstatus:oncetheexitstatusis
readviawaitsystemcallbytheparentprocess.
AnOrphanprocessisaprocessthatisstill
executing,butwhoseparenthasdied.Whenthe
parentdies,theorphanedchildprocessisadopted
byinitorsystemd(processID)

30. MultiprocessArchitecture –Chrome Browser
Manywebbrowsersrunassingleprocess(some
stilldo)
◦Ifonewebsitecausestrouble,entirebrowsercan
hangorcrash
GoogleChromeBrowserismultiprocesswith3
differenttypesofprocesses:
◦Browserprocessmanagesuserinterface,diskand
networkI/O
◦Rendererprocessrenderswebpages,dealswith
HTML,Javascript.Anewrenderercreatedforeach
websiteopened
RunsinsandboxrestrictingdiskandnetworkI/O,
minimizingeffectofsecurityexploits
◦Plug-inprocessforeachtypeofplug-in

31. InterprocessCommunication
Processeswithinasystemmaybeindependentor
cooperating
Cooperatingprocesscanaffectorbeaffectedby
otherprocesses,includingsharingdata
Reasonsforcooperatingprocesses:
◦Informationsharing
◦Computationspeedup
◦Modularity
◦Convenience
Cooperatingprocessesneedinterprocess
communication(IPC)
TwomodelsofIPC
◦Sharedmemory
◦Messagepassing

32. Cooperating Processes
Independentprocesscannotaffectorbe
affectedbytheexecutionofanother
process
Cooperatingprocesscanaffectorbe
affectedbytheexecutionofanother
process
Advantagesofprocesscooperation
◦Informationsharing
◦Computationspeed-up
◦Modularity
◦Convenience

33. Producer-Consumer Problem
Paradigmforcooperatingprocesses,
producerprocessproducesinformation
thatisconsumedbyaconsumer
process
◦unbounded-bufferplacesnopracticallimit
onthesizeofthebuffer
◦bounded-bufferassumesthatthereisa
fixedbuffersize

34. Bounded-Buffer –Shared-Memory Solution
Shared data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

35. Bounded-Buffer
item next_produced;
while (true) {
/* produce an item
in next produced */
while (((in + 1) %
BUFFER_SIZE) == out);
/* do nothing */
buffer[in] =
next_produced;
in = (in + 1) %
BUFFER_SIZE;
}
item next_consumed;
while (true) {
while (in == out);
/* do nothing */
next_consumed=
buffer[out];
out = (out + 1) %
BUFFER_SIZE;
/* consume the item in
next consumed */
}
Producer Consumer
This scheme allows at most BUFFER_SIZE -1 items
in the buffer at the same time.

36. Communications Models
(a) Message passing. (b) shared memory.

37. InterprocessCommunication –Shared
Memory
Anareaofmemorysharedamongtheprocesses
thatwishtocommunicate
Thecommunicationisunderthecontrolofthe
usersprocessesnottheoperatingsystem.
Majorissuesistoprovidemechanismthatwill
allowtheuserprocessestosynchronizetheir
actionswhentheyaccesssharedmemory.
Synchronizationisdiscussedingreatdetailsin
Chapter5.

38. Two kinds of buffers
Unbounded buffer Bounded buffer
FULL
WAIT

39. InterprocessCommunication –Message
Passing
Mechanism for processes to communicate and to
synchronize their actions
Message system –processes communicate with
each other without resorting to shared variables
IPC facility provides two operations:
◦send(message)
◦receive(message)
Themessagesize is either fixed or variable

40. Message Passing (Cont.)
IfprocessesPandQwishto
communicate,theyneedto:
◦Establishacommunicationlinkbetween
them
◦Exchangemessagesviasend/receive
Implementationissues:
 Naming
 Synchronization
 Buffering

41. Message Passing (Cont.)
Implementation of communication link
◦Physical:
Shared memory
Hardware bus
Network
◦Logical:
Directorindirect
Synchronousorasynchronous
Automaticorexplicit buffering

42. Direct Communication
Processesmustnameeachother
explicitly:
◦send(P,message)–sendamessageto
processP
◦receive(Q,message)–receiveamessage
fromprocessQ
Propertiesofcommunicationlink
◦Linksareestablishedautomatically
◦Alinkisassociatedwithexactlyonepairof
communicatingprocesses
◦Betweeneachpairthereexistsexactlyonelink
◦Thelinkmaybeunidirectional,butisusuallybi-
directional

43. Indirect Communication
Messagesaredirectedandreceivedfrommailboxes8(also
referredtoasports)
◦Eachmailboxhasauniqueid
◦Processescancommunicateonlyiftheyshareamailbox
Propertiesofcommunicationlink
◦Linkestablishedonlyifprocessesshareacommonmailbox
◦Alinkmaybeassociatedwithmanyprocesses
◦Eachpairofprocessesmayshareseveralcommunicationlinks
◦Linkmaybeunidirectionalorbi-directional

44. Indirect Communication cont…
Primitivesaredefinedas:
send(A,message)–sendamessageto
mailboxA
receive(A,message)–receivea
messagefrommailboxA
Operations
◦createanewmailbox(port)
◦sendandreceivemessagesthrough
mailbox
◦destroyamailbox

45. Synchronization
Messagepassingmaybeeitherblockingornon-
blocking
Blockingisconsideredsynchronous
◦Blockingsend--thesenderisblockeduntilthe
messageisreceived
◦Blockingreceive--thereceiverisblockeduntila
messageisavailable
Non-blockingisconsideredasynchronous
◦Non-blockingsend--thesendersendsthemessage
andcontinue
◦Non-blockingreceive--thereceiverreceives:
Avalidmessage,or
Nullmessage
Differentcombinationspossible
Ifbothsendandreceiveareblocking,wehavea
rendezvous

46. Buffering
Queueofmessagesattachedtothelink.
implementedinoneofthreeways
1.Zerocapacity–nomessagesarequeued
on a link.
Sendermustwaitforreceiver(rendezvous)
2.Boundedcapacity–finitelengthofn
messages
Sendermustwaitiflinkfull
3.Unboundedcapacity–infinitelength
Senderneverwaits

47. Examples of IPC Systems –Windows
Message-passingcentricviaadvanced
localprocedurecall(LPC)facility
◦Onlyworksbetweenprocessesonthesame
system
◦Usesports(likemailboxes)toestablishand
maintaincommunicationchannels
◦Communicationworksasfollows:
Theclientopensahandletothesubsystem’s
connectionportobject.
Theclientsendsaconnectionrequest.
Theservercreatestwoprivatecommunication
portsandreturnsthehandletooneofthemtothe
client.
Theclientandserverusethecorrespondingport
handletosendmessagesorcallbacksandtolisten
forreplies.

48. Local Procedure Calls in Windows