6.1.1 并发程序设计的概念

顺序程序设计

  • 程序是实现算法的操作(指令)序列
  • 每个程序在处理器上执行是严格有序的
  • 称为程序执行的内部顺序性
  • 程序设计的一般习惯是顺序程序设计
    • 把一个具体问题的求解过程设计成一个程序或者若严格顺序执行的程序序列
    • 这称为程序执行的外部顺序性

顺序程序设计的特性

  • 程序执行的顺序性：程序指令执行是严格按序的
  • 计算环境的封闭性：程序运行时如同独占受操作系统保护的资源
  • 计算结果的确定性：程序执行结果与执行速度和执行时段无关
  • 计算过程的可再现性：程序对相同数据集的执行轨迹是确定的

进程的并发执行

  • 多道程序设计让多个程序同时进入内存去竞争处理器以获得运行机会
  • OS允许计算机系统在一个时间段内存在多个正在运行的进程，即允许多个进程并发执行
  • OS保证按照“顺序程序设计”方法编制的程序在并发执行时不受影响，如同独占计算机
  • 这些按照顺序程序设计思想编制的进程在OS中并发执行属于无关的并发进程

image-20250516172115568

进程的并发性

  • 进程的并发性是指一组进程的执行在时间上是重叠的
  • 宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未结束状态
  • 微观看，任一时刻仅有一个进程在处理器中运行

并发程序设计

  • 使一个程序分成若干个可同时执行的程序模块的方法称并发程序设计，每个程序模块和它执行时所处理的数据就组成一个进程

eg：

把while(1){input, process, output}设计成

while(1){input, send}

while(1){receive, process, send}

while(1){receive, output}

每一部分是一小段程序，可并发执行，并会产生制约关系

并发程序设计的特性

  • 并发性
  • 共享性 多个进程共享软件资源
  • 交往性 多个进程并发执行时存在制约

## 6.1.2 并发进程的制约关系

无关与交往的并发进程

  • 并发进程分类：无关的，交互的
  • 无关的并发进程：一组并发进程分别在不同的变量集合上运行，一个进程的执行与其他并发进程的进展无关
    • 并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件
  • 交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果

交往的进程并发执行可能会产生时间有关的错误

  • 对于一组交往的并发进程，执行的相对速度无法相互控制
  • 如果程序设计不当，可能出现各种“与时间有关的”错误
    • 表现
      • 结果错误
      • 永远等待

进程之间存在两种基本关系

  • 竞争关系 一个进程的执行可能影响到同其竞争资源的其他进程
  • 协作关系 某些进程为完成同一任务需要分工协作 当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行

竞争关系带来的问题

  • 死锁
  • 饥饿

进程的互斥是解决进程间竞争关系的手段

  • 若干进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占用资源的进程释放资源

进程的同步时解决进程间协作关系的手段

  • 两个以上进程基于某个条件来协调它们的活动 依赖消息或信号来唤醒

进程互斥是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调

6.2.1 临界区

互斥和临界区

  • 临界资源：互斥共享变量所代表的资源
    • 即一次只能被一个进程使用的资源
  • 临界区指并发进程中与互斥共享变量相关的程序段

临界区管理的三个要求

  • 一次至多允许一个进程停留在相关的临界区内
  • 一个进程不能无限地停留在临界区内
  • 一个进程不能无限地等待进入临界区

6.2.2 临界区管理实现的尝试

image-20250517120555837

6.2.3 临界区管理实现的硬件方式

实现临界区管理的硬件设施（忙式等待/反复测试）

  • 关中断
  • 测试并建立指令

image-20250517121655825

  • 对换指令

image-20250517121751117

TS和swap指令都是忙式等待，效率低

  • Peterson算法

6.3.1 PV操作与进程互斥

忙式等待方法

  • 对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间
  • 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可 靠性，加重用户编程负担

适用的解决方案：信号量与PV操作

image-20250517124138540

信号量数据结构定义

image-20250517162547634

image-20250517190644878

image-20250517190744872

推论

  • 若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作次数、亦等于s所代表的实际还可以使用的物理资源数
  • 若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数
  • 通常，P操作意味着请求一个资源，V操作意味着释放一个资源；在一定条件下，P操作代表阻塞进程操作，而V操作代表唤醒被阻塞进程的操作

image-20250517191335554

image-20250517192747247

生产者-消费者模型

image-20250517210045277

6.4.1 管程概述

管程定义

  • 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模式
  • 管程的属性
    • 共享性
    • 安全性
    • 互斥性

管程的基本形式

type管程名=monitor{ 局部变量说明；

​ 条件变量说明；

​ 初始化语句； ​ define管程内定义的，管程外可调用的过程或函数名列表；

​ use管程外定义的，管程内将调用的过程或函数名列表；

​ 过程名/函数名(形式参数表){ ​ <过程/函数体>;

​ }

​ 过程名/函数名(形式参数表){ ​ <过程/函数体>; ​ } }image-20250517211718305

管程的条件变量

  • 条件变量(condition variables)-是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它；当调用管程过程的进程无法运行时，用于阻塞进程的信号量
  • wait()-阻塞调用进程并释放管程，直到另一个进程在该条件变量上执行signal();当一个管程过程发现无法继续时(如发现没有可用资源时),它在某些条件变量上执行wait,这个动作引起调用进程阻塞

  • signal()-如果存在其他进程由于对条件变量执行wait()而被阻塞，便释放之；如果没有进程在等待，那么,信号不被保存；用于释放在条件变量上阻塞的进程

  • 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：

    • 执行signal的进程等待，直到被释放进程退出管程或等待另一个条件变量

    • 被释放进程等待，直到执行signal的进程退出管程或等待另一个条件

霍尔管程

  • 霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理
  • 不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程

Hoare管程数据结构

  • mutex
    • 对每个管程，使用用于管程中过程互斥调用的信号量mutex(初值为1)
    • 进程调用管程中的任何过程时，应执行P(mutex);进程退出管程时，需要判断是否有进程在next信号量等待，如果有(即next_count>0),则通过V(next)唤醒一个发出signal的进程，否则应执行V(mutex)开放管程，以便让其他调用者进入
    • 为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex),否则会妨碍其他进程进入管程，导致无法释放资源
  • next和next-count
    • 对每个管程，引入信号量next(初值为0),凡发出signal操作的进程应该用P(next)阻塞自己，直到被释放进程退出管程或产生其他等待条件
    • 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count(初值为0),用来记录在next上等待的进程个数
  • x-sem和x-count
    • 引入信号量x-sem(初值为0),申请资源得不到满足时，执行P(x-sem)阻塞。由于释放资源时，需要知道是否有别 的 进程在 等 待 资 源， 用 计 数 器X-count(初值为0)记录等待资源的进程数
    • 执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现

image-20250517215827949

image-20250517215848827

image-20250517220017267

image-20250517220155201