[TOC]

飞书文档

计算机操作系统

第一章 概述

操作系统的定义

• 控制应用程序执行的程序
• 应用程序和计算机硬件间的接口

或者定义为: 一组控制和管理计算机硬件和软件资源, 合理地对各类作业进行调度, 以及方便用户使用的程序的集合

操作系统的目标: 方便 有效 扩展能力

操作系统所处的位置:

操作系统提供的服务

• 程序开发
• 程序运行
• I/O设备访问
• 文件访问控制
• 系统访问
• 错误检测和响应
• 记账

操作系统控制机制的特殊性

• 与普通软件相同, OS是由处理器执行的一段程序
• OS经常会释放控制, 且必须依赖处理器才能恢复控制

OS需要完成资源管理

• 内存的分配管理
• I/O的访问控制
• 对文件访问控制和使用
• 对处理器的分配

操作系统的发展过程

• 穿行处理
• 简单批处理系统
• 多道批处理系统
• 分时系统
• 实时系统

串行处理

用户按顺序访问计算机: 串行

调度复杂, 准备时间长

简单批处理系统

监控程序

• 对一批作业进行自动处理
• 内存中只能同时存放一道作业

监控程序的功能

• 作业的自动接续
• 内存保护: 保护监控程序所在区域
• 定时器: 防止某作业独占系统
• 特权指令: 只能由监控程序执行的指令
• 中断: 早期计算机没有中断功能

运行模式

• 用户模式: 不允许执行特权指令
• 内核模式: 可执行特权指令及访问受保护的内存区域

处理器经常处于空闲状态

多道批处理系统

简单批处理系统, 处理器必须等待I/O指令完成才能继续处理

多道批处理系统:

• 内存中同时存放多个作业
• 多个作业可并发执行
• 作业调度程序负责作业的调度

多道批处理系统的特征: 多道行, 并行性, 无序性, 无交互能力

分时系统

• 采用多道程序设计技术处理多个交互作业
• 用户共享终端
• 不同终端可以同时访问系统

分时系统的特征: 多路性, 独立性, 及时性, 交互性

	批处理系统多道程序设计	分时
主要目标	充分利用处理器	减小响应时间
操作系统指令源	作业提供命令, 没有用户交互	用户在终端输入命令

第一个分时操作系统: CTSS (Compatible Time-Sharing System)

实时系统

概念:系统能够及时响应外部事件的请求, 在规定的时间内开始或完成对该事件的处理, 控制实时任务协调运行

实时系统的特征: 可确定性, 可响应性, 用户控制, 可靠性, 故障弱化能力

进程

概念:

• 一个正在执行的程序
• 计算机中正在运行的程序的一个实例
• 可分配给处理器并由处理器执行的一个实体
• 由下述表征的活动单元:
  • 一个单一顺序线程
  • 一个当前状态
  • 一组相关系统资源

进程的组成

• 程序
• 数据, 如变量, 工作空间, 缓冲区
• 执行上下文
  • 进程状态
  • OS管理和控制进程所需的所有数据
  • 如处理器寄存器的内容, 进程优先级, 是否在等待I/O事件, 在内存中的位置
  • 进程需要数据结构来保存进程的上下文环境

存储管理的任务

1. 进程隔离
2. 自动分配和管理
3. 支持模块化程序设计
4. 保护盒访问控制
5. 长期存储, 文件系统实现了长期存储, 文件是一个有名称的对象, 也是访问控制和保护的基本单元

虚拟存储

• 以逻辑方式访问存储器, 不考虑物理内存可用的空间数量
• 满足多作业同事主流内存的要求
• 换入换出机制
• 分页机制, 解决每个进程大小不同的问题
  • 进程由若干个固定大小的块组成, 这就是页
  • 虚地址由页号和页内偏移量组成
  • 每一页都可置于内存中的任何位置
  • 提供了虚地址和内存中实地址间的动态映射机制
• 每个作业部分驻留在内存时, 硬件检测到缺页时, 安排载入

OS的四类安全问题

• 可用性: 系统不被中断
• 保密性: 未授权不访问数据
• 数据完整性: 未授权不修改数据
• 认证: 用户身份的正确认证和消息/数据的合法性

资源分配和调度策略需要考虑

• 公平性
• 有差别的响应性
• 有效性
  • OS希望有最大吞吐量和最小响应时间
  • 能容纳尽可能多的用户
  • 折中处理矛盾

现代操作系统的特征

1. 微内核
2. 多线程
3. 对称多处理
4. 分布式的操作系统
5. 面向对象的设计

微内核: 只给内核分配基本的功能, 如地址空间, 进程间通信, 基本调度

多线程: 一个应用的进程划分为同时运行的多个线程

• 线程
  • 可分派的工作单元
  • 包括处理器的上下文环境, 自身的数据区域
  • 顺序执行且可以中断(转到其他线程)
• 进程
  • 一个或多个线程和相关系统资源的集合

对称多处理SMP

• 指计算机硬件体系结构, 也指采用该体系结构的操作系统行为
• 多个进程/线程可以并行运行
• 多个处理器对用户来讲是透明的
  • 多个处理器共享内存和I/O设施
  • 所有处理器可以执行同一任务
• 操作系统在不同处理器上调度不同的进程/线程, 并负责同步
• 优点
  • 性能好, 多个进程可以再不同的处理器上同时运行
  • 可用性好, 单个处理器失效不会导致机器停止
  • 渐增性好, 系统性能可以随着添加新的处理器而提高
  • 扩展性好, 生产商根据处理器的数量提供不同价格与性能的产品

分布式操作系统

面向对象的设计

• 可以模块化扩展小内核
• 保证代码完整性
• 开发分布式工具和分布式操作系统更容易

容错性

提高容错性的技术:

• 进程隔离
• 并发控制
• 虚拟机
• 检测点和回滚机制

多处理器和多核操作系统设计考虑因素

要提供多道系统的所有功能, 还要提供适应多处理器的额外功能

多核系统设计的常用策略: 应用层并行和虚拟机方式

应用层并行

• 开发者决定如何分割任务为子任务
• 操作系统要支持并行编程, 并为子任务分配资源

虚拟机方式

• 随着芯片的核的增加, 为一个进程分配一个或多个核
• 多核操作系统负责为应用程序分配核

主流操作系统

1. Windows
2. 传统UNIX系统
3. 现代UNIX系统
4. Linux系统
5. Android系统

第二章 进程管理–1. 描述

进程和进程控制块

进程

进程的两个基本元素

• 程序代码
• 和代码相关的一组数据

进程的基本特征

• 动态性, 本质特性
• 并发性, 重要特性
• 独立性
• 异步性, 每个进程的执行速度不一致且不可预知

进程和程序的比较

• 进程 = 进程控制块 + 程序 + 相关数据
• 进程是一个正在执行的程序实例
• 引入进程的目的是为了使多道程序能正确地并发执行
• 程序是静态实体, 进程具有动态性
• 进程与程序不一一对应, 一个应用程序的执行对应一个或多个进程

进程控制块

进程由程序代码, 相关数据和进程控制块组成

进程控制块包括了进程的元素, 可以用来回复中断, 由OS创建和管理是支持多进程的重要工具

进程状态

分派器将处理器从一个进程切换到另一个进程的小程序

处理器的行为可以用多个进程交替执行的轨迹来描述

进程的两状态模型

三个进程交替执行的轨迹: (这里假设时间片为6个指令周期)

此时进程的两状态模型图为

进程的创建与终止

进程创建

OS创建数据结构, 为进程分配内存

创建原因

1. 新的批处理作业
2. 交互登陆, 如终端用户登陆系统
3. 提供服务, 如控制打印进程
4. 由现有进程派生 模块化开发或并行性考虑

进程派生: 进程显示地请求创建一个进程, OS创建它的一个子进程

进程终止

批处理作业会包含一个HALT指令或其他显式的OS服务调用来终止进程

用户可以指出交互式的应用程序进程的终止时间

五状态模型

新建态, 就绪态, 运行态, 阻塞态, 退出态

加载, 调度, 超时, 等待时间, 发生事件, 释放

进程的排队模型

• 单阻塞队列: 所有阻塞进程位于一个阻塞队列
  • 
• 多阻塞队列: 一个事件对应一个阻塞队列
  • 

挂起进程

竞争内存资源可能导致

• 内存资源紧张
• 无就绪进程, 处理机空闲

交换

交换: 把内存中的进程部分或全部移到磁盘中, 该进程变为挂起状态, 增加了挂起态

内存紧张/无就绪进程时, 将阻塞进程换出到磁盘的挂起队列, 然后内存从挂起队列取回进程或接纳新进程

挂起

被挂起的进程不参与CPU的竞争

但是存在问题: 挂起进程等待的时间没有发生时, 挂起进程取回内存没有意义, 只有挂起进程没有在等待事件时, 此时从内存中取回才是有意义的, 所以引入阻塞/挂起态和就绪/挂起态

挂起进程的特征:

1. 进程不能立即执行
2. 进程在等待/没有等待一个事件
3. 进程可能被进程自己, 父进程或OS等代理置为挂起状态
4. 除非代理显式命令进程状态转换, 否则挂起状态不会变化

进程描述

操作系统的控制结构

操作系统的控制结构 = 内存表 + I/O表 + 文件表 + 进程表

内存表

用来跟踪内存和外存

外存中保存的进程使用某种虚拟存储或简单的交换机制

内存表包括

• 分配给进程的内存
• 分配给进程的外存
• 内存块或外存块的保护属性, 如为哪些进程共享
• 管理外存所需要的信息

I/O表

进程汇总有I/O操作时, 操作系统必须知道

• I/O操作的抓你
• 作为I/O传输数据的源或目标的内存单元

文件表

文件表包括的信息有:

• 文件是否存在
• 文件在外存中的位置
• 当前状态
• 其他属性

文件管理可能由文件管理系统或O自身维护

进程表

用来管理进程

表中有对内存, I/O设备和文件的直接/间接引用

进程表本身能被OS访问, 受制于内存管理

进程的控制结构

进程的物理存在是什么

• 进程位置

  • 执行程序
  • 数据
  • 栈

• 进程属性

  • 进程控制块PCB, 也即控制属性

  • 进程映像, 程序,数据, 栈和属性的集合

    • 用户数据

    • 用户程序

    • 栈, 每个进程有一个或多个后进先出LIFO栈, 用于保存参数, 过程调用和系统调用地址

    • 进程控制块, OS控制进程所需的数据

      1. 进程标识信息

         • 每个进程都有唯一的数字标识符

         • 可认为是主进程表的索引

         • 标识符可以引用进程表, 进程通信时可以标识通信目标, 指明父进程和子进程

         • 标识符包括:

           1. 进程标识符
           2. 父进程标识符
           3. 用户标识符

      2. 处理器状态信息

         • 由处理器寄存器的内容组成, 包括用户可见寄存器, 控制盒状态寄存器, 栈指针

           

         • 程序状态字寄存器, 包括了条件码(溢出, 进位)和其他状态信息(中断屏蔽, 对齐检查)

      3. 进程控制信息

         • OS控制和协调各种活动进程所需的额外信息

  • 进程映像的位置取决于内存管理方案, 进程映像在虚存中的结构

进程控制

内核, 操作系统的核心

• OS中包含最重要系统功能的部分
• 常驻内存, 提高OS运行效能

OS内核的功能包括资源管理功能, 支撑功能

内核的资源管理功能

1. 进程管理
   • 进程创建和终止
   • 进程调度和分派
   • 进程切换
   • 进程同步和进程间通信的支持
   • 管理进程控制块
2. 存储管理
   • 分配进程的地址空间
   • 交换
   • 页和段管理
3. I/O设备管理
   • I/O缓冲区的管理
   • 为进程分配I/O通道和设备

内核的支撑功能

1. 中断处理
2. 时钟管理, 如时间片控制
3. 记账(统计, 检测)功能

执行模式

采用两种模式的原因: 保护OS和重要的操作系统表(如PCB)不受程序干扰

用户模式

具有较少优先权, 用户程序在用户模式下运行

系统模式(内核模式/控制模式)

与OS相关, 具有更多优先权, 运行OS的内核, 某些指令只能在特权模式下运行, 部分内存只能在特权模式下访问

