级调度算法

内存页面置换算法最佳页面置换算法OPT先进先出置换算法FIFO最近最久未使用的置换算法LRU时钟页面置换算法Lock最不常用置换算法LFU

磁盘调度算法先来先服务算法最短寻道时间优先算法扫描算法循环扫描算法

文件系统文件系统的基本组成虚拟文件系统文件的使用文件的存储连续空间存放方式非连续空间存放方式

空闲空间管理空闲表法空闲链表法位图法

顾名思义先来后到每次从就绪队列选择最先进入队列的进程然后一直运行直到进程退出或被阻塞才会继续从队列中选择第一个进程接着运行。

这似乎很公平但是当一个长作业先运行了那么后面的短作业等待的时间就会很长不利于短作业。

FCFS

SJF调度算法同样也是顾名思义它会优先选择运行时间最短的进程来运行这有助于提高系统的吞吐量。

比如一个长作业在就绪队列等待运行而这个就绪队列有非常多的短作业那么就会使得长作业不断的往后推周转时间变长致使长作业长期不会被运行。

高响应比优先调度算法

每次进行进程调度时先计算「响应比优先级」然后把「响应比优先级」最高的进程投入运行「响应比优先级」的计算公式

时间片轮转调度算法

每个进程被分配一个时间段称为时间片Quantum即允许该进程在该时间段中运行。

CPU

前面的「时间片轮转算法」做了个假设即让所有的进程同等重要也不偏袒谁大家的运行时间都一样。

但是对于多用户计算机系统就有不同的看法了它们希望调度是有优先级的即希望调度程序能从就绪队列中选择最高优先级的进程进行运行这称为最高优先级Highest

Priority

静态优先级创建进程时候就已经确定了优先级了然后整个运行时间优先级都不会变化动态优先级根据进程的动态变化调整优先级比如如果进程运行时间增加则降低其优先级如果进程等待时间就绪队列的等待时间增加则升高其优先级也就是随着时间的推移增加等待进程的优先级。

非抢占式当就绪队列中出现优先级高的进程运行完当前进程再选择优先级高的进程。

抢占式当就绪队列中出现优先级高的进程当前进程挂起调度优先级高的进程运行。

内存页面置换算法

最佳页面置换算法基本思路是置换在「未来」最长时间不访问的页面。

所以该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间然后比较选择未来最长时间不访问的页面。

这很理想但是实际系统中无法实现因为程序访问页面时是动态的我们是无法预知每个页面在「下一次」访问前的等待时间。

所以最佳页面置换算法作用是为了衡量你的算法的效率你的算法效率越接近该算法的效率那么说明你的算法是高效的。

先进先出置换算法FIFO

既然我们无法预知页面在下一次访问前所需的等待时间那我们可以选择在内存驻留时间很长的页面进行中置换这个就是「先进先出置换」算法的思想。

最近最久未使用LRU的置换算法的基本思路是发生缺页时选择最长时间没有被访问的页面进行置换也就是说该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

这种算法近似最优置换算法最优置换算法是通过「未来」的使用情况来推测要淘汰的页面而

LRU

还是以前面的请求的页面序列作为例子假设使用最近最久未使用的置换算法则过程如下图

LRU

LRU需要在内存中维护一个所有页面的链表最近最多使用的页面在表头最近最少使用的页面在表尾。

困难的是在每次访问内存时都必须要更新「整个链表」。

在链表中找到一个页面删除它然后把它移动到表头是一个非常费时的操作。

时钟页面置换算法Lock

该算法的思路是把所有的页面都保存在一个类似钟面的「环形链表」中一个表针指向最老的页面。

就淘汰该页面并把新的页面插入这个位置然后把表针前移一个位置如果访问位是

就清除访问位并把表针前移一个位置重复这个过程直到找到了一个访问位为

最不常用置换算法LFU

最不常用LFU算法这名字听起来很调皮但是它的意思不是指这个算法不常用而是当发生缺页中断时选择「访问次数」最少的那个页面并将其淘汰。

它的实现方式是对每个页面设置一个「访问计数器」每当一个页面被访问时该页面的访问计数器就累加

看起来很简单每个页面加一个计数器就可以实现了但是在操作系统中实现的时候我们需要考虑效率和硬件成本的。

要增加一个计数器来实现这个硬件成本是比较高的另外如果要对这个计数器查找哪个页面访问次数最小查找链表本身如果链表长度很大是非常耗时的效率不高。

但还有个问题LFU

算法只考虑了频率问题没考虑时间的问题比如有些页面在过去时间里访问的频率很高但是现在已经没有访问了而当前频繁访问的页面由于没有这些页面访问的次数高在发生缺页中断时就会可能会误伤当前刚开始频繁访问但访问次数还不高的页面。

磁盘调度算法

先来先服务First-ComeFirst-ServedFCFS顾名思义先到来的请求先被服务。

640

个磁道的距离这么一看这种算法比较简单粗暴但是如果大量进程竞争使用磁盘请求访问的磁道可能会很分散那先来先服务算法在性能上就会显得很差因为寻道时间过长。

最短寻道时间优先算法

但这个算法可能存在某些请求的饥饿因为本次例子我们是静态的序列看不出问题假设是一个动态的请求如果后续来的请求都是小于

183

磁道可能永远不会被响应于是就产生了饥饿现象这里产生饥饿的原因是磁头在一小块区域来回移动。

扫描算法

寻道时间优先算法会产生饥饿的原因在于磁头有可能再一个小区域内来回得移动。

为了防止这个问题可以规定磁头在一个方向上移动访问所有未完成的请求直到磁头到达该方向上的最后的磁道才调换方向这就是扫描Scan算法。

这种算法也叫做电梯算法比如电梯保持按一个方向移动直到在那个方向上没有请求为止然后改变方向。

循环扫描算法

扫描算法使得每个磁道响应的频率存在差异那么要优化这个问题的话可以总是按相同的方向进行扫描使得每个磁道的响应频率基本一致。

循环扫描Circular

规定只有磁头朝某个特定方向移动时才处理磁道访问请求而返回时直接快速移动至最靠边缘的磁道也就是复位磁头这个过程是很快的并且返回中途不处理任何请求该算法的特点就是磁道只响应一个方向上的请求。

循环扫描算法相比于扫描算法对于各个位置磁道响应频率相对比较平均。

文件系统

编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。

索引节点是文件的唯一标识它们之间一一对应也同样都会被存储在硬盘中所以索引节点同样占用磁盘空间。

项的层级关联关系。

多个结构但它与索引节点不同的是目录项是由内核维护的一个数据结构不存放于磁盘而是缓存在内存。

由于索引节点唯一标识一个文件而项和索引节点的关系是多对一也就是说一个文件可以有多个别名。

比如硬链接的实现就是多个项和是个文件持久化存储在磁盘而频繁从磁盘读效率会很低所以内核会把已经读过的项这个数据结构缓存在内存下次再次读到相同的项这个数据结构不只是表示项以及文件数据的关系下面这个图就很好的展示了它们之间的关系

索引节点是存储在硬盘上的数据那么为了加速文件的访问通常会把索引节点加载到内存中。

另外磁盘进行格式化的时候会被分成三个存储区域分别是超级块、索引节点区和数据块区。

超级块用来存储文件系统的详细信息比如块个数、块大小、空闲块等等。

索引节点区用来存储索引节点数据块区用来存储文件或目录数据

我们不可能把超级块和索引节点区全部加载到内存这样内存肯定撑不住所以只有当需要使用的时候才将其加载进内存它们加载进内存的时机是不同的

超级块当文件系统挂载时进入内存索引节点区当文件被访问时进入内存

虚拟文件系统

文件系统的种类众多而操作系统希望对用户提供一个统一的接口于是在用户层与文件系统层引入了中间层这个中间层就称为虚拟文件系统Virtual

File

定义了一组所有文件系统都支持的数据结构和标准接口这样程序员不需要了解文件系统的工作原理只需要了解

VFS

文件系统中用户空间、系统调用、虚拟文件系统、缓存、文件系统以及存储之间的关系如下图

Linux

等都是这类文件系统。

内存的文件系统这类文件系统的数据不是存储在硬盘的而是占用内存空间我们经常用到的

/proc

文件系统都属于这一类读写这类文件实际上是读写内核中相关的数据。

网络的文件系统用来访问其他计算机主机数据的文件系统比如

NFS、SMB

我们从用户角度来看文件的话就是我们要怎么使用文件首先我们得通过系统调用来打开一个文件。

首先用

我们打开了一个文件后操作系统会跟踪进程打开的所有文件所谓的跟踪呢就是操作系统为每个进程维护一个打开文件表文件表里的每一项代表「文件描述符」所以说文件描述符是打开文件的标识。

**文件指针**系统跟踪上次读写位置作为当前文件位置指针这种指针对打开文件的某个进程来说是唯一的**文件打开计数器**文件关闭时操作系统必须重用其打开文件表条目否则表内空间不够用。

因为多个进程可能打开同一个文件所以系统在删除打开文件条目之前必须等待最后一个进程关闭文件该计数器跟踪打开和关闭的数量当该计数为

时系统关闭文件删除该条目**文件磁盘位置**绝大多数文件操作都要求系统修改文件数据该信息保存在内存中以免每个操作都从磁盘中读取**访问权限**每个进程打开文件都需要有一个访问模式创建、只读、读写、添加等该信息保存在进程的打开文件表中以便操作系统能允许或拒绝之后的

I/O

在用户视角里文件就是一个持久化的数据结构但操作系统并不会关心你想存在磁盘上的任何的数据结构操作系统的视角是如何把文件数据和磁盘块对应起来。

所以用户和操作系统对文件的读写操作是有差异的用户习惯以字节的方式读写文件而操作系统则是以数据块来读写文件那屏蔽掉这种差异的工作就是文件系统了。

当用户进程从文件读取

个字节大小的数据时文件系统则需要获取字节所在的数据块再返回数据块对应的用户进程所需的数据部分。

当用户进程把

个字节大小的数据写进文件时文件系统则找到需要写入数据的数据块的位置然后修改数据块中对应的部分最后再把数据块写回磁盘。

文件的数据是要存储在硬盘上面的数据在磁盘上的存放方式就像程序在内存中存放的方式那样有以下两种

连续空间存放方式非连续空间存放方式

其中非连续空间存放方式又可以分为**「链表方式」和「索引方式」**。

不同的存储方式有各自的特点重点是要分析它们的存储效率和读写性能接下来分别对每种存储方式说一下。

连续空间存放方式

连续空间存放方式顾名思义文件存放在磁盘「连续的」物理空间中。

这种模式下文件的数据都是紧密相连读写效率很高因为一次磁盘寻道就可以读出整个文件。

使用连续存放的方式有一个前提必须先知道一个文件的大小这样文件系统才会根据文件的大小在磁盘上找到一块连续的空间分配给文件。

所以文件头里需要指定「起始块的位置」和「长度」有了这两个信息就可以很好的表示文件存放方式是一块连续的磁盘空间。

连续空间存放的方式虽然读写效率高但是有「磁盘空间碎片」和「文件长度不易扩展」的缺陷。

如下图如果文件

被删除磁盘上就留下一块空缺这时如果新来的文件小于其中的一个空缺我们就可以将其放在相应空缺里。

但如果该文件的大小大于所有的空缺但却小于空缺大小之和则虽然磁盘上有足够的空缺但该文件还是不能存放。

当然了我们可以通过将现有文件进行挪动来腾出空间以容纳新的文件但是这个在磁盘挪动文件是非常耗时所以这种方式不太现实。

要想扩大一下需要更多的磁盘空间唯一的办法就只能是挪动的方式前面也说了这种方式效率是非常低的。

那么有没有更好的方式来解决上面的问题呢答案当然有既然连续空间存放的方式不太行那么我们就改变存放的方式使用非连续空间存放方式来解决这些缺陷。

非连续空间存放方式

链表的方式存放是离散的不用连续的于是就可以消除磁盘碎片可大大提高磁盘空间的利用率同时文件的长度可以动态扩展。

根据实现的方式的不同链表可分为「隐式链表」和「显式链接」两种形式。

文件要以「隐式链表」的方式存放的话实现的方式是文件头要包含「第一块」和「最后一块」的位置并且每个数据块里面留出一个指针空间用来存放下一个数据块的位置这样一个数据块连着一个数据块从链头开始就可以顺着指针找到所有的数据块所以存放的方式可以是不连续的。

隐式链表的存放方式的缺点在于无法直接访问数据块只能通过指针顺序访问文件以及数据块指针消耗了一定的存储空间。

隐式链接分配的稳定性较差系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏会导致文件数据的丢失。

如果取出每个磁盘块的指针把它放在内存的一个表中就可以解决上述隐式链表的两个不足**。

那么这种实现方式是「显式链接」它指把用于链接文件各数据块的指针显式地存放在内存的一张链接表中该表在整个磁盘仅设置一张每个表项中存放链接指针指向下一个数据块号。

**内存中的这样一个表格称为文件分配表。

由于查找记录的过程是在内存中进行的因而不仅显著地提高了检索速度而且大大减少了访问磁盘的次数。

但也正是整个表都存放在内存中的关系它的主要的缺点是不适用于大磁盘。

比如对于

链表的方式解决了连续分配的磁盘碎片和文件动态扩展的问题但是不能有效支持直接访问FAT除外索引的方式可以解决这个问题。

索引的实现是为每个文件创建一个「索引数据块」里面存放的是指向文件数据块的指针列表说白了就像书的查就可以。

另外文件头需要包含指向「索引数据块」的指针这样就可以通过文件头知道索引数据块的位置再通过索引数据块里的索引信息找到对应的数据块。

文件的创建、增大、缩小很方便不会有碎片的问题支持顺序读写和随机读写

由于索引数据也是存放在磁盘块的如果文件很小明明只需一块就可以存放的下但还是需要额外分配一块来存放索引数据所以缺陷之一就是存储索引带来的开销。

如果文件很大大到一个索引数据块放不下索引信息这时又要如何处理大文件的存放呢我们可以通过组合的方式来处理大文件的存。

先来看看链表

索引的组合这种组合称为「链式索引块」它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针于是当一个索引数据块的索引信息用完了就可以通过指针的方式找到下一个索引数据块的信息。

那这种方式也会出现前面提到的链表方式的问题万一某个指针损坏了后面的数据也就会无法读取了。

索引的方式这种组合称为「多级索引块」实现方式是通过一个索引块来存放多个索引数据块一层套一层索引。

空闲空间管理

前面说到的文件的存储是针对已经被占用的数据块组织和管理接下来的问题是如果我要保存一个数据块我应该放在硬盘上的哪个位置呢难道需要将所有的块扫描一遍找个空的地方随便放吗

空闲表法

空闲表法就是为所有空闲空间建立一张表表内容包括空闲区的第一个块号和该空闲区的块个数注意这个方式是连续分配的。

如下图

当请求分配磁盘空间时系统**依次扫描空闲表里的内容直到找到一个合适的空闲区域为止。

**当用户撤销一个文件时系统回收文件空间。

这时也需顺序扫描空闲表寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

**这种方法仅当有少量的空闲区时才有较好的效果。

因为如果存储空间中有着大量的小的空闲区则空闲表变得很大这样查询效率会很低。

**另外这种分配技术适用于建立连续文件。

空闲链表法

我们也可以使用「链表」的方式来管理空闲空间每一个空闲块里有一个指针指向下一个空闲块这样也能很方便的找到空闲块并管理起来。

如下图

当创建文件需要一块或几块时就从链头上依次取下一块或几块。

反之当回收空间时把这些空闲块依次接到链头上。

这种技术只要在主存中保存一个指针令它指向第一个空闲块。

其特点是简单但不能随机访问工作效率低因为每当在链上增加或移动空闲块时需要做很多

I/O

空闲表法和空闲链表法都不适合用于大型文件系统因为这会使空闲表或空闲链表太大。

位图法

位图是利用二进制的一位来表示磁盘中一个盘块的使用情况磁盘上所有的盘块都有一个二进制位与之对应。

当值为

1111110011111110001110110111111100111

...

文件系统就采用了位图的方式来管理空闲空间不仅用于数据空闲块的管理还用于

inode索引节点

整个文件系统的结构和块组的内容文件系统都由大量块组组成在硬盘上相继排布

最前面的第一个块是引导块在系统启动时用于启用引导接着后面就是一个一个连续的块组了块组的内容如下

inode

个数、每个块组的块个数等等。

块组描述符包含文件系统中各个块组的状态比如块组中空闲块和

inode

的数目等每个块组都包含了文件系统中「所有块组的组描述符信息」。

数据位图和

inode

用于保存文件系统中与各个文件和目录相关的所有元数据。

数据块包含文件的有用数据。

你可以会发现每个块组里有很多重复的信息比如超级块和块组描述符表这两个都是全局信息而且非常的重要这么做是有两个原因

如果系统崩溃破坏了超级块或块组描述符有关文件系统结构和内容的所有信息都会丢失。

如果有冗余的副本该信息是可能恢复的。

通过使文件和管理数据尽可能接近减少了磁头寻道和旋转这可以提高文件系统的性能。

在前面我们知道了一个普通文件是如何存储的但还有一个特殊的文件经常用到的其实也是个文件你甚至可以通过

vim

和普通文件不同的是普通文件的块里面保存的是文件数据而里面一项一项的文件信息。

列表中每一项就代表该第二项是「..」表示上一级有超级多的文件我们要想在这个的格式改成哈希表**对文件名进行哈希计算把哈希值保存起来如果我们要查找一个的内容这种方法的优点是查找非常迅速插入和删除也较简单不过需要一些预备措施来避免哈希冲突。

缓存在内存以后要使用该文件时只要在内存中操作从而降低了磁盘操作次数提高了文件系统的访问速度。

软链接和硬链接

inode那么只有删除文件的所有硬链接以及源文件时系统才会彻底删除该文件。

inode但是这个文件的内容是另外一个文件的路径所以访问软链接的时候实际上相当于访问到了另外一个文件所以软链接是可以跨文件系统的甚至目标文件被删除了链接文件还是在的只不过指向的文件找不到了而已。

I/O

文件操作的标准库是可以实现数据的缓存那么根据**「是否利用标准库缓冲」**可以把文件

I/O

I/O利用的是标准库的缓存实现文件的加速访问而标准库再通过系统调用访问文件。

非缓冲

比方说很多程序遇到换行时才真正输出而换行前的内容其实就是被标准库暂时缓存了起来这样做的目的是减少系统调用的次数毕竟系统调用是有

CPU

次数在系统调用后会把用户数据拷贝到内核中缓存起来这个内核缓存空间也就是「页缓存」只有当缓存满足某些条件的时候才发起磁盘

I/O

I/O不会发生内核缓存和用户程序之间数据复制而是直接经过文件系统访问磁盘。

非直接

I/O读操作时数据从内核缓存中拷贝给用户程序写操作时数据从用户程序拷贝给内核缓存再由内核决定什么时候写入数据到磁盘。

O_DIRECT

的最后当发现内核缓存的数据太多的时候内核会把数据写到磁盘上用户主动调用

sync内核缓存会刷到磁盘上当内存十分紧张无法再分配页面时也会把内核缓存的数据刷到磁盘上内核缓存的数据的缓存时间超过某个时间时也会把数据刷到磁盘上

Page

cache**它是文件系统中用于缓存文件数据的缓冲所以即使进程崩溃了文件数据还是保留在内核的

page

里的文件数据在持久化到磁盘化到磁盘之前系统发生了崩溃那这部分数据就会丢失了。

fsync

函数在写文文件的时候立刻将文件数据持久化到磁盘这样就可以解决系统崩溃导致的文件数据丢失的问题。

Page

也有其劣势最直接的缺点是需要占用额外物理内存空间物理内存在比较紧俏的时候可能会导致频繁的

swap

I/O用户空间要读写一个文件并不直接与磁盘交互而是中间夹了一层缓存即

page

“直接”在这里还有另一层语义其他所有技术中数据至少需要在内核空间存储一份但是在

Direct

我们的电脑设备可以接非常多的输入输出设备比如键盘、鼠标、显示器、网卡、硬盘、打印机、音响等等每个设备的用法和功能都不同那操作系统是如何把这些输入输出设备统一管理的呢?

为了屏蔽设备之间的差异每个设备都有一个叫设备控制器Device

Control

块设备把数据存储在固定大小的块中每个块有自己的地址硬盘、USB

是常见的块设备。

字符设备以字符为单位发送或接收一个字符流字符设备是不可寻址的也没有任何寻道操作鼠标是常见的字符设备。

块设备通常传输的数据量会非常大于是控制器设立了一个可读写的数据缓冲区。

CPU

写入数据到控制器的缓冲区时当缓冲区的数据囤够了一部分才会发给设备。

CPU

从控制器的缓冲区读取数据时也需要缓冲区囤够了一部分才拷贝到内存。

:::info

I/O将所有控制寄存器映射到内存空间中这样就可以像读写内存一样读写数据缓冲区。

I/O

给设备发送了一个指令让设备控制器去读设备的数据它读完的时候要怎么通知

CPU

控制器的寄存器一般会有状态标记位用来标识输入或输出操作是否完成。

于是我们想到第一种轮询等待的方法让

CPU

一直查寄存器的状态直到状态标记为完成很明显这种方式非常的傻瓜它会占用

CPU

中断通知操作系统数据已经准备好了。

我们一般会有一个硬件的中断控制器当设备完成任务后触发中断到中断控制器中断控制器就通知

另外中断有两种一种软中断例如代码调用

控制器下发指令告诉它想读取多少数据读完的数据放在内存的某个地方就可以了接下来DMA

控制器会向磁盘控制器发出指令通知它从磁盘读数据到其内部的缓冲区中接着磁盘控制器将缓冲区的数据传输到内存当磁盘控制器把数据传输到内存的操作完成后磁盘控制器在总线上发出一个确认成功的信号到

DMA

控制器发送指令然后返回去做其他事情当磁盘数据拷贝到内存后DMA

CPU

数据已经准备好了可以从内存读数据了。

仅仅在传送开始和结束时需要

CPU

虽然设备控制器屏蔽了设备的众多细节但每种设备的控制器的寄存器、缓冲区等使用模式都是不同的所以为了屏蔽「设备控制器」的差异引入了设备驱动程序。

设备控制器不属于操作系统范畴它是属于硬件而设备驱动程序属于操作系统的一部分操作系统的内核代码可以像本地调用代码一样使用设备驱动程序的接口而设备驱动程序是面向设备控制器的代码它发出操控设备控制器的指令后才可以操作设备控制器。

不同的设备控制器虽然功能不同但是**设备驱动程序会提供统一的接口给操作系统这样不同的设备驱动程序就可以以相同的方式接入操作系统。

**如下图

I/O

为了提高文件访问的效率会使用页缓存、索引节点缓存、目录项缓存等多种缓存机制目的是为了减少对块设备的直接调用。

为了提高块设备的访问效率

看完前面的内容相信你对输入输出设备的管理有了一定的认识那接下来就从操作系统的角度回答开头的问题「键盘敲入字母时操作系统期间发生了什么」

CPU

那当用户输入了键盘字符键盘控制器就会产生扫描码数据并将其缓冲在键盘控制器的寄存器中紧接着键盘控制器通过总线给

CPU

键盘的中断处理程序是在键盘驱动程序初始化时注册的那键盘中断处理函数的功能就是从键盘控制器的寄存器的缓冲区读取扫描码再根据扫描码找到用户在键盘输入的字符把扫描码翻译成对应显示字符的

ASCII

码放到**「读缓冲区队列」接下来就是要把显示字符显示屏幕了显示设备的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」最后把「写缓冲区队列」的数据一个一个写入到显示设备的控制器的寄存器中的数据缓冲区最后将这些数据显示在屏幕里。

**

网络系统