حافظه مجازی ۴

حافظه مجازی ۴

اسلاید 1: فصل 9: حافظه مجازی

اسلاید 2: حافظه مجازی: جداسازی حافظه منطقی کاربر از حافظه فیزیکیبرای اجرای برنامه تنها قسمتی از آن باید در حافظه قرار گیرد.بنابراین می توان فضای حافظه منطقی را بسیار بزرگتر از فضای حافظه فیزیکی در نظر گرفت.اجازه می دهد فضاهای آدرس توسط چندین پردازه به اشتراک گذارده شوند.اجازه می دهد پردازه ها به صورت بهینه تری ایجاد شوند.می توان حافظه مجازی را به دو طریق ایجاد کرد:روش تقاضای صفحهروش تقاضای قطعهپیش زمینه

اسلاید 3: حافظه مجازی بزرگ تر از حافظه فیزیکی

اسلاید 4: فضای آدرس مجازی

اسلاید 5: کتابخانه ی مشترک با استفاده از حافظه ی مجازی

اسلاید 6: روش تقاضای صفحهزمانی یک صفحه به حافظه منتقل می شود که مورد نیاز باشد.نیاز به عملیات ورودی/خروجی کمترنیاز به حافظه کمترپاسخ سریعترکاربران بیشتروقتی صفحه ای مورد نیاز باشد به آن ارجاع می شود.ارجاع به آدرس نادرست  توقففقدان صفحه در حافظه  آوردن صفحه به حافظهجا به جا کننده ی کند- تنها در صورتی صفحه را داخل حافظه بارگذاری می کند که به آن صفحه نیاز باشد.

اسلاید 7: انتقال یک حافظه صفحه ای به فضای یکپارچه روی دیسک

اسلاید 8: بیت اعتباربه هر مدخل جدول صفحه یک بیت اعتبار اختصاص داده می شود.1  در حافظه، 0  بیرون از حافظهمقداردهی اولیه برای همه مدخل ها: صفرنمایی از یک جدول صفحهاگر در زمان ترجمه آدرس بیت اعتبار صفحه صفر باشد، خطای صفحه (Page Fault) رخ می دهد.1111000Frame #valid-invalid bitpage table

اسلاید 9: جدول صفحه وقتی برخی صفحات در حافظه اصلی نیستند

اسلاید 10: خطای صفحهاگر به صفحه ای ارجاع شود، اولین ارجاع به آن صفحه به سیستم عامل ارسال می شود.سیستم عامل به جدول دیگری مراجعه می کند...ارجاع نادرست  توقف.عدم حضور صفحه در حافظهسیستم عامل یک قاب حافظه خالی می گیرد.صفحه مورد نظر را به قاب منتقل می کند.جداول را reset کرده بیت اعتبار را مساوی یک قرار می دهد.دستورالعمل را از ابتدا اجرا می کند.

اسلاید 11: مراحل رسیدگی به خطای صفحه

اسلاید 12: کارایی روش تقاضای صفحهنرخ خطای صفحه عددی بین صفر و یک است.اگر p = 0 خطای صفحه نداریم.اگر p = 1 تمام ارجاع ها خطا هستند.زمان دسترسی کارا:EAT = (1 – p) x memory access+ p {page fault overhead+ [swap page out ]+ swap page in+ restart overhead}