程序状态字寄存器中存在指示执行模式的位:

• 用户调用OS服务或中断促发系统例程时, 相关位被置为内核模式
• 从系统服务返回用户进程时, 执行模式置为游戏模式

进程创建

1. 给新进程分配唯一的进程标识符
2. 为进程分配空间
3. 初始化进程控制块
   • 初始化标识信息
   • 初始化处理机状态信息
   • 初始化进程调度信息
4. 建立链接, 将连接插入就绪或就绪/挂起链表
5. 建立或扩充其他数据结构

进程切换

进程切换: 调度另一个就绪进程占用处理器执行

系统中断

• 普通中断

  某种独立的外部事件发生导致程序中断, 如时钟中断, I/O中断, 内存失效

  时间片: 进程被中断前允许执行的最大运行时间

• 陷阱

  当前运行进程内部产生的错误或异常

  OS决定错误或异常是否致命, 若是则进程置为退出态, 切换进程; 若否则OS的动作取决于错误的性质

模式切换

模式切换: 用户模式和内核模式间的相互转换

模式切换的原因: 系统调用或中断

模式切换是否会必然导致进程切换? 不一定, 如I/O中断, 某些系统调用不一定会进程切换

进程状态转换

• 模式切换可在不改变运行进程状态的情况下出现(内核模式也可以执行用户模式的行为), 进程切换必须改变
• 改变进程状态, 操作系统必须使环境产生实质变化

进程切换的步骤:

1. 保存处理器上下文环境, 包括程序计数器和其他寄存器
2. 更新当前进程的进程控制块
3. 将当前进程的进程控制块移到相应队列(就绪, 阻塞, 就绪/挂起)
4. 切换至另一进程, 更新其进程控制块
5. 更新内存管理数据结构
6. 回复被选择进程的上下文环境, 如载入程序计数器和其他寄存器先前的值

UNIX SVR4的进程管理

进程创建

进程创建由内核系统调用fork()实现

OS在内核模式下完成

1. 在进程表中为新进程分配一个空项
2. 为子进程分配一个唯一的进程标识符
3. 复制父进程的进程映像
4. 增加父进程拥有的文件计数器, 反应另一个进程现在也拥有这些文件的事实
5. 将子进程设置为就绪态
6. 将子进程的ID号返回给父进程, 0值返回给子进程

进程创建后, 内核可继续完成分派器的工作, 具体可能为

1. 停留在父进程, 控制权返回到用户模式下父进程调用fork的位置
2. 控制权交给子进程, 执行点为for,k调用返回处
3. 控制权交给其他进程, 父子进程处于就绪态

fork

fork调用格式: pid = fork()

fork()创建子进程后, 父进程和子进程都执行下一条语句

父进程的返回值为子进程的pid, 子进程的返回值为0

父子进程的运行是无关的, 运行顺序不固定

线程

进程与线程

进程的两个基本属性

• 拥有资源的独立单位
• 调度/执行的基本单位

多线程: OS在单个进程内支持多个并发路径的能力

单线程方法: 每个进程中只有一个线程在执行

线程: 进程中的一个实体, 是独立调度和分派的基本单位. 每个线程有

• 执行状态(运行, 就绪等)
• 未运行时保存的线程上下文
• 执行栈
• 用于局部变量的静态存储空间
• 与进程内其他线程共享的内存和资源访问

单线程和多线程模式

线程的优点

1. 创建线程的时间少于创建进程的时间
2. 终止线程比终止进程时间少
3. 同一进程内线程切换时间少于进程切换时间
4. 现成提高了不同执行程序间通信的效率

调度和分派是在线程基础上完成的

线程的主要状态

• 运行
• 就绪
• 阻塞

和线程状态变化相关的基本操作

• 派生
• 阻塞
• 解除阻塞
• 结束

单处理器上的多线程示例

线程同步原因

1. 一个进程中的所有线程共享一个地址空间和进程的资源
2. 一个线程对共享资源的修改都将影响同一进程其他线程的影响

线程分类

• 用户级线程ULT
• 内核级线程KLT
• 混合模式

用户级线程ULT

所有线程管理工作由应用程序完成, 内核意识不到线程的存在

用户级线程状态和进程状态间的关系示例(这里进程被阻塞线程还在运行, 是线程库的数据结构没有改变)

用户级线程ULT的优缺点

• 优点
  1. 线程切换不需要内核模式特权
  2. 调度策略因应用程序不同而有所不同
  3. 可以运行在任何OS上
• 缺点
  1. 典型的OS中, 系统调用会引起进程阻塞. 即某一线程执行系统调用, 同一进程的其他线程都被阻塞
  2. ULT策略和多处理器技术不能同时采用

ULT缺点的解决办法: Jacketing技术

将可能产生阻塞的系统调用转换成非阻塞的系统调用, 即将应用程序写成多进程程序而非多线程

内核级线程KLT

线程管理由内核完成, 应用程序没有线程管理的工作, 如Windows

内核级县城KLT的优缺点

• 优点

  1. 内核可以把同一进程的多个线程调度到多处理器上
  2. 一个线程阻塞时, 内核可以调度同一进程内的其他线程
  3. 内核例程本身也可以是多线程的

• 缺点

  控制权从一个线程给另一个线程时, 需要切换到内核模式

混合方法

线程创建在用户空间完成

线程调度和同步由应用程序完成

一个应用程序中的多个线程被映射到一些内核线程上

第二章 进程管理–2. 调度

如果多个进程/线程竞争CPU, 需要选择下一个要运行的进程/线程, OS中完成这部分工作的程序成为调度程序, 调度程序使用的算法是调度算法

调度的类型

• 长程调度
• 中程调度
• 短程调度

具有三种调度的队列模型:

长程调度

决定哪个程序可以进入系统中处理

控制系统中并发的度

从作业队列中选择作业来创建进程, 为此需要考虑

• 何时OS能接纳一个或多个进程
• 接纳哪个作业创建进程
  • 先来先服务
  • 优先级, 期望执行时间, I/O需求

中程调度

交换功能的一部分

换入决定取决于系统并发度的需求

在不适用虚存的系统中, 换入决策要考虑换出进程的存储需求

短程调度

称为分派程序, 执行最频繁, 精确决定下次执行哪个进程

导致当前进程阻塞或抢占当前运行进程的事件发生时, 调用短程调度程序

事件可能包括: 时钟中断, I/O中断, 系统调用, 信号, 如信号量

短程调度的主要目标: 按照优化系统某些方面的方式, 来分配处理器时间

调度的规则

与调度规则相关的概念

• 响应时间: 从用户提交请求开始到接收响应之间的时间间隔
  • 响应时间 = 输入传送时间 + 处理时间 + 响应传送时间
• 周转时间(驻留时间): 一个进程从提交到完成之间的时间间隔
  • 周转时间 = 等待资源的时间 + 执行时间, 等待资源包括处理器资源
• 截止时间: 任务开始执行的最迟时间, 或必须完成的最迟时间
• 吞吐量: 单位时间内, 系统完成的进程数
• 处理器利用率: 处理器处于忙状态的时间百分比

计算

周转时间: 一个进程从提交到完成之间的时间间隔

$周转时间 = 等待资源的时间 + 执行时间$

平均周转时间: 多个进程周转时间的平均值

带权周转时间: 进程的周转时间与系统为它提供的服务时间之比

平均带权周转时间:多个进程带权周转时间的平均值

调度规则的划分

• 面向用户, 与性能相关

  周转时间, 响应时间, 最后期限

• 面向用户, 与性能无关

  可预测性

• 面向系统, 与性能相关

  吞吐量, 处理器利用率

• 面向系统, 与性能无关

  公平性, 强制优先级, 平衡资源

优先级的使用: 考虑进程优先级可能导致饥饿, 可以采用动态优先级方案

调度的决策模式

• 非抢占

  只有在进程执行完毕或申请I/O或请求OS服务而阻塞自己时才释放处理机

• 抢占

  执行进程可能被OS中断, 并转换为就绪态

  抢占可能发生在

  • 新进程到达时
  • 中断发生后把一个阻塞进程置为就绪态
  • 周期性的时钟中断

调度的选择函数

基于优先级, 资源需求或进程的执行特性, 选择下次执行哪个就绪进程

基于执行特性时的关键参数

• w = 等待时间
• e = 目前的执行时间
• s = 进程的总服务时间, 包括e; 这个参数需要估计或由用户提供

调度算法

• 先来先服务FCFS, 也称FIFO
• 时间片轮转RR
• 短作业优先SPF/SJF/SPN
• 剩余时间最短优先SRT
• 响应比高者优先HRRN
• 反馈Feedback

先来先服务First-Come-First-Served(FCFS)

评价:

• 非抢占调度方式

• 利于CPU繁忙型进程, 不利于I/O进程

• 不适合单处理器系统, 适合和其他调度算法混合使用

• 平均周转时间长

• 长进程有利, 不利于短进程

时间片轮转调度算法Round Robin(RR)

RR在通用的分时系统或事务处理系统中很有效

计算中要注意, 如果一个进程时间片结束的同时有一个新进程, 刚结束的进程在队列中要排到新进程后面

评价:

• 非抢占调度方式
• 常用于分时系统或事务处理系统
• 时间片的设置与系统性能, 响应时间密切相关
  • 时间片太短, 进程切换频繁, 降低CPU效率
  • 时间片太长, 短交互请求的响应时间变长
  • 时间片最好略大于一次典型的交互时间
• 对CPU密集型进程有力, 对I/O密集型进程不利
  • CPU密集型进程可以充分利用时间片
  • I/O密集型进程每次短时间使用CPU, 然后I/O阻塞, I/O操作后加入就绪队列, 若有CPU密集型在前面, 则需要长时间等待
  • CPU密集型进程不公平地使用了大部分CPU时间, 导致I/O密集型进程性能下降

RR算法的改进: VRR算法

增加一个辅助队列, 接受I/O阻塞完成的进程, 调度优先于就绪队列, 但占用的处理机时间小于就绪队列的时间片

短进程优先Shortest Job/Process First/Next(SJF/SPF/SPN)

短进程或短作业优先调度, 前提是执行时间可以预知

评价:

• 非抢占调度方式
• 短进程跳到队列头, 可能导致长进程饥饿
• 有利于短进程, 减小了平均周转时间
• 缺少抢占机制, 不适用于分时系统或事务处理环境
• 进程的长短根据用户提供的估计执行时间确定, 可能由于用户估计不准时而做不到真正的短作业优先调度

剩余时间最短者优先算法Shortest Remaining Time(SRT)

调度程序总是选择预期剩余时间最短的进程, 在SJF的基础上增加了抢占机制

评价

• 优点
  1. 不像FCFS偏爱长进程, 也不限购RR产生额外的中断, 从而减少了开销
  2. 周转时间方面SRT比SJF性能要好, 短进程只要就绪就可以被立即选择执行
• 缺点
  1. 需要估计预期的服务时间
  2. 存在长进程饥饿现象
  3. 必须记录进程的已服务时间

响应比高者优先Highest Response Ratio Next(HRRN)

当前进程执行完毕或需要阻塞时, 选择响应比最高的进程执行

$R_p = \frac{等待时间 + 服务时间}{服务时间} = \frac{w+s}{s}$

评价:

• 实质是一种动态优先权调度算法
• 是FCFS和SJF的结合, 既照顾了短进程, 也考虑了作业到达的先后次序, 不会使长进程长期得不到服务
• 每次调度前, 都要计算响应比, 增加系统开销, 且难以准确计算

反馈调度法Feedback(FB)

SJF, SPT, HRRN: 采用了"奖励短进程"的思想, 但是基于进程的预期执行时间–未来

FB:

• 采用"乘法运行时间较久进程"的思想
• 关注的是"已经执行"的时间
• 根据进程执行历史, 调度基于抢占原则(按时间片)
• 采用动态优先级机制, 可以获得较好的性能

FB采用多级队列区别对待的方法"惩罚长进程"

• 多个独立的, 优先级不同的就绪队列
• 各队列区别对待, 即优先调度优先级高的队列
• 进程执行过程中可降级, 即在整个生命周期内可能位于不同队列

FB有多个变种, 区别主要在于抢占机制不同

基于时间片轮转的反馈调度算法

