ناهنجاری بلدی
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مثالی از ناهنجاری بلیدی. با استفاده از سه قاب, ۹ نقص صفحه اتفاق افتاد. اگر تعداد قابها را به چهار قاب افزایش دهیم، ۱۰ نقص صفحه اتفاق می‌افتد. نقص صقحه‌ها با رنگ قرمز نشان داده شده‌اند. |
ناهنجاری بِلَدی (به انگلیسی: Bélády's anomaly) نام پدیده‌ای است که در آن با افزایش تعداد قابها، تعداد نقص صفحه‌ها هم افزایش می‌یابد. این پدیده در الگوریتم جایگزینی صفحه خروج به ترتیب ورود و سایر الگوریتم‌های غیر پشته‌ای اتفاق می‌افتد. لسلو بلدی این پدیده را در سال ۱۹۶۹ اثبات کرد.
در مدیریت حافظه در رایانه، اطلاعات در قالب تکه‌هایی با اندازه مشخص در حافظه اصلی قرار می‌گیرند. به هر تکه یک صفحه گفته می‌شود. از آنجا که ظرفیت حافظه اصلی محدود است، پردازنده می‌تواند تعداد مشخصی از صفحات را در هر زمان در حافظه نگه دارد. خطای نقص صفحه زمانی رخ می‌دهد که پردازنده بخواهد به یک صفحه مشخص دسترسی داشته باشد، اما آن صفحه در حافظه اصلی وجود نداشته باشد. در این حالت، صفحه مورد نظر باید به حافظه آورده شود که به این پدیده نقص صفحه گفته می‌شود.
وقتی که یک نقص صفحه رخ می‌دهد و تمام قاب‌های حافظه هم در حال استفاده هستند، یکی از صفحات موجود باید حذف شود تا فضا برای صفحه خواسته شده فراهم شود. پردازنده برای انتخاب صفحه‌ای که باید حذف شود از الگوریتم‌های جایگزینی صفحه استفاده می‌کند. یکی از ساده‌ترین الگوریتم‌ها، ورود به ترتیب خروج (به انگلیسی: First in First out) است. در این الگوریتم، صفحه‌ای که از همه زودتر وارد حافظه شده باشد، باید پاک شود تا فضا برای صفحه جدید فراهم شود. تا قبل از اثبات ناهنجاری بلیدی، اعتقاد بر این بود که با افزایش تعداد قابها، تعداد نقصه صقحه‌ها یا کاهش می‌یابد یا تغییر نمی‌کند.
پیوند به بیرون
- Bélády's 1969 paper: An anomaly in space-time characteristics of certain programs running in a paging machine
- FIFO anomaly is unbounded. آرخیو:1003.1336
- Internet Problem Solving Contest Solutions - Problem L - Librarian
منابع
مشارکت‌کنندگان ویکی‌پدیا. «Bélády's anomaly». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۷ ژوئیه ۲۰۱۳.