操作系统先进先出算法

南华大学
计算机科学与技术学院
课程设计报告

（2011~2012学年度 第2学期 ）
课程名称 操作系统课程设计
设计题目
请求分页存储器管理系统

成员 朱志强（20104030338）
专业 电气信息 班级
1003
地点 教师 欧阳纯萍
南华大学计算机科学与技术学院 课程设计报告
设计分工
组员学号 20104030338 组员姓名 朱志强 总评成绩
分工描述及自我评价 主要工作是请求分页存储器管理系统的FIFO算法
本次课程设计自己认为已经尽力的做到了最好

同学评价
等级
同学评语

签字：
教师评分等级 教师评语

1.需求分析
1.1题目描述
在请求分页存储器管理系统中，我们需要一个页面置换算法，而先进先出算法
就是最早出现的一种算法，利用该算法可以实现页面的置换，实现内存的充分利
用，使进程可以执行

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

1、输入当前要调用的页面号
2、判断该页面是否已在队列内，
南华大学计算机科学与技术学院 课程设计报告
若在队列内，不执行任何操作
若不在队列内。则执行以下操作
判断队列是否已满
若队列未满，直接把该页面号存入队列
若队列已满，删除并返回队头元素，然后把该页面号存入队
3、输出置换次数，依次输出置换出的页面
1.3 目的
通过模拟实现请求页式存储管理的基本页面置换算法，了解虚拟存储技术的
特点，掌握虚拟存储请求页式存储管理中基本页面置换算法的基本思想和实现过
程。

2.概要设计
2.1算法思路
在请求分页存储器管理系统设计中，先进先出（FIFO）算法是一种给出页面
访问的顺序与分配给作业的主存块数，使用队列作为数据结构编写算法，实现统
计缺页次数与页面置换操作，该算法总是先淘汰最先进入内存的页面，即选择在
内存中停留时间最久的页面予以淘汰。

2.2先进先出算法步骤
1.设置一些页面参数，
int pagenum=0 内存页面数
int total=0 要访问的页面总数
int lacknumber 缺页的总数
2.设置一个队列
int seque[20]={0}; 队列长度设置为20 ，且初值设为0
3.执行算法
输入1,2,3,4,1,2,5,1,2,3,4,5
以输入-1结束

2.3 数据结构
Array[0][20] 定义一个数组
Void main ( ) 系统主函数
Cin>> pagenum 键盘输入 页号

3.详细设计
南华大学计算机科学与技术学院 课程设计报告
*********程序流程图**********

4.程序调试
4.1程序源代码
#include
using namespace std;
int pagenum=0; ///内存的页面数
int total=0; ///要访问的叶面总数
int lacknumber=0; ///缺页的总数

