مدیریت حافظه

مدیریت حافظه

اسلاید 1: دانشگاه آزاد اسلامي قائمشهرفصل 9استاد: جناب آقای قاسمپوریبه کوشش: حدیث نبوی سودابه علیزادهالمیرا رستمیاناردیبهشت 88 خلاصه فصل نهم1

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

اسلاید 3: حافظه، آرایه بزرگی ازکلمات یا بایت ها است که هر کدام دارای رئوس می باشند. Cpu دستوری را که توسط شمارنده برنامه مشخص می شود، از حافظه مکش می کند. این دستورات ممکن است نیاز به بار کردن و ذخیره کردن در حافظه داشته باشد. مراحل اجرای یک چرخه دستور: ابتدا از حافظه مکش می شود و سپس رمزگشایی می شود پس از اینکه این دستور بر روی عملوندها اجرا شد، نتایج ممکن است در حافظه ذخیره شود. 1-9 مرور کلی3

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

اسلاید 5: اغلب سیستم ها اجازه می دهند که فرآیند کاربر در هر بخشی از حافظه فیزیکی قرار گیرد. لذا، گرچه فضای آدرس کامپیوتر از 00000شروع می شود، لازم نیست آدرس شروع فرآیند کاربر 00000باشد. این نظم، آدرس هایی را که برنامه کاربر می تواند مورد استفاده قرار دهد، تحت تاثیر قرار می دهد.1-1-9انقیاد آدرس5

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

اسلاید 7: 1-1-9انقیاد آدرسزمان بار کردنزمان اجراانقیاد دستورات و داده ها به آدرسهای حافظه در سه مرحله انجام می گیرد:7

اسلاید 8: آدرسی که توسط cpu تولید می شود، آدرس منطقی نام دارد، در حالی که آدرسی که توسط واحد حافظه مشاهده می شود آدرس فیزیکی نام دارد.الگوهای انقیاد آدرس در زمان ترجمه و در زمان بار کردن، آدرسهای فیزیکی و منطقی یکسانی را تولید می کنند. اما، الگوی انقیاد آدرس در زمان اجرا، آدرسهای فیزیکی و مختلفی را ایجاد می کنند. در این حالت، آدرس منطقی را آدرس مجازی می نامیم.2-1-9 فضای آدرس منطقی و فیزیکی8

اسلاید 9: همانطور که در شکل 2-9 آمده است الگوی واحد مدیریت حافظه(MMU) نیامند پشتیبان سخت افزاری است که کمی متفاوت از سخت افزار کامپیوتر است. در اینجا ثبات پایه به نام ثبات جابه جایی، نامیده می شود. مقدار موجود در ثبات جا به جایی، به هر آدرسی که توسط فرآیند برنامه، در هنگام ورود به حافظه ایجاد می شود، اضافه می گردد. +14000ثبات جابجاییcpuحافظهآدرس فیزیکیآدرس منطقی14346346MMU2-1-9 فضای آدرس منطقی و فیزیکی9

اسلاید 10: دو نوع آدرس وجود دارد: آدرسهای منطقی (از صفر تا max) و آدرسهای فیزیکی از(R+0) تا R+max با مقدار پایهR کاربر فقط آدرسهای منطقی را تولید می کند و فکر می کند که فرآیند در محل های صفر تا MAX اجرا می شود. برنامه کاربر آدرس های منطقی را تولید می کند و این آدرسها قبل از به کار گیری باید به آدرسهای فیزیکی نگاشت شوند.2-1-9 فضای آدرس منطقی و فیزیکینکته10

اسلاید 11: در بار کردن پویا، یک روال تا زمانی که فراخوانی نشد، بار نمی شود. تمام روالها بر روی دیسکی با فرمت قابل جابجایی ذخیره می شوند. برنامه اصلی به حافظه بار شده اجرا می شود. وقتی روالی نیاز به فراخوانی روال دیگر دارد، روال فراخوان ابتدا بررسی می کند آیا روالی که باید فراخوانی شود بار شده است یا خیر. اگر بار نشده باشد، بار کننده پیوندی قابل جا به جایی فراخوانی می شود تا روال مطلوب را به حافظه بار کند و جدولهای آدرس برنامه را بروز نمایدسپس کنترل به روال می رود.3-1-9 بار کردن پویا11

