短作業(yè)優(yōu)先的作業(yè)調(diào)度-操作系統(tǒng)課程設(shè)計(jì)

1、摘 要 作業(yè)調(diào)度是對(duì)成批進(jìn)入系統(tǒng)的用戶作業(yè)，根據(jù)作業(yè)控制塊的信息，按一定的策略選取若干個(gè)作業(yè)使它們可以去獲得處理器運(yùn)行的一項(xiàng)工作。而對(duì)每個(gè)用戶來(lái)說(shuō)總希望自己的作業(yè)的周轉(zhuǎn)時(shí)間是最小的，短作業(yè)優(yōu)先（SJF）便是其中一種調(diào)度方法。 本設(shè)計(jì)是為了加深對(duì)作業(yè)概念的理解，掌握短作業(yè)優(yōu)先（SJF）算法，深入了解批處理系統(tǒng)如何組織作業(yè)、管理作業(yè)和調(diào)度作業(yè)，了解作業(yè)控制塊的作用，以及作業(yè)控制塊的內(nèi)容和組織方式。為了將系統(tǒng)中的作業(yè)組織起來(lái)，需要為每個(gè)進(jìn)入系統(tǒng)的作業(yè)建立檔案以記錄和作業(yè)相關(guān)的信息，例如作業(yè)名、作業(yè)所需資源、作業(yè)執(zhí)行時(shí)間、作業(yè)進(jìn)入系統(tǒng)的時(shí)間、作業(yè)信息在存儲(chǔ)器中的位置、指向下一個(gè)作業(yè)控制塊的指針等信息。

2、這個(gè)記錄作業(yè)相關(guān)信息的數(shù)據(jù)塊稱為作業(yè)控制塊（JCB），并將系統(tǒng)中等待作業(yè)調(diào)度的作業(yè)控制塊組織成一個(gè)隊(duì)列，這個(gè)隊(duì)列稱為后備隊(duì)列。一個(gè)作業(yè)全部信息進(jìn)入系統(tǒng)后，就為其建立作業(yè)控制塊，并掛入后備隊(duì)列。當(dāng)進(jìn)行作業(yè)調(diào)度時(shí)，從后備隊(duì)列中查找選擇作業(yè)。在從后備隊(duì)列中查找選擇作業(yè)是，先根據(jù)作業(yè)控制塊中的信息，選中一個(gè)短作業(yè)，也就是執(zhí)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。關(guān)鍵詞 ：作業(yè); 調(diào)度; 短作業(yè)優(yōu)先; SJF; JCBAbstractBatch job scheduling problem is to enter the system according to the user, the job cont

3、rol block of information, according to certain strategy selection several assignments that they can go to obtain a processor runs. For each user is always hope their job cycle time is the smallest, short j (SJF) which is the preferred method of a kind of scheduling.This design is to deepen the under

4、standing of the concept of job assignments, short job first (SJF) algorithm is, in-depth understanding of how the system of batch management and organization, scheduling, understand the job assignments, as well as the job control blocks of content and organization.In order to organize the assignment

5、 system for everyone to enter the system to establish archives of job assignments and related information recorded, for example, job assignments, resources, work into execution time of time, information system in memory of job assignments, pointing to a position job control block etc. The record of

6、the information data block job assignments job control blocks (called), and the system JCB waiting in the job assignments scheduling job control block into a queue, the queue as backup queue. A full information into a system for its establishment, operation job control block, and hung the backup que

7、ue. When scheduling problem, from the backlog queue for choice.From the backlog queue for job first choice, according to the information and job control block a short assignment, and select the shortest time is executed, they would run into memory.Keywords ： Job; Scheduling; Short job first; SJF; JC

