计算机软件技术基础-课件 11ch6(2)-OS

第6章处理器管理（2）6.1进程的概念

6.2进程的状态和转换

6.3进程的控制

6.4进程的协调

6.5进程间的通信

6.6进程的安全性

6.7线程的概念

6.8作业管理

6.9处理器调度进程管理6.4进程的协调

6.4.1进程互斥

6.4.2进程同步

6.4.3信号量和P、V操作6.4进程的协调概述：

在多道程序设计系统中，许多进程可并发执行，但由于资源共享和进程合作，而产生了进程之间的两类相互制约的关系:

互斥关系 同步关系6.4进程的协调(1)互斥关系（竞争关系）:间接制约关系。指进程之间因相互竞争使用系统资源（独占型资源），而产生的制约关系。主要由资源共享引起。表现形式：“进程——资源——进程”。进程间的间接相互作用构成进程互斥。进程互斥(mutualexclusion)：若干进程因相互争夺独占型资源(打印机、共享变量等)而产生的竞争制约关系。资源竞争会引发两个控制问题：死锁(deadlock)

一组进程如果都获得部分资源，还想要得到其他进程所占有的资源，最终所有进程将陷入永远等待的状态。饥饿(starvation)

一个可运行进程由于其它进程总是优先于它，被调度程序无限期的拖延而不能被执行。进程的协调(2)同步关系(协作关系):一个用户作业可以涉及一组并发进程，它们为了完成共同的任务需要分工协作。例：有A、B两个进程，A进程负责从键盘读数据到缓冲区，B进程负责从缓冲区读数据进行计算。要完成取数据并计算的工作，A进程和B进程要协同工作。即B进程只有等待A进程把数据送到缓冲区后才能进行计算。A进程只有等待B进程发出已把缓冲区数据取走的信号之后才能从键盘向缓冲区中送数据，否则就会出现错误。由于每个进程都独立地以不可预知的速度推进，在执行的先后次序上就要有约束，需要相互协作的进程在某些关键点上协调各自的工作。当其中的一个进程到达关键点后，在尚未得到协作进程发来的消息（或信号）之前应阻塞自己，等待协作进程发来消息后方被唤醒继续执行。这种协作进程之间需要排定执行先后次序的协调关系是直接制约关系，称为进程同步。进程的协调(2)同步关系(协作关系):进程同步（synchronization）是指，为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号（或消息）所产生的相互制约关系。可由资源共享引起，也可由进程合作引起。各个进程的行动时间次序必须满足某种依赖关系。表现形式：“进程——进程”进程间的直接作用构成进程的同步。注：进程互斥关系（逐次使用互斥共享资源）是一种特殊的进程同步关系6.4.1进程互斥1.进程互斥与临界区进程互斥在系统中，许多进程常常需要共享资源，而这些资源往往要求排它地使用，即一次只能为一个进程服务。因此，各进程间互斥使用这些资源，进程间的这种关系是进程的互斥。临界资源和临界区

临界资源（criticalresource）：

一次仅允许一个进程使用的资源称为临界资源。许多物理设备（如打印机、光盘刻录机等）和软件资源（如变量、数据、队列等）都具有这种独占性的特点。

临界区(criticalsection)：（Dijkstra于1965年首次提出） 在进程中访问临界资源的那段代码称为临界区。要注意区分临界资源与临界区。2互斥的概念与要求进程的互斥（临界区、临界资源）系统中，当一个进程先进入临界区使用临界资源时，另一个进程必须等待；当占用临界资源的进程退出临界区后，另一进程才允许访问此临界资源。2互斥的概念与要求互斥进程进入临界区的准则/要求：①空闲让进。 无进程处于临界区时，可允许一个申请进入临界区的进程立即进入自己的临界区。②忙则等待。 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。③有限等待。 入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。④让权等待。 等待进入临界区的进程，应放弃占用CPU，避免进程出现“忙等”现象。

3.互斥的实现方法1）软件的方法方法一：设置公用整型变量turn，保存进入临界区的进程标识。Dekker’sAlgorithm[Dijkstra65]例如：有两个进程P0和P1，互斥共享某个资源。P0、P1是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。若turn=0，允许进程P0进入临界区，否则等待。退出临界区时，修改turn为1。P1的算法类似。互斥的实现:软件方法一P0() {…… while(turn!=0)；

CS0；//P0的临界区

turn=1；

……

} turn=0;P1() {…… while(turn!=1)；

CS1;//P1的临界区

turn=0；

……

} 缺点：满足不了“空闲让进”原则3.互斥的实现方法1）软件的方法：方法二：（1981G.L.Peterson提出） 设置全局变量turn，指示允许进入临界区的进程标识。 定义数组flag[]表示进程是否希望进入临界区或是否在临界区执行。若flag[0]=true，表示进程P0希望进入临界区或已经进入临界区。若turn=0，表示进程P0允许进入临界区。互斥的实现:软件方法二P0() {…… flag[0]=true;turn=1;while(flag[1]&&turn==1)；

CS0；//P0的临界区

flag[0]=false；

……

} blooleanflag[2]={false,false};特点：满足“空闲让进”、“忙则等待”原则；P1() {…… flag[1]=true;turn=0;while(flag[0]&&turn==0)；

CS1；//P1的临界区

flag[1]=false；

……

} 互斥的实现方法2）硬件的方法：

