操作系统学习笔记（一）-- 引论
操作系统学习笔记（二）-- 引论
1. 处理机调度的层次和调度算法的目标
-
处理机调度的层次
- 高级调度：对象是作业，将处于后备队列的作业调入到内存。
- 中级调度：即内存调度，旨在提高内存利用率和系统吞吐量，将暂时不能运行/能运行的进程调出/入内存。
- 低级调度：对象是进程，决定就绪队列中哪个进程获得处理机，运行频率最高。
-
调度算法的目标
-
共同目标
-
资源利用率，即尽可能使所有资源都处于忙碌状态
-
公平性
-
平衡性
-
策略强制执行
-
-
批处理系统目标
- 平均周转时间短
- 系统吞吐量高
- 处理机利用率高
-
分时系统的目标
- 响应时间快
- 均衡性
-
实时系统的目标
- 截止时间的保证
- 可预测性
-
2. 作业与作业调度
-
批处理系统中的作业
- 作业：包含通常的程序和数据即作业说明书。
- 作业步：各个作业间相互独立，每个加工步骤成为一个作业步。
- 作业控制块(JCB)：作业进入系统时建立JCB，保存了对作业进行管理和调度所需的全部信息。
- 三种状态和三个阶段
- 收容阶段(后备状态)
- 运行阶段(运行状态)
- 完成阶段(完成状态)
-
作业调度
-
先来先服务(FCFS)调度算法：可用于作业、进程调度，系统按照作业到达的先后次序进行调度。
-
短作业优先(SJF)调度算法：可用于作业、进程调度，作业越短优先级越高。
- 优点：能有效地降低作业的平均等待时间，提高系统吞吐量。
- 缺点：需要预知作业运行时间；对长作业不利；无法实现交互；未考虑作业优先性。
-
高优先权优先调度算法
-
优先级调度算法(PSA)的类型
- 非抢占式优先权算法：主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
- 抢占式优先权调度算法：常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
-
优先权的类型
① 静态优先权：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变
② 动态优先权：动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。 -
高响应比优先(HRRN)调度算法：既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。
Rp优先级 =（等待时间 + 要求服务时间）/ 要求服务时间 = 响应时间 / 要求服务时间
-
-
3. 进程调度
-
进程调度的任务、机制和方式
-
任务
① 保存处理及现场信息；
② 按某种算法选取进程；
③ 把处理器分配给进程。
-
机制
-
方式
① 非抢占方式：进程一旦分配到处理机，就让其一直运行下去，不会因其他条件抢占当前正在运行进程的处理机，直至结束。
② 抢占方式：暂停某个正在运行的进程，将其处理机分配给另一个进程。遵循三个原则：优先权原则、短进程优先原则、时间片原则。
-
-
轮转调度算法
主要应用于分时系统。
让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有 n 个进程，则每个进程每次大约都可获得 1/n 的处理机时间。
时间片大小的确定：时间片略大于一次典型的交互所需要的时间。
-
多队列调度算法
将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法。
-
多级反馈队列调度算法
设置多个就绪队列，每个就绪队列都采用 FCFS 算法，按队列优先级调度。
若进程在本就绪队列的时间片完成则结束该进程，否则进入下一优先级就绪队列末尾等待执行，以此类推；若进程从阻塞队列被唤醒，则插入到比其本身高一优先级队列的末尾执行。
4. 实时调度
-
实现条件
① 提供必要的信息
② 系统处理能力强
③ 采用抢占式调度机制
④ 具有快速切换机制 -
分类
① 非抢占式调度算法- 非抢占式轮转调度算法
- 非抢占式优先调度算法
② 抢占式调度算法
- 基于时钟中断的抢占式优先级调度算法
- 立即抢占的优先级调度算法
-
最早截止时间优先(EDF)算法：根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。
-
最低松弛度优先(LLF)算法：根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。
5. 死锁概述
-
资源
- 可重用性资源：可供用户重复使用多次的资源；此类资源中的单元只能分配给一个进程使用，不允许多个进程共享；遵循请求资源 -> 使用资源 -> 释放资源的顺序；数目固定，进程既不能创建也不能删除。
- 可消耗性资源：临时性资源，由进程在运行期间动态地创建和删除。
- 可抢占性资源：某进程得到该资源后，该资源仍可被其他进程或系统抢占，如CPU、主存等。
- 不可抢占性资源：某进程得到该资源后，不能将此类资源强制回收，只能等待其主动释放，如打印机等。
-
计算机系统中的死锁
-
竞争不可抢占性资源引起死锁
-
竞争可消耗资源引起死锁
-
进程推进顺序不当引起死锁
-
-
死锁
-
定义：在多道程序系统中，一组进程中的每一个进程都在无限期地等待另一组进程所占有且永远不会释放的资源。
-
产生的必要条件
① 互斥条件
② 请求和保持条件
③ 不可抢占条件
④ 循环等待条件
-
处理死锁的方法
① 预防死锁
② 避免死锁
③ 检测死锁
④ 解除死锁
-
6. 预防死锁
-
破坏“请求和保持”条件
-
第一种协议：进程在运行前，必须一次性地申请运行过程中的全部资源。
- 优点：简单、易行、安全。
- 缺点：资源被严重浪费，严重恶化了资源利用率；使进程经常会发生饥饿现象(某进程所需某资源可能被其他进程长期占用)。
-
第二种协议：获得运行必不可少的资源后立即开始运行，在运行过程中逐步释放已分配的且已用毕的资源再申请所需新资源。
- 使进程更快完成任务，提高设备利用率，减少进程发生饥饿的几率。
-
-
破坏“不可抢占”条件
进程已占有的资源会被暂时地释放，待以后需要时再重新申请。
- 代价较高，延长了进程周转时间，增加了系统开销，降低了系统吞吐量。
-
破坏“循环等待”条件
对系统所有资源类型线性排序，规定每个进程必须按序号递增的顺序请求资源
- 优缺点：限制了新类型设备的增加，造成资源浪费，限制用户简单、自主编程。
7. 避免死锁
避免死锁的实质在于,系统在进行资源分配时,应使系统不进入不安全状态。
-
安全状态：在系统进行资源分配前计算此次资源分配是否安全，安全则分配，否则令进程等待。
-
利用银行家算法避免死锁
-
数据结构
可用 Available
最大需求 Max
已分配 Allocation
还需要 NeedNeed = Max - Allocation
-
银行家算法
设 Requesti 是进程 Pi 的请求向量，如果 Requesti[ j ] == K，表示进程 Pi 需要 K 个 Rj 类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査
(1) 如果 Requesti[ j ] ≤ Need[ i, j ]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果 Requesti[ j ] ≤ Available[ i ]，便转向步骤(3)；否则，表示尚无足够资源，Pi 须等待。
(3) 系统试探把资源分配给进程 Pi 并修改下面数据结构中的数值Available[ j ] = Available[ j ] - Requesti[ j ]
Allocation[ i, j ] = Allocation[ i, j ] + Requesti[ j ]
Need[ i, j ] = Need[ i, j ] - Requesti[ j ]
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程P，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程P等待。
-
安全性算法
(1) 设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在执行安全性算法开始时，
Wok = Available；② Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[ i ] = false；当有足够资源分配给进程时，再令 Finish[ i ] = true。
(2) 从进程集合中找到一个能满足下述条件的进程 ① Finish[ i ] = false；② Needl[ i, j ] ≤ Work[ j ]；若找到，执行步骤(3)，否则，执行步骤(4)。
(3) 当进程 P 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行Work[ j ] = Work[ j ] + Allocation[ i, j ]
Finish[ i ] = true
go to step 2；
(4) 如果所有进程的 Finish[ⅰ] = true 都满足,则表示系统处于安全状态，否则，系统处于不安全状态。
-
8. 死锁的检测与解除
-
检测
若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。
-
死锁的解除
- 抢占资源。从一个或多个进程中抢占足够数量的资源,分配给死锁进程,以解除死锁状态。
- 终止(或撇消)进程。终止(或撤消)系统中的一个或多个死锁进程,直至打破循环环路,使系统从死锁状态解脱出来。
- 终止所有死锁进程
- 逐个终止进程