Algorithms/partition allocation methods

هناك أربع طرق لإدارة الذاكرة في أنظمة التشغيل المختلفة:

1. التعيين المفرد المتجاور Single contiguous allocatoin: وهذه هي أبسط طريقة لتعيين الأقسام وتستخدم في نظام MS-DOS. وتكون الذاكرة بأكملها متاحة للعملية قيد التنفيذ باستثناء جزء من الذاكرة يكون محجوزًا من قبل النظام.
2. التعيين المجزّء Partitioned allocation: تقسّم الذاكرة في هذه الطريقة إلى كتل blocks أو أجزاء partitions مختلفة، وتحجز كل عملية ما تحتاج إليه من هذه الأجزاء.
3. إدارة الذاكرة بتقسيمها إلى صفحات Paged memory management: تقسّم الذاكرة في هذه الطريقة إلى وحدات ذات حجم ثابت تدعى بإطارات الصفحات page frames، وتستخدم هذه الطريقة في بيئات الذاكرة الافتراضية virtual memory environment.
4. إدارة الذاكرة المجزّأة Segmented memory management: تقسّم الذاكرة في هذه الطريقة إلى أجزاء segments مختلفة (الجزء هو تجمّع منطقي للبيانات أو الشيفرات الخاصة بالعملية)، ولا يشترط تجاور الذاكرة المحجوزة في هذه الطريقة.

تستخدم معظم أنظمة التشغيل (مثل نظامي ويندوز ولينكس) طريقة التقطيع مع الصفحات، إذ تقسّم العملية إلى أقسام ويمتلك كل قسم منها عددًا من الصفحات.

عند توفّر أكثر من جزء واحد شاغر لتلبية متطلبات عملية معيّنة، فيجب حينئذٍ اختيار جزء من الذاكرة، وتتطلب عملية الاختيار هذه استخدام طريقة معيّنة في حجز جزء معين من الذاكرة، وأفضل طريقة لحجز جزء من الذاكرة هي الطريقة التي تتجنّب التجزئة الداخلية Internal fragmentation.

وهناك عدد من الطرق المتّبعة لحجز جزء من الذاكرة:

1. الملاءمة الأولى First Fit: تُحجز أول كتلة ذات مساحة كافية من قمّة الذاكرة الرئيسية.
2. الملاءمة الفضلى Best Fit: تُحجز أول كتلة ذات أصغر مساحة كافية من بين الكتل المتوفرة في الذاكرة الرئيسية.
3. الملاءمة السوأى Worst Fit: تُحجز الكتلة التي تمتلك أكبر مساحة كافية من بين الكتل المتوفرة في الذاكرة الرئيسية.
4. الملاءمة اللاحقة Next Fit: وهي مشابهة للملاءة الأولى ولكن تبحث هذه الطريقة عن أول جزء كافٍ بدءًا من آخر موقع لحجز الذاكرة.

يجدر التنبيه إلى أنّ الملاءمة الفضلى لا تعني بالضرورة أنّها الطريقة الأفضل في حجز الذاكرة، فمع أنّ هذه الطريقة تقلّل من هدر المساحة المحجوزة من الذاكرة ولكنّها تتطلّب وقتًا أكثر في المعالجة بحثًا عن الكتلة التي يكون حجمها مقاربًا للحجم المطلوب.

خوازرمية الملاءمة الأولى

تحجز هذه الطريقة أول كتلة ذات مساحة كافية من قمّة الذاكرة الرئيسية.

مثال:

Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};
Output:
Process No.    Process Size    Block no.
   1               212            2
   2               417            5
   3               112            2
   4               426        Not Allocated

هذه الطريقة هي الأسرع من بين الطرق الأربعة، إذ أنّها تبحث عن أول كتلة يناسب حجمها حجم العملية المراد تنفيذها.

تعاني هذه الطريقة من بعض المشاكل، إذ أنّها لا تسمح في بعض الأحيان للعمليات بحجز المساحة التي تحتاج إليها حتى وإن كانت تلك المساحة متوفّرة، ففي المثال السابق لم تحصل العملية الرابعة (ذات الحجم 426) على مكان في الذاكرة، ولكنّها تحصل المساحة التي تحتاج إليها باستخدام طريقة الملاءمة الفضلى (تذهب الكتلة 4 (ذات الحجم 300) إلى العملية 1، والكتلة 2 إلى العملية 2، والكتلة 3 إلى العملية 3 والكتلة 5 إلى العملية 4).

