实 验 报 告
实验课程： 计算机操作系统 学生姓名： 舒娅 学 号： 6100511015 专业班级： 管理科学与工程类111班
2013年 6 月 7 日
1---28
目 录
实验一 Linux的文件系统和基本操作命令 ..................................................................... 3 实验二 熟悉Linux开发环境 ............................................................................................... 5 实验三 Linux进程创建和控制............................................................................................ 8 实验四 进程的软中断通信和管道通信 ........................................................................... 10 实验五 进程间通信 ............................................................................................................... 13 实验六 存储管理 .................................................................................................................... 18
2---28
南昌大学实验报告
学生姓名： 舒娅 学 号： 6100511015 专业班级： 管理科学与工程类111班 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩：
√ 实验一 Linux的文件系统和基本操作命令
（一）实验目的
1、熟练掌握Linux的登陆和退出过程
2、熟练掌握基本的Linux文件与目录操作命令 3、熟练掌握基本的LINUX系统管理命令 （二）实验基本要求
1、了解LINUX根文件系统目录内容； 2、了解应用程序和配置文件关系 3、熟悉LINUX系统配置 （三）基本实验条件
PC兼容机、交换机、Red Hat Linux 9.0 （四）实验内容
(五) 实验数据及处理结果
1、登陆与关机
（1）登陆
在login：后输入
user机号↙（这表示回车键） 在password：后输入
123456↙（注意在屏幕上不显示）
出现$提示符，表示正常进入普通用户状态。 （2）关机 在$后输入 halt↙
等屏幕上显示System halted时，再关电源。 2、文件与目录操作基本命令 （1）、用户工作目录
每个用户都有一个与用户名相同的用户自己能完全操作（读、写、删）的子目录，如：/home/user27，就是用户user27的工作目录。 （2）、man命令
man命令用于查看Linux各种命令的使用说明，用法如下： man 命令名↙
（3）、参考背景资料或利用man命令，熟悉掌握以下基本命令的使用方法：
ls；显示目录内容 cd；切换目录 cp；文件复制
mkdir；创建指定的名称的目录
3---28
rmdir；删除空目录
mv；移动档案与目录或更名 rm；删除不需要的目录及文件 cat；将文档中的内容显示出来
more；以一页一页的显示方便使用者逐页阅读，而最基本的指令就是按空格往
下一页显示，按 b 键就会往回一页显示
less；less 与 more 类似，但使用 less 可以随意浏览文件 file；检测文件类型
du；显示目录或文件的大小
df；检查文件系统的磁盘空间占用情况 mount；加载指定的文件系统 umount；卸除文件系统
chmod；改变一个或多个文件的存取模式
chown；变更文件或目录的拥有者或所属群组。 pwd；查看”当前工作目录“的完整路径 which；查看可执行文件的位置 3、系统管理基本命令
Linux是真正的多用户多任务操作系统，任何人使用Linux系统时都要以用某个帐号先进行登陆，帐号名就是用户名。
用户的管理必须在root用户权限下进行操作，请务必小心！！！ 参考背景资料或利用man命令，熟悉掌握以下命的使用方法： useradd；建立用户帐号
userdel；删除用户帐号与相关的文件 passwd；修改密码
finger；查询一台主机上的登录账号的信息 groupadd；将新组加入系统 groupdel；删除群组
ps；将某个时间点的程序运作情况撷取下来 nice；设置优先权
renice；调整程序优先级 kill；终止命令
top；动态观察程序的变化 free；显示内存的使用情况 cal；显示当年的日历
date；显示、修改系统日期时间 uname；显示当前操作系统名称 login；登入系统
logout；用户注销/挂起 exit；退出目前的shell halt；关闭系统
shutdown；安全地关闭或重启Linux系统
4---28
南昌大学实验报告
学生姓名： 舒娅 学 号： 6100511015 专业班级： 管科111 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩：
√ 实验二 熟悉Linux开发环境
（一）实验目的
1、学会使用vi编辑器的使用 2、熟悉Linux开发环境 （二）实验基本要求
1、熟悉LINUX平台下Ｃ语言程序设计方法； 2、编写hello程序；
3、掌握vi编辑器, gdb调试器，gcc编译器 （三）基本实验条件
PC兼容机、交换机、Red Hat Linux 9.0 （四）、实验内容：
1、vi编辑器的使用
vi是visual interface的简称，它是Linux上一个最常用的全屏幕文本编辑器，vi几乎与Unix的历史一样悠久，vi几乎存在于所有的类Unix操作系统中，使用vi就如同使用Linux命令一样方便。vi功能强大，有非常丰富的操作命令，它可以执行输出、删除、查找、替换、块操作等众多文本操作，而且用户可以根据自己的需要对其进行定制，这是其他编辑器所没有的。我们既可以利用其强大的功能进行非常灵活的个性化操作，又可以只掌握几个简单的命令来完成基本的编辑操作。
Linux下还有很多的编辑器，如行文本编辑器ex和ed，全屏幕编辑器joe和mc，还有视窗环境下的编辑器Gedit, GNU Emacs、XEmacs和Kate等，或是使用KDevelop，它是在Linux中的X Window下执行的C/C++集成开发环境。大家可以选择自己喜欢的编辑器来完成C语言程序的编辑工作，本实验只介绍vi编辑器的简单使用方法。 a)、进入vi
在系统提示符（$）后输入vi及文件名称后，就进入vi全屏幕编辑画面： $ vi myfile↙
此时vi处于命令模式，命令模式下有许多操作命令，如“x”删除光标所在位置的字符，“dd”删除光标所在位置的一行，“i”进入插入模式等等。我们只需掌握在命令模式下按i键进入插入模式即可。在插入模式下就可以进行基本的编辑操作，用方向键移动光标，用“←”键或“Delete”键删除光标前或光标后的内容，用“Enter”键换行。 b)、退出vi及保存文件
在插入模式下按ESC键就进入行底模式，底行模式下也有许多命令，如“q”是退出，“q!”是强制不存盘退出等等，需要注意的是，在底行模式下要先按“：”键，然后在冒号后再输入要操作的命令，最后按回车键来执行命令。我
5---28
们需要掌握的底行模式基本命令有： “w”（只存盘不退出vi）；“w filename”（将内容以指定的文件名filename保存）；“wq”（存盘并退出vi）；“q!”（不存盘强制退出vi）。上述vi基本操作可简单总结如下： 2、Linux下C语言程序的编译过程 a、在用户主目录下用vi编辑C语言源程序（源程序已附后），如：$vi hello.c。 b、用gcc编译C语言源程序：$gcc ./hello.c -o example 这里gcc是Linux下的C语言程序编译器，./hello.c表示待编译的源文件是当前工作目录下的hello.c，-o example表示编译后产生的目标代码文件名为example。
c、若编译不正确，则进入vi修改源程序，否则，运行目标代码：$./example 注意：
a、如果用户shell的环境变量设置得当，可省略“./”。 b、这只是gcc最最基本的用法。
c、若源程序用C++编写，则应有以下语句： „„
using namespace std； int main() „„
同时，编译时将gcc换成g++即可。
（五）、实验结果
请问hello.c的功能是什么？ hello.c的功能是求数n的阶层
6---28
附：hello.c源程序 ＃i nclude int n,a[200],carry,temp,i,j,digit = 1; printf(\"Please input n:\"); scanf(\"%d\ for( i = 2; i <= n; ++i) { for( j = 1, carry = 0; j <= digit; ++j) { temp = a[j-1] * i + carry; a[j-1] = temp % 10; carry = temp / 10; } while(carry) { a[++digit-1] = carry % 10; carry /= 10; } } printf(\"Result is:\\n%d ! = \ for( i = digit; i >=1; --i) { printf(\"%d\ } printf(\"\\n\"); } 7---28 南昌大学实验报告 学生姓名： 学 号： 专业班级： 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩： √ 实验三 Linux进程创建和控制 （一）实验目的 1、加深对进程概念的理解，明确进程和程序的区别； 2、观察并发执行的现象，进一步认识并发执行的实质。 3、进一步熟悉Linux的基本命令和开发环境。 （二）实验基本要求 1、熟悉UNIX平台下Ｃ语言程序设计方法； 2、编写进程的创建程序； 3、观察进程的执行情况，掌握fork()系统调用。 （三）基本实验条件 PC兼容机、交换机、Red Hat Linux 9.0、gcc 编译器。 （四）实验内容 1、 用4个基本系统调用实现进程的创建、执行和自我终止： ①fork()。创建一个子进程。用它创建的子进程是fork调用者进程（即父进程）的复制品，即进程映象。除了进程标识数以及与进程特性有关的一些参数外，其它与父进程相同，与父进程共享文本段和打开的文件，并都受进程调度程序的调度。 如果创建进程失败，则fork()返回值为-1：若创建进程成功，则从父进程返回值是子进程号，从子进程返回的值是0，返回值在R0。m=fork()。 ②wait()。父进程处于阻塞（或等待）状态，等待子进程执行完成终止后继续工作。其返回值R0为等待子进程的子进程号。n=wait()。 ③exit()。子进程自我终止，释放所占资源，通知父进程可以删除自己。此时它的状态变成P_state=SZOMB。 ④getpid()。获得进程的标识数（进程号），一般是正整数。P=getpid()。 〈程序设计〉 1．编写一个程序，父进程生成一个子进程，父进程等待子进程wait()，子进程执行完成后自我终止exit()，并唤醒父进程。父、子进程执行时打印有关信息。 2． 编写一个程序，输入两个整数并求和输出，然后创建一个子进程，当进程调度程序调度到父进程或子进程时特输出不同的信息。 （五）实验结果 8---28 编辑 程序一 progress.c 编译和运行 progress.c 9---28 Sum.c的运行结果 附： 1.参考程序 main() { int i,j,k; if (i=fork()) // 非零值 { j=wait(); printf(“Parent process!\\n”); printf(“i=%d k=%d\\n,i,k); } else{ k=getpid(); printf(“Child process!\\n”); printf(“i=%d k=%d\\n,i,k); } } 附： 2.参考程序例 main() { int i,j,k,sum; scanf(“%d%d”,&j,&k); sum=j+k; printf(“sum=%d\\n”,sum); while((i=jork())==-1) printf(“i=%d\\n,i); if (i) printf(“It is parent process!\\n”); else printf(“It is Child process!\\n”); } 10---28 南昌大学实验报告 学生姓名： 舒娅 学 号： 6100511015 专业班级： 管科111 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩： √ 实验四 进程的软中断通信和管道通信 （一）实验目的 1、进一步加深对进程概念的理解。 2、了解Linux系统中进程通信的基本原理。 （二）实验基本要求 1、熟悉Linux平台下Ｃ语言程序设计方法； 2、编写进程通信程序； 3、观察进程的执行情况，掌握pipe()系统调用。 （三）基本实验条件 PC兼容机、交换机、Red Hat Linux 9.0、gcc 编译器。 （四）实验内容 1、 进程的“软中断”通信 它可用于同一用户的进程之间通信。其方式是：一个进程通过系统调用kill(pid,sig) 向同一用户的其它进程pid发送一个软中断信号：另一进程通过系统调用signal(sig,func)捕捉到信号sig后，执行予先约定的动作func，从而实现这两个进程间的通信。 ①发送信号kill(pid,sig)，本进程将指定信号sig发送给指定进程pid，其中参数为pid进程号，pid与sig均为整数值。 ②接收信号signal(sig,func)，本进程接收到其它进程发送给它的信号后，完成指定的功能func。func一般是函数。 〈程序设计〉 编写一个程序，父进程生成子进程，父进程发送信号并等待，子进程接收信号并完成某种功能，然后自我终止并唤醒父进程。 2、进程管道的通信 建立进程间的管道，格式为： pipe(fd); int fd[2]; 其中，fd[1] 是写端，向管道中写入; fd[0] 是读端，从管道中读出; 本质上将其当作文件处理。进程间可通过管道，用write与read来传递数据，但write与read不可以同时进行，在管道中只能有4096字节的数据被缓冲。 〈程序设计〉 编写一个程序，建立一个pipe，同时父进程产生一个子进程，子进程向pipe中写入一个字符串，父进程从中读出该字符串，并每隔3秒种输出打印一次。 （五）实验结果 11---28 附： 1.参考程序 int func(); main() { int i,j: signal(17,func); if(i=fork()) { printf(“Parent: Signal 17 will be send to Child! \\n”); kill(i,17); wait(0); printf(“Parent: finished! \\n”)” } else{ sleep(10); printf(“Child: A signal from my Parent is received! \\n”) exit(); } } func() {printf(“It is signal 17 processing function! \\n”;) 执行结果如下： Parent: Signal 17 will be send to Child! It is signal 17 processing function! Child: A signal from my Parent is received! 12---28 Parent: finished! 附：2.参考程序 main() { int x,fd{2}; char S[30]; pipe(fd); for (;;) { x=fork(); if (x==0) {sprintf(S,”Good-night!\\n”); write(fd[1],S,20); sleep(3); exit(0); } else{wait(0); read(fd[0],S,20); printf(“**********\\n”,S); } } } 13---28 南昌大学实验报告 学生姓名： 舒娅 学 号： 6100511015 专业班级：管科111 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩： √ 实验五 进程间通信 （一）实验目的 了解和熟悉Linux支持的消息通信机制和共享存储区通信机制 （二）实验基本要求 1、利用msgget()、msgsnd()、msgrev()、msgctl()等系统调用编写消息的发送和接收的程序； 2、利用shmget()、sgmat()、smgdt()、shmctl()等系统调用编写消息的发送和接收的程序。 （三）主要仪器设备及器材 PC兼容机、交换机、Red Hat Linux 9.0、gcc 编译器。 （四）实验内容 1、消息的创建，发送和接收 〈任务〉 使用系统调用msgget( ), megsnd( ), msgrev( )及msgctl()编制一长度为1K的消息发送和接收的程序 。 〈程序设计〉 （1） 为了便于操作和观察结果，用一个 程序为“引子”，先后fork( )两个子进程， SERVER和CLIENT，进行通信。 （2） SERVER端建立一个Key为75的消息队列，等待其他进程发来的消息。当遇到类型 为1的消息，则作为结束信号，取消该队列，并退出SERVER 。SERVER每接收到一个消息后显示一句“(server)received”。 （3） CLIENT端使用Key为75的消息队列，先后发送类型从10到1的消息，然后退出。 最后的一个消息，既是 SERVER端需要的结束信号。CLIENT每发送一条消息后显示一句“(client)sent”。 （4） 父进程在 SERVER和 CLIENT均退出后结束。 2、共享存储区的创建,附接和断接 <任务> 使用系统调用shmget(),sgmat(),smgdt(),shmctl()编制一个与上述功能相同的程序. <程序设计> (1)为了便于操作 和观察结果，用一个 程序为“引子”，先后fork( )两个子进程，SERVER 和 CLIENT，进行通信。 (2)SERVER端建立一个KEY为75的共享区,并将第一个字节置为-1.作为数据空的标志.等待其他进程发来的消息.当该字节的值发生变化时,表示收到了该消息,进行处理.然后再次把它 的值设为-1.如果遇到的值为0,则视为结束信号,取消该队列,并退出SERVER.SERVER每接 收到一次数据后显示”(server)received”. (3)CLIENT端建立一个为75的共享区,当共享取得第一个字节为-1时, Server端空闲,可 14---28 发送 请求. CLIENT 随即填入9到0.期间等待Server端再次空闲.进行完这些操作后, CLIENT 退出. CLIENT每发送一次数据后显示”(client)sent”. (4)父进程在SERVER和CLIENT均退出后结束. （五）实验结果 附：1.参考程序 #include #define MSGKEY 75 /*定义关键词MEGKEY*/ struct msgform /*消息结构*/ { long mtype; char mtexe[1030]; /*文本长度*/ }msg; int msgqid,i; void CLIENT( ) { int i; msgqid=msgget(MSGKEY,0777); for(i=10;i>=1;i--) { msg.mtype=i; 15---28 printf(\"(client)sent\\n\"); msgsnd(msgqid,&msg,1024,0); /*发送消息msg入msgid消息队列*/ } exit(0); } void SERVER( ) { msgqid=msgget(MSGKEY,0777|IPC_CREAT); /*由关键字获得消息队列*/ do { msgrcv(msgqid,&msg,1030,0,0); /*从队列msgid接受消息msg*/ printf(\"(server)receive\\n\"); }while(msg.mtype!=1); /*消息类型为1时，释放队列*/ msgctl(msgqid, IPC_RMID,0); exit(0); } main() { if(fork()) SERVER(); else CLIENT( ); wait(0); wait(0); } <结果> 从理想的结果来说，应当是每当Client发送一个消息后，server接收该消息，Client再发送下一条。也就是说“(Client)sent”和“(server)received”的字样应该在屏幕上交替出现。实际的结果大多是，先由 Client 发送两条消息，然后Server接收一条消息。此后Client Server交替发送和接收消息.最后一次接收两条消息. Client 和Server 分别发送和接收了10条消息,与预期设想一致 <分析> message的传送和控制并不保证完全同步,当一个程序不再激活状态的时候,它完全可能继续睡眠,造成上面现象,在多次send message 后才 receive message.这一点有助于理解消息转送的实现机理. 附：2.参考程序 #include #define SHMKEY 75 /*定义共享区关键词*/ int shmid,i; int *addr; 16---28 CLIENT() { int i; shmid=shmget(SHMKEY,1024,0777); /*获取共享区，长度1024，关键词SHMKEY*/ addr=shmat(shmid,0,0); /*共享区起始地址为addr*/ for(i=9;i>=0;i--) { while(*addr!= -1); printf(\"(client)sent\\n\"); /*打印（client）sent*/ *addr=i; /*把i赋给addr*/ } exit(0); } SERVER() { shmid=shmget(SHMKEY,1024,0777|IPC_CREAT); /*创建共享区*/ addr=shmat(shmid,0,0); /*共享区起始地址为addr*/ do { *addr=-1; while(*addr==-1); printf(\"(server)received\\n\"); /*服务进程使用共享区*/ } while(*addr); shmctl(shmid,IPC_RMID,0); exit(0); } main() { if(fork())SERVER(); if(fork())CLIENT(); wait(0); wait(0); } <结果〉 运行的结果和预想的完全一样。但在运行的过程中，发现每当client发送一次数据后，server要等大约0.1秒才有响应。同样，之后client又需要等待大约0.1秒才发送下一个数据。 <分析〉 出现上述的应答延迟的现象是程序设计的问题。当client端发送了数据后，并没有任 17---28 何措施通知server端数据已经发出，需要由client的查询才能感知。此时，client端并没有放弃系统的控制权，仍然占用CPU的时间片。只有当系统进行调度时，切换到了server进程，再进行应答。这个问题，也同样存在于server端到client的应答过程之中。 3 比较两种消息通信机制中的数据传输的时间 由于两种机制实现的机理和用处都不一样，难以直接进行时间上的比较。如果比较其性能，应更加全面的分析。 (1) 消息队列的建立比共享区的设立消耗的资源少.前者只是一个软件上设定的问题,后 者需要对硬件操作,实现内存的映像,当然控制起来比前者复杂.如果每次都重新进行队列或共享的建立,共享区的设立没有什么优势。 (2) 当消息队列和共享区建立好后,共享区的数据传输,受到了系统硬件的支持,不耗费 多余的资源;而消息传递,由软件进行控制和实现,需要消耗一定的CPU资源.从这个意义上讲,共享区更适合频繁和大量的数据传输. (3) 消息的传递,自身就带有同步的控制.当等到消息的时候,进程进入睡眠状态,不再消 耗CPU资源.而共享队列如果不借助其他机制进行同步,接受数据的一方必须进行不断的查询,白白浪费了大量的CPU资源.可见消息方式的使用更加灵活. 18---28 南昌大学实验报告 学生姓名： 舒娅 学 号： 6100511015 专业班级： 管科111 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩： √ 实验六 存储管理 （一）实验目的 通过请求页式存储管理页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理页面置换算法。 （二）实验基本要求 1、设计一个虚拟存储区和内存工作区； 2、计算FIFO、LRU、OPT、LFU、NUR算法的访问命中率； 3、根据实验结果比较几种算法的差别。 （三）主要仪器设备及器材 PC兼容机、交换机、Red Hat Linux 9.0、gcc 编译器。 （四）实验内容 任务：设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 （1）先进先出算法（FIFO） （2）最近最少使用算法（LRU） （3）最佳淘汰算法（OPT） （4）最少访问页面算法（LFU） （5）最近最不经常使用算法（NUR） 命中率=（1-页面失效次数）/页地址流长度 1、数据结构 （1）页面类型 typedef struct{ int pn,pfn,counter,time; }pl_type; 其中pn为页号,pfn为面号，counter为一个周期内访问该页面次数，time为访问时间。 （2）页面控制结构 struct pfc_struct{ int pn,pfn; struct pfc-struct *next;}; typedef struct pfc_struct pfc_type; pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; 其中pfc[total_vp]定义用户进程虚页控制结构， *freepf_head为空页面头的指针， *busypf_head为忙页面头的指针， *busypf-tail为忙页面尾的指针。 2、函数定义 （1）、void initialize():初始化函数，为每个相关页面赋值。 19---28 （2）、void fifo(): （3）、void lru(): （4）、void opt(): （5）、void lfu(): （6）、void nur(): 3、变量定义 （1）、int a[total_instruction]:定义指令流数组。 （2）、int page[total_instruction]:每条指令所属页号。 （3）、int offset[total-instruction]:每页装入10条指令后取模运算页号偏移值。 （4）、int total_pf:用户进程的页面数。 （5）、int diseffect:页面失效次数。 （五）实验报告 附：参考程序 #include #define TRUE 1 #define FALSE 0 #define INVALID -1 #define NUL 0 20---28 #define total_instruction 320 /*指令流长*/ #define total_vp 32 /*虚页长*/ #define clear_period 50 /*清零周期*/ typedef struct{ /*页面结构*/ int pn,pfn,counter,time; }pl_type; pl_type pl[total_vp]; /*页面结构数组*/ struct pfc_struct{ /*页面控制结构*/ int pn,pfn; struct pfc_struct *next; }; typedef struct pfc_struct pfc_type; pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; int diseffect,a[total_instruction]; int page[total_instruction], offset[total_instruction]; void initialize(); void FIFO(); void LRU(); void OPT(); void LFU(); void NUR(); int main() { int S,i; srand((int)getpid()); S=(int)rand()%390; for(i=0;i a[i+3]=a[i+2]+1; /*执行后地址指令*/ S=(int)rand()%390; } for(i=0;i 21---28 offset[i]=a[i]%10; } for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/ { printf(\"%2d page frames\ FIFO(i); LRU(i); OPT(i); LFU(i); NUR(i); printf(\"\\n\"); } return 0; } void FIFO(total_pf) /*FIFO(First in First out)ALGORITHM*/ int total_pf; /*用户进程的内存页面数*/ { int i; pfc_type *p, *t; initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/ for(i=0;i diseffect+=1; /*失效次数*/ if(freepf_head==NUL) /*无空闲页面*/ { p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/ freepf_head=busypf_head; freepf_head->next=NUL; busypf_head=p; } p=freepf_head->next; /*按方式调新页面入内存页面*/ freepf_head->next=NUL; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NUL) busypf_head=busypf_tail=freepf_head; 22---28 else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf(\"FIFO:%6.4F\} void LRU(total_pf) int total_pf; { int min,minj,i,j,present_time; initialize(total_pf);present_time=0; for(i=0;i diseffect++; if(freepf_head==NUL) /*无空闲页面*/ { min=32767; for(j=0;j min=pl[j].time; minj=j; } freepf_head=&pfc[pl[minj].pfn]; pl[minj].pfn=INVALID; pl[minj].time=-1; freepf_head->next=NUL; } pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].time=present_time; freepf_head=freepf_head->next; } else pl[page[i]].time=present_time; present_time++; } 23---28 printf(\"LRU:%6.4f\ } void NUR(total_pf) int total_pf; { int i,j,dp,cont_flag,old_dp; pfc_type *t; initialize(total_pf); dp=0; for(i=0;i diseffect++; if(freepf_head==NUL) /*无空闲页面*/ { cont_flag=TRUE;old_dp=dp; while(cont_flag) if(pl[dp].counter==0&&pl[dp].pfn!=INVALID) cont_flag=FALSE; else { dp++; if(dp==total_vp) dp=0; if(dp==old_dp) for(j=0;j pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } else pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;j } printf(\"NUR:%6.4f\ } void OPT(total_pf) /*OPT(Optimal Replacement)ALGORITHM*/ int total_pf; { int i,j,max,maxpage,d,dist[total_vp]; pfc_type *t; initialize(total_pf); for(i=0;i diseffect++; if(freepf_head==NUL) { for(j=0;j for(j=i+1;j max=-1; for(j=0;j freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NUL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } 25---28 printf(\"OPT:%6.4f\ } void LFU(total_pf) /*LFU(leat Frequently Used) ALGORITHM*/ int total_pf; { int i,j,min,minpage; pfc_type *t; initialize(total_pf); for(i=0;i diseffect++; if(freepf_head==NUL) { min=32767; for(j=0;j min=pl[j].counter; minpage=j; } pl[j].counter=0; } freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; freepf_head->next=NUL; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } else pl[page[i]].counter++; } printf(\"LFU:%6.4f\ } void initialize(total_pf) /*初始化相关数据结构*/ int total_pf; /*用户进程的内存页面数*/ { int i; diseffect=0; 26---28 for(i=0;i pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/ } for(i=1;i pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/ } <结果一：〉 4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.2812 5 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.3094 6 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.3344 7 page framesFIFO:0.3563LRU:0.3563OPT:0.4031LFU:0.3563NUR:0.3500 8 page framesFIFO:0.3937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.3719 9 page framesFIFO:0.4219LRU:0.4094OPT:0.4844LFU:0.4156NUR:0.4062 10 page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.4250 11 page framesFIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.4656 12 page framesFIFO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.4875 13 page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.5437 14 page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.5469 15 page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.5813 16 page framesFIFO:0.5781LRU:0.5938OPT:0.6813LFU:0.5719NUR:0.5969 17 page framesFIFO:0.5906LRU:0.6156OPT:0.6969LFU:0.6156NUR:0.6156 18 page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.6531 19 page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.6719 20 page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.6906 21 page framesFIFO:0.6906LRU:0.7094OPT:0.7688LFU:0.6969NUR:0.7188 22 page framesFIFO:0.7125LRU:0.7219OPT:0.7969LFU:0.7156NUR:0.7344 23 page framesFIFO:0.7156LRU:0.7406OPT:0.8125LFU:0.7250NUR:0.7812 24 page framesFIFO:0.7281LRU:0.7625OPT:0.8187LFU:0.7406NUR:0.7719 25 page framesFIFO:0.7469LRU:0.7750OPT:0.8344LFU:0.7594NUR:0.8000 26 page framesFIFO:0.8125LRU:0.8000OPT:0.8500LFU:0.7812NUR:0.8063 27 page framesFIFO:0.8313LRU:0.8187OPT:0.8594LFU:0.8031NUR:0.8281 28 page framesFIFO:0.8438LRU:0.8375OPT:0.8688LFU:0.8344NUR:0.8469 29 page framesFIFO:0.8688LRU:0.8531OPT:0.8750LFU:0.8562NUR:0.8562 27---28 30 page framesFIFO:0.8781LRU:0.8719OPT:0.8781LFU:0.8750NUR:0.8688 31 page framesFIFO:0.8938LRU:0.8750OPT:0.8844LFU:0.8844NUR:0.8906 32 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000 <分析> 从上述结果可知，在内存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7~18个页面之间时，5种算法的访内命中率大致在35%~60%之间变化。但是，FIFO算法与OPT算法之间的差别一般在6~10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。 比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本问题，在15页之前，FIFO的命中率比LRU的高。 <结果二：> 4 page framesFIFO:0.2594LRU:0.2562OPT:0.2687LFU:0.2437NUR:0.2625 5 page framesFIFO:0.3000LRU:0.3000OPT:0.3000LFU:0.2969NUR:0.2875 6 page framesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.3281 7 page framesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.3469 8 page framesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.3781 9 page framesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.4125 10 page framesFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.4406 11 page framesFIFO:0.4531LRU:0.4688OPT:0.4594LFU:0.4281NUR:0.4656 12 page framesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.4938 13 page framesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.5312 14 page framesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.4938NUR:0.5500 15 page framesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.5563 16 page framesFIFO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.5844 17 page framesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.6031 18 page framesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.6250 19 page framesFIFO:0.6312LRU:0.6156OPT:0.6438LFU:0.6219NUR:0.6438 20 page framesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438NUR:0.6750 21 page framesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.6937 22 page framesFIFO:0.7000LRU:0.6781OPT:0.7125LFU:0.6813NUR:0.6844 23 page framesFIFO:0.7156LRU:0.6906OPT:0.7312LFU:0.7188NUR:0.6969 24 page framesFIFO:0.7438LRU:0.7219OPT:0.7531LFU:0.7438NUR:0.7469 25 page framesFIFO:0.7594LRU:0.7562OPT:0.7656LFU:0.7656NUR:0.7719 26 page framesFIFO:0.7750LRU:0.7812OPT:0.7937LFU:0.7781NUR:0.7781 27 page framesFIFO:0.8125LRU:0.7969OPT:0.8094LFU:0.8125NUR:0.7969 28 page framesFIFO:0.8344LRU:0.8313OPT:0.8281LFU:0.8313NUR:0.8406 29 page framesFIFO:0.8406LRU:0.8594OPT:0.8531LFU:0.8375NUR:0.8406 30 page framesFIFO:0.8625LRU:0.8781OPT:0.8750LFU:0.8562NUR:0.8594 31 page framesFIFO:0.8812LRU:0.8812OPT:0.8906LFU:0.8781NUR:0.8656 32 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000 <分析> 从结果可以看出，FIFO的命中率竟然比OPT的还高。 28---28 因篇幅问题不能全部显示，请点此查看更多更全内容