suwancheng.cpp

计算机操作系统的实验。实现了处理机调度的模拟

#define LEN sizeof(struct process)
#include<stdio.h>
#include<string>
#include<malloc.h>
#include<iostream>
using namespace std;

struct Block                  //空闲链结构体
{
int PID;              //作业名
int address;              //分区首地址  
int size;                  //分区大小
int nowstate;                 //分区状态
struct Block *next;          //前向指针
struct Block *front;         //后向指针
};

struct Used                    //已分配分区结构体
{
  Block *usedArea;        
  Used *next;
};


enum state
{Uncome,Ready,Running,Blocked};

struct process
{char ProName[10];
 int ProPID;
 int ProTimeNeed;
 int ProTimeCome;
 int ProTimeRunning;
 float ProWeight;
 enum state ProState;
 struct process *next;
 struct process *pre;
};

Block *freeHead;         // 带表头附加节点的空闲链头指针
Used *usedHead;          //带表头附加结点的已分配分区头指针

int Total=0,TimeNow=0,TimeChip=0,flag,aa;
struct process *p0=NULL;

bool InitValue()     //初始化函数
{
freeHead=new   Block;
freeHead->size=0;
freeHead->next=NULL;
freeHead->nowstate=1;
usedHead=new Used;
Block *p=new Block;
p->address=0;
usedHead->usedArea=p;
usedHead->next=NULL;
Block *temp=new Block;
cout<<"请输入内存的初始大小(k)："<<endl;
cin>>temp->size;
temp->address=0;
temp->nowstate =0;
temp->next=freeHead;
temp->front=NULL;
freeHead->front=temp;
return true;
}

void Display(Block *p,Used *q)    //打印信息的函数
{
  cout<<"\n\n已分配内存空间的信息(进程PID, 起始地址,  占内存大小):";
  while(q!=NULL)
  {
    cout<<"\n进程PID: "<<q->usedArea->PID<<",  起始地址: "<<q->usedArea->address<<",  占内存大小: "<<q->usedArea->size;
    q=q->next;
  }
  cout<<"\n\n空闲内存空间的信息(起始地址,空闲大小):\n"<<endl;
 while(p!=NULL)
 {
   cout<<"起始地址: "<<p->address<<",  空闲大小:";
   cout<<p->size<<'\n';
   p=p->front;
 }
}

void Allocate(int reqPID,int reqSize)   //分配函数
{    
  Block *p=freeHead->front ;
  Used *r1,*r2;
 while(p!=NULL)
 {
   if(reqSize<p->size)   //如果请求的分区的大小小于一个空闲分区的大小
   {
    Used *temp=new Used;
    temp->usedArea =p;
    Block *q=new Block;
    *q=*p;
    temp->usedArea ->PID =reqPID;  
    temp->usedArea ->size =reqSize;
    temp->usedArea ->front =q;
    temp->usedArea ->nowstate =1;
    q->size =q->size -reqSize;
    q->address =q->address + reqSize;   
    q ->next->front=q;
    if(q ->front!=NULL)
    q ->front->next=q;
    r1=usedHead;
    r2=usedHead->next;
    while(r2!=NULL&&r2->usedArea->address<temp->usedArea->address)
    {r1=r2;r2=r2->next;}
    r1->next=temp;
    temp->next=r2;
    break;
   }
   else if(reqSize==p->size)//如果请求的分区的大小等于一个空闲分区的大小
   {
    Used *temp=new Used;
    temp->usedArea =p;
    temp->usedArea ->PID =reqPID;
    temp->usedArea ->nowstate =1;
    p->next->front =p->front ;
    if(p->front!=NULL)
    p->front ->next =p->next ;
    r1=usedHead;
    r2=usedHead->next;
    while(r2!=NULL&&r2->usedArea->address<temp->usedArea->address)
    {r1=r2;r2=r2->next;}
    r1->next=temp;
    temp->next=r2;
    break;
   }
   p=p->front;
 }
  if(p==NULL)
    cout<<"资源不足请等待"<<endl;
}

void Recycle(int freePID)   //回收分区的函数
{
   Used *pp=usedHead->next,*r=usedHead;
   Block *qq,*temp1;
   while(pp!=NULL)
   {
      if(pp->usedArea->PID==freePID)//找到同名的作业后，再分四种情况讨论
	  {
         qq=pp->usedArea;
         int flag1=1,flag2=1;
         Block *p1=freeHead->front;
         Block *pfront,*pnext;
         while(p1->address<qq->address)
		 {
            if(p1->address+p1->size==qq->address)
			{flag1=0;pnext=p1;}
            p1=p1->front;
		 }
         if(qq->address+qq->size==p1->address)
		 {flag2=0;pfront=p1;}
         if(flag1==0)
		 {
            if(flag2==0)
			{
              pnext->front =pfront->front;
              pnext->size=pnext->size + qq->size + pfront->size;
                if(pfront->front!=NULL)
                 pfront ->front ->next=pnext;
              r->next =pp->next;
			}
            else 
			{pnext->size+=qq->size;
		     r->next =pp->next ;
			}
		 }
         else
		 {
            if(flag2 ==0)
			{
             pfront ->address -=qq->size;
             pfront ->size+=qq->size ;
             r->next =pp->next ;
			}
            else
			{
             temp1=freeHead;
             while(temp1->address <=qq->address )
				 temp1=temp1->front;
             qq->front =temp1;
             qq->next =temp1->next ;
             qq->next->front =qq;
             temp1->next =qq;
             qq->nowstate =0;
             r->next =pp->next ;
			}    
		 }
        break;
	  }
      r=pp;
      pp=pp->next ;
   }
}

struct process *insertpro(struct process *head)
{
 int psize; 
 struct process *p;
     p=(struct process *)malloc(LEN);
     p->next=NULL;
     printf("请按照下面的要求完成输入进程的操作:\n");
     printf("输入进程名称:");
     cin>>(p->ProName);
     printf("输入要求运行时间：");
     scanf("%d",&(p->ProTimeNeed));
     printf("输入进程到达时间：");
     scanf("%d",&(p->ProTimeCome));
     printf("输入进程所需空间：");
     scanf("%d",&psize);
     p->ProWeight=float(TimeNow-p->ProTimeCome+p->ProTimeNeed)/p->ProTimeNeed;
     p->ProPID=aa;
     p->ProTimeRunning=0;
     Allocate(p->ProPID,psize);
      if(p->ProTimeCome==TimeNow)
         p->ProState=Ready;
      else
	     p->ProState=Uncome;
     p->next=head->next;
     p->pre=head;
     p->next->pre=p;
     head->next=p;
     Total++;
     aa++;
 return(head);
}

struct process *checkpro(struct process *head)
{char ch[10];
 struct process *p;
 int id,find=0,check=1,flag;
  do{ p=head->next;
      printf("请按照下面的要求完成操作:\n");
      printf("按1后则输入进程的PID，按2后则输入进程名:\n");
      scanf("%d",&flag);
      if(flag==1)
        {scanf("%d",&id);
         while(p->ProPID!=id&&p!=head)
            p=p->next;
         if(p!=head)
		  {find=1;
		   printf("该进程信息如下：\n"); 
		   printf("\nProName:%s , ",p->ProName);
		   printf("ProPID:%d , ",p->ProPID);
           printf("ProTimeNeed:%d , ",p->ProTimeNeed);
           printf("ProTimeRunning:%d , ",p->ProTimeRunning);
           printf("ProTimeCome:%d , ",p->ProTimeCome);
           printf("ProWeight:%d , ",p->ProWeight);
           switch(p->ProState)
				 {case Ready:printf(" ProState:Ready");break;
			      case Running:printf(" ProState:Running");break;
                  case Blocked:printf(" ProState:Blocked");break;
                  case Uncome:printf(" ProState:Uncome");break;
				 }
		   }
	      else
		   find=0;
        }
      if(flag==2)
        {scanf("%s",ch);
         while(strcmp(p->ProName,ch)!=0&&p!=head)
            p=p->next;
         if(p!=head)
		  {find=1;
           printf("该进程信息如下：\n"); 
		   printf("\nProName:%s , ",p->ProName);
		   printf("ProPID:%d , ",p->ProPID);
           printf("ProTimeNeed:%d , ",p->ProTimeNeed);
           printf("ProTimeRunning:%d , ",p->ProTimeRunning);
           printf("ProTimeCome:%d , ",p->ProTimeCome);
           printf("ProWeight:%f , ",p->ProWeight);
           switch(p->ProState)
	           {case Ready:printf(" ProState:Ready");break;
			    case Running:printf(" ProState:Running");break;
                case Blocked:printf(" ProState:Blocked");break;
                case Uncome:printf(" ProState:Uncome");break;
			   }
		   }
          else
            find=0;
         }   
	  if(!find) 
        printf("不存在该进程,");
	  printf("是否重新输入?是则按1，否则按0返回！\n");
	 scanf("%d",&check);        
  }while(check);
 return(p);
}

struct process *blockpro(struct process *head)
{struct process *p; 
  printf("\n阻塞进程:");
  p=checkpro(head);
 if(p!=head)
 {if(p->ProState==Blocked)
    printf("\n该进程已处于阻塞态，不需再阻塞！\n");
 if(p->ProState==Running)
    {p->ProState=Blocked; 
     printf("\n改进程阻塞成功!\n");
	 p0=NULL;
    }
  if(p->ProState==Ready)
    printf("\n该进程处于就绪态，阻塞失败！\n");
  if(p->ProState==Uncome)
    printf("\n该进程还未到，阻塞失败！\n");
  
 }
 else
  printf("\n由于不存在该进程，阻塞失败！\n"); 
 return(head);
}

struct process *wakepro(struct process *head)
{struct process *p; 
  printf("\n唤醒进程:");
  p=checkpro(head);
 if(p!=head)
 {if(p->ProState==Ready)
    printf("\n该进程已处于就绪态，不需再唤醒！\n");
 if(p->ProState==Blocked)
    {p->ProState=Ready; 
     printf("\n改进程唤醒成功!\n");
    }
  if(p->ProState==Running)
    printf("\n该进程处于运行态，不需要唤醒！\n");
  if(p->ProState==Uncome)
    printf("\n该进程还未到，唤醒失败！\n");
 }
 else
  printf("\n由于不存在该进程，唤醒失败！\n"); 
 return(head);
}

struct process *delpro(struct process *head)
{struct process *p; 
 printf("\n如果要删除进程");
 p=checkpro(head);
 if(p!=head)
 {Recycle(p->ProPID);
  p->pre->next=p->next;
  p->next->pre=p->pre;
  free(p);
  printf("\n删除成功!\n");
  Total--;
 }
 else
  printf("\n由于没有找到该进程，删除失败！\n"); 
 return(head);
}

struct process *priority(struct process *head)
{struct process *p,*q;
 TimeChip=100;
 if(p0!=NULL)
   {p0->ProTimeRunning+=TimeChip;
    if(p0->ProTimeRunning>=p0->ProTimeNeed)
      {Recycle(p0->ProPID);
	   p0->pre->next=p0->next;
       p0->next->pre=p0->pre;
       free(p0);
       p0=NULL;
       }
   }
 if(p0==NULL)
 {for(p=head->next;p->ProState!=Ready&&p!=head;p=p->next)
	        ;
     if(p==head)
       {printf("不存在程序在就绪队列\n");
        return(head);
       }
     else
	   for(q=p->next;q!=head;q=q->next)
         {if(q->ProState==Ready&&p->ProWeight<q->ProWeight)
		     p=q;
         }
    p0=p;
    p0->ProState=Running;
 }
 return(head);
}

struct process *timepiece(struct process *head)
{struct process *q;
 if(p0==NULL)
  {p0=head->next;
      while(p0!=head&&p0->ProState!=Ready)
       p0=p0->next;
      if(p0==head)
      {printf("不存在程序在就绪队列\n");
       p0=NULL;
       return(head);
      }
   p0->ProState=Running;
  }
 if(p0!=NULL)
 {q=p0->next;
   while(q!=p0&&q->ProState!=Ready)
    q=q->next;
   p0->ProTimeRunning+=TimeChip;
   p0->ProState=Ready;
   if(p0->ProTimeRunning>=p0->ProTimeNeed)
      {if(q==p0)
         {printf("不存在程序在就绪队列\n");
          Recycle(p0->ProPID);
		  p0->pre->next=p0->next;
          p0->next->pre=p0->pre;
		  free(p0);
          return(head);
         }
	   else
	    {Recycle(p0->ProPID);
	     p0->pre->next=p0->next;
         p0->next->pre=p0->pre;
		 free(p0);
	    }
      }
   p0=q;
   p0->ProState=Running;
 }
 return(head);
}

struct process *timego(struct process *head)
{struct process *p;
 if(flag==2)
 {head=timepiece(head);
 }
 if(flag==1)
 {head=priority(head);
 }
  TimeNow+=TimeChip;
 p=head->next;
 while(p!=head)
  {if(p->ProState==Ready)
        p->ProWeight=(TimeNow-p->ProTimeCome+p->ProTimeNeed)/p->ProTimeNeed;
   if(p->ProTimeCome<=TimeNow&&p->ProState==Uncome)
        p->ProState=Ready;
   p=p->next;
  }
 return(head);
}


void main()
{int sign;
 struct process *head,*p,*q;
 InitValue();//空间初始化
 head=(struct process *)malloc(LEN);
 head->next=head;
 head->pre=head->next;
  do
    {printf("\n按1输入新的进程,\n按2可以按照PID查询进程信息,或者按照进程名称查询信息,\n按3选择时间片轮转算法,先输入时间片长度,\n按4选择优先权算法,\n按5时间启动,\n按6可以选择阻塞进程,\n按7可以唤醒进程,\n按8可以撤销进程,\n按9可以显示内存空间状态,\n-1退出!\n");
     scanf("%d",&sign);
     switch(sign)
	 {case 1:head=insertpro(head);break;
      case 2:{p=checkpro(head);
              p=head->next;
			  printf("进程信息如下：\n"); 
			     while(p!=head)
				 {printf("\nProName:%s , ",p->ProName);
		          printf("ProPID:%d , ",p->ProPID);
                  printf("ProTimeNeed:%d , ",p->ProTimeNeed);
                  printf("ProTimeRunning:%d , ",p->ProTimeRunning);
                  printf("ProTimeCome:%d , ",p->ProTimeCome);
                  printf("ProWeight:%f , ",p->ProWeight);
				     switch(p->ProState)
					 {case Ready:printf(" ProState:Ready");break;
					  case Running:printf(" ProState:Running");break;
                      case Blocked:printf(" ProState:Blocked");break;
					 }
				  p=p->next;
     			 }
			  }break;
      case 3:{printf("\n请输入时间片长度：");
              scanf("%d",&TimeChip);
              flag=2;
             }
			 break;
	  case 4:{flag=1;
	          for(p=head->next;p->ProState!=Ready&&p!=head;p=p->next)
	               ;
              if(p!=head)
              for(q=p->next;q!=head;q=q->next)
              {if(q->ProState==Ready&&p->ProWeight<q->ProWeight)
		        p=q;
                }
                p0=p;
                p0->ProState=Running; 
             }break;
	  case 5: {head=timego(head);
               if(head->next!=NULL)
               {  
                p=head->next;
	            printf("\nTimeNow: %d\n",TimeNow);
			    printf("进程信息如下：\n");
			     while(p!=head)
				 {printf("\nProName:%s , ",p->ProName);
		          printf("ProPID:%d , ",p->ProPID);
                  printf("ProTimeNeed:%d , ",p->ProTimeNeed);
                  printf("ProTimeRunning:%d , ",p->ProTimeRunning);
                  printf("ProTimeCome:%d , ",p->ProTimeCome);
                  printf("ProWeight:%f , ",p->ProWeight);
				     switch(p->ProState)
					 {case Ready:printf(" ProState:Ready");break;
					  case Running:printf(" ProState:Running");break;
                      case Blocked:printf(" ProState:Blocked");break;
					 }
				  p=p->next;
     			 }
	           }
		       else
		        printf("\n不能再运行！\n"); 
			   } break;
      case 6:head=blockpro(head);break; 
      case 7:head=wakepro(head);break; 
	  case 8:head=delpro(head);break; 
	  case 9:Display(freeHead->front,usedHead->next);
     }
    }while(sign!=-1);
}