مدیریت تخصیص حافظه در سیستم عامل — آموزش ۶ الگوریتم تخصیص حافظه همراه با مثال

مبحث مدیریت تخصیص حافظه در سیستم عامل (Memory allocation algorithms) یکی از مباحث محوری در علوم کامپیوتر به شمار می‌رود. هر فرآیند برای اجراشدن باید دارای حافظه مناسب و اختصاصی باشد که مدیریت تخصیص حافظه در سیستم‌عامل در این حوزه عمل می‌کند و با ارائه الگوریتم‌های تخصیص حافظه برای افزایش کارایی، این مهم را برآورده می‌سازد. در این مقاله از پی‌استور با مدیریت تخصیص حافظه در سیستم عامل بیشتر آشنا می‌شویم.

مقدمه مدیریت تخصیص حافظه در سیستم عامل

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

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

تخصیص حافظه چیست؟

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

به عبارتی تمام برنامه‌ها برای اجرا در حافظه‌ی اصلی بارگذاری می‌شوند که در این هنگام با چند حالت روبرو می‌شویم:

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

مدیریت تخصیص حافظه در سیستم عامل چیست؟

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

مدیریت تخصیص حافظه در سیستم عامل شامل چهار وظیفه زیر است:

۱. نظارت بر وضعیت هر یک از مکان‌های حافظه اصلی: یعنی نظارت بر اینکه کدام مکان تخصیص‌یافته و کدام یک تخصیص نیافته (آزاد) است.

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

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

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

پاورپوینت انواع سیستم عامل از لحاظ عملکرد

کلیک کنید

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

1. الگوریتم First Fit
2. الگوریتم Next fit
3. الگوریتم Best fit
4. الگوریتم Worst fit
5. الگوریتم Quick fit

– الگوریتم First Fit (اولین برازش)

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

مثلا درخواست‌های فرآیندها را به ترتیب 300K، 25K، 125K و 50K در نظر بگیرید. بگذارید دو بلوک حافظه با اندازه 150K و سپس یک بلوک با اندازه 350K موجود باشد.

300K درخواست به بلوک 350K اختصاص داده می‌شود، 50K باقیمانده حذف می‌شود. 25K به بلوک 150K اختصاص داده می‌شود، 125K مابقی حذف می‌شود. سپس 125K و 50K به پارتیشن‌های باقی‌مانده اختصاص داده می‌شوند.

مثالی دیگر با شکل:

• برنامه الگوریتم First Fit در #C سی شارپ — کلیک کنید
• برنامه الگوریتم First Fit در ++C سی پلاس پلاس — کلیک کنید

۲- الگوریتم Next fit (برازش بعدی)

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

همانطوریکه در شکل زیر مشاهده می‌کنید فرآیند A بر اساس الگوریتم First Fit از ابتدا شروع به اسکن کرده و در اولین حفره مناسب قرارگرفته است. فرآیند B که بعد از فرآیند A واردشده است از همان‌جایی که A در جستجو مانده بود ادامه داده و در اولین حفره مناسب قرار می‌گیرد که این عملکرد با عنوان الگوریتم Next Fit شناخته می‌شود.

• برنامه الگوریتم Next Fit در #C سی شارپ — کلیک کنید
• برنامه الگوریتم Next Fit در ++C سی پلاس پلاس — کلیک کنید

۳- الگوریتم Best Fit (بهترین برازش)

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

مزیت آن نسبت به First Fit این است که استفاده از حافظه در آن بسیار بهتر است، زیرا ابتدا کوچک‌ترین پارتیشن آزاد موجود را جستجو می‌کند اما نسبت به آن کندتر است و حتی ممکن است حافظه را با حفره‌های کوچک بی‌فایده پر کند.

300K به یک بلوک با اندازه 350K اختصاص داده می‌شود. 50k در بلوک باقی خواهد ماند. 25K به 50K باقیمانده از بلوک قبل تخصیص داده می‌شود. 25k در بلوک باقی خواهد ماند. 125K به بلوک 150K اختصاص داده می‌شود. 25k در این بلوک نیز باقی خواهد ماند. 50K نمی‌تواند اختصاص داده شود حتی اگر فضای 25K + 25K در دسترس باشد.

• برنامه الگوریتم Best Fit در #C سی شارپ — کلیک کنید
• برنامه الگوریتم Best Fit در ++C سی پلاس پلاس — کلیک کنید

