分页系统课程设计计算说明书doc.docx

分页系统课程设计计算说明书doc.docx

《分页系统课程设计计算说明书doc.docx》由会员分享，可在线阅读，更多相关《分页系统课程设计计算说明书doc.docx（33页珍藏版）》请在冰点文库上搜索。

分页系统课程设计计算说明书doc

摘要

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。

当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间，而用来选择淘汰哪一页的规则叫做页面置换算法。

在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。

但应将哪个页面调出，所以需要根据一定的算法来确定。

常用的算法有先进先出置换算法（FIFO）,最近最久未使用置换算法（LRU）和最佳置换算法（OPT），该设计是在VC++6.0环境下分别用LRU和FIFO来实现页面置换算法的模拟程序，并测试。

关键字：

页面；中断；置换算法

1.概述

分页式虚拟存储系统将作业信息的副本存放在磁盘中，不把作业的程序和数据全部装入主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再把它们动态地装入。

虚拟存储的基本思想是基于程序的局部性原理，仅把目前需要的部分程序加载到内存，其余暂时不用的程序及数据还保留在辅存中。

在进程运行过程中，如果所要执行的程序不在内存，系统要将要执行的程序段自动调入内存。

此时如果内存已满，则要通过置换操作将暂时不用的程序段先调出到辅存，然后将所需的程序段调入内存，继续执行该进程。

虚拟存储器的引入，实际上是利用了存储管理中逻辑地址空间和物理地址空间的关系，将计算机的内存和辅存结合起来，使得用户感觉具有大容量的内存，虚拟内存在虚拟内存在将逻辑地址转换成物理地址时，必须通过一个内存管理单元MMU（Memory Management Unit）来完成。

存储管理一直是操作系统中的重要组成部分，因为冯·诺依曼体系结构就是建立在存储程序概念上的，访问存储器的操作占CPU时间的70%左右。

计算机系统中的存储器一般分为主存储器（简称主存、内存）和辅助存储器（简称辅存）。

由于CPU只能直接与内存进行通信，因此计算机系统的程序以及与该程序相关的数据，只有被装入到内存中才能有效地执行。

计算机系统能否高效地管理内存空间，不仅直接反映存储器的利用率，还会影响整个操作系统的性能。

1.1需求分析

由于纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，并且会产生磁盘碎片问题。

用户程序将受到物理内存大小的限制。

而虚存的存储管理技术——请求分页存储管理技术和请求分段技术，则很好的解决了这个问题。

该设计虚拟实现请求分页管理。

请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。

它允许只装入部分页面的程序和数据，便启动运行。

以后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上，置换时以页面为单位。

实现将程序正在运行时所需的但尚未在内存的页面调入内存，再将内存中暂时不用的页面从内存置换到外存磁盘上。

为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，和在内存的时间的长短。

各字段说明如下：

（1）状态位：

指示该页是否已调入内存。

（2）访问字段：

记录本页在被访问的次数，或记录最近已有多长时间未被访问。

 修改位：

表示该页面在调入内存后是否被修改过。

若未被修改，在替换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。

（3）外存地址：

指出该页在外存上的地址，通常是物理块号。

1.2原理分析

分页虚拟系统存储管理方式是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的虚拟存储器系统。

在进程装入内存时，并不是装入全部页面，而是装入若干页（一个或零个页面）之后根据进程运行的需要，动态装入其他页面。

当内存空间已满，而又需要装入新的内存时，则根据某种算法淘汰某个页面，以便腾出空间，装入新的页面。

在分页虚拟存储管理时使用的页表，是在原来页表的基础上发展起来的，包括以下内容：

页号，物理块号，状态位，外存地址。

其中状态位表示该页是否已经调入内存：

外存地址用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。

在分页虚拟存储管理系统中，每当要访问的页面不在内存时，便产生一缺页中断，请求操作系统把所缺页面调入内存。

如果内存空间已被装满而又要装入新页时，必须按某种算法将内存中的一些页淘汰出去，以便调入新页，这个工作称为“页面置换”。

选择被淘汰页的方法称为页面置换算法。

页面置换算法的好坏，直接影响到系统的性能。

一个好的页面置换算法，应具有较低的页面更换频率。

先进先出算法：

这是最早出现的置换算法，该算法每次淘汰最先进入内存的页。

这种置换算法的优点是：

简单，易于实现。

缺点是：

效率不高，因为在内存中驻留时间最长的页不一定是最长时间后才使用的页。

并且这种置换算法可能产生“抖动”现象。

最近最久未使用算法：

该算法淘汰那些在一段时间最少使用的页。

