操作系统课内实验报告西安交通大学

®む文遊ス學实验报告实验课程: 操作系统原理学生姓名: 高君宇 学号:2110505112专业班级: 计算机15班2013年12月29日实验ー:用户接口实验ー、实验内容1)控制台命令接口实验该实验是通过“几种操作系统的控制台命令:*’终端处理程序ア‘命令解释程序”和"Linux操作系统的bash”来让实验者理解面向操作命令的接口shell和进行简单的shell编A 査看bash版本。A编写bash脚本,统计/my目录下c语言文件的个数2)系统调用实验该实验是通过实验者対''Linux操作系统的系统调用机制”的进ー步了解来理解操作系统调用的运行机制:同时通过''自己创建一个系统调用mycall(，和''编程调用自己创建的系统调用”进ー步掌握创建和调用系统调用的方法。A编程调用一个系统调用fork()观察结果。A编程调用创建的系统调用fo。()观察结果。A自己创建一个系统调用mycall()实现功能:显示字符串到屏幕上。A编程调用自己创建的系统调用。二、实验准备为了使用户通过操作系统完成各项管理任务操作系统必须为用户提供各种接口来实现人机交互。经典的操作系统理论将操作系统的接口分为控制台命令和系统调用两种。前者主要提供给计算机的操作人员对计算机进行各种控制:而后者则提供个程序员,使他们可以方便地使用计算机的各种资源。三、源程序1、控制台命令接口实验(1)查看bash版本在shell提示符下输入：$echo$BASH_VERS10N我们的版本是4.2.37(1)-release(2)建立bash脚本,输出Helloword在编辑器中输入以下内容#!/bin/bashechoHelloWorld!执行脚本使用指令:lai•r«MJblnv;-3./Wflt&Melt)/，4—皿ヤS”3vtrtiulrudblmti|とヨ二(3)编写bash脚本:统计/my目录下c语言文件的个数通过bash脚本,可以有多种方式实现这个功能,而使用函数是其中个ー个选择。在使用函数之前，必须先定义函数。进入自己的工作目录，编写名为count的文件脚本程序:#!/bin/bashfunctioncount(echo-n"Numberofmatchesfor$1:" #接收程序的第一个参数Is$llwc-1#对子程序的第一个参数所在的目录进行操作)将count文件复制到当前目录下，然后在当前目录下建立文件夹，在my目录下建立几个c文件,以便用来进行测试2、系统调用实验(1)系统调用是操作系统为程序员提供的接口服务。使用系统调用,程序员可以更充分的利用计算机资源，使编写的程序更加灵活,功能更加强大。程序员在对系统充分了解的情况下甚至可以订做系统调用，实现那些非专亜程序员所难以实现的功能。同时通过“自己创建一个系统调用mycall(ケ和“编程调用自己创建的系统调用”进ー步掌握创建和调用系统调用的方法。a,添加源代码在/usr/src/linux/kemel/sys.c文件中添加源代码，如ド所示：asmlinkageintsys_foo(intx){printf("％d\n”,x);)b.连接新的系统调用进入目录/usr/src/linux/include/asm-i386/,打开文件unistd.h»这个文件包含了系统调用的淸单,用来给每个系统调用分配ー个唯一・的号码。进入/usr/src/linux/arche/i386/kemel/,打开文件entry.S。重新编译内核配置内核(建议使用默认配置,仅仅修改localversionsB|J,可当然也可以把一些无用的模块去掉)makemenuconfig编译内核スjN中的N表示使用多少个线程编译,一般为处理器数目+1)make-j5bzlmage编译内核模块make-j5modules安装内核模块(需要root权限)提示:模块被安装在/lib/modules/versions/下(比如2.6.31内核在config时设定其的localversions为-myservice,那么versions为2.6.31-myservice)sudomakemodules_install安装内核提示在较新的Linux发行版中会自动生成init内存文件系统,并将配置文件内核及init内存文件系统拷贝至リ/boot目录下,最后更新引导。重启系统完成以上配置后,重新启动系统进入自己的新系统(2)编程调用ー个系统调用fork()观察结果。#include<stdio.h>intmain()(intiUid;illid=fork();if(iUid=O)for(;;) {printf(""Thisisparent.\n");sleep(l);}if(iUid>0)for(;;){printf("Thisischild.\n");sleep(l);}if(iUid<0)printf(，zCannotusesystemcall.\n*);return0;)编程调用创建的系统调用f。。()观察结果。#include<stdio.h>ttinclude<linux/unistd.h>_syscall1(char*,foo,int,ret)main(){intI,J;1=100;J=0;J=foo(I);printf〈Thisistheresultofnewkernel\n");printf("%d",j);)编程调用自己创建的系统调用。#include<linux/unistd.h>syscalll(char*,mycall,int,ret)intmain()char*str;charstring[50];str=string;str="Thisstringwillbedisplayed.";mycall(str);return0;附:内核编译1编译内核的基本步骤将vm和win共享的sharedfolders文件夹中的linux_3.05tar.bz2拷贝到/usr/src目录下更改用户权限sudo-sa.进入sharedfolders:cd/mnt/hfgs/sharedfolders/b.拷贝:cplinux-3.0.5.tar.bz2/usr/src/解压!inux源码:进入目录/usr/srctarxvzflinux-3.0.5.tar.bz2进入目录linux・3.0.5,输入命令makemenuconfiga.fedora和Centos通过yuminstallncurses-devel解决b.UbuttuホロDebian通过sudoapt-getinstallIibncurses5-dev(4)在图形界面中设置config,一般进入GeneralSetup中修改ー下内核名称即可(5)编译内核:make-j4bzlmage(开4个线程编译,如果是单核的cpu就不用加•j4参数了),编译结束以后,出现Kernel:arch/x86/boot/bzlmageisready(#1)则说明内核编译成功(6)编译模块:make-j4modules(时间较长)(7)模块安装:makemodulesjnstall(8)安装内核:makeinstall在高版本中,makeinstall命令会自动生成启动文件,在低内核版本中,需要添加。所以,我们还需要看一下有没有生成启动文件,如果没有,则需要自己手动添加。(9)查看内核是否添加:cat/boot/proc/proc.conf2、创建系统调用的基本步骤(1)在!inux-3.2.11/kernel下创建mysyscall.c文件,内容如下:#include<linux/kernel.h>asmlinkagelongsys_mysysca11(void){printk(KERN_ALERT"Thisismysyscall!\n");return0;}(2)在!inux-3.2.11/kernel/Makefile中加入:obj-y+=mysyscall.o(3)在!inux-3.2.11/include/linux/syscalls.h中加入:asmlinkagelongsys_mysysca11(void);(4)在linux・3.2.11/arch/x8%kernel/syscall_table_32.S(如果是64位机器则32替换为64)中加入：.longsys_mysyscall在linux-3.2.11/arch/x86/ia3^/ia32entry.S中加入:.quadsysmysyscall(5)在!inux-3.2.1Varch/x86/include/asm/unistd_32.h中加入:#define_NR_mysyscall 349并将#defineNR_syscalls349替换为#defineNR_syscalls350(这里根据实际情况,_NR_mysyscal!为现有最大值,NR_syscalls加ー即可)(6)重新编译、安装、重启(7)测试查看/proc/kallsyms中是否有mysyscall,如果有,表示符号已经导出。编译运行,输出。即为正确,-1为错误。若运行正确,用dmesg査看,末尾有输出:Thisismysyscall!编译内核成功截图:FileEditViewSearchTerminalHelpAS .tmpkallsyms2.o 'LD vmlinuxSYSMAPSystem.mapSYSMAP.tmpSystem.mapVOFFSETarch/x86/boot/voffset.hCCarch/x86/boot/version.oOBJCOPYarch/x86/boot/compressedハmlinux.binRELOCSarch/x86/boot/compressed/vmlinux.relocsGZIParch/x86/boot/coinpressed/vmlinux.bin.gzMKPIGGYarch/x86/boot/compressed/piggy.SASarch/x86/boot/compressed/piggy.oLDarch/x86/boot/compressed/vmlinuxZOFFSETarch/x86/boot/zoffset.hOBJCOPYarch/x86/boot/vmlinux.binASarch/x86/boot/header.oLDarch/x86/boot/setup.elfOBJCOPYarch/x86/boot/setup.binBUILDarch/x86/boot/bzlmageRootdeviceis(8,1)Setupis14124bytes(paddedto14336bytes).Systemis4456kBCRC84335C86Kernel：a「ch/x86/boot/bzlmaaeisreadv(#7)2、编译模块成功截图:

