Tutorialspoint 操作系统教程

原创 yBmZlQzJ 2023-08-17

251

Tutorialspoint 操作系统教程

来源：易百教程

操作系统教程™

本操作系统教程提供了操作系统的基本和高级概念。我们的操作系统教程是面向初学者，专业人士等来设计的。在完成对每个概念的深入研究之后，编写了本教程。

内容详细描述，并有能力回答您想要了解的大部分内容和问题。该教程还包含基于问题的一些示例，这些问题将帮助您以实际的方式解决问题。

操作系统可以被定义为用户和硬件之间的接口。它为用户提供了一个环境，使用户可以方便快捷地完成任务。

操作系统教程根据其功能（如进程管理，进程同步，死锁和文件管理）分为多个部分。

前提条件

在学习操作系统教程之前，您必须掌握计算机系统运行方式的基本知识。

面向读者

本操作系统教程旨在帮助初学者，专业人士和计算机爱好者。

问题反馈

我们不能保证您在学习此操作系统教程的过程中不会遇到任何问题。本教程中的讲解，示例和代码等只是根据作者的理解来概括写出。由于作者水平和能力有限，因此不保正所有编写的文章都准确无误。但是如果有遇到任何错误或问题，请反馈给我们，我们会及时纠正以方便后续读者阅读。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统的定义和功能 - 操作系统教程™

在计算机系统(包括硬件和软件)中，硬件只能理解机器代码(以0和1的形式代码)，这对于一般的用户来说没有任何意义。

我们需要一个可以充当中介的系统，并管理系统中存在的所有进程和资源。

操作系统可以被定义为用户和硬件之间的接口。它负责执行所有进程，资源分配，CPU管理，文件管理和许多其他任务。

操作系统的目的是提供一种用户可以方便有效地执行程序的环境。

计算机系统的结构

计算机系统包括:

用户(使用电脑的人)
应用程序(编译器，数据库，，视频播放器，浏览器等)
系统程序(Shell，编辑器，编译器等)
操作系统(作为用户和硬件之间的接口的特殊程序)
硬件(CPU，磁盘，内存等)

操作系统做什么？

进程管理
进程同步
内存管理
CPU调度
文件管理
安全

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统的类型 - 操作系统教程™

当前场景中存在许多类型的操作系统:

批量操作系统

在20世纪70年代，批处理非常受欢迎。作业(job)分批执行。人们习惯于拥有一台称为大型机的计算机。

在批量操作系统中，可以访问多个人; 他们将各自的工作提交给系统执行。

系统根据先到先得的原则将所有工作放入队列中，然后逐个执行工作。用户在所有作业执行时收集各自的输出。

批处理操作系统的缺点

1. 饥饿

批处理经常遭受饥饿。如果批次中存在五个作业J1，J2，J3，J4，J4和J5。如果J1的执行时间非常长，那么其他四个作业将永远不会执行，否则他们将不得不等待很长时间。因此，其他进程饿死了。

2.不交互

批处理不适合依赖于用户输入的作业。如果一项工作需要从控制台输入两个数字，那么它将永远不会在批处理场景中获得它，因为用户在执行时不在场。

多程序操作系统

多程序是对CPU始终处于繁忙状态的批处理的扩展。每个进程需要两种类型的系统时间:CPU时间和IO时间。

在多程序环境中，当进程执行其I/O时，CPU可以开始执行其他进程。因此，多程序可以提高系统的效率。

多处理操作系统

在多处理中，实现了并行计算。系统中有多个处理器可以同时执行多个进程。这将增加系统的吞吐量。

实时操作系统

在实时系统中，每项工作都有一定的截止期限，在这个截止期限内工作应该完成，否则将有巨大的损失，或者即使产生了结果，它也是完全无用的。

实时系统的应用存在于军事应用中，如果要随意射出导弹，那么导弹应该以一定的精度下降。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

进程管理

与进程有关的时间 - 操作系统教程™

与过程有关的各种时间，如下图所示 -

1. 到达时间

进程进入就绪队列的时间称为到达时间。

2. 突发时间

CPU执行整个过程所需的总时间称为突发时间。这不包括等待时间。即使在执行之前计算一个过程的执行时间也是令人困惑的，因此基于突发时间的调度问题无法在现实中实现。

3. 完成时间
进程进入完成状态的时间或进程完成其执行的时间称为完成时间。

4. 周转时间
该过程从抵达到完成所花费的时间总量称为周转时间。

5. 等待时间
进程等待CPU分配的总时间称为等待时间。

6. 响应时间
到达时间和进程首次获取CPU的时间之间的差异称为响应时间。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统CPU调度 - 操作系统教程™

在像MS DOS这样的单编程系统中，当进程等待任何I/O操作完成时，CPU仍然是空闲的。这是一个开销，因为它浪费时间并导致饥饿问题。但是，在多程序系统中，CPU在进程的等待时间内不会保持空闲状态，而是开始执行其他进程。操作系统必须定义CPU将被给予哪个进程。

在多程序系统中，操作系统调度CPU上的进程以获得最大的利用率，此过程称为CPU调度。操作系统使用各种调度算法来调度过程。

这是短期调度程序的一项任务，用于调度CPU以查找作业池中存在的进程数量。每当运行进程请求某个I/O操作时，短期调度程序就会保存进程的当前上下文(也称为PCB)并将其状态从运行状态更改为等待状态。在此期间，进程处于等待状态; 短期调度程序从就绪队列中选择另一个进程并将CPU分配给此进程。这个过程被称为上下文切换。

进程控制块中保存了什么？

操作系统在进程的生命周期中维护一个进程控制块。进程终止或终止时，进程控制块将被删除。有以下信息保存在过程控制块中，并随过程状态而变化。

为什么需要调度？

在多道程序中，如果长期调度程序选择更多的I/O绑定进程，那么大多数时候CPU仍然是空闲的。操作系统的任务是优化资源的利用。

如果大多数正在运行的进程将其状态从运行状态更改为等待状态，那么系统中可能始终存在死锁。因此，为了减少这种开销，操作系统需要调度作业以获得CPU的最佳利用率并避免死锁的可能性。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统调度算法 - 操作系统教程™

操作系统使用各种算法来有效地调度处理器上的进程。

调度算法的目的

最大CPU利用率
公平分配CPU
最大吞吐量
最短周转时间
最短的等待时间
最短响应时间

有以下算法可用于计划作业。

1. 先来先服务

这是最简单的算法。最短到达时间的过程将首先获得CPU。到达时间越少，进程得到CPU的速度越快。这是非抢先式的调度。

2. 轮循

在循环调度算法中，操作系统定义了一个时间片(片)。所有的进程将以循环方式执行。每个进程都会获得CPU一小段时间(称为时间片)，然后返回就绪队列等待下一个回合。这是一种抢先式调度。

3. 最短作业第一
具有最短爆发时间的作业将首先获得CPU。突发时间越短，进程得到CPU的速度越快。这是非抢先式的调度。

4. 首先剩余时间最短
这是SJF的抢先形式。在该算法中，操作系统根据执行的剩余时间安排作业。

5. 基于优先级的调度

在这个算法中，优先级将被分配给每个进程。优先级越高，进程得到CPU的速度越快。如果两个进程的优先级相同，则会根据他们的到达时间进行安排。

6. 最高响应率下一个

在这种调度算法中，下一步将调度响应比率最高的进程。这减少了系统中的饥饿。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统FCFS调度 - 操作系统教程™

先来先服务(FCFS)调度算法根据其到达时间简单地调度作业。就绪队列中第一个工作将首先获得CPU。工作到达时间越少，工作得到的CPU就越快。如果第一个进程的突发时间是所有作业中最长的，则FCFS调度可能会导致饥饿问题。

FCFS的优势

简单
容易
先到先得

FCFS的缺点

调度方法是非抢先式的，该进程将运行到完成。
由于算法的非抢先性，可能会出现饥饿问题。
尽管实现起来很容易，但由于平均等待时间比其他调度算法更高，因此性能较差。

示例

我们来看一个FCFS调度算法的例子。在下面的时间表中，有5个进程的进程ID为P0，P1，P2，P3和P4。 P0到达时间0，P1在时间1，P2在时间2，P3到达时间3，处理P4在时间4到达就绪队列。下表给出了过程及其各自的到达时间和爆发时间。

周转时间和等待时间通过使用以下公式计算。

Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turnaround time - Burst Time

平均等待时间通过将所有过程的各个等待时间相加并且将总和除以过程的总数来确定。

进程ID	到达时间	突发时间	完成时间	转换时间	等待时间
0	0	2	2	2	0
1	1	6	8	7	1
2	2	4	12	8	4
3	3	9	21	18	9
4	4	12	33	19	17

平均等待时间= 31/5

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统FCFS护航效果 - 操作系统教程™

如果第一个作业的爆发时间是最高的，FCFS可能会受到队列影响。就像在现实生活中一样，如果队列在路上经过，那么其他人可能会被堵塞，直到完全通过。这也可以在操作系统中进行模拟。

如果CPU在就绪队列的前端获得较高突发时间的进程，则较低突发时间的进程可能被阻塞，这意味着如果执行中的作业具有非常高的突发时间，则它们可能永远不会获得CPU。这被称为队列效应或饥饿。

示例

在这个例子中，我们有3个进程被命名为P1，P2和P3。进程P1的暴发时间最高。

下表中的周转时间和等待时间通过公式计算，

Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time

在第一种情况下，虽然流程P1到达队列中的第一个，该过程的爆发时间是最高的。由于调度算法，我们所遵循的是FCFS，因此CPU将首先执行Process P1。

在这个时间表中，系统的平均等待时间将非常高。这是因为车队的影响。其他进程P2，P3必须等待40个单位时间，尽管他们的爆发时间非常短。这个时间表遭受饥饿。

进程ID	到达时间	突发时间	完成时间	转换时间	等待时间
1	0	40	40	40	0
2	1	3	43	42	39
2	2	4	12	8	4
3	1	1	44	43	42

平均等待时间= 81/3

在第二种情况下，如果进程P1本来就已经到达队列的最后，而其他过程P2和P3早于那么饥饿问题就不存在了。

以下示例显示了这两种情况的等待时间的偏差。虽然时间表的长度是相同的，即44个单位，但是在这个时间表中等待时间将会减少。

进程ID	到达时间	突发时间	完成时间	转换时间	等待时间
1	1	40	44	43	3
2	0	3	3	3	0
2	2	4	12	8	4
3	0	1	4	4	3

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统FCFS与开销 - 操作系统教程™

在上面的例子中，我们假设所有的进程只是CPU绑定进程。但是也忽略了上下文切换时间。

然而，如果考虑调度器在上下文切换中花费的时间，则系统的平均等待时间将增加，这也影响系统的效率。

上下文切换始终是开销。以下示例描述如果在系统中考虑上下文切换时间，效率将受到影响。

示例

在下面的例子中，假设有五个进程:P1，P2，P3，P4，P5和P6。他们的到达时间和爆发时间如下。

进程ID	到达时间	突发时间
1	0	3
2	1	2
3	2	1
4	3	4
5	4	5
6	5	2

如果系统的上下文切换时间为1个单位，那么系统的甘特图将按如下准备。

给定δ= 1个单位;

在执行每个进程之后，系统将花费额外的1个单位时间(开销)来安排下一个过程。

Inefficiency= (6/23) X 100 %

Efficiencyͷ = (1-6/23) X 100 %

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

操作系统最短作业优先（SJF）调度 - 操作系统教程™

到目前为止，我们根据它们的到达时间(在FCFS调度中)调度这些进程。但是，SJF调度算法根据其突发时间安排进程。

在SJF调度中，就绪队列中可用进程列表中的突发时间最短的进程将在下一个进行调度。

然而，预测一个过程所需的突发时间是非常困难的，因此这个算法在系统中很难实现。

SJF的优势

最大吞吐量
最低的平均等候时间和周转时间

SJF的缺点

可能会面临饥饿问题
这是不可实现的，因为一个进程的确切爆发时间不能预先知道。

有一些其它的技术可用来确定进程的CPU突发时间。我们稍后会详细讨论它们。

示例

在以下示例中，有五个作业命名为:P1，P2，P3，P4和P5。他们的到达时间和爆发时间在下表中给出。

PID	到达时间	突发时间	完成时间	周转时间	等待时间
1	1	7	8	7	0
2	3	3	13	10	7
3	6	2	10	4	2
4	7	10	31	24	14
5	9	8	21	12	4

因为，没有过程在时间0到达; 从时间0到1(第一个过程到达的时间)甘特图中会有一个空槽。

根据该算法，OS调度就绪队列中可用进程中具有最低突发时间的进程。

到目前为止，我们在就绪队列中只有一个进程，因此调度器会将它安排到处理器，而不管它的突发时间是多少。

这将被执行到8个单位的时间。直到那时又有三个进程到达就绪队列，因此调度器将选择具有最低突发时间的进程。

在表中给出的过程中，接下来将执行P3，因为它在所有可用进程中具有最低的突发时间。

所以这就是程序如何以最短作业优先(SJF)调度算法进行。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

预测SJF进程的CPU突发时间 - 操作系统教程™

SJF算法是最好的调度算法之一，因为它提供了最大的吞吐量和最少的等待时间，但是该算法的问题是，CPU的突发时间无法预先知道。

我们可以估算某个进程的CPU爆发时间。有多种技术可用于假定进程的CPU突发时间。假设需要准确以便最佳地利用算法。

有以下技术用于假定某个进程的CPU爆发时间。

1. 静态技术

进程大小

可以根据其大小预测进程的爆发时间。如果有两个进程T_OLD和T_New，并且旧进程的实际突发时间为20秒，进程的大小为20 KB。我们知道P_NEW的大小是21 KB。那么P_New具有类似突发时间20秒的概率是最大的。

If, P_OLD → 20 KB
P_New → 21 KB
BT(P_OLD) → 20 Secs
Then,
BT(P_New) → 20 secs

因此，在这项技术中，我们实际上根据新进程的相似大小的旧进程的突发时间来预测新进程的爆发时间。

进程类型

也可以根据其类型预测过程的爆发时间。进程可以是以下定义的各种类型。

OS进程
进程可以是调度程序，编译器，程序管理器和更多系统进程等操作系统进程。它们的爆发时间通常较低，例如:3到5个单位时间。
用户进程
用户发起的进程称为用户进程。可以有三种类型的过程如下。
- 互动进程
  交互式进程是与用户不时交互的进程或执行完全取决于用户输入的进程，例如各种就是这样的进程。爆发时间需要降低，因为它们不需要CPU很长时间，它们主要取决于用户与进程的交互性，因此它们主要是IO绑定进程。
- 前台进程
  前台进程是用户用来执行其需求的进程，例如MS Office，编辑器，实用程序软件等。这些类型的进程有更高的突发时间，因为它们是CPU和IO绑定进程的完美组合。