1. 设置多个就绪队列, 每个队列赋予不同优先级
   • 第一队列优先级最高, 依次递减
   • 各个队列中进程执行的时间片不相同, 优先级越高的队列, 时间片越小
2. 新进程进入时, 放入第一个队列尾, 按FCFS原则排队
3. 若进程在时间片内完成则退出. 从队列$i$中调度的进程允许执行$2^i$的时间, 然后才被抢占, 降级到下一个优先级队列
4. 到达最低优先级队列后, 不再降级
5. 仅当第一队列空闲时, 才调度第二队列中的进程, 以此类推

评价:

• 多级反馈队列调度算法具有较好的性能, 能较好地满足各种类型用户的需要

• 有利于终端型作业用户

  常为短作业, 能在第一队列规定的时间片内完成

• 对短作业用户有利

  能在前几个队列规定的时间片内完成

• 长进程

  随着优先级的下降, 分配的时间片长度增肌, 减少了抢占次数

• 问题: 不断有新进程到来时, 长进程可能饥饿

实时系统与实时调度

实时系统

系统能及时响应外部事件的请求, 在规定时间内完成对该时间的处理, 并控制所有实时任务协调一致地运行

对实时系统而言, 系统的正确性不仅取决于计算的结果, 还依赖于产生结果的时间

截止时间

• 开始截止时间: 任务在某时间以前, 必须开始执行
• 完成截止时间: 任务在某时间以前必须完成

实时任务分类

• 有截止时间
  • 硬实时任务
  • 软实时任务
• 周期性/非周期性
  • 周期性实时任务
  • 非周期性实时任务

实时操作系统特点

• 可确定性: 任务按照固定的预先确定的时间或时间间隔进行
• 可响应性: 关注系统在知道中断后为中断提供服务的时间
• 用户控制: 用户能区分软/硬实时任务, 并控制任务优先级
• 可靠性: 实时响应和控制事件, 保障性能
• 失效弱化: 系统具有稳定性, 当不能满足所有任务的实时性时, 首先满足重要的/优先级高的任务期限

实时调度的调度方法

调度的方法: 下次调度哪个人物

抢占的烈性: 调度时采用什么抢占方式

实时调度方法

• 静态表驱动调度法
• 静态优先级抢占调度法
• 基于动态规划的调度法
• 动态尽力调度法

静态表驱动调度法

调度周期性实时任务

制订调度表以调度实时任务, 依据有到达时间, 执行时间, 完成截止时间和任务优先级

最早截止时间优先(EDF)调度算法属于此类

算法不灵活

静态优先级抢占调度法

调度非实时多道程序系统

需要确定优先级, 如在分时系统中可以对I/O和CPU密集型的进程赋予不同的优先级

实时系统中根据任务的时间约束赋予优先级

基于动态规划的调度法

实时任务到达后, 系统为新到达的任务和正在执行的任务动态创建一张调度表

在当前执行进程不会超时的条件下, 若也能让新任务在截止时间内完成, 立即调度新任务

动态尽力调度法

用于非周期性实时任务调度

任务到达时, 系统根据其属性赋予优先级, 优先级高的先调度

缺点是, 当任务完成或截止时间到达时, 很难知道该任务是否满足其约束时间

实时调度的抢占方法

• 基于时间片的轮转抢占式调度
• 基于优先级的非抢占式调度
• 基于优先级的抢占点抢占调度
• 立即抢占式调度

基于时间片的轮转调度(属于抢占方式)

实时进程按时间片轮转方式执行, 到达的实施进程放在就绪队列尾

新到的进程的时间片到时调度

响应时间一般为秒级

广泛用于分时系统及一般实时处理系统

基于优先级的非抢占调度

实时进程按优先级/非抢占方式执行, 新到的实时进程放在就绪队列首部

当前进程阻塞或完成时, 立即调度新到进程

响应时间一般在数百毫秒至数秒范围

多用于多道批处理系统及不太严格的实时系统

基于优先级的抢占点抢占调度

实时进程按优先级, 抢占方式执行

当下一个抢占点到来时, 立即占用CPU

响应时间一般在几毫秒至几十毫秒

用于一般实时系统

立即抢占式调度

实施进程按优先级, 抢占方式执行

响应时间为微秒至毫秒级

可用于苛刻的实时系统

实时调度示例

实时调度基于实时任务的信息, 如就绪时间, 启动限期, 完成限期, 处理时间, 资源需求, 优先级, 子任务结构

子任务结构: 一个任务可分解为一个必须执行的子任务和可选执行子任务, 前者有硬截止时间

下次调度哪个人物? 选择ddl最早的任务调度

采用什么抢占方式? 启动限期明确的任务, 采用飞抢占方式; 对于有完成限期的实时系统, 采用抢占策略

针对具有完成限期的周期性实时任务调度示例

此类任务是周期性的, 可预测的

采用最早截止时间有限调度算法Earliest Deadline First(EDF)

针对具有开始限期的非周期性实时任务

此类任务是非周期性的, 不可预测, 采用EDF算法存在危险性

若在任务就绪前, 预先知道任务的开始截止时间, 可以采用允许CPU空闲的EDF调度算法

允许CPU空闲的EDF调度算法

优先调度截止时间最早的合格任务, 并让该任务运行完毕

合格任务可以是还未就绪, 但是事先知道其开始截止时间的任务

CPU的利用率不高, 但这种调度算法可以保证系统中的任务按要求完成

速率单调调度算法Rate Monotonic Scheduling(RMS)

针对周期性任务

任务速率: 任务周期(以秒记)的倒数, 以赫兹为单位

优先级的确定

• 任务周期越短, 优先级越高
• 优先级函数式任务速度的单调递增的函数

系统按任务优先级的高低进行调度

实时系统处理能力限制

假定系统中有$m$个周期性的硬实时任务, 任务$i$的处理时间为$C_i$, 周期为$P_i$, 在单处理机情况下, 必须满足:

$\sum^m_{i=1}\frac{C_i}{P_i}\leq 1$

CPU的利用率 = 任务执行时间爱你 / 任务周期, 上式表示系统中各个任务的处理器总利用率不超过1

优先级翻转

一种错误的调度状态, 高优先级任务简介被低优先级任务抢占

解决: 优先级集成, 优先级较低的任务继承任何与其共享统一资源的优先级较高的任务的优先级

第二章 进程管理–3. 同步

并发的原理

多道程序设计为什么需要同步?

• 进程时计算机中的独立个体, 具有异步性, 并发性
• 资源是计算机中的稀缺个体, 需共享, 如CPU, 内存, I/O设备
• 进程间可能需要写作完成任务

并发相关的关键术语

• 原子操作: 一个或多个指令实现的动作或函数, 对外不可见, 要不都执行, 要么都不执行
• 互斥: 临界区同时只能有一个进程访问
• 临界资源: 不可同时访问, 必须互斥访问
• 临界区: 访问临界资源的代码, 任意时刻只能由一个进程在这段代码中运行
• 忙等现象: 一个进程等待进入临界区, 会继续消耗处理器的时间
• 活锁: 两个或两个以上的进程为响应其他进程而改变自己的状态, 不做有用工作的情形
• 死锁: 两个或两个以上的进程因等待其他进程做完某些事而不能继续执行的情形
• 竞争条件: 多个进程或线程读写共享数据时, 结果取决于多个进程的指令执行顺序
• 饥饿: 可以执行的进程被调度程序无限期忽视而不能执行的情形

进程的相对执行速度不可预测, 取决于

• 其他进程的活动
• OS处理中断的方式
• OS的调度策略

进程执行的速度补课预测, 给并发嗲来了困难

• 资源共享充满了危险
• OS需要优化管理资源的分配
• 定位程序的设计错误很困难

进程间的交互方式

• 竞争, 彼此不知道对方存在
• 通过共享合作, 彼此直到对方存在
• 通过通信合作

竞争

• 进程间不知道彼此存在
• 进程竞争使用同一资源时会发生冲突
• 如I/O设备, 存储器, 处理器, 始终

竞争资源时, 并发控制面临三个问题:

• 互斥
• 死锁
• 饥饿

进程间通过共享合作

多个进程共享资源

一个进程的结果可能取决于另一个进程

进程知道其他进程可能共享同一个数据, 因此必须合作

共享合作可能有四个问题

• 互斥
• 死锁
• 饥饿
• 数据一致性

进程间通过通信合作

进程间通过通信完成同步和协调彼此活动

一个进程的结果可能取决另一个进程

通信可由各种类型的消息组成

不涉及对共享资源的访问

通信合作可能有两个问题

• 死锁
• 饥饿

互斥

互斥的要求

1. 空闲让进: 若临界区空闲, 有进程申请就进入
2. 忙则等待: 每次只允许一个进程处于临界区
3. 有限等待: 保证进程有限时间内能进入临界区(不会死锁或饥饿)
4. 让权等待: 进程在临界区不能长时间阻塞等待某事件

互斥实现的软件方法

在进入区设置和检查一些标志来判断是否有进程在临界区

软件方法评价:

• 始终不能解决忙等现象, 降低系统效率
• 采用软件方法实现进程互斥使用临界资源比较困难, 两个容易但多个困难
• 算法设计需要非常小心, 否则可能出现死锁, 或互斥失败等严重问题

互斥实现的硬件方法

• 中断禁用
• 机器指令
  • compare & swap
  • Exchange

中断禁用(屏蔽中断)

用于单处理器系统

通过禁用中断, 避免进程切换, 实现互斥访问

缺点:

• 执行效率明显下降

  无法响应外部请求, 无法切换进程

• 无法在多处理器环境下工作

  不能实现互斥

专用机器指令

• 多处理器环境中, 几个处理器共享访问公共主存

• 处理器表现出一种对等关系, 不存在主从关系

• 处理器之间没有支持互斥的中断机制

• 处理器的设计者提出了一些机器指令, 用于保证两个动作的原子性

  如在一个周期中对一个存储器单元的读和写

  这些动作在一个指令周期中执行, 不会被打断和干扰

比较和交换指令 compare & swap （compare&exchange）

比较内存单元的值和一个测试, 若相等, 则发生交换

Exchange指令: 原子性地交换寄存器和内存的值

专用机器指令评价:

• 优点
  1. 支持多处理机
  2. 简单, 易证明
  3. 支持多临界区
• 缺点
  1. 忙等现象
  2. 可能饥饿
  3. 可能死锁

信号量

信号量实现进程互斥与同步的基本原理

• 两个或多个进程可以通过传递信号进行合作

  迫使进程在某个位置暂时停止执行(阻塞), 直到收到一个可以向前推进的信号(被唤醒)

• 信号量可视为一个值为整数的变量

• 信号量可以分为二元信号量(0或1), 计数信号量(非二元信号量/一般信号量), 都用队列来组织等待信号量的进程

只有以下三个操作可以检查或操作信号量

1. 信号量初始化为非负数
2. semWait(Wait或P)使信号量-1, 若值为负数, 则阻塞执行semWait(Wati或P)的进程
3. semSignal(Signal或V)使信号量+1, 若值$\leq$0, 则解除执行semWait(Wait或P)的进程的阻塞状态

根据组织方式不同, 可分为

• 强信号量: 进程以FIFO方式从队列里移除
  • 
• 弱信号量: 未规定阻塞进程从队列里移除的顺序

信号量的实现

• semWait和semSignal作为原语实现
• 任意时刻只能有一个进程用semWait和semSignal来操作控制信号量
• 可以通过硬件/固件实现, 或采用硬件指令支持来保证进程互斥使用semWait或semSignal操控信号量

信号量的count值可以解释为

• s.count$\geq$0, s.count表示执行semWati操作而不则色的进程数(或看做可用资源数), 这种情形信号量可支持同步与互斥
• s.count$\leq$0, s.count表示阻塞在s.queue队列上的进程数

经典同步问题有

1. 生产者/消费者问题
2. 理发师问题
3. 读/写者问题
4. 哲学家就餐问题

生产者与消费者问题

描述

• 一个或多个生产者产生数据并放入缓冲
• 消费者从缓冲中互斥取出数据
• 生产者或消费者互斥访问缓冲

需解决的同步问题

• 保证缓冲区满时, 生产者不会往缓冲区中增加数据
• 保证缓冲区空时, 消费者不能从缓冲区中取走数据

