storem.cpp

存储管理参考程序,此程序只供参考

#include "iostream"
using namespace std;
#include "conio.h"
#include "malloc.h"
#include "stdio.h"
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
#define RAMSIZE 640    //初始内存大小
#define MINSIZE 5      //不可再切割的剩余分区的大小
#define ORDERSIZE 30   //操作序列的长度

typedef struct Node
{   //定义双向链表...
    int serial;       //空闲链分区序号
	int content;      //作业分区的内容   
    int addr;         //分区的地址       
	int size;         //分区的大小
    int origin;       //作业分区的空间分配源        
	int combine[2];   //被合并的分区
    struct Node *prior;    
	struct Node *next;
}Node, *Link;

typedef struct
{   //定义带头尾结点的双向链表...
    Link head;
    Link tail;
}DDLink;

int InitDDLink(DDLink &ddl)
{   //初始化带头尾结点的双向链表...
    ddl.head = ddl.tail = getpch(Node);
    ddl.head->prior = NULL;        ddl.head->next = ddl.tail;
    ddl.tail->prior = ddl.head;    ddl.tail->next = NULL;
    return 0;
}

int InitFreeLink(DDLink &Free)
{   //初始化带头尾结点的双向链表为空间空闲链...
    Node *p = getpch(Node);
    p->serial = 0;           p->content = -1;
    p->addr = 0;             p->size = RAMSIZE;
    p->origin = -1;          p->combine[0] = -1;
    p->combine[1] = -1;      Free.head->next = p;
    p->prior = Free.head;    p->next = Free.tail;
    Free.tail->prior = p;
    return 0;
}

int FreeLinkSort(DDLink &Free,int op)
{   //对空闲链中的结点按结点的某一属性排序...
    Node *p,*q,*tempp,*tempn;
    int m,n;
    p = Free.head->next;
    q = p->next;
    while(q != Free.tail)
	{
        if(op == 0){ m = p->addr; n = q->addr; }   //按分区地址从小到大排序
        else{ m = p->size; n = q->size; }          //按分区大小从小到大排序
        if(m > n)
		{   //排序...
            tempp = p->prior;    tempn = q->next;
            tempp->next = q;     q->prior = tempp;
            q->next = p;         p->prior  = q;
            p->next = tempn;     tempn->prior = p;
		}
        p = p->next;    q = q->next;
	}
    return 0;
}

int AssignSpace(DDLink &Free,DDLink &Use,int content,int size)
{   //从空闲链中给作业分配空间...
    Node *p,*q;
    p = Free.head->next;
    while(p != Free.tail && p->size - size <= MINSIZE)    //是否可切割和分配
        p = p->next;
	
	//分配空间给作业...
    q = getpch(Node);
    q->content = content;     q->addr = p->addr;
    q->size = size;           q->serial = -1;
    q->origin = p->serial;    q->combine[0] = -1;
    q->combine[1] = -1;   
    
	//分配空间给作业后...
	p->addr += size;          p->size -= size;         
	p = Use.tail->prior;

	//把作业结点链入作业链中...
    p->next = q;              q->prior = p;
    q->next = Use.tail;       Use.tail->prior = q;
    return 0;
}

int RecycleSpace(DDLink &Free,DDLink &Use,int content,int serial)
{   //空闲链回收作业分区释放的空间...
    Node *p,*q;

	//从作业链中找出回收区并从作业链中释放出来...
    q = Use.head->next;
    while(q != Use.tail && q->content != content)
        q = q->next;
    q->origin = -1;
    q->prior->next = q->next;
    q->next->prior = q->prior;
    p = Free.head->next;

	//从空闲链中找出回收区的插入点并回收回收区...
    while(p != Free.tail && p->addr < q->addr)
        p = p->next;
    if(q->addr - p->prior->addr == p->prior->size && p->addr - q->addr == q->size)
	{   //插入点与前后两分区都相邻...
		p->prior->size += q->size + p->size;
	    p->prior->combine[0] = q->content;
	    p->prior->combine[1] = p->serial;
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
        free(q);
	}
    else if(q->addr - p->prior->addr == p->prior->size)
    {   //插入点与前一分区都相邻...
	    p->prior->size += q->size;
	    p->prior ->combine[0] = q->content;
        free(q);
	}
    else if(p->addr - q->addr == q->size)
	{   //插入点与后一分区都相邻...
        p->size += q->size;
        p->addr = q->addr;
	    p->combine[0] = q->content;
        free(q);
	}
    else
	{   ////插入点与前后两分区都不相邻...
        q->serial = serial;    q->content = -1;
        p->prior->next = q;    q->prior = p->prior;
        q->next = p;           p->prior = q;
	}
    return 0;
}