- 后台进程
  后台进程支持其他进程的执行。它们以隐藏模式工作。例如，密钥记录器是记录用户按下的密钥和用户在系统上的活动的过程。它们主要是CPU绑定的进程，需要更长的CPU时间。

动态技术

简单平均
在简单的平均中，给出了n个进程P(i)……. P(n)的列表。令T(i)表示过程P(i)的突发时间。假设τ(n)表示Pth过程的预测突发时间。然后根据简单平均，过程n + 1的预测突发时间将被计算为，

τ(n+1) = (1/n) ∑ T(i)

其中，0 <= i <= n并且ΣT(i)是到目前为止所有可用过程的实际突发时间的总和。

指数平均或时效

令Tn为第n个过程的实际突发时间.τ(n)为第n个过程的预测突发时间，则下一个过程(n + 1)的CPU突发时间将被计算为，

τ(n+1) = α. Tn + (1-α) . τ(n)

其中，α是平滑。它的值在0和1之间。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

最短剩余时间优先（SRTF）调度算法 - 操作系统教程™

该算法是SJF调度的抢先版本。在SRTF中，过程的执行可以在一段时间后停止。在每个进程到来时，短期调度程序在可用进程列表和正在运行的进程中以最少的剩余突发时间安排进程。

一旦所有进程都在就绪队列中可用，就不会执行抢占，并且该算法将作为SJF调度工作。当进程从执行中被移除并且下一个进程被调度时，进程的上下文被保存在进程控制块中。该PCB在下一次执行该过程时被访问。

示例

在这个例子中，有五个作业:P1，P2，P3，P4，P5和P6。它们的到达时间和爆发时间如下表所示。

进程ID	到达时间	突发时间	完成时间	周转时间	等待时间	响应时间
1	0	8	20	20	12	0
2	1	4	10	9	5	1
3	2	2	4	2	0	2
4	3	1	5	2	1	4
5	4	3	13	9	6	10
6	5	2	7	2	0	5

平均等待时间= 24/6

甘特图根据表中给出的到达和爆发时间进行准备。

因为在0时刻，唯一可用的进程是CPU的CPU突发时间为8的P1。这是列表中唯一可用的进程，因此它是按计划进行的。
下一个过程在时间单元1到达。由于使用的算法是抢占式的SRTF，所以当前的执行被停止，并且调度器以最小的突发时间检查过程。到目前为止，就绪队列中有两个进程可用。到目前为止，操作系统已经执行了一个单元的P1; P1的剩余突发时间是7个单位。过程P2的突发时间是4个单位。因此，根据算法在CPU上调度进程P2。
下一个处理P3在时间单元2到达。此时，处理P3的执行停止，并搜索具有最小剩余突发时间的处理。由于过程P3具有2个单位的突发时间，所以它将被给予优先于其他的优先权。
下一个进程P4以时间单元3到达。在这个到达时，调度程序将停止P4的执行并检查哪个进程在可用进程(P1，P2，P3和P4)中具有最少的突发时间。 P1和P2的剩余突发时间分别为7个单位和3个单位。
P3和P4的剩余突发时间各有1个单位。因为两者都是相同的，所以调度将根据他们的到达时间完成。 P3比P4早到，因此它会再次安排。
下一个进程P5以时间单元4到达。直到此时，进程P3已经完成执行，并且不在列表中。调度程序将比较所有可用进程的剩余突发时间。由于过程P4的突发时间是1，所以这是最少的，因此这将被安排。
下一个过程P6以时间单元5到达，直到此时，过程P4已经完成其执行。我们有4个可用的过程，即P1(7)，P2(3)，P5(3)和P6(2)。 P6的爆发时间是最少的，因此P6被安排。因为现在所有的过程都是可用的，所以现在算法与SJF一样工作。 P6将被执行直到完成，然后剩余时间最短的过程将被安排。

当所有进程到达，不抢占，算法将作为SJF。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

循环调度算法 - 操作系统教程™

轮循调度算法是最流行的调度算法之一，它可以在大多数操作系统中实际实现。这是先到先得的排程先发制人的版本。该算法着重于时间共享。在这个算法中，每个进程都以循环方式执行。在称为时间量的系统中定义了一定的时间片。就绪队列中的每个进程都分配给该时间段的CPU，如果在该时间内进程的执行完成，那么进程将终止，否则进程将返回就绪队列并等待下一轮完成执行。

优点

它可以在系统中实际实现，因为它不依赖于突发时间。
它不会遇到饥饿或车队效应的问题。
所有的作业都可以获得CPU分配。

缺点

时间越长，系统的响应时间就越长。
时间量越小，系统中的上下文切换开销就越高。
确定一个完美的时间段是系统中非常困难的任务。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

循环调度算法示例 - 操作系统教程™

在以下示例中，有六个进程分别命名为P1，P2，P3，P4，P5和P6。他们的到达时间和爆发时间如下表所示。系统的时间量是4个单位。

进程ID	到达时间	突发时间
1	0	5
2	1	6
3	2	3
4	3	1
5	4	5
6	6	4

根据算法，我们必须保持就绪队列和甘特图。两个数据结构的结构在每次调度后都会改变。

就绪队列:
最初，在时间0，过程P1到达，其将被安排为时间片4单位。因此，在就绪队列中，在CPU突发时间5个单元开始时将只有一个进程P1。

甘特图
P1将首先执行4个单位。

就绪队列

同时执行P1，另外四个进程P2，P3，P4和P5到达就绪队列。 P1还没有完成，它需要另外1个单位时间，因此它也将被添加回就绪队列。

P2	P3	P4	P5	P1
6	3	1	5	1

甘特图

在P1之后，P2将在甘特图中显示的4个单位时间内执行。

就绪队列

在执行P2期间，再有一个进程P6进入就绪队列。由于P2尚未完成，因此P2也将被添加回就绪队列，剩余的突发时间为2个单位。

P3	P4	P5	P1	P6	P2
3	1	5	1	4	2

甘特图
在P1和P2之后，由于其CPU突发时间仅为3秒，因此P3将执行3个单位时间。

就绪队列

由于P3已经完成，因此它将被终止并且不会被添加到就绪队列中。下一个进程将执行P4。

P4	P5	P1	P6	P2
1	5	1	4	2

甘特图

之后，P1，P2和P3，P4将被执行。它的爆发时间只有1个单位，与时间量相比更小，因此它会完成。

就绪队列

就绪队列中的下一个进程是P5，有5个单位的突发时间。由于P4已完成，因此它不会被添加回队列。

P5	P1	P6	P2
5	1	4	2

甘特图
P5将在整个时间片执行，因为它需要5个单位的突发时间，这比时间片更高。

就绪队列
P5尚未完成; 它将被添加回队列中，其余的突发时间为1个单位。

P1	P6	P2	P5
1	4	2	1

甘特图
进程P1将在下一个回合完成执行。由于它只需要1单位的突发时间，因此它将被完成。

就绪队列
P1已完成并且不会被添加回就绪队列。接下来的处理P6仅需要4个单位的突发时间，接下来将被执行。

P6	P2	P5
4	2	1

甘特图
P6将执行4个单位时间直至完成。

就绪队列
由于P6已完成，因此不会再次添加到队列中。就绪队列中只有两个进程。下一个进程P2只需要2个单位的时间。

P2	P5
2	1

甘特图

P2将再次执行，因为它只需要2个单位时间，因此这将会完成。

就绪队列

现在，队列中唯一可用的进程是P5，它需要1个单位的突发时间。由于时间片是4个单位，因此它会在下一次突发中完成。

甘特图
P5将被执行直至完成。

完成时间，周转时间和等待时间将按下表所示计算。

周转时间 = 完成时间 - 到达时间
等待时间 = 周转时间 - 爆发时间

进程ID	到达时间	爆发时间	完成时间	周转时间	等待时间
1	0	5	17	17	12
2	1	6	23	22	16
3	2	3	11	9	6
4	3	1	12	9	8
5	4	5	24	20	15
6	6	4	21	15	11

平均等待时间=(12 + 16 + 6 + 8 + 15 + 11)/ 6 = 76/6个单位

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

最高响应比下（HRRN）调度 - 操作系统教程™

下一个最高响应比率(HRNN)是最优调度算法之一。这是一种非抢先式算法，其中，调度是基于称为响应比率的额外参数完成的。计算每个可用作业的响应比率，响应比率最高的作业优先于其他作业。

响应比率由给定的公式计算。

响应比 =(W + S)/ S

这里，

W → 等待时间
S → 服务时间或突发时间

如果我们看一下公式，就会注意到突发时间较短的作业将被优先考虑，但它也包括一个称为等待时间的额外因素。

HRNN α W
HRNN α (1/S)

因此，

这种算法不仅有利于缩短作业时间，而且还涉及较长时间作业的等待时间。
它的模式是非抢占式的，因此在这个算法中上下文切换是最小的。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

最高响应比下（HRRN）调度示例 - 操作系统教程™

在下面的例子中，给出了5个进程。他们的到达时间和爆发时间在表中给出。

进程ID	到达时间	爆发时间
0	0	3
1	2	5
2	4	4
3	6	1
4	8	2

在时间0，过程P0以3个单位的CPU突发时间到达。由于它是迄今为止唯一的流程，因此将立即安排。

P0执行3个单元，同时，只有一个进程P1在时间3到达。由于操作系统没有选择，这将被立即安排。

P1执行5个单位。同时，所有进程都可用。我们必须计算所有剩余工作的响应比率。

RR (P2) = ((8-4) +4)/4 = 2
RR (P3) = (2+1)/1 = 3
RR (P4) = (0+2)/2 = 1

因为，P3的响应率更高，因此P3将首先安排。

P3预定1个单位。下一个可用的进程是P2和P4。我们来计算他们的响应率。

RR ( P2) = (5+4)/4 = 2.25
RR (P4) = (1+2)/2 = 1.5

P2的响应率更高，因此P2将被安排。

现在，唯一可用的过程是P4，突发时间为2个单位，因为没有其他过程可用，因此这将被安排。

进程ID	到达时间	爆发时间	完成时间	周转时间	等待时间
0	0	3	3	3	0
1	2	5	8	6	1
2	4	4	13	9	5
3	6	1	9	3	2
4	8	2	15	7	5

平均等待时间= 13/5

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

优先级调度 - 操作系统教程™

在优先级调度中，为每个进程分配一个优先级编号。在一些系统中，数字越小，优先级越高。而在其他情况下，数字越高，优先级越高。在可用进程中具有较高优先级的进程由CPU提供。存在两种类型的优先级调度算法。一种是抢占式优先级调度，而另一种是非抢先式优先级调度。

分配给每个过程的优先级编号可能会也可能不会变化。如果优先级号码在整个过程中没有改变，它被称为静态优先级，而如果它保持定期改变自己，它被称为动态优先级。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

非抢占式优先级调度 - 操作系统教程™

在非先占优先级调度中，进程根据分配给它们的优先级编号进行调度。一旦进程被安排好了，它就会运行直到完成。通常，优先级数越低，进程的优先级越高。人们可能会对优先级数字感到困惑，因此在GATE中，明确提到哪一个是最高优先级，哪一个是最低优先级。

示例

在例子中，有7个进程:P1，P2，P3，P4，P5，P6和P7。它们的优先级，到达时间和爆发时间在表中给出。

进程ID	优先级	到达时间	爆发时间
1	2	0	3
2	6	2	5
3	3	1	4
4	5	4	2
5	7	6	9
6	4	5	4
7	10	7	10

我们可以根据非抢先优先级调度来准备甘特图。

进程P1在时间0到达，突发时间为3个单位，优先级为2。由于没有其他进程到目前为止，因此操作系统会立即安排它。

同时执行P1，还有两个进程P2和P3到达。由于P3的优先级为3，因此CPU将通过P2执行P3。

同时执行P3，所有进程都可以在就绪队列中使用。优先级最低的进程将被优先考虑。由于P6将优先级编号分配为4，因此它将在P3之后执行。

在P6之后，P4在可用进程中具有最小优先级编号; 它会在整个爆发时间执行。

由于所有作业都在就绪队列中可用，因此所有作业都将根据其优先级执行。如果两个作业的优先级编号相似，则会执行最短到达时间的编号。

从GANTT图表中，可以确定每个进程的完成时间。周转时间，等待时间和响应时间将被确定。

周转时间 = 完成时间 - 到达时间
等待时间 = 周转时间 - 爆发时间

进程Id	优先级	到达时间	爆发时间	完成时间	周转时间	等待时间	响应时间
1	2	0	3	3	3	0	0
2	6	2	5	18	16	11	13
3	3	1	4	7	6	2	3
4	5	4	2	13	9	7	11
5	7	6	9	27	21	12	18
6	4	5	4	11	6	2	7
7	10	7	10	37	30	18	27

平均等待时间=(0 + 11 + 2 + 7 + 12 + 2 + 18)/ 7 = 52/7单位

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

抢先式优先级调度 - 操作系统教程™

在抢占式优先级调度中，在进程到达就绪队列时，其优先级与就绪队列中存在的其他进程的优先级以及CPU在该点执行的优先级进行比较。在所有可用的进程中具有最高优先级的那个将被赋予CPU。

抢先优先级调度和非抢占优先级调度之间的区别在于，在抢先优先级调度中，正在执行的作业可以在更高优先级作业到达时停止。

一旦所有作业在就绪队列中可用，算法将表现为非抢占式优先级调度，这意味着计划的作业将运行直至完成并且不会执行抢占。

示例

有7个过程P1，P2，P3，P4，P5，P6和P7给出。下表列出了他们各自的优先级，到达时间和爆发时间。

进程Id	优先级	到达时间	爆发时间
1	2(L)	0	1
2	6	1	7
3	3	2	3
4	5	3	6
5	4	4	5
6	10(H)	5	6
7	9	15	8

甘特图制备

在时间0，P1以1单位的爆发时间和优先级2到达。由于没有其他进程可用，因此这将被安排到下一个作业到达或完成(以较小者为准)。

在时间1，P2到达。 P1已经完成执行，此时没有其他进程可用，因此操作系统必须安排它，而不管分配给它的优先级如何。

下一个进程P3在时间单元2到达，P3的优先级高于P2。因此，P2的执行将被停止，并且P3将被安排在CPU上。

在执行P3期间，还有三个进程P4，P5和P6可用。因为，所有这三个优先级都低于执行过程，因此PS无法抢占进程。 P3将完成其执行，然后P5将按照可用进程中的优先级排列。

同时执行P5，所有进程都可以在就绪队列中使用。此时，算法将开始表现为非抢占式优先级调度。因此，现在，一旦所有进程在就绪队列中都可用，操作系统就会将进程的优先级最高并执行该进程直到完成。在这种情况下，P4将按计划执行，直至完成。

由于P4已完成，因此就绪队列中具有最高优先级的其他进程为P2。因此P2将在下一个时间安排。

P2被给予CPU直到完成。由于其剩余的爆发时间为6个单位，因此P7将在此之后安排。

唯一剩下的进程是P6，其优先级最低，操作系统除非执行它，否则别无选择。这将在最后执行。

每个过程的完成时间在GANTT图表的帮助下确定。周转时间和等待时间可以通过以下公式计算。

周转时间 = 完成时间 - 到达时间
等待时间 = 转身时间 - 爆发时间

进程Id	优先级	到达时间	爆发时间	完成时间	周转时间	等待时间
1	2	0	1	1	1	0
2	6	1	7	22	21	14
3	3	2	3	5	3	0
4	5	3	6	16	13	7
5	4	4	5	10	6	1
6	10	5	15	45	40	25
7	9	6	8	30	24	16

平均等待时间=(0 + 14 + 0 + 7 + 1 + 25 + 16)/ 7 = 63/7 = 9个单位

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

同步

进程同步简介 - 操作系统教程™

当两个或多个进程相互合作时，必须保留其执行顺序，否则可能会在执行过程中产生冲突，并产生不适当的输出。

协同进程是可以影响其他进程执行的协同进程，也可以受到其他进程执行的影响。这些进程需要同步，以保证其执行顺序。

保持合作进程的适当执行顺序涉及的过程称为进程同步。有各种同步机制用于同步进程。

竞争条件

当两个或多个线程尝试读取，写入并可能根据他们正在同时访问的内存做出决定时，通常会发生竞争状况。

临界部分

试图访问共享资源并可能导致竞争条件的程序区域称为临界区。为避免进程间的竞争状态，我们需要确保一次只能在关键部分执行一个进程。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

临界区问题 - 操作系统教程™

临界区是试图访问共享资源的程序的一部分。该资源可以是计算机中的任何资源，如内存位置，数据结构，CPU或任何IO设备。

临界区不能同时由多个进程执行; 操作系统在允许和禁止进程进入临界区时面临着困难。

临界区问题用于设计一组协议，可以确保进程间的竞争条件永远不会出现。

为了同步协作过程，我们的主要任务是解决临界区问题。我们需要提供一个解决方案，以满足以下条件。

同步机制的要求

主

1. 相互排斥
我们的解决方案必须提供相互排斥。通过相互排斥，如果一个进程在临界区内执行，那么另一个进程不能进入临界区。

2. 进程
进程意味着如果一个进程不需要执行到临界区，那么它不应该阻止其他进程进入临界区。

次要

1. 有界等待
我们应该能够预测每个流程进入临界区的等待时间。这个进程不能无休止地等待进入临界区。

2. 架构中立

我们的机制必须是架构中立的。这意味着如果解决方案在一个架构上运行良好，那么它也应该在其他架构上运行。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

锁定变量机制 - 操作系统教程™

这是最简单的同步机制。这是一个在用户模式下实现的软件机制。这是一个繁忙的等待解决方案，可用于两个以上的进程。

在这个机制中，使用了锁变量lockis。两个锁定值是可能的，可以是0或1。锁定值0表示临界区域是空的，而锁定值1表示它被占用。

想要进入临时部分的进程首先检查锁定变量的值。如果它是0，那么它将锁的值设置为1并进入临界区，否则等待。

该机制的伪代码如下所示。

Entry Section →
While (lock! = 0);
Lock = 1;
//Critical Section
Exit Section →
Lock =0;

如果我们看一下伪代码，发现代码中有三个部分。入口部分，临界区和退出部分。

最初锁定变量的值为0。需要进入临界区的进程进入入口区并检查while循环中提供的条件。

该进程将无限等待，直到锁定值为1(while循环暗示该值)。因为在第一次临界区是空的，因此该过程将通过将锁变量设置为1而进入临界区。

当进程从临界区退出时，在退出部分，它将锁的值重新指定为0。

每个同步机制是根据四个条件来判断的。

相互排斥
进程
有界等待
可移植性

在四个参数中，互斥和进度必须由任何解决方案提供。在上述条件的基础上分析这个机制。

相互排斥

在某些情况下，锁定变量机制不提供互斥。这可以通过操作系统视图I.E，查看伪代码来更好地描述。程序的汇编代码。让我们将代码转换为汇编语言。

Load Lock, R0
CMP R0, #0
JNZ Step 1
Store #1, Lock
Store #0, Lock

考虑一下有两个进程P1和P2。过程P1想要执行其临界区。 P1进入入口部分。由于锁的值为0，因此P1将其值从0更改为1并进入临界区。

同时，P1被CPU抢占，P2被安排。现在临界区没有其他进程，并且锁变量的值为0。 P2还想执行其临界区。它通过将lock变量设置为1进入临界区。

现在，CPU将P1的状态从等待改为运行。 P1尚未完成其临界区。 P1已经检查了锁定变量的值，并且在先前检查它时记得其值为0。因此，它也会进入临界区而不检查锁定变量的更新值。

现在，在临界区有两个进程。根据相互排斥的条件，临界区中的一个以上的过程不得同时出现。因此，锁定变量机制不能保证互斥。

锁变量机制的问题在于，同时，多个进程可以看到空标签，并且在临界区中可以输入多个进程。因此，锁变量不提供互斥，这就是为什么它不能被普遍使用。

因为这种方法在基本步骤上失败了; 因此，没有必要谈谈要实现的其他条件。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

测试集锁定机制 - 操作系统教程™

汇编代码中的修改

在锁变量机制中，有时Process读取锁变量的旧值并进入临界区。由于这个原因，多个流程可能会进入临界区。但是，下面第一部分中显示的代码可以用第二部分中显示的代码替换。这不会影响算法，但通过这样做，我们可以设法在一定程度上提供互斥，但不能完全实现。

在更新版本的代码中，Lock的值被加载到本地寄存器R0中，然后锁的值被设置为1。

但是，在步骤3中，先前的锁定值(现在存储到R0中)与0进行比较，如果该值为0，则该过程将简单地进入临界区域，否则将通过循环连续执行来等待。

将进程本身立即设置为1的好处是，现在进入临界区的进程携带的锁变量的更新值为1。

在它被抢占并重新计划的情况下，它也不会进入临界区，而不管当前锁定变量的值如何，因为它已经知道锁定变量的更新值是什么。

第一部分

1. Load Lock, R0
2. CMP R0, #0
3. JNZ step1
4. store #1, Lock

第二部分

1. Load Lock, R0
2. Store #1, Lock
3. CMP R0, #0
4. JNZ step 1

TSL指令

但是，上述部分提供的解决方案在一定程度上提供了相互排斥，但不能确保互斥将始终存在。临界区可能有多个流程。

在执行第2节中编写的汇编代码的第一条指令之后，如果进程被抢先，该怎么办？在这种情况下，它将携带旧的锁定变量值，并且无论知道锁定变量的当前值，它都将进入临界区域。这可能会使两个进程同时出现在临界区。

要摆脱这个问题，必须确保在加载先前的锁定变量值之前并且在将其设置为1之前不应该发生抢占。如果能够合并前两个说明。

为了解决这个问题，操作系统提供了一个称为测试集锁定(TSL)指令的特殊指令，该指令简单地将锁定变量的值加载到本地寄存器R0中，并将其同时设置为1。

首先执行TSL的过程将进入临界区，之后不会进入其他进程，直到第一个进程出来。即使在抢先执行第一个过程的情况下，任何进程都不能执行临界区。

解决方案的汇编代码如下所示。

TSL Lock, R0
CMP R0, #0
JNZ step 1

以四个条件为基础来考察TSL。

相互排斥
在TSL机制中保证相互排斥，因为在设置锁变量之前，进程永远不会被抢占。只有一个进程可以在特定时间将锁变量看作0，这就是为什么互斥可以保证执行。

进程
根据进程的定义，不想进入临界区的进程不应该阻止其他进程进入进程。在TSL机制中，进程只有在想要进入临界区时才会执行TSL指令。如果没有进程不想进入临界区，锁的值将始终为0，因此在TSL中始终保证进程。

有界等待
TSL不保证有限等待。有些过程可能没有这么长时间。我们无法预测一个进程，在一段时间之后，它肯定会有机会进入临界区。

架构中立
TSL不提供架构中立。这取决于硬件平台。 TSL指令由操作系统提供。有些平台可能不会提供。因此它不是架构中立的。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

优先级反转 - 操作系统教程™

在TSL机制中，可能存在优先级反转的问题。让我们说有两个合作进程:P1和P2。

P1的优先级为2，而P2的优先级为1，P1较早到达并由CPU调度。由于它是一个协作进程，并且希望在临界区执行，因此它将通过将锁变量设置为1来进入临界区。

现在，P2到达就绪队列。 P2的优先级高于P1，因此根据优先级调度，P2被调度并且P1被抢占。 P2也是一个合作进程，并希望在临界区内执行。

虽然，P1被抢占，但它的锁变量的值将显示为1，因为P1没有完成，它还没有完成其临界区。

P1需要完成临界区，但根据调度算法，CPU使用P2。 P2要在临界区执行，但根据同步机制，临界区是用P1。

这是一种锁，其中每个进程既不执行也不完成。这种类型的锁被称为自旋锁。

这与死锁不同，因为它们不处于阻塞状态。一个处于就绪状态，另一个处于运行状态，但两者都没有执行。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

开启可变或严格的交替方式 - 操作系统教程™

Turn Variable或Strict Alternation Approach是在用户模式下实现的软件机制。这是一个繁忙的等待解决方案，只能为两个进程实施。在这种方法中，使用实际上是锁的转弯变量。

这种方法只能用于两个进程。一般来说，让两个进程是:Pi和Pj。它们共享一个称为转变量的变量。程序的伪代码可以给出如下。

对于进程Pi

Non - CS
while (turn ! = i);
Critical Section
turn = j;
Non - CS

对于进程Pj

Non - CS
while (turn ! = j);
Critical Section
turn = i ;
Non - CS

锁变量方法的实际问题是只有当锁变量为1时进程才进入临界区。不止一个进程可以同时看到锁变量为1，因此互斥不能得到保证。

这个问题在转向变量方法中得到解决。现在，只有当转向变量的值等于进程的PID时，进程才能进入临界区。

只有两个可能的值是可变的，i或j。如果它的值不是i，那么肯定会是j，反之亦然。

在入口部分，一般来说，进程Pi不会进入临界区，直到它的值为j，或者进程Pj将不会进入临界区，直到其值为i。

最初，两个进程Pi和Pj可用并且想要执行到临界区。

转向变量等于i，因此Pi将有机会进入临界区。在Pi完成临界区之前，Pi的值仍然为I。

Pi完成其临界区并指定j转变。 Pj将有机会进入临界区。转变值仍然是j直到Pj完成其临界区。

严格交替法分析

让我们根据四个要求分析严格交替方法。

相互排斥
严格的交替方法在每种情况下都提供相互排斥。此过程仅适用于两个进程。这两个进程的伪代码是不同的。只有在看到转弯变量等于其过程ID时才会进入该过程，否则不会进入。因此，无论进程如何，进程都不能进入临界区。

进程

这一机制无法保证进展。如果Pi不想进入临界区，那么Pj被无限期阻挡。 Pj必须等待很长时间，因为转向变量将保持为0，直到Pi将其分配给j。

可移植性
该解决方案提供了便携性。它是在用户模式下实现的纯粹的软件机制，不需要操作系统的任何特殊指令。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

感兴趣变量机制 - 操作系统教程™

必须确保进度必须由我们的同步机制提供。在转向变量机制中，由于不想进入临界区的进程并没有考虑其他感兴趣的进程，所以没有提供进展。

另一个进程也将不得不等待，而不管临界区内部没有进程。如果操作系统可以利用额外的变量以及转向变量，那么这个问题就可以解决，而且我们的问题可以在大部分范围内提供进展。

感兴趣的变量机制利用额外的布尔变量来确保提供进度。

对于进程Pi

Non CS
Int[i] = T ;
while ( Int[j] == T ) ;
Critical Section
Int[i] = F ;

对于进程Pj

Non CS
Int [1] = T ;
while ( Int[i] == T ) ;
Critical Section
Int[j]=F ;

在这个机制中，使用了一个额外的变量。这是一个布尔变量，用于存储在临界区中的兴趣进程。

想要进入临界区的进程首先在入口区检查其他过程是否有兴趣进入内部。该进程将等待直到另一个进程感兴趣的时间。

在退出部分，该进程使其感兴趣变量的值为false，以便其他进程可以进入临界区。

该表格显示了在场景中获得机会的进程和进程的利益变量的可能值。

Interest [Pi]	Interest [Pj]	获得机会的过程
True	True	首先表现出兴趣的进程。
True	False	Pi
False	True	Pj
False	False	X

让我们根据需求分析机制。

相互排斥
在感兴趣的变量机制中，如果一个进程有兴趣进入CPU，那么另一个进程将等待，直到它变得不感兴趣。因此，临界区不能同时存在多个进程，因此该机制保证互斥。

进展

在这种机制中，如果一个进程不想进入临界区，那么它不会阻止另一进程进入临界区。因此，这种方法肯定会提供进展。

有界等待

为了分析有界等待，让我们考虑两个过程Pi和Pj，合作过程是否希望在关键部分执行。下面以相对方式显示过程执行的指令。

最初，这两个过程的利益变量是错误的。进程Pi显示了进入临界区的兴趣。

它将其Interest变量设置为true，并检查Pj是否也有兴趣。由于其他进程的兴趣变量是错误的，因此Pi将进入临界区。

同时，过程Pi被抢占并且Pj被调度。 Pj是一个合作过程，因此它也想进入关键部分。它通过将兴趣变量设置为true来显示其兴趣。

它还检查其他流程是否也有兴趣。我们应该注意到Pi被抢占了，但其感兴趣的变量是真实的，这意味着它需要在临界区进一步执行。因此Pj不会有机会陷入while循环。

同时，CPU将Pi的状态从阻塞状态变为运行状态。 Pi尚未完成临界区，因此它完成临界区并通过将interest变量设置为False而退出。

现在，当Pi再次想要进入临界区并将其感兴趣的变量设置为true并且检查Pj的感兴趣变量是否为真时，情况是可能的。在这里，Pj的兴趣变量是True，因此Pi将陷入while循环并等待Pj变得不感兴趣。

因为，Pj仍然停留在while循环中，等待Pi感兴趣的变量变为false。因此，这两个进程都在等待对方，他们都没有进入临界区。

这是死锁的情况，在死锁的情况下永远不能提供有界的等待。

因此，我们可以说感兴趣的变量机制并不能保证死锁。

架构中立

该机制是在用户模式下执行的完整软件机制，因此它保证了可移植性或架构中立性。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

帕特森（Peterson）解决方案 - 操作系统教程™

这是在用户模式下实现的软件机制。这是一个繁忙的等待解决方案，只能实施两个流程。它使用两个变量:回转变量和感兴趣变量。

