操作系统-课程设计任务(二)：实验请求页式存储管理

操作系统的虚拟存储管理与页式存储技术操作系统是计算机系统中非常重要的一个组件，它负责管理计算机硬件和软件资源，协调各个应用程序的执行，以及提供用户与计算机之间的接口。

虚拟存储管理是操作系统中的一个核心功能，它通过将主存（内存）和辅存（磁盘）结合起来，在有限的主存空间中管理多个应用程序的运行和数据存储。

页式存储技术是一种常用的虚拟存储管理技术，下面将详细介绍虚拟存储管理以及页式存储技术的原理和实现方式。

一、虚拟存储管理的概念和原理虚拟存储管理是一种用于管理计算机主存和辅存的技术，它将辅存中的数据自动地转移到主存中，并且能够在程序运行时动态地分配和回收主存空间。

通过虚拟存储管理，即使计算机的主存空间有限，也可以实现更多应用程序的并发执行和大规模数据的存储与处理。

虚拟存储管理的主要原理是将辅存中的数据划分为若干个固定大小的存储块，称为页面（Page）。

同样，主存也被划分为与辅存页面大小相同的存储块，称为页框（Page Frame）。

每个页面和页框都有唯一的标识符，用于管理和映射页面到页框的关系。

当一个应用程序需要访问或执行某个页面时，操作系统将其从辅存中读入一个空闲的页框，并将其映射到相应的页面标识符。

如果主存中没有空闲的页框，则需要使用一定的页面置换算法将某个页面替换出去，以腾出页框给新的页面使用。

虚拟存储管理能够有效地利用计算机的主存资源，并且能够在不同的应用程序之间进行数据保护和隔离。

通过页面和页框的映射关系，操作系统可以实现虚拟地址空间的划分和隔离，每个应用程序都认为自己独占了整个计算机的内存空间，而不需要关心其他应用程序的存在。

二、页式存储技术的实现方式页式存储技术是一种基于虚拟存储管理的实现方式，它将主存和辅存划分为固定大小的页面，并且使用页表来管理页面和页框的映射关系。

下面将详细介绍页式存储技术的实现方式。

1. 页面和页框的划分页式存储技术将辅存和主存划分为固定大小的页面和页框，通常大小为2的幂次方，例如2KB、4KB或者16KB等。

《计算机操作系统》课程设计教学大纲课程编号：08120070课程名称：计算机操作系统/Computer Operating System课程总学时/学分：56/3.5（其中理论46学时，实验10学时课程设计时间/学分：1周/1学分适用专业：计算机科学与技术一、设计任务及目的《计算机操作系统》课程是计算机科学与技术专业的一门重要专业基础课，“计算机操作系统课程设计”的目的是在学生学习了《计算机操作系统》课程之后理论联系实践，一方面延续《计算机操作系统》课程实验的要求，进一步加深与巩固学生对计算机操作系统中概念、基本原理、算法的理解和掌握，培养学生对计算机常用操作系统的操作能力；另一方面通过本环节加强培养学生分析、修改和设计操作系统的能力。

期望达到学为所用，并且能进一步提高使用计算机和编程能力。

二、课程设计的基本要求1、了解所选择开发环境的调试功能，掌握跟踪，修改错误的技巧。

2、能根据实际问题选择数据结构，清淅的描述算法。

3、培养良好的编程风格。

4、撰写课程设计报告，按格式要求写出完整的、规范的报告并打印，其中模块图、流程图要清楚规范，特别要求学生独立完成。

三、设计需运用的基本理论设计需运用计算机系统知识、操作系统基本概念、进程管理、存储管理技术、I/O管理技术、文件管理、高级语言程序设计、数据结构等内容。

四、课程设计内容与时间安排1、设计内容：可以选择下面提供的参考选题，也可以自选，如果自选，需要将自选题，目的详细内容以及实现要求提供给老师，老师批准后方可采用。

课题一：进程管理演示设计目的：加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。

设计内容：设计一个允许n个进程并发运行的进程管理模拟系统。

该系统包括有简单的进程控制、同步与通讯机构，其进程调度算法可任意选择（优先级调度，时间片轮转，短进程优先中的一种）。

每个进程用一个PCB表示，其内容根据具体情况设置。

操作系统——页式存储管理分区式存储管理最⼤的缺点是碎⽚问题严重，内存利⽤率低。

