حافظه مجازی

حافظه مجازی

اسلاید 1: خلاصه ی فصل 9 سیستم عاملآقای عسکری قاسمپوری اعضای گروه :استاد :میلاد جعفریرضا زاهدیآذین مهرپورشاد1

اسلاید 2: فصل دهمحافظه مجازیتعداد کل اسلاید1002

اسلاید 3: 3فصل دهم : حافظه مجازیحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

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

اسلاید 5: فصل دهم : حافظه مجازیدر موارد زیر ، اغلب نیاز به کل برنامه نیست :برنامه ها اغلب برای پردازش خطای نادر نوشته می شوند که اغلب اجرا نمی شوند ( به دلیل ندرت رخداد خطا )به آرایه ها ، لیست ها و جداول ، حافظه ای بیش از اندازه مورد نیاز تخصیص می یابدبعضی ویژگی ها و گزینه های برنامه ممکن است به ندرت مورد استفاده قرار گیرند.توانایی اجرا برنامه ای که فقط بخشی از آن در حافظه قرار گیرد فواید زیادی دارد :اندازه ی برنامه به فضای فیزیکی محدود نمی شودچون هر برنامه کاربر می تواند فضای فیزیکی کمتری را اشغال کند ، برنامه های بیشتری می توانند به طور همزمان اجرا شوند ( موجب افزایش بهروری CPU )برای بار کردن یا مبادله هر برنامه کاربر به حافظه ، به عمل I/O کمتری نیاز است که موجب افزایش سرعت اجرای برنامه کاربردی می شود. 5

اسلاید 6: 2346فصل دهم : حافظه مجازیصفحه 0صفحه 1صفحه 2صفحه nحافظه فیزیکینگاشت حافظهحافظه منطقی...حافظه مجازی بیش از حافظه فیزیکی است

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

اسلاید 8: 8فصل دهم : حافظه مجازیمفاهیم اساسیکارآیی صفحه بندی درخواستیحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 9: 2-10 صفحه بندی درخواستییک سیستم صفحه بندی درخواستی مشابه سیستم صفحه بندی به همراه مبادله است.فرآیند ها در حافظه ی ثانویه ( معمولا دیسک ) ذخیره می شوند.برای اجرای فرآیند آن را به حافظه می آوریم.اجرای انتقال کامل فرآیند به حافظه ، از مبادله کننده تنبل ( Lazy Swapper ) استفاده می شود که این مبادله تا زمانیکه فرآیندی مورد نیاز نباشد آن را به حافظه نمی آورد.در تکنیک صفحه بندی به جای اصطلاح مبادله کننده از اصطلاح صفحه بند استفاده می کنیم.فصل دهم : حافظه مجازی9

اسلاید 10: 123410فصل دهم : حافظه مجازیبرنامۀAبرنامۀB012345678910111213141520212223انتقال حافظه صفحه بندی شده به فضای همجوار دیسکمبادله به خارجمبادله به داخل

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

اسلاید 12: 1312فصل دهم : حافظه مجازیBAEDCFACF01234567891011121314154Vi6Vii9Vii01234567ABCDEFGH01234567قاببیت اعتبارحافظه منطقیجدول صفحهجدول صفحه وقتی که صفحاتی در حافظه اصلی نیستندحافظه فیزیکی

اسلاید 13: اگر فرآیندی سعی کند از صفحه ای استفاده کند که در حافظه نیست :دستیابی به صفحه ای که به صورت صفحه ای نامعتبر علامت گذاری شده است ، منجر به تله ی خطاهای صفحه (Page Fault) می شود.سخت افزار صفحه بندی برای ترجمه آدرس از طریق جدول صفحه ، متوجه می شود که بیت نا معتبر یک است و تله ای را به سیستم عامل می فرستد و منجربه وقفه می شود.فصل دهم : حافظه مجازی13

اسلاید 14: 123414فصل دهم : حافظه مجازیسیستم عاملبار کردن Miجدول صفحهقاب آزاد156243مراجعهدستور اجرای دوبارهتنظیم مجدد جدول صفحهصفحه مفقودتلهصفحه در حافظه پشتیبانمراحل پردازش خطای صفحه

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

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

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

اسلاید 18: 2-2-10 کارآیی صفحه بندی درخواستیصفحه بندی درخواستی تٲثیر به سزایی در کارآیی سیستم کامپیوتری دارد. برای پی بردن به این موضوع زمان دستیابی موثر را برای صفحه بندی مجازی محاسبه می کنیم.( زمان دستیابی موثر = زمان دستیابی به حافظه : اگر خطای صفحه به وجود نیاید )زمان خطای موثر * P + ma * (1-P) = زمان دستیابی موثرزمان دستیابی به حافظهاحتمال بروز خطای صفحهبرای محاسبه ی زمان دستیابی موثر ، باید بدانیم که برای ارائه خدمات به خطای صفحه ، چقدر زمان نیاز استفصل دهم : حافظه مجازی18

اسلاید 19: خطای صفحه موجب می شود تا اعمال زیر صورت گیرد:ارسال تله به سیستم.ذخیره ثبات های کاربر و حالت فرآیند.تعیین اینکه وقفه ناشی از خطای صفحه بود.کنترل شود که اجرا به صفحه معتبر بود یا خیر و تعیین محل صفحه دیسک.خواندن از دیسک و انتقال به یک قاب آزاد. الف – انتظار در صف آن دستگاه تا ارائه خدمت ب – انتظار برای پیگرد دستگاه و یا زمان تٲخیر ج – شروع انتقال صفحه به قاب آزادفصل دهم : حافظه مجازی19

