实验三：作业调度 作业调度算法模拟 谢世娜：394202453@qq.com.

Presentation on theme: "实验三：作业调度 作业调度算法模拟 谢世娜：394202453@qq.com."— Presentation transcript:

1 实验三：作业调度 作业调度算法模拟

2 提纲 实验目的 实验内容 实验算法 实验示例

3 提纲 实验目的 实验内容 实验算法 实验示例

4 实验目的 理解操作系统中作业调度的概念和调度算法； 了解操作系统中程序，作业，进程的区别与联系；
理解在操作系统中作业是如何被调度的，如何协调和控制各个作业对CPU的使用； 提高动手能力；

5 提纲 实验目的 实验内容 实验算法 实验示例

6 实验内容 作业调度 作业调度又称高级调度，不涉及处理机的分配，主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个（或多个）作业调入主存，为其分配内存、I/O设备等必要的资源，并建立相应的进程，安排在就绪队列上，以使进程获得竞争处理机的权利。

7 实验内容 调度队列模型

8 实验内容 编写并调试作业调度模拟程序； 实现三种作业调度算法，短作业优先（SJF），高响应比优先（HRRF），时间片轮转法（RR）；
对每种算法要求打印平均周转时间、平均带权周转时间、平均等待时间； 每次作业切换时打印作业相关信息（提示开始运行，结束运行\暂停运行；一个作业完成打印其等待时间、周转时间、带权周转时间）。

9 提纲 实验目的 实验内容 实验算法 实验示例

10 实验算法 算法一：先来先服务（FCFS） 基本思想 特点 遵循先进入后备队列的作业，先进行调度的原则。 非抢占式算法 简单，易于编码实现
优先考虑作业的等待时间，没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求

11 实验算法 算法二：短作业优先（SJF） 基本思想
根据作业控制块中作业申请时指出的执行时间，选取执行时间最短的作业优先调度；可有抢占或非抢占方式。 短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。

12 实验算法 算法三：高响应比优先（HRRF） 初衷
FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。 响应比高者优先调度算法为这两种算法的折中，使长作业不会长时间等待，但每次调度前都要进行响应比计算。

13 实验算法 算法四：时间片轮转（RR） 基本思想 优点
系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片结束之后，将该进程加到就绪队列队尾；然后再把处理机分配给就绪队列中新的首进程。 优点 系统能在给定的时间内响应所有用户请求。

14 提纲 实验目的 实验内容 实验算法 实验示例

15 实验示例 作业信息结构 typedef struct node { int number; //作业号
int reach_time; //作业抵达时间 int need_time; //作业的执行时间 double excellent; //响应比 int start_time; //作业开始时间 int wait_time; //等待时间 int tr_time; //周转时间 double wtr_time; //带权周转时间 int run_time; //作业累计已执行时间 } job;

16 实验示例 使用的测试数据 使用读文件的形式读入测试数据 作业ID 到达时间 执行时间 1 700 10 2 800 50 3 810 5 4
815 30 830 25 6 835 35 7 845 15

17 实验示例 读文件 void read_jobdata()；//读取数据文件； 用到的函数有：
fopen(文件名,使用文件方式);//打开文件 fscanf(文件指针,格式字符串,输入列表);//格式化读入； fclose(文件指针);//关闭文件

18 实验示例 常用的打开文件方法： if((fp = fopen(fname, "r")) == NULL) {
printf("error, open file failed, please check filename:\n"); } else {…} fclose(fp);

19 实验示例 void FCFS() { int time = 0; //当前时间 printf("\nFCFS算法作业流\n"); while (cur_count > 0) { int loc = 0; if (time < jobs[loc].reach_time) time = jobs[loc].reach_time; jobs[loc].start_time = time; jobs[loc].wait_time = time - jobs[loc].reach_time; printf("time:%-4d job:%-4d 开始运行 等待时间：%-4d\n", time, jobs[loc].number, jobs[loc].wait_time); time += jobs[loc].need_time; jobs[loc].tr_time = time - jobs[loc].reach_time; jobs[loc].wtr_time = (double)jobs[loc].tr_time / jobs[loc].need_time; printf("time:%-4d job:%-4d 结束运行 周转时间；%-4d 服务时间：%-4d 带权周转时间：%-5.2f\n", time, jobs[loc].number, jobs[loc].tr_time, jobs[loc].need_time, jobs[loc].wtr_time); total_wtime += jobs[loc].wait_time; total_trtime += jobs[loc].tr_time; total_wtrtime += jobs[loc].wtr_time; remove_job(loc); } printf("\n平均等待时间：%.2f\n", total_wtime / count); printf("平均周转时间：%.2f\n", total_trtime / count); printf("平均带权周转时间：%.2f\n", total_wtrtime / count);

20 实验示例 FCFS

21 作业要求 实现短作业优先调度算法（SJF非抢占）； 实现高响应比调度算法（HRRF非抢占）；
对每种算法要求打印平均周转时间、平均带权周转时间、平均等待时间； 每次作业切换时打印作业相关信息（提示开始运行，结束运行\暂停运行；一个作业完成打印其等待时间、周转时间、带权周转时间）。 学号末2位模5所得结果+1为该生所需测试数据文件尾编号如：所得结果为3则测试数据为job3.txt ；

22 实验示例 定义队列 typedef struct { job job_queue[MAX_QUEUE_SIZE]; int head;
int tail; int size; } queue;

23 实验示例 初始化队列 void init_queue(queue *q) { q->head = 0; q->tail = 0;
q->size = 0; }

24 实验示例 判断队列是否为空/已满 int is_empty_queue(queue *q) {
return q->size == 0; } int is_full_queue(queue *q) return q->size == MAX_QUEUE_SIZE;

25 实验示例 其他基本队列操作 //进入队列 void enqueue(queue *q, job j){} //出队
job dequeue(queue *q){} //打印队列内容 void print_queue(queue *q){}

26 作业要求 根据以上提示信息实现时间片轮转调度算法（RR） 对每种算法要求打印平均周转时间、平均带权周转时间、平均等待时间；
每次作业切换时打印作业相关信息（提示开始运行，结束运行\暂停运行；一个作业完成打印其等待时间、周转时间、带权周转时间）。 学号末2位模5所得结果+1为该生所需测试数据文件尾编号如：所得结果为3则测试数据为job3.txt；

27 实验示例 RR