اسلاید 12: روالی که مورد استفاده واقع نمی شود، بار نخواهد شد. این الگو برای مواقعی خوب است که برای پردازش موارد نا درست، کد زیادی مورد نیاز باشد، مثل روالهای مربوط به خطاها. در این مورد،گرچه اندازه کل برنامه ممکن است بزرگ باشد، ولی بخشی از برنامه که مورد استفاده قرارمی گیرد ، ممکن است بسیار کوچک باشد.3-1-9 امتیاز بار کردن پویا12

اسلاید 13: مفهوم پیوند پویا مثل بار کردن پویا است. به جای اینکه بار کردن تا زمان اجرا به تعویق افتد، پیوند زدن به زمان اجرا موکول می شود. این ویژگی معمولا با کتابخانه های سیستم به کار گرفته می شود، مثل کتا بخانه های زیر روال زبان. بدون این قابلیت، تمام برنامه های موجود در یک سیستم باید یک کپی از کتابخانه زبان را داشته باشند یا حداقل، یک کپی از روالهایی را داشته باشند که برنامه به آنها مراجعه می کند. این کار موجب اتلاف فضای دیسک و حافظه اصلی می شود.4-1-9 پیوند پویا و کتابخانه مشترک:13

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

اسلاید 15: اگر تغییرات در کتابخانه اندک باشد، شماره نسخه تغییر نمی کند ولی اگر تغییرات زیاد باشد، شماره نسخه تغییر خواهد کرد. فقط برنامه هایی که با نسخه جدید کتابخانه ترجمه می شوند، تحت تاثیر تغییرات نا سازگار آن قرا رمی کیرند. سایر برنامه هایی که قبل از نصب کتابخانه جدید پیوند زده شده اند، با استفاده از کتابخانه قدیمی اجرا می شوند. این سیستم را کتابخانه های مشترک نیز می نامند.4-1-9 کتابخانه مشترک15

اسلاید 16: فرآیند ممکن است بزرگتر از حافظهای باشد که به آن تخصیص یافته است، بدین سان از تکنیکی به نام جایگذاری استفاده می شود. ایده این تکنیک این است که فقط دستورات و داده های که در همان زمان لازمند، در حافظه قرار گیرند. اگر به دستورات دیگری نیاز باشد، به جای دستورات قبلی، که فعلا مورد نیاز نیستند، قرار می گیرند. 5-1-9 جایگذاری16

اسلاید 17: مثال:یک اسمبر دو گذاره را در نظر بگیرید فرض کنید اندازه این قطعات به صورت زیر است:گذر اول: 70 k ، گذر دوم: 80 k ، جدول نماد: 20 k، روالهای مشترک: 30 k دو جایگذاری را تعریف می کنیم: جایگذاری A برابر است با جدول نمادها، روالهای مشترک، و گذر اول، جایگذاری B برابر است با جدول نمادها، روالهای مشترک و گذر دوم.یک گرداننده جایگذاری برای انجام جایگذاری با ظرفیت 10 K در نظر می کیریم و با جایگذاری A در حافظه شروع می کنیم. وقتی گذر اول تمام شد، به گرداننده جایگذاری می رویم که جایگذاری B را به حافظه می آورد و به جای جایگذاری A قرار می دهد و کنترل را به گذر دوم منتقل می کند. جایگذاری A فقط به 120K نیاز دارد، در حالی که جایگذاری B به 130 K نیاز دارد ( شکل 3-9). 5-1-9 جایگذاریگذر اول70k80k10k30k20k جدول نمادهاروال های مشترکگرداننده جایگداریگذر دوم17

اسلاید 18: فرآیند می تواند موقتا از حافظه اصلی به حافظه پشتیبان برود و بعدا به حافظه برگردد و به اجرایش ادامه دهد. این عمل را مبادله گویند. به عنوان مثال یک محیط چند برنامه ای را با الگوریتم زمانبندی RR در نظر بگیرید. وقتی یک کوانتوم زمانی به سپری می شود، مدیر حافظه فرآیندی را که به پایان رسید از حافظه خارج می کند و فرآیند دیگری را به فضای حافظه ای که فعلا آزاد شده است منتقل می کند (شکل 4-9) . 2-9 مبادلهسیستم عاملفضای کاربرحافظه اصلیحافظه پشتیبانفرآیند p1فرآیندp2مبادله به داخل 2مبادله به خارج 1شکل مبادله دو فرآیند با استفاده از دیسک به عنوان حافظه پشتیبان18

