操作系統(tǒng)實(shí)驗(yàn) FCFS和短作業(yè)優(yōu)先SJF調(diào)度算法模擬

1、 題 目 先來先服務(wù)FCFS和短作業(yè)優(yōu)先SJF進(jìn)程調(diào)度算法 姓 名： 學(xué) 號(hào)： 專 業(yè)： 學(xué) 院： 指導(dǎo)教師： 林若寧 二零一八 年 十一月一、實(shí)驗(yàn)?zāi)康哪M單處理器系統(tǒng)的進(jìn)程調(diào)度，分別采用短作業(yè)優(yōu)先和先來先服務(wù)的進(jìn)程調(diào)度算法作為進(jìn)程設(shè)計(jì)算法，以加深對(duì)進(jìn)程的概念及進(jìn)程調(diào)度算法的理解二、實(shí)驗(yàn)內(nèi)容1. 短作業(yè)優(yōu)先調(diào)度算法原理 短作業(yè)優(yōu)先調(diào)度算法，是指對(duì)短作業(yè)或斷進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別可以用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先調(diào)度算法，是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它使它立即執(zhí)

2、行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。 2. 先來先服務(wù)調(diào)度算法原理 先來先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。三、程序設(shè)計(jì)1.概要設(shè)計(jì)程序包括主函數(shù)、FCFS算法函數(shù)、SJF算法函數(shù)、輸出函數(shù)；主

3、函數(shù)流程：輸入文件中的數(shù)據(jù)顯示各進(jìn)程數(shù)據(jù)選擇算法調(diào)用相應(yīng)算法的函數(shù)輸出結(jié)果2.算法流程SJF算法流程圖：3.詳細(xì)設(shè)計(jì)（1）定義一個(gè)結(jié)構(gòu)體typedef struct PCB char job_id10; /作業(yè)ID float Arr_time; /到達(dá)時(shí)刻 float Fun_time; /估計(jì)運(yùn)行時(shí)間 float Wait_time; /等待時(shí)間 float Start_time; /開始時(shí)刻 float Fin_time; /完成時(shí)刻 float Tur_time; /周轉(zhuǎn)時(shí)間 float WTur_time; /帶權(quán)周轉(zhuǎn)時(shí)間 int Order; /優(yōu)先標(biāo)記list;（2）先來先服務(wù)算

4、法函數(shù)void fcfs(list *p,int count) /先來先服務(wù)算法 list temp; /臨時(shí)結(jié)構(gòu)體變量 int i; int j; for(i = 1;i count;i+) /按到達(dá)時(shí)刻直接插入排序 temp = pi; j = i-1; while(temp.Arr_time = 0) pj+1 = pj; -j; pj+1 = temp; for(i = 0;i count;i+) /循環(huán)計(jì)算各個(gè)作業(yè)的時(shí)間值 if(i = 0) pi.Start_time = pi.Arr_time; else pi.Start_time = pi-1.Fin_time; /開始時(shí)刻=

5、前一個(gè)作業(yè)的完成時(shí)刻 pi.Wait_time = pi.Start_time - pi.Arr_time; /等待=開始-到達(dá) pi.Fin_time = pi.Start_time + pi.Fun_time; /完成=開始+運(yùn)行 pi.Tur_time = pi.Fin_time - pi.Arr_time; /周轉(zhuǎn)=完成-到達(dá) pi.WTur_time = pi.Tur_time / pi.Fun_time; /帶權(quán)周轉(zhuǎn)=周轉(zhuǎn)/運(yùn)行 return;（3）最短作業(yè)優(yōu)先函數(shù)void sjf(list *p,int count) /最短作業(yè)優(yōu)先算法（sjf） list item; /結(jié)構(gòu)體變

6、量 int i = 0; int j = 0; int k = 0; /最短運(yùn)行時(shí)間作業(yè)的下標(biāo) int flag = 0; /優(yōu)先級(jí)設(shè)置 float min = 0; /最短運(yùn)行時(shí)間 float temp; /開始的時(shí)刻 temp = p0.Arr_time; /先求出最先到達(dá)作業(yè)的時(shí)刻 for(i = 0;i pi.Arr_time) temp = pi.Arr_time; /保存最先到達(dá)的作業(yè)的時(shí)刻 k = i; /最先到達(dá)的作業(yè)的下標(biāo)，默認(rèn)為p0 for(i = 0;i count;i+) pk.Order = +flag; /設(shè)置優(yōu)先級(jí)為1，最高優(yōu)先級(jí) pk.Start_time =

7、temp; pk.Wait_time = temp - pk.Arr_time; /計(jì)算各個(gè)時(shí)間 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; /后一個(gè)作業(yè)的開始時(shí)刻是前一個(gè)作業(yè)的完成時(shí)刻 for(j = 0;j count;j+) if(pj.Order != 0 | temp - pj.Arr_time pj.Fun_time) min = p

8、j.Fun_time; k = j; /求出滿足條件最短運(yùn)行時(shí)間的作業(yè)的下標(biāo) for(i = 1;i count;i+) /按優(yōu)先級(jí)排序 item = pi; j = i-1; while(item.Order = 0) pj+1 = pj; -j; pj+1 = item; return;四、實(shí)驗(yàn)結(jié)果測(cè)試數(shù)據(jù)：進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間A04B13C25D44（1）先來先服務(wù)算法調(diào)試（2）最短作業(yè)優(yōu)先算法調(diào)試五、實(shí)驗(yàn)小結(jié)FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)(進(jìn)程)。 CPU繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求I/O。通常的科學(xué)計(jì)算便屬于C

