CS703 - Advanced Operating Systems
Course Page
Mcqs
Q & A
Video
Downloads
Short Question & Answers
Q11: Reader/writer locks are specialized locks used to solve the readers/writers problem. Consider the following pseudo-code implementation of reader-writer locks which is a variant of the readers/writers solution discussed in lectures but implemented via semaphores. Note that readers must call the function AcquireReadLock before reading the data while writers must call AcquireWriteLock before modifying or updating the data. Once data access has been completed, the locks must be released by calling the ReleaseReadLock() and ReleaseWriteLock() functions respectively :

(a) Briefly explain why AcquireReadLock() and AcquireWriteLock() functions perform P and V operations on the mutex semaphore in the above code?

(b) Briefly explain whether readers or writers could be starved due to this implementation?

(c) Suggest a mechanism through which a no starvation policy could be implemented. In other words, suggest in words, how would you modify the code such that a starvation-free implementation results.
(a) Both AcquireReadLock() and AcquireWriteLock() functions perform P and V operations for mutual exclusion on mutex semaphore. As we know P operation on a semaphore means decrementing its value and V operation on a semaphore means incrementing its value . P() make mutex value zero so that no one can enter in critical section. And when reader or writer out from the critical section then they perform v() on mutex and makes its value 1 so that other reader or writer can access.

(b) Yes, reader and writer both can face starvation. Reader starvation In ReleaseWriteLock() function When writer out it give priority to waiting writers as:

if(WAITINGWRITERS>0) {
    V(OkToWrite);
    ACTIVEWRITERS++;
    WAITINGWRITERS--;
}

So reader starvation occur.
Writer starvation AcquireReadLock() function when if condition will be false then else part execute and priority will be given to waiting reader. In other word when active writer not equal to zero because there are some writer then it is necessary to allow writer to access but in the given code priority is given to waiting reader.

if((ACTIVEWRITERS==0) {
    V(OkToRead);
    ACTIVEREADERS++;
} else {
    WAITINGREADERS++;
}

So writer starvation occur.

(c) To remove writer starvation we need to modify if condition in the AcquireReadLock() function as: if(ACTIVEWRITERS+WATINGWRITERS==0).

To remove reader starvation we need to modify the code in a way when fix number of writer access the database after this reader can access. Or when waiting readers increase from their fix limit then reader can access.
Q12: Review the Readers/Writers problem discussed in lecture 12, write the code for Reader() and Writer() functions, when readers are given priority over writers, keeping the problem constraints in mind.
Q13: Which are the necessary conditions to hold the deadlocks?
There are four necessary conditions and all four of them must hold simultaneously for a deadlock to occur. There conditions are Mutual Exclusion, Hold & Wait, No preemption and Circular Wait.

I. Mutual Exclusion means that there must be at least one resource which can only be used by a single process at a time i.e. non-shareable mode. If any other process request for this resource, the requesting process must be delayed until the requested resource is released by the process already using it.

II. Hold and Wait means that a process is holding at least one resource and waiting for other resource(s) which is/are held by other process(es).

III. No preemption means that none of the processes can be forced to release the resources which are being held by them i.e. the processes will released the resources voluntarily.

IV. Circular Wait. There must be a set of processes which are waiting for resources which are being held by the other process. E.g. P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on upto Pn, and Pn is waiting for a resource held by P1.
Q14: Draw a resource graph to show the deadlock condition.
Following resource graph shows the deadlock condition. Here are three process P1, P2, P3 and four different Resources R1, R2, R3 and R4 each having 1, 1, 2 and 3 instances respectively (shown by filled circles inside resource rectangles).

Process requesting for an instance of resource is represented by directed edge from Process Pi to Resource Rj. Similarly, directed edge from resource instance towards any Process Pi represents that that particular instance of Resource Rj is allocated to Process Pi.

The graph shows that there are two cycles in this graph i.e.
P1 → R1, R1 → P2, P2 → R2, R2 →P3, P3 →R3, R3 →P1
and P2 →R2, R2 →P3, P3 →R3, R3 →P2

None of the processes will release the resources that it has already acquired and all of these three will remain in deadlock state.
Q15: How is it possible to prevent the deadlocks?
There are four necessary conditions which must hold simultaneously for a deadlock to occur. So, deadlock can be prevented by implementing some methodology that guarantees that at least one of the four necessary conditions must not hold. By implementing this kind of strategy, it is possible to prevent a deadlock from occurring.

Relaxing first three conditions i.e. Mutual exclusion, Hold & wait, and no pre-emption are not always useful. There may be low utilization of resources & starvation.

Circular Wait is the ultimate choice. This is the most suitable condition i.e. ensuring that circular wait never holds. Simple methodology used for this purpose is order all the resources and each process always requests resources in increasing order. Hence, there may never be a process waiting for a low numbered resource holding a higher numbered resource, ensuring that occurrence of cycle is impossible. So, implementing that there will be no circular wait, deadlocks can be prevented.
Q16: Why it is considered that threads are harmful?
Threads are a difficult thing to handle for most programmers. Bugs can be introduced easily by the programmers while using threads and the most annoying this is that these are hard to find and even harder to fix. The things are painful for experts, so inexperienced programmers consider threads harmful.

While synchronization, it is required that threads must coordinate access to shared data with proper locks and missing a lock results in corruption of data. Threads also cause deadlocks if used inefficiently, carelessly. Main purpose of usage of threads is concurrency, but this is hard.

Hence threads are considered harmful and are avoided by normal programmers.
Q17: Could you give some reasons to use the threads in a beneficial way?
Threads can be used for concurrency. Responsiveness of applications is increased.

Threads should be used with care to increase responsiveness. Performance and utilization of multi-core, multi CPUs is increased with multiple threads running on multiple CPUs, each thread running in parallel on a different processor. Efficiency of high-end servers is increased.

Threads share memory and resources of the process to which they belong. Code sharing in allows an application to have several different threads of activity, all within the same address space.
Q18: Which are the classical issues related to the threads?
Synchronization & Deadlocks are issues to the threads and the classical problems are:
1. Bounded Buffer Problem
2. Readers and Writers Problem
3. Dining Philosophers Problem
Q19: There are p processes competing for r identical resource units. Each process needs a maximum of m resource units (where m ≤ r).
(a) Under what condition can no deadlock occur?
(b) Give an example of a request sequence leading to deadlock.
(a) Under following condition or rule, no deadlock occurs:

• Don’t allocate any more resource to a process if the process is already using some resources. Let that process consume and release those resources first.

• If all the resources are consumed and further request comes, do not put the requesting process go into wait state. Let them consume and release pre-acquired resources first.

(b) Suppose that all the resources have been allocated to P processes or a subset of P processes i.e. P1, P2… Pn.

P1 needs one more resource, but no more resource is available, P1 goes into waiting.

P2 needs one more resource, but no more resource is available, P2 goes into waiting.

P3 needs one more resource, but no more resource is available, P3 goes into waiting.
.
.
Pn needs one more resource, but no more resource is available, Pn goes into waiting.

At this point all the processes are collectively holding all the resources, all the processes are in wait state, no process will release the acquired resources. So the deadlock occurs here.
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.