刚收到了一个消息，老师竟然布置了一个课设 ，要求做一个后台管理系统。做归做，但是！本着为老师节省时间的心态，我花了大量的时间，消耗了无数脑细胞扫描了一遍老师给的课题，最终掐指一算选了一个最简单的——>"图书管理系统"。
 
    刚开始我的想法是用jsp+(struts2+spring+hibernate)+Oracle写的，毕竟以前也用这玩意写过类似的东西，等我打开Oracle后却发现我的Oracle又又又出问题了，再加上用上面这三大框架写的话文件太多了，于是我毅然决然放弃它了。直接用更简单的语言(PHP)来写。
 
 
 
 
 
第一 用到的技术
 
    技术和语言：php + MySQL
 
    开发环境：windows 10
 
    开发工具：sublime3 + XAMPP
 
 
 
 
 
 
 
第二 要求（我只实现了下面这几个要求，其他的没时间弄，而且我也不想写了）
 
            1．用户管理：能够增加、删除和修改用户（用户管理，注销登录）；
 
            2．图书管理：进行分类管理，图书管理 等操作；
 
            3．信息管理：在主界面搜索栏对图书或读者名称可以进行搜索查询，能够增加、删除和修改；
 
 
 
 
 
工具及源码下载在最下方    请在新下载地址下载！（新下载地址里面有详细使用教程）
 
 
 
旧下载地址源码复制完报错解决方案：   
 
                                             https://pan.lanzou.com/i0k52kh
 
                                             把这个压缩包内的两个文件夹粘贴放到xampp\mysql\data\覆盖下就可以了
 
            登录帐号：php 密码：php
 
 
 
 
 
部分截图：


     登录界面：

     主界面：


     图书馆管理界面：

     读者管理界面：

     读者详情界面：

     类型管理：

    

下载：
     工具XAMPP下载地址  https://download.csdn.net/download/leslie___cheung/10260215
         链接：https://pan.baidu.com/s/1sm4KFM1密码：2zxx
     源码下载：http://download.csdn.net/download/leslie___cheung/10208367  (旧地址)
     （新下载地址）https://download.csdn.net/download/leslie___cheung/10479307
 
(太久了 本人也没有源码了 别下)
   

源码使用方法：（新下载地址里面有详细使用教程）
     将其中的将bms和mysql整个文件夹和ibdata1(bms文件夹里的是数据库文件)复制粘贴到xampp安装路
 径下的mysql文件夹里的data文件夹里面，接着接着打开XMAPP，然后再打开浏览器输入网址" http://localhost/phpmyadmin "
 刷新页面数据库就会导入。另一个图书管理系统文件夹复制粘贴到xampp安装路径下的htdocs文件夹里，
 浏览器输入" http://localhost/图书管理系统 "即可进入管理界面。
 我的路径：数据库文件夹粘贴路径 :"D:\xampp\mysql\data\"
      图书管理系统粘贴路径 :"D:\xampp\htdocs\"
 
 
 
 
 
 

课题作业任务：在内存中开辟一个100M的空间作为磁盘空间，在此上模拟创建一个文件管理系统。
 
本系统已经实现的相关操作：
 
 
所有操作都不支持从根目录索引，即都只能访问当前目录下的文件，不能用/a/b越级访问
 
1）目录相关操作
 
列出目录下所有文件：ls
 
切换目录：cd newdir
 
显示目录：pwd
 
创建目录：mkdir dirName
 
删除目录和目录下所有文件：rmdir dirName
 
修改目录名或文件名：mv oldName newName
 
 2）文件相关操作
 
创建文件（大小以1KB为单位）：touch filename fileSize
 
删除文件：rm filename
 
从上一次后读取size字节的文件内容：read fileName size
 
从头开始读取size字节的文件内容：reread fileName size
 
从文件尾写入内容：write fileName content
 
清空文件，从头写入：rewrite fileName content
 
 3）系统操作
 
使用命令帮助:help
 
退出系统：quit
 

 
 
全部代码大概有600多行，是一个非常简单的实现，不适合想要深入了解的人观看，网上有其他的功能较为强大实现，代码都在上千，比较具有学习的价值。
 
点击打开链接（很强大，我自己也还没有仔细看）
 
 
点击打开链接（代码好像有点问题）
 
 
点击打开链接
 
 
1. 系统层次结构：
 

 
 
 
 
 
系统接口:是该文件系统提供给用户可以使用的命令接口,如ls,mkdir,touch等
 
文件管理：是系统对于文件和目录层次的管理的，规定了FCB结构，目录结构等，包含了对接口的实现。
 
磁盘管理：是系统最底层直接对内存空间的管理，如磁盘空闲空间管理，磁盘空间的分配方式等。
 
 
2. 磁盘管理
 
 
盘块大小：以1KB的空间作为系统盘块，用以分配的基本单位
 
分配方式：系统采用连续分配的方式，在磁盘上划定要求的连续盘块分配给文件使用
 
空间管理：系统采用位示图的方法，标记了磁盘上所有盘块的使用情况。
 
    使用systemStartAddr标记了整个系统的起始地址，以1KB作为盘块划分，所以本系统共有100K个盘块。位示图用char[]表示，所以位示图大小为100KB。位示图存储在系统起始位置，在系统初始化时，0~99号盘块默认被存储位示图使用。
 
 
磁盘向文件管理提供的接口说明：
 
DiskOperate.h 
 
#ifndef DISKOPERATE_H_INCLUDED
#define DISKOPERATE_H_INCLUDED
//磁盘操作接口
#define system_size 100*1024*1024   //系统大小
#define block_szie 1024 //盘块大小
#define block_count system_size/block_szie //系统盘块数目

//初始化系统
void initSystem();
//磁盘分配
int getBlock(int blockSize) ;
//获得盘块的物理地址
char* getBlockAddr(int blockNum);
//获得物理地址的盘块号
int getAddrBlock(char* addr);
//释放盘块、
int releaseBlock(int blockNum, int blockSize);
//退出系统
void exitSystem();
#endif // DISKOPERATE_H_INCLUDED
 
 

 
 
3.文件层次管理说明
 

 FileOperate.h （部分内容）
 

 
//目录项结构：
struct dirUnit{
    char fileName[59];  //文件名
    char type;  //文件类型,0目录， 1文件
    int startBlock; //FCB起始盘块
};
//一个目录项包含了文件名和文件类型，当文件为目录时，起始盘块指示了目录表所在的盘块号，当文件为文件时，起始盘块指示了FCB所在的盘块号。
#define dirTable_max_size 15    //目录表项最大值
//目录表结构：
struct dirTable {
    int dirUnitAmount;//目录项数目
    dirUnit dirs[dirTable_max_size];//目录项列表
};
/*
本系统规定一个目录表只占用一个盘块，一个目录项大小为64B，所以一个目录表中最多可含15个目录项，dirUnitAmount记录每个目录表中已含有的目录项数目。系统在初始化时，会自动生成一个空的根目录表存放于磁盘中，作为用户的初始位置，用户所有的目录和文件都这个表为根进行树状目录结构的展开。
当创建一个目录表时，系统会自动为目录表加上一项名为”..”的目录项，指示父目录表的位置。
*/

//FCB结构：
struct FCB {
    int blockNum;   //文件数据起始盘块号
    int fileSize;   //文件大小，盘块为单位
    int dataSize;   //已写入的内容大小，字节为单位
    int readptr;    //读指针，字节为单位
    int link;   //文件链接数
};
/*
	文件控制块包含了文件数据的起始位置和大小。dataSize,readptr是为文件的读写操作而准备的，记录文件已写入的内容长度（不可超过文件大小），和当前读取的位置。Link记录了文件的链接数，用于文件的共享，当文件的链接数为0时，系统可以回收文件的空间。同样的，一个FCB大小为20B，但也用一个盘块保存。
	由于采用的是连续分配方式，所以系统规定文件被创建时，必须给出文件的大小，而且后期也不能修改文件的大小。
*/
 
看到这里，如果你有修过计算机系统的话，你就会发现我采取了一种最简单的实现方式，都说了十分简易嘛~~
 
系统用char[]数组作为位示图保存了每一个盘块的使用状态，而且采取了连续分配的方式，对于目录表和FCB都规定直接使用一个盘块，文件又是规定好大小不能扩展的，所以实现起来减少了很多FAT，索引表，那些离散分配所需的连接方式，单纯练手的话，还是十分简易的。
 
 
 
具体实现
 
1. 磁盘管理的实现
 
这部分比较简单，代码备注也很详细了，可以直接看代码
 
DiskOperate.cpp
 
 
#include"DiskOperate.h"

#include<stdio.h>
#include<stdlib.h>



char* systemStartAddr;  //系统起始地址

//初始化系统
void initSystem()
{
    //创建空间
    systemStartAddr = (char*)malloc(system_size * sizeof(char));
    //初始化盘块的位示图
    for(int i=0; i<block_count; i++)
        systemStartAddr[i] = '0';
    //用于存放位示图的空间已被占用
    int bitMapSize = block_count * sizeof(char) / block_szie;//位示图占用盘块数:100
    for(int i=0; i<bitMapSize; i++)//从零开始分配
        systemStartAddr[i] = '1';   //盘块已被使用
}
//退出系统
void exitSystem()
{
    free(systemStartAddr);
}
//磁盘分配
int getBlock(int blockSize)
{
    int startBlock = 0;
    int sum=0;
    for(int i=0; i<block_count; i++)
    {
        if(systemStartAddr[i] == '0')//可用盘块
        {
            if(sum == 0)//刚开始，设置开始盘块号
                startBlock = i;
            sum++;
            if(sum == blockSize)//连续盘块是否满足需求
            {
                //满足分配，置1
                for(int j=startBlock; j<startBlock+blockSize; j++)
                    systemStartAddr[j] = '1';
                return startBlock;
            }

        }
        else//已被使用,连续已经被打断
            sum = 0;
    }
    printf("not found such series memory Or memory is full\n");
    return -1;
}
//获得盘块的物理地址
char* getBlockAddr(int blockNum)
{
    return systemStartAddr + blockNum * block_szie; //偏移量单位为字节
}
//获得物理地址的盘块号
int getAddrBlock(char* addr)
{
    return (addr - systemStartAddr)/block_szie;
}
//释放盘块、
int releaseBlock(int blockNum, int blockSize)
{
    int endBlock = blockNum + blockSize;
    //修改位示图盘块的位置为0
    for(int i=blockNum; i<endBlock; i++)
        systemStartAddr[i] = '0';
    return 0;
}
 
 

 
 
2.文件管理
 首先说明全局变量 
 
dirTable* rootDirTable; //根目录
dirTable* currentDirTable;  //当前所在目录位置
char path[200]; //保存当前绝对路径
结构体定义可以见上面文件管理

 
 

 
 
1）创建文件:touch fileName size
 
创建文件的过程可以为：
 
