Operating System Concepts - Chapter 3 Processes PDF

Chapter 3: Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication Communication in Client-Server Systems Operating System Concepts – 9th Edition 3.70 Silberschatz, Galvin and Gagne ©...

Chapter 3: Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication Communication in Client-Server Systems Operating System Concepts – 9th Edition 3.70 Silberschatz, Galvin and Gagne ©2013 Interprocess Communication Processes within a system may be independent or cooperating  Independent processes do not depend on and affect other processes  Cooperating process can affect or be affected by other processes, including sharing data Reasons for cooperating processes:  Information sharing  Computation speedup by performing shared tasks and breaking a task into subtasks  Modularity for development and concurrent/parallel process execution  Convenience for user to work on many tasks in parallel (e.g. editing, printing, compiling,...) Operating System Concepts – 9th Edition 3.71 Silberschatz, Galvin and Gagne ©2013  Interprocess Communication Cooperating processes need interprocess communication (IPC) Two models of IPC  Shared memory  Message passing Operating System Concepts – 9th Edition 3.72 Silberschatz, Galvin and Gagne ©2013 Communications Models (a) Message passing (b) Shared memory processprocess A A processprocess A A processprocess B B shared memory shared memory processprocess B B messagemessage queue queue m0 m1 m20 m31 m...2 mn3... mn kernel kernel kernel kernel (a) (a) (b) (b) Operating System Concepts – 9th Edition 3.73 Silberschatz, Galvin and Gagne ©2013  Interprocess Communication Cooperating processes need interprocess communication (IPC) Two models of IPC  Shared memory 4 Communicating processes share an area in the memory (e.g. variable, object,...) 4 Processes can then exchange information by reading and writing data to the shared region process A process A process B shared memory process B message queue m0 m1 m2 m3... mn kernel kernel Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition (a) 3.74 (b) Interprocess Communication Shared Memory An area of memory shared among the processes that wish to communicate The communication is under the control of the processes not the operating system Shared memory requires that two or more processes agree to remove this restriction. They can then exchange information by reading and writing data in the shared areas. Major issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory and maintain the consistency of shared memory. Synchronization is discussed in great details in Chapter 5. Operating System Concepts – 9th Edition 3.75 Silberschatz, Galvin and Gagne ©2013  Interprocess Communication Cooperating processes need interprocess communication (IPC) Two models of IPC  Shared memory 4 Communicating processes share an area in the memory (e.g. variable, object,...) 4 Processes can then exchange information by reading and writing data to the shared region  Message passing 4 Communicating via message passing without the need for a shared memory 4 Communication takes place by means of messages exchanged between the cooperating processes Operating System Concepts – 9th Edition 3.76 Silberschatz, Galvin and Gagne ©2013 Interprocess Communication Message Passing Mechanism for processes to communicate and to synchronize their actions Message system – processes communicate with each other without the need of shared memory IPC facility provides two operations:  send(message)  receive(message) The message size is either fixed or variable Operating System Concepts – 9th Edition 3.77 Silberschatz, Galvin and Gagne ©2013  Interprocess Communication Message Passing Vs. Shared Memory Both models are common in operating systems, and many systems implement both Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided Message passing is also easier to implement in a distributed system than shared memory Shared memory can be faster than message passing  more time-consuming task of kernel intervention Operating System Concepts – 9th Edition 3.78 Silberschatz, Galvin and Gagne ©2013 Chapter 3: Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication  Shared Memory  Message Passing Communication in Client-Server Systems Operating System Concepts – 9th Edition 3.79 Silberschatz, Galvin and Gagne ©2013  Example (1) Shared memory between a parent and a child?! V not shared!! Operating System Concepts – 9th Edition 3.80 Silberschatz, Galvin and Gagne ©2013 Shared memory Memory Management The mmap() function can be used to map a region of memory that is larger than the current size of the object. It also maps files or devices into memory On success, the mmap() returns a pointer to the mapped area; for failure, the function returns MAP_FAILED A void pointer is a pointer that has no associated data type with it A void pointer can hold address of any type and can be typecasted to any type Operating System Concepts – 9th Edition 3.81 Silberschatz, Galvin and Gagne ©2013  Shared memory Memory Management 1. address: This argument gives a preferred starting address for the mapping. If another mapping does not exist there, then the kernel will pick a nearby page boundary and create the mapping; otherwise, the kernel picks a new address. If this argument is NULL, then the kernel can place the mapping anywhere it sees fit. 2. length: This is the number of bytes which to be mapped. 3. protect: This argument is used to control what kind of access is permitted. This argument may be logical ‘OR’ of the following flags PROT_READ | PROT_WRITE | PROT_EXEC | PROT_NONE. The access types of read, write and execute are the permissions on the content. Operating System Concepts – 9th Edition 3.82 Silberschatz, Galvin and Gagne ©2013 Shared memory 4. flags: This argument is used to control the nature of the map. Following are some common values of the flags: MAP_SHARED: This flag is used to share the mapping with all other processes, which are mapped to this object. Changes made to the mapping region will be written back to the file. MAP_PRIVATE: When this flag is used, the mapping will not be seen by any other processes, and the changes made will not be written to the file. MAP_ANONYMOUS / MAP_ANON: This flag is used to create an anonymous mapping. Anonymous mapping means the mapping is not connected to any files. This mapping is used as the basic primitive to extend the heap. MAP_FIXED: When this flag is used, the system has to be forced to use the exact mapping address specified in the address. If this is not possible, then the mapping will be failed. 5. filedes: This is the file descriptor which has to be mapped. 6. offset: This is offset from where the file mapping started. In simple terms, the mapping connects to (offset) to (offset+length-1) bytes for the file open on filedes descriptor. Operating System Concepts – 9th Edition 3.83 Silberschatz, Galvin and Gagne ©2013  Shared memory 4 è size of Be able to read and void pointer typecasted to int the memory write to the shared = sizeof(int) memory NULL è We don’t care about Make the the starting address of the memory shared memory and not backed The fd and up with any file offset arguments are ignored due to ANONYMOUS option Operating System Concepts – 9th Edition 3.84 Silberschatz, Galvin and Gagne ©2013 Shared Memory Syntax: int munmap(void *address, size_t length); Return values: On success, the munmap() returns 0; for failure, the function returns -1. The munmap() system call deletes the mappings for the specified address range (memory unmap) The region is also automatically unmapped when the process is terminated. Operating System Concepts – 9th Edition 3.85 Silberschatz, Galvin and Gagne ©2013  Example (1) Shared memory between a parent and a child V shared!! Operating System Concepts – 9th Edition 3.86 Silberschatz, Galvin and Gagne ©2013 Example (2) Write a program that creates a shared array of integers of size 5. Now you should do the following:  Create a function called “fill_array” that fills the array of integers (array[i]=i+1)  Create a function “print_array” that prints the array.  Create a child process using fork() system call. The child should change the value of the third element of the array, print the array and exit.  The parent should wait for the child to terminate, change the fourth element of the array and print it. Sample output Operating System Concepts – 9th Edition 3.87 Silberschatz, Galvin and Gagne ©2013  AZZAM MOURAD Example (2) SHARED MEMORY(C EXAMPLE) Create a shared array of integers of size 5. 23 23 (C EXAMPLE) (C EXAMPLE) AZZAM MOURAD Operating System Concepts – 9th Edition 3.88 Silberschatz, Galvin and Gagne ©2013 SHARED MEMORY(C EXAMPLE) Example (2) fill_array and print_array functions //OR C EXAMPLE) printf("%d ",array[i]); Operating System Concepts – 9th Edition 3.89 Silberschatz, Galvin and Gagne ©2013  23 C(CEXAMPLE) EXAMPLE) Example (2) (C EXAMPLE) 23 C EXAMPLE) Operating System Concepts – 9th Edition 3.90 Silberschatz, Galvin and Gagne ©2013 Example (2) Create a child process using fork() system call. The child should change the value of the third element of the array, print the array and exit. The parent should wait for the child to terminate, change the fourth element of the array and print it. Operating System Concepts – 9th Edition 3.91 Silberschatz, Galvin and Gagne ©2013  Producer-Consumer Problem Paradigm for cooperating processes: Producer-Consumer  producer process produces information that is consumed by a consumer process  For example, a compiler may produce assembly code that is consumed by an assembler. A buffer of items will reside in a shared region of memory and can be filled by the producer and emptied by the consumer Two types of buffers:  unbounded-buffer  bounded-buffer Operating System Concepts – 9th Edition 3.92 Silberschatz, Galvin and Gagne ©2013 Producer-Consumer Problem A buffer of items will reside in a shared region of memory and can be filled by the producer and emptied by the consumer Two types of buffers:  unbounded-buffer places no practical limit on the size of the buffer 4 The consumer may have to wait for new items, but the producer can always produce new items  bounded-buffer assumes that there is a fixed buffer size 4 The consumer must wait if the buffer is empty, and the producer must wait if the buffer is full Operating System Concepts – 9th Edition 3.93 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer out in First In First Out (FIFO) Consumer Producer Shared Buffer is implemented as a circular array Variable in points to the next free position in the buffer out Variable out points to the first full position in the buffer in Source: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html Operating System Concepts – 9th Edition 3.94 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 out=0 in= 0 Variable in points to the next free position in the buffer Variable out points to the first full position in the buffer Operating System Concepts – 9th Edition 3.95 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 out=0 in= 1 Variable in points to the next free position in the buffer Variable out points to the first full position in the buffer Adding 5,7,9,4 Operating System Concepts – 9th Edition 3.96 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 out=0 in= 4 Operating System Concepts – 9th Edition 3.97 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 4 1 7 9 4 out=1 in= 4 Operating System Concepts – 9th Edition 3.98 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 4 1 7 9 4 Adding 8 5 1 7 9 4 8 out=1 in= 5 Operating System Concepts – 9th Edition 3.99 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 4 1 7 9 4 Adding 8 5 1 7 9 4 8 Reading 7 5 2 9 4 8 out=2 in= 5 Operating System Concepts – 9th Edition 3.100 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer First In First Out (FIFO) in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 4 1 7 9 4 Adding 8 5 1 7 9 4 8 Reading 7 5 2 9 4 8 Reading 9 5 3 4 8 Operating System Concepts – 9th Edition 3.101 out=3 in=Silberschatz, 5 Galvin and Gagne ©2013  Bounded Buffer in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Reading 5 4 1 7 9 4 Adding 8 5 1 7 9 4 8 Reading 7 5 2 9 4 8 Reading 9 5 3 4 8 Reading 4 5 4 8 Buffer is empty Reading 8 5 5 out=5 in= 5 Operating System Concepts – 9th Edition 3.102 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer The buffer is empty when in==out e.g.: Add 5 elements è in=5 Remove 5 elements è out=5 è Buffer is empty out in Source: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html Operating System Concepts – 9th Edition 3.103 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Adding 2 5 0 5 7 9 4 2 Adding 8 6 0 5 7 9 4 2 8 Adding 3 7 0 5 7 9 4 2 8 3 Adding 6 ? 0 5 7 9 4 2 8 3 6 out=0 in= ? Operating System Concepts – 9th Edition 3.104 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Adding 2 5 0 5 7 9 4 2 Adding 8 6 0 5 7 9 4 2 8 Adding 3 7 0 5 7 9 4 2 8 3 Adding 6 ? 0 5 7 9 4 2 8 3 6 out=0 in= ? out updated in Consumer in updated in Producer out=(out +1)% BUFFER SIZE in=(in +1)% BUFFER SIZE Operating System Concepts – 9th Edition 3.105 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Adding 2 5 0 5 7 9 4 2 Adding 8 6 0 5 7 9 4 2 8 Adding 3 7 0 5 7 9 4 2 8 3 Adding 6 0 0 5 7 9 4 2 8 3 6 out=0 in=0 Operating System Concepts – 9th Edition 3.106 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer in out Array Initial 0 0 0 1 2 3 4 5 6 7 Adding 5 1 0 5 Adding 7 2 0 5 7 Adding 9 3 0 5 7 9 Adding 4 4 0 5 7 9 4 Adding 2 5 0 5 7 9 4 2 Adding 8 6 0 5 7 9 4 2 8 Adding 3 7 0 5 7 9 4 2 8 3 Adding 6 0 0 5 7 9 4 2 8 3 6 Reading 5 0 1 7 9 4 2 8 3 6 in=0 out=1 Operating System Concepts – 9th Edition 3.107 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer The buffer is full when ((in + 1) % BUFFER SIZE) == out BUFFER SIZE − 1 items in the buffer at the same time in out Source: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html Operating System Concepts – 9th Edition 3.108 Silberschatz, Galvin and Gagne ©2013 Bounded-Buffer – Shared-Memory Solution The following variables reside in a region of memory shared by the producer and consumer processes: #define BUFFER_SIZE 10. out. typedef struct {.... } item; BUFFER_SIZE item buffer[BUFFER_SIZE]; int in = 0; Shared in int out = 0; BUFFER SIZE − 1 items in the buffer at the same time Shared Buffer is implemented as a circular array  Variable in points to the next free position in the buffer  Variable out points to the first full position in the buffer  Buffer is empty when in==out  Buffer is full when ((in + 1) % BUFFER SIZE) == out Operating System Concepts – 9th Edition 3.109 Silberschatz, Galvin and Gagne ©2013  Bounded-Buffer – Producer item next produced; 3.4 Interprocess Communication 125 while (true) { while (((in + 1) % BUFFER SIZE) == out) ; Buffer is full buffer[in] = next produced; in = (in + 1) % BUFFER SIZE; } Figure 3.13 The producer process using shared memory. If the buffer is full è The producer should wait When an item is produced, store it in the buffer and update in also provides a useful metaphor for the client–server paradigm. We generally think of a server as a producer and a client as a consumer. For example, a web Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9 Edition th 3.110 server produces (that is, provides) HTML files and images, which are consumed (that is, read) by the client web browser requesting the resource. One solution to the producer–consumer problem uses shared memory. To allow producer Bounded and consumerBuffer processes–toConsumer run concurrently, we must have available a buffer of items that can be filled by the producer and emptied by the consumer. This buffer will reside in a region of memory that is shared by 126 Chapter the producer 3 Processes and consumer processes. A producer can produce one item while the consumer is consuming another item. The producer and consumer must item next consumed; be synchronized, so that the consumer does not try to consume an item that has not yet been produced. while (true) { Two types of buffers can be used. The unbounded buffer places no practical while (in == out) limit on the size of the buffer. The consumer may haveisto Buffer wait for new items, empty ; but the producer can always produce new items. The bounded buffer assumes a fixed buffer size.next In this case, the =consumer consumed must wait if the buffer is empty, buffer[out]; and the producer must out =wait if the (out buffer + 1) is full. % BUFFER SIZE; Let’s look more closely at how the bounded buffer illustrates interprocess communication using shared memory. reside in a region of memory } shared by the producer and consumer processes: Figure #define BUFFER process 3.14 The consumer SIZE 10using shared memory. If the buffer is empty è The consumer should wait When an item is consumed, it will be typedef retrieved from struct { the buffer and out will be updated local variable next produced...in which the new item to be produced is stored. The consumer process has a local variable next consumed in which the item }item; to be System Operating consumed Concepts – 9 is th stored. Edition 3.111 Silberschatz, Galvin and Gagne ©2013 This scheme allows item atbuffer[BUFFER most BUFFER SIZE − 1 items in the buffer at the SIZE];  AZZAM MOURAD AZZAM MOURAD PRODUCER-CONSUMER Example(SHARED (1) MEMORY) PRODUCER-CONSUMER //Shared Data (FIFO) PRODUCER-CONSUMER (SHARED MEMORY) #define BUFFER_SIZE 10 (SH First In First Out (FIFO) typedef struct {…} item; //Shared Data (FIFO) item buffer[BUFFER_SIZE]; //Shared Data (FIFO) #define BUFFER_SIZE 10 #defineint inBUFFER_SIZE = 0; 10 Shared typedef struct {…} item; typedefint out = 0;{…} item; struct item buffer[BUFFER_SIZE]; item buffer[BUFFER_SIZE]; int in = 0; int in = 0; int out = 0; int out// In = Parent 0; int// counter In Child = 0; item next_produced; int counter = 0; item next_consumed; while (true) { // Inwhile Parent (true) { // In // In Parent// produce an item // In Child item while (in == out) next_produced; item item next_produced; while (((in+1) % BUFFER_SIZE) == out) item next_consumed; while (true) ; //loop{ while doing nothing while while (true) { ; //loop while doing nothing while (true) { next_consumed // produce an item = buffer[out]; wh // produce an item buffer[in] = next_produced; while (counter while == out (counter 0) == = (out+1) % BUFFER_SIZE) BUFFER_ZIZE; whilein(counter = (in+1)== % BUFFER_SIZE) BUFFER_ZIZE; ; //loop while ;////loop consume doing the while nothing item nothing doing ne ; }//loop while doing nothing next_consumed } buffer[in] = buffer[out]; = next_produced; ou buffer[in] = next_produced; out = (out+1) in = (in+1)BUFFER_ZIZE; % % BUFFER_ZIZE; co in = (in+1) AZZAM %MOURAD BUFFER_ZIZE; counter - -; counter++; Silberschatz, Galvin and Gagne ©2013 // counter++; Operating System Concepts – 9 Edition 3.112 // consume the item th } } } } AZZAM MOURAD PRODUCER-CONSUMER AZZAM MOURAD Example (SHARED (2) MEMORY) //Shared Data (FIFO) PRODUCER-CONSUMER (SH #define BUFFER_SIZE 10 First In First Out (FIFO) PRODUCER-CONSUMER (SHARED MEMORY) typedef struct {…} item; //Shared Data (FIFO) item buffer[BUFFER_SIZE]; #define BUFFER_SIZE 10 //Shared Data (FIFO) int in = 0; typedef struct {…} item; #define BUFFER_SIZE 10 int out typedef = 0; struct {…} item; item buffer[BUFFER_SIZE]; int counter = 0; item buffer[BUFFER_SIZE]; int in = 0; int in = 0; int out = 0; // In int out = 0;Parent // In int Child = 0; counter int item counter next_produced; = 0; item next_consumed; while (true) { //while (true) { In Parent // In C // produce an item // In Parent // Initem Childwhile (counter == 0) next_produced; item n while (counter == BUFFER_SIZE) item next_produced; itemwhile ; //loop (true) next_consumed; { while doing nothing while while (true) ; //loop { while doing nothing //next_consumed while (true)produce { an item= buffer[out]; whi buffer[in] // produce = next_produced; an item while while out =(counter (counter(out+1) == 0) == BUFFER_SIZE) % BUFFER_ZIZE; ; whilein(counter = (in+1)== % BUFFER_ZIZE; BUFFER_SIZE) ; //loop counter ; //loop -while while-;doingdoing nothing nothing nex ; //loop while doing nothing counter++; buffer[in] next_consumed // consume = next_produced; =the buffer[out]; item out buffer[in] } = next_produced; out}in = (in+1)%%BUFFER_ZIZE; = (out+1) BUFFER_ZIZE; cou in = (in+1) % BUFFER_ZIZE; counter++; counter - -; // co Silberschatz, Galvin and Gagne ©2013 //}consume the item } Operating System Concepts – 9 Edition 3.113 counter++; th } }  AZZAM MOURAD PRODUCER-CONSUMER AZZAM MOURAD Example (SHARED (2) MEMORY) //Shared Data (FIFO) PRODUCER-CONSUMER (SH #define BUFFER_SIZE 10 First In First Out (FIFO) PRODUCER-CONSUMER (SHARED MEMORY) typedef struct {…} item; //Shared Data (FIFO) item buffer[BUFFER_SIZE]; #define BUFFER_SIZE 10 //Shared Data (FIFO) int in = 0; typedef struct {…} item; #define BUFFER_SIZE 10 int out = 0; typedef struct {…} item; item buffer[BUFFER_SIZE]; int counter = 0; Buffer is empty item buffer[BUFFER_SIZE]; Buffer is full int in = 0; int in = 0; int out = 0; // In int out = 0;Parent // In int Child = 0; counter int item counter next_produced; = 0; item next_consumed; while (true) { //while (true) { In Parent // In C // produce an item // In Parent // Initem Childwhile (counter == 0) next_produced; item n while (counter == BUFFER_SIZE) item next_produced; itemwhile ; //loop (true) next_consumed; { while doing nothing while while (true) ; //loop { while doing nothing //next_consumed while (true)produce { an item= buffer[out]; whi buffer[in] // produce = next_produced; an item while while out =(counter (counter(out+1) == 0)== BUFFER_SIZE) % BUFFER_ZIZE; ; whilein(counter = (in+1)== % BUFFER_ZIZE; BUFFER_SIZE) ; //loop counter ; //loop -while while-;doingdoing nothing nothing nex ; //loop while doing nothing counter++; buffer[in] next_consumed // consume = next_produced; =the buffer[out]; item out buffer[in] } = next_produced; out }in = = (in+1) (out+1) % % BUFFER_ZIZE; BUFFER_ZIZE; cou in = (in+1) % BUFFER_ZIZE; counter++; counter - -; // co Silberschatz, Galvin and Gagne ©2013 //}consume the item } Operating System Concepts – 9 Edition 3.114 counter++; th } } Bounded Buffer – Example (1) in out Array Counter Initial 0 0 0 1 2 3 4 0 Adding 5 1 0 5 1 Adding 7 2 0 5 7 2 Adding 9 3 0 5 7 9 3 Adding 4 4 0 5 7 9 4 4 Reading 5 4 1 7 9 4 3 Reading 7 4 2 9 4 2 Operating System Concepts – 9th Edition 3.115 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer – Example (2) in out Array Counter Initial 0 0 0 1 2 3 4 0 Adding 5 1 0 5 1 Adding 7 2 0 5 7 2 Adding 9 3 0 5 7 9 3 Adding 4 4 0 5 7 9 4 4 Adding 8 0 0 5 7 9 4 8 5 out=0 in=0 Operating System Concepts – 9th Edition 3.116 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer – Example (2) in out Array Counter Initial 0 0 0 1 2 3 4 0 Adding 5 1 0 5 1 Adding 7 2 0 5 7 2 Adding 9 3 0 5 7 9 3 Adding 4 4 0 5 7 9 4 4 Adding 8 0 0 5 7 9 4 8 5 Reading 5 0 1 7 9 4 8 4 in=0 out=1 Operating System Concepts – 9th Edition 3.117 Silberschatz, Galvin and Gagne ©2013  Bounded Buffer – Example (2) in out Array Counter Initial 0 0 0 1 2 3 4 0 Adding 5 1 0 5 1 Adding 7 2 0 5 7 2 Adding 9 3 0 5 7 9 3 Adding 4 4 0 5 7 9 4 4 Adding 8 0 0 5 7 9 4 8 5 Reading 5 0 1 7 9 4 8 4 Reading 7 0 2 9 4 8 3 in=0 out=2 Operating System Concepts – 9th Edition 3.118 Silberschatz, Galvin and Gagne ©2013 Bounded Buffer – Example (2) in out Array Counter Initial 0 0 0 1 2 3 4 0 Adding 5 1 0 5 1 Adding 7 2 0 5 7 2 Adding 9 3 0 5 7 9 3 Adding 4 4 0 5 7 9 4 4 Adding 8 0 0 5 7 9 4 8 5 Reading 5 0 1 7 9 4 8 4 Reading 7 0 2 9 4 8 3 Adding 3 1 2 3 9 4 8 4 in=1 out=2 Operating System Concepts – 9th Edition 3.119 Silberschatz, Galvin and Gagne ©2013  Example (1) Operating System Concepts – 9th Edition 3.120 Silberschatz, Galvin and Gagne ©2013 Example (1) Operating System Concepts – 9th Edition 3.121 Silberschatz, Galvin and Gagne ©2013  Example (1) Operating System Concepts – 9th Edition 3.122 Silberschatz, Galvin and Gagne ©2013 Chapter 3: Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication  Shared Memory  Message Passing Communication in Client-Server Systems Operating System Concepts – 9th Edition 3.123 Silberschatz, Galvin and Gagne ©2013  Interprocess Communication Message Passing Mechanism for processes to communicate and to synchronize their actions Message system – processes communicate with each other without the need of shared memory process A process A IPC facility provides two operations: process B shared memory  send(message) process B  receive(message) The message size is either fixed or variable message queue m0 m1 m2 m3... mn kernel kernel (a) (b) Operating System Concepts – 9th Edition 3.124 Silberschatz, Galvin and Gagne ©2013 Interprocess Communication Message Passing Vs. Shared Memory Both models are common in operating systems, and many systems implement both Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided Message passing is also easier to implement in a distributed system than shared memory Shared memory can be faster than message passing  more time-consuming task of kernel intervention Operating System Concepts – 9th Edition 3.125 Silberschatz, Galvin and Gagne ©2013  Message Passing If processes P and Q want to communicate  they must send messages to and receive messages from each other: a communication link must exist between them. Direct or Indirect Communication send (message) receive(message) Operating System Concepts – 9th Edition 3.126 Silberschatz, Galvin and Gagne ©2013 Direct Communication Processes must name each other explicitly:  must explicitly name the recipient or sender of the communication 4 send (P, message) – send a message to process P 4 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 – 9th Edition 3.127 Silberschatz, Galvin and Gagne ©2013  Communications A sends messages to B B sends message to A Bi-directional Process A Process B A sends messages to B Uni-directional Process A Process B Uni-directional B sends messages to A Operating System Concepts – 9th Edition 3.128 Silberschatz, Galvin and Gagne ©2013 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  A process can communicate with another process via different mailboxes 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 – 9th Edition 3.129 Silberschatz, Galvin and Gagne ©2013  Synchronization Message passing may be either blocking or non-blocking Blocking is considered synchronous Non-blocking is considered asynchronous Operating System Concepts – 9th Edition 3.130 Silberschatz, Galvin and Gagne ©2013 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 by the receiving process or by the mailbox Non-blocking is considered asynchronous  Non-blocking send -- the sender sends the message and resumes operation Process A Process B 1 … 1 … 2 send(..) 2 … 3 … 3 … 4 … 4 receive() 5 … 5 … 6 … 6 … Operating System Concepts – 9th Edition 3.131 Silberschatz, Galvin and Gagne ©2013  Synchronization Message passing may be either blocking or non-blocking Blocking is considered synchronous  Blocking receive -- the receiver is blocked until a message is available Non-blocking is considered asynchronous  Non-blocking receive -- the receiver receives a valid message, or a Null message Process A Process B 1 … 1 … 2 send(..) 2 … 3 … 3 … 4 … 4 receive() 5 … 5 … 6 … 6 … Operating System Concepts – 9th Edition 3.132 Silberschatz, Galvin and Gagne ©2013 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 by the receiving process or by the mailbox  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 resumes operation  Non-blocking receive -- the receiver receives a valid message, or a Null message Different combinations possible  If both send and receive are blocking, we have a rendezvous Operating System Concepts – 9th Edition 3.133 Silberschatz, Galvin and Gagne ©2013  Synchronization (message) Producer-consumer becomes trivial: The producer invokes the blocking send() call and waits until the message is delivered to either the receiver or the mailbox. Likewise, when the consumer invokes receive(), it blocks until a message is available message next_produced; while (true) { send(next_produced); } message next_consumed; while (true) { receive(next_consumed); } Operating System Concepts – 9th Edition 3.134 Silberschatz, Galvin and Gagne ©2013 Chapter 3: Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication  Shared Memory  Message Passing Communication in Client-Server Systems Operating System Concepts – 9th Edition 3.135 Silberschatz, Galvin and Gagne ©2013  Communications in Client-Server Systems How can processes communicate using shared memory and message passing ?  Pipes  Sockets Operating System Concepts – 9th Edition 3.136 Silberschatz, Galvin and Gagne ©2013 Pipes Acts as a conduit or a channel allowing two processes to communicate Issues:  Must there exist a relationship (i.e., parent-child) between the communicating processes?  Is communication unidirectional or bidirectional? parent-child?  Ordinary pipes – cannot be accessed from outside the process that created it – needs parent-child relationship  Named pipes – can be accessed without a parent-child relationship 3.6 Communication in Client – Server Systems 143 parent child fd(0) fd(1) fd(0) fd(1) pipe Figure 3.24 File descriptors for an ordinary pipe. Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – UNIX treats a pipe as a special type3.137 9th Edition of file. Thus, pipes can be accessed using ordinary read() and write() system calls. An ordinary pipe cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with  Pipes Ordinary pipes – cannot be accessed from outside the process that created it.  Parent-Child relationship is needed where typically a parent creates a pipe for communicating with its child process  Ordinary pipes are unidirectional (one-way communication) 4 If two-way communication is required, two pipes must be used, with each pipe sending data in a different direction.  Windows calls these anonymous pipes Named pipes – can be accessed without a parent-child relationship  Bidirectional communication between two different processes without the need for parent-child relationship  Several processes can use the named pipe for communication Operating System Concepts – 9th Edition 3.138 Silberschatz, Galvin and Gagne ©2013 Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) write() fd read() fd Operating System Concepts – 9th Edition 3.139 Silberschatz, Galvin and Gagne ©2013  Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) write() fd Producer Consumer Pipe read() fd Operating System Concepts – 9th Edition 3.140 Silberschatz, Galvin and Gagne ©2013 Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Producer Consumer write() fd Pipe read() fd write-end read-end file descriptor: Y file descriptor: X read-end X write-end 3.141 Y Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition  Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Producer Consumer write() fd Pipe read() fd write-end read-end file descriptor: Y file descriptor: X fd read-end X int fd; write-end 3.142 Y fd Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) int fd; pipe(fd); write() fd Parameters : fd will be the fd (file descriptor) for the read end of the pipe fd will be the fd for the write end of the pipe read() fd Returns: 0 on Success. -1 on error. Operating System Concepts – 9th Edition 3.143 Silberschatz, Galvin and Gagne ©2013  Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created 4 One process write to the pipe, and the other process reads from the pipe using the read() and write() system calls  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) int fd; pipe(fd); Parameters : fd will be the fd (file descriptor) for the read end of pipe. fd will be the fd for the write end of pipe. Returns: 0 on Success. -1 on error. Operating System Concepts – 9th Edition 3.144 Silberschatz, Galvin and Gagne ©2013 Ordinary Pipes Considering the standard Producer-Consumer problem  Unidirectional communication between a parent and a child only within the process where the pipe was created  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd)  Every process should close their unused ends of the pipe Process 1 Process 2 Write end Read end Write end Read end fd fd fd fd pipe 3.6 Communication in Client – Server Systems 143 parent child fd(0) fd(1) fd(0) fd(1) pipe Read end Write end Figure 3.24 File descriptors for an ordinary pipe. Operating System Concepts – 9th Edition 3.145 Silberschatz, Galvin and Gagne ©2013 UNIX treats a pipe as a special type of file. Thus, pipes can be accessed using ordinary read() and write() system calls. An ordinary pipe cannot be accessed from outside the process that created  Ordinary Pipes Producer: Child Consumer : Parent  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Both the parent process and the child process initially close their unused ends of the pipe Consumer Producer Parent Child Process 1 Process 2 Write end fd x Read end fd Write end fd Read end fd x pipe Operating System Concepts – 9th Edition 3.146 Silberschatz, Galvin and Gagne ©2013 Ordinary Pipes Producer: Child Consumer : Parent  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Both the parent process and the child process initially close their unused ends of the pipe Consumer Producer Parent Child close(fd); Process 1 Process 2 close(fd); Write end fd x Read end fd Write end fd Read end fd x pipe Operating System Concepts – 9th Edition 3.147 Silberschatz, Galvin and Gagne ©2013  Ordinary Pipes Producer: Child Consumer: Parent  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Both the parent process and the child process initially close their unused ends of the pipe 3.6 Communication in Client – Server Systems 143 Consumer Producer close(fd); close(fd); parent child x x fd(0) fd(1) fd(0) fd(1) pipe Read3.24 Figure end Write File descriptors for an ordinary pipe. end UNIX treats a pipe as a special type of file. Thus, pipes can be accessed using ordinary read() and write() system Operating System Concepts – 9th Edition 3.148 calls. Silberschatz, Galvin and Gagne ©2013 An ordinary pipe 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 creates via fork(). Recall from Section 3.3.1 that a child Ordinary Pipes process inherits open files from its parent. Since a pipe is a special type of file, the child inherits the pipe from its parent process. Figure 3.24 illustrates the relationship of the file descriptor fd to the parent and child processes. In the UNIX program shown in Figure 3.25, the parent process creates a Producer: pipe and then Parent sends a fork() call creating the child process. What occurs after the fork() Consumer: Childcall depends on how the data are to flow through the pipe. In this instance, the parent writes to the pipe, and the child reads from it. It is  Producer important writes to notice toboth that one the endparent (the write-end process andofthe thechild pipeprocess fd) initially close their unused  Consumer endsfrom reads of the thepipe. otherAlthough end (thethe programofshown read-end the pipe in Figure fd) 3.25 does not require this action, it is an important step to ensure that a process reading Both thefrom the pipe parent can detect process and theend-of-file (read()initially child process returnsclose 0) when theirtheunused writer has endsclosed itspipe of the end of the pipe. Ordinary pipes on Windows systems are termed anonymous pipes, and they behave similarly Producerto their UNIX counterparts: they are unidirectional and Consumer close(fd); Parent Child close(fd); #include Process 1 #include Process 2 x x #include Write end Read < #include unistd.hWrite end > end Read end fd fd fd fd #define BUFFER SIZE pipe25 #define READ END 0 #define WRITE END 1 int main(void) Operating System Concepts – 9th { Edition 3.149 Silberschatz, Galvin and Gagne ©2013 char write msg[BUFFER SIZE] = "Greetings"; char read msg[BUFFER SIZE];  Ordinary Pipes Producer: Parent Consumer: Child  Producer writes to one end (the write-end of the pipe fd)  Consumer reads from the other end (the read-end of the pipe fd) Both the parent process and the child process initially close their unused ends of the pipe 3.6 Communication in Client – Server Systems 143 parent Producer 3.6child Communication in Client – Server Systems Consumer 143 fd(0) fd(1) fd(0) fd(1) close(fd); close(fd); parent child fd(0) fd(1) fd(0) fd(1) x pipe Figure 3.24 File descriptors for an ordinary pipe. x UNIX treats a pipe as a special type of file. Thus, pipes can be accessed using ordinary read() and write() system calls. pipe An ordinary pipe 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 creates via fork(). Recall from Section 3.3.1 that a child 3.24 Figure 3.24 Read end process inherits open files from its parent. Since a pipe is a special type of file, the child inherits the pipe from its parent process. Figure Write end Filethedescriptors for an ordinary pipe. illustrates relationship of the file descriptor fd to the parent and child processes. In the UNIX program shown in Figure 3.25, the parent process creates a UNIX pipe and then sends a fork() calltreats a pipe creating the as aWhat child process. special type of file. Thus, pipes can be accessed using occurs after the fork() call depends on how the data are to flow through the pipe. In Operating this instance, ordinary System the parent Concepts writes to the–pipe, and theand read() 9 Edition th child reads from it. system write() It is3.150 calls. Silberschatz, Galvin and Gagne ©2013 An important to notice that both the ordinary parent pipe process and cannot the child be accessed from outside the process that created process initially close their unused ends of the pipe. Although the program shown in Figure it. Typically, a parent process creates a pipe and uses it to communicate with 3.25 does not require this action, it is an important step to ensure that a process reading from the pipe can detect end-of-file (read() returns 0) when the writer a child process that it creates via has closed its end of the pipe.. Recall from Section 3.3.1 that a child fork() process Ordinary pipes on Windows inherits systems open are termed files from anonymous its parent. Since a pipe is a special type of file, pipes, and they behave similarly to their UNIX counterparts: they are unidirectional and Example (1) the child inherits the pipe from its parent process. Figure 3.24 illustrates the #include relationship of the file descriptor fd to the parent and child processes. In the #include UNIX program shown in Figure 3.25, the parent process creates a #include #include pipe and> then sends a fork() call creating the child process. What occurs after 0) { 3.6 Communication in Client – Server Systems 143 close(fd[READ END]); parent child fd(0) fd(1) Figure 3.25 Ordinary pipe in UNIX. fd(0) fd(1) write(fd[WRITE END], write msg, strlen(write msg)+1); Parent writes a message to the child pipe close(fd[WRITE END]); } else { Figure 3.24 File descriptors for an ordinary pipe. Producer Consumer close(fd[WRITE END]); Parent Child UNIX treats a pipe as a special type of file. Thus, pipes can be accessed using ordinary read() and write() Process system 1 calls.