实

　验

　报

　告

　 实验课程：

　计算机操作系统

　学生姓名：

　张虹

　学

　号：

　 6100409033

　 专业班级：

　电气信息类 III 091 班

　0 2010 年 年 2 12 月 月 8 18 日

　目录

　 操作系统安装及其接口环境 ............................. 2 编程实现银行家安全算法 ................................ 7 进程调度算法的实现 ................................... 16 存储管理的模拟实现 ................................... 22

　 告 南昌大学实验报告 ---操作系统安装及其接口环境 学生姓名：

　张虹

　学

　号：

　6100409033

　 专业班级：

　 电Ⅲ091 班

　 实验类型：□ 验证 ■ 综合 □ 设计 □ 创新

　 实验日期：

　实验成绩：

　 一、实验目的 熟悉 Windows//Linux 操作系统的安装过程与安装方法，并掌握该操作系统所提供的用户接口环境，并为后续实验做好编程环境准备。

　二、实验内容 1、熟悉 Windows//Linux 操作系统的安装过程与安装方法，并掌握该操作系统所提供的用户接口环境，通过系统提供的用户管理程序、查看系统中的用户情况、进程、线程、内存使用情况等，学会使用它进行监视进程的状况、系统资源的使用情况及用户情况。并为后续实验做好编程环境准备。

　2、用 C 语言编写一小段程序，使其可以通过某个系统调用来获得 OS 提供的某种服务。

　三、实验要求 1． 了解所安装的操作系统对软硬件资源的具体要求； 2． 机器最低硬件配置要求； 3． 操作系统所提供的用户接口环境的熟悉； 4． 了解主要 BIOS CMOS 参数的含义及其设置方法； 5． 掌握程序编写中系统调用的方法。

　四、主要实验步骤 1、可以通过 Vmware workstation 虚拟机来模拟并记录安装 Windows 和 Linux 的过程，主要要准备光盘（虚拟机也可使用光盘镜像 ISO 文件或精灵虚拟光驱），若计算机已经装有一个操作系统，则在安装之前要注意：如果是使用光盘用电脑自带光驱安装，则安装之前必须设定计算机的 BIOS，让计算机从光驱启动；若是使用 USB 光驱或者是 U 盘引导，则要设定 BIOS 使计算机从 USB 接口启动。安装系统主要需要输入序列号，设定管理员及使用者姓名和身份密码。用户可以选择要安装的系统程序（Linux 为软件包），或者也可以在安装完后在控制面板的添加/删除程序中选择。安装方法一般来说使用光盘直接安装，将光盘放入光驱中，没有光驱的电脑可以使用 USB 光驱或者使用 U 盘安装。

　2、熟悉查看用户的接口环境可以使用系统自带的管理程序，操作如下：

　“右击我的电脑”——“管理”——“设备管理器”，也可以“右击我的电脑”——“属性”——“硬件”——“设备管理器”，进入设备管理器可以看到计算机的设备情况，包括计算机的各个接口。

　3、查看系统中的用户情况、进程、线程、内存使用情况，可进行如下操作：

　“右击我的电脑”——“管理”——“本地用户和组”——“用户”，这样就可以查看系统中的用户情况，并可以对用户进行添加、删除、禁用、修改等操作。

　使用任务管理器可以看到系统中活动的用户、系统中的进程、线程和内存的使用情况，进行的操作如下：

　“右击任务栏”——“任务管理器”，或者直接在键盘上使用 ctrl+alt+delete 的快捷键打开任

　务管理器。在任务管理器中，点击“进程”就可以看见当前计算机在运行的进程及该进程的用户、CPU 占用率和内存使用情况。点击“性能”即可看见计算机当前 CPU 的使用、CPU 使用记录、PF 使用率、页面文件使用记录和线程数。点击“用户”就可以看见当前计算机活动的用户。

　4、调用系统服务：

　打开 Microsoft Visual C++ 6.0，新建 C++ Sourse File，写入以下代码：

　#include<stdlib.h> void main() {

　 system("date"); } 保存，使用工具编译，得到结果。

　五、实验数据及处理结果 安装 Windows Xp Sp2 的过程：

　 安装 Ubuntu Linux 10.04 的过程：