为文件控制块申请空间->为文件数据申请空间->创建FCB控制块->在当前目录添加相关的目录项描述
 
 
//创建文件
int creatFile(char fileName[], int fileSize)
{
    //检测文件名字长度
    if(strlen(fileName) >= 59)
    {
        printf("file name too long\n");
        return -1;
    }
    //获得FCB的空间
    int FCBBlock = getBlock(1);
    if(FCBBlock == -1)
        return -1;
    //获取文件数据空间
    int FileBlock = getBlock(fileSize);
    if(FileBlock == -1)
        return -1;
    //创建FCB
    if(creatFCB(FCBBlock, FileBlock, fileSize) == -1)
        return -1;
    //添加到目录项
    if(addDirUnit(currentDirTable, fileName, 1, FCBBlock) == -1)
        return -1;

    return 0;
}
//创建FCB
int creatFCB(int fcbBlockNum, int fileBlockNum, int fileSize)
{
    //找到fcb的存储位置
    FCB* currentFCB = (FCB*) getBlockAddr(fcbBlockNum);
    currentFCB->blockNum = fileBlockNum;//文件数据起始位置
    currentFCB->fileSize = fileSize;//文件大小
    currentFCB->link = 1;//文件链接数
    currentFCB->dataSize = 0;//文件已写入数据长度
    currentFCB->readptr = 0;//文件读指针
    return 0;
}
//添加目录项
int addDirUnit(dirTable* myDirTable, char fileName[], int type, int FCBBlockNum)
{
    //获得目录表
    int dirUnitAmount = myDirTable->dirUnitAmount;
    //检测目录表示是否已满
    if(dirUnitAmount == dirTable_max_size)
    {
        printf("dirTables is full, try to delete some file\n");
        return -1;
    }

    //是否存在同名文件
    if(findUnitInTable(myDirTable, fileName) != -1)
    {
        printf("file already exist\n");
           return -1;
    }
    //构建新目录项
    dirUnit* newDirUnit = &myDirTable->dirs[dirUnitAmount];
    myDirTable->dirUnitAmount++;//当前目录表的目录项数量+1
    //设置新目录项内容
    strcpy(newDirUnit->fileName, fileName);
    newDirUnit->type = type;
    newDirUnit->startBlock = FCBBlockNum;

    return 0;
}
//从目录中查找目录项目
int findUnitInTable(dirTable* myDirTable, char unitName[])
{
    //获得目录表
    int dirUnitAmount = myDirTable->dirUnitAmount;
    int unitIndex = -1;
    for(int i=0; i<dirUnitAmount; i++)//查找目录项位置
       if(strcmp(unitName, myDirTable->dirs[i].fileName) == 0)
            unitIndex = i;
    return unitIndex;
}
 
 

 
 
2）删除文件:rm fileName 
删除文件的流程可以分为：
 
查找文件在当前目录的目录项描述内容->得到FCB的描述内容->释放FCB空间和文件数据空间->从目录表中删除文件的目录项
 
（也就是说，在这里其实只是把用户能得到文件的索引删除，而文件的内容在没有被覆盖之前依旧是存在的）
 

//删除文件
int deleteFile(char fileName[])
{
    //忽略系统的自动创建的父目录
    if(strcmp(fileName, "..") == 0)
    {
        printf("can't delete ..\n");
        return -1;
    }
    //查找文件的目录项位置
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    dirUnit myUnit = currentDirTable->dirs[unitIndex];
    //判断类型
    if(myUnit.type == 0)//目录
    {
        printf("not a file\n");
        return -1;
    }
    int FCBBlock = myUnit.startBlock;
    //释放内存
    releaseFile(FCBBlock);
    //从目录表中剔除
    deleteDirUnit(currentDirTable, unitIndex);
    return 0;
}
//释放文件内存
int releaseFile(int FCBBlock)
{
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    myFCB->link--;  //链接数减一
    //无链接，删除文件
    if(myFCB->link == 0)
    {
        //释放文件的数据空间
        releaseBlock(myFCB->blockNum, myFCB->fileSize);
    }
    //释放FCB的空间
    releaseBlock(FCBBlock, 1);
    return 0;
}
//删除目录项
int deleteDirUnit(dirTable* myDirTable, int unitIndex)
{
    //迁移覆盖
    int dirUnitAmount = myDirTable->dirUnitAmount;
    for(int i=unitIndex; i<dirUnitAmount-1; i++)
    {
        myDirTable->dirs[i] = myDirTable->dirs[i+1];
    }
    myDirTable->dirUnitAmount--;
    return 0;
}

 

 
 
 

 
 
3）目录的删除和创建
 
目录的创建和删除与文件的操作大致相同，创建目录时，目录表项的startBlock不是FCB而是指目录的存放位置，而且还要自动为其添加多一个父目录项“..”，用于跳转。删除目录时需要注意是否递归删除目录下的所有文件和目录。详请看最后的完整代码，这里不专门复述。 

 
 
4）切换目录: cd dirName
 
cd指令，主要就是让当前目录currentDirTable指向新的目录盘块地址就可以了，目录盘块地址可以在当前目录表的表项中找到。
 
 
//切换目录
int changeDir(char dirName[])
{
    //目录项在目录位置
    int unitIndex = findUnitInTable(currentDirTable, dirName);
    //不存在
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    if(currentDirTable->dirs[unitIndex].type == 1)
    {
        printf("not a dir\n");
        return -1;
    }
    //修改当前目录
    int dirBlock = currentDirTable->dirs[unitIndex].startBlock;
    currentDirTable = (dirTable*)getBlockAddr(dirBlock);
    //修改全局绝对路径path
    if(strcmp(dirName, "..") == 0)
    {
        //回退绝对路径
        int len = strlen(path);
        for(int i=len-2;i>=0;i--)
            if(path[i] == '\\')
            {
                path[i+1]='\0';
                break;
            }
    }else {
        strcat(path, dirName);
        strcat(path, "\\");
    }

    return 0;
}

 

 

 
5）读文件:read fileName size 
 
主要就是获得文件的初始地址，然后根据需要的读取长度size和当前的读指针进行输出，如果遇到文件尾则输出#，读写的单位都是字节
 
 
//读文件 read
int read(char fileName[], int length)
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    doRead(myFCB, length);
    return 0;
}
//执行读操作 
int doRead(FCB* myFCB, int length)
{
    //读数据
    int dataSize = myFCB->dataSize;
    char* data = (char*)getBlockAddr(myFCB->blockNum);
    //在不超出数据长度下，读取指定长度的数据
    for(int i=0; i<length && myFCB->readptr < dataSize; i++, myFCB->readptr++)
    {
        printf("%c", *(data+myFCB->readptr));
    }
    if(myFCB->readptr == dataSize)//读到文件末尾用#表示
        printf("#");
    //换行美观
    printf("\n");
    return 0;
}
 reread就是先把读指针readptr置为0，然后执行读操作。 
 

 
 
6）写文件操作:write fileName content
 
和读文件差不多，不过是根据当前文件的数据长度，在文件末尾给文件以字节的形式赋值上输入的content内容，数据长度不能超过文件长度
 
 
//写文件，从末尾写入 write
int write(char fileName[], char content[])
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    doWrite(myFCB, content);
    return 0;
}
//执行写操作
int doWrite(FCB* myFCB, char content[])
{
    int contentLen = strlen(content);
    int fileSize = myFCB->fileSize * block_szie;
    char* data = (char*)getBlockAddr(myFCB->blockNum);
    //在不超出文件的大小的范围内写入
    for(int i=0; i<contentLen && myFCB->dataSize<fileSize; i++, myFCB->dataSize++)
    {
        *(data+myFCB->dataSize) = content[i];
    }
    if(myFCB->dataSize == fileSize)
        printf("file is full,can't write in\n");
    return 0;
}

 
7）展示目录下所有文件:ls 
 
对目录表进行遍历，同时根据文件类型做出不同的输出就可以了
 
 
//展示当前目录 ls
void showDir()
{
    int unitAmount = currentDirTable->dirUnitAmount;
    printf("total:%d\n", unitAmount);
    printf("name\ttype\tsize\tFCB\tdataStartBlock\n");
    //遍历所有表项
    for(int i=0; i<unitAmount; i++)
    {
        //获取目录项
        dirUnit unitTemp = currentDirTable->dirs[i];
        printf("%s\t%d\t", unitTemp.fileName, unitTemp.type);
        //该表项是文件，继续输出大小和起始盘块号
        if(unitTemp.type == 1)
        {
            int FCBBlock = unitTemp.startBlock;
            FCB* fileFCB = (FCB*)getBlockAddr(FCBBlock);
            printf("%d\t%d\t%d\n", fileFCB->fileSize, FCBBlock, fileFCB->blockNum);
        }else{
            int dirBlock = unitTemp.startBlock;
            dirTable* myTable = (dirTable*)getBlockAddr(dirBlock);
            printf("%d\t%d\n",myTable->dirUnitAmount, unitTemp.startBlock);
        }
    }
}
 
 

 
 
8）FileOperate.cpp 
几乎全部的内容都在上面做了阐述了
 

#include"FileOperate.h"

#include<string.h>
#include<stdio.h>



dirTable* rootDirTable; //根目录
dirTable* currentDirTable;  //当前位置
char path[200]; //保存当前绝对路径


//初始化根目录
void initRootDir()
{
    //分配一个盘块空间给rootDirTable
    int startBlock = getBlock(1);
    if(startBlock == -1)
        return;
    rootDirTable = (dirTable*)getBlockAddr(startBlock);
    rootDirTable->dirUnitAmount = 0;
    //将自身作为父级目录
    //addDirUnit(rootDirTable, "..", 0, startBlock);

    currentDirTable = rootDirTable;
    //初始化初始绝对路径
    path[0]='\\';
    path[1]='\0';
}
//获得绝对路径
char* getPath()
{
    return path;
}
//展示当前目录 ls
void showDir()
{
    int unitAmount = currentDirTable->dirUnitAmount;
    printf("total:%d\n", unitAmount);
    printf("name\ttype\tsize\tFCB\tdataStartBlock\n");
    //遍历所有表项
    for(int i=0; i<unitAmount; i++)
    {
        //获取目录项
        dirUnit unitTemp = currentDirTable->dirs[i];
        printf("%s\t%d\t", unitTemp.fileName, unitTemp.type);
        //该表项是文件，继续输出大小和起始盘块号
        if(unitTemp.type == 1)
        {
            int FCBBlock = unitTemp.startBlock;
            FCB* fileFCB = (FCB*)getBlockAddr(FCBBlock);
            printf("%d\t%d\t%d\n", fileFCB->fileSize, FCBBlock, fileFCB->blockNum);
        }else{
            int dirBlock = unitTemp.startBlock;
            dirTable* myTable = (dirTable*)getBlockAddr(dirBlock);
            printf("%d\t%d\n",myTable->dirUnitAmount, unitTemp.startBlock);
        }
    }
}
//切换目录 cd
int changeDir(char dirName[])
{
    //目录项在目录位置
    int unitIndex = findUnitInTable(currentDirTable, dirName);
    //不存在
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    if(currentDirTable->dirs[unitIndex].type == 1)
    {
        printf("not a dir\n");
        return -1;
    }
    //修改当前目录
    int dirBlock = currentDirTable->dirs[unitIndex].startBlock;
    currentDirTable = (dirTable*)getBlockAddr(dirBlock);
    //修改全局绝对路径
    if(strcmp(dirName, "..") == 0)
    {
        //回退绝对路径
        int len = strlen(path);
        for(int i=len-2;i>=0;i--)
            if(path[i] == '\\')
            {
                path[i+1]='\0';
                break;
            }
    }else {
        strcat(path, dirName);
        strcat(path, "\\");
    }

    return 0;
}
//修改文件名或者目录名 mv
int changeName(char oldName[], char newName[])
{
    int unitIndex = findUnitInTable(currentDirTable, oldName);
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    strcpy(currentDirTable->dirs[unitIndex].fileName, newName);
    return 0;
}


