- 1 概述
collapsed:: true
- 操作系统概念
- 操作系统特征
- 并发（Concurrence）：操作系统 具备同时处理和调度多个程序的能力。
- 共享（Sharing）：系统中的资源可供内存中多个并发的进程共同使用。
- 虚拟（Virtual）：将物理的实物虚拟为逻辑上的对应物。
- 异步（Asynchronism）：任务可以不按固定的顺序执行，因此同一操作的结果可能因执行的时序而异。
- 发展历程
- 分类
- 程序运行环境
- CPU 运行模式
- 程序的链接
- 程序的装入
- 绝对装入
- 可重定位装入
- 多个目标模块的起始地址通常都从 0 开始，程序中的其他地址都是相对于起始地址的偏移量
- 动态运行时装入
- 可重入的概念
- 程序代码可以被多个进程共享使用
- 驱动程序和子程序通常是可重入的
- 操作系统结构
- 分层和模块化
- 内核架构
- 微内核
- 优点
- C/S 架构
- 可移植性好
- 易于扩展和维护
- 提高系统的可靠性和安全性
- 缺点
- 宏内核
- 优点
- 缺点
- 可移植性差
- 难以扩展和维护
- 系统可靠性和安全性较低
- 虚拟机
- 虚拟机监视器
- 类型
- 原生型 (Type 1)
- 托管型 (Type 2)
- 优点
- 提高资源利用率
- 提供隔离的运行环境
- 便于系统管理和维护
- 考点:
- 系统调用
- 系统调用的定义
- 用户程序通过系统调用请求操作系统内核提供的服务
- 系统调用是用户程序与操作系统内核之间的接口
- 系统调用实现过程
- 用户程序发出系统调用请求
- 切换到内核模式
- 执行系统调用处理程序
- 返回用户模式继续执行用户程序
- 考点 #🕳 有坑
- 区分系统调用与库函数调用
- 库函数调用是在用户态执行的, 不涉及模式切换
- 系统调用是在内核态执行的, 需要模式切换
- 驱动程序不能执行系统调用
- 驱动程序本身运行在内核态, 不需要通过系统调用请求内核服务
- 2 进程与线程
collapsed:: true
- 进程的概念
collapsed:: true
- 进程定义
- 程序的动态执行过程
- 进程是系统资源分配的基本单位
- 进程拥有独立的系统资源，包括内存空间、文件描述符、CPU 时间片等，这些资源的分配由操作系统负责
- 区分进程与程序
- 程序是静态的代码和数据的集合，而进程是程序在执行时的动态实体
- 进程控制块 PCB
- 进程标识符 PID
- 程序计数器 PC
- CPU 寄存器
- 进程状态
- 优先级
- 内存管理信息
- 资源分配情况
- 父子进程关系
- 子进程由父进程通过
fork()系统调用创建
- 子进程继承父进程代码, 数据和堆栈的副本
- 父子进程的地址空间相互独立
- 僵尸进程
- 子进程终止后, 父进程未调用
wait()或waitpid()回收子进程资源, 导致子进程PCB仍保留在系统中
- 孤儿进程
- 进程状态转换 #🕳 有坑
- 创建态 New
- 就绪态 Ready
- 进程创建并成功获取全部所需资源后, 状态转为就绪态, 等待CPU调度 #🤔 考前记
- 运行态 Running
- 阻塞态 Blocked
- 终止态 Terminated
- 进程的内存空间
- 用户空间
- 代码段
- 数据段
- 初始化数据区
- 存放已初始化的全局变量和静态变量
- 在程序加载时分配内存并初始化
- 未初始化数据区(BSS段)
- 存放未初始化的全局变量和静态变量
- 在程序加载时分配内存并初始化为0
- 堆区
- 存放动态分配的内存
- 由程序在运行时通过
malloc()等函数分配和释放
- 通常从低地址向高地址增长
- 栈区
- 内存映射区
- 存放通过
mmap()函数映射的文件或设备
- 通常用于动态链接库的加载
- 内核空间
- 函数调用时的内存结构
- 栈帧结构
- 线程的定义
- 线程是系统调度的基本单位
- 一个进程中的所有线程共享虚拟地址空间和系统资源
- 每个线程有独立的执行栈和寄存器状态
- 线程与进程的关系
- 线程是进程的一个执行单元
- 线程依赖于进程存在, 线程的生命周期受进程控制
- 线程的优点
- 线程模型
- 用户级线程 ULT
- 线程管理由用户级线程库实现
- 优点: 创建和切换开销小, 可移植性好
- 缺点: 无法利用多核CPU, 阻塞系统调用会阻塞整个进程
- 内核级线程 KLT
- 线程管理由操作系统内核实现
- 优点: 可利用多核CPU, 支持阻塞系统调用
- 缺点: 创建和切换开销大, 可移植性差
- 混合级线程 MLT
- 结合用户级线程和内核级线程的优点
- 映射关系
- 一对一: 每个用户线程对应一个内核线程
- 多对一: 多个用户线程对应一个内核线程
- 多对多: 多个用户线程对应多个内核线程
- {{embed ((693b8742-3957-46fb-8f6c-c90b581ce1e0))}}
- 进程间通信 IPC
- 管道 Pipe
- 特点
- 半双工通信, 全双工需使用两个管道
- 可同时被多个进程使用(读写), 互斥访问由操作系统保证
- 无名管道: 只能在父子进程或兄弟进程间通信
- 命名管道(FIFO): 可在任意进程间通信
- 消息队列 Message Queue
- 一种基于内核的进程间通信机制
- 特点
- 支持异步通信
- 消息有类型, 可按类型读取
- 开销较大
- 共享内存 Shared Memory
- 特点
- 速度快, 适合大数据量传输
- 需要进程间协作, 通过信号量实现同步和互斥
- ((693b8cef-c3ac-43a7-b212-1740c626c867)) Semaphore
- 处理机调度
collapsed:: true
- 调度指标
- 系统层面
- CPU利用率: CPU处于忙碌状态的时间百分比
- 吞吐量: 单位时间内系统完成的工作量或进程数
- 进程层面
id:: 693b8570-db9d-44e7-95f6-afbb1ae08a3f
- 到达时间
- 等待时间
- 要求服务时间: 进程运行所需的总时间
- 完成时间
- 周转时间: 从提交到完成所需的总时间 #🕳 有坑
- 注意: 如果有进程切换时间, 则周转时间 = 完成时间 - 到达时间 + 切换时间
- 平均周转时间 = (所有进程的周转时间之和) / (进程总数)
- 带权周转时间 = 周转时间 / 要求服务时间
- 平均带权周转时间 = (所有进程的带权周转时间之和) / (进程总数)
- 系统调度过程 #🤔 考前记
- 高级调度(长程调度)
- 决定哪些进程应当被加载到内存中, 并进入就绪队列
- 保证内存中保持适当数量的进程
- 频率低, 开销大
- 中级调度(中程调度)
- 决定哪些进程应当被挂起或唤醒
- 联系 ((693c02e8-0ea4-44d0-bb9e-03b0447ffa04))
- 当内存资源紧张时, 将部分进程挂起到辅存中; 在内存资源充足时, 将挂起的进程唤醒并调入内存
- 为高级调度和低级调度优化内存
- 初级调度(短程调度)
- 决定哪个进程应当获得CPU使用权
- 从就绪队列中选择一个进程并分配CPU
- 频率高, 开销小
- 调度的实现
- 调度器
- 调度时机
- 进程进入或退出系统
- 进程从运行变为阻塞状态
- 一个时间片结束
- 调度方式
- 非抢占式调度: 一旦进程获得CPU, 就继续运行直到完成或进入阻塞状态
- 抢占式调度: 操作系统可以强制中断正在运行的进程, 将CPU分配给另一个进程
- 闲逛进程(Idle Process)
- 两种线程的调度
id:: 693b8742-3957-46fb-8f6c-c90b581ce1e0
- 内核级线程
- 用户级线程
- 由用户级线程库调度
- 操作系统只调度进程, 不感知线程的存在
- 线程切换不涉及内核, 开销小
- 调度算法
- 分类
- 非抢占式调度算法
- 先来先服务 FCFS
- 短作业优先 SJF (可抢占和不可抢占)
- 高响应比优先 HRRN
- 抢占式调度算法
- 时间片轮转 RR
- 多级反馈队列 MLFQ
- 优先级调度算法(可抢占和不可抢占)
- 性能指标 ((693b8570-db9d-44e7-95f6-afbb1ae08a3f))
- 平均等待时间
- 平均周转时间
- 响应时间
- CPU利用率
- 吞吐量
- 注意: 进程的运行时间实际上是不可预知的, 因此不能作为评估调度算法的依据
- 先来先服务 FCFS
- 按照进程到达的顺序 分配依次执行
- 优点: 简单易实现
- 缺点: 可能导致平均等待时间长, 不适合交互式系统
- 短作业优先 SJF
- 选择估计运行时间最短的进程优先执行
- 优点: 能最小化平均等待时间
- 缺点: 需要预知进程的运行时间, 可能导致长作业饥饿
- 高响应比优先 HRRN #🤔 考前记
- 计算响应比: (等待时间 + 要求服务时间) / 要求服务时间
- 选择响应比最高的进程优先执行
- 优点: 综合考虑等待时间和服务时间, 避免长作业饥饿
- 时间片轮转 RR
- 为每个进程分配一个固定的时间片, 进程在时间片内运行, 时间片用完后被抢占, 放回就绪队列
- 优点: 提高系统响应性, 适合交互式系统
- 缺点: 时间片过大接近FCFS, 过小则开销大
- 多级反馈队列 MLFQ
- 设立多个优先级队列, 进程根据其行为在不同队列间移动
- 新进程进入最高优先级队列
- 进程在时间片内未完成则降级, 完成则升级
- 优点: 适应不同类型进程的需求, 提高系统性能
- 上下文切换 #🤔 考前记
- 定义: 操作系统在进程调度时保存当前进程状态, 并恢复新进程状态的过程
- 上下文切换流程
- 保存当前进程状态到 PCB
- 选择下一个要运行的进程
- 装入新进程的现场信息
- 切换到新进程执行
- 同步和互斥
collapsed:: true
- 临界区问题
- 临界区定义: 访问共享资源的代码段
- 注意: 进程处于临界区时, 操作系统仍可以进行进程调度.
- 例如, 进程A申请打印机打印后阻塞, 操作系统可以调度进程B运行
- 互斥: 防止多个进程同时进入临界区
- 同步: 保证进程按特定顺序执行
- 互斥
- 分类
- 软件互斥: 通过算法和程序设计实现互斥
- 硬件互斥: 通过硬件支持(如原子操作)实现互斥
- 禁用中断
- 测试并设置 Test-and-Set
- 交换指令 Swap
- 锁机制: 操作系统提供, 软件直接调用
- 信号量: 操作系统提供
- 互斥锁 Mutex
- 操作系统提供的同步原语, 确保同一时刻只有一个线程能进入临界区
- 只有拥有锁的线程才能释放锁
- 操作
- 加锁 Lock或者Acquire
- 解锁 Unlock或者Release
- 软件互斥: Peterson算法
- 适用于两个线程的互斥
- 使用
bool flag[2]表示线程是否想进入临界区, int turn表示轮到哪个线程
- 两个线程都设置自己的
flag为true, 然后将turn设为对方线程, 然后等待直到对方线程的flag为false或者轮到自己
- 硬件互斥
- 原子性操作: 一次不可分割的操作, 中途不能被中断
- Test-and-Set指令
- 读写一个内存位置, 并将其设置为1
- 返回原始值, 如果原始值为0表示锁未被占用, 为1表示锁已被占用
- Compare-and-Swap指令
- 比较内存位置的值与给定值, 如果相等则将其设置为新值
- 返回操作结果
-
int CompareAndSwap(bool *lock, bool expected, bool newValue) {
if (*lock == expected) {
*lock = newValue;
return 1; // 成功
} else {
return 0; // 失败
}
}
- 同步
- 同步基本原则
- 特殊状态
- 死等(饥饿): 进程无限期等待进入临界区
- 忙等: 进程在等待时不断检查条件, 占用CPU资源
- 条件变量
- 一种同步原语, 用于线程间的条件同步
- 作用
- 线程等待某个条件成立时阻塞自己, 条件成立时唤醒等待的线程
- 避免忙等待
- 操作
- 等待 Wait: 线程阻塞自己, 并释放关联的互斥锁, 等待另一个线程发出信号
- 信号 Signal: 唤醒一个等待该条件变量的线程
- 广播 Broadcast: 唤醒所有等待该条件变量的线程
- 信号量
id:: 693b8cef-c3ac-43a7-b212-1740c626c867
- 逻辑上相当于一个整数计数器
- 当
S>=0时, 表示可用资源数量
- 当
S<0时, 其绝对值表示等待该资源的进程数量
- 两个重要操作
- P操作(
P()/wait())
-
P(Semaphore s) {
s.value = s.value - 1; // 尝试获取资源，信号量值减 1
if (s.value < 0) { // 如果值小于 0，表示资源不足
q.push(current_process); // 将当前进程加入等待队列
block(); // 阻塞当前进程
}
}
- V操作(
V()/signal())
-
V(Semaphore s) {
s.value = s.value + 1; // 释放资源，信号量值加 1
if (s.value <= 0) { // 如果值小于或等于 0，表示有进程在等待
Process p = q.pop(); // 从等待队列中取出一个进程
wakeup(p); // 唤醒该进程
}
}
- 应用
- 实现锁
- 一个初值为1的信号量
P()操作获取锁, V()操作释放锁
- 实现同步
- 一个初值为0的信号量
- 前驱进程执行
V()操作, 后继进程执行P()操作
- 实现资源计数
- 计数信号量(Counting Semaphore)
- 考点 #🕳 有坑
- PV操作能解决一切同步互斥问题
- 任何复杂场景, 理论上都能被分解为一系列同步互斥问题. 只要有足够的信号量和正确的PV操作顺序, 就能实现所需的同步互斥行为
- 但PV操作不能防止发生死锁
- 不良的加锁顺序是死锁的直接原因, 信号量本身不关心进程如何使用它们
- 管程
- 一种高级同步原语, 将共享数据和对数据的操作封装在一个模块中
- 由编程语言或操作系统支持
- 实现了让权等待
- 组成
- 共享数据
- 方法: 定义对共享数据的操作
- 条件变量: 进程等待和唤醒的条件
- 经典同步互斥问题
- 总结 #🤔 考前记
- 务必写好注释, 标明每个信号量的用途和初始值 - 评分标准之一
- 关于前驱后继问题
- 前驱进程相当于生产者, 执行
V()操作
- 后继进程相当于消费者, 执行
P()操作
- 不存在前驱后继关系的进程不需要使用信号量
- 关于生产者消费者问题
- 关于复杂数值依赖问题
- 关于多个临界资源的互斥问题
- 仔细归类资源需求, 设计合适的信号量和PV操作顺序
- 生产者消费者问题
- 一般形式
full=0信号量: 记录缓冲区中已用缓冲区数量empty=n信号量: 记录缓冲区中空缓冲区数量mutex=1信号量: 保护对缓冲区的互斥访问
- 扩展一: 要求满足不等式−M≤A−B≤N #🤔 考前记
- 解析
- {A−B≤NB−A≥M
- 库中A物品可以比B物品多，但不能超过N+1个;Ｂ物品可以比A物品多，但不能超过M+1个
- 初始有0个A物品和0个B物品, 因此最多允许生产M个A物品和N个B物品
- 并且每次生产A物品后, 允许生产B物品的数量增加1; 每次生产B物品后, 允许生产A物品的数量增加1
- 定义和实现
mutex=1: 保护对缓冲区的互斥访问maxA=M: 记录A物品允许的最大数量maxB=N: 记录B物品允许的最大数量-
void producer_A() {
P(maxA); // 检查是否允许生产A物品
P(mutex); // 获取对缓冲区的互斥访问
// 生产A物品并放入缓冲区
V(mutex); // 释放对缓冲区的互斥访问
V(maxB); // 增加B物品的允许数量
}
void producer_B() {
P(maxB); // 检查是否允许生产B物品
P(mutex); // 获取对缓冲区的互斥访问
// 生产B物品并放入缓冲区
V(mutex); // 释放对缓冲区的互斥访问
V(maxA); // 增加A物品的允许数量
}
- 读者写者问题
- 读优先: 允许多个读者同时读, 写者等待直到没有读者
rw_mutex=1信号量: 保护对共享数据的互斥访问read_count=0: 记录当前读者数量rmutex=1信号量: 保护对read_count变量的互斥访问-
void reader_i() {
P(rmutex);
read_count++;
if (read_count == 1) P(rw_mutex); // 第一个读者锁定写者
V(rmutex);
// 读取共享数据
P(rmutex);
read_count--;
if (read_count == 0) V(rw_mutex); // 最后一个读者释放写者
V(rmutex);
}
void writer_i() {
P(rw_mutex); // 获取对共享数据的互斥访问
// 写入共享数据
V(rw_mutex); // 释放对共享数据的互斥访问
}
- 写优先: 读者尝试读时, 如果有写者等待则阻塞读者
rw_mutex=1信号量: 保护对共享数据的互斥访问rmutex=n信号量: 最多允许n个读者同时读-
void reader_i() {
P(rw_mutex); // 获取对共享数据的互斥访问
P(rmutex); // 获取读者许可
// 读取共享数据
V(rmutex); // 释放读者许可
V(rw_mutex); // 释放对共享数据的互斥访问
}
void writer_i() {
P(rw_mutex); // 获取对共享数据的互斥访问
for (int j = 0; j < n; j++) P(rmutex); // 阻塞所有读者
// 写入共享数据
for (int j = 0; j < n; j++) V(rmutex); // 允许读者继续读
V(rw_mutex); // 释放对共享数据的互斥访问
}
- 扩展一: 猴子过河的同步互斥问题 Y26王道模拟3/T45
- 哲学家就餐问题
- 方法一: 同时拿起两只筷子
-
semaphore chopstick[5] = {1,1,1,1,1}; // 五个筷子信号量初始化为1
void philosopher_i() {
// 思考
P(chopstick[i]); // 拿起左筷子
P(chopstick[(i+1)%5]); // 拿起右筷子
// 吃饭
V(chopstick[(i+1)%5]); // 放下右筷子
V(chopstick[i]); // 放下左筷子
}
- 方法二: 限制同时就餐人数
- 方法三: 奇偶哲学家拿筷子顺序不同
-
semaphore chopstick[5] = {1,1,1,1,1}; // 五个筷子信号量初始化为1
void philosopher_i() {
// 思考
if (i % 2 == 0) {
P(chopstick[i]); // 拿起左筷子
P(chopstick[(i+1)%5]); // 拿起右筷子
// 吃饭
V(chopstick[(i+1)%5]); // 放下右筷子
V(chopstick[i]); // 放下左筷子
} else {
P(chopstick[(i+1)%5]); // 拿起右筷子
P(chopstick[i]); // 拿起左筷子
// 吃饭
V(chopstick[i]); // 放下左筷子
V(chopstick[(i+1)%5]); // 放下右筷子
}
}
- 十字路口的通行问题
- 四个方向来车，将中心区域分为 4 块，每块作为一个临界资源
- 每个方向来车分为 3 种情况
- 直行：占用 2 个临界资源 (2 个，3, 4)
- 左转：占用 3 个临界资源 (3 个，3, 4, 1)
- 右转：占用 1 个临界资源 (1 个，3)
- 四个方向一共最少需要 4 个临界资源 (不考虑死锁).
- 死锁
collapsed:: true
- 死锁产生的必要条件
- 互斥条件: 资源不能被多个进程共享
- 占有且等待条件: 进程至少持有一个资源, 并等待获取其他被占用的资源
- 非抢占条件: 资源不能被强制从进程中夺取, 只能由进程自己释放
- 循环等待条件: 存在一个进程循环等待资源的链
- 死锁处理方法
- 死锁预防
- 破坏必要条件之一
- 破坏互斥条件: 允许资源共享 (不现实)
- 破坏占有且等待条件:
- 要求进程一次性请求所需的所有资源
- 进程在请求新资源前释放已持有的资源
- 破坏非抢占条件: 如果进程请求资源被阻塞, 它可以抢占另一个进程持有的资源
- 破坏循环等待条件: 为每种资源类型分配唯一编号, 进程按编号顺序请求资源
- 死锁避免
- 动态检查系统状态, 确保不会进入不安全状态
- 银行家算法
- 维护资源分配表和需求表
- 在分配资源前, 检查系统是否处于安全状态
- 死锁检测与解除
- 定期检测系统是否存在死锁
- 如果检测到死锁, 则采取措施解除死锁
- 考点 #🤔 考前记
- 辨析死锁预防、避免和检测
- 运行前(勿谓言之不预也, 预防在最前)/运行时/死锁发生后
- 死锁预防之不发生死锁至少需要的资源个数(鸽巢原理)
- 假设有n个进程, 每个进程最多需要m个资源
- 则系统中至少需要
n*(m-1)+1个资源, 才能保证不会发生死锁
- 3 内存管理
collapsed:: true
- 内存管理概述
- 基本概念
- 虚拟地址: 进程使用的地址空间
- 物理地址: 实际内存芯片上的地址
- 地址映射: 将虚拟地址转换为物理地址的过程
- 地址映射中出现中断的情况 #🕳 有坑
- 地址越界
- 权限问题
- 页错误
- 区分内存溢出, 指的是内存不足问题
- 虚拟内存
id:: 693c0b8d-875d-40b6-9b0c-6db292b3dc71
- 程序不必全部加载到内存中, 通过地址映射和页面置换实现按需调页
- 按序调页的基础是局部性原理
- 内存保护: 防止进程访问未分配给它的内存区域
- 内存共享: 允许多个进程共享同一内存区域
- 内存管理方式
- 连续分配方式
- 单一连续分配
- 系统分为内核区和用户区
- 用户区中只有一个进程(整个用户空间由该进程独占)
- 优点: 实现简单, 无外部碎片
- 缺点: 内存利用率低, 只能运行一个用户进程
- 固定分区分配
- 内存划分为若干固定大小的分区
- 每个分区只能容纳一个进程
- 优点: 实现简单, 支持多道程序设计
- 缺点: 内存利用率低, 可能产生内部碎片
- 动态分区分配
- 将内存视作一整块连续空间, 根据进程需求从空闲内存中分配合适大小的块
- 进程申请内存时, 系统遍历空闲内存块列表, 根据适应算法选择合适的块进行分配
- 适应算法
- 首次适应 First Fit
- 循环首次适应(临近适应) Next Fit
- 从上次分配结束的位置开始查找第一个足够大的空闲块进行分配
- 最佳适应 Best Fit
- 遍历所有空闲块, 选择最小的足够大的块进行分配
- 操作系统维护一个按从小到大排序的空闲块链表, 以提高查找效率
- 缺点: 可能产生大量小碎片, 导致内存碎片化
- 最差适应 Worst Fit
- 遍历所有空闲块, 选择最大的空闲块进行分配
- 缺点: 可能导致大块内存被分割成多个小块, 增加碎片化
- 内存回收
- 动态分区分配中, 进程释放内存后, 系统将释放的块插入空闲块链表
- 合并相邻的空闲块以减少碎片
- 合并后要重新计算起始地址和大小, 并重新排序(若为最佳适应算法)
- 伙伴算法
- 将内存划分为大小为2的幂次方的块
- 分配时, 找到最小的满足需求的块, 若块过大则不断拆分为两个伙伴块, 直到块大小合适
- 释放时, 检查相邻的伙伴块是否空闲, 若空闲则合并为更大的块
- 优点: 分配和回收效率高, 易于合并
- 离散分配方式
- 页式管理 ((693b708a-c623-46d8-ba80-1ed4d1d4bd5c))
- 将进程的虚拟地址空间划分为固定大小的页, 内存划分为同样大小的页框
- 通过页表实现虚拟地址到物理地址的映射
- 段式管理 ((693b708a-2c5c-4a3c-ab11-d3557753031b))
- 将进程的虚拟地址空间划分为逻辑上连续的段, 每个段有不同的长度和属性
- 通过段表实现虚拟地址到物理地址的映射
- 段页式管理
- 结合段式和页式管理的优点
- 先将虚拟地址划分为段, 再将每个段划分为页
- 考点 #🤔 考前记
- 内存管理方式的内部碎片
- 会产生的 - 只要分区固定就会产生内部碎片
- 不会产生的
- 请求分页存储管理和分页存储管理的好处
- 请求分页存储管理: 扩大了存储器的逻辑地址空间
- 分页存储管理: 使作业在内存中的存放不必是连续的
- 虚拟内存管理
collapsed:: true
- 页框分配
id:: 693bbe05-6d65-48c2-81f4-7b42c25949d0
- 抖动(Thrashing)
- 定义: 由于频繁的页面置换导致系统性能急剧下降的现象
- 原因: 内存不足, 进程频繁发生缺页中断, 导致大量页面置换
- 解决方法
- 增加物理内存
- 减少多道程序设计的进程数
- 优化页面置换算法
- 不能通过增加((693c02e8-0ea4-44d0-bb9e-03b0447ffa04))的方式解决, 交换分区是主存换出的文件, 没有从本质上解决主存不够的问题.
- 内存分配和置换策略
id:: 693bbee6-f0a9-45f3-8a26-5fddcc38b1e3
- 内存分配策略
- 固定分配
- 每个进程分配固定数量的页框
- 常用方法: 等比例分配, 均匀分配
- 可变分配
- 内存置换策略
- 局部置换
- 全局置换
- 不存在的策略组合
- 全局+固定: 固定分配下所占页框数量不变, 全局置换意味着可以侵占其他进程的页框, 矛盾
- 页置换算法
id:: 693bbf6b-14e9-44be-9ba7-34324092ac3e
- 先进先出 FIFO
- 替换最早进入内存的页面
- 优点: 实现简单
- 缺点: 可能替换掉频繁使用的页面, 导致性能下降
- Belady异常: 在某些情况下, 增加页框数量反而导致缺页率上升
- 最佳置换 OPT
- 替换最长时间内不会被访问的页面
- 优点: 理论上缺页率最低
- 缺点: 需要预知未来的页面访问序列, 实际中不可行
- 最少使用 LRU
- 替换最长时间未被使用的页面
- 优点: 能较好地反映页面的使用频率, 提高命中率
- 缺点: 实现复杂, 需要维护页面使用时间信息
- 最少使用次数 LFU
- 替换使用次数最少的页面
- 优点: 能较好地反映页面的使用频率
- 缺点: 可能刚进入内存的页面由于使用次数少而被替换掉
- 时钟算法 Clock
- 简单Clock
- 使用一个指针循环扫描页框, 每次检查页面的使用位
- 如果使用位为1, 则将其清0并继续扫描; 如果为0, 则替换该页面
- 优点: 实现简单, 性能接近LRU
- 改进型Clock
- 使用两个位: 使用位和修改位
- 替换时
- 优先选择使用位和修改位都为0的页面
- 其次选择使用位为0且修改位为1的页面(保留优先级:使用>修改)
- 再次选择使用位为1且修改位为0的页面
- 最后选择使用位和修改位都为1的页面
- 页面缓冲算法
- 在页面置换算法的基础上, 增加一个缓冲区来存储最近被替换掉的页面, 当这些页面数量达到一定阈值时, 批量写入到磁盘.
- 空闲页面链表
- 修改页面链表
- 页缓冲队列
- 缓存已修改但未写回磁盘的页面, 提高页面写回效率
- 不直接影响缺页率
- 磁盘交换分区
id:: 693c02e8-0ea4-44d0-bb9e-03b0447ffa04
- 定义: 操作系统使用磁盘上的一个专用区域作为扩展内存, 用于存储暂时不需要的页面
- 作用: 提供虚拟内存支持, 允许进程使用超过物理内存大小的地址空间
- 交换分区管理
- 交换分区表: 记录交换分区的起始位置和大小
- 页面交换: 当内存不足时, 将不常用的页面写入交换分区
- 当页面被访问时, 从交换分区读取回内存
- 内存映射文件
- 定义: 将文件内容映射到进程的虚拟地址空间, 允许进程通过内存访问文件数据
- 优点
- 常规文件操作(如
read()和write())需要2次数据拷贝(磁盘→内核缓冲区→用户缓冲区), 内存映射文件只需1次数据拷贝(磁盘→进程地址空间), 提高效率
- 支持延迟加载
- 支持进程间通信
- 4 文件管理
collapsed:: true
- 文件
- 文件元信息
- 目录文件
- 存储文件名和对应的索引节点号(i-node number)
- 目录文件本身也是一个文件, 由文件系统管理
- 索引节点(i-node)
- 存储文件的元信息, 包括
- 磁盘索引结点
- 文件类型
- 文件权限
- 文件所有者
- 文件大小
- 创建时间、修改时间、访问时间
- 数据块指针: 指向文件数据所在的物理块
- 内存索引结点
- 文件控制块(FCB)
- 存储文件的控制信息, 包括
- 文件名
- 文件位置
- 文件大小
- 文件权限
- 文件状态信息
- 文件描述符(File Descriptor)
- 进程打开文件时, 操作系统为该文件分配一个唯一的整数标识符
- 进程通过文件描述符进行文件操作
- 进程文件管理
- inode 表(系统级)
- 系统维护一个全局的 inode 表, 记录所有打开文件的索引节点信息
- 系统打开文件表(系统级)
- 系统维护一个全局的打开文件表, 记录所有打开文件的状态信息
- 文件描述符表(进程级)
- 每个进程维护一个文件描述符表, 记录该进程打开的文件描述符和对应的打开文件表项的映射关系
- 系统调用
- 涉及文件路径的系统调用
- 打开文件:
open(const char *pathname, int flags): 需要提供文件路径
- 创建文件:
creat(const char *pathname, mode_t mode)
- 删除文件:
unlink(const char *pathname): 需要提供文件路径
- 读写相关
- 读文件:
read(int fd, void *buf, size_t count)
- 写文件:
write(int fd, const void *buf, size_t count)
- 关闭文件:
close(int fd)
- 通过延迟写和预读取提高读写效率
- 定位相关
- 定位文件指针:
lseek(int fd, off_t offset, int whence)
- 考点
- 进程等待键盘输入到进程接收数据的过程
- 执行系统调用
read(), 进程阻塞
- 键盘中断发生前, 数据位于IO接口缓冲区
- 键盘中断处理程序将数据从IO接口缓冲区复制到内核缓冲区
- 系统调用
read()从内核缓冲区复制数据到用户缓冲区
- 进程解除阻塞, 继续执行
- 文件逻辑结构
- 顺序文件
- 按照文件内容的顺序进行读写
- 适用于文本文件、日志文件等
- 随机(直接)文件
- 允许进程直接访问文件的任意位置
- 适用于数据库文件、二进制文件等
- 文件物理结构
- 连续分配
- 文件的所有数据块在磁盘上是连续存储的
- 目录项中记录文件的起始块地址和数量
- 链接分配
- 文件的各数据块通过指针链接在一起, 不要求连续存储
- 目录项中记录文件的起始块地址, 最后一个块指针为
-1
- 文件分配表
- 使用一个专门的表格( ((693c1343-ba77-47b2-b8cb-6db63efb444a)) )记录文件数据块的链接关系
- 目录项中记录文件的盘块号和下一个块号的索引
- 索引分配
- 一个文件占用的所有盘块号都存储在一个索引块中
- 系统先读取索引块, 然后根据索引块中的盘块号访问文件数据
- 单级索引
- 多级索引
- 混合索引(unix文件系统)
id:: 693bc88b-0ad8-419c-9350-cdb8a6c6037c
- inode 中包含
- 直接块指针: 直接指向数据块的指针
- 一级间接块指针: 指向一个间接块, 该间接块存储多个数据块指针
- 二级间接块指针: 指向一个二级间接块, 该二级间接块存储多个一级间接块指针
- 考点 #🤔 考前记
- 最大文件大小
- 计算一个inode能包含的最大磁盘块指针个数, 再乘以块大小
- 最多inode个数
- 即inode指针(索引地址项)中关于inode地址字段的位数所能表示的最大值
- 读文件某个偏移地址的数据, 需要的读磁盘操作次数
- 根据偏移地址计算出对应的数据块号, 然后根据数据块号判断需要经过多少级索引才能找到该数据块的指针
- 插入K个数据块, 需要的读写磁盘操作次数
- 直接索引: K+1 次写磁盘操作, 写入K个数据块和更新inode
- 一级间接索引: K+2 次写磁盘操作, 写入K个数据块, 更新间接块和inode(inode中有文件大小等信息需要更新)
- 依次类推
- 目录
- 目录的概念
- 树形目录
- 存储结构
- 目录文件: 存储目录项的文件
- 目录项: 包含文件名和对应的索引节点号
- 操作
- 文件链接
- 硬链接
- 多个文件名指向同一个索引节点
- 删除其中一个文件名不会影响其他文件名的访问
- 适用于同一文件系统内的文件共享
- 软链接(符号链接)
- 创建一个新的文件, 该文件包含指向目标文件路径的引用
- 删除软链接不会影响目标文件的访问
- 适用于跨文件系统的文件共享
- 文件系统
- 功能
- 数据存储与组织
- 空间管理
- 数据访问与操作
- 数据保护
- 文件系统结构 ((693be6d4-edfe-405c-8a83-50442a4dabe3))
- 引导区(Master Boot Record, MBR)
- 通常位于磁盘的第一个扇区
- 包含引导加载程序(Boot Loader)
- 分区表(Partition Table)
- 通常存储在引导区之后
- 记录磁盘的分区信息, 包括每个分区的起始位置和大小和分区类型
- 分区
- 元数据
- 超级块(Superblock)
- 存储文件系统的总体信息, 如文件系统类型、大小、空闲空间等
- 计算机启动时加载
- 空闲块信息
- 记录文件系统中空闲块的分配情况
- 可能使用位图(Bitmap)或链表(List)等数据结构
- inode 表
- 数据区
- 外存空闲空间管理
- 空闲表法
- 使用一个专门的表格记录磁盘上尚未分配的连续空闲块的所在位置和大小
- 包含空闲块的起始盘块号和盘块数量
- 空闲链表法
- 使用链表结构记录所有空闲块的信息
- 每个空闲块包含一个指向下一个空闲块的指针
- 位图法
- 位图的每一位对应磁盘上的一个块
- 位值为0表示该块空闲, 为1表示该块已分配
- 成组链接法 #🥶 冷门
- 类似于 ((693bc88b-0ad8-419c-9350-cdb8a6c6037c))
- 基本思想
- 将空闲盘块分成若干个组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号
- 各组的第一个盘块形成一个链表，便于管理
- 空闲盘块号栈: 存储当前组的空闲盘块号
- 分配盘块
- 从空闲盘块号栈中弹出一个盘块号进行分配
- 如果栈为空, 则读取弹出的盘块号所指向的盘块, 将该盘块中的内容作为新的空闲盘块号栈, 然后弹出一个盘块号进行分配
- 回收盘块
- 将回收的盘块号压入栈中
- 如果栈已满, 则将栈中的内容写入新回收的盘块中, 并将该盘块号作为新的栈底
- FAT文件系统
- 使用簇作为文件存储单位
- 文件分配表FAT
id:: 693c1343-ba77-47b2-b8cb-6db63efb444a
- 表项结构
- 簇状态
- 空闲簇
- 已分配簇: 指向下一个簇的表项索引
- 文件结束标志
- 下一个簇号
- 可用来管理空闲磁盘块
- 虚拟文件系统 VFS
- 概述
- 提供统一的文件系统接口, 支持多种文件系统类型
- 抽象文件系统的实现细节, 提供一致的文件操作接口
- 提高文件系统的可移植性和扩展性
- 结构
- VFS接口层
- 定义统一的文件操作接口, 如
open(), read(), write(), close()等
- 文件系统实现层
- 实现具体的文件系统类型, 如ext4, NTFS, FAT32等
- 设备驱动层
- 工作原理
- 进程发起文件操作请求, 调用VFS接口层的函数
- VFS根据文件路径解析出对应的文件系统类型
- 调用对应文件系统实现层的函数进行具体操作
- 文件系统通过设备驱动层访问底层存储设备完成操作
- 文件系统挂载
- 概述
- 将一个文件系统集成到操作系统的目录树中, 使其内容对用户和应用程序可见
- 挂载点: 目录树中的一个目录, 用于挂载文件系统
- 挂载过程
- 创建挂载点目录
- 使用
mount系统调用将文件系统挂载到指定的挂载点
- 挂载后, 访问挂载点目录时, 实际访问的是挂载的文件系统
- 卸载过程
- 使用
umount系统调用将文件系统从挂载点卸载
- 卸载前, 确保没有进程正在访问该文件系统
- 优点
- 5 输入输出管理
collapsed:: true
- IO管理基础
- 基本概念
- 统一IO接口
id:: 693c0bd9-2ada-4bfa-94d3-4de780c68eb2
- 为不同类型的IO设备提供统一的访问接口, 用标准方式使用物理设备
- 虚拟设备
id:: 693c0bfa-74ba-4003-b55e-953b58c7997e
- 将一个物理设备抽象为多个逻辑设备, 提供更灵活的访问方式
- IO接口类型
- 块设备
- 支持按块读写数据的设备
- 典型设备: 磁盘驱动器、固态硬盘(SSD)
- 字符设备
- 支持按字符流读写数据的设备
- 典型设备: 键盘、鼠标、串口设备
- 网络设备
- 以数据报为单位进行数据传输的设备
- 典型设备: 网卡、无线网卡
- IO控制方式
- ((693b708a-8e30-4be1-8e8f-f1d0a6ca4c47))
- 又称为轮询方式, 由CPU不断检查IO设备状态, 判断是否需要进行数据传输
- ((693b708a-9326-4c78-aa6d-2940ceabd813))
- IO设备在准备好数据传输时, 通过中断信号通知CPU
- ((693b708a-1d58-4146-8ef6-e3505e2c3df9))
- 直接内存访问方式, 允许IO设备直接与内存交换数据, 减少CPU参与
- IO软件层次结构 #🤔 考前记
- 用户层IO软件
- 直接与用户应用程序交互
- 提供标准化的接口, 以便程序能够访问 IO 设备
- 设备独立性软件
- 屏蔽不同 IO 设备的硬件差异，提供统一的接口供上层软件使用
- 实现了设备无关的功能，例如文件系统管理、设备命名、缓冲管理和错误处理
- 设备驱动程序
- 直接与具体硬件设备交互的部分
- 每个设备驱动程序针对特定类型的硬件设备设计，负责将设备独立性软件的通用命令转换为设备能够理解的特定指令
- 中断处理程序
- 专门处理硬件中断的部分
- 当设备完成操作或发生事件（如数据到达、错误发生）时，硬件会触发中断信号，中断处理程序迅速响应以处理这些事件
- 硬件
- 直接负责执行物理IO操作，包括实际的设备控制器、寄存器、端口和数据传输通道
- IO应用接口
- 设备独立性软件
- 缓冲区管理
- 磁盘高速缓存
id:: 693bd4c5-5a8b-4d08-a8d9-2e66b3fb8390
- 利用内存中的缓冲区缓存磁盘数据, 提高读写效率
- 逻辑上属于磁盘, 物理上驻留在内存中
- 缓冲区实现 #🤔 考前记
- 单缓冲
- 磁盘到缓冲区
T, 缓冲区到用户进程M, CPU处理时间C
- 每块处理时间:
max(T, C) + M
- 原则：缓冲区不能同时被两端读写
- 双缓冲
- 循环缓冲
- 缓冲池
- 设备分配与回收
- 设备分配策略
- 数据结构
- 设备分配方式
- 静态分配: 在程序开始时分配设备,并在程序结束时释放设备
- 动态分配: 在程序运行过程中根据需要分配和释放设备
- 分配安全性
- 安全分配: 确保操作系统在分配设备时不会导致死锁
- 非安全分配: 不考虑死锁风险, 可能导致系统进入不安全状态
- 逻辑设备与物理设备映射
- 逻辑设备名: 用户和应用程序使用的设备标识符
- 物理设备名: 实际硬件设备的标识符
- 操作系统通过逻辑设备表(LUT)实现逻辑设备与物理设备的映射
- 假脱机 SPOOLING
- 基本思想
- 将数据暂时存放在磁盘等中间存储区域，再由专门的后台程序将其送往目标外设（如打印机）
- 实现了设备的分时共享和异步操作
- 组成
- 输入缓冲区和输出缓冲区
- 内存中开辟的两个缓冲区，用来暂存输入设备传入的数据和从输出井准备传给输出设备的数据
- 输入进程和输出进程
- 输入井和输出井
- 在磁盘上开辟的两个区域，用来存放输入数据和输出数据
- 井管理程序
- 优点
- 提高设备利用率
- 把独占设备改造为共享设备
- 实现了虚拟设备
- 考点 #🤔 考前记
- 输出进程至少需要两种驱动程序: 磁盘驱动程序和输出设备驱动程序
- 数据流向
- 数据传送是由系统实现的, 用户进程不参与数据传送过程
- 设备驱动程序
- 功能
- 初始化设备
- 控制设备操作
- 处理中断
- 提供设备状态信息
- 特点
- 与硬件紧密相关, 一部分需使用汇编语言编写
- 与IO控制方式相关, 如中断驱动、DMA等
- 应允许可重入
- 外存管理
- 磁盘
- 磁盘格式化 #🤔 考前记
- 低级格式化(物理格式化)
- 磁盘分区
- 高级格式化(逻辑格式化)
- 创建文件系统结构
- 初始化文件系统元数据
- 建立根目录
- 磁盘调度算法
- 先来先服务 FCFS
- 最短寻道时间优先 SSTF
- 扫描算法 SCAN
- 循环扫描 C-SCAN
- 磁臂黏着
- 短时间大量请求集中在某个区域时，导致磁臂频繁在该区域内移动，形成“黏着”现象，影响整体性能
- 除了FCFS算法外，其他调度算法都可能出现磁臂黏着现象
- ((693b708a-8e5d-4623-bace-e4ac36835532))
- 磁盘引导流程 #🥶 冷门
id:: 693be6d4-edfe-405c-8a83-50442a4dabe3
- 加电自检 (Power-On)
- 执行 ROM 中的引导程序 (bootstrap loader)
- 执行磁盘的主引导记录 (MBR)
- 执行分区引导记录 (PBR)
- 执行操作系统初始化程序