处理机调度与死锁
一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度:
高级调度
-> 低级调度
-> 中级调度
*高级调度* {
又称作业调度、长程调度 、接纳调度
作用：把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配资源、排在就绪队列上，准备执行。
分时系统、实时系统，通常不需要作业调度。
}
*低级调度* { 进程调度
也称为进程调度、短程调度 。
作用：决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。
在OS中都必须配置。
}
进程调度的两种调度方式 {
*1, 非抢占方式 {
一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或阻塞时，才再把处理机分配给其他进程。
}
非抢占方式引起进程调度的因素 {
[1] 进程执行完毕，或因发生某事件而不能在继续执行；
[2] 执行中的进程因提出I/O请求而暂停执行
[3] 在进程通信或同步过程中执行了某种原语操作，如P操作（WAIT操作）、BLOCK原语、WAKEUP原语等。
}
*2, 抢占方式 {
允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
抢占原则 {
（1）优先权原则。优先权高的进程抢占处理机。
（2）短作业优先原则。短作业（进程）抢占当前较长作业（进程）的处理机。
（3）时间片原则。各进程按时间片运行，当一个时间片用完后重新调度。
}
}
中级调度 {
又称中程调度 。
目的 ：提高内存利用率和系统吞吐率
作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上又具备运行条件的就绪进程，重新调入内存，并修改为就绪状态，挂在就绪队列上。
又称对换
}
调度队列模型 {
仅有进程调度的调度队列模型
有高级和低级调度的调度队列模型
同时有三级调度的调度队列模型
}
仅有进程调度的调度队列模型 {
通常，把就绪进程组织成FIFO队列，每当创建新进程时排在就绪队列的末尾，按时间片轮转方式运行
进程在执行时，出现三种情况：
[1] 任务在时间片内完成，进程便在释放处理机后进入完成状态；
[2] 任务在时间片内未完成，OS便将该任务再放入就绪队列的末尾；
[3] 在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。
}
有高级和低级调度的 调度队列模型 {
与前一模型的差别：
（1）就绪队列的形式。批处理系统中最常用的是优先权队列。也可采用无序链表方式。
（2）设置多个阻塞队列。
}
有三级调度的调度队列模型 {
调出时，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞；
在中级调度使外存就绪转变为内存就绪。
}
OS-14
选择调度方式和 调度算法的准则 {
面向用户的准则 {
(1), 周转时间短
(2), 响应时间快
(3), 截止时间的保证
(4), 优先权准则
}
面向系统的准则 {
(1), 系统吞吐量高
(2), 处理机利用率好
(3), 资源的平衡利用
}
}
*周转时间 {
从作业被提交给系统开始，到作业完成为止的这段时间间隔称为作业周转时间。包括四部分时间：
在外存后备队列上等待调度的时间
进程在就绪队列上等待调度的时间
进程在CPU上执行的时间
进程等待I/O操作完成的时间
*}
* 平均周转时间：{ T=1/n[∑ Ti] (i=1~n)}
* 带权周转时间: {
W = T/Ts
T：作业的周期时间
Ts：系统为提供为它提
供服务的时间（真正运行时间）。
}
平均带权周转时间 ：{
W=1/n[∑ Ti/Tsi ]
}
响应时间 {
响应时间是从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间间隔。它包括三部分时间：
从键盘输入的请求信息传送到处理机的时间
处理机对请求信息进行处理的时间
将响应信息回送到终端显示器的时间。
是分时系统中的重要原则。
}
截止时间 { * 实时系统
是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。
对于严格的实时系统，其调度方式和调度算法必须能保证这一点 。
}
吞吐量 {
吞吐量指单位时间内系统所完成的作业数。
评价批处理系统性能的重要指标 。
与作业的平均长度有关。对于大型作业，一般吞吐量约为每小时一道作业对于中、小型作业，其吞吐量则可达到数十道作业。
}
OS-15
调度算法 {
调度算法是指：根据系统的资源分配策略所规定的资源分配算法 。
不同的系统和系统目标，通常采用不同的调度算法
}
先来先服务调度算法 {
作业调度中每次从后备作业队列中，选择一个或多个最先进入该队列的作业调入内存，为它们分配资源、创建进程，然后放入就绪队列。
进程调度时每次从就绪队列中，选择一个最先进入该队列的进程分配处理机使之运行。直到完成或阻塞后，才放弃处理机。
---
是一种最简单的调度算法既可用于作业调度也可用于进程调度。
FCFS( first come first serve)算法
有利长作业（进程），而不利于短作业（进程）。
有利CPU繁忙型作业，而不利于I/O繁忙型作业。
}
短作业（进程）优先法 {
短作业优先（SJF）法：从后备队列中选择一个或若干个估计运行时间最短的作业调入内存运行。
短进程优先（SPF）调度算法：从就绪队列中选出一估计运行时间最短的进程，分配处理机使它立即执行直到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
}
SJ （P）F法缺点 {
（1）对长作业不利。如果有一长作业进入系统的后备队列，由于总是优先调度那些短作业（进程），将导致长作业长期不被调度。
（2）完全未考虑作业的紧迫程度，不能保证紧迫性作业（进程）会被及时处理。
（3）作业（进程）的长短根据用户所提供的估计执行时间而定的不一定能真正做到短作业优先调度。
}
高优先权优先调度算法 {
1．优先权调度算法的类型
2．优先权的类型
3. 高响应比优先调度算法
}
OS-16
优先权调度算法类型 {
1）非抢占式优先权算法
2）抢占式优先权调度算法
}
*1 非抢占式优先权算法 {
把处理机分配给就绪队列中优先权最高的进程后便一直执行下去直至完成；或发生某事件使该进程放弃处理机时，可再将处理机重新分配给另一优先权最高的进程。
用于批处理系统和某些对实时性要求不严的实时系统中。
}
*2** 抢占式优先权调度算法 {
把处理机分配给优先权最高的进程，使之执行。在执行期间，只要又出现优先权更高的进程，就重新将处理机分配给新到的优先权最高的进程。
能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
}
优先权的类型 {
(1), 静态优先权 {
在创建进程时确定
在进程的整个运行期间保持不变。
一般地，用某一范围内的一个整数来表示的，例如，0~7或0~255中的某一整数，又把该整数称为优先数。
----------------------------------------------
确定优先权依据：
（1）进程类型：系统进程高于用户进程
（2）进程对资源的要求：要求少的进程应赋予较高优先权。
（3）用户要求。这是由用户进程的紧迫程度及所付费多少来确定。
--静态优先权法优缺点--- 简单，系统开销小不精确，仅在要求不高的系统中使用
}
动态优先权 {
优先权随进程推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
---高响应比优先调度算法-- {
引入动态优先权，并使作业优先级随着等待时间的增加而以速率a提高。
该优先权的变化规律为：
优先权 =（等待时间+要求服务时间）
/要求服务时间
优先权 = RP =响应时间/要求服务时间RP ：响应比
}
}
* 分析 {
作业等待时间相同，则有利于短作业。
要求服务时间相同，实现的是先来先服务。
长作业也可获得处理机。
优点：兼顾长短作业。
缺点：由于做相应比计算故增加了系统开销
}
* 时间片轮转法 {
分时系统中多采用时间片轮转法
把就绪进程组织成FIFO队列，
把CPU分配给队首进程，
规定它执行一个时间片。
时间片完时排在就绪队列的末尾，重新把处理机分配给就绪队列中新的队首进程，也执行一个时间片。
就绪队列中的所有进程在一给定时间内，均可获得一个时间片的CPU时间.
}
* 多级反馈队列调度算法 {
（1）为多个就绪队列赋不同的优先级。
第一个队列的优先级最高其余逐个降低。
各队列中进程执行时间片的也不同，优先权愈高的队列中时间片愈小。
（2）新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等待调度。到该进程执行时，如果能在该时间片内完成，便准备撤离系统；如果未完成，转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如此下去，当一个长作业从第一队列依次降到第N队列后，在第N队列中便采取按时间片轮转的方式运行。
（3）仅当第1~（i—1）队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列，则新进程将抢占处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。
}
* 多级反馈队列调度算法 的性能 {
（1）终端型作业用户。作业较小，只要使作业（进程）在第一队列所规定的时间片内完成，便可令用户满意。
（2）短批处理作业用户。其周转时间短。
（3）长批处理作业用户。不必担心作业长 期得不到处理。
}
实时调度基本条件 { ------start 实时调度---------
(1) 提供必要的信息
(2) 系统处理能力强
(3) 采用抢占式调度机制
(4) 具有快速切换机制
}
必要信息 {
(1) 就绪时间。
(2) 开始截止时间和完成截止时间。
(3) 处理时间。
(4) 资源要求。
(5) 优先级。
}
假定系统中有有M个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间间表示为Pi，N为系统中的处理机数。则必须满足下面的限制条件：
∑ Ci/ Pi≤ N
系统才是可调度的。
例:单处理机系统中有6个硬实时任务，它们的周期时间都是50MS，而每次的处理时间为10MS，则
∑ Ci/ Pi=6/5>1
所以系统是不可调度的----------------------------------------------
* 快速切换机制
对外部中断的快速响应能力。响应禁止中断的时间间隔尽量短
快速的任务分派能力。
* 实时调度算法分类
按任务性质 { 1), 硬实时调度算法 2), 软实时调度算法 }
按调度方式 { 1), 非抢占调度算法 2), 抢占调度算法 }
按调度时间 { 1), 静态调度算法 2), 动态调度算法 }
如： 非抢占式调度算法 {
算法简单，用在小型实时系统或要求不严的实时控制系统中。
分两种：
（1）非抢占式轮转调度算法 { 可获得数秒至数十秒的响应时间 }
（2）非抢占式优先调度算法 { 响应时间为数秒至数百毫秒 }
}
**抢占式调度算法 { 应用于响应时间在数十毫秒以下的系统。
根据抢占发生时间不同分类：
（1）基于时钟中断的抢占式优先权调度算法。
（2）立即抢占的优先权调度算法。
}
常用的实时调度算法 {
最早截止时间优先算法即EDF算法（EARLIEST DEADLINE FIRST）
最低松弛优先算法即LLF算法 || 高紧迫性优先算法
（LEAST LAXITY FIRST）
}
进程分配方式
多处理器系统中进程的调度与系统结构有关。
同构系统中进程可以分配到任一处理器上
非对称系统中进程只能分配到某一合适运行的处理器上。
OS-19
背景知识
* 计算机执行的任何程序都必须首先读入内存，CPU通过内存来访问程序，而安装
操作系统实际上是把存放在光盘上的OS执行代码存入硬盘的过程。
*1 从硬盘上加载程序到内存很方便。
*2 操作系统中的文件系统主要是靠硬盘提供物理支持。
* 安装OS到硬盘，实际上有两方面的作用
*1 在硬盘上建立文件系统
*2 把OS的全部内容事先存放在硬盘上以备使用
*3 当使用计算机时，从硬盘上加载OS到内存，然后将机器控制权转给OS内核来执行。
OS : 1核心 2外壳
OS-19
进程(线程) 调度方式
*1 自调度方式 + 优点 + 缺点
单处理机环境下的 FCFS, FPF, 抢占式的FPF调度算法。
整个系统中只设置一个就绪队列，供多个处理器共享。
优点 ： 容易将单CPU -> 多CUP。处理器利用率高！
缺点 ：(1) 瓶颈问题。 (2) 低效性。线程在整个生命周期多次更换处理器。高速缓存的使用效率很低。
(3) 线程切换频繁
线程是轻型进程，是处理机调度和分配的基本单位。提高切换线程!
缓存是处理器的缓存，一个处理器一个高速缓存。
线程切换非常频繁，缓存刚存进去就刷新。
*2 成组调度方式
-- 是指将一个进程中的一组线程，分配一组处理器上去执行。
-- 可用两种方式为应用程序分配处理器时间 ：
(1) 面向所有应用程序平均分配处理器时间。
(2) 面向所有线程平均分配处理器时间。
优点 ： 减少线程切换，优于自调度。
*3 专用处理机分配方式
指在一个应用程序的执行期间，专门为该应用程序分配一组处理器，每一个线程
一个处理器，供应用程序专用直至应用程序完成。
缺点 ： 可造成单个处理机的浪费。
该方式的引入原因 ：{
(1) 多处理机系统中单个处理机的利用率不很重要。
(2) 在一个应用程序的运行中完全避免了进程或线程的切换，大大加速运行。
}
***** 死锁 *******
*1 多个进程在运行过程中因竞争资源而造成的一种僵局。
*2 各并发进程彼此等待对方拥有的资源，且在得到对方资源前不释放自己的资源。
例子1，两只羊过独木桥
例子2，系统中共有5台打印机，进程A需要4，进程B需要4，A已经占3，B占用2
产生死锁的原因 {
(1) 竞争资源
(2) 进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致
产生死锁。
() 竞争资源引起死锁
(1) 可剥夺和非剥夺性资源 ： 可剥夺-进程获得该资源可以被其他进程剥夺。
(2) 竞争非剥夺性资源
(3) 竞争临时性资源
临时性资源 : 由一个进程产生由另一个进程使用暂短时间后便无用的资源。
如 ： 进程产生的消息。 可能引起死锁。
进程通信的死锁情况。
---- 产生死锁的必要条件 ----
(1) 互斥条件
(2) 请求和保持条件
(3) 不剥夺条件
(4) 环路等待条件
互斥条件 {
指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占有。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
}
请求和保持条件 {
指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
}
环路等待条件 {
指在发生死锁时，必然存在一个进程——资源的环性链，即进程集合{P0，P1，P2，——，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，——，Pn正在等待已被P0占用的资源。
}
--处理死锁的基本方法-- {
（1）预防死锁
（2）避免死锁
（3）检测死锁
（4）解除死锁
}
预防死锁 {设置某些限制条件，破坏四个必要条件中的一个或几个条件。}简单、较易实现。}
避免死锁 {
事先预防策略
在资源的动态分配过程中，用某种方法去防止系统进入不安全状态
可获得较高的资源利用率及系统吞吐量
实现上有一定的难度。
}
预防死锁 {
互斥条件（ 不可以 ）
请求和保持条件（ 可以 ）
不剥夺条件（可以 ）
}
环路等待条件（ ）}
死锁的解除
常采用的两种方法是：
（1）剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
（2）撤消进程。
①使全部死锁进程都夭折掉；
②按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。