خطوات الخوارزمية

تتبع خوارزمية الملاءمة الأولى الخطوات التالية:

1. تُغذّى الخوارزمية بكتل الذاكرة المتاحة مع حجم كل كتلة إضافة إلى العمليات مع حجم كل عملية.
2. تهيّئ الخوارزمية بعدها جميع كتل الذاكرة لتكون شاغرة.
3. تبدأ الخوارزمية باختيار كل عملية والتحقق من إمكانية إسنادها إلى الكتلة الحالية.
4. إن كان حجم العملية أصغر من حجم الكتلة أو مساويًا له، تُسند العملية إلى تلك الكتلة وتنتقل الخوارزمية إلى العملية التالية.
5. تستمر الخوارزمية في التحقق من الكتل الباقية إن لم يتحقق الشرط في الخطوة السابقة.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++:

#include<bits/stdc++.h> 
using namespace std; 

void firstFit(int blockSize[], int m, 
			int processSize[], int n) 
{ 
	// تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة
	int allocation[n]; 

	// لا تعيّن أي كتلة لأي عملية في بداية الأمر
	memset(allocation, -1, sizeof(allocation)); 

	// اختيار كل عملية والبحث عن الكتل الملائمة
	// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
	for (int i = 0; i < n; i++) 
	{ 
		for (int j = 0; j < m; j++) 
		{ 
			if (blockSize[j] >= processSize[i]) 
			{ 
				// إسناد الكتلة j إلى العملية p[i]
				allocation[i] = j; 

				// تقليص الذاكرة المتوفّرة في هذه الكتلة
				blockSize[j] -= processSize[i]; 

				break; 
			} 
		} 
	} 

	cout << "\nProcess No.\tProcess Size\tBlock no.\n"; 
	for (int i = 0; i < n; i++) 
	{ 
		cout << " " << i+1 << "\t\t"
			<< processSize[i] << "\t\t"; 
		if (allocation[i] != -1) 
			cout << allocation[i] + 1; 
		else
			cout << "Not Allocated"; 
		cout << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int blockSize[] = {100, 500, 200, 300, 600}; 
	int processSize[] = {212, 417, 112, 426}; 
	int m = sizeof(blockSize) / sizeof(blockSize[0]); 
	int n = sizeof(processSize) / sizeof(processSize[0]); 

	firstFit(blockSize, m, processSize, n); 

	return 0 ; 
}

• بايثون:

def firstFit(blockSize, m, processSize, n): 
	
	
	# تخزن هذه القائمة معرّف الكتلة التي حُجزت لعملية معينة 
	allocation = [-1] * n 

	# لا تعيّن أي كتلة لأي عملية في بداية الأمر 

	# اختيار كل عملية والبحث عن الكتل الملائمة 
	# بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية 
	for i in range(n): 
		for j in range(m): 
			if blockSize[j] >= processSize[i]: 
				
				# إسناد الكتلة j إلى العملية p[i]
				allocation[i] = j 

				# تقليص الذاكرة المتوفّرة في هذه الكتلة 
				blockSize[j] -= processSize[i] 

				break

	print(" Process No. Process Size	 Block no.") 
	for i in range(n): 
		print(" ", i + 1, "		 ", processSize[i], 
						"		 ", end = " ") 
		if allocation[i] != -1: 
			print(allocation[i] + 1) 
		else: 
			print("Not Allocated") 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	blockSize = [100, 500, 200, 300, 600] 
	processSize = [212, 417, 112, 426] 
	m = len(blockSize) 
	n = len(processSize) 

	firstFit(blockSize, m, processSize, n)

• جافا:

class GFG 
{ 
	static void firstFit(int blockSize[], int m, 
						int processSize[], int n) 
	{ 
		// تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
		int allocation[] = new int[n]; 
	
		// لا تعيّن أي كتلة لأي عملية في بداية الأمر 
		for (int i = 0; i < allocation.length; i++) 
			allocation[i] = -1; 
	
		// اختيار كل عملية والبحث عن الكتل الملائمة
		// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
		for (int i = 0; i < n; i++) 
		{ 
			for (int j = 0; j < m; j++) 
			{ 
				if (blockSize[j] >= processSize[i]) 
				{ 
					// إسناد الكتلة j إلى العملية p[i]
					allocation[i] = j; 
	
					// تقليص الذاكرة المتوفّرة في هذه الكتلة
					blockSize[j] -= processSize[i]; 
	
					break; 
				} 
			} 
		} 
	
		System.out.println("\nProcess No.\tProcess Size\tBlock no."); 
		for (int i = 0; i < n; i++) 
		{ 
			System.out.print(" " + (i+1) + "\t\t" + 
							processSize[i] + "\t\t"); 
			if (allocation[i] != -1) 
				System.out.print(allocation[i] + 1); 
			else
				System.out.print("Not Allocated"); 
			System.out.println(); 
		} 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int blockSize[] = {100, 500, 200, 300, 600}; 
		int processSize[] = {212, 417, 112, 426}; 
		int m = blockSize.length; 
		int n = processSize.length; 
		
		firstFit(blockSize, m, processSize, n); 
	} 
}

خوارزمية الملاءمة الفضلى

تحجز هذه الطريقة أول كتلة ذات أصغر مساحة كافية من بين الكتل المتوفرة في الذاكرة الرئيسية.

مثال:

Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};
Output:
Process No.    Process Size    Block no.
 1        212        4
 2        417        2
 3        112        3
 4        426        5