（1）中断屏蔽方法当一个进程进入临界区时，通过屏蔽中断来防止其它进程进入临界区。禁用中断->时钟中断或其它均无效->CPU无法切换到其它进程优点：简单、有效，对操作系统自身很有用。缺点：不适合作为通用的互斥机制关中断时间过长会影响性能和系统效率，降低系统对外部中断的响应速度，影响系统处理紧急事件的能力。不适用于多处理器计算机系统。一个处理器关中断，不能阻止进程在其他处理器上执行相同的临界区。损害其他“无辜的”进程，阻止了多个进程并发地进入不同的临界区。互斥的实现方法2）硬件的方法：（2）硬件指令方法使用硬件指令实现进程互斥测试与设置指令TS(TestandSet);交互指令Swap(或Exchange)特点：指令对内存单元内容的操作（包括读和写）是不可分割的（原子性的），即该指令执行结束之前，其他处理器均不允许访问该内存单元。（2）硬件指令方法TS(TestandSetLock)指令把该指令看做函数，它有布尔型参数和返回条件码。TS(&x)返回x的值，并将x值设置为TRUE。其本身不做测试，调用该函数的程序做测试工作，如while(…)。TS指令的处理过程如下(C语言版本)：booleanTS(boolean*x){booleanrv=*x;*x=TRUE;returnrv;}（2）硬件指令方法TS(TestandSet)指令用TS指令管理临界区时，可以把一个临界区与一个布尔型变量s相关联。变量s代表临界资源的状态，把它看成一把锁。s的初值为FALSE，表示没有进程在临界区内，资源可用。系统利用TS指令实现临界区上的上锁和开锁原语操作。P0{…While(TS(&s));CS0;//临界区s=FALSE;…P1{…While(TS(&s));CS1;//临界区s=FALSE;…booleanTS(boolean*x){booleanrv=*x;*x=TRUE;returnrv;}bools=FALSE;（2）硬件指令方法Swap指令 对换指令可以交换两个字节的内容，其处理过程为：voidSwap(boolean*a,boolean*b){ booleantemp=*a; *a=*b; *b=temp;}(在Intelx86中)使用对换指令可以简单有效地实现互斥,方法是:

为每个临界区设置布尔型锁变量lock，当其值为FALSE时表示无进程在临界区内。boollock=FALSE; //初始化Pi{ … booleankey=TRUE; while(key) Swap(&key,&lock); //上锁

CSi;//临界区

Swap(&key,&lock); //开锁

…互斥的实现方法

（2）硬件指令方法优点：(1)适用范围广。硬件方法适用于任何数目的进程，在单处理机和多处理机环境中完全相同。(2)简单。硬件方法的标志设置简单，含义明确，容易验证其正确性。(3)支持多个临界区。在一个进程内有多个临界区时，只需为每个临界区设立一个布尔变量。缺点：进程在等待进入临界区时要耗费处理机时间，不能实现让权等待；由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致饥饿现象。6.4.2进程的同步系统中的各进程可以并发共享资源，从而使系统资源得到充分利用，但是共享资源往往使并发进程产生某种时序上的约束关系。例如:有A、B两个进程，A进程负责从键盘读数据到缓冲区，B进程负责从缓冲区读数据进行计算。要完成取数据并计算的工作，A进程和B进程要协同工作：即B进程只有等待A进程把数据送到缓冲区后才能进行计算。A进程只有等待B进程发出已把缓冲区数据取走的信号之后才能从键盘向缓冲区中送数据，否则就会出现错误。进程同步示意图6.4.2进程的同步进程同步：进程同步是指进程之间一种直接的协同工作关系，这些进程相互合作，共同完成一项任务。进程间的直接相互作用构成进程的同步。进程互斥的实质也是同步，进程互斥可以看成是一种特殊的进程同步。6.4.3信号量（Semaphore）及PV操作1.信号量及PV操作原语实现进程之间互斥关系的方法软件算法太复杂，效率低下；硬件方法虽然简单，但采用了“忙等待”，浪费CPU资源；将测试能否进入临界区的责任推卸给各个竞争的进程，会削弱系统的可靠性，加重用户的编程负担。这些方案只能解决进程互斥却不能解决进程同步问题。信号量和P、V操作1965年，荷兰计算机科学家EdsgerWDijkstra（迪杰斯特拉）提出的同步工具；将交通管制中的信号灯管理方法引入操作系统，让两个或多个进程通过特殊变量展开交互；一个进程在某一关键点上被迫停止执行直至接收到对应的特殊变量值（信号量）；进程通过P、V两个特殊操作来发送和接收信号。6.4.3信号量（Semaphore）及PV操作1.信号量及PV操作原语信号量是一种特殊的变量，表示资源的物理实体（即表示系统中某类资源的数目）。它的表面形式是一个整型变量附加一个队列；仅能被施加3种操作：初始化和2个特殊的原语操作

(1)初始化操作,信号量能初始化为非负的值。

(2)P操作（荷兰语Proberen,尝试减小try）

(3)V操作（荷兰语Vehogen，增加raise/makehigher）数值指针S6.4.3信号量（Semaphore）及PV操作

信号量(S)的数据结构:

为一个值和一个指针，指针指向等待该信号量的下一个进程。数值指针SStructsemaphore{intvalue;point_to_PCBqueue;}信号量及PV操作

设信号量为S，S可以取不同的整数值。信号量的值与相应资源的使用情况有关。当S>=0时，表示当前可用资源的数量；当S<0时，其绝对值表示等待使用该资源的进程个数。

注意:信号量的值仅能由PV操作来改变。

数值（－3）·指针·PCB1·0·信号量·PCB2·PCB3·信号量及PV操作

PV操作既能实现进程互斥，又能实现进程同步。它由P操作原语和V操作原语组成，对信号量进行操作，定义如下：V（S）操作①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则(S≤0)还要释放S信号量队列中第一个等待的进程（阻塞态改为就绪态）。P（S）操作①将信号量S的值减1，即S=S-1；②如果S

0，则该进程继续执行；否则(S<0)该进程置为阻塞状态，排入S信号量的等待队列。VoidP(semaphore*s)//P操作{s->value--;if(s->value<0){/*placethisprocessins->queue*/;/*blockthisprocess*/;asleep(s->queue)}}VoidV(semaphore*s)//V操作{s->value++;if(s->value<=0){/*removeaprocessPfroms->queue*/;/*placeprocessPonreadylist*/;

wakeup(s->queue)}}操作流程见教材信号量及PV操作