　以下是计算机 Xs19 的情况，Xs19 中 Windows Xp 的设备管理器：

　Xs19 中 Windows Xp 的用户情况：

　Xs19 的任务管理器：

　调度服务的结果：

　六、实验体会或对改进实验的建议 感觉这个实验不是光靠掌握书上内容就能做的，平时的实践也是非常重要的，如果对计算机非常熟悉的话，这个实验做起来难度很小。在做的时候基本上可以完成，中间碰到一个问题，就是对计算机有的系统服务不熟悉，所以要用 C 语言编程时感觉有点不知所措。

　七、参考资料 《计算机操作系统》（第三版）

　《计算机操作系统实验指导书》

　 告 南昌大学实验报告 ---编程实现银行家安全算法 学生姓名：

　张虹

　学

　号：

　6100409033

　 专业班级：

　 电Ⅲ091 班

　 实验类型：□ 验证 ■ 综合 □ 设计 □ 创新

　 实验日期：

　实验成绩：

　一、实验目的 通过实验加强对银行家安全算法的理解和掌握。

　二、实验内容 熟悉避免死锁发生的方法，死锁与安全序列的关系，编程实现银行家算法，要求输出进程的安全序列。

　三、实验要求 1、 需写出设计说明； 2、 设计实现代码及说明 3、 运行结果； 四、主要实验步骤 1、 分析银行家算法结构； 2、 画出银行家算法的流程图，即设计说明； 3、 根据画出的流程图使用 C 语言编写相应的代码（代码过长，放到最后）； 程序主要由 main 函数和以下几个函数组成：

　void input();用户输入银行家算法的初始数据； void output();输出当前系统资源分配情况； void change();当请求资源满足要求时，进行分配，系统资源发生改变； int check();安全性算法，检查是否存在安全序列； void outputsafe();输出安全序列的资源分配表。

　4、 检查代码，将编出的代码编译、链接，验证其正确性。

　开始输入银行家算法初始数据执行安全性算法数据是否正确是否存在安全序列输入进程Pi 发出的请求向量请求资源是否小于需求资源系统将资源分配给 Pi执行算法的是否为初始数据结束资源分配无效 ， 恢复分配前的系统资源情况输出当前资源分配表N NY YN NY YN NY Y输出安全序列的资源情况是否有进程发出请求向量N NY YN NY Y请求资源是否小于系统资源Y Y进程Pi需等待N NY Y

　五、实验数据及处理结果

　 六、实验体会或对改进实验的建议 体会：编写银行家算法需要较好分析能力，C 语言也要掌握的很好，而且需要细心和极大地耐心。我的程序在最开始编出来的第一份代码编译时大大小小一堆错误，有些是一个小错误导致了下面全错，这些小错误在一百多行里找起来非常费劲。然后小错误全部找出来以后，再编译，错误没有了，但是得到的结果却是错误的，这样又要开始一行一行分析，看是哪里出了问题。到最后得到了想要的结果以后，程序还需要修饰，至少要输出要简洁明朗，要让别人一运行这个程序就知道自己在什么时候该输入什么数据，数据是什么作用，而不是只有自己知道输进去的是什么东西。

　七、参考资料 《计算机操作系统》 《C 程序设计》 《C 语言程序设计_现代方法》 八、实验代码 #include <stdio.h> #include <stdlib.h> #include <string.h> int max[5][3];

　//开始定义银行家算法中需要用到的数据 int allocation[5][3]; int need[5][3]; int available[3]; int request[5][3]; char *finish[5]; int safe[5]; int n,i,m; int k=0;

　int j=0; int work[3]; int works[5][3]; void start(); //表示程序开始 void end(); //表示程序结束 void input(); //输入数据 void output(); //输出数据 void change(); //系统分配资源，原有资源情况改变 void outputsafe(); //输出安全序列的资源分配情况 int check(); //安全性算法 void main()

　//主程序开始 {

　start();

　for (;j==0;)

　 //确认输入数据的正确性，若输入错误，重新输入

　{

　 input();

　 printf("以下为进程资源情况，请确认其是否正确：\n");

　 output();

　 printf("数据是否无误：\n 正确：输入\n 错误：输入\n 请输入：");

　 scanf("%d",&j);

　}