اسلاید 20: در زمان انتظار برای دیسک ، CPU به کار دیگری تخصیص می یابد (زمانبندی CPU).وقفه ای از دیسک ( کامل شدن عمل I/O دیسک ).ذخیره ی ثبات ها و حالت فرآیند برای کاربر دیگر ( اگر مرحله 6 انجام شده باشد ).تعیین اینکه وقفه از دیسک بوده است.10. تصحیح جدول صفحه و سایر جدول ها تا نشان داده شود که صفحه مطلوب فعلا در حافظه است.11. انتظار برای تخصیص مجدد CPU به این فرآیند.12. بازیابی ثبات های کاربر ، حالت فرآیند و جدول صفحه جدید و از سرگیری دستوری که دچار وقفه شده است.فصل دهم : حافظه مجازی20

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

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

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

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

اسلاید 25: 1-3-10 کپی و نوشتنصفحه بندی درخواستی هنگام خواندن فایل از دیسک به حافظه مورد استفاده قرار می کیرد و این فایل ممکن است حاوی دودویی قابل اجرا باشد ، اما ایجاد فرآیند با استفاده از فراخوان سیستم fork() ، می تواند با استفاده از تکنیکی مشابه با اشتراک صفحه ، نیاز به صفحه بندی درخواستی را برطرف کند.این تکنیک سرعت ایجاد فرآیند را افزایش می دهد و تعداد صفحاتی را که هنگام ایجاد فرآیند جدید باید بوجود آیند را به حداقل می رساند.فرخوان سیستم fork() یک فرآیند فرزند را از پدر آن ایجاد می کند. در واقع ، fork() یک کپی از فضای آدرس پدر را برای فرزند ایجاد می کند.برای این منظور ، صفحات متعلق به پدر را تکثیر می نماید.فصل دهم : حافظه مجازی25

اسلاید 26: تذکر : با توجه به این که فرآیند های فرزند ایجاد شدند ، فراخوان سیستم exec() را فراخوانی می کنند ، کپی کردن فضای آدرس پدر ممکن است ضروری نباشد.از طرف دیگر ، می توانیم از تکنیکی به نام کپی و نوشتن (Copy & Write) استفاده کنیم.روش کپی و نوشتن : در این روش ، فرآیندهای پدر و فرزند از همان آغاز ، از صفحات یکسانی استفاده می کنند.این صفحات مشترک به عنوان صفحات کپی و نوشتن علامت گذاری می شوند یعنی اگر یکی از این فرآیندها بروی صفحه ی مشترک بنویسد ، یک کپی از صفحه ی مشترک ایجاد می شود.فصل دهم : حافظه مجازی26

اسلاید 27: تذکر : تکنیک کپی و نوشتن ، هنگام تکثیر فرآیند در سیستم های عاملی مثل ویندوز 2000 ، لینوکس و سولاریس 2 مورد استفاده قرار می گیرد.تعیین فضای ایجاد صفحه خالی پس از تعیین اینکه صفحه ای باید با استفاده از کپی و نوشتن تکثیرشود:بسیاری از سیستم عامل های مخزنی (Pool) از صفحات آزاد برای این درخواست ها فراهم می کنند.این صفحات آزاد وقتی تخصیص می یابند که پشته یا هرم مربوط به فرآیند باید بسط یابد یا صفحات کپی و نوشتن باید مدیریت شوند. فصل دهم : حافظه مجازی27

اسلاید 28: نکته : سیستم های عامل این صفحات را با تکنیکی به نام پر کردن با صفر در هنگامه تقاضا (zero – fill – on – demand) تخصیص می دهند.تکنیک پر کردن با صفر در هنگام تقاضا : در این تکنیک صفحات درخواستی قبل از تخصیص با صفر پر می شوند و در نتیجه محتویات قبلی آن از بین می روند.نکته : در تکنیک کپی و نوشتن ، صفحه ای که می خواهد کپی شود ، در صفحه ای که با صفر پر شده است کپی می گردد. صفحاتی که برای پشته یا هرم تخصیص یافتند ، به همین ترتیب به صفحاتی نسبت داده می شوند که با صفر پر شده اند.فصل دهم : حافظه مجازی28

اسلاید 29: 2-3-10 فایل های نگاشت حافظهنگاشت حافظه فایل تکنیکی است که با تکنیک حافظه ی مجازی ، با I/O فایل به عنوان روال دستیابی به حافظه استفاده می کنند.رهیافت نگاشت حافظه فایل اجازه می دهد بخشی از فضای آدرس مجازی به طور منطقی به فایل مربوط شوند.فصل دهم : حافظه مجازی29

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

اسلاید 31: نکته : عمل نوشتن در فایلی که در حافظه نگاشت شده است ، ممکن است فورا در فایل روی دیسک انجام نشود.بعضی از سیستم های عامل نگاشت حافظه را فقط از طریق فراخوان سیستم خاصی انجام می دهند و با استفاده از فراخوان سیستم استاندارد ، با I/O فایل برخورد می کند.اما بعضی از سیستم ها صرف نظر از اینکه آیا فایلی به عنوان فایل نگاشت حافظه مشخص شده است یا خیر آن را به صورت نگاشت حافظه در نظر می گیرند.تذکر : ممکن است چند فرآیند بتوانند به یک فایل در حافظه ی مجازی نگاشت شوند تا اشتراک داده به وجود آید.فصل دهم : حافظه مجازی31

اسلاید 32: 132فصل دهم : حافظه مجازی123456حافظه مجازی فرآیند A361542123456123456حافظه مجازی فرآیند Bحافظه فیزیکیفایل دیسکفایلهای نگاشت حافظه