void main()
{
int array[1][20]; //0代表没有内容
for(int y=0;y<2;y++)
for(int x=0;x<20;x++)
{array[y][x]=-1;}
int seque[20]={0};
cout<<"请输入内存的页面数:";
cin>>pagenum;
cout<<"请输入页面的访问顺序(输入-1结束):";
for(int i=0;i<20;i++)
{
int num;
cin>>num;
if(num!=-1)

开始
检查内存是否有
空闲块

选择最先进入
的页面置换

读入访问页面
信息

存入页面

输出置换出的页面序号
结
束

未读完
已读完

有
无
南华大学计算机科学与技术学院 课程设计报告
{
seque[i]=num;
total++;
}
Else
{seque[i]=num;break;}
}
cout<<"总的页面数为"< int j=0;
for(i=0;i {
if(i {
array[0][i]=seque[i];
cout<<"页面"< cout<<"缺页 此时页面内容为";
for(int j=0;j {cout< cout<<"(-1代表没有内容)"< }
cout< }
int kk=0;
for(i=pagenum;i{
int flag=0;
for(int k=0;k {
if(array[0][k]==seque[i])
{flag=1;break;}
}
cout< if(flag==1)
{ cout<<"页面"<cout<<"此时页面内容为";
for(int j=0;j {cout< }
cout< if(flag==0)
{
int tem=array[0][kk];
array[0][kk]=seque[i];
cout<<"页面"< cout<<"缺页 页面"< cout<<"此时页面内容为";
for(int j=0;j {cout< cout< kk++;
lacknumber++; //缺页数
if(kk==pagenum)
{kk=0;}
南华大学计算机科学与技术学院 课程设计报告
}
}
lacknumber=pagenum+lacknumber;

cout<<"缺页率
="<

合集下载

操作系统复习-张尧学

统复习
6.按SJF算法计算周转时间
作 业 号 1 2 3 提 交 时 间 10.00 10.10 10.25 执 行 时 间 2.00 1.00 0.25 开 始 时 间 10.00 12.25 12.00 完 成 时 间 12.00 13.25 12.25 周 转 时 间 2.00 3.15 2.00 带 权 周 转 1.00 3.15 8.00
基本特征:
（1）执行的并发性 （2）资源的共享性 （3）操作的异步性
上一页 下一页 返回首页
操作系统复习
2. 操作系统的功能
(1). 处理机管理 (2). 存储管理 (3). 设备管理 (4). 文件系统管理
(5).用户接口（作业管理）
上一页
下一页
返回首页
操作系统复习
3. 操作系统的三种基本类型及特点
操作系统复习
操作系统复习
考试题型
单选题、填空题 、简答题、综合题
考试范围
第 1 、2 、3 、4 、5 、8 、9 章
重点章节
第2 、3 、4 、5 、8 章
复习内容
各章主要知识点
上一页
下一页
返回首页
操作系统复习
第1章 绪论
知识重点
上一页
下一页
返回首页
操作系统复习
1. 操作系统的定义及特征
操作系统是管理和控制计算机系统中软硬 件资源，合理组织计算机工作流程，方便用户 操作使用机器的程序的集合。
下一页
返回首页
操作系统复习
3. 地址重定位
将程序中的逻辑地址转换映射成内存中物 理的过程。定位方式有：
(1)静态重定位 程序执行前，由软件一次性完成。 (2) 动态重定位 程序执行中，由专门硬件地址变换机构实现。

操作系统(第二版)习题答案

第1章一、填空1．计算机由硬件系统和软件系统两个部分组成，它们构成了一个完整的计算机系统。

2．按功能划分，软件可分为系统软件和应用软件两种。

3．操作系统是在裸机上加载的第一层软件，是对计算机硬件系统功能的首次扩充。

4．操作系统的基本功能是处理机（包含作业）管理、存储管理、设备管理和文件管理。

5．在分时和批处理系统结合的操作系统中引入“前台”和“后台”作业的概念，其目的是改善系统功能，提高处理能力。

6．分时系统的主要特征为多路性、交互性、独立性和及时性。

7．实时系统与分时以及批处理系统的主要区别是高及时性和高可靠性。

8．若一个操作系统具有很强的交互性，可同时供多个用户使用，则是分时操作系统。

9．如果一个操作系统在用户提交作业后，不提供交互能力，只追求计算机资源的利用率、大吞吐量和作业流程的自动化，则属于批处理操作系统。

10．采用多道程序设计技术，能充分发挥CPU 和外部设备并行工作的能力。

二、选择1．操作系统是一种B 。

A．通用软件B．系统软件C．应用软件D．软件包2．操作系统是对C 进行管理的软件。

A系统软件B．系统硬件C．计算机资源D．应用程序3．操作系统中采用多道程序设计技术，以提高CPU和外部设备的A 。

A．利用率B．可靠性C．稳定性D．兼容性4．计算机系统中配置操作系统的目的是提高计算机的B 和方便用户使用。

A．速度B．利用率C．灵活性D．兼容性5．C 操作系统允许多个用户在其终端上同时交互地使用计算机。

A．批处理B．实时C．分时D．多道批处理6．如果分时系统的时间片一定，那么D ，响应时间越长。

A．用户数越少B．内存越少C．内存越多D．用户数越多三、问答1．什么是“多道程序设计”技术？它对操作系统的形成起到什么作用？答：所谓“多道程序设计”技术，即是通过软件的手段，允许在计算机内存中同时存放几道相互独立的作业程序，让它们对系统中的资源进行“共享”和“竞争”，以使系统中的各种资源尽可能地满负荷工作，从而提高整个计算机系统的使用效率。

fifo特点及种类

fifo特点及种类FIFO（First-in, First-out）是一种常见的数据结构，它的特点是按照元素进入的顺序进行处理，先进入的元素先处理，后进入的元素后处理。

FIFO可以用于多种场景，包括计算机中的进程调度、缓存管理、队列等。

FIFO的特点主要有以下几个方面：1. 公平性：FIFO保证了公平性，即先到先服务。

先进入队列的元素会被优先处理，后进入队列的元素会被放在队列的尾部等待。

2. 简单性：FIFO是一种简单的数据结构，实现起来比较容易。

它只需要一个指向队列头和尾的指针，并且只需要实现入队和出队两个操作。

3. 高效性：FIFO的入队和出队操作的时间复杂度都是O(1)，即常数时间复杂度。

这使得FIFO在实际应用中具有高效性。

根据应用场景和具体实现方式的不同，FIFO可以分为多种种类，下面介绍几种常见的FIFO：1. 队列缓存：在计算机中，FIFO常用于实现队列缓存。

队列缓存是一种用于提高数据读写效率的缓存结构。

数据被按照进入的顺序放入队列中，然后按照出队的顺序被读取或写入。

这种缓存结构可以减少数据的等待时间，提高系统的响应速度。

2. 进程调度：在操作系统中，FIFO被用于进程调度。

进程是计算机中正在运行的程序的实例，操作系统通过调度算法来决定哪个进程获得CPU的执行时间。

FIFO调度算法按照进程进入就绪队列的顺序进行调度，先进入就绪队列的进程会被优先执行。

3. 队列数据结构：队列是一种常见的数据结构，它可以使用FIFO 方式进行操作。

队列可以实现先进先出的数据存储和读取方式，常用于解决需要按顺序处理数据的问题。

在队列中，新的元素被添加到队列的尾部，而读取操作则从队列的头部进行。

4. 管道通信：在操作系统中，管道通信是一种进程间通信的方式，其中FIFO被用于实现管道。

管道是一个单向的通道，数据从一个进程通过管道传递给另一个进程。

管道中的数据按照FIFO的顺序进行传递，先进入管道的数据会被先传递给另一个进程。

操作系统-名词解释

信号:信号是一取值为1~19（MAX_SIGS）的某个整数，可以在进程之间传送，用于通知进程发生了某种异常事件，需要执行事先安排好的动作。每个进程在运行中的某几个时机要主动通过信号机制检查是否有信号到达，如有，便中断正在执行的程序，转入对应的事件处理程序。事件处理完毕，再返回断点继续执行原先的程序。这样的信号处理过程与硬件中断处理很相似，故称之为“软中断”。
① 初始化操作，信号灯能初始化为非负的值。
② Wait操作，能减小信号灯的值，如结果值为负，执行Wait操作的进程就被封锁。
③ Signal操作，能增加信号灯的值，如果结果值非正，那么原先因执行Wait操作而阻塞的进程被解除阻塞。
生产者和消费者问题:生产者和消费者问题是通过有限的缓冲区（仓库）将一群生产者P1，P2，…，Pk和一群消费者C1，C2，…，Cm联系起来，通过信号灯实现生产者和消费者的同步与互斥。
进程（不支持线程的进程）:程序在一个数据集合上的运行活动，它是系统进行资源分配和调度的一个可并发执行的独立单位。
并发:并发是指在某一时间间隔内计算机系统内存在着多个程序活动。并发是从宏观上（这种“宏观”也许不到一秒的时间）看多个程序的运行活动，这些程序在串行地、交错地运行，由操作系统负责这些程序之间的运行切换，人们从外部宏观上观察，有多个程序都在系统中运行。
进程控制块PCB（Process Control Block）:系统用于查询和控制进程运行的档案，它描述进程的特征，记载进程的历史，决定进程的命运。
执行（Running）状态:进程占用了CPU，正在执行指令的状态。
就绪（Ready）状态:进程拥有除了CPU之外的任何其他的资源和运行条件，只是由于还没有给它分配CPU而处于下一个执行阶段的起跑线上，它已“万事俱备，只欠东风”，因此就绪状态进程在逻辑上是可执行的。在一个系统中可以有多个进程处于就绪状态，通常将它们排在一个（或多个）就绪队列中。