代码

应先申请资源信号量, 再申请互斥信号量, 顺序不能颠倒

同一个进程中的多个signal语句颠倒会使性能下降

同一个信号量的wait与signal操作, 可以出现在同一进程或不同进程中

对任何信号量的wait与signal操作必须配对

示例1分析

定义互斥信号量mutex

定义产品资源信号量orange, apple, 爸爸儿子因桔子的放入或取出而同步, 爸爸女儿因苹果的放入或取出而同步

设置空间资源信号量empty, 爸爸儿子女儿共享盘子

示例2分析

两个生产者和两个消费者被连接到大小为1的缓冲区上

设置资源信号量plate, 盘子是一互斥访问的空间资源

设置产品信号量apple, 爸爸女儿因为苹果的放入或取出而同步

设置产品信号量orange, 妈妈儿子因为桔子的放入与取出而同步

示例3分析

两个生产者和一个消费者被连接到大小为2的缓冲区上

设置空间资源信号量empty_apple, 盘子中是否可以放入苹果

设置空间资源信号量empty_orange, 盘子中是否可以放入桔子

设置产品资源信号量apple, 盘子中是否可以取出苹果

设置产品资源信号量orange, 盘子中是否可以取出桔子

示例4分析

一个生产者进程和两个消费者进程共享大小为1的缓冲区, 当且仅当缓冲为空时, 生产者进程负责加入数据, 当且仅当缓冲有数据时, 消费者读数据, 只有两个消费者都读取数据后, 生产者才能删除原有数据并继续生产下一个数据

一个生产者和两个消费者, 一幅画要给两个人看; 可看作一个生产者每次针对不同消费者生产两个数据

两个数据都被消费后才能继续生产

设置空间资源信号量empty_dad, 爸爸是否欣赏过

设置产品资源信号量full_dad, 爸爸是否可以欣赏

设置空间资源信号量empty_mom, 妈妈是否欣赏过

设置产品资源信号量full_mom, 妈妈是否可以欣赏

读者和写者问题

描述

• 多个进程访问一个共享数据区(可为文件, 内存空间, 寄存器)
• 读进程只能读, 写进程只能写
• 为数据库, 文件, 内存区及一组寄存器等的数据访问问题建立了一个通用模型
• 三个角色: 读进程, 写进程, 共享数据
• 三个条件: 同时读, 互斥写, 互斥读写

如何判断一个问题是生产者/消费者问题还是读者/写者问题

• 生产者/消费者问题: 数据消费后没有了

  读者/写者问题: 数据可以多次读

• 生产者/消费者问题: 消费者彼此互斥

  读者/写者问题: 读者可以同时读

• 生产者/消费者问题: 生产者/消费者间有互斥关系和同步关系

  读者/写者问题: 读者/写者之间有互斥关系

解决策略

• 读者优先
• 写者优先
• 公平读写

读者优先

若有读者正在读数据, 允许后面的读者读数据

只有所有读者退出 才允许写者写数据

可能导致写者饥饿

读者优先的变量设置

wsem: 互斥信号量, 用于Writers间互斥, Writers和Readers互斥

readcount: 统计同时读数据的Readers个数

x: 对变量readcount互斥算术操作

公平读写

写过程中, 若其他读者写者到来, 按到达顺序处理

公平读写的变量设置

wsem: 互斥信号量, 用于Writers间互斥, Reader互斥Writers

x: 对于变量readcount互斥算术操作

wrsem: 互斥信号量, 确定Writer, Reader请求顺序

在读者优先中, wsem只对第一个读者起阻塞作用, 后续读者不受影响, 为了爆照按照到达顺序处理, 公平优先方式设置wrsem, 读者/写者按到达顺序在wrsem上排队

写者优先

至少一个写者想写数据时, 不允许新的读者进入读数据

例如(队列尾)WWRRW(队列头), 让三个W进程能优先于R进程写数据

解决了写者饥饿问题, 降低了必发成都, 系统的并发性能比较差

写者优先的变量设置

rsem: 互斥信号量, 至少有一个写者申请写数据时互斥新的读者进入读数据

第一个写者受rsem影响, 一旦有第一个写者, 需写者不受rsem影响, 但是读者需要再rsem上排队

writecount: 用于控制rsem信号量

y: 对变量writecount互斥算术操作

写者优先的改进

添加z信号量, 作用:

• 在rsem上不允许建造读进程的长队列, 否则写进程将不能跳过这个队列
• 允许一个读进程在rsem上排队, 其他读进程在信号量z上排队

示例1

多个写者共享数据, 行人-写者, 桥-共享数据

s: 互斥信号量, 用于写者互斥

示例2

两组读者, 同一组内部可以同时读, 不同组之间互斥, 即只要有一组读者上桥, 同组读者优先于另一组读者

桥–共享数据

x: 互斥信号量, 用于两组读者的互斥

countR: 统计读者数目(同时在桥上的行人数目)

mutexR: 对变量countR互斥算术操作

示例3

读者优先问题

行人首先上桥的一方为读者, 另一方为写者

桥–共享数据

x: 互斥信号量, 用于读者互斥写者

countR: 统计读着数目(同一方向要过桥的行人数目)

mutexR: 对变量countR互斥算术操作

count: 位于独木桥上的行人数目

理发师睡觉问题

傻逼, 看不懂, 睡觉吧

管程

信号量可以高效的实现进程间互斥与同步, 但是信号量的PV操作可能分散在整个程序中, 使用难度高

管程是一个程序设计语言结构, 采用了集中式的进程同步方法, 提供了与信号量同样的功能, 但更易于控制

管程

• 管程定义了一个共享数据结构和并发程序能执行的一组操作, 这组操作能同步进程和改变管程中的数据
• 共享数据结构是对系统中共享资源的抽象
• 对该共享数据结构的操作定义为一组过程, 通过调用这些过程实现对共享资源的申请, 释放和其他操作

管程的组成 = 局部数据 + 过程 + 初始化序列

管程的特点

1. 局部数据变量只能被管程的过程访问, 任何外部过程都不能访问
2. 一个进程通过调用管程的一个过程进入管程
3. 任何时候, 只能有一个进程在管程中执行, 调用管程的任何其他进程都被阻塞

若一个正在管程中执行的进程必须阻塞, 可以释放管程供其他进程使用

如果管程内的数据结构代表了共享资源, 则通过管程提供了对资源的互斥访问机制

用管程实现进程同步

管程通过使用条件变量提供对进程同步的支持

条件变量包含在管程中, 只能在管程中访问

操作条件变量的两个函数

• cwait©, 在条件c上阻塞进程, 管程可供其他进程使用
• csignal©, 恢复在条件c上阻塞的进程, 若不存在阻塞进程, 则不操作
• 这里cwait和csignal作用于条件变量, 与作用于信号量的wait和signal不同

消息传递

进程交互时, 需要满足两个基本要求

• 同步: 为实现互斥, 进程间需要同步
• 通信: 为实现合作, 进程间需要交换信息

消息传递提供了上述两方面功能

通信原语

Send(destination, message)

Receive(source, message)

进程给指定的进程发消息, 进程通过接收原语receive接收消息, 接收原语中指明源进程和消息

消息格式

消息传递问题中的同步

只有发送进程发送消息, 接收进程才能收到消息

发送进程调用发送原语时

• 发送进程发送消息后, 要么阻塞直到这个消息被目标进程收到
• 要么不阻塞

一个进程调用接收原语时

• 若没有消息到达, 接收者要么阻塞等待, 要么放弃接收, 继续执行
• 若已经有消息到达, 则接收者接收消息并继续执行

消息的寻址方式

send和receive原语确定目标和原进程的方式有两类

• 直接寻址
• 间接寻址

直接寻址

Send原语包含目标进程的标识号

Receive原语有两种处理方式

• 显示的指明源进程: 对于处理并发进程的合作有效
• 不可能指定源进程: 如就打印机服务进程, 采用隐式寻址, 接收到消息时将源地址保存下来

间接寻址

1. 消息被发送到一个共享的数据结构, 该结构由暂存消息的队列构成
2. 队列也被称为信箱
3. 发送进程往信箱发送消息, 接收进程从信箱取走消息
4. 提供了对消息使用的灵活性

简介寻址发送者和接收者之间的关系

使用消息传递实现互斥

多个并发执行的发送进程和接受进程共享一个邮箱box, box初始状态仅包含一条"空消息"(好比进入临界区的令牌)

不阻塞发送, 阻塞接收

若邮箱中存在一条消息, 则允许一个进程进入临界区

若邮箱为空, 表明有一个进程位于临界区, 其他试图进入临界区的进程必须阻塞

只要保证邮箱中最多只有一条消息, 就能保证只允许一个进程进入临界区, 从而实现进程互斥使用临界资源

使用消息传递实现生产者/消费者问题

使用两个邮箱mayconsume和mayproduce, 大小均为capacity

Mayproduce

• 起初填满空消息(即允许生产的令牌)
• 该邮箱有消息, 生产者就可以生产
• 每次生产前取一条空消息, 之后生产数据, 并将数据作为消息发至mayconsume邮箱
• 消费者的每次消费使得该邮箱中的空消息数增加

Mayconsume

• 生产者产生的数据作为消息发送到该信箱(即允许消费的令牌)
• 只要该邮箱有数据消息, 消费者就可以消费
• 每次消费前, 取一条消息, 消费后, 向mayproduce发送一条空消息
• 生产者的每次生产使得该邮箱的消息数增加

第二章 进程管理4–死锁

死锁的原理

进程死锁现象: 进程P和Q共享资源

死锁: 一组相互竞争系统资源或进行通信的进程间的永久阻塞

当一组进程中的每个进程都在等待某事件, 而只有同组进程中阻塞的其他进程能够促发该事件时, 死锁发生

死锁是永久性的, 没有有效的解决方案

资源的分类

• 可重用资源

  依次仅供一个进程使用且不因使用而耗尽的资源

  如处理器, I/O通道, 内存和外存, 设备

• 可消耗资源

  可消耗资源是指可被创建(生产)和销毁(消耗)的资源

  如中断, 信号, 信息和I/O缓冲中的信息

竞争可重用资源, 可消耗资源都可能引起死锁

下面的资源分配图中, 存在环就存在死锁

死锁的条件

• 充分条件

  循环等待, 存在一闭合的进程链

• 必要条件

  1. 互斥, 同一时刻只有一个进程可以使用一个资源
  2. 占用且等待, 进程等待其他资源时, 继续占有已经分配的资源
  3. 不可抢占, 不能强行抢占进程已经占有的资源

死锁的解决

1. 死锁预防

   防止死锁产生条件的发生

2. 死锁避免

   允许三个必要条件, 根据当前资源分配状态来做出资源分配决策, 保证不产生死锁

3. 死锁检测与解除

   不限制资源访问或约束进程行为, 而是检测死锁的存在并尝试解除

死锁预防

两类方法

• 间接方法: 防止三个必要条件中的任意一个条件发生
  • 互斥: 互斥不能禁止
  • 防止占有且等待: 要求进程一次性请求所有资源, 阻塞进程直至所有资源能满足, 但有低效和事先不知道进程所需全部资源的问题
  • 防止不可抢占: 一个占有某些资源的进程进一步申请资源时若被拒绝, 则释放最初占有的资源; 或OS要求另一个进程释放资源. 只有在资源状态容易保存和恢复的情况下才实用
• 直接方法: 防止循环等待的发生
  • 定义请求资源的顺序, 把资源按类型进行线性排队, 所有进程对资源的请求必须严格按资源序号递增顺序提出. 这种方法低效

死锁避免

允许三个必要条件

动态检查

• 在系统运行过程中, 检查进程的资源申请, 根据检查结果决定是否分配资源
  • 若分配后系统可能死锁, 则不予分配, 阻塞进程
  • 否则予以分配
• 需要预知资源的请求

死锁避免的两种方法

• 资源分配拒绝
• 进程启动拒绝

进程启动拒绝

若一个进程请求会导致死锁, 则不启动该进程

资源分配拒绝, 又称银行家算法

若一个进程增加的资源请求会导致死锁, 则不会允许这一资源分配

系统的状态反映出当前给进程分配资源的情况

