清华大学操作系统笔记

操作系统

字数统计: 16.3k阅读时长: 58 min

 2020/03/11 

清华大学操作系统笔记

除了课程笔记外，还加入了一些补充内容

前言

B站陈渝老师清华大学 https://www.bilibili.com/video/av6538245

chap1 OS概述

功能

OS提供管理（资源角度）、控制（用户角度）和服务（应用程序角度）。

位置

硬件之上，应用软件之下。OS对外的接口是shell（GUI，CLI），内核是kernel。

组成

CPU调度、物理内存、虚拟内存、文件系统、中断处理与设备驱动。

特征

并发concurrent。在一段时间内，多个程序同时运行。需要OS的管理和调度。

与并行要区分。并行parallel：在一个时间点，多个程序同时运行。要求多CPU。
- 并发：代码的性质，是指代码逻辑上可以同时运行。
- 并行：物理运行状态。
并发和并行都可以有很多线程，就是看这些线程能不能被多个CPU执行。
共享（资源）。同时访问、互斥共享。
虚拟。OS把硬件虚拟化了，经过OS后：cpu抽象为进程，内存抽象为地址空间，磁盘抽象为文件。

此外，多道程序设计，可使每个用户觉得有一个计算机专门为他服务。
异步。程序的执行是走走停停的，但只要运行环境相同，OS保证结果要相同。

结构

单体内核。如MS-DOS，内部各个模块间通过函数调用访问，属于紧耦合方式。缺点是复杂庞大，易受攻击。
微内核。模块之间通过消息传递实现，属于松耦合方式。效率不高，但安全，体积小，易扩展。
外核。内核分为两块，一块负责和硬件打交道，另一部分和应用打交道。优点速度快，先主要存于学术界。
虚拟机。硬件资源过剩，VMM可充分利用资源。

chap2 操作系统基础操作

操作系统的启动

BIOS：基本IO处理系统，位于内存。首先会将BootLoader从DISK加载到内存0x7c00，然后跳转到0x7c00。

BootLoader：加载OS到内存，然后跳转到OS起始地址。

DISK：存放OS和BootLoader（存在DISK第一个扇区，即引导扇区，512字节）。

中断/异常和系统调用

操作系统与设备（硬件）和程序（软件）的交互

中断（源于外设）。异步。不同外设的计时器和网络的中断。
系统调用（源于应用程序）。同步或异步。应用程序主动向OS发出服务请求。
异常（源于不良应用程序）。同步。应用程序意想不到的行为，如非法指令等。

为什么需要操作系统这个中介（接口设计的原因）：

安全。应用程序不能直接访问外设，必须通过OS。因为OS内核是被信任的第三方。只有OS可执行特权指令。
封装。即提供简单接口给上层应用，屏蔽底层不同硬件的复杂细节和差异。

中断处理过程

中断表（Map查找表），根据中断表，去找到相应的服务执行。除此之外，还需保存与恢复机制，用于硬件和软件上对原正在执行应用程序的保护。具体过程如下：

硬件上。外设发生中断事件后产生中断标记，CPU根据中断标记设置不同外设的中断事件ID编号（Key）。
软件上。OS保存当前处理状态。根据Key找到中断服务程序的地址（Value），并执行。清除中断标记，然后恢复之前现场。

应用程序感受不到中断。

异常处理过程

与中断有类似地方。

异常编号
保存现场
异常处理。两种情况。
- 直接杀死该程序。程序直接退出。
- 恢复现场后，重新执行引起异常的那条指令（如除零指令）。此时，应用程序感受不到异常。

系统调用

（应用）程序访问的是高层次API接口，然后再由OS进行系统调用。

高层次API接口：

Win32 API用于Windows。
POSIX API用于UNIX，LINUX，Mac OS等。
Java API用于JVM，JVM然后再调用Win32 API或POSIX API。

应用程序执行且CPU处于用户态时，无法执行一些特殊指令和IO；应用程序执行且CPU处于内核态，可执行任何指令，如特权指令和IO。系统调用时，CPU状态会由用户态转换为内核态。

代价

执行时间上开销超过直接程序调用，但因为这些机制，使得计算机更加安全可靠。

开销：

建立中断/异常/系统调用ID与对应服务程序映射关系表。需要在初始化时建好。
除了应用程序本身堆栈，还要建立内核自己的堆栈。
为了安全考虑，需要花时间验证参数。比如验证错误，发出异常等。
内核态映到用户态的地址空间，涉及到从一个内存地方拷贝到另一个地方。更新页面映射权限。
内核态独立地址空间。TLB。

chap3 连续式内存分配

计算机体系结构及内存分层体系

CPU，内存，IO设备连接于总线。速度和容量反比。

OS内存管理**的四个任务：

抽象。使上层应用程序只需访问逻辑地址空间，屏蔽底层如物理地址空间、外设等。

注：程序看到的是逻辑地址空间，内存和硬盘看到的是物理地址空间。
保护。多个应用程序之间隔离，独立地址空间。
共享。访问相同内存，从而实现不同程序交互。
虚拟化。将暂时不需要的数据临时放在磁盘，虚拟地扩展内存大小。

OS内存管理的方法：

程序重定位
分段
分页
虚拟内存
按需分页虚拟内存

OS内存管理高度依赖于硬件：1）必须知道内存架构；2）内存管理单元MMU，硬件组件，负责处理CPU的内存访问请求。

地址空间与地址生成

地址空间

物理地址空间PA。内存，硬盘。范围0-MAXsys。
逻辑地址空间LA。应用程序。一维线性地址空间。范围0-MAXprog。

二者转换关系由OS完成。

地址生成

编译后是基于符号的逻辑地址。如函数地址等。
汇编、链接后形成新的逻辑地址。
载入（程序重定位）内存后，得到偏移后的新的逻辑地址。

LA->PA过程（CPU如何根据某个指令的LA找到其能识别的PA）：

OS方面
1. 提前建好LA-PA映射表。包含base和limit。
CPU方面。（注：CPU包含ALU、寄存器、控制器、MMU、缓存）
1. CPU中计算逻辑单元ALU发起请求，请求的参数是该指令的LA。
2. CPU中的内存管理单元MMU查找LA-PA映射表。
3. 如果找到映射关系，由CPU中的控制器向内存发起请求，请求参数是该指令在内存中的PA。
内存方面
1. 内存将该指令的内容通过总线发回给CPU

地址安全检查

每个程序在内存中有各自的一片地址空间。OS必须确保程序间相互不干扰，确保CPU要访问逻辑地址在该程序的合法地址范围内（长度为MAXprog的一个范围，即limit）。否则，返回内存访问异常给CPU。

连续内存分配

内存碎片问题

无法充分利用一些内存：

外碎片。分配单元间的未使用内存
内碎片。分配单元中的未使用内存

分区的动态分配策略

首次适配。使用找到的第一块够用的空闲内存块。

按地址排序。缺点是易产生外碎片。
最优适配。

按尺寸排序。缺点是外部碎片，重分配慢，产生很多无用的微小碎片。
最差适配。

按尺寸排序。缺点是外部碎片，重分配慢，容易使得大分区无法被分配。

