CPU中有一系列的寄存器来存储数据，

通用寄存器
- EAX:累加器
- EBX:基址寄存器
- ECX:计数器
- EDX:数据寄存器
- ESI:源地址指针寄存器
- EDI:目的地址指针寄存器
- EBP:基址指针寄存器
- ESP:堆栈指针寄存器
段寄存器，主要用来寻址
- CS:代码段(Code Segment)
- DS:数据段(Data Segment)
- ES:附加数据段(Extra Segment)
- SS:堆栈段(Stack Segment)
- FS:附加段
- GS:附加段
指令指针寄存器4
- 指令寄存器和标志寄存器
  - EIP:指令寄存器
    EIP的低16位就是8086的IP，它存储的是下一条要执行指令的内存地址，在分段地址转换中，表示指令的段内偏移地址。
  - EFLAGS:标志寄存器
    IF(Interrupt Flag):中断允许标志位,由CLI，STI两条指令来控制;设置IF 使CPU可识别外部(可屏蔽)中断请求。复位IF 则禁止中断。IF 对不可屏蔽外部中断和故障中断的识别没有任何作用。
    CF,PF,ZF,…

了解x86内存构架

地址是访问内存空间的索引。
80386是32位的处理器，即可以寻址的物理内存地址空间为2^32=4G字节
物理内存地址空间是处理器提交到总线上用于访问计算机系统中的内存和外设的最终地址。一个计算机系统中只有一个物理地址空间
线性地址空间是在操作系统的虚存管理之下每个运行的应用程序能访问的地址空间。每个运行的应用程序都认为自己独享整个计算机系统的地址空间，这样可让多个运行的应用程序之间相互隔离。
逻辑地址空间是应用程序直接使用的地址空间。
- 段机制启动、页机制未启动:逻辑地址->段机制处理->线性地址=物理地址
- 段机制和页机制都启动:逻辑地址->段机制处理->线性地址->页机制处理->物理地址逻辑地址通过段机制的映射能转变成线性地址

A启动、中断、异常和系统调用

系统调用(来源于应用程序)（同步或异步）
- 应用程序主动向操作系统发出服务请求
异常(来源于不良的应用程序)（同步）
- 非法指令或者其他坏的处理状态(如:内存出错)
中断(来源于外设)（异步）
- 来自不同的硬件设备的计时器和网络的中断

B内存分层体系

计算机体系结构

内存分层体系

CPU可以访问的内存包括两大类 : 寄存器 / cache（L1缓存 / L2缓存）
主存（物理内存）/ 磁盘（虚拟内存）主存是在运行程序时所需要保存的数据空间，而磁盘是用于持久化数据保存的数据空间。

操作系统的内存管理&地址空间、地址生成

目标

抽象：逻辑地址空间
保护：独立地址空间
共享：访问相同内存
虚拟：更多的地址空间

物理地址空间：主存和硬盘
逻辑地址空间：运行的程序

内存分配

连续内存分配

内存碎片问题

分区的动态分配

分配方式	第一适配分配	最优适配分配	最差适配分配
原理&实现	按地址排序的空闲块列表分配需要寻找一个合适的分区重分配需要检查是否可以合并相邻空闲分区	按尺寸排序的空闲块列表分配需要寻找一个合适的分区重分配需要检查是否可以合并相邻空闲分区	按尺寸排序的空闲块列表分配差距最大的分区重分配需要检查是否可以合并相邻空闲分区
优势	简单 / 易于产生更大空闲块	比较简单 / 大部分分配是小尺寸时高效	分配很快 / 大部分分配是中尺寸时高效
劣势	产生外部碎片 / 不确定性	产生外部碎片 / 重分配慢 / 产生很多没用的微小碎片	产生外部碎片 / 重分配慢 / 易于破碎大的空闲块以致大分区无法被分配

三种分配方式并无优劣之分，因为我们无法判断内存请求的大小。

压缩式与交换式碎片整理

压缩式碎片整理

紧凑（compaction）

重置程序以合并孔洞（碎片）
要求所有程序是动态可重置的
问题 :

➢ 何时重置？（在程序处于等待状态时才可以重置）

➢ 开销（内存拷贝：重定位）

交换式碎片整理

分区对换（Swapping in/out）

运行程序需要更多的内存时，抢占等待的程序并回收它们的内存，以增大可用内存空间

非连续内存分配

关键在于如何建立虚拟地址和物理地址之间的转换

软件方案

硬件方案

两种硬件方案

分段

段表由操作系统建立

分页

     >划分物理内存至固定大小的帧

>划分逻辑地址空间至相同大小的页

帧代表物理页，page代表逻辑页

页帧是指物理内存的组织和布局，代表物理内存的地址，第一个是页帧号，第二个是帧内偏移；

逻辑页

页表：记录页号所对应的页帧；

页表

页表结构

分页机制的性能问题

解决方式：

缓存Caching

间接访问（inderection）

分级页表

反向页表

◆大地址空间问题
有大地址空间(64-bits)，前向映射页表变得繁琐

比如:5 级页表.

◆不是让页表与逻辑地址空间的大小相对应,而是让页表与物理地址空间的大小相对应.

逻辑(虚拟)地址空间增长速度快于物理地址空间

基于页寄存器Page Register的方案

基于关联内存的方案

基于哈希查找的方案

哈希函数的输入就是页号以及当前程序的id（PID），输出就是页帧号；

C虚拟内存管理技术

在计算机系统中，尤其是在多道程序运行的环境下，可能会出现内存不够用的情况，怎么办？

如果是程序太大，超过了内存的容量，可以采用手动的覆盖（overlay）技术，只把需要的指令和数据保存在内存当中；
如果是程序太多，超过了内存的容量，可以采用自动的交换（swapping）技术，把暂时不能执行的程序送到外存中；
如果想要在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序，可以采用自动的虚拟存储技术。

覆盖技术

目标

是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。
原理

把程序按照其自身逻辑结构，划分为若干个功能上相互独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行。

必要部分（常用功能）的代码和数据常驻内存；
可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要用到时才装入内存；
不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖，即这些模块共用一个分区。

交换技术

目的

多道程序在内存时，让正在运行的程序或需要运行的程序获得更多的内存资源。
方法

可将暂时不能运行的程序送到外存，从而获得空闲内存空间。
操作系统把一个进程的整个地址空间的内容保存到外存中（换出 swap out），而将外存中的某个进程的地址空间读入到内存中（换入 swap in）。换入换出内容的大小为整个程序的地址空间。

覆盖技术和交换技术的比较
特点

覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。
交换技术是以在内存中的程序大小为单位进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。
换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖则发生在运行程序的内部。
在内存不够用的情形下，可以采用覆盖技术和交换技术，但是：

