در قسمت قبلی، تخصیص پیوسته حافظه معرفی شد. یکی از مهم‌ترین مشکل‌های این نوع حافظه‌دهی، external-fragmentation بود. یعنی حافظه مقدار کافی فضا خالی برای اجرا یک پروسه را دارد اما این فضا به بخش‌های کوچک بین دیگر بخش‌های اشغال شده حافظه پخش شده و چون یک‌پارچه نیست، نمی‌توان از آن استفاده مفیدی کرد و عملا آن بخش از حافظه از دست رفته. در این نوشتار روش paging معرفی می‌شود، که در آن مشکل external-fragmentation حل شده است.
در این پست، فرق بین حافظه logical و physical به‌طور اجمالی گفته شد و دیدیم که چیزی که پردازنده و برنامه‌ها از حافظه می‌بینند یک تصویر مجرد (abstract) از حافظه فیزیکی است. جدا بودن حافظه منطقی از حافظه فیزیکی، در اینجا این امکان را به ما می‌دهد، که در لایه فیزیکی، الزاما حافظه به‌طور پیوسته تخصیص داده نشود، اما از نگاه برنامه‌ها، حافظه کاملا پیوسته باشد. اما چطور؟
برای اینکار ابتدا حافظه فیزیکی را به بخش‌های کوچکی به نام frame تقسیم می‌کنیم. مثلا فریم‌های ۴۰۹۶ بایتی. همچنین حافظه منطقی را هم تقسیم می‌کنیم به بخش‌های کوچک‌تر با همان اندازه فریم‌ها. نام هر بخش از حافظه منطقی page می‌گذاریم. حالا وقتی یک برنامه می‌خواهد از حافظه استفاده کند، سیستم‌عامل به تعداد لازم page در اختیار برنامه قرار می‌دهد. این page ها از نگاه برنامه پیوسته هستند. اما لزوما فریم‌های متناظر با page ها، به طور پیوسته در حافظه فیزیکی تخصیص داده نشده‌اند. یعنی دیگر مشکلی نیست که بخش کوچکی از حافظه بین دو بخش اشغال شده خالی مانده باشد. در هر صورت می‌توانیم از آن استفاده کنیم. چون چیزی که برنامه‌ها می‌بینند page ها هستند و نه frame ها.
اینکار ایجاب می‌کند که برای هربار دسترسی به حافظه، آدرس حافظه توسط MMU ترجمه شود. چون برنامه‌ها از حافظه منطقی استفاده می‌کنند اما برای دسترسی به داده‌ها باید این آدرس حافظه به حافظه فیزیکی ترجمه شود.
برای ترجمه آدرس حافظه، هر پروسه جدولی دارد به نام page-table. این جدول صرفا شماره فریم هر page را به ما می‌دهد. مثلا برنامه می‌خواهد از page شماره ۱۲ داده‌ای را بخواند. سخت‌افزار و سیستم‌عامل باید با استفاده از page-table فریم متناظر با page شماره ۱۲ را پیدا کنند. بعد داده مورد نظر را از آن فریم بخوانند و در اختیار برنامه دهند. این یعنی برنامه به‌هیچ‌وجه درگیر جزئیات ترجمه و آدرس‌دهی و مخلفات نمی‌شود. و اصلا برای برنامه مهم نیست که این page مال کدام frame است یا در کجا ذخیره شده.
شمای کلی یک آدرس منطقی به این شکل است:
همان‌طور که در تصویر واضح است، هر آدرس logical از دو بخش تشکیل می‌شود. بخش ابتدائی که شماره page را مشخص می‌کند و با استفاده از آن می‌توان فریم متناظر با آن page را در page-table پیدا کرد. و همچنین بخش انتهای آن، که بعد از پیدا کردن فریم، نشان‌دهنده خانه dام از فریم است.
در واقع ترجمه آدرس منطقی به فیزیکی در ۳ مرحله زیر انجام می‌شود:
حتما متوجه شدید که در مراحل ترجمه، آفست یا همان d تغییری نکرده.
شکستگی‌بیرونی یا همان external-fragmentation در paging وجود ندارد. دلیل آن‌هم این است که هر بخشی از حافظه فیزیکی می‌تواند به هر حافظه‌ای تخصیص داده شود. نمای بیرونی آدرس‌ها که همان آدرس‌های منطقی هستند، پیوسته هستند. اما از نگاه سخت‌افزار، لزوما حافظه تخصیص داده شده به یک برنامه، پیوسته نیست. تصویر زیر این مفهوم را نمایش می‌دهد:
این روش در کنار مزیت اصلی خود - یعنی از بین بردن شکستگی بیرونی - یک ایراد مشابه دارد و آن internal-fragmentation یا شکستگی درونی است. این یعنی اگرچه مطمئن هستیم هیچ فریم‌ای از حافظه فیزیکی بلا استفاده نخواهد ماند و می‌توان از تمام فریم‌ها برای تمام پروسه‌ها استفاده کرد اما به دلیل ثابت بودن اندازه فریم‌ها نمی‌توان دقیقا حافظه مورد نیاز برنامه‌ها را تأمین کرد و معمولا باید چیزی بیشتر از حافظه مورد نیاز هر پروسه را به آن پروسه تخصیص دهیم. یعنی چی؟
فرض کنید اندازه هر سایز ( و به طبیعتا هر page) ۴۰۹۶ باید باشد. اگر یک پروسه ۱۲۵۰۰ بایت حافظه نیاز داشته باشد برای اجرا شدن، باید ۴ فریم به این پروسه اختصاص دهیم. و می‌دانیم که از بخش زیادی از فریم چهارم استفاده نخواهد شد.
12500 = 4096 * 3 + 212
همان‌طور که مشخص است، پروسه ما، از ۳ فریم ابتدائی استفاده کامل می‌کند اما از فریم چهارم فقط ۲۱۲ بایت را استفاده می‌کند، و ۳۸۸۴ بایت دیگر از این فریم هدر می‌رود. به این پدیده internal-fragmentation گفته می‌شود. بدترین حالت وقوع internal-fragmentation وقتی است که از یک فریم فقط ۱ بایت استفاده شود. مثلا در این مثال ما که اندازه هر فریم ۴۰۹۶ بایت است، بدترین حالت وقتی است که ۴۰۹۵ بایت استفاده نشود.
وقتی پروسه جدیدی ایجاد می‌شود، سیستم‌عامل باید حافظه مورد نیاز آن پروسه را در اختیارش قرار دهد. فرض می‌کنیم که پروسه جدید به n فریم نیاز دارد. سیستم‌عامل در حافظه می‌گردد و سعی می‌کند n فریم از هر جای حافظه که بود پیدا کند. وقتی این n فریم پیدا شد، در حافظه منطقی به ازاء هر فریم یک page ساخته می‌شود و نهایتا یک page-table برای این پروسه ساخته می‌شود که آدرس فیزیکی هر فریم را به آدرس منطقی آن page وصل می‌کند. باید توجه داشت که در حالت ساده، هر پروسه page-table خودش را دارد.
به ازا هر پروسه ما یک page-table داریم. از آن‌جایی که page-table ها نسبتا حجیم هستند، نگه‌داری آن‌ها یک چالش مهم است. اولین راهکار برای نگه‌داشتن آن‌ها این است که کل page-table را داخل حافظه کش پردازنده ذخیره کنیم. بدین شکل، سرعت دسترسی به page-table بسیار زیاد خواهد بود. اما از آن‌جایی حافظه کش محدود است، ما دوست نداریم بخش عمده آن را به page-table اختصاص دهیم. از طرف دیگر، چون page-table مخصوص هر پروسه است، در مواقعی که پروسه‌ها عوض می‌شوند، هزینه زمانی context-switch بالا خواهد بود. یعنی پردازنده باید کل مقادیر page-table پروسه قدیم را از حافظه کش خود پاک کند و کل page-table حافظه جدید را در حافظه کش خود بارگذاری کند. اینکار زمان زیادی خواهد برد.
راه‌حلی که برای مشکل بالا وجود دارد، این است که یک بخش بسیار کوچک از حافظه کش پردازنده را، به‌عنوان اشاره‌گر به page-table قرار دهیم. مقادیر اصلی page-table داخل حافظه اصلی ذخیره شده‌اند. و با استفاده از اشاره‌گری که در حافظه کش داریم می‌توانیم به آن دسترسی پیدا کنیم. به آن اشاره‌گر اصطلاحا page-table base register یا PTBR گفته می‌شود.
راهکار بالا در عمل خیلی کارا نیست. چون دسترسی به حافظه اصلی به نسبت حافظه کش پردازنده بسیار سخت‌تر و کندتر است. برای حل این مشکل، طراحان‌سیستم‌عامل دست به دامن سخت‌افزار شدند.
راه‌حل نهایی و استاندارد برای حل این مشکل، داشتن یک حافظه کش جداگونه مخصوص نگه‌داری page-tableها بود. نام این سخت‌افزار translation look-aside buffer یا TLB است. TLB نوعی حافظه key-value هست برای نگه‌داری ساده داده‌های page-table.
این راه‌حل نتیجه مشاهدات طراحان سیستم‌عامل بود. این مشاهدات، نشان می‌داد که در غالب موارد، برنامه‌ها به تعداد کمی از page های خود احتیاج دارند. یعنی درصد زیادی از مواقع برنامه‌ها به بخش کوچکی از حافظه خود نیاز دارند.
همان‌طور که گفته شد، TLB نوعی حافظه کش است. پس معمولا آخرین page-tableهایی که استفاده شده‌اند را در خود نگه می‌دارد. این بدین معناست که غالبا وقتی یک پروسه جدید ایجاد می‌شود، ابتدا با TLB miss مواجه می‌شود. یعنی داده‌های page-table داخل TLB ذخیره نشده‌اند. اما در ادامه دیگر احتمالا این اتفاق رخ ندهد. TLB تعداد دسترسی به حافظه اصلی برای page-table را به شدت پایین می‌آورد.
یکی از مزایایی که paging دارد، استفاده اشتراکی از بعضی از فریم‌های حافظه است. فرض کنید چند برنامه که از کتاب‌خانه اشتراکی X استفاده می‌کنند همزمان در حال اجرا هستند. اگر مطمئن باشیم که استفاده از این کتاب‌خانه‌ها صرفا خواندن است (یعنی داده‌ها تغییری نمی‌کنند) می‌توانیم فریم‌های یکسانی را به چند page در پروسه‌های مختلف نظیر کنیم. تصویر زیر این مطلب را نشان می‌دهد:
همان‌طور که تصویر بالا مشخص است، در تصویر بالا ۳ پروسه همزمان از فریم‌های ۱، ۳،۴ و ۶ استفاده می‌کنند.
