1、 多道程序系统中进程是并发执行的，并发进程之间存在着相互制约关系，为了协调进程之间的相互制约关系，就需要实现进程的低级通信。系统之间之所以有这种关系是由于系统之间之所以有这种关系是由于以下两方面的原因造成的：以下两方面的原因造成的：(1)(1)各并发进程对资源的共享各并发进程对资源的共享 互斥关系互斥关系：通过共享资源而使进程之间产生的关系叫做间接制约关系间接制约关系，又叫做互斥关系。用“进程-资源-进程”描述。例例 进程P1和P2在运行中都要使用打印机，为了使各进程输出的完整性，打印机的使用必须独占。一旦系统将打印机分配给进程P1，那么进程P2必须等待。P1-打印机-P2(2)(2)系统中存
2、在若干协作进程系统中存在若干协作进程 同步关系同步关系：一个用户作业涉及一组并发进程（输入、计算和输出进程），这些进程须相互协作共同完成这项任务。进程之间的这种制约关系叫做直接直接制约关系制约关系。互斥是同步的一种特殊情况。低级通信低级通信：进程之间的这种相互依赖又相互制约、相互合作又相互竞争的关系，也即进程的同步与互斥关系,也叫进程之间的低级通信低级通信。共享资源引起进程之间的互斥共享资源引起进程之间的互斥几个基本概念：几个基本概念：l 共享资源共享资源：慢速的硬设备，如打印机等资源，软件资源，如共享变量、共享文件等。l 临界资源临界资源：一次仅允许一个进程使用的资源。具有这种特点的上述资源
3、。临界资源：上一章打印机的例子：临界资源：上一章打印机的例子：如何避免这种情况发生，关键是防止多个进如何避免这种情况发生，关键是防止多个进程同时读或写共享数据。换句话就是必须程同时读或写共享数据。换句话就是必须互斥的使用共享变量互斥的使用共享变量in。l 临界区临界区(critical section)：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段。2.6.1 进程之间的互斥进程之间的互斥 l为进一步说明临界资源的概念，下面举一个著名的进程同步问题的例子：l生产者_消费者问题。l在生产者与消费者问题中，描述的是生产者与消费者的关系。有一个生产者进程生产产品，并将所生产的产品提供给一
4、个消费者进程去消费。为了使生产者与消费者并发进行，在两者之间设置了一个具有n个缓冲区的缓冲池，尽管生产者与消费者都以异步的方式进行，但是它们之间必须保持一定的同步关系。即消费者进程不允许到空缓冲区去取产品，也不允许生产者进程向一个已装满产品，且尚未取走的缓冲区投放产品。我们利用一个数组表示上述具有n个缓冲区的缓冲池。使用输入指针in指示下一个可以放产品的缓冲区，每放一个产品指针加1。用一个输出指针out指示下一个可以取从中取产品的缓冲区，每当消费者进程从缓冲区取走一个产品输出指针加1由于缓冲区使用的是循环缓冲数组方式，所以输入加1表示为in=（in+1）mod n同样输出加1表示为out=（o
5、ut+1）mod n当（in+1）mod n=out，表示缓冲区满。初始状态in=out表示缓冲区空。此外还要设置一个表示缓冲区产品数量的变量counter初值为0，每投放一个产品counter加1，消费者每取走一个产品counter减1生产者与消费者共享下列变量：Var n,integer;Type item=“”;Var buffer:arry0,1,2,n-1of item;In,out:0,1,.n-1;Counter:0,1,n;In和out初始化为1。Noop表示控操作；While condition do no-op语句表示重复测试条件（condition）直到条件为假false
6、.生产者使用一个局部变量nextp,用于存放每次刚刚生产出来的产品，消费者使用一局部变量nextc存放每次将要消费的产品。则有程序：Producer:repeat produce an item in nextp;.while counter=n do no-op;bufferin:=nextp;In:=(in+1)mod n;Counter:=counter+1;Until fase;Consumer:repeat while counter=0 do no-op;nextc:=bufferout;out:=(out+1)mod n counter:=counter-1;consumer t
7、he item in nextc;until false这个程序显然是正确的，串行运行也是正确的，但是如果并行运行结果就不一定正确：其问题出现在两个进程共享了变量counter。其生产者加1操作和消费者的减1操作，在计算机上实现时可用下面语句描述：其生产者加1操作:Register1:=counter;Register1:=register1+1;Counter:=register1;消费者减1操作:Register2:=counter;Register2:=register2-1;Counter:=register2;假设现在counter当前值为5如果顺序执行先生产者后消费者执行一遍cou
8、nter内的值为5，但按如下顺序执行：Register1:=counter;register1=5Register1:=register1+1；register1=6Register2:=counter;register2=5Register2:=register2-1;register2=4Counter:=register1;counter=6Counter:=register2；counter=4正确值应该是5，可执行结果为4.又是结果还可能是6。表明程序并运行时已失去了再现性。这就是因为counter变量属于临界资源，而生产者与消费者没有互斥的访问它们，对counter的访问具有很大的
9、任意性，故产生了不确定性，解决问题的关键是将counter作为临界资源来处理，即要求生产者和消费者互斥访问。进程之间的互斥进程之间的互斥l临界区临界区(critical section)：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段。l在实现互斥时如果采取整体的程序采取互斥运行将会大大降低进程的并发性。事实上每个进程访问某个临界区的代码只是一小段，因此只需控制进程互斥的进入这一小段代码。我们将这一小段代码叫做临界区。l为此进程在进入临界区之前应对临界区进行检查，看是否被访问的标志，我们将这一段代码成为进入区(entry section),l同样退出临界区应将其标志为未被访问，这一段
10、代码称为退出区（exit section）l此外的代码可成为剩余区（remainder section）l于是可以将访问临界资源的循环进程描述为 repeat entry section critical section Exit section Remainder sectionUntil false任何时刻最多只有一个进程位于临界区。有空让进当已有进程处于其临界区时，后到达的进程只能在外等待。无空等待不应该使要进入临界区的进程无限期地等待在临界区之外。有限等待不能进入临界区的进程，应先释放处理机，转换到阻塞状态。让权等待 为了正确而有效地使用临界资源，系统中为了正确而有效地使用临界资源，系
11、统中的并发进程需要遵循如下四个准则：的并发进程需要遵循如下四个准则：有空让进；无空等待；有限等待；让权等待。2.2.解决进程之间互斥的方法解决进程之间互斥的方法 (1)(1)关中关中断断 解决进程互斥的最简单办法是当一个进程正在临界区执行时，关闭所有的中断。当进程退出临界段时，再开中断。之后其它要进入临界区的进程就可进入。描述如下：关中断关中断(disable)(disable)critical sectioncritical section 开中断开中断(enable)(enable)优点优点：简单。缺点缺点：限制了进程并发执行的能力。在多多处理机处理机情况下，这种方法不灵。l锁位变量锁位变
12、量W W ：为每个临界资源设置一个，以指示该资源当前的状态。系统初始化时，将W置为0。lTestsetTestset指令可定义如下：(2)(2)使用使用测试和设置指令测试和设置指令(test and set)(test and set)testset testset(int w)l:if(w=0)w=1;else goto l;/一条机器指令，其执行不可被中断。Const int n=/Const int n=/*进程数进程数 */int w;int w;void p(int i)void p(int i)while(TRUE)while(TRUE)testset(w);testset(w);
13、w=0;w=0;显然，采用这种加锁语句，由于进程循环测试，白白浪费了CPU的时间。这种现象又叫做“忙等待”。void main()void main()w=0;w=0;p(1);p(2);p(1);p(2);p(n);p(n);同步的原因同步的原因：一组进程要合作完成一项任务。例例 两个用户进程通过共享缓冲区完成其计算和打印任务。2.6.22.6.2 进程之间的同步进程之间的同步共享缓冲区计算进程打印进程计算进程在缓冲区满时等待，打印进程在缓冲区空时等待。两个进程这种由于速度不匹配引起速度不匹配引起的的关系，需要进行同步处理同步处理。为了解决进程之间的同步，引入信号量机制信号量机制。l1965
14、年，荷兰学者Dijkstra提出的一种同同步机制步机制。l基本原理基本原理：两个或多个进程可以通过简单的信号机制，进行同步。为此，需要引入一个称作的特殊变量信号量信号量。2.6.3 2.6.3 信号量和信号量和PVPV操作操作typedef struct semaphore int value;/表示该类资源的可用数量 struct process*pointer;/等待使用该类资源的进程排成队列的队列头指针。sem;v 对信号量s只允许执行P、V操作。v P、V操作由原语组成，执行过程中不可分割。信号量的类型描述：信号量的类型描述：Sem s；P P（S)S)操作原语：操作原语：void w
15、ait(sem s)s.value=s.value-1;/表示申请一个资源 if(s.value0)/申请资源不成功，阻塞等待。add this process to s.pointer;block();/“让让权等待权等待”V(S)V(S)操作原语：操作原语：void signal(sem s)s.value=s.value+1;/释放一个资源（或通过信号量s发消息）if(s.value=0)remove a process P from s.pointer;wakeup(P);/唤醒进程P。l显然，P、V操作的引入，克服了加锁操作的忙等待while(TRUE)while(TRUE)循环循环
16、 现象，有效提高了系统的效率。l操作系统正是利用信号量的状态对进程和资源进行管理和控制的。l对于互斥使用的资源，引入一个互斥信号量，用mutex表示。其初值为1。1.1.利用信号量实现进程之间的互斥利用信号量实现进程之间的互斥int mutex=1;int mutex=1;P1P1：P(mutex);P(mutex);critical section V(mutex);V(mutex);P2P2：P(mutex);P(mutex);critical section V(mutex);V(mutex);l用信号量可以方便地解决n个进程互斥地使用临界资源，实现临界区的互斥执行问题。信号量的取值范围
17、是+1+1-(n-1)-(n-1)。l信号量的值为负的含义：说明临界区中有一个进程正在执行，有若干个进程正在等待进入。等待的进程数为信号量值的绝对值。例例 若P、V操作的信号量初值为1，当前值为-3，则表示有 3个等待进程。例例 用信号量实现计算进程与打印进程之间的同步过程。假定计算进程和打印进程共享使用一个单一个单缓冲的缓冲区缓冲的缓冲区。要解决两者之间的同步，需要引入两个同步信号量s1和s2。lS1S1：表示缓冲区是否空闲，初值为1;lS2S2：表示缓冲区中是否有可供打印的计算结果，初始值为0。2.2.利用信号量实现进程之间的同步利用信号量实现进程之间的同步共享缓冲区计算进程 Pc打印进程
18、 Pp int s1=1 int s1=1，s2=0;s2=0;Pc Pc：compute next number;compute next number;P(s1);P(s1);add the number to buffer;add the number to buffer;V(s2);V(s2);Pp Pp：P(s2);P(s2);take next number from buffer;take next number from buffer;V(s1);V(s1);print the number;print the number;能否用一能否用一个同步信个同步信号量？号量？l计算机
19、中的并发进程，可以抽象成生产者和消费者问题进行解决。l生产者生产者：运行中的进程当其释放一个资源或发一个信号时，可把它看成该资源或信号的生产者，l消费者消费者：当运行中的进程申请一个资源或接收一个信号时，又可把它看成该资源或信号的消费者。电话号码：买一个手机，消费一个空资源。电话号码：买一个手机，消费一个空资源。例例 上述例子中l计算进程：计算进程：被被打印数据的生产者；空缓冲的消费者l打印进程：打印进程：被被打印数据的消费者；空缓冲的生产者3.3.利用信号量解决生产者和消费者问题利用信号量解决生产者和消费者问题 例例 l假定有一组生产者和消费者进程，通过一个有界缓冲区发生联系。l正常情况下，
20、生产者与消费者可并发地释放或取得缓冲区的产品。l限制条件：l缓冲区满：生产者要等待；l缓冲区空，消费者要等待。l设共享缓冲区容量为k。l存取缓冲区的限制：生产者/消费者互斥地使用缓冲区。生产者进程和消费者需要同步存取缓冲区信息。emptyempty：表示空缓冲块的个数，初值为k k；fullfull：有数据的缓冲块个数，初值为0 0。mutexmutex：互斥访问临界区的信号量，初值为1 1（因为多个生产者互斥，相当变量（因为多个生产者互斥，相当变量countercounter）。生产者1生产者2生产者M放产品指针 i消费者1消费者2消费者N取产品指针 jbuffer k（可以是一个循环栈）i
21、nt mutex=1,empty=k,full=0,i=0,j=0;DataType buffer k;Producer：produce a product x;P(empty);/申请空缓冲块 P(mutex);/实现对共享缓冲区的互斥访问 buffer i=x;/放入产品 i=(i+1)%k;V(mutex);V(full);/有数据的缓冲块个数加1 Consumer：P(full);/申请有数据的缓冲块 P(mutex);/实现对共享缓冲区的互斥访问 y=buffer j;/取产品 j=(j+1)%k;V(mutex);V(empty);/空缓冲块的个数加1 注意注意 每个进程中的P操作
22、的次序是很重要的。P操作放置不当，就可能死锁死锁。读读/写问题写问题：有一个多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；一些进程（reader)只读取这个数据区；一些进程（writer)只往数据区中写数据。读写必须满足以下条件：1.允许任意多的读进程可以同时读；2.一次只有一个写进程可写；4.4.读者读者（reader)和写者和写者（writer)问题问题l计数器readcount：记录同时读的读者数，初值为0。l读互斥信号量rmutex：使读者互斥地访问共享变量readcount，初值为1。l读写互斥信号量wrmutex：实现读写互斥和写写互斥地访问共享文件，初值为1。读
23、写同步的实现读写同步的实现int rmutex=1,wrmutex=1,readcount=0;Reader：P(rmutex);/互斥访问readcount if readcount=0 then P(wrmutex);readcount+;V(rmutex);读文件;P(rmutex);readcount=readcount-1;if readcount=0 then V(wrmutex);V(rmutex);Writer：P(wrmutex);写文件；V(wrmutex)；l这也是一个典型的同步问题，是一大类并发控制问题的例子。l假设有5个哲学家，花费一生的时光思考和吃饭。在桌子上放着5
24、只叉子。一个哲学家一次只能拿起一只叉子；仅当拿有两只叉子时才能吃饭；吃完，放下两只叉子。l每只叉子都用一个信号量表示。lsemaphore fork5l所有fork的元素被初始化为1。哲学家 i 的操作：do P(forki);P(fork(i+1)%5);eat V(forki);V(fork(i+1)%5);thinkwhile(1);可能导致死锁/饥饿最后一个人只能得到一把叉子不能吃饭将饿死l最多只允许四个哲学家同时坐在桌子上。l只有左右两只叉子都可用时才允许他拿起叉子（他必须在临界区内拿起两只叉子）。l使用非对称解决。奇数哲学家先拿起他左边的叉子，接着拿起他右边的叉子；偶数哲学家先拿起
25、他右边的叉子，接着拿起他左边的叉子。l信号量：编程负担重，易出错。l管程(Monitor)：一种新的进程间同步机制。l管程比信号量容易控制。l基本思想基本思想：是把信号量及其pv操作原语封装在一个对象内部，将共享变量及对共享变量能够进行的所有操作集中在一个模块中。l管程管程：是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。l管程管程提供互斥机制：一次只有一个进程能在管程内活动。从而，保证管程数据的一致性。l组成组成：局部于该管程的共享数据的说明，对共享数据执行的一组操作过程的说明，共享数据的初值设置语句。mutexshow:Monitor /管程名字 busy:boolea
26、n;/临界资源是否可用标志，是管程 变量的说明，nonbusy:semaphore;/进程等待队列头指针 define request,release;/管程中可供调用的过程说明 use wait,signal;/引用的外部模块的过程说明 begin busy:=false;/为管程局部变量赋初值，表示资源空闲 end;（1）用管程解决临界资源的互斥使用）用管程解决临界资源的互斥使用procedure request /申请临界资源的过程 begin if busy then wait(nonbusy);/忙则阻塞，并释放对管程的互斥使用权 busy:=true;/设置资源已被占用标志 end
27、;procedure release /释放临界资源过程 begin busy:=false;/设置资源已空闲标志 signal(nonbusy);/发信号，唤醒等待者 end;prod_conshow:Monitor rbuffer:array0.n-1of item;有n个元素的环形缓冲区 k:integer;缓冲区中的元素个数 nextempty,nextfull:integer;送、取元素的指针 nonempty,nonfull:semaphore;条件变量 define put,get;管程中定义的过程说明 use wait(),signal();引用外部模块的过程说明 begin
28、k=0;nextempty=nextfull=0;end;procedure put(product:item)向缓冲区送元素过程 begin if k=n then wait(nonempty);缓冲区满，生产者等待 rbuffernextempty=product;k=k+1;nextempty=(nextempty+1)mod n;signal(nonfull);唤醒等待取产品的消费者 end;procedure get(product:goods)从缓冲区取元素的过程 begin if k=0 then wait(nonfull);缓冲区空，消费者等待 goods=rbuffernex
29、tfull;k=k-1;producer:生产者进程 begin produce an item;prod_conshow.put(item);end;consumer:消费者进程 begin prod_conshow.get(item);consume the item;end;nextfull=(nextfull+1)mod n;signal(nonempty);唤醒等待送产品的生产者 end;低级通信的缺点低级通信的缺点：1.效率低。生产者每次只能向缓冲区投放一个消息；消费者每次只能从缓冲区取走一个消息。2.通信对用户不透明。得由用户（程序员）自己去实现通信。3.P、V操作使用不当时，易
30、导致死锁。高级通信高级通信：是指用户可直接利用OS所提供的一组通信命令，高效地传递大量数据的一种通信方式。高级通信机制高级通信机制：是指进程利用SO提供的，消息缓冲、信箱、管道、共享主存区等多种方式实现的通讯。非阻塞发送，阻塞接收发送进程发送完继续前进，而接受进程未收到消息则阻塞，等待接收。阻塞发送（类似）进程执行发送原语的规则进程执行发送原语的规则进程执行接收原语的规则进程执行接收原语的规则阻塞接收非阻塞接收接收者和发送者通信有如下组合方式：接收者和发送者通信有如下组合方式：l非阻塞发送，阻塞接收非阻塞发送，阻塞接收 例例 服务器上的多个服务进程平时处于阻塞状态，一旦有客户请求服务的消息到达
31、，系统便唤醒相应的服务进程，去完成用户所需要的服务。如：数据库监听程序，端口号l非阻塞发送，非阻塞接收非阻塞发送，非阻塞接收 信件通信方式。单向通信方式。我们接收和发送E_mail，是一个例子。l阻塞发送，阻塞接收阻塞发送，阻塞接收 大多数的双向通讯，采用这种方式。打电话，类似。收发进程的同步方式收发进程的同步方式1.消息缓冲通信机制消息缓冲通信机制消息缓冲的实现方法消息缓冲的实现方法l属于直接通信方式。l系统设置一个由若干缓冲区组成的消息缓冲池，每个缓冲区可以存放一个完整的消息。l欲发送消息进程，向系统申请一个消息缓冲区，将消息存入缓冲区，然后把该缓冲区连入接收进程的消息队列上。l消息队列头
32、指针通常放在接收进程控制块PCB中。（1）消息缓冲区的数据结构类型消息缓冲区的数据结构类型 struct message_buffer xx sender；/*发送进程标识符*/xx size；/*消息长度*/xx text；/*消息正文*/struct message_buffer*next；/*指向下一个 消息缓冲区的指针*/（2）PCB中有关通信的数据项描述中有关通信的数据项描述 struct PCB mq；/消息队列队头指针 mutex；/消息队列互斥信号量 sm；/消息队列同步信号量 l发送者先在自己的地址区形成一个消息发送区，把待发送的消息正文、发送进程标识符、接收进程标识符、消息
33、长度等信息填入其中，然后后调用发送原语：send(receiver,message)；l发送原语：申请一个 消息缓冲区，将消息从发送区传入其中，然后将该消息缓冲区挂到接收进程的消息队列中。l接收进程先在自己的地址区形成一个消息接收区，然后后调用接收原语：receive(sender,message)；l接收原语：将消息接收到自己的接收区。（3）发送原语、接收原语发送原语、接收原语send(B,a)text:Hellosize:5sender:Aamqmutexsmsender:Asize:5text:Hellonext:0i第一消息缓冲区Receive(b)sender:Asize:5text
34、:HellobPCB(B)A进程内存空间B进程内存空间消息缓冲通信图消息缓冲通信图 send(receiver,a)/发送原语 getbuf(a.size,i)；/据a区长度申请一缓冲区i i.sender=a.sender;i.size=a.size;i.text=a.text;i.next=0;getid(PCB set,receiver j);/获得接收进程的内部标识符j P(j.mutex);insert(j.mq,i);/将i挂在接收进程j的消息队列mq上 V(j.mutex);V(j.sm);/消息队列同步信号量sm receive(b)/接收原语 j=get internal n
35、ame;P(j.sm);/等消息 P(j.mutex);remove(j.mq,i);/从消息缓冲队列mq中摘下第一个消息缓冲区i。V(j.mutex);b.sender=i.sender;b.size=i.size;b.text=i.text;l发送进程将消息发送到某种中间实体（如信箱）中，接收进程从中取得消息。l是属于间接通信方式 发送原语：send(A,Msg)将一个消息Msg发送到信箱A。接收原语：receive(A,Msg)从信箱A中接收一个消息Msg。2.信箱通信机制信箱通信机制l当发送信件时，若指定的信箱未满，则将信件送入由指针指示的信箱位置。若有等待该信箱中信件的接收者，则将其
36、唤醒；否则（信箱满）发送者等待，直到信箱有空位置为止。l当接收信件时，若指定信箱中有信，则取走一封，并检查是否有发送者在等待，若有则将其唤醒；否则（无信）等待，直到信箱中有信件时为止。（1）管道l管道：是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为pipe文件。（将在UNIX部分介绍）l管道通信：发送进程和接收进程是利用管道进行通信的。发送进程以字符流的形式将大量的数据送入管道；接收进程从管道中接收数据。（2）共享主存机制 在主存中划出一块共享存储区，诸进程通过读或写共享主存区中的数据来实现通信。（速度快）在多道程序系统中，多个进程可能同时竞争一定数量的资源。如果进程
37、由于申请不到资源，相互处于无休止的等待死死 锁锁。例例一个计算机系统，它有4台磁带机和2个并发执行的进程。每个进程最多使用3台磁带机。某一时刻，每一进程都已占有2台磁带机，还要再请求一台磁带机才能完成它们的任务。这时，由于系统再无空闲的磁带机，两个进程就处于永远的相互等待状态，我们就说系统产生了死锁。l可抢占资源：如主存、CPU。当资源从占用进程剥夺走时，对进程不产生什么破坏性的影响。l不可抢占资源：如打印机、磁带机等。一旦分配，不能强行收回，只能由使用者自动释放。l死锁涉及的是不可抢占资源。1.资源的特性资源的特性v资源：硬件和软件之分v资源：可抢占和不可抢占源之分 进程使用资源的规则进程使
38、用资源的规则（1）请求资源：若请求不能立即满足，则等待。（2）使用资源：获得资源后，才能使用。（3）释放资源：使用完毕，将资源归还系统。一组进程是死锁的：是指这一组中的每个进程都正在等待该组中的其他进程占有资源时可能引起的一种错误现象。产生死锁的根本原因：系统中的资源数量不足，并发执行进程的推进速度不当。2.死锁的定义死锁的定义 1)1)互斥条件。（不可抢占的资源）互斥条件。（不可抢占的资源）2)2)保持和等待条件。（同时）保持和等待条件。（同时）3)3)不剥夺条件。（剥夺产生负面影响）不剥夺条件。（剥夺产生负面影响）4)循环等待条件。（相互）循环等待条件。（相互）3.3.死锁产生的必要条件死
39、锁产生的必要条件l用有向图研究解决死锁的方法:l图中圆圈代表进程，方块代表资源。l资源分给进程，用从资源(方块)到进程(圆圈)的有向弧表示；l进程请求资源，用从进程到资源的有向弧表示。2.8.2 解决死锁的方法解决死锁的方法系统资源分配图系统资源分配图TDUC图图2.10 2.10 资源分配图资源分配图(a)分配了一个资源(b)进程B 请求一个资源(c)进程D和进程C已处于死锁状态RSAB1.鸵鸟算法鸵鸟算法。忽略死锁。2.检测和恢复死锁检测和恢复死锁。允许死锁发生，通过设置检测机构，及时检测出死锁的发生，然后采取适当措施清除死锁。3.避免死锁避免死锁。是在资源的动态分配过程中，用某种方法去防
40、止系统进入不安全状态，从而避免发生死锁。4.预防死锁预防死锁。通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。解决死锁的方法解决死锁的方法1 1鸵鸟算法（置之不理）鸵鸟算法（置之不理）l是解决死锁的最简单方法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。l当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。例例 UNIX系统，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。在UNIX系统中系统允许创建进程总数是由进程表中PCB的个数决定的，因此
41、PCB块的资源是有限的，就潜在死锁。如PCB总数为100个已有10个进程，每个进程创建10个子进程，（且每个进程必需创建11个子进程才能完成任务）。:pid=fork();if(pid 0)printf(stderr,“fork failed”);printf(stderr,“fork failed”);exit(-1);exit(-1);if(pid=0)subprocess context if(pid=0)subprocess context else /parent process context else /parent process context :死锁的检测和恢复技术死锁的检
42、测和恢复技术：是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。(1)(1)死锁的检测死锁的检测 方法方法：用软件检查系统中由进程和资源构成的有向图是否包含一个或多个环路，若有，则存在死锁，否则不存在。2 2死锁的检测和恢复死锁的检测和恢复 例例 假定一个系统有七个进程：A AG G；六个资源：R RW W。l进程A保持资源R，请求资源S。l进程B没有保持资源，请求资源T。l进程C没有保持资源，请求S资源。l进程D保持资源U，请求S和T资源。l进程E保持T，请求V资源。l进程F保持W，请求S资源。l进程G保持V，请求U资源。ARSBTCSUDSTTVEWFSVGU图2.1
43、1 进程资源图RSWUTVACFDGBE环路环路死锁死锁环路：环路：DTEVGUDDTEVGUDD D、E E、G G是死锁进程是死锁进程需要一个数据结构L，用来记录系统中各节点的情况。执行过程中，标记已检测过的弧。类似于有向图的遍历。一个简单的死锁检测算法一个简单的死锁检测算法对图中的每个节点N，以N为起始节点，并将选中节点作为当前节点，开始执行：将L初始化为空表，执行以下算法。将当前节点加到L的末端，检查这个节点在表中是否出现过。如果是，这个图包含一个环路，算法终止。如果没有，转。由这个节点再看，是否有未标记过的引出弧。如果有，转；若没有，转。任意选择一个未标记的引出弧并标记它。然后，将引
44、出弧所到节点作为新的当前节点，转。若所有从这个节点引出的弧都已标记，则返回到前一个节点。如果这个节点是最初开始的节点，这个图没有包含环路，算法终止；若不是初始节点，再以该节点作为当前节点，转。例例 从B开始。由B跟踪引出弧一直到D，得L=B,T,E,V,G,U,D。此时D有两条引出弧，若向S方向，S是终结节点(没有引出弧)。因此，由D只能向T前进，并修改 L=L=B,T,E,V,G,U,D,TB,T,E,V,G,U,D,T，由表中看出，T出现两次，因此，该图包含环路，停止算法的执行。由于存在环路，故存在死锁。死锁进程为D、E、G。RSWUTVACFDGBE环路环路死锁死锁1.1.强制终止某个或
45、某几个进程强制终止某个或某几个进程：系统会收回分配给进程的所有资源。2.2.资源抢占资源抢占：逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。选择一个牺牲品：必须确定抢占顺序以最小化系统代价。回滚：应对被抢占资源的进程做些安排，回滚到某个安全状态，以便从该状态重启进程。（2 2）死锁的恢复）死锁的恢复选择选择“代价最小进程代价最小进程”的原则的原则l目前刚刚启动的进程l目前为止产生的输出最少；l预计剩余的时间最长；l目前为止分配的资源总量最少；l优先级最低。基本思想基本思想：允许进程动态地申请资源。系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，
46、便将资源分配给进程；否则，进程等待。安全状态安全状态：是指系统能按某种顺序，如p1,p2,pn(安全序列)，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。3 3 死锁的避免死锁的避免(1)进程的资源轨迹进程的资源轨迹 l避免死锁的主要方法是以系统的安全状态为基础的。l 用图2.12所示的进程资源轨迹图来讨论的安全状态的概念。有两个进程（A和B）有两个资源（一台打印机和一台绘图仪）水平坐标表示A进程语句系列，综坐标表示进程B指令序列。每个进程都需要两个资源才能完成自己的任务。绘图仪打印机绘图仪打印机B进程进程A进程进程图图2.12 一个单处理器系统的进程资源轨迹图禁区安全安全
47、安全安全 安全不安全死锁点死锁点(2)(2)银行家算法银行家算法(Bankers Algorithm)(Bankers Algorithm)l最具代表性的避免死锁的算法是Dijkstra的银行家算法，是在1965年提出的。l利用了上面图中介绍的避免进程进入不安全区的原理。l该算法能用于银行系统的现金贷款的发放上。例例 银行家算法是用来模拟一个小城镇的银行家为一批顾客贷款的问题。有四个顾客：A，B，C，D，每个顾客提出的最大贷款数量分别为6、5、4、7(以千美元为单位)。银行家知道不是所有顾客都马上需要其全部贷款（22）。因此，他只保留10个单位数量(而不是全部22个单位)为这些顾客服务。在这个
48、模型中，顾客是并发进程，现金是资源，而银行家就是操作系统。图图2.13 资源的三种分配状态资源的三种分配状态C C 得到全部贷款后，很快将其全部贷款还清得到全部贷款后，很快将其全部贷款还清顾客拥有量最大需求A06B05C04D07系统拥有量:10(a)初始状态顾客拥有量最大需求A16B15C24D47当前剩余量:2(b)安全状态顾客拥有量最大需求A16B25C24D47当前剩余量:1(c)不安全状态lAvailable：可用资源向量。一个含有m个元素的数组，每个元素代表一类资源可用的数目。l Max：最大需求矩阵。nm矩阵，Max(i,j)=k表示进程i 需要j类资源最大数目为k。lAlloc
49、ation：分配矩阵。nm矩阵，Allocation(i,j)=k 表示进程i当前已分得j类资源数目为k。lNeed：剩余需求矩阵。nm矩阵，Need(i,j)=k表示进程i 还需要j类资源k个。lRequest：进程的当前请求向量。若Requestij=k，表示进程Pi请求j类资源k个。银行家算法银行家算法 若RequestiNeedi，则转；否则，出错。若RequestiAvailable，则转；否则，Pi等待。系统试探把请求的资源分配给进程Pi。Available=Available Requesti Allocationi =Allocationi+Requesti Needi=Nee
50、di Requesti检测此次资源分配后系统是否处于安全状态。若安全，才正式将资源分给进程Pi；否则，试探分配作废，让Pi等待。具体实现：扫描Need的每一行，选择其中一行，若其Needi Available，让其释放资源（使Available Allocationi Available；），并标记该进程为完成。再选择其中一行，重复执行上述操作，直待所有进程被标记时，系统状态才是安全的。，才实施实际分配。进程进程Pi发出资源请求发出资源请求Requesti后，后，系统进行安全检查：系统进行安全检查：例例 P52有一个四种资源，五个进程的系统，初始时：Available=(6,3,4,2)，4类
