操作系统

mo_xiao_yang 10/15/2024 Computer Fundamentals

本笔记中的大部分来自01大学图灵机学长，笔记中引用部分为自己的感悟，请斟酌查看。

01星球：https://space.bilibili.com/1653229811

温馨提示：由于笔记的图床位于github，若是想查看图片需要魔法上网。pdf版本可以移步仓库进行查看或者下载

# 第一章操作系统总览

程序向操作系统迈进

预处理阶段
- 将我们需要引用的所有内容插入到源文件 hello.c gcc -E xxx.c -0 xxxx.i
编译阶段
- 将.i文件翻译成汇编程序gcc -S xxxx.i -0 xxxxx.S
汇编阶段
- 汇编器将 .s文件翻译成机器语言指令gcc -c xxx.s -0 xxX.0
链接阶段

硬件支持系统系统管理硬件

操作系统其实就是一个建立在应用程序和硬件之间的一道桥梁
基本功能:
- 防止硬件被滥用，尤其是一些失控程序。简单点说就是我们所写的bug
- 通过一种比较简单的机制匹配对应的应用程序，进而控制复杂的硬件
对硬件进行的抽象:
- 进程
- 虚拟内存
- 文件

进程

进程的本质就是操作系统执行的一个程序
- 从理论角度看，是对正在运行的程序过程的抽象
- 从实现角度看，是一种数据结构，目的在于清晰地刻画动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。
与进程相关
- 地址空间--从某个最小值的存储位置(通常是零)到某个最大值的存储位置的列表
- 资源集--通常包括寄存器(registers)(寄存器一般包括程序计数器(programecounter)和堆栈指针(stack pointer))、打开文件的清单、突发的报警、有关的进程清单和其他需要执行程序的信息

多个进程的执行

我们需要运行的进程大多都是要多于CPU个数的
而每个不同的进程都可以看作是在独占一个硬件设备

并发技术

通过指令的交错执行，进程在来回切换
一个进程的指令和另一个进程的指令交错执行的过程就叫做并发运行
在每个任务运行前，CPU 都需要知道任务从哪里加载和运行
- CPU寄存器
- 程序计数器

CPU上下文切换

就是先把前一个任务的 CPU 上下文(也就是 CPU 寄存器和程序计数器)保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。
而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

线程

线程(英语:thread)是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。
为什么会有线程的概念?
- 进程的颗粒度太大
- 线程主要共享的是进程的地址空间。
- 进程和线程都是一个时间段的描述，是CPU工作时间段的描述，不过是颗粒大小不同。

在操作系统中的线程和进程的概念和我们平时在写程序中的线程和进程的概念有所区别。在操作系统中，线程和进程都是一个时间段的描述，这里的颗粒度其实可以变相的理解为单位。

地址空间

在一个非常简单的操作系统中，仅仅有一个应用程序运行在内存中。为了运行第二个应用程序，需要把第一个应用程序移除才能把第二个程序装入内存。
复杂一些的操作系统会允许多个应用程序同时装入内存中运行。为了防止应用程序之间相互干扰(包括操作系统)，需要有某种保护机制。

虚拟内存

产生的问题?
- 进程直接访问物理地址会带来不可预估的风险;
- 物理内存资源是宝贵的且非常有限;
- 内存分配时，连续内存分配会产生很多难以分配的内存碎片。

虚拟内存这个概念是对于内存来说的，从某种意义上来说，虚拟内存加大了内存量。虚拟内存在硬件中是实际存在的，一般存在于内存和硬盘中。硬盘中会有一片交换区，用来和内存进行数据的交换，将不常用的资源从内存中置换出来，将常用的添加进去，从而变相的加大了内存。具体的操作会在后续提到。

文件

几乎所有操作系统都支持的另一个关键概念就是文件系统
操作系统的一项主要功能是屏蔽磁盘和其他 I/O 设备的细节特性，给程序员提供一个良好、清晰的独立于设备的抽象文件模型

特殊文件

提供特殊文件是为了使 I/O 设备看起来像文件一般
块特殊文件。
- 指那些由可随机存取的块组成的设备字特殊文件。
字符特殊文件
- 用于打印机、调制解调起和其他接受或输出字符流的设备。

管道

Linux操作系统将电脑上的所有操作都抽象成文件，这样就方便了程序员来编写程序。当然从人的视角来看，将I/O抽象成一个文件其实是十分奇怪的。所以我们就抽象出来一个特殊文件的概念，将I/O这一类较为特殊的定义为特殊文件。

并发和并行

并发和并行是即相似又有区别的两个概念
- 并行是指两个或者多个事件在同一时刻发生;
- 并发是指两个或多个事件在同一时间间隔内发生。
这两个概念是驱使计算机不断进步的动力。即如何让计算机做更多的事情，以及如何让计算机运行的更快。从概念可知，并发可以让系统同时具有多个活动，并发可以让系统变得更快。

并行有多个脑子，可以真正意义上的做到在同一时刻多个事件同时进行。并发就只有一个脑子，所以只能在宏观上认为多个事件在同一时间段内同时进行。

系统调用

操作系统提供两种功能
- 为用户提供应用程序抽象
- 管理计算机资源
只有系统调用能够进入内核态而过程调用则不能进入内核态

程序员一般在编程的过程中不能直接对内核态进行操作。一般程序员只能进行过程调用。如果要用到内核态中的内容只能使用系统调用的方法。

系统调用的种类

用于进程管理的系统调用
用于文件管理的系统调用
用于目录管理的系统调用

操作系统结构

单体结构
- 整个操作系统是以程序集合来编写的
- 优点
  - 调用任何一个所需要的程序都非常高效
- 缺点
  - 但是上千个不受限制的彼此调用往往非常臃肿和笨拙
  - 只要系统发生故障，那么任何系统和应用程序将不可用，这往往是灾难性的
分层系统
- 分层系统使用层来分隔不同的功能单元。每一层只与该层的上层和下层通信。
微内核
- 传统上，所有的层都在内核中，但是这样做没有必要
- 尽可能减少内核态中功能可能是更好的做法。
- 只有一个模块 --- 微内核 --- 运行在内核态，其余模块可以作为普通用户进程运行。
客户-服务端系统
- 现如今个人计算机基本都是这种模式

# 第二章操作系统之进程和线程

我们平常说的进程和线程更多的是基于编程语言的角度来说的，那么你真的了解什么是线程和进程吗? 那么我们就从操作系统的角度来了解一下什么是进程和线程。

# 2.1 进程

进程是对正在运行中的程序的一个抽象。

程序和进程并不能划等号，进程是对运行程序的描述。一个进程是一个正在执行程序的实例。

支持多进程的多道程序系统

严格意义来说，在某一个瞬间，CPU 只能运行一个进程
伪并行
- 伪并行是指单核或多核处理器同时执行多个进程，从而使程序更快。
因为 CPU 执行速度很快，进程间的换进换出也非常迅速，因此我们很难对多个并行进程进行跟踪

进程模型

一般来说，平时在使用的电脑只有一个CPU，那么在某一时刻，进程切换就像是上图中前者一样，用的是层次模型。而我们所希望的几个进行是一起进行的。所以就要加快处理速度，并把时间跨度拉长到一个时间段内，这要就在宏观上实现了多个程序的同时运行。

# 2.1.1 进程的创建

系统初始化(init)
- 启动操作系统时，通常会创建若干个进程
- 前台进程
- 守护进程
我们打开电脑往往需要一段时间，这段时间有大一部分就是用来启动一些系统进程和设置的开机启动软件。前台进程就是我们平时在启动的软件，比如游戏、编译器、网页等；而守护进程就是平时运行在后台的，比如别人给我们发送邮箱，我们会收到邮箱收到信件的提示，这个邮箱就是守护程序，要是没有信息发送过来，就处于休眠（sleep）状态。

需要注意一点，一个同样的进程运行了两边，会被认为是两个进程。

正在运行的程序执行了创建进程的系统调用(比如 fork)

除了在启动阶段创建进程之外，一些新的进程也可以在后面创建。通常一个正在运行的进程会发出系统调用用来创建一个或多个新进程来帮助其完成工作。

上图中的主程序就是一个进程，而在这个进程中又使用fork()创建了一个新的子进程。子程序执行ls的命令。

#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <stdio.h>  // 添加这个头文件

