概述

概念

  • 程序: 是静态的, 就是个存放在磁盘里的可执行文件, 就是一系列的指令集合

  • 进程: 是动态的, 是程序的一次执行过程

  • PID: 当进程被创建时, 操作系统为该进程分配一个唯一的, 不重复的进程号

进程实体组成

  • PCB(进程控制块): 进程存在的唯一标志, 操作系统对进程进行管理工作所需的信息都存在PCB中

    • 进程描述信息
      • 进程标识符PID
      • 用户标识符UID
    • 进程控制和管理信息
      • CPU, 磁盘, 网络流量使用情况统计…
      • 进程当前状态: 就绪态/阻塞态/运行态…
    • 资源分配清单
      • 正在使用哪些文件
      • 正在使用哪些内存区域
      • 正在使用哪些I/O设备
    • 处理机相关信息
      • 如PSW, PC等等各种寄存器的值(用于实现进程切换)

  • 程序段

    • 程序的代码(指令序列)

  • 数据段

    • 运行过程中产生的各种数据(如: 程序中定义的变量)
image-20240314163713949

特征

  • 动态性: 进程是程序的一次执行过程, 是动态地产生, 变化和消亡的

  • 并发性: 内存中有多个进程实体, 各进程并发执行

  • 独立性: 进程是能独立运行, 独立获得资源, 独立接受调度的基本单位

  • 异步性: 各进程按各自独立的, 不可预知的速度向前推进, 操作系统要提供"进程同步机制"来解决异步问题

  • 结构性: 每个进程都会配置一个PCB, 结构上看, 进程由程序段, 数据段, PCB组成

进程的状态与转换

状态

  • 创建态, 就绪态

    image-20240314180713270

  • 运行态

    image-20240314180838029

  • 阻塞态

    image-20240314181030454

  • 终止态

    image-20240314181134761

转换

image-20240314181519159

进程的组织

链接方式

image-20240314181904988

索引方式

image-20240314181938416

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理, 它具有创建新进程, 撤销已有进程, 实现进程状态转换等功能

  • 如何实现进程控制

    • 用 “原语” 实现
    • 原语的执行具有"原子性", 一气呵成
    • 如果不能"一气呵成", 就有可能导致操作系统中的某些关键数据结构信息不统一的情况, 这回影响操作系统进行别的管理工作

  • 如何实现原语的"原子性"

    • 原语的执行具有原子性, 即执行过程只能一气呵成, 期间不允许被中断
    • 可以用"关中断指令"和"开中断指令"这两个特权指令实现原子性
    image-20240315110952995

进程的创建

  • 创建原语 (操作系统创建一个进程时使用的原语) 创建态 --> 就绪态

    1. 申请空白PCB
    2. 为新进程分配所需资源
    3. 初始化PCB
    4. 将PCB插入就绪队列

  • 引起进程创建的事件

    • 用户登录
      • 分时系统中, 用户登录成功, 系统会为其建立一个新的进程
    • 作业调度
      • 多道批处理系统中, 有新的作业放入内存时, 会为其建立一个新的进程
    • 提供服务
      • 用户向操作系统提出某些请求时, 会新建一个进程处理该请求
    • 应用请求
      • 由用户进程主动请求创建一个子进程

进程的终止

  • 撤销原语 就绪态/阻塞态/运行态 --> 终止态 --> 无

    1. 从PCB集合中找到终止进程的PCB
    2. 若进程正在运行, 立即剥夺CPU, 将CPU分配给其他进程
    3. 终止其所有子进程 (进程间的关系是树形结构)
    4. 将该进程拥有的所有资源归还给父进程或操作系统
    5. 删除PCB

  • 引起进程终止的事件

    • 正常结束
      • 进程自己请求终止 (exit系统调用)
    • 异常结束
      • 整数除以0, 非法使用特权指令, 然后被操作系统强行杀掉
    • 外界干预
      • Ctrl + Alt + delete 用户选择杀掉进程

进程的阻塞

  • 阻塞原语 运行态 --> 阻塞态

    1. 找到要阻塞的进程对应的PCB
    2. 保护进程运行现场, 将PCB状态信息设置为"阻塞态", 暂时停止进程运行
    3. 将PCB插入相应事件的等待队列

  • 引起进程阻塞的事件

    • 需要等地啊系统分配某种资源
    • 需要等待相互合作的其他进程完成工作

