صفحه‌بندی (رایانه)

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

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

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

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

1. محل داده را روی دیسک مشخص کند.
2. یک قاب خالی برای جای دادن صفحه در حافظه اصلی بدست آورد تا به عنوان محفظه برای داده عمل کند.
3. داده مدنظر را داخل قاب موجود بارگذاری کند.
4. جدول صفحه‌بندی را به‌روز کند تا ارجاع درست به قاب جدید در آن قرار بگیرد.
5. کنترل را به برنامه‌ای که قبلاً از آن کنترل را گرفته بود برگرداند و دستوری را که باعث ایجاد عیب صفحه شده بود را مجدد اجرا کند.

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

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

صفحه‌بندی بر حسب نیاز

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

صفحه‌بندی رضایت بخش

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

صف صفحات آزاد، دزدی و بازپس‌گیری

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

پیش تمیزکاری

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

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

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

پیاده‌سازی در یونیکس و شبه یونیکس

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

پیاده‌سازی در لینوکس

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

ذخیره‌سازی برای حافظه مجازی سیستم عامل از حافظه اصلی به مراتب کندتر می‌باشد. استفاده از دیسک مغناطیسی به علت عملکرد مکانیکی آن کند می‌باشد و سعی می‌شود که مبادله به حداقل رسیده یا حذف شود. بعضی از سیستم عامل‌ها تنظیمات تأثیرگذاری را به هسته ارائه می‌کنند.

• لینوکس پارامترهایی را در /proc/sys/vm/swappiness ارائه می‌کند که زمان مبادله به خارج و آزادسازی صفحات را تعیین می‌کنند.
• حافظه‌های فلش نیز به عنوان دستگاهی برای مبادله استفاده می‌شوند. این نوع حافظه سرعت بیشتری از دیسک فیزیکی دارد و نسبت به حافظه اصلی ثبات بیشتری دارد اما محدودیت چرخه نوشتن و خواندن دارد یعنی اگر تحت فشار زیاد مبادلات باشند زود از از بین می‌روند.

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

فضای مبادله

سازندگان سیستم‌های عامل معمولاً فضای مورد نیاز برای مبادله را پیشنهاد می‌کنند.

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

حافظه اصلی از مجازی کوچکتر باشد

در اکثر سیستم‌ها حافظه مجازی بیشتر از حافظه اصلیست. در بعضی سیستم‌ها مانند اکثر کامپیوترهای کاربری عادی مانند کامپیوترهایی که قطعه پردازنده آن‌ها فقط ۲۴ پایه آدرس دهی متصل دارد و محدودیت آدرس دهی برای حافظه اصلی وجود دارد و نمی‌توان بیش از ۱۶ مگابایت را آدرس دهی کرد.

بعضی اوقات بیشینه مقدار حافظه اصلی را نمی‌توان نصب کرد به دلیل هزینه بالا یا اینکه مفید نخواهد بود.

بعضی اوقات آدرس‌های داخلی برای ورودی/خروجی استفاده می‌شود و نمی‌توان تمام آن را به حافظه اصلی اختصاص داد.

حافظه اصلی هم اندازه حافظه مجازی

کامپیوتری با آدرس دهی n بیت می‌تواند ۲ به توان n بیت را آدرس دهی کند. مثلاً پردازنده‌هایی با معماری‌های ۳۲ بیتی می‌توانند تمامی ۴ گیگ از حافظه را آدرس بدهند.

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

حافظه اصلی بزرگتر از حافظه مجازی

در این موارد سیستم نمی‌تواند بیش از حد آدرس مجازی قابل دسترسی از حافظه استفاده کند. صفحه‌بندی در این سیستم‌ها به دلایل زیر انجام می‌شود:

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

ابعاد حافظه مجازی تجمعی هنوز توسط حافظه ثانویه قابل دسترسی محدود می‌شود.

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