int main() {
 pid_t pid;
 pid = fork();  // 创建子进程

 if (pid < 0) {
     // fork() 失败
     fprintf(stderr, "ForkFailed\n");
     return 1;  // 返回非0值表示失败
 } else if (pid == 0) {
     // 子进程，执行 ls 命令
     execlp("/bin/ls", "ls", NULL);
     return 1;
 } else {
     // 父进程，等待子进程完成
     wait(NULL);
     printf("Child Complete\n");
 }
 return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

用户请求创建一个新进程
- 输入一个命令或者双击图标就可以启动程序。
初始化一个批处理工作
- 这种创建进程的情形会在大型机的批处理系统中应用。用户在这种系统中提交批处理作业。当操作系统决定它有资源来运行另一个任务时，它将创建一个新进程并从其中的输入队列中运行下一个作业。

# 2.1.2 进程的终止

正常退出(自愿的)。

就是平时正常的关闭软件
错误退出(自愿的)。

比如我们在Linux系统中cd一个不存在的目录，实际上当执行这条指令的时候已经开始了一个进程，只是因错误而使进程终止
严重错误(非自愿的)。

这个情况在我们使用编译器的时候会有遇到，比如在使用vs编写完成程序，点击运行，掷弹出黑框没有显示内容，编译器弹出警告，这个时候其实进程并没有终止只是处于中断状态，需要我们手动终止。
被其他进程杀死(非自愿的)。

最常见的就是我们使用kill命令来杀死一个进程。

# 2.1.3 进程的层次结构和状态

进程的层次结构

UNIX 进程体系

Linux的进程结构是树形的层次结构，这样的进程结构可以更好的梳理进程的逻辑，而Windows的进程结构是“众生平等”，也就是所有进程的结构都是平级的，这样的做法其实不便于对进程的管理。所以人们喜欢把服务器部署在Linux上，进程的层次结构也有一定的原因。
Windows 进程体系
- Windows 中没有进程层次的概念，Windows 中所有进程都是平等的，唯一类似于父进程得到一个特别的令牌(称为句柄)，该层次结构的是在创建进程的时候，句柄可以用来控制子进程。

进程的状态

尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态但是，进程之间仍然需要相互帮助。尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间仍然需要相互帮助。

使用cat chapterl chapter2 chapter3 | grep tree这条命令来解释上图。

首先来解释上面这段命令是什么意思：通过 cat 命令将 chapter1、chapter2 和 chapter3 文件的内容连接起来，然后通过管道将输出传递给 grep 命令，筛选出包含关键词 "tree" 的行。

那么对于这个命令来说会创建两个进程，一个是cat来连接文件内容，一个是grep来筛选包含关键词 "tree" 的行。由于在cpu中的处理时间不同，其实我们无法确定是先执行cat还是grep，但是我们所表达的是先执行cat再执行grep，为了达到这一点。我们就会将grep这个命令先阻塞，然后当cat命令执行完再进入就绪态，如果其实正好有位置执行，那么就将grep去执行。

可能会疑惑为啥要有就绪态？原因是我们执行的进程数量并不唯一，所以当执行时要先看有没有位置来执行进程，这个就需要一个中间态也就是所谓的就绪态来存放这些还未来得及执行的程序。

# 2.2 线程

多线程之间会共享同一块地址空间和所有可用数据的能力，这是进程所不具备的。
线程要比进程更轻量级。
如果多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的 I/O 处理，拥有多个线程能在这些活动中彼此重叠进行,从而会加快应用程序的执行速度。

# 2.2.1 线程的使用

单线程解决方案
- 指的是程序在同一时间点只能执行一个任务。所有操作和任务在一个线程中按顺序依次执行。大部分早期的程序，或者对并发要求不高的程序，都是单线程的。
多线程解决方案
- 程序指的是程序可以在多个线程上并发执行多个任务。每个线程是独立的执行单元，拥有自己的栈空间和程序计数器，但共享进程中的全局内存和资源。
图中就是一个多线程进行的过程，图中划波浪线就是多条线程，当调度线程的指令到达工作线程时，就会选择没有在工作的线程来执行。虽然说多线程是并发执行的，但是若是把目光聚焦在一个任务上其实就是顺序执行的。而多线程相比较于单线程来说就是多了一点线程选择。
状态机解决方案
- 一种以状态和状态转移为核心的编程模型。程序根据当前的状态执行不同的操作，并且根据某些事件或条件从一个状态转换到另一个状态。状态机通常用于描述系统中随着时间或事件变化的有限状态集合。
状态机当然不是一个机器咯，可以看作是一种思想。状态机像是一个自动机，随着不同的输入，它会改变当前的状态，并根据状态执行相应的动作。

类别	单线程	多线程	状态机
执行模式	顺序执行	并发执行（可能并行）	状态驱动，基于状态转移
并发性	无	支持并发，可能有并行	无明确的并发，但状态可以在不同事件下转移
复杂性	简单	较复杂，涉及线程同步与管理	中等复杂，需要定义状态和转移条件
优势	简单易用，适合小程序	提高资源利用率，适合并发任务	流程清晰，适合状态控制逻辑
劣势	无法充分利用多核 CPU	线程管理复杂，可能有同步问题	状态多时设计复杂，难以维护
使用场景	单一任务的脚本、命令行工具	并发服务器、GUI、并发处理程序	协议、控制系统、嵌入式开发

# 2.2.2 经典的线程模型

上图就是经典的两种线程模型，左图中可以看出一线程关系三个进程，而右图中是一个进程中存在三个线程。实现这几点最重要的原因是线程相较于进程来说更加的自由。进程和进程之间是相互独立的，不能相互干扰。但是线程可以做到这一点，所以操作线程可以更加精细的控制，但是也容易引发一些如同步问题一样的问题。

# 2.2.3 线程的系统调用

线程的创立和删除和进程基本相同，图中的yield比较有意思，它是中断的意思，和return终止不同。

# 2.2.4 POSIX编程

为了使编写可移植线程程序成为可能，IEEE 在 IEEE 标准 1003.1c中定义了线程标准。

# 2.2.5 线程实现

在用户空间中实现线程;
- 优势
  - 启动他们比进行内核调用效率更高。因而不需要切换到内核，也就不需要上下文切换，也不需要对内存高速缓存进行刷新，因为线程调度非常便捷，因此效率比较高
  - 它允许每个进程有自己定制的调度算法
- 弊端
  - 如何实现阻塞系统调用呢
  - 不可能使用轮转调度的方式调度线程
优势十分的明显，线程在用户空间实现，这样就不用每次创建线程和删除线程都要去内核中，这样就加快了速度。缺点举个例子：平时在使用软件应该都有过未响应的情况吧。那么这个未响应是整个进程挂了嘛，其实不尽然。如果采用的是用户空间实现线程的这种方法，当软件中的其中一条线程卡住了，那么对于内核来说就是整个进程卡住了，因为内核又没有线程表，它又不知道是那条线程卡住，所以就只能一条切，让整个进程停止。
在内核空间中实现线程;

在内核中实现线程优略点大略就是在用户空间中实现线程的优缺点进行相反。
在用户和内核空间中混合实现线程:

解决上述两个问题最好的方法就是和在一起咯，简单点来说就是将几个线程和在一起作为一组，这一组对应内核中的一个线程。这里要注意一点实际内核中是不存在线程的创建和删除的，线程的数量是固定。当一条线程使用完毕，那就会将这条线程的状态标识为空闲。这和steam中删除游戏是一个道理，删除游戏只是将之前存放数据的区域标识为空闲区域，后面来的数据直接将其覆盖即可。

# 2.3 进程间通信

进程间的通信要解决三个问题

进程如何传递消息给其他进程。
如何确保两个或多个线程之间不会相互干扰。例如，两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。
数据的先后顺序的问题，如果进程A产生数据并日进程 B打印数据。则进程B打印数据之前需要先等A产生数据后才能够进行打印。

# 2.3.1 竞态条件

一个后台打印程序。当一个进程需要打印某个文件时，它会将文件名放在一个特殊的后台目录(spooler directory)中。另一个进程打印后台进程(printer daemon) 会定期的检査是否需要文件被打印，如果有的话，就打印并将该文件名从目录下删除。

图中的out为将要退出的进程，而in为进程可以进入的位置。上图中发生了一个情况也就是进程A和进程B同时到达，那么两个进程就会对7同时进行修改，从而会发生进程的覆盖问题。

类似上述情况，即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)
如何解决?
- 禁止一个或多个进程在同一时刻对共享资源(包括共享内存、共享文件等)进行读写

# 2.3.2 临界区

任何时候两个进程不能同时处于临界区。
不应对 CPU 的速度和数量做任何假设。
位于临界区外的进程不得阻塞其他进程。
不能使任何进程无限等待进入临界区。

由图中可知，在t1时刻进程A到达临界区，t2时刻进程B到达临界区，但是此时进程A还没有出临界区，所以会把进程B进行堵塞。直到进程A出了临界区，进程B再进入临界区。

# 2.3.3 忙等互斥

屏蔽中断
- 在单处理器系统上，最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断
- 这个方案可行吗?进程进入临界区域是由谁决定的呢?不是用户进程吗?当进程进入临界区域后，用户进程关闭中断，如果经过一段较长时间后进程没有离开，那么中断不就一直启用不了，结果会如何?
- 对内核来说，当它在执行更新变量或列表的几条指令期间将中断屏蔽是。很方便的。
1. 屏蔽中断只能用于单处理系统，因为屏蔽中断仅仅只能屏蔽自己的CPU，无法阻止别的进程进入临界区。
2. 当两个进程同时到达时，无法判断让哪个进程先进入临界区。
3. 如果临界区的代码执行时间较长，那么再临界区外会堆积大量的请求，从而影响系统的实时性和响应速度。
4. 不能实现进程的优先级，也就是当一个进程进入临界区后，就算后续有高优先级的进程到来，也不会打开临界区。
锁变量
- 寻找一种软件层面解决方案。（也就是由程序员来编写解决方案）
利用锁变量的方法，就是用一个变量来表示临界区的状态，当lock为0时表示临界区为空，当lock为1时表示临界区被占用，这种解决方法就不会关系到操作系统层面，就是在软件层解决问题。当然这种方法也有点问题，如上图所示。当进程A进入临界区，但是由于进程A临界区较长，所以当进程B到达时，进程A仍然在临界区，所有进程A并没有更新Lock的值，所以就导致了临界区的冲突。

严格轮询法

while(TRUE){
    while(turn == 0)
    {
        // 进入关键区域
        critical_region();
        turn = 1;
        // 离开关键区域
        noncritical_region();
	}
}

while(TRUE){
    while(turn == 1){
        critical_region();
        turn = 0;
        noncritical_region();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

严格轮询法如上述代码所示，也就是将进程编号，然后到达的进程发现有进程在关键区域就不停的循环等待，直到上一个进程完成。这个方法的主要问题就是效率低下，而且如果其中一个进程卡在临界区，那么另一个进程也会被卡住，尽管另一个进程可以被执行。

Peterson算法

// 共享变量
int turn;
bool flag[2] = {false, false};  // 初始时，两个进程都不希望进入临界区
// 进程 0
void process_0() {
    while (TRUE) {
        flag[0] = true;       // 表示进程 0 想要进入临界区
        turn = 1;             // 将机会让给进程 1
        while (flag[1] && turn == 1);  // 如果进程 1 想要进入临界区并且轮到它，等待
        // 进入临界区
        critical_region();
        flag[0] = false;      // 退出临界区
        noncritical_region();
    }
}
// 进程 1
void process_1() {
    while (TRUE) {
        flag[1] = true;       // 表示进程 1 想要进入临界区
        turn = 0;             // 将机会让给进程 0
        while (flag[0] && turn == 0);  // 如果进程 0 想要进入临界区并且轮到它，等待
        // 进入临界区
        critical_region();
        flag[1] = false;      // 退出临界区
        noncritical_region();
    }
}

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

当进程 i 想要进入临界区时，它会将 flag[i] 设置为 true，表明它想要进入。

然后，它会将 turn 设置为对方进程的编号（即如果当前是进程0，它会将 turn 设置为1），表示让对方优先进入。

接着，进程会等待，直到对方进程要么没有请求进入临界区（flag[j] == false），要么不是对方的轮次（turn != j）。

当条件满足时，进程 i 进入临界区。

离开临界区后，进程会将 flag[i] 设置为 false，表示自己不再需要进入临界区。

TSL指令

测试并加锁
- TSL RX,LOCK 执行 TSL 指令的 CPU 将会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存
锁住内存总线和禁用中断不一样

enter region:
		| 复制锁到寄存器并将锁设为1
		TSL REGISTER,LOCK
		| 锁是 0 吗?
		CMP REGISTER,#O
		| 若不是零，说明锁已被设置，所以循环
		JNE enter region
		| 返回调用者，进入临界区来禁止其他 CPU 在这个
		RET

leave region:
		| 在锁中存入 0
		MOVE LOCK，#0
	| 返回调用者
	RET

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2.4 生产者-消费者问题

两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer)，将信息放入缓冲区，另一个是消费者(consumer)，会从缓冲区中取出。个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer)，将信息放入缓冲区，另一个是消费者(consumer)，会从缓冲区中取出。

生产者消费者是为了解决一下这种情况

