康振华制作 1
处理机一直是决定计算机系统性能的最重要的硬件资源之一。多道程序系统中处理机管理的主要任务就是如何安排多任务使用处理机，即如何把处理机分配给多任务用，
因此处理机调度算法是这一部分的主要内容。但由于多数现代操作系统的设计都是基于进程的概念，处理机的分配对象也大都是进程，所以本章先介绍进程管理，再介绍处理机调度。
康振华制作 2
[考核目的 ]：
考核学员对进程概念、状态、组成，以及进程间同步机制的掌握情况。
[考核的知识点 ]：
程序的顺序执行与并发执行，多道程序设计的优点及带来的问题
进程的定义，进程的基本特征，进程控制块，程序与进程的对比
进程的描述：进程的基本状态及转换（就绪、运行、阻塞）
进程通信：同步与互斥、临界区和临界资源、原语、信号量及 P,V操作、消息缓冲
进程管理的基本命令
[考核要求 ]：
掌握：多道程序设计概念，进程定义,PCB，临界区概念，进程的状态及其变化，进程的同步与互斥。
理解：进程的组成，进程管理的基本命令，信号量和 P,V操作及其应用。
了解：进程高级通信原语。
康振华制作 3
2.1 多道程序设计
多道程序设计是指允许多道程序同时进入内存，并允许它们共享资源、
并发执行的程序设计技术。
采用这一技术的系统叫多道程序系统。
多道程序设计技术根本性地推进了操作系统技术发展。是现代操作系统所采用的最基本、最重要的技术，但它也带来一些单道程序系统中没有的新问题，这些多道程序设计中的新问题可以概括为进程间的互斥与同步，另外，对系统各类资源的管理也都复杂了。对这些问题的解决导致多道程序设计的实现代价比单道程序设计高，也使得现代操作系统变得日益复杂、庞大和精巧。
康振华制作 4
一,顺序程序的执行
单道系统中，程序是顺序执行的，即程序在执行时，必须按照某种先后次序进行，仅当前一操作执行完后，才能执行其后续操作。因此在某一时刻，系统的各个部分中只有一部分在工作。
I1 C1 P2P1 I2 C2
程序的顺序执行康振华制作 5
如对于以下三条语句的程序段：
P1,a=x+y
P2,b=a+1
P3,c=b-6
其中的语句 P2必须在 a被赋值后才能执行。
同样,P3也只能在 b被赋值后才能执行。
康振华制作 6
二、程序顺序执行时的特征
1.顺序性处理机的操作，严格按照程序所规定的顺序执行。
2.封闭性程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有本程序才能改变它。程序一旦运行，执行结果不受外界因素的影响。
3.可再现性只要程序执行时的环境和初始条件相同，当程序多次重复执行，
不论是,走走停停,还是,不停顿,,都获得相同的结果。
康振华制作 7
I1 I2 I3 I4
C1 C2 C4C3
P1 P2 P3 P4
三、程序并发执行康振华制作 8
四、并发程序执行的条件
1,定义
程序 Pi在执行期间所需引用的诸变量 ai的集合,
称为 Pi的 读集,记作 R(Pi)={a1,a2,a3,…,am}。
程序 Pi在执行期间所需改变的诸变量 bj的集合，
称为 Pi的 写集,记作 W(Pi)={b1,b2,b3,…,bm} 。
康振华制作 9
写出下列 4条语句的读集、写集。
语句 读集 写集
P1:a=x+y R(P1)={x,y} W(P1)={a}
P2:b=z+1 R(P2)={z} W(P2)={b}
P3:c=a+b R(P3)={a,b} W(P3)={c}
P4:d=c-2 R(P4)={c} W(P4)={d}
康振华制作 10
2．定理
如果两个程序 P1和 P2满足下述条件,它们便能并发执行,
否则不能 。
R(P1)∩ W(P2)∪ R(P1)∩ W(P2)∪ W(P2)∩ W(P2)={}
即当两个程序的读集与写集的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。该定理是程序并发执行的条件，是 Bernstein在 1966年提出的，故称
Bernstein条件。
康振华制作 11
p1
p2
p3 p4
画出这四条语句的前趋图,
程序并发执行时的特征：
间断性程序在并发执行时，由于共享资源，或者为完成同一任务而相互合作，致使在并发程序间形成了相互制约的关系。
失去封闭性程序在并发执行时，是多个程序共享系统中的各种资源，所以这些资源的状态可以由多个程序来改变，，使其失去了封闭性。
不可再现性程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。
康振华制作 13
例如：有两个循环程序 A和 B,A每执行一次时，都要作 m
＝ m＋ 1操作。 B每执行一次时，先执行 print(m)操作，
然后再将 m置成,0”。 A和 B以不同速度运行，可能出现以下三种情况（假定某时刻变量 m的值为 m）：
m=m+1 在 print(m)和 m＝ 0之前。此时得到的 m值分别为 m+1,m+1,0
m=m+1 在 print(m)和 m＝ 0之后。此时得到的 m值分别为 m,0,1
m=m+1 在 print(m)和 m＝ 0之间。此时得到的 m值分别为 m,m+1,0
康振华制作 14
2.2 进程的描述
程序并发执行时，产生了一些新特征，所以一般的程序是不能并发执行的。为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以控制和描述，引入“进程”的概念。
现在,,进程,已经成为操作系统乃至并发程序设计中最核心的概念，它是对正在运行的程序的抽象，操作系统的其他所有内容都是围绕着进程展开的。掌握进程的概念对于理解操作系统的实质以及分析、设计操作系统都有非常重要的意义康振华制作 15
一,进程的定义
,进程,这一术语，在 60年代初期，首先在美国 MIT的 MULTICS系统和 IBM公司的 CTSS/360系统中引入。其中能反映进程实质的定义有：
（ 1）进程是程序的一次执行。
（ 2） 进程是可以和其他计算并发执行的计算 。
（ 3） 进程是一个程序及其数据在处理机上顺序执行时发生的活动 。
（ 4） 进程是程序在一个数据集合上的运行过程,是系统进行资源分配和调度的一个独立单位 。
（ 5）进程是进程实体的一次活动。
康振华制作 16
我国 1978年在庐山召开的全国 OS研讨会上将
,进程,定义为：
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。
一个程序为实现不同的任务可以同时有多次运行活动，每个运行活动分别作为不同的进程康振华制作 17
二,进程的特性及与程序的区别
1.进程的五个特性
(1) 动态性,生命周期。 即它由系统,创建,而诞生，因被,调度,
而执行，因得不到资源而暂停，最后因被,撤消,而消亡。
(2)并发性,是指不同进程的动作在时间上可以重叠，即系统内的多个进程是可以并发执行的。
(3)独立性,指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位 。
(4)异步性,指进程按各自独立的、不可预知的速度向前推进
(5)结构特性,从结构上看，每个进程都由程序段、数据段和一个
PCB三部分组成。
2.进程与程序的区别
(1)从定义上看,进程是程序处理数据的过程,而程序是一组指令的有序集合；
(2)进程具有动态性,并发性,独立性和异步性等,
而程序不具有这些特性；
(3)从进程结构特性上看,它包含程序 （ 以及数据和 PCB） ；
(4)进程和程序并非一一对应。
康振华制作 19
在操作系统中引入,进程,概念的主要目的是（ ）。
A．改善用户编程环境
B,描述程序动态执行过程的性质
C,使程序与计算过程一一对应
D,提高程序的运行速度康振华制作 20
三,进程的基本状态及其转换
1．进程的三种基本状态
（ 1）就绪（ Ready）状态,当进程已分配到除 CPU以外的所有必要的资源，只要能再获得处理机，便可立即执行
（ 2）执行（ Running）状态,当进程已获得处理机，其程序正在处理机上执行，
（ 3）阻塞（ Blocked）状态,正在执行的进程，由于等待某事件发生而无法执行时，便放弃处理机而处于暂停状态。
在不少系统中,又增加了两种基本状态：
①新状态 ②终止（ Terminated）状态康振华制作 21
引入新状态和终止状态的原因：
由于 OS在建立一个新进程时，通常分为 2步：第一步是为新登录的用户程序（分时系统）创建进程，并为他分配资源，此时进程即处于新状态。第二步是把新创建的进程送入就绪队列，一旦进程进入就绪队列，它便由新状态变为就绪状态。
一个结束了的进程，其退出系统的过程也分为两步：第一步是将该进程从就绪队列中移出，使之成为一个不可能再运行的进程，相应的进程处于终止状态。此时系统并不立即撤销它，而是将它暂时留在系统中，以便其它进程去收集该进程的有关信息。
康振华制作 22
新进程就绪 执行结 束阻塞接纳完成
I/O完成或等待的事件发生
I/O请求或等待某事件
2．进程三种基本状态间的转换调度时间片用完康振华制作 23
其他的状态
例如，在有的系统中，为了暂时缓和内存的紧张状态，
或为了调节系统负荷，又引入了挂起功能。即暂时挂起一部分进程，把它们从内存临时换出到外存，使它们暂时和系统脱离联系。这样，就需要把进程的就绪状态进一步细分为 活动就绪状态 （未被挂起的就绪进程）和 静止就绪状态 （被挂起的就绪进程）两种。把进程的阻塞状态也细分为 活动阻塞状态 （未被挂起的阻塞进程）和 静止阻塞状态 （被挂起的阻塞进程）
康振华制作 24
问题：
1.在进程状态转换时,下列哪一种状态转换是不可能发生的？
A)就绪态 → 运行态 B)运行态 → 就绪态
C)运行态 → 等待态 D)阻塞态 → 运行态
2．某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将（ ）。
A.从就绪变为运行 B.从运行变为就绪
C.从运行变为阻塞 D.从阻塞变为就绪康振华制作 25
四,进程控制块 ——PCB
(Process Control Block)
PCB是系统为了描述和控制进程的运行而为进程定义的一种数据结构,
它是进程实体的一部分,是进程存在的唯一标志,也是操作系统中最重要的结构体类型的数据结构 。
PCB中存放着操作系统所需的用于描述进程的当前情况以及控制进程运行的全部信息 。
康振华制作 26
1,PCB的作用
（ 1） 标识进程的存在,系统创建进程时，就为之创建一个 PCB；
进程结束时，系统又回收其 PCB，进程便随之消亡 。
（ 2） 为系统提供可并发执行的独立单位,PCB使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。没有为之建立 PCB的程序是不能并发执行的。
（ 3） 为系统控制和管理进程提供所需的一切信息 。
康振华制作 27
2,PCB中的信息
（ 1） 进程标识符：
（ 2） 进程的现行状态,
（ 3） 处理机的现场保留区,
（ 4） 进程相应的程序和数据地址,
（ 5） 进程资源清单,
（ 6）进程优先级,
（ 7） 进程同步与通信机制：
（ 8） 进程所在 PCB的链接字,
（ 9） 与进程有关的其他信息：
康振华制作 28
五,进程的队列所谓 进程队列 指的是把具有相同状态的进程按照某种原则链接在一起组成的队列，它其实是 PCB的一种组织形式，有时也称 PCB链因为 PCB是系统中最重要也是被频繁访问的数据结构，系统中的许多模块，如调度程序、资源分配程序、中断处理程序以及监督和分析程序等，特别是运行频率很高的进程分派程序，都要对它进行读或写操作，所以 PCB常驻内存的系统区中，系统将所有的
PCB以数组形式连续存放组织成若干个链表（或队列），存放在操作系统中专门开辟的 PCB区内。
康振华制作 29
空闲 PCB队列头指针阻塞进程队列头指针就绪进程队列头指针执行进程指针 PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCB8
PCB9
4
3
0
8
7
9
0
15…
.
康振华制作 30
一、进程控制机构
1．操作系统的内核通常将一些与硬件密切相关的模块，例如，中断处理程序、各种常用设备的驱动程序，以及运行频率较高的模块等安排在紧靠硬件的软件层中，并将它们常驻内存，以提高操作系统运行效率，并对它们加以特殊的保护。上述这一部分程序称为操作系统内核。
操作系统的内核是计算机硬件扩充的第一层软件，是在核心态运行的操作系统程序。
2.3 进程的控制康振华制作 31
2．内核中与进程控制有关的机构
（ 1）原语操作：
原语 本身是由若干条指令构成、用于完成特定功能的一个过程。
原子操作,一个操作中的所有动作，与一般过程的区别：
要么全作，要么全不作。
即：原子操作是不可分割的，它是机器指令的延伸。
康振华制作 32
现代操作系统常采用屏蔽中断的方法来保证原语在执行时的不可分割性，这种 原子性 对于解决进程同步互斥问题是非常重要的。在内核中可能有许多原语，常见的内核原语有进程控制原语、用于链表操作的原语和用于控制进程互斥、同步的原语等。
康振华制作 33
（ 2）进程管理：
进程管理的全部或大部分功能都在内核中,这主要是因为这些功能模块的运行频率较高,例如,进程调度与分派,进程的创建,进程的撤消等,或是因为它们为多种功能模块所调用,例如,实现进程的同步和进程通信的原语等 。 此外,内核中的进程管理,还需要管理好进程控制块 PCB.
康振华制作 34
A
B C
GFE HD
I J K L M
二,进程的控制原语进程树祖先
进程控制原语是对进程生命期控制和实现进程状态转换的原语。
康振华制作 35
1.进程创建原语 Creat()
引起创建进程的事件：
用户登录
作业调度
提供服务
应用请求
进程创建的主要步骤：
申请空白 PCB
为新进程分配资源
初始化 PCB的内容
将新进程插入就绪队列康振华制作 36
2.进程撤销原语 Tenminat()
引起创建进程的事件：
正常结束
异常结束
外界干扰
进程撤销的过程：
检索进程当前的状态，结束并置调度标志，撤销其所有的子进程，归还资源，
移出队列
应由父进程调用进程撤销原语来撤销，以便及时的释放其所占的资源康振华制作 37
3.进程阻塞原语 Block()
引起进程阻塞的事件：
请求系统服务
启动某种操作
新数据尚未到达
无新工作可作
进程堵塞的过程：
发现堵塞事件，调用阻塞原语把自己阻塞，停止进程的执行，修改 PCB的 状态信息,将其插入到自己的堵塞队列。最后转调度程序，将处理机分配给另一个就绪进程 。进程的阻塞是进程自身的一种主动行为康振华制作 38
4.进程唤醒原语 Wakeup()
引起进程唤醒的事件：
当被阻塞进程所期待的事件出现时，或者所期待的数据已经到达。由该有关进程调用进程唤醒原语，
将等待该资源而阻塞的一个进程唤醒成 ……
进程唤醒的过程：
把被阻塞进程从等待该事件的阻塞队列中移出，
将其 PCB的现行状态，
由阻塞改为就绪，再将该进程插入到 PCB就绪队列中。
康振华制作 39
5.挂起原语 Suspend( ):
当出现了引起挂起的事件时，如为了暂时缓和内存的紧张状态，用户进程请求将自己挂起或者当父进程请求将自己的某个子进程挂起时，系统将利用挂起原语 suspend()将制定的进程或处于阻塞状态的进程挂起。
6.激活原语 Active( ):
将进程从外存调入内存，检查该进程的状态，改为相应的活动状态康振华制作 40
2.4 进程的互斥
—— 你要，我也要
多道程序设计带来的问题,
并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。
为此,现代操作系统都在内核中设有进程的互斥同步机制，以控制并发执行的诸进程能有效的共享资源和相互合作，同时使并发程序的执行仍具有可再现性。
康振华制作 41
一,互斥的定义
所谓 进程互斥,指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用 。
进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称 间接制约关系,主要是由被共享资源的使用性质所决定的。
康振华制作 42
这种限定进程只能互斥地访问它的资源叫 临界资源（ 指一次仅允许一个进程使用的资源 ） 。
临界资源限定了使用者只能互斥地使用它。
操作系统也不能中途从抢先者手中把临界资源抢来给其他进程用。
因此，临界资源也是不可剥夺性资源。 例：打印机、共享变量 等。
计算机系统中可剥夺性使用的资源主要有 CPU,内存 和 磁盘 等。
康振华制作 43
程序 段 1 程序 段 2 程序 段 n
共 享 变量康振华制作 44
临界区,进程中访问临界资源的那段程序代码称为临界区或临界段。
使用同一临界资源的不同进程中的临界区称为 同类临界区 或 相关临界区 。
为实现对临界资源的互斥访问，应保证诸进程 互斥 地进入各自的临界区。
但无论采用何种方法，都应 遵循临界区的使用原则,即
,空则让进，忙则等待，等则有限，等则让权,。
康振华制作 45
二,上锁和开锁原语
现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、
管程机制等。
上锁与开锁是一种最简单的进程互斥方法，它使用一个锁变量 W来表示某种临界资源的状态，
W=0表示 资源空闲可用
W=1表示 资源正被使用康振华制作 46
1．上锁原语,LOCK（ W）
L1：如果 W=1那么转向 L1;
否则 W=1
返回
void lock(锁变量 w) {
test,if (w 为 1)
goto test
else
w=1; /*上锁 */
} /* lock(w) */
1.考察锁位的值；
2.如果原来的值为 0，将锁位置 1；
3.如果为 1，则返回第一步再次考察康振华制作 47
2．开锁原语,UNLOCK（ W）
W=0;
返回
void unlock(锁变量
w) {
w=0; /* 开锁 */
} /* unlock(w) */
当进程使用完资源后，它必须将锁位置成,0”，称为开锁操作。
康振华制作 48
三、用上锁和开锁原语可以解决并发进程的互斥
任何欲进入临界区的进程，必须先执行上锁原语。若 上锁原语 顺利通过，则进程可 进入临界区 ；当完成对临界区资源的访问后再执行 开锁原语,以释放该临界资源。
即 在相关进程的程序里由上锁和开锁原语紧夹着临界区,
就能保证这些进程互斥地进入各自的临界区。
康振华制作 49
例如，甲、乙两进程要访问同一类临界资源
甲进程：
其他代码；
LOCK（ W）；
甲进程的临界区；
UNLOCK（ W）；
其他代码；
乙进程,
其他代码；
LOCK（ W）；
乙进程的临界区；
UNLOCK（ W）；
其他代码；
用上锁 用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起 CPU“忙等,。
康振华制作 50
2.5 信号量机制
荷兰著名科学家，后来的计算机图灵奖获得者，
E.W.Dijkstra于 1965年提出了用作进程同步工具的 信号量 （ semaphore） 机制,这是一种卓有成效的进程互斥同步工具，已被广泛应用于现代计算机系统中。
康振华制作 51
信号量机制的基本原理是：
两个或多个进程可以利用彼此间收发的简单的信号来实现,正确的,并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。
经典的整型信号量＝,经记录型信号量＝,信号量集机制
CPU忙等造成死锁 不易死锁，可能导致资源利用率低康振华制作 52
一,信号量的概念
信号量,也叫 信号灯,一般是由两个成员组成的数据结构，是一个确定的二元组 （ S,Q）
S是个具有非负初值的 整型变量,表示该信号量的值，且 S的值只能由定义在信号量上的 P操作原语和 V操作原语来改变；
Q是个初始状态为 空的 队列 。
康振华制作 53
另一定义：
信号量类型是个复合类型，其一个分量是个整型分量 S，另一个分量是个等待队列指针 Q （一个是指向 PCB的指针，
当多个进程都等待同一信号量时，它们就排成一个队列，
由信号量的指针项指出该队列的头。）
信号量通常可以简单反映出相应资源的使用情况，它与 P，
V操作原语一起使用可实现进程的同步和互斥。
康振华制作 54
**信号量的整型分量 S的值的物理含义：
当 S≥ 0时，表示某类可用资源的数目，或者说表示可以执行 P操作而不会被阻塞的进程的数目；
当 S＜ 0时，其绝对值表示信号量 S的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，
亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。
另外,S的值只能由 P,V操作来改变。
康振华制作 55
二,P,V操作原语
P代表荷兰语的 proberen，意为,测试,；
V代表荷兰语的 verhogen，意为,增加,。
现在很多国外的文献都使用 wait和 signal操作（或者 down和 up操作）代替 P,V操作。
康振华制作 56
1．定义在信号量 S上的 P（ S）原语操作的算法描述为：
（ 1） S减 1；
（ 2） 若 S≥ 0,则调用 P（ S） 的进程返回,继续执行；
（ 3） 若 S<0，调用者进程调用阻塞原语 Block
（ Q），把自己插入到信号量 S的阻塞队列 Q
中 (把相应的 PCB连入该信号量队列的末尾，并放弃处理机，进入等待 )。
康振华制作 57
2．定义在信号量 S上的 V（ S）原语操作的算法描述为：
（ 1） S加 1；
（ 2） 若 S>0,则调用 V（ S） 的进程继续执行,
返回；
（ 3）若 S<0,调用者进程调用唤醒原语 Wakeup（ Q）
把信号量 S的阻塞队列 Q中的队首进程移出并唤醒，返回。
康振华制作 58
P(s)入口
S-1=>S
S≥ 0
Block(Q)
返回Y
N
康振华制作 59
V(s)入口
S+1=>S
S>0
Wakeup(Q)
返回Y
N
康振华制作 60
注意 P（ S）操作和 V（ S）操作的物理含义：
P（ S）操作表示,等信号,,即测试一个要等的信号是否到达；
V（ S）操作表示,发信号,。这个信号在实现同步时就是,合作者的伙伴进程已完成前趋任务,,在实现互斥时就是,临界资源可用,。
另外，在互斥问题中，每执行一次 P（ S）操作的含义，
也可理解为进程请求一个单位的 S类资源；每执行一次
V（ S）操作的含义，也可理解为进程释放一个单位的 S
类资源。
康振华制作 61
三,用 P,V操作原语实现进程的互斥
用 P,V操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以 P操作和 V操作即可，即在相关进程的程序里由 P操作和 V操作原语紧夹着临界区，
就能保证这些进程互斥地进入各自的临界区。
这里所用信号量的初值一般为 1，表示临界资源未被占用，
且其可用数目为 1。
用 P,V操作原语实现进程互斥的效率更高一些，因为 P操作中引入了阻塞机制，所以消除了 CPU忙等现象。
康振华制作 62
P(S)
V(S)
P(S)
V(S)
P(S)
V(S)
P1 P2 P3
互斥区康振华制作 63
一个简化的异地售票程序，假设几乎同时两地有两个乘客要购买同一班次的车票各一张
两个终端售票程序都要访问存放该次车票的数据单元 Pk
假设它们都要对 Pk做如下的访问操作
,若 Pk≥1,则将 Pk的值减 1，卖出一张票，返回
否则打印‘无票’信息，返回”
如果不加任何限制让这两个程序并发执行的话,结果可能会导致错误，甚至两地各卖出一张重票的现象康振华制作 64
例 2.1 试用 P,V操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。
主要步骤是：
（ 1）分析清楚题目涉及的进程间的制约关系。
（ 2）设置信号量（包括信号量的个数和初值，
对于同步问题还要写出信号量的物理含义）。
（ 3）给出进程相应程序的算法描述或流程控制，并把 P,V操作加到程序的适当处。
康振华制作 65
北京售票终端进程：
① 根据顾客订票要求找到公共数据单元 PK；
② P（ S）；
③把 PK的值读到工作寄存器 R1中；
④根据顾客订票数修改 R1；
⑤将 R1的值回写到 PK中；
⑥ V（ S）；
⑦售出顾客所订的票，返回；
康振华制作 66
天津售票终端进程：
① 根据顾客订票要求找到公共数据单元 PK；
② P（ S） ；
③ 把 PK的值读到工作寄存器 R2中；
④ 根据顾客订票数修改 R2；
⑤ 将 R1的值回写到 PK中；
⑥ V（ S） ；
⑦ 售出顾客所订的票,返回 ；
康振华制作 67
2.6进程的同步 (synchronism)：
——你等我，我也等你
多道程序系统中，许多进程之间可能存在以下两种制约关系：
1.源于 资源共享的 直接制约关系 （互斥）
2.源于 合作相互的 间接制约关系 （同步）
后者即一种合作进程在独自并发执行过程中的某些确定的时序点上,你等我，我也等你,的同步约束，前者可视为后者的特例（前面已经介绍）。
康振华制作 68
1.资源共享关系很多进程之间彼此无关,它们并不知道其它进程的存在 。
例如在分时系统中,系统分别为每个用户 （ 终端 ） 建立一个进程 。 但这些进程既然同处于一个系统中,也就必然存在着资源共享的关系,如共享 CPU和 I/O设备等 。 此时,进程的主要任务,是保证各个进程能互斥地访问临界资源 。
所以,系统中的资源应该不允许用户进程直接使用,而应该由系统同一分配 。 例如：在仅有一台打印机的系统中,
两个进程提出打印请求
2.相互合作关系
例如输入进程、计算进程、打印进程合作完成一批数据的输入、计算和打印时的关系；中断响应过程；生活中下棋、
看病时等化验结果等等。
康振华制作 69
一,同步的定义进程同步,指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些个确定的时序点上必须相互协调，
即一个进程的执行依赖于另一个进程 ——其合作伙伴的消息，当一个进程到达了某一确定点而没有得到合作伙伴发来的“已完成某些操作”的消息时必须等待，直到该消息到达被唤醒后，才能继续向前推进。
进程同步是多道程序系统中进程之间存在的一种主要 源于进程间合作的 制约关系，也称 直接制约关系。
康振华制作 70
父子进程就是典型的合作进程,
它们之间的同步关系有时也被形象地称为,生产者与消费者” 之间的关系,“产品,（即生产者进程的输出，
亦即消费者进程的输入）是它们的纽带，它们在执行过程中的某个或某些确定的时序点上有着固定的前趋后继的同步约束，即先“生产”后“消费”，这是一种“你等我”
的关系。
而在稍微复杂一点的进程同步问题里，合作进程间的
“生产者与消费者”的关系或身份是可以经常转换的，因此，这些合作进程在执行过程中就会出现时而你等我，时而我等你的现象。
康振华制作 71
进程同步和互斥间的关系：
相似处,进程的互斥实际上是进程同步的一种特殊情况； 进程的互斥和同步统称为进程同步。
差别,进程互斥 是进程间共享资源的使用权,这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，
直到不需要使用时再归还；而 进程同步 则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。
康振华制作 72
P,V操作也都是配对出现,但对 同一个信号量 的 P,V操作却不是同时出现在每一个进程的程序里,而是分别出现在 一个进程和它的合作伙伴的代码中 。
而且 P,V操作的出现位置都在各个合作进程中确定的时序点,
即一个生产者进程在完成了前趋的生产任务后,应立即给合作伙伴 —
—消费者进程发送一条,已完成前趋生产任务,的消息,这要执行 V
操作；而后继的消费者进程在消费前,应该执行对同一个信号量的 P
操作,以测试其合作伙伴 ——生产者进程,已完成前趋生产任务,的消息是否到来,如果到来就开始消费,否则就阻塞自己 。
二、用 P,V操作原语实现进程的同步康振华制作 73
解答这类进程同步问题的主要步骤也是三大步：
(1)分析清楚题目涉及的进程间的制约关系
(2)设置信号量（包括信号量的个数和初值及其物理含义）,合作进程间需要收发几条消息相应就设置几个信号量。同步信号量的初值一般为 0，表示 ……
(3)给出进程相应程序的算法描述或流程控制，并把 P、
V操作加到程序的适当处。
康振华制作 74
＝,例 2.2 生产者 ——消费者问题公用缓冲池，有 n个缓冲区康振华制作 75
生产者－消费者问题是相互合作进程关系的一种抽象
输入 ——计算 ——打印生产者 消费者生产者 消费者系统中使用资源的进程 —— 消费者系统中释放同类资源的进程 —— 生产者康振华制作 76
问题分析：
① 生产者 —消费者之间的同步关系表现为,一旦缓冲池中所有缓冲区均装满产品时，生产者必须 等待消费者提供空缓冲区 ；一旦缓冲池中所有缓冲区全为空时，
消费者必须 等待生产者提供满缓冲区 。
② 生产者 —消费者之间还有互斥关系,由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。
康振华制作 77
问题解答：
① 所用信号量设置如下：
Ⅰ ） 同步信号量 empty,初值为 n,表示消费者已把缓冲池中全部产品取走,有 n个空缓冲区可用 。
Ⅱ ） 同步信号量 full,初值为 0,表示生产者尚未把产品放入缓冲池,有 0个满缓冲区可用 。
Ⅲ ） 互斥信号量 mutex，初值为 1，以保证同时只有一个进程能够进入临界区，访问缓冲池。
康振华制作 78
② 用信号量机制解决生产者 —消费者问题的算法描述如下：
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ empty）； P（ mutex）；
P（ mutex）； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex）； V（ empty）；
V（ full）； 消费该产品；
康振华制作 79
如果将生产者的两个 P操作对调？？
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ mutex） ； P（ mutex）；
P（ empty） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex） ； V（ empty）；
V（ full） ； 消费该产品；
康振华制作 80
如果将消费者的两个 P操作对调？？
生产者 i 消费者 j
生产出一产品； P（ mutex）；
P（ empty ） ； P（ full）；
P（ mutex ） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex ） ； V（ empty）；
V（ full ） ； 消费该产品；
康振华制作 81
如果将两个 V操作对调？？
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ mutex） ； P（ mutex）；
P（ empty） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ full） ； V（ empty）；
V（ mutex） ； 消费该产品；
康振华制作 82
＝,例 2.3 读者 ——写者问题
该问题描述的是：
一组读者与一组写者循环访问共享的同一个数据对象。
读者：指能对共享数据对象读的进程，写者：指对共享数据对象只要求写的进程。
规定：多个读者可以同时读这个数据对象，但 决不允许多个写者同时对这个数据对象进行 写 操作，也不允许读者、写者 同时 访问这个数据对象。
康振华制作 83
读者 —写者问题是共享数据对象的非合作进程关系的一种抽象
如文件管理模块中读文件、写文件等许多操作进程之间
异地售票程序也可看成是写者与写者的问题
读者 —写者问题是指保证一个写者进程必须与其他写者或读者进程互斥地访问一个共享数据对象的同步问题。
康振华制作 84
问题分析：
① 读 者 —写者之间的互斥关系：
写者与写者的互斥、写者与读者的互斥。设一个公用的初值为
1的互斥信号量 RW_mutex？但是实现了读者与读者的互斥。引入一个读者计数器变量 RC。
②读 者 —读者之间又有了互斥关系：
再设一个读者公用的初值为 1的互斥信号量 R_mutex
实现各个读者间互斥的访问 RC
康振华制作 85
问题解答：
① 所用信号量和其他变量设置如下：
Ⅰ ） 互斥 信号量 RW_mutex,初值为 1,用于实现写者与其他写者或读者互斥地访问共享的数据对象 。
Ⅱ ） 互斥 信号量 R_mutex,初值为 1,用于实现诸读者互斥地访问读者计 0数器变量 。
Ⅲ ）整型变 量 RC，初值为 0，用于对读者进行记数。
康振华制作 86
② 用信号量机制解决读者 —写者问题的算法描述如下：
读者 写者
P（ R_mutex） ； P（ RW_mutex） ；
若 RC=0则 P（ RW_mutex）； 对数据对象进行写操作；
RC加 1； （ RW_mutex） ；
V（ R_mutex） ；
读数据对象；
P（ R_mutex） ；
RC减 1；
若 RC=0则 V（ RW_mutex） ；
V（ R_mutex）；
康振华制作 87
＝,例 2.4 试用用信号量机制描述两人下象棋的过程。
两人下象棋的过程可以概括为：一开始只能是,红先黑后,,以后两人要循环轮流走子，直至某一方获胜或双方和棋为止。这是个只有一个生产者和一个消费者的生产者 ——消费者问题，是个典型的,你等我，我也等你,
的问题。红方是总的前趋任务 ——生产者进程，黑方是总的后继任务 ——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。
棋盘则是生产者与消费者共享的缓冲。
康振华制作 88
二人对弈过程是个纯粹的同步过程
解答：
① 所用信号量设置如下：
Ⅰ ） 同步信号量 hei,初值为 1,表示黑方已走子,开始时可使红方先行不受阻 。
Ⅱ ） 同步信号量 hong,初值为 0,表示红方尚未走子,
开始时可使黑方先行受阻 。
康振华制作 89
② 用信号量机制描述的二人下象棋过程如下：
P（ hei）； P（ hong）；
若被黑方将死，则投子认负，结束； 若被红方将死则投子认负，结束 ；
若同意与黑方作和，则结束； 若同意与红方作和，则结束；
否则，根据棋局思考后走一子 ； 否则，根据棋局思考后走一子；
V（ hong）； V（ hei）；
康振华制作 90
＝,例 2.5 某小型超级市场，可容纳 50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和 P,V操作写出购物者的同步算法。
这是个典型的进程互斥问题康振华制作 91
解答,
① 所用信号量设置如下：
Ⅰ ） 互斥信号量 S,初值为 50,用以保证最多可以有 50个购物者同时进入超市 。
Ⅱ ） 互斥信号量 mutex,初值为 1,用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子 。
②用信号量机制给出的每个购物者购物过程的算法描述如下：
康振华制作 92
购物者 i进程（解法一） 购物者 i进程（解法二）：
P（ S） ； P（ S） ；
P（ mutex） ； P（ mutex1） ；
从入口处进超市,并取一只篮子； 同左；
V（ mutex） ； V（ mutex1） ；
进超市内选购商品； 同左 ；
P（ mutex） ； P（ mutex2） ；
到出口结帐,并归还篮子； 同左 ；
V（ mutex） ； V（ mutex2） ；
从出口离开超市； 同左 ；
V（ S） ； V（ S） ；
↓ ↓
结 束,结 束,
康振华制作 93
＝,例 2.6 桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和 P,V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。
本题属于生产者 ——消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。
康振华制作 94
解答：①所用信号量设置如下：
Ⅰ ） 同步信号量 empty,初值为 1,表示盘子是空的,即儿子或女儿已把盘中的水果取走 。
Ⅱ ） 同步信号量 orange,初值为 0,表示爸爸尚未把桔子放入盘中 。
Ⅲ ）同步信号量 apple，初值为 0，表示爸爸尚未把苹果放入盘中。
康振华制作 95
② 使用信号量机制的三个进程的同步描述如下：
爸爸进程（ P）,儿子进程（ C1）,女儿进程（ C2）：
P（ empty）； P（ orange ）； P（ apple）；
将水果放入盘中； 从盘中取出桔子； 从盘中取出苹果；
若放入的是桔子,V（ empty）； V（ empty）；
则 V（ orange）； 吃桔子； 吃苹果；
否则,V（ apple） ；
康振华制作 96
＝,例 2.7 设 A,B两点之间是一段东西向的单行车道，
现在要设计一个 AB路段自动管理系统，管理规则如下：
当 AB间有车辆在行驶时同方向的车可以同时驶入 AB段，
但另一方向的车必须在 AB段外等待；当 AB段之间无车辆行驶时，到达 AB段的任一方向的车都可进入 AB段，
但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在 AB段行驶的车辆驶出了 AB段且暂无车辆进入 AB段时，应让另一方向等待的车辆进入 AB段行驶。试用信号量和 P,V操作管理 AB路段车辆的行驶。
康振华制作 97
解答：①所用信号量和其他变量设置如下：
Ⅰ ） 整型变量 Car_A,初值为 0，
用于对从 A点 （ 东 ） 驶入 AB段的车辆进行记数 。
Ⅱ ） 整型变量 Car_B,初值为 0，
用于对从 B点 （ 西 ） 驶入 AB段的车辆进行记数 。
Ⅲ ） 互斥信号量 mutex,初值为 1，
用于实现不同方向的第一辆车互斥驶入 AB路段 。
Ⅳ ） 互斥信号量 ma,初值为 1，
用于实现东西向的车互斥地访问计数器变量 Car_A。
Ⅴ ）互斥信号量 mb，初值为 1，
用于实现西东向的车互斥地访问计数器变量 Car_B。
康振华制作 98
通过 AB路段向西行驶的车辆 i 向东行驶的车辆 j
P（ ma） ； P（ mb） ；
若 Car_A=0则 P（ mutex）； 若 Car_B=0则 P（ mutex）；
Car_A加 1； Car_B加 1；
V（ ma） ； V（ mb） ；
车辆从 A点通过 AB路段到达 B点； 车辆从 B点通过 AB路段到达 A点；
P（ ma） ； P（ mb） ；
Car_A减 1； Car_B减 1；
Car_A=0则 V（ mutex）； Car_B=0则 V（ mutex）；
V（ ma）； V（ mb）；
康振华制作 99
总结上述几个有趣的实例的解题过程，可以得出这样的结论：
实现进程的同步互斥实际就是给进程的并发执行增加一定的限制，以保证被访问的共享数据的完整性和进程执行结果的可再现性。
康振华制作 100
用信号量机制解这类题的三个步骤：
（ 1）分析进程间的制约关系
（ 2）设置信号量
（ 3）实施 P,V操作。
第一步是基础、关键，第三步是核心。
掌握实现进程互斥与进程同步的第三步在形式上差异：即 P、
V操作总是 配对 出现的。
但 P,V在 互斥问题 中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在 同步问题 中，却是分别出现在两个合作进程的代码中，需要等消息的一方用 P操作，相应的对同一信号量的 V操作则在发出此消息的另一方中。
康振华制作 101
练习题：
1、有两个用户进程 A和 B，在运行过程中都要使用系统中的一台打印机输出计算结果。
试说明 A,B两进程之间存在什么样的制约关系？
为保证这两个进程能正确地打印出各自的结果，
请用信号量和 P,V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。
康振华制作 102
解,(1) A,B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
（ 2） mutex：用于互斥的信号量，初值为 1。
进程 A 进程 B
,.,…
,.,…
P(mutex) P(mutex)
申请打印机 申请打印机
使用打印机 使用打印机
V(mutex) V(mutex)
… …
康振华制作 103
2,有一个阅览室，共有 100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息,试问：
（ 1） 为描述读者的动作，应编写几个程序，设置几个进程？
（ 2） 试用 PV操作描述读者进程之间的同步关系。
康振华制作 104
分析：
读者的动作都是一样的：登记进入阅览室，阅读，撤消登记离开阅览室，因此 可写一个程序，设 n(n≥100)个进程 。
读者共享的资源有阅览室的座位和登记表，因此诸个读者进程之间有两种互斥制约关系,需设 2个信号量 来实现：
seat：用于实现诸读者对阅览室的空闲座位的互斥竞争，
初值为 100；
mutex：用于实现诸读者对登记表的互斥访问，初值为 1。
下面给出一种解法，当然还有其他解法（比如借鉴经典的读者写者问题的解法，利用读者计数器变量）。
康振华制作 105
解,(1)可写一个程序，设 n(n≥100)个进程
(2)读者进程 readeri(i=1,2,3,…… )描述如下：
P（ seat） ; /*申请空座位 */
P（ mutex） ; /*申请登记 */
登记；
V（ mutex） /*允许其他读者登记 */
阅读；
P（ mutex） ; /*申请撤消登记 */
撤消登记；
V（ mutex）； /*允许其他读者撤消登记 */
V（ seat）； /*释放座位，允许他人进入 */
康振华制作 106
§ 2.7进程通信 (communication)
进程之间的信息交换称为进程通信。
合作进程间所交换的信息量，少则是一个状态或数据，多则成千上万字节的。
按 通信所交换的数据量多少进程通信分为低级和高级两种方式。
康振华制作 107
低级通信,在进程间交换数据量少的进程通信方式。
一般只传送一个和几个字节的信息，达到控制进程执行速度的作用（例如进程的同步与互斥）。
信号量机制就是一种低级通信方式，它作为同步工具是卓有成效的，但作为通信工具则不够理想。（?传输效率低。通信对用户不透明）
高级通信,用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。 （?传输效率高。通信过程对用户是透明的）
康振华制作 108
目前，三种基本的进程通信方式：
根据通信实施的方式和数据存取的方式,分为：
=>共享存储器系统 包括 共享内存变量 （ 如信号量机制 ） 和 共享内存区 两种通信方式 。
=>消息传递系统 包括 消息缓冲 和 信箱 两种通信方式 。
=>管道通信方式康振华制作 109
2.7.2 发送和接收原语 ——实现进程通信的基本原语发送原语（ send（接收者进程名，发送区首地址） ）
接收原语（ receive（接收区首地址） ）
send：当要进行消息传递时执行 send
receive：当接收者要接收消息时执行 receive
这是系统提供给用户实现进程通信的最基本的原语，也是构成一种具体的通信系统的主要内容，用户直接使用这些通信原语一次就能发送成千上万字节的信息。
康振华制作 110
2.7.3 消息缓冲通信方式消息（ message）：在计算机网络中又叫报文，指进程之间相互传递的赖以发生相互作用的有结构的数据。
康振华制作 111
2.7.4 信箱通信方式
（只了解定义）
所谓信箱通信方式是指连接两进程之间的一个打开的共享文件,以文件作为缓冲传输介质,一个进程向其写入消息,另一个进程从中读取消息,好象是一个管道,
消息从一头流进,从另一头流出的通信方式 。
康振华制作 112
2.8 *死锁问题 *
——你不让，我也不让在多道程序系统中,多个进程并发运行,共享资源,
从而提高了资源的利用率 。 但是若对资源的管理和使用不当,在一定条件下会导致系统发生一种随机性故障 ―― 死锁 。 在一些系统中,比如实时控制系统,系统一旦发生死锁将导致灾难性的后果 。
死锁问题是 E.W.Dijkstra在 1965年研究银行家算法时首次提出的，以后又由 Havender,Lyach等人研究并发展。
康振华制作 113
2.8.1.死锁的定义
死锁（ Deadlock）,是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于 死锁状态 或 系统产生了死锁 。
称这些永远在互相等待的进程为 死锁进程 。
所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。
计算机系统中,如果系统的资源分配策略不当,或者更常见的是程序员写的程序有错误等,则会导致进程因竞争资源不当 （ 往往与进程的推进速度有关 ） 而产生死锁的现象 。
在计算机系统中有很多独占性的资源，在任一时刻，
它们都只能被一个进程使用。常见的有打印机、磁带驱动器等。例如：两个进程同时打印会引起打印混乱。
鉴于此，操作系统全都具有授权一进程（临时）独占地访问某一种资源的能力。
康振华制作 115
在很多情形中，需要一个进程独占地访问若干种资源而不是一种。
例如,将一个大文件由磁带拷贝至打印机，进程需要同时访问磁带驱动器和打印机，并且不允许其他进程这时访问它们。在只有一个进程的系统中，该进程可以要求任何它所需要的资源，然后进行工作。但是，在一个多道程序系统中，就有可能出现严重的问题。
康振华制作 116
A,B两个进程准备打印一个大的磁带文件
A
B
R1 R2打印机磁带机康振华制作 117
以哲学家就餐问题为例来说明一下死锁：
该问题的描述如下：有 5个哲学家，围坐在圆桌旁，
他们的生活方式是交替地进行思考和进餐；圆桌上间隔地摆放着 5把叉子和 5个装有通心粉的盘子，
规定第 i号哲学家固定坐在第 i把椅子上
（ i=0,1,2,3,4），且每个哲学家必须两手分别拿起他左右两旁的那两把叉子，才能吃通心粉；假定通心粉的数量足够 5个哲学家用的。
假设这 5把叉子与椅子相应也按逆时针方向从 0开始连续编号，即第 i号哲学家左边摆着第 i号叉子，右边摆着第 ((i+1)mod 5)号叉子，这里的
mod代表模运算，即整除取余。
显然，在这个问题中叉子是哲学家进餐竞争的临界资源,5把叉子应分别用一个初值为 1的信号量表示，这 5个信号量构成一个信号量数组 S.
则第 i号哲学家的进餐过程可以描述如下：
哲学家（ I＝ 0,1,2,3,4）
思考；
P(S[i]);
拿起左边的叉子；
P(S[i＋ 1]mod5)；
拿起右边的叉子；
吃通心粉；
放下左边的叉子；
V(S[I]);
放下右边的叉子；
V(S[i＋ 1]mod5)；
下面就是一个不会出现死锁的哲学家进餐过程的算法描述。
哲学家（ I＝ 0,1,2,3,4）
思考；
P(mutex);
P(S[i]);
拿起左边的叉子；
P(S[i＋ 1]mod5)；
拿起右边的叉子；
吃通心粉；
放下左边的叉子；
V(S[i]);
放下右边的叉子；
V(S[i＋ 1]mod5)；
V(mutex)
（ 1） 竞争临界资源当系统中供多个进程共享的临界资源（如打印机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个问题在多道程序系统中是无法解决的。
（ 2） 进程推进顺序不当
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个问题在多道程序系统中是可以解决的。
康振华制作 122
一、竞争资源引起死锁
1,资源的分类：可剥夺和非剥夺性资源
可剥夺性资源,CPU和主存
例如：优先权高的程可以剥夺低优先权进程的处理机 。 又如：内存区可由存储器管理程序把进城从一个存储区移至另外一个存储区,即剥夺了该进城原来占有的存储区,甚至可以将一进程从内存调出到外存上 。
不可剥夺性资源,磁带机、打印机等
当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。
2．竞争非剥夺性资源两个进程分别准备打印一个非常大的磁带文件（ 双方都拥有部分资源，同时在请求对方已占有的资源。）
3,竞争临时性资源永久性资源,打印机资源输入可顺序重复使用的资源 。
临时性资源,由一个进程产生,被另一个进程使用一短暂时间后便无用的资源 。
打印机 R1 磁带机 R2
P1 P2
康振华制作 124
二、进程推进顺序不当引起死锁资源 少也未必一定产生死锁。就如同两个人过独木桥，
如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，
那么问题就解决了。
所以，如果程序设计得不合理，造成进程推进的顺序不当，
也会出现死锁。
康振华制作 125
思考题：（北大 95研）
一个 OS有 20个进程,竞争使用 65个同类资源,申请方式是逐个进行的,一旦某个进程获得它所需要的全部资源,
则立即归还所有资源 。 每个进程最多使用三个资源 。 若仅考虑这类资源,该系统有无可能产生死锁,为什么？
答：不可能 。 因为死锁产生的原因有两点：系统资源不足或推进顺序不当,在本题中,进程所需的最大资源数为 60，
而系统共有该类资源 65个,其资源数已足够系统内各进程使用 。
康振华制作 126
1．互斥条件：
每一资源被分配给 一个进程,或者空闲 。
2,占有并请求条件：
已分配到了一些资源的进程可以申请新的资源 。
3,不可剥夺条件：
进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放 。
4．循环等待条件：
链中的每一个进程都在等待相邻进程所占用的资源。
2.8.3 产生死锁的必要条件康振华制作 127
2.8.4 死锁的解决办法：
① 死锁的预防；
② 死锁的避免；
③ 死锁的检测和恢复；
④ 鸵鸟算法当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。
康振华制作 128
这种办法是在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。
该方法虽然比较保守、资源利用率低，但因简单明了并且安全可靠，仍被广泛采用。
产生死锁的四个必要条件中，互斥条件由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。
一、死锁的防止康振华制作 129
1．静态资源分配法（摒弃,占有并请求条件,）
系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。
此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，
从而破坏了占有与请求条件。
康振华制作 130
静态资源分配法的优缺点：
优点：简单,安全,易实现 。
缺点：
（ 1）资源被严重浪费 （ 因为一个进程一次获得其所需的全部资源并且独占，其中有可能有些资源很少使用，
严重恶化了资源利用率 ）。
（ 2）进程延迟运行。 （ 当且仅当进程获得其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行 ）
康振华制作 131
2．摒弃,不可剥夺条件,
进程在需要资源时才提出请求。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。
实现起来比较复杂，且要付出很大的代价。
进程的周转时间较长，系统开销大。
康振华制作 132
3．有序资源使用法（摒弃,循环等待条件,）
系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为 i的资源，就不允许再申请编号比 i
小的资源了，因此，破坏了循环等待条件。
优点：安全且资源利用率比静态资源分配法有所提高,因为它实际是一种半动态的资源分配法 。
缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象康振华制作 133
二,死锁的避免
死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略,保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态,以避免死锁发生 。
死锁的避免与死锁防止策略不同，它不对进程申请资源加任何限制，而是对进程提出的每一次资源请求进行动态检查，并根据检查结果决定是否分配资源以满足进程的请求。由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法高。
康振华制作 134
(一 )系统的状态
1,安全状态若在某一时刻，系统中存在某种进程序列，如
<P1,P2,…,Pn>，如果系统按此序列为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列
<P1,P2,…,Pn>为安全序列。
安全序列的实质是：序列中的每一个进程 Pi
（ i=1,2,…,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。
康振华制作 135
2.不安全状态
– 若在某一时刻，系统中不存在一个安全序列，
则称系统处于不安全状态。
安全状态的例子例：假定系统有三个进程 P1,P2,P3，共有 12台磁带机。
进程 P1总共要求 10台磁带机,P2和 P3分别要求 4台和九台。设在 T0时刻，进程 P1,P2和 P3已经获得 5台,2
台和 2台，还有 3台空闲没有分配 。
进程 最大需求 已分配 可用
P1 10 5 3
P2
P3
4 2
29
T0时刻系统时安全的。这时存在一个安全序列 <P2,P1,P3>
康振华制作 137
注意：
（ 1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
（ 2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，
而系统处于不安全状态则仅仅可能进入死锁状态。
安全状态不安全状态死锁状态康振华制作 138
银行家算法
银行家算法是最有代表性的避免死锁算法，是 Dijkstra
提出的。 其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。
康振华制作 139
银行家算法的实质就是,
要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。
即：每当进程提出资源请求且系统的资源能够满足该请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。
银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量。
银行家算法中所用的主要的数据结构如下：
(1)可利用资源向量 Available
（ 剩余或可用资源量 ）,记录系统中各类资源的当前可利用数目 。 如果 Available[j]=k,表示系统中现有 Rj类资源
k个 。
(2) 最大需求矩阵 Max
每个进程对各类资源的最大需求量
(3)Allocation
已为每个进程分配的数量或者说每个进程对各类资源当前的占有量 。
(4)需求矩阵 Need
某 进程对各类资源尚需要的数目 。
Need=Max－ Allocation
(5)请求向量 Request
它记录某个进程当前对各类资源的申请量,是银行家算法的入口参数 。
当 Pi发出资源请求后,系统按下述步骤进行检查：
1.如果 Requesti > Needi,则出错 。
2.如果 Requesti>Available,则 Pi 阻塞 ；
3.系统试探把要求的资源分配给进程 Pi,并修改下面数据结构中的数值：
Availablei=Availablei-Requesti;
Allocationi=Allocationi+Requesti;
Needi = Needi- Requesti;
4,系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi等待。
1.设置两个向量
① 工作向量 Work.
表示系统可提供给进程继续运行所需要的各类资源的数目,开始时,Work:=Available。
② Finish.
它表示系统是否有足够的资源分配给进程,使之运行完成 。 开始时先做 Finish[i]:=false；当有足够的资源分配给进程时,令 Finish[i]:=true.
2.执行过程的描述：
(1)初始化,work=available； finish=false；
(2)若按进行编号顺序找到了一个可加入安全序列的进程即：满足条件 finishi=false且 needi≤work 的进程 Pi
则 ① 假设该进程不久将完成任务归还资源,置
work=work+allocationi和 finishi=true
② 重复执行这一步 ；
(3)若所有进程的可完成标志 finish为真,则返回逻辑真值
（ 表示系统处于安全状态 ） ；
(4)否则，返回逻辑假值（表示不安全）；
康振华制作 145
可以看出：
银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，
如果有，也只有极少的系统使用银行家算法来避免死锁。
康振华制作 146
银行家算法之例
假定系统中有四个进程 {P1,P2,P3,P4}和三种类型的资源 {R1,R2,R3}，资源的数量分别为 9,3,6，在 T0
时刻的资源分配情况如图,
资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 1 1 2
P2 6 1 3 5 1 1 1 0 2
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
T0时刻是否安全？
资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 1 1 2
P2 6 1 3 5 1 1 1 0 2
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
资源情况进程
Work
R1 R2 R3
Need
R1 R2 R3
Alloca
R1 R2 R3
Work’
R1 R2 R3
P2 1 1 2 1 0 2 5 1 1 6 2 3
P1 6 2 3 2 2 2 1 0 0 7 2 3
P3 7 2 3 1 0 3 2 1 1 9 3 4
P4 9 3 4 4 2 0 0 0 2 9 3 6
P2发出请求向量 request2（ 1,0,1），系统按银行家算法进行检查：
① request2（ 1,0,1） ≤ need2（ 1,0,2）；
② request2（ 1,0,1） ≤ available（ 1,1,2）；
③系统先假定可为 P2分配资源，并修改 available,allocation2和
need2向量资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 0 1 1
P2 6 1 3 6 1 2 0 0 1
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
表 2-2 为 P2试分配资源后的有关资源数据康振华制作 149
④ 再利用安全性检测子算法检查此时系统是否安全。如表 2-3所示。
资源进程
Work
R1 R2 R3
Need
R1 R2 R3
Alloca
R1 R2 R3
Work’
R1 R2 R3
P1 0 1 2 0 0 1 6 1 2 6 2 3
P2 6 2 3 2 2 2 1 0 0 7 2 3
P3 7 2 3 1 0 3 2 1 1 9 3 4
P4 9 3 4 4 2 0 0 0 2 9 3 6
Finish
True
True
True
True
康振华制作 150
例 2.9 某系统有同类互斥资源 m个，供 n个进程共享使用。如果每个进程最多申请 x个资源（ 1≤x≤m ），试证明：当 n(x-1)+1≤m 时，系统不会发生死锁。
证明：因为每个进程最多申请 x个资源，所以最坏情况是每个进程都得到了（ x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为 m-n(x-
1)，于是只要系统中至少还有一个资源可供使用，就可以使这 n个进程中某个进程得到其所需要的全部资源，
并能够继续执行到完成，归还资源可供其他进程使用。
因而不会发生死锁。即只要 m-n(x-1)≥ 1时，系统就一定不会发生死锁。亦即当 n(x-1)+1≤m 时，系统不会发生死锁。
康振华制作 151
三、死锁的检测和解除死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。
(1)死锁的检测检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。
由于死锁是系统中的恶性小概率事件，死锁检测程序的多次执行往往都不会调用一次死锁解除程序，而这却增加了系统开销，因此在设计操作系统时需要权衡检测精度与时间开销。
康振华制作 152
2．死锁的解除
常见的死锁解除方法有以下两种,
（ 1） 撤消进程法
撤消全部死锁进程,代价太大,该做法很少用 。
最小代价撤消法,首先计算死锁进程的撤消代价，然后依次选择撤消代价最小的进程，逐个地撤消死锁进程，回收资源给其他进程，直至死锁不复存在。进程的撤消代价往往与进程的优先级、占用处理机的时间等成正比。
康振华制作 153
（ 2）挂起进程法 （剥夺资源）
使用挂起 /激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。
目前挂起法比较受到重视。
显然，无论哪一种解除死锁的方法，都需要很大的开销。但是死锁的检测与解除办法不对系统的资源分配等加任何限制，因此是对付死锁的诸办法中导致资源利用率最高的一种办法，在对安全性要求高的大型系统中常用。
康振华制作 154
2.9 处理机调度
处理机管理需要解决三个主要问题：
（ 1）按什么原则分配处理机，即需要确定处理机调度算法；
（ 2）什么时候分配处理机，即需要确定处理机调度时机；
（ 3）如何分配处理机，即需要给出处理机调度过程。
康振华制作 155
一,调度算法
引入多道程序系统的直接目的就是想让处理机,忙,,一直以来处理机都是计算机系统中的瓶颈资源之一，特别是在单处理机系统中，处于就绪状态的多个进程竞争使用一台处理机，所以当处理机空闲时，系统需要从多个就绪进程中挑选一个使其投入运行。选择哪一个呢？这需要按某一种算法。 调度算法的实质就是一种资源分配 。
从资源的角度来看,该算法确定了处理机的分配策略,故称其为处理机调度算法；
而从资源使用者的角度看，该算法确定了进程运行的次序，
故也称进程调度算法。
康振华制作 156
处理机的使用方式有两种：
不可抢占方式 与 可抢占方式基本的处理机调度算法有先来先服务法、优先级法和时间片轮转法等，现在也有些操作系统使用综合性的调度算法，比如多级反馈队列调度算法等。
康振华制作 157
1．先来先服务调度算法 FCFS
该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程,把处理机分配给它,使之投入运行 。
D C B A CPU 完成康振华制作 158
在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：
进程 到达时刻 服务时间 开始时刻 完成时刻 周转时间 带权周转
A
B
C
D
0
1
2
3
1
100
1
100
0
1
101
102
1
101
102
202
1
100
100
199
1
1
100
1.99
短作业 C的带权周转时间高达 100。
长作业 D的带权周转时间仅为 1.99
康振华制作 159
FCFS算法有利于 CPU繁忙型的作业，不利于 I/O繁忙型的作业。
这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待 CPU的时间较长。即有利于长作业（进程），不利于短作业（进程）。
在当今系统中,先进先出很少作为调度模式,而是常常嵌套在其它的调度模式中 。
例如,许多调度模式根据优先级将处理机分配给进程,但具有相同优先级的进程却按先进先出进行分配 。
康振华制作 160
2．优先级调度算法
总是选择具有 最高优先级 的进程首先使用处理机 。 在这种算法中,首先考虑的问题是如何确定进程的优先数 。 分为,
静态优先权,在创建进程的时候便确定的,且在进程的运行期间保持不变 。 （ 简单易行,系统开销小,但不够精确,很可能出现优先权低的作业 （ 进程 ） 长期不被调度的情况 。 所以,只在要求不太高的系统中,才使用静态优先数 （ 权 ） ）
动态优先权,在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能康振华制作 161
这是一种 可抢占方式 的调度算法，可防止一个长作业长期的垄断处理机。
若所有的进程具有相同的优先权初值，则按照
FCFS算法，最先进入就绪队列的进程最先获得处理机。若所有的就绪进程具有各不相同的优先权初值，对于优先权初值低的进程，在等待足够的时间后，其优先权可能升为最高，从而获得处理机执行。
康振华制作 162
例 2.10 有 5个进程 P1,P2,P3,P4,P5，它们同时依次进入就绪队列，它们的优先数和需要的处理机时间如下：
进程 处理机时间 优先数
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
康振华制作 163
忽略进程调度所花的时间，要求：
（ 1） 分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；
（ 2） 分别计算各进程在就绪队列中的等待时间和平均等待时间 。
解,（ 1） 采用先来先服务调度算法时各进程的执行次序为,P1→ P2→ P3→ P4→ P5。
采用静态优先级调度算法时各进程的执行次序为：
P4→ P1→ P3→ P5→ P2。
康振华制作 164
（ 2） FCFS中，平均等待时间＝（ 0+10+11+13+14） /5＝ 9.6；
静态优先级法中，平均等待时间＝（ 1+18+11+0+13） /5＝ 8.6
进程 处理机时间 FCFS等待时间 静态优先级法等待时间
P1 10 0 1
P2 1 10 18
P3 2 11 11
P4 1 13 0
P5 5 14 13
康振华制作 165
3.最短作业 /进程优先法（ SJF/SPF）
SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。
SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。
非抢占式。
缺点：没有考虑到某些作业 /进程的紧迫程度。
用户作出的估计时间并不准确，带有很大的主观性。
康振华制作 166
4.最高响应比作业优先算法（ HRN）
是对 FCFS方式和 SJF方式的一种综合平衡响应比。
R＝ (作业等待时间＋需运行时间 )/ 需运行时间
＝ 1＋已等待时间 / 需运行时间
＝ 1＋ W/T
由于 R与要求运行时间成反比，故对短作业是有利的，
另一方面，因 R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的相应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。
康振华制作 167
5．时间片轮转调度算法 (RR)
基本思想,系统把所有的就绪进程按 FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首的进程使用,当该进程的时间片用完以后，
系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度。 同时处理机调度程序又去调度当前就绪队列的 队首进程,也让它运行给定的时间片，如此循环往复。
F C B A…,CPU 完成
A
B
C
时间片轮转算法图示
这就使得就绪队列中所有的进程，都能在一有限的时间内，轮流获得一个时间片的执行时间。
康振华制作 169
最佳时间片的确定这个最佳的时间片值是多少呢？ 显然,它将随系统而异 。 随负载而异,同时也随进程而异 。
时间片的选取是实现各种调度算法的关键之处,而时间片的选定通常应考虑终端数目,处理机能力,各终端任务的急迫程度,外存传输速度等方面的因素 。 时间片轮转法亦可应用于批处理系统的处理机调度 。
① 当时间片很大时,大到一个进程足以完成其全部运行工作所需的时间,此时轮转调度模式退化为 FCFS模式 。
② 当时间片非常小时,调度程序剥夺处理机的次数增多,这将加重了系统开销,系统性能降低,大多数时间都消耗在处理机的转换上 。
康振华制作 170
6．多级反馈队列调度算法
以上介绍的算法,都存在一定的局限性 。
现在主流的操作系统，如 UNIX,Windows
NT,Linux等，都使用一种综合性的调度算法 ——多级反馈队列调度算法。该算法综合了上述三种算法以及多队列调度算法的思想和优点，总体调度性能优越，适于各种类型的作业，
但其实现也比较复杂。
康振华制作 171
算法的基本思想（实施过程）是,
首先,系统按进程优先级设置了多级 （ 比如 n级,n≥2） 就绪进程队列,从第一级队列到最后一级队列,优先级越来越低 。
其次,每一级就绪队列对应一个不同的时间片 。 优先权越高的队列,进程的时间片越小 。
再次,当一个新进程进入内存后,首先被放到第一级队列的队尾 。 按照 FCFS原则排队等待调度 。 当轮到该进程执行时,如能在时间片内完成,便可准备撤离系统；如果在时间片内未完成,调度程序便将该进程转入第二队列的末尾,再依次按照
FCFS原则等待调度 。
康振华制作 172
最后,仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的 n-1级队列全部为空时，才去调度最后第 n级队列中的进程。如果处理机正在第 I队列中为某进程服务时，又有新的进程进入优先权高的队列（第 1～ I-1中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第 i队列的队尾，重新进行处理机调度。
康振华制作 173
二,调度时机
当发生以下几种情况时,现行进程都要放弃处理机的使用,即将引起系统对进程的重新调度：
1,在分时系统中,现行进程的时间片用完了；
2,发生了外部中断；
3,进程因等待某事件或资源而阻塞；
4．现行进程运行结束或出现异常情况。
康振华制作 174
三,调度过程
1,保存,下降,进程现场
2．选择将要运行的进程 ——“上升,进程
3．恢复,上升,进程的现场康振华制作 175
2.10 线程 (Thread)的概念
自 20世纪 60年代提出进程概念后，在操作系统中一直以进程作为能独立运行的基本单位。直到 20世纪 80年代中期，人们为了减少程序并发执行时的时空开销（如进程创建、切换和通信开销），进一步提高程序的并发执行程度，进而提高系统的吞吐量，提出了比进程更小的能独立运行的基本单位 ——线程。
康振华制作 176
回顾进程的两个基本属性：
1.进程是一个可拥有资源的独立单位；
2.进程又是一个可独立调度和分配的基本单位 。 合起来,
进程便成为一个能独立运行的基本单位,从而构成了程序并发执行的基础 。
简言之,由于进程是一个资源的拥有者,在执行这些操作时会付出较大的时间开销 。 因此在系统中所设的进程数目不宜过多,切换不宜过于频繁,这就限制了系统的并发程度 。
康振华制作 177
一,线程的定义
定义,线程是进程中的一个实体，是被系统独立调度和分配的基本单位，故又称为轻型（轻权）进程 (Light Weight Process)，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。
传统的进程称为重型进程 (Heavy Weight
Process)。
康振华制作 178
线程是进程中可独立执行的子任务，是系统独立调度和分派的基本单位。
一个进程中至少有一个线程。线程继承所属进程的一切资源，它自己只拥有运行所需的很少的一点资源，
如几个寄存器和一个堆栈等。因此，一个进程内的几个线程之间的切换的开销比进程间切换的开销小得多，
这是系统引入线程可以提高效率和并发性的主要原因。
康振华制作 179
二,线程与进程的比较
1．拥有资源方面进程都是拥有资源的一个独立单位，它可以拥有自己的资源。
而线程几乎不拥有系统资源,但它可以访问其隶属进程的资源
2．可调度性
以进程为单位进行处理机切换和调度时，处理机切换时间长，
资源利用率降低。以线程为单位进行进行处理机切换和调度时，
由于不发生资源变化，特别是地址空间的变化，处理机切换时间较短，从而处理机效率较高。
康振华制作 180
3．并发性在引入线程的操作系统，不仅进程之间可以并发执行，而且线程之间也可并发执行，因而使操作系统具有更好的并发性，从而能更有效地利用系统资源，提高系统的吞吐量。
4．系统开销由于在创建或撤消进程时，系统要为之分配或回收资源，如内存空间,I/O设备等，所以操作系统创建进程的开销远大于创建线程的开销。类似地，操作系统为进程切换付出的开销也远大于为同一进程内的线程切换付出的开销。另外，由于同一进程内的多个线程具有相同的地址空间，致使它们之间的同步与互斥的实现，也变得比较容易。
康振华制作 181
进程的调度,同步等由 OS内核完成,而线程的控制既可以由 OS内核进行,也可以由用户控制 。
5．系统感知方面康振华制作 182
三,线程的适用范围线程特别适合于共享存储的 多处理机系统 和 C/S模型，成功例子很多，如文件服务器,WWW浏览器等，以下是几种典型的应用：
1,服务器中的文件管理和进程通信控制；
2,前后台处理；
3,异步处理；
4,数据的批处理；
5,网络系统中信息发送和接受
……
处理机一直是决定计算机系统性能的最重要的硬件资源之一。多道程序系统中处理机管理的主要任务就是如何安排多任务使用处理机，即如何把处理机分配给多任务用，
因此处理机调度算法是这一部分的主要内容。但由于多数现代操作系统的设计都是基于进程的概念，处理机的分配对象也大都是进程，所以本章先介绍进程管理，再介绍处理机调度。
康振华制作 2
[考核目的 ]：
考核学员对进程概念、状态、组成，以及进程间同步机制的掌握情况。
[考核的知识点 ]：
程序的顺序执行与并发执行，多道程序设计的优点及带来的问题
进程的定义，进程的基本特征，进程控制块，程序与进程的对比
进程的描述：进程的基本状态及转换（就绪、运行、阻塞）
进程通信：同步与互斥、临界区和临界资源、原语、信号量及 P,V操作、消息缓冲
进程管理的基本命令
[考核要求 ]：
掌握：多道程序设计概念，进程定义,PCB，临界区概念，进程的状态及其变化，进程的同步与互斥。
理解：进程的组成，进程管理的基本命令，信号量和 P,V操作及其应用。
了解：进程高级通信原语。
康振华制作 3
2.1 多道程序设计
多道程序设计是指允许多道程序同时进入内存，并允许它们共享资源、
并发执行的程序设计技术。
采用这一技术的系统叫多道程序系统。
多道程序设计技术根本性地推进了操作系统技术发展。是现代操作系统所采用的最基本、最重要的技术，但它也带来一些单道程序系统中没有的新问题，这些多道程序设计中的新问题可以概括为进程间的互斥与同步，另外，对系统各类资源的管理也都复杂了。对这些问题的解决导致多道程序设计的实现代价比单道程序设计高，也使得现代操作系统变得日益复杂、庞大和精巧。
康振华制作 4
一,顺序程序的执行
单道系统中，程序是顺序执行的，即程序在执行时，必须按照某种先后次序进行，仅当前一操作执行完后，才能执行其后续操作。因此在某一时刻，系统的各个部分中只有一部分在工作。
I1 C1 P2P1 I2 C2
程序的顺序执行康振华制作 5
如对于以下三条语句的程序段：
P1,a=x+y
P2,b=a+1
P3,c=b-6
其中的语句 P2必须在 a被赋值后才能执行。
同样,P3也只能在 b被赋值后才能执行。
康振华制作 6
二、程序顺序执行时的特征
1.顺序性处理机的操作，严格按照程序所规定的顺序执行。
2.封闭性程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有本程序才能改变它。程序一旦运行，执行结果不受外界因素的影响。
3.可再现性只要程序执行时的环境和初始条件相同，当程序多次重复执行，
不论是,走走停停,还是,不停顿,,都获得相同的结果。
康振华制作 7
I1 I2 I3 I4
C1 C2 C4C3
P1 P2 P3 P4
三、程序并发执行康振华制作 8
四、并发程序执行的条件
1,定义
程序 Pi在执行期间所需引用的诸变量 ai的集合,
称为 Pi的 读集,记作 R(Pi)={a1,a2,a3,…,am}。
程序 Pi在执行期间所需改变的诸变量 bj的集合，
称为 Pi的 写集,记作 W(Pi)={b1,b2,b3,…,bm} 。
康振华制作 9
写出下列 4条语句的读集、写集。
语句 读集 写集
P1:a=x+y R(P1)={x,y} W(P1)={a}
P2:b=z+1 R(P2)={z} W(P2)={b}
P3:c=a+b R(P3)={a,b} W(P3)={c}
P4:d=c-2 R(P4)={c} W(P4)={d}
康振华制作 10
2．定理
如果两个程序 P1和 P2满足下述条件,它们便能并发执行,
否则不能 。
R(P1)∩ W(P2)∪ R(P1)∩ W(P2)∪ W(P2)∩ W(P2)={}
即当两个程序的读集与写集的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。该定理是程序并发执行的条件，是 Bernstein在 1966年提出的，故称
Bernstein条件。
康振华制作 11
p1
p2
p3 p4
画出这四条语句的前趋图,
程序并发执行时的特征：
间断性程序在并发执行时，由于共享资源，或者为完成同一任务而相互合作，致使在并发程序间形成了相互制约的关系。
失去封闭性程序在并发执行时，是多个程序共享系统中的各种资源，所以这些资源的状态可以由多个程序来改变，，使其失去了封闭性。
不可再现性程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。
康振华制作 13
例如：有两个循环程序 A和 B,A每执行一次时，都要作 m
＝ m＋ 1操作。 B每执行一次时，先执行 print(m)操作，
然后再将 m置成,0”。 A和 B以不同速度运行，可能出现以下三种情况（假定某时刻变量 m的值为 m）：
m=m+1 在 print(m)和 m＝ 0之前。此时得到的 m值分别为 m+1,m+1,0
m=m+1 在 print(m)和 m＝ 0之后。此时得到的 m值分别为 m,0,1
m=m+1 在 print(m)和 m＝ 0之间。此时得到的 m值分别为 m,m+1,0
康振华制作 14
2.2 进程的描述
程序并发执行时，产生了一些新特征，所以一般的程序是不能并发执行的。为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以控制和描述，引入“进程”的概念。
现在,,进程,已经成为操作系统乃至并发程序设计中最核心的概念，它是对正在运行的程序的抽象，操作系统的其他所有内容都是围绕着进程展开的。掌握进程的概念对于理解操作系统的实质以及分析、设计操作系统都有非常重要的意义康振华制作 15
一,进程的定义
,进程,这一术语，在 60年代初期，首先在美国 MIT的 MULTICS系统和 IBM公司的 CTSS/360系统中引入。其中能反映进程实质的定义有：
（ 1）进程是程序的一次执行。
（ 2） 进程是可以和其他计算并发执行的计算 。
（ 3） 进程是一个程序及其数据在处理机上顺序执行时发生的活动 。
（ 4） 进程是程序在一个数据集合上的运行过程,是系统进行资源分配和调度的一个独立单位 。
（ 5）进程是进程实体的一次活动。
康振华制作 16
我国 1978年在庐山召开的全国 OS研讨会上将
,进程,定义为：
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。
一个程序为实现不同的任务可以同时有多次运行活动，每个运行活动分别作为不同的进程康振华制作 17
二,进程的特性及与程序的区别
1.进程的五个特性
(1) 动态性,生命周期。 即它由系统,创建,而诞生，因被,调度,
而执行，因得不到资源而暂停，最后因被,撤消,而消亡。
(2)并发性,是指不同进程的动作在时间上可以重叠，即系统内的多个进程是可以并发执行的。
(3)独立性,指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位 。
(4)异步性,指进程按各自独立的、不可预知的速度向前推进
(5)结构特性,从结构上看，每个进程都由程序段、数据段和一个
PCB三部分组成。
2.进程与程序的区别
(1)从定义上看,进程是程序处理数据的过程,而程序是一组指令的有序集合；
(2)进程具有动态性,并发性,独立性和异步性等,
而程序不具有这些特性；
(3)从进程结构特性上看,它包含程序 （ 以及数据和 PCB） ；
(4)进程和程序并非一一对应。
康振华制作 19
在操作系统中引入,进程,概念的主要目的是（ ）。
A．改善用户编程环境
B,描述程序动态执行过程的性质
C,使程序与计算过程一一对应
D,提高程序的运行速度康振华制作 20
三,进程的基本状态及其转换
1．进程的三种基本状态
（ 1）就绪（ Ready）状态,当进程已分配到除 CPU以外的所有必要的资源，只要能再获得处理机，便可立即执行
（ 2）执行（ Running）状态,当进程已获得处理机，其程序正在处理机上执行，
（ 3）阻塞（ Blocked）状态,正在执行的进程，由于等待某事件发生而无法执行时，便放弃处理机而处于暂停状态。
在不少系统中,又增加了两种基本状态：
①新状态 ②终止（ Terminated）状态康振华制作 21
引入新状态和终止状态的原因：
由于 OS在建立一个新进程时，通常分为 2步：第一步是为新登录的用户程序（分时系统）创建进程，并为他分配资源，此时进程即处于新状态。第二步是把新创建的进程送入就绪队列，一旦进程进入就绪队列，它便由新状态变为就绪状态。
一个结束了的进程，其退出系统的过程也分为两步：第一步是将该进程从就绪队列中移出，使之成为一个不可能再运行的进程，相应的进程处于终止状态。此时系统并不立即撤销它，而是将它暂时留在系统中，以便其它进程去收集该进程的有关信息。
康振华制作 22
新进程就绪 执行结 束阻塞接纳完成
I/O完成或等待的事件发生
I/O请求或等待某事件
2．进程三种基本状态间的转换调度时间片用完康振华制作 23
其他的状态
例如，在有的系统中，为了暂时缓和内存的紧张状态，
或为了调节系统负荷，又引入了挂起功能。即暂时挂起一部分进程，把它们从内存临时换出到外存，使它们暂时和系统脱离联系。这样，就需要把进程的就绪状态进一步细分为 活动就绪状态 （未被挂起的就绪进程）和 静止就绪状态 （被挂起的就绪进程）两种。把进程的阻塞状态也细分为 活动阻塞状态 （未被挂起的阻塞进程）和 静止阻塞状态 （被挂起的阻塞进程）
康振华制作 24
问题：
1.在进程状态转换时,下列哪一种状态转换是不可能发生的？
A)就绪态 → 运行态 B)运行态 → 就绪态
C)运行态 → 等待态 D)阻塞态 → 运行态
2．某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将（ ）。
A.从就绪变为运行 B.从运行变为就绪
C.从运行变为阻塞 D.从阻塞变为就绪康振华制作 25
四,进程控制块 ——PCB
(Process Control Block)
PCB是系统为了描述和控制进程的运行而为进程定义的一种数据结构,
它是进程实体的一部分,是进程存在的唯一标志,也是操作系统中最重要的结构体类型的数据结构 。
PCB中存放着操作系统所需的用于描述进程的当前情况以及控制进程运行的全部信息 。
康振华制作 26
1,PCB的作用
（ 1） 标识进程的存在,系统创建进程时，就为之创建一个 PCB；
进程结束时，系统又回收其 PCB，进程便随之消亡 。
（ 2） 为系统提供可并发执行的独立单位,PCB使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。没有为之建立 PCB的程序是不能并发执行的。
（ 3） 为系统控制和管理进程提供所需的一切信息 。
康振华制作 27
2,PCB中的信息
（ 1） 进程标识符：
（ 2） 进程的现行状态,
（ 3） 处理机的现场保留区,
（ 4） 进程相应的程序和数据地址,
（ 5） 进程资源清单,
（ 6）进程优先级,
（ 7） 进程同步与通信机制：
（ 8） 进程所在 PCB的链接字,
（ 9） 与进程有关的其他信息：
康振华制作 28
五,进程的队列所谓 进程队列 指的是把具有相同状态的进程按照某种原则链接在一起组成的队列，它其实是 PCB的一种组织形式，有时也称 PCB链因为 PCB是系统中最重要也是被频繁访问的数据结构，系统中的许多模块，如调度程序、资源分配程序、中断处理程序以及监督和分析程序等，特别是运行频率很高的进程分派程序，都要对它进行读或写操作，所以 PCB常驻内存的系统区中，系统将所有的
PCB以数组形式连续存放组织成若干个链表（或队列），存放在操作系统中专门开辟的 PCB区内。
康振华制作 29
空闲 PCB队列头指针阻塞进程队列头指针就绪进程队列头指针执行进程指针 PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCB8
PCB9
4
3
0
8
7
9
0
15…
.
康振华制作 30
一、进程控制机构
1．操作系统的内核通常将一些与硬件密切相关的模块，例如，中断处理程序、各种常用设备的驱动程序，以及运行频率较高的模块等安排在紧靠硬件的软件层中，并将它们常驻内存，以提高操作系统运行效率，并对它们加以特殊的保护。上述这一部分程序称为操作系统内核。
操作系统的内核是计算机硬件扩充的第一层软件，是在核心态运行的操作系统程序。
2.3 进程的控制康振华制作 31
2．内核中与进程控制有关的机构
（ 1）原语操作：
原语 本身是由若干条指令构成、用于完成特定功能的一个过程。
原子操作,一个操作中的所有动作，与一般过程的区别：
要么全作，要么全不作。
即：原子操作是不可分割的，它是机器指令的延伸。
康振华制作 32
现代操作系统常采用屏蔽中断的方法来保证原语在执行时的不可分割性，这种 原子性 对于解决进程同步互斥问题是非常重要的。在内核中可能有许多原语，常见的内核原语有进程控制原语、用于链表操作的原语和用于控制进程互斥、同步的原语等。
康振华制作 33
（ 2）进程管理：
进程管理的全部或大部分功能都在内核中,这主要是因为这些功能模块的运行频率较高,例如,进程调度与分派,进程的创建,进程的撤消等,或是因为它们为多种功能模块所调用,例如,实现进程的同步和进程通信的原语等 。 此外,内核中的进程管理,还需要管理好进程控制块 PCB.
康振华制作 34
A
B C
GFE HD
I J K L M
二,进程的控制原语进程树祖先
进程控制原语是对进程生命期控制和实现进程状态转换的原语。
康振华制作 35
1.进程创建原语 Creat()
引起创建进程的事件：
用户登录
作业调度
提供服务
应用请求
进程创建的主要步骤：
申请空白 PCB
为新进程分配资源
初始化 PCB的内容
将新进程插入就绪队列康振华制作 36
2.进程撤销原语 Tenminat()
引起创建进程的事件：
正常结束
异常结束
外界干扰
进程撤销的过程：
检索进程当前的状态，结束并置调度标志，撤销其所有的子进程，归还资源，
移出队列
应由父进程调用进程撤销原语来撤销，以便及时的释放其所占的资源康振华制作 37
3.进程阻塞原语 Block()
引起进程阻塞的事件：
请求系统服务
启动某种操作
新数据尚未到达
无新工作可作
进程堵塞的过程：
发现堵塞事件，调用阻塞原语把自己阻塞，停止进程的执行，修改 PCB的 状态信息,将其插入到自己的堵塞队列。最后转调度程序，将处理机分配给另一个就绪进程 。进程的阻塞是进程自身的一种主动行为康振华制作 38
4.进程唤醒原语 Wakeup()
引起进程唤醒的事件：
当被阻塞进程所期待的事件出现时，或者所期待的数据已经到达。由该有关进程调用进程唤醒原语，
将等待该资源而阻塞的一个进程唤醒成 ……
进程唤醒的过程：
把被阻塞进程从等待该事件的阻塞队列中移出，
将其 PCB的现行状态，
由阻塞改为就绪，再将该进程插入到 PCB就绪队列中。
康振华制作 39
5.挂起原语 Suspend( ):
当出现了引起挂起的事件时，如为了暂时缓和内存的紧张状态，用户进程请求将自己挂起或者当父进程请求将自己的某个子进程挂起时，系统将利用挂起原语 suspend()将制定的进程或处于阻塞状态的进程挂起。
6.激活原语 Active( ):
将进程从外存调入内存，检查该进程的状态，改为相应的活动状态康振华制作 40
2.4 进程的互斥
—— 你要，我也要
多道程序设计带来的问题,
并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。
为此,现代操作系统都在内核中设有进程的互斥同步机制，以控制并发执行的诸进程能有效的共享资源和相互合作，同时使并发程序的执行仍具有可再现性。
康振华制作 41
一,互斥的定义
所谓 进程互斥,指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用 。
进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称 间接制约关系,主要是由被共享资源的使用性质所决定的。
康振华制作 42
这种限定进程只能互斥地访问它的资源叫 临界资源（ 指一次仅允许一个进程使用的资源 ） 。
临界资源限定了使用者只能互斥地使用它。
操作系统也不能中途从抢先者手中把临界资源抢来给其他进程用。
因此，临界资源也是不可剥夺性资源。 例：打印机、共享变量 等。
计算机系统中可剥夺性使用的资源主要有 CPU,内存 和 磁盘 等。
康振华制作 43
程序 段 1 程序 段 2 程序 段 n
共 享 变量康振华制作 44
临界区,进程中访问临界资源的那段程序代码称为临界区或临界段。
使用同一临界资源的不同进程中的临界区称为 同类临界区 或 相关临界区 。
为实现对临界资源的互斥访问，应保证诸进程 互斥 地进入各自的临界区。
但无论采用何种方法，都应 遵循临界区的使用原则,即
,空则让进，忙则等待，等则有限，等则让权,。
康振华制作 45
二,上锁和开锁原语
现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、
管程机制等。
上锁与开锁是一种最简单的进程互斥方法，它使用一个锁变量 W来表示某种临界资源的状态，
W=0表示 资源空闲可用
W=1表示 资源正被使用康振华制作 46
1．上锁原语,LOCK（ W）
L1：如果 W=1那么转向 L1;
否则 W=1
返回
void lock(锁变量 w) {
test,if (w 为 1)
goto test
else
w=1; /*上锁 */
} /* lock(w) */
1.考察锁位的值；
2.如果原来的值为 0，将锁位置 1；
3.如果为 1，则返回第一步再次考察康振华制作 47
2．开锁原语,UNLOCK（ W）
W=0;
返回
void unlock(锁变量
w) {
w=0; /* 开锁 */
} /* unlock(w) */
当进程使用完资源后，它必须将锁位置成,0”，称为开锁操作。
康振华制作 48
三、用上锁和开锁原语可以解决并发进程的互斥
任何欲进入临界区的进程，必须先执行上锁原语。若 上锁原语 顺利通过，则进程可 进入临界区 ；当完成对临界区资源的访问后再执行 开锁原语,以释放该临界资源。
即 在相关进程的程序里由上锁和开锁原语紧夹着临界区,
就能保证这些进程互斥地进入各自的临界区。
康振华制作 49
例如，甲、乙两进程要访问同一类临界资源
甲进程：
其他代码；
LOCK（ W）；
甲进程的临界区；
UNLOCK（ W）；
其他代码；
乙进程,
其他代码；
LOCK（ W）；
乙进程的临界区；
UNLOCK（ W）；
其他代码；
用上锁 用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起 CPU“忙等,。
康振华制作 50
2.5 信号量机制
荷兰著名科学家，后来的计算机图灵奖获得者，
E.W.Dijkstra于 1965年提出了用作进程同步工具的 信号量 （ semaphore） 机制,这是一种卓有成效的进程互斥同步工具，已被广泛应用于现代计算机系统中。
康振华制作 51
信号量机制的基本原理是：
两个或多个进程可以利用彼此间收发的简单的信号来实现,正确的,并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。
经典的整型信号量＝,经记录型信号量＝,信号量集机制
CPU忙等造成死锁 不易死锁，可能导致资源利用率低康振华制作 52
一,信号量的概念
信号量,也叫 信号灯,一般是由两个成员组成的数据结构，是一个确定的二元组 （ S,Q）
S是个具有非负初值的 整型变量,表示该信号量的值，且 S的值只能由定义在信号量上的 P操作原语和 V操作原语来改变；
Q是个初始状态为 空的 队列 。
康振华制作 53
另一定义：
信号量类型是个复合类型，其一个分量是个整型分量 S，另一个分量是个等待队列指针 Q （一个是指向 PCB的指针，
当多个进程都等待同一信号量时，它们就排成一个队列，
由信号量的指针项指出该队列的头。）
信号量通常可以简单反映出相应资源的使用情况，它与 P，
V操作原语一起使用可实现进程的同步和互斥。
康振华制作 54
**信号量的整型分量 S的值的物理含义：
当 S≥ 0时，表示某类可用资源的数目，或者说表示可以执行 P操作而不会被阻塞的进程的数目；
当 S＜ 0时，其绝对值表示信号量 S的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，
亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。
另外,S的值只能由 P,V操作来改变。
康振华制作 55
二,P,V操作原语
P代表荷兰语的 proberen，意为,测试,；
V代表荷兰语的 verhogen，意为,增加,。
现在很多国外的文献都使用 wait和 signal操作（或者 down和 up操作）代替 P,V操作。
康振华制作 56
1．定义在信号量 S上的 P（ S）原语操作的算法描述为：
（ 1） S减 1；
（ 2） 若 S≥ 0,则调用 P（ S） 的进程返回,继续执行；
（ 3） 若 S<0，调用者进程调用阻塞原语 Block
（ Q），把自己插入到信号量 S的阻塞队列 Q
中 (把相应的 PCB连入该信号量队列的末尾，并放弃处理机，进入等待 )。
康振华制作 57
2．定义在信号量 S上的 V（ S）原语操作的算法描述为：
（ 1） S加 1；
（ 2） 若 S>0,则调用 V（ S） 的进程继续执行,
返回；
（ 3）若 S<0,调用者进程调用唤醒原语 Wakeup（ Q）
把信号量 S的阻塞队列 Q中的队首进程移出并唤醒，返回。
康振华制作 58
P(s)入口
S-1=>S
S≥ 0
Block(Q)
返回Y
N
康振华制作 59
V(s)入口
S+1=>S
S>0
Wakeup(Q)
返回Y
N
康振华制作 60
注意 P（ S）操作和 V（ S）操作的物理含义：
P（ S）操作表示,等信号,,即测试一个要等的信号是否到达；
V（ S）操作表示,发信号,。这个信号在实现同步时就是,合作者的伙伴进程已完成前趋任务,,在实现互斥时就是,临界资源可用,。
另外，在互斥问题中，每执行一次 P（ S）操作的含义，
也可理解为进程请求一个单位的 S类资源；每执行一次
V（ S）操作的含义，也可理解为进程释放一个单位的 S
类资源。
康振华制作 61
三,用 P,V操作原语实现进程的互斥
用 P,V操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以 P操作和 V操作即可，即在相关进程的程序里由 P操作和 V操作原语紧夹着临界区，
就能保证这些进程互斥地进入各自的临界区。
这里所用信号量的初值一般为 1，表示临界资源未被占用，
且其可用数目为 1。
用 P,V操作原语实现进程互斥的效率更高一些，因为 P操作中引入了阻塞机制，所以消除了 CPU忙等现象。
康振华制作 62
P(S)
V(S)
P(S)
V(S)
P(S)
V(S)
P1 P2 P3
互斥区康振华制作 63
一个简化的异地售票程序，假设几乎同时两地有两个乘客要购买同一班次的车票各一张
两个终端售票程序都要访问存放该次车票的数据单元 Pk
假设它们都要对 Pk做如下的访问操作
,若 Pk≥1,则将 Pk的值减 1，卖出一张票，返回
否则打印‘无票’信息，返回”
如果不加任何限制让这两个程序并发执行的话,结果可能会导致错误，甚至两地各卖出一张重票的现象康振华制作 64
例 2.1 试用 P,V操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。
主要步骤是：
（ 1）分析清楚题目涉及的进程间的制约关系。
（ 2）设置信号量（包括信号量的个数和初值，
对于同步问题还要写出信号量的物理含义）。
（ 3）给出进程相应程序的算法描述或流程控制，并把 P,V操作加到程序的适当处。
康振华制作 65
北京售票终端进程：
① 根据顾客订票要求找到公共数据单元 PK；
② P（ S）；
③把 PK的值读到工作寄存器 R1中；
④根据顾客订票数修改 R1；
⑤将 R1的值回写到 PK中；
⑥ V（ S）；
⑦售出顾客所订的票，返回；
康振华制作 66
天津售票终端进程：
① 根据顾客订票要求找到公共数据单元 PK；
② P（ S） ；
③ 把 PK的值读到工作寄存器 R2中；
④ 根据顾客订票数修改 R2；
⑤ 将 R1的值回写到 PK中；
⑥ V（ S） ；
⑦ 售出顾客所订的票,返回 ；
康振华制作 67
2.6进程的同步 (synchronism)：
——你等我，我也等你
多道程序系统中，许多进程之间可能存在以下两种制约关系：
1.源于 资源共享的 直接制约关系 （互斥）
2.源于 合作相互的 间接制约关系 （同步）
后者即一种合作进程在独自并发执行过程中的某些确定的时序点上,你等我，我也等你,的同步约束，前者可视为后者的特例（前面已经介绍）。
康振华制作 68
1.资源共享关系很多进程之间彼此无关,它们并不知道其它进程的存在 。
例如在分时系统中,系统分别为每个用户 （ 终端 ） 建立一个进程 。 但这些进程既然同处于一个系统中,也就必然存在着资源共享的关系,如共享 CPU和 I/O设备等 。 此时,进程的主要任务,是保证各个进程能互斥地访问临界资源 。
所以,系统中的资源应该不允许用户进程直接使用,而应该由系统同一分配 。 例如：在仅有一台打印机的系统中,
两个进程提出打印请求
2.相互合作关系
例如输入进程、计算进程、打印进程合作完成一批数据的输入、计算和打印时的关系；中断响应过程；生活中下棋、
看病时等化验结果等等。
康振华制作 69
一,同步的定义进程同步,指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些个确定的时序点上必须相互协调，
即一个进程的执行依赖于另一个进程 ——其合作伙伴的消息，当一个进程到达了某一确定点而没有得到合作伙伴发来的“已完成某些操作”的消息时必须等待，直到该消息到达被唤醒后，才能继续向前推进。
进程同步是多道程序系统中进程之间存在的一种主要 源于进程间合作的 制约关系，也称 直接制约关系。
康振华制作 70
父子进程就是典型的合作进程,
它们之间的同步关系有时也被形象地称为,生产者与消费者” 之间的关系,“产品,（即生产者进程的输出，
亦即消费者进程的输入）是它们的纽带，它们在执行过程中的某个或某些确定的时序点上有着固定的前趋后继的同步约束，即先“生产”后“消费”，这是一种“你等我”
的关系。
而在稍微复杂一点的进程同步问题里，合作进程间的
“生产者与消费者”的关系或身份是可以经常转换的，因此，这些合作进程在执行过程中就会出现时而你等我，时而我等你的现象。
康振华制作 71
进程同步和互斥间的关系：
相似处,进程的互斥实际上是进程同步的一种特殊情况； 进程的互斥和同步统称为进程同步。
差别,进程互斥 是进程间共享资源的使用权,这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，
直到不需要使用时再归还；而 进程同步 则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。
康振华制作 72
P,V操作也都是配对出现,但对 同一个信号量 的 P,V操作却不是同时出现在每一个进程的程序里,而是分别出现在 一个进程和它的合作伙伴的代码中 。
而且 P,V操作的出现位置都在各个合作进程中确定的时序点,
即一个生产者进程在完成了前趋的生产任务后,应立即给合作伙伴 —
—消费者进程发送一条,已完成前趋生产任务,的消息,这要执行 V
操作；而后继的消费者进程在消费前,应该执行对同一个信号量的 P
操作,以测试其合作伙伴 ——生产者进程,已完成前趋生产任务,的消息是否到来,如果到来就开始消费,否则就阻塞自己 。
二、用 P,V操作原语实现进程的同步康振华制作 73
解答这类进程同步问题的主要步骤也是三大步：
(1)分析清楚题目涉及的进程间的制约关系
(2)设置信号量（包括信号量的个数和初值及其物理含义）,合作进程间需要收发几条消息相应就设置几个信号量。同步信号量的初值一般为 0，表示 ……
(3)给出进程相应程序的算法描述或流程控制，并把 P、
V操作加到程序的适当处。
康振华制作 74
＝,例 2.2 生产者 ——消费者问题公用缓冲池，有 n个缓冲区康振华制作 75
生产者－消费者问题是相互合作进程关系的一种抽象
输入 ——计算 ——打印生产者 消费者生产者 消费者系统中使用资源的进程 —— 消费者系统中释放同类资源的进程 —— 生产者康振华制作 76
问题分析：
① 生产者 —消费者之间的同步关系表现为,一旦缓冲池中所有缓冲区均装满产品时，生产者必须 等待消费者提供空缓冲区 ；一旦缓冲池中所有缓冲区全为空时，
消费者必须 等待生产者提供满缓冲区 。
② 生产者 —消费者之间还有互斥关系,由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。
康振华制作 77
问题解答：
① 所用信号量设置如下：
Ⅰ ） 同步信号量 empty,初值为 n,表示消费者已把缓冲池中全部产品取走,有 n个空缓冲区可用 。
Ⅱ ） 同步信号量 full,初值为 0,表示生产者尚未把产品放入缓冲池,有 0个满缓冲区可用 。
Ⅲ ） 互斥信号量 mutex，初值为 1，以保证同时只有一个进程能够进入临界区，访问缓冲池。
康振华制作 78
② 用信号量机制解决生产者 —消费者问题的算法描述如下：
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ empty）； P（ mutex）；
P（ mutex）； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex）； V（ empty）；
V（ full）； 消费该产品；
康振华制作 79
如果将生产者的两个 P操作对调？？
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ mutex） ； P（ mutex）；
P（ empty） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex） ； V（ empty）；
V（ full） ； 消费该产品；
康振华制作 80
如果将消费者的两个 P操作对调？？
生产者 i 消费者 j
生产出一产品； P（ mutex）；
P（ empty ） ； P（ full）；
P（ mutex ） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ mutex ） ； V（ empty）；
V（ full ） ； 消费该产品；
康振华制作 81
如果将两个 V操作对调？？
生产者 i 消费者 j
生产出一产品； P（ full）；
P（ mutex） ； P（ mutex）；
P（ empty） ； 从缓冲区取出一产品；
将该产品放入缓冲区 ； V（ mutex）；
V（ full） ； V（ empty）；
V（ mutex） ； 消费该产品；
康振华制作 82
＝,例 2.3 读者 ——写者问题
该问题描述的是：
一组读者与一组写者循环访问共享的同一个数据对象。
读者：指能对共享数据对象读的进程，写者：指对共享数据对象只要求写的进程。
规定：多个读者可以同时读这个数据对象，但 决不允许多个写者同时对这个数据对象进行 写 操作，也不允许读者、写者 同时 访问这个数据对象。
康振华制作 83
读者 —写者问题是共享数据对象的非合作进程关系的一种抽象
如文件管理模块中读文件、写文件等许多操作进程之间
异地售票程序也可看成是写者与写者的问题
读者 —写者问题是指保证一个写者进程必须与其他写者或读者进程互斥地访问一个共享数据对象的同步问题。
康振华制作 84
问题分析：
① 读 者 —写者之间的互斥关系：
写者与写者的互斥、写者与读者的互斥。设一个公用的初值为
1的互斥信号量 RW_mutex？但是实现了读者与读者的互斥。引入一个读者计数器变量 RC。
②读 者 —读者之间又有了互斥关系：
再设一个读者公用的初值为 1的互斥信号量 R_mutex
实现各个读者间互斥的访问 RC
康振华制作 85
问题解答：
① 所用信号量和其他变量设置如下：
Ⅰ ） 互斥 信号量 RW_mutex,初值为 1,用于实现写者与其他写者或读者互斥地访问共享的数据对象 。
Ⅱ ） 互斥 信号量 R_mutex,初值为 1,用于实现诸读者互斥地访问读者计 0数器变量 。
Ⅲ ）整型变 量 RC，初值为 0，用于对读者进行记数。
康振华制作 86
② 用信号量机制解决读者 —写者问题的算法描述如下：
读者 写者
P（ R_mutex） ； P（ RW_mutex） ；
若 RC=0则 P（ RW_mutex）； 对数据对象进行写操作；
RC加 1； （ RW_mutex） ；
V（ R_mutex） ；
读数据对象；
P（ R_mutex） ；
RC减 1；
若 RC=0则 V（ RW_mutex） ；
V（ R_mutex）；
康振华制作 87
＝,例 2.4 试用用信号量机制描述两人下象棋的过程。
两人下象棋的过程可以概括为：一开始只能是,红先黑后,,以后两人要循环轮流走子，直至某一方获胜或双方和棋为止。这是个只有一个生产者和一个消费者的生产者 ——消费者问题，是个典型的,你等我，我也等你,
的问题。红方是总的前趋任务 ——生产者进程，黑方是总的后继任务 ——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。
棋盘则是生产者与消费者共享的缓冲。
康振华制作 88
二人对弈过程是个纯粹的同步过程
解答：
① 所用信号量设置如下：
Ⅰ ） 同步信号量 hei,初值为 1,表示黑方已走子,开始时可使红方先行不受阻 。
Ⅱ ） 同步信号量 hong,初值为 0,表示红方尚未走子,
开始时可使黑方先行受阻 。
康振华制作 89
② 用信号量机制描述的二人下象棋过程如下：
P（ hei）； P（ hong）；
若被黑方将死，则投子认负，结束； 若被红方将死则投子认负，结束 ；
若同意与黑方作和，则结束； 若同意与红方作和，则结束；
否则，根据棋局思考后走一子 ； 否则，根据棋局思考后走一子；
V（ hong）； V（ hei）；
康振华制作 90
＝,例 2.5 某小型超级市场，可容纳 50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和 P,V操作写出购物者的同步算法。
这是个典型的进程互斥问题康振华制作 91
解答,
① 所用信号量设置如下：
Ⅰ ） 互斥信号量 S,初值为 50,用以保证最多可以有 50个购物者同时进入超市 。
Ⅱ ） 互斥信号量 mutex,初值为 1,用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子 。
②用信号量机制给出的每个购物者购物过程的算法描述如下：
康振华制作 92
购物者 i进程（解法一） 购物者 i进程（解法二）：
P（ S） ； P（ S） ；
P（ mutex） ； P（ mutex1） ；
从入口处进超市,并取一只篮子； 同左；
V（ mutex） ； V（ mutex1） ；
进超市内选购商品； 同左 ；
P（ mutex） ； P（ mutex2） ；
到出口结帐,并归还篮子； 同左 ；
V（ mutex） ； V（ mutex2） ；
从出口离开超市； 同左 ；
V（ S） ； V（ S） ；
↓ ↓
结 束,结 束,
康振华制作 93
＝,例 2.6 桌上有个只能盛得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和 P,V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。
本题属于生产者 ——消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。
康振华制作 94
解答：①所用信号量设置如下：
Ⅰ ） 同步信号量 empty,初值为 1,表示盘子是空的,即儿子或女儿已把盘中的水果取走 。
Ⅱ ） 同步信号量 orange,初值为 0,表示爸爸尚未把桔子放入盘中 。
Ⅲ ）同步信号量 apple，初值为 0，表示爸爸尚未把苹果放入盘中。
康振华制作 95
② 使用信号量机制的三个进程的同步描述如下：
爸爸进程（ P）,儿子进程（ C1）,女儿进程（ C2）：
P（ empty）； P（ orange ）； P（ apple）；
将水果放入盘中； 从盘中取出桔子； 从盘中取出苹果；
若放入的是桔子,V（ empty）； V（ empty）；
则 V（ orange）； 吃桔子； 吃苹果；
否则,V（ apple） ；
康振华制作 96
＝,例 2.7 设 A,B两点之间是一段东西向的单行车道，
现在要设计一个 AB路段自动管理系统，管理规则如下：
当 AB间有车辆在行驶时同方向的车可以同时驶入 AB段，
但另一方向的车必须在 AB段外等待；当 AB段之间无车辆行驶时，到达 AB段的任一方向的车都可进入 AB段，
但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在 AB段行驶的车辆驶出了 AB段且暂无车辆进入 AB段时，应让另一方向等待的车辆进入 AB段行驶。试用信号量和 P,V操作管理 AB路段车辆的行驶。
康振华制作 97
解答：①所用信号量和其他变量设置如下：
Ⅰ ） 整型变量 Car_A,初值为 0，
用于对从 A点 （ 东 ） 驶入 AB段的车辆进行记数 。
Ⅱ ） 整型变量 Car_B,初值为 0，
用于对从 B点 （ 西 ） 驶入 AB段的车辆进行记数 。
Ⅲ ） 互斥信号量 mutex,初值为 1，
用于实现不同方向的第一辆车互斥驶入 AB路段 。
Ⅳ ） 互斥信号量 ma,初值为 1，
用于实现东西向的车互斥地访问计数器变量 Car_A。
Ⅴ ）互斥信号量 mb，初值为 1，
用于实现西东向的车互斥地访问计数器变量 Car_B。
康振华制作 98
通过 AB路段向西行驶的车辆 i 向东行驶的车辆 j
P（ ma） ； P（ mb） ；
若 Car_A=0则 P（ mutex）； 若 Car_B=0则 P（ mutex）；
Car_A加 1； Car_B加 1；
V（ ma） ； V（ mb） ；
车辆从 A点通过 AB路段到达 B点； 车辆从 B点通过 AB路段到达 A点；
P（ ma） ； P（ mb） ；
Car_A减 1； Car_B减 1；
Car_A=0则 V（ mutex）； Car_B=0则 V（ mutex）；
V（ ma）； V（ mb）；
康振华制作 99
总结上述几个有趣的实例的解题过程，可以得出这样的结论：
实现进程的同步互斥实际就是给进程的并发执行增加一定的限制，以保证被访问的共享数据的完整性和进程执行结果的可再现性。
康振华制作 100
用信号量机制解这类题的三个步骤：
（ 1）分析进程间的制约关系
（ 2）设置信号量
（ 3）实施 P,V操作。
第一步是基础、关键，第三步是核心。
掌握实现进程互斥与进程同步的第三步在形式上差异：即 P、
V操作总是 配对 出现的。
但 P,V在 互斥问题 中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在 同步问题 中，却是分别出现在两个合作进程的代码中，需要等消息的一方用 P操作，相应的对同一信号量的 V操作则在发出此消息的另一方中。
康振华制作 101
练习题：
1、有两个用户进程 A和 B，在运行过程中都要使用系统中的一台打印机输出计算结果。
试说明 A,B两进程之间存在什么样的制约关系？
为保证这两个进程能正确地打印出各自的结果，
请用信号量和 P,V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。
康振华制作 102
解,(1) A,B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
（ 2） mutex：用于互斥的信号量，初值为 1。
进程 A 进程 B
,.,…
,.,…
P(mutex) P(mutex)
申请打印机 申请打印机
使用打印机 使用打印机
V(mutex) V(mutex)
… …
康振华制作 103
2,有一个阅览室，共有 100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息,试问：
（ 1） 为描述读者的动作，应编写几个程序，设置几个进程？
（ 2） 试用 PV操作描述读者进程之间的同步关系。
康振华制作 104
分析：
读者的动作都是一样的：登记进入阅览室，阅读，撤消登记离开阅览室，因此 可写一个程序，设 n(n≥100)个进程 。
读者共享的资源有阅览室的座位和登记表，因此诸个读者进程之间有两种互斥制约关系,需设 2个信号量 来实现：
seat：用于实现诸读者对阅览室的空闲座位的互斥竞争，
初值为 100；
mutex：用于实现诸读者对登记表的互斥访问，初值为 1。
下面给出一种解法，当然还有其他解法（比如借鉴经典的读者写者问题的解法，利用读者计数器变量）。
康振华制作 105
解,(1)可写一个程序，设 n(n≥100)个进程
(2)读者进程 readeri(i=1,2,3,…… )描述如下：
P（ seat） ; /*申请空座位 */
P（ mutex） ; /*申请登记 */
登记；
V（ mutex） /*允许其他读者登记 */
阅读；
P（ mutex） ; /*申请撤消登记 */
撤消登记；
V（ mutex）； /*允许其他读者撤消登记 */
V（ seat）； /*释放座位，允许他人进入 */
康振华制作 106
§ 2.7进程通信 (communication)
进程之间的信息交换称为进程通信。
合作进程间所交换的信息量，少则是一个状态或数据，多则成千上万字节的。
按 通信所交换的数据量多少进程通信分为低级和高级两种方式。
康振华制作 107
低级通信,在进程间交换数据量少的进程通信方式。
一般只传送一个和几个字节的信息，达到控制进程执行速度的作用（例如进程的同步与互斥）。
信号量机制就是一种低级通信方式，它作为同步工具是卓有成效的，但作为通信工具则不够理想。（?传输效率低。通信对用户不透明）
高级通信,用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。 （?传输效率高。通信过程对用户是透明的）
康振华制作 108
目前，三种基本的进程通信方式：
根据通信实施的方式和数据存取的方式,分为：
=>共享存储器系统 包括 共享内存变量 （ 如信号量机制 ） 和 共享内存区 两种通信方式 。
=>消息传递系统 包括 消息缓冲 和 信箱 两种通信方式 。
=>管道通信方式康振华制作 109
2.7.2 发送和接收原语 ——实现进程通信的基本原语发送原语（ send（接收者进程名，发送区首地址） ）
接收原语（ receive（接收区首地址） ）
send：当要进行消息传递时执行 send
receive：当接收者要接收消息时执行 receive
这是系统提供给用户实现进程通信的最基本的原语，也是构成一种具体的通信系统的主要内容，用户直接使用这些通信原语一次就能发送成千上万字节的信息。
康振华制作 110
2.7.3 消息缓冲通信方式消息（ message）：在计算机网络中又叫报文，指进程之间相互传递的赖以发生相互作用的有结构的数据。
康振华制作 111
2.7.4 信箱通信方式
（只了解定义）
所谓信箱通信方式是指连接两进程之间的一个打开的共享文件,以文件作为缓冲传输介质,一个进程向其写入消息,另一个进程从中读取消息,好象是一个管道,
消息从一头流进,从另一头流出的通信方式 。
康振华制作 112
2.8 *死锁问题 *
——你不让，我也不让在多道程序系统中,多个进程并发运行,共享资源,
从而提高了资源的利用率 。 但是若对资源的管理和使用不当,在一定条件下会导致系统发生一种随机性故障 ―― 死锁 。 在一些系统中,比如实时控制系统,系统一旦发生死锁将导致灾难性的后果 。
死锁问题是 E.W.Dijkstra在 1965年研究银行家算法时首次提出的，以后又由 Havender,Lyach等人研究并发展。
康振华制作 113
2.8.1.死锁的定义
死锁（ Deadlock）,是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于 死锁状态 或 系统产生了死锁 。
称这些永远在互相等待的进程为 死锁进程 。
所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。
计算机系统中,如果系统的资源分配策略不当,或者更常见的是程序员写的程序有错误等,则会导致进程因竞争资源不当 （ 往往与进程的推进速度有关 ） 而产生死锁的现象 。
在计算机系统中有很多独占性的资源，在任一时刻，
它们都只能被一个进程使用。常见的有打印机、磁带驱动器等。例如：两个进程同时打印会引起打印混乱。
鉴于此，操作系统全都具有授权一进程（临时）独占地访问某一种资源的能力。
康振华制作 115
在很多情形中，需要一个进程独占地访问若干种资源而不是一种。
例如,将一个大文件由磁带拷贝至打印机，进程需要同时访问磁带驱动器和打印机，并且不允许其他进程这时访问它们。在只有一个进程的系统中，该进程可以要求任何它所需要的资源，然后进行工作。但是，在一个多道程序系统中，就有可能出现严重的问题。
康振华制作 116
A,B两个进程准备打印一个大的磁带文件
A
B
R1 R2打印机磁带机康振华制作 117
以哲学家就餐问题为例来说明一下死锁：
该问题的描述如下：有 5个哲学家，围坐在圆桌旁，
他们的生活方式是交替地进行思考和进餐；圆桌上间隔地摆放着 5把叉子和 5个装有通心粉的盘子，
规定第 i号哲学家固定坐在第 i把椅子上
（ i=0,1,2,3,4），且每个哲学家必须两手分别拿起他左右两旁的那两把叉子，才能吃通心粉；假定通心粉的数量足够 5个哲学家用的。
假设这 5把叉子与椅子相应也按逆时针方向从 0开始连续编号，即第 i号哲学家左边摆着第 i号叉子，右边摆着第 ((i+1)mod 5)号叉子，这里的
mod代表模运算，即整除取余。
显然，在这个问题中叉子是哲学家进餐竞争的临界资源,5把叉子应分别用一个初值为 1的信号量表示，这 5个信号量构成一个信号量数组 S.
则第 i号哲学家的进餐过程可以描述如下：
哲学家（ I＝ 0,1,2,3,4）
思考；
P(S[i]);
拿起左边的叉子；
P(S[i＋ 1]mod5)；
拿起右边的叉子；
吃通心粉；
放下左边的叉子；
V(S[I]);
放下右边的叉子；
V(S[i＋ 1]mod5)；
下面就是一个不会出现死锁的哲学家进餐过程的算法描述。
哲学家（ I＝ 0,1,2,3,4）
思考；
P(mutex);
P(S[i]);
拿起左边的叉子；
P(S[i＋ 1]mod5)；
拿起右边的叉子；
吃通心粉；
放下左边的叉子；
V(S[i]);
放下右边的叉子；
V(S[i＋ 1]mod5)；
V(mutex)
（ 1） 竞争临界资源当系统中供多个进程共享的临界资源（如打印机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个问题在多道程序系统中是无法解决的。
（ 2） 进程推进顺序不当
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个问题在多道程序系统中是可以解决的。
康振华制作 122
一、竞争资源引起死锁
1,资源的分类：可剥夺和非剥夺性资源
可剥夺性资源,CPU和主存
例如：优先权高的程可以剥夺低优先权进程的处理机 。 又如：内存区可由存储器管理程序把进城从一个存储区移至另外一个存储区,即剥夺了该进城原来占有的存储区,甚至可以将一进程从内存调出到外存上 。
不可剥夺性资源,磁带机、打印机等
当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。
2．竞争非剥夺性资源两个进程分别准备打印一个非常大的磁带文件（ 双方都拥有部分资源，同时在请求对方已占有的资源。）
3,竞争临时性资源永久性资源,打印机资源输入可顺序重复使用的资源 。
临时性资源,由一个进程产生,被另一个进程使用一短暂时间后便无用的资源 。
打印机 R1 磁带机 R2
P1 P2
康振华制作 124
二、进程推进顺序不当引起死锁资源 少也未必一定产生死锁。就如同两个人过独木桥，
如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，
那么问题就解决了。
所以，如果程序设计得不合理，造成进程推进的顺序不当，
也会出现死锁。
康振华制作 125
思考题：（北大 95研）
一个 OS有 20个进程,竞争使用 65个同类资源,申请方式是逐个进行的,一旦某个进程获得它所需要的全部资源,
则立即归还所有资源 。 每个进程最多使用三个资源 。 若仅考虑这类资源,该系统有无可能产生死锁,为什么？
答：不可能 。 因为死锁产生的原因有两点：系统资源不足或推进顺序不当,在本题中,进程所需的最大资源数为 60，
而系统共有该类资源 65个,其资源数已足够系统内各进程使用 。
康振华制作 126
1．互斥条件：
每一资源被分配给 一个进程,或者空闲 。
2,占有并请求条件：
已分配到了一些资源的进程可以申请新的资源 。
3,不可剥夺条件：
进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放 。
4．循环等待条件：
链中的每一个进程都在等待相邻进程所占用的资源。
2.8.3 产生死锁的必要条件康振华制作 127
2.8.4 死锁的解决办法：
① 死锁的预防；
② 死锁的避免；
③ 死锁的检测和恢复；
④ 鸵鸟算法当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。
康振华制作 128
这种办法是在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。
该方法虽然比较保守、资源利用率低，但因简单明了并且安全可靠，仍被广泛采用。
产生死锁的四个必要条件中，互斥条件由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。
一、死锁的防止康振华制作 129
1．静态资源分配法（摒弃,占有并请求条件,）
系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。
此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，
从而破坏了占有与请求条件。
康振华制作 130
静态资源分配法的优缺点：
优点：简单,安全,易实现 。
缺点：
（ 1）资源被严重浪费 （ 因为一个进程一次获得其所需的全部资源并且独占，其中有可能有些资源很少使用，
严重恶化了资源利用率 ）。
（ 2）进程延迟运行。 （ 当且仅当进程获得其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行 ）
康振华制作 131
2．摒弃,不可剥夺条件,
进程在需要资源时才提出请求。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。
实现起来比较复杂，且要付出很大的代价。
进程的周转时间较长，系统开销大。
康振华制作 132
3．有序资源使用法（摒弃,循环等待条件,）
系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为 i的资源，就不允许再申请编号比 i
小的资源了，因此，破坏了循环等待条件。
优点：安全且资源利用率比静态资源分配法有所提高,因为它实际是一种半动态的资源分配法 。
缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象康振华制作 133
二,死锁的避免
死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略,保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态,以避免死锁发生 。
死锁的避免与死锁防止策略不同，它不对进程申请资源加任何限制，而是对进程提出的每一次资源请求进行动态检查，并根据检查结果决定是否分配资源以满足进程的请求。由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法高。
康振华制作 134
(一 )系统的状态
1,安全状态若在某一时刻，系统中存在某种进程序列，如
<P1,P2,…,Pn>，如果系统按此序列为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列
<P1,P2,…,Pn>为安全序列。
安全序列的实质是：序列中的每一个进程 Pi
（ i=1,2,…,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。
康振华制作 135
2.不安全状态
– 若在某一时刻，系统中不存在一个安全序列，
则称系统处于不安全状态。
安全状态的例子例：假定系统有三个进程 P1,P2,P3，共有 12台磁带机。
进程 P1总共要求 10台磁带机,P2和 P3分别要求 4台和九台。设在 T0时刻，进程 P1,P2和 P3已经获得 5台,2
台和 2台，还有 3台空闲没有分配 。
进程 最大需求 已分配 可用
P1 10 5 3
P2
P3
4 2
29
T0时刻系统时安全的。这时存在一个安全序列 <P2,P1,P3>
康振华制作 137
注意：
（ 1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
（ 2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，
而系统处于不安全状态则仅仅可能进入死锁状态。
安全状态不安全状态死锁状态康振华制作 138
银行家算法
银行家算法是最有代表性的避免死锁算法，是 Dijkstra
提出的。 其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。
康振华制作 139
银行家算法的实质就是,
要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。
即：每当进程提出资源请求且系统的资源能够满足该请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。
银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量。
银行家算法中所用的主要的数据结构如下：
(1)可利用资源向量 Available
（ 剩余或可用资源量 ）,记录系统中各类资源的当前可利用数目 。 如果 Available[j]=k,表示系统中现有 Rj类资源
k个 。
(2) 最大需求矩阵 Max
每个进程对各类资源的最大需求量
(3)Allocation
已为每个进程分配的数量或者说每个进程对各类资源当前的占有量 。
(4)需求矩阵 Need
某 进程对各类资源尚需要的数目 。
Need=Max－ Allocation
(5)请求向量 Request
它记录某个进程当前对各类资源的申请量,是银行家算法的入口参数 。
当 Pi发出资源请求后,系统按下述步骤进行检查：
1.如果 Requesti > Needi,则出错 。
2.如果 Requesti>Available,则 Pi 阻塞 ；
3.系统试探把要求的资源分配给进程 Pi,并修改下面数据结构中的数值：
Availablei=Availablei-Requesti;
Allocationi=Allocationi+Requesti;
Needi = Needi- Requesti;
4,系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi等待。
1.设置两个向量
① 工作向量 Work.
表示系统可提供给进程继续运行所需要的各类资源的数目,开始时,Work:=Available。
② Finish.
它表示系统是否有足够的资源分配给进程,使之运行完成 。 开始时先做 Finish[i]:=false；当有足够的资源分配给进程时,令 Finish[i]:=true.
2.执行过程的描述：
(1)初始化,work=available； finish=false；
(2)若按进行编号顺序找到了一个可加入安全序列的进程即：满足条件 finishi=false且 needi≤work 的进程 Pi
则 ① 假设该进程不久将完成任务归还资源,置
work=work+allocationi和 finishi=true
② 重复执行这一步 ；
(3)若所有进程的可完成标志 finish为真,则返回逻辑真值
（ 表示系统处于安全状态 ） ；
(4)否则，返回逻辑假值（表示不安全）；
康振华制作 145
可以看出：
银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，
如果有，也只有极少的系统使用银行家算法来避免死锁。
康振华制作 146
银行家算法之例
假定系统中有四个进程 {P1,P2,P3,P4}和三种类型的资源 {R1,R2,R3}，资源的数量分别为 9,3,6，在 T0
时刻的资源分配情况如图,
资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 1 1 2
P2 6 1 3 5 1 1 1 0 2
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
T0时刻是否安全？
资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 1 1 2
P2 6 1 3 5 1 1 1 0 2
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
资源情况进程
Work
R1 R2 R3
Need
R1 R2 R3
Alloca
R1 R2 R3
Work’
R1 R2 R3
P2 1 1 2 1 0 2 5 1 1 6 2 3
P1 6 2 3 2 2 2 1 0 0 7 2 3
P3 7 2 3 1 0 3 2 1 1 9 3 4
P4 9 3 4 4 2 0 0 0 2 9 3 6
P2发出请求向量 request2（ 1,0,1），系统按银行家算法进行检查：
① request2（ 1,0,1） ≤ need2（ 1,0,2）；
② request2（ 1,0,1） ≤ available（ 1,1,2）；
③系统先假定可为 P2分配资源，并修改 available,allocation2和
need2向量资源情况进程
Max
R1 R2 R3
Allocation
R1 R2 R3
Need
R1 R2 R3
Available
R1 R2 R3
P1 3 2 2 1 0 0 2 2 2 0 1 1
P2 6 1 3 6 1 2 0 0 1
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0
表 2-2 为 P2试分配资源后的有关资源数据康振华制作 149
④ 再利用安全性检测子算法检查此时系统是否安全。如表 2-3所示。
资源进程
Work
R1 R2 R3
Need
R1 R2 R3
Alloca
R1 R2 R3
Work’
R1 R2 R3
P1 0 1 2 0 0 1 6 1 2 6 2 3
P2 6 2 3 2 2 2 1 0 0 7 2 3
P3 7 2 3 1 0 3 2 1 1 9 3 4
P4 9 3 4 4 2 0 0 0 2 9 3 6
Finish
True
True
True
True
康振华制作 150
例 2.9 某系统有同类互斥资源 m个，供 n个进程共享使用。如果每个进程最多申请 x个资源（ 1≤x≤m ），试证明：当 n(x-1)+1≤m 时，系统不会发生死锁。
证明：因为每个进程最多申请 x个资源，所以最坏情况是每个进程都得到了（ x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为 m-n(x-
1)，于是只要系统中至少还有一个资源可供使用，就可以使这 n个进程中某个进程得到其所需要的全部资源，
并能够继续执行到完成，归还资源可供其他进程使用。
因而不会发生死锁。即只要 m-n(x-1)≥ 1时，系统就一定不会发生死锁。亦即当 n(x-1)+1≤m 时，系统不会发生死锁。
康振华制作 151
三、死锁的检测和解除死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。
(1)死锁的检测检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。
由于死锁是系统中的恶性小概率事件，死锁检测程序的多次执行往往都不会调用一次死锁解除程序，而这却增加了系统开销，因此在设计操作系统时需要权衡检测精度与时间开销。
康振华制作 152
2．死锁的解除
常见的死锁解除方法有以下两种,
（ 1） 撤消进程法
撤消全部死锁进程,代价太大,该做法很少用 。
最小代价撤消法,首先计算死锁进程的撤消代价，然后依次选择撤消代价最小的进程，逐个地撤消死锁进程，回收资源给其他进程，直至死锁不复存在。进程的撤消代价往往与进程的优先级、占用处理机的时间等成正比。
康振华制作 153
（ 2）挂起进程法 （剥夺资源）
使用挂起 /激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。
目前挂起法比较受到重视。
显然，无论哪一种解除死锁的方法，都需要很大的开销。但是死锁的检测与解除办法不对系统的资源分配等加任何限制，因此是对付死锁的诸办法中导致资源利用率最高的一种办法，在对安全性要求高的大型系统中常用。
康振华制作 154
2.9 处理机调度
处理机管理需要解决三个主要问题：
（ 1）按什么原则分配处理机，即需要确定处理机调度算法；
（ 2）什么时候分配处理机，即需要确定处理机调度时机；
（ 3）如何分配处理机，即需要给出处理机调度过程。
康振华制作 155
一,调度算法
引入多道程序系统的直接目的就是想让处理机,忙,,一直以来处理机都是计算机系统中的瓶颈资源之一，特别是在单处理机系统中，处于就绪状态的多个进程竞争使用一台处理机，所以当处理机空闲时，系统需要从多个就绪进程中挑选一个使其投入运行。选择哪一个呢？这需要按某一种算法。 调度算法的实质就是一种资源分配 。
从资源的角度来看,该算法确定了处理机的分配策略,故称其为处理机调度算法；
而从资源使用者的角度看，该算法确定了进程运行的次序，
故也称进程调度算法。
康振华制作 156
处理机的使用方式有两种：
不可抢占方式 与 可抢占方式基本的处理机调度算法有先来先服务法、优先级法和时间片轮转法等，现在也有些操作系统使用综合性的调度算法，比如多级反馈队列调度算法等。
康振华制作 157
1．先来先服务调度算法 FCFS
该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程,把处理机分配给它,使之投入运行 。
D C B A CPU 完成康振华制作 158
在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：
进程 到达时刻 服务时间 开始时刻 完成时刻 周转时间 带权周转
A
B
C
D
0
1
2
3
1
100
1
100
0
1
101
102
1
101
102
202
1
100
100
199
1
1
100
1.99
短作业 C的带权周转时间高达 100。
长作业 D的带权周转时间仅为 1.99
康振华制作 159
FCFS算法有利于 CPU繁忙型的作业，不利于 I/O繁忙型的作业。
这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待 CPU的时间较长。即有利于长作业（进程），不利于短作业（进程）。
在当今系统中,先进先出很少作为调度模式,而是常常嵌套在其它的调度模式中 。
例如,许多调度模式根据优先级将处理机分配给进程,但具有相同优先级的进程却按先进先出进行分配 。
康振华制作 160
2．优先级调度算法
总是选择具有 最高优先级 的进程首先使用处理机 。 在这种算法中,首先考虑的问题是如何确定进程的优先数 。 分为,
静态优先权,在创建进程的时候便确定的,且在进程的运行期间保持不变 。 （ 简单易行,系统开销小,但不够精确,很可能出现优先权低的作业 （ 进程 ） 长期不被调度的情况 。 所以,只在要求不太高的系统中,才使用静态优先数 （ 权 ） ）
动态优先权,在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能康振华制作 161
这是一种 可抢占方式 的调度算法，可防止一个长作业长期的垄断处理机。
若所有的进程具有相同的优先权初值，则按照
FCFS算法，最先进入就绪队列的进程最先获得处理机。若所有的就绪进程具有各不相同的优先权初值，对于优先权初值低的进程，在等待足够的时间后，其优先权可能升为最高，从而获得处理机执行。
康振华制作 162
例 2.10 有 5个进程 P1,P2,P3,P4,P5，它们同时依次进入就绪队列，它们的优先数和需要的处理机时间如下：
进程 处理机时间 优先数
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
康振华制作 163
忽略进程调度所花的时间，要求：
（ 1） 分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；
（ 2） 分别计算各进程在就绪队列中的等待时间和平均等待时间 。
解,（ 1） 采用先来先服务调度算法时各进程的执行次序为,P1→ P2→ P3→ P4→ P5。
采用静态优先级调度算法时各进程的执行次序为：
P4→ P1→ P3→ P5→ P2。
康振华制作 164
（ 2） FCFS中，平均等待时间＝（ 0+10+11+13+14） /5＝ 9.6；
静态优先级法中，平均等待时间＝（ 1+18+11+0+13） /5＝ 8.6
进程 处理机时间 FCFS等待时间 静态优先级法等待时间
P1 10 0 1
P2 1 10 18
P3 2 11 11
P4 1 13 0
P5 5 14 13
康振华制作 165
3.最短作业 /进程优先法（ SJF/SPF）
SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。
SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。
非抢占式。
缺点：没有考虑到某些作业 /进程的紧迫程度。
用户作出的估计时间并不准确，带有很大的主观性。
康振华制作 166
4.最高响应比作业优先算法（ HRN）
是对 FCFS方式和 SJF方式的一种综合平衡响应比。
R＝ (作业等待时间＋需运行时间 )/ 需运行时间
＝ 1＋已等待时间 / 需运行时间
＝ 1＋ W/T
由于 R与要求运行时间成反比，故对短作业是有利的，
另一方面，因 R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的相应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。
康振华制作 167
5．时间片轮转调度算法 (RR)
基本思想,系统把所有的就绪进程按 FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首的进程使用,当该进程的时间片用完以后，
系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度。 同时处理机调度程序又去调度当前就绪队列的 队首进程,也让它运行给定的时间片，如此循环往复。
F C B A…,CPU 完成
A
B
C
时间片轮转算法图示
这就使得就绪队列中所有的进程，都能在一有限的时间内，轮流获得一个时间片的执行时间。
康振华制作 169
最佳时间片的确定这个最佳的时间片值是多少呢？ 显然,它将随系统而异 。 随负载而异,同时也随进程而异 。
时间片的选取是实现各种调度算法的关键之处,而时间片的选定通常应考虑终端数目,处理机能力,各终端任务的急迫程度,外存传输速度等方面的因素 。 时间片轮转法亦可应用于批处理系统的处理机调度 。
① 当时间片很大时,大到一个进程足以完成其全部运行工作所需的时间,此时轮转调度模式退化为 FCFS模式 。
② 当时间片非常小时,调度程序剥夺处理机的次数增多,这将加重了系统开销,系统性能降低,大多数时间都消耗在处理机的转换上 。
康振华制作 170
6．多级反馈队列调度算法
以上介绍的算法,都存在一定的局限性 。
现在主流的操作系统，如 UNIX,Windows
NT,Linux等，都使用一种综合性的调度算法 ——多级反馈队列调度算法。该算法综合了上述三种算法以及多队列调度算法的思想和优点，总体调度性能优越，适于各种类型的作业，
但其实现也比较复杂。
康振华制作 171
算法的基本思想（实施过程）是,
首先,系统按进程优先级设置了多级 （ 比如 n级,n≥2） 就绪进程队列,从第一级队列到最后一级队列,优先级越来越低 。
其次,每一级就绪队列对应一个不同的时间片 。 优先权越高的队列,进程的时间片越小 。
再次,当一个新进程进入内存后,首先被放到第一级队列的队尾 。 按照 FCFS原则排队等待调度 。 当轮到该进程执行时,如能在时间片内完成,便可准备撤离系统；如果在时间片内未完成,调度程序便将该进程转入第二队列的末尾,再依次按照
FCFS原则等待调度 。
康振华制作 172
最后,仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的 n-1级队列全部为空时，才去调度最后第 n级队列中的进程。如果处理机正在第 I队列中为某进程服务时，又有新的进程进入优先权高的队列（第 1～ I-1中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第 i队列的队尾，重新进行处理机调度。
康振华制作 173
二,调度时机
当发生以下几种情况时,现行进程都要放弃处理机的使用,即将引起系统对进程的重新调度：
1,在分时系统中,现行进程的时间片用完了；
2,发生了外部中断；
3,进程因等待某事件或资源而阻塞；
4．现行进程运行结束或出现异常情况。
康振华制作 174
三,调度过程
1,保存,下降,进程现场
2．选择将要运行的进程 ——“上升,进程
3．恢复,上升,进程的现场康振华制作 175
2.10 线程 (Thread)的概念
自 20世纪 60年代提出进程概念后，在操作系统中一直以进程作为能独立运行的基本单位。直到 20世纪 80年代中期，人们为了减少程序并发执行时的时空开销（如进程创建、切换和通信开销），进一步提高程序的并发执行程度，进而提高系统的吞吐量，提出了比进程更小的能独立运行的基本单位 ——线程。
康振华制作 176
回顾进程的两个基本属性：
1.进程是一个可拥有资源的独立单位；
2.进程又是一个可独立调度和分配的基本单位 。 合起来,
进程便成为一个能独立运行的基本单位,从而构成了程序并发执行的基础 。
简言之,由于进程是一个资源的拥有者,在执行这些操作时会付出较大的时间开销 。 因此在系统中所设的进程数目不宜过多,切换不宜过于频繁,这就限制了系统的并发程度 。
康振华制作 177
一,线程的定义
定义,线程是进程中的一个实体，是被系统独立调度和分配的基本单位，故又称为轻型（轻权）进程 (Light Weight Process)，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。
传统的进程称为重型进程 (Heavy Weight
Process)。
康振华制作 178
线程是进程中可独立执行的子任务，是系统独立调度和分派的基本单位。
一个进程中至少有一个线程。线程继承所属进程的一切资源，它自己只拥有运行所需的很少的一点资源，
如几个寄存器和一个堆栈等。因此，一个进程内的几个线程之间的切换的开销比进程间切换的开销小得多，
这是系统引入线程可以提高效率和并发性的主要原因。
康振华制作 179
二,线程与进程的比较
1．拥有资源方面进程都是拥有资源的一个独立单位，它可以拥有自己的资源。
而线程几乎不拥有系统资源,但它可以访问其隶属进程的资源
2．可调度性
以进程为单位进行处理机切换和调度时，处理机切换时间长，
资源利用率降低。以线程为单位进行进行处理机切换和调度时，
由于不发生资源变化，特别是地址空间的变化，处理机切换时间较短，从而处理机效率较高。
康振华制作 180
3．并发性在引入线程的操作系统，不仅进程之间可以并发执行，而且线程之间也可并发执行，因而使操作系统具有更好的并发性，从而能更有效地利用系统资源，提高系统的吞吐量。
4．系统开销由于在创建或撤消进程时，系统要为之分配或回收资源，如内存空间,I/O设备等，所以操作系统创建进程的开销远大于创建线程的开销。类似地，操作系统为进程切换付出的开销也远大于为同一进程内的线程切换付出的开销。另外，由于同一进程内的多个线程具有相同的地址空间，致使它们之间的同步与互斥的实现，也变得比较容易。
康振华制作 181
进程的调度,同步等由 OS内核完成,而线程的控制既可以由 OS内核进行,也可以由用户控制 。
5．系统感知方面康振华制作 182
三,线程的适用范围线程特别适合于共享存储的 多处理机系统 和 C/S模型，成功例子很多，如文件服务器,WWW浏览器等，以下是几种典型的应用：
1,服务器中的文件管理和进程通信控制；
2,前后台处理；
3,异步处理；
4,数据的批处理；
5,网络系统中信息发送和接受
……
