操作系统思维导图模板_ProcessOn思维导图、流程图

21.死锁的处理

预防死锁

破坏互斥条件

将临界资源改造为可共享使用的资源（如SPOOLing技术）

缺点：可行性不高，很多时候无法破坏互斥条件

破坏不剥夺条件

方案一，申请的资源得不到满足时，立即释放拥有的所有资源

方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）

缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿

破坏请求和保持条件

运行前分配好所有需要的资源，之后一直保持

缺点：资源利用率低；可能导致饥饿

破坏循环等待条件

给资源编号，必须按编号从小到大的顺序申请资源

缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

避免死锁

什么是安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。

什么是系统的不安全状态，与死锁有何联系

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有的进程都无法顺利的执行下去。如果有进程提前归还了一些资源，系统也有可能重新回到安全状态。

如何避免系统进入不安全状态--银行家算法

检测和解除

死锁的检测

数据结构：资源分配图

两种结点

进程结点

资源结点

两种边

进程结点——>资源结点（请求边）

资源节点——>进程结点（分配边）

死锁检测算法

依次消除与不阻塞进程相连的边，直到无边可消

注：所谓不阻塞进程是指其申请的资源数还足够的进程

死锁定理：若资源分配图是不可完全简化的，说明发生了死锁

死锁的解除

资源剥夺法

撤销进程法（终止进程法）

进程回退法

22.内存的基础知识

什么是内存，有何作用

存储单元、内存地址的概念和联系

按字节编址vs按字编址

进程运行的基本原理

指令的工作原理

操作码+若干参数（可能包含地址参数）

逻辑地址（相对地址）vs 物理地址（绝对地址）

从写程序到程序运行

编辑源代码文件

编译

由源代码文件生成目标模块（高级语言“翻译”为机器语言）

链接

由目标模块生成装入模块，链接后形成完整的逻辑地址

装入

将装入模块装入内存，装入后形成物理地址

三种链接方式

静态链接

装入前链接成一个完整装入模块

装入时动态链接

运行前边装入边链接

运行时动态链接

运行时需要目标模块才装入并链接

三种装入方式

绝对装入

编译时产生绝对地址

可重定位装入

装入时将逻辑地址转换为物理地址

动态运行时装入

运行时将逻辑地址转换为物理地址，需设置重定位寄存器

23.内存管理

内存空间的分配与回收

连续分配管理方式

单一连续分配

固定分区分配

动态分区分配

非连续分配管理方式

基本分页储存管理

基本分段存储管理

段页式存储管理

内存空间的扩充（实现虚拟性）

覆盖技术

交换技术

虚拟存储技术

地址转换

操作系统负责实现逻辑地址到物理地址的转换

三种方式

绝对装入：编译器负责地址转换（单道程序阶段，无操作系统）

可重定位装入：装入程序负责地址转换（早期多道批处理阶段）

动态运行时装入：运行时才进行地址转换（现代操作系统）

存储保护

保证各进程在自己的内存空间内运行，不会越界访问

两种方式

设置上下限寄存器

利用重定位寄存器、界地址寄存器进行判断

24.覆盖与交换

覆盖技术

一个固定区

存放最活跃的程序段

固定区中的程序段在运行过程中不会调入调出

若干覆盖区

不可能同时被访问程序段可共享一个覆盖区

覆盖区中的程序段在运行过程中会根据需要调入调出

必须由程序员声明覆盖结构，操作系统完成自动覆盖

缺点：对用户不透明，增加了用户编程的负担

交换技术

内存紧张时，换出某些进程以腾出内存空间，再换入某些进程

磁盘分为文件区和对换区，换出的进程放在对换区

覆盖与交换的区别

覆盖是在同一个程序或进程中的

交换是在不同进程（或作业）之间的

25.连续分配管理方式

单一连续分配

只支持单道程序，内存分为系统区和用户区，用户程序放在用户区

无外部碎片，有内部碎片

固定分区分配

支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业

无外部碎片，有内部碎片

两种分区方式

分区大小相等

分区大小不等

动态分区分配

支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区

无内部碎片，有外部碎片

外部碎片可用“紧凑”技术来解决

回收内存分区时，可能遇到四种情况

回收区之后有相邻的空闲分区

回收区之前有相邻的空闲分区

回收区前、后都有相邻的空闲分区

回收区前、后都没有相邻的空闲分区

动态分区分配算法

首次适应算法（First Fit）

算法思想

从头到尾找适合的分区

分区排列顺序

空闲分区以地址递增次序排列

优点

综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序

最佳适应算法（Best Fit）

算法思想

优先使用更小的分区，以保留更多大分区

分区排列顺序

空闲分区以容量递增次序排列

优点

会有更多的大分区被保留下来，更能满足大进程需求

缺点

会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序

最坏适应算法（Worst Fit）

算法思想

优先使用更大的分区，以防止产生太小的不可用的碎片

分区排列顺序

空闲分区以容量递减次序排列

优点

可以减少难以利用的小碎片

缺点

大分区容易被用完，不利于大进程；算法开销大（原因同上）

临近适应算法（Next Fit）

算法思想

由首次适应演变而来，每次从上次查找结束位置开始查找

分区排列顺序

空闲分区以地址递增次序排列（可排列成循环链表）

