الگوریتم حافظه پنهان
در رایانه حافظه پنهان نرم‌افزار یا سخت‌افزاری است که اطلاعات را ذخیره می‌کند و زمان دسترسی به داده‌ها را تسریع می‌بخشد. الگوریتم‌های حافظه پنهان الگوریتم و دستورالعمل‌های بهینه‌سازی شده ایست که یک حافظه پنهان برای مدیریت ذخیره‌سازی داده در رایانه به کار می‌گیرد. می‌توان با نگهداری داده‌هایی که در زمانی نزدیک استفاده شده‌اند، یا داده‌هایی که اغلب در گذشته در دسترس قرار گرفته‌اند (همجواری زمانی)، در مکان‌های حافظه ای که سریعتر از حافظه‌های معمولی هستند، عملکرد دسترسی داده‌ها را در آینده تسریع بخشید.[1]
الگوریتم و سیاست‌ها
الگوریتم بلاودی
بهینه‌ترین الگوریتم ذخیره‌سازی، الگوریتمی است که داده‌هایی را که در مدت طولانی در آینده مورد استفاده قرار نمی‌گیرند، در ساختار حافظهٔ پنهان ذخیره نکند. این عملکرد ایده‌آل با نام الگوریتم منحصر به فرد یا الگوریتم بهینه بلاودی بیان شده‌است. چون تقریباً غیرممکن است پیش‌بینی این که چه اطلاعاتی در آینده مورد نیاز است، این الگوریتم ایده‌آل در عمل قابل اجرا نیست. الگوریتم حافظه پنهان تنها می‌تواند با آزمایش و تجربه، بازدهی ذخیره‌سازی را بهبود ببخشد.[2][3]
| داده‌ها به ترتیب ورود | ۵ | ۶ | ۰ | ۱ |
|---|---|---|---|---|
| بلوک اول حافظه | ۵ | ۵ | ۵ | ۱ |
| بلوک دوم حافظه | ۶ | ۶ | ۶ | |
| بلوک سوم حافظه | ۰ | ۰ |
برای مثال در شکل بالا، ۵، ۶ و ۰ به ترتیب در جایگاه‌های ۱، ۲ و ۳ قرار گرفته‌اند اما لحظه ای که حافظه پر شده و داده‌ای جدید استفاده می‌شود، به ناچار ۵ را حذف کرده و ۱ را جایگزین می‌کنیم زیرا احتمال دسترسی به ۵ نسبت به ۶ و ۰ به دلیل دورتر بودن زمان دسترسی کمتر است. ازآن جا که در عمل نمی‌توان به‌طور قطع پیش‌بینی کرد که ۵ درچه زمانی در آینده مورد استفاده قرار می‌گیرد، پس الگوریتم بلاودی را نمی‌توان در چنین سیستمی پیاده‌سازی کرد.
اولین ورود اولین خروج
این الگوریتم درصورت پرشدن حافظه نهان بدون توجه به تعداد دفعات دسترسی، آیتمی را که برای اولین بار در حافظه قرار گرفته‌است حذف می‌کند. این الگوریتم با ذخیره کردن آیتم‌ها در یک لیست پیوندی ترتیب ورود صفحه‌ها را حفظ می‌کند.[4]
اخیراً کمتر استفاده شده
این الگوریتم آیتم‌هایی را که اخیراً استفاده شده‌است در حافظه نگه می‌دارد. در صورتی که حافظه پنهان پر شود، آیتمی که تعداد دفعات کمتری مورد دسترسی قرار گرفته باشد حذف می‌شود. برای پیاده‌سازی این الگوریتم لازم است زمان استفاده شدن هر آیتم را بدانیم. معمولاً در عمل رتبه هر آیتم را در کنارش ذخیره می‌کنیم و در هر بار که حافظه پر شد برای اضافه شدن آیتم جدید، آیتمی با کمترین رتبه را حذف می‌کنیم. برای مثال در جدول زیر اعداد ۱، ۲، ۶، ۸، ۹، ۲، ۵ به ترتیب استفاده شده‌اند.[5][6]
| داده‌ها به ترتیب ورود | ۱ | ۲ | ۶ | ۸ | ۹ | ۲ | ۵ |
|---|---|---|---|---|---|---|---|
| بلوک اول حافظه | (۰)۱ | (۰)۱ | (۰)۱ | (۰)۱ | (۴)۹ | (۴)۹ | (۴)۹ |
| بلوک دوم حافظه | (۱)۲ | (۱)۲ | (۱)۲ | (۱)۲ | (۵)۲ | (۵)۲ | |
| بلوک سوم حافظه | (۲)۶ | (۲)۶ | (۲)۶ | (۲)۶ | (۶)۵ | ||
| بلوک چهارم حافظه | (۳)۸ | (۳)۸ | (۳)۸ | (۳)۸ |
برای اضافه شدن ۹ به حافظه، عنصری را که کمترین رتبه را دارد یعنی ۱ با رتبه ۰ را حذف می‌کنیم و هربار با اضافه کردن عنصر جدید مقدار رتبه را یکی اضافه می‌کنیم. با دسترسی مجدد به ۲ رتبه آن به رتبه ۵ به روز می‌شود. در آخر با دسترسی به ۵، عضو ۶ با کمترین رتبه جایگاه خود را به عضو جدید می‌دهد.
اخیراً بیشتر استفاده شده
این الگوریتم بر خلاف الگوریتم اخیراً کمتر استفاده شده آیتم‌هایی که اخیراً بیشتر استفاده شده‌اند را زودتر حذف می‌کند؛ این روش برای موقعیت‌هایی که احتمال دسترسی به آیتم‌هایی قدیمی بیشتر باشد، مناسب است.[7]
شبه اخیراً کمتر استفاده شده
در حافظه پنهان با اندازه‌های بزرگ هزینه پیاده‌سازی الگوریتم اخیراً کمتر استفاده شده زیاد است. با توجه به اینکه حذف عناصری که اخیراً کمتر استفاده شده در الگوریتم حافظه پنهان به صرفه می‌باشد، طراحان پردازنده الگوریتم شبه اخیراً کمتر استفاده شده انتخاب می‌کنند. برخلاف الگوریتم اخیراً کمتر استفاده شده این الگوریتم برای ذخیره هر آیتم تنها یک بیت نیاز دارد. این الگوریتم به نسبت الگوریتم اخیراً کمتر استفاده شده توان کمتری مصرف می‌کند، مخارج کمتری نیاز دارد و زمان اجرا و تأخیر بهتری دارد.[8]
اساس این الگوریتم یک درخت دودویی می‌باشد که در هر راس بیت صفر نشان دهندهٔ یک اشاره گر به فرزند سمت چپ خود و بیت یک نشان دهندهٔ یک اشاره گر به فرزند سمت راست خود خواهد بود. برای پیدا کردن عنصری که داوطلب حذف و جایگزین شدن است از ریشه به سمت پایین اشاره گرها را دنبال می‌کنیم و برگ مقصد همان آیتم مورد نظربرای جایگزینی می‌باشد. سپس جهت تمام اشاره گرهای طی شده را تغییر می‌دهیم.
مثال زیر ترتیب یک دسترسی به صورت E , D , C , B , A نشان می‌دهد.
ابتدا برای اضافه شدن هر آیتم به حافظه بررسی می‌کنیم که آیا این عنصر در حافظه موجود است یا خیر. درصورتی که وجود نداشت، اشاره گرها را از ریشه به سمت برگ‌ها دنبال کرده و آیتم مورد نظر را در بلوک یافت شده جایگزین می‌کنیم؛ سپس از پایین به بالا اشاره گرها را به جهت مخالف تغییر می‌دهیم.
جایگزینی تصادفی
این الگوریتم به صورت تصادفی بلوکی را برای حذف و جایگزینی انتخاب می‌کند. در نتیجه به حافظه اضافی برای ذخیره زمان دسترسی به آیتم‌ها نیازی ندارد. به دلیل سادگی، این الگوریتم را در برخی پردازنده‌ها به کار می‌گیرند.
مکرراً کمتر استفاده شده
در این الگوریتم شمارنده ای به هر آیتم نسبت داده می‌شود که تعداد دفعات استفاده از آن را ذخیره می‌کند. در صورت پرشدن حافظه آیتمی که کمترین تعداد دفعات استفاده را دارد حذف می‌شود. این الگوریتم بسیار شبیه الگوریتم اخیراً کمتر استفاده شده می‌باشد با این تفاوت که به جای ذخیرهٔ زمان دسترسی قبلی به آیتم، تعداد دفعات دسترسی آیتم را ذخیره می‌کند. این الگوریتم برای بعضی از برنامه‌ها نامناسب است؛ مثلاً آیتم‌هایی ممکن است برای مدتی محدود و به تعداد زیاد مورد استفاده قرار گیرند ولی بعداً برای مدت زیادی بلااستفاده باشند. بدین ترتیب آیتم‌هایی که در آینده مورد استفاده نیستند، در حافظه باقی می‌مانند.[9]
منابع
- https://en.wikipedia.org/wiki/Cache_replacement_policies#Pseudo-LRU_(PLRU)
- https://en.wikipedia.org/wiki/Bélády%27s_anomaly
- "Lecture Notes" by Douglas W. Jones 1995
- "Page Replacement Algorithms" by Andrew S. Tanenbaum 2002
- http://www.informit.com/articles/article.aspx?p=25260&seqNum=7
- "CS111 Lecture 11 notes". Archived from the original on 9 January 2009.
- «نسخه آرشیو شده». بایگانی‌شده از اصلی در ۳۱ مه ۲۰۱۹. دریافت‌شده در ۳۱ مه ۲۰۱۹.
- https://en.wikipedia.org/wiki/Pseudo-LRU
- https://en.wikipedia.org/wiki/Least_frequently_used