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.
- 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?
- 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
Also, identify the queueing model for this system in Kendall's
- Compare the Java and C pthread synchronization primitives by showing
the equivalent language construction, where possible, for each in the
- 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
philNumber identifies the number of the philosopher wishing
to eat. When a philosopher finishes eating, it invokes
returnForks(philNumber). Your solution will implement the
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.
- 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?
- 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.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?
- 7.12: Consider the following snapshot of a system:
||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:
- What is the content of the matrix Need?
- Is the system in a safe state?
- If a request from process P1 arrives for (0,2,4,0), can the request
be granted immediately?
- Write a C/pthread program that illustrates deadlock between two or
more threads using one of the pthread synchronization primitives.
- 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?
- 9.18: Assume there is an initial 2048 KB segment where memory is
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:
- request 270 bytes
- request 240 bytes
- request 130 bytes
- request 60 bytes
- release 60 bytes
- release 270 bytes
- release 240 bytes
- 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?
- 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.
by Henning Schulzrinne