上海集团网站建设,河北企业网站建设技术,wordpress的搭建环境,十个知名的跨境电商公司实验三#xff1a;页面调度算法程序
课程名称#xff1a;操作系统原理 项目名称#xff1a;页面调度算法程序 实验#xff08;实训#xff09;类型#xff1a;验证性实验 实验#xff08;实训#xff09;课时#xff1a;2
[目的和要求]
目的#xff1a;
加深对请…实验三页面调度算法程序
课程名称操作系统原理 项目名称页面调度算法程序 实验实训类型验证性实验 实验实训课时2
[目的和要求]
目的
加深对请求页式存储管理实现原理的理解掌握页面置换算法。
进一步理解页面调度算法的相关内容明白页面调度的主要内容通过编程掌握页面调度的主要算法
要求
页式虚拟存储器实现的一个难点是设计页面调度(置换)算法即将新页面调入内存时如果内存中所有的物理页都已经分配出去就要按某种策略来废弃某个页面将其所占据的物理页释放出来供新页面使用。本实验的目的是通过编程实现几种常见的页面调度(置换)算法加深对页面思想的理解。
具体要求为 1、假设分给一作业的内存块数为4,每个页面中可存放10条指令 2、用C语言设计一个程序模拟一作业的执行过程。设该作业共有320条指令即它的地址空间为32页目前它的所有页面都还未调入内存。
[内容与步骤]
在模拟过程中如果所访问的指令已经在内存则显示其物理地址并转下一条指令。如果所访问的指令尚未装入内存则发生缺页此时需记录缺页的次数并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面则需进行页面置换。最后显示其物理地址并转下一条指令。在所有320条指令执行完毕后请计算并显示作业运行过程中发生的缺页率。
内容
1先入先出法(FIFO)
最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是总是选择在主存中停留时间最长(即最老)的一页置换即先进入内存的页先退出内存。理由是:最早调入内存的页其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的否则效率不高。因为那些常被访问的页往往在主存中也停留得最久结果它们因变“老”而不得不被置换出去。 FIFO的另一个缺点是它有一种异常现象即在增加存储块的情况下反而使缺页中断率增加了。当然导致这种异常现象的页面走向实际上是很少见的。
2最优置换算法(OPT)
最优置换(Optimal Replacement)是在理论上提出的一种算法。 其实质是:当调入新的一页而必须预先置换某个老页时所选择的老页应是将来不再被使用或者是在最远的将来才被访问。采用这种页面置换算法保证有最少的缺页率。 但是最优页面置换算法的实现是困难的因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过这个算法可用来衡量(如通过模拟实验分析或理论分析)其他算法的优劣。
3最久未使用算法(LRU)
FIFO算法和OPT算法之间的主要差别是FIFO算法利用页面进入内存后的时间长短作为置换依据而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是当需要置换–页时选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法(Least Recently Used, LRU)。 LRU算法是与每个页面最后使用的时间有关的。当必须置换–个页面时选择过去–段时间里最久未被使用的页面。 LRU算法是经常采用的页面置换算法并被认为是相当好的但是存在的问题。LRU算法需要实际硬件的支持。
步骤
(1)计数器。
最简单的情况是使每个页表项对应一-个使用时间字段并加一个逻辑时钟或计数器。每次存储访问该时钟都加1。每当访问一时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们保留着每个页面最后访问的“时间”。在置换页面时选择该时间值最小样做不仅要查页表而且当页表改变时(因CPU调度)要维护这个页表还要考虑到时钟值溢出的问题。
(2)栈。
用一个栈保留页号。每当访问一个页面时就把它从栈中取出放这样–来栈顶总是放有目前使用最多的页而栈底放着目前最少使用要从栈的中间移走一项所以要用具有头尾指针的双向链连起来。在最坏移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销哪个页面却可直接得到用不着查找因为尾指针指向栈底。
[主要器材与工具]
Windows xp、VMware、 I inux系统
