作业调度实验
一、实验目的
掌握周转时间、等待时间、平均周转时间等概念及其计算方法；
二、实验指导
常用的作业调度算法有先来先服务，短作业优先，高响应比优先，优先权高者优先算法，其思想分别如下：
算法一：先来先服务（FCFS）
- 基本思想
遵循先进入等待队列的作业，先进行调度的原则。
- 特点
简单，易于编码实现。
优先考虑作业的等待时间，没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求。
算法二：短作业优先（SJF）
- 基本思想
根据作业控制块中作业申请时指出的执行时间，选取执行时间最短的作业优先调度。
短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。
算法三：高响应比优先（HRRF）
- 基本思想
FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。
响应比高者优先调度算法为这两种算法的折中，使长作业不会长时间等待，但每次调度前都要进行响应比计算。
算法四：优先权高者优先（HPF）
- 基本思想
系统根据作业的优先权进行作业调度，每次选取优先权高的作业优先调度。作业的优先权通常用一个整数表示，也叫做优先数。优先数的大小与优先权的关系由系统或者用户来规定,本实验采用优先权值越小，优先权越高。
优先权高者优先调度算法综合考虑了作业执行时间和等待时间的长短、作业的缓急度、作业对外部设备的使用情况等因素。
算法五：时间片轮转（RR）
- 基本思想 系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片结束之后，将该进程加到就绪队列队尾；然后再把处理机分配给就绪队列中新的首进程。
- 优点
系统能在给定的时间内响应所有用户请求。
三、参考实现
实现先来先服务算法（测试数据如下），参考下列程序。
#include struct Job { int id; // 作业号 int reach_time; // 到达时间 int need_time; // 执行时间};#define N 7struct Job jobs[] = { {1, 700, 10}, {2, 800, 50}, {3, 815, 30}, {4, 820, 5}, {5, 830, 25}, {6, 835, 20}, {7, 845, 15}};int max(int x, int y) { return x < y ? y : x;}// First Come, First Servevoid FCFS() { int cur_time = 0; float total_round_time = 0; float total_weighted_time = 0; int i; for (i = 0; i < N; i++) { int start_time = max(cur_time, jobs[i].reach_time); int end_time = start_time + jobs[i].need_time; // 周转时间 float round_time = end_time - jobs[i].reach_time; // 带权周转时间 float weighted_time = round_time / jobs[i].need_time; printf("作业 %d: 周转时间 = %.0f, 带权周转时间 = %.2f \n", jobs[i].id, round_time, weighted_time); total_round_time += round_time; total_weighted_time += weighted_time; cur_time = end_time; } printf("\n平均周转时间 = %.2f, 平均带权周转时间 = %.2f \n", total_round_time / N, total_weighted_time / N);}int main() { FCFS();}手工计算先来先服务算法(FCFS)的平均周转时间和平均带权周转时间，验证与计算机的计算 结果是否一致。
实现短作业优先算法（测试数据如下），参考下列程序。
代码实现：
#include using namespace std;struct process{ char name[16];//名字 double come_time; //到达时间 double run_time;//运行时间 double finish_time;//完成时间 double circle_time;//周转时间 double weight_circletime;//带权周转时间 int finished;//程序是否被执行（0）为未被执行，反之已经执行}Process[1024];int n; // 输入进去n个进程//输入void Input(){ cin>>n; for(int i=0;i>Process[i].name; Process[i].finished = 0;//输入进去的程序都是未被执行的 } for(int i=0;i>Process[i].come_time; } for(int i=0;i>Process[i].run_time; }}//输出void Output(){ printf("作 业 名："); for(int i=0;i<n;i++){ cout<<Process[i].name; if(i<n-1){ printf(" "); } } printf("\n"); printf("到达时间："); for(int i=0;i<n;i++){ cout<<Process[i].come_time; if(i<n-1){ printf(" "); } } printf("\n"); printf("服务时间："); for(int i=0;i<n;i++){ cout<<Process[i].run_time; if(i<n-1){ printf(" "); } } printf("\n"); printf("完成时间："); for(int i=0;i<n;i++){ cout<<Process[i].finish_time; if(i<n-1){ printf(" "); } } printf("\n"); printf("周转时间："); for(int i=0;i<n;i++){ cout<<Process[i].circle_time; if(i<n-1){ printf(" "); } } printf("\n"); printf("带权周转时间："); for(int i=0;i<n;i++){ printf("%.2f",Process[i].weight_circletime); if(i < n-1) { printf(" "); } }}bool cmp(process p1,process p2){ //将到达的进程按照到达时间进行排序 return p1.come_time<p2.come_time;}int main(){ Input(); sort(Process,Process+n,cmp); int finished_count = 0; //记录已经完成的进程数 int unfinish_pos = 0; // 记录未完成的进程的位置 double now_time; while(finished_count<n){ if(now_time<Process[unfinish_pos].come_time){ // 对在上一个程序完成前到达的新的程序的到达时间更新给now_time now_time = Process[unfinish_pos].come_time; } double min_run_time = INT_MAX; // 作为中间量来比较最短运行时间（一开始赋给一个很大的值） int pos = 0; //用来记录下一个要运行的进程的位置 for(int i = unfinish_pos;(i = Process[i].come_time);i++){// //因为更新了时间，所以比较也适用于在最早到达的一堆作业中找运行时间最短的作业 if(Process[i].finished == 1) continue ; if(Process[i].run_time < min_run_time){ min_run_time = Process[i].run_time; pos = i; } } { // //因为更新现在时间肯定是大于或者等于最早到达时间，所以直接加上后来到达程序的运行时间 now_time += Process[pos].run_time; Process[pos].finish_time = now_time; Process[pos].circle_time = now_time - Process[pos].come_time; Process[pos].weight_circletime = Process[pos].circle_time / Process[pos].run_time; Process[pos].finished = 1; if(pos == unfinish_pos){ //如果pos的位置恰好定位在unfinish_pos处，则将unfinish_pos记录到下一个进程 unfinish_pos = pos + 1; } finished_count++; } } Output(); return 0;}
实验截图：
计算过程：
