Windows操作系统-处理机管理(中)

进程和进程控制线程进程互斥和同步死锁问题进程间通信处理器调度

第三章处理机管理(中)进程互斥和同步问题的提出互斥算法信号量(semaphore)经典进程同步问题管程(monitor)Windows的进程互斥和同步进程互斥和同步进程间临界资源访问冲突共享变量的修改冲突操作顺序冲突临界资源：计算机系统中的硬件或软件〔如外设、共享代码段、共享数据结构〕资源，各个进程在对其进行访问时〔关键是进行写入或修改〕，必须互斥地进行并非所有共享资源都是临界资源，如只读数据可以同时访问在多道程序环境中，进程之间存在相互制约的关系，这种制约关系主要是由对共享资源的竞争使用而引起的。进程互斥和同步问题的提出共享变量的修改冲突进程互斥和同步临界资源问题的提出一个飞机订票系统，两个终端，运行T1、T2进程T1:T2:......Read(x);Read(x);ifx>=1thenifx>=1thenx:=x-1;x:=x-1;write(x);write(x);......3个进程：get,process和print进程互斥和同步操作顺序冲突临界资源getprocessprint问题的提出Buf1Buf2磁带打印机临界资源的访问过程进程互斥和同步为了保证临界资源的正确访问，必须采取一定的协调措施临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。退出区(exitsection)：用于将"正在访问临界区"标志去除。剩余区(remaindersection)：代码中的其余局部。问题的提出同步机制应遵循的准那么①空闲那么入：当没有进程处于临界区时，假设有一个进程要求进入临界区，那么应该允许；②无空等待：已有进程处于其临界区，其他要求进入临界区的进程必须；③有限等待：等待进入临界区的进程应该在有限的时间内得到满足；④让权等待：不能进入临界区的进程，应释放CPU〔如转换到阻塞状态〕进程互斥和同步目的：防止死锁和饥饿死锁指多个进程互不相让，都得不到足够的资源；饥饿指某一个进程一直得不到资源问题的提出进程互斥和同步互斥算法

——基于进程间平等协商的互斥算法解决进程互斥的方法：基于进程间平等协商的互斥方法软件方法硬件方法由操作系统协调互斥问题的方法进程互斥的软件方法有两个进程Pi,Pj，其中的Pi算法1：单标志设立一个公用整型变量turn：描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；进程互斥和同步互斥算法算法2：双标志、先检查设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE。先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。进程互斥和同步进程互斥的软件方法互斥算法算法3：双标志、后检查类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。缺点：Pi和Pj可能都进入不了临界区。进程互斥和同步进程互斥的软件方法互斥算法算法4：先修改、后检查、后修改者等待结合算法1和算法3，满足空闲那么入和无空等待要求turn=j;描述可进入的进程〔同时修改标志时〕在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区那么自己进入－－空闲那么入否那么再检查turn：保存的是较晚的一次赋值，那么较晚的进程等待，较早的进程进入－－先到先入，后到等待进程互斥和同步进程互斥的软件方法互斥算法信号量(semaphore)信号量和P、V原语信号量集前面的互斥算法是进程间的一种平等协商机制，不能满足进程同步机制准那么的全部要求。另一种进程互斥的解决方法是引如一个地位高于进程的管理者来解决临界资源的使用问题。操作系统可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理临界资源的有效手段。信号量代表可用资源实体的数量。进程互斥和同步信号量和P、V原语1965年，由荷兰学者Dijkstra提出〔P、V分别是荷兰语的proberen=test和verhogen=increment的首字母〕，是一种卓有成效的进程同步机制。每个信号量s包含一个整数值s.count〔计数〕和一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问——作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数〔又称为“资源信号量”〕——假设为非负值表示当前的空闲资源数，假设为负值其绝对值表示当前等待临界区的进程数进程互斥和同步信号量P原语P(s){ --s.count; //表示申请一个资源; if(s.count<0) //表示没有空闲资源; {

调用进程进入等待队列s.queue;

阻塞调用进程; }}进程互斥和同步信号量V原语V(s){ ++s.count; //表示释放一个资源；

if(s.count<=0) //表示有进程处于阻塞状态；

{

从等待队列s.queue中取出一个进程P;

进程P进入就绪队列; }}进程互斥和同步信号量利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语那么不能保证互斥访问，遗漏V原语那么不能在使用临界资源之后将其释放〔给其他等待的进程〕；P、V原语不能次序错误、重复或遗漏进程互斥和同步信号量利用信号量可以实现进程间的同步前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为0进程互斥和同步信号量经典进程同步问题1.生产者－消费者问题(theproducer-consumerproblem)问题描述：假设干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有n个；任何时刻只能有一个进程可对共享缓冲区进行操作。进程互斥和同步采用信号量机制：full是“满”数目，初值为0，empty是“空”数目，初值为n。full和empty存在关系：full+empty==nmutex用于访问缓冲区时的互斥，初值是1每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否那么可能死锁(为什么？)进程互斥和同步经典进程同步问题1.生产者－消费者问题(theproducer-consumerproblem)2.读者－写者问题(thereaders-writersproblem)问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”那么允许多个“读－写”互斥，“写－写”互斥，"读－读"允许进程互斥和同步经典进程同步问题采用信号量机制：Wmutex表示"允许写"，初值是1。公共变量Rcount表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。进程互斥和同步2.读者－写者问题经典进程同步问题P(Rmutex);if(Rcount==0)P(Wmutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)V(Wmutex);V(Rmutex);ReaderP(Wmutex);write;V(Wmutex);Writer信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁〔如P、V操作的次序错误、重复或遗漏〕易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统中并发执行的各个程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；进程互斥和同步管程用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程的引入1973年，由Hoare和Hanson提出管程的根本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。引入管程可提高代码的可读性，便于修改和维护，正确性易于保证。进程互斥和同步管程管程的主要特性模块化：一个管程是一个根本程序单位，可以单独编译；抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，进程可调用管程中实现了某些功能〔函数〕，至于这些功能是怎样实现的，在其外部那么是不可见的；进程互斥和同步管程管程作为一个模块，它的结构定义如下：

