作業系統實驗二作業排程模拟程式

實驗二作業排程模拟程式

專業：商業軟體工程一班姓名：李康梅學号：201406114103

一、目的和要求

1. 實驗目的

（1）加深對作業排程算法的了解；

（2）進行程式設計的訓練。

2．實驗要求

用進階語言編寫一個或多個作業排程的模拟程式。

單道批處理系統的作業排程程式。作業一投入運作，它就占有計算機的一切資源直到作業完成為止，是以排程作業時不必考慮它所需要的資源是否得到滿足，它所運作的時間等因素。

作業排程算法：

1) 采用先來先服務（FCFS）排程算法，即按作業到達的先後次序進行排程。總是首先排程在系統中等待時間最長的作業。

2) 短作業優先 (SJF) 排程算法，優先排程要求運作時間最短的作業。

3) 響應比高者優先(HRRN)排程算法，為每個作業設定一個優先權(響應比)，排程之前先計算各作業的優先權，優先數高者優先排程。RP (響應比)＝作業周轉時間 / 作業運作時間=1+作業等待時間/作業運作時間

每個作業由一個作業控制塊JCB表示，JCB可以包含以下資訊：作業名、送出（到達）時間、所需的運作時間、所需的資源、作業狀态、鍊指針等等。

作業的狀态可以是等待W（Wait）、運作R（Run）和完成F（Finish）三種之一。每個作業的最初狀态都是等待W。

一、模拟資料的生成

1．允許使用者指定作業的個數（2-24），預設值為5。

2．允許使用者選擇輸入每個作業的到達時間和所需運作時間。

3．（**）從檔案中讀入以上資料。

4．（**）也允許使用者選擇通過僞随機數指定每個作業的到達時間（0-30）和所需運作時間（1-8）。

二、模拟程式的功能

1．按照模拟資料的到達時間和所需運作時間，執行FCFS, SJF和HRRN排程算法，程式計算各作業的開始執行時間，各作業的完成時間，周轉時間和帶權周轉時間（周轉系數）。

2．動态示範每排程一次，更新現在系統時刻，處于運作狀态和等待各作業的相應資訊（作業名、到達時間、所需的運作時間等）對于HRRN算法，能在每次排程時顯示各作業的響應比R情況。

3．（**）允許使用者在模拟過程中送出新作業。

4．（**）編寫并排程一個多道程式系統的作業排程模拟程式。隻要求作業排程算法：采用基于先來先服務的排程算法。對于多道程式系統，要假定系統中具有的各種資源及數量、排程作業時必須考慮到每個作業的資源要求。

三、模拟資料結果分析

1．對同一個模拟資料各算法的平均周轉時間，周轉系數比較。

2．（**）用曲線圖或柱形圖表示出以上資料，分析算法的優點和缺點。

四、實驗準備

序号	準備内容	完成情況
1	什麼是作業？	作業是使用者送出給作業系統計算的一個獨立任務。
2	一個作業具備什麼資訊？
3	為了友善模拟排程過程，作業使用什麼方式的資料結構存放和表示？JCB	單個作業使用結構體，多個作業使用隊列。
4	作業系統中，常用的作業排程算法有哪些？	先來先服務（FCFS）算法，最短作業優先 (SJF)算法，最短剩餘時間優先算法，最高響應比優先(HRRN)算法。
5	如何程式設計實作作業排程算法？	先來先服務算法。
6	模拟程式的輸入如何設計更友善、結果輸出如何呈現更好？	輸入：讀取檔案輸出：計算并列印這組作業的平均周轉時間及帶權周轉時間。

五、其他要求

1．完成報告書，内容完整，規格規範。

2．實驗須檢查，回答實驗相關問題。

注：帶**号的條目表示選做内容。

二、實驗内容

根據指定的實驗課題，完成設計、編碼和調試工作，完成實驗報告。

三、實驗環境

可以采用TC，也可以選用Windows下的利用各種控件較為友善的VB，VC等可視化環境。也可以自主選擇其他實驗環境。

四、實驗原理及核心算法參考程式段

單道FCFS算法：

