دانلود مقاله صفحه‌بندی در سیستم عامل

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

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

در چنین وضعیتی، هر صفحه از یک برنامه می‌تواند در هر قاب آزاد حافظه قرار گیرد.

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

جدول صفحه می‌تواند در ثبات‌های خاص و یا در حافظه‌های سریع و موسوم به حافظه تناظری قرار گیرد.

به دلیل محدود بودن بودن اندازه TBL همواره بخشی از جدول صفحه هر برنامه در داخل TLB قرار می‌گیرد و در هنگام تبدیل آدرس، اگر سطر حاوی شماره صفحه و شماره قاب در TLB موجود باشد، وضعیت برخورد (hit) رخ می‌دهد و اگر این سطر موجود نباشد، وضعیت عدم برخورد (miss) پیش می‌آید که نسبت این دو به نام نسبت برخورد از رابطه زیر محاسبه می‌شود:
با توجه به اینکه در مکانیزم تبدیل آدرس، برای اجرای هر دستور یک مراجعه به جدول و یک مراجعه به حافظه لازم است، محل قرار گرفتن جدول صفحه مهم می‌باشد.

به دلیل محدود بودن بودن اندازه TBL همواره بخشی از جدول صفحه هر برنامه در داخل TLB قرار می‌گیرد و در هنگام تبدیل آدرس، اگر سطر حاوی شماره صفحه و شماره قاب در TLB موجود باشد، وضعیت برخورد (hit) رخ می‌دهد و اگر این سطر موجود نباشد، وضعیت عدم برخورد (miss) پیش می‌آید که نسبت این دو به نام نسبت برخورد از رابطه زیر محاسبه می‌شود: hit ratio = hit/hit + miss اشتراک و حفاظت در صفحه‌بندی اشتراک در صفحه‌بندی به مفهوم استفاده چند برنامه از صفحات مشترک و در نتیجه، استفاده بهتر از حافظه است.

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

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

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

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

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

همچنین با داشتن یک ثبات به نام PTLR‌ می‌توان محدوده جدول صفحه یک برنامه را در حافظه مشخص نمود.

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

بدین منظور با اجرای روش صفحه‌بندی به صورت مناسب می‌توان به این هدف دست یافت.

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

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

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

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

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

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

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

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

دستور مراجعه به حافظه مجدداً اجرا می‌شود و اکنون صفحه مورد تقاضا در حافظه قرار دارد.

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

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

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

در چنین وضعیتی، اگر وقفه فقدان صفحات بروز کند، باید یکی از قاب‌ها پر مورد استفاده قرار گیرد.

اگر این قاب قبلاً اصلاح شده باشد، قبل از بار کردن صفحه مورد نیاز به آن، باید بر روی دیسک بازنویسی شود و در این صورت در یک وقفه، زمان دو برابر تلف خواهد شد(یک بار نوشتن قاب و یک بار خواندن صفحه مورد نیاز).

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

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

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

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

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

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

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

این الگوریتم به راحتی قابل پیاده‌سازی است، ولی دارای مشکلی به نام Belady Anomaly‌ است.

الگوریتم‌های دارای این مشکل بر طبق نمودار شکل 2 عمل نمی‌کنند و در بعضی شرایط با افزایش تعداد قاب‌هایی که در اختیار دارند، تعداد وقفه صفحه آنها نیز افزایش می‌یابد.

الگوریتم Optimal: در این الگوریتم، فرض می‌شود دنباله صفحات مورد نیاز از ابتدا در اختیار مدیر حافظه قرار دارد.

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

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

در این الگوریتم مشکل Baleady Anomaly بروز نمی‌کن.

الگوریتم NRU: در این الگوریتم، برای هر قاب دو بیت اضافی در جدول صفحه در نظر گرفته می‌شود.

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

دسته 1: قابی که مورد رجوع قرار نگرفته است و اصلاح شده است.

دسته 2: قابی که مورد رجوع قرار گرفته است، ولی اصلاح نشده است.

دسته 3: قابی که هم مورد رجوع قرار گرفته است و هم اصلاح شده است.

به طبق این الگوریتم، اگر در دسته با شماره کمتر قاب‌هایی موجود باشد، یکی از آنها بر طبق الگوریتمی نظیر FIFO انتخاب می‌شود.

نکته: ظاهراً دسته 1 هیچگاه شامل قابی نخواهد بود، ولی هنگامی که یک قاب از دسته 3 مدت طولانی مورد رجوع قرار نگیرد، بیت R‌ آن در چرخه ساعت سیستم که بر اساس مدت زمانی طولانی تنظیم شده، پاک می‌شود و به دسته 1 می‌رود.

بدین صورت بیت R‌ پاک می‌شود، ولی هرگز بیت M یک نمی‌شود، مگر زمانی که قاب به دیسک بازنویسی شود.

الگوریتم Second Chance: این الگوریتم شبیه الگوریتم FIFO است که از بیت R استفاده می‌کند.

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

الگوریتم Clock: این الگوریتم، با انجام تغییری در الگوریتم Second Chance‌ بهتر از آن عمل می‌کند.

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

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

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

سپس با حذف این قاب، به قاب بعدی اشاره می‌کند.

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

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

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

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

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

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

نکته: بعضی از الگوریتم‌های نظیر الگوریتم‌های نظیر الگوریتم LRU‌ الگوریتم‌های Stack‌ نامیده می‌شوند.

در چنین الگوریتم‌هایی، مجموعه صفحات در حافظه دارای n قاب همواره زیر مجموعه صفحات آنها در حافظه با n-1 قاب است.

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

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

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

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

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

در تعیین اندازه قاب، عوامل متعددی دخالت دارند.

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

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

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

اگر اندازه میانگین برنامه‌ها، s بایت و اندازه یک صفحه p بابت و هر سطر جدول صفحه e بایت فضا لازم داشته باشد، تعداد سطرهای لازم برای یک برنامه در جدول صفحه برابر s/p است و در نتیجه اندازه جدول صفحه se/p می‌باشد.

برای یک برنامه نصف صفحه اتلاف وجود دارد.

بنابراین کل فضای اضافی که برای یک برنامه اضافی بر فضای لازم در حافظه نیاز دارد، مجموع این دو مقدار است.

Se/p + p/2 فضای سربار هر برنامه برای حداقل کردن این اتلاف باید مقدار آن نسبت به p حداقل گردد، بنابراین با محاسبه مستق این تابع و یافتن ریشه آن p محاسبه می‌شود.

-se/p2+1/2=0→p=^2se به صورت عددی، اندازه قاب‌ها در سیستم عامل‌های مختلف از 256 بایت تا 32 کیلوبایت استفاده می‌شود.

الگوریتممشکل Balady AnomalyOptimalنداردLRUنداردSecond ChanceداردFIFOدارد