2022-12-20人工智能106

本文完成磁盘管理4层抽象中的最后一层抽象：目录与文件系统。达成的效果是整个磁盘抽象为我们日常所熟悉的 目录树，这个树应当能够适配不同的操作系统（是一个独立子系统），通过目录树/文件系统对文件的组织，我们可以方便的访问我们需要的文件。

参考资料：

课程：哈工大操作系统（本部分对应 L31 && L32）

磁盘管理共4层抽象，本部分为第4层，前3层在笔记11、笔记12
实验：操作系统原理与实践_Linux - 蓝桥云课 (lanqiao.cn)
课本：《操作系统原理、实现与实践》- 李治军、刘宏伟

由于新学期课程开始启动，加入了学校的操作系统实践，所以后续本系列的实验更新也会变慢。不过幸运的是，能够在线下课程之前，更新完这系列的哈工大操作系统理论课程。

1. 第4层抽象描述：文件系统

经过了前3层的抽象，对磁盘的使用已经变成了对于文件的访问，而这已经很接人们时使用操作系统的图像了。但是这还不是最后我们眼中的系统模样，因为我们的系统中有一个类似于文件树的多级文件结构（Ubuntu 下可用 tree 命令查看）。

而第4层抽象，就是建立文件树。

在第3层抽象中，一个文件对应一个盘块集合，通过抽象将磁盘的盘块变为用户眼中的字符流。

用户眼里文件的样子 —— 字符流；
磁盘上的文件的样子 —— 扇区集合；
磁盘文件抽象: 建立了以单个文件中字符流到盘块集合的映射关系。

操作系统学习笔记13 | 目录与文件系统

实际生活中，我们不会只使用一个文件，我们见到的电脑中有数以万计的文件，而第四层抽象，就是从多个文件向一个文件系统的抽象，文件的物理存储位置是磁盘，这层抽象意味着 对整个磁盘的抽象、组织。最终形成我们所熟悉的 文件树结构。

当然，我们会好奇这种抽象到底是如何实现的。

磁盘中存放文件系统的映射关系，操作系统用相关数据结构维护这些映射关系； ！这些映射关系也就是这层抽象的核心。！
当用户 用文件树/文件系统访问文件、管理文件时，先使用这些映射关系定位到文件及文件操作，然后接入前3层抽象，向下读写磁盘。

可见，当磁盘组织为上述形式，理论上也就可以实现在不同操作系统下的适配。（即磁盘拆卸，放到不同系统的电脑上，可以继续使用）。

2. 目录：多个文件的组织结构

既然我们要使用多个文件，那么计算机如何安排多个文件呢？

最刚开始，所有文件都放在同一层面，这时查找目标文件就会十分麻烦。如下图所示。
紧接着优化一下，每个用户的文件分开，但还是不能避免上述难以查找的情况。

操作系统学习笔记13 | 目录与文件系统

虽然这种优化很初级，但是基于这种分治的理念，就可以想到引入中间结构（文件夹），来管理不同层次的文件， 也就是目录树。每个目录下的文件大大减少，这样就便于查找。如下图所示：
操作系统学习笔记13 | 目录与文件系统

上述引入了一个中间结构，用户常称之为文件夹，实际上也可称为目录，表示一个文件及集合，用目录形成整个树状结构。这就是我们想要的多个文件的组织结构。

接下来的问题就是，目录这个上层抽象概念，如何对应盘块、磁盘；或是说，如何用盘块来实现目录。

3. 目录的实现思路和原理

3.1 目录的使用

有这样一个基本事实，用户对目录的使用，实际上都应当对应一些代码的执行。要弄清楚目录的实现原理，不妨看看目录在使用过程中都发生了什么。

用户想要打开 a 文件时，向下层发出的信号是 open 某个路径名，如 open("/my/data/a")，接着操作系统应当在目录树结构中定位 a 文件。