解决方案的代码如下-

# define N 2
# define TRUE 1
# define FALSE 0
int interested[N] = FALSE;
int turn;
voidEntry_Section (int process)
{
int other;
other = 1-process;
interested[process] = TRUE;
turn = process;
while (interested [other] =True && TURN=process);
}
voidExit_Section (int process)
{
interested [process] = FALSE;
}

到目前为止，每个解决方案都受到一个或另一个问题的影响。但是，Peterson解决方案为您提供了所有必要的要求，例如互斥，进度，有限等待和可移植性。

Peterson解法分析

voidEntry_Section (int process)
{
1. int other;
2. other = 1-process;
3. interested[process] = TRUE;
4. turn = process;
5. while (interested [other] =True && TURN=process);
}

Critical Section

voidExit_Section (int process)
{
6. interested [process] = FALSE;
}

这是一个双进程解决方案。假设有两个合作进程:P1和P2。入口部分和退出部分如下所示。最初，感兴趣的变量和转向变量的值是0。

最初进程P1到达并想要进入临界区。它将其感兴趣的变量设置为True(指令行3)，并将其设置为1(行号4)。由于P1中给出的条件完全满足P1，所以它将进入临界区。

P1 → 1 2 3 4 5 CS

同时，进程P1被抢占，进程P2被计划。 P2也想进入临界区并执行入口部分的指令1,2,3和4。在指令5中，由于它不满足条件(其他感兴趣的变量的值仍然为真)，它被卡住了。因此它进入了繁忙的等待状态。

P2 → 1 2 3 4 5

P1再次按计划执行，并通过执行指令编号完成临界区。 6(将感兴趣的变量设置为false)。现在，如果P2检查，那么它将满足条件，因为其他进程的感兴趣变量变为false。 P2也将进入临界区。

P1 → 6
P2 → 5 CS

任何过程都可以在临界区输入多次。因此，该过程按循环顺序进行。

相互排斥

该方法确实提供互斥。在入口部分，while条件涉及两个变量的标准，因此一个进程无法进入临界区，直到另一个进程感兴趣，并且进程是最后一个更新转向变量。

进展
一个不感兴趣的进程永远不会阻止另一个感兴趣的进程进入临界区。如果另一个进程也有兴趣，那么这个进程将会等待。

有限的等待

感兴趣的变量机制失败了，因为它没有提供有限的等待。但是，在Peterson解决方案中，死锁永远不会发生，因为首先设置转向变量的进程肯定会进入临界区。因此，如果在执行入口部分的第4行之后进程被抢占，那么它在下一次机会中肯定会进入临界区。

可移植性

这是完整的软件解决方案，因此它在每个硬件上都是可移植的。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

同步机制无需等待 - 操作系统教程™

迄今为止，我们所看到的所有解决方案都是为了在忙碌的等待中提供相互排斥。然而，忙等待并不是资源的最佳分配，因为它始终在持续检查while循环条件时保持CPU繁忙，尽管进程正在等待临界区变为可用。

所有具有繁忙等待的同步机制也受到优先级反转问题的困扰，即每当存在具有较高优先级的进程必须在关键部分之外等待的进程时总会存在自旋锁的可能性，因为机制意图执行较低优先级在关键部分进行处理。

然而，这些问题需要一个适当的解决方案，而无需等待和优先倒置。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

睡眠和唤醒 - 操作系统教程™

下面我们来看看睡眠和醒来的基本模型。假设有两个系统调用作为睡眠和唤醒。呼叫睡眠的过程将被阻止，而调用的过程将被唤醒。

有一个叫做生产者消费者问题的流行例子，它是模拟睡眠和唤醒机制的最流行的问题。

睡眠和觉醒的概念非常简单。如果关键部分不是空的，那么该过程将进入休眠状态。它将被临界区内正在执行的其他进程唤醒，以便进程可以进入临界区。

在生产者消费者问题中，让我们说有两个过程，一个过程写某事，而另一个过程读取。正在写东西的过程称为生产者，而正在阅读的过程称为消费者。

为了读取和写入，它们都使用缓冲区。下面显示了为生产者消费者问题提供解决方案的模拟睡眠和唤醒机制的代码。

#define N 100 //maximum slots in buffer
#define count=0 //items in the buffer
void producer (void)
{
int item;
while(True)
{
item = produce_item(); //producer produces an item
if(count == N) //if the buffer is full then the producer will sleep
Sleep();
insert_item (item); //the item is inserted into buffer
countcount=count+1;
if(count==1) //The producer will wake up the
//consumer if there is at least 1 item in the buffer
wake-up(consumer);
}
}

void consumer (void)
{
int item;
while(True)
{
{
if(count == 0) //The consumer will sleep if the buffer is empty.
sleep();
item = remove_item();
countcount = count - 1;
if(count == N-1) //if there is at least one slot available in the buffer
//then the consumer will wake up producer
wake-up(producer);
consume_item(item); //the item is read by consumer.
}
}
}

生产者生产该项目并将其插入缓冲区。每次插入时全局变量计数的值都会增加。如果缓冲区被完全填满并且没有插槽可用，那么生产者将会休眠，否则它将继续插入。

在消费者方面，每次消费时，计数值都降低了1。如果缓冲区在任何时间点都是空的，那么消费者就会进入休眠状态，它会持续消耗这些物品并将计数值减1。

如果缓冲区中至少有1个物品可用，消费者将被生产者唤醒。如果缓冲区中至少有一个可用槽位，生产者将被消费者唤醒，以便生产者可以写入。

那么，这个问题就出现在消费者即将休眠之前被抢占的情况下。现在消费者既不休眠也不消费。由于生产者没有意识到消费者实际上并不在休眠的事实，因此它不断地唤醒消费者，而消费者因为没有休眠就会响应。

这导致了系统调用的浪费。当消费者重新安排时间时，它会因为即将被抢占而休眠。

生产者不停地写入缓冲区，并在一段时间后得到填充。生产者也会在那个时候休眠，记住当缓冲区中有一个插槽时，消费者会唤醒他。

消费者也在休眠，并且不知道生产者会把他叫醒。

这是一种僵局，无论生产者还是消费者都活跃起来，彼此等待唤醒他们。这是一个需要解决的严重问题。

使用标志位来消除问题

标志位可以用来消除这个问题。生产者可以在第一次唤醒时设置该位。当消费者安排时，它会检查这个标志位。

消费者现在会知道生产者试图唤醒他，因此它不会休眠并进入准备好的状态，以消费生产者产生的任何东西。

这种解决方案仅适用于一对生产者和消费者，如果有n个生产者和n个消费者，该怎么办？在那种情况下，需要保持一个整数，该整数可以记录多少次唤醒呼叫以及有多少消费者不需要睡眠。这个整数变量被称为信号量。稍后我们将详细讨论关于信号量的更多信息。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

信号量介绍 - 操作系统教程™

为了摆脱浪费唤醒信号的问题，Dijkstra提出了一种包含存储所有唤醒调用的方法。迪克斯特拉(Dijkstra)表示，生产者可以将唤醒调用存储在一个变量中，而不是将唤醒调用直接发送给消费者。任何消费者只要需要就可以读取。

信号量是存储从生产者转移到消费者的整个唤醒调用变量。它是在内核模式下自动进行读取，修改和更新的变量。

信号量不能在用户模式下实现，因为在两个或更多进程试图同时访问变量时总会出现竞争条件。它始终需要操作系统的支持才能实施。

根据情况的需求，信号量可以分为两类。

计算信号量
二进制信号量或互斥量

在接下的教程文章中，我们将详细讨论它们。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

计算信号量的问题 - 操作系统教程™

有一些情况需要同时在临界区执行多个进程。但是，当我们需要同时在临界区中有多个进程时，可以使用计数信号量。

信号量实现的编程代码如下所示，其中包括信号量的结构以及在临界区中可以执行的入口和退出的逻辑。

struct Semaphore
{
int value; // processes that can enter in the critical section simultaneously.
queue type L; // L contains set of processes which get blocked
}
Down (Semaphore S)
{
SS.value = S.value - 1; //semaphore's value will get decreased when a new
//process enter in the critical section
if (S.value< 0)
{
put_process(PCB) in L; //if the value is negative then
//the process will get into the blocked state.
Sleep();
}
else
return;
}
up (Semaphore s)
{
SS.value = S.value+1; //semaphore value will get increased when
//it makes an exit from the critical section.
if(S.value<=0)
{
select a process from L; //if the value of semaphore is positive
//then wake one of the processes in the blocked queue.
wake-up();
}
}
}

在这种机制中，临界区的入口和退出是根据计数信号量的值执行的。在任何时间点计算信号量的值表示可以同时在临界区输入的最大进程数。

想要进入临界区的进程首先将信号量值减1，然后检查它是否为负值。如果它变为负数，则该过程被推入阻塞过程的列表(即q)，否则它进入临界区。

当进程从临界区退出时，它会将计数信号量增加1，然后检查它是否为负值或零。如果它是负数，那么这意味着至少有一个进程在阻塞状态下等待，因此，为了确保有界等待，阻塞进程列表中的第一个进程将被唤醒并进入临界区。

被阻止列表中的进程将按其睡眠顺序进行唤醒。如果计数信号量的值为负数，则表示处于阻塞状态的进程数量，如果为正数，则表示临界区域中可用的插槽数量。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

计算信号量的问题 - 操作系统教程™

在GATE计算信号量时会问到这些问题。一般来说，问题非常简单，只包含减法和加法。

Wait → Decre → Down → P
Signal → Inc → Up → V

以下类型的问题可以在GATE中询问。

计数信号量初始化为12。然后在这个信号量上计算10P(等待)和4V(信号)操作。结果是什么？

S = 12 (initial)
10 p (wait) :
SS = S -10 = 12 - 10 = 2
then 4 V :
SS = S + 4 =2 + 4 = 6

因此，计数信号量的最终值是6。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

二进制信号量或互斥量 - 操作系统教程™

在计算信号量时，没有提供相互排斥，因为有一组同时需要在临界区执行的进程。

然而，二进制信号严格提供互斥。在这里，临界区域不能有超过1个槽位，而临界区域最多只能有1个槽位。信号量只能有两个值，0或1。

下面，我们来看看二进制信号量的编程实现。

StructBsemaphore
{
enum Value(0,1); //value is enumerated data type which can only have two values 0 or 1.
Queue type L;
}
/* L contains all PCBs corresponding to process
Blocked while processing down operation unsuccessfully.
*/
Down (Bsemaphore S)
{
if (s.value == 1) // if a slot is available in the
//critical section then let the process enter in the queue.
{
S.value = 0; // initialize the value to 0 so that no other process can read it as 1.
}
else
{
put the process (PCB) in S.L; //if no slot is available
//then let the process wait in the blocked queue.
sleep();
}
}
Up (Bsemaphore S)
{
if (S.L is empty) //an empty blocked processes list implies that no process
//has ever tried to get enter in the critical section.
{
S.Value =1;
}
else
{
Select a process from S.L;
Wakeup(); // if it is not empty then wake the first process of the blocked queue.
}
}

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

死锁

死锁简介 - 操作系统教程™

每个进程都需要一些资源来完成它的执行。但是，该资源是按顺序授予的。

该进程请求一些资源。
如果可用，操作系统会授予资源，否则请等待进程。
该过程使用它并在完成时释放。

死锁是每个计算机进程等待分配给另一个进程的资源的情况。在这种情况下，由于它所需的资源不被执行，因此其他进程也在等待其他资源被释放。

假设有三个进程P1，P2和P3。有三种不同的资源R1，R2和R3。 R1分配给P1，R2分配给P2，R3分配给P3。

过了一段时间后，P1要求P2正在使用R1。 P1停止执行，因为它不能在没有R2的情况下完成。 P2也需要P3正在使用的R3。 P2也停止执行，因为没有R3就不能继续执行。 P3也要求R1使用P1，因此P3也停止执行。

在这种情况下，三个流程之间正在形成一个循环。没有一个进程正在进行，它们都在等待。由于所有进程都被阻止，计算机变得无响应。

饥饿和死锁的区别

编号	死锁	饥饿
1	死锁是一种没有进程被阻塞而没有进程继续的情况	饥饿是低优先级进程被阻止并且高优先级进程继续进行的情况。
2	死锁是一个无限的等待。	饥饿是漫长的等待，但不是无限的。
3	每个死锁始终是一个饥饿。	每一个饥饿不一定是死锁。
4	请求的资源被其他进程阻塞。	请求的资源不断被更高优先级的进程使用。
5	当相互排斥，保持和等待，同时不发生抢占和循环等待时，发生死锁。	它由于不受控制的优先权和资源管理而发生。

死锁的必要条件

相互排斥

资源只能以互斥方式共享。这意味着，如果两个进程不能同时使用相同的资源。

保持并等待

进程等待一些资源，同时持有另一个资源。

没有抢先
原定的过程将一直执行到完成。调度程序不能同时调度其他进程。

循环等待
所有进程都必须以循环方式等待资源，以便最后一个进程正在等待第一个进程持有的资源。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

处理死锁的策略 - 操作系统教程™

1.死锁无知

死锁无知是所有机制中使用最广泛的方法。许多操作系统主要为最终用户使用。在这种方法中，操作系统假定永远不会发生死锁。它只是无视死锁。这种方法最适合用户使用系统仅用于浏览和所有其他常规内容的单个最终用户系统。

正确性和性能之间总是有一个折衷。 Windows和Linux等操作系统主要关注性能。但是，如果死锁发生的次数是100次，那么系统的性能就会一直下降，如果它始终使用死锁处理机制，那么完全没有必要始终使用死锁处理机制。

在这些类型的系统中，用户不得不在死锁情况下重新启动计算机。 Windows和Linux主要使用这种方法。

2.死锁预防

只有当相互排斥，持有和等待，没有抢先和循环等待同时成立时，才会发生死锁。如果有可能在任何时候违反四个条件之一，那么在系统中永远不会发生死锁。

这种方法背后的想法非常简单，我们必须在四种情况之一中失败，但在系统中的物理实现方面可能会有一个大的争论。

我们稍后会详细讨论它。

3.避免死锁

在避免死锁时，操作系统会在操作系统执行的每一步中检查系统是处于安全状态还是处于不安全状态。该过程一直持续到系统处于安全状态。一旦系统进入不安全状态，操作系统必须回溯一步。

简而言之，操作系统审查每个分配，以便分配不会导致系统中的死锁。

稍后我们将详细讨论避免死锁。

4.死锁检测和恢复

这种方法让进程陷入死锁，然后定期检查系统中是否发生死锁。如果它发生，那么它会将一些恢复方法应用到系统中以消除死锁。

我们稍后将更详细地讨论死锁检测和恢复，因为这是一个讨论问题。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

死锁预防 - 操作系统教程™

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

避免死锁 - 操作系统教程™

