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

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

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

الگوریتم بهینه

این الگوریتم فقط به صورت تئوری بوده و قابل پیاده‌سازی نیست. چرا که برای پیاده‌سازی آن احتیاج به پیش‌بینی آینده است که در عمل امکان‌پذیر نیست. این الگوریتم مشکل ناهنجاری بلیدی را ندارد. در این الگوریتم سیستم‌عامل صفحه‌ای را برای جایگزینی انتخاب می‌کند که در آینده، دیرتر از همه به آن نیاز خواهد شد. به عنوان مثال فرض کنید دو صفحه داریم که به یکی از آنها تا ۶ ثانیهٔ آینده، و به دیگری تا ۰٫۴ ثانیهٔ آینده احتیاج نداریم. در اینجا صفحه اول جایگزین می‌شود. به دلیل اینکه در این الگوریتم نیاز به پیش‌بینی آینده وجود دارد، قابل پیاده‌سازی نیست. اما کارایی آن از همه الگوریتم‌ها به مراتب بالاتر است.

اخیراً استفاده نشده

در الگوریتم اخیراً استفاده نشده (به انگلیسی: Not recently used)، صفحه‌ای جایگزین می‌شود که اخیراً کمتر از همه مورد استفاده قرار گرفته است. این الگوریتم صفحاتی که اخیراً مورد استفاده قرار گرفته‌اند را در حافظه نگه می‌دارد. این الگوریتم بدین شکل کار می‌کند: در جدول صفحه، هر صفحه دارای چند بیت کنترلی است. مثل «بیت دستیابی» یا «بیت تغییر». وقتی که یک صفحه مورد دسترسی قرار می‌گیرد (از آن استفاده می‌شود)، بیت دستیابی آن صفحه ۱ می‌شود. به این معنی که صفحه استفاده شده است. به طور مشابه، وقتی که اطلاعات صفحه‌ای تغییر می‌کند، «بیت تغییر» مربوط به آن صفحه هم ۱ می‌شود تا نشان دهد اطلاعات صفحه دستکاری شده است. این بیت‌ها معمولاً توسط سخت‌افزار تغییر می‌کنند، هر چند که می‌توان آنها را به کمک نرم‌افزار هم تغییر داد.

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

۳: استفاده شده، تغییر کرده

۲: استفاده شده، تغییر نکرده

۱: استفاده نشده، تغییر کرده

۰: استفاده نشده، تغییر نکرده

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

همچنین ممکن است این سؤال پیش بیاید که چگونه یک صفحه تغییر کرده اما مورد دستیابی قرار نگرفته؟ (گروه ۱) این حالت وقتی پیش می‌آید که در گروه ۳، وقفه ساعت بیت دستیابی یک صفحه را صفر کرده باشد. وقفه ساعت بیت تغییر را صفر نمی‌کند زیرا این بیت نشان‌دهنده این مسئله است که آیا صفحه مورد نظر باید بر روی دیسک نوشته شود یا خیر.

الگوریتم FIFO

اولین ورودی، اولین خروجی (به انگلیسی: First in, First out) ساده‌ترین الگوریتم صفحه‌بندی است. در این الگوریتم صفحه‌ای از حافظه خارج می‌شود که از همه زودتر وارد حافظه شده باشد. به عبارت دیگر، صفحه‌ای که از همه قدیمی‌تر باشد از حافظه خارج می‌شود تا فضا برای صفحه جدید محیا شود. منطق این روش آن است که صفحه‌ای که زودتر از همه به حافظه آورده شده، احتمالاً برنامه کار خود را با آن به اتمام رسانده و در آینده دیگر به آن احتیاج نیست. این الگوریتم ساده است و سربار کمی به سیستم‌عامل تحمیل می‌کند. این الگوریتم دارای مشکل ناهنجاری بلیدی است و خیلی کم از آن استفاده می‌شود. الگوریتم FIFO توسط یک صف پیاده‌سازی می‌شود. هر صفحه‌ای که در جلوی صف قرار گرفته باشد، با صفحه جدید جایگزین می‌شود.

