操作系统课程设计 请求调页存储管理.doc

计算机科学与应用系操作系统原理课程设计报告题目 请求调页存储管理 Linux的安装及用户接口 班级 xxx 学号 xxx 姓名 xxx 专业 计算机科学与技术 指导教师 实验一 请求调页存储管理1实验目的(1) 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。(2) 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。(3) 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2实验内容 1假设每个页面中可存放10条指令，分配给作业的内存块数为4。2用C语言或C+语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3置换算法：请分别考虑最佳置换算法（OPT）、先进先出（FIFO）算法和最近最久未使用（LRU）算法。4作业中指令的访问次序按下述原则生成；50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令均匀分布在后地址部分。具体的实现办法是：（1）在0，319之间随机选取一条起始执行指令，其序号为m；（2）顺序执行下一条指令，其序号为m+1条指令；（3）通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为m1；（4）顺序执行下一条指令，即序号为m1+1的指令；（5）通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2；（6）顺序执行下一条指令，则序号为m2+1的指令；（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分；顺序执行的过程，直至执行320条指令。3实验步骤1分析及概要设计在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性能。以下分别是实验要求的两个页面置换算法的介绍及设计思想。（1）先进先出法（First In First Out）：该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1；并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；（2）最近最久未使用（Least Recently Used）： 该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。（3）最佳置换算法（OPT）：发生缺页时，有些页面在内存中，其中有一页见很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。 最佳页面置换算法只是简单地规定：标记最大的页应该被置换。如果某页在八百万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面，从而把因需要调回这一页发生的缺页推到将来，越远越好。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。2流程图开始调用FIFO算法调用LRU算法调用OPT算法提示输入数据非法输出指令执行顺序和页面调用顺序得到指令执行的顺序接收键盘输入数值判断输入数是否在1320选择页面置换算法结束3程序代码#include <iostream.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>#define size 4typedef struct BLOCK/声明一种新类型物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问BLOCK; int count;/程序计数器，用来记录指令的序号int n;/缺页计数器，用来记录缺页的次数static int temp320;/用来存储320条随机数BLOCK blocksize; /定义一大小为4的物理块数组void init( ); /程序初始化函数int findExist(int curpage);/查找物理块中是否有该页面int findSpace( );/查找是否有空闲物理块int findReplace( );/查找应予置换的页面void display ( );/显示void Random( );/产生320条随机数,显示并存储到temp320void pagestring( );/显示调用的页面队列void OPT( );/OPT算法void LRU( );/ LRU算法void FIFO( );/FIFO算法void init( ) for(int i=0;i<size;i+) blocki.pagenum=-1; blocki.accessed=0; count=n=0; int findExist(int curpage) /查找物理块中是否有该页面for(int i=0; i<size; i+) if(blocki.pagenum = curpage ) return i; /检测到内存中有该页面，返回block中的位置 return -1;int findSpace( ) /查找是否有空闲物理块 for(int i=0; i<size; i+) if(blocki.pagenum = -1) return i; /找到空闲的block，返回block中的位置return -1;int findReplace( ) /查找应予置换的页面int pos = 0; for(int i=0; i<size; i+)if(blocki.accessed >blockpos.accessed) pos = i;/找到应予置换页面，返回BLOCK中位置 return pos;void display( ) for(int i=0; i<size; i+) if(blocki.pagenum != -1) /物理块不空 printf(" %02d",blocki.pagenum); cout<<endl;void Random( ) int flag=0; cin>>count; cout<<"*按照要求产生的320个随机数：*"<<endl; for(int i=0;i<320;i+) tempi=count;if(flag%2=0)count=+count%320;/产生50%的顺序执行指令（flag=0或2时顺序执行） if(flag=1) count=rand( )% (count-1); /产生25%的均匀分布在前地址部分指令 if(flag=3) count=count+1+(rand( )%(320-(count+1); /产生25%的均匀分布在后地址部分指令 flag=+flag%4;printf(" %03d",tempi); if(i+1)%10=0) cout<<endl;void pagestring( ) /显示调用的页面队列 for(int i=0;i<320;i+) printf(" %02d",tempi/10); if(i+1)%10=0) cout<<endl;/-最佳置换算法void OPT( )int exist,space,position ; int curpage; for(int i=0;i<320;i+) if(i%100=0) getch( ); count=tempi; curpage=count/10; exist = findExist(curpage); if(exist=-1) space = findSpace ( ); if(space != -1)blockspace.pagenum = curpage; display( ); n=n+1; elsefor(int k=0;k<size;k+)for(int j=i;j<320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/将来不会用，设置为一个很大数 elseblockk.accessed = j;break; position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; cout<<"缺页次数:"<<n<<endl; cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;/- 最近最少使用算法 void LRU( ) int exist,space,position ; int curpage; for(int i=0;i<320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; /指令在数组中的位置 curpage=count/10; /指令所在页面 exist = findExist(curpage); /查找物理块中是否有该页面,若有返回物理块号 if(exist=-1) /物理块中不存在该页space = findSpace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; blockposition.accessed = -1; /恢复刚调入的BLOCK中页面accessed为-1 display( ); n+; else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1 for(int j=0; j<4; j+) blockj.accessed+; cout<<"缺页次数:"<<n<<endl; cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;/- 先进先出算法void FIFO( ) int exist,space,position ; int curpage; for(int i=0;i<320;i+) if(i%100=0) getch( ); /getch直接从键盘获取键值 count=tempi; curpage=count/10; exist = findExist(curpage); /查找物理块中是否有该页面 if(exist=-1)space = findSpace( ); /查找是否有空闲物理块 if(space != -1) /有空闲物理块 blockspace.pagenum = curpage; display( ); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace( ); /查找应予置换的页面 blockposition.pagenum = curpage; display( ); n+; blockposition.accessed-; /置换页面所在的物理块中访问标记设为-1 else/若存在该页for(int i=0; i<size; i+) if(blocki.pagenum != -1) /物理块不空printf(" %02d ",blocki.pagenum);cout<<"指令已经存在! 其物理块地址为:"<<&blockexist<<endl;for(int j=0; j<size; j+)blockj.accessed+; cout<<"缺页次数:"<<n<<endl; cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;void main( )int select; cout<<"请输入第一条指令号(1320): " Random( ); cout<<"*对应的调用页面队列*"<<endl; pagestring( ); docout<<"*"<<endl; cout<<"* 1:OPT 2:LRU 3:FIFO 4:退出 *"<<endl; cout<<"*"<<endl; cout<<" 请选择一种页面置换算法:" cin>>select; cout<<"*"<<endl; init( ); switch(select) case 1:cout<<"最佳置换算法OPT:"<<endl; cout<<"*"<<endl; OPT( ); break; case 2:cout<<"最近最久未使用置换算法LRU:"<<endl; cout<<"*"<<endl; LRU( ); break; case 3:cout<<"先进先出置换算法FIFO:"<<endl;cout<<"*"<<endl;FIFO( ); break; default: ; while(select!=4);4 运行结果运行程序根据提示先输入一个指令号（1-319），运行结果如下：选择一种置换算法，运行结果如图：再次选择置换算法，结果如图：再次选择置换算法，结果如图：运行完毕，退出程序：4实验过程中遇到的问题及解决方案 在对置换算法进行设计的时候，由于对算法的原理理解不深刻，导致编写算法错误，然后从新从教程深入理解，请教同学，上网查资料才写出正确的算法。编写程序是以0表示空闲物理块，不论什么时候都被换出，上网查资料发现0是页面标号不能用来表示空闲物理块，然后改为用-1表示空闲物理块。等等，在这次设计中遇到了不少的问题，大多是对编程语言不熟悉造成的，不过最终都一一解决了，收益良多。5课程设计总结通过本次操作系统课程设计，使我对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，加深了对OPT、LRU、FIFO三种置换算法的原理的了解，同时了解虚拟存储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。本实验的难点之一在于如何用c语言按要求模拟生成随机指令，即50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分，小组花了大量时间讨论和研究该算法，并参考了相关的资料、运用了随机函数，最终通过一个函数Random( )予以实现。第二，如何较好地模拟出先进先出算法（FIFO）、最近最少使用算法（LRU）也花费了较多时间。在本次设计过程中，用到了许多C+的基本知识和操作系统的基本原理，是对平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。在设计的过程中我们发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。总之，通过该实验，使我学到很多知识以及认识到实践的重要性。也使我了解到编写程序不是首要任务，而是一种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简洁的流程设计，这样可以达到事半功倍的效果。实验二 Linux的安装及用户接口1实验目的（1） 了解Linux的发行版本以及Linux系统对硬件资源的要求，掌握Linux系统的安装方法，会使用Disk Druid程序进行分区。熟悉Linux系统的启动、登录、重启和关闭。（2） 学习和掌握关于文件操作、目录操作、磁盘操作、系统管理等基本命令。使用Linux系统的图形界面进行系统的配置和管理，掌握用vi编辑文本文件。（3） 掌握shell启动的方法，熟悉shell命令的功能和使用方法，shell变量的特点和应用。掌握利用shell的控制结构编写程序，熟练进行shell程序的调试。2实验内容1Linux安装（1）Linux系统的获取和制作以Red Hat Linux9.0为例，从ftp:/202.196.160.10/linux/ISO/redhat/9.0/下载其iso映像文件，制作Red Hat Linux系统的安装光盘。（2）设置CMOS由光盘启动 启动机器，按Del进入CMOS，设置机器由CD-ROM启动，保存退出。（3）Linux系统的安装插入第一张安装盘启动机器安装系统。进入安装界面后，按提示逐步安装系统。包括图形界面或文本界面的选择、光盘的检测、语言的选择、键盘鼠标的配置、安装类型的选择（个人桌面、工作站、服务器、定制）、磁盘分区设置（自动、手工分区，见第4个实验内容）、引导装载程序（GRUB、LILO）的配置、网络环境的配置、防火墙的配置、时区配置、设置根口令（需牢记）、选择安装包、创建引导盘、配置视频卡、配置显示器。（4）磁盘分区设置用Disk Druid为Linux系统分区。Linux至少需要主分区和交换分区两个分区。主分区存放根目录下的文件系统，挂载点为/，文件类型为ext3，大小可以根据需要设定。交换分区文件类型为swap，不需设置挂载点。交换分区的大小一般为内存的2倍。（5）首次启动的相关配置首次启动的相关配置包括，设置用户帐号、设置系统的时间和日期、声卡设置、设置Red Hat网络、安装额外的软件或者文档。（6）系统的登录、注销和关闭在XWindow图形界面输入用户名和口令以图形化方式登录，进入图形化桌面。root用户的用户名为root。若安装时选择控制台登录，则以文本模式登录。注销可以取消当前用户的登录，重新回到登录前的状态。图形界面可以通过主菜单下的注销命令也可以按Ctrl+Alt+Backspace注销。命令行方式输入logout注销用户。图形界面通过主菜单下的关闭命令管理系统。命令行方式执行halt或者shutdown命令关闭系统。2.Linux命令以图形化方式登录Linux系统，在图形化桌面单击鼠标右键，选新建终端命令进入Linux字符界面，练习Linux命令。也可以在Windows环境通过telnet远程登录Linux服务器。练习文件操作命令、目录操作命令、基本的系统管理命令、磁盘操作命令及其他相关命令，使用Linux系统图形界面，练习使用vi命令。3. shell程序设计（1）菜单设计要求根据选择可以实现查看目录内容，文件内容的显示，文件的删除功能。（2）文件备份和恢复（3）求任意n个整数的累加和。3实验步骤1）Linux安装 1. 插入archlinux安装关盘,并设置计算机为光驱优先启动 2. 进入archlinux livecd系统,并用root用户登录.，执行 setup 命令开始安装.3. 用Disk Druid为系统分区，进行分区设置；4. 将GRUB放在硬盘第一个分区的superblock里.5. 添加普通用户,和设置root用户密码.6. 配置网络等相关设置.7. 系统登录、注销和关闭。2）Linux命令a: 练习文件操作命令ls cat more less cp rm mv tar gzip unzip is命令cat和more命令cp rm mv tar gzip unzip命令待添加的隐藏文字内容3b: 练习目录操作命令pwd mkdir rmdir cdpwd mkdir命令c: 练习基本的系统管理命令 chmod chgrp chown useradd userdel passwdchmod chgrp chown命令d: 练习磁盘操作命令 df du usb e: 练习其他相关命令 find grep ps kill who echo cal date clear man rpmgrep命令kill命令f: 使用Linux系统图形界面g: 练习使用vi命令3）shell程序设计（1）菜单设计要求根据选择可以实现查看目录内容，文件内容的显示，文件的删除等功能。#！/bin/shclearecho “please choose 1,2,3or 0”echo “1: View the directory”echo “2: Display a file”echo “3: Delete a file”echo “0: Quit the program”read choicecase $choice in1) ls -l;2)echo “Name of file to display?”read filenamecat $filename;3)echo “Name of file to delete?”read filenamerm $filename;4)echo “Quit now”#退出shellexit 0;esac（2）文件备份和恢复#！/bin/shclear#输入要备份的目录名echo “Please input the directory name:”#读目录名read directory#判断是否是目录if -d “$ directory”;thenecho”$directory is a directory”fi#进入目录cd $directory#备份和恢复菜单，1备份，2恢复，0退出echo “please choose 1,2or 0”echo “1: Backup directory”echo “2: Restore directory”echo “0: Quit the program”read choicecase $choice in1）tar zcvf /tmp/backup.tar.gz $directory;2)# 请恢复功能$cat >re.shcd $directorycpio I $1 </dev/fd()d0)exit 0;esac（3）求任意n个整数的累加和。for i in 1 2 3 4 ndos=s+$idoneecho “sum=$s”（4）运行结果4实验过程中遇到的问题及解决方案Linux系统安装过程中下载映像文件，用虚拟光驱DAEMON Tools Lite来实现安装，同时，linux系统不是我们所熟悉的系统，所以在安装的过程中有一定的难度。Linux命令仿照windows下命令实现方式，来通过命令实现对系统的基本操作shell编程过程中，shell命令与c语言有相似的地方也有很多不同，由于c语言经常使用，在编程是往往用错命令与语法，因此在编写好程序后我都会自己检查一遍，然后再让同学帮助检查。5课程设计总结通过此次课程设计，对所学内容及操作系统有了更深入的了解：深入认识到操作系统所起的作用，以及它的发展极大的推动了计算机的发展，以使操作更简单，用户得到更好的便利；更深刻的理解多道程序系统中进程的引入，为实现资源充分利用及用户对计算机效率的要求。以及在如何解决进程的并发执行来实现多个程序协调、融洽的运行。本次课程设计的题目只涉及课程中的一部分。通过课程设计，对操作系统原理有了更深层次的理解。对Linux系统内核有了全面认识，以及深入了解。对操作系统实现处理机管理功能、存储器管理功能、设备管理功能、文件管理功能等功能时，所采取的各种方法和策略进行了全面学习，为今后的学习奠定了很好的基础。 指 导 教 师 评 语 评分 指导教师 年 月 日