覆盖技术：需要程序要自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担。
交换技术：以进程作为交换的单位，需要把进程的整个地址空间都换入换出，增加了处理器的开销。
“四海之内” 解决之道：虚拟内存管理技术——虚存技术 ↓

虚拟技术

虚拟页式内存管理

修改位如果为零表示不用再写入硬盘，直接清空即可；需要的时候再从硬盘写入内存了；如果被修改过则还需要将其写回硬盘中去；

举例

缺页中断处理机制

后备存储

在何处保存未被映射的页?

能够简单地识别在二级存储器中的页
交换空间(磁盘或者文件):特殊格式，用于存储未被映射的页面

概念:后备存储 backing store

一个虚拟地址空间的页面可以被映射到一个文件(在二级存储中)中的某个位置
代码段:映射到可执行二进制文件
动态加载的共享库程序段:映射到动态调用的库文件
其它段:可能被映射到交换文件(swapfle)——>在硬盘上的换入换出分区

虚拟内存性能

页面置换算法

最优页面置换算法（OPT）

最优页面置换算法（OPT，optimal）

基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

这是一种理想情况，在实际系统中是无法实现的，因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问。

可用作其他算法的性能评价的依据。（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）

先进先出算法（FIFO）

先进先出算法（FIFO，First-In First-Out）

基本思路：选择在内存中驻留时间最长的页面淘汰。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出去，并把新的页面添加到链表的末尾。

性能较差，调出的页面有可能是经常要访问的页面。并且有Belady现象。 FIFO算法很少单独使用。

最近最久未使用算法（LRU）

最近最久未使用算法（LRU，Least Recently Used）

基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰。

它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间）最近几条指令）内，如果某些页面被频繁地访问，那么再将来的一小段时间内，他们还可能会再一次被频繁地访问。反过来说，如果过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。

时钟页面置换算法（Clock）

Clock页面置换算法，LRU的近似，对FIFO的一种改进；

基本思路

需要用到页表项的访问位(access bit)，当一个页面被装入内存时，把该位初始化为 0 00。然后如果这个页面被访问，则把该位置设为 1 11;

把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）;

当发生一个缺页中断时，考察指针所指向的最老页面，

➢ 若它的访问位为 0 00，立即淘汰；

➢ 若访问位为 1 11，则访问位置为 0 00，然后指针往下移动一格。

➢ 如此下去，直到找到被淘汰的页面，然后把指针移动到下一格。

示例

维持一个环形页面链表保存在内存中

➢ 用一个时钟（或者使用 / 引用）位来标记一个页面是否经常被访问

➢ 当一个页面被引用的时候，这个位被设置（为1）

时钟头扫遍页面寻找一个带有 u s e d b i t = 0 ( a s s e s s b i t ) used\ bit=0\ (assess\ bit)used bit=0 (assess bit)

➢ 替换在一个周转内没有被引用过的页面

二次机会算法（Enhanced Clock）

改进的Clock算法（Enhanced Clock）

这里有一个巨大的代价来替换“脏”页

修改Clock算法，使它允许脏页总是在一次时钟头扫描中保留下来

➢ 同时使用脏位和使用位来指导置换

因为考虑到时钟页面置换算法，有时候会把一些 d i r t y b i t dirty\ bitdirty bit 为 1 11（有过写操作）的页面进行置换，这样的话，代价会比较大。

因此，可以结合使用位和脏位一起来决定应该置换哪一页。

最不常用算法（LFU）

最不常用算法（LFU，Least Frequently used）

基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰。

实现方法：对每一个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。当发生缺页中断时，淘汰计数值最小的那个页面。

LRU和LFU的对比：LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问次数越多越好。

Belady现象

在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象；
原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的）即替换较少使用的页面），因此，被他置换出去的页面不一定是进程不会访问的。

FIFO算法有Belady现象

gif示例，物理页面数为 3 ：

局部页替换算法的问题、工作集模型

工作集

示例

常驻集
常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。

工作集与常驻集的关系

➢ 工作集是进程在运行过程中固有的性质

➢ 常驻集取决于系统分配给进程的物理页面数目和页面置换算法

缺页率与常驻集的关系

➢ 常驻集 ⊇ ⊇⊇ 工作集时（一个进程的整个工作集都在内存当中），缺页较少

➢ 工作集发生剧烈变动（过渡）时，缺页较多

➢ 进程常驻集大小达到一定数目后，再给它分配更多的物理页面，缺页率也不会明显下降

工作集页置换算法
思路
换出不在工作集中的页面
窗口大小 Π
当前时刻前 Π 个内存访问的页引用是工作集， Π 被称为窗口大小
实现方法
访存链表：维护窗口内的访存页面链表

访存时，换出不在工作集的页面；更新访存链表

缺页时，换入页面；更新访存链表

全局页面置换算法

1.工作集页置换算法

➢ 示例：

这种窗口大小是固定的，因此想要动态改变工作集大小，引出了

缺页率页面置换算法

可变分配策略：常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。

可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
优缺点：性能较好，但增加了系统开销。
具体实现：可以使用==缺页率算法（PFF，page fault frequency）==来动态调整常驻集的大小。
缺页率（page fault rate）
表示 “缺页次数 / 内存访问次数”（比率）或 “缺页平均时间间隔的倒数”。

影响缺页率的因素

页面置换算法
分配给进程的物理页面数目
页面本身的大小
程序的编写方法

算法实现
保持追踪缺失发生概率。

访存时，设置引用位标志
缺页时，计算从上次缺页时间$t_{last}$ 到现在 $t_{current}$的时间间隔

➢ 如果发生页缺失之间的时间是“大”的，之后减少工作集。

➢ 如果 $t_{current}-t_{last}> T $，则置换所有在$ [t_{current}-t_{last}]$时间内没有被引用的页。

➢ 如果这个发生页缺失的时间是“小”的，之后增加工作集。

➢ 如果 $t_{current}-t_{last}\leqslant T $，则增加缺失页到工作集中。

抖动问题

工作集、常驻集概念的拓展

抖动

➢ 如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集 ⊂ ⊂⊂ 工作集；

➢ 那么进程将会造成很多的缺页中断，需要频繁的在内存与外存之间替换页面；

➢ 从而使进程的运行速度变得很慢，我们把这种状态称为 ”抖动“。

产生抖动的原因

➢ 随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断就减小，缺页率不断上升。

操作系统需要在并发水平和缺页率之间达到一个平衡

➢ 选择一个适当的进程数目和进程需要的物理页面数。

负载控制

D进程管理

进程描述

进程的定义

进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

进程的组成

一个进程应该包括：

