OS-2-3-进程同步思维导图模板_ProcessOn思维导图、流程图

经典问题

生产者消费者问题

资源

初始为空，大小为n的缓冲区

关系

缓冲区空时，生产者必须先放入，消费者才能消耗：同步关系

缓冲区满时，消费者必须先取走，生产者才能放入：同步关系

生产者和消费者访问缓冲区：互斥关系

实现

semaphore mutex=1; //即产品池的访问权 semaphore empty=0; //即空缓冲区的数量 semaphore full=0;  //即产品的数量

Producer()

while(1) {     Produce();     P(empty);     P(mutex);     PutInto();     V(mutex);     V(full); }

Consumer()

while(1) {     P(full);     P(mutex);     Get();     V(mutex);     V(full);     Consume(); }

多生产者-多消费者问题

资源

初始为空，大小为1的缓冲区

关系

缓冲区空时，生产者必须先放入，消费者才能消耗：同步关系

缓冲区满A时，消费者A必须先取走，生产者才能放入：同步关系

缓冲区满B时，消费者B必须先取走，生产者才能放入：同步关系

生产者AB、消费者AB对缓冲区的访问：互斥关系

实现

semaphore mutex=1; semaphore A=0; semaphore B=0; semaphore empty=1;

可以分析得：任何时刻A、B、empty最多只有1个为1， 即最多只有一个进程不被阻塞，因此可以去掉mutex

如果缓冲区大小大于1，此时上述情况不总成立，mutex不可去

Class ProducerA

while (1) {     ProduceA();     P(empty);     P(mutex);     PutInto();     V(mutex);     V(A); }

Class ProducerB

while (1) {     ProduceB();     P(empty);     P(mutex);     PutInto();     V(mutex);     V(B); }

Class ConsumerA

while (1) {     P(A);     P(mutex);     Get();     V(mutex);     V(empty);     Consume(); }

Class ConsumerB

while (1) {     P(B);     P(mutex);     Get();     V(mutex);     V(empty);     Consume(); }

吸烟者问题 单万能生产者-多消费者问题

资源

大小为1的缓冲区

关系

缓冲区内有A时，消费者A才会取走A：同步关系

缓冲区内有B时，消费者B才会取走B：同步关系

缓冲区内有C时，消费者C才会取走C：同步关系

消费者完成消费时，生产者才为下一个消费者提供资源：同步关系

轮流关系是盲的，无需区分是谁完成了

生产者和消费者ABC访问缓冲区：互斥关系

缓冲区大小为1，可去

实现

semaphore mutex=1; semaphore A=0; semaphore B=0; semaphore C=0; semaphore finish=0;

Class MultiProducer

while(1) {     ProduceA();     PutInto();     P(finish);         ProduceB();     PutInto();     P(finish);     ProduceC();     PutInto();     P(finish); }

也可以用变量和循环控制

根据题目要求，最好用变量

Class ConsumerA

while(1) {     P(A);     Get();     Consume();     V(finish); }

Class ConsumerB

while(1) {     P(B);     Get();     Consume();     V(finish); }

Class ConsumerC

while(1) {     P(C);     Get();     Consume();     V(finish); }

读者写者问题

资源

一个文件

关系

写者修改文件：互斥关系

写者写时不允许读者读：互斥关系

写者欲写时，阻止后来的读者进入读状态：互斥关系

核心

利用count取消互斥

用额外的信号量保证count互斥

用PV包裹“读写非互斥量的代码段”可使其具备互斥性

用w保证写者不饥饿

任何针对互斥量m的一组PV操作实际上阻断了 其他进程进入其被针对m的PV操作包裹的代码段

亦可认为： 本进程一组对m的PV包裹的代码段执行 优先于其他进程被对m的PV包裹的代码段

当进程A用P(m)V(m)包裹P(n)V(n)， 而进程B用P(m)V(m)仅包裹P(n)时， 表明进程A执行P(n)V(n)所包裹的代码段 优先于进程B执行P(n)V(n)所包裹的代码段

所谓优先，是当B类进程间不存在互斥关系， 而A类B类间存在互斥关系时，A类可以阻断 后来的B类进程资源请求，从而“强行插队”。

实现

semaphore rw = 1; int count = 0; semaphore countMutex = 1; semaphore w = 1;

Class Writer

while(1) {     P(w);     P(rw);     Write();     V(rw);     V(w); }

Class Reader

while(1) {     P(W);     P(countMutex);     if (count == 0)         P(rw);     count++;     V(countMutex);     V(w);     Read();     P(countMutex);     count--;     if(count == 0)         V(rw);     V(countMutex); }

哲学家进餐问题

资源

不同的临界资源

关系

当进程拿到两个资源时，进程开始工作

进程工作结束后，释放占用的资源

进程获取资源是逐个的

进程获取不到需要的资源时，进程进入等待，不释放已经获得的资源

核心

死锁隐患

解决死锁

实现1 最多4人同时拿筷子 (总有一人可以吃饭)

semaphore maxEater = 4; semaphore chopstick[5] = [1, 1, 1, 1, 1 ];

Class Philosopher

while (1) {     P(maxEater);     P(chopstick[this]);     P(chopstick[(this + 1) % 5]);     Eat();     V(chopstick[this]);     V(chopstick[(this + 1) % 5]);     V(maxEater);     Think(); }

实现2 奇偶位哲学家拿筷子策略不同 总有人一根筷子都拿不到

semaphore chopstick[5] = [1, 1, 1, 1, 1 ];

Class Philosopher

while (1) {     if(this % 2 == 0) {         P(chopstick[this]);         P(chopstick[(this + 1) % 5]);     }     else {         P(chopstick[(this + 1) % 5]);         P(chopstick[this]);     }     Eat();     V(chopstick[this]);     V(chopstick[(this + 1) % 5]);     Think(); }