۴- الگوریتم Worst Fit (بدترین برازش)

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

• برنامه الگوریتم Worst Fit در #C سی شارپ — کلیک کنید
• برنامه الگوریتم Worst Fit در ++C سی پلاس پلاس — کلیک کنید

۵- الگوریتم Quick Fit (برازش سریع)

پنجمین الگوریتم تخصیص حافظه در سیستم عامل، الگوریتم Quick Fit (برازش سریع) رویکرد متفاوتی نسبت به الگوریتم‌هایی دارد که تاکنون در نظر گرفته‌ایم. لیست‌های جداگانه‌ای برای برخی از اندازه‌های حافظه رایج درخواست شده، نگهداری می‌شود. برای مثال، می‌توانیم فهرستی برای حفره‌های 4K، فهرستی برای حفره‌هایی با اندازه 8K و غیره داشته باشیم. یک فهرست را می‌توان برای حفره‌های بزرگ یا حفره‌هایی که در هیچ‌ یک از لیست‌های دیگر قرار نمی‌گیرند، نگه داشت.

در Quick Fit، قبل از اینکه تصمیم بگیرید از سیستم عامل فضای ذخیره‌سازی بیشتری بخواهید، ادغام انجام می‌شود. سپس ببینید آیا اکنون یک بلوک به اندازه کافی بزرگ دارید یا خیر؟ اگر این کار را نکنید، فضای بیشتری از سیستم دریافت خواهید کرد. توجه داشته باشید که Quick Fit، بر خلاف First Fit و Best Fit، تمایل دارد تا تکه تکه شدن حافظه آزاد را به حداقل برساند که عملکرد کلی سیستم را بهبود می‌بخشد. اگرچه یافتن حفره مناسب سریع است اما هر‌گاه یک فرآیند خاتمه می‌یابد، عمل ترکیب حفره‌ها بسیار وقت‌گیر خواهد بود.

برنامه الگوریتم های زمانبندی در #C سی شارپ

کلیک کنید

۶- الگوریتم Buddy’s system (سیستم دوستان)

در سیستم دوستان، اندازه بلوک‌های آزاد به‌صورت توان یکپارچه ۲ است: ۲، ۴، ۸، ۱۶ و غیره تا اندازه حافظه. هنگامی‌که یک بلوک آزاد با اندازه 2k درخواست می‌شود، یک بلوک آزاد از لیست بلوک‌های آزاد با اندازه 2k اختصاص داده می‌شود. اگر بلوک آزاد با اندازه 2k در دسترس نباشد، بلوک با اندازه بزرگ‌تر بعدی، یعنی 2k+1 به دو نیمه به نام دوستان تقسیم می‌شود تا درخواست را برآورده کند.

مثال:

فرض کنید اندازه کل حافظه ۵۱۲ کیلوبایت باشد و فرآیند P1، به ۷۰ کیلوبایت نیاز دارد تا تخصیص داده شود. ازآنجایی‌که لیست‌های حفره فقط برای توان‌های ۲ هستند، ۱۲۸ کیلوبایت به‌اندازه کافی بزرگ خواهد بود. در ابتدا هیچ ۱۲۸ کیلوبایتی وجود ندارد و بلوک‌های ۲۵۶ کیلوبایتی نیز وجود ندارند. بنابراین بلوک ۵۱۲ کیلوبایتی به دو دوست با حجم ۲۵۶ کیلوبایت تقسیم می‌شود، یکی از آن‌ها به دو بلوک ۱۲۸ کیلوبایتی تقسیم می‌شود و یکی به فرآیند اختصاص می‌یابد. فرآیند بعدی با نام P2 به ۳۵ کیلوبایت نیاز دارد. برای گرد کردن ۳۵ کیلوبایت تا توان ۲، یک بلوک ۶۴ کیلوبایتی موردنیاز است.

وقتی بلوک ۱۲۸ کیلوبایتی به دو دوست ۶۴ کیلوبایتی تقسیم و دوباره فرآیندی دیگر مثل P3 (130KB) در کل 256KB تنظیم می‌شود. پس از ارضای درخواست به این صورت، زمانی که چنین بلوکی آزاد است، می‌توان دو بلوک/رفیق را دوباره باهم ترکیب کرد تا بلوک اصلی دو برابر بزرگ‌تر را تشکیل دهند، وقتی‌که نیمه دوم هم آزاد است.

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

