Project 2: Semaphores

Assigned: March 2
Due: March 30

In this project, you will extend the Simulated Toy Machine (STM) with semaphores and the two operations DOWN and UP.

There are 8 semaphores, indexed 0-7. Each semaphore consists of a value , which is a non-negative integer, and a FIFO queue of processes waiting for the semaphore.

The operations on the semaphores are defined as follows.

{ if (s > 0) s--;
   else block the current process --
        i.e. take the current process off the ready queue and 
             put it at the end of the queue of processes waiting for s.

{ QW = the queue of processes waiting for s;
  if (QW is empty) then s++;
   else { P = pop the first process off QW;
          push P onto the end of the ready queue.
Semaphore operations are invoked by STML code by doing traps to the kernel. Specifically, to execute DOWN(s), load the code 3 into register R15, load the index of semaphore s into register R14, and execute the instruction "TRP". To execute UP(s), load the code 4 into register R15, load the index of semaphore s into register R14, and execute the instruction "TRP".

At the start of execution, semaphores are initialized to 1.

Context switches

A call to UP or DOWN causes a context switch only in the case where the current process blocks doing a DOWN. Otherwise, the rules for context switches is the same as in project 1. Putting these all together, therefore, the rule for context switches is this:

Let P be the current process, and let Q be the next process on the ready queue.

Debugging output

If the debugging flag is 1 or 2, the program should generate a trace statement each time an UP or DOWN occurs, stating that the operation has occurred. If the operation causes a process to block or to unblock, that should be stated.


This project is an extension of project 1. It may be done either in C or in Java. You can take as your starting point either: This project should be substantially easier than project 1. For one thing, it involves writing less code; for another, you are already familiar with the STM. What you mainly need to do is:


The STML file fractionx.stm has a modified version of "fraction.stm" in which semaphores are used to enforce mutual exclusion on the reading and the writing section of the code. Semaphore 0 protects the reading; semaphore 1 protects the writing. The result is that if several instances of "fractionx.stm" are run in parallel, the inputs to each process all sequential, and the outputs are all sequential, whereas project 1 interspersed reading from the different processes and interspersed the outputs from the different processes.

The particular example shown here has the command line
"proj2 -d DEBUG fractionx.stm fractionx.stm fractionx.stm":

1/7 base 10 is .142857 ...
13/19 base 100 is .68 42 10 52 63 ...
700/1001 base 1000 is .699 300 699 300 ...