操作系统——处理机调度算法

实验目的：

1.理解三级调度；

2.掌握作业调度、进程调度算法的基本思想；

3.掌握最早截止时间优先和最低松弛度优先实时调度算法

实验器材：

VSCode

实验内容：

1.编程实现先来先服务、短作业/进程优先、优先数和最高响应比优先、时间片轮转调度算法；

2.编程实现实时调度算法（二选一）：最早截止时间优先和最低松弛度优先

实验步骤：

1.先来先服务：

#include?<stdio.h>

#include?<stdlib.h>

typedef?struct?{

? ? int?pid;?? ? ? ? ?// 进程 ID

? ? int?arrival_time;??// 到达时间

? ? int?burst_time;?? ?// 执行时间

} Process;

void?fcfs_schedule(Process?*processes, int?num_processes) {

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].arrival_time?<=?processes[i].burst_time) {

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, processes[i].arrival_time, processes[i].arrival_time?+?processes[i].burst_time);

? ? ? ? processes[i].arrival_time?+=?processes[i].burst_time;

? ? ? ? i++;

? ? }

}

int?main() {

? ? Process?processes[] =?{

? ? ? ? {1, 0, 30},

? ? ? ? {2, 5, 8},

? ? ? ? {3, 10, 3},

? ? ? ? {4, 15, 5}

? ? };

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? fcfs_schedule(processes, num_processes);

? ? return?0;

}

2.短作业/进程优先：

#include?<iostream>

#include?<string.h>

#include?<iomanip>

struct?job

{

? ? char?name[10];?? ? ?//作业的名字

? ? int?starttime;?? ? ?//作业到达系统时间

? ? int?needtime;?? ? ? //作业服务时间

? ? int?runtime;?? ? ? ?//作业周转时间

? ? int?endtime;?? ? ? ?//作业结束时间

? ? int?flag=0;?? ? ? ? ? //作业完成标志

? ? char?state='W';?? ? ? ? //作业状态，一开始都默认为就绪

? ? double?dqzz_time;?? ?//带权周转时间

};

