OPERATING SYSTEM IMPORTANT QUESTION ANSWER Part 2

OPERATING SYSTEM IMPORTANT QUESTION ANSWER PART 2

for IGNOU BCA MCA Students

22. What is the producer consumer problem? Give an example of its occurence in operating systems.

The producer-consumer problem is a idea where two threads exist, one is "producing" data to store in the buffer and the other is "consuming" that data from said buffer. Concurrency problems arise when we need to keep track of the number of items in the buffer, which has a fixed limit on how many items can be inside it at any one time.

23. A semaphore is a blocking synchronisation primitive. Describe how they work with the

aid of pseudo-code. You can assume the existance of a thread_block() and a thread_wakeup()

function.

Semaphores work by blocking processes with P, calling thread_block(), waiting for a resource if it is not available, then being put into a queue of processes that want to access this resource. This is more efficient than other solutions because we avoid busy waiting – other processes can do other things while blocked ones are in the queue! When a resource is released, V is run, which calls thread_wakeup() to signal the next thread to use it. See:

typedef struct _semaphore {

int count;

struct process *queue;

} semaphore;

semaphore sem;

void P(sem) {

sem.count--;

if (sem.count < 0) {

/* add process to sem.queue */

thread_block();

}

}

void V(sem) {

sem.count++;

if (sem.count <= 0) {

/* remove a process from sem.queue */

thread_wakeup();

}

}

24. Describe how to implement a lock using semaphores.

You place a P(mutex) before writing to a critical variable, then a V(mutex) to signal that the operation is complete so that other processes may have their turn.

25. What are monitors and condition variables?

Monitors are a higher level synch primitive that takes the form of a data type, in which the compiler defines mutual exclusion. When a thread calls a monitor which is already used, it is queued and sleeps until the monitor is free again – very much like a semaphore, but needs to be defined beforehand as part

of the OS. A  condition variable is a wait() and signal() primitive for monitor functions.

26. What is deadlock? What is startvation? How do they differ from each other?

Deadlock is the phenomenon that arises when a number of concurrent processes all become blocked waiting for another thread to make available a resource, but it can only be released by a thread that is still blocked. Starvation is the phenomenon which arises when a process does not ever receive the resource it is waiting for, even if it repeatedly becomes available, as it is always allocated to another waiting process.

  Processes halt in deadlock becayse they cannot proceed and the resources are never made available.                           Therefore, no progress can be made. With starvation, progress is made overall at the expense of a      particular process or processes, which consistently miss out on being allocated their requested resource.

27. What are the four condtions required for deadlock to occur?

The four conditions required for deadlock to occur are:

Mutual Exclusion – the processes must be trying to access the same resource at the same time Circular Wait – the processes exist in a circular chain, where each is waiting for the resource held by the next member of the chain.

Hold & Wait – process holds a resource, DOESN'T GIVE IT BACK, and blocks because it's waiting for

More No Preemption – resource can't be forcibly taken from the process holding it

28.  Describe four general strategies for dealing with deadlocks.

Ignorance – If deadlocks are not liable to happen, the effort required to deal with them outweighs the problem of deadlocks actually occurring.

Detection and Recovery – Keep log of resource ownership and requests. If no progress is made, recover from said deadlock by pre-emption (steal a resource from another process), rollback (make checkpoints – but operating systems aren't Halo or Call of Duty, this is difficult), or crudely killing

processes in the deadlock cycle.

Deadlock Avoidance – The most difficult option. We disallow deadlock by setting "safe states", in which

process completion is always guaranteed.

Deadlock Prevention – Negate one of the four deadlock conditions. Most commonly we deal with the

circular wait condition. Attacking mutex is infeasible, attacking hold and wait is prone to starvation, and attacking no preemption is downright idiotic.

29. For single unit resources, we can model resource allocation and requests as a directed graph connecting processes and resources. Given such a graph, what is involved in deadlock detection.

We detect deadlocks by finding closed loops in the graph, where two or more processes requesting resources are held by other processes.

30. Is the following system of four processes with 2 resources deadlocked?

Current allocation matrix

P1	1	3
P2	4	1
P3	1	2
P4	2	0

Current request matrix

P1	1	2
P2	4	3
P3	1	7
P4	5	1

Availability Vector

1              4

Process 1 uses 1 of resource 1, 2 of resource 2, making the availability vector 0 2.

It then runs to completion, freeing all its resources, making the availibility vector 2 7. Process 3 uses 1 of resource 1, 7 of resource 2, making the availability vector 1 0.

It then runs to completion, freeing all its resources, making the availability vector 3 9. The only processes left are  P2 and P4 – the system is deadlocked because we don't have enough of resource 1 – P2 wants 4, and P4 wants 5 – but we only have 3.

If the availability vector is as below, is the system above still deadlocked?

2              3

Is the system deadlocked if the availability is

2               4

31. Assuming the operating system detects the system is deadlocked, what can the operating system do to recover from deadlock?

The operating system can recover from deadlock by:

- Killing the deadlocked process (crude, and requires that it will be restarted)

- Rolling Back (going back a few instructions until it can enter a non-deadlocked state, and retry)

- Pre-emption (forcing the handing over of a resource to another process, at the expense of the one it's currently deadlocked on)

32. What must the banker's algorithm know a priori in order to prevent deadlock?

The banker's algorithm must calculate whether giving a process a resource will lead to a safe state or not. In order to work, it must know how many resources the process in question may be granted at any one time, and how many resources the OS is able to give. This is difficult because how can we know what future requests might be?

  To see if a state is safe – the algorithm checks to see if enough resources exist to satisfy a process. If

so, the "loans" are assumed to be "repaid".

33. Describe the general strategy behind deadlock prevention, and give an example of a practical deadlock prevention method.

Deadlock prevention is theorised on the basis that if one nullifies one of the four conditions for deadlock to occur (mutual exclusion, hold and wait, circular wait and no preemption), a deadlock cannot occur. Attacking mutual exclusion and no preemption has no practical basis, so we commonly prevent the circular wait condition. We do this by globally numbering all resources. (e.g. Blu-Ray drive #1 and USB Hard Drive #2). At every instant – one of the processes will have the highest numbered resource. The process holding it will never ask for a lower one, because we only allow processes to access higher numbered resources. Eventually it will finish and free all its resources. All processes can finish.