WIXLIB

Chapter 4: Processesn Process Conceptn Process Schedulingn Operations on Processesn Cooperating Processesn Interprocess Communicationn Communication in Client-Server SystemsOperating System Concepts4.1Silberschatz, Galvin and Gagne 2002Process Conceptn An operating system executes a variety of programs:F Batch system – jobsF Time-shared systems – user programs or tasksn Textbook uses the terms job and process almostinterchangeably.n Process – a program in execution; process executionmust progress in sequential fashion.n A process includes:Fprogram counterstackF data sectionFOperating System Concepts4.2Silberschatz, Galvin and Gagne 2002

Process Staten As a process executes, it changes stateF new: The process is being created.F running: Instructions are being executed.F waiting: The process is waiting for some event to occur.F ready: The process is waiting to be assigned to aprocessorF terminated: The process has finished execution.Operating System Concepts4.3Silberschatz, Galvin and Gagne 2002Diagram of Process StateOperating System Concepts4.4Silberschatz, Galvin and Gagne 2002

Process Control Block (PCB)Information associated with each process.n Process IDn Process staten Program countern CPU registersn CPU scheduling informationn Memory-management informationn Accounting informationn I/O status informationOperating System Concepts4.5Silberschatz, Galvin and Gagne 2002Process Control Block (PCB)Operating System Concepts4.6Silberschatz, Galvin and Gagne 2002

CPU Switch From Process to ProcessOperating System Concepts4.7Silberschatz, Galvin and Gagne 2002Process Scheduling Queuesn Job queue – set of all processes in the system.n Ready queue – set of all processes residing in mainmemory, ready and waiting to execute.n Device queues – set of processes waiting for an I/Odevice.n Processes migrate between the various queues.Operating System Concepts4.8Silberschatz, Galvin and Gagne 2002

Ready Queue And Various I/O Device QueuesOperating System Concepts4.9Silberschatz, Galvin and Gagne 2002Representation of Process SchedulingOperating System Concepts4.10Silberschatz, Galvin and Gagne 2002

Schedulersn Long-term scheduler (or job scheduler) – selects whichprocesses should be brought into the ready queue.n Short-term scheduler (or CPU scheduler) – selects whichprocess should be executed next and allocates CPU.Operating System Concepts4.11Silberschatz, Galvin and Gagne 2002Addition of Medium Term SchedulingOperating System Concepts4.12Silberschatz, Galvin and Gagne 2002

Schedulers (Cont.)n Short-term scheduler is invoked very frequently(milliseconds) (must be fast).n Long-term scheduler is invoked very infrequently(seconds, minutes) (may be slow).n The long-term scheduler controls the degree ofmultiprogramming.n Processes can be described as either:FI/O-bound process – spends more time doing I/O thancomputations, many short CPU bursts.F CPU-bound process – spends more time doingcomputations; few very long CPU bursts.Operating System Concepts4.13Silberschatz, Galvin and Gagne 2002Context Switchn When CPU switches to another process, the system mustsave the state of the old process and load the saved statefor the new process.n Context-switch time is overhead; the system does nouseful work while switching.n Time dependent on hardware support.Operating System Concepts4.14Silberschatz, Galvin and Gagne 2002

Process Creationn Parent process creates children processes, which, in turncreate other processes, forming a tree of processes.n Resource sharingF Parent and children share all resources.F Children share subset of parent’s resources.F Parent and child share no resources.n ExecutionF Parent and children execute concurrently.F Parent waits until children terminate.Operating System Concepts4.15Silberschatz, Galvin and Gagne 2002Process Creation (Cont.)n Address spaceF Child duplicate of parent.F Child has a program loaded into it.n UNIX examplesF fork system call creates new processF fork returns 0 to child , process id of child for parentF exec system call used after a fork to replace the process’memory space with a new program.Operating System Concepts4.16Silberschatz, Galvin and Gagne 2002

Unix Program#include stdio.h main(int argc, char *argv[]){ int pid;pid fork(); /* fork another process */if (pid 0) { /* child */exclp(“/bin/ls”,”ls”,NULL);}else { /* parent */wait(NULL); /* parent waits for child */printf(“Child complete\n”);exit(0);}}Operating System Concepts4.17Silberschatz, Galvin and Gagne 2002Processes Tree on a UNIX SystemOperating System Concepts4.18Silberschatz, Galvin and Gagne 2002

Process Terminationn Process executes last statement and asks the operatingsystem to delete it (exit).FFOutput data from child to parent (via wait).Process’ resources are deallocated by operating system.n Parent may terminate execution of children processes(abort).FChild has exceeded allocated resources.Task assigned to child is no longer required.F Parent is exiting.4 Operating system does not allow child to continue if itsparent terminates.4 Cascading termination.F In Unix, if parent exits children are assigned init as parentFOperating System Concepts4.19Silberschatz, Galvin and Gagne 2002Cooperating Processesn Independent process cannot affect or be affected by theexecution of another process.n Cooperating process can affect or be affected by theexecution of another processn Advantages of process cooperationFInformation sharingComputation speed-upF ModularityF ConvenienceFOperating System Concepts4.20Silberschatz, Galvin and Gagne 2002

