os_进程

第一章 导论

操作系统简介

• 操作系统的目的

  • 运行用户程序 核心目标
  • 更方便使用计算机 面向用户
  • 更高效使用计算机 面向系统

• 系统操作

  • 每个设备控制器有一个本地缓冲
  • CPU在内存和本地缓冲之间传输数据
  • I/O控制器在设备和本地缓冲之间传输数据
  • 控制器通过调用中断通知CPU完成操作

• 中断

  • 中断 ：指当出现需要时 CPU 暂时停止当前程序的执行，转而执行处理新情况的程序和执行过程
  • 中断号 ：外部设备进行 I/O 操作时产生的中断信号，发送给 CPU
  • 中断向量 ：中断服务程序的入口地址
  • 中断服务程序 ：执行中断处理的代码
  • 操作系统是中断驱动

批处理系统

• 批处理

  • 用户将一批作业提交操作系统后就不再干预，由操作系统控制它们自动运行

• 批处理操作系统

  • 采用批量处理作业技术的操作系统

  • 自动作业调度

    • 自动从一个运行完的作业转换到下一个作业

  • 常驻监控程序

    • 控制作业传输
    • 调度作业运行
  • 单道程序设计
  • 不具有交互性
  • 提高CPU的利用率

多道程序系统

• 在内存中同时存在多道作业，在管理程序控制下相互穿插运行

  • 通过作业调度选中一个作业并运行
  • 当作业必须等待时，切换到另一个作业

• 目的

  • 提高CPU的利用率，充分发回计算机系统部件的并行性
• 现代操作系统广泛采用多道程序设计技术

并行和并发的区别

• 并行

  • 两个或多个作业在同一时刻运行

• 并发

  • 两个或多个作业在同一时间间隔内依次运行
  • 一个时间段中，有几个作业在同一个处理及上运行，但任一个时刻点上只有一个作业在处理及上运行
• 随着多核处理器的出现，这两个概念并不严格区分

分时系统

• 分时系统是多道程序设计的延申

• 作业分类

  • 批处理作业

  • 交互作业

    • 响应时间短，小于1s
    • 多道程序设计技术

  • 时间片

    • 把一段CPU时间按照固定单位进行分割，每个分割得到的时间段称为一个时间片
    • 每个任务以此轮流使用时间片

• 分时系统

  • 一种联机的多用户交互式操作系统
  • 一般采用时间片轮转方式使一台计算机为多个用户服务
  • 在单位时间内，每个用户获得一个时间片并运行
  • 保证用户获得足够小的响应时间，并提供交互能力

• 原理

  • 若某个作业在分配的时间片用完之前计算还未完成，该作业就暂时中断，等待下一轮；此时，处理机让给另一个作业使用。
  • 每个用户好像独占一台计算机（时间片小的原因）

操作系统操作和功能

操作系统操作

• 双模式
• I/O和内存保护
• 定时器

双重操作模式

• 程序运行中的问题

  • 软件错误或者特定请求产生的异常
  • 其他进程问题：如死循环

• 解决方法：双重模式

  • 允许OS保护自身和其他系统部件
  • 用户模式和内核模式
  • 由硬件提供模式位

  • 特权指令

    • 可能引起系统崩溃的指令，只能运行在内核模式
• 系统调用：模式转换

• 用户程序需要用特权指令怎么办？

  • 解决方法：系统调用
  • 视为软件中断

I/O和内存保护

• I/O保护

  • 防止用户程序执行非法I/O
  • 解决方法：所有IO指令都是特权指令
  • 用户程序通过系统调用进行IO操作

• 内存保护

  • 防止内存非法访问
  • 解决方法：存储保护机制
  • 硬件支持

• 内存保护的例子

  • 基址寄存器
  • 限长寄存器

定时器

• 如果操作系统不能获得CPU控制权，就无法管理系统

  • 用户程序死循环
  • 用户程序不调用系统调用

• 解决方法：定时器

  • 在一段时间后发生中断，CPU控制权返回操作系统
  • 固定时间和可变时间的定时器
  • 利用时钟和计数器实现

操作系统功能

• 进程管理
• 内存管理
• 文件管理
• IO系统管理

进程管理

• 操作系统的核心目标：运行程序
• 进程：运行中的程序
• 进程管理：对CPU进行管理

• 具体包括

  • 创建和删除用户和系统进程
  • 暂停和恢复进程
  • 提供进程同步机制
  • 提供进程通信机制
  • 提供死锁处理机制

内存管理

• 程序运行必须的存储设备

  • CPU只能直接访问寄存器、高速缓存和内存
  • 处理前和处理后的数据都在内存
  • 执行的指令都在内存

• 内存管理：提供内存的分配、回收、地址转换、共享和保护等功能

  • 提高内存利用率

  • 提高内存访问速度

    • 从而提高计算机运行效率

文件管理

• 解决信息在计算机中存储问题
• 以文件为单位，以目录为组织方式构建文件系统

• 内容

  • 文件逻辑结构
  • 文件物理结构
  • 目录
  • 文件检索方法
  • 文件操作
  • 空闲空间管理
  • 存储设备管理

I/O设备管理

• 管理IO设备，解决计算机中信息的输入和输出问题

• 关键：设备无关性

  • 所有物理设备按照物理特性抽象为逻辑设备
  • 应用程序针对逻辑设备编程
  • 应用程序和物理设备无关

• 内容

  • 设备管理
  • 设备驱动

第二章 操作系统结构

操作系统服务和接口

操作系统服务

• 以服务形式向程序和用户提供环境执行程序

• 基本服务

  • 用户界面
  • 程序执行
  • IO操作
  • 文件系统
  • 通信
  • 错误检测

• 增值服务

  • 资源分配
  • 统计
  • 保护和安全

• 服务形式

  • 系统调用
  • 用户接口
  • 系统程序

