جلسه 6تعریف صفحه و الگوریتمهاي جایگزیني صفحه
مقدمه: چرا به صفحهبندی نیاز داریم؟
- مشکل حافظه اصلی: محدودیت حافظه اصلی (RAM) و نیاز به اجرای برنامههای بزرگتر از حافظه فیزیکی.
- راه حل: حافظه مجازی: ایجاد یک لایه انتزاعی برای حافظه که به برنامهها اجازه میدهد تصور کنند حافظه بسیار بیشتری در اختیار دارند.
- مفهوم صفحهبندی: تقسیم فضای آدرس منطقی (Virtual Address Space) فرآیند به بلوکهای با اندازه ثابت به نام “صفحه” (Page) و تقسیم حافظه فیزیکی (RAM) به بلوکهایی با همان اندازه به نام “قاب صفحه” (Page Frame).
۲. مفاهیم کلیدی:
- فضای آدرس منطقی (Logical Address Space): مجموعهای از آدرسهایی که پردازنده تولید میکند. این فضا توسط برنامه دیده میشود.
- فضای آدرس فیزیکی (Physical Address Space): مجموعهای از آدرسهای واقعی در حافظه RAM.
- صفحه (Page): یک بلوک با اندازه ثابت در فضای آدرس منطقی.
- قاب صفحه (Page Frame): یک بلوک با اندازه ثابت در حافظه فیزیکی. اندازه صفحه و قاب صفحه برابر است.
- جدول صفحه (Page Table): ساختار دادهای که توسط سیستمعامل نگهداری میشود و نگاشت بین صفحات منطقی و قابهای صفحه فیزیکی را انجام میدهد. هر فرآیند جدول صفحه مخصوص به خود را دارد.
- ورودی جدول صفحه (Page Table Entry - PTE): هر ورودی شامل شماره قاب صفحه فیزیکی مربوط به صفحه منطقی است. همچنین شامل بیتهای معتبر/نامعتبر (Valid/Invalid bit) و بیتهای کنترلی دیگر (مانند بیت ارجاع، بیت تغییر یافته) است.
- آدرسدهی صفحهبندی شده:
- آدرس منطقی: شامل شماره صفحه (p) و افست در صفحه (d) است.
- تبدیل آدرس: سیستم مدیریت حافظه (Memory Management Unit - MMU) با استفاده از جدول صفحه، شماره صفحه منطقی (p) را به شماره قاب صفحه فیزیکی (f) تبدیل میکند. سپس آدرس فیزیکی با ترکیب شماره قاب صفحه (f) و افست (d) ساخته میشود.
- آدرس فیزیکی = (f * اندازه صفحه) + d
۳. خطای صفحه (Page Fault):
- رخ دادن خطا: زمانی اتفاق میافتد که برنامه به صفحهای دسترسی پیدا کند که در حال حاضر در حافظه فیزیکی بارگذاری نشده است (بیت معتبر در PTE برابر با نامعتبر باشد).
- مراحل مدیریت خطای صفحه:
- سیستمعامل متوجه خطای صفحه میشود.
- بررسی میشود که آیا آدرس منطقی معتبر است یا خیر (اگر نامعتبر باشد، برنامه خاتمه مییابد).
- اگر صفحه در دیسک (حافظه ثانویه مانند HDD/SSD) موجود باشد، پیدا میشود.
- یک قاب صفحه خالی در حافظه فیزیکی پیدا میشود.
- اگر قاب صفحهای خالی نباشد، یکی از صفحات موجود در حافظه باید جایگزین شود (اینجاست که الگوریتمهای جایگزینی صفحه وارد میشوند).
- صفحه انتخاب شده برای جایگزینی (اگر کثیف - Modified/Dirty - باشد) به دیسک نوشته میشود.
- صفحه مورد نیاز از دیسک خوانده شده و در قاب صفحه خالی قرار میگیرد.
- جدول صفحه بهروزرسانی میشود (PTE جدید تنظیم میشود).
- دستورالعمل (instruction) که باعث خطای صفحه شده بود، دوباره اجرا میشود.
۴. الگوریتمهای جایگزینی صفحه (Page Replacement Algorithms):
هدف این الگوریتمها انتخاب صفحهای است که در صورت نیاز به جایگزینی، کمترین احتمال استفاده مجدد در آینده نزدیک را داشته باشد تا تعداد خطاهای صفحه کاهش یابد.
الف) الگوریتم بهینه (Optimal - OPT/MIN):
نحوه کار: صفحهای را جایگزین میکند که بیشترین زمان در آینده مورد استفاده قرار نخواهد گرفت.
مزایا: بهترین عملکرد ممکن (کمترین خطای صفحه).
معایب: در عمل قابل پیادهسازی نیست، زیرا اطلاعات آینده (زمان استفاده بعدی هر صفحه) در دسترس نیست. صرفاً به عنوان معیار مقایسه استفاده میشود.
ب) الگوریتم اولین ورود، اولین خروج (First-In, First-Out - FIFO):
نحوه کار: صفحهای را که زودتر از همه وارد حافظه شده است، جایگزین میکند (مانند صف).
مزایا: پیادهسازی ساده.
معایب: عملکرد ضعیفی دارد. ممکن است صفحهای که بارها استفاده شده و زودتر وارد شده را حذف کند (پدیده Belady’s Anomaly).
ج) الگوریتم کمترین استفاده اخیر (Least Recently Used - LRU):
نحوه کار: صفحهای را جایگزین میکند که اخیراً (در گذشته نزدیک) کمترین استفاده را داشته است. فرض بر این است که صفحهای که اخیراً استفاده شده، احتمالاً دوباره به زودی استفاده خواهد شد.
مزایا: عملکرد خوب و نزدیک به بهینه.
معایب: پیادهسازی آن هزینهبر است. نیاز به نگهداری اطلاعات دقیق استفاده از صفحات دارد (مانند شمارندهها یا پشتهها).
د) الگوریتمهای تقريبي LRU (Approximation Algorithms for LRU):
به دلیل هزینه بالای پیادهسازی LRU واقعی، از روشهای تقریبی استفاده میشود که با استفاده از بیتهای کمکی در جدول صفحه، عملکردی شبیه LRU را با هزینه کمتر ارائه میدهند.
۱. الگوریتم “استفاده نشده” (Not Used - NU) یا Ref-Bit:
هر PTE یک بیت “ارجاع” (Reference bit) دارد که توسط سختافزار وقتی صفحه خوانده یا نوشته میشود، تنظیم میشود.
به صورت دورهای، سیستمعامل این بیتها را بررسی میکند. صفحاتی که بیت ارجاعشان ۰ است، اخیراً استفاده نشدهاند و کاندید خوبی برای حذف هستند.
۲. الگوریتم “کلاس دستورالعمل” (Clock Algorithm) یا Second-Chance:
صفحات در یک ساختار دایرهای (مانند ساعت) قرار میگیرند و یک اشارهگر (عقربه ساعت) روی آنها حرکت میکند.
وقتی نیاز به جایگزینی است، اشارهگر جلو میرود. اگر صفحه زیر اشارهگر بیت ارجاعش ۱ باشد، آن را به ۰ تغییر داده و اشارهگر جلوتر میرود (فرصت دوم). اگر بیت ارجاع ۰ باشد، آن صفحه جایگزین میشود.
۳. الگوریتم “کلاس دستورالعمل بهبود یافته” (Enhanced Clock Algorithm) یا Not Recently Used, Not Clean (NRU/NUC):
از دو بیت در PTE استفاده میکند: بیت ارجاع ® و بیت تغییر یافته (m - dirty bit).
طبقهبندی صفحات بر اساس (r, m):
کلاس 0: (0, 0) - اخیراً استفاده نشده و تمیز (بهترین کاندید برای حذف)
کلاس 1: (0, 1) - اخیراً استفاده نشده ولی کثیف (نیاز به نوشتن در دیسک قبل از حذف)
کلاس 2: (1, 0) - اخیراً استفاده شده ولی تمیز
کلاس 3: (1, 1) - اخیراً استفاده شده و کثیف (بدترین کاندید برای حذف)
الگوریتم سعی میکند ابتدا از کلاس 0، سپس کلاس 1، و … حذف کند.
۵. خلاصه نکات کلیدی:
- صفحهبندی مکانیزمی برای پیادهسازی حافظه مجازی است که حافظه را به صفحات و قابهای صفحه تقسیم میکند.
- جدول صفحه نگاشت بین آدرسهای منطقی و فیزیکی را انجام میدهد.
- خطای صفحه زمانی رخ میدهد که صفحه مورد نیاز در حافظه فیزیکی نباشد و نیاز به بارگذاری از دیسک دارد.
- الگوریتمهای جایگزینی صفحه برای انتخاب صفحهای که باید از حافظه خارج شود تا جای صفحه جدید باز شود، به کار میروند.
- LRU بهترین عملکرد را دارد اما پیادهسازی آن گران است. الگوریتمهای تقریبی مانند Clock، راهحلهای عملیتری ارائه میدهند.
