操作系统-进程调度模拟算法(附源码).doc

进程调度模拟算法
课程名称：计算机操作系统 　　 　 　 　 班级:信１501-2
实验者姓名:李琛 　 　 　 　 　 　 　 实验日期:2０1８年5月１日
评分: 　　 　 　 　 　 　　 　　 　 教师签名:
一、实验目得
进程调度就是处理机管理得核心内容。本实验要求用高级语言编写模拟进程调度程序，以 便加深理解有关进程控制快、进程队列等概念,并体会与了解优先数算法与时间片轮转算法　得具体实施办法。
二、实验要求
1、设计进程控制块　ＰCB 得结构,通常应包括如下信息:
进程名、进程优先数(或轮转时间片数）、进程已占用得 CPU　时间、进程到完成还需要得时间、进程得状态、当前队列指针等。
2、编写两种调度算法程序:
优先数调度算法程序
循环轮转调度算法程序
3、按要求输出结果。
三、实验过程
分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态(ＲＵＮ)、
就绪状态（REAＤY,包括等待状态）与完成状态(ＦＩNIＳH),并假定初始状态为就绪状态。
(一)进程控制块结构如下：
NAME——进程标示符
PＲIＯ／ＲOUND——进程优先数/进程每次轮转得时间片数(设为常数 2）
　ＣPＵTIＭE——进程累计占用 CPU　得时间片数
NEEDＴIＭE——进程到完成还需要得时间片数
STＡTE——进程状态
NＥXT——链指针
注:
1、为了便于处理，程序中进程得得运行时间以时间片为单位进行计算;
　2、各进程得优先数或轮转时间片数，以及进程运行时间片数得初值,均由用户在程序运行时给定。
（二)进程得就绪态与等待态均为链表结构,共有四个指针如下:
　RUN——当前运行进程指针
READY——就需队列头指针
　ＴAIL—— 就需队列尾指针
FIＮISH—— 完成队列头指针
（三)程序说明
１、 在优先数算法中,进程优先数得初值设为:
　５0-ＮEEＤTＩME
每执行一次,优先数减 １,CPU 时间片数加 1,进程还需要得时间片数减 1。在轮转法中,采用固定时间片单位(两个时间片为一个单位),进程每轮转一次，ＣPU时间片数加 2，进程还需要得时间片数减 2,并退出 CPＵ,排到就绪队列尾,等待下一次调度。
２、 程序得模块结构如下:
　整个程序可由主程序与如下 7 个过程组成：
２
　(1)INSERＴ1——在优先数算法中，将尚未完成得 ＰCＢ 按优先数顺序插入到就绪队列中;
　(２)IＮSEＲT2——在轮转法中,将执行了一个时间片单位(为　2),但尚未完成得进程
得 ＰＣB，插到就绪队列得队尾;
(3)FIRＳＴＩＮ——调度就绪队列得第一个进程投入运行；
(４)ＰRINT——显示每执行一次后所有进程得状态及有关信息。
　(5)CREATE——创建新进程，并将它得 ＰCＢ　插入就绪队列;
　（6)ＰＲISCH——按优先数算法调度进程;
(7)RＯＵNDＳCH——按时间片轮转法调度进程。
主程序定义 PCB 结构与其她有关变量。
实验代码:
Maiｎ、ｃｐp
＃iｎｃlude<ｉoｓtreａm>
＃ｉnclude<string>
using naｍeｓpａce　stｄ;
typedef ｓtrｕｃｔ　ｎｏde
{
chaｒ ｎaｍe[20]; 　 　　 　 //进程名
iｎt prio；　 　 　 　／/进程优先级
inｔ roｕnd; 　　 　 //分配CPU得时间片
ﻩinｔ　cpuｔimｅ; 　 　 　　　 　/／CPU执行时间
ﻩinｔ nｅedｔimｅ; 　 　 //进程执行所需时间
char state; 　 　 　 　　 　 ／／进程状态
int count; 　　 　　　 　//记录执行次数
ﻩsｔrｕct　noｄe *nexｔ; 　 /／链表指针
}PCB；
int nｕｍ；
/／定义三个队列,就绪队列,执行队列,完成队列
ＰCB ＊rｅadｙ　= NUＬL； //就绪队列
PＣB *rｕn =　NULL; 　 　 　 /／执行队列
ＰCB　*ｆinish = NULL; 　 //完成队列
/／取得第一个就绪节点
void GetFirsｔ()
｛
ruｎ = ready;
ﻩif （ready !＝　NULL)
{
run-＞sｔａｔe = 'R＇;
ｒｅａｄy = ｒｅadｙ－>neｘt;
ﻩ rｕn－>neｘt ＝　NUＬL;
ﻩ}
}
/／优先级输出队列
ｖoid Oｕtput1（)
｛
PCＢ *p；
ﻩｐ = rｅady；
while (ｐ != NＵLL)
｛
ﻩ ｃｏut << p－>nａmｅ <＜　"\t＂　<<　p-＞pｒio ＜<　＂\t" ＜< p->cpｕtiｍｅ ＜＜ "\t"　<<　p-＞neｅdtiｍe　<< "\t ＂　＜<　p-＞state << " \t " ＜< p->count　<< eｎdｌ；
ｐ ＝ ｐ－＞ｎｅｘt;
ﻩ}
ｐ = finiｓh;
ﻩwhile　（p　!＝ NUＬＬ)
{
ﻩ cout ＜< ｐ－>namｅ << "\t" << p->pｒio << ＂\t" <<　ｐ－>cputｉme　＜<　＂\ｔ＂ << p->nｅｅｄtime <<　"\t " ＜< ｐ－>state ＜＜　" \t "　<<　p->cｏｕnt << ｅnｄｌ;
p ＝ p->next;
}
ﻩp = run;
ﻩwｈile (p != NＵＬL)
｛
ｃout　<< p->ｎame ＜< "\t" <＜　p-＞prｉｏ ＜< "\t＂　＜<　p-＞cｐuｔimｅ　<<　＂\t" <<　p-＞ｎeｅdtime　<＜ ＂\t "　＜＜ p->staｔe << " ＼t　 ＂ <<　p-＞coｕnｔ　<< endl；
ﻩﻩp ＝　ｐ-＞next;
}
}
//轮转法输出队列
voiｄ Outpｕt2(）
｛
ＰCB　*p；
p = reａdy;
while　（ｐ != ＮＵLＬ)
ﻩ｛
ﻩcout << p->name << "\ｔ＂　<＜ p->round　<< "＼t" << p->cputimｅ << "＼t＂　<<　ｐ->needｔimｅ ＜< ＂＼t　" ＜< p->ｓtａte << "\t " << p-＞cｏunt　＜＜ ｅｎdl;
ﻩﻩｐ = p-＞nｅxt;
}
ﻩp = fｉnish;
ﻩwhilｅ (p != NULL）
ﻩ{
ﻩﻩcouｔ ＜＜　ｐ->nａmｅ << ＂\t" << p－>ｒound << "\ｔ"　<< p－＞cpｕtｉｍe << ＂\t"　＜< ｐ->ｎｅeｄtｉme ＜< "\t ＂　＜＜　p－>ｓtａte　<<　"\t " << p－>count <<　eｎｄl;
ﻩp = ｐ->next;
ﻩ}
ﻩp =　ruｎ;
wｈile (p ！= NUＬL)
ﻩ{
ﻩｃoｕt <<　p->naｍe << "\ｔ＂ ＜< p－＞ｒｏund << "\ｔ"　<＜ p-＞cpuｔime <＜ "＼ｔ" <<　p-＞nｅedtimｅ << "＼t " ＜< p->state << ＂＼ｔ　 " << p->cｏunｔ　<＜ ｅndl;
ﻩ p　= p－＞neｘｔ;
}
}
//创建优先级队列
//创建优先级队列,规定优先数越小,优先级越低
vｏid　InserｔPｒiｏ(PＣB *in)
{
ＰCＢ　*fst， *ｎxt;
fｓｔ = nxt =　rｅady;
ﻩif (ready　==　ＮULL)　 ／／如果队列为空，则为第一个元素　
｛
ﻩ in-＞next　=　ready;
ﻩready　＝ in；
ﻩ}
eｌsｅ 　 /／查到合适得位置进行插入　
{
ﻩﻩiｆ (iｎ－>prio ＞= fｓｔ->prｉo) //比第一个还要大,则插入到队头
ﻩ{
ｉn->neｘt　= readｙ;
ﻩrｅady = in;
ﻩ ｝
ﻩ elｓe
ﻩ ｛
ﻩ ﻩwhｉle (fｓt->next !＝ NＵＬL) 　//移动指针查找第一个比它小得元素得位置进行插入
ﻩ ﻩ｛
ﻩﻩ ﻩｎｘt ＝　fｓt;
ﻩ ﻩｆst　= fst-＞next;
ﻩﻩﻩ}
ﻩﻩif　（ｆsｔ-＞ｎｅxt ＝＝ ＮULＬ) ／/已经搜索到队尾,则其优先级数最小,将其插入到队尾即可　
ﻩ ﻩ{
ﻩ ﻩｉn->neｘt ＝ fst->ｎexｔ；
ﻩﻩﻩ fst－＞nｅｘt = in;
ﻩ }
ﻩﻩ elｓe　 　//插入到队列中
ﻩ ｛
ﻩﻩﻩ nxt = in;
ﻩ ﻩ ｉｎ->ｎext = fsｔ;
ﻩ }
}
ﻩ}
｝
//将进程插入到就绪队列尾部
ｖoｉｄ ＩnsｅrtTiｍe(PCB ＊in）
{
PCB *ｆｓt;
ﻩfsｔ =　ready;
ﻩiｆ　(ｒeady ==　NULL)
ﻩ｛
ﻩ in-＞next = rｅaｄy；
ﻩｒeａdy ＝　iｎ；
}
ｅlｓe
{
ﻩ while (fst－＞nexｔ != NULL)
ﻩ {
fｓt　= fst-＞next;
ﻩ}
ﻩiｎ－>next ＝ ｆｓｔ->next;
ﻩfst-＞nｅｘｔ =　ｉn;
｝
}
//将进程插入到完成队列尾部
vｏｉd InseｒtFiｎiｓh(ＰCB ＊ｉn)
｛
ﻩPCB *fsｔ;
ｆsｔ ＝ fｉｎｉsh；
if (fiｎｉsh　＝= NUＬＬ)
{
ﻩ in－>next = finish；
finiｓh = iｎ;
ﻩ}
ﻩelse
ﻩ{
ﻩﻩwhile (fst->nｅxｔ　!= NULL)
ﻩﻩ{
ﻩﻩfst = fst->nｅxt;
ﻩ }
ﻩ ｉn->nｅxt = fｓt-＞neｘｔ;
ﻩﻩｆｓt->next = in;
｝
}
//优先级调度输入函数
void　PrioCrｅatｅ(）
{
PCB ＊tｍｐ;
ﻩint ｉ;
ﻩcoｕt << "Ｅnter　tｈｅ ｎamｅ ａnｄ needｔiｍｅ："　＜< endｌ；
ﻩfoｒ (i　=　0; i ＜　num；　i++）
｛
iｆ ((tmｐ　= (PCB *)ｍaｌloc（siｚeof(PＣB))）　==　NULL)
ﻩ {
ceｒｒ << "ｍallｏc" ＜< ｅｎdl;
ﻩexit(1);
}
cin　＞>　tmｐ-＞nａmｅ；
ﻩ ｇetchaｒ(）;
ﻩﻩcin　>>　tmｐ-＞neｅdｔime;
ﻩﻩtmp－＞cpuｔime　= 0；
ﻩ ｔｍp－>ｓtate = 'Ｗ';
ﻩﻩtmp－>ｐrio =　5０ -　tmｐ－>nｅedｔｉme； //设置其优先级,需要得时间越多，优先级越低
ﻩ ｔmp-＞round　= 0；
ﻩ ｔｍp-＞couｎt = ０；
InsertPrｉo（tmp); 　//按照优先级从高到低，插入到就绪队列
ﻩ}
cｏｕｔ << "进程名＼t优先级\tcpu时间\ｔ需要时间 进程状态 计数器" ＜<　eｎdl;
}
/／时间片输入函数
void TimeＣrｅate()
{
ﻩＰCＢ　＊tmp;
int　i;
coｕｔ << "输入进程名字与进程时间片所需时间：" <<　endl;
ﻩfｏr　(i = 0;　i ＜ num;　ｉ++)
ﻩ{
ﻩｉf (（tmｐ =　(PCB ＊)malloc(sizeof（PCB))) ＝= NUＬＬ）
{
ﻩcｅrr ＜< "malloc" <＜　endl;
ﻩ exiｔ（1);
ﻩ }
cｉn ＞> tmｐ->nａmｅ;
ﻩｇetｃｈａr(）;
ﻩｃin >＞ ｔmｐ->neeｄtｉme;
ﻩtmp->cputiｍe = 0；
tmp－>ｓtate = ＇W＇;
ﻩ tmp-＞pｒio　=　0;
ﻩ ｔmp->round　＝　２;
ﻩtｍp-＞ｃouｎｔ = 0;
ﻩﻩＩnsertＴime(tmp);
ﻩ｝
ﻩcout <＜　"进程名\t轮数\tCPU时间\t需要时间 进程状态 计数器" << endl;
}
//按照优先级调度,每次执行一个时间片
vｏｉd Pｒｉority()
{
ﻩint flag = 1;
ﻩGetFirｓt();
ﻩｗhｉle （ｒun　!= NUＬＬ)
{
ﻩﻩOuｔｐut1()；
ﻩ wｈile (flａg)
ﻩﻩ{
ﻩ run->prio　-= 3; //优先级减去三　
ﻩ run->cputime+＋; ／/CPU时间片加一
ﻩﻩruｎ->neｅｄtime－－;//进程执行完成得剩余时间减一　
ﻩ if （run->needtiｍe ＝= 0)／／如果进程执行完毕,将进程状态置为F，将其插入到完成队列　
ﻩ{
ﻩ ﻩrun->stａte = ＇Ｆ'；
ﻩ ｒun－>count++；
ﻩ ﻩIｎserｔＦiniｓh(ｒuｎ)；
ﻩｆlaｇ =　0;
}
ﻩﻩelse /／将进程状态置为W,入就绪队列
ﻩﻩ ｛
ｒun->stａte　=　'W＇;
ﻩﻩ ｒｕｎ->counｔ++; //进程执行得次数加一
ﻩ ﻩＩnsｅrtTime(ｒｕn)；
flａg =　0;
ﻩ ｝
ﻩﻩ}
fｌaｇ = 1;
ﻩﻩGetFｉrsｔ(); ／/继续取就绪队列队头进程进入执行队列
ﻩ｝
}
vｏid RoundRuｎ()　 //时间片轮转调度算法
{
int fｌａg　= 1；
GetFｉrst(）;
ｗhile (rｕn ！= ＮULＬ)
ﻩ｛
ﻩﻩＯutｐut２(）；
ﻩ wｈile (flag)
｛
ﻩﻩruｎ->count+＋；
ﻩ ﻩrｕn－＞cputime++；
run->ｎeedtime－-;
ﻩiｆ (ruｎ->neeｄtimｅ ==　0) //进程执行完毕
ﻩ{
ﻩﻩﻩrｕn－＞sｔate　＝ 'Ｆ';
ﻩﻩﻩ IｎｓｅｒtFinish（run);
ﻩ ﻩ flag　= ０;
｝
ﻩﻩﻩeｌse if　(rｕｎ->couｎt ＝= ruｎ-＞roｕnd)//时间片用完
ﻩ ﻩ｛
ﻩ ﻩruｎ->ｓtａｔｅ ＝ 'W';
ﻩﻩ ﻩrun-＞count　= 0; ／/计数器清零,为下次做准备　
ﻩ ﻩＩnsｅｒｔTime(run);
ﻩﻩﻩfｌag = 0;
ﻩﻩﻩ｝
ﻩ}
ﻩ ｆlaｇ ＝ 1;
ﻩ ＧｅtFirst();
}
}
ｉnt ｍain(voiｄ)
{
ﻩint　n;
ﻩｃout　＜< "输入进程个数:" <<　endl；
ﻩcｉｎ ＞> nｕm；
ﻩｇｅtｃhar();
ﻩcｏut <<　＂--－－-－---－----－--进程调度算法模拟----－－---------－－----－＂ ＜<　ｅndl;
ｃouｔ　＜＜ " 　 　 1、优先级调度算法" <<　ｅnｄl;
ﻩcouｔ <＜ "　 　　 　 2、循环轮转调度算法 　" << ｅｎdｌ；
ﻩcｏut　<< ＂--－－－---－---－－-－-－-----－-－-－-----－－--－-------－--－-－--－-" << eｎdl;
ｃout <<　"输入选择序号:"　＜< enｄl;
ｃｉn >>　n;
swiｔｃh （n）
{
ｃasｅ 1:
ﻩcｏut ＜< "优先级调度:"　<< endl;
ＰrｉoCreate()；
ﻩ Ｐｒiｏｒity（);
ﻩ Oｕtput１();
ﻩﻩbreak;
case 2:
ﻩﻩcout << "循环轮转算法:" ＜< endｌ;
TiｍeCｒeaｔe();
RoundRｕｎ(）;
Oｕtｐut2（);
ﻩﻩｂrｅａk;
ｃase 0:
ﻩ ｅxit(1);
ﻩ break;
ﻩｄefault：
ﻩcout　<< ＂Enｔer error!" ＜<　ｅndl;
ﻩﻩbｒeak;
ﻩ｝
ﻩcout　<< ｅndl;
ｒeturn 0;
}
四、实验结果
优先级调度

时间片轮转法

五、实验总结
通过本次实验,我学到了进程调度算法,了解了进程调度就是CPU管理得核心,不同得调度算法会使得进程运行时间不同,运行得先后顺序也不同,这就会有一个算法选择得问题、掌握了用C语言实现进程调度算法得模拟，提高了编程能力,以及对进程调度算法得理解。在思考上出现得一个问题就是，队列就是先进先出得,在优先级算法中怎么来向链表中插入新得进程,使其能够按优先级排序、第一想到得就是用数组,后来发现不如链表方便，所以换成链表,但就是发现自己用链表有待提高、