熊猫圈里的老鼠屎

进程与线程

7/27/2022 可恶的408

难馁

进程与线程

进程

概念

为使每个参与并发执行的程序（含数据）都能独立运行，必须配备PCB用于描述进程基本情况和运行状态。

进程实体由程序段，相关数据段，PCB组成。创建和撤销进程实体（映像）实质上都是创建和撤销PCB

  1. 进程使程序的一次执行过程
  2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
  3. 进程是具有独立功能的程序在一个数据集合上运行的过程，它是操作系统进行资源分配和调度的一个独立单位

这里的资源是指设备服务于某个进程的时间片

特征

  1. 动态性
  2. 并发性
  3. 独立性
  4. 异步性

状态与转换

  1. 运行态
  2. 就绪态
  3. 阻塞态，等待态
  4. 创建态
  5. 结束态

组织

  1. PCB
  2. 程序段，程序可以被多个进程共享
  3. 数据段

控制

进程控制用的控制段用原语

  1. 创建
  2. 终止
  3. 阻塞和唤醒，主动阻塞，唤醒插入就绪队列

通信

信息交换，PV操作低级通信方式

高级通信方式（较高速率传输大量数据）

  1. 共享存储，操作系统提供空间，用户自己实现互斥
  2. 消息传递，直接，间接（信箱）
  3. 管道通信，链接读写进程的文件

线程

概念

为提高资源利用率和系统吞吐量引入。目的减小程序在并发执行时所付出的时空开销，提高并发性能。

线程时进程中的一个实体，被系统独立调度和分派的基本单位，不拥有系统资源，只有一点必不可少的资源。

比较

  1. 调度
  2. 并发性
  3. 拥有资源
  4. 独立性
  5. 系统开销
  6. 支持多处理机系统

属性

状态与转换

  1. 执行状态
  2. 就绪状态
  3. 阻塞状态

组织与控制

  1. 线程控制块
  2. 创建
  3. 终止

实现方式

用户级线程User-Level Thread，内核级线程Kernel-Level Thread

  1. ULT

有关线程管理的应用工作都由用户空间完成，内核意识不到线程的存在

优点：线程切换不用转到内核态，减小开销；专用的调度算法；与平台无关；

缺点：系统调用阻塞所有线程；不能发挥多处理机优势

  1. KLT

每个用户级线程对应一个内核级线程

优点：发挥多处理机又是；线程被阻塞可以调度其他线程；线程切换快；内核自己也可以多线程；

缺点：同一进程线程切换也要从用户态转到内核态，由于线程调度在内核实现

  1. 组合方法

内核支持多个内核级先从建立、调度、管理同时允许用户程序建立、调度和管理用户级线程；

线程库实现方法：

  1. 用户空间提供没有内核支持的库
  2. 操作系统直接支持的内核级的库

多线程模型

  1. 多对一，多个用户级线程映射到一个内核级线程
  2. 一对一，每个用户级线程映射到一个内核级线程
  3. 多对对，n个用户级线程映射到m个内核级线程，n≥mn\geq m

处理机调度

概念

对处理机进行分配，从就绪队列中按照一定算法（公平、高效）选择一个进程

层次

  1. 高级调度（作业调度），内存与外存
  2. 中级调度（内存调度），存储器管理的对换功能
  3. 低级调度（进程调度），分配处理机

联系

  1. 作业调度为进程活动做准备，进程调度使进程正常活动起来
  2. 中级调度挂起暂时不能运行的进程
  3. 高少，中略多，低最多
  4. 进程调度最为重要，不可获取

目标

  1. CPU利用率
  2. 系统吞吐量
  3. 周转时间、平均周转时间、带权周转时间
  4. 等待时间
  5. 响应时间

实现

调度程序

调度和分派CPU的程序

  1. 排队器
  2. 分派其
  3. 上下文切换器

实际、切换与过程

  1. 请求调度
  2. 运行调度程序
  3. 进程切换

以下一定不能调度与切换

  1. 中断过程中
  2. 进程在操作系统内核临界区
  3. 需要完全屏蔽中断的原子操作

何时

  1. 发生调度条件且当前进程无法继续进行下去
  2. 中断处理结束后或自陷处理结束后

调度方式

  1. 非抢占式
  2. 抢占式

闲逛idle进程

没有就绪就运行idle

线程调度

  1. 用户级
  2. 内核级

调度算法

  1. FCFS
  2. SJF
  3. 优先级
  4. 高相应比优先
  5. 时间片轮转
  6. 多级队列
  7. 多级反馈队列

进程切换

同步与互斥

基本概念

  1. 临界资源
  2. 同步
  3. 互斥

实现临界区互斥的方法

软件方法实现

  1. 单标志法
  2. 双标志先检查法
  3. 双标志后检查法
  4. Peterson's Algorithm

硬件实现方法

  1. 中断屏蔽方法
  2. 硬件指令方法

互斥锁

信号量

  1. 整型信号量
  2. 记录型信号量
  3. 利用信号量实现同步
  4. 利用信号量实现互斥
  5. 利用信号量实现前驱关系

管程

  1. 定义，代表共享资源的数据结构，以及对该共享数据结构实施操作的一组过程组成的资源管理程序。
  2. 条件变量

经典同步问题

  1. 生产者-消费者问题
  2. 读者-写者问题
  3. 哲学家进餐问题
  4. 吸烟者问题

死锁

必要条件

  1. 互斥条件
  2. 不可剥夺条件
  3. 请求并保持条件
  4. 循环等待条件

处理策略

  1. 死锁预防
  2. 死锁避免
  3. 死锁的检测及解除

死锁预防

破坏必要条件

死锁避免

  1. 系统安全状态
  2. 银行家算法

死锁的检测和解除

  1. 资源分配图
  2. 死锁定理，简化资源分配图
  3. 死锁解除