安全状态指至少有一个资源分配序列($P_x, P_y, \cdots, P_z$, 安全序列)不会导致死锁, 所有进程$P_x, P_y, \cdots, P_z$能够运行结束

安全状态与不安全状态的思考

安全序列是否唯一? 不是

安全状态是否一定没有死锁发生? 若系统处于安全状态, 且按照某个安全序列分配资源, 则不会出现死锁

并非所有不安全状态都是死锁状态(若某一进程提前释放了资源, 让其他进程可以使用资源, 后来再次需要这些资源, 系统就变成了安全状态)

当系统进入不安全状态后, 便可能进入死锁状态

避免死锁的实质在于: 如何避免系统进入不安全系统

死锁避免的优点

• 无须死锁预防中的抢占和回滚(释放最初占有的资源)
• 比起死锁预防, 限制少

死锁避免的使用限制

• 必须事先声明每个进程请求的最大资源
• 进程必须是独立的, 它们执行顺序没有同步的要求
• 分配资源的数量必须是固定的
• 占有资源时, 进程不能退出

死锁检测与解除

死锁检测

对死锁的检测可以频繁的发生在每次资源请求时, 也可以少检测, 具体取决于死锁发生的可能性

优缺点

• 优点

  1. 可尽早检测死锁
  2. 算法相对简单

• 缺点

  频繁的检测会耗费处理器相当多的时间

死锁检测算法步骤

1. 标记Allocation矩阵中一行全为零的进程
2. 初始化一个向量$W$, 令$W$等于Available向量
3. 查找下标$i$, 进程$i$当前未标记且满足$Q$($Q_{ij}$表示进程$i$请求$j$类资源的数量)的第$i$行小于等于$W$, 即对所有的$1\leq k\leq m, Q_{ik}\leq W_k$, 若找不到这样的行, 终止算法
4. 若找到这样的行, 标记进程$i$, 并把Allocation矩阵中的响应行加到$W$中, 即对所有$1\leq k\leq m$, 令$W_k = W_k + A_{ik}$, 返回3

当且仅当最终有未标记进程时, 才存在死锁, 未标记的进程都是死锁的

资源分配图进行死锁检测

资源分配图的化简:

1. 在图中找到全部请求都能满足的进程节点$P_i$, 消去$P_i$所有的请求边和分配边, 使之成为孤立的节点
2. 重复步骤1, 直至无法化简为止

示例

可完全化简图

• 能消去图中所有的边, 使所有进程节点都成为孤立结点的资源分配图
• 不可完全化简图存在死锁

死锁解除

检测死锁后, 按照某种可能的策略来解除

1. 撤销进程

   撤销死锁进程直至不再存在死锁

2. 回退

   把进程回退到前面定义的某些检查点, 并重新启动所有进程

3. 抢占

   连续抢占资源直至不再存在死锁

取消/抢占哪些进程的资源?选择原则:

• 消耗处理器时间少, 或输出少, 或分配资源少, 或剩余时间长, 或优先级最低的进程

哲学家就餐问题

描述: 5个哲学家围坐一张餐桌, 5只餐叉间隔摆放, 哲学家不是思考就是在进餐, 进餐时必须同时拿到两边的餐叉, 思考时将餐叉放回原处

资源分级方法一

• 为餐叉编号
• 就餐前, 先取编号较低的餐叉, 再取编号较高的餐叉
• 就餐完, 先放下编号较高的餐叉, 再放下编号较低的餐叉(也可不限制)

资源分级方法二

• 为哲学家编号
• 奇数号的哲学家必须先拿左边的餐叉
• 偶数号的哲学家必须先拿右边的餐叉

服务生方法

引入一个餐厅服务生, 哲学家必须经过他的允许才能拿起餐叉, 最多允许4个哲学家同时进食

哲学家就餐问题的引申: And型信号量集

在一个原语中申请需要的多个临界资源, 要么全部分, 要么一个都不分配

AND型信号量集P原语为Swait(S1, S2, …, Sn), V原语为Ssignal(S1, S2, …, Sn)

管程解决方案

内存管理1–基本

内存管理: 关注内存和外存之间的信息流的组织

程序的加载

高级语言源代码转化为进程的3个步骤

1. 编译

   编译程序将源代码编译为若干个目标模块

2. 链接

   链接程序将模块和他们所需要的库函数链接在一起, 形成一个完整的加载模块

3. 加载(装入)

   由加载程序将加载模块装入内存

加载的任务

• 将可加载模块装入内存

• 地址重定位

  将执行文件中的逻辑地址转化为内存物理地址的过程

加载方式分类(地址映射建立方式)

• 绝对加载方式
• 可重定位加载(静态重定位)方式
• 运行时加载(动态重定位)方式

绝对加载方式

程序中的逻辑地址与实际内存地址完全相同, 不需对程序和数据的地址修改

编译程序产生绝对地址的目标代码, 编译时就知道程序将驻留在内存中的具体位置

为了便于程序的修改, 对程序采用符号地址, 在编译时转化为绝对地址

优缺点

• 优点

  实现简单, 无须逻辑地址到物理地址的变换

• 缺点

  1. 程序每次必须装入同一内存区
  2. 程序员必须实现了解内存的使用情况, 根据内存情况确定程序的逻辑地址
  3. 不适用于多道程序系统

可重定位加载方式(静态重定位)

编译时采用相对地址, 即编译器假设是加载到从零开始的内存位置

逻辑地址与装入内存后的物理地址无直接关系

必须进行重定位, 即加载程序根据加载的位置将逻辑地址转换为物理地址

静态重定位技术: 地址映射在程序加载时进行, 以后不再更改程序地址

优缺点:

• 优点: 易实现, 无需硬件支持
• 缺点: 程序重定位后就不能移动, 因而不能重新分配内存, 不利于内存的有效利用

运行时加载(动态重定位)方式

程序地址转换在程序运行时动态进行

运行时动态加载需要硬件支持, 即重定位寄存器, 用于保存程序在内存中的起始地址

程序被执行时, 通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址

优缺点

• 优点
  1. 程序不必连续存放在内存中, 可分散存储, 可移动
  2. 便于共享
  3. 有利于紧凑, 碎片问题的解决
  4. 主流方式
• 缺点
  1. 需要硬件支持, 实现存储管理的软件算法比较复杂
  2. 同一地址, 可能多次转换

程序加载方法小结

• 绝对加载

  编译时执行: 编译时就知道进程将在内存中的驻留地址, 生成绝对代码. 在可执行文件中记录内存地址, 加载时直接定位在该内存地址

  如果将来开始地址发生变化, 就必须重新编译代码

• 静态重定位加载

  加载时执行, 静态地址重定位: 地址绑定在加载内存时才进行. 系统根据内存当时的使用情况, 决定将目标代码放在内存的什么位置

  不允许程序在内存中移动

• 不允许程序在内存中移动

  执行时执行, 动态地址重定位: 地址绑定延迟到执行时才进行

  支持执行时进程在内存中移动

程序的链接

链接

• 源程序经过编译后, 可得到一组目标模块
• 链接程序将这组目标模块链接, 产生一个包含完整程序和数据模块的加载模块

链接方式(链接的时机)

• 静态链接
• 加载时动态链接
• 运行时动态链接

静态链接

程序运行前, 先将各目标模块及它们所需的库函数, 链接成一个完整的装配模块, 以后不再拆开

静态链接需要解决两个问题

1. 相对地址的修改

   由编译程序产生的所有目标模块中, 使用的都是相对地址, 链接成一个加载模块时需要修改模块的相对地址

2. 变换外部引用地址

   每个模块中所用的外部调用符号也都变换为相对地址

缺点

• 不利于代码共享(每个应用都含有目标模块的拷贝)
• 不利于模块的独立升级(每次对某个目标模块的修改升级, 都要打开整个加载模块)
• 可能链接一些不会执行的模块, 浪费存储空间和处理机时间

加载时动态链接

在加载内存时, 如果待加载的模块中有到外部模块的引用, 加载程序将查找这些模块并加载内存, 并把这些引用修改为相对应用程序模块开始处的相对地址

优缺点

• 优点
  1. 便于各个模块的独立升级
  2. 便于实现模块的共享
• 缺点
  1. 可能链接一些不会执行的模块, 浪费存储时间和处理机时间
  2. 模块加载后不能移动位置

运行时动态链接

程序执行中需要某目标模块时, 由OS找到模块并将之加载内存, 随后把它链接到调用者模块上

优点

1. 凡是在执行过程中未用到的目标模块, 不会被调入内存和被链接到加载模块上, 加快了程序的加载过程, 节省了大量的内存空间
2. 支持分段系统

内存管理的需求

1. 重定位
2. 保护
3. 共享
4. 逻辑组织
5. 物理组织

重定位

为什么要有重定位?

1. 程序员事先不知道在某个程序执行期间会有其他哪些程序驻留在内存中
2. 把活动进程换入或换出内存, 进而使处理器的利用率最大化
3. 进程下次换入时若要放在相同区域, 会存在诸多困难

重定位–进程寻址的需求

1. OS需要知道进程控制信息, 栈和入口点位置
2. 处理器需要处理程序内部的内存访问, 处理跳转指令和数据访问指令的地址转换

保护

1. 进程以外的其他进程中的程序不能未经授权地访问(读或写)进程的内存单元
2. 程序在内存中的位置不可预测
3. 需要支持重定位和保护的机制, 处理器硬件需要有这个能力

共享

1. 多个进程正在执行同一程序时, 允许每个进程访问该程序的同一个副本, 这比每个进程有独立副本要有利
2. 需要支持重定位和共享的机制

逻辑组织

内存被组织称线性(或一维)地址空间

分段可以满足该需求

为什么程序按模块组织?

1. 可以独立编写和编译模块
2. 可以为不同的模块提供不同的保护级别(只读, 只执行)
3. 模块可以被多个进程共享, 与用户看待问题的方式一致

物理组织

在内存和外存间完成移动信息的任务应该交给OS而不是程序员, 因为

1. 不应让程序员负责管理内存
2. 可供程序和数据使用的内存可能不足
3. 程序员不知道可用空间的大小和位置
4. 覆盖允许不同的模块占用相同的存储空间, 但是编程耗时

内存分区

内存管理的主要操作是处理器把程序加载到内存中执行

内存管理包括虚拟内存的复杂方案

内存分区有基于分段和分页的两种基本技术

固定分区

分区数量固定

• 分区大小相等
• 分区大小不等

分区大小相等

存在问题

• 程序可能太大而不能放到一个分区中
• 内存的利用率非常低, 会产生很多内部碎片

分区大小不等

可以使内部碎片更小

固定分区的问题

1. 分区数量在系统生成阶段已经确定, 限制了系统活动进程的数量
2. 小作业不能有效地利用分区空间

动态分区

分区大小和数量不固定

分配与进程需求完全一致的闲散内存空间

外部碎片

• 动态分区方法在内存中产生越来越多的碎片
• 内存利用率下降

压缩(紧凑)

• 解决外部碎片问题的技术
• OS移动进程, 使进程占用的空间连续
• 所有空闲空间连成一片
• 紧凑费时, 浪费处理器时间

动态分区分配算法

1. 首次匹配
2. 下次匹配(循环匹配)
3. 最佳匹配
4. 最差匹配

首次匹配

从头扫描内存, 选择第一个可用块

要求空闲分区以地址递增的顺序链接, 从链首开始查找

评价

1. 简单, 快速
2. 为大作业分配大的内存空间创造条件
3. 内存前段出现很多小的空闲分区, 每次查找都要经过这些分区

循环匹配/下次匹配

从上一次放置的位置开始扫描内存, 选择下一个大小足够的可用块

空闲分区按地址从低到高排列

评价

1. 比首次匹配性能差, 常常在内存末尾分配空间, 导致空闲的分区分布均匀
2. 缺少大的空闲块, 需要更多次数紧凑

最佳匹配

选择空间大小与需求最接近的空闲块分配

空闲分区按容量大小从小到大链接

评价

1. 产生的外部碎片很小
2. 内存中形成很多小到无法满足任何分配需求的块
3. 需要频繁进行内存压缩

最差匹配

选择满足需求的最大空闲分区分配

空闲分区按容量从大到小链接

评价

