• 阻塞是在线程一级完成 • 核心例程是多线程的 缺点： • 在同一进程内的线程切换调用内核，导致 速度下降
（3）两者分析
• • • • • • • • 针对不同的操作系统 开销和性能（线程的调度和切换速度） 系统调用（阻塞） 线程执行时间 灵活性 可扩充性 抢占CPU 共享进程的资源
（4）ULT和KLT结合方法
* 首先系统中设置多个就绪队列
* 每个就绪队列分配给不同时间片，优先级高的为第一级 队列，时间片最小，随着队列级别的降低，时间片加大
* 各个队列按照先进先出调度算法
* 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的 事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢 占进程回到原来一级就绪队列末尾
2．确定算法的原则
• 具有公平性 • 资源利用率高（特别是CPU利用率）
• 在交互式系统情况下要追求响应时间 （越短越好）
• 在批处理系统情况下要追求系统吞吐量
3．各种进程调度算法
先进先出进程调度算法（FIFO）
按照进程就绪的先后次序来调度进程
优点:实现简单 缺点:没考虑进程的优先级
基于优先数的调度 （HPF—Highest Priority First）
固定时间片
可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力
多队列反馈调度算法：
将就绪队列分为N级，每个就绪队列分配 给不同的时间片，队列级别越高，时间 越长，级别越小，时间片越小，最后一 级采用时间片轮转，其他队列采用先进 先出； 系统从第一级调度，当第一级为 空时，系统转向第二个队列，.....当运 行进程用完一个时间片，放弃CPU时，进 入下一级队列；等待进程被唤醒时，进 入原来的就绪队列；当进程第一次就绪 时，进入第一级队列
进程调度（CPU调度）
要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU
—CPU调度过程（进程的上下文切换）
处理机调度分成三个层次
处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综 合性能指标有重要影响 可把处理机调度分成三个层次：
间隔时钟
进行分析比较
虚时钟:
每个进程分配给一个虚时钟来记录CPU时 间,这个时钟称为虚时钟 虚时钟存放在PCB中，属于现场的一部分， 进程运行时，将虚时钟放入内存开辟的 专门单元，离开CPU则放在 PCB中
2.核心处理流程
进入核心的唯一入口:中断 中断后进入核心，由硬件完成
3.内核的执行特点
（2）核心级线程（KLT）
• 所有线程管理由核心完成
• 没有线程库，但对核心线程工具提供API
• 核心维护进程和线程的上下文
• 线程之间的切换需要核心支持
• 以线程为基础进行调度
• 例子：Windows NT，OS/2
核心级线程的优点和缺点
优点：
• 对多处理器，核心可以同时调度同一进程 的多个线程
• 选择另一个要执行的进程
• 更新被选中进程的PCB
• 从被选中进程中重装入 CPU 上下文
二.系统核心 系统核心：
向上提供多个无中断的虚拟机器
在核心内不允许中断 特点：* 为进程运行提供一个舞台
* 核心常驻内存
* 设计短小精焊
1.核心的组成
中断处理 进程管理: 调度 控制 通讯 互斥 同步等 原语管理: 在核心中提供一系列原语，同步,通 信，创建，撤消等
线程的引入（续3） 线程：有时称轻量级进程
进程中的一个运行实体 是一个CPU调度单位 资源的拥有者还是进程或称任务 将原来进程的两个属性分开处理
线程的引入（续4）
线程：
• 有执行状态（状态转换） • 不运行时保存上下文
• 有一个执行栈
• 有一些局部变量的静态存储
• 可存取所在进程的内存和其他资源
由中断驱动的: 中断→内核→退出
内核执行是连续的
内核执行过程中在中断屏蔽状态下 内核使用特权指令
三.线程的基本概念 • 线程的引入
• 线程与进程的对比
• 线程的实现
• 实例：Solaris
1.线程的引入
进程的两个基本属性： • 资源的拥有者： 给每个进程分配一虚拟地址空间，保存进 程 映 像 ， 控 制 一 些 资 源 （ 文 件 ， I/O 设 备），有状态、优先级、调度 • 调度单位：
• 低级调度 也称微观调度，从处理机资源分配
的角度来看，处理机需要经常选择就绪进程或 线程进入运行状态，低级调度的时间尺度通常 是毫秒级的。由于低级调度算法的频繁使用， 要求在实现时做到高效
一.进程调度算法
1．进程调度
进程调度的任务是控制协调进程对CPU的 竞争。即按一定的调度算法从就绪队列 中选中一个进程，把CPU的使用权交给被 选中的进程
何时切换进程?
• 只要OS取得对CPU的控制，进程切换就可 能发生，如:
–超级用户调用
• 来自程序的显式请求 (如：打开文件)， 该进程 通常会被阻塞
–陷阱
• 最末一条指令导致出错，会引起进程移至退出状 态
–中断
• 外部因素影响当前指令的执行，控制被转移至IH （中断处理程序）
中断的例子
–时钟
• 进程用完其时间片，被转换至就绪状态
优先选择就绪队列中优先级最高的进程投 入运行
优先级根据优先数来决定
确定优先数的方法
静态优先数法： 在进程创建时指定优先数，在进程运行 时优先数不变
动态优先数法：
在进程创建时创立一个优先数，但在其 生命周期内优先数可以动态变化。如等 待时间长优先数可改变
两种占用CPU的方式
可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就 绪时，系统可强行剥夺正在运行进程的CPU， 提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的 原因不能运行，否则一直运行下去
队列管理:
队列数据结构:指向队首的表指针
三个队列: 运行，就绪，等待队列
排队方式: 排队首
排队尾
插 队
出队方式: 队首出队/队中出队
队列管理: 中断之后，进程调度之前
现场管理:
保存现场;注意顺序,中断之后第一步
恢复现场:恢复时机，进程调度最后一步
时钟管理:
以固定频率 +1 -1
用途:进入绝对时钟
* 当第一级队列空时，就去调度第二级队列，如此类推
* 当时间片到后，进程放弃CPU，回到下一级队列
二.进程调度的时机
当一个进程运行完毕，或由于某种错误而终止 运行 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就 绪 在进程通信中，执行中的进程执行了某种原语 操作（P操作，阻塞原语，唤醒原语）
一组管理线程的过程
• 核心不知道线程的存在
• 线程切换不需要核心态特权 • 调度是应用特定的
线程库
• 创建、撤消线程 • 在线程之间传递消息和数据 • 调度线程执行
• 保护和恢复线程上下文
对用户级线程的核心活动
• 核心不知道线程的活动，但仍然管理线程 的进程的活动 • 当线程调用系统调用时，整个进程阻塞
• 但对线程库来说，线程仍然是运行状态
即线程状态是与进程状态独立的
用户级线程的优点和缺点
优点：
• 线程切换不调用核心
• 调度是应用程序特定的：可以选择最好的算法 • ULT可运行在任何操作系统上（只需要线程库）
缺点：
• 大多数系统调用是阻塞的，因此核心阻塞进程， 故进程中所有线程将被阻塞 • 核心只将处理器分配给进程，同一进程中的两个 线程不能同时运行于两个处理器上
例子1：
LAN中的一个文件服务器，在一段时间内需 要处理几个文件请求
因此有效的方法是：为每一个请求创建一个 线程
在一个SMP机器上：多个线程可以同时在不 同的处理器上运行
例子2：
一个线程显示菜单，并读入用户输入； 另一个线程执行用户命令
考虑一个应用：由几个独立部分组成，这 几个部分不需要顺序执行，则每个部分 可以以线程方式实现
（如果没有就绪进程,系统会安排一个闲 逛进程(idle),没有其他进程时该进程一 直运行,在执行过程中可接收中断） * 恢复现场：最后一步恢复选中进程的PSW
在进程（上下文）中切换的步骤
• 保存处理器的上下文，包括程序计数器和其它 寄存器 • 用新状态和其它相关信息更新正在运行进程的 PCB
• 把原来的进程移至合适的队列-就绪、阻塞
• 线程创建在用户空间完成
• 大量线程调度和同步在用户空间完成
• 程序员可以调整KLT的数量
• 可以取两者中最好的
• 例子：Solaris
4. 实例：Solaris
进程：
• 用户地址空间 • 用户栈
• 进程控制块
实例：Solaris（续1）
用户级线程（线程库）：
可在应用进程中建立多个ULT 每个ULT需要：栈、程序计数器 不受调度程序的调度，线程切换快 对操作系统不可见
当一个线程因I/O阻塞时，可以切换到同一 应用的另一个线程
2.线程与进程的比较
• 调度 • 并发性 • 拥有资源 • 系统开销
3.线程的实现机制
• 用户级线程 • 核心级线程 • 两者结合方法
（1）用户级线程（User Level Thread）
• 由应用程序完成所有线程的管理
通过线程库(用户空间)
用户 地址 空间
核 心 栈
核 心 栈