究其原因，主要在于连续分配的限制，即它要求每个作⽤在内存中必须占⼀个连续的分区。

如果允许将⼀个进程分散地装⼊到许多不相邻的分区中，便可充分地利⽤内存，⽽⽆需再进⾏“紧凑”。

基于这⼀思想，产⽣了“⾮连续分配⽅式”，或者称为“离散分配⽅式”。

连续分配：为⽤户进程分配的必须是⼀个连续的内存空间。

⾮连续分配：为⽤户进程分配的可以是⼀些分散的内存空间。

分页存储管理的思想：把内存分为⼀个个相等的⼩分区，再按照分区⼤⼩把进程拆分成⼀个个⼩部分。

分页存储管理分为：实分页存储管理和虚分页存储管理⼀、实分页式存储管理实分页式存储最⼤的优点是内存利⽤率⾼，与⽬前流⾏的虚分页存储管理相⽐，具有实现简单，程序运⾏快的优点。

⽬前，飞速发展的硬件制造技术使得物理内存越来越⼤，因此我们认为，实分页式存储管理将是⼀种最有发展前途的存储管理⽅式。

1.1、基本原理假设⼀个⼤型饭店，所有的客房都是标准的双⼈间，部分客房已经住进客⼈，现在⼜有⼀个旅游团要求⼊住。

接待员统计了⼀下，对旅游团领队说：“贵团全体成员都能住下，两⼈⼀个房间，但是不能住在同⼀楼层了，因为每层空着的客房不够，更没有⼏个挨着的。

请原谅！”。

对于这样的安排，⼀般⼈不会感到奇怪。

因为旅游团本来就是由⼀位位个⼈或夫妻等组成的，⽽饭店的客房本来也是两⼈⼀间的，两⼈⼀组正好可住在⼀个客房⾥；另外，饭店⼏乎每天都有⼊住的和退房的客⼈，想在同⼀楼层找⼏间挨着的客房实在不容易。

①将整个系统的内存空间划分成⼀系列⼤⼩相等的块，每⼀块称为⼀个物理块、物理页或实页，页架或页帧（frame），可简称为块（block）。

所有的块按物理地址递增顺序连续编号为0、1、2、……。

这⾥的块相当于饭店的客房，系统对内存分块相当于饭店把⼤楼所有的客房都设计成标准的双⼈间。

②每个作业的地址空间也划分成⼀系列与内存块⼀样⼤⼩的块，每⼀块称为⼀个逻辑页或虚页，也有⼈叫页⾯，可简称为页（page）。

操作系统实验指导书实验1 存储管理1、实验目的存储管理的主要功能之一是合理地分配空间。

请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。

2、实验内容（1）通过随机数产生一个指令序列，共320条指令。

指令的地址按下述原则生成：①50%的指令是顺序执行的；②50%的指令是均匀分布在前地址部分；③50%的指令是均匀分布在后地址部分。

具体的实施方法是：①在 [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条-第19条指令为第一页（对应虚存地址为[10，19]）；……第310条~第319条指令为第31页（对应虚地址为[310，319]）。

按以上方式，用户指令可组成32页。

（3）计算并输出下述各种算法在不同内存容量下的命中率。

①先进先出的算法（FIFO）；②最近最少使用算法（LRR)；③最佳淘汰算法（OPT）先淘汰最不常用的页地址；④最少访问页面算法（LFR）；⑤最近最不经常使用算法（NUR）。

其中③和④为选择内容。

命中率=1-页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

3、随机数产生办法，Linux或UNIX系统提供函数strand()和rand(),分别进行初始化和产生随机数。

操作系统-请求页式存储管理实验报告分析解析实验背景在计算机系统中，内存是一项很重要的资源。

其中，操作系统需要管理内存，以便为用户进程和内核提供适当的内存空间。

页式内存管理是操作系统能够管理和维护内存的一种方式。

在页式内存管理中，主存分为固定大小的框架，称为页框，而进程的地址空间被分割为固定大小的页。

页式内存管理系统采用了一种称为“请求页式存储”的技术，允许进程只存取正在使用的那些页面。

这样可以节省空间，并且提高了处理器访问内存的速度。

实验环境本次实验使用的操作系统是 Ubuntu 20.04 LTS 操作系统。

