目錄

• 1.題目
• 2.程序設(shè)計(jì)
• 3.測(cè)試結(jié)果
• 4.源碼

1.題目

多級(jí)隊(duì)列調(diào)度算法
設(shè)RQ(就緒隊(duì)列)分為RQ1和RQ2，RQ1采用輪轉(zhuǎn)法，時(shí)間q=7.RQ1>RQ2，RQ2采用短進(jìn)程優(yōu)先調(diào)度算法。測(cè)試數(shù)據(jù)如下：RQ1: P1-P5, RQ2: P6-P10　
進(jìn)程 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
運(yùn)行時(shí)間 16 11 14 13 15 21 18 10 7 14
已等待時(shí)間 6 5 4 3 2 1 2 3 4 5
實(shí)現(xiàn)描述：

typedef struct tag_pcb{ char name[8];int need;//須運(yùn)行的時(shí)間int turn;//周轉(zhuǎn)時(shí)間(周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間)struct tag_pcb *next;}PCB(進(jìn)程控制塊); PCB * RQ1,*RQ2，*Finish; int clock=0; //時(shí)鐘 main() { 輸入RQ1；輸入RQ2；（最好從文件讀入）while（ＲＱ１！＝ＮＵＬＬ）  ｛ 從RQ1中選取一進(jìn)程Pi準(zhǔn)備運(yùn)行；計(jì)算其運(yùn)行的時(shí)間t;clock+=t; //表示Pi運(yùn)行t;if (Pi完成） 計(jì)算其turn;否則 Pi加入到隊(duì)尾；}while（ＲＱ2!＝ＮＵＬＬ）{ 從RQ2中選取一進(jìn)程Pi準(zhǔn)備運(yùn)行；clock+=Pi.need;計(jì)算Pi的turn;}輸出進(jìn)程的周轉(zhuǎn)時(shí)間； }

2.程序設(shè)計(jì)

• 首先在頭文件里面包含list.h，使得程序可以使用鏈表的各個(gè)操作函數(shù)。然后就是設(shè)立一個(gè)進(jìn)程信息結(jié)構(gòu)體，其中包括進(jìn)程名字、須運(yùn)行時(shí)間、開始運(yùn)行時(shí)間等進(jìn)程信息，接著就是利用list RQ1和list RQ2聲明兩個(gè)就緒隊(duì)列RQ1和RQ2，并設(shè)置系統(tǒng)時(shí)間和輪轉(zhuǎn)法的時(shí)間片。接著就是RQ1和RQ2的初始化，由于兩者基本一樣，所以只介紹RQ1的：首先初始化已知的進(jìn)程信息，然后利用for循環(huán)以及RQ1.push_back(project1)依次將所有屬于該隊(duì)列的進(jìn)程信息輸入至鏈表，并cout部分進(jìn)程信息。
• 然后就是輪轉(zhuǎn)法的定義：首先調(diào)用函數(shù)CreateRQ1()創(chuàng)建隊(duì)列，初始化時(shí)鐘之后當(dāng)RQ1不空時(shí)，PCB* p=&RQ1.front();//指向第一個(gè)元素，先輸出進(jìn)程部分信息，當(dāng)進(jìn)程執(zhí)行時(shí)間大于時(shí)間片時(shí)，調(diào)整系統(tǒng)時(shí)間、程序還需時(shí)間、程序已執(zhí)行時(shí)間以及執(zhí)行次數(shù)，而執(zhí)行次數(shù)主要目的是用來設(shè)立進(jìn)程最初開始執(zhí)行時(shí)間(p->count)++;if (p->count == 1){p->first_starttime = p->starttime;}，然后再輸出執(zhí)行次數(shù)以及已執(zhí)行時(shí)間，由于該進(jìn)程還未執(zhí)行完成，所以利用RQ1.push_back(RQ1.front());RQ1.pop_front()首先將其插入至隊(duì)列尾部，然后再刪除頭結(jié)點(diǎn)；若進(jìn)程所需時(shí)間小與等于時(shí)間片，則進(jìn)行各個(gè)進(jìn)程信息的更新之后直接利用RQ1.pop_front();//刪除頭結(jié)點(diǎn)，至此，輪轉(zhuǎn)法算法結(jié)束。
• 接下來就是短進(jìn)程優(yōu)先算法：同樣的先創(chuàng)建隊(duì)列，當(dāng)！RQ2.empty()時(shí)，std::
  list::iterator q=RQ2.begin();//迭代器iterator提供一種訪問對(duì)象容器中的元素，返回第一個(gè)元素的迭代器，然后利用循環(huán)for (std::list::iterator p = RQ2.begin();p != RQ2.end();++p) 找到最短預(yù)計(jì)執(zhí)行時(shí)間的進(jìn)程，找到之后再對(duì)進(jìn)程的部分信息更新，然后由于該進(jìn)程已執(zhí)行完，所以直接利用RQ2.erase(q)從隊(duì)列刪除結(jié)點(diǎn)q，短進(jìn)程優(yōu)先算法結(jié)束。
• 程序最后在main函數(shù)里面直接依次調(diào)用RR();//輪轉(zhuǎn)法、SPPSM();//短進(jìn)程優(yōu)先調(diào)度法即可，整個(gè)程序結(jié)束。

3.測(cè)試結(jié)果

4.源碼

/*操作系統(tǒng)實(shí)驗(yàn)一 多級(jí)隊(duì)列調(diào)度算法　 設(shè)RQ(就緒隊(duì)列)分為Q1 > RQ2，RQ2采用短進(jìn)程優(yōu)先調(diào)度算法。 測(cè)試數(shù)據(jù)如下：RQRQ1和RQ2，RQ1采用輪轉(zhuǎn)法，時(shí)間q = 7. R1: P1 - P5, RQ2 : P6 - P10　 進(jìn)程 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 運(yùn)行時(shí)間 16 11 14 13 15 21 18 10 7 14 已等待時(shí)間 6 5 4 3 2 1 2 3 4 5 */#include<iostream> #include<list>//包含雙向鏈表的各個(gè)操作函數(shù) using namespace std;struct PCB//進(jìn)程信息 {int name; //進(jìn)程名字int needtime; //須運(yùn)行時(shí)間int starttime; //開始運(yùn)行時(shí)間int endtime; //結(jié)束時(shí)間int first_starttime;//第一次開始運(yùn)行時(shí)間(用來計(jì)算周轉(zhuǎn)時(shí)間)int runtime; //已經(jīng)運(yùn)行時(shí)間int waittime; //已等待時(shí)間int count; //運(yùn)行次數(shù) };list<PCB> RQ1; list<PCB> RQ2; int clock; //系統(tǒng)時(shí)間 int capacity = 7;//時(shí)間片void CreateRQ1()//創(chuàng)建隊(duì)列RQ1(以隊(duì)列為結(jié)構(gòu)創(chuàng)建) {int name1[5] = { 1,2,3,4,5 };int needtime1[5] = { 16,11,14,13,15 };int waittime1[5] = { 6,5,4,3,2 };for (int i = 0;i < 5;i++){PCB project1;project1.name = name1[i];project1.waittime = waittime1[i];project1.needtime = needtime1[i];project1.runtime = 0;project1.count = 0;project1.endtime = 0;project1.first_starttime = 0;project1.starttime = 0;RQ1.push_back(project1);//放進(jìn)鏈表cout << "創(chuàng)建進(jìn)程 : p"<<project1.name<<"\t"<<"執(zhí)行所需時(shí)間 : "<<project1.needtime<<endl;} }void CreateRQ2()//創(chuàng)建隊(duì)列RQ2(以鏈表為結(jié)構(gòu)創(chuàng)建) {int name2[5] = { 6,7,8,9,10 };int needtime2[5] = { 21,18,10,7,14 };int waittime2[5] = { 1,2,3,4,5 };for (int i = 0;i < 5;i++){PCB project2;project2.name = name2[i];project2.waittime = waittime2[i];project2.needtime = needtime2[i];project2.runtime = 0;project2.count = 0;project2.endtime = 0;project2.first_starttime = 0;project2.starttime = 0;RQ2.push_back(project2);cout << "創(chuàng)建進(jìn)程 : p" << project2.name << "\t" << "執(zhí)行所需時(shí)間 : " << project2.needtime << endl;} }void RR()//輪轉(zhuǎn)法(round-robin) {cout << "***********輪轉(zhuǎn)法***********"<<endl;CreateRQ1();clock = 0;while (!RQ1.empty()){PCB* p = &RQ1.front();//指向第一個(gè)元素p->starttime = clock;cout << "進(jìn)程 : p" << p->name << "\t" << "執(zhí)行還需時(shí)間 : "<< p->needtime << "\t" << "開始執(zhí)行時(shí)間 : " << p->starttime <<"\t";if (p->needtime > capacity){clock += capacity;p->needtime -= capacity;p->runtime += capacity;(p->count)++;if (p->count == 1){p->first_starttime = p->starttime;}cout << "執(zhí)行次數(shù) ：" << p->count << "\t" << "已執(zhí)行時(shí)間 : " << p->runtime << endl;RQ1.push_back(RQ1.front());//首先插入頭結(jié)點(diǎn)到尾部RQ1.pop_front(); //然后把頭結(jié)點(diǎn)刪除}else{p->runtime += p->needtime;clock += p->needtime;p->endtime = clock;(p->count)++;cout << "執(zhí)行次數(shù) : " << p->count << "\t" << "已執(zhí)行時(shí)間 : " << p->runtime<< "\t" << "結(jié)束時(shí)間 : " << p->endtime <<"\t"<< "周轉(zhuǎn)時(shí)間 : " << p->endtime - p->first_starttime <<"\t"<< "執(zhí)行完畢" <<endl;p->needtime = 0;RQ1.pop_front();//刪除頭結(jié)點(diǎn)}}cout << endl; }void SPPSM()//短進(jìn)程優(yōu)先調(diào)度法(short process priority scheduling method) {cout << "*******短進(jìn)程優(yōu)先調(diào)度法*******"<<endl;CreateRQ2();clock = 0;while (!RQ2.empty()){std::list<PCB>::iterator q = RQ2.begin();//迭代器iterator提供一種訪問對(duì)象容器中的元素，返回第一個(gè)元素的迭代器for (std::list<PCB>::iterator p = RQ2.begin();p != RQ2.end();++p){ //找到最短預(yù)計(jì)執(zhí)行時(shí)間的進(jìn)程if (p->needtime < q->needtime){q = p;}}q->starttime = clock;q->endtime = clock + q->needtime;clock = q->endtime;cout<< "進(jìn)程 : p" << q->name << "\t" << "執(zhí)行所需時(shí)間 : " << q->needtime << "\t"<< "開始執(zhí)行時(shí)間 : " << q->starttime << "\t" << "結(jié)束時(shí)間 : " << q->endtime <<"\t"<<"周轉(zhuǎn)時(shí)間 : "<< q->endtime - q->starttime<<endl;RQ2.erase(q);//刪除節(jié)點(diǎn)q} }int main(void) {RR();//輪轉(zhuǎn)法SPPSM();//短進(jìn)程優(yōu)先調(diào)度法return 0; }

總結(jié)

以上是生活随笔為你收集整理的多级队列调度算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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