如上图所示，进程B到达临界区，此时高优先级的进程A到达，但是由于进程B在临界区中，所以进程A无法到达临界区。但是由于CPU会优先调用优先级高的进程，但是由于进程A没进入临界区，CPU又调不了进程A，但是CPU会被进程A”吸引“，同样不会调用进程B这样就卡住了。

// 缓冲区 slot槽的数量
#define N 100
// 监视变量
int count = 0;

// 生产者
void productor()
{
	int item;
	// 无限循环
	while (1)
	{
		// 生成下一项数据
		item = prodect_item();
		if (count == N) // 如果槽位满了，那么就进入睡眠
		{
			sleep();
		}
	}
	insert_item(item); // 向槽位中增加一个进程
	count = count + 1;
	if (count == 1) // 发现有进程到来，唤醒消费者
	{
		wakeup(consumer);
	}

}

void consumer() // 消费者其实就是生产者反一下
{
	int item;
	while (1)
	{
		if (count == 0)// 当没有进程需要处理时，睡眠
		{
			sleep();
		}
	}
	// 从缓冲区取得数据
	item = remove_item();
	count = count - 1; // 数据量减一
	if (count == N - 1)// 若count没到N，那就唤醒生产者
	{
		wakeup(productor);
	}
}

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

但是上述的处理还是有一些问题。比如在某时刻，当缓冲区为空刚好消费者读取count是0暂停消费者，启用生产者放入一条数据count增加，然后要唤醒消费者。但是消费者去查看上一时刻的时候，count值任然时0，然后就进入睡眠，所以就不会处理这一条数据，而是导致生产者会一直接受数据。简单来说唤醒一个尚未进行睡眠状态的进程唤醒信号就丢了。为了解决这个问题，我们亲爱的迪杰斯特拉就提出了信号量的概念。

// 定义缓冲区大小
#define N 100

typedef int semaphore;

// 控制关键区域访问
semaphore mutex = 1;
// 统计缓冲区中空槽的数量
semaphore empty = N;
// 统计缓冲区满槽的数量
semaphore full = 0;
// 生产者
void productor() {
    int item;
    while (1) {
        item = prodect_item(); // 生成下一项数据
        down(&empty);         // 空槽数据减1
        down(&mutex);         // 进入关键区域
        insert_item(item);   // 数据放入到缓冲区当中
        up(&mutex);          // 离开关键区域
        up(&full);           // 将缓冲区的满槽的数量+1
        
        sleep(1); // 模拟生产时间
    }
}

// 消费者
void consumer() {
    int item;
    while (1) {
        down(&full);          // 缓冲区满槽-1
        down(&mutex);         // 进入关键区域
        remove_item(&item);  // 缓冲区取出数据
        up(&mutex);          // 离开关键区域
        up(&empty);          // 将缓冲区的空槽的数量+1

        consume_item(item); // 处理数据项

        sleep(1); // 模拟消费时间
    }
}

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
31
32
33
34
35
36
37
38
39
40
41

# 2.5 管程

管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。
管程有一个很重要的特性，即在任何时候管程中只能有一个活跃的进程，这一特性使管程能够很方便的实现互斥操作。

需要注意的是管程和前面的不同，管程是在用户层的概念，只有一些语言拥有，如java。

# 2.6 消息传递

消息传递系统通常包含两个基本操作：

发送消息：一个进程向另一个进程发送数据。
接收消息：一个进程从另一个进程接收数据。

消息传递在操作系统内核中一般应用于设备之间的数据传递，一般依托于计算机网络方面的知识来实现，而对于操作系统来说就是要解决重传问题。如上图所示，发送方在第一次发送后没有收到接收方的确认包，所以出发超时重传，发送和第一次数据一样的包给u接受方，但这时接收方并不知道发送方发送的数据是新数据还是老数据，所以要进行判断，而判断的方法就是包的首部携带的序号，具体内容在计算机网络中已经叙述。

# 2.7 避免锁

无招胜有招
在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用。
确保每个读操作要么读取旧的版本，要么读取新的版本

这个方法就是直接放弃掉锁，但是由于放弃掉锁，所有使用这种方法的条件比较苛刻，一般只用于读的操作。

# 2.8 调度的介绍

当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争 CPU 时间片。
当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个 CPU 可用，那么必须选择接下来哪个进程/线程可以运行。
操作系统中有一个叫做调度程序(scheduler) 的角色存在，它就是做这件事儿的，该程序使用的算法叫做调度算法(scheduling algorithm)

调度的本质就是进程对于时间片的占用，或者说是CPU对时间片的分配。

# 2.9 计算机上执行任务的两种策略

CPU密集型
- 一般是指服务器的硬盘、内存硬件性能相对CPU好很多，或者使用率低很多。系统运行CPU读写I/O(硬盘/内存)时可以在很短的时间内完成，几乎没有阻塞(等待I/O的实时间)时间，而CPU一直有大量运算要处理，因此CPU负载长期过高。
I/O密集型
- 一般是指服务器CPU的性能相对硬盘、内存硬件好很多，或者使用率低很多。系统运行多是CPU在等I/O(硬盘/内存)的读写操作，此类情景下CPU负载并不高。

如图中所示，上者为CPU密集型，下者为I/O密集型。一般CPU密集型用于电脑的计算量比较大的情况，如现在大火的人工智能，一般就是使用CPU密集型。而我们家用的电脑要平凡的调度进程，所以显然以I/O密集型更为符合要求。

# 2.10 调度时机

第一，和调度有关的问题是何时进行调度决策。存在着需要调度处理的各种情形。首先，在创建一个新进程后，需要决定是运行父进程还是子进程。
第二，在进程退出时需要作出调度决定。因为此进程不再运行(因为它将不。再存在)，因此必须从就绪进程中选择其他进程运行。
第三，情况是，当进程阻塞在 I/O 、信号量或其他原因时，必须选择另外-个进程来运行。
第四，当 I/O 中断发生时，可以做出调度决策。

一般来说第三点我们都会去考虑，其实就是正常的临界区的进出情况嘛，第三点的考虑都会包含在一二四中。

# 2.11 调度算法的分类

根据如何处理时钟中断可以把调度算法可以分为两类。
非抢占式
- 挑选一个进程，让该进程运行直到被阻塞(阻塞在 I/0 上或等待另一个进程)，或者直到该进程自动释放 CPU。
抢占式
- 选择一个进程，并使其在最大固定时间内运行。如果在时间间隔结束后仍在运行，这个进程会被挂起，调度程序会选择其他进程来运行(前提是存在就绪进程)。

# 2.12 调度系统的环境

批处理
交互式
实时

调度算法的目标

所有系统
- 公平、策略强制执行、平衡
批处理系统
- 吞吐量、周转时间、CPU利用率
交互式系统
- 响应时间、均衡性
实时系统
- 满足截止时间、可预测性

# 2.12.1 批处理中的调度

先来先服务（FCFS）
- 按照进程到达的顺序依次调度。先到达的进程会被优先处理，直到执行完成后下一个进程才开始执行。
最短作业优先（SJF）
- 选择执行时间最短的进程优先执行。若有多个进程同时到达系统中，系统会选择执行时间最短的进程。
最短剩余时间优先（SRTF）
- 这是 SJF 的抢占式版本。当一个新的进程到达系统时，如果它的执行时间比当前正在执行的进程的剩余执行时间更短，则抢占当前进程，优先执行剩余时间更短的进程。

# 2.12.2 交互式中的调度

优先级调度
- 轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。
- 每个进程都被赋予一个优先级，优先级高的进程优先运行。
- 调度程序会在每个时钟中断期间降低当前运行进程的优先级。
- 优先级可以静态分配，也可以动态分配。

静态优先级简单易实现，但灵活性较差，适用于工作负载稳定的系统。

动态优先级可以根据系统情况自适应调整，适合负载变化较大的场景，提升系统响应效率。

最短进程优先
- 交互式进程通常遵循下列模式:等待命令、执行命令、等待命令、执行命令
- 如果我们把每个命令的执行都看作一个分离的作业，那么我们可以通过首先运行最短的作业来使响应时间最短。
- 通过预测从当前可运行进程中找出最短的那一个进程

饥饿形象会在这种调度中较为平凡的出现，所谓的饥饿现象反应到这种调度方法上就是，CPU一直在跑短进程，不去跑长进程，所有就发生了饥饿现象

保证调度
- 若用户工作时有n个用户登录，则每个用户将获得 CPU 处理能力的 1/n。

这种调度的前提是所有的任务都是平级的。

彩票调度
- 为进程提供各种系统资源(例如 CPU 时间)的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得该资源。
- 可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生速度之靴的效果。

这种调度方法听上去很不靠谱，但是可以解决一些边角料问题。必然上面提到的饥饿现象。所以其实这种调度方法还是很有用的。

# 2.12.3 实时系统中的事件的分类

周期性(以规则的时间间隔发生)事件
非周期性(发生时间不可预知)事件
实时系统的调度算法可以是静态的或动态的。

# 第三章操作系统之内存管理

首先需要思考为何我们需要内存管理

上面这个图是计算机存储的分层结构，上面这个问题的答案其实很好理解：不管存储器有多大，程序大小的增长速度比内存容量的增长速度要快的多。在我们现实生活中会把cpu设计的很小，原因之一就是加快速度。

# 3.1 实现并行性

在没有存储器抽象的系统中实现并行性一种方式是使用多线程来编程。
- 人们通常希望能够在同一时间内运行没有关联的程序，而这正是线程抽象所不能提供的。
把当前内存中所有内容保存到磁盘文件中，然后再把程序读入内存即可。

如果没有存储器抽象的支持，则所有程序都必须运行在同一个地址空间中，无法实现进程之间的隔离。就比方上图的情况，当我们在编程的时候不会直接编辑绝对地址，一般进行的操作都是相对的地址。就像是我们操作数组的时候，都是从0下标开始的。上图中就是对这种情况的举例。我们编写程序a与程序b，然后我们将两个程序连续装载到内存中，那么实际地址其实就会和我们编写的相对地址发生冲突。图中拼接起来的16380号地址跳转到28，事实上要跳转的是16412，但是由于编写的时候写的28，所以就会跳转到28执行ADD命令。

# 3.2 物理内存暴露的缺点

如果用户程序可以寻址内存的每个字节，它们就可以很容易的破坏操作系统
想要运行多个程序是很困难的
如果要使多个应用程序同时运行在内存中，必须要解决两个问题：保护和重定位。

重定位的问题体现在实现并行性中已经有所体现，至于保护。其实就是用了三把锁，分别分给进程、进程表、操作系统。在进行操作的时候，进行匹配，若是匹配不是就不允许操作。

# 3.3 地址空间

进程可以用来寻址内存的地址集
每个进程都有它自己的地址空间，独立于其他进程的地址空间。
最简单的办法是使用动态重定位(dynamic relocation)技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理内存的不同区域。
- 基址寄存器和变址寄存器
- 存储数据内存的起始位置和存储应用程序的长度
如果计算机的物理内存足够大来容纳所有的进程，那么之前提及的方案或多或少是可行的。

