先進(jìn)先出算法實驗報告

1、文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.答卷封面(COVER)評閱結(jié)果Final mark評閱人Examiner課程名稱（ Subject）：操作系統(tǒng)課程設(shè)計編號 (No.) ：系別 (Department):專業(yè) (Major) ：姓名 (Name)：學(xué)號 (Students Number)：注意事項（ Notes ）1. 考生需將上述有關(guān)項目填寫清楚2. 字跡要清楚，保持卷面清潔。3. 交卷時請將本答卷和題簽一起上交，題簽作為封面下一頁裝訂。1、Candidates should fill in the information appropriately.2、K

2、eep the handwriting clear and the paper tidy.3、Candidate should hand in this cover and paper together; the answer sheet should be attached to the cover.文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.機(jī)密（ Confidential ）編號（ No.）： 11-12-1-050154試 題（ Test）課程名稱 （Subject ）：操作系統(tǒng)課程設(shè)計考核類別（ Type of test）：考查課程類別(Type of cou

3、rse ) :實踐環(huán)節(jié)考試形式(Test type) :論文使用范圍（Target group ）：計算機(jī)科學(xué)與技術(shù)要求：一、通過本課程設(shè)計， 使學(xué)生在上機(jī)實驗中體會計算機(jī)操作系統(tǒng)的基本原理，訓(xùn)練學(xué)生模擬實現(xiàn)操作系統(tǒng)管理和控制資源的能力。二、學(xué)生可在下列14 個題目中任選 1 個。（ 1）先來先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法、時間片輪轉(zhuǎn)調(diào)度算法、優(yōu)先級調(diào)度算法（ 2）生產(chǎn)者 -消費(fèi)者問題、讀者 -寫者問題（ 3）最先適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法（ 4）先進(jìn)先出算法、最久未使用淘汰算法、理想淘汰算法（ 5）銀行家算法（ 6）進(jìn)程通信（ 7）小型文件系統(tǒng)三、模擬實現(xiàn)算法在 Windows

4、 平臺下，可用 C 語言、C+語言和 Java 語言等。摘要本文圍繞 Java 編程，按照進(jìn)程進(jìn)入就緒隊列的先后次序來分配處理器，對先進(jìn)先出程序進(jìn)行需求分析、概要設(shè)計、詳細(xì)設(shè)計，最后使用Java 編程實現(xiàn)的全過程。關(guān)鍵詞： 操作系統(tǒng)先進(jìn)先出算法java語言文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.目錄一、設(shè)計題目.二、設(shè)計內(nèi)容.三、設(shè)計過程.3.1 需求分析 .3.2 概要設(shè)計 .3.3 詳細(xì)設(shè)計 .3.4 代碼實現(xiàn) .3.5 程序運(yùn)行 .四、總結(jié) .五、參考文獻(xiàn).文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.一、設(shè)計題目先來先服務(wù)調(diào)度算法。二、

5、設(shè)計內(nèi)容1、 綜合應(yīng)用下列知識點(diǎn)設(shè)計并實現(xiàn)操作系統(tǒng)的進(jìn)程調(diào)度：先進(jìn)先出，進(jìn)程控制塊，進(jìn)程狀態(tài)轉(zhuǎn)換，多級反饋隊列進(jìn)程調(diào)度算法。2、 加深理解操作系統(tǒng)進(jìn)程調(diào)度的過程。3、 加深理解先進(jìn)先出調(diào)度算法。4、由于在單道批處理系統(tǒng)中，作業(yè)一投入運(yùn)行，它就占有計算機(jī)的一切資源直到作業(yè)完成為止，因此調(diào)度作業(yè)時不必考慮它所需要的資源是否得到滿足，它所占用的CPU限等因素。5、作業(yè)調(diào)度算法：采用先來先服務(wù)（FCFS）調(diào)度算法，即按作業(yè)提交的先后次序進(jìn)時行調(diào)度。6、總是首先調(diào)度在系統(tǒng)中等待時間最長的作業(yè)。每個作業(yè)由一個作業(yè)控制塊JCB表示， JCB 可以包含如下信息：作業(yè)名、提交時間、所需的運(yùn)行時間、所需的資源、作

6、業(yè)狀態(tài)、鏈指針等等。7、作業(yè)的狀態(tài)可以是等待W(Wait) 、運(yùn)行 R(Run) 和完成 F(Finish) 三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待W。8、各個等待的作業(yè)按照提交時刻的先后次序排隊，總是首先調(diào)度等待隊列中隊首的作業(yè)。9、每個作業(yè)完成后要打印該作業(yè)的開始運(yùn)行時刻、完成時刻、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，這一組作業(yè)完成后10、要計算并打印這組作業(yè)的平均周轉(zhuǎn)時間、帶權(quán)平均周轉(zhuǎn)時間。三、設(shè)計過程3.1 需求分析1. 由于在單道批處理系統(tǒng)中， 作業(yè)一投入運(yùn)行， 它就占有計算機(jī)的一切資源直到作業(yè)完成為止，因此調(diào)度作業(yè)時不必考慮它所需要的資源是否得到滿足，它所占用的CPU 時限等因素。2. 每個

