操作系统与数据库系统的核心知识点，属于计算机科学与技术专业（尤其是考研408统考或相关课程）的重点复习提纲

操作系统与数据库系统的核心知识点，属于计算机科学与技术专业（尤其是考研408统考或相关课程）的重点复习提纲。以下是对各部分的简明梳理与关键点说明：

✅死锁处理

• 预防：破坏死锁四个必要条件之一（互斥、占有并等待、非抢占、循环等待），如要求进程一次性申请所有资源（破坏“占有并等待”）。
• 避免：动态检测资源分配状态是否安全，典型算法为银行家算法（需已知最大需求）。
• 检测：允许死锁发生，通过资源分配图或等待图定期检测环路。
• 解除：检测到死锁后，通过撤销进程或剥夺资源（如回滚、抢占）打破循环等待。

✅存储管理

• 分区管理：固定/可变分区，易产生外部碎片；简单但缺乏灵活性。
• 分页：逻辑地址→页号+页内偏移；物理地址→帧号+页内偏移；消除外部碎片，但有内部碎片。
• 分段：按逻辑模块（如主程序、栈、数据段）划分，支持共享与保护；存在外部碎片。
• 段页式：先分段再分页，兼具逻辑清晰性与内存利用率，地址结构为：段号 + 页号 + 页内偏移。

✅页面置换算法

• FIFO：最先进入内存的页被换出；可能产生Belady异常（增加页框数反而缺页率上升）。
• LRU（最近最少使用）：换出最久未被访问的页；性能好但实现开销大（需硬件支持访问位/时间戳）。
• OPT（最优置换）：换出未来最久不使用的页；仅作为理论下界，不可实现。

✅文件逻辑结构

• 顺序结构：记录按逻辑顺序连续存放；适合顺序存取，效率高但插入/删除困难。
• 索引结构：建立索引表，支持随机存取；索引本身可顺序/链式组织；兼顾灵活性与效率。
• 链接结构：每个记录含指针指向下一记录（显式链接）或由FAT/索引节点隐式链接；便于动态增删，但不支持高效随机访问。

✅磁盘调度算法

• FCFS：按请求到达顺序服务；公平但平均寻道时间长。
• SSTF：优先服务离当前磁头最近的请求；减少寻道时间，但可能导致饥饿。
• SCAN（电梯算法）：磁头单向扫描，到端点后反向；公平且性能稳定。
• CSCAN：磁头单向服务，到端点后直接跳回起点继续；提供更均匀的响应时间。

✅I/O 控制方式

• 程序查询：CPU轮询设备状态；简单但CPU利用率极低。
• 中断驱动：设备就绪后发中断，CPU响应处理；提高CPU并发性。
• DMA（直接内存存取）：由DMA控制器接管数据传输，CPU仅初始化和结束处理；适合大批量数据传输。
• 通道：专用I/O处理器，可执行通道程序，实现CPU与I/O高度并行；用于大型机/高端服务器。

✅并发基本概念

• 宏观同时，微观交替：多任务在单核上通过时间片轮转实现“并发”，多核则可真正“并行”。

✅数据库系统核心要点

• 三要素：数据结构（如关系表）、操作（增删改查）、完整性约束（实体/参照/用户自定义）。
• 三级模式+两级映像：外模式（用户视图）、模式（全局逻辑结构）、内模式（物理存储结构）；外-模式映像保障逻辑独立性，模式-内映像保障物理独立性。
• 数据模型：关系模型（主流，基于数学集合论）；层次/网状为早期模型，已少用。
• 关系代数：5种基本运算（选择σ、投影π、笛卡尔积×、并∪、差−），连接（自然连接、θ连接）是衍生运算。
• SQL核心子句：
  SELECT（投影）
  FROM（笛卡尔积+连接）
  WHERE（选择）
  GROUP BY（分组）
  HAVING（分组后筛选）
  ORDER BY（排序）

银行家算法中的安全性检查（Safety Algorithm）是用于判断系统当前资源分配状态下是否处于安全状态的核心步骤。若存在至少一个安全序列，则系统是安全的（不会发生死锁）；否则为不安全状态（可能发生死锁）。

✅ 安全性检查的具体步骤（伪代码+说明）

设系统有：

• m类资源
• n个进程
• Available[1..m]：当前可用的各类资源数量
• Max[i][j]：进程i对资源j的最大需求量
• Allocation[i][j]：进程i当前已分配的资源j数量
• Need[i][j] = Max[i][j] − Allocation[i][j]：进程i尚需的资源j数量

目标：判断是否存在一个进程执行顺序（即安全序列），使得所有进程都能顺利完成。

🔁 算法步骤如下：

1. 初始化工作向量
   Work[1..m] ← Available[1..m]
Finish[1..n] ← false（标记每个进程是否已完成）

2. 寻找可满足进程
   遍历所有进程i（i = 1 to n），若同时满足：

   • Finish[i] == false（该进程尚未完成）
   • Need[i][1..m] ≤ Work[1..m]（即对每类资源j，都有Need[i][j] ≤ Work[j]）
     → 则认为进程i可获得所需全部资源并顺利执行完毕。

3. 模拟分配与释放
   若找到这样的进程i：

   • Work[1..m] ← Work[1..m] + Allocation[i][1..m]（进程执行完后归还全部已占资源）
   • Finish[i] ← true
   • 将i加入候选安全序列（记录顺序）

4. 重复步骤2–3，直到：

   • 所有Finish[i] == true→系统安全，记录的执行顺序即为一个安全序列；
   • 或再也找不到满足条件的i（即剩余未完成进程中，任一的Need > Work）→系统不安全。

✅ 构造安全序列的示例（简例）

假设有 3 类资源 A、B、C，5 个进程 P₀~P₄：

当前Available = [3,3,2]

✅执行安全性检查：

• 初始：Work = [3,3,2],Finish = [F,F,F,F,F]
• 查找：P₁（Need=[1,2,2] ≤ Work）→ 满足 →Work = [3,3,2]+[2,0,0] = [5,3,2],Finish[P₁]=T
• 再查：P₃（Need=[0,1,1] ≤ [5,3,2]）→ 满足 →Work = [5,3,2]+[2,1,1] = [7,4,3],Finish[P₃]=T
• 再查：P₀（Need=[7,4,3] ≤ [7,4,3]）→ 满足 →Work = [7,4,3]+[0,1,0] = [7,5,3],Finish[P₀]=T
• 再查：P₂（Need=[6,0,0] ≤ [7,5,3]）→ 满足 →Work = [7,5,3]+[3,0,2] = [10,5,5],Finish[P₂]=T
• 最后：P₄（Need=[4,3,1] ≤ [10,5,5]）→ 满足 →Finish[P₄]=T

✅ 所有 Finish 为 true →系统安全
✅ 安全序列为：P₁ → P₃ → P₀ → P₂ → P₄（注意：可能不唯一，只要存在一个即可）

📌关键提醒：

• 安全序列 ≠ 实际运行顺序，仅表示“存在一种调度可能使所有进程完成”；
• 银行家算法在每次资源请求前都执行此检查，仅当结果为安全时才批准分配；
• 时间复杂度为 O(m×n²)，适用于进程/资源数不大的场景。

如需我为您生成可运行的 Python 实现代码（含输入解析与安全序列输出），欢迎继续提问！