سلام. ممنون میشم اینا رو برام توضیح بدین:
اگه سه قاب ازاد داشته باشیم و صفحات مجازی به ترتیب از چپ به راست تقاضا شه با الگوریتم های بهینه lru و fifo چند نقص صفحه داریم؟
۲/۳/۱/۲/۴/۳/۱/۵/۲/۴/۲/۳/۵/۲
سلام
FIFO = 7
LRU = 11
سلام الگوریتم fifo چکار میکنه؟fifo که مخفف first in first out می باشد صفحه ای را جایگزین میکند که قدیمی ترین صفحه در حافظه می باشد. مثل یه صف نانوایی میمونه اونی که اول میاد اول خارج میشه میگیره
حالا نقص صفحه چیه ؟اگر صفحه ای وارد حافظه شود و ببیند که صفحه ای مثل خودش در حافظه نیست بنابراین یک نقص صفحه رخ می دهد.اما اگر آن صفحه ی آمده ببیند که یک صفحه مثل خودش قبلاً در حافظه وارد شده و اکنون نیز در حافظه وجود دارد ،این صفحه ی تکراری دیگر نقص صفحه ندارد.
خب حالا حل مسئله با الگوریتم fifo
صفحات ۲و۳و۱ به ترتیب از چپ به راست وارد می شوند و چون قبل از این در حافظه نبوده اند پس سه تا نقص صفحه رخ می دهد. حافظه ـــــ> ۲و۳و۴ تعداد نقص تا اینجا: ۳
بسیار خب. صفحه بعدی که وارد می شود، صفحه شماره ۲ می باشد. اما چون داخل حافظه است هیچ نقص صفحه رخ نمیدهد و میریم سراغ ورود صفحه ۴
اما حافظه ی ما سه قاب دارد و آن سه تا هم توسط ۲و۳و۱ پر شده اند.تکلیف چیست؟؟؟؟
باید یکی از صفحات خارج شود تا جا برای ۴ باز شود.کدام صفحه را خارج کنیم؟؟
خیلی ساده به نوع الگوریتم نگاه می کنیم، میبینیم fifo می باشد. طبق این الگوریتم صفحه ای را خارج می کنیم که قدیمی ترین صفحه است...به نظر شما کدام صفحه قدیمی ترین است... نگاه کنید ــــــــ> ۲و۳و۱ صفحه ی شماره ۲ اولین و در نهایت قدیمی ترین است پس ۴ با اون جایگزین می شود.
و چون در حافظه صفحه یکی وجود نداشت ۴ جای ۲ می نشیند و نقص صفحه هم رخ می دهد.
حافظه ـــــــ> 4و۳و۱ تعداد نقص تا اینجا:۴
همینجور الگوریتمو ادامه بده
داخل عکس روند کاملش هستش
حالا LRU
LRU اینطوری کار میکنه:"صفحه ای رو جایگزین کن که اخیراً کمترین استفاده از آن شده باشد." یعنی صفحه ای رو جایگزین کن که برای مدت طولانی توی صف مونده باشه.
عکس روند هردو الگوریتمو کشیدم برات با مداد رنگی
انشالله که متوجه بشیمهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از راهنمایی تون و توضیح خوبتون.
میشه بهینه رو هم بگید
(۱۲ تیر ۱۳۹۴ ۰۵:۳۴ ب.ظ)maryam.iii نوشته شده توسط: خیلی ممنون از راهنمایی تون و توضیح خوبتون.
میشه بهینه رو هم بگید
خواهش میکنم
فقط کاش تایپیک جدا میزدی ببین درمورد الگوریتم بهینه دقیقا همون کار LRUرو انجام میده ولی این به جای نگاه به گذشته به آینده نگاه میکنه و صفحه ای رو از حافظه خارح میکنه که در اینده دورتری بهش مراجعه میشه
مرحله اول سه تا صفحه ۲,۳,۱ با سه نقص صفحه وارد میشن
در مرحله بعدصفحه ۲ داخل حافظه است پس نقص صفحه ای اتفاق نمیفته
در مرحله بعد صفحه ۴ که میخواد وارد بشه باید صف صفحاتی که در اینده میخوان وارد بشنرو نگاه کنه و اون صفحه ای که داخل حافظه است و نسبت به باقی صفحات داخل حافظه دیرتر بهش رجوع میشه رو از حافظه خارج کنه.الان اینجا ۲ دیرتر از ۳ و ۱ بهش مراجع میشه پس ۲ رو میندازه بیرون.الان صفحات داخل حافظه ۴,۳,۱
در مرحله بعد صفحات ۳ , ۱ هم وارد میشن بدون هیچ نقص صفحه ای و نوبت به ورود صفحه ۵ میشه میبینه در اینده اصلا به ۱ مراجعه نمیشه پس ۱ رو میندازه بیرون
با همین رواال بقیه صفحات هم وارد میشن.این الگوریتم رویکردش به اینده است.متوجه نشدی بگو برات بکشم
این الگوریتم
خیلی ممنون از لطفتون. فقط وقتی اعداد ۲و۵ موندن دو عددد اخر . حافظه با اعداد ۲و۳و۴ پر شده ۵ میخواد بیاد تو ۲ رو که نمیشه حذف کرد بین ۴ و ۳ دیگه هیچ کدوم تو صف نیستن ۵ رو جایگزین اولی یعنی ۴ میکنه؟؟؟
(۱۳ تیر ۱۳۹۴ ۰۱:۱۷ ق.ظ)maryam.iii نوشته شده توسط: خیلی ممنون از لطفتون. فقط وقتی اعداد ۲و۵ موندن دو عددد اخر . حافظه با اعداد ۲و۳و۴ پر شده ۵ میخواد بیاد تو ۲ رو که نمیشه حذف کرد بین ۴ و ۳ دیگه هیچ کدوم تو صف نیستن ۵ رو جایگزین اولی یعنی ۴ میکنه؟؟؟خواهش میکنم
بله اینجه دیگه خیلی مهم نیست کدوم خارج بشه ولی معمولا اونی که قدیمی تره خارج میشه. چون خواه ناحواه نقص صفحه اتفاق میفته ولی خب اونی که طولانیمدت داخل صف بوده رو خارج میکنیم.
(۱۳ تیر ۱۳۹۴ ۰۱:۲۶ ق.ظ)so@ نوشته شده توسط:ممنون بابت توضیح عالیتون دمت گرم(13 تیر ۱۳۹۴ ۰۱:۱۷ ق.ظ)maryam.iii نوشته شده توسط: خیلی ممنون از لطفتون. فقط وقتی اعداد ۲و۵ موندن دو عددد اخر . حافظه با اعداد ۲و۳و۴ پر شده ۵ میخواد بیاد تو ۲ رو که نمیشه حذف کرد بین ۴ و ۳ دیگه هیچ کدوم تو صف نیستن ۵ رو جایگزین اولی یعنی ۴ میکنه؟؟؟خواهش میکنم
بله اینجه دیگه خیلی مهم نیست کدوم خارج بشه ولی معمولا اونی که قدیمی تره خارج میشه. چون خواه ناحواه نقص صفحه اتفاق میفته ولی خب اونی که طولانیمدت داخل صف بوده رو خارج میکنیم.
(۱۳ تیر ۱۳۹۴ ۰۱:۲۶ ق.ظ)so@ نوشته شده توسط:ممنون بابت توضیح عالیتون دمت گرم(13 تیر ۱۳۹۴ ۰۱:۱۷ ق.ظ)maryam.iii نوشته شده توسط: خیلی ممنون از لطفتون. فقط وقتی اعداد ۲و۵ موندن دو عددد اخر . حافظه با اعداد ۲و۳و۴ پر شده ۵ میخواد بیاد تو ۲ رو که نمیشه حذف کرد بین ۴ و ۳ دیگه هیچ کدوم تو صف نیستن ۵ رو جایگزین اولی یعنی ۴ میکنه؟؟؟خواهش میکنم
بله اینجه دیگه خیلی مهم نیست کدوم خارج بشه ولی معمولا اونی که قدیمی تره خارج میشه. چون خواه ناحواه نقص صفحه اتفاق میفته ولی خب اونی که طولانیمدت داخل صف بوده رو خارج میکنیم.