LRU算法是较好的一个算法，但是开销太大，要求系统有较多的支持硬件，因而在实际应用中，大多只采用LRU的近似算法。

1.3设计相关知识

1．虚拟存储器的引入：

局部性原理：

程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：

时间局限性和空间局限性。

2．虚拟存储器的定义：

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3．虚拟存储器的实现方式：

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4.页面：

是将一个进程的逻辑地址空间分成若干个大小相等的区，称为页面或页，并为各页加以编号，从0开始。

页框（页帧）：

把主存空间分成与页面相同大小的若干个存储区，称为物理块或页框，也同样从0开始依次编号。

页表：

将页号和页内地址转换成内存地址，必须要有一个数据结构，用来登记页号和块的对应关系和有关信息，这样的数据结构称为页表。

5．页面置换算法：

常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。

2.总体设计

分页存储管理方式提高了内存的利用率，分段存储管理方式方便了用户的使用。

结合两者的优点，将分页存储管理和分段存储管理方式组合在一起，形成了段页式存储管理方式。

在段页式存储管理方式中内存分为大小相同的块，每个作业地址空间按照逻辑关系分成若干段，并为每个段赋予一个段名，每段可以独立从0编址，每段按内存块大小分成页，每段分配与其页数相同的内存块，内存块可以连续也可以不连续。

系统为每段建立页表记录每页对应的块，同时还为该程序建立段表记录每段对应的页表。

由段页式存储管理方式的基本原理可以知道，为了访问段页式的地址空间，逻辑地址由三部分组成：

段号S，段内页号P和页内地址d。

（1）硬件地址变换

在段页式存储管理系统中，为了实现地址变换，配置一段表寄存器，在该寄存器中存放段表的始址和段长。

地址变换时，首先利用段号和段长进行比较，如果段号小于段长，则没有越界，于是利用段表寄存器中的段表始址和段号求出该段的段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号得到该页对应的页表的位置，从中读出该页所对应的物理块，把物理块号和页内地址送物理地址寄存器，构成物理地址。

作业业执行时,指令中的逻辑地址指出参加运算的操作数（或指令）地址中的页号和页内偏移量。

硬件地址转换机构按页号查页表。

若该页的标志为1 ,则表示该页已在主存,从而找到该页对应的主存块号。

根据关系式:

 绝对地址=块号*块的长度+页内偏移量 

计算出欲访问的主存地址。

由于页号为2的整次幂,所以只要将块号与页内偏移量相拼接,放入主存地址寄存器即可。

按照该地址取指令或取操作数,完成指定的操作。

设计一个”地址变换”程序,模拟硬件地址变化过程。

当访问的页在主存时,则形成绝对地址后,不去模拟指令的执行,而是输出被转换的地址。

当访问的页不在主存时,输出”该页不在主存,产生缺页中断”,以表示产生一次缺页中断。

（2）页面置换算法

a．先进先出置换算法（FIFO）：

是最简单的页面置换算法。

这种算法的基本思想是：

当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。

其理由是：

最早调入主存的页面不再被使用的可能性最大。

b．最近最久未使用（LRU）算法：

这种算法的基本思想是：

利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。

它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。

所以，这种算法的实质是：

当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

总体设计模块图如下图2.1

图2.1总体设计模块图

3.详细设计

3.1地址转换

（1）分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。

为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，其中，标志----用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。

主存块号----用来表示已经装入主存的页所占的块号，在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。

（2）作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：

绝对地址=块号×块长+单元号。

计算出欲访问的主存单元地址。

如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。

若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

（3）设计一个“地址转换”程序来模拟硬件的地址转换工作。

当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。

当访问的页不在主存时，则输出“产生缺页”，表示产生了一次缺页中断。

（4）地址变换过程：

当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动将逻辑地址分为页号和页内地址两部分，再以页号为索引去检索页表，查找操作由硬件执行。

在执行检索之前，先将页号与页表寄存器中的页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。

于是，这一错误将被系统发现并产生一地址越界中断。

若没有出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。

与此同时，再将逻辑地址寄存器中的页内地址直接送入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的转换。

图3.1地址变换图

3.2先进先出算法

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。

但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。

（1）在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。

如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。

调出和装入后都要修改页表中对应页的标志。

（2）FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。

假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。

例如：

P[0]，P[1]，….，P[m-1]

其中每一个P[i]（i=0，1，….，m-1）表示一个在主存中的页面号。

它们的初值为：

P[0]:

=0，P[1]:

=1，….，P[m-1]:

=m-1

用一指针k指示当要装入新页时，应淘汰的页在数组中的位置，k的初值为“0”。

当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行：

P[k]:

=要装入页的页号

k:

=（k+1）modm

