中国十大设计素材网站,wordpress发布失败,门户网站开发视频教学,当今做那些网站致富3.1 处理机调度概述
3.1.1 处理机调度概述
高级调度 (High level Scheduling)决定把外存上哪些作业调入内存、创建进程、分配资源。高级调度又称作业调度、长程调度或宏观调度。只在批处理系统中有高级调度。
中级调度 (Middle level Scheduling)完成进程的部分或全部在内、…3.1 处理机调度概述
3.1.1 处理机调度概述
高级调度 (High level Scheduling)决定把外存上哪些作业调入内存、创建进程、分配资源。高级调度又称作业调度、长程调度或宏观调度。只在批处理系统中有高级调度。
中级调度 (Middle level Scheduling)完成进程的部分或全部在内、外存间的交换。中级调度又称中程调度。 低级调度 (Low level Scheduling)决定就绪队列中哪个进程应获得处理机。低级调度又称进程调度、短程调度或微观调度。
3.1.2 作业调度及算法
作业基本概念 作业是用户提交给系统的一项相对独立的工作。比程序更为广泛批处理系统中以作业为单位从外存调入内存。 作业步作业进行的步骤。 作业控制块JCB作业在系统中存在的唯一标识。 作业运行的三个阶段收容、运行、完成。 作业的三种状态后备、运行、完成。
作业调度的主要决策 接纳多少个作业 取决于系统多道程序度 多道程序度的确定根据计算机的系统规模、运行速度、作业大小以及能否获得较好的系统性能等
接纳哪些作业 取决于系统的调度算法 先来先服务调度算法 短作业优先调度算法 优先级调度算法
3.1.3 进程调度及算法
进程调度的任务 保存处理机的现场信息 按某种调度算法选取进程 把处理器分配给进程由分派程序把处理器分配给该进程设置选中进程的处理机现场信息交处理机控制权给进程运行
进程调度的机制 进程调度方式 非抢占式(Non-preemptive Mode)不允许某进程抢占已经分配出去的处理机。 抢占方式(Preemptive Mode)允许调度程序根据某种原则暂停正在执行进程将处理机重新分配给另一进程。优先权原则、短进程优先原则、时间片原则
3.1.4 处理机调度算法的目标
共同的目标 资源利用率 Utilization 高 公平性(Fairness) 资源的平衡利用(Balance) 策略的强制执行
批处理系统的目标 周转时间(Turnaround time)短每个用户都希望自己的周转时间短系统希望 平均周转时间短 假定某一作业提交系统的时间为Si它被选中执行运行结束时的时间为Ei 。 周转时间为Ti Ei – Si 则作业平均周转时间为 平均带权周转时间为 CPU利用率 CPU Utilization 高尽量选择计算量大的作业 系统吞吐量Throughput高吞吐量指在单位时间内系统所完成的作业数。
分时系统的目标 响应时间(Response time)快 响应时间是从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间。 均衡性系统响应时间的快慢应与用户请求服务的复杂性相适应
实时系统的目标 截止时间(Deadline)的保证 可预测性(Predictability)准则
3.2 调度算法
3.2.1 先来先服务调度算法FCFS: First Come First Served
调度思想完成选择一个或多个最先进入后备队列的作业将它们调入内存为它们分配资源、创建进程并放入就绪队列。 FCFS的特点 有利于长作业不利于短作业。 有利于CPU密集/繁忙型的作业不利于I/O密集/繁忙型的作业。 CPU密集型作业(CPU-bound process)作业大部分时间用于计算 I/O密集型作业 (I/O bound process )作业大部分时间用于等待I/O 随着计算机运行速度加快作业越来越趋向于I/O密集型进程
3.2.2 短作业优先调度算法SJF: Shortest Job First
调度思想完成在后备队列选择一个或多个估计运行时间最短的作业将它们调入内存为它们分配资源、创建进程并放入就绪队列。 SJF的特点 优点能有效地降低作业的平均等待时间提高系统吞吐量。 缺点对长作业不利未考虑作业紧迫程度作业的估计运行时间不准确。
3.2.3 优先级调度算法PSA: Priority-scheduling algorithm
调度思想完成在后备队列选择一个或多个优先级最高的作业将它们调入内存为它们分配资源、创建进程并放入就绪队列。 静态优先级 动态优先级随着时间延长而增加 3.2.4 高响应比优先调度算法HRRN: Highest Response Ratio Next 如作业等待时间相同则处理时间越短响应比越高有利于短作业。 对于长作业随等待时间增加响应比增高最后同样可获得处理机。 如处理时间相同等待时间越长响应比越高实现的是先来先服务。 3.2.5 基于时间片的轮转调度算法RR—Round Robin
RR的基本原理 把CPU划分成若干时间片 按顺序赋给FCFS就绪队列中的每一个进程 时间片用完时时钟中断请求即使进程未执行完毕系统也剥夺该进程的CPU将该进程排在就绪队列末尾同时系统选择队首进程运行 RR的进程切换时机 时间片内进程已运行完成立即激活进程调度程序 时间片用完计时器中断处理程序被激活送当前进程到就绪队列末尾
时间片大小的确定 时间片大小对系统性能影响很大 时间片很小有利于短进程但进程调度和切换频繁增加系统开销 时间片过大退化为FCFS无法满足短作业和交互式进程的需求 时间片可选取略大于一次典型交互的所需时间使大多数交互式进程能在一个时间片内完成从而获得很小的响应时间 3.2.6 多级反馈队列调度算法multileveled feedback queue
将就绪队列分为N级每个就绪队列分配给不同的时间片队列级别越高时间片越短级别越低时间片越长。
进程第一次就绪时进入第一级队列队尾按FCFS 原则等待调度。
系统从第一级队列调度当第一级为空时系统转向第二级队列.....
当前进程用完一个时间片如运行完成则退出系统否则必须放弃CPU并插入下一级队列队尾如果CPU正在处理第i级队列时有新进程加入第一级队列或者有新唤醒的进程比当前进程的队列级别高则新进程抢占当前进程的CPU而原来的当前进程插入第i级队列队尾。 特点 终端型作业用户交互型作业第一级队列的时间片可完成 短批处理作业用户最多轮两次就可完成周转时间较短 长批处理作业用户不必担心长期得不到调度比简单轮转性能好
3.3 实时调度
实时系统例子实验控制、过程控制设备、机器人、空中交通管制、远程通信、军事指挥与控制系统下一代系统还包括自动驾驶汽车、具有弹性关节的机器人控制器、智能化生产中的系统查找、空间站和海底勘探。
每种实时系统都有若干个实时进程来反应或控制某个外部事件它们往往带有某种程度的紧迫性需要实时系统的调度有特殊处理所以引入实时调度。
3.3.1 实现实时调度的基本条件
提供必要的信息开始/完成截止时间、就绪时间、处理时间、资源要求、优先级 系统处理能力强 采用抢占式调度机制硬实时系统 具有快速切换机制对外部中断的快速响应能力——要求快速硬件中断机构、允许中断的间隔短快速的任务分派能力——系统中的每个运行功能单位适当的小
3.3.2 实时调度算法的分类
根据实时任务性质不同可分为硬实时调度和软实时调度 根据调度方式不同可分非抢占调度和抢占调度算法 根据调度时间的不同分成静态和动态调度算法 在多处理机情况下可分为集中式和分布式调度算法。
非抢占式调度算法轮转调度算法、优先调度算法 响应时间在几秒到数十秒之间。 应用于不太严格的实时控制系统比如工业生产的群控系统。
抢占式调度算法基于时钟中断的抢占式优先权调度算法、立即抢占的优先权调度算法。 当实时任务到达放在就绪队列队首等待当前任务的自我终止或运行完成。 响应时间为数百毫秒适用于较为严格的实时控制系统。
基于时钟中断的抢占式优先权调度算法 当优先级高于当前任务的实时任务到达则等到下一个时钟中断抢占当前任务的处理机。 响应时间为几到数十毫秒之间应用于较严格的实时系统。
立即抢占的优先权调度算法 一旦出现请求中断的紧急任务只要当前任务未在临界区立即抢占它的CPU 响应时间为100微秒到几毫秒之间 系统必须具有快速响应外部中断能力
3.3.3 最早截止时间优先算法EDF
根据任务的开始截止时间来确定任务的优先级可用于抢占式调度和非抢占式调度。 3.3.4 最低松弛度优先算法 LLF
根据任务的紧急或松弛程度确定任务的优先级松弛度必须完成的时间-还需运行的时间-当前时间松弛度是动态变化的主要用于可抢占式调度方式。 3.4 死锁的概念
一组进程中每个进程都无限等待被该组进程中另一进程所占有的资源而处于的一种僵持局面若无外力作用它们都无法向前推进这种现象称为进程死锁(Deadlock)这组进程就称为死锁进程。
3.4.1 死锁产生的原因
竞争资源引起进程死锁 1可剥夺和非可剥夺资源 可剥夺资源进程在获得这个资源后可以在被其它进程或系统剥夺 非可剥夺资源资源被系统分配给某个进程后就不能强行收回只能进程自己释放 2竞争不可抢占资源引起死锁 3竞争临时性资源可消耗资源引起死锁 进程推进顺序不当引起死锁
3.4.2 死锁产生的必要条件
一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件那么该组进程是死锁的。 互斥条件Mutual exclusion涉及的资源是非共享的 不剥夺条件no preemption不能剥夺进程拥有资源 请求保持条件hold and wait进程在等待一新资源时继续占有已分配的资源 环路条件circular wait存在一种进程的循环链链中的每一个进程已获得的资源同时被链中的下一个进程所请求存在一种进程的循环链链中的每一个进程已获得的资源同时被链中的下一个进程所请求。
3.4.3 预防死锁deadlock prevention
通过设置某些限制条件去破坏死锁四个必要条件中的 一个或多个来防止死锁。 较易实现广泛使用。 由于所施加的限制往往太严格可能导致系统资源利用率和系统吞吐量的降低。
3.4.4 避免死锁deadlock avoidance
不事先采取限制去破坏产生死锁的条件而是在资源的动态分配过程中用某种方法去防止系统进入不安全状态从而避免死锁的发生。 事先只需要较弱的限制条件可获得较高的资源利用率和系统吞吐量。
3.4.5 检测死锁deadlock detection
事先并不采取任何限制也不检查系统是否进入不安全区允许死锁发生但可通过检测机构及时检测出死锁的发生并精确确定与死锁有关的进程和资源然后采取适当措施将系统中已发生的死锁清除掉。
3.4.6 解除死锁deadlock recovery
与检测死锁相配套用于将进程从死锁状态解脱出来。 常用的方法是撤消或挂起一些进程以回收一些资源再将它们分配给处于阻塞状态的进程使 之转为就绪状态。 实现难度大但可获得较好的资源利用率和系统吞吐量。
3.4.7 资源分配图法
二元组GN,E N结点集分为PR两部分 P{p1,p2,…,pn}进程结点 R{r1,r2,…,rm}资源结点 E边的集合其元素为有序二元组pi,rj 或rj,pi 系统由若干类资源构成一类资源称为一个资源类每个资源类包含若干个同种资源称为资源实例。
结点的表示法 资源类资源的不同类型用方框表示Pi 资源实例存在于每个资源类中用方框中的黑圆点圈表示 进程用圆圈中加进程名表示边集中各边的含义 分配边资源实例→进程 的一条有向边 rj,pi 申请边进程→资源类 的一条有向边 pi,rj
3.5 死锁的预防
破坏产生死锁的四个必要条件之一. 原理设计不同的资源分配算法来保证不发生死锁。
3.5.1 破坏互斥条件
如果资源不需要互斥访问就可以破坏互斥条件。 对于某些硬件资源可以采用特殊技术实现允许同时访问 对于软件资源无法实现。
3.5.2 破坏请求和保持条件
第一种协议在执行时不再提出资源请求系统要求所有进程要一次性地申请在整个运行过程中所需 的全部资源。若系统有足够资源则完全分配。 缺点 用户作业必须等待直到所有资源满足才能运行。 一个作业运行期间对某些设备的使用时间很短甚至不会用到。如当用户作业出错时才需要打印机输出错误信息但采用静态分配法必须把打印机分配给该作业并长期占用。采用该方法对系统来说是非常浪费的。
第二种协议请求不保持所有资源 获得初期所需资源以后就开始运行在运行过程中逐步释放分配给自己的并且已经用毕的全部资源然后再请求新的所需资源。
3.5.3 破坏不可抢占条件
一个已拥有资源的进程若它再提出新资源要求而不能立即得到满足时它必须释放已经拥有的所有资源待以后需要时再重新申请。
实现复杂且要付出很大的代价以前工作的失效执行的推迟。
3.5.4 破坏环路条件
系统将所有资源按类型进行线性排序并赋予不同的序号所有进程对资源的请求必须严格按照资源序号递增的次序提出。
例如系统中有下列设备输入机1打印机2穿孔机3磁带机4磁盘5。有一进程要先后使用输入机、磁盘、打印机则它申请设备时要按输入机、打印机、磁盘的顺序申请。
优点同前两法相比其资源利用率和系统吞吐量有较明显的改善。 缺点进程实际需要资源的顺序不一定与资源的编号一致因此仍会造成资源浪费资源的序号必须相对稳定从而限制了新设备的增加。
3.6 避免死锁
3.6.1 系统的安全状态
在系统运行过程中对进程提出的每一个系统能够满足的资源申请进行动态检查安全性检 查根据检查结果决定是否分配资源若分配后系统可能发生死锁则不予分配否则予以分配。
如果系统能按某种顺序为每个进程依次分配其所需的资源直至所有进程都能运行完成称此时 系统处于安全状态。 这种进程的顺序如P4,P1,…,Pn, 称为安全序列。 若不存在这样一个安全序列称此时系统处于不安全状态。
注意不安全状态≠死锁 处于不安全状态的系统不一定会发生死锁处于安全状态的系统一定不会发生死锁。 系统处于安全与不安全状态都是静态进行的评价。
安全状态举例
由安全状态向不安全状态的转换
3.7.2 利用银行家算法避免死锁
银行家算法中的数据结构 可利用资源向量Available是一个含有m个元素的数组其中每个元素代表一类资源的可利用的数目。 最大需求矩阵Maxn×m矩阵n为当前系统进程的数目m为系统资源种类数。Max[i,j]为第i个进程对j类资源的最大需求。 分配矩阵Allocation n×m矩阵表示每个进程已分配的每类资源数。 需求矩阵Needn×m矩阵表示每个进程还需要各类资源数。 Need[i,j] Max[i,j]- Allocation[i,j]
银行家算法 当Pi发出资源请求分配一个Request向量。Request_i是进程Pi的请求向量。如Request_i[j]K表示进程i需要K个R_j类型的资源。然后系统按下述流程进行执行。 安全性算法 增加两个向量Work和Finish Work表示系统可提供给进程继续运行所需的各类资源数目即在试着分配过程中系统的可用资源数。初始值 Work∶Available可用资源向量; Finish表示系统是否有足够的资源分配给进程i使之运行完成。初始值 Finish[i]:false布尔型当有足够资源分配给进程时 Finish[i]:true。 3.8 死锁的检测和解除
3.8.1 死锁检测
允许死锁发生操作系统不断监视系统进展情况判断死锁是否发生 一旦死锁发生则采取专门的措施解除死锁并以最小的代价恢复操作系统运行
检测时机 定时检测 当进程阻塞时检测死锁其缺点是系统的开销大 系统资源利用率下降时检测死锁
检测方法资源分配图法
死锁定理如果资源分配图中没有环路则系统中没有死锁如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例则环路是死锁存在的充分必要条件。
资源分配图化简 1.找一个非阻塞非独立的进程结点去掉分配和请求边将其变为孤立结点 2.再把相应的资源分配给一个等待该资源的进程即将某进程的申请边变为分配边 3.重复以上步骤若所有进程都可成为孤立结点称该图是可完全简化的否则称该图是不可完全简化的。 死锁状态的充分条件是资源分配图是不可完全简化的。
3.8.2 死锁的解除
抢占资源 终止或者撤销进程终止所有进程、逐个终止进程
重要的是以最小的代价解除死锁恢复系统运行。方法如下 撤消所有的死锁进程 连续撤消死锁进程直至不再存在死锁 连续剥夺资源直到不再存在死锁 把每个死锁进程备份到前面定义的某个检查点并重新启动所有进程