8、B目 錄第一章 課題概述.11.1 設(shè)計(jì)背景.11.2 目的及要求.11.3 基本理論依據(jù).1第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述 . 22.1 設(shè)計(jì)簡(jiǎn)介 .22.2 設(shè)計(jì)內(nèi)容.2第三章詳細(xì)設(shè)計(jì). 33.1 設(shè)計(jì)流程圖 .33.2 主要程序代碼 .4第四章設(shè)計(jì)結(jié)果及分析. 74.1 運(yùn)行結(jié)果截圖 . 74.2 運(yùn)行結(jié)果分析 . 8總 結(jié) . 9致 謝 .10參考文獻(xiàn) .11附錄 程序代碼 .12- 17 -第一章 課題概述1.1設(shè)計(jì)背景在多道程序環(huán)境下，主存中有著多個(gè)進(jìn)程，其數(shù)目往往多于處理機(jī)數(shù)目。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由處理機(jī)

9、調(diào)度程序完成的。由于處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理機(jī)的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間），在很大程度上取決于處理機(jī)調(diào)度性能的好壞，因而，處理機(jī)調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過(guò)處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。對(duì)于批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度和進(jìn)程調(diào)度兩個(gè)過(guò)程后方能獲得處理機(jī)。本次設(shè)計(jì)就是模擬作業(yè)調(diào)度和短作業(yè)優(yōu)先的設(shè)計(jì)。1.2目的及要求1.2.1目的加深對(duì)作業(yè)概念的理解；深入了解批處理系統(tǒng)如何組織作業(yè)、管理作業(yè)和調(diào)度作業(yè)；1.2.2設(shè)計(jì)要求 1.加深對(duì)作業(yè)概念地理解。2.掌握短作業(yè)優(yōu)先調(diào)度算法。3.深入了解批處理系統(tǒng)如何組織作業(yè)

10、、管理作業(yè)和調(diào)度作業(yè)。4.了解作業(yè)控制塊的作用，以及作業(yè)控制塊的內(nèi)容和組織方式。1.3基本理論依據(jù)根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。短作業(yè)優(yōu)先調(diào)度算法，從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。第二章 設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述2.1 設(shè)計(jì)簡(jiǎn)介在多道程序環(huán)境下，將系統(tǒng)中的作業(yè)組織起來(lái)，為每個(gè)進(jìn)入系統(tǒng)的作業(yè)建立檔案以記錄和作業(yè)相關(guān)的信息，按要求輸入作業(yè)名、到達(dá)時(shí)間和服務(wù)時(shí)間，并為其建立作業(yè)控制塊（JCB）掛入后備隊(duì)列。進(jìn)行作業(yè)調(diào)度時(shí)，在其后計(jì)算出各個(gè)作

11、業(yè)的開(kāi)始執(zhí)行時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間，利用短作業(yè)優(yōu)先算法進(jìn)行作業(yè)調(diào)度，并按照由小到大的順序顯示出來(lái)。2.2 設(shè)計(jì)內(nèi)容 編寫(xiě)程序完成批處理系統(tǒng)中的作業(yè)調(diào)度，要求采用短作業(yè)優(yōu)先的作業(yè)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定作業(yè)控制塊的內(nèi)容，作業(yè)控制塊的組成方式；然后完成作業(yè)調(diào)度；最后編寫(xiě)主函數(shù)對(duì)所作工作進(jìn)程測(cè)試。 2.2.1 創(chuàng)建JCB作業(yè)控制塊 創(chuàng)建作業(yè)控制塊JCB，定義為結(jié)構(gòu)體，為進(jìn)入系統(tǒng)的作業(yè)建立檔案，其中定義了作業(yè)名，作業(yè)到達(dá)時(shí)間，作業(yè)服務(wù)時(shí)間，作業(yè)開(kāi)始執(zhí)行時(shí)間，作業(yè)完成時(shí)間，作業(yè)周轉(zhuǎn)時(shí)間，作業(yè)平均周轉(zhuǎn)時(shí)間。2.2.2 控制顯示信息 輸出文字提醒用戶操作步驟；設(shè)定輸入數(shù)據(jù)的格式及數(shù)量