在避免死锁的情况下，如果系统的结果状态不会导致系统中的死锁，那么将会授予对任何资源的请求。系统的状态将持续检查安全和不安全的状态。

为了避免死锁，进程必须告诉OS，进程可以请求完成其执行的最大资源数量。

最简单和最有用的方法指出，流程应声明它可能需要的每种类型的最大资源数量。死锁避免算法检查资源分配，以便永远不会有循环等待条件。

安全和不安全的状态

系统的资源分配状态可以由可用资源和已分配资源的实例以及进程所需资源的最大实例来定义。

下面显示了随机时间记录的系统状态。

已分配资源

仍然需要的资源

E = (7 6 8 4)
P = (6 2 8 3)
A = (1 4 0 1)

上表和向量E，P和A描述了系统的资源分配状态。系统中有4个进程和4个类型的资源。表1 显示了分配给每个进程的每个资源的实例。

表2显示了每个流程仍然需要的资源实例。向量E表示系统中每个资源的总实例。

向量P表示已分配给进程的资源实例。向量A表示未使用的资源的数量。

如果系统可以分配所有进程请求的所有资源而不进入死锁，则系统的状态称为安全。

如果系统不能满足所有进程的请求，那么系统的状态称为不安全。

死锁避免方法的关键在于当对资源进行请求时，只有在结果状态也是安全状态的情况下才能批准请求。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

避免死锁 - 操作系统教程™

资源分配图是系统状态的图形表示。顾名思义，资源分配图是关于持有一些资源或等待某些资源的所有进程的完整信息。

它还包含有关所有资源的所有实例的信息，无论这些资源是否可用或正在被进程使用。

在资源分配图中，进程由圆形表示，而资源由矩形表示。我们来详细看看顶点和边的类型。

顶点主要有两种类型，资源和过程。它们中的每一个将以不同的形状表示。 Circle代表进程，而矩形代表资源。

一个资源可以有多个实例。每个实例将由矩形内的一个点表示。

RAG中的边也有两种类型，一种代表分配，另一种代表资源进程的等待。上面的图片显示了每一个边。

如果箭头的尾部附加到资源的实例并且头部连接到进程，则将资源显示为分配给进程。

如果在头指向资源时将箭头的尾部连接到进程，则会显示进程等待资源。

示例

我们考虑有3个进程:P1，P2和P3以及两种资源R1和R2。每个资源都有1个实例。

根据图表，R1正在被P1使用，P2正在保持R2并等待R1，P3正在等待R1以及R2。

由于图中没有形成循环，因此该图是无死锁的。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

使用RAG进行死锁检测 - 操作系统教程™

如果在资源分配图中形成一个循环，其中所有资源都有单个实例，则系统将死锁。

在具有多实例资源类型的资源分配图的情况下，周期是死锁的必要条件，但不是充分条件。

以下示例包含三个进程P1，P2，P3和三个资源R2，R2，R3。所有资源都有单个实例。

如果我们分析图表，那么我们可以发现图表中存在一个循环，因为系统满足所有四种死锁条件。

分配矩阵

分配矩阵可以通过使用系统的资源分配图来形成。在分配矩阵中，将为每个分配的资源分配一个条目。例如，在下面的矩阵中，因为R3被分配给P1，所以在P1之前和R3之下进行输入。

请求矩阵

在请求矩阵中，将为每个请求的资源输入一个条目。如以下示例所示，P1需要R1，因此在P1之前和R1之下进行输入。

Avial =(0,0,0)

我们既没有系统中的任何资源，也没有将要发布的进程。每个进程至少需要一个资源才能完成，因此他们将持续保持每一个资源。

我们无法满足使用可用资源的至少一个进程的需求，因此当在图中检测到一个循环时，系统就会被锁定，如前所述。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

死锁检测和恢复 - 操作系统教程™

在这种方法中，OS不应用任何机制来避免或防止死锁。因此，系统认为死锁肯定会发生。为了摆脱死锁，OS定期检查系统是否存在死锁。如果发现死锁，操作系统将使用一些恢复技术来恢复系统。

操作系统的主要任务是检测死锁。操作系统可以借助资源分配图来检测死锁。

在单个实例化的资源类型中，如果系统中正在形成一个循环，那么肯定会出现死锁。另一方面，在多实例资源类型图中，检测周期不够。我们必须通过将资源分配图转换为分配矩阵和请求矩阵来在系统上应用安全算法。

为了从死锁中恢复系统，任一操作系统都会考虑资源或进程。

对于资源

抢占资源

我们可以从资源所有者(进程)中获取其中一个资源，并将其交给另一个进程，并期望它能够完成执行，并且会尽快释放该资源。那么，选择一个将被抢走的资源将会有点困难。

回滚到安全状态

系统通过各种状态进入死锁状态。操作系统将系统回滚到以前的安全状态。为此，操作系统需要在每个状态下执行检查指针。

现在，我们陷入死锁，将回滚所有分配以进入之前的安全状态。

对于进程

杀死一个进程

杀死一个进程可以解决问题，但更重要的是要决定要杀死哪个进程。一般来说，操作系统杀死一个迄今为止工作量最少的进程。

杀死所有进程

这不是一个可以接受的方法，但如果问题变得非常严重，可以实施。杀死所有进程将导致系统效率低下，因为所有进程将从头开始重新执行。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

内存管理

内存管理简介 - 操作系统教程™

什么是内存？

计算机内存是以二进制格式表示的一些数据的集合。在各种功能的基础上，内存可以分为不同的类别。稍后我们将详细讨论它们。

能够暂时或永久存储任何信息或数据的计算机设备称为存储设备。

数据如何存储在计算机系统中？

要理解内存管理，我们必须清楚如何将数据存储在计算机系统中。

机器只能识别0或1的二进制语言。计算机会先将每个数据转换为二进制语言，然后将其存储到内存中。

这意味着如果我们有一个程序行写成int α= 10，那么计算机会将它转换为二进制语言，然后将其存储到内存块中。

下面显示了int i = 10的表示形式。

数字10的二进制表示是1010。因此，如果是32位系统，因此int的大小是2个字节，即16位。 1个存储块存储1位。如果使用有符号整数，那么存储器阵列中最重要的位总是有符号的位。

有符号位值0表示正整数，而1表示负整数。这里，可以使用存储器阵列存储的值的范围是-32768到+32767。

好吧，可以使用unsigned int来扩大这个范围。在这种情况下，现在存储符号的位也将存储位值，因此范围将为0到65,535。

需要多种编程

但是，CPU可以直接访问系统的主内存，寄存器和缓存。程序总是在主内存中执行。主存的大小影响到大多数现存的多重编程的程度。如果主存储器的容量大于CPU，可以同时在主存储器中加载更多的进程，因此会提高多重编程的程度以及CPU利用率。

让我们考虑一下，

进程大小= 4 MB
主内存大小= 4 MB
该进程只能随时驻留在主内存中。
如果进程执行IO的时间是P，

然后，

CPU利用率=(1-P)
比方说，
P = 70%
CPU利用率= 30%
现在，增加内存大小，假设它是8 MB。
进程大小= 4 MB
两个进程可以同时驻留在主内存中。
假设一个进程的IO是P的时间，

然后

CPU利用率=(1-P ^ 2)
假设P = 70%
CPU利用率=(1-0.49)= 0.51 = 51%

因此，如果内存大小增加，可以认为CPU利用率会增加。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

固定分区 - 操作系统教程™

最早和最简单的技术之一是用于将多个进程加载到主内存中的是固定分区或连续内存分配。

在这种技术中，主存储器被分成相等或不同大小的分区。操作系统始终驻留在第一个分区中，而其他分区可用于存储用户进程。内存以连续的方式分配给进程。

在固定分区中，

分区不能重叠。
进程必须在分区中连续存在才能执行。

有使用这种技术的各种缺点。

1. 内部碎片

如果进程的大小较小，那么分区的总大小会导致分区的某些大小被浪费并且保持不用。这是内存的浪费，称为内部碎片。

如下图所示，4 MB分区仅用于加载3 MB进程，其余1 MB则被浪费。

2. 外部碎片

即使有可用空间但不是连续形式，各个分区的总未使用空间也不能用于加载进程。

如下图所示，每个分区的剩余1 MB空间不能用作存储4 MB进程的单位。尽管有足够的空间可用于加载进程，但进程将不会加载。

3. 限制进程的大小

如果进程大小大于最大的分区的大小，则该进程无法加载到内存中。因此，可以对进程大小施加限制，即不能大于最大分区的大小。

4. 多程序的程度较低

按照多编程的程度，这里只是指可以同时加载到内存中的最大进程数。在固定分区中，多程序的程度是固定的，因为分区的大小不能根据进程的大小而变化。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

动态分区 - 操作系统教程™

动态分区试图克服由固定分区造成的问题。在这种技术中，分区大小最初并未声明。它在进程加载时声明。

第一个分区是为操作系统保留的。剩余空间分成几部分。每个分区的大小将等于进程的大小。分区大小根据进程的需要而变化，以避免内部碎片。

动态分区比固定分区的优势

1. 没有内部碎片
考虑到动态分区中的分区是根据进程的需要创建的，很明显，不会有任何内部碎片，因为分区中不会有任何未使用的剩余空间。

2. 对过程的大小没有限制
在固定分区中，由于缺少足够的连续内存，因此大于最大分区大小的进程无法执行。这里，在动态分区中，由于分区大小是根据进程大小决定的，因此进程大小不能受到限制。

3. 多程序的程度是动态的
由于没有内部碎片，分区中不会有任何未使用的空间，因此可以同时将更多的进程加载到内存中。

动态分区的缺点

外部碎片
没有内部碎片并不意味着不会有外部碎片。

让我们考虑三个进程P1(1 MB)和P2(3 MB)和P3(1 MB)正在加载到主内存的各个分区中。

一段时间后，P1和P3完成并释放指定的空间。现在，在主内存中有两个未使用的分区(1 MB和1 MB)，但它们不能用于在内存中加载2 MB进程，因为它们不是连续定位的。

该规则表示，该进程必须连续存在于主内存中才能执行。需要更改此规则以避免外部碎片。

复杂的内存分配

在固定分区中，分区列表只会生成一次，并且永远不会改变，但在动态分区中，分配和释放非常复杂，因为每次分配给新进程时分区大小都会发生变化。操作系统必须跟踪所有的分区。

由于在动态内存分配中分配和取消分配的操作非常频繁，而且分区大小每次都会改变，所以操作系统很难管理所有内容。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

压缩（碎片整理） - 操作系统教程™

我们知道动态分区受到外部碎片的影响。但是，这可能会导致一些严重的问题。

为了避免压缩，我们需要更改规则，该规则指出进程无法存储在内存中的不同位置。

也可以使用压缩来减少外部碎片的可能性。在压缩过程中，所有的空闲分区都是连续的，所有加载的分区都集中在一起。

通过应用这种技术，可以将更大的进程存储在内存中。合并可用分区，现在可以根据新进程的需要分配这些分区。这种技术也称为碎片整理。

如上图所示，由于缺少连续的空间，无法将内存装载到内存中的进程P5现在可以加载到内存中，因为空闲分区是连续的。

压实问题

由于所有的自由空间将从几个地方转移到一个地方，因此在压实的情况下系统的效率会降低。

这个过程投入了大量的时间，并且CPU一直保持空闲状态。尽管压实避免了外部碎片，但却使得系统效率低下。

让我们考虑一下，操作系统需要6个NS将1个字节从一个地方复制到另一个地方。

1 B转移需要6 NS
256 MB传输需要256 X 2 ^ 20 X 6 X 10 ^ -9秒

因此，在一定程度上证明，较大容量的存储器传输需要几秒钟的大量时间。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

用于动态分区的位图 - 操作系统教程™

动态分区的主要关注点是跟踪所有空闲和分配的分区。但是，操作系统为此任务使用以下数据结构。

位图
链表

位图是存储细节最少见的数据结构。在这个方案中，主存储器被分成分配单元的集合。根据该过程的需要，可以将一个或多个分配单元分配给过程。但是，分配单元的大小是由操作系统定义的，并且从不更改。虽然分区大小可能会有所不同，但分配大小是固定的。

操作系统的主要任务是跟踪分区是空闲的还是空闲的。为此，操作系统还管理另一个称为位图的数据结构。

分配单元中的进程或空洞由位图的标志位表示。在下面显示的图像中，为分配单元的每一位定义了一个标志位。但是，这并不是一般情况，它取决于操作系统，对于多少位分配单元，它想要存储标志位。

如果在分配单元中的相邻位上存在连续存在的过程，则将标志位设置为1，否则将其设置为0。

位图中的一串0表示相对分配单元中有一个孔，而1的字符串表示相对分配单元中的过程。

使用位图的缺点

OS必须为位图分配一些内存，因为它存储了有关分配单元的详细信息。大量的内存不能用于加载任何进程，因此降低了多进程的程度以及吞吐量。在上图中，分配单位是4位，即0.5位。这里，位图的1位表示1位的分配单位。

1个分配单元的大小= 4位
位图大小= 1 /(4 + 1)=总内存的1/5。

因此，在这个位图配置中，总内存的1/5被浪费了。

要识别内存中的任何空洞，操作系统需要在位图中搜索0字符串。这种搜索花费了大量的时间，这使得系统在一定程度上效率低下。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

链表动态分区 - 操作系统教程™

跟踪自由或填充分区的更好和最流行的方法是使用链表。

在这种方法中，操作系统维护一个链表，每个节点代表每个分区。每个节点都有三个字段。

节点的第一个字段存储一个标志位，该标志位显示该分区是一个洞还是某个进程在里面。
第二个字段存储分区的起始索引。
第三个字段存储分区的结束索引。

如果某个分区在某个时间点被释放，那么该分区将与其相邻的空闲分区合并，而不会做任何额外的工作。

在使用这种方法时需要注意一些要点。

操作系统必须非常清楚要添加到链表中的新节点的位置。但是，根据起始索引的增加顺序添加节点是可以理解的。
由于双链表中的节点也可以跟踪其之前的节点，所以使用双链表将会对性能产生一些积极影响。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分区算法 - 操作系统教程™

操作系统实现了各种算法，以便找出链表中的空洞并将它们分配给进程。

关于每种算法的解释如下。

1. 第一拟合算法

第一拟合算法(First Fit)算法扫描链表，每当它找到第一个足够大的孔来存储进程时，它就会停止扫描并将进程加载到该进程中。该过程产生两个分区。其中，一个分区将是一个空洞，而另一个分区将存储该进程。

First Fit算法按照起始索引的递增顺序维护链表。这是所有算法中最简单的实现方式，与其他算法相比，它产生更大的空洞。

2. 下一个拟合算法

Next Fit算法与First Fit算法类似，不同之处在于，Next fit从先前分配空洞的节点扫描链表。