为了解决重定位的问题，可以新增两个硬件也就是所谓的基址寄存器和变址寄存器，这两个寄存器说简单点就是记录了进程实际地址的开头和结尾的位置。当我们执行地址的操作的时候，就会加上基址寄存器中存放的该进程的基址地址，从而来正确的定位到需要操作的地址。但是随着我们软件所需的内存越来越多，由于计算机的物理内存不可能无限制度的大下去，所以为了解决这个问题提出了交换技术。

# 3.4 交换技术

把一个进程完整的调入内存，然后再内存中运行一段时间，再把它放回磁盘

交换技术如上图所示，a->c是进程ABC的加入。在d时刻进程A执行完毕，所以将进程A换出内存，e时刻进程D呗换入内存，f时刻进程B执行完毕，被换出进程。g时刻，进程A被换入内存。事实上专门有一个交换区用于交换进程。

在上述的过程其实有两个问题出现，一个是存在空闲区，如在e时刻BD之间就有空闲区，这里会用到一个技术叫做内存紧缩，但在平时我们不会去应用这个技术，因为这个技术需要的时间十分的长。而另一个问题是当进程进入到内存区在运行的过程中可能会变大，如g时刻中的A，进程大小不会一成不变，当A需要扩大是上下都被CD给顶着，没有空间来给它扩大。所以我们就需要一些方法来处理这些情况

# 3.5 内存增长处理方式

如果一个进程与空闲区相邻，那么可把该空闲区分配给进程以供其增大。
如果进程相邻的是另一个进程，就会有两种处理方式：要么把需要增长的进程移动到一个内存中空闲区足够大的区域，要么把一个或多个进程交换出去，已变成生成一个大的空闲区。
如果一个进程在内存中不能增长，而且磁盘上的交换区也满了，那么这个进程只有挂起一些空闲空间（或者可以结束该进程）

我们可以想象一个常见的情况来解决这个问题。假如有一个胖子在饭店里，这个胖子一把板凳坐不下，那么第一种解决办法如果他旁边有另一把板凳的话，那就可以把两把板凳拼在一起坐。第二种解决办法，就是把小板凳换成一个大板凳（如果店里有大板凳的话）。第三种解决办法，就是赶出去一些人，然后把赶出去的人的板凳拼在一起给这个胖子坐。第四种方法，就是让胖子等一等别人吃完腾出来板凳，或者直接不让这个胖子如饭店。

逻辑层面操作系统把数据分成不同的段来存储

代码段（codesegment/textsegment）
- 存储程序的可执行代码。
数据段（datasegment）
- 存储已初始化的全局变量和静态变量
bss段（bsssegment）
- 存储未初始化的全局变量和静态变量。
rodata段
- 存储只读数据，例如字符串常量。
栈（stack）
- 用于存储局部变量、函数参数和返回地址。
堆（heap）
- 用于动态分配内存

事实上在进程通过交换区进入到内存中往往会留出一部分来供进程进行增长

# 3.6 空闲内存的管理

位图
空闲链表

空闲内存的管理有两个方式，也就是我们数据结构中的顺序表和链表。位图的大小与管理的内存块数量成正比，也就是将每个内存块进行标号，从而进行空闲内存的管理。而链表也和数据结构的中的相同，只不过数据域存在三个值，第一个表明这块地址是否为空闲地址上图中的P代表这块地址存放了进程，H则代表这块地址为空闲地址。剩下的两位数据就是起始位置以及该块地址的长度。

按照地址顺序在链表中存放进程和空闲区

首次适配
- 内存管理器会沿着段列表进行扫描
- 首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。
下次适配
- 记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索
- 性能略低于首次匹配
最佳适配
- 试图找出最接近实际需要的空闲区
最差适配
- 总是分配最大的内存区域
快速匹配
- 为那些常用大小的空闲区维护单独的链表

首次适配算法就是直接顺序遍历链表当发现空闲区且大小足够就直接放到这个位置。下次适配算法，就是记录当前存放的位置，下次进程进入的时候就可以往这个位置往后进行查找。通过国外的某位大佬的证明，下次适配算法并没有首次适配算法效率快，尽管看上去好像是下次匹配较快。最佳适配就是找大小最为的合适的地址块。这样引申出来的问题就是被最佳设配占用的地址块在分裂余下的地址块的时候会非常的小，从而导致这些很小的地址块很难被再次利用。而最差适配就是最佳适配的反面，就去找大小最大的，但是同样也有问题，万一下一次进来一个特别大的进程，那内存中就都只剩下中等大小的进程了，那么就会发生冲突。快速匹配是就是单独拿了一张链表出来，然后将常用大小的空闲分配在这些链表上从而加快运行速度。

# 3.7 虚拟内存

基本思想: 每个程序都有自己的地址空间
这个地址空间被划分为多个称为页面(page)的块。
虚拟地址是对基址寄存器和变址寄存器的一种描述

虚拟内存就是为了解决一个程序太大，导致放不进去内存。虚拟地址是对基址寄存器和变址寄存器的一种抽象。

# 3.8 分页技术

在任何一台计算机上，程序会引用使用一组内存地址
地址可以通过索引、基址寄存器、段寄存器或其他方式产生
这些程序生成的地址被称为虚拟地址(virtual addresses) 并形成虚拟地址空间(virtual address space)

上图中MMU就是对虚拟地址进行处理，分析出对应的实际地址给总线去调用内存中的资源。

图中的左侧就是一种虚拟内存的一张虚拟地址表，可以看到这个虚拟地址表比物理内存地址表要大一倍。虚拟地址映射到物理内存地址。分页技术给这种映射提供了最小单位，分页技术将整张虚拟内存表分成一段一段的虚拟页面，而分页技术在物理内存地址中的分出来的最小单位是页框。之所以能使用分页技术的原因是，我们的一个很大的程序是由很多的代码段组成，这些代码段不可能一起运行，那么代码段与代码段的执行之间有时间差，这就给分页技术提供了可行性。

# 3.9 存在映射的页的映射

虚拟地址空间由固定大小的单元组成，这种固定大小的单元称为页(pages)。
物理内存中也有固定大小的物理单元，称为页框(page frames)。
程序试图访问地址时 MOV REG, 0

图中展示了虚拟地址如何映射到物理地址。比如虚拟地址中的前四位是用来映射的位，可以叫做是页号。页号对应过去在页表中找到对应的物理地址，然后看一下在/不在位，若为1说明在，那就根据这个号码找到物理地址的前三位，可以叫做是段号或者是页框号。然后将这个段号和虚拟地址的后12位也就是偏移量。两者一拼接就成了物理地址。

# 3.10 针对大内存的页表

多级页表
- 避免把全部页表一直保存在内存中。不需要的页表就不应该保留
倒排页表
- 针对分页层级结构中不断增加
- 实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。

多级页表就是将一张大页表拆开，拆成多张小页表，然年用新一张页表去映射这些页表，到要使用这种页表的时候就将其调用到内存中进行使用，不用了就将其移除

倒排页表是利用了数据结构中的散列表的这种结构，来进行存储页表。

# 3.11 页面置换算法

页面置换算法就是用来解决缺页问题，所谓的缺页就是当一个进程访问一个虚拟地址，但该地址对应的页不在物理内存中时，CPU 会产生缺页异常。

# 3.11.1 最优页面置换算法

在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。

这个算法就是个理想算法，在实际的操作其实很难去实现因为硬件怎么知道哪个进程将会被访问，即使在用户层面这个都难以实现

# 3.11.2 最近未使用页面算法（NRU）

状态位
每当引用页面（读入或写入）时都设置 R
写入（即修改）页面时设置 M
由硬件来设置它们非常重要。
如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟

用两个位来表示这个页面是否被引用和修改。使用一个时钟来对R状态进行修改（置0），每次换出的页面选择没有引用R和没有修改M的页面，注意如果M被修改，说明这个页面中的内容要被读入磁盘，所有不能将其换出。

# 3.11.3 先进先出置换算法（FIFO）

由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。
在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。

这个很好理解，如图中所示，1先进的，当发生缺页的时候1先出来，也就是先进先出的算法。这种算法无法保证置换出的是不常用的页面。

# 3.11.4 第二次机会页面置换算法（SC）

避免把经常使用的页面置换出去
我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。

这个就是上面两种方法的结合，就是对页面进行标记，要是发现R是0，则将其置换出来。若发现R为1，那就将其置0然后放到最后。

# 3.11.5 时钟页面置换算法（CLOCK）

对第二次机会算法的改进

页表的移动会消耗大量的资源，所以就直接用一根指针指向最晚的的页面。

# 3.11.6 最近最少使用页面置换算法（LRU）

在缺页中断时，置换未使用时间最长的页面。
用软件模拟LRU
- 最不常使用置换（NFU）
- 一个软件计数器来和每个页面关联
- NFU 最主要的问题是它不会忘记任何东西
老化算法
- 首先，在 R 位被添加进来之前先把计数器右移一位；
- 第二步，R 位被添加到最左边的位而不是最右边的位。

就如图所示，若是页面被调用，就放入1，若是没有就放入0。然后就选择最小的进行置换。

# 3.11.7 工作集置换算法

在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面）
当进程想要再次把之前调回磁盘的页面调回内存怎么办？
工作集模式
- 分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方法叫做工作集模式(working set model)
- 预先调页

# 3.11.8 工作集时钟页面置换算法

基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。
原则上来说，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。
- 为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。
指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？
- 至少调度了一次写操作
  - 指针仅仅是不停的移动，寻找一个未被修改过的页面。
- 没有调度过写操作
  - 置换一个未被修改的页面来使用

# 第四章操作系统之文件系统

所有的应用程序都需要存储和检索信息
进程运行时，它能够在自己的存储空间内存储一定量的信息
当进程终止时信息会丢失
通常需要很多进程在同一时刻访问这些信息
于长久存储的信息我们有三个基本需求
- 必须要有可能存储的大量的信息
- 信息必须能够在进程终止时保留
- 必须能够使多个进程同时访问有关信息

# 4.1 文件

文件(Files)是由进程创建的逻辑信息单元。
一个磁盘会包含几千甚至几百万个文件，每个文件是独立于其他文件的。
文件不会因为进程的创建和终止而受影响。一个文件只能在有明确删除的时候才能消失。
所有文件由操作系统进行管理，有关文件的构造、命名、访问、使用、保护、实现和管理方式都是操作系统设计的主要内容————文件系统

# 4.1.1 文件命名

文件是一种抽象机制，它提供了一种方式用来存储信息以及在后面进行读取。
Windows引入MS—DOS，称之为FAT—16，后来扩展为FAT—32
目前新的操作系统支持另外一个新的文件系统，NTFS（本机文件系统）
Windos8服务器版本——ReFS

# 4.1.2 文件结构

# 4.1.3 文件类型

