#include<windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
using namespace std;
#define MAX 1048576 //设置内存大小为1048576
//定义数据结构
//进程所占内存
struct operation
{
int size;//分配的大小
int time; //起始时间
int end;
string oper; //操作
operation *next;
operation *before;
};
//存储进程数
struct Head
{
int count;
operation *next;
};
//加锁数据结构
struct Clock
{
int count;
operation *next;
};
//从内存空间由上往下搜索合适的空间并装入内存,添加进程
int add_pro(Head *head,operation *p)//返回1,表示插入成功；返回0表示插入失败
{
operation *p1=head->next;
//搜索插入位置
if(0==p1)//内存为空
{
head->next=p;
p->time=10*1024;
p->end=p->size+10240;
p->before=0;
p->next=0;
return 1;
}
else//如果内存中有进程
{
int temp=p1->time-10240;
if(p->size<=temp)//如果第一个进程前面有足够空间，cut in before p1
{
p->next=head->next;
head->next->before=p;
p->before=0;
head->next =p;
p->time=10240;
p->end=p->size+10240;
return 1;
}
else//在两个进程间寻找合适位置
while(p1->next!=0)//当p1不是指向最后一个进程
{
temp=p1->next->time-p1->end;//以下有重复代码，可优化
if(p->size<= temp)//搜索到了合适位置,cut in after p1
{
p->next= p1->next;
p1->next->before = p;
p1->next=p;
p->before = p1;
p->time = p1->end;
p->end = p->time + p->size;
return 1;
}
p1 = p1->next;
}
//都没找到可插入的位置
if((p1->end+p->size)<=MAX)//内存足够大，允许进程插入到内存末尾,此时p1指向最后一个节点
{
p->next=0;
p->before=p1;
p1->next=p;
p->time=p1->end;
p->end=p->time+p->size;
return 1;
}
else
return 0;//返回0，表示插入失败
}
}
//提交一个进程
void commit(Head *head)
{
operation *p = new operation;//提交进程
cout<<"请输入要commit的进程名：";
cin>>p->oper;
cout<<"请输入进程大小：\n";
int kb,bb;
cout<<"多少KB？";
cin>>kb;
cout<<"多少B?";
cin>>bb;
p->size=1024*kb+bb;
p->next=0;
p->before=0;
kb=add_pro(head,p);
if(kb==0)
cout<<"进程提交失败！\n";
else cout<<"进程提交成功！\n";
system("pause");
system("cls");
return;
}
//回收一个区域
void release(Head *head)
{
cout<<"请输入要release的进程名：";
string op;
cin>>op;
operation *p=head->next;
while(p)
{
if(p->oper==op)
break;
p=p->next;
}
if(0==p)
{
cout<<"未找到进程："<<op<<"！"<<endl;
system("pause");
system("cls");
return;
}
//删除就绪队列中p节点
if(head->next==p)//p是第一个节点
{
head->next=p->next;
if(0!=p->next)
p->next->before = 0;
}
else if(p->next==0)//p是最后一个节点
{
p->before->next=0;
p->before=0;
}
else//中间节点
{
p->next->before=p->before;
p->before->next=p->next;
}
delete p;
cout<<"成功释放进程:"<<op<<'!'<<endl;
system("pause");
system("cls");
}
//加锁进程
void lock(Head *head,Clock *out)
{
cout<<"请输入要lock的进程名：";
string op;
cin>>op;
operation *p = head->next;;//指向移动源head链表
operation *p1 = out->next;;//指向移动目的out链表
while(p != 0)//搜索要加锁的进程
{
if(p->oper == op)
break;
p = p->next;
}
if(0 == p)//无相关进程
{
cout<<"找不到进程："<<op<<"！"<<endl;
system("pause");
system("cls");
return;
}
//处理就绪队列,p指向要解锁节点
if(head->next == p)//要加锁的进程在第一个
{
head->next = p->next;
if(0 != p->next)//有至少两个链表
p->next->before = 0;
}
else if(p->next == 0)//要加锁的进程在最后一个
{
p->before->next=0;
p->before=0;
}
else //要加锁的进程在中间
{
p->before->next = p->next;
p->next->before = p->before;
}//done
//处理加锁序列，p指向要插入加锁队列的节点，p1指向加锁队列第一个节点
if(0 == p1)//加锁链表为空
{
out->next = p;
p->before = 0;
}
else
{
while(0 != p1->next)//p1指向加锁进程链表的末尾
p1 = p1->next;
p1->next = p;
p->before = p1;
}
p->next = 0;//done
system("cls");
}
//解锁进程unlock
void unlock(Head *head,Clock *out)
{
cout<<"请输入要解锁的进程名：";
string op;
cin>>op;
operation *p=out->next;;//指向移动源out链表
while(0 != p)
{
if(p->oper == op)
break;
p = p->next;
}
if(0 == p)//无相关进程
{
cout<<"找不到进程："<<op<<"！"<<endl;
system("pause");
system("cls");
return;
}
//解锁队列中的p
if(out->next==p)//要解锁进程在第一个
{
out->next=p->next;
if(0 != p->next)//如果p后面还有节点
p->next->before = 0;
}
else if(p->next==0)//要解锁进程在最后一个
{
p->before->next=0;
}
else//要加锁的进程在中间
{
p->before->next=p->next;
p->next->before=p->before;
}
//done
add_pro(head,p);
cout<<"成功解锁进程："<<op<<endl;
system("pause");
system("cls");
return;
}
int main()
{
Head *head=new Head;//定义内存进程头节点
head->next=0;
head->count=0;
Clock *out=new Clock;
out->next=0;
long int temp=0;
operation *p=head->next;
operation *p1=out->next;
while(1)
{
p=head->next;
while(0!=p)
{
cout<<"\t进程名:"<<p->oper<<"\t大小:"<<(p->size)/1024<<"K"<<(p->size)%1024<<"B\t起始地址:"<<p->time<<"\t结束地址:"<<p->end<<endl;
p=p->next;
}
p=head->next;
cout<<"内存空间段：\n";
if(0==p)//无进程
cout<<'\t'<<MAX;
else//有进程
{
if((p->time-10240)!=0)
cout<<'\t'<<(p->time-10240)<<endl;
if(0==p->next)//仅有一个进程时
cout<<'\t'<<MAX-(p->end)<<endl;
else while(1)//至少有两个进程，p->next != 0
{
temp=p->next->time-p->end;
if(temp)
cout<<'\t'<<temp<<endl;
p=p->next;
if(0==p->next)//p指向最后一个节点时
{
cout<<'\t'<<MAX-(p->end)<<endl;
break;
}
}
}
cout<<"\n加锁队列："<<endl;
p1 = out->next;
while(p1)
{
cout<<"\t进程名:"<<p1->oper<<"\t大小:"<<(p1->size)/1024<<"K"<<(p1->size)%1024<<'B'<<endl;
p1 = p1->next;
}
cout<<"\n1、提交一个区域\n2、加锁一个区域\n3、解锁一个区域\n4、释放一个区域\n5、退出"<<endl;
cout<<"\n请选择内存操作序号：";
long int chose;
cin>>chose;
switch(chose)
{
case 1: commit(head);break;
case 2: lock(head,out);break;
case 3: unlock(head,out);break;
case 4: release(head);break;
case 5: return 0;
}
}
}
