CS703 –
ADVANCED OPERATING SYSTEMS
MS (CS),
SPRING 2015
ASSIGNMENT
NO. 2 Due
Date: 11th June, 2015
SOLVED BY
Muhammad Sadaqat Ali
Question 1
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 database
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
void AcquireReadLock()
{
P(mutex); // remember that P operation on a semaphore means
decrementing its 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
a)
Briefly explain why AcquireReadLock() and AcquireWriteLock()
functions perform P and V
operations on the mutex semaphore in the above code?
Solution:
A semaphore is a protected variable whose value can be
accessed and altered only by the operations P and V.
When semaphore operations has started, no other process can
access the semaphore until operation has completed. Mutual exclusion on the
semaphore is enforced within P and V.
P semaphore function signals that the task requires a
resource and if not available waits for it.
V semaphore function signals which the task passes to the OS
that the resource is now free for the other users.
In the above code, P and V semaphore functions used with
mutex property.
For AcquireReadLock() :
P and V Semaphore functions with mutex property ─ Wait for
starting Critical Section
P(mutex); // remember that P operation on a semaphore means
decrementing its value
The codes will
execute only when mutex not less than 0. it keep wait until the resource become
available for further processing.
P and V Semaphore functions with mutex property ─ running
end exiting Critical Section
V(OkToRead); // remember that V operation on a semaphore
means incrementing its value
if OkToRead not equal
to 0 or not less than 0. No other process is executing at present. Now reader
can access DB.
V(mutex);
mutex not equal to 0 or not less than 0. No processor
(reader) process executing at present.
P(OkToRead);
The following codes will execute only when OkToRead not less
than 0. Wait for Reader.
For AcquireWriteLock():
P(mutex);
The codes will execute only when mutex not less than 0. it
keep wait until the resource become available for further processing.
V(OkToWrite);
if OkToWrite not equal to 0 or not less than 0. No other process
is executing at present. Now writer can access DB.
V(mutex);
mutex not equal to 0 or not less than 0. No processor
(writer) process executing at present.
P(OkToWrite);
The following codes will execute only when OkToWrite not
less than 0. Wait for Writer.
(b)
Briefly explain whether readers or writers could be starved
due to this implementation?
Solution:
In this code, Writer could be starved as the priority is
given to Reader.
In the function, void ReleaseWriteLock(), implementation for
WaitingReader gives access to ActiveReader and if waitingwriter available, only
access given to ActiveWriter and then instead of accessing DB to waiting writer
access is given to Reader.
Thus, Writer could be starved.
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.
Solution:
To get starvation free implementation results, we can use
any scheduling algorithm as the task of the scheduler is to find a conflict
free matching based on input requests.
Four major scheduling algorithm are:
First Come
First Serve FCFS Scheduling
Shortest Job
First Scheduling
Priority
Scheduling
Round Robin
Scheduling
Multilevel
Queue Scheduling
All these algorithm have their own advantages and
disadvantages.
Question 2
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.
Solution:
Reader () {
lock.Acquire();
while (AW > 0) {
WR++;
okToRead.wait(&lock);
WR--;
}
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();
}