很多操作系统支持多种文件类型。例如，UNIX（同样包括 OS X）和 Windows 都具有常规的文件和目录。
UNIX 具有字符特殊文件(character special file) 和块特殊文件(block special file)
常规文件一般分为 ASCII 码文件或者二进制文件
Unix嵌入make程序
分层文件系统——目录

注意Windows中是不区分大小写的，但是UNIX中是严格区分大小的

# 4.1.4 文件访问

早期的操作系统只有一种访问方式：序列访问(sequential access)。
随机访问文件(random access file)——在使用磁盘来存储文件时，可以不按照顺序读取文件中的字节或者记录，或者按照关键字而不是位置来访问记录。
读取方式
- 直接使用 read 从头开始读取
- 用一个特殊的 seek 操作设置当前位置

# 4.1.5 文件属性

文件包括文件名和数据。除此之外，所有的操作系统还会保存其他与文件相关的信息，如文件创建的日期和时间、文件大小——属性/元数据

# 4.1.6 文件操作

Create，创建不包含任何数据的文件。调用的目的是表示文件即将建立，并对文件设置一些属性。
Delete，当文件不再需要，必须删除它以释放内存空间。为此总会有一个系统调用来删除文件。
Open，在使用文件之前，必须先打开文件。这个调用的目的是允许系统将属性和磁盘地址列表保存到主存中，用来以后的快速访问。
Close，当所有进程完成时，属性和磁盘地址不再需要，因此应关闭文件以释放表空间。很多系统限制进程打开文件的个数，以此达到鼓励用户关闭不再使用的文件。磁盘以块为单位写入，关闭文件时会强制写入最后一块，即使这个块空间内部还不满。
Read，数据从文件中读取。通常情况下，读取的数据来自文件的当前位置。调用者必须指定需要读取多少数据，并且提供存放这些数据的缓冲区。
Write，向文件写数据，写操作一般也是从文件的当前位置开始进行。如果当前位置是文件的末尾，则会直接追加进行写入。如果当前位置在文件中，则现有数据被覆盖，并且永远消失。
append，使用 append 只能向文件末尾添加数据。
seek，对于随机访问的文件，要指定从何处开始获取数据。通常的方法是用 seek 系统调用把当前位置指针指向文件中的特定位置。seek 调用结束后，就可以从指定位置开始读写数据了。
get attributes，进程运行时通常需要读取文件属性。
set attributes，用户可以自己设置一些文件属性，甚至是在文件创建之后，实现该功能的是 set attributes 系统调用。
rename，用户可以自己更改已有文件的名字，rename 系统调用用于这一目的。

# 4.2 目录

# 4.2.1 一级目录系统

目录系统最简单的形式是有一个能够包含所有文件的目录。这种目录被称为根目录(root directory)

一级目录用于早期的计算机，还有一些目的单一的嵌入式系统，比如数码相机。

# 4.2.2 层次目录系统

层次目录系统就是以一颗树的形式来管理文件

# 4.2.3 路径名

当目录树组织文件系统时，需要有某种方法指明文件名。
常用的方法有两种
- 第一种方式是每个文件都会用一个绝对路径名(absolute path name)，它由根目录到文件的路径组成——/usr/ast/mailbox
- 另外一种指定文件名的方法是相对路径名(relative path name)。它常常和工作目录(working directory) （也称作当前目录(current directory)）一起使用。
支持层次目录结构的大多数操作系统在每个目录中有两个特殊的目录项. 和 ..
- dot 指的是当前目录
- dotdot 指的是其父目录（在根目录中例外，在根目录中指向自己）

# 4.2.4 目录操作

Create，创建目录，除了目录项 . 和 .. 外，目录内容为空。
Delete，删除目录，只有空目录可以删除。只包含 . 和 .. 的目录被认为是空目录，这两个目录项通常不能删除
opendir，目录内容可被读取。例如，未列出目录中的全部文件，程序必须先打开该目录，然后读其中全部文件的文件名。与打开和读文件相同，在读目录前，必须先打开文件。
closedir，读目录结束后，应该关闭目录用于释放内部表空间。
readdir，系统调用 readdir 返回打开目录的下一个目录项。以前也采用 read 系统调用来读取目录，但是这种方法有一个缺点：程序员必须了解和处理目录的内部结构。相反，不论采用哪一种目录结构，readdir 总是以标准格式返回一个目录项。
rename，在很多方面目录和文件都相似。文件可以更换名称，目录也可以。
link，链接技术允许在多个目录中出现同一个文件。这个系统调用指定一个存在的文件和一个路径名，并建立从该文件到路径所指名字的链接。这样，可以在多个目录中出现同一个文件。有时也被称为硬链接(hard link)。
unlink，删除目录项。如果被解除链接的文件只出现在一个目录中，则将它从文件中删除。如果它出现在多个目录中，则只删除指定路径名的链接，依然保留其他路径名的链接。在 UNIX 中，用于删除文件的系统调用就是 unlink。

# 4.3 文件系统的实现

# 4.3.1 文件系统的布局

文件系统存储在磁盘中。大部分的磁盘能够划分出一到多个分区，叫做磁盘分区(disk partitioning) 或者是磁盘分片(disk slicing)。
磁盘的 0 号分区称为主引导记录(Master Boot Record, MBR)，用来引导(boot) 计算机。
在 MBR 的结尾是分区表(partition table)。
MBR 可以用在 DOS 、Microsoft Windows 和 Linux 操作系统中。从 2010 年代中期开始，大多数新计算机都改用 GUID 分区表（GPT）分区方案。

# 4.3.2 引导块

MBR 做的第一件事就是确定活动分区，读入它的第一个块，称为引导块(boot block) 并执行。

# 4.3.3 超级块

紧跟在引导块后面的是超级块(Superblock)，超级块的大小为 4096 字节，从磁盘上的字节偏移 4096 开始。超级块包含文件系统的所有关键参数
- 文件系统的大小
- 文件系统中的数据块数
- 指示文件系统状态的标志
- 分配组大小

# 4.3.4 空闲空间快

文件系统中空闲块的信息——可以用位图或者指针列表的形式
位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0和1，0表示已分配该块，而1表示一个空闲块。

# 4.3.4 碎片

一般零散的单个数据通常称为片段。
磁盘块可以进一步分为固定大小的分配单元，片段只是在驱动器上彼此不相邻的文件片段。

# 4.3.5 inode

索引节点——index node
模式/权限（保护）
所有者 ID
组 ID
文件大小
文件的硬链接数
上次访问时间
最后修改时间
inode 上次修改时间

# 4.3.6 文件的实现

最重要的问题是记录各个文件分别用到了哪些磁盘块。
分配背后的主要思想是有效利用文件空间和快速访问文件
连续分配
链表分配
索引分配

连续分配

分配文件时，操作系统为整个文件分配连续的磁盘块。这种方式访问速度快，因为可以进行随机访问。但是会产生磁盘碎片，还有就是文件的扩展十分的麻烦，如果预留的空间不足要移动整个文件。

链表分配

文件的每个数据块包含指向下一个块的指针，形成链表结构。这种方式文件扩展方便，可以动态分配非连续的块。而且不会产生外部碎片。但是由于是链表方式存储，所以不能进行随机访问，而且指针也需要空间来存储，当文件的数量上去之后，也是不小的开销。

使用内存表进行链表分配

内存表简单点来看就是静态的链表，这种方式既能进行随机访问，也不会出现顺序存储的问题。但是由于这一张内存表本身就要有一个地方来进行存储，如果我们的存储空间是1T，1K作为一个文件块，那么这张表的大小将会达到亿级别，这无疑是一个很大的消耗。

索引分配（inode）

每个文件都有一个专用的索引块，索引块包含指向文件各数据块的指针。支持随机访问，读取特定数据块时可以通过索引快速定位。不需要连续的磁盘空间，文件可以分散在磁盘的不同区域。

# 4.3.7 共享文件

当多个用户在同一个项目中工作时，他们通常需要共享文件。

共享文件要处理很多的问题，首要处理的就是如何实现共享文件这一功能，即如何链接

上图中就是直接链接起来，但是这个问题很明显，就是直接破坏了文件系统树的结构，这会使文件维护十分的困难。

上图中文件A是共享文件，当用户A对其进行修改，那么这个文件A就成了另一个文件，和原本的不相同。

解决方案

第一种解决方案，磁盘块不列入目录中，而是会把磁盘块放在与文件本身相关联的小型数据结构中。目录将指向这个小型数据结构。这是 UNIX 中使用的方式（小型数据结构就是 inode）。
在第二种解决方案中，通过让系统建立一个类型为 LINK 的新文件，并把该文件放在 B 的目录下，使得 B 与 C 建立链接。新的文件中只包含了它所链接的文件的路径名。当 B 想要读取文件时，操作系统会检查 B 的目录下存在一个类型为 LINK 的文件，进而找到该链接的文件和路径名，然后再去读文件，这种方式称为符号链接(symbolic linking)。

# 4.3.8 日志结构文件系统

技术的改变会给当前的文件系统带来压力。
CPU 会变得越来越快，磁盘会变得越来越大并且越来越便宜（但不会越来越快）。内存容量也是以指数级增长。但是磁盘的寻道时间（除了固态盘，因为固态盘没有寻道时间）并没有获得提高。
解决问题
- 不断增长的系统内存
- 顺序 I/O 性能胜过随机 I/O 性能
- 现有低效率的文件系统
- 文件系统不支持 RAID（虚拟化）

移除文件
- 在目录中删除文件
- 释放 inode 到空闲 inode 池
- 将所有磁盘块归还给空闲磁盘池。
一般文件系统崩溃后必须运行 fsck（文件系统一致性检查）实用程序。
为了让日志能够正确工作，被写入的日志操作必须是幂等的(idempotent)
为了增加可靠性，一个文件系统可以引入数据库中原子事务(atomic transaction) 的概念。
一组动作可以被界定在开始事务和结束事务操作之间。这样，文件系统就会知道它必须完成所有的动作

# 4.3.9 虚拟文件系统

即使在同一台计算机上或者在同一个操作系统下，都会使用很多不同的文件系统。
Windows 中的主要文件系统是 NTFS 文件系统，但不是说 Windows 只有 NTFS 操作系统，它还有一些其他的例如旧的 FAT -32 或FAT -16 驱动器或分区
UNIX 把多种文件系统整合到一个统一的结构中。一个 Linux 系统可以使用 ext2 作为根文件系统，ext3 分区装载在 /usr 下，另一块采用 Reiser FS 文件系统的硬盘装载到 /home下，以及一个 ISO 9660 的 CD - ROM 临时装载到 /mnt 下。
UNIX 操作系统使用一种虚拟文件系统(Virtual File System, VFS) 来尝试将多种文件系统构成一个有序的结构。

# 4.5 文件系统的管理和优化

# 4.5.1 磁盘空间管理

