حافظه مجازی

صفحه 1:


صفحه 2:


صفحه 3:


صفحه 4:
حافظه ی مجازی تکنیکی است که موجب می شود فرآیند بدون اینکه کاملا در حافظه باشد اجرا گردد. امتیاز عمده این الگو این است که ممکن است برنامه ها بزرگتر از حافظه ی فیزیکی باشند. 1-0 مرور کلی برای قرار گرفتن دستورات در حال اجرا در حافظه یک روش این است که کل فضای آدرس منطقی در حافظه ی فیزیکی قرار گیرد اما اين روش موجب می شود که اندازه ی برنامه به اندازه ی حافظه ی فیزیکی محدود شود. 

صفحه 5:
دزضوارد زیر » اغلب تیار هکل ترناههآنجست:؛ ۰ برنامه ها اغلب برای پردازش خطای نادر نوشته می شوند که اغلب اجرا نمی شوند ( به دلیل ندرت رخداد خطا ) ۰ به آرایه ها , لیست ها و جداول ؛ حافظه ای بیش از اندازه مورد نیاز تخصیص می یابد بعضی ویژگی ها و گزینه های برنامه ممکن است به ندرت مورد استفاده قرار گیرند. توانایی اجرا برنامه ای که فقط بخشی از آن در حافظه قرار گیرد فواید زیادی دارد : * اندازه ی برنامه به فضای فیزیکی محدود نمی شود 8 " چون هر برنامه کاربر می تواند فضای فیزیکی کمتری را اشغال 

صفحه 6:


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

صفحه 8:


صفحه 9:
2-0 صفحه بندی درخواستی یک سیستم صفحه بندی درخواستی مشابه سیستم صفحه بندی به همراه مبادله است. فرآیند ها در حافظه ی ثانویه ( معمولا دیسک ) ذخیره می شوند. برای اجرای فرآیند آن را به حافظه می آوریم. ۲ اجرای انتقال کامل فرآیند به حافظه » از مبادله کننده تنبل ( بتكنا ری ) استفاده می شود که این مبادله تا زمانیکه فرآیندی سورد نیاز نباشد آن را به حافظه نمی آورد. + بيت ا لاد اطع سان دا سای 

صفحه 10:
4 5 ]۰ زاهبادله به خارج برنامة © 9 7 ۲ 1 شاد بدا برنامة 

صفحه 11:
1-2-0 مفاهیم اساسی وقتی فرآیندی باید به حافظه مبادله شود , صفحه بند حدث می زند که قبل از این که فرآیند از حافظه خارج شود چه صفحه ای مورد استفاده قرار خواهد گرفت بنابراین به جای اينکه کل فرآیتد زا بة بحافطظه بیآوزد .عمط سعحات موره. ییاز زا وآرد حافظه می کند. ۲ در این اگو نیاز به پشتیبانی سخت افزار داریم تا بین صفحات موجود: در حاقظه و متشحاتموجود ادن ديصق حفکیک: قانل شویم که برای این منظور الگوی بیت اعتبار مورد استفاده قرار می گیرد. 

صفحه 12:
حافظه فیزیکی ‎٠ ٠ > © © 8 8 8 8 6 8‏ ۶ 0 م “ ‎& oO © ‏چم ‏© ۵ 9 © © © ۰ و ‏یت اعتبار قاب ‎6 ۵ ۵ ۵ ۵ 6 ‏جدول صفحه حافظه منطقی ‏© © ۵ ۶ 0 ۵ ۰ و ‎es: ‎ 

صفحه 13:
اگر فرآیندی سعی کند از صفحه ای استفاده کند که در حافظه نیست : دستیابی به صفحه ای که به صورت صفحه ای نامعتبر علامت گذاری شده است ؛ منجر به تله ی خطاهای ‎(Pag Pout) arturo‏ می شود. سخت افزار صفحه بندی برای ترجمه آدرس از طریق جدول صفحه متوچه.می شود که بیت نا فعتبر یک است و تله ای را به 

صفحه 14:
صفحه در حافظه © 

صفحه 15:
روش مقابله با اين نوع خطای صفحه : !. جدول مربوط به این فرآیند را که معمولا در 06 فرآیند ذخیره می شود , بررسی می شود تا مشخص شود آیا مراحعه معتبر بوده يا خیر اا. اگر ارجاع نا معتبر بود فرآیند را خاتمه می دهیم و اگر معتبر بود وب به حافظه نیامده بود آن را به حافظه می آوریم ااا.یک قاب آزاد را می یابیم ‎IV‏ عملیات دیسک را زمانبندی می کنیم تا صفحه مورد نظر را به قابی که الان تخصیص یافته است بخوانیم ‏۷ وقتی خواندن از دیسک آغاز شد , جدول صفحه و جدول داخلی را ‏همراه فرآیند نگهداری شده است اصلاح می کنیم تا بیانگر اين باشد که آن صفحه فعلا در حافظه نیست 

صفحه 16:
لا نکته : برنامه ها تمایل به ارجاع محلی دارند که منجربه کارآیی معقولی در صفحه بندی درخواستی می شود ( اینطور نیست که برنامه ها به چندین صفحه جدید دستیابی داشته باشند و دچار چندین خطای صفحه شوند ) سخت افزار پشتیبان صفحه بندی درخواستی , همانند سخت افزار صفحه بندی و مبادله است : ۷ جدول صفحه : اين جدول از طریق بیت اعتبار یا بیت های حافظه می تواند ورودیی را به عنوان ورودی نامعتبر علامت گذاری کند. 

صفحه 17:
لا نکته : علاوه بر پشتیبانی سخت افزاری نیاز به نرم افزار قابل ملاحظه ای نیز می باشد. از سر گیری اجرای یک دستور در صورت خطای صفحه : 1 اگر خطای صفحه هنگام مکش (6۳۲) دستور رخ دهد » می توانیم آن دستور را دوباره مکش کنیم. 2 اك هتكام امكش ريك عملونه خطاي صفحة رع دهدة: | دوباره " ۳ | رمزگشایی 

صفحه 18:
أفظه مجازی 2-2-0 كارآيى صفحه بندى درخواستى صفحه بندی درخواستی تأثیر به سزایی در کارآیی سیستم کامپیوتری دارد. برای پی بردن به این موضوع زمان دستیابی موثر را برای صفحه بندی مجازی محاسبه می کنیم. ( زمان دستیابی موثر < زمان دستیابی سحانحاه زطلکر خطاطیی به حافظه صفحه به وجود نیاید ) احتمال بروز زمان خطای موثر * (04) * مب + هگای‌مانفحصتیابی موثر ‎sly‏ محاسبه ی زمان دستیابی موثر ؛ باید بدانیم که برای ارائه خدمات به خطای صفحه , چقدر زمان نیاز است 

صفحه 19:
< خطای صفحه موجب می شود تا اعمال زیر صورت گیرد: 1 ارسال تله بة سجستم: 2 ذخیره ثبات هاى كاربر و حالت فرآيند. 3 تعیین اینکه وقفه ناشی از خطای صفحه بود. 4 کنترل شود که اجرا به صفحه معتبر بود يا خیر و تعیین محل صفحه دیسک. 5 خواندن از دیسک و اثثقال به یک قاب آزاد. الف - انتظار در صف آن دستگاه تا ارائه خدمت ب - انتظار برای پیگرد دستگاه و یا زمان تخیر 

صفحه 20:
52.6 زمان انتظار برای دیسک ؛ 000 به کار دیگری تخصیص می یاید (زمانبندی 060). 7.وقفه ای از دیسک ( کامل شدن عمل 1/0 دیسک ). 8.ذخیره ی ثبات ها و حالت فرآیند برای کاربر دیگر ( اگر مرحله 6 انجام شده باشد ). 9 .تعیین اينکه وقفه از دیسک بوده است. 0 تصحیح جدول صفحه و ساير جدول ها تا نشان داده شود که صفحه مطلوب فعلا در حافظه است. 1 انتظار برای تخصیص مجدد 060 به این فرآیند. 

صفحه 21:
*#تذکر : ممکن است تمام این مراحل در هر مورد الزامب باشند. در هر مورد , خطای صفحه شا سه زمان است که ناشی از سه عمل می باشد: می توانند با کد نویسی دقیق به چند که ستور گاهس 1 ارائه خدمات به وقفه خطا 2 خواندن صفحه به حافظه 3. اجرای دوباره ی فرآيند مه خطای صفحه شده اند » 

صفحه 22:
سیستم های با فضای مبادله محدود » برای فایل های باینری از الگوی زیر استفاده می کنند: !. صفحاتی که در فایل های باینری درخواست می بشتوند. مستقیما از سیستتج فایل آوزده مین شوند: وقتی آن صفحات باید جایگزین شوند . صفحات جدید بروی آنها نوشته می شوند و در صورت لزوم » دوباره باید از سیستم فایل خوانده شوند. اا. صفحات از همان اولاز همان اول از سبستم فایل درخواست شوند ولی هنگام جایگزینی در فضای مبادله نوشته شوند. ت کند که فقط صفحات د نباز از 

صفحه 23:


صفحه 24:
3-0 ایجاد فرآیند در بخش 10-2توضیح دادیم که فرآیند چگونه با صفحه بندی درخواستی شروع کند. با استفاده از اين تکنیک ؛ فرآیند فقط بوسیله ی صفحه بندی درخواستی در صفحه ای که حاوی اولین دستور است , آغاز می شود. اما , صفحه بندی و حافظه ی مجازی در اثنای ایجاد فرآیند , فواید دیگری نیز دارند . در اینجا در تکنیک که توسط حافظه مجازی فراهم می شود و کارآیی ایجاد و اجرا فرآیند را بهبود می بخشد , شرح داده مى شود. 

صفحه 25:
افظه مجازی 1-3-0 کپی و نوشتن صفحه بندی درخواستی هنكام خواندن فایل از دیسک ‎a,‏ حافظه نورد استحفاده:فزاز سن کیرد و این فایل. مکن آست«حاود دودویی قابل اجرا باشد , اما ایجاد فرآیند با استفاده از فراخوان سیستم ۳:۲() , می تواند با استفاده از تکنیکی مشابه با اشتراک صفحه , نیاز به صفحه بندی درخواستی را برطرف کند. این تکنیک سرعت ایجاد فرآیند را افزایش می دهد و تعداد متقحاتن را که .هنگام انجاه قرآیند جدیدباند بوجود آیبهزا چه حداقل می رساند. 

صفحه 26:
افظه مجازی *#تذکر * با توجه ‎aS yl a‏ فرآیند های فرزند ایجاد شدند , فراخوان سیستم تحح() را فراخوانی می کنند , كبى كردن فضاى آدرس پدر ممکن است ضروری نباشد. ۲ از طرف دیگر , می توانیم از تکنیکی به نام کپی و نوشتن (بوه 0 8۵) استفاده کنیم. روش کپی و نوشتن : در این روش , فرآیندهای پدر و فرزند از همان آغاز , از صفحات یکسانی استفاده می کنند. ا ات ‎iS‏ و نوشتن علامت 

