1Lecture 5IPC: Interprocess CommunicationOctober 9, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 7• Semaphores• Monitors• Message-PassingProgramming Assignment #1 (see CSE120 web page)• Due in October 19• Contact a TA if you need an account• Start early!3Cooperating ProcessesWhy structure a computation as cooperative processes?Performance: speed• Exploit inherent parallelism of computation• Allow some parts to proceed why others do I/OModularity: reusable self-contained programs• Each may do a useful task on its own• May also be useful as a sub-task for others4Examples of Cooperating ProcessesPipelineClient/ServerParent/ChildP1P2P3CSPC1C2C35Interprocess CommunicationIn order to cooperate, need to be able to communicateAchieved via IPC: interprocess communication• ability for a process to communicate with anotherInterprocess communication requires•information transfer•synchronizationNeed mechanisms for each6The Producer/Consumer ProblemProducer process produces dataConsumer process consumes dataCooperation: data from Producer is fed to Consumer• How does data get from Producer to Consumer?• How does Consumer wait for Producer?Producer Consumer7Producer/Consumer: Shared MemoryProblems• No synchronization (only shared memory)• No mutual exclusion for critical sectionsProducerint nextin = 0;while (TRUE) { buffer[nextin%N] = produce (); nextin++;}Consumerint nextout = 0;while (TRUE) { consume (buffer[nextout%N]); nextout++;}shared int buffer[N]; /* shared memory */8Add Semaphore for Mutual ExclusionProblem: still no synchronizationProducerint nextin = 0;while (TRUE) { Wait (mutex); buffer[nextin%N] = produce (); Signal (mutex); nextin++;}Consumerint nextout = 0;while (TRUE) { Wait (mutex); consume (buffer[nextout%N]); Signal (mutex); nextout++;}shared int buffer[N];shared sem mutex = 1;9Add Semaphores for SynchronizationWorks, but not easy to understand: easily leads to bugsProducerint nextin = 0;while (TRUE) { Wait (emptyslots); Wait (mutex); buffer[nextin%N] = produce (); Signal (mutex); Signal (fullslots); nextin++;}Consumerint nextout = 0;while (TRUE) { Wait (fullslots); Wait (mutex); consume (buffer[nextout%N]); Signal (mutex); Signal (emptyslots); nextout++;}shared int buffer[N];shared sem mutex = 1, fullslots = 0, emptyslots = N;10MonitorsProgramming language construct for IPC• Variables requiring controlled access (shared mem)• Accessed via procedures (mutual exclusion)• Condition variables (synchronization)– Wait (cond), Signal (cond)Only one process can be active inside the monitor• “active” means running or able to run• others must wait11Analogy for MonitorsGate enforces mutual exclusion:allows only one processat a time inside monitorWait(cond) causes callingprocess to enter waiting areaSignal (cond) causes a waitingprocess to re-enter active areaACTIVEAREAWAITINGAREAOnly one activeprocess allowed12Producer/Consumer Using a MonitorProducerwhile (TRUE) { PutItem (produce ());}Consumerwhile (TRUE) { consume (GetItem ());}monitor ProducerConsumer { condition slotavail, itemavail; int count = 0, nextin = 0, nextout = 0, buffer[N];}PutItem (item) int item; { if (count == N) Wait (slotavail); buffer[nextin%N] = item; nextin++; count++; if (count == 1) Signal (itemavail); }GetItem (item) int item; { if (count == 0) Wait (itemavail); item = buffer[nextout%N]; nextout++ count--; if (count == N-1) Signal (slotavail); return (item); }13Issues with MonitorsGiven P1 waiting on condition c, and P2 signals c• now, P1 and P2 able to run (breaks mutual exclusion)• one solution: signal statements must be at end ofmonitor proceduresCondition variables have no memory• a signal without someone waiting does nothing• signal is “lost” (no memory, no future effect)Monitors bring structure to IPC• localizes critical sections and synchronization14Message PassingOperating system mechanism for IPC• Send (destination, message)• Receive (source, message)Data transfer: into and out of kernel message buffersSynchronization: can’t receive until message is sentsend (to, &msg) receive (from, &msg)kernelP1P215Producer/Consumer: Message-PassingProducerint item;message msg;while (TRUE) { item = produce (); insert (&msg, item); Send (Consumer, &msg);}Consumerint item;message msg;while (TRUE) { Receive (Producer, &msg); item = extract (&msg); consume (item);}/* NO SHARED MEMORY */16With Flow ControlProducerint item;message msg, empty;while (TRUE) { Receive (Consumer, &empty); item = produce (); insert (&msg, item); Send (Consumer, &msg);}Consumerint item;message msg, empty;do N times { Send (Producer, &empty);}while (TRUE) { Receive (Producer, &msg); item = extract (&msg); consume (item); Send (Producer, &empty);}17An OptimizationProducerint item;message msg;while (TRUE) { item = produce (); Receive (Consumer, &msg); insert (&msg, item); Send (Consumer, &msg);}Consumerint item;message msg;do N times { Send (Producer, &msg);}while (TRUE) { Receive (Producer, &msg); item = extract (&msg); Send (Producer, &msg); consume (item);}18Issues with Message PassingWho should messages be addressed to?• processes or ports (mailboxes)What if a process wants to receive from anyone?• pid = receive (*, msg)Synchronous (blocking) vs. asynchronous (non-blocking)• typically, send is non-blocking, receive is blockingKernel buffering: how many sends without receives?Good paradigm for IPC over networks (no shared
View Full Document