آموزش سیستم عامل – مدیریت حافظه – مرور مفاهیم

 

یکی از وظایف سیستم عامل، مدیریت حافظه است. مدیریت حافظه اصلی و مدیریت حافظه دیسک بر عهده سیستم عامل است.

مدیریت حافظه:

۱ – تک برنامگی

۲ – چند برنامگی

 

چند برنامگی با پارتیشن ثابت

1

در این شکل سیستم عامل در قسمتی از حافظه قرار گرفته است، در شکل a باقیمانده حافظه به قسمت‌هایی ۸m تقسیم شده یعنی همه قسمت‌ها ۸m هستند، اما در شکل b همه قسمت‌ها یکسان نیستند و قسمت‌های ۲m, 4m, 6m,8m و غیره هستند.

 

معایب مدیریت حافظه به روش پارتیشن بندی ایستا

۱ – مشکل بودن تعیین تعداد و اندازه پارتیشن‌ها.

۲ – محدود بودن درجه چند برنامگی به تعداد پارتیشن‌ها.

۳ – تکه تکه شدن داخلی

 

صف

هر پارتیشن می‌تواند صف مربوط به خود را داشته باشد می‌توان یک صف مشترک برای همه پارتیشن‌ها در نظر گرفت.

 

2

 

ثبات پایه و حد

هنگامی‌که پردازنده به فرایندی داده می‌شود آدرس شروع پارتیشن در Base و طول پارتیشن در Limit قرار می‌گیرد.

اگر ثبات پایه حاوی ۱۰۰ و ثبات حد شامل ۲۰ باشد آن گاه برنامه می‌تواند به آدرس‌هایی از ۱۰۰ تا خود ۱۲۰ دستیابی داشته باشد.

برای جلوگیری از مشکل جا به جایی هر آدرس حافظه‌ای که تولید می‌شود قبل از ارسال به حافظه مقدارش به صورت خودکار با محتوای Base جمع می‌شود.

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

 

مبادله Swapping

در سیستم‌های اشتراک زمانی در گاهی اوقات نمی‌توان همه فرایندهای فعال را در حافظه اصلی جای داد و باید فرایندهای اضافی به دیسک منتقل شده و بعداً به صورت پویا به داخل حافظه آورده شوند.

در روش مبادله هر فرایند به طور کامل به حافظه اصلی آورده می‌شود و بعد از مدتی اجرا به دیسک برگردانده می‌شود (Swap in , Swap out)

مثلاً در یک محیط چند برنامه‌ای که از RR استفاده می‌کند وقتی فرایندی کوانتوم زمانی‌اش تمام می‌شود با فرایند دیگری مبادله می‌شود.

در پارتیشن بندی پویا،”تعداد، موقعیت و اندازه ” پارتیشن‌ها متفاوت است این انعطاف پذیری باعث بهبود بهره وری حافظه می‌شود.

مثال: شکل زیر نحوه عملکرد سیستمی را نشان می‌دهد که بر اساس مبادله کار می‌کند.

5

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

 

تکه تکه شدن خارجی

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

 

تشخیص بخش های آزاد حافظه

وقتی که حافظه به صورت پویا تخصیص داده می‌شود سیستم عامل باید بداند که کدام بخش حافظه در هر لحظه تخصیص داده شده و کدام بخش آزاد است.

برای این منظور دو روش وجود دارد:

۱ – مدیریت حافظه با نگاشت‌های بیتی

۲ – مدیریت حافظه با لیست‌های پیوندی

 

مدیریت حافظه با نگاشت های بیتی

حافظه به چندین واحد تخصیص تقسیم می شود .متناظر با هر واحد تخصیص یک بیت وجود دارد .اگر واحد متناظر آزاد باشد این بیت ۰ است و در صورت پر بودن ۱  است.

مثال :شکل زیر قسمتی از حافظه شامل ۵ فرایند و ۳ حفره را نشان می دهد.

مناطق هاشور خورده فضاهای خالی هستند به طور مثال ۸ بیت اول شامل پنج تا ۱ و سه تا ۰ است.

4

هرچه واحد تخصیص کوچک‌تر باشد نگاشت بیتی بزرگ‌تر خواهد بود.

اگر اندازه فرایند ضریبی از اندازه واحد تخصیص نباشد در آخرین واحد مقداری از حافظه هدر می‌رود.

برای انتقال یک فرایند به حافظه که به k واحد فضا نیاز دارد مدیر حافظه باید در نگاشت بیتی جستجو کرده و k بیت متوالی ۰ را پیدا کند که عملی زمان‌بر است.

 