آخرین الگوریتم تخصیص حافظه در سیستم عامل (Buddy’s system)، معایبی هم دارد ازجمله اینکه، اغلب ازنظر استفاده از حافظه به تدریج ناکارآمد می‌شود. ازآنجایی‌که همه درخواست‌ها باید به توان ۲ گرد شوند، یک فرآیند ۳۵ کیلوبایتی به ۶۴ کیلوبایت اختصاص داده می‌شود، بنابراین ۲۹ کیلوبایت اضافی هدررفته و باعث تکه‌تکه شدن داخلی می‌شود. ممکن است حفره‌هایی هم بین دوستان وجود داشته باشد که باعث تکه‌تکه شدن خارجی شود.

برنامه الگوریتم Buddy System در #C به صورت زیر است:

using System;
using System.Collections.Generic;

public class Buddy
{
	
	// Inner class to store lower
	// and upper bounds of the
	// allocated memory
	class Pair
	{
		public int lb, ub;
		public Pair(int a, int b)
		{
			lb = a;
			ub = b;
		}
	}
	
	// Size of main memory
	int size;
	
	// Array to track all
	// the free nodes of various sizes
	List<Pair> []arr;
	
	// Else compiler will give warning
	// about generic array creation
	Buddy(int s)
	{
		size = s;
		
		// Gives us all possible powers of 2
		int x = (int)Math.Ceiling(Math.Log(s) /
								Math.Log(2));
		
		// One extra element is added
		// to simplify arithmetic calculations
		arr = new List<Pair>[x + 1];
		
		for (int i = 0; i <= x; i++)
			arr[i] = new List<Pair>();
			
		// Initially, only the largest block is free
		// and hence is on the free list
		arr[x].Add(new Pair(0, size - 1));
	}
	
	void allocate(int s)
	{
		
		// Calculate which free list to search
		// to get the smallest block
		// large enough to fit the request
		int x = (int)Math.Ceiling(Math.Log(s) /
								Math.Log(2));
		
		int i;
		Pair temp = null;
		
		// We already have such a block
		if (arr[x].Count > 0)
		{
			
			// Remove from free list
			// as it will be allocated now
			temp = (Pair)arr[x][0];
				arr[x].RemoveAt(0);
			Console.WriteLine("Memory from " + temp.lb +
					" to " + temp.ub + " allocated");
			return;
		}
		
		// If not, search for a larger block
		for (i = x + 1; i < arr.Length; i++)
		{
			if (arr[i].Count == 0)
				continue;
				
			// Found a larger block, so break
			break;
		}
		
		// This would be true if no such block
		// was found and array was exhausted
		if (i == arr.Length)
		{
			Console.WriteLine("Sorry, failed to" +
							" allocate memory");
			return;
		}
		
		// Remove the first block
		temp = (Pair)arr[i][0];
		arr[i].RemoveAt(0);
		
		i--;
		
		// Traverse down the list
		for (; i >= x; i--)
		{
			
			// Divide the block in two halves
			// lower index to half-1
			Pair newPair = new Pair(temp.lb, temp.lb +
								(temp.ub - temp.lb) / 2);
			
			// half to upper index
			Pair newPair2 = new Pair(temp.lb + (temp.ub -
							temp.lb + 1) / 2, temp.ub);
			
			// Add them to next list which is
			// tracking blocks of smaller size
			arr[i].Add(newPair);
			arr[i].Add(newPair2);
			
			// Remove a block to continue
			// the downward pass
			temp = (Pair)arr[i][0];
			arr[i].RemoveAt(0);
		}
		
		// Finally inform the user
		// of the allocated location in memory
		Console.WriteLine("Memory from " + temp.lb +
				" to " + temp.ub + " allocated");
	}
	
	// Driver Code
	public static void Main(String []args)
	{
		int initialMemory = 0;
		initialMemory = 128;
		
		// Initialize the object with main memory size
		Buddy obj = new Buddy(initialMemory);
		obj.allocate(32);
		obj.allocate(7);
		obj.allocate(64);
		obj.allocate(56);
	}
}

// This code is contributed by 29AjayKumar

سخن پایانی درمورد مدیریت تخصیص حافظه در سیستم عامل

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

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