موضوع مقاله: الگوریتم جایگزینی صفحه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم جایگزینی صفحه | مقدمه: صفحه‌بندی وقتی انجام می‌شود که یک خطای نقص صفحه اتفاق افتاده و صفحه خواسته شده را نتوان اختصاص داد، یا به این دلیل که هیچ صفحه خالی در حافظه نیست یا به این دلیل که تعداد صفحات خالی کمتر از حد آستانه است. | ## بخش 1: الگوریتم جایگزینی صفحه | (در بعضی از سیستم‌ها همواره تعدادی صفحه خالی در حافظه نگه‌داری می‌شود تا نیاز کمتری به فراخوانی الگوریتم جایگزینی صفحه باشد) در این حالت برای آوردن صفحه جدید به حافظه، مجبور هستیم صفحاتی را از حافظه خارج کرده و در دیسک بنویسیم تا فضای کافی برای اختصاص صفحه جدید فراهم شود. مراحل انجام این کار بدین صورت است که صفحه‌ای که برای جایگزینی انتخاب شده از حافظه اصلی خارج شده و در دیسک نوشته می‌شود. سپس صفحه خواسته شده توسط برنامه از دیسک برداشته شده و در مکان صفحه قبلی نوشته می‌شود. ممکن است صفحه‌ای که برای جایگزینی انتخاب شده مجدداً توسط برنامه مورد ارجاع قرار گیرد و نیاز باشد تا صفحه بار دیگر از دیسک به حافظه آورده شود. آوردن یک صفحه از دیسک عملی به مراتب زمانبر است چرا که سرعت دیسک از سرعت حافظه اصلی کمتر است. پیاده‌سازی برخی از این الگوریتم‌ها نیازمند پشتیبانی سخت‌افزاری است و برخی از آنها هم قابل پیاده‌سازی نیستند. در بیشتر سیستم‌ها برای کاهش عمل ورودی/خروجی از یک تکنیک سخت‌افزاری به این صورت استفاده می‌شود: هر صفحه دارای یک بیت m (به معنی modify) است. حال اگر قرار باشد که این صفحه جایگزین شود، سیستم‌عامل با نگاه کردن به این بیت تصمیم می‌گیرد که آیا نیاز است صفحه بر روی دیسک نوشته شود یا نه. اگر این بیت ۱ بود، ابتدا صفحه بر روی دیسک نوشته می‌شود و سپس صفحه جدید وارد حافظه شده و جای این صفحه را می‌گیرد. اما اگر این بیت صفر بود، صفحه جدید مستقیماً ار دیسک بر روی این صفحه بازنویسی می‌شود. صفحه‌بندی محلی و صفحه‌بندی سراسری صفحه‌بندی می‌تواند به صورت محلی یا سراسری باشد. در صفحه‌بندی محلی صفحه‌ای برای جایگزینی انتخاب می‌شود که متعلق به همان فرایند باشد. اما در صفحه‌بندی سراسری، هر صفحه‌ای که در حافظه است را می‌توان برای جایگزینی انتخاب کرد. همچنین فرایندهایی که اولویت بالایی دارند، می‌توانند صفحات فرایندهایی که اولویت پایین‌تری دارند را جایگزین کنند. الگوریتم‌ها برخی از سیستم‌ها از صفحه‌بندی درجا یا صفحه‌بندی نیازی استفاده می‌کنند. بدین صورت یک یک صفحه تنها زمانی به حافظه آورده می‌شود که برنامه واقعاً آن را درخواست داده باشد. در برخی دیگر از سیستم‌ها، از همان ابتدای اجرای برنامه تعدادی از صفحات وارد حافظه می‌شوند. چرا که برای پیاده‌سازی آن احتیاج به پیش‌بینی آینده است که در عمل امکان‌پذیر نیست. در این الگوریتم سیستم‌عامل صفحه‌ای را برای جایگزینی انتخاب می‌کند که در آینده، دیرتر از همه به آن نیاز خواهد شد. به عنوان مثال فرض کنید دو صفحه داریم که به یکی از آنها تا ۶ ثانیهٔ آینده، و به دیگری تا ۰٫۴ ثانیهٔ آینده احتیاج نداریم. به دلیل اینکه در این الگوریتم نیاز به پیش‌بینی آینده وجود دارد، قابل پیاده‌سازی نیست. اخیراً استفاده نشده در الگوریتم اخیراً استفاده نشده ، صفحه‌ای جایگزین می‌شود که اخیراً کمتر از همه مورد استفاده قرار گرفته است. این الگوریتم صفحاتی که اخیراً مورد استفاده قرار گرفته‌اند را در حافظه نگه می‌دارد. این الگوریتم بدین شکل کار می‌کند: در جدول صفحه، هر صفحه دارای چند بیت کنترلی است. وقتی که یک صفحه مورد دسترسی قرار می‌گیرد (از آن استفاده می‌شود)، بیت دستیابی آن صفحه ۱ می‌شود. | ## بخش 2: الگوریتم جایگزینی صفحه | به طور مشابه، وقتی که اطلاعات صفحه‌ای تغییر می‌کند، «بیت تغییر» مربوط به آن صفحه هم ۱ می‌شود تا نشان دهد اطلاعات صفحه دستکاری شده است. این بیت‌ها معمولاً توسط سخت‌افزار تغییر می‌کنند، هر چند که می‌توان آنها را به کمک نرم‌افزار هم تغییر داد. در یک فاصله زمانی مشخص، وقفه ساعت فعال شده و بیت دستیابی همه صفحات را صفر می‌کند تا صفحاتی که اخیراً به آنها مراجعه نشده از دیگر صفحات قابل تمیز باشند. بنابراین تنها صفحاتی که در بازه زمانی فعلی استفاده شده‌اند دارای بیت دستیابی ۱ هستند. وقتی که قرار است صفحه‌ای جایگزین شود، سیستم‌عامل صفحات را به گروه‌های زیر تقسیم می‌کند: ۳: استفاده شده، تغییر کرده ۲: استفاده شده، تغییر نکرده ۱: استفاده نشده، تغییر کرده ۰: استفاده نشده، تغییر نکرده سپس سیستم‌عامل یک صفحه تصادفی را از آخرین گروه برای حذف شدن انتخاب می‌کند. بنابراین در الگوریتم، صفحه‌ای انتخاب می‌شود که نه استفاده شده و نه اطلاعات آن تغییر کرده است. توجه کنید که در این الگوریتم اولویت صفحه‌ای که تغییر کرده، اما استفاده نشده، از صفحه‌ای که استفاده شده، اما تغییر نکرده کمتر است. (گروه‌های دو و سه) همچنین ممکن است این سؤال پیش بیاید که چگونه یک صفحه تغییر کرده اما مورد دستیابی قرار نگرفته؟ (گروه ۱) این حالت وقتی پیش می‌آید که در گروه ۳، وقفه ساعت بیت دستیابی یک صفحه را صفر کرده باشد. وقفه ساعت بیت تغییر را صفر نمی‌کند زیرا این بیت نشان‌دهنده این مسئله است که آیا صفحه مورد نظر باید بر روی دیسک نوشته شود یا خیر. در این الگوریتم صفحه‌ای از حافظه خارج می‌شود که از همه زودتر وارد حافظه شده باشد. به عبارت دیگر، صفحه‌ای که از همه قدیمی‌تر باشد از حافظه خارج می‌شود تا فضا برای صفحه جدید محیا شود. منطق این روش آن است که صفحه‌ای که زودتر از همه به حافظه آورده شده، احتمالاً برنامه کار خود را با آن به اتمام رسانده و در آینده دیگر به آن احتیاج نیست. الگوریتم دومین شانس این الگوریتم مشابه الگوریتم FIFO است اما با یک تغییر کوچک که باعث می‌شود کمی کارایی آن بالاتر برود. هر وقت که صفحه مورد دستیابی قرار گرفت (از آن استفاده شد)، این بیت توسط سخت‌افزار ۱ می‌شود. اما به جای آنکه صفحه مورد نظر بی درنگ حذف شود، سیستم‌عامل ابتدا به «بیت دستیابی» آن صفحه نگاه می‌کند، اگر بیت دستیابی صفر بود، صفحه حذف می‌شود. اما اگر بیت دستیابی ۱ بود، سیستم‌عامل آن بیت را صفر کرده و صفحه را به انتهای صف منتقل می‌کند. اگر بیت دستیابی تمام صفحات ۱ بود، آنگاه الگوریتم شانس دوم هم به مانند الگوریتم FIFO عمل می‌کند. الگوریتم ساعت الگوریتم ساعت هم بر اساس الگوریتم FIFO است، اما از الگوریتم شانس دوم موثرتر است. اگر یک نقص صفحه رخ دهد و قاب خالی هم در حافظه وجود نداشته باشد، آنگاه بیت دستیابی در صفحه‌ای که عقربه به آن اشاره می‌کند بررسی می‌شود. اگر بیت دستیابی صفر بود، صفحه حذف می‌شود و صفحه جدید در جایی که عقربه به آنجا اشاره می‌کند قرار می‌گیرد. در غیر این صورت اگر بیت دستیابی ۱ بود، انگاه این بیت صفر شده و عقربه یک واحد افزایش می‌یابد و به عنصر بعدی در صف اشاره می‌کند. اخیراً کمتر استفاده شده الگوریتم اخیراً کمتر استفاده شده هر چند که در نام مشابه NFU است اما در عمل با آن متفاوت است. تفاوت آنها در این است که LRU میزان استفاده صفحات را در یک بازه زمانی کوتاه پیگیری می‌کند اما NFU تنها به میزان استفاده صفحات در آخرین وقفه ساعت نگاه می‌کند. ایده اصلی LRU آن است که صفحاتی که در چند لحظه گذشته به شدت مورد استفاده قرار گرفته‌اند، در چند لحظه آینده هم به شدت مورد استفاده خواهند بود. | ## بخش 3: الگوریتم جایگزینی صفحه | در این الگوریتم وقتی که یک نقص صفحه اتفاق می‌افتد، صفحه‌ای از حافظه خارج می‌شود که نسبت به دیگر صفحات، مدت طولانی‌تری بلااستفاده بوده است. در حالی که به صورت تئوری الگوریتم LRU می‌تواند تقریباً به اندازه الگوریتم بهینه کارایی داشته باشد، پیاده‌سازی آن در عمل مشکل است. تعدادی روش پیاده‌سازی برای این الگوریتم وجود دارد که سعی می‌کنند هزینه پیاده‌سازی را کاهش دهند، بدون اینکه افت قابل توجهی در کارایی الگوریتم ایجاد شود. پرهزینه‌ترین روش، استفاده از یک لیست پیوندی است که تمام صفحات موجود در حافظه را در بر می‌گیرد. در انتهای این لیست، صفحاتی با کمترین میزان استفاده قرار دارند و در ابتدای لیست هم صفحاتی با بیشترین میزان استفاده قرار دارند. مشکل اصلی این گونه پیاده‌سازی این است که صفحات موجود در لیست باید در هر بار دستیابی به حافظه در لیست جابجا شوند که عملی بسیار هزینه بر است. یک روش پیاده‌سازی دیگر که احتیاج به پشتیبانی سخت‌افزار دارد به صورت زیر است: سخت‌افزار یک شمارنده ۶۴ بیتی دارد که با اجرای هر دستورالعمل یک واحد به این شمارنده افزوده می‌شود. هر وقت که صفحه‌ای مورد دستیابی قرار گرفت، صفحه مورد نظر مقداری برابر با مقدار شمارنده در لحظه دستیابی بدست می‌آورد (مقدار شمارنده اصلی در شمارنده صفحه مورد نظر کپی می‌شود). هرگاه که نیاز به جایگزینی یک صفحه است، سیستم‌عامل صفحه‌ای که کمترین شمارنده را دارد را انتخاب می‌کند. به خاطر وجود چنین مشکلاتی در پیاده‌سازی، معمولاً از الگوریتم‌های مشابه LRU استفاده می‌شود که پیاده‌سازی آنها ارزانتر و به صرفه تر است. الگوریتم تصادفی در این الگوریتم یک صفحه به شکل تصادفی انتخاب شده و صفحه جدید جایگزین آن می‌شود. در این الگوریتم هر صفحه شمارنده مخصوص به خود را دارد که این شمارنده در ابتدا بر روی صفر تنظیم شده است. یک ساعت هم در سیستم وجود دارد که هر چند لحظه یک بار فعال می‌شود و یک وقفه ایجاد می‌کند. شمارندهٔ صفحاتی که در این بازه زمانی مورد استفاده قرار گرفته‌اند، یک واحد افزایش می‌یابد. (در عمل، شمارنده با بیت دستیابی صفحه جمع می‌شود) در واقع، شمارنده‌ها تعداد دفعات استفاده از صفحات را نگه می‌دارند. مشکل اصلی این الگوریتم این است که تنها تعداد دفعات استفاده از یک صفحه را بدون در نظر گرفتن فاصله زمانی محاسبه می‌کند. بنابراین در یک کامپایلر چند گذری، صفحاتی که در گذر اول به شدت مورد استفاده بوده‌اند، اما در دومین گذر مورد استفاده نیستند، در مقایسه با صفحاتی که در فاز دوم، هر چند به میزان اندک به آنها نیاز است، بیشتر مورد علاقه خواهند بود. سناریوهای مشابهی مانند بوت شدن سیستم‌عامل هم وجود دارد که الگوریتم NFU کارایی خوبی از خود نشان نمی‌دهد. خوشبختانه یک الگوریتم مشابه با عملکردی بهینه‌تر وجود دارد که در ادامه به آن اشاره خواهیم کرد. هنگامی که جدول صفحه دربرگیرنده مقادیر اشاره‌گر تهی است، الگوریتم NFU کارایی بهتری نسبت به LFU دارد. در اثر این شیفت، بیت سمت راست به بیرون می‌افتد و از بین می‌رود و بیت سمت چپ شمارنده هم با بیت دستیابی پر می‌شود. به عنوان مثال اگر بیت دستیابی یک صفحه در شش تیک آخر ساعت به صورت ۱٫۰٫۰٫۱٫۰٫۰ باشد، شمارنده دستیابی به شکل ۱۰۰۰۰۰۰۰، ۰۱۰۰۰۰۰۰، ۰۰۱۰۰۰۰۰، ۱۰۰۱۰۰۰۰، ۱۱۰۰۱۰۰۰، ۰۱۱۰۰۱۰۰ است. صفحاتی که به تازگی مورد دستیابی واقع شده‌اند، نسبت به صفحاتی که در گذشته دورتر مورد دستیابی واقع شده‌اند، اولویت بیشتری دارند. این ویژگی تضمین می‌کند که صفحاتی که به تازگی دستیابی شده‌اند، هر چند که تعداد دفعات دستیابی به آنها اندک باشد، اولویت بیشتری نسبت به صفحاتی دارند که در گذشته دور به طور مکرر مورد دستیابی قرار گرفته‌اند. (این مقدار به پردازنده وابسته است) در نتیجه، شمارنده دستیابی دو صفحه می‌تواند ۰۰۰۰۰۰۰۰ باشد، حتی اگر یکی از آنها ۹ واحد زمانی قبل و دیگری ۱۰۰۰ واحد زمانی قبل مورد دستیابی واقع شده باشند. | ## جمع‌بندی | به طور کلی، داشتن اطلاعات دستیابی به صفحات در طول ۱۶ واحد زمانی قبل مناسب و کافی بوده و به این ترتیب می‌توان گفت کارایی الگوریتم سالخوردگی به الگوریتم بهینه نزدیک است.