مدل کردن بن بست با استفاده از گراف تخصیص

مدل کردن بن بست با استفاده از گراف تخصیص

گراف تخصیص بر اساس درخواست فرآیندها برای تخصیص منابع ساخته می شود. یک گراف تخصیص شامل تعدادی گره و یال است. دو نوع گره در گراف تخصیص وجود دارد، گره های دایره ای و گره های مربعی. به ازای هر فرآیند موجود در سیستم یک گره دایره ای در گراف اضافه مب شود و به ازای هر منبع موجود در سیستم یک گره مربعی به سیستم اضافه می گردد. چنانچه فرآیندی منابعی را درخواست کند و منبع به وی تخصیص داده شود یالی از منبع به سمت فرآیند رسم می شود. اگر به دلیلی فرآیند نتواند منبع را در اختیار بگیرد یال از فرآیند به سمت منبع رسم می شود.
نکته: در حالتیکه از یک نوع منبع بیشتر از یک نمونه موجود است معمولا در داخل مربع مربوط به منابع  تعدادی نقطه قرار می گیرد که هر نقطه نشان دهنده یک منبع می باشد. و به ازای هر تخصیص یکی از این نقاط تخصیص داده می شود.
برای تشخیص بن بست کافی است به ازای تخصیص و یا درخواست  هر منبع به هر فرآیندی، گراف تخصیص را به روز در آورد ( بر اساس نکته های فوق) چنانچه در گراف به روز آورده شده، حلقه وجود داشت که از تمام فرآیندها عبو ر می کند بن بست رخ داده است، در غیر این صورت بن بست تا به حال وجود نداشته است.
نکته: اگر دستورات مربوط به فرآیندها به صورت ترتیبی اجرا شود، یعنی ابتدا فرآیند A به وطور کامل اجرا شود، بعد فرآیند B و به همین ترتیب، مطمئنا هیچ گاه بن بست رخ نخواهد داد.

شرکت مهندسی آبان رایان البرز