#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Process
{
int name;
int addr; //起始地址
int length; //长度
struct Process *next;
}Process,*ProList;
//初始化
int InitList(ProList &P)
{
if((P=(ProList)malloc(sizeof(Process)))==NULL)
exit(-1);
P->next=NULL;
P->addr=0;
P->length=0;
P->name=0;
return 1;
}
//链表插入（尾插） 插就绪状态链表中
int ListInsert1(ProList &P,int name,int addr,int length)
{
Process *s,*q,*p;
q=new Process;
p=new Process;
s=P;
p->addr=addr;
p->length=length;
p->name=name;
while(s->next)
{
s=s->next;
}
p->next=s->next;
s->next = p;
return 1;
}
//状态链表插入（尾插）改状态时调用
int ListInsert(ProList &P,Process *p)
{
Process *s,*q;
q=new Process;
s=P;
while(s->next)
{
s=s->next;
}
p->next=s->next;
s->next = p;
return 1;
}
//状态链表删除（头删）
Process ListDelete(ProList &P)
{
Process *s;
s=P->next;
P->next=s->next;
return *s;
}
//内存链表排序插入 按地址从小到大排序
int Sorting(ProList &L,int name,int addr,int length)
{
Process *p,*s;
s=new Process;
s->addr=addr;
s->length=length;
s->name=name;
p=L->next;
if(!p||p->addr>s->addr)
{
s->next=p;
L->next=s;
return 1;
}
while(p->next)
{
if(s->addr>=p->addr&&s->addr<p->next->addr)
{
s->next=p->next;
p->next=s;
return 1;
}
p=p->next;
}
if(!p->next)
{
s->next=NULL;
p->next=s;
}
return 1;
}
//创建进程
int Create(ProList &L1,ProList &S,ProList &L,int name,int length)
{
Process *p,*q,*pre,*r;
q=new Process;
int addr;
pre=S;
p=pre->next;
r=p;
if(!p)
{
printf("内存已满，无法创建进程！！\n");
return 0;
}
while(p)
{
if(p->length>=length)
if(p->length<r->length||r->length<length)
{
while(pre->next!=p)
pre=pre->next;
r=pre->next;
}
p=p->next;
}
if(r->length<length)
{
printf("无充足内存可创建进程！！\n");
return 0;
}
addr=r->addr;
if(r->length-length<=2)
{
length=r->length;
pre->next=r->next;
free(r);
}
else{
r->addr=r->addr+length;
r->length=r->length-length;
}
ListInsert1(L1,name,addr,length);
Sorting(L,name,addr,length);
return 1;
}
//就绪态/执行态
int Ready(ProList L1,ProList L2)
{
Process *p,*s,*q;
q=new Process;
p=L1->next;
s=L2->next;
if(p==NULL)
{
//printf("无新建进程！！\n");
return 1;
}
if(!s)
{
*q=ListDelete(L1);
ListInsert(L2,q);
}
return 1;
}
//阻塞态
int Blocking(ProList L1,ProList L2,ProList L3)
{
Process *r,*s,*q;
q=new Process;
s=new Process;
if(L2->next)
{
*q=ListDelete(L2);
ListInsert(L3,q);
if(L1->next)
{
*s=ListDelete(L1);
ListInsert(L2,s);
}
}
else
printf("无被阻塞进程！！\n");
return 1;
}
//唤醒
int Wakeup(ProList L1,ProList L2,ProList L3)
{
Process *p,*q,*r;
q=new Process;
r=new Process;
if(L3->next==NULL)
{
printf("无阻塞进程！！\n");
return 1;
}
*q=ListDelete(L3);
ListInsert(L1,q);
if(!L2->next)
{
*r=ListDelete(L1);
ListInsert(L2,r);
}
return 1;
}
//时间片到
int Timing(ProList L1,ProList L2)
{
Process *p,*q,*r;
p=new Process;
q=new Process;
r=new Process;
if(!L1->next&&!L2->next)
{
printf("无可执行进程！！\n");
return 1;
}
*q=ListDelete(L2);
ListInsert(L1,q);
*r=ListDelete(L1);
ListInsert(L2,r);
return 1;
}
//结束进程
int Ending(ProList L1,ProList L2,ProList L,ProList S)
{
Process *p,*q,*r,*k,*s,*h,*pre;
int addr,length;
p=new Process;
q=new Process;
k=new Process;
if(!L2->next)
{
printf("无可结束进程！！\n");
return 1;
}
*p=ListDelete(L2);
if(L1->next)
{
*k=ListDelete(L1);
ListInsert(L2,k);
}
//回收算法
h=L;
s=h->next;
while(s)
{
if(s->addr==p->addr)
break;
h=s;
s=s->next;
}
h->next=s->next;
free(s);
length=p->length;
addr=p->addr;
Sorting(S,0,addr,length);
pre=S->next;
r=pre->next;
while(r)
{
if(r->addr==pre->addr+pre->length)
{
pre->length+=r->length;
pre->next=r->next;
r=pre->next;
}
else{
pre=r;
r=r->next;
}
}
return 1;
}
int Show2(ProList L)
{
Process *p;
p=L->next;
while(p)
{
printf("<%d,%d> ",p->addr,p->length);
p=p->next;
}
printf("\n");
return 1;
}
int Show1(ProList L)
{
Process *p;
p=L->next;
while(p)
{
printf("%d ",p->name);
p=p->next;
}
printf("\n");
return 1;
}
int main()
{
ProList L1,L2,L3,S,L;
Process *q;
q=new Process;
S=new Process;
InitList(L1); //就绪态
InitList(L2); //执行态
InitList(L3); //阻塞态
InitList(L); //已占用内存
InitList(S); //空余内存
printf(" ~~~~~~~~~~~~~菜单~~~~~~~~~~\n") ;
printf(" * c.创建进程(就绪/执行)*\n");
printf(" * b.阻塞进程 *\n");
printf(" * w.唤醒进程 *\n");
printf(" * t.时间片到 *\n");
printf(" * e.结束进程 *\n");
printf(" * s.查询状态内存 *\n");
printf(" * l.结束程序 *\n");
printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
int a,b,c,d;
char ch;
printf("请输入起始地址和内存大小：");
scanf("%d%d",&a,&b);
getchar();
q->addr=a;
q->length=b;
q->next=S->next;
S->next=q;
S->length=0;
S->addr=a;
while(1)
{
printf("请输入你要执行：");
//scanf("%c",&ch);
ch=getchar();
if(ch=='c')
{
//getchar();
scanf("%d %d",&c,&d);
Create(L1,S,L,c,d);
Ready(L1,L2);
}
else if(ch=='b')
{
Blocking(L1,L2,L3);
}
else if(ch=='w')
{
Wakeup(L1,L2,L3);
}
else if(ch=='t')
{
Timing(L1,L2);
}
else if(ch=='e')
{
Ending(L1,L2,L,S);
}
else if(ch=='s')
{
printf("就绪态：");
Show1(L1);
printf("执行态：");
Show1(L2);
printf("阻塞态：");
Show1(L3);
printf("已用空间<起始地址，长度>:");
Show2(L);
printf("剩余内存<起始地址，长度>:");
Show2(S);
}
else if(ch=='l')
if(!L->next)
return 1;
else printf("还有未结束进程！！\n");
else
printf("命令错误！！\n");
getchar();
}
}