下一个适合不扫描整个列表，它开始扫描下一个节点的列表。下一个拟合背后的想法是列表已被扫描一次，因此在列表的其余部分查找空洞的可能性更大。

该算法的实验表明，下一个拟合并不比第一个拟合更好。所以这些日子在大多数情况下都没有被使用。

3. 最佳拟合算法

最佳拟合算法试图找出列表中可能的最小空洞，以适应流程的大小要求。

使用Best Fit有一些缺点。

由于每次扫描整个列表并试图找出能够满足过程要求的最小空洞，因此速度较慢。
由于整个尺寸与工艺尺寸之间的差异非常小，所产生的孔将会小到不能用于加载任何工艺，因此它仍然没有用处。尽管算法的名称最适合，但它并不是最好的算法。

4. 最差拟合算法

最差匹配算法每次都扫描整个列表，并试图找出列表中最大的空洞，以满足过程的要求。

尽管这个算法产生了更大的漏洞来加载其他进程，但这并不是更好的方法，因为它比较慢，因为它每次都搜索整个列表。

5. 快速拟合算法

快速拟合算法建议保留常用大小的不同列表。虽然，实际上这并不是可以暗示的，因为程序需要花费很多时间来创建不同的列表，然后花费空间来加载进程。

第一个拟合算法是所有算法中最好的算法，这是因为

与其他算法相比，花费的时间更少。
它会产生更大的空洞，以后可以用来加载其他进程。
这是最容易实现的。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分页技术 - 操作系统教程™

动态分区的缺点

动态分区的主要缺点是外部碎片。尽管这可以通过压缩来消除，但正如我们前面所讨论的那样，压缩使得系统效率低下。

我们需要找一种替代机制，以更优化的方式加载分区中的进程。让我们讨论一个称为分页的动态灵活机制。

需要分页

让我们考虑一个大小为2 MB的进程P1和分为三个分区的主内存。在三个分区中，两个分区是每个大小为1 MB的空洞。

P1需要在主存中加载2 MB空间。我们有两个1MB的空洞，但它们不是连续的。

虽然在主存储器中有2MB空间可用，但这些空间在连续使用之前一直没有用处。这是一个需要解决的严重问题。

我们需要有某种机制可以在内存的不同位置存储一个进程。

分页后的想法是将页面分成多个页面，这样就可以将它们存储在不同的空洞中。我们将在下一节讨论分页相关的例子。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分页技术实例 - 操作系统教程™

在操作系统中，分页是一种存储机制，用于以页面形式从辅助存储器检索进程到主内存中。

分页背后的主要思想是以页面的形式划分每个进程。主存也将以帧的形式分割。

进程的一页将被存储在存储器的一个帧中。分页可以存储在内存的不同位置，但优先级始终是查找连续的帧或空洞。

进程页面只有在需要时才会被带入主内存，否则它们将驻留在辅助存储中。

不同的操作系统定义不同的帧大小。每个帧的大小必须相等。考虑到页面被映射到页面中的帧，页面大小需要与帧大小相同。

示例

让我们考虑主存储器大小为16Kb，帧大小为1KB，因此主存储器将被分成每个1KB的16个帧的集合。

系统中有4个进程，分别是4KB的P1，P2，P3和P4。每个进程分为每个1 KB的页面，以便一个页面可以存储在一个帧中。

最初，所有的帧都是空的，因此进程的页面将以连续的方式存储。

下图显示了框架，页面两者之间的映射。

让我们考虑一下，P2和P4在一段时间后会转移到等待状态。现在，8个帧变空了，因此可以将其他页面加载到空闲的地方。大小为8 KB(8页)的进程P5正在就绪队列内等待。

鉴于这一事实，在内存中有8个不连续的帧，分页提供了将流程存储在不同位置的灵活性。因此，可以在P2和P4的地方加载进程P5的页面。

内存管理单元

内存管理单元(MMU)的目的是将逻辑地址转换为物理地址。逻辑地址是CPU为每个页面生成的地址，而物理地址是存储每个页面的帧的实际地址。

当CPU使用逻辑地址访问页面时，操作系统需要获取物理地址以物理访问该页面。

逻辑地址有两部分。

页码
偏移量

OS的内存管理单元需要将页码转换为帧号。

示例

考虑到上面的图像，假设CPU要求进程P3的第4页的第10个字。由于处理P1的第4号页面被存储在第9号帧，因此第9帧的第10个字将作为物理地址返回。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

二进制地址基础知识 - 操作系统教程™

计算机系统将二进制地址分配给内存位置。但是，系统使用位数来寻址内存位置。

使用1位，可以解决两个存储位置。使用2位，我们可以解决4个问题，使用3个位解决8个存储器位置问题。

可以在地址中的位数与存储器位置的范围之间的映射中识别模式。

我们知道，

使用1比特位，可以表示2 ^ 1，即2个存储位置。
使用2比特位，可以表示2 ^ 2，即4个存储位置。
使用3比特位，可以表示2 ^ 3，即8个存储位置。
因此，如果概括这些，
使用n位，可以分配2 ^ n个存储位置。

n位地址→2 ^ n个存储位置

这n位可以分成两部分，即K位和(n-k)位。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

物理和逻辑地址空间 - 操作系统教程™

物理地址空间

系统中的物理地址空间可以被定义为主存储器的大小。将进程大小与物理地址空间进行比较非常重要。进程大小必须小于物理地址空间。

物理地址空间 = 主内存的大小

如果，物理地址空间= 64 KB = 2 ^ 6 KB = 2 ^ 6 X 2 ^ 10 Bytes = 2 ^ 16字节

考虑一下，
字大小= 8字节= 2 ^ 3字节

因此，
物理地址空间(以字为单位)=(2 ^ 16)/(2 ^ 3)= 2 ^ 13字

因此，
物理地址= 13位

一般来说，
如果，物理地址空间 = N个字

那么物理地址= log2N

逻辑地址空间

逻辑地址空间可以定义为进程的大小。进程的大小应该足够小，以便它可以驻留在主内存中。

逻辑地址空间= 128 MB =(2 ^ 7 X 2 ^ 20)字节= 2 ^ 27字节
字大小= 4字节= 2 ^ 2字节

逻辑地址空间(以字为单位)=(2 ^ 27)/(2 ^ 2)= 2 ^ 25字
逻辑地址= 25位

一般来说，
如果，逻辑地址空间 = L个字
然后，逻辑地址 = Log2L位

什么是单词？

Word是内存的最小单位。它是字节的集合。在分析输入到解码器的n位地址和从解码器产生的2 ^ n个存储位置之后，每个操作系统定义不同的字长。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

页表 - 操作系统教程™

页表是虚拟内存系统用来存储逻辑地址和物理地址之间映射的数据结构。

CPU为进程页面生成逻辑地址，因此它们通常由进程使用。

物理地址是存储器的实际帧地址。它们通常由硬件或更具体地由RAM子系统使用。

下面给出的图像认为，

物理地址空间= M个字
逻辑地址空间= L个字
页面大小= P字

物理地址= log 2 M = m位
逻辑地址= log 2 L = 1位
页偏移量= log 2 P = p位

CPU始终通过其逻辑地址访问进程。但是，主存仅识别物理地址。

在这种情况下，一个名为内存管理单元的单元出现在图片中。它将逻辑地址的页码转换为物理地址的帧号。两个地址的偏移量保持不变。

要执行这个任务，内存管理单元需要一个由页表完成的特殊映射。页表存储与页表的页码相对应的所有帧号。

换句话说，页面表将页码映射到其在存储器中的实际位置(帧号)。

下面给出的图像显示了如何在偏移的帮助下访问帧的所需字。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

从页表映射到主内存 - 操作系统教程™

在操作系统中，总是需要从逻辑地址映射到物理地址。但是，该过程涉及如下定义的各个步骤。

1. 生成逻辑地址

CPU为进程的每个页面生成逻辑地址。这包含两部分:页码和偏移量。

2. 缩放

要确定进程的实际页码，CPU将页表基地存储在特殊的寄存器中。每次生成地址时，都会将页表基数的值添加到页码中，以获取表中页表项的实际位置。这个过程称为缩放。

3. 生成物理地址

所需页面的帧号由其在页面表中的条目确定。生成的物理地址也包含两部分:帧号和偏移量。偏移将类似于逻辑地址的偏移量，因此它将从逻辑地址复制。

4. 获取实际的帧数

帧号和来自物理地址的偏移量被映射到主存储器以获得实际的字地址。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

页表项 - 操作系统教程™

除了页面帧号之外，页面表还包含一些表示关于页面的额外信息的位。

下面来看看每个比特代表什么分页。

1. 禁用高速缓存

有时候，最接近CPU的信息和最接近用户的信息之间存在差异。操作系统总是希望CPU尽快访问用户的数据。 CPU访问某些情况下可能不准确的缓存，因此，操作系统可以禁用所需页面的缓存。如果缓存被禁用，则该位被设置为1。

2. 引用

本教程稍后会介绍各种页面替换算法。如果页面在最后一个时钟周期被引用，则该位被设置为1，否则它保持为0。

3. 修改

如果页面已被修改，则该位将被设置，否则它将保持为0。

4. 保护

保护字段表示在页面上应用的保护级别。它可以只读或读写和执行。需要记住它不是一个点，而是一个包含许多比特的字段。

5. 存在/缺席

在请求分页的概念中，所有页面不需要存在于主存储器中。因此，对于存在于主存储器中的所有页面，该位将被设置为1，并且该位对于所有不存在的页面。

如果某个页面不在主内存中，则称为页面错误。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

查找最佳页面大小 - 操作系统教程™

我们已经看到，较大的页表会导致额外的开销，因为必须将该表分成页面，然后将其存储到主内存中。

我们担心的是执行进程而不是执行页表。页表为执行过程提供了支持。页面越大，开销越高。

例如，我们知道 -

页面大小=页面表中的页面条目数量一个页面条目的X大小
下面来看一个例子，
虚拟地址空间= 2 GB = 2 X 2 ^ 30字节
页面大小= 2 KB = 2 X 2 ^ 10字节
页表中的页数=(2 X 2 ^ 30)/(2 X 2 ^ 10)= 1 M页

将会有100万页这是相当大的数字。但是，尝试使页面大小更大，例如:2MB。

然后，页表中的页数=(2 X 2 ^ 30)/(2 X 2 ^ 20)= 1K页。

如果比较两种情况，可以知道页面大小与页面大小成反比。

在分页中，最后一页总会有浪费。如果虚拟地址空间不是页面大小的倍数，那么将剩余一些字节，并且必须将整个页面分配给那些许多字节。这只是一个开销。

让我们考虑一下，

页面大小= 2 KB
虚拟地址空间= 17 KB
然后页数 = 17 KB / 2 KB

页数将为9，但第9页只包含1个字节，剩余的页面将被浪费。

一般来说，

如果页面大小= p个字节
项目大小= e字节
虚拟地址空间= S字节
然后，开销:O =(S / p)X e +(p / 2)

平均而言，虚拟空间中浪费的页面数量为p / 2(总页数的一半)。

因为，最小的开销，

∂O/∂p = 0
-S/(p^2) + ½ = 0
p = √ (2.S.e) bytes

因此，如果页面大小为√(2.S.e)字节，则开销将很小。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

虚拟内存 - 操作系统教程™

虚拟内存是一种存储方案，为用户提供了一个拥有非常大的主内存的幻觉。这是通过将辅助存储器的一部分作为主存储器来完成的。

在这种方案中，用户可以加载比可用主存更大的进程，因为存在内存可用于加载进程的错觉。

操作系统不是在主内存中加载一个大进程，而是在主内存中加载多个进程的不同部分。

通过这样做，多程序的程度将会增加，因此CPU利用率也会增加。

虚拟内存如何工作？

在现代语言中，虚拟内存近来变得非常普遍。在这种方案中，无论何时需要将一些页面加载到主存储器中用于执行，并且存储器对于那些许多页面不可用，那么在这种情况下，而不是停止页面进入主存储器，OS搜索最近最少使用的RAM区域或未被引用的RAM区域，并将其复制到辅助存储器中以为主存储器中的新页面留出空间。

由于所有这些过程都是自动发生的，因此它使电脑感觉像是拥有无限的RAM。

按需分页

按需分页(Demand Paging)是虚拟内存管理的一种流行方法。在需求分页中，最少使用的进程页面存储在辅助存储器中。

当需求发生或发生页面错误时，页面会被复制到主存储器。有各种页面替换算法用于确定将被替换的页面。稍后我们将详细讨论它们。

虚拟内存管理系统的快照

假设2个进程，P1和P2，每个包含4个页面。每个页面大小是1 KB。主存储器包含8个每个1 KB的帧。操作系统驻留在前两个分区中。在第三个分区中，P1的第1页被存储，而其他帧也被显示为在主存储器中填充了不同的进程页面。

两个页面的页表都是1 KB大小，因此每个页面可以放在一个框架中。这两个进程的页表包含图像中也显示的各种信息。

CPU包含一个寄存器，其中包含页表的基址，在P1的情况下为5，在P2的情况下为7。当涉及访问实际的相应条目时，该页表基地址将被添加到逻辑地址的页码。

虚拟内存的优点

多程序的程度将会增加。
用户可以用较少的真实RAM运行大型应用程序。
不需要购买更多的内存RAM。

虚拟内存的缺点

由于交换需要时间，系统变慢。
切换应用程序需要更多时间。
用户将有较小的硬盘空间供其使用。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

后备缓冲器 - 操作系统教程™

寻呼的缺点

页表的大小可能非常大，因此浪费了主存。
CPU将花费更多时间从主存储器中读取单个字。

如何减少页面大小

页面大小可以通过增加页面大小来减小，但会导致内部碎片，并且也会导致页面浪费。
其他方式是使用多级分页，但增加了有效访问时间，因此这不是一个实际的方法。

如何减少有效的访问时间

CPU可以使用一个寄存器，里面存储页表，这样访问页表的访问时间可以变得非常少，但是寄存器并不便宜，并且与页表大小相比非常小，因此这也不是实用的方法。
为了克服分页中的这些缺点，我们寻找一种比寄存器便宜并且比主存更快的存储器，以便CPU可以一次又一次地访问页表所需的时间可以减少，并且它只能聚焦访问实际的单词。

参考地点

在操作系统中，引用局部性的概念表明，OS不能将整个进程加载到主存储器中，而只能加载主存储器中经常由CPU访问的那些页面数量，以及OS 也可以仅加载那些对应于那些许多页面的页表项。

转换后备缓冲器(TLB)

可将转换后备缓冲区定义为内存缓存，可用于减少一次又一次访问页表所需的时间。

它是一个更靠近CPU的内存缓存，CPU访问TLB所用的时间少于访问主内存所花费的时间。

换句话说，TLB比主存更快更小，但比寄存器更便宜，更大。

