الگوریتم least recently used

الگوریتم least recently used" href="http://wikiprojects.ir/downloads/%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-least-recently-used/">

توضیح الگوریتم least recently used :
اخیرا میباشد که میزان استفاده صفحات را در یک بازه ً الگوریتم LRU یا سیاست کمتر استفاده شده
زمانی کوتاه پیگیری میکند یده اصلی LRU آن است که صفحاتی که در چند لحظه گذشته به شدت مورد
استفاده قرار گرفتهاند، در چند لحظه آینده ھم به شدت مورد استفاده خواھند بود. در این الگوریتم وقتی که یک
نقص صفحه اتفاق میافتد، صفحهای از حافظه خارج میشود که نسبت به دیگر صفحات، مدت طولانیتری
ً بلااستفاده بوده است. در حالی که به صورت تئوری الگوریتم LRU می به اندازه الگوریتم بھینه کارایی
تواند تقریبا
داشته باشد، پیادهسازی آن در عمل مشکل است. تعدادی روش پیادهسازی برای این الگوریتم وجود دارد که
سعی میکنند ھزینه پیادهسازی را کاھش دھند، بدون اینکه افت قابل توجھی در کارایی الگوریتم ایجاد شود.
پرھزینهترین روش، استفاده از یک لیست پیوندی است که تمام صفحات موجود در حافظه را در بر میگیرد. در
انتھای این لیست، صفحاتی با کمترین میزان استفاده قرار دارند و در ابتدای لیست ھم صفحاتی با بیشترین
میزان استفاده قرار دارند. مشکل اصلی این گونه پیادهسازی این است که صفحات موجود در لیست باید در ھر
بار دستیابی به حافظه در لیست جابجا شوند که عملی بسیار ھزینه بر است.
بنابراین برای پیاده سازی از یک کلاس به نام Page که دارای شماره و یک عدد برای نشان دادن اولویت و ھمچنین
از ارایه ھای پویا یعنی وکتور برای پیاده سازی این الگوریتم استفاده کردیم
مثال براي الگوریتم:
ترتیب صفحات به صورت ذیل میباشد (از چپ یه راست):
ترتیب 1 2 3 4 5 6 7 8 9 10 11 12
صفحھ 4 3 2 1 4 3 5 4 3 2 1 5
الویت 0 0 0 0 0 0 0 0 0 0 0 0
حل با الگوریتم LRU :

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

RIAL 75,000 – خرید
0
اشتراک‌گذاری
admin