تستهای بنبست معمولاً یکی از این سه را میپرسند: کدام شرط شکسته شده؟ این حالت امن است؟ این درخواست پذیرفته میشود؟ دو سؤال آخر با الگوریتم بانکدار جواب داده میشوند و یک اشتباه رایج ثابت دارند که پایینتر روی عدد میبینیم.
چهار شرط بنبست
بنبست فقط وقتی ممکن است که هر چهار شرط همزمان برقرار باشند. برای جلوگیری از بنبست کافی است یکی را بشکنی:
| شرط | یعنی | یک راه شکستنش |
|---|---|---|
| انحصار متقابل | منبع همزمان فقط دست یک فرایند است | منابع اشتراکی، مثل فایل فقطخواندنی |
| نگهداشتن و انتظار | فرایند منبعی دارد و منتظر منبع دیگری است | همهٔ منابع را یکجا در شروع بخواهد |
| انحصاری نبودن | منبع را نمیشود به زور از فرایند گرفت | اجازهٔ پس گرفتن منبع |
| انتظار چرخشی | زنجیرهای بسته از فرایندهای منتظر هم | به منابع شماره بده و فقط به ترتیب صعودی درخواست کن |
گراف تخصیص منابع
فرایندها و منابع رأساند؛ یال از فرایند به منبع یعنی درخواست و یال از منبع به فرایند یعنی تخصیص. قاعدهٔ تستی این است: اگر از هر منبع فقط یک نمونه باشد، دور در گراف یعنی بنبست. اگر منابع چند نمونه داشته باشند، دور لازم است ولی کافی نیست؛ ممکن است دور باشد و بنبست نباشد، چون نمونهٔ دیگری از منبع آزاد میشود.
الگوریتم بانکدار روی یک مثال
چهار فرایند و سه نوع منبع A، B و C داریم با کل منابع (۵، ۳، ۴). هر فرایند اعلام کرده حداکثر به چه مقدار نیاز دارد:
| فرایند | تخصیص فعلی (A، B، C) | حداکثر نیاز | نیاز باقیمانده = حداکثر − تخصیص |
|---|---|---|---|
| P1 | ۱، ۰، ۱ | ۳، ۲، ۲ | ۲، ۲، ۱ |
| P2 | ۲، ۱، ۰ | ۳، ۲، ۲ | ۱، ۱، ۲ |
| P3 | ۰، ۱، ۱ | ۲، ۲، ۳ | ۲، ۱، ۲ |
| P4 | ۱، ۰، ۰ | ۲، ۱، ۱ | ۱، ۱، ۱ |
منابع آزاد = کل منهای جمع تخصیصها = (۵، ۳، ۴) − (۴، ۲، ۲) = (۱، ۱، ۲).
الگوریتم امنیت
دنبال فرایندی بگرد که نیاز باقیماندهاش از منابع آزاد بیشتر نباشد. فرض کن تا آخر اجرا میشود و منابعش را آزاد میکند. تکرار کن. اگر همهٔ فرایندها تمام شدند، حالت امن است:
- P2 با نیاز (۱، ۱، ۲) با منابع آزاد (۱، ۱، ۲) جور است؛ تمام میشود و منابع آزاد میشود (۳، ۲، ۲).
- P1 با نیاز (۲، ۲، ۱) جور است؛ منابع آزاد میشود (۴، ۲، ۳).
- P3 با نیاز (۲، ۱، ۲) جور است؛ منابع آزاد میشود (۴، ۳، ۴).
- P4 با نیاز (۱، ۱، ۱) جور است و تمام میشود.
پس حالت امن است و P2، P1، P3، P4 یک ترتیب امن است. با امتحان همهٔ ترتیبها، این حالت ۱۰ ترتیب امن دارد و همهشان با P2 یا P4 شروع میشوند؛ چون فقط نیاز این دو با منابع آزاد اولیه جور است.
درخواستها: کدام پذیرفته میشود؟
برای هر درخواست سه قدم داری: درخواست نباید از نیاز باقیمانده بیشتر باشد (وگرنه خطاست)، نباید از منابع آزاد بیشتر باشد (وگرنه فرایند صبر میکند)، و بعد از دادنش حالت باید هنوز امن باشد (وگرنه رد میشود):
| درخواست | از نیاز کمتر؟ | موجود است؟ | بعد از دادن امن است؟ | نتیجه |
|---|---|---|---|---|
| P2 میخواهد (۰، ۱، ۱) | بله | بله | بله | پذیرفته |
| P4 میخواهد (۱، ۱، ۰) | بله | بله | بله | پذیرفته |
| P1 میخواهد (۱، ۰، ۰) | بله | بله | نه | رد |
سطر آخر کل نکتهٔ الگوریتم بانکدار است. اگر به P1 یک A بدهی، منابع آزاد میشود (۰، ۱، ۲). حالا هیچ فرایندی نمیتواند شروع کند: P1، P2، P3 و P4 همه دستکم یک A دیگر لازم دارند و A آزاد صفر است. یعنی منبع موجود بود، ولی دادنش سیستم را به حالتی میبرد که ممکن است به بنبست برسد.
یک فرمول سریع برای یک نوع منبع
اگر n فرایند از یک نوع منبع هر کدام حداکثر k واحد لازم داشته باشند، بنبست فقط وقتی ممکن است که کل منابع R حداکثر n(k − ۱) باشد. دلیلش ساده است: بدترین حالت این است که هر فرایند k − ۱ واحد گرفته باشد و منتظر آخری باشد. یک واحد بیشتر کافی است تا یکی تمام کند. پس کمترین R بدون بنبست n(k − ۱) + ۱ است؛ مثلاً برای ۳ فرایند که هر کدام ۳ واحد لازم دارند، ۷ واحد.
سه اشتباه رایج
اشتباه ۱: «منبع هست، پس درخواست پذیرفته میشود»
در الگوریتم بانکدار موجود بودن کافی نیست؛ بعد از دادن، حالت باید امن بماند. درخواست P1 در مثال بالا همین را نشان میدهد.
اشتباه ۲: ناامن یعنی بنبست
حالت ناامن یعنی سیستم نمیتواند تضمین کند که بنبست پیش نمیآید، نه اینکه الان در بنبست است. ممکن است فرایندها زودتر از حداکثر اعلامشده کارشان را تمام کنند و بنبستی رخ ندهد.
اشتباه ۳: دور در گراف یعنی همیشه بنبست
این فقط برای منابع تکنمونهای درست است. با منابع چندنمونهای، دور شرط لازم است نه کافی.
پرسشهای پرتکرار
چهار شرط لازم بنبست کداماند؟
انحصار متقابل، نگهداشتن و انتظار، انحصاری نبودن و انتظار چرخشی. بنبست فقط وقتی ممکن است که هر چهار شرط همزمان برقرار باشند، پس شکستن یکی از آنها کافی است.
حالت امن یعنی چه؟
حالتی که دستکم یک ترتیب اجرای فرایندها وجود دارد که هر فرایند با منابع آزاد بهعلاوهٔ منابعی که فرایندهای قبلی آزاد میکنند، نیاز حداکثرش را بگیرد و تمام کند.
فرق پیشگیری، اجتناب و تشخیص بنبست چیست؟
پیشگیری یکی از چهار شرط را از اساس ناممکن میکند. اجتناب، مثل بانکدار، هر درخواست را بررسی میکند تا حالت امن بماند. تشخیص اجازه میدهد بنبست پیش بیاید، بعد پیدایش میکند و با خاتمه دادن به فرایند یا پس گرفتن منبع برطرفش میکند.
زمان اجرای الگوریتم امنیت چقدر است؟
با n فرایند و m نوع منبع، O(m·n²) است: حداکثر n دور، و در هر دور بررسی n فرایند که هر کدام مقایسهٔ m مقدار دارد.
قدم بعدی تو
در همان مثال، این سه درخواست را جداگانه بررسی کن: ۱) P3 میخواهد (۱، ۰، ۰). ۲) P4 میخواهد (۰، ۰، ۱). ۳) P2 میخواهد (۱، ۱، ۲).
جوابها: ۱) رد؛ منبع موجود است ولی بعد از دادنش A آزاد صفر میشود و هیچ فرایندی نمیتواند تمام کند. ۲) پذیرفته؛ یک ترتیب امن بعدش P4، P2، P1، P3 است. ۳) پذیرفته؛ P2 با آن کل نیازش را میگیرد، تمام میکند و منابعش را آزاد میکند.
روش کار را در روش تولید محتوا ببین.
منابع این مطلب
- اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶سازمان سنجش آموزش کشور · بررسی ۱۷ شهریور ۱۴۰۵ · اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶
سیستمهای عامل در بستهٔ تخصصی مجموعههای ۱۲۷۷ و ۱۲۷۶
سازمان سنجش آموزش کشور — اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