Linux环境下几种内存调度算法模拟0.docx
《Linux环境下几种内存调度算法模拟0.docx》由会员分享，可在线阅读，更多相关《Linux环境下几种内存调度算法模拟0.docx（17页珍藏版）》请在冰点文库上搜索。
Linux环境下几种内存调度算法模拟0
课程设计（大作业）报告
课程名称：
操作系统
设计题目：
Linux环境下几种内存调度算法模拟
院系：
班级：
设计者：
学号：
指导教师：
设计时间：
2011.12.20—2011.12.23
昆明学院
昆明学院课程设计（大作业）任务书
姓名：
院（系）：
信息学院
专业：
计算机科学与技术学号：
任务起止日期：
2011.12.20—2011.12.23
课程设计题目：
Linux环境下几种内存调度算法模拟
课程设计要求及任务描述：
设计内容：
1.理解FIFO、LRU、OPT等常见内存调度算法的原理。
2.模拟实现其中任意两种调度算法。
3.采用这两种调度算法，对同一访问序列进行命中率计算和输出，并比较结果。
注：
命中率=1-缺页率。
实验环境及工具：
1．实验环境：
Linux
2．文本编辑工具：
Vi
3．编译器：
GCC
工作计划及安排：
2011年12月20日
安装软件调试
2011年12月21日—2011年12月22日
按照要求完成实验内容
2011年12月23日
完成实验报告
指导教师签字
年月日
课程设计（大作业）成绩
学号：
姓名：
指导教师：
课程设计题目：
Linux环境下几种内存调度算法模拟
完成情况总结：
通过这次实验我对先进先出FIFO和最近最久未使用LRU算法的实现方法，有了跟多的了解，在编程过程中查阅了很多的书籍，对编程语言进行了复习。
通过这次实验也使我体会到了思路的重要性，一个程序如果有好的计划，好的设计才能够顺利进行。
这次实验使我更加了解算法的调度过程，以前仅限于知道这一知识点，现在居然能用程序来实现这个过程，我相信这将是一个好的学习方法，希望以后有更多的机会锻炼。
指导教师评语：
成绩：
填表时间：
指导教师签名：
课程设计（大作业）报告
一、两种算法的原理分析
1．FIFO内存调度算法的原理
原理简述。
①在分配内存页面数（AP）大于进程页面数（PP）时，所有进程需要的页面（PP个页面）
按提出请求的先后次序放人内存；
②在分配内存页面数（AP）小于进程页面数（PP）时，当然是按提出请求的次序将最先
的AP个页面放人内存；
③这时有需要处理新的页面，则将原理在内存中的AP个页面中最先进入的调出（称
为FIFO），然后放入新页面；
④以后如果有新页面需要调入，按③的规则进行。
算法特点：
所使用的内存页面构成一个队列。
算法实现提示。
：
，
要得到“命中率”，必然应该有一个常量total—instruction记录页面总共使用次数；此
外，需要一个变量记录总共换人页面的次数（需要换出页面，总是因为没有命中而产生的）
diseffect。
利用公式1一——磐型生l×100％可以得到命中率。
tot
alInstructlon’’’’’’’。
。
’。
。
①初始化。
设置两个数组page[PP]乘1pagecontrol[AP]分别表示进程页面数和内存
分配的页面数，并产生一个随机数序列main[total—instruction]（当然这个序列由page[]的
下标随机构成），表示待处理的进程页面顺序，diseffect置零。
I
②’看main[]中是否有下一个元素，有，就由main[]中获取该页面下标，并转到③；没I
有，就转到⑦。
’I
③如果该page页已在内存中，就转到②；否则转到④，同时未命中的diseffect加1。
I
④观察pagecontrol是否占满，如果占满需将使用队列（⑥中建立的）中最先进入的（就I
是队列第一个单元）pagecontrol单元“清干净”，同时将对应的page口单元置为“不在内l
存中”。
l
⑤将该page口与pagecontrol[]建立关系（可以酶变pagecontrol[]的标示位，tgn-1以采I
用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：
一是它被使用了，二是I
哪个page口单元使用的。
page口单元包含两个信息：
对应的pagecontrol单元号、本page[-]I
单元已在内存中）。
I
⑥将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构1
了，而不是泛指），返回②。
⑦显示1一石i兰篡等兰而×l00％，完成。
2．LRU内存调度算法的原理
原理简述。
①在分配内存页面数（AP）小于进程页面数（PP）时，当然是最先的AP个页面放人
内存；
②当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择其中最长时间
没有用到那个页面调出，以空出内存来放置新调入的页面（称为LRU）。
算法特点：
每个页面都有属性表示有多长时间未被CPU使用的信息。
算法实现提示。
与前述算法一样，只有先得到diseffect才能获得最终的“命中率”。
①初始化。
主要是进程页面page[]和分配的内存页面pagecontrol[]，同时产生随机
序列main[-]，diseffect置零。
②看序列main口是否有下一个元素，如果有就从main[]获取该page[]的下标，并转到
③；如果没有就转到⑥。
③如果该page[]单元在内存中便改变页面属性，使它保留“最近使用”的信息，转到②；
否则转到④，同时diseffct加1。
④判断是否有空闲的内存页面，如果有就返回页面指针，转到⑤；否则，在内存页面中
找出最长时间没有使用到的页面，将其“清干净”，并返回该页面指针。
⑤将需处理的page[]与④中得到的pagecontrol[]建立联系，同时需让对应的page[-]
单元保存“最新使用”的信息，返回②。
⑥如果序列处理完成，就输出1一石石产羔‰×100％，并结束。
二、两种算法的流程图表示
1．FIFO算法的流程图
2．内存调度算法的流程图
三、两种算法的实现代码
1．FIFO内存调度算法的代码
#defineTRUEl
#defineFALSE0
#defineINVALID一1
#defineNULL0
#definetotal—instruction320／*指令流长*／
#definetotal—vp32／*虚页长*／
#defineclear—period50／*清0周期*／
typedefstruct／*页面结构*／
{．
intpn，pfn，counter，time；
}pl—type；
pl—typepl[total—vp]；／*页面结构数组*／
structpfc—struct{／*页面控制结构*／
intpn，pfn}
structpfc—struct*next!
）；
typedefstructpfc—structpfc—type；
pfc—typepfc[total一、rp]，*freepf—head，*busypf—head，*busypf—tailI
intdiseffect，a；[total—instruction]1’
intpage[total—instruction]，offset[total—instruction]；
intinitialize（int）；
intFIFO（int）；．
intmain（）
{
ints，i，J；
srand（10*getpid（））；／*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种
子”*／
S=（float）319*rand（）／32767／32767／2+1；／／
for（i=0；ii+=4）／*产生指令队列*／
{
if（s<<011s>319）
（
printf（”Wheni==％d。
Error。
s==％Q％n”，i，8）I
exit（O）；+
）
a[i]=s；／*任选一指令访问点m*／
a[i+1]=a[i]+1；／*顺序执行一条指令*／
a[i十2]=（float）a[i]*rand（）／32767／32767／2；／*执行前地址指令m’*／
a[i+3]=a[i+2]+1；／*顺序执行一条指令*／
s=（float）（318一a[i+2]）*rand（）／32767／32767／2+a[i+2]+2；
if（（a[i+2]>318）l|（S>319））
printf（”a[％d+2]，anumberwhichis：
％dands==％d＼n”，i，a[i+2]，s）；
）
for（i=0；ii++）／*将指令序列变换成页地址流*／
{
page[i]=a[i]／l0；
offset[i]=a[i]％ioi
}
for（i=4；i<=32；i++）／*用户内存工作区从4个页面到32个页面*／
{
printf（”一％2dpageframes…＼n”，i）l
FIFO（i）；。
）
return0；
）
intinitialize（total—pf）／*初始化相关数据结构*／
inttotal—pf；／*用户进程的内存页面数*／
{inti5
diseffect=0；
for（i=0fi（
pl[i]．pn=i：
pl[i]．pfn=INVALIDl／*置页面控制结构中的页号，页面为空*／
pl[i]．counter=0；
pl[i]．time=一1；／*页面控制结构中的访问次数为0，时间为一1*／
）
for（i=0；i{
pfc[i]．next=&pfc[i+1]；
pfc[i]．pfn=i；
）／*建立pfc[i一1]和pfc[i]之间的链接*／
pfc[total—pf一1]．next=NULL；
pfc[total—pf一1]．pfn=total—pf一1；
freepf—head=＆pfc[o]；／*空页面队列的头指针为pfc[o]*／
return0；
）
intFIFO（total—pf）／*先进先出算法*／
inttotal—pf}／*用户进程的内存页面数*／
{
inti，j；
pfc—type+P；
in北ialize（tota上一pf）；／*初始化相关页面控制用数据结构*／
busypf—head=busypf—tail=NULL!
／*忙页面队列头，队列尾链接*／
for（i=0；i{
if（pl[page[i]]．pfn==INVALID）／*页面失效*／
{
diseffect+=1；／*失效次数*／
if（freepf—head==NULL）／*无空闲页面*／
{
P=busypf—head一>next；
pl[busypf—head一>pn]．pfn=INVALID；
freepf—head=busypf—head；／*释放忙页面队列的第一个页面*／
freepf—head一>next=NULL；
busypf—head=p；
）
P=freepf—head一>next；／*按FIF0方式调新页面入内存页面*／
freepf—head一>next=NULL；
freepf—head一>pn=page[i]；
pl[page[i]]．pfn=freepf—head一>pfn!
if（busypf—tail==NULL）j
busypf—head=busypf—tail=freepf—head；
else
{V
busypf—tail一>nextcfreepf—head!
／*free页面减少一个*／
busypf—tail=freepf—head；
}
freepf—head=p；
}
}
printf（”FIF0：
％6．4f＼n”，l一（float）diseffect／320）：
return01
）
5．可选实验、
这里介绍LRU、NUR、OPT、LFU策略的核心实现代码。
1）LRU／*最近最久未使用算法*／
程序源代码：
intLRU（total—pf）
inttotal—pf；
{
intmin，minj，i，J，present—time）
initialize（total—pf）；
present—time20；
for（i=0；i{
if（pl[page[i33．pfn==INVALID）／*页面失效*／
（
diseffect++；
if（freepf—head==NULL）／*无空闲页面*／
{
min=32767；
for（J20；jif（min>pl[j]．time&&pl[j]．pfnl=INVALID）
{
min=plEj3．time；
minj=J；
}
，freepf—head=&pfc[plEminj]．pfn]；／／腾出一个单元
plEminj]．pfn=INVALID；
pl[minj3．time=一l；
freepf—head—next=NULL）
）
pl[page[i]]．pfn=freepf—head一>pfn）／／有空闲页面，改为有效
pl[page[i33．time=present—time；
freepf—head3freepf—head—next）／／减少一个free页面
}
else
pl[page[i3]．time=present—time）／／命中，则增加该单元的访问次数
present—time++；
）
printf（’’LRU．．％6．4f＼n”，l一（float）diseffect／320）：
return0；
）
2．LRU内存调度算法的代码
intNUR（total—pf）
inttotal—pf；
{inti，J，dp，cont—fla9，old_dp；
pfc—type*t；
initialize（total—pf）；
dp=0；
for（i。
0；i{if（pl[page[i]]．pfn==INVALID）／*页面失效*／
{dlseffect++；
if（freepf—head==NULL）／*无空闲页面*／
（cont—flag=TRUE；
old-dp=dp；
while（cont—flag）
if（plEdp]．counter==O&&pl[dp]．pfnl=INVALID）
cont—flag=FALSE；
else
{
dp++；
if（dp==total—vp）
dp=0；
if（dp==old_dp）
for（J20；jpI[j]．counter=0；
）
freepf—head=&Pfc[pl[dp]．pfn3；
pl[dp]．pfn=INVALID；
freepf—head一>next=NULL；
）
plEpaqe[i]]．pfn=freepf—head一>pfn；
freepf—head=freepf—head->next；
）
else
pl[page[i]]．counter=1；
if（i％clear—period==0）
for（j=0；jpl[j]．counter=0；
）
printf（”NUR：
％6．4f＼n”，l一（float）diseffect／320）：
return0I
）
3）OPT／*最佳置换算法*／
程序源代码：
．’
int0PT（total—pf）
inttotal—pf；
{inti，J，max，maxpage，d，dist[total一、rp]；
pfc—type*t；
initialize（total—pf）；
for（i=0；ii++）
{／／printf（”InOPTforl，i=％d＼n”。
i）；／／i=86；i2176一；206；250；220，221；192，193，194；
258；274，275，276，277，278；
if（pl[page[i]3．pfn==INVALID）／*页面失效*／
{
diseffect++；，
if（freepf—head==NULL）／*无空闲页面*／
{for（J=0；jif（pl[j]．pfn!
=INVALID）dist[j]=32767；／*最大”距离”*／
elsedistEj3=0；
d=1；
for（J=i+1；j{
if（pl[page[j33．pfn!
=INVALID）
dist[page[j]]=d：
d++2
）
max2一l。
for（J=0；jif（max<{
ma】【=dist[j3：
maxpage=J；
）?
freepf—head=&pfcEpl[maxpage]．pfn]；
freepf—head一>next=NULL；
pl[maxpage]．pfn=INVALID；
}
plEpage[i]]．pfn=freepf—head一>pfn；
freepf—head=freepf—head一>next；
）
}‘
printf（”OPT：
％6．4f＼n”，l一（float）diseffect／320）；
return0；
）
4）LFU’／*最不经常使用置换法*／
程序源代码：
intLFU（total—pf）
inttotal—pf；
{
inti，J，min，minpage；
pfc—type*t；
initialize（total—pf）；
for（i=0；i{if（pl[page[i]]．pfn==INVALID）／*页面失效*／
{diseffect++；．
if（freepf—head==WOLL）／*无空闲页面。
／{
j
I
{rain=32767；
for（J=0；j{if（min>pl[j]．counter&&pl[j]．pfn!
=INVALID）
{
min=pl[j]．counter；
minpage=J；
）
pl[j]．counter=0；
}
freepf—head=&pfc[pl[minpage]．pfn]；
pl[minpage]．pfn=INVALID；
freepf—head一>next=NULL；
}
pl[page[i]]．pfn=freepf—head->pfn；／／有空闲页面，改为有效
pi[page[i]]．counter++；
freepf—head=freepf—head一>next；／／减少一个free页面
）
else
pl[page[i]]．counter++；
}
printf（”LFU：
％6．4f＼n”，l一（float）diseffect／320）：
return0；
）
四、结果分析
1.分析设计结果是否达到预期目标
比较FIFO和LRU的命中率相近，但是FIFO的要低些，到达预期目标
2.针对同一访问序列比较两种算法的命中率
命中率=1-缺页率
LRU的命中率高于FIFO的命中率
五、实验总结及心得体会
通过该课程设计，使我们全面系统的理解了存储结构的一般远离和实现方法。
把死板的课本知识变得生动有趣，激发了学习的积极性。
把学习过的计算机操作系统的知识强化。
能够把课堂上学到的知识通过自己的设计的程序表示出来。
加深了对理论知识的理解。
以前对与计算机操作系统的认识是模糊的，概念上的，现在通过自己手动做实验从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机操作系统的认识更加深刻。
这次操作系统的课程设计，让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎么样执行的，对该理论在实践中的应用有深刻的理解。
并且这次课程设计把学习到的知识融合起来，对计算机的整体的认识更加深刻。
升级会员 