Assignment 10, due Apr. 22

On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies 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 Consider the problem of writing a thread manager on a Unix system that supports only the heavyweight primitives fork(), exit(), and wait(), plus the shmat() and shmdt() primitives for attaching and detatching shared memory segments. Your system supports multicore CPUs by running processes on separate cores of the CPU whenever possible.

   Also, suppose you have a lightweight thread manager such as the user-level thread package that was the subject of last week's homework. This thread manager multiplexes a single user process to support multiple threads. As such, it cannot exploit the resources of a multicore CPU. This thread manager creates thread data structures on a heap, maintains a ready list, and provides a relinquish() operation by which a thread may allow another thread to run.

   Your goal is to design (but not write the code for) a lightweight thread manager. This thread manager should allow lightweight threads to run on different cores of the CPU when possible.

   One way (not very smart, but easy to debug) to write the thread manager would be for it to start by launching one idle thread per core of the CPU and then fork multiple times so that there is one process per core. Then, and only then, would it begin launching and running user threads. All of the thread manager processes would run concurrently until the thread manager terminates, usually when the program itself terminates. The disadvantage of this is obvious: It uses all of the cores as much of the time as the operating system permits whether or not the user needs that many threads.

   a) Suggest an alternative rule for when the thread manager should fork another process to run threads. (0.5 points)

   b) As a companion to part a, suggest an alternative rule for when one process of the thread manager should terminate. (0.5 points)

   c) Consider the problem of supporting semaphores in this multicore thread manager. The semaphore implementation in the user-level thread package discussed in last week's homework would suffice on a uniprocessor. Why would this fail on a multithreaded processor? (0.5 points)

2. Background: Consider the following approaches to mutual exclusion:
   • Disable interrupts, then critical seciton, then enable interrupts.
   • Claim a spin-lock, then critical seciton, then release a spin lock.
   • Wait on a semaphore, then critical seciton, then signal that semaphore.
   • Use flock(fd,LOCK_EX), then critical seciton, then flock(fd,LOCK_UN).
   • Create a lock file, then critical seciton, then delete the lock file.

   a) For each of these, clearly identify the setting in which it is the most appropriate alternative. (0.5 points)

   b) For each of these, clearly identify the major disadvantage or limitaiton of the approach that makes it inappropriate in many settings. (0.5 points)

   c) Each of the above approaches rests on mechanisms. Some of the mechanisms used in some of these approaches require mutual exclusion to implement them. Others are stand-alone mechanisms. For each such mechanism mentioned in the above list, which approach (or approaches) will likely be used to implement that mechanism. (0.5 points)

MACHINE PROBLEM 5

Back to the little Unix shell from MP1! Due, May 2. Add support for these two little features:

• Parallel execution: If a shell command ends with an ampersand (&), launch it as a parallel process so that it runs in parallel with other shell commands launched later.

• Pipes. Modify your shell to include support for the pipe mechanism, so that if you type a | b it means to run the executable files a and b in parallel, with the standard output of a piped into the standard input of b.

You may require that there be spaces before the ampersand and pipe symbols, in order to minimize the need to make any changes to the command line parsing mechanism.

You will need to look at the pipe() kernel call to create a pipe, and you will need to look at the You may need to look at the open(), close() and dup() kernel calls to understand how to control which file descriptors are used for what.