并发程序设计-intro

并发进程

这篇笔记就用我理解的顺序来记了。首先，我们之前写的都是顺序程序设计，程序是实现算法的操作（指令）序列，每个程序在处理器上执行是严格有序的。这样的程序有非常好的特性：程序执行的顺序性、计算环境的封闭性、计算结果的确定性、计算过程的可再现性

而多道程序设计让多个程序同时进入内存去竞争处理器以获得运行机会，OS允许计算机系统在一个时间段内存在多个正在运行的进程（“并发执行”）

OS保证按照“顺序程序设计”方法编制的程序在并发执行时不受影响，如同独占计算机

进程的并发性(Concurrency)是指一组进程的执行在时间上是重叠的

• 从宏观上看，并发性反映一个时间段中几个进程都在同 一处理器上，处于运行还未运行结束状态
• 从微观上看，任一时刻仅有一个进程在处理器上运行

临界区管理

临界区

多个进程共享同一数据
↓
访问该数据的代码称为临界区（Critical Section）
↓
一次只允许一个进程进入临界区
↓
实现互斥（Mutual Exclusion）

临界资源：互斥共享变量所代表的资源，即一次只能被一个进程使用的资源

• 共享变量（shared variable）：多个线程/进程都能访问的变量。
• 互斥（mutual exclusion, mutex）：同一时刻只允许一个线程访问某段资源。

临界区指的是并发进程中与互斥共享变量相关的程序段

临界区管理的三个要求

1. 一次至多允许一个进程停留在相关的临界区内
2. 一个进程不能无限地停留在临界区内
3. 一个进程不能无限地等待进入临界区

互斥临界区的一般形式：

申请进入 - 使用 - 退出，释放临界资源

临界区可以嵌套使用，但是需要慎重，有可能产生死锁！

临界区管理实现的尝试

两个进程同时进入临界区，互斥失败（Mutual Exclusion Violated）

“检查对方标志”和“设置自己标志”之间不是原子操作，导致两个进程可能同时通过检查，从而破坏互斥（甚至进一步导致死锁）。”

Peterson算法

只利用普通共享变量，不依赖硬件原子指令，就实现两个进程（线程）的互斥。

Peterson 算法第一次清晰地展示了：

互斥（Mutual Exclusion） 前进（Progress） 有限等待（Bounded Waiting）

三个性质如何同时满足。

两个进程：P0、P1

目的：都想要访问临界区 Critical Section

要求：任意时刻最多一个进程进入临界区

最容易想到的方法：加一个共享变量bool lock = false;

while(lock);

lock = true;

/* critical section */

lock = false;

显然不对，P0、P1可能同时进入临界区，互斥失败

而Peterson算法发现仅仅表达“我想进去”还不够，还要表达“如果咱俩都想进去，谁先让一步”

因此设计两个共享变量：

/*
flag[i] = true

表示：
进程 Pi 想进入临界区
*/
bool flag[2];

//发生冲突时轮到谁先进入
int turn;

//算法核心

//两个进程
int i = 0; // or 1
int j = 1 - i;

//对于进程i
flag[i] = true;
turn = j;

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

/* critical section */

flag[i] = false;

讨论：

临界区管理实现的硬件方式

硬件设施：关中断、测试并建立指令、对换指令

TS 和 swap 指令均是忙式等待，效率低

简单的解决办法是在进出临界区时开关中断，这样临界区执行就不会中断了，执行就有原子性 — 关中断；临界区；开中断

TS指令

bool TS(bool &x) {
    if (x) {
        x = false;
        return true;   // 成功抢锁
    } else {
        return false;  // 抢锁失败
    }
}

整个函数是一条原子硬件指令，不可被打断。它做了两件事：

1. 读取 x 的当前值
2. 同时把 x 设为 false（无论原来是什么）

返回值是x 的旧值。

bool s = true; // true表示锁空闲
cobegin
process Pi( ) { //i=1,2,...,n
	while(!TS(s)); //上锁
	{临界区};
  s=true; //开锁
}
coend

为什么这样设计有效？

关键在于：读取和修改是原子的。没有任何窗口让两个进程同时读到 s = true 然后都进入临界区。

对比软件方案的漏洞：LockOne 里”读 inside[1]”和”写 inside[0] = true”之间有窗口，调度器可以插入。TS 把这两步合并成一条指令，窗口消失。

swap指令

void SWAP(bool &a, bool &b) {
    bool temp = a;
    a = b;
    b = temp;
}

同样是一条原子硬件指令，原子地交换两个变量的值。

bool lock=false; // false表示锁空闲
cobegin
Process Pi( ){ //i=1,2,...,n
bool keyi=true; 
 do {
 SWAP(keyi,lock);
 }while(keyi); //上锁
 {临界区};
 SWAP(keyi,lock); //开锁
}
coend

本质上两者等价：SWAP 用本地变量 keyi 充当了 TS 的返回值，都是”原子地把锁的旧值取出来，同时写入新值”。区别只是实现形式，逻辑完全一致。

为什么还是不够好？ — 两者都是忙等（Spin Lock）：抢不到锁的进程一直占着 CPU 执行 while 循环，不做任何有用的工作。

PV操作

PV操作与互斥进程

互斥解决的是“不能同时做”。

同步解决的是“必须按顺序做”。

忙式等待的问题：

1. 对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间
2. 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重用户编程负担

通用解决方案：信号量与PV操作