Operating System Concepts Chapter 3: Processes PDF

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

Chapter 3: Processes Operating System Concepts – 10 th 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 IPC Systems ▪ Communication in Client-Server Systems Operating System Concepts – 10 th 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 interprocess communication using shared memory and message passing. ▪ Design programs that uses pipes and POSIX shared memory to perform interprocess communication. ▪ Describe client-server communication using sockets and remote procedure calls. ▪ Design kernel modules that interact with the Linux operating system. Operating System Concepts – 10 th Edition 3.3 Silberschatz, Galvin and Gagne ©2018  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 Operating System Concepts – 10 th Edition 3.4 Silberschatz, Galvin and Gagne ©2018  Communications Models (a) Shared memory. (b) Message passing. Operating System Concepts – 10 th Edition 3.5 Silberschatz, Galvin and Gagne ©2018  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 Operating System Concepts – 10 th Edition 3.6 Silberschatz, Galvin and Gagne ©2018  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 Chapters 6 & 7. Operating System Concepts – 10 th Edition 3.7 Silberschatz, Galvin and Gagne ©2018  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 Operating System Concepts – 10 th Edition 3.8 Silberschatz, Galvin and Gagne ©2018  Producer Process – Shared Memory item next_produced; while (true) { while (((in + 1) % BUFFER_SIZE) == out) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } Operating System Concepts – 10 th Edition 3.9 Silberschatz, Galvin and Gagne ©2018  Consumer Process – Shared Memory item next_consumed; while (true) { while (in == out) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } Operating System Concepts – 10 th Edition 3.10 Silberschatz, Galvin and Gagne ©2018  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 and is decremented by the consumer after it consumes a buffer. Operating System Concepts – 10 th Edition 3.11 Silberschatz, Galvin and Gagne ©2018  Producer while (true) { while (counter == BUFFER_SIZE) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } Operating System Concepts – 10 th Edition 3.12 Silberschatz, Galvin and Gagne ©2018  Consumer while (true) { while (counter == 0) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } Operating System Concepts – 10 th Edition 3.13 Silberschatz, Galvin and Gagne ©2018  Race Condition ▪ counter++ could be implemented as register1 = counter register1 = register1 + 1 counter = register1 ▪ counter-- could be implemented as register2 = counter register2 = register2 - 1 counter = register2 ▪ Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4} Operating System Concepts – 10 th Edition 3.14 Silberschatz, Galvin and Gagne ©2018  Race Condition (Cont.) ▪ Question – why was there no race condition in the first solution (where at most N – 1) buffers can be filled? ▪ More in Chapter 6. Operating System Concepts – 10 th Edition 3.15 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 – 10 th Edition 3.16 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 – 10 th Edition 3.17 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 – 10 th Edition 3.18 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 – 10 th Edition 3.19 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 – 10 th Edition 3.20 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 – 10 th Edition 3.21 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 – 10 th Edition 3.22 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 ▪ Different combinations possible If both send and receive are blocking, we have a rendezvous Operating System Concepts – 10 th Edition 3.23 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 – 10 th Edition 3.24 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 – 10 th Edition 3.25 Silberschatz, Galvin and Gagne ©2018