概述

操作系统的功能

• CPU管理：进程/线程管理。进程/线程状态、控制、同步互斥、通信、调度…
• 存储管理。分配/回收、地址管理、存储保护、内存扩充…
• 文件管理。文件目录、文件操作、磁盘空间、文件存取控制…
• 设备管理。设备驱动、分配回收、缓冲技术…
• 用户接口。系统命令、编程接口…

OS是硬件上的第一层软件

• 例如读取文件：“从某个文件读一个数据块” or “移动磁头，等待放下”
• OS 在应用程序578和硬件之间建立一个“虚拟机”
• 对硬件抽象、提高程序可移植性

OS的特征

• 并发（concurrency），能处理同时的活动。
  • 这些活动之间有依赖关系，需要解决同步等问题。
  • 宏观上看，程序在同步执行。微观上看，程序在CPU上轮流执行
• 共享（sharing），
  • 互斥共享（打印机）/同时共享（磁盘文件）
• 虚拟（virtual）
  • 一个物理实体，映射为若干逻辑实体
  • 提高资源利用率
  • 例如：CPU–进程，存储器–每个进程有独立的虚拟地址空间，显示设备–多窗口/虚拟终端
• 随机。处理不可预测的次序发生的事件
  • 多个进程的运行速度不可预知

操作系统的分类（还有别的分类方法，这里只写一种）

1. 批处理操作系统。用户把作业交给系统操作员，操作员把作业输入到计算机系统，计算机批量处理。
   • 用户用卫星机把作业放入“输入井”，主机读取“输入井”，处理后把结果放入“输出井”，用户从“输出井”获取处理结果
2. 分时操作系统：CPU分成片段，轮流供每个用户使用，使用户感觉自己在连续使用。
3. 实时操作系统：要求计算机立即响应外部请求，并在严格时间内完成处理，高可靠性。
   • 工业控制、航空、军事
   • 实时通信（信息）处理
   • 硬实时系统：要求必须在规定时间内完成。
   • 软实时系统：偶尔可以违反时限。例如播放器。
4. 个人计算机操作系统：界面友好、使用方便、应用丰富。
5. 网络操作系统。按网络体系结构协议标准开发的软件。
   • 网络管理、通信、安全、资源共享、各种网络应用
6. 分布式操作系统。是一个统一的操作系统，若干台计算机共同完成任务。
7. 嵌入式操作系统。各种设备，例如汽车、手机、电视机。

系统调用：操作系统给应用程序的接口

• 允许应用程序执行一些操作/服务（例如文件操作、进程管理、内存分配、设备管理）
• 过程中从用户态切换到内核态（叫做陷入 trap）

中断和异常

• 中断由外部设备和事件引起的
• 异常是由正在执行的程序内部产生的错误或特殊情况引起的
• 都对应从 用户态 切换到 内核态度

进程/线程

多道程序设计：允许多个程序同时进入内存并运行。目的是提高系统效率。

• 每个程序都有自己的逻辑程序计数器
• 哪个运行，就把哪个放入物理计数器
• 每个程序轮流执行，并发执行

并发环境：

• 单个处理器上的程序，同时 处于开始运行但尚未结束的状态
• 并且次序不是事先确定的

进程（Process）：有独立功能的程序关于某个数据集合上的一次运行活动

• 又称任务（Task、Job）
• 是对 CPU 的抽象。
• 是把一个 CPU 抽象为 多个虚拟的CPU
• 一单位为分配，如内存、文件
  • 每个都有独立的地址空间。意味着每个进程的地址空间是逻辑地址，而不是物理地址。
• 操作系统把 CPU 调度给需要的进程

PCB（Process Control Block，进程描述符，进程属性）

• 一个专门数据结构，记录进程的各种属性、描述进程的动态变化过程
• 进程与 PCB 是一一对应的
• 所有 PCB 集合叫做 进程表
  • 进程表的大小限制了操作系统可以同时开多少个进程
• PCB 记录了哪些信息？
  • 进程描述信息
    • 进程标识符 process ID，唯一、整数
    • 进程名，通常基于可执行文件名
    • 用户标识符 user ID
    • 进程组关系
  • 进程控制信息
    • 当前状态
    • 优先级 priority
    • 代码执行入口地址
    • 程序的磁盘地址
    • 运行统计信息（执行时间、页面调度）
    • 进程间同步和通信
    • 进程的队列指针
    • 进程的消息队列指针
  • 进程拥有的资源和使用情况
    • 虚拟地址文件状况
    • 打开文件列表
  • CPU 现场信息。进程不运行状态下保存的信息。
    • 寄存器值（通用机孙琦、PC、状态字PSW、栈指针）
    • 指向进程页表的指针
• 在不同的操作系统下是不一样的。Linux：task_struct, Windows：EPROCESS,KPROCESS,PEB

进程状态（基础状态）

• 运行态（Running），占有 CPU，并在 CPU 运行
• 就绪态（Ready），已经具备运行条件，但没有空闲 CPU
• 等待态（Waiting/Blocked、阻塞态、封锁态、睡眠态），等待某个事件而暂时不能运行。例如等待读磁盘。

进程的其他状态