再由装入程序把要访问的一页信息装入到主存中。

重新启动刚才那条指令执行。

（3）FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。

假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。

（4）优点：

对每个进程来说都是公平的。

对于长作业来说比较有利，但对于短作业来说需要等待很长的时间。

缺点：

FIFO算法从表面上看对所有作业都是公平的，但实际上当一个长作业排在就绪队列前面时，就会使排在其后的许多短作业等待很长的时间。

所以，这种算法不利于短作业，致使短作业的等待时间可能要远远超出它运行的时间

图3.2先来先服务算法图

3.3最近最久未使用算法

（1）算法的基本思想：

当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。

该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。

（2）在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。

如果主存中已经没有空闲块，则可用LRU页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。

调出和装入后都要修改页表中对应页的标志。

（3）LRU页面调度算法总是淘汰该作业中距现在最久没有访问过的那一页，因此可以用一个数组来表示该作业已在主存的页面。

数组中的第一个元素总是指出当前刚访问的页号，因此最久没被访问的页总是由最后一个元素指出。

图3.3最近最久未使用算法图

4.系统调试

调试分析：

调试是整个程序编写过程中十分重要也是很困难的一部分，在这个过程中用了不少的时间进行程序的调试，在调试过程中遇到的相关问题如下：

一、语法错误

1、语句的最后忘记了加上“；”，使程序发生错误。

2、把“<<”与“>>”写反，以及字符与字符串的操作问题，这些是比较简单的错误，很容易分辨出来，并改正之。

3、函数的返回值问题，也是比较容易找出并解决的问题。

二、逻辑错误

1、最大的一个问题就是两个算法的正确实现，在程序的编写时，两个程序是分开进行编写的，分别执行起来没有什么问题，但是把两个程序融合在一起后，却出现了问题，即在执行完成一个算法后再执行另外一个算法时，开始的数据是紧接着上次算法结果的数据进行实验的。

这个问题困扰了我好长时间，直到现在还没有很好的解决掉，程序只能分别执行一次，如果再进行执行的话，就会出现问题。

自己的编程技术不好，程序编的也很繁琐，但是基本的要求已经实现了，希望这次的实验是自己动手的一个开始，自己应该更加努力，再接再厉。

2、在这次课程设计中，遇到了一些困难，例如怎么实现各种算法，如何进行函数调用及对数据的限制操作等，在遇到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在各种方法中选择一种最好的方法，有的时候会碰到不知道如何实现的函数，我就尽量去和同学去调试它。

整个调试过程中主要是这么几个问题，其余的是一些小问题，很容易的就调试出来了。

（1）进入界面：

选项1为地址变换算法，选项2为页面置换算法

图4.1主界面

（2）进入硬件地址变换算法：

选择；进入之后共有输入指令和进入置换页面算法两个选项，当输入1时就可以进行地址变换了。

图4.2地址变换界面

（3）输入选择1后，系统自动生成页号，标记位，外存地址和主存号，再输入逻辑地址，系统即可算出物理地址，并给出详细信息：

页面号，主存号和偏移量

图4.3地址变换图

（4）当输入的逻辑地址超出地址范围时就产生了缺页中断，显示该页不在主存内

图4.4缺页中断图

（5）退回到主界面选择2进入页面置换算法，有3个选择：

产生随机序列号，先进先出算法和最近最久未使用算法

图4.5进入页面置换算法界面

（6）选择1产生随机进程序列号：

即可产生一组无规则的随意的进程序列号

图4.6产生进程序列号图

（7）产生随机序列号后，选择2进入最近最久未使用算法，将产生内存状态并自动显示调入队列，缺页次数和缺页率

图4.8最近最久未使用算法图

（8）选择3先进先出算法，就可产生算法表和缺页次数

图4.8先进先出算法图

5.总结

对于C++初学者来说，这一抽象的编程语言的确有些晦涩难懂，尤其是其中的一些细节部分，在课设过程时稍有不慎就会出错。

好在C++实践编程给我们提供了一个很好的运用所学知识来提高自己编程能力的机会，编程过程中需要的是细心和耐心，另外，完备和熟络的基础知识也很重要。

一个较为复杂的程序通常需要串联多种语句、定义多个变量，这样就很容易出现问题，包括一些语法错误和运行错误，所以调试很重要，每当出现的结果和预想的不一样或是效果不是很好时就需要调试了。

调试过程是一个完善程序的过程，也是一个提升自己编程能力的过程，在不断的检查与修改中，自己的编程能力才会不断提升，只有这样，最终的程序才会趋于简单、正确，避免冗长、复杂。

对于这次编程实践，我总结了以下心得：