خطوات الخوارزمية

1. تُغذّى الخوارزمية بكتل الذاكرة المتاحة مع حجم كل كتلة إضافة إلى العمليات مع حجم كل عملية.
2. تهيّئ الخوارزمية بعدها جميع كتل الذاكرة لتكون شاغرة.
3. تبدأ الخوارزمية باختيار كلّ عملية والبحث عن الكتلة ذات الحجم الأصغر والتي يمكن تعيينها إلى العملية الحالية، فإن وجدتها عيّنتها إلى العملية الحالية.
4. إن لم تعثر الخوارزمية على الكتلة المطلوبة تجاوزت تلك العملية وانتقلت إلى العملية التي تليها.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 
using namespace std; 

void bestFit(int blockSize[], int m, int processSize[], int n) 
{ 
	//  تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
	int allocation[n]; 

	// لا تعيّن أي كتلة لأي عملية في بداية الأمر
	memset(allocation, -1, sizeof(allocation)); 

	// اختيار كل عملية والبحث عن الكتل الملائمة
	// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
	for (int i=0; i<n; i++) 
	{ 
		// البحث عن أفضل كتلة تلائم العملية الحالية
		int bestIdx = -1; 
		for (int j=0; j<m; j++) 
		{ 
			if (blockSize[j] >= processSize[i]) 
			{ 
				if (bestIdx == -1) 
					bestIdx = j; 
				else if (blockSize[bestIdx] > blockSize[j]) 
					bestIdx = j; 
			} 
		} 

		// إن كان بالإمكان العثور على كتلة للعملية الحالية
		if (bestIdx != -1) 
		{ 
			// إسناد الكتلة j إلى العملية p[i] 
			allocation[i] = bestIdx; 

			// تقليص الذاكرة المتوفّرة في هذه الكتلة
			blockSize[bestIdx] -= processSize[i]; 
		} 
	} 

	cout << "\nProcess No.\tProcess Size\tBlock no.\n"; 
	for (int i = 0; i < n; i++) 
	{ 
		cout << " " << i+1 << "\t\t" << processSize[i] << "\t\t"; 
		if (allocation[i] != -1) 
			cout << allocation[i] + 1; 
		else
			cout << "Not Allocated"; 
		cout << endl; 
	} 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int blockSize[] = {100, 500, 200, 300, 600}; 
	int processSize[] = {212, 417, 112, 426}; 
	int m = sizeof(blockSize)/sizeof(blockSize[0]); 
	int n = sizeof(processSize)/sizeof(processSize[0]); 

	bestFit(blockSize, m, processSize, n); 

	return 0 ; 
}

• بايثون:

def bestFit(blockSize, m, processSize, n): 
	
	#  تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
	allocation = [-1] * n 
	
	# اختيار كل عملية والبحث عن الكتل الملائمة
	# بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
	for i in range(n): 
		
		# البحث عن أفضل كتلة تلائم العملية الحالية 
		bestIdx = -1
		for j in range(m): 
			if blockSize[j] >= processSize[i]: 
				if bestIdx == -1: 
					bestIdx = j 
				elif blockSize[bestIdx] > blockSize[j]: 
					bestIdx = j 

		# إن كان بالإمكان العثور على كتلة للعملية الحالية 
		if bestIdx != -1: 
			
			# إسناد الكتلة j إلى العملية p[i]  
			allocation[i] = bestIdx 

			# تقليص الذاكرة المتوفّرة في هذه الكتلة 
			blockSize[bestIdx] -= processSize[i] 

	print("Process No. Process Size	 Block no.") 
	for i in range(n): 
		print(i + 1, "		 ", processSize[i], 
								end = "		 ") 
		if allocation[i] != -1: 
			print(allocation[i] + 1) 
		else: 
			print("Not Allocated") 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	blockSize = [100, 500, 200, 300, 600] 
	processSize = [212, 417, 112, 426] 
	m = len(blockSize) 
	n = len(processSize) 

	bestFit(blockSize, m, processSize, n)

• جافا:

public class GFG 
{ 
	static void bestFit(int blockSize[], int m, int processSize[], 
													int n) 
	{ 
		//  تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة  
		int allocation[] = new int[n]; 
	
		// لا تعيّن أي كتلة لأي عملية في بداية الأمر
		for (int i = 0; i < allocation.length; i++) 
			allocation[i] = -1; 
	
	    // اختيار كل عملية والبحث عن الكتل الملائمة
		//  بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
		for (int i=0; i<n; i++) 
		{ 
			// البحث عن أفضل كتلة تلائم العملية الحالية 
			int bestIdx = -1; 
			for (int j=0; j<m; j++) 
			{ 
				if (blockSize[j] >= processSize[i]) 
				{ 
					if (bestIdx == -1) 
						bestIdx = j; 
					else if (blockSize[bestIdx] > blockSize[j]) 
						bestIdx = j; 
				} 
			} 
	
			// إن كان بالإمكان العثور على كتلة للعملية الحالية
			if (bestIdx != -1) 
			{ 
				// إسناد الكتلة j إلى العملية p[i] 
				allocation[i] = bestIdx; 
	
				// تقليص الذاكرة المتوفّرة في هذه الكتلة
				blockSize[bestIdx] -= processSize[i]; 
			} 
		} 
	
		System.out.println("\nProcess No.\tProcess Size\tBlock no."); 
		for (int i = 0; i < n; i++) 
		{ 
			System.out.print(" " + (i+1) + "\t\t" + processSize[i] + "\t\t"); 
			if (allocation[i] != -1) 
				System.out.print(allocation[i] + 1); 
			else
				System.out.print("Not Allocated"); 
			System.out.println(); 
		} 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int blockSize[] = {100, 500, 200, 300, 600}; 
		int processSize[] = {212, 417, 112, 426}; 
		int m = blockSize.length; 
		int n = processSize.length; 
		
		bestFit(blockSize, m, processSize, n); 
	} 
}

خوارزمية الملاءمة السوأى

تحجز هذه الطريقة الكتلة التي تمتلك أكبر مساحة كافية من بين الكتل المتوفرة في الذاكرة الرئيسية. وإن أتت عملية تتطلب مساحة كبيرة في مرحلة متأخرة فلن يكون هناك متّسع لهذه العملية في الذاكرة.

خطوات الخوارزمية

1. تُغذّى الخوارزمية بكتل الذاكرة المتاحة مع حجم كل كتلة إضافة إلى العمليات مع حجم كل عملية.
2. تهيّئ الخوارزمية بعدها جميع كتل الذاكرة لتكون شاغرة.
3. تبدأ الخوارزمية باختيار كلّ عملية والبحث عن الكتلة ذات الحجم الأكبر والتي يمكن تعيينها إلى العملية الحالية، فإن وجدتها عيّنتها إلى العملية الحالية.
4. إن لم تعثر الخوارزمية على الكتلة المطلوبة تجاوزت تلك العملية وانتقلت إلى العملية التي تليها.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 
using namespace std; 

