Deadlocksبن بست ها
کامپیوتر ها دارای منابع زیادی هستند که در هر لحظه فقط توسط یک processمی توانند استفاده شوند . مثلا printer ها ،tape drive ها ، scanner ها ، slot های process table .
اگر دو پروسس همزمان بخواهند در یک slot درون process table بنویسند، باعث خراب شدن سیستم میشود.اگر دو پروسس بخواهند روی printer بنویسند حاصل آشغال خواهد بود.
بنا بر این تمام سیستمهای عامل قدرت تخصیص دسترسی انحصاری (به طور موقت) به منابع مشخصی را دارند . در بسیاری از برنامه های کاربردی ، process نیازانحصاری به چندین منبع را دارد . فرض کنیدقرار باشد نقشه یک کشور از روی یک cd ،روی یک plotterبرده شود . فرض کنید process Aدرخواست cd-Rom کند وcd-Rom به او تخصیص یابد. کمی بعد process Bدرخواست plotterکند وبه او داده شودحالا process A درخواست plotterکند،و در انتظار آن منبع ،block شود . سپس process B، تقاضای cd_Rom driverکند وblock شود . در این لحظه هر دوی process ها در حالت blockهستند و تا ابد در این حالت باقی می مانند . این وضعیت deadlockنام دارد.
A
B
R1
R2
منبع : هر چیزی است که در هر لحظه فقط توسط یک پروسس می تواند استفاده شود . منبع می تواند سخت افزاری یا نرم افزاری باشد .
Resource ها دو نوعند:
قابل پس گرفتن preemptable
غیر قابل پس گرفتن nonpreemptable
دنباله اتفاقات در مورد استفاده از یک منبع به این صورت است:
تقاضا برای منبع
استفاده از منبع
آزاد کردن منبع
typedef int semaphore; typedef int semaphore;
semaphore resource_1; semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource _1); void process_A(void) {
use_resource_1( ); down(&resource _1);
up(&resource _1); down(&resource _2);
use_both_resources( );
} up(&resource _2);
up(&resource _1);
}
(a) (b)
typedef int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource _1);
down(&resource _2);
use_both_resources( );
up(&resource _2);
up(&resource _1);
}
void process_B(void) {
down(&resource _1);
down(&resource _2);
use_both_resources( );
up(&resource _2);
up(&resource _1);
}
typedef int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource _1);
down(&resource _2);
use_both_resources( );
up(&resource _2);
up(&resource _1);
}
void process_B(void) {
down(&resource _2);
down(&resource _1);
use_both_resources( );
up(&resource _1);
up(&resource _2);
}
Fig. 3-2. (a) Deadlock-free code. (b) Code with a potential deadlock.
اصول بن بست
تعریف رسمی بن بست این است:
مجموعه ای از processها در حالت بن بست قرار دارد اگر هر process
این مجموعه منتظر اتفاقی باشد که فقط process دیگری در این مجموعه میتواند ایجادش کند.از آنجا ئیکه همه پروسس ها منتظر هستند،هرگزهیچ یک از آنها نمی تواند اتفاقی که باعث بیدار شدن عضو دیگری از مجموعه شود
را ایجاد کنند و همه process ها برای همیشه منتظر خواهند بود.
شرایط لازم برای بوجود آمدن بن بست
شرط ” دو بدو ناسازگاری “ Mutual exclusion
شرط ” نگهدار و منتظر شو “Hold and wait
شرط“ غیر قابل پس گرفتن “ No preemption
شرط“ انتظار دایره ای “Circular wait condition
Coffman و چند نفر دیگر (1971) نشان دادند که چهار شرط برای بوجود آمدن بن بست لازم است :
مدل سازی بن بست
Dead lock modeling
شخصی به نام Holt درسال 1972 نشان داد….
A
R
R
B
D
T
U
C
گرافهای جهت دار ( گرافهای منابع )
How deadlock occurs
A B C
Deadlock Modeling
Deadlock Modeling (5)
How deadlock can be avoided
(o) (p) (q)
کلا چهار استراتژی ممکن است در ارتباط با پرداختن بهDEADLOCK استفاده شود.
به کل نادیده گرفتن مسئله
کشف و ترمیم
اجتناب پویا توسط تخصیص دقیق منابع
جلوگیری توسط نقض ساختاری یکی از 4 شرط لازم برای بوجود آمدن بن بست
1- الگوریتم شترمرغ
THE OSTRICH ALGORITHM
DEADLOCK DETECTION AND RECOVERY
2- کشف و ترمیم بن بست
2-1 : کشف بن بست در حالت چندین منبع از هر نوع
The Ostrich Algorithm
Pretend there is no problem
Reasonable if
deadlocks occur very rarely
cost of prevention is high
UNIX and Windows takes this approach
It is a trade off between
convenience
correctness
Detection with One Resource of Each Type (1)
Note the resource ownership and requests
A cycle can be found within the graph, denoting deadlock
Detection with Multiple Resource of Each Type
Data structures needed by deadlock detection algorithm
Detection with Multiple Resource of Each Type
An example for the deadlock detection algorithm
1
Recovery from Deadlock (1)
Recovery through preemption
take a resource from some other process
depends on nature of the resource
Recovery through rollback
checkpoint a process periodically
use this saved state
restart the process if it is found deadlocked
Recovery from Deadlock (2)
Recovery through killing processes
crudest but simplest way to break a deadlock
kill one of the processes in the deadlock cycle
the other processes get its resources
choose process that can be rerun from the beginning
Deadlock Avoidance Resource Trajectories
Two process resource trajectories
Safe and Unsafe States
Demonstration that the state in (a) is safe
(a) (b) (c) (d) (e)
وضعیتهای امن و ناامن
Safe and Unsafe States
Demonstration that the sate in b is not safe
(a) (b) (c) (d)
اجتناب از بن بست
الکوریتم بانکدار BANKER برای یک نوع منبع
یک الگورتم در سال 1965 توسطDIJKSTRAبیان شد که به الکوریتم BANKER مشهور است.
Free:10 Free:2 Free:1
The Banker's Algorithm for a Single Resource
Three resource allocation states
safe
safe
unsafe
(a) (b) (c)
الگوریتم بانکدار برای منابع چند گانه ( یعنی از چند نوع مختلف )
بردار E : بردار تعداد منابع موجود EXISTING
بردارP : بردار تعداد منابع تخصیص داده شده POSSESSED
بردارA : بردار تعداد منابع در دسترس AVAILABLE
A = E – P
Resources assigned
Resources still needed
Process
tapedriv
plotters
scanners
Cd roms
Process
tapedriv
scanners
plotters
cd roms
Banker's Algorithm for Multiple Resources
Example of banker's algorithm with multiple resources
پیشگیری از بن بست DEADLOCK PREVENTION
اگر منبع به طور اختصاصی به پروسس داده شود هرگز بن بست پیش نمی آید.
جلوی در اختیار گرفتن منابع و انتظار برای منابع دیگر را بگیریم.
استفاده از منابع بصورت NONPREEMPTIVEنباشد ولی این روش مناسب نیست .
جلوگیری از انتظار چرخشی
روش اول: هر پروسس که منبع اول را گرفت و به منبع دوم نیاز داشت ابتدا منبع اول را رها کند.
روش دوم: یک شماره سراسری به هر منبع داده شود.هر پروسس می تواند منبع درخواست کندولی درخواستهایش باید به ترتیب صعودی شماره باشد(ترتیب نزولی قابل قبول نیست)
Deadlock Prevention Attacking the Mutual Exclusion Condition
Some devices (such as printer) can be spooled
only the printer daemon uses printer resource
thus deadlock for printer eliminated
Not all devices can be spooled
Principle:
avoid assigning resource when not absolutely necessary
as few processes as possible actually claim the resource
Attacking the Hold and Wait Condition
Require processes to request resources before starting
a process never has to wait for what it needs
Problems
may not know required resources at start of run
also ties up resources other processes could be using
Variation:
process must give up all resources
then request all immediately needed
Attacking the No Preemption Condition
This is not a viable option
Consider a process given the printer
halfway through its job
now forcibly take away printer
!!??
Attacking the Circular Wait Condition (1)
Normally ordered resources
(a) (b)
Attacking the Circular Wait Condition (1)
Summary of approaches to deadlock prevention
Other Issues Two-Phase Locking
Phase One
process tries to lock all records it needs, one at a time
if needed record found locked, start over
(no real work done in phase one)
If phase one succeeds, it starts second phase,
performing updates
releasing locks
Note similarity to requesting all resources at once
Algorithm works where programmer can arrange
program can be stopped, restarted
Nonresource Deadlocks
Possible for two processes to deadlock
each is waiting for the other to do some task
Can happen with semaphores
each process required to do a down() on two semaphores (mutex and another)
if done in wrong order, deadlock results
Starvation
Algorithm to allocate a resource
may be to give to shortest job first
Works great for multiple short jobs in a system
May cause long job to be postponed indefinitely
even though not blocked
Solution:
First-come, first-serve policy