اسلاید 13: مثالی از روش تقاضای صفحهزمان دسترسی به حافظه: 200 نانوثانیهمتوسط زمان سرویس خطای صفحهEAT = (1 – p) x 200 + p (8 milliseconds) = (1 – p x 200 + p x 8,000,000 = 200 + p x 7,999,800اگر در هر 1000 بار دسترسی به حافظه، یک خطای صفحه رخ دهد، EAT= 8.2 microseconds40 برابر کند شده است!

اسلاید 14: ایجاد پردازهبرخی دیگر از مزایای حافظه مجازی به زمان ایجاد پردازه مربوط می شوند:کپی هنگام نوشتنفایل های در حافظه نگاشت شده

اسلاید 15: کپی هنگام نوشتنکپی هنگام نوشتن به پردازه های پدر و فرزند اجازه می دهد در ابتدای اجرا از صفحه های حافظه مشترک استفاده کنند.هرگاه یک پردازه خواست رو ی صفحه تغییری بدهد، یک نسخه از آن کپی می کند.کپی هنگام نوشتن کارایی ایجاد پردازه را بالا می برد زیرا فقط صفحات تغییرکرده کپی می شوند.معمولا صفحات مورد نیاز از یک استخر (pool) از صفحاتی که با صفر مقداردهی شده اند اختصاص می یابد.

اسلاید 16: قبل از آنکه پردازه 1 صفحه C را تغییر دهد.

اسلاید 17: بعد از آنکه پردازه 1 صفحه C را تغییر داد.Copy of Page C

اسلاید 18: چه اتفاقی می افتد اگر قاب خالی وجود نداشته باشد؟جابجایی صفحه: صفحه ای را که در حافظه اصلی قرار دارد اما از آن استفاده نمی شود یافته و آن را با صفحه مورد نظر جابجا کن.نیاز به الگوریتمی است که به کمترین تعداد خطای صفحه منجر شود.ممکن است یک صفحه چندین بار به درون حافظه منتقل شود.

اسلاید 19: جابجایی صفحهبرای جلوگیری از اختصاص فضای حافظه بیش از فضای موجود، روال سرویس خطای حافظه باید به گونه ای تغییر کند که جابجایی صفحه را نیز در بر بگیرد.از بیت تغییر (یا کثیف) استفاده می کند تا سربار انتقال صفحه را کاهش دهد.تنها صفحاتی که تغییر کرده اند روی دیسک نوشته می شوند.جابجایی صفحه جداسازی حافظه منطقی و حافظه فیزیکی را تکمیل می کند.یک حافظه مجازی بزرگ روی یک حافظه فیزیکی کوچک.

اسلاید 20: نیاز به جابجایی صفحه

اسلاید 21: جابجایی صفحه ابتداییمکان صفحه مورد نظر را روی دیسک پیدا کن.یک قاب صفحه خالی پیدا کن.اگر قاب خالی پیدا شد از آن استفاده کن.اگر قاب خالی پیدا نشد، از یک الگوریتم جابجایی صفحه استفاده کن تا یک قاب به عنوان قربانی انتخاب شود.صفحه مورد نظر را به قاب خالی منتقل کن و جداول قاب و صفحه را به روز کن.پردازه را از ابتدا آغاز کن.

اسلاید 22: جابجایی صفحه

اسلاید 23: الگوریتم های جابجایی صفحهپایین ترین نرخ خطای صفحه مورد نظر است.ارزیابی با اجرای الگوریتم روی یک رشته ارجاع به حافظه و شمارش خطاهای صفحه رخ داده.در مثال های این بخش رشته ارجاع به صورت زیر است:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

اسلاید 24: رابطه بین خطای صفحه و تعداد قاب ها

اسلاید 25: الگوریتم اولین ورودی، اولین خروجیرشته ارجاع:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5سه قاب:چهار قاب: 9 خطای صفحه 10 خطای صفحهاین روش (FIFO replacement) دارای بی نظمی Belady است.قاب های بیشتر  خطاهای صفحه بیشتر12312341253412312351245443

اسلاید 26: جابجایی صفحه الگوریتم اولین ورودی، اولین خروجی

اسلاید 27: الگوریتم اولین ورودی، اولین خروجی و بی نظمی Belady

اسلاید 28: الگوریتم جابجایی بهینهصفحه ای را جابجا کن که تا طولانی ترین زمان ممکن مورد ارجاع قرار نمی گیرد.مثال با چهار قاب: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 6 خطای صفحهبرای سنجش کارایی سایر الگوریتم ها به کار می رود.123445

اسلاید 29: الگوریتم جابجایی بهینه

اسلاید 30: الگوریتم کمترین اخیرترین مورد استفاده (LRU)رشته ارجاع: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5پیاده سازی با استفاده از شمارنده:هر مدخل صفحه یک شمارنده دارد که در هر بار ارجاع مساوی ساعت پردازنده قرار می گیرد.برای جابجایی صفحات، صفحه قربانی بر اساس این شمارنده انتخاب می شود.52431234125412531243

اسلاید 31: جابجایی صفحات در الگوریتم کمترین اخیرترین مورد استفاده (LRU)

اسلاید 32: الگوریتم کمترین اخیرترین مورد استفاده (LRU) (ادامه)پیاده سازی با استفاده از پشته: یک پشته از شماره صفحات را نگهداری کن.ارجاع به صفحه: انتقال صفحه به بالای پشتهنیاز به جستجو برای جابجایی نیست.

اسلاید 33: استفاده از پشته برای نگه داری اخیرترین ارجاع به صفحه ها

اسلاید 34: الگوریتم های LRU تقریبیروش بیت ارجاعبه هر صفحه یک بیت با مقدار اولیه صفر اختصاص بده.ارجاع به صفحه  بیت ارجاع = یک.یکی از صفحه هایی که بیت ارجاع آنها صفر است را برای جابجایی انتخاب کن.ترتیب را نمی دانیم.روش فرصت دوم (Second Chance) نیاز به بیت ارجاع و برچسب ساعت دارد.اگر بیت ارجاع صفحه ای که کوچکترین برچسب ساعت را دارد یک است...بیت ارجاع را صفر کن و صفحه را جابجا نکن.بر اساس همین قوانین به سراغ صفحه بعدی برو.

اسلاید 35: الگوریتم فرصت دوم

اسلاید 36: الگوریتم های شمارشیدر یک شمارنده تعداد ارجاعات به هرصفحه را نگهدار.الگوریتم LFU (Least Frequently Used) : صفحه ای را که کمترین شماره ارجاع را دارد جابجا می کند.الگوریتم MFU (Most Frequently Used) : با این استدلال که صفحه ای که کوچکترین شماره ارجاع را دارد احتمالا به تازگی به حافظه منتقل شده است و هنوز استفاده خواهد شد، صفحه ای را که بیشترین شماره ارجاع را دارد جابجا می کند.

اسلاید 37: اختصاص قابهر پردازه به تعداد حداقلی از صفحات نیاز دارد.مثلا IBM370 برای هر دستور SS MOVE نیاز به 6 صفحه دارد.دستورات 6 بایتی، 2 صفحهدو صفحه برای مبدادو صفحه برای مقصددو روش عمده: اختصاص ثابت و اختصاص اولویت دار.

اسلاید 38: اختصاص قاب ثابت (Fixed Allocation)اختصاص برابر5 پردازه و 100 قاب  هر پردازه 20 قاب.اگر برای پردازه ای یک خطای صفحه رخ داد...یکی از قاب های همان پردازه را برای جابجایی انتخاب کن.یکی از قاب های پردازه با اولویت کمتر را برای جابجایی انتخاب کن.

اسلاید 39: اختصاص قاب ثابت (Fixed Allocation)اختصاص به نسبت اندازه پردازه

اسلاید 40: اختصاص قاب اولویت داربه جای استفاده از اندازه پردازه از یک معیار اولویت برای اختصاص قاب به پردازه ها استفاده کن.اگر برای پردازه ای یک خطای صفحه رخ داد...یکی از قاب های همان پردازه را برای جابجایی انتخاب کن.یکی از قاب های پردازه با اولویت کمتر را برای جابجایی انتخاب کن.

اسلاید 41: اختصاص سراسری و محلی (Global vs. Local Allocation)در جابجایی سراسری (Global replacement) هر پردازه می تواند یک قاب را از میان تمام قاب های موجود در سیستم انتخاب کند.یک پردازه می تواند از قاب یک پردازه دیگر استفاده کند.در جابجایی محلی (Local replacement) هر پردازه تنها می تواند از قاب های اختصاص داده شده به خود استفاده کند.

اسلاید 42: دور ریختن (Thrashing)اگر یک پردازه به تعداد کافی صفحه در اختیار نداشته باشد، نرخ خطای صفحه به شدت بالا می رود.بهره وری پایین پردازندهسیستم عامل تصور می کند لازم است درجه چندبرنامگی را بالا ببرد.پردازه دیگری به سیستم اضافه می شود.به حالتی که یک پردازه مدام مشغول جابجایی صفحات خود باشد Thrashing می گویند.

اسلاید 43: دور ریختن (trashing)

اسلاید 44: تقاضای صفحه و دور ریختن (Thrashing)چرا صفحه بندی موثر است؟مدل موضعی (Locality Model) : یک پردازه از یک موضع به یک موضع دیگر مهاجرت می کند.ممکن است چند موضع با یکدیگر همپوشانی داشته باشند.چرا Thrashing رخ می دهد؟مجموع اندازه موضع ها  کل اندازه حافظه

اسلاید 45: Locality در یک الگوی ارجاع به حافظه

اسلاید 46: مدل مجموعه کاری (Working Set) یا مجموعه کاری به صورت تعداد ثابتی ارجاع به حافظه مشخص می شود، مثلا 10000 دستور. WSSi (مجموعه کار پردازه i) را به صورت تعداد صفحاتی که در آخرین مجموعه کاری مورد ارجاع قرار گرفته اند تعریف می کنیم.اگر  خیلی کوچک باشد، تمام یک موضع (Locality) را شامل نمی شود.اگر  خیلی بزرگ باشد، چندین موضع را شامل می شود.اگر  بی نهایت باشد، تمام برنامه را شامل می شود. D =  WSSi مجموع قاب های مورد نیاز می باشد.اگر D بزرگتر از اندازه حافظه باشد، دور ریختن (trashing) رخ می دهد. راه حل: معلق کردن یکی از پردازه ها

اسلاید 47: نگهداری سوابق مجموعه کاریتخمین با استفاده از زمان سنج وقفه ای و یک بیت ارجاعمثال:  = 10000زمان سنج پس از هر 5000 واحد زمانی یک وقفه می زند.برای هر صفحه دو بیت در حافظه در نظر بگیر.با هر وقفه مقدار بیت های ارجاع را کپی و سپس همه بیت های ارجاع را صفر کن.اگر هر یک از این بیت ها در حافظه یک بود، صفحه در مجموعه کاری پردازه است.این مدل دقیق نیست، برای بهبود 10 بیت در نظر بگیر و هر 1000 واحد زمانی وقفه ایجاد شود.

اسلاید 48: مدل بسامد خطای صفحهنرخ خطای صفحه قابل قبول را مشخص کن.اگر نرخ واقعی خیلی پایین  قاب های آن پردازه را کم کن.اگر نرخ واقعی خیلی بالا  قاب های آن پردازه را زیاد کن.

اسلاید 49: مدل مجموعه کاری

اسلاید 50: فایل های در حافظه نگاشت شده در این مکانیزم یک بلوک روی دیسک به یک صفحه در حافظه نگاشت می شود.فایل های در حافظه نگاشت شده اجازه می دهد عملیات ورودی/خروجی روی فایل به صورت عملیات دستیابی به حافظه انجام شود.این فایل ها با روش تقاضای صفحه خوانده می شوند.قسمتی از فایل که به اندازه ی صفحه است، از سیستم فایل به یک صفحه ی فیزیکی خوانده می شود و به حافظه اصلی منتقل می شود.دستیابی های بعدی به صورت دستیابی معمولی به حافظه انجام می شوند.این روش دستیابی به پرونده را با جایگزینی دستورات دستیابی به حافظه به جای فراخوانی های سیستمی read () و write () تسهیل می کند.همچنین اجازه می دهد چندین پردازه یک فایل را به اشتراک بگذارند.

اسلاید 51: فایل های در حافظه نگاشت شده

اسلاید 52: حافظه ی مشترک نگاشت شده در windows

اسلاید 53: اختصاص حافظه ی kernelمتفاوت با حافظه ی کاربر با آن برخورد می شود.معمولا از یک استخر حافظه ی آزاد اختصاص می یابد.کرنل درخواست حافظه برای ساختارهای با اندازه های متفاوت می کند.بعضی حافظه های کرنل، باید پیوسته باشند.

اسلاید 54: سیستم buddyحافظه را از بخش هایی با اندازه ی ثابت که شامل صفحات به طور فیزیکی پیوسته اند، اختصاص می دهد.حافظه ی اختصاص داده شده از اختصاص دهنده ی توان 2 استفاده می کند.در خواست ها را در واحد هایی به اندازه ی توانی از 2 بر آورده می کند.در خواست تا نزدیک ترین توان 2 بزرگتر گرد می شود.وقتی اختصاص کوچکتری از آنچه در دسترس است نیاز است، بخش فعلی به دو قسمت به اندازه ی نزدیکترین توان کوچکتر 2 تقسیم می شوند.این روش ادامه می یابد تا بخش هایی با اندازه ی مناسب ایجاد شود.

اسلاید 55: اختصاص دهنده ی سیستم buddy

اسلاید 56: اختصاص دهنده ی slabروش جایگزینSlab یک یا چند صفحه ی فیزیکی پیوسته است.Cache شامل یک یا چند slab است.یک cache برای هر ساختمان داده ی یکتای کرنلهر cache با شیء ها پر شده است- نمونه های ساختمان دادهوقتی cache ساخته می شود، پر از اشیائی است که آزاد شناخته می شوند.وقتی ساختار ذخیره می شود، اشیا به عنوان مصرف شده شناخته می شوند.اگر slab پر از اشیاء مصرف شده باشد، شیء بعد از slab خالی اختصاص می یابد.اگر slab خالی نبود، slab جدید اختصاص می یابد.مزایا : بدون فضای قطعه قطعه، اختصاص سریع حافظه

اسلاید 57: اختصاص به روش slab

اسلاید 58: سایر موارد - پیش صفحه بندیپیش صفحه بندی (Prepaging)بزای جلوگیری از تعداد زیاد خطای صفحه که در زمان شروع اجرای یک پردازه ایجاد می شود..راه حل: تمام یا تعدادی از صفحات مورد نیاز پردازه را قبل از آنکه مورد ارجاع قرار بگیرند.اما اگر این صفحات از قبل آماده شده مورد استفاده قرار نگیرند، ورودی/خروجی و حافظه اتلاف شده است.فرض کنید s صفحه پیش صفحه بندی شده و a صفحه مورد استفاده قرار گرفته استهزینه ی s * α برای جلوگیری از خطای صفحه بیشتر است یا s * (1- α) هزینه ی صفحات غیر لازم؟اگر a نزدیک 0 باشد، پیش صفحه بندی شکست خورده است.

اسلاید 59: سایر موارد - اندازه ی صفحهانتخاب اندازه صفحهموثر بر قطعه قطعه گیاندازه جدول صفحهسربار ورودی/خروجیlocality

اسلاید 60: سایر موارد - حافظه قابل دسترسی توسط TLBحافظه قابل دسترسی توسط TLB (TLB Reach)TLB Reach = (TLB Size) X (Page Size)ایده آل آن است که مجموعه کاری هر پردازه در TLB ذخیره شود، در غیر این صورت نرخ خطای صفحه بالا می رود.می توان حافظه قابل دسترسی توسط TLB را با افزایش اندازه صفحه افزایش داد.افزایش قطعه قطعه گی در پردازه های نیازمند به صفحات کوچکراه حل: استفاده از اندازه صفحات در اندازه های مختلف به برنامه هایی که اندازه ی صفحه بیشتری نیاز دارند، شانس استفاده از صفحات بزرگتر بدون افزایش قطعه قطعه گی می دهد.

اسلاید 61: ساختار برنامه:Int[128,128] data;هر سطر در یک صفحه ذخیره شده است.برنامه یک:for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i,j] = 0;تعداد خطای صفحه: 128 x 128 = 16,384برنامه دو:for (i = 0; i < 128; i++)for (j = 0; j < 128; j++)data[i,j] = 0;تعداد خطای صفحه: 128سایر موارد - ساختار برنامه

