مدیریت حافظه و الگوریتم های تخصیص حافظه

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

به طور کلی برای مدیریت حافظه میتوان چهار وظیفه زیر را در نظر گرفت:

۱- ثبت وضعیت هر یک از مکان های حافظه

۲- تعیین سیاست و خط مشی تخصیص حافظه

۳- تکنیک تخصیص حافظه اصلی

۴- تکنیک آزاد کردن حافظه اصلی

الگوریتم های تخصیص حافظه و مدیریت حافظه

 

هر پیوند، نگاشتی از یک فضای آدرس به فضای آدرس دیگر می باشد. پیوندها در زمان های زیر صورت میگیرند:

– در زمان Compile : اگر در زمان ترجمه معلوم گردد که فرآیند در چه بخشی از حافظه قرار خواهد گرفت.

– زمان بارگذاری (Load Time) : در این حالت کامپایلر (Compiler) کد Relocatable تولید میکند و آدرس نسبی شروع بعداً معلوم میشود.

– زمان اجرا (Run Time) : چنانچه فرآیند در زمان اجرایش بتواند تغییر مکان دهد، آنگاه پیوند آدرس ها تا زمان اجرا به تعویق می افتد.

در این حالت سخت افزار خاصی مورد نیاز است.

 

آدرس منطقی همان آدرس تولید شده توسط پردازنده (CPU) می باشد در حالی که آدرس فیزیکی، آدرس قابل رؤیت توسط واحد حافظه است.

مجموعه آدرس های منطقی به نام فضای آدرس منطقی و مجموعه آدرس های فیزیکی به نام فضای آدرس فیزیکی شناخته میشوند.

 

جایگذاشت ها (Overlays) : به منظور آنکه فرآیندی محدود به اندازه حافظه فیزیکی نگردد و بتواند بزرگتر از حافظه تخصیص یافته به آن اجرا شود، تکنیکی به نام جایگذاشت به کار میرود.

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

این روش به پشتیبانی مستقیم سیستم عامل (OS) نیاز ندارد و میتواند کاملاً توسط کاربر پیاده سازی شود.

 

مدیریت حافظه یکپارچه:

در این شیوه پردازش در هنگام زمانبندی، کل حافظه را به خود اختصاص میدهد.

هنگامی که فرآیند انجام شد، کل حافظه به وضعیت آزاد بازگردانده میشود.

در این صورت برنامه ها از لحاظ اندازه محدود به مقدار حافظه اصلی هستند اما این امکان وجود دارد که با استفاده از جایگذاری، برنامه های بزرگتر از حاظه اصلی را اجرا نمود.

 

در این بخش از بحث، لازم میدانیم چند نکته را نیز در تکمیل صحبت های قبلی ذکر کنیم:

– این روش نیازی به پشتیبانی سخت افزار ندارد.

– در چنین سیستم هایی عملکرد چند برنامگی وجود ندارد.

– وظیفه اصلی مدیریت حافظه، انتقال برنامه به داخل حافظه جهت اجرا توسط پردازنده است.

– در تمامی سیستم عامل های جدید چند برنامگی انجام این وظیفه همراه با طرح حافظه مجازی صورت میپذیرد.

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

 

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

۱- روش بخش بندی ایستا:

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

۱) بخش های با اندازه های مساوی؛ که در این حالت هر فرآیندی که اندازه آن کمتر یا مساوی اندازه بخش باشد میتواند به داخل بخش مورد نظر وارد شود.

در این حالت به دو مشکل بر میخوریم:

– ممکن است برنامه بزرگتر از یک بخش باشدو در این صورت روش overlay میتواند استفاده شود.

– استفاده از حافظه اصلی ناکارآمد میشود. هر برنامه صرف نظر از اندازه اش فضای کامل را اشغال میکند. فضای به هدر رفته را تکه تکه شدن داخلی (Internal Fragmentation) میگویند.

 

۲) امکان استفاده از بخش هایی با اندازه نامساوی؛ که در این حالت هر دو مشکل مطرح شده در بالا میتوانند کاهش یابند.

در این روش تخصیص هر فرآیند میتواند به کوچکترین بخشی باشد که در آنجا قرار میگیرد.

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

 

۲- روش بخش بندی پویا:

در این روش، سیستم عامل، جدول شامل بخش های حافظه آزاد و اشغال را نگه میدارد.

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

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

حافظه در این روش به مرور به قطعاتی تقسیم میشود که ممکن است این قطعات به قدری کوچک باشند که مورد استفاده هیچ برنامه ای قرار نگیرد. این نوع تکه تکه شدن را تکه تکه شدن خارجی یا External Fragmentation میگوییم.

لازم به ذکر است که یک روش برای مقابله با External Fragment فشرده سازی یا Compacation است و این مورد زمانی امکان پذیر است که کد برنامه ها Relocatable باشند.

سیستم عامل باید از وضعیت حافظه شامل محل شروع، طول یک بخش اشغال شده و برنامه هایی که این بخش ها را در اختیار دارند مطلع باشد، بدین منظور میتوان از دو ساختار زیر استفاده کرد:

– روش Bitmap : متناظر با هر واحد تخصیص، یک بیت در نظر گرفته میشود؛ در این حالت داریم:

۰ : آزاد (صفر)

۱ : اِشغال

– روش Linked List : یک لیست پیوندی از قطعات تخصیص یافته و آزاد

 

 

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

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

 

الگوریتم اولین برازش

ساده ترین الگوریتم، اولین برازش (First fit) نام دارد که توضیح آن چنین است:

“از ابتدای حافظه شروع کن؛ فرآیند را در اولین حفره ای قرار بده که در آن، جا میشود.”

الگوریتم اولین برازش ساده و سریع است. همچنین کارآیی آن نیز مناسب است.

 

الگوریتم برازش بعدی

نوع دیگری از همین الگوریتم، برازش بعدی (Next fit) است.

“از محل آخرین تخصیص شروع کن؛ فرآیند را در اولین حفره ای قرار بده که در آن، جا میشود.”

جالب است بدانید که بر اساس شبیه سازی های انجام شده توسط Bays در سال ۱۹۷۷ نشان میدهد که کارآیی الگوریتم Next fit کمر کمتر از کارآیی الگوریتم First fit است.

الگوریتم برازش بعدی، ساده و سریع است.

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

 

الگوریتم بهترین برازش

الگوریتم مشهور بعدی، بهترین برازش (Best fit) است.

“تمام لیست را جستجو کن؛ فرآیند را در کوچکترین حفره ای قرار بده که در آن جا میشود.”

الگوریتم Best fit سرعت پایینی داشته (به دلیل نیاز به جستجو در لیست) و در حافظه تعداد زیادی حفره ریز بدون مصرف ایجاد میکند.

البته کارآیی آن که بهره وری حافظه است، در کل مناسب است.

 

الگوریتم بدترین برازش

برای این که مشکل به وجود آمدن حفره های بسیار کوچک در حافظه برطرف گردد، الگوریتم بدترین برازش (Worst fit) پیشنهاد شده است.

“تمام لیست را جستجو کن؛ فرآیند را در بزرگترین حفره موجود قرار بده؛ البته اگر در آن جا میشود!”

الگوریتم Worst fit سرعت پایین (به دلیل نیاز به جستجو در لیست) و کارآیی پایین (بهره وری پایین حافظه) دارد.

 

الگوریتم برازش سریع

در نهایت الگوریتم تخصیص دیگری به نام برازش سریع (الگوریتم Quick fit) وجود دارد که برای هر دسته از فرآیندها با اندازه های متداول، یک لیست جداگانه تهیه میکند.

اگرچه یافتن حفره مناسب سریع است اما هر گاه یک فرآیند خاتمه می یابد، عمل ترکیب حفره ها بسیار وقت گیر خواهد بود.

 

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



[ برچسب ها ] : , , , , , , , ,
ارسال شده در : بخش کامپیوتر
نظر شما در مورد اين پست چيست ؟

دیدگاه خود را به ما بگویید.

 
 
  دکتری تخصصی برق الکترونیک
طراح مدارهای الکترونیکی
برنامه نویس انواع میکروها
مشاوره و اجرای لینک های وایرلس
پیاده سازی سیستم های مبتنی بر شبکه
E_mail: electronic@sabzelco.ir
Tel: 09150462401
توسعه دهنده برنامه های سمت سرور

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

E_mail: computer@sabzelco.ir
Tel: 09371974233