第2章进程的描述与控制(下).

操作系统第二章进程管理1§2.4进程互斥一、互斥的概念1．资源共享引起的制约——间接制约在多道程序系统中，各进程并发执行，并以各自独立的速度向前推进。当并发进程竞争使用同一资源（如处理机、主存空间、I/O设备以及文件等一类资源）时，它们之间会发生冲突，竞争资源的进程之间没有任何信息交换，但是，一个进程的执行可能会影响到竞争进程的行为。例如，两个进程都期望访问同一个资源，操作系统把这个资源分配给其中一个进程，另一个就必须等待。这种由竞争共享资源带来的进程之间的相互制约关系称为间接制约关系。操作系统第二章进程管理22．临界资源与临界区如若两个或更多的进程需要访问打印机，在并发执行的过程当中，若让它们任意使用，则可能发生的情况是多个进程交替使用打印机，输出结果交织在一起，很难区分。解决的方法是任何一个进程在使用打印机打印整个文件时，都独占打印机的控制权，直到打印完成释放打印机为止。临界资源：一次仅允许一个进程使用的资源。许多物理设备都属于临界资源，例如：输入机、打印机、绘图机等；此外还有许多软件资源，例如：共享的变量、数据、表格、队列等也属于临界资源。它们虽然可被若干进程所共享，但一次只能为一个进程所利用。操作系统第二章进程管理3设某时刻游艺场的在场人数count为n，这时有一个人进场，同时有一个人退场。由于进场和退场是随机的，因此进程PIN和POUT的执行是并发的。例如:某游艺场设置了一个自动计数系统，用一个计数器count指示在场的人数。当有一个人进场时，由进程PIN实现计数加1；当有一个人退场时，由进程POUT实现计数减1。count→R1R1+1→R1R1→countcount→R2R2－1→R2R2→count进程PIN进程POUT如果这两个进程按下述不同顺序执行时，执行的结果分别如下：操作系统第二章进程管理41）进程PIN和POUT各自顺序执行：假若进程PIN先执行，结束之后进程POUT再执行，两个进程分别完成了对count的计数加1和计数减1的工作，count的计数值保持为n，显然，这个结果是正确的。2）进程PIN和POUT交替执行各个操作：假若：PINR1：=count；POUTR2：=count；PINR1：=R1+1；count：=R1；POUTR2：=R2－1；count：=R2；执行完毕时，count的计数值为n-1。假若：PINR1：=count；POUTR2：=count；R2：=R2－1；count：=R2；PINR1：=R1+1；count：=R1；执行完毕时，count的计数值为n+1。上述两种结果和实际的情况不一致，即发生与时间有关的错误。操作系统第二章进程管理5问题的关键在于共享变量count，两个进程访问这个共享变量，如果一个进程修改了count，完成了对count的一部分操作，然后被中断，另一个进程在第一个进程使用完count的值之前又修改了count，从而造成了count计数值的错误；如果一次只允许一个进程对共享变量count进行访问，就能解决这个问题，共享变量count属于临界资源。要防止临界资源使用过程中发生“与时间有关的错误”，惟一的办法是控制访问临界资源的各进程的执行,实现对临界资源的互斥访问。临界区：每个进程中访问临界资源的那一部分程序。注意：临界区是对某一资源而言的，对于不同资源的临界区，它们之间是无关的，所以不必互斥地执行。操作系统第二章进程管理63.互斥在操作系统中，当一个进程进入临界区访问临界资源时，另一个欲进入相关临界区的进程必须等待，直到占用临界资源的进程退出临界区后，另一个进程才可以进入临界区，进程之间这种相互制约的关系称为互斥。即进程的互斥就是两个或两个以上的进程不能同时进入共享同一临界资源的(相关)临界区。操作系统第二章进程管理71）若有多个进程同时要求进入它们的临界区时，应在有限的时间内让其中之一进入临界区，而不应相互阻塞，以致于各进程都不能进入临界区；2）每次至多只允许一个进程处于临界区；3）进程在临界区内仅停留有限的时间。实现进程互斥，也就是实现对于临界区的管理。为了保证共享临界资源的各进程在临界区互斥地执行，提出了对临界区管理的原则：4.对临界区管理的原则操作系统第二章进程管理8根据上述对临界区的管理原则，可以得出临界区的调度原则：1）空闲让进:当无进程处于临界区内时，允许一个进程进入临界区；2）忙则等待:当某一个进程已进入临界区时，其它欲进入临界区的进程必须等待；3）有限等待:当某一个进程离开临界区时，若有进程等待进入临界区，则允许其中一个进程进入临界区;4）让权等待:当进程不能进入自己的临界区时，应立即释放处理机。操作系统第二章进程管理9实现进程互斥的同步机构：锁机制、信号量和PV操作机制、管程机制。二、锁机制1.锁：使用一个标志或一个变量来代表临界资源的状态。W=1为锁被关闭，表示该资源已占用；W=0为锁已打开，表示该资源空闲，未被占用。系统提供一对在锁位W上进行操作的上锁原语Lock（W）和开锁原语UnLock（W）。进程互斥的实现可以采用软件的方法，也可以通过系统提供的同步机构来协调进程间的关系。操作系统第二章进程管理102.上锁原语Lock（W）：测试W的值，若W=1，表示资源正在使用，继续反复测试；若W=0，则设置W=1（上锁）。上锁原语算法:lock(w）begintest:if(w=1）gototestelsew：=1；endW=1？1→W入口返回是否操作系统第二章进程管理113.开锁原语UnLock（W）：设置W=0（开锁）。0→W入口返回开锁原语算法:Unlock(w）beginw：=0;end在测试锁位W的值和设置锁位W的值为1的这两步之间，锁位W的值不得被其它进程所改变，这是应该绝对保证的，因此采用了在锁位W上的原语操作。有些系统中，机器在硬件中提供了专门的硬件指令TestandSet（简称TS）来完成上述的上锁和开锁操作。例如，在IBM/370中就有一条称为“测试并置位”的TS指令。操作系统第二章进程管理124.用上锁原语和开锁原语实现进程互斥利用上锁原语和开锁原语可以解决并发进程对临界区访问的互斥问题。任何申请进入临界区的进程，必须先执行上锁原语。若上锁原语顺利通过，则进程可以进入临界区，这时临界区已被上锁原语锁住，其它申请进入临界区的进程只能等到临界区开锁之后才有可能进入临界区；当进程完成对临界资源的访问退出临界区时再执行开锁原语，以释放该临界资源。操作系统第二章进程管理13上锁原语临界区CSA开锁原语上锁原语临界区CSB开锁原语进程A进程B操作系统第二章进程管理14进程使用临界资源的操作流程R1+1→R1R1→countcount→R2R2+2→R2R1→count上锁原语Lock(W)开锁原语UnLock(W)count→R1上锁原语Lock(W)开锁原语UnLock(W)进程PIN进程POUT临界区临界区操作系统第二章进程管理15三、信号量和PV操作1.信号量的概念在操作系统中，信号量是表示资源的实体，是一个特殊的变量，其值仅能由PV操作来改变。操作系统利用信号量的状态对进程和资源进行管理。信号量是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的进程PCB队列的首指针。因此，一个信号量w包括两个部分：即整数值部分w.s和指针部分w.q。w.sw.q信号量w∧操作系统第二章进程管理16信号量的物理含义：从资源观点来看，s的值表示系统中某类可用资源的数目。其大于等于零时，表示系统中当前可用资源的数目；其小于零时，其绝对值表示系统中还欠缺的资源数目，(即正在等待使用临界资源的进程数)。w.sw.q∧…PCB队列建立一个信号量必须说明该信号量所代表的意义，并赋初值，而信号量的值仅能由PV操作原语来改变。操作系统第二章进程管理172.P、V操作PV操作是P操作原语P（s）和V操作原语V（s）的简称，是定义在信号量上的两个操作原语，在执行期间不可分割。P操作原语P（s）的过程：(P（s）--wait(s))1）s的值减1；2）若相减的结果大于或等于零，则调用P（s）的进程继续执行；3）若相减的结果小于零，则调用P（s）的进程被阻塞，并插入到该信号量的等待队列中，然后转进程调度程序。操作系统第二章进程管理18P(S)操作-wait(s)算法pbegins：=s–1；ifs0block()ends-1→ss≥0?调用block()转进程调度入口返回是否操作系统第二章进程管理19V操作原语V（s）的过程：(V（s）--signal(s))（1）s的值加1；（2）若相加的结果大于零，则进程继续执行；（3）若相加的结果小于或等于零，则从该信号量的等待队列中唤醒一等待进程，然后返回原进程继续执行或转进程调度程序。操作系统第二章进程管理20V(S)操作-signal(s)算法Vbegins=s+1；ifs＝0wakeup()end调用wakeup（）返回或转进程调度s+1→s入口返回s≤0?是否操作系统第二章进程管理21从PV操作原语的定义中可以看出，当进程调用P操作，判断s的值小于零时，调用P（s）的进程被阻塞后，该进程并没有象锁机制中那样陷入“忙等待”，而是“让权等待”，放弃占用处理机而进入等待队列，然后转进程调度程序重新选择一个进程占用处理机。从而避免了处理机的空耗，提高了处理机的效率。操作系统第二章进程管理223.用信号量实现进程互斥利用信号量能方便地解决临界区问题。设有n个进程，用数组P(i)表示，设与n个进程共享的临界资源对应的互斥信号量为s，信号量初始化为1，表示初始状态时共享资源是空闲的。只需把各个进程临界区的程序段置于P（s）和V（s）之间即可实现n个进程的互斥。进程P（1）…进程P（i）…进程P（n）P（s）V（s）临界区1P（s）P（s）临界区i临界区nV（s）V（s）……操作系统第二章进程管理232）进程每执行一次V操作，信号量的数值加1，意味着进程释放一个单位的资源。当s＞0，说明系统中没有进程在等待此类资源，则释放资源的进程继续执行；当s≤0，说明此信号量的等待队列中有等待进程，那么应唤醒等待队列中的一个进程，将释放的资源分配给它，使其能获取所需资源，然后释放资源的进程可继续执行下去。当s＜0，表示系统已无资源可用，所有的此类资源均已被占用，则应将该进程阻塞，并插入等待队列。此时，s的绝对值表示信号量s的等待队列中的进程数。注意：信号量和PV操作的物理含义1）进程每执行一次P操作，信号量的数值减1，意味着进程申请分配一个单位的资源。当s≥0，表示了某类可用资源的数量;操作系统第二章进程管理24分析信号量s的取值范围例如：设一民航售票系统有n个售票处。每个售票处通过终端访问系统中的公用数据区，假定公共数据区中的一些单元xk（k=1，2，……，m）分别存放×月×日×次航班的现存票数。设P1，P2，……，Pn表示各售票处的处理程序，R1，R2，……，Rn表示各进程执行时所用的工作单元。操作系统第二章进程管理25用信号量实现各进程间的互斥begincobeginprocessPi（i=1，2，……，n）begin按旅客订票要求找到xk（k=1，2，……，m）；Ri：=xk；ifRi≥1thenbeginRi：=Ri-1；xk：=Ri；输出一张票；endelse输出“票已售完”；end；coend；end；sk：semaphore；sk=1；P（sk）；V（sk）；V（sk）；beginend；信号量Sk的取值范围是：1到-（n–1）之间的整数操作系统第二章进程管理26§2.5进程同步一、同步的概念异步环境中的各进程并发执行，并以各自独立的速度向前推进，并发执行的进程之间可能由于合作完成同一任务而相互支持和依赖，从而引发出进程间的直接制约关系。异步环境：主要指各并发进程的执行起始时间的随机性和执行速度的独立性。直接制约关系带来进程的同步。亦即，一组相互合作的并发进程，为了协调其推进速度，在一些关键点上可能需要相互等待或互通消息，进程之间这种相互制约的关系称作进程同步。具