操作系统原理——期末速成笔记

参考视频：
操作系统原理期末速成不挂科主攻大题

地址变换

![[操作系统原理期末速成不挂科主攻大题PT6M13.743S.png|操作系统原理期末速成不挂科主攻大题 - 06:13|1000]]

• 视频节点：06:13
  这里页面大小有一个转换关系：

$$1K \leftrightarrow 2^{10}$$

$$4K \leftrightarrow 2^{12}$$

$$1M \leftrightarrow 2^{20}$$

$$1G \leftrightarrow 2^{30}$$

补充一个基础知识（D 表示10进制，H 表示16进制）：

$$10\quad D = A\quad H$$

![[操作系统原理期末速成不挂科主攻大题PT13M3.606S.png|操作系统原理期末速成不挂科主攻大题 - 13:03|1000]]

• 视频节点：13:03

1. 先算出需要多少磁盘块：$磁盘块数=\frac{磁盘容量}{每个磁盘块的大小}$
2. 算出后，例如题目中 540K ，1.2M 处都进行了取整，因为到最后要把这个数变成仅用 $2^?$ 表示的数。
3. $?$ 的值即为位数，还要再 ÷ 8，这就算出了每个磁盘块的 FAT 表占用的空间为 $\frac{?}{8}$ 个字节（这一步如果不是整数，还要向上取整）。
4. 最后再乘磁盘数个数，即求得 FAT 表一共占用的空间。

---

分区分配

![[大题-分区分配算法PT11M25.638S.png|大题-分区分配算法 - 11:25|1000]]

• 视频节点：11:25

1. 将进程大小和分区大小比较，选择一个能装下的
2. 此时此分区的变换：
   • 起始地址要加上进程的大小
   • 分区大小要减去进程的大小

算法

首次适应（First Fit）

分区编号从小到大开始比较，直到找到满足条件的

最佳适应（Best Fit）

每次给新进程分配时，都扫描整个空闲内存块列表，寻找最小的、足够大以容纳请求的内存块。

特性	首次适应（First Fit）	最佳适应（Best Fit）
查找效率	快，停止在第一个合适的块	慢，需要扫描整个空闲块列表
内存碎片化	产生较多的外部碎片	产生较多的小碎片
实现复杂度	简单	复杂，需要对所有块进行比较
使用场景	简单和快速分配的情况	尽量减少内存浪费的场景

---

页面置换算法

![[大题-页面置换算法PT12M44S.png|大题-页面置换算法 - 12:44|1000]]

• 视频节点：12:44

FIFO（First In, First Out）算法

最早进入内存的页面会被最先移出

LRU（Least Recently Used）算法

又名最近最少使用（最近最久未使用）算法。
每次选择最近最少使用的页面进行替换。即，如果一个页面长时间未被访问，那么它更可能在未来一段时间内不再被访问，因此应该被替换。

OPT（Optimal）算法

理论最优的算法。
在页面置换时，总是选择那个在未来最长时间内不会被使用的页面进行替换。

处理机调度

基本概念

大题-处理机调度算法 - 05:09|1000

• 视频节点：05:06 以 FCFS 调度（First-Come, First-Served） 为例：
  

  

  本题在 FCFS 算法下的情况

服务时间 & 执行时间（Burst Time）

完成任务，CPU所需要的时间。

到达时间

进程进入操作系统就绪队列的时刻。
一旦 CPU 执行完一个进程进入空闲状态时，就会按照一定顺序处理就绪队列里的任务。

这里有一个反直觉的假设：

即使进程到达时间相同，它们的到达顺序和队列排序也是可以区分的。

完成时间

一个进程完成执行的时刻。
等于前面所有进程的服务时间加上自身的服务时间。

周转时间

周转时间是一个进程从提交到完成所需要的总时间。
等于完成时间 - 到达时间

带权周转时间

等于周转时间 ÷ 执行时间。

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

除以总进程数即可。

算法

FCFS 调度（First-Come, First-Served）

先进入等待队列的进程将先执行。
⚠️ 即使进程到达时间相同，它们的到达顺序和队列排序也是可以区分的。

SJF（Shortest Job First）

执行时间（Burst Time）最短的进程会被优先执行。

• 一些细节：

  1. 初始化： 系统开始时会查看就绪队列中所有已经到达的进程，计算它们的执行时间（Burst Time）。

  2. 选择最短作业执行： 每次CPU空闲时，操作系统会从所有已经到达并在就绪队列中的进程中，选择执行时间最短的一个进程。这个选择会根据当前时刻已到达的所有进程来判断，而不是一次性决定所有进程的执行顺序。

  3. 执行完一个进程后，重新检查：每当一个进程执行完（即服务时间或执行时间完成），操作系统会重新检查当前已到达的进程，再次选择其中执行时间最短的进程。如果有多个进程的执行时间相同，系统会按照FCFS的顺序（先到先服务）来选择。

高响应比优先（HRN，Highest Response Ratio Next）

公式

$$相应比=\frac{等待时间+服务时间}{服务时间}=\frac{周转时间}{服务时间}$$

抢占式 & 非抢占式

• 抢占式：在高响应比优先算法中，若一个新的进程到达时，其响应比比当前正在执行的进程的响应比更大，则当前进程会被抢占，新的进程会执行。
• 非抢占式：如果使用非抢占式高响应比优先调度，如果有新的进程到达，只有当当前进程执行完毕时，才会考虑调度新的进程。

---

银行家算法

![[大题-银行家算法PT10M51.753S.png|大题-银行家算法 - 10:51|1000]]

• 视频节点：10:51
  银行家算法的核心思想是：在进程请求资源时，系统会检查这些请求是否会导致系统进入不安全状态。如果请求会导致系统进入不安全状态，那么请求将被拒绝，否则允许资源分配。

为了实现这一目标，银行家算法维护了以下几个重要数据结构：

关键数据结构

Available：

一个数组，表示当前系统中各类型资源的可用数量。

Max：

一个矩阵，表示每个进程在执行过程中所需的各类型资源的最大需求量。

Allocation：

一个矩阵，表示当前各进程已分配的资源数量。

Need：

一个矩阵，表示每个进程还需要的各类型资源数量。计算方式是 Need = Max - Allocation。

request 引起的重新推演

当进程发出新的 request( , , , …) 的时候，各关键值的变化：

• Available: 减去request
• Need: 减去request
• Allocation: 加上request
  然后用更新后的值继续推演最终 Available 是否等于题目给的总资源量。