同步和互斥

进程同步，进程互斥

①进程同步：解决进程的异步问题，协调工作顺序。

②进程互斥对于临界资源，必须互斥地进行访问。（or结果就像两个文档打印混一起了）

临界资源（临界区）：一个时间段内只允许一个进程使用的资源。

实现互斥的四个逻辑部分：

进入区。临界区。退出区。剩余区。

image-20260407115928870

实现互斥遵循的四个原则：

空闲让进。忙则等待。有限等待。让权等待。

image-20260407120115888

回顾

image-20260407120223745

进程互斥的软件实现方法

image-20260407120546922

①单标志法

一个进程在访问完临界区后，会把使用临界区的权限 交给 另一个进程。

标志位turn，表示当前允许进入临界区的进程号。

image-20260407121033219

缺点：当允许进入临界区的进程A不访问临界区（或者是并发时时间片到期了），造成临界区空闲，而别的进程如B使用不了临界区。

违背原则：“空闲让进”

②双标志先检查法

先“检查”后“上锁”

先检查对方想不想使用（检查）

自己要用（表达意愿，上锁）

flag[0]，flag[1]标记各进程的意愿，T/F。

image-20260407121408670

缺点：如果两个进程是，并发的运行时，时间片切换，【1[false]（time out）-5[false]-6-7（time out）,2-3】会造成两个进程P1 P2同时使用临界区。

违反原则：“忙则等待”

原因在于：“检查”后，“上锁”前，可能发生进程切换。【即进入区的“检查”和“上锁”两个处理不是一气呵成的。】

③双标志后检查法

先“上锁”后“检查”。

自己想用临界资源（表达意愿，上锁）

自己不想再问对方。（检查）

image-20260407122058835

缺点：并发运行，两个进程都访问不了临界区。【1(time out)-5(time out)-2-6-…】。造成“饥饿”。

违背原则：“空闲让进”，“有限等待”。

④peterson 算法

1.主动争取【flag[自己id]=true】

2.主动谦让【turn=对方id】

3.如果对方也想使用。且最后一次是自己谦让，则让对方进入临界区。【while（flag[对方id] && turn==对方id】

初始的 flag[]=false

image-20260407130332695

优点：遵循了空闲让进，忙则等待，有限等待三个原则。

缺点：没有遵循让权等待的原则。造成“忙等”

回顾

image-20260407130605883

进程互斥的硬件实现方法

image-20260407130917923

①中断屏蔽方法

实现机制：开/关中断指令

优点：简单，高效

缺点：不适合多处理机。只适用于OS内核进程。（开/关中断指令只能运行在内核态，给用户随意使用很危险）

②TestAndSet指令

“检查”与“上锁是一体的。

一体的原因是：TSL（TS）指令是一条硬件指令，CPU执行这条指令时不会被打断。

image-20260408195122907

优点：实现简单。适用于多处理机环境。

违背原则：“让权等待”

③swap指令

类似于TSL指令。

image-20260407132030461

回顾

image-20260407132113604

进程互斥的高级方法

互斥锁

【还有信号量，管程，条件变量等】

上锁：acquire（）

解锁：release（）

image-20260408201632972

阻塞型互斥锁：放弃CPU，把自己挂起（阻塞），让CPU去执行其他进程，等锁可用时再被唤醒。

  • 适用于：临界区较长或单处理器的场景。

自旋型互斥锁：连续循环，忙等。

  • 忙等 – 即B也会使用CPU进程（时间片到期），但是B做不了事情，造成CPU空转，A又少了些许的CPU执行时间。
  • 违背原则：“让权等待”。
  • 适用于：临界区极短且多处理器的场景。
  • 自旋锁的底层实现：可以是TSL指令，swap指令，单标志法

信号量机制

image-20260407185832865

image-20260408201840520

信号量不同于普通的变量，对信号量的操作只有：初始化，P，V三种。

整型信号量

原理：和双标志先检查后上锁相同。但是实现了 检查和上锁 一气呵成。（避免进程同时在临界区的问题）

缺点：不满足“让权等待”，会发生忙等。

原语wait–检查+上锁，signal–释放

image-20260407191021773

记录型信号量⭐

原理：S. value表示剩余资源数，S.L指向等待资源的队列。

优点：遵循了“让权等待”原则（解决“忙等”问题）

image-20260407191510154

⭐左右两边都重要

image-20260407192540826

EG

image-20260408203257921

image-20260408203557838

回顾

image-20260407192710692

用信号量机制实现进程互斥、同步、前驱关系

P（s） – 申请一个进程S，如果资源不够就阻塞等待

V（s） – 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。

image-20260407193006251

实现进程互斥

信号量初始值为1。

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

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

image-20260407193439280

实现进程同步

同步：保证顺序执行。

信号量初始值为0。

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

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

image-20260407194247598

实现前驱关系

为每一对的前驱关系设置信号量，初始值为0。

在每一个“前操作”之后执行V操作

在每一个“后操作”之前执行P操作

image-20260407194634672

回顾

进程同步互斥问题

生产者消费问题

image-20260407200124695

image-20260407200559910

不能改变相邻P操作的顺序：会造成死锁（如果已经没有空闲区了，生产者会被阻塞，切换成消费者进程，消费者在等待对方释放资源锁，也被阻塞了，进入阻塞队列。互相等待被对方唤醒，出现“死锁”）

  • 因此得，先执行同步P操作，再执行互斥P操作

可以改变相邻V操作的顺序，不会造成进程阻塞。

不建议把处理内容都放入临界区，会造成临界区上锁时间长。

image-20260407201147190

回顾

发现题目之间的同步，互斥关系。

确定PV顺序。

互斥信号量初值一般是1，同步信号量初值看资源初值是多少。

image-20260407201312529

多（类）生产者-多（类）消费者

image-20260408210312635

image-20260408210802579

image-20260408210819715

image-20260408210959318

image-20260408211018840

缓冲区为1，有可能，不用设置互斥信号量。

image-20260408211556844

image-20260408211705339

回顾

看成 事件 的先后关系（而不是进程的前后关系，这样子复杂）

image-20260408212033596

读者-写者问题

image-20260408212844691

设置一个信号量mutex，保证读进程检查和上锁一体，保证不会在执行完检查（count==0）后被切换进程导致之后进不去进程。

又有潜在的问题…写进程可能被“饿死”。

image-20260408213612808

再设置一个信号量w，用于实现 “读写公平”（谁先来谁优先，而不是一直是读先）

（读者1完成，释放rw信号量，唤醒因为rw而阻塞的写进程）

image-20260409143038771

image-20260408214234143

回顾

image-20260409143418447

哲学家进餐问题

image-20260409143954536

死锁的出现：

image-20260409144136181

如何防止死锁的发生？

image-20260409144351383

image-20260409145049433

回顾

image-20260409145241883

管程

image-20260409145326232

信号量机制存在的问题，编写程序困难，易出错。

管程：不易出错，易编写。

image-20260409150003981

相当于封装，自己调函数就行

image-20260409150803432

image-20260409151047767

image-20260409151200299

回顾

image-20260409151338758