操作系统课内实验指导书.doc

操作系统课内实验指导书 操作系统原理课内实验指导书实验一用户接口实验准备知识为了使用户通过操作系统完成各项管理任务，操作系统必须为用户提供各种接口来实现人机交互。 经典的操作系统理论将操作系统的接口分为控制台命令和系统调用两种。 前者主要提供给计算机的操作人员对计算机进行各种控制；而后者则提供个程序员，使他们可以方便地使用计算机的各种资源。 1.控制台命令接口操作系统向用户提供一组控制台命令，用户可以通过终端输入命令的方式获得操作系统的服务，并由此来控制自己作业的运行。 一般来讲，控制台命令应该包含一组命令、终端处理程序以及命令解释程序。 1)bash的由来当登录Linux或者打开一个xterm时，当前默认的shell就是bash。 Bash是GNU Project的shell。 GNU Project是自由软件基金会（Free SoftwareFoundation）的一部分。 它对Linux下的许多编程工具负责。 Bash（Bourne AgainShell）是自由软件基金会发布的Bourne shell的兼容程序。 它包含了其他有些shell的许多良好的特性，功能非常的全面。 很多Linux版本都供bash。 2)bash的大致原理bash处理自己的脚本时，先找到需要处理的命令名称，进而在当前用户的默认命令目录中找到对应的命令，这些默认目录一般是/usr/bin、/bin或/sbin。 在执行这些命令时，先使用进程创建系统调用fork（），在使用exex（）来执行这些命令。 3)建立bash脚本?文件可以用最熟悉的器来这个文本文件，比如文件名为script，在shell下输入$vi script#!/bin/bash EchoHello World!然后保存，退出。 ?测试脚本。 使用指令$source script?更改脚本属性使用指令$chmod a+x script将脚本程序设置为可执行。 ?执行脚本使用指令$./script4)关键字参考Echo在终端上显示Bash特殊变量19，保存当前进程或脚本的前9个参数。 Ls列举文教案Wc统计数量Function定义函数2系统调用系统调用是操作系统为程序员提供的接口服务。 使用系统调用，程序员可以更充分的利用计算机资源，使编写的程序更加灵活，功能更加强大。 程序员在对系统充分了解的情况下甚至可以订做系统调用，实现那些非专业程序员所难以实现的功能。 1)添加源代码第一个任务是编写添加到内核的源程序，即添加到内核文件中的一个函数。 该函数的名称应该是在新的系统调用名称之间前加上sys_标志。 假设新加的系统调用为foo（），功能为原值返回输入的整型数。 格式为int foo（int iNumber），返回的值就是出入的参数。 在/usr/src/linux/kernel/sys.c文件中添加源代码，如下所示Asmlinkage intsys_foo（int x）printf（“%dn”,x）;注意目录“/usr/src/linux“是linux各个版本的统称，它因系统内核的版本不同而名称不同。 例如，当前操作系统是Linux7.1器内核四Linux-2.4.2,所以在”usr/src”目录下有两个文件Linux-2.4和Linux-2.4.2,其中Linux-2.4是Linux-2.4.2的连接文件，程序员可以进入任何一个目录，它对内核的修改都是一样的。 2)连接新的系统调用添加新的系统调用之后，下一个任务是让Linux内核的其余部分知道该程序的存在。 为了从已有的内核程序中增加新函数的链接，需要进行下面的操作 （1）进入目录/usr/src/linux/include/asm-i386/，打开文件unistd.h。 这个文件包含了系统调用的清单，用来给每个系统调用分配一个唯一的号码。 系统调用号的定义格式如下#define_NR_name NNN其中，name以系统调用名称代替，而NNN是该系统调用对应的号码，应该将新的系统调用名称放到清单的最后，并给它分配已经用到的系统调用号后面的一个号码，比如#define_NR_foo222以上的系统调用号便是222。 Linux内核自身用的系统调用号已经用到了221了。 如果读者还要自行增加系统调用，就必须从223开始。 （2）进入/usr/src/linux/arche/i386/kernel/,打开文件entry.S。 该文件中有类似下面的清单ENTRY（sys_call_table）.long SYSMBOL_NAME(sys_ni_syscall).long SYSMBOL_NAME(sys_exitl).long SYSMBOL_NAME(sys_fork).在该表的最后加上.long SYSMBOL_NAME(sys_foo)3)重新编译内核为了使新的系统调用生效，需要重建Linux的内核，首先必须以root的身份登录。 进入目录/usr/src/linux/，重建内核rootlinuxserver root#make menuconfig/配置新内核rootlinuxserver root#make dep/创建新内核rootlinuxserver root#make moduless_install/加入模块rootlinuxserver root#make clean/清楚多余创建的文件rootlinuxserver root#make bzImage/生成可执行内核引导文件4)使用新编译的内核cpa/usr/src/linux-2.4.2/arch/i386/boot/bzImage/boot5)重新配置/etc/lilo.conf文件使用vi器/etc/lilo.conf文件vi/etc/lilo.conf在其中加入如下几行Image=/boot/baImage#启动内核的位置，即自己#新配置的内核所在目录label=xhlinux#给内核起一个名称，配#置完成，重新启动的时候，#会显示这个名称read_only#定义新的内核为只读root=/dev/hda5#定义硬盘的启动位置为#/dev/hda5，在该设计中没有变#仿照以前内核引导位置，不#用修改，用以前的就可以了6)重启系统完成以上配置后，重新启动系统进入自己的新系统实验指导1.控制台命令接口实验指导1)查看bash版本在shell提示符下输入$echo$BASH_VERSION2)编写bash脚本统计/my目录下c语言文件的个数通过bash脚本，可以有多种方式实现这个功能，而使用函数是其中个一个选择。 在使用函数之前，必须先定义函数。 （1）进入自己的工作目录，用vi编写名为count的文件cd/home/student#在home/student目录下编程vi count下面是脚本程序#!/bin/bash functioncountechonNumber ofmatches for$1:#接收程序的第一个参数ls$1|wcl#对子程序的第一个参数所在的目录进行操作 （2）执行将count文件复制到当前目录下，然后在当前目录下建立文件夹my mkdirmy3)cd myvi1.c#在my目录下建立几个c文件,以便用来进行测试.cd.chmod+x count count./my/*.c2.系统调用实验指导1)编程调用一个系统调用fork（）在应用程序中调用系统调用fork（）非常简单，下面的程序可以很清楚的显示出有fork（）系统调用生成了子进程，而产生的分叉作用#includeint main()int iUid;iUid=fork();if(iUid=0)for(;)printf(This isparent.n);sleep (1);if(iUid0)for(;)printf(This ischild.n);sleep (1);if(iUid0)printf(Can notuse systemcall.n);return0;下面是可能得到的一种结果this ischild.this isparent.this ischild.this isparent.this isparent.this ischild.this ischild.this isparent.this isparent.this ischild.this ischild.this isparent.this isparent.this ischild.2)编程调用创建的系统调用foo（）foo（）是本实验系统设计者自行添加的一个简单的系统调用。 其实现过程在前面一进介绍了，它的功能很简单，就是向标准输出一个特定的整数。 程序test.c如下#include#include_syscall1(char*,foo,int,ret)main()int I,J;I=100;J=0;J=foo(I);printf(This isthe resultof newkerneln);printf(%d,j);程序编译goI/usr/src/linux-2.4.2/include test.c注意由于需要引入内核头文件unistd.h，不能简单的用普通的编译命令，而应该这样设置参数。 运行测试程序./test解释当函数还没有定义在内核中时，如果运行以上程序，系统将显示一个未定义的值-1，而在内核中定义了以后，系统将显示100.说明我们内核添加系统调用已经成功。 3)创建系统调用mycall（），实现功能显示字符串到屏幕上。 （1）编写系统调用相应的函数在/usr/src/linux/kernel/sys.c文件中添加如下代码asmlinkage voidmycall(char*str)printk(%sn,str);注意在上面的例子中，有一个很少见的特殊函数printk（），它的功能与printf（）类似。 之所以不用printf（）的原因在于，它不是内核的函数。 要在内核实现在控制台显示字符串的功能，就必须以内核所提供的printk（）函数来代替。 Printk（）不同于printf（）的地方是printk（）会把输出的结果送到内核的缓冲区里面，最终调用控制台的写函数将其打印出来。 （2）添加系统调用号打开文件/usr/src/linux/include/asm-i386/unistd.h,添加如下一行#include_NR_mycall223/因为_NR_foo是222,所以这个只能用223了 （3）改动系统调用表打开文件/usr/src/linux/arch/i386/kernel/entry.s，在“.long SYMBOL_NAME(sys_foo)”,下面添加一行.long SYMBOL_NAME(sys_mycall) （4）重新编译内核对重新编译内核和使用新内核引导熟悉的读者，可以不必阅读 （4）和 （5）步。 以root身份登录，进入目录/usr/src/linux,重建内核rootlinuxserver root#make menuconfig/配置新内核rootlinuxserver root#make dep/创建新内核rootlinuxserver root#make modules_install/加入模块rootlinuxserver root#make clean/清除多余创建的文件rootlinuxserver root#make bzImage/生成可执行内核引导文件rootlinuxserver root#cp编译完毕之后，新的内核引导文件在目录/usr/src/linux/arch/i386/boot/中，叫baImage.把它复制到/boot/下面rootlinuxserver root#cp/usr/src/linux/arch/i386/boot/bzImage/boot/ （5）用新的内核引导这需要修改文件/etc/lilo.conf,先打开该文件，然后进行修改。 修改完成后，存盘退出，运行命令rootlinuxserver root#/sbin/lilo （6）重新启动系统、4)编程调用自己创建的系统调用系统调用mycall（）是读者自己创建的，自己应该对该系统调用表非常的熟悉。 然而使用这个系统调用还需要注意系统调用需要装换宏。 这个转换宏是将系统调用命令装换为对应参数的INT80中断请求，一般格式是syscallN（），这个N可以是06，对应与系统调用的参数格式，此处N=1，下面是一个简单的源代码test1.c#includesyscall1(char*,mycall,int,ret)int main()char*str;char string50;str=string;str=This stringwill bedisplayed.;mycall(str);return0;实验二进程管理实验指导准备知识1.基本概念2)进程的概念3)进程与程序的区别4)并发执行的概念5)进程互斥的概念6)进程通信的基本概念2.系统调用系统调用是一种进入系统空间的办法。 通常，在OS的核心中都设置了一组用于实现各种系统功能的子程序，并将他们提供给程序员使用。 程序员在需要OS提供某种服务的时候，便可以调用一条系统调用命令，去实现希望的功能，这就是系统调用。 因此，系统调用就像一个黑箱子一样，对用户屏蔽了操作系统的具体动作而只是提供了调用功能的接口。 不同的操作系统有各自的系统调用方法。 如Windows API，便是Windows的系统调用。 Linux的系统调用与之不同的是源于Linux内核代码完全公开，所以可以细致地分析出其系统调用的机制。 2.1系统调用和普通函数的区别1)运行于不同的状态用户程序可以通过系统调用进入系统空间，在核心态执行；而普通函数则只能在用户空间当中进行。 2)通过软中断切断由于用户程序使用系统调用后要进入系统空间，所以需要调用一个软中断；而普通函数在被调用时则没有这个进程。 2.2系统调用的类型系统调用的作用与它的宿主操作系统有密切关系。 根据操作系统的性质不同，它们所提供的系统调用会有一定的差异，不过对于普通操作系统而言，应该具有下面几类系统调用?进程控制类?文件操纵类?进程通信类?信息维护类2.3系统调用的实现机制由于操作系统的不同，其系统调用的实现方式可能不一样，然而实现机制应该大致相同的，一般包含下面两个步骤。 1)设置系统调用号在系统当中，往往设置多条系统调用命令，并赋予每条系统调用命令一个惟一的系统调用号。 根据分配系统调用号方式的不同分为直接方式和参数表方式。 系统调用的参数表方式分为直接和间接两种方式，如图1所示。 图1系统调用的参数表方式2)处理系统调用操作系统中有一张系统调用入口表。 表中的每个表目都对应一条系统调用命令，它包含有该系统调用自带参数的数目、系统调用命令处理程序的入口地址等等。 操作系统内核便是根据所输入的系统调用号在该表中查找到相应的系统调用，进而转入它的入口地址去执行系统调用程序。 3.Linux的系统调用机制Linux的系统调用是通过中断机制实现的。 中断这个概念涉及计算机系统结构方面的知识，显然它与微处理器等硬件有着密不可分的关系。 中断（Interrupt），是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得CPU不得不暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后再返回原来被中断处继续执行的进程。 其发生一般而言是“异步”的。 换句话说就是在无法预测的情况下发生的（如系统掉电）。 所以计算机的软硬件对于中断的相应反应完全是被动的。 软中断，是对硬中断的一种模拟，发送软中断就是向接收进程的proc结构中的相应项发送一个特定意义的信号。 软中断必须等到接收进程执行时才能生效的。 陷阱（Trap），即由软件产生的中断，指处理机和内存内部产生的中断，它包括程序运算引起的各种错误，如地址非法、校验错误、页面失效等。 它有专门的指令，如X86中的“INTn”，在程序中是有意产生的。 所以说陷阱是主动的、“同步”的。 异常（Exception），一般也是异步的，大多是由于不小心或无意造成的，比如在进行除法操作时除数为0，就会产生一次异常。 4.相关函数fork函数fork（）函数用于创建一个新进程（子进程）。 其调用格式为int fork();正确返回等于0，创建子进程，从子进程返回的ID值。 等于1，从父进程返回的子进程的进程ID值。 错误返回等于-1，创建失败。 1)子进程和父进程的调度执行子进程被创建后就进入就绪队列和父进程分别分别独立地等待调度。 子进程继承父进程的程序段代码，子进程被调度执行时，也会和父进程一样从fork()返回。 从共享程序段代码的角度来看，父进程和子进程所执行的程序代码是同一个，在内存中只有一个程序段副本；但是从编程的角度来看，为了使子进程和父进程做不同的事，要在程序中区分父进程和子进程的代码段，这就需要借助于从fork()带回的值来标志当前程序身份。 从fork()返回后，都会执行如下语句pid=fork();得到返回的值pid，有如下几种情况 (1)若pid小于0，则表示fork()出错，相应语句为if(pid0)printf(The parentprocess isrunning now!n);exit (0);由于父进程和子进程分别独立地进入就绪队列等待调度，所以谁会先得到调度是不确定的，这与系统的调度策略和系统当前的资源状态有关。 因此谁先从fork()返回，继续执行后面的语句也是不确定的。 2)父进程和子进程的存放及资源共享当父进程创建子进程时，首先为子进程分配由task向量数组指向的task_struct结构的内存、所需的堆栈和页表等，创建进程标识号（在系统的进程标识号组中是惟一的），并且将其父进程的进程标识号填入task_struct中的家族信息中。 然后将父进程的task_struct的相关内容复制到子进程的task_struct，对一些数据成员进行初始化，如图2所示。 子进程从父进程处继承的资源包括真实用户标识号和组标识号、有效用户标识号和组标识号、进程组标识号、对话标识号、控制终端、根目录与当前工作目录、设置用户标识号和设置组标识号计位、信号标识、文件描述符、文件默认创建权限掩码、可访问的内存区、线程、环境变量及其他资源分配。 图2父进程和子进程的内存映像wait()函数wait()函数常用来控制父进程与子进程的同步。 在父进程中调用wait()函数，则父进程被阻塞，进入等待队列，等待子进程结束。 当子进程结束时，产生一个终止状态字，系统会向父进程发出SIGCHLD信号。 当接到信号后，父进程提取子进程的终止状态字，从wait()函数返回继续执行原来的程序。 其调用格式为#include#include(pid_t)wait(int*statloc);正确返回大于0，子进程的进程ID值。 等于0，其他。 错误返回等于-1，调用失败。 exit()函数exit()函数是进程结束时最常调用的函数，在main()函数中调用return，最终也是调用exit()函数。 这些都是进程的正常终止。 在正常终止时，exit()函数返回进程结束状态。 其调用格式为#includevoid exit(int status);其中，status为进程结束状态。 kill()函数kill()函数用于删除执行中的程序或者任务。 其调用格式为kill(int PID,int IID);其中，PID是要被杀死的进程号，IID为向将被杀死的进程发送中的中断号。 Signal()函数signal()函数是允许调用进程控制软中断信号的处理。 其调用格式为#includeint sig;void(*func)();signal(sig,function);其中, (1)sig的取值如下信号功能值SIGHUP挂起1SIGINT键盘中断，键盘按Delete键或Break键2SIGQUIT键盘按Quit键3SIGILL非法指令4SIGTRAP跟踪中断5SIGIOT IOT指令6SIGBUS总线错7SIGFPE浮点运算溢出8SIGKILL要求终止进程9SIGUSR1用户定义信号#110SIGSEGV段违法11SIGUSR2用户定义信号#212SIGPIPE向没有读进程的管道上写13SIGALRM定时器告警，时间到14SIGTERM kill发出的软件结束信号15SIGCHLD子进程死17SIGCONT若已停止则继续18SIGPWR电源故障30 （2）function的解释如下SIG_DFL默认操作。 对除SIGPWR和SIGCHLD外所有信号的默认操作是进程终结。 对信号SIGQUIT、SIGRAP、SIGLL、SIGFPE、SIGBUS和SIGSEGV，它产生一内存映像文件。 SIG_IGN忽视该信号的出现。 Function在该进程中的一个函数地址，在核心返回用户态时，它以软中断信号的序号作为参数调用该函数，对除了信号SIGILL、SIGTRAP、SIGPWAP以外的信号，核心自动地重新设置软中断信号处理程序的值SIG_DFL，一个进程不能捕获SIGKILL信号。 pipe()函数pipe()函数用于创建一个管道。 其调用格式为#includepipe(int fp2);其中，fp2是供进程使用的文件描述符数组，fp0用于写，fp1用于读。 正确返回0，调用成功错误返回-1，调用失败。 实验指导1.进程的软中断通信 （1）算法流程图图3为进程软中断通信的算法流程图图3软中断通信程序流程图 （2）参考程序源代码#include#include#include#includeint wait_flag;void stop();main()int pid1,pid2;/定义两个进程号变量signal(3,stop);/或者signal(14,stop);while(pid1=fork()=-1);/若创建子进程1不成功,则空循环if(pid10)/子进程创建成功,pid1为进程号while(pid2=fork()=-1);/创建子进程2if(pid20)wait_flag=1;sleep (5);/父进程等待5秒kill(pid1,16);/杀死进程1kill(pid2,17);/杀死进程2wait (0);/等待第1个子进程1结束的信号wait (0);/等待第2个子进程2结束的信号printf(n Parent process is killed!n);exit (0);/父进程结束elsewait_flag=1;signal(17,stop);/等待进程2被杀死的中断号17printf(n Child process2is killedby parent!n);exit (0);elsewait_flag=1;signal(16,stop);/等待进程1被杀死的中断号16printf(n Child process1is killedby parent!n);exit (0);void stop()wait_flag=0; （3）程序运行结果Child process1is killedby parent!Child process2is killedby parent!Parent processis killed!或者多次运行，并且Delete键后，会出现如下结果Child process2is killedby parent!Child process1is killedby parent!Parentprocessis killed! （4）简要分析1)signal函数上述程序中，调用函数signal()都放在一段程序的前面部位，而不是在其他接收信号处。 这是因为signal()的执行起的作用只是为进程指定信号量16和17，以及分配相应的与stop()过程连接的指针。 因而signal()函数必须在程序前面部分执行。 2）wait函数在父进程中调用第1个wait (0)后，则父进程被阻塞。 进入等待第一个子进程运行结束的队列，等待子进程结束。 当子进程结束后，会产生一个终止状态字，系统会向父进程发出SIGCHLD信号。 当接到信号后，父进程提取子进程的终止状态字，从wait()返回继续执行原程序。 同样的方式，父进程继续执行第二个wait (0)，并再次阻塞，等待第2个子进程运行结束。 当第二个子进程运行结束后父进程继续执行剩余的语句。 3）关于exit函数该函数中每个进程退出时都用了语句exit (0)，这是进程的正常终止。 在正常终止时，exit()函数返回进程结束状态。 进程终止时，则由系统内核产生一个代表异常终止原因的终止状态，该进程的父进程都能用wait()得到其终止状态。 在子进程调用exit()后，子进程的结束状态会返回给系统内核，由内核根据状态字生成终止状态，供父进程在wait()中读取数据。 若子进程结束后，父进程还没有读取子进程的终止状态，则子进程就变成了“孤儿进程”，系统进程init会自动“收养”该子进程，成为该子进程的父进程，即父进程标识号变成1，当子进程结束时，init会自动调用wait()读取子进程的遗留数据，从而避免在系统中留下大量的垃圾。 4）结果显示上述结果中“Child process1is killedby parent!”和“Child process2iskilledby parent!”相继出现，当运行几次后，谁在前谁在后是随机的。 这是因为从进程调度的角度看，子进程被创建后处于就绪态。 此时，父进程和子进程作为两个独立的进程，共享同一个代码段，分别参加调度、执行，直至进程结束。 但是谁会先被调度程序选中执行，则与系统的调度策略和系统当前的资源状态有关，是不确定的。 因此，谁先从fork()函数中返回继续执行后面的语句也是不确定的。 2.进程的管道通信 （1）算法流程图图4为基于进程的管道通信的算法流程图图4管道通信程序流程图 （2）参考程序源代码#include#include#includeint pid1,pid2;/定义两个进程变量main()int fd2;char OutPipe100,InPipe100;/定义两个字符数组pipe(fd);/创建管道while(pid1=fork()=-1);/如果进程1创建不成功,则空循环if(pid1=0)/如果子进程1创建成功,pid1为进程号lockf(fd1,1,0);/锁定管道sprintf(OutPipe,n Childprocess1is sendingmessage!n);/给Outpipe赋值write(fd1,OutPipe,50);/向管道写入数据sleep (5);/等待读进程读出数据lockf(fd1,0,0);/解除管道的锁定exit (0);/结束进程1elsewhile(pid2=fork()=-1);/若进程2创建不成功,则空循环if(pid2=0)lockf(fd1,1,0);sprintf(OutPipe,n Childprocess2is sendingmessage!n);write(fd1,OutPipe,50);sleep (5);lockf(fd1,0,0);exit (0);elsewait (0);/等待子进程1结束read(fd0,InPipe,50);/从管道中读出数据printf(%sn,InPipe);/显示读出的数据wait (0);/等待子进程2结束read(fd0,InPipe,50);printf(%sn,InPipe);exit (0);/父进程结束 （3）程序运行结果Childprocess1is sendingmessage!Childprocess2is sendingmessage！ （4）简要分析管道，是指用于连接一个读进程和一个写进程，以实现它们之间信息的共享文件又称pipe文件。 向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入管道；而接收管道输送的接收进程（读进程），可以从管道中接收数据。 为了协调双方的通信，管道通信机制必须提供以下3方面的协调能力?互斥。 当一个进程正在对pipe进程读/写操作时，另一进程必须等待，程序中使用lock(fd1,1,0)函数实现对管道的加锁操作，用lock(fd1,0,0)解除管道的锁定。 ?同步。 当写进程把一定数量的数据写入pipe后，便去睡眠等待，直到读进程取走数据后，再把它唤醒。 当读进程试图从一空管道中读取数据时，也应睡眠等待，直至写进程将数据写入管道后，才将其唤醒。 ?判断对方是否存在。 只有确定写进程和读进程都存在的情况下，才能通过管道进行通信。 实验三存储器管理实验准备知识 （1）C+、指针、结构体（类） （2）HASH表查找方式 （3）操作系统相关内存交换知识 （4）用到的LINUX函数Int getpid()获得当前进程的id Voidsrand(int a)以a为种子产生随机数Int rand()根据前面的种子，返回一个随机数实验指导本实验并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续存储方式对进程页面交换进行模拟。 1.FIFO算法?原理简述 （1）在分配内存页面数（AP）小天进程页面数（PP）时，当然是最先运行的AP个页面放入内存； （2）这时又需要处理新的页面，则将原来放的内存中的AP个页中最先进入的调出（FIFO），再将新页面放入； （3）以后如果再有新页面需要调入，则都按上述规则进行。 （4）算法特点所使用的内存页面构成一个队列。 ?图表描述假设某个进程在硬盘上被划分成5个页面（PP=5），以 1、 2、 3、 4、5分别表示，CPU调用它们的顺序（这应该取决于进程本身）为 1、 4、 2、 5、 3、 3、 2、 4、 2、5，如果内存可以控制的页面数为3（AP=3），那么在使用FIFO算法时，这3个页面的内存使用情况应该如图5所示。 图5不难看出，本例共换入页面8次，若用变量diseffect表示页面换入次数，则diseffect=8。 ?算法实现提示要得到命中率，必然应该有一个常量total_instruction来记录页面总共使用的次数，此外还需要一个变量记录总共换入页面的次数diseffect（需要换出页面总是因为缺页中断而产生）。 利用公式1-diseffect/total_instruction*100%可以得到命中率。 （1）初始化。 设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个随机数序列maintotal_instruction（这个序列由pageap的下标随机构成）表示待处理的进程页面顺序，diseffect置0。 （2）看main中是否有下一个元素，若有，就由main中获取该页面下标，并转 （3），如果没有则转 （7）。 （3）如果该页已在内存中，就转 （2），否则转 （4），同时未命中的diseffect加1。 （4）观察pagecontrol是否占满，如果占满则须将使用队列（在第 （6）步中建立的）中最先进入的（就是队列的第一个单元）pagecontrol单元“清干净”，同时将page单元置为“不在内存中”。 （5）将该page与pagecontrol建立对应关系（可以改变pagecontrol的标志位，也可以采用指针链接，总之至少要使对应的pagecontrol单元包含两个信息一是它被使用了，二是哪个page单元使用的。 page单元也包含两个信息对应的pagecontrol单元号和本page单元已在内存中）。 （6）将用到的pagecontrol置入使用队列（这里的队列是一种FIFO的数据结构），返回 （2）。 （7）显示计算1-diseffect/total_instruction*100%，完成。 2.LRU算法?原理简述 （1）当内存分配页面数（AP）小于进程页面数（PP）时，把最先执行的AP个页面放入内存。 （2）当需调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那一页调出，以空出内存来放置新调入的页面（LRU）。 （3）算法特点每个页面都有属性来表示有多长时间未被CPU使用的信息。 ?图表描述这里采用的例子和前面的一样。 假设某个进程在硬盘上被划分成5个页面（PP=5），以 1、 2、 3、 4、5分别表示，CPU调用它们的顺序（这应该取决于进程本身）为 1、 4、 2、 5、 3、 3、 2、 4、 2、5，而内存可以控制的页面数为3（AP=3），那么在使用LRU算法时，这三个页面的内存使用情况应该如图6所示。 不难看出，本例共换入页面7次，若用变量diseffect表示页面换入次数，则diseffect=7。 图6?算法实现提示与前述算法一样，只有先得到diseffect才能获得最终的命中率。 （1）初始化。 设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个随机数序列maintotal_instruction（这个序列由pageap的下标随机构成）表示待处理的进程页面顺序，diseffect置0。 （2）看序列main中是否有下一个元素，如果有，就由main中获取该页面下标，并转 （3），如果没有则转 （6）。 （3）如果该page单元在内存中便改变页面属性，使它保留“最近使用”的信息，转 （2），否则转 （4），同时diseffect加1。 （4）看是否有空闲页面，如果有，就返回页面指针，并转到 （5），否则，在内存页面中找出最长时间没有使用到的页面，将其“清干净”，并返回该页面指针。 （5）在需处理的page与 （4）中得到的pagecontrol之间建立联系，同时让对应的page单元保存“最新使用”的信息，转 （2）。 （6）如果序列处理完成，就输出计算1-diseffect/total_instruction*100%的结果，完成。 3.NUR算法?原理简述所谓“最近未使用”，首先是要对“近”做一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面。 那么可能会有以下几种情况 （1）如果这样的页面只有一个，就将其换出，放入需要处理的新页面。 （2）如果有这样的页面不止一个，就在这些页面中任取一个换出（可以是下标最小的或者最小的），放入需要处理的页面。 （3）如果没有一个这样的页面，就随意换出一个页面（可以是下标最小的或者最大的）。 算法特点有一个循环周期，每到达这个周期，所有页面存放是否被CPU处理的信息的属性均被置于初始态（没有被访问）。 ?图表描述还是用前面的例子，某进程在硬盘上被划分为5个页面，用 1、 2、 3、 4、5表示，而处理及处理它们的顺序为 1、 4、 2、 5、 3、 3、 2、 4、 2、5，而内存可以控制的页面数为3（AP=3），CLEAR_PERIOD取5；在循环周期内，如果所有内存页面均被CPU处理或者有多个页面未被CPU处理，取页码最小的页面换出。 算法实现过程如下图图7显示页面交换共6次，disaffect=6。 ?算法实现提示 （1）初始化。 设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列maintotal_instruction（当然这个序列由page德下标随机构成）表示待处理的进程页面顺序，diseffect置0，设定循环周期CLEAR_PERIOD。 （2）看main是否有下一个元素。 若有，就从main中获得一个CPU将处理页面的序号；如果没有就转到 （8）。 （3）如果待处理的页面在内存中，就转到 （2）；否则diseffect加1，并转到 （4）。 （4）看是否有空闲得内存页面，如果有，返回空闲内存页面指针，并转到 （5）；否则，在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的?）取出一个，返回清空后的内存页面指针。 （5）在待处理进程页面与内存页面之间建立联系，并标注该页被访问。 （6）如果CPU已处理了CLEAR_PERIOD个页面，就将所有页面均设为“未访问”。 （7）返回 （2）。 （8）如果CPU所有处理工作完成，就返回1-(disaffect/total_instruction)*100%的结果，并结束。 4.OPT算法?原理简述所谓的最佳算法是一种理想状况下的算法，它要求先遍历所有的CPU待处理的进程页面序列。 在这些页面中，如果有些已经在内存中，而CPU不再处理的，就将其换出；而有些页面已在内存中而CPU即将处理，就从当前位置算起，取最后才会处理到的页面，将其换出。 如CPU待处理的页面序列为13224525143411553421如果已经处理了前5个页面（底纹为黑色），那么随后的页面5是第一个待处理的页面，这时若要将页面5调入内存，需选择页面3换出，因为页面3是最后才会被处理到的。 ?图表描述这里采用的例子和前面的一样。 假设某个进程在硬盘上被划分成5个页面（PP=5），以 1、 2、 3、 4、5分别表示，CPU调用它们的顺序（这应该取决于进程本身）为 1、 4、 2、 5、 3、 3、 2、 4、 2、5，而内存可以控制的页面数为3（AP=3），那么在使用LRU算法时，这三个页面的内存使用情况应该如图8所示。 不难看出，本例共换入页面6次，若用变量diseffect表示页面换入次数，则diseffect=6。 图8?算法实现提示为每个进程页面设一个“间隔”属性cDistance表示CPU将在第几步处理到该页面，如果页面不再被CPU处理，可以被设为某个很大的值（如32767），这样每次被换出的就是cDistance最大的那个页面。 （1）初始化。 设置两个数组pageap和pagecontrolpp分别表示进程页面数和内存分配的页面数，并产生一个随机数序列maintotal_instruction（这个序列由pageap的下标随机构成）表示待处理的进程页面顺序，diseffect置0。 然后扫描整个页面访问序列，对cDistanceTOTAL_VP数组进行赋值，表示该页面将在第几步被处理。 （2）看序列main中是否有下一个元素，如果有，就由main中获