　printf("数据确认无误，算法继续。\n");

　if (check()==0)

　 //若 check 函数返回值为，表示输入的初始数据找不到安全序列，无法进行下一步，程序结束

　{

　 end();

　 exit(0);

　}

　for(;j==1;)

　 //当有多个进程请求资源时，循环开始

　{

　 printf("请输入请求资源的进程 i(0、、、、)：");

　//输入发出请求向量的进程及请求向量

　 scanf("%d",&i);

　 printf("请输入进程 P%d 的请求向量 Request%d：",i,i);

　 for(n=0;n<3;n++)

　scanf("%d",&request[i][n]);

　 for (;request[i][0]>need[i][0] || request[i][1]>need[i][1] || request[i][2]>need[i][2];) //若请求向量大于需求资源，则认为是输入错误，要求重新输入

　 {

　printf("数据输入有误，请重试！\n 请输入进程 P%d 的请求向量 Request%d：",i,i);

　for(n=0;n<3;n++)

　 scanf("%d",&request[i][n]);

　 }

　if(request[i][0]<=available[0] && request[i][1]<=available[1] && request[i][2]<=available[2])

　//判断系统是否有足够资源提供分配

　 {

　printf("系统正在为进程 P%d 分配资源……\n",i);

　change();

　//分配资源

　j=0;

　 }

　 else

　printf("系统没有足够的资源，进程 P%d 需要等待。\n",i);

　 if (j==0)

　 //j=0 表示系统有足够资源分配的情况

　 {

　printf("当前系统资源情况如下：\n");

　//输出分配资源后的系统资源分配情况

　output();

　if(check()==0)

　//若找不到安全系列，则之前的资源分配无效

　{

　 printf("本次资源分配作废，恢复原来的资源分配状态。\n");

　 for (m=0;m<3;m++)

　//恢复分配资源前的系统资源状态

　 {

　available[m]+=request[i][m];

　allocation[i][m]-=request[i][m];

　need[i][m]+=request[i][m];

　 }

　output();

　 //输出系统资源状态

　}

　 }

　 printf("是否还有进程请求资源？\n 是：输入\n 否：输入\n 请输入：");

　 scanf("%d",&j);

　//若还有进程请求资源，j=1，之前的 for 循环条件满足

　}

　end(); } void line()

　 //美化程序，使程序运行时更加明朗美观 {

　printf("------------------------------------------------------------------\n"); }

　void start()

　 //表示银行家算法开始 {

　line();

　printf("

　 银行家算法开始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line(); }

　void end()

　 //表示银行家算法结束

　{

　line();

　printf("

　 银行家算法结束，谢谢使用\n");

　line(); }

　void input()

　//输入银行家算法起始各项数据 {

　 for (n=0;n<5;n++)

　 {

　printf("请输入进程 P%d 的相关信息：\n",n);

　printf("Max:");

　for (m=0;m<3;m++)

　 scanf("%d",&max[n][m]);

　printf("Allocation:");

　for (m=0;m<3;m++)

　 scanf("%d",&allocation[n][m]);

　for (m=0;m<3;m++)

　 need[n][m]=max[n][m]-allocation[n][m];

　 }

　printf("请输入系统可利用资源数 Available:");

　for (m=0;m<3;m++)

　 scanf("%d",&available[m]); }

　void output()

　//输出系统现有资源情况 {

　line();

　printf("资源情况

　 Max

　 Allocation

　Need

　Available\n");

　printf("进程

　 A

　B

　C

　A

　B

　C

　 A

　B

　C

　 A

　B

　C\n");

　line();

　for(n=0;n<5;n++)

　{

　 printf("P%d%9d%3d%3d%5d%3d%3d%6d%3d%3d",n,max[n][0],max[n][1],max[n][2],allocation[n][0],allocation[n][1],allocation[n][2],need[n][0],need[n][1],need[n][2]);

　 if (n==0)

　printf("%6d%3d%3d\n",available[0],available[1],available[2]);

　 else

　printf("\n");

　}

　line(); }

　void change()

　 //当 Request[i,j]<=Available[j]时，系统把资源分配给进程 P[i]，Available[j]和 Need[i,j]发生改变 {

　for (m=0;m<3;m++)

　{

　 available[m]-=request[i][m];

　 allocation[i][m]+=request[i][m];

　 need[i][m]-=request[i][m];

　} }

