第?章 进程管理 中

目录

第?节 调度算法的评价指标

知识预览

?些指标

第?节 ?结

第九节 FCFS、SJF、HRRN调度算法知识总览

先来先服务（FCFS，First come first serve) 例题

短作业优先（SJF，Shortest job First）例题1 （?抢占式）

例题2（抢占式）srtn最短剩余时间优先算法

对于FCFS和SJF两种算法的思考

?响应?优先（HRRN，Highest Response Ratio Next）例题

第九节?结

第?节 调度算法：时间?轮转、优先级、多级反馈队列知识总览

时间?轮转调度算法例题

优先级调度算法例题

优先级如何合理设置

动态优先级该如何调整思考

多级反馈队列算法例题

第?节?节第??节 进程同步 进程互斥概念引?

第??节?结

第??节 进程互斥地软件实现?法知识总览

如果不存在互斥单标志法

双标志先检查法例?双标志后检查法

pererson算法（?特森算法）第??节?节

第?三节 进程互斥地硬件实现?法知识总览

中断屏蔽?法

TestAndSet指令 swap指令

第?三节?结第?四节 信号量机制

知识总览

wait（P）和signal（V）整形信号量记录型信号量第?四节?结

第?五节 ?信号量实现进程互斥、同步、前驱关系知识总览

信号量机制实现进程互斥信号量机制实现进程同步信号量机制实现前驱关系第?五节?结

第?六节 ?产者消费者问题

思考是否能改变相邻pv操作顺序第?六节?结

第?节 调度算法的评价指标

知识预览

?些指标

CPU利?率：指CPU“忙碌”的时间占总时间的?例。

利?率=忙碌的时间/总时间

系统吞吐量：单位时间内完成作业的数量

系统吞吐量=总共完成了多少道作业/总共花了多少时间

eg：某计算机系统处理10道作业，共花费100买，则系统吞吐量为

10/100=0.1道/秒

周转时间：是指从作业被提交给系统开始，道作业完成诶那个为?的这段时间间隔。他包括四个部分：作业在外存后备队列上等待作业调度（?级调度）的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执?的时间、进程等待I/O 操作完成的时间。后三项在?个作业的整个处理过程中，可能发?多次。（后三项实为就绪态、运?态、阻塞态）

作业周转时间=作业完成时间-作业提交时间

带权周转时间=作业周转时间/作业实际运?时间=（作业完成时间-作业提交时间）/作业实际运?时间

对于周转时间相同的零个作业，实际运?时间?的作业在相同时间内被服务的时间更多，带权周转时间更?，?户满意度更?

对于实际运?时间相同的两个作业，周转时间短的带权周转时间更?，?户满意度更

?

平均带权周转时间=各作业带权周转时间之和/作业数

等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越?，?户满意度越低

指?户提交请求到?次产?响应所?的时间。

第?节 ?结

第九节 FCFS、SJF、HRRN调度算法知识总览

调度算法的学习思路

1、算法思想 2、算法规则

1. 这种算法是?于作业调度还是进程调度？
2. 抢占 式还是?抢占式
3. 优点和缺点
4. 是否会导致饥饿（某进程/作业?期得不到服务）

先来先服务（FCFS，First come first serve)

算法思想 主要从“公平”的?度考虑（类似?活中买东?的例?算法规则 按照作业/进程到达的先后顺序进?服务

?于作业/进程调度 ?于作业调度时，考虑的式那个作业先到达后备队列，?于进程调度时。考虑的式哪个进程先到达就绪队列是否可抢占 ?抢占式的算法

优缺点 优点 公平、算法实现简单 缺点排在?作业（进程）后?的短作业需要等待很

