操作系统——文件系统

Posted on | In | 次阅读
Words count in article: 4.3k 字 | Reading time ≈ 18 min

实验简介

本实验要求在模拟的I/O系统之上开发一个简单的文件系统。用户通过create, open, read等命令与文件系统交互。文件系统把磁盘视为顺序编号的逻辑块序列，逻辑块的编号为0至L − 1。
I/O系统利用内存中的数组模拟磁盘。

整体设计

根据题设要求，文件系统的整体设计框架如下：
Alt text

I/O系统

设计要求

实际物理磁盘的结构是多维的：有柱面、磁头、扇区等概念。I/O系统的任务是隐藏磁盘的结构细节，把磁盘以逻辑块的面目呈现给文件系统。逻辑块顺序编号，编号取值范围为0至L−1，其中L表示磁盘的存储块总数。实验中，我们可以利用数组ldisk[C][H][B]构建磁盘模型，其中CHB 分别表示柱面号，磁头号和扇区号。每个扇区大小为512字节。I/O系统从文件系统接收命令，根据命令指定的逻辑块号把磁盘块的内容读入命令指定的内存区域，或者把命令指定的内存区域内容写入磁盘块。

数据结构

本实验需要用数组来模拟实际磁盘的三维结构，为了方便表述对扇区内存储内容的描述，我们使用如下结构体：

1
2
3
4
5
6
7
typedef struct ldisk
{
    int C; //柱面号
    int H; //磁头号
    int B; //扇区号
    char content[SIZE + 1]; //扇区中的内容
}LDISK;

功能接口

read_block

函数原型

1
read_block(int i, char *p)

实现的功能：把逻辑块i的内容读入到指针p指向的内存位置，拷贝的字符个数为存储块的长度B。
核心思想：根据传入的逻辑块i计算出其对应的磁盘三维坐标数据，计算过程如注释所述。
其中sectorsPerTrack代表每个磁道上的扇区数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
int read_block(int i, char *p)
{
    int y = i / sectorsPerTrack;
    //扇区号
    disk[i].B = i % sectorsPerTrack + 1;
    //柱面号
    disk[i].C = y >> 1;
    //磁头号
    disk[i].H = y & 1;
    //读入p
    strcpy(p, disk[i].content);
    return 0;
}

write_block

函数原型

1
int write_block(int i, char *p)

实现的功能：把指针p指向的内容写入逻辑块i，拷贝的字符个数为存储块的长度B。
实现思路同上，核心思想也是解决坐标的变换。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int write_block(int i, char *p)
{
    int y = i / sectorsPerTrack;
    //扇区号
    disk[i].B = i % sectorsPerTrack + 1;
    //柱面号
    disk[i].C = y >> 1;
    //磁头号
    disk[i].H = y & 1;
    //写入
    strcpy(disk[i].content, p);
    return 0;
}

文件系统

设计要求

文件系统的总体设计共有如下要求：

  • 文件系统位于I/O系统之上；
  • 文件系统需提供如下函数：create, destroy, open, read, write；
  • 磁盘的前k个块是保留区，其中包含如下信息：位图和文件描述符；
  • 文件系统中仅设置一个目录，该目录包含文件系统中的所有文件；
  • 创建文件/删除文件；
  • 文件打开：在打开文件表中为其分配一个表目；
  • 文件关闭：其对应的表目被释放；
  • 文件读写：计算读写指针对应的位置在读写缓冲区中的偏移、把缓冲区中的内容拷贝到指定的内存位置。

文件系统的组织

磁盘的前k个块是保留区，其中包含如下信息：位图和文件描述符。位图用来描述磁盘块的分配情况。位图中的每一位对应一个逻辑块。创建或者删除文件，以及文件的长度发生变化时，文件系统都需要进行位图操作。前k个块的剩余部分包含一组文件描述符。每个文件描述符包含如下信息：
• 文件长度，单位字节
• 文件分配到的磁盘块号数组。该数组的长度是一个系统参数。在实验中我们可以把它设置为一个比较小的数，例如3。

为了辅助实现用户与文件系统之间的接口函数，需要定义文件类型变量的结构体，根据上述需求，结构体中需要包含如下的的成员变量：