int Print(DDLink ddl)
{   //打印链表中结点的信息...
    Node *p;
    p = ddl.head->next;
    cout << endl;
    if(p->serial != -1)
	    cout << " >>>>>空闲链分区如下<<<<< " << endl;
    if(p->content != -1)
	    cout << " >>>>>作业链分区如下<<<<< " << endl;
    while(p != ddl.tail)
	{
        if(p->serial != -1)
            cout << " 区号: " << p->serial;
        if(p->content != -1)
            cout << " 作业: " << p->content;
        cout << " 地址: " << p->addr;
        cout << " 容量: " << p->size;
	    if(p->origin != -1)
		{
		    cout << " 分配源: " << p->origin;
	   	    p->origin = -1;
		}
	    if(p->combine[0] != -1)
		{
		    cout << " 合并: 作业分区 " << p->combine[0];
	        if(p->combine[1] != -1)
			{
			    cout << " 和空闲分区 " << p->combine[1];
			    p->combine[1] = -1;
			}
		    p->combine[0] = -1;
		}
	cout << endl;
	p = p->next;
	}
    return 0;
}

struct OpOrder
{   //操作序列...
	int content;
	int size;
	int state;
};

OpOrder oporder[ORDERSIZE];

int ApplySpace(DDLink &Free,DDLink &Use,int &len)
{   //作业申请空间并用操作序列存储相关信息...
	int content,size;
	cout << endl << " >>>>>申请(作业为 0 时，终止申请)<<<<< " << endl;
	cout << endl << " 作业: ";
	cin >> content;
	int i = len;
	while(content != 0)
	{
	    cout << " 大小: ";
		cin >> size;
		oporder[i].content = content;
		oporder[i].size = size;
		oporder[i].state = 1;
		++i;
	    cout << endl << " 作业: ";
	    cin >> content;
	}
	len = i;
	return 0;
}

int ReleaseSpace(DDLink &Free,DDLink &Use,int &len)
{   //作业释放空间并用操作序列存储相关信息...
	int content;
	cout << endl << " >>>>>释放(作业为 0 时，终止释放)<<<<< " << endl;
	cout << endl << " 作业: ";
	cin >> content;
	int i = len;
	while(content != 0)
	{
		oporder[i].content = content;
		oporder[i].state = 0;
		++i;
		cout << endl << " 作业: ";
		cin >> content;
	}
	len = i;
	return 0;
}

int main()
{   //主函数...
    DDLink Free,Use;
    InitDDLink(Use);
    InitDDLink(Free);
    InitFreeLink(Free);

	//定义操作序列...
    cout << " ******定义操作序列****** " << endl;
    int len = 0;    //操作序列长度
    char op;        //操作码
    while(1)
	{   
	    cout << endl << " 输入操作码(a-申请, f-释放, c-完毕): ";
        cin >> op;
	    if(op == 'c' || op == 'C')
	  	    break;
	    if(op == 'a' || op == 'A')
		    ApplySpace(Free,Use,len);
	    else if(op == 'f' || op == 'F')
		    ReleaseSpace(Free,Use,len);
	} 
	system("cls");
    oporder[len+1].state = 0;

	//选择相应的分配方式作空间分配和回收，并打印分配或回收后分区的状况...
    int view;    //分配方式
    int i,serial,atimes,rtimes;
    while(1)
	{   
		cout << " *****分配方式(2-首址适应算法, 1-最佳适应算法, 0-退出)***** " << endl; 
	    cout << " 选择分配方式: ";
	    cin >> view;
	    i = 0;
	    serial = 0;
	    atimes = 0;   //分配次数...
        rtimes = 0;   //回收次数...
	    if(view == 0) break;
	    else
		{
		    while(i < len)
			{
			    if(oporder[i].state == 1)
				{
				    AssignSpace(Free,Use,oporder[i].content,oporder[i].size);
		            if(oporder[i+1].state == 0)
					{
					    cout << endl << " ----------------------------------- " << endl;
					    cout << endl << " >>>>>第 " << ++atimes << " 次分配<<<<< " << endl;
			            Print(Free);
			            Print(Use);
			            cout << endl << " 按任意键继续... " << endl;
			            getch();
					}
				}
	            else
				{
				    if(view == 1)   //若是选择最佳适应法分配...
				        FreeLinkSort(Free,0);
		            RecycleSpace(Free,Use,oporder[i].content,++serial);
				    if(view == 1)   //若是选择最佳适应法分配...
				        FreeLinkSort(Free,1);
				    cout << endl << " ----------------------------------- " << endl;
				    cout << endl << " >>>>>第 " << ++rtimes << " 次回收<<<<< " << endl;
		            Print(Free);
		            Print(Use);
		            cout << endl << " 按任意键继续... " << endl;
		           getch();
				}
	            ++i;
			}
		}
	    InitDDLink(Free);
	    InitDDLink(Use);
	    InitFreeLink(Free);
	    system("cls");
	} 
    return 0;
}