memory.cpp

该小程序完好的模拟了内存管理系统的相关功能

#include <iostream>
#include <new>
#include "memory.h"

struct RegionPointerList * findposition(int s,struct RegionPointerList * head)
{
	struct RegionPointerList * p = NULL;
	while(head != NULL){
		if(s < (head->data)->start)
			break;
		p = head;
		head = head->next;
	}
	return p;
}
struct region * findpos(struct region * element,struct region * head,int flag)
{
	struct region * p = NULL;
	while(head != NULL){
		if(flag == 0)
		{
			if(element->start < head->start)
				break;
		}
		else
		{
			if(element->length < head->length)
				break;
		}
		p = head;
		head = head->next;
	}
	return p;
}
void putout1(struct region * head)
{
	if(head == NULL){
		cout <<  "region list is null...\n" << endl;
	}
	else{
		while(head != NULL)
		{
			if(head->job == 0)
				cout << "begin:" << head->start << "K\tlength:" << head->length << "K\tleisure\t\t" << endl;
			else
				cout << "begin:" << head->start << "K\tlength:" << head->length << "K\tuse:Job" << head->job << endl;
			head = head->next;
		}
	}
}
void putout2(struct RegionPointerList * head)
{
	struct region * data_temp;
	if(head == NULL)
		cout << "region pointer list is null..." << endl;
	else{
		while(head != NULL)
		{
			data_temp = head->data;
			if(data_temp->job == 0)
				cout << "begin:" << data_temp->start << "K\tlength:" << data_temp->length << "K\tleisure\t\t" << endl;
			else
				
			cout << "begin:" << data_temp->start << "K\tlength:" << data_temp->length << "K\tuse:Job" << data_temp->job << endl;

			head = head->next;
		}
	}
}
struct RegionPointerList * combination(struct region * leisure_temp,struct region * used_temp)
{
	struct RegionPointerList * previcious;
	struct RegionPointerList * temp;

	if(used_temp != NULL)
	{
		thewhole = (struct RegionPointerList *)malloc(sizeof(struct RegionPointerList));
		thewhole->data = used_temp;
		thewhole->next = NULL;
		previcious = thewhole;
		used_temp = used_temp->next;
		while(used_temp != NULL){
			temp = (struct RegionPointerList *)malloc(sizeof(struct RegionPointerList));
			temp->data = used_temp;
			temp->next = NULL;
			previcious->next = temp;
			previcious = temp;

			used_temp = used_temp->next;
		}
	}

	while(leisure_temp != NULL){
		struct region * leisure_next = leisure_temp->next;
		struct RegionPointerList * pos = findposition(leisure_temp->start,thewhole);

		if(pos == NULL)
		{
			temp = (struct RegionPointerList *)malloc(sizeof(struct RegionPointerList));
			temp->data = leisure_temp;
			temp->next = thewhole;

			thewhole = temp;
		}
		else
		{
			temp = (struct RegionPointerList *)malloc(sizeof(struct RegionPointerList));
			temp->data = leisure_temp;
			temp->next = pos->next;

			pos->next = temp;
		}

		leisure_temp = leisure_next;
	}

	return thewhole;
}
struct region * insert()
{
	

	struct region * p = NULL;
	struct region * n = NULL;
	struct region * current = new region;
	current->start = 0;
	current->length = 640;
	current->job = 0;
	if(p == NULL){            
		current->next = n;
		return current;
	}
	else{
		if(p->next == NULL){         
			current->next = NULL;
			p->next = current;
		}
		else{             
			current->next = p->next;
			p->next = current;
		}
		return current;
	}



}
struct region * insert_list(struct region * element,struct region * list,int flag)
{
	if(list == NULL)
		list = element;
	else{
		struct region * pos = findpos(element,list,flag);
		if(pos == NULL){
			element->next = list;
			list = element;
		}
		else{
			element->next = pos->next;
			pos->next = element;
		}
	}
	return list;
} 
void free_regionList(struct region * head)
{
	struct region * temp;
	while(head != NULL){
		temp = head;
		head = head->next;
		free(temp);
	}
}

