zhucunchuqi.cpp

在可变分区管理方式下

#define LEN sizeof(struct PCB)
#define LEN1 sizeof(struct partition)
#include"stdio.h"
#include"stdlib.h"
struct PCB
{
 char PID[5];      /*进程名*/
 int needtime;     /*要求运行的时间*/
 int cputime;      /*已经运行的时间*/
 int priority;     /*优先权(越小越高)*/
 int starttime;    /*进入就绪队列的时间*/
 int overtime;     /*运行完成的时间*/
 int state;        /*状态:1就绪2运行3完成*/
 int needspace;    /*需要的主存大小*/
 int startplace;   /*主存的起始位置*/
 int overplace;    /*主存的结束位置*/
 int truespace;    /*实际所占主存大小*/
 struct PCB *next;
};

struct partition
{
 int size;                /*分区大小*/
 int startplace;          /*分区开始地址*/
 int finishplace;         /*分区结束地址*/
 struct partition *next;
};

struct partition *header,*lasthead;    /*定义全局变量*/
struct PCB *head,*runhead,*overhead;

struct PCB *create(int num)   /*创建进程，并将进程按优先级顺序插入队列中*/
{
 struct PCB *head1,*p,*p1,*p2;
 int i;
 head1=NULL;     /*头指针指零*/
 printf("---------------初始化进程-----------------\n");
 printf("1进程名 2要求运行的时间 3优先权 4需要的主存大小\n");       
 for(i=1;i<=num;i++)        /*循环建立所有进程*/
 {	 
  p=(struct PCB *)malloc(LEN);    /*开辟一个空间*/    
  printf("第%d个进程的信息:",i);
  scanf("%s%d%d%d",p->PID,&p->needtime,&p->priority,&p->needspace);
  p->cputime=0;                   /*已运行的时间为零*/
  p->starttime=0;                 /*进入就绪队列的时间赋为零*/
  p->overtime=-1;                 /*运行没有结束所以运行完成的时间赋为-1*/
  p->state=1;                     /*状态赋为就绪状态*/
  p->startplace=-1;               /*主存的起始位置赋为-1*/
  p->overplace=-1;                /*主存的结束位置赋为-1*/
  p->truespace=0;                 /*初始占用赋为0*/
  p1=head1;                        /*p1指针指向头指针*/
  if(head1==NULL)      /*如果头指针为零将头指针指向新建立的进程*/     
  {head1=p;head1->next=NULL;}
  else                /*头指针不为零的情况*/
  {
   while(p1!=NULL&&p->priority>p1->priority)  /*查找插入点*/
   {p2=p1;
    p1=p1->next;
   }
   if(head1==p1)   /*优先权的值最小作为表头*/
   {p->next=head1;p2=head1=p;}
   else           /*否则的话插入*/
   {p2->next=p;p->next=p1;}
  }
 }
 return(head1);
}

/*首次适应算法:从空闲分区链表开始处进行扫描，选择第一个满足要求的空闲分区*/
int find1()
{
 int flag=0,space;
 struct partition *p1,*p2;
 space=(head->needspace/5+1)*5;     /*最小剩余空间定为6kb*/
 p1=header;
 while(p1!=NULL&&space>p1->size)
 {p2=p1,p1=p1->next;}
 if(p1!=NULL)
 {
  flag=1;
  head->state=2;
  head->startplace=p1->startplace;
  head->truespace=space;
  if(p1==header)
  {
   if(space==p1->size)
   {head->overplace=header->finishplace;header=header->next;}
   else
   {header->size-=space;header->startplace+=space;head->overplace=header->startplace-1;}
  }
  else
  {
   if(space==p1->size)
   {head->overplace=p1->finishplace;p2->next=p1->next;}
   else
   {p1->size-=space;p1->startplace+=space;head->overplace=p1->startplace-1;}
  }
 }
 return(flag);
} 