7、作業(yè)由一個作業(yè)控制塊JCB 表示， JCB可以包含如下信息：作業(yè)名、提交時間、所需的運(yùn)行時間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。作業(yè)的狀態(tài)可以是等待W(Wait) 、運(yùn)行R(Run) 和完成F(Finish)三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待W。例如，三個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時間作業(yè)1 28作業(yè)2 9作業(yè)采用FCFS 算法，三個作業(yè)的周轉(zhuǎn)時間分別為：28、 37和 40，因此，平均作業(yè)周轉(zhuǎn)時間T = (28+37+40)/3 = 35文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.若三個作業(yè)提交順序改為作業(yè)2、 1、 3 ，平均作業(yè)周轉(zhuǎn)時間

8、約為29 。(9+37+40)/3 29)若三個作業(yè)提交順序改為作業(yè)3、 2、 1 ，平均作業(yè)周轉(zhuǎn)時間約為18 。(3+12+40)/3 18)FCFS 調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)。3.2 概要設(shè)計設(shè)計、編寫一個進(jìn)程調(diào)度程序，允許多個進(jìn)程共同運(yùn)行的進(jìn)程調(diào)度程序。（ 1）進(jìn)程調(diào)度算法：采用先進(jìn)先出算法（ 2）每個進(jìn)程有一個進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時間、需要運(yùn)行時間、已用CPU時間、進(jìn)程狀態(tài)等等。（ 3）進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時間可以事先人為地指定 （也可以由隨機(jī)數(shù)產(chǎn)生） 。進(jìn)程的到達(dá)時間為輸入進(jìn)程的時間。（ 4）進(jìn)程的運(yùn)行時

9、間以時間片為單位進(jìn)行計算。（ 5）進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換。 1）每個進(jìn)程的狀態(tài)可以是就緒 W（ Wait ）、運(yùn)行 R（Run）、或完成 F（ Finish ）三種狀態(tài)之一； 2）就緒進(jìn)程獲得 CPU 后都只能運(yùn)行一個時間片。用已占用 CPU時間加 1 來表示； 3）如果運(yùn)行一個時間片后，進(jìn)程的已占用CPU 時間已達(dá)到所需要的運(yùn)行時間， 則撤消該進(jìn)程， 如果運(yùn)行一個時間片后進(jìn)程的已占用CPU時間還未達(dá)所需要開 始CPU； 4）每進(jìn)行一的運(yùn)行時間，也就是進(jìn)程還需要繼續(xù)運(yùn)行，然后把它插入就緒隊列等待次調(diào)度程序都打印一次運(yùn)行進(jìn)程、就緒隊列、以及各個進(jìn)程的PCB，以便進(jìn)行檢查； 5）重復(fù)以上過程，直到所要

10、進(jìn)程都完成為止。（ 6）進(jìn)程的到達(dá)時間為輸入進(jìn)程時間，進(jìn)程的運(yùn)行時間以時間片的計算單位計算。調(diào)用初始化子程序（ 7）每一個進(jìn)程的狀態(tài)可以使就緒W(wait), 運(yùn)行 R(Run) 或完成 F(Fish) 三種狀態(tài)之一（ 8）建立一個類 PCB控制進(jìn)程建立一個類 TestFrame 測試進(jìn)程建立一個類List_Test管理進(jìn)程建立一個類Main 寫主函數(shù)調(diào)用運(yùn)行子程序主流程圖：結(jié)束3.3 詳細(xì)設(shè)計設(shè)定系統(tǒng)中有n 個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊（PCB）表示，進(jìn)程隊列采用鏈表數(shù)據(jù)結(jié)構(gòu)。進(jìn)程控制塊包含如下信息：進(jìn)程名、優(yōu)先數(shù)、需要運(yùn)行時間、已用CPU時間、進(jìn)程狀態(tài)等等。每次運(yùn)行設(shè)計的處理調(diào)度程序

11、之前，由終端輸入n 個進(jìn)程的 “優(yōu)先數(shù)” 和“要求運(yùn)行時間”。進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時間人為地指定. 進(jìn)程的運(yùn)行時間以時間片為單位進(jìn)行計算。采用優(yōu)先權(quán)調(diào)度算法， 將五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成就緒隊列。 用頭指針指出隊列首進(jìn)程，隊列采用鏈表結(jié)構(gòu)。處理機(jī)調(diào)度總是選隊列首進(jìn)程運(yùn)行。采用動態(tài)優(yōu)先數(shù)辦法，進(jìn)程每運(yùn)行一次將已運(yùn)行時間加“1”。進(jìn)程運(yùn)行一次后，若要求運(yùn)行時間不等于已運(yùn)行時間，則再將它加入就緒隊列；否則文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.將其狀態(tài)置為“結(jié)束”, 且退出就緒隊列?！熬途w”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面 6，7 步驟，直到所有進(jìn)程都成為“

