1. 概念

  • 临界资源：一次仅允许一个进程使用的资源
    • 访问过程：进入区（检查）-临界区（访问）-退出区-剩余区
  • 同步：直接制约关系，源于进程间相互合作
  • 互斥：间接制约关系

2.互斥实现方法

①软件实现

  • 一、单标志法

image-20251108155931710

两个进程轮流进入临界区

不足：若一个无法不不再进入，另一个也将无法进入（违背“空闲让进”原则）

  • 二、双标志先检查法

image-20251108160225396

不足：可能同时进入临界区。即检查对方标志后和设置自己标志之前可能发生进程切换（违背“忙则等待”原则）

  • 三、双标志后检查法

image-20251108160636710

不足：两个都想进时谁都进不了（违背“空闲让进”、“有限等待”原则）

  • 四、Peterson算法（四种算法中最好）

image-20251108161251058

②硬件实现

  • 中断屏蔽方法（最简单，效率降低，不适用多处理系统）
  • 硬件指令方法——TestAndSet指令（原子操作，适用多处理系统，但违背“让权等待”）
  • 硬件指令方法——Swap指令

3.信号量

一个变量。表示系统中某种资源的数量。

  • ①整型信号量

操作：初始化、wait（P操作：“申请”）、signal（V操作：“释放”）

缺陷：不满足“让权等待”

  • ⭐②记录型信号量

    在整型基础上加一个进程链表L

    image-20251108194444256

    value初值表示系统中某种资源的数目。

    image-20251108194714713

    • 一次P操作（wait）会执行value–，一次V操作（signal）会执行value++
    • 当value–后剩余资源数**<0时，主动调用block原语进行自我阻塞**，进程被放入等待队列中
    • 当value++后剩余资源数依然**<=0**，说明还有进程在等待，在V操作后主动执行wakeup原语用来唤醒等待队列 中对头的进程

​ 该机制遵循“让权等待”

实现进程互斥、同步

  • ①互斥

    初始化互斥信号量为1

    临界区之前对信号量执行P操作

    临界区之后对信号量执行V操作

    • P、V成对出现

  • ②同步

    初始化信号量为0

    判断先后顺序（例x、y）

    x之后执行V

    y之前执行P

4.经典同步问题

①生产者-消费者image-20251108215103130

思考：为什么不能交换相邻P操作（empty和mutex）？

如果mutex在前，mutex变为0，若此时缓冲区无空位（empty=0,full=n)，生产者被阻塞。然而消费者执行时由于mutex=0也被阻塞，无法释放缓冲区，出现死锁。

∴ 互斥的P操作一定在同步的P操作之后

但V操作可以颠倒，因为不会导致阻塞

②多生产者-多消费者问题

image-20251108221921398

思考：可不可以删掉互斥信号mutex？

在本题中删掉是可以的。因为缓冲区大小=1，最多只允许一个进程访问。

但如果缓冲区大小>1则必须专门设置mutex来保证互斥访问！

③读者-写者问题

互斥：写—写、读—写（读—读可以同时）

image-20251108222947966

引入count变量，只有count==0时需要在读之前加锁（既阻塞写进程，又保证后续读操作不被阻塞）

同时使用mutex来保证对count的互斥访问，防止在判断count时切换导致错误。

问题：读进程优先级更高，即如果源源不断地有读进程，写进程会“饿死”

进阶版：

image-20251108223949775

增加一个变量w实现读写公平，解决写进程饥饿问题。

④哲学家进餐问题

需要避免每个人拿一支筷子陷入”死锁“

  • 方案1：最多n-1个人能拿筷子
  • 方案2：奇数号先拿左边，偶数号先拿右边
  • 方案3：仅当左右2支筷子都能用时才允许拿筷子

5.管程

是什么

进程同步工具，保证进程互斥

组成

  • ① 名称
  • ② 管程内部共享数据结构说明
  • ③ 对②操作的一组过程（函数）
  • ④ 对②设置初始值的语句

管程像一个类，将共享资源的操作封装起来

管程vs.信号量

同：都有类似P/V操作

异：管程条件变量没有值，仅有“排队等待”功能；信号量有值