//******************创建和删除文件
//创建文件 touch
int creatFile(char fileName[], int fileSize)
{
    //检测文件名字长度
    if(strlen(fileName) >= 59)
    {
        printf("file name too long\n");
        return -1;
    }
    //获得FCB的空间
    int FCBBlock = getBlock(1);
    if(FCBBlock == -1)
        return -1;
    //获取文件数据空间
    int FileBlock = getBlock(fileSize);
    if(FileBlock == -1)
        return -1;
    //创建FCB
    if(creatFCB(FCBBlock, FileBlock, fileSize) == -1)
        return -1;
    //添加到目录项
    if(addDirUnit(currentDirTable, fileName, 1, FCBBlock) == -1)
        return -1;

    return 0;
}
//创建目录 mkdir
int creatDir(char dirName[])
{
    if(strlen(dirName) >= 59)
    {
        printf("file name too long\n");
        return -1;
    }
    //为目录表分配空间
    int dirBlock = getBlock(1);
    if(dirBlock == -1)
        return -1;
    //将目录作为目录项添加到当前目录
    if(addDirUnit(currentDirTable, dirName, 0, dirBlock) == -1)
        return -1;
    //为新建的目录添加一个到父目录的目录项
    dirTable* newTable = (dirTable*)getBlockAddr(dirBlock);
    newTable->dirUnitAmount = 0;
    char parent[] = "..";
    if(addDirUnit(newTable, parent, 0, getAddrBlock((char*)currentDirTable)) == -1)
        return -1;
    return 0;
}
//创建FCB
int creatFCB(int fcbBlockNum, int fileBlockNum, int fileSize)
{
    //找到fcb的存储位置
    FCB* currentFCB = (FCB*) getBlockAddr(fcbBlockNum);
    currentFCB->blockNum = fileBlockNum;//文件数据起始位置
    currentFCB->fileSize = fileSize;//文件大小
    currentFCB->link = 1;//文件链接数
    currentFCB->dataSize = 0;//文件已写入数据长度
    currentFCB->readptr = 0;//文件读指针
    return 0;
}
//添加目录项
int addDirUnit(dirTable* myDirTable, char fileName[], int type, int FCBBlockNum)
{
    //获得目录表
    int dirUnitAmount = myDirTable->dirUnitAmount;
    //检测目录表示是否已满
    if(dirUnitAmount == dirTable_max_size)
    {
        printf("dirTables is full, try to delete some file\n");
        return -1;
    }

    //是否存在同名文件
    if(findUnitInTable(myDirTable, fileName) != -1)
    {
        printf("file already exist\n");
           return -1;
    }
    //构建新目录项
    dirUnit* newDirUnit = &myDirTable->dirs[dirUnitAmount];
    myDirTable->dirUnitAmount++;//当前目录表的目录项数量+1
    //设置新目录项内容
    strcpy(newDirUnit->fileName, fileName);
    newDirUnit->type = type;
    newDirUnit->startBlock = FCBBlockNum;

    return 0;
}
//删除文件 rm
int deleteFile(char fileName[])
{
    //忽略系统的自动创建的父目录
    if(strcmp(fileName, "..") == 0)
    {
        printf("can't delete ..\n");
        return -1;
    }
    //查找文件的目录项位置
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    dirUnit myUnit = currentDirTable->dirs[unitIndex];
    //判断类型
    if(myUnit.type == 0)//目录
    {
        printf("not a file\n");
        return -1;
    }
    int FCBBlock = myUnit.startBlock;
    //释放内存
    releaseFile(FCBBlock);
    //从目录表中剔除
    deleteDirUnit(currentDirTable, unitIndex);
    return 0;
}
//释放文件内存
int releaseFile(int FCBBlock)
{
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    myFCB->link--;  //链接数减一
    //无链接，删除文件
    if(myFCB->link == 0)
    {
        //释放文件的数据空间
        releaseBlock(myFCB->blockNum, myFCB->fileSize);
    }
    //释放FCB的空间
    releaseBlock(FCBBlock, 1);
    return 0;
}
//删除目录项
int deleteDirUnit(dirTable* myDirTable, int unitIndex)
{
    //迁移覆盖
    int dirUnitAmount = myDirTable->dirUnitAmount;
    for(int i=unitIndex; i<dirUnitAmount-1; i++)
    {
        myDirTable->dirs[i] = myDirTable->dirs[i+1];
    }
    myDirTable->dirUnitAmount--;
    return 0;
}
//删除目录 rmdir
int deleteDir(char dirName[])
{
    //忽略系统的自动创建的父目录
    if(strcmp(dirName, "..") == 0)
    {
        printf("can't delete ..\n");
        return -1;
    }
    //查找文件
    int unitIndex = findUnitInTable(currentDirTable, dirName);
    if(unitIndex == -1)
    {
        printf("file not found\n");
        return -1;
    }
    dirUnit myUnit = currentDirTable->dirs[unitIndex];
    //判断类型
    if(myUnit.type == 0)//目录
    {
        deleteFileInTable(currentDirTable, unitIndex);
    }else {
        printf("not a dir\n");
        return -1;
    }
    //从目录表中剔除
    deleteDirUnit(currentDirTable, unitIndex);
    return 0;
}
//删除文件/目录项
int deleteFileInTable(dirTable* myDirTable, int unitIndex)
{
   //查找文件
    dirUnit myUnit = myDirTable->dirs[unitIndex];
    //判断类型
    if(myUnit.type == 0)//目录
    {
        //找到目录位置
        int FCBBlock = myUnit.startBlock;
        dirTable* table = (dirTable*)getBlockAddr(FCBBlock);
        //递归删除目录下的所有文件
        printf("cycle delete dir %s\n", myUnit.fileName);
        int unitCount = table->dirUnitAmount;
        for(int i=1; i<unitCount; i++)//忽略“..”
        {
            printf("delete %s\n", table->dirs[i].fileName);
            deleteFileInTable(table, i);
        }
        //释放目录表空间
        releaseBlock(FCBBlock, 1);
    }else {//文件
        //释放文件内存
        int FCBBlock = myUnit.startBlock;
        releaseFile(FCBBlock);
    }
    return 0;
}



//**********************读写操作
//读文件 read
int read(char fileName[], int length)
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    doRead(myFCB, length);
    return 0;
}
//重新读文件 reread
int reread(char fileName[], int length)
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    myFCB->readptr = 0;
    doRead(myFCB, length);

    return 0;
}
//执行读操作
int doRead(FCB* myFCB, int length)
{
    //读数据
    int dataSize = myFCB->dataSize;
    char* data = (char*)getBlockAddr(myFCB->blockNum);
    //在不超出数据长度下，读取指定长度的数据
    for(int i=0; i<length && myFCB->readptr < dataSize; i++, myFCB->readptr++)
    {
        printf("%c", *(data+myFCB->readptr));
    }
    if(myFCB->readptr == dataSize)//读到文件末尾用#表示
        printf("#");
    //换行美观
    printf("\n");
    return 0;
}
//写文件，从末尾写入 write
int write(char fileName[], char content[])
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    doWrite(myFCB, content);
    return 0;
}
//重新写覆盖 rewrite
int rewrite(char fileName[], char content[])
{
    int unitIndex = findUnitInTable(currentDirTable, fileName);
    if(unitIndex == -1)
    {
        printf("file no found\n");
        return -1;
    }
    //控制块
    int FCBBlock = currentDirTable->dirs[unitIndex].startBlock;
    FCB* myFCB = (FCB*)getBlockAddr(FCBBlock);
    //重设数据块
    myFCB->dataSize = 0;
    myFCB->readptr = 0;

    doWrite(myFCB, content);
    return 0;
}
//执行写操作
int doWrite(FCB* myFCB, char content[])
{
    int contentLen = strlen(content);
    int fileSize = myFCB->fileSize * block_szie;
    char* data = (char*)getBlockAddr(myFCB->blockNum);
    //在不超出文件的大小的范围内写入
    for(int i=0; i<contentLen && myFCB->dataSize<fileSize; i++, myFCB->dataSize++)
    {
        *(data+myFCB->dataSize) = content[i];
    }
    if(myFCB->dataSize == fileSize)
        printf("file is full,can't write in\n");
    return 0;
}



//从目录中查找目录项目
int findUnitInTable(dirTable* myDirTable, char unitName[])
{
    //获得目录表
    int dirUnitAmount = myDirTable->dirUnitAmount;
    int unitIndex = -1;
    for(int i=0; i<dirUnitAmount; i++)//查找目录项位置
       if(strcmp(unitName, myDirTable->dirs[i].fileName) == 0)
            unitIndex = i;
    return unitIndex;
}


 

 
 工程代码链接（含有exe可直接运行）：
FileSystem

 
 

 
 
 

 

如何实现一个文件系统
   
 
摘要
   
 
本章目的是分析在Linux系统中如何实现新的文件系统。在介绍文件系统具体实现前先介绍文件系统的概念和作用，抽象出了文件系统概念模型。熟悉文件系统的内涵后，我们再近一步讨论Linux系统中和文件系统的特殊风格和具体文件系统在Linux中组成结构，逐步为读者勾画出Linux中文件系统工作的全景图。最后在事例部分，我们将以romfs文件系统作实例分析实现文件系统的普遍步骤。
   
 
什么是文件系统
   
 
别混淆“文件系统”
   
 
首先要谈的概念就是什么是文件系统，它的作用到底是什么。
   
 
文件系统的概念虽然许多人都认为是再清晰不过的了，但其实我们往往在谈论中或多或少地夸大或片缩小了它的实际概念（至少我时常混淆），或者说，有时借用了其它概念，有时说的又不够全面。
   
 
比如在操作系统中，文件系统这个术语往往既被用来描述磁盘中的物理布局，比如有时我们说磁盘中的“文件系统”是EXT2或说把磁盘格式化成FAT32格式的“文件系统”等——这时所说的“文件系统”是指磁盘数据的物理布局格式；另外，文件系统也被用来描述内核中的逻辑文件结构，比如有时说的“文件系统”的接口或内核支持Ext2等“文件系统”——这时所说的文件系统都是内存中的数据组织结构而并非磁盘物理布局（后面我们将称呼它为逻辑文件系统）；还有些时候说“文件系统”负责管理用户读写文件——这时所说的“文件系统”往往描述操作系统中的“文件管理系统”，也就是文件子系统。
   
 
虽然上面我们列举了混用文件系统的概念的几种情形，但是却也不能说上述说法就是错误的，因为文件系统概念本身就囊括众多概念，几乎可以说在操作系统中自内存管理、系统调度到I/O系统、设备驱动等各个部分都和文件系统联系密切，有些部分和文件系统甚至未必能明确划分——所以不能只知道文件系统是系统中数据的存储结构，一定要全面认识文件系统在操作系统中的角色，才能具备自己开发新文件系统的能力。
   
 
文件系统的体系结构
   
 
为了澄清文件系统的概念，必须先来看看文件系统在操作系统中处于何种角色，分析文件系统概念的内含外延。我们先抛开Linux文件系统的实例，而来看看操作系统中文件系统的普遍体系结构，从而增强对文件系统的理论认识。
   
 
下面以软件组成的结构图[1][1]的方式描述文件系统所涉及的内容。
 

   
    
   
 

  
   
    
    
   
   
    
     
    
   
  
 
    
 
     
 
用户程序
            
 
 
     

       
         
       
 
    
 
 

 
  
  
 
      
 
       
 
                访问方法
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
逻辑I/O
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
              基础I/O监督
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
                物理I/O
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
                设备驱动
               
 
 
       

         
           
         
 
      
 
 
 





 
 
  
  
  
  
  
  
  
  
  
  
  
  
 
 
 


 
 

  
    
  
 
                    图 1 ： 文件系统体系结构层次图
   
 