1. 每次分配留下的空闲空间较大, 便于再次利用
2. 大的空间不容易保留, 对大作业不利

伙伴系统

固定分区方案限制了活跃进程的数量. 如果分区大小与进程大小不匹配, 内存空间的利用率很低

动态分区方案维护复杂, 引入了压缩的额外开销

折中方案: 伙伴系统

分配的空间可以视为$2^U$的块, 每次分配的块的大小为$2^K$, $L\leq K\leq U$, 且

• $2^L$ = 分配的最小块的大小
• $2^U$ = 分配的最大块的大小
• 通常, $2^U$是内存中整个可分配空间的大小

评价:

1. 较为合理的折中方案, 一定程度上克服了固定分区和动态分区的缺陷
2. 是并行程序分配和释放的一种有效方案
3. UNIX内核存储分配中使用了一种改进的伙伴系统

重定位

地址类型

• 逻辑地址: 与当前数据在内存中的物理分配无关的访问地址, 执行前要转换成物理地址
• 相对地址: 逻辑地址的特例, 相对于某些已知点的存储单元
• 物理地址: 内存中的实际地址

重定位的硬件支持

• 基地址寄存器: 存放作业的起始地址
• 界限寄存器: 存放作业界限地址

分页

将内存划分成大小固定且相等的块, 且块相对较小. 进程也划分成同样大小的块

页: 进程中的块

页框: 内存中的块

将进程的页装入内存的页框

分页的逻辑地址 = 页号 + 页内偏移量. 下面是32位机, 4KB/页的分页存储系统逻辑地址结构示意图

页表

• OS为每个进程维护一个页表
• 页表包括进程中每个页对应的页框位置
• 处理器需要知道如何访问当前进程的页表
• 处理器使用页表来生成一个物理地址

页表的存储

• 页表存放在内存
• PCB保存有页表的起始地址
• 页表寄存器存放当前运行进程的页表的起始地址

页号和页内地址的计算

对于某特定机器, 其地址结构是一定的. 若给定一个逻辑地址空间中的地址为A, 页面的大小为L, 则页号P和页内地址d可按下式:

示例:

分页的逻辑地址到物理地址的转换

分页存储管理的优缺点

• 优点
  1. 存在页内碎片, 但碎片相对较小, 内存利用率高
  2. 实现了离散分配
  3. 无外部碎片
• 缺点
  1. 需要专门的硬件支持, 尤其是快表
  2. 不支持动态链接, 不易实现共享

分段

一个程序可以划分成几个段, 段的长度可以不等, 每个段从0开始编址, 并占用一段连续的地址空间爱你, 有最大段长限制

分段类似动态分区, 分段使一个程序可以占据多个分区, 且不必联系, 消除了内部碎片

分页对用户透明, 分段对用户可见

分段是一种组织程序和数据更方便的手段, 程序员或编译器将程序和数据划分到不同的段. 为实现模块化程序设计, 程序和数据可能会进一步被划分成多个段

不便: 程序员或编译器需要清楚最大段长限制

逻辑地址 = 段号 + 段内偏移量

段表

段表: 记录逻辑段和物理段的对应情况

逻辑地址与物理地址的转换:

1. 提取段号: 逻辑地址最左侧的n位
2. 以段号为索引, 查找段表中该段的起始物理地址
3. 逻辑地址最右侧m位为偏移量, 偏移量与段长度比较, 若偏移量>段长, 则地址无效
4. 物理地址: 该段的起始物理地址 + 偏移量

分段逻辑地址转换为物理地址示例

分段存储管理的优点和缺点

• 优点
  1. 便于程序模块化设计
  2. 便于动态链接
  3. 便于保护和共享
  4. 无内部碎片
• 缺点
  1. 地址转换需要硬件的支持–段表寄存器
  2. 分段的最大尺寸收到主存可用空间的限制
  3. 有外部碎片

分页和分段的比较

1. 页是信息的物理单位, 分页的目的是实现离散分配, 减少内存的外部碎片, 提高内存利用率. 分页是系统管理的需要而不是用户的需要. 段是信息的逻辑单位, 它含有一组意义相对完整的信息, 分段的目的是为了满足用户的需要
2. 页的大小固定且由系统决定, 系统把逻辑地址划分为页号和页内地址两部分, 是由机器硬件实现的, 所以在系统中只能有一种大小的页面. 段的长度不固定, 决定于用户编写的程序, 通常由编译程序在对源程序进行编译时, 根据信息的性质来划分
3. 分页的作业地址空间是一维的, 即一个记忆符可以表示一个地址. 分段的作业地址空间是二维的, 段名和段内地址共同标识一个地址
4. 分页存储管理系统不易实现"共享", 不支持"运行时动态链接". 分段存储管理系统易于实现"共享"和"动态链接"

第三章 内存管理2–虚拟内存管理

虚拟内存的支持条件

• 分页或分段的硬件支持
• 操作系统必须有管理页或段在内存和辅存间移动的软件

虚拟内存术语

• 虚拟内存: 辅存可被看作主存的一部分来完成寻址. 程序使用的地址与内存物理存储的地址不同, 程序生成的地址会自动转换为物理地址. 虚拟存储的大小受计算机系统寻址机制和可用辅存容量的限制, 而不受主存实际大小限制
• 虚拟地址/逻辑地址: 在虚拟内存中分配给某一位置的地址, 使得该位置可被访问.
• 虚拟地址空间: 分配给进程的虚拟存储
• 地址空间爱你: 用于某进程的内存地址范围
• 实地址: 内存中存储位置的地址

硬件和控制结构

分页和分段内存管理的两个基本特征

• 进程中所有内存访问都是逻辑地址, 逻辑地址会动态地转换为物理地址
• 一个进程可划分为许多块(页和段), 在执行过程中, 这些块不需要连续地位于内存中

若上述特征存在, 则在一个进程执行过程中, 该进程不需要所有页或所有段都在内存中

进程的执行过程:

1. OS仅读取包含程序开始处的几个块进入内存
2. 任意时刻, 进程驻留在内存的部分–驻留集
3. 访问一个不在内存中的逻辑地址(称为内存失效), 产生一个中断
4. OS把被中断的进程置为阻塞状态
5. OS把该进程中包含引发内存失效的部分读入内存
   • OS产生一个磁盘I/O读请求
   • 在执行磁盘I/O期间, OS调度另外一个进程运行
   • 磁盘I/O完成后产生中断, OS将相应的进程置于就绪状态

提高系统利用率的方法:

1. 内存中保留多个进程
   • 每个进程仅装入部分块
   • 任何时刻内存中的进程至少有一个处于就绪状态
   • 提高了处理器的利用率
2. 进程可以比内存的全部空间还大
   • 基于分页和分段的技术, OS和硬件只加载程序的一部分
   • 程序员面对的是一个巨大内存, 大小与磁盘存储器相关

实存储器(实存) – 主存, 实际的物理内存

虚拟内存(虚存) – 感觉更大的内存, 且常分配在磁盘上; 更有效地支持并发, 减轻用户对内存的严格限制

使用和不适用虚存技术下分页或分段的特点

局部性和虚拟内存

抖动: 即将要用到的块被换出, 系统又得很快将它取回, 导致页面被频繁地换入换出, 缺页率急剧增加

内存空间几乎被进程快占据时, 如果出现抖动, 则处理器的大部分时间都用于交换而非执行指令. 为了避免这种情况, OS根据最近的历史来猜测将来最可能用到的块

局部性原理:

• 存储器的访问呈簇性(簇: 一组程序或数据的集合), 在很长一段时间内, 使用的簇会发生变化; 在很短的时间内, 处理器与固定的簇接触)
• 局部性原理描述了程序和数据引用的集簇倾向, 在很短时间内进需要一部分块, 对将来访问的块可以猜测, 避免抖动
• 局部性原理说明虚存方案是可行的

分页

虚拟内存常与分页系统联系在一起

收个使用分页实现虚拟存储的Atlas计算机

每个进程都有自己的页表

• 分页的虚存方案中, 页表项变得更复杂

页表项

存在位P: 表明对应的页是否在内存

页框号: 若页在内存, 则有对应的页框号

修改位M: 表明相应页上次装入内存到现在是否修改过

• 若修改过, 换出时要更新辅存上对应页
• 若没有若改过, 换出时不必更新

分页系统中的地址转换

• 页表位于内存
• 进程运行时, 一个寄存器保存页表的起始地址
• 虚拟地址的页号用于检索页表, 查找对应页框号

庞大的页表组织

每个进程一个页表, 如果进程的逻辑地址空间大, 则页表庞大

大多数虚拟内存在虚存而非内存中保存页表

• 分页和其他页一样服从分页管理
• 进程运行时, 它的页表至少一部分在内存, 这部分包含正在运行页的页表项

庞大页表的离散存储解决方案 – 多级页表

两级页表

• 页表分页, 典型情况喜爱每页大小最大限制和进程分页大小一致
• 建立页目录, 每项指向一页页表
• 页目录长度X, 页表项数Y, 则一个进程可以有XY页

32位地址的两级页表

两级分页的逻辑地址结构: 页表页号(页目录号) + 页号 + 页内偏移地址

两级分页中的地址转换

虚拟地址(逻辑地址)结构中分离出根页表号

检索根页表, 查找关于用户页的页表项

• 如果不在内存产生一次缺页中断
• 若在内存, 用虚拟地址中间页号就按所用户页表, 查找对应的页表项

得到页框号, 和页内偏移量一起形成物理地址

多级页表

对某些机器, 二级页表也可能很大

• 采用多级页表, 对外层页表再进行分页

建立多级页表

• 会增加额外的存储空间
• 页表的级数越多, 地址转换过程越复杂, 转换的速度也越慢

倒置页表

• 虚拟地址的页号部分用一个简单的散列函数映射到散列表中

  哈希值指向倒排页表

• 无论有多少进程, 支持多少虚拟页, 页表都只需要实存中的一个固定部分

• 页表结构称为"倒排"的原因: 使用页框号而非虚拟页号来索引页表项

倒置页表结构

页号 + 进程标志符 + 控制位 + 链指针

进程标志符指出使用该页的进程, 控制位作标记如有效, 访问与修改, 保护与锁定, 链指针为下一项的索引值

转换检测缓冲区TLB(translation lookaside buffer 快表)

每次虚存访问都可能会引起两次物理地址访问

• 一次取相应的页表项
• 另一次取需要的数据

为了克服这个问题, 大多数虚拟内存文案都为页表项使用了一个特殊的高速缓存, 称为转换检测缓冲区TLB(快表), TLB包含最近用过的页表项

具有快表的地址转换流程

• 给定一个虚拟地址, 处理器首先检查TLB
• 若命中: 即页表项在TLB中, 检索页框号形成物理地址
• 若未命中: 即页表项不在TLB中, 检索进程页表, 查找相应页表项
  • 若"存在位"已置位, 页位于内存, 用页框号+偏移量形成物理地址
  • 若"存在位"未置位, 页不在内存, 产生缺页中断, 装入所需页, 更新页表

具有快表的地址转换流程图

页表项的直接查找和关联查找(TLB查找)

• TLB包含整个页表中的部分表项, 必须包括页号和完整的页表项, 所以不能简单地将页号编入TLB的索引
• 处理器的硬件机制允许同时查询许多TLB页, 以确定是否存在匹配的页号

TLB操作和内存高速缓存(Cache)操作

单词访问内存设计CPU硬件的复杂性

• 页表项可能在TLB, 也可能在内存或磁盘中
• 被访问的字可能在高速缓存中, 也可能在内存或磁盘中

页尺寸

• 页越小, 内部碎片的总量越少, 每个进程需要的页的数量越多
• 页数量越多, 进程的页表越大
• 页数量越多, 进程的页表越大
• 多道程序设计环境中的大程序, 意味着活动进程有一部分页表在虚存而非内存, 则一次内存访问可能产生两次缺页中断
  • 依次读取所需页表
  • 依次读取进程页
• 基于辅存设备的物理特性, 希望页尺寸比较大, 从而实现更有效的数据传输

缺页率

缺页率: 发生缺页的次数与总访问次数的比值

缺页率与页尺寸的关系