void?sjf(struct?job?jobs[50],int?n){

? ? int?i=0,j=0,k,temp,count=0,min_needtime,min_starttime,t_time,flag1;

? ? char?t_name[10];

? ? int?nowtime=0;

? ? for(i=0;i<n;i++)?//按作业到达系统时间进行排序，最早到达的排在最前面

? ? {

? ? ? ? min_needtime=jobs[i].needtime;

? ? ? ? temp=i;

? ? ? ? for(j=i;j<n;j++)?//按作业到达系统时间进行排序，最早到达的排在最前面

? ? ? ? {

? ? ? ? ? ? if(jobs[j].needtime<min_needtime)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? temp=j;

? ? ? ? ? ? ? ? min_needtime=jobs[j].needtime;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if(temp!=i)

? ? ? ? {

? ? ? ? ? ? jobs[40]=jobs[temp];

? ? ? ? ? ? for(k=temp-1;k>=i;k--)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? jobs[k+1]=jobs[k];

? ? ? ? ? ? }

? ? ? ? ? ? jobs[i]=jobs[40];

? ? ? ? }

? ? }

? ? while(count<n){

? ? ? ? temp=1000;

? ? ? ? flag1=0;

? ? ? ? min_needtime=1000;

? ? ? ? min_starttime=1000;

? ? ? ? for(i=0;i<n;i++){

? ? ? ? ? ? if(jobs[i].flag==0){

? ? ? ? ? ? ? ? if(jobs[i].starttime<=nowtime)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? flag1=1;

? ? ? ? ? ? ? ? ? ? if(jobs[i].needtime<min_needtime){

? ? ? ? ? ? ? ? ? ? ? ? min_needtime=jobs[i].needtime;

? ? ? ? ? ? ? ? ? ? ? ? temp=i;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if(flag1==0)

? ? ? ? {

? ? ? ? ? ? for(i=0;i<n;i++){

? ? ? ? ? ? ? ? if(jobs[i].flag==0){

? ? ? ? ? ? ? ? ? ? if(jobs[i].starttime<min_starttime){

? ? ? ? ? ? ? ? ? ? ? ? min_starttime=jobs[i].starttime;

? ? ? ? ? ? ? ? ? ? ? ? temp=i;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? nowtime=jobs[temp].starttime+jobs[temp].needtime;

? ? ? ? ? ? jobs[temp].endtime=nowtime;

? ? ? ? ? ? jobs[temp].flag=1;

? ? ? ? ? ? jobs[temp].runtime=jobs[temp].endtime-jobs[temp].starttime;

? ? ? ? ? ? jobs[temp].dqzz_time=float(jobs[temp].runtime)/jobs[temp].needtime;

? ? ? ? ? ? count++;

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? nowtime+=jobs[temp].needtime;

? ? ? ? ? ? jobs[temp].endtime=nowtime;

? ? ? ? ? ? jobs[temp].flag=1;

? ? ? ? ? ? jobs[temp].runtime=jobs[temp].endtime-jobs[temp].starttime;

? ? ? ? ? ? jobs[temp].dqzz_time=float(jobs[temp].runtime)/jobs[temp].needtime;

? ? ? ? ? ? count++;

? ? ? ? }

? ? }

}

void?print(struct?job?jobs[50],int?n)

{

? ? int?i;

? ? double?avertime;

? ? double?dqzz_avertime;

? ? int?sum_runtime=0;

? ? double??sum_time=0.00;

? ? printf("作业名 ?到达时间 运行时间 完成时间 周转时间 带权周转时间\\n");

? ? for(i=0;i<n;i++)

? ? {

? ? printf("%s?? ? ? %2d?? ? ? ?%2d?? ? ? %2d?? ? ? ?%2d?? ? ? ?%.2f\\n",jobs[i].name,jobs[i].starttime,jobs[i].needtime,jobs[i].endtime,jobs[i].runtime,jobs[i].dqzz_time);

? ? sum_runtime=sum_runtime+jobs[i].runtime;

? ? sum_time=sum_time+jobs[i].dqzz_time;

? ? }

? ? avertime=sum_runtime*1.0/n;

? ? dqzz_avertime=sum_time*1.000/n;

? ? printf("平均周转时间:%.2f?\\n",avertime);

? ? printf("平均带权周转时间:%.3f?\\n",dqzz_avertime);

? ? printf("\\n");

}

int?main()

{

? ? struct?job?jobs[50];

? ? int?n,i;?//n个作业

? ? printf("请输入作业个数:");

? ? scanf("%d",&n);

? ? printf("请输入各作业的信息(格式：作业名 到达时间 服务时间)：\\n");

? ? for(i=0;i<n;i++)

? ? {

? ? ? ? scanf("%s",jobs[i].name);?//作业名

? ? ? ? scanf("%d",&jobs[i].starttime);//到达时间

? ? ? ? scanf("%d",&jobs[i].needtime);//运行（服务时间）时间

? ? }

? ? printf("\\n");

? ? sjf(jobs,n);

? ? printf("先来先服务(FCFS)调度算法运行结果：\\n");

? ? print(jobs,n);

}

3.优先数和最高响应比优先：

#include?<iostream>?

#include?<iomanip>?//格式化输出

using?namespace?std;

//最大进程数

#define?MAXSIZE_N?10

//定义数据结构

struct?PCB{

? ? ? ? int?number;//进程代号

? ? ? ? int?arrive_time;//到达时间

? ? ? ? int?serve_time;//服务时间

? ? ? ? int?priority;//优先级

? ? ? ? int?finish_time=0;//记录结束运行时刻

? ? };

? ?

int?main(){

? ? int?n;//进程总数

? ? PCB?p_list[MAXSIZE_N];//PCB数组

? ?

? ? cout<<"======非抢占的优先级调度算法======\n";

? ?

? ? //读入进程信息

? ? cout<<"请输入进程总数："?;

? ? cin>>n;

? ? for(int?i=0;i<n;i++){

? ? ? ? cout<<"\n"<<i+1<<":\n请依次输入进程的信息\n请输入进程代号number = ";

? ? ? ? cin>>p_list[i].number;

? ? ? ? cout<<"请输入到达时间arrive_time = "?;

? ? ? ? cin>>?p_list[i].arrive_time;

? ? ? ? cout<<"请输入服务时间serve_time = "?;

? ? ? ? cin>>?p_list[i].serve_time;

? ? ? ? cout<<"请输入优先级priority = "?;

? ? ? ? cin>>?p_list[i].priority;

? ? }

? ?

? ? //找到进程执行的序列 work_list

? ? int?work_list[n];

? ? for(int?i=0;i<n;i++){//元素代表执行的进程在p_list中的下标，下标代表执行顺序

? ? ? ? work_list[i]=i;

? ? }

? ? int?temp=0;

? ? for(int?i=0;i<n;i++){//先按到达时间排序

? ? ? ? for(int?j=0;j<n-i-1;j++){

? ? ? ? ? ? if(p_list[j].arrive_time>p_list[j+1].arrive_time){

? ? ? ? ? ? ? ? temp=work_list[j];

? ? ? ? ? ? ? ? work_list[j]=work_list[j+1];

? ? ? ? ? ? ? ? work_list[j+1]=temp;

? ? ? ? ? ? }

? ? ? ? } ?

? ? }

? ?

? ? for(int?i=0;i<n;i++){//再按优先级排序

? ? ? ? for(int?j=0;j<n-i-1;j++){

? ? ? ? ? ? if(p_list[j].arrive_time==p_list[j+1].arrive_time&&p_list[j].priority<p_list[j+1].priority){

? ? ? ? ? ? ? ? temp=work_list[j];

? ? ? ? ? ? ? ? work_list[j]=work_list[j+1];

? ? ? ? ? ? ? ? work_list[j+1]=temp;

? ? ? ? ? ? }

? ? ? ? } ?

? ? }

? ? //执行进程

? ? int?time=p_list[work_list[0]].arrive_time;//记录运行的时刻

? ? cout<<"\n调度序号"<<setw(20)<<"运行的进程代号"<<setw(15)<<"优先级"<<setw(20)<<"开始运行的时刻"<<setw(15)<<"运行时间"<<setw(20)<<"结束运行时间";

? ? for(int?i=0;i<n;i++){//执行进程并输出

? ? ? ? cout<<"\n?? "<<i+1<<setw(17)<<p_list[work_list[i]].number<<setw(19)<<p_list[work_list[i]].priority<<setw(16)<<time<<setw(18)<<p_list[work_list[i]].serve_time<<setw(19);

? ? ? ? time=time+p_list[work_list[i]].serve_time;

? ? ? ? p_list[work_list[i]].finish_time=time;

? ? ? ? cout<<time;

? ? }

? ?

? ? //每个进程的周转时间

? ? cout<<"\n\n进程代号"<<setw(17)<<"完成时刻"<<setw(18)<<"周转时间"<<setw(20)<<"带权周转时间";

? ? float?work_time;//记录周转时间

? ? float?time_sum=0;//记录总周转时间

? ? float?weight_time;?//记录带权周转时间

? ? float?weight_sum=0;// 记录总带权周转时间

? ?

? ? for(int?i=0;i<n;i++){

? ? ? ?

? ? ? ? work_time=p_list[i].finish_time-p_list[i].arrive_time;

? ? ? ? time_sum+=work_time;

? ? ? ? weight_time=work_time/(float)p_list[i].serve_time;

? ? ? ? weight_sum+=weight_time;

? ? ? ?

? ? ? ? cout<<"\n?? "<<p_list[i].number<<setw(17)<<p_list[i].finish_time<<setw(19)<<work_time<<setw(19)<<weight_time;

? ? }

? ?

? ? //平均（带权）周转时间

? ? cout<<"\n\n平均周转时间:"<<time_sum/n;

? ? cout<<"\n平均带权周转时间"<<weight_sum/n; ? ?

4.RR算法：

#include?<stdio.h>??

#include?<stdlib.h>

typedef?struct?{ ? ?

? ? int?pid;?? ? ? ? ?// 进程 ID ? ?

? ? int?arrival_time;??// 到达时间 ? ?

? ? int?burst_time;?? ?// 执行时间 ? ?

? ? int?remaining_time;?// 剩余执行时间 ?

} Process;

void?round_robin_schedule(Process?*processes, int?num_processes) { ? ?

? ? int?current_time?=?0; ?

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].remaining_time?>?0) { ?

? ? ? ? int?min_remaining_time?=?processes[i].remaining_time; ?

? ? ? ? int?min_index?=?i;

? ? ? ? for?(int?j?=?i?+?1; j?<?num_processes; j++) { ?

? ? ? ? ? ? if?(processes[j].remaining_time?>?0?&&?processes[j].remaining_time?<?min_remaining_time) { ?

? ? ? ? ? ? ? ? min_remaining_time?=?processes[j].remaining_time; ?

? ? ? ? ? ? ? ? min_index?=?j; ?

? ? ? ? ? ? } ?

? ? ? ? }

? ? ? ? if?(min_index?!=?i) { ?

? ? ? ? ? ? Process?temp?=?processes[i]; ?

? ? ? ? ? ? processes[i] =?processes[min_index]; ?

? ? ? ? ? ? processes[min_index] =?temp; ?

? ? ? ? }

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, current_time, current_time?+?processes[i].remaining_time); ?

? ? ? ? processes[i].remaining_time?=?0; ?

? ? ? ? i++; ?

? ? ? ? current_time?+=?processes[i?-?1].remaining_time; ?

? ? } ?

}

int?main() { ? ?

? ? Process?processes[] =?{ ? ?

? ? ? ? {1, 0, 20, 10}, ? ?

? ? ? ? {2, 5, 10, 5}, ? ?

? ? ? ? {3, 10, 30, 20}, ? ?

? ? ? ? {4, 15, 25, 15} ? ?

? ? }; ? ?

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? round_robin_schedule(processes, num_processes);

? ? return?0; ? ?

}

5.最早截止时间优先算法：

#include?<stdio.h>??

#include?<stdlib.h>

typedef?struct?{ ?

? ? int?pid;?? ? ? ? ?// 进程 ID ?

? ? int?arrival_time;??// 到达时间 ?

? ? int?burst_time;?? ?// 执行时间 ?

? ? int?remaining_time;?// 剩余执行时间 ?

? ? int?deadline;?? ? ?// 截止时间 ?

} Process;

void?edf_schedule(Process?*processes, int?num_processes) { ?

? ? int?current_time?=?0; ?

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].remaining_time?>?0) { ?

? ? ? ? int?min_deadline?=?processes[i].deadline; ?

? ? ? ? int?min_index?=?i;

? ? ? ? for?(int?j?=?i?+?1; j?<?num_processes; j++) { ?

? ? ? ? ? ? if?(processes[j].deadline?<=?min_deadline?&&?processes[j].remaining_time?>?0) { ?

? ? ? ? ? ? ? ? min_deadline?=?processes[j].deadline; ?

? ? ? ? ? ? ? ? min_index?=?j; ?

? ? ? ? ? ? } ?

? ? ? ? }

? ? ? ? if?(min_index?!=?i) { ?

? ? ? ? ? ? Process?temp?=?processes[i]; ?

? ? ? ? ? ? processes[i] =?processes[min_index]; ?

? ? ? ? ? ? processes[min_index] =?temp; ?

? ? ? ? }

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, current_time, current_time?+?processes[i].remaining_time); ?

? ? ? ? processes[i].remaining_time?=?0; ?

? ? ? ? i++; ?

? ? ? ? current_time?+=?processes[i?-?1].remaining_time; ?

? ? } ?

}

int?main() { ?

? ? Process?processes[] =?{ ?

? ? ? ? {1, 0, 20, 10, 30}, ?

? ? ? ? {2, 5, 10, 5, 40}, ?

? ? ? ? {3, 10, 30, 20, 50}, ?

? ? ? ? {4, 15, 25, 15, 60} ?

? ? }; ?

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? edf_schedule(processes, num_processes);

? ? return?0; ?

}

实验结果（附数据和图表）：

1.先来先服务：

2.短作业优先：

3.高响应比：

4.时间轮转片：

5.最早截至算法：

实验结果分析及结论：

1. 先来先服务算法：依据进程进入就绪状态的先后顺序进行调度，FCFS 算法简单易实现，但可能导致较长作业阻塞较短作业，导致平均等待时间较长，资源利用率降低。
2. 最短进程优先算法：根据进程执行剩余时间的长短进行调度，优先选择剩余时间最短的进程，法能有效减少平均等待时间和平均响应时间，提高系统吞吐量，但可能导致较长作业无法得到执行，且容易产生饥饿现象。
3. 优先级调度算法：根据进程优先级进行调度，优先级高的进程优先执行，确保高优先级进程优先执行，满足实时性要求，但低优先级进程可能长时间得不到执行，导致资源利用率降低。
4. 时间片轮转算法：为每个进程分配一个固定的时间片，进程按照顺序轮流执行，实现简单，能保证公平性，但可能导致较长的平均响应时间，且容易产生饥饿现象。

实验心得体会和建议：

通过实验更加深入体会到了这些算法的各自特点，也有助于我更好地理解相应的算法。

在实验过程中，我意识到处理机调度算法并非绝对完美的，总有改进的空间。因此，在未来的学习中，我将不断探索更优秀的调度算法，以期在实际应用中取得更好的效果。

总之，通过本次实验，我对处理机调度算法有了更加深入的认识。在实现和优化算法的过程中，我体会到了理论与实践相结合的重要性。在今后的学习中，我将不断积累经验，探索更优秀的调度算法，为计算机系统的高效运行贡献力量。

实验目的：

1.理解三级调度；

2.掌握作业调度、进程调度算法的基本思想；

3.掌握最早截止时间优先和最低松弛度优先实时调度算法

实验器材：

VSCode

实验内容：

1.编程实现先来先服务、短作业/进程优先、优先数和最高响应比优先、时间片轮转调度算法；

2.编程实现实时调度算法（二选一）：最早截止时间优先和最低松弛度优先

实验步骤：

1.先来先服务：

#include?<stdio.h>

#include?<stdlib.h>

typedef?struct?{

? ? int?pid;?? ? ? ? ?// 进程 ID

? ? int?arrival_time;??// 到达时间

? ? int?burst_time;?? ?// 执行时间

} Process;

void?fcfs_schedule(Process?*processes, int?num_processes) {

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].arrival_time?<=?processes[i].burst_time) {

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, processes[i].arrival_time, processes[i].arrival_time?+?processes[i].burst_time);

