操作系统

参考

• https://www.yuque.com/saodai/ss8tp9
• B站视频

1. 操作系统地位
2. 计算机系统由软件、硬件组成，没有配置软件的称为裸机
3. 操作系统地位：计算机硬件 》操作系统 》 系统软件 》 应用软件 》 用户
4. 所有其他软件，如编译程序、汇编程序、数据库管理系统等，以及大量应用软件都是建立在操作系统之上的
5. 把操作系统看做用户与计算机之间的接口
6. 进程管理
7. 进程是源分配和独立运行的基本单位
8. 进程管理重点是要研究诸进程之间的并发特性，以及进程间相互合作与资源竞争产生的问题
9. 前趋图：有向无循环图，由节点和单向边组成，节点代表各个程序段的操作，单向边表示前前趋关系 Pi(节点、前趋) -——> Pj(节点、后继)，Pi 执行结束 Pj 才能执行
10. 前趋图，有n 个箭头就要设置 n个信 量，按照从小到大顺序写到图中，箭头方向是 P 操作，箭头尾部是 V操作
11. 程序顺序执行的主要特征：顺序性、封闭性（独享资源）、可再现性
12. 程序并发执行的主要特征：失去程序封闭性、程序和机器执行程序的活动不再一一对应、并发程序之间的相互制约性
13. 进程的三态模型
14. 在多道程序系统中，进程在处理器上交替运行，一般由三种状态 运行、就绪、阻塞
15. 运行：当一个进程在处理机（CPU）上运行时，就是运行态
16. 就绪：一个进程获得了除了处理机（CPU）外的所有资源, 一旦得到处理机即可运行，这个时候就是就绪态
17. 阻塞：等待、睡眠，一个进程正在等待某个事件（例如等待I/O完成）发生而停止运行
18. 同步与互斥
19. 同步是合作资源进程之间直接制约的问题
20. 互斥是申请临界资源进程间的间接制约问题
21. 临界区管理原则：
    1. 有空即进，临界区无进程，则允许进入，且只能在临界区运行有限时间
    2. 无空则等，临界区有进程，其他进程则要等待
    3. 有限等待，在外等待的进程，要保证在有限时间可进入
    4. 让权等待，进程有CPU 没有资源时，不能进入自己的临界区，要立即释放 CPU 资源，避免忙等
22. 信 量机制
23. 信 量S的物理意义，S>=0表示资源的可用数，S
24. PV 操作是实现同步和互斥的常用方法
    1. P 表示申请一个资源（S = S-1，可以理解为从信 量S 中申请出一个来使用，申请后 S
    2. V 表示释放一个资源（S = S+1，可以理解为 释放一个资源到信 量，释放后，S
25. PV 操作实现进程互斥
26. 令信 量 mutex 初值为 1，当进入临界区时 执行 P操作，退出临界区时执行V 操作，这两就利用PV 实现代码互斥
27. PV 操作实现进程的同步
28. 单缓冲区同步(缓冲区只能放一个产品)：分为生产者和消费者，需要设置两个信 量, S1 初值为 1表示可放入缓冲区的产品数，S2 初值为0，表示可从缓冲区取出的产品数；每次生产产品 要进行 P(S1) 和 V(S2), 每次消费产品要进行 P(S2) V(S1)
29. 多缓冲区同步(缓冲区可以放多个产品)：在 单缓冲区的基础上增加一个信 量 S, 名为互斥信 量，初始值为 1，标记缓冲区可操作的量（缓冲区是个互斥资源）；每次生产产品及消费产品是都要增加一个 P(S1) P(S) V(S) V(S2) 操作, S 的PV 操作放中间
30. 死锁：
31. 同类资源分配不当引起的死锁：若采用的资源分配策略是，轮流的为每个进程分配，则可能会导致分配几轮后，没有一个进程达到所需的资源数，这个时候，每个进程都在等待资源分配，形成死锁；
32. 同类资源分配不当引起的死锁的解法：m 为资源总量、n 为进程数、k 为每个进程需要的资源，满足 m >= n * (k-1) + 1 就可以避免死锁
33. 进程资源图
34. Pi 代表进程，Ri 代表资源类型；每个 Ri 可以有多个资源； 指向进程的箭头表示分配资源；指向资源的箭头表示申请资源；
35. 先分配资源再申请资源，经过分配申请后没有满足资源的进程即为“阻塞”
36. 是否可化简：取决于是否可以在某个进程完成后释放资源，并使得后续进程得以完成
37. 可化简的就是非死锁的
38. 死锁避免
39. 死锁处理策略：鸵鸟策略（不理睬）、预防策略、避免策略、检测与解除死锁
40. 死锁避免算法：银行家算法，即在每次分配资源前检测分配资源后系统是否安全（是否安全取决与分配资源后，系统是否可以有某种进行序列，来将所有的进程都执行完），资源利用率高，但增加了检测的开销
41. 银行家算法题计算：，1. 先算出仍需资源数，2.在算出，剩余资源数
42. 线程
43. 进程在创建、撤销、切换中，系统会付出较大的时空开销，故系统引入的进程不易过多，进程切换频率不易太高，因此引入了线程
44. 线程作为调度和分配的基本单位，进程作为独立分配资源的单位，线程是进程中的一个实体
45. 线程与线程之间不可见，但是线程与线程可以共享进程的资源
46. 局部性原理
47. 时间局限性：程序的某一条指令执行，那在不久的将来该指令可能被再次执行，如果某个存储单元被访问，那不久的将来还可能被再次访问
48. 空间局限性：程序访问了某个存储单元，不久的将来其附近的存储单元也可能被访问
49. 相关题型“淘汰”问题：
    1. 在内存中才能被淘汰
    2. 先淘汰未访问过的
    3. 再淘汰未修改过的
50. 分页存储管理
51. 纯分页存储管理的地址结构： n位的页 + m位的页内地址
52. 做题技巧：
    1. 计算机的页面大小为4k => 则代表n位页内地址 2^n = 4 * 1024 => n=12
    2. 页面变换表逻辑地址转物理地址 => 逻辑地址即为纯分页存储管理的地址结构，由n位的页 + m位的页内地址组成 => 页内地址组成不变，将页 替换成“页面变换表”中对应的物理块 即可
53. 段页式存储管理
54. 段页式存储管理地址结构：n位段 + k位段内页 + m位的页内地址
55. 单缓冲区
56. 缓冲区只能有一个“作业”，缓冲区为空时可以输入，缓冲区有作业时可以传送
57. I/O设备 —输入(T)—> 缓冲区 —传送(M)—> 工作区(处理C)
58. 计算n个作业单缓冲区所花时间：(T+M)*n + C
59. 双缓冲区
60. 缓冲区有两个，每个可存一个”作业“
61. 计算n个作业双缓冲区所花时间： T*n + M + C
62. 磁盘调度算法
63. 先来先服务（FCFS）: 按请求访问者的先后顺序来启动磁盘驱动器，平均寻道长度大
64. 最短寻道时间优先（SSTF）:让距离当前磁道位置最短的先执行，不考虑访问者的先后顺序
65. 扫描算法或者电梯调度算法（SCAN）: 从磁头当前位置开始，沿着磁头移动方向，选择最近的柱面，如果磁头移动方向无请求柱面，则调转方向，选择最近的
66. 循环扫描算法（CSCAN）: 在扫描算法的基础上，调转方向后不再选择最近的柱面，而是移动到最里端
67. 旋转调度算法
68. 磁盘旋转不会停下，磁盘旋转完一个扇区，就代表读取了一个扇区的记录，记录读取后的处理时间内，磁盘不会停下
69. 如果是顺序处理n，总时间 = (读时间 + 扇区一圈时间)*(n-1) + 第一个扇区的读时间 + 第一个扇区的处理时间
70. 优化处理：重排扇区，让第一个扇区处理后所停在的位置，在第二个记录所在扇区的起始位置，所耗时 = (读时间+处理时间)*n
71. 多级索引结构
72. 直接地址索引：索引从0开始，一个地址项指向一个磁盘数据块
73. 一级间接地址索引：一个地址项指向一个磁盘索引块（也可以叫一级索引块），一个磁盘索引块又包含很多个地址项，磁盘索引块中的地址项指向一个磁盘数据块
74. 二级间接地址索引：比一级间接地址索引，多了一级磁盘索引块
75. 文件目录
76. 为了实现按名存取，系统为每个文件设置用于描述和控制的数据结构，至少包含文件名和存放文件的物理地址，这个结构称为文件数据块FCB
77. 文件目录是由文件控制块组成的，用来文件检索
78. 文件控制块包含三类信息
    1. 基本信息：文件名、文件物理地址、文件长度、文件块数等
    2. 存取控制信息：文件存取权限
    3. 使用信息：建立日期、最后修改日期、当前使用信息
79. 目录文件的修改时发生崩溃对系统的影响很大
80. 目录结构
81. 多级目录结构：倒置的有根树，也称为树形目录结构
82. 全路径名：从根目录开始，一直到文件名 D:
83. 绝对路径：从根目录开始，最后是 /
84. 相对路径：从当前目录开始，最后是 /
85. 位视图
86. 位视图用二进制来表示一个物理块的使用情况，0 表示空闲 1表示使用
87. 位视图的大小由磁盘空间大小（物理块数）决定，位视图描述能力强，适合各种物理结构
88. 假设计算机系统n位，那位视图第0个字能对应存储器上的第 0~n-1 物理块，第1个字能对应存储器上的第 n~2n-1 物理块后边以此类推
89. 其他
90. 可变式分区分配方案：进程P 有上邻空闲区 或 有下邻空闲区，那么 P进程释放后，空闲区合并成一个
91. 当用户通过鼠标或键盘进入某应用系统时，中断处理程序最先获得键盘或鼠标的输入信息
92. 实时操作系统的实时是指，计算机对于外来信息能够以足够快的速度处理，并在被控制对象允许的时间范围内做出快速响应
93. I/O 系统的层次结构：硬件 -》中断处理程序 -》设备驱动程序 -》设备无关程序 -》用户进程
94. I/O 软件隐藏了I/O操作的实现细节，方便用户使用
95. 磁盘调度管理中，先进行移臂调度在进行旋转，访问不同柱面信息时要先移臂调度，访问同一磁道只需要进行旋转