Notes@Tsukino

第7周_星期二_第2大节

12分钟阅读

第7周 星期二 第2大节

  • 视频：screen_操作系统与分布式计算_第7周_星期二_第2大节.mp4
  • 字幕：transcripts/第7周_星期二_第2大节.txt

死锁收尾：扩展银行家算法

数据结构定义（N个进程，M类资源）

数据结构类型含义
Available向量（M个元素）系统当前可用的每类资源数量
Max矩阵（N×M）每个进程对每类资源的最大需求量
Allocation矩阵（N×M）每个进程当前已分配的每类资源数量
Need矩阵（N×M）每个进程仍需的每类资源数量
  • Need[i][j] = Max[i][j] - Allocation[i][j]

扩展银行家算法流程

当进程 P_i 发出请求向量 Request_i 时：

  1. 合法性检查：若 Request_i > Need_i，拒绝（超出声称的最大量）
  2. 资源可用性检查：若 Request_i > Available，进程阻塞等待
  3. 试探分配（修改数据结构）：
    • Available = Available - Request_i
    • Allocation_i = Allocation_i + Request_i
    • Need_i = Need_i - Request_i
  4. 安全状态检测：调用安全检测算法
    • 若安全 → 正式分配
    • 若不安全 → 回滚（逆操作恢复数据结构），进程阻塞

安全状态检测算法（Work + Finish）

两个工作变量：

  • Work：向量（M个元素），当前可用的资源，初始 Work = Available
  • Finish：数组（N个元素），进程是否可运行完，初始全部为 false

算法步骤：

  1. 从进程集合中找满足以下条件的进程 P_i：
    • Finish[i] == false
    • Need_i <= Work
  2. 若找到，模拟 P_i 运行完毕释放资源：
    • Work = Work + Allocation_i
    • Finish[i] = true
    • 回到步骤1
  3. 若找不到，进入步骤4
  4. 检查 Finish 数组：
    • 若所有 Finish[i] == true → 系统处于安全状态，存在安全序列
    • 若有任一 Finish[i] == false → 系统处于不安全状态

T0时刻实例演算（5进程3类资源）

系统资源总量： A类=15, B类=7, C类=4

T0时刻状态：

进程MaxAllocationNeedAvailable
P07 5 30 1 07 4 33 3 2
P13 2 22 0 01 2 2
P29 0 23 0 26 0 0
P32 2 22 1 10 1 1
P44 3 30 0 24 3 1

安全序列查找过程：

  1. Work=332，P1(Need=122)符合 → P1释放(Allocation=200) → Work=532
  2. P3(Need=011)符合 → P3释放(Allocation=211) → Work=743
  3. P0(Need=743)符合 → P0释放(Allocation=010) → Work=753
  4. P2(Need=600)符合 → P2释放(Allocation=302) → Work=E（全部释放）
  5. P4(Need=431)符合 → P4释放

安全序列： P1 → P3 → P0 → P2 → P4（不唯一）

P1请求 1 0 2： 试探分配后安全 → 可分配（Available=230） P4请求 3 3 0： Request > Available(230) → 阻塞等待 P0请求 0 2 0： 试探分配后 Available=210，所有进程 Need 均 > Work → 不安全 → 拒绝

死锁检测算法

与安全状态检测算法完全相同，使用 Work 和 Finish：

  • 区别：死锁检测使用当前实际分配情况（而非试探分配）
  • 检测后若存在 Finish[i] == false 的进程 → 该进程已死锁

资源分配图（RAG）及化简

构成要素

  • 两类节点： 进程（圆形）和资源（方形，内含小圆点表示资源实例数）
  • 两类有向边：
    • 进程 → 资源（申请边）：进程申请该类资源
    • 资源 → 进程（分配边）：资源已分配给进程

图化简算法

  1. 找一个进程节点 P_i，其所有请求边均能立即满足
  2. 删除 P_i 的所有相连边（表示进程运行完毕释放资源）
  3. 重复直到无进程可删
  4. 检查结果：
    • 所有进程节点都变成孤立点 → 无死锁
    • 仍有进程与资源存在边 → 存在死锁

示例： T4/T3 满足条件 → 删边 → T1 满足 → 删边 → T2 满足 → 全部孤立 → 无死锁

死锁解除（恢复）方式

