1
سیستم عامل
Operating Systems
مهندس نیک فرجام
دانشگاه پیام نور واحد بیرجند
دانشگاه آزاد اسلامی واحد بیرجند
www.prozhe.com
2
فصل هفتم:
مدیریت حافظه
3
مباحث این فصل:
نیازهای مدیریت حافظه
جابجایی، حفاظت، اشتراک، سازمان منطقی، سازمان فیزیکی
بخش بندی حافظه
بخش بندی ایستا
بخش بندی پویا
سیستم رقابتی
جابجایی
صفحه بندی
قطعه بندی
سوالات دوره ای
4
مدیریت حافظه:
در یک سیستم تک برنامه ای حافظه به دو بخش تقسیم می شود:
یک بخش برای سیستم عامل (ناظر، مقیم، هسته)
یک بخش برای برنامه در حال اجرای کاربر
در یک سیستم چند برنامه ای بخش کاربر باید تقسیم بندی شود تا چندین برنامه را همزمان در خود جای دهد.
وظیفه تقسیم بندی حافظه به زیر بخشها به صورت پویا و توسط سیستم عامل صورت میگیرد و به این عمل مدیریت حافظه میگویند.
حافظه باید به گونه ای تخصیص یابد که فرایندهای آماده بیشتری در آن مجتمع شوند.
5
نیازمندی های مدیریت حافظه:
جابجایی
برنامه نویس نمی داند برنامه هنگام اجرا در کجای حافظه ذخیره میشود.
هنگام اجرای برنامه ممکن است برنامه به دیسک منتقل شود و دوباره در مکان دیگری از حافظه قرار گیرد.
ارجاعهای به حافظه باید به آدرسهای فیزیکی که منعکس کننده مکان فعلی برنامه در حافظه اند ترجمه شوند.
6
نمایی از نیازهای آدرس دهی فرایند:
7
نیازمندی های مدیریت حافظه:
حفاظت
فرایندها نباید بدون اجازه قادر به مراجعه به اطلاعات سایر فرایندها باشند
به دلایل زیر بررسی آدرسهای فیزیکی در زمان ترجمه غیر ممکن است:
مکان برنامه در حافظه اصلی در زمان ترجمه مشخص نیست.
اکثر زبانهای برنامه سازی محاسبه پویای آدرس در زمان اجرا (مثل محاسبه شاخص یک آرایه یا اشاره گر به یک ساختمان داده ) را اجازه میدهند.
یک فرایند کاربر نمیتواند به هیچ بخش سیستم عامل اعم از برنامه یا داده دسترسی داشته یاشد.
نیازهای حفاظتی باید توسط پردازنده (سخت افزار) برآورده شود نه توسط سیستم عامل (نرم افزار).
8
نیازمندی های مدیریت حافظه:
اشتراک:
اشتراک امکان دسترسی چندین فرایند به یک بخش یکسان از حافظه را میدهد.
اگر چند فرایند در حال اجرای یک برنامه هستند، به جای اینکه هر فرایند کپی جداگانه ای از برنامه داشته باشد بهتر است همه فرایندها به یک کپی از برنامه دسترسی داشته باشند.
9
نیازمندی های مدیریت حافظه:
سازمان منطقی:
اکثر برنامه ها به صورت مولفه ای سازمان یافته اند.
مزایای کار کردن با مولفه ها:
هر مولفه را میتوان به طور مستقل نوشت و ترجمه کرد.
با یک سربار مختصر مراتب مختلف حفاظتی (فقط خواندنی، فقط اجرایی) میتواند به مولفه های مختلف نسبت داده شود.
اشتراک مولفه ها بین فرایندها
10
نیازمندی های مدیریت حافظه:
سازمان فیزیکی:
ممکن است حافظه موجود، برای یک برنامه و داده های آن کافی نباشد. در این صورت از روی هم گذاری استفاده میشود.
روی هم گذاری اجازه میدهد یک ناحیه از حافظه به چندین مولفه تخصیص یابد
در یک محیط چندبرنامگی، برنامه ساز در زمان نوشتن برنامه نمیداند چه مقدار از فضا در دسترس است و آن فضا کجاست.
11
بخش بندی ایستا:
در اغلب طرحهای مدیریت حافظه سیستم عامل، بخش ثابتی از حافظه را اشغال میکند و بقیه برای استفاده فرایندها است.
در این روش بخش مربوط به فرایند ها به چندین بخش با طول ثابت تقسیم میشود.
هر فرایندی که اندازه آن کمتر یا مساوی اندازه بخش باشد میتواند داخل هر بخش موجود بار شود.
اگر همه بخش ها پر باشد، و هیچ فرایند مقیمی در حال آماده یا اجرا نباشد، سیستم عامل میتواند فرایند را به خارج مبادله کند.
12
بخش بندی ایستا:
معایب بخش بندی طول ثابت:
ممکن است یک برنامه در یک بخش جا نشود، در این صورت برنامه نویس باید از روی هم گذاری استفاده کند.
استفاده ناکارمد از حافظه اصلی حافظه اصلی : هر برنامه صرف نظر از کوچکی آن یک بخش کامل را اشغال میکند به این پدیده پراکندگی داخلی میگویند.
13
بخش بندی ایستا:
بخش بندی طول ثابت بر اساس اندازه بخشها دو نوع است:
بخشهای مساوی
بخش های نامساوی
14
الگوریتم جاگذاری بخش بندی ایستا:
بخشهای مساوی:
بدلیل مساوی بودن تمام بخشها، مهم نیست کدام بخش استفاده شود.
بخش های نامساوی:
میتوان هر فرایند را در کوچکترین بخشی که در آن جا میشود قرار داد. در این صورت باید از صف زمانبندی استفاده شود.
برای هر بخش یک صف: حداقل هدر رفتن حافظه داخل هر بخش
یک صف برای همه بخشها:
15
تخصیص حافظه برای بخش بندی ایستا:
16
مثالی برای درک تکه تکه شدن داخلی:
8M
P3 : 8M
8M
P2 : 1M
8M
P1 : 5M
سیستم عامل
8M
پراکندگی داخلی
پراکندگی داخلی
7 /
3M
17
بخش بندی پویا:
بخشها دارای طول و تعداد متغیر هستند.
حافظه تخصیص یافته به هر فرایند، دقیقاً برابر میزان نیاز فرایند است.
پس از تخصیص و آزاد سازی های مکرر حفره هایی در حافظه پدید می آیند که پراکندگی خارجی نامیده میشوند.
فشرده سازی: معمولا برای مقابله با پراکندگی خارجی، سیستم عامل فرایند ها را انتقال میدهد تا کنار یکدیگر قرار گیرند و تمام حافظه آزاد در یک بلوک قرار گیرد.
18
مثالی برای درک پراکندگی خارجی:
سیستم عامل
8M
56M
در ابتدا سیستم عامل 8M فضا اشغال میکند و 56Mفضای آزاد برای تخصیص به فرایند ها وجود دارد.
فرایند1، 20M فضا اشغال میکند و 36M فضای آزاد باقی میماند.
فرایند P1
20M
36M
فرایند2، 14M فضا اشغال میکند و 22M فضای آزاد باقی میماند.
فرایند P2
14M
22M
فرایند3، 18M فضا اشغال میکند و 4M فضای آزاد باقی میماند.
فرایند P3
18M
4M
Press Enter
19
مثالی برای درک پراکندگی خارجی:
سیستم عامل
8M
فرایند P1
20M
فرایند P2
14M
فرایند P3
18M
4M
فرایند2،حذف میشود و 14M فضا آزاد میکند.
فرایند4، 8M فضا اشغال میکند و در مکان قبلی فرایند2 قرار میگیرد و 6M فضای آزاد باقی میماند.
فرایند P4
8M
6M
فرایند1، حذف میشود و 20M فضا آزاد میکند.
فرایند2، 14M فضا اشغال میکند و در مکان قبلی فرایند1 قرار میگیرد 6M فضای آزاد باقی میماند.
فرایند P2
14M
6M
پراکندگی خارجی
پراکندگی خارجی
پراکندگی خارجی
Press Enter
20
الگوریتم جاگذاری بخش بندی پویا:
اگر چند بلوک آزاد وجود داشته باشد سیستم عامل باید تصمیم بگیرد کدام بلوک آزاد را تخصیص دهد.
3 الگوریتم جایگذاری وجود دارد:
بهترین برازش
اولین برازش
در پی برازش
21
الگوریتم جاگذاری بخش بندی پویا:
بهترین برازش:
کوچکترین بلوکی را که فرایند در آن جا میشود انتخاب میکند.
بیشترین هزینه اجرا و بدترین کارایی را دارد.
از آنجا که کوچکترین بلوک به فرایند اختصاص میابد، کمترین پراکندگی را بوجود می آورد.
اما معمولاً فضای باقیمانده 100% پراکندگی است، چرا که خیلی کوچک است، بنابراین فشرده سازی بیشتر باید انجام شود.
22
الگوریتم جاگذاری بخش بندی پویا:
اولین برازش:
حافظه را از ابتدا مرور میکند و اولین بلوک آزاد و کافی را به فرایند اختصاص میدهد.
ساده ترین، سریعترین و بهترین الگوریتم است.
ممکن است قسمت ابتدایی حافظه را از تکه های کوچک انباشته کند که هر بار باید جستجو شوند.
23
الگوریتم جاگذاری بخش بندی پویا:
در پی برازش:
حافظه را از محل آخرین جایابی به بعد مرور میکند. و اولین بلوک با اندازه کافی را انتخاب میکند.
معمولاً به تخصیص یک بلوک آزاد در انتهای حافظه (جایی که بلوک های بزرگتری پیدا میشوند) می انجامد.
بلوکهای بزرگ حافظه سریعاً به بلوکهای کوچکتر تقسیم میشوند.
فشرده سازی در این الگوریتم با بسامد بیشتری انجام میشود.
24
پیکر بندی حافظه قبل و بعد تخصیص یک بلو 16 مگا بایتی
14M
36M
18M
22M
12M
8M
آخرین
تخصیص
اولین برازش
بهترین برازش
6M
2M
در پی برازش
20M
بلوک آزاد
بلوک تخصیص یافته
25
سیستم رفاقتی:
در یک سیستم رفاقتی بلوک های حافظه بصورت زیر هستند:
مراحل تقسیم تا زمانی که بلوکی با اندازه بزرگتر یا مساوی به فرایند تخصیص یابد تکرار میشود.
26
سیستم رفاقتی:
27
جابجایی:
زمانی که یک برنامه در حافظه بار میشود محلهای واقعی حافظه تخصیص یافته به برنامه تعیین میشوند.
یک برنامه ممکن است در طول اجرا بخش های مختلفی از حافظه و بنابراین مکان های واقعی مختلفی از حافظه را اشغال کند.
فشرده سازی موجب انتقال بخشهای فرایند میشود و این به معنای اشغال کردن محل های واقعی مختلفی از حافظه در طول اجراست.
28
انواع آدرس:
منطقی:
یک مراجعه به حافظه مستقل از اختصاص داده جاری به حافظه است.
برای دسترسی به حافظه آدرس منطقی باید به آدرس فیزیکی ترجمه شود.
نسبی:
آدرس به صورت مکان نسبی به یک نقطه معلوم ( مثلاً ابتدای برنامه ) بیان میشود.
فیزیکی:
آدرس های وقعی یا مطلق در حافظه اصلی
29
حمایت سخت افزاری برای جابجایی:
برای ترجمه آدرس های نسبی به آدرس های فیزیکی حافظه اصلی در زمان اجرای دستورالعمل حاوی مراجعه راهکار های سخت افزاری مورد نیاز است.
30
ثبات های بکار رفته حین اجرای دستورالعمل:
ثبات پایه:
آدرس شروع فرایند
ثبات حد:
آدرس پایان فرایند
این ثباتها هنگام بار شدن فرایند به حافظه اصلی یا مبادله تصویر فرایند به داخل مقدار دهی میشوند.
31
ثبات های بکار رفته حین اجرای دستورالعمل:
مقدار ثبات پایه به آدرس نسبی افزوده میشود تا یک آدرس مطلق بدست آید.
آدرس بدست آمده با مقدار ثبات حد مقایسه میشود.
اگر در محدوده باشد، اجرای دستورالعمل ادامه میابد. در غیر این صورت خطایی به سیستم عامل داده میشود.
32
صفحه بندی:
بخش های حافظه به قطعات کوچکی با اندازه ثابت تقسیم میشوند. برنامه ها نیز به قطعاتی با همان اندازه تقسیم میشوند.
قطعات یک برنامه، صفحه نامیده میشوند و قطعات مربوط به حافظه قاب نام دارند.
سیستم عامل برای هر فرایند یک جدول صفحه نگه می دارد.
محل قابی که هر صفحه از فرایند را در بر دارد، نگه می دارد.
هر آدرس منطقی شامل شماره صفحه و یک انحراف در صفحه است.
33
مثالی از اختصاص قاب های آزاد به فرایندها:
وجود پانزده
قاب خالی
Press Enter
فرایند A با 4
صفحه بار میشود
A.1
A.2
A.3
A.0
فرایند B با 3
صفحه بار میشود
B.0
B.1
B.2
فرایند C با 4
صفحه بار میشود
C.0
C.1
C.2
C.3
فرایند B معلق شده
و
به دیسک انتقال میابد
پس از مدتی تمام
فرایندها معلق میشوند و
نیاز است سیستم عامل
فرایند D رابا 5 صفحه
بار کند!!!!
5 صفحه متوالی وجود ندارد
اما با مفهوم آدرس منطقی
(شماره قاب و انحراف
داخل صفحه) این مساله حل میشود.
D.1
D.2
D.3
D.0
D.4
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
34
A.1
A.2
A.3
A.0
B.0
B.1
B.2
C.0
C.1
C.2
C.3
D.1
D.2
D.3
D.0
D.4
Press Enter
پس از مدتی تمام
فرایندها معلق میشوند و
نیاز است سیستم عامل
فرایند D رابا 5 صفحه
بار کند!!!!
5 صفحه متوالی وجود ندارد
اما با مفهوم آدرس منطقی
(شماره قاب و انحراف
داخل صفحه) این مساله حل میشود.
مثالی از اختصاص قاب های آزاد به فرایندها:
—–
9
—–
8
7
12
6
5
4
11
14
13
—–
10
2
1
0
3
فهرست
قابهای خالی
جدول صفحه
فرایند D
جدول صفحه
فرایند C
جدول صفحه
فرایند B
جدول صفحه
فرایندA
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
35
قطعه بندی:
لزومی ندارد همه قطعات تمام برنامه ها دارای اندازه یکسان باشند
حداکثری برای طول قطعه وجود دارد.
آدرس منطقی شامل دو بخش است: شماره قطعه و انحراف داخل قطعه
ازآنجایی که قطعه ها دارای طول متغیراند قطعه بندی مانند بخشبندی پویا است.
36
آدرسهای منطقی :
37
ترجمه آدرس منطقی به فیزیکی در صفحه بندی:
38
ترجمه آدرس منطقی به فیزیکی در قطعه بندی:
39
سوال و پاسخ :
? ? ? ? ?
40
سوال اول:
مدیریت حافظه قصد دارد چه نوع نیاز هایی را برآورده سازد؟
جابجایی
حفاطت
اشتراک
سازمان منطقی
سازمان فیزیکی
41
سوال دوم:
به چه دلیل قابلیت جابجایی فرایند ها مفید است؟
برنامه نویس نمی داند برنامه هنگام اجرا در کجای حافظه ذخیره میشود.
هنگام اجرای برنامه ممکن است برنامه به دیسک منتقل شود و دوباره در مکان دیگری از حافظه قرار گیرد.
42
سوال سوم:
چرا نمیتوان حفاظت حافظه را در زمان ترجمه انجام داد؟
مکان برنامه در حافظه اصلی در زمان ترجمه مشخص نیست.
اکثر زبانهای برنامه سازی محاسبه پویای آدرس در زمان اجرا (مثل محاسبه شاخص یک آرایه یا اشاره گر به یک ساختمان داده ) را اجازه میدهند.
43
سوال چهارم:
دلایل مجاز بودن یک یا دو فرایند جهت دسترسی به بخشهای مشخصی از حافظه را بیان کنید.
اگر تعدادی فرایند یک برنامه را اجرا میکنند، به جای اینکه هر فرایند کپی جداگانه ای از برنامه داشته باشد بهتر است همه فرایند ها به یک کپی از برنامه دسترسی داشته باشند.
فرایند هایی که با همکاری یک وظیفه را جلو میبرند، ممکن است لازم باشد در دسترسی به ساختمان داده ای شریک باشند.
44
سوال پنجم:
در طرح بخش بندی ثابت مزایای کاربرد بخش های با اندازه نامساوی چیست؟
امکان این وجود دارد که دو یا چند بخش بزرگ را در کنار بخشهای دیگر داشت . بخشهای بزرگ، برنامه های بزرگتری را در خود جای میدهند.
پراکندگی داخلی کمتر میشود چرا که برنامه های کوچکتر میتوانند در بخش های کوچکتر قرار گیرند.
45
سوال ششم:
تفاوت میان پراکندگی داخلی و خارجی چیست؟
پراکندگی داخلی مربوط به اتلاف فضای داخلی در داخل بلوک ها میشود. زمانی رخ میدهد که برنامه بار شده در بلوک از فضای بلوک کوچکتر است.
پراکندگی خارجی پدیده ایست که به بخش بندی پویا مربوط میشود و از این واقعیت ناشی میشود که تعداد زیادی از فضاهای کوچک داخل حافضه اصلی در یک فضای غیر قابل استفاده انباشته میشوند.
46
سوال هفتم:
آدرس های منطقی نسبی و فیزیکی چگونه متمایز میشوند؟
یک آدرس منطقی یک ارجاع به یک محل مستقل از حافظه گمارده شده برای داده های کنونی است. یک عمل ترجمه باید آدرس فیزیکی را برای داده هایی که قرار است از حافظه دستیابی شوند ایجاد نماید.
آدرس نسبی یک نمونه خاص از آدرس منطقی است که در آن آدرس یک مکان نسبی نسبت به یک نقطه معین مثلاً ابتدای برنامه را مشخص میکند.
آدرس فیزیکی یا آدرس مطلق یک محل واقعی در حافظه اصلی میباشد.
47
سوال هشتم:
تفاوت میان صفحه و قاب چیست؟
در یک سیستم صفحه بندی برنامه ها و داده های ذخیره شده در دیسک به بلوک های با اندازه ثابت و مساوی تقسیم میشوند، که صفحه نامیده میشوند، و حافظه اصلی نیز به قطعاتی با همان اندازه تقسیم میشود که قاب نامیده میشود. دقیقاً هر قاب برای یک صفحه مناسب است.
48
سوال نهم:
تفاوت میان صفحه و قطعه چیست؟
در روش قطعه بندی، برنامه کاربر به تعدادی قطعه تقسیم میشود. لزومی ندارد اندازه قطعه ها با هم برابر باشد، گر چه حداکثری برای طول قطعه وجود دارد.