进程状态转换
就绪态 (Ready): 进程万事俱备, 只缺少 {c1:: CPU} 资源.
Q: 进程五态之间的关系, 画图
A: 
进程控制
导致进程创建的典型事件有:
- 用户登录: {c1:: 为登录的用户创建一个新的进程}
- 作业调度: {c2:: 批处理系统中的作业调度程序选中一个作业}
- 提供服务: {c3:: 操作系统为响应用户请求而创建一个进程}
- 应用请求: {c4:: 用户进程主动请求创建一个子进程}
- 程序执行: {c5:: 用户在终端或图形界面中启动一个应用程序}
Q: 设备分配会导致新进程的创建吗?
A: 不会
设备分配是在系统中设置对应的数据结构实现的
不需要创建进程
Q: 撤销父进程与撤销子进程的影响
A: 撤销子进程时, 应将其从父进程那里获得的资源还给父进程
撤销父进程时, 通常也会同时撤销其所有的子进程
进程通信
管道通信
Q: 一个管道可以实现两个进程之间的双向通信吗?
A: 不可以
当你通过 pipe () 系统调用创建一个管道时, 内核会返回两个文件描述符:
fd[0]: 管道的读端 (read end)
fd[1]: 管道的写端 (write end)
数据的流动方向是固定的: 数据只能从写端 fd[1] 流入, 从读端 fd[0] 流出, 是一种半双工通信方式.
只能实现单向的通信
进程与线程
进程是{资源分配}的基本单位
线程是{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: 高级调度 (作业调度)、中级调度 (内存调度) 和低级调度 (进程调度).
Q: 什么是高级调度 (作业调度)?
A: 决定将外存上的哪个作业调入内存, 为其创建进程并分配资源. 它控制了进入系统的作业数量.
Q: 什么是中级调度 (内存调度)?
A: 决定将内存中哪个暂时不能运行的进程换出到外存 (挂起), 或将外存中具备条件的进程换入内存 (激活). 目的是提高内存利用率.
Q: 什么是低级调度 (进程调度)?
A: 决定就绪队列中的哪个进程可以获得 CPU 的使用权. 这是最基本、最频繁的调度.
现代操作系统中, 典型的进程调度时机有:
{c1: 创建新进程}
{c2: 进程终止}
{c3: 当前进程被阻塞时}
{c4: I/O 完成, 进程从阻塞态变为就绪态}
{c5: 中断结束}
Q: 时间片轮转算法, 为什么中断处理结束, 可能进行进程调度?
A: 中断可能是时钟中断. 时钟中断结束, 当前进程的时间片剩余时间可能为 0, 需要进行进程调度
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 不能同时访问某个资源
临界区互斥必须遵循的四大原则是{c1: 空闲让进}、{c2: 忙则等待}、{c3: 有限等待}和{c4: 让权等待}.
Q: 临界区互斥原则中的”空闲让进”是什么意思?
A: 当临界区没有进程使用时, 应允许一个请求进入的进程立即进入.
Q: 临界区互斥原则中的”忙则等待”是什么意思?
A: 当临界区已被占用时, 其他试图进入的进程必须等待.
Q: 临界区互斥原则中的”有限等待”是什么意思?
A: 对请求访问的进程, 应保证其在有限时间内能进入临界区, 以防止”饥饿”.
Q: 临界区互斥原则中的”让权等待”是什么意思?
A: 当进程不能进入临界区时, 应立即释放 CPU, 从运行态转为阻塞态, 以避免”忙等”.
实现互斥的基本方法
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 进行循环检查 (忙等).
Q: 实现临界区互斥的硬件方法中,“中断屏蔽”方法有什么主要局限性?
A: 它在多核/多处理器系统中无效, 因为屏蔽单个 CPU 的中断并不能阻止其他 CPU 上的进程访问临界资源.
信号量机制
Q: 用硬件还是软件实现信号量同步/互斥机制?
A: 可以用硬件实现, 也可以用软件实现
Q: 整型信号量与记录型信号量的定义
A: - 整型信号量:
表示资源数目的整型变量 S
- 记录型信号量:
表示资源数目的整型变量 value
链接所有等待该资源的进程的链表 L
Q: 记录型信号量解决了整型信号量的什么缺点?
A: 整型变量缺点:
如果临界资源数目不够, 使用整型变量的进程会一直处于 while 循环中
并未遵循”让权等待”的准则
记录型信号量:
如果临界资源数目不够, 会用 block 原语对进程进行自我阻塞, 主动放弃 CPU, 并插入该类资源的等待队列
遵循”让权等待”的准则
管程
Q: 管程用硬件实现还是软件实现?
A: 软件
管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块
Q: 为什么任何时候只能有一个进程在管程中执行
A: 确保了对管程内部共享资源的访问是互斥的
Q: 管程可以实现让权等待吗?
A: 可以
process.wait (), 将进程转换为阻塞态, 放入阻塞队列
Q: 管程 (Monitor) 和记录型信号量 (Record-based Semaphore) 这两种不同机制, 实现互斥和同步的方法有什么区别?
A: 管程是一种高级同步原语, 它将共享数据和对该数据进行操作的若干过程封装在一个模块里, 保证了对共享数据的互斥访问和同步操作
记录型信号量则是将信号量与数据结构 (记录) 相结合, 提供了一种更结构化的方式来管理信号量及其相关的操作.
管程机制的条件变量等价于信号量机制的{信号量}
死锁
Q: 饥饿与死锁的定义
A: 饥饿: 至少有一个进程的执行被无限期推迟
死锁: 一组内的每个进程都在等待一个事件, 而该事件只可能由组内的另一个进程产生
Q: 饥饿与死锁的对象有什么不同?
A: 一个或者几个进程发生饥饿
一组进程内发生死锁, 一组内至少要有两个进程
Q: 死锁产生的四大必要条件
A: 资源互斥
不可剥夺
请求与保持 (请求新资源, 保持已获得资源)
循环等待
死锁的处理策略
死锁预防: 最保守, 破坏{死锁的必要条件}实现
死锁避免: 中庸, 避免进入{不安全状态}
死锁处理: 最激进, 发生死锁后,{想办法处理}
Q: 银行家算法是死锁避免算法还是死锁预防算法
A: 死锁避免
死锁预防是破坏了四个必要条件中的某个
银行家算法并没有
Q: 银行家算法为什么不用判断当前是否处于死锁状态?
A: 银行家算法是死锁检测算法的变体
不同于死锁检测算法, 检测当前是否存在死锁，银行家算法会跟踪每个进程可能提出的最大资源请求量，在批准某个可能导致未来死锁的请求前就予以阻止。
Q: 如何通过资源分配图判断是否发生死锁?
A: 先进行化简
如果化简之后仍然存在环则会发生死锁
否则不会发生死锁
k 个进程竞争使用, 每个进程最多要 n 个资源
不会发生死锁的 m 的最小值是{