1
2
3
4
5
6
7
8
9
typedef struct files
{
    int number; //文件编号
    char *filename; //文件名
    int size; //文件大小
    int pos; //文件偏移指针
    INDIRECT *addr[3]; //3个直接地址
    char *content; //存放文件中的所有内容
}FILES;

用户与文件系统之间的接口

根据题目要求，该处的主要工作为上述五个接口函数的实现。

create

函数原型

1
int create(char *filename)

实现的功能：根据指定的文件名创建新文件。

实现思想：首先根据传入文件名判断是否已存在同名文件，若存在则报错；若不存在则将其装入位图。
实现代码如下，其中M为位图的行数、K为保留区的长度、L为总的逻辑扇区数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int create(char *filename)
{

    DIC *dic = dicHead;
    int flag = 0;
    for(int i = 0; i < countOfFiles; i ++)
    {
        if(strcmp(dic->filename, filename) == 0)
        {
            flag = 1;
            break;
        }

        dic = dic->next;
    }

    if(flag == 1)
    {
        printf("FileExisted!\n");
        return NULL;
    }

    int a = M;
    int start = K;
    int size = L - K;
    countOfFiles ++;
    //生成随机数
    int blockNumber = createRandomNUmber(start, size);
    //查询位图
    while(map[blockNumber / a][blockNumber % a] == 1)
        blockNumber = createRandomNUmber(start, size);
    //置位图为1
    map[blockNumber / a][blockNumber % a] = 1;
    //建立目录
    createDirectory(filename, blockNumber);
    printf("创建%s成功\n", filename);
    return 0;
}

delete

函数原型

1
int delete(char *filename)

实现的功能：根据指定的文件名删除指定文件。

实现思想：首先根据传入文件名判断是否已存在同名文件，若不存在则报错；若存在则将其从块、目录中删除。
实现代码如下，其中SIZE为扇区大小（字节数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int destroy(char *filename)
{
    DIC *dic = dicHead;

    int flag = 0;
    for(int i = 0; i < countOfFiles; i ++)
    {
        if(strcmp(dic->filename, filename) == 0)
        {
            flag = 1;
            break;
        }

        dic = dic->next;
    }

    if(flag == 0)
    {
        printf("FileNotExist!\n");
        return -1;
    }

    //删除文件
    int blockNumber = dic->index1->size / SIZE;
    if(dic->index1->size % SIZE > 0)
        blockNumber ++;
    //删除所有块里的元素
    for(int i = 0; i < blockNumber; i ++)
    {
        write_block(dic->index1->addr[i]->diskNum, "\0");
    }
    //删除目录
    destoryDirectory(filename);
    countOfFiles --;
    return 0;
}

open

函数原型

1
FILES *open(char *filename)

实现的功能：根据指定的文件名打开文件，且该函数返回的索引号可用于后续的read, write, lseek,或close操作。

实现思想：首先根据传入文件名判断是否已存在同名文件，若不存在则报错；若存在则计算块号和块内偏移地址，并将其从磁盘中读至file。
实现代码如下，其中SIZE为扇区大小（字节数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
FILES *open(char *filename)
{
    DIC *dic = dicHead;

    char buffer[512] = ""; //缓冲区
    int flag = 0;
    for(int i = 0; i < countOfFiles; i ++)
    {
        if(strcmp(dic->filename, filename) == 0)
        {
            flag = 1;
            break;
        }

        dic = dic->next;
    }

    if(flag == 0)
    {
        printf("FileNotExist!\n");
        return NULL;
    }

    FILES *file = NULL;
    file = (FILES *)malloc(sizeof(FILES));
    file->number = dic->index1->number;
    for(int i = 0; i < 3; i ++)
        file->addr[i] = (INDIRECT *)malloc(sizeof(INDIRECT));
    for(int i = 0; i < 3; i ++)
        memcpy(file->addr[i], dic->index1->addr[i], sizeof(INDIRECT));
    file->size = dic->index1->size;
    file->filename = (char *)malloc(strlen(filename) * sizeof(char));
    memcpy(file->filename, filename, strlen(filename));
    file->pos = 0;
    //将磁盘中的内容读到file中
    int block = file->size / SIZE;
    int offset = file->size % SIZE;
    file->content = (char *)malloc(file->size * sizeof(char));
    if(offset > 0)
        block ++;
    for(int i = 0; i < block; i ++)
    {
        read_block(dic->index1->addr[i]->diskNum, buffer);
        strcpy(&file->content[i * SIZE], buffer);
    }
//    printf("打开成功\n");
    return file;
}

