Dynamic partitioned storage management

The free partition table is as follows:

1. NF

1) NF theory

In order to avoid leaving many small space partitions in the low address part and reduce the cost of finding available free partitions, when allocating memory space for the process, the cyclic first adaptation algorithm no longer starts from the head of the chain every time, but starts from the next free partition of the last found free partition until a free partition that can meet the requirements is found, Set aside a memory space equal to the size of the request and allocate it to the job.

2) NF thought

In order to realize the algorithm, the starting lookup pointer should be set to indicate the free partition for the next starting lookup, and the circular lookup method should be adopted, that is, if the size of the last (tail) free partition still cannot meet the requirements, it should return to the first free partition to compare whether its size meets the requirements. Once found, the start lookup pointer should be adjusted.

3) Specific implementation process of NF algorithm

a) An idle partition chain should be initialized before NF;
Idle partition chain structure:
typedef struct free_excel {
int number; // Partition number
double begin_address; // Starting address
double scale; // length
int partition_status; // Partition status
struct free_excel * next;
} Sqfree_ex, *Sqfree;
b) When a job applies for memory space, it should find the memory size for which memory space can be allocated from the starting search pointer. If the found memory space size - the memory space size applied by the job > the segmentation threshold is 0.3k, the found memory space size needs to be segmented again. Otherwise, the memory space will be allocated to the job directly. If no memory space can be found to meet the size of the job, its allocation is considered to have failed.
In the specific implementation, the linked list is used to represent the free partition, and another linked list is used to store the job with the allocated memory free size. Each time the allocation is successful, the job is stored in the linked list with the allocated memory space, and the job is removed from the linked list every time the job is completed.
Use a pointer to record the starting query address. This search pointer starts from the node and determines whether the next address can be assigned to the job each time. Because the head node does not store the size of memory space, because it is set as a one-way linked list, one advantage of this is that if you find a memory space that can be allocated and the segmentation threshold is less than 0.3, you can remove the memory space from the linked list. Otherwise, you need to find its previous node to delete the memory space. That is, judge the next, judge that the segmentation threshold is less than 0.3, and delete the next; For one-way linked list, it is troublesome to judge and delete the current.
c) After the job is completed, the memory space of the job needs to be reclaimed
The recycling process is complex, which can be divided into four cases:
i. The recycle partition is adjacent to the previous free partition of the insertion point. At this time, the recycle partition should be merged with the previous partition of the insertion point. There is no need to allocate new table entries to the recycle partition, but only need to modify the size of the previous partition.
ii. The recycle partition is adjacent to the next free partition of the insertion point. At this time, the two partitions can also be merged to form a new free partition, but the first address of the recycle area is used as the first address of the new free area, and the size is the sum of the two.
iii. The recycle area is adjacent to the front and rear partitions of the insertion point at the same time. At this time, the three partitions are merged, the table item and the first address of the first partition of the three partitions are used, and the last table item in the three partitions is cancelled. The size is the sum of the two partitions in the original free linked list + the memory space to be recycled.
iv. if the recycling area is not adjacent to any partition, a new table item should be established for the recycling area, fill in the first address and size of the recycling area, and insert it into the appropriate position in the idle chain according to its first address.
In the specific code implementation, it is divided into three cases: the first non head node partition is considered, the tail node partition is considered, and the above two nodes are considered. When considering the first non head node, we only need to consider whether the end of the recycling area can be adjacent to the first non head node partition. When considering the tail node partition, we only need to consider whether the end of the tail node can be adjacent to the first address of the recycling partition. When considering the above two node partitions, we need to consider the above four situations.

4) NF algorithm core code

int NF(Sqfree &s, job &j, Sqjob &ljob) { //Cycle first adaptation
	Sqfree begin = flag;
	for (int i = 0; i < Sqfree_sum; i++) {
		if (begin->next != NULL && begin->next->scale >= j.request)	{
			if (begin->next->scale - j.request > limit) {    //The rest is too large and needs to be partitioned
				j.begin_address = begin->next->begin_address;
				j.end_address = begin->next->begin_address + j.request;
				begin->next->begin_address = begin->next->begin_address + j.request;
				begin->next->partition_status = 1;
				begin->next->scale = begin->next->scale - j.request;
				insert_Sqjob(ljob , j);
				flag = begin;
				cout << "Allocation succeeded" << endl;
				return 1;}
			else if (begin->next->scale - j.request <= limit) {
				j.begin_address = begin->next->begin_address;
				j.end_address = j.begin_address + begin->next->scale;
				begin->next = begin->next->next;
				Sqfree_sum--;
				insert_Sqjob(ljob , j);
				flag = begin;
				cout << "Allocation succeeded" << endl;
				return 1;
			}
	    }
		else if (begin->next == NULL){
			begin = s;
		}
		else {
			begin = begin->next;
		}
	}
	cout << "allocation failed" << endl;
	return 0;
 }


