操作系统实验 FCFS和短作业优先SJF调度算法模拟

1、 题 目 先来先服务FCFS和短作业优先SJF进程调度算法 姓 名： 学 号： 专 业： 学 院： 指导教师： 林若宁 二零一八 年 十一月一、实验目的模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法，以加深对进程的概念及进程调度算法的理解二、实验内容1. 短作业优先调度算法原理 短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它使它立即执

2、行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理  先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。三、程序设计1.概要设计程序包括主函数、FCFS算法函数、SJF算法函数、

3、输出函数； 主函数流程：输入文件中的数据显示各进程数据选择算法调用相应算法的函数输出结果2.算法流程SJF算法流程图：3.详细设计（1）定义一个结构体typedef struct PCB char job_id10; /作业ID float Arr_time; /到达时刻 float Fun_time; /估计运行时间 float Wait_time; /等待时间 float Start_time; /开始时刻 float Fin_time; /完成时刻 float Tur_time; /周转时间 float WTur_time; /带权周转时间 int Order; /优先标记li

4、st;（2）先来先服务算法函数void fcfs(list *p,int count) /先来先服务算法 list temp; /临时结构体变量 int i; int j; for(i = 1;i < count;i+) /按到达时刻直接插入排序 temp = pi; j = i-1; while(temp.Arr_time < pj.Arr_time && j >= 0) pj+1 = pj; -j; pj+1 = temp; for(i = 0;i < count;i+) /循环计算各个作业的时间值 if(i = 0) pi.Start_time =

5、 pi.Arr_time; else pi.Start_time = pi-1.Fin_time; /开始时刻=前一个作业的完成时刻 pi.Wait_time = pi.Start_time - pi.Arr_time; /等待=开始-到达 pi.Fin_time = pi.Start_time + pi.Fun_time; /完成=开始+运行 pi.Tur_time = pi.Fin_time - pi.Arr_time; /周转=完成-到达 pi.WTur_time = pi.Tur_time / pi.Fun_time; /带权周转=周转/运行 return;（3）最短作业优先函数voi

6、d sjf(list *p,int count) /最短作业优先算法（sjf） list item; /结构体变量 int i = 0; int j = 0; int k = 0; /最短运行时间作业的下标 int flag = 0; /优先级设置 float min = 0; /最短运行时间 float temp; /开始的时刻 temp = p0.Arr_time; /先求出最先到达作业的时刻 for(i = 0;i < count;i+) if(temp > pi.Arr_time) temp = pi.Arr_time; /保存最先到达的作业的时刻 k = i; /最先到达

7、的作业的下标，默认为p0 for(i = 0;i < count;i+) pk.Order = +flag; /设置优先级为1，最高优先级 pk.Start_time = temp; pk.Wait_time = temp - pk.Arr_time; /计算各个时间 pk.Fin_time = temp + pk.Fun_time; pk.Tur_time = pk.Fin_time - pk.Arr_time; pk.WTur_time = pk.Tur_time / pk.Fun_time; min = 100; temp = pk.Fin_time; /后一个作业的开始时刻是前一

8、个作业的完成时刻 for(j = 0;j < count;j+) if(pj.Order != 0 | temp - pj.Arr_time <= 0) /跳过不满足条件的（已设置优先级的 和 到达时刻要晚于前一个作业的完成时刻的） continue; if(min > pj.Fun_time) min = pj.Fun_time; k = j; /求出满足条件最短运行时间的作业的下标 for(i = 1;i < count;i+) /按优先级排序 item = pi; j = i-1; while(item.Order < pj.Order &&

9、 j >= 0) pj+1 = pj; -j; pj+1 = item; return;四、实验结果测试数据：进程名到达时间运行时间A04B13C25D44（1）先来先服务算法调试（2）最短作业优先算法调试五、实验小结FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。 CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。 I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。SJ(P)F调度算法也存在不容忽视的缺点：该算法对长作业不利，如作业C的周转时间

10、由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。#include "stdafx.h"#include<stdio.h>#define MAX 100typedef struc

