Tutorial Week 5

Questions and Answers

Deadlock

Q1: What is deadlock?

A set of processes are deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

Q2: What is starvation, give an example?

Starvation is where the system allocates resources according to some policy such that progress is being made, however one or more processes never receive the resources they require as a result of that policy.

Example, a printer that is allocated based on "smallest print job first" in order to improve the response for small jobs. A large job on a busy system may never print and thus starve

Q3: Describe the four conditions required for deadlock to occur.

• Mutual exclusion condition
• Hold and wait condition
• No preemption condition
• Circular wait condition

Q4*: Describe four ways to prevent deadlock by attacking the conditions required for deadlock.

• Mutual exclusion condition
  • Make the resource sharable, i.e. allow concurrent access to read-only files. However, in general some resources are not shareable and require mutual exclusion.
• Hold and wait condition
  • Dictate only a single resource can be held at any time. Not really practical.
  • Require that all required resource be obtained initially. If a resource is not available, all held resources must be releases before trying again.
• No preemption condition
  • Preempt the resource (take it away from the holder). Not always possible.
• Circular wait condition
  • Order the resources numerically and request them in numerical order.

Q5: Answer the following questions about the tables.

1. Compute what each process still might request and display in the columns labeled "still needs".
2. Is the system in a safe or unsafe state? Why?

   Safe, feasible schedule p1,p4,p5,p2,p3

3. Is the system deadlocked? Why or why not?

   No. There are not process remaining after the feasible schedule p1,p4,p5,p2,p3

4. Which processes, if any, are or may become deadlocked?

   None

5. Assume a request from p3 arrives for (0,1,0,0)
   • Can the request be safely granted immediately?

     No

   • In what state (deadlocked, safe, unsafe) would immediately granting the request leave the system?

     Unsafe

   • Which processes, if any, are or may become deadlocked if the request is granted immediately?

     p2, p3

	current allocation				maximum demand				still needs
process	r1	r2	r3	r4	r1	r2	r3	r4	r1	r2	r3	r4
p1	0	0	1	2	0	0	1	2	0	0	0	0
p2	2	0	0	0	2	7	5	0	0	7	5	0
p3	0	0	3	4	6	6	5	6	6	6	2	2
p4	2	3	5	4	4	3	5	6	2	0	0	2
p5	0	3	3	2	0	6	5	2	0	3	2	0

Threads

Q6: Compare cooperative versus preemptive multithreading?

Cooperative multithreading is where the running thread must explicitly yield() the CPU so that the dispatcher can select a ready thread to run next. Preemptive multithreading is where an external event (e.g. a regular timer interrupt) causes the dispatcher to be invoked and thus preempt the running thread, and select a ready thread to run next.

Cooperative multithreading relies on the cooperation of the threads to ensure each thread receives regular CPU time. Preemptive multithreading enforces a regular (at least systematic) allocation of CPU time to each thread, even when a thread is uncooperative or malicious.

Q7: Describe user-level threads and kernel-level threads. What are the advantages or disadvantages of each approach?

User-level threads are implemented in the application (usually in a "thread library"). The thread management structures (Thread Control Blocks) and scheduler are contained withing the application. The kernel has no knowledge of the user-level threads.

Kernel threads are implemented in the kernel. The TCBs are managed by the kernel, the thread scheduler is the normal in-kernel scheduler.

• User threads are generally faster to create, destroy, manage, block and activate (no kernel entry and exit required).
• If a single user-level thread blocks in the kernel, the whole process is blocked. However, some libraries (e.g., most UNIX pthreads libraries) avoid blocking in the kernel by using non-blocking system call variants to emulate the blocking calls.
• User threads don't take advantage of parallelism available on multi-CPU machines.
• Kernel threads are usually preemptive, user-level threads are usually cooperative (Note: some user-level threads use alarms or timeouts to provide a tick for preemption).
• User-level threads can be implemented on OSes without support for kernel threads.

Q8: Describe a plausible sequence of activities that occur when a timer interrupt results in a context switch.

• The interrupt generates an interrupt (exception) which transfers control to the kernel-mode handler.
• The handler switches to the kernel stack base for the current process.
• It saves the user-level state (registers, sp, ip) on the stack
• It determines a timer interrupt occurred and calls the timer interrupt handler.
• The handler acknowledges the interrupt
• It calls the dispatcher (scheduler).
• The scheduler chooses a new process to run.
• The current in-kernel context is saved on the kernel stack, the sp stored in the PCB (or TCB).
• The new process's sp is loaded; the new kernel stack base is substituted for the old processes' stack base.
• The new processes' kernel context is restored.
• It returns to the assembly routine to restore the user-level state.
• The user-state of the new process (as opposed to the old) is restored.

Page last modified: 7:24pm on Sunday, 5th of April, 2009

Print Version