第5课进程调度算法

操作系统第5课进程的调度与管理内容回顾：程序的执行程序的顺序执行：程序的并发执行引入并发的目的内容回顾：进程的定义进程是具有独立功能的程序关于某个数据集合上的一次运行过程，是系统进行资源分配和运行调度的独立单位内容回顾：进程的定义进程是具有独立功能的程序关于某个数据集合上的一次运行过程，是系统进行资源分配和运行调度的独立单位内容回顾：程序与进程之间的区别进程是由程序和数据两部分组成的程序是静态的，进程是动态的进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的进程更能真实地描述并发，而程序不能通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程具有创建其他进程的功能，而程序没有内容回顾：进程的特征动态性进程是对应程序的执行进程是动态产生，动态消亡的，有生命周期并发性多个进程同时运行独立性进程是资源分配的一个独立单位制约性指进程在执行过程中可能与其它进程产生直接或间接的关系内容回顾：进程三状态进程模型进程的三种基本状态：运行态就绪态阻塞（等待）态进程在生命消亡前处于且仅处于三种基本状态之一运行态（Running）：进程占有CPU，并在CPU上运行就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）阻塞态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）运行就绪阻塞进程的状态及其转换内容回顾系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的内容回顾系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的今日目标进程调度算法先来先服务调度算法时间片轮转调度算法优先数调度算法多级队列调度算法进程调度程序和进程调度算法进程调度程序：---操作系统中决定把cpu分配给哪个进程使用的程序---从就绪队列中选择一个进程并把cpu分配给它使用进程调度算法：---进程调度程序采用的调度方法CPU调度的时机当一个进程终止时当一个进程从运行状态切换到阻塞状态当一个进程从运行状态切换到就绪状态当一个进程从阻塞状态切换到就绪状态两种占用CPU的方式不可抢占式：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去可抢占式：当有比正在运行的进程优先级更高的进程就绪或时间片用完时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用进程调度算法先来先服务调度算法时间片轮转调度算法优先数调度算法多级队列调度算法先来先服务调度算法基本思想：调度时以到达就绪队列的先后次序选择占用处理机的进程。进程一旦占有处理机，就一直用下去，直至结束或因等待某事件而让出处理机。ABCD调度就绪队列到达阻塞队列完成I/O完成阻塞CPUI/O先来先服务调度算法优缺点优点:实现简单缺点:使短进程等待长进程，重要或紧迫的进程等待不那么重要或紧迫的进程时间片轮转调度算法基本思想：调度时为进程分配一个称为“时间片”的时间段，在使用完一个时间片后，即使进程没运行完，也要释放处理机，让给另一个进程使用，自己则排到就绪队列末尾，等待下一次调度。AABCD调度就绪队列到达阻塞队列完成I/O完成阻塞CPUI/O时间片到时间片长度的确定过长－退化为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所占用的存储区归还给系统。阻塞进程原语功能：将被阻塞进程的现场信息保存到PCB中，状态改为阻塞；将其PCB排到相应的阻塞队列中。若被阻塞的是自己，调用了该原语后，就重新分配处理机。唤醒进程原语功能：在等待的事件发生后，由唤醒进程原语把等待进程从相应的阻塞队列里解放出来，进入就绪队列，重新参与调度。课堂练习P38填空、选择