链接文件系统的设计与实现

1、OS课程设计.链接文件系统的设计与实现操作系统课程设计报告课 题： 链接文件系统的设计与实现 班 级： 计科1002 学 号： 101304219 姓 名： 宋震宇 指导老师： 邹姝稚 成 绩： 2013.1.16目录一、课题设计目的1二、课题任务描述1三、课题研发相关知识1四、课题设计3 五、源程序·························

2、;·····6 六、运行与测试15 七、心得体会16一、课题设计目的1.课题设计背景 文件系统是现代OS用来存储和管理信息的机构，其涉及到磁盘空间管理、文件存储结构和用户接口等诸多技术机制。本课题在位示图的磁盘空间管理方式下，模拟实现文件的显示连接存储，并在此基础上实现文件的读写等操作方法。2.课题设计目的 通过本课题，深入理解文件物理结构与存取方法之间的关系,掌握磁盘空间管理与文件分配过程间的联系，从而更好地掌握文件系统概念。二、课题任务描述1.磁盘文件的管理采用显式链接结构，将文件占用的物理块号和链接指针记录在一张文件分配表（FAT）中。文

3、件第一块的块号记录在索引结点中。文件目录只记录文件名和索引结点的编号。索引结点的结构如下：索引结点编号文件属性创建时间文件第一块块号文件占用盘块数备用2.假定磁盘存储空间共有100个物理块用于存放数据，目录文件盒索引结点可直接访问，不存放在这100个块中。3.一个物理块可存放3个文件逻辑记录，并且假设文件逻辑记录定长。4.要求用键盘输入的方式模拟用户读写请求，输入格式如下：Create (filename)Write (filename,text,logical_record_no)Read (filename,logical_record_no)其中filename是要读写的文件名，text

4、是写入的内容，logical_record_no是逻辑记录号。Create、Write、Read分别表示创建一个文件，向文件的某个逻辑记录写，从文件的某个逻辑记录读。5.文件存储空间管理采用位示图（位示图为7行，16列）的方式。6.设计和实现文件存储空间的分配，并完成用户的读写请求。三、课题研发相关知识1.文件系统 在现代计算机系统中，要用到大量的程序和数据，因内存容量有限，且不能长期保存，故而平时总是把它们以文件的形式存放在外存中，需要时再随时将它们调入内存。如果由用户直接管理外存上的文件，不仅要求用户熟悉外存特性，了解各种文件的属性，以及它们在外存上的位置，而且在多用户环境下，还必须能保持

5、数据的安全性和一致性。显然，这是用户所不能胜任、也不愿意承担的工作。于是，取而代之的便是在操作系统中又增加了文件管理功能，即构成一个文件系统，负责管理在外存上的文件，并把对文件的存取、共享和保护等手段提供给用户。这不仅方便了用户，保证了文件的安全性，还可有效地提高系统资源的利用率。2.链接分配 在采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。由于链接分配是采取离散分配方式，消除了外部碎片，故而显著地提高了外存空间的利用率；又因为是根据文件的当前需要，为它分配必需的盘块，当文件动态增长时，可动态地再为它分配盘块

6、，故而无需事先知道文件的大小。此外，对文件的增、删、改也十分方便。链接方式又可分为隐式链接和显式链接两种形式。3.显式链接 这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把

7、该表称为文件分配表FAT(File Allocation Table)。4.位示图 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。（它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。）磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用m*n个位数来构成位示图，并使m*n等于磁盘的总块数。5.索引结点 在检索目录文件的过程中只用到了文件名，仅当找到一个目录项时，才需从该目录项中读出该文件的物理地

8、址。而其他一些对该文件进行描述的信息，在检索目录时一概不用。显然，这些信息在检索目录时不需调入内存。为此有的系统便采用了把文件名与文件描述信息分开的方法，亦即，使文件描述信息单独形成一个称为索引结点的数据结构，简称i结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针所构成。6.库函数介绍 该程序所用的库函数为#include<stdio.h>、#include<string.h>、#include<stdlib.h>、#include<iostream.h>等。1）在使用标准函数库中的输入输出函数时，编译系统要求程序提供有关

