OS-2-3-进程同步
2021-08-17 21:39:38 0 举报AI智能生成
操作系统 第二章 第三节 同步-互斥机制的实现方式，信号量机制及其应用 知识点梳理 个人理解
作者其他创作
大纲/内容
初始为空，大小为n的缓冲区
资源
缓冲区空时，生产者必须先放入，消费者才能消耗：同步关系
缓冲区满时，消费者必须先取走，生产者才能放入：同步关系
生产者和消费者访问缓冲区：互斥关系
关系
一个关系对应一个信号量
semaphore mutex=1; //即产品池的访问权semaphore empty=0; //即空缓冲区的数量semaphore full=0; //即产品的数量
while(1) { Produce(); P(empty); P(mutex); PutInto(); V(mutex); V(full);}
Producer()
while(1) { P(full); P(mutex); Get(); V(mutex); V(full); Consume();}
Consumer()
实现
生产者消费者问题
初始为空，大小为1的缓冲区
缓冲区满A时，消费者A必须先取走，生产者才能放入：同步关系
缓冲区满B时，消费者B必须先取走，生产者才能放入：同步关系
生产者AB、消费者AB对缓冲区的访问：互斥关系
亦可概括为：生产者A提供一个A时，消费者A才能取走生产者B提供一个B时，消费者B才能取走消费者取走时，生产者才能放入
可以分析得：任何时刻A、B、empty最多只有1个为1，即最多只有一个进程不被阻塞，因此可以去掉mutex
如果缓冲区大小大于1，此时上述情况不总成立，mutex不可去
semaphore mutex=1;semaphore A=0;semaphore B=0;semaphore empty=1;
while (1) { ProduceB(); P(empty); P(mutex); PutInto(); V(mutex); V(B);}
Class ProducerB
while (1) { ProduceA(); P(empty); P(mutex); PutInto(); V(mutex); V(A);}
Class ProducerA
while (1) { P(B); P(mutex); Get(); V(mutex); V(empty); Consume();}
Class ConsumerB
while (1) { P(A); P(mutex); Get(); V(mutex); V(empty); Consume();}
Class ConsumerA
多生产者-多消费者问题
大小为1的缓冲区
缓冲区内有A时，消费者A才会取走A：同步关系
缓冲区内有B时，消费者B才会取走B：同步关系
缓冲区内有C时，消费者C才会取走C：同步关系
轮流关系是盲的，无需区分是谁完成了
消费者完成消费时，生产者才为下一个消费者提供资源：同步关系
缓冲区大小为1，可去
生产者和消费者ABC访问缓冲区：互斥关系
semaphore mutex=1;semaphore A=0;semaphore B=0;semaphore C=0;semaphore finish=0;
也可以用变量和循环控制
根据题目要求，最好用变量
while(1) { ProduceA(); PutInto(); P(finish); ProduceB(); PutInto(); P(finish); ProduceC(); PutInto(); P(finish);}
Class MultiProducer
while(1) { P(C); Get(); Consume(); V(finish);}
Class ConsumerC
while(1) { P(B); Get(); Consume(); V(finish);}
while(1) { P(A); Get(); Consume(); V(finish);}
吸烟者问题单万能生产者-多消费者问题
一个文件
写者修改文件：互斥关系
写者写时不允许读者读：互斥关系
写者欲写时，阻止后来的读者进入读状态：互斥关系
利用count取消互斥
用PV包裹“读写非互斥量的代码段”可使其具备互斥性
用额外的信号量保证count互斥
亦可认为：本进程一组对m的PV包裹的代码段执行优先于其他进程被对m的PV包裹的代码段
任何针对互斥量m的一组PV操作实际上阻断了其他进程进入其被针对m的PV操作包裹的代码段
所谓优先，是当B类进程间不存在互斥关系，而A类B类间存在互斥关系时，A类可以阻断后来的B类进程资源请求，从而“强行插队”。
当进程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)所包裹的代码段
用w保证写者不饥饿
核心
semaphore rw = 1;int count = 0;semaphore countMutex = 1;semaphore w = 1;
while(1) { P(w); P(rw); Write(); V(rw); V(w);}
Class Writer
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);}
Class Reader
读者写者问题
不同的临界资源
当进程拿到两个资源时，进程开始工作
进程工作结束后，释放占用的资源
进程获取资源是逐个的
进程获取不到需要的资源时，进程进入等待，不释放已经获得的资源
死锁隐患
解决死锁
while (1) { P(maxEater); P(chopstick[this]); P(chopstick[(this + 1) % 5]); Eat(); V(chopstick[this]); V(chopstick[(this + 1) % 5]); V(maxEater); Think();}
Class Philosopher
实现1最多4人同时拿筷子(总有一人可以吃饭)
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();}
实现2奇偶位哲学家拿筷子策略不同总有人一根筷子都拿不到
while (1) { P(mutex); P(chopstick[this]); P(chopstick[(this + 1) % 5]); V(mutex); Eat(); V(chopstick[this]); V(chopstick[(this + 1) % 5]); Think();}
实现3只允许一人拿筷子不能全拿别人都别想拿
哲学家进餐问题
经典问题
临界资源的访问必须是互斥的
临界资源
为了完成某种任务的多个进程，需要在某种条件下协调工作顺序，必须进行等待或传递信息形成的制约关系
将条件是否存在(事件是否发生)视为一种资源，可以由先执行者提供条件资源，后执行者消耗条件资源
直接制约关系来源于合作关系
同步直接制约关系
一个程序访问临界资源时，其他意图访问此临界资源的进程必须等待，直到该资源被释放
间接制约关系来源于竞争关系
互斥间接制约关系
临界资源空闲时，立即允许一个进程进入临界区
空闲让进
有进程进入临界区时，令其他试图访问的进程等待
忙则等待
保证进程不饥饿
有限等待
进不了临界区的进程必须释放处理机，避免忙等
让权等待
基本原则：
负责实现互斥的部分是进入区和退出区
进程访问临界资源的代码段称为临界区
do { entry section; //进入区：负责检查是否可以进入临界区；进入时对临界资源上锁，阻止其他进程进入临界区 critical section; //临界区： exit section; //退出区：负责临界资源的解锁 remainder section; //剩余区} while {true}
互斥机制程序结构
互斥实现
概念
单标志法
双标志先检查
双标志后检查
Peterson算法
实现进程互斥软件方法
概要
简单高效
进程进入临界区前执行关中断指令
只适用于内核进程，不适用于用户进程
不适用于多处理机系统
中断屏蔽
TSL：TestAndSetLock，别称
该指令由硬件实现，执行过程不可中断。
bool TestSet (bool *lock) { bool old = *lock; *lock = true; return old;}
while (TestSet(&lock));//临界区代码段lock = false;//解锁//剩余区代码段
逻辑实现
没有逻辑漏洞，适用于多处理机环境
卡在循环，造成忙等
不满足让权等待
TestAndSet(TS指令/TSL指令)
该指令用硬件实现，执行过程不可中断
SWAP指令(XCHG指令)
实现进程互斥硬件方法
所有的解决方案均无法实现“让权等待”，都会卡循环
双标志先检查法甚至因为操作不具有原子性无法实现互斥
背景
用户通过OS提供的一对原语来对信号量进行操作
信号量是一类数据，表征系统中某类资源的存量
若进入区和退出区的操作通过原语实现，可以实现原子性
Proboren
P操作
wait(S)原语
Verhogen
V操作
signal(S)原语
PV原语
将条件是否存在(事件是否发生)视为一种资源，可以由先执行者进行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)。
应用
不满足组让权等待
整型信号量
L为等待该资源的剩余进程队列
Class semaphore { int value; Process* 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); }
注意block和wakeup的参数都是对应资源的等待队列S.L
当进程调用wait(S)申请资源时，若资源不能满足，则block自身
必然先S.value++/S.value--
适用于实现进程同步、互斥
记录型信号量
分类
根据具体资源被进程访问的情况(代码)，划定临界区
根据资源存量不同，初值可以不同
设置互斥信号量mutex，初值为1，表示资源的存量
在进程临界区前后分别加入P(mutex);和V(mutex);
进程互斥
需要保证两个进程中两段代码的先后关系
设置同步信号量S，初值为0，表示一种只有某段代码执行才能产生的资源
在需要先执行的代码段后加V(S)，后执行的代码段前加P(S)
进程同步
前VP后，一对VP：先完成V，P就会发生
每一对前驱关系都是个进程同步关系
实现进程前驱关系
同步P在互斥PV外
实现互斥的P操作一定要放在实现同步的P操作之后。即：进程内实现同步的P操作必须放在互斥的PV对之外
V操作不会直接导致任何阻塞，颠倒V操作的顺序不会造成死锁
尽量缩短临界区的长度，操作能不放进临界区就不要放进去
操作顺序
考察
信号量
典型管程的定义
while (1) { PCMnt.Insert(Produce());}
Class Producer
while (1) { Consume(PCMnt.Get());}
Class Consumer
采用管程后生产者消费者的定义
管程的应用1生产者消费者问题
解决信号量机制编程困难、易出错
一种高级的同步机制
在Pascal语言中被引入
定义
管程私有的共享数据结构说明
操作上述数据结构的一组过程(方法)
(管程私有)初始化上述数据结构的方法
管程的名字
组成结构
管程的成员只能被管程的方法访问
进程仅能使用管程的方法访问管程的成员
此为管程的精髓
进程只能互斥地使用管程的任意方法
管程的基本特征
在管程中设置条件变量、等待/唤醒操作以解决同步问题
这一层解决了互斥访问就无需再管程内部再实现互斥
进程互斥访问管程的特性是由编译器实现的
进程无需关注自身逻辑是否满足同步互斥关系
管程的意义
基本概念
管程
职业：暂无
0 条评论
回复 删除
下一页