صفحه 27:
* تذکر : تکنیک کپی و نوشتن , هتگام تکثیر فرآیند در سیستم ‎Sly‏ ‏عاملی مثل ویندوز 2000 , لینوکس و سولاریس 2 مورد استفاده قرار می گیرد. ‎(AUS acne SIRS Sages‏ نس( از تعیین !الک صفاتها الق باید نا استفاده از کپی و نوشتن تکثیرشود: ‏بسیازی ار سیسعم:عامل:هایحخربی (ی) از سقجات آراد بزای لین درخواست ها فراهم می کنند. ‏* این صفحات آزاد وقتی تخصیص می یابند که پشته یا هرم مربوط ‏به فرآیند باید بسط یابد پا صفحات کپی و نوشتن باید مدیریث 

صفحه 28:
لانکته : سیستم های عامل این صفحات را با تکنیکی به نام پر کردن با صفر در هنگامه تقاضا (لمصمط -م - ۷ -سد) تخصیص می دهند. تکنیک پر کردن با صفر در هنگام تقاضا : در این تکنیک صفحات درخواستی قبل از تخصیص با صفر پر می شوند و در نتیجه محتویات قبلی آن از بین می روند. لانکته : در تکنیک کپی و نوشتن » صفحه ای که می خواهد کپی ‎seit‏ اک اس کت سفن تست كيف هف كرت 

صفحه 29:
2-3-0 فایل های نگاشت حافظه نگاشت حافظه فایل تکنیکی است که با تکنیک حافظه ی مجازی ؛ با 0 فایل به عنوان روال دستیابی به حافظه استفاده می کنند. * رهیافت نگاشت حافظه فایل اجازه می دهد بخشی از فضای آذریتن عجازینبه طور محظفی به قایل:مربوط شوب 

صفحه 30:
نکات : 1 برای نگاشت حافظه ی یک فایل بلوک دیسک به صفحه ( صفحاتی ) در حافظه نگاشته می شود. 2 دستیابی اولیه به فایل از طریق صفحه بندی درخواستی عادی انجام می شود و منجر به خطای صفحه می گردد اما بخشی از فایل که به اندازه ی صفحه است , از سیستم فایل به صفحه ی فیزیکی خوانده می شود. 3 خواندن و نوشتن های بعدی در فایل به صورت روال های دستیابی به حافظه اداره می شوند. بدین ترتیب , چون دستکاری فایل ها به جای فرخوان سبستم لمحب() و عس() از 

صفحه 31:
لانکته : عمل نوشتن در فایلی که در حافظه نگاشت شده است , ممکن است فورا در فایل روی دیسک انجام نشود. < بعضی از سیستم های عامل نگاشت حافظه را فقط از طریق فراخوان سیستم خاصی انجام می دهند و با استفاده از فراخوان یسم انسلسارد»: با :5 سابل جرسوره می ‎su‏ ‎NaS fits ie Lota fl pice LS‏ قانلی بة عنؤان فاب نگاشت حافظه مشخص شده است یا خیر آن را به صورت نگاشت جاقطه در نظن من ‎1213S‏ ‏#تذکر : ممکن است چند فرآیند بتوانند به یک فایل در حافظه ی مجازی نگاشت شوند تا اشتراک داده به وجود آید. 

صفحه 32:


صفحه 33:


صفحه 34:
در بحث هایی که تا کنون گفته شد نرخ خطای صفحه چندان جدی نبود چرا که هر صفحه حداکثر یک بار ( هنگامیکه اولین بار به آن ارجاع می شود ) دچار خطای صفحه می گردید. 7 اگر فرآیند 10 صفحه ای فقط نیمی از آنها استفاده کند صفحه بندی درخواستی , در ‎VO‏ مورد نیاز برای 5 صفحه ی دیگر صرفه همچنین می توانستیم با اجرای در برابر فرآیندها ؛ درجه چندبرنامه ای را بالا ببریم , لذا اگر 40 قاب می داشتیم می 

صفحه 35:
تخصیص اضافی : اگر درجه چندبرنامه ای را بالا ببریم » تخصیص اضافی حافظه صورت می گیرد. تخصیص اضافی حافظه بدین ترتيب عمل مى کته : ‎٠‏ در حالیکه فرآیند کاربر در حال اجراست ؛ خطای صفحه رخ می دهد. ‎٠‏ سخت افزار تله ای را به سیستم عامل می فرستد و سیستم عامل جدول های داخلی خود را بررسی می کند تا ببیند آیا اين 

صفحه 36:


صفحه 37:
0 طرح اصلی .جابگزیتی. صفحه جایگذینی صفحه به این صورت عمل می کند : 9 اگر قاب آزادی موجود نباشد قابی را پیدا می کنیم که فعلا در حال استفاده نیست و آن را آژاد می کنیم. لا برای آزاد کردن قاب » محتویات آن را در فضای مبادله می نویسیم و جدول صفحه ( و ساير جداول ) را تغییر می دهیم ( تا نشان دهیم صفحه فعلا در حافظه نیست ) 

صفحه 38:
روال خدمات خطای صفحه به صورت زیر تغییر می کند تا جایگذینی صفحه را نیز انجام دهد. ‎«I‏ محلی از دیسک را بیابد که صفحه مطلوب در آنجا قرار دارد. ‎I‏ قاب آزاد را بيابد : ‎all,‏ اکن ها آزاد وجوه نازد ار آن انستفاده کید ‏جحوكره با اسفایه ان الگووسم خانگوسی سطع بلك ان را ‏برای قربانی کردن انتخاب نماید ( آن قاب را خالی کند) ‏ج - صفحه ی قربانی را بروی دیسک بنویسد و جدول قاب و صفحه را ‏.نیز بطور مناسب تغییر دهد ‏ااا. صفحه مطلوب را به قاب آزاد منتقل کند و جداول صفحه و قاب 

صفحه 39:
رز قاب صفحة قربانی \ برای مباله با خارج ‎TO ee‏ قرباد نامعتبر مام 5 تفت تنظیم مجدد ی ‎ern‏ براى صفحة مطلوب به دن حافظه 

صفحه 40:
لانکته : اگر قاب خالی موجود نباشد نیاز به دو انتقال صفحه است ( یکی برای خروج از صفحه و دیگری برای ورود به صفحه ) بدین ترتیب زمان خدمات خطای صفحه دو برابر می شود و زمان دستیابی موثر نیز افزایش می یابد. ربا ناقشى ‎pat‏ وجود قاب حالی,با استفاده آر پیت اصلاح کاهش می یابد : ‎٠‏ هر صفحه یا قاب می تواند بیت اصلاح مخصوص به خود را در ‏سخت افزار داشته باشد. ‎ ‎2-3-0-2 a 3 

صفحه 41:
+ اوقتی تفج آی زا برای جایگزیتی آنتخاب ‎oe‏ کنیع« ببت لظلا آن را بررسی می کنیم. 0 اگر برابر با یک باشد : متوجه می شویم که هنگام خواندن از دیسک تغییر کرده است و در این حالت می بایست آن صفحه را بروی دیسک بنویسیم. تاکز ترایز نا ‎ey‏ تباشتد, زابه معناق. این است. که صفحه هنگام خوانده شدن به حافظه تغییر نکرده است بنابراین اگر کیی صفحه موجود در دیسک 

صفحه 42:
نکات : 1 این تکنیک به صفحات فقط خواندنی ( مثل صفحات كد باينرى ) اعمال مى شود 2. اين الكو زمان ارائه خدمات به خطاى صفحه را كاهش مى دهد , زیرا در صورتیکه صفحه تغییر نکند » زمان ‎VO‏ به نصف تغليل مى يابد. تذکر : جایگزینی صفحه اساس کار صفحه بندی درخواستی است ۳ برای:پیاده سازی تفحه بیدی: دوجواستی ,دی فسقله را باند حل re 

صفحه 43:
۲ اگر چندین فرآیند در حافظه باشند , باید تصمیم بگیریم که چند قاب به هر فرآیند تخصیص يابد. ۲" علاوه بر این , در صورت نیاز جایگزینی صفحه , قاب هایی را که بايد جايكزين شوند انتخاب می کنیم. لا نکته : با افزایش تعداد قاب ها , تعداد خطاهای صفحه به حد ‎sl aid‏ کاهش می یابد. البته افزايش حافظه فیزیکی نیز منجربه افزایش تعداد قاب ها می شود. 

صفحه 44:
تعداد قاب oO 9 & oO oO 9 لاه © ه ه وه وه وه وه ۱ وه عمج رد 

صفحه 45:
2-4-0 الگوریتم ۳۹۵ اين الگوریتم ,برای هر صفحه » زمان ورود آن صفحه به حافظه را ثبت می کند. هر وقت صفحه ای بخواهد جایگزین شود , قدیمی ترین صفحه برای جایگزینی انتخاب می گردد. لا نکته : لازم نیست زمان ورود به حافظه ثبت شود , بلکه مى توانیم یک صف 10 ایجاد کنیم تا تمام صفحات موجود در حافظه را نگهداری کند. برای جایگزینی , صفحه موجود در ابتدای صف را انتخاب می کنیم , وقتی صفحه به حافظه آورده شد آن را در انتهای این صفحه قرار می دهیم. 

صفحه 46:


صفحه 47:
لا نکته : کارایی الگوریتم 0 همواره خوب نیست چرا که صفحه ای که جایگزین شد ممکن است یک پیمانه ی ارزش دهی اولیه باشد که مدت ها قبل مورد استفاده قرار گرفته است و فعلا نیازی به آن نیست. از طرف دیگر ممکن است حاوی متغیر های پر استفاده ای باشد که قبلا مقدار اولیه گرفتند و دائما مورد استفاده قرار می گیرند. لا نکته : از را خن الگفرشم ها اجایگوخین سقحه و نرق لاج صفحه با افزایش قاب های تخصیص یافته , افزایش می یابد ( تناقض بیلدی - سس له ) 

صفحه 48:
9 a e 9 تعداد قاب oe لاه © ه ه وه وه وه وه ۱ وه عمج رد 

صفحه 49:
3-4-0 الگوریتم بهینه * نرخ خطای صفحه در الگوریتم جایگزینی صفحه بهینه » نسبت به سایر الگوریتم ها کمتر است. ۰ الگوریتم بهینه دچار تناقض بهینه نمی شود. ۰ استفاده از این الگوریتم تضمین می کند که نرخ خطای صفحه برای تعداد ثابتی از قاب ها » کمینه است. ‎٠‏ یک الگوریتم بهینه وجود دارد که به نام های ‎OPT‏ یا 010 خوانده می شود و به صورت زیر است. ‏[| صفحه ای را که به مدت طولانی مورد استفاده قرار نمی گیرد . جایگزین کنید. 

صفحه 50:


صفحه 51:
4-4-0 الگوریتم ۵ اگر تهیه الگوریتم بهینه امکان پذیر نباشد , تقریبی از آن الگوریتم آشکان: پیز است: تفاوت ‎yu‏ الگوریتم های 10 و 067 : الگوریتم ۵۹0 از زمان ورود به حافظه استفاده می کند و الگوریتم 0۳۲ از زمانیکه صفحه مورد استفاده قرار می گیرد استفاده می کند. ۵ : اگر از گذشته ی نزدیک‌به عنوان‌تقریبی‌از آیندم ی 

صفحه 52:


صفحه 53:
* الگوریتم ۷۸۵ آخرین زمانی را که هر صفحه مورد استفاده قرار گرفته است ثبت می کند و برای جایگزینی یک صفحه , ۲۵ صفحه ای را انتخاب می کند که برای مدت طولانی تری مورد استفاده قرار نگرفته است. ل نکته : الگوریتم بهینه جایگزینی ۷۵ زمان را به صورت معکوس نگاه می کند یعنی اگر *۵ را معكوس رشته مراجعت 6 در نظر بگیریم , آنگاه نرخ خطای صفحه برای الگوریتم 00 بروی 6 همانند نرخ صفحه برای الگوریتم 00 بروی *6 است به طور مشابه نرخ خطای صفحه بروی الگوریتم ۷۵ بروی 6 , همانند 

صفحه 54:
دو روش برای تعیین اینکه چگونه می بایست برای قاب هایی که توسط آخرین زمان استفاده تعریف شده اند ء ترتیبی را تعیین کرد » وجود دارد : 1ستفاده از شمارنده 2.استفاده از پشته 

صفحه 55:
1 استفاده از شمارنده : در ساده ترین حالت برای هر ورودی جدول صفحه , فیلدی به نام فیلد زمان استفاده در نظر می گیریم و به 0060 یک ساعت منطقی يا شمارنده اضافه می کنیم. 7 در هر مراجعه به حافظه , یک واحد به ساعت اضافه می شود. 7 هر وقت به صفحه ای مراجعه می شود , محتویات ثبات ساعت به فیلد ژمان استفاده در جدول صفحه ی مربوط به آن صفحه کپی می شود. بدین ترتیب ؛ آخرین زمان مراجعه به هر صفحه را می دانیم © صفحه ای را جایگزین می کنیم که مقدار زمان آن از همه کمتر 

صفحه 56:
% * تذکر : این الگو مستلزم جستجوی جدول صفحه است تا صفحه 0 پیدا شود و همچنین در هر دستیابی به حافظه نیاز به نوشتن در صفحه است ( فیلد زمان استفاده باید در جدول صفحه کپی شود ) 2 استفاده از پشته : روش دیگر پیاده سازی ۱۵ استفاده از پشته ای است که از شماره صفحات نگهداری می کند. 50 هر وقت به صفحه ای مراجعه شود , از پشته حذف شده در بالای پشته قرار می گیرد. 7 بدین ترتیب , آخرین صفحه ای که مورد استفاده قرار گرفته است هميشه در بالای پشته قرار دارد و صفحه 7۲0 در پایین پشته 

صفحه 57:
رشته مراجعات a 

صفحه 58:
# تذکر : چون عناصری باید از میانه پشته حذف شوند » بهتر است پشته به صورت لیست دو پیوندی پیاده سازی گردد. نكات : ‎«I‏ هیچکدام از الگوریتم های بهینه و ۵۵ دچار تناقض بیلدی نمی شوند. اا. هیچکدام از پیاده سازی های 7۲۵ بدون پشتیبانی سخت افزاری و استفاده از ثبات های ۲۷۵ انجام پذیر نیست. ااا. دسته ای از الگوریتم های جایگزینی صفحه به نام الگوریتم های پشته ای وجود دارد که هیچگاه دچار تناقض بیلدی نمی 

صفحه 59:
الگوریتم پشته ای : الگوریتمی است که در آن , مجموعه ای از صفحات موجود در حافظه برای » قاب , هميشه زیر مجموعه ای از صفحاتی ‎cH Shy oS cowl‏ قاب در حافظه خواهند بود. آلابرای جایگزینی 00 مجموعه صفحات موجود در حافظه , آخرین جصتفحه آف که به مها جراعم سوة اسع آگااگر تعداد قاب ها افزایش یابد : اين > هنوز صفحاتی خواهد بود که اخیرا به ّن قا مراجعه شده است و در حافظه باقی می ‎eee‏ 

صفحه 60:
افظه مجازی 5-4-0 تقریبی از الگوریتم ۱۵0 سخت افزار لازم برای پشتیبانی از ۷۵ ؛ برای اغلب سیستم های کامپیوتری مهیا نیست. بعضی از سیستم ها از بیت ارجاع برای کمک به الگوریتم جایگزینی استفاده می کنند. روش بیت ارجاع : | هر ورودی جدول صفحه , دارای یک بیت ارجاع است | در آغاز تمام بیت ها توسط سیستم عامل صفر می شوند | وقتی فرآیند کاربر اجرا می گردد ؛ بيت ارجاع مربوط به هر ارحاع شده است , توسط سخت ! 1 

صفحه 61:
| با استفاده از بیت ارجاع می توانیم تعیین کنیم که کدام صفحات تاکنون مورد استفاده قرار گرفته اند و کدام صفحات مورد استفاده واقع نشده اند ولی ترتیب استفاده از آن ها مشخص نیست . این اطلاعات جزئی در مورد ترتیب صفحات منجربه الگوریتم هایی می شود که تقریبی از الگوریتم 6۵| هستند. 1-5-4-0 الگوریتم بیت ارجاع اضافی با ثبت بیت های ارجاع با فواصل زمانی منظم » اطلاعات بیشتری راجع به ترتیب مراجعه به صفحات بدست می آوریم. می توانیم برای هر صفحه 8 بیت (1 سبا) را در جدولی در حافظه نگهداری کنیم. در فواصل زمانی منظم , یک وقفه از تایمر ؛ 

صفحه 62:
۰ سیستم عامل بیت ارجاع مربوط به هر صفحه را به بيت با ارزش بايت 8 بيتى شيفت مى دهد. براى اين منظور » بقيه ى بيت ها را يك بيت به سمت راست شيفت مى دهد و از بيت مرتبه پایین صرفه نظر می کند. لا نکقه : ‎old gal‏ های شبفت 8 بیتی » سابقه استفاده: از حافظه را برای آخرین هشت دورهارَجاتی نگهداری می کند . در هشت دوره زمانی اخیر مورد استقتاتهقرار نگرفته 0 -< ثبات شیفت ذر هشت. ذوره زمانی یکبار مورد استفاده قرار گرفثه 2-2-1 ثبات شیفت 

صفحه 63:
Gevow!) cus 9 yrog? ‏الگوریتم‎ 2-5-4-0 (Chee اساس الگوریتم دومین فرصت الگوریتم ۲۹۵ است. وقتی صفحه ای انتخاب شد , بیت ارجاع آن را بررسی می کنیم. ۲ اگر 0 باشد : آترا جایگزین می کنیم. ۲ اگر 1 باشد : فرصت دیگری به آن صفحه می دهیم و صفحه ی بعدی را به ترتیب 1۴0 انتخاب می کنیم. وقتی صفحه ای فرصت دوباره پیدا می کند بیت ارجاع آن 0 می شود و زمان فعلی آن به عنوان زمان ورود آن محسوب می شود. 

صفحه 64:
پیاده سازی الگوریتم دومین فرصت با صف حلقوی : در لنن.صق یک اشارم كر تصن میا کتد اگم چه صفحه ای بايد جایگزین شود. وقتی نیاز به قابی باشد , اشاره گر حرکت می کند تا صفحه ای را بیابد که بیت ارچاع آن 0 باشد. ‎OF‏ وقتی اشاره گر حرکت می کند » بیت ارجاع را 0 می کند. لأ وقتی صفحه ای برای جایگزینی انتخاب شد , آن صفحه از صف خارج می گردد و صفحه ی جدید به جای آن در صف حلقوی قرار ‎tint 

صفحه 65:
ل بيت هاى ارجاع 

صفحه 66:
3-5-4-0 الگوریتم دومین فرصت پیشرفته برای جایگزینی صفحه برای توسعه الگوریتم دومین فرصت از بیت ارجاع و بیت اصلاح ( بخش 1622 ) به صورت یک جفت استفاده می شود که با اين دو بیت چهار حالت زیر امکان پذیر است : 1. )0,0( نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است و تغيير نكرده است. بهترين صفحه براى جايكزينى است. 2 درک نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است ولى تغيير كرده است. صفحه ى.مناسبى براى جايكزينى نيست زیرا یگ از جايكزينى نياز به نوشتن است. ‎aS 2B) no‏ صفحه | ‎1١‏ داستفا 

صفحه 67:
أفظه مجازی 6-4-0 الكوريتم هاى جايكزينى شمارشى © الكوريتم (-0 بفصدص” اسدر) 0©ا : در الكوريتم جايكزينى کمترین کاربرد , صفحه اى كه كمترين ارجاع به آن شده است براى جايكزينى انتخاب مى شود. - علت این انتخاب این است که تصور می شود صفحه ای که ارجاع کمتری به آن صورت می گیرد , کاربرد زیادی ندارد. © الگوریتم 0 هجو 0) 060۵ : در الگوریتم جایگزینی بیشترین کاربرد , صفحه ای که ارجاع بیشتری به آن صورت گرفت , به عنوان صفحه ی جایگزین انتخاب می شود. * اینطور استدلال می شود که صفحه ای که کمتر به کار گرفته 

صفحه 68:
7-4-0 الگوریتم میانگیری صفحه سیستم ها معمولا انباری (۷) از قاب های آزاد را نگه می دارند . وقتی خطای صفحه رخ دهد. همانند الگوریتم های قبلی» صفحه ای برای جایگزینی انتخاب می شود (صفحه قرباتی) اما در انتجا قبل از ایتکه صفحه قرباتی به خارج از حافظه بزود:: صفحه ی مطلوب به قاب آزاد خوانده می شود. بدین ترتیب بدون ايینکه فرآیند منتظر بماند تا صفحه ی قربانی از حافظه خارج شود , می تواند اجرای خودش را از سر گیرد. پس ازآنکه صفحه قریانی از حافظه خارج شد , قاب آن به انبار قاب های آزاد 

صفحه 69:
7-4-0 الگوریتم میانگیری صفحه ( ادامه... ) شکل دیگری از این الگوریتم : انباری از قاب های آزاد نگهداری شود و مشخص گردد که در هر قاب چه صفحاتی وجود دارد. چون محتویات قاب , هنگام نوشتن آن ‎Soy‏ دیسک تغییر نمی کند , صفحه قدیمی مستقیما می تواند از انبار قاب آزاد مورد استفاده قرار گیرد. | در این حالت نیاز به 10 نیست. لا وقتی خطای صفحه رخ دهد , ابتدا بررسی می کنیم که آیا صفحه مطلوب در انبار قاب آزاد وجود دارد یا خیر. اگر نبود » بايد قاب 

صفحه 70:


صفحه 71:
5-0 تخصیص قاب ها راهبرد اصلی ‎sl»‏ تخصیص حافظه به فرآیندهای مختلف , بدین صورت است که هر قاب آزادی به فرآیند کاربر تخصیص می ‎aul‏ ‏وقتی صفحه بندی درخواستی با چند برنامه ای ترکیب می شود , مسئله دیگری بوجود می آید. چندبرنامه ای در هر زمان دو یا چند فرآیند را در حافظه قرار می دهد. در راهبرد تخصیص قاب ها محدودیت های گوناگونی وجود دارد. !| نمی توان بیش از تعداد قاب های موجود را تخصیص دهیم مگر ۲ اد دسا صفحه امکان پذیر باشد. 

صفحه 72:
| می توان حداقل قاب های قابل تخصیص را نیز مشخص کرد که با کاهش تعداد قاب های تخصیصی به هر فرآیند , نرخ خطای صفحه افزایش می یابد. | حداقل تعداد قاب ها توسط معماری مجموعه دستورات تعریف 358 ae لا فنکته : اگر قبل از اجرای کامل یک دستور خطای صفحه رخ دهد , آن دستور باید از اول اجرا شود. در نتيجه بايد قاب های کافی برای نگهداری تمام صفحاتی که توسط یک دستور به آنها 

صفحه 73:
0424 الگوریتم های تخصیص "ساده ترین روش تخصیص] قاب به ‏ فرآیند است که به هر کدام ۲0/0 قاب داده می شود .که با این الگوی تخصیص ‎٠‏ تخصیص مساوی (611010 ۵۱۱۵ ۲0۵۱ا(0]) می گویند. *روش دیگر تخصیص قاب ها این است که تشخیص دلده شود هر فرآیند چه میزان از حافظه نیاز دارد يعنى حافظه بر حسب اندازه فایل ها به آنها تخصیص می یابد . حافظه مورد نياز فرليند 61 -51 ‎S=Ssi‏ ‏اگر تعداد قاب ها ی موجود را 80 در نظر بكيريم » 21 قاب را به فرآيند 6 تخصيص می دهیم که : ai=Si/s*m 

صفحه 74:
6-0-0 تخصیص محلی و عمومی الگوریتم های جایگزینی صفحه را می توان به در دسته تقسیم کرد : ‎iin‏ عمومی ‎٩‏ جایگزینی محلی ‏جایگزینی عمومی : فرآیند می تواند قاب جایگزینی را از مجموعة تمام قاب ها انتخاب كند .حتى اگر آن قاب به فرلیندی تخصیص داده شده باشد . ‏<< در جایگزینی عمومی » یک فریند ممکن است فقط قاب های تخصیص یافتهبهسایر فرآیند ها را انتخاب کند و در نتیجه به تعداد قاب های خودش بیفزاید . 

صفحه 75:
جایگزینی محلی : هر .فرایندی می تواند قاب هایی را انتخاب کند که به آن تخصیص یافته است . . ‏در جایگزینی محلی » تعداد قاب هايى كه به فرآيند تخصيص يافته است تغيير نمى كند‎ AGP ‎as]‏ : مشكل الكوريتم جايكزينى عمومى اين است كه فرآيندى نمى تواند نرخ خطاى صفحه خود را کنترل کند . 

