OS实验指导书（蒋剑修改） - 图文(10)

for(j=0;jnext=NULL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf(\ return 0; }

/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/ int LFU(int total_pf) { int i,j,min,minpage; pfc_type *t; initialize(total_pf); for(i=0;ipl[j].counter&&pl[j].pfn!=INVALID) { min=pl[j].counter; minpage=j; } } freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; pl[minpage].counter=0; freepf_head->next=NULL;

44

}

} pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效 pl[page[i]].counter++; freepf_head=freepf_head->next; //减少一个free 页面 } else { pl[page[i]].counter; pl[page[i]].counter=pl[page[i]].counter+1; } }

printf(\return 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

45

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的还高。至于为什么，请探讨。

46

实验9 文件系统模拟程序设计

一、实验目的

加深对文件系统的内部功能及其实现的理解。 二、实验内容

用C语言设计一个简单的二级文件系统。要求做到以下几点： 1．可以实现下列几条命令（至少4条）： login 用户登录 dir 列文件目录 creat 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件

2．列目录时要列出文件名、物理地址、保护码和文件长度。 3．源文件可以进行读写保护。 三、实验指导

首先应确定文件系统的数据结构：主目录、子目录及活动文件等。主目录和子目录都以文件的形式存放于磁盘，这样便于查找和修改。用户创建的文件，可以编号存储于磁盘上。如file0，file1,file2...并以编号作为物理地址，在目录中进行登记。

1．设计思想

本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。对这些内容感兴趣的读者，可以在本系统的程序基础上进行扩充。

2．主要数据结构 (1) I节点 struct inode{

struct inode *i_forw; struct inode *i_back; char I_flag;

unsigned int i_into; /*磁盘i节点标号*/ unsigned int i_count; /*引用计数*/

unsigned short di_number; /*关联文件书，当为0时，则删除该文件*/ unsigned short di_mode; /*存取权限*/

unsigned short di_uid; /*磁盘i节点用户*/ unsigned short di_gid; /*磁盘i节点组*/ unsigned int di_addr[NADDR]; /*物理块号*/ }

(2) 磁盘i结点

47

struct dinode {

unsigned short di_number; /*关联文件数*/ unsigned short di_mode; /*存取权限*/ unsigned short di_uid; unsigned short di_gid;

unsigned long di_size; /*文件大小*/

unsigned int di_addr[NADDR]; /*物理块号*/ }

(3) 目录项结构 struct direct {

char d_name[DIRSIZ]; /*目录名*/ unsigned int d_ino; /*目录号*/ }

(4) 超级块 struct filsys {

unsigned short s_isize; /*i节点块块数*/ unsigned long s_fsize; /*数据块块数*/ unsigned int s_nfree; /*空闲块块数*/ unsigned short s_pfree; /*空闲块指针*/

unsigned int s_free[NICFREE]; /*空闲块堆栈*/

unsigned int s_ninode; /*空闲i节点数*/ unsigned short s_pinode; /*空闲i节点指针*/ unsigned int s_inode[NICINOD]; /*空闲i节点数组*/ unsigned int s_rinode; /*铭记i节点*/

char s_fmod; /*超级块修改标志*/ };

(5) 用户密码 struct pwd {

unsigned short P_uid; unsigned short P_gid; char passward[PWOSIZ]; }

(6) 目录 struct dir {

strut direct direct[DIRNUM]; int size; }

(7) 查找i内存节点的hash表

48