CS 414 Fall 2003: Homework 2 (due Tuesday Sept. 23 Thursday, Sept 25)

 

Please type your solutions.

 

 

 

1.  Consider the following n-process critical section "solution"

 

 

boolean   inside[0..N-1] = { false, false, .... false };

 

CSEnter()

{

        int k

        for(k = 0; k < N; k++)

        {

            while(inside[k] == true)

                continue;

        }

        inside[i] = true;

}

 

CSExit()
{

        inside[i] = false;

}

 

a) Is this solution safe (does it satisfy mutual exclusion)?  Either give an informal proof, or give a counter example.

 

b) Is this solution live (will a process eventually get in)?  Again, give an informal proof or a counter example.

 

Now suppose that we change the code for CSEnter() as follows.  

CSEnter()

{

        int k;

       inside[i] = true;

        for(k = 0; k < N; k++)

        {

            while(inside[k] == true && k != i)

                continue;

        }

}

 

 

c) Is the new solution safe?  

 

d) Is the new solution Live?

2.    Suppose that you are writing software to control a roller coaster.  We'll treat the patrons as processes.  The roller coaster itself is a process too.  Here's the basic code for each:

Patron_i:

        forever
        {
               think about going on the roller coaster
               wait_on_line();
               find_a_seat();
               wait_until_ride_ends();
               leave_the_seat();
         }

boolean  the_roller_coaster[0...K-1] = { false, false, .... false };

RollerCoaster:

         forever
         {
                allow_K_patrons_off_line();
                wait_until_seated();
                zoom around
                ride_is_over();
                wait_until_empty();
          }

Using semaphores, write code for the 8 procedures called by these skeletons.  Notice that the roller coaster itself is represented by a vector of flags.  The idea is that it has K seats and each seat has its flag set to false if empty, and true while someone is sitting in it.  You may assume that if we wait long enough, eventually K patrons will show up.  You can add extra global variables if needed (and you will need some, although you can get by with just semaphores if you are clever).
                

3.   Suppose that process A outputs a file (a stream of characters) and program B will read that file in.  Such patterns arise all the time in applications like compilers, which may need to do a pass to expand "macros", a pass to build the symbol table, etc.  You've decided to connect A directly to B using a bounded buffer.  What considerations would you weigh in deciding how large the buffer should be?  For example, should the buffer be as large as possible?  As small as possible?   In answering, try to relate your answer to the costs of the approach you favor.  Your goal is to recommend the solution that will be cheapest in terms not just of memory consumed but also computer time lost to overhead (such as context switching).

4.  A CD or DVD burner device can support one process writing to the device, or a maximum of 4 processes concurrently reading from the device.  

a)  Using semaphores, implement procedures StartRead, StartWrite, EndRead and EndWrite so that (1) these limits will be enforced, and (2) Processes are allowed to access the device in a strict FIFO order.  For example if P2 calls StartWrite and has to wait, and then P4 calls StartRead, P2 gets to write before P4 gets to read.  

b) Solve the problem again, but this time using monittors.