配 n 个字节的连续磁盘空间；或者把文件拆分成多个并不一定连续的块。
在存储管理系统中，主要有分段管理和分页管理两种方式。
按连续字节序列存储文件
- 当文件扩大时，有可能需要在磁盘上移动文件
内存中分段
- 相对于把文件从磁盘的一个位置移动到另一个位置，内存中段的移动操作要快很多
因此几乎所有文件系统都是把文件分割成固定大小的块来进行存储

选用固定块大小的方式来存储属于是矮子里挑高个子，目前没有更好的方式来管理磁盘空间，其实用分段方式来处理任然会遇到按字节存储时遇到的问题。

# 4.5.2 块大小

按照磁盘组织方式，扇区、磁道和柱面显然都可以作为分配单位。
在分配块大小的时候要合理，如果分配的块太大会浪费空间；分配的块太小会浪费时间。

# 4.5.3 记录空闲块

空闲块的管理和内存管理用的方法一样，上面就是两种方式，a是用链表将空闲块相连接，b是用位图的方式来存放空闲块，具体的存放方式和内存管理中的相同。

如果空闲块是长期连续的话，那么空闲列表可以改成记录连续分块而不是单个的块。
- 第一个空闲块的地址和空闲块的计数
如果磁盘严重碎片化，那么跟踪连续分块要比跟踪单个分块运行效率低
空闲链表
只有一个指针块保存在内存中。创建文件时，所需要的块从指针块中取出。当它用完时，将从磁盘中读取一个新的指针块。类似地，删除文件时，文件的块将被释放并添加到主存中的指针块中。当块被填满时，写回磁盘。

如果空闲块长期闲置，而且这些空闲块是连续的，那么就可以把这些空闲块进行拼接，形成一个大的空闲块。

# 4.5.4 磁盘配额

在多用户操作中，为了防止一些用户占用太多的磁盘空间，多用户操作通常提供一种磁盘配额(enforcing disk quotas)的机制。
系统管理员为每个用户分配最大的文件和块分配，并且操作系统确保用户不会超过其配额。
当一个用户尝试登陆，系统将检查配额文件以查看用户是否超出了文件数量或磁盘块数量的软限制。如果违反了任一限制，则会显示警告，保存的警告计数减 1，如果警告计数为 0 ，表示用户多次忽略该警告，因而将不允许该用户登录。要想再得到登录的许可，就必须与系统管理员协商。

配额表中两个属性比较难以理解，一个是软块限制，另一个是硬块限制。其实这两个都是用来表示这个分配的文件的上线，只是软块限制不是真真意义上的分配的文件的最大值，这个软块限制是给进程看的，若是用户多次突破这个软块限制，那么操作系统会直接将这个用户踢除。而硬块限制就是真正意义上的文件大小的最大值，被硬件给限定死了。

# 4.5.5 文件系统备份

文件系统的毁坏要比计算机的损坏严重很多。无论是硬件还是软件的故障，只要计算机文件系统被破坏，要恢复起来都是及其困难的，甚至是不可能的。
磁带备份主要要处理的问题
- 从意外的灾难中恢复
- 从错误的操作中恢复
备份引发的问题
- 是要备份整个文件还是仅备份一部分呢
- 对上次未修改过的文件再进行备份是一种浪费
- 待转储的往往是海量数据，那么在将其写入磁带之前对文件进行压缩就很有必要
- 对正在使用的文件系统做备份是很难的

# 4.5.6 物理转储

从磁盘的 0 块开始，依次将所有磁盘块按照顺序写入到输出磁盘，并在复制最后一个磁盘时停止。这种程序的万无一失性是其他程序所不具备的。
优点
- 简单
- 极为快速（基本上是以磁盘的速度运行）
缺点
- 全量备份
- 不能跳过指定目录，也不能增量转储，也不能恢复个人文件的请求
大多数情况下不会使用物理转储，而使用逻辑转储

# 4.5.7 逻辑转储

从一个或几个指定的目录开始，递归转储自指定日期开始后更改的文件和目录。

逻辑转储算法的执行分成四个阶段

第一阶段从起始目录（本例为根目录）开始检查其中所有的目录项。对每一个修改过的文件，该算法将在位图中标记其 inode。
再次递归遍历目录树，并去掉目录树中任何不包含被修改过的文件或目录的标记。
以节点号为序，扫描这些 inode 并转储所有标记为需转储的目录
在第四阶段，上图中被标记的文件也被转储

# 4.5.8 文件系统一致性

文件系统的一致性是影响可靠性的一个因素。
为了处理文件系统一致性问题，大部分计算机都会有应用程序来检查文件系统的一致性。例如，UNIX 有 fsck；Windows 有 sfc，每当引导系统时（尤其是在崩溃后），都可以运行该程序。
检查
- 块的一致性检查
- 文件的一致性检查
检查一致性——两张表
- 第一个表中的计数器跟踪该块在文件中出现的次数
- 第二张表中的计数器记录每个块在空闲列表、空闲位图中出现的频率

# 4.5.9 文件系统检验程序

除了检查每个磁盘块计数的正确性之外，文件系统还会检查目录系统。
这时候会用到一张计数器表，但这时是一个文件（而不是一个块）对应于一个计数器。程序从根目录开始检验，沿着目录树向下查找，检查文件系统的每个目录。
在检验程序完成后，会得到一张由 inode 索引的表，说明每个文件和目录的包含关系。
问题
- 如果 inode 节点的链接计数大户目录项个数，这时即使所有文件从目录中删除，这个计数仍然不是 0 ，inode 不会被删除。这种错误不严重，却因为存在不属于任何目录的文件而浪费了磁盘空间。
- 如果同一个文件链接两个目录项，但是 inode 链接计数只为 1，如果删除了任何一个目录项，对应 inode 链接计数变为 0。

# 4.6 文件系统的优化

# 4.6.1 硬件层面的优化

通过分层的结构来进行存储，平衡了性价比。采用哈希存储的方式，访问更加快速。

# 4.6.2 块提前读

许多文件都是顺序读取。如果请求文件系统在某个文件中生成块 k，文件系统执行相关操作并且在完成之后，会检查高速缓存，以便确定块 k + 1 是否已经在高速缓存。如果不在，文件系统会为 k + 1 安排一个预读取，因为文件希望在用到该块的时候能够直接从高速缓存中读取。

# 4.6.3 减少磁盘转动

把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘的转动次数。

# 4.6.4 磁盘碎片整理

移动文件使它们相互挨着，并把所有的至少是大部分的空闲空间放在一个或多个大的连续区域内。Windows 有一个程序 defrag 就是做这个事儿的。Windows 用户会经常使用它，SSD 除外。

# 第五章操作系统之输入输出

# 5.1 I/O设备

I/O 设备又叫做输入/输出设备，它是人类用来和计算机进行通信的外部硬件。
输入/输出设备能够向计算机发送数据（输出）并从计算机接收数据（输入）。
I/O 设备(I/O devices)可以分成两种：
- 块设备(block devices)
- 字符设备(character devices)

# 5.1.1 块设备

块设备是一个能存储固定大小块信息的设备，它支持以固定大小的块，扇区或群集读取和（可选）写入数据。
每个块都有自己的物理地址。通常块的大小在 512 - 65536 之间。
常见的块设备有硬盘、蓝光光盘、USB 盘
缺点：
- 基于给定固态存储器的块设备比基于相同类型的存储器的字节寻址要慢一些，因为必须在块的开头开始读取或写入。

# 5.1.2 字符设备

字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。
字符设备是不可寻址的，也没有任何寻道操作。
常见的字符设备有打印机、网络设备、鼠标、以及大多数与磁盘不同的设备

# 5.1.3 设备控制器

设备控制器是处理 CPU 传入和传出信号的系统
设备通过插头和插座连接到计算机，并且插座连接到设备控制器。设备控制器从连接的设备处接收数据，并将其存储在控制器内部的一些特殊目的寄存器(special purpose registers) 。
每个设备控制器都会有一个应用程序与之对应，设备控制器通过应用程序的接口通过中断与操作系统进行通信。
I/O 设备通常由机械组件(mechanical component)和电子组件(electronic component)构成
- 电子组件——PCIE
- 机械设备——设备本身

# 5.1.4 内存映射I/O

每个控制器都会有几个寄存器用来和 CPU 进行通信。
为了控制寄存器，许多设备都会有数据缓冲区(data buffer)，来供系统进行读写。
CPU 如何与设备寄存器和设备数据缓冲区进行通信呢？
每个控制寄存器都被分配一个 I/O 端口(I/O port)号，这是一个 8 位或 16 位的整数
PDP—11——所有控制寄存器映射到内存空间

以上是两种I/O端口存放的形式，第一种是将I/O端口放在内存空间中，这样就可以直接用C这种能取地址值的语言就行操作，现代计算机基本用的都是这样形式，而第二种则是单独拿一个地方来存放I/O端口，这样做只能用汇编才能进行对其的操作，这种形式一般用于现在的大型计算机，因为相比于第一种，第二种方式更为安全。

# 5.1.5 内存映射I/O的优点和缺点

优点
- 第一，如果需要特殊的 I/O 指令读写设备控制寄存器，那么访问这些寄存器需要使用汇编代码，因为在 C 或 C++ 中不存在执行 IN 和 OUT指令的方法。
- 第二，对于内存映射 I/O ，不需要特殊的保护机制就能够阻止用户进程执行 I/O 操作。
- 第三，对于内存映射 I/O，可以引用内存的每一条指令也可以引用控制寄存器，便于引用。
缺点
- 大部分计算机现在都会有一些对于内存字的缓存
- 如果仅仅只有一个地址空间，那么所有的内存模块(memory modules)和所有的 I/O 设备都必须检查所有的内存引用来推断出谁来进行响应。

# 5.1.6 直接内存访问

无论一个 CPU 是否具有内存映射 I/O，它都需要寻址设备控制器以便与它们交换数据。

CPU会以块的方式进行请求，通过DMA控制器发送请求给内存，然后内存去调数据，然后返给DMA控制器，DMA控制器中的计数器Count去加1，知道请求完所有块中的内容，然后中断CPU，将读取到的数据给CPU，这样做可以加快CPU的运行效率，让CPU不会疲于I/O等待。

# 5.1.7 中断

中断在前面的内容中已经多次体现了，I/O设备完成任务会对中断控制器发送请求，中断控制器会对CPU做出中断，然后CPU对中断做出反应。

那么这些中断信息保存在哪里呢

保存在寄存器当中

一段时间内设备无法响应，直到所有的内部寄存器中存储的信息被读出后，才能恢复运行

寄存器数量限制

保存在堆栈当中

转换内核态浪费CPU时间

精确中断和不精确中断