源代碼：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct jcb{
    char name[10];//作業名
    float subTime;//送出時間
    float waitTime;//等待時間
    float startTime;//開始時間
    float runTime;//運作時間
    float finishTime;//完成時間
    float cycleTime; //周轉時間
    float ValueCycleTime;//帶權周轉時間
    float rp;//響應比
};
jcb JCB[100];
void display1(float p,char *h,int i,int j)
{   
     strcpy(h,JCB[i].name);
     strcpy(JCB[i].name,JCB[j].name);
     strcpy(JCB[j].name,h);

     p=JCB[i].subTime;
     JCB[i].subTime=JCB[j].subTime;
     JCB[j].subTime=p;

     p=JCB[i].runTime;
    JCB[i].runTime=JCB[j].runTime;
    JCB[j].runTime=p;

    p=JCB[i].startTime;
    JCB[i].startTime=JCB[j].startTime;
    JCB[j].startTime=p;

    p=JCB[i].finishTime;
    JCB[i].finishTime=JCB[j].finishTime;
    JCB[j].finishTime=p;
}
void display2(int i,int y)
{
    printf("\n");
    printf("作業%s先開始運作\n\n",JCB[0].name);
    float AvgCycleTime,AvgValueCycleTime,k=0,m=0;//AvgCycleTime為平均周轉時間,AvgValueCycleTime為平均帶權周轉時間
      for(i=0;i<y;i++)
    {     
        JCB[0].startTime=JCB[0].subTime;
        JCB[i].finishTime=JCB[i].startTime+JCB[i].runTime;//結束時間    
        JCB[i+1].startTime=JCB[i].finishTime;
        JCB[i].waitTime=JCB[i].startTime-JCB[i].subTime;//等待時間
        JCB[i].cycleTime=JCB[i].finishTime-JCB[i].subTime;//周轉時間
        JCB[i].ValueCycleTime=JCB[i].cycleTime/JCB[i].runTime;//帶權周轉時間
        k+=JCB[i].cycleTime;
        m+=JCB[i].ValueCycleTime;
    }   
    AvgCycleTime=k/y;//平均周轉時間
    AvgValueCycleTime=m/y;//平均帶權周轉時間
    printf("作業名 送出時間 開始時間 運作時間 結束時間 等待時間 周轉時間 帶權周轉時間\n");
    for(i=0;i<y;i++)
        printf("%s\t%.2f\t%.2f\t%4.2f\t%6.2f\t%7.2f\t%7.2f\t%8.2f\n\n",JCB[i].name,JCB[i].subTime,JCB[i].startTime,JCB[i].runTime,JCB[i].finishTime,JCB[i].waitTime,JCB[i].cycleTime,JCB[i].ValueCycleTime);
    printf("平均周轉時間為：");
    printf("%.2f\n\n",AvgCycleTime);
    printf("平均帶權周轉時間為：");
    printf("%.2f\n\n",AvgValueCycleTime);
}
void FCFS(int y)//先來先服務算法
{ 
    float p;
    int i,j;
    char h[100];
    for(i=0;i<y;i++)
    {
          for(j=i+1;j<y;j++)
          {
             if(JCB[i].subTime>JCB[j].subTime)
             {
               display1(p,h,i,j);
             }
          }
    }
    display2(i,y);
}

void SJF(int y)//短作業優先算法
{
       float p;
    int i,j;
    char h[100];
    for(i=0;i<y;i++)//先送出的作業先運作，後面來的作業再比較運作時間長短
    {
          for(j=i+1;j<y;j++)
          {
             if(JCB[i].subTime>JCB[j].subTime)//先把作業按送出時間來排序
             {
               display1(p,h,i,j);
             }
          }
    }
    for(i=1;i<y;i++)
    {
         for(j=i+1;j<y;j++)
        {
             if(JCB[i].runTime>JCB[j].runTime)//比較後面來的作業的運作時間
            {
                  display1(p,h,i,j);
             }
        }
    }
    display2(i,y);
}

void HRRN(int y)//響應比高者優先算法
{
    int i,j;
    float AvgCycleTime,AvgValueCycleTime,p;
    char h[100];
    for(i=0;i<y;i++)//先送出的作業先運作，後面來的作業再比較響應比的大小
    {
          for(j=i+1;j<y;j++)
          {
             if(JCB[i].subTime>JCB[j].subTime)//先把作業按送出時間來排序
             {
               display1(p,h,i,j);
             }
          }
    }
    for(i=0;i<y;i++)
    {    
        JCB[0].startTime=JCB[0].subTime;
        JCB[i].finishTime=JCB[i].startTime+JCB[i].runTime;//結束時間    
        JCB[i+1].startTime=JCB[i].finishTime;
        JCB[i].waitTime=JCB[i].startTime-JCB[i].subTime;//等待時間
        JCB[i].cycleTime=JCB[i].finishTime-JCB[i].subTime;//周轉時間
        JCB[i].rp=JCB[i].cycleTime/JCB[i].runTime;//響應比
    }   
    for(i=1;i<y;i++)
    {
          for(j=i+1;j<y;j++)
          {
             if(JCB[i].rp<JCB[j].rp)//比較後面來的作業的響應比
             {
                display1(p,h,i,j);
                 p=JCB[i].rp;
                 JCB[i].rp=JCB[j].rp;
                 JCB[j].rp=p;
             }
          }
    } 
    display2(i,y);
    for(i=1;i<y;i++)
    {
        printf("%s的響應比為：%.2f\n",JCB[i].name,JCB[i].rp);
    }
}

int main()
{
    int i,x,y;
loop3:printf("-----------------請選擇作業排程算法------------------\n");
    printf("1:采用先來先服務 (FCFS) 排程算法\n2:采用短作業優先 (SJF) 排程算法\n3:采用響應比高者優先 (HRRN) 排程算法\n");
loop1:printf("請選擇：");
   scanf("%d",&i);
    if(i<=0||i>3)
    {
        printf("輸入有誤，請重新輸入\n");
        goto loop1;//無條件轉移語句
    }
loop2:printf("請輸入作業的個數(2-24):");
    scanf("%d",&y);
    if(y>=2&&y<=24)
    {
         printf("作業名 送出時間 運作時間\n");
         for(x=0;x<y;x++)
         {
            
             scanf("%s\t%f\t%f",&JCB[x].name,&JCB[x].subTime,&JCB[x].runTime);
             
         }
    }
    else
    {
        printf("輸入有誤，請重新輸入\n");
        goto loop2;
    }
    if(i==1)
    {
       FCFS(y);
       goto loop3;
    }
    else if(i==2)
    {
       SJF(y);
       goto loop3;
    }
    else if(i==3)
    {
       HRRN(y);
       goto loop3;
    }
    return 0;
}

運作結果：

五、實驗總結

今次的實驗主要是了解了作業排程的原理，是以做起來比較輕松，也熟悉掌握了冒泡排序算法。

雖然先來先服務算法、最短作業優先算法和最高響應比優先算法的原理不同，但是程式大體的架構

還是大同小異的。

作業系統 實驗二 作業排程模拟程式