• 页尺寸很小时, 缺页率低. 每个进程由较多数量的页, 内存中的页都包含有最近访问的部分
• 页尺寸增加时, 缺页率增加 页尺寸增加时, 每页包含的单元和最近访问过的单元变远, 局部性原理的影响被削弱
• 页尺寸较大时, 缺页率下降 页尺寸接近整个进程的大小时, 一页包含整个进程不会发生缺页中断

缺页率与分配页框数的关系

• 对固定的页尺寸, 当分配给进程的页框数增加时, 缺页率下降

大型程序中所用的当代程序设计技术可能降低程序的局部性, 解决方法

• 面向对象技术: 对小程序和数据的引用会分散在不同的对象中
• 多线程应用: 指令流突然变化, 引用分散在内存中

分段

允许程序员把内存视作由多个地址空间或段组成

段大小不等, 可以动态变化

内存访问时, 短号+ 段内偏移量

分段优点

1. 简化了对不断增长的数据结构的处理
2. 允许程序独立地改变或重新编译
3. 有助于进程间的共享
4. 有助于保护

段的组织

每个进程一个段表, 每个段表项包括

• 存在位P, 标识响应的段是否位于内存

  是, 段表项还包括

  • 段基址:相应段在内存中的起始地址
  • 段长度

• 修改位M, 标识相应的段是否被修改

  • 是, 换出时写回辅存
  • 否, 换出时不需写回

• 其他控制位, 如用于保护和共享

分段系统中的地址转换

• 逻辑地址 = 段号 + 段内偏移量, 寄存器存储段表地址
• 物理地址 = 基地址 + 段内偏移量

段页式

用户的地址空间划分成许多段, 每段划分为许多固定大小的页

• 分段对程序员可见

  支持数据结构增长:段长可变

  支持共享和保护

• 分页对程序员透明

  消除外部碎片

  有效利用内存

段页式的逻辑地址

程序员角度: 逻辑地址 = 段号 + 段内偏移量

系统角度: 段内偏移量 = 页号 + 页号偏移量

段表和页表

每个进程一个段表

每个段一个页表

段表项: 含段长和对应页表的起始地址

页表项:含页框号, 存在位P, 修改位M等

段页式的地址转换

虚拟地址/逻辑地址 = 段号 + 页号 + 偏移量, 寄存器存放段表起始地址

根据段表起始地址和段号查找段表, 得到对应段的页表起始地址

根据页表起始地址和页号查找页表, 得到页框号

页框号和偏移量构成物理地址

段页式系统中, 获取一条指令或数据, 至少要访问三次内存

1. 访问段表, 从中获得该段的页表首址
2. 访问页表, 从中取出逻辑地址指定的页面所在页框号
3. 根据物理地址, 取出对应存储单元的指令或数据

保护与共享

分段有助于实现保护和共享机制

保护: 每个段都包括一个长度和基地址, 可以控制非法访问

共享: 一个段可以在多个进程的段表中被引用, 实现共享

分段有助于实现共享

• 分页: 假定每个页面4KB, 160KB的共享代码需要40个页面, 每个进程需要40个页表项来存储相应信息
• 
• 分段: 共享部分作为一个段, 每个进程仅需一个段表项来存放共享段信息
• 

段间保护关系: 每个段表项包括一个长度和一个基地址, 程序不会不经意地超过该段的内存单元 – 段结构对程序员可见

操作系统软件

内存管理设计的三个基本选择:

1. 是否使用虚拟技术

2. 分页, 分段还是段页式

3. 为各种存储管理特征采用的算法

   术语OS软件领域的问题, 是本节的主题

为实现虚拟内存, OS需要考虑的软件策略

1. 读取策略

   • 请求调页
   • 预调页

2. 放置策略

   预留在内存中的位置

3. 置换策略

   基本算法

   • 最优OPT
   • 最近最少使用LRU
   • 先进先出FIFO
   • 时钟CLOCK

   页缓冲

4. 驻留集管理

   驻留集大小

   • 固定
   • 可变

   置换范围

   • 全局
   • 局部

5. 清除策略

   • 请求式清除
   • 预约式清除

6. 负载控制

   多道程序度(系统并发度)

读取策略

• 请求调页
• 预调页

请求调页

仅在引用页面时, 才把相应的页面调入内存

进程首次启动时, 会发生很多缺页中断

局部性原则表明, 大多数将来访问的页面都是最近读取的页面, 一段时间后, 缺页中断会降低到很低的水平

预调页

额外读取所缺页面以外的页面

考虑辅存设备的特性: 寻道, 旋转延迟

若进程的页面连续存储在辅存中, 则一次读取多个页面会更有效

若额外读取的页面未使用, 则低效

放置策略

确定进程驻留在内存中的位置

分段系统中的重要设计内容, 如首次匹配和循环匹配

硬件以相同的效率执行地址转换功能, 所以分页或段内分页是无关紧要的

对于非一致性存储访问, 需要自动放置策略

置换策略

页面置换设计的问题:具体淘汰哪个页面用以置换

置换策略

• 读取新页时, 如何选择内存要淘汰的页面

  目标: 最近最不可能访问的页面

• 置换策略越精细, 硬件和软件开销越大

页框锁定

• 页框锁定时, 当前存储在该页框中的页面不能被置换
• OS内核和重要的数据结构保存在锁定的页框中
• I/O缓冲区和时间要求严格的区域也可能保存在锁定的页框中
• 通过将锁定位与每个页框相关联来实现锁定

几种基本的置换算法

1. 最佳OPT Optimal
2. 最近最少使用LRU Least recently used
3. 先进先出FIFO Firsr-in-first-out
4. 时钟CLOCK

评价置换算法的指标 – 缺页率: 给定时间内, 发生缺页的次数与访问总次数的比值

最佳OPT

置换下次访问句当前时间最长的页面

理想算法, 缺页率最少

由于奥球OS必须知道将来的事件, 因此不可能实现

F表示产生缺页中断

最近最少使用LRU

置换内存中最长时间未引用的的页面

根据局部性原理, 这也是最近最不可能访问的页面

难以实施

• 每页添加最近访问时间戳 – 开销大
• 建立链表 – 开销大

先进先出FIFIO

将分配给进程的页框视为循环缓冲区

页面以循环方式删除 – 简单的置换策略

置换驻留在内存中时间最长的页面

时钟CLOCK

每个页框关联一个使用位U(也称访问位)

页面首次加载到内存中或被引用时, 使用位U设置为1

用于置换的候选页框视作一个循环缓冲区

发生缺页中断时

• 检查表针指向页面, 若使用位为0, 则新页面替换之
• 如果使用位为1, 则清0, 表针前移一个位置
• 重复以上过程

注意: 命中时, 表针不移动

几种置换算法的比较(固定分配, 局部置换)

改进的CLOCK算法

在CLOCK算法基础上, 优先置换最近未访问, 未修改的页面

每个页框处于下列情形之一(u:使用位/访问位, m:修改位)

1. u=0, m=0: 最近未被访问, 又未被修改, 最佳淘汰页
2. u=0, m=1
3. u=1, m=0
4. u=1, m=1

算法流程

1. 从指针当前位置开始扫描, 这次扫描对使用位不修改, 选择遇到的第一个u=0, m=0页框置换
2. 若第1步事变, 重新扫描, 选择遇到的第一个u=0, m=1的页框置换. 这一过程中, 使每个扫描过的页框u置0
3. 若第2步失败, 重新扫描重复1

页缓冲

置换的页, 如果要写回辅存, 代价较大

在内存中使用页缓冲, 提高分页性能, 允许使用更简单的页面替换策略

置换的页面仍在内存中

• 未修改, 放入空闲页链表尾部
• 已修改, 放入修改页链表尾部

置换策略和高速缓存大小

若选择替换的页在高速缓存中, 则该高速缓存块和内存中对应的页将失效

在使用页缓冲的系统重, 可以使用页缓冲区中的页放置策略来提高高速缓存性能

大多数OS通过从页缓冲区中选择任意页框来放置高速缓存中需置换的页

驻留集管理

页框分配, 即给每个活动分配多少页框

• 分配给每个进程的内存越小, 可以驻留在内存中的进程越多
• 若一个进程在内存中的页面少, 则缺页率相对较高
• 给进程分配的页框数超出一定大小后, 由于局部性原理, 缺页率下降到稳定水平

置换范围, 即计划置换的页集局限于产生缺页的进程本身, 还是内存内的所有进程

• 局部置换: 仅在缺页中断的进程的驻留页中选择置换对象
• 全局置换: 在整个内存中选择置换对象, 只要不是锁定的页, 都可以作为候选页

页框分配策略

• 固定分配: 在内存中为进程提供固定数量的页框

  发生缺页时, 必须替换该进程的其中一个页面

• 可变分配

  允许分配给进程的页框数在进程的生命周期内变化

固定分配, 局部置换

事先确定分配给一个进程的页框数量

如果进程分配的数量太少, 产生较高缺页率

如果分配的页框数太多, 内存中只能有较少的程序

• 增加了处理器的空闲时间
• 增加了交换的时间

可变分配, 全局置换

最容易实现的方法, 在很多OS中使用

OS维护一个空闲页框列表

缺页中断发生时, 一个空闲页框分配给缺页的进程

若没有空闲页框, OS选择一个内存中的页框(未被锁定, 没有被内核占用)作为置换对象

选择置换对象不当, 容易再次产生缺页中断, 使用页缓冲可以缓解问题

可变分配, 局部置换

新进程装入内存时, 分配一定页框作为驻留集

缺页中断发生时, 从进程驻留集中选择一页用于置换

不时重新评估进程的页框分配情况, 增加或减少分配的页框

关键要素

• 决定驻留集大小的原则
• 驻留集大小变化的时机

工作集

• 一个进程在某一段时间内访问页面的集合。
• 如果页面正在使用，它就落在工作集中；
• 如果不再使用，它将不出现在相应的工作集中，所以，工作集是程序局部性的近似表示。
• 工作集避免抖动方法
  • OS监视每个进程的工作集
    • 新增页面分配内存。
    • 淘汰不在工作集中的页面。
  • 若有足够多的额外内存块，就可装入另一个进程。
  • 如果所有工作集之和超过了可用内存，则OS选择挂起一个进程，把它的页换出，将其内存块分配给其它进程。
  • 工作集的估算不容易：Δ

平均访问时间/平均有效访问时间

若缺页率为p, 内存访问时间为ma, 发生缺页时的访问时间为da, 则平均访问时间 = (1-p)*ma + p*da

发生缺页时访问时间的构成:

• 缺页中断服务时间
• 页面写出时间(若需置换)
• 页面调入时间 – 20ms(寻道时间 + 旋转时间 + 数据传送时间)
• 重新访问内存指令时间

由于ma很小(<10ns), 因此很低的缺页率也会导致很大的平均访问时间

第四章 I/O管理与磁盘调度

I/O控制方式

• 程序I/O方式
• 中断驱动I/O方式
• 直接存储器访问(DMA)方式

I/O通道控制方式

一个设备可以连接到多个控制上, 而一个控制器又连接到多个通道上

操作系统的设计问题

I/O缓冲

选填专题

第一章 绪论

计算机系统结构

1. 硬件
2. 操作系统
3. 系统程序
4. 应用程序
5. 用户

OS的目标: 方便性, 有效性, 扩展性, 开放性

第二章 进程1–描述

操作系统的基本特征 并发性 共享性 异步性(不确定性) 虚拟性

进程是资源申请和系统调度的基本单位

阻塞状态/等待状态: 进程因等待某种事件的发生而暂时不能继续运行的状态

操作系统内核: 操作系统中包含重要系统功能的部分

操作系统内核功能

1. 资源管理功能
   • 进程管理
   • 存储管理
   • I/O设备管理
2. 支撑功能
   • 中断处理
   • 时钟管理
   • 记账(统计, 监测)功能

进程控制块PCB – 进程存在的唯一标识, 常驻内存, 是一个数据结构

PCB包含三类信息

1. 进程标识符: 唯一地标识一个进程
2. 处理机状态信息: 由处理器的各种寄存器中的内容组成的
3. 进程控制信息: 与进程调度和进程切换有关的信息

进程的组成

• 程序
• 数据, 如变量, 工作空间, 缓冲区
• 执行上下文
  • 进程状态
  • OS管理和控制进程所需的所有数据
  • 如处理器寄存器的内容, 进程优先级, 是否在等待I/O事件, 在内存中的位置
  • 进程需要数据结构来保存进程的上下文环境

