Homework 1, cs414 Fall 2000. Published on the cs414 webpage on Sep 7.

Due back in in Upson Hall 4119 with Tammy Howe on Sep 15, 3pm (or class on Sep 14).

Late homeworks accrue 10% penalty period of 24 hours (0-24 hours, 10%, 24:01-25, 20%, etc)

Collaboration is prohibited and will be treated as a violation of the University's academic integrity code.

Hand in a single hardcopy, typeset (in 10 point or larger font). This is because hand-written solutions are often hard to read and with such a large class, we really need to use our time to understand your work, not your handwriting. Solutions which are not typed will be graded at the discretion of the grader.

1. A computer system has two printers, named pr1 and pr2, attached to it. A program called print is available. It takes the name of a file and the name of a printer as arguments and causes the named file to be printed on the named printer. The print program returns once the file has been printed.

There are two problems with print. If two processes try to use it to print files on the same printer at the same time, the printer's output is garbled. Second, processes often don't care which printer their file is printed on. Whichever printer is available will do.

a.

Write a program called print_anywhere which can be called by multiple processes and which will solve these problems. Your program should take one argument, the name of the file to be printed. If either printer is not in use, the file should be printed immediately on a free printer (by a call to print ). If both printers are in use, printing should be delayed (block the calling process) until a machine is available. You must ensure that each printer prints only one file at a time.

Implement print_anywhere using semaphores and any shared or local (not shared) variables you need. Your program should be short. Use C, or any understandable pseudo-code, to express your algorithm. You may assume that all access to the printers will be through your print_anywhere program. You should only use semaphores, busy waiting is not acceptable.

b. Give a proof sketch (high-level reasoning) that the print_anywhere program is fair and does not cause starvation or deadlocks in the system.

2. The given solution of the unbounded buffer producer-consumer problem in class works for the specified assumptions:

Show which lines of the code you would change to optimize it for the following cases; in each case, provide a short explanation (1-2 lines) why there would be no deadlock and no starvation in your new code.

  1. a single producer and a single consumer exist
  2. producers and consumers can access the buffer, as long as there is no conflict (that is, no two processes are trying to access the same item in the buffer)

3. To implement semaphores, we mentioned in class that one can disable interrupts in uniprocessors. Give short (2-3 lines) to the questions below.

  1. What are the consequences of this, with respect to the clock interrupt routines and how it can affect the processes or the computer system itself?
  2. Define the semaphore P and V operations for multiprocessors in terms of tset or Xchng primitives.

4. You've just been hired by Mother Nature to help her out with the chemical reaction to form water, which she doesn't seem to be able to get right due to synchronization problems. The trick is to get two H atoms and one O atom all together at the same time. The atoms are threads. Each H atom invokes a procedure hReady when it's ready to react, and each O atom invokes a procedure oReady when it's ready. For this problem, you are to write the code for hReady and oReady. The procedures must delay until there are at least two H atoms and one O atom present, and then one of the procedures must call the procedure makeWater (which just prints out a debug message that water was made). After the makeWater call, two instances of hReady and one instance of oReady should return. Write the code for hReady and oReady using either semaphores or locks and condition variables for synchronization. Your solution must avoid starvation and busy-waiting.