Your Site Title

Compute System sync

独立的线程:

• 不和其它线程共享资源或状态
• 确定性=> 输入状态决定结果
• 可重现=> 能够重现起始条件, 1/0
• 调度顺序不重要

合作线程:

• 在多个线程中共享状态
• 不确定性
• 不可重现
• 并行和并发, 提高资源利用
• 模块化

一些概念

Race condition(竞态条件)

• 系统缺陷: 结果依赖于并发执行或者事件的顺序/时间
  • 不确定性
  • 不可重现
• 怎样避免竞态?

Atomic Operation(原子操作)

• 原子操作是指一次不存在任何中断或者失败的执行
  • 该执行成功结束
  • 或者根本没有执行
  • 并且不应该发现任何部分执行的状态
• 实际上操作往往不是原子的
  • 有些看上去是原子操作, 实际上不是
  • 连x++这样的简单语句, 实际上是由3条指令构成的
  • 有时候甚至连单条机器指令都不是原子的(Pipeline, super-scalar, out-of-order
    , page fault)

Critical section(临界区)

临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不
会被执行的代码区域

Mutual exclusion(互斥)

当一个进程处于临界区并访问共享资源时, 没有其他进程会处于临界区并且访问任何相同
的共享资源

Dead lock(死锁)

两个或以上的进程, 在相互等待完成特定任务, 而最终没法将自身任务进行下去

Starvation(饥饿)

一个可执行的进程, 被调度器持续忽略, 以至于虽然处于可执行状态却不被执行

临界区

• 互斥
• Progress
• 有限等待
• 无忙等待: 如果可以马上进入临界区, 那么可以忙等

禁止硬件中断

没有中断, 没有上下文切换, 因此没有并发.

1. 整个系统都会停下来
2. 可能导致其他线程处于饥饿状态
3. 对多个CPU处理更复杂

基于软件的解决方法

Peterson算法 使用两个共享变量turn和flag处理

1. 如果只使用turn, 那么有时候不满足progress
2. 如果只使用flag, 那么有时候不满足互斥

Dekker算法

Eisenberg-McGuire算法 处理多进程互斥算法 Bakery算法

• 算法只要求LOAD和STORE指令是原子操作

更高级的抽象

软件实现非常复杂, 开锁比较大, 而且很容易出错, 调试困难

硬件提供了一些原语: 中断禁用, 原子操作.
操作系统在些基础上提供更高级的编程抽象: 锁, 信号量

硬件原主指令 (原子操作):

• Test-and-Set 测试和置位
  • 从内存中读取值, 并且返回该值
  • 测试该值是否为1
  • 如果是0, 内存值设置为1
• exchange
  • 交换内存中的两个值

优点:

1. 适用于单处理器或者共享主存的多处理器中任意数量的进程
2. 简单并且容易证明
3. 可以用于支持多临界区

缺点:

1. 忙等待
2. while判断 抢lock时, 有进程总是抢不到, 导致饥饿
3. 有些实现导致死锁, 低优先级进程获取lock, 高优先级进程忙等

信号量和管程

有些进程进入同一个临界区是处理不同任务, 这时使用Lock严重影响系统性能(比如有部分
进程进入是只读的). 那么如何保存多进程进入临界区互斥呢?

Di jkstra提出信号量

Semaphore (信号量) :

• 一个整型(sem), 两个原子操作
• P(): sem减1, 如果sem 小于 0, 等待, 否则继续
• V(): sem加1, 如果sem 大于等于 0, 唤醒一个等待的P, 一般使用FIFO

两种类型信号量:

• 二进制信号量: 可以是0或1
• 一般/计数信号量: 可取任何非负值

信号量可以用在2个方面:

• 互斥
• 条件同步

多个信号使用, 粒度小的在里面, 不然容易死锁

管程

monitors, 一开始使用在语言level, 很多条件变量和很多共享资源, 还有对共享资源操作的
一系列函数, 并且有一个Lock.

Lock: - Lock::Acquire() - Lock::Release()

Condition Variable: - Wait() 释放锁, 睡眠 - Signal() 唤醒等待者

死锁

多个进程相互持有对方需要的资源锁, 并且等待对方持有的资源, 就造成死锁.

死锁特征(必要条件) 1: 互斥 2: 持有并等待 3: 无抢占 4: 循环等待

处理办法(约束从强到弱): Deadlock prevention: 打破上面死锁的条件中的一条 Deadlock Avoidance: 使用安全序列, 进程按这个顺列执行就不会死锁. 需要识别safe和
unsafe(包含deadlock), 银行家算法 Deadlock Detection: 死锁检测 Recovery from Deadlock: 出现死锁, 系统可以识别出死锁进程, 按照策略kill进程

进程间通信

IPC(Inter processes communication), 信号(Signal), 管道, 消息队列, 共享内存, 这
里的信号与Lock中的Semaphore不一样.

通信手段, 需要操作系统支持:

• 直接通信
• 间接通信
• blocking
• unblocking

进程间通信的类型: Signal(信号): 软件中断通知事件处理, 不能传输要交换的任何数据, 需要注册信号和信号
产生时处理的函数. 管道(Pipe): 一个进程的输出重定向为另一个进程的输入, stdout和stdin都指向一个buf,
buf大小有限, 父进程是shell 消息队列(Message queues) 共享内存(Shared memory): 直接通信, 最快方式, 必须同步数据访问 套接字(socket)

This site is open source. Improve this page.