موضوع مقاله: الگوریتم حافظه پنهان | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم حافظه پنهان | مقدمه: در رایانه حافظه پنهان نرم‌افزار یا سخت‌افزاری است که اطلاعات را ذخیره می‌کند و زمان دسترسی به داده‌ها را تسریع می‌بخشد. | ## بخش 1: الگوریتم حافظه پنهان | الگوریتم‌های حافظه پنهان الگوریتم و دستورالعمل‌های بهینه‌سازی شده ایست که یک حافظه پنهان برای مدیریت ذخیره‌سازی داده در رایانه به کار می‌گیرد. می‌توان با نگهداری داده‌هایی که در زمانی نزدیک استفاده شده‌اند، یا داده‌هایی که اغلب در گذشته در دسترس قرار گرفته‌اند (همجواری زمانی)، در مکان‌های حافظه ای که سریعتر از حافظه‌های معمولی هستند، عملکرد دسترسی داده‌ها را در آینده تسریع بخشید. الگوریتم و سیاست‌ها الگوریتم بلاودی بهینه‌ترین الگوریتم ذخیره‌سازی، الگوریتمی است که داده‌هایی را که در مدت طولانی در آینده مورد استفاده قرار نمی‌گیرند، در ساختار حافظهٔ پنهان ذخیره نکند. این عملکرد ایده‌آل با نام الگوریتم منحصر به فرد یا الگوریتم بهینه بلاودی بیان شده‌است. چون تقریباً غیرممکن است پیش‌بینی این که چه اطلاعاتی در آینده مورد نیاز است، این الگوریتم ایده‌آل در عمل قابل اجرا نیست. الگوریتم حافظه پنهان تنها می‌تواند با آزمایش و تجربه، بازدهی ذخیره‌سازی را بهبود ببخشد. Jones 1995 +داده‌ها به ترتیب ورود۵۶۰۱بلوک اول حافظه۵۵۵۱بلوک دوم حافظه۶۶۶بلوک سوم حافظه۰۰ برای مثال در شکل بالا، ۵، ۶ و ۰ به ترتیب در جایگاه‌های ۱، ۲ و ۳ قرار گرفته‌اند اما لحظه ای که حافظه پر شده و داده‌ای جدید استفاده می‌شود، به ناچار ۵ را حذف کرده و ۱ را جایگزین می‌کنیم زیرا احتمال دسترسی به ۵ نسبت به ۶ و ۰ به دلیل دورتر بودن زمان دسترسی کمتر است. ازآن جا که در عمل نمی‌توان به‌طور قطع پیش‌بینی کرد که ۵ درچه زمانی در آینده مورد استفاده قرار می‌گیرد، پس الگوریتم بلاودی را نمی‌توان در چنین سیستمی پیاده‌سازی کرد. | ## بخش 2: الگوریتم حافظه پنهان | اولین ورود اولین خروج این الگوریتم درصورت پرشدن حافظه نهان بدون توجه به تعداد دفعات دسترسی، آیتمی را که برای اولین بار در حافظه قرار گرفته‌است حذف می‌کند. در صورتی که حافظه پنهان پر شود، آیتمی که تعداد دفعات کمتری مورد دسترسی قرار گرفته باشد حذف می‌شود. معمولاً در عمل رتبه هر آیتم را در کنارش ذخیره می‌کنیم و در هر بار که حافظه پر شد برای اضافه شدن آیتم جدید، آیتمی با کمترین رتبه را حذف می‌کنیم. +داده‌ها به ترتیب ورود۱۲۶۸۹۲۵بلوک اول حافظه(۰)۱(۰)۱(۰)۱(۰)۱(۴)۹(۴)۹(۴)۹بلوک دوم حافظه(۱)۲(۱)۲(۱)۲(۱)۲(۵)۲(۵)۲بلوک سوم حافظه(۲)۶(۲)۶(۲)۶(۲)۶(۶)۵بلوک چهارم حافظه(۳)۸(۳)۸(۳)۸(۳)۸ برای اضافه شدن ۹ به حافظه، عنصری را که کمترین رتبه را دارد یعنی ۱ با رتبه ۰ را حذف می‌کنیم و هربار با اضافه کردن عنصر جدید مقدار رتبه را یکی اضافه می‌کنیم. اخیراً بیشتر استفاده شده این الگوریتم بر خلاف الگوریتم اخیراً کمتر استفاده شده آیتم‌هایی که اخیراً بیش‌تر استفاده شده‌اند را زودتر حذف می‌کند؛ این روش برای موقعیت‌هایی که احتمال دسترسی به آیتم‌هایی قدیمی بیش‌تر باشد، مناسب است. شبه اخیراً کمتر استفاده شده در حافظه پنهان با اندازه‌های بزرگ هزینه پیاده‌سازی الگوریتم اخیراً کمتر استفاده شده زیاد است. با توجه به اینکه حذف عناصری که اخیراً کمتر استفاده شده در الگوریتم حافظه پنهان به صرفه می‌باشد، طراحان پردازنده الگوریتم شبه اخیراً کمتر استفاده شده انتخاب می‌کنند. برخلاف الگوریتم اخیراً کمتر استفاده شده این الگوریتم برای ذخیره هر آیتم تنها یک بیت نیاز دارد. | ## بخش 3: الگوریتم حافظه پنهان | این الگوریتم به نسبت الگوریتم اخیراً کمتر استفاده شده توان کمتری مصرف می‌کند، مخارج کمتری نیاز دارد و زمان اجرا و تأخیر بهتری دارد. اساس این الگوریتم یک درخت دودویی می‌باشد که در هر راس بیت صفر نشان دهندهٔ یک اشاره گر به فرزند سمت چپ خود و بیت یک نشان دهندهٔ یک اشاره گر به فرزند سمت راست خود خواهد بود. برای پیدا کردن عنصری که داوطلب حذف و جایگزین شدن است از ریشه به سمت پایین اشاره گرها را دنبال می‌کنیم و برگ مقصد همان آیتم مورد نظربرای جایگزینی می‌باشد. ابتدا برای اضافه شدن هر آیتم به حافظه بررسی می‌کنیم که آیا این عنصر در حافظه موجود است یا خیر. درصورتی که وجود نداشت، اشاره گرها را از ریشه به سمت برگ‌ها دنبال کرده و آیتم مورد نظر را در بلوک یافت شده جایگزین می‌کنیم؛ سپس از پایین به بالا اشاره گرها را به جهت مخالف تغییر می‌دهیم. جایگزینی تصادفی این الگوریتم به صورت تصادفی بلوکی را برای حذف و جایگزینی انتخاب می‌کند. مکرراً کمتر استفاده شده در این الگوریتم شمارنده ای به هر آیتم نسبت داده می‌شود که تعداد دفعات استفاده از آن را ذخیره می‌کند. این الگوریتم بسیار شبیه الگوریتم اخیراً کمتر استفاده شده می‌باشد با این تفاوت که به جای ذخیرهٔ زمان دسترسی قبلی به آیتم، تعداد دفعات دسترسی آیتم را ذخیره می‌کند. | ## جمع‌بندی | این الگوریتم برای بعضی از برنامه‌ها نامناسب است؛ مثلاً آیتم‌هایی ممکن است برای مدتی محدود و به تعداد زیاد مورد استفاده قرار گیرند ولی بعداً برای مدت زیادی بلااستفاده باشند.