进程同步
2025-02-09 19:47:03 2 举报AI智能生成
江上制作
作者其他创作
大纲/内容
⭐同步与互斥问题
程序的并发执行
并发
间断性
共享
非封闭性
不确定性
不可再现性
竞争
竞争条件
临界资源
我们将一次仅允许一个进程访问的资源称为临界资源。
临界区
每个进程中访问临界资源的那段代码称为临界区
进程的同步与互斥
进程互斥
（间接制约关系）
进城同步
（直接制约关系）
临界区管理应满足的条件
没有进程在临界区时，想进入临界区的进程可进入
任何两个进程都不能同时进入临界区（MutualExclusion）；
当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区（Progress）；
任何一个进程进入临界区的要求应该在有限时间内得到满足（Bounded Waiting）。
⭐进程互斥的原则
空闲让进
忙则等待
有限等待
让权等待
进程互斥的实现方法（了解）
基于忙等待的互斥方法
软件层面
单标志法
在进入区检查，不上锁
在退出区把临界区的使用权交给另一个进程
主要问题
不遵循空闲让进
双标志先检查
在进入区先检查后上锁，退出区解锁
主要问题
不遵循忙则等待
双标志后检查
进入区先检查后加锁，退出区解锁
主要问题
不遵循空闲让进
不遵循有限等待
可能导致进程饥饿
Peterson算法
在进入区“主动争取-主动谦让-检查对方是否想进、己方是否谦让”
主要问题
不遵循让权等待
会发生忙等
面包店算法
设置一个发号器，按由小到大的次序发放号码。
主要问题
忙式等待空耗CPU资源，其它进程无法使用，因而是低效的。
硬件层面
中断屏蔽
使用
关中断
访问临界区
开中断
优点
简单、高效
缺点
不适合多处理机
只适用于操作系统内核进程
TestAndSet（TS指令/TSL指令）
与CAS机制相同
Swap指令（XCHG指令）
与CAS机制相同
几个算法共性
忙等待
优先级反转
基于信号量的同步方法
同步实现的基本思路
信号量
引入
定义
二元信号量机制
一般信号量的结构
一般信号量的操作
物理意义（重要）
信号量机制的实现
信号量在并发中的典型应用
前驱关系
多进程同步原语：屏障Barriers
一种低级通信原语
进程同步/互斥类问题的求解
“信号量集”机制
AND型信号量集机制
一般“信号集”机制
pv操作优缺点
基于管程的同步与互斥
定义
一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据
组成
管程的名称
局部于管程内部的共享数据结构（变量）说明；
对该数据结构进行操作的一组互斥执行的过程；
对局部于管程内部的共享数据设置初始值的语句。
条件变量与信号量的区别
进程通信的主要方法
进程间的通信
无名管道
有名管道
消息传递
两个通信原语
主要问题
共享内存
存在意义
同一块物理内存被映射到进程A、B各自的进程地址空间。
⭐经典进程同步问题
生产者与消费者问题
问题描述
两个隐含条件
消费者和生产者数量不固定
.消费者和生产者不能同时使用缓存区。
行为分析
行为关系
用pv操作解决生产者/消费者问题
读者-写者问题分析
引入
分析
读进程的行为
写进程的行为
确定同步与互斥关系
确定临界资源
信号量设置
基本框架
对读者有利的算法总结
深究读写问题
如何设计高效且公平算法
Solaries/”读写锁“
哲学家问题
定义
有5个哲学家，并且只有5只筷子在5个哲学家的中间
解决方法
先拿左边，再拿右边
可能导致死锁现象
每个哲学家拿到一个筷子，造成环路等待
先拿左边，再拿右边，并且只有4个哲学家在进程竞争
至少有一个哲学家是可以正常进餐的
偶数哲学家先拿左，奇数哲学家先拿右
拿左右筷子前后加PV操作，形成连贯的操作
0 条评论
下一页