进程的唤醒

  • 唤醒原语 阻塞态 --> 就绪态

    1. 在事件等待队列中找到PCB
    2. 将PCB从等待队列移除, 设置进程为就绪态
    3. 将PCB插入就绪队列, 等待被调度

  • 引起进程唤醒的事件

    • 等待的事件发生 (因何事阻塞, 就应由何事唤醒)

进程的切换

  • 切换原语 运行态 <–> 就绪态

    1. 将运行环境信息存入PCB
    2. PCB移入相应队列
    3. 选择另一个进程执行, 并更新其PCB
    4. 根据PCB恢复新进程所需的运行环境

  • 引起进程切换的事件

    • 当前进程时间片到
    • 有更高优先级的进程到达
    • 当前进程主动阻塞
    • 当前进程终止

进程通信

IPC 指两个进程之间产生数据交互

  • 进程是分配系统资源的单位, 因此各进程拥有的内存地址空间相互独立

共享存储

  • 设置一个共享内存区域, 并映射到进程的虚拟地址空间

  • 要互斥地访问共享空间 (由通信进程自己负责实现互斥)

    image-20240315170511574

  • 基于数据结构的共享 (低级通信)

  • 基于存储区的共享 (高级通信)

消息通信

  • 进程间的数据交换以格式化的消息为单位, 进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换

  • 直接通信方式 (点名道姓)

    image-20240315171129374

  • 间接通信方式

    image-20240315171405318

管道通信

image-20240315172336425

线程

  • 可以把线程理解为"轻量级进程"

  • 线程是一个基本的CPU执行单元, 也是程序执行流的最小单位

  • 引入线程之后, 不仅是进程之间可以并发, 进程内的各线程之间也可以并发, 从而进一步提升了系统的并发度, 使得一个进程内也可以并发处理各种任务(如QQ视频, 文字聊天, 传文件)

  • 引入线程后, 进程只作为除CPU之外的系统资源的分配单元(如打印机, 内存地址空间等都是分配给进程的)

image-20240318101755479

属性

image-20240318102153659

线程的实现方式

  • 用户级线程

    image-20240318102605837

  • 内核级线程

    image-20240318102834198

多线程模型

  • 一对一模型

    image-20240318103302354

  • 多对一模型

    image-20240318103359730

  • 多对多模型

    image-20240318103709047

状态与转换

image-20240318103832867

组织与控制

image-20240318104233032

处理机调度

三层调度

  • 高级调度 (作业调度) 外存 -> 内存

    • 按一定的原则从外存的作业后备队列中挑选一个作业调入内存, 并创建进程. 每个作业只调入一次, 调出一次. 作业调入时会建立PCB, 调出时才撤销PCB

  • 中级调度 (内存调度) 外存 -> 内存

    • 按照某种策略决定将哪个处于挂起状态的进程重新调入内存
    • 内存不够时, 可将某些进程的数据调出外存, 等内存空闲或者进程需要运行时再重新调入内存
    • 暂时遇到外存等待的进程状态为挂起状态, 被挂起的进程PCB会被组织成挂起队列

  • 低级调度 (进程调度/处理机调度) 内存 -> CPU

    • 按照某种策略从就绪队列中选取一个进程, 将处理机分配给它
    • 进程调度是操作系统中最基本的一种调度

进程的挂起态与七状态模型

image-20240318105716217

进程调度

时机

image-20240318112050426

调度方式

image-20240318112627318

调度器/调度程序

image-20240318113806289

闲逛进程

  • 没有其他就绪进程时, 运行闲逛进程

  • 闲逛进程的特性

    • 优先级最低
    • 可以是0地址指令, 占一个完整的指令周期(指令周期末尾例行检查中断)
    • 能耗低

调度算法评价指标

  • CPU利用率

  • 系统吞吐量

  • 周转时间

  • 等待时间

  • 响应时间

调度算法

先来先服务 (FCFS)

  • 算法思想

    • 从"公平"角度考虑

  • 算法规则

    • 按照作业/进程到达的先后顺序进行服务

  • 用于作业/进程调度

    • 用于作业调度时, 考虑的是哪个作业先到达后备队列; 用于进程调度时, 考虑的是哪个进程先到达就绪队列

  • 是否可抢占 ?

    • 非抢占式算法

  • 优缺点

    • 优点: 公平, 算法实现简单
    • 缺点: 对长作业有利, 对短作业不利

  • 是否会导致饥饿 ?

    • 不会

