______ Equivalence of IPC primitives (CS 273 (OS), Fall 2019)
Home
>>    




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() and receive()
    • 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 receives and non-blocking sends.
  • 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)
       }
    }