FileEditViewSearchTerminalHelpCRC84335C86Kernel：arch/x86/boot/bzlmageisready(#7)root@zhangtong-virtual-machine:/usr/src/linux-3.0.50#makeinstallmage\sh/usr/src/linux>3.6.56/arch/x86/boot/install.sh3.6.56-zhangarch/x86/boot/bzlmage\run-parts：executingmlinuz-3.6.56-zhangrun-parts：executinginuz-3.6.50-zhangrun-parts：executing3.0.50-zhangrun-parts：executingmlinuz-3.0.50-zhangrun-parts：executinglinuz-3.0.50-zhangSystem.map"/boot"run-parts：executingmlinuz-3.6.56-zhangrun-parts：executinginuz-3.6.50-zhangrun-parts：executing3.0.50-zhangrun-parts：executingmlinuz-3.0.50-zhangrun-parts：executinglinuz-3.0.50-zhangSystem.map"/boot"Generatinggrub.cfg...Foundlinuximage：/boot/vmlinuz-3.0.50-zhangFoundlinuximage:/boot/vmlinuz-3.0.50-zhang.oldFoundlinuximage:/boot/vmlinuz-2.6.38-8-genericFoundinitrdimage:/boot/initrd.img-2.6.38-8-genericFoundmemtest86+image：/boot/memtest86+.bindone实验中出现的问题:在进行内核编译时,首先遇到的困难就是将缺少的程序补入,但因为本省Ubantu所带的编辑器很不好用在输入过程中就花费了非常大的时间但最后经过学长的帮助顺利完成。在编译期间有经历了一个多小时的时间,最后编译成功。在编写调用程序并进行验证的过程中，只能通过自己在网上查找资料，并借鉴同学的作法，最终完成。四、实验体会通过本次实验，我们理解了面向操作命令的接口Shell,学会了简单的shell编码,理解了操作系统调用的运行机制,掌握了创建系统调用的方法。本次实验通过内核编译，将一组源代码变成操作系统的内核，并由此重新引导系统，这让我们初步了解了操作系统的生成过程。实验ニ:进程管理实验ー、实验内容1）编制实现软中断通信的程序使用系统调用fork。创建两个了进程，再用系统调用signal。让父进程捕捉键盘上发出的中断信号（即按delete键）当父进程接收到这两个软中断的某ー个后，父进程用系统调用kill。向两个子进程分别发出整数值为16和17软中断信号,子进程获得对应软中断信号，然后分别输出下列信息后终止:Childprocess1iskilledbyparent!!Childprocess2iskilledbyparent!!父进程调用wait。函数等待两个子进程终止后,输入以下信息,结束进程执行:Parentprocessiskilled!!多运行几次编写的程序,简略分析出现不同结果的原因。2）编制实现进程的管道通信的程序使用系统调用pipe。建立一条管道线,两个子进程分别向管道写一句话:Childprocess1issendingamessage!Childprocess2issendingamessage!而父进程则从管道中读出来自于两个子进程的信息,显示在屏幕上。要求:父进程先接收子进程P1发来的消息,然后再接收子进程P2发来的消息。二、实验分析1、进程软中断实现:算法流程图:

亘）相关函数:wait。函数wait。函数常用来控制父进程与子进程的同步。在父进程中调用wait。函数,则父进程被阻塞,进入等待队列,等待子进程结束。当子进程结束时,产生一个终止状态字,系统会向父进程发出SIGCHLD信号。当接到信号后,父进程提取子进程的终止状态字，从wait。函数返回继续执行原来的程序。其调用格式为:#include<sys/type.h>#include<sys/wait.h>(pid_t)wait(int*statloc);正确返回:大于0,子进程的进程!D值。等于0,其他。错误返回:等于ー1,调用失败。exit。函数exit。函数是进程结束时最常调用的函数在main。函数屮调用return最终也是调用exit。函数。这些都是进程的正常终止。在正常终止时,exit。函数返回进程结束状态。其调用格式为：#include<stdio.h>voidexit(intstatus);其中,status为进程结束状态。kill。函数kill()函数用于删除执行中的程序或者任务。其调用格式为：kill(intPIDjntIID);其中,PID是要被杀死的进程号,HD为向将被杀死的进程发送中的中断号。Signal。函数signal。函数是允许调用进程控制软中断信号的处理。其调用格式为：#include<signal.h>intsig;signaKsig,function);2.管道实现:管道是指用于连接・个读进程和一个写进程以实现它们之间信息的共享文件又称pipe文件。向管道（共享文件）提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道;而接收管道输送的接收进程（读进程）可以从管道中接收数据。为了协调双方的通信,管道通信机制必须提供以下3方面的协调能力:A互斥。当一个进程正在对pipe进程读/写操作时,另ー进程必须等待。程序中使用lock（fd[l],1,0）函数实现对管道的加锁操作。用lock（fd[1],0,0）解除管道的锁定A同步。当写进程把一定数量的数据写入pipe后,便去睡眠等待,直到读进程取走数据后,再把它唤醒。当读进程试图从ー空管道中读取数据时，也应睡眠等待，直至写进程将数据写入管道后,オ将其唤醒。A判断对方是否存在。只有确定写进程和读进程都存在的情况下,才能通过管道进行通信。在该程序中,使用父进程创建两个子进程，其中一个向管道中写数据，另一个从管道中读数据,父进程控制读写的互斥和同步。利用管道锁机制控制两次写或两次读的互斥。父进程创建子进程1,使之向管道中写数据,写好后，结束子进程1,并向父进程发中断,父进程收到中断信号后,再创建子进程2,子进程2从管道中读数据，读完后结束，并向父进程发中断。三、源程序1、进程软中断:#include<stdio.h>#include<signal.h>#include<unistd.h>#include<sys/types.h>intwait_flag;voidstop();main(){intpidl,pid2;//定义两个进程号变量signal(3,stop);/Z或者signal(14,stop);while((pidl=fork())=-1); //环若创建子进程1不成功,则空循if(pidl>0){ 〃子进程创建成功,pidl为进程号い〃・ハケfレハ、い〃创建子进程2while((pid2=fork())=-1);//if(pid2>0){wait_flag=1;sleep(5);/Z父进程等待5秒kill(pidl,16);/Z杀死进程1kill(pid2,17);/Z杀死进程2//等待第1个子进程1结束的信wait(0); .rwait(0); //等待第2个子进程2结束的信printf("\nParentprocessiskilled!!\nM);exit(O); /Z父进程结束}else{wait_flag=1;signal(17,stop);/Z等待进程2被杀死的中断号17printf(M\nChildprocess2iskilledbyparent!!\nn);exit(O);)}else{wait_flag=1;signal(16,stop); /Z等待进程1被杀死的中断号16printf("\nChildprocess1iskilledbyparent!!\nM);exit(O);}voidstop(){wait_flag=0;)实验结果:Childprocess1iskilledbyparent!!Childprocess2iskilledbyparent!!Parentprocessiskilled!!实验结果简要分析:上述结果中“Childprocess1iskilledbyparent!!"和"Childprocess2iskilledbyparent!!”相继出现,当运行几次后,谁在前谁在后是随机的。这是因为:从进程调度的角度看,子进程被创建后处于就绪态。此时,父进程和子进程作为两个独立的进程,共享同一个代码段,分别参加调度、执行,直至进程结束。但是谁会先被调度程序选中执行,则与系统的调度策略和系统当前的资源状态有关,是不确定的。因此,谁先从fork。函数中返回继续执行后面的语句也是不确定的。2、管道实现#include<unistd.h>#include<signal.h>#include<stdio.h>intpidl,pid2;main(){intfd[2];charOutPipe[100],InPipe[100];pipe(fd);while((pidl=fork())=-1);if(pidl==0){lockf(fd[l],l,0);sprintf(OutPipe,"Childprocess1issendingmessage!\n");write(fd[l],OutPipe,50);sleep(5);exit(O);)else(wait(O);while((pid2=fork())==-I);if(pid2=0){read(fd[O],InPipe,50);printf(M%s\nM,InPipe);printf("Childprocess2isreceivingmessage!\n");lockf(fd[0],0,0);exit(O);)else{wait(0)；exit(O);}运行结果:iott.c:Infunctionmain:ioft.c:17: warning: incompatible implicit declaration of built-in function *exit;oft.c:31: warning: incompatible implicit declaration of built-in function *exitioft.c：35: warning: incompatible implicit declaration of built-in function *exitihane@shane-VirtualBox:'$./a.out:hildprocess1issendingmessage!：hildprocess2isreceivingmessage!ihane@shane-VirtualBox:|四、实验体会通过本次实验,我们理解了进程的实质和进程管理的机制。进程是操作系统中最重要的概念是现代操作系统的关键实验中我们在Linux系统下实现进程从创建到终止的全过程,体会了进程的创建过程、父进程和子进程的关系、进程状态的变化、进程之间的同步机制、进程调度的原理和以信号和管道为代表的进程间通信方式的实现。实验三:存储器管理实验ー、实验内容对比以下几种算法的命中率:1)先进先出算法FIFO(FirstInFirstOut)2)最近最少使用算法LRU(LeastRecentlyUsed)最近未使用算法NUR(NeverUsedRecently)4)最佳置换算法OPT(OptimalReplacement)二、实验分析.置换算法原理*FIFO原理简述在分配内存页面数(AP)小天进程页面数(PP)时,当然是最先运行的AP个页面放入内存:这时又需要处理新的页面,则将原来放的内存中的AP个页中最先进入的调出(FIFO)再将新页面放入:以后如果再有新页面需要调入,则都按上述规则进行。算法特点:所使用的内存页面构成一个队列。*LRU算法原理简述当内存分配页面数（AP）小于进程页面数（PP）时,把最先执行的AP个页面放入内存。当需调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那ー页调出，以空出内存来放置新调入的页面（LRU）算法特点:每个页面都有属性来表示有多长时间未被CPU使用的信息。*NUR算法原理简述所谓‘‘最近未使用;’首先是要对’‘近”做ー个界定,比如CLEAR.PERIOD=50,便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面。那么可能会有以ド几种情况:如果这样的页面只有一个，就将其换出,放入需要处理的新页面。如果有这样的页面不止ー个，就在这些页面中任取ー个换出（可以是下标最小的或者最小的）放入需要处理的页面。如果没有一个这样的页面，就随意换出ー个页面（可以是下标最小的或者最大的）*OPT原理简述所谓的最佳算法是ー种理想状况下的算法,它要求先遍历所有的CPU待处理的进程页面序列。在这些页面中，如果有些已经在内存中，而CPU不再处理的，就将其换出:而有些页面已在内存中而CPU即将处理，就从当前位置算起，取最后才会处理到的页面，将其换出。2.OPT算法实现:为每个进程页面设ー个“间隔”属性eDistance表示CPU将在第几步处理到该页面,如果页面不再被CPU处理,可以被设为某个很大的值(如32767)这样每次被换出的就是eDistance最大的那个页面。初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数并产生一个随机数序列main[total_instruction](这个序列由page[ap]的下标随机构成)表示待处理的进程页面顺序,diseffect置。。然后扫描整个页面访问序列，对cDistance[TOTAL_VP]数组进行赋值，表示该页面将在第几步被处理。看序列main[]中是否有下ー个元素，如果有,就由main」中获取ー个CPU待处理的页面号，并转(3)如果没有则转(6)如果该页面已经在内存中了，就转(2)否则转(4)同时•diseffect加1。看是否有空闲页面,如果有,就返回页面指针,并转到(5)否则,遍历所有未处理的进程页面序列，如果有位于内存中的页面而以后CPU不再处理的，首将其换出,返回页面指针:如果没有这样的页面,找出CPU将最晚处理的页面,将其换出,并返回该页面指针。在内存页面和待处理的进程页面之间建立联系，转(2)输出计算ldseffecUtotaLinstruction*100%的结果，完成。三、源程序#include<iostream>#include<string>#include<vector>#include<cstdlib>#include<cstdio>#include<unistd.h>usingnamespacestd;#defineINVALID-1constintTOTAL^_INSTRUCTION(320);constintTOTAL_VP(32);constintCLEAR_PERIOD(50);#include"Page.hu#include''PageConlroLh"#includenMemoryhMintmain()(inti;CMemorya;for(i=4;i<=32;i++)(a.FIFO(i);a.LRU(i);a.NUR(i);a.OPT(i);cout«M\nu;}return0;}#ifndef_MEMORY_H#define_MEMORY_HclassCMemory(public:CMemoryO;voidinitialize(constintnTotal_pf);voidFIFO(constintnTotal_pf);voidLRU(constintnTotal_pf);voidNUR(constintnTotal_pf);voidOPT(constintnTotal_pf);private:vector<CPage>_vDiscPages;vector<CPageControl>_vMemoryPages;CPageControl*_pFreepf_head,*_pBusypf_head,*_pBusypf_tail;vector<int>_vMain,_vPage,_vOffset;int_nDiseffect;)；CMemory::CMemory():_vDiscPages(TOTAL_VP),_vMemoryPages(TOTAL_VP),_vMain(TOTAL_INSTRUCTION),_vPage(TOTAL_INSTRUCTION),_vOffset(TOTALJNSTRUCTION){intS?i,nRand;srand(getpid()*10);nRand=rand()%32767;S=(float)31#nRand/32767+1;for(』0;ivTOTAL_INSTRUCTION;i+=4){_vMain[i]=S;_vMain[i+l]=_vMainfi]+1;nRand=rand()%32767;_vMain[i+2]=(float)_vMain[i]:f:nRand/32767;_vMainti+3]=_vMainli+2J+l;nRand=rand()%32767;S=(float)nRand*(318-_vMain[i+2])/32767+_vMain[i+2]+2;for(i=0;i<TOTAL_INSTRUCTION;i++){_vPage[i]=_vMain[i]/10;_vOflfset[i]=_vMain[i]%10;_vPage[i]%=32;}}voidCMemory::initialize(constintnTotal_pf)(intix;_nDiseffect=O;for(ix=0;ix<_vDiscPages.size();ix++){_vDiscPages[ix].m_nPageNumber=ix;_vDiscPages[ix].m_nPageFaceNumber=INVALID;_vDiscPages[ix].m_nCounter=0;_vDiscPages[ix].m_nTime=-1;}for(ix=1;ix<nlbtal_pf;ix++){_vMemoryPages[ix-l].m_pNext=&_vMemoryPages[ix];_vMemoryPages[ix-l].m_nPageFaceNumber=ix-l;}_vMemoryPages[nTotal_pf-1].m_pNext=NULL;_vMemoryPages[nTotal_pf-l].m_nPageFaceNumber=nTotal_pf-1;_pFreepf_head=&_vMemoryPages[0];voidCMemory::FIFO(constintnTotal_pf)(inti;CPageControl*p；initialize(nTotal_pf);_pBusypf_head=_pBusypf_tail=NULL;for(i=0;i<TOTAL_INSTRUCTION;i4-+){if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID){_nDiseffect+=l;if(_pFreepfLhead==NULL)//noemptypages(p=_pBusypLhead->m_pNext;_vDiscPages[_pBusypf_head->m_nPageNumber].m_nPageFaceNumber=INVALID;_pFreepf_head=_pBusypf_head;_pFreepf_head->m_pNext=NULL;_pBusypf_head=p;)p=_pFreepf_head->m_pNext;_pFreepf_head->m_pNext=NULL;_pFreepChead->m_nPageNumber=_vPage[i];_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepfLhead->m_nPageFaceNumber;if(_pBusypf_tail==NULL)_pBusypf_head=_pBusypf_tail=_pFreepf_head;else_pBusypOail->m_pNext=_pFreepfLhead;_pBusypf_tail=_pFreepf__head;)_pFreepf_head=p;))cout«MFIFO:M«1-(float)_nDiseffect/320;}voidCMemory::LRU(constintnTotal_pf)(inti,j,nMin,minj,nPresentTime(O);initialize(nTotal_pf);for(i=0;i<TOTAL_INSTRUCTION;i4-+){if(_vDiscPages[_vPage[iJ].m_nPageFaceNumber==INVALID){_nDiseffect4-+;if(_pFreepf_head==NULL)(nMin=32767;for(j=0;j<TOTAL_VP;j++)//getthesubscribeoftheleastusedpage//aftertherecycleiMinisthenumberoftimes//usedoftheleastusedpagewhileminjisitssubscribeif(nMin>_vDiscPages[j].m_nTime&&_vDiscPages[j].m_nPageFaceNumber!=INVALID)(nMin=_vDiscPages[j].m_nTime;minj=j;_pFreepf_head=&_vMemoryPages[_vDiscPages[minj].m_nPageFaceNumber];_vDiscPages[minj].m_nPageFaceNumber=INVALID;_vDiscPages[minj].m_nTime="l;_pFreepChead->m_pNext=NULL;|_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_vDiscPages[_vPage[i]].m_nTime=nPresentTime;_pFreepf_head=_pFreepf_head->m_pNext;}else_vDiscPagesLvPage[i]].m_nTime=nPresentTime;nPresentTime++;)cout«nLRU:"«1-(float)_nDiseffect/320;}voidCMemory::NUR(constintnTotal_pO(intij,nDiscPage,nOld_DiscPage;boolbCont_flag;initialize(nTotal_pf);nDiscPage=O;for(i=0;i<TOTAL_INSTRUCTION;i++)(if(_vDiscPages[_vPage[iJ].m_nPageFaceNumber==INVALID){_nDiseffect++;if(_pFreepLhead==NULL)bCont_flag=true;nOld_DiscPage=nDiscPage;while(bCont_flag){if(_vDiscPages[nDiscPagel.m_nCounter==0&&_vDiscPages[nDiscPage].m_nPageFaceNumber!=INVALID)bCont_flag=false;else(nDiscPage++;if(nDiscPage==TOTAL_VP)nDiscPage=O;if(nDiscPage==nOld_DiscPage)for(j=0;j<TOTAL_VP;j++)_vDiscPages|j].m_nCounter=0;)}_pFreepf_head=&_vMemoryPages[_vDiscPages[nDiscPage].m_nPageFaceNumber];_vDiscPages[nDiscPageJ.m_nPageFaceNumber=INVALID;_pFreepf_head->m_pNext=NULL;}_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_pFreepLhead=_pFreepLhead->m_pNext;}else_vDiscPages[_vPage[i]].m__nCounter=1;if(i%CLEAR_PERIOD==0)for(j=0;j<TOTAL_VP;j++)_vDiscPages[j].m_nCounter=0;cout«uNUR:H«l-(float)_nDiseifect/320;voidCMemory::OPT(constintnTotal_pO{inti,j,max,maxpage,nDistance,vDistance[TOTAL_VP];initialize(nTotal_pO;for(i=0;i<TOTAL_INSTRUCTION;i++){if(_vDiscPagesLvPage[i]].m_nPageFaceNumber==INVALID)(_nDiseffect++;if(_pFreepf_head==NULL){for(j=0;j<TOTAL_VP;j++)if(_vDiscPages[j].m_nPageFaceNumber!=INVALID)vDistance[j]=32767;elsevDistance[j]=O;nDistance=l;for(j=i+l;j<TOTALJNSTRUCTION;j++)(if((_vDiscPages[_vPage[j]].m_nPageFaceNumber!=INVALID)&&(vDistance[_vPage[j]]==32767))vDistance[_vPage|jJ]=nDistance;nDistance++;max=-l;for(j=0;j<TOTAL_VP;j++)if(max<vDistance[j])(max=vDistance[j];maxpage=j;}_pFreepL_head=&_vMemoryPages[_vDiscPages[maxpage].m_nPageFaceNumber];_pFreepf_head->m_pNext=NULL;_vDiscPages[maxpage].m_nPageFaceNumber=INVALID;I_vDiscPages[_vPage[i]J.m_nPageFaceNumber=_pFreepChead->m_nPageFaceNumber;_pFreepf_head=_pFreepf_head->m_pNext;))cout«nOPT:"«1-(float)_nDiseffect/320;}实验结果:

FIFO:0.53125LRU:0.5375NUR:0.534375OPT:0.63125FIFO:0.54375LRU:0.546875NUR:0.5375OPT:0.665625FIFO:0.553125LRU:0.559375NUR:0.559375OPT:0.6875FIFO:0.56875LRU:0.565625NUR:0.575OPT:0.70625FIFO:0.58125LRU:0.58125NUR:0.59375OPT:0.725FIFO:0.6LRU:0.590625 NUR:0.6 OPT:0.74375FIFO:0.61875LRU:0.615625NUR:0.6125OPT:0.759375FIFO:0.63125LRU:0.628125NUR:0.634375OPT:0.775FIFO:8.640625LRU:0.634375NUR:0.640625OPT:0.7875FIFO:0.659375LRU:0.653125NUR:0.640625OPT:0.8FIFO:0.671875LRU:0.66875NUR:0.665625OPT:0.8125FIFO:0.684375LRU:0.68125NUR:0.6625 OPT:0.821875FIFO:0.690625LRU:0.7125NUR:0.68125OPT:0.83125FIFO:0.690625LRU:0.71875NUR:0.703125OPT:0.840625FIFO::0.725LRU:0.7375NUR:0.746875OPT:0.846875FIFO::0.74375LRU:0.746875NUR:0.746875OPT:0.853125FIFO::0.75LRU:0.759375NUR:0.784375OPT:0.859375FIFO:0.759375LRU:0.775NUR:0.7625OPT:0.865625FIFO:0.7625LRU:0.784375NUR:0.7875 OPT:0.871875FIFO:0.803125LRU:0.80625NUR:0.790625 OPT:0.878125FIFO:0.815625LRU:0.8125NUR:0.825OPT:0.884375FIFO:0.81875LRU:0.840625NUR:0.840625OPT:0.890625FIFO:0.8375LRU:0.846875NUR:0.84375OPT:0.89375FIFO:0.8375LRU:e1.859375NUR:0.859375OPT:0.896875FIFO:0.88125LRU:0.8625NUR:0.85625OPT:0.9FIFO:0.88125LRU:0.884375NUR:0.896875 OPT:0.9FIFO:0.8875LRU:e,896875NUR:0.896875OPT:0.9FIFO:0.9LRU:0.9NUR:0.896875OPT:0.9FIFO:0.9LRU:0.9NUR:0.9OPT:0.9四、实验体会通过本次实验,我们理解了内存页面调度的机制,掌握了几种理论页面置换算法的实现方法,了解了HASH数据结构的使用。页面置换算法是虚拟存储管理实现的关键,FIFO、LRU.NRU和OPT是几种经典页面置换算法,我们通过实现这几种算法,比较了较各种页面置换算法的效率及优缺点，从而了解了虚拟存储实现的过程。实验四:文件系统实验ー、实验内容2）设计并实现ー个ー级（单用户）文件系统程序a.提供以下操作:A文件创建/删除接口命令create/deleteA 目录创建珊リ除接口命令mkdir/rmdirA 显示目录内容命令Isb.创建的文件不要求格式和内容3）设计并实现ー个二级文件系统程序a.提供用户登录;b.文件、目录要有权限二、实验分析.基本思路:用ー个文件（disk.txt）模拟ー个物理硬盘,通过对该文件的一系列操作,模拟UNIX文件系统中的文件操作。.理磁盘块的设计:卷盘块数等于100块,每个磁盘块512字节,磁盘块之间用/n隔开,总共是514字节。0#表示超块，1#一10#放索引结点,每个索引结点占64字节，共80个索引结点。初始化是存在根目录root,占用了0#结点和11#盘块。.空闲磁盘块:采用成组链接法管理。每组10块，12#—99#分为9组,每组的最后一个磁盘块里存放下ー组的磁盘号信息。最后ー组只有8块,加上。作为结束标志。在超块中用ー个ー维数组（10个元素）作为空闲磁盘块栈。放入第一组盘块。.空闲I结点采用混合索引式文件结构。索引结点结构中文件物理地址为六项:四个直接块号,一个一次间址,ー个两次间址，其中一次间址和两次间址中一个磁盘块中存放16个磁盘号。在超块中也用ー维数组（80个元素）作为空闲I结点栈，与空闲磁盘块管理不同的是这里不用采用成组链接法,这ー维数组中存放所有I结点编号,而且一直保持同一大小秩序。根目录占〇#索引结点,由于根目录不会删改,是一直占0#索引结点,所以我并未按实验指导所说，把它写在超块里，不过写进去也无所谓的。.超级块，I结点和目录结构的设计structSUPERBLOCK〃超级块（intfistack[80];〃空闲结点号栈intfiptr;//空闲结点栈指针（还有多少个）intfbstack[10];〃空闲盘块号栈intfbptr;//空闲结点栈指针intinum;〃空闲i结点总数intbnum;//空闲盘块总数｝；struct11»0^7バ结点（64B） 已保证了每两个数据之间有空格隔开intfsize;〃文件大小intfbnum;〃文件盘块数int2£!打[4];〃四个直接盘块号(0ヽ512*4==2048)intaddrl;〃ー个一次间址()intaddr2;〃ー个两次间址()charowner[6];〃文件拥有者chargroup[6];〃文件所属组charmode[ll]://文件类别及存储权限charctime[9];〃最近修改时间｝；structDIR〃目录项(36B)｛charfname[14];〃文件名(当前目录)intレ(10ス;〃1结点号charparfname[14];〃父目录名intparindex;〃父目录i结点号｝；.用户,密码和组用户组信息是存放在另ー个文件(user,txt)中的。各个主要功能函数的说明main,cpp:是程序的主函数模块主函数首先会根据控制文件control,txt的头ー个位(初始化确定位)来确定是否进行初始化。如果初始化,那么将只有一个根目录。因为一旦初始化后,初始化确定位就会置为0,所以系统只会在第一次进入时初始化，以后都是在前面建立的文件结构上进行操作的。如果一定要系统初始化时，可把control.txt的头一个位置为1,或者使用命令"reset”。进入系统时，当前路径是根目录。然后是登陆请求。登陆后，超块读入内存(由一个结构对象superblock模拟)进入命令解析层，对用户的不同命令执行不同的操作。退出系统前，把内存的超块再写回disk,txt。head,h:是程序的所有全局变量、结构、函数声明的模块。也包括了所有要用到的系统库。blockinodesuperblock.h:是定义有关超块、结点、盘块、目录项的底层操作函数的模块。1.对结点的操作:intialloc(void);申请ー个i结点返回结点号否则返回一:!。返回的是空闲结点号栈中最小的结点号,结点用完时返回T,申请失败。voidifree(intindex):指定一个结点号,回收ー个i结点。先清空结点,然后插入栈中合适位置(必须保持结点号的有序性)voidreadinode(intindex,INODE&inode);读指定的i结点(n#结点,读指针应定位到514+64*n(64B)+2*(n/8))到INOEinode寄存便于对同一结点的大量操作voidwriteinode(INODEinode,intindex);把INODEinode写回指定的i结点对盘块的操作;用的是成组链接法。(n#盘块读指针应定位到514*n)intballoc(void);申请ー个盘块返回盘块号否则返回-1voidbfree(intindex);指定一个盘块号,回收ー个盘块对超块的操作:voidreadsuper(void);读超块到内存SUPERBLOCKsuperblock;voidwritesuper(void);内存SUPERBLOCKsuperblock;写回超块对目录项的操作(n#目录项读指针应定位514*index+36*n)voidreaddir(INODEinode,intindex,DIR&dir);读指定目录项进临时对象DIRdir;voidwritedir(INODEinode,DIRdir,intindex);目录项对象DIRdir写到指定目录项initial,h:是定义初始化函数的模块其中包括了对用户组的初始化定义三个用户adm,cnj和jtq,其中adm,cnj的组为adm,jtq的组为guest。用户的初始密码都为123。对超块的(0#盘块)初始化、对根目录文件结点(0#结点)的初始化、对数据盘块的初始化。userop.h:定义了两个功能函数:.登陆boollogin(void);要求输入用户信息,并判断是否合法。.改变用户密码voidchangepassword(void):改变当前用户的密码。file,h:定义了有关文件操作的四个函数.创建文件voidmk(char*dirname,char*content)!当前目录下创建一个数据文件(规定目录文件只占1~4个盘块)。虽然不要求这个函数,但我觉得很有必要。而且,因为我使用了两个参数,前ー个表示文件名，后一个表示文件内容，可以在文件拷贝里使用这个函数。.删除文件voidrm(char*filename)：当前目录下删除指定数据文件.文件拷贝voidcp(char*string);给定一个路径,把那个文件拷贝到当前目录下。首先要使用dir.h里面根据路径找到目标的函数(find(char*string))找到对应文件,如果是数据文件的话,记录文件内容到ー缓冲区，然后在当前目录下调用创建目录的函数，就完成了。.显示文件内容voidcat(char*filename)：显示当前目录下指定数据文件的内容。dir.h:定义两个底层函数boolhavesame(char*dirname,INODEinode,int&i,int&index2)判断对象inode指向的目录文件盘块中有无该名(dirname)的目录项存在着,有返回1无返回0。同时，有该目录项的话，则按引用调用的i为待删子目录目录项下标index2为目录项中的待删子目录的结点号boolfind(char*string)根据路径找到指定文件或目录く路径至少有一个‘/‘以root开头，不以‘/‘结尾》。需要注意的是,使用此函数时当前路径跟着改掉了，所以使用前必须保存当前路径。万ー找不到目标的话,可以还原为当前路径。定义了有关目录操作的四个功能函数,voidmkdir(char*dirname)当前目录下创建目录(规定目录文件只占ー个盘块。为了降低难度,已设定目录文件只占ー个盘块。voidrmdir(char*dirname,intindex)当前目录下删除目录。将要删除的目录可能非空。有两种策略:ー、规定只能删除空目录。二、递归地将非空目录的所有子目录删除，让后再删除自己。第一种实现较简单.，我使用了第二种策略。所以参数为(子目录名,当前结点)。如果使用第一种策略的话，参数为只要子目录名就可以了。voidIs(void)显示当前结点的所有子目录voidcd(char*string)改变当前目录。有四中处理过程:string为切换到当前目录;为切换到父目录;为“/”切换到根目录;如果为一路径的话，就调用boolfind(char*string)切换到指定目录。chsome.h：定义ー个底层函数：boolhavewpower(INODEinode)判断当前用户对指定的结点有无写权限定义四个功能函数：voidchmod(char*name)改变当前目录下指定文件的文件权限voidchown(char*name)改变当前目录下指定文件的文件拥有者(如拥有者在另ー个组,那么组也要改掉)voidchgrp(char*name)改变当前目录下指定文件的文件所属组voidchnam(char*name)改变当前目录下指定文件的文件名command,h:命令解析层函数模块。接受用户命令,执行不同的操作。实验结果如下:single文件系统管理:x-□shane@>shane-TW8-SW8-DW&/tmp/OSHelloThisisshaneFS.Youcan*************************FormatListCreateDeleteWriteRead*************************>?formatDiskFormatted [OK]*************************>?touchIlnPutthefilename:a.cTOC\o"1-5"\h\zCreateFile [OK]*************************>?lsa.c 0ListFiles [OK]*************************ko double文件管理x一口shane（9）shane-TW8-SW8-DW8:/tmp/OSshane@shane-TW8-SW8-DW8:/tmp/OS$./double_fsA***************'*****'***'*HelloThisisshaneFS.YoucanI*************************FormatListCreateDeleteWriteReadWelcome!PleaseInPutYourName:shaneshane>?touchInPutthefilename:a•cCreateFile [OK]*************************shane>?lsa.c 6ListFiles や[OK]I'*************************|shane>三、源程序main.cpp#include"head.h"#include"blockinodesuperblock.h'1#includeninitial.hK#include"userop.h**#include"file.h"#include"dir.h"#include“command.h"#includeMchsome.h"〃〃〃〃〃〃〃〃〃〃〃〃ル〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃voidmain()(control.open(Mcontrol.txtn,ios::inIios::outIios::nocreate);inti;control»i;control.close();if(i!=0)〃不为〇就初始化(initial();)control.open(ncontrol.txtn,ios::inIios::outIios::nocreate);control.seekp(O);control«0;〃默认是上次基础上继续下去不用再初始化control.close();strcpy(curname,"rooビ);〃当前目录文件名为rootroad[0]=0;〃当前目录路径(存放从根目录到这里的结点号)num=l;〃最后位road[num・l]为当前目录文件i结点号cout«M请登陆系统\n”;while(!login())〃登陆为止cout«"wrong!!!\n”；cout«"loginsuccessu«endl;cout«"******Welcomen«auser«n******0；readsuper();getcommand。ル命令解析函数writesuper();)2.blockinodesuperblock.h〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃ル〃〃〃〃〃〃〃〃〃〃intialloc()〃申请ー个i结点返回结点号否则返回(if(superblock.fiptr>0)(inttemp=superblock.fistack[80-superblock.fiptr];〃当冃U可用superblock.fistack[80-superblock.fiptr]=-1;superblock.fiptr—;returntemp;)return-1;)lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll〃〃〃〃〃〃〃〃〃〃〃〃ル〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃voidifree(intindex)〃指定一个结点号,回收ー个i结点(disk.open(ndisk.txtM,ios::inIios::outIios::nocreate);〃清空结点disk.seekp(514+64*index+2*(index/8));disk«setw(64)«,*;disk.close();for(inti=80・superblock.fiptr;iv80;i++)〃结点号找到合适位置插入空闲结点号栈(if(superblock.fistack[i]vindex)〃小于它的前移一位(superblock.fistack[i-1]=superblock.fistack[i];}else〃放在第一个大于它的结点号前面superblock.fistack[i-l]=index;break;superblock.fiptr++;)llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll/・成组链接法・/intballoc()〃申请ー个盘块返回盘块号否则返回-1(inttemp=superblock.fbstack[10-superblock.fbptr];if(superblock.fbptr==l)〃是栈底了=>是记录盘块了(〃是最后记录盘块最后号〇(保留作栈底分配不成功)if(temp==O){return-1;}superblock.fbstack[10-superblock.fbptr]="l;superblock.fbptr=0;〃盘块内容读入栈for(inti=0;i<10;i++){intid,num=O;disk.open(”disk・txr',ios::inIios::outIios::nocreate);〃先计算盘块内容个数num(最多10)最后盘块可能不到10个disk.seekg(514*temp);for(inti=0;i<10;i++)disk»id;num++;if(id==O)break;}disk.seekg(514*temp);〃盘块内容读入栈for(intj=10-num;j<lO;j-H-)(disk»id;superblock.fbstack[j]=id;superblock.fbptr=num;disk.close();disk.open(ndisk.txt'\ios::inIios::outIios::nocreate)ソ/清空回收盘块disk.seekp(514*temp);disk«setw(512)«,*;disk.close();〃盘块使用掉returntemp;)else//不是记录盘块==>盘块使用掉(superblock.fbstackf10-superblock.fbptr]=-l;superblock.fbptr—;returntemp;})IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIU〃〃〃〃〃〃〃〃〃ん〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃voidbfree(intindex)〃指定一个盘块号,回收ー个盘块{disk.open("disk.txtn,ios::inIios::outIios::nocreate);〃清空回收盘块disk.seekp(514*index);disk«setw(512)«,*;disk.close();if(superblock.fbptr==10)〃栈已满栈中内容记入回收盘块栈清空(disk.open(”disk.txピ,ios::inIios::outIios::nocreate);disk.seekp(514*index);for(inti=0;i<10;i++)(disk«setw(3)«superblock.fbstackfil;superblock.fbstackfil="l;)disk.close();superblock.fbptr=0;}〃回收盘短压栈superblock.fbstack[10-superblock.fbptr-1]=index;superblock.fbptr++;}IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIU〃〃〃〃〃〃〃ル〃〃〃〃〃〃/〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃/〃〃〃〃〃〃〃〃〃〃〃〃〃〃voidreadsuper()〃读超块到内存(disk.openCdisk.txt",ios::inIios::outIios::nocreate);inti;for(i=0;i<80;i++)〃读空闲结点号栈(disk»superblock.fistack[i];}disk»superblockfptr;〃空闲结点号栈指针for(i=0;i<!0;i++)〃读空闲盘块号栈(disk»superblock.fbstack[i];1disk»superblock.fbptr;〃空闲盘块号栈指针disk»superblock.inum;〃空闲结点号总数disk»superblock.bnum;〃空闲盘块号总数disk.close();)〃〃〃〃〃〃〃〃〃〃〃〃ル〃/〃〃〃〃〃〃〃/〃〃/〃〃〃〃〃〃/〃〃〃〃〃〃〃〃/〃〃〃/〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃ん〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃voidwritesuper。//内存写回超块1disk.open("disk.txt",ios::inIios::outIios::nocreate);inti;for(i=0;i<80;i++)〃写空闲结点号栈(disk«setw(3)«superb!ock.fistack[i];)disk«setw(3)«superblock.fiptr;〃空闲结点号栈指针for(i=0;i<!〇;i++)〃写空闲盘块号栈(disk«setw(3)«supe