اسلاید 33: 33فصل دهم : حافظه مجازیالگوریتم FIFOاگوریتم بهینهطرح اصلی جایگزینی صفحهالگوریتم LRUتقریبی از الگوریتم LRUالگوریتم های جایگزینی شمارشیالگوریتم میانگیری صفحهحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 34: 4-10 جایگزینی صفحهدر بحث هایی که تا کنون گفته شد نرخ خطای صفحه چندان جدی نبود چرا که هر صفحه حداکثر یک بار ( هنگامیکه اولین بار به آن ارجاع می شود ) دچار خطای صفحه می گردید.اگر فرآیند 10 صفحه ای فقط نیمی از آنها استفاده کند صفحه بندی درخواستی ، در I/O مورد نیاز برای 5 صفحه ی دیگر صرفه جویی می کند.همچنین می توانستیم با اجرای در برابر فرآیندها ، درجه چندبرنامه ای را بالا ببریم ، لذا اگر 40 قاب می داشتیم می توانستیم 8 فرآیند را به جای 4 فرآیندی که اجرا شدند به هر 10 قاب نیاز داشتند ، اجرا کنیم ( 5 عدد از آنها مورد استفاده واقع نمی شوند )فصل دهم : حافظه مجازی34

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

اسلاید 36: 36فصل دهم : حافظه مجازینیاز به جایگزینی صفحهناظرDHبار کردن MJAE01234567BMحافظه فیزیکیHبار کردن MJMHBJM3V4V5Vi6Vi2V7Vقاببیت اعتبارقاببیت اعتبارحافظه منطقی برای کاربر 1حافظه منطقی برای کاربر 2جدول صفحه برای کاربر 1جدول صفحه برای کاربر 2

اسلاید 37: 1-4-10 طرح اصلی جایگزینی صفحهجایگذینی صفحه به این صورت عمل می کند :اگر قاب آزادی موجود نباشد قابی را پیدا می کنیم که فعلا در حال استفاده نیست و آن را آزاد می کنیم.برای آزاد کردن قاب ، محتویات آن را در فضای مبادله می نویسیم و جدول صفحه ( و سایر جداول ) را تغییر می دهیم ( تا نشان دهیم صفحه فعلا در حافظه نیست )قاب آزاد شده می تواند برای نگهداری صفحه ای که فرآیند برای آن دچار خطا شده است بکار رودفصل دهم : حافظه مجازی37

اسلاید 38: روال خدمات خطای صفحه به صورت زیر تغییر می کند تا جایگذینی صفحه را نیز انجام دهد.محلی از دیسک را بیابد که صفحه مطلوب در آنجا قرار دارد.قاب آزاد را بیابد : الف - اگر قاب آزاد وجود دارد از آن استفاده کند. ب - وگرنه با استفاده از الگوریتم جایگزینی صفحه ، یک قاب را برای قربانی کردن انتخاب نماید ( آن قاب را خالی کند)ج - صفحه ی قربانی را بروی دیسک بنویسد و جدول قاب و صفحه را نیز بطور مناسب تغییر دهد.صفحه مطلوب را به قاب آزاد منتقل کند و جداول صفحه و قاب را تغییر دهد.فرآیند کاربر را دوباره اجرا نماید.فصل دهم : حافظه مجازی38

اسلاید 39: 123439فصل دهم : حافظه مجازیقربانیحافظه فیزیکی0ifV1243fقاببیت اعتبارتغییر به مقدار نامعتبرتنظیم مجدد برای صفحۀ جدیدصفحۀ قربانی برای مباله با خارج مبادلۀ صفحۀ مطلوب به حافظهجایگزینی صفحه

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

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

اسلاید 42: نکات :این تکنیک به صفحات فقط خواندنی ( مثل صفحات کد باینری ) اعمال می شوداین الگو زمان ارائه خدمات به خطای صفحه را کاهش می دهد ، زیرا در صورتیکه صفحه تغییر نکند ، زمان I/O به نصف تغلیل می یابد.تذکر : جایگزینی صفحه اساس کار صفحه بندی درخواستی است برای پیاده سازی صفحه بندی درخواستی دو مسئله را باید حل کنیمالگوریتم تخصیص قاب بنویسیمالگوریتم جایگزینی صفحه بنویسیمفصل دهم : حافظه مجازی42

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

اسلاید 44: 123444فصل دهم : حافظه مجازیتعداد قابتعداد خطای صفحه161412108642123456نمودار خطای صفحه بر حسب تعداد قاب ها

اسلاید 45: 2-4-10 الگوریتم FIFO این الگوریتم ،برای هر صفحه ، زمان ورود آن صفحه به حافظه را ثبت می کند. هر وقت صفحه ای بخواهد جایگزین شود ، قدیمی ترین صفحه برای جایگزینی انتخاب می گردد.نکته : لازم نیست زمان ورود به حافظه ثبت شود ، بلکه می توانیم یک صف FIFO ایجاد کنیم تا تمام صفحات موجود در حافظه را نگهداری کند. برای جایگزینی ، صفحه موجود در ابتدای صف را انتخاب می کنیم ، وقتی صفحه به حافظه آورده شد آن را در انتهای این صفحه قرار می دهیم.فصل دهم : حافظه مجازی45

اسلاید 46: 146فصل دهم : حافظه مجازی77070120123123043042070120304230321201701423023013012712702701قاب های صفحهرشته مراجعاتالگوریتم جایگزینی صفحه FIFO

اسلاید 47: نکته : کارایی الگوریتم FIFO همواره خوب نیست چرا که صفحه ای که جایگزین شد ممکن است یک پیمانه ی ارزش دهی اولیه باشد که مدت ها قبل مورد استفاده قرار گرفته است و فعلا نیازی به آن نیست.از طرف دیگر ممکن است حاوی متغیر های پر استفاده ای باشد که قبلا مقدار اولیه گرفتند و دائما مورد استفاده قرار می گیرند.نکته : برای بعضی الگوریتم ها جایگزینی صفحه ، نرخ خطای صفحه با افزایش قاب های تخصیص یافته ، افزایش می یابد ( تناقض بیلدی – Belady’s anomally )این فرض همیشه درست نیست که اگر حافظه ی بیشتری در اختیار فرآیند قرار گیرد ، کارایی آن افزایش می یابد. فصل دهم : حافظه مجازی47