说明：信号量S

0时，S表示某类可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；减1后,若S<0，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；加1后,若S

0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态（阻塞状态）的进程，使之能运行下去。2.利用P、V原语实现进程互斥

设有A、B两个进程，竞争使用某一临界资源。利用信号量和PV原语操作可以方便地实现进程间的互斥执行。设mutex为公共互斥信号量。初值为1，取值范围为（1，0，-1）。mutex＝1表示进程A、B都没有进入临界区。mutex＝0表示进程A、B中的一个已经进入临界区。mutex＝-1表示进程中，一个进程已经进入临界区，另一个进程被阻塞，等待前一进入临界区的进程退出并释放资源后唤醒它。

令mutex初值为1，进程A、B竞争进入临界区的程序可以写成： 进程A 进程B … …

P(mutex)； P(mutex)；

A临界区 B临界区

V(mutex)； V(mutex)；2.利用P、V原语实现进程互斥注意：PV操作必须成对出现，先做P进临界区；后做V，出临界区。互斥信号量初值一般为1。3.利用P、V原语实现进程同步设两个信号量S1和S2S1表示缓冲区是否为空（信息是否取走，空闲单元的个数）S1=0,缓冲区不空；S1=1，缓冲区空。S2表示缓冲区是否为满（是否装满信息，非空单元/数据的个数）S2=0，缓冲区不满；S2=1，缓冲区满。赋予初值S1为1，S2为0，程序可写成：进程A P(S1)；把信息送入缓冲区；V(S2)；进程BP(S2)；把信息从缓冲区取走；V(S1)；注意事项：分析进程间的制约关系，确定信号量种类。通过信号量协调进程的执行先后顺序。(当进程需要等待相关协同进程完成某个协作任务时，就可以对初值为0的信号量执行P操作，以使自己在此点阻塞。)信号量初值与资源数量有关，也与PV操作的出现位置有关。同一信号量的P、V操作“成对”出现，但分别在不同的进程代码中。互斥和同步对信号量PV操作方法的差异都是通过对信号量的P、V操作来实现，但策略不同互斥：不同进程对同一信号量进行P、V操作一个进程在成功地对信号量执行了P操作后进入临界区；在退出临界区后，由该进程对信号量执行V操作。同步：进程PA要同步等待PB。由进程PA对信号量进行P操作后，只能由进程PB对同一个信号量进行V操作，从而使PA能够继续执行。若进程PB也要同步等待PA，则要设置另一个信号量。4.生产者—消费者问题“生产者和消费者”问题是一个典型的进程同步的例子计算机系统中的许多问题都可以被归结“生产者和消费者”问题：针对某类资源，一个进程如果产生并释放它，则该进程称作生产者；一个进程如果使用这类资源，则该进程称作消费者；例如:生产者可以是计算进程，消费者是打印进程生产者和消费者可以通过一个缓冲区联系起来。（课本P131）生产者存放产品的单元数不能超过缓冲区的容量N;消费者取出产品的总量不能超过生产者生产产品的总量。4.生产者—消费者问题可设信号量buffers:空闲的缓冲区数目。初值为N。products:已存入缓冲区的产品数目。初值为0。mutex:互斥信号量。初值为1。生产者和消费者问题的一般过程为：生产者在执行P(buffers)之后，只要buffers≥0(还有空闲的缓冲区)，就可将产品送入。消费者在执行P(produ