• 创建态（New），已经完成创建的必要工作（PID，PCB），但是尚未同意执行该进程（例如资源有限）
• 终止态（Terminated）。
  • 终止执行
  • 可完成一些数据统计工作（资源使用量等）
  • 资源回收
• 挂起态（suspend）
  • 用于负载调节
  • 进程的内存会被回收，进程印象道磁盘上。
  • 资源足够后会重新激活

除此之外，还有类似的七状态模型

Linux 的进程态:

进程队列。进程状态的改变，实际上是 PCB 从一个队列出列，进入另一个队列的过程

• 例如，就绪态可能有多个队列

进程控制

进程控制操作完成进程之间的转换，由 原语（primitive） 完成。（原语一种原子操作，不可分割、不可中断）

进程的创建

• 分配一个唯一标识，进程控制块
• 分配地址空间
• 初始化进程控制块
• 设置相应的队列指针。
  • 例如新进程加入到就绪队列链表中。
• unix：fork, exec。Windows：CreateProcess

进程的撤销（结束进程）

• 资源回收：关闭打开的文件、断开网络链接、回收分配的内存
• 撤销进程的 PCB
• unix:exit，windows：TerminateProcess

进程的阻塞

• 进程自己执行阻塞原语
• unix：wait，windows：WaitForSingleObject

unix 几个进程控制函数

• fork() 复制调用进程来建立新的进程。最基本的进程建立过程。
• exec() 用新的程序代码覆盖原来的地址空间，实现进程执行代码的转换
• wait() 初级进程同步操作，使一个进程等待另一个进程的结束
• exit() 终止一个进程的运行

fork() 的实现

• 为子进程分配一个空闲的进程描述符（proc 结构）
• 为子进程分配 pid
• 一次一页的方式复制父进程地址空间
  • 子进程的代码一般与父进程不同，这一步就造成浪费。Linux 采用 Copy-On-Write 技术来解决
    • 不复制父进程地址空间，而是用一个指针指向它，然后设定为只读。
    • 如果需要写入它，就开辟一个新的空间来写入
• 从父进程继承共享资源（如，打开的文件、当前工作目录）
• 把子进程状态设为就绪，插入到就绪队列
• 对子进程返回标识符 0
• 向父进程返回子进程的 pid

fork() 的使用

伪代码：

pid = fork(); // 创建一个子进程
if(pid<0){
    fprintf("出错");
    exit(-1);
}
else if(pid == 0){ 
    // 因为子进程会把父进程的一页复制进来
    fprintf("pid = 0 说明正在运行的是子进程");
    exec("xxx") // 调用 exec，用新代码覆盖子进程的地址空间
}
else {
    fprintf("pid>0 ，指的是子进程的 pid，并且正在运行的是父进程");
    wait(NULL); // 父进程等待子进程结束
    exit(0);
}

进程相关概念

分类1:

• 系统进程（优先级较高）
• 用户进程

分类2:

• 前台进程。与用户直接交互的，例如鼠标键盘
• 后台进程。打印、防火墙、电子邮件接收等

分类3:

• CPU密集型进程
• IO密集型进程

进程的层次结构

• unix：进程树。init 为根。父进程结束，子进程也必须结束。
• Windows：地位相同。虽然也是由进程建立另一个进程，但是未必一个结束另一个也结束。

进程与程序：一个程序可以对应多个进程。

进程有自己的地址空间（逻辑地址，而不是物理地址）

进程映像（IMAGE）

• 由进程地址空间内容、硬件寄存器、进程相关的内核数据结构、内核栈组成
• 相当于一个快照

上下文切换（Context Swith）

• CPU 硬件从一个进程切换到另一个进程的过程
• 进程不运行时，寄存器值保存在 PCB 中；切换到某个进程时，从对应的 PCB 中把值送回寄存器

线程

为什么需要多线程？

• 例如一个编辑器，需要同时处理：键盘输入、自动排版、定时保存。
• 一个Web服务器，需要同时接受网页请求、从磁盘检索网页、读入内存、把结果返回给客户端。

其它方案都有缺点：

• 如果使用单个进程，顺序编程，性能低
• 如果使用多进程，就不能使用共享的内存空间了
• 如果使用有限状态机方法（就是用一些编程手段来模拟多进程），例如非阻塞IO，编程会非常复杂

多线程的好处2:开销小

• 进程涉及到进程创建、进程撤销、进程通信、进程切换，时间和空间开销大
• 线程开销小：
  • 创建和撤销花费时间少
  • 线程切换花费时间少
  • 线程间通信无须调用内核，同一个进程的线程共享内存和文件

线程的好处3:多个处理器，可以充分发挥优势

线程是什么？

• 进程有两个属性：资源拥有者、CPU调度单位
• 线程只继承一个属性：CPU调度单位。（因此有时候把线程称为 轻量级进程）

线程的属性

• 标识符 ID
• 状态、状态转换
• 不运行时需要保存的上下文（例如PC寄存器）
• 线程有自己的栈和栈指针
• 共享所在进程的地址空间和其它资源
• 线程可以创建、撤销另一个线程

线程的实现

用户级线程

• Run-time system 完成线程的管理工作
• 内核管理的还是进程，不知道线程的存在
• 线程切换不需要内核态特权
• 例子：UNIX，遵守 POSIX 规范
• 优点：
  • 线程切换快
  • 调度算法是应用程序特定的
  • 可以运行在任何操作系统上（只需实现线程库）
