第2章 进程管理

该模板是一张关于408考研，期末考试，操作系统第二章进程思维导图，专为计算机专业学生、考研 / 软考备考者、计算机基础课程学习者打造，是系统梳理操作系统进程管理核心知识的高效学习工具。思维导图的结构化呈现方式，将进程与线程、处理机调度、进程同步、死锁四大核心模块拆解为层级清晰、逻辑连贯的分支框架，帮助使用者快速构建进程管理的知识体系，精准攻克操作系统学习中的重难点与高频考点。对于计算机专业学生与考研 / 软考备考者而言，这份思维导图模板可直接用于课堂笔记整理、期末复习、考点梳理，将进程控制、线程模型、调度算法、同步机制、死锁处理等零散知识点系统化，降低理解与记忆难度，提升备考效率；对于计算机基础课程学习者，模板清晰呈现了进程管理的核心概念、原理与经典问题，可用于入门学习、知识框架搭建，快速建立对操作系统核心逻辑的整体认知。模板完整覆盖进程管理核心考点：从进程与线程的概念、通信方式、信号处理，到线程模型与多线程实现；从处理机调度的时机、方式与调度器设计，到进程同步的临界区、互斥实现方法与生产者 - 消费者等经典同步问题；再到死锁的概念、产生条件与预防 / 避免 / 检测解除策略，均以思维导图形式清晰呈现，层级分明，便于快速查阅、重点标记与按需编辑修改，适配备考笔记、课程复习提纲、学习课件等多种场景。该模板借助万兴脑图软件绘制，助力计算机学习者高效掌握操作系统进程管理知识。

第二章 进程管理