• 系统调用

  • 操作系统服务的编程接口—面向程序
  • 高级语言编写
  • 程序通过应用程序接口API访问

  • 三种常用API

    • Win32 API
    • POSIX API
    • Java API

CLI （Command-Line Interface）

• 字符模式

• 用户直接输入

• 内核或系统程序实现

• 多种实现方式

• 作用

  • 获取并执行用户指定的命令
  • 内置和外置命令

图形化接口GUI（Graphical User Interface）

• 用户界面友好的桌面接口
• 使用鼠标、键盘和监视器

系统程序

• 用于管理、维护操作系统

• 允许用户使用操作系统服务

• 功能

  • 文件管理
  • 状态信息
  • 文件处理
  • 程序语言支持
  • 程序装入和执行
  • 通信

操作系统结构

简单结构

• 无结构

• 早期操作系统采用

  • 规模小，简单
  • 功能有限

• 问题

  • 混乱
  • 不易维护和更新
  • 不适合大规模系统开发
• 例如MS-DOS，早期UNIX

层次结构

• 操作系统划分为若干层

• 在低层上构建高层

• 底层为硬件

• 最高层为用户层

• 每层只使用低层次的功能和服务

• 优点

  • 简化了系统设计和实现，便于调试和升级维护

• 缺点

  • 层定义困难
  • 效率差
• 例如IOS，THE

微内核

• 核内移出尽可能多的功能到用户空间

• 好处

  • 便于扩充微内核
  • 便于移植操作系统到新架构系统上
  • 更稳定（更少的代码运行在核心态）
  • 更安全

• 坏处

  • 用户空间和内核空间通信的系统开销增加
  • 解决方法：提出消息传递机制

• 例子

  • 第一个，CMU的Mach
  • Tru64 Unix
  • QNX
  • Windows NT, 2000, 2003以及后续版本

模块结构

• 大部分现代操作系统采用模块结构

  • 使用面向对象方法
  • 每个核心分开
  • 每个与其他模块的会话被称为接口
  • 每个模块在需要时被加载到内核
• 类似于分层方法，但更灵活

• 例子

  • Solaris
  • Linux
  • Mac

虚拟机

虚拟机 Virtual Machines

• 一种通过软件模拟实现，具有完整硬件系统功能，并运行在一个完全隔离环境中的完整计算机系统
• 物理计算机资源共享以创建虚拟机
• 每个虚拟机同其他虚拟机隔离

虚拟机实现

• 高级语言虚拟机

  • 模拟代码执行
  • 目的：跨平台

• 工作站虚拟机

  • GuestOS
  • 面向工作站、PC
  • 目的：多个操作系统可以同时在一个计算机上使用

• 服务器虚拟机

  • 多用户、多操作系统并存
  • 面对：把一个物理计算机虚拟化为多个虚拟机

Java虚拟机

• JVM：Java语言的解释器
• 可运行Java代码的假想计算机
• 只要根据JVM规格将解释起移植到特定的操作系统上，就能运行经过编译的任何Java代码
• 特点：平台无关性

工作站虚拟机

• 操作系统上的虚拟机

  • 宿主操作系统（Host OS）：安装在硬件上的OS
  • 客户操作系统（Guest OS）安装在操作系统上的操作系统
  • 工作站虚拟机安装在宿主操作系统上，在工作站虚拟机中可以安装客户操作系统

• 好处

  • 同时在一个计算机上使用多个操作系统
  • 一个宿主操作系统，若干个客户操作系统

服务器虚拟机

• 服务器虚拟化：将服务器的物理资源抽象成逻辑资源，让一台服务器变成几台甚至上百台相互隔离的虚拟服务器

• 常用模式

  • 一虚多：一台服务器虚拟成多台服务器虚拟机
  • 多虚一：多个独立物理服务器虚拟为一个服务器虚拟机

• 优点

  • 安全性好
  • 资源共享
  • 可扩展性好
  • 便于隔离
  • 性价比高

第三章 进程

进程概念

• 进程 - 执行中的程序
• 进程的执行必须以顺序方式进行

进程组成

• 代码（Text）

• 当前活动

  • 程序计数器（PC）- 指向当前要执行的指令（地址）
  • 堆栈（Stack）- 存放函数参数、临时变量等临时数据
  • 数据（Data) - 全局变量，处理的文件
  • 堆（Heap）- 动态内存分配

进程和程序的区别与联系

• 进程是一个实例，是程序的一次执行
• 一个程序可对应一个或者多个进程，同样一个进程可以对应一个或多个程序
• 程序是进程的代码（Text）部分
• 进程是活动实体，程序是静止实体
• 进程在内存，程序在外存

进程控制块PCB

• PCB包括的信息

  • 进程状态
  • 程序计数器
  • CPU寄存器
  • CPU调度信息
  • 内存管理信息
  • 记账信息
  • I/O状态信息

进程的上下文切换

• 进程的并发执行需要PCB保存和恢复现场

引起上下文切换的原因

1. 当前正在执行的任务完成，系统的CPU正常调度下一个任务。
2. 当前正在执行的任务遇到I/O等阻塞操作，调度器挂起此任务，继续调度下一个任务。
3. 多个任务并发抢占锁资源，当前任务没有抢到锁资源，被调度器挂起，继续调度下一个任务。
4. 用户的代码挂起当前任务，比如线程执行sleep方法，让出CPU。
5. 硬件中断。

进程状态

• 进程改变状态的事件

  • 新建：在创建进程
  • 运行：指令在执行
  • 等待：进程等待某些事件发生
  • 就绪：进程等待分配处理器
  • 终止：进程执行完毕

进程操作

进程创建

• 父进程创建子进程

• 资源共享

  • 双方共享所有资源
  • 子进程共享父进程资源子集
  • 父进程和子进程无资源共享

• 执行

  • 并发执行
  • 父进程等待，直到子进程终止