void delete_job(Sqjob &ljob, Sqjob j) { //Remove the job from the job already assigned
	Sqjob head = ljob;
	while ( head != NULL){
		if ( head->next == j) {
			head->next = head->next->next;
		}
		head = head->next;
	}
}

int recovery(Sqfree &s, Sqjob &ljob) {
	sortSqfree_bgadd(s);
	Sqfree pre = s;
	Sqfree head = s->next;
	Sqjob  temp = recovery_job(ljob);
	if (temp != NULL) {
		while (head != NULL)
		{
			if (head == s->next) { //If it is the first node, consider its previous situation
				if (head->begin_address > temp->end_address) { //Add a node directly in front of it
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head;
					s->next = newnode;
					Sqfree_sum++;
					break;
				} else if (head->begin_address == temp->end_address) {  //Just connect to the front
					head->begin_address = temp->begin_address;
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				}
			} else if(pre != s) {
				if (pre->begin_address + pre->scale == temp->begin_address&&head->begin_address==temp->end_address) {
					pre->scale = pre->scale + temp->end_address - temp->begin_address + head->scale;
					pre->next = head->next;
				    Sqfree_sum--;
					break;
				} else if (pre->begin_address + pre->scale == temp->begin_address) {
					pre->scale = pre->scale + temp->end_address - temp->begin_address;
					break;
				} else if (head->begin_address == temp->end_address) {
					head->begin_address = temp->begin_address;
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				} else if (pre->begin_address + pre->scale<temp->begin_address && temp->end_address<head->begin_address) {
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head;
					pre->next = newnode;
					Sqfree_sum++;
					break;
				}
			} else if (head->next == NULL) {
				if (head->begin_address + head->scale == temp->begin_address) {
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				} else {
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head->next;
					head->next = newnode;
					Sqfree_sum++;
					break;
				}
			}
			head = head->next;
			pre = pre->next;
		}
		delete_job(ljob, temp);
	} else {
		cout << "The job cannot be found,Cannot recycle" << endl;
	}
	return 0;
}

2. WF

1) WF theory

Because the strategy of selecting free partition in the worst-case adaptation algorithm is just opposite to the best adaptation algorithm: when scanning the whole free partition list or linked list, it always selects a largest free area and divides part of the storage space for jobs, so that there is a lack of large free partition in the memory, so it is called the worst-case adaptation algorithm.

2) WF thought

The worst-case adaptive allocation algorithm only needs to form a chain of free partitions according to their capacity from large to small, as long as the first partition can meet the job requirements.

3) Specific implementation process of WF algorithm

a) In WF and NF, an idle partition chain should be initialized first;
Idle partition chain structure:
typedef struct free_excel {
int number; // Partition number
double begin_address; // Starting address
double scale; // length
int partition_status; // Partition status
struct free_excel * next;
} Sqfree_ex, *Sqfree;
b) When the job needs to apply for large memory space, the free partition chain should be sorted according to the capacity from large to small,
In order to realize this process, a variable is set to record the number of non head nodes in the free partition chain. After recording the number of non head nodes in the free partition chain, the bubble method can be used to sort.
Because it is better to output the address from small to large during output, a function is also written to output the free linked list from small to large, which is also operated by bubbling method.
c) For memory allocation, you only need to judge whether the first non head node can be allocated to the job applying for memory free size each time. If the found memory space size - the memory space size applied by the job > the segmentation threshold is 0.3k, the found memory space size needs to be segmented again. Otherwise, the memory space will be allocated to the job directly. If the memory space of the first non head node can meet the job, it is considered that its allocation has failed.
d) After the job is completed, the memory space of the job needs to be reclaimed. The process is the same as that of NF
The recycling process is complex, which can be divided into four cases:
v. The recycle partition is adjacent to the previous free partition of the insertion point. At this time, the recycle partition should be merged with the previous partition of the insertion point. There is no need to allocate new table entries to the recycle partition, but only need to modify the size of the previous partition.
vi. the recycle partition is adjacent to the next free partition of the insertion point. At this time, the two partitions can also be merged to form a new free partition, but the first address of the recycle area is used as the first address of the new free area, and the size is the sum of the two.
vii. The recycle area is adjacent to the front and rear partitions of the insertion point at the same time. At this time, the three partitions are merged. The table item and the first address of the first partition of the three partitions are used to cancel the last table item in the three partitions. The size is the sum of the two partitions in the original free linked list + the memory space to be recycled.
viii. The recycle area is not adjacent to any partition, so a new table item should be created for the recycle area, fill in the first address and size of the recycle area, and insert it into the appropriate position in the idle chain according to its first address.
In the specific code implementation, it is divided into three cases: the first non head node partition is considered, the tail node partition is considered, and the above two nodes are considered. When considering the first non head node, we only need to consider whether the end of the recycling area can be adjacent to the first non head node partition. When considering the tail node partition, we only need to consider whether the end of the tail node can be adjacent to the first address of the recycling partition. When considering the above two node partitions, we need to consider the above four situations.