　void outputsafe()

　 //输出安全序列的资源分配表 {

　printf("该安全序列的资源分配图如下：\n");

　line();

　printf("资源情况

　Work

　 Need

　Allocation Work+Allocation

　Finish\n");

　printf("进程

　 A

　B

　C

　A

　B

　C

　A

　B

　C

　 A

　B

　C\n");

　line();

　for(n=0;n<5;n++)

　 printf("P%d%9d%3d%3d%5d%3d%3d%5d%3d%3d%6d%3d%3d%12s\n",safe[n],works[safe[n]][0],works[safe[n]][1],works[safe[n]][2],need[safe[n]][0],need[safe[n]][1],need[safe[n]][2],allocation[safe[n]][0],allocation[safe[n]][1],allocation[safe[n]][2],works[safe[n]][0]+allocation[safe[n]][0],works[safe[n]][1]+allocation[safe[n]][1],works[safe[n]][2]+allocation[safe[n]][2],finish[n]);

　line(); }

　int check()

　//安全性算法 {

　printf("开始执行安全性算法……\n");

　for (m=0;m<3;m++)

　//数组 work 和 finish 初始化

　 work[m]=available[m];

　for (n=0;n<5;n++)

　{

　 finish[n]="false";

　 safe[n]=0;

　}

　k=0;

　for (m=0;m<5;m++)

　 for (n=0;n<5;n++)

　if(strcmp(finish[n],"false")==0 && need[n][0]<=work[0] && need[n][1]<=work[1] && need[n][2]<=work[2])

　 //查找可以分配资源但尚未分配到资源的进程

　{

　 safe[k]=n;

　//以数组 safe[k]记下各个进程得到分配的资源的顺序

　works[safe[k]][0]=work[0];

　 works[safe[k]][1]=work[1];

　 works[safe[k]][2]=work[2];

　 work[0]+=allocation[n][0];

　 //进程执行后释放出分配给它的资源

　 work[1]+=allocation[n][1];

　 work[2]+=allocation[n][2];

　 finish[n]="ture"; //finish[n]变为以示该进程完成本次分

　 k++;

　}

　for (m=0;m<5;m++)

　//判断是否所有进程分配资源完成

　{

　 if (strcmp(finish[m],"false")==0)

　 {

　printf("找不到安全序列，系统处于不安全状态。\n");

　return 0;

　//找不到安全序列，结束 check 函数，返回

　 }

　 else

　 if (m==4)

　 //此处 m=4 表示所有数组 finish 的所有元素都为 ture

　{

　 printf("找到安全序列 P%d->P%d->P%d->P%d->P%d，系统是安全的\n",safe[0],safe[1],safe[2],safe[3],safe[4]);

　 j=1;

　 outputsafe();

　 //输出安全序列的资源分配表

　}

　}

　return 1; }

　 告 南昌大学实验报告

　---进程调度算法的实现 学生姓名：

　张虹

　学

　号：

　6100409033

　 专业班级：

　 电Ⅲ091 班

　 实验类型：□ 验证 ■ 综合 □ 设计 □ 创新

　 实验日期：

　实验成绩：

　 一、实验目的 通过实验加强对进程调度算法的理解和掌握。

　二、实验内容 编写程序实现进程调度算法，具体可以编写程序实现先来先服务算法或优先度高者调度算法。

　三 、实验要求 1、 需写出设计说明； 2、 设计实现代码及说明 3、 运行结果； 四、主要实验步骤 1、 分析实验内容，画出算法流程图； 2、 根据流程图写出实验代码； 3、 编译代码，验证结果正确与否； 4、 对程序进行修改，得到最后结果。

　流程图如下：

　开始系统随机产生数据将数据按照到达时间从小到大排序用户输入数据进程到达时前一个进程是否已经完成完成时间=服务时间+前一个进程完成时间完成时间=服务时间+到达时间周转时间=完成时间-到达时间带权周转时间=完成时间/服务时间是否所有进程已完成计算输出结果结束YNYNYN

　五、实验数据及处理结果

