theory and practice

Question 1

• Mutual exclusion problem

Answer 1

In many computer systems, processes must cooperate with each other when accessing shared data. The designer must ensure that only one process at a time modifies the shared information. During the execution of such critical sections of code mutual exclusion must be ensured.

Question 2

• Producer-Consumer problem

Answer 2

In this problem a set of producer processes provide messages to a set of consumer processes. They all share a common pool of space into which messages may be placed by the producers and removed by the consumers.

Question 3

• Reader-Writer problem

Answer 3

In this problem reader processes access shared data but do not alter it while writer processes change the contents of the shared data. Any number of readers should be allowed to proceed concurrently in the absence of a writer, but writers must insist on mutual exclusion while in their critical section.

Question 4

SEMAPHORE

Answer 4

A semaphore is an integer variable, S, and an associated group of waiting processes, Q(S), upon which only two operations, P and V , may be performed.

P (S) if S ≥ 1 then S = S − 1 else the executing process places itself in Q(S) and goes to sleep.

V (S) if Q(S) is non-empty then wake up one waiting process and make it available for execution else S = S + 1.

Question 5

circular hold and wait:

Answer 5

• circular hold and wait: There must exist a set of waiting processes {p1, p2, . . . , pn}
  such that p1 is waiting for a resource held by p2, p2 is waiting for a resource that is
  held by p3, . . ., pn is waiting for a resource that is held by p1. The resources involved
  must be held in a non-sharable mode

Question 6

deadlock

Answer 6

A set of processes is in a state of deadlock when every process in the set is waiting for a resource that can only be released by another process in the set

Question 7

linear ordering

Answer 7

To do this one must define a 1 − 1 function F that maps resource types to integer numbers.suppose that we insist that each process can only request resources in increasing order of enumeration. To do this we require that whenever a process requests a resource rj it first releases any resource ri such that F (ri) > F (rj ). If this protocol is followed then a circular hold and wait condition cannot happen.

Question 8

Bankers algorithm

Answer 8

ensures that a circular hold and wait condition cannot occur by demanding that at any time the system is in a safe state. More formally, a system of processes is in a safe state if there exists a sequence, {p0, p1, . . . , pn−1} such that for each pi the resources which pi can still request can be satisfied by the available resources plus the resources held by all the pj with j < i

Question 9

preemption

Answer 9

To prevent the hold and wait condition we allow implicit preemption. If a process that is holding some resources requests another resource that cannot be immediately allocated to it then all resources currently held are preempted and implicitly released. The preempted
resources are added to the list of resources for which the process is waiting. The process will only be restarted when it can regain all its old resources as well as the new one that it requested