4) WF algorithm core code

Because the code of partition recycling is the same as NF, it is not listed here.

int WF_allocation(Sqfree &s, Sqjob &ljob, job &j) {
	sortSqfree_scale(s);
    Sqfree head = s;
		if (head->next->scale >= j.request) {
			if (head->next->scale - j.request > limit) { //Memory space needs to be subdivided
				j.begin_address = head->next->begin_address;
				head->next->scale = head->next->scale - j.request;
				head->next->begin_address = head->next->begin_address + j.request;
				j.end_address = j.begin_address + j.request;
				insert_Sqjob(ljob,j);
				cout << "Allocation succeeded" << endl;
				return 1;
			} else {  //There is no need to subdivide the memory space
				j.begin_address = head->next->begin_address;
				j.end_address = head->next->begin_address + head->next->scale;
				head->next = head->next->next;
				insert_Sqjob(ljob, j);
				Sqfree_sum--;
				cout << "Allocation succeeded" << endl;
				return 1;
			}
		}
	cout << "allocation failed" << endl;
	return 0;
}
void sortSqfree_scale(Sqfree& s) {  //Sort by memory size
	Sqfree head = s->next;
	for (int j = 0; j < Sqfree_sum - 1; j++) { //Bubble sort from large to small
		head = s->next;
		for (int i = 0; i < Sqfree_sum - 1 - j; i++) {
			if (head->scale < head->next->scale) {
				Sqfree_ex temp;
				temp.scale = head->scale;
				temp.begin_address = head->begin_address;
				temp.partition_status = head->partition_status;
				temp.number = head->number;
				head->scale = head->next->scale;
				head->begin_address = head->next->begin_address;
				head->partition_status = head->next->partition_status;
				head->number = head->next->number;
				head->next->scale = temp.scale;
				head->next->begin_address = temp.begin_address;
				head->next->partition_status = temp.partition_status;
				head->next->number = temp.number;
			}
			head = head->next;
		}
	}
}
void sortSqfree_bgadd(Sqfree &s) { //Sort the free linked list according to the starting address
	Sqfree head = s->next;
	for (int j = 0; j < Sqfree_sum - 1; j++) { //Bubble sorting from small to large
		head = s->next;
		for (int i = 0; i < Sqfree_sum - 1 - j; i++) {
			if (head->begin_address > head->next->begin_address) {
				Sqfree_ex temp;
				temp.scale = head->scale;
			    temp.begin_address = head->begin_address;
				temp.partition_status = head->partition_status;
                temp.number = head->number;
		        head->scale = head->next->scale;
			    head->begin_address = head->next->begin_address;
				head->partition_status =head->next->partition_status;
				head->number = head->next->number;
	            head->next->scale = temp.scale;
				head->next->begin_address = temp.begin_address;
				head->next->partition_status = temp.partition_status;
				head->next->number = temp.number;
			}
			head = head->next;
		}
	}
}

The complete code is as follows:
You can modify the times of allocation and recycling according to your needs:

#include <iostream>
#include <string>
using namespace std;