?时间，带权周转时间很?，对短作业来说?户体验不好。即，FCFS算法对?作业有利，对短作业`不利（Eg：排队买奶茶 你只买?杯奶茶?你的前边有?个?排队买

20被奶茶 你的带权周转时间会变得很? 体验很差）是否会导致饥饿 不会

例题

先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。

因此上图调度顺序为：P1-P2-P3-P4

周转时间=完成时间-到达时间

P1的周转时间=7-0=7

P2的周转时间=11-2=9 因为P2在2时刻就到达了然后等待P1执?完毕后P2才可以开始

P3的周转时间=12-4=8

P4的周转时间=12+4-5=11

带权周转时间=周转时间/运?时间

p1=7/7=1 p2=9/4=2.25 p3=8/1=8

p4=11/4=2.75

等待时间=周转时间-运?时间

P1=7-7=0

P2=9-4=5

P3=8-1=7

P4=11-4=7

平均周转时间=（7+9+8+11)/4=8.75

平均带权周转时间=（1+2.25+8+2.75）/4=3.5 平均等待时间=（0+5+7+7）/4=4.75

短作业优先（SJF，Shortest job First）

算法思想 追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间算法规则 最短的作业（进程）优先得到服务（所谓最短指的是要求服务时间最短）

?于作业/进程调度 即可?于作业调度，也可以?于进程调度。?于进程调度时称为“短进程优先算法” 是否可抢占？

SJF和SPF是?抢占式的算法。但是也有抢占式的版本—最短剩余时间优先算法

优点 ”最短的“平均等待时间、平均周转时间

缺点 不公平 对短作业有利，对?作业不利。可能产?饥饿现象，另外作业进程的运?时间是由?户提功德，并不?定真实，不?定做到真正的短作业优先

是否会导致饥饿 会，如果源源不断地有短作业/进程到来，可能使?作业/进程?时间得不到服务，产?“饥饿”现象。如果?直得不到服务，则程为“饥饿” 例题1 （?抢占式）

短作业/进程优先调度算法：每次调度时选择当前已到达且运?时间最短的作业（进程）

上图优先级顺序为p1-p3-p2-p4

周转时间=完成时间-到达时间

P1=7-0=7

P3=8-4=4

P2=12-2=10

P4=16-5=11

带权周转时间=周转时间/运?时间

P1=7/7=1 P3=4/1=4 P2=10/4=2.25 P4=11/4=2.75 等待时间=周转时间-运?时间

P1=7-7=0 P3=4-1=3 P2=10-4=6 P4=11-4=7

例题2（抢占式）srtn最短剩余时间优先算法

srtn最短剩余时间优先算法：每当有进程加?就绪队列改变时就需要调度，如果新到达的进程剩余时间?当前运?的进程剩余时间更短，则由新进程抢占处理机，当前进程重新回到就绪队列，另外当?个进程完成时也需要调度

TIPs：如果题?中未特别说明所提的短作业/进程优先算法默认时?抢占的

SJF调度算法的平均等待时间、平均周转时间最少是不严谨的 因为最短剩余时间算法得到的平均等待、周转时间更少 如果加上附加条件“在所有进程同时可运?时。采?

SJF算法的平均等待时间、平均周转时间最少

对于FCFS和SJF两种算法的思考

FCFS先来先服务算法是在每次调度的时候选择?个等待时间最?的作业（进程）为其服务。的那是没有考虑到作业的运?时间，因此导致了对短作业不由好的问题（买奶茶例?）

SJF算法是选择?个执?时间最短的作业为其服务。但是?完全不考虑各个作业的等待时间，因此导致了对?作业不友好的问题，甚?还会造成饥饿问题

为了解决这两个的缺点问题引出了?响应?优先（HRRN，Highest Response Ratio

Next）

?响应?优先（HRRN，Highest Response Ratio Next）算法思想 要综合考虑作业/进程的等待时间和要求服务的时间

算法规则 在每次调度时先计算各个作业/进程的响应?，选择响应?最?的作业/进程为其服务

响应?=（等待时间+要求服务时间）/ 要求服务时间 ?=1

?于作业/进程调度 即可?于作业调度，也可?于进程调度

是否可抢占 ?抢占式的算法。因此只有当前运?的作业/进程主动放弃处理机时，才需要调度，才需要计算响应?

优缺点 综合考虑了等待时间和运?时间（要求服务时间） 等待时间相同时，要求服务时间短的优先（SJF的优点） 要求服务时间相同时，等待时间?的优先（FCFS的优点） 对于?作业来说，随着等待会四溅越来越久，其响应?也会越来越?，从?避免了?作业饥饿的问题。

是否会导致饥饿 不会

例题

0时刻：只有P1到达就绪队列，P1上处理机

7时刻：（P1结束主动发起CPU）:就绪队列中有P2（响应?=（5+4）/4=2.25)、

P3((3+1)=4) 、P4（（2+4）/4=1.5）

8时刻：（P3完成）：P2（2.5）、P4（1.75）

12时刻：（P2完成）：就绪队列中只剩下P4

P2和P4要求服务时间?样，但P2等待时间?，所以必然是P2响应?更?

第九节?结

本?结需要多做题进?练习。

第?节 调度算法：时间?轮转、优先级、多级反馈队列

知识总览

时间?轮转调度算法

算法思想 公平的、轮流的为各个进程服务，让每个进程在?定的时间间隔内都可以得到响应

算法规则 按照各进程到达就绪队列的顺序，轮流让各个进程执??个时间?（如

ms）。若进程未在?个时间?内执?完，则剥夺处理机，将进程重新放到就绪队列尾重新排队。

?于作业/调度 主要?于进程调度（因为只有作业放?内存建?了相应的进程后，才能呢个杯分配处理机时间?）

是否可抢占 是?种抢占式的算法，由时钟装置发出的时钟中断来通知CPU时间已到。（计算机组成原理相关内容）

优缺点 优点：公平；?硬块，适?于分时操作系统，缺点：由于?频率切换进程，因此有?定开销；不去分任务的紧急程度是否会导致饥饿 不会导致饥饿例题

如果时间?太?，每?个进程都可以在?个时间?内完成诶那个，则时间?轮转调度

?法就退化为先来先服务调度算法?且会增?响应时间，因此时间?不能呢个太?但是如果时间?太?会导致系统频繁的切换，系统会化肥?量地时间来处理切换进程，从?导致?于进程执?的时间?例减?。因此时间?也不能太?。

优先级调度算法

算法思想 实时操作系统的出现，越来越多的应?场景需要根据任务的紧急程度来决定处理顺序

算法规则 每隔作业/进程有各?的优先级，调度室选择优先级最?的作业/进程

?于作业/调度 即可?于作业调度，也可?于进程调度。甚?嘛还会?于在之后会学习的I/O调度中

是否可抢占 抢占式、?抢占式都有。做题是的去别在于：?抢占式在进程主动放弃处理机时进?调度即可，?抢占式还需要在就绪队列变化是检查是否会发?抢占。优缺点 优点：?优先级区分紧急程度、重要程度，适?于实时操作系统。克灵活的调整对各种作业/进程的偏好程度。 缺点 若源源不断的有?优先级进程到来，则可能导致饥饿

是否会导致饥饿 会导致饥饿 新来的进程如果优先级较? 原先到达的优先级较低的进程可能?直没有机会上处理机运?

例题

?抢占式

?抢占式的优先级算法，?先P1到达了处理机，P1先运?直到主动放弃处理机然后此时P2和P3都到达了选择优先数?的P3运?，然后P2和P4优先数?样但是由于P2先到达所以先运?P2 抢占式

除了要关注主动放弃处理机的情况 还要关注新到达的进程优先级是否更?。每次调度时选择当前已到达且优先级最?的进程。当前进程主动放弃处理机时发?商呢个调度。另外，当就绪队列发?改变时也需要检查是否会发?抢占。

就绪队列未必只有?个，可以按照不同的优先级来进?组织。另外可以吧优先级?的进程排在更靠近队头的位置。 根据优先级是否可以动态改变，可以将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时确定，之后?直不变。

动态优先级:创建进程时有?个初始值，之后会根据情况动态的调整优先级

优先级如何合理设置

系统进程优于?户进程前台进程优于后台进程

操作系统更偏好于I/O繁忙型进程(对?时计算型进程—cpu繁忙型进程）

1.解释 I/O设备和CPU可以并??作，如果优先让io繁忙型进程优先运?的话，则

?有可能呢个让2.io设备尽早的投??作，则资源利?率，系统吞吐量都会得到提升

动态优先级该如何调整

从各进程公平、提升资源利?率等?度

1.如果进程在队列中等待了很?时间，则可以适当提升其优先级 ——等待时间变

?响应?会变?

2.如果进程占?处理机运?了很?时间，则可以适当降低其优先级

3.如果?个进程频繁的进?I/O操作，则可以认为该程序是?个I/O繁忙型进程 适当提升其优先级

思考

FCFS先来先服务算法的优点是公平

SJF短作业优先算法优点是能尽快处理完短作业，平均等待时间/周转时间等参数都很优秀

时间?轮转算法是可以让各个进程得到及时的响应 每个进程都被分配相对公平的执?时间

优先级调度算法可以灵活的调整各种进程被服务的机会

针对此我们引?了?种 多级反馈队列算法

多级反馈队列算法

算法思想 对其他调度算法的折中权衡算法规则

1. 设置多级就绪队列，各级队列优先级从?到低，时间?从?到?
2. 新进程到达时先进?第?级队列，按照先到先服务原则排队等待被分配时间?，若时间??完进程还未结束，则进程进?下?级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
3. 只有K级队列为空时，才会为k+1级队列的队头进程分配时间?

?于作业/进程调度 ?于进程调度

是否可抢占 抢占式的算法。在k级队列的进程运?过程中，若更上级的队列（1~`k-1 级）中进?了?个新进程，则优于新进程处于优先级更?的队列中，因此新进程会抢占处理机，原来运?的进程放回K级队列队尾

