搶占式優(yōu)先級調(diào)度算法是什么意思

系統(tǒng)把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程(原優(yōu)先權(quán)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。

本教程操作環(huán)境：windows7系統(tǒng)、C++17版本、Dell G3電腦。

搶占式優(yōu)先權(quán)調(diào)度算法

在這種方式下，系統(tǒng)把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程(原優(yōu)先權(quán)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。因此，在采用這種調(diào)度算法時，是每當系統(tǒng)中出現(xiàn)一個新的就緒進程i 時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進程j 的優(yōu)先權(quán)Pj進行比較。如果Pi≤Pj，原進程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進程切換，使i 進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。

具體代碼：

#include <iostream>#include <string>#include <vector>using namespace std;using std::cout;struct PCB {    // 進程名     string name;    // 到達時間     int arrivetime;    // 運行時間     int runtime;                     // 仍需運行時間     int resttime;    // 開始時間     int starttime;    // 完成時間     int endtime;    // 運行次數(shù)     int runcount;    // 周轉(zhuǎn)時間     int zhouzhuangtime;    // 帶權(quán)周轉(zhuǎn)時間（周轉(zhuǎn)時間/運行時間)     double weightzhouzhuangtime;    // 優(yōu)先級（靜態(tài)）     int priority;      PCB *next; };// 進程數(shù)int num_process;// 記錄所有進程的總時間int totaltime;// 記錄所有進程的總帶權(quán)周轉(zhuǎn)時間double weighttotaltime;  PCB *createPCB() {    int i;    // 定義隊首、隊尾     PCB *head, *rear;    // 初始化     head = rear = NULL;    // 臨時指針變量     PCB *p;    cout<<"請輸入進程數(shù)量：";    cin>>num_process;    for(i = 0; i < num_process; i++)     {        // 初始化一個空間給進程         p = new PCB;        cout<<"請依次輸入第"<<i+1<<"個進程的信息（進程名、優(yōu)先級、到達時間、運行時間）："<<endl;        cin>>p->name>>p->priority>>p->arrivetime>>p->runtime;         p->resttime = p->runtime;         p->runcount = 1;         totaltime += p->runtime;         p->starttime = 0;         p->endtime = 0;         p->zhouzhuangtime = 0;         p->weightzhouzhuangtime = 0;         p->next = NULL;        // 存入鏈表中         if(rear == NULL)         {             head = p;             rear = p;         }        else         {             rear->next = p;             rear = p;         }      }    return head; }// 鏈表插入排序PCB *insertSort(PCB *head) {    /*         1、先在原鏈表中以第一個節(jié)點為一個有序鏈表，其余節(jié)點為待定節(jié)點；         2、從待定節(jié)點中取節(jié)點，插入到有序鏈表中相應(yīng)位置；         3、實際上只有一條鏈表，在排序中，實際只增加了一個用于指向剩下需要排序節(jié)點的頭指針。     */     PCB *first;// 為原鏈表剩下用于直接插入排序的節(jié)點頭指針     PCB *t; // 臨時指針變量：要插入的節(jié)點     PCB *p; // 臨時指針變量：要插入的位置     PCB *q; // 臨時指針變量：指向原鏈表      first = head->next;     head->next = NULL; // 只含有一個節(jié)點的鏈表的有序鏈表      while(first != NULL) // 遍歷剩下的無序鏈表     {        // 無序節(jié)點在有序鏈表中找插入位置p         for(t = first, q = head; (q != NULL) && (q->arrivetime < t->arrivetime); p = q, q = q->next);        // 無序鏈表中的節(jié)點離開，以便插入到有序鏈表中         first = first->next;        if(q == head)// 插入在第一個節(jié)點之前         {             head = t;         }        else// p是q的前驅(qū)         {             p->next = t;         }         t->next = q;// 完成插入動作     }    return head; }// 獲取當前時間段內(nèi)的進程數(shù)量int getCurrentNumOfProcess(PCB *head, int time) {    int count = 0;     PCB *t;// 臨時指針變量，指向鏈表     t = head;    while(t != NULL && t->arrivetime <= time)     {         count++;         t = t->next;     }    return count; }// 刪除當前節(jié)點PCB* deletePCB(PCB *head, PCB *t) {     PCB *p, *q;     p = head;     q = p->next;    // 刪除節(jié)點是頭節(jié)點     if(t == head)     {         head = head->next;     }    else      {        while(q != t)// 跳出循環(huán)之后q為該節(jié)點，p為前一節(jié)點         {             p = p->next;             q = p->next;         }        if(t->next == NULL)// 刪除節(jié)點是尾節(jié)點             p->next = NULL;        else             p->next = q->next;     }    // 刪除     free(t);    return head; }// 在頭節(jié)點后的count個節(jié)點中選擇優(yōu)先數(shù)最大的返回PCB *findMaxPriority(PCB *head, int count) {    int max;     PCB *p, *q, *f;     q = head;     max = q->priority;     f = q;    while(count > 0)     {        if(q->priority > max)         {             max = q->priority;             f = q;         }         count--;         q =q->next;     }    return f;  }/*      輸出a時間內(nèi)的特定輸出格式,當某一時間段內(nèi)沒有進程工作時，進程名稱為0     進程名稱.進程工作時間，進程與進程間以|分隔     輸入：1 3 2 8           2 2 1 7           3 6 3 12     輸出：[0.1|2.1|1.1|3.12|1.7|2.6|0.172] */void print(vector<PCB> vec_output, int a) {    for(int i = 0; i < vec_output.size(); i++)     {        cout<<"******************************************"<<endl;        cout<<"進程名："<<vec_output[i].name<<endl;        cout<<"到達時間："<<vec_output[i].arrivetime<<endl;        cout<<"開始運行時間: "<<vec_output[i].starttime<<endl;        cout<<"結(jié)束運行時間: "<<vec_output[i].endtime<<endl;        cout<<"此次運行時間："<<vec_output[i].endtime - vec_output[i].starttime<<endl;        cout<<"******************************************"<<endl;        cout<<endl;        cout<<endl;     }    // 輸出周轉(zhuǎn)時間信息,只有進程結(jié)束了才輸出     int i;    for(i = 0; i < vec_output.size()-1; i++)     {        bool flag = true;        for(int j = i+1; j < vec_output.size(); j++)         {            if(vec_output[j].name == vec_output[i].name)             {                 flag = false;                break;             }         }        if(flag)         {            cout<<"進程"<<vec_output[i].name<<"的周轉(zhuǎn)時間為："<<vec_output[i].zhouzhuangtime<<endl;            cout<<"進程"<<vec_output[i].name<<"的帶權(quán)周轉(zhuǎn)時間為: "<<vec_output[i].weightzhouzhuangtime<<endl;            cout<<endl;            cout<<endl;         }     }    cout<<"進程"<<vec_output[i].name<<"的周轉(zhuǎn)時間為："<<vec_output[i].zhouzhuangtime<<endl;    cout<<"進程"<<vec_output[i].name<<"的帶權(quán)周轉(zhuǎn)時間為: "<<vec_output[i].weightzhouzhuangtime<<endl;    cout<<endl;    cout<<endl;    // 輸出平均周轉(zhuǎn)時間信息     cout<<"平均周轉(zhuǎn)時間："<<totaltime/(double)num_process<<endl;    cout<<"平均帶權(quán)周轉(zhuǎn)時間："<<weighttotaltime/(double)num_process<<endl;    cout<<endl;    cout<<endl;    cout<<a<<"個時間單位內(nèi)的執(zhí)行順序為："<<endl;    cout<<"[";    if(vec_output[0].starttime > 0)     {        cout<<"0."<<vec_output[0].starttime<<"|";     }    if(vec_output[vec_output.size() - 1].endtime < a)     {        for(int i = 0; i < vec_output.size(); i++)         {            cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";            // 補全從開始到結(jié)束之間沒有進程運行項             if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)             {                cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";             }         }        cout<<"0."<<a-vec_output[vec_output.size()-1].endtime<<"]"<<endl;     }    else if(vec_output[vec_output.size() - 1].endtime == a)     {        for(int i = 0; i < vec_output.size()-1; i++)         {            cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";            // 補全從開始到結(jié)束之間沒有進程運行項             if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)             {                cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";             }         }        cout<<vec_output[vec_output.size()-1].name<<"."<<vec_output[vec_output.size()-1].endtime - vec_output[vec_output.size()-1].starttime<<"]"<<endl;     }    else     {        for(int i = 0; i < vec_output.size(); i++)         {            if(vec_output[i].endtime <= a)             {                cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";                // 補全從開始到結(jié)束之間沒有進程運行項                 if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)                 {                    cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";                 }             }            else             {                cout<<vec_output[i].name<<"."<<a - vec_output[i].starttime<<"]"<<endl;                return;             }         }     } }void PCB_MAIN(PCB *head) {     head = insertSort(head);    int time = 0;// 模擬時間變量     int count;// 當前時間內(nèi)運行的進程數(shù)量     PCB *q;    vector<PCB> vec_out;//輸出     PCB temp;    while(head != NULL)     {         count = getCurrentNumOfProcess(head, time);        if(count == 0)             time++;        else         {            /************************************************************************/             /* 搶占式                                                               */             /************************************************************************/             // 找出優(yōu)先數(shù)最大的線程             q = findMaxPriority(head, count);            if(q->runcount == 1)// 該進程第一次運行             {                 q->starttime = time;                // 輸出信息                 temp = *q;                 temp.endtime = 0;                 temp.next = NULL;                if(vec_out.size() != 0 && vec_out[vec_out.size()-1].endtime == 0)                 {                     vec_out[vec_out.size()-1].endtime = temp.starttime;                 }                 vec_out.push_back(temp);             }             ++time;             ++q->runcount;             --q->resttime;            if(q->resttime == 0)// 該進程運行結(jié)束             {                // 記錄結(jié)束時間                 q->endtime = time;                // 計算周轉(zhuǎn)時間                 q->zhouzhuangtime = time - q->arrivetime;                // 計算帶權(quán)周轉(zhuǎn)時間                 q->weightzhouzhuangtime = q->zhouzhuangtime/(double)q->runtime;                 weighttotaltime += q->weightzhouzhuangtime;                // 輸出信息                 temp = *q;                 temp.starttime = 0;                 temp.next = NULL;                if(vec_out[vec_out.size()-1].name == temp.name)                 {                     vec_out[vec_out.size()-1].endtime = temp.endtime;                     vec_out[vec_out.size()-1].zhouzhuangtime = temp.zhouzhuangtime;                     vec_out[vec_out.size()-1].weightzhouzhuangtime = temp.weightzhouzhuangtime;                 }                else                 {                     temp.starttime = vec_out[vec_out.size()-1].endtime;                     vec_out.push_back(temp);                 }                // 刪除該進程                 //deletePCB(q);                 head = deletePCB(head, q);             }         }     }    // 輸出200時間單位內(nèi)的執(zhí)行順序     print(vec_out, 200); }int main() {     PCB *head = NULL;     head = createPCB();     PCB_MAIN(head);    return 0; }

輸出實例

輸入：

輸出：

推薦教程：《C#》