操作系统编程进程或作业先来先服务、高优先权、按时间片轮转调度算法.docx

湖南农业大学科学技术师范学院
学 生 实 验 报 告

姓名： 汤黎波 年级专业班级 06级计算机教育班 日期 2008 年 12 月 8 日 成绩
课程名称
计算机操作系统
实验名称
编程进程或作业先来先服务、高优先权、按时间片轮转调度算法(4学时)
实验类型
验证 设计
综合 创新

【实验目的、要求】
实验目的：（1）通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。
（2）了解Windows2000/XP中进程（线程）的调度机制。
（3）学习使用Windows2000/XP中进程（线程）调度算法，掌握相应的与调度有关的Win32 API函数。
实验要求：（1）经调试后程序能够正常运行。
（2）采用多进程或多线程方式运行，体现了进程或作业先来先服务、高优先权、按时间片轮转调度的关系。
（3）程序界面美观。
【实验内容】
在Windows XP、Windows 2000等操作系统下，使用C语言，利用相应的WIN32 API函数，编写程序实现进程或作业先来先服务、高优先权、按时间片轮转调度算法。

【实验环境】（含主要设计设备、器材、软件等）
Pc电脑一台
【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）
定义:  
1)先来先服务算法：如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务（FCFS：first come first service）总是把当前处于就绪队列之首的那个进程调度到运行状态。
2)轮转法就是按一定时间片(记为q)轮番运行各个进程。如果q是一个定值，则轮转法是一种对各进程机会均等的调度方法。
3)优先级调度的基本思想是，把当前处于就绪队列中优先级最高的进程投入运行，而不管各进程的下一个CPU周期的长短和其他因素。
实验步骤： （1）需求分析：了解基本原理，确定程序的基本功能，查找相关资料，画出基本的数据流图；
（2）概要设计：确定程序的总体结构、模块关系和总体流程；
（3）详细设计：确定模块内部的流程和实现算法；
（4）上机编码和调试；
（5）运行测试；
（6）编写实验报告。

流程图：

（先来先服务流程图）

（高优先权流程图）

（按时间片轮转调度）

程序说明及实现:  
  1)先来先服务调度算法：
高响应比优先实现进程调度.(用C语言实现),
2) 优先级调度程序：  
  该程序由主程序、构造队列子程序、打印子程序、运行子程序构成。        
  3) 时间片轮转法程序：    
  在此程序中由于程序比较小，未进行分模块设计。直接采用单一模块。

