Operating System [Algorithms]
Q. Producer - Consumer Problem
Ans:
The code for the producer process can be modified as follows:
while (true)
{
/* produce an item in nextProduced */
while (counter == BUFFER.SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER-SIZE;
counter++;
The code for the consumer process can be modified as follows:
while (true)
{
while (counter == 0)
; /* do nothing */
nextConsumed = buffer [out] ,-
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in nextConsumed */
}
Q. Peterson's Solution
Ans:
do {
flag[i] = TRUE;
turn = j ;
while (flag[j] turn == j ) ;
//critical section
flag[i] = FALSE;
//remainder section
} while (TRUE);
Q. The definition of the TestAndSet () instruction
Ans:
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = TRUE;
return rv;
}
Q. Mutual-exclusion implementation with TestAndSet ()
Ans:
do {
while (TestAndSetLock(&lock))
; // do nothing
// critical section
lock = FALSE;
// remainder section
}while (TRUE);
Q. The definition of the Swap () instruction.
Ans:
void Swap(boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
Q. Mutual-exclusion implementation with the Swap() instruction
Ans:
do {
key = TRUE;
while (key == TRUE)
Swap (&lock, &key);
// critical section
lock = FALSE;
// remainder section
}while (TRUE);
Q. Bounded-waiting mutual exclusion with TestAndSet ()
Ans:
do {
waiting [i] = TRUE;
key = TRUE;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting [i] = FALSE;
// critical section
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
}while (TRUE);
Q. The definition of wait () is as follows:
Ans:
wait(S) {
while S <= 0
; // no-op
S--;
}
Q. The definition of signal () is as follows:
Ans:
signal(S) {
S++;
}
Q. Mutual-exclusion implementation with semaphores
Ans:
do {
waiting(mutex);
// critical section
signal(mutex);
// remainder section
}while (TRUE);
Q. Implementation of Semaphore
Ans:
typedef struct {
int value;
struct process *list;
}semaphore;
The wait () semaphore operation can now be defined as
wait(semaphore *S) {
S->value—;
if (S->value < 0) {
add this process to S->list;
block();
}
}
The signal 0 semaphore operation can now be defined as #
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
Q. A Semaphore Solution to the Producer-Consumer Problem
Ans:
Initialization:
shared binary semaphore mutex = 1;
shared counting semaphore empty = MAX;
shared counting semaphore full = 0;
shared anytype buffer[MAX];
shared int in, out, count;
Producer:
anytype item;
do {
/* produce something */
item = produce();
/* wait for an empty space */
P(empty);
/* store the item */
P(mutex);
buffer[in] = item;
in = in + 1 mod MAX;
count = count + 1;
V(mutex);
/* report the new full slot */
V(full);
} while (TRUE);
Consumer:
anytype item;
do {
/* wait for a stored item */
P(full);
/* remove the item */
P(mutex);
item = buffer[out];
out = out + 1 mod MAX;
count = count - 1;
V(mutex);
/* report the new empty slot */
V(empty);
/* consume it */
consume(item);
} while (TRUE);
Q. Solution of Reader - Writter problem using semaphore
Ans:
Initialization:
semaphore mutex, wrt;
int readcount;
The structure of a writer process:
do {
wait(wrt);
// writing is performed
signal (wrt) ,-
}while (TRUE);
The structure of a reader process:
do {
wait(mutex);
readcount + + ;
if (readcount == 1)
wait(wrt);
signal(mutex);
...
// reading is performed
...
wait (mutex)
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
}while (TRUE);
Q. Syntax of Monitor
Ans:
monitor monitor name
{
// shared variable declarations
procedure P1 (. . .) {
...
}
procedure P2 (. . .) {
...
}
..
..
..
procedure Pn (. . .) {
...
}
initialization code (. . .) {
...
}
Q. Structure of Dining Philosoher Problem using Semaphore
Ans:
do {
wait (chopstick [i] ) ,-
wait(chopstick [ (i + 1) % 5] ) ;
...
// eat
signal(chopstick [i]);
signal(chopstick [(i + 1) % 5]);
// think
}while (TRUE);
Q. Solution of Dining Philosopher Problem using Monitor
Ans:
monitor dp
{
enum {THINKING, HUNGRY, EATING}state [5];
condition self [5] ;
void pickup(int i) {
state [i] = HUNGRY;
test (i) ;
if (state [i] != EATING)
self [i] .wait() ;
}
void putdown(int i) {
state [i] = THINKING;
test((i + 4) % 5} ;
test( (i + 1) % 5) ;
}
void test(int i) {
if ((state [(i + 4) % 5] != EATING) && (state [i] == HUNGRY) &&
(state [(i + 1) % 5] != EATING)) {
state [i] = EATING;
self [i] .signal() ;
}
initialization-code () {
for (int i = 0; i < 5; i++)
state [i] = THINKING;
}
}
Q. Solution of Producer Consumer Problem using Monitor
Ans:
monitor ProducerConsumer
condition full, empty;
int count;
procedure insert(item) {
if (count == MAX)
wait(full); // if buffer is full, block
insert_item(item); // put item in buffer
count = count + 1; // increment count of full slots
if (count == 1)
signal(empty); // if buffer was empty, wake consumer
}
procedure remove() {
if (count == 0)
wait(empty); // if buffer is empty, block
remove_item(item); // remove item from buffer
count = count – 1; // decrement count of full slots
if (count == MAX – 1)
signal(full); // if buffer was full, wake producer
}
count = 0;
end monitor;
procedure Producer() {
while (TRUE)
{
produce_item(item); // make a new item
ProducerConsumer.insert(item); // call enter function in monitor
}
}
procedure Consumer() {
while (TRUE)
{
ProducerConsumer.remove; // call remove function in monitor
consume_item; // consume an item
}
}
Q. Banker's Algorithm [Deadlock Avoidance]
Ans:
➔ Available. A vector of length m indicates the number of available resources of each type. If
Available[j] equals k, there are k instances of resource type Rj available.
➔ Max. An n x m matrix defines the maximum demand of each process. If Max[i][j] equals k, then
process Pi may request at most k instances of resource type Rj.
➔ Allocation. An n x in matrix defines the number of resources of each type currently allocated to
each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of
resource type Rj.
➔ Need. An n x m matrix indicates the remaining resource need of each process. If Need[i][j]
equals k, then process Pi may need k more instances of resource type Rj to complete its task.
Note that Need[i][j] equals Max[i][j] - Allocation[i][j].
Safety Algorithm
We can now present the algorithm for finding out whether or not a system is in a safe state. This
algorithm can be described, as follows:
1. Let Work and Finish be vectors of length in and n, respectively. Initialize
Work = Available and Finish[i] = false for i = [0 , 1 , ..., n - l].
2. Find an i such that both
a. Finish[i] == false
b. Needi <= Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true
Go to step 2.
4. If Finish[i] == true for all i, then the system is in a safe state.
Resource-Request Algorithm
We now describe the algorithm which determines if requests can be safely granted.
Let Requesti be the request vector for process Pi, If Request[i] == k, then process Pi, wants k
instances of resource type Rj. When a request for resources is made by process Pi, the following
actions are taken:
1. If Requesti <= Needi, go to step 2. Otherwise, raise an error condition, since
the process has exceeded its maximum claim.
2. If Requesti <= Available, go to step 3. Otherwise, Pi must wait, since the
resources are not available.
3. Have the system pretend to have allocated the requested resources to
process Pi by modifying the state as follows:
Available = Available - Requesti;
Allocationi, = Allocationi + Requesti;
Needi = Needi - Requesti;
Q. Deadlock Detection Algorithm
Ans:
➔ Available. A vector of length m indicates the number of available resources of each type.
➔ Allocation. An n x m matrix defines the number of resources of each type currently allocated to
each process.
➔ Request. An n x in matrix indicates the current request of each process. If Request[i][j] equals k,
then process Pi is requesting k more instances of resource type Rj.
1. Let Work and Finish be vectors of length in and n, respectively. Initialize
Work - Available. For i = 0 , 1 , . . . , n-1, if Allocation, not equal to 0,
then Finish[i]= false;
otherwise, Finisli[i] = true.
2. Find an index i such that both
a. Finish[i] == false
b. Requesti <= Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true
Go to step 2.
4. If Finish[i] == false, for some i, 0 < i < n, then the system is in a deadlocked state.
Moreover, if Finish[i] == false, then process Pi is deadlocked.
