调度的队列模型.pptVIP

第四讲 CPU调度 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013 内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法 内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法 调度的类型 按调度的层次： 长期（长程、作业、高级）调度； 中期（中级、中程）调度； 短期（短程、进程、低级）调度 按OS的类型： 批处理调度 分时调度 实时调度 多处理机调度 等等 作业调度 在批处理系统中，一般需要进行作业调度；分时系统和实时系统大多不需要作业调度 作业调度要考虑1）接纳多少个作业??多道程序度2）接纳哪些作业??调度算法 中期调度 与挂起状态相关 目的：提高内存利用率和系统吞吐量 对换 进程调度 在分时系统中，进程调度的运行频率很高 Linux中，常规经验值，时间片大小50ms左右 进程调度要考虑1）什么时候 发生调度的时机2）哪个进程 调度原则和调度算法3）如何分派 进程上下文切换 调度的方式：抢占式／非抢占式 可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去 Scheduling time 调度的时机 When a process Switches from running to waiting state Switches from running to ready state Switches from waiting to ready Terminates Scheduling Nonpreemptive: for 1 & 4 Till 1 or 4 Win 3.x, old versions of MacOS, … Preemptive: for 2 & 3 根据时间片抢占、根据优先关系抢占 与进程调度相关的进程运行规律分析 Process execution = n (CPU execution + I/O wait) Objective of multiprogramming Maximum CPU utilization Scheduling is a fundamental OS function for almost all resources Alternating Sequence of CPU And I/O Bursts A property of process：CPU-I/O burst cycle Process Starts as a CPU burst Ends as a CPU burst CPU burst distribution CPU-bound VS. I/O-bound Histogram of CPU-burst Times 内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法 调度队列模型 按照系统中调度层次的数目，有3种模型 仅有进程调度的 具有高级和低级调度的 同时具有三种调度的 仅具有进程调度的调度队列模型 就 绪 队 列 阻 塞 队 列 CPU 时间片完 交互用户 进程调度 进程完成 等待事件 事件发生 具有高、低两级调度的调度队列模型 进程完成 进程调度 就 绪 队 列 阻 塞 队 列 CPU 时间片完 作 业 调 度 等待事件1 阻 塞 队 列 阻 塞 队 列 等待事件2 等待事件n 事件1发生 事件2发生 事件n发生 后 备 队 列 批作业 交互 具有三级调度的调度队列模型 进程完成 进程调度 就 绪 队 列 绪 就 、 挂 起 队 列 CPU 时间片完 作业 调度 事件出现 阻 塞 队 列 挂起 等待事件 中级 调度 事件发生 后 备 队 列 塞 阻 、 挂 起 队 列 挂起 批作业 交互 内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法 选择调度方式和算法的若干准则 面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐率高 处理机利用率好 各类资源的平衡利用 面向用户的准则：1、周转时间短 定义：作业周转时间(Turnaround time)是指从作业提交给系统开始，到作业完成为止的这段时间间隔。包括： 1）作业在外存后备队列上等待作业调度的时间 2）进程在就绪队列上等待进程调度的时间(waiting time) 3）进程在CPU上执行的时间 4）等待I/O操作完成的时间 其中，第2、3、4项在一个作业的处理过程中，可能发生多