使机器处于良好状态的中断称为精确中断(precise interrupt)。这样的中断具有四个属性：
- PC （程序计数器）保存在一个已知的地方
- PC 所指向的指令之前所有的指令已经完全执行
- PC 所指向的指令之后所有的指令都没有执行
- PC 所指向的指令的执行状态是已知的
不满足以上要求的中断称为不精确中断(imprecise interrupt)，不精确中断让人很头疼

# 5.2 I/O软件原理

# 5.2.1 设备独立性

我们能够编写访问任何设备的应用程序，而不用事先指定特定的设备
计算机操作系统是这些硬件的媒介，因为不同硬件它们的指令序列不同，所以需要操作系统来做指令间的转换。
与设备独立性密切相关的一个指标就是统一命名(uniform naming)。
设备的代号应该是一个整数或者是字符串，它们不应该依赖于具体的设备。

设备独立性是十分必要的，试想一个鼠标或者键盘，连接到任意电脑上都能使用，这个就是设备独立性的体现。

# 5.2.2 错误处理

通常情况下来说，错误应该交给硬件层面去处理
如果设备控制器处理不了这个问题，那么设备驱动程序应该进行处理
如果设备驱动程序无法处理这个错误，才会把错误向上抛到硬件层面（上层）进行处理

一般情况下，错误都是交给硬件处理，然后一层层的上交处理，最后到达上层会直接报错。平时我们插入U盘无法读取就是这种情况，电脑会直接弹出无法读取。

# 5.2.3 同步和异步传输

同步传输
- 同步传输中数据通常以块或帧的形式发送。发送方和接收方在数据传输之前应该具有同步时钟。
异步传输
- 异步传输中，数据通常以字节或者字符的形式发送，异步传输则不需要同步时钟，但是会在传输之前向数据添加奇偶校验位。

同步体现在网络中，也就是客户端发送请求，然后等待服务器响应，若是没有收到响应，则超时重传，这个超时的时间由同步时钟来规定。

异步常用于CPU中，异步要用到中断。也就是发出命令后，转头去做其他的事情。当发出的命令完成后，中断，对完成的命令做出回应。

# 5.2.4 缓冲

通常情况下，从一个设备发出的数据不会直接到达最后的设备。其间会经过一系列的校验、检查、缓冲等操作才能到达。

# 5.2.5 共享和独占

有些 I/O 设备能够被许多用户共同使用。一些设备比如磁盘，让多个用户使用一般不会产生什么问题，但是某些设备必须具有独占性，即只允许单个用户使用完成后才能让其他用户使用。

# 5.3 I/O层次结构

# 5.3.1 中断处理程序

中断处理程序负责处理中断发生时的所有操作，操作完成后阻塞，然后启动中断驱动程序来解决阻塞
如何通知
- 信号量实现中：在信号量上使用 up 进行通知
- 管程实现：对管程中的条件变量执行 signal 操作
- 发送一些消息

中断处理方案

非嵌套的中断处理程序按照顺序处理各个中断，非嵌套的中断处理程序也是最简单的中断处理
嵌套的中断处理程序会处理多个中断而无需分配优先级
可重入的中断处理程序可使用优先级处理多个中断
简单优先级中断处理程序可处理简单的中断
标准优先级中断处理程序比低优先级的中断处理程序在更短的时间能够处理优先级更高的中断
高优先级中断处理程序在短时间能够处理优先级更高的任务，并直接进入特定的服务例程。
优先级分组中断处理程序能够处理不同优先级的中断任务

其他比较好理解，注释一下嵌套的中断，简单点来说就是中断中有中断，来一个中断就执行一个中断。

通用的中断处理程序的步骤

保存所有没有被中断硬件保存的寄存器
为中断服务程序设置上下文环境，可能包括设置 TLB、MMU 和页表
为中断服务程序设置栈
对中断控制器作出响应，如果不存在集中的中断控制器，则继续响应中断
把寄存器从保存它的地方拷贝到进程表中
运行中断服务程序，它会从发出中断的设备控制器的寄存器中提取信息
操作系统会选择一个合适的进程来运行。如果中断造成了一些优先级更高的进程变为就绪态，则选择运行这些优先级高的进程
为进程设置 MMU 上下文，可能也会需要 TLB，根据实际情况决定
加载进程的寄存器，包括 PSW 寄存器
开始运行新的进程

# 5.3.2 设备驱动程序

这些提供 I/O 设备到设备控制器转换的过程的代码称为设备驱动程序(Device driver)。
设备驱动程序通常是操作系统内核的一部分
还有一种方案是构造用户空间的设备驱动程序

驱动装载

在 UNIX 系统中，操作系统是一个二进制程序，包含需要编译到其内部的所有驱动程序，如果你要对 UNIX 添加一个新设备，需要重新编译内核，将新的驱动程序装到二进制程序中
然而随着大多数个人计算机的出现，由于 I/O 设备的广泛应用，上面这种静态编译的方式不再有效，因此，从 MS-DOS 开始，操作系统转向驱动程序在执行期间动态的装载到系统中。

驱动功能

设备驱动程序具有很多功能，比如接受读写请求，对设备进行初始化、管理电源和日志、对输入参数进行有效性检查等。
控制设备就是对设备发出指令。
发出命令后，设备控制器便开始将它们写入控制器的设备寄存器。在将每个命令写入控制器后，会检查控制器是否接受了这条命令并准备接受下一个命令。
一般控制设备会发出一系列的指令，这称为指令序列，设备控制器会依次检查每个命令是否被接受，下一条指令是否能够被接收，直到所有的序列发出为止。

# 5.3.3 设备控制器

在大多数情况下，设备驱动程序会进行等待直到控制器完成它的事情。
设备控制器
- 设备控制器的主要主责是控制一个或多个 I/O 设备，以实现 I/O 设备和计算机之间的数据交换。
- 设备控制器接收从 CPU 发送过来的指令，继而达到控制硬件的目的
主要功能
- 接收和识别命令：设备控制器可以接受来自 CPU 的指令，并进行识别。设备控制器内部也会有寄存器，用来存放指令和参数
- 进行数据交换：CPU、控制器和设备之间会进行数据的交换，CPU 通过总线把指令发送给控制器，或从控制器中并行地读出数据；控制器将数据写入指定设备。
- 地址识别：每个硬件设备都有自己的地址，设备控制器能够识别这些不同的地址，来达到控制硬件的目的，此外，为使 CPU 能向寄存器中写入或者读取数据，这些寄存器都应具有唯一的地址。
- 差错检测：设备控制器还具有对设备传递过来的数据进行检测的功能。

# 5.3.4 与设备无关的 I/O软件

I/O 软件有两种，一种是我们上面介绍过的基于特定设备的，还有一种是设备无关性的，设备无关性也就是不需要特定的设备。
设备驱动程序与设备无关的软件之间的界限取决于具体的系统。
与设备无关的软件的基本功能是对所有设备执行公共的 I/O 功能，并且向用户层软件提供一个统一的接口。
功能
- 缓冲
- 错误报告
- 设备驱动程序统一接口
- 分配和释放特定的设备
- 提供和设备无关的块大小

# 5.3.5 缓冲

无论是对于块设备还是字符设备来说，缓冲都是一个非常重要的考量标准。

这里一般来说在内核空间中也会加入一个缓冲模块，然后会先缓冲到内核空间，然后当这个缓冲块满了就让用户空间拿一个块来，然后复制到用户空间，接着继续装缓存。

# 5.3.6 用户空间的 I/O 软件

虽然大部分 I/O 软件都在内核结构中，但是还有一些在用户空间实现的 I/O 软件，凡事没有绝对。一些 I/O 软件和库过程在用户空间存在，然后以提供系统调用的方式实现。

在一些嵌入式结构中会在用户空间来实现，我们现在计算机基本都在内核中，毕竟现在的内核做的都很大。

# 5.3.7 磁盘臂调度算法

先来先服务（FCFS, First Come First Served）

算法描述：按照请求到达的顺序进行磁盘调度，即哪个请求先到，就先处理哪个请求。
优点：简单易实现。
缺点：可能出现"长寻道时间"的问题，比如，如果先处理最远的请求，会导致接下来的请求需要花费更多的寻道时间。
示例：假设磁头当前位置在 50，且接收到的请求序列是 98、183、37、122、14、124、65、67。处理顺序：50 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

最短寻道时间优先（SSTF, Shortest Seek Time First）

算法描述：优先处理离磁头最近的磁盘请求，减少磁头移动的距离，选择当前最近的磁道。
优点：可以减少磁头的寻道时间，提高 I/O 效率。
缺点：存在"饥饿问题"，如果总有离磁头更近的请求，远处的请求可能会长期得不到处理。
示例：磁头当前位置 50，接收到的请求是 98、183、37、122、14、124、65、67。处理顺序：50 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183

扫描算法（SCAN，也叫电梯调度算法）

算法描述：磁头像电梯一样在磁盘上来回移动，先一个方向逐步处理磁盘请求，直到到达某一端后再反向处理请求。在某个方向上，优先处理该方向上的请求。
优点：减少了磁头反复的来回寻道，提高了整体性能。
缺点：仍然存在"饥饿问题"，离磁头较远但在当前方向的请求可能长期得不到处理。
示例：磁头当前位置 50，接收到的请求是 98、183、37、122、14、124、65、67，假设磁头当前向上移动（增加磁道号）。处理顺序：50 → 65 → 67 → 98 → 122 → 124 → 183，然后反转方向，处理 37 → 14。

循环扫描算法（C-SCAN，Circular SCAN）

算法描述：类似于 SCAN，但只在一个方向上扫描磁盘。当磁头到达磁盘的一端时，不进行反向处理，而是回到磁盘另一端的起点，再继续同一方向的扫描。
优点：可以保证所有请求的平均等待时间更平衡，不会因为在两端来回而有偏向。
缺点：回到起点需要额外的移动，但通常这种算法可以减少等待时间的不公平现象。
示例：磁头当前位置 50，接收到的请求是 98、183、37、122、14、124、65、67，假设磁头当前向上移动。处理顺序：50 → 65 → 67 → 98 → 122 → 124 → 183，然后回到磁盘起点，再处理 14 → 37。

# 5.3.8 错误处理

磁盘在制造的过程中可能会有瑕疵，如果瑕疵比较小，比如只有几位，那么使用坏扇区并且每次只是让 ECC 纠正错误是可行的，如果瑕疵较大，那么错误就不可能被掩盖。
两种处理办法
- 一种是在控制器中进行处理
- 一种是在操作系统层面进行处理
- 两种方法交替使用

两种方法，一种就是当扇区坏了，拿一个好的扇区将其替代。另一种方法是将扇区5向后移动，扇区5原来的位置变成扇区4。

# 5.4 时钟

时钟(Clocks) 也被称为定时器(timers)
时钟软件(clock software) 也是一种设备驱动的方式

# 5.4.1 时钟硬件