以上三种比较简单，都有各自的缺点。因此在实际中，往往使用更复杂的策略。

压缩式与交换式碎片整理

如何减少碎片。

压缩式：

压缩式整理是一个内存拷贝的过程（将一段内存移动到另一块区域，也叫重定位），只能发生在程序停止、等待时。

开销很大。

交换式swap：

把等待的程序，换入换出到虚拟内存空间。

chap4 非连续式内存分配

连续内存分配缺点：

分配给一个程序的物理内存是连续的
内存利用率低
外碎片、内碎片问题

非连续内存分配优点：

一个程序的物理地址空间是非连续的
更好地内存利用和管理
允许共享代码与数据（共享库等）
支持动态加载和动态链接

如果使用非连续内存分配，如何建立虚拟地址和物理地址之间的转换？

软件方案：开销大。
硬件方案：分段和分页。

分段Segmentation

程序的分段地址空间。

更好地分离和共享。

一维逻辑地址（连续）->分段的物理地址（离散）

段：一个内存块
分段寻址方案

逻辑地址=(段号SegmentationNum，段内偏移地址address)
- 段号和段偏移分开：段寄存器+地址寄存器实现方案。如x86。
- 段号和段偏移在一起：单地址实现方案。

段表：LA段号->PA段号。段表由OS建立，存放的是一系列base和limit，会据此进行地址安全检查。

分页Paging

当前绝大多数CPU不采用分段，而采用分页。

最大区别：段的分段大小不固定。

程序的分页地址空间

帧：frame，物理页，非连续物理内存。物理内存大小固定（2的次幂）。

页：page，逻辑页，连续虚拟内存。逻辑地址大小固定（2的次幂）
页寻址方案

逻辑地址=（页号，页偏移）

物理地址=（帧号，帧偏移）

其中，页偏移=帧偏移

页表Page Table：LA->PA。页表存放的是对应的页号和帧号。由OS建立。页表还会有一些标志位（对应的物理页是否存在、可读、可写等）。

LA>PA。不是所有的页都有对应的帧，如果内存不够，用虚拟内存解决。

页表

性能问题：

空间：页表可能非常大。
时间：访问一个内存单元需要两次，一次用于获取页表项，一次用于访问数据。

性能解决方案如下，大致分为缓存（解决时间问题）和多级页表（解决空间问题）两种方案。

转换后备缓冲区TLB（快表）

Translation Look-aside Buffer，缓存页表内容。

TLB使用关联内存实现，可并行快速访问，用一个Map将页号映射为帧号。如果TLB中未存在，CPU不得不查页表，然后更新TLB。相当于空间换时间。

因此写程序时，使程序具有访问局部性，把访问集中在一个区域，可有效减少TLB的缺失，提高效率。

二级页表与多级页表

页号分为一级页号和二级页号两部分。

虽然又多了一次寻址，但是使得某些不存在映射关系的页表项可以省略。相当于时间换空间。比如一级页表中根据标志位发现映射关系不存在，则二级页表就不需要了。

推广：多级页表，树状结构。

反向页表

将映射表的Key和value对换。优点占内存小，表大小与逻辑空间大小无关。

缺点是需要的信息对调了，如何根据页号得到帧号。方案：

基于寄存器。
基于关联内存。类似TLB。但开销大
基于哈希查找。

chap5 虚拟内存

起因：内存不够用。

覆盖技术（overlay）

手动覆盖程序。按程序自身逻辑，划分为独立的模块（相互之间没有调用关系），分时的方式先后运行。例如DOS系统。覆盖发生在运行程序的内部。

时间换空间。

缺点是程序员需要负责划分和设计，编程复杂度增加。

交换技术（swap）

自动交换程序。由OS负责换入换出。交换发生在程序与操作系统之间。

缺点是交换粒度大，大小为整个程序的地址空间。

需要考虑的三个问题：

交换时间：内存快要不够时
交换区大小：必须足够放入内存映像的拷贝。
换入时的重定位：换回去后原来的地址可能变动，因此要使用动态地址映射（还是维护页表等映射关系）。

虚存技术

基本知识

更小的页粒度或段粒度导入导出到内存。

如果需要执行的指令或数据尚未在内存中（缺页或缺段），则由CPU通知OS将页面或段调入内存，再继续执行。

程序局部性原理（principle of locality）：在执行的较短时间内，指令地址和操作数分别局限于一定区域。表现为：

时间局部性：指令和数据的访问集中在较短时期内。
空间局部性：指令和数据集中在较小区域。

程序局部性好的程序，可以高效实现虚存效果。例如for循环遍历二维数据，最外层进行行循环，最内层进行列循环产生的缺页中断次数最少。

虚拟页式内存管理=页式存储管理+请求调页+页面置换

请求调页：CPU向OS发出缺页中断信号。

页面置换：换入换出。

基本过程：当一个程序运行时，只装入部分的页面。等到需要访问其他不在内存的页面时，CPU产生一个缺页中断请求，OS再将页面换入内存即可。

页表项的标志位

（见chap4）

驻留位（状态位）：用于指示该页是否已调入内存。1表示该页位于内存；0表示在外存。如果访问该页表项，将产生缺页中断。供程序访问时参考。
保护位：只读、可读写、可执行等。
修改位（改变位、脏位、写位）：用于表示该页在调入内存后是否被修改过。1表示该页被写过，0表示未被修改。由于内存中的每一页都在外存保留一份副本，因此，若未被修改，在置换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。供置换（换出）页面时参考。
访问位（读位）：记录本页在一段时间内被访问（读或写）的次数，或记录多长时间未被访问。供选择换出页面时参考（尽量换出那些最近没被访问的页面）。

缺页中断

访问页p时，发生缺页中断的处理过程：

如果内存中有空闲物理内存，则分配一物理页帧f，然后转到第4步（不需换出只需换入）；否则，转到第2步（需要先换出再换入）。
采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为q，如果该页在内存期间被修改过，则需把它写回外存。（在内存中页面被修改时，并没有也没必要写回外存。只有当该页好久没使用后，被换出时才要写回外存，即更新外存中对应的页副本）
对q所对应的页表项进行修改，把驻留位置为0（表示该页已换出）。
将需要访问的页p装入到物理页帧f中。
修改p所对应的页表项内容。把驻留位置为1，把物理页帧号置为f。（页p的虚拟地址空间LA是一开始就固定已知的，映射在外存中位置也是OS已知的，但是f的位置是比较随机产生的，因此必须要更新物理页帧号）
重新运行被中断的命令。

后备存储

Backing Store，又叫二级存储。

数据：一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）中某个位置。
代码段：映射到可执行二进制文件。
动态加载的共享程序段：映射到动态调用的库文件。
其他段：可能被映射到交换文件（swap files）。

chap6 页面置换算法

目标：减少页面换入换出次数。在局部性原理的指导下，依据历史统计数据进行预测。

页面锁定：一些常驻内存（如操作系统的关键部分或时间关键的应用）。实现方法是在页表中添加锁定标志位lock bit。

局部页面置换算法

最优页面置换算法OPT

基本思路：选择未来等待时间最长的那个页面，作为被置换页面。