monitor_name=MONITOR;

共享变量说明;

define本管程内部定义、外部可调用的函数名表;

use本管程外部定义、内部可调用的函数名表;

内部定义的函数说明和函数体

{

共享变量初始化语句;

}

进程互斥和同步管程进程互斥和同步管程bulletin=MONITOR;

r,w:condition;//r控制读者使用黑板,w控制写者；

writing:boolean;//当前是否写者使用黑板

read_account:integer;

definestart_read,end_read,start_write,end_write;

usemonitor.wait,monitor.signal;

procedurestart_read();

{

if(writing)monitor.wait(r);

read_account++;

monitor.signal(r);

}

procedureend_read();

{

read_account--;

if(read_account=0)monitor.signal(w);

}

假设已实现一根本管程monitor，提供signal,wait等操作

procedurestart_write();

{

if((read_account<>0)orwriting)monitor.wait(w);

writing=true;

}

procedureend_write();

{

writing=false;

if(r<>NULL)monitor.signal(r);

elsemonitor.signal(w);

}

进程互斥和同步管程reader()：

{

while(true)

{

bulletin.start_read();

read();

bulletin.end_read();

}

}

writer()

{

while(true)

{

bulletin.start_write();

write();

bulletin.end_write();

}

}

读者进程写者进程Mutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关的API：CreateMutex创立或翻开一个互斥对象，返回对象句柄；OpenMutex返回一个已存在的互斥对象的句柄，用于后续访问；ReleaseMutex释放对互斥对象的占用，使之成为可用；Windows支持三种同步对象对象名称是由用户给出的字符串。不同进程中用同样的名称来创立或翻开对象，从而获得该对象在本进程的句柄。Windows的进程互斥和同步——互斥对象、信号量对象和事件对象进程互斥和同步HANDLECreateMutex(LPSECURITY_ATTRIBUTESlpMutexAttributes,//SDBOOLbInitialOwner,//initialownerLPCTSTRlpName//objectname);Semaphore对象：相当于资源信号量，取值在0到指定最大值之间，用于限制并发访问的线程数。有关的API：CreateSemaphore创立一个信号量对象，指定最大值和初值，返回对象句柄；OpenSemaphore返回一个已存在的信号量对象的句柄，用于后续访问；ReleaseSemaphore释放对信号量对象的占用；进程互斥和同步Windows支持的三种同步对象Windows的进程互斥和同步HANDLECreateSemaphore( LPSECURITY_ATTRIBUTESlpSemaphoreAttributes,//SD LONGlInitialCount,//initialcount LONGlMaximumCount,//maximumcount LPCTSTRlpName//objectname);Event对象：事件对象，相当于"触发器"，可通知一个或多个线程某事件的出现。有关的API：CreateEvent创立一个事件对象，返回对象句柄；OpenEvent返回一个已存在的事件对象的句柄，用于后续访问；SetEvent和PulseEvent设置指定事件对象为有信号状态；ResetEvent设置指定事件对象为无信号状态〔nonsignaled〕进程互斥和同步Windows支持的三种同步对象Windows的进程互斥和同步同步对象等待(1)WaitForSingleObject在指定的时间内等待指定对象为有信号状态(signaledstate)；

DWORDWaitForSingleObject( HANDLEhHandle,//handleofobjecttowaitfor DWORDdwMilliseconds//time-outintervalinmilliseconds);进程互斥和同步Windows的进程互斥和同步(2)WaitForMultipleObjects在指定的时间内等待多个对象为有信号状态；

DWORDWaitForMultipleObjects( DWORDnCount,//对象句柄数组中的句柄数；

CONSTHANDLE*lpHandles,//指向对象句柄数组的指针，数组中 //可包括多种对象句柄；

BOOLbWaitAll, //等待标志：TRUE表示所有对象同时可用 //FALSE表示至少一个对象可用；

DWORDdwMilliseconds//等待超时时限；

);同步对象等待Windows的进程互斥和同步其他同步方法CriticalSection对象：只能在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的。把变量说明为CRITICAL_SECTION类型，就可作为临界区使用。有关的API：InitializeCriticalSection对临界区对象进行初始化；EnterCriticalSection等待占用临界区的使用权，得到使用权时返回；TryEnterCriticalSection非等待方式申请临界区的使用权；申请失败时，返回0；LeaveCriticalSection释放临界区的使用权；DeleteCriticalSection释放与临界区对象相关的所有系统资源；进程互斥和同步Windows的进程互斥和同步互锁变量访问相当于硬件指令，对一个整数〔进程内的变量或进程间的共享变量〕进行操作。其目的是防止线程间切换的影响。有关的API：InterlockedExchange进行32位数据的先读后写原子操作；InterlockedCompareExchange依据比较结果进行赋值的原子操作；InterlockedExchangeAdd先加后存结果的原子操作；InterlockedDecrement先减1后存结果的原子操作；InterlockedIncrement先加1后存结果的原子操作；进程互斥和同步Windows的进程互斥和同步死锁问题(DEADLOCK)概述死锁的预防死锁的检测死锁的防止解决死锁问题的综合方法概述可重用资源(reusableresource)：每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如CPU、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。死锁是指系统中多个进程无限制地等待永远不会发生的条件；死锁发生原因对互斥资源的共享；并发执行的顺序不当死锁问题进程使用的资源分为可重用资源和可消耗资源两类：可重用资源死锁死锁发生：双方都拥有局部资源，同时在请求对方已占有的资源。如次序：P1<a>P2<a>P1<b>P2<b>概述死锁问题可消耗资源(consumableresource)：可以动态生成和消耗，一般不限制数量。如硬件中断、信号、消息、缓冲区内的数据。死锁发生：双方都等待对方去生成资源，如次序：P1<a>P2<a>概述死锁问题死锁发生条件：互斥：任一时刻只允许一个进程使用资源请求和保持：进程在请求其余资源时，不主动释放已经占用的资源非剥夺：进程已经占用的资源，不会被强制剥夺环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。只有4个条件都满足时，才会出现死锁。死锁问题概述处理死锁问题的根本方法：预防、检测、防止死锁的预防预防死锁的两种策略：预先静态分配法：进程开始运行前一次分配所需全部资源，假设系统不能满足，那么进程阻塞，直到系统满足其要求——保证进程运行过程中不会再提出新的资源请求；降低了对资源的利用率，降低进程的并发程度；有可能无法预先知道所需资源；有序资源使用法：把资源分类按顺序排列，保证对资源的请求不形成环路；限制进程对资源的请求顺序；资源的排序占用系统开销；预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。死锁问题死锁的检测保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待。死锁问题资源分配图算法将进程和资源间的请求和分配关系用一个有向图描述，通过检查有向图中是否存在循环判断是否存在死锁死锁的防止在分配资源时判断是否会出现死锁，如