اسلاید 62: برخی اوقات باید یک صفحه در حافظه اصلی قفل شود و جابجا نشود.برای مثال یک صفحه حافظه که برای کپی یک فایل از یک ابزار استفاده می شود نباید توسط الگوریتم های جابجایی صفحه برای خروج از حافظه اصلی انتخاب شود.سایر موارد – قفل داخلی ورودی/خروجی

اسلاید 63: صفحاتی که اعمال ورودی/خروجی انجام می دهند نباید از حافظه خارج شوند.

اسلاید 64: بررسی یک سیستم عامل: Windows XPاز روش تقاضای صفحه به همراه گروه بندی (clustering) استفاده می کند.گروه بندی باعث می شود صفحات پیرامونی صفحه ای که خطای صفحه ایجاد کرده است نیز به درون حافظه آورده شوند.هر پردازه یک مجموعه کاری مینیمم و یک مجموعه کاری ماکزیمم دارد.مجموعه کاری مینیمم حداقل تعداد صفحاتی است که یک پردازه به صورت تضمینی در حافظه دارد.یک پردازه می تواند حداکثر به اندازه مجموعه کاری ماکزیمم صفحه داشته باشد.

اسلاید 65: وقتی مقدار حافظه آزاد سیستم از یک مقدار آستانه خاص کمتر می شود، روال ساماندهی خودکار مجموعه کاری فراخوانی می شود تا مقداری حافظه آزاد کند.روال ساماندهی خودکار صفحاتی از مجموعه کاری صفحات پردازه هایی را که بیش از مجموعه کاری مینیمم خود صفحه دارند حذف می کند.بررسی یک سیستم عامل: Windows XP (ادامه)

اسلاید 66: بررسی یک سیستم عامل : سولاریسلیستی از صفحات آزاد برای اختصاص به صفحات خطاخورده نگهداری می کند. Lotsfree پارامتر آستانه (میزان حافظه ی آزاد) برای آغاز صفحه بندی است.Desfree پارامتر آستانه برای افزایش میزان صفحه بندی است.Minfree پارامتر آستانه برای شروع جابجایی صفحات است.صفحه بندی با استفاده از پردازه pageout انجام می شود. pageout صفحات را با استفاده از الگوریتم ساعت تغییریافته پویش می کند. scanrate نرخ پویش صفحه هاست. این نرخ بین پویش کند و پویش تند تغییر می کند.Pageout بسته به میزان حافظه ی آزاد در دسترس فراخوانی می شود.

اسلاید 67: پویشگر صفحه سولاریس 2

اسلاید 68: پایان فصل نهم