实验目的和要求
理解操作系统的文件系统组成以及基本原理，利用这些知识在内存中模拟一个FAT格式的文件系统，完成文件的创建和索引功能，实现以下命令接口：
（1）新建文件，格式：mkfile filename filecontent
filename：文件名
filecontent：文件内容(字符)
实现按FAT格式写FAT表和目录表，以及文件内容。
（2）列出文件，格式：dir
列出目录里所有的文件信息和虚拟磁盘信息。
（3）显示文件内容，格式：type filename
filename：文件名
在目录项中查找文件名所在块号，并把文件内容打印在屏幕上。
（4）删除文件：del filename
filename：文件名
将文件删除，回收虚拟磁盘空间。
（5）退出文件系统：quit
实验原理及内容
实验原理：
文件系统指文件存在的物理空间，Linux系统中每个分区都是一个文件系统，都有自己的目录层次结构。Linux会将这些分属不同分区的、单独的文件系统按一定的方式形成一个系统的总的目录层次结构。一个操作系统的运行离不开对文件的操作，因此必然要拥有并维护自己的文件系统。
Linux文件系统使用索引节点来记录文件信息，作用像windows的文件分配表。
索引节点是一个结构，它包含了一个文件的长度、创建及修改时间、权限、所属关系、磁盘中的位置等信息。一个文件系统维护了一个索引节点的数组，每个文件或目录都与索引节点数组中的唯一一个元素对应。系统给每个索引节点分配了一个号码，也就是该节点在数组中的索引号，称为索引节点号。
Linux文件系统将文件索引节点号和文件名同时保存在目录中。目录只是将文件的名称和它的索引节点号结合在一起的一张表，目录中每一对文件名称和索引节点号称为一个连接。
对于一个文件来说有唯一的索引节点号与之对应，对于一个索引节点号，却可以有多个文件名与之对应。因此，在磁盘上的同一个文件可以通过不同的路径去访问它。
本次实验将要采用的用例―FAT。作为一种文件名称，FAT（File Allocation Table，文件分配表）FAT中的每个表项都对应了磁盘中每一块的分配状况，FAT的表项位数决定了最大可表示的磁盘容量。FAT16表示最多支持216个块(或簇)。FAT表项的可能值为：
0x00：表示对应块空闲
0xFF：表示对应块为文件的最后一块
其它值：表示该文件的下一块的块号
文件目录里记录了文件的控制信息，每一个目录项(FCB)都对应一个文件，用户要操作文件时总是先查询目录找出FCB，然后才能读取文件内容。
简单文件系统示范：
（1）虚拟磁盘结构
#define MAX_DISK_SIZE 256
u_char g_disk[MAX_DISK_SIZE]
若定义每一个磁盘块大小为16字节，则系统最多存放16个磁盘块内容。
规定FAT表总占用第0块，使用8位的FAT表项，所以第0块共有16个FAT表项，目录表占用第1至4块，每个目录项(FCB)占16个字节，因此系统最多支持4个文件。由于0-5块被系统占用，FAT的第0~5字节应为0xFF，故系统最大支持量为10块。
（2）系统数据结构
typedef struct _tagfat {
u_char cluster;
} FAT,*PFAT,**PPFAT;
typedef struct _tagfcb {
char f_name[10];
int f_size;
int f_firstblock;
} FCB,*PFCB,**PPFCB;
（3）文件删除原理。删除一个文件时需要做两件事：
①把文件占用的块号对应的FAT项清0x00。例如被删除的文件占用了第7块物理块，那么要将FAT的第7字节置0x00(原本为0xFF)
②把目录表中的相应项中的文件名第一个字节置0xE5
由此看出，使用FAT的文件系统删除文件时并不清除文件占用的物理块内容，这也给反删除文件带来了可能。在目录项中，文件名的第一个字节很关键，如果是0xE5的话则说明该目录项空闲可以存放一个文件信息，否则说明已被占用。
1、给出核心算法的源代码，并加上详细注释；
#include#include #include //定义返回值 #define SUCCESS 1 #define DELETE_FAIL 0xE0 #define ALLOC_FAIL 0xE1 #ifndef _FILESYS #define _FILESYS //类型定义，下面即将用的一些类型可以直接用约简的形式替换 typedef unsigned short u_short; typedef unsigned short* pu_short; typedef unsigned char u_char; typedef unsigned char* pu_char; typedef unsigned int u_int; typedef unsigned int* pu_int; typedef char* pchar; typedef int* pint; typedef short* pshort; //文件控制块结构（20字节） typedef struct _tagfcb { char f_name[10]; //文件名 int f_size; //文件长度 int f_firstblock; //起始块号 }FCB, *PFCB, **PPFCB; typedef struct _tagfat { u_char cluster; }FAT, *PFAT, **PPFAT; typedef struct tagNode { int iValue; struct tagNode *pNext; }NODE, *PNODE; #define MAX_DISK_SIZE 1024 #define BLOCKSIZE 16 #define MAX_FAT 16 extern u_char g_disk[MAX_DISK_SIZE]; //模拟的磁盘空间 //获取指定块的首地址 void* getBlockAddr(int blockno); //虚拟磁盘初始化 void InitDisk(); //创建文件 int CreateFile(pchar f_name, pchar f_content, int f_size); //列出文件 int ListFile(); //显示文件 int displayFile(pchar filename); //删除文件 int initList(PNODE* pListHead); //创建一个头节点，iValue = 0 int insert(PNODE pListHead,int iValue); //插入一个值为iValue的节点至链表尾 int deleteList(PNODE pListHead); //删除一个指定头指针的链表空间 void printList(PNODE pListHead); //打印整个链表 #endif int initList(PNODE* pListHead) { //创建一个头结点空间，并赋值为0 if ((*pListHead = (PNODE)malloc(sizeof(NODE))) == NULL) { return ALLOC_FAIL; } (*pListHead)->iValue = 0; (*pListHead)->pNext = NULL; return SUCCESS; } //在指定的头结点的链表末尾插入一个新的结点 int insert(PNODE pListHead,int iValue) { PNODE pNode; PNODE pLastNode = pListHead; if ((pNode = (PNODE)malloc(sizeof(NODE))) == NULL) { return ALLOC_FAIL; } pNode->iValue = iValue; pNode->pNext = NULL; while(1) { if (pLastNode->pNext == NULL) { pLastNode->pNext = pNode; break; } pLastNode = pLastNode->pNext; } return SUCCESS; } //删除整个链表空间，程序结束必做 int deleteList(PNODE pListHead) { PNODE pReadyToDelete = pListHead; while(pListHead == NULL) { pListHead = pListHead->pNext; free(pReadyToDelete); pReadyToDelete = pListHead; } return SUCCESS; } void printList(PNODE pListHead) { PNODE pNode = pListHead; if (pNode->pNext == NULL) { printf("This linkerList has no NODE except Header!n"); return; } printf("HEAD->"); pNode = pNode->pNext; while(pNode != NULL) { printf("%d->",pNode->iValue); pNode = pNode->pNext; } printf("NULLn"); return; } u_char g_disk[MAX_DISK_SIZE];//用内存模拟的磁盘空间 const int g_freedisksize = MAX_DISK_SIZE; //虚拟磁盘的空闲空间 const char g_freeflag = (char)0xE5; void * getBlockAddr(int blockno) { return (g_disk + blockno * BLOCKSIZE); } //初始化虚拟磁盘空间 void InitDisk() { PFCB pFCB = NULL; int i, j; memset(g_disk,0,MAX_DISK_SIZE); for (i = 1 ; i <= 4 ; i++) //4个目录项置为空闲 { pFCB = (PFCB)getBlockAddr(i); pFCB->f_name[0] = g_freeflag; } for (j = 0 ; j <= 4 ; j++) //FAT表的前5字节置FF，表示已被占用 { ((PFAT)(g_disk+j))->cluster = (u_char)0xFF; } } int CreateFile(pchar f_name, pchar f_content, int f_size) { PFCB pFCB = NULL; //目录项（FCB）指针 PFAT pFAT = (PFAT)getBlockAddr(0); //FAT表的首地址 int blockcount = 0; for(int i=1;i <= 4;i++) { pFCB = (PFCB)getBlockAddr(i); if(pFCB->f_name[0] == g_freeflag) //有空闲的目录项 { blockcount = (f_size / BLOCKSIZE) + 1; //查找FAT，是否有足够的空闲块，使用一个链表记录要占用的空闲块号 int k = blockcount; PNODE pListHead,pNode; if(initList(&pListHead) != SUCCESS) { return 12; //list initialize errno } for (int j=5; j < MAX_FAT ; j++) { if(((PFAT)(pFAT + j))->cluster == (u_char)0) { insert(pListHead,j); if(--k == 0) break; } } printList(pListHead); if (k > 0) return 10; //file size error no //下面开始向块中写文件内容，同时更改目录项FCB的内容 strcpy(pFCB->f_name,f_name); //写文件名 pFCB->f_size = f_size; //写文件大小 pFCB->f_firstblock = pListHead->pNext->iValue; //文件起始块号 int remainbyte = f_size; //还剩多少字节没写进块 pNode = pListHead->pNext; for (k = 0 ; k < blockcount ; k++) { if (remainbyte <= BLOCKSIZE) //不足一个块 { memcpy(getBlockAddr(pNode->iValue), f_content + (BLOCKSIZE * k), remainbyte); } else { memcpy(getBlockAddr(pNode->iValue), f_content + (BLOCKSIZE * k), BLOCKSIZE); remainbyte -= BLOCKSIZE; } pNode = pNode->pNext; } //根据文件占用的空闲块号改FAT表 pNode = pListHead->pNext; while (1) { if (pNode->pNext == NULL) { ((PFAT)(pFAT + pNode->iValue))->cluster = (u_char)0xFF; break; } ((PFAT)(pFAT + pNode->iValue))->cluster = pNode->pNext->iValue; pNode = pNode->pNext; } //回收链表空间 deleteList(pListHead); return 0; } } return 11;//directory full error no } int ListFile() { PFCB pFCB = NULL; int filecount = 0; //文件记数 int bytecount = 0; //文件大小累计 printf("My file system list:n"); printf("----------------------------------------------n"); printf("filenamettt filesizen"); printf("----------------------------------------------n"); for (int i=1 ; i<=4 ; i++) { pFCB = (PFCB)getBlockAddr(i); if (pFCB->f_name[0] != g_freeflag) { //display file info filecount++; bytecount += pFCB->f_size; printf("%stttt %d Bytesn",pFCB->f_name,pFCB->f_size); } } if (filecount == 0) { printf("no file in this system now!n"); } printf("----------------------------------------------n"); printf("total files : %d t total bytes : %d Bytes nttt remain bytes : %d Bytesn", filecount,bytecount,g_freedisksize-bytecount); return filecount; } void printc(pchar filecontent,int size) { for(int i=0 ; i f_name,filename)) { remainbytes = pFCB->f_size; //根据FCB中的起始块号得到文件第一块所在地 //打印出第一块的内容 printc((pchar)getBlockAddr(pFCB->f_firstblock),BLOCKSIZE); remainbytes -= BLOCKSIZE; //再到FAT中去找该文件后续块的块号，直到FAT中显示FF说明文件结束 int firstblock = pFCB->f_firstblock; while ( ((PFAT)(pFAT+firstblock))->cluster != (u_char)0xFF ) { //说明该文件还有后续块，跟据这个指示打印后续块内容 printc((pchar)getBlockAddr(((PFAT)(pFAT+firstblock))->cluster),BLOCKSIZE); firstblock = ((PFAT)(pFAT+firstblock))->cluster; remainbytes -= BLOCKSIZE; } //打印最后一块 printc((pchar)getBlockAddr(((PFAT)(pFAT+firstblock))->cluster),remainbytes); printf("n"); return 0; //执行成功 } } return -1;//未找到 } int deleteFile(pchar filename) { PFCB pFCB = NULL; PFAT pFAT = (PFAT)getBlockAddr(0); for (int i=1 ; i<=4 ; i++) { pFCB = (PFCB)getBlockAddr(i); if (!strcmp(pFCB->f_name,filename)) { //将目录项FCB的文件名第一个字节置为E5即可 pFCB->f_name[0] = g_freeflag; //再将FAT中文件占用的块号置00 int firstblock = pFCB->f_firstblock; int nextblock = pFCB->f_firstblock; if (((PFAT)(pFAT+firstblock))->cluster == (u_char)0xFF) { //该文件仅占一块，将此项清0 ((PFAT)(pFAT+firstblock))->cluster = (u_char)0x00; } else //说明该文件占有了若干块，将这些FAT块指示都清0 { while ( ((PFAT)(pFAT+nextblock))->cluster != (u_char)0xFF ) { nextblock = ((PFAT)(pFAT+firstblock))->cluster; ((PFAT)(pFAT+firstblock))->cluster = (u_char)0x00; firstblock = nextblock; } //将文件最后一块回收 ((PFAT)(pFAT+nextblock))->cluster = (u_char)0x00; } printf("file deleted!n"); return 0; //执行成功 } } return -1;//未找到 } int main() { InitDisk(); //初始化虚拟磁盘空间 char filename[10]; char filecontent[176];//文件内容不能超过176 B char command[10]; int filesize = 0; int err_no = 0; printf("--------------------------------Tips--------------------------------n"); printf(" The commonds of filesystemn"); printf(" 创建文件：mkfilen"); printf(" 文件目录：dirn"); printf(" 显示内容：typen"); printf(" 删除文件：deln"); printf(" 退出系统：quitn"); printf("---------------------------------------------------------------------n"); while(1) { printf("filesys>"); //命令提示行 scanf("%s",command); if (!strcmp(command,"mkfile")) //创建文件命令，需要用户提供文件名 { printf("ninput file name(<10 chars):"); scanf("%s",filename); printf("nReady to create file. Please input file content end with ENTER:n"); scanf("%s",filecontent); filesize = strlen(filecontent); if((err_no = CreateFile(filename,filecontent,filesize)) == 0) { printf("File created ! n"); } else { printf("Create failed! err_no=%dn",err_no); } } else if (!strcmp(command,"dir")) //列目录命令 { printf("The stored files are:n"); ListFile(); } else if(!strcmp(command,"type")) //显示文件内容命令 { printf("Please enter the file you want to view:n"); scanf("%s",filename); if (displayFile(filename) != 0 ) printf("can't find the file you given!n"); } else if(!strcmp(command,"del")) //删除文件命令 { printf("Please enter the file you want to delete:n"); scanf("%s",filename); if (deleteFile(filename) != 0 ) printf("can't find the file you given!n"); } else if (!strcmp(command,"quit")) //退出本系统命令 { break; } else { printf("Unknown command!n"); } } return 0; }
2、给出测试数据及运行结果、实验相关结论等。
运行文件模拟系统程序，显示出几大常用选项，即文件的创建、目录显示、内容显示、删除文件和退出系统的操作命令。
1.文件的创建：输入mkfile命令，此时系统将提示里输入文件名和文件内容，然后便创建了一个test文件并向里面输入内容：hello，同时将这个文件写入磁盘。
2.显示目录：输入dir命令，文件系统显示了相应的模拟的磁盘中的目录，可以看到相应的存储在磁盘中的文件信息。
3.显示内容：输入type命令，提示输入想要查看的文件名字，可以看到输入test可以显示出test文件中存储的内容为hello。
4.删除文件：输入del命令，提示想要删除的文件名字，如果输入test文件名，那么就可以删除文件模拟系统中的test文件，可以看到再次输入dir命令查看文件系统中的文件已经没有文件存在了。
整个文件模拟系统的主要功能如上述所述，使用完之后可以通过quit命令退出系统。