/*循环首次适应算法:从上次找到的空闲分区位置开始查找，直至找到第一个满足要求的空闲分区*/
int find2()
{
 int flag=0,space,signal=0;
 struct partition *p1,*p2;
 space=(head->needspace/5+1)*5;     /*最小剩余空间定为6kb*/
 if(header!=NULL&&header->next==NULL)
 {
  lasthead=header;
  if(space<=header->size)
  {
   flag=1;
   head->state=2;
   head->startplace=header->startplace;
   head->truespace=space;
   if(space==header->size)
   {head->overplace=header->finishplace;header=header->next;}
   else
   {header->size-=space;header->startplace+=space;head->overplace=header->startplace-1;}
  }
 }
 else
 {
  if(header!=NULL)
  {
   p1=lasthead;
   if(header!=lasthead) signal++; 
   while(p1!=NULL&&space>p1->size)
   {p2=p1,p1=p1->next;}
   if(p1!=NULL)
   {
    flag=1;
    head->state=2;
    head->startplace=p1->startplace;
    head->truespace=space;
    if(p1==header)
	{
     if(space==p1->size)
	 {head->overplace=header->finishplace;lasthead=header=header->next;}
     else
	 {header->size-=space;header->startplace+=space;head->overplace=header->startplace-1;}
	}
    else
	{
     if(space==p1->size)
	 {
	  head->overplace=p1->finishplace;
	  if(p1==lasthead)
	  {
	   p2=header;
	   while(p2->next!=p1) p2=p2->next;
      }
	  p2->next=p1->next;
	  if(p2->next!=NULL) lasthead=p2->next;
	  else lasthead=header;
	 }
     else
	 {p1->size-=space;p1->startplace+=space;head->overplace=p1->startplace-1;lasthead=p1;}
	}
   }
   else signal++;
   if(signal==2)
   {
    p1=header;
    while(p1!=lasthead&&space>p1->size)
	{p2=p1,p1=p1->next;}
    if(p1!=lasthead)
	{
     flag=1;
     head->state=2;
     head->startplace=p1->startplace;
     head->truespace=space;
     if(p1==header)
	 {
      if(space==p1->size)
	  {head->overplace=header->finishplace;header=header->next;}
      else
	  {header->size-=space;header->startplace+=space;head->overplace=header->startplace-1;}
	  lasthead=header;
	 }
     else
	 {
      if(space==p1->size)
	  {head->overplace=p1->finishplace;p2->next=p1->next;lasthead=p2->next;}
      else
	  {p1->size-=space;p1->startplace+=space;head->overplace=p1->startplace-1;lasthead=p1;}
	 }
	}
   }
  }
 }
 return(flag);
}
   
/*最佳适应算法:选择既满足要求且是最小的空闲分区*/
int find3(int kb)
{
 int flag=0,space,min=kb+1;
 struct partition *p1,*p2,*p3;
 space=(head->needspace/5+1)*5;     /*最小剩余空间定为6kb*/
 p1=header;
 p2=NULL;
 while(p1!=NULL)
 {
  if(space<=p1->size&&min>p1->size)
  {
   min=p1->size;
   p2=p1;
  }
  p1=p1->next;
 }
 if(p2!=NULL)
 {
  flag=1;
  head->state=2;
  head->startplace=p2->startplace;
  head->truespace=space;
  if(p2==header)
  {
   if(space==p2->size)
   {head->overplace=header->finishplace;header=header->next;}
   else
   {
	header->size-=space;
    header->startplace+=space;
    head->overplace=header->startplace-1;
   }
  }
  else
  {
   if(space==p2->size)
   {
	p3=header;
	while(p3->next!=p2) p3=p3->next;
	head->overplace=p2->finishplace;
	p3->next=p2->next;
   }
   else
   {
	p2->size-=space;
    p2->startplace+=space;
    head->overplace=p2->startplace-1;
   }
  }
 }
 return(flag);
}

