CMSC 412 Midterm #1 (Spring 1996)
- (15 points) Define the following
terms:
- thread
- policy vs. mechanism
- preemptive multi-tasking
-
critical
section (three conditions)
- (10 points) Statement: In
DOS, user programs change the hardware interrupt vector.
- If user programs can do this, why
is it impossible to provide processor protection?
- Windows NT provides processor protection
and can run DOS programs? Explain how this might be accomplished?
- (20 points) In a system that contains
only one instance of each resource, circular waiting is a necessary
and sufficient condition for deadlock.
- Why is circular waiting sufficient
if there is only one instance of each resource, but only necessary
if there is one instance of each resource?
- Consider a system with one instance
of each resource, and the condition that requests for resources
must be satisfied in the order in which they are received. Give
an algorithm that takes as input requests to allocate and release
resources and determines if the system is deadlocked.
- (25 points) You have to solve a
variation of the readers-writers problem, in which multiple writers
can write at the same time. Specifically, there are readers and
writers. Multiple reads at the same time are allowed. Multiple
writes at the same time are allowed. A read and a write at the
same time is not allowed. Provide a solution using semaphores
with the following properties:
- no busy waiting.
- starvation-free (i.e. a continuous
stream of readers does not starve writers, and vice versa) is
desirable but not compulsory (but you will lose some
points).
- you cannot use process ids and you
cannot have a separate semaphore for every process.
(15 points) Your friend, Lazy Student,
wants to test his implementation of multiplication (shown below)
as a process in your kernel from assignment number two. Why might
Lazy not want to run multiply(5000, 2)? Explain (in as much detail
as possible) what would happen if he tried this.
int multiply(int x, int y)
{
if (x == 1) {
return(y);
} else {
return(y + multiply(x-1,y));
}
}
(15 points) Using test-and-set
instructions, provide an algorithm that solves the dining philosophers
problem. Recall that in this problem, n philosophers sit at a
round table with one chop stick between each philosopher. Philosophers
either are thinking or eating (rather dull people :). To eat,
they need to acquire the chopsticks to their left and their right.
Your solution must work for any number of philosophers and ensure
that none of them starves to death.
Web Accessibility