方式描述适用场景
重启（Reboot）最简单粗暴，系统重启通用操作系统，损失可接受
撤销进程（Kill）强制终止部分死锁进程，回收资源任务管理器杀进程
剥夺资源（Deprive）保留进程，仅收回占有资源，解除死锁后重新分配存储/处理机资源
回退（Rollback）根据历史信息让进程回到之前某个安全节点数据库管理系统
  • 通用操作系统通常采用”检测→恢复”的被动策略（减少额外开销）
  • 关键/实时系统采用预防/避免的主动策略

存储管理开篇

地址重定位

  • 逻辑地址（程序空间） → 物理地址（内存空间）的转换
  • 由 MMU（Memory Management Unit） 完成

三种重定位方式

方式时机特点典型应用
绝对装入编译时地址一一对应，简单但灵活性差单片机、早期DOS
静态重定位加载时装入时修改地址值，执行期间不变，无需额外硬件需连续存储，不支持动态空间分配
动态重定位执行时逻辑地址保持不变，访问时才映射（基址+偏移），需额外寄存器支持现代操作系统，支持换入换出、内存紧致、页式存储
  • 动态重定位通过基址寄存器 + 长度寄存器实现地址转换与越界保护

存储管理核心任务

  1. 地址变换：逻辑地址 → 物理地址
  2. 资源分配与回收：进程创建时分配空间，撤销时回收
  3. 共享与保护：防止进程间串扰
  4. 存储器扩充：虚拟存储技术，让有限内存运行更多进程

分区存储管理方案

1. 单一连续分区

  • 内存分两块：系统区（OS内核） + 用户区（一个进程独占）
  • 通过界地址寄存器实现越界保护
  • 适用：单道批处理系统
  • 缺点：CPU利用率低，内存浪费严重

2. 固定分区

  • 内存预先划分为若干个大小固定的分区
  • 通过分区状态表（起始地址 + 分区大小 + 状态）管理
  • 进程排队方式：多队列（按大小排队，减少内部碎片）或单队列
  • 适用：多道程序系统
  • 缺点：
    • 存在内部碎片（分区内未用完的空间）
    • 存在外部碎片（空闲分区但大小不满足需求）
    • 分区总数固定，限制并发进程数

3. 可变分区（动态分区）

  • 不预先划分，进程需要多少内存就切多少
  • 用空闲区链表管理（节点含：大小、起始地址、next指针）
  • 分配算法：
算法策略优点缺点
First Fit从头查找第一个满足的空闲区简单，保留高端大空间产生外部碎片，查找次数多
Next Fit循环链表，从上次位置继续分配均匀，查找更快不易保留大分区
Best Fit空闲区按容量从小到大排序，找最佳匹配剩余碎片最小产生许多小外部碎片
Worst Fit取最大空闲区分配无需查找，直接取首大分区被切碎
  • 释放时合并规则： 空闲块相邻时需合并（前邻空闲、后邻空闲、前后皆空闲、前后皆占用四种情形）
  • 内存紧致（Compaction）： 移动进程聚到一端，合并空闲空间，需动态重定位支撑
  • 采用 Bitmap（位图）管理空闲空间，0=空闲，1=占用

内部碎片 vs 外部碎片

类型定义产生场景
内部碎片已分配给进程的分区中，未被使用的空间固定分区（进程需求 < 分区大小）
外部碎片空闲分区总和够用，但不成连续，无法分配固定分区/可变分区（经过多次分配释放）

页式存储管理思想（预告）

  • 将进程逻辑空间分成页（Page），内存物理空间分成页帧（Frame）
  • 页和页帧大小相同（通常为 2 的整数次幂）
  • 逻辑页可离散存放在不连续的物理页帧中
  • 引入页表记录逻辑页到物理页帧的映射关系
  • 解决了连续分配中”大作业无法装入分散空闲区”的问题

实验室招实习生

实验室基于 AI 方向：

  • AI医疗（辅助诊疗、智能读片、多模态融合诊断）
  • 智能制造（材料配比、焊接参数优化）
  • AI for Science
  • 无人机智能感知（避障、目标识别、群检）

有意者欢迎联系实验室实习。

作业

  • 死锁检测实例作业
  • 第一次作业截止日期 3 月 16 日

考试/复习重点

  • 扩展银行家算法安全序列判断
  • 资源分配图化简
  • 地址重定位（绝对装入/静态/动态）
  • 固定分区 vs 可变分区（内部碎片 vs 外部碎片）
  • 首次/最佳/最坏适应分配算法
  • 死锁检测算法与安全检测算法的关系

关系图谱