程序的代码；
程序处理的数据；
程序计数器中的值，指示下一条将运行的指令；
一组通用的寄存器的当前值，堆，栈；
一组系统资源（如打开的文件）
总之，进程包含了正在运行的一个程序的所有状态信息。

进程和程序的联系

程序是产生进程的基础
程序的每次运行构成不同的进程
进程是程序功能的体现
通过多次执行，一个程序可以对应多个进程；通过调用关系，一个进程可包括多个程序。

进程和程序的区别

进程是动态的，程序是静态的：程序是有序代码的集合。进程是程序的执行，进程有核心态 / 用户态。核心态是在操作系统中运行，但并没有写操作系统的代码，为什么会有核心态，这是因为进程在执行过程中需要完成某些特定功能,这些功能只能操作系统提供,比如从磁盘读写文件;
进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。
进程和程序的组成不同：进程的组成包括程序，数据和进程控制块（进程状态信息）

进程的特点

动态性：可动态地创建，结果进程；

并发性：进程可以被独立调度并占用处理机运行；（并发：一段，并行：一时刻）

独立性：不同进程的工作不相互影响；（页表是保障措施之一）

制约性：因访问共享数据 / 资源或进程间同步而产生制约。

进程的特点

动态性：可动态地创建，结果进程；
并发性：进程可以被独立调度并占用处理机运行；（并发：一段，并行：一时刻）对应多个进程
独立性：不同进程的工作不相互影响；（页表是保障措施之一）
制约性：因访问共享数据 / 资源或进程间同步而产生制约。

进程控制结构

描述进程的数据结构：进程控制块（Process Control Block）

操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。

进程控制块：操作系统管理控制进程运行所用的信息集合。

操作系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志。

使用进程控制块

➢ 进程的创建：为该进程生成一个PCB

➢ 进程的终止：回收它的PCB

➢ 进程的组织管理：通过对PCB的组织管理来实现

（PCB具体包含什么信息？如何组织的？进程的状态转换？）

PCB的组织方式

链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表。

各状态的进程形成不同的链表：就绪链表，阻塞链表

索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表

各状态的进行形成不同的索引表：就绪索引表，阻塞索引表

进程状态

进程生命期管理

进程创建——》进程运行——》进程等待——》进程唤醒——》进程结束

进程创建

引起进程创建的3个主要事件：

系统初始化；
用户请求创建一个新进程；
正在运行的进程执行了创建进程的系统调用。

进程运行

内核选择一个就绪的进程，让它占用处理机并执行（后续的调度算法）

为何选择？
如何选择？

进程等待

在以下情况下，进程等待（阻塞）：

请求并等待系统服务，无法马上完成
启动某种操作，无法马上完成
需要的数据没有到达

进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生。

进程唤醒

唤醒进程的原因：

被阻塞进程需要的资源可被满足
被阻塞进程等待的事件到达
将该进程的PCB插入到就绪队列

进程只能被别的进程或操作系统唤醒。

进程结束

在以下四种情况下，进程结束：

正常退出（自愿的）
错误退出（自愿的）
致命错误（强制性的）
被其他进程所杀（强制性的）

进程状态变化模型

进程状态变化模型
进程的三种基本状态：

进程在生命结束前处于三种基本状态之一。

不同系统设置的进程状态数目不同。

运行状态（Running）：当一个进程正在处理机上运行时
就绪状态（Ready）：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行
等待状态（阻塞状态 Blocked）：一个进程正在等待某一时间而暂停运行时。如等待某资源，等待输入 / 输出完成。

创建状态（New）：一个进程正在被创建，还没被转到就绪状态之前的状态。

结束状态（Exit）： 一个进程正在从系统中消失时的状态，这是因为进程结束或由于其它原因所导致。

可能的状态变化如下：

NULL → New：一个新进程被产生出来执行一个程序。

New → Ready：当进程创建完成并初始化后，一切就绪准备运行时，变为就绪状态。是否会持续很久？很快。

Ready → Running ：处于就绪态的进程被进程调度程序选中后，就分配到处理机上来运行。（怎么选中取决于后面的调度算法）

Running → Exit ：当进程表示它已经完成或者因出错，当前运行进程会由操作系统作结束处理。

Running → Ready ：处于运行状态的进程在其运行过程中，由于分配它的处理机时间片用完而让出处理机。谁完成？OS。

Running → Blocked：当进程请求某样东西且必须等待时。例如？等待一个计时器的到达、读 / 写文件比较慢等。

Blocked → Ready ：当进程要等待某事件到来时，它从阻塞状态变到就绪状态。例如？事件到达等。谁完成？OS。

进程挂起模型

Why？为了合理且充分地利用系统资源。

进程在挂起状态时，意味着进程没有占用内存空间，处在挂起状态的进程映像在磁盘上。（把进程放到磁盘上）

挂起状态

阻塞挂起状态（Blocked-suspend）：进程在外存并等待某事件的出现。
就绪挂起状态（Ready-suspend）：进程在外存，但只要进入内存，即可运行。

与挂起相关的状态转换

挂起（Suspend）： 把一个进程从内存转到外存，可能有以下几种情况：

阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行时就绪进程。
就绪到就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程。
运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转导就绪挂起状态。

在外存时的状态转换：

阻塞挂起到就绪挂起：当有阻塞挂起因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。
解挂 / 激活： 把一个进程从外存转到内存；可能有以下几种情况：

就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换。
阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程。

问题：OS怎么通过PCB和定义的进程状态来管理PCB，帮助完成进程的调度过程？

线程（Thread）

为什么使用线程？

【案例】编写一个MP3播放软件。

核心功能模块有三个：
(1) 从MP3音频文件中读取数据；
(2) 对数据进行解压缩；
(3) 把解压缩后的音频数据播放出来。

单进程的实现方法

main()
{
    while (TRUE) 
    {
        Read(); // I/O
        Decompress(); // CPU
        Play();
	}
}
Read() {...}
Decompress() {...}
Play() {...}
/*
	问题：
	播放出来的声音能否连贯？ 
	各个函数之间不是并发执行，影响资源的使用效率。
*/

多进程的实现方法

// 程序1
main()
{
    while (TRUE) 
    {
		Read();
	}
}
Read() {...}
// 程序2
main()
{
    while (TRUE) 
    {
		Decompress();
	}
}
Decompress() {...}
// 程序3
main()
{
    while (TRUE) 
    {
		Play();
	}
}
Play() {...}
// 问题：进程之间如何通信，共享数据？另外，维护进程的系统开销较大；
// 创建进程时，分配资源，建立PCB；撤销进程时，回收资源，撤销PCB；进程切换时，保存当前进程的状态信息

怎么来解决这些问题？

