处理器调度
班 级：10网工三班 学生姓名：谢昊天 学号：1215134046
实验目的和要求：
选择一个调度算法，实现处理器调度。在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。
实验内容与分析设计：
本实验有两个题，学生可选择其中的一题做实验。
第一题：设计一个按优先数调度算法实现处理器调度的程序。
[提示]：
(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名，指针，要求运行时间，优先数，状态
(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。
(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：
优先数-1
要求运行时间-1
来模拟进程的一次运行。
提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
(5) 进程运行一次后，若要求运行时间?0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。
(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。
(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
第二题：设计一个按时间片轮转法实现处理器调度的程序。
[提示]：
(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：进程名，指针，要求运行时间，已运行时间，状态
(2) 每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。
(3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。
(4) 处理器调度总是选择标志单元指示的进程运行。
(5) 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间?已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。
(6) 若“就绪”状态的进程队列不为空，则重复上面的（4）和(5）的步骤，直到所有的进程都成为“结束”状态。
(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。
(8) 为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。
实验步骤与调试过程:
1．打开vc,新建工程，并建基于控制台的文件
2．确定五个进程并在运行所设计的处理器调度程序前确定每个进程要求运行时间
3．把五个进程按顺序排成循环队列，用指针指出队列连接情况
4．需求分析：了解基本原理，确定程序的基本功能，查找相关资料，画出基本的数据流图；【先来先服务流程图】（开始 -> 初始化说有的JCB 使JCB按作业提交的时刻的先后顺序排队时间量T1=0 -> 调度对首作业投入运行->计算并打印作业i的完成时间Tc，周转时间Ti带权周转时间Wi -> 更改时间量T的值 -> 等待队列空？ - > 空 （不空—>调度对首作业投入运行）-> 计算并打印这组作业的平均周转时间及带权平均周转时间 –> 结束）；【高优先权流程图】（开始 -> 初始化PCB，输入进程信息 -> 各进程按优先数从高到低排列 -> 就绪队列空？ -> （空 -> 结束） 不空 -> 就绪队列进程投入运行 -> 时间片到，运行进程已占用CPU时间+1 -> 运行进程已占用CPU时间已达到所需的运行时间 -> (已到达 -> 进程完成，撤销该进程) -> 未到达 ->是运行进程的优先数-1 把运行进程插入就绪队列 -> 就绪队列空？ ->…… ）【按时间片轮转调度】（系统初始化 -> 启动计数器 -> 读取DTMF编码、摘、挂机信号 -> 0→用户编号 -> 所有用户任务以调用？ -> (没有调用 -> 根据用户编号，子程序号调用相应任务 -> 指向下一用户，编号+1 -> 所有用户任务以调用？ -> ……) 已调用 -> 发送DTMF编码 -> 定时时间已到？ -> （没有到 -> 定时时间已到？ -> ……） -> 已到 -> 启动计数器）
6.在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化
7.为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。
5．运行测试；
实验结果：
运行后可执行输入总进程个数后，显示出进程名，总运行时间，已运行时间，状态等信息，分别开始运行程序。运行完毕后会显示a进程已运行结束，进程被删除。完成处理器调度试验。
四、疑难与小结：
通过本次试验，我对处理器调度思想有了进一步的了解，通过动手实现其调度算法，更加深刻的理解了时间片轮调度算法与其他几种算法的不同优点。同时，在实验过程中，回顾书本上的理论知识，巩固了我的知识。
1.轮转法就是按一定时间片(记为q)轮番运行各个进程。如果q是一个定值，则轮转法是一种对各进程机会均等的调度方法。
2.优先级调度的基本思想是，把当前处于就绪队列中优先级最高的进程投入运行，而不管各进程的下一个CPU周期的长短和其他因素。
3.先来先服务调度算法：高响应比优先实现进程调度.(用C语言实现), 如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务（FCFS：first come first service）总是把当前处于就绪队列之首的那个进程调度到运行状态。
4.优先级调度程序：该程序由主程序、构造队列子程序、打印子程序、运行子程序构成。
5.时间片轮转法程序：在此程序中由于程序比较小，未进行分模块设计。直接采用单一模块。
五、主要算法和程序清单：
按时间片轮转法：
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct PNode {
struct PNode *next;
char name[10];
int ALL_Time;
int Runed_Time;
char state;
}* Proc;
int ProcNum;
void InitPCB(Proc &H){
cout<<"请输入总进程个数:";
cin>>ProcNum;
int Num=ProcNum;
H=(Proc)malloc(sizeof(PNode));
H->next=NULL;
Proc p=H;
cout<<"总进程个数为"<<ProcNum<<" 个,请依次输入相应信\n\n";
while(Num--){
p=p->next=(Proc)malloc(sizeof(PNode));
cout<<"进程名 总运行时间 已运行时间:";
cin>>p->name>>p->ALL_Time>>p->Runed_Time;
p->state='R';
p->next=NULL;
}
p->next=H->next;
}
void DispInfo(Proc H){
Proc p=H->next;
do{
if(p->state !='E')
{
cout<<"进程名:"<<p->name<<"\t总运行时间:"<<p->ALL_Time
<<"\t已运行时间:"<<p->Runed_Time
<<"\t状态:"<<p->state<<endl;
p=p->next;
}
else p=p->next;
}while (p!=H->next);
}
void SJP_Simulator(Proc &H){
cout<<endl<<" START \n";
int flag=ProcNum;
int round=0;
Proc p=H->next;
while (p->ALL_Time >p->Runed_Time){
round++;
cout<<endl<<"Round "<<round<<"--正在运行 "<<p->name<<"进程"<<endl;
p->Runed_Time++;
DispInfo(H);
if(p->ALL_Time == p->Runed_Time){
p->state='E';
flag--;
cout<<p->name<<"进程已运行结束，进程被删除!\n";
}
p=p->next;
while (flag &&p->ALL_Time == p->Runed_Time)
p=p->next;
}
cout<<endl<<" END \n";
}
void main(){
Proc H;
InitPCB(H);
DispInfo(H);
SJP_Simulator(H);
system("pause");
}
先来先服务法：
#include<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");
}
}
}
优先级调度方法：
#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();
}