8月13日笔记

13.2 现实生活中的同步问题

原子锁

Lock.Acquire()

在锁被释放前一直等待，然后获得锁

如果两个线程都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能够获得锁

Lock.Release()

解锁并唤醒任何等待中的进程

进程的交互关系：相互感知程度

1、相互不感知（完全不了解其它进程的存在） => 交互关系：独立 => 进程间相互影响：一个进程的操作对其它进程的结果无影响

2、间接感知（双方都与第三方交互，如共享资源） => 交互关系：通过共享进行协作 => 进程间相互影响：一个进程的结果依赖于共享资源的状态

3、直接感知（双方直接交互，如通信） => 交互关系：通过通信进行协作 => 进程间相互影响：一个进程的结果依赖于从其他进程获得的信息

互斥（mutual exclusion）：一个进程占用资源，其它进程不能使用

死锁（deadlock）：多个进程各占用部分资源，形成循环等待

饥饿（starvation）：其它进程可能轮流占用资源，一个进程一直得不到资源

13.3 临界区和禁用硬件中断同步方法

临界区（Critical Section）:进程中访问临界资源的一段需要互斥执行的代码

entry section

critical section

exit section

remainder section

进入区（entry section）：检查可否进入临界区的一段代码；如可进入，设置相应“正在访问临界区”标志

退出区（exit section）：清除“正在访问临界区”标志

剩余区（remainder section）：代码中其余部分

临界区的访问规则：

1、空闲则入；没有进程在临界区时，任何进程可进入

2、忙则等待；有进程在临界区时，其他进程均不能进入临界区

3、有限等待；等待进入临界区的进程不能无限期等待

4、让权等待（可选）：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

临界区的实现方法：

1、禁用中断：其它进程就没有办法对当前进程的执行进行任何的打扰了，对系统中断的响应会有影响

2、软件方法：硬件还没有支持的时候，尝试用共享变量协调的方式

3、更高级的抽象方法：借用操作系统的支持，来对应用提供同步的服务

不同临界区实现机制的比较

性能：并发级别

方法一：禁用硬件中断：仅限于单处理器

没有中断，没有上下文切换，因此没有并发；硬件将中断处理延迟到中断被启用之后，对于紧急的事情无法立即做出响应，现代计算机体系结构都提供指令来实现禁用中断

local_irq_save(unsigned long flags);

critical section;

local_irq_restore(unsigned long flags);

进入临界区：禁止所有中断，并保存标志

离开临界区：使能所有中断，并恢复标志

缺点：禁用中断后，进程无法被停止；进程如果出了问题，整个系统都会为此停下来，可能导致其他进程处于饥饿状态；临界区可能很长，无法确定响应中断所需的时间（可能存在硬件影响）

12.4 基于软件的同步方法

两个线程之间，通过共享变量的方法来实现线程之间的同步

线程通过共享一些共有变量来同步它们的行为

Peterson算法

满足线程Ti和Tj之间互斥的经典的基于软件的解决方法（1981年）

共享变量

int turn;//表示该谁进入临界区

boolean flag[];//表示进程是否准备好进入临界区

进入区代码

flag[i] = true;

turn = j;

while (flag[j] && turn == j)

退出区代码

flag[i] = false;

Dekkers算法

N线程的软件方法（Eisenberg和McGuire）

处理循环，线程Ti要等待从turn到i-1的线程都退出临界区后访问临界区；线程Ti退出时，把turn改成下一个请求线程

复杂，需要两个进程间的共享数据项；需要忙等待，浪费CPU时间

13.5 高级抽象的方法

硬件提供了一些同步原语：中断禁用，原子操作指令等

操作系统提供更高级的编程抽象来简化进程同步，例如，锁、信号量；用硬件原语来构建

锁（lock）：抽象的数据结构，一个二进制变量（锁定/解锁）

Lock::Acquire() 锁被释放前一直等待，然后得到锁

Lock::Release() 释放锁，唤醒任何等待的进程

使用锁来控制临界区的访问

lock_next_pid -> Acquire();

new_pid = next_pid++;

lock_next_pid -> Release();

现代CPU体系结构都提供一些特殊的原子操作指令

测试与置位指令（Test-and-Set）指令

从内存单元中读取值

测试该值是否为1（然后返回真或假）

内存单元值设置为1

交换指令（exchange）

交换内存中的两个值

使用TS指令实现自旋锁（spinlock）

class Lock {

int value = 0;

}

然后构造它的请求操作原语

Lock::Acquire() {

while (test-and-set(value))

   ;//spin

}

如果锁被释放，那么TS指令读取0并将值设置为1.锁被设置为忙并且需要等待完成

如果锁处于忙状态，那么TS指令读取1并将值设置为1，不改变锁的状态并且需要循环

Lock::Release() {

value = 0;

}

TS锁的执行需要耗用CPU的时间，线程在等待的时候消耗CPU时间

优点：适用于单处理器或者共享主存的多处理器中任意数量的进程同步，简单并且容易验证正确性，支持多临界区，

缺点：忙等待消耗处理器时间，可能导致饥饿，进程离开临界区时有多个等待进程的情况，还可能出现死锁，一个拥有临界区的低优先级进程，另一个请求访问临界区的高优先级进程获得处理器并等待临界区

第十四讲 信号量与管程

14.1 信号量

多线程并发导致资源竞争

同步概念：1、协调多线程对共享数据的访问；2、任何时刻只能有一个线程执行临界区代码；

确保同步正确的方法：1、底层硬件的支持；2、高层次的编程抽象

信号量与锁在同一个层次，是OS提供的一种协调共享资源访问的方法

软件同步是平等线程间的一种同步协商机制

对于信号量，OS是管理者，地位高于进程，用信号量表示系统资源的数量，OS作为一个仲裁者

由Dijkstra在20世纪60年代提出，早期的OS中重要的同步机制，现在很少用，但还是非常重要在计算机科学研究中

信号是一种抽象数据类型：由一个整型（sem）变量（共享的资源数目）和两个原子操作组成

P（）（Prolaag，P操作，申请资源时使用），sem减1，如sem<0，进入等待，否则继续

V（）（Verhoog，V操作，释放资源时使用），sem加1，如sem<=0，唤醒一个等待进程

信号量是被保护的整数变量，初始化完成后，只能通过P（）和V（）操作修改，由操作系统保证，PV操作是原子操作

P操作可能阻塞，V不会阻塞

实际用的时候，通常假定信号量是公平的，线程不会被无限期阻塞在P操作，假定信号量等待按先进先出排队