需要预知未来。不实用，常用来作为基准评价其他算法好坏。

FIFO算法

基本思路：选择内存中驻留时间最长的页面并淘汰之。

维护一个链表（模拟队列），记录内存中页面。链表头驻留时间最长。链表尾时间最短。发生缺页中断时，remove链表头页面，add新的页面到末尾。

性能差，用的少。Belady现象。

Belady现象

有时会出现分配的物理页面数增加，缺页率反而提高的异常现象。

产生原因：FIFO算法没能达到“替换较少使用页面”这个目标。

最近最久未使用算法LRU

Least Recently Used。

基本思路：选择最久未被使用的页。

基于局部性原理。需要不断查找，开销比较大。

时钟算法Clock

各个页面组成环形链表，用一个指针指向某个页面。发生缺页中断时，判断指针当前页访问位（访问位由硬件自动生成，表示最近是否被访问过）。

如果该页访问位为1：则置0，指针指向链表的下一页再判断（像一个Clock）。
如果该页访问位为0：则该页应该被置换。重置该页访问位为1，并将其物理页帧号更新，指针指向下一个位置（次老的页）。

LRU的近似，对FIFO的改进。

增强时钟算法（二次机会法）

同时使用修改位（写位）和访问位（读位）来判断是否置换，以减少对硬盘的读写操作次数。是一种对Clock算法的改进版。

Used	Dirty		Used	Dirty
0	0	->	x	x
0	1	->	0	0
1	0	->	0	0
1	1	->	0	1

注：x表示要被替换。对于上一次刚写过的页（标注位为11），相当于多了第二次机会，需要指针访问两次才会被替换。

最不常用法LFU

Least Frequently Used。

基本思路：选择访问次数最少的页。

对页面设置一个访问计数器，每次访问后加1。选择计数最少的页被置换，置换后该计数器归0。

但只使用次数判断是片面的，比如一个程序可能刚开始使用次数很多，但后来就不再使用了。改进：把时间也考虑进去，如定期把计数器寄存器右移一位，定期减小次数这个值。

LRU和LFU区别：LRU考虑的是多久未访问，时间越短越好；而LFU考虑的是访问次数，访问次数越多越好。

FIFO，LRU和Clock的比较

FIFO和LRU本质上都是先进先出思路。LRU针对页面的最近访问时间来排序；FIFO针对页面进入内存的时间进行排序，没有考虑访问时间的历史信息。

但LRU算法效果虽好，但效率不高。FIFO效率最好，但效果较差。Clock算法是一个折中。

Clock算法没有记录精确的时间，使用标志位来近似模拟LRU算法，同时也保证了较高的效率，更加实用。

这些算法，都是基于局部性原理这个前提。如果局部性原理不成立，比如页面访问顺序是单调递增的1，2，3，4，5...那么不管采用哪种算法，每次访问都必然导致缺页中断。

全局页面置换算法

局部页面置换算法的问题

物理页大小对于页面置换算法效果影响很大。在实际OS中往往多个程序同时运行，且程序在不同运行阶段访问内存的特征不同。因此可以动态分配物理页帧大小，从而减少总体的缺页次数。

局部页面置换算法只在没有空闲物理内存时置换，而全局置换算法根据工作集和缺页率动态调整，可使整个系统层面缺页率降低。

工作集模型

工作集：一个进程当前正在使用的逻辑页面集合set。用W(t,deleta)表示，即当前时刻t之前deleta时间窗口中所有页面组成的集合（集合不包含重复的，集合的大小越小，程序当前的局部性越好）。

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

工作集是程序运行时固有属性；常驻集取决于OS分配给进程的物理页面数量+页面置换算法。工作集是需求，常驻集是实际。二者尽可能重合时，缺页中断最少。

工作集页置换算法

置换不在工作集的页
只要某页不属于工作集，即使没有发生缺页，也换出。

在物理页面中放哪些页取决于是否在工作集窗口内。老的页面都会被换出，确保了物理内存中始终有足够多的页存在，给其他运行程序提供更多的内存。在整个系统层面（不是单个程序层面），减少页面中断次数。

缺页率置换算法

与工作集页置换算法使用固定窗口大小不同，缺页率置换算法使用缺页率算法（PFF，Page Fault Frequency）来动态调整常驻集大小。缺页率越高，应该分配更大的常驻集（物理内存）；反之应减小常驻集。使得每个程序缺页率保持在一个合理的范围内，不高也不低。

缺页率：缺页次数/内存访问次数

缺页率影响因素：

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

优缺点：性能好，但增加了系统开销

假定给定window size=2，算法具体过程：

当发生中断时，进行如下判断

如果Tcurrent-Tlast>2（缺页率低），从工作集中移除没有在[Tlast, Tcurrent]被引用的页面；
如果Tcurrent-Tlast<=2（缺页率高），仅增加缺失页到工作集。

抖动问题

抖动thrashing：常驻集包含于工作集，造成很多缺页中断，需要频繁换入换出。

chap7 进程和线程

进程

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

程序本身是静态的（永久的）。程序由加载到内存后，再由CPU一条条执行得到动态的进程。

进程包含了一个运行程序的所有状态信息。组成：

程序的代码
程序处理的数据
程序计数器的值，指示下一条将运行的指令
寄存器的值，堆，栈
一组系统资源（如打开的文件）

进程与程序(作业)：

程序是产生进程的基础，进程是程序功能的体现
程序的每次运行构成不同的进程（比如输入数据每次可能不同）
多对多的映射关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
进程有核心态/用户态

进程特点：

动态性
并发性（与并行区别）
独立性。不同进程互不影响。页表使进程在独立地址空间运行，保障了进程间的独立性。
制约性。共享数据/资源或进程同步而产生制约。

OS为每个进程维护一个进程控制块PCB（链表），保存各种状态信息。PCB含三大类信息：

进程标识信息。如本进程标识，父进程标识，用户标识
处理机状态信息保护区。保护进程的运行现场信息：
- 用户可见寄存器：用户可见的数据、地址等寄存器。
- 控制和状态寄存器：程序计数器PC，程序状态字PSW。
- 栈指针：过程调用、系统调用、中断处理和返回时需要。
进程控制信息：调度和状态信息、进程间通信信息、存储管理信息、进程所用资源、连接信息。

进程状态

生命周期

创建。创建时机：
- 系统初始化时
- 用户请求创建
- 正在运行的进程创建
运行。内核选择一个就绪进程执行。
等待（阻塞）。三种情况：
- 请求并等待系统服务，无法马上完成
- 启动某种操作，无法马上完成
- 需要的数据没有到达。
进程只能自己阻塞自己，因为只有进程自己知道何时需要等待某种事件发生。
唤醒。三种原因：
- 需要的资源被满足
- 等待的事件达到
- 该进程的PCB插入到就绪队列
进程只能被别的进程或操作系统唤醒。
结束。四种情况：
- 正常退出（自愿的）
- 错误退出（自愿的）
- 致命错误（强制的）。如内存溢出
- 被其他进程所杀（强制的）。如kill

进程状态变化模型

进程结束前的三种基本状态：运行、就绪、阻塞。