优点

不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法）

缺点

会使高地址的大分区也被用完

26.非连续分配管理方式

基本分页存储管理

基本分页存储管理的基本概念

基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个内存块中

重要概念

“页框、页帧、内存块、物理块”vs“页、页面”

“页框号、页帧号、内存块号、物理块号、“页号、页面号””

如何实现地址转换

1.计算出逻辑地址对应的页号

2.找到对应页面在内存中的存放位置

3.算出逻辑地址对应的页内偏移量

4.物理地址=页面起始地址+页内偏移量

页号、页内偏移量的计算

页号=逻辑地址/页面大小；页内偏移量=逻辑地址%页面大小

或根据逻辑地址结构计算，逻辑地址=【页号P，页内偏移量W】

页表

页表记录进程页面和实际存放的内存块之间的对应关系

一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成

每个页表项的长度是相同的，页号是“隐含的”

基本地址变换机构

页表寄存器的作用

存放页表起始地址

存放页表长度

地址变换过程

1.根据逻辑地址算出页号、页内偏移量

2.页号的合法性检查（与页表长度对比）

3.若页号合法，再根据页表起始地址、页号找到对应页表项

4.根据页表项中记录的内存块号、页内偏移量得到最终的物理地址

5.访问物理内存对应的内存单元

其他小细节

页内偏移量位数与页面大小之间的关系（要能用其中一个条件推出另一个条件）

页式管理中地址是一维的

实际应用中，通常使一个页框恰好能放入整数个页表项

为了方便找到页表项，页表一般是放在连续的内存块中的

地址变化过程图解

具有快表的地址变换机构

局部性原理

时间局部性

如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）

空间局部性

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存中都是连续存放的）

什么是快表（TLB）

又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程对应的，内存中的页表常称为慢表

引入快表后，地址的变换过程

1.算页号、页内偏移量

2.检查页号合法性

3.查快表。若命中，即可知道页面存放的内存块号，可直接进行5；若未命中则进行4

4.查页表，找到页面存放的内存块号，并且将页表项复制到快表中

5.根据内存块号与页内偏移量得到物理地址

6.访问目标内存单元

地址变换过程图解

两级页表

单级页表存在的问题

所有页表项必须连续存放，页表过大时需要很大的连续空间

在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存

两级页表

将长长的页表再分页

逻辑地址结构（一级页号，二级页号，页内偏移量）

注意几个术语：页目录表/外层页表/顶级页表

如何实现地址转换

按照地址结构将逻辑地址拆分成三部分

从PCB中读出页目录表地址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置

根据二级页号查表，找到最终想访问的内存块号

结合页内偏移量得到物理地址

几个细节

多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级

多级页表的访存次数（假设没有快表机构）——N级页表访问一个逻辑地址需要N+1访存

地址变换图解

基本分段存储管理

分段

将地址空间按照程序自身的逻辑关系划分为若干段，每段从0开始编址

每个段在内存中占据连续空间，但各段之间可以不相邻

逻辑地址结构：（段号、段内地址）

段表

记录逻辑段到实际存储地址的映射关系

每个段对应一个段表项，各段表项长度相同，由段号（隐含）、段长、基址组成

地址变化

1.由逻辑地址得到段号、段内地址

2.段号与段表寄存器中的段长度比较，检查是否越界

3.由段表始址、段号找到对应段表项

4.根据段表中记录的段长，检查段内地址是否越界

5.由段表中的“基址+段内地址”得到最终的物理地址

6.访问目标单元

分段VS分页

分页对用户不可见，分段对用户可见

分页的地址空间是一维的，分段的地址空间是二维的

分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享）

分页（单级页表）、分段访问一个逻辑地址需要两次访存，分段存储中也可以引入快表机制

地址变换图解

段页式存储管理

分段+分页

将地址空间按照程序自身的逻辑关系划分为若干段，在将各段分为大小相等的页面

将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存

逻辑地址结构：（段号，页号，页内偏移量）

段表、页表

每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放地址组成

每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成

地址变换

1.由逻辑地址得到段号、页号、页内偏移量

2.段号与段表寄存器中的段长度比较，检查是否越界

3.由段表始址、段号找到对应段表项

4.根据段表中记录的页表长度，检查页号是否越界

5.由段表中的页表地址、页号得到查询页表，找到相应页表项

6.由页面存放的内存块号、页内偏移量得到最终的物理地址

7.访问目标单元

访问一个逻辑地址所需访存次数

第一次——查段表、第二次——查页表、第三次——访问目标单元

可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存

地址变化过程图解

27.虚拟内存的基本概念

传统存储管理方式的特征、缺点

一次性：作业数据必须一次全部调入内存

驻留性：作业数据在整个运行期间都会常驻内存

局部性原理

时间局部性：现在访问的指令、数据在不就之后很可能会被再次访问

空间局部性：现在访问的内存单元周围的内存空间，很可能在不久之后会被访问

高速缓存技术：使用频繁的数据放倒更高速的存储器中

虚拟内存的定义和特征

程序不需要全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据

特征

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存

对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出

虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

如何实现虚拟内存技术

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）

内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）

虚拟内存的实现

请求分页存储管理

页表机制