صفحه 76:


صفحه 77:
)۲۳۲۵5:۳۴9( ‏کریییگی‎ ٩-0 5-8 می تولن فرآیند هایی را در نظر گرفت که قاب های کافی ندارند و اگر فرآندی فاقد قاب های تعداد قاب مورد نیاز باشد به زودی دچار خطا می شود که می بایست در چنین وضعیتی » صفحه ای را جایگزین کند ‏ حال اگر تمام صفحات در حال استفاده باشد » مى بایست صفحه ای را جایگزین کند که بلافاصله به آن نیاز می شود . 8 در نتیجه به زودی دچار خطای صفحه می شود واین ادامه می يابد . اين صفحه بندبى زياد را كوبيدكى يا عدم تعادل كويند . 

صفحه 78:
افظه مجازی 6-0 علت کوبیدگی یا عدم تعادل زمتنبند (۳۱) کاهش بهره وری [ا۳) را می بیند و درجه چند برنامه ای را افزایش می دهد (فرآیند های جدید را جایگزین می کند ‎ )‏ اين فرآيند سعی می کند با دریافت صفحاتی از فرآیند های در حال اجرا ‏ شروع به اجرا نماید و منجر به خطای صفحه بیشتری می شود و صف انتظار برای دستگاه طولانی می شود . در نتیجه بهره وری لا ۳-بیشتر کاهش می یابد و زمانبد (۳۸ سعی می کند درجة چند برنامه ای را هنوز هم بیشتر کند .بدين ترتیب کوبیدگی یا عدم تعادل بوجود می آید وتوان عملیاتی سیستم کاهش می یابد . 

صفحه 79:
i 3 بهره وری لا درجه چند برنامه ای 5 اثر كوبيدكى يا عدم تعادل با استفاده لز الكوريتم جايكزينى محلى محدود می شود .چنانچه فرآیندی در جایگزینی محلی دچار کوبیدگی شود » نمی تواند قاب ها را از فرآیندهای دیگر بگیرد و منجر به کوبیدگی شود . 

صفحه 80:
6 برای جلوگیری از کوبیدگی » بايد تمام قاب هاى مورد نياز فرآيند تامينكردد که برای تعیین اینکه یک فرآیند به چند قاب نیاز دارد از راهبرد مجموعه کاری استفاده می شود . این روش ۰ مدل محلی اجرای فرآیند را تعریف می کند . مدل محلی : بیان می کند که وقتي فرآیندی در حال اجراست از یک محیط محلی به محیط محلی دیگر می رود (منظور از محل » مجموعه لی از صفحات است که به طور فعال با یکدیگر مورد استفاده قرار می گیرند ) 

صفحه 81:
‎(Dorr Gets) GIS 46 sane Js (0-0-2‏ اين مدل از مرن برلى تعريف ينجره مجموعه كارى استفاده می کند . ‏أ یو هه اتن اذ متقسفة هد القور: ترازو ار #اأاكر صفحه اى در حال استفاده باشد ؛ در مجموعه كارى قرار دارد و اكر ديكر مورد استفاده قرار ‏نكيرد » از مجموعة كارى حذف مى كردد .بنا براين مجموعة كارى تقريبى از محل برنامه است . جدول ارجاع صفحه ‎26157777 516234123444343444132 3444344 4... ‎ ‎ ‎ ‎ ‏هم ‎ti 12‏ ‎WS( ti) ={1,2,5,6,7 }WS( tz) ={3,4}‏ 

صفحه 82:
افظه مجازی بهترین ویژگی مجموعه کاری اندازه ی آن است . اگر اندازه مجموعه کاری بعنی ۷۷55 را برای هر فرآیند موجود در سیستم محاسبه کنیم » داریم : ‎D= swssi‏ كزقابهاودرخولستى ‏[]هر فرآیند از صفحات موجود در مجموعه ی کاری خود به طور فعال استفاده می کند ؛بنبراین هر فرآیند ة به ۷/۷551 قاب نیاز دارد . ‎ ‏گر ۷1] < 20(]2 تعدادقاب های موجود ) : کوبیدگی بوجود می آید. 

صفحه 83:
)۳۳۳۴( ‏فراوانی خطای صفحه‎ ٩0-0 راهبرد فراوانی خطای صفحه نسبت به مدل مجموعه کاری » روش مناسبتری است . در اين روش کران بالا و پایین برای نرخ خطای صفحه در نظر گرفته می شود . اگر ترخ خطای صفحه > کران بالای نرخ خطا : قب دیگری را به فرآيند مورد نظر تخصیص می دهیم . اگر نرخ خطای صفحه < کران پایین نرخ خطا : قابی را از آن فرآیند پس می گیریم . بنابراین می توانیم خطای صفحه را اندازه گیری وکنترل کنیم تا از کوبیدگی جلوگیری به عمل آید . 

صفحه 84:


صفحه 85:


صفحه 86:
۳-0 مثال هایی از سیستم عامل در اینجا چگونگی پیاده سازی حافظه مجازی در ویندوز 81۲ و سولاریس 0 شرح دلده می شود . ‎NT jis 1-7-0‏ ویندوز ۱۷۲ حافظه مجازی را با استفاده از صفحه بندی درخواستی به همراه خوشه بندی ‎oly (Clustering)‏ سازى مى كند . خوشه بندى » خطا های صفحه را به این صورت حل می کند که نه تنها صفحات مولد خطا را به حافظه می آورد » بلکه صفحاتی را که در اطراف این صفحه ‏قرار دارند » به حافظه می آورد . 

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

صفحه 88:
0-7-0 سولارین © وقتی بندی منجر به خطای صفحه می شود ۰ هسته صفحه ای را از لیست صفحات آزاد آن » به آن بند تخصیص می دهد . بنابراین لازم است هسته میزان کافی از حافظه آزار را در اختیار داشته باشد . همراه اين ليست از صفحات آزاد پارامتری به نام 1058۴۲66 وجود دارد که کوبیدگی را نشان مى دهد که باید صفحه بندی شوند . [آاگر تعداد صفحات آزاد کمتر از 105۴۴۳۵6 باشد ء فرآیند را فرآیند ۳۵6000۴ می نامند . فرآیند ‎Pageout‏ همانند الگوریتم دومین فرصت است . ‎Ls Pageout pix Sul)‏ کنترل نرخ پویش صفحات از چندین پارامتر استفاده می کند . نرخ پیمایش بر حسب صفحات در ثانیه بیان می شود و در بازه 510/56210 تا ۴۵55۵1 است , 

صفحه 89:
Fastscan 0 100 1 Slowscan minfree desfree lostfree میزان حافظه آزاد 

صفحه 90:
ور کلی ae سسست ‎sd‏ ‎=e‏ ‏تیه ‎bine‏ ‎so‏ 

صفحه 91:
0-0 سایر ملاحظات 0-0 پیش صفحه بندی (۳۲۵۵۵91۳9) یکی از ویژگی های بارز سیستم صفحه بندی درخواستس این است که وقتی شروع به کار می کند » تعداد زیادی از خطای صفحه بوجود مى آيد .اين وضعیت ناشی از تلاش برای انتقل محل اولیه به حافظه است .همین وضعیت در زمان های دیگر نیز ممکن است پیش بیاید . الابيش صفحه بندی سعی می کند از این صفحه بندی زیاد جلوگیری به عمل آورد .در اين راهبرد تمام صفحات مورد نیاز فرآیند به طور یکجا در همان اول به حافظه آورده می شوند . 

صفحه 92:
‎٩-0-0‏ اندازه صفحه یکی از مواردی که برای تعیین اندازه صفحه می بایست در نظر گرفت » اندازه صفحه جدول است . ‏7 برای یک مقدار معین از فضای حافظه مجازی »کاهش اندازه صفحه ء به تعداد صفحات و اندازه ی ‏جدول صفحه می افزاید . از طرف دیگرهرچه صفحه کوچکتر باشد » بهره وری بیشتر است . ‏"هرچه صفحه کوچکتر باشد » کل زمان 1/0 نیز کمتر است . ‎asl]‏ : بعضی از عوامل مثل تکه تکه شدن داخلی و محلی بودن » به صفحات کوچک تمایل دارند .در حالیکه عوامل دیگری مثل اندازه جدول و زمان 1/0 بر صفحات بزرگتر تاکید دارند . 

صفحه 93:
TLB ‏رسش‎ 900 رسش ۲1.8 میزان حافظه است که از ۲1-8 قابل دستیایی است ویرابر است با : تعداد ورودی های ۲1.8" * اندازه صفحه در حالت ايده آل » مجموعه كارى مربوط به يك فرآیند در 71-8 ذخیره مى شود .در غير اينصورت » فرآيند وقت زيادى را صرف برطرف كردن ارجاعات حافظه در جدول صفحه (به جاى ‎ct (TLB‏ کند . 7اگر ورودی های ۳18 را دو برابر کنیم ؛ رسش718 دو برابر مى شود . آرهیافت دیگری برای افزایش رسش ۲1.8 » افزودن اندازه صفحه یا ارائه اندازه های گوناگون از صفحه می باشد که پشتیبانی از صفحاتی با اندازه های مختلف مستلزم اين است سیستم عامل ۲18 را ۳ 

صفحه 94:
6-0 جدول صفحه معکوس هدف این شکل از مدیریت حافظه ۰ کاهش میزان حافظه فیزیکی مورد نیاز برای ترجمه آدرس مجازی به فیزیکی است , برای این صرفه جویی جدولی ایجاد می شود که برای هر صفحه ی حافظه ی فیزیکی یک ورودی دارد و این ورودی با جفت< شماره صفحه و شماره فرآیند > مشخص شده است . ادر صفحات معكوس ء با نگهداری اين اطلاعات که کدام صفحه مجازی در کدام قاب فیزیکی ذخیره شده است » میزان حافظه ی فیزیکی مورد نیاز برای نخیره ی این اطلاعات » کاهش یافته است . . ‏فاقد اطلاعات کامل راجع به فضای آدرس منطقی فرآیند است‎ سوکعم‎ dain J pte LAD] 

