Interprocess Communication PDF

2.3 Inter process communication 9/1/2024 Bahir Dar University OS(ITec2022) 1  contents Inter process communication Processes communication Process synchronization 9/1/2024 Bahir Dar University OS(ITec2022) 2 ...

2.3 Inter process communication 9/1/2024 Bahir Dar University OS(ITec2022) 1  contents Inter process communication Processes communication Process synchronization 9/1/2024 Bahir Dar University OS(ITec2022) 2  Process communication 9/1/2024 Bahir Dar University OS(ITec2022) 3  process communication o The processes executing on multiprogramming can be independent or cooperating processes. o Independent process cannot affect or be affected by the execution of another process. o Cooperating process can affect or be affected by the execution of another process o A process need to cooperate should have a facility in which the are communicate and synchronize their action. o Advantages of process cooperation Information sharing Computation speed-up  Break into several subtasks and run in parallel Modularity  Constructing the system in modular fashion. Convenience  User will have many tasks to work in parallel (Editing, compiling, printing) 9/1/2024 Bahir Dar University OS(ITec2022) 4  Process communication(con’t….) o IPC facility provides a mechanism to allow processes to communicate and synchronize their actions. o Processes can communicate through shared memory or message passing. Both schemes may exist in OS. o The Shared-memory method requires communication processes to share some variables. o The responsibility for providing communication rests with the programmer. The OS only provides shared memory. Example: producer-consumer problem. 9/1/2024 Bahir Dar University OS(ITec2022) 5  Communication model Message Passing Shared Memory 9/1/2024 Bahir Dar University OS(ITec2022) 6  Process communication(con’t…) o Message system – processes communicate with each other without resorting to shared variables. o If P and Q want to communicate, a communication link exists between them. o OS provides this facility. o IPC facility provides two operations: send(message) – message size fixed or variable receive(message) o If P and Q wish to communicate, they need to: establish a communication link between them exchange messages via send/receive o Implementation of communication link physical (e.g., shared memory, hardware bus) logical (e.g., logical properties) 9/1/2024 Bahir Dar University OS(ITec2022) 7  Message passing systems oDirect or Indirect communication oSynchronous or asynchronous communication oAutomatic or explicit buffering 9/1/2024 Bahir Dar University OS(ITec2022) 8  Direct Communication o Processes must name each other explicitly: send (P, message) – send a message to process P receive(Q, message) – receive a message from process Q o 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. o This exhibits both symmetry and asymmetry in addressing Symmetry: Both the sender and the receiver processes must name the other to communicate. Asymmetry: Only sender names the recipient, the recipient is not required to name the sender.  The send and receive primitives are as follows.  Send (P, message)– send a message to process P.  Receive(id, message)– receive a message from any process. 9/1/2024 Bahir Dar University OS(ITec2022) 9 Disadvantages: Changing a name of the process creates problems.  Indirect Communication o The messages are sent and received from mailboxes (also referred to as ports). o A mailbox is an object Process can place messages Process can remove messages. o Two processes can communicate only if they have a shared mailbox. o Operations create a new mailbox send and receive messages through mailbox destroy a mailbox o Primitives are defined as:  send(A, message) – send a message to mailbox A  receive(A, message) – receive a message from mailbox A 9/1/2024 Bahir Dar University OS(ITec2022) 10  Indirect Communication(con’t…) Mailbox sharing P1, P2, and P3 share mailbox A. P1, sends; P2 and P3 receive. Who gets a message ? Properties of a link: A link is established if they have a shared mailbox A link may be associated with more than two boxes. Between a pair of processes they may be number of links A link may be either unidirectional or bi-directional. OS provides a facility To create a mailbox Send and receive messages through mailbox To destroy a mail box. The process that creates mailbox is a owner of that mailbox The ownership and send and receive privileges can be passed to other processes through system calls. 9/1/2024 Bahir Dar University OS(ITec2022) 11  Synchronous or asynchronous o Message passing may be either blocking or non-blocking. o Blocking is considered synchronous o Non-blocking is considered asynchronous o send and receive primitives may be either blocking or non- blocking.  Blocking send: The sending process is blocked until the message is received by the receiving process or by the mailbox.  Non-blocking send: The sending process sends the message and resumes operation.  Blocking receive: The receiver blocks until a message is available.  Non-blocking receive: The receiver receives either a valid message or a null. 9/1/2024 Bahir Dar University OS(ITec2022) 12  Automatic and explicit buffering  A link has some capacity that determines the number of messages that can reside in it temporarily.  Queue of messages is attached to the link; implemented in one of three ways. 1. Zero capacity – 0 messages, 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.  In non-zero capacity cases a process does not know whether a message has arrived after the send operation.  The sender must communicate explicitly with receiver to find out whether the later received the message.  Example: Suppose P sends a message to Q and executes only after the message has arrived.  Process P:  send (Q. message) : send message to process Q  receive(Q,message) : Receive message from process Q  Process Q  Receive(P,message)  Send(P,”ack”) 9/1/2024 Bahir Dar University OS(ITec2022) 13  Client-Server Communication Sockets Remote Procedure Calls Remote Method Invocation (Java) 9/1/2024 Bahir Dar University OS(ITec2022) 14  Sockets A socket is defined as an endpoint for communication. A pair of processes communicating over a network employees a pair of sockets– one for each process. Socket: Concatenation of IP address and port The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8 Servers implementing specific services listen to well-known ports telnet server listens to port 80 ftp server listens to port 21 http server listens to port 80. The ports less than 1024 are used for standard services. The port for socket is an arbitrary number greater than1024. Communication consists between a pair of sockets. 9/1/2024 Bahir Dar University OS(ITec2022) 15  Socket Communication 9/1/2024 Bahir Dar University OS(ITec2022) 16  Remote Procedure Calls Remote procedure call (RPC) abstracts procedure calls between processes on networked systems. Stubs – client-side proxy for the actual procedure on the server. The client-side stub locates the server and marshals the parameters. Marshalling: Parameters must be marshaled into a standard representation. The server-side stub receives this message, unpacks the marshaled parameters, and performs the procedure on the server. 9/1/2024 Bahir Dar University OS(ITec2022) 17 Execution of RPC 9/1/2024 Bahir Dar University OS(ITec2022) 18  Remote Method Invocation Remote Method Invocation (RMI) is a Java mechanism similar to RPCs. RMI allows a Java program on one machine to invoke a method on a remote object. 9/1/2024 Bahir Dar University OS(ITec2022) 19  Marshalling Parameters 9/1/2024 Bahir Dar University OS(ITec2022) 20  Process Synchronization 9/1/2024 Bahir Dar University OS(ITec2022) 21  Background Concurrent processes may have access to shared data and resources. If there is no controlled access to shared data, some processes will obtain an inconsistent view of the shared data. Consider two processes P1 and P2, accessing shared data. while P1 is updating data, it is preempted (because of timeout, for example) so that P2 can run. Then P2 try to read the data, which are partly modified. Results in data inconsistency In such cases, the outcome of the action performed by concurrent processes will then depend on the order in which their execution is interleaved. Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes Process Synchronization o mechanisms to ensure the orderly execution of cooperating processes that share a logical address space, so that data 9/1/2024 consistency is maintained Bahir Dar University OS(ITec2022) 22  Race condition  Race condition: The situation where several processes access and manipulate shared data concurrently and the final value of the shared data depends upon which process finishes last.  The key to preventing trouble here and in many other situations involving shared memory, shared files, and shared everything else is to find some way to prohibit more than one process from reading and writing the shared data at the same time.  To prevent race conditions, concurrent processes must coordinate or be synchronized. 9/1/2024 Bahir Dar University OS(ITec2022) 23  Race condition(cont…) Example: print spooler  When a process wants to print a file, it enters the fie name in a special spooler directory.  spooler directory has a very large number of slots, numbered 0, 1, 2,..., each one capable of holding a file name.  The printer daemon, periodically checks to se if there are any files to be printed, and if there are, it prints them and then removes their names from the directory.  There are also two shared variables, out, which points to the next file to be printed, and in, which points to the next free slot in the directory.  At a certain instant, slots 0 to 3 are empty (the files have already been printed) and slots 4 to 6 are full (with the names of files queued for printing).  More or less simultaneously, processes A and B decide they want to queue a fie for printing. 9/1/2024 Bahir Dar University OS(ITec2022) 24  Race condition(cont…)  Process A reads in and stores the value, 7, in a local variable called next_fre_slot.  The CPU decides that process A has run long enough, so it switches to process B.  Process B also reads in, and also gets a 7. It too stores it in its local variable next_fre_slot.  Process B now continues to run. It stores the name of its file in slot 7 and updates in to be an 8. Then it goes off and does other things.  Eventually, process A runs again, starting from the place it left off. It looks at next_free_slot, finds a 7 there, and writes its file name in slot 7, erasing the name that process B just put there.  Then it computes next_free_slot + 1, which is 8, and sets in to 8. The spooler directory is now internally consistent, so the printer daemon will not notice anything wrong, but process B will never receive any output.  Process B will hang around the printer room for years, wistfully hoping for output that never comes. 9/1/2024 Bahir Dar University OS(ITec2022) 25  Critical-Section  A critical section is a piece of code in which a process or thread accesses a common shared resource. The important features of the system is that – ensure that when one process is executing in its CS, no other process is allowed to execute in its CS. i.e no two processes are executed in their critical sections at the same time.  When a process executes code that manipulates shared data (or resource), we say that the process is in it’s Critical Section (for that shared data).  The execution of critical sections must be mutually exclusive: at any time, only one process is allowed to execute in its critical section (even with multiple processors). Bahir Dar University OS(ITec2022)  Critical section (con’t…) 9/1/2024 Bahir Dar University OS(ITec2022) 27  Critical section (con’t…) Critical section to prevent a race condition  Multiprogramming allows logical parallelism, uses devices efficiently but we lose correctness when there is a race condition.  So we forbid logical parallelism inside critical section so we lose some parallelism but we regain correctness. 9/1/2024 Bahir Dar University OS(ITec2022) 28  The Critical-Section Problem  process must first request permission to enter its critical section.  The section of code implementing this request is called the Entry Section (ES).  The critical section (CS) might be followed by a Leave/Exit Section (LS).  The remaining code is the Remainder Section (RS).  The critical section problem is to design a protocol that the processes can use so that their action will not depend on the order in which their execution is interleaved (possibly on many processors). General structure of process Pi (other process Pj) do { entry section critical section leave/exit section reminder section } while (1); Bahir Dar University OS(ITec2022)  Solution to Critical-Section Problem A solution to a critical –section problem must satisfy the following four requirements. 1. No two processes may be simultaneously inside their critical regions. 2. No assumptions may be made about speed or the number of CPUs. 3. No process running outside its critical region may block other processes. 4. No process should have to wait forever to enter its critical region. 9/1/2024 Bahir Dar University OS(ITec2022) 30  Mutual Exclusion with busy waiting 1. Disabling interrupts:- here each process will disable all interrupts just after entering its critical region and re-enable them just before leaving it.  With interrupts disabled, no clock interrupts can occur.  The CPU is only switched from process to process as a result of clock or other interrupts, after all, and with interrupts turned off the CPU will not be switched to another process.  Thus, once a process has disabled interrupts, it can examine and update the shared memory without fear that any other process will intervene. Process Pi: repeat disable interrupts critical section enable interrupts remainder section forever 9/1/2024 Bahir Dar University OS(ITec2022) 31  Mutual Exclusion with busy waiting(cont…)  Drawbacks of Disabling Interrupts: 1. If the user process did not turned off the interrupts, this could be the end of the system. 2. If the system is a multiprocessor, with two or more CPUs, disabling interrupts affects only the CPU that executed the disable instruction.  The other ones will continue running and can access the shared memory. That is, critical section is now atomic but not mutually exclusive (interrupts are not disabled on other processors).  In general, disabling interrupts is often a useful technique within the operating system itself but is not appropriate as a general mutual exclusion mechanism for user processes 9/1/2024 Bahir Dar University OS(ITec2022) 32  Mutual Exclusion with busy waiting(cont…) 2. Lock Variables:- is a software solution which uses a single, shared (lock)variable, initially 0.  When a process wants to enter its critical region, it first tests the lock.  If the lock is 0, the process sets it to 1 and enters the critical region.  If the lock is already 1, the process just waits until it becomes 0. Thus, a 0 means that no process is in its critical region, and a 1 means that some process is in its critical region.  Unfortunately, this idea contains exactly the same fatal flaw that we saw in the spooler directory. Suppose that one process reads the lock and sees that it is 0. Before it can set the lock to 1, another process is scheduled, runs, and sets the lock to 1. When the first process runs again, it will also set the lock to 1, and two processes will be in their critical regions at the same time. 9/1/2024 Bahir Dar University OS(ITec2022) 33  Mutual Exclusion with busy waiting(cont…) Lock variable do { acquire lock critical section release lock remainder section } while (TRUE); 9/1/2024 Bahir Dar University OS(ITec2022) 34  Mutual Exclusion with busy waiting(cont… ) 3. Strict Alternation:-the integer variable turn, initially 0, keeps track of whose turn it is to enter the critical region and examine or update the shared memory.  Initially, process 0 inspects turn, finds it to be 0, and enters its critical region.  Process 1 also finds it to be 0 and therefore sits in a tight loop continually testing turn to see when it becomes 1.  Continuously testing a variable until some value appears is called busy waiting.  It should usually be avoided, since it wastes CPU time. Only when there is a reasonable expectation that the wait will be short is busy waiting used.  A lock that uses busy waiting is called a spin lock. 9/1/2024 Bahir Dar University OS(ITec2022) 35  Mutual Exclusion with busy waiting(cont…)  When process 0 leaves the critical region, it sets turn to 1, to allow process 1 to enter its critical region.  Suppose that process 1 finishes its critical region quickly, so both processes are in their noncritical regions, with turn set to 0. Now process 0 executes its whole loop quickly, exiting its critical region and setting turn to 1. At this point turn is 1 and both processes are executing in their noncritical regions.  Suddenly, process 0 finishes its noncritical region and goes back to the top of its loop. Unfortunately, it is not permitted to enter its critical region now, because turn is 1 and process 1 is busy with its noncritical region. It hangs in its while loop until process 1 sets turn to 0.  So while this algorithm does avoid all races, it is not really a serious candidate as a solution because it violates condition 3. while (TRUE) { while (TRUE){ while(turn != 1) while(turn != 0) critical_region(); critical_region(); turn = 1; turn = 0; noncritical_region(); noncritical_region(); } } 9/1/2024 Bahir Dar University OS(ITec2022) 36  Peterson’s Solution It is two process solution #define FALSE 0 it consists of two procedures written in #define TRUE 1 ANSI C. #define N 2 Each process calls enter_region with its int turn; own process number, 0 or 1, as int interested[N parameter to access shared data. void enter_ region(int process); the process calls leave_region to { indicate that it is completed accessing int other shared data and to allow the other process to enter, if it so desires. other = 1 - process; interested[process] = TRUE; The two processes share two variables: turn = other; int turn; while (turn==process && Boolean flag interested[other]==TRUE; The variable turn indicates whose turn it } is to enter the critical section. Void leave_region(int process The flag array is used to indicate if a { process is ready to enter the critical interested[process]= FALSE; section. flag[i] = true implies that 9/1/2024 process Pi is ready! Bahir Dar University OS(ITec2022) 37  Semaphore o Semaphore is special variable which is used for signaling. o Two and more processes can cooperate by means of simple signals, such that a process is forced to stop at a specified place until it has received a specific signal. o If a process is waiting for a signal, it is suspended until that signal is sent o Semaphore has an integer value that may be initialized to a nonnegative number o Two standard operations are used on semaphore: wait() and signal() o The wait operation on a semaphore checks to see if the value is greater than 0. If so, it decrements the value and just continues. If the value is 0, the process is block without completing the wait operation for the moment. o The signal operation increments the value of the semaphore addressed. If one or more processes were sleeping on that semaphore, unable to complete an earlier wait operation, one of them is chosen by the system (e.g., at random) and is allowed to complete its wait. o Wait and signal operations indivisible atomic action which means the operation cannot be interrupted o Queue is used to hold processes waiting on the semaphore 9/1/2024 Bahir Dar University OS(ITec2022) 38  Semaphore(con’t…) o Semaphore can be : Counting semaphore – integer value can range over an unrestricted domain Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement. Also known as mutex locks  Binary semaphore used to provides mutual exclusion o Must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time. o Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section. 9/1/2024 Bahir Dar University OS(ITec2022) 39  Problems with Semaphores o Semaphores provide a powerful tool for enforcing mutual exclusion and coordinate processes. o But wait(S) and signal(S) are scattered among several processes. Hence, difficult to understand their effects. o Usage must be correct in all the processes (correct order, correct variables, no omissions). o One bad (or malicious) process can fail the entire collection of processes. 9/1/2024 Bahir Dar University OS(ITec2022) 40  Monitors Monitors are a programming language construct, that provides a convenient and effective mechanism for process synchronization A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but they cannot directly access the monitor's internal data structures from procedures declared outside the monitor. A procedures inside a monitor should be a critical section part of a processes. Only one process may be active within the monitor at a time monitor monitor-name {// shared variable declarations procedure P1 (…) { …. } … procedure Pn (…) {……} Initialization code ( ….) { … } } } 9/1/2024 Bahir Dar University OS(ITec2022) 41  Schematic view of a Monitor 9/1/2024 Bahir Dar University OS(ITec2022) 42  Condition Variables o Monitor defined so far not sufficiently powerful for modeling some synchronization scheme. o Conditional constructs mechanism is used to provide such synchronization. o Conditional variable is defined like:condition x, y; o The operations that invoked on condition variable are: o x.wait () – a process that invokes the operation is suspended. o x.signal () – resumes one of processes (if any) that invoked x.wait () 9/1/2024 Bahir Dar University OS(ITec2022) 43  Monitor with Condition Variables 9/1/2024 Bahir Dar University OS(ITec2022) 44  Classical Problems of Synchronization Producer and consumer problem Readers and Writers Problem Dining-Philosophers Problem 9/1/2024 Bahir Dar University OS(ITec2022) 45  Producer and consumer problem  Two processes share a common, fixed-size buffer. One of them, the producer, puts information into the buffer, and the other one, the consumer, takes it out.  We need a buffer to hold items that are produced and later consumed:  unbounded-buffer:- places no practical limit on the size of the buffer. Producer can produce any number of items. Consumer may have to wait  bounded-buffer:- assumes that there is a fixed buffer size.  Trouble arises when the producer wants to put a new item in the buffer, but it is already full.  The solution is for the producer to go to sleep, to be awakened when the consumer has removed one or more items.  Similarly, if the consumer wants to remove an item from the buffer but, the buffer is empty,  The solution is the consumer goes to sleep until the producer puts something in the buffer and wakes it up. 9/1/2024 Bahir Dar University OS(ITec2022) 46  Producer and consumer problem(con’t…) Producer and consumer problem using semaphore #define N 100 semaphoremutex = 1 ; semaphore empty = N; semaphore full = 0; void producer(void) {int item; while (TRUE) { item = produce_item( ); down(&empty); down(&mutex); inserUtem(item); up(&mutex); up(&full); } } 9/1/2024 Bahir Dar University OS(ITec2022) 47  Producer and consumer problem(con’t…) Producer and consumer problem using semaphore void consumer(void) { int item; while (TRUE) { down(&full); down(&mutex); item = remove_ item( ); up(&mutex); up(&empty); consume_item(item); } } 9/1/2024 Bahir Dar University OS(ITec2022) 48  Producer and consumer problem(con’t…) Producer and consumer problem using monitor 9/1/2024 Bahir Dar University OS(ITec2022) 49  Producer and consumer problem(con’t…) Producer and consumer problem using monitor procedure producer; Begin while true do Begin item = produce_item; ProducerConsumer. insert( item); end; end; item = ProducerConsumer.remove; consume _item( item) procedure consumer; Begin while true do Begin item = ProducerConsumer.remove; consume _item( item) end; end; 9/1/2024 Bahir Dar University OS(ITec2022) 50  Readers and writers problem o There is a data area shared among a number of processes. o The data area could be a file, a block of main memory, or even a bank of processor registers. o There are a number of processes that only read the data area (readers) and a number that only write to the data area (writers). The conditions that must be satisfied are as follows: 1. Any number of readers may simultaneously read the file. 2. Only one writer at a time may write to the file. 3. If a writer is writing to the file, no reader may read it. The readers and writers problem have several variation. First reader-writer problem: No reader will be kept waiting unless writer has a permission to access the shared object. Second readers -writers problem: Once reader ready, that writer perform its write a soon as possible. o in next slide the solution for the first readers –writers problem is 9/1/2024 presented. Bahir Dar University OS(ITec2022) 51  Readers and writers problem Readers and consumers problem using semaphore Writers code int readcount=0; /* number of readers concurrently use shared object void writer() semaphore mutex= 1; /* provide mutual exclusion for readcount { Semaphore wrt= 1; /* provide mutual exclusion for readers while (true){ void reader() Wait (wrt); { while (true){ WRITEUNIT(); Wait(mutex); Signal (wrt); readcount++; } if(readcount == 1) } wait(wrt); signal (mutex); READUNIT(); wait (mutex); Readcount--; if(readcount == 0) Readers code signal (wrt); signal (mutex); } } 9/1/2024 Bahir Dar University OS(ITec2022) 52  End Assignment: 1. Write semaphore and monitor based solution for second readers- writers problem(writer priority) 2. Write semaphore and monitor based solution for Dining philosopher problem.  Deadline for assignment submission: 26/04/2016  Assignment is done with in three group. 9/1/2024 Bahir Dar University OS(ITec2022) 53