chap3 进程调度

《chap3 进程调度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲进程调度叶保留yebl@nju.edu.cn南京大学计算机科学与技术系教学目标了解进程调度设计的影响因素掌握进程调度的基本设计思想理解Linux2.4的进程调度机制理解Linux2.6的进程调度机制23目录进程调度概述Linux2.4进程调度机制Linux2.6进程调度机制4调度类型高级调度(作业调度、长程调度)选出若干作业进入系统，分配所需资源，创建对应作业的用户进程控制多道程序的道数，作业数越多，每个作业获得的CPU时间越少中级调度根据主存资源量决定主存能容纳的进程数，根据进程的当前状态决定辅存和主存中的进程的对换短期平滑和调整系统负荷，充分提高

2、主存利用率和系统吞吐率低级调度(进程/线程调度、短程调度)从就绪队列中选择进程/内核级线程使用处理器操作系统最为核心的部分，执行十分频繁，常驻主存进程调度概述5三级调度模型处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度进程调度概述6低级调度目标提高CPU使用率基本任务选择下一个要运行的进程核心问题在就绪态进程间分配CPU时间，保证各进程公平、有效地使用CPU资源难点响应时间vs.系统开销满足不同进程的调度需求调度器的基本要求减少调度器自身开销增加执行程序时间对交互式应用有良好的响应速度进

3、程调度概述7多任务系统分类非抢占式多任务工作模式：让步(yielding)除非进程主动停止运行，否则一直执行特点无法预料进程独占处理器的时间，易导致系统崩溃抢占式多任务工作模式：抢占(preemption)进程在被抢占前可运行的时间是预先设置好的，称为时间片（timeslice）特点可避免个别进程独占系统资源难点调度策略？进程调度概述8进程分类第一种分类I/O-boundI/O操作频繁通常会花费很多时间等待I/O操作的完成不需要太长时间片CPU-bound计算密集型需要大量的CPU时间进行运算进程调度概述9进程分类(续)第二种分类方法交互式进程需与用户频繁

4、交互，因此要花很多时间等待用户输入操作响应时间要快，平均延迟要低于50~150ms典型交互式程序：shell、文本编辑程序、图形应用程序等批处理进程不必与用户交互，通常在后台运行可容忍一定的响应延迟典型批处理程序：编译程序、科学计算实时进程有实时需求，不应被低优先级的进程阻塞响应时间要短、要稳定典型实时进程：视频/音频、自动化控制等进程调度概述10调度策略设计目标决定何时如何选择一个新进程投入运行进程响应时间尽可能快（切换时机）后台作业吞吐量尽可能高（降低切换开销）协调不同进程的调度顺序（优先级定义）避免进程饥饿（动态优先级更新）运行态就绪态等待态选中落选

5、出现等待事件等待事件结束进程调度概述11调度策略设计的技术难点如何动态管理和维护就绪进程进程调度相关数据结构设计如何设定进程优先级进程类型：实时进程vs.交互式进程vs.普通进程进程动态/动态优先级的定义进程动态优先级调整策略及调整时机如何设置/调整进程CPU时间片初始值设置原则时间片修改/调整位置、时机及策略（进程创建/运行/退出）进程调度/切换依据如何选择侯选进程与静态/动态优先级、进程类型、时间片等的关系多处理器系统SMPCPU选择策略负载均衡与迁移机制进程处理调度流程进程调度概述12Linux进程调度基本机制调度方法基于分时技术的抢占式调度CPU时

6、间被划分成“时间片”，为每个可运行进程分配一个时间片分时依赖于时钟中断，对进程透明调度策略进程分类普通进程实时进程优先级静态优先级动态优先级进程调度概述13目录进程调度概述Linux2.4进程调度机制进程调度相关数据结构进程调度相关数据调度策略调度时机调度过程的实现Linux2.6进程调度机制14调度相关数据结构task[NR_TASKS]所有进程（包括0号进程）构成的双向循环链表该链表全系统唯一表头是启动CPU（BSP）的0号进程，即init_taskinit_tasks[NR_CPUS]由所有CPU的idle_task(idle进程)组成的双向链表实质

7、为task[NR_TASKS]的子链表调度器通过宏idle_task(cpu)访问这些“idle”进程Linux2.4进程调度机制15init_tasks结构说明调度器不直接使用以init_task为表头的进程链表仅使用其中的“idle_task”，该进程在引导完系统后即处于cpu_idle()循环中新进程被添加到init_task的左端，即prev端Linux2.4进程调度机制16idle进程系统引导进程（init_task）在引导结束后成为cpu0上的idle进程每个cpu上都有一个idle进程进程登记在init_tasks[]数组中，可用idle_t

8、ask()宏访问idle进程不进入就绪队列仅当就绪队列为空时idl