close

函数原型

1
int close(FILES *file)

实现的功能：关闭指定文件。
实现思想：将file指针指定的文件的文件名和文件内容释放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int close(FILES *file)
{
    for(int i = 0; i < 3; i ++)
        free(file->addr[i]);
    for(int i = 0; i < 3; i ++)
        file->addr[i] = NULL;
    //释放文件名
    if(file->filename != NULL)
    {
        free(file->filename);
        file->filename = NULL;
    }
    //释放文件内容
    if(file->content != NULL)
    {
        free(file->content);
        file->content = NULL;
    }
    //释放file指针
    free(file);
    printf("关闭成功\n");
    return 0;
}

read

函数原型

1
FILES *read(FILES *file, char *mem_area, int count)

实现的功能：从指定文件顺序读入count个字节memArea指定的内存位置。读操作从文件的读写指针指示的位置开始。

实现思想：根据count指定的长度计算需要读的扇区数目a，然后依次从这a个扇区中将file->content所指向的数据依次读入缓冲区buffer，并拷贝至指定的内存连续区mem_area，最后修改读写文件指针file->pos向后移动count个位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FILES *read(FILES *file, char *mem_area, int count)
{
    char buffer[512] = ""; //缓冲区
    if((count + file->pos) > file->size)
        return NULL; //越界错误
    int a = count / SIZE;
    for(int i = 0; i < a; i ++)
    {
        memcpy(buffer, &file->content[file->pos + i * SIZE], SIZE * sizeof(char));
        strcpy(&mem_area[i * SIZE], buffer);
    }
    memcpy(buffer, &file->content[file->pos + a * SIZE], (count % SIZE) * sizeof(char));
    strcpy(&mem_area[a * SIZE], buffer);
    file->pos = file->pos + count;
    printf("读入成功\n");
    return file;
}

write

函数原型

1
FILES *write (FILES *file, char *mem_area, int count)

实现的功能：把memarea指定的内存位置开始的count个字节顺序写入指定文件。写操作从文件的读写指针指示的位置开始。

