Ch 3 Processes F24 PDF

Chapter 3: Processes Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline ▪ Process Concept ▪ Process Scheduling ▪ Operations on Processes ▪ Interprocess Communication...

Chapter 3: Processes Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline ▪ Process Concept ▪ Process Scheduling ▪ Operations on Processes ▪ Interprocess Communication ▪ IPC in Shared-Memory Systems ▪ IPC in Message-Passing Systems ▪ Examples of Process creation, IPC Systems Operating System Concepts – 10th Edition 3.2 Silberschatz, Galvin and Gagne ©2018  Objectives ▪ Identify the separate components of a process and illustrate how they are represented and scheduled in an operating system. ▪ Describe how processes are created and terminated in an operating system, including developing programs using the appropriate system calls that perform these operations. ▪ Describe and contrast inter-process communication using shared memory and message passing. ▪ Design programs that uses pipes to perform inter-process communication. Operating System Concepts – 10th Edition 3.3 Silberschatz, Galvin and Gagne ©2018  Process Concept ▪ An operating system executes a variety of programs that run as a process. A process is an instance of a running program, i.e., a program in execution process execution must progress in sequential fashion.  No parallel execution of instructions of a single process Needs certain resources – CPU time, Memory, I/O control, file storage space, etc. Process represents unit of work for systems Operating System Concepts – 10th Edition 3.4 Silberschatz, Galvin and Gagne ©2018  Program vs Process ▪ A program by itself is not a process Program is passive entity stored on disk (executable file); process is active Program becomes process when an executable file is loaded into memory  having a program counter (a register in CPU) specifying the next instruction to execute and a set of associated resources.  Execution of program starts either via GUI mouse clicks, command line entry of its name, etc. ▪ One program can be several processes Consider multiple users executing the same program Operating System Concepts – 10th Edition 3.5 Silberschatz, Galvin and Gagne ©2018  Memory Layout of Process ▪ The memory layout of a process is typically divided into multiple section The program code, also called text section Data section containing global variables Stack containing temporary data  Function parameters, return addresses, local variables Heap containing memory dynamically allocated during run time ▪ The sizes of the text and data sections are fixed, as their sizes do not change during program run time. ▪ However, the stack and heap sections can shrink and grow dynamically during program execution Operating System Concepts – 10th Edition 3.6 Silberschatz, Galvin and Gagne ©2018  Process in Memory Operating System Concepts – 10th Edition 3.7 Silberschatz, Galvin and Gagne ©2018  Memory Layout of a C Program Operating System Concepts – 10th Edition 3.8 Silberschatz, Galvin and Gagne ©2018  Multi Tasking ❑ Let, there be two processes P and Q ❑ Let, Running process P contains an instruction requiring an I/O operation, e.g., Multitasking O/S ❑ Input from Keyboard by human user ❑ Reading/Writing from/to Disk ❑ I/O operations is significantly slower than the speed of a CPU! ❑ Causes CPU to wait for Keyboard input ❑ Increases CPU Idle time Operating System Concepts – 10th Edition 3.9 Silberschatz, Galvin and Gagne ©2018  Multi Tasking ❑ How about an instruction from Q execute while P is waiting? ❑ This concept referred to as multitasking ❑ Multitasking allows for the concurrent execution of multiple processes ❑ As long as at least one job needs to execute, the CPU is never idle ❑ But only one process active at any time Operating System Concepts – 10th Edition 3.10 Silberschatz, Galvin and Gagne ©2018  Multi Tasking ❑ The objective is to reduce idle time of the processor by having some process running at all the times until there is one Why Multitasking? ❑ It maximizes CPU utilization ❑ The CPU moves around processes in such a fast pace, appearing that all the applications are running simultaneously Operating System Concepts – 10th Edition 3.11 Silberschatz, Galvin and Gagne ©2018  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 Operating System Concepts – 10th Edition 3.12 Silberschatz, Galvin and Gagne ©2018  Diagram of Process State Operating System Concepts – 10th Edition 3.13 Silberschatz, Galvin and Gagne ©2018  Process Execution States If processes are scheduled in a round robin manner, then when time quantum expires or an interrupts happen, the After finish execution, process When you run is returned a to ready queue exits program, a new process is created New Ready Running Exit Admit The new process is loaded into memory and placed in ready Waiting queue CPU scheduler takes a process from the head of a ready queue to execute When the wait for I/O is over there is a return to the When a running process needs an I/O operation to Ready state perform, it is placed in the Waiting State awaiting for I/O Operating System Concepts – 10th Edition 3.14 Silberschatz, Galvin and Gagne ©2018  Context Switching and PCB Context switching is a technique that allows CPU to switch between multiple processes for execution Context Switch The system must save the state of old process and load saved state for new process The necessary information associated with a process in O/S is represented by Process Control Block Operating System Concepts – 10th Edition 3.15 Silberschatz, Galvin and Gagne ©2018  Process Control Block (PCB) A process is represented by a Process Control Block (PCB) in Operating systems ▪ Process state – new, running, waiting, etc. ▪ Program counter – Holds the location of instruction to execute next ▪ CPU registers – contents of all process-centric registers such as Accumulators, stack pointer, general-purpose registers, etc. ▪ CPU scheduling information- priorities, scheduling queue pointers ▪ Memory-management information – memory allocated to the process ▪ Accounting information – CPU and real time used, clock time elapsed since start, time limits ▪ I/O status information – List of I/O devices allocated to process, list of open files, etc. Operating System Concepts – 10th Edition 3.16 Silberschatz, Galvin and Gagne ©2018  Process Representation in Linux Represented by the C structure task_struct pid t_pid; long state; unsigned int time_slice struct task_struct *parent; struct list_head children; struct files_struct *files; struct mm_struct *mm; Operating System Concepts – 10th Edition 3.17 Silberschatz, Galvin and Gagne ©2018  Threads ▪ 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 – Multithreaded word processor ▪ Must then have storage for thread details, multiple program counters in PCB Operating System Concepts – 10th Edition 3.18 Silberschatz, Galvin and Gagne ©2018  Threads ▪ So far, process performs a single thread of execution allows the process to perform only one task at a time In a word-processor program, users cannot simultaneously type in characters and run the spell checker ▪ Most modern OS have extended idea of the process concept of having multiple threads of execution Multiple locations can execute at once – having multiple threads of control -> threads This feature is beneficial on multicore systems, where multiple threads can run in parallel each in a separate processing core E.g., in a multithreaded word processor, one thread manages user input while another thread runs the spell checker Must then have storage for thread details, multiple program counters in PCB Operating System Concepts – 10th Edition 3.19 Silberschatz, Galvin and Gagne ©2018  Process Scheduling ▪ The number of processes currently in memory is known as the degree of multiprogramming. ▪ OS must balance between two goals: The goal of multiprogramming is to have some process running at all times to maximize CPU utilization Goal of timesharing - switch processes onto CPU core frequently to allow users to interact fast with each program  especially for interactive programs requiring quick response) Increasing the degree of multi-programming (i.e., more processes) lowers the degree of timesharing (i.e., waiting time increases) Operating System Concepts – 10th Edition 3.20 Silberschatz, Galvin and Gagne ©2018  Process Scheduling ▪ OS’s Balancing decision also consider behavior of the process  I/O Bound process: spends more time doing I/O than computation in CPU  CPU Bound process spends more time doing computation in CPU with infrequent I/O request ▪ In a multi-programmed system, if there are more processes than number of cores, excess processes will have to wait until a core becomes free andcan be rescheduled by a process scheduler process scheduler is OS program that selects among available processes for next execution on CPU core There are several CPU scheduling algorithms Operating System Concepts – 10th Edition 3.21 Silberschatz, Galvin and Gagne ©2018  Scheduling Queues ▪ A multi-programmed system also maintains scheduling queues of migrating processes Ready queue – set of all processes ready and waiting to execute in CPU Wait queues – set of processes waiting for a completion of an I/O event Queues are implemented as a linked list Operating System Concepts – 10th Edition 3.22 Silberschatz, Galvin and Gagne ©2018  Representation of Process Scheduling A new process is initially put in the ready At termination, a process is queue waiting to be selected for execution, or removed from all queues and dispatched to CPU core has its PCB and resources deallocated. While a process is executing in a CPU core, one of several events could occur Operating System Concepts – 10th Edition 3.23 Silberschatz, Galvin and Gagne ©2018  Context Switch ▪ When CPU switches from one process to another, the kernel must save the current context (state save) of the old process and load the saved context (state restore) for the new process scheduled to run via a context switch (another OS program) Context of a process represented in the PCB PCB includes the value of the CPU registers, the process state, and memory-management information Operating System Concepts – 10th Edition 3.24 Silberschatz, Galvin and Gagne ©2018  Context Switch A context switch occurs when the CPU switches from one process to another including OS processes Operating System Concepts – 10th Edition 3.25 Silberschatz, Galvin and Gagne ©2018  Context Switch - Overhead ▪ Context-switch time is a pure overhead as the system does no useful work but executes the kernel process while switching The more complex the OS and the PCB ➔ the longer the context switch time Time is dependent on hardware support (registers, instruction sets, etc.) Some hardware provides multiple sets of registers per CPU ➔ multiple contexts loaded at once Operating System Concepts – 10th Edition 3.26 Silberschatz, Galvin and Gagne ©2018  Operations on Processes ▪ System must provide mechanisms for: Process creation Process termination Operating System Concepts – 10th Edition 3.27 Silberschatz, Galvin and Gagne ©2018  Process Creation ▪ Parent process create children processes, which, in turn create other processes, forming a tree of processes ▪ A tree of process in Linux (see below) Operating System Concepts – 10th Edition 3.28 Silberschatz, Galvin and Gagne ©2018  Process identifier ▪ Generally, a process is uniquely identified and managed via a process identifier (pid) pid is usually an integer value ▪ Resource sharing options b/w parent and child 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 ▪ Two Address space options Child duplicate of parent (it has the same program and data as the parent). Child has a new program loaded into it Operating System Concepts – 10th Edition 3.29 Silberschatz, Galvin and Gagne ©2018  Process Creation ▪ 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 Parent process calls wait ( ) to make it to wait before for the child has terminated Operating System Concepts – 10th Edition 3.30 Silberschatz, Galvin and Gagne ©2018  Fork()System Call ▪ If fork ( ) succeeds it returns the child PID (greater than 0) to the parent Also, it returns 0 to the child ▪ If fork ( ) fails, it returns -1 to the parent (no child is created) ▪ pid_t data type represents process identifiers ▪ Other calls: ▪ getpid( ) – returns the PID of calling process ▪ getppid( ) – returns the PID of parent process Operating System Concepts – 10th Edition 3.31 Silberschatz, Galvin and Gagne ©2018  C Program Forking Separate Process #include #include #include #include int main(int argc, char *argv[]) { printf("hello world (my pid is:%d)\n", (int) getpid()); int rc = fork(); if (rc < 0) { // fork failed // another implementation: fprintf(stderr, "fork failed\n"); exit(1); printf("fork unsuccessful"); return 1; } else if (rc == 0) { // child (new process) printf("hello, I am child (pid:%d)\n", (int) getpid()); } else // same as (rc >0) { // parent goes down this path (main) printf("hello, I am the parent (pid:%d) of child %d\n", (int) getpid(), rc); } return 0; } Operating System Concepts – 10th Edition 3.32 Silberschatz, Galvin and Gagne ©2018  Wait() System call ▪ Sometimes, it is quite useful for a parent to wait for a child process to finish ▪ This task is accomplished with the wait() system call ▪ The parent process calls wait() to delay its execution until the child finishes executing. When the child is done, wait() returns to the parent. ▪ Adding a wait() could make an output deterministic. Operating System Concepts – 10th Edition 3.33 Silberschatz, Galvin and Gagne ©2018  C Program – Use of wait () #include #include #include #include int main(int argc, char *argv[]) { printf("hello world (my pid is:%d)\n", (int) getpid()); int rc = fork(); if (rc < 0) { // fork failed // another implementation: fprintf(stderr, "fork failed\n"); exit(1); printf("fork unsuccessful"); return 1; } else if (rc == 0) { // child (new process) printf("hello, I am child (pid:%d)\n", (int) getpid()); } else // same as (rc >0) { // parent goes down this path (main) wait (NULL); // Guarantee that the child will always finish first printf("hello, I am a parent (pid:%d) of the child %d\n", (int) getpid(), rc); } return 0; } Operating System Concepts – 10th Edition 3.34 Silberschatz, Galvin and Gagne ©2018  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())  The call returns status information and the pid of the terminated process pid = wait(&status); 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: Task assigned to child is no longer required Child has exceeded allocated resources The parent is exiting, and the operating systems does not allow a child to continue if its parent terminates Operating System Concepts – 10th Edition 3.35 Silberschatz, Galvin and Gagne ©2018  Process Termination ▪ 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 - a phenomenon known as cascading termination cascading termination. All children, grandchildren, etc., are terminated with parent’s termination Cascading termination is initiated by the operating system when a parent terminates ▪ The parent process may wait for termination of a child process by using the wait()system call (to avoid immature termination of child due to cascading)  The call returns status information and the pid of the terminated child process to the parent pid = wait(&status);  Wait () function can be called without any argument, such as wait (NULL); Operating System Concepts – 10th Edition 3.36 Silberschatz, Galvin and Gagne ©2018  Zombie and Orphan Process ▪ When a process terminates, its resources are deallocated by the operating system. However, its entry in the process table must remain there until the parent calls wait() since the process table contains the process’s exit status. ▪ A process that has terminated, but whose parent has not yet called wait(), is known as a zombie process. A zombie process has its entry in the process table but has already terminated Once the parent calls wait(), the process identifier of the zombie process and its entry in the process table are released. ▪ If a parent did not invoke wait() and instead terminated, thereby leaving its child processes as orphans. Operating System Concepts – 10th Edition 3.37 Silberschatz, Galvin and Gagne ©2018  Exec() System Call ▪ This system call is useful when you want to run a program that is different from the calling program ▪ This system call exec()takes the executable file name and list of arguments terminated by a NULL pointer. ▪ Given the name of an executable (e.g., wc) It loads code (and static data) from that executable and overwrites its current code segment in the address space The heap and stack and other parts of the memory space of the program are re-initialized Then the OS simply runs that program The control will not return back to where exec () was called ▪ Thus, it does not create a new process; rather, it transforms the currently running program into a different running program Note: For more information regarding execvp()and other variants can be found at https://linux.die.net/man/3/execvp Operating System Concepts – 10th Edition 3.38 Silberschatz, Galvin and Gagne ©2018  C Program – Use of exec() or execvp() #include #include #include #include #include int main(int argc, char *argv[]) { printf("hello world (pid:%d)\n", (int) getpid()); int rc = fork(); if (rc < 0) { // fork failed; exit fprintf(stderr, "fork failed\n"); exit(1); } else if (rc == 0) { // child (new process) printf("Hello, I am child (pid:%d)\n", (int) getpid()); printf ("I am replaced by the word count program and will be executing it now..\n"); printf ("(# Lines) (# Words) (# Bytes) (File Name)\n"); char *myargs; myargs = strdup("wc"); // program: "wc" (word count) myargs = strdup("process_exec.c"); // argument: file to count myargs = NULL; // marks end of array execvp(myargs, myargs); // runs word count printf("this shouldn’t print out"); } else // same as (rc>0) { // parent goes down this path (main) int rc_wait = wait(NULL); printf("\nHello, I am parent of %d (child PID as I get from wait:%d) (my pid:%d)\n", rc, rc_wait, (int) getpid()); } return 0; } Operating System Concepts – 10th Edition 3.39 Silberschatz, Galvin and Gagne ©2018  Inter-process Communication (IPC) ▪ 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) Operating System Concepts – 10th Edition 3.40 Silberschatz, Galvin and Gagne ©2018  Inter-process Communication (IPC) ❖ Processes require an inter-process communication (IPC) mechanism that will allow them to exchange data and information. ❖ There are two fundamental models of inter-process communication: 1. Shared memory: A shared memory is established where processes can then exchange information by reading and writing data to the shared region. 2. Message passing: Communication takes place by means of messages exchanged between the processes. Operating System Concepts – 10th Edition 3.41 Silberschatz, Galvin and Gagne ©2018  Communications Models (a) Shared memory. (b) Message passing. Operating System Concepts – 10th Edition 3.42 Silberschatz, Galvin and Gagne ©2018  Pipes ▪ Acts as a conduit allowing two processes to communicate ▪ Issues: Is communication unidirectional or bidirectional? In the case of two-way communication, is it half or full-duplex? Must there exist a relationship (i.e., parent-child) between the communicating processes? Can the pipes be used over a network? ▪ Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created. ▪ Named pipes – can be accessed without a parent-child relationship. Operating System Concepts – 10th Edition 3.43 Silberschatz, Galvin and Gagne ©2018  Ordinary Pipes ▪ Ordinary Pipes allow communication in standard producer-consumer style ▪ Producer writes to one end (the write-end of the pipe) ▪ Consumer reads from the other end (the read-end of the pipe) ▪ Ordinary pipes are therefore unidirectional ▪ Require parent-child relationship between communicating processes Operating System Concepts – 10th Edition 3.44 Silberschatz, Galvin and Gagne ©2018  Pipe () System Call  The pipe()system call can be used to provide the shared memory to allow communication between two processes  pipe()must be created before fork()  Single R/W operations by parent (P1) and child (P2)  Multiple R/W operations by parent and child P2/P1 MEMORY READ Port WRITE Port P1/P2  Write()function can be used to write to the write port of the pipe in C  Read()function can be used to read from the read port of the pipe in C Operating System Concepts – 10th Edition 3.45 Silberschatz, Galvin and Gagne ©2018  Creating a Pipe int port; int status; READ Port port status = pipe(port); C O N ❖ Returns 0 if ok, -1 on error T E N ❖ The array Port attached two file T descriptors, port and port port WRITE port port - open for reading port[1 ] - open for writing Operating System Concepts – 10th Edition 3.46 Silberschatz, Galvin and Gagne ©2018  Combination of fork()and pipe () ❑ A fork() copies the port info to the child whenever pipe is created before the fork() is called. It is expected! ❑ port of parent and child points to the same location in the pipe. ❑ port of parent and child points to the same location in the pipe. Operating System Concepts – 10th Edition 3.47 Silberschatz, Galvin and Gagne ©2018  C Program – Use of Pipe () - 1 #include #include #include #include #include #include int main(void){ int n; int port; pid_t pid; if (pipe(port) < 0) { printf("pipe error"); return 1;} pid = fork(); if (pid < 0) { printf("fork error"); return 2; } if(pid > 0) //parent { char message; int length; close(port); Operating System Concepts – 10th Edition 3.48 Silberschatz, Galvin and Gagne ©2018  C Program – Use of Pipe () - 2 printf("\n------Parent Process----- \nInsert your message and press Enter: "); fgets(message, 30, stdin); length = strlen(message); printf("\nParent: Sent message is %s Size of sent message is: %d", message, length); write(port,&length,sizeof(int)); write(port,message,length); printf("\nParent: Waiting for child to complete..\n"); close(port); wait(NULL); } else //child (pid ==0) { int length; char inbox; close (port); //printf("\nReading from the pipe now.."); read (port,&length,sizeof(int)); printf("\n\n--- Child Process ---\nThe received message has length of %d bytes", length); read (port,inbox, length); printf("\nChild: This is what I read: %s\n", inbox); close (port); return 0; } return 0; } Operating System Concepts – 10th Edition 3.49 Silberschatz, Galvin and Gagne ©2018  Open Questions 1. What will happen if you invoke the fork () multiple times? How many processes will be created, and how can we identify them. 2. If there are multiple pipes created, how can we handle them for each pair of communicating process? Operating System Concepts – 10th Edition 3.50 Silberschatz, Galvin and Gagne ©2018  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 Operating System Concepts – 10th Edition 3.51 Silberschatz, Galvin and Gagne ©2018  Message Passing (Cont.) ▪ If processes P and Q wish to communicate, they need to: Establish a communication link between them Exchange messages via send/receive ▪ Implementation issues: How are links established? Can a link be associated with more than two processes? How many links can there be between every pair of communicating processes? What is the capacity of a link? Is the size of a message that the link can accommodate fixed or variable? Is a link unidirectional or bi-directional? Operating System Concepts – 10th Edition 3.52 Silberschatz, Galvin and Gagne ©2018  Implementation of Communication Link ▪ Physical: Shared memory Hardware bus Network ▪ Logical: Direct or indirect Synchronous or asynchronous Automatic or explicit buffering Operating System Concepts – 10th Edition 3.53 Silberschatz, Galvin and Gagne ©2018  Direct Communication ▪ Processes must name each other explicitly: send (P, message) – send a message to process P receive(Q, message) – receive a message from process Q ▪ Properties of communication link Links are established automatically A link is associated with exactly one pair of communicating processes Between each pair there exists exactly one link The link may be unidirectional, but is usually bi-directional Operating System Concepts – 10th Edition 3.54 Silberschatz, Galvin and Gagne ©2018  Indirect Communication ▪ Messages are directed and received from mailboxes (also referred to as ports) Each mailbox has a unique id Processes can communicate only if they share a mailbox ▪ Properties of communication link Link established only if processes share a common mailbox A link may be associated with many processes Each pair of processes may share several communication links Link may be unidirectional or bi-directional Operating System Concepts – 10th Edition 3.55 Silberschatz, Galvin and Gagne ©2018  Indirect Communication (Cont.) ▪ Operations Create a new mailbox (port) Send and receive messages through mailbox Delete a mailbox ▪ Primitives are defined as: send(A, message) – send a message to mailbox A receive(A, message) – receive a message from mailbox A Operating System Concepts – 10th Edition 3.56 Silberschatz, Galvin and Gagne ©2018  Indirect Communication (Cont.) ▪ 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 two processes Allow only one process at a time to execute a receive operation Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was. Operating System Concepts – 10th Edition 3.57 Silberschatz, Galvin and Gagne ©2018  Synchronization Message passing may be either blocking or non-blocking ▪ Blocking is considered synchronous Blocking send -- the sender is blocked until the message is received Blocking receive -- the receiver is blocked until a message is available ▪ Non-blocking is considered asynchronous Non-blocking send -- the sender sends the message and continue Non-blocking receive -- the receiver receives:  A valid message, or  Null message Operating System Concepts – 10th Edition 3.58 Silberschatz, Galvin and Gagne ©2018  Producer-Consumer: Message Passing ▪ Producer message next_produced; while (true) { send(next_produced); } ▪ Consumer message next_consumed; while (true) { receive(next_consumed) } Operating System Concepts – 10th Edition 3.59 Silberschatz, Galvin and Gagne ©2018  Buffering ▪ Queue of messages attached to the link. ▪ Implemented in one of three ways 1. Zero capacity – no messages are queued on a link. Sender must wait for receiver (rendezvous) 2. Bounded capacity – finite length of n messages Sender must wait if link full 3. Unbounded capacity – infinite length Sender never waits Operating System Concepts – 10th Edition 3.60 Silberschatz, Galvin and Gagne ©2018  End of Chapter 3 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018