11、t PCB char job_id10; /作业ID float Arr_time; /到达时刻 float Fun_time; /估计运行时间 float Wait_time; /等待时间 float Start_time; /开始时刻 float Fin_time; /完成时刻 float Tur_time; /周转时间 float WTur_time; /带权周转时间 int Order; /优先标记list;void fcfs(list *p,int count); void sjf(list *p,int count);void print(list *p,int count);vo

12、id avg(list *p,int count);void fcfs(list *p,int count) /先来先服务算法 list temp; /临时结构体变量 int i; int j; for(i = 1;i < count;i+) /按到达时刻直接插入排序 temp = pi; j = i-1; while(temp.Arr_time < pj.Arr_time && j >= 0) pj+1 = pj; -j; pj+1 = temp; for(i = 0;i < count;i+) /循环计算各个作业的时间值 if(i = 0) pi.S

13、tart_time = pi.Arr_time; else pi.Start_time = pi-1.Fin_time; /开始时刻=前一个作业的完成时刻 pi.Wait_time = pi.Start_time - pi.Arr_time; /等待=开始-到达 pi.Fin_time = pi.Start_time + pi.Fun_time; /完成=开始+运行 pi.Tur_time = pi.Fin_time - pi.Arr_time; /周转=完成-到达 pi.WTur_time = pi.Tur_time / pi.Fun_time; /带权周转=周转/运行 return;voi

14、d sjf(list *p,int count) /最短作业优先算法（sjf） list item; /结构体变量 int i = 0; int j = 0; int k = 0; /最短运行时间作业的下标 int flag = 0; /优先级设置 float min = 0; /最短运行时间 float temp; /开始的时刻 temp = p0.Arr_time; /先求出最先到达作业的时刻 for(i = 0;i < count;i+) if(temp > pi.Arr_time) temp = pi.Arr_time; /保存最先到达的作业的时刻 k = i; /最先到达

15、的作业的下标，默认为p0 for(i = 0;i < count;i+) pk.Order = +flag; /设置优先级为1，最高优先级 pk.Start_time = temp; pk.Wait_time = temp - pk.Arr_time; /计算各个时间 pk.Fin_time = temp + pk.Fun_time; pk.Tur_time = pk.Fin_time - pk.Arr_time; pk.WTur_time = pk.Tur_time / pk.Fun_time; min = 100; temp = pk.Fin_time; /后一个作业的开始时刻是前一

16、个作业的完成时刻 for(j = 0;j < count;j+) if(pj.Order != 0 | temp - pj.Arr_time <= 0) /跳过不满足条件的（已设置优先级的 和 到达时刻要晚于前一个作业的完成时刻的） continue; if(min > pj.Fun_time) min = pj.Fun_time; k = j; /求出满足条件最短运行时间的作业的下标 for(i = 1;i < count;i+) /按优先级排序 item = pi; j = i-1; while(item.Order < pj.Order &&

17、 j >= 0) pj+1 = pj; -j; pj+1 = item; return;void print(list *p,int count) /输出各个作业的详细信息 int i; printf("*n"); printf("IDt到达t运行t等待t开始t完成t周转t带权周转n"); for(i = 0;i < count;i+) printf("%st%.3ft%.3ft%.3ft%.3ft%.3ft%.3ft%.3fn",pi.job_id,pi.Arr_time,pi.Fun_time,pi.Wait_time

18、,pi.Start_time,pi.Fin_time,pi.Tur_time,pi.WTur_time); return;void avg(list *p,int count) float AvgTur1; /平均周转 float AvgTur2; /平均带权周转 float t1 = 0; float t2 = 0; int i; for(i = 0;i < count;i+) t1 += pi.Tur_time; /周转时间和 t2 += pi.WTur_time; /带权周转和 AvgTur1 = t1/count; AvgTur2 = t2/count; printf("n平均周转时间为：%ft平均带权周转时间为：%fn",AvgTur1,AvgTur2); printf("n*n"); return;int main() list stMAX; /最多可以一百个作业 int job_count = 0; /