进程终止

• 进程执行最后一项并退出（exit）

  • 从子进程向父进程输出数据（通过wait）
  • 操作系统回收进程的资源

• 父进程可中止子进程的执行（abort）

  • 子进程超量分配资源

  • 赋予子进程的任务不再需要

  • 父进程结束

    当父进程中止时，一些系统不允许子进程继续存在

所有子进程都会终止 – 级联终止

• 父进程等子进程结束，调用wait()系统调用

进程间通信

• 独立进程：不会影响另一个进程的执行或被另一个进程执行影响

• 协同进程：可能影响另一个进程的执行或被另一个进程执行影响

  • 优点：

    • 信息共享
    • 加速运算
    • 模块化
    • 方便

• 用于进程通信，同步其间的活动

• 两种模式

  • 共享内存
  • 消息传递

共享内存

• 一块内存被多个进程共享

• 通信由应用程序自己控制，一般用于大数据通信

• 实现手段

  • 文件映射
  • 管道
  • 剪贴板

• 例子：生产者-消费者

  • 生产者进程生产，供消费者进程消费的信息

    • 无界缓冲(Unbounded-buffer)没有对缓冲区大小的限制
    • 有界缓冲(Bounded-buffer)对缓冲区大小作了限定

消息传递

• 微内核中的应用，远程通信无法采用共享内存

• 两个操作

  • 发送 send
  • 接受 receive

• 通信过程

  • 建立通信连接

    • 物理的（共享存储，硬件总线）
    • 逻辑的（逻辑特性）
  • 通过send/receive交换消息

• 问题

  • 如何建立连接？
  • 可以连接多于两个的进程？
  • 每对在通信进程有多少连接？
  • 一个连接的容量？
  • 连接可使用的固定或可变消息的大小？
  • 连接是无向的还是双向的？

• 直接通信

  • send(P, message) 向进程P发消息
  • receive(Q, message) 从进程Q收消息

  • 特性

    • 连接自动建立
    • 连接精确地与一对通信进程相关
    • 在每一对通信进程间存在一个连接
    • 连接可单向，但通常双向

• 间接通信

  • 消息导向至信箱，从信箱接收

    • 每个信箱有唯一id
    • 仅当共享一个信箱时进程才能通信

  • 通信连接的特性

    • 仅当进程共有一个信箱时连接才能建立
    • 连接可同多个进程相关
    • 每一对进程可共享多个通信连接
    • 连接可是单向或双向的

  • 操作

    • 创建新的信箱
    • 通过信箱发送和接收消息
    • 销毁信箱
  • send(A, message) - 发送消息到信箱A
  • receive(A, message) - 从信箱A接收消息

  • 信箱共享

    • P1 P2 P3共享信箱A
    • P1发送；P2 P3 接受
    • 谁收到消息？

    • 解决方案

      • 允许一个连接最多同2个进程相关
      • 只允许一个时刻有一个进程执行接收操作
      • 允许系统任意选择接收者，发送者被通知谁是接收者

同步

• 消息传递

  • 阻塞（blocking）

    • 同步
    • send：发送进程阻塞，直到消息被接受
    • receive：接收者进程阻塞，直到有消息可用

  • 非阻塞（non-blocking）

    • 异步
    • send：发送进程发送消息，并继续操作
    • receive：接收者收到一个有效消息或无效消息

第四章 线程

• 引入线程前，进程是CPU的调度单位和任务单位

• 引入原因

  • 性能

    • 操作进程系统开销大
    • UNIX的轻型进程

  • 应用

    • 进程代码并发执行的需求
    • 例如PPT编辑（输入/拼写检查/存盘）

  • 硬件

    • 多核处理器
    • 加速进程的运行

• 线程 Thread

  • 在CPU上运行的基本执行单位
  • 进程内的一个代码片段可以被创建为一个线程
  • 状态：就绪、等待、运行等
  • 操作：创建、撤销、等待、唤醒等
  • 进程是资源分配的基本单位
  • 线程不拥有系统资源，通过进程申请资源

线程和进程对比

线程结构

• 代码和数据：来自进程
• 各类资源：来自进程

• TCB

  • 线程ID
  • 程序计数器PC
  • 寄存器集
  • 栈空间

线程优点

• 响应度高

  • 线程创建开销小
  • 例子：Web服务器

• 资源共享

  • 进程中的线程可以共享进程资源

• 经济性

  • 线程创建、上下文切换比进程快

多线程模型

• 用户线程

  • 由用户线程库进行管理的线程
  • 内核看不到用户线程
  • 用户线程的创建和调度都在用户空间中，不需要内核干预

• 例子

  • POISX Pthreads
  • Win32 threads
  • Java threads

• 内核线程

  • 内核进行管理的线程
  • 需要内核支持，由内核完成线程调度，包括创建和撤销

• 多对一模型

  • 不支持内核线程的操作系统，内核只有进程

  • 内核只能看到一个进程

    • 多个线程不能并行运行在多个处理器上

  • 进程中的用户线程由进程自己管理

    • 进程内线程切换不会导致进程切换
    • 一个线程的系统调用会导致整个进程阻塞

• 一对一模型

  • 用于支持线程的操作系统

    • 用户线程映射到内核线程
    • 操作系统管理这些线程
  • 并发性好：多个线程可并行运行在多个处理器上
  • 内核开销大

  • 例子

    • Windows
    • OS/2
    • Linux

• 多对多模型

  • 多个用户线程映射为相等或更小数目的内核线程

    • 并发性和效率兼顾
    • 增加复杂度
  • Solaris 9 以前的版本

线程库

• 为程序员提供API来创建和管理线程

• 两种模式

  • 用户库（用户线程）

    • 存在于用户空间
    • 没有内核支持
    • 调用线程库不会产生系统调用

  • 内核库（内核线程）2

    • 存在于内核
    • 操作系统支持
    • 调用线程库会产生系统调用

