CHAPTER 4: PROCESSESn nProcess conceptn nProcess schedulingn nProcess operationsn nProcess cooperatingn nInter-process communicationn nCommunication in client-server systemsPROCESS CONCEPTn nAn operating system executes a variety of programs:An operating system executes a variety of programs:uuBatch system jobsBatch system jobsuuTime-shared systems system/user programs or Time-shared systems system/user programs or tasks.tasks. Processes (The current popular term). Processes (The current popular term).n nProcess a program in execution. Process a program in execution. uuRelationship between process and program. Relationship between process and program. n nTwo or more processes may be associated with the same Two or more processes may be associated with the same program. A process can spawn new processes. program. A process can spawn new processes. n nA process includes:A process includes:uuprogram code program code uuprogram counter value and processor register program counter value and processor register contentscontentsuustack section and data sectionstack section and data sectionProcess concept: Statesn nTwo state modeln nFive state modeln nSix state modeln nSeven State modeln nOther modelsProcess concept: Two state modelProcess concept: Five state modelProcess concept: Five state modelProcess concept: Five state modelProcess concept: Six state modelProcess concept: Seven state modelProcess concept: PCBPCB: Information associated with each process.PCB: Information associated with each process.n nProcess state,Process state,n nProgram counter,Program counter,n nCPU registers (This info must be saved in order to CPU registers (This info must be saved in order to allow the process to be continued correctly afterward, allow the process to be continued correctly afterward, See the following Fig),See the following Fig),n nCPU scheduling information,CPU scheduling information,n nMemory-management information,Memory-management information,n nI/O status information,I/O status information,n nAccounting information,Accounting information,n nFor Linux: /usr/src/linux-2.4/include/linux/sched.hFor Linux: /usr/src/linux-2.4/include/linux/sched.hProcess concept: PCBProcess concept: PCBPROCESS SCHEDULINGn nThe Queues in the OSThe Queues in the OSuuJob queue,Job queue,uuRead queue: set of all processes ready for execution. Read queue: set of all processes ready for execution. (Swapped out or in main memory),(Swapped out or in main memory),uuDevice queue: A set of processes waiting for an I/O Device queue: A set of processes waiting for an I/O device. Each device has its own device queue. device. Each device has its own device queue. n nA process migrates among the various queues throughout A process migrates among the various queues throughout its life time. its life time. Process scheduling: Ready Queue Various I/O Device QueuesProcess scheduling: RepresentationProcess scheduling: Schedulersn nThe lifetime of a processThe lifetime of a processuuJob pool Job pool memory pool memory pool CPU pool CPU pooln nLong-term scheduler (or job scheduler) (Long-term scheduler (or job scheduler) (长程调度长程调度) selects which processes should be brought into ) selects which processes should be brought into the system.the system.n nMedium-term scheduler (Medium-term scheduler (中程调度中程调度) selects which ) selects which swapped out process should be swapping into swapped out process should be swapping into memory.memory.n nShort-term scheduler (or CPU scheduler) (Short-term scheduler (or CPU scheduler) (短程调度短程调度) selects which process should be executed next ) selects which process should be executed next and allocates CPU.and allocates CPU.Process scheduling: Schedulersn nShort-term scheduler is invoked very frequently Short-term scheduler is invoked very frequently (milliseconds) (milliseconds) must be fast.must be fast.n nMedium-term scheduler is invoked infrequently Medium-term scheduler is invoked infrequently fast.fast.n nLong-term scheduler is invoked very infrequently Long-term scheduler is invoked very infrequently (seconds, minutes) (seconds, minutes) may be slow. may be slow. uuThe long-term scheduler controls the The long-term scheduler controls the degree of degree of multiprogramming.multiprogramming.uuThe long-term scheduler should select a good process The long-term scheduler should select a good process mix of I/O-bound and CPU-bound processes.mix of I/O-bound and CPU-bound processes. t tI/O-I/O-bound processbound process (I/O (I/O约束进程约束进程) spends more ) spends more time doing I/O than computations, many short CPU time doing I/O than computations, many short CPU bursts.bursts.t tCPUCPU- -bound processbound process （CPUCPU约束进程）约束进程） spends spends more time doing computations; few very long CPU more time doing computations; few very long CPU bursts.bursts.Process scheduling: Context switchn nWhen CPU switches to another process, the system When CPU switches to another process, the system must save the context of the old process and load the must save the context of the old process and load the saved context for the new process.saved context for the new process.uuThe context of a process is represented in the PCB The context of a process is represented in the PCB of a process. of a process. uuTo freeze it; to preserve it; to thaw it. To freeze it; to preserve it; to thaw it. n nContext-switch time is overhead; the system does no Context-switch time is overhead; the system does no useful work while switching.useful work while switching.n nContext-switch time is mainly dependent on hardware Context-switch time is mainly dependent on hardware support.support.n nOS programmer try new structures to reduce context-OS programmer try new structures to reduce context-switch time whenever possible. switch time whenever possible. PROCESS OPERATIONn nProcess creationProcess creationn nProcess execution Process execution uuGet/set process attributesGet/set process attributesuuWait for time/event/Wait for time/event/uuSignal eventsSignal eventsuuAllocate/free memoryAllocate/free memoryn nProcess terminationProcess terminationn nProcess communicationProcess communicationuuShard-memory (Threads belonging to single Shard-memory (Threads belonging to single process)process)uuIPC on the same computerIPC on the same computeruuC/S on the distributed systems. C/S on the distributed systems. Process operation: Process creationParent process create children processes, which, in turn Parent process create children processes, which, in turn create other processes, forming a tree of processes.create other processes, forming a tree of processes.Process operation: Process creationn nIn general, a process will need certain resources to In general, a process will need certain resources to accomplish its task. accomplish its task. n nResource sharingResource sharinguuParent and children share all resources.Parent and children share all resources.uuChildren share subset of parents resources.Children share subset of parents resources.uuParent and child share no resources.Parent and child share no resources.n nExecutionExecutionuuParent and children execute concurrently.Parent and children execute concurrently.uuParent waits until children terminate.Parent waits until children terminate.Process operation: Process creationn nAddress spaceAddress spaceuuThe child process is a duplicate of the parent The child process is a duplicate of the parent process.process.uuThe child has a program loaded into it.The child has a program loaded into it.n nThe DEC VMS exampleThe DEC VMS exampleuuCreating a new process and loading a specified Creating a new process and loading a specified program into that process and starting it running. program into that process and starting it running. n nThe UNIX exampleThe UNIX exampleuuforkfork system call creates new process system call creates new processuuexecexec system call used after a system call used after a forkfork to replace the to replace the process memory space with a new program.process memory space with a new program.Process operation: Process terminationn nProcess executes last statement and asks the operating Process executes last statement and asks the operating system to decide it (system to decide it (exitexit). ).uuOutput data from child to parent (via Output data from child to parent (via waitwait). ).uuProcess resources are de-allocated.Process resources are de-allocated.n nParent may terminate execution of children processes Parent may terminate execution of children processes ( (abortabort). ).uuChild has exceeded allocated resources.Child has exceeded allocated resources.uuTask assigned to child is no longer required.Task assigned to child is no longer required.uuParent is exiting.Parent is exiting.t tOperating system does not allow child to continue Operating system does not allow child to continue if its parent terminates.if its parent terminates.t tCascading termination.Cascading termination.PROCESS COOPERATINGn nIndependent processes vs cooperating processesIndependent processes vs cooperating processesuuIndependentIndependent process cannot affect or be affected by the process cannot affect or be affected by the execution of another process.execution of another process.uuCooperatingCooperating process can affect or be affected by the process can affect or be affected by the execution of another processexecution of another processn nWhy process cooperation?Why process cooperation?uuInformation sharing Information sharing uuComputation speed-upComputation speed-upuuModularity (system)Modularity (system)uuConvenience (user)Convenience (user)n nMechanisms for process cooperationMechanisms for process cooperationuuCommunication and Communication and uusynchronizationsynchronizationProcess cooperating: The Producer-consumer problemn nThe producer-consumer problem: a The producer-consumer problem: a producerproducer process process produces information that is consumed by a produces information that is consumed by a consumerconsumer process.process.uuPrint program Print program print driver, print driver,uuCompiler Compiler assembler assembler loader. loader.n nCommunication choices:Communication choices:uuIPC (Interprocess-communication),IPC (Interprocess-communication),uuShared memory.Shared memory.SHARED MEMORY COMMUNICATIONn nA buffer pool: filled by the producer and consumed A buffer pool: filled by the producer and consumed by the consumer. by the consumer. uuunbounded-bufferunbounded-buffer places no practical limit on the places no practical limit on the size of the buffer,size of the buffer,uubounded-bufferbounded-buffer assumes that there is a fixed buffer assumes that there is a fixed buffer size.size.Shared memory: Bounded-Buffer Shared-Memory Solutionn nShared dataShared data#define BUFFER_SIZE 10#define BUFFER_SIZE 10typedef struct typedef struct . . . . . item; item;item bufferBUFFER_SIZE;item bufferBUFFER_SIZE;int in = 0;int in = 0;int out = 0;int out = 0;Shared memory: Bounded-Buffer Shared-Memory Solutionn nProducer processitem nextProduced;item nextProduced;while (1) while (1) while(in + 1)%BUFFER_SIZE) = while(in + 1)%BUFFER_SIZE) = out)out); /* do nothing */; /* do nothing */bufferin = nextProduced;bufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;in = (in + 1) % BUFFER_SIZE; Shared memory: Bounded-Buffer Shared-Memory Solutionn nConsumer Processitem nextConsumed;item nextConsumed;while (1) while (1) while (in = out)while (in = out); /* do nothing */; /* do nothing */nextConsumed = bufferout;nextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;out = (out + 1) % BUFFER_SIZE; INTER-PROCESS COMMUNICATION (IPC)n nIPC v.s. Shared-memoryIPC v.s. Shared-memoryuuEfficiency,Efficiency,uuCentralized vs Distributed. Centralized vs Distributed. n nTwo IPC operationsTwo IPC operationsuusend send uureceivereceiven nIPC issuesIPC issuesuuNaming: direct or indirect communicationNaming: direct or indirect communicationuuSymmetric or asymmetric communicationSymmetric or asymmetric communicationuuAutomatic or explicit bufferingAutomatic or explicit bufferinguuSend by copy or send by referenceSend by copy or send by referenceuuFixed-sized or variable-sized messagesFixed-sized or variable-sized messagesInter-Process Communication (IPC)n nImplementation issuesImplementation issuesuuHow to refer to each other: How to refer to each other: t tDirect communication Direct communication t tIndirect communicationIndirect communicationuuHow to synchronize each otherHow to synchronize each othert tBlocking Blocking t tNonblockingNonblockinguuHow to handle messages in the link.How to handle messages in the link.IPC: Namingn nDirect communicationDirect communicationuuProcesses must name each other explicitly:Processes must name each other explicitly:t tsendsend ( (P, messageP, message) send to process P) send to process Pt treceivereceive( (Q, messageQ, message) receive from process Q) receive from process QuuProperties of direct communication linkProperties of direct communication linkt tLinks are established automatically.Links are established automatically.t tA link is associated with exactly one pair of A link is associated with exactly one pair of communicating processes.communicating processes.t tBetween each pair there exists exactly one link.Between each pair there exists exactly one link.uuAsymmetry in addressingAsymmetry in addressingt tSend (P, message)Send (P, message)t tReceive (id, message): the variable id is set to the name of Receive (id, message): the variable id is set to the name of the process with which communication has taken place. the process with which communication has taken place. IPC: Namingn nIndirect communicationIndirect communicationuuMessages are directed and received from mailboxes Messages are directed and received from mailboxes (also referred to as ports).(also referred to as ports).t tEach mailbox has a unique id.Each mailbox has a unique id.t tProcesses can communicate only if they share a Processes can communicate only if they share a mailbox.mailbox.uuTwo primitivesTwo primitivest tsendsend( (A, messageA, message) send a message to mailbox ) send a message to mailbox A At treceivereceive( (A, messageA, message) receive a message from ) receive a message from mailboxmailboxIPC: Namingn nHow about three processes?How about three processes?uuP P1 1, P, P2 2, , and and P P3 3 share mailbox A. share mailbox A.uuP P1 1, sends; , sends; P P2 2 andand P P3 3 receive. receive.uuWho gets the message?Who gets the message?uuSolutionsSolutionst tAllow a link to be associated with at most two Allow a link to be associated with at most two processes.processes.t tAllow only one process at a time to execute a Allow only one process at a time to execute a receive operation.receive operation.t tAllow the system to select arbitrarily the Allow the system to select arbitrarily the receiver. The sender is notified who the receiver. The sender is notified who the receiver was.receiver was.IPC: Namingn nProperties of indirect communication linkProperties of indirect communication linkuuLink established only if processes share a common Link established only if processes share a common mailboxmailboxuuA link may be associated with many processes.A link may be associated with many processes.uuEach pair of processes may share several Each pair of processes may share several communication links.communication links.uuLink may be unidirectional or bi-directional.Link may be unidirectional or bi-directional.uuMailbox can be owned by a process or OS. Mailbox can be owned by a process or OS. t tcreate a new mailboxcreate a new mailboxt tsend and receive messages through mailboxsend and receive messages through mailboxt tdestroy a mailboxdestroy a mailboxIPC: Synchronizationn nBlocking and NonblockingBlocking and NonblockinguuBlocking sendBlocking senduuNonblocking sendNonblocking senduuBlocking receiveBlocking receiveuuNonblocking receiveNonblocking receiven nBlocking send and blocking receive Blocking send and blocking receive rendezvous.rendezvous.n nNonblocking send and blocking receive Nonblocking send and blocking receive the most the most common one.common one.IPC: Bufferingn nQueue of messages attached to the link; implemented Queue of messages attached to the link; implemented in one of three ways.in one of three ways.uuZero capacity 0 messagesZero capacity 0 messagesSender must wait for receiver (rendezvous).Sender must wait for receiver (rendezvous).uuBounded capacity finite length of Bounded capacity finite length of n n messages messagesSender must wait if link full.Sender must wait if link full.uuUnbounded capacity infinite length Unbounded capacity infinite length Sender never waits.Sender never waits.IPC: An example: Machn nEach task has two special mailboxes: the Kernel Each task has two special mailboxes: the Kernel mailbox and the Notify mailbox. mailbox and the Notify mailbox. n nMessage transferringMessage transferringuumsg_send, msg_receive, msg_rpc. msg_send, msg_receive, msg_rpc. n nMailbox creationMailbox creationuuport_allocate.port_allocate.IPC: An example: Windows 2Kn nLPC: local procedure call facilityLPC: local procedure call facilityn nTwo types of ports: connection ports and Two types of ports: connection ports and communication ports.communication ports.n nMessage-passing techniquesMessage-passing techniquesuuFor small messages, to use the ports message For small messages, to use the ports message queue as intermediate storage and copies the queue as intermediate storage and copies the message from one process to othermessage from one process to otheruuFor a large message, to pass the message through For a large message, to pass the message through a section object (or shared memory)a section object (or shared memory)uuCLIENT-SERVER COMMUNICATIONn nSocketsn nRemote Procedure Callsn nRemote Method Invocation (Java)C/S: Socketsn nA socket is defined as an endpoint for communication.n nConcatenation of IP address and portn nThe socket 161.25.19.8:1625 refers to port 1625 on host n nCommunication consists between a pair of sockets.C/S: Socket CommunicationC/S: Java Socket Programmingn nWriting C/S Application using Java Sockets Writing C/S Application using Java Sockets uuKnockKnockProtocol KnockKnockProtocol ServerServer: Knock knock!: Knock knock!ClientClient: Whos there?: Whos there?ServerServer: Dexter.: Dexter.ClientClient: Dexter who?: Dexter who?ServerServer: Dexter halls with boughs of holly.: Dexter halls with boughs of holly.ClientClient: Groan. : Groan. uuKnockKnockClient KnockKnockClient uuKnockKnockServer KnockKnockServer C/S: Remote Procedure Callsn nRemote procedure call (RPC) abstracts procedure Remote procedure call (RPC) abstracts procedure calls between processes on networked systems.calls between processes on networked systems.n nStubsStubs client-side proxy for the actual client-side proxy for the actual procedure on the server.procedure on the server.n nThe client-side stub locates the server and The client-side stub locates the server and marshallsmarshalls the parameters. the parameters.n nThe server-side stub receives this message, The server-side stub receives this message, unpacks the marshalled parameters, and performs unpacks the marshalled parameters, and performs the procedure on the server.the procedure on the server.n nXDR (External data representation).XDR (External data representation).C/S: Execution of RPCC/S: Remote Method Invocationn nRemote Method Invocation (RMI) is a Java mechanism similar to RPCs.n nRMI allows a Java program on one machine to invoke a method on a remote object.C/S: Marshalling ParametersExercisesn nExercisesuu4.2uu4.4uu4.5uu4.8*