Written Assignment 2 – Exercises in Multiprogramming and Multithreading

Assigned: Monday, 9/26/2005, 5pm	PLEASE TYPE (INSERT) YOUR ANSWERS IN THIS
Due: Tuesday, 10/4/2005 before 4pm	DOC AND EMAIL IT TO doursat@unr.edu (NO PDF!)

Name: __________________________________________________________________________

Part 1.  In the code below, assume that all fork statements return successfully and the execvp statements execute programs that do not spawn other processes.

a.	What is the total number of processes that will be created by the execution of this code?  Include the process executing the main routine.

b.	How many of each character ‘A’ to ‘G’ will be printed out?

You must justify your answers with a clear and readable table or diagram.  (40 pts / grad: 32 pts)

void main()
{
	...
	pid1 = fork();
	pid2 = fork();
	if (pid1 != 0) {
    pid3 = fork();
	    printf("A\n");
} else {
	    printf("B\n");
    execvp(...);
}
	if (pid2 == 0 && pid3 != 0) {
	    execvp(...);
	    printf("C\n");
}
	pid4 = fork();
	printf("D\n");
	if (pid3 != 0) {
    printf("E\n");
	    pid5 = fork();
	    execvp(...);
}
	printf("F\n");
execvp(...);
pid6 = fork();
	printf("G\n");
if (pid6 == 0)
    pid7 = fork();
}

Part 2.  Dekker’s algorithm was incorrectly copied in the code below:

boolean lamp[2];
int book = 0;

void do_thread0()
{
    while (true) {
        lamp[0] = true;
        while (lamp[1]) {
            if (book == 1) {
                lamp[0] = false;
                while (book == 1);
                    /* nothing */
                lamp[0] = true;
            }
        }
        /*** CRITICAL REGION 0 ***/
        book = 0;
        lamp[0] = false;
        ...
    }
}
	
void do_thread1()
{
    while (true) {
        lamp[1] = true;
        while (lamp[0]) {
            if (book == 0) {
                lamp[1] = false;
                while (book == 0);
                    /* nothing */
                lamp[1] = true;
            }
        }
        /*** CRITICAL REGION 1 ***/
        book = 1;
        lamp[1] = false;
        ...
    }
}

a.	Where does this code logically differ from the correct implementation?  (5 pts / grad: 4 pts)

b.	Does this code guarantee mutual exclusion of the two threads from their respective critical regions?  (15 pts / grad: 12 pts)

c.	Does this code guarantee “progress”, i.e., if one thread is currently executing outside its critical region, the other thread will always be able to enter its own critical region?  (15 pts / grad: 12 pts)

d.	Does this code prevent starvation, i.e., does it prevent the situation where a thread repeatedly enters and exits its critical region without letting the other thread enter its own critical region?  (15 pts / grad: 12 pts)

For questions b., c. and d.: if your answer is yes, write an explanation that will logically cover all possible scheduling scenarios.  If your answer is no, give only one counter-example.

Part 3.  In the code below, three processes are competing for six resources labeled A to F.

a.	Using a resource allocation graph (Stallings, Fig. 6.5 and 6.6) show the possiblity of a deadlock in this implementation.  (10 pts / grad: 8 pts)

b.	Graduate students only (bonus points for the others): Modify the order of some of the get requests to prevent the possiblity of any deadlock.  You cannot move requests across procedures, only change the order inside each procedure.  Use a resource allocation graph to justify your answer.  (20 pts)

void P0()
{
  while (true) {
    get(A);
    get(B);
    get(C);
    // critical region: 
    // use A, B, C
    release(A);
    release(B);
    release(C);
  }
}
	
void P1()
{
  while (true) {
    get(D);
    get(E);
    get(B);
    // critical region: 
    // use D, E, B
    release(D);
    release(E);
    release(B);
  }
}
	
void P2()
{
  while (true) {
    get(C);
    get(F);
    get(D);
    // critical region: 
    // use C, F, D
    release(C);
    release(F);
    release(D);
  }
}