进程挂起

目的：合理充分利用系统资源。

挂起：进程被换出到swap后，没有占用内存空间，而是处于磁盘上。分为：

阻塞挂起
就绪挂起

线程

上世纪60年代，OS中一直以进程作为独立运行的基本单位。80年代后，线程成为更小的能独立运行的基本单元。

why

程序设计时，多进程方案开销较大。需要创建进程、销毁进程、进程间通信IPC等等。

多线程方案：1）线程实体之间可以并发执行；2）实体之间共享相同地址空间。

what

定义：进程中的一条执行流程。

进程负责资源管理，线程负责执行。线程=进程-共享资源

线程控制块TCB。

优点：

一个进程可存在多个线程
可并发执行
可共享地址和文件等资源

缺点：

由于资源共享，一个线程崩溃，会导致其他线程也崩溃

应用：Chrome浏览器为了高可靠，采用多进程方式打开多个网页；高性能计算为了效率考虑，往往采用多线程方案。

多个线程具有各自独立的PC、寄存器、堆栈（这些资源必不可少，以确保相互是独立运行的），但共享代码段、数据段、文件等资源。

线程与进程比较：

进程是资源分配单位，线程是CPU调度单位
进程具有一个完整的资源平台，线程只独享必不可少的资源
线程同样具有就绪、阻塞和执行三种基本状态，同样可以相互转换，同样可以并发执行。
线程能减少并发执行的时间和空间开销：
- 线程创建时间更短（不用创建那么多资源）
- 线程终止时间更短（不用考虑其他资源释放问题）
- 同一进程内线程切换时间更短（各线程拥有同一个页表，切换进程时需要切换页表）
- 同一进程内各线程共享内存、文件资源、代码段、数据段等资源（但也有独立的堆栈、寄存器、PC），可直接进行不通过内核的通信（直接通过内存地址通信）

how

线程的实现

用户线程：在用户空间实现（应用程序来管理）

POSIX Pthreads，Mach C-threads，Solaris threads

TCB为该进程私有，由用户级线程库完成。由一组用户级线程库完成线程创建、终止、切换、同步和调度等，OS内核不参与也感知不到线程存在。OS只能通过该进程来管理资源等。

缺点：
- 如果一个线程发起系统调用（如读一个大文件）而阻塞，则整个进程在等待（因为OS不知道线程的存在，它会直接把进程阻塞）
- 如果一个运行的线程不主动交出CPU使用权，则该进程中其他线程无法运行
- 由于时间片直接分配给进程，故多线程执行时，每个线程得到的时间片较少，执行较慢。
内核线程：在内核中实现（操作系统来管理）

Windows，Linux，Solaris

TCB由内核管理。由OS内核负责线程创建、终止、切换和管理，粒度更小。

优缺点：
- 由OS负责管理，需要用户态/内核态不断切换，因此开销大
- 如果某个线程被阻塞，不会影响其他线程
- 时间片分配给线程，多线程的进程获得更多的CPU时间。
轻量级进程：在内核中实现，支持用户线程

Solaris

比较灵活但复杂

用户线程与内核线程对应关系：多对一，一对一，多对多。

上下文切换

进程上下文（存储于PCB中）：寄存器（PC，SP，...），CPU状态等

停止当前运行进程，并调度其他进程：

切换前必须存储进程上下文
必须能够恢复上下文
必须快速

OS将PCB放置在一个合适的队列中：

就绪队列
等待IO队列（每个设备的队列）
僵尸队列

进程控制

创建，加载和执行进程

Windows：CreateProcess(filename)

Unix：fork/exec

fork()把一个进程复制成两个进程（创建子进程）：parent(old PID)，child(new PID)
exec()用新程序来重写（加载）当前进程内容（比如用新的程序替换掉fork复制来的的代码、堆栈等），但是子程序的PID保持不变。

/*
* 子进程返回pid为0，父进程返回pid为子进程ID
* 在子进程中如果要获取pid，使用getpid()
*/

int pid=fork();	// 创建子进程
if(pid==0){ 		// 子进程
  exec("program",argc,argv0,argv1,...);
  printf("I will not execute!");
}else{ // 父进程
  wait();
}

如果for循环三次，fork会产生7个子进程（共8个）。fork开销昂贵。而99%情况下，调用fork()后会调用exec()，因此fork()中内存复制没有作用，子进程也会关闭打开的文件和连接。解决方法：

windows只采用一个系统调用
vfork()创建进程时，不再复制。子进程几乎立即调用exec()。
现在使用Copy on Write写时复制技术。

等待和执行进程

父进程调用wait():

父进程睡眠，等待子进程exit()。
父进程帮助回收子进程的资源。wait()执行后，子进程才算退出状态。

子进程调用exit():

传递一些参数，如子进程pid，返回值等。
关闭所有打开的文件，连接等
释放内存
释放大部分支持进程的操作系统结构
检查是否父进程是存活的：
- 如果是。它保留结果直到父进程需要它（父进程调用wait()），这种情况下，进程没有真正死亡，进入僵尸状态。
  
  exit执行完毕，wait尚未执行期间：僵尸状态，等待被父进程回收。每个进程结束时都会经历一段。
- 如果没有。它释放所有数据结构（相当于由OS的init进程（pid=1，根进程）以父进程的身份负责调用wait()释放资源），进程死亡。

其他相关概念：孤儿进程，僵尸进程，守护进程

chap8 CPU调度

背景

CPU调度：从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程。

内核运行调度程序的条件（满足一条即可）：

一个进程从运行切换到阻塞
一个进程被终结了

不可抢占（早期OS策略）

调度程序必须等待事件结束

可以抢占（当前OS）

调度程序在中断被响应后执行
当前进程从运行切换到就绪，或者一个进程从等待切换到就绪

调度原则

程序在CPU突发和IO中交替。

比较调度算法的准则

CPU使用率。CPU处于忙状态所占时间的百分比。
吞吐量。单位时间内完成的进程数量。
周转时间。一个进程初始化到结束，包括等待时间。

执行的时间+等待别的程序运行完的时间（队列前面的程序总执行时间）
等待时间。进程在就绪队列中的总时间。
响应时间。发出请求到被响应花费的总时间（比如鼠标响应的时间）。

一些准则很难平衡。比如桌面系统追求交互低延迟（响应时间），服务器追求带宽（吞吐量）。

低延迟：打开水龙头立刻出水

高吞吐：打开粗水管，浇花

公平的目标

每个进程占相同的CPU时间。公平通常会增加平均响应时间。

通用调度算法

FCFS 先来先服务

First Come, First Served

如果进程阻塞，队列中下一个得到CPU

缺点：

平均等待时间波动大（跟队列中进程顺序有关）
花费时间少的任务可能在花费时间长的任务后面
可能导致IO和CPU之间的重叠处理

CPU密集型进程会导致IO设备闲置，而此时IO密集型的进程也只能等待

SPN 短进程优先

Shortest Process Next 按预测完成时间来将任务入队。不可抢占。

变种1：SRT（Shortest Remaining Time，最短剩余时间）是SPN的可抢占版本。下一个执行程序=min{当前程序剩余时间，新的程序预估时间}

