文章目錄

• • 實驗原理
  • 算法流程
  • 數(shù)據(jù)結(jié)構(gòu)
  • PSA算法思路
  • 完整代碼
  • 測試
  • • 測試代碼
    • 測試數(shù)據(jù)
    • 測試結(jié)果

---

實驗原理

(1) 假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：

其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為P1，P2，P3，P4，P5。
指針——按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。
要求運(yùn)行時間——假設(shè)進(jìn)程需要運(yùn)行的單位時間數(shù)。
優(yōu)先數(shù)——賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。
狀態(tài)——可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。

(2) 在每次運(yùn)行你所設(shè)計的處理器調(diào)度程序之前，為每個進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運(yùn)行時間”。

(3) 為了調(diào)度方便，把五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊列。用一單元指出隊首進(jìn)程，用指針指出隊列的連接情況。

(4) 處理器調(diào)度總是選隊首進(jìn)程運(yùn)行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)就減“1”。由于本實驗是模擬處理器調(diào)度，所以，對被選中的進(jìn)程并不實際的啟動運(yùn)行，而是執(zhí)行：
優(yōu)先數(shù)-1
要求運(yùn)行時間-1
來模擬進(jìn)程的一次運(yùn)行。
提醒注意的是：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運(yùn)行時，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作。

(5) 進(jìn)程運(yùn)行一次后，若要求運(yùn)行時間0，則再將它加入隊列（按優(yōu)先數(shù)大小插入，且置隊首標(biāo)志）；若要求運(yùn)行時間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊列。

(6) 若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。

(7) 在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊列的變化。

(8) 為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。

---

算法流程

首先了解了實驗的原理后，接下來就需要開始規(guī)劃流程。

---

數(shù)據(jù)結(jié)構(gòu)

下面開始數(shù)據(jù)結(jié)構(gòu)的選取，因為這里只需要模擬進(jìn)程的操作，所以只需要用一個PCB類對象就行。
需要具備進(jìn)程名、運(yùn)行時間、當(dāng)前狀態(tài)、優(yōu)先數(shù)等屬性，同時還需要開放給外界運(yùn)行的接口以及判斷是否退出的接口。