/*最坏适应算法:选择空闲分区链表中最大的空间*/
int find4()
{
 int flag=0,space,max=0;
 struct partition *p1,*p2,*p3;
 space=(head->needspace/5+1)*5;     /*最小剩余空间定为6kb*/
 p1=header;
 p2=NULL;
 while(p1!=NULL)
 {
  if(max<p1->size)
  {
   max=p1->size;
   p2=p1;
  }
  p1=p1->next;
 }
 if(p2!=NULL)
 {
  if(p2->size>=space)
  {
   flag=1;
   head->state=2;
   head->startplace=p2->startplace;
   head->truespace=space;
   if(p2==header)
   {
    if(space==p2->size)
    {head->overplace=header->finishplace;header=header->next;}
    else
    {
	 header->size-=space;
     header->startplace+=space;
     head->overplace=header->startplace-1;
    }
   }
   else
   {
    if(space==p2->size)
    {
	 p3=header;
	 while(p3->next!=p2) p3=p3->next;
	 head->overplace=p2->finishplace;
	 p3->next=p2->next;
    }
    else
    {
	 p2->size-=space;
     p2->startplace+=space;
     head->overplace=p2->startplace-1;
    }
   }
  }
 }
 return(flag);
} 

/*进程结束后，将释放的内存放入空闲分区链表*/
void insert()
{
 struct partition *p,*p1,*p2,*p3,*p4,*p5;
 if(header==NULL)
 {
  p=(struct partition *)malloc(LEN1);
  p=(struct partition *)malloc(LEN1);
  p->size=overhead->truespace;
  p->startplace=overhead->startplace;
  p->finishplace=overhead->overplace;
  header=p;
 }
 else
 {
  p1=header;
  if(overhead->overplace<p1->startplace)
  {
   if((overhead->overplace+1)==p1->startplace)
   {
    p1->startplace=overhead->startplace;
    p1->size+=overhead->truespace;
   }
   else
   {
    p3=(struct partition *)malloc(LEN1);
    p3->size=overhead->truespace;
    p3->startplace=overhead->startplace;
    p3->finishplace=overhead->overplace;
    p3->next=header;
    header=p3;
   }
  }
  else
  {
   if(p1->next!=NULL)
   {
    p2=p1;p1=p1->next;
    while(p1!=NULL&&overhead->overplace>p1->startplace)
    {p2=p1;p1=p1->next;}
    if(p1!=NULL)
    {
     if((overhead->overplace+1)==p1->startplace&&(overhead->startplace-1)==p2->finishplace)
     {
	  p2->finishplace=p1->finishplace;
      p2->size=p1->finishplace-p2->startplace+1;
 	  p2->next=p1->next;
     }
     else
     {
      if((overhead->overplace+1)<p1->startplace&&(overhead->startplace-1)>p2->finishplace)
      {
	   p4=(struct partition *)malloc(LEN1);
	   p4->size=overhead->truespace;
       p4->startplace=overhead->startplace;
       p4->finishplace=overhead->overplace;
       p2->next=p4;
	   p4->next=p1;
      }
   	  else
      {
       if((overhead->overplace+1)==p1->startplace)
	   {
	    p1->startplace=overhead->startplace;
        p1->size+=overhead->truespace;
       }
	   else
       {
        p2->finishplace=overhead->overplace;
        p2->size+=overhead->truespace;
       }
      }
     }
    }
   }
   else 
   {
	p5=(struct partition *)malloc(LEN1);
	p5->size=overhead->truespace;
    p5->startplace=overhead->startplace;
    p5->finishplace=overhead->overplace;
    p1->next=p5;
	p5->next=NULL;
   }
  }
 }
} 
   
