CS703 - Advanced Operating Systems
Course Page
Mcqs
Q & A
Video
Downloads
Short Question & Answers
Q20: Write a resource allocation algorithm which will prevent deadlock.
Following algorithm will p revent the deadlock:
P processes are requesting for r resources. Resource allocation algorithm does the following:
If (process P has ever acquired any resources before)
{
        Do not serve the request;
}
Else if (no resource is remaining)
{
      Do not serve the r equest;
}
Else
{
    If (no resource is free)
   {
       Wait until all resources r are free;
   }
   Grant process P individual access to r resources;
}
Q21: How should threads coordinate? And how should they wait for an event or state change?
A thread, while holding the lock, may change the variables constituting the condition expression. It should then call signals to notify a single waiting thread to resume execution or broadcast to wake all waiting threads. Signal and broadcast move waiting threads off the condition variable’s queue and queue them on the associated lock. Only after the signaling/broadcasting thread releases the lock may these threads resume execution. However, it is possible that other threads were previously waiting on the lock, so the waiting threads are not guaranteed that the condition expression is true. Rather, returning from wait is considered a hint that expression may have become true. After resuming, the thread must test the expression again before proceeding. Hence, threads commonly wait within a while loop that tests the condition expression
Q22: What are conditional critical regions? What are their limitations? And how can we overcome these limitations.
Conditional critical regions are the regions in a program that must be executed distinctly by one process and no other process can execute that region at the same time. When we use condition variables for locking purposes then the critical regions are referred to as conditional critical regions. The limitations of conditional critical region are:  With conditional critical regions, waiting occurs without any changes to shared state.  The resource concept is unreliable  The context switching is inefficient  The scheduling mechanism is too restrictive  These limitations can be removed using conditional variables.
Q23: What are condition variable? What are their limitations? And how can we overcome these limitations?
Condition variable are queues of waiting threads. Condition variables support three operations: wait, signal and broadcast. Logically, every condition variable is associated with one (or more) Boolean condition expressions and a mutex lock. Condition variables are used to complement locks by allowing a program to specify the order of execution. There are two limitations for condition variables: (1) the signal operation is explicit, so a programmer may forget to call signal when changing shared state, (2) condition variables do not nest within multiple levels of mutex locks because only the inner-most lock is released when waiting. As a result, deadlock may result if the blocked thread can only be woken by code that acquires a lock still held by the waiting thread. These limits are removed when we use conditional variables with transactional memory.
Q24: What is lost wakeup problem and how can it be resolved?
Signaling or broadcasting transaction may execute concurrently with a transaction that it woke up. If the waking transaction completes before the signaling transaction, it is called wakeup problem. The waking transaction may view shared state from before the signaling transaction, and hence before the logical condition it awaits is visibly changed. The wakeup problem may be resolved by deferred signal approach, or by speculative signal approach
Q25: What are the requirements and implications for the discussed two implementations of condition variables for transactional memory?
The requirements and implications for deferred signal approach are Commit Actions The requirements and implications for Speculative signal approach are Escape Actions, and Robust Conflicts Detections
Q26: Explain, in your own words, how the proposed approach manages to avoid deadlocks when unstructured locking is used.
The proposed approach says that the deadlock cannot occur when we have the requested lock and its future lock set. The future lockset is the set of locks when the lock is requested and all locks in between till a matching unlock is found. The proposed approach starts by tracking the simple effects. Simple effects may be the empty sequences of locks and unlocks events. Proposed approach uses a continuation effects i.e. the effect of code to its following expression. The proposed approach has the feature to add notes to the lock operation according to their continuation effects.

The continuation effects are calculated statically, but the future lock sets are computed at run time. When a function is called the continuation effects is pushed on to the stack up to the time the call is not fully executed. During the continuation effect, the locks are identified and added to the lock set. At runtime the lock operation unblocks whenever we find a lockset. This assists to avoid deadlocks. The proposed approach gives only a single lock to every lock operation, this increase the degree of parallelism.

Now let us see constitutes of the proposed approach and its implementation in various programming language constructs.

Effects: Simple effects may be the empty sequences of locks and unlocks events. Continuation effect i.e. the effect of code to its following expression. Notes are added to the lock operation according to their continuation effects. The continuation effects are calculated statically, but the future lock sets are computed at run time. When a function is called the continuation effects is pushed on to the stack up to the time the call is not fully executed. During the continuation effect, the locks are identified and added to the lock set. At runtime the lock operation unblocks whenever we find a lockset. This assists to avoid deadlocks. The proposed approach gives only a single lock to every lock operation, this increase the degree of parallelism. The runtime system utilizes the dynamically computed future locksets so that each lock operation can only proceed when its future lockset is available to the requesting thread.

Function Calls: As we know that the continuation approach is intra-procedural so the unlock operation for a lock operation may not reside in the same function. This problem is resolved by adding the notes to function call according to the continuation effect. As static analysis says ensures that there is always an unlock operation for a lock, so the algorithm traverse the lockset and find the matching unlock terminates.

Conditionals: A demerit defining effects as ordered events is that, in case of conditional expressions/statements, it becomes less likely that the branches will have the same effect. Proposed approach can deal with it. Proposed approach traversed each branch and keep tracks of each branch, and algorithms calculates the lockset for each branch individually.

Loops and recursions: loops and recursions introduce additional problems. In the case of recursion and loops, function and its body name must express the same name. But this is no possible, due to the reason that the two effects cannot be structure-wise equivalent: the effect of a function name is contained in the effect of its body, due to the recursive call. To handle this problem, a summary is tagged to the function names showing the effect of their bodies.
Course Instructor

Mr. Farhan Zaidi
MS Computer Science
University of Southern California, USA
Books

Modern Operating Systems by Tanenbaum

Operating Systems Internals and Design Principles by William Stallings

Operating Systems by Gary Nutt

Computer Systems: A programmer’s perspective
by Randal E. Bryant & David R.