1、不懂的部分多与小组成员交流，上网查资料；

2、把复杂程序按照功能进行分解，分解成一个个模块，一个模块一个功能，避免大程序；

3、多写注释，当遇到错误时可以方便的找出问题所在；

4、要记得判断可能出现运行异常的地方。

经过本次程序设计，暴露出本团队的很多问题，首先是知识掌握水平不一，作为组长因自身水平不高，果断决定所有变量及函数名采用拼音缩写。

然后是队员编出的程序无法完美兼容，显示出我们沟通的缺乏。

同时也表现出我们知识的欠缺，对于置换算法，地址变换及页表的使用，了解的是在有限，仍需要不断学习，书本上的东西跟本无法完成一个程序。

每次报错我们需要根据错误修改，改不了的就上网查找原因,还有好多好多的瑕疵。

但是不得不承认，经过本次课题设计，也表现出队员们的很多优点，思维缜密，查漏补缺，集体的力量是伟大，通过大家的讨论，总能得到一个好的解决方案。

参考文献

[1]汤子瀛，哲凤屏.计算机操作系统[M].西安：

西安电子科技大学学出版社.1996年

[2]王万森.计算机操作系统原理[M].北京：

高等教育出版社.2001年

[3]周长林，左万历.计算机操作系统教程[M].北京：

高等教育出版社.1994年

[4]黄廷辉，王宇英.计算机操作系统实践教程[M].北京：

清华大学出版社.2007年5月

[5]殷兆麟.计算机操作系统[M].北京：

清华大学出版社.2007年3月

[6]张尧学，史美林，张高.计算机操作系统教程[M].北京：

清华大学出版社.1993年

致谢

在编写程序的过程中，我们得到了马老师的精心指导以及孜孜不倦的教诲，在老师的指导下，我们的能力得到了提高，同时养成了科学、严谨的作风和习惯，在此，我们对老师的精心栽培表示衷心的感谢！

在课设的这几天中感谢同学和搭档的帮忙，我才能够完成课设任务，同时感谢学校的大力支持。

首先得感谢马老师这几天的指导，在此表示衷心的感谢！

其次也感谢那些在我们不懂得时候给予我们帮助的同学。

起初，我们刚开始设计时，对内容掌握度根本就不够，通过了4天的上机实习及课后的查阅资料、询问同学才对自己的程序有了系统的认识及完成程序的设计思路，并在大家的帮助下完成了本次课程设计的全部内容，看着自己做出来的东西心中莫名的开心，在这次过程中也历练了自己的耐心及学习方法。

总之在这次实习中获益匪浅。

对马老师再次表示感谢！

附录

#include

#include

#include

#include

#include

#include

#include

usingnamespacestd;

#defineMyprintfprintf（"|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n"）/*表格控制*/

#definebsize4//物理块大小

#definepsize16//进程大小

voidchushihua（）;//初始化函数

voidymzh（）;

voidyemianzhihuan（）;

voidchangeaddr（structPagep[],intlogaddr）;

voiddizhizhuanhuan（）;

voidmenu（）;

intwang（）;

intyemianliu[32]={0};//全局变量数组，地址流

intp;

structPage{

intpno;//页号

intflag;//标志位

intcno;//主存号

intmodf;//修改位

intaddr;//外存地址

}Page;//全局变量p是一共有多少地址流

typedefstructpage1

{

intnum;/*记录页面号*/

inttime;/*记录调入内存时间*/

}Page1;/*页面逻辑结构，结构为方便算法实现设计*/

Page1b[bsize];/*内存单元数*/

intc[bsize][psize];/*暂保存内存当前的状态：

缓冲区*/

intqueue[100];/*记录调入队列*/

intK;/*调入队列计数变量*/

intphb[bsize]={0};//物理块标号

intpro[psize]={0};//进程序列号

intflag[bsize]={0};//进程等待次数（存放最久未被使用的进程标志）

inti=0,j=0,k=0;//i表示进程序列号,j表示物理块号

intm=-1,n=-1;//物理块空闲和进程是否相同判断标志

intmax=-1,maxflag=0;//标记替换物理块进程下标

intcount=0;//统计页面缺页次数

voidchushihua（）//初始化函数

{

intt;

srand（time（0））;//随机产生指令序列

p=12+rand（）%32;

cout<<"地址流序列：

";

cout<

for（inti=0;i

{

t=1+rand（）%9;

yemianliu[i]=t;//将随机产生的指令数存入页面流

}

for（i=p-1;i>=0;i--）

{

cout<

}

cout<

}

voidymzh（）

{

chushihua（）;

yemianzhihuan（）;

}

voidyemianzhihuan（）