9、的信息（例如对这些输入输出函数的声明），#include<stdio.h>的作用就是用来提供这些信息的，stdio.h是C编译系统提供的一个文件名，stdio是“standard input & output”的缩写，即有关标准输入输出的信息。在程序中用到系统提供的标准函数库中的输入输出函数时，应在程序的开头写上一行：#include"stdio.h"或者是#include<stdio.h>,这样才能调用库函数。2）#include<string.h>用于字符串处理3）stdlib 头文件即standard library标准库头

10、文件。stdlib 头文件里包含了C、C+语言的最常用的系统函数。该文件包含了的C语言标准库函数的定义。stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。4）iostream.h是input output stream的简写，意思为标

11、准的输入输出流头文件。它包含：cin>>"要输入的内容"和cout<<"要输出的内容"。这两个输入输出的方法需要#include<iostream.h>来声明头文件。四、课题设计1.总体结构： 文件管理读文件写文件关闭文件创建文件打开文件删除文件2.数据结构：1）文件及其类别 文件是由大量性质相同的记录组成的集合。可按其记录的类型不同分为两类：操作系统的文件和数据库文件。操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。它也是记录的集合，这个记录仅是一个字符组，用户为了存取、加工方便，把文件中的信息划分成若干组

12、，每一组信息称为一个逻辑记录，且可按顺序编号。数据库中的文件时带有结构的记录的集合；这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。2）记录的逻辑结构和物理结构 记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的而表示和存取方式。物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织。用户的读/写一个记录是指逻辑记录，查找对应的物理记录则是操作系统的职责。3）文件的物理结构 文件在存储介质（磁盘或磁带）上的组织方式称为文件的物理结构。文件可以有各种各样的组织方式，其基本方式有3种：顺序组织、随机组织和链组织。3.主要功能流程图：创建文件创

13、建文件：重名否是创建成功退出删除文件删除文件：否在当前目录是退出是否打开状态删除成功退出打开文件打开文件：是否文件存在目录文件属性退出不可打开打开成功关闭文件关闭文件：是否文件打开退出关闭成功写文件写文件：是否写入字节<=文件剩余空间写入一部分，再寻找空闲盘块继续写入操作写入成功读文件读文件：否是读出字节<=实际文件空间根据所占磁盘块号和文件起始位置继续读操作读成功五、源程序#include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream.h>#define

14、DIR_LENGTH 1024 #define MAX_WRITE 1024*128 #define MEM_D_SIZE 1024*1024 #define DISKSIZE 1024 #define MSD 5 #define DISK_NUM MEM_D_SIZE/DISKSIZE #define FATSIZE DISK_NUM*sizeof(struct fatitem) #define MOFN 5 #define ROOT_DISK_NO FATSIZE/DISKSIZE+1 #define ROOT_DISK_SIZE sizeof(struct direct) struct

15、fatitem int item; /*FAT表项结构*/ char em_disk; ;struct direct struct FCB /*目录项结构*/char name9; char property; int size; int firstdisk;int next; int sign; directitemMSD+2;struct opentable struct openttableitem /*文件打开表项结构*/char name9; int firstdisk; int size; openitemMOFN;int cur_size; ;struct fatitem *fa