اسلاید 48: 123448فصل دهم : حافظه مجازی1234فصل دهم : حافظه مجازیتعداد قابتعداد خطای صفحه1614121086421234567منحنی خطای صفحه برای جایگزینی FIFO در رشته ای از مراجعات

اسلاید 49: 3-4-10 الگوریتم بهینه نرخ خطای صفحه در الگوریتم جایگزینی صفحه بهینه ، نسبت به سایر الگوریتم ها کمتر است.الگوریتم بهینه دچار تناقض بهینه نمی شود.استفاده از این الگوریتم تضمین می کند که نرخ خطای صفحه برای تعداد ثابتی از قاب ها ، کمینه است.یک الگوریتم بهینه وجود دارد که به نام های OPT یا MIN خوانده می شود و به صورت زیر است.صفحه ای را که به مدت طولانی مورد استفاده قرار نمی گیرد ، جایگزین کنید.تذکر : پیاده سازی الگوریتم بهینه جایگزین صفحه دشوار است چرا که به اطلاعات زود هنگام در مورد رشته مراجعه نیاز دارد.فصل دهم : حافظه مجازی49

اسلاید 50: 23450فصل دهم : حافظه مجازی70120304230321201701رشته مراجعات70701201231203243203201701قاب های صفحهالگوریتم بهینه جایگزینی صفحه

اسلاید 51: 4-4-10 الگوریتم LRU اگر تهیه الگوریتم بهینه امکان پذیر نباشد ، تقریبی از آن الگوریتم امکان پذیر است.تفاوت بین الگوریتم های FIFO و OPT : الگوریتم FIFO از زمان ورود به حافظه استفاده می کند و الگوریتم OPT از زمانیکه صفحه مورد استفاده قرار می گیرد استفاده می کند.LRU : اگر از گذشته ی نزدیک به عنوان تقریبی از آینده ی نزدیک استفاده کنیم ، صفحه ای را جایگزین می کنیم که برای مدت طولانی مورد استفاده قرار نگرفته است. این روش را الگوریتم کمترین استفاده در گذشته نزدیک (Least Recently Used) می نامند.فصل دهم : حافظه مجازی51

اسلاید 52: 123452فصل دهم : حافظه مجازیفصل دهم : حافظه مجازی77070120120340340243270120304230321201701032132102107قاب های صفحهرشته مراجعاتالگوریتم LRUجایگزینی صفحه

اسلاید 53: الگوریتم LRU آخرین زمانی را که هر صفحه مورد استفاده قرار گرفته است ثبت می کند و برای جایگزینی یک صفحه ، LRU صفحه ای را انتخاب می کند که برای مدت طولانی تری مورد استفاده قرار نگرفته است. نکته : الگوریتم بهینه جایگزینی LRU زمان را به صورت معکوس نگاه می کند یعنی اگر SR را معکوس رشته مراجعت S در نظر بگیریم ، آنگاه نرخ خطای صفحه برای الگوریتم OPT بروی S همانند نرخ صفحه برای الگوریتم OPT بروی SR است به طور مشابه نرخ خطای صفحه بروی الگوریتم LRU بروی S ، همانند نرخ خطای صفحه برای الگوریتم LRU بروی SR است.فصل دهم : حافظه مجازی53

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

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

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

اسلاید 57: 123457فصل دهم : حافظه مجازی4707101212712رشته مراجعاتab10742104پشته بعد از bپشته قبل از a27استفاده از پشته برای ضبط تازه ترین مراجعات به صفحه

اسلاید 58: تذکر : چون عناصری باید از میانه پشته حذف شوند ، بهتر است پشته به صورت لیست دو پیوندی پیاده سازی گردد.نکات : هیچکدام از الگوریتم های بهینه و LRU دچار تناقض بیلدی نمی شوند.هیچکدام از پیاده سازی های LRU بدون پشتیبانی سخت افزاری و استفاده از ثبات های TLB انجام پذیر نیست.دسته ای از الگوریتم های جایگزینی صفحه به نام الگوریتم های پشته ای وجود دارد که هیچگاه دچار تناقض بیلدی نمی شود.فصل دهم : حافظه مجازی58

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

اسلاید 60: 5-4-10 تقریبی از الگوریتم LRU سخت افزار لازم برای پشتیبانی از LRU ، برای اغلب سیستم های کامپیوتری مهیا نیست.بعضی از سیستم ها از بیت ارجاع برای کمک به الگوریتم جایگزینی استفاده می کنند.روش بیت ارجاع : هر ورودی جدول صفحه ، دارای یک بیت ارجاع استدر آغاز تمام بیت ها توسط سیستم عامل صفر می شوندوقتی فرآیند کاربر اجرا می گردد ، بیت ارجاع مربوط به هر صفحه ای که به آن ارجاع شده است ، توسط سخت افزار برابر یک می شود.فصل دهم : حافظه مجازی60

اسلاید 61: با استفاده از بیت ارجاع می توانیم تعیین کنیم که کدام صفحات تاکنون مورد استفاده قرار گرفته اند و کدام صفحات مورد استفاده واقع نشده اند ولی ترتیب استفاده از آن ها مشخص نیست . این اطلاعات جزئی در مورد ترتیب صفحات منجربه الگوریتم هایی می شود که تقریبی از الگوریتم LRU هستند.1-5-4-10 الگوریتم بیت ارجاع اضافی با ثبت بیت های ارجاع با فواصل زمانی منظم ، اطلاعات بیشتری راجع به ترتیب مراجعه به صفحات بدست می آوریم.می توانیم برای هر صفحه 8 بیت (1 byte) را در جدولی در حافظه نگهداری کنیم. در فواصل زمانی منظم ، یک وقفه از تایمر ، کنترل را به سیستم عامل انتقال می دهد.فصل دهم : حافظه مجازی61