　六、实验体会或对改进实验的建议 在做这个实验的时候，一开始以为很简单，只要做简单的加减乘除就行了，但是仔细做过以后发现需要考虑很多情况。比如说输入进程到达时间的时候，要是乱序的该怎么办？还有到达时间和服务时间等等定义的都是整型变量，但是带权周转时间确会得到小数，此时就需要用到强制转换。在做系统产生随机数的时候也要考虑随机数的范围，如到达时间可以为0，但是服务时间却不能为 0，否则带权周转时间的计算会出错。

　七、参考资料 《计算机操作系统》 《计算机操作系统实验指导书》 《C 程序设计》 《C 语言程序设计_现代方法》 八、实验代码 #include <stdio.h>

　#include <stdlib.h> #include <time.h> #define N 5

　 //进程个数，可改变 int rt[N];

　//到达时间 int st[N];

　//服务时间 int ct[N];

　//完成时间 int cyt[N]; //周转时间 float rct[N]; //带权周转时间 float av[2]; //平均数 int n,m; void start(); //表示程序开始 void end(); //表示程序结束 void input(); //输入数据 void random(); //系统随机产生数据 void ordination(); //对数据按到达时间进行排序 void fcfs(); //先来先服务计算 void output(); //输出结果 void main() {

　start();

　int which;

　int c=1;

　for (;c==1;)

　{

　 for (;;)

　 {

　printf("输入数据还是由系统随机产生数据？\n1、输入数据\t2、系统随机产生数据\n 请输入：");

　scanf("%d",&which);

　if (which==1)

　{

　 input();

　 break;

　}

　else

　 if (which==2)

　 {

　random();

　break;

　 }

　 else

　printf("输入错误，请重新输入！");

　 }

　 ordination();

　//进程按照到达时间进行排序

　fcfs();

　 output();

　 printf("继续输入，退出输入。请输入：");

　 scanf("%d",&c);

　}

　end(); } void line()

　 //美化程序，使程序运行时更加明朗美观 {

　printf("------------------------------------------------------------------\n"); } void start()

　 //表示 FCFS 算法开始 {

　line();

　printf("

　 FCFS 算法开始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line(); } void end()

　 //表示 FCFS 算法结束 {

　line();

　printf("

　 FCFS 算法结束,谢谢使用\n");

　line(); } void input() {

　printf("请输入%d 个进程的到达时间：",N);

　for (n=0;n<N;n++)

　 scanf("%d",&rt[n]);

　printf("请输入%d 个进程对应的服务时间：",N);

　for (n=0;n<N;n++)

　 scanf("%d",&st[n]); } void random() {

　srand((unsigned)time(NULL));

　for (n=0;n<N;n++)

　{

　 rt[n]=rand()%100;

　 for (m=0;m<n;m++)

　if (n!=0 && rt[n]==rt[m])

　{

　 rt[n]=rand()%100;

　 m=0;

　 }

　 st[n]=rand()%98+1;

　 for (m=0;m<n;m++)

　if (n!=0 && st[n]==st[m])

　{

　 st[n]=rand()%98+1;

　 m=0;

　}

　} } void ordination()

　//重新排序，应对出现输入的到达时间为乱序的情况 {

　int temp;

　for (n=0;n<N;n++)

　 for (m=0;m<N-n-1;m++)

　if (rt[m+1]<rt[m])

　{

　 temp=rt[m+1];

　 rt[m+1]=rt[m];

　 rt[m]=temp;

　 temp=st[m+1];

　 st[m+1]=st[m];

　 st[m]=temp;

　} } void fcfs()

　 //执行 fcfs 算法 {

　av[0]=0;

　av[1]=0;

　ct[0]=rt[0]+st[0];

　for (n=1;n<N;n++)

　{

　 if (ct[n-1]>=rt[n])

　//考虑当前一个进程完成而后一个进程还没有到达的情况

　ct[n]=ct[n-1]+st[n];

　 else

　ct[n]=rt[n]+st[n];

　}

　for (n=0;n<N;n++)

　 cyt[n]=ct[n]-rt[n];

　for (n=0;n<N;n++)

　 rct[n]=(float)cyt[n]/(float)st[n];

　for (n=0;n<N;n++)

