进程状态转换
就绪态 (Ready): 进程万事俱备, 只缺少 {c1:: CPU} 资源。
阻塞态 (Blocked/Waiting): 进程因等待某一事件 (如 I/O 完成) 而暂停执行, 等待的是 {c1:: CPU 以外的资源}。
Q: 进程五态之间的关系, 画图
A: 
进程控制
导致进程创建的典型事件有:
- 用户登录: {c1::为登录的用户创建一个新的进程}
- 作业调度: {c2::批处理系统中的作业调度程序选中一个作业}
- 提供服务: {c3::操作系统为响应用户请求而创建一个进程}
- 应用请求: {c4::用户进程主动请求创建一个子进程}
- 程序执行: {c5::用户在终端或图形界面中启动一个应用程序}
Q: 设备分配会导致新进程的创建吗?
A: 不会
设备分配是在系统中设置对应的数据结构实现的
不需要创建进程
Q: 撤销父进程与撤销子进程的影响
A: 撤销子进程时, 应将其从父进程那里获得的资源还给父进程
撤销父进程时, 通常也会同时撤销其所有的子进程
进程通信
管道通信
Q: 一个管道可以实现两个进程之间的双向通信吗?
A: 不可以
管道只支持单向通信
一定要有两个管道才能实现双向通信
即使是父子进程, 也需要两个管道
进程与线程
进程是{资源分配}的基本单位
线程是{CPU 调度}的基本单位
Q: 为什么切换线程的开销比切换进程的开销小? (地址空间角度考虑)
A: 属于同一进程的所有线程都具有相同的地址空间
而不同进程拥有各自独立的地址空间
相同地址空间, 使得切换线程开销变小
线程的状态与转换
线程的状态与转换与进程的状态与转换, 基本相同
用户级线程与内核级线程
Q: 什么是用户级线程?
A: 线程的管理 (创建, 撤销和切换等) 在用户态实现
Q: 用户态线程对于操作系统是透明的吗?
A: 是的
进程管理的 PCB 在内核态中
线程管理的 TCB 在用户态中
操作系统不能够直接获取线程信息, 等于线程不存在
Q: 什么是系统级线程?
A: 系统级线程 (System-Level Thread), 通常与内核级线程 (Kernel-Level Thread) 同义, 是指由操作系统内核直接创建、调度和管理的线程.
Q: 用户级线程间的切换比内核级线程间的切换效率, 谁更高?
A: 用户级线程.
用户级线程管理在用户态执行, 不用进入内核态
效率更高
Q: 用户级线程与内核级线程调度由谁来完成?
A: 用户级线程: 由包含该线程的进程, 管理线程调度
内核级线程: 操作系统管理线程调度
CPU 调度
Q: 什么是单核处理机? 什么是多核处理机?
A: 就是单核 CPU 与多核 CPU
Q: CPU 三级调度的定义
A: 高级调度: 作业调度. 将外存中的作业调入内存中. 一般只有多道批处理系统中有
中级调度: 内存调度. 暂时不能运行的进程调至外存, 外存上已具备运行条件进程重新调入内存
低级调度: 进程调度. 按照某种算法从就绪队列中选取一个进程, 将 CPU 分配给它
现代操作系统中, 应该进行进程调度与切换的情况如下
- 创建新进程
- 当前进程正常结束后或者异常终止后
- 当前进程被阻塞时
- 原先等待 I/O 的进程从阻塞态变为就绪态
Q: CPU 调度的性能指标: “周转时间”是如何计算的?
A: 作业完成时刻 - 作业提交时刻
Q: CPU 调度的性能指标: “带权周转时间”是如何计算的?
A: 作业周转时间 / 作业实际运行时间
Q: CPU 调度的性能指标: “吞吐量”的定义是什么?
A: 单位时间内 CPU 完成作业的数量。
Q: CPU 调度的性能指标: “CPU 利用率”的定义是什么?
A: CPU 实际有效工作时间占总运行时间的比例。
进程调度
Q: 处理机调度和进程调度有什么区别?
A: 没区别
处理机调度就是进程调度
Q: 什么是饥饿现象?
A: 进程一直无法获得运行所需的必要资源
Q: 饥饿所需要的资源是 CPU 资源吗?
A: 不只是 CPU 资源
“资源” = 任何导致进程/线程等待的东西
除了 CPU 资源还有内存资源, I/O 资源 (硬件设备) 等等
Q: 哪些进程调度算法会有缺乏 CPU 资源的饥饿现象?
A: 只有短作业优先 (SJF) 调度算法可能有饥饿现象
Q: 批处理系统使用的是哪种进程调度算法?
A: 短作业优先 (SJF) 调度算法
Q: 分时操作系统使用的是哪种进程调度算法?
A: 时间片轮转 (RR) 调度算法
哪些时候可以进行进程调度?
进程结束
创建新进程
系统调用完成
同步与互斥
一次仅允许{c1:: 一个}进程使用的资源称为临界资源。
Q: 同步与互斥的定义
A: 同步: 进程 A, B 运行有先后关系
互斥: 进程 A, B 不能同时访问某个资源
Q: 临界区互斥四大原则及其含义
A: 空闲让进: 临界区空闲时, 可以允许一个请求进入临界区的进程立即进入临界区.
忙则等待: 当已有进程进入临界区时, 其他试图进入临界区的进程必须等待.
有限等待: 对请求访问的进程, 应保证能在有限时间内进入临界区, 防止进程无限等待.
让权等待 (原则上应该遵循, 但非必须): 当进程不能进入临界区时, 应立即释放处理器, 防止进程忙等待.
实现互斥的基本方法
Q: 实现临界区互斥的“单标志法”是如何工作的?
A: 设置一个公共整型变量 turn, 用于指示允许哪个进程进入临界区。例如, turn == 0 允许 P0 进入, turn == 1 允许 P1 进入。
Q: 实现临界区互斥的“单标志法”有什么缺陷?
A: 两个进程必须交替进入临界区。若某个进程不再需要进入, 会导致另一个进程也无法进入, 违背了“空闲让进”原则。
Q: 实现临界区互斥的“双标志先检查法”是如何工作的?
A: 设置一个布尔数组 flag[], flag[i] = true 表示进程 i 希望进入临界区。进程先检查对方的 flag, 如果对方不想进入, 自己再将 flag 设为 true 并进入。
Q: 实现临界区互斥的“双标志先检查法”有什么缺陷?
A: 两个进程可能在检查 flag 后、设置 flag 前同时通过检查, 导致它们同时进入临界区, 违背了“忙则等待”原则。
Q: 实现临界区互斥的“双标志后检查法”是如何工作的?
A: 设置一个布尔数组 flag[]。进程先将自己的 flag 设为 true, 然后再检查对方的 flag。如果对方 flag 也为 true, 则等待。
Q: 实现临界区互斥的“双标志后检查法”有什么缺陷?
A: 两个进程可能同时设置 flag 并检查对方, 导致双方都认为对方要进入而互相谦让, 谁也无法进入临界区, 造成“饥饿”, 违背了“空闲让进”和“有限等待”原则。
Q: Peterson 算法是如何巧妙地解决临界区互斥问题的?
A: 它结合了“双标志法”的 flag 数组和“单标志法”的 turn 变量, 通过 turn 来决定谦让冲突中的哪一方, 从而保证了“空闲让进”、“忙则等待”和“有限等待”。
Q: Peterson 算法是否遵循了“让权等待”原则?
A: 没有。进程在无法进入临界区时, 仍会占用 CPU 进行循环检查 (忙等)。
硬件实现
中断屏蔽方法
不适用于多处理器系统,
硬件指令方法——TestAndSet 指令
为每个临界资源设置一个共享布尔变量 lock, 表示该资源的两种状态: true 表示正被占用 (已加锁); false 表示空闲 (未加锁)
相比于软件实现方法, TS 指令将”加锁”和”检查”操作用硬件的方式变成了一气呵成的原子操作
此不能实现”让权等待”.
硬件指令方法——Swap 指令
和 TestAndSet 指令类似
用硬件指令方法实现互斥的优点:①简单, 容易验证其正确性;②适用于任意数目的进程,
支持多处理器系统;③支持系统中有多个临界区, 只需为每个临界区设立一个布尔变量. 缺点:
①等待进入临界区的进程会占用 CPU 执行 while 循环, 不能实现”让权等待”;②从等待进程中
随机选择一个进程进入临界区, 有的进程可能一直选不上, 从而导致”饥饿”现象.
互斥锁 (自旋锁) 通常采用硬件机制来实现
其主要缺点是违背了”让权等待”
信号量机制
Q: 用硬件还是软件实现信号量同步/互斥机制?
A: 可以用硬件实现, 也可以用软件实现
Q: 整型信号量与记录型信号量的定义
A: - 整型信号量:
表示资源数目的整型变量 S
- 记录型信号量:
表示资源数目的整型变量 value
链接所有等待该资源的进程的链表 L
Q: 记录型信号量解决了整型信号量的什么缺点?
A: 整型变量缺点:
如果临界资源数目不够, 使用整型变量的进程会一直处于 while 循环中
并未遵循”让权等待”的准则
记录型信号量:
如果临界资源数目不够, 会用 block 原语对进程进行自我阻塞, 主动放弃 CPU, 并插入该类资源的等待队列
遵循”让权等待”的准则
管程
Q: 管程用硬件实现还是软件实现?
A: 软件
管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块
任何时候只能有一个进程在管程中执行
管程中定义的变量只能被管程内的过程访问
Q: 管程可以实现让权等待吗?
A: 可以
process.wait(), 将进程转换为阻塞态, 放入阻塞队列
Q: 管程 (Monitor) 和记录型信号量 (Record-based Semaphore) 这两种不同机制, 实现互斥和同步的方法有什么区别?
A: 管程是一种高级同步原语, 它将共享数据和对该数据进行操作的若干过程封装在一个模块里, 保证了对共享数据的互斥访问和同步操作
记录型信号量则是将信号量与数据结构 (记录) 相结合, 提供了一种更结构化的方式来管理信号量及其相关的操作.
死锁
Q: 饥饿与死锁的定义
A: 饥饿: 至少有一个进程的执行被无限期推迟
死锁: 一组内的每个进程都在等待一个事件, 而该事件只可能由组内的另一个进程产生
Q: 饥饿与死锁的对象有什么不同?
A: 一个或者几个进程发生饥饿
一组进程内发生死锁, 一组内至少要有两个进程
Q: 死锁产生的四大必要条件
A: 资源互斥
不可剥夺
请求与保持 (请求新资源, 保持已获得资源)
循环等待
死锁的处理策略
死锁预防: 最保守, 破坏{死锁的必要条件}实现
死锁避免: 中庸, 避免进入{不安全状态}
死锁处理: 最激进, 发生死锁后,{想办法处理}
Q: 银行家算法是死锁避免算法还是死锁预防算法
A: 死锁避免
死锁预防是破坏了四个必要条件中的某个
银行家算法并没有
Q: 如何通过资源分配图判断该状态是否是死锁
A: 资源分配图存在边, 则为死锁
否则, 不是死锁
总共有 m 个资源, 由 K 个进程竞争使用, 每个进程最多要 n 个资源
不会发生死锁的 m 的最小值是{