CMSC 412 (shankar, exam 1, oct 27, 1994)                       Name:-------------

Total points 50. Total time 75 mins. Closed book. There are 7 problems over 5 pages.

1. [7 pts]  The following 3 processes implement a mutual exclusion algorithm.
 

  

Assume the following:

• and  use busy-waiting (e.g. with test-and-set loops).
• Execution time of  is 0 if no process in its  (e.g. the lock is free).
• Execution time of  ,  , and loop branch is 10 ms.
• The 3 processes are run on a single CPU using round-robin scheduling with quantum size of 5 ms.

(a) What is the throughput, i.e. number of critical sections executed per second.

(b) What can you say about the waiting time of a process, i.e. the time taken to execute  .

2. [5 pts]  Using semaphores, modify the following so that at any time at most three of the processes,  , are executing their  's.
 

   

3. [5 pts]  Is the following following a correct solution to the 2-process mutual exclusion problem? Justify your answer.

: array [0..1] of { true, false }. Initialized to false.
: 0..1. Initialized to 0.
 

 
 

4. [8 pts]  You have to solve the 4-process mutual exclusion problem by repeatedly applying Peterson's 2-process mutual exclusion solution. Assume the following constructs for Peterson's solution:

• variables  ,  ,  .        /* of appropriate type and initial value */
•                     /* executed by process 0 */
•                    /* executed by process 1 */
•                       /* executed by process 0 */
•                       /* executed by process 1 */

Using the above constructs, solve the 4-process mutual exclusion problem, i.e. supply the variables and code for the boxes below. Your solution must not use any other synchronization primitives (such as test-and-sets, disabling/enabling interrupts, semaphores, etc.).

    // shared variables

   

Hint: think of a binary tree with four leaves representing A, B, C, and D.

5. [5 pts]  In project 2, the top of the stack of a ready process contained the address of dispatch(), and you had the following:

void scheduler ()
 { ...
   /* get next ready process,
      put it in run queue,
      update \_SP and \_SS to process's stack */
      asm retf  /* go to dispatcher */
 }

void dispatch ()
 { asm {
    mov sp, bp
    pop bp
    pop bp
    pop di
    ...
  }

If you replaced the asm retf in the scheduler by dispatch(), what changes would be required elsewhere?

6. [5 pts]  In project 2, you had

void interrupt system_service ( sbp, sdi, ssi, sds, ses, sdx, ... , proc, argc, argv )

What is the purpose of specifying all these parameters in the definition of system_service?

7. [15 pts]  You have to solve a variation of the readers-writers problem, in which multiple writers can write at the same time. Specifically, there are readers and writers. Multiple reads at the same time are allowed. Multiple writes at the same time are allowed. A read and a write at the same time is not allowed.

Provide a solution using semaphores with the following properties:

• no busy waiting.
• starvation-freedom (i.e. a continuous stream of readers does not starve writers, and vice versa) is desirable but not compulsory (you will lose only some points).
• you cannot use process ids and you cannot have a separate semaphore for every process.

Below is a skeleton program for you to build upon by supplying code for the boxes and perhaps introducing more variables. You are also welcome to disregard this skeleton and come up with something else.

integer initialized to 0.       /* number of reads currently executing */
integer initialized to 0.          /* number of readers currently waiting */
semaphore initialized to 0.      /* readers wait here */
integer initialized to 0.       /* number of writes currently executing */
integer initialized to 0.          /* number of writers currently waiting */
semaphore initialized to 0.     /* writers wait here */

 

SOLUTION TO EXAM 1 CMSC 412 (shankar): Fall 94

1. [7 pts]

Assume without loss of generality that round-robin queue has processes in the order A, B, and C. Here is the evolution starting from time 0.

     A executes  till time                     5 ms          A  waited 0 ms
     B executes  till time                            10 ms         B  starts wait at 5 ms
     C executes  till time                          15 ms        C starts wait at 10 ms
    A executes , till time    20 ms        A  completes

    B executes  till time                     25 ms       B waited 15 ms
    C executes  till time                           30 ms
    A executes  till time                            35 ms       A starts wait at 30 ms
    B executes  ,  till time   40 ms       B completes

   C executes  till time                      45 ms      C waited 30 ms
   A executes  till time                              50 ms
   B executes  till time                              55 ms      B starts wait at 50 ms
   C executes  ,  till time    60 ms      C completes

and so on

(a) [5 pts] one  executed every 20 ms, or equivalently 50 per second.

(b) [2 pts] average waiting time is 30 ms (ignoring initial transient).

2. [5 pts]  Introduce the following: a semaphore, say gate, initialized to 3; P(gate) before every  ; and V(gate) after every  .

3. [5 pts]  No. It allows both processes to enter CS as follows.

executes	-   true  - while  do  - while  do skip  (  at  )
executes	-  true  - while  do  (  at CS)
executes	-   - while  do  (  at CS)

 

Can also have starvation as follows:

 (1)    executes -    true ; ... ; enters  

 (2)  executes -  true ; enters while  do skip

 (3)  executes -  false ; branches back ;  true ; 

Steps (2), (3), (2), (3), ... can repeat endlessly. Each process is getting a share of CPU, but  starves.

4. [8 pts]  Introduce three sets of variables, say,  ,   ,   , 
 

   
 

[3 points for recognizing three applications of Peterson's algorithm, 2 points for declaring the variables, 3 points for the entry and exit code.]

5. [5 pts]  Calling dispatch() instead of using retf places the return address (a location within scheduler) on the stack, after which dispatch() puts its frame on the stack.

The simplest fix is to modify dispatch() so that it removes the frame (as is currently done), then removes the next 4 words on stack (skipping return address and address of dispatch on stack), and continue as before (restore registers).

A more natural fix is to not have the address of dispatch() on top of a ready process's stack. proc_start and defer should not put address of dispatch () on stack. The beginning of dispatch() should be modified to remove the frame (as is currently done) and the return address to scheduler.

6. [5 pts]  To access variables that are already on the process's stack, and have the compiler generate the addressing code.

7. [15 pts]

Add semaphore  initialized to 1 to protect the variables.

 

[2 points for  , 4 for updating  and  (consitently), 3 for updating  and  , 2 for P(  and P(  , 4 for P(  and P(  .]

Common mistakes: Using more than one  . Doing only one V when last reader (or writer) leaves (causes readers and writers to alternate in heavy load, readers can be left stranded if no writers show up, ...).
 

Wed Oct 7 12:17:05 EDT 1998