Solved Mid Term Paper CS703 (Advance Operating Systems )
1 CS-703 Advance Operating Systems Virtual University of Pakistan
Question 1
A total of how many processes would be created in the function fork test () given below, excluding the main process that called fork test()? How many times will “Whatsup” be printed. Briefly explain your answer.
void fork_test( ) {
if (fork() != 0) {
if (fork() != 0)
fork();
else
printf(“Hello 1 \n”);
} else {
if (fork() != 0) {
printf(“Hello \n”);
} else {
fork();
}
}
printf("Whatsup \n");
}
Answer:
Five process create in this process excluding the fork test (). Whatsup line prints six times in this coding because each process print this line. fork test () method contain (fork()!=0) condition that is false in case of child process because child process fork() return 0 value. This condition is true for parent process because it return non zero value. If it return -1 then it contain error. First we consider parent process. It enter to this method and then check again condition that is false for child process and true for parent process. Parent process again call fork() method and make child process. Second (fork()!=0) condition that is false for child process run else portion of if condition and print hello line. Now we consider child process of 1st condition (fork()!=0) that is false for child process so we come to the else portion. In the else portion there is another (fork()!=0) condition. That is true for parent so parent process print hello line and this condition false for child process so it come to else portion and call fork() method and make child process. At the end each process print Whatsup line. As we know that is 6 process so it print 6 times Whatsup line
Question 2
Describe what problems would happen when multiple threads will execute the following C statement; also justify your answer with proper reasons.
{
static int I;
I++;
}
Answer:
1. Incorrect ordering: When two thread increment the counter but the result is 1 instead 2.
2. Concurrence issues: when executing static methods concurrently are static fields, which only exist one time. So, if the method reads and writes static fields, concurrence issues can occur In concurrent environment two or many threads can run concurrently, if all threads are trying to update some shared resource concurrently, there might be chance that threads trying to read shared resource get stale data and produce wrong outputs.
2 CS-703 Advance Operating Systems Virtual University of Pakistan
3. Deadlock problem: A deadlock occurs when each of two threads tries to lock a resource the other has already locked. Neither thread can make any further progress. Deadlock occur when two of many thread are waiting for two or more resources, where each thread need to get access on all resources to progress and those resources are acquired by different threads and waiting for other resources to be release, which will not be possible ever. For example, two threads A and B need both resources X and Y to perform their tasks. If thread A acquires resource X and thread B acquires Y and now both threads are waiting for resources to be release by other thread. Which is not possible and this is called deadlock. You need to take care of the way of your synchronization if this is going to be a cause of deadlock.
4. Race condition problem: A race condition is a bug that occurs when the outcome of a program depends on which of two or more threads reaches a particular block of code first. Running the program many times produces different results, and the result of any given run cannot be predicted. In a multithreaded application, a thread that has loaded and incremented the value might be preempted by another thread which performs all three steps; when the first thread resumes execution and stores its value, it overwrites objCt without taking into account the fact that the value has changed in the interim. When writing multi-threaded applications, one of the most common problems experienced are race conditions. A race condition occurs when two or more threads can access shared data and they try to change it at the same time. Because the thread scheduling algorithm can swap between threads at any time, you don't know the order in which the threads will attempt to access the shared data. Therefore, the result of the change in data is dependent on the thread scheduling algorithm, i.e. both threads are "racing" to access/change the data A "race condition" exists when multithreaded (or otherwise parallel) code that would access a shared resource could do so in such as way as to cause unexpected results.
5. Visibility problem: Visibility of shared object could be different for different threads. This is one of the problems of multi-threading environment. Suppose there are two threads, one is writing any shared variable and other is reading from shared variable. When reading and writing will be occur in different threads, there is no guarantee that reader thread will see the value written by writer thread. This problem of multi-threading is known as visibility issue of shared resource. This problem can be resolved with proper synchronization of shared resource.
Question 3 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 :
Class ReaderWriterLock
{
Semaphore mutex = 1; // declaration of a semaphore
OkToRead = 0; // a flag to check it is OK to read the database
OkToWrite = 0; // a flag to check it it is OK to write the database int
ACTIVEREADERS=0; // number of readers holding the read lock and accessing the DB
WAITINGREADERS=0; // number of readers waiting to acquire read lock
ACTIVEWRITERS=0; // number of writers that have acquired write lock
// (practically this will always be 1)
WAITINGWRITERS=0; // number of writers that are waiting for write lock 3 CS-703 Advance Operating Systems Virtual University of Pakistan
void AcquireReadLock() {
P(mutex); //remember that P operation on a semaphore means decrement value
if ((ACTIVEWRITERS == 0) {
V(OkToRead); // remember that V operation on a semaphore
means incrementing its value
ACTIVEREADERS++;
} else {
WAITINGREADERS++;
}
V(mutex);
P(OkToRead);
}
void ReleaseReadLock() {
P(mutex);
ACTIVEREADERS--;
if ((ACTIVEREADERS == 0) && (WAITINGWRITERS > 0)) {
V(OkToWrite);
ACTIVEWRITERS++;
WAITINGWRITERS--;
}
V(mutex);
}
void AcquireWriteLock() {
P(mutex);
If (ACTIVEWRITERS + ACTIVEREADERS == 0) {
V(OkToWrite);
ACTIVEWRITERS++;
} else {
WAITINGWRITERS++;
}
V(mutex);
P(OkToWrite);
}
void ReleaseWriteLock() {
P(mutex);
ACTIVEWRITERS--;
if (WAITINGWRITERS > 0) {
V(OkToWrite);
ACTIVEWRITERS++;
WAITINGWRITERS--;
} else {
while (WAITINGREADERS > 0) {
V(OkToRead);
ACTIVEREADERS++;
WAITINGREADERS--;
}
}
V(mutex);
} } // end of class 4 CS-703 Advance Operating Systems Virtual University of Pakistan
(a) Briefly explain why AcquireReadLock() and AcquireWriteLock() functions perform P and V operations on the mutex semaphore in the above code?
Answer:
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) Briefly explain whether readers or writers could be starved due to this implementation?
Answer:
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) 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.
Answer:
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. 5 CS-703 Advance Operating Systems Virtual University of Pakistan
Question 4: 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.
Answer:
Reader () {
lock.Acquire();
while (AW > 0) {
WR++;
okToRead.wait(&lock);
WR--;
} // while
AR++;
lock.Release();
Access DB
lock.Acquire();
AR--;
If (WR > 0) {
okToRead.Broadcast(&lock);
} else if (AR == 0 & WW > 0) {
okToWrite.Signal(&lock);
}
lock.Release();
}
Writer () {
lock.Acquire();
while ((AR + WR + AW) > 0) {
WW++;
okToWrite.Wait(&lock);
WW--;
}
AW++;
lock.Release();
Access DB
lock.Acquire();
AW--;
If (WR > 0)
okToRead.Broadcast(&lock);
else if (WW > 0)
okToWrite.Signal(&lock)
lock.Release(); }
}
Question 5: Which are the necessary conditions to hold the deadlocks?
Answer:
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
6 CS-703 Advance Operating Systems Virtual University of Pakistan
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.
Question 6:
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.
Question 7:
How is it possible to prevent the deadlocks?
Answer:
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.
Question 8:
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. 7 CS-703 Advance Operating Systems Virtual University of Pakistan
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.
Question 9:
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. An 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.
Question 10:
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
Question 11:
Consider the following processes and their related information:
Process Arrival Time Burst Time Priority
P1 0 5 4
P2 2 8 2
P3 4 9 5
P4 6 7 1
P5 8 6 3
Use the appropriate information from the above given. Calculate response time, Waiting Time, and turnaround time and draw the Gant charts for following scheduling algorithms:
|
1. First come first Serve P1
|
P2
|
P3
|
P4
|
P5
|
|||||
|
0
|
5
|
13
|
22
|
29
|
35
|
||||
No comments: