部分引用：

  1. https://blog.csdn.net/weixin_43914604/article/details/104415990
  2. https://blog.csdn.net/WangDou_Dou/article/details/122231755?spm=1001.2014.3001.5501

概念

C1

⚪什么是多道程序设计

多道程序系统设计是指允许多个程序（作业）同时进入一个计算机系统的内存储器并启动进行交替计算的方法。
充分发挥计算机系统部件的并行性，提高 CPU 的 (资源) 利用率。

e.g.1.多道程序设计的操作系统有以下特性：并发性、共享性、不确定性（异步性）、虚拟性。

①并发性。它是指两个或两个以上的事件或活动在同一时间间隔内发生。操作系 统是一个并发系统，并发性是它的重要特征，操作系统的并发性指计算机系统中同时 存在若干个运行着的程序，因此，它应该具有处理和调度多个程序同时执行的能力。 ②共享性。共享指计算机系统中的资源可被多个并发执行的用户程序和系统程序 共同使用，而不是被其中某一个程序所独占。共享有两种形式：其一是顺序共享。其 二是并发共享。 ③ 不确定性。不确定性也称异步性。在多道程序并发执行的环境中，各程序之间 存在着直接或间接的联系，程序的推进速度会受到运行环境的影响，若不能正确控制， 则执行结果会因为运行环境的不同而不同。 ④ 虚拟性。虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变 成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。所谓 虚拟是指物理上没有提供，但是逻辑上却具备的功能。在用户看来好像是物理上原来就 具有的功能一样。采用虚拟技术的目的是为了提高资源利用率和为用户提供易于使用、 方便高效的操作环境。

C3

⚪进程控制块（PCB）

操作系统为了管理进程专门设置的一个数据结构。
记录进程外部特征、描述进程运动变化过程（动态特征）。
PCB 是系统感知进程存在的唯一标志，进程与 PCB 一一对应。

谁创建的（用户id）、进程叫什么、进程id、进程组关系

⚪程序并发执行会有哪些特点

  • 程序执行间断性：并行的本质是程序交替串行。
  • 资源共享：使用相同的系统资源
  • 不确定性：每次，初始状态相同，进程执行的相对速度可能不同，资源使用和改变次序变化，结果不同。

⚪并发进程引入的目的是什么？会导致什么问题？

并发进程能共享计算机资源。这能使资源利用率大幅提升，CPU 和其他资源更能保持 “忙碌” 状态，系统吞吐量增大。
由于共享资源的原因，加上进程并发执行的随机性，一个进程对另一个进程的影响是不可预测的，这时就可能导致并发进程交替使用共享资源时出现 “与时间有关的错误”。

C4

⚪进程同步与互斥的概念

e.g.1.叙述进程的同步与互斥的区别和联系

并发进程执行会产生相互制约关系： 1） 互斥是进程之间竞争使用临界资源，只能让它们逐个使用，是一种竞争关系，也称间接制约关系。 2） 同步是进程之间的协同完成任务，在关键点上等待另一进程发来的消息，以便协同一致，是一种协作关系，也是直接制约关系。 3） 本质上，互斥是一种特殊的同步，因为它也是进程之间的执行次序上的一种协调。

⚪死锁的概念！

并发环境下，各进程竞争资源导致进程阻塞。
对不可剥夺资源的不合理分配会导致死锁。

处理死锁的 4 种方式对比：定义、异同、资源利用率！


 资源分配策略 ** **
死锁的预防 保守分配，宁可资源闲置 (即保证死锁不会发生) 适用于做突发式处理的进程，不需要进行剥夺 效率低，进程初始化的时间会延长；剥夺次数过多；不便灵活申请新资源
死锁的避免 是 “预防” 和 “检测” 的折中 (通过银行家算法判断，在运行过程中是否可能有死锁产生) 不需要进行剥夺 必须知道将来的资源需求；进程不能被长时间阻塞
死锁的检测与解除 定期检测是否有死锁的发生，若有则采取某种措施解除死锁 不会延长进程初始化的时间，允许对死锁进行现场处理 通过剥夺解除死锁会造成损失
  1. 预防：破坏死锁产生的必要条件（静态方法）

产生死锁的 4 个必要条件（必须同时满足）以及解决方法以及解决办法缺点：

互斥 （临界）
一个资源每次只能给一个进程使用		 SPOOLing 技术（资源共享） 仅满足小部分
不剥夺 （非抢占）
资源申请者不能强行地从资源占有者手中夺取资源，资源只能由占有者自愿释放		 直接释放 || 操作系统介入剥夺 实现复杂，系统开销大、导致饥饿
请求和保存 （部分分配，占有申请）
一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才 是动态申请，动态分配）。		 提前备好所有资源 资源利用率低、导致饥饿
循环等待 循环等待链 资源编号、顺序分配 资源浪费
  1. 避免：银行家算法（动态方法）

保证安全状态：以后需要的资源量不超过系统当前剩余资源量和所有进程所占有的资源量之和。


  1. 检测：“进程-资源分配图”

是否可完全简化（能经过一系列简化使所有进程成为孤立结点，则该图是可完全简化的；否则该图是不可完全简化的）

  1. 解除
  • 资源剥夺
  • 撤销进程

⚪三态模型

e.g.1.请简单叙述进程的三态模型的状态转化：就绪态↔运行态→等待态→就绪态
15FABD2B3DA5B5558DECF2A706908C26.png

①就绪态→运行态：当调度程序选择一个新的进程运行时，进程会由就绪态切换到 运行态； ②运行态→就绪态：当运行进程用完了获得的时间片时运行进程就会被中断由运行 态切换到就绪态，或是因为一高优先级进程处于就绪状态，正在运行的低优先级进程 即会被中断而由运行态切换到就绪态； ③运行态→等待态：以下几种情况会导致进程会由运行态切换到等待态，例如当一 进程必须等待时，或是操作系统尚未完成服务，进程对一资源的访问尚不能进行时， 还有初始化 I/O 且必须等待结果时，在进程间通信时 IPC（Inter-process Communication） 进程等待另一进程提供输入时； ④等待态→就绪态：当进程所等待的事件发生时，例如资源申请获得满足，或是等 待的数据或信号到来时，进程就可能由等待态切换到就绪态

C5

⚪静态 & 动态重定位

项目 描述 优点 缺点
静态重定位 在程序装入内存后，且在运行前，一次将需要转换的逻辑地址转换为物理地址的操作。 无须增加硬件地址转换机构，便于实现程序的静态连接。 [1] 程序的存储空间只能是连续的一篇区域，而且在重定位之后就不能移动，这不利于内存空间的有效使用。
[2] 各个用户进程很难共享内存中的同一程序副本。
动态重定位 在程序运行期间，每次访问内存之前都要进行的操作，它是靠硬件地址变换机制实现的。 [1] 程序占用的内存空间动态可变，也不必连续存放在一起。
[2] 比较容易实现几个进程对同一程序副本的共享使用。		 需要附加的硬件支持，增加了机器成本，而且实现存储管理的软件算法比较复杂。

⚪动态分区分配算法

动态分区/可变分区 首次适应算法等 概念

项目 算法原理语言描述 优点 缺点
首次适应 地址递增 / 从头到尾
找到第 1 个满足的		 综合性能最好
算法开销小		 低址部分碎片化
最佳适应 容量从小到大
优先小空使用间		 （对比首次适应）更多大空间保留
1. 产生小碎片
1. 算法开销大（排序）
最坏适应 容量递减
优先使用大空间		 （对比最佳适应）少了小碎片
1. 大分区容易用完，对大进程不友好
1. 算法开销大（排序）
临近适应
（循环首次适应）		 地址递增 / 从头到尾
循环
从上次结束地方开始		 算法开销小 由于每次的开始位置，导致（和最坏适应相同问题）高地址的大空间也容易用完，对大进程不友好

C6

⚪I/O 控制方式有？哪种 CPU 搬运最少