Producer-Consumer Problemn Paradigm for cooperating processes, producer processproduces information that is consumed by a consumerprocess.Funbounded-buffer places no practical limit on the size of thebuffer.F bounded-buffer assumes that there is a fixed buffer size.Operating System Concepts4.21Silberschatz, Galvin and Gagne 2002Bounded-Buffer – Shared-Memory SolutionnnnnnOperating System ConceptsShared data#define BUFFER SIZE 10Typedef struct {.} item;item buffer[BUFFER SIZE];int in 0;int out 0;Circular arrayEmpty: in outFull: ((in 1)%BUFFER SIZE) outSolution is correct, but can only use BUFFER SIZE-1elements4.22Silberschatz, Galvin and Gagne 2002

Bounded-Buffer – Producer Processitem nextProduced;while (1) {while (((in 1) % BUFFER SIZE) out); /* do nothing */buffer[in] nextProduced;in (in 1) % BUFFER SIZE;}Operating System Concepts4.23Silberschatz, Galvin and Gagne 2002Bounded-Buffer – Consumer Processitem nextConsumed;while (1) {while (in out); /* do nothing */nextConsumed buffer[out];out (out 1) % BUFFER SIZE;}Operating System Concepts4.24Silberschatz, Galvin and Gagne 2002

Interprocess Communication (IPC)n Mechanism for processes to communicate and tosynchronize their actions.n Message system – processes communicate with eachother without resorting to shared variables.n IPC facility provides two operations:FFsend(message) – message size fixed or variablereceive(message)n If P and Q wish to communicate, they need to:F establish a communication link between themF exchange messages via send/receiven Implementation of communication linkF physical (e.g., shared memory, hardware bus) consideredlaterF logical (e.g., logical properties) nowOperating System Concepts4.25Silberschatz, Galvin and Gagne 2002Implementation Questionsn How are links established?n Can a link be associated with more than two processes?n How many links can there be between every pair ofcommunicating processes?n What is the capacity of a link?n Is the size of a message that the link can accommodatefixed or variable?n Is a link unidirectional or bi-directional?Operating System Concepts4.26Silberschatz, Galvin and Gagne 2002

Direct Communicationn Processes must name each other explicitly:F send (P, message) – send a message to process PF receive(Q, message) – receive a message from process Qn Properties of communication linkF Links are established automatically.F A link is associated with exactly one pair of communicatingprocesses.F Between each pair there exists exactly one link.F The link may be unidirectional, but is usually bi-directional.n Asymmetric variantF receive(id, message) – receive a message from anyprocess, pid stored in idOperating System Concepts4.27Silberschatz, Galvin and Gagne 2002Indirect Communicationn Messages are directed and received from mailboxes (alsoreferred to as ports).FFEach mailbox has a unique id.Processes can communicate only if they share a mailbox.n Properties of communication linkF Link established only if processes share a common mailboxF A link may be associated with many processes.F Each pair of processes may share several communicationlinks.F Link may be unidirectional or bi-directional.Operating System Concepts4.28Silberschatz, Galvin and Gagne 2002

Indirect Communicationn OperationsF create a new mailboxF send and receive messages through mailboxF destroy a mailboxn Primitives are defined as:send(A, message) – send a message to mailbox Areceive(A, message) – receive a message from mailbox AOperating System Concepts4.29Silberschatz, Galvin and Gagne 2002Indirect Communicationn Mailbox sharingF P1, P2, and P3 share mailbox A.F P1, sends; P2 and P3 receive.F Who gets the message?n SolutionsF Allow a link to be associated with at most two processes.F Allow only one process at a time to execute a receiveoperation.F Allow the system to select arbitrarily the receiver. Sender isnotified who the receiver was.Operating System Concepts4.30Silberschatz, Galvin and Gagne 2002

Synchronizationn Message passing may be either blocking or non-blocking.n Blocking is considered synchronousn Non-blocking is considered asynchronousn send and receive primitives may be either blocking ornon-blocking.Operating System Concepts4.31Silberschatz, Galvin and Gagne 2002Bufferingn Queue of messages attached to the link; implemented inone of three ways.1. Zero capacity – 0 messagesSender must wait for receiver (rendezvous).2. Bounded capacity – finite length of n messagesSender must wait if link full.3. Unbounded capacity – infinite lengthSender never waits.Exercise: Read about Mach and Windows 2000Operating System Concepts4.32Silberschatz, Galvin and Gagne 2002

Machn Mach kernel support creation of tasks – similar to processes butwith multiple threads of controln IPC, even system calls, is by messages using mailboxes calledportsn When task created, so are Kernel and Notify mailboxesFThe kernel communicates via kernel mailboxF Events are notified via Notify mailboxn Three system calls used for message transferF Msg send, msg receive, msg rpcF Msg rcp executes RPC by sending a message and waiting forexactly one return messagen Task creating mailbox using port allocate owns/receives from itn Messages from same sender are queued in FIFO order, but noother guarantees givenOperating System Concepts4.33Silberschatz, Galvin and Gagne 2002Machn Message headers contain destination mailbox and mailbox forrepliesn If mailbox not full the sending thread continues (non-blocking)n If full the sender canF Wait until there is roomF Wait at most n millisecsF Return immediatelyF Cache the message is OS temporarily (one only)nnnnReceivers can receive from mailbox or mailbox setSimilar options for receiverCan check # of msgs in mailbox with port status syscallMach avoids performance penalties associated with doublecopy (to/from mailbox) by using virtual-memory techniques tomap message into receiver’s memoryOperating System Concepts4.34Silberschatz, Galvin and Gagne 2002