03-Higher-Level Synchronization

1 .3. Higher-Level Synchronization 3.1 Shared Memory Methods Monitors Protected Types 3.2 Distributed Synchronization/Comm. Message-Based Communication Procedure-Based Communication Distributed Mutual Exclusion 3.3 Other Classical Problems The Readers/Writers Problem The Dining Philosophers Problem The Elevator Algorithm Operating Systems 1

2 .Motivation Semaphores are powerful but low-level abstractions Programming with them is highly error prone Such programs are difficult to design, debug, and maintain Not usable in distributed memory systems Need higher-level primitives Based on semaphores or messages Operating Systems 2

3 .Monitors Follow the principles of abstract data types (object-oriented programming): A data object is manipulated only by a set of predefined operations A monitor consists of: A collection of data representing the state of the resource controlled by the monitor, and Procedures/functions to manipulate the data Operating Systems 3

4 .Monitors Implementation must guarantee: Resource is accessible by only monitor procedures Monitor procedures are mutually exclusive For coordination , monitor provides “condition variable” c not a conventional variable, has no value, only a name chosen by programmer Each c has a waiting queue associated c.wait Calling process is blocked and placed on queue c.signal Calling process wakes up waiting process (if any) Operating Systems 4

5 .Monitors Example: process p1 needs to wait until a variable X becomes positive before it can proceed p1 steps out to wait on queue associated with condition variable X _is_positive Operating Systems 5

6 .Monitors process p1 may reenter the monitor, however … Another process may execute X_is_positive.signal to wake up p1 when X becomes positive Operating Systems 6

7 .Monitors Design Issue: After c.signal , there are 2 ready processes : The calling process that did the c.signal The waiting process that the c.signal woke up Which should continue? (Only one can be executing inside the monitor!) Two different approaches Hoare monitors Mesa-style monitors Operating Systems 7

8 .Hoare Monitors Introduced by Tony Hoare in a 1974 http://wikipedia.org/wiki/C._A._R._Hoare First implemented by Per Brinch Hansen in Concurrent Pascal http://wikipedia.org/wiki/Per_Brinch_Hansen Approach taken by Hoare monitor: After c.signal , Awakened process continues Calling process is suspended , and placed on high-priority queue Operating Systems 8

9 .Hoare Monitors Effect of c. signal Operating Systems 9 urgent p 1 reenters Signaling process has the highest priority It r eenters as soon as p1 terminates

10 .Bounded buffer problem monitor BoundedBuffer { char buffer[n]; int nextin =0, nextout =0, fullCount =0; condition notempty , notfull ; deposit(char data) { if ( fullCount ==n) notfull.wait ; buffer[ nextin ] = data; nextin = (nextin+1) % n; fullCount = fullCount+1; notempty.signal ; } remove(char data) { if ( fullCount ==0) notempty.wait ; data = buffer[ nextout ]; nextout = (nextout+1) % n; fullCount = fullCount - 1; notfull.signal ; } } Operating Systems 10

11 .Priority waits Original Hoare monitor signal resumes longest waiting process (i.e., queue is a FIFO queue) May lead to unnecessary wake-ups Solution: Priority Waits Every wait operation specifies a priority p c.wait (p ) Waiting processes are kept sorted by p Smallest p = highest priority Reason: p frequently represents time Earlier events (smaller p) must be processed first c.signal wakes up highest-priority process (lowest p) Operating Systems 11

12 .Example: alarm clock A monitor ( AlarmClock ) maintains the current time value T ime is advanced by periodic calls by hardware A processes can go to sleep by calling AlarmClock.wakeMe (n ) monitor AlarmClock { int now=0; condition wakeup; tick() { /*invoked by hardware*/ now = now + 1; wakeup.signal ; } wakeMe ( int n ) { int alarm; alarm = now + n; while (now<alarm ) wakeup.wait (alarm ); wakeup.signal ; } } Operating Systems 12

13 .Example: alarm clock Why do we need the last wakeup.signal in wakeMe ? tick only wakes up one process If there are multiple processes with same alarm time , all must be awakened tick wakes up the first process the first process wakes up the second process, etc. Do we really need priority waits? Not for correctness but for efficiency: Without priority waits, all processes would need to wake up to check their alarm settings Operating Systems 13

14 .Mesa-style monitors After issuing c. signal , calling process continues executing Problem: Condition cannot be guaranteed after wakeup Assume that p 1 and p 2 are waiting for some condition c Caller could satisfying c and wake up both processes Assume p 1 starts and makes the condition false again When p 2 resumes, c is not guaranteed to be true Solution: process must retest c after wakeup instead of: if (!condition) c.wait use: while (!condition) c.wait This form of signal is sometimes called notify Operating Systems 14