• 2.1进程与线程
  • 进程的概念与特征
    • 进程的概念
      • 进程映像（进程实体）
        • 是静态的
        • 由程序段、数据段和PCB组成
        • 进程实体反应了进程在某一时刻的状态(如: x++后， x=2)
          • 进程运行过程中进程实体不断变化
      • 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
    • 进程的组成
      • PCB（进程控制块）
        • 存放操作系统对进程进行管理工作所需的信息
        • 进程存在的唯一标志
          • 区分各个进程
          • 进程被创建时
            • 操作系统为其创建PCB
          • 进程结束时
            • 回收其PCB
        • • 进程描述信息
            • 进程标识符PID
              • 每一次新建进程都会分配一个不重复的唯一PID
            • 用户标识符UID
            • 让操作系统区分各个进程
          • 进程控制信息和管理信息
            • CPU、磁盘、网络流量使用情况统计.
            • 进程当前状态:就绪态/阻塞态/运行态...
            • 操作系统对进程的控制、调度
          • 资源分配清单
            • 正在使用哪些文件
            • 正在使用哪些内存区域
            • 正在使用哪些I/O设备
            • 实现操作系统对资源的管理
          • 处理机相关信息（CPU现场信息）
            • 如PSW. PC等等各种寄存器的值
              • 用于实现进程切换
          • 给操作系统用
      • 程序段
        • 程序的代码(指令序列)
        • CPU从内存中取出指令
      • 数据段
        • 运行过程中产生的各种数据(如:程序中定义的变量)
        • 信息，数据
      • 给进程自己用
        • 与进程自身的运行逻辑有关
    • 程序运行
      • 程序是静态的
        • 磁盘中的可执行文件
          • .exe
        • 一系列指令的集合
          • 程序的执行运行指令序列
      • 运行前把程序从硬盘放入内存
        • 建立对应进程（PCB）
          • 程序段
            • 数据段
      • 同一个程序每一次执行都会对应一个不同的进程
        • PCB、数据段各不相同，但程序段的内容都是相同
      • • 一个进程可以顺序地执行一个或多个程序
          • 只要在执行过程中改变其 CPU 状态和内存空间
    • 进程的特征
      • 动态性
        • 进程是程序的一次执行过程，是动态地产生、变化和消亡的
        • 进程的最基本特征
      • 并发性
        • 内存中有多个进程实体,各进程可并发执行
        • 并发性带来了异步性
      • 独立性
        • 进程是能独立运行、独立获得资源、独立接受调度的基本单位
      • 异步性
        • 异步性会导致并发程序执行结果的不确定性
        • 各进程按各自独立的、不可预知的速度向前推进
          • 操作系统要提供"进程同步机制"来解决异步问题
      • 结构性
        • 每个进程都会配置一个PCB
        • 结构上看，进程由程序段、数据段、PCB组成
  • 进程的状态与转换
    • 进程的状态
      • 运行态
        • 进程在CPU上运行
        • 在单核处理机环境下，每个时刻最多只有一个进程处于运行态
        • 多核CPU情况可能有多个进程处于运行态
      • 就绪态
        • 进程获得了除了处理机外所需的一切资源，一旦得到处理机，便可立即运行
        • 处于就绪态的进程进程可能有多个，通常将它们排成一个就绪队列
      • 阻塞态/等待态
        • 等待某资源可用（不包括处理机）或等待输入/输出完成
        • 即使处理机空闲，该进程也不能运行
      • 三种基本状态
      • 创建态（新建态）
        • 进程正在被创建，尚未转到就绪态
        • 操作系统会为进程分配资源、初始化PCB
      • 终止态（结束态）
        • 进程正在从系统中消失
          • 可能是进程正常运行结束或其他原因中断退出运行
        • 进程正在从系统中撤销
          • 操作系统会回收进程拥有的资源，撤销PCB
        • 当终止进程的工作完成之后,这个进程就彻底消失了
        • 注
          • 父进程可能还需要用到子进程的某些信息，因此子进程还不能完全杀掉
      • 注
        • 只要有就绪队列存在，就一定有程序处于运行态
          • 不可能全部处于就绪态
        • 系统中可能不存在运行态的进程
          • 全部处于阻塞态
          • 如发生死锁
        • eg，在单处理器系统中，若同时存在 10个进程
          • 最多9个进程处于就绪态、1个进程处于运行态
          • 最多10个进程都处于阻塞态
    • 进程转换图
      • • 就绪态- ->运行态:
          • 进程被调度
        • 运行态一>就绪态
          • 时间片到，CPU被其他高优先级的进程抢占、主动让出处理机
        • 运行态一>阻塞态
          • 等待系统资源分配，或等待某事件发生(主动行为)
          • 进程自身做出的主动行为
            • 系统调用
        • 阻塞态一-> 就绪态
          • 资源分配到位，等待的事件发生(被动行为)
            • 唤醒
            • 由协作进程决定
          • 不受进程自身能控制
          • 是一种被动行为
        • 创建态一 >就绪态
          • 系统完成创建进程相关的工作
        • 运行态一->终止态
          • 进程运行结束，或运行过程中遇到不可修复的错误
      • 注
        • 不能由阻塞态直接转换为运行态
        • 不能由就绪态直接转换为阻塞态
          • 进入阻塞态是进程主动请求
            • 运行时才能发出请求
  • 进程的组织
    • 链接方式
      • 大多数操作系统采用
      • 按照进程状态将PCB分为多个队列
        • 对同一个状态下的各个进程进行统一的管理
      • 操作系统持有指向各个队列的指针
        • 操作系统会管理一系列的队列
        • 每个队列都会指向相应状态进程的PCB
      • • 通常会把优先级高的进程放在队头
        • 很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列
    • 索引方式
      • 根据进程状态的不同，建立几张索引表
      • 操作系统持有指向各个索引表的指针
      • 给各种状态的进程建立索引表，每个索引表的表项指向一个PCB
  • 进程控制
    • 原语
      • 一般把进程控制的程序段称为原语
      • 特点
        • 不允许被中断
          • 可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性
          • CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。
        • 是不可分割的基本单位
    • 进程控制
      • 对系统中的所有进程实施有效的管理
    • 功能
      • 进程的创建（fork）
        • 操作系统创建一个进程时使用的原语
        • 创建原语
          • 申请空白PCB
            • PCB填入一些控制和管理进程的信息
          • 为新进程分配所需资源
          • 初始化PCB
            • PID UID
          • 将PCB插入到就绪队列
            • 创建态->就绪态
              • 修改PCB内容和相应队列
            • 就绪队列
              • 由各就绪进程的PCB组成
        • 引起进程创建的事件
          • 用户登录
            • 分时系统中，用户登录成功，系统会建立为其建立一个新的进程
          • 作业调度
            • 多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
            • • 作业：放在外存还未投入运行的程序
              • 作业调度：从外存中挑选一个程序放入内存开始运行
          • 系统提供服务
            • 用户向操作系统提出某些请求时，会新建一个进程处理该请求
          • 用户程序的应用请求
            • 由用户进程主动请求创建一个子进程
        • 子进程与父进程
          • 一个进程创建另一个进程
          • 父进程
            • 创建者为父进程
          • 子进程
            • 被创建者为子进程
            • 可以继承（共享）父进程所拥有的资源
              • 如系统IPC、文件描述符等
              • 不能共享虚拟地址空间
                • 创建时分配
              • 也可以通过系统调用获取独立的资源来实现自己的功能
            • 被撤销时，应将从父进程哪里得到的资源归还给父进程
          • 父进程撤销后，子进程可能有两种状态
            • ①子进程一并被终止
            • ②子进程成为孤儿进程，被 init 进程领养
          • 孤儿进程：
            • 一个父进程退出，而它的一个或多个子进程还在运行，那些子进程将成为孤儿进程
            • 对比
              • 当进程结束时，所有线程都会被强制终止，不会继续在后台运行
                • 线程几乎不占有资源
          • 特点
            • 父进程与子进程可以并发执行
            • 父进程与子进程具有不同的PID
            • 父进程与子进程具有相同却独立的地址空间
            • 进程间的关系是树形结构
        • 一个计算机系统中，进程的最大数量主要受到内存大小限制。
          • 由内存存放PCB
      • 进程的终止
        • 撤销原语
          • 就绪态/阻塞态/运行态→终止态→无
          • 步骤
            • 从PCB集合中找到终止进程的PCB
            • 若进程正在运行，立刻剥夺CPU,将CPU分配给其他进程
            • 通常终止其所有子进程（不一定）
            • 将该进程拥有的所有资源归还给父进程或操作系统
            • 删除PCB
              • 进程号是有限的必须要回收，必要时杀死父进程，变为孤儿进程
        • 引起进程终止的事件
          • 正常结束
            • 进程自己请求终止（exit系统调用）
          • 异常结束
            • 整数除以0、非法使用特权指令，然后被操作系统强行杀掉
          • 外界干预
            • Ctrl+Alt+delete，用户选择杀掉进程
      • 进程的阻塞
        • 阻塞原语
          • 运行态->阻塞态
          • 步骤
            • 找到将要阻塞进程的标识号对应的PCB
            • 保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止程序运行
            • 将PCB插入到相应事件的等待队列
        • 引起进程阻塞的事件
          • 需要等到系统分配某种资源
          • 需要等待相互合作的其他进程完成工作
      • 进程的唤醒
        • 唤醒原语
          • 阻塞态->就绪态
          • 步骤
            • 等待队列找到相应进程的PCB
            • 将其从等到进程中移出，并将其状态变为就绪态
            • 把PCB插入到等待队列，等待调度程序调度
        • 引起进程唤醒的事件
          • 等待事件的发生
        • 注
          • 阻塞原语唤醒原语必须成对使用
          • 因何事阻塞，就应由何事唤醒
      • 进程的切换
        • 切换原语
          • 会让两个进程的状态发生改变
            • 运行态→就绪态
            • 就绪态→运行态
          • 进程运行环境/进程上下文：
            • CPU的所有寄存器中的值
              • 进程的现场信息
                • 包括PC的值
              • 进程在运行过程中的中间结果
            • 进程的状态
            • 控制信息
            • 堆栈中的内容
          • 上下文切换
            • 将运行环境信息存入PCB
              • 保留处理机上下文，包括PC和其他寄存器
              • 更新PCB信息
            • 把进程的PCB移入到相应的队列
            • 选择另一个进程执行，更新其PCB
              • 修改进程状态( state )
            • 根据PCB恢复进程所需的运行环境
              • 恢复处理机上下文
              • 将新进程的现场信息装入 CPU 的各个寄存器
              • 更新内存管理的数据结构
              • 将控制转至新进程执行，即更新程序计数器(PC)的值
          • 保存进程的运行环境和恢复进程的运行环境是实现进程并发执行的关键技术
        • 引起进程切换的事件
          • 当前进程时间片到时
          • 有更高优先级的进程到达
          • 当前进程主动阻塞
          • 当前进程终止
    • 教材
      • 进程的挂起
        • 与挂起对应的是激活操作
      • 挂起操作的引入
        • 引起挂起的原因
          • 终端用户的需要
          • 父进程请求
          • 负荷调节的需要
          • 操作系统的需要
      • 引如挂起原语操作后的三个进程状态的转换
        • 活动就绪→静止就绪
        • 活动阻塞→静止阻塞
        • 静止就绪→活动就绪
        • 静止阻塞→活动阻塞
  • 进程通信IPC
    • 进程通信
      • 两个进程之间产生数据交互
      • 进程
        • 分配系统资源的单位（包括内存地址空间）
        • 各进程拥有的内存地址空间相互独立
          • 不能直接访问另一个进程的地址空间
      • 三种方式都需要操作系统底层来支持
    • 三种方式
      • 共享存储
        • • 基于数据结构的共享
            • 特殊的全局变量
              • 比如共享空间里只能放一个长度为10的数组
            • 低级通信方式
            • 速度慢、限制多、灵活性差
          • 基于存储区的共享
            • 操作系统在内存中画出一块共享存储区
              • 数据的形式、存放位置都由进程控制，而不是操作系统
            • 高级通信方式
            • 速度最快
        • 共享存储区
          • 可被其他进程访问
          • 通过“增加页表项/段表项”
            • 将同一片共享内存区映射到各个进程的虚拟地址空间中
        • 两个进程对共享空间的访问必须是互斥的
          • 互斥由进程实现
          • 各个进程可使用操作系统内核提供的同步互斥工具(如P、V操作)
      • 消息传递
        • 进程间的数据交换
          • 单位
            • 格式化的消息
              • 消息头
                • 包括
                  • 发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息
                  • 计算机网络中发送的“报文”其实就是一种格式化的消息
              • 消息体
                • 具体的进程要传给另一个进程的数据
          • “发送消息/接收消息”两个原语
        • • 直接通信方式
            • 消息发送进程要指明接收进程的ID
            • 消息体从进程P的地址空间被复制到了内核空间
              • 挂到接收进程PCB的消息队列
                • 消息队列
                  • 其他进程要发送给进程Q,应该被进程Q接收的消息
                • 之后再被复制到Q的地址空间
          • 间接通信方式/信箱通信方式
            • 消息要先发送到中间实体（信箱）中
              • 信箱
                • 共享数据结构
                • 通信中转
              • 指明发送给哪个信箱，并没有指明发送给哪个进程
              • 可多个进程往同一个信箱send消息，也可多个进程从同一个信箱中receive消息
              • Eg：计网中的电子邮件系统
      • 管道通信
        • 管道/pipe文件
          • 一个特殊的共享文件
          • 其实就是在内存中开辟一个大小固定的内存缓冲区
          • 申请管道文件
            • 进程通过系统调用的方式
        • 特点
          • 管道只能采用半双工通信
            • 某一时间段内只能实现单向的传输
              • 数据的流动只能是单向的
              • 传输结束可以改变方向
            • 如果要实现双向同时通信，则需要设置两个管道
          • 先进先出
            • 区别共享存储可随机读写数据
          • 各进程要互斥地访问管道。
            • 互斥由操作系统实现
          • 数据一旦被读出，就从管道中被抛弃
            • 读进程最多只能有一个，否则可能会有读错数据的情况
            • 解决方法
              • 一个管道允许多个写进程，一个读进程
              • 互斥锁或信号量等同步机制
        • 数据以字符流的形式写入管道
          • 当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。
          • 当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
          • 管道通信无论读还是写进程都有可能阻塞
        • • 只要管道没空，读进程就可以从管道读数据
          • 只要管道没满，写进程就可以往管道写数据
      • 管道文件和共享存储的区别
        • 同：
          • 均是操作系统给两个进程分配的，可共享访问的大小固定的内存区
        • 区：
          • 共享存储两个进程可以在任意区域内读写进程
          • 管道通信以数据流的形式读和写，先进先出
            • 本质是循环队列
  • 信号
    • 区别
      • 信号量(Semaphore)
        • 实现进程间的同步、互斥
      • 信号(Signal)
        • 实现进程间通信
    • 信号
      • 不同的操作系统对信号类型的定义不一样
      • 信号名
        • 通常用宏定义常量表示信号名
          • 如:#define SlGINT2
          • 信号名对应序号
            • 事件发生时触发一个信号
            • 用于通知进程某个特定事件已经发生
            • 进程收到一个信号后，对该信号进行处理
    • 信号的发送
      • 常使用kill函数(需指明接收进程的pid、信号的序号（int型的值）)
      • 发送方
        • 用户进程
          • 用户进程之间可以发生信号
            • 注:
              • 进程之间允许发送的信号类型是有限制的
        • 内核进程
          • 内核进程也可以给用户进程发送信号
            • 内核给用户进程发送信号没限制
        • 进程自己
          • 一个进程也可以给自己发送信号
      • 若进程2和内核进程都给进程1发送了信号1
        • 进程1只会记录第一次收到的信号
        • 第二次收到的重复信号丢弃
          • 重复收到的同类信号，将被简单地丢弃
          • 1bit记录一类待处理信号
    • 信号的保存
      • 在每个进程的PCB中，用两个N bit位向量表示待处理信号、被阻塞信号
      • 位向量
        • 两个位向量
          • 待处理信号pending
            • 不少于 N bit 的位向量，对应N种信号
          • 被阻塞信号blocked
            • 也称信号掩码(signal mask)
            • 等于1就相当于屏蔽了该信号
              • 可以由进程自己来决定
              • 通过系统调用自行设置要屏蔽哪些信号
        • 从进程P1的位向量中无法区分出信号由哪个进程发送
    • 信号的处理
      • 处理时机
        • 进程从内核态转为用户态时
          • 例行检查是否有待处理信号，如果有就处理信号
          • 如:系统调用返回、或中断处理返回时
        • 例行检查原理
          • 被阻塞信号全部按位取反，再和Pending按位与
            • 仅处理信号为1，不处理信号为0
          • 设置为1的被阻塞信号被屏蔽
      • 如何处理
        • ①执行默认的信号处理程序
          • 操作系统内核对每一种信号都有默认处理程序
          • 某些信号默认忽略，不必处理。如: Linux的SIGWINCH信号
        • ②执行用户定义的信号处理程序
          • 自定义信号处理程序
            • 通过系统调用来自定义
            • 覆盖操作系统的默认处理
          • 每个进程都可以有自己的自定义信号处理程序
            • 只作用于自身
      • 信号处理程序运行结束后，通常会返回进程的下一条指令继续执行
        • 除非信号处理程序将进程阻塞或终止
      • 注
        • 信号的检测和初步处理发生在内核态
          • 信号相关的数据结构（如进程的信号屏蔽字和待处理信号集）存储在进程控制块（PCB）中，而PCB属于内核数据
          • 由操作系统在内核态完成。
        • 处理方式不同
          • 默认处理或忽略
            • 信号的处理会完全在内核态完成
          • 自定义信号处理函数
            • 切换到用户态执行用户定义的信号处理函数
            • 信号处理函数执行完毕后，进程再次陷入内核态，清除信号的待处理标志
            • 最后返回用户态，继续执行用户程序
        • 有些信号既不能被用户自定义处理函数，也不能被阻塞。如: Linux的SIGKILL、SIGSTOP信号
      • • 一旦处理了某个信号，就将pending位重置为0
          • 内核态
        • 当同时收到多个不同类信号时，通常先处理序号更小的信号。
    • 作用
      • 信号用于通知进程某个特定事件已经发生(实现简单的进程间通信)
      • “信号”常作为异常处理的一种配套机制
        • 注: 此为拓展知识
    • 信号与异常的关系
      • 异常可以由内核完成全部处理
        • 如:缺页异常
        • 此时就不必再使用信号机制
      • 异常无法由内核完成全部处理，还需要用户进程配合
        • 用“信号机制”与“异常机制”相互配合
  • 线程的概念和多线程模型
    • 线程的基本概念
      • 引入线程的目的是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能
      • 线程
        • 也称作轻量级进程
          • 但不是所有线程都比进程小
        • CPU基本的执行单元
        • 程序执行流的最小单元
        • 线程是一种特殊的进程
      • 线程也有阻塞、就绪和运行三种状态
        • 线程的状态与转换
          • 与进程之间的转换完全一致
          • 
    • 线程的组织与控制
      • 线程控制：线程在各个状态之间来回切换
      • 线程控制块TCB
        • 用于管理线程
          • 记录了线程执行的现场状态
        • TCB含有的内容
          • 线程标识符
            • 线程ID（TID）
            • 线程的唯一标识符
          • 一组寄存器，包括PC、状态寄存器和通用寄存器的内容
          • 线程运行状态
          • 线程优先级
          • 线程专用存储区
          • 信号屏蔽
          • 堆栈指针
            • 堆栈指针通常把它恢复到SP堆栈寄存器里
        • 
      • 线程表
        • 多个TCB组织成一张线程表
    • 进程和线程的比较
      • 一个进程可以创建多个线程，他们之间代码可以相同也可以不同
      • 调度
        • 引入线程后
          • 进程是除CPU之外系统资源分配的基本单位
            • 进程不再是调度的基本单位
          • 线程是（处理机）调度的基本单位
        • • 同一进程的线程切换不会引起进程的切换
          • 在不同进程进行线程切换，会引起进程切换
      • 拥有资源
        • 引入线程后
          • 进程是资源分配的基本单位
          • 线程几乎不拥有资源
            • 线程是个轻型实体
            • 只拥有极少量的，能保证独立运行的资源（线程控制块TCB、寄存器信息、堆栈等）
      • 并发性
        • 引入线程的操作系统中
          • 进程之间可以并发执行
          • 多个线程之间可以并发执行
      • 系统开销
        • 当切换进程时
          • 需要保存/恢复进程运行环境
          • 切换内存地址空间
            • 更新快表、更新缓存
        • • 同一进程中的线程切换
            • 不会引起进程切换
              • 系统开销很=小
            • 同一进程内的各个线程间并发不需要切换进程运行环境和内存地址空间
          • 不同进程中的线程切换
            • 会引起进程切换
      • 地址空间和其他资源
        • 进程
          • 地址空间之间相互独立
        • 线程
          • 同一进程的各线程之间共享进程的资源
            • IO设备，内存地址空间、全局变量、进程已经打开的文件、定时器、信号量机构等
            • 带来不安全，若一个线程出错，则可能影响整个进程的运行
          • 某进程内的线程对其他进程不可见
      • 通信方面
        • 进程间通信
          • 需要进程同步和互斥手段的辅助
            • 保证数据的一致性
        • 同一进程各线程间通信
          • 共享内存地址空间
            • 可以直接读/写进程数据段（如全局变量）
          • 同一进程中的线程间通信甚至无需系统干预
      • 注
        • 引入线程后，进程已不是可执行的实体
        • 进程处于执行状态，实际上指进程中的线程处于执行状态，其他状态也类似
    • 线程的属性
      • 1. 不同线程可以执行相同的程序
      • 2. 一个线程被创建时便拥有了它的生命周期，直至终止
    • 线程的实现方式
      • 用户级线程
        • 早期的操作系统，只支持进程，不支持线程时使用
        • 用户级线程
          • 实现
            • 由应用程序通过线程库实现
              • 代码逻辑的载体
          • 线程管理工作
            • 应用程序负责
              • 所有的线程管理工作都由线程库应用程序负责
                • 包括线程切换的管理
          • 线程切换
            • 可以在用户态下完成，无需操作系统干预
          • 处理机分配的单位
            • CPU的调度单位任然是进程
              • 操作系统内核意识不到线程的存在
            • 操作系统给进程分配CPU时间
          • 用户级线程对用户不透明，对操作系统透明
            • 在用户看来，是有多个线程
          • 控制块
            • 用户级线程的控制块一般存放在用户空间的数据结构中
              • 如链表或数组
              • 由用户空间的线程库来管理
            • 操作系统只负责为每个进程建立一个进程控制块
        • 优点
          • 调度算法可以是进程专用的
          • 用户线程的实现与OS平台无关
          • 线程管理的系统开销小，效率高
            • 用户级线程的切换在用户空间即可完成
            • 线程转换不需要切换到内核空间
        • 缺点
          • 系统调用的阻塞
            • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。
            • 线程执行一个系统调用时，该进程的所有线程都会被阻塞
              • 内核只看到一个调度实体
          • 多线程应用不能利用多处理机进行多重处理
            • 内核给进程分配的只有一个cpu，进程中只有一个线程能执行
            • 多个线程不可在多核处理机上并行运行。
      • 内核级线程
        • 内核级线程
          • 处理机分配的单位
            • 内核级线程
              • 操作系统只“看得见”内核级线程
              • 运行机会的载体
              • 进程只作为分配资源的基本单位
          • 线程管理工作
            • 由操作系统内核完成
            • 线程调度、切换等工作都由内核负责
          • 线程切换
            • 在核心态下才能完成
        • 拥有多个内核级线程的进程阻塞的条件
          • 所有线程都处于阻塞状态（没有可运行线程）
        • 优点
          • 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。
          • 多线程可在多核处理机上并行执行。
        • 缺点
          • 线程管理的成本高，开销大
            • 一个用户进程会占用多个内核级线程
            • 同一进程中的线程切换，需要从用户态转到内核态进行
    • 多线程模型
      • 几个用户级线程映射到几个内核级线程
      • 多对一模型
        • 多个用户级线程映射到一个内核级线程。
          • 类似于用户级线程的实现方式
        • 处理机分配的单位
          • 内核级线程
            • 操作系统只“看得见”内核级线程
            • 一个进程只对应一个内核级线程，同一时刻这个进程只能被分配一个CPU的核心
        • 优点
          • 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
        • 缺点
          • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。
          • 多个线程不可在多核处理机上并行运行
      • 一对一模型
        • 一个用户级线程映射到一个内核级线程
          • 每个用户进程有与用户级线程同数量的内核级线程
        • 优点
          • 并发能力强
            • 当一个线程被阻塞后，别的线程还可以继续执行
          • 多线程可在多核处理机上并行执行
        • 缺点
          • 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
      • 多对多模型
        • n 个用户级线程映射到m 个内核级线程（n >= m）
          • 每个用户进程对应m 个内核级线程。
        • 克服了多对一模型并发度不高的缺点， 又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
    • 补充
      • 适合用多线程解决的业务场景
        • 可以将处理逻辑拆分成多个互不相干的部分
          • 每个线程负责几个请求
        • 计算量较大，需要高并发
        • 注
          • 都是需要快速响应的任务
            • eg，整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处理整个系统的键盘输入