• 缺点：
  • 内核把处理器分配给进程。同一个进程的两个线程不能同时运行在两个处理器上
  • 大多数系统调用时阻塞的。因此内核阻塞时，进程中所有线程也被阻塞

核心级线程

• 内核管理所有的线程
• 内核既维护进程，也维护线程
• 线程的切换需要内核支持
• 以线程为基础进行调用
• 例子：Windows

混合模型

• 线程的创建在用户空间完成
• 线程调度在核心态完成
• 例子：Solaris

协程：比线程更加轻量级。用户态。资源消耗更小。

• 计算密集型任务：
  • 多线程：适用于支持真正多线程的编程语言（如C++、Java、Go），能够高效利用多核CPU，实现并行计算。
  • 多进程：适用于存在全局解释器锁（如Python）或需要高隔离性的应用，能够绕过GIL，实现真正的并行。
  • 协程：不推荐单独使用，因其无法充分利用多核并行计算能力。
• I/O密集型任务：
  • 协程：非常适合高并发、I/O密集型任务，通过高效的任务切换和低开销实现高并发。
  • 多线程和多进程： 也可用于I/O密集型任务，但协程在资源利用和性能上更具优势。

通过综合考虑任务类型、编程语言特性和系统架构需求，选择最合适的并发模型能够显著提升系统性能和开发效率。

CPU调度

CPU调度：从就绪队列中选择一个进程，把 CPU 使用权交给它。

• N个进程就绪状态
• M个CPU空闲状态
• 需要决策：给哪个进程分配哪个CPU

需要解决3个问题：

• When：调度时机
• What：调度算法，调度哪个
• How：如何调度（进程的上下文切换）

调度时机：就绪队列改变。具体来说，有4个情况：

• 进程正常终止、由于错误终止
• 新进程创建。某个进程从等待变成就绪
• 进程从运行态变成阻塞态
• 进程从运行态变成就绪态

上下文切换的开销

• 直接开销：内核完成切换所用的CPU时间
  • 保存和恢复寄存器
  • 切换地址空间（昂贵）
• 间接开销
  • 高速缓存、缓冲区缓存、TLB等区域的失效

调度算法考虑的因素

• 不同的系统：批处理系统、多道程序设计系统、批处理与分时的混合系统、个人计算机、网络服务器
• 性能的理解。用户角度：周转时间、响应时间、任务的最后期限。系统角度：吞吐量、CPU利用率。
• 其它方面。用户角度：可预测性。系统角度：公平性、强制优先性、平衡资源。
• 调度算法衡量指标
  • 吞吐量（Throughput）：单位时间完成的进程数
  • 周转时间（TT，Turnaround Time）：进程从提出请求到运行完成的时间
  • 响应时间（RT，Response Time）：从提出请求到第一次回应的时间
  • CPU利用率（CPU Utilization）：CPU做有效工作时间的比例
  • 等待时间（Waiting time）：每个进程就绪队列（ready queue）中的等待时间。
• 调度算法相关的因素：
  • PCB 中存储了优先级。静态优先级（优先级不会变），动态优先级（优先级会变，例如等待较长时间后，把优先级提高）
  • 就绪队列。按照不同的优先级，队列有多个。
  • 抢占 CPU 的方式
    • 不可抢占式（Non-preemitive）。某进程被调度后一直运行下去，除非它由于自身原因不能运行
    • 抢占式（Preemptive）。有更高优先级的进程就绪时，系统强行剥夺正在运行进程的 CPU，提供给更高优先级的进程使用
  • IO密集型/CPU密集型
    • 一般优先运行IO密集型。因为它运行完后会进入等待态。
  • 时间片（Time slice，quantum）。单次允许进程运行的时间
    • 考虑因素：进程切换开销，对响应时间的要求，就绪进程个数，CPU能力，进程的行为。
    • 问题：时间片多大合适？长度固定还是可变？

调度算法

批处理系统常用的调度算法

• 先来先服务（FCFX，First Come First Serve）
  • 按照进程就绪的先后顺序使用 CPU
  • 非抢占
  • 实现简单、公平
  • 如果短进程在后面，整体等待时间长
• 最短作业优先（SJF，Shortest Job First）
  • 有最短完成时间的进程优先执行
  • 非抢占式
  • 提高了平均周转时间
• 最短剩余时间优先（SRTN，Shortest Remaining Time Next）
  • SJF 的抢占式版本，一个新就绪的进程比当前运行的进程有更短的完成时间时，抢占进程。
  • 所有进程同时可运行前提下，有最短的平均周转时间
  • 如果有源源不断的短任务到来，长任务会长时间得不到运行（饥饿问题）
• 最高响应比优先（HRRN，Highest Response Ratio Next）
  • 是 FCFX 和 SJF 的折中。先计算响应比 R = 周转时间/处理时间 = 1 + （等待时间/处理时间），响应比越高越优先。

交互式系统中的调度算法

