一、实验简介
本实验要求在模拟的I/O系统之上开发一个简单的文件系统。用户通过create, open, read等命令与文件系统交互。文件系统把磁盘视为顺序编号的逻辑块序列,逻辑块的编号为0至L − 1。I/O系统利用内存中的数组模拟磁盘。
二、I/O系统
实际物理磁盘的结构是多维的:有柱面、磁头、扇区等概念。I/O系统的任务是隐藏磁盘的结构细节,把磁盘以逻辑块的面目呈现给文件系统。逻辑块顺序编号,编号取值范围为0至L−1,其中L表示磁盘的存储块总数。实验中,我们可以利用数组ldisk[C][H][B]
构建磁盘模型,其中CHB 分别表示柱面号,磁头号和扇区号。每个扇区大小为512字节。I/O系统从文件系统接收命令,根据命令指定的逻辑块号把磁盘块的内容读入命令指定的内存区域,或者把命令指定的内存区域内容写入磁盘块。文件系统和I/O系统之间的接口由如下两个函数定义:
-
read_block(int i, char *p);
该函数把逻辑块i的内容读入到指针p指向的内存位置,拷贝的字符个数为存储块的长度B。 -
write block(int i, char *p);
该函数把指针p指向的内容写入逻辑块i,拷贝的字符个数为存储块的长度B。
此外,为了方便测试,我们还需要实现另外两个函数:一个用来把数组ldisk 存储到文件;另一个用来把文件内容恢复到数组。
-
int backup_disk(FILE *filepath);
该函数将内存中现有的ldisk[C][H][B]
保存到文件句柄FILE *filepath
对应的二进制文件中。 -
int restore_disk(FILE *filepath);
该函数将从二进制文件句柄FILE *filepath
中读取硬盘数据,并存储到内存数组ldisk[C][H][B]
中。
在IO系统中,我们的文件结构组成为:
-
iosystem.h
用来声明全局变量与函数接口。 -
iosystem.c
用来定义函数与实现变量。
在iosystem.h
中:
#define C 80
#define H 2
#define B 18
定义了我们物理硬盘的柱面号,磁头号和扇区号的最大值。
unsigned char *ldisk[C][H][B];
int init_ldisk();
int read_block(int i,unsigned char *p);
int write_block(int i,unsigned char *p);
int backup_disk(FILE *filepath);
int restore_disk(FILE *filepath);
声明了我们IO系统对外的接口与物理硬盘ldisk的数组结构。
unsigned char *ldisk[C][H][B]
是一个unsigned char
类型的指针数组。
在iosystem.c
中,我们查看相关函数的实现:
int init_ldisk()
{
for(int i=0;i<C;i++)
{
for(int j=0;j<H;j++)
{
for(int k=0;k<B;k++)
{
ldisk[i][j][k]=(unsigned char *)malloc(sizeof(unsigned char)*512);
}
}
}
printf("IO INFO,logic disk init successfuly.\n");
return 0;
}
这是初始化物理硬盘的函数,通过一个三重循环来对指针数组申请内存空间,根据题意,每个扇区我们申请了512B的大小。
int read_block(int i,unsigned char *p)
{
if (i >= C*H*B)
{
printf("IO ERROR,index out of range!\n");
return -1;
}
int CylinderIndex=i/(H*B);
int SectorIndex=i%B+1;
int HeadsIndex=(i/18)%2;
memcpy(p,ldisk[CylinderIndex][HeadsIndex][SectorIndex-1],512);
printf("IO INFO,read logic index is %d,physic index is %d,%d,%d,the content is %s.\n",i,CylinderIndex,HeadsIndex,SectorIndex,ldisk[CylinderIndex][HeadsIndex][SectorIndex-1]);
return 0;
}
这是读取逻辑块的函数,其参数int i,unsigned char *p
分别为需要读取的逻辑块号与返回结果的指针。在函数体中,我们通过模运算与取整运算将逻辑块号转化为物理三维块号,并使用memcpy()
函数将对应内存空间的数据拷贝给返回指针p。
int write_block(int i,unsigned char *p)
{
if (i >= C*H*B)
{
printf("IO ERROR,index out of range!\n");
return -1;
}
int CylinderIndex=i/(H*B);
int SectorIndex=i%B+1;
int HeadsIndex=(i/18)%2;
memcpy(ldisk[CylinderIndex][HeadsIndex][SectorIndex-1],p,512);
printf("IO INFO,write logic index is %d,physic index is %d,%d,%d,the content is %s.\n",i,CylinderIndex,HeadsIndex,SectorIndex,p);
return 0;
}
这是写入逻辑块的函数,其参数int i,unsigned char *p
分别为需要写入的逻辑块号与输入数据的指针。在函数体中,我们通过模运算与取整运算将逻辑块号转化为物理三维块号,并使用memcpy()
函数将对应指针的数据拷贝给对应内存空间的指针。
int backup_disk(FILE *filepath)
{
if(filepath==NULL)
{
printf("IO ERROR,filepath open fail");
return -1;
}
for(int i=0;i<C;i++)
{
for(int j=0;j<H;j++)
{
for(int k=0;k<B;k++)
{
fwrite(ldisk[i][j][k],sizeof(unsigned char),512,filepath);
}
}
}
fclose(filepath);
printf("IO INFO,backup successfuly.\n");
return 0;
}
根据实验要求,我设计了备份函数,可以将虚拟在内存中的物理硬盘数据空间保存为文件,文件的储存方式为二进制储存,这样方便我们在恢复的时候直接读取。
int restore_disk(FILE *filepath)
{
if(filepath==NULL)
{
printf("IO ERROR,filepath open fail");
return -1;
}
for(int i=0;i<C;i++)
{
for(int j=0;j<H;j++)
{
for(int k=0;k<B;k++)
{
fread(ldisk[i][j][k],sizeof(unsigned char),512,filepath);
}
}
}
fclose(filepath);
printf("IO INFO,restore backup successfuly.\n");
return 0;
}
根据实验要求,我设计了恢复备份函数,可以读取硬盘中的二进制文件,并将其恢复到我们虚拟的内存硬盘空间之中。
三、文件系统
文件系统位于I/O系统之上。
文件系统的组织结构如下:
-
filesystem.h
用来声明全局变量与函数接口。 -
filesystem.c
用来定义函数与实现变量。
typedef struct
{
int fileSize;
int blockList[3];
}fileDescriptorItem;
我们定义了名为fileDescriptorItem
的文件描述符结构体类型,其中fileSize
为文件大小,blockList[3]
为这个文件所分配的逻辑块号,最多每个文件可分配3块。
typedef struct
{
unsigned char fileName[28];
int fileDescriptorIndex;
}dictionaryItem;
我们定义了名为dictionaryItem
的目录结构体类型,其中fileName
为文件名称,fileDescriptorIndex
为这个文件所分配的文件描述符的序号,最多每个文件名最长为28字节。
fileDescriptorItem *fileDescriptor[7];
unsigned char *bitMap;
dictionaryItem *dictionary;
在这里,我们定义了三个指针,分别为文件描述符指针数组、位图指针、目录指针,其中文件描述符指针数组大小为7。
int init()
{
printf("\nFILE INFO,file system will init.\n");
init_ldisk();
bitMap=(unsigned char*)calloc(512,sizeof(unsigned char));
for(int i=0;i<512;i++)
{bitMap[i]=0;}
bitMap[0]=0xff;
write_block(0,bitMap);
for(int i=0;i<7;i++)
{
fileDescriptor[i]=(fileDescriptorItem*)calloc(sizeof(unsigned char)*512/sizeof(fileDescriptorItem),sizeof(fileDescriptorItem));
write_block(i+1,(unsigned char*)fileDescriptor[i]);
}
printf("FILE INFO,file system init finished.\n");
return 0;
}
在这个函数中,我们对位图、文件描述符进行了初始化,对指针分配了内存空间,并将所有更改写入到硬盘之中。
int bitMapUpdate(int flag,int index)
{
printf("\nFILE INFO,bitmap is updating.\n");
read_block(0,bitMap);
int temp=index%8;
if(flag==1){
switch(temp)
{
case 0:bitMap[index/8]=bitMap[index/8]|0x80;break;
case 1:bitMap[index/8]=bitMap[index/8]|0x40;break;
case 2:bitMap[index/8]=bitMap[index/8]|0x20;break;
case 3:bitMap[index/8]=bitMap[index/8]|0x10;break;
case 4:bitMap[index/8]=bitMap[index/8]|0x08;break;
case 5:bitMap[index/8]=bitMap[index/8]|0x04;break;
case 6:bitMap[index/8]=bitMap[index/8]|0x02;break;
case 7:bitMap[index/8]=bitMap[index/8]|0x01;break;
}}
else if(flag==0)
{
switch(temp)
{
case 0:bitMap[index/8]=bitMap[index/8]&0x7f;break;
case 1:bitMap[index/8]=bitMap[index/8]&0xbf;break;
case 2:bitMap[index/8]=bitMap[index/8]&0xdf;break;
case 3:bitMap[index/8]=bitMap[index/8]&0xef;break;
case 4:bitMap[index/8]=bitMap[index/8]&0xf7;break;
case 5:bitMap[index/8]=bitMap[index/8]&0xfb;break;
case 6:bitMap[index/8]=bitMap[index/8]&0xfd;break;
case 7:bitMap[index/8]=bitMap[index/8]&0xfe;break;
}
}
write_block(0,bitMap);
printf("FILE INFO,bitmap updated.\n");
}
这个函数是对位图进行更新操作的函数,参数int flag,int index
分别是指将位图修改为0 or 1 与修改的位图序号。在函数体中,我们先读取了硬盘中对应块号的位图,另外,由于C语言中没有对二进制的直接修改操作,所以在这里我们使用位运算来代替,比如我们举例如下:
位图中一个字节
10010011
现在我们希望将其最后一位1修改为0
我们只需要将10010011
与11111110
进行按位与&
操作,这样我们就可以得到正确结果。
两个switch-case
语句分别对应了修改为0
或1
的情况下的位运算类型。
int findFreeBitMap()
{
printf("\nFILE INFO,is finding free bitmap.\n");
read_block(0,bitMap);
for(int i=0;i<512;i++)
{
printf("%d",bitMap[i]);
if(bitMap[i]!=0xff)
{
for(int j=0;j<8;j++)
{
int a=bitMap[i];
if(a==0)
{
printf("\nFILE INFO,found free bitmap:%d.\n",i*8+j);
return i*8+j;
}
}
}
}
printf("\nFILE ERROR,can't find free bitmap.\n");
return -1;
}
这个函数用来寻找位图中空闲的下一位,如果寻找成功返回序号,寻找失败返回-1。
int bitMapOutput()
{
printf("\nFILE INFO,bitmap output:\n");
for(int i=0;i<512;i++)
{
if(bitMap[i]==0)
printf("00000000");
else
{
for(int j=7;j>=0;j--)
{
int a=bitMap[i];
printf("%d",(a>>j)&0x01);
}
}
if((i+1)%16==0 && i!=0)
printf("\n");
}
printf("\nFILE INFO,bitmap output finished.\n");
}
这个函数可以将位图按照一定格式打印出来,在这里值得注意的是我们使用位运算来实现读取每一位。先右移,再与00000001
进行&
操作,这样便得到了每一位。
int fileDescriptorInsert(int fileSize,int blockList[3])
{
printf("\nFILE INFO,file descriptor is inserting.\n");
for(int i=0;i<7;i++)
{
read_block(i+1,(unsigned char*)fileDescriptor[i]);
}
for(int i=0;i<7;i++)
{
for(int j=0;j<sizeof(unsigned char)*512/sizeof(fileDescriptorItem);j++)
{
if (fileDescriptor[i][j].fileSize==0 && fileDescriptor[i][j].blockList[0]==0 && fileDescriptor[i][j].blockList[1]==0 && fileDescriptor[i][j].blockList[2]==0)
{
fileDescriptor[i][j].fileSize=fileSize;
fileDescriptor[i][j].blockList[0]= blockList[0];
fileDescriptor[i][j].blockList[1]= blockList[1];
fileDescriptor[i][j].blockList[2]= blockList[2];
for(int l=0;l<7;l++)
{
write_block(l+1,(unsigned char*)fileDescriptor[l]);
}
printf("FILE INFO,file descriptor inserted.\n");
return i*sizeof(unsigned char)*512/sizeof(fileDescriptorItem)+j;
}
}
}
printf("FILE ERROR,can't insertfile descriptor.\n");
return -1;
}
这个函数的功能是插入文件描述符。首先读取文件描述符所对应的逻辑块到内存中,之后寻找空的文件描述符位置,然后进行相应的修改操作,最后将所有修改写入物理硬盘中。
int fileDescriptorUpdate(int index,int fileSize,int blockList[3])
{
printf("\nFILE INFO,file descriptor is updating.\n");
for(int i=0;i<7;i++)
{
read_block(i+1,(unsigned char*)fileDescriptor[i]);
}
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].fileSize=fileSize;
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[0]= blockList[0];
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[1]= blockList[1];
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[2]= blockList[2];
for(int l=0;l<7;l++)
{
write_block(l+1,(unsigned char*)fileDescriptor[l]);
}
printf("FILE INFO,file descriptor updated.\n");
return 0;
}
这个函数是用来更新文件描述符,首先读取文件描述符所对应的逻辑块到内存中,然后进行相应的修改操作,最后将所有修改写入物理硬盘中。
int fileDescriptorDelete(int index)
{
printf("\nFILE INFO,file descriptor is deleting.\n");
for(int i=0;i<7;i++)
{
read_block(i+1,(unsigned char*)fileDescriptor[i]);
}
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].fileSize=0;
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[0]= 0;
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[1]= 0;
fileDescriptor[index/(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))][index%(sizeof(unsigned char)*512/sizeof(fileDescriptorItem))].blockList[2]= 0;
for(int l=0;l<7;l++)
{
write_block(l+1,(unsigned char*)fileDescriptor[l]);
}
printf("FILE INFO,file descriptor deleted.\n");
return 0;
}
这个函数的功能是用来删除文件描述符,参数为删除文件描述符的序号,进入函数体之后先从硬盘对应逻辑块读取文件描述符,之后进行对应修改,最后将所有内存中的文件描述符写会到硬盘中。
int initDic()
{
printf("FILE INFO,is initing dic.\n");
dictionary=(dictionaryItem*)calloc(sizeof(unsigned char)*512/sizeof(dictionaryItem),sizeof(dictionaryItem)) ;
int index=findFreeBitMap();
write_block(index,(unsigned char*)dictionary);
bitMapUpdate(1,index);
int blockList[3]={index};
int descriptorIndex=fileDescriptorInsert(1,blockList);
strncpy(dictionary[0].fileName,"Dictionary",strlen("Dictionary"));
dictionary[0].fileDescriptorIndex=descriptorIndex;
write_block(index,(unsigned char*)dictionary);
printf("FILE INFO,inited dic.\n");
return 0;
}
这个是用来初始化目录的函数,我们给目录指针分配了内存空间,并将其写入到硬盘之中,需要注意的是里面对于位图的分配与文件描述符的建立。
int readDic()
{
for(int i=0;i<7;i++)
{
read_block(i+1,(unsigned char*)fileDescriptor[i]);
}
int i0=fileDescriptor[0][0].blockList[0];
int i1=fileDescriptor[0][0].blockList[1];
int i2=fileDescriptor[0][0].blockList[2];
if(i0!=0)
{
read_block(i0,(unsigned char*)dictionary);
}
if(i1!=0)
{
read_block(i0,(unsigned char*)dictionary+512);
}
if(i2!=0)
{
read_block(i0,(unsigned char*)dictionary+512);
}
return 0;
}
这个是用来将目录从逻辑块中读取到内存中,由于目录最多可能有三块,所以我们需要先找到目录的文件描述符,然后根据blockList
里面的参数情况来分别读取。
int create(unsigned char *filename)
{
printf("\nFILE INFO,is creating file,filename is %s\n",filename);
int flag=0;
read_block(0,bitMap);
for(int i=1;i<512;i++)
{
if(bitMap[i]!=0)
{
flag=1;
break;
}
}
if(flag==0)
{
initDic();
}
/*Check dic is full or not*/
readDic();
CheckDic();
int FileDescriptorNum,MenuItemNum,DiskNum;
MenuItemNum = SearchMenuItem();
strcpy(menuitem[MenuItemNum].FileName,filename);
FileDescriptorNum = SearchFileDescriptor();
menuitem[MenuItemNum].FileDescriptorNum = FileDescriptorNum;
DiskNum = SearchBitMap();
filedescriptor[FileDescriptorNum].DiskNum[0] = DiskNum;
filedescriptor[FileDescriptorNum].IsFree = 'N';
return 0;
}
这个是建立文件函数,参数为所建立的文件名称,首先读取位图,并查找空闲的位,之后查看目录书否建立,如果没有建立执行相关操作,读取目录与文件描述符,并寻找空的目录项与文件描述符项,写入修改,最后写入到硬盘上。
int destroy(char* filename)
{
int temp = 1;
int pos = 0;
for (int i = 0; i < B_MAX; i++)
{
if (ldisk[0][0][i].flag == '1')
{
if (strcmp(ldisk[0][0][i].data, filename)== 0)
{
pos = i;
break;
}
}
}
if (pos == 0)
{
cout << "FILE ERROR,can't delete.\n" << endl;
}
else {
ldisk[0][0][pos].flag = '0';
ldisk[0][0][pos].data[0] = '\0';
ldisk[0][0][pos].next = NULL;
cout << "FILE INFO,deleted." << endl;
}
return 0;
}
这个函数用来根据文件名删除对应文件,需要注意的是删除时对文件描述符、逻辑块、目录项、位图等的具体操作,并写入更改到硬盘之中。
int open(char* filename)
{
int pos = 0;
for (int i = 0; i < B_MAX; i++)
{
if (ldisk[0][0][i].flag == '1')
{
if (strcmp(ldisk[0][0][i].data, filename)==0)
{
pos = i;
break;
}
}
}
if (pos == 0)
{
cout << "FILE ERROR,can't open.\n" << endl;
}
else {
cout << "FILE INFO,opened." << endl;
for (int j = 0; j < C_MAX; j++)
{
if (item[j].index == 0)
{
item[j].index = 19706500 + j;
item[j].pos = 0;
item[j].data = ldisk[0][0][pos].next;
cout << "index: " << item[j].index << endl;
return item[j].index;
}
}
}
return 0;
}
文件系统维护一张打开文件表.打开文件表的长度固定,其表目包含如下信息:
•读写缓冲区
• 读写指针
• 文件描述符号
文件被打开时,便在打开文件表中为其分配一个表目;文件被关闭时,其对应的表目被释放。读写缓冲区的大小等于一个磁盘存储块。打开文件时需要进行的操作如下:
• 搜索目录找到文件对应的描述符编号
• 在打开文件表中分配一个表目
• 在分配到的表目中把读写指针置为0,并记录描述符编号
• 读入文件的第一块到读写缓冲区中
• 返回分配到的表目在打开文件表中的索引号
int close(int index)
{
for (int j = 0; j < C_MAX; j++)
{
if (item[j].index == index)
{
item[j].index == 0;
item[j].pos = 0;
item[j].data = NULL;
}
}
cout << "FILE INFO,closed." << endl;
return 0;
}
关闭文件时需要进行的操作如下:
• 把缓冲区的内容写入磁盘
• 释放该文件在打开文件表中对应的表目
• 返回状态信息
int read(int index, string mem_area, int count)
{
for (int j = 0; j < C_MAX; j++)
{
if (item[j].index == index)
{
for (int i = 0; i < count; i++)
{
mem_area[i] = item[j].data->data[i + item[j].pos];
cout << mem_area[i];
}
cout << "FILE INFO,read." << endl;
return 0;
}
}
cout << "FILE ERROR,can't read.'" << endl;
return 0;
}
文件打开之后才能进行读写操作.读操作需要完成的任务如下:
- 计算读写指针对应的位置在读写缓冲区中的偏移
- 把缓冲区中的内容拷贝到指定的内存位置,直到发生下列事件之一:
• 到达文件尾或者已经拷贝了指定的字节数。这时,更新读写指针并返回相应信息
• 到达缓冲区末尾。这时,把缓冲区内容写入磁盘,然后把文件下一块的内容读入磁盘。最后返回第2步。
int write(int index, string mem_area, int count)
{
for (int j = 0; j < C_MAX; j++)
{
if (item[j].index == index)
{
myblock* p = item[j].data;
for (int i = 0; i < count; i++)
{
if (i+1 % 512 == 0)
{
p->next = NULL;
p = p->next;
}
p->data[item[j].pos] = mem_area[i];
item[j].pos++;
}
cout << "FILE INFO,wirtten." << endl;
return 0;
}
}
cout << "FILE ERROR,can't write." << endl;
return 0;
}
写文件时,须在相应系统调用中给出文件名和其在内存源地址。此时,系统要查找目录,找到指定目录项,从再利用目录中的写指针进行写操作。设置文件读/写指针的位置,以便每次读/写文件时,不需要从始端开始而是从所设置的位置开始操作。可以改顺序存取为随机存取。
四、测试
在这部分,我们将利用命令行测试上述编写的文件系统。
1.创建文件
2.删除文件
3.打开文件
已经嵌入到上述展示之中。
4.关闭文件
同上。
5.读取文件
6.写入文件
7.目录打印
8.备份与恢复
进入程序的开发者模式进行以下操作:
我们先进行备份测试:
int main()
{
init_ldisk();
write_block(2581,"55555555555555555");
FILE *fp=fopen("backupFile.bin","wb");
backup_disk(fp);
// init_ldisk();
// FILE *fp=fopen("backupFile.bin","rb");
// restore_disk(fp);
// char *p=(char*)malloc(sizeof(unsigned char)*512);
// read_block(2581,p);
// printf("%s\n",p);
// printf("\n");
system("pause");
return 0;
}
查看目录,发现备份文件:
下面我们进行恢复的测试:
int main()
{
// init_ldisk();
// write_block(2581,"55555555555555555");
// FILE *fp=fopen("backupFile.bin","wb");
// backup_disk(fp);
init_ldisk();
FILE *fp=fopen("backupFile.bin","rb");
restore_disk(fp);
char *p=(char*)malloc(sizeof(unsigned char)*512);
read_block(2581,p);
printf("%s\n",p);
printf("\n");
system("pause");
return 0;
}
可以看到,我们成功把磁盘内容恢复了。
9.位图打印
int main()
{
init();
bitMapOutput();
create("5555");
bitMapOutput();
}
可以看到,位图如我们预期更改了。
代码详见:https://github.com/Jerlllly/BJTU_operating-system-lesson/tree/master/Lab5