JAVA线程库

• Java线程库由Java虚拟机JVM管理

  • Java线程操作系统部件
  • 用户线程
  • 定义了创建和操纵线程的一整套API
  • 跨操作系统平台

• 创建线程

  • 扩展java.lang.Thread类
  • 实现Runnable接口

第五章 CPU调度

概述

• 长程调度

  • 又称作业调度、高级调度
  • “新建”状态转换到“就绪状态”, new->ready
  • 由调度程序选择
  • 控制多道程序的道/度（Degree）

• 短程调度

  • 又称CPU调度、低级调度
  • 调度程序选择下一个执行进程
  • 一个进程从“就绪”到“运行”, ready->running
• 二者比较

• 中程调度

  • 又称交换
  • 将进程在内存和外存中换进换出
  • 目的：节省内存空间

• 进程调度队列

  • 就绪队列

    • 在主内存中处于就绪状态并等待执行的所有进程的集合

  • 设备队列

    • 等待某一I/O设备的进程队列

      进程的执行过程实际上就是进程在各种队列之间的迁移

CPU调度过程

• 调度程序 Scheduler

  • 根据某种策略选择就绪程序
  • 一个CPU同时只能运行一个进程

• 分派程序 Dispatcher

  • 负责把CPU的控制权转交CPU调度程序
  • 切换上下文
  • 切换到用户态
  • 跳转到用户程序的适当位置并重新运行

• 分派延迟 Dispatch latency

  • 分派程序终止一个进程的运行并启动另一个进程运行所花费的事件

调度方式

• 非抢占调度 Nonpreemptive

  • 不可以抢占已分配的CPU
  • 只有进程自愿释放CPU，才能分配给其他进程

  • 优点

    • 容易实现
    • 调度开销小，适合批处理系统

  • 缺点

    • 响应时间长
    • 不适合交互式系统

• 抢占式调度 Preemptive

  • 调度程序可以根据某种原则暂停正在执行的进程，重新分配CPU
  • 可以防止单一进程长时间独占CPU
  • 系统开销大
• 区别在于是否自愿放弃CPU

调度时机

• CPU调度可能发生在一个进程

  • 从运行转到等待（非抢占）
  • 从运行转到就绪（抢占）
  • 从等待转到就绪（抢占）
  • 终止运行（非抢占）

调度准则 - 基本指标

• CPU利用率

  • 固定时间内CPU运行时间的比例

• 吞吐量

  • 单位时间内运行完的进程数

• 周转时间

  • 进程从提交到运行结束的全部时间

• 等待时间

  • 进程等待调度（不运行）的时间片综合

• 响应时间

  • 从进程提交到首次运行的事件，也就是第一段的等待时间

• 周转时间 = 等待时间 + 运行时间

• 响应时间<=等待时间

• 优化方法

  • 最大CPU利用率
  • 最大吞吐量
  • 最小周转时间、等待时间、响应时间

• 解决方法

  • 调度算法：就绪队列中哪个进程被选中运行

调度算法

先来先服务调度算法

• First-come, First-served - FCFS

  • 按进程请求CPU的先后顺序使用CPU
• 举例：

• Gantt图
  

  • 周转时间：P1：24; P2：27; P3：30；平均周转时间： (24 + 27 + 30)/3 =27
    等待时间：P1：0; P2：24; P3：27；平均等待时间: (0 + 24 + 27)/3 = 17
    响应时间：P1：0; P2：24; P3：27；平均等待时间: (0 + 24 + 27)/3 = 17

• 特点

  • 实现简单，可使用FIFO队列实现
  • 非抢占
  • 公平
  • 对长CPU脉冲的进程有利，对短CPU脉冲的进程不利
  • 适用于长程调度、后台批处理系统的短程调度

• Gantt图调整顺序
  

  • 周转时间：P1：30；P2：3；P3：6，平均周转时间：13
  • 等待时间：P1：6；P2：0；P3：3，平均等待时间：3
  • 响应时间：P1：6；P2：0；P3：3，平均等待时间：3
  • 前例结果（护航效果）的产生是由于长进程先于短进程到达

短作业优先调度算法

• SJF，Shortest-Job-First

• 两种模式

  • 非抢占模式
  • 抢占模式

• 优点：最短的平均等待时间

• 缺点：进程会被饿死

• 非抢占式SJF例子
  

  • SJF(non-preemptive)
    

  • 平均周转时间 = (7+10+ 4+ 11)/4 = 8

  • 平均等待时间 = (0 + 6 + 3 + 7)/4 = 4

• 抢占式SJF例子

  • 
  • SJF(preemptive)
  • 
  • 平均周转时间：（16+5+1+6）/ 4 = 7
  • 平均等待时间：（9+1+0+2）/ 4 = 3

  • 平均响应时间 ：（0+0+0+2）/4 = 0.5

    • 进程被提交到首次运行的时间

• SJF算法的难度在于如何知道下一个CPU区间的长度

• SJF通常用于长程调度

• 通过CPU区间长度及其指数平均进行预测

优先级调度

• Priority Scheduling

• 基于进程的紧迫程度，由外部赋予每个进程相应的优先级，CPU分配给最高优先级的进程

  • 每个进程都有一个优先数，优先数为整数
  • 默认：小优先数具有高优先级
  • 目前主流的操作系统调度算法

• PR非抢占式例子

  • 
  • 
  • 平均等待时间 = （6+0+16+18+1）/ 5 = 8.2

• 存在问题

  • 饥饿 – 低优先级的进程可能永远得不到运行

• 优先级类型

  • 静态优先级

    • 进程创建时确定，在运行期间不变
    • 简单易行，系统开销小
    • 不够精确，可能会出现饥饿问题

  • 动态优先级

    • 进程创建时的优先级随进程推进或等待时间增加而改变