• 2.2处理机调度
  • 调度的概念
    • 调度的基本概念
      • 处理机调度
        • 从就绪队列中按照一定的算法选择一个进程并将处理机分配给它
        • 实现进程的并发执行
    • 调度的层次
      • 作业调度/高级调度
        • 好几个程序需要启动，到底启动哪一个
        • 进程从创建态转换到就绪态
          • 从外存上处于后备队列的作业中挑选
          • 分配内存等必要资源，并创建进程（建立PCB）
          • 获得竞争处理机的权利
        • 注
          • 辅存（外存）——>内存
            • 外存调入内存
          • 作业调入时会建相应的PCB，作业调出时才撤销PCB
          • 每个作业只调度一次，调出一次
          • 后备队列在外存，就绪队列在内存
        • • 作业只被高级调度一次
            • （从磁盘调入内存，创建 初始进程
          • 初始进程可通过系统调用创建任意多个子进程
            • （不受作业调度限制）
        • • 作业:一个具体的任务
          • 用户向系统提交一个作业≈用户让操作系统启动一个程序(来处理一个具体的任务)
      • 中级调度/内存调度
        • 目的
          • 节约内存
        • 从挂起队列中选择合适的进程将其数据调回内存
          • 外存——>内存
        • 一个进程可能会被多次调出、调入内存
        • 挂起
          • 目的
            • 为减轻系统负载，提高资源利用率、系统吞吐量
          • 将数据从内存调出外存
            • 引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待
            • 等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存
          • 挂起状态
            • 暂时调到外存等待的进程状态
            • 分类
              • 就绪挂起
                • 创建态->就绪挂起
                  • 内存空间不够
                • 就绪态->就绪挂起
                  • 系统负载比较高，内存空间不够
              • 阻塞挂起
          • 挂起队列
            • 被挂起的进程PCB会被放到的挂起队列中
          • 注
            • PCB常驻内存
              • 不会一起调到外存
              • PCB中会记录进程数据在外存中的存放位置，进程状态等信息
              • 操作系统通过内存中的PCB来保持对各个进程的监控、管理
            • 区别阻塞
              • 阻塞态下进程映像还在内存中
                • 但都不能获得CPU服务
      • 低级调度/进程调度/处理机调度
        • 分配处理机
          • 从就绪队列中选取一个进程，分配处理机
          • 内存——>CPU
        • 操作系统中最基本的一种调度
          • 多道程序并发执行一定会用到
          • 一般的操作系统中都必须配置进程调度
      • 三种调度的对比
        • 
  • 进程调度的时机切换与过程
    • 需要进行进程调度与切换的情况
      • 当前运行的进程主动放弃处理机
        • 进程正常终止
        • 运行过程中发生异常而终止
        • 进程主动请求阻塞（如等待I/O）
      • 当前运行的进程被动放弃处理机
        • 分给进程的时间片用完
        • 有更紧急的事需要处理（如I/O中断）
        • 有更高优先级的进程进入就绪队列
    • 注
      • 中断处理结束后
        • 返回原程序
        • 或重新选择程序运行
          • 发生进程调度
          • 例如在时间片轮转调度中，时钟中断处理结束后，若当前进程的时间片用完，则会发生进程调度
          • 当前进程阻塞时，将其放入阻塞队列，若就绪队列不空，则调度新进程执行。
      • 在系统调用完成并返回用户态时能进行处理机调度
    • 不能进行进程调度与切换的情况
      • 在处理中断的过程中
        • 中断处理过程复杂，与硬件密切相关，很难 做到在中断处理过程中进行进程切换。
      • 进程在操作系统内核程序临界区中
      • 在原子操作过程中（原语）
    • 补充
      • 操作系统内核程序临界区和普通临界区
        • 内核程序临界区
          • 一般是用来访问某种内核数据结构的
            • 如就绪队列、内存分配表、设备控制块等
          • 需要关中断
          • 访问内核程序临界区期间不能进行调度与切换
            • （个人理解）进程调度相关的程序需要用到被临界区保护的资源
        • 普通临界区
          • 普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。
          • 访问的是用户进程共享的资源
            • 如共享内存区、文件、消息队列
            • 通常不涉及关中断指令
              • 特权指令，用户进程无权使用
            • 主要依赖软件同步机制来实现互斥访问
              • 如信号量、互斥锁
            • 这些机制在阻塞等待时允许进程调度和切换
              • 用户进程的同步问题不应该影响到整个系统的中断响应能力和调度能力
          • 访问普通临界区时可以进行调度与切换
    • 进程调度与进程切换的区别
      • 进程调度
        • 狭义的进程调度
          • 从就绪队列中选中一个要运行的进程
            • 可以是刚刚被暂停执行的进程
            • 也可能是另一个进程
              • 需要进程切换
        • 广义的进程调度
          • 包含选择一个进程和进程切换两个步骤。
      • 进程切换
        • 一个进程让出处理机，由另一个进程占用处理机的过程
    • 进程切换
      • 1. 对原来运行进程各种数据的保存
        • 保存到PCB
      • 2. 对新的进程各种数据的恢复
        • 从PCB中读出数据放入相应的寄存器中
        • 如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息
      • 并不是越频繁并发度越高
        • 进程切换有代价
        • 频繁的进程切换会使系统效率降低
          • 大部分时间都花在了进程切换上，而真正用于执行进程的时间减少
  • 进程调度方式
    • 非剥夺调度方式/非抢占方式
      • 只允许进程主动放弃处理机
        • 进程会一直运行直到该进程终止或主动要求进入阻塞态
      • 特点
        • 实现简单
        • 系统开销小
      • 缺点
        • 无法及时处理紧急任务
      • 适合于早期的批处理系统
    • 剥夺调度方式，又称抢占方式
      • 立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程
      • 特点
        • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能
      • 适合于分时操作系统、实时操作系统
  • 调度器、闲逛进程
    • 调度器/调度程序
      • 操作系统内核的一个重要的程序模块
      • 
        • ②、③由调度程序引起
        • 调度程序决定:
          • 让谁运行? -- -调度算法
          • 运行多长时间? --时间片大小
      • 调度时机-- -什么事件会触发“调度程序”?
        • 创建新进程
        • 进程退出
        • 运行进程阻塞
        • I/O中断发生(可能唤醒某些阻塞进程)
        • 非抢占式调度策略
          • 只有运行进程阻塞或退出才触发调度程序工作
        • 抢占式调度策略
          • 每个时钟中断或k个时钟中断会触发调度程序工作
      • • 不支持内核级线程的操作系统，
          • 调度程序的处理对象是进程
        • 支持内核级线程的操作系统，
          • 调度程序的处理对象是内核线程
    • 闲逛进程
      • 没有其他就绪进程时，运行闲逛进程(idle)
      • 实际系统中CPU永远不可能空闲，至少有一个闲逛进程可以运行
      • 闲逛进程的特性:
        • 优先级最低
        • 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
          • 周期性唤醒调度程序，检查是否有其他进程就绪
        • 能耗低
          • 0地址：不需要访问CPU的任何一个寄存器
  • 调度的基本准则
    • CPU利用率
      • 指CPU “忙碌”的时间占总时间的比例
      • 
      • 通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算
    • 系统吞吐量
      • 单位时间内完成作业的数量
      • 
    • 周转时间
      • （作业）周转时间= 作业完成时间– 作业提交时间
        • 单个作业的周转时间
      • 包括
        • 作业在外存后备队列上等待作业调度(高级调度)的时间
          • 只会有一个作业调度
        • 进程在就绪队列上等待进程调度(低级调度)的时间
          • 就绪态
        • 进程在CPU上执行的时间
          • 运行态
        • 进程等待I/O操作完成的时间
          • 阻塞态
        • 在一个作业的整个处理过程中，可能发生多次
      • 平均周转时间
        • 
          • 所有作业
      • 带权周转时间
        • 
        • • 带权周转时间必然≥1
          • 带权周转时间与周转时间都是越小越好
      • 平均带权周转时间
        • 
    • 等待时间
      • 进程/作业处于等待处理机状态时间之和
      • 等待时间越长，用户满意度越低。
      • 对于进程来说
        • 在等待I/O完成的期间进程也是在被服务的，所以不计入等待时间
        • 等待时间=周转时间-运行时间-I/O操作的时间
          • 进程建立后等待被服务的时间之和
      • 对于作业来说
        • 等待时间=建立进程后的等待时间+作业在外存后备队列中等待的时间
      • 作业等待时间和进程等待时间不同
      • 调度算法只会影响作业/进程的等待时间
        • 作业总共需要被CPU、I/O设备服务多久一般是确定不变的
      • 平均等待时间
        • 加和/作业数
    • 响应时间
      • 响应时间，指从用户提交请求到首次产生响应所用的时间。
  • 典型的调度算法
    • 适用于早期批处理系统
      • 注：其他条件相同时，默认选择先到达的运行
      • 先来先服务（FCFS, First Come First Serve）
        • 算法思想
          • 从“公平”的角度考虑
        • 算法规则
          • 按照作业/进程到达的先后顺序进行服务
        • 用于作业/进程调度
          • 作业调度
            • 考虑的哪个作业先到达后备队列；
          • 进程调度
            • 考虑的哪个进程先到达就绪队列
        • 是否可抢占？
          • 非抢占式的算法
        • 优缺点
          • 优点
            • 公平、算法实现简单
          • 缺点
            • 排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大
            • FCFS算法对长作业有利，对短作业不利
        • 是否会导致饥饿
          • 否
      • 短作业优先（SJF, Shortest Job First）
        • 算法思想
          • 追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
        • 算法规则
          • 最短的作业/进程优先得到服务
            • 最短”，是指要求服务时间最短
          • 每次调度时选择当前已经到达且运行时间最短的作业/进程
        • 是否可抢占？
          • SJF和SPF是非抢占式的算法。
            • 进程调度
              • 短进程优先（SPF, Shortest Process First）算法
          • 也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
        • 最短剩余时间优先算法
          • 调度时机
            • 有进程加入就绪队列改变时
            • 一个进程完成时
          • 如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。
        • 优缺点
          • 优点
            • “最短的”平均等待时间、平均周转时间
              • 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，最短剩余时间优先算法更优，但相比于其他算法(如FCFS)，SJF依然可以获得较少的平均等待时间、平均周转时间
          • 缺点
            • 不公平。对短作业有利，对长作业不利。
            • 可能产生饥饿现象。
            • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
        • 是否会导致饥饿（某进程/作业长期得不到服务）
          • 会。如果源源不断地有短作业/进程到来，可能使长作业/进 程长时间得不到服务，产生“饥饿”现象。
          • 如果一直得不到服务，则称为“饿死”
        • 注
          • 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
          • 如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项
      • 高响应比优先（HRRN,Highest Response Ratio Next）
        • 算法思想
          • 要综合考虑作业/进程的等待时间和要求服务的时间
        • 算法规则
          • 在每次调度时先计算各个作业/进程的响应比
            • 选择响应比最高的作业/进程为其服务
          • 
            • 响应比≥1
        • 调度时机
          • 当前运行的作业/进程主动放弃处理机时
        • 是否可抢占？
          • 非抢占式的算法
        • 优缺点
          • 优点
            • 综合考虑了等待时间和运行时间（要求服务时间）
            • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
            • 要求服务时间相同时，等待时间长的优先（FCFS 的优点）
            • 对于长作业来说，随着等待时间越来越久，其响应比也会 越来越大，从而避免了长作业饥饿的问题
        • 是否会导致饥饿
          • 不会
      • 注
        • 这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标
        • 不关心“响应时间”，也并不区分任务的紧急程度
        • 对用户来说，交互性很差
        • 这三种算法一般适合用于早期的批处理系统
        • 三种算法即可用于作业调度，又可用于进程调度
    • 交互式系统
      • 时间片轮转（RR, Round-Robin）
        • 算法思想
          • 公平地、轮流地为各个进程服务
            • 让每个进程在一定时间间隔内都可以得到响应
        • 算法规则
          • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片
          • 默认新到达的进程先进入就绪队列
            • 根据题目规则
        • 用于作业/进程调度
          • 用于进程调度
            • 只有作业放入内存建立了相应的进程后，才能被分配处理机时间片
        • 是否可抢占？
          • 抢占式算法
          • 由时钟装置发出时钟中断来通知CPU时间片已到
          • 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
        • • 如果时间片太大
            • 退化为先来先服务
              • 增大进程响应时间
            • 运行结束时间片没有用完会主动放弃处理机
              • 调度发生在进程主动放弃处理机时
          • 时间片太小
            • 进程切换有时间代价（保存/恢复运行环境）
            • 实际进程运行时间少
        • 优缺点
          • 优点
            • 公平；响应快，适用于分时操作系统
              • 更关心响应时间
          • 缺点
            • 增大了系统开销
              • 高频率的进程切换
            • 不区分任务的紧急程度
        • 是否会导致饥饿
          • 不会
        • 通用操作系统
          • 使用时间片轮转调度算法
          • 用户运行程序并不需要预先预订运行时间
      • 优先级调度算法
        • 算法思想
          • 根据任务的紧急程度来决定处理顺序
        • 算法规则
          • 每个作业/进程有各自的优先级
          • 每次调度时选择当前已到达且优先级最高
        • 用于作业/进程调度
          • 既可用于作业调度，也可用于进程调度。甚至，还会用于I/O调度
        • 注意区分
          • 优先数 优先级
        • 是否可抢占？
          • 抢占式、非抢占式都有
            • 非抢占式
              • 只需在进程主动放弃处理机时进行调度即可，
            • 抢占式
              • 调度时机
                • 进程主动放弃处理机时
                • 就绪队列变化时，检查是否会发生抢占。
        • 优缺点
          • 优点
            • 用优先级区分紧急程度、重要程度
              • 适用于实时操作系统
            • 可灵活地调整对各种作业/进程的偏好程度（被服务的机会）
          • 缺点
            • 若源源不断地有高优先级进程到来，则可能导致饥饿
        • 是否会导致饥饿
          • 会
        • 根据优先级是否可以动态改变
          • 就绪队列未必只有一个，可以按照不同优先级来组织，也可以把优先级高的进程排在更靠近队头的位置
          • 静态优先级：创建进程时确定，之后一直不变。
          • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
        • 如何合理地设置各 类进程的优先级？
          • 系统进程优先级高于用户进程
          • 前台进程优先级高于后台进程
          • 操作系统更偏好I/O型进程（或称I/O繁忙型进程）
            • 原因：
              • I/O设备和CPU可以并行工作
              • 如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作
              • 资源利用率、系统吞吐量都会得到提升
            • 注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
        • 如果采用的是动态优先 级，什么时候应该调整？
          • 可以从追求公平、提升资源利用率等角度考虑
          • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
          • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
          • 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
            • 提升系统资源利用率、系统吞吐量……
            • I/O繁忙型进程
      • 多级反馈队列调度算法
        • 算法思想
          • 对其他调度算法的折中权衡
        • 算法规则
          • 1||| 设置多级就绪队列
            • 各级队列优先级由高到低，时间片从小到大
          • 2||| 新进程到达时先进入第1级队列
            • 按FCFS原则排队等待被分配时间片
            • 若用完时间片进程还未结束，则进程进入下一级队列队尾。
            • 如果此时已经是在最下级的队列，则重新放回该队列队尾
            • 注
              • 每个进程刚进来时都会被优先处理
          • 3||| 3. 只有第k 级队列为空时，才会为k+1 级队头的进程分配时间片
          • 4||| 被抢占处理机的进程重新放回原队列队尾
          • 
        • 用于作业/进程调度
          • 用于进程调度
        • 是否可抢占？
          • 抢占式的算法。
            • 在k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程则新进程会抢占处理机
            • 原来运行的进程放回k 级队列队尾。
        • 优缺点
          • 优点
            • 对各类型进程相对公平（FCFS的优点）；
            • 每个新到达的进程都可以很快就得到响应（RR的优点）；
            • 短进程只用较少的时间就可完成（SPF的优点）；
            • 不必实现估计进程的运行时间（避免用户作假）；
            • 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程
              • 拓展:可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级
            • 使各个作业用户都满意
        • 是否会导致饥饿
          • 会
      • 注
        • 这三种算法适合用于交互式系统。
          • 交互式操作系统
            • 包括分时操作系统、实时操作系统等
            • 更注重系统的响应时间、公平性、平衡性等指标
          • UNIX使用的就是多级反馈队列调度算法
    • 多级队列调度
      • 
      • 注
        • 系统中按进程类型设置多个就绪队列，进程创建成功后插入某个队列
          • 每个队列优先级不同
          • 每一次调度发生时要选中一个队列
      • • 队列之间可采取固定优先级，或时间片划分
          • 每次调度选哪个队列
          • 固定优先级:高优先级空时低优先级进程才能被调度
          • 时间片划分:如三个队列分配时间50%、40%、 10%
            • 固定时间内任何一个进程都至少被响应一次
        • 各队列可采用不同的调度策略，如:
          • 系统进程队列采用优先级调度
          • 交互式队列采用RR
            • 时间片轮转
          • 批处理队列采用FCFS
            • 先来先服务
    • 多处理机调度
      • • 单处理机调度:
          • 只需决定让哪个就绪进程优先上处理机即可。
        • 多处理机调度
          • 用调度算法决定让哪个就绪进程优先上处理机
          • 还需决定被调度的进程到底上哪个处理机
      • 目标
        • 负载均衡
          • 尽可能让每个CPU都同等忙碌
        • 处理机亲和性会
          • 尽量让一个进程调度到同一个CPU上运行，以发挥CPU中缓存的作用(Cache)
      • 公共就绪队列
        • 所有CPU共享同一个就绪进程队列(位于内核区)
          • 将就绪进程的PCB用队列的形式连在一起
        • 每个CPU空闲时运行调度程序，根据某种调度算法从公共就绪队列中选择一个进程运行
        • 每个CPU访问公共就绪队列时需要上锁(确保互斥)
        • 优点
          • 可以天然地实现负载均衡
        • 缺点
          • 各个进程频繁地换CPU运行，“亲和性”不好
        • 如何提升处理机亲和性?
          • 软亲和:
            • 由进程调度程序尽量保证“亲和性“
          • 硬亲和
            • 由用户进程通过系统调用，主动要求操作系统分配固定的CPU，确保“亲和性
          • 可混用
      • 私有就绪队列
        • 每个CPU都有一个私有就绪队列
        • CPU空闲时运行调度程序，从私有就绪队列中选择一个进程运行
        • 如何实现负载均衡?
          • 推迁移(Push)策略:
            • 一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌CPU的就绪队列中“推”一些就绪进程到空闲CPU的就绪队列
            • 推迁移=有一个包工头专门负责派活
          • 拉迁移(pull)策略:
            • 每个CPU运行调度程序时，周期性检查自身负载与其他CPU负载。如果一个CPU负载很低，就从其他高负载CPU的就绪队列中“拉”一些就绪进程到自己的就绪队列
            • 拉迁移=一群互帮互助的同事(看到其他同事很忙主动揽活过来，分担任务)
          • 如何提升处理机亲和性?
            • 私有就绪队列天然地实现了“处理机亲和性
            • 同样可以采用系统调用的方式保证硬亲和