最优平均等待时间。

缺点：

连续的短任务会使长任务饥饿（虽然平均时间最少，但缺乏公平性）
怎么预知未来（程序的执行时间）
- 询问用户。如果用户欺骗就杀死进程
- 根据历史信息预测

HRRN 最高响应比优先

Highest Response Ratio Next。SPN变种2。

Ratio=(等待时间+执行时间)/执行时间

选择Ratio最高的进程。不可抢占，防止无限期推迟。

但缺点依然需要预知未来。

Round Robin 轮循

使用时间片和抢占来轮流执行，公平。时间片中断

额外的上下文切换
时间片设置如果过大：等待时间过长，极限情况退化为FCFS；时间片设置过小：反应迅速，但不断切换开销较大。因此，需要设置一个合适大小的时间片。

Multilevel Feedback Queues 多级反馈队列

优先级队列中的轮循

就绪队列被划分为独立的队列，如前台交互，后台批处理。针对每个队列，设置不同的调度算法，如前台使用RR，后台使用FCFS。

不同队列之间，可以采用固定优先级（可能导致饥饿），也可以采用时间切片。

一个进程还可以在不同优先级队列中移动，动态调整，根据反馈信息。比如CPU密集型任务优先级下降很快，IO密集型停留在高优先级。

用户级别公平，而不是进程级别公平（用户拥有进程数量不同）。

用于科学计算等多用户。

实时系统调度

实时系统

确定性，可预测性。

分为强实时系统（比如火箭发射）和弱实时系统（比如播放视频）。

周期任务。使用率=执行时间/周期

单调速率 RM

最佳静态优先级调度

通过执行周期安排优先级（实时系统的执行时间和周期一开始就确定了）

周期越短优先级越高

执行周期最短的任务

截止日期最早优先 EDF

最佳动态优先级调度

deadline越早优先级越高（任务执行过程会影响优先级确定）

执行deadline最早的任务

多处理器调度

与通用调度和实时调度采用单CPU不同，手机电脑等多CPU调度。两个问题：在哪个CPU上执行，多CPU如何负载均衡。

对称多处理器（SMP）

每个处理器运行自己的调度程序
需要在调度程序中同步

优先级反转

可能发生在任何基于优先级的可抢占调度机制中，高优先级任务等待低优先级任务。（比如：低优先级任务有一块共享资源正在处理，而高优先级任务则需要等待这块共享资源处理完成才执行，此时就发生了别的低优先级任务先执行的情况。）

解决：

优先级继承。低优先级任务如果在执行高优先级任务的共享资源时，其优先级动态得到提升。
优先级天花板。”资源优先级“和”所有可能锁定该资源的任务优先级中最高的那个任务优先级“相同。（最开始会统计所有任务需要的资源）本质和优先级继承类似。

chap9 互斥

背景

独立的线程：调度顺序不重要。确定性+可重现

合作线程：调度顺序重要。不确定性+不可重现。bug可能会间歇性发生，调试难度高。

合作优点：

共享资源
加速
- IO操作和计算可以重叠
- 多处理器，程序分为多个部分并行执行
模块化
- 大程序分解为小程序
- 使系统易于扩展

竞态条件：结果依赖于并发执行或事件的顺序/时间

死锁：两个以上进程，互相等待完成特定任务（或特定资源），最终没法完成自己的任务。

临界区 Critical section

临界区：访问共享资源的那段代码

临界区属性：

互斥：同一时间临界区中最多只存在一个线程。
前进原则Progress：如果一个进程想要进入临界区，最终会成功。
有限等待：线程等待有限时间进入临界区。
无忙等（可选）：如果一个进程在等待进入临界区，可能被挂起。（忙等busy-waiting：是指比如利用while死循环，通过不断占用CPU资源的方式来等待）

使用加锁和解锁来解决。加锁和解锁操作必须是原子操作。

实现方式1：禁用硬件中断

没有中断，没有上下文切换，因此没有并发。

进入临界区：禁用中断（不允许别的进程打断）
离开临界区：开启中断

缺点：

整个系统都必须停下来（比如IO等操作也必须等待，会影响系统正常工作）。临界区比较长时，影响更大。
仅限于单CPU，多CPU时无法使用

实现方式2：基于软件的解决方案

使用两个共享数据项

1 2	int turn; // 表示该谁进入临界区 bool flag[]; // 指示进程是否准备好进入临界区

缺点：忙等，CPU占用时间很大。复杂。

没有硬件保证情况下，无真正软件解决方案。Peterson算法也需要原子的LOAD和STORE指令。

实现方式3：更高级的抽象

基于硬件原子操作。

硬件提供了一些原语，比如中断禁用，原子操作指令等。操作系统提供更高级的编程抽象来简化并行编程，如锁、信号量等，从硬件原语中构建。

OS提供特殊原子操作帮助实现互斥（二者之一就可以）：

Test-and-set测试和置位
- 从内存中读取值
- 测试该值是否为1（然后返回真或假）
- 内存值置位1
交换
- 交换内存中的两个值

优点：

适用于单处理器或共享内存的多处理器中任意数量的进程
简单并容易证明
可支持多临界区

缺点：

如果实现采用忙等，则会消耗CPU时间
可能导致饥饿
死锁（通过优先级反转解决方法来解决）

Chap10 同步

锁可以帮助实现互斥，但是如果需要同步，或者需要临界区中多个进程存在（比如只进行读操作），则需要一些其他的东西辅助——信号量等。

信号量 Semaphore

类似多条铁路的信号灯，控制多条铁路上火车的数量。

信号量相当于锁的扩展概念，二进制信号量=锁

信号量原理

一个整型（sem）表示，初始值是非负值，两个原子操作：

P()：sem-1。

如果sem<0，阻塞；否则继续。

（P操作类似于获取锁，然后判断后，需要负责一些调度工作）
V()：sem+1。

如果sem<=0，唤醒一个等待的P（队列中选一个）

（V操作类似于释放锁，然后判断后，需要负责一些调度工作）

信号量缺点

开发代码困难增加
容易出错
- 使用的信号量已被另一个线程占用
- 忘记释放信号量
不能处理死锁问题

生产者消费者问题

一个线程等待另一个线程处理事情，这时互斥（锁机制）是不够的，必须引入同步。比如有界缓冲区的生产者-消费者问题：

一个或多个生产者产生数据并放在一个缓冲区内。缓冲区为空时，正常生产；缓冲区满时，必须等待消费者（调度/同步约束）
一个或多个消费者每次从缓冲区取出数据。缓冲区满时，正常消费；缓冲区空时，必须等待生产者（调度/同步约束）
在任何时间只有一个生产者或消费者可以访问缓冲区（互斥）

每个约束对应一个信号量：

一般信号量 emptyBuffers=new Semaphore(n)
一般信号量 fullBuffers=new Semaphore(0)
二进制信号量互斥 mutex=new Semaphore(1)

// 初始状态buffer为空
// 所以condition1初值n表示生产者当前还可以生成n次，condition2初值0表示当前只能等待
class RoundBuffer{
	mutex=new Semaphore(1);
	condition1=new Semaphore(n); // n is size of buffer
	condition2=new Semaphore(0);
}