مدیریت حافظه با لیست های پیوندی

یک لیست پیوندی از قطعه‌های آزاد یا تخصیص یافته حافظه تشکیل می‌شود.

فضاهای خالی با H و فضاهای پر با P مشخص شده‌اند.

5

فیلدهای گره لیست پیوندی:

۱ – حفره یا فرایند بودن

۲ – آدرس شروع

۳ – طول

۴ – آدرس گره بعدی

مزیت این روش این است که زمانی که فرایندی خاتمه می‌یابد یا مبادله می‌شود این لیست به سادگی update می‌شود.

 

الگوریتم های مکان یابی و تخصیص حافظه

وقتی فرایندها و حفره‌ها در یک لیست مرتب شده بر اساس آدرس قرار می‌گیرند الگوریتم‌های مختلفی جهت تخصیص حافظه به یک فرایند وجود دارد

۱ – اولین برازش (First fit):  جستجو از ابتدای حافظه شروع شده و فرایند در اولین حفره‌ای قرار داده می‌شود که دران جا می‌شود.

۲ – برازش بعدی (Next fit):  مانند First fit است با این تفاوت که جستجو از آخرین محل تخصیص شروع می‌شود.

۳ – بهترین برازش (Best fit): تمام لیست جستجو می‌شود و فرایند در کوچک‌ترین حفره‌ای قرار داده می‌شود که در آن جا می‌شود.

۴ – بدترین برازش (Worst fit): تمام لیست جستجو می‌شود و فرایند در بزرگ‌ترین حفره‌ای قرار داده می‌شود که در آن جا می‌شود.

مثال: در یک سیستم که مدیریت حافظه با استفاده از مبادله انجام  می‌شود حافظه اصلی شامل فضاهای خالی با اندازه‌های به ترتیب ۱۰  ، ۴، ۲۰، ۱۸،۷،۹، ۱۲ است برای درخواست تکه‌هایی از حافظه به طور متوالی و به مقدارهای ۱۲، ۱۰، ۶ کیلو بایت با استفاده از روش‌های گفته شده کدامم یک از فضاهای خالی فوق‌الذکر اشغال می‌شوند؟

6First fit

7Next fit

8Best fit

9Worst fit

  • اگر لیست فضاهای خالی بر اساس اندازه فضاها مرتب باشد سرعت Best fit افزایش می‌یابد.
  • سرعت الگوریتم‌های Best fit,Worst fit پایین است چون لیست باید جستجو شود.
  • در Next fit حفره‌های بزرگ انتهای حافظه سریع‌تر شکسته می‌شود و در ورود فرایندهای بزرگ بعدی مشکل ایجاد می‌شوند.

 

برازش سریع (Quick fit)

برای هر دسته از فرایندها با اندازه‌های متداول یک لیست جداگانه تهیه می‌شود.

جدولی با n  خانه را فرض کنید که:

خانه اول: اشاره گری به ابتدای لیست حفره‌های ۴ کیلو بایتی

خانه دوم: به ابتدای حفره‌های ۸ کیلو بایتی

و…

یافتن حفره‌ای با اندازه مناسب بسیار سریع است.

 

مدیریت حافظه با سیستم رفاقتی (Buddy System)

در بخش بندی ایستا امکان تکه تکه شدن داخلی و در بخش بندی پویا امکان تکه تکه شدن خارجی وجود دارد.

سیستم رفاقتی یک تعادل قابل قبول برای فائق آمدن بر معایب طرح‌های بخش بندی ایستا و پویا است. اندازه بلاک‌های حافظه توانی از ۲ می‌باشند.

نحوه کار:

اگر اندازه یک حفره برابر ۲k  باشد و فرایندی به اندازه S باید به داخل آن مبادله شود اگر S از نصف اندازه حفره بزرگ‌تر بود کل فضا به آن داده می‌شود در غیر این صورت کل بلوک نصف شده و دو بلوک رفیق ایجاد می‌شود این روند به صورت بازگشتی تکرار خواهد شد در صورت آزاد شدن یک حفره امکان ترکیب رفقای مجاور می‌باشد.

از معایب سیستم رفاقتی اتلاف حافظه در این روش است.

شکل زیر نحوه عملکرد سیستم رفاقتی را نشان می‌دهد:

7