12、；運(yùn)行完程序后顯示輸出實(shí)驗(yàn)結(jié)果。2.2.3 實(shí)現(xiàn)短作業(yè)優(yōu)先選擇首先按各個(gè)作業(yè)完成時(shí)間由小到大排序。再用輸入的到達(dá)時(shí)間與服務(wù)時(shí)間按一定算法算出各個(gè)作業(yè)的開(kāi)始執(zhí)行時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間和作業(yè)平均周轉(zhuǎn)時(shí)間。第三章 詳細(xì)設(shè)計(jì)開(kāi)始定義最多能管理的作業(yè)數(shù)目，建立作業(yè)控制塊定義作業(yè)各個(gè)數(shù)據(jù)輸出提示，讓用戶輸入需要處理的作業(yè)數(shù)目，并輸入各作業(yè)的作業(yè)名、作業(yè)到達(dá)時(shí)間和作業(yè)服務(wù)時(shí)間計(jì)算各個(gè)作業(yè)的作業(yè)開(kāi)始執(zhí)行時(shí)間，作業(yè)完成時(shí)間，作業(yè)周轉(zhuǎn)時(shí)間，作業(yè)平均周轉(zhuǎn)時(shí)間進(jìn)入作業(yè)比較后備隊(duì)列是否為空作業(yè)i完成時(shí)間<作業(yè)i+1完成時(shí)間按完成時(shí)間由小到大輸出結(jié)果，并由小到大輸出作業(yè)名，作業(yè)到達(dá)時(shí)間，作業(yè)服務(wù)時(shí)間，作業(yè)開(kāi)始執(zhí)行

13、時(shí)間，作業(yè)完成時(shí)間，作業(yè)周轉(zhuǎn)時(shí)間，作業(yè)平均周轉(zhuǎn)時(shí)間結(jié)束3.1 設(shè)計(jì)流程圖 是 否 否 是 圖3-13.2 主要程序代碼3.2.1 采用數(shù)據(jù)結(jié)構(gòu)定義作業(yè)控制塊struct jcb char name10; /作業(yè)名 float arrivetime; /作業(yè)到達(dá)時(shí)間 float servicetime;/作業(yè)服務(wù)時(shí)間 float starttime; /作業(yè)開(kāi)始執(zhí)行時(shí)間 float finishtime; /作業(yè)完成時(shí)間 float zztime; /作業(yè)周轉(zhuǎn)時(shí)間 float avezztime; /作業(yè)平均周轉(zhuǎn)時(shí)間;3.2.2 jcb調(diào)度算法void jcbf(jcb *p,int N)flo

14、at arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,avezztime=0; sort(p,N); /以到達(dá)時(shí)間從小到大排序 for(int m=0;m<N-1;m+) if(m=0) pm.finishtime=pm.arrivetime+pm.servicetime; else pm.finishtime=pm-1.finishtime+pm.servicetime; int i=0; for(int n=m+1;n<=N-1;n+) if(pn.arrivetime<=pm.finishtime

15、) /查找下標(biāo)m+1以后的作業(yè)中:服務(wù)時(shí)間<=pm.finishtime的作業(yè)個(gè)數(shù) i+; float min=pm+1.servicetime; int next=m+1;/m+1=n for(int k=m+1;k<m+i;k+) /循環(huán)查找服務(wù)時(shí)間最小的作業(yè) if(pk+1.servicetime<min) min=pk+1.servicetime; next=k+1; jcb temp; temp=pm+1; pm+1=pnext; pnext=temp; 3.2.3 主函數(shù)int main() while(1) system("CLS"); in

16、t N; printf("ttt-短作業(yè)優(yōu)先調(diào)度算法-n"); printf("請(qǐng)輸入作業(yè)數(shù)目:"); scanf("%d",&N); char ch; if(N>MAX) printf("t!輸入的作業(yè)數(shù)目太大,請(qǐng)輸入不大于%d的整數(shù)n",MAX); printf("按Q或者q退出程序,按其他任意鍵繼續(xù)測(cè)試."); ch = getch(); if(ch='Q'|ch='q') break; else continue; input(a,N); j

