Bangladesh Bank
<
Assistant Maintenance Engineer/Assistant Engineer (IT)
Exam Date: 08/05/2026
Circular Wait
- Circular wait is one of the necessary conditions for deadlock.
- It occurs when a group of processes are waiting for resources in a circular chain.
- In this situation, each process holds at least one resource and waits for another resource held by the next process in the cycle.
Example:
- Process P1 holds Resource R1 and waits for R2.
- Process P2 holds Resource R2 and waits for R3.
- Process P3 holds Resource R3 and waits for R1.
This creates a circular waiting condition.
Cycle in Resource Allocation Graph (RAG)
If a cycle exists in a Resource Allocation Graph, it does not always guarantee deadlock.
- If each resource type has only one instance, then a cycle definitely indicates deadlock.
- If resource types have multiple instances, then a cycle may exist without deadlock.
So, a cycle is:
- A necessary condition for deadlock
- But not always a sufficient condition
Deadlock Detection using Resource Allocation Graph
To detect deadlock using Resource Allocation Graph (RAG), we follow these steps −
- If RAG contains no cycles, then there is no deadlock in the system.
- If RAG is of single instance resources and it contains a cycle, then there is a deadlock in the system.
- If RAG is of multiple instance resources and it contains a cycle, then deadlock may or may not exist. To check for deadlock, we need convert multiple instance RAG to single instance RAG, by treating each instance of a resource as a separate resource type.
In the graph:
- Resource R1 has only one instance.
- Resource R2 has two instances.
- P1 is holding R1 and requesting R2.
- P2 is holding one instance of R2 and requesting R1.
- P3 is using another instance of R2.
A cycle exists in the graph: P1 → R2 → P2 → R1 → P1
But this graph does not indicate deadlock.
Reason:
Resource R2 has multiple instances. One instance of R2 is currently allocated to P3.
If P3 finishes its work and releases R2, then:
- P1 can obtain R2 and complete execution.
- After P1 completes, it releases R1.
- Then P2 can obtain R1 and continue execution.
Since the processes can still proceed and resources can eventually be released, the system is not permanently blocked.
প্রশ্ন: Circular Wait সংক্ষেপে ব্যাখ্যা কর। Resource Allocation Graph (RAG)-এ cycle থাকলে কি নিশ্চিতভাবে Deadlock হয়েছে বোঝায়? সংক্ষেপে ব্যাখ্যা কর।
Circular Wait
- Circular wait হলো deadlock-এর একটি প্রয়োজনীয় শর্ত।
- এটি তখন ঘটে যখন একাধিক process একটি circular chain আকারে resource-এর জন্য অপেক্ষা করে।
- এখানে প্রতিটি process অন্তত একটি resource ধরে রাখে এবং পরবর্তী process-এর কাছে থাকা অন্য resource-এর জন্য অপেক্ষা করে।
উদাহরণ:
- Process P1 Resource R1 ধরে রেখে R2-এর জন্য অপেক্ষা করছে।
- Process P2 Resource R2 ধরে রেখে R3-এর জন্য অপেক্ষা করছে।
- Process P3 Resource R3 ধরে রেখে R1-এর জন্য অপেক্ষা করছে।
এভাবে একটি circular waiting condition তৈরি হয়।
Resource Allocation Graph (RAG)-এ Cycle
RAG-এ cycle থাকলেই সবসময় deadlock হয়েছে এমন নয়।
- যদি প্রতিটি resource type-এর শুধুমাত্র একটি instance থাকে, তাহলে cycle থাকলে নিশ্চিত deadlock হয়েছে।
- কিন্তু resource type-এর একাধিক instance থাকলে cycle থাকলেও deadlock নাও হতে পারে।
অতএব cycle হলো:
- Deadlock-এর জন্য একটি necessary condition
- কিন্তু সবসময় sufficient condition নয়
Graph-এ:
- Resource R1-এর একটি instance রয়েছে।
- Resource R2-এর দুটি instance রয়েছে।
- P1, R1 ধরে রেখে R2-এর জন্য অপেক্ষা করছে।
- P2, R2-এর একটি instance ধরে রেখে R1-এর জন্য অপেক্ষা করছে।
- P3, R2-এর অন্য instance ব্যবহার করছে।
Graph-এ একটি cycle রয়েছে:
P1 → R2 → P2 → R1 → P1
কিন্তু এই graph-এ deadlock নেই।
কারণ:
Resource R2-এর একাধিক instance রয়েছে। বর্তমানে R2-এর একটি instance P3 ব্যবহার করছে।
যদি P3 তার কাজ শেষ করে R2 release করে, তাহলে:
- P1, R2 পেয়ে execution সম্পন্ন করতে পারবে।
- P1 কাজ শেষ করলে R1 release করবে।
- তারপর P2, R1 পেয়ে execution চালিয়ে যেতে পারবে।
অর্থাৎ process-গুলো পরবর্তীতে execution চালিয়ে যেতে পারছে, তাই system permanently blocked নয়।