صفحه 95:
9-0-0 ساختار برنامه صفحه بندی درخواستی از دید کاربر شفاف و روشن اس . در بسیاری از موارد کاربر از ماهیت صفحه بندی حافظه خبر ندارد . در موارد دیگر » کارآیی سیستم با آگاهی از صفحه بندی درخواستی بهبود می یابد . 6 انتخاب دقیق ساختمان داده ها و ساختار های برنامه نویسی می تواند محلی بودن مراجعات را افزایش دهد و نرخ خطای صفحه و تعداد صفحات موجود در مجموعة کاری کاهش دهد . 

صفحه 96:
؟أکامپایلر و بار کننده عامل دیگری در صفحه بندی اند . تفکیک کد و داده و تولید کد چند دخولی به معنای این است که صفحات کد می توانند فقط خواندنی با شند . لذا لازم نیست صفحه ای که تغییر نکرده است جایگزین شود . آبار کننده . هر روال را کاملا در یک صفحه قرار می دهد و در نتیجه صفحات در مرز صفحات قرار نمی گیرند . روال هایی که همدیگر را چندین بار فراخوانی می کنند در یک صفحه قرار می گیرند . اگذآزبان برنامه سازی نیز می تواند در صفحه بندی موثر باشد . 

صفحه 97:
9-0-0 قنل شدن وقتی از صفحه بندی درخواستی استفاده می گردد » نیاز به این است که بعضی از صفحات در حافظه قفل شوند . یکی از اين وضعیت ها وقتی رخ می دهد كه عمل 1/0 از حافظه مجازی کاربر و یا در آن صورت گیرد . ۱/0 معمولا توسط پردازنده 1/0 صورت می گیرد . به عنوان مثال تعداد بایت هایی که بايد انتقال یابد و آدرس حافظه میانگیر » به کنترل کننده نوار دلده می شود. وقتی عمل انتقال کامل شد ۰ وقفه ای به ۲۳10 ارسال مى شود . 

صفحه 98:
تلا لاه > مبانگ گرداننده دیسک عر 

صفحه 99:
باید مطمئن شویم که فرآیندی درخواست 1/0 نمی کند تا مجبور شود در صف سستگاه 1/0 قرار كيرد .جراكه به هر حال ل51© به اين فرآيند ها تخصیصی می یابد و این فرآیند ها موجب خطای صفحه می شوند . دوراه حل برای حل این مسئله وجود دارد : "هیچ عمل 1/0 در حافظه صورت نگیرد » بلکه داده ها هميشه بین حافظه ی سیستم و حافظه ی کاربر کپی شوند . *برای نوشتن بلوکی بروی صفحه » ابتدا آن را در حافظه سیستم کپی می کنیم و سپس آنرا بروی نوار می نویسیم .این عمل کپی ممکن است سربار نا معقولی را ایجاد کند . آراه حل ديكر اين است که صفحات در حافظه قنل شوند : به هر قاب يك بيت قفل نسبت داده می شود و اگر قابی ققل باشد »نمی تواند برای جایگزینی انتخاب گردد . *در اين روش ۰ برای نوشتن بلوکی بروی نوار ؛ صفحاتی را که حاوی آن بلوک هستند در حافظه قفل می کنیم . 

صفحه 100:
۳-0 پردازش بی درنگ يك فرآيند يا بند بى درنك انتظار دارد که با کمترین تاخیر لا ۲ را در اختيار كيرد و اجرا شود . حافظه مجازی میتواند تاخیر های زیا دی را برای این فرآیند اجاد نماید (هنگام انتقال صفحات به حافظه ) .بدین ترتیب » سیستم های بی درنگ فاقد حافظة مجازی اند . 