الگوریتم دومین شانس

این الگوریتم مشابه الگوریتم FIFO است اما با یک تغییر کوچک که باعث می‌شود کمی کارایی آن بالاتر برود. در این الگوریتم، هر صفحه دارای یک «بیت دستیابی» است. هر وقت که صفحه مورد دستیابی قرار گرفت (از آن استفاده شد)، این بیت توسط سخت‌افزار ۱ می‌شود. مانند الگوریتم FIFO، صفحه‌ای که در جلوی صف قرار داشته باشد حذف می‌شود. اما به جای آنکه صفحه مورد نظر بی درنگ حذف شود، سیستم‌عامل ابتدا به «بیت دستیابی» آن صفحه نگاه می‌کند، اگر بیت دستیابی صفر بود، صفحه حذف می‌شود. اما اگر بیت دستیابی ۱ بود، سیستم‌عامل آن بیت را صفر کرده و صفحه را به انتهای صف منتقل می‌کند. (انگار یک صفحه جدید وارد حافظه شده) این پروسه به همین ترتیب ادامه می‌یابد. بدین ترتیب صفحه مورد نظر شانس دوباره‌ای برای باقی ماندن در حافظه کسب کرده است. می‌توان این صف را مانند یک صف حلقوی فرض کرد که ابتدای صف به انتهای آن متصل است. اگر بیت دستیابی تمام صفحات ۱ بود، آنگاه الگوریتم شانس دوم هم به مانند الگوریتم FIFO عمل می‌کند.

الگوریتم ساعت

الگوریتم ساعت هم بر اساس الگوریتم FIFO است، اما از الگوریتم شانس دوم موثرتر است. زیرا لازم نیست صفحات به طور مدام در انتهای صف گذاشته شوند. اما کارکرد اصلی آن مشابه الگوریتم شانس دوم است. الگوریتم ساعت، یک لیست حلقوی از صفحات را در حافظه نگه می‌دارد. «عقربه» ساعت هم به آخرین صفحه بررسی شده اشاره می‌کند. اگر یک نقص صفحه رخ دهد و قاب خالی هم در حافظه وجود نداشته باشد، آنگاه بیت دستیابی در صفحه‌ای که عقربه به آن اشاره می‌کند بررسی می‌شود. اگر بیت دستیابی صفر بود، صفحه حذف می‌شود و صفحه جدید در جایی که عقربه به آنجا اشاره می‌کند قرار می‌گیرد. در غیر این صورت اگر بیت دستیابی ۱ بود، انگاه این بیت صفر شده و عقربه یک واحد افزایش می‌یابد و به عنصر بعدی در صف اشاره می‌کند. این پروسه آن قدر تکرار می‌شود تا یک صفحه برای جایگزینی پیدا شود.

اخیراً کمتر استفاده شده

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

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

یک روش پیاده‌سازی دیگر که احتیاج به پشتیبانی سخت‌افزار دارد به صورت زیر است: سخت‌افزار یک شمارنده ۶۴ بیتی دارد که با اجرای هر دستورالعمل یک واحد به این شمارنده افزوده می‌شود. همینطور هر صفحه هم شمارنده مخصوص به خود را دارد. هر وقت که صفحه‌ای مورد دستیابی قرار گرفت، صفحه مورد نظر مقداری برابر با مقدار شمارنده در لحظه دستیابی بدست می‌آورد (مقدار شمارنده اصلی در شمارنده صفحه مورد نظر کپی می‌شود). هرگاه که نیاز به جایگزینی یک صفحه است، سیستم‌عامل صفحه‌ای که کمترین شمارنده را دارد را انتخاب می‌کند. با استفاده از سخت‌افزارهای فعلی، پیاده‌سازی چنین چیزی امکان‌پذیر نیست. زیرا سیستم‌عامل نیاز به بررسی شمارنده برای هر صفحه در حافظه نهان دارد.

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