针对各层做以简要分析：
   
 
1.首先我们来分析最低层——设备驱动层，该层负责与外设——磁盘等——通讯。文件系统都需要和存储设备打交道，而系统操作外设离不开驱动程序。所以内核对文件的最后操作行为就是调用设备驱动程序完成从主存（内存）到辅存（磁盘）的数据传输。
   
 
文件系统相关的多数设备都属于块设备，常见的块设备驱动程序有磁盘驱动，光驱驱动等，之所以称它们为块设备，一个原因是它们读写数据都是成块进行的，但是更重要的原因是它们管理的数据能够被随机访问——不需要向字符设备那样必须顺序访问。
   
 
2.设备驱动层的上一层是物理I/O层，该层主要作为计算机外部环境和系统的接口，负责系统和磁盘交换数据块。它要知道据块在磁盘中存储位置，也要知道文件数据块在内存缓冲中的位置，另外它不需要了解数据或文件的具体结构。可以看到这层最主要的工作是标识别磁盘扇区和内存缓冲块[2][2]之间的映射关系。
   
 
3.再上层是基础I/O监督层，该层主要负责选择文件 I/O需要的设备，调度磁盘请求等工作，另外分配I/O缓冲和磁盘空间也在该层完成。由于块设备需要随机访问数据，而且对速度响应要求较高，所以操作系统不能向对字符设备那样简单、直接地发送读写请求，而必须对读写请求重新优化排序，以能节省磁盘寻址时间，另外也必须对请求提交采取异步调度（尤其写操作）的方式进行。总而言之，内核对必须管理块设备请求，而这项工作正是由该层负责的。
   
 
4.倒数第二层是逻辑I/O层，该层允许用户和应用程序访问记录。它提供了通用的记录（record）I/O操作，同时还维护基本文件数据。由于为了方便用户操作和管理文件内容，文件内容往往被组织成记录形式，所以操作系统为操作文件记录提供了一个通用逻辑操作层。
   
 
5.和用户最靠近的是访问方法层，该层提供了一个从用户空间到文件系统的标准接口，不同的访问方法反映了不同的文件结构，也反映了不同的访问数据和处理数据方法。这一层我们可以简单地理解为文件系统给用户提供的访问接口——不同的文件格式（如顺序存储格式、索引存储格式、索引顺序存储格式和哈希存储格式等）对应不同的文件访问方法。该层要负责将用户对文件结构的操作转化为对记录的操作。
   
 
文件处理流程
   
 
对比上面的层次图我们再来分析一下数据流的处理过程，加深对文件系统的理解。
   
 
假如用户或应用程序操作文件（创建/删除），首先需要通过文件系统给用户空间提供的访问方法层进入文件系统，接着由使用逻辑I/O层对记录进行给定操作，然后记录将被转化为文件块，等待和磁盘交互。这里有两点需要考虑——第一，磁盘管理（包括再磁盘空闲区分配文件和组织空闲区）；第二，调度块I/O请求——这些由基础I/O监督层的工作。再下来文件块被物理I/O层传递给磁盘驱动程序，最后磁盘驱动程序真正把数据写入具体的扇区。至此文件操作完毕。
   
 
当然上面介绍的层次结构是理想情况下的理论抽象，实际文件系统并非一定要按照上面的层次或结构组织，它们往往简化或合并了某些层的功能（比如Linux文件系统因为所有文件都被看作字节流，所以不存在记录，也就没有必要实现逻辑I/O层，进而也不需要在记录相关的处理）。但是大体上都需要经过类似处理。如果从处理对象上和系统独立性上划分，文件系统体系结构可以被分为两大部分：——文件管理部分和操作系统I/O部分。文件管理系统负责操作内存中文件对象，并按文件的逻辑格式将对文件对象的操作转化成对文件块的操作；而操作系统I/O部分负责内存中的块与物理磁盘中的数据交换。
   
 
数据表现形式在文件操作过程中也经历了几种变化：在用户访问文件系统看到的是字节序列，而在字节序列被写入磁盘时看到的是内存中文件块（在缓冲中），在最后将数据写入磁盘扇区时看到的是磁盘数据块[3][3]。
   
 
本文所说的实现文件系统主要针对最开始讲到第二种情况——内核中的逻辑文件结构（但其它相关的文件管理系统和文件系统磁盘存储格式也必须了解），我们用数据处理流图来分析一下逻辑文件系统主要功能和在操作系统中所处的地位。
   
 

  
    
  
 

  
   
    
     
    
   
  
 
    
 
     
 
用户程序
            
 
 
     

       
         
       
 
    
 
 

 
  
  
 
      
 
       
 
 I/O调度层
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
系统调用
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
文件系统接口
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
物理存储布局管理
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
 设备驱动
              
 
 
       

         
           
         
 
      
 
 
 


 
 
  
  
 
      
 
       
 
逻辑文件系统
              
 
 
       

         
           
         
 
      
 
 
 


 


 
  
  
 
      
 
       
 
用户程序
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
 I/O调度层
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
文件系统接口
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
物理存储布局管理
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
 设备驱动
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
 磁盘设备
              
 
 
       

         
           
         
 
      
 
 
 


 
 
  
  
 
      
 
       
 
逻辑文件系统
              
 
 
       

         
           
         
 
      
 
 
 


 


 


 


 


 


 




 
 
                   图 2 文件系统操作流程
   
 
其中文件系统接口与物理布局管理是逻辑文件系统要负责的主要功能。
   
 
l  文件系统接口为用户提供对文件系统的操作，比如open、close、read、write和访问控制等，同时也负责处理文件的逻辑结构。
   
 
l  物理存储布局管理，如同虚拟内存地址转化为物理内存地址时，必须处理段页结构一样，逻辑文件结构必须转化到物理磁盘中，所以也要处理物理分区和扇区的实际存储位置，分配磁盘空间和内存中的缓冲也要在这里被处理。
   
 
       所以说要实现文件系统就必须提供上面提到的两种功能，缺一不可。
   
 
在了解了文件系统的功能后，我们针对Linux操作系统分析具体文件系统如何工作，进而掌握实现一个文件系统需要的步骤。
   
 
Linux 文件系统组成结构
   
 
Linux 文件系统的结构除了我们上面所提到的概念结构外，最主要有两个特点，一个是文件系统抽象出了一个通用文件表示层——虚拟文件系统或称做VFS。另外一个重要特点是它的文件系统支持动态安装（或说挂载等），大多数文件系统都可以作为根文件系统的叶子接点被挂在到根文件目录树下的子目录上。另外Linux系统在文件读写的I/O操作上也采取了一些先进技术和策略。
   
 
我们先从虚拟文件系统入手分析linux文件系统的特性，然后介绍有关文件系统的安装、注册和读写等概念。 
     
 
虚拟文件系统
   
 
虚拟文件系统为用户空间程序提供了文件系统接口。系统中所有文件系统不但依赖VFS共存，而且也依靠VFS系统协同工作。通过虚拟文件系统我们可以利用标准的UNIX文件系统调用对不同介质上的不同文件系统进行读写操作[4][4]。
   
 
虚拟文件系统的目的是为了屏蔽各种各样不同文件系统的相异操作形式，使得异构的文件系统可以在统一的形式下，以标准化的方法访问、操作。实现虚拟文件系统利用的主要思想是引入一个通用文件模型——该模型抽象出了文件系统的所有基本操作(该通用模型源于Unix风格的文件系统)，比如读、写操作等。同时实际文件系统如果希望利用虚拟文件系统，既被虚拟文件系统支持，也必须将自身的诸如，“打开文件”、“读写文件”等操作行为以及“什么是文件”，“什么是目录”等概念“修饰”成虚拟文件系统所要求的（定义的）形式，这样才能够被虚拟文件系统支持和使用。
   
 
我们可以借用面向对象的一些思想来理解虚拟文件系统，虚拟文件系统好比一个抽象类或接口，它定义（但不实现）了文件系统最常见的操作行为。而具体文件系统好比是具体类，它们是特定文件系统的实例。具体文件系统和虚拟文件系统的关系类似具体类继承抽象类或实现接口。而在用户看到或操作的都是抽象类或接口，但实际行为却发生在具体文件系统实例上。至于如何将对虚拟文件系统的操作转化到对具体文件系统的实例，就要通过注册具体文件系统到系统，然后再安装具体文件系统才能实现转化，这点可以想象成面向对象中的多态概念。
   
 
我们个实举例来说明具体文件系统如何通过虚拟文件系统协同工作。
   
 
例如：假设一个用户输入以下shell命令：
   
 
$ cp /hda/test1 /removable/test2
    
 
其中 /removable是MS-DOS磁盘的一个安装点，而 /hda 是一个标准的第二扩展文件系统（ Ext2）的目录。cp命令不用了解test1或test2的具体文件系统，它所看到和操作的对象是VFS。cp首先要从ext3文件系统读出test1文件，然后写入MS-DOS文件系统中的test2。VFS会将找到ext3文件系统实例的读方法，对test1文件进行读取操作；然后找到MS-DOS（在Linux中称VFAT）文件系统实例的写方法，对test2文件进行写入操作。可以看到 VFS是读写操作的统一界面，只要具体文件系统符合VFS所要求的接口，那么就可以毫无障碍地透明通讯了。
   
 
下图给出Linux系统中VFS文件体统和具体文件系统能的层次示意图
   
 

  
   
    
   
   
    
     
      
     
    
   
  
 
    
 
     
 
VFS
             
 
 
     

       
         
       
 
    
 
 

 
  
  
 
      
 
       
 
Ext2
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
romfs
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
JFS
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
msdos
               
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
内存缓冲区
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
 
      
 
       
 
I/O驱动driver 
               
 
 
       

         
           
         
 
      
 
 
 


 


 


 


 


 


 


 


 


 


 
  
  
 
      
 
       
 
用户
              
 
 
       

         
           
         
 
      
 
 
 


 




 
 
图3 linux系统中VFS和具体文件系统关系图 
 

     
      
     
 
Unix风格的文件系统
   
 
虚拟文件系统的通用模型源于Unix风格的文件系统，所谓Unix风格是指Unix传统上文件系统传统上使用了四种和文件系统相关的抽象概念：文件(file)、目录项(dentry)、索引节点(inode)和安装点(mount point)。
   
 
1.文件——在Unix中的文件都被看做是一有序字节串，它们都有一个方便用户或系统识别的名称。另外典型的文件操作有读、写、创建和删除等。
   
 
2.目录项——不要和目录概念搞混淆，在Linux中目录被看作文件。而目录项是文件路径中的一部分。一个文件路径的例子是“/home/wolfman/foo”——根目录是/，目录home,wolfman和文件foo都是目录项。
   
 
3.索引节点——Unix系统将文件的相关信息（如访问控制权限、大小、拥有者、创建时间等等信息），有时被称作文件的元数据（也就是说，数据的数据）被存储在一个单独的数据结构中，该结构被称为索引节点(inode)。
   
 
4.安装点——在Unix中，文件系统被安装在一个特定的安装点上，所有的已安装文件系统都作为根文件系统树中的叶子出现在系统中。
   
 
上述概念是Unix文件系统的逻辑数据结构，但相应的Unix文件系统（Ext2等）磁盘布局也实现了部分上述概念，比如文件信息（文件数据元）存储在磁盘块中的索引节点上。当文件被载如内存时，内核需要使用磁盘块中的索引点来装配内存中的索引接点。类似行为还有超级块信息等。
   
 
对于非Unix风格文件系统，如FAT或NTFS，要想能被VFS支持，它们的文件系统代码必须提供这些概念的虚拟形式。比如，即使一个文件系统不支持索引节点，它也必须在内存中装配起索引节点结构体——如同本身固有一样。或者，如果一个文件系统将目录看作是一种特殊对象，那么要想使用VFS，必须将目录重新表示为文件形式。通常，这种转换需要在使用现场引入一些特殊处理，使得非Unix文件系统能够兼容Unix文件系统的使用规则和满足VFS的需求。通过这些处理，非Unix文件系统便可以和VFS一同工作了，是性能上多少会受一些影响[5][5]。这点很重要，我们实现自己文件系统时必须提供（模拟）Unix风格文件系统的抽象概念。
   
 

  
    
  
 
Linux文件系统中使用的对象
   
 
Linux文件系统的对象就是指一些数据结构体，之所以称它们是对象，是因为这些数据结构体不但包含了相关属性而且还包含了操作自身结构的函数指针，这种将数据和方法进行封装的思想和面向对象中对象概念一致，所以这里我们就称它们是对象。
   
 
Linux文件系统使用大量对象，我们简要分析以下VFS相关的对象，和除此还有和进程相关的一些其它对象。
   
 
VFS相关对象
   
 
这里我们不展开讨论每个对象，仅仅是为了内容完整性，做作简要说明。
   
 
VFS中包含有四个主要的对象类型，它们分别是：
   
 
l  超级块对象，它代表特定的已安装文件系统。
   
 
l  索引节点对象，它代表特定文件。
   
 
l  目录项对象，它代表特定的目录项。
   
 
l  文件对象，它代表和进程打开的文件。
   
 
每个主要对象中都包含一个操作对象，这些操作对象描述了内核针对主要对象可以使用的方法。最主要的几种操作对象如下：
   
 
super_operations对象，其中包括内核针对特定文件系统所能调用的方法，比如read_inode()和sync_fs()方法等。
   
 
inode_operations对象，其中包括内核针对特定文件所能调用的方法，比如create()和link()方法等。
   
 
dentry_operations对象，其中包括内核针对特定目录所能调用的方法，比如d_compare()和d_delete()方法等。
   
 
file对象，其中包括，进程针对已打开文件所能调用的方法，比如read()和write()方法等。
   
 
除了上述的四个主要对象外,VFS还包含了许多对象，比如每个注册文件系统都是由file_system_type对象表示——描述了文件系统及其能力（如比如ext3或XFS）；另外每一个安装点也都利用vfsmount对象表示——包含了关于安装点的信息，如位置和安装标志等。
   
 
其它VFS对象
   
 
系统上的每一进程都有自己的打开文件，根文件系统，当前工作目录，安装点等等。另外还有几个数据结构体将VFS层和文件的进程紧密联系，它们分别是：file_struct 和fs_struct
    
 
file_struct结构体由进程描述符中的files项指向。所有包含进程的信息和它的文件描述符都包含在其中。第二个和进程相关的结构体是fs_struct。该结构由进程描述符的fs项指向。它包含文件系统和进程相关的信息。每种结构体的详细信息不在这里说明了。
   
 
缓存对象
   
 
除了上述一些结构外，为了缩短文件操作响应时间，提高系统性能，Linux系统采用了许多缓存对象，例如目录缓存、页面缓存和缓冲缓存（已经归入了页面缓存），这里我们对缓存做简单介绍。
   
 
页高速缓存（cache）是 Linux内核实现的一种主要磁盘缓存。其目的是减少磁盘的I/O操作，具体的讲是通过把磁盘中的数据缓存到物理内存中去，把对磁盘的I/O操作变为对物理内存的I/O操作。页高速缓存是由RAM中的物理页组成的，缓存中每一页都对应着磁盘中的多个块。每当内核开始执行一个页I/O操作时（通常是对普通文件中页大小的块进行磁盘操作），首先会检查需要的数据是否在高速缓存中，如果在，那么内核就直接使用高速缓存中的数据，从而避免了访问磁盘。
   
 
但我们知道文件系统只能以每次访问数个块的形式进行操作。内核执行所有磁盘操作都必须根据块进行，一个块包含一个或多个磁盘扇区。为此，内核提供了一个专门结构来管理缓冲buffer_head。缓冲头[6][6]的目的是描述磁盘扇区和物理缓冲之间的映射关系和做I/O操作的容器。但是缓冲结构并非独立存在，而是被包含在页高速缓存中，而且一个页高速缓存可以包含多个缓冲。我们将在文件后面的文件读写部分看到数据如何被从磁盘扇区读入页高速缓存中的缓冲中的。
   
 
    
   
 
文件系统的注册和安装
   
 
使用文件系统前必须对文件系统进行注册和安装，下面分别对这两种行为做简要介绍。
   
 
文件系统的注册
   
 
VFS要想能将自己定义的接口映射到实际文件系统的专用方法上，必须能够让内核识别实际的文件系统，实际文件系统通过将代表自身属性的文件类型对象(file_system_type)注册(通过register_filesystem()函数)到内核，也就是挂到内核中的文件系统类型链表上，来达到使文件系统能被内核识别的目的。反过来内核也正是通过这条链表来跟踪系统所支持的各种文件系统的。
   
 
我们简要分析一下注册步骤：
   
 
struct file_system_type {
    
 
       const char *name;                                      /*文件系统的名字*/
    
 
    int fs_flags;                                              /*文件系统类型标志*/
    
 
/*下面的函数用来从磁盘中读取超级块*/
    
 
       struct super_block * (*read_super)  (struct file_system_type *, int,
    
 
                                   const char *, void *);
    
 
       struct file_system_type * next;                    /*链表中下一个文件系统类型*/
    
 
       struct list_head fs_supers;                           /*超级块对象链表*/
    
 
};
    
 
其中最重要的一项是read_super()函数，它用来从磁盘上读取超级块，并且当文件系统被装载时，在内存中组装超级块对象。要实现一个文件系统首先需要实现的结构体便是file_system_type结构体。
   
 
注册文件系统只能保证文件系统能被系统识别，但此刻文件系统尚不能使用，因为它还没有被安装到特定的安装点上。所以在使用文件系统前必须将文件系统安装到安装点上。
   
 
文件系统被实际安装时，将在安装点创建一个vfsmount结构体。该结构体用代表文件系统的实例——换句话说，代表一个安装点。
   
 
vfsmount结构被定义在<linux/mount.h>中，下面是具体结构
   
 
―――――――――――――――――――――――――――――――――――――――
    
 
struct vfsmount
    
 
{
    
 
       struct list_head mnt_hash;            /*哈希表*/
    
 
       struct vfsmount *mnt_parent;              /*父文件系统*/
    
 
       struct dentry *mnt_mountpoint;    /*安装点的目录项对象*/
    
 
       struct dentry *mnt_root;               /*该文件系统的根目录项对象*/
    
 
       struct super_block *mnt_sb;         /*该文件系统的超级块*/
    
 
       struct list_head mnt_mounts;        /*子文件系统链表*/
    
 
       struct list_head mnt_child;            /*和父文件系统相关的子文件系统*/
    
 
       atomic_t mnt_count;                    /*使用计数*/
    
 
       int mnt_flags;                      /*安装标志*/
    
 
       char *mnt_devname;             /*设备文件名字*/
    
 
       struct list_head mnt_list;              /*描述符链表*/
    
 
};
    
 
――――――――――――――――――――――――――――――――――――――
    
 
文件系统如果仅仅注册，那么还不能被用户使用。要想使用它还必须将文件系统安装到特定的安装点后才能工作。下面我们接着介绍文件系统的安装[7][7]过程。
   
 
安装过程
   
 
用户在用户空间调用mount()命令——指定安装点、安装的设备、安装类型等——安装指定文件系统到指定目录。mount()系统调用在内核中的实现函数为sys_mount(),该函数调用的主要例程是do_mount()，它会取得安装点的目录项对象，然后调用do_add_mount()例程。
   
 
   do_add_mount()函数主要做的是首先使用do_kern_mount()函数创建一个安装点，再使用graft_tree（）将安装点作为叶子与根目录树挂接起来。
   
 
   整个安装过程中最核心的函数就是do_kern_mount()了，为了创建一个新安装点（vfsmount）,该函数需要做一下几件事情：
   
 
l  1     检查安装设备的权利，只有root权限才有能力执行该操作。
   
 
l  2     Get_fs_type()在文件链表中取得相应文件系统类型（注册时被填加到练表中）。
   
 
l  3     Alloc_vfsmnt()调用slab分配器为vfsmount结构体分配存储空间，并把它的地址存放在mnt局部变量中。
   
 
l  4     初始化mnt->mnt_devname域
   
 
l  5     分配新的超级块并初始化它。do_kern_mount( )检查file_system_type描述符中的标志以决定如何进行如下操作：根据文件系统的标志位，选择相应的方法读取超级块(比如对Ext2,romfs这类文件系统调用get_sb_dev()；对于这种没有实际设备的虚拟文件系统如 ramfs调用get_sb_nodev())——读取超级块最终要使用文件系统类型中的read_super方法。
   
 
    安装过程做的最主要工作是创建安装点对象，挂接给定文件系统到根文件系统的指定接点下，然后初始化超级快对象，从而获得文件系统基本信息和相关操作方法(比如读取系统中某个inode的方法)。
   
 
  
    
 
总而言之，注册过程是告之内核给定文件系统存在于系统内；而安装是请求内核对给定文件系统进行支持，使文件系统真正可用。
   
 
文件系统的读写
   
 
要自己创建文件系统必须知道文件系统需要那些操作，各种操作的功能范围，所以我们下面内容就是分析Linux文件系统文件读写过程，从中获得文件系统的基本功能函数信息和作用范围。
   
 
打开文件
   
 
在对文件进行写前，必须先打开文件。打开文件的目的是为了能使得目标文件能和当前进程关联，同时需要将目标文件的索引节点从磁盘载入内存，并初始化。
   
 
open操作主要包含以下几个工作要做（实际多数工作由sys_open()完成）：
   
 
l  1分配文件描述符号。
   
 
l  2获得新文件对象。
   
 
l  3获得目标文件的目录项对象和其索引节点对象（主要通过open_namei()函数）——具体的讲是通过调用索引节点对象（该索引节点或是安装点或是当前目录）的lookup方法找到目录项对应的索引节点号ino，然后调用iget(sb，ino)从磁盘读入相应索引节点并在内核中建立起相应的索引节点(inode)对象（其实还是通过调用sb->s_op->read_inode()超级块提供的方法），最后还要使用d_add(dentry,inode)函数将目录项对象与inode对象连接起来。
   
 
l  4初始化目标文件对象的域，特别是把f_op域设置成索引节点中i_fop指向文件对象操作表——以后对文件的所有操作将调用该表中的实际方法。
   
 
l      5如果定义了文件操作的open方法（缺省），就调用它。
   
 
到此可以看到打开文件后，文件相关的“上下文”、索引节点、目录对象等都已经生成就绪，下一步就是实际的文件读写操作了。
   
 
文件读写
   
 
用户空间通过read/write系统调用进入内核执行文件操作，read操作通过sys_read内核函数完成相关读操作，write通过sys_write内核函数完成相关写操作。简而言之，sys_read( )  和sys_write( )几乎执行相同的步骤，请看下面：
   
 
l1 调用fget( )从fd获取相应文件对象file，并把引用计数器file->f_count减1。
   
 
l2 检查file->f_mode中的标志是否允许请求访问（读或写操作）。
   
 
l3 调用locks_verify_area( )检查对要访问的文件部分是否有强制锁。
   
 
l 4 调用file->f_op->read 或file->f_op->write来传送数据。两个函数都返回实际传送的字节数。
   
 
l5 调用fput( )以减少引用计数器file->f_count的值
   
 
l6 返回实际传送的字节数。
   
 
搞清楚大体流程了吧？但别得意，现在仅仅看到的是文件读写的皮毛。因为这里的读写方法仅仅是VFS提供的抽象方法，具体文件系统的读写操作可不是表面这么简单，接下来我们试试看能否用比较简洁的方法把从这里开始到数据被写入磁盘的复杂过程描述清楚。
   
 
现在我们要进入文件系统最复杂的部分——实际读写操作了。f_op->read/f_op->write两个方法属于实际文件系统的读写方法，但是对于基于磁盘的文件系统（必须有I/O操作），比如EXT2等,所使用的实际的读写方法都是利用Linux系统业以提供的通用函数——generic_file_read/generic_file_write完成的，这些通用函数的作用是确定正被访问的数据所在物理块的位置，并激活块设备驱动程序开始数据传送，它们针对Unix风格的文件系统都能很好的完成功能 ，所以没必要自己再实现专用函数了。下面来分析这些通用函数。
   
 
先说读方法：
   
 
第一部分利用给定的文件偏移量（ppos）和读写字节数（count）计算出数据所在页[8][8]的逻辑号(index)。
   
 
第二 然后开始传送数据页。
   
 
第三 更新文件指针，记录时间戳等收尾工作。
   
 
其中最复杂的是第二部，首先内核会检查数据是否已经驻存在页高速缓存（page= find_get_page(mmaping ,index),其中mammping为页高速缓存对象，index为逻辑页号），如果在高速缓存中发现所需数据而且数据是有效的（通过检查一些标志位，如，PG_uptodate），那么内核就可以从缓存中快速返回需要的页；否则如果页中的数据是无效的，那么内核将分配一个新页面，然后将其加入到页高速缓存中，随即使用address_space对象的readpage方法（mapping->a_ops->readpage(file,page)）激活相应的函数使磁盘到页的I/O数据传送。完成之后[9][9]还要调用file_read_actor( )方法把页中的数据拷贝到用户态缓冲区，最好进行一些收尾等工作，如更新标志等。
   
 
 到此为止，我们才要开始涉及和系统系统I/O层打交道了，下面我们就来分析readpage函数具体如何激活磁盘到页的I/O传输。
   
 