اسلاید 62: سیستم عامل بیت ارجاع مربوط به هر صفحه را به بیت با ارزش بایت 8 بیتی شیفت می دهد. برای این منظور ، بقیه ی بیت ها را یک بیت به سمت راست شیفت می دهد و از بیت مرتبه پایین صرفه نظر می کند.نکته : این ثبات های شیفت 8 بیتی ، سابقه استفاده از حافظه را برای آخرین هشت دوره زمانی نگهداری می کند .در هشت دوره زمانی اخیر مورد استفاده قرار نگرفته 00000000 = ثبات شیفتدر هشت دوره زمانی یکبار مورد استفاده قرار گرفته 11111111= ثبات شیفتصفحه ای که ثبات شیفت آن 11000100 است نسبت به صفحه ای با ثبات شیفت 01110111 ، اخیرا بیشتر مورد استفاده واقع شده است.فصل دهم : حافظه مجازی62

اسلاید 63: 2-5-4-10 الگوریتم دومین فرصت (Second Chance) اساس الگوریتم دومین فرصت الگوریتم FIFO است. وقتی صفحه ای انتخاب شد ، بیت ارجاع آن را بررسی می کنیم.اگر 0 باشد : آنرا جایگزین می کنیم.اگر 1 باشد : فرصت دیگری به آن صفحه می دهیم و صفحه ی بعدی را به ترتیب FIFO انتخاب می کنیم.وقتی صفحه ای فرصت دوباره پیدا می کند بیت ارجاع آن 0 می شود و زمان فعلی آن به عنوان زمان ورود آن محسوب می شود.فصل دهم : حافظه مجازی63

اسلاید 64: پیاده سازی الگوریتم دومین فرصت با صف حلقوی :در این صف یک اشاره گر مشخص می کند که چه صفحه ای باید جایگزین شود. وقتی نیاز به قابی باشد ، اشاره گر حرکت می کند تا صفحه ای را بیابد که بیت ارجاع آن 0 باشد.وقتی اشاره گر حرکت می کند ، بیت ارجاع را 0 می کند.وقتی صفحه ای برای جایگزینی انتخاب شد ، آن صفحه از صف خارج می گردد و صفحه ی جدید به جای آن در صف حلقوی قرار می گیرد.نکته : اگر تمام بیت ها یک باشند ( بدترین حالت ) الگوریتم second chance به الگوریتم FIFO تبدیل می شود.فصل دهم : حافظه مجازی64

اسلاید 65: 65فصل دهم : حافظه مجازی2340000011صفحاتبیت های ارجاعصف حلقوی از صفحات0011011صفحاتبیت های ارجاعصف حلقوی از صفحاتصفحۀ بعدی برای جایگزینی(الف)(ب)الگوریتم دومین فرصت برای جایگزینی صفحه

اسلاید 66: 3-5-4-10 الگوریتم دومین فرصت پیشرفته برای جایگزینی صفحهبرای توسعه الگوریتم دومین فرصت از بیت ارجاع و بیت اصلاح ( بخش 4-10 ) به صورت یک جفت استفاده می شود که با این دو بیت چهار حالت زیر امکان پذیر است :(0,0) نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است و تغییر نکرده است. بهترین صفحه برای جایگزینی است.(0,1) نشان می دهد که صفحه اخیرا مورد استفاده قرار نگرفته است ولی تغییر کرده است. صفحه ی مناسبی برای جایگزینی نیست زیرا قبل از جایگزینی نیاز به نوشتن است.(1,0) نشان می دهد که صفحه اخیرا مورد استفاده قرار گرفته ولی تغییر نکرده است. احتمال دارد در آینده ای نزدیک مورد استفاده قرار گیرد.(1,1) نشان می دهد که صفحه اخیرا مورد استفاده قرار گرفته و تغییر کرده است. احتمالا دوباره مورد استفاده قرار می گیرد و قبل از جایگزینی باید نوشته شود.فصل دهم : حافظه مجازی66

اسلاید 67: 6-4-10 الگوریتم های جایگزینی شمارشیالگوریتم LFU (Least Frequently Used) : در الگوریتم جایگزینی کمترین کاربرد ، صفحه ای که کمترین ارجاع به آن شده است برای جایگزینی انتخاب می شود.علت این انتخاب این است که تصور می شود صفحه ای که ارجاع کمتری به آن صورت می گیرد ، کاربرد زیادی ندارد.الگوریتم MFU (Most Frequently Used) : در الگوریتم جایگزینی بیشترین کاربرد ، صفحه ای که ارجاع بیشتری به آن صورت گرفت ، به عنوان صفحه ی جایگزین انتخاب می شود. اینطور استدلال می شود که صفحه ای که کمتر به کار گرفته شده و تازه به حافظه آورده شده است ، احتمالا در آینده بیشتر به کار گرفته خواهد شد.فصل دهم : حافظه مجازی67

اسلاید 68: 7-4-10 الگوریتم میانگیری صفحهسیستم ها معمولا انباری (Pool) از قاب های آزاد را نگه می دارند . وقتی خطای صفحه رخ دهد. همانند الگوریتم های قبلی، صفحه ای برای جایگزینی انتخاب می شود (صفحه قرباتی)اما در اینجا قبل از اینکه صفحه قربانی به خارج از حافظه برود ، صفحه ی مطلوب به قاب آزاد خوانده می شود. بدین ترتیب بدون اینکه فرآیند منتظر بماند تا صفحه ی قربانی از حافظه خارج شود ، می تواند اجرای خودش را از سر گیرد. پس ازآنکه صفحه قربانی از حافظه خارج شد ، قاب آن به انبار قاب های آزاد اضافه می شود.فصل دهم : حافظه مجازی68