• 动态优先级举例

  • 高响应比优先调度算法
  • 既考虑进程的 等待时间，又考虑进程的运行时间
  • 
  • 如果等待时间相同，运行时间越短，优先级越高，类似于SJF
  • 如果运行时间相同，优先级取决于其等待时间，类似于FCFS
  • 长进程的优先级可随等待时间的增加而提高，最终可得到服务

  • 缺点

    • 每次调度之前，都需要计算响应比，增加系统开销

时间片轮转

• RR - Round Robin
• 专为分时系统设计，类似于FCFS，但增加了抢占

• 时间片

  • 小单位的CPU时间，通常是10-100毫秒

• 为每个进程分配不超过一个时间片的CPU

  • 时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行
  • 假定就绪队列中有n个进程、时间片为q，则任何一个进程的等待时间不会超过(n-1)*q

• 举例

  • 
  • Gant
  • 
  • 平均等待时间：(57+20+64+80)/4 = 55.25
  • 平均响应时间: (0+20+37+57)/4= 28.5
  • 通常，RR的平均周转时间比SJF长，但响应时间要短

• 时间片大小

  • q大 => FCFS
  • q小 => 增加上下文切换时间
  • 一般准则：时间片/10>进程上下文切换时间

多级队列调度

• 以上算法存在局限性

  • SJF有利于短进程而不利于长进程
  • RR系统开销大
  • 所有进程采用同一策略，不合理

• 不同类型的进程需要不同策略

  • 交互进程需要短的响应时间
  • 批处理进程需要短的等待时间

• MultiLevel Queue Scheduling

  • 系统中有多个就绪队列，每个队列有自己的调度算法

• 要素

  • 队列数
  • 每一队列的调度算法
  • 决定新进程将进入哪个队列方法

• 例子

  • 就绪队列分为

    • 前台[交互式]
    • 后台[批处理]

  • 每个队列有自己的调度算法

    • 前台 - RR
    • 后台 - FCFS
  • 先调度哪个队列的进程呢？

  • 解决方法

    • 固定优先级：前台运行完后在运行后台，有可能产生饥饿

    • 给定时间片：每个队列得到一定比例的CPU时间，进程在给定时间内执行

      • 如：80%时间执行前台RR，20%时间执行后台FCFS

多级反馈队列调度

• MultiLevel Feedback Queue Scheduling

• 区别

  • 多级队列：进程不能再不同队列之间移动
  • 多级反馈队列：进程能在不同队列间移动

• 多级反馈队列调度需要考虑

  • 队列数
  • 每一个队列的调度算法
  • 决定进程升级的方法
  • 决定进程降级的方法
  • 决定新进程将进入那个队列的方法

多处理器调度

• 适用多核处理器的CPU调度

• 多个CPU可用时，CPU调度将更为复杂

• 对称多处理器 (SMP) – 每个处理器决定自己的调度方案，主流方案

• 非对称多处理器(ASMP) – 仅一个处理器能处理系统数据结构，减轻对数据的共享需求

• 调度算法：和单处理器相似

• 负载平衡：将任务平均分配给各个处理器

• 亲和性：进程在某个给定的 CPU 上尽量长时间地运行而不被迁移到其他处理器的倾向性

  • 软亲和性：进程通常不会在处理器之间频繁迁移
  • 硬亲和性：进程不会在处理器之间迁移

单队列调度方法

• 单队列多核调度方法

• Single-Queue MultiProcessor Scheduling

• 系统有一个就绪队列。当任意一个CPU空闲时，就从就绪队列中选择一个进程到该CPU上运行

• 优点

  • 容易从单核调度算法推广到多核/多处理器
  • 实现简单，负载均衡

• 缺点

  • 不具有亲和性
  • 加锁问题

多队列调度方法

• Multi-Queue MultiProcessor Scheduling
• 系统有多个就绪队列，一般每个CPU一个。每个就绪队列有自己的调度算法，并且每个就绪队列的调度相对独立

• 优点

  • 亲和性好
  • 不需要加锁

• 缺点

  • 负载不均衡

• 策略

  • “偷”进程

✨第六章 进程同步

竞争条件和临界区

数据不一致性

• 多个进程并发或并行执行

  • 每个进程可在任何时候被中断
  • 仅仅进程的部分代码片段可连续执行

• 共享数据并发/并行访问：数据不一致性

  • 协同进程，共享资源
  • 又称不可再现性：同一进程在同一批数据上多次运行的结果不一样

  • 解决方法

    • 同步(互斥)机制

• 举例

  • counter++的伪机器语言：

    • （S0）register1 = counter
    • （S1）register1 = register1 + 1
    • （S2）counter = register1

  • counter--的伪机器语言：

    • （S3）register2 = counter
    • （S4）register2 = register2 – 1
    • （S5）counter = register2

  • 错误例子

    • v初时counter = 5:
      S0: register1=counter {register1 = 5}
      S1: register1=register1+1 {register1 = 6}
      S3: register2=counter {register2 = 5}
      S4: register2=register2–1 {register2 = 4}
      S2: counter=register1 {counter = 6}
      S5: counter=register2 {counter = 4}
      

  • 解决方法

    • 原子性地执行某些语句
    • 原子操作：一个操作在整个执行期间不能中断

竞争条件

• Race Condition

• 竞争条件: 多个进程并发访问同一共享数据的情况

  • 共享数据的最终结果取决于：最后操作的进程
• 防止竞争条件方法：并发进程同步或互斥

同步和互斥

• 同步

  • 协调进程的执行次序，使并发进程间能有效地共享资源和相互合作，保证数据一致性
  • 协调执行次序

• 互斥

  • 进程排他性地运行某段代码，任何时候只有一个进程能够运行
  • 互斥访问独占资源

临界资源

