首页  思维导图  详情

OS-2-3-进程同步

2021-08-17 21:39:38   0  举报





AI智能生成

操作系统第二章第三节同步-互斥机制的实现方式，信号量机制及其应用知识点梳理个人理解

同步-互斥算法

信号量

生产者消费者模型

操作系统

计算机

作者其他创作

大纲/内容

经典问题

生产者消费者问题

资源

初始为空，大小为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语言中被引入

组成结构