اسلاید 69: 7-4-10 الگوریتم میانگیری صفحه ( ادامه... )شکل دیگری از این الگوریتم : انباری از قاب های آزاد نگهداری شود و مشخص گردد که در هر قاب چه صفحاتی وجود دارد. چون محتویات قاب ، هنگام نوشتن آن بروی دیسک تغییر نمی کند ، صفحه قدیمی مستقیما می تواند از انبار قاب آزاد مورد استفاده قرار گیرد.در این حالت نیاز به I/O نیست.وقتی خطای صفحه رخ دهد ، ابتدا بررسی می کنیم که آیا صفحه مطلوب در انبار قاب آزاد وجود دارد یا خیر. اگر نبود ، باید قاب آزادی را انتخاب کرده آن را به حافظه بخوانیم.فصل دهم : حافظه مجازی69

اسلاید 70: 70فصل دهم : حافظه مجازیالگوریتم های تخصیصتخصیص محلی و عمومیحداقل قابهای قابل تخصیصحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 71: 5-10 تخصیص قاب هاراهبرد اصلی برای تخصیص حافظه به فرآیندهای مختلف ، بدین صورت است که هر قاب آزادی به فرآیند کاربر تخصیص می یابد. وقتی صفحه بندی درخواستی با چند برنامه ای ترکیب می شود ، مسئله دیگری بوجود می آید. چندبرنامه ای در هر زمان دو یا چند فرآیند را در حافظه قرار می دهد.-15-10 حداقل قاب های قابل تخصیصدر راهبرد تخصیص قاب ها محدودیت های گوناگونی وجود دارد.نمی توان بیش از تعداد قاب های موجود را تخصیص دهیم مگر اینکه اشتراک صفحه امکان پذیر باشد.فصل دهم : حافظه مجازی71

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

اسلاید 73: 2473فصل دهم : حافظه مجازی10-5-2 الگوریتم های تخصیص ساده ترین روش تخصیصm قاب به n فرآیند است که به هر کدام m/n قاب داده می شود .که با این الگوی تخصیص ، تخصیص مساوی (Equal Allocation) می گویند.روش دیگر تخصیص قاب ها این است که تشخیص داده شود هر فرآیند چه میزان از حافظه نیاز دارد یعنی حافظه بر حسب اندازه فایل ها به آنها تخصیص می یابد .S=si si= Pi حافظه مورد نیاز فرآینداگر تعداد قاب ها ی موجود را m در نظر بگیریم ، ai قاب را به فرآیند Pi تخصیص می دهیم که :ai=Si/s*m

اسلاید 74: 2474فصل دهم : حافظه مجازی3-5-10 تخصیص محلی و عمومیالگوریتم های جایگزینی صفحه را می توان به دو دسته تقسیم کرد :جایگزینی عمومیجایگزینی محلی جایگزینی عمومی : فرآیند می تواند قاب جایگزینی را از مجموعۀ تمام قاب ها انتخاب کند .حتی اگر آن قاب به فرآیندی تخصیص داده شده باشد .در جایگزینی عمومی ، یک فرآیند ممکن است فقط قاب های تخصیص یافته به سایر فرآیند ها را انتخاب کند و در نتیجه به تعداد قاب های خودش بیفزاید .

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

اسلاید 76: 76فصل دهم : حافظه مجازیمدل مجموعه کاریفراوانی خطای صفحهعلت کوبیدگی یا عدم تعادلحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 77: 2477فصل دهم : حافظه مجازی6-10 کوبیدگی (Thrashing)می توان فرآیند هایی را در نظر گرفت که قاب های کافی ندارند و اگر فرآندی فاقد قاب های تعداد قاب مورد نیاز باشد به زودی دچار خطا می شود که می بایست در چنین وضعیتی ، صفحه ای را جایگزین کند ، حال اگر تمام صفحات در حال استفاده باشد ، می بایست صفحه ای را جایگزین کند که بلافاصله به آن نیاز می شود .در نتیجه به زودی دچار خطای صفحه می شود واین ادامه می یابد . این صفحه بندبی زیاد را کوبیدگی یا عدم تعادل گویند .

اسلاید 78: 2478فصل دهم : حافظه مجازی1-6-10 علت کوبیدگی یا عدم تعادلزمتنبند CPU کاهش بهره وری CPU را می بیند و درجه چند برنامه ای را افزایش می دهد (فرآیند های جدید را جایگزین می کند ) ، این فرآیند سعی می کند با دریافت صفحاتی از فرآیند های در حال اجرا ، شروع به اجرا نماید و منجر به خطای صفحه بیشتری می شود و صف انتظار برای دستگاه طولانی می شود . در نتیجه بهره وری CPUبیشتر کاهش می یابد و زمانبد CPU سعی می کند درجۀ چند برنامه ای را هنوز هم بیشتر کند .بدین ترتیب کوبیدگی یا عدم تعادل بوجود می آید وتوان عملیاتی سیستم کاهش می یابد .

اسلاید 79: 79فصل دهم : حافظه مجازی4کوبیدگیدرجه چند برنامه ایبهره وری CPU اثر کوبیدگی یا عدم تعادل با استفاده از الگوریتم جایگزینی محلی محدود می شود .چنانچه فرآیندی در جایگزینی محلی دچار کوبیدگی شود ، نمی تواند قاب ها را از فرآیندهای دیگر بگیرد و منجر به کوبیدگی شود .

