# GATE1989-11a

992 views
1. A system of four concurrent processes, $P, Q, R$ and $S$, use shared resources $A, B$ and $C$. The sequences in which processes, $P, Q, R$ and $S$ request and release resources are as follows:

$$\begin{array}{ll} \text{ Process P: } & \text{1.}& \text{ P requests A } && \\ \text{ } & \text{2.}& \text{ P requests B } && \\ \text{ } & \text{3.}& \text{ P releases A } &&\\ \text{} & \text{4.}& \text{ P releases B } && \\ \text{ Process Q: } & \text{1.}& \text{ Q requests C } && \\ \text{ } & \text{2.}& \text{ Q requests A } && \\ \text{ } & \text{3.}& \text{ Q releases C } &&\\ \text{} & \text{4.}& \text{ P releases A } &&\\ \text{ Process R: } & \text{1.}& \text{ R requests B } \\ \text{ } & \text{2.}& \text{ R requests C } \\ \text{ } & \text{3.}& \text{ R releases B } &&\\ \text{} & \text{4.}& \text{ R releases C } &&\\ \text{ Process S: } & \text{1.}& \text{ S requests A } && \\ \text{ } & \text{2.}& \text{ S requests C } && \\ \text{ } & \text{3.}& \text{ S releases A } &&\\ \text{} & \text{4.}& \text{ S releases C } && \end{array}$$

If a resource is free, it is granted to a requesting process immediately. There is no preemption of granted resources. A resource is taken back from a process only when the process explicitly releases it.

Can the system of four processes get into a deadlock? If yes, give a sequence (ordering) of operations (for requesting and releasing resources) of these processes which leads to a deadlock.

1. Will the processes always get into a deadlock? If your answer is no, give a sequence of these operations which leads to completion of all processes.
2. What strategies can be used to prevent deadlocks in a system of concurrent processes using shared resources if preemption of granted resources is not allowed?

edited
0
I think there is a typo in the question in Process Q. It should be Q releases A instead of P releases A.

i) Assuming only one instance of a resource is available,

Process P: Hold A, request B

Process Q: Hold C, request A

Process R: Hold B, request C

Process S: Request A, request C

In this instance, Process P,Q,R and S are waiting for the release of resources among each other and none of them can proceed. This is deadlock.

ii) Any sequential ordering will be free from deadlock. An instance(concurrent) can be:

 Process P Process Q Process R Process S request A request B request C release A request A release C release B request B request C release A request A release B release C request C

All the requests of all processes are satisfied and leads to completion of all processes.

• Resources can be shared (violating mutual exclusion)
• Not allowing processes to hold a resource and request for another( violating hold and wait)
• Break circular wait by allocating resources in some order
• Banker's algorithm(safe state)- to avoid deadlock
0
Do we need Bankers algorithm for single instance resources?
6
No Sir, we can use resource-allocation graph.(for single instances of resource RAG can be easily converted to wait-for graph and if cycle exists in wait-for graph then deadlock exists)
6
Yes because bankers algorithm is more expensive.

processes, P,Q,R,S, and resources A,B,C

let process request resource :  P() and Process release resource : V()

P Q R S
P1(A) P2(C) P3(B) P4(A)
P1(B) P2(A) P3(C) P4(C)
V1(A) V2(C) V3(B) V4(A)
V1(B) V2(A) V3(C) V4(C)

Can the system of four processes get into a deadlock ?

Yes : P1(A) -> P2(C) -> P3(B) -> P4(A) busy wait -> P1(B) busy wait -> P2(A)  busy wait-> P3(C) busy wait

Will the processes always get into a deadlock ?

No  : any sequential execution of processes not going to Deadlock. Ex- PQRS.

strategies can be used to prevent deadlocks in a system :

1. there are 4 processes and each process is requesting to resources so we can allow maximum to processes at a  time                     until any process releases there resource.\

suggest some more strategies to prevent deadlocks in a system.

0
1.For not happening of mutual Exclusion we spool everything.

SPOOL means simultameous Peripheral Operations Online.Ex: Printer uses this technique but this is not preferable

2.For not Happening Hold and wait grant the resources before the process starts execution

But this method is not preferable because a Process do not come to know beforehand how many resources it needs.

3.For not happening Circular Wait number the resources in an increasing or decreasing order

So that a process will always requests resources of higher number.

Means if Process P1 wants R1 and R2 resources and Process Q should not come again resource R1.

Any of these conditions must be broken down to prevent deadlock.

Can the system of four processes get into a deadlock? If yes, give a sequence (ordering) of operations (for requesting and releasing resources) of these processes which leads to a deadlock.

Answer: YES...Process $Q\to R(C)$, Process $S\to R(A)$, Process $Q \to R(A)$ Process $S \to R(C)$ Process $P\to R(A)$, Process $R\to R(B)$ Process $R \to R(C)$

Will the processes always get into a deadlock? If your answer is no, give a sequence of these operations which leads to completion of all processes.

edited
0

@rishu_darkshadow Ans: NO....!!! PQRS - all are concurrent process so sequence is not possible

0
@arjun sir

0
Here what is meaning of  explicitly  release?
0
Explicit release in the sense, the process should release the resource by itself, for this purpose they used 'P releases B' convention, telling that the process P is releasing resource B.
1 vote
Can the system of four processes get into a deadlock? If yes, give a sequence (ordering) of operations (for requesting and releasing resources) of these processes which leads to a deadlock.

Ans: Yes . The system may leads to dead lock. Considering the sequence like

Process Q: R(c)  , Process S:R(A) ,Process Q : R(A) Process S :R(c) Process P: R(A) ,Process R: R(B) got it. , Process R : R(C) all of them in dead lock because none of them request not will fullfil.

(ii) Will the processes always get into a deadlock? If your answer is no, give a sequence of these operations which leads to completion of all processes.

Ans: The processs Q and S will always be in dead lock because they request resource in reverse order of each other..

(iii) What strategies can be used to prevent deadlocks in a system of concurrent processes using shared resources if preemption of granted resources is not allowed?

Ans: For this we need to change order of request of any Q or S process.

## Related questions

1
628 views
Consider the following precedence graph (Fig.6) of processes where a node denotes a process and a directed edge from node $P_{i}$ to node $P_{j}$ implies; that $P_{i}$ must complete before $P_{j}$ commences. Implement the graph using FORK and JOIN constructs. The actual computation done by a process may be indicated by a comment line.
Provide short answers to the following questions: Disk requests come to disk driver for cylinders $10, 22, 20, 2, 40, 6$ and $38$, in that order at a time when the disk drive is reading from cylinder $20$. The seek time is $6$ msec per cylinder. Compute the total seek time if the disk arm scheduling algorithm is. First come first served. Closest cylinder next.