last.c

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

    t=RQ->head;
    q=RQ->head->next;
    p=q->next;

    change=0;
    for(j=0;j<RQ->length-1-i;j++){
        if(p!=NULL)
    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)RQ->rear=q;
    if(change==0)break;
}


}
/*进程调度*/
void proScheduling(JobQueue JQ,Queue RQ,Queue SQ,Queue WQ,mlist ML){
 printf("procedure scheduling...\n");
 getch();
 drawing(JQ,RQ,SQ,WQ,ML,source);

 if(RQ->length>1){
 Psort(RQ);

 drawing(JQ,RQ,SQ,WQ,ML,source);


}
}
/*释放内存空间*/
void releasememo(PCBPtr p,mlist ML){
 mnode m=ML->head->next,h=ML->head,np;
  printf("the memory before release is %d\n",ML->rest);
  printf("the released memory is %d\n",p->msize);

  /*drawing();*/

 while(p->maddress>m->start){
    h=m;
    m=m->next;
 }
    if(h!=ML->head){
    if(h->start+h->size==p->maddress){
    if(p->maddress+p->msize==m->start){
    h->size+=p->msize+m->size;
    h->next=m->next;
    free(m);

    }
       else h->size+=p->msize;
    }
    else if(p->maddress+p->msize==m->start){
    m->start=p->maddress;
    m->size+=p->msize;
    }
    else {
     np=malloc(sizeof(memory));
     np->start=p->maddress;
     np->size=p->msize;
     np->next=m;
     h->next=np;

    }
    }
    else{
    if(p->maddress+p->msize==m->start){
    m->start=p->maddress;
    m->size+=p->msize;
    }
    else {
     np=malloc(sizeof(memory));
     np->start=p->maddress;
     np->size=p->msize;
     np->next=m;
     h->next=np;

    }
    }
    ML->rest+=p->msize;
    printf("memory release successful...\n");
    printf("the memory after release is %d\n",ML->rest);
   
    getch();

}

/*银行家算法*/
int Banker(int s[],Queue RQ){
int work[skinds],i=0,c,j,t,T,flag,k=0,d;
int m[5];
PCBPtr p=RQ->head->next,h;
t=(p->runtime-p->leftime)/timeslip;
T=p->T-2;
for(i=0;i<skinds;i++)   /*work[]为临时工作区,保存可分配资源*/
work[i]=s[i];
 /*运行到t时间片时的资源请求*/
for(i=0;i<skinds;i++){
printf("%d VS %d\n",(p->TS+t)->tsource[i+1],work[i]);
if((p->TS+t)->tsource[i+1]>work[i]){
printf("Available is less than required!\n");
return 0; /*检查可分配资源能满足请求*/
}
}
for(i=0;i<skinds;i++){              /*将资源分配模拟分配给进程*/
work[i]-=(p->TS+t)->tsource[i+1];
(p->TS+T)->tsource[i+1]-=(p->TS+t)->tsource[i+1];
}


while(1){                                /*安全算法*/
h=RQ->head->next;
flag=0;
for(i=0;i<RQ->length;i++){
T=h->T-2;
for(j=0;j<skinds;j++){
printf("%d VS %d\n",(h->TS+T)->tsource[j+1],work[j]);
if((h->TS+T)->tsource[j+1]>work[j])break;
}
 if(j==skinds){
 for(d=0;d<k;d++)if(m[d]==h->PID)break;
 if(d==k){
 for(c=0;c<skinds;c++)
 work[c]+=(h->TS+(T+1))->tsource[c+1]-(h->TS+T)->tsource[c+1];
 m[k]=h->PID;
 k++;
 flag=1;
 }
 }

 getch();
 if(k==RQ->length){
 printf("safe sequence....");
 for(flag=0;flag<k;flag++)printf("%d \t",m[flag]);
 return 1;
}
 h=h->next;
}

if(flag==0){
for(i=0;i<skinds;i++){              /*将资源分配模拟分配给进程*/
(p->TS+T)->tsource[i+1]+=(p->TS+t)->tsource[i+1];
}
return 0;

 }


}


}
/*将就绪队列中的进程加入等待队列，或将挂起队列中的节点加入等待队列*/

void QmovtoWQ(Queue Q,Queue WQ){

 PCBPtr p=Q->head->next;
 printf("put the procedure into the waitQueue...");
 getch();
 Q->head->next=p->next;
 if(p==Q->rear)Q->rear=Q->head;
 p->Pstate=wait;
 WQ->rear->next=p;
 WQ->rear=p;
 WQ->rear->next=NULL;
 Q->length--;
 WQ->length++;

}




/*将等待队列中的进程加入就绪队列*/
void WQmovtoRQ(Queue WQ,Queue RQ){

 PCBPtr p=WQ->head->next;

 int i=degree-RQ->length;
 if(WQ->length>0){
 printf("put the procedure from waitQueue into readyQueue\n");
 getch();
 if(i>0) {
 WQ->head->next=p->next;
 if(p==WQ->rear)WQ->rear=WQ->head;
 p->Pstate=ready;
 RQ->rear->next=p;
 RQ->rear=p;
 RQ->rear->next=NULL;
 WQ->length--;
 RQ->length++;
}
}
else printf("no procedure in the waitqueue\n");
}



/*模拟运行*/

void  Run(JobQueue JQ,Queue RQ,Queue SQ,Queue WQ,mlist ML){                      /*Queue SQ,Queue WQ*/
  PCBPtr p=RQ->head->next;
  int t=timeslip,i,j,T,tsn;
  printf("running.....\n");
  getch();

  p->Pstate=run;

  i=Banker(source,RQ);    /* 欲分配资源 */
  if(i==0){QmovtoWQ(RQ,WQ);drawing(JQ,RQ,SQ,WQ,ML,source);}
  else{
  printf("procedure %d is Runing....\n",p->PID);
   getch();
  tsn=(p->runtime-p->leftime)/timeslip;
  for(j=0;j<skinds;j++){
  source[j]-=(p->TS+tsn)->tsource[j+1];
  }
  drawing(JQ,RQ,SQ,WQ,ML,source);
  p->priority++;
  if(t>p->leftime)t=p->leftime;
  p->leftime-=t;
  p->Pstate=ready;
  if(p->leftime==0){
  RQ->length--;
  printf("procedure %d is finish...\n",p->PID);

  T=p->T-1;
  releasememo(p,ML);

  for(j=0;j<skinds;j++){
  source[j]+=(p->TS+T)->tsource[j+1];
  }

  RQ->head->next=p->next;
  if(p==RQ->rear)RQ->rear=RQ->head;
  free(p);
  WQmovtoRQ(WQ,RQ);
  drawing(JQ,RQ,SQ,WQ,ML,source);

}
}
}






/*将就绪队列中的进程加入挂起队列*/
void  RQmovtoSQ(Queue RQ,Queue SQ,mlist ML){
 PCBPtr p=RQ->head->next,h=RQ->head;
 int j,T,ts;
 printf("put the procedure from readyQueue into the suspendQueue\n");
 printf("which procedure do you want to suspend? input the PID\n");
 scanf("%d",&j);
 while(p->PID!=j&&p!=NULL)
 {h=p;
  p=p->next;
 }
 if(p!=NULL){
 h->next=p->next;
 if(p==RQ->rear)RQ->rear=h;
 releasememo(p,ML);

 T=p->T-1;
 for(j=0;j<skinds;j++){
  source[j]+=(p->TS+T)->tsource[j+1]-(p->TS+(T-1))->tsource[j+1];
  (p->TS+(T-1))->tsource[j+1]=(p->TS+T)->tsource[j+1];
  }
  ts=(p->runtime-p->leftime)/timeslip;
  p->priority-=ts;
  p->leftime=p->runtime;

  p->Pstate=suspend;
 SQ->rear->next=p;
 SQ->rear=p;
 SQ->rear->next=NULL;
 RQ->length--;
 SQ->length++;
 printf("RQmovtoSQ successfully!\n");
 getch();
 }
 else {printf("failed to suspend the procedure for it is not in the readyQueue\n");
     getch();
}
}




mnode requireformemo2(PCBPtr p,mlist ML,Queue RQ,Queue WQ){
 mnode m=ML->head->next,le,h=ML->head;
  if(ML->rest>=p->msize){
 while(m!=NULL){

         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 {
          p->msize=m->size;
          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){
         Compaction(ML,RQ,WQ);
         m=requireformemo2(p,ML,RQ,WQ);

          }
    }
    else m=NULL;
   return m;

}


/*将挂起队列中的进程加入就绪队列或等待队列*/
void  SQmovtoRQ(Queue SQ,Queue RQ,Queue WQ,mlist ML){
 PCBPtr p=SQ->head->next;
 int i=degree-RQ->length;
 mnode m=NULL;

 if(i>0){
 m=requireformemo2(p,ML,RQ,WQ);
 if(m!=NULL){
 SQ->head->next=p->next;
 if(p==SQ->rear)SQ->rear=SQ->head;
 p->Pstate=ready;
 RQ->rear->next=p;
 RQ->rear=p;
 RQ->rear->next=NULL;
 SQ->length--;
 RQ->length++;
 printf("put the procedure from suspendQueue into readyQueue\n");
 getch();
 }
 else{
 printf("not enough memory for the suspendprocedure into readyQueue\n");
 getch();

 }
}
else {
 m=requireformemo2(p,ML,RQ,WQ);
 if(m!=NULL){
 QmovtoWQ(SQ,WQ);
 printf("put the procedure from suspendQueue into waitQueue\n");
 getchar();
 }
 else{
 printf("not enough memory for the suspendprocedure into readyQueue\n");
  getchar();
 }
}
}



/*主函数*/

main()
{ Queue RQ,SQ,WQ;
  JobQueue JQ;
  mlist ML;
  char a;
  JQ=malloc(sizeof(jobqueue));
  RQ=malloc(sizeof(queue));
  WQ=malloc(sizeof(queue));
  SQ=malloc(sizeof(queue));
  ML=malloc(sizeof(memolist));
  initmemory(ML);
  init(RQ,SQ,WQ,JQ);
  drawing(JQ,RQ,SQ,WQ,ML,source);

  enJobQueue(JQ);
  drawing(JQ,RQ,SQ,WQ,ML,source);

  
  while(1){
   if(RQ->length!=0||JQ->length!=0){
   jobScheduling(JQ,RQ,SQ,WQ,ML);
   drawing(JQ,RQ,SQ,WQ,ML,source);
   proScheduling(JQ,RQ,SQ,WQ,ML);
   Run(JQ,RQ,SQ,WQ,ML);
   getchar();
   printf("continue to add job? press 'Y' to confirm.\n");
   a=getchar();
   if(a=='Y'||a=='y'){
   enJobQueue(JQ);
   drawing(JQ,RQ,SQ,WQ,ML,source);

   }
   a='A';
   while(a!='N'){
   printf("Do you want to suspend any node? press 'Y' to confirm.\n");
   a=getchar();
   if(a=='Y'||a=='y'){
   RQmovtoSQ(RQ,SQ,ML);
   drawing(JQ,RQ,SQ,WQ,ML,source);
   }
   }
   a='A';
   while(a!='N'){
   printf("Do you want to dissuspend any node? press 'Y' to confirm.\n");
   a=getchar();
   if(a=='Y'||a=='y'){
   SQmovtoRQ(SQ,RQ,WQ,ML);
   drawing(JQ,RQ,SQ,WQ,ML,source);

   }
   }

  }

  else {
         printf("no job or process to run!\n");
         getch();
         break;
       }
   
   }

}