在基本分页的基础上增加了几个表项

状态位：表示页面是否已在内存中

访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考

修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存

外存地址：页面在外存中存放的位置

缺页中断机构

找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断

缺页中断处理中，需要将目标页面调入内存，有必要时还需换出页面

缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常

一条指令在执行过程中可能产生多次缺页中断

地址变换机构（重点关注与基本分页不同的地方）

找到页表项时需要检查页面是否在内存中

若页面不在内存中，需要请求调页

若内存空间不够，还需换出页面

页面调入内存后，需要修改相应页表项

请求分段存储管理

请求段页式存储管理

28.页面置换算法

最佳置换算法（OPT）

先进先出置换算法（FIFO）

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

时钟置换算法（CLOCK）

改进型的时钟置换算法

29.页面分配策略

驻留集

指请求分页存储管理中给进程分配的内存块的集合

页面分配、置换策略

固定分配 VS 可变分配：区别在于进程运行期间驻留集大小是否可变

局部置换 VS 全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出

固定分配局部置换；进程进行前就分配一定数量物理块，缺页时只能换出进程自己的某一页

可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面

可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率低的进程，回收一些物理块。直到缺页率合适

调入页面的时机

预调页策略：一般用于进程运行前

请求调页策略：进程运行时，发现缺页再调页

从何处调页

对换区——采用连续存储方式，速度更快；文件区——采用离散存储方式，速度更慢

对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行

对换区不够大：不会修改的数据每次都从文件区调入：会修改的数据调出到对换区，需要时再从对换区调入

UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入

抖动（颠簸）现象

页面频繁换入换出的现象。主要原因是分配给进程的物理块不够

工作集

在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小

30.初识文件管理

文件的定义：一组有意义的信息的集合

文件的属性：文件名、标识符、类型、位置、大小、保护信息...

文件内部应该如何被组织起来（文件的逻辑结构）

文件之间应该如何组织起来（目录结构）

操作系统应向上提供哪些功能（create、delete、open、read、write系统调用）

文件应如何存放在外存中（文件的物理结构）

操作系统如何管理外存中的空闲块（存储空间的管理）

操作系统需要提供的其他文件管理功能

文件共享

文件保护

31.文件的逻辑结构

无结构文件

由二进制流或字符流组成，无明显的逻辑结构

有结构文件

由记录组成，分为定长记录、可变长记录

逻辑结构

顺序文件

串结构：记录顺序与关键字无关

顺序结构：记录按关键字顺序排列

可变长记录的顺序文件无法实现随机存取，定长记录可以

定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）

最大缺点：不方便增加/删除记录

索引文件

建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录

索引表本身就是定长记录的顺序文件，一个缩影表项就是一条定长记录，因此索引文件可支持随机存取

若索引表按关键字顺序排列，则可支持快速检索

解决了顺序文件方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间

索引顺序文件

将记录分组，每组对应一个索引表项

检索记录时先顺序查索引表，找到分组，再顺序查找分组

当记录过多时，可建立多级索引表

32.文件目录

文件目录的实现

一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录

对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件

目录结构

单级目录结构

一个系统只有一张目录表，不允许文件重名

两级目录结构

不同用户的文件可以重名，但不能对文件进行分类

多级（树形）目录结构

不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享

系统根据“文件路径”找到目标文件

从根目录出发的路径是“绝对路径”

从“当前目录”出发的路径是“相对路径”

无环图目录结构

在树形目录结构的基础上，增加一些指向同一个节点的有向边，使整个目录成为一个有向无环图

为共享节点设置一个共享计数器，计数器为0时才真正删除该结点

索引结点

除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引节点

目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减少

由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就少了很多

33.文件的物理结构

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块

优点：支持顺序访问和直接访问（即随机访问）：连续分配的文件在顺序访问时速度最快

缺点：不方便文件拓展；存储空间利用率，会产生磁盘碎片

链式分配

隐式链接

除文件的最后一块盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高

缺点：支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间

显式链接

把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，Flle Allocation Table）一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点：文件分配表的需要占用一定的存储空间

索引分配

链接方案

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放

缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，磁盘I/O次数多，查找效率低

多层索引

建立多层索引（原理类似多级页表）。使第一层索引块指向第二层索引块。还可根据文件大小的要求再建立第三层、四层。采用k层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要k+1次磁盘操作

缺点：即使是小文件，访问一个数据块依然需要k+1次读磁盘

混合索引

多种索引分配方式的结合。一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引、还包含两级间接索引

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

总结

34.文件存储空间管理

储存空间的划分与初始化

文件卷（逻辑卷），目录区、文件区的概念

目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据

几种管理方法

空闲表法

空闲表中记录每个连续空闲区的起始盘块号、盘块数

分配时可采用首次适应、最佳适应等策略；回收时注意表项的合并问题

空闲链表法

空闲盘块链

以盘块为单位组成一条空闲链

分配时从链头依次取出空闲块，回收时将空闲块插到链尾

空闲盘区链

以盘区为单位组成一条空闲链

分配时可采用首次适应、最佳适应策略；回收时注意相邻空闲盘区合并的问题

位示图法

一个二级制位对应一个盘块（字号，位号）或（行号，列号）与盘块号一一对应