توضیح شکل فوق بدین صورت است که ما در ابتدا یک بلوک ۱m داریم سپس یک درخواست ۱۰۰ k داریم یعنی فرایند a درخواست ورود به حافظه را دارد و ۱۰۰ k است پس ۱m تقسیم می‌شود به دو قسمت ۵۱۲k سپس به قسمت اول می‌رویم و چون ۵۱۲k برای ۱۰۰ k زیاد است آن را به دو قسمت ۲۵۶ k تقسیم کرده در اینجا هم ۲۵۶k کیلو زیاد است و به دو قسمت ۱۲۸k تقسیم می‌شود سپس فرایند a در قسمت اول جا می‌گیرد چون فرایند a، ۱۰۰ k می‌خواست ۲۸ k هدر رفت داریم و همین روال را ادامه می‌دهیم هر جا که فرایند کارش به اتمام برسد از حافظه خارج می‌شود.

 

ساختار درختی سیستم رفاقتی

مزیت سیستم رفاقتی این است که چیدمان حفره‌ها ساخت یافته است و می‌توان یک ساختار درختی برای بلوک‌های پر و خالی ایجاد کرد و با یک الگوریتم بازگشتی حفره مناسب را خیلی سریع پیدا کرد

مثال: درخت دودویی بعد از درخواست Release R

11

صفحه بندی

صفحه بندی (Paging)

حافظه اصلی به بلوک‌هایی با اندازه‌های ثابت به نام قاب (frame) تقسیم می‌شود.

حافظه منطقی به بلوک‌هایی با اندازه‌های یکسان به نام صفحه (page) تقسیم می‌شود.

اندازه صفحه و اندازه قاب توسط سخت افزار تعریف می‌شود.

وقتی یک فرایند به داخل حافظه آورده می‌شود تمام صفحات آن به داخل قاب‌های موجود بار می‌شوند و یک جدول صفحه ایجاد می‌شود. جدول صفحه محل قاب هر صفحه آر فرایند را مشخص می‌کند. اندازه صفحه و اندازه قاب باید توانی از ۲ باشند.

نقطه ضعف اصلی صفحه بندی تکه تکه شدن داخلی است.

مثال: تخصیص قاب‌های آزاد به صفحه‌های فرایند A و نمایش جدول صفحه:

12

یک فرایند به نام A داریم که به سه قسمت ۰, ۱, ۲ تقسیم شده است، سپس فرایند اجرا شده و به حافظه می‌آید به‌صورت شکل فوق، قسمت ۰ فرایند A در در قاب شماره ۵ قرار دارد، قسمت ۱ فرایند A در قاب شماره ۸ قرار دارد, قسمت ۲ فرایندA در قاب شماره ۷ قرار دارد. صفحه بندی یعنی حافظه به قسمت‌هایی تقسیم می‌شود به نام فریم و برنامه (فرایند) به قسمت‌هایی تقسیم می‌شود به نام پیج هنگامی که فرایند اجرا می‌شود تمام قاب‌های فرایند در پیج های مورد نظر جای می‌گیرد و جدول صفحه نشان می‌دهد که هر پیج در کدام قاب جای می‌گیرد.

 

ترجمه آدرس در سیستم صفحه بندی

آدرس منطقی از دو قسمت تشکیل شده است:

۱- شماره صفحه (p) 2- آفست (d)

پردازنده به کمک جدول صفحه یک آدرس فیزیکی تولید می‌کند.

آدرس فیزیکی از دو قسمت تشکیل شده است:

۱- شماره قاب ۲- آفست

به آفست انحراف یا تفاوت مکان نیز می گویند.

 

نحوه ترجمه آدرس در سیستم صفحه بندی

مثال: با توجه به آدرس نسبی ۰۰۰۰۰۱۰۱۱۱۰۱۱۱۱۰ چند بیت برای شماره صفحه نیاز است؟

(اندازه صفحه برابر یک کیلو بایت می‌باشد)

پاسخ: اندازه صفحه یک کیلو بایت است پس ۱۰ بیت برای آفست مورد نیاز است، چون آدرس ۱۶ بیتی است ۶ بیت برای صفحه باقی می‌ماند.

آدرس نسبی داده شده دارای آفست (۰۱۱۱۰۱۱۱۱۰) در صفحه (۰۰۰۰۰۱) است

14

یک برنامه می‌تواند حداکثر ۶۴ = ۲۶ صفحه یک کیلو بایتی داشته باشد.

مثال: یک فضای آدرس دهی منطقی شامل ۴ صفحه است و هر صفحه حاوی ۲ کلمه است اگر این صفحات بر روی یک فضای آدرس دهی فیزیکی حاوی ۸ قاب صفحه نگاشت شود آدرس منطقی و فیزیکی چند بیتی خواهد بود؟

فضای آدرس دهی منطقی ۴* ۲=۸= ۲۳