需要提出一种新的实体，满足以下特征：

实体之间可以并发执行；
实体之间共享相同的地址空间。

这实体就是线程（Thread）。

什么是线程

Thread：线程就是进程当中的一条执行流程。

进程由两部分组成，一部分是资源组合，另一部分是线程

从两个方面重新理解进程：

从资源组合的角度：进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段、数据段）、打开的文件等各种资源；
从运行的角度：代码在这个资源平台上的一条执行流程（线程）。

线程有自己的程序控制块TCP，TCP只负责管理和执行流程相关的一系列信息，包括程序计数器PC，堆栈SP，寄存器Register，共享的是资源，比如代码段、数据段以及文件等。

*PC总是指向下一条将要取指的指令地址*

线程的优点也是线程的缺点，由于共享资源，安全性得不到保障。

使用线程：很强调性能、执行代码相对统一的高性能计算（天气预报、水利、空气动力）；

使用进程：Chrome浏览器，一个进程打开一个网页，某一个网页崩溃之后不会影响到其他进程网页的浏览。

进程和线程有各自的特点，需要根据应用具体情况选择合适的模式设计程序。

线程和进程的比较

进程是资源分配单位，线程是CPU调度单位；
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
线程同样具有就绪，阻塞和执行三种基本状态，同样具有状态之间的转换关系；
线程能减少并发执行的时间和空间开销：

➢ 线程的创建时间比进程短；（直接利用所属进程的一些状态信息）

➢ 线程的终止时间比进程短；（不需要考虑资源的释放问题）

➢ 同一进程内的线程切换时间比进程短；（同一进程不同线程的切换不需要切换页表）

➢ 由于同一进程的各线程之间共享内存和文件资源，可直接进行不通过内核的通信。（直接通过内存地址数据传递）

线程的实现

主要有三种线程的实现方式：

用户线程：在用户空间实现；

POSIX Pthreads，Mach C-threads，Solaris threads

内核线程：在内核中实现；

Windows，Solaris，Linux

轻量级进程：在内核中实现，支持用户线程。

cess）
操作系统看不到的线程称作用户线程，由专门的用户线程库来完成对用户线程的管理，而操作系统管理起来的线程称作内核线程

在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等。

由于用户线程的维护由相应的进程来完成（通过线程库函数），不需要操作系统内核了解用户进程的存在，可用于不支持线程技术的多进程操作系统；
每个进程都需要它自己私有的线程控制块（TCB）列表，用来跟踪记录它的各个线程的状态信息（PC，栈指针，寄存器），TCB由线程库函数来维护；
用户线程的切换也是由线程库函数来完成，无需用户态 / 核心态切换，所以速度特别快；
允许每个进程拥有自定义的线程调度算法。

用户线程的缺点：

阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待；
当一个线程开始运行时，除非它主动地交出CPU的使用权，否则它所在的进程当中的其他线程将无法运行；
由于时间片分配给进程，所以与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。

内核线程
操作系统能够看到进程也可能看到线程，线程在内核中实现；CPU、操作系统调度的单位是线程

内核线程的调度是由操作系统完成，而资源的管理是由进程完成

轻量级进程（LightWeight Process）

它是内核支持的用户线程。一个进程可以有一个或多个轻量化进程，每个轻量级进程由一个单独的内核线程来支持。（Solaris / Linux）

进程切换

上下文切换（Context switch）,是切换进程中所用到的一些寄存器

停止当前运行进程（从运行状态变成其他状态），并且调度其他进程（转变为运行状态）

必须在切换之前存储许多部分的进程上下文
必须能够在之后恢复他们，所以进程不能显示它曾经被暂停过
必须快速（上下文切换时非常频繁）

需要存储什么上下文？

寄存器（PC，SP…），CPU状态，…
一些时候可能会费时，所以我们应该尽可能避免

操作系统为活跃进程准备了进程控制块（PCB）
操作系统将进程控制块（PCB）放置在一个合适的队列里

➢ 就绪队列

➢ 等待I/O队列（每个设备的队列）

➢ 僵尸队列

进程控制

创建进程

fork()的地址空间复制

加载和执行进程

系统调用exec()加载程序取代当前运行的进程。