优缺点 优点：对于各种类型的进程相对公平；每个新到达的进程都可以很快就得到响应；短进程只?较少的时间就可完成；不必实现估计进程的运?时间（避免?户作假）；可灵活的调整对各类进程的偏好程度，?如CPU密集型进程、I∕O密集型进程

（因为将因I/O?阻塞的进程重新放回原队列，这样I/O进程就了?保持较?优先级）是否会导致饥饿 会 被降为低级优先级的进程可能?时间得不到服务。

例题

只有K级队列为空时，才会为K+1级队头的进程分配时间?最后?级 被抢占处理机的进程重新放回原队列的队尾第?节?节

第??节 进程同步 进程互斥

回顾 异步性的特征 异步性是指，各并发执?的进程以各?独?的，不可预知的速度向前推进。

进程通信—管道通信

需要先写数据到管道然后在读数据

概念引?

进程同步

读进程和写进程并发的执?，优于并发必然导致异步性，因此写数据和读数据两个操作的先后顺序是不确定的。?实际应?中?必须按照“写数据-读数据”的顺序来执?的。

如何解决这种异步问题就是“进程同步”所讨论的内容

同步亦称直接制约关系，他是指为完成某种任务?建?的两个或多个进程，这些进程因为需要在某些位置上协调他们的?作次序?产?的制约关系，进程间的直接制约关系就是源于他们之间的相互合作进程互斥