? ? ? ? processes[i].arrival_time?+=?processes[i].burst_time;

? ? ? ? i++;

? ? }

}

int?main() {

? ? Process?processes[] =?{

? ? ? ? {1, 0, 30},

? ? ? ? {2, 5, 8},

? ? ? ? {3, 10, 3},

? ? ? ? {4, 15, 5}

? ? };

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? fcfs_schedule(processes, num_processes);

? ? return?0;

}

2.短作业/进程优先：

#include?<iostream>

#include?<string.h>

#include?<iomanip>

struct?job

{

? ? char?name[10];?? ? ?//作业的名字

? ? int?starttime;?? ? ?//作业到达系统时间

? ? int?needtime;?? ? ? //作业服务时间

? ? int?runtime;?? ? ? ?//作业周转时间

? ? int?endtime;?? ? ? ?//作业结束时间

? ? int?flag=0;?? ? ? ? ? //作业完成标志

? ? char?state='W';?? ? ? ? //作业状态，一开始都默认为就绪

? ? double?dqzz_time;?? ?//带权周转时间

};

void?sjf(struct?job?jobs[50],int?n){

? ? int?i=0,j=0,k,temp,count=0,min_needtime,min_starttime,t_time,flag1;

? ? char?t_name[10];

? ? int?nowtime=0;

? ? for(i=0;i<n;i++)?//按作业到达系统时间进行排序，最早到达的排在最前面

? ? {

? ? ? ? min_needtime=jobs[i].needtime;

? ? ? ? temp=i;

? ? ? ? for(j=i;j<n;j++)?//按作业到达系统时间进行排序，最早到达的排在最前面

? ? ? ? {

? ? ? ? ? ? if(jobs[j].needtime<min_needtime)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? temp=j;

? ? ? ? ? ? ? ? min_needtime=jobs[j].needtime;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if(temp!=i)

? ? ? ? {

? ? ? ? ? ? jobs[40]=jobs[temp];

? ? ? ? ? ? for(k=temp-1;k>=i;k--)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? jobs[k+1]=jobs[k];

? ? ? ? ? ? }

? ? ? ? ? ? jobs[i]=jobs[40];

? ? ? ? }

? ? }

? ? while(count<n){

? ? ? ? temp=1000;

? ? ? ? flag1=0;

? ? ? ? min_needtime=1000;

? ? ? ? min_starttime=1000;

? ? ? ? for(i=0;i<n;i++){

? ? ? ? ? ? if(jobs[i].flag==0){

? ? ? ? ? ? ? ? if(jobs[i].starttime<=nowtime)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? flag1=1;

? ? ? ? ? ? ? ? ? ? if(jobs[i].needtime<min_needtime){

? ? ? ? ? ? ? ? ? ? ? ? min_needtime=jobs[i].needtime;

? ? ? ? ? ? ? ? ? ? ? ? temp=i;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if(flag1==0)

? ? ? ? {

? ? ? ? ? ? for(i=0;i<n;i++){

? ? ? ? ? ? ? ? if(jobs[i].flag==0){

? ? ? ? ? ? ? ? ? ? if(jobs[i].starttime<min_starttime){

? ? ? ? ? ? ? ? ? ? ? ? min_starttime=jobs[i].starttime;

? ? ? ? ? ? ? ? ? ? ? ? temp=i;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? nowtime=jobs[temp].starttime+jobs[temp].needtime;

? ? ? ? ? ? jobs[temp].endtime=nowtime;

? ? ? ? ? ? jobs[temp].flag=1;

? ? ? ? ? ? jobs[temp].runtime=jobs[temp].endtime-jobs[temp].starttime;

? ? ? ? ? ? jobs[temp].dqzz_time=float(jobs[temp].runtime)/jobs[temp].needtime;

? ? ? ? ? ? count++;

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? nowtime+=jobs[temp].needtime;

? ? ? ? ? ? jobs[temp].endtime=nowtime;

? ? ? ? ? ? jobs[temp].flag=1;

? ? ? ? ? ? jobs[temp].runtime=jobs[temp].endtime-jobs[temp].starttime;

? ? ? ? ? ? jobs[temp].dqzz_time=float(jobs[temp].runtime)/jobs[temp].needtime;

? ? ? ? ? ? count++;

? ? ? ? }

? ? }

}

void?print(struct?job?jobs[50],int?n)

{

? ? int?i;

? ? double?avertime;

? ? double?dqzz_avertime;

? ? int?sum_runtime=0;

? ? double??sum_time=0.00;

? ? printf("作业名 ?到达时间 运行时间 完成时间 周转时间 带权周转时间\\n");

? ? for(i=0;i<n;i++)

? ? {

? ? printf("%s?? ? ? %2d?? ? ? ?%2d?? ? ? %2d?? ? ? ?%2d?? ? ? ?%.2f\\n",jobs[i].name,jobs[i].starttime,jobs[i].needtime,jobs[i].endtime,jobs[i].runtime,jobs[i].dqzz_time);

? ? sum_runtime=sum_runtime+jobs[i].runtime;

? ? sum_time=sum_time+jobs[i].dqzz_time;

? ? }

? ? avertime=sum_runtime*1.0/n;

? ? dqzz_avertime=sum_time*1.000/n;

? ? printf("平均周转时间:%.2f?\\n",avertime);

? ? printf("平均带权周转时间:%.3f?\\n",dqzz_avertime);

? ? printf("\\n");

}

int?main()

{

? ? struct?job?jobs[50];

? ? int?n,i;?//n个作业

? ? printf("请输入作业个数:");

? ? scanf("%d",&n);

? ? printf("请输入各作业的信息(格式：作业名 到达时间 服务时间)：\\n");

? ? for(i=0;i<n;i++)

? ? {

? ? ? ? scanf("%s",jobs[i].name);?//作业名

? ? ? ? scanf("%d",&jobs[i].starttime);//到达时间

? ? ? ? scanf("%d",&jobs[i].needtime);//运行（服务时间）时间

? ? }

? ? printf("\\n");

? ? sjf(jobs,n);

? ? printf("先来先服务(FCFS)调度算法运行结果：\\n");

? ? print(jobs,n);

}

3.优先数和最高响应比优先：

#include?<iostream>?

#include?<iomanip>?//格式化输出

using?namespace?std;

//最大进程数

#define?MAXSIZE_N?10

//定义数据结构

struct?PCB{

? ? ? ? int?number;//进程代号

? ? ? ? int?arrive_time;//到达时间

? ? ? ? int?serve_time;//服务时间

? ? ? ? int?priority;//优先级

? ? ? ? int?finish_time=0;//记录结束运行时刻

? ? };

? ?

int?main(){

? ? int?n;//进程总数

? ? PCB?p_list[MAXSIZE_N];//PCB数组

? ?

? ? cout<<"======非抢占的优先级调度算法======\n";

? ?

? ? //读入进程信息

? ? cout<<"请输入进程总数："?;

? ? cin>>n;

? ? for(int?i=0;i<n;i++){

? ? ? ? cout<<"\n"<<i+1<<":\n请依次输入进程的信息\n请输入进程代号number = ";

? ? ? ? cin>>p_list[i].number;

? ? ? ? cout<<"请输入到达时间arrive_time = "?;

? ? ? ? cin>>?p_list[i].arrive_time;

? ? ? ? cout<<"请输入服务时间serve_time = "?;

? ? ? ? cin>>?p_list[i].serve_time;

? ? ? ? cout<<"请输入优先级priority = "?;

? ? ? ? cin>>?p_list[i].priority;

? ? }

? ?

? ? //找到进程执行的序列 work_list

? ? int?work_list[n];

? ? for(int?i=0;i<n;i++){//元素代表执行的进程在p_list中的下标，下标代表执行顺序

? ? ? ? work_list[i]=i;

? ? }

? ? int?temp=0;

? ? for(int?i=0;i<n;i++){//先按到达时间排序

? ? ? ? for(int?j=0;j<n-i-1;j++){

? ? ? ? ? ? if(p_list[j].arrive_time>p_list[j+1].arrive_time){

? ? ? ? ? ? ? ? temp=work_list[j];

? ? ? ? ? ? ? ? work_list[j]=work_list[j+1];

? ? ? ? ? ? ? ? work_list[j+1]=temp;

? ? ? ? ? ? }

? ? ? ? } ?

? ? }

? ?

? ? for(int?i=0;i<n;i++){//再按优先级排序

? ? ? ? for(int?j=0;j<n-i-1;j++){

? ? ? ? ? ? if(p_list[j].arrive_time==p_list[j+1].arrive_time&&p_list[j].priority<p_list[j+1].priority){

? ? ? ? ? ? ? ? temp=work_list[j];

? ? ? ? ? ? ? ? work_list[j]=work_list[j+1];

? ? ? ? ? ? ? ? work_list[j+1]=temp;

? ? ? ? ? ? }

? ? ? ? } ?

? ? }

? ? //执行进程

? ? int?time=p_list[work_list[0]].arrive_time;//记录运行的时刻

? ? cout<<"\n调度序号"<<setw(20)<<"运行的进程代号"<<setw(15)<<"优先级"<<setw(20)<<"开始运行的时刻"<<setw(15)<<"运行时间"<<setw(20)<<"结束运行时间";

? ? for(int?i=0;i<n;i++){//执行进程并输出

? ? ? ? cout<<"\n?? "<<i+1<<setw(17)<<p_list[work_list[i]].number<<setw(19)<<p_list[work_list[i]].priority<<setw(16)<<time<<setw(18)<<p_list[work_list[i]].serve_time<<setw(19);

? ? ? ? time=time+p_list[work_list[i]].serve_time;

? ? ? ? p_list[work_list[i]].finish_time=time;

? ? ? ? cout<<time;

? ? }

? ?

? ? //每个进程的周转时间

? ? cout<<"\n\n进程代号"<<setw(17)<<"完成时刻"<<setw(18)<<"周转时间"<<setw(20)<<"带权周转时间";

? ? float?work_time;//记录周转时间

? ? float?time_sum=0;//记录总周转时间

? ? float?weight_time;?//记录带权周转时间

? ? float?weight_sum=0;// 记录总带权周转时间

? ?

? ? for(int?i=0;i<n;i++){

? ? ? ?

? ? ? ? work_time=p_list[i].finish_time-p_list[i].arrive_time;

? ? ? ? time_sum+=work_time;

? ? ? ? weight_time=work_time/(float)p_list[i].serve_time;

? ? ? ? weight_sum+=weight_time;

? ? ? ?

? ? ? ? cout<<"\n?? "<<p_list[i].number<<setw(17)<<p_list[i].finish_time<<setw(19)<<work_time<<setw(19)<<weight_time;

? ? }

? ?

? ? //平均（带权）周转时间

? ? cout<<"\n\n平均周转时间:"<<time_sum/n;

? ? cout<<"\n平均带权周转时间"<<weight_sum/n; ? ?

4.RR算法：

#include?<stdio.h>??

#include?<stdlib.h>

typedef?struct?{ ? ?

? ? int?pid;?? ? ? ? ?// 进程 ID ? ?

? ? int?arrival_time;??// 到达时间 ? ?

? ? int?burst_time;?? ?// 执行时间 ? ?

? ? int?remaining_time;?// 剩余执行时间 ?

} Process;

void?round_robin_schedule(Process?*processes, int?num_processes) { ? ?

? ? int?current_time?=?0; ?

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].remaining_time?>?0) { ?

? ? ? ? int?min_remaining_time?=?processes[i].remaining_time; ?

? ? ? ? int?min_index?=?i;

? ? ? ? for?(int?j?=?i?+?1; j?<?num_processes; j++) { ?

? ? ? ? ? ? if?(processes[j].remaining_time?>?0?&&?processes[j].remaining_time?<?min_remaining_time) { ?

? ? ? ? ? ? ? ? min_remaining_time?=?processes[j].remaining_time; ?

? ? ? ? ? ? ? ? min_index?=?j; ?

? ? ? ? ? ? } ?

? ? ? ? }

? ? ? ? if?(min_index?!=?i) { ?

? ? ? ? ? ? Process?temp?=?processes[i]; ?

? ? ? ? ? ? processes[i] =?processes[min_index]; ?

? ? ? ? ? ? processes[min_index] =?temp; ?

? ? ? ? }

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, current_time, current_time?+?processes[i].remaining_time); ?

? ? ? ? processes[i].remaining_time?=?0; ?

? ? ? ? i++; ?

? ? ? ? current_time?+=?processes[i?-?1].remaining_time; ?

? ? } ?

}

int?main() { ? ?

? ? Process?processes[] =?{ ? ?

? ? ? ? {1, 0, 20, 10}, ? ?

? ? ? ? {2, 5, 10, 5}, ? ?

? ? ? ? {3, 10, 30, 20}, ? ?

? ? ? ? {4, 15, 25, 15} ? ?

? ? }; ? ?

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? round_robin_schedule(processes, num_processes);

? ? return?0; ? ?

}

5.最早截止时间优先算法：

#include?<stdio.h>??

#include?<stdlib.h>

typedef?struct?{ ?

? ? int?pid;?? ? ? ? ?// 进程 ID ?

? ? int?arrival_time;??// 到达时间 ?

? ? int?burst_time;?? ?// 执行时间 ?

? ? int?remaining_time;?// 剩余执行时间 ?

? ? int?deadline;?? ? ?// 截止时间 ?

} Process;

void?edf_schedule(Process?*processes, int?num_processes) { ?

? ? int?current_time?=?0; ?

? ? int?i?=?0;

? ? while?(i?<?num_processes?||?processes[i].remaining_time?>?0) { ?

? ? ? ? int?min_deadline?=?processes[i].deadline; ?

? ? ? ? int?min_index?=?i;

? ? ? ? for?(int?j?=?i?+?1; j?<?num_processes; j++) { ?

? ? ? ? ? ? if?(processes[j].deadline?<=?min_deadline?&&?processes[j].remaining_time?>?0) { ?

? ? ? ? ? ? ? ? min_deadline?=?processes[j].deadline; ?

? ? ? ? ? ? ? ? min_index?=?j; ?

? ? ? ? ? ? } ?

? ? ? ? }

? ? ? ? if?(min_index?!=?i) { ?

? ? ? ? ? ? Process?temp?=?processes[i]; ?

? ? ? ? ? ? processes[i] =?processes[min_index]; ?

? ? ? ? ? ? processes[min_index] =?temp; ?

? ? ? ? }

? ? ? ? printf("Process %d?starts at time %d?and ends at time %d\n", processes[i].pid, current_time, current_time?+?processes[i].remaining_time); ?

? ? ? ? processes[i].remaining_time?=?0; ?

? ? ? ? i++; ?

? ? ? ? current_time?+=?processes[i?-?1].remaining_time; ?

? ? } ?

}

int?main() { ?

? ? Process?processes[] =?{ ?

? ? ? ? {1, 0, 20, 10, 30}, ?

? ? ? ? {2, 5, 10, 5, 40}, ?

? ? ? ? {3, 10, 30, 20, 50}, ?

? ? ? ? {4, 15, 25, 15, 60} ?

? ? }; ?

? ? int?num_processes?=?sizeof(processes) /?sizeof(processes[0]);

? ? edf_schedule(processes, num_processes);

? ? return?0; ?

}

实验结果（附数据和图表）：

1.先来先服务：

2.短作业优先：

3.高响应比：

4.时间轮转片：

5.最早截至算法：

实验结果分析及结论：

1. 先来先服务算法：依据进程进入就绪状态的先后顺序进行调度，FCFS 算法简单易实现，但可能导致较长作业阻塞较短作业，导致平均等待时间较长，资源利用率降低。
2. 最短进程优先算法：根据进程执行剩余时间的长短进行调度，优先选择剩余时间最短的进程，法能有效减少平均等待时间和平均响应时间，提高系统吞吐量，但可能导致较长作业无法得到执行，且容易产生饥饿现象。
3. 优先级调度算法：根据进程优先级进行调度，优先级高的进程优先执行，确保高优先级进程优先执行，满足实时性要求，但低优先级进程可能长时间得不到执行，导致资源利用率降低。
4. 时间片轮转算法：为每个进程分配一个固定的时间片，进程按照顺序轮流执行，实现简单，能保证公平性，但可能导致较长的平均响应时间，且容易产生饥饿现象。

实验心得体会和建议：

通过实验更加深入体会到了这些算法的各自特点，也有助于我更好地理解相应的算法。

在实验过程中，我意识到处理机调度算法并非绝对完美的，总有改进的空间。因此，在未来的学习中，我将不断探索更优秀的调度算法，以期在实际应用中取得更好的效果。

总之，通过本次实验，我对处理机调度算法有了更加深入的认识。在实现和优化算法的过程中，我体会到了理论与实践相结合的重要性。在今后的学习中，我将不断积累经验，探索更优秀的调度算法，为计算机系统的高效运行贡献力量。