In the parent process:
main()
...
int pid = fork(); // 创建子进程
if (pid == 0) {   // 子进程
	exec_status = exec("calc", argc, argv0, argv1, ...);
	printf("Why would I execute?");
} else { // 父进程。合理设计：else if (pid > 0)
	printf("Whose your daddy?");
	...
	child_status = wait(pid);
}
if (pid < 0) { /* error occurred */

在shell中调用fork()后加载计算器的图示

执行完exec()后，pid的id变化了，open files的路径也改变了

在实际内存中的布局图：

执行完exec()后，PCB中的代码段完全被新的程序calc所替换，且执行地址发生了变化

fork后，exec前

上图为exec后,代码、堆栈都会被覆盖，执行也从calc的main函数开始执行，文件发生改变，地址发生改变

exec()调用允许一个进程”加载“一个不同的程序并且在main开始执行（事实上 _start）
它允许一个进程指定参数的数量（argc）和它字符串参数数组（argv）
如果调用成功

➢ 它是相同的进程…

➢ 但是它运行了一个不同的程序！！

代码，stack & heap 重写

fork()的简单实现：

对子进程分配内存
复制父进程的内存和CPU寄存器到子进程（有一个寄存器例外）
开销昂贵！！

在99%的情况下，我们在调用fork()之后调用exec()

在fork()操作中内存复制是没有作用的
子进程将可能关闭打开的文件和连接
开销因此是最高的

为什么不能结合它们在一个调用中（OS/2，windows）？
vfork()

一个创建进程的系统调用，不需要创建一个同样的内存映像
一些时候称为轻量级fork()
子进程应该几乎立即调用exec()
现在不再使用（虚fork，早期的Unix系统提供的一种手段，只复制一小部分内容）

➢ 目前使用 Copy on Write（COW）技术参考

➢ Java中也有Copy on Write技术，相关实现在并发包java.util.concurrent中：

等待和终止进程

wait()系统调用是被父进程用来等待子进程的结束，用于配合子进程的exit完成对所有资源的回收

一个子进程向父进程返回一个值，所以父进程必须接受这个值并处理（子进程无法释放掉自己的PCB，父进程在子进程执行结束后，接收返回值，帮助子进程释放内存中的PCB等资源）

子进程在exit之后wait之前属于僵尸进程
wait()系统调用担任这个要求

➢ 它使父进程去睡眠来等待子进程的结束

➢ 当一个子进程调用exit()的时候，操作系统解锁父进程，并且将通过exit()传递得到的返回值作为wait()调用的一个结果（连同子进程的pid一起）如果这里没有子进程存活，wait()立刻返回。

➢ 当然，如果这里有为父进程的僵尸等待，wait()立即返回其中一个值（并且解除僵尸状态）

进程结束执行之后，它调用exit()

这个系统调用：

➢ 将这程序的 ”结果“ 作为一个参数

➢ 关闭所有打开的文件，连接等等

➢ 释放内存

➢ 释放大部分支持进程的操作系统结构

➢ 检查是否父进程是存活着的：

√ 如果是的话，它保留结果的值直到父进程需要它；在这种情况里，进程没有真正死亡，但是它进入了僵尸（zombie/defunct）状态

     √ 如果没有，它释放所有的数据结构，这个进程死亡（Root进程会定期扫描僵尸队列 判断僵尸状态的子进程的父进程是否存在）

➢ 清理所有等待的僵尸进程

祖宗进程（root）会定期扫描进程控制块的列表看是否有进程处于僵尸状态，如果有就会代替这个进程的父进程完成回收操作

进程终止是最终的垃圾收集（资源回收）

执行exec()时，进程可能处于不同的状态。

进程间通信

进程互斥不同步

死锁

第8章调度

操作系统——调度

当计算机是多道程序设计系统时，通常会有多个进程或线程竞争CPU。只要有两个或更多进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，，那么就必须选择下一个要运行的进程。在操作系统中，完成这一选择工作的部分称为调度程序；

背景

上下文切换

切换CPU的当前任务，从一个进程/线程到另一个
保存当前进程/线程在 PCB/TCB 中的执行上下文（CPU状态）
读取下一个进程/线程的上下文
CPU调度
从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
调度程序：挑选进程/线程的内核函数（通过一些调度策略）
什么时候进行调度？
CPU调度时间

以上进程之间的切换都会涉及CPU的调度问题

比较调度算法的准则

CPU使用率

➢ CPU处于忙状态所占时间的百分比

吞吐量

➢ 在单位时间内完成的进程数量

周转时间

➢ 一个进程从初始化到结束，包括所有等待时间所花费的总时间

等待时间

➢ 进程在就绪队列中的总时间

响应时间

➢ 从一个请求被提交到产生第一次相应所花费的总时间

吞吐量 vs 延迟
人们通常都需要 ”更快“ 的服务

什么是更快？

➢ 传输文件时的高带宽

➢ 玩游戏时的低延迟

➢ 这两个因素是独立的

和水管类比

➢ 低延迟：喝水的时候想要一打开水龙头水就流出来（响应时间）

➢ 高带宽：给游泳池充水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟（吞吐量）

我们的目标：

➢ 减少响应时间：及时处理用户的输出并且尽快将输出提供给用户

➢ 减少平均响应时间的波动：在交互系统中，可预测性比高差异性低平均更重要

➢ 增加吞吐量—两个方面：

√ 减少开销（操作系统开销，上下文切换）

√ 系统资源的高效率用（CPU，I/O设备）

➢ 减少等待时间：减少每个进程的等待时间

其实这些指标是有矛盾的，比如很难同时满足最小响应时间和最大吞吐量，要么只顾及某一点，要么对两点进行折中。

低延迟调度增加了交互式表现

➢ 如果移动了鼠标，但是屏幕中的光标却没动，我们可能会重启电脑

操作系统需要保证低吞吐量不受影响

➢ 我想要结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务

吞吐量是操作系统的计算带宽

响应时间是操作系统的计算延迟

公平的目标
举例

➢ 保证每个进程占用相同的CPU时间

➢ 这公平吗？如果一个用户比其他用户运行更多的进程怎么办

举例

➢ 保证每个进程都等待相同的时间

公平通常会增加平均响应时间

调度算法

先来先服务算法（FCFS）

FCFS：First Come，First Served

依据进程进入就绪状态的先后顺序排列

➢ 如果进程进入阻塞或结束状态时，就绪队列中的下一个进程会得到CPU

优点

简单

缺点

平均等待时间波动较大

花费时间少的任务可能排在花费时间长的任务后面

可能导致I/O和CPU之间的重叠处理

➢ CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待

短进程优先算法（SPN(SJF) / SRT）

SPN：Shortest Process Next（短进程优先算法）
SJF：Shortest Job First（短作业优先算法）
SRT：Shortest Remaining Time（短剩余时间优先算法）

选择下一个最短的进程（短任务优先）

➢ 按照预测的完成时间来将任务入队

可以是抢占的或者是不可抢占的

➢ 可抢占：又叫 Shortest-Remaining-Time (SRT) （最短剩余时间）

短进程优先算法具有最优平均周转时间。

可能导致饥饿

➢ 连续的短任务流会使长任务饥饿

➢ 短任务可用时的任何场任务的CPU时间都会增加平均等待时间
需要预测未来

➢ 怎么预估下一个CPU突发的持续时间

➢ 简单的解决：询问用户

➢ 如果用户欺骗就杀死进程

➢ 如果不知道怎么办

短进程优先算法的执行时间预估

最高响应比优先算法（HRRN）

HRRN：Highest Response Ratio Next

选择就绪队列中响应比R值最高的进程

在短进程优先算法的基础上改进
不可抢占
关注进程的等待时间
防止无限期推迟

轮循算法（RR）

时间片轮转算法（Round Robin，RR）

时间片

➢ 分配处理机资源的基本时间单元

时间片结束时，按FCFS算法切换到下一个就绪进程
每隔(n–1) 个时间片进程执行一个时间片 q

设置时间片为 20 2020，每个进程轮流的占用时间片：

RR 花销：额外的上下文切换（保证每个进程都有机会执行）
时间量子太大

➢ 等待时间过长

➢ 极限情况退化成FCFS

时间量子太小

➢ 反应迅速，但产生大量上下文切换

➢ 吞吐量由于大量的上下文切换开销受到影响

目标

➢ 选择一个合适的时间量子

➢ 经验规则：维持上下文切换开销处于1%以内

看起来好像FCFS更好一点，因为在FCFS中没有频繁的上下文切换，所以它总等待时间反而还会降低，但是我们还要权衡，因为在FCFS中它达不到像RR一样每一个进程及时得到相应。

公平性会带来一定的代价。

多级反馈队列算法（MFQ）

MFQ：Multilevel Feedback Queues

多级队列调度算法（MQ）

就绪队列被划分成独立的队列

➢ 如：前台（交互），后台（批处理）

每个队列拥有自己的调度策略

➢ 如：前台 — RR，后台 — FCFS

调度必须在队列间进行

➢ 固定优先级

√ 先处理前台，然后处理后台

√ 可能导致饥饿

➢ 时间切片（时间片轮转）

√ 每个队列都得到一个确定的能够调度其进程的CPU总时间

√ 如：80%给使用RR的前台，20%给使用FCFS的后台

在多级队列中，各个队列之间是没有交互的，进一步改进，进程可在不同队列间移动的多级队列算法：

多级反馈队列算法（MFQ）

➢ 可以根据情况（反馈）调整进程的优先级、队列。

优先级越高的队列中它的时间片就越短。

优点

CPU密集型任务的优先级下降很快
I/O密集型任务停留在高优先级

公平共享调度算法（FSS）

FSS：Fair Share Scheduling

FSS控制用户对系统资源的访问

➢ 一些用户组比其他用户组更重要

➢ 保证不重要的组无法垄断资源

➢ 未使用的资源按照每个组所分配的资源的比例来分配

➢ 没有达到资源使用率目标的组获得更高的优先级

评价方式

调度算法总结

先来先服务算法（FCFS）

➢ 不公平，平均等待时间较差

短进程优先算法（SPN(SJF) / SRT）

➢ 不公平，但是平均等待时间最小

➢ 需要精确预测计算时间

➢ 可能导致饥饿

最高响应比优先算法（HRRN）

➢ 基于SPN调度改进

➢ 不可抢占

轮循算法（RR）

➢ 公平，但是平均等待时间较差

多级反馈队列算法（MFQ）

➢ 和SPN类似，多种算法的集成

公平共享调度算法（FSS）

➢ 公平是第一要素
实时调度
实时系统
定义

➢ 正确性依赖于其时间和功能两方面的一个操作系统

性能指标

➢ 时间约束的及时性（deadlines）

➢ 速度和平均性能相对不重要

主要特征

➢ 时间约束的可预测性

分类

强实时系统

➢ 需要在保证时间内完成重要的任务，必须完成

弱实时系统

➢ 要求重要的进程的优先级更高，尽量完成，并非必须

实时任务

周期实时任务

硬时限和软时限

硬时限（Hard deadline）

➢ 如果错过了最后期限，可能会发生灾难性或非常严重的后果

➢ 必须验证：在最坏的情况下也能够满足时限吗？

➢ 保证确定性

软时限（Soft deadline）

➢ 理想情况下，时限应该被最大满足。如果有时限没有被满足，那么就相应地降低要求

➢ 尽最大努力去保证

可调度性

单调速率（RM）

速率单调调度算法（RM，Rate Monotonic）

最佳静态优先级调度
通过周期安排优先级
周期越短优先级越高
执行周期最短的任务

截止日期最早优先（EDF）

最早期限调度 (EDF，Earliest Deadline First)

最佳动态优先级调度
Deadline越早优先级越高
执行Deadline最早的任务

多处理器调度

多处理器的CPU调度更复杂

➢ 多个相同的单处理器组成一个多处理器

➢ 优点：复杂共享

对称多处理器（SMP）

➢ 每个处理器运行自己的调度程序

➢ 需要在调度程序中同步

优先级反转

优先级继承（Priority Inheritance）

优先级天花板协议（priority ceiling protocol）

第9章同步互斥

死锁，多个进程各自占用部分的资源

背景

独立的线程

➢ 不和其他线程共享资源或状态

➢ 确定性 => 输入状态决定结果

➢ 可重现 => 能够重现起始条件，I/O

➢ 调度顺序不重要

合作线程

➢ 在多个线程中共享状态

➢ 不确定性

➢ 不可重现

不确定性和不可重现意味着bug可能是间歇性发生的

进程 / 线程，计算机 / 设备需要合作。

合作优点

1.共享资源

➢ 一台电脑，多个用户

➢ 一个银行存款余额，多台ATM机

➢ 嵌入式系统（机器人控制：手臂和手的协调）

2.加速

➢ I/O操作和计算可以重叠

➢ 多处理器：将程序分成多个部分并行执行

3.模块化

➢ 将大程序分解成小程序

√ 以编译为例，gcc会调用cpp，cc1，cc2，as，ld

➢ 使系统易于扩展

新进程分配标识中的可能的异常现象

最主要的问题在于：整个操作的四条机器指令执行过程中，产生了一次上下文切换，使得整个的结果和我们预期不一致了。

调度的时机点可以在四条语句的任何一个位置产生切换，会得到很多不一样的结果，这种交叉切换性会有很多种情况，也就意味着最终的结果具有不确定性和不可重复性。

无论多个线程的指令序列怎样交替执行，程序都必须正常工作

➢ 多线程程序具有不确定性和不可重现的特点

➢ 不经过专门设计，调试难度很高

不确定性要求并行程序的正确性

➢ 先思考清楚问题，把程序的行为设计清楚

➢ 切忌给予着手编写代码，碰到问题再调试

我们必须要有一些新的机制来保证能够达到最终确定的结果，后面会引入同步互斥机制解决这种不确定性的问题。

一些概念

Race Condition（竞态条件）

系统缺陷：结果依赖于并发执行或者时间的顺序 / 时间

➢ 不确定性

➢ 不可重现

怎么样避免竞态？

Atomic Operator（原子操作）

原子操作是指一次不存在任何终端或者失败的执行

➢ 该执行成功结束

➢ 或者根本没有执行

➢ 并且不应发生任何部分执行的状态

实际上操作往往不是原子的

➢ 有些看上去是原子操作，实际上不是

➢ 连x++这样的简单语句，实际上是由三条指令构成的

➢ 有时候甚至连单条假期指令都不是原子的

√ Pipeline，super-scalar，out-of-order，pape fault

有可能 A AA 赢，有可能 B BB 赢，有可能两个人都无法赢，无法保证。

临界区（Critical section）

是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域
互斥（Mutual exclusion）

是指当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源
死锁（Dead lock）

是指两个或以上进程，在相互等待完成特定任务，而最终没法将自身任务进行下去，形成循环等待
饥饿（Starvation）

是指一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行
临界区（Critical section）
临界区的属性

互斥：同一时间临界区中最多存在一个线程

Progress：如果一个线程想要进入临界区，那么它最终会成功

有限等待：如果一个线程i处于入口区，那么在i的请求被接受之前，其他线程进入临界区的时间是有限制的

无忙等待（可选）：如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起

临界区的实现方法

禁用中断

软件方法

更高级的抽象方法

不同的临界区实现机制的比较

➢ 性能：并发级别

补充：

临界区（critical section）

➢ 进程中访问临界资源的一段需要互斥执行的代码

进入区（entry setcion）

➢ 检查是否进入临界区的一段代码

➢ 如可进入，设置相应 “正在访问临界区” 标志

退出区（exit section）

➢ 清除 “正在访问临界区” 标志

剩余区（remainder section）

➢ 代码中的其余部分

临界区的访问规则

空闲则入（Progess）

➢ 没有进程在临界区时，任何进程可以进入

忙则等待（互斥）

➢ 有进程在临界区时，其他进程均不能进入临界区

有限等待

➢ 等待进入临界区的进程不能无限期的等待

让权等待（可选）

➢ 不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

方法1：禁用硬件中断
没有中断，没有上下文切换，因此没有并发

➢ 硬件将中断处理延迟到中断被启用之后

➢ 大多数现代计算机体系结构都提供指令来完成

进入临界区

➢ 禁用中断

离开临界区

➢ 开启中断

用这种方法确实可以解决这个问题，但它还有一些缺点：

一旦中断被禁用，线程就无法被停止

➢ 整个系统都会为你停下来

➢ 可能导致其他线程处于饥饿状态

要是临界区可以任意长怎么办？

➢ 无法限制响应中断所需的时间（可能存在硬件影响）

要小心使用

➢ 适用于临界区很小的情况

在多CPU的情况下存在一定局限性，无法解决互斥问题。

基于软件的解决方案

这里即使两个进程都为turn和flag赋值了，turn也只能为0或1，所以flag = [true, true]时也能保证有一个能跳出循环并执行

方法3：更高级的抽象

第10章信号量和管理

背景

信号量

信号量（semaphore），抽象数据类型

➢ 一个整形（s e m semsem），具有两个原子操作

➢ P ( ) P()P()：s e m semsem 减 1 11，如果 s e m < 0 sem<0sem<0，等待，否则继续

➢ V ( ) V()V()：s e m semsem 加 1 11，如果 s e m ≤ 0 sem≤0sem≤0，唤醒一个等待的 P PP

信号量类似铁路

➢ 初始化 2 22 个资源控制信号灯

gif

xinhaol

进入临界区的进程执行 P ( ) P()P() 操作，当临界区已经有 2 22 个进程时，信号量不够，变为红灯，再来的进程只能等待，直到某一个进程离开了临界区，变为绿灯，此时进程执行 V ( ) V()V() 操作，将等待的进程唤醒，进入临界区。

Dijkstra在20世纪60年代提出

➢ P：Prolaag（荷兰语简称“Probeer te Verlagen”，或尝试减少）

➢ V：Verhoog（荷兰语增加）

在早期的操作系统主要是同步原语

➢ 例如，原Unix

➢ 现在很少用（但是还是非常重要在计算机科学中研究）

信号量的特性

信号量是整数
信号量是被保护的变量

➢ 初始化完成后，唯一改变一个信号量的值的办法是通过 P ( ) P()P() 和 V ( ) V()V()

➢ 操作必须是原子

P () 能够阻塞，V() 不会阻塞
我们假定信号量是 “公平的”

➢ 没有线程被阻塞在 P ( ) P()P() 仍然堵塞如果 V ( ) V()V() 被无限频繁调用（在同一个信号量）

➢ 在实践中，FIFO经常被使用，也就是先进先出

自旋锁（Spinlock）能否是FIFO类型？

不能

信号量的实现

两个类型信号量

➢ 二进制信号量：可以是 0 或 1

➢ 一般/计数信号量：可取任何非负值

➢ 两者相互表现（给定一个可以实现另一个）

信号量可以用在 2 个方面

➢ 互斥

➢ 条件同步（调度约束：一个线程等待另一个线程的事情发生）

信号量使用

用二进制信号量实现的互斥

mutex = new Semaphore(1);

mutex->P();
...
Critical Section;
...
mutex->V();

用二进制信号量实现的调度约束

condition = new Semaphore(0);

// Thread A
...
condition->P(); // 等待线程B某一些指令完成之后再继续运行，在此阻塞
...

// Thread B
...
condition->V(); // 信号量增加唤醒线程A
...

生产者-消费者问题

一个线程等待另一个线程处理事情

➢ 比如生产东西或消费东西（生产者消费者模式）

➢ 互斥（锁机制）是不够的

例如：有界缓冲区的生产者-消费者问题

➢ 一个或者多个生产者产生数据将数据放在一个缓冲区里

➢ 单个消费者每次从缓冲区取出数据

➢ 在任何一个时间只有一个生产者或消费者可以访问该缓冲区

正确性要求

➢ 在任何一个时间只能有一个线程操作缓冲区（互斥）

➢ 当缓冲区为空时，消费者必须等待生产者（调度/同步约束）

➢ 当缓存区满，生产者必须等待消费者（调度/同步约束）

每个约束用一个单独的信号量

➢ 二进制信号量互斥

➢ 一般信号量fullBuffers

➢ 一般信号了emptyBuffers

class BoundedBuffer {
	mutex = new Semaphore(1);
	fullBuffers = new Semaphore(0);  // 说明缓冲区初始为空
 	emptyBuffers = new Semaphore(n); // 当前生产者可以往buffer中存入n个数据(size)
}
// 生产者 添加数据
BoundedBuffer::Deposit(c){
	emptyBuffers->P();
	mutex->P();
	Add c to the buffer;
	mutex->V();
	fullBuffers->V();
}
// 消费者 取出数据
BoundedBuffer::Remove(c){
	fullBuffers->P();
	mutex->P();
	Remove c from buffer; 
	mutex->V();
	emptyBuffers->V();
}

信号量实现

使用硬件原语

➢ 禁用中断

➢ 原子指令（test-and-set）
类似锁

➢ 例如：“禁用中断”

class Semaphore {
	int sem;
	WaitQueue q;
}

Semaphore::P() {
	--sem;
	if (sem < 0) {
		Add this thread t to q;
		block(p);
	}
}

Semaphore::V() {
	++sem;
	if (sem <= 0) {
		Remove a thread t from q;
		wakeup(t);
	}
}

信号量的双用途

➢ 互斥和条件同步

➢ 但等待条件是独立的互斥
读/开发代码比较困难

➢ 程序员必须非常精通信号量
容易出错

➢ 使用的信号量已经被另一个线程占用

➢ 忘记释放信号量
不能够处理死锁问题

管程

目的：分离互斥和条件同步的关注
什么是管程（Moniter）

➢ 一个锁：指定临界区

➢ 0或者多个条件变量：等待，通知信号量用于管程并发访问共享数据
一般方法

➢ 收集在对象 / 模块中的相关共享数据

➢ 定义方法来访问共享数据

南大操作系统

1、为什么要学操作系统

理解操作系统：三个根本问题

操作系统服务谁？

程序 = 状态机
课程涉及：多线程Linux应用程序

（设计、应用视角）操作系统为程序提供什么服务？

操作系统 = 对象 + API
课程涉及：POSIX+ 部分Linux特性

（实现/硬件视角）如何实现操作系统提供的服务？

操作系统 = C程序
- 完成初始化后就成为interrupt/trap/fault handle
课程设计：xv6，自制迷你操作系统

2、什么是程序和编译器

数字逻辑电路

程序和状态机的关系

C程序的状态机模型

void hanoi(int n, char from, char to, char via) {
    if(n == 1) printf("%c-> %c", from, to);
else {
    hanoi(n-1, from, via, to);
    hanoi(1, from, to, via);
    hanoi(n-1, via, to, from);
}
    return;
}

每一次函数调用都会创建新的栈帧；

什么是栈

在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。

在计算机系统中，栈也可以称之为栈内存是一个具有动态内存区域,存储函数内部（包括main函数）的局部变量和方法调用、以及函数参数值，是由系统自动分配的，一般速度较快；存储地址是连续且存在有限栈容量，会出现溢出现象。程序可以将数据压入栈中，也可以将数据从栈顶弹出。压栈操作使得栈增大，而弹出操作使栈减小。

栈用于维护函数调用的上下文，离开了栈函数调用就没法实现。

什么是栈帧

每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame).每个独立的栈帧一般包括:

