操作系统原理笔记(二)
四、资源管理
4.1 资源管理概述
资源管理的目标
- 高利用率：保证资源的高利用率
- 避免饥饿：在“合理”时间内使所有顾客有获得所需资源的机会
- 互斥使用：对不可共享的资源实施互斥使用
- 避免死锁：防止由资源分配不当而引起的死锁
资源管理的功能
- 描述资源数据结构：包含资源的物理名、逻辑名、类型、地址、分配状态等
- 确定资源分配原则：决定资源应分给谁，何时分配，分配多少等问题
- 实施资源分配：执行资源分配、资源收回工作
- 存取控制和安全保护：对资源的存取进行控制并对资源实施安全保护措施
资源分配的类型
静态分配（基于作业调度）：在进程运行前，操作系统即分配该进程所需的全部资源
动态分配（基于进程调度）：在进程运行中，边运行边向操作系统提出资源申请，操作系统根据申请分配资源
4.2 资源分配机构
- 资源描述器：描述各类资源的最小分配单位的数据结构
- 包含资源名，类型，大小，地址，分配标志，描述器连接信息，存取权限等
- 资源信息块：描述某类资源的请求者、可用资源和资源分配程序等必要信息的数据结构
| 内容 | 指向 |
|---|---|
| 等待队列头指针 | 请求者队列 |
| 可利用资源队列头指针 | 可利用资源队列 |
| 资源分配程序入口地址 | 资源分配程序 |
中央处理机资源信息块
4.3 资源分配策略(★)
- 先请求先服务
- 队列结构：按请求的先后次序排序，每一个新产生的请求均排在队尾；
- 当资源可用时，取队首元素，并满足其需要
- 优先调度
- 队列结构：按优先级的高低排序，对每个进程指定优先级，每一个新产生的请求，按其优先级的高低插到相应的位置；
- 当资源可用时，取队首元素，并满足其需要
4.4 死锁(★)
4.4.1 死锁的定义
定义
在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们正占有着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。
进程在占有某个资源而请求某种资源，当该进程占有的资源是别人请求的资源时，就可能产生死锁
进程-资源分配图
- 两类顶点
所有的进程P
所有的资源R
两类有向边
- 资源请求边：如果进程$P_i$请求资源$R_j$，则存在一条由$P_i$指向$R_j$的有向边
- 资源分配边：如果资源$R_j$分配给进程$P_i$，则存在一条由$R_j$指向$P_i$的有向边
- 两类顶点
4.4.2 产生死锁的必要条件
互斥条件：涉及的资源是非共享的，为临界资源
不剥夺条件（非抢占）：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走
部分分配：进程每次只申请他所需要的资源的一部分，在等待新一批资源的时候，进程继续占用分配到的资源
环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求
4.4.3 解决死锁
死锁预防
- 静态预防死锁：在作业调度的时候就给选中的作业分配它所需要的全部资源（破坏部分分配）
- 有序资源分配法：系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配（破坏环路条件）
死锁避免（银行家算法）
要求进程声明需要资源的最大数目，在分配资源时判断是否会出现死锁，只有在不会出现死锁时才分配资源
数据结构
算法过程
- 寻找一个没有标记的进程$p_i$，该进程需满足资源请求矩阵$D$的第$i$行向量小于或等于剩余资源向量$R$（这意味着能够满足该进程的资源请求）；
- 如果存在这样的进程，则将资源分配矩阵$A$的第$i$行向量加到$R$中（这意味着该进程执行后 ，将把已占有资源释放给剩余资源池），标记该进程，并转到第1步；如果找不到这样的进程，则转到第3步；
- 如果所有进程均被标记，则系统处于安全状态（即所有进程均能被执行）；否则系统处于不安全状态
死锁的检测和解除
- 对资源的分配不加任何限制，也不采取死锁避免措施，而是系统定时地运行一个“死锁检测”程序，检测到死锁后采取措施解除
- 根据进程-资源分配图检测死锁
- 如果进程-资源分配图中无环路，则此时系统没有发生死锁；
- 如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程；
- 如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件
- 解除死锁
- 立即结束所有进程的执行，并重启操作系统
- 撤销陷于死锁的所有进程
- 逐个撤销陷于死锁的进程，回收其资源，直至死锁解除
- 剥夺陷于死锁的进程占用的资源，但并不撤销它， 直至死锁解除
- 根据系统保存的检查点，让所有进程回退，直到足以解除死锁
死锁定理：P个进程共享m个同类资源，如果所有进程对资源的最大需要数目之和小于P+m，该系统不会发生死锁
五、处理机调度
5.1 作业调度
5.1.1 作业调度概述
对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行
- 作业存储在辅存设备上
- 在辅存中挑选一个作业，将其载入到主存
- 作业被载入到主存后，建立其对应的进程结构，使之投入运行
- 运行完毕，回到第二步
作业控制块JCB：存放作业控制和管理信息
作业调度的因素
- 注意系统资源均衡使用
- 保证提交的作业在截止时间内完成
- 设法缩短作业平均周转时间
5.1.2 作业调度算法的性能衡量
- 周转时间：作业提交给计算机系统到该作业的结果返回给用户所需要的时间
- 平均周转时间：$t=\frac{1}{n}\sum_\limits{i=1}^{n}t_i$
- 带权周转时间：一个作业的周转时间与其运行时间的比值$w_i=\frac{t_i}{t_{ri}}$
- 平均带权周转时间：$w=\frac{1}{n}\sum_\limits{i=1}^{n}w_i$
5.1.3 作业调度算法(★)
- 先来先服务：优先考虑等待时间最长的作业
| 作业 | 提交时间$T_{si}$ | 运行时长$T_{ri}$ | 开始时间 | 结束时间$T_{ci}$ | 周转时长$T_i$ | 带权周转时间$w_i$ |
|---|---|---|---|---|---|---|
| 1 | 8.00 | 2.00 | 8.00 | 10.00 | 2.00 | 1 |
| 2 | 8.50 | 0.50 | 10.00 | 10.50 | 2.00 | 4 |
| 3 | 9.00 | 0.10 | 10.50 | 10.60 | 1.60 | 16 |
| 4 | 9.50 | 0.20 | 10.60 | 10.80 | 1.30 | 6.5 |
平均周转时间$t=1.725$，平均带权周转时间$w=6.875$
- 短作业优先调度：优先考虑运行时间最短的作业
| 作业 | 提交时间$T_{si}$ | 运行时长$T_{ri}$ | 开始时间 | 结束时间$T_{ci}$ | 周转时长$T_i$ | 带权周转时间$w_i$ |
|---|---|---|---|---|---|---|
| 1 | 8.00 | 2.00 | 8.00 | 10.00 | 2.00 | 1 |
| 2 | 8.50 | 0.50 | 10.30 | 10.80 | 2.30 | 4.6 |
| 3 | 9.00 | 0.10 | 10.00 | 10.10 | 1.10 | 11 |
| 4 | 9.50 | 0.20 | 10.10 | 10.30 | 0.80 | 4 |
平均周转时间$t=1.55$，平均带权周转时间$w=5.15$
- 响应比高者优先调度：响应比=响应时间/运行时间，其中响应时间表示运行时间与已等待时间之和
| 作业 | 提交时间$T_{si}$ | 运行时长$T_{ri}$ | 开始时间 | 结束时间$T_{ci}$ | 周转时长$T_i$ | 带权周转时间$w_i$ |
|---|---|---|---|---|---|---|
| 1 | 8.00 | 2.00 | 8.00 | 10.00 | 2.00 | 1 |
| 2 | 8.50 | 0.50 | 10.10 | 10.60 | 2.10 | 4.2 |
| 3 | 9.00 | 0.10 | 10.00 | 10.10 | 1.10 | 11 |
| 4 | 9.50 | 0.20 | 10.60 | 10.80 | 1.30 | 6.5 |
平均周转时间$t=1.625$，平均带权周转时间$w=5.675$
5.2 进程调度
5.2.1 进程调度概述
基本功能
在众多处于就绪状态的进程中，按一定的原则选择一个进程运行
调度：组织和维护就绪进程队列
分派：处理机空闲的时候，从就绪队列首部选取一个PCB投入运行
调度时机
- 当一个进程从运行态切换成等待态时
- 当一个进程从运行态切换成就绪态时
- 当一个进程从等待态切换成就绪态时
- 当一个进程终止时
调度方式
非抢占方式：高优先级的进程无法打断正在运行的进程
抢占方式：高优先级的进程可以打断正在运行的进程
5.2.2 进程调度算法(★)
优先数调度算法：优先级最高的先被调度
- 静态优先数：在进程创建时，根据其需使用的资源、进程类型以及程序运行时间的估计确定
- 动态优先数：在进程运行时，动态改变优先数
- 进程使用CPU超过一定数值时，降低优先数
- 进程进行I/O操作后，增加优先数
- 进程等待时间超过一定数值时，增加优先数
循环轮转调度算法
- 简单循环轮转调度
- 每个进程被调度后，占用一个时间片，时间片用完后转为就绪态并进入就绪队列队尾
- 可变时间片轮转调度
- 时间片动态选取：过长则轮转时间过长，过短则进程切换开销增加
- 调整时间片需要消耗系统时间，调整周期过大则等效固定时间片，过小则调整开销增加
- 多重时间片轮转调度
- 将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列
- 较高优先级的队列分配较短的时间片，较低优先级的队列分配较长的时间片
- 优先从高级就绪进程队列中选取进程，只有在其为空时，才从较低级的就绪进程队列中选取进程
- 简单循环轮转调度
六、主存管理
6.1 主存管理概述
主存共享方式
大小不同的区域：分区存储管理、段式存储管理
大小相等的区域：页式存储管理
段页式存储管理
逻辑组织
一维地址结构
- 一个程序是一个连续、线性的地址结构
- 确定线性地址空间中的指令地址或操作数地址只需要一个信息
二维地址结构
- 一个程序由若干个分段组成，每个分段是一个连续的地址区
- 确定线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量
6.2 主存管理功能
基本概念
物理地址（绝对地址、实地址）：计算机主存单元的真实地址
主存空间：物理地址的集合所对应的空间
逻辑地址（相对地址、虚地址）：用户的程序地址 （指令地址或操作数地址）
程序地址空间：用户程序所有的逻辑地址集合对应的空间
主存管理功能
- 地址映射：将逻辑地址变换成主存中的物理地址
| 静态地址映射 | 动态地址映射 |
|---|---|
| 在程序装入时确定地址映射关系 | 在程序运行时确定地址映射关系 |
| 需软件（重定位装入程序） | 需硬件地址变换机构（重定位寄存器） |
| 耗费时间长 | 映射速度快 |
主存分配
- 构造主存资源信息块（包括等待队列、空闲区队列、主存分配程序）
- 制定分配策略
- 实施主存分配和回收
存储保护
- 主存按照区的模式分配给各用户程序使用，每个用户程序必须在给定的存储区域内活动
- 上下界保护：设置上界寄存器和下界寄存器，程序访问内存只能使用在上界寄存器和下界寄存器之间的物理地址，否则发生越界中断
- 基地址、限长保护：基址寄存器表示程序在内存中存储空间从何开始，限长寄存器限制程序访问的逻辑地址，其为逻辑地址的最大值
主存扩充
- 程序的全部代码和数据存放在辅存中；
- 将程序当前执行所涉及的那部分程序代码放入主存中；
- 程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行
6.3 分区存储管理(★)
6.3.1 静态分区
- 把内存预先划分成多个分区，分区大小可以相同或不同，一旦确定则整个系统运行阶段中都保持不变
- 一个分区装入一个作业
6.3.2 动态分区
在运行程序的过程中：建立分区，依照用户请求的大小分配分区
分区分配数据结构
主存资源信息块M_RIB
- 等待队列头指针
- 空闲区队列头指针
- 主存分配程序入口地址
分区描述器PD
- flag：为0表示空闲，为1表示占用
- size：分区大小
- next：如果是空闲区，则为下一个空闲区的首地址；如果是已分配区，该项为0
分区分配
- 寻找空闲块：依申请者所要求的主存区的大小，分区分配程序在自由主存队列中找一个满足用户需要的空闲块
- 若找到了所需的空闲区
- 空闲区与要求的大小相等，将该空闲区分配并从队列中摘除
- 空闲区大于所要求的的大小，将空闲区分为两部分：一部分成为已分配区，建立已分配区的描述器，剩下部分仍为空闲区
- 返回所分配区域的首址
- 否则，通知申请者无法满足要求
分区回收
检查被回收分区在主存中的连接情况
如果上/下邻接空闲区，则合并，成为一个新的空闲区
若回收分区不与任何空闲区相邻接，则建立一个新的空闲区，加入到空闲队列
6.3.3 选择空闲区的放置策略
- 首次适应算法
- 将程序放置到第一个足够装入它的地址最低的空闲区
- 空闲区队列：按空闲区地址由低到高排序
- 最佳适应算法
- 将程序放置到主存中与它所需大小最接近的空闲区中
- 空闲区队列：按空闲区大小由小到大排序
- 最坏适应算法
- 将程序放置到主存中与它所需大小差距最大的空闲区中
- 空闲区队列：按空闲区大小由大到小排序
6.3.4 分区管理的缺点
- 程序必须整体装入
- 需要分配连续的内存空间
- 碎片问题：在已分配的区域里面存在着一些没有被充分利用的空闲区
6.4 页式存储管理(★)
6.4.1 基本概念
- 页面（虚页）：逻辑地址空间被等分成大小相等的片，称为页面
- 主存块（实页）：物理地址空间又被分成大小相等的片，称为主存块
- 页表：为了实现地址映射，系统建立的记录页面与主存块之间对应关系的地址变换的机构称为页面映像表
- 页表缓冲TLB：CPU中用于存放热页表项的高速缓存，地址变换速度快，但成本较高
- 主存区域中的页表：地址变换速度比硬件慢，成本较低
6.4.2 页式地址变换
- 地址变换过程
- CPU给出逻辑地址
- 分页机构将逻辑地址分成两部分——高地址页号为P，低地址页内偏移为W
- 已知页表基址寄存器指示的首地址PTBR，则PTBR+P就是该虚页对应的页表项地址，获得物理块块号B
- 将物理块块号B和页内偏移量W合并，即得到物理块地址
- 快表TLB（联想存储器）
- 先在快表中查找有没有相关页表项记录，快表是一个独立的硬件，独立于内存之外
- 如果快表中没有，只能查找存储在内存中的页表，然后把查出来的页表项记录在快表里面
- 多级页表
- 间接引用
- 页表项中可能存储的不是物理块号，而是下一级页表的首地址
6.4.3 请调页面的机制
两种页式系统
简单页式系统：装入一个程序的全部页面才能投入运行
请求页式系统：装入一个程序的部分页面即可投入运行
扩充页表项
- 中断位：表示此页是不是在主存里面，如果是0表示在主存，如果为1表示不在主存
- 辅存地址：表示该页在辅存中的地址
缺页中断
- 当需要访问的逻辑地址所在虚页不在主存时，需要操作系统将该页面调入主存后再进行访问
- 缺页中断的处理
- 如果没有空闲的主存块，则需要淘汰某个虚页，该虚页对应的主存块重新分配（如果该虚页发生修改，则需要将修改写入外存）
- 从外存中调入所需的页并调整页表
- 重新启动被中断的指令
- 抖动
- 简单地说，导致系统效率急剧下降的主存和辅存之间的频繁的页面置换现象.
6.4.4 淘汰策略
在发生缺页中断且没有空闲的主存块时，选择淘汰哪一页的规则称为淘汰策略
扩充页表项
- 引用位：该页最近是否被访问，1表示已被访问
- 脏位：该页是否被修改，1表示已被修改
最佳算法（OPT算法）
- 当需要淘汰页面时，所淘汰的页面应是以后不会使用的，或是在最长的时间以后才会使用的页面
- 建立在已知未来页面访问顺序的前提下，理想化的算法
先进先出淘汰算法（FIFO算法）
- 总是淘汰在主存中停留时间最长（最早进入主存）的页面
- 实现方法
- 建立一个页面进入主存的页号表
- 建立一个替换指针，指向最早进入主存的页面
- 当需要置换一页时，选择替换指向的那一页，然后调整替换指针的内容
- 实现方法2
- 在存储分块表中记录页面进入主存的先后次序
最久未使用算法（LRU算法）
- 实现方法：采用页号栈
- 最新被访问的页面入栈，最久未访问的页面在栈底
- 要淘汰某个元素了，栈底元素出栈，新的页号入栈
- 实现方法：采用页号栈
时钟算法（CLOCK算法、LRU近似淘汰算法）
- 为每一个存储块（存储分块表）或页面（页表）设立一个引用位，当访问某页时，就将该页引用位置1
- 当内存中无对应数据
- 如果访问位为0即置换并将访问位置1
- 如果访问位为1，则不置换，将该访问位置0，然后指针下移，重复第一步
- 当内存中有对应数据
- 将该数据访问位置1，指针不移动
6.5 段式与段页式存储管理
段式系统
段：程序中自然划分的一组逻辑意义完整的信息集合，如代码段、数据段
段式地址变换
- 将段地址划分为程序地址(s,w)，其中s为段号，w为段内偏移
- 用段号s检索段表，得到该段的起始地址B
- 如果w＜0或w≥L则发生主存越界中断；否则(B+w)即为物理地址
段页式系统
在一个分段内划分页面，就形成了段页式存储管理
段页式地址变换
- 将段页式地址划分为程序地址(s,p,w)，其中s为段号，p为段内页号，w为页内偏移
- 根据段号s找到该段的页表基址PTEP
- 根据段内页号p查找页表，得到物理页号，与页内偏移合并得到物理地址
6.6 Linux存储管理(★)
地址映射机构MMU
- CPU把虚拟地址送给MMU
- MMU进行地址映射
- MMU把物理地址送给存储器
多级页表
二级页表
对于32位虚拟地址空间，假设页面大小为$4K$，页表项大小为$4$字节
则一个进程最大拥有$4G$字节内存，即一个进程拥有$\frac{4G}{4k}=2^{20}$个页面
其页表项个数为$2^{20}$个，因此该进程的页表占用了$\frac{2^{20}*4}{ 4K}=2^{10}$个页面
即32位的虚拟地址应划分$$(C_{10},P_{10},W_{12})$$，其中C表示页表号，P表示页号，W表示页内偏移
在进行地址映射时，使用页表号在页目录中查询页表地址，然后使用页号在页表中查询物理页号，物理页号与页内偏移组合后得到物理地址
