实验报告二
——进程调度算法的设计
姓名：xxxx 学号：xxxxx班级：xxxx
一、实习内容
? 实现短进程优先调度算法（SPF）
? 实现时间片轮转调度算法（RR）
二、实习目的
? 通过对进程调度算法的设计，深入理解进程调度的原理。
? 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
? 进程调度分配处理机，是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。
三、实习题目
1. 先来先服务（FCFS）调度算法
? 原理：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。
? 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。
? 按照就绪进程进入就绪队列的先后次序进行调度，简单易实现，利于长进程，CPU繁忙型作业，不利于短进程，排队时间相对过长。
2. 时间片轮转调度算法RR
? 原理：时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度按一定时间片(q)轮番运行各个进程.
? 进程按到达时间在就绪队列中排队，调度程序每次把CPU分配给就绪队列首进程使用一个时间片，运行完一个时间片释放CPU，排到就绪队列末尾参加下一轮调度，CPU分配给就绪队列的首进程。
? 固定时间片轮转法：
1 所有就绪进程按 FCFS 规则排队。
2 处理机总是分配给就绪队列的队首进程。
3 如果运行的进程用完时间片，则系统就把该进程送回就绪队列的队尾，重新排队。
4 因等待某事件而阻塞的进程送到阻塞队列。
5 系统把被唤醒的进程送到就绪队列的队尾。
? 可变时间片轮转法：
1 进程状态的转换方法同固定时间片轮转法。
2 响应时间固定，时间片的长短依据进程数量的多少由 T=N×(q+t)给出的关系调整。
3 根据进程优先级的高低进一步调整时间片，优先级越高的进程，分配的时间片越长。
3. 算法类型:
4. 模拟程序可由两部分组成，先来先服务(FCFS)调度算法，时间片轮转。流程图如图所示:
四、主要数据结构及符号说明
enum Status{running,ready,block} 用枚举类型来列举进程的状态
enum Algorithm{spf,rr} 用枚举类型来列举两种进程调度算法
typedef class PCB //define PCB class which store information of PCB
{
public:
int id,cputime,alltime,startblock,blocktime;//进程号、已经运行时间、还需要的时间、何时开始阻塞及阻塞时间的变量
Status state;//进程的状态
class PCB *next;//指向下一个进程的指针
PCB()
{ }
}PCB,*PCBptr,**PCBpp;
定义类类型来存储一个进程的相关信息，并用链表的方式来存放进程
五、实现代码为：
#define MAX 100
#include<stdio.h>
#include<stdlib.h>
int m,b,n,x;
int rt[10]; //到达时间
int st[10]; //服务时间
int ct[10]; //完成时间
int cyt[10]; //周转时间
/**************RR算法***************/
void RR(int N)
{
int i,t,k;
int a[MAX];//存放进程的剩余时间
int cnt[MAX];//存放进程调度次数
printf("please input the time piece(t):");
scanf("%d",&t);
for(i=0;i<N;i++)
{
printf("please input the serive time of process %d:\n",i+1);
scanf("%d",&a[i]);
cnt[i]=0;
}
k=1;
while(k)
{
for(i=0;i<N;i++)
{
if(a[i]!=0)
if(a[i]>=t)
{
a[i]-=t;
b+=t;
cnt[i]=cnt[i]+1;
printf("process name:%d \ncalled number:%d \nend time:%d\nleft time:%d\n",i+1,cnt[i],b,a[i]);
printf("*********************************\n");
}
else
{
b=b+a[i];
cnt[i]=cnt[i]+1;
a[i]=0;
printf("process name:%d\ncalled number:%d \nend time:%d\nleft time:%d \n",i+1,cnt[i],b,a[i]);
printf("*********************************\n");
}
else continue;
}
for(i=0;i<N;i++)
if(a[i]!=0)
{
k=1;break;
}
else
continue;
if(i>=N)
k=0;
}
printf("all the process have been done\n");
}
/********SPF算法*********/
//定义进程结构体
struct pro
{
int num; //进程号
int arriveTime; //到达时间
int service; //执行时间
struct pro *next;
};
//函数声明
struct pro* creatList();//创建链表，按照进程的到达时间排列
void insert(struct pro *head,struct pro *s); //插入节点
struct pro* searchByAT(struct pro *head,int AT); //查找第一个到达时间大于AT的节点，返回其前一个指针
void run(struct pro *head);//按短进程优先算法调度，并输出其运行情况
void del(struct pro* p);//删除p的下一个节点
int getCount(struct pro *head,int time);//查看当前就绪队列中的进程数
struct pro* creatList() //创建链表，按照进程的到达时间排列
{
struct pro* head=(struct pro*)malloc(sizeof(struct pro));
struct pro* s;
int i;
head->next=NULL;
for(i=0;i<x;i++)
{
s=(struct pro*)malloc(sizeof(struct pro));
printf("plaese input process name(number):\n");
scanf("%d",&(s->num));
printf("please input process arrive time\n");
scanf("%d",&(s->arriveTime));
printf("please input service time\n");
scanf("%d",&(s->service));
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* SPF(struct pro *head,int count) //在头节点后的count个节点中选择service最小的，返回其前一个节点的指针
{
int min;
struct pro *p,*q,*flag;
p=head;
q=p->next;
min=q->service;
flag=p; //flag记录返回值
while(count>0)
{
if(q->service<min)
{
min=q->service;
flag=p;
}
count--;
p=q;
q=q->next;
}
return flag;
}
void run(struct pro *head) //按短进程优先算法调度，并输出其运行情况
{
int time=0,count,i;
struct pro *s,*t;
while(head->next!=NULL)
{
count=getCount(head,time);//查看就绪队列中的进程数目
if(count==0) //如果当前就绪队列中没有进程，时间自增
time++;
else if(count==1) //如果就绪队列中只有一个进程，则必定是第一个节点
{
t=head;
s=t->next;
printf("process name：%d\n",s->num);
printf("arrive time:%d\n",s->arriveTime);
printf("serive time:%d\n\n",s->service);
printf("star time：%d\n",time);
time+=s->service;
printf("end time:%d\n",time);
printf("turnaround time:%d\n",time-s->arriveTime);
i=time-s->arriveTime;
printf("*********************************\n");
del(t);
}
else //如果就绪队列中的进程数≥2，则在head后的count个节点中的短进程优先调度
{
t=SPF(head,count);
s=t->next;
printf("process name：%d\n",s->num);
printf("arrive time :%d\n",s->arriveTime);
printf("serive time:%d\n\n",s->service);
printf("star time%d\n",time);
time+=s->service;
printf("end time:%d\n",time);
printf("turnaround time:%d\n",time-s->arriveTime);
i=time-s->arriveTime;
printf("*********************************\n");
del(t);
}
}
}
/******FCFS算法**********/
void FCFS(int x)
{
void input(); //输入数据
void ordination(); //对数据按到达时间进行排序
void fcfs(); //先来先服务计算
void output(); //输出结果
printf("/*********FCFS*********/\n");
input(x);
ordination(x);
fcfs(x);
output(x);
}
void input(int x)
{
printf("please input arrive time of the %d processes:",x);
for (n=0;n<x;n++)
scanf("%d",&rt[n]);
printf("please input serivce time of the %d processes:",x);
for (n=0;n<x;n++)
scanf("%d",&st[n]);
}
void ordination(int x)
{
int temp;
for (n=0;n<x;n++)
for (m=0;m<x-n-1;m++)
if (rt[m+1]<rt[m])
{
temp=rt[m+1];
rt[m+1]=rt[m];
rt[m]=temp;
temp=st[m+1];
st[m+1]=st[m];
st[m]=temp;
}
}
void fcfs(int x) {
ct[0]=rt[0]+st[0];
for (n=1;n<x;n++)
{
if (ct[n-1]>=rt[n]) //考虑当前一个进程完成而后一个进程还没有到达的情况
ct[n]=ct[n-1]+st[n];
else
ct[n]=rt[n]+st[n];
}
for (n=0;n<x;n++)
cyt[n]=ct[n]-rt[n];
}
void output(int x)
{
for (n=0;n<x;n++)
printf("name:%d\narrive time:%d\nserive:%d\nend time:%d\nturnaround time:%d\n",n+1,rt[n],st[n],ct[n],cyt[n]);
}
void main()
{
int swich;//选择使用算法
struct pro *head;
int c=1;//选择是否继续
for (;c==1;)
{
printf("please input the number of the processes:");
scanf("%d",&x);
printf("please choose method(RR:0 SPF:1 FCFS:2):");
scanf("%d",&swich);
if(swich==0)
RR(x);
else
if(swich==1)
{
head=creatList();
printf("SPF:\n");
run(head);
}
else
if(swich==2)
FCFS(x);
else
printf("input error,please input again:\n");
printf("continue:1，quit:0\nplease input:");
scanf("%d",&c);
}
printf("*************end***********\n");
}
六、在虚拟机上的具体操作
七、实验结果
RR:
SPF:
FCFS:
八、思考题
根据上面的观察结果，比较这两种算法各自的优缺点，根据结果再和其他的算法比较。
FCFS算法可以保证先到的进程先执行,直到进程结束,但是所有进程的平均周转时间长;
RR算法不会使一些较长时间一直等待,但是不一定能够减少平均等待时间和平均周转时间;
SPF算法使短进程优先执行,减少平均等待时间和平均周转时间,有利用短进程的执行,但是不利于长进程.
九、实验总结
通过实验了解了FCFS、SPF、RR算法的具体实现过程，通过实验结果了解各个算法的优缺点，深入学习，由此可以在以后选择更优更合适的算法实现其他内容。