اسلاید 19: در این فاصله، زمانبند CPU یک برهه زمانی را به فرآیند دیگر موجود در حافظه تخصیص می دهد. وقتی هر فرآیندی کوانتوم زمانی خودش را تمام می کند، با فرآیند دیگری مبادله می شود. در حالت ایده آل، مدیر حافظه می تواند فرآیند ها را آنقذر سریع مبادله کند که هر وقت زمانبند CPU می خواهد CPU را دوباره زمانبندی کند، فرآیندهایی در حافظه وجود داشته باشد. کوانتوم زمانی نیز باید به اندازه کافی بزرگ باشد تا در بین مبادله ها، محاسبات معقولی صورت گیرد. 2-9 مبادله19

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

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

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

اسلاید 23: 3-9 تخصیص همجوارفرآیند های کاربر23حافظهسیستم عامل مقیمحافظه معمولا به دو قسمت تقسیم می شود:

اسلاید 24: سیستم عامل را می توان در قسمت بالایی حافظه یا در قسمت پایینی حافظه قرار داد. عامل مهمی که در این تقسیم گیری نقش دارد، محل بردار وقفه است. چون معمولا بردار وقفه در حافظه پایین قرار دارد، سیستم عامل نیز در حافظه پایین قرار می گیرد.3-9 تخصیص همجوار24

اسلاید 25: منظور از حفاظت از حافظه، حفاظت سیستم عامل از فرآیند های کاربر و حفاظت فرآیندهای کاربر از یکدیگر است. این حفاظت با استفاده از ثبات جابه جایی و ثبات حد فراهم می شود. با ثباتهای جا به جایی وحد هر آدرس منطقی باید کمتر از ثبات حد باشد، MMU آدرس منطقی را با افزودن مقدار موجود در ثبات جا به جایی به آن، به طور پویا به آدرس فیزیکی نگاشت می کند. این آدرس نگاشت شده به حافظه فرستاده می شود(شکل 5-9) .حفاظت از حافظهcpu<+آدرس منطقیثبات حدثبات جابجاییبلیآدرس فیزیکیخیرحافظهتله: خطای آدرس دهیشکل 5-9 پشتیبانی سخت افزاری برای ثباتهای جابجایی و حد25

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

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

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

اسلاید 29: راهبردهایی برای انتخاب یک حفره آزاد از مجموعه ای از حفره ها:29

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

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

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

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

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

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

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

اسلاید 37: 1-4-9 روش انجام کار در صفحه بندیحافظه فیزیکی به بلوکهایی با اندازه ثابت به نام قاب تقسیم می شود. حافظه منطقی نیز به بلوکهایی با اندازه های یکسان به نام صفحه تقسیم می شود. وقتی فرآیندی می خواهد اجرا شود، صفحات آن از حافظه پشتیبان به قابهای حافظه آزاد بار می شود. حافظه پشتیبان به بلوکهایی با طول ثابت تقسیم می شود که به اندازه قابهای حافظه است. پشتیبانی سخت افزاری برای صفحه بندی در شکل 6-9آمده است.حافظه فیزیکیآدرس فیزیکیآدرس منطقیpdcpufdجدول صفحهfpff000…0000f111…1111شکل 6-9 سخت افزار صفحه بندی37

اسلاید 38: هر آدرسی که توسط CPU تولید می شودبه دو بخش تقسیم می گردد: شماره صفحهP)) و آفست صفحه (d) . شماره صفحه به عنوان اندیسی برای جدول صفحه به کار می رود. جدول صفحه حاوی آدرس پایه هر صفحه در حافظه فیزیکی است. این آدرس پایه، با آفست صفحه ترکیب می شود تا فضای آدرس فیزیکی تولید شود و به واحد حافظه3ارسال گردد. مدل صفحه بندی حافظه در شکل 7-9 آمده است.1-4-9 روش انجام کار در صفحه بندی01234567صفحه 0صفحه 2صفحه 3صفحه 1صفحه 0صفحه 1صفحه 2صفحه 30123جدول صفحهحافظه منطقیحافظه فیزیکیشماره قابشکل 7-9 مدل صفحه بندی حافظه منطقی و فیزیکی38

اسلاید 39: اندازه صفحه توان 2 است، ترجمه آدرس منطقی به شماره صفحه و آفست صفحه، آسا ن است. اگر فضای منطقی 2m باشدو اندازه صفحه برابر با 2n واحد آدرس دهی باشد، آنگاه m-n بیت با ارزش آدرس منظقی، شماره صفحه و n بیت کم ارزش، آفست صفحه را تعیین می کند. بنابر این آدرس منطقی به صورت زیر است:1-4-9 روش انجام کار در صفحه بندیشماره صفحهآفست صفحهpdm-nn39

