آموزش الگوریتم fifo نقص صفحه در سیستم عامل
fifo که مخفف first in first out می باشد صفحه ای را جایگزین میکند که قدیمی ترین صفحه در حافظه می باشد. مطلب را با ارائه یک مثال بیشتر توضیح میدهم.
مثال:فرض کنید حافظه ی ما دارای سه قاب می باشد، و یک سری درخواست به شکل زیر از چپ به راست میرسد.
۵ و ۱ و ۲ و ۳ و ۴ و ۵ و ۳ و ۴ و ۱ و۲ و ۳ و ۴
بسیار خب. ابتدا سه قاب خالی می باشند، و به ترتیب از چپ به راست سه صفحه ی ۲و۳و۴ وارد حافظه میشوند. اما یک قانون در این بین است:اگر صفحه ای وارد حافظه شود و ببیند که صفحه ای مثل خودش در حافظه نیست بنابراین یک نقص صفحه رخ می دهد.اما اگر آن صفحه ی آمده ببیند که یک صفحه مثل خودش
قبلاً در حافظه وارد شده و اکنون نیز در حافظه وجود دارد ،این صفحه ی تکراری دیگر نقص صفحه ندارد.
مثال را ادامه می دهیم.....
صفحات ۲و۳و۴ به ترتیب از چپ به راست وارد می شوند و چون قبل از این در حافظه نبوده اند پس سه تا نقص صفحه رخ می دهد. حافظه ـــــ> ۲و۳و۴ تعداد نقص تا اینجا: ۳
بسیار خب. صفحه بعدی که وارد می شود، صفحه شماره ۱ می باشد.اما حافظه ی ما سه قاب دارد و آن سه تا هم توسط ۲و۳و۴ پر شده اند.تکلیف چیست؟؟؟؟
باید یکی از صفحات خارج شود تا جا برای ۱ باز شود.کدام صفحه را خارج کنیم؟؟
خیلی ساده به نوع الگوریتم نگاه می کنیم، میبینیم fifo می باشد. طبق این الگوریتم
صفحه ای را خارج می کنیم که قدیمی ترین صفحه است...به نظر شما کدام صفحه قدیمی ترین است... نگاه کنید ــــــــ> ۲و۳و۴ درست حدس زدید صفحه ی شماره ۴ اولین و در نهایت قدیمی ترین است پس ۱ با اون جایگزین می شود.
و چون در حافظه صفحه یکی وجود نداشت ۱ جای ۴ می نشیند و نقص صفحه هم رخ می دهد.
حافظه ـــــــ> ۲و۳و۱ تعداد نقص تا اینجا:۴
حالا باید دقت داشته باشید که الآن قدیمی ترین صفحه ، صفحه شماره ۳ می باشد یعنی صفحه بعدی که بیاد اگر تکراری نباشد باید جای ۳بنشیند. صفحه شماره ۴ میاد داخل. آیا تکراری است؟
خیر چون تو حافظه صفحات ۲و۳و۱ وجود دارد و چهاری وجود ندارد.پس می تواند جایگزین شود حالا به جای کدوم... جای قدیمی ترین که همانطور در بالاتر گفتم صفحه ۳قدیمی ترین است. ۴ جای ۳ می نشیند و چون در حافظه نبود نقص صفحه برای این صفحه هم رخ می دهد.
حافظه ــــــــ> ۲و۴و۱ تعداد نقص تا اینجا:۵
حالا قدیمی ترین صفحه می شود ۲. صفحه ی بعدی که وارد می شود ۳ است و چون
در حافظه نیست می تواند در حافظه بنشیند . اما جای کدوم؟؟؟ جای قدیمی ترین صفحه که ۲ می باشد و چون در حافظه نبود نقص صفحه هم برایش اتفاق می افتد.
حافظه ـــــــــ>۳و۴و۱ تعداد نقص صفحه تا اینجا:۶
حالا قدیمی ترین صفحه می شود ۱. صفحه ۵ وارد می شود چون در بین صفحات کنونی حافظه قرار ندارد می تواند در حافظه بنشیند.اما جای کدوم؟؟؟ جای قدیمی ترین که ۱ است. و چون در حافظه کنونی صفحه پنجی نیست پس نقص صفحه هم دارد.
حافظه ـــــــ>۳و۴و۵ تعداد نقص صفحه تا اینجا:۷
حالا قدیمی ترین می شود صفحه ۴.بسیار خب ...صفحه ۴ وارد می شود.حالا چون صفحه ۴ در حافظه وجود دارد این صفحه ی جدید ۴ دیگر به حافظه نمی آید و نقص صفحه هم ندارد و همچنان قدیمی ترین صفحه همان ۴ می ماند.
حافظه ــــــــ>۳و۴و۵ تعداد نقص صفحه تا اینجا: همچنان ۷
صفحه بعدی شماره ۳ است که می خواهد وارد شود.آیا ۳ در حافظه وجود دارد.بـــله.
درست است که قدیمی ترین صفحه ۴ است و صفحه ی آمده باید جای ۴ بنشیند اما ما صفحه ی ۳ را هم الآن در حافظه داریم. پس این ۳ جدید وارد نمی شود و در نتیجه نقص صفحه ای هم ندارد.
حافظه ــــــــ>۳و۴و۵ تعداد نقص صفحه تا اینجا: همچنان ۷
و همچنان قدیمی ترین صفحه، صفحه ۴ است.صفحه بعدی که وارد میشود ۲ است و چون صفحه مشابه ای با آن در حافظه وجود ندارد جای قدیمی ترین صفحه که ۴ است می نشیند و نقص صفحه هم دارد.
حافظه ــــــــ>۳و۲و۵ تعداد نقص صفحه تا اینجا: ۸
حالا قدیمی ترین صفحه ۳ (سه) می باشد.و صفحه جدید الورود ۱ است و چون ۱ در حافظه نیست جایگزین می شود و نقص هم اتفاق می افتد.
حافظه ــــــــ>۱و۲و۵ تعداد نقص صفحه تا اینجا: ۹
حالا قدیمی ترین صفحه ۵ است و صفحه جدیدالورود هم ۵ است که چون در حافظه وجود دارد پس وارد نمی شود. و نقصی هم اتفاق نمی افتد.
وضعیت نهاییحافظه ــــــــ>۱و۲و۵ تعداد نقص صفحه تا اینجا: 9
منبع: alirezafc.blogfa.com