重要考点：要能够自己推出盘块号->（字号，位号）之间相互转换公式

需要注意的题目条件

二进制位0/1到底哪个代表空闲空间，哪个代表不空闲

字号、位号、盘块号到底从0开始还是从1开始

成组链接法

UNIX采用的策略，适合大型文件系统。理解即可，不方便用文字描述的知识点也很难作为考题

35.文件的基本操作

创建文件

分配外存空间，创建目录项

删除文件

回收外存空间，删除目录项

打开文件

将目录项的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户

打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作

每个进程都有自己的打开文件表，系统中也有一张总的打开文件表

进程打开文件表中特有的属性：读写指针、访问权限（只读？读写？）

系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）

关闭文件

将进程打开文件表中的相应表项删除

系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项

读文件

根据读指针、读入数据量、内存位置将文件数据从外存读入内存

写文件

根据写指针、写出数据量、内存位置将文件数据从内存写出外存

36.文件共享

硬链接

各个用户的目录项指向同一个索引结点

索引结点中需要有链接计数count

某用户想删除文件时，只是删除该用户的目录项，且count--

只有count==0时才能真正删除文件数据和索引结点，否则会导致指针悬空

软链接（符号链接）

在一个LInk型的文件中记录共享文件的存放路径（Windows快捷方式）

操作系统根据路径一层层查找目录，最终找到共享文件

即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径区查找共享文件会失败（找不到对应项）

由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问文件的速度比硬链接慢

37.文件保护

口令保护

为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确

实现开销小，但“口令”一般存放在FCB或索引结点中（也就是存放在系统中）因此不太安全

加密保护

用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确的解密

访问控制

用一个访问控制表（ACL）记录各个用户（或各组用户）对文件的访问权限

实现灵活，可以实现复杂的文件保护功能

38.文件系统的层次结构

用户接口

文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（Read、Write、Open、Close等系统调用）

文件目录系统

用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等。

存取控制模块

为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能

逻辑文件系统与文件信息缓冲区

用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址

物理文件系统

辅助分配模块

负责文件存储空间的管理，即负责分配和回收存储空间

设备管理模块

设备

例子

1.用户需要通过操作系统提供的接口发出上述请求--用户请求

2.由于用户提供的是文件存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项--文件目录系统

3.不同的用户对文件有不同的操作权限，因此保证安全，需要检查用户是否有访问权限--存取控制模块（存取控制验证层）

4.验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址--逻辑文件系统与文件信息缓冲区

5.知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址--物理文件系统

6.要删除这条记录，必定要对磁盘设备发出请求--设备管理程序模块

7.删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收--辅助分配模块

39.磁盘

磁盘结构

磁盘、磁道、扇区的概念

磁盘由表面涂有磁性物质的圆形盘片组成

每个盘片被划分为一个个磁道，每个磁道又被划分为一个个扇区

如何在磁盘中读/写数据

磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写

盘面、柱面的概念

磁盘有多个盘片“摞”起来，每个盘片有两个盘面

所有盘面中相对位置相同的磁道组成柱面

磁盘的物理地址

（柱面号，盘面号，扇区号）

磁盘的分类

根据磁头是否可移动

固定头磁盘（每个磁道有一个磁头）

移动头磁盘（每个盘面只有一个磁头）

根据盘片是否可更换

固定盘磁盘

可换盘磁盘

磁盘调度算法

一次磁盘读/写操作需要的时间

寻找时间（寻道时间）：启动磁臂、移动磁头所花的时间

延迟时间：将目标扇区转到磁头下面所花的时间

传输时间：读/写数据花费的时间

磁盘调度算法

先来先服务（FCFS）

被访问请求到达的先后顺序进行处理

最短寻找时间优先（SSTF）

每次都优先响应距离磁头最近的磁道访问请求

贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短

缺点：可能导致饥饿

扫描算法（电梯算法、SCAN）

只有磁头移动到最边缘的磁道时才可以改变磁头移动方向

缺点：对各个位置磁道的相应频率不平均

循环扫描算法（C-SCAN）

只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求

低频考点

LOOK算法

SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向

C-LOOk

C-SCAN算法的改进，只要在磁头移动方向不再有请求，就立即让磁头返回

减少延迟时间的方法

交替编号

具体做法：让编号相邻的扇区在物理上不相邻

原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区

错位命名

具体做法：让相邻盘面的扇区编号“错位”

原理：与“交替编号”的原理相同。“错位命名法”可降低延迟时间

磁盘地址结构的设计

理解为什么要用（柱面号，盘面号，扇区号）的结构

理解为什么不要（盘面号，柱面号，扇区号）的结构

原因：在读取地址连续的磁盘块时，前者不需要移动磁头

磁盘管理

磁盘初始化

低级格式化/物理格式化：划分扇区

磁盘分区（C盘、D盘、E盘）

逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构）

引导块

计算机启动时需要运行初始化程序（自举程序）来完成初始化

ROM中存放很小的自举装入程序

完整的自举程序存放在初始块（引导块）中

坏块的管理

简单的磁盘：逻辑格式化时将坏块标记出来

复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区

40.I/O设备

I/O设备的基本概念与分类

什么是I/O设备

将数据Input/Output（输入/输出）计算机的外部设备

按使用特性分类

