من هر چی این موضوع رو می خونم نمی فهمم چه از روی کتاب پارسه چه از روی مقسمی لطفا اگه کسی می تونه این مطلب رو توضیح بده ممنون می شم
سلام. موضوع پیچیده ای نیست.
یکی از راههای پیاده سازی سخت افزاری الگوریتم LRU استفاده از یک ماتریس n*n هست. وقتی n قاب صفحه در اختیار داریم، سخت افزار می تواند یک ماتریس n*n ایجاد کند که در ابتدای کار همه خانه های ان عدد ۰ هست. هنگامی که به یک قاب صفحه رجوع میشه """" همه بیت های سطر مربوطه عدد یک"""" و """"همه بیت های ستون مربوطه عدد صفر"""" می گیرند. و برای بار بعدی وقتی که مراجعه به صفحه ای شود که هم اکنون در حافظه نیست، صفحه ای (یا به عبارت بهتر) سطری انتخاب می شود که معادل عدد دودویی ان از همه سطر های دیگه کمتر باشه.
یک مثال : اگر تعداد قاب صفحه برابر ۴ باشد و رشته مراجعات به صفحه از چپ به راست به صورت ۰/۱/۲/۳/۱/۴ باشد، دسترسی به صفحات چگونه است؟
جواب: همونطور که از صورت مساله پیداست، تعدا قابها ۴ تا هستند، پس نیاز به یک ماتریس ۴*۴ هست که در ابتدای کار همه خانه ها صفر هستند. وقتی مراجعه به صفحه ۰ انجام می گیره، همه خانه های سطر اول برابر ۱ و همه خانه های ستون اول برابر ۰ خواهند بود (پس سطر اول برابر ۰۱۱۱ خواهد بود). حالا که به صفحه شماره ۱ مراجعه میشه همه خانه های سطر دوم برابر با یک و همه ستون های سطر دوم برابر ۰ خواهد بود (توجه داشته باش که این عدد گذاری برای مراجعه به صفحه شماره ۱، روی سطر اول ماتریس هم اثر گذاشته و از ۰۱۱۱ به ۰۰۱۱ تغییر پیدا می کند، دلیلش هم عدد گذاری برای صفحه شماره ۱ است). وبه همین صورت برای صفحات شماره ۲ و ۳ هم این عدد گذاری انجام میشود. در زیر مرحله به مرحله ماتریس رو می کشم:
(درخواست صفحه ۰ در ابتدای کار)
۰۱۱۱
۰۰۰۰
۰۰۰۰
۰۰۰۰
(درخواست صفحه ۱)
۰۰۱۱
۱۰۱۱
۰۰۰۰
۰۰۰۰
(درخواست صفحه ۲)
۰۰۰۱
۱۰۰۱
۱۱۰۱
۰۰۰۰
(درخواس صفحه ۳ و آخرین صفحه، چون تعداد قابها برابر ۴ است)
۰۰۰۰
۱۰۰۰
۱۱۰۰
۱۱۱۰
(دوباره نوبت به صفحه شماره ۱ میرسه و چون این صفحه وجود داره پس اعداد همون سطر که قبلا ذخیره شده مقدار میگیرن)
۰۰۰۰
۱۰۱۱
۱۰۰۰
۱۰۱۰
حالا که نیاز به صفحه ۴ هست و صفحه خالی وجود نداره و صفحه ۴ هم قبلا بارگذاری نشده پس طبق قانون، سطری که مقدار دودویی اون از همه کمتره برای جایگذاری انتخاب میشه. (یعنی سطر اول)
پس با ورود صفحه شماره ۴ ماتریس بصورت :
۱۰۰۰
۰۰۱۱
۰۰۰۰
۰۰۱۰
تا اونجا که تونستم واضح توضیح دادم
اگه باز مشکلی داشتید بپرسید در خدمت خواهیم بود.موفق باشید.
ممنون که جواب دادید کاملا متوجه شدم