内容大纲
- 1、处理机调度基本概念、调度方式
- 2、典型调度算法及基本准则
- 3、进程同步基本概念
- 4、进程同步实现方法及典型同步问题
1 处理机调度
(1) 基本概念
在多道程序设计系统中，内存中有多道程序运行，它们相互争夺处理机这一重要资源。处理机调度就是从就绪队列中，按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
作业从提交开始直到完成，往往需要经历三级调度。
(2) 调度的三个层次
高级调度发生在新进程的创建中，它决定一个进程能否被创建，或者创建后能否被置成就绪状态；
中级调度反映到进程状态上就是挂起和解除挂起，它根据系统的当前负荷情况决定停留在主存中进程数；把不是特别需要的调出到辅存。起到平滑和调整系统负荷的作用。
低级调度决定哪一个就绪进程占有CPU，占用多长时间。它是操作系统最为核心的部分。分为：剥夺方式（高优先级剥夺原则和时间片剥夺原则）和非剥夺方式两种。
层次模型
(3) 低级调度过程
- 记录进程（内核级线程）的状态。一般记录在一个进程（内核级线程）的进程控制块（线程控制块）内。
- 决定某个进程（内核级线程）什么时候获得处理器，以及占用多长时间。
- 把处理器分配给进程（内核级线程）。即进行进程（内核级线程）上下文切换，把选中进程（内核级线程）的进程控制块（线程控制块）内有关现场信息送入处理器相应的寄存器中，让它占用处理器运行。
- 收回处理器。将处理器有关寄存器内容送入该进程（内核级线程）的进程控制块（线程控制块）内的相应单元，使该进程出让处理器。
2 典型调度算法及基本准则
(1) 选择调度算法的原则
资源利用率
- CPU利用率=CPU有效工作时间/CPU总的运行时间
- CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间
响应时间
- 交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。
- 使交互式用户的响应时间尽可能短，或尽快处理实时任务，这是分时系统和实时系统衡量调度性能的一个重要指标。
吞吐量
- 单位时间内处理的作业数。
公平性
- 确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。
周转时间
- 批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短，这是批处理系统衡量调度性能的一个重要指标。
批处理系统的调度性能指标：批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间越短，则系统效率越高，作业吞吐量越大。
如果作业i提交给系统的时刻是Ts ，完成时刻是Tf ，该作业的周转时间Ti为：
Ti = Tf - Ts ; 作业平均周转时间 T = (Σ Ti) / n
实际上，它是作业在系统里的等待时间与运行时间之和。
如果作业 i 的周转时间为Ti ，所需运行时间为Tk，则称Wi= Ti / Tk为该作业的带权周转时间。作业平均带权周转时间W = (Σ Wi) / n
Ti是等待时间与运行时间之和，故带权周转时间总大于1。
为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。
(2) 典型调度算法
先来先服务(FCFS first come first serve)
短作业优先(SJF short job first)
优先级：可分为（1）非剥夺式（2）剥夺式；其中优先级可分为：（1）静态优先级（2）动态优先级
高响应比优先：响应比=（等待时间+处理时间）/处理时间=1+等待时间/处理时间
时间片轮转
先来先服务
- 按照进程进入就绪队列的先后次序分配处理器。先进入就绪队列的进程优先被挑选，进程一旦占有处理器将一直运行直到结束或阻塞。这是一种非剥夺式调度。
- 算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。有利于CPU繁忙型作业而不利于I/O繁忙型作业。
例 ： 设进程P1 , P2 , P3的运行时间分别为24、3、3。若3个进程按P1 , P2 , P3的顺序到达，则按FCFS算法，求平均等待时间和平均周转时间。
解： 等待时间： P1 = 0; P2 = 24; P3 = 27
平均等待时间：(0 + 24 + 27)/3 = 17
周转时间：P1 = 24; P2 = 27; P3 = 30
平均周转时间：(24 + 27 + 30)/3 = 27
短作业优先
- 每个进程有一个CPU时间（运行时间）。利用进程的CPU时间的长度作为调度的依据，每次总是将CPU时间最短的进程调度到CPU上运行。
- 有两种短作业调度的实现方式:
非抢占SJF – 进程一旦获得CPU，就一直运行直到它主动放弃CPU为止。
抢占式SJF – 若新到达进程的CPU时间少于当前正在运行的进程，则新进程就抢占原进程的CPU。又被称为Shortest-Remaining-Time-First (SRTF)。
例 ： 设进程P1 , P2 , P3的运行时间分别为24、3、3。若3个进程按P1 , P2 , P3的顺序到达，则按短作业优先算法，求平均等待时间和平均周转时间。
解： 等待时间： P1 = 6; P2 = 0 ; P3 = 3
平均等待时间：(6 + 0 + 3)/3 = 3 （17）
周转时间：P1 = 30; P2 = 3; P3 = 6
平均周转时间：(30 + 3 + 6)/3 = 13 （27）
忽视了作业等待时间，会出现饥饿现象；
该算法对长作业不利，甚至造成长作业处于饥饿状态。
— 如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。
优先级调度算法
每个进程都被赋予一个优先数 (整形值)，CPU总是分配给具有最高优先级的进程。
抢占式高优先级调度
非抢占式高优先级调度
存在的问题：可能发生饥饿现象
解决方法：使进程优先级随着它等待时间的延长而增长。
高响应比优先
由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。故又可表示为：
- 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
- 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
- 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。
时间片轮转RR
- 系统将所有的就绪进程按先来先服务的原则，排成一个队列。
- 每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。
- 当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；
- 然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
多级反馈队列
- 设置多个就绪队列，每个队列赋予不同的优先级，第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。
- 赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍。
- 新进程进入内存后，先进入第1个队列的末尾，按照FCFS原则排队等待调度。时间片用完后，若完成则撤离系统。若未完成，进入第2个队列末尾，再按照FCFS调度。各个队列按时间片轮转算法调度。
-
仅当第1~i-1个队列都为空时，才会调度第i个队列中的进行运行。若正执行第i个队列某进程时，又有新进程进入优先权高的队列，则此时新进程抢占运行进程的处理器。
image.png
3 进程同步基本概念
(1) 进程同步的背景
有一环形缓冲池，包含n个缓冲区（0~n-1）。有两类进程：一组生产者进程和一组消费者进程，生产者进程向空的缓冲区中放产品，消费者进程从满的缓冲区中取走产品。
count++ 的执行过程（机器指令）� register1 = count� register1 = register1 + 1� count = register1
count-- 的执行过程（机器指令）� register2 = count� register2 = register2 - 1� count = register2
设初始状态为 “count = 5” :
S0: producer execute register1 = count {register1 = 5}�S1: producer execute register1 = register1+1 {register1 = 6} �S2: consumer execute register2 = count {register2 = 5} �S3: consumer execute register2=register2-1 {register2 = 4} �S4: producer execute count = register1 {count = 6 } �S5: consumer execute count = register2 {count = 4}
正确结果应该是： “count = 5” ，
现在的结果是： “count = 4”
(2) 进程同步的概念
- 多道程序环境下，进程并发执行，不同进程存在相互制约关系。为协调该关系，避免进程冲突，引入进程同步。
临界资源：一次仅允许一个进程使用的资源称为临界资源。比如：打印机、共享变量等。
临界区：是指并发进程中访问临界资源的程序段。
进入区：检查是否可以进入临界区，若可以，设置正在访问临界区标志。
退出区：清除正在访问临界区标志。
进程的互斥是指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。
进程的同步是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。
进程互斥关系是一种特殊的进程同步关系。
临界区访问原则
- 互斥访问– 若已有进程进入临界区，则其他的进程必须等待其离开临界区，释放临界资源。 （忙则等待）
- 前进– 若没有进程处于其临界区，应允许一个请求进入临界区的进程立即进入临界区，访问临界资源。（空闲让进）
- 有限等待– 对请求访问的进程，应保证能在有限的时间内进入临界区，避免进入“死等”。
- 让权等待– 当进程不能进入临界区时，该进程应释放处理机，以免进入“忙等”状态。
4 进程同步实现方法及典型同步问题
(1) 进程同步的实现方法---软件方法
- 在进入区设置和检查一些标志来标明是否有进程在临界区，若有则在进入区循环检查进行等待，进程在退出区修改标志，以允许别的进程进入临界区。
Peterson 算法
1981年，由Peterson提出，满足临界区访问的4原则。
设有两个进程Pi和Pk，且 LOAD 和 STORE 指令是原子操作。 Pi和Pk共享两个变量:
int turn;
Boolean flag[2] ;
变量 turn：turn==i 表示Pi可进入其临界区。
数组 flag ： flag[i] = true 表示进程Pi请求进入临界区!
若pi和pk同时请求进入临界区，while中的turn变量可保证只允许一个进入临界区,从而实现了互斥。考虑Pi进程的代码，flag[i] = true;意味着Pi想进入临界区，同时将turn设置为k, 若Pk在临界区，则Pi的while条件为真，Pi等待。若PK不在临界区，则flag[k]为false，Pi进入临界区，从而避免了死等。
(1) 进程同步的实现方法---硬件方法
很多系统都提供了解决临界区问题的硬件支持。
- 对于单处理器环境 – “禁止中断”
并发进程可以无预设地运行
限制了交替执行程序的能力，执行效率明显降低。 - 许多现代计算机系统提供了特殊的原子（执行该代码时不允许被中断）机器指令：
TestAndSet指令：读出标志并把该标志设置为TRUE。
Swap指令：交换两个内存字的内容。
利用TestAndSet解决临界区访问算法。
声明一个布尔变量互斥锁 lock, 初值为false。
利用Swap解决同步算法
共享全局布尔变量 lock，初值为FALSE;
每个进程定义一个局部布尔变量 key.
(2) 经典同步问题
生产者消费者
问题描述：一组生产者进程和消费者进程共享一个初始为空的缓冲池，含N个缓冲区，每个缓冲区可以存放一个消息。缓冲池未满时，生产者才能把消息放到缓冲池，否则，生产者等待。缓冲池不空时，消费者才能取出消息，否则，消费者等待。
这个缓冲池是临界资源，只允许一个生产者放消息，或者一个消费者取消息。
生产者和消费者进程对缓冲池的访问是互斥关系。
另一方面，只有生产者生产之后消费者才能消费，它们也是同步关系。
信号量设置：
互斥信号量 mutex，初值为 1，控制互斥访问缓冲池。
同步信号量 full，初值为 0。记录“满”缓冲区的个数。
同步信号量 empty，初值为 N。记录“空”缓冲区的个数。
Semaphore mutex=1; //缓冲池互斥信号量
Semaphore empty =n; //缓冲池中空闲缓冲区个数，初始值为n
Semaphore full=0; //缓冲池中满缓冲区个数，初始值为0
对信号量的PV操作成对出现。另多个P操作顺序不能颠倒，否则容易引起死锁。
读者写者
有一个供多个并发进程共享的数据集，如：数据库
读者进程 – 只能读数据集; 这些进程不执行更新数据集的操作。
写者进程 – 负责更新数据库。
问题描述 :
允许多个读者进程同时执行读操作，写者进程必须互斥执行写数据集的操作.
分析：
写者比较简单，与任何进程互斥，用互斥信号量的P、V操作即可解决。
读者比较复杂。与其他读者是同步，与写者是互斥。这里用一个计数器ReadCount ，用来记录当前读者数目。
如果读者数目ReadCount为0，则可能有也可能没有写者在写；
如果读者数目ReadCount不为0，则不会有写者在写，请求读的读者便可读；
如果读者数目ReadCount为0，又没有写者在写，则请求写的写者才能写。
哲学家进餐
问题描述：5个哲学家致力于思考和进餐，思考不影响其他人，饥饿时拿起左右两边的筷子（一根一根地拿起）。若筷子在别人手中，等待。进餐完，放下筷子继续思考。
思路：
关键是如何让一个哲学家拿到左、右两根筷子而不造成死锁或者饥饿现象的发生。
设置一个互斥信号量数组chostick[5]={1,1,1,1,1}，用于实现对5根筷子的互斥访问。�
若5个哲学家都要进餐，同时拿起左边的筷子p( chopstick[i] );筷子都被拿光了，等到想拿右边得筷子p( chopStick[ (i + 1) % 5] );时，全都阻塞，造成死锁。
可采取以下几种解决方法：
- 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
- 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
-
规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。
image.png