12、結(jié)束”狀態(tài)。在計的程序中有輸入語句，輸入n 個進(jìn)程的“優(yōu)先數(shù)”和“要求運(yùn)行時間”，也有顯示或打印語句， 能顯示或打印每次被選中進(jìn)程的進(jìn)程名、 運(yùn)行一次后隊列的變化， 以及結(jié)束進(jìn)程的進(jìn)程名。最后，為 n 個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時間”，運(yùn)行并調(diào)試所設(shè)計的程序，顯示或打印出逐次被選中進(jìn)程的進(jìn)程名及其進(jìn)程控制塊的動態(tài)變化過程。：程序說明：在先來先服務(wù)算法中，按作業(yè)提交的先后次序進(jìn)行調(diào)度。程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明：#define num 5/假定系統(tǒng)中進(jìn)程個數(shù)為5struct PCBchar ID;/int runtime;/char state; /進(jìn)程名要求運(yùn)行時間狀態(tài)， R

13、-就緒，F(xiàn)- 結(jié)束;struct PCB pcblistnum;/定義進(jìn)程控制塊數(shù)組流程圖：3.4 代碼實現(xiàn)經(jīng)過前面的工作，最后在集成編輯環(huán)境中，編寫的程序代碼如下： public class FCFS extends JFrame implements ActionListener Vector workVector;int status=0,0,0,0,0;String workname=" 作業(yè)名 "," 提交時刻 "," 要求運(yùn)行時間 "," 運(yùn)行時刻 "," 完成時刻 ","

14、 周轉(zhuǎn)時間 "," 帶權(quán)周轉(zhuǎn)時間 "String worktable=new String57;JTable workjtable;JScrollPane messageScrollPane;JToolBar toolBar = new JToolBar();JButton InputButton;JButton FCFSButton;JButton exitButton;JTextField show;JTextArea source;public void actionPerformed(ActionEvent e)Object obj = e.getSour

15、ce();if (obj =InputButton)String stringnum;Work work=new Work();stringnum=JOptionPane.showInputDialog(this," 作業(yè)名、 提交時刻、 要求運(yùn)行時間 ").trim();文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.StringTokenizer st0 = new StringTokenizer(stringnum);if(st0.hasMoreTokens()work.workname=(String)st0.nextToken();source

16、.append("作業(yè) : "+work.workname);if(st0.hasMoreTokens()work.refertime=Double.valueOf(st0.nextToken().doubleValue();source.append("提交時間為 : "+work.refertime);if(st0.hasMoreTokens()work.needtime=Double.valueOf(st0.nextToken().doubleValue(); source.append(" 要求運(yùn)行時間為 : "+work.n

17、eedtime);source.append("n");workVector.add(work);if ( obj = FCFSButton)for(int a=0;a<5;a+)statusa=0;int i=0;double minrefertime,finishtime=0,T=0,sunT=0,sunW=0,W=0;Work work=new Work();Work work1=new Work();Work work2=new Work();String msg;while(i<workVector.size()if(statusi=0)work=(W

18、ork)workVector.elementAt(i);worktablei0=String.valueOf(work.workname);worktablei1=String.valueOf(work.refertime);worktablei2= String.valueOf(work.needtime);minrefertime=work.refertime;int j=0,k=i;while(j<workVector.size() /找出最先到達(dá)的進(jìn)程work1=(Work)workVector.elementAt(j);/指定索引處if(minrefertime>work

19、1.refertime&&statusj=0)文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.minrefertime=work1.refertime;k=j;j+;T=sunT/i;W=sunW/i;msg=" 平均周轉(zhuǎn)時間 T="+T+" 時間單位 "+","+" 平均帶權(quán)周轉(zhuǎn)時間 W="+W; workjtable=new JTable(worktable,workname); show=new JTextField(30);show.setText(msg);messag

20、eScrollPane = new JScrollPane(workjtable, JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED, JScrollPane.HORIZONTAL_SCROLLBAR_AS_NEEDED);messageScrollPane.setPreferredSize(new Dimension(400, 101); messageScrollPane.revalidate();JFrame frame=new JFrame();frame.setSize(400,180);frame.setLocation(200,300);frame

21、.setTitle("FCFS的作業(yè)調(diào)度 ");frame.setLayout(new BorderLayout();frame.add(messageScrollPane,BorderLayout.NORTH);frame.add(show,BorderLayout.CENTER);frame.setVisible(true);if ( obj = exitButton)int j=JOptionPane.showConfirmDialog(this,"真的要停止服務(wù)嗎"," 停止服務(wù) ",JOptionPane.YES_OPTIO

22、N,JOptionPane.QUESTION_MESSAGE); if(j=JOptionPane.YES_OPTION)System.exit(0);public static void main(String arg)FCFS FCFS1=new FCFS();class WorkString workname=null;double refertime=0;double needtime=0;double starttime=0;double finishtime=0;文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.double alltime=0;double ratealltime=0;3.5 程序運(yùn)行測試用例：屏幕顯示：請輸入進(jìn)程個數(shù)輸入：4<回車>屏幕顯示：請輸入 進(jìn)程名稱 ( 字母 ) 提交時刻 運(yùn)行時間輸入：進(jìn)程