اسلاید 40: در حافظه شکل 8-9 با استفاده از صفحه 4 بایتی و حافظه فیزیکی 32 بایتی (8صفحه) نشان می دهیم که حافظه از دیدگاه کاربر چگونه به حافظه فیزیکی نگاشت می شود. وقتی از الگوی صفحه بندی استفاده می کنیم تکه تکه شدن خارجی وجود ندارد، زیرا هر قاب آزاد می تواند به فرآیندی که به آن نیاز دارد تخصیص یابد. اما ممکن است تکه تکه شدن داخلی به وجود آید. توجه کنید که قابها به عنوان واحد های حافظه تخصیص می یابند. اگر حافظه مورد نیاز فرآیندی ر محدوده یک صفحه نباشد، آخرین قابی که تخصیص یافت ممکن است کاملا پر نباشد.1-4-9 روش انجام کار در صفحه بندی40

اسلاید 41: abCd01234567efgh891011ijkl12131415Mnop01235612حافظه منطقیجدول صفحهijklMnop048121620 abCdefgh2428حافظه فیزیکیشکل 8-9 نمونه ای از صفحه بندی برای 32 بایت حافظه و صفحه 4 بایتی41

اسلاید 42: وقتی فرآیندی بخواهد اجرا شود، اندازه آن بر حسب صفحات سنجیده می شود. هر صفحه از فرآیند به یک قاب نیاز دارد. بنابراین، اگر فرآیندی به n صفحه نیاز داشته باشد، حداقل باید n قاب آزاد در حافظه موجود باشد اگر n قاب آزاد موجود باشد، به این فرآیند تخصیص می یابد. اولین صفحه فرآیند به یکی از این قابهای تخصیص یافته بار می شود و شماره آن قاب در جدول صفحه مر بوط به این فرآیند قرار می گیرد. صفحه بعدی به قاب دیگری منتقل می شود و شماره این قاب نیز در جدول صفحه قرار می گیرد و این روند ادامه می یابد( شکل9-9).1-4-9 روش انجام کار در صفحه بندی42

اسلاید 43: صفحه 0 صفحه 1صفحه 2صفحه 3لیست قابهای آزاد1413182015131415161718192021صفحه 0 صفحه 1صفحه 2صفحه 3لیست قابهای آزاد15131415161718192021012314131820صفحه 1صفحه 0صفحه 2صفحه 3جدول صفحه فرآیند جدیدفرآیند جدید(ب)(الف)1-4-9 روش انجام کار در صفحه بندی43

اسلاید 44: 2-4-9 پشتیبانی سخت افزاری از صفحه بندیهر سیستم عامل برای ذخیره جدول صفحات به ازای هر فرآیند یک جدول صفحه ایجاد می کند.یک اشاره گربه جدول صفحه بهمراه سایر مقادیر ثبات در بلوک کنترل فرآیند ذخیره می شود.وقتی به توزیع کننده گفته می شود فرآیندی را آغاز کند،باید ثباتهای کاربر را دوباره بار کند و با استفاده از جدول صفحه کاربر،مقادیر جدول صفحه سخت افزار را تعریف نماید.44

اسلاید 45: پیاده سازی جدول صفحهدر روش اول جدول صفحه بصورت مجموعه ای از ثباتها پیاده سازی می گردد. توزیع کننده cpu این ثباتها را همانند ثباتهای دیگر دوباره بار می کند.مانند: DEC PDP-11 آدرس: 16 بیتیاندازه صفحه:8K 45

اسلاید 46: در روش دوم جدول صفحه در حافظه اصلی نگهداری می شود و یک ثبات پایه جدول صفحه(PTBR) به جدول صفحه اشاره می کند. تغییر جدولهای صفحه مستلزم تغییر یک ثبات است و در نتیجه زمان تعویض بستر کاهش می یابد.مشکل این روش زمان لازم برای دستیابی به محل حافظه کاربر است که برای دستیابی به یک بایت دوبار باید به حافظه دستیابی داشت. بنابراین دستیابی به حافظه به اندازه ضریب 2 کند می شود. پیاده سازی جدول صفحه46

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

اسلاید 48: TLB به این صورت با جدول صفحه بکار گرفته می شود:شکل 10-9fآدرس منطقیشماره صفحهشماره قابTLBشکست TLBاصابتTLB حافظه فیزیکیآدرس فیزیکیجدول صفحهfdpdcpupپیاده سازی جدول صفحه48