实现思想：写入文件的逻辑较读操作来说更为复杂。
首先需要根据文件指针找到文件所在的逻辑块并清空所对应磁盘中的内容；其次需要将位图的对应部分清空；最后还需要将现有目录中的对应内容（即diskNum、count）清空。
准备工作完成后，下面进行写入动作。
首先根据写入文件的数据大小count更新文件读写指针的位置为file->pos + count；其次为文件内容区域重新分配内存空间并把待写入的数据mem_area写入；最后将写入新数据的file写回磁盘和目录中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
FILES *write (FILES *file, char *mem_area, int count)
{
    DIC *dic = dicHead;
    char buffer[512] = ""; //缓冲区
    if(file->pos + count > file->size)
        return NULL; //越界

    //清除原先磁盘扇区中的数据
    int m = M;
    int blocknumber = file->size / SIZE;
    if((file->size % SIZE) > 0)
        blocknumber ++;
    for(int i = 0; i < blocknumber; i ++)
        strcpy(disk[file->addr[i]->diskNum].content, "\0");
    for(int i = 1; i < blocknumber; i ++)
        //改位图
        map[file->addr[i]->diskNum / m][file->addr[i]->diskNum % m] = 0;
    //找到目录
    for(int i = 0; i < countOfFiles; i ++)
    {
        if(dic->index1->number == file->number)
            break;
        dic = dic->next;
    }
    //更改目录中的内容
    for(int i = 1; i < blocknumber; i ++)
        dic->index1->addr[i]->diskNum= 0;
    for(int i = 0; i < 3; i ++)
        dic->index1->addr[i]->count = 0;
    for(int i = 1; i < 3; i ++)
        dic->index1->addr[i]->diskNum = -1;
    //更改file指针中文件的内容
    file->size = file->pos + count;
    //重新分配空间
    char *s;
    s = (char *)malloc(strlen(file->content) *sizeof(char));
    memcpy(s, file->content, strlen(file->content) *sizeof(char));
    file->content = (char *)realloc(file->content, file->size * sizeof(char));
    memcpy(file->content, s, sizeof(file->pos) *sizeof(char));
    memcpy(&file->content[file->pos], mem_area, count * sizeof(char));
    //将file中的内容通过buffer写入磁盘
    blocknumber = file->size / SIZE;
    if(file->size % SIZE > 0)
        blocknumber ++;
    //生成随机的磁盘扇区块
    int start = K;
    int size = L - K;
    for(int i = 1; i < blocknumber; i ++)
    {
        file->addr[i]->diskNum = createRandomNUmber(start, size);
        while(map[file->addr[i]->diskNum / m][file->addr[i]->diskNum % m] != 0)
            file->addr[i]->diskNum = createRandomNUmber(start, size);
    }
    //从buffer中写入扇区
    for(int i = 0; i < blocknumber - 1; i ++)
    {
        //存入缓冲区
        memcpy(buffer, &file->content[i * SIZE], (SIZE) * sizeof(char));
        //缓冲区存入磁盘
        write_block(file->addr[i]->diskNum, buffer);
    }
    if(count % SIZE > 0)
    {
        strcpy(buffer, &file->content[(blocknumber - 1) * SIZE]);
        write_block(file->addr[blocknumber - 1]->diskNum, buffer);
    }
    else if(count % SIZE == 0)
    {
        memcpy(buffer, &file->content[(blocknumber - 1) * SIZE], SIZE * sizeof(char));
        write_block(file->addr[blocknumber - 1]->diskNum, buffer);
    }
    for(int i = 0; i < blocknumber - 1; i ++)
        file->addr[i]->count = SIZE;
    if(file->size == SIZE)
        file->addr[blocknumber - 1]->count = file->size;
    else
        file->addr[blocknumber - 1]->count = file->size % SIZE;
    //写回目录
    for(int i = 0; i < 3; i ++)
        memcpy(dic->index1->addr[i], file->addr[i], sizeof(INDIRECT));
    dic->index1->size = file->size;
    file->pos = file->size;
    printf("写入成功\n");
    free(buffer);
    return file;
}

lseek

函数原型

1
FILES *lseek(FILES* file, int pos)

实现的功能：把文件的读写指针移动到pos指定的位置。pos是一个整数，表示从文件开始位置的偏移量。文件打开时，读写指针自动设置为0。每次读写操作之后，它指向最后被访问的字节的下一个位置。lseek能够在不进行读写操作的情况下改变读写指针能位置。

实现思想：直接对file指针对应的结构体变量pos操作即可。

1
2
3
4
5
FILES *lseek(FILES* file, int pos)
{
    file->pos += pos;
    return file;
}

目录

我们的文件系统中仅设置一个目录，该目录包含文件系统中的所有文件。除了不需要显示地创建和删除之外，目录在很多方面和普通文件相像。目录对应0号文件描述符。初始状态下，目录中没有文件，所有目录对应的描述符中记录的长度应为0，而且也没有分配磁盘块。每创建一个文件，目录文件的长度便增加。目录文件的内容由一系列的目录项组成，其中每个目录项由如下内容组成：
• 文件名
• 文件描述符序号

数据结构

地址项

1
2
3
4
5
typedef struct indirect
{
    int diskNum; //磁盘逻辑扇区号
    int count; //使用过的长度
}INDIRECT;

文件标识符

1
2
3
4
5
6
typedef struct index
{
    int number; //文件标识符号
    int size; //大小
    INDIRECT *addr[3]; //3个直接地址
}INDEX;

目录的存储结构

目录结构体的存储结构如下：

1
2
3
4
5
6
typedef struct directory1
{
    int number; //文件标识符号
    int size; //大小
    INDIRECT **addr; //目录所占的直接地址
}DIC1;

