• Object: Simulate Token ring with processes and pipes. (4.6)
  • Create a directory named ``pup4'' under your home directory.
    This directory must contain
    • Makefile
    • README
    • other files..
  • When type ``make'' in your exercise directory, an executable named ring is created.
  • The file ``README'' contains your description of your exercise.
  • Due day, 4/16 00:01am
  • Since the description of token-ring in textbook is too concise to complete the exercise, I have written the following more precise description.
    • Each Host or IMP has an id which is just his pid.
    • Each IMP process, after forking his HOST process, must collect all the ids of IMP and HOSTS. You will need to find the corresponding IMP id for a HOST id and vice versa.
    • A HOST process will read from his IMP and a FIFO. The name of the FIFO is left to your choice. But eash HOST process should print his id and the name of FIFO to stderr so you know how to commmit command. Each command is consisted of two integers. First is the target host id, second is the msg to the host.
    • If possible, design a method to terminate the program gracefully such that all resources, processes and fifos, are removed.
    • If host h1 wants to send a meg to h2, five messages are generated in the order, P1, P2, P3, P4, and P5. The diagram below also shows the contents of individual fields. Beware of P4 is similar to P2 but with only status changed. Fields denoted '---' mean don't care. 
          h1  HOST                               HOST h2
         |                                   ^
         | P1                             P3 |        P1:  h1 -> i1
         |                                   |        P2:  i1 -> i2
         V               P2                  |        P3:  i2 -> h2
    i1  IMP  ---------------------------->  IMP i2    P4:  i2 -> i1
         ^               P5                  |        P5:  i1 -> ring 
         |                                   |
         |               P4                  |
         <-----------------------------------V

                 P1           P2         P3         P4        P5
     -------+------------+----------+-----------+---------+-------
     type   | HOST2HOST  |  IMP2IMP | HOST2HOST | IMP2IMP | TOKEN
     dst    |    h2      |    i2    |    h2     |   i2    |   --
     src    |    h1      |    i1    |    h1     |   i1    |   --
     status |    NEW     |    NEW   |    NEW    |   ACK   |   --
     msg    |    xxx     |    xxx   |    xxx    |   --    |   --
     -------+------------+----------+-----------+---------+-------
    • The HOST may send its IMP an message with type=HOST2IMP just for testing if IMP is alive. The IMP when receive such message, will send its host an message with type=IMP2HOST and message field is the same as the host provides. This is just like HOST pings the IMP and the IMP replies something to HOST.
    • The control of flow of a HOST process is 
      HOST:
    reading from FIFO or IMP
    if a message from IMP then     // message: (type,src,dst,status,msg)
      if   type=HOST2HOST then     // a new message arrived
          show (src,msg) to stderr // The style of format is left to you.
      elif type=IMP2HOST           // IMP replies
          show (msg)  to stderr 
      endif
    endif
    if a command from FIFO then  // A command is a pair of integers:(host, msg).
       if host = 0 then          // host wants to check if IMP alive
         send to IMP (HOST2IMP, 0,0,0, msg)
       else                      // host sends a msg to another host
         send to IMP (HOST2HOST, host, my_host_id,  NEW, msg)
       endif
    endif
    • The control of flow of an IMP process is 
      IMP
    reading from HOST or ring
    if a message from HOST then  // message: (type,dst,src,status,msg)
      if   type = HOST2IMP then            // host asks:   Are you there?
        send to HOST (IMP2HOST,0,0,0,msg)  // IMP replies: Your command, sir?
      elif type = HOST2HOST then           // host want to send a new message
        if got_msg                         // buffer is already filled with
           do nothing                      //     the previous message. 
        else                               // buffer is empty. so store it.
           store this message to buffer
           got_msg := true
        endif
      endif
    endif
    if a message from ring then  // message: (type,src,dst,status,msg)
      if type = TOKEN then                  // Aha, it is my turn
        if got_msg then                     // Yes, I have something to send
          // if the stored message is (HOST2HOST, dst, src, status, msg)
          dstIMP := lookupIMP( dst )        // translate from host id to imp id 
          srcIMP := lookupIMP( src )    
          sending to ring (IMP2IMP,dstIMP,srcIMP,status,msg) 
        else                                // host has nothing to send
          send to ring (TOKEN, 0,0,0,0)
        endif
      elif type = IMP2IMP then 
        if dst = myIMP then              // a message for me
          dstHOST := lookupHOST( dst )   // translate from imp id to host id 
          srcHOST := lookupHOST( src )    
          sending to HOST (HOST2HOST, dstHOST, srcHOST, status, msg)
          sending to ring (IMP2IMP, dst, src, ACK, msg) //only status changed
          show something to stderr
        elif src = myIMP then            // an ack for me
          got_msg := false               // clean the buffer
          send to ring (TOKEN, 0,0,0,0)  // regenerate a TOKEN
          show something to stderr
        else
          bypass it, that is, send (type, dst, src, status, msg) to ring
        endif
      endif
    endif