|Due date: May 9, 2008
These can be answered in a sentence or two, and are intended to reinforce
In FreeBSD, what is the ZOMBIE state? What causes the process
to exit that state?
In FreeBSD, how does the system tailor the short-term scheduling
algorithm to favor interactive jobs?
What are the three conditions that any solution to the
critical section problem must meet?
These questions require some thought and longer answers than the short-answer
questions. They are intended to have you use the concepts discussed in class, to be
sure you understand them and can work with them.
A binary semaphore is most commonly defined
as a semaphore whose integer value can range only between 0 and 1. Implement
the usual type of semaphore using binary semaphores.
The sleeping barber problem takes place in a
barber shop. The barber shop has one barber, one barber’s chair, and 5
chairs for waiting customers. If there are no customers, the barber sits in the
barber’s chair and falls asleep. When a customer comes in, if there are
no other customers, he wakes the barber, sits in the barber’s chair, and the
barber cuts his hair. If customers arrive while someone is having his hair cut,
they sit in the chairs for waiting customers, if any are empty, or leave, if all
are full. Write a program using semaphores to solve the sleepy barber problem.
An operating system designer has proposed a multilevel feedback
queueing scheme in which there are five levels with round robin scheduling on each
level. The quantum at the first level is 0.5
seconds, and each lower level has a quantum twice the size of the quantum at the
previous level. A process cannot be pre-empted until its quantum expires, and
then it is moved to the next lower queue (unless it is in the lowest queue, of
course). If the process does I/O, upon completion it is returned to the queue
from which it left. The system runs both batch and interactive jobs, and these,
in turn, consist of both CPU-bound and I/O-bound jobs.
- Why is this scheme deficient?
- What minimal changes would you propose to make the scheme more
acceptable for its intended job mix?
Measurements of a certain system have shown that the average process
runs for a time t before blocking on I/O. A process switch requires
a time s, which is effectively wasted (i.e., it is overhead time).
For round robin scheduling with a quantum q, give a formula for
the processor utilization for each of the following:
- q = ∞
- q ≥ t
- s < q < t
- q = s
- q nearly 0
Extra Credit Problems
Consider a computer that does not have a test-and-set instruction
but does have an instruction to swap the contents of a register and a memory word
in a single indivisible action. Can that be used to solve the critical section
problem? If so, how; if not, why not?