address_space对象的readpage方法存放的是函数地址，该函数激活从物理磁盘到页高速缓存的I/O数据传送。对于普通文件，该函数指针指向block_read_full_page( )函数的封装函数。例如，REISEFS文件系统的readpage方法指向下列函数实现：
   
 
       int reiserfs _readpage(struct file *file, struct page *page)
    
 
{ 
    
 
return block_read_full_page(page, reiserfs _get_block);
    
 
}
    
 
需要封装函数是因为block_read_full_page( )函数接受的参数为待填充页的页描述符及有助于block_read_full_page()找到正确块的函数get_block的地址。该函数依赖于具体文件系统，作用是把相对于文件开始位置的块号转换为相对于磁盘分区中块位置的逻辑块号。在这里它指向reiserfs _get_block( )函数的地址。
   
 
block_read_full_page( )函数目的是对页所在的缓冲区启动页I／O操作，具体将要完成这几方面工作：
   
 
n  调用create_empty_buffers(  )为页中包含的所有缓冲区[10][10]分配异步缓冲区首部
   
 
n  从页所对应的文件偏移量（page->index域）导出页中第一个块的文件块号
   
 
n  初始化缓冲区首部，最主要的工作是通过get_block函数进行磁盘寻址，找到缓冲区的逻辑块号（相对于磁盘分区的开始而不是普通文件的开始）
   
 
n  对于页中的每个缓冲区首部，对其调用submit_bh( )函数，指定操作类型为READ。
   
 
l  接下来的工作就该交给I/O传输层处理了，I/O层负责磁盘访问请求调度和管理传输动作。我们简要分析submit_bt()函数，该函数总体来说目的是向tq_disk任务队列[11][11]提交请求，但它所做工作颇多，下面就简要分析该函数的行为：
   
 
u  从b_blocknr（逻辑块号）和b_size（块大小）两个域确定磁盘上第一个块的扇区号，即b_rsector域的值
   
 
u  调用generic_make_request()函数向低级别驱动程序[12][12]发送请求，它接受的参数为缓冲区首部bh和操作类型rw。而该函数从低级驱动程描述符blk_dev[maj]中获得设备驱动程序请求队列的描述符，接着调用请求队列描述符的make_request_fn方法
   
 
make_request_fn方法是请求队列定义的合并相临请求，排序请求的主要执行函数。它将首先创建请求(实际上就是缓冲头和磁盘扇区的映射关系)；然后检查请求队列是否为空：
   
 
l  如果请求队列为空，则把新的请求描述符插入其中，而且还要将请求队列描述符插入tq_disk任务队列，随后再调度低级驱动程序的策略例程的活动。
   
 
l  如果请求队列不为空，则把新的请求描述符插入其中，试图把它与其他已经排队的请求进行组合(使用电梯调度算法)。
   
 
低级驱动程序的活动策略函数是request_fn方法。
   
 
策略例程通常在新请求插入到空列队后被启动。随后队列中的所有请求要依次进行处理，直到队列为空才结束。
   
 
策略例程request_fn(定义在请求结构中)的执行过程如下：
   
 
u  策略例程处理队列中的第一个请求并设置块设备控制器，使数据传送完成后产生一个中断。然后策略例程就终止。
   
 
u  数据传送完毕后块设备控制器产生中断，中断处理程序就激活下半部分。这个下半部分的处理程序把这个请求从队列中删除（end_request( )）并重新执行策略例程来处理队列中的下一个请求。
   
 
好了，写操作说完了，是不是觉得不知所云呀，其实上面仅仅是抽取写操作的骨架简要讲解，具体操作还要复杂得多，下面我们将上面的流程总结一便。
   
 
    粗略地分，读操作依次需要经过：
   
 
l  用户界面层——负责从用户函数经过系统调用进入内核；
   
 
l  基本文件系统层——负责调用文件写方法，从高速缓存中搜索数据页，返回给用户。
   
 
l  I/O调度层——负责对请求排队，从而提高吞吐量。
   
 
l  I/O传输层——利用任务列队异步操作设备控制器完成数据传输。
   
 
请看下图4给出的逻辑流程。
 

   
    
   
 

  
   
     
    
   
  
 
    
 
     
 
周期运行
            
 
 
     

       
         
       
 
    
 
 

  
  
 
      
 
       
 
read
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
sys_read
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
file->f_op->read
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
do_generic_file_read
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
i_mapping->readpage
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
block_read_full_page
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
submit_bh                                                                                                                                                         submit_bh( )                                                                                           
               
 

             
               
             
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
generic_make_request
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
make_request_fn
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
add_requst
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
用户空间函数
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
内核系统调用
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件系统读操作
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
通用文件系统读操作
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
页面读操作
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
通用页读取操作
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
请求提交操作
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
向低级设备驱动发送请求
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
设备具体的请求发送函数
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
将请求加入请求队列
              
 
 
       

         
           
         
 
      
 
 
 


 


  
  
 
      
 
       
 
I/O
               
 
调度层
              
 
 
       

         
           
         
 
      
 
 
 


 


  
  
 
      
 
       
 
tq_disk
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
request_fn
               
 
 
       

         
           
         
 
      
 
 
 





  
  
 
      
 
       
 
调度策略函数
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
任务队列
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
end_request
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
请求处理完毕收尾函数
              
 
 
       

         
           
         
 
      
 
 
 


 


 


  
  
 
      
 
       
 
中断处理函数
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
块设备DMA数据传送
              
 

             
               
             
 
 
       

         
           
         
 
      
 
 
 







 
 
 图 4 读操作流
   
 

  
    
  
 

  
    
  
 
写操作和读操作大体相同，不同之处主要在于写页面高速缓存时，稍微麻烦一些，因为写操作不象读操作那样必须和用户空间同步[13][13]执行，所以用户写操作更新了数据内容后往往先存先存储在页高速缓存中，然后等页回写后台例程bdflush和kupdate[14][14]等来完成写如磁盘的工作。当然写入请求处理还是要通过上面提到的submit_bh函数[15][15]进行I/O处理的。下面简要介绍写过程：
   
 
page = __grab_cache_page(mapping,index,&cached_page,&lru_pvec);
   
 
status = a_ops->prepare_write(file,page,offset,offset+bytes);
   
 
page_fault = filemap_copy_from_user(page,offset,buf,bytes);
   
 
status = a_ops->commit_write(file,page,offset,offset+bytes);
   
 
首先，在页高速缓存中搜索需要的页，如果需要的页不在高速缓存中，那么内核在高速缓存中新分配一空闲项；下一步，prepare_write()方法被调用，为页分配异步缓冲区首部；接着数据被从用户空间拷贝到了内核缓冲；最后通过commit_write()函数将对应的函数把基础缓冲区标记为脏，以便随后它们被页回写例程写回到磁盘。
   
 
好累呀，到此总算把文件读写过程顺了一便，大家明白了上述概念后，我门进入最后一部分：Romfs事例分析。
   
 
实例—romfs文件系统的实现
   
 
文件系统实在是个庞杂的“怪物”，我很难编写一个恰当的例子来演示文件系统的实现。开始我想写一个纯虚文件系统，但考虑到它几乎没有实用价值，而且更重要的是虚文件系统不涉及I/O操作，缺少现实文件系统中置关重要的部分，所以放弃了；后来想写一个实际文件系统，但是那样工程量太大，而且也不容易让大家简明扼要的理解文件系统的实现，所以也放弃了。最后我发现内核中提供的romfs文件系统是个非常理想的实例，它即有实际应用结构也清晰明了，我们以romfs为实例分析文件系统的实现。
   
 
Linux文件系统实现要素
   
 
编写新文件系统自己需要一些基本对象[16][16]。具体的讲创建文件系统需要建立“一个结构四个操作表”：
   
 
n  文件系统类型结构（file_system_type）、
   
 
n  超级块操作表（super_operations）、
   
 
n  索引节点操作表（inode_operations）、
   
 
n  页高速缓存（address_space_operations）、
   
 
n  文件操作表（file_operations）。
   
 
对上述几种结构的处理贯穿了文件系统的主要操作过程，理清晰这几种结构之间的关系是编写文件系统的基础，下来我们具体分析这几个结构和文件系统实现的要点。
   
 

  
    
  
 

  
   
    
     
    
   
  
 

 
  
   
 


  
  
 
      
 
       
 
挂载文件系统
              
 
 
       

         
           
         
 
      
 
 
 


 
  
  
  
  
  
  
  
  
  
  
  
  
 
 
 
  
  
 



  
  
 
      
 
       
 
获取文件系统类型
             
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
获取超级块
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
初始化
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
填充sb->s_op
               
 
 
       

         
           
         
 
      
 
 
 



 


 
 
  
  
  
  
  
  
  
  
  
  
 
 


  
  
 
      
 
       
 
statfs
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
read_inode
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
建root目录项
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
get_sb
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
kill_sb
               
 
 
       

         
           
         
 
      
 
 
 


 
 
 


 


  
  
 
      
 
       
 
读取磁盘INODE
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
初始化INODE
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
设置i_op
               
 
 
       

         
           
         
 
      
 
 
 


 
 
  
 
 
 
  
 
 


 


  
  
 
      
 
       
 
creat
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
lookup
               
 
 
       

         
           
         
 
      
 
 
 


 



 


  
  
 
      
 
       
 
open
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
read
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
write
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
设置i_fop
               
 
 
       

         
           
         
 
      
 
 
 


 


 
  
   
 


  
  
 
      
 
       
 
readpage
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
writepage
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
commit_write
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
设置i->i_data.a_ops
              
 
 
       

         
           
         
 
      
 
 
 


 


  
  
 
      
 
       
 
页缓存操作表
              
 

             
               
             
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件操作表
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
索引节点操作表
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件系统类型结构
              
 

             
               
             
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
超级块操作表
              
 

             
               
             
 

             
               
             
 
 
       

         
           
         
 
      
 
 
 




 
 

  
    
  
 
你必须首先建立一个文件系统类型结构来“描述”文件系统，它含有文件系统的名称、类型标志以及get_sb等操作。当你安装文件系统时（mount）时，系统会解析“文件系统类型结构”，然后使用get_sb函数来建立超级节点“sb”，注意对于基于块的文件系统，如ext2、romfs等，需要从文件系统的宿主设备读入超级块来在内存中建立对应的超级节点，如果是虚文件系统的话，则不是读取宿主设备的信息（因为它没有宿主设备），而是在现场创建一个超级节点，这项任务由get_sb完成。
   
 
超级节点可喂是一切文件操作的鼻祖，因为超级块是我们寻找索引节点——索引节点对象包含了内核在操作文件或目录时需要的全部信息——的唯一源头，我们操作文件必然需要获得其对应的索引节点（这点和建立超级节点一样或从宿主设备读取或现场建立），而获取索引节点是通过超级块操作表提供的read_node函数完成的，同样操作索引节点的底层次任务，如创建一个索引节点、释放一个索引节点，也都是通过超级块操作表提供的有关函数完成的。所以超级块操作表是我们第二个需要创建的数据类型。
   
 
除了派生或释放索引节点等操作是由超级块操作表中的函数完成外，索引节点还需要许多自操作函数，比如lookup搜索索引节点，为建立符号连接等，这些函数都包含在索引节点操作表中，因此我们下一个需要创建的数据类型就是索引节点操作表。
   
 
为了提高文件系统的读写效率，Linux内核设计了I/O缓存机制。所有的数据无论出入都会经过系统管理的高速缓存——对于非基于块的文件系统则可跳过该机制。处于操作数据的目的，页高速缓存同样提供了一函数操作表，其中包含有readpage()、writepage()等函数负责操作高速缓存中的页读写。
   
 
     文件系统最终和用户交互还需要实现文件操作表，该表中包含有关用户读写文件、打开、关闭、影射等用户接口。
   
 
     对于基于块的文件系统实现的一般方式而言，都离不开以上5种数据结构。但根据文件系统的特点（如有的文件系统只可读、有的没有目录），并非要实现操作表中的全部的函数，换句话说，你只需要实现部分函数，而且很多函数系统都已经存在现成的通用方法，因此留给你做的事情其实不多。
   
 
Romfs文件系统是什么
   
 
Romfs是基于块的只读文件系统，它使用块（或扇区）访问存储设备驱动（比如磁盘,CD,ROM盘）。由于它小型、轻量，所以常常用在嵌入系统和系统引导时。
   
 
Romfs是种很简单的文件系统，它的文件布局和Ext2等文件系统相比要简单的得多。它比ext2文件系统要求更少的空间。空间的节约来自于两个方面，首先内核支持romfs文件系统比支持ext2文件系统需要更少的代码，其次romfs文件系统相对简单，在建立文件系统超级块（superblock）需要更少的存储空间。Romfs文件系统不支持动态擦写保存，对于系统需要动态保存的数据采用虚拟ram盘的方法进行处理（ram盘将采用ext2文件系统）。
   
 
下面我们来分析一下它的实现方法，为读者勾勒出编写新文件系统的思路和步骤。希望能为大家自己设计文件系统起到抛砖引玉的效果。
   
 
Romfs文件系统布局与文件结构
   
 
文件系统简单理解就是数据的分层存储结构，数据由文件组织，而文件又由文件系统安排存储形式，所以首先必须设计信息和文件组织形式——也就是这里所说的文件布局。
   
 
       
   
 
