Homework 8

22C:116, Fall 2001

Due Friday Nov 2, 2001, in class

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

1. Programming Assignment: Write a package of functions callable from C programs that supports semi-synchronous message passing interprocess communication under UNIX. The user interface to this package is as follows:

   send( process_id, buffer, message_length )

   sends the message stored in the buffer, of the length given, in bytes, to the given process. Send blocks if the previous message sent by any process to the given process has not yet been received.

   message_length = receive( buffer, buffer_length )

   receives a message addressed to the calling process into the buffer. This blocks until a message is received, and then returns the length of the message that was received. The length returned will always be less than or equal to the buffer length; if the length returned equals the buffer length, it is possible that the message sent did not fit entirely within the buffer and data may have been lost.

   In all cases, the buffer parameter points to the first byte of the array of bytes to use as a buffer, and the message lengths are given in bytes. All process IDs in UNIX are integers.

   Note that no limitation is placed on the UNIX primitives you may use! If you ignore efficiency, you will find that you can construct a working solution that is quite small and not horribly inefficient.

   Test your solution with a program that forks two child processes and then sends them alternate lines of text from standard input. Each child process should print the lines it gets to standard output.

   Problems from the text:
   a) Do problem 3 on page 578.
   b) Do problem 10 on page 579.
   c) Do problem 15 on page 579.
   d) Do problem 23 on page 580.
   e) Do problem 26 on page 580.

2. Background:

   The HW8 multiprocessor (invented for this assignment) has 8 identical processors. When a trap request is issued by a processor, the trap is handled on that processor. The interrupt hardware, in contrast, distributes interrupts to whatever processor is currently running the lowest priority code. To allow this, each processor must, of course, export the priority field of its processor status word to the interrupt control system.

   The HW8 bus supports atomic operations on 64 bit quantities. It includes the optomistic synchronization primitives load-locked and store-conditional, these may be used for implementing atomic operations on shared variables. It also includes instructions to enable and disable interrupts. There are also the usual load and store instructions.

   The HW8 operating system kernel dispatches processes from a single shared ready list. The ready list is a simple linked list of process control blocks with a single head pointer called (very creatively) ready_list_head. Each process control block includes a pointer to the next block in the list, called (very creatively) next_process.

   Problem: Give, at a fairl level of detail, the code needed to dequeue a process from the ready list. Before you begin to write code, think about these two questions: Is it necessary to disable interrupts? Is a special semaphore needed to guard the ready_list_head? (The answers to these questions are not required for this assignment, they are merely to guide you in your programming).