沈阳工程学院信息学院操作系统课程设计 第三章 需求分析
第三章 需求分析
3.1 问题描述
1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。
2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。
在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：采用先进先出（FIFO）置换算法。
3.2 基本功能需求
1） 存放页面数M(M<=32)，分配给作业的内存块数为N(N<=4)。 2） 计算并显示作业运行过程中发生的缺页率。 3） 置换算法：采用先进先出（FIFO）置换算法。
3.3 提示要求
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： ① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分； ③ 25%的指令是均匀分布在后地址部分； 具体的实施方法是：
① 在[0，319]的指令地址之间随机选取一起点m； ② 顺序执行一条指令，即执行地址为m+1的指令；
③ 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m′； ④ 顺序执行一条指令，其地址为m′+1的指令；
⑤ 在后地址[m′+2，319]中随机选取一条指令并执行； ⑥ 重复上述步骤①～⑤，直到执行320次指令。 （2）将指令序列变换为页地址流 ① 设页面大小为1K；
② 用户内存容量为4页到32页； ③ 用户虚存容里为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
10
沈阳工程学院信息学院操作系统课程设计 第三章 需求分析
第10条～第19条指令为第1页（对应虚存地址为[10，19]）； ??
??
第310条～第319条指令为第31页（对应虚存地址为[310，319]）。 按以上方式，用户指令可组成32页。
（3）计算先进先出（FIFO）算法在不同内存容量下的命中率。
11
沈阳工程学院信息学院操作系统课程设计 第四章 概念设计
第四章 概念设计
4.1 数据结构
先进先出（FIFO）算法即先入先出队列，先进入的对象先出来。
FIFO存储器 FIFO是英文First In First Out 的缩写，是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。 在系统设计中，以增加数据传输率、处理大量数据流、匹配具有不同传输率的系统为目的而广泛使用FIFO存储器，从而提高了系统性能。FIFO存储器是一个先入先出的双口缓冲器，即第一个进入其内的数据第一个被移出，其中一个存储器的输入口，另一个口是存储器的输出口。对于单片FIFO来说，主要有两种结构：触发导向结构和零导向传输结构。触发导向传输结构的FIFO是由寄存器阵列构成的，零导向传输结构的FIFO是由具有读和写地址指针的双口RAM构成。
FIFO存储器是系统的缓冲环节，如果没有FIFO存储器，整个系统就不可能正常工 作，它主要有几方面的功能：
1）对连续的数据流进行缓存，防止在进机和存储操作时丢失数据；
2）数据集中起来进行进机和存储，可避免频繁的总线操作，减轻CPU的负担； 3）允许系统进行DMA操作，提高数据的传输速度。这是至关重要的一点，如果不
采用DMA操作，数据传输将达不到传输要求，而且大大增加CPU的负担，无法同时完成数据的存储工作。
因此，选择合适的存储芯片对于提高系统性能很重要，在以往的设计中经常采用的是“乒乓型”存储方式，这种方式就是采用两片存储器，数据首先进入其中一片，当数据满时再让数据进入第二片存储器，同时通过逻辑控制，将第一片存储器中的数据取走，以此类推，两片轮流对数据进行缓存。这种方式有着较明显的缺点，首先是控制复杂，要有专门的逻辑来维护这种轮流机制;其次，数据流的流向要不断变化，限制了数据流的速率，还容易产生干扰。从数据传输上说，缓存芯片容量越大，对后续时序要求就越低，可减少总线操作的频次；但从数据存储上说，就意味着需要开辟更大的内存空间来进行进行缓冲，会增加计算机的内存销，而且容量越大，成本也越高。因此，在综合考虑系统性能和成本的基础上，选择满足系统需要的芯片即可。FIFO是First In/First－Out的缩写，是先入先出的意思。FIFO存储器分为写入专用区和读取专用区。读操作与写操作可以异步进行，写入区上写入的数据按照写入的顺序从读取端的区中读出，类似于吸收写入端与读出端速度差的一种缓冲器。计算机的串口，一般也都具有FIFO缓冲器（不是单一的FIFO存储器，而是嵌入在设备内部）。FIFO存储器的连接模式如图所示。在FIFO存储器而不是地址总线上附加了表示内部缓冲器状态（Buffer Full，缓冲器已满；Buffer Empty，缓冲器为空）的状态引脚，连接于FIFO的双方利用该状态进行操作的控制。另外，还设计了在接通电源及复位（Reset）或由于操作中的某些异常等原因而重新初始化（无数据状态）FIFO的复位引脚，这可以说是FIFO存储器的特点。
下面是队列的实现：
12
沈阳工程学院信息学院操作系统课程设计 第四章 概念设计
需由此接口发送的报文 说明： 紧急报文 次紧急报文 非紧急报文
队列 FIFO 离开接口的报文
图4.1.1 队列
4.2 系统包含的函数
typedef struct BLOCK//声明一种新类型——物理块类型 {
int pagenum;//页号
int accessed;//访问字段，其值表示多久未被访问 }BLOCK;
int count;//程序计数器，用来记录指令的序号 int n;//缺页计数器，用来记录缺页的次数 static int temp[320];//用来存储320条随机数
BLOCK block[size]; //定义一大小为4的物理块数组 void init( ); //程序初始化函数
int findExist(int curpage);//查找物理块中是否有该页面 int findSpace( );//查找是否有空闲物理块 int findReplace( );//查找应予置换的页面
void display ( );//显示
void Random( );//产生320条随机数,显示并存储到temp[320] void pagestring( );//显示调用的页面队列 void FIFO( );//FIFO算法
13