الگوریتم جایگزینی صفحه LRU در سی پلاس پلاس ++C

الگوریتم های جایگزینی صفحه

الگوریتم جایگزینی صفحه LRU که مخفف Least Recently Used  یعنی اخیراً کمتر استفاده شده می‌‎باشد یکی از مهم‌‎ترین الگوریتم‌های جایگزینی صفحه است. صفحه‌بندی وقتی انجام می‌شود که یک خطای نقص صفحه یا Page fault اتفاق افتاده و صفحه خواسته شده را نتوان اختصاص داد. در ادامه به توضیح این الگوریتم پرداخته می‌‍شود.

قبل از کد نویسی الگوریتم جایگزینی صفحه LRU در سی پلاس پلاس ++C بایستی از کلیات مبحث الگوریتم‌های جایگزینی صفحه اطلاعاتی را داشته باشید. همانطور که قبلاً هم بیان شد صفحه‌بندی وقتی انجام می‌شود که یک خطای نقص صفحه اتفاق افتاده و صفحه خواسته شده را نتوان اختصاص داد، یا به این دلیل که هیچ صفحه خالی در حافظه نیست یا به این دلیل که تعداد صفحات خالی کمتر از حد آستانه است.

(در بعضی از سیستم‌ها همواره تعدادی صفحه خالی در حافظه نگه‌داری می‌شود تا نیاز کمتری به فراخوانی الگوریتم جایگزینی صفحه باشد) در این حالت برای آوردن صفحه جدید به حافظه، مجبور هستیم صفحاتی را از حافظه خارج کرده و در دیسک بنویسیم تا فضای کافی برای اختصاص صفحه جدید فراهم شود.

مراحل انجام این کار بدین صورت است که صفحه‌ای که برای جایگزینی انتخاب شده از حافظه اصلی خارج شده و در دیسک نوشته می‌شود. سپس صفحه خواسته شده توسط برنامه از دیسک برداشته شده و در مکان صفحه قبلی نوشته می‌شود. ممکن است صفحه‌ای که برای جایگزینی انتخاب شده مجدداً توسط برنامه مورد ارجاع قرار گیرد و نیاز باشد تا صفحه بار دیگر از دیسک به حافظه آورده شود. آوردن یک صفحه از دیسک عملی به مراتب زمانبر است چرا که سرعت دیسک از سرعت حافظه اصلی کمتر است.

بنابراین الگوریتمی از همه بهتر است که عمل ورودی/خروجی در آن اندک باشد.

الگوریتم LRU یا همان اخیراً کمتر استفاده شده هر چند که در نام مشابه NFU یا (Not Frequently Used) است اما در عمل با آن متفاوت است. تفاوت آن‌ها در این است که LRU میزان استفاده صفحات را در یک بازه زمانی کوتاه پیگیری می‌کند اما NFU تنها به میزان استفاده صفحات در آخرین وقفه ساعت نگاه می‌کند. ایده اصلی LRU آن است که صفحاتی که در چند لحظه گذشته به شدت مورد استفاده قرار گرفته‌اند، در چند لحظه آینده هم به شدت مورد استفاده خواهند بود.

در این الگوریتم وقتی که یک نقص صفحه اتفاق می‌افتد، صفحه‌ای از حافظه خارج می‌شود که نسبت به دیگر صفحات، مدت طولانی‌تری بلااستفاده بوده است. در حالی که به صورت تئوری الگوریتم LRU می‌تواند تقریباً به اندازه الگوریتم بهینه کارایی داشته باشد، پیاده‌سازی آن در عمل مشکل است. تعدادی روش پیاده‌سازی برای این الگوریتم وجود دارد که سعی می‌کنند هزینه پیاده‌سازی را کاهش دهند، بدون اینکه افت قابل توجهی در کارایی الگوریتم ایجاد شود.

پرهزینه‌ترین روش، استفاده از یک لیست پیوندی است که تمام صفحات موجود در حافظه را در بر می‌گیرد. در انتهای این لیست، صفحاتی با کمترین میزان استفاده قرار دارند و در ابتدای لیست هم صفحاتی با بیشترین میزان استفاده قرار دارند. مشکل اصلی این گونه پیاده‌سازی این است که صفحات موجود در لیست باید در هر بار دستیابی به حافظه در لیست جابجا شوند که عملی بسیار هزینه بر است.

سورس کد lru چیست

الگوریتم جایگزینی صفحه LRU به زبان ++C در نرم افزار ++DEV C نوشته شده است. این سورس کد در واقع یک برنامه کنسولی است. در این سورس کد نحوه انجام الگوریتم LRU برای جایگزنی مناسب نشان داده شده است در ادامه تصویر خروجی این اثر قابل مشاهده است.

درباره الگوریتم جایگزینی صفحه LRU

برنامه الگوریتم جایگزینی صفحه LRU به زبان سی پلاس پلاس اثری است که در این پست به آن پرداخته شده است. این اثر در محیط ++Dev-C نوشته شده است. این سورس کد بصورت کامل توسط گروه پشتیبانی پی استور تست و بازبینی شده و دارای کامنت گذاری برای هر دستور می‌باشد. این سورس کد دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر آن را خریداری کنید.