第6章-进程管理与作业管理2

进程的安全性1死锁概述操作系统中的死锁基于如下假定：任意一个进程要求资源的最大数量不超过系统能提供的最大量；如果一个进程在执行中提出的资源要求能够得到满足，那么它一定能在有限时间内结束；一个资源在任何时刻最多只为一个进程所占有；一个进程申请资源，只在资源得不到满足时才处于等待状态；一个进程结束时释放它所占有的全部资源；系统具有有限个进程和资源。2死锁在多道程序系统中，若干个进程彼此相互等待对方拥有且不会释放的资源，从而形成各进程都想得到资源而又都得不到资源，因而不能继续向前推进的僵局状态，就叫死锁。3例1：进程推进顺序不当产生死锁设系统有打印机、读卡机各一台，被进程P和Q共享。两个进程并发执行，按下列次序请求和释放资源：进程P 进程Q

请求读卡机 请求打印机请求打印机 请求读卡机释放读卡机 释放读卡机释放打印机 释放打印机4例2PV操作使用不当产生死锁 进程Q1 进程Q2 ……… ………P(S1);P(s2);P(s2);P(s1);

使用r1和r2;使用r1和r2V(S1); V(s2);V(S2);V(S1);5资源的概念资源的分类a、可再用资源/消耗性资源可再用资源：可供进程重复使用如：硬件资源、软件资源消耗性资源：由某个进程所产生，只为另一个进程使用一次，或经短暂时间后便不再使用的资源。如：时钟中断、同步信号、消息等b、共享/独享资源：例如CPU、主存/打印机c、可剥夺/不可剥夺资源6产生死锁的必要条件互斥：对于独占资源，每个资源每次只能给一个进程使用，进程申请到了资源后占为己有，则排斥其他进程享受该资源非剥夺：正在使用的资源不可剥夺，进程获得的资源尚未使用完毕之前，只能由占有者自己释放，不能被其他进程强行占用占有且等待：进程因未分配到新的资源而受阻，但对已占有的资源又“死抱住不放”循环等待：存在进程的循环等待链，前一进程占有的资源是后一进程所需求的资源，结果就形成了循环等待的僵持局面说明：发生死锁，则四个条件一定同时成立；破坏其中一个，死锁就可以阻止。7资源分配图约定Pi→Rj为请求边，表示进程Pi申请资源类Rj中的一个资源得不到满足而处于等待Rj类资源的状态，该有向边从进程开始指到方框的边缘，表示进程Pi申请Rj类中的一个资源。Rj→Pi为分配边，表示Rj类中的一个资源已被进程Pi占用，由于已把一个具体的资源分给了进程Pi，故该有向边从方框内的某个圆点出发指向进程。8资源分配图的一个例子R1R2P1P2P3R39资源分配图的另一个例子R1R2P1P2P3P410资源分配图死锁状态(1)如果进程-资源分配图中无环路，则此时系统没有发生死锁。(2)如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。(3)如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。11处理死锁的基本方法死锁的预防死锁的避免死锁的检测死锁的解除（＊）12死锁的预防死锁预防策略是试图设计一种系统，在这样的系统中排除发生死锁的可能性。可以把死锁预防方法看作两类间接的死锁预防方法：即防止前三个必要条件中任何一个的发生直接的死锁预防方法：即防止循环等待的发生13死锁的预防(1)破坏互斥条件使资源可同时访问而不是互斥使用，是个简单的办法，磁盘可用这种办法管理,但有许多资源往往是不能同时访问，所以这种做法许多场合行不通。所以一般来说，4个条件中的互斥条件不可能禁止。如果访问资源要求互斥，操作系统必须支持。某些资源，如文件，可能允许多个读访问，但只允许互斥的写访问。即使在这种情况下，如果有多个进程要求写权限，也可能发生死锁。14死锁的预防(2)剥夺式分配采用剥夺式调度方法可破坏第二个条件，但只适用于对主存资源和处理器资源的分配；如果占有某些资源的一个进程，其进一步的资源请求被拒绝，则该进程必须释放它最初的资源；如果一个进程请求当前被另一个进程占有的一个资源，操作系统可以剥夺第二个进程，要求它释放资源；只有当应用于资源的状态可以很容易地保存并在以后恢复的情况下(像处理器一样)，这种方法才是实用的15死锁的预防(3)按序分配采用资源顺序使用法，破坏环路条件;循环等待条件可以通过定义资源类型线性顺序来预防。如果一个进程已经分配到了R类型资源，它接下来请求的资源只能是那些排在R类型之后的资源类型。和占有等待预防一样，循环等待预防可能是低效的，它使进程执行速度变慢，并且可能没有必要地拒绝资源访问。16死锁的预防(4)系统分配静态预分配,破坏部分分配条件：一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。缺点：a、资源浪费