• 轮转调度（RR，Round Robin）
  • 按照确定的顺序轮番调度，每次运行一个时间片
  • 如何确定时间片：
    • 时间片太长，大于一次典型交互时间，退化成FCFS算法。并且会延长响应时间（例如，100个进程，则需要100T才能轮到）。
    • 时间片太短，小于一次典型交互时间，进程切换频繁，浪费 CPU 时间
    • 经验选择 10ms-100ms 之间
  • 优点：公平。有利于交互式计算，响应快。
  • 缺点：进程切换有成本
  • 缺点：平均完成时间会下降。例如进程 A，B都需要 100ms完成，时间片为 1ms，那么调度顺序为 ABABAB...A(199)B(200)，平均完成时间为 199.5ms。相比之下， FCFS 平均完成时间为 （100ms+200ms）/2= 150ms
• 虚拟轮转算法（Virtual RR）
  • 为什么？使用 RR 算法时，IO 密集型任务每次分片都会提前执行完，并进入调度循环。这对于 IO 密集型任务很不公平。
  • Virtual RR 是 RR 的改进。另开一个“辅助队列”，当一个分片提前执行完，就会放入“辅助队列”。每次轮换优先从“辅助队列”选取，直到“辅助队列”为空。
• 最高优先级调度（HPF，Highest Priority First）
  • 总是选择优先级最高的进程来执行
  • 优先级设计：系统进程高于用户进程，前台进程高于后台进程，IO密集型进程高于CPU密集型进程
  • 优先级可以是静态不变的，也可以是动态变化的
  • 评价：实现简单、不公平、会让某些进程一直无法运行（饥饿现象）
  • 优先级反转 现象。例子，有高、中、低三个优先级的进程，记为 H、M、L，其中 L 持有 H 所需要的资源。那么 H 进入临界区被阻断，L进入临界区被抢占，M一直执行。导致高优先级进程一直无法运行，系统性能降低。（1997年，火星探测器上发生了此现象）
    • 解决方法3种：1）设置优先级上限，进入临界区的进程优先级都是最高的。2）优先级继承，L可以继承H的优先级。3）进入临界区的进程禁止中断
• 多级反馈队列（Multiple feedback queue）非抢占式
  • 是UNIX的BSD采用的调度算法，是一个综合调度算法
  • 就绪队列为多个，每个队列优先级不同，第一个队列优先级最高
  • 每个队列的时间片不同，优先级越低，时间片越大。$2^n$ 的方式递增。
  • 优先调度高优先级，直到高优先级为空，再调度下一个优先级的队列
  • 一个新进程就绪后直接进入第一级队列
  • 由于用完时间片而放弃 CPU 的进程，进入更低等级队列
  • 由于阻塞而放弃 CPU 的进程，就绪后进入原队列。这里有不同的策略：可以插入队尾或队首；分配的时间片可以是原本未用完的，也可以是新值。
  • 评价：对IO密集型更优先调度。对计算密集型，虽然优先度低，但时间分片长。
• 多级反馈队列，允许抢占
  • 被抢占的进程回到原来一级就绪队列的队尾（或队首）
• 最短进程优先（Shortest Process Next），与上面批处理中的 SJF 一样

多处理器调度算法，考虑问题：

• 不但要确定选择哪个进程执行，还要考虑哪个CPU上执行
• 考虑多CPU之间迁移时的开销。进程尽可能在同一个CPU上执行。
• 负载均衡问题

Windows的线程调度算法

典型系统的调度算法

• UNIX 动态优先数
• 5.3BSD 多级反馈队列
• Linux 抢占式调度
• Windows 基于优先级的抢占式多任务调度
• Solaris 综合调度算法

Windows的线程调度

• 由于 Windows 支持内核级线程，因此 调度单位是线程
• 调度算法是：基于动态优先级、抢占式、结合时间配合调整
  • 就绪线程按照优先级进入队列
  • 总是悬着优先级最高的就绪线程运行
  • 同一优先级各线程按时间片轮转进行调度
  • 多 CPU 允许多个线程并行运行
• 引发线程调度的条件
  • 一般的：正常终止/错误终止，新线程创建，等待线程变成就绪，运行态进入阻塞态，运行态变成就绪态
  • 还新增两种情况：1）一个线程的优先级改变了。2）一个线程改变它的亲和（Affinity）处理机集合

Windows 共有 32 个优先级

时间配额

进程互斥

进程互斥的例子 某程序是关于从账户付款的，初始余额为 5000元，连续两次付款（1000元和2000元），引发了2个进程：

这两个进程运行后，根据不同的调度顺序，可能有不同的结果

概念

• 进程互斥（Mutual Exclusive）：进程使用的某些共享资源（变量、文件等）需要排他性的使用（否则结果可能不对），各进程之间竞争使用这些资源。
• 临界资源 （critical resource）：资源一次只允许一个进程使用（叫做临界资源、互斥资源、共享变量）
• 临界区(互斥区，critical section，region)：各个进程中对某个临界资源（共享变量）实施操作的程序片段

不允许两个进程同时处于临界区。带来优先级反转问题（前面写了）

为了防止临界区重叠，有一些解决方案

• 软件方案：Dekker、Peterson
• 硬件方案：屏蔽中断、TSL(XCHG)指令

进程互斥的软件解决方案

一个错误的解决方案1：

... ...
while(free); // 如果 free = true，则一直在此等待；如果 free = false，则
free = true; // 标识临界区已被占用

临界区;

free = false; // 表示临界区已释放
... ...