人机交互类外部设备

存储设备

网络通信设备

按传输速率分类

低速设备

中速设备

高速设备

按信息交换的单位分类

块设备（传输块，可寻址）

字符设备（传输慢，不可寻址，常采用中断驱动方式）

I/O控制器

主要功能

接收和识别CPU发出的命令（要有控制寄存器）

向CPU报告设备的状态（要有状态寄存器）

数据交换（要有数据寄存器，暂存输入/输出的数据）

地址识别（由I/O逻辑实现）

组成

CPU与控制器之间的接口（实现控制器与CPU之间的通信）

I/O逻辑（负责识别CPU发出的命令，并向设备发出命令）

控制器与设备之间的接口（实现控制器与设备之间的通信）

两种寄存器编址方式

内存映射I/O

控制器中的寄存器与内存统一编址

可以采用对内存进行操作的指令来对控制器进行操作

寄存器独立编址

控制器中的寄存器独立编址

需要设置专门的指令来操作控制器

I/O控制方式

程序直接控制方式

完成一次读/写操作的流程

CPU干预的频率

很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查

数据传送的单位

每次读/写一个字

数据的流向

读操作（数据输入）：I/O设备->CPU->内存

写操作（数据输出）：内存->CPU->I/O设备

主要缺点和优点

优点：实现简单。在读/写指令后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”）

缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低

中断驱动方式

完成一次读/写操作的流程

CPU干预的频率

每次I/O操作开始之前、完成之后需要CPU介入。等待I/O完成的过程中CPU可以切换到别的进程执行

数据传送的单位

每次读/写一个字

数据的流向

读操作（数据输入）：I/O设备->CPU->内存

写操作（数据输出）：内存->CPU->I/O设备

主要缺点和优点

优点：与“程序直接控制方式”相比，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。

缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间

DMA方式

完成一次读/写操作的流程

CPU干预的频率

仅在传送一个或多个数据块的开始和结束时，才需要CPU干预

数据传送的单位

每次读/写一个或多个块（注意：每次读写的只能是连续的多个块，它们读入内存后也是连续的）

数据的流向

读操作（数据输入）：I/O设备->内存

写操作（数据输出）：内存->I/O设备

主要缺点和优点

优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加

缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块

通道控制方式

完成一次读/写操作的流程

CPU干预的频率

极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写之后才需要发出中断信号，请求CPU干预

数据传送的单位

每次读/写一组数据块

数据的流向

读操作（数据输入）：I/O设备->内存

写操作（数据输出）：内存->I/O设备

主要缺点和优点

优点：CPU、通道、I/O设备可并行性工作，资源利用率很高

缺点：实现复杂，需要专门的通道硬件支持

I/O软件层次结构

I/O核心子系统

假脱机技术/SPOOLing技术

脱机技术

外围控制机+更高速的设备--磁带

作用：缓解设备与CPU的速度矛盾，实现预输入、缓输出

假脱机技术

又叫SPOOLing技术，用软件的方式模拟脱机技术

输入井和输出井--模拟脱机输入/输出时的磁带

输入进程和输出进程--模拟脱机输入/输出时的外围控制机

输入缓冲区和输出缓冲区--内存中的缓冲区、输入、输出时的“中转站”

共享打印机

用SPOOLing技术将独占式的打印机“虚拟”成共享打印机

设备的分配与回收

应考虑的因素

固有属性

独占设备、共享设备、虚拟设备

分配算法

先来先到服务、优先级高者优先、短任务优先等

安全性

安全分配方式、不安全分配方式

静态分配与动态分配

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源

动态分配：进程运行过程中动态申请设备资源

设备分配管理中的数据结构

设备控制表（DCT）

每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针

控制器控制表（COCT）

每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列的指针

通道控制表（CHCT）

每个控制器对应一张CHCT，关键字段：状态/等待队列指针

系统设备表（SDT）

记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口

设备分配的步骤

1.根据进程请求的物理设备名查找SDT

2.根据SDT找到DCT并分配设备

3.根据DCT找到COCT并分配控制器

4.根据COCT找到CHCT并分配通道

设备分配步骤的改进

用户编程时使用逻辑设备申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射（通过LUT）

逻辑设备表的设置问题

整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复

每个用户一张LUT：各个用户的逻辑设备名可重复

缓冲区管理

缓冲区的概念

一般利用内存作为缓冲区

缓解CPU与设备的速度矛盾、减少时对CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与I/O设备之间并行性

单缓冲

设备--（T）--缓冲区--（M）--工作区--（C）--处理

处理一块数据平均耗时Max（C,T）+M

分析问题的初始状态：工作区满，缓冲区空

双缓冲

处理一块数据平均耗时Max（T,C+M）

分析问题的初始状态：工作区空，一个缓冲区满，另一个缓冲区空

循环缓冲

多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区

缓冲池

三个队列：空缓冲队列、输入队列、输出队列

四种工作缓冲区

用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区

用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区

1.操作系统的概念、功能和目标

概念（定义）

功能和目标

资源的管理者

目标

安全、高效

提供的功能

处理机管理

3.对应的进程被处理机（CPU）处理

存储器管理

2.需要把该程序相关数据放入内存

文件管理

