模拟設計程序排程

在采用多道程式設計的系統中，往往有若幹個程序同時處于就緒狀态。當就緒程序數大于處理器數時，就必須按照某種政策來進行程序排程，以決定程序占用處理器的次序。這裡模拟設計一個在單處理器情況下的程序排程，按照優先級排程算法實作程序排程。

1.程序控制塊及隊列

假設有五個程序p1, p2, p3, p4, p5。程序的狀态有就緒态（READY）、運作态（RUN）、完成态（FINISH）。每個程序的初始态都為READY。當一個程序運作結束後，它的狀态為FINISH。

初始化是為每個程序确定他的優先級和要求運作時間，且按給定的優先級從高到低鍊成隊列，用一單元指出對首程序，程序狀态都為READY。

2.程序的運作

每次總是選擇隊首程序運作。可以采用動态改變優先級的辦法，程序沒運作一次就把優先級和要求運作時間減一。由于這是模拟程序排程，是以被選中運作的程序不必完成複雜的特定功能，而可以執行：

          優先級 - 1

          要求運作時間 - 1

來模拟程序的一次運作。

要提醒注意的是：在實際的系統中，當一個程序被選中運作時，必須回複程序現場，讓它來占用處理器，知道等待時間或運作結束。這裡省去了這些工作。

某程序的一次模拟運作結束後，若它的要求運作時間！=0，則需按照優先級從高到低調整隊列。若它的要求運作時間=0，則撤銷該程序，即把他的狀态修改為FINISH，且退出隊列。

若程序隊列不為空，則再從首選程序運作，直到所有程序都運作結束。

具體的參考代碼如下所示（由于涉及到作業系統底層的東西，是以采用C++或C編寫比較友善）

#include<iostream> using namespace std; typedef struct node {          char name[10];                                     // 程序名          int priority;                                   // 優先級          int cputime;                                 // 占用CPU時間          int needtime;                               // 到完成還要的時間          char state;                                             // 狀态          struct node *next; }PCB; PCB *finish, *ready, *run, *tail; // 初始化程序 void init() {          run = ready;          run->state = 'R';          ready = ready->next; } void print1() {          cout << endl;          cout << "程序名 占用CPU時間 到完成還要的時間 優先級   狀态" << endl; } void print2(PCB *q) {          cout << q->name << "/t/t" << q->cputime << "/t/t" << q->needtime << "/t" << q->priority << "/t" << q->state <<endl; } // 輸出結果 void print() {          PCB *p;          print1();          if(run != NULL)          print2(run);          p = ready;          while(p != NULL)          {                    print2(p);                    p = p->next;          }          p = finish;          while(p != NULL)          {                    print2(p);                    p = p->next;          }          getchar();                                     // 利用getchar()函數讓程式調試運作結束後等待使用者按下Enter鍵才傳回編輯界面 } // 插入程序 void insert(PCB *q) {          PCB *p1,*s,*r;          int b;          s = q;          p1 = ready;          r = p1;          b = 1;          while((p1 != NULL) && b)          {                    if(p1->priority >= s->priority)                    {                             r = p1;                             p1 = p1->next;                    }                    else                             b = 0;          }          if(r != p1)          {                    r->next = s;                    s->next = p1;          }          else          {                    s->next = p1;                    ready = s;          } } // 建立程序 void create(int n) {          PCB *p;          int i, time, priority;          char na[10];          ready = NULL;          finish = NULL;          run = NULL;          cout << "輸入程序名及其需要運作的時間和優先級:" << endl;          for(i = 1; i <= n; i++)          {                    p = new PCB;                    cin >> na;                    cin >> time;                    cin >> priority;                    strcpy(p->name, na);                    p->cputime = 0;                    p->needtime = time;                    p->state = 'w';                    p->priority = priority;                    if(ready != NULL)                       insert(p);                    else                    {                             p->next = ready;                             ready = p;                    }                    cout<<"輸入程序名及其需要運作的時間和優先級:"<<endl;          }          print();          run = ready;          ready = ready->next;          run->state = 'R'; } // 處理程序 void process() {          while(run != NULL)          {                    run->cputime = run->cputime + 1;                    run->needtime = run->needtime - 1;                    run->priority = run->priority - 1;                    if(run->needtime == 0)                    {                             run->next = finish;                             finish = run;                             run->state = 'F';                             run = NULL;                             if(ready != NULL)                                      init();                    }                    else                             if((ready != NULL) && (run->priority < ready->priority))                             {                                      run->state = 'W';                                      insert(run);                                      init();                              }             print();          } } void main() {          int n;          cout << "輸入程序的個數:";          cin >> n;          create(n);          process(); }

3.顯示或列印執行情況

在所設計的程式中，應有顯示或列印語句，能顯示或列印每次被選中的程序名，運作一次後各程序控制塊以及程序隊列的變化。