实 验 报 告
实验课程： 计算机操作系统
学生姓名： 舒娅
学 号： 6100511015
专业班级： 管理科学与工程类111班
20##年 6 月 7 日
目 录
实验一 Linux的文件系统和基本操作命令... 3
实验二 熟悉Linux开发环境... 5
实验三 Linux进程创建和控制... 8
实验四 进程的软中断通信和管道通信... 10
实验五 进程间通信... 13
实验六 存储管理... 18
南昌大学实验报告
学生姓名：
舒娅
学 号：
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；创建指定的名称的目录
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系统
南昌大学实验报告
学生姓名：
舒娅
学 号：
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!”是强制不存盘退出等等，需要注意的是，在底行模式下要先按“：”键，然后在冒号后再输入要操作的命令，最后按回车键来执行命令。我们需要掌握的底行模式基本命令有： “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的阶层
附：hello.c源程序
＃i nclude <stdio.h>
main()
{
int n,a[200],carry,temp,i,j,digit = 1;
printf("Please input n:");
scanf("%d",&n); a[0] = 1;
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 ! = ",n);
for( i = digit; i >=1; --i)
{
printf("%d",a[i-1]);
}
printf("\n");
}
南昌大学实验报告
学生姓名：
学 号：
专业班级：
实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 实验成绩：
实验三 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． 编写一个程序，输入两个整数并求和输出，然后创建一个子进程，当进程调度程序调度到父进程或子进程时特输出不同的信息。
（五）实验结果
编辑 程序一 progress.c
编译和运行 progress.c
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”);
}
南昌大学实验报告
学生姓名：
舒娅
学 号：
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秒种输出打印一次。
（五）实验结果
附： 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!
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);
}
}
}
南昌大学实验报告
学生姓名：
舒娅
学 号：
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端空闲,可发送 请求. CLIENT 随即填入9到0.期间等待Server端再次空闲.进行完这些操作后, CLIENT 退出. CLIENT每发送一次数据后显示”(client)sent”.
(4)父进程在SERVER和CLIENT均退出后结束.
（五）实验结果
附：1.参考程序
#include <stdio.h>
#include <sys/types.h>
#include <sys/msg.h>
#include <sys/ipc.h>
#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;
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<sys/types.h>
#include<sys/msg.h>
#include<sys/ipc.h>
#define SHMKEY 75 /*定义共享区关键词*/
int shmid,i;
int *addr;
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端发送了数据后，并没有任何措施通知server端数据已经发出，需要由client的查询才能感知。此时，client端并没有放弃系统的控制权，仍然占用CPU的时间片。只有当系统进行调度时，切换到了server进程，再进行应答。这个问题，也同样存在于server端到client的应答过程之中。
3 比较两种消息通信机制中的数据传输的时间
由于两种机制实现的机理和用处都不一样，难以直接进行时间上的比较。如果比较其性能，应更加全面的分析。
(1) 消息队列的建立比共享区的设立消耗的资源少.前者只是一个软件上设定的问题,后者需要对硬件操作,实现内存的映像,当然控制起来比前者复杂.如果每次都重新进行队列或共享的建立,共享区的设立没有什么优势。
(2) 当消息队列和共享区建立好后,共享区的数据传输,受到了系统硬件的支持,不耗费多余的资源;而消息传递,由软件进行控制和实现,需要消耗一定的CPU资源.从这个意义上讲,共享区更适合频繁和大量的数据传输.
(3) 消息的传递,自身就带有同步的控制.当等到消息的时候,进程进入睡眠状态,不再消耗CPU资源.而共享队列如果不借助其他机制进行同步,接受数据的一方必须进行不断的查询,白白浪费了大量的CPU资源.可见消息方式的使用更加灵活.
南昌大学实验报告
学生姓名：
舒娅
学 号：
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():初始化函数，为每个相关页面赋值。
（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 <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NUL 0
#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<total_instruction;i+=1) /*产生指令队列*/
{
a[i]=S; /*任选一指令访问点*/
a[i+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(int)rand()%390; /*执行前地址指令m’*/
a[i+3]=a[i+2]+1; /*执行后地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("%2d page frames",i);
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<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
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;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4F",1-(float)diseffect/320);
}
void LRU(total_pf)
int total_pf;
{
int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲页面*/
{
min=32767;
for(j=0;j<total_vp;j++)
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
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++;
}
printf("LRU:%6.4f",1-(float)diseffect/320);
}
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<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
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<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NUL;
}
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<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f",1-(float)diseffect/320);
}
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<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID)
{
diseffect++;
if(freepf_head==NUL)
{
for(j=0;j<total_vp;j++)
if(pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{
max=dist[j];maxpage=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;
}
}
printf("OPT:%6.4f",1-(float)diseffect/320);
}
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<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID)
{
diseffect++;
if(freepf_head==NUL)
{
min=32767;
for(j=0;j<total_vp;j++)
{
if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{
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",1-(float)diseffect/320);
}
void initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{
int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/
}
for(i=1;i<total_pf;i++)
{
pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[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
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的还高。