آموزش الگوریتم LRU نقص صفحه در سیستم عامل

امروز الگوریتم  LRU رو با یه مثال توضیح میدم، چون مباحث کامپیوتری رو بچه ها با ذکر مثال بهتر درک می کنند.

LRU اینطوری کار میکنه:"صفحه ای رو جایگزین کن که اخیراً کمترین استفاده از آن شده باشد." یعنی صفحه ای رو جایگزین کن که برای مدت طولانی توی صف مونده باشه.

فرض کنید رشته مراجعات با 3 قاب در حافظه اصلی به صورت زیر می باشد:(از چپ به راست)

4,3,2,1,4,3,5,4,3,2,1,5

توجه:دوستان من صفحه ای که برایش نقص صفحه رخ میده رو با رنگ سبز و صفحه ای که مدت طولانی تری در صف بوده رو ، با رنگ قرمز نشان میدهم.

بسار خب از چپ به راست سه صفحه اولی وارد حافظه میشه. چرا سه صفحه؟ چون حافظه ما دارای سه قاب است. و چون این صفحات جدید هستند و مثل اینها قبلاً صفحه ای در حافظه نبوده ، برای هر کدام یک نقص صفحه رخ میده و حافظه بدین صورت میشه                                                     2  3  4

خوُب حالا ما سه صفحه داریم که برا هر کدوم سه نقص رخ داده. همانطور که با رنگ سبز نشون دادم.

حالا صفحه بعدی که 1 هست وارد میشه.  سوال: جای کدوم صفحه قرار بگیره؟  جواب: چون ما از LRU استفاده میکنیم جای اونی قرار میگیره که بیشتر از همه تو حافظه بوده و کم تر استفاده شده. خوب اون کدومه؟ معلومه صفحه 4  .. پس 1 جای 4 میشینه، حالا 3 میشه آخرین صفحه مورد استفاده .پس از ورود 1 حافظه ایجوری میشه                                                                  2  3  1

همانطور که میبینید چون وقتی 1 وارد شد هیچ صفحه ای با این شماره وجود نداشت نقص صفحه براش رخ میده که رنگ سبز نشانگر این امر میباشه. و صفحه 3 که با قرمز مشخص کردم میشه آخرین صفحه ای که کم تر استفاده شده. صفحه بعدی که 4 هست وارد میشه. جای کدوم قرار میگیره... جای 3 چون آخرین صفحه ای است که مورد استفاده قرار گرفته و چون وقتی 4 وارد میشه ، صفحه ای با این شماره در بین صفحات نیست پس نقص صفحه داره. و حالا آخرین صفحه ای که مورد استفاده قرار گرفته ، 2 است،  یعنی حافظه اینجوری میشه:

                                                                                            2  4  1

همونطور میبینید 4 اومد جای 3 که آخرین صفحه ی مورد استفاده قرار گرفته بود میشینه و حالا 2 میشه آخرین صفحه ای که مورد استفاده قرار گرفته است. (خسته شدین اما پیشنهاد میکنم تا آخر مثال باشید یه جاییش باید دقت کنین که الآن میرسیم)

حالا صفحه ی بعدی که 3 هست وارد میشه ، دیگه میتونیم بفهمیم جای کدوم میشینه.. درست حدس زدین جای صفحه 2 که آخرین استفاده ازش شده میشینه و چون صفحه ای با شماره 3 در بین صفحات وجود نداره ، نقص صفحه دارد. و حالا بعد از قرار گرفتن 3 به جای 2 ، آخرین صفحه ای که مورداستفاده قرار گرفته 1 میباشد

میشه اینجوری                                                   3  4  1

حالا صفحه ی بعدی که 5 هست وارد میشه و جای 1 قرار میگیره و چون در صفحه وجود ندارد نقص صفحه براش رخ میده و حالا آخرین صفحه ای که مورد استفاده قرار گرفته میشه صفحه ی شماره 4

بعد از وارد شدن 5، حافظه اینجوری میشه                           3  4  5

حالا اینجا خیلی مهمه!!!  چرا؟  میگم.... صفحه شماره 4 وارد میشه و باید بشینه جای آخرین صفحه ی مورد استفاده قرار گرفته که 4 هست( همونی که رنگش قرمزه)  حالا چون 4  وجود داره دیگه این صفحه ی جدیدی که اینم 4 هست وارد نمیشه اما!!! دیگه این صفحه شماره 4ی که توی حافظه است آخرین صفحه ی مورد استفاده نیست!! چون به 4 رجوع شده و اون صفحه وارد شده با این مورد تطابق قرار گرفته. و از این به بعد آخرین صفحه ی مورد استفاده قرار گرفته، صفحه ی شماره 3 است یعنی صفحه ی جدید در صورت تکراری نبودن جای این 3 میشینه. بعد از ورود اون 4 و تطابق، حافظه اینجوری میشه          3  4  5    

صفحه ی بعدی که وارد میشه ، صفحه ی شماره 3 میباشه. اما این صفحه هم در صفحات قرار داره پس وارد نمیشه اما درسته که صفحه شماره 3 در حافظه که آخرین صفحه مورد استفاده است تغییری نمیکنه ولی از این به بعد آخرین صفحه ی مورد استفاده قرار گرفته، صفحه ی 5 است نه 3. بعد از وارد شدن صفحه ی شماره 3 که دید تکراری هست و وارد نمیشه حافظه اینجوری میشه                 3  4  5   

حالا صفحه بعدی میاد. اون صفحه ی شماره 2 میباشه.. چون تکراری نیست جای 5 که آخرین صفحه ی مورد استفاده است ، قرار میگیره. و نقص صفحه هم براش رخ میده و حالا آخرین صفحه مورد استفاده قرار گرفته 4 میشه.  اینجوری>>>>>>>>>                                                3  4  2

حالا صفحه بعدی که 1 هست وارد میشه و چون تکراری نیست جای 4 که آخرین صفحه ی مورد استفاده است ، قرار میگیره. و نقص صفحه هم براش رخ میده و حالا آخرین صفحه مورد استفاده قرار گرفته، 3 میشه.

و حافظه اینجوری میشه                                3  1  2

و در نهایت آخرین صفحه که 5 هست وارد میشه.. و جای 3 که آخرین صفحه ی مورد استفاده است ، قرار میگیره. و نقص صفحه هم براش رخ میده و حالا آخرین صفحه مورد استفاده قرار گرفته 2 است اما دیگه ما صفحه ای برای ورود نداریم. و حافظه اینجوری میشه                   5  1  2

حالا اگه بریم از بالا ، صفحات سبز رنگ رو (رنگ سبز نشان دهنده ی نقص صفحه بود) بشماریم ، میبینیم 10 صفحه سبز رنگ یعنی 10 نقص صفحه رخ داده است. حال همین تعداد قاب و صفحه در الگوریتم FIFO ،  9 نقص صفحه دارد.

منبع: alirezafc.blogfa.com