在计算机中有两种类型的时钟，这些时钟与现实生活中使用的时钟完全不一样。
- 比较简单的一种时钟被连接到 110 V 或 220 V 的电源线上，这样每个电压周期会产生一个中断，大概是 50 - 60 HZ。这些时钟过去一直占据支配地位。
- 另外的一种时钟由晶体振荡器、计数器和寄存器组成

# 5.4.2 时钟软件

维护一天的时间
阻止进程运行的时间超过其指定时间
统计 CPU 的使用情况
处理用户进程的警告系统调用
为系统各个部分提供看门狗定时器
完成概要剖析，监视和信息收集

# 5.4.3 软定时器

时钟软件也被称为可编程时钟，可以设置它以程序需要的任何速率引发中断。
避免了频繁的内核态和用户态之前的切换，提高了程序运行效率
软定时器因为不同的原因切换进入内核态的速率不同
- 系统调用
- TLB 未命中
- 缺页异常
- I/O 中断
- CPU 变得空闲

# 第六章操作系统之死锁

# 6.1 资源和资源的获取

资源

需要排他性使用的对象称为资源(resource)。
可抢占资源
- 从拥有它的进程中抢占而不会造成其他影响
不可抢占资源
- 除非引起错误或者异常，否则进程无法抢占指定资源
死锁一般与不可抢占资源有关
基本步骤：请求、使用、释放

资源获取

对于一些数据库系统中的记录这类资源来说，应该由用户进程来对其进行管理
- 信号量
- 互斥锁

信号量和互斥锁在前面以及提到了，这里再重复一下。

信号量

互斥锁

# 6.2 死锁的概念

如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况会导致死锁
资源死锁
- 死锁进程集合中的每个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都不能运行，它们之中任何一个资源都无法释放资源，所以没有一个进程可以被唤醒。
- 资源死锁是最常见的类型

# 6.3 资源死锁的条件

互斥条件：每个资源都被分配给了一个进程或者资源是可用的
保持和等待条件：已经获取资源的进程被认为能够获取新的资源
不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。

# 6.4 避免死锁（银行家算法）

银行家算法的工作原理

银行家算法通过以下步骤来避免死锁：

系统数据结构：
- Available：表示当前系统中各类资源的可用数量。
- Max：每个进程对各类资源的最大需求。
- Allocation：当前已分配给每个进程的各类资源数量。
- Need：每个进程仍需的资源数量，等于 Max - Allocation。
安全性检查：系统通过一个安全性算法来判断在进行资源分配后，系统是否能够处于安全状态。
- 安全状态：存在一个进程执行顺序，可以让所有进程在有限时间内顺利完成，并释放所有资源。
- 不安全状态：可能会导致某些进程无法执行，可能进入死锁。
银行家算法的流程：
1. 当某个进程 P 请求一组资源时，系统首先检查请求量是否小于等于 Need 和 Available。如果超出 Need 或 Available，直接拒绝。
2. 系统试探性地分配资源给进程 P，即更新 Available 和 Allocation，然后调用安全性算法来判断此时系统是否处于安全状态。
3. 如果分配后系统处于安全状态，则真正进行资源分配。
4. 如果分配后系统处于不安全状态，则取消分配，进程 P的请求被拒绝。

示例

假设系统有3类资源 (A, B, C)，初始状态下系统的资源数量是：

资源类型	可用资源数 (Available)
A	10
B	5
C	7

有5个进程 (P0, P1, P2, P3, P4)，它们的最大需求 (Max)、已分配资源 (Allocation) 和需要的资源 (Need) 如下：

进程	Max (A, B, C)	Allocation (A, B, C)	Need (A, B, C)
P0	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
P1	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
P2	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
P3	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
P4	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)

系统当前的 Available 资源为 (3, 3, 2)。

步骤：

假设 P1 进程请求 (1, 0, 2) 资源。
系统先检查 P1 的请求是否满足 Need 和 Available

条件：
- 请求 (1, 0, 2) 小于等于 P1 的 Need(1, 2, 2) 和 Available(3, 3, 2)，所以可以继续。
系统试探性分配资源，更新数据：
- Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
- Allocation(P1) = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
- Need(P1) = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)
系统调用安全性算法，检查是否能够进入安全状态：
- 系统找出可完成的进程，并验证资源回收后是否可以继续满足其他进程的需求。
- 如果找到了安全序列，分配成功，否则恢复原状，拒绝请求。

# 6.5 处理死锁的几种策略

忽略影响（鸵鸟算法）
检测死锁并回复死锁，死锁发生时对其进行检测，一旦发生死锁后，采取行动解决问题
通过仔细分配资源来避免死锁
通过破坏死锁产生的四个条件之一来避免死锁

# 6.5.1 鸵鸟算法

鸵鸟算法虽然看上去不靠谱，但是在很多情况下很好用，比如在硬件层面，电脑的主板损坏，很少有人会拿焊接器来修主板，一般都是直接买一块新的主板，这种方法就是鸵鸟思想的体现。在操作系统中，有些影响不大的死锁也可以用鸵鸟算法来处理

# 6.5.2 死锁的检测和恢复

检测

每隔 k 分钟检测一次，或者当 CPU 使用率降低到某个标准下去检测。检测的方法通常基于资源分配图或检测算法

恢复

通过抢占进行恢复
- 在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。
通过回滚进行恢复
- 如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。
杀死进程恢复
- 最简单有效的解决方案是直接杀死一个死锁进程

# 6.5.3 死锁避免

死锁避免依赖于安全状态的概念。系统在分配资源之前会检查，分配后系统是否会进入安全状态。如果系统保持安全状态，则进行资源分配；否则，拒绝该请求，避免进入死锁。上述说的银行家算法就是其中的一张算法。

# 6.5.4 破坏死锁

死锁本质上是无法避免的，因为它需要获得未知的资源和请求
但是死锁的出现满足四个条件
- 互斥
  - 如果资源不被一个进程独占，那么死锁肯定不会产生。
  - 如果两个打印机同时使用一个资源会造成混乱，打印机的解决方式是使用假脱机打印机(spooling printer)
- 保持和等待
  - 如果我们能阻止持有资源的进程请求其他资源，我们就能够消除死锁。
    - 让所有的进程开始执行前请求全部的资源。如果所需的资源可用，进程会完成资源的分配并运行到结束。
    - 进程在请求其他资源时，先释放所占用的资源，然后再尝试一次获取全部的资源。
- 不可抢占
  - 通过虚拟化破坏不可抢占条件
- 循环等待
  - 一种方式是制定一个标准，一个进程在任何时候只能使用一种资源。如果需要另外一种资源，必须释放当前资源。
    - 对于需要将大文件从磁带复制到打印机的过程，此限制是不可接受的。
  - 是将所有的资源统一编号

# 6.6 关于死锁的其他问题

两阶段加锁
- 如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受
通信死锁
- 两个或多个进程在发送消息时出现的死锁。
- 通信死锁不能通过调度的方式来避免，但是可以使用通信中一个非常重要的概念来避免：超时(timeout)
- 并非所有网络通信发生的死锁都是通信死锁，也存在资源死锁
活锁
- 某些情况下，当进程意识到它不能获取所需要的下一个锁时，就会尝试礼貌的释放已经获得的锁，然后等待非常短的时间再次尝试获取。
饥饿
- 一个进程想要获取的资源一直被优先级高的进程获取。

解释一下通信死锁中的资源死锁以及活锁。

资源死锁

比如有A、B、C三方。A->B、B->C、C->A，三方分别向各自的指定方发送消息，但是由于三方的缓冲区都满了，所以并不能发送出去，所以会造成资源死锁

活锁

活锁和死锁刚好对应。可以想象一个场景。两辆车想要过一条只能通过一辆车的小路，双方互相礼让对方通行，那么一直礼让下去就会发生活锁，两量车都会无法通过这条小路，折射到进程中也相同，两个进程都想让一个资源然后互相礼让，如若这两个进程的定时器刚好相同，那么这两个进程将一直拿不到这个资源

blog

操作系统

操作系统

# 第一章 操作系统总览

# 第二章 操作系统之进程和线程

# 2.1 进程

# 2.1.1 进程的创建

# 2.1.2 进程的终止

# 2.1.3 进程的层次结构和状态

# 2.2 线程

# 2.2.1 线程的使用

# 2.2.2 经典的线程模型

# 2.2.3 线程的系统调用

# 2.2.4 POSIX编程

# 2.2.5 线程实现

# 2.3 进程间通信

# 2.3.1 竞态条件

# 2.3.2 临界区

# 2.3.3 忙等互斥

# 2.4 生产者-消费者问题

# 2.5 管程

# 2.6 消息传递

# 2.7 避免锁

# 2.8 调度的介绍

# 2.9 计算机上执行任务的两种策略

# 2.10 调度时机

# 2.11 调度算法的分类

# 2.12 调度系统的环境

# 2.12.1 批处理中的调度

# 2.12.2 交互式中的调度

# 2.12.3 实时系统中的事件的分类

# 第三章 操作系统之内存管理

# 3.1 实现并行性

# 3.2 物理内存暴露的缺点

# 3.3 地址空间

# 3.4 交换技术

# 3.5 内存增长处理方式

# 3.6 空闲内存的管理

# 3.7 虚拟内存

# 3.8 分页技术

# 3.9 存在映射的页的映射

# 3.10 针对大内存的页表

# 3.11 页面置换算法

# 3.11.1 最优页面置换算法

# 3.11.2 最近未使用页面算法（NRU）

# 3.11.3 先进先出置换算法（FIFO）

# 3.11.4 第二次机会页面置换算法（SC）

# 3.11.5 时钟页面置换算法（CLOCK）

# 3.11.6 最近最少使用页面置换算法（LRU）

# 3.11.7 工作集置换算法

# 3.11.8 工作集时钟页面置换算法

# 第四章 操作系统之文件系统

# 4.1 文件

# 4.1.1 文件命名

# 4.1.2 文件结构

# 4.1.3 文件类型

# 4.1.4 文件访问

# 4.1.5 文件属性

# 4.1.6 文件操作

# 4.2 目录

# 4.2.1 一级目录系统

# 4.2.2 层次目录系统

# 4.2.3 路径名

# 4.2.4 目录操作

# 4.3 文件系统的实现

# 4.3.1 文件系统的布局

# 4.3.2 引导块

# 4.3.3 超级块

# 4.3.4 空闲空间快

# 4.3.4 碎片

# 4.3.5 inode

# 4.3.6 文件的实现

# 4.3.7 共享文件

# 4.3.8 日志结构文件系统

# 4.3.9 虚拟文件系统

# 4.5 文件系统的管理和优化

# 4.5.1 磁盘空间管理

# 4.5.2 块大小

# 4.5.3 记录空闲块

# 4.5.4 磁盘配额

# 第一章操作系统总览

# 第二章操作系统之进程和线程

# 第三章操作系统之内存管理

# 第四章操作系统之文件系统

# 第五章操作系统之输入输出

# 第六章操作系统之死锁