进程的“并发”需要“共享”的?持，各个并发执?的进程不可避免的需要共享?些系统资源（?如内存，??如打印机、摄像?这样的I/O设备）两种资源共享?式

互斥共享?式 — 系统中的某些资源（临界资源），虽然可以提供给多个进程使

?，但是?个时间段只允许?个进程访问该资源

（临界资源）：?个时间段只允许?个进程使?的资源，?如许多物理设备，还有很多变量 数据 内存缓冲区等都属于临界资源，必须互斥地访问，只有?个进程访问完成然后释放资源后其他进程才能去访问

临界区是进程中访问临界资源的代码段

进?区和退出区是负责实现互斥的代码段临界区也可称为”临界段“

思考

进程互斥访问需要遵循以上四个原则 在后期会详细学到

同时共享?式 — 系统中的某些资源，允许?个好似简短内?多个进程”同时“对他们进?访问。第??节?结

第??节 进程互斥地软件实现?法

知识总览

1.本节需要学习各个算法的思想 原理

2.接合上节学习的”实现互斥的四个逻辑分区“ 重点理解各算法理解各种算法在进?区、退出区都做了什么

3.分析各算法存在的缺陷如果不存在互斥

单标志法

算法思想：两个进程诶那各在访问完临界资源后会把使?临界区的权限转交给另?个进程。也就是说每个进程进?临界区的权限只能被另?个进程赋予。

