文章目录
1 内容概要
2 操作系统概述
操作系统（OS，Operating System）
- 管理系统的硬件、软件、数据资源
- 控制程序运行
- 人机之间的接口
- 应用软件与硬件之间的接口
操作系统的功能：
- 进程管理
- 存储管理
- 文件管理
- 作业管理
- 设备管理
3 进程管理
3.1 进程与线程
进程的2个基本属性：可拥有资源的独立单位；可独立调度和分配资源的基本单位。
一个进程中有一个至多个线程。
例题：在支持多线程的操作系统中，假设进程Р创建了若干个线程，那么（ )是不能被这些线程共享的。
A该进程中打开的文件
B该进程的代码段
C该进程中某线程的栈指针
D该进程的全局变量
解题思路：同一进程中的多个线程的私有部分包括：程序计数器、寄存器、栈。
答案：选C。
3.2 信号量与PV操作
3.2.1 基本概念
临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
临界区:每个进程中访问临界资源的那段代码称为临界区
互斥:如千军万马过独木桥(资源上的制约，间接制约)
同步:速度有差异,在一定情况停下等待。(工序上的制约，直接制约)
信号量
- 是一种特殊的变量
- 信号量可以表示资源数量
- 信号量为负数时还可以表示排队进程数
PV操作
- P(S)操作：申请S资源，S=S-1
- V(S)操作：释放资源，S=S+1
原语：原子性，要么都做，要么都不做
信号量初值：指的是没有任何操作的情况下，信号量的取值。
P(S)：如果执行S=S-1之后S=0，则此时资源有没有申请到？
分析：执行P(S)后S=0，则执行P(S)之前S=1，即存在一个资源待分配，故在执行P(S)之后可以申请到一个资源。
V(S)：如果执行S=S+1之后S=0，则此时有没有资源在排队？
分析：执行V(S)后S=0，则执行V(S)之前S=-1，即存在一个进程在排队。
例子：系统中有3台打印机，5个进程需要用打印机，此时用PV操作控制打印机的访问，信号量S表示打印机资源，信号量最大能取多少？最小能取多少？
分析：当3台打印机均空闲时，信号量取值最大，S=3；当5个进程一起请求打印机时，信号量最小，S=-2，因为有3个进程可以请求到打印机资源。
3.2.2 互斥模型
多个进程共享一台打印机问题（互斥模型）：
互斥信号量S的初值为1
3.2.3 同步模型
生产者与消费者模型：
3.2.4 PV操作解题思路
先判断模型互斥还是同步?
同一类进程：互斥，P和V在一个进程内成对
不同类进程：同步，P和V在不同进程内成对
然后根据互斥、同步不同情况来解题。
3.3 前趋图
3.3.1 相关概念
假设上图表示包饺子的过程，其中，A绞肉、B切葱末、C切姜末、D搅拌、E包饺子，左侧表示依次执行包饺子的过程，如果有多个进程一起进行的话，就可以将过程改成右侧来执行，其中，A、B、C可以同时进行。
如何线性记录一个前趋图?
关键点：结点、有向弧
(A,B）表示A→B
直接制约关系：如DE、AD、BD、CD
间接制约关系：如AE、BE、CE
1个有向弧对应1个前趋关系。
有向弧的前趋关系
前趋执行完，以V()通知后继
后继执行前，以P()检查前趋
3.3.2 例题
例题1：
分析：根据给出的进程前趋图，可记为{(P1,P2), (P1,P4), (P2,P3), (P3,P4), (P2,P5), (P3,P6), (P4,P7), (P5,P6), (P7,P6), (P6,P8)}，故选B
前趋关系个数即有向弧的条数，图中有10条，即有10个前趋关系；
没有前趋的是初始结点，即为P1；
没有后继的为终止结点，即为P8
故选D
例题2：
分析：先根据PV个数确定某些选项；再根据选项的信号量，确定图示信号量的位置。
解题过程：
根据上图，可以排除第一空的选项A、D；第二空的选项B、C、D，第二空正确选项为A。
根据上图第一空可以排除B，故第一空正确选项为C。
答案：C、A
3.4 死锁
3.4.1 基本概念
所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象
进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁
3.4.2 死锁资源数计算问题
例1:系统有3个进程:A、B、C。这3个进程都需要5个系统资源。如果系统至少有多少个资源，则不可能发生死锁。
| 资源总数n 范围 | 说明 |
|---|---|
| [0,4] | 一定发生死锁 |
| [5,12] | 可能发生死锁 |
| [13,+∞） | 一定不发生死锁 |
故系统至少有13个资源，才不可能发生死锁。
例2：某系统中有5个并发进程竞争资源R。假设每个进程都需要3个R，那么最少需要有（）个R，才能保证系统不会发生死锁。
解题思路：
假设系统有m个进程，每个进程需要w个资源，则当资源总数n≥m*(w-1)+1时，一定不会发生死锁。
解题过程：
n≥5*(3-1)+1，即n大于等于11。
答案：11
3.4.3 进程资源图
- 进程指向资源：表示正在申请还未分配
- 资源指向进程：表示资源已经分配出去了
- 非阻塞结点：一个进程能够拿到它想要的资源
- 阻塞结点：一个进程拿不到他想要的资源
- 可化简：有结点可以获取足够的资源，执行完之后，可以将所持有的资源释放出去。这个结点执行完，图示就可以消除掉这个结点，即为可化简。
- 死锁：不可化简，会发生死锁
例题：
解题思路：
分析图示的基本信息：
3个进程：P1、P2、P3
2类资源：R1、R2
资源数：2个R1、3个R2
分析箭头：
已分配资源：2个R1、2个R2
剩余资源：0个R1、1个R2
结点需要资源：P1：一个R2；P2：一个R1；P3：一个R2
能否化简：如果从P1或P3开始则不会阻塞：P1->P3->P2或P3->P1->P2；如果从P2开始，则会阻塞
故：P2是阻塞结点，P1、P3是非阻塞结点，该图可以化简，所以是非死锁。
答案：D
3.4.4 银行家算法
银行家算法:分配资源的原则
- 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
- 进程可以分期请求资源，但请求的总数不能超过最大需求量
- 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源
例题1：
假设系统中有三类互斥资源R1、R2、R3，可用资源分别是9、8、5。在TO时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下所示，如果进程按____序列执行,那么系统状态是安全的。
A P1→P2→P4→P5→P3
B P2→P4→P5→P1→P3
C P2→P1→P4→P5→P3
D P4→P2→P5→P1→P3
分析：
初始情况下：R1、R2、R3：9、8、5；
已分配资源：R1、R2、R3：7、7、5；
剩余资源： R1、R2、R3：2、1、0
各进程还需资源：
P1：R1、R2、R3：5、3、1；
P2：R1、R2、R3：0、1、0；
P3：R1、R2、R3：6、0、1；
P4：R1、R2、R3：0、0、1；
P5：R1、R2、R3：2、3、1；
对比剩余资源和各进程还需资源，排除A、D选项，因为剩余资源不足以支持P1和P4执行
那么根据选项B、C；先将资源分配给P2，P2进程完成后，释放资源，此时系统剩余资源：R1、R2、R3：4、2、1，对比此时的剩余资源和各进程还需资源，排除C，因为剩余资源不足以支持P1执行；
故选项B正确。
例题2：
假设计算机系统中有三类互斥资源R1、R2和R3，可用资源数分别为9、5和3，若在TO时刻系统中有P1，P2，P3，P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示。在TO时刻系统剩余的可用资源数分别为（)。如果进程按（）序列执行，那么系统状态是安全的。
A 1、1和0
B 1、1和1
C 2、1和0
D 2、0和1
A P1→P2→P4→P5→P3
B P4→P2→P1→P5→P3
C P5→P2→P4→P3→P1
D P5→P1→P4→P2→P3
分析：
初始时资源数：R1、R2、R3：9、5、3；
已分配资源数：R1、R2、R3：7、5、2；
剩余的资源数：R1、R2、R3：2、0、1；
故第一空选D
各进程还需资源：
P1：R1、R2、R3：4、0、1；
P2：R1、R2、R3：1、1、0；
P3：R1、R2、R3：3、2、0；
P4：R1、R2、R3：2、2、1；
P5：R1、R2、R3：1、0、1；
对比剩余资源和各进程还需资源，排除A、B选项，因为剩余资源不足以支持P1和P4执行
那么根据选项C、D；先将资源分配给P5，P5进程完成后，释放资源，此时系统剩余资源：R1、R2、R3：3、1、1，对比此时的剩余资源和各进程还需资源，排除D，因为剩余资源不足以支持P1执行；
故选项C正确。
4 存储管理
4.1 页式存储
页式存储：将程序与内存均划分为同样大小的块，以页为单位将程序调入内存。
高级程序语言使用逻辑地址;
运行状态,内存中使用物理地址。
逻辑地址=页号+页内地址
物理地址=页帧号+页内地址
例如，页式存储系统中，每个页的大小为4KB。
逻辑地址:10 1100 1101 1110
对应的物理地址为:110 1100 11011110
4KB个地址，需要12位二进制进行编码，即页内地址长度为12
则上面的逻辑地址，页号二进制为10，即2，物理地址，页帧号二进制为110，即为6
优点:利用率高，碎片小，分配及管理简单
缺点∶增加了系统开销;可能产生抖动现象
- 从页面大小计算页内地址长度；
- 分析逻辑地址结构：页内地址、页号；
- 转换成物理地址：页内地址不变，页号查表可得；
- 十六进制与二进制之间的关系：1位十六进制对应4位二进制。
例题1：
进程P有8个页面，页号分别为0~7，页面大小为4K，假设系统给进程P分配了4个存储块，进程P的页面变换表如下所示。若进程P要访问的逻辑地址为十六进制5148H，则该地址经过变换后,其物理地址应为十六进制( ) 。
分析：
- 页面大小为4K，则页内地址长度为log_2(4K)=12位二进制，即3位十六进制
- 逻辑地址十六进制为5148H，地址结构进行分析：页号：5H，页内地址：148H
- 转换物理地址：页内地址不变：148H，页帧号查表可得：3H
故物理地址十六进制为：3148H；
超过时限访问位会置0；
如果要访问的内容不在内存中，就会发生缺页中断；
页面淘汰原则：
- 淘汰的页面肯定在内存中，即状态位为1；
- 根据局部性原理，优先淘汰近期未被访问的页面，即访问位为0的页面；
- 如果多个页面访问位为0，才考虑修改位，优先淘汰修改位为0的页面。
例题2：
进程P有8个页面，页号分别为0~7，页面大小为4K，假设系统给进程P分配了4个存储块，进程P的页面变换表如下所示。表中状态位等于1和0分别表示页面在内存和不在内存。如果进程P要访问的页面6不在内存，那么应该淘汰页号为(）的页面。
分析：
- 先排除状态位位0的页号，即0、3、4、6；
- 再优先淘汰访问位为0的页号，即2；
- 答案：淘汰页号为2的页面。
4.2 段式存储
段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。
上图中，段号为0的段长为30K，超出30K会发生地址溢出，故(0,25K)为合法段地址，(0,35K)为非法段地址。
优点:多道程序共享内存，各段程序修改互不影响
缺点:内存利用率低，内存碎片浪费大
4.3 段页式存储
段页式存储：段式与页式的综合体。先分段，再分页。1个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。
优点:空间浪费小、存储共享容易、存储保护容易、能动态连接
缺点:由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加,使得执行速度大大下降
0~15是多少个二进制位？
编号范围和编号个数的关系：大编号-小编号+1
故0~15是15-0+1=16个二进制位
5 文件管理
5.1 索引文件
文件在逻辑上一定是连续的，在物理上可以是分散的。
数据块：存储文件内容；
索引块：存储索引表；
默认有13个索引结点，10个直接索引结点，一个一级间接索引结点，一个二级间接索引结点，一个三级间接索引结点。
考察方式：
- 逻辑位置（字节或页号)对应的索引方式
- 不同索引方式指向的对象（数据块&索引表)
- 不同索引方式访问磁盘的次数
- 能够表示的文件长度
例题
某文件系统采用索引节点管理，其磁盘索引块和磁盘数据块大小均为4KB字节，且每个文件索引节点有8个地址项iaddr[0]~iaddr[7]，每个地址项大小为4字节，其中iaddr[0] ~iaddr[4]采用直接地址索引，iaddr[5]和iaddr[6]采用一级间接地址索引，iaddr[7]采用二级间接地址索引。若用户要访问文件fileX中逻辑块号为5和2056的信息，则系统应分别采用（）物理块。
A、直接地址访问和直接地址访问
B、直接地址访问和一级间接地址访问
C、一级间接地址访问和一级间接地址访问
D、一级间接地址访问和二级间接地址访问
分析：
- 索引结点结构分析：
直接地址索引：iaddr[0] ~ iaddr[4]，每个地址项4字节，指向直接数据块。
一级间接地址索引：iaddr[5] 和 iaddr[6]，每个地址项4字节，指向一个包含更多地址项的块。
二级间接地址索引：iaddr[7]，每个地址项4字节，指向一个包含一级间接地址块的块- 计算每个地址项的覆盖范围
直接地址索引：iaddr[0] ~ iaddr[4]，每个地址项指向一个4KB的数据块，共5个，覆盖逻辑块号0~4。
一级间接地址索引：iaddr[5] 和 iaddr[6]，每个地址项指向一个4KB的块，该块包含1024个4字节的地址项（因为4KB / 4字节 = 1024），每个地址项指向一个4KB的数据块。因此，每个一级间接地址项可以覆盖1024个逻辑块。
二级间接地址索引：iaddr[7]，指向一个4KB的块，该块包含1024个4字节的地址项，每个地址项指向一个一级间接地址块，每个一级间接地址块又包含1024个地址项，每个地址项指向一个4KB的数据块。因此，二级间接地址项可以覆盖1024 * 1024个逻辑块。- 访问逻辑块号5和2056
逻辑块号5超出直接地址索引范围，故需要采用一级间接地址访问；
设一级间接地址范围为5~X，则（X-5）+1=2048，X=2052
则二级间接地址：2053~，所以逻辑块号2056采用二级间接地址访问- 答案：选D正确。
5.2 位示图
编号64的磁盘块记录在几号字几号bit位上？
编号：默认从0开始，故编号64的磁盘块是第64+1=65个
65/16=4…1，故编号64的磁盘块放在第5个字的第1个bit上。
例题1：
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若计算机系统的字长为32位（注:每位可以表示一个物理块“使用”还是“未用”的情况),若磁盘的容量为400GB，物理块的大小为4MB，那么位示图的大小需要（）个字。
分析：
- 计算磁盘块个数：400GB/4MB=102400
- 字长为32位： 102400/32=3200 字
故位示图需要3200个字
例题2：
某文件管理系统存磁盘上建立了位示图(bitmap)，记录磁盘的使用情况。若磁盘上物理块的编号依次为:0、1、2、…，系统中的字长为32位，字的编号依次为:0、1、2、…，字中的一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用，如图所示。
假设操作系统将2053号物理块分配给某文件，那么该物理块的使用情况在位示图中编号为()的字中描述；系统应该将()。
A 32
B 33
C 64
D 65
A 该字的位号5的位置"0"
B 该字的位号5的位置"1"
C 该字的位号6的位置"0"
D 该字的位号6的位置"1"
分析：
- 2053号是第几个物理块
2053+1=2054- 2054需要使用多少字表示
2054/32=64…6- 放在第65个字的第6个bit位上，又因为字号和位号都是从0开始的，即字号为64，位号为5
- 该物理块的使用情况在位示图中编号为64的字中描述，系统应将该字的位号5的位置"1"；
- 答案：C、B
6 考点总结
- 线程共享；
- 信号量与PV；
- 前趋图分析；
- 死锁资源数计算问题；
- 银行家算法问题；
- 进程资源图分析；
- 页式存储地址转换；
- 页式存储页面淘汰的原则
- 段页式特点及描述
- 索引文件结构计算
- 位示图计算
7 附件 思维导图