这里通过链表结构来显示目录中的所有文件及其长度：

1
2
3
4
5
6
typedef struct directory
{
    char *filename; //文件名
    INDEX *index1;//文件索引
    struct directory *next; //使用循环链表储存目录信息
}DIC;

与目录相关的操作如下所述：

初始化目录

初始化即为目录的相关成员分配各自的内存空间。

1
2
3
4
5
6
7
8
9
10
11
int initDic()
{
    printf("初始化目录-----");
    dic1 = (DIC1 *)malloc(sizeof(DIC1));
    dic1->number = 0;
    dic1->size = 0;
    dicHead = (DIC *) malloc(sizeof(DIC));
    dicTail = (DIC *) malloc(sizeof(DIC));
    printf("ok\n");
    return 0;
}

创建目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int createDirectory(char *filename, int blockNumber)
{
    int k = K;
    if(countOfFiles * sizeof(DIC) + sizeof(dic1) > (k - blockOfMap) * SIZE)
        return -1; //目录越界
    DIC *dic = NULL;
    dic = (DIC *) malloc(countOfFiles * sizeof(DIC));
    dic->filename = (char *) malloc(strlen(filename) * sizeof(char));
    strcpy(dic->filename, filename);
    dic->index1 = (INDEX *)malloc(sizeof(INDEX));
    dic->index1->number = countOfFiles;
    dic->index1->size = 0;
    for(int i = 0; i < 3; i ++)
        dic->index1->addr[i] = (INDIRECT *)malloc(sizeof(INDIRECT));
    dic->index1->addr[0]->diskNum = blockNumber;
    dic->index1->addr[0]->count = 0;
    dic->next = (DIC *)malloc(sizeof(DIC));
    //生成链表
    if(countOfFiles == 1)
    {
        memcpy(dicHead, dic, sizeof(DIC));
        dicTail = dicHead;
        dicHead->next = dicTail;
        dicTail->next = dicHead;
        free(dic);
    } else
    {
        dicTail->next = dic;
        dic->next = dicHead;
        dicTail = dic;
    }
    return 0;
}

删除目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int destoryDirectory(char *filename)
{
    DIC *dic = dicHead;
    DIC *dic2 = dicHead;
    int a = M;
    int i;
    //找到filename对应的目录
    for(i = 0; i < countOfFiles; i ++)
    {
        if(strcmp(dic->filename, filename) == 0)
            break;
        dic2 = dic;
        dic = dic->next;
    }
    //计算出文件占用了多少扇区
    int x = dic->index1->size;
    int y = x / SIZE;
    if(x % SIZE > 0)
        y ++;
    //释放所有扇区信息
    for(int j = 0; j < y; j ++)
        //修改位图
        map[dic->index1->addr[j]->diskNum / a][dic->index1->addr[j]->diskNum % a] = 0;
    for(int i = 0; i < 3; i ++)
        free(dic->index1->addr[i]);
    free(dic->index1);
    //释放文件名
    free(dic->filename);
    //释放目录
    dic2->next = dic->next;
    dicHead = dic2->next;
    free(dic);
    return 0;
}

测试

在文件系统的基础功能都完成之后，编写外壳程序来将各个功能组织到一起，下面来对各个功能进行测试。
首先通过终端编译生成可执行文件：
Alt text
创建文件：通过调用1号功能来新建三个测试文件test1、test2和test3
Alt text
显示文件：通过调用8号功能来显示目前已有的文件，可以观察到刚刚新建的三个文件的物理信息（文件名，文件标号，大小，所占磁盘块，所占大小）
Alt text
删除文件：通过调用2号功能来删除测试文件test3，再通过8号功能显示文件信息如下
Alt text
写文件：通过调用3号功能首先打开测试文件test1，再通过6号功能向文件中写入测试数据，最后通过8号功能显示文件信息如下
Alt text
读文件：通过5号功能从已打开的文件test1中读取10位测试数据，显示读取结果如下，可以看到成功把之前向文件中写入的测试字符串按指定长度读中并显示
Alt text

至此，文件系统的基本功能：增删改查已全部实现！

小手一抖⬇️