短作业优先 (SJF)

  • 算法思想

    • 追求最少的平均等待时间, 最少的平均周转时间, 最少的平均带权周转时间

  • 算法规则

    • 最短的作业/进程优先得到服务

  • 用于作业/进程调度

    • 既可用于作业调度, 也可用于进程调度. 用于进程调度时称为"短进程优先(SPF)算法"

  • 是否可抢占 ?

    • SJF和SPF是非抢占式的算法. 但也有抢占式的版本——最短剩余时间优先算法

      image-20240330210459308

  • 优缺点

    • 优点: "最短的"平均等待时间, 平均周转时间
    • 缺点: 对短作业有利, 对长作业不利

  • 是否会导致饥饿 ?

    • 会

高响应比优先 (HRRN)

  • 算法思想

    • 要综合考虑作业/进程的等待时间和要求服务的时间

  • 算法规则

    • 在每次调度时先计算各个作业/进程的响应比, 选择响应比最高的作业/进程为其服务

      image-20240330211341623

  • 用于作业/进程调度

    • 既可用于作业调度, 也可用于进程调度

  • 是否可抢占 ?

    • 非抢占式, 只有当前运行的作业/进程主动放弃处理机时才需要调度

  • 优缺点

    • 综合考虑了等待时间和运行时间

  • 是否会导致饥饿 ?

    • 不会

时间片轮转 (RR)

  • 算法思想

    • 公平地, 轮流地为各个进程服务, 让每个进程在一定时间间隔内都可以得到响应

  • 算法规则

    • 按照各进程到达就绪队列的顺序, 轮流让各个进程执行一个时间片. 若进程未在一个时间片内执行完, 则剥夺处理机, 将进程重新放到就绪队列队尾重新排队

  • 用于作业/进程调度

    • 用于进程调度 (只有作业放入内存建立了相应的进程后, 才能被分配处理机时间片)

  • 是否可抢占 ?

    • 若进程未能在时间片内运行完, 将被强行剥夺处理机使用权, 因此时间片轮转调度算法属于抢占式的算法. 由时钟装置发出时钟中断来通知CPU时间片已到

  • 优缺点

    • 优点: 公平, 响应快, 适用于分时操作系统
    • 缺点: 由于高频率的进程切换, 因此有一定开销; 不区分任务的紧急程度

  • 是否会导致饥饿 ?

    • 不会

优先级

  • 算法思想

    • 随着实时操作系统的出现, 越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

  • 算法规则

    • 每个作业/进程有各自的优先级, 调度时选择优先级最高的作业/进程

  • 用于作业/进程调度

    • 既可用于作业调度, 也可用于进程调度, 甚至还可用于I/O调度

  • 是否可抢占 ?

    • 抢占式和非抢占式都有

  • 优缺点

    • 优点: 用优先级区分紧急程度, 重要程度, 适用于实时操作系统. 可灵活地调整对各种作业/进程的偏好程度
    • 缺点: 若源源不断地有高优先级进程到来, 则可能导致饥饿

  • 是否会导致饥饿 ?

    • 会

多级反馈队列

image-20240330220936557

  • 算法思想

    • 对其他调度算法的折中权衡

  • 算法规则

    • image-20240330215339516

  • 用于作业/进程调度

    • 用于进程调度

  • 是否可抢占 ?

    • image-20240330215609480

  • 优缺点

    • 结合了FCSF, SJF, RR, 优先级的优点

  • 是否会导致饥饿 ?

    • 会

进程同步/进程互斥

image-20240331112450719

进程互斥的软件实现方法

单标志法

image-20240331115359342

  • 违反空闲让进原则

双标志先检查

image-20240331120207382

  • 违反忙则等待原则

双标志后检查

image-20240331120522293

  • 违反空闲让进和有限等待原则

Peterson算法

image-20240331121116271

  • 违反让权等待原则

进程互斥的硬件实现方法

中断屏蔽方法

image-20240331121849649

TestAndSet (TS指令/TSL指令)

image-20240331154634638

  • 违反让权等待原则

Swap指令 (XCHG指令)

image-20240331154910140

  • 违反让权等待原则

信号量机制

  • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作, 从而很方便地实现了进程互斥, 进程同步

  • 信号量其实就是一个变量(可以是一个整数, 也可以是更复杂地记录型变量), 可以用一个信号量来表示系统中某种资源的数量, 比如: 系统中只有一台打印机, 就可以设置一个初值为1的信号量