更准确地说，定位文件 a 意味着要拿到文件 a 的 FCB / inode。

这里这个 "更准确的"，可以参见上一篇笔记最后的总结中的梳理。

也就是说，上层用户传下路径名，操作系统拿到文件的 inode，这就接上了前3层抽象，inode->盘块 -> 电梯队列 -> 解算CHS -> 磁盘控制器读写磁盘。这时，用户眼中的目录树就形成了。
操作系统学习笔记13 | 目录与文件系统

那么问题就在于，如何根据路径名，得到 FCB？

3.2 目录下寻找文件

如何在父文件夹下找到子文件（夹）呢？一个很直观的想法就是，在夫文件 my（可以把文件夹/目录也视为一个文件）中存放子文件 data、cont、mail 的 FCB。

而如果父文件存放所有子文件的 FCB，操作系统在拿到路径名匹配子文件时，需要把父文件中的子文件信息 全部读到内存中，说到这里大家可能都明白了，实际上我们只需要在父文件下匹配下一级目录的 文件名，却需要读入所有记录着子文件 全部信息的 FCB 来进行匹配。

磁盘读写很慢（相较于CPU来说），而且需要读入这么多的 FCB，FCB 中有大量的无效信息，所以这样文件系统的查找比较慢，效率比较低。

更简洁的方法就是，在父文件中存放子文件 FCB 的地址（也就是指针）。当然，地址/指针是一个内存概念，在磁盘中应当是： 父文件中存放子文件 FCB 的某种编号，根据这个编号可以计算子文件 FCB 的位置。
操作系统学习笔记13 | 目录与文件系统

具体如何实现这个编号的操作呢？

父文件/目录中存放
让 FCB 在磁盘中来连续存放；也就是单独划一块连续磁盘区域存放各个文件的 FCB 。
这样父文件的存储内容就少了很多，搜索时解析也更方便。

当我们找到 my 文件的 FCB，这也是一个目录，根据 FCB 找到 my 文件夹的数据块，其中存放 my 目录下子文件的 FCB 编号，依次递推，就能找到最末端我们需要的文件。

整个流程：

根目录的 FCB 放在 FCB 数组的首位（一个固定的位置），这个固定的位置，或是说数组的基址，由下图中蓝色区域在磁盘初始化时记载在蓝色区域固定的位置。
根据父目录的数据块中的索引项，可以找到子文件的 FCB 编号，据此访问 FCB数组中的 FCB，根据 FCB 找到文件的数据块；
同样的第二步过程，再向下搜索、匹配、解析。

操作系统学习笔记13 | 目录与文件系统

3.3 文件系统自举

根据上面的流程梳理，很明显还有一个环节需要设计，那就是这个最开始根目录如何找到的问题，找到根目录后中间到末尾都可以递推得到。这就是自举。（自己能够很好的运作）

所以我们需要在别的地方设置根目录的位置。

将整个磁盘格式化为下图样子；
根目录的 FCB 放在 FCB 数组的第一项（下图中的 i 节点区的第一项）
盘块位图区域用于表示盘块的空闲状态，并且表征盘块大小。
inode 节点位图，用于表示 inode/FCB 区域的空闲状态，用于新建、删除文件时的状态判断。这里可以表征操作系统支持的最多文件个数。
超级块，记录自身大小、盘块位图区和 i 节点位图区的大小等信息；同时根据这三个区域的大小（以及超级块的起始位置），就可以推算 i节点区的开始位置，即 根目录的 FCB 位置。
拿到根目录，整个文件系统接下来递推，就实现了自举。
操作系统在使用磁盘时，需要将磁盘 mount 到系统上，mount 本质就是在读取超级块，拿到位图信息和根目录。
引导块，存放磁盘启动和初始化信息。

这里位图的翻译不太直观，英文是 bitmap=bit map 用比特表示的映射。

3.4 总结

到这里四层抽象都介绍完毕了。这里来梳理一下整个磁盘抽象过程。

如下图所示。用户操作文件，如读取 test.c 中的一段字符流。
目录解析找到 test.c 文件的 FCB/ inode ； =👆第4层，前3层👇=
根据第 2 步的 FCB 以及所要访问的字符流找到对应盘块789；
根据多进程图像，用电梯算法放入电梯队列；
从队列取出789盘块号，算出 CHS；
根据 CHS ，out 驱动磁盘控制器读写磁盘。

操作系统学习笔记13 | 目录与文件系统

4. 目录解析的代码实现

这里就来看看上面的第2步中的目录如何解析。

还是从顶向下看。

4.1 open()：建立路径名到inode链接

open 是一个系统调用，他就会触发目录解析。要形成路径文件名到 inode 的链条，实际上就是第四层抽象到第三层抽象的过程。如下图所示。而 open()调用了 sys_open()来执行，所以目录解析代码应当从sys_open 开始看。
操作系统学习笔记13 | 目录与文件系统

// 这里跟书上不大一样，理解即可
//在linux/fs/open.c中
int sys_open(const char* filename, int flag)
{
    //解析路径函数，参数分别为 文件名，内存存放inode的地址
    i=open_namei(filename,flag,&inode);
    ...

}
//目录解析
int open_namei(...)
{
    dir=dir_namei(pathname,&namelen,&basename);
    ....

}
//核心代码
static struct m_inode *dir_namei()
{ dir=get_dir(pathname); }

4.2 get_dir：完成真正解析

真正完成目录解析的是get_dir，它是整个目录解析的主控函数，有 4 个比较重要的环节：

root：找到根目录；
find_entry：从目录中读取目录项；
inr：目录项中的索引节点号 inode；
iget：再读下一层目录；

// pathname 是路径名
static struct m_inode *get_dir(const char *pathname)
{
    //如果是'/'，从根目录开始
    if((c=get_fs_byte(pathname))=='/')
    {
        /*
           current->root 是根目录的FCB，
           为什么这里根目录直接有inode呢？
           这是因为所有进程都由原始shell父进程fork而来，
           而操作系统初始化父进程时时
           就初始磁盘得到了根目录的inode/FCB
           所以root是一直都有的
           （初始化代码后续还会再讲）
        */
        inode=current->root; pathname++;
    }
    //解析从当前目录开始
    else if(c) inode=current->pwd;
    while(1)
    {
        if(!c) return inode; //函数的正确出口
        //根据根目录的inode找到根目录下的目录项
        bh=find_entry(&inode,thisname,namelen,&de);
        // 相当于中的13
        int inr=de->inode;
        int idev=inode->i_dev;
        //根据目录项读取下一层inode对应的目录项
        inode=iget(idev,inr);
        //不断循环，向下解析
    }
}

操作系统学习笔记13 | 目录与文件系统

4.3 mount_root：根目录的来源

4.2 中对于 inode = current -> root;的最长注释中，提到了根目录的初始化。下面看看根目录的 inode 是如何得到的。

inode=current->root;

void init(void)
{
    // shell 进程会挂载磁盘
    setup((void *) &drive_info);
    ...

}
//在kernel/hd.c中
sys_setup(void * BIOS)
{
    hd_info[drive].head = *(2+BIOS);
    hd_info[drive].sect = *(14+BIOS);
    //挂载硬盘时将根目录挂进来
    mount_root();
    ...

}
//在 fs/super.c 中
void mount_root(void)
{
    // 根目录的挂载就是调用 iget，根据1号ROOT_INO
    mi=iget(ROOT_DEV,ROOT_INO));
    // 把根目录FCB读入进程PCB。
    current->root = mi;
    //接下来就是 子进程创建时fork继承这个root
    ...

}

操作系统学习笔记13 | 目录与文件系统

4.4 iget()：读入目录节点

看看 iget 如何将根目录读入，以及其如何将普通目录的 inode 读入。

struct m_inode * iget(int dev, int nr)
{
    struct m_inode * inode = get_empty_inode();
    inode->i_dev=dev; inode->i_num=nr;
    //这个iget函数要做的事情就是 read_inode。
    read_inode(inode); return inode;
}

static void read_inode(struct m_inode *inode)
{
    //读取超级块，获得两个位图区的大小信息放到sb中，用以计算i节点的盘块号
    struct super_block *sb=get_super(inode->i_dev);
    lock_inode(inode);

    //引导块占1个盘块，超级块1个盘块，所以从2开始计数
    // i_map_block 和 z_map_block 就是两个位图区的大小
    // 再加 inode->i_num-1，就是所要读的inode序号之前有几个inode块
    // 这样就算出了 inode 的盘块号

    block=2+sb->s_imap_blocks+sb->s_zmap_blocks+
    (inode->i_num-1)/INODES_PER_BLOCK;

    // 接下来调用bread，这就是从磁盘将对应盘块号内容读入内存
    bh=bread(inode->i_dev,block);
    //解析处理inode,因为一个盘块可能有多个inode，取出所需的。
    inode=bh->data[(inode->i_num-1)%INODES_PER_BLOCK];
    unlock_inode(inode);
}

操作系统学习笔记13 | 目录与文件系统

根据这个图再敲一下黑板： *inode 在磁盘上的位置 = 引导块大小 + 超级块大小 + s_imap_blocks大小 + s_zmap_blocks大小+它前面inode的大小

4.5 find_entry()：读取数据块中目录项

函数 find_entry 根据目录文件的 inode 在其对应 数据块中读取目录项数组，然后逐个目录项进行匹配，即 :

while(i<entries) if(match(namelen,name,de))< code></entries)>

//de是是什么意思: directory entry(目录项)
#define NAME_LEN 14
struct dir_entry
{
    unsigned short inode; //i节点号
    char name[NAME_LEN]; //文件名
}

//================================
//在fs/namei.c中
static struct buffer_head *find_entry(struct m_inode
**dir, char *name, ..., struct dir_entry ** res_dir)
{
    int entries=(*dir)->i_size/(sizeof(struct dir_entry));
    //将目录项一项一项读入内存，这是一个索引磁盘并读入的过程
    int block=(*dir)->i_zone[0];
    *bh=bread((*dir)->i_dev, block);
    struct dir_entry *de =bh->b_data;
    //entries是目录项数，持续循环来进行匹配
    while(i = BLOCK_SIZE+bh->b_data)
        {
            brelse(bh);
            block=bmap(*dir,i/DIR_ENTRIES_PER_BLOCK);
            bh=bread((*dir)->i_dev,block);
            de=(struct dir_entry*)bh->b_data;
        }
        //读入下一块上的目录项继续 match
        if(match(namelen,name,de))
        {
            *res_dir=de;return bh;
        }
            de++; i++;
    }
}

4.6 梳理总结

原始父进程--shell 进程，通过磁盘初始化得到了 根目录的inode；
之后的子进程创建时拷贝这个inode信息；
当文件访问开始，首先使用系统调用 open，open其实是包装函数，其具体代码在 get_dir 中实现；
get_dir 是整个过程的上层主控函数；
如果是根目录直接获取inode并开始解析根目录下的目录项，循环递归实现自举；
如果是普通目录，则也进行上述过程，不过需要解析 inode 所在的盘块号；
解析由 iget 来完成，有一个计算公式，mark 在 4.4 的结尾： inode 在磁盘上的位置 = 引导块大小 + 超级块大小 + s_imap_blocks大小 + s_zmap_blocks大小+它前面inode的大小
拿到 inode，需要据此找到其对应的数据块，在其中的目录项中匹配下一层文件，这就是最后 find_entry 做的事情；
一旦匹配，最后在 get_dir 返回的就是 inode， 拿到具体文件的 inode 后，就接入前3层抽象；
根据具体的read or write 调用，应用前3层抽象完成整个磁盘的读写。

这也是整个文件系统的流程，只不过省去了前3层hhh。

5. 操作系统全貌

这是整个课程笔记的最后一篇，后续或许会更新实验笔记，现在总结一下：

多进程视图
CPU管理相关内容
- 进程切换；
- 进程同步与合作；
- 信号量和锁；
某些进程需要使用内存，涉及内存管理的相关内容；
- 段页式管理；
- 虚拟内存，换入换出；
需要使用文件，涉及外设、磁盘相关内容；
- open进行目录解析
- read write 读写磁盘； 文件视图
各个部分并行执行，彼此之间可能还有合作。'
再加上系统接口与系统启动，就可以实现一个完整的操作系统。

Original: https://www.cnblogs.com/Roboduster/p/16705198.html
Author: climerecho
Title: 操作系统学习笔记13 | 目录与文件系统

Title: KenLM使用教程

1. 安装

git clone https://github.com/kpu/kenlm.git
cd kenlm/
mkdir -p build
cd  build
cmake ..

make -j 32

安装过程中可能会出现没有libboost库，engin3，执行命令:

sudo yum install boost-devel
sudo yum install eigen3

其他linux发行版，自行查找对应的安装方式。
测试安装是否成功， build/bin/lmplz，有显示则安装成功。将bin目录加入PATH，这样在任意目录下都可以使用bin下面的命令。

2. 训练

基本用法：

lmplz -o N --verbose_header --text your_corpus --arpa model.arpa

将 .arpa转成 .bin效果是一样的，但是速度会更快。

build_binary -s test.arpa test.bin

参数解释：
(1) --vocab_estimate
为了在corpus count计算预分配内存，默认词表大小为1000000，可以根据实际的词表大小进行设置（稍大词表大小）
(2) --verbose_header
生成的arpa文件头部显示一些信息，如各个文法元组的个数
(3) --text
需要训练的文本，事先得预处理好，去标点，正则化等等，训练词级别的N-gram需要进行分词，字级别的N-gram，只要把各个字符用空格空开就可
(4) --arpa
生成的arpa文件的名称
(5) --prune
剪枝操作，使用方法如： --prune 1 1 3 4，首先这四个位置的数字表示对应元组词频的阈值，即小于这个词频的元组会被剪枝掉，如 4 表示4-gram中元组出现次数小于4的需要被剪枝。另外需要注意，这一串数字需要满足 非递减 。
(6) --limit_vocab_file
指定词表文件，不在词表的字都会被剪枝掉。词表的形式是，用空格隔开每个单元，如我你他
(7) --discount_fallback
平滑操作
(8) --interpolate_unigrams
为了模拟srilm的实现，这个几乎用不上

3. Python接口

安装

pip install kenlm

以 kenlm/lm/test.arpa为例：

import kenlm
model=kenlm.LanguageModel('test.arpa')
print(model.score('this is a sentence.',bos = True,eos = True))

结果如下：
操作系统学习笔记13 | 目录与文件系统

Original: https://blog.csdn.net/qq_33424313/article/details/120726582
Author: 爱可乐的松鼠
Title: KenLM使用教程

2024 年 4 月
一	二	三	四	五	六	日
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

1. 第4层抽象描述：文件系统

2. 目录：多个文件的组织结构

3. 目录的实现思路和原理

3.1 目录的使用

3.2 目录下寻找文件

3.3 文件系统自举

3.4 总结

4. 目录解析的代码实现

4.1 open()：建立路径名到inode链接

4.2 get_dir：完成真正解析

4.3 mount_root：根目录的来源

4.4 iget()：读入目录节点

4.5 find_entry()：读取数据块中目录项

4.6 梳理总结

5. 操作系统全貌

相关阅读

Title: KenLM使用教程

1. 安装

2. 训练

3. Python接口