实验目标本次实验的主要目标是通过模拟请求页式内存管理系统，来了解和深入理解页式内存管理技术。

本次实验需要完成以下任务：1.编写一个简单的请求页式存储模拟器；2.使用该模拟器对作业和内存进行模拟；3.分析模拟结果并撰写实验报告。

实验过程阅读并理解作业说明在开始实验之前，我们首先需要阅读和了解具体的作业说明。

在本次实验中，我们需要完成一个请求页式存储模拟器，以及使用该模拟器对作业与内存进行模拟。

编写模拟器在了解了作业说明后，我们开始按照作业的要求，编写请求页式内存管理模拟器。

在这里，我们需要使用到Python 编程语言。

实际上，我们在编写该模拟器时，主要分为以下几步：1.文件操作：首先，我们需要通过读取文件中的数据来模拟进程对内存的请求。

在输入文件中，每一行表示一个请求，包含了进程 ID、请求的地址和访问类型。

2.内存分配：接着，我们需要模拟请求页式内存管理系统中对于内存分配的操作，即在访问时，将需要的页加载到内存中，如果内存已满，则需要选择一个页面将其从内存中移除，为新的页面腾出空间。

3.页面置换：如果进行页面置换，则需要选出最久未访问的页面并移出内存，空出空间用于新的页面，这就是所谓的“最久未使用”（LRU）策略。

进行模拟有了模拟器之后，我们就可以针对不同的作业和内存大小进行实验。

在实验的过程中，我们可以观察不同大小的内存和不同的作业怎样影响模拟的结果。

计算机操作系统实验教程徐 慧中国矿业大学（北京）机电与信息工程学院计算机系二0 0四年四月实验简介 (2)实验一进程管理 (3)一、实验目的 (3)二、实验预备内容 (3)三、实验内容 (3)四、预备知识 (3)五实验指导 (4)实验二进程间的通信 (5)一、实验目的 (5)二、实验预备内容 (5)三、实验内容 (5)四、实验预备知识 (5)五、实验指导 (9)实验三存储管理 (10)一、实验目的 (10)二、实验内容 (10)三、实验预备知识 (10)四、实验指导 (13)实验四文件系统设计 (14)一、实验目的 (14)二、实验内容 (14)三、实验提示 (14)四、实验指导 (14)实验简介1．学时：16学时2．先修课程：计算机导论 ，高级语言程序设计 ， 数据结构3．课程性质：专业基础必修课4．适合专业：计算机科学与技术5．内容简介：操作系统上机课程通Linux操作系统各自的编程接口，提供编程实例，由此加深学生对操作系统工作原理的领会和对操作系统实现方法的理解，并且使学生在程序设计方面得到基本的训练。

上机课程主要针对课本重点内容，以提高学生的动手能力，加深学生对相关的内容的理解而展开的实验课程。

在Linux环境下提供了关于操作系统的命令接口程序shell的编制、存储管理相关内容的实路、作业调研系统以及虚拟磁盘文件系统管理4个实验。

实验环境是基于Linux操作系统的。

在计算机软硬件课程的设置上，它起着承上启下的作用。

其特点是概念多、较抽象和涉及面广，其整体实现思想和技术又往往难于理解。

6．参考书：张尧学，史美林 《计算机操作系统课程设计实验指导》 清华大学出版社 2000年实验一 进程管理一、实验目的(1)加深对进程概念的理解,明确进程的程序的区别;(2)可进一步认识并发执行的实质;(3)分析进程争用资源的现象,学习解决进程互斥的方法;(4)了解LINUX系统中进程通信的进本原理;二、实验预备内容(1)阅读LINUX 的sched.h源码文件,加深对进程管理概念的理解;(2)阅读LINUX的fork.c源码,分析进程的创建过程;三、实验内容(1)进程创建编写一段程序,使用系统调用fork()创建两个子进程.(2)进程的控制修改以编写的程序,将每个进程输出一个字符改为输出一句话,观察程序执行时屏幕上出现的现象;(3)编写一段程序实现软中断;(4)进程的管道通信;四、预备知识现代操作系统的重要特点是程序的并发执行，及系统所拥有的资源被共享和系统用户随机地使用系统。

实验六：请求分页存储管理一．实验目的深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的地址变换、缺页中断、置换算法等实现思想。

