操作系统(Operating.pdf

第6章处理机调度主讲：王攀主讲：王攀操作系统(操作系统(Operating System)2010年年12月月7日星期二日星期二My Email：2?6.1处理机的多级调度处理机的多级调度?6.2作业调度作业调度?6.3进程调度进程调度目 录2010年年12月月7日星期二日星期二My Email：3?1.批处理系统中的处理机调度批处理系统中的处理机调度?处理机调度分两级：作业调度和进程调度。处理机调度分两级：作业调度和进程调度。?作业调度作业调度(又称宏观调度)：对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。(又称宏观调度)：对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。?进程调度进程调度(又称微观调度)：对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。(又称微观调度)：对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。6.1处理机的多级调度2010年年12月月7日星期二日星期二My Email：4?2.多任务操作系统中的处理机调度多任务操作系统中的处理机调度?在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。?进程调度的任务是：进程调度的任务是：当处理机空闲时，以当处理机空闲时，以某种策略选择一个就绪进程去运行，并分某种策略选择一个就绪进程去运行，并分配处理机的时间配处理机的时间。6.1处理机的多级调度(续)2010年年12月月7日星期二日星期二My Email：5?3.多线程操作系统中的处理机调度多线程操作系统中的处理机调度?在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配单位则为线程。在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配单位则为线程。?系统提供线程调度程序，其功能是系统提供线程调度程序，其功能是当处理当处理机空闲时，以某种策略选择一个就绪线程机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间去运行，并分配处理机时间。6.1处理机的多级调度(续)2010年年12月月7日星期二日星期二My Email：6?1.作业的状态作业的状态?作业在整个活动期间一共有四种状态。作业在整个活动期间一共有四种状态。?提交状态提交状态：用户将自己的程序和数据提交给系统，等待输入。：用户将自己的程序和数据提交给系统，等待输入。?后备状态后备状态：作业已存放在：作业已存放在磁盘磁盘上，等待调度。上，等待调度。?执行状态执行状态：作业进入：作业进入主存主存开始运行。开始运行。?完成状态完成状态：作业计算完成开始，退出系统。：作业计算完成开始，退出系统。6.2作业调度2010年年12月月7日星期二日星期二My Email：76.2作业调度(续)就绪就绪完成完成等待等待后备后备提交提交作业调度作业调度作业录入作业调度作业调度作业录入执行执行运行运行2010年年12月月7日星期二日星期二My Email：8?2.作业调度的功能作业调度的功能?确定数据结构确定数据结构?建立作业控制块建立作业控制块jcb（记录了每个作业类型、状态、资源请求及分配情况）。（记录了每个作业类型、状态、资源请求及分配情况）。?确定调度策略与调度算法确定调度策略与调度算法?分配资源分配资源?为选中的作业分配所需要的系统资源。为选中的作业分配所需要的系统资源。?善后处理善后处理?收回该作业所占用全部资源，撤消作业控制块以及与该作业有关的全部进程。收回该作业所占用全部资源，撤消作业控制块以及与该作业有关的全部进程。6.2作业调度(续)2010年年12月月7日星期二日星期二My Email：9?3.作业控制块作业控制块?jcb是一个作业是一个作业存在的标志。存在的标志。?不同系统，不同系统，jcb的内容也有所不的内容也有所不同。同。?右表列出了右表列出了jcb的主要内容。的主要内容。6.2作业调度(续)作业名估计执行时间最迟完成时间要求的主存量要求外设的类型及台数要求文件量和输出量进入系统时间开始执行时间已执行时间主存地址外设台号控制方式类型作业类型优先级状态资源使用情况资源要求作业名估计执行时间最迟完成时间要求的主存量要求外设的类型及台数要求文件量和输出量进入系统时间开始执行时间已执行时间主存地址外设台号控制方式类型作业类型优先级状态资源使用情况资源要求2010年年12月月7日星期二日星期二My Email：10?4.作业调度算法性能的衡量作业调度算法性能的衡量?周转时间（一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间）周转时间（一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间）?定义：定义：ti=tcitsiti作业作业i的周转时间的周转时间tsi作业作业i的提交时间，的提交时间，tci作业作业i的完成时间的完成时间?意义：说明作业意义：说明作业i在系统中停留时间的长短。在系统中停留时间的长短。?平均周转时间平均周转时间：t=。niit16.2作业调度(续)n12010年年12月月7日星期二日星期二My Email：11?带权周转时间 带权周转时间?定义：一个作业的周转时间与其运行时间的比值。定义：一个作业的周转时间与其运行时间的比值。wi=?意义：说明作业意义：说明作业i在系统中相对等待时间。在系统中相对等待时间。?平均周转时间：平均周转时间：w=6.2作业调度(续)riittniiwn112010年年12月月7日星期二日星期二My Email：12?5.作业调度算法作业调度算法?先来先服务调度 先来先服务调度?策略：按作业来到先后次序进行调度。策略：按作业来到先后次序进行调度。?特点：简单、易实现。特点：简单、易实现。6.2作业调度(续)作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.208.0010.002.0010.0010.502.0010.5010.601.6010.6010.801.30t=1.72514166.5w=6.8752010年年12月月7日星期二日星期二My Email：13?短作业优先调度 短作业优先调度?策略：按作业请求运行的时间长短进行调度。策略：按作业请求运行的时间长短进行调度。?特点：易实现，特点：易实现，系统吞吐量最高系统吞吐量最高；只照顾短作业，而没有考虑长作业的利益。；只照顾短作业，而没有考虑长作业的利益。6.2作业调度(续)作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.208.0010.002.0010.3010.802.3010.0010.101.1010.1010.300.80t=1.5514.6114w=5.152010年年12月月7日星期二日星期二My Email：14?响应比高者优先调度 响应比高者优先调度?策略：计算后备作业表中每个作业的响应比（响应时间策略：计算后备作业表中每个作业的响应比（响应时间/执行时间），然后投入响应比最高的作业投入运行。执行时间），然后投入响应比最高的作业投入运行。?特点：对前两种算法一种较好的折衷。特点：对前两种算法一种较好的折衷。6.2作业调度(续)作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间作业编号提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.208.0010.002.0010.1010.602.1010.0010.101.1010.6010.801.30t=1.62514.2116.5w=5.6752010年年12月月7日星期二日星期二My Email：15?1.调度调度/分派结构分派结构?进程调度功能可细分为进程调度功能可细分为调度调度和和分派分派两部分。两部分。?调度意味着依照完全确定的策略将一批进程进行排序。调度意味着依照完全确定的策略将一批进程进行排序。?分派是从就绪队列中移出一个进程并给它提供使用处理机的权利。分派是从就绪队列中移出一个进程并给它提供使用处理机的权利。6.3进程调度2010年年12月月7日星期二日星期二My Email：16?调度调度/分派结构图分派结构图6.3进程调度(续)ready_qschedulersusp wakeup receive pcb6pcb4pcb3pcb2pcb1dispatcherCPU2010年年12月月7日星期二日星期二My Email：17?2.进程调度的功能进程调度的功能?记录进程的有关情况和状态特征。记录进程的有关情况和状态特征。?决定调度策略 决定调度策略?优先调度原则优先调度原则进程就绪队列按进程优先级高低排序进程就绪队列按进程优先级高低排序?先来先服务原则先来先服务原则进程就绪队列按进程来到的先后次序排序进程就绪队列按进程来到的先后次序排序?实施处理机的分配和回收。实施处理机的分配和回收。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：18?3.进程调度方式进程调度方式?什么是调度方式？当一进程正在处理机上执行时，若有某个更为什么是调度方式？当一进程正在处理机上执行时，若有某个更为“重要而紧迫重要而紧迫”的进程需要进行运行，系统如何分配处理机。的进程需要进行运行，系统如何分配处理机。?非剥夺方式非剥夺方式：一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入：一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成完成”或或“阻塞阻塞”状态时，才把处理机分配给状态时，才把处理机分配给“重要而紧迫重要而紧迫”的进程的进程?剥夺方式剥夺方式：当：当“重要而紧迫重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：19?4.进程优先数调度算法进程优先数调度算法?预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权（优先数和一定的优先级相对应）的就绪进程。预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权（优先数和一定的优先级相对应）的就绪进程。?静态优先数静态优先数：在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。其可按以下方法确定：在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。其可按以下方法确定：?a.根据进程所需使用的资源来计算根据进程所需使用的资源来计算?b.基于程序运行时间的估计基于程序运行时间的估计?c.基于进程的类型（系统基于进程的类型（系统/用户进程，联机用户进程，联机/脱机进程）。脱机进程）。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：20?动态优先数动态优先数：进程优先数在进程运行期间可以改变。其可按以下方法确定：进程优先数在进程运行期间可以改变。其可按以下方法确定：?a.进程使用进程使用CPU时间超过一定数值时，降低优先数；时间超过一定数值时，降低优先数；?b.进程等待时间超过一定数值时，提高优先数；进程等待时间超过一定数值时，提高优先数；?c.当等待某一外设的进程较多时，可以提高使用该设备的进程的优先数。当等待某一外设的进程较多时，可以提高使用该设备的进程的优先数。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：21?5.循环轮转调度算法循环轮转调度算法?当当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。?简单循环轮转调度简单循环轮转调度：就绪队列中的所有进程以等速度向前进展。其中时间片：就绪队列中的所有进程以等速度向前进展。其中时间片q=t/nmax（t为响应时间，为响应时间，nmax为进入系统的最大进程数目）为进入系统的最大进程数目）?循环轮转调度算法的发展：循环轮转调度算法的发展：可变时间片轮转调度可变时间片轮转调度、多就绪队列轮转法多就绪队列轮转法6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：22?6.调度用的进程调度变迁图调度用的进程调度变迁图?队列结构 队列结构?I/O等待队列等待队列：一个进程如果请求：一个进程如果请求I/O，进入，进入I/O等待队列。等待队列。?低优先就绪队列低优先就绪队列：一个进程如果在运行中超过了它的时间量，进入低优先就绪队列。：一个进程如果在运行中超过了它的时间量，进入低优先就绪队列。?高优先就绪队列高优先就绪队列：当进程从等待状态变为就绪状态时，进入高优先就绪队列。：当进程从等待状态变为就绪状态时，进入高优先就绪队列。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：23?调度算法（优先调度与时间片调度结合）调度算法（优先调度与时间片调度结合）?a.当当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms；?b.若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。?调度效果 调度效果?优先照顾了优先照顾了I/O量大的进程；量大的进程；?适当照顾了计算量大的进程。适当照顾了计算量大的进程。6.3进程调度(续)2010年年12月月7日星期二日星期二My Email：24?较简单的进程状态变迁图较简单的进程状态变迁图6.3进程调度(续)运行运行因因I/O而等待而等待高优先就绪高优先就绪低优先就绪低优先就绪超时间片其次选择超时间片其次选择500ms首先选择首先选择100msI/O完成请求完成请求I/OThanks!