专业电商网站建设哪家好,电商营销的策略与方法,写作网站推荐,在vs做的项目怎么连接到网站处理机调度与死锁 处理机调度的层次 高级调度 高级调度又称为作业调度或长程调度#xff0c;其主要功能是根据某种算法#xff0c;把外存上处于后备队列中的那些作业调入内存#xff0c;也就是说#xff0c;它的调度对象是作业。 1.作业和作业步 作业#xff1a;一个比程…处理机调度与死锁 处理机调度的层次 高级调度 高级调度又称为作业调度或长程调度其主要功能是根据某种算法把外存上处于后备队列中的那些作业调入内存也就是说它的调度对象是作业。 1.作业和作业步 作业一个比程序广泛的概念不仅包含了通常的程序和数据而且还应有一份作业说明书系统根据说明书来对程序的运行进行控制。在批处理系统中是以作业为基本单位从外存调入内存的。 作业步在作业运行期间每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果我们把其中的每一个加工步骤称为一个作业步各作业步之间存在着相互联系往往是把上一个作业步的输出作为下一个作业步的输入。一个典型的作业可以分为三步①编译作业步②连结装配作业步③运行作业步。 作业流若干个作业进入系统后被依次存放在外存上这便形成了输入的作业流在OS控制下逐个作业进行处理便形成了作业流。 2.作业控制块JCB 为了管理和调度作业在多道批处理系统中为每个作业设置而来一个作业控制块其中保存了系统对作业进行管理和调度所需的全部信息。通常应包含作业标识用户名称用户账户作业类型作业状态调度信息资源需求进入系统时间开始处理时间作业完成时间作业退出时间资源使用情况等。JCB类似进程的PCB。 3.作业调度 作业调度的主要功能是根据作业控制块中的信息审查系统能否满足用户作业的资源需求以及按照一定的算法从外存的后备队列中选取某些作业调入内存并为它们创建进程分配必要的资源。然后再将新创建的进程插入到就绪队列准备执行。 在每次执行作业调度时都须做出以下两个决定接纳多少个作业取决于多道程序度接纳哪些作业取决于所采用的调度算法。 低级调度 低级调度也称为进程调度或短程调度它所调用的对象是进程。它是最基本的一种调度。 低级调度的主要功能如下①保存处理机的现场信息②按某种算法选取进程③把处理器分配给进程。 进程调度中的三个基本机制 ①排队器。为了提高进程调度的效率应事先将系统中所有的就绪进程按一定的方式排成一个或多个队列以便调度程序能够最快的找到它。 ②分派器。分派器把由进程调度所选定的进程从就绪队列取出该进程然后进行上下文切换将处理机分配给它。 ③上下文切换机制。当对处理机进行切换时会发生两对上下文切换操作。在第一对上下文切换时操作系统将保存当前进程的上下文而装入分派程序的上下文以便分派程序运行在第二对上下文切换时将移出分派程序而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。 3.进程调度方式 1) 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时可能引起进程调度的因素可归结为这样几个① 正在执行的进程执行完毕 或因发生某事件而不能再继续执行 ② 执行中的进程因提出I/O请求而暂停执行③ 在进程通信或同步过程中执行了某种原语操作如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行因而可能造成难以预料的后果。显然在要求比较严格的实时系统中不宜采用这种调度方式。 2) 抢占方式(Preemptive Mode) 这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程将已分配给该进程的处理机重新分配给另一进程。优点是可以防止一个长进程长时间占用处理机能为大多数进程提供更公平的服务特别是能满足对响应时间有着较严格要求的实时任务的需求。抢占调度方式的原则优先权原则对一些重要的和紧急的作业赋予较高的优先权短作业或进程优先原则当新到达的作业比正在执行的作业明显的短时将暂停当前的长作业的执行将处理机分配给新到达的作业时间片原则各进程按时间片轮转运行当一个时间片用完后便停止该进程的执行而重新进行调度。 中级调度 中级调度又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。 为此应使那些暂时不能运行的进程不再占用宝贵的内存资源而将它们调至外存上去等待把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时由中级调度来决定把外存上的哪些又具备运行条件的就绪进程重新调入内存并修改其状态为就绪状态挂在就绪队列上等待进程调度。 调度队列模型和调度准则 调度队列模型 1. 仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型 选择调度方式和调度算法的若干准则 1. 面向用户的准则 (1) 周转时间短 (2) 响应时间快 (3) 截止时间的保证 (4) 优先权准则。 2. 面向系统的准则系统吞吐量高处理机利用率好各类资源的平衡利用。 调度算法 先来先服务调度算法FCFS 短作业进程优先调度算法SJPF SJPF调度算法虽然能有效地降低作业的平均等待时间提高系统的吞吐量。但也存在缺点①对长作业不利②该算法未考虑作业的紧迫程度因而不能保证紧迫性作业会被及时处理③用户可能会有意或无意的缩短其作业的估计时间致使该算法不一定能真正做到短作业优先。 高优先权优先调度算法 为了照顾紧迫型作业使之在进入系统后便获得优先处理引入了最高优先权优先调度FPF算法。 1. 优先权调度算法的类型 ①非抢占式优先权算法系统一旦把处理机分配给就绪队列中优先权最高的进程后该进程便一直执行下去直至完成 或因发生某事件使该进程放弃处理机时系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中也可用于某些对实时性要求不严的实时系统中。 ②抢占式优先权调度算法系统同样是把处理机分配给优先权最高的进程使之执行。但在其执行期间只要又出现了另一个其优先权更高的进程进程调度程序就立即停止当前进程(原优先权最高的进程)的执行重新将处理机分配给新到的优先权最高的进程。因此在采用这种调度算法时是每当系统中出现一个新的就绪进程i时就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj原进程Pj便继续执行但如果是PiPj, 则立即停止Pj的执行做进程切换使i进程投入执行。显然这种抢占式的优先权调度算法能更好地满足紧迫作业的要求故而常用于要求比较严格的实时系统中 以及对性能要求较高的批处理和分时系统中。 2. 优先权的类型 ①静态优先权是在创建进程时确定的且在进程的整个运行期间保持不变。确定进程优先权的依据有进程类型进程对资源的需求用户要求。 ②动态优先权在创建进程时所赋予的优先权是可以随进程的推进或随其等待时间的增加而改变的以便获得更好的调度性能。 3. 高响应比优先调度算法 优先权的变化规律可描述为 由于等待时间与服务时间之和就是系统对该作业的响应时间故该优先权又相当于响应比RP。据此又可表示为 由上式可以看出 ①如果作业的等待时间相同则要求服务的时间愈短其优先权愈高因而该算法有利于短作业。 ②当要求服务的时间相同时作业的优先权决定于其等待时间等待时间愈长其优先权愈高因而它实现的是先来先服务。 ③ 对于长作业作业的优先级可以随等待时间的增加而提高当其等待时间足够长时其优先级便可升到很高 从而也可获得处理机。 基于时间片的轮转调度算法 在分时系统中为了能及时响应用户的请求必须采用基于时间片的轮转式进程调度算法。 1. 时间片轮转法 在早期的时间片轮转法中系统将所有的就绪进程按先来先服务的原则排成一个队列每次调度时把CPU分配给队首进程并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时由一个计时器发出时钟中断请求调度程序便据此信号来停止该进程的执行并将它送往就绪队列的末尾然后再把处理机分配给就绪队列中新的队首进程同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。 2. 多级反馈队列调度算法 (1) 应设置多个就绪队列并为各个队列赋予不同的优先级。 第一个队列的优先级最高第二个队列次之其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同在优先权愈高的队列中为每个进程所规定的执行时间片就愈小。例如第二个队列的时间片要比第一个队列的时间片长一倍……第i1个队列的时间片要比第i个队列的时间片长一倍。 (2) 当一个新进程进入内存后首先将它放入第一队列的末尾按FCFS原则排队等待调度。当轮到该进程执行时如它能在该时间片内完成便可准备撤离系统如果它在一个时间片结束时尚未完成调度程序便将该进程转入第二队列的末尾再同样地按FCFS原则等待调度执行如果它在第二队列中运行一个时间片后仍未完成再依次将它放入第三队列……如此下去当一个长作业(进程)从第一队列依次降到第n队列后在第n队列中便采取按时间片轮转的方式运行。 (3) 仅当第一队列空闲时调度程序才调度第二队列中的进程运行 仅当第1~(i-1) 队列均空时才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)则此时新进程将抢占正在运行进程的处理机即由调度程序把正在运行的进程放回到第i队列的末尾把处理机分配给新到的高优先权进程。 3. 多级反馈队列调度算法的性能终端型作业用户短批处理作业用户长批处理作业用户。 实时调度 实现实时调度的基本条件 1. 提供必要的信息 ①就绪时间 ②开始截止时间和完成截止时间 ③处理时间 ④资源要求 ⑤优先级 2. 系统处理能力强 在实时系统中通常都有着多个实时任务。若处理机的处理能力不够强则有可能因处理机忙不过来而使某些实时任务不能得到及时处理 从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务它们的处理时间可表示为Ci周期时间表示为Pi则在单处理机情况下必须满足下面的限制条件 解决的方法是提高系统的处理能力其途径有二其一仍是采用单处理机系统 但须增强其处理能力 以显著地减少对每一个任务的处理时间其二是采用多处理机系统。假定系统中的处理机数为N则限制条件应改为N。 3. 采用抢占式调度机制 当一个优先权更高的任务到达时允许将当前任务暂时挂起而令高优先权任务立即投入运行这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统如果能预知任务的开始截止时间则对实时任务的调度可采用非抢占调度机制以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时应使所有的实时任务都比较小并在执行完关键性程序和临界区后能及时地将自己阻塞起来以便释放出处理机 供调度程序去调度那种开始截止时间即将到达的任务。 4. 具有快速切换机制 该机制应具有如下两方面的能力 (1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应要求系统具有快速硬件中断机构还应使禁止中断的时间间隔尽量短 以免耽误时机(其它紧迫任务)。 (2) 快速的任务分派能力。在完成任务调度后便应进行任务切换。为了提高分派程序进行任务切换时的速度 应使系统中的每个运行功能单位适当的小以减少任务切换的时间开销。 实时调度算法的分类 非抢占式调度算法非抢占式轮转调度算法非抢占式优先调度算法。 抢占式调度算法基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法。 常用的集中实时调度算法 1.最早截止时间优先即EDFEarliest Deadline First算法 2.最低松弛度优先即LLFLeast Laxity First算法 产生死锁的原因和必要条件 产生死锁的原因竞争资源进程间推进顺序非法。 产生死锁的必要条件互斥条件请求和保持条件不剥夺条件 环路等待条件 处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁。 预防死锁的方法摒弃“请求和保持”条件摒弃“不剥夺”条件摒弃“环路等待”条件 系统安全状态所谓安全状态是指系统能按某种进程顺序(P1, P2, …Pn)(称〈P1, P2, …, Pn〉序列为安全序列)来为每个进程Pi分配其所需资源直至满足每个进程对资源的最大需求使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列则称系统处于不安全状态。 利用银行家算法避免死锁 1. 银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组其中的每一个元素代表一类可利用的资源数目其初始值是系统中所配置的该类全部可用资源的数目其数值随该类资源的分配和回收而动态地改变。如果AvailablejK则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个n×m的矩阵它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,jK则表示进程i需要Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个n×m的矩阵它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,jK则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个n×m的矩阵用以表示每一个进程尚需的各类资源数。如果Needi,jK则表示进程i还需要Rj类资源K个方能完成其任务。 上述三个矩阵间存在下述关系Need[i, j]Max[i, j] - Allocation[i, j] 2. 银行家算法 设Requesti是进程Pi的请求向量如果RequestijK表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后系统按下述步骤进行检查 (1) 如果Requestij≤Needi,j便转向步骤2否则认为出错因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requestij≤Availablej便转向步骤(3)否则 表示尚无足够资源Pi须等待。 (3) 系统试探着把资源分配给进程Pi并修改下面数据结构中的数值 Availablej∶Availablej-Requestij; Allocationi,j∶Allocationi,jRequestij; Needi,j∶Needi,j-Requestij; (4) 系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程Pi以完成本次分配否则 将本次的试探分配作废恢复原来的资源分配状态让进程Pi等待。 3. 安全性算法 (1) 设置两个向量① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目它含有m个元素在执行安全算法开始时Work∶Available; ② Finish: 它表示系统是否有足够的资源分配给进程使之运行完成。开始时先做Finishi∶false; 当有足够资源分配给进程时 再令Finishi∶true。 (2) 从进程集合中找到一个能满足下述条件的进程 ① Finishifalse; ② Needi,j≤Workj 若找到 执行步骤(3) 否则执行步骤(4)。 (3) 当进程Pi获得资源后可顺利执行直至完成并释放出分配给它的资源故应执行 Workj∶WorkiAllocationi,j; Finishi∶true; go to step 2; (4) 如果所有进程的Finishitrue都满足 则表示系统处于安全状态否则系统处于不安全状态。 死锁定理S为死锁的充分条件是当且仅当S状态的资源分配图示不可完全简化的。 死锁的解除剥夺资源撤销进程。