9、PU繁忙型作業(yè)。 I/O繁忙型作業(yè)是指CPU進(jìn)行處理時(shí)需頻繁地請(qǐng)求I/O。目前的大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)：該算法對(duì)長(zhǎng)作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長(zhǎng)作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度。該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使

10、該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。#include stdafx.h#include#define MAX 100typedef struct PCB char job_id10; /作業(yè)ID float Arr_time; /到達(dá)時(shí)刻 float Fun_time; /估計(jì)運(yùn)行時(shí)間 float Wait_time; /等待時(shí)間 float Start_time; /開始時(shí)刻 float Fin_time; /完成時(shí)刻 float Tur_time; /周轉(zhuǎn)時(shí)間 float WTur_time; /帶權(quán)周轉(zhuǎn)時(shí)間 int Order; /優(yōu)先標(biāo)記list;void fcfs(list *p,

11、int count); void sjf(list *p,int count);void print(list *p,int count);void avg(list *p,int count);void fcfs(list *p,int count) /先來先服務(wù)算法 list temp; /臨時(shí)結(jié)構(gòu)體變量 int i; int j; for(i = 1;i count;i+) /按到達(dá)時(shí)刻直接插入排序 temp = pi; j = i-1; while(temp.Arr_time = 0) pj+1 = pj; -j; pj+1 = temp; for(i = 0;i count;i+)

12、/循環(huán)計(jì)算各個(gè)作業(yè)的時(shí)間值 if(i = 0) pi.Start_time = pi.Arr_time; else pi.Start_time = pi-1.Fin_time; /開始時(shí)刻=前一個(gè)作業(yè)的完成時(shí)刻 pi.Wait_time = pi.Start_time - pi.Arr_time; /等待=開始-到達(dá) pi.Fin_time = pi.Start_time + pi.Fun_time; /完成=開始+運(yùn)行 pi.Tur_time = pi.Fin_time - pi.Arr_time; /周轉(zhuǎn)=完成-到達(dá) pi.WTur_time = pi.Tur_time / pi.Fun_

13、time; /帶權(quán)周轉(zhuǎn)=周轉(zhuǎn)/運(yùn)行 return;void sjf(list *p,int count) /最短作業(yè)優(yōu)先算法（sjf） list item; /結(jié)構(gòu)體變量 int i = 0; int j = 0; int k = 0; /最短運(yùn)行時(shí)間作業(yè)的下標(biāo) int flag = 0; /優(yōu)先級(jí)設(shè)置 float min = 0; /最短運(yùn)行時(shí)間 float temp; /開始的時(shí)刻 temp = p0.Arr_time; /先求出最先到達(dá)作業(yè)的時(shí)刻 for(i = 0;i pi.Arr_time) temp = pi.Arr_time; /保存最先到達(dá)的作業(yè)的時(shí)刻 k = i; /最先到達(dá)

14、的作業(yè)的下標(biāo)，默認(rèn)為p0 for(i = 0;i count;i+) pk.Order = +flag; /設(shè)置優(yōu)先級(jí)為1，最高優(yōu)先級(jí) pk.Start_time = temp; pk.Wait_time = temp - pk.Arr_time; /計(jì)算各個(gè)時(shí)間 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; /后一個(gè)作業(yè)的開始時(shí)刻是前一個(gè)作業(yè)的完

15、成時(shí)刻 for(j = 0;j count;j+) if(pj.Order != 0 | temp - pj.Arr_time pj.Fun_time) min = pj.Fun_time; k = j; /求出滿足條件最短運(yùn)行時(shí)間的作業(yè)的下標(biāo) for(i = 1;i count;i+) /按優(yōu)先級(jí)排序 item = pi; j = i-1; while(item.Order = 0) pj+1 = pj; -j; pj+1 = item; return;void print(list *p,int count) /輸出各個(gè)作業(yè)的詳細(xì)信息 int i; printf(*n); printf(I

16、Dt到達(dá)t運(yùn)行t等待t開始t完成t周轉(zhuǎn)t帶權(quán)周轉(zhuǎn)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,pi.Start_time,pi.Fin_time,pi.Tur_time,pi.WTur_time); return;void avg(list *p,int count) float AvgTur1; /平均周轉(zhuǎn) float AvgTur2; /平均帶權(quán)周轉(zhuǎn) float t1 = 0; float t2 =

17、0; int i; for(i = 0;i count;i+) t1 += pi.Tur_time; /周轉(zhuǎn)時(shí)間和 t2 += pi.WTur_time; /帶權(quán)周轉(zhuǎn)和 AvgTur1 = t1/count; AvgTur2 = t2/count; printf(n平均周轉(zhuǎn)時(shí)間為：%ft平均帶權(quán)周轉(zhuǎn)時(shí)間為：%fn,AvgTur1,AvgTur2); printf(n*n); return;int main() list stMAX; /最多可以一百個(gè)作業(yè) int job_count = 0; /作業(yè)數(shù)量 int flag = 1; /算法標(biāo)記 int i = 0; printf(請(qǐng)輸入作業(yè)數(shù)量：); scanf(%d,&job_count); printf(請(qǐng)輸入作業(yè)ID，到達(dá)時(shí)刻，估計(jì)運(yùn)行時(shí)間(用空格隔開)：n); do scanf(%s %f %f,sti.job_id,&sti.Arr_time,&sti.Fun_time); sti.Order = 0; /優(yōu)先級(jí)初始化 wh