TLB遵循参考位置的概念，这意味着它仅包含CPU经常访问的那些许多页面项。

EAT = P (t + m) + (1 - p) (t + k.m + m)

其中，p→TLB命中率，t→访问TLB的时间，m→访问主存储器所需的时间k = 1，如果已实现单层寻呼。

通过公式，就可以清楚地知道了。

如果TLB命中率提高，有效访问时间将会减少。
在多级寻呼的情况下，有效的访问时间将会增加。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

按需分页 - 操作系统教程™

根据虚拟内存的概念，要执行某个进程，只需要在主内存中存在一部分过程，这意味着在任何时候只有少数几页才会出现在主内存中。

但是，决定哪些页面需要保存在主存储器中，哪些页面需要保存在辅助存储器中，这很困难，因为不能预先说明某个过程在特定时间需要特定的页面。

因此，为了克服这个问题，有一个叫做按需分页(Demand Paging)的概念被引入。它建议将所有帧的页面保留在辅助存储器中，直到它们被需要为止。换句话说，它表示在需要之前不要在主内存中加载任何页面。

每当首次在主存中引用任何页面时，该页面将在辅助存储器中找到。

之后，它可能会或可能不会出现在主内存中，具体取决于本教程后面将介绍的页面替换算法。

什么是页面错误？

如果引用的页面不存在于主内存中，那么将会有一个未命中的概念被称为页面遗漏或页面错误。

CPU必须从辅助存储器访问遗漏页面。如果页面错误的数量非常多，那么系统的有效访问时间将变得非常高。

什么是抖动？

如果页面错误的数量等于参考页面的数量或者页面错误的数量如此之高以致CPU在从辅助存储器读取页面时仍然忙，则有效访问时间将是 CPU从辅助存储器读取一个字。这个概念被称为抖动。

如果页面错误率为PF%，则从辅助存储器获取页面并再次重新启动所需的时间为S(服务时间)，并且存储器访问时间为ma，那么有效访问时间可以表示为;

EAT = PF X S + (1 - PF) X (ma)

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

转换页表 - 操作系统教程™

转换页表是由操作系统为所有进程维护的全局页表。在转换页表中，条目数等于主存储器中的帧数。它可以用来克服页表的缺点。

无论是否存在于主存储器中，总是为页面保留一个空间。但是，如果页面不存在，这只是内存的浪费。

可以通过反转页面表来节省这种浪费。我们可以只保存主存中存在的页面的细节。框架是索引，保存在块内的信息将是进程ID和页码。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

页面替换算法 - 操作系统教程™

页面替换算法决定哪个内存页面将被替换。替换过程有时称为换出或写入磁盘。在主存储器中找不到请求的页面时(页面错误)，完成页面替换。

虚拟内存有两个主要方面，即帧分配和页面替换。拥有最佳的帧分配和页面替换算法是非常重要的。帧分配全部是关于将多少帧分配给进程，而页面替换则是确定需要替换的页码，以便为请求的页面留出空间。

如果算法不是最优的？

如果分配给进程的帧数量不够或不准确，则可能会出现抖动问题。由于缺少帧，大部分页面将驻留在主内存中，因此会出现更多页面错误。但是，如果操作系统将更多的帧分配给进程，则可能会出现内部碎片。
如果页面替换算法不是最优的，那么也会出现抖动问题。如果在不久的将来会引用被请求的页面替换的页面数量，那么将会有更多的插入和换出数量，因此操作系统必须执行更多的替换操作，这会导致性能不足。

因此，最佳页面替换算法的任务是选择可限制抖动的页面。

页面替换算法的类型

有各种页面替换算法。每种算法都有一个不同的方法，用来替换页面。

最佳页面替换算法- 这种算法取代了将来不会被引用的页面。虽然它不能实际实行，但可以用作基准。其他算法在最优性方面与此相比较。
最近使用过的(LRU)页面替换算法 - 该算法替代长时间未被引用的页面。该算法与最佳页面替换算法相反。
FIFO - 在这个算法中，维护一个队列。首先分配帧的页面将首先被替换。换句话说，在队列稀有端的页面将被替换为每个页面错误。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

Belady异常 - 操作系统教程™

在LRU和最佳页面替换算法的情况下，可以看出，如果增加帧数，页面错误的数量将会减少。然而，Balady发现，在FIFO页面替换算法中，随着帧数的增加页面错误的数量会增加。

在某些情况下，这是FIFO算法显示的奇怪行为。这一个异常称为Belady异常。

我们来看看下面一个的例子:

引用字符串为:0 1 5 3 0 1 4 0 1 5 3 4 。分析两种情况下FIFO算法的行为。

情况1:帧数= 3

页面错误数量= 9

情况2:帧数= 4

页面错误数量= 10

因此，在这个例子中，页面错误的数量正在增加，因为这增加了帧的数量，所以这受到了Belady异常现象的影响。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分段 - 操作系统教程™

在操作系统中，分段是一种内存管理技术，其中内存分为可变大小的部分。每个部分被称为可以分配给进程的段。

有关每个段的详细信息存储在称为段表的表中。分段表存储在一个(或多个)分段中。

分段表主要包含两个关于分段的信息:

基:它是细分分段的基地址
限制:它是分段的长度。

为什么需要分段？

到目前为止，我们使用分页作为主要内存管理技术。分页更接近操作系统而不是用户。它将所有进程划分为页面形式，而不管进程是否具有需要在同一页面中加载的某些相关功能部分。

操作系统不关心用户对过程的看法。它可以将相同的功能划分为不同的页面，这些页面可以或不可以同时加载到存储器中。它降低了系统的效率。

将进程划分为细分部分最好是细分。每个段包含相同类型的功能，例如main函数可以包含在一个分段中，并且库函数可以包含在另一个分段中。

逻辑地址按段表转换为物理地址

CPU产生一个包含两部分的逻辑地址:

分段号
偏移量

分段号被映射到段表。将各段的限制与偏移进行比较。如果偏移量小于极限值，则地址有效，否则由于地址无效而引发错误。

在有效地址的情况下，该段的基地址被添加到偏移量以获得主存储器中实际字的物理地址。

分段的优势

没有内部碎片
平均分段大小大于实际页面大小。
较少开销
重定位段比整个地址空间更容易。
与分页中的页表相比，分段表更小。

分段的缺点

它可以有外部碎片。
很难将连续内存分配给可变大小的分区。
昂贵的内存管理算法。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分页与分段比较 - 操作系统教程™

分页与分段比较，如下表所示 -

编号	分页	分段
1	非连续的内存分配	非连续的内存分配
2	分页将程序分成固定大小的分页。	分段将程序分成可变大小的段。
3	由操作系统负责	由编译器负责。
4	分页比分段更快	分段比分页慢
5	分页更接近操作系统	分段更接近用户
6	它会遭受内部碎片问题	它会遭受外部碎片问题
7	没有外部碎片	没有外部碎片
8	逻辑地址分为:页码和页码偏移	逻辑地址分为:分段号和分段偏移量
9	页表用于维护分页信息。	分段表维护分段信息
10	页表项具有帧号和一些标志位，以表示关于分页的细节。	分段表项具有分段的基地址和段的一些保护位。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

分段的分页 - 操作系统教程™

纯粹的分段并不是很流行，并没有被许多操作系统所使用。但是，分段可以与分页结合使用，以从两种技术中获得最佳功能。

在分段的分页中，主存储器被分成可变大小的段，它们被进一步分成固定大小的页面。

页面比分段小。
每个段都有一个页表，这意味着每个程序都有多个页表。
逻辑地址表示为分段号(基地址)，页码和页面偏移量。

分段号 → 它指向相应的分段号。
页码 → 它指向分段中的确切页面。
页面偏移 → 用作页面帧内的偏移量。

每页表都包含有关该分段每个页面的各种信息。分段表包含有关每个分段的信息。每个分段表项都指向一个页表项，并且每个页表项都被映射到一个分段内的页面。

逻辑地址到物理地址的转换

CPU产生一个分为两部分的逻辑地址:分段号和分段偏移。分段偏移必须小于分段限制量。偏移量进一步分为分页码和分页偏移量。为了映射页表中的确切分页码，分页码被添加到页表基地中。

具有页面偏移量的实际帧号被映射到主存储器以在该过程的某个段的页面中获得期望的字。

分段分页的优点

它减少了内存使用量。
分页表大小受到分段大小的限制。
分段表只有一个对应于一个实际分段的条目。
外部碎片不存在。
它简化了内存分配。

分段分页的缺点

内部碎片将在那里。
与分页相比，分段复杂度要高得多。
分页表需要连续存储在内存中。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件管理

文件的属性 - 操作系统教程™

什么是文件？

文件可以定义为一个存储记录序列的数据结构。文件存储在文件系统中，该文件系统可能存在于磁盘或主存储器中。文件可以是简单的(纯文本)或复杂的(特殊格式)。

文件的集合被称为目录。在不同级别的目录集合被称为文件系统。

文件的属性

常见的文件属性如下所示

编号	属性	描述
1	名称	每个文件都包含文件在文件系统中被识别的名称。同一目录中不能有两个同名的文件。
2	标识符	每个文件都有其自己的扩展名，用于标识文件的类型。例如，文本文件的扩展名为.txt，视频文件的扩展名为.mp4。
3	类型	在文件系统中，文件分为不同的类型，如:视频文件，音频文件，文本文件，可执行文件等。
4	位置	在文件系统中，有几个位置可以存储文件。每个文件都将其位置作为其属性。
5	大小	文件的大小是其最重要的属性之一。这是指文件在内存中获取的字节数。
6	保护	计算机的管理员可能希望为不同的文件提供不同的保护。因此，每个文件都将自己的一组权限传送给不同的用户组。
7	时间和日期	每个文件都带有一个时间戳，其中包含上次修改文件的时间和日期。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件上的操作 - 操作系统教程™

可以在文件上执行各种操作。我们将在下面中详细地看到。

编号	操作	描述
1	创建	文件的创建是文件上最重要的操作。不同类型的文件通过不同的方法创建，例如文本编辑器用于创建文本文件，文字处理器用于创建文字文件，图像编辑器用于创建图像文件。
2	写入	写入文件与创建文件不同。操作系统为每个指向文件中需要写入数据的位置的文件维护一个写指针。
3	读取	每个文件都以三种不同的模式打开:读取，写入和追加。一个读指针由OS维护，指向数据已经被读取的位置。
4	复位	重新定位只是根据用户的需求向前或向后移动文件指针。它也被称为寻求。
5	删除	删除文件不仅会删除存储在文件中的所有数据，还会删除文件的所有属性。分配给文件的空间现在变得可用，并且可以分配给其他文件。
6	截短	截断仅仅是删除文件，除了删除属性。虽然存储在文件内的信息被替换，但文件并未完全删除。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件访问方法 - 操作系统教程™

文件访问方法

看看访问存储在辅助存储器中的文件的各种方法。

顺序访问

大多数操作系统按顺序访问文件。换句话说，可以说大多数文件需要由操作系统按顺序访问。

在顺序访问中，操作系统逐字读取文件。维护一个指针，该指针最初指向文件的基地址。如果用户想要读取文件的第一个字，那么指针将该字提供给用户并将其值增加1个字。这个过程一直持续到文件结束。

现代文字系统确实提供了直接访问和索引访问的概念，但最常用的方法是顺序访问，因为大多数文件(如文本文件，音频文件，视频文件等)需要按顺序访问。

直接访问

在数据库系统中，直接访问通常是必需的。在大多数情况下，需要从数据库中过滤信息。在这种情况下，顺序访问可能非常慢并且效率低下。

假设每个存储块存储4条记录，并且知道需要的记录存储在第10个块中。在这种情况下，顺序访问将不会执行，因为它将遍历所有块以访问所需的记录。

直接访问将提供所需的结果，尽管操作系统必须执行一些复杂的任务，例如确定所需的块号。但是，这通常在数据库应用程序中实现。

索引访问

如果文件可以在任何字段上排序，那么可以将索引分配给一组特定的记录。但是，特定的记录可以通过其索引来访问。索引只不过是文件中记录的地址。

在索引访问中，在大型数据库中搜索变得非常快捷，但需要在内存中留出一些额外的空间来存储索引值。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

目录结构 - 操作系统教程™

什么是目录？

目录可以被定义为磁盘上相关文件的列表。该目录可以存储一些或整个文件属性。

为了在不同的操作系统上获得不同文件系统的好处，可将硬盘划分为不同大小的分区数。分区也称为卷或小型磁盘。

每个分区必须至少有一个目录，其中可以列出分区的所有文件。为目录中的每个文件维护一个目录条目，该目录存储与该文件相关的所有信息。

一个目录可以被视为一个文件，其中包含一堆文件的元数据。每个目录都支持文件上的许多常用操作:

文件创建
搜索文件
文件删除
重命名文件
遍历文件
文件列表

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

一级目录 - 操作系统教程™

每个文件包含一个条目的目录出现在磁盘文件系统上。如下图所示 -

这种类型的目录可以用于简单的系统。

优点

实现非常简单。
如果文件的大小非常小，则搜索速度会更快。
由于只有一个目录，因此文件创建，搜索和删除非常简单。

缺点

不能有两个具有相同名称的文件。
该目录可能非常大，因此搜索文件可能需要很长时间。
保护不能为多个用户执行。
没有办法将相同类型的文件分组。
为每个文件选择唯一的名称有点复杂，并限制了系统中的文件数量，因为大多数操作系统限制了用于构建文件名的字符数。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

两级目录 - 操作系统教程™

在两级目录系统中，可以为每个用户创建一个单独的目录。有一个主目录，其中包含专用于每个用户的单独目录。对于每个用户，第二级存在不同的目录，其中包含用户文件组。系统不允许用户未经许可进入其他用户的目录。

两级目录系统的特点

每个文件的路径名为/User-name/directory-name/
不同的用户可以拥有相同的文件名。
由于只有一个用户的列表需要遍历，搜索变得更有效率。
同一种文件不能分组到一个特定用户的单个目录中。

每个操作系统都将一个变量保存为包含当前目录名称(当前用户名)的PWD，以便可以适当地进行搜索。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

树型结构目录 - 操作系统教程™

在树结构的目录系统中，任何目录条目都可以是文件或子目录。树结构的目录系统克服了两级目录系统的缺点。现在可以将类似的文件分组到一个目录中。

每个用户都有自己的目录，并且不能进入其他用户的目录。但是，用户有权读取根数据，但他不能写入或修改此数据。只有系统管理员才能完全访问根目录。

在这个目录结构中搜索更有效率。使用当前工作目录的概念。一个文件可以通过两种类型的路径访问，无论是相对的还是绝对的。

绝对路径是文件相对于系统根目录的路径，而相对路径是相对于系统当前工作目录的路径。在树形目录系统中，用户有权创建文件以及目录。

文件和目录的权限

树形结构的目录系统可能由多个层次组成，因此有一组权限分配给每个文件和目录。

