1. What are the four necessary conditions for deadlock?

Mutual exclusion: only one process may use resource at a time

Hold-and-wait: resources held by one process, and other must wait until granted access

No Preemption: once one process has a resource, no other process can take it away.

Circular Wait: process a holds resource 1, needs resource 2; process b holds 2, needs 1.

2. Why are these four conditions necessary, but not sufficient?

If multiple instances of a resource exist, can have four conditions, but still not be deadlocked because a process not involved in the cycle could release a resource.

2) (15 points) Synchronization

1. If you computer has an atomic swap instruction, but not test-and-set, show the code to simulate test-and-set using swap.

Test-and-set(int *loc) {
	Int word = 1;
	Swap word, *loc
	Return word
}

2. In a multi-processor system, why is turning off interrupts on a processor not a sufficient solution to the critical section problem?

 
Semaphore mutex = 1
Semaphore writer = 0
Semaphore reader = 0
 
int nReader = 0
int nWriter = 0
int wReader = 0
int wWriter = 0
 
Writers execute this code:
 
while (1) {
 
P(mutex);
if (nReader + wWriter + nWriter == 0) {
	nWriter++;
	V(mutex);
} else {
	wWriter++;
	V(mutex);
	P(writer);
}
 
Write operation;
 
P(mutex);
NWriter = 0;
If (wReaders > 0) {
	 for i = 1 to min(wReaders,5) {
		V(readers)
		nReaders++;
		wReaders--;
	}
else if (wWriters > 0) {
	wWriters--;
	nWriters++;
	V(writer);
}
V(mutex);
}
 
Readers execute this code:
 
while (1) {
 
P(mutex)
if (nWriters + wWriter == 0 & nReader < 5) {
	nReaders++;
	V(mutex);
} else {
	wReaders++;
	V(mutex);
	P(reader);
}
 
Read operation;
 
P(mutex);
nReaders--;
if (wWriters > 0 & nReaders == 0) {
	wWriters--; 
nWriters++;
	V(writer);
} else if (wReaders > 0 & wWriters == 0) {
	nReaders++; 
	wReaders--;
	V(reader);
}
V(mutex);

void interrupt yield_process ()
{
...
 
_AX = FP_SEG(dispatch); /* Push the address of dispatch */
asm push ax
_AX = FP_OFF(dispatch); /* on the top of the stack */
asm push ax
 
runq.stack_top = MK_FP(_SS,_SP);
 
...
}

1. Why is the statement runq.stack_top = ... needed? We have already set the stack up when we created the process?

The stack might have changed while running the thread, so we need to save the current value.

2. Why is yield_process an interrupt handler? We only call it from inside system_service which is already an interrupt handler.

Alhtough system_service has already saved the state on the stack when it starts, yield_process is called within system_service which may have changed the state (for example due to local variables on the stack in system_serivce).

5) (20 points) Scheduling. It has been claimed that for every scheduling strategy, there is a counter strategy (a way for a user to exploit the policy to their advantage and the detriment of other users). For each scheduling policy below, describe a counter strategy. For all cases, assume we are using a mulit-level feedback queue that does round-robin scheduling within each priority level.

1. To penalize compute bound jobs, any jobs that use an entire scheduling quantum are dropped to the next lowest priority level.

Yield the processor an epsilon before your time is up, and the process will remain at the highest priority level.

2. To help I/O bound jobs, any process that performs an I/O operation during its scheduling quantum is moved up to the next highest priority level.

Just before the end of a quantum, perform a I/O operation such as write a character to the screen.

3. Any time left in a scheduling quanta when the process voluntarily yields the processor is added to the next scheduling quanta.

Web Accessibility