Assignment 7: Chapter 6, 7, 8 and 9

This assignment is to be completed individually, not as a group.

Please make sure that you're using the same edition of the book. There is no guarantee that older editions use the same numbering for problems. Please submit a single tar file.

  1. Why do operating systems such as Solaris, Linux and Windows 2000 use spinlocks as synchronization primitives only on multiprocessor systems and not on single-processor systems?
  2. Using pthreads condition variables and threads, implement the sleeping barber problem in C: The QuickShave barbershop consists of a waiting room with n (a parameter configurable via the command line) chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is is busy but chairs are available, then the customer sits in one of the three chairs. If the barber is asleep, the customer wakes up the barber. To prevent arguments, customers are served in order of arrival. Your program should use sequentially-numbered customers that arrive at intervals that are randomly distributed between 1 and 10 second; the shave always takes 5 seconds.

    Also, identify the queueing model for this system in Kendall's notation.

  3. Compare the Java and C pthread synchronization primitives by showing the equivalent language construction, where possible, for each in the other language.
  4. 6.30: In Section 6.7.2, we provide an outline of a solution to the dining-philosophers problem using monitors. This exercise will require implementing this solution using Java's condition variables. Begin by creating six philosophers, each identified by a number 0..5. Each philosopher runs as a separate thread. Philosophers will al- ternate between thinking and eating. When a philosopher wishes to eat, it invokes the method takeForks(philNumber), where philNumber identifies the number of the philosopher wishing to eat. When a philosopher finishes eating, it invokes returnForks(philNumber). Your solution will implement the following interface: 
    public interface DiningServer 
{ 
  // called by a philosopher when it wishes to eat 
  public void takeForks(int philNumber); 
  // called by a philosopher when it is finished eating 
  public void returnForks(int philNumber); 
}

    The implementation of the interface follows the outline of the solution provided in Figure 6.25. Use Java's condition variables to synchronize activity of the philosophers and prevent deadlock.

    Note: If you prefer, you can also implement this in C uses pthreads.

  5. Fig. 6.40 shows a concurrent serializable schedule that is equivalent to the serial schedule in Fig. 6.39. Is there another schedule that is conflict serializable?
  6. Consider a four-way stop sign. Can there be deadlock? Indicate whether the four necessary conditions for deadlock are met. How would you avoid it?
  7. 7.3: A possible solution for preventing deadlocks is to have a single, higher-order resource that must be requested before any other resource. For example, if multiple threads attempt to access the synchronization objects A, ..., E, deadlock is possible. (Such synchronization objects may include mutexes, semaphores, condition variables, etc.) We can prevent the deadlock by adding a sixth object F. Whenever a thread wants to acquire the synchronization lock for any object A ... E, it must first acquire the lock for object F. This solution is known as containment: The locks for objects A, ..., E are contained within the lock for object F. Compare this scheme with the circular-wait scheme of Section 7.4.4. What are the advantages and disadvantages of the scheme?
  8. 7.12: Consider the following snapshot of a system:
    Process Allocation Max Available
    A B C D A B C D A B C D
    P0 2 1 0 0 2 1 0 0 0 2 5 1
    P1 0 0 0 1 0 5 7 1
    P2 4 5 3 1 6 5 3 2
    P3 2 3 6 0 2 5 6 0
    P4 4 1 0 0 6 5 6 3

    Answer the following questions using the banker's algorithm:

    1. What is the content of the matrix Need?
    2. Is the system in a safe state?
    3. If a request from process P1 arrives for (0,2,4,0), can the request be granted immediately?
  9. Write a C/pthread program that illustrates deadlock between two or more threads using one of the pthread synchronization primitives.
  10. 9.5: Assume we have a demand-paged memory. The page table is held in registers. It takes 5 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 60 nanoseconds. Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?
  11. 9.18: Assume there is an initial 2048 KB segment where memory is allocated using the Buddy system. Using Figure 9.27 as a guide, draw the tree illustrating how the following memory requests are allocated: Next, modify the tree for the following releases of memory. Perform coalescing whenever possible:
  12. Suppose that a machine provides instructions that can access memory locations using the one-level indirect addressing scheme. What is the sequence of page faults incurred when all of the pages of a program are currently non resident and the first instruction of the program is an indirect memory load operation? What happens when the operating system is using a per-process frame allocation technique and only two pages are allocated to this process?
  13. Implement a simulator for the clock algorithm for simulating LRU replacement in either Java or C. Your system has pages numbered 0 through 31. Your program should generate a random page reference sequence and you should be able to vary the number of frames. Record the number of page faults as you set the frame count to 10, 20, and 25.
Last updated by Henning Schulzrinne