:استاد آقای عسکری ‏میالد قاسمپوری اعضای جعفری گروه : ‏ ‏آذین رضا زاهدی مهرپورشاد خالصه ی فصل 9 1 تعداد کل اسالید صل دهم 10 0 حافظه مجاز 2 فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 3 فصل دهم :حافظه مجازی حافظه ی مجازی تکنیکی است که موجب می شEEود فرآینEEد بEEدون اینکه کامال در حافظه باشد اجرا گEEردد .امتیEEاز عمEEده این الگEEو این اسEEت کEEه ممکن اسEEت برنامEEه هEEا بزرگEEتر از حافظEEه ی فیزیکی باشند. 1-10مرور کلی برای قرار گرفتن دستورات در حال اجرا در حافظه یک روش این است که کل فضای آدرس منطقی در حافظه ی فیزیکی قEEرار گEEیرد امEEا این روش مEEوجب می شEEود کEEه انEEدازه ی برنامEEه بEEه اندازه ی حافظه ی فیزیکی محدود شود. 4 فصل دهم :حافظه مجازی در موارد زیر ،اغلب نیاز به کل برنامه نیست : • برنامه ها اغلب برای پردازش خطای نEEادر نوشEEته می شEEوند کEEه اغلب اجرا نمی شوند ( به دلیل ندرت رخداد خطا ) • به آرایه ها ،لیست ها و جداول ،حافظه ای بیش از اندازه مورد نیاز تخصیص می یابد • بعضی ویژگی ها و گزینه های برنامه ممکن است به ندرت مورد استفاده قرار گیرند. توانایی اجرا برنامه ای کEEه فقEEط بخشEEی از آن در حافظEEه قرار گیرد فواید زیادی دارد : اندازه ی برنامه به فضای فیزیکی محدود نمی شود 5 چون هر برنامه کاربر می تواند فضای فیزیکی کمتری را اشEEغال حافظه مجازی بیش از حافظه استمجازی حافظه : دهم فصل فیزیکی صفحه 0 صفحه 1 صفحه 2 2 . . . 3 4 نگاشت حافظه 6 حافظه فیزیکی حافظه منطقی فصل دهم :حافظه مجازی ‏تذکر : .Iحافظه ی مجEEازی معمEEوال توسEEط صEEفحه بنEEدی درخواسEEتی پیاده سازی می شود. .IIحافظه مجازی در سیستم قطعه بندی نیز قابل پیاده سEEازی است. .IIIبEEEرای پیEEEاده سEEEازی حافظEEEه ی مجEEEازی از قطعEEEه بنEEEدی درخواستی نیز می توان استفاده کرد. 7 فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 8 مفاهیم اساسی کارآیی صفحه بندی درخواستی فصل دهم :حافظه مجازی 2-10صفحه بندی درخواستی یک سیستم صفحه بندی درخواسEEتی مشEEابه سیسEEتم صEEفحه بنEEدی بEEه همراه مبادله است. فرآیند ها در حافظه ی ثانویه ( معموال دیسک ) ذخیره می شوند. برای اجرای فرآیند آن را به حافظه می آوریم. اجرای انتقال کامل فرآیند به حافظه ،از مبادله کننEEده تنبEEل ( Lazy ) SwapperاسEEتفاده می شEEود کEEه این مبادلEEه تEEا زمانیکEEه فرآینEEدی مورد نیاز نباشد آن را به حافظه نمی آورد. در تکنیک صفحه بنEEدی بEEه جEEای اصEEطالح مبادلEEه کننEEده از اصEEطالح 9 صفحه بند استفاده می کنیم. انتقال حافظه صفحه بندی شده به مجازی حافظه دهم : فصل دیسک همجوار فضای 1 10 3 2 1 0مبادله به خارج 2برنامۀ ‏A 7 6 5 4 11 10 9 8 3 15 14 13 12 23 2 2 21 2 0 مبادله به داخل 4برنامۀ ‏B فصل دهم :حافظه مجازی 1-2-10مفاهیم اساسی وقتی فرآیندی باید به حافظه مبادلEEه شEEود ،صEEفحه بنEEد حEEدث می زند که قبل از این که فرآیند از حافظه خارج شود چه صفحه ای مورد استفاده قرار خواهد گEEرفت بنEEابراین بEEه جEEای اینکEEه کEEل فرآیند را بEEه حافظEEه بیEEاورد فقEEط صEEفحات مEEورد نیEEاز را وارد حافظه می کند. در این اگو نیاز به پشتیبانی سخت افEEزار داریم تEا بین صEEفحات موجEEود در حافظEEه و صEEفحات موجEEود در دیسEEک تفکیEEک قائEEل شویم کEEه بEEرای این منظEEور الگEEوی بیت اعتبEEار مEEورد اسEEتفاده قرار می گیرد. 11 جدول صفحه وقتی که صفحاتی در نیستند حافظه :اصلی مجازی حافظه فصل دهم 0 1 2بیت اعتبار قاب 1 3 ‏A ‏C ‏B ‏A ‏E ‏D ‏C ‏F ‏F 4 ‏V 5 ‏i 6 ‏V 7 ‏i 3 8 ‏i 9 34 ‏E ‏V 5 ‏F 5 ‏i 6 ‏G 6 ‏i 7 ‏H 7 10 11 12 13 14 15 12 حافظه فیزیکی 4 6 9 جدول صفحه 0 ‏A 0 1 ‏B 1 2 ‏C 2 ‏D 3 4 حافظه منطقی فصل دهم :حافظه مجازی اگر فرآیندی سعی کند از صفحه ای استفاده کند کEEه در حافظه نیست : دسEEتیابی بEEه صEEفحه ای کEEه بEEه صEEورت صEEفحه ای نEEامعتبر عالمت گذاری شده است ،منجر به تله ی خطاهای صEEفحه ()Page Fault می شود. سخت افزار صفحه بندی برای ترجمه آدرس از طریق جدول صفحه ،متوجه می شEEود کEEه بیت نEEا معتEEبر یEEک اسEEت و تلEEه ای را بEEه 13 سیستم عامل می فرستد و منجربه وقفه می شود. صفحه خطای پردازش مجازی حافظه مراحل دهم : فصل صفحه در حافظه 3 پشتیبان 1 سیستم عامل تله 2جدول صفحه 2 مراجعه 1 ‏i 4 صفحه مفقود 14 قاب آزاد 5 تنظیم مجدد جدول صفحه 6 3 دستور 4 اجرای دوباره بار کردن M فصل دهم :حافظه مجازی روش مقابله با این نوع خطای صفحه : .Iجدول مربوط به این فرآیند را که معموال در PCBفرآیند ذخیره می شود ،بررسی می شود تا مشخص شود آیا مراحعه معتبر بوده یا خیر .IIاگر ارجاع نا معتبر بود فرآیند را خاتمه می دهیم و اگر معتبر بود وب به حافظه نیامده بود آن را به حافظه می آوریم .IIIیک قاب آزاد را می یابیم .IVیک عملیات دیسک را زمانبندی می کنیم تا صفحه مورد نظر را به قابی که االن تخصیص یافته است بخوانیم .Vوقتی خواندن از دیسک آغاز شد ،جدول صفحه و جدول داخلی را همراه فرآیند نگهداری شده است اصالح می کنیم تا بیانگر این باشد که آن صفحه فعال در حافظه نیست .VI15دستوری را که توسط آدرس نامعتبر دچار وقفه شده است ،از فصل دهم :حافظه مجازی نکته : برنامه ها تمایل به ارجاع محلی دارند که منجربه کارآیی معقولی در صفحه بندی درخواستی می شود ( اینطور نیست که برنامه ها به چندین صفحه جدید دستیابی داشته باشند و دچار چندین خطای صفحه شوند ) سخت افزار پشتیبان صفحه بندی درخواستی ،همانند سخت افزار صفحه بندی و مبادله است : جدول صفحه :این جدول از طریق بیت اعتبار یا بیت های حافظه می تواند ورودیی را به عنوان ورودی نامعتبر عالمت گذاری کند. 16 فصل دهم :حافظه مجازی نکته : عالوه بر پشتیبانی سخت افزاری نیاز به نEEرم افEEزار قابEEل مالحظه ای نیز می باشد. از سر گیری اجرای یEEک دسEEتور در صEEورت خطEEای صفحه : .1اگر خطای صفحه هنگام مکش ( )Fetchدستور رخ دهد ،می توانیم آن دستور را دوباره مکش کنیم. .2اگر هنگام مکش یک عملوند خطای صEEفحه رخ دهEEد ، 17 باید دستور را دوبEEاره مکش کEEنیم ،آنEEرا رمزگشEEایی فصل دهم :حافظه مجازی 2-2-10کارآیی صفحه بندی درخواستی صفحه بندی درخواستی تٲ ثیر به سزایی در کارآیی سیستم کامپیوتری دارد .برای پی بردن به این موضوع زمان دستیابی موثر را برای صفحه بندی مجازی محاسبه می کنیم. دستیابی زمان اگر خطای ( زمان دستیابی موثر = زمان دستیابی به حافظه : به حافظه صفحه به وجود نیاید ) احتمال بروز صفحه خطای دستیابی موثر زمان زمان خطای موثر * )= P + ma * (1-P برای محاسبه ی زمان دستیابی موثر ،باید بدانیم که برای ارائه خدمات به خطای صفحه ،چقدر زمان نیاز است 18 فصل دهم :حافظه مجازی خطای صفحه موجب می شود تا اعمEEال زیEEر صEEورت گیرد: .1ارسال تله به سیستم. .2ذخیره ثبات های کاربر و حالت فرآیند. .3تعیین اینکه وقفه ناشی از خطای صفحه بود. .4کنترل شود که اجرا به صفحه معتبر بود یا خEEیر و تعEEیین محEEل صفحه دیسک. .5خواندن از دیسک و انتقال به یک قاب آزاد. الف – انتظار در صف آن دستگاه تا ارائه خدمت ب – انتظار برای پیگرد دستگاه و یا زمان تٲخیر 19 ج – شروع انتقال صفحه به قاب آزاد فصل دهم :حافظه مجازی .6در زمان انتظار برای دیسک CPU ،به کار دیگری تخصیص می یابد (زمانبندی .)CPU .7وقفه ای از دیسک ( کامل شدن عمل I/Oدیسک ). .8ذخیره ی ثبات ها و حالت فرآیند برای کاربر دیگر ( اگر مرحله 6 انجام شده باشد ). .9تعیین اینکه وقفه از دیسک بوده است. .10تصحیح جدول صفحه و سایر جدول ها تا نشان داده شود که صفحه مطلوب فعال در حافظه است. .11 20 .12 انتظار برای تخصیص مجدد CPUبه این فرآیند. بازیابی ثبات های کاربر ،حالت فرآیند و جدول صفحه جدید و فصل دهم :حافظه مجازی تEEذکر :ممکن اسEEت تمEEام این مراحEEل در هEEر مEEورد الزامب باشند. در هر مEEورد ،خطEEای صEEفحه شEEامل سEEه زمEEان اسEEت کEEه ناشی از سه عمل می باشد: می توانند با کد نویسی دقیق به چند .1ارائه خدمات به وقفه خطای صفحهدستور کاهش صد یابد .2خواندن صفحه به حافظه .3اجرای دوباره ی فرآیند نکته :فرآیند هایی که منجربه خطای صفحه شده انEEد ، 21 فصل دهم :حافظه مجازی سیستم های با فضEEای مبادلEEه محEEدود ،بEEرای فایEEل هEEای باینری از الگوی زیر استفاده می کنند: .Iصفحاتی که در فایEEل هEEای بEEاینری درخواسEEت می شوند مستقیما از سیستم فایل آورده می شوند. • وقEEتی آن صEEفحات بایEEد جEEایگزین شEEوند ،صEEفحات جدیEEد بروی آنها نوشEEته می شEEوند و در صEEورت لEEزوم ،دوبEEاره باید از سیستم فایل خوانده شوند. .IIصفحات از همان اوالز همان اول از سیسEEتم فایEEل درخواست شEEوند ولی هنگEEام جEEایگزینی در فضEEای مبادله نوشته شوند. 22 • این روش تضمین می کند که فقط صفحات مEEورد نیEEاز از سیستم فایل خوانده شود ولی تمام صفحه بند های بعدی فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 23 کپی و نوشتن فایل های نگاشت حافظه فصل دهم :حافظه مجازی 3-10ایجاد فرآیند در بخش 10-2توضEEیح دادیم کEEه فرآینEEد چگونEEه بEEا صEEفحه بنEEدی درخواستی شروع کند .با اسEEتفاده از این تکنیEEک ،فرآینEEد فقEEط بوسیله ی صفحه بندی درخواستی در صفحه ای کEEه حEEاوی اولین دسEEتور اسEEت ،آغEEاز می شEEود .امEEا ،صEEفحه بنEEدی و حافظEEه ی مجازی در اثنای ایجاد فرآیند ،فواید دیگری نیز دارند . در اینجEEا در تکنیEEک کEEه توسEEط حافظEEه مجEEازی فEEراهم می شEEود و کارآیی ایجاد و اجرا فرآیند را بهبEEود می بخشEEد ،شEEرح داده می شود. 24 فصل دهم :حافظه مجازی 1-3-10کپی و نوشتن صفحه بندی درخواستی هنگEEام خوانEEدن فایEEل از دیسEEک بEEه حافظEEه مEEورد اسEEتفاده قEEرار می کEEیرد و این فایEEل ممکن اسEEت حEEاوی دودویی قابEEل اجEEرا باشEEد ،امEEا ایجEEاد فرآینEEد بEEا اسEEتفاده از فراخوان سیستم ، )(forkمی تواند با استفاده از تکنیکی مشEEابه با اشتراک صفحه ،نیاز به صEEفحه بنEEدی درخواسEEتی را برطEEرف کند. این تکنیEEک سEEرعت ایجEEاد فرآینEEد را افEEزایش می دهEEد و تعEEداد صفحاتی را که هنگام ایجاد فرآیند جدید بایEEد بوجEEود آینEEد را بEEه حداقل می رساند.  25فرخوان سیستم )(forkیک فرآیند فرزند را از پEEدر آن ایجEEاد می فصل دهم :حافظه مجازی تذکر : بEEا توجEEه بEEه این کEEه فرآینEEد هEEای فرزنEEد ایجEEاد شEEدند ، فراخوان سیستم )(execرا فراخوانی می کنند ،کپی کردن فضای آدرس پدر ممکن است ضروری نباشد. از طرف دیگر ،می توانیم از تکنیکی به نام کEEپی و نوشEEتن (Copy )& Writeاستفاده کنیم. روش کپی و نوشتن :در این روش ،فرآیندهای پEEدر و فرزنEEد از همان آغاز ،از صفحات یکسانی استفاده می کنند. این صEEفحات مشEEترک بEEه عنEEوان صEEفحات کEEپی و نوشEEتن عالمت 26 گذاری می شوند یعنی اگEEر یکی از این فرآینEEدها بEEروی صEEفحه ی فصل دهم :حافظه مجازی تذکر : تکنیک کپی و نوشتن ،هنگام تکثیر فرآیند در سیستم های عاملی مثل ویندوز ، 2000لینوکس و سEEوالریس 2مEEورد اسEEتفاده قرار می گیرد. تعیین فضای ایجاد صفحه خالی پس از تعیین اینکEEه صEEفحه ای بایEEد بEEا استفاده از کپی و نوشتن تکثیرشود: بسیاری از سیستم عامل های مخزنی ( )Poolاز صفحات آزاد بEEرای این درخواست ها فراهم می کنند. این صفحات آزاد وقتی تخصیص می یابند که پشته یEEا هEEرم مربEEوط به فرآیند باید بسEEط یابEEد یEEا صEEفحات کEEپی و نوشEEتن بایEEد مEEدیریت 27 شوند. فصل دهم :حافظه مجازی نکته : سیستم های عامل این صفحات را با تکنیکی به نام پر کردن با صفر در هنگامه تقاضا ( )zero – fill – on – demandتخصیص می دهند. تکنیک پر کردن با صفر در هنگام تقاضا :در این تکنیک صفحات درخواستی قبل از تخصیص با صفر پر می شوند و در نتیجه محتویات قبلی آن از بین می روند. نکته : 28 در تکنیک کپی و نوشتن ،صفحه ای که می خواهد کپی شود ،در صفحه ای که با صفر پر شده است کپی می گردد. فصل دهم :حافظه مجازی 2-3-10فایل های نگاشت حافظه نگاشت حافظه فایل تکنیکی است که با تکنیک حافظEEه ی مجEEازی ،بEEا I/Oفایل به عنوان روال دستیابی به حافظه استفاده می کنند. ‏ رهیEEافت نگاشEEت حافظEEه فایEEل اجEEازه می دهEEد بخشEEی از فضEEای آدرس مجازی به طور منطقی به فایل مربوط شوند. 29 فصل دهم :حافظه مجازی نکات : .1برای نگاشEEت حافظEEه ی یEEک فایEEل بلEEوک دیسEEک بEEه صEEفحه ( صفحاتی ) در حافظه نگاشته می شود. .2دستیابی اولیه بEEه فایEEل از طریEEق صEEفحه بنEEدی درخواسEEتی عادی انجام می شود و منجر به خطای صEEفحه می گEEردد امEEا بخشی از فایل که به اندازه ی صفحه است ،از سیستم فایل به صفحه ی فیزیکی خوانده می شود. .3خواندن و نوشتن های بعEEدی در فایEEل بEEه صEEورت روال هEEای دسEEتیابی بEEه حافظEEه اداره می شEEوند .بEEدین تEEرتیب ،چEEون دستکاری فایل ها به جای فرخوان سیسEEتم )(readو )(writeاز 30 طریق حافظه انجام می گیرد ،دستیابی به فایل و کاربرد آن فصل دهم :حافظه مجازی نکته : عمل نوشتن در فایلی که در حافظه نگاشت شده است ، ممکن است فورا در فایل روی دیسک انجام نشود. بعضی از سیستم های عامل نگاشت حافظه را فقط از طریق فراخوان سیستم خاصی انجام می دهند و با استفاده از فراخوان سیستم استاندارد ،با I/Oفایل برخورد می کند. اما بعضی از سیستم ها صرف نظر از اینکه آیا فایلی به عنوان فایل نگاشت حافظه مشخص شده است یا خیر آن را به صورت نگاشت حافظه در نظر می گیرند. تذکر : ممکن است چند فرآیند بتوانند به یک فایل در حافظه ی مجازی نگاشت شوند تا اشتراک داده به وجود آید. 31 فایلهای حافظه نگاشت مجازی فصل دهم :حافظه 1 2 3 3 1 4 2 6 5 3 6 حافظه مجازی فرآیند B 4 1 5 5 6 4 2 حافظه فیزیکی 6 32 1 5 4 3 2 1فایل دیسک حافظه مجازی فرآیند A فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی طرح اصلی جایگزینی صفحه الگوریتم FIFO اگوریتم بهینه ایجاد فرآیند الگوریتم LRU حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 33 تقریبی از الگوریتم ‏LRU الگوریتم های جایگزینی شمارشی الگوریتم میانگیری صفحه فصل دهم :حافظه مجازی 4-10جایگزینی صفحه در بحث هایی که تا کنون گفته شد نرخ خطای صفحه چندان جدی نبود چرا که هر صفحه حداکثر یک بار ( هنگامیکه اولین بار به آن ارجEEاع می شود ) دچار خطای صفحه می گردید. اگر فرآیند 10صفحه ای فقط نیمی از آنهEEا اسEEتفاده کنEEد صEEفحه بندی درخواستی ،در I/Oمورد نیاز برای 5صEEفحه ی دیگEEر صEEرفه جویی می کند. همچEEEنین می توانسEEEتیم بEEEا اجEEEرای در برابEEEر فرآینEEEدها ،درجEEEه چندبرنامEEه ای را بEEاال بEEبریم ،لEEذا اگEEر 40قEEاب می داشEEتیم می 34 توانستیم 8فرآیند را به جای 4فرآیندی که اجرا شEEدند بEEه هEEر 10 فصل دهم :حافظه مجازی تخصیص اضافی :اگر درجه چندبرنامه ای را بEEاال بEEبریم ،تخصEEیص اضافی حافظه صورت می گیرد. تخصEEیص اضEEافی حافظEEه بEEدین تEEرتیب عمEEل می کند : • در حالیکه فرآیند کEEاربر در حEEال اجراسEEت ،خطEEای صEEفحه رخ می دهد. • سEEخت افEEزار تلEEه ای را بEEه سیسEEتم عامEEل می فرسEEتد و سیسEEتم عامل جدول های داخلی خود را بررسEEی می کنEEد تEEا ببینEEد آیEEا این 35 صفحه دچار خطا شده و دستیابی به حافظه معتبر است یا خیر. نیاز به جایگزینی فصل دهم :صفحه حافظه مجازی بیت اعتبار ناظر 0 1 ‏B ‏M ‏V 3 ‏H ‏V 4 ‏V 5 بار کردن ‏M ‏D 2 ‏H 3 بار کردن M 4 ‏J 6 ‏A ‏V 7 ‏i ‏E قاب ‏i جدول صفحه برای کاربر 1 قاب 5بیت اعتبار حافظه فیزیکی 6 ‏M حافظه منطقی برایH کاربر1 B ‏V 2 ‏J ‏V 7 ‏M جدول صفحه برای کاربر 2 36 ‏J حافظه منطقی برای فصل دهم :حافظه مجازی 1-4-10طرح اصلی جایگزینی صفحه جایگذینی صفحه به این صورت عمل می کند : اگر قاب آزادی موجود نباشد قابی را پیدا می کنیم که فعال در حال استفاده نیست و آن را آزاد می کنیم. برای آزاد کردن قاب ،محتویات آن را در فضای مبادله می نویسیم و جدول صفحه ( و سایر جداول ) را تغییر می دهیم ( تا نشان دهیم صفحه فعال در حافظه نیست ) 37 فصل دهم :حافظه مجازی روال خدمات خطای صفحه به صورت زیر تغییر می کند تا جایگذینی صفحه را نیز انجام دهد. .I محلی از دیسک را بیابد که صفحه مطلوب در آنجا قرار دارد. .IIقاب آزاد را بیابد : الف -اگر قاب آزاد وجود دارد از آن استفاده کند. ب -وگرنه با استفاده از الگوریتم جایگزینی صفحه ،یک قاب را برای قربانی کردن انتخاب نماید ( آن قاب را خالی کند) ج -صفحه ی قربانی را بروی دیسک بنویسد و جدول قاب و صفحه را نیز بطور مناسب تغییر دهد. .IIIصفحه مطلوب را به قاب آزاد منتقل کند و جداول صفحه و قاب 38 را تغییر دهد. صفحه جایگزینی فصل دهم :حافظه مجازی 1بیت اعتبار صفحۀ قربانی برای مباله با خارج 1 2 قربان f 3 مبادلۀ صفحۀ مطلوب به حافظه ی تغییر به مقدار 2 نامعتبر3 تنظیم مجدد 4 برای صفحۀ جدید 4 حافظه فیزیکی 39 قاب ‏i 0 ‏V ‏f فصل دهم :حافظه مجازی نکته : اگر قاب خEEالی موجEEود نباشEEد نیEEاز بEEه دو انتقEEال صEEفحه است ( یکی برای خروج از صفحه و دیگری برای ورود بEEه صEEفحه ) بدین ترتیب زمان خدمات خطای صفحه دو برابر می شEEود و زمEEان دستیابی موثر نیز افزایش می یابد. سربار ناشی از عدم وجود قاب خEEالی بEEا اسEEتفاده از بیت اصالح کاهش می یابد : • هر صفحه یEEا قEEاب می توانEEد بیت اصEEالح مخصEEوص بEEه خEEود را در سخت افزار داشته باشد. • 40 هر وقت بایت یEEا کلمEEه ای در صEEفحه نوشEEته شEEود بیت اصEEالح آن فصل دهم :حافظه مجازی • وقتی صفحه ای را برای جایگزینی انتخاب می کEEنیم ،بیت اصEEالح آن را بررسی می کنیم. oاگر برابر با یک باشد :متوجه می شEEویم کEEه هنگEEام خواندن از دیسک تغیEEیر کEEرده اسEEت و در این حEEالت می بایست آن صفحه را بروی دیسک بنویسیم. oاگEEر برابEEر بEEا یEEک نباشEEد :بEEه معنEEای این اسEEت کEEه صفحه هنگام خوانده شدن بEEه حافظEEه تغیEEیر نکEEرده اسEEت بنEEابراین اگEEر کEEپی صEEفحه موجEEود در دیسEEک 41 توسEEط صEEفحات دیگEEر رونویسEEی شEEده باشEEد می فصل دهم :حافظه مجازی نکات : .1این تکنیک به صفحات فقط خواندنی ( مثل صEEفحات کد باینری ) اعمال می شود .2این الگEEو زمEEان ارائEEه خEEدمات بEEه خطEEای صEEفحه را کاهش می دهد ،زیرا در صورتیکه صفحه تغییر نکند ، زمان I/Oبه نصف تغلیل می یابد. تذکر :جایگزینی صفحه اساس کار صفحه بندی درخواستی است ‏ برای پیاده سازی صفحه بندی درخواسEEتی دو مسEEئله را بایEEد حEEل کنیم 42 .I الگوریتم تخصیص قاب بنویسیم فصل دهم :حافظه مجازی اگر چندین فرآیند در حافظه باشند ،بایEEد تصEEمیم بگEEیریم کEEه چنEEد قاب به هر فرآیند تخصیص یابد. عالوه بر این ،در صورت نیاز جایگزینی صفحه ،قEEاب هEEایی را کEEه باید جایگزین شوند انتخاب می کنیم. نکته :با افزایش تعداد قEEاب هEEا ،تعEEداد خطاهEEای صEEفحه بEEه حEEد کمینEEه ای کEEاهش می یابEEد .البتEEه افEEزایش حافظEEه فEEیزیکی نEEیز منجربه افزایش تعداد قاب ها می شود. 43 نمودار خطای صفحه بر حسب تعداد حافظه مجازی : دهم فصل قاب ها 1 2 1 4 3 1 2 1 0 4 8 6 6 44 5 4 3 تعداد قاب 2 1 4 2 تعداد خطای صفحه 1 6 فصل دهم :حافظه مجازی 2-4-10الگوریتم FIFO این الگوریتم ،برای هر صفحه ،زمEEان ورود آن صEEفحه بEEه حافظEEه را ثبت می کند .هر وقت صفحه ای بخواهد جEEایگزین شEEود ،قEEدیمی ترین صفحه برای جایگزینی انتخاب می گردد. نکته :الزم نیسEEت زمEEان ورود بEEه حافظEEه ثبت شEEود ،بلکEEه می تEEوانیم یEEک صEEف FIFOایجEEاد کEEنیم تEEا تمEEام صEEفحات موجEEود در حافظه را نگهداری کند .برای جایگزینی ،صفحه موجود در ابتEEدای صف را انتخاب می کنیم ،وقتی صفحه به حافظه آورده شد آن را در انتهای این صفحه قرار می دهیم. 45 FIFO صفحه جایگزینی مجازی حافظه الگوریتمدهم : فصل 1 رشته مراجعات 1 0 7 1 0 2 3 2 0 3 2 1 4 4 4 7 7 7 0 0 0 3 3 0 0 1 1 1 2 2 2 0 0 2 1 2 2 3 3 0 3 0 2 1 0 7 4 0 3 7 7 7 2 2 2 0 3 0 0 1 1 1 قاب های صفحه 46 فصل دهم :حافظه مجازی نکته :کEEارایی الگEEوریتم FIFOهمEEواره خEEوب نیسEEت چEEرا کEEه صفحه ای که جایگزین شد ممکن است یک پیمانEEه ی ارزش دهی اولیه باشد که مدت ها قبل مورد استفاده قEEرار گرفتEEه اسEEت و فعال نیازی به آن نیست. از طرف دیگر ممکن است حاوی متغیر های پر استفاده ای باشد که قبال مقدار اولیه گرفتند و دائما مورد استفاده قرار می گیرند. نکته : .I بEEرای بعضEEی الگEEوریتم هEEا جEEایگزینی صEEفحه ،نEEرخ خطEEای صفحه با افزایش قEEاب هEEای تخصEEیص یافتEEه ،افEEزایش می یابد ( تناقض بیلدی – ) Belady’s anomally 47 .IIاین فرض همیشه درست نیست که اگEEر حافظEEه ی بیشEEتری منحنی خطای صفحه برای جایگزینی FIFOدر مجازی حافظه دهم : مراجعات ای از فصل رشته 1 3 4 1 4 1 2 1 0 8 6 7 48 6 5 4 3 تعداد قاب 2 1 4 2 تعداد خطای صفحه 2 1 6 فصل دهم :حافظه مجازی 3-4-10الگوریتم بهینه • نرخ خطای صفحه در الگوریتم جایگزینی صفحه بهینه ،نسEEبت بEEه سایر الگوریتم ها کمتر است. • الگوریتم بهینه دچار تناقض بهینه نمی شود. • استفاده از این الگوریتم تضمین می کنEEد کEEه نEEرخ خطEEای صEEفحه برای تعداد ثابتی از قاب ها ،کمینه است. • ‏ یک الگوریتم بهینه وجود دارد که به نام های OPTیا MINخوانEEده می شود و به صورت زیر است. صفحه ای را که به مدت طوالنی مورد استفاده قEEرار نمی گEEیرد ، جایگزین کنید. 49 تذکر :پیاده سازی الگوریتم بهینه جایگزین صفحه دشوار است چEEرا الگوریتم بهینه جایگزینی فصل دهم :حافظه مجازی صفحه رشته مراجعات 1 7 0 1 0 1 2 2 3 0 3 2 4 3 0 0 2 2 1 7 0 7 2 2 2 2 2 2 7 7 0 0 0 4 0 3 0 0 0 1 1 3 3 3 1 1 1 3 قاب های صفحه 4 50 فصل دهم :حافظه مجازی 4-4-10الگوریتم LRU اگر تهیه الگوریتم بهینه امکEEان پEEذیر نباشEEد ،تقریEEبی از آن الگEEوریتم امکان پذیر است. تفEEاوت بین الگEEوریتم هEEای FIFOو : OPTالگEEوریتم FIFOاز زمEEان ورود بEEه حافظEEه اسEEتفاده می کنEEد و الگEEوریتم OPTاز زمانیکEEه صفحه مورد استفاده قرار می گیرد استفاده می کند. : LRU 51 اگر از گذشته ی نزدیک به عنوان تقریEEبی از آینEEده ی نزدیEEک اسEEتفاده کEEنیم ،صEEفحه ای را جEEایگزین می کEEنیم کEEه بEEرای مEEدت صفحه جایگزینی مجازی ‏LRUحافظه الگوریتمدهم : فصل 1 رشته مراجعات 1 7 0 0 1 1 2 2 3 0 3 2 4 3 0 1 1 1 4 0 4 4 2 0 0 3 3 3 0 0 0 7 2 2 2 2 2 3 3 0 2 3 1 0 7 2 2 7 7 7 0 0 0 1 1 قاب های صفحه 4 52 فصل دهم :حافظه مجازی ‏ الگوریتم LRUآخرین زمانی را که هر صفحه مورد استفاده قEEرار گرفتEEه اسEEت ثبت می کنEEد و بEEرای جEEایگزینی یEEک صEEفحه LRU ، صفحه ای را انتخاب می کنEEد کEEه بEEرای مEEدت طEEوالنی تEEری مEEورد استفاده قرار نگرفته است. نکتEEه : الگEEوریتم بهینEEه جEEایگزینی LRUزمEEان را بEEه صEEورت معکوس نگاه می کند یعنی اگر SRرا معکوس رشته مراجعت Sدر نظر بگیریم ،آنگاه نرخ خطای صفحه بEEرای الگEEوریتم OPTبEEروی Sهمانند نرخ صفحه برای الگوریتم OPTبروی SRاست بEEه طEEور مشابه نرخ خطای صفحه بEEروی الگEEوریتم LRUبEEروی ، SهماننEEد 53 نرخ خطای صفحه برای الگوریتم LRUبروی SRاست. فصل دهم :حافظه مجازی دو روش برای تعیین اینکه چگونه می بایست برای قEEاب هایی که توسط آخرین زمEEان اسEEتفاده تعریEEف شEEده اند ،ترتیبی را تعیین کرد ،وجود دارد : .1استفاده از شمارنده .2استفاده از پشته 54 فصل دهم :حافظه مجازی .1استفاده از شمارنده :در ساده ترین حالت برای هر ورودی جدول صفحه ،فیلدی به نEEام فیلEEد زمEEان اسEEتفاده در نظEEر می گیریم و بEEه CPUیEEک سEEاعت منطقی یEEا شEEمارنده اضEEافه می کنیم. ‏ ‏ در هر مراجعه به حافظه ،یک واحد به ساعت اضافه می شود. هر وقت به صفحه ای مراجعه می شود ،محتویات ثبات سEEاعت به فیلد زمان استفاده در جدول صفحه ی مربوط بEEه آن صEEفحه کپی می شود .بدین ترتیب ،آخرین زمان مراجعه به هEEر صEEفحه را می دانیم ‏ 55 صفحه ای را جایگزین می کنیم که مقدار زمان آن از همه کمEEتر است. فصل دهم :حافظه مجازی تذکر :این الگو مستلزم جستجوی جدول صفحه اسEEت تEEا صEEفحه LRUپیدا شود و همچنین در هر دستیابی به حافظه نیاز به نوشEEتن در صفحه است ( فیلد زمان اسEEتفاده بایEEد در جEEدول صEEفحه کEEپی شود ) .2استفاده از پشته :روش دیگEEر پیEEاده سEEازی LRUاسEEتفاده از پشته ای است که از شماره صفحات نگهداری می کند. ‏ هر وقت به صفحه ای مراجعه شود ،از پشته حذف شده در بEEاالی پشته قرار می گیرد. ‏ بدین ترتیب ،آخرین صفحه ای که مورد استفاده قرار گرفته است همیشEEه در بEEاالی پشEEته قEEرار دارد و صEEفحه LRUدر پEEایین پشEEته 56 قرار می گیرد. استفاده از پشته برای ضبط تازه ترین مجازی حافظه : دهم فصل مراجعات به صفحه 1 رشته مراجعات 2 1 7 ‏b 57 2 ‏a 1 2 1 0 1 7 7 0 2 7 2 2 1 1 0 0 7 4 4 پشته بعد از ‏b پشته قبل از ‏a 3 4 4 فصل دهم :حافظه مجازی تذکر :چون عناصری باید از میانه پشته حذف شوند ،بهتر است پشته به صورت لیست دو پیوندی پیاده سازی گردد. نکات : .I هیچکدام از الگوریتم های بهینه و LRUدچEEار تنEEاقض بیلEEدی نمی شوند. .IIهیچکدام از پیاده سEEازی هEEای LRUبEEدون پشEEتیبانی سEEخت افزاری و استفاده از ثبات های TLBانجام پذیر نیست. .IIIدسته ای از الگوریتم های جایگزینی صفحه به نEEام الگEEوریتم های پشته ای وجود دارد که هیچگاه دچار تناقض بیلEEدی نمی 58 شود. فصل دهم :حافظه مجازی الگوریتم پشته ای : الگEEوریتمی اسEEت کEEه در آن ،مجموعEEه ای از صEEفحات موجEEود در حافظEEه بEEرای nقEEاب ،همیشEEه زیEEر مجموعEEه ای از صEEفحاتی اسEEت کEEه بEEرای n+1قEEاب در حافظEEه خواهند بود. ‏برای جایگزینی LRUمجموعه صفحات موجود در حافظه ،آخEEرین nصفحه ای که به آنها مراجعه شده است. ‏اگر تعداد قاب ها افزایش یابد ،این nهنوز صفحاتی خواهEEد بEEود که اخEEیرا بEEه آن هEEا مراجعEEه شEEده اسEEت و در حافظEEه بEEاقی می مانند. 59 فصل دهم :حافظه مجازی 5-4-10تقریبی از الگوریتم LRU سخت افزار الزم برای پشتیبانی از ، LRUبEEرای اغلب سیسEEتم هEEای کامپیوتری مهیا نیست. بعضی از سیستم ها از بیت ارجاع برای کمک به الگEEوریتم جEEایگزینی استفاده می کنند. روش بیت ارجاع : ‏ ‏ ‏ 60 هر ورودی جدول صفحه ،دارای یک بیت ارجاع است در آغاز تمام بیت ها توسط سیستم عامل صفر می شوند وقتی فرآینEEد کEEاربر اجEEرا می گEEردد ،بیت ارجEEاع مربEEوط بEEه هEEر صفحه ای که به آن ارجاع شده است ،توسط سEEخت افEEزار برابEEر فصل دهم :حافظه مجازی ‏ با استفاده از بیت ارجاع می توانیم تعیین کنیم که کدام صفحات تاکنون مورد اسEEتفاده قEEرار گرفتEEه انEEد و کEEدام صEEفحات مEEورد استفاده واقع نشده اند ولی ترتیب اسEEتفاده از آن هEEا مشEEخص نیست .این اطالعEEات جEEزئی در مEEورد تEEرتیب صEEفحات منجربEEه الگوریتم هایی می شود که تقریبی از الگوریتم LRUهستند. 1-5-4-10الگوریتم بیت ارجاع اضافی با ثبت بیت های ارجاع با فواصل زمانی منظم ،اطالعEEات بیشEEتری راجع به ترتیب مراجعه به صفحات بدست می آوریم. می توانیم برای هر صEEفحه 8بیت ( )byte 1را در جEEدولی در حافظEEه نگهداری کنیم .در فواصEEل زمEEانی منظم ،یEEک وقفEEه از تEEایمر ، 61 کنترل را به سیستم عامل انتقال می دهد. فصل دهم :حافظه مجازی • سیستم عامEEل بیت ارجEEاع مربEEوط بEEه هEEر صEEفحه را بEEه بیت بEEا ارزش بایت 8بیتی شیفت می دهد .برای این منظEEور ،بقیEEه ی بیت ها را یEEک بیت بEEه سEEمت راسEEت شEEیفت می دهEEد و از بیت مرتبه پایین صرفه نظر می کند. نکتEه : این ثبEEات هEEای شEEیفت 8بیEEتی ،سEEابقه اسEEتفاده از حافظه را برای آخرین هشت دوره زمانی نگهداری می کند . در هشت دوره زمانی اخEEیر مEEورد اسEEتفاده قEEرار نگرفتEEه = 00000000ثبات شیفت در هشت دوره زمانی یکبEEار مEEورد اسEEتفاده قEEرار گرفتEEه =11111111ثبات شیفت ‏62 صفحه ای که ثبات شیفت آن 11000100است نسبت به صفحه فصل دهم :حافظه مجازی 2-5-4-10الگوریتم دومین فرصت (Second )Chance اساس الگوریتم دومین فرصت الگوریتم FIFOاست .وقتی صفحه ای انتخاب شد ،بیت ارجاع آن را بررسی می کنیم. اگر 0باشد : آنرا جایگزین می کنیم. اگر 1باشد : فرصت دیگری به آن صفحه می دهیم و صفحه ی بعدی را به ترتیب FIFOانتخاب می کنیم. ‏ وقتی صفحه ای فرصت دوباره پیدا می کند بیت ارجاع آن 0می شود و زمان فعلی آن به عنوان زمان ورود آن محسوب می شود. 63 فصل دهم :حافظه مجازی پیEEاده سEEازی الگEEوریتم دومین فرصEEت بEEا صEEف حلقوی : در این صف یک اشاره گر مشخص می کنEEد کEEه چEEه صEEفحه ای بایEEد جایگزین شود .وقتی نیاز به قابی باشد ،اشEEاره گEEر حEEرکت می کند تا صفحه ای را بیابد که بیت ارجاع آن 0باشد. ‏ ‏ وقتی اشاره گر حرکت می کند ،بیت ارجاع را 0می کند. وقتی صفحه ای برای جایگزینی انتخاب شد ،آن صفحه از صEEف خارج می گEEردد و صEEفحه ی جدیEEد بEEه جEEای آن در صEEف حلقEEوی قرار می گیرد. 64 الگوریتم دومین فرصت برای جایگزینی صفحه فصل دهم :حافظه مجازی صفحات صفحات بیت های ارجاع بیت های ارجاع 0 0 0 0 صفحۀ 21 بعدی برای جایگزینی 1 3 0 0 0 1 0 )ب( 1 65 صف حلقوی از صفحات 4 1 )الف( 1 صف حلقوی از صفحات فصل دهم :حافظه مجازی 3-5-4-10الگوریتم دومین فرصت پیشرفته برای جایگزینی صفحه بEEرای توسEEعه الگEEوریتم دومین فرصEEت از بیت ارجEEاع و بیت اصEEالح ( بخش ) 10-4به صورت یک جفت اسEEتفاده می شEEود کEEه بEEا این دو بیت چهار حالت زیر امکان پذیر است : )0,0( .1 نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است و تغییر نکرده است .بهترین صفحه برای جایگزینی است. )0,1( .2 نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است ولی تغییر کرده است .صفحه ی مناسبی برای جایگزینی نیسEEت زیرا قبل از جایگزینی نیاز به نوشتن است. 66 )1,0( .3 نشان می دهد که صفحه اخیرا مورد استفاده قرار گرفتEEه فصل دهم :حافظه مجازی 6-4-10الگوریتم های جایگزینی شمارشی • الگEEEوریتم ) : LFU (Least Frequently Usedدر الگEEEوریتم جEEEایگزینی کمترین کاربرد ،صفحه ای که کمترین ارجاع بEEه آن شEEده اسEEت برای جایگزینی انتخاب می شود. ‏ علت این انتخEEاب این اسEEت کEEه تصEEور می شEEود صEEفحه ای کEEه ارجاع کمتری به آن صورت می گیرد ،کاربرد زیادی ندارد. • الگEEEوریتم ) : MFU (Most Frequently Usedدر الگEEEوریتم جEEEایگزینی بیشترین کاربرد ،صEEفحه ای کEEه ارجEEاع بیشEEتری بEEه آن صEEورت گرفت ،به عنوان صفحه ی جایگزین انتخاب می شود. ‏ 67 اینطور استدالل می شود که صفحه ای که کمEEتر بEEه کEEار گرفتEEه شده و تازه به حافظه آورده شده است ،احتماال در آینده بیشEEتر فصل دهم :حافظه مجازی 7-4-10الگوریتم میانگیری صفحه سیستم ها معموال انباری ( )Poolاز قاب های آزاد را نگEEه می دارنEEد . وقتی خطای صفحه رخ دهد .همانند الگوریتم هEEای قبلی ،صEEفحه ای برای جایگزینی انتخاب می شود (صفحه قرباتی) اما در اینجا قبل از اینکه صفحه قربEEانی بEEه خEEارج از حافظEEه بEEرود ، صفحه ی مطلوب به قاب آزاد خوانده می شود .بدین ترتیب بدون اینکه فرآیند منتظر بمانEEد تEEا صEEفحه ی قربEEانی از حافظEEه خEEارج شود ،می تواند اجرای خودش را از سر گیرد .پس ازآنکEEه صEEفحه قربانی از حافظEEه خEEارج شEEد ،قEEاب آن بEEه انبEEار قEEاب هEEای آزاد 68 اضافه می شود. فصل دهم :حافظه مجازی 7-4-10الگوریتم میانگیری صفحه ( ادامه) ... شکل دیگری از این الگوریتم :انباری از قاب های آزاد نگهداری شEEود و مشخص گEEردد کEEه در هEEر قEEاب چEEه صEEفحاتی وجEEود دارد .چEEون محتویات قاب ،هنگام نوشEEتن آن بEEروی دیسEEک تغیEEیر نمی کنEEد ، صفحه قدیمی مستقیما می تواند از انبار قاب آزاد مورد اسEEتفاده قرار گیرد. در این حالت نیاز به I/Oنیست. وقتی خطای صفحه رخ دهد ،ابتدا بررسی می کنیم که آیا صفحه مطلوب در انبار قاب آزاد وجود دارد یا خیر .اگر نبEEود ،بایEEد قEEاب 69 آزادی را انتخاب کرده آن را به حافظه بخوانیم. فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 70 حداقل قابهای قابل تخصیص الگوریتم های تخصیص تخصیص محلی و عمومی فصل دهم :حافظه مجازی 5-10تخصیص قاب ها راهبرد اصلی برای تخصEEیص حافظEEه بEEه فرآینEEدهای مختلEEف ،بEEدین صورت است که هر قاب آزادی به فرآیند کاربر تخصیص می یابEEد. وقتی صفحه بندی درخواستی با چند برنامه ای ترکیب می شود ، مسئله دیگری بوجود می آید .چندبرنامه ای در هر زمان دو یا چند فرآیند را در حافظه قرار می دهد. 15-10حداقل قاب های قابل تخصیصدر راهبرد تخصیص قاب ها محدودیت های گوناگونی وجود دارد. نمی توان بیش از تعداد قاب هEEای موجEEود را تخصEEیص دهیم مگEEر 71 اینکه اشتراک صفحه امکان پذیر باشد. فصل دهم :حافظه مجازی می توان حداقل قاب های قابل تخصیص را نیز مشEEخص کEEرد کEEه با کاهش تعداد قاب های تخصیصEEی بEEه هEEر فرآینEEد ،نEEرخ خطEEای صفحه افزایش می یابد. حداقل تعداد قاب ها توسط معماری مجموعEEه دسEEتورات تعریEEف می گردد. نکته : اگر قبل از اجرای کامEEل یEEک دسEEتور خطEEای صEEفحه رخ دهد ،آن دستور باید از اول اجرا شEEود .در نتیجEEه بایEEد قEEاب هEEای کافی برای نگهداری تمام صفحاتی که توسط یک دستور بEEه آنهEEا مراجعه شود ،داشته باشیم. 72 فصل دهم :حافظه مجازی 10-5-2الگوریتم های تخصیص •ساده ترین روش تخصیص mقاب به nفرآیند است که به هر کدام m/nقaaاب داده می شaaود .که با این الگوی تخصیص ،تخصیص مساوی ( )Equal Allocationمی گویند. •روش دیگر تخصیص قاب ها این است که تشخیص داده شaaود هaaر فرآینaaد چaaه مaaیزان از حافظaaه نیaaاز دارد یعنی حافظه بر حسب اندازه فایل ها به آنها تخصیص می یابد . حافظه مورد نیاز فرآیند si= Pi ‏S=si 2 اگر تعداد قاب ها ی موجود را mدر نظر بگیریم ai ،قaaاب را بaaه 4 فرآینaaد Piتخصaaیص می دهیم که : ‏ai=Si/s*m 73 فصل دهم :حافظه مجازی 3-5-10تخصیص محلی و عمومی الگوریتم های جایگزینی صفحه را می توان به دو دسته تقسیم کرد : ‏ ‏جایگزینی محلی جایگزینی عمومی جایگزینی عمومی :فرآیند می تواند قاب جایگزینی را از مجموعۀ تمام قاب ها انتخاب کند .حتی اگر آن قاب به فرآیندی تخصیص داده شده باشد . ‏ در جایگزینی عمومی ،یک فرآیند ممکن است فقط قاب های تخصیص یافته به سایر فرآیند ها را انتخاب کند و در نتیجه به تعداد قاب های خودش بیفزاید . 74 2 4 فصل دهم :حافظه مجازی جایگزینی محلی :هر ،فرایندی می تواند قاب هایی را انتخاب کند که به آن تخصیص یافته است . ‏ ‏ در جایگزینی محلی ،تعداد قاب هایی که به فرآیند تخصیص یافته است تغییر نمی کند . نکته : مشکل الگوریتم جایگزینی عمومی این اسaaت کaه فرآینaدی نمی توانaaد نaرخ خطaaای صaفحه خود را کنترل کند . 2 4 75 فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها علت کوبیدگی یا عدم تعادل کوبیدگی مدل مجموعه کاری مثال هایی از سیستم عامل فراوانی خطای صفحه سایر مالحظات 76 فصل دهم :حافظه مجازی 6-10کوبیدگی ()Thrashing ‏ می توان فرآیند هایی را در نظر گرفت که قاب هaaای کaaافی ندارنaaد و اگaaر فرآنaaدی فاقaaد قaaاب هaaای تعداد قاب مورد نیاز باشد به زودی دچار خطا می شود که می بایست در چنین وضعیتی ،صفحه ای را جایگزین کند ،حال اگر تمام صفحات در حال استفاده باشد ،می بایست صفحه ای را جaaایگزین کنaaد کaaه بالفاصله به آن نیاز می شود . ‏ صaaفحه بنaaدبی زیaaاد را در نتیجه به زودی دچار خطای صفحه می شaaود واین ادامaaه می یابaaد .این2 کوبیدگی یا عدم تعادل گویند . 77 4 فصل دهم :حافظه مجازی 1-6-10علت کوبیدگی یا عدم تعادل زمتنبنaaد CPUکaaاهش بهaaره وری CPUرا می بینaaد و درجaaه چنaaد برنامaaه ای را افaaزایش می دهaaد (فرآیند های جدید را جایگزین می کند ) ،این فرآیند سعی می کند با دریافت صaaفحاتی از فرآینaaد هaaای در حال اجرا ،شروع به اجرا نماید و منجر به خطای صفحه بیشتری می شaaود و صaaف انتظaaار بaaرای دستگاه طوالنی می شود .در نتیجه بهره وری CPUبیشaaتر کaaاهش می یابaaد و زمانبaaد CPUسaaعی می کند درجۀ چند برنامه ای را هنوز هم بیشتر کند .بدین ترتیب کوبیدگی یا عدم تعادل بوجaaود می آیaaد وتوان عملیاتی سیستم کاهش می یابد . 78 2 4 فصل دهم :حافظه مجازی 4 بهره وری CPU کوبیدگی درجه چند برنامه ای اثaaر کوبیaaدگی یaaا عaaدم تعaaادل بaaا اسaaتفاده از الگaaوریتم جaaایگزینی محلی محaaدود می شaaود .چنانچه فرآیندی در جایگزینی محلی دچار کوبیدگی شود ،نمی تواند قاب هaaا را از فرآینaaدهای دیگaaر بگaaیرد و منجر به کوبیدگی شود . 79 فصل دهم :حافظه مجازی ‏ برای جلوگیری از کوبیدگی ،باید تمام قاب های مورد نیاز فرآیند تامینگردد که برای تعیین اینکaaه یک فرآیند به چند قاب نیاز دارد از راهبرد مجموعaaه کaaاری اسaaتفاده می شaaود .این روش ،مaaدل محلی اجرای فرآیند را تعریف می کند . مدل محلی :بیان می کند که وقaaتی فرآینaaدی در حaaال اجراسaaت از یaک محیaط محلی بaه محیaط محلی دیگر می رود (منظور از محل ،مجموعaaه ای از صaaفحات اسaaت کaaه بaaه طaaور فعaaال بaaا یکaaدیگر مaaورد استفاده قرار می گیرند ) 80 2 4 فصل دهم :حافظه مجازی 10-6-2مدل مجموعه کاری ()Working-Sets ‏ این مدل از پارامتر برای تعریف پنجره مجموعه کاری استفاده می کند . = مجمو عه ا ی از صفحات که اخیرا مراجعه شده اند . 1 ‏ اگر صفحه ای در حال استفاده باشد ،در مجموعه کاری قرار دارد و اگر دیگر مورد استفاده قaaرار نگیرد ،از مجموعۀ کاری حذف می گردد .بنا براین مجموعۀ کاری تقریبی از محل برنامه است . 2 جدول ارجاع صفحه 2 …2615777751623412344434344413234443444 1 4 3 ‏ ‏ مدل مجموعه 81کاری ‏t2 ‏t1 4 }WS( t1) ={1,2,5,6,7}WS( t2) ={3,4 فصل دهم :حافظه مجازی بهترین ویژگی مجموعه کاری اندازه ی آن است .اگر اندازه مجموعه کاری بعنی WSsiرا برای هر فرآیند موجود در سیستم محاسبه کنیم ،داریم : ‏D=WSsi کل قاب های درخواستی ‏aتفاده می کنaaد ،بنaaابراین ‏هر فرآیند از صفحات موجود در مجموعه ی کاری خود به طور فعال اس2 a هر فرآیند iبه WSsiقاب نیاز دارد . ‏اگر =M(D>Mتعداد قاب های موجود ) :کوبیدگی بوجود می آید . 82 4 فصل دهم :حافظه مجازی 3-6-10فراوانی خطای صفحه ()PFF راهبرد فراوانی خطای صفحه نسبت به مدل مجموعه کاری ،روش مناسaaبتری اسaaت .در این روش کaaران باال و پایین برای نرخ خطای صفحه در نظر گرفته می شود . اگر نرخ خطای صفحه > کران باالی نرخ خطaا : قaaاب دیگaaری را بaaه فرآینaaد مaaورد نظر تخصیص می دهیم . اگر نرخ خطای صفحه < کران پایین نرخ خطا : قابی را از آن2فرآیند پس می گیریم . 4 بنابراین می توانیم خطای صفحه را اندازه گیری وکنترل کنیم تا از کوبیدگی جلوگیری به عمل آید . 83 صفحه فراوانی :خطای مجازی حافظه فصل دهم 2 حد باال 3 حد پایین 2 4 کاهش تعداد قاب ها تعداد قاب 84 نرخ خطای صفحه 1 فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 85 ویندوز NT سوالریس 2 فصل دهم :حافظه مجازی 7-10مثال هایی از سیستم عامل در اینجا چگونگی پیاده سازی حافظه مجازی در ویندوز NTو سوالریس 2شرح داده می شود . 1-7-10ویندوز NT وینaaدوز NTحافظaaه مجaaازی را بaaا اسaaتفاده از صaaفحه بنaaدی درخواسaaتی بaaه همaaراه خوشaaه بنaaدی ( )Clusteringپیاذه سازی می کند .خوشه بندی ،خطا هaaای صaaفحه را بaaه این صaaورت حaaل می 2 4اطaaراف این صaaفحه کند که نه تنها صفحات مولد خطا را به حافظه می آورد ،بلکه صaaفحاتی را کaaه در قرار دارند ،به حافظه می آورد . 86 فصل دهم :حافظه مجازی وقتی فرآیندی ایجاد می شود ،یک مجموعه کاری کمینه و بیشینه به آن اختصاص می یابد . ‏اگر برای فرآینaaدی زیaaر مجموعaaه کaaاری آن بیشaaینه اسaaت ،خطaaای صaaفحه ای رخ دهaaد ،مaaدیر حافظه مجازی صفحه ای از لیست صفحات آزاد را تخصیصی می دهد . 2 4 87 فصل دهم :حافظه مجازی 2-7-10سوالریس 2 وقتی بندی منجر به خطای صفحه می شود ،هسته صفحه ای را از لیسaت صaفحات آزاد آن ،بaه آن بنaد تخصیص می دهد .بنابراین الزم است هسته میزان کافی از حافظه آزار را در اختیار داشته باشد . همراه این لیست از صفحات آزاد پارامتری به نام lostfreeوجaaود دارد کaaه کوبیaaدگی را نشaaان می دهد که باید صفحه بندی شوند . Pageoutمی نامند .فرآیند ‏اگر تعداد صفحات آزاد کمتر از lostfreeباشد ،فرآیند را فرآیند 2 Pageoutهمانند الگوریتم دومین فرصت است . 4 ‏الگوریتم Pageoutبرای کنترل نaaرخ پaaویش صaaفحات از چنaaدین پaaارامتر اسaaتفاده می کنaaد .نaaرخ پیمایش بر حسب صفحات در ثانیه بیان می شود و در بازه Slowscanتا Fastscanاست . 88 سوالریس 2 صفحه در فصلکننده پیمایش حافظه مجازی دهم : 1 8192 ‏Fastscan 3 2 4 4 ‏lostfree ‏desfree میزان حافظه آزاد 89 ‏minfree نرخ پویش 2 100 ‏Slowscan فصل دهم :حافظه مجازی مرور کلی صفحه بندی درخواستی ایجاد فرآیند حافظه مجازی جایگزینی صفحه تخصیص قاب ها کوبیدگی مثال هایی از سیستم عامل سایر مالحظات 90 پیش صفحه بندی اندازه صفحه رسش TLB جدول صفحه معکوس ساختار برنامه قفل شدن I/O پردازش بی درنگ فصل دهم :حافظه مجازی 8-10سایر مالحظات 1-8-10پیش صفحه بندی ()Prepaging یکی از ویژگی های بارز سیستم صفحه بندی درخواسaaتس این اسaaت کaaه وقaaتی شaaروع بaaه کaaار می کنaaد ، تعداد زیادی از خطای صaaفحه بوجaaود می آیaaد .این وضaaعیت ناشaaی از تالش بaaرای انتقaaال محaaل اولیaaه بaaه حافظه است .همین وضعیت در زمان های دیگر نیز ممکن است پیش بیاید . . 2در این راهaaبرد تمaaام پیش صفحه بندی سعی می کند از این صفحه بندی زیاد جلوگaaیری بaaه عمaaل آورد 4 صفحات مورد نیاز فرآیند به طور یکجا در همان اول به حافظه آورده می شوند . 91 فصل دهم :حافظه مجازی 2-8-10اندازه صفحه یکی از مواردی که برای تعیین اندازه صفحه می بایست در نظر گرفت ،اندازه صفحه جدول است . برای یک مقدار معین از فضای حافظه مجازی ،کاهش اندازه صفحه ،به تعaaداد صaaفحات و انaaدازه ی جدول صفحه می افزاید .از طرف دیگرهرچه صفحه کوچکتر باشد ،بهره وری بیشتر است . ‏هرچه صفحه کوچکتر باشد ،کل زمان I/Oنیز کمتر است . ‏نکته : 2 4 بعضی از عوامل مثل تکه تکه شaدن داخلی و محلی بaودن ،بaه صaفحات کوچaک تمایaل دارند .در حالیکه عوامل دیگری مثل اندازه جدول و زمان I/Oبر صفحات بزرگتر تاکید دارند . 92 فصل دهم :حافظه مجازی 3-8-10رسش TLB رسش TLBمیزان حافظه است که از TLBقابل دستیابی است وبرابر است با : تعداد ورودی های × TLBاندازه صفحه در حالت ایده آل ،مجموعه کاری مربوط به یک فرآیند در TLBذخیره می شود .در غaaیر اینصaaورت ، فرآیند وقت زیادی را صرف برطaaرف کaaردن ارجاعaaات حافظaaه در جaaدول صaaفحه (بaaه جaaای )TLBمی کند . 2 ‏اگر ورودی های TLBرا دو برابر کنیم ،رسش TLBدو برابر می شود 4. ‏رهیافت دیگری برای افزایش رسش ، TLBافزودن اندازه صفحه یا ارائaaه انaaدازه هaaای گونaaاگون از صفحه می باشد که پشتیبانی از صفحاتی با اندازه های مختلف مستلزم این اسaaت سیسaaتم عامaaل TLBرا مدیریت کند . 93 فصل دهم :حافظه مجازی 4-8-10جدول صفحه معکوس هدف این شکل از مدیریت حافظه ،کاهش میزان حافظه فیزیکی مورد نیاز بaaرای ترجمaaه آدرس مجaaازی به فیزیکی است . برای این صرفه جویی جدولی ایجاد می شود که برای هر صفحه ی حافظه ی فیزیکی یaaک ورودی دارد و این ورودی با جفت< شماره صفحه و شماره فرآیند > مشخص شده است . کدام قاب فیزیکی ذخaaیره در صفحات معکوس ،با نگهداری این اطالعات که کدام صفحه مجازی در2 4 شده است ،میزان حافظه ی فیزیکی مورد نیاز برای ذخیره ی این اطالعات ،کاهش یافته است . اما جدول صفحه معکوس ،فاقد اطالعات کامل راجع به فضای آدرس منطقی فرآیند است . 94 فصل دهم :حافظه مجازی 5-8-10ساختار برنامه صفحه بندی درخواسaaتی از دیaaد کaaاربر شaaفاف و روشaaن اسaaت .در بسaaیاری از مaaوارد کaaاربر از مaaاهیت صفحه بندی حافظه خبر ندارد . در موارد دیگر ،کارآیی سیستم با آگاهی از صفحه بندی درخواستی بهبود می یابد . ‏انتخaaاب دقیaaق سaaاختمان داده هaaا و سaaاختار هaaای برنامaaه نویسaaی می توانaaد محلی بaaودن مراجعaaات را افزایش دهد و نرخ خطای صفحه و تعداد صفحات موجود در مجموعۀ کاری کاهش دهد . 2 4 95 فصل دهم :حافظه مجازی ‏کامپایلر و بار کننده عامل دیگری در صفحه بندی اند . تفکیک کد و داده و تولید کد چند دخولی به معنای این است که صفحات کد می توانند فقط خواندنی با شند .لذا الزم نیست صفحه ای که تغییر نکرده است جایگزین شود . بار کننده ،هر روال را کامال در یک صفحه قرار می دهد و در نتیجه صفحات در مرز صaaفحات قرار نمی گیرند .روال هایی که همدیگر را چندین بار فراخaaوانی می کننaaد در یaaک صaaفحه قaaرار می گیرند . ‏زبان برنامه سازی نیز می تواند در صفحه بندی موثر باشد . 96 2 4 فصل دهم :حافظه مجازی 6-8-10قفل شدن وقتی از صفحه بندی درخواستی استفاده می گردد ،نیاز به این است کaaه بعضaaی از صaaفحات در حافظaaه قفل شوند . یکی از این وضعیت ها وقتی رخ می دهد که عمل I/Oاز حافظه مجaaازی کaaاربر و یaaا در آن صaaورت گیرد I/O .معموال توسط پردازنده I/Oصورت می گیرد .به عنوان مثال تعداد بaaایت هaaایی کaaه بایaaد انتقال یابد و آدرس حافظه میانگیر ،به کنترل کننده نوار داده می شود. وقتی عمل انتقال کامل شد ،وقفه ای به CPUارسال می شود . 97 2 4 نموداری که نشان می دهد چرا قابهایی مجازی می استفاده قرار مورد فصل I/O که برای حافظه دهم : گیرند باید در حافظه باشند گرداننده دیسک میانگ یر 2 4 98 فصل دهم :حافظه مجازی بایaaد مطمئن شaaویم کaaه فرآینaaدی درخواسaaت I/Oنمی کنaaد تaaا مجبaaور شaaود در صaaف دسaaتگاه I/Oقaaرار گیرد .چراکه به هر حال CPUبه این فرآیند ها تخصیصی می یابد و این فرآیند ها موجب خطaaای صaaفحه می شوند . دوراه حل برای حل این مسئله وجود دارد : ‏هیچ عمل I/Oدر حافظه صورت نگیرد ،بلکه داده ها همیشه بین حافظه ی سیستم و حافظaaه ی کaaاربر کپی شوند . • برای نوشتن بلوکی بروی صفحه ،ابتدا آن را در حافظه سیستم کپی می کنیم و سپس آنرا بروی نوار می نویسیم .این عمل کپی ممکن است سربار نا معقولی را ایجاد کند . ‏راه حل دیگر این است که صفحات در حافظه قفل شوند :به هر قاب یک بیت قفل نسبت داده می شaaود و اگر قابی قفل باشد ،نمی تواند برای جایگزینی انتخاب گردد . • در این روش ،برای نوشتن بلوکی بروی نوار ،صفحاتی را که حاوی آن بلوک هستند در حافظه قفل می کنیم . 99 فصل دهم :حافظه مجازی 7-8-10پردازش بی درنگ یک فرآیند یا بند بی درنگ انتظار دارد که با کمترین تاخیر CPUرا در اختیار گیرد و اجرا شود . حافظۀ مجازی میتواند تاخیر هaaای زیaaا دی را بaaرای این فرآینaaد اجaaاد نمایaaد (هنگaaام انتقaaال صaaفحات بaaه حافظه ) .بدین ترتیب ،سیستم های بی درنگ فاقد حافظۀ مجازی اند . 100