搞了点资料搜索和自行yy

本来就写了写文件系统,后来干脆扩展到整个操作系统了。

一般来说理清这种问题有两种不同的视角。

文件系统

进程角度

每个进程自己都维护了两个dentry 一个是文件系统的根的dentry另一个就是当前工作目录的dentry

什么是dentry?

对于这样一个路径 /home/kvrmnks/a

/ 这个路径对应了一个dentry

/home 这个路径对应了一个dentry

/home/kvrmnks 这个路径也对应了一个dentry

dentry就是描述一个目录的数据结构。

这个数据结构不存在外存,仅仅存在于内存(当然内存交换的时候并不考虑)。

这个数据结构中存放了对应文件(包括文件夹和文件外设blabla,文中文件均为UNIX下的文件定义)的inode节点。

也存放了目录下的子dentry,当然还有父dentry。

什么是inode?

由于inode同时存在于外设内存,文中用外设inode与内存inode,进行区分,没有前缀时代表共同点。

inode中存放了文件的元数据(创建时间,修改时间,访问权限,大小,块大小等)

内存inode中存放有对应目录下的dentry,当然也有一些比如读写指针的数据。

到这里就可以发现,在内存inode和dentry可以互相访问,当然是一对多的关系(注意这里并不意味着访问不可一对一),毕竟不同目录可以指向同一个文件(inode)。

如果索引文件?

其实十分显然,首先不考虑有mount和软硬链接以及dentry缓存的情况下。

首先判断是从root开始找,还是从工作目录开始找,找到dentry。

看看是不是找到了,否则就从dentry的子dentry里找,重复以上过程,直到找到对应的dentry,返回内存inode。

拿到内存inode了怎么进行操作呢?

首先系统会创建一个file数据结构来代表这个进程打开的文件(当然可以联系一下课上内容,这里其实是内核创建了这个file数据结构,进程得到了指针,指向了内核中的file数据结构),这个数据结构也是不存在于外设上的。

这个数据结构理所当然地有着指向内存inode的指针(不然它有什么用)。

干嘛还要再用file封装一层呢,用inode不好吗?

不好,因为存在多个用户打开同一个文件或者一个用户不同进程多次打开一个文件的情况,联系到内存inode中存放着读写指针,显然不可能对每一次打开多维护一个,于是就重新封装了一层,封装成file,实则操作file时操作内存inode。

怎么操作file数据结构呢?

首先UNIX中抽象出了VFS这种东西,实现方式之一就是对于每个数据结构维护一个函数指针表,通过这个指针表来进行操作。

操作系统角度

从操作系统的角度来看主要的问题便是考虑如何维护以上出现地数据结构。

首先不考虑mount,缓存的情况下,mount的存在像是给整个系统打了个补丁,于是先不考虑。

dentry都不在外设里,怎么维护呢?

首先dentry是随着内核运行动态创建的,起始的目录存放在superblock中。

但是连dentry都没有,该怎么访问一个目录下的文件呢?

~~一开始确实被这个问题困扰了好久~~,不过想想看目录也是一个文件,其文件数据就是子文件了。

superblock是什么?

superblock存放着整个文件系统的元数据,比如块大小等。

当然对于不同的文件系统来说,superblock的定义也可能不同。

内存superblock中存放着所有内存inode的指针。

如此说来,内核中对于一个文件系统需要维护一个superblock,所有的内存inode节点,以及随着运行动态创建的dentry。

为了给进程操作文件,也要维护一个全局的file数据结构链表。

其中dentry形成一颗树的形状,每个节点指向了内存inode。

内存inode中存放着文件的元数据。

那么在加入mount的情况下,会发生什么样的变化呢?

首先每个dentry多加了一个标记位,来标记这个dentry是不是被mount了。

同时内核需要维护一棵mount数据结构树

mount数据结构中维护了父mount指针,mount挂载的dentry,mount的root dentry,还有子mount链表。

主要的修改在索引文件时,如果当前的dentry被标记了被mount

从父mount中搜索子mount链表,查看子mount中的挂载dentry,如果匹配,跳到子mount的root dentry,继续以上流程。

mount同时也会带来其他的影响,比如由于文件系统类型的不同,处理函数也会发生相应的改变,同样利用函数指针表的方式进行解决。

在添加缓存的情况下呢?

其实也没啥,无非就是内存inode可能不全了,不需要的时候就写回到外设。


同步与死锁

关于饥饿

显然在进程管理(CPU调度),外设管理等地方也涉及到了饥饿这个概念。

但是在不同地方讨论饥饿时完全有可能陷入主语的混乱。

在外设管理的地方,磁盘的调度算法(非先来先服务)有可能会产生饥饿,更详细地说,是导致有些请求永远也无法响应。

在进程管理中,一些调度算法也会产生饥饿,例如FIFO,又如设定优先级的方法,这时候饥饿的结果是一些进程永远也无法被调度到。

而这里的饥饿的表述则更加模糊,甚至在我个人的理解里,似乎所有除了死锁之外的导致并发出现问题的情形都叫饥饿。

讨论有关同步与死锁的饥饿时,理应应该将进程管理的饥饿抛出在讨论范围

例如在哲学家就餐问题中,如果一直只允许1个哲学家就餐,也不能说发生了死锁,程序也能一直执行不会中断。

但是这样导致的结果是其他哲学家被饿死了。

再比如一座桥,有来回两个方向,设置了优先级,保证每次先从南到北,这样程序也可以正常运行,但是会导致从北向南的车辆拥堵,这也是这里讨论的一种饥饿。

那么是不是定义这里的饥饿为“每个线程,都可以机会均等地进入临界区”,或者是课本上那句有关判断是否解决了缓冲区问题的判据“一个线程等待其他线程进入临界区的次数是有上界的”等等诸如此类意思的句子。

很容易就能给出“反例”,例如进入了临界区,然后发现什么也操作不了。

于是就产生了同步与死锁这里“饥饿”定义的混乱。当然我也没什么好办法。

关于在资源分配图上检查是否发生死锁的算法

本来以为经典算法已经达到下界了,就在尝试能不能证明这个下界,尝试了许多问题的归约,最后发现能给出一个更好的算法。。。

首先定义一些记号,定义图\(G = <V, E>\)为资源分配图,\(P\)为进程集合,\(F\)表示资源集合。

首先对于\(P\)中的每一个元素,枚举出边到\(F\)中的元素,\(F\)中元素上标记,还需要分配多少这类资源。

每个\(F\)上进行排序,显然可以维护一个指针,因为在释放的时候是单调的。

突然不想写了,大不了当个练习题,总之这个复杂度是\(O(E + VlogV)\)

关于“预防”和“避免”

个人也不知道为什么要用这么两个十分相近的词语来混淆概念,总之这里提供一个大概可行的意会方式。

预防 prevent 避免 avoid

避免代表死锁可能发生,但是操作系统“绕”了过去

预防代表死锁根本不可能发生,因为其必要条件被破坏掉了。


总之就是胡说完了(

参考文献1

参考文献2

参考文献3