操作低掣聪_处理机调度与死锁.doc

处理机调度与死锁 3.1 处理机调度的层次 对于批量作业而言，通常要经历的处理机调度包括： 作业调度(高级调度或长程调度)，进程调度(低级调度或短程调度)； 对于终端型作业，通常只需通过进程调度即可获得处理机； 完善的OS中，为提高内存的利用率，设置了中级调度(中程调度) 。 3.1.1 高级调度(High Level Scheduling) 其主要功能是： 根据某种调度算法把外存上处于后备队列中的作业调入内存，调度对象是作业。 作业和作业步 作业---程序、数据、作业说明书；外存-内存； 作业步---作业加工步骤；编译-连结-运行 作业流---若干作业依次放在外存上，等待处理； 作业控制块JCB(相当于进程中PCB): 包含管理和调度作业的全部信息，主要有：作业标识,用户名称，用户账户，作业类型，作业状态，调度信息，资源需求，进入系统时间，开始处理时间，作业完成时间，退出时间，资源使用状况。 作业进入系统，运行时，完成时，都要用到JCB。 作业调度 作业调度：根据JCB，审查系统是否满足资源需求，并按照算法从外存的后备队列中选取某些作业调入内存，为其建立进程，分配资源，最后将进程插入就绪队列。 在每次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业 (多道程序度)：即内存中允许多少个程序同时运行，太多影响服务质量，太少资源利用率系统吞吐量低。应根据系统的规模和速度折中。 2) 接纳哪些作业：取决于调度算法。最简单的“先来先服务”，较常用的“短作业优先”和“基于优先级”的调度，比较好的“响应比高者优先”。 3.1.2 低级调度(Low Level Scheduling) 1.功能---保存CPU现场信息；按算法选进程；分配CPU； 2.基本机制--- 1)排队器：就绪队列排队； 2)分派器 ：取出进程,分配处理机； 3)上下文切换：两对切换分别是：当前进程—分派程序，分派程序—新选进程； 思考：如何优化上下文切换机制？ 采用硬件（两组寄存器），存储上下文，这样上下文切换只需改变指针。 3.调度方式---非抢占方式和抢占方式： 1) 非抢占方式(Non-preemptive Mode)--占有CPU,一直运行 采用这种方式，可能引起进程调度的几个因素： ① 进程执行完毕或因某事件不能继续； ② 提出I/O请求而暂停； ③ 在进程通信或同步过程中执行了P (wait)、Block、Wakeup等某种原语操作。 优点：实现简单、系统开销小，适于批处理系统。 缺点：难以满足实时任务立即执行的要求。 2) 抢占方式(Preemptive Mode) 抢占的原则有：优先权原则、 短作业(进程)优先原则、时间片原则。 优点：对大多数进程公平、适于实时系统。 缺点：系统开销大 3.1.3 中级调度(Intermediate-Level Scheduling) 又称中程调度(Medium-Term Scheduling)。 引入目的：提高内存利用率和系统吞吐量。 实质是存储器管理中的对换功能(外存-内存):暂时不能运行的进程调至外存上去等待(静止就绪或静止阻塞)，具备条件且内存空闲时，由中级调度决定把哪些进程重新调入内存。 三种层次调度的比较--- 低级调度 高级调度 中级调度 运行频率 10-100ms 几分钟 中等 3.2 调度队列模型和调度准则 3.2.2 选择调度方式和调度算法的若干准则 1. 面向用户的准则 (1) 周转时间短——作业从开始到结束：通常作为评价批处理系统调度算法的依据。 可把平均周转时间描述为： 作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权 周转时间，而平均带权周转时间则可表示为: (2) 响应时间快—从输入到首次响应：选择分时系统调度算法的依据。 (3) 截止时间的保证—开始或完成的最迟时间：评价实时系统调度算法的指标。 (4) 优先权准则：作为批处理、分时、实时系统选择算法的依据。 3.3 调度算法 3.3.1 先来先服务和短作业(进程)优先调度算法 1.先来先服务调度算法 (FCFS)—可用于作业和进程调度利于长作业(CPU繁忙型)，不利于短作业(I/O繁忙型) 短作业(进程)优先调度算法SJ(P)F--可用于作业和进程调度 SJ(P)F是从后备(就绪)队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行(将处理机分配给它)。 优点：适合于短作业,如上表中的D。 缺点： (1) 该算法对长作业不利：如上表中的C。更严重的是，由于总是优先调度那些(即使是后进来的)短作业(进程)，将可能导致长作业