上面的思路正确，但结果仍然可能错误。

• 原因是 程序挂起的时间点可能在 while(free) 和 free = true，这样仍然会临界区重叠
• 解决方案是把 while(free) 和 free = true 变成一个元语 ``，使其不可被中断，如下：

进程互斥的软件解决方案1:

... ...
lock();
临界区;
unlock();
... ...

一个错误的解决方案2：

进程 P:
... ...
while(not turn);
临界区
turn = false;

进程Q:
while(turn);
临界区
turn = true;

错误在于，如果 turn = true，且 Q 不想进入临界区，那么 P 就永远无法进入临界区。

一个错误的解决方案3：

进程 P:
... ...
pturn = true;
while(qturn);
临界区
pturn = false;

进程Q:
qturn = true;
while(pturn);
临界区
qturn = false;

上面的错误在于，如果 P 和 Q 恰好都在 pturn = true; 和 while(qturn); 语句之间中断，那么两个进程都永远无法进入临界区（After you 问题）。

DEKKER算法 （1965年）

• 在解法3 的基础上，引入 turn 变量（枚举类型），当出现 after you 问题时，由 turn 来决定谁进入临界区

进程 P:
... ...
pturn = true;
while(qturn){
    if (turn == 2){
        pturn = false;
        while(turn == 2);
        pturn = true;
    }
}
临界区
turn = 2;
pturn = false;

进程Q:
qturn = true;
while(pturn){
    if (turn ==1){
        qturn = false;
        while (turn == 1);
        qturn = true;
    }
}
临界区
turn = 1;
qturn = false;

此算法的缺点必须轮流运行

peterson算法 （1981年）

• 解决互斥问题
• 克服了DEKKER算法强制轮流的缺点

// 对于进程i：
enter_region(i);
临界区;
leave_region(i);


// 进入临界区的函数：
int turn; // 轮到谁了
int interested[N]; // 兴趣数组，记录哪个进程对进入 CPU 感兴趣，初始化为 false
void enter_region(int process){ // 此案例假设只有 2 个进程，因此 process = 0 或 1
    int other; // 另一个进程的进程号
    other = 1 - process;
    interested[process] = true; // 本进程对进入 CPU 感兴趣
    turn = process; // 设置标志位
    while(turn == process && interested[other] == true);
}


void leave_region(int process){
    interested[process] = false;
}

进程互斥的硬件解决方案

方案1：“开关中断”指令

执行 “关中断”指令
临界区
执行“开中断”指令

评价

• 简单、高效
• 如果临界区大，就限制了 CPU 的并发能力。
• 不适用于多处理器
• 适用于操作系统本身，不适于用户进程（因为用户程序不能使用特权指令）。

方案2:“测试并加锁”指令（TSL，TEST AND SET LOCK）

enter_region:
    TSL REGISTER,LOCK       | 复制锁到寄存器
    CMP REGISTER,#0        | 判断寄存器内容是否为0
    JNE enter_region        | 若不为0，跳转到 enter_region
    RET                     | 返回调用者，使其进入临界区 

leave_region:
    MOVE LOCK,#0            | 在锁中置0
    RET                     | 返回调用者

方案3:“交换指令”

enter_region:
    MOVE REGISTER,#1        | 寄存器置1
    XCHG REGISTER,LOCK      | 交换寄存器和锁的内容
    CMP REGISTER,#0        | 判断寄存器内容是否为0
    JNE enter_region        | 若不为0，跳转到 enter_region
    RET                     | 返回调用者，使其进入临界区 

leave_region:
    MOVE LOCK,#0            | 在锁中置0
    RET                     | 返回调用者

进程同步

进程同步（synchronization）：进程之间存在 时序关系。例如，一个进程运行到某一点，需要另一个进程给它提供消息，此时该进程进入阻塞态，获得消息后才进入就绪态。

生产者/消费者问题

• 生产者负责在缓冲区中放入数据。
• 消费者负责从缓冲区中取出数据。
• 如果缓冲区满了，生产者必须等待消费者消耗掉一些数据后才能继续放入数据。
• 如果缓冲区空了，消费者必须等待生产者放入数据后才能继续取出数据。
• 问题：忙等待，缓存区满/缓冲区空，都会有浪费。
• 解决方法：新增两个原语 睡眠、唤醒

【图片】

问题：if(count==0) sleep(); 之间用完时间并中断，那么重新调用时出现问题

信号量与 P、V 操作

• 1965年 Dijkstra 提出的
• 解决进程同步问题

信号量定义：

struct semaphore{
    int count;
    queueType queue;
}

信号量有3个操作

• 初始化
• P
• V

P(s){
    s.count--;
    if(s.count<0){
        进程设置为阻塞态，并吧进程插入到 s.queue 的末尾;
        重新调度，选另一个进程进入 CPU;
    }
}


V(s){
    s.count++;
    if(s.count<=0){
        唤醒 s.queue 中等待的一个进程;
        将其改为就绪态，并插入到就绪队列;
    }
}

说明：

• P、V 操作是原语
• 最初提出是二元信号量（解决互斥问题）
• 后来推广到一般信号量，可以解决同步问题

使用方法：

• 初始化信号量 mutex = 1
• 进入临界区前实施 P(mutex)
• 退出临界区之后实施 V(mutex)