通道/DMA

  1. 程序直接控制：轮询；CPU忙等利用率低！
  2. 中断驱动：程序控制；一次一字的中断处理消耗 CPU 时间！
  3. DMA：仅开始和结束通知 CPU，过程绕过 CPU 直接存储、单位块；读写的只能是连续数据块！
  4. 通道控制：硬件，改进 DMA 只能连续读写的问题

CPU干预频率由高到低

⚪为什么引入缓冲？

目标是为了缓解什么？

  1. 为了改善 CPU 与外设之间速度不匹配的矛盾。
  2. 为了减少 I/O 对 CPU 的中断次数和放宽对 CPU 中断响应时间的要求。
  3. 为了提高 CPU 和 I/O 设备的并行性。

⚪磁道编号概念

（柱面号，盘面号，扇区号）
必须这个顺序的原因：磁头的移动消耗时间
image.png

扇区：同一盘面交替编号 & 不同盘面的柱面错位编号：减少延迟时间
读完一个要反应一会儿才会读下一个，这期间盘片又必须转，对于相邻的扇区…oh no 下一圈见

image.png

⚪磁盘读写访问具体操作流程

注意磁头共进退。
image.png
image.png

⚪什么是设备独立性？如何实现设备独立性？

用户进程独立于具体使用的物理设备。
（也就是说，进程只需用逻辑设备名称请求使用某类设备就可以了，当系统中有多台该类设备时，系统可将其中任一台分配给请求进程，而无需仅局限于某一台设备。）

系统通过设置一张逻辑设备表 LUT，将应用程序 (或用户程序) 中所使用的逻辑设备名称映射为物理设备名 (来实现设备的独立性)。

其它

⚠死锁

今年重点！！！

⚪逻辑地址

相关计算 概念：https://blog.csdn.net/weixin_43914604/article/details/105907291 题：https://blog.csdn.net/WangDou_Dou/article/details/120893128#t22

  1. 考虑一个由 8 个页面，每页有 1024 个字节组成的逻辑空间，把它装入到有 32 个物理块的存储器中
  2. 问：（1）逻辑地址需要多少二进制位表示？（2）物理地址需要多少二进制位表示？
  5. 因为页面数为 8 = 2^3，故需要 3 位二进制数表示页号。
  6. 每页有 1024 个字节，1024 = 2^10，于是页内地址需要 10 位二进制数表示页内地址；
  7. 内存中有 32 个物理块，故需要 5 位二进制数表示块号（32 = 2^5）。
  9.     （1）页的逻辑地址由页号和页内地址组成，所以需要 3 + 10 =13 位二进制数表示。
  10.     （2）页的物理地址由块号和页内地址的拼接，所以需要 5 + 10 = 15 位二进制数表示。

image.png

⚠磁盘

有计算，非大题，分高，计算量大。

⚪索引

选填有计算 混合索引 群里给过题目！

索引表（索引） vs 文件分配表（FAT，显示链接）：索引表是一个文件对应一张，FAT 是一个磁盘对应一张
image.png

  • 目录项记录索引块的位置，索引块中存储索引表，索引表指向数据块。
  • 注意逻辑块号不是必要的。

索引块中的索引表太大了咋办？同样可以链接（略）或索引
多层索引：类似多级页表。
混合索引：顶级索引表中，包含直接索引、各种多级索引

例题②：某系统中磁盘的每个盘块大小为 1KB，外存分配方法采用中的混合索引结构，
其中索引节点中直接地址 6 项，一级索引地址 2 项，二级索引地址 1 项，
每个盘块号占用 4 个字节，请问该系统中允许的文件最大长度是多少？

解：
因为，该系统中磁盘的每个盘块大小为 1KB，且每个盘块号占用 4 个字节。
故一个物理块可放：1KB / 4B ≈ 256 个 (物理块) 地址。

因为，索引节点中直接地址有 6 项，一级索引地址 2 项，二级索引地址 1 项。
所以该系统中允许的文件最大长度：
6×1KB+2×256×1KB+1×256^2×1KB=66,054KB (约为 66MB)

某个文件系统，采用混合索引分配方式为文件分配磁盘空间，FCB 中共有 13 个地址项，
每个盘块的大小为 512 字节，
如果每个盘块号只需要用 2 个字节来描述，则该 **文件系统** 需要设置几级间接索引？