15 .Monitors in Java Java supports synchronized methods, which permit Java objects to be used somewhat similarly to Mesa monitors Every object has an implicit lock, with a single associated condition If a method is declare synchronized, the object’s lock protects the entire method wait() causes a thread to wait until it is notified notifyAll () awakens all threads waiting on the object’s lock notify () awakens a single randomly chosen thread waiting on the object’s lock But there are differences… Operating Systems 15

16 .Differences between Java objects and monitors Monitors Resource is only accessible by monitor procedures Monitor procedures are mutually exclusive Java objects Fields are not required to be private Methods are not required to be synchronized Per Brinch Hansen: “It is astounding to me that Java’s insecure parallelism is taken seriously by the programming community, a quarter of a century after the invention of monitors and Concurrent Pascal. It has no merit.” [Java’s Insecure Parallelism, ACM SIGPLAN Notices 34: 38-45, April 1999]. Operating Systems 16

17 .Protected types Introduced in programming language Ada (1995) Equivalent to special case of monitor where c.wait is the first operation of a procedure c.signal is the last operation wait/signal are combined into a when( cond ) clause Procedure executes only when the condition is true when( cond ) guards access to the procedure (instead of: if (! cond ) c.wait ; ) When some other procedure makes cond true and terminates, it automatically enables the corresponding when clauses (instead of c.signal ) Operating Systems 17

18 .Example: Bounded Buffer deposit(char c) when ( fullCount < n) { buffer[ nextin ] = c; nextin = ( nextin + 1) % n; fullCount = fullCount + 1; } remove(char c) when ( fullCount > 0) { c = buffer[ nextout ]; nextout = ( nextout + 1) % n; fullCount = fullCount - 1; } Operating Systems 18

19 .Di str ibuted Synchronization Semaphore-based primitive requires shared memory For distributed memory: send( p,m ) Send message m to process p receive( q,m ) Receive message from process q in variable m Semantics of send and receive vary significantly in different systems : Does sender wait for message to be accepted? Does receiver wait if there is no message? Does sender name exactly one receiver? Does receiver name exactly one sender? Operating Systems 19

20 .Types of send/receive Operating Systems 20

21 .Channels, Ports, and Mailboxes Allow indirect communication Senders/Receivers name channel/port/mailbox instead of processes Senders/Receivers determined at runtime Sender does not need to know who receives the message Receiver does not need to know who sent the message Operating Systems 21

22 .Named Message Channels Named channel, ch1 , connects processes p1 and p2 p1 sends to p2 using send(ch1,”a”) p2 receives from p1 using: receive(ch1,x) Used in CSP/Occam: Communicating Sequential Processes in the Occam Programming Language (Hoare, 1978) Operating Systems 22

23 .Named Message Channels in CSP/Occam Receive statements may be implemented as guarded commands Syntax: when (c1) s1 s is enabled (able to be executed) only when c is true If more than one guarded command is enabled, one of them is selected for execution The condition c may contain receive statements, which evaluate to true if and only if the sending process is ready to send on the specified channel. Allow processes to receive messages selectively based on arbitrary conditions Operating Systems 23

24 .Example: Bounded buffer with CSP Producer P , Consumer C , and Buffer B are Communicating Sequential Processes Problem statement: When Buffer full: B can only send to C When Buffer empty: B can only receive from P When Buffer partially filled: B must know whether C or P is ready to act Solution: C sends request to B first; B then sends data Inputs to B from P and C are guarded with when clause Operating Systems 24

25 .Bounded Buffer with CSP Define 3 named channels deposit: P  B request: B  C remove: B  C P does: send(deposit, data); C does: send(request) receive(remove, data) Code for B on next slide Operating Systems 25

26 .Bounded buffer with CSP process BoundedBuffer { ... while (1) { when ((fullCount<n) && receive(deposit, buf[nextin])) { nextin = (nextin + 1) % n; fullCount = fullCount + 1; } or when ((fullCount>0) && receive(request)) { send(remove, buf[nextout]); nextout = (nextout + 1) % n; fullCount = fullCount - 1; } } Operating Systems 26

27 .Ports and Mailboxes Indirect communication (named message channels) allows a receiver to receive from multiple senders ( nondeterministically ) When channel is a queue, send can be nonblocking Such a queue is called mailbox or port , depending on number of receivers: A mailbox can have multiple receivers This can be expensive because receivers referring to the same mailbox may reside on different computers A port can have only one receiver So all messages addressed to the same port can be sent to one central place. Operating Systems 27

28 .Ports and Mailboxes Operating Systems 28 Figure 3-2

29 .UNIX implements of interprocess communication 2 mechanisms: pipes and sockets Pipes: Sender’s standard output is receiver’s standard input p1 | p2 | … | pn Sockets are named endpoints of a 2-way channel between 2 processes. Processes may be on different machines. To establish the channel: One process acts as a server, the other a client Server binds it socket to IP address of its machine and a port number Server issues an accept statement and blocks until client issues a corresponding connect statement The connect statement supplies the client’s IP address and port number to complete the connection. Operating Systems 29