实现3 只允许一人拿筷子 不能全拿别人都别想拿

semaphore mutex = 1; semaphore chopstick[5] = [1, 1, 1, 1, 1 ];

Class Philosopher

while (1) {     P(mutex);     P(chopstick[this]);     P(chopstick[(this + 1) % 5]);     V(mutex);     Eat();     V(chopstick[this]);     V(chopstick[(this + 1) % 5]);     Think(); }

概念

临界资源

临界资源的访问必须是互斥的

同步 直接制约关系

为了完成某种任务的多个进程，需要在某种条件下协调工作顺序， 必须进行等待或传递信息形成的制约关系

将条件是否存在(事件是否发生)视为一种资源，可以由 先执行者提供条件资源，后执行者消耗条件资源

直接制约关系来源于合作关系

互斥 间接制约关系

一个程序访问临界资源时，其他意图访问此临界资源的进程必须等待，直到该资源被释放

间接制约关系来源于竞争关系

互斥实现

基本原则：

空闲让进

临界资源空闲时，立即允许一个进程进入临界区

忙则等待

有进程进入临界区时，令其他试图访问的进程等待

有限等待

保证进程不饥饿

让权等待

进不了临界区的进程必须释放处理机，避免忙等

互斥机制程序结构

负责实现互斥的部分是进入区和退出区

进程访问临界资源 的代码段称为临界区

do {     entry section;     //进入区：负责检查是否可以进入临界区；进入时对临界资源上锁，阻止其他进程进入临界区     critical section;  //临界区：     exit section;      //退出区：负责临界资源的解锁     remainder section; //剩余区 } while {true}

实现进程互斥 软件方法

单标志法

双标志先检查

双标志后检查

Peterson算法

实现进程互斥 硬件方法

中断屏蔽

进程进入临界区前执行关中断指令

简单高效

只适用于内核进程，不适用于用户进程

不适用于多处理机系统

TestAndSet (TS指令/TSL指令)

TSL：TestAndSetLock，别称

该指令由硬件实现，执行过程不可中断。

逻辑实现

bool TestSet (bool *lock) {     bool old = *lock;     *lock = true;     return old; }

while (TestSet(&lock)); //临界区代码段 lock = false;//解锁 //剩余区代码段

没有逻辑漏洞，适用于多处理机环境

不满足让权等待

卡在循环，造成忙等

SWAP指令 (XCHG指令)

该指令用硬件实现，执行过程不可中断

逻辑实现

bool old = true; while (old) Swap(&lock, old); //临界区代码段 lock = false; //剩余区代码段

不满足让权等待

信号量

背景

所有的解决方案均无法实现“让权等待”，都会卡循环

双标志先检查法甚至因为操作不具有原子性无法实现互斥

机制

用户通过OS提供的一对原语来对信号量进行操作

信号量是一类数据，表征系统中某类资源的存量

若进入区和退出区的操作通过原语实现，可以实现原子性

PV原语

wait(S)原语

P操作

Proboren

signal(S)原语

V操作

Verhogen

将条件是否存在(事件是否发生)视为一种资源，可以由先执行者 进行V操作以提供条件资源，后执行者进行P操作消耗条件资源

分类

整型信号量

相比普通int，int信号量只有“初始化”，“P操作”，“V操作”3种操作

原语实现

void wait(int S) { while (S <= 0); S -= 1; }

void signal(int S) { S += 1; }

应用

进入区使用wait(S)，退出区使用signal(S)。

不满足组让权等待

记录型信号量

数据定义

Class semaphore { int value; Process* L; }

L为等待该资源的剩余进程队列

原语实现

void wait(semaphore S) { S.value--; if (S.value < 0) block(S.L); }

void signal(semaphore S) { S.value++; if (S.value <= 0) wakeup(S.L); }

应用

当进程调用wait(S)申请资源时，若资源不能满足，则block自身

注意block和wakeup的参数都是对应资源的等待队列S.L

必然先S.value++/S.value--

适用于实现进程同步、互斥

应用

进程互斥

根据具体资源被进程访问的情况(代码)，划定临界区

设置互斥信号量mutex，初值为1，表示资源的存量

根据资源存量不同，初值可以不同

在进程临界区前后分别加入P(mutex);和V(mutex);

进程同步

需要保证两个进程中两段代码的先后关系

设置同步信号量S，初值为0，表示一种只有某段代码执行才能产生的资源

在需要先执行的代码段后加V(S)，后执行的代码段前加P(S)

实现进程前驱关系

每一对前驱关系都是个进程同步关系

前VP后，一对VP：先完成V，P就会发生

考察

操作顺序

实现互斥的P操作一定要放在实现同步的P操作之后。 即：进程内实现同步的P操作必须放在互斥的PV对之外

同步P在互斥PV外

V操作不会直接导致任何阻塞，颠倒V操作的顺序不会造成死锁

尽量缩短临界区的长度，操作能不放进临界区就不要放进去

管程

管程的应用1 生产者消费者问题

典型管程的定义

Monitor PCMnt {     private condition notFull, notEmpty;     private int count = 0;     private Buffer buffer;     public void insert(Item item) {         if(count == buffer.size) wait(notFull);         count++;         InsertItem();         if(count == 1) signal(notEmpty);     }         public Item Get() {         if(count == 0) wait(notEmpty);         count--;         if(count == buffer.size - 1) signal(notFull);         return GetItem();     } }

采用管程后生产者消费者的定义

Class Producer

while (1) {     PCMnt.Insert(Produce()); }

Class Consumer

while (1) {     Consume(PCMnt.Get()); }

基本概念

背景

解决信号量机制编程困难、易出错

定义

一种高级的同步机制

在Pascal语言中被引入

组成结构