typedef struct free_excel {
	int number;  //Partition number
	double begin_address; //Starting address
	double scale; //length
	int partition_status; //Partition status
	struct free_excel * next; 
} Sqfree_ex, *Sqfree;

typedef struct job {
	double request; //Request resource space
	string name; //Job / process name
	double begin_address; //First address
	double end_address;
	struct job* next;
}job, *Sqjob;

static Sqfree flag; //Marker pointer;
#define limit 0.3
static int number = 6;
static int Sqfree_number = 6; //The number of free linked list partition shall start from 6 at least
static int Sqfree_sum = 6; //Quantity in free linked list

int init_Sqfree(Sqfree &s) {      //Initialize free linked list
	Sqfree head = (Sqfree)malloc(sizeof(Sqfree_ex));
	if (head != NULL) {
		s = head;
		head->next = NULL;
		return 1;
    } else {
		return 0;
	}
}
int init_Sqjob(Sqjob& ljob); //Initializes the job chain that allocates space
void insert_Sqjob(Sqjob& ljob, job& j); //Tail insertion
void insert_Sqfree(Sqfree& s, Sqfree_ex excel[6]); //Initialize free partition table
void print_Sqfree(Sqfree s);  //Output free partition chain
void WF_init(Sqfree s, Sqfree_ex excel[6]);   //The worst-case adaptation algorithm initializes the linked list from large to small  
int WF_allocation(Sqfree& s, Sqjob& ljob, job& j); //WF
void sortSqfree_bgadd(Sqfree& s); //Sort the free linked list according to the starting address
void sortSqfree_scale(Sqfree& s); //Sort by memory size
Sqjob recovery_job(Sqjob& ljob); //Reclaim memory input
void delete_job(Sqjob& ljob, Sqjob j);  //Remove the job from the job already assigned
int recovery(Sqfree& s, Sqjob& ljob); //Memory recycling
void init_job(job& j);
void print_Sqjob(Sqjob ljob);
int NF(Sqfree& s, job& j, Sqjob& ljob); //Cycle first adaptation

int init_Sqjob(Sqjob  &ljob) {  
	Sqjob head = (Sqjob)malloc(sizeof(job));
	if (head != NULL) {
		ljob = head;
		head->next = NULL;
		return 1;
	} else
	{
		return 0;
	}
}

void insert_Sqjob(Sqjob& ljob, job &j) {  
	Sqjob head = ljob;
	Sqjob temp;
	while (head->next != NULL) {
		head = head->next;
	}
	temp = &j;
	temp->next = head->next;
	head->next = temp;
}

void insert_Sqfree(Sqfree &s, Sqfree_ex excel[6]) { 
	Sqfree head = s;
	Sqfree temp;
	for (int i = 0; i < 6; i++){
		temp = &excel[i];
		temp->next = head->next;
		head->next = temp;
		head = head->next;
	}
}

void print_Sqfree(Sqfree s) {
	sortSqfree_bgadd(s);
	Sqfree head = s->next;
	cout << "Partition number" <<'\t'<<'\t'<< "Starting address" << '\t' << "length" <<'\t'<<'\t'<< "state" << endl;
	while (head != NULL) {
		cout << head->number<<'\t'<<'\t'<<head->begin_address<<'\t'<<'\t'<<head->scale<<'\t'<<'\t';
		if (head->partition_status == 1) {
			cout << "free" << endl;
		}
		else {
			cout << "Assigned" << endl;
		}
		head = head->next;
	}
}

void WF_init(Sqfree s, Sqfree_ex excel[6]) {   
	Sqfree head = s;
	Sqfree temp;
	for (int j = 0; j < 6 - 1; j++) {   //Bubble sorting from small to large
		for (int i = 0; i < 6 - 1 - j; i++) {
			if (excel[i].scale < excel[i + 1].scale) {
				Sqfree_ex temp;
				temp = excel[i];
				excel[i] = excel[i + 1];
				excel[i + 1] = temp;
			}
		}
	}
	for (int i = 0; i < 6; i++) {
		temp = &excel[i];
		temp->next = head->next;
		head->next = temp;
		head = head->next;
	}
}


