CS221-03-Processes.pdf

PROCESSES Lecture 3 PROCESS CONCEPT ØAn operating system executes a variety of programs that run as a process. ØProcess: a program in execution; process execution must progress in sequential fashion. No parallel execution of instructions of a single process ØMultiple parts ­ The program code, al...

PROCESSES Lecture 3 PROCESS CONCEPT ØAn operating system executes a variety of programs that run as a process. ØProcess: a program in execution; process execution must progress in sequential fashion. No parallel execution of instructions of a single process ØMultiple parts ­ The program code, also called text section ­ Current activity including program counter, processor registers ­ Stack containing temporary data ­ Function parameters, return addresses, local variables ­ Data section containing global variables ­ Heap containing memory dynamically allocated during run time 2 PROCESS CONCEPT (CONT.) ØProgram is passive entity stored on disk (executable file); process is active ­ Program becomes process when an executable file is loaded into memory ØExecution of program started via GUI mouse clicks, command line entry of its name, etc. ØOne program can be several processes ­ Consider multiple users executing the same program 3 MEMORY LAYOUT OF A C PROGRAM 4 PROCESS STATE ØAs a process executes, it changes state ­ 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 5  new terminated admitted exit interrupt ready running scheduler dispatch I/O or event completion I/O or event wait waiting DIAGRAM OF PROCESS STATE 6  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 7 PROCESS CONTROL BLOCK (PCB) (CONT.) ØSo far, process has a single thread of execution ØConsider having multiple program counters per process ­ Multiple locations can execute at once ­ Multiple threads of control -> threads ØMust then have storage for thread details, multiple program counters in PCB (detail in Lecture 4) 8 PROCESS SCHEDULING ØProcess scheduler selects among available processes for next execution on CPU ØGoal: Maximize CPU use ØMaintains scheduling queues of processes ­ Ready queue – set of all processes residing in main memory, ready and waiting to execute ­ Wait queues – set of processes waiting for an event (i.e., I/O) ­ Processes migrate among the various queues 9 READY AND WAIT QUEUES 10  REPRESENTATION OF PROCESS SCHEDULING ØA common representation of process scheduling is called Queueing-diagram Jobs ready queue CPU I/O I/O queue I/O request time slice expired child fork a executes child interrupt wait for an occurs interrupt 11 CPU SWITCH FROM PROCESS TO PROCESS ØA context switch occurs when the CPU switches from one process to another. process P0 operating system process P1 interrupt or system call executing save state into PCB0 Context switch idle reload state from PCB1 idle interrupt or system call executing save state into PCB1 Context switch idle reload state from PCB0 executing 12 CONTEXT SWITCH ØWhen CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch ØContext of a process represented in the PCB ØContext-switch time is pure overhead; the system does no useful work while switching ­ The more complex the OS and the PCB è the longer the context switch ØTime dependent on hardware support ­ Some hardware provides multiple sets of registers per CPU è multiple contexts loaded at once 13 PROCESS CREATION ØSystem must provide mechanisms for: ­ Process creation ­ Process termination ØParent process create children processes, which, in turn create other processes, forming a tree of processes ØGenerally, process identified and managed via a process identifier (pid) ØResource sharing options ­ Parent and children share all resources ­ Children share subset of parent’s resources ­ Parent and child share no resources ØExecution options ­ Parent and children execute concurrently ­ Parent waits until children terminate 14 PROCESS CREATION (CONT.) ØAddress space ­ Child duplicate of parent ­ Child has a program loaded into it ØUNIX examples ­ fork() system call creates new process ­ Returns 0 in the child ­ Returns child’s pid in the parent ­ exec() system call used after a fork() to replace the process’ memory space with a new program ­ Parent process calls wait() waiting for the child to terminate 15 A TREE OF PROCESSES IN LINUX 16 C PROGRAM FORKING SEPARATE PROCESS = 0 pi d >0 pi d Child Parent 17 PROCESS TERMINATION ØProcess executes last statement and then asks the operating system to delete it using the exit() system call. ­ Returns status data from child to parent (via wait()) ­ Process’ resources are deallocated by operating system ØParent may terminate the execution of children processes using the abort() system call. Some reasons for doing so: ­ Child has exceeded allocated resources ­ Task assigned to child is no longer required ­ The parent is exiting, and the operating systems does not allow a child to continue if its parent terminates 18 PROCESS TERMINATION (CONT.) ØSome operating systems do not allow child to exists if its parent has terminated. If a process terminates, then all its children must also be terminated. ­ cascading termination. All children, grandchildren, etc., are terminated. ­ The termination is initiated by the operating system. ØThe parent process may wait for termination of a child process by using the wait() system call. The call returns status information and the pid of the terminated process ­ pid = wait(&status); ØIf no parent waiting (did not invoke wait()) process is a zombie ØIf parent terminated without invoking wait(), process is an orphan 19 INTERPROCESS COMMUNICATION ØProcesses within a system may be independent or cooperating ØCooperating process can affect or be affected by other processes, including sharing data ØReasons for cooperating processes: ­ Information sharing ­ Computation speedup ­ Modularity ­ Convenience ØCooperating processes need interprocess communication (IPC) ØTwo models of IPC ­ Shared memory ­ Message passing 20  Shared memory Message passing COMMUNICATIONS MODELS 21 IPC: SHARED MEMORY ØAn area of memory shared among the processes that wish to communicate ØThe communication is under the control of the users processes not the operating system. ØMajor issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory. ØSynchronization is discussed in great details in Lecture 6. 22 PRODUCER-CONSUMER PROBLEM ØParadigm for cooperating processes: ­ producer process produces information that is consumed by a consumer process ØTwo variations: ­ unbounded-buffer places no practical limit on the size of the buffer: ­ Producer never waits ­ Consumer waits if there is no buffer to consume Øbounded-buffer assumes that there is a fixed buffer size ­ Producer must wait if all buffers are full ­ Consumer waits if there is no buffer to consume 23 BOUNDED-BUFFER: SHARED-MEMORY SOLUTION ØShared data #define BUFFER_SIZE 10 typedef struct {... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; ØSolution is correct, but can only use BUFFER_SIZE-1 elements 24 item next_produced; Producer Process while (true) { while (((in + 1) % BUFFER_SIZE) == out) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } item next_consumed; Consumer Process while (true) { while (in == out) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } PRODUCER & CONSUMER PROCESSES: SHARED MEMORY 25 WHAT ABOUT FILLING ALL THE BUFFERS? ØSuppose that we wanted to provide a solution to the consumer-producer problem that fills all the buffers. ØWe can do so by having an integer counter that keeps track of the number of full buffers. ­ Initially, counter is set to 0. ­ The integer counter is incremented by the producer after it produces a new buffer. ­ The integer counter is decremented by the consumer after it consumes a buffer. 26  Producer Process while (true) { while (counter == BUFFER_SIZE) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } while (true) { Consumer Process while (counter == 0) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } PRODUCER & CONSUMER PROCESSES: SHARED MEMORY(USING COUNTER) 27 IPC: MESSAGE PASSING ØProcesses communicate with each other without resorting to shared variables ØIPC facility provides two operations: ­ send(message) ­ receive(message) ØThe message size is either fixed or variable ØIf processes P and Q wish to communicate, they need to: ­ Establish a communication link between them ­ Exchange messages via send/receive 28 ANDROID PROCESS HIERARCHY ØMobile operating systems often have to terminate processes to reclaim system resources such as memory. ØAndroid will begin terminating processes that are least important, i.e. empty processes, followed by background processes etc. ØProcesses types listed from most to least important: ­ Foreground process ­ Visible process ­ Service process ­ Background process ­ Empty process 29 MULTITASKING IN MOBILE SYSTEMS ØSome mobile systems (e.g., early version of iOS) allow only one process to run, others suspended ØStarting from iOS4 Apple provided a limited form of multitasking. ­ Single foreground process- controlled via user interface. Foreground- app that is currently opened and appears on display ­ Multiple background processes– in memory, running, but not on the display, and with limits ­ Limits include single, short task, receiving notification of events, specific long-running tasks like audio playback ­ Subsequent versions of iOS - support richer functionality for multitasking with fewer restrictions. E.g. the larger screen on iPad tablets with two foreground apps at the same time, a technique called split-screen. 30 MULTITASKING IN MOBILE SYSTEMS (CONT.) ØAndroid runs foreground and background, with fewer limits, since its origin ­ Background process uses a service to perform tasks ­ Service can keep running even if background process is suspended ­ Service has no user interface, small memory is being used 31