二．实验属性该实验为综合性、设计性实验。

三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求2学时完成。

本实验要求完成如下任务：（1）建立相关的数据结构：页表、页表寄存器、存储块表等；（2）指定分配给进程的内存物理块数，设定进程的页面访问顺序；（3）设计页面置换算法，可以选择OPT、FIFO、LRU等，并计算相应的缺页率，以比较它们的优劣；（4）编写地址转换函数，实现通过查找页表完成逻辑地址到物理地址的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU等）完成页面的交换；（5）将整个过程可视化显示出来。

实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。

实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。

三、设计过程3.1算法原理分析OPT算法是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。

FIFO算法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。

LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。

3.2数据定义int length,num_page,count,seed; //length记录访问串的长度，num_page页面数，count记录缺页次数int result[20][30],order[30],a[10]; //result记录结果,order存储访问串,a存储当前页面中的值int pos1,flag1,flag2,flag3; //pos1位置变量，flag1等为标志变量 char result1[30]; //记录缺页数组 void opt() //最佳void fifo() //先进先出bool search(int n) //查找当前内存中是否已存在该页3.3流程图与运行截图图6.1 FIFO （）函数流程图;否是 是否 开始得到执行的指令指令是否在内存中最先存入指令被淘汰下面是否还有指令 结束得出命中率图2.2 OPT算法流程图四、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

操作系统实验报告专业：软件工程姓名：李程星学号：2011221104220092实验一操作系统的用户界面LINUX操作系统提供了图形用户界面和命令行界面，本实验主要熟悉命令行界面，为后续的实验编程做准备。

一、系统启动1. 开机，选择进入Linux系统，约40秒后系统启动成功，系统提示输入用户名：user输入口令：111111 然后进入Linux系统桌面。

2.进入Linux命令行方式单击小红帽图标，选择“系统工具”，单击“终端”图标，出现Linux的shell提示符.....@......$,，即可输入命令。

实验二进程管理一、实验目的（1）加深对进程概念的理解，明确进程和程序的区别。

（2）进一步认识并发执行的实质。

二、实验内容1、进程的创建执行下面的程序，分析执行的结果。

#include <stdio.h>main(){ int i;printf("just 1 process.\n");i=fork();if (i==0)printf("I am child.\n");elseif (i>0)printf("I am parent.\n");elseprintf("fork() failed.\n");printf("program end.\n");}输出结果：just 1 process.I am parent.program end.I am a child.program end.2、进程的同步执行下面的程序，分析执行的结果。

#include <stdio.h>main(){ int i;printf("just 1 process.\n");i=fork();if (i>0){printf("I am parent.\n");wait();}elseif (i==0) {printf("I am child.\n");exit(1);}printf("program end.\n");}输出结果：just 1 process.I am parent.I am child.program end.3、进程的延迟执行下面的程序，分析执行的结果。

操作系统课程设计报告项目：模拟请求页式存储管理一、目的和要求1、实训目的（1）通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。

熟悉虚存管理的各种页面淘汰算法（2）通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。

2、实训要求编写并调试完成请求页式存储管理程序。

页面置换算法：最佳置换算法（OPT）、先进先出算法(FIFO)和最近最少用算法（LRU）。

要求打印每个页面置换算法的页面置换变化示意图、缺页中断次数和缺页中断率，以比较各种算法的优缺点。

二、设计思路及过程1、概要设计1.1 问题概述根据三种不同的置换算法（FIFO、LRU、OPT），依据其不同的算法方式，分别计算该页面引用串在不同算法下的缺页次数与缺页率，并显示各页面的变化情况。

1.2 内容分析对于该课程设计中模拟的请求页式存储管理的页面置换过程，只要掌握其中最基本的三种算法，包括FIFO、LRU及OPT。

另外，对于同一个页面引用串，要求能够调用不同的算法对它进行操作。

2、过程设计2.1模块设计在下图的主模块设计图中，只注重描绘了请求页式存储管理的三种主要算法，未描绘出细节部分。

图2.1 请求页式存储管理的主模块设计图2.2 算法原理分析要成功实现算法，首先要知道各个方法是怎么做的，即原理是怎样的，下面是三种算法的原理。

（1）FIFO算法：该算法认为刚被调入的页面在最近的将来被访问的可能性很大，而在主存中滞留时间最长的页面在最近的将来被访问的可能性很小。