فضای آدرس دهی فیزیکی ۸*۲=۱۶ = ۲۴

بنابراین آدرس منطقی ۳ بیتی و آدرس فیزیکی ۴ بیتی است.

مثال: در یک سیستم حافظه صفحه بندی با یک جدول صفحه حاوی ۶۴ مدخل ۱۰ بیتی و صفحه‌های ۵۱۲ بایتی آدرس منطقی و فیزیکی چند بیتی است؟

اندازه حافظه منطقی = حاصل ضرب تعداد صفحات (تعداد مدخل‌ها) در اندازه هر صفحه:

۶۴*۵۱۲= ۲۶ * ۲۹ = ۲۱۵

اندازه حافظه فیزیکی = حاصل ضرب تعداد آدرس‌ها در اندازه هر صفحه:

۲۱۰* ۵۱۲ = ۲۱۹

بنابراین آدرس منطقی ۱۵ بیتی و آدرس فیزیکی ۱۹ بیتی است.

مثال: در یک فضای آدرس دهی منطقی هر صفحه حاوی ۵۱۲ کلمه است صفحات اصلی بر روی یک فضای آدرس دهی فیزیکی حاوی ۸ قاب صفحه نگاشته می‌شود آدرس فیزیکی حاوی چند بیت است؟

۸*۵۱۲=۲۳ * ۲۹ = ۲۱۲

 

قطعه بندی

در روش قطعه بندی برای مدیریت حافظه برنامه و داده‌ها به تعدادی قطعه (Segment) تقسیم می‌شوند و لزومی ندارد اندازه این قطعه‌ها هم اندازه باشند.

هنگامی که یک فرایند به داخل آورده می‌شود کلیه قطعه‌های ان به داخل حافظه بار می‌شوند و جدول قطعه ایجاد می‌شود.

هر سطر این جدول شامل آدرس شروع قطعه مورد نظر حافظه اصلی و طول قطعه می‌باشد.

دید منطقی از قطعه بندی

15

نکاتی در رابطه با قطعه بندی

۱ – آدرس منطقی از دو قسمت تشکیل یافته است ” شماره قطعه و آفست

۲ – امتیاز قطعه بندی، حفاظت از قطعات و اشتراک داده‌ها و کد می‌باشد.

۳ – الگوی صفحه بندی نمی‌تواند حافظه فیزیکی را از دیدگاه کاربر نسبت به حافظه تفکیک کند.

۴ – قطعه بندی به دلیل به‌کارگیری قطعه‌های غیر هم اندازه مشابه بخش بندی پویا است البته در قطعه بندی یک برنامه می‌تواند بیش از یک بخش را اشغال کند و لزومی ندارد این بخش‌ها پیوسته باشند.

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

 

سخت افزار قطعه بندی

16

مثال: آدرس منطقی ۱۶ بیتی ۰۰۰۱۰۰۱۰۱۱۱۱۰۰۰۰ مفروض است. نحوه تولید آدرس فیزیکی در روش قطعه بندی را نشان دهید (آفست ۱۲ بیتی و شماره قطعه ۴ بیتی).

17

آدرس فیزیکی از جمع آفست ۱۲ بیتی با مقدار پایه به‌دست می‌آید

حداکثر اندازه قطعه: ۲۱۲ = ۴۰۹۶

مثال: کدام آدرس منطقی فاقد آدرس فیزیکی هستند

18

آدرس منطقی در سیستم قطعه بندی از دو قسمت (شماره قطعه و آفست) تشکیل شده

اولین آدرس منطقی، آدرس فیزیکی ندارد چون ۷۰۰>600

آدرس منطقی دوم دارای آدرس فیزیکی است چون ۱۵۰ < ۲۰۰

این آدرس برابر است با ۵۰۰ + ۱۵۰= ۶۵۰

 

 

آنچه مطالعه کردید، توسط یکی یکی از مخاطبین فرادرس به عنوان پیاده سازی و برداشت متنی بخش هایی از آموزش «سیستم های عامل» تهیه شده و جهت استفاده سایر مخاطبین گرامی در متلب سایت منتشر می شود.

 

 

 

 

 

 




1 پاسخ
  1. شاهین احمدی
    شاهین احمدی says:

    سلام و خسته نباشید میخواستم واقعا ازتون تشکر کنم جمعه کنکورمه و توی کتاب اینجوری توضیح نداده بود ولی از این سایت شما تونستم این مبحثو یاد بگیرم
    ???

    پاسخ دادن

ارسال یک پاسخ

در گفتگو ها شرکت کنید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *