sjf2.c

用C语言实现的最短作业优先（包括抢占式和非抢占式）调度。

#include "stdio.h"
#include <stdlib.h>
char ch;
/*短作业优先算法*/
struct pro
{ char name[10];/*进程名*/
  int arrivetime;/*到达时间*/
  int burst;/*运行时间*/
  struct pro *next;
};
/*函数声明*/
struct pro *creatlist();
void insert(struct pro *head,struct pro *s);
struct pro *searchByAT(struct pro *head,int AT);
void run(struct pro *head);
void del(struct pro *p);
int getcount(struct pro *head,int time);
struct pro  *creatlist()  /*创建链表，按照进程的到达时间排列*/
{  int i,MAX;/*MAX表示进程数*/
   struct pro *s;
   struct pro *head=(struct pro *)malloc(sizeof(struct pro));
   head->next=NULL;
   /*struct pro *s;*/
   /*int i;*/
  printf("\n\ninput the number of processes");
  scanf("%d",&MAX); 
  for(i=0;i<MAX;i++)
   {
       s=(struct pro *)malloc(sizeof(struct pro));
       printf("input the name:");
       scanf("%s",&(s->name));
       printf("input the arrival time:");
       scanf("%d",&(s->arrivetime));
       printf("input the burst time:");
       scanf("%d",&(s->burst));
       printf("\n");
       s->next=NULL;
       insert(head,s);
   }
   return head;
}
void insert(struct pro *head,struct pro *s)  /*插入结点*/
{  struct pro *p=searchByAT(head,s->arrivetime);
    s->next=p->next;
    p->next=s;
    return;
}
struct pro *searchByAT(struct pro *head,int AT)  /*查找第一个到达时间大于等于AT的节点，返回其前一个指针*/
{ struct pro *p,*q;
    p=head;
    q=head->next;
    while(q!=NULL&&q->arrivetime<=AT)
     { p=q;
       q=q->next;
     }
     return p;
}
void del(struct pro *p)  /*删除P的下一个节点*/ 
{ struct pro *tmp;
  tmp=p->next;
  p->next=tmp->next;
  free(tmp);
  return;
}
int getcount(struct pro *head,int time)  /*查看当前就绪队列中的进程数*/
{ int count=0;
  struct pro *p,*q;
  p=head;
  q=p->next;
  while(q!=NULL&&q->arrivetime<=time)
  { count++;
      p=q;
      q=q->next;
  }
  return count;
}
struct pro *SJF(struct pro *head,int count) /*在头结点后的count个节点中选择burst最小的，返回其前一个节点的指针*/
{ int min;
  struct pro *p,*q,*flag;
  p=head;
  q=p->next;
  min=q->burst;
  flag=p;    /*flag记录返回指针*/
  while(count>0)
  { if(q->burst<min)
      { min=q->burst;
        flag=p;
      }
      count--;
      p=q;
      q=q->next;
  }
  return flag;
}
void run(struct pro *head) /*按短作业优先算法调度进程，并输出其运行情况*/
{ int time=0;
  int count;
  struct pro *s,*t;
  while(head->next!=NULL)
  { count=getcount(head,time);
    if(count==0)    /*如果当前就绪队列中没有进程，时间自增*/
     time++;
    else if(count==1) /*如果就绪队列中只有1个进程，则必定是第一个节点*/
       {if(ch=='1')
         {t=head;
         s=t->next;
         printf("name:%s\n",s->name);
         printf("arrival time:%d\n",s->arrivetime);
         printf("running time begins at:%d\n",time);
         printf("response time%d\n",time-s->arrivetime);
         time+=s->burst;
         printf("running time ends at:%d\n",time);
         printf("turnaround time:%d\n",time-s->arrivetime);
         printf("*****************************\n");
         del(t);}
        if(ch=='2')
          { t=head;
          s=t->next;
          printf("name:%s\n",s->name);
          printf("arrival time:%d\n",s->arrivetime);
          printf("running time begins at:%d\n",time);
          time++;
          s->burst--;
          printf("runnimg time:\n");
          printf("remainging time:%d\n",s->burst);
          printf("*****************************\n");
          printf("\n");
          if(s->burst==0)
             {del(t);
              printf("%sfinished\n",s->name); }
          }
          getch();
        }
   else    /*如果就绪队列中的进程数>=2，则在head后的count个节点中进行短作业优先调度*/
    {  if(ch=='1'){
           t=SJF(head,count);
           s=t->next;
           printf("name:%s\n",s->name);
           printf("arrival time:%d\n",s->arrivetime);
           printf("runnig time begins at:%d\n",time);
        printf("response time:%d\n",time-s->arrivetime);
        time+=s->burst;
        printf("running time ends at:%d\n",time);
        printf("turnaround time:%d\n",time-s->arrivetime);
        printf("*****************************\n");
        del(t);}
        if(ch=='2'){  t=SJF(head,count);
      s=t->next;
      printf("name:%s\n",s->name);
      printf("arrival time:%d\n",s->arrivetime);
      printf("running time begins:%d\n",time);
      time++;
      s->burst--;
      printf("running time：1\n",time);
      printf("remaining time:%d\n",s->burst);
      printf("*****************************\n");
      printf("\n");
      if(s->burst==0)
      {del(t);
       printf("%sfinished\n",s->name); }
       }
      getch();
    }

}
}
void main()
{ struct pro *head;
  start:clrscr();
  printf("1nonpreemptive SJF\n");
  printf("2preemptive SJF\n");
  printf("3quit\n");
  printf("please choose:");
  scanf("%c",&ch);
  switch(ch){
  case '1':
  case '2':head=creatlist();
  printf("CPU scheduling as follows\n");
  run(head);
  printf("all processes finished\npress any key to continue");
  getch();
  goto start;
  case '3':exit(0);
  default:goto start;
  }

}