1.逐层打开文件夹，找到QQ.exe这个程序（可执行文件）的存放位置

设备管理

4.将摄像头设备分配给进程

向用户提供服务

目标

方便用户使用

提供的功能

命令接口

联机命令接口（交互式命令接口）

脱机命令接口（批处理命令接口）

程序接口

由一组系统调用组成（程序接口=系统调用）

GUI（图形用户界面）

对硬件机器的扩展

功能和目标

实现对硬件机器的扩展

2.操作系统的特征

并发

指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

共享

互斥共享方式

系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源

同时共享方式

系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问（这个同时是宏观上的）

虚拟

概念

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的

虚拟技术

空分复用技术（如虚拟存储器技术）

时分复用技术（如虚拟处理器）

异步

概念

在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一管到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

3.操作系统的发展和分类

手工操作阶段

批处理阶段

单道批处理系统

引入脱机输入/输出技术（用磁带完成），并监督程序负责控制作业的输入、输出

多道批处理系统（操作系统开始出现）

分时操作系统

计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

实时操作系统

硬实时系统

必须在绝对严格的规定时间内完成处理

软实时系统

能接受偶尔违反时间规定

网络操作系统

分布式操作系统

个人计算机操作系统

4.操作系统的运行机制和体系结构

运行机制

两种指令

特权指令

非特权指令

两种处理器状态

核心态（管态）

用户态（目态）

两种程序

内核程序

应用程序

操作系统内核

时钟管理

中断处理

原语

是一种特殊的程序

处于操作系统最底层，是最接近硬件的部分

这种程序的运行具有原子性--其运行只能一气呵成，不可中断

运行时间较短、调用频繁

对系统资源进行管理的功能

进程管理

存储器管理

设备管理

操作系统的体系结构

大内核

将操作系统的主要功能模块都作为系统内核，运行在核心态

优点：高性能

缺点：内核代码庞大，结构混乱，难以维护

微内核

只把最基本的功能保留在内核

优点：内核功能少，结构清晰，方便维护

缺点：需要频繁地在核心态和用户态之间切换，性能低

5.中断和异常

中断机制的诞生

中断的概念和作用

发生中断就意味着需要操作系统介入，开展管理工作，CPU会立即进入核心态

“中断”是CPU从用户态进入核心态的唯一途径

中断的分类

内中断

自愿中断——指令中断

强迫中断

硬件故障

软件故障

外中断

外设请求

人工干预

外中断的处理过程

6.系统调用

概念和作用

概念

作用

系统调用分类（按功能）

设备管理

文件管理

进程控制

进程通信

内存管理

系统调用和库函数的区别

普通应用程序

编程语言

操作系统

裸机

系统调用背后的过程

7.进程的定义、组成、组织方式、特征

定义

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

组成

程序段

数据段

PCB

进程描述信息

进程标识符PID

用户标识符UID

进程控制和管理信息

进程当前状态

进程优先级

资源分配清单

程序段指针

数据段指针

键盘

鼠标

处理机相关信息

各种寄存器值

组织方式

链接方式

按照进程装填将PCB分为多个队列

操作系统持有指向各个队列的指针

索引方式

根据进程状态的不同，建立几张索引表

操作系统持有指向各个索引表的指针

特征

动态性

进程是程序的一次执行过程，是动态地产生、变化和消亡的

并发性

内存中有多个进程实体，各进程可并发执行

独立性

进程是能独立运行、独立获得资源、独立接受调度的基本单位

异步性

个进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题

结构性

每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成

8.进程的状态与转换

状态

运行状态

占有CPU，并在CPU上运行

就绪状态

已经具备运行条件，但由于没有空闲CPU，而暂时不能运行

阻塞状态

因等待某一事件而暂时不能运行

创建状态

进程正在被创建，操作系统为进程分配资源、初始化PCB

终止状态

进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

进程状态间的转换

就绪态->运行态

运行态->就绪态

运行态->阻塞态

阻塞态->就绪态

运行原理图

9.进程控制

基本概念

进程控制就是要实现进程状态的转换

进程控制用原语实现

原语用关/开中断来实现

原语是一种特殊的程序

原语的执行必须一气呵成，不可中断

进程控制相关原语

进程的创建

创建原语

申请空白PCB

为新进程分配所需资源

初始化PCB

将PCB插入就绪队列

引起进程创建的事件

用户登录

分时系统中，用户登录成功，系统会为其建立一个新的进程

作业调度

多道批处理系统中，有新的作业放入内存是，会为其建立一个新的进程

提供服务

用户向操作系统提出某些请求时，会新建一个进程处理该请求

应用请求

由用户进程主动请求创建一个子进程

进程的终止

撤销原语

从PCB集合中找到终止进程的PCB

若进程正在运行，立即剥夺CPU，将CPU分配给其他进程

终止其所有子进程

将该进程拥有的所有资源归还给父进程或操作系统

删除PCB

引起进程终止的事件

正常结束

异常结束

外界干预

进程的阻塞

阻塞原语

找到要阻塞的进程对应的PCB

保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行

将PCB插入相应事件的等待队列

引起进程阻塞的事件

需要等待系统分配某种资源

需要等待相互合作的其他进程完成工作

进程的唤醒

唤醒原语

在事件等待队列中找到PCB