void worstFit(int blockSize[], int m, int processSize[], 
												int n) 
{ 
	// تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
	int allocation[n]; 

	//  لا تعيّن أي كتلة لأي عملية في بداية الأمر 
	memset(allocation, -1, sizeof(allocation)); 

	// اختيار كل عملية والبحث عن الكتل الملائمة
	// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
	for (int i=0; i<n; i++) 
	{ 
		// البحث عن أفضل كتلة تلائم العملية الحالية 
		int wstIdx = -1; 
		for (int j=0; j<m; j++) 
		{ 
			if (blockSize[j] >= processSize[i]) 
			{ 
				if (wstIdx == -1) 
					wstIdx = j; 
				else if (blockSize[wstIdx] < blockSize[j]) 
					wstIdx = j; 
			} 
		} 

		// إن كان بالإمكان العثور على كتلة للعملية الحالية
		if (wstIdx != -1) 
		{ 
			//  إسناد الكتلة j إلى العملية p[i] 
			allocation[i] = wstIdx; 

			// تقليص الذاكرة المتوفّرة في هذه الكتلة 
			blockSize[wstIdx] -= processSize[i]; 
		} 
	} 

	cout << "\nProcess No.\tProcess Size\tBlock no.\n"; 
	for (int i = 0; i < n; i++) 
	{ 
		cout << " " << i+1 << "\t\t" << processSize[i] << "\t\t"; 
		if (allocation[i] != -1) 
			cout << allocation[i] + 1; 
		else
			cout << "Not Allocated"; 
		cout << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int blockSize[] = {100, 500, 200, 300, 600}; 
	int processSize[] = {212, 417, 112, 426}; 
	int m = sizeof(blockSize)/sizeof(blockSize[0]); 
	int n = sizeof(processSize)/sizeof(processSize[0]); 

	worstFit(blockSize, m, processSize, n); 

	return 0 ; 
}

• بايثون:

def worstFit(blockSize, m, processSize, n): 
	
	# تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة
	
	# لا تعيّن أي كتلة لأي عملية في بداية الأمر
	allocation = [-1] * n 
	
	# اختيار كل عملية والبحث عن الكتل الملائمة
	#  بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية 
	for i in range(n): 
		
		# البحث عن أفضل كتلة تلائم العملية الحالية
		wstIdx = -1
		for j in range(m): 
			if blockSize[j] >= processSize[i]: 
				if wstIdx == -1: 
					wstIdx = j 
				elif blockSize[wstIdx] < blockSize[j]: 
					wstIdx = j 

		# إن كان بالإمكان العثور على كتلة للعملية الحالية 
		if wstIdx != -1: 
			
			# إسناد الكتلة j إلى العملية p[i]  
			allocation[i] = wstIdx 

			# تقليص الذاكرة المتوفّرة في هذه الكتلة 
			blockSize[wstIdx] -= processSize[i] 

	print("Process No. Process Size Block no.") 
	for i in range(n): 
		print(i + 1, "		 ", 
			processSize[i], end = "	 ") 
		if allocation[i] != -1: 
			print(allocation[i] + 1) 
		else: 
			print("Not Allocated") 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	blockSize = [100, 500, 200, 300, 600] 
	processSize = [212, 417, 112, 426] 
	m = len(blockSize) 
	n = len(processSize) 

	worstFit(blockSize, m, processSize, n)

• جافا:

public class GFG 
{ 
	static void worstFit(int blockSize[], int m, int processSize[], 
													int n) 
	{ 
		//  تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
		int allocation[] = new int[n]; 
	
		//  لا تعيّن أي كتلة لأي عملية في بداية الأمر
		for (int i = 0; i < allocation.length; i++) 
			allocation[i] = -1; 
	
		// اختيار كل عملية والبحث عن الكتل الملائمة 
		// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
		for (int i=0; i<n; i++) 
		{ 
			// البحث عن أفضل كتلة تلائم العملية الحالية
			int wstIdx = -1; 
			for (int j=0; j<m; j++) 
			{ 
				if (blockSize[j] >= processSize[i]) 
				{ 
					if (wstIdx == -1) 
						wstIdx = j; 
					else if (blockSize[wstIdx] < blockSize[j]) 
						wstIdx = j; 
				} 
			} 
	
			// إن كان بالإمكان العثور على كتلة للعملية الحالية
			if (wstIdx != -1) 
			{ 
				// إسناد الكتلة j إلى العملية p[i] 
				allocation[i] = wstIdx; 
	
				//  تقليص الذاكرة المتوفّرة في هذه الكتلة
				blockSize[wstIdx] -= processSize[i]; 
			} 
		} 
	
		System.out.println("\nProcess No.\tProcess Size\tBlock no."); 
		for (int i = 0; i < n; i++) 
		{ 
			System.out.print(" " + (i+1) + "\t\t" + processSize[i] + "\t\t"); 
			if (allocation[i] != -1) 
				System.out.print(allocation[i] + 1); 
			else
				System.out.print("Not Allocated"); 
			System.out.println(); 
		} 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int blockSize[] = {100, 500, 200, 300, 600}; 
		int processSize[] = {212, 417, 112, 426}; 
		int m = blockSize.length; 
		int n = processSize.length; 
		
		worstFit(blockSize, m, processSize, n); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Process No.    Process Size    Block no.
   1        212        5
   2        417        2
   3        112        5
   4        426        Not Allocated

خوارزمية الملاءمة التالية

طريقة الملاءمة التالية هي نسخة معدّلة من طريقة الملاءمة الأولى، إذ تبدأ هذه الطريقة -كما هو الحال في طريقة الملاءمة الأولى- بالبحث عن جزء شاغر في الذاكرة، ولكن الفرق هو أنّ الاستدعاء الثاني لهذه الطريقة يبدأ بالبحث من المكان الذي توقفت فيه سابقًا، وليس من البداية. وتستفيد هذه الطريقة من المؤشر المتنقل، إذ يتنقل المؤشر عبر سلسلة الذاكرة بحثًا عن المكان الملائم التالي. ويساعد هذا في تجنب استخدام الذاكرة من بداية سلسلة الكتل الفارغة دائمًا.

خوارزمية الملاءمة الأولى خوارزمية سريعة وواضحة، ولكنّها تميل إلى تقسيم جزء كبير من الأقسام الفارغة إلى أجزاء أصغر ونتيجة لذلك لن تحصل العمليات التي تحتاج إلى أجزاء كبيرة من الذاكرة على أي مكان فيها، حتى لو كان مجموع جميع القطع الصغير أكبر من الحجم المطلوب لتنفيذ العملية، وتسمى هذه الحالة بمشكلة التجزئة الخارجية external fragmentation.

تميل خوارزمية الملاءمة الأولى كذلك إلى حجز أجزاء الذاكرة الموجودة في بدايتها، ما يؤدي إلى تكوّن المزيد من الأجزاء الداخلية internal fragments في بداية الذاكرة. تحاول خوارزمية الملاءمة اللاحقة معالجة هذه المشكلة وذلك بأن تبدأ البحث عن الأجزاء الشاغرة من آخر موقع وصلت إليه وليس من الموقع الأول في الذاكرة.

تعدّ خوارزمية الملاءمة التالية خوارزمية بحث سريعة جدًّا، وتتفوق في سرعتها على خوارزميتي الملاءمة الأولى والملاءمة الفضلى.

مثال:

Input :  blockSize[] = {5, 10, 20};
     processSize[] = {10, 20, 30};
Output:
Process No.     Process Size    Block no.
 1              10              2
 2              20              3
 3              30              Not Allocated

خطوات الخوارزمية

1. تُغذّى الخوارزمية بكتل الذاكرة المتاحة مع حجم كل كتلة إضافة إلى العمليات مع حجم كل عملية.
2. تهيّئ الخوارزمية بعدها جميع كتل الذاكرة لتكون شاغرة.
3. تبدأ الخوارزمية باختيار كلّ عملية والتحقق من إمكانية إسنادها إلى الكتلة الحالية، فإن تحقق ذلك تُحجز الذاكرة المطلوبة لهذه العملية، وتعيد الخوارزمية الكرّة مع العملية التالية ولكن من الموقع الذي انتهت إليه وليس من بداية الذاكرة.
4. إن كان حجم الكتلة الحالية أصغر من المطلوب تستمر الخوارزمية بالبحث عن كتل أخرى.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void NextFit(int blockSize[], int m, int processSize[], int n) 
{ 
	// تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 
	int allocation[n], j = 0; 

	// لا تعيّن أي كتلة لأي عملية في بداية الأمر
	memset(allocation, -1, sizeof(allocation)); 

	//  اختيار كل عملية والبحث عن الكتل الملائمة
	// بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
	for (int i = 0; i < n; i++) { 

		// لا تبدأ البحث من البداية
		while (j < m) { 

			if (blockSize[j] >= processSize[i]) { 

				// إسناد الكتلة j إلى العملية p[i]
				allocation[i] = j; 

				// تقليص الذاكرة المتوفّرة في هذه الكتلة
				blockSize[j] -= processSize[i]; 

				break; 
			} 

			// تساعد هذه العملية في التنقل عبر الكتل
			// ابتداءً من الكتلة الأولى وذلك بعد الوصول إلى نهاية الكتل
			j = (j + 1) % m; 
		} 
	} 

	cout << "\nProcess No.\tProcess Size\tBlock no.\n"; 
	for (int i = 0; i < n; i++) { 
		cout << " " << i + 1 << "\t\t" << processSize[i] 
			<< "\t\t"; 
		if (allocation[i] != -1) 
			cout << allocation[i] + 1; 
		else
			cout << "Not Allocated"; 
		cout << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int blockSize[] = { 5, 10, 20 }; 
	int processSize[] = { 10, 20, 5 }; 
	int m = sizeof(blockSize) / sizeof(blockSize[0]); 
	int n = sizeof(processSize) / sizeof(processSize[0]); 

	NextFit(blockSize, m, processSize, n); 

	return 0; 
}

• بايثون:

def NextFit(blockSize, m, processSize, n): 
	
	# تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة 

	#  لا تعيّن أي كتلة لأي عملية في بداية الأمر
	allocation = [-1] * n 
	j = 0

	# اختيار كل عملية والبحث عن الكتل الملائمة
	#  بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية 
	for i in range(n): 

		# لا تبدأ البحث من البداية 
		while j < m: 

			if blockSize[j] >= processSize[i]: 

				# إسناد الكتلة j إلى العملية p[i] 
				allocation[i] = j 

				#  تقليص الذاكرة المتوفّرة في هذه الكتلة
				blockSize[j] -= processSize[i] 

				break

			# تساعد هذه العملية في التنقل عبر الكتل
			# ابتداءً من الكتلة الأولى وذلك بعد الوصول إلى نهاية الكتل
			j = (j + 1) % m 

	print("Process No. Process Size Block no.") 
	for i in range(n): 
		print(i + 1, "		 ", processSize[i], 
									end = "	 ") 
		if allocation[i] != -1: 
			print(allocation[i] + 1) 
		else: 
			print("Not Allocated") 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	blockSize = [5, 10, 20] 
	processSize = [10, 20, 5] 
	m = len(blockSize) 
	n = len(processSize) 

	NextFit(blockSize, m, processSize, n)

• جافا:

import java.util.Arrays; 

public class GFG { 

	static void NextFit(int blockSize[], int m, int processSize[], int n) { 
		//  تخزن هذه المصفوفة معرّف الكتلة التي حُجزت لعملية معينة  
		int allocation[] = new int[n], j = 0; 

		// لا تعيّن أي كتلة لأي عملية في بداية الأمر
		Arrays.fill(allocation, -1); 

		// اختيار كل عملية والبحث عن الكتل الملائمة
		//  بالاعتماد على حجم الكتلة ثم إسنادها إلى العملية
		for (int i = 0; i < n; i++) { 

			// لا تبدأ البحث من البداية
			while (j < m) { 

				if (blockSize[j] >= processSize[i]) { 

					// إسناد الكتلة j إلى العملية p[i] 
					allocation[i] = j; 

					//  تقليص الذاكرة المتوفّرة في هذه الكتلة
					blockSize[j] -= processSize[i]; 

					break; 
				} 

				// تساعد هذه العملية في التنقل عبر الكتل
				// ابتداءً من الكتلة الأولى وذلك بعد الوصول إلى نهاية الكتل
				j = (j + 1) % m; 
			} 
		} 

		System.out.print("\nProcess No.\tProcess Size\tBlock no.\n"); 
		for (int i = 0; i < n; i++) { 
			System.out.print( i + 1 + "\t\t" + processSize[i] 
					+ "\t\t"); 
			if (allocation[i] != -1) { 
				System.out.print(allocation[i] + 1); 
			} else { 
				System.out.print("Not Allocated"); 
			} 
			System.out.println(""); 
		} 
	} 

// اختبار التابع السابقة 
	static public void main(String[] args) { 
		int blockSize[] = {5, 10, 20}; 
		int processSize[] = {10, 20, 5}; 
		int m = blockSize.length; 
		int n = processSize.length; 
		NextFit(blockSize, m, processSize, n); 
	} 
}

مصادر

• صفحة Partition allocation methods في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Program for First Fit algorithm in Memory Management في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Program for Best Fit algorithm in Memory Management في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Program for Worst Fit algorithm in Memory Management في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Program for Next Fit algorithm in Memory Management في توثيق الخوارزميات في موقع GeeksforGeeks.