void main()
{
 int i,j,num,kb,conti,choose,cho,flag1,flag2=0,time,time1;
 struct PCB *p,*p1,*p2,*p3,*q,*q1,*q2;
 do
 {
  printf("输入总的就绪进程数--");
  scanf("%d",&num);
  head=create(num);      /*建立就绪进程的链表*/
  printf("\n输入主存储器的容量(以KB计算)--");
  scanf("%d",&kb);
  printf("选择分配算法:1首次适应算法2循环首次适应算法3最佳适应算法4最坏适应算法--");
  scanf("%d",&choose);
  time=0;
  time1=1;
  runhead=NULL;
  overhead=NULL;
  header=(struct partition *)malloc(LEN1);
  header->size=kb;
  header->startplace=1;
  header->finishplace=kb;
  header->next=NULL;
  do     /*查找是否有满足要求的空闲内存，有的话将就绪进程放入运行链表中运行*/
  {
   switch(choose)
   {
    case 1:flag1=find1();break;
	case 2:flag1=find2();break;
	case 3:flag1=find3(kb);break;
	case 4:flag1=find4();break;
   }
   if(flag1==1)
   {
    p=head;
    head=head->next;
    p->next=runhead;
    runhead=p;
   }
  }while(head!=NULL&&flag1==1);
  while(head!=NULL||runhead!=NULL)  /*如果就绪进程和运行进程链表都不为空，循环*/
  {
   p1=runhead;
   while(p1!=NULL)
   {
	if(p1->cputime<p1->needtime)
	{p2=p1;p1=p1->next;}
    else
    {
	 p1->state=3;
	 p1->overtime=time;
	 if(p1==runhead)
	 {runhead=runhead->next;flag2=1;}
	 else
	 {p2->next=p1->next;flag2=2;}
     p1->next=overhead;
     overhead=p1;
    }
    if(flag2!=0)  /*有进程结束的情况*/
	{
	 insert(); 
	 printf("\n结束进程%s信息:\n",overhead->PID);
     printf("要求运行的时间:%d\t进入就绪队列的时间:%d\n",overhead->needtime,overhead->starttime);
	 printf("运行完成的时间:%d\t需要的主存大小:%d\n",overhead->overtime,overhead->needspace);
	 printf("主存的起始位置:%d\t主存的结束位置:%d\n",overhead->startplace,overhead->overplace);
	 printf("实际所占主存大小:%d\n\n",overhead->truespace);
	 printf("在%d到%d秒这段时间中有无进程进入就绪队列:1有2没有--",time1,time);
	 scanf("%d",&cho);
	 time1=time;
	 if(cho==1) 
	 {
	  printf("请输入就绪进程个数:");
	  scanf("%d",&i);
	  printf("请输入:1进程名 2要求运行的时间 3优先权 4进入就绪队列时间 5需要的主存大小\n");
	  for(j=0;j<i;j++)
	  {
	   q=(struct PCB *)malloc(LEN);
       scanf("%s%d%d%d%d",q->PID,&q->needtime,&q->priority,&q->starttime,&q->needspace);
       q->cputime=0;                   /*已运行的时间为零*/
       q->overtime=-1;                 /*运行没有结束所以运行完成的时间赋为-1*/
       q->state=1;                     /*状态赋为就绪状态*/
       q->startplace=-1;               /*主存的起始位置赋为-1*/
       q->overplace=-1;                /*主存的结束位置赋为-1*/
       q->truespace=0;  
       q1=head;
       if(head==NULL)      /*如果头指针为零将头指针指向新建立的进程*/     
	   {head=q;head->next=NULL;}
       else                /*头指针不为零的情况*/
	   {
        while(q1!=NULL&&q->priority>q1->priority)  /*查找插入点*/
		{q2=q1;
         q1=q1->next;
		}
        if(head==q1)   /*优先权的值最小作为表头*/
		{q->next=head;q2=head=q;}
        else           /*否则的话插入*/
		{q2->next=q;q->next=q1;}
      }
	 }
	 }
	 flag1=1;
	 while(head!=NULL&&flag1==1)    /*查找合适新进入的就绪进程的内存*/
	 {
      switch(choose)
	  {
       case 1:flag1=find1();break;
	   case 2:flag1=find2();break;
	   case 3:flag1=find3(kb);break;
   	   case 4:flag1=find4();break;
	  }
      if(flag1==1)
      {
	   p=head;
       head=head->next;
       p->next=runhead;
       runhead=p;
      }
	 }
   }
   if(flag2==1) p1=runhead;   /*指针指向下一个运行进程*/
   if(flag2==2) p1=p2->next;
   flag2=0;
  }
  p3=runhead;
  while(p3!=NULL)     /*所有运行的进程时间加一*/
  {p3->cputime++;p3=p3->next;}
  time++;
 }
  printf("\n是否继续(1是2不是)--");
  scanf("%d",&conti);
  }while(conti==1);
}