اسلاید 80: 2480فصل دهم : حافظه مجازیبرای جلوگیری از کوبیدگی ، باید تمام قاب های مورد نیاز فرآیند تامینگردد که برای تعیین اینکه یک فرآیند به چند قاب نیاز دارد از راهبرد مجموعه کاری استفاده می شود . این روش ، مدل محلی اجرای فرآیند را تعریف می کند .مدل محلی : بیان می کند که وقتی فرآیندی در حال اجراست از یک محیط محلی به محیط محلی دیگر می رود (منظور از محل ، مجموعه ای از صفحات است که به طور فعال با یکدیگر مورد استفاده قرار می گیرند )

اسلاید 81: 2481فصل دهم : حافظه مجازی10-6-2 مدل مجموعه کاری (Working-Sets)این مدل از پارامتر برای تعریف پنجره مجموعه کاری استفاده می کند . = مجمو عه ا ی از صفحات که اخیرا مراجعه شده اند .اگر صفحه ای در حال استفاده باشد ، در مجموعه کاری قرار دارد و اگر دیگر مورد استفاده قرار نگیرد ، از مجموعۀ کاری حذف می گردد .بنا براین مجموعۀ کاری تقریبی از محل برنامه است .123413…2615777751623412344434344413234443444…جدول ارجاع صفحهمدل مجموعه کاریWS( t1) ={1,2,5,6,7}WS( t2) ={3,4}t2t1

اسلاید 82: 2482فصل دهم : حافظه مجازیبهترین ویژگی مجموعه کاری اندازه ی آن است . اگر اندازه مجموعه کاری بعنی WSsi را برای هر فرآیند موجود در سیستم محاسبه کنیم ، داریم :D=WSsi کل قاب های درخواستی هر فرآیند از صفحات موجود در مجموعه ی کاری خود به طور فعال استفاده می کند ، بنابراین هر فرآیند i به WSsi قاب نیاز دارد .اگر D>M(M= تعداد قاب های موجود ) : کوبیدگی بوجود می آید .

اسلاید 83: 2483فصل دهم : حافظه مجازی3-6-10 فراوانی خطای صفحه (PFF)راهبرد فراوانی خطای صفحه نسبت به مدل مجموعه کاری ، روش مناسبتری است . در این روش کران بالا و پایین برای نرخ خطای صفحه در نظر گرفته می شود .اگر نرخ خطای صفحه > کران بالای نرخ خطا : قاب دیگری را به فرآیند مورد نظر تخصیص می دهیم . اگر نرخ خطای صفحه < کران پایین نرخ خطا : قابی را از آن فرآیند پس می گیریم .بنابراین می توانیم خطای صفحه را اندازه گیری وکنترل کنیم تا از کوبیدگی جلوگیری به عمل آید .

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

اسلاید 85: 85فصل دهم : حافظه مجازیسولاریس 2ویندوز NTحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 86: 2486فصل دهم : حافظه مجازی7-10 مثال هایی از سیستم عامل در اینجا چگونگی پیاده سازی حافظه مجازی در ویندوز NT و سولاریس 2 شرح داده می شود .1-7-10 ویندوز NTویندوز NT حافظه مجازی را با استفاده از صفحه بندی درخواستی به همراه خوشه بندی (Clustering) پیاذه سازی می کند . خوشه بندی ، خطا های صفحه را به این صورت حل می کند که نه تنها صفحات مولد خطا را به حافظه می آورد ، بلکه صفحاتی را که در اطراف این صفحه قرار دارند ، به حافظه می آورد .

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

اسلاید 88: 2488فصل دهم : حافظه مجازی2-7-10 سولاریس 2وقتی بندی منجر به خطای صفحه می شود ، هسته صفحه ای را از لیست صفحات آزاد آن ، به آن بند تخصیص می دهد . بنابراین لازم است هسته میزان کافی از حافظه آزار را در اختیار داشته باشد .همراه این لیست از صفحات آزاد پارامتری به نام lostfree وجود دارد که کوبیدگی را نشان می دهد که باید صفحه بندی شوند .اگر تعداد صفحات آزاد کمتر از lostfree باشد ، فرآیند را فرآیند Pageout می نامند . فرآیند Pageout همانند الگوریتم دومین فرصت است .الگوریتم Pageout برای کنترل نرخ پویش صفحات از چندین پارامتر استفاده می کند . نرخ پیمایش بر حسب صفحات در ثانیه بیان می شود و در بازه Slowscan تا Fastscan است .

اسلاید 89: 2489فصل دهم : حافظه مجازی1234فصل دهم : حافظه مجازیمیزان حافظه آزادنرخ پویشlostfreedesfreeminfree8192Fastscan100Slowscanپیمایش کننده صفحه در سولاریس 2

اسلاید 90: 90فصل دهم : حافظه مجازیاندازه صفحهرسش TLBپیش صفحه بندیجدول صفحه معکوسساختار برنامهقفل شدن I/Oپردازش بی درنگحافظه مجازیمرور کلیصفحه بندی درخواستیایجاد فرآیندجایگزینی صفحهتخصیص قاب هاکوبیدگیمثال هایی از سیستم عاملسایر ملاحظات

اسلاید 91: 2491فصل دهم : حافظه مجازی8-10 سایر ملاحظات 1-8-10 پیش صفحه بندی (Prepaging) یکی از ویژگی های بارز سیستم صفحه بندی درخواستس این است که وقتی شروع به کار می کند ، تعداد زیادی از خطای صفحه بوجود می آید .این وضعیت ناشی از تلاش برای انتقال محل اولیه به حافظه است .همین وضعیت در زمان های دیگر نیز ممکن است پیش بیاید .پیش صفحه بندی سعی می کند از این صفحه بندی زیاد جلوگیری به عمل آورد .در این راهبرد تمام صفحات مورد نیاز فرآیند به طور یکجا در همان اول به حافظه آورده می شوند .

