last.c

模拟操作系统进程调度、内存管理、临界资源分配

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "Conio.h"
#include "graphics.h"
#define closegr closegraph
#define NULL 0
#define memorysize 300
#define skinds 3
typedef enum state{run,suspend,ready,wait}state;     /*进程状态*/
int jid=0,pid=0,startaddress=0,timeslip=5;
int source[skinds]={10,10,10},degree=5;
typedef struct memory{                       /*空白内存链节点*/
int start;
int size;
struct memory * next;
}memory,*mnode;


typedef struct memolist{                     /*空白内存链*/

mnode head;
mnode rear;
int rest;
}memolist,*mlist;

typedef struct requiresource{
int tsource[skinds+1];
}requiresource;


typedef struct JCB{                     /*作业控制块*/
int JID,priority,msize,runtime;
struct JCB * next;
}JCB,*JCBPtr;
                                          /*进程控制块*/
typedef struct PCB{
int PID,priority,msize,runtime,maddress,leftime,T;
requiresource * TS;
enum state Pstate;
struct PCB * next;
}PCB,*PCBPtr;

typedef struct queue{                   /*队列包括就绪队列，等待队列，挂起队列*/
PCBPtr head;
PCBPtr rear;
int length;
}queue,*Queue;

typedef struct jobqueue{                /*作业队列*/
JCBPtr head;
JCBPtr rear;
int length;
}jobqueue,*JobQueue;
void drawing(JobQueue JQ,Queue RQ,Queue SQ,Queue WQ,mlist ML,int source[])
{ int i,h=0,b=0,j,prio;
  int gd = DETECT, gm = 0;
  JCBPtr p;
  PCBPtr q;
   mnode m=ML->head->next;
   /* 和gd = VGA,gm = VGAHI是同样效果 */
  registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
  initgraph(&gd, &gm, "");
  cleardevice();
   setbkcolor(15);
   setcolor(2);
  rectangle(50,100,100,400);
  rectangle(150,100,200,400);
  rectangle(250,100,300,400);
  rectangle(350,100,400,400);
  rectangle(450,100,500,400);
  rectangle(550,100,570,400);
  rectangle(570,100,590,400);
  rectangle(590,100,610,400);
  q=RQ->head->next;
 for(i=0;i<RQ->length;i++){
  prio=q->priority;
  setcolor((prio+1)%15);
  rectangle(50,400-20*(i+1),100,400-20*i);
  setfillstyle(SOLID_FILL,(prio+1)%15);
  floodfill(75,400-20*i-10,(prio+1)%15);
  q=q->next;
  }
  p=JQ->head->next;
  for(i=0;i<JQ->length;i++){
   prio=p->priority;
   setcolor((prio+1)%15);

   rectangle(150,400-20*(i+1),200,400-20*i);
   setfillstyle(SOLID_FILL,(prio+1)%15);
   floodfill(175,400-20*i-10,(prio+1)%15);
   p=p->next;
  }
   q=WQ->head->next;
  for(i=0;i<WQ->length;i++){
   prio=q->priority;
   setcolor((prio+1)%15);

   rectangle(250,400-20*(i+1),300,400-20*i);
   setfillstyle(SOLID_FILL,(prio+1)%15);
   floodfill(275,400-20*i-10,(prio+1)%15);
   q=q->next;
  }
   q=SQ->head->next;
   for(i=0;i<SQ->length;i++){
   prio=q->priority;
  setcolor((prio+1)%15);
   rectangle(350,400-20*(i+1),400,400-20*i);
   setfillstyle(SOLID_FILL,(prio+1)%15);
   floodfill(375,400-20*i-10,(prio+1)%15);
   q=q->next;
  }





  i=0;
  while(m!=NULL){
  i++;
  h=m->start;
  b=m->size;
  setcolor((i+1)%15);
  rectangle(450,400-h,500,400-(b+h));
  setfillstyle(SOLID_FILL,(i+1)%15);
  floodfill(475,400-(2*h+b)/2,(i+1)%15);
  m=m->next;

  }


  for(i=0;i<3;i++){
  for(j=0;j<source[i];j++){
  setcolor((j+1)%15);
  rectangle(550+20*i,400-30*(j+1),550+20*(i+1),400-30*j);
  setfillstyle(SOLID_FILL,(j+1)%15);
  floodfill(550+20*i+10,400-30*j-15,(j+1)%15);

  }

  }



  getch(); /* 暂停一下，看看前面绘图代码的运行结果 */
  closegr(); /* 恢复TEXT屏幕模式 */

}




void initmemory(mlist ML){

mnode node=malloc(sizeof(memory));
ML->head=node;
ML->rear=ML->head;
ML->rest=memorysize;
ML->rear->next=NULL;
node=malloc(sizeof(memory));
node->size=memorysize;
node->start=startaddress;
node->next=NULL;
ML->rear->next=node;
ML->rear=node;

}

/*初始化队列*/
void init(Queue RQ,Queue WQ,Queue SQ,JobQueue JQ){
  JCBPtr t=malloc(sizeof(JCB));
  PCBPtr p1=malloc(sizeof(PCB)),p2=malloc(sizeof(PCB)),p3=malloc(sizeof(PCB));
  JQ->head=t;
  JQ->rear=JQ->head;
  JQ->length=0;
  JQ->rear->next=NULL;
  RQ->head=p1;
  RQ->rear=RQ->head;
  RQ->length=0;
  RQ->rear->next=NULL;
  SQ->head=p2;
  SQ->rear=SQ->head;
  SQ->length=0;
  SQ->rear->next=NULL;
  WQ->head=p3;
  WQ->rear=WQ->head;
  WQ->length=0;
  WQ->rear->next=NULL;

}

/*添加作业创建作业控制块*/
void  enJobQueue(JobQueue JQ){
  int i,n;
JCBPtr p;
printf("enter job num\n");

  scanf("%d",&n);

    for(i=0;i<n;i++){
    p=(JCBPtr)malloc(sizeof(JCB));
    printf("enter job priority\n");
    scanf("%d",&p->priority);
    printf("enter memory size\n");
    scanf("%d",&p->msize);
    printf("enter runtime\n");
    scanf("%d",&p->runtime);
    p->JID=jid++;
    p->next=NULL;
    JQ->rear->next=p;
    JQ->rear=p;
    JQ->length++;

    }

 }


 /*作业按优先级排序*/

void jobsort(JobQueue JQ){
  JCBPtr t,q,p;
  int change,i,j;
  printf("job sort....\n");
  if(JQ->length>=2)
  for(i=0;i<JQ->length-1;i++){
    t=JQ->head;
    q=JQ->head->next;
    p=q->next;
    change=0;
    for(j=0;j<JQ->length-1-i;j++){

    if(q->priority>p->priority){
    t->next=p;
    q->next=p->next;
    p->next=q;
    p=q->next;
    t=t->next;
    change=1;
    }
    else{
        t=q;
        q=p;
        p=p->next;

    }
    }
    if(i==0)JQ->rear=q;
    if(change==0)break;
}

printf("job num is %d\n",JQ->length);

}

/*紧凑技术*/
void Compaction(mlist ML,Queue RQ,Queue WQ){

     mnode m=ML->head->next,h=m->next;
     PCBPtr p,q;
     printf("compact memory.......\n");
    
     while(1){

     p=RQ->head->next,q=WQ->head->next;
     while(p!=NULL){
     if(p->maddress>=m->start+m->size&&p->maddress+p->msize<=h->start)
     p->maddress-=m->size;
     p=p->next;}
     while(q!=NULL){
     if(q->maddress>=m->start+m->size&&q->maddress+q->msize<=h->start)
     q->maddress-=m->size;
     q=q->next;}
     ML->head->next=h;
     h->start-=m->size;
     h->size+=m->size;

     free(m);
     if(h==ML->rear)break;
     m=ML->head->next;
     h=m->next;
     }
      printf("compact successful!\n");

     
}
/*申请内存空间.......*/
mnode requireformemo(JCBPtr p,mlist ML,Queue RQ,Queue WQ){
   mnode m=ML->head->next,le,h=ML->head;
    if(ML->rest>=p->msize){
    while(m!=NULL){
          printf("node's memo is %d vs JCB's need memo is %d",m->size,p->msize );
         if(m->size>=p->msize){

         if(m->size-p->msize>0){
            le=malloc(sizeof(memory));
            le->start=m->start+p->msize;
            le->size=m->size-p->msize;
            le->next=m->next;
            h->next=le;
            ML->rest-=p->msize;
            }
          else {

          h->next=m->next;
          if(m==ML->rear)ML->rear=ML->head;

          ML->rest-=m->size;
          }
          break;
          }
      else {
         h=m;
         m=m->next;
          }
    }
    if(m==NULL){
         printf("failed cause memo fragment\n");
         Compaction(ML,RQ,WQ);
         m=requireformemo(p,ML,RQ,WQ);

          }
          }
    else m=NULL;
   return m;

}

/*为作业创建进程控制块，并将其加入到就绪队列中*/
void JQtoRQ(JobQueue JQ,Queue RQ,Queue SQ,Queue WQ,mlist ML,int n){
    PCBPtr Q;
    JCBPtr p,q;
    mnode m=NULL;
    int i=n,j,c,l=JQ->length,T;
    drawing(JQ,RQ,SQ,WQ,ML,source);
     
    for(;i>0&&l>0;l--){


     m=NULL;
     p=JQ->head->next;
     m=requireformemo(p,ML,RQ,WQ);
     if(m!=NULL){
     Q=malloc(sizeof(PCB));
     printf("the %d th job's PCB creat success\n",p->JID);
     printf("the rest of the memory is %d\n",ML->rest);
     JQ->head->next=p->next;
     if(JQ->rear==p)JQ->rear=JQ->head;
     JQ->length--;
     Q->Pstate=ready;
     Q->PID=pid++;
     Q->priority=p->priority;
     Q->runtime=p->runtime;
     Q->leftime=p->runtime;
     if(Q->runtime%timeslip==0)T=Q->runtime/timeslip+2;
     else T=Q->runtime/timeslip+3;
     Q->T=T;
     Q->TS=malloc(T*sizeof(requiresource));
     printf("this procedure needs %d time slips\n",T-2);
     (Q->TS+(T-2))->tsource[0]=0;
     (Q->TS+(T-1))->tsource[0]=0;
   label:
      for(j=1;j<=skinds;j++){
     (Q->TS+(T-2))->tsource[j]=0;
     (Q->TS+(T-1))->tsource[j]=0;
     }

     for(c=0;c<T-2;c++){
     printf("input critical source during %d time slip\n",c);
     (Q->TS+c)->tsource[0]=c;

     for(j=1;j<=skinds;j++){
     scanf("%d",&(Q->TS+c)->tsource[j]);

     (Q->TS+(T-2))->tsource[j]+=((Q->TS+c)->tsource[j]);
     (Q->TS+(T-1))->tsource[j]+=((Q->TS+c)->tsource[j]);
     printf("need %d,allneed %d\n", (Q->TS+(T-2))->tsource[j],(Q->TS+(T-1))->tsource[j]);
     }
     }
     if((Q->TS+(T-1))->tsource[1]>10||(Q->TS+(T-1))->tsource[2]>10||(Q->TS+(T-1))->tsource[3]>10){
     printf("error! the totall required must less than 10 !\n");
     printf("please input again!\n");
     goto label;

     }
     Q->msize=p->msize;
     Q->maddress=m->start;
     Q->next=NULL;
     printf("the job's procedure ID is %d\n",Q->PID);
     free(m);
    if(RQ->length>0&&Q->priority<RQ->head->next->priority){          /*抢占。。。。*/
    printf("the CPU is reaved!\n");
    getch();
    Q->next=RQ->head->next;
    RQ->head->next=Q;
    }
    else{
    RQ->rear->next=Q;
    RQ->rear=Q;
    RQ->rear->next=NULL;
    }
    RQ->length++;
    drawing(JQ,RQ,SQ,WQ,ML,source);
    q=p;
    p=p->next;
    free(q);
    i--;
    }
   else{                                              /*空闲链表中无符合的空间大小*/
   printf("not enough memory,job %d failed to process\n",p->JID);
   getch();
   JQ->head->next=p->next;
   if(p==JQ->rear)JQ->rear=JQ->head;
   JQ->rear->next=p;
   JQ->rear=p;
   JQ->rear->next=NULL;
   }
   }
}

/*作业调度*/
void jobScheduling(JobQueue JQ,Queue RQ,Queue WQ,Queue SQ,mlist ML){
    int i=degree-RQ->length;
    printf("job scheduling...\n");
    getch();
    drawing(JQ,RQ,SQ,WQ,ML,source);
    if(i>0){
    jobsort(JQ);
    drawing(JQ,RQ,SQ,WQ,ML,source);
    if(i>JQ->length)i=JQ->length;
    if(i>0){
    JQtoRQ(JQ,RQ,WQ,SQ,ML,i);
    drawing(JQ,RQ,SQ,WQ,ML,source);
    }
    }
}
/*就绪队列中的进程按优先级排序*/
void Psort(Queue RQ){
  PCBPtr t,q,p=RQ->head->next;
  int change,i,j;
  printf("procedur sort...for %d procedure\n",RQ->length);
  getch();

  printf("before procedure sort.....");
  getch();
  while(p!=NULL){
  printf("procedure %d priority is %d\n",p->PID,p->priority);
  getch();
  p=p->next;

  }
  if(RQ->length>=2)
  for(i=0;i<RQ->length-1;i++){