函数的返回地址和参数

临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量

函数调用的上下文
栈是从高地址向低地址延伸,一个函数的栈帧用ebp 和 esp 这两个寄存器来划定范围**.ebp 指向当前的栈帧的底部,esp 始终指向栈帧的顶部;**
ebp 寄存器又被称为帧指针(Frame Pointer);
esp 寄存器又被称为栈指针(Stack Pointer);

什么是栈帧 - 清华大咖 - 博客园 (cnblogs.com)

【Golang】函数调用栈（上）栈帧布局与函数跳转~_哔哩哔哩_bilibili

每个函数开始前会创建栈帧，结束时又会释放栈帧；

什么是（二进制）程序

GDB十个常用调试命令_gdb si-CSDN博客

操作系统知识：程序计数器（pc）、指令寄存器（IR）、通用寄存器（GR）、状态寄存器（SR）、程序状态字PSW_pc和ir-CSDN博客

GDB观察点watchpoints的介绍和演示 - 刘跑跑 - 博客园 (cnblogs.com)

构造最小的Hello，World

int main() {
    prinf("Hello,World");
}

gcc编译出来的文件不满足“最小”

——verbose可以查看所有编译选项
- printf变成了puts@plt
-static会复制libc

直接硬来？

强行编译+链接：gcc -c+ld

