Operating Systems--Spring 2011

    Home | | Schedule | | Assignments | | Lecture Notes

    Homework 3

    Due: Thursday, April 28, 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. deadlock
    4. reader/writer problem
    5. dining philosopher's problem

    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. 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 5. 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 Thursday, April 28 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: April 14, 2011
    Page Expires: January 8, 2012