执行模式包括内核/系统/控制模式和用户模式

内核态和用户态, 阻塞态和就绪态, 是两套独立描述进程的东西, 一个是进程状态, 一个是执行模式

进程切换必然导致模式切换, 模式切换不一定伴随进程切换

进程的创建

1. 申请空白PCB
2. 为新进程分配资源(内存, 文件)
3. 初始化PCB数据结构
4. 将新进程插入就绪队列

进程的终止

1. 检索PCB, 检查进程状态
2. 若为执行态, 则中止, 调度下一个就绪进程执行
3. 若有子孙, 则终止子孙
4. 归还资源给父进程或系统
5. 从PCB队列中移出PCB

何时发生进程切换

1. 时钟中断
2. I/O中断
3. 内存失效
4. 陷阱
5. 系统调用(与用户/内核模式切换的区别)

子进程是父进程的精确复制

进程的两个基本属性 拥有资源的独立单位和调度/执行的基本单位

进程是拥有资源和独立运行的基本单位

线程是系统独立调度和分派的单位

调度类型

1. 长程调度

   新建任务, 外存作业调入内存

2. 中程调度

   内外存对换, 进程挂起

3. 短程调度

   就绪队列中哪个进程执行

调度的评价准则

• 面向用户准则
  1. 响应时间: 提交到系统首次响应
  2. 周转时间: 提交到系统完成
     • 平均周转时间
     • 带权周转时间
     • 平均带权周转时间
  3. 截止时间: 必须开始执行的最迟时间
• 面向系统准则
  1. 处理机利用率
  2. 系统吞吐量: 单位时间内, 系统完成的作业数
  3. 公平性
  4. 优先权
  5. 资源平衡利用

第二章 进程3–同步

同步原则

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待: 在临界区不能长时间阻塞等待某事件

生产者/消费者问题, 要先申请资源, 再申请访问权

第二章 进程4–死锁

产生死锁的原因

1. 资源不足导致的资源竞争
2. 并发执行的顺序不当

死锁的四个必要条件

1. 互斥
2. 占有且等待
3. 非抢占
4. 循环等待(充要条件)

进程回退:把死锁进程备份到前面定义的某些检查点, 并且重新启动所有进程 - 需要系统构造重新运行和重新启动机制

第三章 内存1–基本

存储管理的基本功能

1. 存储分配和回收
2. 地址变换
3. 存储保护
4. 存储共享
5. 存储器扩充

高级语言的源代码转化为进程的三个基本步骤

1. 编译: 编译程序将用户源代码编译成若干个目标模块
2. 链接: 由链接程序将编译后形成的一组目标模块, 以及所需库函数链接在一起, 形成一个完整的装入模块
3. 装入: 由装入程序将装入模块装入物理内存

程序的链接

1. 静态链接

   需要修改相对地址, 变换外部调用符号

2. 动态链接

   • 装入时动态链接
   • 运行时动态链接

装入方式(程序加载)

1. 绝对装入方式
2. 重定位装入
3. 运行时装入

重定位: 在装入时对目标程序中指令和数据的变换过程称为重定位

连续分配

1. 单一连续分配
2. 固定分区分配
3. 动态分区分配
4. 可重定位分区分配

覆盖: 一个程序的几个代码段或数据段, 按照时间先后占用公共的内存空间

页表: 实现逻辑页号到物理块号的映射

每个进程拥有一个页表/页表, 其信息(如长度, 开始地址)放在PCB中, 执行时页表始址和页表长度装入页表寄存器

页表在内存, 属于进程的内核信息

分段式便于

1. 编写程序
2. 分段共享
3. 分段保护
4. 动态链接
5. 动态增长

含有快表的平均访存时间, 下面n代表n级页表

$平均访存时间 = TLB命中率 * (TLB访问时间 + 1次访存时间) + (1-TLB命中率) * (TLB访问时间 + n次页表访问时间 + 1次访存时间)$

第三章 内存2–虚拟内存

局部性原理:

• 时间局限性: 程序中存在着大量的循环操作
• 空间局限性: 以单纯恒旭访问了某个存储单元, 不久后附近的存储单元也将被访问

请求分页存储管理方式, 请求分页中的硬件支持需要

1. 一台具有一定容量内存和外存的计算机系统
2. 页表机制
3. 缺页中断机构
4. 地址变换机构

内存分配的分配策略(指如何给程序分占用的物理块块数): 固定分配, 可变分配

内存分配的置换策略(逻辑上发现缺页, 从哪里寻找物理块): 全局置换, 局部置换

分配策略和置换策略可以组合出三种策略

1. 固定分配局部置换
2. 可变分配全局置换
3. 可变分配局部置换

内存分配的分配算法: 平均分配, 按程序大小比例分配, 按优先级分配

页面置换算法

1. OPT最优置换算法
2. FIFO先进先出算法
3. LRU最近最久未使用算法
4. CLOCK算法

抖动的现象

1. 页面被频繁地换入换出, 缺页率急剧增加
2. 页面有效存取时间加长
3. 系统吞吐量骤减

抖动的根本原因: 多道程序度过高, 每个进程分配的页框数目过少

抖动的预防

1. 采用局部置换策略
2. CPU调度程序中运用工作集算法
3. L=S准则, 发生缺页的平均时间L = 处理缺页故障的平均时间S
4. 挂起若干进程

工作集: 一个进程在某短时间内访问页面的集合, 工作集是程序局部性的近似表示

工作集避免抖动方法

1. OS监视每个进程的工作集
2. 若有足够多的内存块, 可装入另一个进程
3. 若所有工作集之和超过了可用内存, OS选择挂起一个进程, 换出页, 将其内存块分配给其他进程
4. 工作集的估算不容易

虚拟存储器的特征

1. 多次性, 多次调入内存运行
2. 对换性, 运行中存在换进换出
3. 虚拟性, 逻辑上扩充内存容量

第四章 设备

各类I/O设备在数据传输速率, 用途, 控制接口复杂性, 传输单元(字节流, 块), 数据编码方式, 错误等方面都存在差异

四种执行I/O的技术

1. 程序控制I/O
2. 中断驱动I/O
3. 直接内存访问DMA: 允许外设绕过CPU直接修改内存的一种带中断的技术
4. I/O通道方式

中断驱动I/O方式不适用于块设备: 过于频繁的中断

I/O通道控制方式, 通道是一个独立于CPU的专管I/O控制的处理机, 有自己的通道指令集,通过通道程序控制I/O, 以一个数据块为单位的读写, 改进为一组数据块为单位的读写

设备管理中, 引入缓冲区的主要原因

1. 缓和CPU与I/O设备速度不匹配的矛盾
2. 减少对CPU的中断频率, 放宽对CPU中断响应时间的限制
3. 提高CPU和I/O设备间的并行性

为了避免死锁和丢失数据等问题, 一些进程和虚拟地址单元被锁定在内存中, 直到I/O执行结束. 为避免这些开销和低效的操作, 提出缓冲技术

缓冲:

1. 在输入请求发出前开始输入传送
2. 输出请求发出后一段时间后才开始执行输出传送

为了实现双向数据传输, 必须在两台机器中都设置两个缓冲区, 一个用作发送缓冲区, 一个用作接收缓冲区

缓冲的作用: 缓解I/O设备速度与CPU速度不匹配的矛盾

SPOOLing: 在联机情况下实现的同时外围操作, 或称假脱机操作

SPOOLing系统的特点

1. 提高I/O速度
2. 将独占设备改造成共享设备
3. 实现了虚拟设备功能

SPOOLing的I/O缓冲区建立在磁盘中, 将一台独占I/O的物理设备虚拟为多台逻辑I/O设备, 实现设备共享. 通过将对低速I/O设备的操作转化为对输入/输出井中数据的存取, 缓和了CPU与低速I/O设备间速度不匹配的问题

设备的硬件层次结构

1. 用户层软件
2. 设备独立性软件
3. 设备驱动程序
4. 中断处理程序
5. 硬件

磁盘管理:

• 存储面: 每个磁片分一个或两个存储面
• 磁道: 每个磁盘面被组织成若干个同心环
• 扇区: 每条磁道逻辑上划分成若干个扇区
• 柱面: 不同盘面相同的磁道称为柱面
• 读写头: 分为固定头和移动头

磁盘调度的目的: 减少寻道时间

磁盘调度

1. 先进先出-FIFO
2. 优先级-PRI
3. 后进先出-LIFO
4. 最短寻道时间优先-SSTF
5. 扫描-SCAN(电梯调度算法), 掉头条件改为"前方没有要处理的其他请求"称为LOOK
6. 循环扫描-C-SCAN, 单向扫描
7. N步SCAN, 请求队列分成N个子队列, 依次处理
8. FSCAN, 两个子队列, 新请求放在另一个

磁盘高速缓存: 内存中为磁盘扇区设置的一个缓冲区, 包含磁盘中某些扇区的副本

磁盘高速缓存的两种置换策略

1. 最近最少使用算法-LRU
2. 最不常使用算法-LFU

DMA的寄存器包括命令/状态寄存器, 内存地址寄存器, 数据寄存器

第五章 文件

文件: 一种具有符号名的, 相关联元素的有序集合

文件是信息在磁盘上存储的基本逻辑单位

文件 = 元数据 + 内容数据, 元数据记录的是文件属性如文件名拥有者访问权限文件大小

文件系统管理的对象: 文件(直接对象), 目录, 磁盘存储空间

文件系统的实现模型: "文件系统接口-逻辑功能层-物理驱动层`"三层组成

文件系统的主要目的: 实现对文件的按名存取

文件结构

• 逻辑结构: 用户角度研究文件的组织形式
  • 流式文件(非结构化文件), 如txt, 以字节为基本组成单位
  • 记录文件(结构化文件), 按记录的组织形式又分类为
    1. 堆文件, 按记录到达的时间先后顺序存储
    2. 顺序文件, 记录长度固定, 各域含义固定, 记录按"关键域"有序排列
    3. 索引顺序文件, 是一个顺序文件, 每组一个索引而不是每条记录一个索引, 添加索引表和溢出文件, 组与组间记录的关键字必须有序排列.插入记录时放在溢出文件中, 批处理方式合并溢出文件
    4. 索引文件, 解决了顺序文件对非关键域查找困难的问题
    5. 哈希(直接)文件: 适用于快速访问, 记录定长, 每次只访问一个记录的场景
• 物理结构

辅存管理

1. 文件分配
2. 辅存中的空闲空间管理

记录组块方式

1. 定长组块
2. 变长跨越式组块
3. 变长非跨越式组块

文件组织形式

1. 堆文件
2. 顺序文件
3. 索引顺序文件
4. 索引文件
5. 直接文件/散列文件/哈希文件

文件目录是文件目录项的有序集合

文件分配方式(物理结构), 分配内存时的方式

1. 连续分配
2. 链式分配
3. 索引分配

空闲空间管理方法

1. 空闲表法
2. 空闲链表法
3. 位示图法
4. 成组链接法

位示图占用的存储空间大小 = 磁盘容量(字节数) / (8 * 数据块大小)

FCB: 描述和控制文件的数据结构, 与文件一一对应, 是文件存在的标志, 包括以下信息

1. 文件名
2. 文件物理位置
3. 存取信息: 创建时间, 读写访问时间

文件的元数据在目录项和inode中, incode缺少文件名

目录结构包括: 单级目录, 两级目录, 层次结构

文件共享包括两个方面用户共享和实体共享

用户共享会遇到访问权限和并发控制的问题

实体共享在Unix系统上通过链接实现.

• 硬链接: 多个文件名链接到同一个索引结点
• 软链接: 建立一个独立于源文件的符号链接文件

区分重要算法

进程调度

• 抢占算法的抢占时机
• FCFS/ SJF/ SRT/ HRRN/ RR

页面替换

• OPT/ FIFO/ LRU/ CLOCK

磁盘调度

• FCFS/ SSTF
• SCAN/ LOOK/ CSCAN/ CLOOK

内存分配(动态分区)

• 空闲分区组织方式
• First Fit/ Next First Fit/ Best Fit/ Worst Fit

$$