Operating Systems--Spring 2005

    Home | | Schedule | | Assignments | | Lecture Notes

    Homework 3

    Due: Friday, April 22, in class

    Answer the following questions. Your answers should be typed (except for the Gantt diagrams, which you may draw by hand).

    Question 1. Briefly define each of these terms (one or two sentences each):

    1. critical section
    2. atomic execution
    3. busy waiting
    4. deadlock
    5. semaphore
    6. progress
    7. reader/writer problem
    8. dining philosopher's problem
    9. logical address
    10. physical address
    11. internal fragmentation
    12. external fragmentation

    Question 2. Consider a concurrent system with two processes, P and Q, shown in the following code. A, B, C, D, and E are arbitrary atomic (indivisible) statements. Assume that these two processes are executing concurrently.
    Process P Process Q
    begin begin
    A; D;
    B; E;
    C; end.
    end.
    Show all the possible interleavings for the execution of P and Q. That is, give each possible execution "trace", in terms of the atomic statements, that could occur.

    Question 3. Does the following solution to the critical section problem for three processes satisfy mutual exclusion? Justify your response.

    Concurrent Flags:
    There are three flags (shared variables): flag1, flag2 and flag3
    There is one shared variable, sign, that is set to 1, 2 or 3, corresponding to each process.
    initially: all flags are false and sign is set to 1.

    Process A: 
    while(1) {
   //do some stuff
   flag1 = true;
   sign = 1;
   while ((flag2 || flag3)
      && (sign == 1)) {
      // do nothing
   }
   //critical section
      ...
   flag1 = false;
}
    		Process B: 
    while(1) {
   //do some stuff
   flag2 = true;
   sign = 2;
   while ((flag1 || flag3)
      && (sign == 2)) {
      // do nothing
   }
   //critical section
      ...
   flag2 = false;
}
    		Process C: 
    while(1) {
   //do some stuff
   flag3 = true;
   sign = 3;
   while ((flag1 || flag2)
      && (sign == 3)) {
      // do nothing
   }
   //critical section
      ...
   flag3 = false;
}

    Question 4. Does the following solution to the critical section problem for two processes satisfy the following requirements for critical sections: mutual exclusion, bounded waiting (no starvation) and progress? Justify your response.

    Concurrent Flags2:
    There are two flags (shared variables): flag1 and flag2
    There is one shared variable, sign, that is set to 1 or 2, corresponding to each process.
    initially: both flags are false and sign is set to 1.
    Process A: 
    while(1) {
   //do some stuff
   flag1 = true;
   while (flag2) {
      if (sign == 2) {
   	     flag1 = false;
   	     while (sign == 2)
   	        ; //do nothing
   	     flag1 = true;
      }
   }
   //critical section
      ...
   sign = 2;
   flag1 = false;
}
    		Process B: 
    while(1) {
   //do some stuff
   flag2 = true;
   while (flag1) {
      if (sign == 1) {
   	     flag2 = false;
   	     while (sign == 1)
   	        ; //do nothing
   	     flag2 = true;
      }
   }
   //critical section
      ...
   sign = 1;
   flag2 = false;
}

    Question 5. Suppose a fixed partitioning memory system with partitions of 100K, 500K, 200K, 300K, and 600K (in memory order) exists. All five partitions are currently available.

    1. Using the first fit algorithm, show the state of memory after processes of 212K, 417K, 112K, and 350K (in request order) arrive.
    2. Using the best fit algorithm, show the state of memory after processes of 212K, 417K, 112K, and 350K (in request order) arrive.
    3. At the end of part (a), how much internal fragmentation exists in this system?
    4. At the end of part (b), how much external fragmentation exists in this system?

    Question 6. Consider a logical address space of eight pages of 1024 bytes each, mapped onto a physical memory of 32 frames.

    1. How many bits are there in the logical address?
    2. How many bits are there in the physical address?

    Completed homework:

    • Turn in your typed answers to the homework questions (and drawn timing charts) by Friday, April 22 in class.

    Home | | Schedule | | Assignments | | Lecture Notes

    Constance Royden--croyden@mathcs.holycross.edu
    Computer Science 346--Operating Systems
    Date Created: January 9, 2004
    Last Modified: January 7, 2005
    Page Expires: January 8, 2006