(۰۵ بهمن ۱۳۹۴ ۱۲:۳۶ ق.ظ)Black.Star نوشته شده توسط:  سلام
ما اینجا ۱۰ تا کار آماده برای اجرا در حال حاضر و با مقدار مشخص حافظه در اختیار داریم، از طرفی هم چهار ناحیه از حافظه برای قرار گرفتن این کارها در نظر گرفته شده. با توجه به شرط سوال برای بلوکه نشدن کارهای بزرگ، ما سعی می‌کنیم بزرگ‌ترین کار ممکن که داخل اون خونه حافظه جا میشه رو بهش تخصیص بدیم، پس ما در وهله تو اون جدول فقط به حافظه مورد نظر کارها نگاه می‌کنیم.

مرحله - ۱
برای مثال در اولین مرحله مناسب‌ترین کار برای خونه اول حافظه یعنی B0=20KB کدومه؟ اونی که نزدیک‌ترینه بهش و بیشترین استفاده رو می‌تونه ازش داشته باشه (با بیشترین صرفه جویی در مصرف حافظه) یعنی J7=19KB (نزدیک‌تر از ۱۹ به ۲۰ که نداریم، داریم؟) یا برای خونه دوم حافظه یعنی B1=30KB چی؟ خب مسلما J9=21KB ! و به همین ترتیب برای B2=30KB داریم: J2=29KB و برای آخری یعنی B3=50KB داریم: J6=49KB ... .

خب الان چهار تا کار تو حافظه قرار دادیم که طبق صورت سوال اولویت اجرا با ایناست، پس تا اتمام کارشون تو حافظه می‌مونن و فقط موقعی خارج میشن که تموم بشن. پس از اینجا به بعد حواسمون باید به ستون آخر جدول صورت سوال هم باشه (زمان ماندگاری کارها در حافظه)، ما از زمان صفر شروع کردن بودیم و زمان اجرای کارهایی که وارد شدن اینطوری بود: J7=5KB و J9=15KB و J2=5KB و J6=10KB . خب پس اولین زمان خروج ما ثانیه پنج هست چون دو تا از کارهامون زمان اجراشون ۵ ثانیه هست که در نتیجه باید با کارهای J7 و J2 خداحافظی کنیم و حافظه مربوط به اون‌ها یعنی B0=20KB و B2=30KB رو آزاد کنیم.

مرحله - ۲
حالا تو مرحله دوم دو تا کار جدید رو طبق همون الگوریتم بیشترین صرفه جویی جایگزین خونه‌های خالی حافظه می‌کنیم:

B0=20KB که خالی شده رو به J8=16KB تخصیص می‌دیم که از همه بهش نزدیک‌تره.
B2=30KB که خالی شده رو هم به J1=18KB تخصیص می‌دیم که از همه بهش نزدیک‌تره.

خب دوباره زمان جلو میره و پنج ثانیه می‌گذره و روی ثانیه ۱۰ ایست می‌کنه تا بفهمیم زمان کار J6=10 که از اولین کارهای وارد شده بود تموم شده و باید باهاش خداحافظی می‌کنیم.

مرحله - ۳
بهترین انتخاب ما برای جایگزین کردنش توی خونه B3=50KB چیزی جز J4=33KB نیست، چون از این نزدیک‌تر دیگه به ۵۰KB نداریم!

خب زمان جلو میره و پنج ثانیه دیگه می‌گذره و روی ثانیه ۱۵ ایست می‌کنه تا بفهمیم زمان کارهای J8=10KB و J9=15KB و J1=10KB با هم به پایان رسیده و باید با همشون خداحافظی کنیم.

مرحله - ۴
حالا بهترین انتخاب‌های ما چیه؟ ما دقیقا سه کار باقیمونده (J3 و J5 و J10) و سه خونه خالی (B0 و B1 و B2) داریم، پس بهترین انتخاب‌های ما می‌تونه این شکلی باشه: کار J3=10KB می‌تونه داخل خونه B0=20KB قرار بگیره، کار J5=14KB هم می‌تونه داخل B1=30KB یا B2=30KB قرار بگیره، اما مشکل اینجاست که J10=31KB به هیچ عنوان تو هیچ خونه‌ای از حافظه جا نمیشه! فقط تو آخری (B3=50KB) جا میشه که اونم پر شده! پس تنها چاره‌اش اینه که تا اتمام B3 انتظار بکشه!

خب زمان جلو میره و روی ثانیه ۲۵ ایست می‌کنه تا بفهمیم J4=15KB تموم شده و باید بره بیرون و به جاش B3=31KB که مدتی منتظر بود بیاد داخل!

مرحله - ۵
در ادامه هم J5=14KB در زمان ۳۰ از حافظه خارج میشه!

مرحله - ۶
و نهایتا کارهای J3=20KB و J10=31KB بعد از اتمام زمان اجرای خودشون و راس ثانیه ۳۵ از حافظه خداحافظی می‌کنند تا دیگه کاری در سیستم نداشته باشیم و گزینه چهارم رو به عنوان پاسخ انتخاب کنیم.

* هر مرحله به معنی یک توقف زمانی هست، ما در این سوال مجموعا شش مرحله توقف بین بازه‌های ۵ ثانیه‌ای داشتیم. برای حل اینطور سوالات بهتره از همون جدول پاسخنامه کتاب پارسه و به صورت گام به گام با خط زدن Job پایان یافته و کسر کردن زمان باقی‌مونده Job های فعلی استفاده کرد.