جلسه 4 الگوریتمهاي تخصیص حافظه (Fit ،Best Fit ،Next Fit ،Fisrt Fit )

مقدمه:

در سیستم‌های عامل، مدیریت حافظه یکی از وظایف حیاتی است. تخصیص حافظه به فرآیندها به شیوه‌ای کارآمد، تأثیر مستقیمی بر عملکرد کلی سیستم دارد. الگوریتم‌های تخصیص حافظه روش‌هایی هستند که برای تعیین اینکه کدام بخش از حافظه به یک فرآیند اختصاص یابد، به کار گرفته می‌شوند. در این بخش، چهار الگوریتم رایج تخصیص حافظه را بررسی می‌کنیم: First Fit، Next Fit، Best Fit و Worst Fit.

خلاصه نکات کلیدی:

• حافظه خارجی (External Fragmentation): وضعیتی که حافظه کل به اندازه کافی آزاد است، اما تکه‌های حافظه آزاد پراکنده هستند و نمی‌توانند یک درخواست جدید را برآورده کنند.


• حافظه داخلی (Internal Fragmentation): وضعیتی که یک بلاک حافظه به فرآیندی اختصاص داده شده، اما بخشی از آن بلاک استفاده نشده و به صورت بلااستفاده باقی مانده است.

1. الگوریتم First Fit:

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


• مزایا: ساده و سریع است.


• معایب: ممکن است منجر به حافظه خارجی شود، زیرا بلوک‌های کوچک در ابتدای لیست ممکن است زودتر پر شوند.

2. الگوریتم Next Fit:

• نحوه عملکرد: این الگوریتم مشابه First Fit عمل می‌کند، با این تفاوت که جستجو برای بلوک حافظه آزاد از آخرین بلوکی که قبلاً به فرآیندی اختصاص داده شده، آغاز می‌شود و به صورت چرخشی ادامه می‌یابد.


• مزایا: معمولاً سریع‌تر از First Fit است، زیرا نیاز به اسکن کل لیست بلوک‌های آزاد نیست.


• معایب: ممکن است منجر به ایجاد بلوک‌های کوچک در انتهای حافظه شود و حافظه خارجی را تشدید کند.

3. الگوریتم Best Fit:

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


• مزایا: تلاش می‌کند تا حد امکان حافظه داخلی را کاهش دهد.


• معایب: کندتر از First Fit و Next Fit است، زیرا باید کل لیست بلوک‌های آزاد را اسکن کند تا بهترین تطابق را پیدا کند. همچنین ممکن است منجر به ایجاد بلوک‌های حافظه آزاد بسیار کوچک شود که قابل استفاده نیستند.

4. الگوریتم Worst Fit:

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


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


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

تمرین پایان فصل:

1. چهار الگوریتم تخصیص حافظه (First Fit، Next Fit، Best Fit، Worst Fit) را با هم مقایسه کنید. مزایا و معایب هر کدام را در زمینه کاهش حافظه داخلی و خارجی توضیح دهید.


2. سناریویی را توصیف کنید که در آن الگوریتم Worst Fit عملکرد بهتری نسبت به Best Fit داشته باشد.


3. چگونه الگوریتم Next Fit سعی در بهبود عملکرد الگوریتم First Fit دارد؟ محدودیت‌های Next Fit چیست؟


4. تفاوت اصلی بین حافظه داخلی و حافظه خارجی چیست و هر کدام از الگوریتم‌های ذکر شده چگونه بر این دو تأثیر می‌گذارند؟


5. فرض کنید حافظه شما به صورت بلوک‌های آزاد زیر است: [100K، 500K، 200K، 300K]. اگر درخواستی برای تخصیص 250K داشته باشیم، کدام بلوک توسط هر یک از الگوریتم‌های First Fit، Best Fit و Worst Fit انتخاب می‌شود؟