RoundBuffer::Deposite(c){
	condition1->P(); // if buffer still has some place

	mutex->P();
	addStaff(c);
	mutex->V();

	condition2->V();
}

RoundBuffer::Remove(c){
	condition2->P(); // if buffer is not empty

	mutex->P();
	removeStaff(c);
	mutex->V();	

	condition1->V();
}

注意：P操作会产生阻塞，因此不能换顺序Deposite()中前两条语句顺序，否则会造成死锁。

管程 Monitor

管程最早出现是针对编程语言并发设计的，而不是为了OS

一个锁：指定临界区
0或多个条件变量：等待/通知信号量用于管理并发访问共享数据（与信号量类似，一个等待操作Wait，一个信号操作Signal）

目的：分离互斥和条件同步的关注

注意与信号量区别的地方：wait一定做加操作，但signal不一定做减操作。

生产者消费者问题

// define max buffer size as n
class RoundBuffer{
	int count=0;	// current number of staff
	Lock lock;
	Condition condition1;
	Condition condition2;
}

RoundBuffer::Deposite(c){
	lock.acquire();

	while(count==n){ // Hansen-style, use 'if' for Hoare-style
		condition1.wait(lock);
	}

	addStaff(c);
	++count;
	condition2.signal();

	lock.release();	
}

RoundBuffer::Remove(c){
	lock.acquire();

	while(count==0){
		condition2.wait(lock);
	}

	removeStaff(c);
	--count;
	condition1.signal();

	lock.release();
}

注意：进入管程的线程必须只有一个，因此lock放在了函数的开头和结尾的地方。

经典同步问题

读者-写者问题

动机

共享数据的访问
两种使用者
- 读者：不需要修改数据
- 写者：读取和修改数据
问题约束：
- 允许同一时间多个读者，但在任何时候只有一个写者
- 当没有写者时读者才能访问数据
- 当没有读者和写者时写者才能访问数据
- 任何时候只能有一个线程可以操作共享变量

两类：

基于读者优先（上面的伪代码属于这一类）：只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断，写者始终被阻塞。
基于写者优先。一旦写者就绪，写者就会尽可能快地执行写操作。如果写者源源不断，读者始终处于阻塞。

基于信号量、读者优先方法

class BoundBuffer{
	int numReader=0;
	numReaderMutex=new Semaphore(1);
	documentMutex=new Semaphore(1);	// 第一个读者（或最后一个），以及写者必须互斥使用文档
};

BoundBuffer::read(){
	numReaderMutex->P();
	if(numReader==0) documentMutex->P();
	++numReader;
	numReaderMutex->V();

	readData();	// read until is done

	numReaderMutex->P();
	--numReader；
	if(numReader==0) documentMutex->V();
	numReaderMutex->P();
}

BoundBuffer::write(){
	documentMutex->P();

	writeData(); // write until finish

	documentMutex->V();
}

基于管程、写者优先方法

哲学家就餐问题

class Philosopher{
public:
    void philosopher(int i);

private:
    void think(){};
    void eat(){};
    void take_forks(int i);
    void put_forks(int i);
    void test_take_left_right_forks(int i);

    static const int N=5;                           // 哲学家人数
    enum class state{EATING, WAITING, THINKING};    // 3种状态
    state states[N];                                // 哲学家的状态
    semaphore s[N];                                 // 均初始化为0，用于同步调度
    semaphore mutex;                                // 用于互斥操作

};

void Philosopher::philosopher(int i) {
    while(true){
        think();
        take_forks(i);
        eat();
        put_forks(i);
    }
}

// 原子操作：要么同时拿两把叉子，要么进入等待
void Philosopher::take_forks(int i) {
    mutex.P();

    states[i]=state::WAITING;
    test_take_left_right_forks(i);

    mutex.V();

    s[i].P();   // 没有叉子便阻塞
}

// 试图拿两把叉子
void Philosopher::test_take_left_right_forks(int i) {
    if(states[i]==state::WAITING&&states[(i-1+N)%N]==state::THINKING&&states[(i+1)%N]==state::THINKING){
        states[i]=state::EATING;
        s[i].V();   // 有叉子，所以通知自己不用阻塞
    }
}

// 原子操作：同时放两把叉子，同时将身边等待的哲学家唤醒
void Philosopher::put_forks(int i) {
    mutex.P();

    states[i]=state::THINKING;
    test_take_left_right_forks((i-1+N)%N);
    test_take_left_right_forks((i+1)%N);

    mutex.V();
}

chap11 死锁和IPC

死锁

死锁问题

当两个以上的运算单元，双方都在等待对方停止执行，以取得系統资源，但是沒有一方提前退出时，发生死锁。

可重复使用的资源

一个时间只能一个进程使用且不能被删除
进程释放资源后可被重用
处理器，IO通道，主和副存储器，设备和数据结构，如文件，数据库和信号量
如果每个进程拥有一个资源并请求其他资源，死锁可能发生

资源分配图（有向图），顶点V表示进程和资源实例，有向边E表示资源请求和资源占用关系。

如果图中不包含资源->没有死锁
如果图中包括循环->
- 如果每个资源类只有一个实例，那么死锁
- 如果每个资源类有几个实例，可能死锁

死锁特征（四个必要条件）

互斥：在一个时间只能有一个进程使用资源
持有并等待：进程保持至少一个资源，正在等待获取其他进程持有的额外资源
无抢占：一个资源只能被进程执行完后自动释放
循环等待：等待进程集合出现”环“

处理方法

鸵鸟

出现死锁的概率很小，且预防或恢复死锁开销太大，因此大多OS（比如UNIX）选择忽略这个问题，这种策略称之为鸵鸟策略。

预防

（约束最强）

思路：打破其中一个必要条件

打破互斥：不太可行，实际中必须同时用到同步和互斥。
打破持有并等待：进程要么持有所有资源，要么等待。（类似哲学家就餐必须同时拿起两个叉子问题）

缺点是资源利用率低，可能发生饥饿。而实际中进程在不同运行阶段需要的资源往往是不同的。
打破抢占：比较强势，也会破坏互斥
打破循环等待：对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请。

在实际OS中用的少，在嵌入式OS中用的比较多，因此其资源类型有限。

避免

需要系统一些额外先验信息提供。如果进程需要资源可能会造成死锁，则不分配给该进程资源。

思路：

需要每个进程声明它可能需要的类型资源的最大数目（先验信息）
限定分配资源的数量（不能超过进程需求的最大数量）
动态检查资源分配状态，不允许出现环形等待。（注意环形等待不一定会造成死锁，但此时已经不安全了）

银行家算法

前提条件：

多个实例
每个进程必须最大限度利用资源
当一个进程请求一个资源，就不得不等待
当一个进程获得所有资源就必须在一段有限时间（执行完后）释放它们。

目的：尝试找到一个进程/线程理想执行时序，如果找不到，则该系统状态为不安全（但不表示一定是死锁），拒绝给其分配资源。

安全状态判断算法（找到一个进程，其所需小于剩余的资源，然后分配。分配后回收这个进程的所有资源。并不断循环直到所有的进程均能被满足要求，则该进程序列就是安全的。否则是不安全的）：