اسلاید 92: 2492فصل دهم : حافظه مجازی2-8-10 اندازه صفحه یکی از مواردی که برای تعیین اندازه صفحه می بایست در نظر گرفت ، اندازه صفحه جدول است .برای یک مقدار معین از فضای حافظه مجازی ،کاهش اندازه صفحه ، به تعداد صفحات و اندازه ی جدول صفحه می افزاید . از طرف دیگرهرچه صفحه کوچکتر باشد ، بهره وری بیشتر است . هرچه صفحه کوچکتر باشد ، کل زمان I/O نیز کمتر است .نکته : بعضی از عوامل مثل تکه تکه شدن داخلی و محلی بودن ، به صفحات کوچک تمایل دارند .در حالیکه عوامل دیگری مثل اندازه جدول و زمان I/O بر صفحات بزرگتر تاکید دارند .

اسلاید 93: 2493فصل دهم : حافظه مجازی3-8-10 رسش TLBرسش TLB میزان حافظه است که از TLB قابل دستیابی است وبرابر است با : تعداد ورودی های TLB × اندازه صفحهدر حالت ایده آل ، مجموعه کاری مربوط به یک فرآیند در TLB ذخیره می شود .در غیر اینصورت ، فرآیند وقت زیادی را صرف برطرف کردن ارجاعات حافظه در جدول صفحه (به جای TLB) می کند .اگر ورودی های TLB را دو برابر کنیم ، رسشTLB دو برابر می شود .رهیافت دیگری برای افزایش رسش TLB ، افزودن اندازه صفحه یا ارائه اندازه های گوناگون از صفحه می باشد که پشتیبانی از صفحاتی با اندازه های مختلف مستلزم این است سیستم عامل TLB را مدیریت کند .

اسلاید 94: 2494فصل دهم : حافظه مجازی4-8-10 جدول صفحه معکوسهدف این شکل از مدیریت حافظه ، کاهش میزان حافظه فیزیکی مورد نیاز برای ترجمه آدرس مجازی به فیزیکی است .برای این صرفه جویی جدولی ایجاد می شود که برای هر صفحه ی حافظه ی فیزیکی یک ورودی دارد و این ورودی با جفت< شماره صفحه و شماره فرآیند > مشخص شده است . در صفحات معکوس ، با نگهداری این اطلاعات که کدام صفحه مجازی در کدام قاب فیزیکی ذخیره شده است ، میزان حافظه ی فیزیکی مورد نیاز برای ذخیره ی این اطلاعات ، کاهش یافته است .اما جدول صفحه معکوس ، فاقد اطلاعات کامل راجع به فضای آدرس منطقی فرآیند است .

اسلاید 95: 2495فصل دهم : حافظه مجازی5-8-10 ساختار برنامه صفحه بندی درخواستی از دید کاربر شفاف و روشن است . در بسیاری از موارد کاربر از ماهیت صفحه بندی حافظه خبر ندارد .در موارد دیگر ، کارآیی سیستم با آگاهی از صفحه بندی درخواستی بهبود می یابد .انتخاب دقیق ساختمان داده ها و ساختار های برنامه نویسی می تواند محلی بودن مراجعات را افزایش دهد و نرخ خطای صفحه و تعداد صفحات موجود در مجموعۀ کاری کاهش دهد .

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

اسلاید 97: 2497فصل دهم : حافظه مجازی6-8-10 قفل شدنوقتی از صفحه بندی درخواستی استفاده می گردد ، نیاز به این است که بعضی از صفحات در حافظه قفل شوند .یکی از این وضعیت ها وقتی رخ می دهد که عمل I/O از حافظه مجازی کاربر و یا در آن صورت گیرد . I/O معمولا توسط پردازنده I/O صورت می گیرد . به عنوان مثال تعداد بایت هایی که باید انتقال یابد و آدرس حافظه میانگیر ، به کنترل کننده نوار داده می شود.وقتی عمل انتقال کامل شد ، وقفه ای به CPU ارسال می شود .

اسلاید 98: 2498فصل دهم : حافظه مجازیمیانگیرگرداننده دیسکنموداری که نشان می دهد چرا قابهایی که برای I/O مورد استفاده قرار می گیرند باید در حافظه باشند

اسلاید 99: 99فصل دهم : حافظه مجازیباید مطمئن شویم که فرآیندی درخواست I/O نمی کند تا مجبور شود در صف دستگاه I/O قرار گیرد .چراکه به هر حال CPU به این فرآیند ها تخصیصی می یابد و این فرآیند ها موجب خطای صفحه می شوند .دوراه حل برای حل این مسئله وجود دارد :هیچ عمل I/O در حافظه صورت نگیرد ، بلکه داده ها همیشه بین حافظه ی سیستم و حافظه ی کاربر کپی شوند . برای نوشتن بلوکی بروی صفحه ، ابتدا آن را در حافظه سیستم کپی می کنیم و سپس آنرا بروی نوار می نویسیم .این عمل کپی ممکن است سربار نا معقولی را ایجاد کند .راه حل دیگر این است که صفحات در حافظه قفل شوند : به هر قاب یک بیت قفل نسبت داده می شود و اگر قابی قفل باشد ،نمی تواند برای جایگزینی انتخاب گردد .در این روش ، برای نوشتن بلوکی بروی نوار ، صفحاتی را که حاوی آن بلوک هستند در حافظه قفل می کنیم .

اسلاید 100: 100فصل دهم : حافظه مجازی7-8-10 پردازش بی درنگیک فرآیند یا بند بی درنگ انتظار دارد که با کمترین تاخیر CPU را در اختیار گیرد و اجرا شود .حافظۀ مجازی میتواند تاخیر های زیا دی را برای این فرآیند اجاد نماید (هنگام انتقال صفحات به حافظه ) .بدین ترتیب ، سیستم های بی درنگ فاقد حافظۀ مجازی اند .