　{

　 av[0]+=(float)cyt[n]/N;

　av[1]+=rct[n]/N;

　} } void output()

　 //输出结果 {

　line();

　printf("进程名\t");

　for (n=0;n<N;n++)

　 printf("\t%c",65+n);

　printf("\t 平均\n 到达时间");

　for (n=0;n<N;n++)

　 printf("\t%d",rt[n]);

　printf("\n 服务时间");

　for (n=0;n<N;n++)

　 printf("\t%d",st[n]);

　printf("\n 完成时间");

　for (n=0;n<N;n++)

　 printf("\t%d",ct[n]);

　printf("\n 周转时间");

　for (n=0;n<N;n++)

　 printf("\t%d",cyt[n]);

　printf("\t%0.1f",av[0]);

　printf("\n 带权周转时间");

　for (n=0;n<N;n++)

　 printf("\t%0.1f",rct[n]);

　printf("\t%0.1f",av[1]);

　printf("\n");

　line(); }

　 南昌大学实验报告

　---存储管理的模拟实现 学生姓名：

　张虹

　学

　号：

　6100409033

　 专业班级：

　 电Ⅲ091 班

　 实验类型：□ 验证 ■ 综合 □ 设计 □ 创新

　 实验日期：

　实验成绩：

　 一、

　实验目的 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

　二、

　实验内容 1． 过随机数产生一个指令序列，共 320 条指令。其地址按下述原则生成：

　①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是：

　A. 在[0，319]的指令地址之间随机选区一起点 M; B. 顺序执行一条指令，即执行地址为 M+1 的指令； C. 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为 M’; D. 顺序执行一条指令，其地址为 M’+1； E. 在后地址[M’+2，319]中随机选取一条指令并执行； F. 重复 A—E，直到执行 320 次指令。

　2． 指令序列变换成页地址流，设：

　（1）

　页面大小为 1K； （2）

　用户内存容量为 4 页到 32 页； （3）

　用户虚存容量为 32K。

　在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：

　第 0 条—第 9 条指令为第 0 页（对应虚存地址为[0，9]）； 第 10 条—第 19 条指令为第 1 页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。

　第 310 条—第 319 条指令为第 31 页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成 32 页。

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

　A. FIFO 先进先出的算法 B. LRU 最近最少使用算法 C. LFU 最少访问页面算法 三、

　实验要求 1、 需写出设计说明； 2、 设计实现代码及说明 3、 运行结果；

　四、

　主要实验步骤 1、 分析算法结构； 2、 画出算法的流程图，即设计说明； 3、 根据画出的流程图使用 C 语言编写相应的代码（代码过长，放到最后）； 程序主要由 main 函数和以下几个函数组成：

　void initialization();初始化内存数据 void FIFO();FIFO 先进先出算法； void LRU();LRU 最久未使用算法； void LFU();LFU 最近最久未使用算法； 4、 检查代码，将编出的代码编译、链接，验证其正确性。

　开始按要求产生 320个随机数将随机数转换成页面用户内存容量i i= =4 4i i> > 32? ?FIFO 页面置换算法LRU 页面置换算法LFU 页面置换算法i i= =i i+ +1 1结束N NY Y 页面置换算法整体结构