这?段刚开始还没看明?；这段的意思是因为turn的初值是0，所以允许P0

进程上处理机操作，但是是P1现在处理机只能等待P1进程的时间?先消耗完调度到

P0上处理机

xdm我感觉这?段没看明? 因为turn的初值是0 然后如果P1进程先执?括号内（0！

=1）是成?的 所以他的值就是1吧，然后P1进程就能执?吧要是?家看明?这块还?烦跟我说?声反正以上算法可以实现”同?时刻最多只允许?个进程访问临界区“ 就是他的解释这点没?理解协助理解的例?

因为只能按照P0-P1-P0-P1循环这样轮流访问，带来的问题是如果P1此刻允许进?临界资源区?P1?直不访问这时候turn的值?法改变P0也?法去访问该临界资源，所以为翻了”空闲让进“原则

双标志先检查法

算法思想： 设置?个 布尔类型数组flag「」，数组中各个元素?来标记各进程进?临界区的意愿，?如”flag[0]=ture“意味着0号进程P0现在想要进?临界区，每个进程在进

?临界区之前先检查当前有没有别的进程想进?临界区，如果没有，则把??对应的标志flag［i］设置为ture，之后开始访问临界区

例?

如果在P0进程刚执?完判断还没有对true的值进?修改时发?了进程切换P1判断并上锁就会发?很尴尬的事情 P1访问临界资源后切换会P0进程继续也去把flag的值设为 true访问临界资源

所以按照152637的顺序进?执?的时候，P0和P1将会同时访问临界区。

因此，双标志先检查法的主要问题是违反了”忙则等待“原则。

原因在于，进?区的”检查“和”上锁“两个处理不是??呵成的，检查后上锁前可能发?进程切换

双标志后检查法算法思想 先上锁后检查 其余与先检查法

虽然解决了忙则等待的问题但是?违背了”空闲让进“和”有限等待“原则，会因各进程都

?期?法访问临界资源?产?”饥饿“现象

pererson算法（?特森算法）

算法思想 ：结合双标志法 单标志法的思想，如果双?都整着想要进?临界区，可以让进程尝试”孔融让梨“（谦让）。

?特森算法看似复杂其实在进?区就?了

主动争取 主动谦让 检查对?是否也想使?，且最后?次是不是??谦让了

如果上?次是对?谦让则??进?临界区（谁在最后进?了谦让，谁就失去了?动的优先权）

?特森算法?软件的?法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然为遵循让权等待的原则。

第??节?节

第?三节 进程互斥地硬件实现?法

知识总览

中断屏蔽?法

前边在学习原语的不可被打断中可以引导此种?法

利?“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为?都不允许被中断，也就不能发?进程切换，因此也不可能发?两个同时访问临界区的情况）

。。。

关中断———关中断后即不允许当前进程被中断，也必然不会发?进程切换临界区

开中断———-直到当前进程访问完临界区，再执?开中断指令，才有可能有别的进程上处理机并访问临界资源

。。。

优点：简单?效

缺点：不是?于多处理机；只适?于操作系统内核程序，不适?于?户进程（因为开关中断指令只能运?在内核态，这组指令如果让?户随意使?会很危险）