直接用ld链接失败
- ld不知道怎么链接库函数
空的main函数倒是可以
- 链接时得到奇怪的警告（可以定义成_start避免警告）
- 但Segmentation Fault了……

解决异常退出

Hello World的汇编实现

具体汇编代码

如何在程序的两个视角之间切换

操作系统中的一般程序

二进制程序也是操作系统中的对象

系统中常见的应用程序

对于状态机的数学理解

编译器和编译优化

什么是编译器

编译器的输入

高级语言c代码=状态机

编译器的输出

汇编代码（指令序列）= 状态机

编译器 = 状态机之间的翻译器

编译优化操作

但编译优化同样也存在着问题

编译正确性

3、硬件视角的操作系统

一切皆为状态机

计算机系统的状态机模型

状态

内存、寄存器的数值

初始状态

由系统设计者规定（CPU Reset）

状态迁移

从PC取指令执行

寄存器、内存

struct CPUState {
    uint32_t regs[32],csr[CSR_COUNT];
    uint8_t *mem;
    uint32_t mem_offset,mem_size;
}

还有外部世界的态

设备上的寄存器（memory-mapped I/O可以访问）
Interrupt/Reset Line
客观存在，但计算机系统不能直接访问
- 类比：进程只能通过syscall访问进程外的信息