算法主体：

检测

（与死锁恢复结合使用）

允许系统进入死锁。定期进行检测。

死锁检测算法与安全状态判断算法类似，复杂度O(mxn^2)，因此实际OS中很少使用银行家算法、死锁检测算法等。

恢复

（约束最弱）

终止所有死锁进程
一个时间内终止一个进程直到死锁消除
按顺序终止进程：如进程优先级、进程占用的资源、进程运行的时间、进程完成需要的资源等

IPC

概述

通信模型

如果两个进程想通信，需要：

之间建立通信链路

通信链路实现：
- 物理（如共享内存，硬件总线）
- 逻辑（如逻辑属性）
通过send/receive交换消息

直接与间接通信

直接通信：打电话

进程必须正确命名对方
通信链路属性：
- 自动建立链路
- 一条链路对应一对进程
- 每对进程之间只有一个链接存在
- 链接是单向的，但通常为双向

间接通信：让朋友捎口信（第三方，kernel）

定向从消息队列接收消息
- 每个消息队列都有一个唯一的ID
- 共享同一个消息队列
通信链路属性：
- 共享同一个消息队列
- 链接可以与许多进程相关联
- 每对进程可以共享多个通信链路
- 连接可以单向或双向

阻塞与非阻塞

消息传递：

阻塞（同步）
- 发送被阻塞，直到消息被接收
- 接收被阻塞，直到消息可被获得
非阻塞（异步）
- 发送消息后直接继续进行
- 直接接收消息（即使是空消息）

在不同情况下各有用途

通信链路缓冲

缓存容量大小：

0容量

发送方必须等待接受方（类似阻塞式消息传递）
有限容量

发送方必须等待，如果队列满（同理，接收方必须等待，如果队列为空）
无限容量

发送方不需要等待（只是理论上。如果没有数据，接收方返回错误信息）

信号

软件级的”中断“，用于通知事件处理。例子：SIGFPE，SIGKILL，SIGUSER1，SIGSTOP，SIGCONT

接收到信号后会发生什么？

catch：指定信号处理函数被调用（一般运行后，回到被打断的程序继续继续执行）
ignore：依靠操作系统的默认操作
- 例子：abort，memory dump，suspend or resume process
mask：闭塞信号因此不会传送
- 可能是暂时的（当处理同样类型的信号）

缺点：不适合传递数据，信号本身只是很小的值

优点：异步打断，效率高

详细过程（需要系统调用，并修改原始堆栈）：

编程参考：Communication between two process using signals in C

管道

1	ls\|more // unix管道重定向

定义：是指用于连接一个读进程和一个写进程，以实现它们之间通信。写进程在管道的尾端写入数据，读进程在管道的首端读出数据。

半双工，具有固定的读端和写端。当一个管道建立时，会创建两个文件文件描述符，要关闭管道只需将这两个文件描述符关闭即可。如果需要双向通信，则需两个管道。

子进程从父进程继承文件描述符（通过父进程帮子进程建立好通道）

缺点：

如果进程间没有亲属关系（父子关系或子子关系），管道无法使用。
数据是字节流，而不是结构化数据。因此需要额外解析工作。
管道buffer是有限的，来不及处理时有可能被阻塞

#include <iostream>
#include <unistd.h>

int main() {
    // create 2 pipes and check
    int pipe1[2];   // parent to child
    int pipe2[2];   // child to parent
    if (pipe(pipe1) == -1) {
        std::cerr << "unable to create pipe1\n";
        return 1;
    }
    if (pipe(pipe2) == -1) {
        std::cerr << "unable to create pipe2\n";
        return 1;
    }

    // create child process
    int pid = fork();
    if (pid < 0) {
        std::cout << "error occured\n";
    } else if (pid == 0) { // child process
        close(pipe2[0]);    // close pipe2 read end
        close(pipe1[1]);    // close pipe1 write end

        char str2[] = "Hello, I am child";
        write(pipe2[1], str2, sizeof(str2));
        std::cout << "child send: " << str2 << std::endl;

        char buff[50];
        read(pipe1[0], &buff, sizeof(buff));
        std::cout << "child receive: " << buff << std::endl;
    } else { // parent process
        close(pipe1[0]);    // close pipe1 read end
        close(pipe2[1]);    // close pipe2 write end

        char str1[] = "Hi, I am parent";
        write(pipe1[1], str1, sizeof(str1));
        std::cout << "parent send: " << str1 << std::endl;

        char buff[50];
        read(pipe2[0], &buff, sizeof(buff));
        std::cout << "parent receive: " << buff << std::endl;
    }

    return 0;
}

编程参考：

消息队列

在内核中存放一个消息队列，按FIFO管理消息（但进程读取消息不一定要按FIFO顺序，根据消息类型读即可）。

优点：

可以实现多个不相关进程间传递数据

缺点：

消息队列buffer也是有限的，会出现阻塞情况。

编程参考：IPC using Message Queues

共享内存

定义：通过内存管理，把同一块物理地址映射到不同进程的地址空间中。

之前几种数据间接通信方式，共享内存属于直接通信方式。

优点：快速，高效，没有数据复制，没有系统调用干预。

缺点：必须同步互斥机制保障（程序员提供，类似生产者消费者模式）

编程参考：IPC through shared memory

socket机制

《网络原理》课讲。

tcp协议栈实现在内核中。

chap12 文件系统

基本概念

文件系统和文件

文件系统：一种用于持久性存储的系统抽象（与内存不同）

功能：

分配文件磁盘空间（硬件层面）
- 管理文件块（类似PCB，TCB）
- 管理空闲空间
- 分配算法
管理文件集合（用户层面）
- 定位文件及内容
- 命名：通过名字找到文件的接口
- 最常见：分层文件系统
- 文件系统类型（组织文件的不同方式）
提供便利及特征
- 保护：分层来保护数据安全
- 可靠性/持久性：保持文件的持久即使发生崩溃，媒体错误，攻击等。

文件：文件系统中一个单元的相关数据在OS中的抽象。

文件头（文件块）：保存文件信息，属性

文件描述符

1
2
3

fileDescriptor=open(name, flag); // 返回文件描述符，整型
data=read(fileDescriptor, ...);
close(fileDescriptor);

文件描述符，与文件表中该文件的索引关联。用于帮助OS找到该文件。

需要元数据管理打开文件：

文件指针：指向最近一次读写位置，每个打开了这个文件的进程都有这个指针
文件打开计数：记录文件打开次数
文件磁盘位置：缓存数据访问信息
访问权限：每个程序访问模式信息

文件系统中所有的操作都是在整个块空间进行的。如getc()，putc()即使每次访问1字节数据，也会缓存目标数据4096字节（块大小4K）。

访问数据模式：

顺序访问
随机访问
基于内容访问：通过特征。如数据库是建立在索引内容的磁盘访问，需要高效的随机访问。

文件别名

硬链接：多个文件项指向同一个文件。

有一个引用计数，当所有的链接都删除后，该文件才真正被删除。

软链接：以”快捷方式“指向其他文件。（存的是文件路径）

