操作系统综合题
操作系统综合题
🕰️ 调度算法 Scheduling Algorithms 详细笔记
🌟 基础概念 Basic Concepts
✅ 周转时间（Turnaround Time）
定义： 一个进程从提交到完成所经历的总时间。 计算：
周转时间=完成时间−提交时间 = -
⚠️ 忽略进程切换（context switch）时间时：
周转时间=等待时间+运行时间 = +
原因： 进程执行的整个周期只包含运行或等待两个状态。
✅ 常用评价指标 Performance Metrics
| 指标 | 英文 | 含义 |
|---|---|---|
| 吞吐量 | Throughput | 单位时间内完成的进程数 |
| 周转时间 | Turnaround Time | 单个进程从提交到完成的时间 |
| 平均周转时间 | Average Turnaround Time | 所有进程周转时间的平均 |
| 带权周转时间 | Weighted Turnaround Time | 周转时间 / 运行时间 |
| 平均带权周转时间 | Avg. Weighted Turnaround Time | 所有进程带权周转时间的平均 |
📋 各类调度算法详解
A. 先来先服务（FCFS: First-Come First-Served）
特点：
- 按提交顺序排队调度
- 简单易实现
- 可能产生“护航效应（Convoy Effect）”
缺点：
- 平均等待时间可能较大
- 短作业可能因排在长作业后而等待很久
B. 最短作业优先（SJF: Shortest Job First）
特点：
- 总是选择运行时间最短的作业
- 平均周转时间最短
缺点：
- 不利于长作业
- 需要预知作业长度
C. 最短剩余时间优先（SRTF: Shortest Remaining Time First）
特点：
- 是 SJF 的抢占式版本
- 如果新到进程的剩余时间小于当前运行的进程，则抢占
优点：
- 理论上能达到最优平均等待时间
缺点：
- 计算复杂
- 可能导致长作业长时间得不到运行（饥饿）
D. 时间片轮转（Round Robin, RR）
特点：
- 所有进程排队，每次运行一个时间片（quantum）
- 时间片结束就抢占，放到队尾
优点：
- 公平，适合时间共享系统
- 响应快
缺点：
- 时间片太短：切换开销大；太长：接近FCFS
E. 优先级调度（Priority Scheduling）
特点：
- 为每个进程分配优先级，高优先级先调度
问题：
- 饥饿问题（starvation）：低优先级可能永远得不到调度
解决方案：
- 优先级老化（Aging）：随着等待时间增长提升优先级
F. 多队列调度（Multi-Queue Scheduling）
特点：
- 将进程分成不同优先级的队列（如前台、后台）
- 每个队列可以有自己的调度策略（如FCFS、RR）
调度策略示例：
- 比如前台采用RR，后台采用FCFS
- 队列之间的CPU时间按比例分配
G. 多级反馈队列（Multilevel Feedback Queue, MLFQ）
特点：
- 动态调节优先级：运行时间越长，优先级越低
- 新进程从高优先级队列开始
- 如果未完成→降级→放入低优先级队列
优点：
- 综合考虑响应性与公平性
- 广泛用于现代操作系统
H. 最短进程优先（SPF: Shortest Process First）
📌 有时与 SJF 同义，有时更强调运行总时间最短的进程优先
I. 保证调度（Guaranteed Scheduling）
思想：
- 按承诺向用户提供公平资源
- 记录每个进程“应得的时间”与“实际获得的时间”之比
- 比例越低者优先运行（优待落后的进程）
优点：
- 提供公平保障
- 控制饥饿和不平衡
J. 彩票调度（Lottery Scheduling）
思想：
- 每个进程持有一定数量的“彩票”
- 抽奖决定谁获得 CPU
- 彩票数量可随优先级动态调整
优点：
- 实现公平 + 动态可调
- 易于实现分配比例控制
K. 公平分享调度（Fair-Share Scheduling）
特点：
- 以“用户”为单位控制资源（而非以进程为单位）
- 保证每个用户获得公平资源
举例：
- 用户A有5个进程，B有1个。系统会让B的进程比A的每个进程运行得更多，以实现用户公平。
📊 对比小结（调度算法优缺点）
| 算法 | 是否抢占 | 公平性 | 是否考虑运行时间 | 适用场景 |
|---|---|---|---|---|
| FCFS | 否 | 差 | 否 | 批处理 |
| SJF | 否 | 差 | 是 | 知道作业时长 |
| SRTF | 是 | 差 | 是 | 响应性要求高 |
| RR | 是 | 好 | 否 | 时间共享系统 |
| 优先级 | 可抢占 | 差（饥饿） | 否 | 实时任务 |
| MLFQ | 是 | 好 | 否 | 综合性操作系统 |
| 彩票调度 | 是 | 好 | 否 | 动态比例控制 |
| 保证调度 | 是 | 好 | 否 | 面向服务承诺系统 |
| Fair-Share | 是 | 用户公平 | 否 | 多用户共享系统 |
💀 死锁（Deadlock） 详细笔记
✅ 一、死锁的定义（Definition）
死锁（Deadlock）： 当多个进程因争夺资源而造成的一种互相等待的现象。 一旦发生死锁，除非外力干预，否则进程将永远阻塞。
✅ 二、系统模型（System Model）
系统中存在：
- 一组进程 {P1,P2,...,Pn}{P_1, P_2, ..., P_n}
- 一组资源类型 {R1,R2,...,Rm}{R_1, R_2, ..., R_m}
每类资源可以有多个实例。进程通过以下操作使用资源：
- 请求（request）
- 使用（use）
- 释放（release）
✅ 三、死锁的四个必要条件（Necessary Conditions for Deadlock）
只要同时满足以下四个条件，系统就可能进入死锁状态。
| 条件 | 中文名称 | 英文名称 | 含义 |
|---|---|---|---|
| ① | 互斥条件 | Mutual Exclusion | 至少有一个资源在任一时刻只能由一个进程占用。 |
| ② | 占有且等待 | Hold and Wait | 至少有一个进程占有资源的同时等待其他进程占用的资源。 |
| ③ | 不可抢占 | No Preemption | 已分配的资源不能被系统强行抢占，只能由占有者释放。 |
| ④ | 循环等待 | Circular Wait | 存在一个进程循环链，每个进程都在等待下一个进程占用的资源。 |
🧠 快速记忆口诀：
“互占不让还循环” 互斥、占有、不可抢、循环等待
✅ 四、死锁的处理策略（Deadlock Handling Strategies）
死锁处理的方式主要有以下四种：
1. 鸵鸟策略（The Ostrich Algorithm）
- 什么都不做，忽略死锁。
- 适用于死锁几率极低或代价太高的系统。
2. 死锁预防（Deadlock Prevention）
核心思想：破坏四个必要条件之一 常见方法如下：
| 条件 | 破坏策略 |
|---|---|
| 互斥 | 使用可共享资源（不常见） |
| 占有等待 | 要求一次性申请所有资源 |
| 不可抢占 | 若得不到资源，则释放已有资源后重试 |
| 环路等待 | 给资源编号，按升序申请资源，防止形成循环 |
3. 死锁避免（Deadlock Avoidance）
核心思想：不进入不安全状态 代表算法：银行家算法（Banker's Algorithm）
要求：
- 进程在开始时声明最大资源需求
- 系统在每次资源分配时判断“是否安全”
4. 死锁检测与恢复（Deadlock Detection and Recovery）
核心思想：允许死锁发生，之后检测和恢复
步骤：
- 定期运行死锁检测算法（如资源分配图）
- 若检测到死锁，选择：
- 撤销进程
- 回收资源
- 进程回退
✅ 五、图示理解：资源分配图（Resource Allocation Graph, RAG）
节点类型：
- 圆形节点：进程 PiP_i
- 方形节点：资源 RjR_j
边类型：
- 请求边：进程 → 资源（表示正在请求）
- 分配边：资源 → 进程（表示资源已分配）
判断死锁：
- 如果图中存在一个环路，则可能发生死锁
- 若每类资源仅有一个实例，存在环 = 死锁
✅ 六、经典例子：哲学家就餐问题（Dining Philosophers Problem）
- 5位哲学家围坐圆桌，筷子放在哲学家之间
- 每人要左右两根筷子才能吃饭
- 若每人同时拿左手边的筷子 → 死锁！
解决思路：
- 引入限制（例如最多只能有4人同时拿起一根筷子）
- 编号资源并按序申请
🌟页面置换算法概述
当发生缺页中断（page fault）时，如果内存已满，需要将某个页面换出内存，为新页面腾出空间。页面置换算法负责决定换出哪个页面。
一、最优页面置换算法（Optimal Page Replacement，OPT）
- 思想：替换未来最长时间内不会被访问的页面。
- 优点：理论上缺页次数最少，是理想的参考算法。
- 缺点：需要预知未来页面访问顺序，因此只能用于模拟或性能比较。
- 关键：淘汰“未来最后使用的页面”。
二、NRU算法（Not Recently Used）
- 依靠 R 位（Referenced）和 M 位（Modified）
- R：是否被访问过
- M：是否被修改过
- 操作方式：
- 启动时，所有页面 R 和 M 设置为 0。
- 每次时钟中断时，清除所有页面的 R 位。
- 缺页时，将页面分为四类：
- 类 0：R=0，M=0（最理想）
- 类 1：R=0，M=1
- 类 2：R=1，M=0
- 类 3：R=1，M=1（最不理想）
- 随机从编号最小的非空类中选一页置换。
三、先进先出算法（FIFO）
- 思想：淘汰最早进入内存的页面。
- 实现：维护一个队列，先进的先出。
- 问题：可能淘汰“经常使用”的页面（不考虑页面使用频率）。
四、第二次机会算法（Second-Chance）
- 在 FIFO 的基础上引入 R 位判断
- 操作流程：
- 检查队首页面 R 位：
- 若 R=0：淘汰该页面。
- 若 R=1：将 R 清 0，把页面放到队尾（认为它刚进入过），继续检查下一个页面。
- 检查队首页面 R 位：
- 目标：给被访问过的页面“第二次机会”避免立即被淘汰。
- 缺点：频繁移动页面，效率较低。
五、时钟页面置换算法（Clock Algorithm）
- 第二次机会算法的优化版
- 实现方式：
- 将页面组成环形队列，每个页面挂在一个“钟面”位置。
- 有一个指针（表针）指向当前候选页面。
- 若指针指向的页面：
- R=0：淘汰并替换此页，表针移动到下一个。
- R=1：将 R 清 0，表针向前移动一格。
- 重复直到找到 R=0 的页面为止。
- 优点：实现效率高，性能接近 LRU。
六、最近最少使用算法（Least Recently Used, LRU）
- 思想：淘汰最久没有被访问的页面。
- 实现方式：
- 用链表/栈/时间戳记录每个页面上次使用时间。
- 缺点：硬件实现复杂、成本高。
- 常见近似实现：
- Aging 算法
七、Aging（老化）算法（LRU 的近似实现）
- 思想：用一个8位寄存器记录页面“访问历史”，每时钟周期右移一位。
- 操作流程：
- 每个时钟周期：
- 所有页面的 aging 寄存器右移一位。
- 若某页面 R=1，其最高位变成 1。
- 然后将所有 R 位清 0。
- 缺页时：淘汰 aging 值最小的页面。
- 每个时钟周期：
- 优点：近似 LRU，硬件开销较小。
🔁 小结：置换算法比较表
| 算法 | 是否考虑使用频率 | 是否考虑最近使用 | 实现成本 | 优劣情况 |
|---|---|---|---|---|
| OPT | ✔️（未来） | ✔️（未来） | ❌ | 理想但无法实现 |
| FIFO | ❌ | ❌ | ✅ | 简单但可能误淘 |
| NRU | ✔️（R,M） | ✔️（R） | ✅ | 近似，效果一般 |
| Second-Chance | ✔️（R） | ✔️ | ✅ | 给页面第二次机会 |
| Clock | ✔️（R） | ✔️ | ✅✅ | 实用性强 |
| LRU | ✔️ | ✔️ | ❌ | 效果好但难实现 |
| Aging | ✔️（近似） | ✔️（近似） | ✅✅ | 实用的近似LRU算法 |
分页 (Paging) 和 分段 (Segmentation)
1. 分页 (Paging)
分页是一种将物理内存分为固定大小块的内存管理方式。每个块称为页面（Page），而虚拟内存也被划分为与物理页面大小相同的虚拟页面。分页的目的是解决内存的连续分配问题，允许非连续的物理内存分配。
内部碎片 (Internal Fragmentation) 由于每个页面的大小固定，而实际使用的空间可能小于页面大小，导致每个页面内部可能有未使用的空间，这部分未使用的空间称为内部碎片。分页方式下，内部碎片的产生是不可避免的。
2. 分段 (Segmentation)
分段是将程序或数据分为多个具有不同意义的部分（如代码段、数据段、栈段等）。每个段可以具有不同的大小，因此可以更灵活地管理内存。
外部碎片 (External Fragmentation) 由于分段使用的是不等长的内存块，当程序需要的内存量不连续时，内存中会产生一些未被利用的空闲空间，这部分未被利用的空间称为外部碎片。外部碎片随着内存的分配和释放而不断增加。
空闲内存管理方法
空闲内存管理的目的是有效地分配和回收内存，避免碎片化，常见的管理方法包括位图存储管理和链表存储管理。
1. 位图存储管理 (Bitmap Allocation)
位图存储管理使用一个位图（Bitmap）来表示内存的使用情况。每一位对应内存的一块（如一个页面或一个内存块），位为0表示该内存块空闲，位为1表示该内存块已被分配。
优点：
- 管理简单，空间开销较小。
- 可以快速地找到空闲块的位置。
缺点：
- 如果内存块较小，位图可能会很大，增加额外的内存开销。
- 查询一个块是否空闲需要扫描位图，可能效率较低。
2. 链表存储管理 (Linked List Allocation)
链表存储管理通过链表来表示内存的使用情况。每个内存块的控制块包含指向下一个内存块的指针，可以通过遍历链表找到空闲块并进行分配。
优点：
- 动态分配内存，适用于任意大小的内存块。
- 内存分配和回收比较灵活。
缺点：
- 对内存块的访问需要遍历链表，可能增加时间复杂度。
- 会有额外的指针开销。
内存分配算法
内存分配算法用于决定如何选择空闲内存块进行分配。常见的算法有：
1. 首次适配 (First Fit)
首次适配算法从头开始搜索空闲内存列表，找到第一个足够大的空闲块并分配。如果找不到合适的块，则返回失败。
优点：
- 实现简单，分配效率较高。
- 对于小块内存的分配较为有效。
缺点：
- 可能会导致外部碎片，特别是在频繁分配和释放内存时。
2. 下次适配 (Next Fit)
下次适配算法与首次适配类似，但它不是从内存的开头开始查找，而是从上次分配结束的位置开始查找。
优点：
- 可以避免首次适配导致的过多集中分配，减少外部碎片。
缺点：
- 如果分配的内存较大，可能仍然会导致外部碎片。
3. 最佳适配 (Best Fit)
最佳适配算法遍历所有空闲内存块，选择最适合当前请求的最小块进行分配。这样可以尽量减少剩余的碎片。
优点：
- 尽量减少未使用空间的碎片。
缺点：
- 查找最适合的内存块需要遍历所有空闲块，可能会增加搜索时间。
- 可能会造成大量的小空闲块，增加内存碎片。
4. 最差适配 (Worst Fit)
最差适配算法选择最大的空闲内存块进行分配。这样可以保证剩余的空闲块相对较大，有利于未来的分配。
优点：
- 可以保证剩余的空闲块较大，减少小碎片。
缺点：
- 查找最大的空闲块可能需要遍历所有空闲块，效率较低。
- 可能导致一些内存块过于分散，增加外部碎片。
5. 快速适配 (Quick Fit)
快速适配算法通过预先维护多个空闲链表，每个链表代表固定大小的空闲块。当请求分配某一特定大小的内存时，直接从相应的链表中取出。
优点：
- 分配和回收都非常迅速。
- 通过精细化的分区管理，减少外部碎片。
缺点：
- 需要额外的空间来维护多个链表。
- 可能会导致部分内存块无法有效利用，增加内部碎片。
总结
- 分页和分段分别解决了内存管理中的不同问题。分页减少了内存连续性的要求，但可能导致内部碎片；分段则更加灵活，但可能会导致外部碎片。
- 内存管理有多种方法，使用位图和链表都可以有效地管理内存块，选择不同的管理方式有其各自的优缺点。
- 内存分配算法提供了不同的策略来减少碎片化，选择合适的算法可以提高内存的使用效率，减少碎片化。
内核态 (Kernel Mode) 与 用户态 (User Mode)
在计算机系统中，操作系统将程序的执行分为两种模式：内核态 (Kernel Mode) 和 用户态 (User Mode)。
- 内核态 (Kernel Mode)
- 在内核态下，程序有权限访问系统的所有资源，包括硬件和内存。
- 操作系统的内核代码在此模式下执行，系统调用、硬件驱动程序、资源管理等都运行在内核态。
- 内核态具有最高的权限，因此能够执行特权操作，例如内存分配、进程调度等。
- 用户态 (User Mode)
- 用户态是用户程序执行的模式，具有较低的权限，不能直接访问硬件资源。
- 在用户态下，程序只能通过系统调用来请求操作系统服务，避免了直接控制硬件的风险。
- 用户态程序会受到操作系统的保护，无法进行任何可能破坏系统稳定性或安全性的操作。
用户程序通常从用户态开始运行，只有在进行系统调用（如文件操作、网络通信等）时，才会切换到内核态。
用户级线程 (User-level Threads)
用户级线程是由应用程序管理的线程，操作系统内核对其并不直接感知。
特点：
- 由应用程序管理
- 用户级线程的管理完全在用户空间进行，操作系统内核不需要参与线程的创建、调度和销毁。
- 内核不感知线程
- 操作系统并不知道用户级线程的存在。线程的管理和调度由用户级线程库（如 POSIX Threads, pthreads）处理。
- 上下文切换便宜
- 由于不涉及内核，用户级线程的上下文切换（从一个线程切换到另一个线程）非常快速和高效。
- 可以创建任意数量的线程
- 因为线程的管理完全由用户控制，所以下限是应用程序的内存和处理器能力，理论上可以创建任意多的线程。
- 必须小心使用
- 用户级线程并不由操作系统直接调度和管理，可能会遇到如多核CPU利用不完全、线程阻塞等问题。使用时需要谨慎设计，确保应用程序的线程调度合理，避免不必要的性能问题。
优点：
- 线程创建和销毁速度较快，消耗较少的内存。
- 可以创建大量的线程而不依赖内核的资源限制。
- 适用于需要大量轻量级线程的应用场景，如并行计算、网络服务等。
缺点：
- 用户级线程无法利用多核处理器的优势，因为操作系统无法感知线程，因此无法进行多核分配。
- 如果用户级线程中的一个线程被阻塞（如 I/O 操作），整个进程会被阻塞，因为操作系统看不到线程的存在。
- 用户级线程需要由应用程序自己管理，因此开发和调试难度较大。
内核级线程 (Kernel-level Threads)
内核级线程是由操作系统内核管理的线程，操作系统对这些线程的状态和调度有完全控制。
特点：
- 由内核管理
- 内核级线程的创建、调度、销毁等操作完全由操作系统内核管理，操作系统会分配必要的资源并调度执行。
- 消耗内核资源
- 每个内核级线程都需要操作系统为其分配内核资源（如内存、线程控制块等）。这使得内核级线程的管理和调度比用户级线程更消耗资源。
- 上下文切换开销大
- 内核级线程的上下文切换需要操作系统进行干预，涉及到从用户态到内核态的切换，因此相较于用户级线程，上下文切换的开销较大。
- 线程数量受限于内核资源
- 内核级线程的数量受到操作系统的资源限制，线程的创建和调度都会消耗系统资源，因此线程的数量通常较少。
- 更容易使用
- 由于操作系统内核负责线程的管理，程序员无需关心线程的调度和上下文切换，内核会自动进行处理，程序员只需要关注线程的创建和同步。
优点：
- 可以有效利用多核处理器，因为操作系统内核会调度线程到不同的 CPU 核心上运行。
- 内核能感知线程的状态，因此在多核环境下，操作系统可以更高效地进行调度。
- 线程阻塞不会导致整个进程的阻塞。内核可以在另一个线程上调度运行，避免进程整体挂起。
缺点：
- 线程创建和销毁的速度相对较慢，因为需要内核介入。
- 内核级线程的管理消耗了更多的系统资源，包括内存和 CPU 时间。
- 内核的上下文切换开销较大，可能导致性能下降。
用户级线程与内核级线程的对比
| 特性 | 用户级线程 (User-level Thread) | 内核级线程 (Kernel-level Thread) |
|---|---|---|
| 管理 | 由应用程序管理 | 由操作系统内核管理 |
| 内核感知 | 内核无法感知 | 内核完全感知 |
| 上下文切换开销 | 低 | 高 |
| 线程数量限制 | 不受内核限制，可以创建任意多线程 | 受内核资源限制，数量有限 |
| 资源消耗 | 较少，主要消耗用户空间 | 消耗内核资源，如线程控制块等 |
| 多核利用 | 无法有效利用多核 | 可以有效利用多核 |
| 阻塞影响 | 一个线程阻塞会导致整个进程阻塞 | 线程阻塞时，内核可以切换其他线程运行 |
| 适用场景 | 适用于需要大量轻量级线程的应用场景 | 适用于需要充分利用系统资源、支持多核的场景 |
总结
- 用户级线程适用于轻量级、创建数量多的线程管理场景，但需要谨慎设计以避免线程阻塞和效率问题。
- 内核级线程适用于需要更强系统调度和多核支持的场景，虽然它们的管理和调度开销较大，但能够充分利用现代操作系统的优势，提供更好的并发处理能力。
选择使用用户级线程还是内核级线程，主要取决于应用场景的需求，性能要求，以及系统资源的限制。
信号量（Semaphore）
信号量是一种用于进程间同步和互斥的机制，它用于控制访问共享资源的进程数量，确保在多进程环境中，资源的分配和回收不会发生冲突。信号量的操作包括 P 操作 和 V 操作，它们用于申请和释放资源。
1. P 操作（Proberen，申请资源）
- P(S)：执行 P 操作时，信号量 S 减少1（即 S = S - 1），表示一个资源被分配。
- 过程：
- 如果 S >= 0，表示有可用资源，进程可以继续执行。
- 如果 S < 0，表示没有足够的资源，进程需要进入信号量的等待队列，挂起等待。
- 作用：P 操作保证了资源的申请是互斥的，即当一个进程申请资源时，其他进程不能同时占用该资源，避免了并发冲突。
2. V 操作（Verhogen，释放资源）
- V(S)：执行 V 操作时，信号量 S 增加1（即 S = S + 1），表示一个资源被释放。
- 过程：
- 如果 S > 0，表示有足够的资源，进程可以继续执行。
- 如果 S <= 0，表示有进程在等待队列中，操作系统会唤醒一个等待的进程，允许它继续执行。
- 作用：V 操作负责释放资源，并在有进程等待资源时唤醒一个等待队列中的进程。
信号量总结：
- S ≥ 0：表示有可用资源。
- S < 0：表示没有可用资源，进程需要进入等待队列。
- 信号量的一个重要特性是它用于控制并发访问资源的数量，确保多个进程不会同时访问资源，造成冲突。
银行家算法（Banker's Algorithm）
银行家算法是一种用于避免死锁的资源分配和安全性算法，特别适用于具有多个资源和多个进程的系统。该算法通过模拟银行对客户的信用授予方式，来判断是否安全地分配资源。银行家算法的核心思想是：在任何时刻，资源的分配不能超过系统的最大需求，且分配后必须确保系统最终能进入安全状态。
1. 概念与基本原则
- 安全状态：系统处于安全状态时，表示存在一种顺序，使得所有进程最终都能获得足够的资源并顺利完成。换句话说，系统在这种状态下不会进入死锁。
- 最大需求矩阵：每个进程对各类资源的最大需求。
- 当前资源矩阵：每个进程当前已经分配的资源。
- 可用资源矩阵：系统当前未分配的资源数量。
2. 算法步骤
- 步骤 1：每个进程在开始时都声明它的最大需求（即需要的最大资源量）。当进程运行时，它会获得当前资源的分配，使用一部分资源。
- 步骤 2：每次进程请求资源时，系统会检查是否能满足进程的请求。如果请求超过进程的最大需求，则拒绝。
- 步骤
3：系统检查满足进程请求后是否仍能保持安全状态：
- 将请求的资源分配给进程后，检查是否存在一种进程执行的顺序，使得所有进程都可以顺利完成（即系统是否处于安全状态）。
- 步骤 4：如果存在安全顺序，则批准资源请求，更新资源状态。如果不存在安全顺序，则拒绝资源请求。
3. 安全性检查
- 系统进行“安全性检查”时，会通过模拟进程执行来判断系统是否处于安全状态：
- 假设某个进程请求了资源，并且假设系统分配了这些资源。
- 系统检查是否有至少一个进程能够完成执行（即它所需的资源可以完全分配给它）。
- 如果有，则假设该进程执行完成后会释放资源，并且继续分配给其他进程。
- 如果所有进程都可以在某个顺序下完成，系统就是安全的。
- 如果没有这种执行顺序，则系统不安全，拒绝该进程的请求。
4. 银行家算法的核心矩阵
- 最大需求矩阵
Max：每个进程对各类资源的最大需求。 - 已分配矩阵
Alloc：每个进程当前已分配的资源数量。 - 需求矩阵
Need：每个进程的资源需求，Need = Max - Alloc。 - 可用资源向量
Available：当前系统中未分配的资源数量。
5. 银行家算法的例子
假设有 3 个资源类型（A、B、C）和 5 个进程（P1, P2, P3, P4, P5）。它们的资源信息如下：
| 进程 | 最大需求 A | 最大需求 B | 最大需求 C | 已分配 A | 已分配 B | 已分配 C |
|---|---|---|---|---|---|---|
| P1 | 7 | 5 | 3 | 2 | 1 | 1 |
| P2 | 3 | 2 | 2 | 2 | 1 | 1 |
| P3 | 9 | 0 | 2 | 3 | 2 | 2 |
| P4 | 2 | 2 | 2 | 2 | 1 | 1 |
| P5 | 4 | 3 | 3 | 0 | 0 | 2 |
- 可用资源：系统中还剩余多少资源，可以通过公式计算：
Available = Total Resources - Allocated Resources
6. 银行家算法的运行
当一个进程请求资源时，银行家算法会根据当前状态来判断是否可以分配资源：
- 如果进程请求的资源超出它的最大需求，则拒绝。
- 否则，计算资源分配后是否会进入安全状态。如果进入安全状态，则批准分配；否则拒绝请求。
资源分配图（Resource Allocation Graph, RAG）
资源分配图是一种用于表示和分析资源分配与进程需求的图形工具，特别用于死锁检测和预防。
1. 图的组成
- 进程节点：表示系统中的进程。
- 资源节点：表示系统中的资源类型。
- 请求边：从进程节点指向资源节点，表示进程请求资源。
- 分配边：从资源节点指向进程节点，表示资源已经分配给进程。
2. 资源分配图的操作
- 请求资源：当进程请求某个资源时，系统将在图中添加一条请求边。
- 分配资源：当资源分配给进程时，系统将在图中添加一条分配边。
- 资源释放：当进程释放资源时，分配边会被删除，资源节点会回到空闲状态。
3. 死锁检测
通过分析资源分配图，如果图中存在环路（Cycle），则表示系统可能处于死锁状态。对于每个请求的资源，如果请求无法满足，且图中存在环路，说明该请求可能导致死锁。
总结
- 信号量用于进程间同步，确保资源的正确申请和释放。
- 银行家算法是一种避免死锁的资源分配算法，它确保在资源请求时保持系统安全性，防止进入死锁状态。
- 资源分配图是一种图形化的工具，用于分析和检测死锁，通过分析图中的请求和分配情况，判断是否存在死锁。
操作系统的两种视角
操作系统可以从以下两个视角来看待：
- 扩展机器（Extended Machine）：
- 从这一视角来看，操作系统的目标是简化硬件资源的使用，提供更方便的接口给用户程序。它抽象出硬件细节，让应用程序能够在一个虚拟的、简化的机器上运行，用户无需关注硬件的复杂性。
- 操作系统像一个扩展机器，为用户提供了更多的功能和灵活性，使得硬件资源能够得到更加高效、简单的管理。
- 资源管理器（Resource Manager）：
- 从这个角度来看，操作系统的主要职责是管理计算机的资源，包括CPU、内存、I/O设备等。
- 操作系统作为资源管理器，负责分配和调度这些资源，确保不同程序在执行过程中不会发生冲突，并尽量保证资源的高效利用。
临界区域（Critical Section）
临界区是指一段程序代码，它需要对共享资源（如内存、文件等）进行访问。由于资源是共享的，多个进程或线程可能同时访问它们，因此需要确保在任何时刻，只有一个进程或线程能够进入临界区，从而避免竞争条件（race condition）。
竞争条件：
- 竞争条件发生在多个进程或线程试图同时访问共享资源时，导致系统行为不可预测或错误。
- 例如，如果两个进程都在同一时刻修改共享变量，没有适当的同步机制，结果可能是不可预料的。
临界区解决方案：
为了解决竞争条件问题，我们需要保证互斥性，即在任何时刻，只有一个进程能够进入临界区。常见的解决方案包括：
- 信号量（Semaphore）：用来控制进程对临界区的访问。
- 互斥锁（Mutex）：用于保证互斥访问，即一次只允许一个进程进入临界区。
- 条件变量（Condition Variables）：在多线程编程中，用于在线程之间同步操作。
多道程序设计（Multiprogramming）
多道程序设计是计算机系统的一种特性，指的是系统能够在内存中同时存放并执行多个作业。这些作业共享系统资源，但通过合理的调度，它们能并行执行，提升计算机资源的利用率。
- 多道程序设计的优点：
- 提高了计算机资源的利用率，减少了空闲时间。
- 使得多个作业可以同时进行，增加了系统的吞吐量。
- 实现方式：
- 操作系统通过任务调度算法（如轮转调度、优先级调度等）来管理不同进程之间的切换，从而实现多道程序设计。
设备独立性（Device Independence）
设备独立性是I/O软件设计中的一个关键概念。它意味着程序应该能够访问任何类型的I/O设备，而不需要事先为每种不同的设备进行专门的编程。
设备独立性的重要性：
- 抽象层次的引入：操作系统通过引入设备驱动程序，为不同的硬件设备提供统一的接口。无论设备是硬盘、DVD、USB盘还是其他设备，程序都能够通过相同的方式进行访问。
- 增强程序的移植性：如果程序不依赖于特定的硬件设备，它就能够在不同的硬件平台上运行，而不需要修改程序的代码。
设备独立性的体现：
- 统一的接口：操作系统为各种I/O设备提供统一的接口，用户程序只需要调用操作系统提供的接口进行I/O操作，而不需要关心底层硬件的细节。
- 硬件无关的程序设计：通过设备独立性，程序能够访问硬盘、DVD、USB驱动器等设备，而不需要编写针对每种设备的特定代码。
- 示例：比如，编写一个读取文件的程序，它应当能够从硬盘、DVD或USB驱动器读取文件，而不需要修改程序代码以适应不同的存储设备。
总结
- 操作系统的两种视角：操作系统既是一个扩展机器，简化了硬件访问，也作为资源管理器负责管理计算机系统的资源。
- 临界区：为避免竞争条件，需要确保对共享资源的访问是互斥的，通常通过信号量或互斥锁来实现。
- 多道程序设计：通过在内存中同时运行多个作业，操作系统提升了计算机资源的利用率和系统的吞吐量。
- 设备独立性：操作系统通过提供统一的接口和设备驱动程序，确保程序能够在不同的硬件设备上运行，而不需要专门为每种设备编写代码。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Totoroの旅！
相关推荐
评论
