清华⼤学操作系统（陈渝，向勇）课程笔记——（⼗）协同多道
程序设计和并发问题
主要内容
背景
—些概念
临界区 (Critical section)
⽅法1：禁⽤硬件中断
⽅法2：基于软件的解决⽅法
⽅法3：更⾼级的抽象
背景
多道程序设计(multi-programming)：现代操作系统的重要特性
并⾏很有⽤(为什么? )
提⽰：多个并发实体:CPU(s)，I/O, …，⽤户,…
进程/线程：操作系统抽象出来⽤于⽀持多道程序设计
CPU调度：实现多道程序设计的机制
调度算法-不同的策略
独⽴的线程:
不和其他线程共享资源或状态
确定性=输⼊状态决定结果
可重现→能够重现起始条件，I/O
I/O调度顺序不重要
合作线程：
在多个线程中共享状态
不确定性
不可重现
不确定性和不可重现意味着bug可能是间歇性发⽣的
进程/线程，计算机/设备需要合作
优点1：共享资源
—台电脑，多个⽤户
⼀个银⾏存款余额，多台ATM机
嵌⼊式系统〔机器⼈控制:⼿臂和⼿的协调)
优点2：加速嵌入式多线程编程
I/O操作和计算可以重叠
多处理器–将程序分成多个部分并⾏执⾏
优点3：模块化
将⼤程序分解成⼩程序使系统易于扩展
以编译为例，gcc会调⽤cpp，cc1，cc2，as，ld
程序可以调⽤函数fork()来创建⼀个新的进程
操作系统需要分配⼀个新的并且唯⼀的进程ID
因此在内核中，这个系统调⽤会运⾏共享的全局变量翻译成机器指令
new_pid = next_pidit ++(不是原⼦操作);
1) LOAD next_pid Regl
2)STORE Regl new_pid
3)INC Regl
4STORE Regl next_pid
假设两个进程并发执⾏
如果next_pid等于100，那么其中⼀个进程得到的ID应该是100，另⼀个进程的ID应该是101，next_pid应该增加到102
⽆论多个线程的指令序列怎样交替执⾏，程序都必须正常⼯作
多线程程序具有不确定性和不可重现的特点
不经过专门设计，调试难度很⾼
不确定性要求并⾏程序的正确性
先思考清楚问题，把程序的⾏为设计清楚
切忌急于着⼿编写代码，碰到问题再调试
Race Condition(竞态条件)
系统缺陷：结果依赖于并发执⾏或者事件的顺序/时间
不确定性
不可重现
怎样避免竞态?
让程序不会被打断
Atomic Operation(原⼦操作)
原⼦操作是指⼀次不存在任何中断或者失败的执⾏
该执⾏成功结束
或者根本没有执⾏
并且不应该发现任何部分执⾏的状态
实际上操作往往不是原⼦的
有些看上去是原⼦操作，实际上不是
连x++这样的简单语句，实际上是由3条指令构成的
有时候甚⾄连单条机器指令都不是原⼦的
Pipeline，super-scalar，out-of-order，page fault
问题
Critical section(临界区)
临界区是指进程中的⼀段需要访问共享资源并且当另⼀个进程处于相应代码区域时便不会被执⾏的代码区域
Mutual exclusion (互斥)
当⼀个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源Dead lock (死锁)
两个或以上的进程，在相互等待完成特定任务，⽽最终没法将⾃⾝任务进⾏下去
Starvation(饥饿)
⼀个可执⾏的进程，被调度器持续忽略，以⾄于虽然处于可执⾏状态却不被执⾏
临界区
临界区属性
互斥：同⼀时间临界区中最多存在⼀个线程
Progress：如果⼀个线程想要进⼊临界区，那么它最终会成功
有限等待：如果⼀个线程i处于⼊⼝区，那么在i的请求被接受之前，其他线程进⼊临界区的时间是有限制的⽆忙等待(可选)∶如果⼀个进程在等待进⼊临界区，那么在它可以进⼊之前会被挂起
临界区代码保护⽅法
⽅法1：禁⽤硬件中断
没有中断，没有上下⽂切换，因此没有并发
硬件将中断处理延迟到中断被启⽤之后
⼤多数现代计算机体系结构都提供指令来完成
进⼊临界区
禁⽤中断
离开临界区
开启中断
缺点
⼀旦中断被禁⽤，线程就⽆法被停⽌
整个系统都会为你停下来
可能导致其他线程处于饥饿状态
要是临界区可以任意长怎么办
⽆法限制响应中断所需的时间(可能存在硬件影响)
所以要⼩⼼使⽤
另外，禁⽤软件中断⽆法在多CPU情况下⽆法解决互斥问题
⽅法2：基于软件的解决⽅法
经典逻辑
线程可以共享⼀些共有的变量来同步他们的⾏为。Peterson算法
Dekker算法：第⼀个针对双线程例⼦的正确解决⽅法
Bakery算法——N个进程的临界区
进⼊临界区之前，进程接收⼀个数字
得到的数字最⼩的进⼊临界区
如果进程Pi和Pj收到相同的数字，那么如果i<j，Pi先进⼊临界区，否则Pj先进⼊临界区编号⽅案总是按照枚举的增加顺序⽣成数字
基于软件的解决⽅法总结
复杂
需要两个进程间的共享数据项
需要忙等待
浪费CPU时间
没有硬件保证的情况下⽆真正的软件解决⽅案
Peterson算法需要原⼦的LOAD和STORE指令
⽅法3：更⾼级的抽象
硬件提供了⼀些原语
像中断禁⽤，原⼦操作指令等
⼤多数现代体系结构都这样
操作系统提供更⾼级的编程抽象来简化并⾏编程
例如：锁，信号量
从硬件原语中构建
锁是⼀个抽象的数据结构
⼀个⼆进制状态（锁定/解锁)，两种⽅法
Lock::Acquire()–锁被释放前⼀直等待，然后得到锁
Lock::Release()–释放锁，唤醒任何等待的进程
使⽤锁来编写临界区，前⾯的例⼦变得简单起来:
lock_next_pid->Acquire() ;
new_pid = next_pid++ ;
lock_next_pid->Release() ;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。