17、cb *b=a; jcbf(b,N); printf("按Q或者q退出程序,按其他任意鍵繼續(xù)測(cè)試.");ch = getch(); if(ch='Q'|ch='q') break; return 0;第四章 設(shè)計(jì)結(jié)果及分析4.1 運(yùn)行結(jié)果截圖4.1.1 初始化界面圖4-1 初始化4.1.2 輸入要調(diào)度的作業(yè)數(shù)目圖4-2 輸入作業(yè)數(shù)目4.1.3 輸入作業(yè)名、到達(dá)時(shí)間、服務(wù)時(shí)間圖4-3 輸入各作業(yè)信息4.1.4 運(yùn)行出的結(jié)果圖4-4 運(yùn)行結(jié)果4.2 運(yùn)行結(jié)果分析調(diào)度順序?yàn)椋篈->D->B->E->C運(yùn)行結(jié)果如表所示：Nam

18、e作業(yè)名Arrive到達(dá)時(shí)間Service服務(wù)時(shí)間Start開(kāi)始時(shí)間Finish完成時(shí)間Zz周轉(zhuǎn)時(shí)間Avezz平均周轉(zhuǎn)時(shí)間A0.004.000.004.004.001.00D3.002.004.006.003.001.50B1.003.006.009.008.002.67E4.004.009.0013.009.002.25C2.005.0013.0018.0016.003.20表4-2 結(jié)果分析可知：短作業(yè)優(yōu)先法先由到達(dá)時(shí)間排序，執(zhí)行作業(yè)，然后對(duì)后來(lái)進(jìn)入系統(tǒng)的作業(yè)和系統(tǒng)中等待執(zhí)行的作業(yè)進(jìn)行計(jì)算、比較，以服務(wù)時(shí)間有小到大排序，并按此順序進(jìn)行調(diào)度?？?結(jié)課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí)，發(fā)現(xiàn)、提

19、出、分析和解決實(shí)際問(wèn)題，鍛煉實(shí)踐能力的重要環(huán)節(jié)，是對(duì)我們的實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程。我做的是作業(yè)調(diào)度模擬，一開(kāi)始拿到題目時(shí)，實(shí)在不知道操作系統(tǒng)和c+如何聯(lián)系在一起，經(jīng)過(guò)翻閱資料、網(wǎng)上查詢、討論，最后終于完成了本次課程設(shè)計(jì)。短作業(yè)優(yōu)先調(diào)度算法易于實(shí)現(xiàn)，并且效率很高，但是短作業(yè)只考慮到短作業(yè)的利益，而不顧長(zhǎng)作業(yè)，這樣就可能會(huì)使得長(zhǎng)作業(yè)一直處于等待狀態(tài)而不能運(yùn)行。所以，短作業(yè)優(yōu)先算法適用于系統(tǒng)中短作業(yè)較多的情況。通過(guò)這次課程設(shè)計(jì)，我對(duì)操作系統(tǒng)中的作業(yè)調(diào)度模擬和短作業(yè)優(yōu)先算法有了更深的認(rèn)識(shí)。并且發(fā)現(xiàn)，只看課本上的知識(shí)遠(yuǎn)遠(yuǎn)不夠，只一味學(xué)習(xí)也根本沒(méi)用，必須要?jiǎng)邮钟H自實(shí)踐，才能真正掌握所學(xué)的東西。致