用信号量解决生产者/消费者问题

【代码】

读者写者问题

问题描述

• 多个进程共享一个数据区，这些进程分为两组：
• 读者进程： 只读数据区中的数据
• 写者进程： 只往数据区写数据
• 要求满足条件：
  • 允许多个读者同时执行读操作
  • 不允许多个写者同时操作
  • 不允许读者、写者同时操作

分析

• 对于读者：
  • 无其他读者、写者，该读者可以读
  • 若已有写者等，但有其他读者正在读，则该读者也可以读
  • 若有写者正在写，该读者必须等
• 对于写者：
  • 无其他读者、写者，该写者可以写
  • 若有读者正在读，该写者等待
  • 若有其他写者正在写，该写者等待
• 读者写者问题是既包括互斥问题，也包括同步问题

Linux提供的读写锁

• 允许多个读同时进行
• 不允许读和写同时进行
• 不允许多个写同时进行

管程

为什么需要 管程（Monitor）

• 问题：信号量机制，程序编写困难、易出错
• 解决：1973年提出了新的同步机制，叫做管程
• 管程是一种高级同步机制
• 是一个特殊的模块，有个名字，有共享资源的数据结构以及一组操作组成
• 进程通过调用管程中的过程来间接访问管程中的数据结构

一个管程

monitor example
    integer i; // 变量
    condition c;

    procedure insert(); // 过程
    procedure remove(); // 过程

管程作为一种同步机制，解决两个问题

• 互斥
  • 管程是互斥进入的，这样可以保证管程中数据结构的完整性。
  • 管程的互斥性由编译器保证
• 同步
  • 管程中设置条件变量及等待/唤醒操作以解决同步问题
  • 可以让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒

场景：多个进程同时出现在管程中

• 原因：一个已进入管程的进程执行等待时，后进入管程的进程执行唤醒
• 如何解决
  • Hoare 管程，P 等待 Q 执行
  • MESA 管程，Q 等待 P 继续执行
  • Hansen，规定唤醒操作作为管程中最后一个可执行的操作

Hoare 管程

Hoare 管程说明

• 如果一个进程试图进入一个已被占用的管程，在 入口等待队列 等待
• 如果进程P唤醒进程Q，Q又唤醒R，管程内部出现多个等待进程，因此它们放在 紧急等待队列 中。紧急等待队列的优先级高于入口等待队列
• 条件变量：c:condition;
• 过程 wait(c)： 如果“紧急等待队列”为空，则唤醒第一个等待者；否则释放管程互斥权，并把执行该操作的进程放到 c 链的末尾
• 过程 signal(c)：如果 c 链为空，继续执行下一条语句；否则唤醒第一个等待者，然后执行该操作的进程进入“紧急等待队列”的末尾

如何实现一个管程？

• 直接构造：某个变成语言对应的编译器直接支持
• 间接构造：用已有的机制去构造，例如信号量和PV

用管程解决生产者消费者问题，代码会更简洁

// 生产者
procedure producer;
while 1:
    item = producer.produce();
    ProducerConsumer.insert(item); // 管程

// 消费者
procedure consumer;
while 1:
    item = ProducerConsumer.remove(); // 管程
    consumer.consume(item); 

对应的管程

monitor Producer Consumer;
    condition full, empty;
    integer count;

    procedure insert(item: integer){
        if count == N{
            wait(full);
        }
        insert_item(item);
        count++;
        if count == 1{
            signal(empty);
        }
    }

    procedure remove(){
        if count == 0{
            wait(empty);
        }
        item = remove_item();
        count--;
        if count==N-1{
            signal(full);
        }
    }

C/C++ 没有支持管程，但是 JAVA 支持

python、rust 本身没有管程，但可以用其它机制实现。

import threading

class Counter:
    def __init__(self):
        self.count = 0
        self.lock = threading.Lock()

    def increment(self):
        with self.lock:
            self.count += 1

    def get_count(self):
        with self.lock:
            return self.count

MESA 管程

Mesa语言（1980）提出的

Hoare 管程的缺点

• 两次额外的进程切换

进程间通信 IPC

为什么需要？

• 信号量和管程只能传递少量信息，不能传递大量信息
• 管程不适合多处理器的情况
• 因此引入进程间通信机制。

进程间通信方法

• 消息传递
• 共享内存
• 管道
• 套接字
• 远程过程调用

消息传递

• 不同的进程，内存地址不一样
• 因此需要“操作系统空间”作为中间缓冲
• 使用 send 和 receive 原语
• send 和 receive 原语可以用PV操作来构建

共享内存

• 两个进程的某一块逻辑地址，实际上都使用同一个物理地址
• 问题1:如何把两个进程各自的逻辑地址空间中的某一块，映射到同一个物理地址
• 问题2:读者-写者问题

管道PIPE

使用一个缓冲传输介质（内存或文件）链接两个进程

• 字符流方式写入读出
• 先进先出顺序
• 管道通信机制必须提供的协调能力
  • 互斥、同步、判断对方进程是否存在

典型操作系统的IPC

• UNIX
  • 管道、消息队列、共享内存、信号量、信号、套接字
• Linux
  • 管道、消息队列、共享内存、信号量、信号、套接字
  • 内核同步机制：原子操作、自旋锁、读写锁、信号量、屏障、BKL