int WF_allocation(Sqfree &s, Sqjob &ljob, job &j) {
	sortSqfree_scale(s);
    Sqfree head = s;
		if (head->next->scale >= j.request) {
			if (head->next->scale - j.request > limit) { //Memory space needs to be subdivided
				j.begin_address = head->next->begin_address;
				head->next->scale = head->next->scale - j.request;
				head->next->begin_address = head->next->begin_address + j.request;
				j.end_address = j.begin_address + j.request;
				insert_Sqjob(ljob,j);
				cout << "Allocation succeeded" << endl;
				return 1;
			} else {  //There is no need to subdivide the memory space
				j.begin_address = head->next->begin_address;
				j.end_address = head->next->begin_address + head->next->scale;
				head->next = head->next->next;
				insert_Sqjob(ljob, j);
				Sqfree_sum--;
				cout << "Allocation succeeded" << endl;
				return 1;
			}
		}
	cout << "allocation failed" << endl;
	return 0;
}

void sortSqfree_bgadd(Sqfree &s) { 
	Sqfree head = s->next;
	for (int j = 0; j < Sqfree_sum - 1; j++) { //Bubble sorting from small to large
		head = s->next;
		for (int i = 0; i < Sqfree_sum - 1 - j; i++) {
			if (head->begin_address > head->next->begin_address) {
				Sqfree_ex temp;
				temp.scale = head->scale;
			    temp.begin_address = head->begin_address;
				temp.partition_status = head->partition_status;
                temp.number = head->number;
		        head->scale = head->next->scale;
			    head->begin_address = head->next->begin_address;
				head->partition_status =head->next->partition_status;
				head->number = head->next->number;
	            head->next->scale = temp.scale;
				head->next->begin_address = temp.begin_address;
				head->next->partition_status = temp.partition_status;
				head->next->number = temp.number;
			}
			head = head->next;
		}
	}
}

void sortSqfree_scale(Sqfree& s) {  
	Sqfree head = s->next;
	for (int j = 0; j < Sqfree_sum - 1; j++) { //Bubble sorting from small to large
		head = s->next;
		for (int i = 0; i < Sqfree_sum - 1 - j; i++) {
			if (head->scale < head->next->scale) {
				Sqfree_ex temp;
				temp.scale = head->scale;
				temp.begin_address = head->begin_address;
				temp.partition_status = head->partition_status;
				temp.number = head->number;
				head->scale = head->next->scale;
				head->begin_address = head->next->begin_address;
				head->partition_status = head->next->partition_status;
				head->number = head->next->number;
				head->next->scale = temp.scale;
				head->next->begin_address = temp.begin_address;
				head->next->partition_status = temp.partition_status;
				head->next->number = temp.number;
			}
			head = head->next;
		}
	}
}

Sqjob recovery_job(Sqjob &ljob) { 
	string temp;
	cout << "Please enter a job to recycle:";
	cin >> temp;
	Sqjob head = ljob->next;
	while (head != NULL){
		if (head->name == temp){
			return head;
		}
		head = head->next;
	}
	return NULL;
}

void delete_job(Sqjob &ljob, Sqjob j) {
	Sqjob head = ljob;
	while ( head != NULL){
		if ( head->next == j) {
			head->next = head->next->next;
		}
		head = head->next;
	}
}

int recovery(Sqfree &s, Sqjob &ljob) {
	sortSqfree_bgadd(s);
	Sqfree pre = s;
	Sqfree head = s->next;
	Sqjob  temp = recovery_job(ljob);
	if (temp != NULL) {
		while (head != NULL)
		{
			if (head == s->next) { //If it is the first node, consider its previous situation
				if (head->begin_address > temp->end_address) { //Add a node directly in front of it
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head;
					s->next = newnode;
					Sqfree_sum++;
					break;
				} else if (head->begin_address == temp->end_address) {  //Just connect to the front
					head->begin_address = temp->begin_address;
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				}
			} else if(pre != s) {
				if (pre->begin_address + pre->scale == temp->begin_address&&head->begin_address==temp->end_address) {
					pre->scale = pre->scale + temp->end_address - temp->begin_address + head->scale;
					pre->next = head->next;
				    Sqfree_sum--;
					break;
				} else if (pre->begin_address + pre->scale == temp->begin_address) {
					pre->scale = pre->scale + temp->end_address - temp->begin_address;
					break;
				} else if (head->begin_address == temp->end_address) {
					head->begin_address = temp->begin_address;
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				} else if (pre->begin_address + pre->scale<temp->begin_address && temp->end_address<head->begin_address) {
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head;
					pre->next = newnode;
					Sqfree_sum++;
					break;
				}
			} else if (head->next == NULL) {
				if (head->begin_address + head->scale == temp->begin_address) {
					head->scale = head->scale + temp->end_address - temp->begin_address;
					break;
				} else {
					Sqfree newnode = (Sqfree)malloc(sizeof(Sqfree_ex));
					newnode->begin_address = temp->begin_address;
					newnode->partition_status = 1;
					newnode->scale = temp->begin_address - temp->end_address;
					newnode->number=++Sqfree_number;
					newnode->next = head->next;
					head->next = newnode;
					Sqfree_sum++;
					break;
				}
			}
			head = head->next;
			pre = pre->next;
		}
		delete_job(ljob, temp);
	} else {
		cout << "The job cannot be found,Cannot recycle" << endl;
	}
	return 0;
}