class PCB { public:friend class List;friend void PSA(List& q);PCB(std::string processName, size_t time, size_t priority, size_t order): _processName(processName), _time(time), _priority(priority), _status('R'), _order(order){}//運(yùn)行進(jìn)程void Run(){std::cout << "---進(jìn)程" << _processName << "正在運(yùn)行---" << std::endl;//模擬運(yùn)行，每運(yùn)行一次優(yōu)先數(shù)和剩余運(yùn)行時間減一--_priority;--_time;//運(yùn)行時間已滿，修改狀態(tài)為結(jié)束if (!_time){_status = 'E';}std::cout << "進(jìn)程名: " << _processName << " 優(yōu)先級: " << _priority << " 剩余運(yùn)行時間: " << _time << " 狀態(tài): " << _status << std::endl;std::cout << "---進(jìn)程" << _processName << "運(yùn)行結(jié)束---" << std::endl;std::cout << std::endl;}//判斷當(dāng)前狀態(tài)是否結(jié)束bool isEnd() const{return (_status == 'E');}private:std::string _processName; //進(jìn)程名size_t _time; //運(yùn)行時間int _priority; //優(yōu)先數(shù)char _status; //狀態(tài)size_t _order; //順序 };

同時，我采用C++ STL庫中的鏈表來實現(xiàn)隊列，為其重寫了push函數(shù)，讓他能夠按照優(yōu)先級插入隊列

class List { public:friend void PSA(List& q);void Push(const PCB& data){auto it = _list.begin();while (it != _list.end()){//按照先后順序以及優(yōu)先級大小插入到合適的位置if (data._priority > it->_priority || ((data._priority == it->_priority) && (data._order < it->_order))){_list.insert(it, data);return;}else{it++;}}//如果比前面的都小就尾插_list.push_back(data); }//輸出表中所有進(jìn)程信息void Print() const{std::cout << "--------------------------------" << std::endl;for (auto it = _list.begin(); it != _list.end(); it++){std::cout << "進(jìn)程名: " << it->_processName << " 優(yōu)先級: " << it->_priority << " 剩余運(yùn)行時間: " << it->_time << " 狀態(tài): " << it->_status << std::endl;}std::cout << "--------------------------------" << std::endl;std::cout << std::endl;}private:std::list<PCB> _list; };

PSA算法思路

這個算法其實思路非常簡單，每次只需要取出隊首進(jìn)行調(diào)度，如果調(diào)度結(jié)束后剩余運(yùn)行時間為0則說明該進(jìn)程運(yùn)行結(jié)束，永久出隊，如果不為0則說明還沒運(yùn)行完成，再次按優(yōu)先級插入隊列中即可，因為上面重寫了Push函數(shù)，所以直接Push回去即可。如果隊列為空，則說明所有的進(jìn)程調(diào)度完畢。

void PSA(List& q) {while (!q._list.empty()){//取出隊首運(yùn)行auto cur = q._list.front();cur.Run();q._list.pop_front();//如果還沒運(yùn)行完則重新放入表中if (!cur.isEnd()){q.Push(cur);}else{std::cout << "進(jìn)程" << cur._processName << "運(yùn)行結(jié)束， 退出" << std::endl;}q.Print();}std::cout << "************調(diào)度結(jié)束************" << std::endl; }

完整代碼

#pragma #include <string> #include <iostream> #include <list> class List; class PCB { public:friend class List;friend void PSA(List& q);PCB(std::string processName, size_t time, size_t priority, size_t order): _processName(processName), _time(time), _priority(priority), _status('R'), _order(order){}//運(yùn)行進(jìn)程void Run(){std::cout << "---進(jìn)程" << _processName << "正在運(yùn)行---" << std::endl;--_priority;--_time;if (!_time){_status = 'E';}std::cout << "進(jìn)程名: " << _processName << " 優(yōu)先級: " << _priority << " 剩余運(yùn)行時間: " << _time << " 狀態(tài): " << _status << std::endl;std::cout << "---進(jìn)程" << _processName << "運(yùn)行結(jié)束---" << std::endl;std::cout << std::endl;}//判斷當(dāng)前狀態(tài)是否結(jié)束bool isEnd() const{return (_status == 'E');}private:std::string _processName; //進(jìn)程名size_t _time; //運(yùn)行時間int _priority; //優(yōu)先數(shù)char _status; //狀態(tài)size_t _order; //順序 };class List { public:friend void PSA(List& q);void Push(const PCB& data){auto it = _list.begin();while (it != _list.end()){//按照先后順序以及優(yōu)先級大小插入到合適的位置if (data._priority > it->_priority || ((data._priority == it->_priority) && (data._order < it->_order))){_list.insert(it, data);return;}else{it++;}}//如果比前面的都小就尾插_list.push_back(data); }//輸出表中所有進(jìn)程信息void Print() const{std::cout << "--------------------------------" << std::endl;for (auto it = _list.begin(); it != _list.end(); it++){std::cout << "進(jìn)程名: " << it->_processName << " 優(yōu)先級: " << it->_priority << " 剩余運(yùn)行時間: " << it->_time << " 狀態(tài): " << it->_status << std::endl;}std::cout << "--------------------------------" << std::endl;std::cout << std::endl;}private:std::list<PCB> _list; };void PSA(List& q) {while (!q._list.empty()){//取出隊首運(yùn)行auto cur = q._list.front();cur.Run();q._list.pop_front();//如果還沒運(yùn)行完則重新放入表中if (!cur.isEnd()){q.Push(cur);}else{std::cout << "進(jìn)程" << cur._processName << "運(yùn)行結(jié)束， 退出" << std::endl;}q.Print();}std::cout << "************調(diào)度結(jié)束************" << std::endl; }

測試

測試代碼

#include"PSA.hpp" #include<vector> using namespace std;void test() {List List;size_t pcbNum;cout << "請輸入進(jìn)程的數(shù)量:" << endl;cin >> pcbNum;vector<string> processName(pcbNum);vector<size_t> time(pcbNum);vector<int> priority(pcbNum);cout << "請輸入所有進(jìn)程的名字:" << endl;for (size_t i = 0; i < pcbNum; i++){cin >> processName[i];}for (size_t i = 0; i < pcbNum; i++){cout << "請輸入進(jìn)程" << processName[i] << "的運(yùn)行時間" << endl;cin >> time[i];cout << "請輸入進(jìn)程" << processName[i] << "的優(yōu)先級" << endl;cin >> priority[i];PCB p(processName[i], time[i], priority[i], i);List.Push(p);}List.Print();PSA(List); }int main() {test(); }

測試數(shù)據(jù)

這里直接用實驗要求中的數(shù)據(jù)，五個進(jìn)程，P1、P2、P3、P4、P5。
P1的要求運(yùn)行時間為2，優(yōu)先數(shù)為1。
P2的要求運(yùn)行時間為3，優(yōu)先數(shù)為5。
P3的要求運(yùn)行時間為1，優(yōu)先數(shù)為3。
P4的要求運(yùn)行時間為2，優(yōu)先數(shù)為4。
P5的要求運(yùn)行時間為4，優(yōu)先數(shù)為2。

測試結(jié)果

總結(jié)

以上是生活随笔為你收集整理的操作系统 : 按优先数调度算法实现处理器调度（C++）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。