权限是R W X，与读取，写入和执行文件或目录有关。权限分配给三种类型的用户:所有者，组和其他人。

有一个区分目录和文件的标识位。对于一个目录，它是d，对于一个文件，它是点(.)

以下快照显示了在基于Linux的系统中分配给文件的权限。初始位d表示它是一个目录。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

非循环图结构化目录 - 操作系统教程™

树形目录系统不允许同一文件存在于多个目录中，因此共享是树形目录系统中的主要关注点。我们可以通过使目录成为一个非循环图来提供共享。在这个系统中，两个或多个目录项可以指向相同的文件或子目录。该文件或子目录在两个目录条目之间共享。

这些类型的目录图可以使用链接或别名来制作。可以为同一个文件创建多个路径。链接可以是符号(逻辑)或硬链接(物理)。

如果文件在非循环图结构化目录系统中被删除，那么

在软链接的情况下，文件只是被删除，则会留下一个悬挂指针。
在硬链接的情况下，当它的所有引用被删除，实际文件也将被删除。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件系统 - 操作系统教程™

文件系统是负责文件管理的操作系统的一部分。它提供了一种机制来存储数据和访问文件内容，包括数据和程序。一些操作系统将所有内容视为Ubuntu文件。

文件系统处理以下问题 -

文件结构 - 前面已经了解可存储文件的各种数据结构。文件系统的任务是保持最佳的文件结构。

恢复可用空间 - 每当文件从硬盘中删除时，磁盘中都会创建一个可用空间。可能有很多这样的空间需要被恢复，以便将它们重新分配给其他文件。

磁盘空间分配给这些文件 - 关于文件的主要问题是决定将文件存储在硬盘上的何处。本教程之后的章节将介绍各种磁盘调度算法。

跟踪数据位置 - 文件可以或不可以仅存储在一个块内。它可以存储在磁盘上的非连续块中。需要跟踪部分文件所在的所有块。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件系统结构 - 操作系统教程™

文件系统通过允许以方便的方式存储，定位和检索数据来提供对磁盘的有效访问。文件系统必须能够存储文件，找到文件并检索文件。

大多数操作系统对包括文件系统在内的每个任务都使用分层方法。文件系统的每一层都负责一些活动。

下面显示的图像详细说明了文件系统在不同层中的划分方式，以及每层的功能。

当应用程序要求提供文件时，第一个请求将被引导至逻辑文件系统。逻辑文件系统包含文件和目录结构的元数据。如果应用程序没有文件所需的权限，那么该图层将会引发错误。逻辑文件系统也验证文件的路径。
通常，文件被分成各种逻辑块。文件将存储在硬盘中，并从硬盘中检索。硬盘分为各种轨道和扇区。因此，为了存储和检索文件，逻辑块需要映射到物理块。该映射由文件组织模块完成。它也负责自由空间管理。
一旦文件组织模块决定了应用程序需要哪个物理块，它就会将这些信息传递给基本文件系统。基本文件系统负责将命令发布到I/O控制以获取这些块。
I/O控件包含使用它可以访问硬盘的代码。这些代码被称为设备驱动程序。 I/O控制也负责处理中断。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

主引导记录（MBR） - 操作系统教程™

主引导记录是存在于任何硬盘的第一个扇区中的信息。它包含有关操作系统在硬盘中的位置和位置的信息，以便它可以在RAM中引导。

MBR有时称为主分区表，因为它包含一个分区表，用于查找硬盘中的每个分区。

主引导记录(MBR)还包括一个程序，该程序读取包含操作系统的分区的引导扇区记录。

当打开电脑时会发生什么？

由于主存储器是具有易失性，所以当我们打开计算机时，CPU不能直接访问主内存。但是，有一个特殊的程序存储在ROM中，叫做:BIOS，它会第一次被CPU访问。

BIOS包含代码，通过执行它，CPU访问MBR的第一个硬盘分区。它包含硬盘所有分区的分区表。

因为MBR包含有关操作系统存储位置的信息，并且它还包含可以读取分区引导扇区记录的程序，因此CPU会获取所有这些信息并将操作系统加载到主内存中。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

磁盘中的数据结构 - 操作系统教程™

有多种磁盘数据结构用于实现文件系统。该结构可能会因操作系统而异。

1. 引导控制块
启动控制块包含从该卷启动操作系统所需的所有信息。它在UNIX文件系统中被称为引导块。在NTFS中，它被称为分区引导扇区。

2. 卷控制块
卷控制会阻止有关该音量的所有信息，如块的数量，每个块的大小，分区表，指向空闲块和空闲FCB块的指针。在UNIX文件系统中，它被称为超级块。在NTFS中，此信息存储在主文件表内。

3. 目录结构(每个文件系统)
目录结构(每个文件系统)包含文件名和指向相应FCB的指针。在UNIX中，它包含与文件名关联的索引节点编号。

4. 文件控制块
文件控制块包含有关文件的所有详细信息，例如所有权详细信息，权限详细信息，文件大小等。在UFS中，此详细信息存储在inode中。在NTFS中，此信息作为关系数据库结构存储在主文件表内。下图显示了一个典型的文件控制块。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

内存中的数据结构 - 操作系统教程™

到目前为止，我们已经讨论了为了实现文件系统而需要存在于硬盘上的数据结构。在这里，我们将了解要实现文件系统需要存在于内存中的数据结构。

内存数据结构用于文件系统管理以及通过缓存提高性能。该信息在安装时间加载并在弹出时丢弃。

1. 内存安装表
内存中安装表包含正在安装到系统的所有设备的列表。每当连接维护到设备时，其输入将在安装表中完成。

2. 内存目录结构缓存

这是CPU最近访问的目录列表。列表中的目录也可以在不久的将来被访问，所以最好将它们临时存储在缓存中。

3. 全系统打开文件表

这是特定时间系统中所有打开文件的列表。每当用户打开任何文件进行读取或写入时，都会在此打开的文件表中进行输入。

4. 每个进程打开文件表

它是受到每个进程打开的文件列表。由于系统中每个打开的文件都有一个列表，因此它只包含指向系统范围表中相应条目的指针。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

目录实现 - 操作系统教程™

有很多算法可以使用这些目录来实现。但是，选择合适的目录实现算法可能会显着影响系统的性能。

目录实现算法根据它们正在使用的数据结构进行分类。目前主要使用两种算法。

1. 线性列表
在这个算法中，目录中的所有文件都保持为单行列表。每个文件都包含指向分配给它的数据块的指针和目录中的下一个文件。

特点

在创建新文件时，检查整个列表是否新文件名与现有文件名匹配。如果它不存在，则可以在开始或结束时创建该文件。因此，寻找一个唯一的名字是一个大问题，因为遍历整个列表需要时间。
该列表需要在文件的每个操作(创建，删除，更新等)的情况下遍历，因此系统变得低效。

2. 哈希表

要克服目录单链表实现的缺点，有一种替代方法就是哈希表。这种方法建议使用散列表和链表。

目录中每个文件的键值对都会生成并存储在哈希表中。键可以通过在文件名上应用散列函数来确定，而键指向存储在目录中的相应文件。

现在，搜索变得高效，因为整个列表在每次操作时都不会被搜索到。只有哈希表项被使用该键检查，并且如果找到的条目然后将使用该值来获取相应的文件。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

目录实现 - 操作系统教程™

有多种方法可用于为文件分配磁盘空间。选择合适的分配方法将显着影响系统的性能和效率。分配方法提供了一种使用磁盘并访问文件的方法。

有以下可用于分配的方法。

连续分配
最大化
链接分配
集群
FAT
索引分配
链接索引分配
多级索引分配
索引节点

我们将详细讨论三种最常用的方法。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

连续分配 - 操作系统教程™

如果将块分配给文件，使得文件的所有逻辑块都得到硬盘中的连续物理块，则这种分配方案被称为连续分配。

在下面显示的图像中，目录中有三个文件。表中提到了起始块和每个文件的长度。我们可以在表格中检查连续块是否按照需要分配给每个文件。

优点

实现起来很简单。
可获得优秀的读取性能。
支持随机访问文件。

缺点

磁盘将变成碎片。
文件增长可能很困难。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

链表分配 - 操作系统教程™

链表分配解决了连续分配的所有问题。在链表分配中，每个文件都被视为磁盘块的链表。但是，分配给特定文件的磁盘块不需要在磁盘上连续存在。分配给文件的每个磁盘块都包含一个指向分配给同一文件的下一个磁盘块的指针。

优点

链接分配没有外部碎片。
可以使用任何空闲块来满足文件块请求。
只要空闲块可用，文件可以继续增长。
目录条目将仅包含起始块地址。

缺点

随机访问不提供。
指针在磁盘块中需要一些空间。
链接列表中的任何指针都不能被破坏，否则文件将被损坏。
需要遍历每个块。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

文件分配表 - 操作系统教程™

链表分配的主要缺点是它不提供对特定块的随机访问。要访问一个块，我们还需要访问它之前的所有块。

文件分配表克服了链表分配的缺点。在这个方案中，维护一个文件分配表，它收集所有的磁盘块链接。该表对每个磁盘块都有一个条目，并按块编号进行索引。

文件分配表需要被缓存以减少头部搜索的数量。现在头部不需要遍历所有的磁盘块来访问一个连续的块。

它只是访问文件分配表，从那里读取所需的块条目并访问该块。这是通过使用FAT完成随机访问的方式。它由MS-DOS和NT之前的Windows版本使用。

优点

使用整个磁盘块获取数据。
坏磁盘块不会导致所有连续的块丢失。
提供随机访问，尽管它不太快。
每个文件操作中只需要遍历FAT。

缺点

每个磁盘块都需要一个FAT条目。
根据FAT条目的数量，FAT大小可能非常大。
可以通过增加块大小来减少FAT条目的数量，但也会增加内部碎片。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

索引分配 - 操作系统教程™

FAT的限制

现有技术的局限性导致新技术的发展。到目前为止，我们已经看到了各种分配方法; 他们都有几个优点和缺点。

文件分配表尽量解决尽可能多的问题，但会导致一个缺点。块的数量越多，FAT的大小就越大。

因此，我们需要为文件分配表分配更多空间。由于文件分配表需要被缓存，因此不可能在缓存中具有尽可能多的空间。在这里我们需要一种可以解决这些问题的新技术。

索引分配方案

索引分配方案不是维护所有磁盘指针的文件分配表，而是将所有磁盘指针存储在一个称为索引块的块中。索引块不包含文件数据，但它保存指向分配给该特定文件的所有磁盘块的指针。目录条目将只包含索引块地址。

优点

支持直接访问
坏数据块会导致只有该块的丢失。

缺点

坏索引块可能导致整个文件丢失。
文件的大小取决于指针块的数量，索引块可以容纳。
有一个小文件的索引块完全是浪费。
更多的指针开销

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

链接索引分配 - 操作系统教程™

单级链接索引分配

在索引分配中，文件大小取决于磁盘块的大小。要允许大文件，我们必须将几个索引块链接在一起。在链接索引分配中，

提供文件名称的小标题
前100个块地址的集合
指向另一个索引块的指针

对于较大的文件，索引块的最后一个条目是一个指向另一个索引块的指针。这也被称为链接模式。

优点: 它消除了文件大小限制
缺点: 随机访问变得有点困难

多级索引分配

在多级指数分配中，有各种索引级别。有外层索引块包含指向内层索引块的指针，内层索引块包含指向文件数据的指针。

外层索引用于查找内层索引。
内层索引用于查找所需的数据块。

优点: 随机访问变得更好，更高效。
缺点: 文件的访问时间会更长。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

索引节点 - 操作系统教程™

在基于UNIX的操作系统中，每个文件都由一个Inode索引。 Inode是创建文件系统时创建的特殊磁盘块。文件系统中的文件或目录数量取决于文件系统中的Inode数量。

Inode包含以下信息 -

文件的属性(权限，时间戳，所有权详细信息等)
包含指向文件的前12个块的指针的多个直接块。
指向索引块的单个间接指针。如果文件不能被直接块完全索引，则使用单个间接指针。
指向磁盘块的双重间接指针，该磁盘块是指向作为索引块的磁盘块的指针的集合。如果文件太大而无法通过直接块以及单个间接指针完全索引，则使用双索引指针。
指向一个指针集合的磁盘块的三元索引指针。每个指针分别指向一个磁盘块，该块还包含一组指针，这些指针分别指向一个包含指向文件块的指针的索引块。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

空闲空间管理 - 操作系统教程™

文件系统负责将空闲块分配给文件，因此它必须跟踪磁盘中存在的所有空闲块。主要有两种方法，使用它们管理磁盘中的空闲块。

1. 位向量

在这种方法中，空闲空间列表被实现为位图向量。它包含每个位代表每个块的位数。

如果该块为空，则该位为1，否则为0。最初，所有块都是空的，因此位图向量中的每个位都包含1。

随着空间分配的进行，文件系统开始为文件分配块并将各个位设置为0。

2. 链接列表

这是空闲空间管理的另一种方法。这种方法建议将所有空闲块链接在一起，并在指向第一个空闲块的缓存中保留一个指针。

因此，磁盘上的所有空闲块将用指针连接在一起。每当块被分配时，其先前的空闲块将被链接到其下一个空闲块。

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

磁盘调度 - 操作系统教程™

如我们所知，一个进程需要两种类型的时间，CPU时间和IO时间。对于I/O，它请求操作系统访问磁盘。

但是，操作系统必须足够满足每个请求，同时操作系统必须保持流程执行的效率和速度。

操作系统用来确定接下来要满足的请求的技术称为磁盘调度。

我们来讨论一些与磁盘调度有关的重要术语。

寻道时间

寻道时间是将磁盘臂定位到满足读/写请求的指定磁道所用的时间。

倒换延迟

期望的扇区将自己倒换到可以访问R / W磁头的位置。

转换时间

这是传输数据所需的时间。

磁盘访问时间

磁盘访问时间为，

磁盘访问时间=旋转延迟+搜索时间+传输时间

磁盘响应时间

这是每个请求等待IO操作所花费时间的平均值。

磁盘调度的目的

磁盘调度算法的主要目的是从IO请求队列中选择一个磁盘请求，并决定处理该请求的时间表。

磁盘调度算法的目标

公平
始终最高
最小的遍历时间

磁盘调度算法

下面给出了各种磁盘调度算法的列表。每种算法都具有一些优点和缺点。每种算法的局限性导致了新算法的发展。

FCFS调度算法
SSTF(最短寻找时间优先)算法
SCAN调度
C-SCAN调度
LOOK调度
C-LOOK调度

易百教程移动端：请扫描本页面底部(右侧)二维码并关注微信公众号，回复："教程" 选择相关教程阅读或直接访问：http://m.yiibai.com 。

进程控制块进程调度 cpu时间批处理教程

「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」

关注作者