　开始内存数据初始化 ， 物理块0 0< <m m< <i i 中页面停留时间time[ [m m ]=m m+ +1 1n n= =0 0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N N将页面调入空物理块中 ， 该物理块time[ [m m ]=0 0比较所有物理块的time[ [m m] ] ， 找到最大值 ，将页面调入最大值所在物理块 ， 该物理块time[ [m m ]=0 0所有已经存入页面的内存 time[ [m m ]++ ，n n ++N NY YY Yn n> > 320? ?结束将页面p p[ [n n] ] 调入内存Y YN N FIFO 页面置换算法

　开始内存数据初始化 ， 物理块0 0< <m m< <i i 中页面停留时间time[ [m m ]=m m+ +1 1n n= =0 0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N N将页面调入空物理块中 ， 该物理块time[ [m m ]=0 0比较所有物理块的time[ [m m] ] ， 找到最大值 ，将页面调入最大值所在物理块 ， 该物理块time[ [m m ]=0 0所有已经存入页面的内存 time[ [m m ]++ ，n n ++N NY YY Yn n> > 320? ?结束将页面p p[ [n n] ] 调入内存Y YN N存在该页面的物理块timg[ [m m ]=0 0 LRU 页面置换算法

　开始内存数据初始化 ， 物理块0 0< <m m< <i i 中页面停留时间time[ [m m ]=m m+ +1 1n n= =0 0n n> > 50? ?将页面p p[ [n n] ] 调入内存比较物理块中页面在之前的 50 次调用中出现的次数 ， 将页面p p[ [n n] ] 调入使用最少的页面占用的物理块n n> > 320? ?结束按照 LRU 页面置换算法调入页面n n ++Y YN NY YN N LFU 页面置换算法

　五、

　实验数据及处理结果

　六、

　实验体会或对改进实验的建议 我做实验的时候，主要的难度是在几个特殊情况的处理上，如 LRU 内存中的页面都是之前没有调用过的，那怎么办，还有就是 LFU 中还没有达到“一定时间间隔”的条件时怎么办？另外就是由于实验使用的是系统产生的随机数，所以难以验证实验结果的正确性。

　实验产生随机指令的方法是：

　1、 在[0，319]的指令地址之间随机选区一起点 M; 2、 顺序执行一条指令，即执行地址为 M+1 的指令； 3、 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为 M’; 4、 顺序执行一条指令，其地址为 M’+1； 5、 在后地址[M’+2，319]中随机选取一条指令并执行； 6、 重复 A—E，直到执行 320 次指令。

　那么，产生的第一个随机起点 M 指令是否执行？这对结果影响比较大，若起点 M 执行，那么命中率至少能提高 0.2 以上！

　七、

　参考资料 《计算机操作系统》 《计算机操作系统实验指导书》 《C 程序设计》 《C 语言程序设计_现代方法》 《计算机操作系统教程习题解答与实验指导(第二版)》 八、

　实验代码 #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 320 #define M 32 #define R 32 #define runtime 100 //程序运行次数，保证结果的准确性 int run; float average[3][32]; //取平均数，使结果更加准确 int s,i; //s表示产生的随机数，i表示物理块数 int m,n,h; //循环专用 int k,g,f; int sum; //缺页次数 float r; //rate命中率 int p[N]; //page页数 int a[N]; //执行的指令 int pb[M]; //physical block用户内存容量（物理块）

　void FIFO(); void LRU(); void LFU(); void line(); void start(); void end(); void main() {

　start();

　srand((int) time (NULL)); //以计算机当前时间作为随机数种子

　for (run=0;run<runtime;run++) //共产生“runtime”次随机数，保证结果的准确性

　{

　 for (n=0;n<N;n+=3)

　 {

　s=rand()%N+0; //随机产生一条指令

　a[n]=s+1; //顺序执行一条指令

　 s=rand()%(a[n]+1); //执行前地址指令M`

　a[n+1]=s+1;

　s=rand()%(N-a[n+1]-1)+(a[n+1]+1);

　a[n+2]=s;

　 }

　 for (n=0;n<N;n++)

　p[n]=a[n]/10; //得到指令相对的页数

　 for (i=4;i<=32;i++)

　 {

　FIFO();

　LRU();

　LFU();

　 }

　}

　printf("物理块数\t FIFO\t\t LRU\t\t LFU\n");

　line();

　for (i=4;i<=32;i++)

　{

　 printf("\n

　%2d：",i);

　 for (m=0;m<3;m++)

　printf("\t\t%6.4f",average[m][i]); //输出“runtime”次运行后的平均数

　}

　end(); } void initialization() //用户内存及相关数据初始化 {

　for (n=0;n<M;n++)

　 pb[n]=-1;

　sum=0;

　r=0;

　k=0;

　g=-1;

　f=-1; }

　void FIFO() //先进先出置换算法 {

　int time[M]; //定义进入内存时间长度数组

　int max; //max表示进入内存时间最久的，即最先进去的

　initialization();

　for(m=0;m<i;m++)

　 time[m]=m+1;

　for (n=0;n<N;n++)

　{

　k=0;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n]) //表示内存中已有当前要调入的页面

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1) //用户内存中存在空的物理块

　{

　 f=m;

　 break;

　}

　 if (g!=-1)

　g=-1;

　 else

　 {

　if (f==-1) //找到最先进入内存的页面

　{

　 max=time[0];

　 for(m=0;m<i;m++)

　if(time[m]>max)

　{

　 max=time[m];

　 k=m;

　}

　 pb[k]=p[n];

　 time[k]=0; //该物理块中页面停留时间置零

　 sum++; //缺页数+1

　}

　else

　{

　 pb[f]=p[n];

　 time[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time[m]++; //物理块中现有页面停留时间+1

　 /*if (n==0 && i==6)

　printf("\n");

　 if (i==6 && n<=30)

　 {

　 printf("%d......",p[n]);

　for (m=0;m<i;m++)

　 printf("%d ",pb[m]);

　printf("\n");

　 }*/

　}

　r=1-(float)sum/N;

　average[0][i]+=r/runtime; }

　void LRU() //最近最少使用算法 {

　int time[M];

　int max;

　initialization();

　for (m=0;m<i;m++)

　 time[m]=m+1;

　for (n=0;n<N;n++)

　{

　 k=0;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n])

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1)

　{

　 f=m;

　 break;

　}

　 if (g!=-1)

　 {

　time[g]=0;

　g=-1;

　 }

　 else

　 {

　if (f==-1)

　{

　 max=time[0];

　 for (m=0;m<i;m++)

　if (time[m]>max)

　 {

　 k=m;

　 max=time[m];

　}

　pb[k]=p[n];

　time[k]=0;

　sum++;

　}

　else

　{

　 pb[f]=p[n];

　 time[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time[m]++;

　}

　r=1-(float)sum/N;

　average[1][i]+=r/runtime; }

　void LFU() //最少访问页面算法 {

　initialization();

　int time_lru[M],time[M],min,max_lru,t;

　for (m=0;m<i;m++)

　{

　 time[m]=0;

　 time_lru[m]=m+1;

　}

　for (n=0;n<N;n++)

　{

　 k=0;

　 t=1;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n])

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1)

　 {

　 f=m;

　 break;

　}

　 if (g!=-1)

　 {

　time_lru[g]=0;

　g=-1;

　 }

　 else

　 {

　if (f==-1)

　{

　 if (n<=R) //将最少使用的间隔时间定位为R个单位

　 {

　max_lru=time_lru[0]; //在未达到“一定时间”的要求时，先采用LRU进行页面置换

　for (m=0;m<i;m++)

　 if (time_lru[m]>max_lru)

　 {

　k=m;

　max_lru=time_lru[m];

　 }

　 pb[k]=p[n];

　 time_lru[k]=0;

　 sum++;

　 }

　 else

　 {

　for (m=0;m<i;m++) //计算一定时间间隔内物理块中的页面使用次数

　 for (h=n-1;h>=n-R-1;h--)

　if (pb[m]==p[h])

　 time[m]++;

　min=time[0];

　for (m=0;m<i;m++)

　 if (time[m]<min)

　 {

　min=time[m];

　k=m;

　 }

　for (m=0;m<i;m++) //应对出现页面使用次数同样少的情况

　 if (time[m]==min)

　t++;

　 if (t>1) //若使用次数同样少，将次数相同的页面按照LRU进行页面置换

　{

　 max_lru=time_lru[k];

　 for (m=0;m<i && time[m]==min;m++)

　if (time_lru[m]>max_lru)

　{

　 k=m;

　 max_lru=time_lru[m];

　}

　}

　pb[k]=p[n];

　time_lru[k]=0;

　sum++;

　 }

　}

　else

　{

　 pb[f]=p[n];

　 time_lru[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time_lru[m]++;

　}

　r=1-(float)sum/N;

　average[2][i]+=r/runtime; } void line()

　 //美化程序，使程序运行时更加明朗美观 {

　printf("------------------------------------------------------------------"); } void start()

　 //表示算法开始 {

　line();

　printf("\n

　 页面置换算法开始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line();

　printf("\n\n"); } void end()

　 //表示算法结束 {

　 printf("\n");

　line();

　printf("\n

　 页面置换算法结束,谢谢使用\n");

　line(); }

推荐访问:操作系统 实验 报告