【文件系统】文件系统实现

一.文件系统结构

前一篇文章，讲了磁盘的结构，了解磁盘的结构之后，更容易了解内存和磁盘之间的I/O。

磁盘被分成磁道和扇区。一个扇区就是的数据块大小通常为512B。为了改善I/O效率，内存和磁盘之间的I/O转移是以块为单位而不是以字节为单位的。

每块（簇）为一个或多个扇区。

文件系统能轻松的存储，定位，提取数据，它的设计有两个问题。

  • 定义文件系统的接口，定义文件极其属性，文件所允许的操作、组织文件的目录结构。
  • 创建数据结构和算法来将逻辑文件系统映射到物理外存设备上。

1.1.基本文件系统

　　基本文件系统只需要向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写，每个块由其数值磁盘地址来表示。（驱动器1，柱面73，磁道3，扇区10）

我写了一个模拟的磁盘IO读取程序。main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "mode_disk.h"
char buf[BLOCKSIZE] = "love";
int main()
{
    srand((unsigned int)time(NULL));
    int k = 1000;
    int i,j,l;
    i = j = l = 0;
    while(k--)
    {
        write_disk(buf,i,j,l);
        *buf = rand()%10 + '0';
        *(buf + 1) = rand()%10 + '0';
        *(buf + 2) = rand()%10 + '0';
        *(buf + 3) = rand()%10 + '0';
        if(++l > (SECTORS - 1))
        {
            l = 0;
            if(++j > (TRACKS - 1))
            {
                j = 0;
                if(++i > (CYLINDERS - 1))
                {
                    printf("error.");
                    exit(0);
                }
            }
        }
    }
    k = 1000;
    i = j = l = 0;
    while(k--)
    {
        read_disk(buf,i,j,l);
        printf("%d,%d,%d:%s
",i,j,l,buf);
        if(++l > (SECTORS - 1))
        {
            l = 0;
            if(++j > (TRACKS - 1))
            {
                j = 0;
                if(++i > (CYLINDERS - 1))
                {
                    printf("error.");
                    exit(0);
                }
            }
        }
    }
    return 0;
}

disk.h

 1 #ifndef MODE_DISK_H_INCLUDED
 2 #define MODE_DISK_H_INCLUDED
 3 #define CYLINDERS 100
 4 #define TRACKS    500
 5 #define SECTORS   64
 6 #define BLOCKSIZE 5
 7 #define DATAFINE  1
 8 #define DATAERROR 0
 9 typedef struct __sector
10 {
11     char fine_flag;
12     char data_block[BLOCKSIZE];
13 }SECTOR_s;
14 int read_disk(char * buf,int cylinder,int tarck,int sector);
15 int write_disk(char * data,int cylinder,int tarck,int sector);
16 #endif // MODE_DISK_H_INCLUDED
mode_disk
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 #include <string.h>
 5 #include "mode_disk.h"
 6 SECTOR_s disk[CYLINDERS][TRACKS][SECTORS];
 7 int read_disk(char * buf,int cylinder,int tarck,int sector)
 8 {
 9     if(disk[cylinder][tarck][sector].fine_flag == DATAFINE)
10     {
11         memcpy(buf,disk[cylinder][tarck][sector].data_block,BLOCKSIZE);
12         return 1;
13     }
14     else
15     {
16         printf("Disk,cylinde=%d,track=%d,setcor=%d is error.
",cylinder,tarck,sector);
17         return 0;
18     }
19 }
20 int write_disk(char * data,int cylinder,int tarck,int sector)
21 {
22     if((100 - rand()%100) > 5)
23     {
24         memcpy(disk[cylinder][tarck][sector].data_block,data,BLOCKSIZE);
25         disk[cylinder][tarck][sector].fine_flag = DATAFINE;
26         return 1;
27     }
28     else
29     {
30         disk[cylinder][tarck][sector].fine_flag = DATAERROR;
31         return 0;
32     }
33 }
mode_disk.c

 1.2.文件组织模块

文件组织模块FOM知道文件及其逻辑块和物理块。由于知道所使用的文件分配类型和文件的位置，文件组织模块可以将逻辑地址转换成基本文件系统同所使用的物理块地址。每个文件的逻辑块按从0或1到N来编号，文件组织模块也包括空闲空间管理器。用来跟踪未分配的块并且根据要求提供给文件组织模块。

1 #define TRACK_n(n) ((n / SECTORS) % TRACKS)
2 #define CYLINDER_n(n) ((n / (SECTORS * TRACKS))% CYLINDERS)
3 #define SECTOR_n(n) (n % SECTORS)
逻辑块到物理块的转换

1.3. 逻辑文件系统

逻辑文件系统管理元数据，元数据包括文件系统的所有结构数据，而不包括实际数据，逻辑文件系统根据给定符号文件名来管理目录结构，并提供给文件组织模块所需要的信息。

逻辑文件系统通过文件控制块来维护文件结构。文件控制块（FILE CONTROL BLOCK,PCB）或许unix中称为inode。包括文件的信息，如拥有者，权限，文件内容的位置。

二. 文件系统实现

2.1 概述

在磁盘上，文件系统可能包含如下信息，如何启动所存储的操作系统，总的块数，空闲块的数目和位置，目录结构以及各个具体文件等。

  • 每个卷的引导控制块（boot control block）
  • 每个卷的卷控制块（volume control block）
  • 每个文件系统的目录结构，UFS中包含文件名和相关的索引节点号（NOT inode itself） NTFS中它存储在文件控制表(Master File Table)中。
  • 每个文件的FCB包含很多该文件的详细信息。如权限，拥有者，大小和数据块的位置。UFS中成为inode，NTFS将这些信息存在主控文件表中，主控文件表采用关系数据库，每个文件占一行。
  • 一个内存中的安装表，包括所有安装卷的信息。
  • 一个内存中的目录结构缓存，用来保存进来访问过的目录信息。
  • 系统范围内的打开文件表
  • 单个进程的打开文件表

创建一个新文件，应用程序调用逻辑文件系统，逻辑文件系统知道目录结构形式，为了创建一个新文件，它将分配一个新的PCB（如果文件系统实现在文件系统被创建的时候已经建立了所有的FCB（inode），那么只是从空闲FCB集合中分配一个。）然后系统把相应的目录信息读入内存，用新的文件名更新目录和PCB，并将结果写会磁盘。

2.2 分区与安装

每个分区包含不同类型的文件系统和不同的操作系统。

操作系统有“装入表”来注明该文件系统已装入该文件系统已经装入和该文件系统的类型。

UNIX可以将文件系统安装在任何目录上。

2.3 虚拟文件系统

面向对象思想？？？？？？？？？？

回调函数？？？？？？？？？？？？

保留一个指针，然后注册函数？？？

三. 目录实现

3.1 线性列表

最简单的目录实现方法使用存储文件名和数据块的线性列表。（可以固定列表长度，也可以不固定列表长度。）

我们想想/etc/hello文件夹下有以下文件

hello.c

hello.o

hello.h

nota.c

notb.c

缺点是需要线性搜索，比如查找hello.h需要从头开始逐个对比。

可以用二分搜索，建立复杂的树数据结构等等来优化操作。

3.2 哈希表

哈希表很厉害很厉害，需要一些措施避免冲突。

四. 分配方法

分配方法有三种，连续分配，连接分配，索引分配。

4.1 连续分配

4.2 连接分配

4.3 索引分配

　　索引分配有三个变种

　　4.3.1 连接方案

　　4.3.2 多层索引

　　4.3.3 组合方案

　　组合方案有直接块，间接块，二级间接快。

五. 空闲空间管理

　　空闲空间管理有四种方案

　　位向量，空闲链表，组，计数。

　　空闲链表的大致结构体如下：

　　

　typedef struct __hello

　　{

　　　　char data[508];

　　　　struct __hello * next;

　　}HELLO;

　　组是一个空闲块的前n个区域存放的是n个空闲块的地址，最后一个块存放的是包含指向n个空闲地址的块。

　typedef struct __hello

　　{

　　　　void * free_blocks[n];

　　　　struct __hello * next;

　　}HELLO;

　　经典链表方式，不值一提。

　　计数的方式如下：

　typedef struct __hello

　　{

　　　　void * freeblock;

　　　　long n;　　

　　}

　　表示freeblock地址及其接下来的长度都是空闲的，由于连续块的数量常常大于1，所以这种结构是有意义的。

总结：

这两篇文章是我在阅读《操作系统概念》的时候写的，为了弄清楚文件系统的概念，搜索了大量的资料。觉得搞清楚了一大堆东西。

有两个问题没有说清楚就是分区和制作文件系统。

我们通常用fdisk /dev/sda来分区，我认为（没有安装操作系统的磁盘）这个命令将在设备的第一块磁盘建立分区表。

分区表有分区表的数据结构，知道了这个数据结构，便也没有什么难度。

然后使用mkfs.ext3 /dev/sda1制作文件系统的是时候。

我认为是这样的，在分区的第一个扇区建立超级块，然后建立大量的inode，inode建立在磁盘的各个地方。

现在还有一个地方搞不懂！，我们可以通过inode知道一个文件的块，但是怎么访问inode呢？？？？？？？？

又假设inode遍布磁盘的话，问题更难了。

OK,在linux0.11中，是用数组来保存的。

#define NR_INODE 32
struct m_inode inode_table[NR_INODE]={0};// 内存中i 节点表（NR_INODE=32 项）。

而linux3.0中初始化inode用的是hash表。

好吧，文件系统的探索之旅告一个段落了，我越来越发现数据结构和算法的重要性。我要学习他们。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/likeyiyy/p/3264176.html