Transcription
ProcessesChapter 3 2015 Prof. Amr El-Kadi
Process Concept An operating system executes avariety of programs:– Batch system – jobs– Time-shared systems – userprograms or tasks the terms job and process areused almost interchangeably 2015 Prof. Amr El-Kadi2
Process in Memory Process – a program inexecution; process executionmust progress in sequentialfashionA process includes:– program counter– stack data section 2015 Prof. Amr El-Kadi3
Two-State Process Model Process may be in one of two states– Running– Not-running 2015 Prof. Amr El-Kadi4
A Five-State Model As a process executes, it changes state– new: The process is being created– running: Instructions are being executed– Waiting (Blocked): The process is waiting forsome event to occur– ready: The process is waiting to be assigned toa processor– terminated: The process has finished execution 2015 Prof. Amr El-Kadi5
Diagram of Process State 2015 Prof. Amr El-Kadi6
Process Description 2015 Prof. Amr El-Kadi7
Operating System ControlStructures Information about the current status ofeach process and resource Tables are constructed for each entity theoperating system manages 2015 Prof. Amr El-Kadi8
Operating System ControlStructures (cont.) 2015 Prof. Amr El-Kadi9
User Processes in VirtualMemory 2015 Prof. Amr El-Kadi10
Process Control Block (PCB) Information associated with each process–––––––Process stateProgram counterCPU registersCPU scheduling informationMemory-management informationAccounting informationI/O status information 2015 Prof. Amr El-Kadi11
Context Switch When CPU switches to anotherprocess, the system must save thestate of the old process and load thesaved state for the new process Context-switch time is overhead; thesystem does no useful work whileswitching Time dependent on hardware support 2015 Prof. Amr El-Kadi12
CPU Switch From Process toProcess 2015 Prof. Amr El-Kadi13
The Role of the Process ControlBlock 2015 Prof. Amr El-Kadi14
Process Scheduling Queues Job queue – set of all processes in thesystem Ready queue – set of all processesresiding in main memory, ready andwaiting to execute Device queues – set of processeswaiting for an I/O device Processes migrate among the variousqueues 2015 Prof. Amr El-Kadi15
Using Two Queues 2015 Prof. Amr El-Kadi16
Ready Queue And Various I/ODevice Queues 2015 Prof. Amr El-Kadi17
Representation of ProcessScheduling 2015 Prof. Amr El-Kadi18
Schedulers Long-term scheduler (or jobscheduler) – selects whichprocesses should be brought intothe ready queue Short-term scheduler (or CPUscheduler) – selects whichprocess should be executed nextand allocates CPU 2015 Prof. Amr El-Kadi19
Addition of Medium TermScheduling 2015 Prof. Amr El-Kadi20
Schedulers (Cont.) Short-term scheduler is invoked veryfrequently (milliseconds) (must be fast) Long-term scheduler is invoked veryinfrequently (seconds, minutes) (may beslow) The long-term scheduler controls thedegree of multiprogramming 2015 Prof. Amr El-Kadi21
Schedulers (Cont.) Processes can be described as either:– I/O-bound process – spends more timedoing I/O than computations, many shortCPU bursts– CPU-bound process – spends moretime doing computations; few very longCPU bursts 2015 Prof. Amr El-Kadi22
Process Control: Modes ofExecution User mode– Less-privileged mode– User programs typically execute in this mode System mode, control mode, or kernelmode– More-privileged mode– Kernel of the operating system 2015 Prof. Amr El-Kadi23
Process Creation Parent process create childrenprocesses, which, in turn create otherprocesses, forming a tree of processes Resource sharing– Parent and children share all resources– Children share subset of parent’s resources– Parent and child share no resources 2015 Prof. Amr El-Kadi24
Process Creation (Cont.) Execution– Parent and children execute concurrently– Parent waits until children terminate 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 replacethe process’ memory space with a newprogram 2015 Prof. Amr El-Kadi25
Process Creation 2015 Prof. Amr El-Kadi26
Process Creation in POSIX 2015 Prof. Amr El-Kadi27
Process Termination Process executes last statement andasks the operating system to delete it(exit)– Output data from child to parent (viawait)– Process’ resources are deallocated byoperating system 2015 Prof. Amr El-Kadi28
Process Termination (cont.) Parent may terminate execution ofchildren processes (abort)– Child has exceeded allocated resources– Task assigned to child is no longer required– If parent is exiting Some operating system do not allow child tocontinue if its parent terminates– All children terminated - cascading termination 2015 Prof. Amr El-Kadi29
Interprocess CommunicationMessage PassingShared Memory 2015 Prof. Amr El-Kadi30
Cooperating Processes Independent process cannot affect or beaffected by the execution of another process Cooperating process can affect or beaffected by the execution of another process Advantages of process cooperation––––Information sharingComputation speed-upModularityConvenience 2015 Prof. Amr El-Kadi31
Producer-Consumer Problem Paradigm for cooperating processes,producer process produces informationthat is consumed by a consumerprocess– unbounded-buffer places no practical limiton the size of the buffer– bounded-buffer assumes that there is afixed buffer size 2015 Prof. Amr El-Kadi32
Bounded-Buffer – SharedMemory Solution Shared data#define BUFFER SIZE 10typedef struct {.} item;item buffer[BUFFER SIZE];int in 0;int out 0; Solution is correct, but can only use BUFFER SIZE1 elements 2015 Prof. Amr El-Kadi33
Bounded-Buffer – Shared-MemorySolution 2015 Prof. Amr El-Kadi34
Bounded-Buffer – Shared-MemorySolution 2015 Prof. Amr El-Kadi35
Bounded-Buffer -- insert() method 2015 Prof. Amr El-Kadi36
Bounded-Buffer - remove() method 2015 Prof. Amr El-Kadi37
Interprocess Communication – Message Passing Mechanism for processes to communicate and tosynchronize their actions Message system – processes communicate witheach other without resorting to shared variables IPC facility provides two operations:– send(message) – message size fixed or variable– receive(message) If P and Q wish to communicate, they need to:– establish a communication link between them– exchange messages via send/receive Implementation of communication link– physical (e.g., shared memory, hardware bus)– logical (e.g., logical properties) 2015 Prof. Amr El-Kadi38
Implementation Questions How are links established? Can a link be associated with more than twoprocesses? How many links can there be between everypair of communicating processes? What is the capacity of a link? Is the size of a message that the link canaccommodate fixed or variable? Is a link unidirectional or bi-directional? 2015 Prof. Amr El-Kadi39
Direct Communication Processes must name each other explicitly:– send (P, message) – send a message to process P– receive(Q, message) – receive a message fromprocess Q Properties of communication link– Links are established automatically– A link is associated with exactly one pair ofcommunicating processes– Between each pair there exists exactly one link– The link may be unidirectional, but is usually bidirectional 2015 Prof. Amr El-Kadi40
Indirect Communication Messages are directed and received frommailboxes (also referred to as ports)– Each mailbox has a unique id– Processes can communicate only if they sharea mailbox Properties of communication link– Link established only if processes share acommon mailbox– A link may be associated with many processes– Each pair of processes may share severalcommunication links– Link may be unidirectional or bi-directional 2015 Prof. Amr El-Kadi41
Indirect Communication Operations– create a new mailbox– send and receive messages throughmailbox– destroy a mailbox Primitives are defined as:send(A, message) – send a messageto mailbox Areceive(A, message) – receive amessage from mailbox A 2015 Prof. Amr El-Kadi42
Indirect Communication Mailbox sharing– P1, P2, and P3 share mailbox A– P1, sends; P2 and P3 receive– Who gets the message? Solutions– Allow a link to be associated with at most twoprocesses– Allow only one process at a time to execute areceive operation– Allow the system to select arbitrarily the receiver.Sender is notified who the receiver was. 2015 Prof. Amr El-Kadi43
Synchronization Message passing may be either blockingor non-blocking Blocking is considered synchronous– Blocking send has the sender block untilthe message is received– Blocking receive has the receiver blockuntil a message is available Non-blocking is consideredasynchronous– Non-blocking send has the sender sendthe message and continue– Non-blocking receive has the receiverreceive a valid message or null 2015 Prof. Amr El-Kadi44
Buffering Queue of messages attached to thelink; implemented in one of three ways1. Zero capacity – 0 messagesSender must wait for receiver(rendezvous)2. Bounded capacity – finite length of nmessagesSender must wait if link full3. Unbounded capacity – infinite lengthSender never waits 2015 Prof. Amr El-Kadi45
Process Concept An operating system executes a variety of programs: –Batch system –jobs –Time-shared systems –user programs or tasks