• 2.3进程同步
  • 概念
    • 临界资源
      • 一个时间段内只允许一个进程使用的资源
        • eg
          • 摄像头、打印机
          • 许多变量、数据、内存缓冲区
      • 各进程需要互斥地访问临界资源
        • 不同线程对同一个进程内部的共享变量的访问才有可能需要进行互斥
          • 读操作可以不互斥
        • 不同进程的线程、代码段或变量不存在互斥访问的问题，同一个线程内部的局部变量（私有变量）也不存在互斥访问的问题
      • 临界资源的访问过程
        • 进入区
          • 检查是否可进入临界区
            • 可进入
              • 设置正在访问临界资源的标志
                • 上锁
                • 阻止其他进程同时进入临界区
        • 临界区/临界段
          • 进程中实际访问临界资源的代码段
          • 可称为“临界段”
          • 一个进程对临界区上锁的时间增长不利于各个进程交替使用临界区资源
          • 让临界区的代码尽可能的短，
            • 不建议放在PV操作之间影响系统效能
        • 退出区
          • 解除正在访问临界资源的标志
            • 解锁
          • 进入区和退出区是负责实现互斥的代码段。
        • 剩余区
          • 代码中的剩余部分
      • 注意
        • 共享环形缓冲区不需要互斥访问
        • 循环队列有队头指针和队尾指针
    • 同步
      • 进程之间的直接制约关系
        • 进程有一定的先后次序（合作）
    • 互斥
      • 进程之间的间接制约关系
      • 为了实现对临界资源的互斥访问，需要遵循以下原则
        • 1. 空闲让进
          • 临界区空闲时，可以允许一个请求进入临界区的进程立即进入
        • 2. 忙则等待
          • 已有进程进入临界区时，其他试图进入临界区的进程必须等待
        • 3. 有限等待
          • 对请求访问的进程，应保证能在有限时间内进入临界区
          • 保证不会饥饿
        • 4. 让权等待
          • 当进程不能进入临界区时，应立即释放处理机
          • 防止进程忙等
    • 补充
      • 可重入代码/纯代码/可重入编码
        • 不会修改任何数据/变量的代码
        • 允许多个进程同时访问的代码
          • 任意一个进程在调用此段代码时都以同样的方式运行
          • 进程在运行过程中被中断后再继续执行，其执行结果不受影响
        • 不属于临界资源
        • 共享程序段可能同时被多个进程使用，所以必须可重入编码，否则无法实现共享的功能
      • 不可重入代码
        • 会修改某些数据
        • 是不能共享，必须互斥访问
          • 如，一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致
  • 实现临界区互斥的基本方法
    • 软件实现方法
      • 单标志法
        • 算法思想
          • 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程
          • 每个进程进入临界区的权限只能被另一个进程赋予
            • 除了初值以外，对方用了自己才能用
          • turn
            • 表示当前允许进入临界区的进程号
        • 实现
          • 在进入区只做“检查"，不“上锁”
          • 在退出区把临界区的使用权转交给另一个进程
            • 既给另一进程“解锁"，又给自己“上锁
        • 
        • turn 的初值为0
          • 开始只允许0 号进程进入临界区
          • 若P1 先上处理机运行，则会一直卡在⑤
          • P1 的时间片用完，发生调度，切换P0 上处理机运行。
          • 代码① 不会卡住P0，P0 可以正常访问临界区
          • 在P0 访问临界区期间即时切换回P1，P1依然会卡在⑤
          • 只有P0 在退出区将turn 改为1 后，P1才能进入临界区。
        • 主要问题
          • 违背“空闲让进”原则
            • 用过一次后，要对方用完了自己才能再次使用
      • 双标志法
        • 算法思想
          • 进程在进入临界区前检查当前有没有别的进程想进入临界区
            • 没有
              • 把自身对应的标志flag[i] 设为true
              • 开始访问临界区
          • 布尔型数组flag[]
            • 数组中各个元素用来标记各进程想进入临界区的意愿
            • flag[0] = ture意味着0 号进程P0 现在想要进入临界区
          • 在进入区先“检查"后“上锁"，退出区“解锁"
        • 
        • 主要问题
          • 违反“忙则等待”原则
            • 在并发情况下可能出现两个进程同时访问临界区
            • “检查”和“上锁”前后可能发生进程切换（进程调度）
      • 双标志后检查法
        • 算法思想
          • 在进入区先“上锁"后“检查"，退出区“解锁"
        • 
        • 解决了忙则等待
        • 主要问题
          • 违背了“空闲让进”和“有限等待”原则
          • 会因各进程都长期无法访问临界资源而产生“饥饿”现象
          • 不是死锁
      • Peterson 算法
        • 算法思想
          • 在进入区“主动争取一主动谦让一检查对方是否想进、己方是否谦让”
          • flag[]
            • 进程想进入临界区的意愿
          • turn
            • 表示优先让哪个进程进入临界区
              • turn设为对方的编号
              • 最后turn的失去优先权
        • 
        • 用软件方法解决了进程互斥问题
          • 遵循了空闲让进、忙则等待、有限等待三个原则
        • 主要问题
          • 未遵循让权等待的原则
          • 进程进入不了临界区依旧被卡在while循环处，在CPU中执行
      • 软件实现的互斥离不开表示谦让，表示自己想要访问临界资源的意愿这两个变量
    • 硬件实现方法
      • 中断屏蔽方法
        • 利用“开/关中断指令”实现
          • 关中断
            • 关中断后即不允许当前进程被中断，也必然不会发生进程切换
          • 开中断
            • 当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区
          • 特权指令
            • 原语实现思想
        • 优点
          • 简单、高效
        • 缺点
          • 不适用于多处理机
            • 关中断指令只对执行关中断的处理机有用
          • 只适用于操作系统内核进程，不适用于用户进程
            • 开/关中断指令只能运行在内核态
            • 这组指令如果能让用户随意使用会很危险
      • 硬件指令方法
        • TestAndSet指令
          • 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令
          • 用硬件实现的，“上锁”和“检查”操作执行的过程不允许被中断
            • 原子操作
              • 不需要额外的关中断来实现
            • TSL 指令实现原子性的原理是，执行 TSL 指令的 CPU 锁住内存总线，以禁止其他 CPU 在本指令结束之前访问内存
          • 指令的功能描述
            • 
            • old 记录是否已被上锁
              • 原来lock的值
            • lock
              • 表示当前临界区是否被加锁
              • true 表示已加锁
              • false 表示未加锁
          • 实现进程互斥
            • 若刚开始 lock 是 false
              • TSL 返回的old 值为 false
              • while 循环不满足
                • 直接跳过循环，进入临界区
            • 若刚开始 lock 是 true
              • TLS 返回的值为 true
              • while 循环满足
                • 一直循环
                • 直到当前访问的临界区的进程在退出区进行“解锁”
                  • 时间片用完
          • 优点
            • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
            • 适用于多处理机环境
          • 缺点
            • 不满足让权等待
              • 暂时无法进入临界区的进程会占用CPU并循环执行TSL指令
              • “忙等”
                • 不断while循环
        • Swap指令
          • 也叫 Exchange 指令，或简称 XCHG 指令
          • 用硬件实现，执行的过程不允许被中断
          • 指令的功能描述
            • Swap指令
          • 实现进程互斥
          • 优缺点同TSL
        • Swap 和 TSL
          • 先记录下此时临界区是否已经被上锁
            • 记录在old 变量上
          • 再将上锁标记 lock 设置为 true
          • 最后检查 old
            • 如果old 为 false
              • 之前没有别的进程
              • 可跳出循环，进入临界区
      • 硬件方法实现进程同步时不能实现让权等待
    • 互斥锁
      • 概念
        • 实现互斥
          • 解决临界区最简单的工具
      • 特点
        • bool型变量
          • 只有true和false
          • 表示当前已上锁，没上锁
      • available
        • 每个互斥锁有一个布尔变量available,表示锁是否可用。
          • 如果锁是可用的，调用acqiure(）会成功，且锁不再可用
          • 当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
      • • 一个进程在进入临界区时应获得锁
          • acquire()
        • 在退出临界区时释放锁
          • release(）
        • acquire()或release(）的执行必须是原子操作， 因此互斥锁通常采用硬件机制来实现。
        • 
      • 缺点
        • 忙等待
          • 当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。
            • 当多个进程共享同一CPU时，浪费了CPU周期
          • 互斥锁通常用于多处理器系统
            • 一个线程可以在一个处理器上等待，不影响其他线程的执行。
      • 自旋锁：
        • 解决进程互斥问题
        • 都有忙等问题，违法让权等待原则
        • 需要连续循环忙等的互斥锁，都可称为自旋锁(spin lock)
          • 如TSL指令、swap指令、单标志法
          • 不是只有上锁才叫互斥锁，只要保证了临界区互斥访问的都是
      • 特性
        • 需忙等
          • 进程时间片用完才下处理机
          • 违反“让权等待”
        • 常用于多处理器系统
          • 一个核忙等，其他核照常工作，并快速释放临界区
        • 不太适用于单处理机系统
          • 忙等的过程中不可能解锁
      • 优点:
        • 等待期间不用切换进程上下文
        • 多处理器系统中，若上锁的时间短，等待代价很低
    • 信号量
      • 信号量
        • 一个变量
          • 可以整数，也可以是更复杂的记录变量
        • 信号量的值=这种资源的剩余数量
          • 信号量的值如果小于0，说明此时有进程在等待这种资源
          • 比如：系统中只有一台打印机，就可以设置一个初值为 1
        • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作
          • 实现了进程互斥、进程同步
          • 只有信号量涉及原语关中断，不是后续对临界资源的访问都涉及关中断，因此后续访问过程可以发生调度
      • wait(S) 原语和 signal(S) 原语
        • wait(s)、signal(s)也可以记为 P(S)、V(S)
          • 常简称为P、V操作
        • 用于实现系统资源的“申请”和“释放"
          • 对信号量进行操作
        • 信号量 S
          • 函数调用时传入的一个参数
      • 整型信号量
        • 用一个整数型的变量作为信号量
          • 用来表示系统中某种资源的数量
        • 与普通整数变量的区别:
          • 对信号量的操作只有三种：初始化、P操作、V操作
        • wait和signal的操作描述
        • 执行过程
        • 缺点
          • 违背“让权等待”原则，会发生“忙等”
      • 记录型信号量
        • 用记录型数据结构表示的信号量
          • 可以表示任何关系，比如可以用记录型信号量表示产品A和产品B之间的差值
        • 记录型信号量的定义
          • 
          • S.value
            • 表示某种资源数
          • S.L
            • 指向等待该资源的队列
          • 如果题目没特别说明，可以把信号量的声明简写成这种形式
          • 只要用semaphore信号量，表明是记录型信号量，不是整型信号量
          • semaphore初值可以不是1
            • 表示资源数量
            • 如果题目资源<M，则semaphore=M-1
        • 记录型信号量实现
          • 系统资源的“申请"和“释放"
          • 实现进程互斥、进程同步
        • wait操作
          • 进程请求一个单位的该类资源
            • 剩余资源数不够
              • 使用block原语进行自我阻塞
                • 运行态进入阻塞态
              • 主动放弃处理机
                • 挂到信号量s的等待队列(即阻塞队列)中
          • P 操作中，一定是先 S.value--
            • 天然阻塞
              • 当消费者需要连续取出多个数据时不需要判断数据是否够取，因为不够会阻塞，直到够为止。
        • signal操作
          • 进程释放一个单位的该类资源
          • 释放资源后，若还有别的进程在等待这种资源，则使用wakeup 原语
            • 唤醒等待队列中的一个进程
            • 该进程从阻塞态变为就绪态
          • V 操作中，一定是先 S.value++
            • 因此小于等于能取到等号
            • V操作是没有上限的，资源数不断增加
        • 该机制遵循了“让权等待”原则，不会出现“忙等”现象。
        • 注：
          • 若考试中出现 P(S)、V(S) 的操作，除非特别说明，否则默认S 为记录型信号量。
            • 不会忙等，而是进入阻塞状态
          • P、V操作必须成对出现
          • 对不同的临界资源需要设置不同的互斥信号量。
      • 信号量机制
        • 信号量机制实现进程互斥
          • 一个时间段内只允许一个进程使用
          • 特点
            • 信号量初值设置为1
            • 在同一进程中进行一对PV操作
          • 步骤
            • 划定临界区
              • ( 如:对临界资源打印机的访问就应放在临界区)
            • 设置互斥信号量mutex，初值为1
              • mutex表示“进入临界区的名额”
            • 在进入区P(mutex)- -- - 申请资源
            • 在退出区V(mutex)--释放资源
        • 信号量机制实现进程同步
          • 进程同步
            • 必须保证“一前一后”执行的两个操作（或两句代码）
          • 理解
            • 信号量s代表“某种资源”
              • 刚开始没有这种资源
              • P2需要使用这种资源，而又只能由P1产生这种资源
          • 特点
            • 同步信号量S初值为0
              • 用PV操作实现进程同步时，信号量的初值应根据具体情况来确定
            • 同步信号量初始值根据可用资源数来确定
              • 若期望的消息尚未产生
                • 初值应设为0
              • 若期望的消息已存在
                • 则信号量的初值应设为一个非0的正整数
                  • 资源数确定
              • 比如缓冲区empty=8，full=0
                • 分别表示当前缓冲区的剩余容量和多少个可供消费的产品
            • 在其中一个进程中执行P，另一进程中执行V
            • 前V后P
              • 在“前操作”之后执行V(S)
              • 在“后操作”之前执行 P(S)
          • 进程同步
            • 代码4要在代码1，2之后执行
              • 
        • 信号量机制实现前驱关系
          • 
            • 
          • 多级同步问题
          • 进程执行的前趋关系实质上是指进程的同步关系
          • 步骤
            • 1. 要为每一对前驱关系各设置一个同步信号量
              • ？几条线几个同步信号量
                • 初值都为0
            • 2. 在“前操作”之后对相应的同步信号量执行V 操作
            • 3. 在“后操作”之前对相应的同步信号量执行P 操作
        • 多个资源的问题
          • 有多少资源就把信号量初值设为多少
          • 申请资源时进行P操作，释放资源时进行v操作即可
        • 终极总结（408信号量题三步法）
          • 数条件
            • 资源型阻塞
              • 找出所有需要 阻塞等待的条件 （如空/满、其他进程完成）
              • 尤其是当有多个缓冲区/多个盘子，全满全空要阻塞的进程不同
                • 实现同步的信号量
            • 顺序型阻塞
              • 识别哪个动作必须在哪个动作之后发生
                • 动作时序上的同步关系
                • ds,所有通知响应类交互都要动作完成信号量
                • 本质：代码4要在代码1，2之后执行
              • 营业员叫号，顾客接受服务
          • 加互斥
            • 只要修改共享资源，必加mutex
            • 共享访问的都要互斥
              • 数据本身
              • 访问个数的计数器
                • count++的操作虽然正确，但实际上并发运行的进程都因为自己是进入时的count
          • 查顺序
            • 同步P在前，互斥P在后；V操作顺序任意
      • 管程
        • 为什么会出现管程
          • 问题
            • 信号量机制的不足
              • 程序编写困难，易出错
          • 方案
            • 在程序设计语言中引入管程成分
            • 实现一种高级同步机制
          • 管程是进程同步工具，解决信号量机制大量同步操作分散的问题
            • 用了封装的思想
        • 解决问题
          • 同步
            • 设置条件变量及等待/唤醒操作以解决
          • 互斥
            • 由编译器负责保证
              • 由编译器负责实现各进程互斥地进入管程中的过程
          • 实现进程的同步和互斥
        • 定义
          • 是一个特殊的软件模块
            • 管程是被进程调用的，管程是语法范围，无法创建和撤销
              • 静态的
          • 共享资源的数据结构+其上定义的一组过程
            • 1. 局部于管程的共享数据结构说明；
              • 如共享访问的缓冲区可以用数据结构来表示缓冲区
            • 2. 对该数据结构进行操作的一组过程；
              • 能为并发进程在该数据结构上所执行
                • 访问这些共享数据的“入口
              • 一组过程/操作——函数
                • 管程提供的特定“入口"
              • 如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区
              • 这组操作能同步进程并改变管程中的数据。
            • 3. 对局部于管程的共享数据设置初始值的语句；
              • 初始化
            • 4. 管程有一个名字。
        • 条件变量
          • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题
            • 将阻塞原因定义为条件变量
          • 条件变量相当于定义了一个等待队列
          • 对条件变量只有两种操作
            • x.wait
              • 当x对应的条件不再满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列/阻塞队列，并释放管程
            • x.signal
              • 当x对应的条件发生变化时，调用x.signal,唤醒因为x条件而阻塞的进程
          • 注
            • 各个进程不能直接访问条件变量
              • 想要访问只能通过管程中定义的函数
            • wait和signal只实现了对进程的阻塞或者唤醒，并不会对条件变量的值进行修改和检查
          • 条件变量与信号量的比较
            • 都实现了进程同步
              • 可以实现进程的阻塞和唤醒
            • 信号量有具体的值
            • 条件变量是没有值的
              • 仅实现了排队等待的功能
              • 在管程中剩余资源数用共享数据结构记录
        • 管程的基本特征
          • 进程只能通过调用管程中的过程来间接地访问管程中的数据结构
            • 局部于管程的数据只能被局部于管程的过程所访问；
            • 管程中定义的共享数据结构只能被管程中定义的函数所修改
            • 修改数据只能调用管程中的函数间接修改数据结构
          • 任何时候只能有一个进程在管程中执行
            • 互斥访问
              • 各个进程对管程调用的互斥性
              • 共享数据结构也被互斥访问
                • 实现各进程需要互斥地访问共享缓冲区
            • 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入
            • 如果多个进程都想调用管程里的函数，管程的特性天然地会保证每一个时刻最多只有一个进程正在使用管程里的函数
        • 用管程实现生产者和消费者问题
          • 
          • 
            • insert函数：把生产者进程生产的产品放到缓冲区
          • 
            • remove函数：从缓冲区里取走一个产品，并且返回给消费者进程
          • 程序员可以用某种特殊的语法定义一个管程(比如: monitor ProducerConsumer ... end monitor;)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。
  • 经典同步问题
    • 生产者消费者问题
      • 问题描述
        • 系统中有一组生产者进程和一组消费者进程
          • “产品”理解为某种数据
          • 生产者、消费者共享一个初始为空、大小为n的缓冲区。
          • • 生产者进程每次生产一个产品放入缓冲区
            • 消费者进程每次从缓冲区中取出一个产品并使用
        • 同步关系
          • 缓冲区没满→生产者生产
          • 缓冲区没空→消费者消费
        • 互斥关系
          • 缓冲区是临界资源，各进程必须互斥地访问。
      • 考虑两种极端状态
        • 全满
          • 生产者阻塞，入阻塞队列
        • 全空
          • 消费者阻塞，入阻塞队列
      • PV操作题目分析步骤
        • 1. 关系分析
          • 找出题目中描述的各个进程，分析它们之间的同步、互斥关系
        • 2. 整理思路
          • 根据各进程的操作流程确定P、V操作的大致顺序
        • 3. 设置信号量
          • 并根据题目条件确定信号量初值。
          • 互斥信号量初值一般为1
          • 同步信号量的初始值要看对应资源的初始值是多少
      • 具体算法
        • 
        • 
          • 
      • 顺序
        • 实现互斥的P操作一定要在实现同步的P操作之后
          • (死锁问题)
        • V操作不会导致进程阻塞，因此两个操作顺序可以交换。
    • 多生产者消费者问题
      • 问题描述
        • 桌子上有一只盘子
          • 每次只能向其中放入一个水果
        • • 爸爸专向盘子中放苹果
            • 儿子专等着吃盘子中的橘子
          • 妈妈专向盘子中放橘子
            • 女儿专等着吃盘子中的苹果
        • 只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。
        • 仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
      • 分析
        • 互斥关系
          • 对缓冲区（盘子）的访问要互斥地进行
          • mutex=1
          • 在临界区前后分别PV
        • 同步关系
          • 1. 父亲将苹果放入盘子后，女儿才能取苹果
          • 2. 母亲将橘子放入盘子后，儿子才能取橘子
          • 3. 只有盘子为空时，父亲或母亲才能放入水果
            • 考虑某个事件发生在某个进程之前，而不是某个行为发生在前
          • 一前一后，前V后P
      • 具体算法
        • semaphore mutex = 1; //实现互斥访问盘子（缓冲区） semaphore apple = 0; //盘子中有几个苹果 semaphore orange = 0; //盘子中有几个橘子 semaphore plate = 1; //盘子中还可以放多少个水果
          • apple和orange取代了full变量，因此不需要full
        • dad () { while(1){ 准备一个苹果; P(plate); P(mutex); 把苹果放入盘子; V(mutex); V(apple); } }
          • mom (){ while(1){ 准备一个橘子; P(plate); P(mutex); 把橘子放入盘子; V(mutex); V(orange); } }
            • daughter (){ while(1){ P(apple); P(mutex); 从盘中取出苹果; V(mutex); V(plate); 吃掉苹果; } }
              • son (){ while(1){ P(orange); P(mutex); 从盘中取出橘子; V(mutex); V(plate); 吃掉橘子; }
        • 注
          • 即使不设置专门的互斥变量mutex，也不会出现可多个进程同时访 互问盘子的现象
          • 原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。
            • 因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…
      • 注
        • 在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能，但不绝对
          • 建议:在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定 会互斥地访问缓冲区。
        • 生产者消费者问题遇到缓冲区大于1的时候必须设置一个互斥信号量mutex来保证各个进程可以互斥地访问缓冲区
          • 防止数据的覆盖
        • 缓冲区大小不为1时，生产者进程即可能唤醒消费者，又可能唤醒其他生产者，互斥访问缓冲区，消费者进程也一样。
    • 读者-写者问题
      • 互斥
      • 互斥问题
      • 问题描述
        • 有读者和写者两组并发进程，共享一个文件
          • ①允许多个读者可以同时对文件执行读操作；
          • ②只允许一个写者往文件中写信息；
          • ③任一写者在完成写操作之前不允许其他读者或写者工作；
          • ④写者执行写操作前，应让已有的读者和写者全部退出。
        • • 两类进程:写进程、读进程
          • 互斥关系:
            • 写进程一写进程
            • 写进程一读进程
            • 互斥访问count计数器
            • 两类共享资源，数据本身以及计数器
      • 算法
        • 
      • 核心思想
        • 设置了一个计数器 count
          • 记录当前正在访问共享文件的读进程数
          • 用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
            • 实现读者和读者不互斥的问题
          • 进程切换依然存在，但各个进程对count的访问互斥，同一时刻只要一个变量对count进行检查和赋值操作
        • 对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。
      • 算法2， 解决写进程饥饿问题
        • 
        • 信号量有排队功能
        • 不是真正的“写优先”，而是相对公平的先来先服务原则。有的书上把这种算法称为“读写公平法”
          • 写者不会饥饿
    • 哲学家进餐问题
      • 算法描述
        • 一张圆桌上，当哲学家饥饿时，试图拿起左、右两根筷子（一根一根地起）。如果筷子已在他人手上，则需等待
        • 饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
      • 关键
        • 解决进程死锁。
        • 这些进程之间只存在互斥关系
          • 每个进程都需要同时持有两个临界资源，因此有“死锁”问题的隐患。
      • 解决什么类型问题
        • 遇到了一个进程需要同时持有多个临界资源的情况
        • 参考哲学家问题的思想
        • 分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。
        • 可以参考哲学家就餐问题解决死锁的三种思路。
      • • 如果5个哲学家并发地拿起了自己左手边的筷子..
        • 每位哲学家循环等待右边的人放下筷子(阻塞) 发生“死锁’
      • 防止死锁的发生
        • 可以对哲学家进程施加一些限制条件
        • ①比如最多允许四个哲学家同时进餐。
          • 这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
          • semaphore chopstick[5]={1,1,1,1,1}; semaphore count=4; // 设置一个count，最多有四个哲学家可以进来 void philosopher(int i) { while(true) { think(); wait(count); //请求进入房间进餐 当count为0时 不能允许哲 学家再进来了 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[i]); //释放左手边的筷子 signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(count); //离开饭桌释放信号量 } }
        • ②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子
          • 而偶数号哲学家刚好相反
          • 用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。
          • 这就避免了占有一支后再等待另一只的情况。
          • semaphore chopstick[5]={1,1,1,1,1}; void philosopher(int i) { while(true) { think(); if(i%2 == 0) //偶数哲学家，先右后左。 { wait (chopstick[(i + 1)%5]) ; wait (chopstick[i]) ; eat(); signal (chopstick[(i + 1)%5]) ; signal (chopstick[i]) ; } else //奇数哲学家，先左后右。 { wait (chopstick[i]) ; wait (chopstick[(i + 1)%5]) ; eat(); signal (chopstick[i]) ; signal (chopstick[(i + 1)%5]) ; } } }
        • ③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
          • 各哲学家拿筷子这件事必须互斥的执行。
            • 一个个地拿起筷子
          • 这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。
          • 
      • semaphore chopsticks[n];是被允许的，伪代码
• 2.4死锁
  • 死锁的概念
    • 死锁的定义
      • 在并发环境下各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
      • 死锁、饥饿、死循环
        • 同
          • 都是进程无法顺利向前推进的现象(故意设计的死循环除外)
        • 区别
          • 死锁
            • 一定是“循环等待对方手里的资源”导致的
            • 特点
              • 如果有死锁现象
                • 那至少有两个或两个以上的进程同时发生死锁
              • 发生死锁的进程一定处于阻塞态
          • 饥饿
            • 由于长期得不到想要的资源
            • 特点
              • 可能只有一个进程发生饥饿
              • 发生饥饿进程的可能状态
                • 阻塞态
                  • 如长期得不到需要的I/O设备
                • 就绪态
                  • 长期得不到处理机
                    • 短进程优先
          • 由于操作系统分配资源的策略不合理导致
            • 是管理者（操作系统）的问题
          • 死循环
            • 某进程执行过程中一直跳不出某个循环的现象
              • 程序逻辑bug
              • 程序员故意设计
            • 特点
              • 可能只有一个进程发生死循环
              • 可以上处理机运行
                • 可以是运行态
                  • 区别：死锁和饥饿进程一定不处于运行态
                • 只不过无法像期待的那样顺利推进。
            • 由代码逻辑的错误导致
              • 是被管理者的问题
    • 死锁产生的必要条件
      • 互斥条件
        • 必须互斥使用的资源的争抢才会导致死锁
          • 如哲学家的筷子、打印机设备
        • 多个进程可同时使用的资源不会导致死锁
          • 内存，扬声器
          • 进程不用阻塞等待这种资源
      • 不剥夺条件
        • 进程保持的资源只能主动释放，不可强行剥夺
      • 请求和保持条件
        • 保持着某些资源不放的同时，请求别的资源
      • 循环等待条件
        • 存在一种进程资源的循环等待链
          • 每一个进程已获得的资源同时被下一个进程所请求
        • 注
          • 发生死锁时一定有循环等待，但是发生循环等待时未必死锁
          • 循环等待是死锁的必要不充分条件
            • 同类资源数大于1，则即使有循环等待，也未必发生死锁
            • 如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件
    • 发生死锁的原因
      • 1. 对系统资源的竞争
        • 各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁
        • 对可剥夺的资源（CPU）的竞争不会引起死锁的
        • 独占资源分配不当，互斥资源部分分配又不可剥夺，极易造成死锁
      • 2. 进程推进顺序非法
        • 请求和释放资源的顺序不当
        • 两个线程分别对两个不同的互斥锁先后加锁，但顺序相反，则可能导致死锁，这是典型的循环等待现象
        • 例如，并发执行的进程P1、P2 分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
      • 3. 信号量的使用不当也会造成死锁
        • 以把互斥信号量、同步信号量也看做是一种抽象的系统资源
        • 如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。
      • 对不可剥夺资源的不合理分配，可能导致死锁。
  • 死锁的处理策略
    • 死锁的处理
      • 不允许死锁发生
        • 静态策略
          • 预防死锁
            • 破坏四个条件
        • 动态策略
          • 避免死锁
            • 银行家算法
      • 允许死锁发生
        • 死锁的检测和解除
          • 死锁的检测
            • 用于检测系统状态，以确定系统中是否发生了死锁。
            • • 资源分配图/资源有向图化简法
              • 资源矩阵法
              • 死锁检测算法
                • 死锁定理
          • 死锁的解除
            • 当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。
            • 三种方式
    • 死锁预防
      • 破坏死锁产生的四个必要条件中的一个或几个。
      • 破坏互斥条件
        • 把临界资源改造为可共享使用的资源
          • 比如: SPOOLing技术
            • 把独占设备在逻辑上改造成共享设备
          • 使用了SPooLing技术后，在各进程看来，自己对打印机资源的使用请求立即就被接收处理了，不需要再阻塞等待
        • 缺点
          • 可行性不高，很多时候无法破坏互斥条件
            • 并不是所有的资源都可以改造成可共享使用的资源
            • 为了系统安全，很多地方还必须保护这种互斥性
      • 破坏不剥夺条件
        • 方案一
          • 申请的资源得不到满足时，立即释放拥有的所有资源，以后需要时再重新申请
          • 缺点
            • 会导致进程饥饿
        • 方案二
          • 申请的资源被其他进程占用时，由操作系统协助剥夺(考虑优先级)
        • 缺点
          • 1||| 实现起来复杂
          • 2||| 释放已获得的资源可能造成前一阶段工作的失效
            • 一般只适用于易保存和恢复状态的资源，如CPU
          • 3||| 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
      • 破坏请求和保持条件
        • 可以采用静态分配方法
          • 程序在运行前一次申请完它所需要的全部资源
          • 在它的资源未满足前，不让它投入运行
          • 一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了
        • 缺点
          • 严重的资源浪费，资源利用率极低
          • 可能导致某些进程饥饿
        • 改进
          • 允许一个进程只获得运行初期所需的资源后，便开始运行
      • 破坏循环等待条件
        • 可采用顺序资源分配法
          • 限制了用户申请资源的顺序
          • 给系统中的资源编号
            • 每个进程必须按编号递增的顺序请求资源
            • 同类资源（即编号相同的资源）一次申请完
          • 原理
            • 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源
            • 已持有大编号资源的进程不可能逆向地回来申请小编号的资源
              • 总有一个能得到全部资源然后释放，不断满足下一个进程
        • 缺点
          • 不方便增加新的设备
            • 可能需要重新分配所有的编号
          • 资源浪费
            • 进程实际使用资源的顺序可能和编号递增顺序不一致
          • 编程麻烦
            • 必须按规定次序申请资源
    • 死锁的避免
      • 用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
      • 系统安全状态
        • 安全序列
          • 如果系统按照这种序列分配资源，则每个进程都能顺利完成
          • 只要能找出一个安全序列，系统就是安全状态
          • 安全序列可能有多个
            • 多种可能的分配方案
            • 银行家算法不会限制用户申请资源的顺序
        • 找不出任何一个安全序列，系统就进入了不安全状态
          • 之后可能所有进程都无法顺利的执行下去
        • 注
          • 系统处于安全状态一定不会死锁
          • 系统处于不安全状态未必死锁
            • 因此银行家算法无法检测死锁，只是检测到不安全
          • 发生死锁时一定是在不安全状态
      • 银行家算法
        • 核心思想
          • 在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。
          • 以此决定是否答应资源分配请求
          • 如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待
        • 数据结构描述
          • 假设系统中有n 个进程，m 种资源
            • 每个进程在运行前先声明对各种资源的最大需求数
          • n*m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。Max[i, j]=K 表示进程 Pi 最多需要K 个资源 Rj
          • n*m 的分配矩阵 Allocation表示对所有进程的资源分配情况。
          • Max – Allocation =Need 矩阵，表示各进程最多还需要多少各类资源。
          • 长度为m的一维数组 Available 表示当前系统中还有多少可用资源。
          • 用长度为m的一位数组Request表示进程此次申请的各种资源数
          • 
        • 算法描述
          • 
          • 银行家算法步骤:
            • ①检查此次申请是否超过了之前声明的最大需求数
            • ②检查此时系统剩余的可用资源是否还能满足这次请求
            • ③试探着分配，更改各数据结构
            • ④用安全性算法检查此次分配是否会导致系统进入不安全状态
        • 安全性算法
          • 
          • 安全性算法步骤:
            • 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
            • 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
    • 死锁检测和解除
      • 系统为进程分配资源时不采取任何措施，但提供死锁检测和解除的手段，一旦检测到系统发生死锁，就立即采取相应的措施来解除死锁
        • 不关心进程所需的总资源量
      • 为了能对系统是否已发生了死锁进行检测，必须
        • ①用某种数据结构来保存资源的请求和分配信息;
        • ②提供一种算法， 利用上述信息来检测系统是否已进入死锁状态
      • 如何检测
        • 数据结构
          • 资源分配图
            • 从进程到资源的有向边为请求边
            • 从资源到进程的有向边为分配边
            • 两种结点
              • 进程结点:
                • 对应一个进程
              • 资源结点:
                • 对应一类资源
                • 一类资源可能有多个
                • 一般用矩形表示资源结点
                  • 矩形中的小圆代表该类资源的数量
            • 两种边
              • 请求边
                • 进程结点一> 资源结点
                  • 从进程到资源的有向边
                • 表示进程想申请几个资源(每条边代表一个)
              • 分配边
                • 资源节点一> 进程结点
                  • 从资源到进程的有向边
                • 表示已经为进程分配了几个资源(每条边代表一个)
            • 
        • 死锁检测算法
          • 依次消除与不阻塞进程相连的边，直到无边可消
          • 注:
            • 所谓不阻塞进程是指其申请的资源数还足够的进程
          • 题中一般会给出资源分配图。不过也要小心与数据结构结合考察。
          • 死锁定理
            • 简化方法
              • 
              • 
            • 可完全简化
              • 最终能消除所有边
              • 此时一定没有发生死锁
                • 相当于能找到一个安全序列
            • 死锁定理
              • 若资源分配图是不可完全简化的，说明发生了死锁
              • 处于死锁状态的进程
                • 最终还连着边的那些进程
                  • 并不是系统中所有的进程都是死锁状态
          • 注
            • 系统的资源分配图
              • 死锁状态
                • 每种资源只有一个，并出现环路
              • 一定不会发生死锁
                • 没有环路
                  • 破坏了循环等待条件
            • 出现环路不一定会导致死锁
      • 死锁的解除
        • 1. 资源剥夺法
          • 挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程
          • 应防止被挂起的进程长时间得不到资源而饥饿。
        • 2. 撤销进程法（或称终止进程法）
          • 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。
          • 优点
            • 实现简单
          • 缺点
            • 代价可能会很大
              • 有些进程可能已经运行了很长时间，已经接近结束了
        • 3. 进程回退法
          • 让一个或多个死锁进程回退到足以避免死锁的地步
          • 要求系统要记录进程的历史信息，设置还原点。
      • 如何决定“对谁动手”
        • 1.进程优先级
        • 2.已执行多长时间
        • 3.还要多久能完成
        • 4.进程已经使用了多少资源
          • 优先剥夺资源多的
        • 5.进程是交互式的还是批处理式的
          • 优先牺牲批处理式的
    • 计算
      • 不会发生死锁
        • 资源数大于进程个数乘以“每个进程需要的最大资源数减1
      • 采用银行家算法分配资源
        • m个资源，n个进程
        • 银行家算法
          • 任何时刻都能保证至少有一个进程可以得到所需的全部资源
        • 只要保证系统中进程申请的最大资源数小于或等于 m
          • 存在一个安全序列
        • 极端的情况
          • n-1个进程都申请了1个资源
          • 一个进程申请了m个资源
          • 最大需求量之和为m+n-1，此时能保证一定不会发生死锁。
• 自旋锁：
• 被阻塞信号blocked