进程互斥同步
进程的异步性: 进程以各自不同的独立的, 不可预知的速度向前推进
同步
进程同步: 解决进程异步会导致顺序错乱的问题, 亦称直接制约关系, 指为完成某种工作而创立的两个或多个进程, 进程需要在某些位置上协调工作次序而产生的制约关系, 进程间的直接制约关系源于他们之间的相互合作, 遵循一定的先后顺序
互斥
进程互斥: 并非进行的进程不可避免的共享资源
- 互斥共享方式: 某些资源提供给多个进程, 但一个时间段只允许一个进程访问该资源
- 同时共享方式: 允许一个时间段内由多个进程同时进行访问
一个时间段只允许一个进程进行访问的资源称为临界资源
对临界资源的访问需要互斥进行(间接制约关系), 一个进程访问的时候另一个进程访问该资源需要进行等待, 结束并释放之后别的进程才能进行访问
- 进入区: 检查是否可以进入, 可以进入设置标志, 防止其他进程进入
- 临界区(临界段): 访问临界资源的代码
- 退出区: 解除标志
- 剩余区: 其他处理
- 空闲让进, 临界区空闲的时候允许请求进入临界区的进程立即进入临界区
- 忙则等待: 已有进程进入的时候其他试图进入的进程必须等待
- 有限等待: 对访问的进程, 保证在有限的时间内进入临界区
- 让权等待: 进程不能进入临界区时, 立即释放处理机, 防止进程等待
进程互斥的软件实现方法
实现方法
- 单标志法
- 双标志先检查
- 双标志后检查
- Peterson算法
单标志法
算法思想: 两个进程在访问临界区后会把临界区权限转移给另一个进程, 每个进程进入临界区的权限只能被另一个进程赋予
缺点: 只能轮流使用, 违背空闲让进(在空闲的时候禁入标志可能给出但另一方没有使用并归还)
双标志先检测法
使用一个数组, 用各个元素标记想进入临界区的意愿, 每个进程进入之前检查当前有没有别的进程想进入, 没有把自己的flog[i]设置为true之后开始访问, 退出之后设置为0
进程并发进行, 在检查之后但是没有更改标志的时候发生进程切换会出现问题
双标志后检查法
先上锁后进行检查, 同样会导致卡住, 违背空闲让进和有限等待
Peterson算法
结合双标志单标志优点
同时设置数组和优先级, 使用turn表示谦让, 让对方先进入
turn为全局变量
没有实现让权等待原则
硬件实现方法
中断屏蔽方法
利用开关中断的指令实现, 和原语的实现原理相似, 在执行完成切换不会进行中断
优点: 简单高效
缺点: 不适合多处理机(只能关闭一个处理机的中断), 只适用于操作系统内核, 不适合用户进程
TestAndSet指令(TS或TSL(TestAndSetLock))
使用硬件实现, 不能被中断
使用代码介绍大概原理
swap指令(Exchange或XCHG)
Swap和TSL逻辑上没有太大区别, 硬件实现不同, 优缺点相似