b、作业延迟17死锁的避免解决死锁问题的另一种方法是死锁避免。在死锁预防中，约束资源请求，至少防止4个死锁条件中的一个发生。这可以通过防止发生三个必要策略条件中的一个直接完成，也可以通过防止循环等待间接完成，但这都会导致低效的资源使用和低效的进程执行。死锁避免则相反，它允许三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此避免比预防允许更多的并发。18预防和避免的比较19死锁的避免死锁避免的优点是它不需要死锁预防中的剥夺和重新运行进程，并且比死锁预防的限制少，但在使用中也有许多限制。必须事先声明每个进程请求的最大资源；考虑的进程必须是无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制；分配的资源数目必须是固定的；在占有资源时，进程不能退出。20避免死锁的算法——银行家算法银行家算法银行家拥有一笔周转资金。客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款。银行家应谨慎的贷款，防止出现坏帐。用银行家算法避免死锁操作系统(银行家)操作系统管理的资源(周转资金)进程(要求贷款的客户)21银行家算法的数据结构Available:可利用的资源量；Needi：进程Pi尚需要的各类资源数；Allocation：已经分配给某进程的资源数；Requesti：进程Pi的请求量。(1)若Requesti≤Needi，转向步骤(2)，否则出错；(2)若Requesti≤Available，转向步骤(3)，否则表示系统没有足够的资源，进程Pi必须等待；(3)系统试探分配资源，修改以下数据：

Available=Available–Requesti Allocation=Allocation+Requesti

Needi=Needi-Requesti(4)执行安全检查：系统是否处于安全状态。 若系统处于安全状态，才正式将资源分配给进程Pi；

若系统不安全，试探分配作废，恢复资源原态，进程Pi等待。22银行家算法的安全检查算法(1)设置两个向量Work:系统可提供进程继续运行所需要的各类资源数； 初始值：work=available;Finish:系统能否有足够的资源分配给进程完成 初始值：Finish[i]=false;得到资源后为True(2)从进程集合中找到一个能满足下列条件的进程：

Finish[i]=false;Needi≤available若找到这样的进程，执行步骤(3)，否则执行步骤(4)；(3)进程获得资源后，可以顺利执行，直到完成，释放所有资源：

work=work+Allocation；

Finishe[i]=false;

回到步骤(2);(4)如果所有进程的Finish[i]=True；表示系统安全；否则系统表示不安全状态；23银行家算法银行家算法的特点允许互斥、部分分配和不可抢占，可提高资源利用率；要求事先说明最大资源要求，在现实中很困难；银行家算法的缺点：①要求被分配的各类资源数量固定；②要求用户也要保持不变；③算法只保证用户在有限时间内得到满足，难以满足更高响应的要求；④需要花费很多时间用于不断的测试。24银行家算法示例现在有12个资源供三个进程共享，进程1共需要4个资源，但第一次先申请一个资源；进程2总共需要6个资源，第一次要求4个资源；进程3总共需要8个资源，第一次需要5个资源。现在的分配情况如下：进程已占资源数最大需求量P1P2P31454③

6②8③剩余资源数

2系统安全25银行家算法示例系统不安全银行家算法就是不断测试各个进程占用和申请资源的情况，在保证至少一个进程能得到所需的全部资源的前提下进行资源的分配。进程已占资源数最大需求量P1P2P32454②

6②8③剩余资源数126银行家算法示例对每个请求进行检查，是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

