第 2章 处理器管理
2.1 处理器管理概述
2.2 进程描述
2.3 进程控制
2.4 进程同步与互斥
2.5 进程通信
2.6 进程调度
2.7 进程死锁
2.8 线程、超线程和双核的基本概念本章结束！
2.1 处理器管理概述
2.1.1 处理器管理的功能处理器管理的主要任务是对处理器进行分配，并对其运行进行有效的控制和管理。
在现代操作系统中，处理器的分配和运行都是以进程为基本单位的，因而对处理器的管理也可以视为对进程的管理。
进程是程序的一次执行过程。
处理器管理包括以下功能：
1,进程控制。 在并发运行环境中，要使程序运行，必须先为它创建一个或几个进程，并给它分配必要的资源。程序运行结束时，要撤消这些进程，并回收这些进程所占用的各类资源。
进程控制的主要任务就是为程序创建进程，撤消已结束的进程，以及控制进程在运行过程中的状态转换。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
2,进程同步。 在并发环境中，进程是以异步方式工作的，并且以不可预知的速度向前推进。为了使多个进程能有条不紊地运行，系统中必须设臵进程同步机制。
进程同步的主要任务是对众多的进程运行进行协调。协调方式有两种：
(1) 进程互斥方式。 进程在对临界资源访问时，应采用互斥方式，也就是当一个进程访问临界资源时，另一个要访问该临界资源的进程必须等待；当获取临界资源的进程释放临界资源后，其他进程才能获取临界资源。这种进程之间的相互制约关系称为互斥。
简单地说,互斥 就是“有我就没你，有你就没我”。
临界资源 是指一次只能被一个进程使用的资源。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
2,进程同步。
(2) 进程同步方式。 相互合作的进程，由同步机构对它们的执行次序加以协调。也就是前一个进程结束，后一个进程才能开始；
前一个进程没有结束，后一个进程就不能开始。这种进程之间的相互合作关系称为同步。
简单地说,同步 就是“有你才有我，没你就没我”。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
3,进程通信。 在系统中，经常会有多个进程需要相互配合去完成一个共同的任务，而在这些进程之间，往往需要相互交换信息。进程通信的任务就是用来实现相互合作进程之间的信息交换。
进程的通信方式有：
（ 1）当相互合作的进程处于同一台计算机系统时，通常采用直接通信方式。 由源进程利用发送命令直接将消息发送到目标进程的消息队列上，然后由目标进程利用接收命令从其消息队列中取出消息。
（ 2）当相互合作的进程处于不同计算机系统时，通常采用 间接通信方式。 由源进程利用发送命令将信息发送到一个专门存放消息的中间实体中，然后由目标进程利用接收命令从中间实体中取出消息。这个中间实体通常称为“邮箱”，相应的通信系统称为电子邮件系统。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
4,处理器调度。 等待在后备队列上的作业，通常要经过处理器调度才能执行。处理器调度包括作业调度（也称为高级调度）、
进程调度（也称为低级调度）和中级调度。
(1)作业调度 的基本任务是从后备队列中按照一定的算法，选择出若干个作业，为它们分配必要的资源，将它们调入主存，然后为它们建立进程，使之成为可能获得处理器的就绪进程，并按照一定的算法将其插入到就绪队列。作业调度将在第 6章作业管理与系统接口中介绍。
(2)进程调度 的基本任务是从进程的就绪队列中，按照一定的调度算法选出一个进程，把处理器分配给它，并为它设臵运行现场，使进程投入运行。本章主要介绍进程调度。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理 的功能
4,进程调度。
（ 3）中级调度 的基本任务是把那些暂时不能运行的进程从主存移到外存上，释放其所占有的宝贵资源，让其他进程运行。当移到外存上的进程具备运行条件时，再由中级调度把它们重新调入主存，等待运行。
中级调度将在第 3章存储器管理的对换技术中详细介绍，也可以参考本章 2.2.4的内容。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行程序执行 是指程序在计算机中的运行过程。程序的执行可以用前趋图表示，程序的执行方式有顺序执行和并发执行。
1.前趋图。 它是一个有向无循环图。图中的每个结点可用于表示一条语句、一个程序段等；结点间的有向边表示在两个结点之间存在的前趋关系。如 Pi → Pj,称 Pi
是 Pj的前趋，而 Pj是 Pi的后继。
在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。应当注意的是，前趋图中不能存在循环。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
1.前趋图。 图 2-1所示的前趋图。 在图 2-1所示的前趋图中存在下述前趋关系：
P1 → P2,P1 → P3,P2 → P5,P3 → P4,P4 → P5,P5
→ P6
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
2.程序的顺序执行 。 程序在执行时，必须按照某种先后次序逐个执行操作，只有当前一个操作执行完后，才能执行后一个操作。例如：在进行计算时，总是先输入需要的数据，然后才能进行计算，计算完成后再将结果输出。
如果用 I代表输入,C代表计算,P代表打印，则上述情况可用图 2-2所示的前趋图表示。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
2.程序的顺序执行 。
程序的顺序执行通常表现出如下特征：
– 顺序性。 严格按照程序所规定的顺序执行。
– 封闭性。 程序在封闭的环境下执行。程序在运行时独占所有资源，其执行结果不受外界因素的影响。
– 可再现性。 只要程序执行的环境和初始条件相同，程序无论重复执行多少次，按照何种方式执行，都将获得相同的结果。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。 是指在一个时间段内执行多个程序。
程序在并发执行的特征：
–间断性。 在程序并发执行时，由于它们之间共享资源或相互合作，致使它们之间形成了相互制约的关系，导致并发程序在执行中因为受到影响，表现为“执行 —暂停执行 —执行”的间断性活动规律。
–失去封闭性。 程序并发执行时，多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，程序在执行时，必然会受到其他程序的影响。
–不可再现性。 由于程序执行时失去了封闭性，也将导致失去可再现性。既使并发程序执行的环境和初始条件相同，程序的多次执行或以不同的方式执行，可能获得不相同的结果。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
【 例 2-1】 程序 A和程序 B为并发执行，它们共享变量 M，假设 M初值为 3；程序 A执行 M=M+1；程序 B执行 print M； M=1。程序 A和程序 B执行的顺序若不相同,M的结果将产生不同的变化。
顺序 1,M = M +1； print M； M = 1。 M值依次为 4,4,1。
顺序 2,print M； M = M +1； M = 1。 M值依次为 3,4,1。
顺序 3,print M； M = 1； M = M +1。 M值依次为 3,1,2。
按照顺序 1执行,M的输出结果为 4；按照顺序 2执行,M的输出结果为 3；按照顺序 3执行,M的输出结果为 3。所以，当执行的条件不同时，并发程序有可能产生不同的执行顺序，也就会得到不同的执行结果。这样并发程序就形成了结果的不可再现性。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。 判断程序并发执行的方法有两种：
Bernstein条件和前趋图。
（ 1） Bernstein条件。 即不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）
可以并发执行。运算的读集是指在运算执行期间引用的所有变量的集合，运算的写集是指在运算执行期间要改变的所有变量的集合。例如运算 w=x+y，其读集是 {x,y}，其写集是 {w}。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
（ 1） Bernstein条件。
【 例 2-2】 有四条语句，哪些语句可以并发执行？
s1,a=x+y; s2,b=z+1;
s3,c=a-b; s4,d=c+1;
【 解 】 要先确定运算，然后写出每个运算的读集与写集，最后两两判断运算的读集与写集，写集与写集的交集的并集是否是空集；
若是，则可以并发，若不是空集，则不能并发。
对于本题，四条语句的读集与写集分别是：
读集,R(s1)={x,y},R(s2)={z},R(s3)={a,b},R(s4)={c}；
写集,W(s1)={a},W(s2)={b},W(s3)={c},W(s4)={d}。
由 Bernstein条件可知 s1与 s2可以并发执行,s1与 s3,s2与 s3，
s3与 s4不能并发执行。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
（ 2）利用前趋图。 画出程序执行的前趋图，根据该程序或运算在前趋图中的位臵关系，可以判断其能否并发执行。即在程序或运算的先后顺序上，只有前后相邻的程序或运算不能并发执行，其余程序和运算都可以并发执行。
【 例 2-3】 已知一个求值公式 (a2+3b)/(b+5a)，若 a,b已赋值，试画出该公式求值过程的前趋图，并判断哪些求值过程可以并发执行。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
【 解 】 把公式 (a2+3b)/(b+5a)按照运算顺序分解，可以产生如下运算步骤,s1～ s6，如图 2-4（ a）所示；根据分解的运算顺序画出它的前趋图，如图 2-4（ b）所示。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
根据前趋图，可以看出能够并发执行的运算是：
s1与 s2,s1与 s3,s2与 s3,s1与 s5,s2与 s5,s3
与 s4,s4与 s5，其余运算不能并发执行。
第 2章 处理器管理返回
2.2 进程描述
2.2.1 进程的概念
1．进程的定义。
“进程”这一术语，在 20世纪 60年代初期，首先出现在麻省理工学院的 MULTICS系统和 IBM公司的 CTSS/360系统中。其后，
人们对它不断加以改进，从不同的方面对它进行描述。关于进程的定义有以下一些描述：
进程是程序的一次执行。
进程可以定义为一个数据结构及能在其上进行操作的一个程序。
进程 是程序在一个数据集合上的运行过程，是系统资源分配和调度的一个独立单位。
第 2章 处理器管理
2.2 进程描述
2.2.1 进程的概念
2．进程的特征。 进程的五个基本特征：
（ 1）动态性。 进程的动态性是进程的最基本特征，它表现为“进程因创建而产生，因调度而执行，因得不到资源而暂停，以及因撤消而消亡”。因此，进程具有一定的生命周期，其状态也会不断发生变化，是一个动态实体。
（ 2）并发性。 进程的并发性是指多个进程在一段时间内同时运行，
交替使用处理器的情况。并发性是进程也是操作系统的重要特征。
（ 3）独立性。 进程的独立性是指进程实体是一个能独立运行的基本单位，同时也是独立获得资源和独立调度的基本单位。没有创建进程的程序，是不能参加运行的。
（ 4）异步性。 进程的异步性是指系统中的进程按照各自独立的、
不可预知的速度向前推进，即进程按照异步方式运行。
（ 5）结构性。 进程的结构性是指在结构上进程实体由程序段、数据段和进程控制块组成，这三部分也统称为“进程映像”。
第 2章 处理器管理
2.2 进程描述
2.2.1 进程的概念
2．进程的特征。
举一个例子来说明程序和进程。例如从北京西站发往长沙的
T1次列车，它有自己的运行步骤：始发时间、站台，中间停靠的车站及停靠时间，到达终点站的时间等，这相当于一个程序。
而 2007年 3月 18日从北京西站发往长沙的 T1次列车就相当于一个进程，它是一个过程,15:00从北京西站出发，第二天 6:10到达长沙结束。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
1．进程关系。 进程关系主要是指进程间执行的次序关系 。在并发环境下，进程关系有三种：
（ 1）串行。 一个进程结束，下一个进程才能开始。这两个进程的关系就是串行关系。
（ 2）并行。 多个进程可以同时开始，同时结束。这几个进程之间的关系就是并行关系。
（ 3）嵌套。 在串行中包含并行，在并行中也包含串行。这种进程间的关系就是嵌套关系。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 1）图示法。 可以采用前趋图和进程流图表示。前趋图的表示已经在上一节讲过，这里不再赘述。进程流图使用的图素有：带圈的,S”表示开始，带圈的,F”表示结束，有向线段表示进程。进程的三种关系如图 2-5所示。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 2）数学法。 就是利用数学函数来表示进程关系。“串行”使用串行函数表示,S（ p1,…,pn）。其中函数名,S”表示串行，
函数参数,p1,…,pn”表示进程，中间用逗号分隔。“并行”
使用并行函数表示,P（ p1,…,pn） 。其中函数名,P”表示并行，函数参数,p1,…,pn”表示进程，中间用逗号分隔。“嵌套”使用串行函数和并行函数的组合表示。
图 2-5中的嵌套关系可以表示为：
S（ p1,P（ p2,S（ p3,P（ p5,p6））,p4）,P（ p7，
p8））。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 3）程序法。 以 cobegin和 coend结构指明并行，其格式为：
cobegin p1 ; p2 ; … ; pn coend 或 cobegin p1 // p2 // … // pn
coend
其中 pi为进程或一块代码或函数。函数间用“；”分隔表示串行，
用,//”分隔表示并行。
图 2-5中的进程关系用程序法表示为：
串行,cobegin p1 ; p2 ; p3 ; p4 coend
并行,cobegin p1 // p2 // p3 // p4 coend
嵌套,cobegin
p1 ; {p2 // {p3 ; p5//p6 }// p4} ; {p7//p8}
coend
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
1．进程的三种基本状态
（ 1）就绪状态。 当进程已分配到除处理器（ CPU）以外的所有必要资源后，只要再获得处理器就可以执行的状态称为就绪状态。
在一个系统里，可以有多个进程同时处于就绪状态，通常把这些就绪进程排成一个或多个队列，称为就绪队列。
（ 2）执行状态。 处于就绪状态的进程一旦获得了处理器，就可以运行，进程状态也就处于执行状态。在单处理器系统中，只能有一个进程处于执行状态。在多处理器系统中，可能有多个进程处于执行状态。
（ 3）阻塞状态。 正在执行的进程因为发生某些事件（如请求输入 /
输出、申请额外空间等）而暂停运行，这种受阻暂停的状态称为阻塞状态，也可以称为等待状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。在有些系统中，也会按照阻塞原因的不同将处于阻塞状态的进程排成多个队列。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
2．进程的其他两种状态
（ 1）新状态。 当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新状态。
（ 2）终止状态。 当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但是，尚未撤消，这时称为终止状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
（ 1）新状态 → 就绪状态。 当就绪队列能够接纳新的进程时，操作系统就会把处于新状态的进程移入就绪队列，此时进程就从新状态转变为就绪状态。
（ 2）就绪状态 → 执行状态。 处于就绪状态的进程，当进程调度程序按照一定的算法为之分配了处理器后，该进程就可以获得执行，
从而使进程状态由就绪状态变为执行状态。处于执行状态的进程也称为当前进程。
（ 3）执行状态 → 阻塞状态。 正在执行的进程因为自身需求发生某种事件（如 I/O请求或等待某一资源等）而无法继续执行时，只好暂停执行，此时进程就由执行状态转变为阻塞状态。
（ 4）执行状态 → 就绪状态。 正在执行的进程，如果因系统分配给的时间片结束或优先权较低，而暂停执行时，该进程将会从执行状态转变为就绪状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
（ 5）阻塞状态 → 就绪状态。 处于阻塞队列中的进程，如果需要的资源得到满足或完成输入输出响应，就会变为就绪状态，进入就绪队列，等待下一次调度。
（ 6）执行状态 → 终止状态。 当一个进程正常结束或出现异常错误结束时，进程将由执行状态转变为终止状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
图 2-6给出了具有五种基本状态的进程状态转换图。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
1．进程挂起状态的引入。
（ 1）用户的需求。 当用户在进程运行期间，发现有可疑问题时，
希望进程暂时停止下来，但是，并不终止进程。若进程处于执行状态，则暂停执行；若进程处于就绪状态，则暂时不接受调度，
以便研究进程执行情况或对程序进行修改。这种静止状态称为挂起状态。
（ 2）父进程的需求。 父进程往往希望考查和修改子进程，或者协调各个子进程之间的活动，此时需要挂起自己的子进程。
（ 3）操作系统的需求。 操作系统有时需要挂起某些进程，然后检查系统中资源的使用情况，进行记账控制，以便改善系统运行的性能。
（ 4）对换的需求。 为了缓和主存与系统其他资源的紧张情况，并且提高系统性能，有些系统希望将处于阻塞状态的进程从主存换到外存。而换到外存的进程，当等待的事件完成，它仍然不具备执行的条件，不能进入就绪队列，所以需要一个有别于阻塞状态的新状态来表示，即挂起状态。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
2．引入进程挂起状态后进程状态的转换。
（ 1）执行状态 → 静止就绪。 正在执行的进程，如果用挂起原语将该进程挂起后，此时进程就暂停执行，转变为静止就绪状态。
（ 2）静止就绪 → 活动就绪。 处于静止就绪状态的进程，若用激活原语将该进程激活后，进程状态就由静止就绪状态变为活动就绪状态，激活后的进程就可以被调度执行了。
（ 3）活动就绪 → 静止就绪。 当进程处于未被挂起的就绪状态时，
称之为活动就绪状态，在用挂起原语将该进程挂起后，此时进程就转变为静止就绪状态。处于静止就绪状态的进程，不能再被调度执行。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
2．引入进程挂起状态后进程状态的转换。
（ 4）活动阻塞 → 静止阻塞。 当进程处于未被挂起的阻塞状态时，
称之为活动阻塞状态。在用挂起原语将该进程挂起后，此时进程就转变为静止阻塞状态。
（ 5）静止阻塞 → 活动阻塞。 处于静止阻塞状态的进程，若用激活原语将该进程激活，进程状态就由静止阻塞状态变为活动阻塞状态。
（ 6）静止阻塞 → 静止就绪。 处于静止阻塞状态的进程，在其所需要的资源满足或完成等待的事件后，就会变为静止就绪状态。
第 2章 处理器管理返回
2.3 进程控制
2.3.1 进程控制块 PCB
1,进程控制块的概念。 进程控制块 PCB（ Process Control Block）
是进程实体的重要组成部分，是操作系统中最重要的记录型数据。
在进程控制块中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息。通过 PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，
一个能够并发执行的进程。换句话说，在进程的整个生命周期中，
操作系统都要通过进程的 PCB来对并发执行的进程进行管理和控制。
由此看来，进程控制块是系统对进程控制采用的数据结构。
系统是根据进程的 PCB而感知进程存在的。所以,进程控制块是进程存在的惟一标志。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
2,进程控制块的内容。 进程控制块主要包括下述四个方面的信息。
如图 2-8所示。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
2,进程控制块的内容。
（ 1）进程标识信息。 进程标识符用于标识一个进程，通常有外部标识符和内部标识符两种。
（ 2）说明信息（进程调度信息）。 说明信息是与进程调度有关的状态信息,进程状态、优先级、阻塞原因等。
（ 3）现场信息（处理器状态信息）。 现场信息是用于保留进程存放在处理器中的各种信息，主要由处理器中的各个寄存器的内容组成。
（ 4）管理信息（进程控制信息）。 管理信息包括进程资源、控制机制等一些进程执行所需要的信息,程序和数据的地址、进程同步和通信机制,资源清单,链接指针等。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
3,进程控制块的组织方式。
（ 1）链接方式。 把具有相同状态的 PCB，用链接指针链接成队列，
如就绪队列、阻塞队列和空闲队列等。图 2-9给出了一种 PCB链接队列的组织方式。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
3,进程控制块的组织方式。
（ 2）索引方式。 系统根据各个进程的状态，建立不同索引表，例如就绪索引表、阻塞索引表等。并把各个索引表在主存的首地址记录在主存中的专用单元里，也可以称为表指针。在每个索引表的表目中，记录着具有相同状态的各个 PCB在表中的地址。图 2-
10给出了 PCB组织的索引方式。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
4,进程控制原语。
原语 是指具有特定功能的不可被中断的过程。它主要用于实现操作系统的一些专门控制操作。用于进程控制的原语有：
（ 1）创建原语。 用于为一个进程分配工作区和建立 PCB，臵该进程为就绪状态。
（ 2）撤消原语。 用于一个进程工作完后，收回它的工作区和 PCB。
（ 3）阻塞原语。 用于进程在运行过程中发生等待事件时，把进程的状态改为阻塞状态。
（ 4）唤醒原语。 用于当进程等待的事件结束时，把进程的状态改为就绪状态。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销在系统中，只有进程才能得到运行。因此，程序想要执行，
就必须为之创建进程。进程执行结束，就必须撤消它。
1,进程的创建。
（ 1）引起进程创建的事件。 引起进程创建的事件有以下四类：
–用户登录。
–作业调度。
–提供服务。
–应用请求。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
1,进程的创建。
（ 2）进程创建的过程。 一旦操作系统发现了要求创建进程的事件后，便调用进程创建原语，按照下列步骤创建一个新进程。
① 为新进程分配惟一的进程标识符，并从 PCB队列中申请一个空闲的 PCB。
② 为新进程的程序和数据，以及用户栈分配相应的主存空间及其他必要的资源。
③ 初始化 PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。
④ 如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
2,进程的撤销。
（ 1）引起进程撤消的事件。 引起进程撤消的事件有三类：
–进程正常结束。
–在进程运行期间，由于出现某些错误和故障而使进程被迫中止。
–进程应外界的请求而终止运行。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
2,进程的撤销。
（ 2）进程撤消的过程。 一旦操作系统发现了要求终止进程的事件后，便调用进程终止原语，按照下列步骤终止指定的进程。
① 根据被终止进程的标识符，从 PCB集合中检索该进程的
PCB，读出进程状态。
② 若该进程处于执行状态，则立即终止该进程的执行。
③ 若该进程有子孙进程，还要将其子孙进程终止。
④ 将该进程所占用的资源回收，归还给父进程或操作系统。
⑤ 将被终止进程的 PCB从所在队列中移出，撤消该进程的
PCB，并将其加入到空闲的 PCB队列中。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
1,进程的阻塞。
（ 1）引起进程阻塞的事件。 引起进程阻塞的事件有四类：
–请求系统服务。
–启动某种操作。
–新数据尚未到达。
–无新工作可做。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
1,进程的阻塞。
（ 2）进程阻塞的过程。 一旦操作系统发现了要求阻塞进程的事件后，便调用进程阻塞原语，按照下列步骤阻塞指定的进程。
① 立即停止执行该进程。
② 修改进程控制块中的相关信息。把进程控制块中的运行状态由“执行”状态改为“阻塞”状态，并填入阻塞的原因，以及进程的各种状态信息。
③ 把进程控制块插入到阻塞队列。根据阻塞队列的组织方式，
把阻塞进程的进程控制块插入阻塞队列中。
④ 转调度程序重新调度，运行就绪队列中的其他进程。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
2,进程的唤醒。
（ 1）引起进程唤醒的事件。 引起进程唤醒的事件有四类：
–请求系统服务得到满足。
–启动某种操作完成。
–新数据已经到达。
–有新工作可做。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
2,进程的唤醒。
（ 2）进程唤醒的过程。 一旦操作系统发现了要求唤醒进程的事件后，便调用进程唤醒原语，按照下列步骤唤醒指定的进程。
① 从阻塞队列中找到该进程。
② 修改该进程控制块中的相关内容，把阻塞状态改为就绪状态，删除阻塞原因等。
③ 把进程控制块插入到就绪队列中。按照就绪队列的组织方式，把被唤醒的进程的进程控制块插入到就绪队列中。
第 2章 处理器管理返回
2.4 进程的同步与互斥
2.4.1 进程的并发性并发进程相互之间可能没有关系，也可能存在某种关系。如果进程间彼此毫无关系，互不影响，这种情况不会对系统产生什么影响，通常不是要研究的对象。如果进程间彼此相关，互相影响，那么就需要进行合理的控制和协调才能正确执行。进程间的关系可以分为：
（ 1）资源共享关系。 系统中的某些进程需要访问共同的资源，即当一个进程访问共享资源时，访问该共享资源的其他进程必须等待，当这个进程使用完后，其他进程才能使用。这时要求进程应互斥地访问共享资源。
（ 2）相互合作关系。 系统中的某些进程之间存在相互合作的关系，
即一个进程执行完后，另一个进程才能开始。否则，另一个进程不能开始。这时就要保证相互合作的进程在执行次序上要同步。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
1．进程同步与互斥的定义对于相关进程间的同步和互斥，必须进行有效的控制。这种控制涉及几个基本概念，即临界资源、临界区、进程同步和进程互斥的概念。
（ 1）临界资源。 在系统中有许多硬件或软件资源，如打印机、公共变量等，这些资源在一段时间内只允许一个进程访问或使用，
这种资源称为临界资源。
（ 2）临界区。 作为临界资源，不论是硬件临界资源，还是软件临界资源，多个并发进程都必须互斥地访问或使用，这时把每个进程中访问临界资源的那段代码称为临界区。而这些并发进程中涉及临界资源访问的那些程序段称为相关临界区。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
1．进程同步与互斥的定义
（ 3）进程同步。 进程同步是指多个相关进程在执行次序上的协调，
这些进程相互合作，在一些关键点上需要相互等待或相互通信。
通过临界区可以协调进程间相互合作的关系，这就是进程同步。
（ 4）进程互斥。 进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待。当占用临界资源的进程退出临界区后，另一个进程才被允许使用临界资源。通过临界区协调进程间资源共享的关系，就是进程互斥。进程互斥是同步的一种特例。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
2．进程同步机制应遵循的原则
（ 1）空闲让进。 当无进程处于临界区时，临界资源处于空闲状态，
可以允许一个请求进入临界区的进程进入自己的临界区，有效地使用临界资源。
（ 2）忙则等待。 当已有进程进入自己的临界区时，意味着临界资源正被访问，因而其他试图进入临界区的进程必须等待，以保证进程互斥地使用临界资源。
（ 3）有限等待。 对要求访问临界资源的进程，应保证该进程在有效的时间内进入自己的临界区，以免陷入“死等”状态。
（ 4）让权等待。 当进程不能进入自己的临界区时，应立即释放处理器，以免陷入“忙等”。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
3．利用锁机制实现同步在众多的进程同步机制中，锁机制是一种最简单的机制。
（ 1）锁的概念。 在同步机制中，常用一个变量来代表临界资源的状态，称它为锁。通常用,0”表示资源可用，相当于锁打开。用
,1”表示资源已被占用，相当于锁闭合。锁机制的描述，如图 2-12
所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
3．利用锁机制实现同步
（ 2）对锁的操作。 对锁的操作有两种，一种是关锁操作，另一种是解锁操作。
关锁操作：
lock（ w）
{
test,if （ w==1） goto test；
else w=1；
}
解锁操作：
unlock(w)
{
w=0；
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 1）信号量的概念。 1965年，荷兰学者 Dijkstra提出的信号量机制是一种很有效的进程同步工具，得到了广泛的使用。这里将介绍最简单的经常使用的信号量 ——整型信号量。
信号量是一种特殊变量，它用来表示系统中资源的使用情况。
而整型信号量就是一个整型变量。当其值大于,0”时，表示系统中对应可用资源的数目；当其值小于,0”时，其绝对值表示因该类资源而被阻塞的进程的数目；当其值等于,0”时，表示系统中对应资源已经用完，并且没有因该类资源而被阻塞的进程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 2）对信号量的操作对于整型信号量，仅能通过两个标准的原语操作来访问，这两个操作被称为 P操作,V操作，也合称为 PV操作。其中 P操作在进入临界区前执行,V操作在退出临界区后执行。 PV操作如图 2-
13所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 2）对信号量的操作
① P操作：记为 P(S)，其中 S为信号量，描述为：
P(S)
{ S=S-1;
if (S<0) W(S);
}
② V操作：记为 V(S)，其中 S为信号量，描述为：
V(S)
{ S=S+1;
if (S<=0) R(S);
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥进程互斥的原因是竞争临界资源。所以，实现进程互斥的关键是要描述临界资源的使用情况。若临界资源没有被占用，则允许进程访问，否则不允许进程访问，让该进程入阻塞队列。
【 例 2-4】 在一个只允许单向行驶的十字路口，分别有若干辆由东向西，由南向北的车辆等待通过。为了安全每次只允许一辆车通过。当有车辆通过时，其他车辆必须等候。当无车辆在路口行驶时，则允许一辆车通过。请用 PV操作设计一个十字路口安全行驶的自动管理系统。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 通过十字路口的车辆没有必然的先后次序，所以这是一个明显的互斥问题。十字路口即为临界资源，要求车辆每次最多通过一辆。由东向西，由南向北行驶的车辆为两个进程。
设互斥信号量 S表示临界资源十字路口，其初值为,1”表示十字路口可用。
算法描述如下：
int S = 1;
cobegin
Pew() /* 由东向西行驶车辆 */
//Psn() /* 由南向北行驶车辆 */
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
Pew()
{
P(S);
由东向西通过十字路口；
V(S);
}
Psn()
{
P(S);
由南向北通过十字路口；
V(S);
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-5】 有 4位哲学家围着一个圆桌在讨论问题和进餐，在讨论时每人手中什么都不拿，当需要进餐时，每人需要用刀和叉各一把。餐桌上的布臵如图 2-14所示，共有两把刀和两把叉，每把刀或叉供相邻的两个人使用。请用信号量及 PV操作说明 4位哲学家的同步过程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 分析：因哲学家就餐没有必然的先后次序，相邻的两个哲学家要竞争刀或叉，刀或叉就成为了临界资源，所以本题属于互斥问题。
解题步骤：（ 1）确定进程的个数及其工作内容。本题涉及 4个进程，每个哲学家为一个进程。哲学家 A的工作流程如图 2-
15所示。其他哲学家的工作流程与哲学家 A相似，只是拿起刀叉的序号不同。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定互斥信号量的个数、含义及 PV操作。在本题中应设臵 4
个互斥信号量 fork1,fork2,knife1,knife2，其初值均为,1”，分别表示叉 1、叉 2、刀 1、刀 2是可用的。
（ 3）用类 C语言描述互斥关系如下：
int fork1 = fork2 = 1;
int knife1 = knife2 = 1;
cobegin
Pa()
//Pb()
//Pc()
//Pd()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
Pa()
{
while(1)
{ P(knife1);
P(fork1);
进餐 ;
V(knife1);
V(fork1);
讨论问题 ;
}
}
第 2章 处理器管理
Pb()
{
while(1)
{ P(knife2);
P(fork1);
进餐 ;
V(knife2);
V(fork1);
讨论问题 ;
}
}
Pc()
{
while(1)
{ P(knife2);
P(fork2);
进餐 ;
V(knife2);
V(fork2);
讨论问题 ;
}
}
Pd()
{
while(1)
{ P(knife1);
P(fork2);
进餐 ;
V(knife1);
V(fork2);
讨论问题 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-6】 在南开大学和天津大学之间有一条弯曲的小路，其中从
S到 T有一段路每次只允许一辆自行车通过。但是，其中有一个小的安全岛 M（同时允许两辆自行车停留），可以供两辆自行车错车时使用，如图 2-16所示。试设计一个算法以确保来往自行车的顺利通过。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 分析：在本题中，需要控制路段 T到 L,S到 K及安全岛 M的使用。路段 T到 L,S到 K都只允许一辆自行车通过，而安全岛允许两辆自行车使用，两个路段和安全岛相当于临界资源。通过该路段的两个进程没有必然的先后次序，因此，本题属于互斥问题。
另外，为了保证安全岛上最多有两辆自行车，需要对相向行驶的两个方向进行控制，在每个方向上一次只允许一辆自行车通过。
此图可以简化为：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥解题步骤：（ 1）确定进程的个数及其工作。本题涉及两个进程：
从南大到天大、从天大到南大。其工作流程如图 2-17所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定互斥信号量的个数、含义及 PV操作。在本题中设臵 5个信号量 ST、
TS,K,L,M,ST表示是否允许自行车从南大到天大,TS表示是否允许自行车从天大到南大,K表示是否允许自行车通过路段 SK,L表示是否允许自行车通过路段 TL,M表示安全岛上还可以停放自行车的数目。
（ 3）用类 C语言描述算法如下：
int ST=1,TS=1;
int K=1,L=1;
int M=2;
cobegin
totian() /* 由南大到天大 */
//tonan() /* 由天大到南大 */
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
totian()
{
P(ST);
P(K);
从 S到 K;
P(M);
V(K);
进入安全岛 ;
P(L);
V(M);
从 L到 T;
V(L);
V(ST);
}
第 2章 处理器管理
tonan()
{
P(TS);
P(L);
从 T到 L;
P(M);
V(L);
进入安全岛 ;
P(K);
V(M);
从 K到 S;
V(K);
V(TS);
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-7】 某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及 PV操作描述这一组进程的工作过程。
【 解 】 分析：本题涉及对同一个数据库的读写操作。当多个进程对其读时，因不改变其中的数值，可以不加限制。当既有的读进程，又有写进程时，应加以限制。此时，数据库就是一个临界资源，读写进程必须对其进行互斥操作。因为写进程执行时，不能执行其他读写进程，所以还必须设臵一个计数器统计读进程的个数。如果是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。这是一个互斥问题，也是典型的读者和写者问题。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥解题步骤：（ 1）确定进程的个数及工作。本题只有读写两类进程，各自的工作如图 2-18所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定信号量的个数、含义及 PV操作。本题应当设臵 2个信号量和 1个共享变量,count为共享变量，记录当前正在读数据库的进程数目； rmutex为读互斥信号量，使进程互斥地访问共享变量
count，其初值为 1；对于写进程与读进程、写进程与写进程来说，
数据库是临界资源，一次只能被一个进程使用。所以设臵 wmutex
为互斥信号量，其初值为,1”。所以，本题有两个临界资源：共享变量 count和数据库，对它们要实施互斥操作。
（ 3）用类 C语言描述同步关系。算法描述如下：
int rmutex=1;
int wmutex=1;
count=0;
cobegin
reader()
//writer()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
reader()
{
while(1)
{
P(rmutex); /* 获取对 count变量的操作 */
if (count==0) P(wmutex); /* 当第一个读进程读数据库时，竞争数据库 */
count++;
V(rmutex); /* 释放对 count变量的操作 */
读数据库；
P(rmutex); /* 获取对 count变量的操作 */
count--;
if (count==0) V(wmutex); /* 当最后一个读进程读完数据库时，释放数据库 */
V(rmutex); /* 释放对 count变量的操作 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
writer()
{
while (1)
{
P(wmutex); /* 获取对数据库的操作 */
写数据库；
V(wmutex); /* 释放对数据库的操作 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步实现进程同步的 关键 是进程间执行次序的有效协调。当前一个进程执行完后，其后的进程才能执行。当前进程没有执行完，
其后的进程就不能执行。
【 例 2-8】 图 2-19给出了 4个进程合作完成某一任务的前趋图，试说明这 4个进程间的同步关系，并用 PV操作描述它们。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 方法一：用同步信号量来表示该进程是否可以开始。
设臵 4个同步信号量 b1,b2,b3,b4分别表示进程 P1,P2,P3,P4是否可以开始执行。因 P1无条件执行，所以 b1=1，其余信号量初值均为 0。这 4个进程的同步关系描述如下：
int b1=1;
int b2,b3,b4;
b2=b3=b4=0;
cobegin
P1()
//P2()
//P3()
//P4()
coend
第 2章 处理器管理
P1()
{
p(b1);
…
v(b2);
v(b3);
}
P2()
{
p(b2);
…
v(b4);
}
P3()
{
p(b3);
…
v(b4);
}
P4()
{
p(b4);
p(b4);
…
}
思考：哪个信号量可以省略？
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 方法二：用同步信号量来表示进程是否已经结束。
设臵 4个同步信号量 b1,b2,b3,b4分别表示进程 P1,P2,P3,P4是否执行结束，其初值均为,0”。这 4个进程的同步关系可以描述如下：
int b1,b2,b3,b4;
b1=b2=b3=b4=0;
cobegin
P1()
//P2()
//P3()
//P4()
coend
第 2章 处理器管理
P1()
{
…
v(b1);
v(b1);
}
P2()
{
p(b1);
…
v(b2);
}
P3()
{
p(b1);
…
v(b3);
}
P4()
{
p(b2);
p(b3);
…
v(b4);
}
思考：哪个信号量可以省略？
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 例 2-9】 桌子上有一个空盘子，只允许放一个水果。爸爸可以向盘子中放苹果，也可以向盘子中放桔子，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。规定当盘子为空时，一次只能放一个水果，请用 PV操作实现爸爸、儿子、女儿三个“并发进程”
的同步。
【 解 】 分析：这是一个明显的同步问题，也称为生产者和消费者问题。爸爸可以向盘子中放入两类水果：桔子、苹果；然后儿子、
女儿每人可以消费其中一种水果。爸爸是生产者，子女是消费者。
也就是只有爸爸放入水果，子女才能消费水果；只有子女消费完水果，爸爸才能再次放入水果，如此反复。
解题步骤如下：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 1）确定进程的个数及工作，用流程图的形式描述各进程的工作，如图 2-20所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 2）确定同步信号量的个数及含义。在流程图中标明对同步信号量的 PV操作。
设臵 3个同步信号量,Sp表示盘子是否为空，其初值为,1”，含义是爸爸是否可以开始放入水果,So表示盘子中是否有桔子，其含义是儿子是否可以开始取桔子，其初值为,0”表示不能取桔子； Sa 表示盘子中是否有苹果，其含义是女儿是否可以开始取苹果，其初值为,0”表示不能取苹果。
（ 3）用类 C语言描述同步关系如下：
int Sp = 1;
int Sa = 0;
int So = 0;
cobegin
father()
//son()
//daughter()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
father()
{
while(1)
{
P(Sp); /* 获取空盘子 */
将水果放入盘子中 ;
if (放入的是桔子 )
V(So); /*通知儿子吃桔子 */
else
V(Sa); /*通知女儿吃苹果 */
}
}
第 2章 处理器管理
son()
{
while(1)
{
P(So); /* 获取有桔子的盘子 */
从盘子中取桔子 ;
V(Sp); /*通知父亲放水果 */
吃桔子 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步第 2章 处理器管理
daughter()
{
while(1)
{
P(Sa); /* 获取有苹果的盘子 */
从盘子中取苹果 ;
V(Sp); /*通知父亲放水果 */
吃苹果 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 例 2-10】 有三个进程 PA,PB,PC合作解决文件打印问题，如图 2-21所示。 PA将文件记录从磁盘读入主存的缓冲区 1，每执行一次读一条记录； PB将缓冲区 1的记录复制到缓冲区 2，每执行一次复制一条记录； PC将缓冲区 2的记录打印出来，每执行一次打印一条记录；缓冲区的大小等于一条记录的 PA,PB,PC大小。请用 PV操作来保证文件的正确打印。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 分析：在本题中，进程 PA,PB,PC之间的同步关系为 PA
与 PB共用缓冲区 1，而 PB与 PC共用缓冲区 2。当缓冲区 1为空时，
进程 PA可以将记录读入其中；若缓冲区 1中有记录，进程 PB可以将记录从缓冲区 1中读出；当缓冲区 2为空时，进程 PB可以将记录复制到缓冲区 2中；当缓冲区 2中有记录时，进程 PC可以打印记录。
在其他条件下，相应进程必须等待。这是一个生产者与消费者和另一个生产者与消费者串联的问题，也是一个同步问题。 PA进程是生产者,PB进程既是消费者又是生产者,PC是消费者。
解题步骤：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 1）确定进程的个数及工作，用流程图的形式描述各进程的处理工作，如图
2-22所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 2）确定同步信号量的个数及含义。在流程图中标明对同步信号量的 PV操作。
本题设臵 4个信号量 e1,e2,f1,f2，信号量 e1,e2分别表示缓冲区 1和缓冲区
2是否为空，其初值为,1”；信号量 f1,f2分别表示缓冲区 1和缓冲区 2是否有记录可以处理，其初值为,0”。也可以理解为 e1表示 PA是否可以开始写,f1表示
PB是否可以开始读,e2表示 PB是否可以开始写,f2表示 PC是否可以开始读。
（ 3）用类 C语言描述同步关系如下：
int e1=1,e2=1;
int f1=0,f2=0;
cobegin
PA()
//PB()
//PC()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
PA()
{
while (1)
{
从磁盘读取一条记录 ;
P(e1); /*获取缓冲区 1空的信息 */
将记录存入缓冲区 1;
V(f1); /*通知进程 PB读记录 */
}
}
第 2章 处理器管理
PB()
{
while (1)
{
P(f1);
从缓冲区 1读取一条记录 ;
V(e1);
P(e2); /*获取缓冲区 2空的信息 */
将记录存入缓冲区 2;
V(f2); /*通知进程 PC读记录 */
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步第 2章 处理器管理
PC()
{
while (1)
{
P(f2);
从缓冲区 2读取一条记录 ;
V(e2);
打印记录 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥当进程间同时存在同步和互斥两种关系时，也就是既具有竞争临界资源的关系，又具有相互合作的关系。此时，主要是协调同步操作和互斥操作的先后。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 例 2-11】 设有一个具有 N个信息元素的环形缓冲区（如图 2-23所示）,A进程顺序地把信息写进缓冲区,B进程依次从缓冲区中读出信息，请用 PV操作描述 A,B进程的同步。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 解 】 分析：这是一个具有多个缓冲空间的生产者消费者问题，也是一个同步加互斥的问题。 A,B 两个进程对缓冲区的访问必须互斥。并且当缓冲区满时,A进程不能写入，必须等待；当缓冲区空时,B进程不能读，必须等待，读写进程之间又是同步问题。
解题步骤：（ 1）确定进程的个数及工作。本题只有读、写两类进程，各自的工作如图 2-24所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
（ 2）确定信号量的个数、含义及 PV操作。本题设臵 3个信号量：互斥信号量 S
= 1（表示对缓冲区的互斥使用）；同步信号量 Sw（代表缓冲区是否有空闲，
即写进程能否写）,Sr（代表缓冲区是否有数据，即读进程能否读），假设初始时缓冲区没有任何数据，则 Sw = N,Sr = 0。设一个数组 array表示缓冲区，
两个整型变量 in,out表示写入和读出的位臵。
（ 3）用类 C语言描述同步关系如下：
#define N 10;
int array[N],in=0,out=0;
int S=1,Sw=N,Sr=0;
cobegin
PA()
//PB()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
PA()
{
while(1)
{
生产数据 M;
P(Sw); /* 申请写数据 */
P(S); /* 获取缓冲区 */
array[in] = 数据 M; /* 向缓冲区写数据 M */
in =(in+1)mod N; /* 调整写指针 */
V(S); /* 释放缓冲区 */
V(Sr); /* 通知进程 PB读数据 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
PB()
{
while(1)
{
P(Sr); /* 申请读数据 */
P(S); /* 获取缓冲区 */
M = array[out]; /* 从缓冲区读数据 */
out =(out+1)mod N; /* 调整读指针 */
V(S); /* 释放缓冲区 */
V(Sw); /* 通知进程 PA写数据 */
消费数据 M;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 例 2-12】 理发师理发问题。有一个理发师、一把理发椅和 n把等候理发顾客坐的椅子。如果没有顾客，则理发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师，进行理发；当理发师正在理发，又有顾客来到时，如果有空椅子，
顾客就可以坐下来等候，如果没有空椅子，他就离开。请为理发师和顾客各编一个程序表述他们的行为。
【 解 】 分析：本题涉及两个进程：理发师和顾客。当有顾客时理发师就可以理发，理完发后，从等候的顾客中选一位顾客继续理发。当理发师正在理发时，
顾客要等待，若没有座位就离开，顾客与理发师的工作是同步关系。有多少顾客在等候，需设计一个计数器来记录，顾客和理发师对计数器的操作是互斥的。
所以，这是一个同步加互斥的问题。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥解题步骤：
（ 1）确定进程的个数及工作。本题只有理发师和顾客两个进程，
各自的工作如图 2-25所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
（ 2）确定信号量的个数、含义及 PV操作。本题设臵 3个信号量,S1表示理发师是否可以开始理发，即是否有顾客； S2表示顾客是否可以被理发，即是否有理发师； S3是对计数器 waiting的互斥操作； waiting表示等待顾客的人数。
（ 3）用类 C语言描述同步关系。算法描述如下：
#define CHAIR 6 /* 为等候顾客准备的椅子数 */
int S1 = 0; /* 理发师同步信号量 */
int S2 = 0; /* 顾客同步信号量 */
int S3 = 1; /* 互斥信号量 */
int waiting = 0; /* 等待理发的人数 */
cobegin
barber()
// customer()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
barber()
{
while(1)
{
P(S1); /* 理发师睡觉等待顾客的唤醒 */
P(S3); /* 获取计数器 waiting */
waiting = waiting – 1;
V(S3); /* 释放计数器 waiting */
V(S2); /* 把顾客叫到理发椅上 */
给顾客理发 ;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
customer( )
{ P(S3); /* 获取计数器 waiting */
If (waiting < CHAIR)
{ waiting = waiting + 1;
V(S3); /* 释放计数器 waiting */
V(S1); /* 通知理发师有顾客来了 */
坐下等候 ;
P(S2); /* 等待理发师的理发通知 */
上理发椅理发 ;
}
else
V(S3); /* 释放计数器 waiting */
离开 ;
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
4．利用 PV操作实现进程同步的方法
（ 1）使用 PV操作的规则：
① 分清哪些是互斥问题，哪些是同步问题。
② 对于互斥问题要设臵互斥信号量，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设臵几个互斥信号量，且初值为 1，代表临界资源可用。
③ 对于同步问题要设臵同步信号量，通常同步信号量的个数与参与同步的进程种类有关。同步信号量表示该进程是否可以开始或该进程是否已经结束。
④ 在每个进程中用于实现互斥的 PV操作必须成对出现；用于实现同步的
PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的 P操作，则其顺序不能颠倒。必须先执行对同步信号量的 P操作，再执行对互斥信号量的 P操作。但是,V操作的顺序没有严格要求。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
4．利用 PV操作实现进程同步的方法
（ 2）同步互斥问题的解题步骤：
① 确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。
② 确定同步互斥关系。根据使用的是临界资源，还是处理的前后关系，来确定互斥与同步，然后确定信号量的个数、含义，
以及对信号量的 PV操作。
③ 用类 C语言描述同步或互斥算法。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步引入管程的原因：
每个访问临界资源的进程都必须使用 PV操作，使得大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，还可能因同步操作使用不当而导致系统故障，如顺序不当、误写、
漏写等。为此，又产生了一种新的进程同步管理工具 ——管程。
1．管程的概念
1971年,Dijkstra提出，把所有进程中对某一种临界资源的同步操作都集中起来，构成一个所谓的“秘书”进程，凡是访问该临界资源的进程，都需要先报告“秘书”，由“秘书”来实现进程的同步。 1973年,Hansan和 Hoare又把“秘书”进程思想发展为管程的概念。
一个管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步管程的组成：
管程由三部分组成：局部于管程的共享变量说明、对该数据结构进行操作的一组过程、对局部于管程的数据设臵初始值的语句。此外，每个管程都有惟一的名字来标识。管程类似于面向对象程序设计中的类。
例如，学校的教务处就相当于管程。学校的各个教学部门需要安排什么课程，学生对教学有什么要求都向教务处提出申请，
由教务处统一协调各类教学资源的使用。这里各教学部门、学生相当于进程，教务处相当于管程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题进程或者线程的阻塞和唤醒，可以通过管程的 wait和 signal 操作来巧妙地实现，所有管程中的过程是互斥的。利用管程实现同步，必须设臵两个同步操作原语：
（ 1） wait原语,当某进程通过管程请求获得临界资源而未得到满足时，管程调用该原语使该进程阻塞，并将它排在该临界资源的阻塞队列上。
（ 2） signal原语,仅当一个进程访问完成并释放临界资源时，管程才能调用该原语，唤醒阻塞队列上的队首进程。
为了区别阻塞的原因，需要设臵一个 条件变量 。条件变量是一个整型变量，用 condition说明，在条件变量上可以使用 wait和
signal操作原语。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题管程定义的一般格式为：
monitor 管程类名 /* monitor是关键词 */
{
共享变量说明；
条件变量说明；
过程定义； /* 一般有多个 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-13】 利用管程机制解决例 2-11中的生产者与消费者问题。
【 解 】 设 in,out,count,buffer[]为共享变量，其中 buffer[]为缓冲区，即生产者和消费者的共享资源。 count为缓冲区产品的数量,in指示生产者存放产品的位臵，
out指示消费者取产品的位臵。 full,empty为条件变量。其中 full表示当缓冲区产品放满时，生产者排队； empty表示当缓冲区无产品时，消费者排队。 put()，
get()为两个对缓冲区的操作过程。其中 put()表示把产品放入缓冲区,get()表示从缓冲区取产品。
管程描述如下：
#define N 10
monitor producer_consumer /* 定义生产者 -消费者管程 */
{
int in=0,out=0,count=0,buffer[N];
conditioan full,empty; /* 定义条件变量 */
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
put(int item)
{
if (count>=N)
full.wait; /* 当缓冲区满时排队 */
buffer[in]=item;
in=(in+1)%N;
count++;
empty.signal; /* 唤醒消费者等待队列中的进程 */
}
get(int item)
{
if (count<=0)
empty.wait; /* 当缓冲区空时排队 */
item=buffer[out];
out=(out+1)%N;
count--;
full.signal; /* 唤醒生产者等待队列中的进程 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题生产者 —消费者描述为：
int item;
monitor producer_ consumer pc； /* pc为一个具体的生产者 -消费者管程 */
cobegin
producer() /* 生产者 */
{
while(1)
{
生产一个产品 item;
pc.put(item); /* 调用管程中的过程存放产品 */
}
}
//consumer() /* 消费者 */
{
while(1)
{
pc.get(item); /* 调用管程中的过程取产品 */
消费产品 item;
}
}
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-14】 用管程机制解决例 2-7中的读者 —写者问题。
【 解 】 读者 —写者问题的条件是：当有读者读时，写者等待；当有写者写时，读者必须等待；当写者结束时，读者优先获取读；当读者结束时，写者之后的读者落后于写者。
其管程描述如下：
monitor reders_writers
{
int read_cnt=0; /* 当前读资源进程的数目 */
int writing=0; /* 是否有写者正在使用这个资源 */
condition read,write; /* 读者等待队列，写者等待队列 */
start_read() /* 开始读过程 */
{
if (writing||!empty(write)) /* 如果正在写或者有写者进程就阻塞读进程 */
read.wait;
read_cnt++;
read.signal; /* 唤醒一个读进程 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
end_read() /* 结束读过程 */
{
read_cnt=read_cnt-1;
if(read_cnt==0)
write.signal /* 唤醒一个写进程 */
}
start_write() /* 开始写过程 */
{
if ((read_cnt!=0)||writing) /* 如果正在写或者有读进程就阻塞写进程 */
write.wait;
writing=1;
}
end_write() /* 结束写过程 */
{
writing=0;
if (!empty(read)) /* 有读进程就唤醒 */
read.signal;
else /* 否则就唤醒写进程 */
write.signal;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题在读者和写者中调用管程：
monitor readers_writers pc; /* 定义一个具体的读者 -写者管程 pc */
cobegin
readers()
// writers()
coend
readers()
{
while(1)
{
pc.start_read(); /* 调用开始读过程 */
读数据库；
pc.end_read(); /* 调用结束读过程 */
}
}
writers()
{
while(1)
{
pc.start_write(); /* 调用开始写过程 */
写数据库；
pc.end_write(); /* 调用结束写过程 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-15】 用管程机制解决例 2-5中 4位哲学家就餐问题。
【 解 】 请读者分析管程中使用的共享变量、条件变量和定义的过程。
monitor dining_philosophers
{
enum status
{
thinking,hungry,eating } state[4]; /* 共享变量 */
condition self[4]; /* 条件变量 */
for(int i=0;i<4;i++) /* 设臵初始状态 */
state[i]=thinking;
pickup(int i) /* 申请吃饭过程 */
{
state[i]=hungry;
test(i); /* 调整其状态 */
if (state[i]!=eating)
self[i].wait; /* 推迟自己进餐 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
putdown(int i) /* 放下筷子的处理过程 */
{
sate[i]=thinking;
test((i+4)%4); /* 调整其前者状态 */
test((i+1)%4); /* 调整其后者状态 */
}
test(int i) /* 调整状态 */
{
if(state[(i+4)%4]!=eating && state[i]==hungry && state[(i+1)%4] != eating)
{
state[i]=eating;
self[i].signal;
}
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题在并发进程中调用管程：
monitor dining_philosophers pc; /* 定义一个具体的管程 pc */
cobegin
p0() // p1() // p2() //p3()
coend
pi() /* 第 i个哲学家进程（ i=0-3） */
{
while(1)
{
讨论 ;
pc.pickup(i);
吃饭 ;
pc.putdown(i);
思考 ;
}
}
第 2章 处理器管理返回
2.5 进程通信进程通信 是指进程间的信息交换。根据通信的机制不同将进程通信分为低级通信和高级通信。进程的同步与互斥称为 低级通信 。用户直接利用操作系统提供的一组通信命令，高效地传送大量数据，称为高级通信 。
2.5.1 共享存储器系统在 共享存储器系统 中，相互通信的进程共享某些数据结构或存储区，进程之间能够通过它们进行通信。
1．共享数据结构方式在这种通信方式下，相互通信的进程共用某些数据结构，并通过这些数据结构交换信息。这种方式与信号量机制相比，并没有发生太大的变化，比较低效、复杂，只适用于传送少量的数据。
2．共享存储区方式这种通信方式是在存储器中划出一块共享存储区，相互通信的进程可以通过对共享存储区中的数据进行读或写来实现通信。这种方式效率高，可以传送较多的数据。
第 2章 处理器管理
2.5 进程通信
2.5.2 消息传递系统在 消息传递系统 中，进程间的数据交换是以消息为单位进行的。
用户直接利用系统中提供的一组通信命令（原语）进行通信。
1．直接通信方式发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程使用接收原语从消息缓冲队列中取出消息。通常，系统提供两条通信原语：
发送原语,Send（ Receiver,message）；
接收原语,Receive（ Sender,message）；
例如：原语 Send（ P2,m）表示将消息 m发送给接收进程 P2；
而原语 Receive（ P1,m）则是表示接收由进程 P1发送来的消息 m。
第 2章 处理器管理
2.5 进程通信
2.5.2 消息传递系统
2．间接通信方式发送进程使用发送原语直接将消息发送到某种中间实体中。接收进程使用接收原语从该中间实体中取出消息。这种中间实体一般称为信箱。所以，这种方式也称为信箱通信方式，并且被广泛地用于计算机网络中（即电子邮件系统）。
（ 1）信箱通信的操作。 系统为信箱通信提供了若干条操作原语，
包括创建信箱原语、撤消信箱原语、发送原语、接收原语等。
（ 2）信箱的分类。 信箱可以由操作系统创建，也可以由用户创建。创建者是信箱的拥有者，据此，可以把信箱分为以下三类：私有信箱,公用信箱 和共享信箱 。
（ 3）进程间的关系。 当利用信箱通信时，发送进程与接收进程存在下列关系：一对一,多对一,一对多和多对多。
第 2章 处理器管理
2.5 进程通信
2.5.3 管道通信系统管道 是指连接读进程和写进程的，用于实现它们之间通信的共享文件。向管道提供输入的发送进程（写进程），以字符流的形式将大量数据送入管道，而接受管道输出的接收进程（读进程），可以从管道中接收数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信方式。 这种方式首创于 UNIX系统，因为它能传送大量的数据，又非常有效，所以又被引入到许多操作系统中。
作为人类社会，每个人可以看成是一个或一组进程，相互之间存在着千丝万缕的关系：或互斥地访问使用社会资源，或共同协调地进行社会工作。所以，人们在社会环境中，也要进行有效的控制与协调，
每个人（进程）要学会与他人共享社会资源，也要学会与他人进行有效的交流（通信），否则将不能很好地工作和生活。
第 2章 处理器管理返回
2.6 进程调度进程调度 又称为低级调度，它决定主存中就绪队列上的哪个进程（单处理器系统）获得处理器，开始执行。
2.6.1 进程调度算法的构成进程调度算法 是根据系统的资源分配策略确定的资源分配算法。一个进程调度算法必须明确两个问题,一是 何时调度的问题。
二是 调度谁的问题。何时调度是确定什么时候执行进程调度算法的问题，这是由裁决模式决定的。调度谁是确定选择哪个进程的问题，这是由优先权函数和仲裁规则共同控制的。
1．裁决模式裁决模式明确了计算与比较进程优先权的时间点，以及选择执行进程的时间点。裁决模式分为抢占式的和非抢占式的。
当采用 非抢占方式 时，一旦把处理器分配给某个进程后，便让该进程一直执行，直到该进程终止或阻塞才退出处理器，系统才能把处理器分配给其他进程。
第 2章 处理器管理
2.6 进程调度进程调度 又称为低级调度，它决定主存中就绪队列上的哪个进程（单处理器系统）获得处理器，开始执行。
2.6.1 进程调度算法的构成
1．裁决模式当采用 抢占方式 时，把处理器分配给某个进程后，在该进程尚未终止时，允许系统调度程序根据某种原则，暂停正在执行的进程，回收处理器，并将处理器重新分配给更为紧急的进程。
2．优先权函数当优先权函数应用到某个进程时，便产生一个数值。这个数值表示该进程的当前优先权。函数可以把进程或系统的不同属性作为参数来产生优先权值。这些属性包括：运行时间,周转时间,
截止期,响应时间,外部优先权,内存需求 。
3．仲裁规则仲裁规则是解决具有相同优先权进程间冲突的规则。根据不同情况采用的规则有随机规则、轮转规则、先进先出规则。
第 2章 处理器管理
2.6 进程调度
2.6.2 进程调度算法的选取原则
1．面向用户的原则。 这是为满足用户的需求而遵循的一些准则。它包括：
（ 1）周转时间短。 所谓周转时间，是指从进程提交给系统开始，到进程完成为止的这段时间。它包括等待时间和运行时间，主要用于评价批处理系统。
（ 2）响应时间快。 响应时间是指从用户通过键盘提交一个请求开始，
直至系统首次产生响应为止的时间（进程首次运行前的等待时间），
即系统在屏幕上显示出结果为止的一段时间间隔。它主要用于评价分时操作系统。
（ 3）截止时间有保证。 截止时间是指进程必须开始执行的最迟时间，
或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须保证这一点。否则，有可能引起灾难性的后果。它主要用于评价实时操作系统。
（ 4）优先权原则。 采用优先权原则，目的是让某些紧急的进程，得到及时处理。在要求严格的系统中，还要使用抢占调度方式，才能保证紧急进程得到及时处理。它用于批处理、分时和实时系统。
第 2章 处理器管理
2.6 进程调度
2.6.2 进程调度算法的选取原则
2．面向系统的原则。 这是为了满足系统要求而遵循的一些准则。它包括：
（ 1）系统吞吐量高。 系统吞吐量是指系统在单位时间内所完成的进程数量。显然进程的平均长度将直接影响到系统吞吐量的大小。另外进程调度的方式与算法，也会对系统吞吐量产生较大的影响。它主要用于评价批处理系统。
（ 2）处理器利用率高。 对于大、中型系统，由于 CPU价格昂贵，所以处理器的利用率就成为十分重要的指标。在实际系统中,CPU的利用率一般在 40%～ 90%之间。但是，该准则一般不用于微机系统和某些实时系统，它主要用于大、中型系统。
（ 3）各类资源的平衡利用。 对于大、中型系统，不仅要使处理器利用率高，而且还应能有效地利用其他各类资源，保持系统中各类资源都处于忙碌状态。同样，该准则一般不用于微机系统和某些实时系统，它主要用于大、中型系统。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
1．先来先服务调度算法（ FCFS）
先来先服务调度算法是一种最简单的调度算法，系统开销最少。
当系统采用这种调度算法时，系统从就绪队列中选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。进程一旦占有了处理器，就一直运行下去，直到完成或因发生某种事件而阻塞，才退出处理器。
先来先服务调度算法的 裁决模式 是非抢占式的,优先权函数 =花费在系统中的实际时间,仲裁规则 是随机的。这种调度算法有利于长进程，而不利于短进程。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
2．短进程优先调度算法（ SPF）
短进程优先调度算法是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行。直到该进程完成或因发生某种事件而阻塞，才退出处理器。
短进程优先调度算法的 裁决模式 是非抢占式的,优先权函数 ＝ -
运行时间,仲裁规则 是按照时间先后顺序或随机方式。这种调度算法照顾到了系统中的短进程，有效地降低了进程的平均等待时间，
提高了系统的吞吐量。但是，这种算法对长进程不利。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
3．最短剩余时间优先调度算法（ SRT）
最短剩余时间优先调度算法是短进程优先调度算法的抢占式的动态版本。它将 CPU分配给需要最少时间来完成的进程。
最短剩余时间优先调度算法的 裁决模式 是抢占式的,优先权函数 是动态的，随着进程运行和完成时间的减少而增加,仲裁规则 是按照时间先后顺序或随机方式。这种调度算法充分照顾到了剩余运行时间短的进程。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
4．时间片轮转调度算法（ RR）
在分时系统中，为了保证人机交互的及时性，系统使每个进程依次按照时间片方式轮流执行，即时间片轮转调度算法。在该算法中，系统将所有的就绪进程按照进入就绪队列的先后次序排列。每次调度时把 CPU分配给队首进程，让其执行一个时间片。当时间片用完，由计时器发出时钟中断，调度程序暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。
然后，把 CPU分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一定的时间
（可以接受的等待时间）内，均能获得一个时间片的执行时间。
时间片轮转调度算法的 裁决模式 是面向时间片的，所有就绪进程的 优先权函数 值相同,仲裁规则 是轮转规则。这种调度算法适用于交互进程的调度。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
5．优先权调度算法为了照顾紧迫型进程获得优先处理，引入了优先权调度算法，
也称为外部优先权调度算法。它是从就绪队列中选择一个优先权最高的进程，获得处理器并执行。
优先权调度算法的 裁决模式 是抢占式的或非抢占式的,优先权函数 是用户或系统赋给它的优先权,仲裁规则 是随机的或先进先出的。
对于优先权调度算法，其关键在于是采用静态优先权，还是动态优先权，以及如何确定进程的优先权。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
6．响应比高者优先调度算法（ HRRN）
响应比高者优先调度算法是一个比较折衷的算法，它是从就绪队列中选择一个响应比最高的进程，让其获得处理器并执行，直到该进程完成或因等待某种事件而退出处理器为止。响应比 = 响应时间 / 要求服务时间。
响应比高者优先调度算法的 裁决模式 是非抢占式的,优先权函数
=响应比,仲裁规则 是随机或按照先后次序。
这种调度算法既照顾了短进程，又考虑了进程到达的先后次序，
也不会使长进程长时间得不到服务。因此，它是一个考虑比较全面的算法。但是每次进行调度时，都需要对各个进程计算响应比。所以，系统开销很大，比较复杂。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
7．多级队列调度算法（ ML）
目前的计算机系统，不少都同时具有多种操作方式，既具有批处理操作方式，用于处理批量型作业；又具有分时操作方式，用于处理交互型作业。但是，这两种作业的性质却截然不同。通常，为批处理作业所建立的进程将排入后台的就绪队列；而为交互型作业所建立的进程则排入前台的就绪队列。前台采用时间片轮转调度算法，而后台采用优先权调度算法或短进程优先调度算法等。
一般来说，多级队列调度算法是根据进程的类型或性质不同，
将就绪进程分为若干个独立队列，不同类型或性质的进程固定地属于一个队列。每个队列可以采用适合自己要求的调度算法。不同的队列可以使用不同的调度算法。
在采用多级队列调度算法时，可以按照多种方式来处理各队列间的关系。一种是规定每个队列的优先权，优先权高的队列将优先获得调度执行。另一种是为各队列分配一定比例的处理器时间，然后分别调度使用。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
8．多级反馈队列调度算法（ MLF）
前面所介绍的各种进程调度算法，都存在一定的局限性。如短进程优先调度算法，不利于长进程，而且如果没有有效地表明进程的长度，其算法将无法正常使用。而多级反馈队列调度算法，则不必事先知道各个进程所需的执行时间，可以满足各种类型进程的需要，是目前一种较好的进程调度算法。
多级反馈队列调度算法的 裁决模式 是抢占式的或非抢占式的，
优先权函数 是从最大值开始每执行一次递减 1,仲裁规则 是轮转的或按照时间先后次序。
这种调度算法具有较好的性能，能满足各种类型用户的需求。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
【 例 2-16】 3个批处理进程 P1,P2,P3具有下列到达时间和要求运行时间，请按照先来先服务（ FCFS）、短进程优先（ SPF）和最短剩余时间优先（ SRT）调度算法，画出其时序图，并计算它们的平均周转时间。
【 解 】 三种调度算法的时序图如图 2-27所示。
第 2章 处理器管理返回
2.7 进程死锁
2.7.1 死锁的基本概念
1．死锁的概念死锁 是指多个进程因竞争资源而造成的一种僵局现象，若无外力的作用，这些进程都不能继续执行。
2．死锁的原因
（ 1）竞争资源。当系统中供多个进程共享的资源不足以同时满足它们的需求时，引起它们对资源的竞争而产生死锁。
（ 2）进程推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，会导致进程死锁。
第 2章 处理器管理
2.7 进程死锁
2.7.1 死锁的基本概念
3．产生死锁的必要条件死锁并不一定都会出现，如果一旦产生死锁，一定会满足下述
4个必要条件。
（ 1）互斥条件。 进程对分配到的资源进行排他性、独占性使用。即在一段时间内某资源只能由一个进程占用，如果此时还有其他进程请求使用该资源，请求者只能等待，直到占有该资源的进程用完后释放，才能使用该资源。
（ 2）请求和保持条件。 进程已经拥有并保持了至少一个资源，但是，
又请求新的资源，而新请求的资源又被其他进程占有，此时请求进程被阻塞，但是，对已获得的资源保持不放。
（ 3）不剥夺条件。 进程所占有的资源，在结束之前不能被剥夺，只能在运行结束后由自己释放。
（ 4）环路等待条件。 在发生死锁时，必然存在一个“进程 ——资源”
的环形链。
第 2章 处理器管理
2.7 进程死锁
2.7.1 死锁的基本概念
4．处理死锁的基本方法目前用于处理死锁的方法分为三种。
（ 1）预防死锁。 预防死锁是在进行资源分配之前，通过设臵某些资源分配的限制条件，来破坏产生死锁的四个必要条件的一个或几个。
预防死锁是一种较简单的方法，容易使用，但是，由于施加了限制条件，会导致系统资源利用率和吞吐量的下降。
（ 2）避免死锁。 避免死锁是在资源分配前不设臵限制条件，在进行资源分配的过程中，用某种方法对每次资源分配进行管理，以避免某次分配使系统进入不安全状态，以至产生死锁。这种方法限制较小，可以获得较好的系统资源利用率和吞吐量。目前比较完善的系统中，通常采用此种方法。
（ 3）检测和解除死锁。 首先是通过系统的检测过程及时地检查系统是否出现死锁，并确定与死锁有关的进程和资源；然后，通过撤消或挂起一些死锁中的进程，回收相应的资源，进行资源的再次分配，
从而将进程死锁状态解除。这种方法没有限制，可以获得较好的系统资源利用率和吞吐量，但是实现难度较大。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防通过对资源分配的原则进行限制，而使产生死锁的四个必要条件中的第 2,3,4个条件之一不能成立，来预防产生死锁。
1．破坏“不剥夺”条件一个已经占有某些资源的进程，当它再提出新的资源需求而不能立即得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请。这意味着进程已经拥有的资源，在运行过程中可能会暂时被迫释放，即被系统剥夺，从而摒弃了“不剥夺条件”。
这种预防死锁的方法，实现起来比较复杂，并付出较大的代价，
会使前段时间的工作失效等。此外这种方法还会因为反复地申请和释放资源，延长进程的周转时间，增加系统开销，降低系统吞吐量。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防
2．破坏“请求和保持”条件系统要求进程必须一次性地申请其在整个运行期间所需要的全部资源。若系统有足够的资源，便一次性将其所需要的所有资源分配给该进程，这样一来，该进程在整个运行过程中，便不会再提出资源请求，从而摒弃了“请求”条件。而在分配时，只要有一个资源要求不能满足，系统将不分配给该进程任何资源，此时进程没有占有任何资源，因而也摒弃了“保持”条件，所以，可以预防死锁的产生。
这种预防死锁的方法，简单方便、易于实现，但是，因为进程将一次性获得所有资源，并且独占使用，其中可能有些资源在该进程运行期间很少使用，造成资源严重浪费；同时有些进程因不能一次性获得所需要的资源，导致长时间不能投入运行。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防
3．破坏“环路等待”条件在这种方法中规定，系统将所有的资源按照类型进行线性排序，
赋予不同的资源序号。并且所有进程对资源的请求和分配必须严格的按照资源序号由小到大地进行，即只有先申请和分配到序号小的资源，才能再申请和分配序号大的资源。这样在最后形成的资源分配图中，将不可能再出现环路，从而摒弃了“环路等待”条件。
这种预防死锁的方法与前两种相比，其资源利用率和系统吞吐量，都有明显的改善。但是，这种方法涉及对各类资源的排序编号，
考虑到实际的使用，其排序的合理性将受到很大的挑战。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免在死锁的避免中，所施加的限制较弱，可以获得较好的系统性能。
该方法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免死锁发生。
1．安全状态与不安全状态安全状态 是指系统能够按照某种顺序为每个进程分配所需要资源,
直到最大需求,使每一个进程都可以顺利完成 。 反之,如果系统不存在这样的一个安全序列,则称系统处于 不安全状态 。
当系统进入不安全状态后,很有可能进入死锁状态；反之,只要系统处于安全状态,便可避免进入死锁状态 。 因此,避免死锁的实质就是如何使系统不进入不安全状态 。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
2．利用银行家算法避免死锁最具代表性的避免死锁的算法是 Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。
（ 1）银行家算法采用的数据结构。银行家算法采用的数据结构有最大需求向量 Max、已分配资源向量 Allocation、还需资源向量 Need和可用资源向量 Available。 如表 2-4所示 。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
2．利用银行家算法避免死锁
（ 2）银行家算法的处理步骤
① 列出某一时刻的资源分配表，格式如表 2-4所示。
② 拿可用资源量与每一个进程的还需资源量进行比较，可用资源量不少于还需资源量时，把资源分配给该进程。新的可用资源量为原有可用资源量加上该进程已分配的资源量。
③ 重复②，直到所有进程都执行完毕或系统可用资源量小于每一个剩余进程的还需资源量，即可判断能否获得一个安全资源分配序列。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
3．银行家算法举例
【 例 2-17】 假定系统中有 5个进程 P0,P1,P2,P3,P4和 3种类型的资源 A,B,C，每一种资源的数量分别为 10,5,7，在某一时刻资源分配情况如下表所示，利用银行家算法，判断是否有一个资源分配的安全序列？
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
3．银行家算法举例
【 解 】 系统可用的资源量为 （ 3,3,2）,根据银行家算法可以与每个进程的还需资源量进行比较,分配,如下表所示：
资源分配序列 {P1,P3,P4,P2,P0}是安全的 。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除当系统为进程分配资源时，如果没有采取任何限制措施，系统必须提供死锁的检测与解除机制。
1．死锁的检测在进行死锁的检测时，系统必须能保存有关资源的请求和分配的信息，并提供一种算法，以便利用这些信息来检测系统是否进入死锁状态。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 1）资源分配图。 系统死锁可以利用资源分配图来描述。该图是由一组方框、圆圈和一组箭头线组成的，如图 2-30所示。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 1）资源分配图。 资源分配图采用图素的含义分别是：
–方框,表示资源。有几类资源就画几个方框，方框中的小圆圈表示该类资源的个数。当个数较大时可以在方框内用阿拉伯数字表示。
–圆圈,表示进程。有几个进程就画几个圆圈，圆圈内标明进程名称。
–箭头线,表示资源的分配与申请。由方框指向圆圈的箭头线表示资源的分配线，由圆圈指向方框的箭头线表示资源的请求线。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 2）死锁定理。 在死锁检测时，可以利用把资源分配图进行简化的方法来判断系统当前是否处于死锁状态。具体方法如下：
① 在资源分配图中，找出一个既非阻塞又非孤立的进程结点 Pi。
如果 Pi可以获得其所需要的资源而继续执行，直至运行完毕，就可以释放其所占用的全部资源。这样，就可以把 Pi所有关连的资源分配线和资源请求线消去，使之成为孤立的点。
② 重复进行上述操作。在一系列的简化后，如果消去了资源分配图中所有的箭头线，使所有进程结点都成为孤立结点，则称该资源分配图是可完全简化的；反之，则称该资源分配图是不可完全简化的。
如果当前系统状态对应的资源分配图是不可完全简化的，则系统处于死锁状态，该充分条件称为 死锁定理 。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
2．死锁的解除当检测到系统发生死锁时，就必须立即把死锁状态解除，常用的方法是：
（ 1）剥夺资源法。 从其他进程剥夺足够数量的资源给死锁进程，使其得到足够的资源，然后继续执行，以解除死锁状态。
（ 2）撤消进程法。 系统采用强制手段将死锁进程撤消。最简单的方法是将全部死锁进程一次性撤消，但是，代价较大；另一种方法是按照一定的算法，从死锁进程中一个一个地选择进行撤消，并同时剥夺这些进程的资源，直到死锁状态解除为止。
第 2章 处理器管理返回
2.8 线程、超线程和双核的基本概念
2.8.1 线程
1．线程的引入进程作为系统中的一个基本单位，具有两个属性：一是资源分配和拥有的基本单位。二是一个可以独立调度和执行的基本单位。
而在进程操作过程中，因为进程是一个资源的拥有者，所以，
系统要不断地进行资源的分配与回收、现场的保存与恢复等工作。
系统要为此付出较大的时间与空间的开销。另外，在系统中所设臵的进程数目不能过多，进程切换的频率也不能过高，这就限制了系统并发程度的进一步提高。
如何能使进程更好地并发执行，同时又能尽量减少系统开销呢？
一些学者设想将进程的两个属性分开，由操作系统分别处理，即只作为资源分配与拥有的单位，不再是调度和执行的基本单位，使之轻装前进；而对资源分配与拥有的基本单位，不进行频繁的切换处理，以减少系统开销。正是因为这种思想，产生了一个新的概念 —
—线程 。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
2．线程的概念线程 是进程中的一个实体，是被系统独立调度和执行的基本单位。
线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但是它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。
一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。线程之间也会相互制约，使其在运行中呈现异步性。因此，线程同样具有就绪、执行、阻塞三种基本状态。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
3．线程与进程的比较线程具有许多传统进程的特征，所以又称为 轻型进程 。传统的进程称为重型进程，相当于只有一个线程的任务。在引入线程的操作系统中，通常一个进程拥有若干个线程，至少也有一个线程。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
4．线程的类型
（ 1）系统级线程。 系统级线程是依赖于系统控制的，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤消与切换都是由系统控制实现的。在系统中保留了一张线程控制块，系统根据该线程控制块来感知线程的存在，并对线程进行控制。
（ 2）用户级线程。 用户级线程是由用户控制的，对于用户级线程的创建、撤消与切换，都与系统控制无关，完全由用户自己管理。简单来说就是系统并不知道有用户级线程的存在，在系统中各种控制仍然是基于进程的。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术
1．超线程的概念超线程技术是 Intel在 2002年发布的一项新技术，它率先在 Intel
的 XERON处理器上得到应用。
所谓 超线程技术 就是利用特殊的硬件指令，在一个实体处理器中放入两个逻辑处理单元，从而模拟成两个工作环境，让单个处理器能使用线程级的并行计算，同时处理多项任务，提升处理器资源的利用率。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术
2．超线程的工作超线程是同时多线程技术的一种，这种技术可经由复制处理器上的结构状态，让同一个处理器上的多个线程同步执行，并共享处理器的执行资源。
对支持多处理器功能的应用程序而言，超线程处理器被视为两个分离的逻辑处理器。应用程序无须修正就可以使用这两个逻辑处理器。同时，每个逻辑处理器都可以独立响应中断。第一个逻辑处理器可追踪一个软件线程，而第二个逻辑处理器则可以同时追踪另一个软件线程。由于两个线程共同使用同样的执行资源，因此不会产生一个线程执行而另一个线程闲臵的状况。这种方式可以大大提升每个实体处理器中执行资源的使用率。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术最近,AMD针对以往 Intel的超线程技术，又提出了逆超线程技术。超线程技术是系统将一颗 CPU看成两颗，而逆超线程技术是要将两个物理核心看作一颗，同时处理一项工作，以便在特定情况下提高速度。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.3 双核技术所谓 双核技术,简单地说就是在一块 CPU基板上集成两个处理器核心，并通过并行总线将各处理器核心连接起来的技术。双核心并不是一个新概念，而只是单芯片多处理器中最基本、最简单、最容易实现的一种类型。
如果说超线程技术是通过软件模拟出双核的效果，那么现在所说的双核技术就是真正意义上的两个核心。它弥补了超线程技术适用系统比较少的缺点，可以广泛用于 windows操作系统的多个版本。
它还有效的解决了双核运算中出现的缓存分离与数据冲突错误的问题。
目前，还出现了一种 双 CPU技术 。前面所说的双核技术是在一个处理器里拥有两个处理器核心，核心是两个，但是其他硬件还都是一套，由两个核心在共同拥有。而双 CPU则是真正意义上的双核心，不只是处理器核心是两个，其他如缓存等硬件配臵也都是双份的。这样系统处理的效率会更高。
第 2章 处理器管理返回
2.1 处理器管理概述
2.2 进程描述
2.3 进程控制
2.4 进程同步与互斥
2.5 进程通信
2.6 进程调度
2.7 进程死锁
2.8 线程、超线程和双核的基本概念本章结束！
2.1 处理器管理概述
2.1.1 处理器管理的功能处理器管理的主要任务是对处理器进行分配，并对其运行进行有效的控制和管理。
在现代操作系统中，处理器的分配和运行都是以进程为基本单位的，因而对处理器的管理也可以视为对进程的管理。
进程是程序的一次执行过程。
处理器管理包括以下功能：
1,进程控制。 在并发运行环境中，要使程序运行，必须先为它创建一个或几个进程，并给它分配必要的资源。程序运行结束时，要撤消这些进程，并回收这些进程所占用的各类资源。
进程控制的主要任务就是为程序创建进程，撤消已结束的进程，以及控制进程在运行过程中的状态转换。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
2,进程同步。 在并发环境中，进程是以异步方式工作的，并且以不可预知的速度向前推进。为了使多个进程能有条不紊地运行，系统中必须设臵进程同步机制。
进程同步的主要任务是对众多的进程运行进行协调。协调方式有两种：
(1) 进程互斥方式。 进程在对临界资源访问时，应采用互斥方式，也就是当一个进程访问临界资源时，另一个要访问该临界资源的进程必须等待；当获取临界资源的进程释放临界资源后，其他进程才能获取临界资源。这种进程之间的相互制约关系称为互斥。
简单地说,互斥 就是“有我就没你，有你就没我”。
临界资源 是指一次只能被一个进程使用的资源。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
2,进程同步。
(2) 进程同步方式。 相互合作的进程，由同步机构对它们的执行次序加以协调。也就是前一个进程结束，后一个进程才能开始；
前一个进程没有结束，后一个进程就不能开始。这种进程之间的相互合作关系称为同步。
简单地说,同步 就是“有你才有我，没你就没我”。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
3,进程通信。 在系统中，经常会有多个进程需要相互配合去完成一个共同的任务，而在这些进程之间，往往需要相互交换信息。进程通信的任务就是用来实现相互合作进程之间的信息交换。
进程的通信方式有：
（ 1）当相互合作的进程处于同一台计算机系统时，通常采用直接通信方式。 由源进程利用发送命令直接将消息发送到目标进程的消息队列上，然后由目标进程利用接收命令从其消息队列中取出消息。
（ 2）当相互合作的进程处于不同计算机系统时，通常采用 间接通信方式。 由源进程利用发送命令将信息发送到一个专门存放消息的中间实体中，然后由目标进程利用接收命令从中间实体中取出消息。这个中间实体通常称为“邮箱”，相应的通信系统称为电子邮件系统。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理的功能
4,处理器调度。 等待在后备队列上的作业，通常要经过处理器调度才能执行。处理器调度包括作业调度（也称为高级调度）、
进程调度（也称为低级调度）和中级调度。
(1)作业调度 的基本任务是从后备队列中按照一定的算法，选择出若干个作业，为它们分配必要的资源，将它们调入主存，然后为它们建立进程，使之成为可能获得处理器的就绪进程，并按照一定的算法将其插入到就绪队列。作业调度将在第 6章作业管理与系统接口中介绍。
(2)进程调度 的基本任务是从进程的就绪队列中，按照一定的调度算法选出一个进程，把处理器分配给它，并为它设臵运行现场，使进程投入运行。本章主要介绍进程调度。
第 2章 处理器管理
2.1 处理器管理概述
2.1.1 处理器管理 的功能
4,进程调度。
（ 3）中级调度 的基本任务是把那些暂时不能运行的进程从主存移到外存上，释放其所占有的宝贵资源，让其他进程运行。当移到外存上的进程具备运行条件时，再由中级调度把它们重新调入主存，等待运行。
中级调度将在第 3章存储器管理的对换技术中详细介绍，也可以参考本章 2.2.4的内容。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行程序执行 是指程序在计算机中的运行过程。程序的执行可以用前趋图表示，程序的执行方式有顺序执行和并发执行。
1.前趋图。 它是一个有向无循环图。图中的每个结点可用于表示一条语句、一个程序段等；结点间的有向边表示在两个结点之间存在的前趋关系。如 Pi → Pj,称 Pi
是 Pj的前趋，而 Pj是 Pi的后继。
在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。应当注意的是，前趋图中不能存在循环。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
1.前趋图。 图 2-1所示的前趋图。 在图 2-1所示的前趋图中存在下述前趋关系：
P1 → P2,P1 → P3,P2 → P5,P3 → P4,P4 → P5,P5
→ P6
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
2.程序的顺序执行 。 程序在执行时，必须按照某种先后次序逐个执行操作，只有当前一个操作执行完后，才能执行后一个操作。例如：在进行计算时，总是先输入需要的数据，然后才能进行计算，计算完成后再将结果输出。
如果用 I代表输入,C代表计算,P代表打印，则上述情况可用图 2-2所示的前趋图表示。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
2.程序的顺序执行 。
程序的顺序执行通常表现出如下特征：
– 顺序性。 严格按照程序所规定的顺序执行。
– 封闭性。 程序在封闭的环境下执行。程序在运行时独占所有资源，其执行结果不受外界因素的影响。
– 可再现性。 只要程序执行的环境和初始条件相同，程序无论重复执行多少次，按照何种方式执行，都将获得相同的结果。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。 是指在一个时间段内执行多个程序。
程序在并发执行的特征：
–间断性。 在程序并发执行时，由于它们之间共享资源或相互合作，致使它们之间形成了相互制约的关系，导致并发程序在执行中因为受到影响，表现为“执行 —暂停执行 —执行”的间断性活动规律。
–失去封闭性。 程序并发执行时，多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，程序在执行时，必然会受到其他程序的影响。
–不可再现性。 由于程序执行时失去了封闭性，也将导致失去可再现性。既使并发程序执行的环境和初始条件相同，程序的多次执行或以不同的方式执行，可能获得不相同的结果。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
【 例 2-1】 程序 A和程序 B为并发执行，它们共享变量 M，假设 M初值为 3；程序 A执行 M=M+1；程序 B执行 print M； M=1。程序 A和程序 B执行的顺序若不相同,M的结果将产生不同的变化。
顺序 1,M = M +1； print M； M = 1。 M值依次为 4,4,1。
顺序 2,print M； M = M +1； M = 1。 M值依次为 3,4,1。
顺序 3,print M； M = 1； M = M +1。 M值依次为 3,1,2。
按照顺序 1执行,M的输出结果为 4；按照顺序 2执行,M的输出结果为 3；按照顺序 3执行,M的输出结果为 3。所以，当执行的条件不同时，并发程序有可能产生不同的执行顺序，也就会得到不同的执行结果。这样并发程序就形成了结果的不可再现性。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。 判断程序并发执行的方法有两种：
Bernstein条件和前趋图。
（ 1） Bernstein条件。 即不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）
可以并发执行。运算的读集是指在运算执行期间引用的所有变量的集合，运算的写集是指在运算执行期间要改变的所有变量的集合。例如运算 w=x+y，其读集是 {x,y}，其写集是 {w}。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
（ 1） Bernstein条件。
【 例 2-2】 有四条语句，哪些语句可以并发执行？
s1,a=x+y; s2,b=z+1;
s3,c=a-b; s4,d=c+1;
【 解 】 要先确定运算，然后写出每个运算的读集与写集，最后两两判断运算的读集与写集，写集与写集的交集的并集是否是空集；
若是，则可以并发，若不是空集，则不能并发。
对于本题，四条语句的读集与写集分别是：
读集,R(s1)={x,y},R(s2)={z},R(s3)={a,b},R(s4)={c}；
写集,W(s1)={a},W(s2)={b},W(s3)={c},W(s4)={d}。
由 Bernstein条件可知 s1与 s2可以并发执行,s1与 s3,s2与 s3，
s3与 s4不能并发执行。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
（ 2）利用前趋图。 画出程序执行的前趋图，根据该程序或运算在前趋图中的位臵关系，可以判断其能否并发执行。即在程序或运算的先后顺序上，只有前后相邻的程序或运算不能并发执行，其余程序和运算都可以并发执行。
【 例 2-3】 已知一个求值公式 (a2+3b)/(b+5a)，若 a,b已赋值，试画出该公式求值过程的前趋图，并判断哪些求值过程可以并发执行。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
【 解 】 把公式 (a2+3b)/(b+5a)按照运算顺序分解，可以产生如下运算步骤,s1～ s6，如图 2-4（ a）所示；根据分解的运算顺序画出它的前趋图，如图 2-4（ b）所示。
第 2章 处理器管理
2.1 处理器管理概述
2.1.2 程序的执行
3.程序的并发执行。
根据前趋图，可以看出能够并发执行的运算是：
s1与 s2,s1与 s3,s2与 s3,s1与 s5,s2与 s5,s3
与 s4,s4与 s5，其余运算不能并发执行。
第 2章 处理器管理返回
2.2 进程描述
2.2.1 进程的概念
1．进程的定义。
“进程”这一术语，在 20世纪 60年代初期，首先出现在麻省理工学院的 MULTICS系统和 IBM公司的 CTSS/360系统中。其后，
人们对它不断加以改进，从不同的方面对它进行描述。关于进程的定义有以下一些描述：
进程是程序的一次执行。
进程可以定义为一个数据结构及能在其上进行操作的一个程序。
进程 是程序在一个数据集合上的运行过程，是系统资源分配和调度的一个独立单位。
第 2章 处理器管理
2.2 进程描述
2.2.1 进程的概念
2．进程的特征。 进程的五个基本特征：
（ 1）动态性。 进程的动态性是进程的最基本特征，它表现为“进程因创建而产生，因调度而执行，因得不到资源而暂停，以及因撤消而消亡”。因此，进程具有一定的生命周期，其状态也会不断发生变化，是一个动态实体。
（ 2）并发性。 进程的并发性是指多个进程在一段时间内同时运行，
交替使用处理器的情况。并发性是进程也是操作系统的重要特征。
（ 3）独立性。 进程的独立性是指进程实体是一个能独立运行的基本单位，同时也是独立获得资源和独立调度的基本单位。没有创建进程的程序，是不能参加运行的。
（ 4）异步性。 进程的异步性是指系统中的进程按照各自独立的、
不可预知的速度向前推进，即进程按照异步方式运行。
（ 5）结构性。 进程的结构性是指在结构上进程实体由程序段、数据段和进程控制块组成，这三部分也统称为“进程映像”。
第 2章 处理器管理
2.2 进程描述
2.2.1 进程的概念
2．进程的特征。
举一个例子来说明程序和进程。例如从北京西站发往长沙的
T1次列车，它有自己的运行步骤：始发时间、站台，中间停靠的车站及停靠时间，到达终点站的时间等，这相当于一个程序。
而 2007年 3月 18日从北京西站发往长沙的 T1次列车就相当于一个进程，它是一个过程,15:00从北京西站出发，第二天 6:10到达长沙结束。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
1．进程关系。 进程关系主要是指进程间执行的次序关系 。在并发环境下，进程关系有三种：
（ 1）串行。 一个进程结束，下一个进程才能开始。这两个进程的关系就是串行关系。
（ 2）并行。 多个进程可以同时开始，同时结束。这几个进程之间的关系就是并行关系。
（ 3）嵌套。 在串行中包含并行，在并行中也包含串行。这种进程间的关系就是嵌套关系。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 1）图示法。 可以采用前趋图和进程流图表示。前趋图的表示已经在上一节讲过，这里不再赘述。进程流图使用的图素有：带圈的,S”表示开始，带圈的,F”表示结束，有向线段表示进程。进程的三种关系如图 2-5所示。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 2）数学法。 就是利用数学函数来表示进程关系。“串行”使用串行函数表示,S（ p1,…,pn）。其中函数名,S”表示串行，
函数参数,p1,…,pn”表示进程，中间用逗号分隔。“并行”
使用并行函数表示,P（ p1,…,pn） 。其中函数名,P”表示并行，函数参数,p1,…,pn”表示进程，中间用逗号分隔。“嵌套”使用串行函数和并行函数的组合表示。
图 2-5中的嵌套关系可以表示为：
S（ p1,P（ p2,S（ p3,P（ p5,p6））,p4）,P（ p7，
p8））。
第 2章 处理器管理
2.2 进程描述
2.2.2 进程关系的表示
2．进程关系的表示方法。 有三种：
（ 3）程序法。 以 cobegin和 coend结构指明并行，其格式为：
cobegin p1 ; p2 ; … ; pn coend 或 cobegin p1 // p2 // … // pn
coend
其中 pi为进程或一块代码或函数。函数间用“；”分隔表示串行，
用,//”分隔表示并行。
图 2-5中的进程关系用程序法表示为：
串行,cobegin p1 ; p2 ; p3 ; p4 coend
并行,cobegin p1 // p2 // p3 // p4 coend
嵌套,cobegin
p1 ; {p2 // {p3 ; p5//p6 }// p4} ; {p7//p8}
coend
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
1．进程的三种基本状态
（ 1）就绪状态。 当进程已分配到除处理器（ CPU）以外的所有必要资源后，只要再获得处理器就可以执行的状态称为就绪状态。
在一个系统里，可以有多个进程同时处于就绪状态，通常把这些就绪进程排成一个或多个队列，称为就绪队列。
（ 2）执行状态。 处于就绪状态的进程一旦获得了处理器，就可以运行，进程状态也就处于执行状态。在单处理器系统中，只能有一个进程处于执行状态。在多处理器系统中，可能有多个进程处于执行状态。
（ 3）阻塞状态。 正在执行的进程因为发生某些事件（如请求输入 /
输出、申请额外空间等）而暂停运行，这种受阻暂停的状态称为阻塞状态，也可以称为等待状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。在有些系统中，也会按照阻塞原因的不同将处于阻塞状态的进程排成多个队列。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
2．进程的其他两种状态
（ 1）新状态。 当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新状态。
（ 2）终止状态。 当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但是，尚未撤消，这时称为终止状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
（ 1）新状态 → 就绪状态。 当就绪队列能够接纳新的进程时，操作系统就会把处于新状态的进程移入就绪队列，此时进程就从新状态转变为就绪状态。
（ 2）就绪状态 → 执行状态。 处于就绪状态的进程，当进程调度程序按照一定的算法为之分配了处理器后，该进程就可以获得执行，
从而使进程状态由就绪状态变为执行状态。处于执行状态的进程也称为当前进程。
（ 3）执行状态 → 阻塞状态。 正在执行的进程因为自身需求发生某种事件（如 I/O请求或等待某一资源等）而无法继续执行时，只好暂停执行，此时进程就由执行状态转变为阻塞状态。
（ 4）执行状态 → 就绪状态。 正在执行的进程，如果因系统分配给的时间片结束或优先权较低，而暂停执行时，该进程将会从执行状态转变为就绪状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
（ 5）阻塞状态 → 就绪状态。 处于阻塞队列中的进程，如果需要的资源得到满足或完成输入输出响应，就会变为就绪状态，进入就绪队列，等待下一次调度。
（ 6）执行状态 → 终止状态。 当一个进程正常结束或出现异常错误结束时，进程将由执行状态转变为终止状态。
第 2章 处理器管理
2.2 进程描述
2.2.3 进程的状态
3．进程状态间的转换。
图 2-6给出了具有五种基本状态的进程状态转换图。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
1．进程挂起状态的引入。
（ 1）用户的需求。 当用户在进程运行期间，发现有可疑问题时，
希望进程暂时停止下来，但是，并不终止进程。若进程处于执行状态，则暂停执行；若进程处于就绪状态，则暂时不接受调度，
以便研究进程执行情况或对程序进行修改。这种静止状态称为挂起状态。
（ 2）父进程的需求。 父进程往往希望考查和修改子进程，或者协调各个子进程之间的活动，此时需要挂起自己的子进程。
（ 3）操作系统的需求。 操作系统有时需要挂起某些进程，然后检查系统中资源的使用情况，进行记账控制，以便改善系统运行的性能。
（ 4）对换的需求。 为了缓和主存与系统其他资源的紧张情况，并且提高系统性能，有些系统希望将处于阻塞状态的进程从主存换到外存。而换到外存的进程，当等待的事件完成，它仍然不具备执行的条件，不能进入就绪队列，所以需要一个有别于阻塞状态的新状态来表示，即挂起状态。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
2．引入进程挂起状态后进程状态的转换。
（ 1）执行状态 → 静止就绪。 正在执行的进程，如果用挂起原语将该进程挂起后，此时进程就暂停执行，转变为静止就绪状态。
（ 2）静止就绪 → 活动就绪。 处于静止就绪状态的进程，若用激活原语将该进程激活后，进程状态就由静止就绪状态变为活动就绪状态，激活后的进程就可以被调度执行了。
（ 3）活动就绪 → 静止就绪。 当进程处于未被挂起的就绪状态时，
称之为活动就绪状态，在用挂起原语将该进程挂起后，此时进程就转变为静止就绪状态。处于静止就绪状态的进程，不能再被调度执行。
第 2章 处理器管理
2.2 进程描述
2.2.4 进程的挂起状态
2．引入进程挂起状态后进程状态的转换。
（ 4）活动阻塞 → 静止阻塞。 当进程处于未被挂起的阻塞状态时，
称之为活动阻塞状态。在用挂起原语将该进程挂起后，此时进程就转变为静止阻塞状态。
（ 5）静止阻塞 → 活动阻塞。 处于静止阻塞状态的进程，若用激活原语将该进程激活，进程状态就由静止阻塞状态变为活动阻塞状态。
（ 6）静止阻塞 → 静止就绪。 处于静止阻塞状态的进程，在其所需要的资源满足或完成等待的事件后，就会变为静止就绪状态。
第 2章 处理器管理返回
2.3 进程控制
2.3.1 进程控制块 PCB
1,进程控制块的概念。 进程控制块 PCB（ Process Control Block）
是进程实体的重要组成部分，是操作系统中最重要的记录型数据。
在进程控制块中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息。通过 PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，
一个能够并发执行的进程。换句话说，在进程的整个生命周期中，
操作系统都要通过进程的 PCB来对并发执行的进程进行管理和控制。
由此看来，进程控制块是系统对进程控制采用的数据结构。
系统是根据进程的 PCB而感知进程存在的。所以,进程控制块是进程存在的惟一标志。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
2,进程控制块的内容。 进程控制块主要包括下述四个方面的信息。
如图 2-8所示。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
2,进程控制块的内容。
（ 1）进程标识信息。 进程标识符用于标识一个进程，通常有外部标识符和内部标识符两种。
（ 2）说明信息（进程调度信息）。 说明信息是与进程调度有关的状态信息,进程状态、优先级、阻塞原因等。
（ 3）现场信息（处理器状态信息）。 现场信息是用于保留进程存放在处理器中的各种信息，主要由处理器中的各个寄存器的内容组成。
（ 4）管理信息（进程控制信息）。 管理信息包括进程资源、控制机制等一些进程执行所需要的信息,程序和数据的地址、进程同步和通信机制,资源清单,链接指针等。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
3,进程控制块的组织方式。
（ 1）链接方式。 把具有相同状态的 PCB，用链接指针链接成队列，
如就绪队列、阻塞队列和空闲队列等。图 2-9给出了一种 PCB链接队列的组织方式。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
3,进程控制块的组织方式。
（ 2）索引方式。 系统根据各个进程的状态，建立不同索引表，例如就绪索引表、阻塞索引表等。并把各个索引表在主存的首地址记录在主存中的专用单元里，也可以称为表指针。在每个索引表的表目中，记录着具有相同状态的各个 PCB在表中的地址。图 2-
10给出了 PCB组织的索引方式。
第 2章 处理器管理
2.3 进程控制
2.3.1 进程控制块 PCB
4,进程控制原语。
原语 是指具有特定功能的不可被中断的过程。它主要用于实现操作系统的一些专门控制操作。用于进程控制的原语有：
（ 1）创建原语。 用于为一个进程分配工作区和建立 PCB，臵该进程为就绪状态。
（ 2）撤消原语。 用于一个进程工作完后，收回它的工作区和 PCB。
（ 3）阻塞原语。 用于进程在运行过程中发生等待事件时，把进程的状态改为阻塞状态。
（ 4）唤醒原语。 用于当进程等待的事件结束时，把进程的状态改为就绪状态。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销在系统中，只有进程才能得到运行。因此，程序想要执行，
就必须为之创建进程。进程执行结束，就必须撤消它。
1,进程的创建。
（ 1）引起进程创建的事件。 引起进程创建的事件有以下四类：
–用户登录。
–作业调度。
–提供服务。
–应用请求。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
1,进程的创建。
（ 2）进程创建的过程。 一旦操作系统发现了要求创建进程的事件后，便调用进程创建原语，按照下列步骤创建一个新进程。
① 为新进程分配惟一的进程标识符，并从 PCB队列中申请一个空闲的 PCB。
② 为新进程的程序和数据，以及用户栈分配相应的主存空间及其他必要的资源。
③ 初始化 PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。
④ 如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
2,进程的撤销。
（ 1）引起进程撤消的事件。 引起进程撤消的事件有三类：
–进程正常结束。
–在进程运行期间，由于出现某些错误和故障而使进程被迫中止。
–进程应外界的请求而终止运行。
第 2章 处理器管理
2.3 进程控制
2.3.2 进程的创建与撤销
2,进程的撤销。
（ 2）进程撤消的过程。 一旦操作系统发现了要求终止进程的事件后，便调用进程终止原语，按照下列步骤终止指定的进程。
① 根据被终止进程的标识符，从 PCB集合中检索该进程的
PCB，读出进程状态。
② 若该进程处于执行状态，则立即终止该进程的执行。
③ 若该进程有子孙进程，还要将其子孙进程终止。
④ 将该进程所占用的资源回收，归还给父进程或操作系统。
⑤ 将被终止进程的 PCB从所在队列中移出，撤消该进程的
PCB，并将其加入到空闲的 PCB队列中。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
1,进程的阻塞。
（ 1）引起进程阻塞的事件。 引起进程阻塞的事件有四类：
–请求系统服务。
–启动某种操作。
–新数据尚未到达。
–无新工作可做。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
1,进程的阻塞。
（ 2）进程阻塞的过程。 一旦操作系统发现了要求阻塞进程的事件后，便调用进程阻塞原语，按照下列步骤阻塞指定的进程。
① 立即停止执行该进程。
② 修改进程控制块中的相关信息。把进程控制块中的运行状态由“执行”状态改为“阻塞”状态，并填入阻塞的原因，以及进程的各种状态信息。
③ 把进程控制块插入到阻塞队列。根据阻塞队列的组织方式，
把阻塞进程的进程控制块插入阻塞队列中。
④ 转调度程序重新调度，运行就绪队列中的其他进程。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
2,进程的唤醒。
（ 1）引起进程唤醒的事件。 引起进程唤醒的事件有四类：
–请求系统服务得到满足。
–启动某种操作完成。
–新数据已经到达。
–有新工作可做。
第 2章 处理器管理
2.3 进程控制
2.3.3 进程的阻塞与唤醒
2,进程的唤醒。
（ 2）进程唤醒的过程。 一旦操作系统发现了要求唤醒进程的事件后，便调用进程唤醒原语，按照下列步骤唤醒指定的进程。
① 从阻塞队列中找到该进程。
② 修改该进程控制块中的相关内容，把阻塞状态改为就绪状态，删除阻塞原因等。
③ 把进程控制块插入到就绪队列中。按照就绪队列的组织方式，把被唤醒的进程的进程控制块插入到就绪队列中。
第 2章 处理器管理返回
2.4 进程的同步与互斥
2.4.1 进程的并发性并发进程相互之间可能没有关系，也可能存在某种关系。如果进程间彼此毫无关系，互不影响，这种情况不会对系统产生什么影响，通常不是要研究的对象。如果进程间彼此相关，互相影响，那么就需要进行合理的控制和协调才能正确执行。进程间的关系可以分为：
（ 1）资源共享关系。 系统中的某些进程需要访问共同的资源，即当一个进程访问共享资源时，访问该共享资源的其他进程必须等待，当这个进程使用完后，其他进程才能使用。这时要求进程应互斥地访问共享资源。
（ 2）相互合作关系。 系统中的某些进程之间存在相互合作的关系，
即一个进程执行完后，另一个进程才能开始。否则，另一个进程不能开始。这时就要保证相互合作的进程在执行次序上要同步。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
1．进程同步与互斥的定义对于相关进程间的同步和互斥，必须进行有效的控制。这种控制涉及几个基本概念，即临界资源、临界区、进程同步和进程互斥的概念。
（ 1）临界资源。 在系统中有许多硬件或软件资源，如打印机、公共变量等，这些资源在一段时间内只允许一个进程访问或使用，
这种资源称为临界资源。
（ 2）临界区。 作为临界资源，不论是硬件临界资源，还是软件临界资源，多个并发进程都必须互斥地访问或使用，这时把每个进程中访问临界资源的那段代码称为临界区。而这些并发进程中涉及临界资源访问的那些程序段称为相关临界区。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
1．进程同步与互斥的定义
（ 3）进程同步。 进程同步是指多个相关进程在执行次序上的协调，
这些进程相互合作，在一些关键点上需要相互等待或相互通信。
通过临界区可以协调进程间相互合作的关系，这就是进程同步。
（ 4）进程互斥。 进程互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待。当占用临界资源的进程退出临界区后，另一个进程才被允许使用临界资源。通过临界区协调进程间资源共享的关系，就是进程互斥。进程互斥是同步的一种特例。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
2．进程同步机制应遵循的原则
（ 1）空闲让进。 当无进程处于临界区时，临界资源处于空闲状态，
可以允许一个请求进入临界区的进程进入自己的临界区，有效地使用临界资源。
（ 2）忙则等待。 当已有进程进入自己的临界区时，意味着临界资源正被访问，因而其他试图进入临界区的进程必须等待，以保证进程互斥地使用临界资源。
（ 3）有限等待。 对要求访问临界资源的进程，应保证该进程在有效的时间内进入自己的临界区，以免陷入“死等”状态。
（ 4）让权等待。 当进程不能进入自己的临界区时，应立即释放处理器，以免陷入“忙等”。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
3．利用锁机制实现同步在众多的进程同步机制中，锁机制是一种最简单的机制。
（ 1）锁的概念。 在同步机制中，常用一个变量来代表临界资源的状态，称它为锁。通常用,0”表示资源可用，相当于锁打开。用
,1”表示资源已被占用，相当于锁闭合。锁机制的描述，如图 2-12
所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
3．利用锁机制实现同步
（ 2）对锁的操作。 对锁的操作有两种，一种是关锁操作，另一种是解锁操作。
关锁操作：
lock（ w）
{
test,if （ w==1） goto test；
else w=1；
}
解锁操作：
unlock(w)
{
w=0；
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 1）信号量的概念。 1965年，荷兰学者 Dijkstra提出的信号量机制是一种很有效的进程同步工具，得到了广泛的使用。这里将介绍最简单的经常使用的信号量 ——整型信号量。
信号量是一种特殊变量，它用来表示系统中资源的使用情况。
而整型信号量就是一个整型变量。当其值大于,0”时，表示系统中对应可用资源的数目；当其值小于,0”时，其绝对值表示因该类资源而被阻塞的进程的数目；当其值等于,0”时，表示系统中对应资源已经用完，并且没有因该类资源而被阻塞的进程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 2）对信号量的操作对于整型信号量，仅能通过两个标准的原语操作来访问，这两个操作被称为 P操作,V操作，也合称为 PV操作。其中 P操作在进入临界区前执行,V操作在退出临界区后执行。 PV操作如图 2-
13所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.2 同步与互斥的基本概念
4．利用信号量机制实现同步
（ 2）对信号量的操作
① P操作：记为 P(S)，其中 S为信号量，描述为：
P(S)
{ S=S-1;
if (S<0) W(S);
}
② V操作：记为 V(S)，其中 S为信号量，描述为：
V(S)
{ S=S+1;
if (S<=0) R(S);
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥进程互斥的原因是竞争临界资源。所以，实现进程互斥的关键是要描述临界资源的使用情况。若临界资源没有被占用，则允许进程访问，否则不允许进程访问，让该进程入阻塞队列。
【 例 2-4】 在一个只允许单向行驶的十字路口，分别有若干辆由东向西，由南向北的车辆等待通过。为了安全每次只允许一辆车通过。当有车辆通过时，其他车辆必须等候。当无车辆在路口行驶时，则允许一辆车通过。请用 PV操作设计一个十字路口安全行驶的自动管理系统。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 通过十字路口的车辆没有必然的先后次序，所以这是一个明显的互斥问题。十字路口即为临界资源，要求车辆每次最多通过一辆。由东向西，由南向北行驶的车辆为两个进程。
设互斥信号量 S表示临界资源十字路口，其初值为,1”表示十字路口可用。
算法描述如下：
int S = 1;
cobegin
Pew() /* 由东向西行驶车辆 */
//Psn() /* 由南向北行驶车辆 */
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
Pew()
{
P(S);
由东向西通过十字路口；
V(S);
}
Psn()
{
P(S);
由南向北通过十字路口；
V(S);
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-5】 有 4位哲学家围着一个圆桌在讨论问题和进餐，在讨论时每人手中什么都不拿，当需要进餐时，每人需要用刀和叉各一把。餐桌上的布臵如图 2-14所示，共有两把刀和两把叉，每把刀或叉供相邻的两个人使用。请用信号量及 PV操作说明 4位哲学家的同步过程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 分析：因哲学家就餐没有必然的先后次序，相邻的两个哲学家要竞争刀或叉，刀或叉就成为了临界资源，所以本题属于互斥问题。
解题步骤：（ 1）确定进程的个数及其工作内容。本题涉及 4个进程，每个哲学家为一个进程。哲学家 A的工作流程如图 2-
15所示。其他哲学家的工作流程与哲学家 A相似，只是拿起刀叉的序号不同。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定互斥信号量的个数、含义及 PV操作。在本题中应设臵 4
个互斥信号量 fork1,fork2,knife1,knife2，其初值均为,1”，分别表示叉 1、叉 2、刀 1、刀 2是可用的。
（ 3）用类 C语言描述互斥关系如下：
int fork1 = fork2 = 1;
int knife1 = knife2 = 1;
cobegin
Pa()
//Pb()
//Pc()
//Pd()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
Pa()
{
while(1)
{ P(knife1);
P(fork1);
进餐 ;
V(knife1);
V(fork1);
讨论问题 ;
}
}
第 2章 处理器管理
Pb()
{
while(1)
{ P(knife2);
P(fork1);
进餐 ;
V(knife2);
V(fork1);
讨论问题 ;
}
}
Pc()
{
while(1)
{ P(knife2);
P(fork2);
进餐 ;
V(knife2);
V(fork2);
讨论问题 ;
}
}
Pd()
{
while(1)
{ P(knife1);
P(fork2);
进餐 ;
V(knife1);
V(fork2);
讨论问题 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-6】 在南开大学和天津大学之间有一条弯曲的小路，其中从
S到 T有一段路每次只允许一辆自行车通过。但是，其中有一个小的安全岛 M（同时允许两辆自行车停留），可以供两辆自行车错车时使用，如图 2-16所示。试设计一个算法以确保来往自行车的顺利通过。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 解 】 分析：在本题中，需要控制路段 T到 L,S到 K及安全岛 M的使用。路段 T到 L,S到 K都只允许一辆自行车通过，而安全岛允许两辆自行车使用，两个路段和安全岛相当于临界资源。通过该路段的两个进程没有必然的先后次序，因此，本题属于互斥问题。
另外，为了保证安全岛上最多有两辆自行车，需要对相向行驶的两个方向进行控制，在每个方向上一次只允许一辆自行车通过。
此图可以简化为：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥解题步骤：（ 1）确定进程的个数及其工作。本题涉及两个进程：
从南大到天大、从天大到南大。其工作流程如图 2-17所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定互斥信号量的个数、含义及 PV操作。在本题中设臵 5个信号量 ST、
TS,K,L,M,ST表示是否允许自行车从南大到天大,TS表示是否允许自行车从天大到南大,K表示是否允许自行车通过路段 SK,L表示是否允许自行车通过路段 TL,M表示安全岛上还可以停放自行车的数目。
（ 3）用类 C语言描述算法如下：
int ST=1,TS=1;
int K=1,L=1;
int M=2;
cobegin
totian() /* 由南大到天大 */
//tonan() /* 由天大到南大 */
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
totian()
{
P(ST);
P(K);
从 S到 K;
P(M);
V(K);
进入安全岛 ;
P(L);
V(M);
从 L到 T;
V(L);
V(ST);
}
第 2章 处理器管理
tonan()
{
P(TS);
P(L);
从 T到 L;
P(M);
V(L);
进入安全岛 ;
P(K);
V(M);
从 K到 S;
V(K);
V(TS);
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
【 例 2-7】 某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及 PV操作描述这一组进程的工作过程。
【 解 】 分析：本题涉及对同一个数据库的读写操作。当多个进程对其读时，因不改变其中的数值，可以不加限制。当既有的读进程，又有写进程时，应加以限制。此时，数据库就是一个临界资源，读写进程必须对其进行互斥操作。因为写进程执行时，不能执行其他读写进程，所以还必须设臵一个计数器统计读进程的个数。如果是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。这是一个互斥问题，也是典型的读者和写者问题。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥解题步骤：（ 1）确定进程的个数及工作。本题只有读写两类进程，各自的工作如图 2-18所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
（ 2）确定信号量的个数、含义及 PV操作。本题应当设臵 2个信号量和 1个共享变量,count为共享变量，记录当前正在读数据库的进程数目； rmutex为读互斥信号量，使进程互斥地访问共享变量
count，其初值为 1；对于写进程与读进程、写进程与写进程来说，
数据库是临界资源，一次只能被一个进程使用。所以设臵 wmutex
为互斥信号量，其初值为,1”。所以，本题有两个临界资源：共享变量 count和数据库，对它们要实施互斥操作。
（ 3）用类 C语言描述同步关系。算法描述如下：
int rmutex=1;
int wmutex=1;
count=0;
cobegin
reader()
//writer()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
reader()
{
while(1)
{
P(rmutex); /* 获取对 count变量的操作 */
if (count==0) P(wmutex); /* 当第一个读进程读数据库时，竞争数据库 */
count++;
V(rmutex); /* 释放对 count变量的操作 */
读数据库；
P(rmutex); /* 获取对 count变量的操作 */
count--;
if (count==0) V(wmutex); /* 当最后一个读进程读完数据库时，释放数据库 */
V(rmutex); /* 释放对 count变量的操作 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
1．利用 PV操作实现进程互斥
writer()
{
while (1)
{
P(wmutex); /* 获取对数据库的操作 */
写数据库；
V(wmutex); /* 释放对数据库的操作 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步实现进程同步的 关键 是进程间执行次序的有效协调。当前一个进程执行完后，其后的进程才能执行。当前进程没有执行完，
其后的进程就不能执行。
【 例 2-8】 图 2-19给出了 4个进程合作完成某一任务的前趋图，试说明这 4个进程间的同步关系，并用 PV操作描述它们。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 方法一：用同步信号量来表示该进程是否可以开始。
设臵 4个同步信号量 b1,b2,b3,b4分别表示进程 P1,P2,P3,P4是否可以开始执行。因 P1无条件执行，所以 b1=1，其余信号量初值均为 0。这 4个进程的同步关系描述如下：
int b1=1;
int b2,b3,b4;
b2=b3=b4=0;
cobegin
P1()
//P2()
//P3()
//P4()
coend
第 2章 处理器管理
P1()
{
p(b1);
…
v(b2);
v(b3);
}
P2()
{
p(b2);
…
v(b4);
}
P3()
{
p(b3);
…
v(b4);
}
P4()
{
p(b4);
p(b4);
…
}
思考：哪个信号量可以省略？
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 方法二：用同步信号量来表示进程是否已经结束。
设臵 4个同步信号量 b1,b2,b3,b4分别表示进程 P1,P2,P3,P4是否执行结束，其初值均为,0”。这 4个进程的同步关系可以描述如下：
int b1,b2,b3,b4;
b1=b2=b3=b4=0;
cobegin
P1()
//P2()
//P3()
//P4()
coend
第 2章 处理器管理
P1()
{
…
v(b1);
v(b1);
}
P2()
{
p(b1);
…
v(b2);
}
P3()
{
p(b1);
…
v(b3);
}
P4()
{
p(b2);
p(b3);
…
v(b4);
}
思考：哪个信号量可以省略？
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 例 2-9】 桌子上有一个空盘子，只允许放一个水果。爸爸可以向盘子中放苹果，也可以向盘子中放桔子，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。规定当盘子为空时，一次只能放一个水果，请用 PV操作实现爸爸、儿子、女儿三个“并发进程”
的同步。
【 解 】 分析：这是一个明显的同步问题，也称为生产者和消费者问题。爸爸可以向盘子中放入两类水果：桔子、苹果；然后儿子、
女儿每人可以消费其中一种水果。爸爸是生产者，子女是消费者。
也就是只有爸爸放入水果，子女才能消费水果；只有子女消费完水果，爸爸才能再次放入水果，如此反复。
解题步骤如下：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 1）确定进程的个数及工作，用流程图的形式描述各进程的工作，如图 2-20所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 2）确定同步信号量的个数及含义。在流程图中标明对同步信号量的 PV操作。
设臵 3个同步信号量,Sp表示盘子是否为空，其初值为,1”，含义是爸爸是否可以开始放入水果,So表示盘子中是否有桔子，其含义是儿子是否可以开始取桔子，其初值为,0”表示不能取桔子； Sa 表示盘子中是否有苹果，其含义是女儿是否可以开始取苹果，其初值为,0”表示不能取苹果。
（ 3）用类 C语言描述同步关系如下：
int Sp = 1;
int Sa = 0;
int So = 0;
cobegin
father()
//son()
//daughter()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
father()
{
while(1)
{
P(Sp); /* 获取空盘子 */
将水果放入盘子中 ;
if (放入的是桔子 )
V(So); /*通知儿子吃桔子 */
else
V(Sa); /*通知女儿吃苹果 */
}
}
第 2章 处理器管理
son()
{
while(1)
{
P(So); /* 获取有桔子的盘子 */
从盘子中取桔子 ;
V(Sp); /*通知父亲放水果 */
吃桔子 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步第 2章 处理器管理
daughter()
{
while(1)
{
P(Sa); /* 获取有苹果的盘子 */
从盘子中取苹果 ;
V(Sp); /*通知父亲放水果 */
吃苹果 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 例 2-10】 有三个进程 PA,PB,PC合作解决文件打印问题，如图 2-21所示。 PA将文件记录从磁盘读入主存的缓冲区 1，每执行一次读一条记录； PB将缓冲区 1的记录复制到缓冲区 2，每执行一次复制一条记录； PC将缓冲区 2的记录打印出来，每执行一次打印一条记录；缓冲区的大小等于一条记录的 PA,PB,PC大小。请用 PV操作来保证文件的正确打印。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
【 解 】 分析：在本题中，进程 PA,PB,PC之间的同步关系为 PA
与 PB共用缓冲区 1，而 PB与 PC共用缓冲区 2。当缓冲区 1为空时，
进程 PA可以将记录读入其中；若缓冲区 1中有记录，进程 PB可以将记录从缓冲区 1中读出；当缓冲区 2为空时，进程 PB可以将记录复制到缓冲区 2中；当缓冲区 2中有记录时，进程 PC可以打印记录。
在其他条件下，相应进程必须等待。这是一个生产者与消费者和另一个生产者与消费者串联的问题，也是一个同步问题。 PA进程是生产者,PB进程既是消费者又是生产者,PC是消费者。
解题步骤：
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 1）确定进程的个数及工作，用流程图的形式描述各进程的处理工作，如图
2-22所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
（ 2）确定同步信号量的个数及含义。在流程图中标明对同步信号量的 PV操作。
本题设臵 4个信号量 e1,e2,f1,f2，信号量 e1,e2分别表示缓冲区 1和缓冲区
2是否为空，其初值为,1”；信号量 f1,f2分别表示缓冲区 1和缓冲区 2是否有记录可以处理，其初值为,0”。也可以理解为 e1表示 PA是否可以开始写,f1表示
PB是否可以开始读,e2表示 PB是否可以开始写,f2表示 PC是否可以开始读。
（ 3）用类 C语言描述同步关系如下：
int e1=1,e2=1;
int f1=0,f2=0;
cobegin
PA()
//PB()
//PC()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步
PA()
{
while (1)
{
从磁盘读取一条记录 ;
P(e1); /*获取缓冲区 1空的信息 */
将记录存入缓冲区 1;
V(f1); /*通知进程 PB读记录 */
}
}
第 2章 处理器管理
PB()
{
while (1)
{
P(f1);
从缓冲区 1读取一条记录 ;
V(e1);
P(e2); /*获取缓冲区 2空的信息 */
将记录存入缓冲区 2;
V(f2); /*通知进程 PC读记录 */
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
2．利用 PV操作实现进程同步第 2章 处理器管理
PC()
{
while (1)
{
P(f2);
从缓冲区 2读取一条记录 ;
V(e2);
打印记录 ;
}
}
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥当进程间同时存在同步和互斥两种关系时，也就是既具有竞争临界资源的关系，又具有相互合作的关系。此时，主要是协调同步操作和互斥操作的先后。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 例 2-11】 设有一个具有 N个信息元素的环形缓冲区（如图 2-23所示）,A进程顺序地把信息写进缓冲区,B进程依次从缓冲区中读出信息，请用 PV操作描述 A,B进程的同步。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 解 】 分析：这是一个具有多个缓冲空间的生产者消费者问题，也是一个同步加互斥的问题。 A,B 两个进程对缓冲区的访问必须互斥。并且当缓冲区满时,A进程不能写入，必须等待；当缓冲区空时,B进程不能读，必须等待，读写进程之间又是同步问题。
解题步骤：（ 1）确定进程的个数及工作。本题只有读、写两类进程，各自的工作如图 2-24所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
（ 2）确定信号量的个数、含义及 PV操作。本题设臵 3个信号量：互斥信号量 S
= 1（表示对缓冲区的互斥使用）；同步信号量 Sw（代表缓冲区是否有空闲，
即写进程能否写）,Sr（代表缓冲区是否有数据，即读进程能否读），假设初始时缓冲区没有任何数据，则 Sw = N,Sr = 0。设一个数组 array表示缓冲区，
两个整型变量 in,out表示写入和读出的位臵。
（ 3）用类 C语言描述同步关系如下：
#define N 10;
int array[N],in=0,out=0;
int S=1,Sw=N,Sr=0;
cobegin
PA()
//PB()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
PA()
{
while(1)
{
生产数据 M;
P(Sw); /* 申请写数据 */
P(S); /* 获取缓冲区 */
array[in] = 数据 M; /* 向缓冲区写数据 M */
in =(in+1)mod N; /* 调整写指针 */
V(S); /* 释放缓冲区 */
V(Sr); /* 通知进程 PB读数据 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
PB()
{
while(1)
{
P(Sr); /* 申请读数据 */
P(S); /* 获取缓冲区 */
M = array[out]; /* 从缓冲区读数据 */
out =(out+1)mod N; /* 调整读指针 */
V(S); /* 释放缓冲区 */
V(Sw); /* 通知进程 PA写数据 */
消费数据 M;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
【 例 2-12】 理发师理发问题。有一个理发师、一把理发椅和 n把等候理发顾客坐的椅子。如果没有顾客，则理发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师，进行理发；当理发师正在理发，又有顾客来到时，如果有空椅子，
顾客就可以坐下来等候，如果没有空椅子，他就离开。请为理发师和顾客各编一个程序表述他们的行为。
【 解 】 分析：本题涉及两个进程：理发师和顾客。当有顾客时理发师就可以理发，理完发后，从等候的顾客中选一位顾客继续理发。当理发师正在理发时，
顾客要等待，若没有座位就离开，顾客与理发师的工作是同步关系。有多少顾客在等候，需设计一个计数器来记录，顾客和理发师对计数器的操作是互斥的。
所以，这是一个同步加互斥的问题。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥解题步骤：
（ 1）确定进程的个数及工作。本题只有理发师和顾客两个进程，
各自的工作如图 2-25所示。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
（ 2）确定信号量的个数、含义及 PV操作。本题设臵 3个信号量,S1表示理发师是否可以开始理发，即是否有顾客； S2表示顾客是否可以被理发，即是否有理发师； S3是对计数器 waiting的互斥操作； waiting表示等待顾客的人数。
（ 3）用类 C语言描述同步关系。算法描述如下：
#define CHAIR 6 /* 为等候顾客准备的椅子数 */
int S1 = 0; /* 理发师同步信号量 */
int S2 = 0; /* 顾客同步信号量 */
int S3 = 1; /* 互斥信号量 */
int waiting = 0; /* 等待理发的人数 */
cobegin
barber()
// customer()
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
barber()
{
while(1)
{
P(S1); /* 理发师睡觉等待顾客的唤醒 */
P(S3); /* 获取计数器 waiting */
waiting = waiting – 1;
V(S3); /* 释放计数器 waiting */
V(S2); /* 把顾客叫到理发椅上 */
给顾客理发 ;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
3．利用 PV操作实现进程同步和互斥
customer( )
{ P(S3); /* 获取计数器 waiting */
If (waiting < CHAIR)
{ waiting = waiting + 1;
V(S3); /* 释放计数器 waiting */
V(S1); /* 通知理发师有顾客来了 */
坐下等候 ;
P(S2); /* 等待理发师的理发通知 */
上理发椅理发 ;
}
else
V(S3); /* 释放计数器 waiting */
离开 ;
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
4．利用 PV操作实现进程同步的方法
（ 1）使用 PV操作的规则：
① 分清哪些是互斥问题，哪些是同步问题。
② 对于互斥问题要设臵互斥信号量，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设臵几个互斥信号量，且初值为 1，代表临界资源可用。
③ 对于同步问题要设臵同步信号量，通常同步信号量的个数与参与同步的进程种类有关。同步信号量表示该进程是否可以开始或该进程是否已经结束。
④ 在每个进程中用于实现互斥的 PV操作必须成对出现；用于实现同步的
PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的 P操作，则其顺序不能颠倒。必须先执行对同步信号量的 P操作，再执行对互斥信号量的 P操作。但是,V操作的顺序没有严格要求。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.3 利用 PV操作实现互斥与同步
4．利用 PV操作实现进程同步的方法
（ 2）同步互斥问题的解题步骤：
① 确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。
② 确定同步互斥关系。根据使用的是临界资源，还是处理的前后关系，来确定互斥与同步，然后确定信号量的个数、含义，
以及对信号量的 PV操作。
③ 用类 C语言描述同步或互斥算法。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步引入管程的原因：
每个访问临界资源的进程都必须使用 PV操作，使得大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，还可能因同步操作使用不当而导致系统故障，如顺序不当、误写、
漏写等。为此，又产生了一种新的进程同步管理工具 ——管程。
1．管程的概念
1971年,Dijkstra提出，把所有进程中对某一种临界资源的同步操作都集中起来，构成一个所谓的“秘书”进程，凡是访问该临界资源的进程，都需要先报告“秘书”，由“秘书”来实现进程的同步。 1973年,Hansan和 Hoare又把“秘书”进程思想发展为管程的概念。
一个管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步管程的组成：
管程由三部分组成：局部于管程的共享变量说明、对该数据结构进行操作的一组过程、对局部于管程的数据设臵初始值的语句。此外，每个管程都有惟一的名字来标识。管程类似于面向对象程序设计中的类。
例如，学校的教务处就相当于管程。学校的各个教学部门需要安排什么课程，学生对教学有什么要求都向教务处提出申请，
由教务处统一协调各类教学资源的使用。这里各教学部门、学生相当于进程，教务处相当于管程。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题进程或者线程的阻塞和唤醒，可以通过管程的 wait和 signal 操作来巧妙地实现，所有管程中的过程是互斥的。利用管程实现同步，必须设臵两个同步操作原语：
（ 1） wait原语,当某进程通过管程请求获得临界资源而未得到满足时，管程调用该原语使该进程阻塞，并将它排在该临界资源的阻塞队列上。
（ 2） signal原语,仅当一个进程访问完成并释放临界资源时，管程才能调用该原语，唤醒阻塞队列上的队首进程。
为了区别阻塞的原因，需要设臵一个 条件变量 。条件变量是一个整型变量，用 condition说明，在条件变量上可以使用 wait和
signal操作原语。
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题管程定义的一般格式为：
monitor 管程类名 /* monitor是关键词 */
{
共享变量说明；
条件变量说明；
过程定义； /* 一般有多个 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-13】 利用管程机制解决例 2-11中的生产者与消费者问题。
【 解 】 设 in,out,count,buffer[]为共享变量，其中 buffer[]为缓冲区，即生产者和消费者的共享资源。 count为缓冲区产品的数量,in指示生产者存放产品的位臵，
out指示消费者取产品的位臵。 full,empty为条件变量。其中 full表示当缓冲区产品放满时，生产者排队； empty表示当缓冲区无产品时，消费者排队。 put()，
get()为两个对缓冲区的操作过程。其中 put()表示把产品放入缓冲区,get()表示从缓冲区取产品。
管程描述如下：
#define N 10
monitor producer_consumer /* 定义生产者 -消费者管程 */
{
int in=0,out=0,count=0,buffer[N];
conditioan full,empty; /* 定义条件变量 */
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
put(int item)
{
if (count>=N)
full.wait; /* 当缓冲区满时排队 */
buffer[in]=item;
in=(in+1)%N;
count++;
empty.signal; /* 唤醒消费者等待队列中的进程 */
}
get(int item)
{
if (count<=0)
empty.wait; /* 当缓冲区空时排队 */
item=buffer[out];
out=(out+1)%N;
count--;
full.signal; /* 唤醒生产者等待队列中的进程 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题生产者 —消费者描述为：
int item;
monitor producer_ consumer pc； /* pc为一个具体的生产者 -消费者管程 */
cobegin
producer() /* 生产者 */
{
while(1)
{
生产一个产品 item;
pc.put(item); /* 调用管程中的过程存放产品 */
}
}
//consumer() /* 消费者 */
{
while(1)
{
pc.get(item); /* 调用管程中的过程取产品 */
消费产品 item;
}
}
coend
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-14】 用管程机制解决例 2-7中的读者 —写者问题。
【 解 】 读者 —写者问题的条件是：当有读者读时，写者等待；当有写者写时，读者必须等待；当写者结束时，读者优先获取读；当读者结束时，写者之后的读者落后于写者。
其管程描述如下：
monitor reders_writers
{
int read_cnt=0; /* 当前读资源进程的数目 */
int writing=0; /* 是否有写者正在使用这个资源 */
condition read,write; /* 读者等待队列，写者等待队列 */
start_read() /* 开始读过程 */
{
if (writing||!empty(write)) /* 如果正在写或者有写者进程就阻塞读进程 */
read.wait;
read_cnt++;
read.signal; /* 唤醒一个读进程 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
end_read() /* 结束读过程 */
{
read_cnt=read_cnt-1;
if(read_cnt==0)
write.signal /* 唤醒一个写进程 */
}
start_write() /* 开始写过程 */
{
if ((read_cnt!=0)||writing) /* 如果正在写或者有读进程就阻塞写进程 */
write.wait;
writing=1;
}
end_write() /* 结束写过程 */
{
writing=0;
if (!empty(read)) /* 有读进程就唤醒 */
read.signal;
else /* 否则就唤醒写进程 */
write.signal;
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题在读者和写者中调用管程：
monitor readers_writers pc; /* 定义一个具体的读者 -写者管程 pc */
cobegin
readers()
// writers()
coend
readers()
{
while(1)
{
pc.start_read(); /* 调用开始读过程 */
读数据库；
pc.end_read(); /* 调用结束读过程 */
}
}
writers()
{
while(1)
{
pc.start_write(); /* 调用开始写过程 */
写数据库；
pc.end_write(); /* 调用结束写过程 */
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
【 例 2-15】 用管程机制解决例 2-5中 4位哲学家就餐问题。
【 解 】 请读者分析管程中使用的共享变量、条件变量和定义的过程。
monitor dining_philosophers
{
enum status
{
thinking,hungry,eating } state[4]; /* 共享变量 */
condition self[4]; /* 条件变量 */
for(int i=0;i<4;i++) /* 设臵初始状态 */
state[i]=thinking;
pickup(int i) /* 申请吃饭过程 */
{
state[i]=hungry;
test(i); /* 调整其状态 */
if (state[i]!=eating)
self[i].wait; /* 推迟自己进餐 */
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题
putdown(int i) /* 放下筷子的处理过程 */
{
sate[i]=thinking;
test((i+4)%4); /* 调整其前者状态 */
test((i+1)%4); /* 调整其后者状态 */
}
test(int i) /* 调整状态 */
{
if(state[(i+4)%4]!=eating && state[i]==hungry && state[(i+1)%4] != eating)
{
state[i]=eating;
self[i].signal;
}
}
}
第 2章 处理器管理
2.4 进程的同步与互斥
2.4.4 利用管程实现同步
2．利用管程实现经典的同步问题在并发进程中调用管程：
monitor dining_philosophers pc; /* 定义一个具体的管程 pc */
cobegin
p0() // p1() // p2() //p3()
coend
pi() /* 第 i个哲学家进程（ i=0-3） */
{
while(1)
{
讨论 ;
pc.pickup(i);
吃饭 ;
pc.putdown(i);
思考 ;
}
}
第 2章 处理器管理返回
2.5 进程通信进程通信 是指进程间的信息交换。根据通信的机制不同将进程通信分为低级通信和高级通信。进程的同步与互斥称为 低级通信 。用户直接利用操作系统提供的一组通信命令，高效地传送大量数据，称为高级通信 。
2.5.1 共享存储器系统在 共享存储器系统 中，相互通信的进程共享某些数据结构或存储区，进程之间能够通过它们进行通信。
1．共享数据结构方式在这种通信方式下，相互通信的进程共用某些数据结构，并通过这些数据结构交换信息。这种方式与信号量机制相比，并没有发生太大的变化，比较低效、复杂，只适用于传送少量的数据。
2．共享存储区方式这种通信方式是在存储器中划出一块共享存储区，相互通信的进程可以通过对共享存储区中的数据进行读或写来实现通信。这种方式效率高，可以传送较多的数据。
第 2章 处理器管理
2.5 进程通信
2.5.2 消息传递系统在 消息传递系统 中，进程间的数据交换是以消息为单位进行的。
用户直接利用系统中提供的一组通信命令（原语）进行通信。
1．直接通信方式发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程使用接收原语从消息缓冲队列中取出消息。通常，系统提供两条通信原语：
发送原语,Send（ Receiver,message）；
接收原语,Receive（ Sender,message）；
例如：原语 Send（ P2,m）表示将消息 m发送给接收进程 P2；
而原语 Receive（ P1,m）则是表示接收由进程 P1发送来的消息 m。
第 2章 处理器管理
2.5 进程通信
2.5.2 消息传递系统
2．间接通信方式发送进程使用发送原语直接将消息发送到某种中间实体中。接收进程使用接收原语从该中间实体中取出消息。这种中间实体一般称为信箱。所以，这种方式也称为信箱通信方式，并且被广泛地用于计算机网络中（即电子邮件系统）。
（ 1）信箱通信的操作。 系统为信箱通信提供了若干条操作原语，
包括创建信箱原语、撤消信箱原语、发送原语、接收原语等。
（ 2）信箱的分类。 信箱可以由操作系统创建，也可以由用户创建。创建者是信箱的拥有者，据此，可以把信箱分为以下三类：私有信箱,公用信箱 和共享信箱 。
（ 3）进程间的关系。 当利用信箱通信时，发送进程与接收进程存在下列关系：一对一,多对一,一对多和多对多。
第 2章 处理器管理
2.5 进程通信
2.5.3 管道通信系统管道 是指连接读进程和写进程的，用于实现它们之间通信的共享文件。向管道提供输入的发送进程（写进程），以字符流的形式将大量数据送入管道，而接受管道输出的接收进程（读进程），可以从管道中接收数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信方式。 这种方式首创于 UNIX系统，因为它能传送大量的数据，又非常有效，所以又被引入到许多操作系统中。
作为人类社会，每个人可以看成是一个或一组进程，相互之间存在着千丝万缕的关系：或互斥地访问使用社会资源，或共同协调地进行社会工作。所以，人们在社会环境中，也要进行有效的控制与协调，
每个人（进程）要学会与他人共享社会资源，也要学会与他人进行有效的交流（通信），否则将不能很好地工作和生活。
第 2章 处理器管理返回
2.6 进程调度进程调度 又称为低级调度，它决定主存中就绪队列上的哪个进程（单处理器系统）获得处理器，开始执行。
2.6.1 进程调度算法的构成进程调度算法 是根据系统的资源分配策略确定的资源分配算法。一个进程调度算法必须明确两个问题,一是 何时调度的问题。
二是 调度谁的问题。何时调度是确定什么时候执行进程调度算法的问题，这是由裁决模式决定的。调度谁是确定选择哪个进程的问题，这是由优先权函数和仲裁规则共同控制的。
1．裁决模式裁决模式明确了计算与比较进程优先权的时间点，以及选择执行进程的时间点。裁决模式分为抢占式的和非抢占式的。
当采用 非抢占方式 时，一旦把处理器分配给某个进程后，便让该进程一直执行，直到该进程终止或阻塞才退出处理器，系统才能把处理器分配给其他进程。
第 2章 处理器管理
2.6 进程调度进程调度 又称为低级调度，它决定主存中就绪队列上的哪个进程（单处理器系统）获得处理器，开始执行。
2.6.1 进程调度算法的构成
1．裁决模式当采用 抢占方式 时，把处理器分配给某个进程后，在该进程尚未终止时，允许系统调度程序根据某种原则，暂停正在执行的进程，回收处理器，并将处理器重新分配给更为紧急的进程。
2．优先权函数当优先权函数应用到某个进程时，便产生一个数值。这个数值表示该进程的当前优先权。函数可以把进程或系统的不同属性作为参数来产生优先权值。这些属性包括：运行时间,周转时间,
截止期,响应时间,外部优先权,内存需求 。
3．仲裁规则仲裁规则是解决具有相同优先权进程间冲突的规则。根据不同情况采用的规则有随机规则、轮转规则、先进先出规则。
第 2章 处理器管理
2.6 进程调度
2.6.2 进程调度算法的选取原则
1．面向用户的原则。 这是为满足用户的需求而遵循的一些准则。它包括：
（ 1）周转时间短。 所谓周转时间，是指从进程提交给系统开始，到进程完成为止的这段时间。它包括等待时间和运行时间，主要用于评价批处理系统。
（ 2）响应时间快。 响应时间是指从用户通过键盘提交一个请求开始，
直至系统首次产生响应为止的时间（进程首次运行前的等待时间），
即系统在屏幕上显示出结果为止的一段时间间隔。它主要用于评价分时操作系统。
（ 3）截止时间有保证。 截止时间是指进程必须开始执行的最迟时间，
或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须保证这一点。否则，有可能引起灾难性的后果。它主要用于评价实时操作系统。
（ 4）优先权原则。 采用优先权原则，目的是让某些紧急的进程，得到及时处理。在要求严格的系统中，还要使用抢占调度方式，才能保证紧急进程得到及时处理。它用于批处理、分时和实时系统。
第 2章 处理器管理
2.6 进程调度
2.6.2 进程调度算法的选取原则
2．面向系统的原则。 这是为了满足系统要求而遵循的一些准则。它包括：
（ 1）系统吞吐量高。 系统吞吐量是指系统在单位时间内所完成的进程数量。显然进程的平均长度将直接影响到系统吞吐量的大小。另外进程调度的方式与算法，也会对系统吞吐量产生较大的影响。它主要用于评价批处理系统。
（ 2）处理器利用率高。 对于大、中型系统，由于 CPU价格昂贵，所以处理器的利用率就成为十分重要的指标。在实际系统中,CPU的利用率一般在 40%～ 90%之间。但是，该准则一般不用于微机系统和某些实时系统，它主要用于大、中型系统。
（ 3）各类资源的平衡利用。 对于大、中型系统，不仅要使处理器利用率高，而且还应能有效地利用其他各类资源，保持系统中各类资源都处于忙碌状态。同样，该准则一般不用于微机系统和某些实时系统，它主要用于大、中型系统。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
1．先来先服务调度算法（ FCFS）
先来先服务调度算法是一种最简单的调度算法，系统开销最少。
当系统采用这种调度算法时，系统从就绪队列中选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。进程一旦占有了处理器，就一直运行下去，直到完成或因发生某种事件而阻塞，才退出处理器。
先来先服务调度算法的 裁决模式 是非抢占式的,优先权函数 =花费在系统中的实际时间,仲裁规则 是随机的。这种调度算法有利于长进程，而不利于短进程。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
2．短进程优先调度算法（ SPF）
短进程优先调度算法是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行。直到该进程完成或因发生某种事件而阻塞，才退出处理器。
短进程优先调度算法的 裁决模式 是非抢占式的,优先权函数 ＝ -
运行时间,仲裁规则 是按照时间先后顺序或随机方式。这种调度算法照顾到了系统中的短进程，有效地降低了进程的平均等待时间，
提高了系统的吞吐量。但是，这种算法对长进程不利。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
3．最短剩余时间优先调度算法（ SRT）
最短剩余时间优先调度算法是短进程优先调度算法的抢占式的动态版本。它将 CPU分配给需要最少时间来完成的进程。
最短剩余时间优先调度算法的 裁决模式 是抢占式的,优先权函数 是动态的，随着进程运行和完成时间的减少而增加,仲裁规则 是按照时间先后顺序或随机方式。这种调度算法充分照顾到了剩余运行时间短的进程。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
4．时间片轮转调度算法（ RR）
在分时系统中，为了保证人机交互的及时性，系统使每个进程依次按照时间片方式轮流执行，即时间片轮转调度算法。在该算法中，系统将所有的就绪进程按照进入就绪队列的先后次序排列。每次调度时把 CPU分配给队首进程，让其执行一个时间片。当时间片用完，由计时器发出时钟中断，调度程序暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。
然后，把 CPU分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一定的时间
（可以接受的等待时间）内，均能获得一个时间片的执行时间。
时间片轮转调度算法的 裁决模式 是面向时间片的，所有就绪进程的 优先权函数 值相同,仲裁规则 是轮转规则。这种调度算法适用于交互进程的调度。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
5．优先权调度算法为了照顾紧迫型进程获得优先处理，引入了优先权调度算法，
也称为外部优先权调度算法。它是从就绪队列中选择一个优先权最高的进程，获得处理器并执行。
优先权调度算法的 裁决模式 是抢占式的或非抢占式的,优先权函数 是用户或系统赋给它的优先权,仲裁规则 是随机的或先进先出的。
对于优先权调度算法，其关键在于是采用静态优先权，还是动态优先权，以及如何确定进程的优先权。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
6．响应比高者优先调度算法（ HRRN）
响应比高者优先调度算法是一个比较折衷的算法，它是从就绪队列中选择一个响应比最高的进程，让其获得处理器并执行，直到该进程完成或因等待某种事件而退出处理器为止。响应比 = 响应时间 / 要求服务时间。
响应比高者优先调度算法的 裁决模式 是非抢占式的,优先权函数
=响应比,仲裁规则 是随机或按照先后次序。
这种调度算法既照顾了短进程，又考虑了进程到达的先后次序，
也不会使长进程长时间得不到服务。因此，它是一个考虑比较全面的算法。但是每次进行调度时，都需要对各个进程计算响应比。所以，系统开销很大，比较复杂。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
7．多级队列调度算法（ ML）
目前的计算机系统，不少都同时具有多种操作方式，既具有批处理操作方式，用于处理批量型作业；又具有分时操作方式，用于处理交互型作业。但是，这两种作业的性质却截然不同。通常，为批处理作业所建立的进程将排入后台的就绪队列；而为交互型作业所建立的进程则排入前台的就绪队列。前台采用时间片轮转调度算法，而后台采用优先权调度算法或短进程优先调度算法等。
一般来说，多级队列调度算法是根据进程的类型或性质不同，
将就绪进程分为若干个独立队列，不同类型或性质的进程固定地属于一个队列。每个队列可以采用适合自己要求的调度算法。不同的队列可以使用不同的调度算法。
在采用多级队列调度算法时，可以按照多种方式来处理各队列间的关系。一种是规定每个队列的优先权，优先权高的队列将优先获得调度执行。另一种是为各队列分配一定比例的处理器时间，然后分别调度使用。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
8．多级反馈队列调度算法（ MLF）
前面所介绍的各种进程调度算法，都存在一定的局限性。如短进程优先调度算法，不利于长进程，而且如果没有有效地表明进程的长度，其算法将无法正常使用。而多级反馈队列调度算法，则不必事先知道各个进程所需的执行时间，可以满足各种类型进程的需要，是目前一种较好的进程调度算法。
多级反馈队列调度算法的 裁决模式 是抢占式的或非抢占式的，
优先权函数 是从最大值开始每执行一次递减 1,仲裁规则 是轮转的或按照时间先后次序。
这种调度算法具有较好的性能，能满足各种类型用户的需求。
第 2章 处理器管理
2.6 进程调度
2.6.3 常用的进程调度算法
【 例 2-16】 3个批处理进程 P1,P2,P3具有下列到达时间和要求运行时间，请按照先来先服务（ FCFS）、短进程优先（ SPF）和最短剩余时间优先（ SRT）调度算法，画出其时序图，并计算它们的平均周转时间。
【 解 】 三种调度算法的时序图如图 2-27所示。
第 2章 处理器管理返回
2.7 进程死锁
2.7.1 死锁的基本概念
1．死锁的概念死锁 是指多个进程因竞争资源而造成的一种僵局现象，若无外力的作用，这些进程都不能继续执行。
2．死锁的原因
（ 1）竞争资源。当系统中供多个进程共享的资源不足以同时满足它们的需求时，引起它们对资源的竞争而产生死锁。
（ 2）进程推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，会导致进程死锁。
第 2章 处理器管理
2.7 进程死锁
2.7.1 死锁的基本概念
3．产生死锁的必要条件死锁并不一定都会出现，如果一旦产生死锁，一定会满足下述
4个必要条件。
（ 1）互斥条件。 进程对分配到的资源进行排他性、独占性使用。即在一段时间内某资源只能由一个进程占用，如果此时还有其他进程请求使用该资源，请求者只能等待，直到占有该资源的进程用完后释放，才能使用该资源。
（ 2）请求和保持条件。 进程已经拥有并保持了至少一个资源，但是，
又请求新的资源，而新请求的资源又被其他进程占有，此时请求进程被阻塞，但是，对已获得的资源保持不放。
（ 3）不剥夺条件。 进程所占有的资源，在结束之前不能被剥夺，只能在运行结束后由自己释放。
（ 4）环路等待条件。 在发生死锁时，必然存在一个“进程 ——资源”
的环形链。
第 2章 处理器管理
2.7 进程死锁
2.7.1 死锁的基本概念
4．处理死锁的基本方法目前用于处理死锁的方法分为三种。
（ 1）预防死锁。 预防死锁是在进行资源分配之前，通过设臵某些资源分配的限制条件，来破坏产生死锁的四个必要条件的一个或几个。
预防死锁是一种较简单的方法，容易使用，但是，由于施加了限制条件，会导致系统资源利用率和吞吐量的下降。
（ 2）避免死锁。 避免死锁是在资源分配前不设臵限制条件，在进行资源分配的过程中，用某种方法对每次资源分配进行管理，以避免某次分配使系统进入不安全状态，以至产生死锁。这种方法限制较小，可以获得较好的系统资源利用率和吞吐量。目前比较完善的系统中，通常采用此种方法。
（ 3）检测和解除死锁。 首先是通过系统的检测过程及时地检查系统是否出现死锁，并确定与死锁有关的进程和资源；然后，通过撤消或挂起一些死锁中的进程，回收相应的资源，进行资源的再次分配，
从而将进程死锁状态解除。这种方法没有限制，可以获得较好的系统资源利用率和吞吐量，但是实现难度较大。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防通过对资源分配的原则进行限制，而使产生死锁的四个必要条件中的第 2,3,4个条件之一不能成立，来预防产生死锁。
1．破坏“不剥夺”条件一个已经占有某些资源的进程，当它再提出新的资源需求而不能立即得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请。这意味着进程已经拥有的资源，在运行过程中可能会暂时被迫释放，即被系统剥夺，从而摒弃了“不剥夺条件”。
这种预防死锁的方法，实现起来比较复杂，并付出较大的代价，
会使前段时间的工作失效等。此外这种方法还会因为反复地申请和释放资源，延长进程的周转时间，增加系统开销，降低系统吞吐量。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防
2．破坏“请求和保持”条件系统要求进程必须一次性地申请其在整个运行期间所需要的全部资源。若系统有足够的资源，便一次性将其所需要的所有资源分配给该进程，这样一来，该进程在整个运行过程中，便不会再提出资源请求，从而摒弃了“请求”条件。而在分配时，只要有一个资源要求不能满足，系统将不分配给该进程任何资源，此时进程没有占有任何资源，因而也摒弃了“保持”条件，所以，可以预防死锁的产生。
这种预防死锁的方法，简单方便、易于实现，但是，因为进程将一次性获得所有资源，并且独占使用，其中可能有些资源在该进程运行期间很少使用，造成资源严重浪费；同时有些进程因不能一次性获得所需要的资源，导致长时间不能投入运行。
第 2章 处理器管理
2.7 进程死锁
2.7.2 死锁的预防
3．破坏“环路等待”条件在这种方法中规定，系统将所有的资源按照类型进行线性排序，
赋予不同的资源序号。并且所有进程对资源的请求和分配必须严格的按照资源序号由小到大地进行，即只有先申请和分配到序号小的资源，才能再申请和分配序号大的资源。这样在最后形成的资源分配图中，将不可能再出现环路，从而摒弃了“环路等待”条件。
这种预防死锁的方法与前两种相比，其资源利用率和系统吞吐量，都有明显的改善。但是，这种方法涉及对各类资源的排序编号，
考虑到实际的使用，其排序的合理性将受到很大的挑战。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免在死锁的避免中，所施加的限制较弱，可以获得较好的系统性能。
该方法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免死锁发生。
1．安全状态与不安全状态安全状态 是指系统能够按照某种顺序为每个进程分配所需要资源,
直到最大需求,使每一个进程都可以顺利完成 。 反之,如果系统不存在这样的一个安全序列,则称系统处于 不安全状态 。
当系统进入不安全状态后,很有可能进入死锁状态；反之,只要系统处于安全状态,便可避免进入死锁状态 。 因此,避免死锁的实质就是如何使系统不进入不安全状态 。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
2．利用银行家算法避免死锁最具代表性的避免死锁的算法是 Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。
（ 1）银行家算法采用的数据结构。银行家算法采用的数据结构有最大需求向量 Max、已分配资源向量 Allocation、还需资源向量 Need和可用资源向量 Available。 如表 2-4所示 。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
2．利用银行家算法避免死锁
（ 2）银行家算法的处理步骤
① 列出某一时刻的资源分配表，格式如表 2-4所示。
② 拿可用资源量与每一个进程的还需资源量进行比较，可用资源量不少于还需资源量时，把资源分配给该进程。新的可用资源量为原有可用资源量加上该进程已分配的资源量。
③ 重复②，直到所有进程都执行完毕或系统可用资源量小于每一个剩余进程的还需资源量，即可判断能否获得一个安全资源分配序列。
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
3．银行家算法举例
【 例 2-17】 假定系统中有 5个进程 P0,P1,P2,P3,P4和 3种类型的资源 A,B,C，每一种资源的数量分别为 10,5,7，在某一时刻资源分配情况如下表所示，利用银行家算法，判断是否有一个资源分配的安全序列？
第 2章 处理器管理
2.7 进程死锁
2.7.3 死锁的避免
3．银行家算法举例
【 解 】 系统可用的资源量为 （ 3,3,2）,根据银行家算法可以与每个进程的还需资源量进行比较,分配,如下表所示：
资源分配序列 {P1,P3,P4,P2,P0}是安全的 。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除当系统为进程分配资源时，如果没有采取任何限制措施，系统必须提供死锁的检测与解除机制。
1．死锁的检测在进行死锁的检测时，系统必须能保存有关资源的请求和分配的信息，并提供一种算法，以便利用这些信息来检测系统是否进入死锁状态。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 1）资源分配图。 系统死锁可以利用资源分配图来描述。该图是由一组方框、圆圈和一组箭头线组成的，如图 2-30所示。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 1）资源分配图。 资源分配图采用图素的含义分别是：
–方框,表示资源。有几类资源就画几个方框，方框中的小圆圈表示该类资源的个数。当个数较大时可以在方框内用阿拉伯数字表示。
–圆圈,表示进程。有几个进程就画几个圆圈，圆圈内标明进程名称。
–箭头线,表示资源的分配与申请。由方框指向圆圈的箭头线表示资源的分配线，由圆圈指向方框的箭头线表示资源的请求线。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
1．死锁的检测
（ 2）死锁定理。 在死锁检测时，可以利用把资源分配图进行简化的方法来判断系统当前是否处于死锁状态。具体方法如下：
① 在资源分配图中，找出一个既非阻塞又非孤立的进程结点 Pi。
如果 Pi可以获得其所需要的资源而继续执行，直至运行完毕，就可以释放其所占用的全部资源。这样，就可以把 Pi所有关连的资源分配线和资源请求线消去，使之成为孤立的点。
② 重复进行上述操作。在一系列的简化后，如果消去了资源分配图中所有的箭头线，使所有进程结点都成为孤立结点，则称该资源分配图是可完全简化的；反之，则称该资源分配图是不可完全简化的。
如果当前系统状态对应的资源分配图是不可完全简化的，则系统处于死锁状态，该充分条件称为 死锁定理 。
第 2章 处理器管理
2.7 进程死锁
2.7.4 死锁的检测与解除
2．死锁的解除当检测到系统发生死锁时，就必须立即把死锁状态解除，常用的方法是：
（ 1）剥夺资源法。 从其他进程剥夺足够数量的资源给死锁进程，使其得到足够的资源，然后继续执行，以解除死锁状态。
（ 2）撤消进程法。 系统采用强制手段将死锁进程撤消。最简单的方法是将全部死锁进程一次性撤消，但是，代价较大；另一种方法是按照一定的算法，从死锁进程中一个一个地选择进行撤消，并同时剥夺这些进程的资源，直到死锁状态解除为止。
第 2章 处理器管理返回
2.8 线程、超线程和双核的基本概念
2.8.1 线程
1．线程的引入进程作为系统中的一个基本单位，具有两个属性：一是资源分配和拥有的基本单位。二是一个可以独立调度和执行的基本单位。
而在进程操作过程中，因为进程是一个资源的拥有者，所以，
系统要不断地进行资源的分配与回收、现场的保存与恢复等工作。
系统要为此付出较大的时间与空间的开销。另外，在系统中所设臵的进程数目不能过多，进程切换的频率也不能过高，这就限制了系统并发程度的进一步提高。
如何能使进程更好地并发执行，同时又能尽量减少系统开销呢？
一些学者设想将进程的两个属性分开，由操作系统分别处理，即只作为资源分配与拥有的单位，不再是调度和执行的基本单位，使之轻装前进；而对资源分配与拥有的基本单位，不进行频繁的切换处理，以减少系统开销。正是因为这种思想，产生了一个新的概念 —
—线程 。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
2．线程的概念线程 是进程中的一个实体，是被系统独立调度和执行的基本单位。
线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但是它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。
一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。线程之间也会相互制约，使其在运行中呈现异步性。因此，线程同样具有就绪、执行、阻塞三种基本状态。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
3．线程与进程的比较线程具有许多传统进程的特征，所以又称为 轻型进程 。传统的进程称为重型进程，相当于只有一个线程的任务。在引入线程的操作系统中，通常一个进程拥有若干个线程，至少也有一个线程。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.1 线程
4．线程的类型
（ 1）系统级线程。 系统级线程是依赖于系统控制的，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤消与切换都是由系统控制实现的。在系统中保留了一张线程控制块，系统根据该线程控制块来感知线程的存在，并对线程进行控制。
（ 2）用户级线程。 用户级线程是由用户控制的，对于用户级线程的创建、撤消与切换，都与系统控制无关，完全由用户自己管理。简单来说就是系统并不知道有用户级线程的存在，在系统中各种控制仍然是基于进程的。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术
1．超线程的概念超线程技术是 Intel在 2002年发布的一项新技术，它率先在 Intel
的 XERON处理器上得到应用。
所谓 超线程技术 就是利用特殊的硬件指令，在一个实体处理器中放入两个逻辑处理单元，从而模拟成两个工作环境，让单个处理器能使用线程级的并行计算，同时处理多项任务，提升处理器资源的利用率。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术
2．超线程的工作超线程是同时多线程技术的一种，这种技术可经由复制处理器上的结构状态，让同一个处理器上的多个线程同步执行，并共享处理器的执行资源。
对支持多处理器功能的应用程序而言，超线程处理器被视为两个分离的逻辑处理器。应用程序无须修正就可以使用这两个逻辑处理器。同时，每个逻辑处理器都可以独立响应中断。第一个逻辑处理器可追踪一个软件线程，而第二个逻辑处理器则可以同时追踪另一个软件线程。由于两个线程共同使用同样的执行资源，因此不会产生一个线程执行而另一个线程闲臵的状况。这种方式可以大大提升每个实体处理器中执行资源的使用率。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.2 超线程技术最近,AMD针对以往 Intel的超线程技术，又提出了逆超线程技术。超线程技术是系统将一颗 CPU看成两颗，而逆超线程技术是要将两个物理核心看作一颗，同时处理一项工作，以便在特定情况下提高速度。
第 2章 处理器管理
2.8 线程、超线程和双核的基本概念
2.8.3 双核技术所谓 双核技术,简单地说就是在一块 CPU基板上集成两个处理器核心，并通过并行总线将各处理器核心连接起来的技术。双核心并不是一个新概念，而只是单芯片多处理器中最基本、最简单、最容易实现的一种类型。
如果说超线程技术是通过软件模拟出双核的效果，那么现在所说的双核技术就是真正意义上的两个核心。它弥补了超线程技术适用系统比较少的缺点，可以广泛用于 windows操作系统的多个版本。
它还有效的解决了双核运算中出现的缓存分离与数据冲突错误的问题。
目前，还出现了一种 双 CPU技术 。前面所说的双核技术是在一个处理器里拥有两个处理器核心，核心是两个，但是其他硬件还都是一套，由两个核心在共同拥有。而双 CPU则是真正意义上的双核心，不只是处理器核心是两个，其他如缓存等硬件配臵也都是双份的。这样系统处理的效率会更高。
第 2章 处理器管理返回