将PCB从等待队列移除，设置进程为就绪态

将PCB插入就绪队列，等待被调度

引起进程唤醒的事件

等待的事件发生

进程的切换

切换原语

将运行环境信息存入PCB

PCB移入相应队列

选择另一个进程执行，并更新其PCB

根据PCB恢复新进程所需的运行环境

引起进程切换的事件

当前进程时间片到

有更高优先级的进程到达

当前进程主动阻塞

当前进程终止

10.进程通信

共享存储

基于数据结构的共享

基于存储区的共享

消息传递

直接通信方式

间接通信方式

管道通信

11.线程、多线程模型

什么是线程，为什么要引入线程

可理解为“轻量级进程”

可增加并发度，减少并发带来的开销

带来的变化

资源分配、调度

传统进程机制中，进程是资源分配、调度的基本单位

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

并发性

传统进程机制中，只能进程间并发

引入线程后，各线程间也能并发，提升了并发度

系统开销

传统的进程间并发，需要切换进程的运行环境，系统开销很大

线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小

引入线程后，并发所带来的系统开销减小

线程的属性

线程是处理机调度的单位

多CPU中，各个线程可以占用不同的CPU

每个线程都有一个线程ID、线程控制块（TCB）

线程也有就绪、阻塞、运行三种基本状态

线程几乎不拥有系统资源

同一进程的不同线程间共享进程的资源

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

同一进程中的线程切换，不会引起进程切换

不同进程中的线程切换，会引起进程切换

切换同进程内的线程，系统开销很小

切换进程，系统开销很大

线程的实现方式

用户级线程

内核级线程

组合方式

多线程模型

多对一模型

优点：进程管理开销小效率高

缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）

一对一模型

优点：各个线程可分配到多核处理机并行执行，并发度高

缺点：进程管理开销大

多对多模型

及二者之所长

12.处理机调度

基本概念

按照某种算法选择一个进程将处理机分配给它

三个层次

高级调度（作业调度）

按照某种规律，从后备队列中选择合适的作业将其调入内存，并为其创建进程

中级调度（内存调度）

按照某种规则，从挂起队列中选择合适的进程将其数据调回内存

低级调度（进程调度）

按照某种规则，从就绪队列中选择一个进程为其分配处理机

三层调度的联系、对比

补充

进程的“挂起态”

就绪挂起

阻塞挂起

七状态模型

13.进程调度的时机、切换与过程、方式

时机

需要进行进程调度与切换的情况

当前运行的进程主动放弃处理机

进程正常终止

运行过程中发生异常而终止

进程主动请求阻塞（如等待I/O）

当前运行的进程被动放弃处理机

分给进程的时间片用完

有更紧急的事需要处理（如I/O中断）

有更高优先级的进程进入就绪队列

不能进行进程调度与切换的情况

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换

进程在操作系统内核程序临界区

在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）

切换与过程

狭义“调度”和“切换”的区别

切换过程

对原来运行进程各种数据的保存

对新的进程各种数据的恢复

重要结论

进程调度、切换是有代价的，并不是调度越频繁，并发度就越高

方式

非剥夺调度方式（非抢占式）

只允许进程主动放弃处理机

剥夺调度方式（抢占式）

可由操作系统剥夺当前进程的CPU使用权

14.调度算法的评价指标

CPU利用率

指CPU“忙碌”的时间占总时间的比例

系统吞吐量

单位时间内完成作业的数量

周转时间

周转时间、平均周转时间

周转时间，指作业被提交给系统开始，到作业完成为止的这段时间间隔

带权周转时间、平均带权周转时间

等待时间

指进程/作业处于等待处理机状态时间之和，就是指进程建立后等待被服务的时间之和

响应时间

指从用户提交请求到首次产生相应所用的时间

15.调度算法

先来先到服务（FCFS）

算法思想

主要从“公平”的角度考虑（类似于排队）

算法规则

按照作业/进程到达的先后顺序进行服务

用于调度

作业

考虑哪个作业先到达后备队列

进程

考虑哪个进程先到达就绪队列

是否可抢占？

非抢占式的算法

优缺点

优点

公平、算法实现简单

缺点

排在长作业（进程）后面的段作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好

是否会导致饥饿

不会

短作业优先（SJF）

算法思想

追求最少平均等待时间，最少的平均周转时间、最少平均带权周转时间

算法规则

最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）

用于调度

作业

即可

进程

称为“短进程优先算法（SPF）”

是否可抢占？

SJF和SPF是非抢占式的算法。但是也有抢占式版本--最短剩余时间优先算法（SRTN）

优缺点

优点

“最短的”平均等待时间、平均周转时间

缺点

不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

是否会导致饥饿

会。如果源源不断地有短作业/进程到来，可能会使长作业/进程长时间得不到服务，产生“饥饿”现象。一直得不到，则称“饿死”

高响应比优先（HRRN）

算法思想

要综合考虑作业/进程的等待时间和要求服务时间

算法规则

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

用于调度

作业

即可

进程

也可

是否可抢占？

非抢占式。只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

优缺点

优点

上述两种算法的权衡折中，综合考虑的等待时间和运行时间

缺点

是否会导致饥饿

不会

时间片轮转调度算法（RR）