整型信号量

  • 用一个整数型的变量作为信号量, 用来表示系统中某种资源的数量

  • 违反让权等待原则

记录型信号量 (P/V操作)

image-20240401121602992

  • 遵循了让权等待原则

实现进程互斥

  1. 分析并发进程的关键活动, 划定临界区(如: 对临界资源打印机的访问就应放在临界区)

  2. 设置互斥信号量mutex, 初值为1

  3. 在进入区 P(mutex)——申请资源

  4. 在退出区 V(mutex)——释放资源

  • 对不同的临界资源需要涉资不同的互斥信号量

  • PV操作必须成对出现

实现进程同步

  1. 分析什么地方需要实现"同步关系", 即必须保证"一前一后"执行的两个操作

  2. 设置同步信号量S, 初始为0

  3. 在"前操作"之后执行 V(S)

  4. 在"后操作"之前执行 P(S)

image-20240401165724118

实现进程的前驱关系

  1. 要为每一对前驱关系各设置一个同步信号量

  2. 在"前操作"之后对相应的同步信号量执行V操作

  3. 在"后操作"之前对相应的同步信号量执行P操作

image-20240401170151018image-20240401170208876

PV操作问题

  1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系

  2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序

  3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

生产者消费者问题

image-20240411112222607 image-20240411112816607

  • 实现互斥的P操作一定要在实现同步的P操作之后

多生产者-多消费者问题

  • 与生产者消费者问题的区别在于——多类生产者，多类消费者

image-20240415113711743

吸烟者问题

  • 可以生产多个产品的单生产者问题

image-20240415113557462

读者写者问题

  • 背景

    • 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误

  • 要求

    • 允许多个读者可以同时对文件执行读操作（不会改变文件内容）
    • 只允许一个写者往文件中写信息
    • 任一写者在完成写操作之前不允许其他读者或写者工作
    • 写者执行写操作前，应让已有的读者和写者全部退出
image-20240415105404758

  • 核心思想：

    • 设置了一个计数器count用来记录当前正在访问共享文件的读进程数，判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理
    • 对count变量的检查和处理需要一气呵成，自然想到用互斥信号量
    • 用S(w)解决写饥饿问题

哲学者进餐问题

  • 该问题中只有互斥关系，但每个哲学家进程需要同时持有两个临界资源才能开始进餐

  • 如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓

  • 其中一个解法

    image-20240415113806980

管程

  • 背景

    • 信号量机制存在的问题，编写程序困难、易出错
    • 让程序员不在关注复杂的PV操作

  • 组成部分

    • 局部于管程的共享数据结构说明
    • 对该数据结构进行操作的一组过程
    • 对局部于管程的共享数据设置初始值的语句
    • 管程有一个名字

  • 基本特征

    • 局部于管程的数据只能被局部于管程的过程所访问
    • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
    • 每次仅允许一个进程在管程内执行某个内部过程（该特性由编译器实现）
image-20240415115746679

死锁

概念

  • 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

  • 产生的必要条件

    • 互斥条件
    • 不剥夺条件：不能由其他进程强行夺走资源
    • 请求和保持条件
    • 循环等待条件：存在一种进程资源的循环等待链

处理策略

破坏死锁

破坏死锁产生的四个必要条件中的一个或几个

  • 破坏互斥条件

    image-20240425112414890

  • 破坏不剥夺条件

    image-20240425112727566

  • 破坏请求和保持条件

    image-20240425112940509

  • 破坏循环等待条件

    image-20240425113257879

避免死锁

用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)

  • 什么是安全序列

    • 如果系统按照这种序列分配资源, 则每个进程都能顺利完成. 只要能找出一个安全序列, 系统就是安全状态, 安全序列可能有多个

  • 如果分配了资源之后, 系统中找不到任何一个安全序列, 系统就进入了不安全状态

  • 如果系统处于安全状态, 就一定不会发生死锁. 如果系统进入不安全状态, 就可能发生死锁

  • 银行家算法

    • 核心思想:
      • 在资源分配之前预先判断这次分配是否会导致系统进入不安全状态, 以此决定是否答应资源分配请求
    • image-20240425115727580

死锁的检测和解除

  • 检测

    image-20240425130307987 image-20240425130850541 image-20240425133425061

  • 解除

    image-20240425134528530