1先来先服务
＃i nclude<stdio.h>
float t,d; /*定义两个全局变量*/
struct /*定义一个结构体数组，包括进程的信息*/
{
int id;
float ArriveTime;
float RequestTime;
float StartTime;
float EndTime;
float RunTime;
float DQRunTime;
int Status;
}arrayTask[4]; /*定义初始化的结构体数组*/
GetTask()/*给结构体数组赋值，输入到达，服务时间*/
{ int i;
float a;
for(i=0;i<4;i++)
{arrayTask[i].id=i+1;
printf("input the number");
printf("input the the ArriveTime of arrayTask[%d]:",i); /*用户输入进程的时间，初始为零 */
scanf("%f",&a);
arrayTask[i].ArriveTime=a;
printf("input the RequestTime of arrayTask[%d]:",i);
scanf("%f",&a);
arrayTask[i].RequestTime=a;
arrayTask[i].StartTime=0;
arrayTask[i].EndTime=0;
arrayTask[i].RunTime=0;
arrayTask[i].Status=0; /*开始默认的标志位零*/
}
}
int fcfs() /*定义FCFS中寻找未执行的进程的最先到达时间*/
{
int i,j,w=0; /*在结构体数组中找到一个未执行的进程*/
for(i=0;i<4;i++)
{
if(arrayTask[i].Status==0)
{
t=arrayTask[i].ArriveTime;
w=1;
}
if(w==1)
break;
}
for(i=0;i<4;i++) /*查找数组中到达时间最小未执行的进程*/
{
if(arrayTask[i].ArriveTime<t&&arrayTask[i].Status==0)
t=arrayTask[i].ArriveTime;
} /*返回最小到达时间的数组的下标*/
for(i=0;i<4;i++)
{
if (arrayTask[i].ArriveTime==t)
return i;
}
}
int sjf() /*定义FCFS中寻找未执行的进程的最先到达时间*/
{
int i,x=0,a=0,b=0; /*判断是不是第一个执行的进程*/
float g;
for(i=0;i<4;i++)
{
if(arrayTask[i].Status==1)
{g=arrayTask[i].EndTime;
x=1;
}
}
if(x==0) /*第一个执行的进程按FCFS*/
{
t=arrayTask[0].ArriveTime;
for(i=0;i<4;i++)
{
if(arrayTask[i].ArriveTime<t)
{ t=arrayTask[i].ArriveTime;
a=i;
}
}
return a;}
else
{
for(i=0;i<4;i++)
{if(arrayTask[i].EndTime>g)
g=arrayTask[i].EndTime;
}
for(i=0;i<4;i++)
{if(arrayTask[i].Status==0&& arrayTask[i].ArriveTime<=g)
{t=arrayTask[i].RequestTime;
a=i;
b=1;} /*判断有没有进程在前个进程完成前到达*/
}
if(b!=0) /*有进程到达则按SJF*/
{for(i=0;i<4;i++)
{
if(arrayTask[i].Status==0&&arrayTask[i].ArriveTime<=g&&arrayTask[i].RequestTime<t)
{t=arrayTask[i].RequestTime;
a=i;}
}
return a;}
else{ /*否则按FCFS*/
for(i=0;i<4;i++)
{if(arrayTask[i].Status==0)
t=arrayTask[i].ArriveTime;
}
for(i=0;i<4;i++)
{
if(arrayTask[i].Status==0&&arrayTask[i].ArriveTime<t)
{t=arrayTask[i].ArriveTime;
a=i;
}
}
return a;}
}
}
new(int s) /*定义执行进程后相关数据的修改*/
{
int i,g=0;
for(i=0;i<4;i++)
{
if(arrayTask[i].Status==0)
continue;
else
{
g=1;
break;
}
}
if(g==0) /*当处理的是第一个未执行的进程时执行*/
{
arrayTask[s].StartTime=arrayTask[s].ArriveTime;
arrayTask[s].EndTime=arrayTask[s].RequestTime+arrayTask[s].ArriveTime;
arrayTask[s].RunTime=arrayTask[s].RequestTime;
arrayTask[s].Status=1;
g=2;
}
if(g==1) /*当处理的不是第一个未执行的进程时执行*/
{
arrayTask[s].Status=1;
for(i=0;i<4;i++)
{
if(arrayTask[i].Status==1)
d=arrayTask[i].EndTime;
}
for(i=0;i<4;i++) /*查找最后执行的进程的完成时间*/
{
if(arrayTask[i].EndTime>d&&arrayTask[i].Status==1)
d=arrayTask[i].EndTime;
}
if(arrayTask[s].ArriveTime<d) /*判断修改的进程的到达时间是否在前一个执行的进程的完成时间前面*/
arrayTask[s].StartTime=d;
else
arrayTask[s].StartTime=arrayTask[s].ArriveTime;
arrayTask[s].EndTime=arrayTask[s].StartTime+arrayTask[s].RequestTime;
arrayTask[s].RunTime=arrayTask[s].EndTime-arrayTask[s].ArriveTime;
}
arrayTask[s].DQRunTime=arrayTask[s].RunTime/arrayTask[s].RequestTime;
}
Printresult(int j) /*定义打印函数*/
{
printf("%d\t",arrayTask[j].id);
printf("%5.2f\t",arrayTask[j].ArriveTime);
printf("%5.2f\t",arrayTask[j].RequestTime);
printf("%5.2f\t",arrayTask[j].StartTime);
printf("%5.2f\t",arrayTask[j].EndTime);
printf("%5.2f\t",arrayTask[j].RunTime);
printf("%5.2f\n",arrayTask[j].DQRunTime);
}
main()
{ int i,b,k,a,c=0;
int d[4];
clrscr();
printf("\t F. FCFS \n");
printf("\t S. SFJ  \n");
printf("\t Q. EXIT \n");
for(i=0;;i++)
{if(c)
break;
printf("please input the number a:\n");
scanf("%d",&a);
switch(a)
{
case Q: c=1;
break;
case F:printf("please input the different-ArriveTime of arrayTasks\n");
GetTask();
printf("*****************************the result of fcfs\n");
printf("Number\tArrive\tServer\tStart\tFinish\tTurnove\tTake power turnover time\n");
for(b=0;b<4;b++) /*调用两个函数改变结构体数的值*/
{
k=fcfs();
d[b]=k;
new(k);
}
for(b=0;b<4;b++)
Printresult(d[b]);/*调用打印函数打出结果*/
continue;
case S: printf("please input the different-RequestTime of arrayTasks\n");
GetTask();
printf("******************************the result of sjf\n");
printf("Number\tArrive\tRequest\tStart\tEnd\tRun\tDQRun time\n");
for(b=0;b<4;b++)
{
k=sjf();
d[b]=k;
new(k);
}
for(b=0;b<4;b++)
Printresult(d[b]);
continue;
default:printf("the number Error.please input another number!\n");
}
}
}
2 时间片轮转法：  
  #include"string.h"  
  #include   "stdio.h"  
  #include   "conio.h"  
  #include   "graphics.h"  
  #define   NULL   0  
  typedef   struct   quen       /*定义结构*/  
  {   char   pname[8];  
      int     time1;  
      int     time2;  
      char   state;  
      struct   quen   *next;  
  }   QUEN;  
  main()/*主程序*/  
            {  
                QUEN   *q,*p,*head,*m;  
                char   str[8],f;  
                int   t,d,n;  
                clrscr();  
  textmode(C80);  
  textbackground(0);  
  textcolor(15);  
  printf("Enter the maxnumber of nodes(n):\n");/*输入进程数*/  
  scanf("%d",&n);  
  d=n;  
  if(d>0)  
  {   printf("enter thepname:");  
    scanf("%s",str);  
    printf("enter   the   need   time:");  
    scanf("%d",&t);  
    head=p=(QUEN   *)malloc(sizeof(QUEN));  
    strcpy(p->pname,str);  
    p->time1=t;  
    p->time2=0;  
    p->state='R';  
    p->next=NULL;  
    head=p;  
    getchar();  
    --d;}  
  while(d>0)   {/*构建队列表*/  
    printf("enter   the   pname:");  
    scanf("%s",str);  
    printf("enter   need   time:");  
    scanf("%d",&t);  
    q=(QUEN   *)malloc(sizeof(QUEN));  
    strcpy(q->pname,str);  
    q->time1=t;  
    q->time2=0;  
    q->state='R';  
    q->next=NULL;  
    p->next=q;  
    p=q;  
  --d;  
  p->next=head;  
  q=head;}  
  printf("process name need time runned static\n");  
  do{   printf(" %s%d %d %c\n",q->pname,q->time1,q->time2,q->state);  
       q=q->next;  
      }while(q!=head);  
      printf("\n");  
  do{  

 if(head->time2<head->time1)  
  {head->time2++;  
    if(head->time2==head->time1)  
      {   head->state='E';  
            q=head;  
            textbackground(0);  
            printf("The running process is %s\n",q->pname);  
            printf("process name left time runned static\n");  
        do{   textcolor(15);  
  /*输入队列表*/  
        printf(" %s %d %d %c\n",q->pname,q->time1,q->time2,q->state);  
  q=q->next;}  
  while(q!=head);  
        printf("\n");  
        head=head->next;  
        q=head;  
        p->next=head;  
         }  
    else{  
    printf("The running process is %s\n",q->pname);  
      printf("process name left time runned static\n");  
      do {  
            printf(“%s%d%d %c\n",q->pname,q->time1,q->time2,q->state);  
              q=q->next;}while(q!=head);  
              printf("\n");  
              head=head->next;  
              q=head;  
              p=p->next;}  

    printf("Is it needing new process?(y or n)\n");/*是否加入新的进程*/  
        getchar();  
        scanf("%c",&f);  
    if(f=='Y'||f=='y'){  
        getchar();  
        printf("Enter the new pname:");  
        scanf("%s",str);  
        printf("Enter the new neededtime:");  
        scanf("%d",&t);  
    m=(QUEN   *)malloc(sizeof(QUEN));  
    strcpy(m->pname,str);  
    m->time1=t;  
    m->time2=0;  
    m->state='R';  
    m->next=NULL;  
  if(q->next->state=='E')  
        {p=m;  
          head=m;  
          p->next=head;  
  q=head;}  
  else{p->next=m;  
          m->next=head;  
          p=m;}}  
  }}while(q->next->state!='E');  
        printf("The processes are finished\n");  
  }  
 3优先级调度方法：  
  #include     <stdio.h>  
  #include   "conio.h"  
  typedef   struct   pcb/*定义结构*/  
          {char name[5];  
            struct pcb *next;  
            int   needtime;  
            int   priority;  
            char state[5];  
          }NODE;  

  NODE  *create_process(int   n)/*创建队列*/  
        {NODE     *head,*s,*t;  
          int   time,i=0,j;  
          char     pname[5];  
          head=(NODE   *)malloc(sizeof(NODE));  
          printf("please   input   process   name:");  
          scanf("%s",pname);  
          strcpy(head->name,pname);  
          printf("please   input   need   time:");  
          scanf("%d",&time);  
          head->needtime=time;  
          printf("please   input   priority:");  
          scanf("%d",&j);  
          head->priority=j;  
          strcpy(head->state,"ready");  
          head->next=NULL;  
          t=head;  
          for(i=1;i<n;i++)  
              {  s=(NODE *)malloc(sizeof(NODE));  
  printf("please input process name:");  
  getchar();  
  gets(pname);  
  strcpy(s->name,pname);  
  printf("please input need time:");  
  canf("%d",&time);  
  s->needtime=time;  
  printf("please input priority:");  
  scanf("%d",&j);  
  s->priority=j;  
  strcpy(s->state,"ready");  
  s->next=NULL;  
   t->next=s;  
  t=s;  
      }  
   return  head;  
      }  
  pri_process(NODE *p)/*输出进程队列*/  
      {int   i;  
        NODE  *q;  
        q=p->next;  
        printf("\n name\tneedtime\tpriority \t state\n");  
        while(q!=NULL)  
            {printf("%5s\t %2d \t %2d \t %5s \n",  
      q->name,q->needtime,q->priority,q->state);  
              q=q->next;  
            }  
      }  
  NODE   *order(NODE   head_sort)/*对进程的优先级进行排序*/  
    {NODE   *p,*s,*q,*head,*r,*t;  
      int     m,pr;  
      char     name[5];  
      head=head_sort;  
      p=head->next;  
      r=p;  
      t=p;  
      q=p->next;  
      while(r!=NULL)  
        {   while(q!=NULL)  
            {if(p->priority<q->priority)  
  {m=p->priority;  
    p->priority=q->priority;  
    q->priority=m;  
    strcmp(name,p->name);  
    strcmp(p->name,q->name);  
    strcmp(q->name,name);  
    pr=p->needtime;  
    p->needtime=q->needtime;  
    q->needtime=pr;  
  }  
              p=q;  
              q=q->next;  
            }  
            r=r->next;  
            p=t;  
            q=p->next;  
        }  
      return(head_sort);  
  }  
  main()/*主程序*/  
  {     NODE   *p=NULL,*head=NULL,*m=NULL,*z=NULL,*n=NULL;  
        int   j,time,x=0;  
        char   c,pname[5];  
        clrscr();  
        printf("please input process number!");  
        scanf("%d",&x);  
        p=create_process(x);  
        head->next=p;  
        pri_process(head);  
        getchar();  
        while(x>0)  
            { order(head);  
  m=head->next;  
  strcpy(m->state,"run");  
  if(m->priority>=2)  
        m->priority--;  
        m->needtime--;  
  if(head->next!=NULL)  
        pri_process(head);  
  if(m->needtime==0)  
    {   head->next=m->next;  
          printf("%s   has   finished\n",m->name);  
          free(m);  
        x--;  
    }  
          getchar();     }  
          textmode(C80);  
          textbackground(0);  
          textcolor(4);  
          printf("over!");  
          getchar();  
  }  
  Top
【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见）
通过做本实验，让我对进程或作业先来先服务、高优先权、按时间片轮转调度算法以及进程调度的概念和算法，有了更深入的认识！初步理解了操作系统对于作业处理的基本思想！对于时间片轮转法的处理要比优先级调度算法的理解要深。在实验的过程中遇到了很多困难，感谢同学们的帮助。

指导教师签名：

20 年 月 日
【备注】