اسلاید 49: بعضی از TLBها شناسه های فضای آدرس(ASID) را در هر ورودی TLB ذخیره می کنند. هر ASID فرآیند منحصر به فردی را مشخص می کند و برای حفاظت فضای آدرس آن فرآیند بکار می آید. همچنین به TLB اجازه می دهد که همزمان برای فرآیندهای مختلف، ورودیهایی را داشته باشد.پیاده سازی جدول صفحه49

اسلاید 50: نسبت اصابتدرصد تعداد دفعاتی که شماره صفحه در ثباتهای انجمنی یافت می شود،نسبت اصابت نام دارد. اگر نسبت اصابت 80درصد باشد یعنی 80درصد از تعداد دفعاتی که به TLB مراجعه کردیم،شماره صفحه پیدا شده است.50

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

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

اسلاید 53: 4-4-9 ساختار جدول صفحه53

اسلاید 54: 1-4-4-9 صفحه بندی سلسله مراتبیبرای اینکه جدول صفحه بطور همجوار در حافظه اصلی قرار نگیرد باید جدول صفحه به فضاهای کوچکتری تقسیم شود: الگوی صفحه بندی دو سطحیالگوی صفحه بندی چهار سطحی54

اسلاید 55: در این روش خود جدول نیز صفحه بندی می شود.شکل 12-9 الگوی صفحه بندی دو سطحی...صفحه جدول صفحه929900............1500100708........................ 01100500708900929جدول صقحه بیرونیجدول صفحهحافظه55

اسلاید 56: آدرس منطقی به صورت زیر است: P1 P2 dشماره صفحه آفست صفحه101012 چون ترجمه آدرس از صفحه بیرونی به طرف داخل کار می کند،این روش را جدول صفحه نگاشت به جلو می نامند.شکل 13-9 الگوی صفحه بندی دو سطحی56

اسلاید 57: الگوی صفحه بندی دو سطحیآدرس منطقیp2جدول صفحه بیرونیصفخه جدول صفحهp1p2dp1p357

اسلاید 58: در سیستمی با فضای آدرس منطقی 64 بیتی،الگوی صفحه بندی دو سطحی مناسب نیست. یک روش برای پرهیز از جدول بزرگ این است که جدول صفحه بیرونی به قطعات کوچکتری تقسیم شود. همچنین می توان جدول صفحه بیرونی را صفحه بندی کرد تا الگوی صفحه بندی سه سطحی بوجود آید:p1 p2 p3 dصفحه بیرونی دومصفحه بیرونیصفحه درونی آفست 3210 10 12 الگوی صفحه بندی دو سطحی58

اسلاید 59: در این الگو جدول صفحه بیرونی سطح دوم، صفحه بندی می شود. معماری سیستم SPARC با آدرس دهی 32 بیتی از الگوی سه سطحی استفاده می کند،در حالیکه معماری موتورولا 68030 سی و دو بیتی،از الگوی صفحه بندی چهار سطحی استفاده می کند.الگوی صفحه بندی چهار سطحی59

اسلاید 60: 2-4-4-9 جدولهای صفحه درهم سازی شدهدر این روش،یک مقدار درهم سازی بعنوان شماره صفحه مجازی منظور می شود. هر ورودی حاوی یک لیست پیوندی از عناصری است که به محل یکسانی درهم سازی می شوند.هر عنصر شامل سه فیلد است:شماره صفحه مجازیمقدار قاب صفحه نگاشت شدهاشاره گری به عنصر بعدی در لیست پیوندی60

اسلاید 61: روش کار این الگوریتم در شکل زیر نشان داده شده است:2-4-4-9 جدولهای صفحه درهم سازی شدهشکل 14-9qsqr …حافظه فیزیکیآدرس فیزیکیآدرس منطقیتابع درهم سازیجدول درهم سازی61

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

اسلاید 63: 3-4-4-9 جدول صفحه معکوسیکی از معایب جدول طبیعی وجود میلیونها ورودی برای هر جدول صفحه است که مقدار زیادی از حافظه فیزیکی را مصرف می کنند. برای حل این مشکل می توان از جدول صفحه معکوس استفاده کرد.جدول صفحه معکوس به ازای هر قاب حافظه یک ورودی دارد که هر ورودی متشکل ازآدرس مجازی صفحه ای است که در آن محل واقعی حافظه ذخیره شده است.63