void init_job(job &j) {
	cout << "Please enter the job name" << endl;
	cin >> j.name;
	cout << "Please enter the requested memory space" << endl;
	cin >> j.request;
}

void print_Sqjob(Sqjob ljob) {
	Sqjob head = ljob->next;
	while (head != NULL) {
		cout << "Job name:" << head->name<<'\t'<<"Requested memory space:"<<head->request<<'\t'<<"Start address:"<<head->begin_address<<'\t'
			<<"End address:"<<head->end_address<<endl;
		head = head->next;
	}
}

int NF(Sqfree &s, job &j, Sqjob &ljob) { 
	Sqfree begin = flag;
	for (int i = 0; i < Sqfree_sum; i++) {
		if (begin->next != NULL && begin->next->scale >= j.request)	{
			if (begin->next->scale - j.request > limit) {    //The rest is too large and needs to be partitioned
				j.begin_address = begin->next->begin_address;
				j.end_address = begin->next->begin_address + j.request;
				begin->next->begin_address = begin->next->begin_address + j.request;
				begin->next->partition_status = 1;
				begin->next->scale = begin->next->scale - j.request;
				insert_Sqjob(ljob , j);
				flag = begin;
				cout << "Allocation succeeded" << endl;
				return 1;}
			else if (begin->next->scale - j.request <= limit) {
				j.begin_address = begin->next->begin_address;
				j.end_address = j.begin_address + begin->next->scale;
				begin->next = begin->next->next;
				Sqfree_sum--;
				insert_Sqjob(ljob , j);
				flag = begin;
				cout << "Allocation succeeded" << endl;
				return 1;
			}
	    }
		else if (begin->next == NULL){
			begin = s;
		}
		else {
			begin = begin->next;
		}
	}
	cout << "allocation failed" << endl;
	return 0;
 }

int main() {
	Sqfree_ex excel[6] =   { 
							{1, 0, 10, 1, NULL},
							{2, 10, 18, 1, NULL},
							{3, 28, 16, 1, NULL},
							{4, 44, 6, 1, NULL},
							{5, 50, 21, 1, NULL},
							{6, 71, 30, 1, NULL}};
	Sqfree s;
	job  j1;
	job  j2;
	job  j3;
	Sqjob ljob;

	//initialization
	cout << "Initialize free partition table" << endl;
	init_Sqjob(ljob);
	init_Sqfree(s);
    insert_Sqfree(s, excel);
	print_Sqfree(s);
	flag = s;

	//Start WF processing
	cout << "----WF----" << endl;
	init_job(j1);
	WF_allocation(s, ljob, j1);
	print_Sqfree(s);
	//WF processing for the second time
	init_job(j2);
	WF_allocation(s, ljob, j2);
	print_Sqfree(s);
	//recovery
	recovery(s, ljob);
	print_Sqfree(s);
	//WF treatment for the third time
	init_job(j3);
	WF_allocation(s, ljob, j3);
	print_Sqfree(s);
	print_Sqjob(ljob);
	//For NF test, just cancel the following notes
	//cout << "----NF----" << endl;
	//init_job(j1);
	//NF(s , j1 , ljob);
	//print_Sqfree(s);
	//init_job(j2);
	//NF(s, j2, ljob);
	//print_Sqfree(s);
	//recovery(s , ljob);
	//print_Sqfree(s);
	//init_job(j3);
	//NF(s , j3, ljob);
	//print_Sqfree(s);
	//print_Sqjob(ljob);
	return 0;
}

Keywords: Operating System

Added by russellcox77777 on Tue, 08 Feb 2022 00:33:44 +0200