• Windows
  • 同步对象：互斥对象、事件对象、信号量对象临界区对象互锁变量
  • 套接字、文件映射、管道、命名管道、邮件槽、剪贴板、动态数据交换、对象连接与嵌入、动态链接库、远程过程调用

其它概念

• 原子操作。原子操作命令可以确保操作不可中断性。
  • 大多数操作，例如 i++; 也是多步骤执行的，也会被中断，这在多线程中也会引发问题。
  • C/C++ 的 std::atomic, Java 的 AtomicInteger, Rust 的 Atomic
• Barrier （屏障，栅栏，关卡）。
  • 一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进
  • 是一种同步机制，是对一组线程的协调
  • 例如，多线程做矩阵计算，需要等待所有线程执行完毕，才进行下一步操作。

存储模型

为什么需要地址重定位（relocation）

• 进程运行前，代码不知道进程会被加载到内存的哪个区域
• 因此代码使用的地址不是物理地址，而是逻辑地址
• 所以需要 地址重定位，它是逻辑地址和物理地址之间的转化
• 逻辑地址，是汇编后目标代码采用的地址。逻辑地址的首地址为0，其余地址都相对于首地址而编址
• 物理地址：就是内存中存储单元的地址

分类：

• 静态重定位：
  • 当用户程序加载到内存时，一次性实现逻辑地址到物理地址映射
  • 一般可以由软件完成
• 动态重定位（现代操作系统的主流）：
  • 在进程执行过程中进行地址变换。即逐条指令执行时完成地址转换
  • 需要硬件部件支持 内存管理单元（MMU，Memory Management Unit）

空闲内存管理

1. 为了更好的管理，内存可以划分为若干的区域，这分为 等长划分，不等长划分
2. 可以有若干种数据结构管理它：
   • bitmap，只适用于等长划分。用一长串二进制表示，0代表空闲，1代表占用。
   • 空闲表。表中的每一项纪录了空闲区的起始地址、长度、标志（标志用来指向程序）
   • 空闲块链表

内存分配算法，有若干种：

• 首次适配 first fit：在空闲区表中找到第一个满足进程要求的空闲区。
• 下次适配 next fit：从上次找到的空闲区接着查找
• 最佳适配 best fit：遍历整个空闲区表，找到能够满足进程要求的最小空闲区
• 最差适配 worst fit：总是分配满足进程要求的最大空闲区

以“空闲表”为例，分配以后，记得更新“空闲区域表”、“已分配区表”

内存回收算法

• 归还后，前后空闲空间合并
• 四种情况：上相邻、下相邻、上下相邻、上下都不相邻

伙伴系统（Buddy System）

• Linux 采用的一种内存分配算法
• 优点是可以保持大的内存块
• 主要思路：
  1. 把内存按照 $2^n$ 划分
  2. 组成若干空闲块链表
  3. 分配时选择满足要求的最小的块
  4. 如果最小的块超过需要的两倍，就把块二分，继续寻找。
  5. 回收后，如果一对伙伴都空闲，则合并；如果合并后，相邻的伙伴也空闲，继续合并（消消乐）

基本内存管理方案

常见的几种：

• 进程对应的物理内存连续的方案：
  • 单一连续区
  • 固定分区
  • 可变分区
• 进程对应的物理地址不连续的方案：
  • 页式
  • 段式
  • 段页式

单一连续区（Single Contiguous Allocation）。

• 整个可用内存被分配给一个单一的进程。
• 简单，内存利用率低。

固定分区（Fixed Partitioning）。

• 将内存划分为若干分区
• 每个分区大小可以相同，也可以不同
• 分区大小固定不变
• 每个分区可以容纳一个进程。
• 简单、可多进程。内存有浪费，分区大小不灵活。

可变分区（Variable Partitioning）。

• 根据进程需要来分配空间
• 运行一段时间后，随着进程启动和销毁，会出现大量碎片的空闲区（外碎片）。
• 解决方案：紧缩技术（memory compaction，压缩技术、紧致技术、搬家技术）
• 紧缩考虑的问题：系统开销、移动时机。

页式（Paging）

• 进程的地址空间划分为大小相同的 页（page，页面）
• 内存空间也划分同样大小的 页框（page frame）
• 典型的页大小：4K/4M
• 内存分配规则：以页为单位分配，按进程需要的页来分配。逻辑上相邻的页，物理上不一定相邻。
• 使用 页表（Page Table） 这种数据结构来把 逻辑页 映射到 物理页
• 空闲内存管理：bitmap
• 地址转换，用硬件完成。CPU获取逻辑地址，分解为页号+页内地址，用页表把页号映射到页框号，然后页框号+页内偏移=物理地址
• 问题：内碎片。末尾页只有1个字节，也要分配一页。

段式（Segmentation）。

• 程序按照自身的逻辑关系，划分为若干程序段。
• 内存动态划分为若干长度不懂的物理段
• 内存分配规则：以段为单位进行分配，每段占据物理内存连续，但是段之间物理内存可以不连续

段页式（Segmented Paging）。段页式结合了段式和页式的优点，先将进程划分为多个段，每个段再划分为若干页。

交换技术