• Critical Resource 临界资源

  • 一次只允许一个进程使用的资源
  • 又称互斥资源、独占资源或共享变量
  • 例如in，out，counter，缓冲区，打印机都是临界资源

• 共享资源

  • 一次允许多个进程使用的资源
  • 例如磁盘

• Critical Section 临界区

  • 涉及临界资源的代码段
  • 临界区是代码片段
  • 临界区是进程内的代码
  • 每个进程有一个或多个临界区
  • 临界区的设置方法由程序员确定
• 若能保证诸进程互斥进入关联的临界区，可实现对临界资源的互斥访问

item nextCounsumed;
while(1){
    while(counter==0)
        ;// do thing
    nextConsumed = buffer[out];
    out = (out+1)%BUFFER_SIZE;
    counter--;
    // 这里的counter是临界资源
    // counter--;这一行是临界区
}

临界区使用准则

• 互斥 Mutual Exclusion

  • 假定进程在某个临界区执行，其他进程将被排斥在该临界区外
  • 有相同临界资源的临界区都需互斥
  • 无相同临界资源的临界区不需互斥

• 有空让进 Progress

  • 临界区内无进程执行，不能无限期地延长下一个要进临界区进程的等待时间

• 有限等待 Bounded Waiting

  • 每个进程进入临界区前的等待时间必须有限
  • 不能无限等待

• 让权等待

  • 当进程无法进入临界区的时候，应该放弃CPU的控制权（如转换到阻塞状态）

访问临界区

• 访问过程

  • 在进入区实现互斥准则
  • 在退出区实现有空让进准则
  • 每个临界区不能过大，从而实现有限等待准则

• 软件同步

  • Peterson算法

• 硬件同步

  • 许多系统采用硬件同步机制来处理临界区

  • 利用锁来保护临界区

  • 单处理器：禁止中断

  • 现代操作系统：特殊硬件指令

    • 原子操作

      do{
      acquire lock
      critical section
      release lock
      remainder section
      }while(Ture);

信号量

• 信号量 Semaphore 软件解决临界区的同步问题

  • 保证两个或多个代码段不被并发调用
  • 在进入关键代码段前，进程必须获取一个信号量，否则不能运行
  • 执行完该关键代码段，必须释放信号量
  • 信号量有值，为正说明它空闲，为负说明其忙碌

• 整型信号量

  • 提供两个不可分割的原子操作访问信号量

  • wait(S){
    while S<=0 do no-op;
    S--;
    }
    signal(S){
    S++;
    }

• wait(S)又称为P(S)

• signal(S)又称为V(S)

• 整型信号量的问题：不满足让全等待的原则（忙等）

• ✨记录型信号量：去除忙等的信号量 ```c // 当进程需要使用资源时，通过wait申请s Wait(semaphore *S) { S->value—; if (S->value < 0) {

    add this process to list S->list;
    block();

  } } // 当进程使用完资源后，通过singal释放，同时去唤醒等待队列的进程 Signal(semaphore *S) { S->value++; if (S->value <= 0) {

    remove a process P from list S->list;
    wakeup(P);

  } }

// 记录型信号量定义 typedef struct { int value; // 剩余资源数 struct process *list; // 等待进程队列 } semaphore

- 
信号量分类
   - 计数信号量
      - 变化范围：没有限制的整型值
      - 计数信号量 = 同步信号量
   - 二值信号量
      - 变化范围仅限于0和1的信号量
      - 二值信号量 = 互斥信号量
- 
信号量S的使用
   - S必须置一次初值
   - S初值不能为负数
   - 除了初始化，只能通过执行P, V操作来访问S
- 
互斥信号量的使用
```c
Semaphore *S;     // 初始化为 1
wait(S);
CriticalSection()    //临界区
signal(S);

• 同步信号量的使用 ```c // 例子：P1和P2需要C1比C2先运行 semaphore s=0; P1: C1; signal(s);

P2: wait(s); C2;

<a name="63d2763e"></a>
### 经典同步问题
<a name="22d26fe8"></a>
#### 生产者-消费者问题 — 共享有限缓冲区
- 生产者（M个）：生产产品，并放入缓冲区
- 消费者（N个）：从缓冲区中取出产品并消费
![](https://gitee.com/ethanloo/markdownImage/raw/master/img/image-20201009111251684.png#alt=image-20201009111251684)
- 
如何实现生产者和消费者之间的同步和互斥？
- 
解决步骤
   1. 
写出核心代码

生产者{ 生产一个产品; 把产品放入指定缓冲区; // 临界区 } 消费者{ 从指定缓冲区取出产品; // 临界区 消费取出产品; }

   2. 
增加互斥信号量
      - 
生产者
         - 
把产品放入指定缓冲区
         - 
**in**：所有生产者对in指针需要互斥
         - 
**counter**：所有生产者消费者进程对counter互斥
         - 
```c
buffer[in] = nextProduced;
in = (in+1)%BUFFER_SIZE;
counter++

  - 

消费者

     - 

从指定缓冲区取出产品

     - 

out：所有的消费者对out指针需要互斥

     - 

counter：所有生产者消费者进程对counter互斥

     - 

nextConsumed = buffer[out];
out = (out+1)%BUFFER_SIZE;
counter--;

生产者{
    生产一个产品;
    wait(m); // 互斥操作
    把产品放入指定缓冲区; // 临界区
    signal(m); // 互斥操作
}
消费者{
    wait(m); // 互斥操作 
    从指定缓冲区取出产品; // 临界区
    signal(m); // 互斥操作
    消费取出产品;
}

1. 增加同步信号量
   两者需要协同的部分

   • 生产者：把产品放入指定缓冲区（关键代码C1）

• 消费者：从满缓冲区取出产品（关键代码C2）

• 所有缓冲区空时：C1->C2

• 所有缓冲区满时：C2->C1

• 缓冲区有空也有满时：C2，C1都可以执行
  算法分析：