算法思想

公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则

按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）

用于调度

作业

进程

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

是否可抢占？

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此属于抢占式算法。

优缺点

优点

公平；相应快，适用于分时操作系统

缺点

由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度

是否会导致饥饿

不会

优先级调度算法

算法思想

随着计算机发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

算法规则

每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

用于调度

作业

即可

进程

也可

是否可抢占？

抢占式、非抢占式都有

优缺点

优点

用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对个作业/进程的偏好程度

缺点

若源源不断地有高优先级进程到来，则可能导致饥饿

是否会导致饥饿

会

多级反馈队列调度算法

算法思想

对其他调度算法的折中权衡

算法规则

1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级队列，则重新放回该队列队尾

3.只有第k级队列为空时，才会为k+1级对头的进程分配时间片

4.被抢占处理机的进程重新放回原队列队尾

用于调度

作业

进程

用于进程调度

是否可抢占？

抢占式算法。在k级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原理运行的进程放回k级队列队尾。（也就是算法规则的第4条）

优缺点

优点

对各类型进程相对公平（FCFS优点）；每个新到达的进程都可以很快得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间；可灵活地调整对各类进程的偏好程度。

缺点

是否会导致饥饿

会

16.进程同步和互斥

进程同步

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序

进程互斥

概念

对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源

四个部分

进入区

检查是否可进入临界区，若可进入，需要“上锁”

临界区

访问临界资源的那段代码

退出区

负责“解锁”

剩余区

其余代码部分

需要遵循的原则

空闲让进

临界区空闲时，应允许一个进程访问

忙则等待

临界区正在被访问时，其他试图访问的进程需要等待

有限等待

要在有限时间内进入临界区，保证不会饥饿

让权等待

进不了临界区的进程，需要释放处理机，防止忙等

进程互斥的软件实现方法

单标志法

双标志先检查

双标志后检查

Peterson算法

进程互斥的硬件实现方法

中断屏蔽方法

使用“开/关中断”指令实现

优点；简单高效

缺点：只适用于单处理机；只适用于操作系统内核进程

TestAndSet（TS指令/TSL指令）

Swap指令（XCHG指令）

17.信号量机制

整型信号量

用一个整数型变量作为信号量，数值表示某种资源数

整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作

整型信号量存在的问题：不满足让权等待原则

数据结构

记录型信号量

S.value表示某种资源数，S.L指向等待该资源的队列

P操作中，一定是先S.value--，之后可能需要执行block原语

V操作中，一定是先S.value++，之后可能需要执行wakeup原语

注意：要能够直接推断在什么条件下需要执行block或wakeup

可以用记录型信号量实现系统资源的“申请”和“释放”

可以用记录型信号量实现进程互斥、进程同步

数据结构

实现进程互斥

分析问题，确定临界区

设置互斥信号量，初值为1

临界区之前对信号量执行P操作

临界区之后对信号量执行V操作

实现进程同步

分析问题，找出哪里需要实现“一前一后”的同步关系

设置同步信号量，初始值为0

在“前操作”之后执行V操作

在“后操作”之前执行P操作

实现进程的前驱关系

分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题

为每一对前驱关系设置同步信号量，初始值为0

在每个“前操作”之后执行V操作

在每个“后操作”之前执行P操作

18.进程互斥同步问题

生产者消费者问题

问题描述

如何实现

多生产者多消费者问题

问题描述

如何实现

重要思路

吸烟者问题

问题描述

如何实现

读者写者问题

问题描述

如何实现

读者优先

写者优先（读写公平法）

重要思路

哲学家进餐问题

问题描述

代码实现

死锁问题解决

1.可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样就可以保证至少有一个哲学家是可以拿到左右两只筷子的

2.要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起一只筷子，另一个会阻塞

3.仅当一个哲学家左右两支筷子都可使用时才允许他抓起筷子，为拿起两只筷子的操作前后加上互斥信号量mutex

19.管程

为什么要引入管程

解决信号量机制编程麻烦、易出错的问题

组成

共享数据结构

对数据结构初始化的语句

一组用来访问数据结构的过程（函数）

基本特征

各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据

每次仅允许一个进程在管程内执行某个内部过程

补充

各进程必须互斥访问管程的特性是由编译器实现的

可在管程中设置条件变量及等待/唤醒操作以解决同步问题

20.死锁

什么是死锁

各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进

死锁、饥饿、死循环的区别

死锁：至少是两个进程一起死锁，死锁进程处于阻塞态

饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪

死循环：可能只有一个进程发生死循环，死循环是应用程序员要解决的

死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的

死锁产生的必要条件

互斥条件

对必须互斥使用的资源的争抢才会导致死锁

不剥夺条件

进程保持的资源只能主动释放，不可强行剥夺

请求和保持条件

保持着某些资源不放的同时，请求别的资源

循环等待条件

存在一种进程资源的循环等待链

循环等待未必死锁，死锁一定有循环等待

什么时候会发生死锁

对不可剥夺资源的不合理分配，可能导致死锁

死锁的处理策略

预防死锁

破坏死锁产生的四个必要条件

避免死锁

避免系统进入不安全状态（银行家算法）

死锁的检测和解除

允许死锁发生，系统负责检测出死锁并解除