اسلاید 64: عملکرد جدول صفحه معکوسشکل 15-9حافظه فیزیکیآدرس فیزیکیآدرس منطقیcpupidpdipidpdجستجوجدول صفحهi64

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

اسلاید 66: 5-4-9 صفحات مشترکاستفاده ازکد مشترک در محیط اشتراک زمانی مناسب است. اگر کد برنامه چند دخولی باشد می تواند به طور اشتراکی مورد استفاده واقع شود.شکل 16-9ویراستار 1ویراستار 2ویراستار3داده 1فرآیند P1ویراستار 1ویراستار 2ویراستار3داده 3فرآیند P3 ویراستار 1ویراستار 2ویراستار3داده 2فرآیند P2 3461جدول صفحه برای P13462جدول صفحه برای P33467جدول صفحه برای P2012345678910داده 1داده2ویراستار1ویراستار2ویراستار3داده266

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

اسلاید 68: 5-9 قطعه بندیالگوی صفحه بندی نمی تواند حافظه فیزیکی را از دیدگاه کاربر نسبت به حافظه تفکیک کند. دیدگاه کاربر، به آدرس فیزیکی نگاشت می شود که این نگاشت تفاوت بین حافظه منطقی و فیزیکی را ممکن می سازد. 68

اسلاید 69: 1-5-9 روش انجام کار در قطعه بندیکاربر حافظه را بصورت یک آرایه خطی از بایتها نمی داند بلکه حافظه را مجموعه ای از قطعات طول متغیر در نظر می گیرد که هیچ ترتیب خاصی ندارند. شکل 17-9زیر روالپشتهجدول نمادSQRTحافظه اصلیفضای آدرس منطقی69

اسلاید 70: قطعه بندی یک الگوی مدیریت حافظه است که دیدگاه کاربر نسبت به حافظه را پشتیبانی می کند.فضای آدرس منطقی مجموعه ای از قطعات است.کاربر هر آدرس را با دو کمیت مشخص می کند: < نام قطعه و یک آفست>برای سهولت قطعات شماره گذاری می شوند و از طریق این شماره مراجعه می شوند. بنابر این آدرس منطقی شامل دوتایی است: <آفست و شماره صفحه> 1-5-9 روش انجام کار در قطعه بندی70

اسلاید 71: 2-5-9 سخت افزارآدرسهای دو بعدی کاربر به آدرسهای فیزیکی یک بعدی توسط جدول قطعه نگاشت می شود.پایه قطعه= آدرس شروع حافظه فیزیکی مکان قطعهحد قطعه= طول قطعه71

اسلاید 72: کاربرد جدول قطعهS : شماره قطعهd : آفست قطعه( که باید بین صفر و حد قطعه باشد)تله: خطای آدرس دهیخیر<CPUSdحدپایهsجدول قطعه+حافظه فیزیکیبلی72

اسلاید 73: زیر روالپشتهجدول نمادSQRTحافظه اصلیفضای آدرس منطقیقطعه0 قطعه 1قطعه 3قطعه 2 قطعه 4 01234حدپایه10004004001100100014006300430032004700جدول قطعهقطعه 0قطعه 3قطعه 2قطعه 4قطعه 114002400320043004700570063006700 نمونه ای از قطعه بندی73

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

اسلاید 75: هر فرآیند دارای یک جدول قطعه است. قطعات وقتی به اشتراک گذاشته می شوند که ورودیهای جداول قطعه مربوط به دو فرآیند مختلف، به یک محل فیزیکی اشاره نمایند. شکل 20-93-5-9 حفاظت و اشتراک کد و داده هاویراستار داده1قطعه 0قطعه 1حافظه منطقی فرآیندp1ویراستار داده 2قطعه 0قطعه 1حافظه منطقی فرآیندp2 حدپایه2528644254306268348جدول قطعه فرآیند p1012528688504306290003جدول قطعه فرآیند p101حدپایهویراستارداده 1داده 2 4306268348727739000398553حافظه فیزیکی75

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

اسلاید 77: 6-9 قطعه بندی با صفحه بندیدر جدول توصیفگر محلی(LDT)فضای آدرس منطقی یک فرآینددر جدول توصیفگر عمومی(GDT)77

اسلاید 78: آدرس منطقی بصورت جفت(آفست و انتخابگر)است: S g p1312 s شماره قطعه است، g معلوم می کند که آیا قعه در GDT است یا در LDT و p مربوط به حفاظت است. آفست یک عدد 32 بیتی و انتخابگر یک عدد 16 بیتی است. 6-9 قطعه بندی با صفحه بندی78

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