在Linux内核源代码种得Document/fs/romfs中介绍了romfs(下载romfs）文件系统得布局和文件结构。现面我们简要说明一下它们。
   
 

  
   
     
    
   
  
 
    
 
     
 
0
             
 
 
     

       
         
       
 
    
 
 

 
   
   
 
       
 
        
 
文件系统名称
               
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
文件系统大小
               
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
检验合（前512字节）
               
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
8
                
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
12
                
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
16
                
 
 
        

          
            
          
 
       
 
 
  
 
 
 
 
 
 
 
   
   
 
       
 
        
 
卷名
               
 
 
        

          
            
          
 
       
 
 
  
 
 
   
   
 
       
 
        
 
第一个文件头
               
 
 
        

          
            
          
 
       
 
 
  
 




 
 

  
    
  
 
                                         
 
 图 5 romfs文件系统布局
   
 
上图是romfs布局图，可以看到文件系统中每部分信息都是16位对其的，也就是说存储的偏移量必须最后4位为0，这样作是为了提高访问速度。随意如果信息不足时，需要填充0以保证所有信息的开始位置都为16为对其[17][17]。
   
 
   文件系统的开始8个字节存储文件系统的ASCII形式的名称，比如“romfs”；接着4个字节记录文件大小；然后的4个字节存储的是文件系统开始处512字节的检验和；接下来是卷名；最后是第一个文件的文件头，从这里开始依次存储的信息就是文件本身了。
  
 
  Romfs的文件结构也非常简单，我们看下图
  
 

  
    
  
 

  
    
  
 

  
   
     
    
   
  
 
    
 
     
 
0
             
 
 
     

       
         
       
 
    
 
 

  
  
 
      
 
       
 
下一个文件头的偏移
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件类型信息
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件大小
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
检验和
              
 
 
       

         
           
         
 
      
 
 
 









  
  
 
      
 
       
 
文件
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
文件
              
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
4
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
8
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
12
               
 
 
       

         
           
         
 
      
 
 
 


  
  
 
      
 
       
 
16
               
 
 
       

         
           
         
 
      
 
 
 




 
 
具体需要实现的对象
   
 
   Romfs文件系统定义针对文件系统布局和文件结构定义了一个磁盘超级块结构和磁盘inode(对应于文件)结构：
   
 
struct romfs_super_block {
  
 
                  __u32 word0;
  
 
              __u32 word1;
  
 
              __u32 size;
  
 
              __u32 checksum;
  
 
char name[0];          
  
 
 };
  
 
  struct romfs_inode {
  
 
          __u32 next;           
  
 
         __u32 spec;
  
 
          __u32 size;
  
 
          __u32 checksum;
  
 
          char name[0];
  
 
  };
  
 
上述两种结构分别描述了文件系统结构与文件结构，它们将在内核装配超级块对象和索引节点对象时被使用。
   
 
   Romfs文件系统首先要定义的对象是文件系统类型romfs_fs_type。定义该对象同时还要定义读取超级块的函数romfs_read_super。
   
 
ramfs_read_super()作用是从磁盘读取磁盘超级块给超级块对象，具体行为如下
   
 
1 装配超级块。
   
 
  1．1 初始化超级块对象某些域。
    
 
1．2 从设备中读取磁盘第0块到内存到内存 bread(dev,0,ROMBSIZE)，其中dev是文件系统安装时指定的设备，0指设备的首块，也就是磁盘超级块，ROMBSIZE是读取的大小。 
    
 
  1．3 检验磁盘超级块中的校验和
    
 
  1．4 继续初始化超级块对象某些域
    
 
2 给超级块对象的操作表赋值（s->s_op = &romfs_ops）
   
 
3 为根目录分配目录项 s->s_root = d_alloc_root(iget(s,sz), sz为文件系统开始偏移。 
   
 
               超级块操作表中romfs文件系统实现了两个函数
   
 
static struct super_operations romfs_ops = {
   
 
        read_inode:     romfs_read_inode,
   
 
        statfs:         romfs_statfs,
   
 
};
   
 
第一个函数read_inode(inode)是用磁盘上的数据填充参数指定的索引节点对象的域；索引节点对象的i_ino域标识从磁盘上要读取的具体文件系统的索引节点。
    
 
1 根据inode参数寻找对应的索引节点。
    
 
2 初始化索引节点某些域
    
 
3 根据文件的访问权限（类别）设置索引节点的相应操作表
   
 
  3．1 如果是目录文件则将索引节点表设为i->i_op = &romfs_dir_inode_operations;文件操作表设置为->i_fop = &romfs_dir_operations; 如果索引节点对应目录的话，那么需要的操作仅仅会是lookup操作（因为romfs是个功能很有限的文件系统）；对于文件操作表中的两个方法一个为read，另一个为readdir。前者利用通用函数generic_read_dir，返回用户错误消息。后者是针对readdir/getdents等系统调用实现的返回目录中文件的函数
     
 
  3．2 如果是常规文件，则将文件操作表设置为i->i_fop = &generic_ro_fops; 
     
 
将页高诉缓存表设置为i->i_data.a_ops = &romfs_aops;由于romfs是只读文件系统，它在对正规文件操作时不需要索引节点操作，如mknod，link等，因此不用给管索引节点操作表。
     
 
对常规文件的操作也只需要使用内核提供的通用函数表struct generic_ro_fops ，它包含基本的三种常规文件操作：
     
 
 llseek:         generic_file_llseek,
    
 
     read:           generic_file_read,
    
 
mmap:           generic_file_mmap,
    
 
   利用这几种通用函数，完全能够满足romfs文件系统的的文件操作要求，具体函数请自己阅读源代码。
     
 
回忆前面我们提到过的页高速缓存，显然常规文件访问需要经过它，因此有必要实现页高诉缓存操作。因为只需要读文件，所以只用实现romfs_readpage函数，这里readpage函数使用辅助函数romfs_copyfrom完成将数据从设备读入页高速缓存，该函数根据文件格式从设备读取需要的数据。设备读取操作需要使用bread块I/O例程，它的作用是从设备读取指定的块[18][18]。
     
 
  3．3 如果是连接文件，则将索引节点操作表设置为：i->i_op=&page_symlink_inode_operations;
     
 
将页高速缓存操作表设置为：
     
 
i->i_data.a_ops = &romfs_aops;
    
 
符号连接文件需要使用通用符号连接操作page_symlink_inode_operations实现，同时也需要使用页高速缓存方法。 
     
 
  3．4 如果是套接字或管道则，进行特殊文件初始化操作init_special_inode(i, ino, nextfh);
     
 
到此，我们已经遍例了romfs文件系统使用的几种对象结构：romfs_super_block、romfs_inode、romfs_fs_type、super_operations romfs_ops、address_space_operations romfs_aops 、file_operations romfs_dir_operations、inode_operations romfs_dir_inode_operations 。实现上述对象是设计一个新文件系统的最低要求。
   
 

  
    
  
 
最后要说明的是为了使得romfs文件系统作为模块挂载，需要实现static int __init init_romfs_fs(void)
    
 
{
   
 
   return register_filesystem(&romfs_fs_type);
   
 
}
   
 
和
    
 
static void __exit exit_romfs_fs(void)
   
 
{
   
 
   unregister_filesystem(&romfs_fs_type);
   
 
}
   
 
两个在安装romfs文件系统模块时使用的例程。
    
 
安装和卸载
    
 
module_init(init_romfs_fs)
   
 
module_exit(exit_romfs_fs)
   
 

  
    
  
 
           到此，romfs文件系统的关键结构都已介绍，至于细节还是需要读者仔细推敲。Romfs是最简单的基于块的只读文件系统，而且没有访问控制等功能。所以很多访问权限以及写操作相关的方法都不必去实现。
    
 
      使用romfs首先需要genromfs来制作romfs文件系统镜象（类似于使用mke2fs格式化文件系统），然后安装文件系统镜象 mount –t romfs ********。 Romfs可以在编译内核时制定编译成模块或编如内核，如果是模块则需要首先加载它。
   
 

  
    
  
 
小结：实现文件系统必须想上要清楚文件系统和系统调用的关系，想下要了解文件系统和I/O调度、设备驱动等的联系。另外还必须了解关于缓存、进程、磁盘格式等概念。在这里并没有对这些问题进行是深入分析，仅仅提供给大家一个文件系统全景图，希望能对自己设计文件系统有所帮助。文件系统内容庞大、复杂，许多问题我也不确定，有文件系统经验的朋友希望能够广泛交流。
   
 


  
   
  
 

 
  

 

  
    
  
 

 

 
  
 
 
 
  
[1][1] 请参见  OPERATION SYSTEMS INTERNALS AND DESIGN PRINCIPLES 一书第12章 
 
 
 
 
 
  
[2][2] 扇区是磁盘的最小寻址单元单元，而文件块是内核操作文件的最小单位，一个块可以包含一个或数个扇区。这些磁盘块被读入内存后即刻被存入缓冲中，同样文件块被写出是也要通过缓冲。
 
 
 
 
 
  
[3][3] 如果文件按记录形式组织，那么在数据在成为文件块前，还要经过记录形式的阶段。
 
 
 
 
 
  
[4][4] 摘自 Linux 内核开发 中第 11 章中文件系统抽象层一节
 
 
 
 
 
  
[5][5] 请看Linux 内核开发 一书第11章
 
 
 
 
 
  
[6][6] 在2.6内核以后，缓冲头的作用比不象以前那么重要了。因为2.6中缓冲头仅仅作为内核中的I/O操作单元，而在2.6以前缓冲头不但是磁盘块到物理内存的映射，而且还是所有块I/O操作的容器。
 
 
 
 
 
  
[7][7] 这里安装的文件系统属于非根文件系统的安装方法。根文件系统安装方法有所区别，请查看相关资料。
 
 
 
 
 
  
[8][8] 无论读文件或写文件，文件中的数据都是必须经过内存中的页高速缓存做中间存储才能够被使用。高速缓存由一个叫做address_space的特殊数据结构表示，其中含有对页高速缓存宿主（address_space->host）的操作表。
     
 
 
 
 
 
  
[9][9] 这期间要要处理一些预读，以此提高未来访问的速度。
 
 
 
 
 
  
[10][10]  缓冲与相应的块一一对应，它的作用相当于是磁盘块在内存中的表示。
 
 
 
 
 
  
[11][11]  tq_disk是专门负责磁盘请求的任务队列，任务队列是用来推后异步执行的一种机制。2.6内核中已经用工作队列代替了工作队列。
 
 
 
 
 
  
[12][12]  块设备驱动程序可以划分为两部分：底级驱动程序（blk_dev_struct）和高级设备驱动(block_device)。底级设备驱动程序作用是记录每个高级驱动程序送来的请求组成的队列。
 
 
 
 
 
  
[13][13] 文件读区操作必须同步进行，在读取的数据返回前，工作无法继续进行。而且如果结果在30秒内回不来，则用户必需将无法忍受，所以读操作执行紧迫。而对于写操作，则可以异步执行，因为写入操作一般不会影响下一步的执行，所以紧迫性也低。
 
 
 
 
 
  
[14][14] bdflush和kupdate 分别是当空闲内存过低时释放脏页和当脏缓冲区在内存中存在时间过长时刷新磁盘的。而在2.6内核中，这两个函数的功能已经被pdflush统一完成。
 
 
 
 
 
  
[15][15] 实际是从block_read_full_page( )函数中调用submit_bh()函数的。
 
 
 
 
 
  
[16][16] 对象指的是内存中的结构体实例，而不是物理上的存储结构。
 
 
 
 
 
  
[17][17] 创建romfs文件系统可使用genromfs格式化工具。
 
 
 
 
 
  
[18][18] 索引节点结构描述了从物理块（块设备上的存取单位，是每次I/O操作最小传输的数据大小）到逻辑块（文件实际操作基本单元）的映射关系。
 
 
 
  

文件系统结构（File System Structure）
 
磁盘提供大量的外存空间来维持文件系统。磁盘的下述两个特点使得其成为存储多个文件的方便介质。
 
①可以原地重写；
②可以直接访问磁盘上的任意一块信息。
 
为了提供对磁盘的高效且便捷的访问，操作系统通过文件系统来轻松地存储、定位、提取数据。文件系统有两个设计问题。
 
①定义文件系统对用户的接口
②创建数据结构和算法来将逻辑文件系统映射到物理外存设备上。
 
文件系统本身通常由不同的层组成。如下图所示的是一个分层设计的简单例子。
 


 

 
I/O控制 
 
  
由设备驱动程序和中断处理程序组成，实现内存与磁盘之间的信息传递
基本文件系统 
 
  
向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写
文件组织模块 
 
  
知道文件及其逻辑块和物理块。
空闲空间管理器
逻辑文件系统 
 
  
管理元数据：文件系统的所有结构数据，而不包括实际数据（或文件内容）
根据给定符号文件名来管理目录结构
逻辑文件系统通过文件控制块(FCB)来维护文件结构
 
FCB的典型结构如下图所示 
 

 

 
文件系统实现（File System Implementation ）
 
实现文件系统要使用多个磁盘和内存结构。虽然这些结构赢操作系统和文件系统而异，但是还是有其规律性的。
 
实现文件系统的结构和操作如下：
 
磁盘结构；
内存中的文件系统结构；
分区与安装
虚拟文件系统
 
磁盘结构
 
引导控制块（卷）（boot control block\Volume） 
 
  
包含启动OS的控制信息
UFS 中称为引导块（boot block ） 
 
    
通常为分区的第一块。如果该分区没有OS，则为空
NTFS中称为分区引导扇区（partition boot sector）
卷控制块（卷）（ Volume control block (/volume)）
 
  
包含卷的详细信息，包括 
 
    
块数和块的大小；
空闲块的数量和指针；
空闲FCB的数量和指针。
UFS称为超级块 Superblock ， NTFS 称为 主控文件表master file table 。
目录结构
 
  
用来组织文件
UFS ，包括文件名和关联的inode 号
NTFS，主控文件表（master file table ）；
文件控制块（FCB）：包括很多文件信息，如文件许可、拥有者、大小和数据块的位置等，详情见上文示例。 
 
  
UFS中， 索引节点（ inode） ；
NTFS中，主控文件表； 
 
    
采用关系数据库结构, 记录/文件
 
内存中的文件系统结构
 
安装表 
 
  
包含所有安装分区的信息
目录结构快表 
 
  
保存近来访问过的目录信息（对安装分区的目录，可以包括一个指向分区表的指针）
系统范围的打开文件表 
 
  
包括每个打开文件的FCB拷贝和其他信息
单个进程的打开文件表 
 
  
包括一个指向系统范围内已打开文件表中合适条目和其他信息的指针 
 
    
文件描述符（file descriptor, Linux/UNIX）
文件句柄（file handle, Windows）
 
下图总结了文件系统实现的 操作结构。 
 

 

 
分区与安装
 
磁盘布局赢操作系统而异。一个磁盘可分成多个分区，或者一个卷可以跨越多个磁盘上的数个分区。
 
分区可以是“生的”（raw），即没有文件系统，或是“熟的”（cooked）即含有文件系统。生的分区用于没有合适文件系统的地方。如：Unix中的交换区，因为它不使用文件系统而是使用自己的磁盘格式。
 
引导信息能存在各个分区中，并且有自己的格式。因为在引导时，系统并没有文件系统设配驱动程序，所以不能解释文件系统格式。它通常为一组有序块并且作为二进制镜像文件读入内存。引导信息除了包括如何启动一个特定操作系统外，还可以有其他指令。（如BootManager bootstar 8.3，Linux GRUB, GRUB - GRand Unified Bootloader）
 
根分区（root partition）包括操作系统内核或其他系统文件，在引导时装入内存。其他分区根据不同操作系统可以在引导时自动装入或在此之后手动装入。
 
/root, /boot
文件系统安装表（file system mount table）
 
虚拟文件系统
 
虚拟文件系统(VFS)提供了一种面向对象的方法来实现文件系统
VFS功能 
 
  
通过定义VFS 接口将一般文件系统操作与实现分离；
为网络中唯一表示一个文件提供一种机制（by vnode）
VFS允许在不同类型的文件系统上采用同样的系统调用接口（API）
API是针对VFS的接口，而非对任何特定类型的文件系统
 


 

 
第一层为文件系统接口，包括，open()、read()、write()和close()调用以及文件描述符。
 
第二层称为虚拟文件系统(VFS)层，它有两个目的：
 
VFS层通过定义一个清晰的VFS接口，以将文件系统的通用操作和具体实现分开。多个VFS接口的实现可以共存在同一台机器上，它允许访问已经装再本地的多个类型的文件系统
VFS提供了在网络上唯一标示一个文件的机制。
 
目录实现（Directory Implementation）
 
目录分配和目录管理算法的选择对文件系统的效率、性能和可靠性有很大的影响。
 
线性列表
 
最为简单的目录实现方法是使用存储文件名和数据块指针（数组、链表等）的线性列表，这种方法编程简单但是运行时较为费时。
 
目录条目的线性列表的真正缺点是采用线性搜索来查找特定条目。 
 事实上，许多操作系统采用软件缓存来存储最近访问过的目录信息。缓存命中避免了不断地从磁盘读取信息，排序列表可以使用二分搜索，并减少平均搜索时间。
 
Hash表
 
采用Hash数据结构的线性表
 
减少了目录搜索时间，插入和删除也较为简单。
不过需要一些机制来避免碰撞（两个文件名哈希到相同的位置） 
 哈希表的最大困难是：其固定的大小和哈希函数对大小的依赖性
 
分配方法（Allocation Methods）
 
目标 
 
  
有效使用磁盘空间；
快速访问文件。
常用的分配方法有以下三类 
 
  
连续分配
链接分配
索引分配
 
连续分配 (contiguous allocation）
 
连续分配方法要求每个文件占据磁盘上的一组连续的块。
 
特点：
 
简单 － 只需要记录文件的起始位置（块号）及长度。
访问文件很容易，所需的寻道时间也最少 
 
  
顺序访问；
直接访问。
存在的问题 
 
  
为新文件找空间比较困难 
 
    
首次，最佳，最差
文件很难增长
 


 

 
逻辑地址到物理地址的映射方法如下：
 
逻辑地址 / 块大小 = 商, 余数 
 
   $${LA\over 512} = Q \cdot\cdot\cdot\cdot\cdot\cdot R$$ 
 
 
 
访问的块 = Q + 起始地址（base） 
 块中的位置 = R
 
 
基于扩展的连续分配方法：
 
许多新的文件系统采用一种修正的连续分配方法
扩展是一个连续的磁盘块 
 
  
文件分配时，将扩展分配给文件
另一个大的连续空间
一个文件包括一个或多个扩展
需要一个指向下一个扩展的指针
文件块的位置就成为开始地址、块数、加上一个指向下一扩展的指针。
分配磁盘块时，在扩展中进行
 
链接分配 (linked allocation)
 
链接分配解决了连续分配的所有问题。
 
采用链接分配，每个文件是磁盘块的链表：
 
磁盘块分布在磁盘的任何角落。
每个目录条目都有一个指向文件第一块的指针。
该指针初始化为 nil (表尾指针的值)以标识空文件。
 


 

 
优点： 
 
  
简单 － 只需起始位置
文件创建与增长容易
缺点： 
 
  
不能随机访问
块与块之间的链接指针需要占用空间 
 
    
簇：将多个连续块组成簇，磁盘以簇为单位进行分配
存在可靠性问题
 


 

 
文件分配表(FAT)
 
每个分区的开始部分用于存储该FAT表。
 
每个磁盘块在该表中有一项，该表可以通过块号来索引。
 
目录条目中含有文件首块的块号码。根据块号码索引的FAT条目包含文件下一块的地号码。这种链会一直继续到最后一块，该块对应FAT条目的值为文件结束值。未使用的块用0值来表示。
 
为文件分配一个新的块只要简单地找到第一个值为０的FAT条目，用新块的地址替换前面文件结束值，用文件结束值替代0。
 
如果不对FAT采用缓存，FAT分配方案可能导致大量的磁头寻道时间。但通过读入FAT信息，磁盘能找到任何块的位置，从而实现随机访问。
 


 

 
索引分配(indexed allocation)
 
将所有的数据块指针集中到索引块中 
 
  
索引块中的第i个条目指向文件的第i块。
目录条目包括索引块的地址
 


 

 
每个文件都有索引块； 
 
  
磁盘块地址的数组
索引分配支持直接访问，且没有外部碎片问题
索引块本身可能会浪费空间 
 
  
链接方案：一个索引块通常为一个磁盘块。对于大文件，可以将多个索引块链接起来。
多层索引：类似于内存的间接寻址方式（一级、二级间接…）
 


 

 


 

 
空闲空间管理（Free-Space Management ）
 
位向量(Bit vector)（n块）
 


 

 
 
 
bit[i] = 1 $\rightarrow$ block[i]空闲
bit[i] = 0 $\rightarrow$ block[i]被占用
 
 
第一个空闲块号: 
 
 $$一个字的位数 × 值为0的字数 ＋ 第一个值为1的位的偏移$$ 
 
位向量需要额外的空间 
 
  
设块大小为$2^{12}$ 字节
磁盘大小为$2^{30}$字节 (1GB)
N = $2^{30} / 2^{12} = 218$ (即32K bytes)
容易得到连续的文件
分配与回收过程 
 
  
分配过程
回收过程
 
空闲表法
 


 

 
链表(空闲链表)
 
将所有空闲磁盘块用链表连接起来，并将指向第一空闲块的指针保存在磁盘的特殊位置，同时也缓存在内存中。
 
不易得到连续空间
 
没有空间浪费
 


 

 
分组（成组链接）
 
将n个空闲块的地址存在第一个空闲块中；
最后一块包含另外n个空闲块的地址。
 
成组链接图如下所示 
 

 

 
分组（成组链接） 
 
  
分配与回收过程
分配过程
回收过程 
 
  
所需的保护
指向空闲表的指针
 
所需的保护
 
位映射 
 
  
必须保存在磁盘上
内存中的副本可能与磁盘上不相同；
对于 block[i]不允许出现的情形：在内存中 bit[i] = 1，而在磁盘上 bit[i] = 0 。
解决方法 
 
  
设置磁盘上bit[i] = 1
分配block[i]
设置内存中 bit[i] = 1
 
效率和性能（Efficiency and Performance）
 
效率
 
效率依赖于
 
磁盘分配与目录算法 
 
  
预分配，簇
文件目录项中保存的数据的类型 
 
  
最近写/访问日期
指针大小 
 
  
$2^{12} , 2^{32} , 2^{64} , 2^{128}$
 
性能
 
性能有如下几点：
 
磁盘缓冲 － 将最近使用过的块放在内存的某个地方
马上释放与预先读取 － 优化顺序访问
留出一块内存作为虚拟磁盘（或RAM磁盘）来提高个人计算机的性能
 
页缓存（page cache）
 
页缓存使用虚拟内存技术，以将文件数据作为页而不是面向文件系统的块来缓存。
内存映射I/O使用了页缓存
I/O通过文件系统再使用缓冲缓存
 
无统一缓冲缓存的I/O如下图所示
 


 

 
采用了统一缓冲缓存的I/O则变化如下 
 

 

 
不同的磁盘缓存位置
 


 

 
恢复（Recovery)
 
一致性检查 － 比较目录中的数据与磁盘中的数据块，以消除不一致性
使用系统程序将数据从磁盘备份到其他存储设备（如磁盘，磁带） 
 
  
增量备份
从备份上恢复数据以恢复丢失的文件或磁盘
 
结构化日志的文件系统(Log-Structured File Systems)
 
每个更新作为事务记录；
所有的事务写到日志中 
 
  
一旦写到日志中，就认定为确认的提交；
但是FS可以不更新。
事务异步写到FS中 
 
  
当FS修改后，事务从日志中删除
如果FS崩溃，在日志中的所有事务都要执行