2 个字节 = 16bit
2 字节能表示 2^16 = 65536 个地址
每个盘块能存放 512 ÷ 2 = 256 个盘块地址
10 + 256 < 65536 < 10 + 256 + 256^2
直接寻址 + 一次间接寻址 + 二次间址索引

某个文件系统，采用混合索引分配方式为文件分配磁盘空间，FCB 中共有 13 个地址项，
每个盘块的大小为 512 字节，
如果每个盘块号需要用 3 个字节来描述，共允许每个盘块中存放 170 个盘块地址，
而且 FCB 中采用 10 个直接地址项、1 个一级间接索引、1 个二级间接索引项和 1 个三级间接索引项，
则对某个长度为 18000000 字节的文件，它共需占用多少个盘块（包括索引块)?

https://blog.csdn.net/Wang_Dou_Dou_/article/details/122208409#t13

image.png

⚪磁盘读写访问、调度算法

image.png

  1. 先来先服务：FCFS：磁道分散时性能差

image.png

  1. 最短寻道时间优先：SSTF：本质贪心（眼前最优而非总体最优），会饥饿

image.png

  1. 扫描：SCAN：解决饥饿：电梯坐到底后必须回头：显然这样各位置响应频率不平均了

不做到底有 LOOK 算法
image.png

  1. 循环扫描：C-SCAN：增加坠机时间解决 SCAN 不平均问题

image.png

综合题 10分*4道

⚪PV

汤课件课后习题

操作系统_题型分析 - 图14

/* 基于 C 语言写的伪代码 */
semaphore c1 = 0, c2 = 0;    // c1、c2 分别是 A、B 组的计数器
semaphore S1 = 1, S2 = 1;    // S1、S2 分别是计数器 c1、c2 的互斥信号量
semaphore Sab = 1;            // Sab 是 a、b 两组间的互斥信号量
while(true)
{
    "A组进程 Ai():"        // i = 1, 2, 3, ..., a
    while(true)
    {
        P(S1);
        if( c1 == 0 )
            P(Sab);
        c1 = c1 + 1;
        V(S1);
        读文件 F;
        P(S1);
        c1 = c1 - 1;
        if( c1 == 0 )
            V(Sab);
        V(S1);        
    }

    "B组进程 Bj():"        // j = 1, 2, 3, ..., b
    while(true)
    {
        P(S2);
        if( c2 == 0 )
            P(Sab);
        c2 = c2 + 1;
        V(S2);
        读文件 F;
        P(S2);
        c2 = c2 - 1;
        if( c2 == 0 )
            V(Sab);
        V(S2);    
    }
}

操作系统_题型分析 - 图15
其实一模一样的…

⚪？银行家

Max - Allocation = Need
Available
Request

⚪两级调度

作业、进程调度 常用算法

考察抢占式！！！
考察平均周短时间！！！

频率 发生地点 做什么 进程状态变化
作业调度 高级调度 低频 外存 -> 内存 创建进程 无 -> 创建态 -> 就绪态
进程调度 低级调度 高频 内存 -> CPU 分配处理机 就绪态 -> 运行态

F8E6AFB544F5D7FCC80209D295E404F4.png

Craft 2.2.4&5

抢占式的几种算法：
早期算法：FCFS、SJF、HRRN

  • 抢占式短作业优先：最短剩余时间优先（抢占SJF->SRTN）：会饥饿

现：RR、优先级调度、多级反馈队列

  • 时间片轮转（RR）：就绪队列按顺序：时间片过长退化 FCFS，太短开销大
  • 抢占式优先级调度：就绪队列优先级高先：会饥饿
  • 多级反馈队列：多队列、有优先级：可能饥饿

⚪页面置换

3 个算法、缺页率

OPT：最佳置换算法：淘汰最长时间不使用：太过理想化
EE69071D318265FAFB591CE23527DE44.png

FIFO：先进先出：淘汰最早进入的：会产生贝拉迪现象（分配越多内存缺页越厉害）

LRU：最近最久未使用：注意和 FIFO 区分