16、t; /*FAT表*/struct direct *root; /*根目录*/struct direct *cur_dir; /*当前目录*/struct opentable u_opentable; /*文件打开表*/int fd=-1; /*文件打开表的序号*/char *bufferdir; /*记录当前路径的名称*/char *fdisk; /*虚拟磁盘起始地址*/void initfile(); void format();void enter(); void halt();int create(char *name); int open(char *name);int close(

17、char *name); int write(int fd,char *buf,int len);int read(int fd,char *buf); int del(char *name);void print(); void show();/*-初始化文件系统-*/void initfile()fdisk = (char *)malloc(MEM_D_SIZE*sizeof(char); /*申请空间*/format(); free(fdisk);void format()int i;/*格式化*/ FILE *fp;fat = (struct fatitem *)(fdisk+DISK

18、SIZE); /*计算FAT表地址*/fat0.item=-1; fat0.em_disk='1'for(i=1;i<ROOT_DISK_NO-1;i+) /*存放 FAT表的磁盘块号*/ fati.item=i+1; fati.em_disk='1' fatROOT_DISK_NO-1.item=-1; fatROOT_DISK_NO-1.em_disk='1'fatROOT_DISK_NO.item=-1; fatROOT_DISK_NO.em_disk='1'for(i=ROOT_DISK_NO+1;i<DISK

19、_NUM;i+)fati.item = -1;fati.em_disk = '0' root = (struct direct *)(fdisk+DISKSIZE+FATSIZE); /*根目录的地址*/root->directitem0.sign = 1;/*指向当前目录的目录项*/ root->directitem0.firstdisk = ROOT_DISK_NO;strcpy(root->,".");root->directitem0.next = root->directitem0.fi

20、rstdisk;root->perty = '1'root->directitem0.size = ROOT_DISK_SIZE;root->directitem1.sign = 1;/*指向上一级目录的目录项*/root->directitem1.firstdisk = ROOT_DISK_NO;strcpy(root->,".");root->directitem1.next = root->directitem0.firstdisk;root->

21、;perty = '1'root->directitem1.size = ROOT_DISK_SIZE;for(i=2;i<MSD+2;i+) root->directitemi.sign = 0;root->directitemi.firstdisk = -1; strcpy(root->,"");root->directitemi.next = -1; root->perty = '0'root->d

22、irectitemi.size = 0; if(fp = fopen("disk.dat","wb")=NULL)printf("Error:n Cannot open file n");return;if(fwrite(fdisk,MEM_D_SIZE,1,fp)!=1) /*虚拟磁盘空间保存到磁盘文件中*/ printf("Error:n File write error! n"); fclose(fp);void enter()FILE *fp; /*进入文件系统*/int i; fdisk = (char

23、*)malloc(MEM_D_SIZE*sizeof(char); /*申请空间*/if(fp=fopen("disk.dat","rb")=NULL)printf("Error:nCannot open filen");return; if(!fread(fdisk,MEM_D_SIZE,1,fp) /*把disk.dat 读入虚拟磁盘空间*/ printf("Error:nCannot read filen"); exit(0); fat = (struct fatitem *)(fdisk+DISKSIZE)

24、; /*找到FAT表地址*/root = (struct direct *)(fdisk+DISKSIZE+FATSIZE);/*找到根目录地址*/fclose(fp);for(i=0;i<MOFN;i+)/*初始化用户打开表*/ strcpy(u_,"");u_opentable.openitemi.firstdisk = -1;u_opentable.openitemi.size = 0; u_opentable.cur_size = 0; cur_dir = root; void exit()/*退出文件系统*/F

25、ILE *fp; int i;if(fp=fopen("disk.dat","wb")=NULL)printf("Error:nCannot open filen");return; if(!fwrite(fdisk,MEM_D_SIZE,1,fp) /*把虚拟磁盘空间内容读入disk.dat */ printf("Error:nFile write error!n");fclose(fp); free(fdisk); /free(bufferdir);for(i=0;i<MOFN;i+) /*撤销用户打开表

26、 */ strcpy(u_,"");u_opentable.openitemi.firstdisk = 0; u_opentable.openitemi.size = 0; u_opentable.cur_size = 0; /*用户打开文件数清零*/ return;int create(char *name) int i,j;/*创建文件*/if(strlen(name)>8) return(-1);for(i=2;i<MSD+2;i+) /*找到第一个空闲子目录*/ if(cur_dir->directi

27、temi.firstdisk=-1) break; for(j=2;j<MSD+2;j+) /*检查创建文件是否与已存在的文件重名*/ if(!strcmp(cur_dir->,name) break; if(i>=MSD+2) /*无空目录项*/ return(-2); if(u_opentable.cur_size>=MOFN) /*打开文件太多*/ return(-3); if(j<MSD+2) /*文件已经存在*/ return(-4);for(j=ROOT_DISK_NO+1;j<DISK_NUM;j+) /*找到空

28、闲盘块 j 后退出*/ if(fatj.em_disk='0') break;if(j>=DISK_NUM) return(-5); fatj.em_disk = '1' /*将空闲块置为已经分配*/ strcpy(cur_dir->,name); cur_dir->directitemi.firstdisk = j; cur_dir->directitemi.size = 0; cur_dir->directitemi.next = j; cur_dir->per

29、ty = '0' /*cur_dir->directitemi.sign 丢失*/ fd = open(name); /*打开所创建的文件*/ return 0;int open(char *name)int i, j;/*打开文件*/for(i=2;i<MSD+2;i+) /*文件是否存在*/ if(!strcmp(cur_dir->,name) break; if(i>=MSD+2) /*文件不存在*/ return(-1);/*-是文件还是目录-*/ if(cur_dir->per

30、ty='1') return(-4); for(j=0;j<MOFN;j+) /*文件是否打开*/if(!strcmp(u_,name) break; if(j<MOFN) /*文件已经打开*/ return(-2); if(u_opentable.cur_size>=MOFN) /*文件打开太多*/ return(-3); for(j=0;j<MOFN;j+)/*查找一个空闲用户打开表项*/ if(u_opentable.openitemj.firstdisk=-1) break; u_opentable

31、.openitemj.firstdisk = cur_dir->directitemi.firstdisk; strcpy(u_,name); u_opentable.openitemj.size = cur_dir->directitemi.size; u_opentable.cur_size+; return(j);/*返回用户打开表表项的序号*/int close(char *name)/*关闭文件*/ int i;for(i=0;i<MOFN;i+)if(!strcmp(u_opentable.openitemi.nam

32、e,name)break; if(i>=MOFN) /*-文件没有打开-*/ return(-1); strcpy(u_,"");/*清空该文件用户打开表项内容*/ u_opentable.openitemi.firstdisk = -1; u_opentable.openitemi.size = 0; u_opentable.cur_size-; fd = -1; /*文件打开表的序号为 -1 */ return 0;int write(int fd, char *buf, int len)/*写文件*/char *f

33、irst;int item, i, j, k; int ilen1, ilen2, modlen, temp;char Space = 32; /*SPACE的ASCII码值*/ char Endter= 'n'for(i=0;i<len;i+)if(bufi = '$') /*用 $ 字符作为空格*/bufi = Space;else if(bufi = '#') bufi = Endter; item=u_opentable.openitemfd.firstdisk;for(i=2;i<MSD+2;i+)if(cur_dir-&g

34、t;directitemi.firstdisk=item) break;temp = i; while(fatitem.item!=-1) item =fatitem.item; /*查找该文件的下一盘块*/first = fdisk+item*DISKSIZE+u_opentable.openitemfd.size%DISKSIZE;if(DISKSIZE-u_opentable.openitemfd.size%DISKSIZE>len)strcpy(first,buf);u_opentable.openitemfd.size = u_opentable.openitemfd.size

35、+len;cur_dir->directitemtemp.size = cur_dir->directitemtemp.size+len;elsefor(i=0;i<(DISKSIZE-u_opentable.openitemfd.size%DISKSIZE);i+) firsti = buf i;ilen1 = len-(DISKSIZE-u_opentable.openitemfd.size%DISKSIZE);ilen2 = ilen1/DISKSIZE; modlen = ilen1%DISKSIZE;if(modlen>0) ilen2 = ilen2+1;

36、/*-还需要多少块磁盘块-*/for(j=0;j<ilen2;j+)for(i=ROOT_DISK_NO+1;i<DISK_NUM;i+) if(fati.em_disk='0') break;if(i>=DISK_NUM) /*如果磁盘块已经分配完了*/ return(-1);first = fdisk+i*DISKSIZE; /*找到的那块空闲磁盘块的起始地址*/if(j=ilen2-1) /*如果是最后要分配的一块*/for(k=0;k<len-(DISKSIZE-u_opentable.openitemfd.size%DISKSIZE)-j*DI

37、SKSIZE;k+)firstk = bufk;elsefor(k=0;k<DISKSIZE;k+) firstk =bufk;fatitem.item = i; /找到一块后将它的序号存放在上一块的指针中fati.em_disk = '1' /*-置找到的磁盘快的空闲标志位为已分配-*/fati.item = -1; /*-它的指针为 -1 (即没有下一块)-*/u_opentable.openitemfd.size = u_opentable.openitemfd.size+len;cur_dir->directitemtemp.size = cur_dir-&

38、gt;directitemtemp.size+len;return 0;int read(int fd, char *buf)/*读文件*/int len = u_opentable.openitemfd.size;char *first; int i, j, item;int ilen1, modlen; item = u_opentable.openitemfd.firstdisk;if(len>u_opentable.openitemfd.size) return(-1);ilen1 = len/DISKSIZE; modlen = len%DISKSIZE;if(modlen!=

39、0) ilen1 = ilen1+1; /*-计算文件所占磁盘的块数-*/first = fdisk+item*DISKSIZE; /*-计算文件的起始位置-*/for(i=0;i<ilen1;i+)if(i=ilen1-1) /*-如果在最后一个磁盘块-*/ for(j=0;j<len-i*DISKSIZE;j+) bufi*DISKSIZE+j = firstj;else for(j=0;j<len-i*DISKSIZE;j+) bufi*DISKSIZE+j = firstj;item = fatitem.item; /*-查找下一盘块-*/first = fdisk+

40、item*DISKSIZE; return 0;int del(char *name)/*删除文件*/int i,cur_item,item,temp;for(i=2;i<MSD+2;i+) /*-查找要删除文件是否在当前目录中-*/if(!strcmp(cur_dir->,name) break;cur_item = i; /*-用来保存目录项的序号,供释放目录中-*/if(i>=MSD+2) /*-如果不在当前目录中-*/ return(-1);if(cur_dir->directitemcur_perty!='

41、;0') /*-如果删除的不是目录-*/return(-3);for(i=0;i<MOFN;i+) /*-如果文件打开,则不能删除,退出-*/if(!strcmp(u_,name) return(-2);item = cur_dir->directitemcur_item.firstdisk;/*-该文件的起始盘块号-*/while(item!=-1) /*-释放空间,将FAT表对应项进行修改-*/temp = fatitem.item; fatitem.item = -1;fatitem.em_disk = '0&#

42、39; item = temp;cur_dir->directitemcur_item.sign = 0;/*释放目录项*/cur_dir->directitemcur_item.firstdisk = -1;strcpy(u_opentable.openitemcur_,""); cur_dir->directitemcur_item.next = -1; cur_dir->directitemcur_perty = '0'cur_dir->directitemcur_item.size =

43、0; return 0;void show()/*显示当前路径*/printf("n操作码:n");void print()/*输出提示信息*/printf("*n");printf("*tt 欢迎使用本系统! *n");printf("*n");printf("*tt 1.创建文件 create 文件名 *n");printf("*tt 2.删除文件 delete 文件名 *n");printf("*tt 3.打开文件 open 文件名 *n");pri

44、ntf("*tt 4.关闭文件 close 文件名 *n");printf("*tt 5.写文件 write *n");printf("*tt 6.读文件 read *n");printf("*tt 0.退出系统 exit *n");printf("*n");printf("请输入您的操作码:");void main()/*主函数*/FILE *fp;char ch; char a100;char code1110; char name10;int i,flag; char

45、*contect;contect = (char *)malloc(MAX_WRITE*sizeof(char);if(fp=fopen("disk.dat","rb")=NULL)printf("您还未初始化，是否进行初始化?(y/n)");scanf("%c",&ch);if(ch='y'|ch='Y')initfile(); printf("初始化成功! n");else return;enter(); print(); show();strcpy(

46、code0,"exit");/*将命令全部保存在CODE数组中*/strcpy(code1,"create"); strcpy(code2,"open");strcpy(code3,"close"); strcpy(code4,"write");strcpy(code5,"read"); strcpy(code6,"delete");while(1)scanf("%s",a);for(i=0;i<11;i+)if(!strcmp(

47、codei,a) break;switch(i)case 0: /*退出文件系统*/free(contect); exit(); return;case 1: /*创建文件*/scanf("%s",name); flag = create(name);if(flag=-1)printf("Error: n The length is too long !n");else if(flag=-2)printf("Error: n The direct item is already full !n");else if(flag=-3)pr

48、intf("Error: n The number of openfile is too much !n");else if(flag=-4)printf("Error: n The name is already in the direct !n");else if(flag=-5)printf("Error: n The disk space is full!n");elseprintf("Successfully create a file! n");show(); break;case 2:/*打开文件*/

49、scanf("%s",name); fd = open(name);if(fd = -1)printf("Error: n The open file does not exist! n");else if(fd = -2)printf("Error: n The file have already opened! n");else if(fd = -3)printf("Error: n The number of file is too much! n");else if(fd = -4)printf("Error: n It is a direct,can not open for read or write! n");elseprintf("Successfully opened! n");show(); break;case 3:/*关闭文件*/scanf("%s",