TestAndSet指令由硬件完成

swap指令

第?三节?结

第?四节 信号量机制

知识总览

?户进程可以通过操作系统的?堆原语来对信号量进?操作，从?很?便的

信号量其实就是?个变量（可以是?个整数，也可以是更复杂的记录型变量）可以?

?个信号量来表?系统中某种资源的数量，?如：系统中只有?台打印机就可以设置

?个初值为1的信号量

原语是?种特殊的程序段，其执?只能?起呵成，不可被中断。原语是由关中断开中断指令实现的。软件解决?案的主要问题是有“进?区的各种操作?法?起呵成”，因此如果能把进?区、退出区的操作都?原语实现，使这些操作都能“??呵成”就能避免这些问题。

wait（P）和signal（V）

简写记忆为PV操作

整形信号量

??个整数型的变量作为信号量，?来表?系统中某种资源的数量

与普通的整形变量不同之处在于 对信号量的操作只有三种即 初始化 P操作 V操作

Eg：计算机系统中有?台打印机

代码的部分说明

在第?个图中 while(s≤0);结束是分号 s的初始值是1所也不满?循环条件直接执?s=s-1；若是资源被占?

S的值=0则?直重复while循环直到时间??完发?进程调度改变s的值。

记录型信号量

整形信号量的缺陷是存在“忙等”问题，因此?们?提出了“记录型信号量”即?记录型数据结构表?的信号量

Eg:

每有?个进程申请打印机进程就会使value的值减?，P0，P1进程使value值由2到1到 0，P2再进?申请时会使value的值变为-1，这时候P2进程会主动把??阻塞放?打印机的等待队列中。

P3进?申请时会使value值变为-2然后也会主动进?阻塞队列。每个进程在调?完后都会对value的值进?加?，如果?于0的话说明仍然有进程还在等待队列 进程在使?完成后会使??个wake up原语唤醒处于等待队列的进程

第?四节?结

第?五节 ?信号量实现进程互斥、同步、前驱关系

知识总览

?个信号量对应?种资源

信号量的值=这种资源的剩余数量（信号量的值如果?于0，说明此时有进程正在等待这种资源）

P(s)—申请?个资源s，如果资源补够就阻塞等待

V(s)—释放?个资源s，如果有进程在等待该资源，则唤醒进程信号量机制实现进程互斥

分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就放在临界区）

设置互斥信号mutex，初始值为1 进?区P（mutex）申请资源退出区v（mutex）释放资源代码

semaphore mutex=1声明记录型信号量

注意对于不同的临界资源要设置不同的互斥信号量

每?个进程进?临界区都需要对mutex进?p操作 处临机区都要进?v操作—可以认为 mutex表?进?临界区的名额 初始值为1表??有?个名额进?临界区

信号量机制实现进程同步

进程同步：要让各并发进程按要求有序的推进

设置?个初始信号量s为0

如果P1先上处理机运?则执?完代码2后才会对s进?v操作使s的值加?这时候执?P2代码4之前的P操作就能得到资源继续执?

如果P2先上处理机运?，?先对s进?P操作发现s的值是0知识后P2进程就会发?阻塞，发?进程调度执?P1进程释放?个s资源然后唤醒进程P2就可以?直保证代码2是在代码4之前执?的了。

注意

在前操作之后执?V（s）在后操作之前执?P（s） 前V后P

信号量机制实现前驱关系这?块跟数据结构上的?样

第?五节?结

第?六节 ?产者消费者问题

问题描述：有?产者 有消费者 有容量有限的仓库 仓库满了不能存，仓库没有不能取我们需要设置的变量有

semaphore mutex = 1； //互斥信号量，实现对缓冲区的互斥访问 semaphore empty = n； //同步信号量，表?空闲缓冲区的数量 semaphore full = 0； //同步信号量，表?产品的数量，也即?空缓冲区的数量如何实现

思考是否能改变相邻pv操作顺序

第?六节?结