آشنایی با الگوریتم بانکدار

الگوریتم گراف تخصیص – منبع قابل اعمال به سیستم تخصیص – منبع با نمونه های متعدد از هر نوع منبع، باشد. الگوریتم اجتناب بن بست که در ذیل توصیف می کنیم در مورد چنین سیستمهایی قابل کاربرد است، اما بازدهی کمتری نسبت به طرح گراف تخصیص – منبع دارد. این الگوریتم ، معمولاً به نام الگوریتم بانکدار شناخته می شود. اسم بدینگونه انتخاب شده که این الگوریتم می تواند      در یک سیستم بانکی هم به کار رود و تضمین نماید که بانک هرگز تمام سرمایه در دسترسش را تخصیص نمی دهد طوری که نتواند نیازهای کلیه مشتریانش را ارضاء نمایدوقتی پردازش جدیدی وارد سیستم می شود، بایستی ماکزیمم نمونه های هر نوع منبع مورد نیازش را اعلان نماید. این عدد نباید از تعداد کل منابع موجود در سیستم فراتر رود.  

، سیستم باید تعیین کند که تخصیص این منابع منجر به حالت امن می شود. اگر چنین باشد، منابع اختصاص داده می شوند؛ در غیر این صورت، پردازش باید منتظر بماند تا پردازش دیگری منابع کافی آزاد کندساختمانهای داده متعددی برای پیاده سازی الگوریتم بانکدار بایستی فراهم شود. این ساختمانهای داده سیستم تخصیص – منبع را تشبیه خواهند نمود. فرض کنید n تعداد پردازشها در سیستم و m تعداد انواع منابع باشد. به ساختمانها داده زیر نیازمندیم• Available : یک برداد به طول m که تعداد منابع آزاد از هر نوع را نشان می دهد. اگر Available [j] = k یعنی k نمونه از منبع نوع Ri در دسترس قرار دارد• m که ماکزیمم نیاز هر پردازش را تعریف می کند، اگر Max [I,j] = kÍMax : یک ماترس n ، یعنی پردازش Pi می تواند حداکثر k نمونه از منبع نوع Rj درخواست کند• m که تعداد منابع از هر نوع که در حال حاضر به هر پردازشÍAllocation : یک ماترس n تخصیص داده شده است، را تعریف می نماید. اگر Allocation [I,j] = k ، یعنی پردزاش Pi در حال حاضر k نمونه از نوع منبع Rj در اختیار دارد. • Need : یک ماترس nÍm که نیاز باقیمانده منبع مورد نیاز هر پردازش را بازگو می کند. اگر داشته باشیم Need [I,j] = k ، آنگاه پردازش Pi می تواند k نمونه بیشتر از منبع نوع Rj را برای تکمیل وظیفه اش درخواست کند. دقت کنید که Allocation [I,j] Max [I,j] - Need [I,j] = این ساختمانهای داده با گذر زمان ، از حیث هم طول و هم اندازه تغییر می کنند. برای سهولت نمایش الگوریتم بانکدار، بیایید سبک نگارشی را برپا داریم. فرض کنید X و Y بردارهایی به طول n باشند. بیان می کنیم که X≤Y اگر و فقط اگر X[i]≤Y[i] برای همه i= 1 , 2 , …, n به عنوان مثال، اگر (2 و3و 7و1) X= و (1و2و3و0) Y= باشند در آن صورت Y≤X است. Y<X است اگر Y≤X بوده و نیز Y≠X باشد. می توانیم هر سطر در ماتریس تخصیص و نیاز را همانند بردارهایی به کار بریم و به صورت                  Allocation i و Need به ترتیب مورد اجرا قرار دهیم. بردارAllocation i نشان دهنده منابع تخصیص یافته به پردازش Pi می باشد؛ بردار Need i مشخص کنندPi می تواند هنوز درخواست نماید، اضافی که پردازش است Safety Algorithm الگوریتم امنیت است الگوریتمی که برای دریافتن حالت امن یا نا امن سیستم به کار می رود به شرح زیرفرض کنید Work و Finish به ترتیب بردارهایی به طول m وn باشند. مقادیر آغازین Work = Available 1. و Finish [i] : = false برای i = 1 , 2 , …, n می باشند یک i چنان بیابید که هر دو شرط زیر را داشته باشد: a.Finfish[i]= false 2. b. Need i ≤Work
if no such i exists, go to step 4Work : = Work + Allocation i 3. Finish [i] : = true Go to step 24. اگر برای همه i ها ، Finish[i] = true باشد، آنگاه سیستم در حالت امن واقع است. این الگوریتم به اعمال از درجه n*m برای تصمیم گیری حالت امن، نیازمند استالگوریتم درخواست – منبع Resource-Request Algorithm فرضکنیدRequest i بردار درخواست برای پردازش Pi باشد. اگر Request i [j]=k ، آنگاه پردازش Pi ، k نمونه از نوع منبع Rj را می خواهد. وقتی درخواستی توسط پردازش Pi صادر می شود، اعمال زیر انجام می گیرند: 1. اگر Request i ≤ Need i ، به قدم 2 بروید . در غیر اینصورت وضعیت خطایی را معین نمایید زیرا پردازش از ماکزیمم ادعایش فراتر خواسته است2. اگر Request i ≤ Available ، به قدم 3 بروید. در غیر اینصورت ، Pi بایستی منتظر بماند، زیرا منابع در دسترس نمی باشند. 3. بگذارید سیستم وانمود کند که منابع درخواستی پردازش Pi را تخصیص داده است. با تغییر حالت به شرح زیرAvailable : = Available – Request iAllocation i : = Allocation i + Request i Need i : = Need i - Request i اگر گراف تخصیص – منبع حاصله، امن باشد تراکنش کامل است و پردازش Pi منابعش را در اختیار می گیرد. اما، اگر حالت جدید ناامن باشد، Pi بایستی منتظر Request i بماند و گراف تخصیص – منابع قبلی ، بازیافت شود. یک مثال روشن کننده An illustrative Example سیستمی متشکل از پنج پردازش P0 تا P4 و سه نوع منبع C,B,A را در نظر بگیرید. منبع نوع A دارای 10 نمونه، منبع نوع B دارای 5 نمونه و منبع نوع C دارای 7 نمونه می باشند. فرض کنید در زمان t0 ، تصویر لحظه ای زیر از سیستم گرفته شده استAvailable Max Allocation A B C A B C A B C محتویات ماتریس Need به صورت Max-Allocation تعریف شده و عبارت است از: Need A B C ادعا می را ارضاء می کنیم که سیستم در حال حاضر در حالت امن است. در واقع، توالی <P1> معیارهای امنیت نماید. اکنون فرض کنید که پردازش P1 نمونه اضافه تری از نوع منبع نوع A و دو نمونه از منبع نوع C درخواست کند، لذا Request 1 = (1, 0 ,2) جهت تصمیم گیری اینکه، این درخواست می تواند آنی تخصیص داده شود، ابتدا وارسی می کنیم که Request 1 ≤ Available (یعنی، (2و3و3) ≥ (2و0و1)) صادق است. سپس وانمود می کنیم که درخواست انجام گیرد و به حالت جدید زیر می رسیم: Available Need Allocation A B C A B C A B C حال باید تعیین نماییم که آیا این حالت جدید امن است یا خیر. برای انجام این کار، الگوریتم امنیت را اجرا می نماییم و درمی یابیم که توالی <P1> نیازهای امنیتی را ارضاء می کند. بنابراین می توان آنی درخواستهای پردازش P1 را تخصیص داداما بایستی قادر باشید درک کنید که وقتی سیستم در این حالت است، یک درخواست از جانب P4 برای (0 و 3و3) قابل اعطا نیست، زیرا منابع کافی در دسترس نیست. درخواست (0 و 2و 0) از P0 هم قابل اعطا نیست، اگر چه منابع در دسترس به اندازه کافی است اما حالت منتجه ، ناامن است. آشکارسازی بن بست Deadlock Detectionاگر سیستمی هیچ یک از الگوریتمهای پیشگیری از بن بست و اجتناب از بن بست را به کار نگیرد، در این صورت وضعیت بن بست رخ می دهد. در چنین محیطی، سیستم بایستی امکانات زیر را فراهم سازد: • الگوریتمی که حالت سیستم را وارسی می کند تا تعیین نماید که بن بست رخ داده است. • الگوریتمی که از حالت بن بست سیستم را احیا نماید. در بحث پیش روی، بر روی این دو نیاز در مورد سیستمهایی دارای نمونه منبعهای منفرد و نیز نمونه منبعهای متعدد کار می کنیم. اما، در این نقطه بایستی دقت نماییم که طرح بازیافت و آشکار سازی بارسری است که نه تنها هزینه زمان – اجرای نگهداری اطلاعات لازم و راندن الگوریتم تشخیص را دربر می گیرد، بلکه زیانهای احتمالی بالفطره در بازیافت نمونه از منفرد از هر نوع منبع بن بست را نیز شامل می شود .                    Single Instance of EachResource Type اگر کلیه منابع دارای یک نمونه باشند، آنگاه می توان الگوریتم آشکارسازی بن بست را که نسخه متفاوتی از گراف تخصیص – منابع است، به نام گراف انتظار – برای، به کار بریم. این گراف از گراف تخصیص – منابع بدین گونه حاصل می شود که گره های نوع منبع را حذف می نماییم و کمانهای مناسب را تخریب می کنیمدقیقتر ، یک کمان از پردازش Pi به Pj در گراف انتظار – برای، بیان می کند که پردازش Pi در انتظار پردازش  Pi در گراف انتظار –"Pj است تا منبعی را که Pi نیازمند است آزاد کند. یک کمان Pj   Pi و"برای، وجود دارد اگر و فقط اگر گراف تخصیص – منابع متناظرش شامل دو کمان Rq   Rq برای منبعی از Rq ، باشد. به عنوان مثال ، دریک گراف تخصیص – منبع و گراف"Pj  انتظار – برای متناظرش را نشان داده ایمشکل همانند قبل یک بن بست در سیستم وجود دارد اگر و فقط اگر گراف انتظار – برای، دارای سیکل بسته باشد. برای تشخیص بن بست، سیستم بایستی این گراف را نگهداری کرده و بطور پریودیک الگوریتمی را فرا خواند که به جست و جوی سیکلی در گراف بپردازدالگوریتم تشخیص سیکل در گراف، اعمال با درجه n را لازم دارد، که n تعداد رئوس گراف می باشد. نمونه های متعدد از یک نوع منبع Several Instances of a Resource Type طرح گراف انتظار – برای در مورد سیستمی با نمونه های متعدد از نوع مختلف، قابل اعمال نیست. الگوریتم آشکار سازی – بن بست بعدی که معرفی می کنیم در چنین سیستمهایی کاربرد دارد. الگوریتم، سازه های اطلاعاتی متغیر با زمان متعددی را نظیر الگوریتم بانکداررا کار می گیرد• Available : برداری به طول m که نشان دهنده تعداد منابع آزاد از هر نوع منبع، می باشد. • Allocation : ماتریس m*n که تعداد منابع تخصیص یافته به هر پردازش را، در حال حاضر تعریف می کند. • Request : ماتریس m*n که نیازهای فعلی هر پردازش را بیان می کند. اگر Request[i,j] = k باشد، یعنی پردازش Pi ، k نمونه بیشتر از منبع نوع Rj را درخواست نموده استرابطه کوچکتر از (<) بین بردارهاتعریف شده، می باشد. جهت سهولت طرز نگارش، سطرهای ماتریسهای Allocation و Request را همانند قبل به صورت بردارهای Allocation i و Request i ، به ترتیب نمایش می دهیم. الگوریتم آشکارسازی که در اینجا توصیف می شود به سادگی هر توالی تخصیص ممکن را برای پردازشهایی که جهت تکمیل باقیمانده اند، تحقیق می نماید. این الگوریتم را با الگوریتم بانکدار مقایسه نمایید1. فرض کنید Work و Finish بردارهایی به طول m و n به ترتیب باشند. Work : = Available را آغازدهی کنید. برای i = 1, 2 ,…,n ، اگر Allocation i ≠ 0 باشد ، آنگاه Finish [i] : = false قرار دهید و در غیر اینصورت Finish [i] : = true باشد. 2. اندیس i ای ، بیابید طوری که هر دو شرط زیر برقرار باشدa. Finish [i] : = false b. Request i ≤ Work If no such i exists, go to step 4. 3. Work : = Work + Allocation Go to step 2 4. اگر Finish [i] = false ، برای بعضی iهای مابین i≤n ≤ 1 ، در آنصورت سیستم در حالت بن بست قرار دارد. به علاوه ، اگر Finish [i] = false ، پردازش Pi در بن بست واقع است این الگوریتم به اعمال از درجه n*m برای آشکار سازی این که سیستم در حالت بن بست واقع است، نیازمند است. ممکن است شک آور باشد که چرا منابع پردازش Pi باز ستانده می شوند (در قدم 3) به محض این که تعیین گردید که Request i ≤ Work (در قدم b2) است. می دانیم که پردازش Pi در حال حاضر در بن بست قرار ندارد (زیرا Request i ≤ Work ) بنابراین، یک گرایش خوش بینانه می گیریم، و فرض می کنیم که Pi منابع بیشتری برای تکمیل وظیفه اش نیاز ندارد؛ لذا کلیه منابع تخصیص یافته کنونی اش را به زودی به سیستم باز خواهد گرداند. اگر فرض ما نادرست باشد، بعداً یک بن بست رخ خواهد داد. این بن بست، دفعه آینده که الگوریتم تشخیص بن بست فراخوانده می شود، شناسایی خواهد شدبرای روشنگری این الگوریتم، سیستمی با پنج پردازش P0 تا P4 و سه نوع منبع A، B، C در نظر می گیریم. منبع نوع A دارای 7 نمونه و منبع نوع B دارای 2 نمونه و منبع نوع C دارای 6 نمونه است. فرض کنید که در زمان t0 حالت تخصیص – منبع زیر را داریمAvailable Request Allocation A B C A B C A B C ادعا می کنیم که سیستم در حالت بن بست واقع نیست. در واقع، اگر الگوریتم مان را اجرا نماییم، در می یابیم که توالی <P0> منجر به نتیجه Finish [i] = true برای همه i ها خواهد بوداکنون فرض کنید که پردازش P2 یک درخواست اضافی برای یک نمونه نوع C ، می نماید. ماتریس Request به شرح زیر تغییر می یابدRequestA B C ادعا می کنیم که سیستم اکنون در حالت بن بست قرار دارد . اگر چه می توانیم منابع گرفته شده توسط پردازش P0 را بازپس بگیریم، تعدا منابع در دسترس برای انجام تقاضاهای سایر پردازشها،‌ کافی نیست. لذا، یک بن بست متشکل از پردازشهای P1 ، P2 ، P3 ، P4 موجود استکاربرد الگوریتم تشخیص etection Algorithm Usage چه موقع باید الگوریتم تشخیص را فراخوانی کنیم؟ جواب به دو فاکتور بستگی دارد1. با چه تناوبی احتمال وقوع بن بست وجود دارد؟ 2. چه تعداد پردازش در موقع رخداد بن بست، متاثر خواهند شد؟ اگر بن بست مکرر رخ دهد، در این صورت الگوریتم تشخیص بایستی مکرراً فراخوانده شود. منابع تخصیص یافته به پردازشهای در بن بست، بیهوده خواهند ماند تا زمانی که بن بست شکسته شود. به علاوه، تعداد پردازشهای واقع در سیکل بن بست، ممکن است افزایش یابندبن بست وقتی در معرض وقوع است که پردازشی درخواستی نماید و نتوان فوراً آنر ا اعطا نمود. ممکن است که این درخواست، درخواست آخری باشد که زنجیر پردازشهای منتظر را تکمیل می نماید. در حد، می توانیم در هر بار درخواستی که فوراً قابل اعطا نیست ، الگوریتم تشخیص بن بست را صدا زنیم. در این حالت، نه تنها می توانیم مجموعه پردازشهای در بن بست را شناسایی کنیم بلکه پردازش خاصی را که سبب بن بست شده است، نیز معلوم می کنیم. (در واقع ، هر یک از پردازشهای در بن بست، یک اتصال در سیکل گراف منبع می باشند، لذا همه آنها ، توام با یکدیگر، سبب بن بست می شوند.) اگر انواع منبع متفاوت بسیاری وجود داشته باشند، یک درخواست می تواند سیکلهای بسیاری در گراف منبع ایجاد نماید. هر سیکل توسط آخرین درخواست تکمیل شده و هویت پردازش مسبب،‌ قابل شناسایی استالبته، فراخوانی الگوریتم تشخیص – بن بست در هر بار درخواست می تواند بارسر قابل توجهی در زمان محاسبه ایجاد نماید. یک آلترناتیو کم هزینه تر، آن است که الگوریتم را با تناوب کمتری صدا بزنیم – به عنوان مثال، یک باز در ساعت، یا هر بار که بهره وری CPU زیر 40 درصد افت نماید. (بن بست بالاخره، توان عملیاتی سیستم را ،‌فلج نموده و باعث افت بهره وری CPU می گردد.) اگر الگوریتم تشخیص در نقاط دلخواهی در زمان، صدا زده شود، ممکن است سیکلهای بسیاری در گراف منبع وجود داشته باشند. در حالت کلی، قادر نخواهیم بود بگوییم که کدام یک از پردازش ها باعث بن بست شده اندبازیافت از بن بست Recovery from Deadlockوقتی یک الگوریتم تشخیص، تعیین نماید که بن بست رخ داده است، راههای متعددی وجود دارند. یک امکان آن است که به اپراتور خبر دهیم که بن بست رخ داده است و بگذاریم که به طور دستی بن بست را اداره کند. امکان دیگر آن است که بگذاریم سیستم از حالت بن بست به طور اتوماتیک احیا شود. دو مورد دلخواه برای شکستن بن بست وجود دارد. یک مورد آن است که از یک یا چند پردازش صرف نظر کنیم تا انتظار چرخشی شکسته شود. مورد دوم آن است که بعضی منابع را از یک یا چند پردازش بن بست پس بگیریماتمام پردازش rocess Terminationبرای حذف بن بست، توسط نیمه کاره رها کردن یک پردازش، یکی از دو متد را به کار می بریم. در هر دو متد، سیستم کلیه منابع تخصیص یافته به پردازشهای خاتمه یافته را بازپس می گیرد• از کلیه پردازشهای بن بست صرف نظر نمایید: این روش به وضوح سیکل بن بست را خواهد شکست، اما در ازای هزینه سنگین . زیرا این پردازشها ممکن است برای مدت طولانی اجرای محاسباتی داشته باشند، و نتیجه این محاسبات جزیی بایستی چشم پوشی شود و احتمالاً بعداً مجدداً محاسبه صورت گیرد• هر بار یک پردازش نیمه کاره صرف نظر شود تا سیکل بن بست حذف گردد: این روش بارسر قابل توجهی اعمال می کند، زیرا بعد از هر پردازش که صرف نظر می شود، الگوریتم تشخیص بن بست باید صدا زده شود تا معین شود که هنوز پردازشهایی در بن بست واقعنددقت کنید که صرف نظر کردن از یک پردازش ممکن است آسان نباشد. اگر پردازش در میانه بهنگام سازی یک فایل باشد، خاتمه دادن به آن در وسط کار، آن فایل را در یک حالت نادرست قار می دهد. به طور مشابه، اگر پردازش در وسط چاپ داده ای باشد، سیستم بایستی حالت چاپگر را ری ست نماید تا آماده چاپ برای کار بعدی باشداگر روش خاتمه جزیی به کار رود، بایستی برای مجموعه مفروضی از پردازشهای در بن بست،‌تعیین نماییم که کدام پردازش بایستی خاتمه داده شود. این تعیین نمودن یک سیاست تصمیم گیری است. مشابه مشکلات زمانبندی – CPU ، سئوال اساساً یک موضوع اقتصادی است بایستی پردازشهایی را خاتمه دهیم که هزینه کمینه ای تحمیل می نمایند. متاسفانه واژه هزینه کمینه دقیقاً مشخص نیست. فاکتورهای بسیاری در انتخاب پردازش تعیین کننده اند از جمله :
1. اولویت پردازش چگونه است2. چه مدتی پردازش در حال محاسبه بوده است و چه مقدار عمل محاسباتی CPU باید صورت گیرد تا وظیفه پردازش کامل شود3. چه تعداد و چه نوع منابعی مورد استفاده پردازش قرار گرفته است (به عنوان مثال، آیا منابع برای پس دادن سهل هستند). 4. چه تعداد منابع بیشتر برای تکمیل پردازش مورد نیاز است5. چه تعداد پردازش لازم است خاتمه داده شود6. پردازش انتخابی دسته ای است یا محاوره ای. پس گرفتن منابع Resource Preemption برای حذف بن بست با استفاده از پس گرفتن منابع زودتر از موعد، متوالیا منابعی را از پردازش پس می گیریم و این منابع را به سایر پردازشها می دهیم تا سیکل بن بست باز شوداگرپس گرفتن منابع برای رفع بن بست ضروری باشد، آنگاه بایستی سه موضوع مشخص شوند1. انتخاب یک قربانی: چه منابعی و چه پردازشهایی باید پس داده شوند. همانند خاتمه دادن پردازش بایستی ترتیب پس دادن را برای هزینه مینیمم تعیین نماییم.فاکتورهای هزینه شامل پارامترهایی است از قبیل : تعداد منابعی که پردازش بن بست در اختیار دارد، میزان زمان یکه پردازش بن بست در حین اجرا صرف کرده است. 2. بازگرداندن به عقب : اگر منبعی از یک پردازش پس گرفته شود، با آن پردازش چه باید کرد؟ به وضوح اجرای نرمالش را نمی تواند ادامه دهد. تعدادی از منابع مورد نیازش را از دست داده است. بایستی پردازش را به حالت امنی به عقب باز گرداند و از آن حالت مجدداً آغازش نمود. چون در حالت کلی دشوار است تعیین نمود که حالت امن چیست ساده ترین راه حل بازگرداندن کامل است: پردازش رانیمه کاره متوقف نموده و سپس مجدداً از ابتدا آغازش کنید. اما موثرتر است که فقط به اندازه کافی دور، به عقب بازگردیم تا بن بست رفع شود. از سوی دیگر این روش ملزم می دارد که سیستم اطلاعات بیشتری درباره حالت کلیه پردازشهای در حال اجرا نگهداری نماید3. قحطی زدگی: چگونه اطمینان کنیم که قحطی زدگی رخ نخواهد داد؟ یعنی چگونه می توانیم تضمین نماییم که منابع همواره از یک پردازش خاصی پس گرفته نمی شوند؟ در سیستمی که انتخاب قربانی بر اسس فاکتورهای هزینه استوار است ممکن است پردازش یکسانی همواره به عنوان قربانی انتخاب گردد. در نتیجه این پردازش هرگز وظیفه محوله اش را به انجام نمی رساند – وضعیت قحطی زدگی که در هر سیستم کاربردی لازم است در مدنظر قرار گیرد. به وضوح بایستی تضمین نمود که یک پردازش به عنوان قربانی به دفعات محدودی (کم) برگزیده می شود. رایج ترین راه حل آن است که تعداد بازگردانهای به عقب را جزو فاکتورهای هزینه به حساب آوریم. رهیافت مرکب در اداره بن بست Combined Approach to Deadlock Handling محققین مباحثه کرده اند که هیچ یک از رهیافتهای اساسی برای اداره بن بست (پیشگیری، اجتناب و آشکار سازی) به تنهایی برای طیف گسترده مسائل تخصیص – منابع در سیستمهای عامل، مناسب نمی باشند. یک امکان آن است که سه رهیافت اساسی را ترکیب نماییم، تا رهیافت بهینه ای برای هر کلاس منابع سیستم به کار رود. روش پیشنهادی بر اساس این ایده استوار است که منابع می توانند بر حسب کلاسهایی که به ترتیب تسلسلی مرتب شده اند تقسیم بندی شود. یک تکنیک ترتیب – منابع به کلاسها اعمال می شود. درون هر کلاس مناسبترین تکنیم برای اداره بن بست می تواند به کار رود. سهل است نشان دهیم سیستمی که این استراتژی را به کار می گیرد در معرض بن بست قرار نخواهد گرفت. در واقع بن بست نمی تواند بیشتر از یک کلاس را دربر گیرد، زیرا تکنیک ترتیب – منابع به کار رفته است. درون کلاس، یکی از رهیافتهای اصلی به کار رفته است. در نتیجه سیستم در معرض بن بست قرار نمی گیرد. برای روشنگری این تکنیک، سیستمی را در نظر بگیری که شامل چهار کلاس منابع به شرح زیر باشد: • منابع داخلی: منابع مورد استفاده سیستم نظیر بلوک کنترل پردازش • حافظه اصلی: حافظه مورد استفاده توسط کاربر • منابع کار: وسایل منسوب (نظیر گرداننده نوار) و فایلها • فضای قابل جابه جایی: فضا برای هر کاربر بر روی ذخیره پشتیبان یک راه حل بن بست آمیخته برای این سیستم، کلاسها را به ترتیب نشان داده شده مرتب می نماید، و روشهای زیر را در هر کلاس به کار می برد• منابع داخلی : پیشگیری از طریق ترتیب منابع می تواند حاصل شود، زیرا انتخابهای زمان – اجرا مابین درخواستهای معوقه غیر ضروری می باشند• حافظه اصلی: پیشگیری از طریق پس دادن می تواند به کار رود زیرا یک کار همواره می تواند به دیسک مبادله شود و حافظه اصلی می تواند پس گرفته شود• منابع کار: اجتناب می تواند به کار رود زیرا اطلاعات مورد نیاز درباره ملزومات منبع می تواند از کارتهای کنترل کار به دست آید• فضای قابل جابه جایی: تخصیص – از – پیش می تواند به کار رود زیرا نیازهای ذخیره ماکزیمم معمولا مشخص می باشند این مثال نشان می دهد که چگونه رهیافتهای اساسی مختلف می توانند درون چهارچوب ترتیبمنابع آمیخته شوند،.