哈工大张英涛操作系统视频对应课件21_30(全)

操作系统第21讲主讲人：张英涛哈尔滨工业大学远程教育课程摒弃“请求和保持”条件系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。优点：简单、易实现且安全摒弃“请求和保持”条件的缺点资源被严重浪费，恶化了系统的利用率；使进程延迟运行。摒弃“不剥夺”条件进程逐个地提出资源要求。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后许需要时再重新申请。进程已经占有的资源，在运行过程中会被暂时地释放掉，可认为是被剥夺。摒弃“不剥夺”条件的缺点实现较复杂．代价大。可能因为反复地申请和释放资源，而使进程的执行无限地推迟、延长了进程的周转时间增加系统开销、降低系统吞吐量。摒弃“环路等待”条件系统将所有的资源按类型进行线性排队，并赋予不同的序号。所有进程请求资源严格按资源序号递增的次序提出，防止出现环路．摒弃“环路等待”条件的缺点（1）序号必须相对稳定，限制了新设备类型的增加。（2）作业(进程)使用资源顺序与系统规定的顺序不同而造成资源的浪费。例如，某进程先用磁带机．后用打印机，但按系统规定该进程应先申请打印机而后申请磁带机，使先打印机长期闲置。（3）限制了用户编程。系统安全状态指系统能按某种顺序如(P1，P2，…，Pn)，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列、则称系统处于不安全状态。系统进入不安全状态后可能进入死锁只要系统处于安全状态，系统便可避免进入死锁状态。避免死锁的实质：如何使系统不进入不安全状态。例：假定系统有三个进程P1、P2、P3．共有12台磁带机。进程P1总共要求10台磁带视，P2和P3分别要求4台和9台。设在T时刻，进程P1、P2、P3已分别获得；5台、2台和2台、尚有3台空闲未分．判断系统在T时刻的安全性。进程最大需求已分配可用p1P2p310495223安全序列P2、P1、P3进程最大需求已分配可用p1P2p3104952+223-2=11进程最大需求已分配可用p1p3109521+4=52进程最大需求已分配可用p3925+5=103进程最大需求已分配可用p39934谢谢收看操作系统第21讲哈尔滨工业大学张英涛操作系统第22讲主讲人：张英涛哈尔滨工业大学远程教育课程银行家算法避免死锁1．银行家算法中的数据结构2.银行家算法3.安全性算法4.银行家算法之例银行家算法的数据结构（1）可利用资源向量Available。（2）最大需求矩阵Max。（3）分配矩阵Allocation。（4）需求矩阵Need。可利用资源向量Available含有m个元素每个元素代表一类可利用的资源数目初值是该类全部可用资源的数目数值随该类资源的分配和回收而动态地改变。如：Available[j]=K，表示系统中现有Rj类资源K个。最大需求矩阵Maxn*m的矩阵定义了n个进程中的每一个进程对m类资源的最大需求。如：Max[i，j]=K，表示进程i需要Rj类资源的最大数值为K。分配矩阵Allocationn*m的矩阵定义了系统中每一类资源当前已分配给每一进程的资源数。如：Allocation[i，j]=K，表示进程i当前以分得Rj类资源的数目为K。需求矩阵Needn*m的矩阵表示每一个进程尚需的各类资源数。如：Need[i，j]=K，表示进程i还需要Rj类资源K个，方能完成其任务。三个矩阵间关系：Need[i，j]=Max[i，j]—Allocation[i，j]银行家算法设Requesti是进程pi的请求向量。如果Requesti[j]＝k，表示进程pi只需要k个Rj类型的资源。pi发出资源请求后．按下述步骤检查：（1）Requesti[j]≤Need[i,j]，则转向步骤2；否则，认为出错（2）Requesti[j]≤Available[j]则转向步骤3；否则，进程pi等待（3）系统试探着把资源分给进程pi：Available[j]：=Available[j]-Requesti[j]Allocation[i，j]：=Allocation[i，j]=+Requesti[j]；Need[i,j]=Need[i,j]-Requesti[j]；（4）系统执行安全性算法．检查此次资源分配后，系统是否处于安全状态。若安全，才将资源分配给进程；否则．将试探分配作废．恢复原来的资源分配状态、让进程pi等待。安全性算法（一）设置两个向量工作向量Work:供进程继续运行的各类资源数，含m个元素，初值Work:=AvailableFinish:表示系统是否有足够的资源分配给进程。初值：Finish[i]:=false,当有足够资源分配时Finish[i]:=true.（二）找满足下列条件的进程：Finish[i]:=falseNeed[i,j]≤Work[j];若找到执行步（三）否则执行步骤（四）（三）Work[j]：=Work[i]+Allocation[i,j];Finish[i]:=true;Gotostep2;（四）如果所有进程的Finish[i]:=true则系统处于不安全状态银行家算法之例系统中有五个进程{p0p1p2p3p4}，三类资源{A,B,C}，数目为；10，5，7.在T时刻的资源分配情况如图。资源进程MAXABCAllocationABCNeedABCAvailableABCp0p1p2p3p4753322902222433010200302211002743122600011431332workABCNeedABCAllocationABCWork+AllocationFinishp1p3p4p2p0332532743745104712201143160074320021100230201053274374510471057TTTTT安全性：P1请求资源，按银行家算法进行检查：（1）Request1(1,0,2)≤Need1(1,2,2)（2）Request1(1,0,2)≤AVailable1(3,3,2)（3）系统假定为P1分配资源并修改向量值（4）利用安全算法检查是否安全。资源进程MAXABCAllocationABCNeedABCAvailableABCp0p1p2p3p4753322902222433010200(302）302211002743122（020）600011431332(230)可得到安全序列：p1p3p4p2p0可以将p1申请的资源分配给它。谢谢收看操作系统第22讲哈尔滨工业大学张英涛操作系统第23讲主讲人：张英涛哈尔滨工业大学远程教育课程P4请求资源，按银行家算法进行检查：（1）Request4(3,3,0)≤Need4(1,2,2)（2）Request4(3,3,0)AVailable1(2,3,0)则P4等待。P0请求资源，按银行家算法进行检查：（1）Request0(0,2,0)≤Need0(7,4,3)（2）Request1(0,2,0)≤AVailable1(2,3,0)（3）系统假定为P0分配资源并修改向量值（4）利用安全算法检查是否安全。资源进程AllocationABCNeedABCAvailableABCp0p1p2p3p4030302302211002732020600011431210死锁的解除常采用的两种方法是：（1）剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。（2）撤消进程。①使全部死锁进程都夭折掉；②按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。用户程序的主要处理阶段连续分配方式虚拟存储器的基本特征分页、分段存储管理技术第四章存储器管理存储管理的功能（1）内存分配——为每个进程分配一定的内存空间（2）地址映射——把程序中所用的相对地址转换成内存的物理地址（3）内存保护——检查地址的合法性，防止越界访问（4）内存扩充——解决“求大于供”的问题，采用虚拟存储技术从用户的源程序进入系统到相应程序在机器上运行，所经历的主要处理阶段有，，______________和______________。连接阶段装入阶段运行阶段编译阶段程序的装入和链接编译程序：将用户源代码编译成若干个目标模块；链接程序：将一组目标模块及它们所需要的库函数链接在一起，形成一个完整的装入模块装入程序：将装入模块装入内存。内存空间（或物理空间、绝对空间）由内存一系列存储单元所限定的地址范围逻辑地址空间（或地址空间）由程序中逻辑地址组成的地址范围相对地址（或逻辑地址）用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为相对地址LOAD1,50012345LOAD1,5001234501005007005000510055005700程序A的地址空间程序A的内存空间..................绝对地址（或物理地址）内存中各物理存储单元的地址是从统一的基地址顺序编址，这种地址称为绝对地址程序的装入1．绝对装入方式2．可重定位装入方式3．动态运行时装入方式谢谢收看操作系统第22讲哈尔滨工业大学张英涛操作系统第24讲主讲人：张英涛哈尔滨工业大学远程教育课程程序的装入1．绝对装入方式2．可重定位装入方式3．动态运行时装入方式绝对装入方式逻辑地址与实际地址相同要求程序员熟悉内存的使用情况通常在程序中采用符号地址可重定位装入方式目标模块从0编址，其它地址相对于起始地址计算重定位：装入时对目标程序中指令和数据的修改过程。LOAD1,50012345LOAD1,5001234501005007005000510055005700程序A的地址空间程序A的内存空间..................动态运行时装入方式在程序执行时将相对地址转换成为绝对地址允许程序在内存中移动程序的链接（1）静态链接。（2）装入时动态链接。（3）运行时动态链接。静态链接执行前将目标模块和它们的库函数，连接成一个完整的装配模块。两个问题：对相对地址修改变换外部调用标号模块ACallBReturn模块BCallCReturn模块CReturn0L-10M-10N-1模块CReturn模块BJSR“L+M”Return模块AJSB“L”Return0L-1LL+M-1L+ML+M+N-1运行时动态链接将某些目标模块的链接，推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由操作系统去找到该模块，将它装入内存，并把它链接到调用者模块上。连续分配方式为一个用户程序分配一个连续的内存空间。分为:单一连续分配固定分区分配动态分区分配动态重定位分区分配单一连续分配内存分系统区和用户区，系统区供os使用在内存中仅驻留一道程序，整个用户区为一用户独占。这种分配方式仅能用于单用户、单任务os中.如：MS-DOSCP/M固定分区分配最简单的多道程序的存储管理方式将内存分为几个固定大小的区域，每个区域装入一道作业。划分分区的方法分区大小相等：缺乏灵活性。用于一台计算机控制多个相同对象。分区大小不等。可根据程序大小为它分配适当分区。内存分配将分区按大小进行分配，建立分区使用表，表项包含分区的起始地址、大小、状态。分区号大小(k)起址(k)状态11220已分配232已分配364已分配4128已分配分区号大小(k)起址(k)状态11220已分配23232已分配364已分配4128已分配分区号大小(k)起址(k)状态11220已分配23232已分配36464已分配4128已分配分区号大小(k)起址(k)状态11220已分配23232已分配36464已分配4128128已分配谢谢收看操作系统第24讲哈尔滨工业大学张英涛操作系统第25讲主讲人：张英涛哈尔滨工业大学远程教育课程动态分区分配数据结构分区分配算法分配与回收操作分区分配中的数据结构空闲分区表空闲分区链空闲分区表每个分区占一个表目，包含分区序号、分区始址、分区大小分区