CPU Reset：其他体系结构

计算机系统：状态迁移

执行指令：

如果有多个处理器？
- 可以想象成每次选一个处理器执行一条指令
- 在并发时会回答这个问题

响应中断

if(intr) goto vec;

输入和输出

与计算机系统外交换数据

计算机系统中的固件

在reset后运行的程序被称为固件

计算机系统 = 状态机

程序员如何控制计算机系统?

仅有 RESET 状态是不够的

答案:计算机系统会和 System Programmers 达成约定

如果你把代码放在某个位置，它就会被执行

随着计算机发展形成的约定

Firmware

“固件”

厂商“固定”在计算机系统里的代码
- 早期：固件是ROM
- 想升级？换芯片
Firmware的功能
- 运行程序前的计算机系统配置
  - CPU电压、内存时序、接口开关
  - 这些配置生效可能需要重启计算机
- 不严格的说，加载操作系统
  - QEMU：可以绕过Firmware直接加载操作系统RTFM

Firmware就是一段代码

BIOS启动（40年前）

即完成512字节从主引导扇区到内存的加载

cat makefile 是使用cat命令来显示makefile文件的内容

QEMU存在一个kernel选项可以绕过固件BIOS将操作系统直接加载到内核

CPU从reset开始就要开始执行firmwore的代码了

|less 通过分页显示

了解x86内存构架

A启动、中断、异常和系统调用

B内存分层体系

计算机体系结构

内存分层体系

操作系统的内存管理&地址空间、地址生成

目标

内存分配

连续内存分配

内存碎片问题

分区的动态分配

压缩式与交换式碎片整理

压缩式碎片整理

交换式碎片整理

非连续内存分配

分段

分页

页表

C虚拟内存管理技术

覆盖技术

交换技术

虚拟技术

虚拟页式内存管理

虚拟内存性能

页面置换算法

Belady现象

局部页替换算法的问题、工作集模型

工作集

全局页面置换算法

抖动问题

D进程管理

进程描述

进程的定义

进程的组成

进程的特点

进程控制结构

进程状态

进程生命期管理

进程创建

进程运行

进程等待

进程唤醒

进程结束

进程状态变化模型

进程挂起模型

线程（Thread）

为什么使用线程？

什么是线程

线程的实现

进程切换

进程控制

创建进程

加载和执行进程

等待和终止进程

进程间通信

进程互斥不同步

死锁

第8章 调度

背景

比较调度算法的准则

调度算法

先来先服务算法（FCFS）

短进程优先算法（SPN(SJF) / SRT）

最高响应比优先算法（HRRN）

轮循算法（RR）

多级反馈队列算法（MFQ）

实时任务

单调速率（RM）

截止日期最早优先（EDF）

多处理器调度

第9章同步互斥

背景

一些概念

Race Condition（竞态条件）

Atomic Operator（原子操作）

基于软件的解决方案

方法3：更高级的抽象

第10章信号量和管理

背景

信号量

第8章调度