第二章：进程的描述与控制

这是一篇关于第二章：进程的描述与控制的思维导图，主要内容包括：前趋图和程序执行，进程，线程。介绍详细，描述全面，希望对感兴趣的小伙伴有所帮助！

第二章：进程的描述与控制

• 前趋图和程序执行
  • 前趋图
    • 定义：用于描述程序执行先后顺序的前趋图，是有向无循环图，可记为DAG
    • 例子：由下列前趋关系可以得到如下前趋图
      • 表示为: P1→P2,P1→P3,P1→P,P2→P3,P3→P5,P4→P6,P4→P7, Ps→P8,P6→P8,P7→P9,P8-p9或者P = {P1, P2, P3, P4,P5, P6, P7, P8, P9}
  • 程序顺序执行
    • 定义：一个应用程序通常由若干个程序段组成，他们在执行时，都需要按某种次序进行，仅当前一个程序段执行结束，才能运行下一段程序段。
    • 例子：在进行运算时，顺序通常是Ii(输入）→Ci(计算)→Pi(输出)
    • 特征：顺序性；封闭性；可再现性（无论是一气呵成还是走走停停，程序运行都能得到同样的结果）
  • 程序并发执行
    • 定义：多个任务在同一时间段内交替执行，看似同时进行（但未必真正并行）。通过时间片轮转、多线程或多进程等技术，系统快速切换任务，提高资源利用率。
    • 特征：间断性；失去密封性；不可再现性。
    • 支撑操作，中断处理，时钟管理，原语操作（要么运行一气呵成要么全都不做）
    • 与顺序执行比较：两者在特征上完全相反
• 进程
  • 进程的描述
    • 定义:它是正在运行的程序实例，是程序的一次执行
    • 特征
      • 动态性：进程是程序的执行过程，有创建、运行、终止的生命周期。
      • 并发性：多个进程可以同时存在于内存中，由操作系统调度交替执行（宏观上并行，微观上串行）。
      • 独立性：进程是资源分配的基本单位，拥有独立的地址空间和系统资源。
      • 异步性：进程的执行速度不可预知，可能因资源竞争或调度而暂停/恢复。
    • 基本状态与转换
      • 基本状态：
        • 就绪态（Ready）：
          • 进程已获得除CPU外的所有必要资源，等待被调度执行。
          • 例如：进程创建后进入就绪队列，或运行态进程时间片用完被剥夺CPU。
        • 运行态（Running）：
          • 进程正在CPU上执行指令。
          • 单核CPU同一时刻只有一个进程处于运行态。
        • 阻塞态（Blocked/Waiting）：
          • 进程因等待某事件（如I/O完成、信号量）而暂停执行，此时不占用CPU。
          • 例如：进程请求读取磁盘数据时进入阻塞态。
      • 状态转换
        • 就绪 → 运行：被操作系统调度程序选中，分配CPU。
        • 运行 → 就绪：时间片用完或被更高优先级进程抢占。
        • 运行 → 阻塞：进程主动等待资源或事件（如发起I/O请求）。
        • 阻塞 → 就绪：等待的事件已完成（如I/O操作结束），被操作系统重新唤醒。
      • 附加状态（可选）
        • 创建态（New）：进程正在被创建，尚未进入就绪队列。
        • 终止态（Exit）：进程执行完毕或异常终止，等待资源回收。
    • 进程管理中的数据结构
      • OS中用于管理控制的数据结构
      • 进程控制块PCB的作用：一作为独立运行基本单位的标志，二能实现间断性运行方式，三提供进程管理所需要的信息，四提供进程调度所需要的信息，五实现与其他进程的同步与通信
  • 进程控制
    • 操作系统内核
      • 支撑功能、中断处理、时钟管理、原语操作
      • 资源管理功能：进程管理、存储器管理、设备管理
    • 创建与终止
      • 进程的创建：申请空白PCB、为进程分配其运行所需的资源、初始化进程控制块PCB
      • 进程的终止：进程执行完毕或被迫结束，释放所占用的系统资源并退出内存。
    • 阻塞与唤醒
      • 引起进程阻塞和唤醒的事件：向系统请求共享资源失败，等待某种操作的完成，新数据尚未到达，等待新任务的到达。
    • 挂起与激活
      • 进程的挂起：进程被暂时移出内存并存入外存，停止执行但仍保留状态信息以便后续恢复。 进程的激活：被挂起的进程重新调入内存，恢复执行状态并继续运行。
  • 进程同步及经典同步问题
    • 进程同步概念
      • 临界资源
        • 定义：一次仅允许一个进程使用的资源
        • 例子：打印机、共享数据结构
      • 临界区
        • 定义：访问临界资源的代码段
        • 目的：保证互斥访问
      • 同步机制
        • 目的：协调进程间的执行顺序
        • 类型：信号量、互斥锁、条件变量等
    • 同步问题的产生
      • 竞争条件
        • 定义：多个进程同时访问和修改共享数据
        • 结果：数据不一致
      • 临界区问题
        • 定义：多个进程试图同时进入临界区
        • 解决方法：互斥机制
    • 经典同步问题
      • 生产者-消费者问题
        • 定义：一组生产者和消费者共享一个有限大小的缓冲区
        • 同步要求：生产者不能在缓冲区满时生产，消费者不能在缓冲区空时消费
      • 读者-写者问题
        • 定义：多个读者可以同时读取数据，但写者必须独占访问
        • 同步要求：保证数据一致性，避免读者和写者同时操作
      • 哲学家就餐问题
        • 定义：一组哲学家围坐在圆桌旁，每两个哲学家之间有一根筷子
        • 同步要求：避免死锁和饥饿
    • 同步机制的实现
      • 信号量
        • 定义：用于控制多个进程对共享资源的访问
        • 类型：二进制信号量、计数信号量
      • 互斥锁
        • 定义：用于保证临界区的互斥访问
        • 特点：简单易用，但可能导致优先级反转
      • 条件变量
        • 定义：与互斥锁配合使用，用于线程间的同步
        • 功能：等待某个条件成立，然后继续执行
    • 死锁问题
      • 定义：多个进程因竞争资源而无限等待对方释放资源
      • 条件：互斥、占有和等待、不可剥夺、循环等待
      • 避免方法：资源分配图、银行家算法
    • 饥饿问题
      • 定义：进程长时间得不到所需资源而无法执行
      • 原因：优先级调度、资源分配策略
      • 解决方法：老化、公平调度算法
  • 进程通信
    • 定义
      • 进程间交换信息
        • 数据传输
        • 控制信号
      • 同步进程行为
        • 协调执行
        • 避免冲突
    • 类型
    • 实现方式
      • 低级通信
        • 直接消息传递系统
      • 高级通信
    • 实现机制
      • 系统调用
        • 创建通信机制
        • 发送/接收数据
      • 库函数
        • 封装系统调用
    • 同步问题
      • 互斥
        • 避免资源冲突
          • 临界区管理
          • 锁机制
      • 死锁
        • 资源分配问题
          • 预防策略
          • 检测与恢复
      • 饥饿
        • 公平性问题
          • 资源分配算法
          • 优先级调整
• 线程
  • 定义
    • 减少程序在并发执行时所付出的时空开销，使操作系统具备更好的并发性
    • 线程是调度和分配的基本单位
  • 实现
    • 内核支持线程
    • 用户级线程
    • 两种线程的组合
  • 线程与进程的区别
    • 资源分配
      • 线程共享进程资源
      • 进程拥有独立资源
    • 创建与销毁
      • 线程创建快于进程
      • 线程销毁成本低
    • 系统开销
      • 线程开销小于进程
  • 线程的状态
    • 和进程的三种基本状态一样
  • 线程的控制
    • 线程创建
      • 分配线程标识符
      • 分配线程控制块
    • 线程终止
      • 完成执行
      • 被其他线程强制终止
    • 线程阻塞
      • 等待资源或事件
    • 线程唤醒
      • 从阻塞状态恢复
  • 线程的同步
    • 互斥锁
      • 控制对共享资源的访问
    • 条件变量
      • 等待某个条件成立
    • 信号量
      • 控制多个线程对资源的访问
  • 线程的优先级
    • 动态优先级
    • 静态优先级
  • 线程的优势
    • 提高并发性
    • 资源共享
    • 响应性
    • 灵活性
  • 线程的挑战
    • 线程安全
      • 避免数据竞争和条件竞争
    • 死锁
      • 防止线程间相互等待