الگوریتم تصادفی

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

کمتر استفاده شده

الگوریتم کمتر استفاده شده (به انگلیسی: Not frequently used) به شمارنده احتیاج دارد. در این الگوریتم هر صفحه شمارنده مخصوص به خود را دارد که این شمارنده در ابتدا بر روی صفر تنظیم شده است. یک ساعت هم در سیستم وجود دارد که هر چند لحظه یک بار فعال می‌شود و یک وقفه ایجاد می‌کند. شمارندهٔ صفحاتی که در این بازه زمانی مورد استفاده قرار گرفته‌اند، یک واحد افزایش می‌یابد. (در عمل، شمارنده با بیت دستیابی صفحه جمع می‌شود) در واقع، شمارنده‌ها تعداد دفعات استفاده از صفحات را نگه می‌دارند. در نتیجه صفحاتی که شمارنده آنها پایینتر از همه است جایگزین می‌شوند.

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

هنگامی که جدول صفحه دربرگیرنده مقادیر اشاره‌گر تهی است، الگوریتم NFU کارایی بهتری نسبت به LFU دارد.

الگوریتم سالخوردگی

این الگوریتم مشابه NFU است. اما تغییری در آن ایجاد شده تا از مدت زمان استفاده هم آگاه باشد. در این الگوریتم هر صفحه برای خود یک شمارنده دارد. یک وقفه ساعت هم در سیستم وجود دارد که هر چند لحظه فعال می‌شود. وقتی که این وقفه فعال شد، شمارنده صفحات یک واحد به سمت راست شیفت داده می‌شود. در اثر این شیفت، بیت سمت راست به بیرون می‌افتد و از بین می‌رود و بیت سمت چپ شمارنده هم با بیت دستیابی پر می‌شود. به عنوان مثال اگر بیت دستیابی یک صفحه در شش تیک آخر ساعت به صورت ۱٫۰٫۰٫۱٫۰٫۰ باشد، شمارنده دستیابی به شکل ۱۰۰۰۰۰۰۰، ۰۱۰۰۰۰۰۰، ۰۰۱۰۰۰۰۰، ۱۰۰۱۰۰۰۰، ۱۱۰۰۱۰۰۰، ۰۱۱۰۰۱۰۰ است. صفحاتی که به تازگی مورد دستیابی واقع شده‌اند، نسبت به صفحاتی که در گذشته دورتر مورد دستیابی واقع شده‌اند، اولویت بیشتری دارند. این ویژگی تضمین می‌کند که صفحاتی که به تازگی دستیابی شده‌اند، هر چند که تعداد دفعات دستیابی به آنها اندک باشد، اولویت بیشتری نسبت به صفحاتی دارند که در گذشته دور به طور مکرر مورد دستیابی قرار گرفته‌اند. در نتیجه وقتی که قرار است صفحه‌ای برای جایگزینی انتخاب شود، سیستم‌عامل صفحه‌ای را برمی‌دارد که دارای کمترین شمارنده است.

دقت کنید که الگوریتم سالخوردگی با الگوریتم NFU متفاوت است. چرا که الگوریتم سالخوردگی، تنها ۱۶ یا ۳۲ ارجاع آخر را نگه می‌دارد. (این مقدار به پردازنده وابسته است) در نتیجه، شمارنده دستیابی دو صفحه می‌تواند ۰۰۰۰۰۰۰۰ باشد، حتی اگر یکی از آنها ۹ واحد زمانی قبل و دیگری ۱۰۰۰ واحد زمانی قبل مورد دستیابی واقع شده باشند. به طور کلی، داشتن اطلاعات دستیابی به صفحات در طول ۱۶ واحد زمانی قبل مناسب و کافی بوده و به این ترتیب می‌توان گفت کارایی الگوریتم سالخوردگی به الگوریتم بهینه نزدیک است.

مشارکت‌کنندگان ویکی‌پدیا. «Page replacement algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۴ ژوئیه ۲۰۱۳.