int memeryAlloc(int length,int job,int flag)
{
	struct region * used_element;
	struct region * free_element;

	struct region * head = leisure;
	struct region * head_temp = used;
	struct region * p = NULL;


	 
	while(head_temp != NULL)
	{
		if(head_temp->job == job)
			return 2;
		head_temp = head_temp->next;
	}

 
	while(head != NULL)
	{
		if(head->length >= length)
			break;
		p = head;
		head = head->next;
	}

	if(head != NULL)
	{
	 
		if(p == NULL) 
		{
			leisure = leisure->next;
		}
		else
		{
			p->next = head->next;
		}
		head->next = NULL;
	}
	else return 0;

	 
	used_element = (struct region * )malloc(sizeof(struct region));
	used_element->start = head->start;
	used_element->length = length;
	used_element->job = job;
	used_element->next = NULL;

	used = insert_list(used_element,used,0);


	 
	if(head->length > length){
		free_element = (struct region * )malloc(sizeof(struct region));
		free_element->start = head->start + length;
		free_element->length = head->length - length;
		free_element->job = 0;
		free_element->next = NULL;

		leisure = insert_list(free_element,leisure,flag);
	}

	 
	free(head);

	return 1;
}
int memeryFree(int job,int flag)
{
	struct region * used_element;
	struct region * free_element;
	struct region * head = used;
	struct region * p = NULL;

	struct region * previcious1 = NULL;
	struct region * current1 = NULL;
	struct region * previcious2 = NULL;
	struct region * current2 = NULL;

	 
	while(head != NULL)
	{
		if(head->job == job)
			break;
		p = head;
		head = head->next;
	}

	if(head != NULL)
	{
		 
		if(p == NULL) 
		{
			used = used->next;
		}
		else
		{
			p->next = head->next;
		}
		head->next = NULL;
	}
	else return 0;

	 
	used_element = head;
	free_element = (struct region * )malloc(sizeof(struct region));
	free_element->start = used_element->start;
	free_element->length = used_element->length;
	free_element->job = 0;
	free_element->next = NULL;


	 
	head = leisure;
	p = NULL;

	while(head != NULL)
	{
		if(head->start + head->length == used_element->start)
		{
			previcious1 = p;
			current1 = head;
		}
		if(used_element->start + used_element->length == head->start)
		{
			previcious2 = p;
			current2 = head;
		}
		p = head;
		head = head->next;
	}


	 
	if( current1 != NULL )
	{
		 
		if( previcious1 == NULL )
			leisure = leisure->next;
		else
			previcious1->next = current1->next;
		current1->next = NULL;

		 
		free_element->start = current1->start;
		free_element->length = free_element->length + current1->length;
	}
	if( current2 != NULL )
	{
		 
		if( previcious2 == NULL )
			leisure = leisure->next;
		else
			previcious2->next = current2->next;
		current2->next = NULL;

		 
		free_element->length = free_element->length + current2->length;
	}

	 
	leisure = insert_list(free_element,leisure,flag);

	 
	free(used_element);

	return 1;
}


int main()
{

	leisure = insert();
	used = NULL;
	
	cout << "******************************************************************************************************" << endl;
	cout << "操作系统第二次作业" << endl;
	cout << endl;	
	cout << "请输入数据,数据格式为 : 0(作业号) 0(1为申请内存,0为释放内存) 0(单位为K,申请或释放的内存大小)" << endl;
	cout << endl;	
	cout << "例如 作业2 申请 100K 的内存空间 : 2 1 100" << endl;
	cout << endl;	
	cout << "例如 作业5 释放 60K  的内存空间 : 5 0 60 " << endl;
	cout << endl;	
	cout << "每输入一条,按回车结束,系统将会显示内存分配结果" << endl;
	cout << endl;	
	cout << "!!注意: 输入数据格式：作业号(大于零) 分区长度(大于零)"<< endl;
	cout << "******************************************************************************************************" << endl;
	cout << endl;	

	int job;
	int apply_free;
	int length;
	int flag;

	cout << "请选择分配算法:输入0(FIFO最先适配算法) 输入1(LRU最优适配算法)" << endl;
	cin >> flag;

	while(flag != 0 && flag != 1)
	{
		cout << "数据输入错误，请参照提示重新输入" << endl;
		cin >> flag;
	}

	if(flag == 0)
		cout << "选择最先适配算法--->请输入请求队列数据:输入 0 0 0 回车" <<endl;
	if(flag == 1)
		cout << "选择最优适配算法--->请输入请求队列数据:输入 0 0 0 回车" <<endl;

	while(1)
	{
		cin >> job >> apply_free >> length;

		if(job == 0 && apply_free == 0 && length == 0)break;

		while(job<=0 || (apply_free != 0 && apply_free != 1) || length<=0)
		{
			cout << "数据输入错误，请参照提示重新输入" <<endl;
			cin >> job >> apply_free >> length;
			//if(job == 0 && apply_free == 0 && length == 0)return;
		}
		if (apply_free == 1)
		{
			int backvalue1 = memeryAlloc(length,job,flag);
			if(backvalue1 == 0)
			{
				cout << endl;	
				cout <<"没有符合条件的空闲分区可供分配，请等待释放..."<<endl;
				cout << endl;	
				continue;
			}
			if(backvalue1 == 2)
			{
				cout << endl;
				cout <<"输入作业号已存在于占用分区链表，请重新输入..."<<endl;
				cout << endl;
				continue;
			}
		}
		if(apply_free == 0)
		{
			int backvalue2 = memeryFree(job,flag);
			if(backvalue2==0)
			{
				cout << endl;
				cout << "没有与指定作业号符合的占用分区，请重新输入..."<<endl;
				cout << endl;
				continue;
			}
		}
		combination(leisure,used);

		cout << endl;
		cout << "******************************************************************************************************" << endl;
		cout << "the leisure address:" << endl;
		putout1(leisure);
		cout << endl;

		cout <<"the used address:" << endl;
		putout1(used);
		cout << endl;

		cout <<"the thewhole address:" << endl;
		cout <<"low address:" << endl;
		putout2(thewhole);
		cout <<"high address" << endl;
		cout << "******************************************************************************************************" << endl;
		cout << endl;
		 
		struct RegionPointerList * temp;
		struct RegionPointerList * temphead;
		temphead = thewhole;
		while(temphead != NULL)
		{
			temp = temphead;
			temphead = temphead->next;
			free(temp);
		}
		thewhole = NULL;


	}
	free_regionList(leisure);
	free_regionList(used);
	leisure = NULL;
	used = NULL;
	return 0;
}