• 生产者

  1.判断是否能获得一个空缓冲区，如果不能就阻塞 （同步 判断
  C1:把产品放入指定缓冲区
  2.满缓冲区数量加1，如果消费者由于等消费产品而被阻塞，则唤醒该消费者 （同步 通知

  - 消费者

 1.判断是否能获得一个满缓冲区，如果不能则阻塞（同步 判断
从满缓冲区取出一个产品
 2.空缓冲区数量加1，如果有生产者由于等空缓冲区而阻塞，则唤醒该生产者（同步 通知

 // 共享数据
semaphore *full, *empty, *m;  //full:满缓冲区数量   empty：空缓冲区数量 
 // 初始化
full->value = 0;     empty->vaule = N;    m->vaule = 1；

```c 生产者{ 生产一个产品; wait(empty); // 同步操作，消耗一个空闲缓冲区 wait(m); // 互斥操作 把产品放入指定缓冲区; // 临界区 signal(m); // 互斥操作 signal(full); // 同步操作，增加一个产品 } 消费者{ wait(full); // 同步操作，消耗一个产品 wait(m); // 互斥操作 从指定缓冲区取出产品; // 临界区 signal(m); // 互斥操作 singal(empty); // 同步操作，增加一个空闲缓冲区 消费取出产品; }

**✨同步的批操作必须在互斥的批操作之前 wait()**
- 
例题
<br />![](https://gitee.com/ethanloo/markdownImage/raw/master/img/image-20201012154240518.png#alt=image-20201012154240518)
```java
司机{
    do{
        启动车辆();
        正常驾驶();
        到站停车();
    }while(...)
}
售票员{
    do{
        关门();
        售票();
        开门();
    }while(...)
}

• 画出流程图

• 添加同步操作 ```java samaphore close = 1, start = 0, stop = 1; 司机{ do{ wait(close); 启动车辆(); 正常驾驶(); 到站停车(); singal(stop); }while(…) }

售票员{ do{ 关门(); signal(close); 售票(); wait(stop); 开门(); }while(…) }

- 
父亲往盘子里放苹果或橙子
<br />儿子吃橙子 ，女儿吃苹果
   - 
```java
father{
    getFruit();
    V(empty);
    putFruit();
    if (fruit == "orange"){
        P(apple);
    }else if (fruit == "apple"){
        P(orange);
    }
}
son{
    V(orange);
    get();
    eat();
    P(empty);
}
daughter{
    V(apple);
    get();
    eat();
    P(empty);
}

读者写者问题 — 数据读写操作

• 两组并发进程

  • 读者和写者
  • 共享一组数据区进行读写

• 要求

  • 允许多个读者同时读
  • 不允许读者、写者同时读写
  • 不允许多个写者同时写

• 第一类读者写者问题 — 读者优先

  • 读者

    • 无读者和写者，新读者可读
    • 有写者等，但有读者读，新读者可读
    • 有写者写，新读者等

  • 写者

    • 无读者和写者，新写者可写
    • 有读者，新写者等待
    • 有其他写者，新写者等待

Reader{
    P(M);
    rc++;
    if (rc == 1) P(W);
    V(M);
    read();
    P(M);
    rc--;
    if (rc == 0) V(W);
    V(M);
}
Writer{
    P(W);
    write();
    V(W);
}
// W既是同步信号量，又是互斥信号量

哲学家就餐问题 — 资源竞争

• 一个圆桌

  • 5个哲学家
  • 5根筷子

semaphore chopstick[5];
哲学家i{
    P(chopStick[i]);
    P(chopStick[i+1]%5);
    eat();
    V(chopStick[i]);
    V(chopStick[i+1]%5);
}

• 该解决方案会出现死锁问题

  • 当每个哲学家同时执行P(chopStick[i])，都拿起了左筷子

• 防止死锁措施

  1. 最多允许4个哲学家同时坐在桌子周围
  2. 仅当哲学家左右筷子都可用时，才允许拿筷子
  3. 给所有哲学家编号，奇数号哲学家必须先拿起左边筷子，偶数号哲学家反之

1. 最多4个哲学家入座

   semaphore chopstick[5];
   semaphore seat=4;
   哲学家i{
    P(seat);
    P(chopStick[i]);
    P(chopStick[i+1]%5);
    eat();
    V(chopStick[i]);
    V(chopStick[i+1]%5);
    V(seat);
   }

1. 同时拿左右筷子

   int[] state = [thinking]*5;
   semaphore ph[5]; // 初始值都为0
   void test(int i){
    if (state[i]==hungry && state[(i+4)%5]!=eating && state[(i+1)%5]!=eating){
        state[i] = eating;
        V(ph[i]);
    }
   }
   哲学家i{
    think();
    state[i] = hungry;
    P(m);
    test(i);
    V(m);
    P(ph[i]);
    pickLeft();
    pickRight();
    eat();
    putLeft();
    putRight();
    state[i] = thinking;
    test((i+4)%5);
    test((i+1)%5);
   }

信号量S的物理含义

• S>0：有S个资源可用
• S=0：无资源可用
• S<0：则S的绝对值表示S等待队列中的进程个数
• P（S）：申请一个资源
• V（S）：释放一个资源
• 互斥信号初始值一般为：1
• 同步信号量初始值：0-N

信号量的使用

• PV操作成对出现

  • 互斥操作：PV操作处在同一进程内
  • 同步操作：PV操作在不同进程内

• 同步与互斥P操作在一起时，同步的P操作要在互斥的P操作之前

• V操作的次序无关紧要

管程

信号量机制的问题

• 需要程序员实现，编程困难
• 维护困难
• 容易出错

解决方法

• 用编程语言解决同步互斥问题
• 管程（1970s，Hoare和Hansen）
• 信号量：分散式
• 管程：集中式

Hansen管程

• 定义

  • 定义了一个数据结构和能为并发进程所执行的一组操作
  • 这组操作能同步进程和改变管程中的数据

