1、计算机操作系统计算机操作系统 进程调度进程调度摘要基础：进程调度策略：进程调度实现：互斥与同步-避免：死锁与饥饿避免：死锁与饥饿-解决：几个经典问题（如生产者解决：几个经典问题（如生产者-消费者）消费者）-了解：进程通信了解：进程通信单道程序与多道程序的执行 单道程序执行的过程 多道程序执行的过程课堂思考与练习 设时刻0，在内存中有三个程序A、B、C，占用CPU的优先权为A最高，C最低；它们的计算和I/O操作时间如表所示。试画出单道运行和多道运行的时间关系图。ABC计算306020I/O403040计算101020什么叫进程？为什么要引入“进程”这一概念？为了提高系统资源的利用率，出现了多道程
2、序设计技术，但多道程序的并发执行和资源共享带来了新的问题，破坏了程序的封闭性和可再现性，程序和机器执行程序的活动不再一一对应，并发程序之间有可能存在相互制约关系。并发程序的独立性、并发性、动态性和相互制约反映了并发程序的本质，而程序的概念已不能反映程序并发执行的实质，因此，人们引入了进程的概念来描述并发程序的执行过程。进程：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。进程=程序的执行？进程和程序的区别和关系？进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：(1)进程是
3、一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。(2)进程具有并行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征。(3)进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。这里，制约就是对进程独立性和异步性的限制。(4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同。如何监控程序的执行？用各种数据结构来记录多个进程（PCB
4、）用状态的变迁来跟踪多个进程用进程调度来选择控制多个进程用并发控制来同步、协调多个进程进程的静态描述进程=程序+数据+进程控制块PCB 程序描述进程所要完成的功能 数据是对其进行操作的数据结构集，程序在执行时必不可少的工作区和操作对象。进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。进程状态及转换进程控制 进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。1.进程创建 2.进程撤销 3.进程阻塞 4.进程唤醒 5.进程切换：在某一时刻，一运行的进程被迫中断，让出C
5、PU给指定进程。一般在进行进程上下文切换时，不保留被切换的进程上下文的正文，但保留进程执行时所使用的寄存器。程序执行过程单进程单一进程多进程独立进程彼此独立多进程协作进程彼此依赖在并发环境下不存在完全独立的进程！程序执行过程多进程竞争进程共享互斥共享资源多进程通信进程相互通信程序执行过程中的问题不存在资源竞争，只存在CPU调度多个进程相互依赖、彼此竞争资源，既存在CPU调度，又存在同步协调，从而引入并发控制。并发控制的实施 策略：临界资源与临界区 机制：标志、信号量 方法：加锁、P、V原语 实现：互斥和同步进程互斥（1）临界资源：一次仅允许一个进程使用的共享资源。每次只准许一个进程进入临界区，
6、进入后不允许其他进程进入。对于临界资源，多个进程必须互斥地对它进行访问。临界区：每个进程中访问临界资源的那段代码。临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的。间接制约：由共享公有资源而造成的对并发进程执行速度的间接制约。即把这种由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象。进程互斥（2）互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。当占用临界资源的进程
7、退出临界区，才允许另一进程区访问此临界资源。为了禁止两个进程同时进入临界区，需采用一定的方法来协调它们。无论方法是什么都应遵循下述准则：1.空闲让出2.忙则等待3.让权等待4.有限等待进程互斥（3）互斥的加锁实现 对临界区加锁以实现互斥：当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。进程互斥（4）设临界区的类名为。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位 key。key表示该锁定位属于类名为的临界区。加锁后的临界区程序描述如下：l
8、ock(key)临 界 区unlock(key)设key=1时表示类名为的临界区可用，key=0时表示类名为的临界区不可用。进程互斥（5）一种简便的实现方法是：lock(x)=begin local vrepeatvxuntilv=1x0end 因为当同时有几个进程调用lock(key)时，在x0语句执行之前，可能已有两个以上的多个进程由于key=1而进入临界区。为解决这个问题有些机器在硬件中设置了“测试与设置指令，保证第一步和第二步执行不可分离。注意：在系统实现时锁定位key 总是设置在公有资源所对应的数据结构中的。进程互斥（6）试考虑以下进程PA和PB反复使用临界区的情况：PAA：lock
9、(key)unlock(key)Goto APBB：lock(key)unlock(key)Goto B 设进程A已通过lock(key)过程而进入临界区。显然，在进程PA执行unlock(key)过程之前，key=0且进程PB没有进入临界区的机会。然而，当进程PA执行完unlock(key)过程之后，由于紧接着是一转向语句，进程PA将又立即去执行lock(key)过程。此时，由于unlock(key)过程已将key的值置为1，也就是开锁状态，从而进程PA又可进入临界区。只有在进程PA执行完unlock(key)过程之后、执行Goto A语句之前的瞬间发生进程调度，使进程PA把处理机转让给进程
10、PB，进程PB才有可能得到执行。然而遗憾的是，这种可能性是非常小的。因此，进程PB将处于永久饥饿状态（starvation）。使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象。进程互斥（7）这正如某个学生想使用某个人人都可借用、且不规定使用时间的教室时一样，他必须首先申请获得使用该教室的权利，然后再到教室看看该教室是不是被锁上了。如果该教室被锁上了，他只好下次再来观察，看该教室的门是否已被打开。这种反复将持续到他进门后为止。从这个例子中，可以得到解决加锁法所带来的问题的方法。一种最直观的办法是，设置一个教室管理员。从而，如果有学生申请使用教室而未能如愿时，教室管理员记下他的名字，
11、并等到教室门一打开则通知该学生进入。这样，既减少了学生多次来去教室检查门是否被打开的时间，又减少了因为学生自发地检查造成的不公平现象。在操作系统中，这个管理员就是信号量。信号量管理相应临界区的公有资源，它代表可用资源实体。进程互斥（8）信号量 信号量的概念和下面所述的、原语是荷兰科学家E.W.Dijkstra提出来的。信号是铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。在操作系统中，信号量sem是一整数。在sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。显然，用于互斥的信号量sem的初值应该大于零，而建立一个信
12、号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程。进程互斥（9），原语 信号量的数值仅能由，原语操作改变(和分别是荷兰语 Passeren 和Verhoog 的头一个字母，相当于英文的pass和increment的意思)。采用，原语，可以把类名为的临界区描述为When do(sem)临界区(sem)od。这里，sem是与临界区内所使用的公用资源有关的信号量。一次原语操作使得信号量sem减1，而一次原语操作将使得信号量sem加1。必须强调的一点是，当某个进程正在临界区内执行时，其他进程如果执行了原语操作，则该进程并不像调用lock时那样因进
13、不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做原语操作释放资源后，进入临界区，这时，原语的执行才算真正结束。另外，当有好几个进程执行原语未通过而进入等待状态之后，如有某进程作了原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。进程互斥（10）原语操作的主要动作是：(1)sem减 1；(2)若sem减1后仍大于或等于零，则进程继续执行；(3)若sem减1后小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度。进程互斥（11）原语的操作主要动作是：(1)sem加1；(2)若相加结果大于零，进程继续执行；(3)若相加结果小于或等于零，则
14、从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。用，原语实现进程互斥利用，原语和信号量，可以方便地解决并发进程的互斥问题，而且不会产生使用加锁法解决互斥问题时所出现的问题。设信号量sem是用于互斥的信号量，且其初值为1表示没有并发进程使用该临界区。显然，由上面几节的讨论可知，只要把临界区置于(sem)和(sem)之间，即可实现进程间的互斥。当一个进程想要进入临界区时，它必须先执行原语操作以将信号量sem减1。在一个进程完成对临界区的操作之后，它必须执行原语操作以释放它所占用的临界区。由于信号量初始值为 1，所以，任一进程在执行原语操作之后将sem的值变为0，表示该进程
15、可以进入临界区。s10-1-2-101Wait 操作信号量非负，P1进入临界区Wait 操作信号量为负，P2阻塞Wait 操作信号量为负，P3 阻塞Signal 操作后信号量非正，从等待队列中唤醒一个进程Signal 操作后信号量非正，从等待队列中唤醒一个进程Signal 操作后信号量为正，表示已无进程在临界区用信号量实现两并发进程PA，PB互斥的描述如下：1)设 sem为互斥信号量，其取值范围为(1,0,-1)。其中sem=1表示进程PA和PB都未进入类名为的临界区，sem=0表示进程PA或PB已进入类名为的临界区，sem=-1表示进程PA和PB中，一个进程已进入临界区，而另一个进程等待进入
16、临界区。2）描述：PA：（sem）（sem）：PB：（sem）（sem）：练习与思考一试用P、V操作实现飞机联网售票系统中各地N个终端的终端售票进程发售同月同日同一次航班机票的过程。例：设余票单元为 count，有 N 个售票进程正确并发执行的算法Process Pi(i=1,2,n)Begin begin count:integer;s:semaphore;Var Xi:integer;s:=1;按旅客要求找到 count;cobeginP(s);P1;Xi:=count;P2;If Xi=1 then begin Pn;Xi:=Xi-1;coendXi:=count;end.V(s);输出
17、一张票;EndElse输出“票已售完”;End;思考与练习二两个火车站 A、B 之间是单轨连接，现有许多列车同时到达 A 站，经 A 站到 B 站，列车驶出 B 站后又可分路行驶。为了保证行车安全，请用信号量机制设计一个自动调度算法。Program mutualexclusion;begin(*main program*)Count=n;(*n为列车数*);cobegin Var s:semaphore(:=1);P(1);Procedure P(i:integer);P(2);Begin P(n);Repeat coend P(s);end.列车驶入A、B段;V(s);列车分路行驶 Fore
18、verEnd;进程同步（1）除了对公有资源的竞争而引起的间接制约之外，并发进程之间是否还存在着其他制约关系影响执行速度呢？来看下面的例子。计算进程和打印进程共同使用同一缓冲区Buf。计算进程反复地把每次计算结果放入 Buf中，而打印进程则把计算进程每次放入 Buf中的数据通过打印机打印输出。如果不采取任何制约措施，这两个进程的执行起始时间和执行速度都是彼此独立的，其相应的控制段可以描述为：PC：:A:local BufRepeatBuf BufUntil Buf=空计算得到计算结果Buf 计算结果Goto APP:：:B:local PriRepeatPri BufUntil Pri 空打印
19、Buf中的数据清除 Buf中的数据Goto B 直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程。进程同步：把异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程。具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。如果对一个消息或事件赋以唯一的消息名，则可用过程wait（消息名）表示进程等待合作进程发来的消息，而用过程signal（消息名）表示向合作进程发送消息。利用过程wait和signal，可以简单地描述上面例子中的计算进程PC和打印进程PP的同步关系
20、如下：（1）设消息名Bufempty表示Buf空，消息名Buffull表示Buf中装满了数据。（2）初始化Bufempty=true，Buffull=false。（3）描述：PC：A:wait（Bufempty）计算Buf 计算结果Bufempty falsesignal（Buffull）GotoAPP：B:wait（Buffull）打印Buf中的数据清除Buf中的数据Buffull falsesignal（Bufempty）GotoB过程wait的功能是等待到消息名为true的进程继续执行，而signal的功能则是向合作进程发送合作进程所需要的消息名，并将其值置为true。私用信号量：上面用
21、wait（消息名）与signal（消息名）的方式，描述了进程同步的一种实现方法。只与制约进程及被制约进程有关而不是与整组并发进程有关，称该信号量为私用信号量。公用信号量：一个进程Pi的私用信号量Semi是从制约进程发送来的进程Pi的执行条件所需要的消息。与私用信号量相对应，称互斥时使用的信号量为公用信号量。用，原语操作实现同步 利用，原语实现进程同步的方法与利用wait和signal过程时相同，也是分为三步。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用，原语和私用信号量规定各进程的执行顺序。缓冲区队列缓冲区队列例：设进程PA和PB通过缓冲区队列传递数据（如上图）。PA为发送
22、进程，PB为接收进程。PA发送数据时调用发送过程deposit(data)，PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：（1）在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度），即缓冲区空时PB不能取数；（2）PA往缓冲队列发送数据时，至少有一个缓冲区是空的，即缓冲区满时PA不能送数；（3）由PA发送的数据块在缓冲队列中按先进先出（FIFO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。解：由题意可知，进程PA调用的过程deposit(data)和进程PB调用的过程rem
23、ove(data)必须同步执行，因为过程 deposit(data)的执行结果是过程remove(data)的执行条件，而当缓冲队列全部装满数据时，remove(data)的执行结果又是deposit(data)的执行条件，满足同步定义。从而，按以下三步描述过程deposit(data)和remove(data)：（1）设Bufempty为进程PA的私用信号量，Buffull 为进程PB的私用信号量；（2）令Bufempty的初始值为n（n 为缓冲队列的缓冲区个数），Buffull 的初始值为0；（3）描述：PA:deposit(data):begin local xP(Bufempty)；按
24、FIFO方式选择一个空缓冲区Buf(x)；Buf(x)dataBuf(x)置满标记（Buffull）endPB:remove(data):Begin local x（Buffull）；按FIFO方式选择一个装满数据的缓冲区Buf(x)data Buf(x)Buf(x)置空标记（Bufempty）end思考与练习 设课程的前驱、后继关系如下，若每修一门课程看作进程Px（x1.6）试用P、V操作算法描述这种前驱与后继关系。计算机导论高级语言程序设计 计算机组成原理 数据结构 86汇编语言 计算机操作系统生产者-消费者问题 把并发进程的同步和互斥问题一般化，可以得到一个抽象的一般模型，即生产者-消费
25、者问题。计算机系统中，每个进程都申请使用和释放各种不同类型的资源，这些资源既可以是像外设、内存及缓冲区等硬件资源，也包括临界区、数据、例程等软件资源。把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。例如在上面的计算进程PC与打印进程PP公用一个缓冲区的例子中，计算进程PC把数据送入缓冲区，打印进程PP从缓冲区中取数据打印输出，因此，PC进程相当于数据资源的生产者，而PP进程相当于消费者。用信号量解决生产者/消费者问题说明 假如是一个生产者、一个消费者，且缓冲区只有一个单元。Begin Process producer Process consumer
26、Buffer:integer;Begin Begin Se,Sf:semaphore;Repeat Repeat Se:=1;Sf:=0;Produce a product;P(Sf);cobegin P(Se);Take a product;producer;Buffer:=product;V(Se);consumer;V(Sf);Consumer;coend Forever Forever End.End;End;验证：1、缓冲区满生产者不能送数；缓冲区空消费者不能取数 2、在这个问题中同步隐含着互斥。用信号量解决生产者/消费者问题说明 假如是一个生产者、一个消费者，且缓冲区有 N 个单元
27、。当缓冲区没有放满 N 个数据时，生产者进程调用 P（Se）都不会成为等待状态，可以把数据送入缓冲区。但当缓冲区中已有 N 个数据时，生产者进程想要再送数将被拒绝。由于每送入一个数后要调用 V（Sf），所以此时 Sf 的值表示缓冲区中可取的数据数，只要 Sf 0，消费者进程在调用 P（Sf）后总可以从缓冲区取数。每取走一个数据就调用 V（Se），因此增加了一个存放数据的位置。可以用指针 in 和 out 分别指示生产者进程向缓冲区送数和消费者进程从缓冲区取数的相对位置；指针的初始值为“0”。这种情况下生产者与消费者进程的同步算法为：用信号量解决生产者/消费者问题说明Begin Process
28、producer Process consumer B:array0.n-1 of integer;Begin Begin in,out:integer;Repeat Repeat Se,Sf:semaphore;Produce a product;P(Sf);in:=out:=0;P(Se);Take a product from Bout;Se:=n;Sf:=0;Bin:=product;out:=(out+1)mod n;cobegin in:=(in+1)mod n;V(Se);producer;V(Sf);Consumer;consumer;Forever Forever coend
29、 End;End;End.说明：这时缓冲区可以看成是头尾相连一个环形，in、out 指针指出存取数的位置。验证：1、缓冲区满生产者不能送数；缓冲区空消费者不能取数 2、在这个问题中生产者与消费者进程有可能同时进入缓冲区，但不会出错。把一个长度为的有界缓冲区（n0)与一群生产者进程1，2，m和一群消费者进程1，2，k联系起来（如图3.14所示）。设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程deposit(data)和各消费者使用的过程remove(data)可描述如下：首先，可以看到，上述生产者-消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：(1)消费者想接收
30、数据时，有界缓冲区中至少有一个单元是满的；(2)生产者想发送数据时，有界缓冲区中至少有一个单元是空的。另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。图3.14 生产者-消费者问题由以上分析，设公用信号量mutex保证生产者进程和消费者进程之间的互斥，设信号量avail为生产者进程的私用信号量，信号量full为消费者进程的私用信号量。信号量avail表示有界缓冲区中的空单元数，初值为n；信号量full表示有界缓冲区中非空单元数，初值为0。信号量mutex表示可用有界缓冲区的个数，初值为 1。从而有：deposit(data):begin（avail）（mute
31、x）送数据入缓冲区某单元（full）（mutex）endremove(data):begin（full）（mutex）取缓冲区中某单元数据（avail）（mutex）end在上例中，由于一个过程中包含有几个公用、私用信号量，因此，、原语的操作次序要非常小心。一般说来，由于原语是释放资源的，所以可以以任意次序出现。但原语则不然，如果次序混乱，将会造成进程之间的死锁。关于死锁，将在3.8 中介绍。用信号量解决生产者/消费者问题说明 假设是M个生产者、R个消费者，且缓冲区有 N 个单元。现在不仅生产者与消费者之间要同步，而且 M 个生产者之间、R 个消费者之间还必须互斥地访问缓冲区。要同步的原因和前
32、面的问题一样；之所以要互斥是因为如果 M 个生产者进程各自个向缓冲区送数，当第一个生产者按指针 in 指示的位置送一个数，但在改变指针前可能被打断执行，于是当第二个生产者送数时仍按原指针所指出的位置存放，这样两个数被放在同一个单元，造成数据丢失。同样，R 个消费者都要取数时可能都从指针 out 指出的位置取数，造成一个数据被重复取出。用信号量解决生产者/消费者问题说明如果该问题描述在任一时刻只能有一方(生产者或消费者)访问缓冲区。即一次只能有一个进程可以进入缓冲区。这是第一种方法（书上前例）。可是、当有一个生产者（或消费者）在送数（或取数）时，可以允许一个消费者（或生产者）同时访问缓冲区去取数
33、（或送数）。因此这是第二种方法。显然、第二种方法的并行性要比第一种方法的并行性高。用信号量解决生产者/消费者问题说明第一种方法Begin Process producer i Process consumer j B:array0.n-1 of integer;Begin Begin in,out:integer;Repeat Repeat S,Se,Sf:semaphore;Produce a product;P(Sf);in:=out:=0;P(Se)P(S);S:=1;Se:=n;Sf:=0 P(S);Take a product from Bout;cobegin Bin:=produ
34、ct;out:=(out+1)mod n;producer;in:=(in+1)mod n;V(Se);consumer;V(Sf);V(S);coend V(S);Consumer;End.Forever Forever End;End;思考：1、如果生产者或消费者进程中的两个 P 操作次序对调 可以吗？2、第二种方法应该如何改写？思考与练习 有三个进程R、P、D，进程R从输入设备上读数据到缓冲区B，进程P将缓冲区B中的数据写到磁带、进程D将缓冲区B中的数据写到磁盘（即把一个数据做两个副本分别存放在磁盘和磁带上），P、D互斥共享缓冲区B；设B只能放一个数据，试用信号量机制写出R、P、D三个进
35、程的同步工作算法。解答 分析：R与P、R与D之间为同步关系；P与D之间为互斥关系 信号量：S表示P、D之间的互斥，初值为1Se1、Sf1表示R、P之间的同步关系，Se1初值为1、Sf1初值为0Se2、Sf2表示R、D之间的同步关系，Se2初值为1、Sf2初值为0 算法：R（）、P（）、D（）并发执行。R（）P（）D（）while(1)while(1)while(1)读数；P（Sf1）；P（Sf2）；P（Se1）；P（S）；P（S）；P（Se2）；从B中取数到磁带；从B中取数到磁盘；送数到B中；V（S）；V（S）；V（Sf1）；V（Se1）；V（Se2）；V（Sf2）；并发控制是否完全解决问题？
36、死锁死锁 死锁：指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。死锁的起因死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是，可以采用适当的资源分配算法，以达到消除死锁的目的。为此，先看看产生死锁的必要条件。产生死锁的必要条件(1)互斥条件。并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。(
37、2)不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。(3)部分分配。进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。(4)环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。显然，只要使上述4个必要条件中的某一个不满足，则死锁就可以排除。死锁的排除方法 预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构
38、能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。在实际操作系统中大都使用检测与恢复法排除死锁。死锁预防1.打破资源的互斥条件。例如允许进程同时访问某些资源等2.打破不可剥夺条件，即允许剥夺。3.打破资源的部分分配。即预先分配各并发进程所需要的全部资源。如某个进程的资源得不到满足时，则安排一定的等待次序让其他进程释放资源。4.打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。死锁避免 死锁避免可被称为动态预防，因为系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并采取措施加以避免。死锁避免方法并不是严
39、格限制产生死锁必要条件的存在，只是防止系统进入不安全状态，从而避免死锁的发生。死锁避免算法就是避免系统进入不安全状态的算法。银行家（Banker）算法是最著名的死锁避免算法 首先，从每个进程预先得到有关该进程所需要资源的信息。然后，通过仔细的分配资源来避免死锁。（1）分配要使计算机系统总是停留在“安全”状态。（2）确保仅仅将以避免死锁的方式分配资源。如果存在一个安全序列，那么系统处于安全状态。存在进程顺序 P1、P2、P3、Pn 如果对于每个 Pi，Pi 申请的资源小于当前可用资源加上所有进程 Pj（其中 ji）所占有的资源，那么这一顺序为安全序列。如果没有这样的顺序存在，那么系统就处于不安全
40、状态。是否存在安全序列？设系统有三种类型的资源，数量为(4，2，2)，系统中有进程A，B，C按如下顺序请求资源：进程A申请(3，2，1)进程B申请(1，0，1)进程A申请(0，1，0)进程C申请(2，0，0)请你给出一种防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。银行家算法的主要思想（1）若进程Pi的申请超过了其申报的最大需求数，则报错；（2）若进程Pi的申请超过了可用资源数，则Pi必须等待；（3）否则，系统暂时为进程Pi分配其所需要的资源，修改资源分配状态；（4）调用安全算法检查系统当前状态，若导致不安全状态，则推迟这种分配。死锁检
41、测与恢复 当进程进行资源请求时死锁检测算法检查并发进程组是否构成资源的请求和保持环路。有限状态转移图和petriNet等技术都可用来有效地判断死锁发生。死锁的恢复办法较多。最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程时为止。另外，也可以从被锁住进程强迫剥夺资源以解除死锁。线程 引入线程主要是为了提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，以及便于系统管理。线程：一个进程内的基本调度单位，或称为轻权进程（Light weight process），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制。进程与线程的关系
