Equivalence of IPC primitives
CS 273 (OS), Fall 2019
Building monitors with semaphores
- Use a binary semaphore
mutex
initialized at 1 to insure mutual exclusion of each monitor object. - Use a semaphore initialized at 0 for each condition variable in a monitor.
- Implementation of
wait(c)
:up(mutex); down(c); down(mutex);
- Implementation of
signal(c)
:up(c);
- Is there a race?
Building message passing using monitors
- Create a monitor for holding and dispensing messages.
- Mailbox data structure: two integers counting full and empty slots, array of messages
- Procedures
send()
andreceive()
- Two condition variables S for sending and R for receiving
- Algorithm for
send()
:if (empty == 0) wait(S) add message at next empty slot empty-- full++ if (full == 1) signal(R)
- Algorithm for
receive()
:if (full == 0) wait(R) remove a message from mailbox empty++ full-- if (empty == 1) signal(S)
- Observe that these messages will need to be within a single computer.
Building semaphores from message passing
- Create a new process
sync
, the synchronization process, which holds an integer and a queue for each semaphore. One synchronization process could be used for all semaphores. - We will use blocking
receive
s and non-blockingsend
s. - Algorithm for
up(sem)
primitive:make_msg(&msg, UP, sem) send(sync, &msg) receive(sync, &msg)
- Algorithm for
down(sem)
primitive:make_msg(&msg, DOWN, sem) send(sync, &msg) receive(sync, &msg)
- Algorithm for synchronization process:
repeat forever { receive(any, &msg) decode(msg, &sender, &type, &sem) /* sem is semaphore */ if (type == DOWN) { if (sem.int == 0) add sender to sem.queue else { sem.int-- send(sender, ack_msg) } } else { /* type == UP */ if (sem.queue is non-empty) { remove one proc from sem.queue send(proc, ack_msg) } else sem.int++ send(sender, msg) } }