第4章调度与死锁1.ppt
《第4章调度与死锁1.ppt》由会员分享,可在线阅读,更多相关《第4章调度与死锁1.ppt(68页珍藏版)》请在三一文库上搜索。
1、第4章 调度与死锁,处理机调度需要解决的问题: 多任务以何种方式共享处理机; 各任务处理机时间的分配和使用处理机时间长短的确定; 处理机的分配策略; 交换控制权的频繁程度和开销之间必须权衡。,4.1 调度的层次与性能评价,一个作业从提交到完成通常要经历多级调度。 在不同操作系统中所采用的调度层次不完全相同。 有的系统中仅采用一级调度,而在另一些系统中则可能采用两级或三级调度。,处理机的三级调度,处理机的三级调度: 作业调度 进程调度 交换调度,1.调度的层次,运行,就绪,阻塞,进程调度,挂起阻塞,挂起就绪,中级调度,创建,退出,作业调度,作业调度,作业调度又称高级调度、宏观调度或长程调度,其主
2、要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业,给它们分配内存、输入/输出设备等必要的资源,并建立相应的进程,以使该作业具有获得竞争处理机的权利。然后将新创建的进程排入就绪队列,准备执行。进程经过若干次状态转换后,作业执行结束。 一般要经历提交、收容、运行和完成等四个阶段。,作业调度,作业调度的运行频率较低,通常为几分钟一次。 在批处理系统中或通用系统批处理部分,新提交的作业先存放在磁盘上,因此需要作业调度,将它们分批装入内存。而在其他类型的操作系统中不需要配置作业调度。,进程调度,进程调度又称低级调度、微观调度或短程调度,其主要任务是按照某种策略和方法从就绪队列中选取一个
3、进程,将处理机分配给它。 进程调度的运行频率很高,一般几十毫秒要运行一次。 是最基本的调度,在一般os中都配置。,中级调度,中级调度又称中程调度或交换调度,其功能是将内存中暂时不用的信息移到外存,以腾出空间给内存中的进程使用,或将需要的信息从外存读入内存。 引入中程调度的目的是提高内存利用率和系统吞吐量。它实际上是存储器管理中的交换功能。 中级调度的运行频率介于两者之间。,2. 调度性能评价,由于操作系统的类型及目标不同,因此选择的调度策略及算法也不同。 调度算法的好坏直接影响系统的性能,影响调度算法的因素很多,常互相矛盾,所以实际采用的调度算法往往依赖系统的设计目标。,系统设计应达到的目标,
4、系统的处理能力高。使系统每天运行尽可能多的作业。 系统资源利用充分。使处理机保持忙碌状态,使设备保持忙碌状态,以达到充分利用系统资源的目的。 算法对所有的作业公平合理。使所有用户感到满意。 同时满足不可能,根据需要兼顾某些目标。,确定调度算法时应考虑因素,设计目标:系统选择的调度算法应与系统的总体设计目标一致。如分时系统应保证用户所能忍受的响应时间 。 资源使用的均衡性:例如I/O和CPU搭配 平衡系统和用户的要求:如任何用户都希望自己的作业一进入系统就立即执行,而系统却要考虑综合效益。因此对用户而言应该保证作业在截止时间内完成,而系统应该缩短作业的平均周转时间。,调度性能的评价准则,有很多评
5、价准则,下面介绍几种主要的评价准则: CPU利用率高。一般在40%-90%之间。CPU利用率CPU有效工作时间/CPU总的运行时间 系统吞吐量大。系统吞吐量表示单位时间内CPU完成作业的数量。 周转时间短。 响应时间快。响应时间是指从用户提交请求到系统首次产生响应所用的时间。这是分时系统和实时系统衡量调度性能的一个重要指标。,周转时间,作业的周转时间是指从作业提交到作业完成之间的时间间隔。 平均周转时间是指多个作业的周转时间的平均值。个作业的平均周转时间: T =(T1T2 Tn)n(Ti为作业的周转时间),带权周转时间,带权周转时间是指作业周转时间与作业实际运行时间的比。 平均带权周转时间是
6、指多个作业的带权周转时间的平均值。个作业的平均带权周转时间: W (W1W2 Wn)/n(Wi为作业的带权周转时间),这些因素一般无法全部满足,因为它们有时相互矛盾。 分时系统: 重点考虑响应时间、公平性 批处理系统: 重点考虑吞吐率、周转时间 实时系统: 要求CPU能及时响应。,4.2 作业调度,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合,包括用户程序、所需的数据及命令等。 计算机系统在完成一个作业的过程中所做的一项相对独立的工作称为一个作业步。 例如,在编制程序过程中通常要进行编辑输入、编译、链接、运行几个作业步。,作业的状态及转换,作业从提交到完成要经历四种状态
7、: 提交状态:用户作业由输入设备向系统外存输入时作业所处的状态。 后备状态:作业输入到外存后,系统为其建立了作业控制块,并把它插入到后备作业队列中等待调度运行。从作业输入开始到放入后备队列这一过程称为收容阶段,也称为作业注册。 运行状态:作业在内存中执行。不一定真正占有处理机 完成状态:作业正常或异常结束,但作业占有的资源还未被系统全部回收。 此时,os将JCB从作业队列中删除,并且收回资源,将运行结果存入输出文件输出。,作业状态转换图,阻塞,就绪,执行,I/O请求,I/O完成,时间片完,提交,作业录入,后备,作业调度,进程调度,运行状态,完成,作业调度,SPOOLING技术,SPOOLING
8、技术 , 也称作假脱机技术,实现原理是在硬盘中开辟出一块称之为输入井和输出井的空间,将多个用户作业随机存储在输入井中,各个用户作业之间相互隔离,互不干扰。当系统要调度用户作业执行时,不是从输入设备上得到该作业,而是直接从输入井中提取。这样就缩短了用户作业提交的时间。同样,当需要把执行作业过程中的数据向慢速的外部I/O设备输出时,不是直接向外部设备输出,而是写入到输出井中,然后再从输出井向外部设备输出。通过外部设备的频繁工作,提高了系统的效率。,2.作业调度,作业调度程序主要完成以下工作 记录进入系统的各个作业情况。 从后备作业中挑选一些作业投入执行。数量有限,一般4或10个。 为被选中的作业做
9、好执行前的准备工作。例如创建进程,分配资源。 在作业运行结束或运行过程中因某种原因需要撤离时,作业调度程序还要完成作业的善后处理工作。例如把作业的一些如运行时间、执行情况等信息输出,回收资源,撤销进程和JCB。,作业控制块,为管理作业,系统设置了作业控制块。系统通过JCB感知作业的存在,JCB是作业存在的唯一标志。 通常作业控制块中包括的主要内容有: 资源要求。 资源使用情况。 作业的控制方式、类型和优先级等。 作业名、作业状态。,资源要求,资源要求是指作业运行需要的资源情况,包括:估计运行时间、最迟完成时间、需要的内存容量、外设类型及数量等。,资源使用情况,资源使用情况包括作业进入系统的时间
10、、开始运行时间、已运行时间、内存地址、外设台号等。,作业控制方式、类型和优先级,作业的控制方式有联机作业控制(直接控制)和脱机作业控制(自动控制)。 从不同角度出发可以对作业进行不同的分类,如终端型和批量型,I/O繁忙型和CPU繁忙型。 作业的优先级是指作业进入系统运行的优先级别,优先级高的作业可以优先进入系统运行。,作业名、作业状态,记录作业的标识信息及作业的当前状态。,4.3 进程调度,进程调度程序主要完成以下功能: 记录系统中所有进程的状态、优先数和资源情况。进程调度程序通过PCB的变化来掌握系统所有的执行情况和状态特征。 选择获得处理机的进程。按照一定的策略选择一个处于就绪状态的进程。
11、 实施处理机的分配及回收。当正在执行的进程要放弃CPU时,进程调度程序要保护CPU现场,将状态由执行改为就绪或阻塞,并插入到相应队列中,同时从就绪队列中挑选一个进程移出,恢复其CPU现场,并且将状态改为执行。,引起进程调度的原因,正在运行进程结束。正常结束或出现错误异常结束。 运行进程因某种原因阻塞,如I/O等 执行某种原语操作,如P操作、阻塞原语等 从系统调用或中断返回时,有进程进入就绪队列且就绪队列为空,或进程优先级高于当前运行进程且为剥夺调度方式 时间片用完,2. 进程调度方式,进程调度有两种方式: 抢占方式 非抢占方式,抢占方式,抢占方式:又称剥夺方式、可剥夺方式。这种调度方式是指允许
12、调度程序根据某种原则去停止正在执行的进程,将已分配给该进程的处理机重新分配给其他进程。 抢占原则有:优先权、时间片。,非抢占方式,非抢占方式:又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后,便让该进程一直执行,直到该进程完成或发生某事件而进入阻塞状态,才把处理机分配给其他进程。 非抢占方式中引起进程调度的因素有:进程结束、因某种原因而阻塞、执行同步原语等。 特点:简单,系统开销小,但无法处理紧急任务。,4.4 调度算法,调度算法是指根据系统资源分配策略所规定的资源分配算法。 本章的算法有些适合作业调度,有些适合进程调度,有些适用于两者。,1先来先服务调度
13、算法,先来先服务算法既可用于作业调度,也可用于进程调度。 在作业调度中:从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源,创建进程,然后放入就绪队列。 进程调度中:从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。,设有4道作业,它们的提交时间及执行时间如下表,若按先来先服务调度算法进行调度,试计算4个作业的平均周转时间和平均带权周转时间。(时间单位:小时,以十进制计算)。,先来先服务调度算法例,作业周转时间及带权周转时间的计算,平均周转时间T=(2.02.83.13.3)/4=2
14、.8 平均带权周转时间W=(12.86.211)/4=5.25,11,6.2,2.8,1,带权周转时间,3.3,3.1,2.8,2,周转 时间,13.8,13.5,13,12,完成 时间,13.5,13,12,10,开始 时间,0.3,0.5,1,2,运行 时间,10.5,10.4,10.2,10,提交 时间,4,3,2,1,作业,先来先服务算法特点,算法简单,易于实现, 但不利于短作业及I/O繁忙型作业。,2.短作业优先调度算法,在作业调度中,从后备队列中选择一个或多个估计运行时间最短的作业,将它们调入内存运行。 在进程调度中,从就绪队列中选择一个估计运行时间最短的进程,为之分配处理机,使之
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 调度 死锁
链接地址:https://www.31doc.com/p-2909659.html