第5课进程调度算法

操作系统,第5课进程的调度与管理,内容回顾：程序的执行,程序的顺序执行：程序的并发执行引入并发的目的,内容回顾：进程的定义,进程是具有独立功能的程序关于某个数据集合上的一次运行过程，是系统进行资源分配和运行调度的独立单位,内容回顾：进程的定义,进程是具有独立功能的程序关于某个数据集合上的一次运行过程，是系统进行资源分配和运行调度的独立单位,内容回顾：程序与进程之间的区别,进程是由程序和数据两部分组成的程序是静态的，进程是动态的进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的进程更能真实地描述并发，而程序不能通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程具有创建其他进程的功能，而程序没有,内容回顾：进程的特征,动态性进程是对应程序的执行进程是动态产生，动态消亡的，有生命周期并发性多个进程同时运行独立性进程是资源分配的一个独立单位制约性指进程在执行过程中可能与其它进程产生直接或间接的关系,内容回顾：进程三状态进程模型,进程的三种基本状态：运行态就绪态阻塞（等待）态进程在生命消亡前处于且仅处于三种基本状态之一,运行态（Running）：进程占有CPU，并在CPU上运行就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）阻塞态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）,运行,就绪,阻塞,进程的状态及其转换,内容回顾,系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,内容回顾,系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,今日目标,进程调度算法先来先服务调度算法时间片轮转调度算法优先数调度算法多级队列调度算法,进程调度程序和进程调度算法,进程调度程序：-操作系统中决定把cpu分配给哪个进程使用的程序-从就绪队列中选择一个进程并把cpu分配给它使用进程调度算法：-进程调度程序采用的调度方法,CPU调度的时机,当一个进程终止时当一个进程从运行状态切换到阻塞状态当一个进程从运行状态切换到就绪状态当一个进程从阻塞状态切换到就绪状态,两种占用CPU的方式不可抢占式：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去可抢占式：当有比正在运行的进程优先级更高的进程就绪或时间片用完时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用,进程调度算法,先来先服务调度算法时间片轮转调度算法优先数调度算法多级队列调度算法,先来先服务调度算法,基本思想：调度时以到达就绪队列的先后次序选择占用处理机的进程。进程一旦占有处理机，就一直用下去，直至结束或因等待某事件而让出处理机。,先来先服务调度算法优缺点,优点:实现简单缺点:使短进程等待长进程，重要或紧迫的进程等待不那么重要或紧迫的进程,时间片轮转调度算法,基本思想：调度时为进程分配一个称为“时间片”的时间段，在使用完一个时间片后，即使进程没运行完，也要释放处理机，让给另一个进程使用，自己则排到就绪队列末尾，等待下一次调度。,时间片长度的确定,过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。,优先数调度算法,基本思想：为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程有优先获得处理机的权利；如果几个进程的优先数相同，则对它们实行先来先服务的调度。,优先数调度算法：如何确定进程的优先数,根据进程的类型系统和用户进程根据进程执行任务的重要性根据进程程序的性质根据对资源的要求根据用户的请求,两种优先权算法,非抢占式：调度程序将CPU分配给优先权最高的进程后，等该执行进程执行完后再重新调度抢占式：调度程序将CPU分配给优先权最高的进程后，该进程执行过程中，如有另一高优先权进程出现，则停止该进程的执行，将CPU调度给新进程。,设置优先数的方法,静态优先数法：在进程创建时指定优先数，在进程运行时优先数不变存在的问题：饥饿动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,多级队列调度算法,基本思想：系统中维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。级1就绪队列里进程的调度级别最高，可获得的时间片最短；级n就绪队列里进程的调度级别最低，但可以获得的时间片最长。创建新进程时，它的PCB将先进入级1就绪队列的末尾。,多级队列调度算法具体方法,*首先系统中设置多个就绪队列*每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大*各个队列按照先进先出调度算法*一个新进程就绪后进入第一级队列*进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列*当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾*当第一级队列空时，就去调度第二级队列，如此类推*当时间片到后，进程放弃CPU，回到下一级队列,多级队列调度算法,调度,就绪队列,到达,完成,CPU,阻塞、就绪,时间片到,调度,完成,CPU,阻塞、就绪,调度,完成,CPU,阻塞、就绪,时间片到,时间片到,级1(先来先服务),级2(先来先服务),级n(先来先服务),进程调度程序功能,纪录系统中所有进程的情况确定cpu调度算法完成cpu的分配完成cpu的回收,进程管理原语,原语的定义创建进程原语撤销进程原语阻塞进程原语唤醒进程原语,原语定义操作系统提供若干基本操作，以便能创建、撤消、阻塞和唤醒进程。为了保证执行的正确，要求它们以一个整体出现，不可分割。即一旦启动了对应的程序，就要保证做完，中间不能插入其它程序的执行序列。具有这种特性的程序被称为“原语”。为保证原语操作的不可分割性，通常总是利用屏蔽中断的方法。,进程管理原语,创建进程原语功能：为新建进程申请进程控制块PCB，将创建者提供的信息填入PCB，将新建进程设置为就绪状态，按照调度算法把PCB排入就绪队列中。撤销进程原语功能：收回该进程占用的资源，将该进程的PCB从所在队列里摘下，把PCB所占用的存储区归还给系统。阻塞进程原语功能：将被阻