20、 謝本次課程設(shè)計(jì)能順利完成，是在老師的精心指導(dǎo)和同學(xué)的互相幫助下完成的，無(wú)論從學(xué)習(xí)上還是實(shí)踐上都使我受益匪淺。感謝院系為我們提供實(shí)練的機(jī)會(huì),感謝老師的細(xì)心指導(dǎo)，也感謝組員們的互相幫助互相探討。在本次設(shè)計(jì)中，自己動(dòng)手，親身經(jīng)歷了從學(xué)習(xí)、探討、編寫(xiě)、調(diào)試的過(guò)程。不僅使對(duì)書(shū)本上的知識(shí)點(diǎn)和理論有了更深一層的了解，使我學(xué)會(huì)如何利用所學(xué)知識(shí)，把理論結(jié)合于實(shí)踐，更重要的是讓我發(fā)散思路，提高實(shí)踐動(dòng)手能力。此次的課程設(shè)計(jì)收獲很多，雖然過(guò)程磕磕絆絆，但是最終還是完成了。但是，單單完成還遠(yuǎn)遠(yuǎn)不夠，還有許許多多的問(wèn)題，自己仍然不懂，是在老師、同學(xué)的幫助下完成的，在這里再次對(duì)他們的幫助表示衷心的感謝。參考文獻(xiàn)1 湯小丹

21、 梁紅兵 哲鳳屏等計(jì)算機(jī)操作系統(tǒng)（第三版）M西安電子科技大學(xué)出版社，2007年出版91-95頁(yè)2任愛(ài)華 李鵬 劉方毅 編著. 操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)M . 清華大學(xué)出版社,2004年出版.134-157頁(yè).3呂鳳翥 編著.C+語(yǔ)言基礎(chǔ)教程M .清華大學(xué)出版社,2007年出版.4 譚浩強(qiáng)著.C程序設(shè)計(jì)(第三版)M .清華大學(xué)出版社，2005年出版.附錄 程序代碼#include<stdio.h>#include<conio.h>#include<windows.h>#define MAX 100 /最多能管理的作業(yè)數(shù)目struct jcb /作業(yè)控制塊JCB,定義為

22、結(jié)構(gòu)體 char name10; /作業(yè)名 float arrivetime; /作業(yè)到達(dá)時(shí)間 float servicetime;/作業(yè)服務(wù)時(shí)間 float starttime; /作業(yè)開(kāi)始執(zhí)行時(shí)間 float finishtime; /作業(yè)完成時(shí)間 float zztime; /作業(yè)周轉(zhuǎn)時(shí)間 float avezztime; /作業(yè)平均周轉(zhuǎn)時(shí)間;jcb aMAX; void input(jcb *p,int N) int i; printf("請(qǐng)分別輸入:nt作業(yè)名,到達(dá)時(shí)間,服務(wù)時(shí)間(如:JOB1 5 10)nn"); for(i=0;i<=N-1;i+) pr

23、intf("請(qǐng)輸入第%d個(gè)作業(yè)信息:",i+1); scanf("%s%f%f",&,&pi.arrivetime,&pi.servicetime); printf("n"); void Print(jcb *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float avezztime,int N) int k; printf("調(diào)度順序:"); printf

24、("%s",); for(k=1;k<N;k+) printf("->%s",); printf("nn"); printf("ttt作業(yè)信息:n"); printf("nnametarrivetservicetstarttfinishtzztavezzn"); for(k=0;k<=N-1;k+) printf("%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftn",,pk.arriv

25、etime,pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.avezztime); void sort(jcb *p,int N) for(int i=0;i<=N-1;i+) for(int j=0;j<=i;j+) if(pi.arrivetime<pj.arrivetime) jcb temp; temp=pi; pi=pj; pj=temp; void deal(jcb *p, float arrivetime,float servicetime,float starttime,float finishti

26、me,float &zztime,float &avezztime,int N) int k; for(k=0;k<=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k<=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.avezztime=pk.zztime/pk.servicetime; void jcbf(jcb *p,int N) float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,avezztime=0;sort(p,N); for(int m=0;m<N-1;m+) if(m=0) pm.finishtime=pm.arrivetime+pm.servicetime; else pm.finishtime=pm-1.finish