如果使用链接，必须保证没有循环，几种可行方法：

只允许链接到文件，不允许在子目录链接
每增加一个新的链接都用循环检测算法确定是否合理
限制路径可遍历文件目录的数量

文件系统种类

硬盘文件系统。FAT，NTFS，EXT。
数据库文件系统。WinFS。
日志文件系统
网络/分布式文件系统。NFS，SMB，AFS，GFS。
特殊/虚拟文件系统

分布式文件系统：

文件可通过网络共享
- 文件位于远程服务器
- 客户端远程挂载服务器文件系统
- 系统文件访问转换为远程访问
问题
- 客户端上用户辨别复杂
- NFS不安全
- 一致性问题
- 错误处理模式

虚拟文件系统

上层：虚拟（逻辑）文件系统。抽象统一访问的接口，屏蔽底层不一致性。

底层：特定文件系统模块

卷控制块（Unix: "superblock"）
- 每个文件系统只有一个
- 文件系统的详细信息
- 块、块大小、空闲块、计数/指针等
文件控制块（Unix: "vnode" or "inode"）
- 每个文件一个
- 文件详细信息
- 许可、拥有者、大小、数据库位置等
目录节点（Linux: "dentry"）
- 每个目录项一个（目录和文件）
- 树型数据结构
- 指向文件控制块、父节点、项目列表等

当需要时，从磁盘加载到内存。

数据块缓存

编程时考虑cout<<""比cout<<endl更快速。减少对磁盘的访问次数

数据块按需读入内存
- 预读：预先读取后面的数据块
数据块使用后缓存
- 延迟写入
缓存方式
- 磁盘块缓存
- 页缓存（类似页置换算法，只不过是IO）

打开文件的数据结构

打开文件描述
- 每个被打开的文件一个
- 文件状态信息
- 目录项，当前文件指针，文件操作设置等
打开文件表
- 一个进程一个
- 一个系统级的
- 每个卷控制块也会保存一个列表
- 如果有文件被打开将不能被加载

文件分配

如何为一个文件分配数据块，兼顾小文件和大文件

方式：

连续分配
链式分配
索引分配

指标：

高效：如存储利用（外部碎片），空间利用率
表现：如访问速度

连续分配

文件头指定起始块和长度（像一个定长数组）

优点：

文件读取表现好
高效的顺序和随机访问（类似数组）

缺点：

碎片（类似连续内存分配造成碎片问题）
文件扩展增长问题（预分配？按需分配？）

分配策略：

与连续内存的分区的动态分配策略类似。

链式分配

文件块包含了到第一块和最后一块的指针。链表。

优点：

创建、增大、缩小很容易
没碎片

缺点：

不能真正的随机访问
可靠性（如果破坏一个链，整个文件就不行了）

索引分配

文件头包含了索引数据块（非数据数据块），包含了所有到文件数据块的指针列表。

优点：

创建、增大、缩小很容易
没碎片
支持直接访问

缺点：

存储索引的开销
文件大的时候，索引块也需要很大。那索引块本身如何组织？（禁止套娃）链式索引、多级索引。

空闲空间列表

创建新文件时必须快速查找空闲区域。

创建新文件时，需要保持一致（尽量防止电脑突然掉电使得不一致出现）：

在磁盘设置bit[i]=1（表示占用）
分配block[i]
在内存中设置bit[i]=1

为快速查找，可以使用位图列表（数组）、链式列表、分组列表等。

多磁盘管理 RAID

磁盘通过分区最大限度减小寻道时间

一个分区是一个柱面集合
每个分区是逻辑上独立的磁盘

使用多个并行磁盘来增加

吞吐量（通过并行）
可靠性和可用性（通过冗余）

RAID——冗余磁盘阵列

数据块分成多个子块，存储在独立的磁盘中（为了并行）
- 和内存交叉类似
通过更大的有效块来提供更大的磁盘带宽
可靠性成倍增长（加一个冗余磁盘，起到镜像作用）
读取性能线性增加
- 向两个磁盘写入，从任何一个读取
数据块级磁带配有专用奇偶校验磁盘（RAID4）
- 允许从任意一个故障磁盘中恢复
- 但是奇偶校验磁盘成为系统瓶颈，需要频繁读写
RAID5把奇偶校验磁盘均分到各个磁盘中。各个磁盘兼顾并行和冗余，既高效又可靠。
RAID5每个条带块只有一个奇偶校验块，因此只允许一个磁盘错误。而RAID6有两个冗余块。

磁盘调度

寻道时间。开销最大，必须减少

旋转延迟

访问时间

寻道策略：

FCFS。性能差，磁臂粘着。
最短服务优先。
- 选择从当前位置移动最少的磁道（最短寻道时间）
- 饥饿现象，不公平
SCAN法（电梯算法）。
- 在一个方向移动，直到到达该方向最后的磁道，再调换方向。
C-SCAN改进版C-LOOK
- 到达该方向最后一个请求处，立即反转
N-step-SCAN
- 分为N个子队列。先按FCFS处理这些子队列，每个子队列按SCAN处理。（两种方法结合）

原文作者：GJGJH

原文链接：https://gjgjh.github.io/%E6%B8%85%E5%8D%8E%E5%A4%A7%E5%AD%A6%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0.html

发表日期：March 11th 2020, 7:43:25 am

更新日期：February 2nd 2022, 7:37:38 pm

Next Post

C++面试题
Previous Post

设计模式笔记(下)

CATALOG

1. 清华大学操作系统笔记

清华大学操作系统笔记

清华大学操作系统笔记

前言

chap1 OS概述

功能

位置

组成

特征

结构

chap2 操作系统基础操作

操作系统的启动

中断/异常和系统调用

中断处理过程

异常处理过程

系统调用

代价

chap3 连续式内存分配

计算机体系结构及内存分层体系

地址空间与地址生成

地址空间

地址生成

地址安全检查

连续内存分配

内存碎片问题

分区的动态分配策略

压缩式与交换式碎片整理

chap4 非连续式内存分配

分段Segmentation

分页Paging

转换后备缓冲区TLB（快表）

二级页表与多级页表

反向页表

chap5 虚拟内存

覆盖技术（overlay）

交换技术（swap）

虚存技术

基本知识

页表项的标志位

缺页中断

后备存储

chap6 页面置换算法

局部页面置换算法

最优页面置换算法OPT

FIFO算法

Belady现象

最近最久未使用算法LRU

时钟算法Clock

增强时钟算法（二次机会法）

最不常用法LFU

FIFO，LRU和Clock的比较

全局页面置换算法

局部页面置换算法的问题

工作集模型

工作集页置换算法

缺页率置换算法

抖动问题

chap7 进程和线程

进程

进程状态

生命周期

进程状态变化模型

进程挂起

线程

why

what

how

上下文切换

进程控制

创建，加载和执行进程

等待和执行进程

chap8 CPU调度

背景

调度原则

通用调度算法

FCFS 先来先服务

SPN 短进程优先

HRRN 最高响应比优先

Round Robin 轮循

Multilevel Feedback Queues 多级反馈队列

Fair Share Scheduling 公平共享调度