1
$\begingroup$

I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below:

Three processes are competing for six resources labelled A to F as shown below.

enter image description here

Using a resource allocation graph, show the possibility of a deadlock in the implementation above.

I know how to do the graph but what I am struggling to understand is, do I take the Release(); methods into consideration or only the Get(); methods. And also, would P0() access resources A, B and C first or will each process run simultaneously meaning P0() access resource A, P1() access resource D and P2() access resource C, and then the second set of Get() methods are requested simultaneously? Lastly it does not specify how many instances (dots) are in each resource, is there any indication as to how to determine/go about working with this? As soon as I can clear up these misunderstandings I can draw the diagram

$\endgroup$

2 Answers 2

1
$\begingroup$

Here is one bad scenario:

  1. P0 obtains A and B.
  2. P1 obtains D and E.
  3. P2 obtains C and F.

At this point, we have reached deadlock, since P0 is waiting for P2 to release C, P1 is waiting for P0 to release B, and P2 is waiting P1 to release D.

$\endgroup$
1
  • $\begingroup$ Thank you, looks like that confirms what I was working towards :) $\endgroup$
    – Osiris93
    Commented Sep 1, 2015 at 17:56
1
$\begingroup$

Introduction

Consider a Petri Net model of the three processes. Assume the following:

  1. Every resource (A, B, C, D, E, F) has one unit only.
  2. All three processes run on a single processor. The processor can execute one and only one process at a time. This means that if a process is executing its Get() or Release() function or critical region, no other process can execute.
  3. After executing a statement in any process (such as Get(), a statement in the critical section or Release()), the operating system can switch to another process and execute the other process’ next statement.

Petri Net: Model and Sub-Models

Figure 1 is a Petri Net model of Process 1. Figure 2 is a Petri model of Process 2. Figure 3 is a Petri Net model of Process 3. Figure 4 is a Petri Net model of all processes.

Label Descriptions for Petri Net Model and Sub-Models

Petri Net Model and Sub-Models Figures

Deadlock Scenario

Figure 5 is an initial state of the system where none of the resources have been allocated. Figure 6 is the state of the system reached from the state in Figure 5 following the firing sequence: G_0^0→G_1^0→G_0^1→G_1^1→G_0^2→G_1^2.

An Initial Marking and a Deadlock State

Three Processes Competing for Resources

Figure 7 is a larger version of Figure 5 and (for the PDF version of this document) it is an interactive, dynamic diagram.

Petri Net Model of Three Processes Competing for Resources

Reference

Chionglo, J. F. (2015). "A Reply to 'Help interpreting this deadlock problem'". Available at http://www.aespen.ca/AEnswers/1449369180.pdf.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.