• 功能

  • 互斥

    • 管程中的变量只能被管程中的操作访问
    • 任何时候只有一个进程在管程中操作
    • 类似临界区
    • 由编译器完成

  • 同步

    • 条件变量
    • 唤醒和阻塞操作

条件变量 condition x,y;

• 条件变量的操作

  • 阻塞操作：wait
  • 唤醒操作：signal

• x.wait():进程阻塞知道另外一个进程调用x.signal

• x.signal():唤醒另一个进程

• 管程内可能存在不止一个进程

  • 例如进程P调用signal操作唤醒进程Q后

• 存在的可能性

  • P等到直到Q离开管程(Hoare)
  • Q等待直到P离开管程(Lampson&Redll, MESA语言)
  • P的signal操作是P在管程内的最后一个语句(Hansen, 并行Pascal)

Hoare管程

• 进程互斥进入管程

  • 如果有进程在管城内运行，管城外的进程等待
  • 入口队列：等待进入管程的进程队列

• 管程内进程P唤醒Q后

  • P等待，Q运行
  • P加入紧急队列
  • 紧急队列的优先级高于入口队列

• condition x;

• x.wait()

  • 紧急队列非空：唤醒第一个等待进程
  • 紧急队列空：释放管程控制权，允许入口队列进程进入管程
  • 执行该操作进程进入x的条件队列

• x.signal()

  • x的条件队列空：空操作，执行该操作的进程继续运行
  • x的条件队列非空：唤醒该条件队列的第一个等待进程，执行该此操作的进程进入紧急队列

Linux的同步机制

• 使用禁止中断来实现短的临界区
• 自旋锁 —- 不会引起调用者阻塞
• 互斥锁
• 条件变量
• 信号量

Windows同步机制

• 事件 —- 通过通知操作的方式来保持线程的同步
• 临界区
• 互斥锁
• 自旋锁
• 信号量

哲学家就餐的Hoare管程解决方案

monitor DP{
    enum {THINKING, HUNGERY, EATING} state[5];
    condition self[5];
    init(){
        for(int i = 0;i<5;i++){
            state[i] = THINKING;
        }
    }
    void pickup(int i){
        state[i] = HUNGERY;
        test(i);
        if(state[i]!=EATING){
            self[i].wait();
        }
    }
    void putdown(int i){
        state[i] = THINKING;
        test((i+4)%5);
        test((i+1)%5);
    }
    void test(int i){
        if((state[(i+4)%5]!=EATING)&&(state[(i+1)]!=EATING)){
            state[i] = EATING;
            self[i].signal();
        }
    }
}

作业

• 利用管程解决生产者消费者问题

第七章 死锁

死锁的特征

• 互斥：一次只有一个进程可以使用一个资源

• 占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源

• 不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放

• 循环等待：等待资源的进程之间存在环 {P0, P1, …, P0}

  P0等待P1占有的资源, P1等待P2占有的资源, …, Pn–1等待Pn占有的资源, Pn等待P0占有的资源

系统模型

• 资源类型R1, R2, R3…..

  • CPU周期
  • 内存空间
  • I/O设备
• 每一种资源Ri有Wi种实例

• 每一个进程通过如下方法来使用资源

  • 申请
  • 使用
  • 释放

• 资源动态申请-常用方法

  • 在进程运行过程中申请资源

• 资源静态申请

  • 在进程运行前一次申请所有资源

资源分配图

• 顶点集合V

  • P = {P1, P2, …, Pn}, 含有系统中全部的进程
  • R = {R1, R2, …, Rm}, 含有系统中全部的资源

• 边集合E

  • 请求边：有向边Pi -> Rj
  • 分配边：有向边Ri -> Pj

• 正常分配

• 有环有死锁

• 有环无死锁

• 如果图没有环，那么没有死锁

• 如果图有环

  • 如果每一种资源类型只有一个实例，那么死锁发生
  • 如果一种资源类型有多个实例，可能死锁

• 处理方法

  • 确保系统永远不会进入死锁状态
  • 允许系统进入死锁状态，然后恢复系统

  • 忽略问题，假装从未出现。这个方法被大部分的操作系统采用，例如unix

    • 设备虚拟化

死锁预防

• 确保至少一个必要条件不成立

  • 互斥（无法改变）
  • 占有并等待
  • 非抢占
  • 循环等待

• 占有并等待

  • 必须保证进程申请资源的时候没有占有其他资源

  • 静态分配策略

    • 要求进程在执行前一次性申请全部的资源（只有没有占有资源时才可以分配资源）
    • 利用率低，可能出现饥饿

• 非抢占

  • 如果一个进程的申请没有实现，就释放所有占有的资源
  • 先占的资源放入进程等待资源列表中
  • 进程在重新得到旧的资源的时候可以重新开始

• 循环等待

  • 对所有的资源类型排序进行总排序，并且要求进程按照递增顺序申请资源

死锁避免

• 需要的额外信息

  • 一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数
  • 死锁避免算法动态检查资源分配状态以确保循环等待条件不可能成立
  • 资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量所决定

安全状态

• 当进程申请一个有效的资源的时候，系统必须确定分配后是安全的

• 如果存在一个安全序列，系统处于安全态

• 进程序列<P1, P2, …, Pn>是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数

• 如果 Pi 需要的资源不能马上获得，那么Pi 等待直到所有的Pi-1进程结束。

• 当Pi-1 结束后， Pi获得所需的资源，执行、返回资源、结束。

• 当Pi结束后， Pi+1获得所需的资源执行，依此类推。

• 如果一个系统在安全状态，就没有死锁

• 如果一个系统不是处于安全状态，就有可能死锁

• 所以要避免死锁就是确保系统永远不会进入不安全状态

单实例资源

• 转换资源分配图

  • 需求边Pi->Rj：