Assignment 12, due Apr. 20

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: The Unix/Linux fork() kernel call returns the process ID of the child process to the parent process, and wait() kernel call returns the process ID of the process that terminated. waitpid() allows you to wait for a specific child to terminate.

   a) Write code to fork a process into parent and child, then have the parent wait for that specific child using waitpid(). (0.5 points)

   b) Suppose you wanted to use waitpid() but you only had wait(). Write code for waitpid() using a call to wait(). This is not trivial because it is possible that the user calls waitpid(A) and then waitpid(B), but process B terminates before process A. (0.5 points)

2. Background: Recall that a set of processes is deadlocked if every process in that set is blocked waiting for some action that can only be done by some other process in that set.

   For each set of conditions discussed below, is automatic deadlock detection possible? If yes, how? In this case, don't give an algorithm, but give enough detail that you can convert the problem to one where there are known algorithms that solve the problem. If no, why not?

   a) All memory is shared between all processes, with processes using semaphores for mutual exclusion and synchronization. (0.5 points)

   b) Memory is not shared. Interprocess communication is through shared files, with the Unix/Linux flock kernel call being used for mutual exclusion and synchronization. Ignore the LOCK_NB option that allows for non-blocking operations (polling), so locks have only 3 states: unlocked, shared or exclusive. (0.5 points)

3. Background: Consider the following (invented) tools for client-server interaction on a shared-memory system:

   reply_handle = send_request( object_handle, server_ID )

   sends the indicated object as a request to the indicated process, which must act as a server and then await a reply. After the server replies, send_request returns the object that was included in the reply. Requests are queued and held until the server is ready to receive them.

   (object_handle, request_ID) = await_request()

   awaits a request from any client. The return value includes both the object handle sent with the request and the ID of the requesting process. (OK, the notation is a bit invented, but this function returns two distinct values.)

   send_reply( reply_handle, request_ID )

   sends a reply to the indicated client. The client must have sent a request to this process, and the value of request_ID must be a value returned buy await_request(). The reply_handle will be sent to the requesting process and returned by send_request() to that process.

   In this system, from a user perspective, each process may be either running, awaiting a request, or awaiting a reply. There may be additional process states that matter to the system in implementing these primitives. Assume that the implementation of these operations is done using semaphores. All semaphores involved in implementing these primitives go in the process description record.

   a) How many semaphores are required in each process description, who signals each of them, and who waits on each of them? Don't forget that there is a mutual exclusion problem hiding in the above description. (0.5 points)

   b) What would be a sensible way to implement the queue of processes that have sent requests to a server that have not yet been delivered to that server. Hint: Think about how many requests a process may have outstanding at any time and how may processes may be requesting service from any particular server. (0.5 points)