因此。

FIFO算法总是淘汰最先进入主存的页面，即淘汰在主存中滞留时间最长的页面。

（2）LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。

该算法总是选择最近一段时间内最长时间没有被访问过的页面调出。

它认为那些刚被访问过的页面可能在最近的将来还会经常访问他们，而那些在较长时间里未被访问的页面，一般在最近的将来再被访问的可能性较小。

页式存储管理一、实验目的：掌握分页式存储管理的基本概念和实现方法。

要求编写一个模拟的分页式管理程序，并能对分页式存储的页面置换算法进行编写和计算各个算法的缺页率。

二、程序设计：首先创建页面链指针数据结构，并设计页面映像表，采用数组的方法给定页面映像。

申请缓冲区，将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称做页面或页。

每页都有一个编号，叫做页号，页号从0开始依次编排，如0，1，2……。

设置等大小的内存块。

初始状态：将数据文件的第一个页面装入到该缓冲区的第0块。

设计页面置换算法，这里分别采用最佳页面置换算法OPT和最近最久未使用置换算法LRU,并分别计算它们的缺页率，以比较它们的优劣。

三、算法说明：执行程序时，当主存没有可用页面时，为了选择淘汰主存中的哪一页面，腾出1个空闲块以便存放新调入的页面。

淘汰哪个页面的首要问题是选择何种置换算法。

该程序采用人工的方法选择，依置换策略选择一个可置换的页，并计算它们的缺页率以便比较。

/*分页式管理实验-源程序*/#include"stdio.h"#define N 16#define num 5 /*进程分配物理块数目*/int A[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4}; /*页表映像*/typedef struct page{ int address; /*页面地址*/struct page *next;}page;struct page *head,*run,*rear;void jccreat() /*进程分配物理块*/{ int i=1;page *p,*q;head=(page *)malloc(sizeof(page)); p=head;for(i=1;i<=num;i++) { q=(page *)malloc(sizeof(page));p->next=q; q->address=0; q->next=NULL; p=q; }rear=p;}int search(int n){page *p;int i=0;p=head;while(p->next){if(p->next->address==n){printf("Get it at the page %d\n",i+1);run=p;return 1;}p=p->next;i++;}return 0;}void changeOPT(int n,int position){int i;int total=0;int flag=1;int distance[num];int MAX;int order=0;page *p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)distance[i]=100;i=0;while(p){if(p->address==0){flag=0;break;}p=p->next;i++;}if(!flag){p->address=n;printf("Change the page %d\n",i+1);}else{while(q){for(i=position;i<N;i++){if(q->address==A[i])distance[total]=i-position;}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++){if(distance[i]>MAX){MAX=distance[i];order=i;}}printf("Change the page %d\n",order+1);i=0;while(p){if(i==order)p->address=n;i++;p=p->next;}}}void changeLRU(int n){int i=0;int flag=1;page *p,*delect;p=head->next;while(p){if(p->address==0){flag=0;p->address=n;printf("Change the page %d\n",i+1);break;}p=p->next;i++;}if(flag){delect=head->next;head->next=delect->next;printf("Delect from the head, and add new to the end.\n");delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;}}float OPT(){int i;int lose=0;float losef;float percent;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}}losef=lose;percent=1-(losef/N);return percent;}float LRU(){int i;int lose=0;float losef;float percent;page *p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeLRU(A[i]);}else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Move it to end of queue.\n");}}losef=lose;percent=1-(losef/N);return percent;}main() /*主函数部分*/{float percent;int choice;printf("Select the arithmetic:\n(1)OPT\n(2)LRU\nyour choice is:"); scanf("%d",&choice);/*选择页面置换算法*/jccreat(); /*创建进程*/if(choice==1) /*采用OPT算法置换*/{percent=OPT(); /*计算OPT时的缺页率*/ printf("The percent of OPT is %f",percent);}else if(choice==2) /*采用LRU算法置换*/ {percent=LRU(); /*计算LRU时的缺页率*/ printf("The percent of OPT is %f",percent);}else printf("Your choice is invalid.");getch();}四．运行结果:最佳（Optimal）置换算法：最近最久未使用(LRU)置换算法：五、心得体会掌握分页式存储管理的基本概念和实现方法。