• 问题：如何在较小的内存空间，运行较大的进程？有以下几个方法
• 清除碎片：内存紧缩技术
• 覆盖技术 overlaying：程序大小超过物理内存总和。
  • 早期的操作系统
  • 按照自身的逻辑结构，让不会同时执行的程序段使用同一块内存区域
  • 要求各模块之间有明确的调用结构
  • 程序员声明覆盖结构，操作系统完成自动覆盖
• 交换技术 swapping
  • 内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与磁盘之间的动态调度）
  • 问题：
    • 进程的哪些内容要交换到磁盘？会遇到什么困难？
    • 在磁盘的什么位置保存被换出的进程？
    • 交换时机？
    • 如何选择被换出的进程？
    • 如何处理进程空间增长？
  • 问题回答
    • 交换的是栈和堆，因为它们会被频繁的分配和释放。代码和静态数据相对稳定，不需要交换。
    • 交换到哪里？交换区 一块特殊的磁盘区域，包含连续的磁道。不经过文件系统，操作系统直接访问低层磁盘读写操作。
    • 何时交换？不用就换出，内存空间不够就换出
    • 不应换出等待IO状态的进程
• 虚拟存储技术 virtual memory

虚拟存储技术

虚拟存储技术（virtual memory） 是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作

• 虚拟地址空间 即为 分配给进程的虚拟内存
• 虚拟地址 是 在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分

功能

• 虚存地址提供比物理内存空间大得多的地址空间（大小取决于CPU是多少位的）
• 存储保护
  • 确保那个进程都有独立的地址空间
  • 确保进程访问合法的地址范围
  • 确保进程的操作合法
  • 防止越界
  • 防止越权

虚拟页式存储管理系统

• 虚拟存储技术 + 页式存储管理方案
• 基本思想
  • 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
  • 之后，根据进程运行的需要，动态装入其他页面
  • 当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面。具体有两种方式
    1. 请求调页（demand paging）（更常用），需要页面时掉入内存。
    2. 预先调页（prepaging），预测并提前掉入内存
• 本质上是以CPU时间和磁盘空间换取昂贵内存空间。

页表和页表项

• 页表由页表项组成
• 通常，页表项是硬件设计的
• 页框号、有效位、访问位、修改位、保护位
  • 页框号（内存块号、物理页面号、页帧号）
  • 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘，0/1 型数据
  • 访问位：1表示正在被访问
  • 修改位：1表示被修改过，之后还会写会到磁盘
  • 保护位：读/可读写

页表也是存放在页中的，也需要多个页来存放，这些页也是不连续存放的，所以还需要一个“页目录”来表示页表存放在哪。

• 这就是“二级页表”
• 还可以有多级页表。CORE I7 有4级页表。

实际实现中，还引入了反转（倒排）页表、Hash 值等

快表（TLB，Translation Look-aside Buffers）

• 为什么？引入页表后，一次访问带来了两次以上的内存访问。CPU指令速度比内存访问快得多，CPU不能被充分利用。
• 由于 程序访问的局部性规律，引入快表
• 快表存放在高速缓存（Cache），它是一种随机存储器，可以在一个存储周期内查找。
• 它还可以在一个存储周期内，按内容并行查找出来
• 快表可以是 64个/128个
• 快表也可以用多级缓存，设计多级快表

页错误

页错误（page fault，页面错误，页故障，页面实效）

• 定义：地址转换过程中产生的异常
• 具体原因：
  • 所访问的虚拟页面没有调入物理内存：缺页异常
  • 页面访问违反权限（读/写、用户/内核）
  • 错误的访问地址（地址指向了还没写入内容的区域）

缺页异常

• 触发异常
• 操作系统执行 缺页异常处理程序：获得磁盘地址，启动磁盘，把页调入内存
  • 如果内存中有空闲页框，则分配一个页框，将新调入页装入，并修改页表中相应页表项的有效位及相应的页框号
  • 若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘

驻留集 大小：指的是给每个进程分配多少页框

• 固定分配策略：进程创建时确定
  • 可以根据进程类型（交互、批处理、应用类）
  • 或者基于程序员或系统管理员的需要来确定
• 可变分配策略：根据缺页率评估进程局部性表现
  • 缺页率高→增加页框数
  • 缺页率低→减少页框数
  • 系统开销

置换范围 计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框？ - 局部置换策略：仅在产生本次缺页的进程的驻留集中选择 - 全局置换策略：将内存中所有未锁定的页框都作为置换的候选

置换策略 在计划置换的页框集合中，选择换出哪一个页框？ - 所有策略的目标：置换 最近最不可能访问的页 - 由于 局部性原理，大多数策略都基于过去的行为来预测将来的行为 - 置换策略设计得越精致实现的软硬件开销就越大 - 不能置换被锁定的页框

页框锁定

• 为什么？虚存技术带来了开销，使进程运行时间变得不确定
• 给每个页框增加一个锁定位
• 锁定谁？操作系统核心代码、关键数据结构、IO缓冲区
• Windows提供了 VirtualLock/VirtualUnLock 函数来控制

文件系统

IO

死锁

参考资料

写本文时，画了一些图片素材：操作系统.pptx

Coursera课程：《操作系统原理》，北京大学，陈向群

• 课件pdf

说明：本文中的代码均为伪代码。