系统拥有某类资源10个进程已有资源数还要申请资源数P44Q22R2727银行家算法示例存在一个状态序列能够使所有的客户均得到其所有的贷款，则称该状态是安全的。28银行家算法示例图示状态是安全的，以使Marvin运行结束，释放所有的4个单位资金。这样下去便可满足Suzanne或Barbara的请求。考虑给Barbara另一个她申请的资源，则得到的状态是不安全的。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。29死锁的检测死锁检测算法与死锁避免算法是类似的，不同在于前者考虑了检查每个进程还需要的所有资源能否满足要求；而后者则仅要根据进程的当前申请资源量来判断系统是否进入了不安全状态。死锁检测算法的策略是查找一个进程，使得可用资源可以满足该进程的资源请求，然后假设同意这些资源，让进程运行直到完成，再释放它的所有资源，然后算法寻找另一个可以满足资源请求的进程。30死锁的检测用表格来记录进程使用和等待资源的情况。进程依次申请已占等待资源P1P2P3r1、r5、r3r3、r4、r2r2、r5r5、r1r3r2r3r2、r4r5出现死锁31解除死锁①资源剥夺法②撤消进程法32解除死锁立即结束所有进程的执行，并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。撤销陷于死锁的所有进程,解除死锁继续运行。逐个撤销陷于死锁的进程,回收其资源,直至死锁解除。剥夺陷于死锁的进程占用的资源，但并不撤销它,直至死锁解除。根据系统保存的checkpoint,让所有进程回退,直到足以解除死锁。当检测到死锁时，如果存在某些未卷入死锁的进程，而这些进程随着建立一些新的抑制进程能执行到结束，则它们可能释放足够的资源来解除死锁。33小结和示例例:

假定希望顺序执行s1,s2,s3,但s2需互斥执行。请利用信号量机制和P/V操作实现这一要求。解:

设S=1(初值)，程序段为：

s1;P(s);s2;V(s)；s334线程35线程的基本概念研究可否将进程的属性分开，由操作系统分别进行处理。即把处理机调度和其他资源的分配针对不同的活动实体进行；而对拥有资源的基本单位，不进行频繁切换。正是这样，产生了线程概念。在引入线程的操作系统中，线程是进程中的一个实体，是被系统独立调度和分配的基本单位。线程基本上不拥有系统资源，只拥有一些在运行中必不可少的资源(如程序计数器、一组寄存器和栈)，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程；同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中也呈现出间断性、相应地，线程也同样有就绪、阻塞和执行三种基本状态，有的系统中线程还有终止状态。36线程与进程的比较调度：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。37作业管理38作业管理概述(1)作业由程序、数据和作业说明书三部分组成。作业说明书包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。39作业管理概述(2)作业进入系统和作业建立启动SPOOLing系统的“预输入”程序实现作业的装入。(p208)作业建立：接收作业信息，组织文件，建立JCB。作业控制块JCB(p166)JCB是记录类型的数据结构；包含对作业进行管理的必要信息；比如：用户名、作业名；优先级、地址、长度、类型说明、作业状态等JCB是作业调度的基本依据，是作业存在的唯一标志。40作业管理概述(3)作业管理的任务作业调度：又称高级调度。主要功能是根据一定的算法，从一批作业中选取若干作业进入内存，并做好运行前的准备和作业完成后的善后工作。作业控制：指程序员或操作员对作业运行的全过程进行控制，从作业输入系统直到作业运行结束。分为联机作业控制和脱机作业控制。41作业状态四种状态①进入状态（提交状态）：在输入设备上预输入②后备状态：在输入井中，已建JCB，挂在队列中③运行状态：调入内存，参与对CPU的竞争；先到"就绪"，经调度"运行"，有I/O请求"等待"，I/O完成到"就绪"④完成状态：运行完毕或非正常终止，回收全部资源，释放PCB和JCB。42作业状态变迁43处理机调度的层次三级调度层次高级调度(HighLevelScheduling)低级调度(LowLevelScheduling)中级调度(IntermediateLevelScheduling)44高级调度作业调度/长程调度用于决定把外存上处于后备队列的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上。两个决定：接纳多少作业；接纳哪些作业。45低级调度进程调度/短程调度它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给进程的操作。短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能。两种调度方式：非剥夺方式剥夺方式：时间片原则、优先权原则、短作业优先原则……46中级调度平衡负载调度，中程调度。引入目的：为了提高内存的利用率和系统的吞吐量决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源。中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换。47中级调度中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过把一些进程换出主存，使之进入“挂起”状态，不参与进程调度，起到平滑和调整系统负荷的作用。使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待；当这些进程重又具备运行条件，且内存又稍有空闲时由中级调度决定将哪些进程重新调入内存。48处理器调度的层次中级调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态49调度的模型中级调度处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度50作业调度及调度算法检查系统是否