ch6 进程同步

6.1 临界区问题

背景
- 若干个进程/线程同步的时候可能会共享数据，当他们几乎同时对一个数据进行修改的时候可能会带来数据的不一致性。（类似数据库事务并发模型）
概念
1. 原子操作（Atomic Operation）：和数据库的原子性（Atomaticity）类似，一个完整的没有中断的操作要么全做要么全不做，不可分。这些原子操作在核心态运行并常驻内存
2. 源语（primitive）（プリミティブドラゴン！Get！（乱入））：一段完成一定功能的执行期间不能被中断的程序段
3. 临界资源（Critical Resource）：系统可以供多给线程使用但是同一时间段只允许一个进程访问的资源，其他想要访问的进程必须等待直到该进程完全访问并释放资源后。临界资源的例子包括一个变量、表格、文件、打印机等。
4. 临界区（Critical Section）：程序中访问临界资源的那段代码，要将临界资源的互斥访问转化为对临界区的互斥访问，即没有两个进程同时在临界区中运行
5. 临界区问题是设计一个以便进程协作的协议，每个进程必须请求进入其临界区（进入区，entry section），临界资源使用结束后还要有退出区（exit section），其他代码为剩余区（remainder section）。
6. 竞争条件（Race Condition）：多个进程并发访问和操作统一数据且执行结果和访问发生的特定顺序有关
临界区问题解答原则
1. 互斥（Mutual Exclusion）：忙则等待，进程不同时在临界区内执行
2. 前进（progress）：有空让进。当无进程在临界区执行时，若由进程进入应该允许
3. 优先等待（bounded waiting）：进程进入灵界去的要求必须在有限时间内获得满足
4. 让权等待（no busy waiting）：等待的时候可以选择释放CPU的执行权（非必须）
- 有两种方式用于处理操作系统内的临界区问题：抢占内核和非抢占内核。非抢占内核不允许处于内核模式的进程被抢占，根本不会导致竞争对手，因为只能有一个进程处于内核模式。但是抢占内核需要认真设计才能保证不会导致竞争条件

6.2 解决方案

Peterson算法

这是一个经典的算法，可以通过这个算法理解同步的三个要求，这个算法经历了三个阶段。

使用令牌。turn的值就相当于一个进程令牌。当获得这个令牌后，进入；在退出时移交令牌。

c++

//Processi
do{
    while(turn!=i){
        //critical section
    }
    turn = j;
    //reminder section
}while(1);

c++

//Processj
do{
    while(turn!=j){
        //critical section
    }
    turn = i;
    //reminder section
}while(1);

这个方法有问题，因为在获取令牌的一方在不执行程序的时候没有令牌的一方即使在临界区空闲也得等待，不符合progress的规则（有空让进）

登记簿。使用flag[]做登记簿记录进程进入临界区

c++

//Processi  
do{
    flag[i] = true;
    while(flag[j]){
        //critical section      
    }
    flag[i] = false;
    //reminder section
}while(1)

c++

//Processj
do{
    flag[j] = true;
    while(flag[i]){
        //critical section      
    }
    flag[j] = false;
    //reminder section
}while(1)

正常情况是可以的，但是当两者几乎同时到达的时候，可能两个进程测试另一个进程已经登记，就会互相谦让，都会陷入无限循环之中，不符合progress且会无限等待

使用登记簿和令牌，想要进入临界区，则登记并将令牌移交给另一个进程

c++

//Processi
do{
    flag[i] = true;
    turn = j;
    while(flag[j] && turn == j){
        //critical section
    }
    flag[i] = false;
    //reminder section
}while(1);

c++

//Processj
do{
    flag[j] = true;
    turn = i;
    while(flag[i] && turn == i){
        //critical section
    }
    flag[j] = false;
    //reminder section
}while(1);

如果对方已经等级并且有令牌那么进入，否则自己进入
可以看到，Peterson算法只适合只有两个进程共享的资源。一般同时申请容易出毛病

硬件同步（Hardware Synchronization）
- 不难看出临界区问题需要一个锁来防护，即进程进入临界区以前得到锁，退出临界区时释放锁
- 硬件解决临界区问题，对于单处理器环境在修改共享变量时禁止中断出现即可。但是多处理器需要将消息传给所有的处理器，费时，所以不采用
1. 指令TestAndSet()主要特点是可以原子的执行，即两个指令在不同CPU上执行会按照顺序执行。使用这个指令需要声明一个bool变量lock初始化为false
  - 作用是返回target的现在的值并将target设置为true。它的使用方法是，每个进程都不停执行这个指令直到发现lock为false，说明lock正处在初始状态或者另一个临界区的进程已经释放了锁。
  c++
```
bool TestAndSet(bool *target){
    bool temp = *target; //获取target的值
    *target = true; //将target设置为true，加锁
    return temp; //返回锁原来的状态
}
```
  c++
```
while(true){
    while(TestAndSet(&lock)){
        //返回原来lock的值，并置lock为true
        //如果原来已经上锁，则自己也上锁并等待
        //critical section
        lock = false; //开锁
        //reminder section
    }
}
```
2. 指令Swap()与TestAndSet()类似，不过要操纵两个数据key和lock，其中lock初始值是false，Swap()的功能就是不停的交换两个bool变量的值
  - 其工作原理基本相似，进程不断地交换lock和key的值，只有初始值是lock = false的时候或者另一个进程释放资源将lock设置为false的时候，交换获得的key值才能为false，才能跳出循环
  c++
```
void Swap(bool *key, bool *lock){
    bool temp = *key;
    *key = *lock;
    *lock = temp;
}
```
  c++
```
while(true){
    key = true;
    while(key){
        Swap(&key, &lock);
        //key与lock交换
        //如果原来已经加锁，则也加锁并等待
        //critical section
        lock = false; //开锁
        //reminder section
    }
}
```
信号量（Semaphore）
1. 概念
  - 信号S量是一个整型变量，除了初始化以外，他只能通过两个标准的原子操作wait()和signal()来访问，这两个操作可以被简写为P()和V()
  - wait(S)方法相当于申请资源；signal(S)相当于释放了临界资源以后发出一个信号
  c++
```
void wait(S){
    while(S<=0){
        S--;
    }
}
```
  c++
```
void signal(S){
    S++;
}
```
2. 用法
  - 操作系统有计数信号量和二进制信号量（互斥锁），计数信号量值域不受限，互斥锁只能为0/1，可以提供互斥
  - 二进制信号量可以处理多进程临界区问题，他们公用一个初始值为1的信号量mutex
  c++
```
do{
    ...
    wait(mutex);
    //critical section
    ...
    signal(mutex);
    //reminder section
    ...
}while(1);
```
  - mutex的值为剩余可用资源数目，需要该资源的时候使用wait()，释放资源的时候使用signal()，计数值为0的时候所有请求该资源的进程都会被阻塞直到资源释放。计数信号量和二进制信号量本质上是相同的
3. 实现
  1. 上面定义的信号量主要缺点是忙等待（busy waiting），也就是所有处于等待状态的进程都必须进入代码循环中不停循环。这种类型的信号量也称为自旋锁（spin lock）
    - 缺点：循环等待，占用CPU时间
    - 优点：循环等待时不需要进行上下文切换，减少系统开销，当等待锁的时间较短时，自旋锁是有效的。
    - 自旋锁一般在多处理器系统中使用，但在单处理器系统中，当一个进程等待一个事件，而该事件需要其他进程产生，而其他进程无法执行，也就无法产生该事件。
  2. 非忙等信号量
    - 有两个操作
      1. block：一个进程发现信号量不为正的时候进入等待状态，但是等待状态不是进入忙等待，而是将自己阻塞。阻塞的方法就是将自己送入该信号量的等待队列中
      2. wakeup：signal执行这个操作，将等待队列中的一个进程唤醒
    - 为了实现这种操作，信号量被重新的一位一个结构，包含了整型数和等待链表
    c++
```
typedef struct{
    int value;
    struct process *L;
}semaphore;
```
    - 那么P()``V()操作：
    c++
```
void wait(semaphore *S){
    value--;
    if(value < 0){
        //add this process to waiting queue
        block();
    }
}
```
    c++
```
void signal(semaphore *S){
    val++;
    if(val <= 0){
        //remove a process from the waiting queue
        wakeup();
    }
}
```
    - 忙等信号值不可能为负，但是非忙等则有可能。value为正数表示可用资源数；value为负数表示等待进程数
    - wait()就是对value-1同时在没有可有资源的时候将当进程加入等待队列，而signal()则是value+1同时将等待一个进程唤醒
    - 信号量的关键在于原子性，这属于临界区问题。单处理器环境下可以执行PV操作时简单的不允许中断，而多处理器环境必须提供加锁技术（如自旋锁）确保原子执行
4. 死锁（Deadlock）和饥饿（Starvation）
  - 具有等待队列的信号量实现可能会导致死锁
  - 死锁：两个或多个进程无限的等待一个事件，而该事件只能由这些等待进程之一来产生
  - 饥饿：进程在信号量中无限等待
管程（Monitor）
- 信号量提供了一种方便有效的机制处理同步，但是使用不正确仍然会导致时序错误，如上面所说的死锁与饥饿
- 管程类型提供了一组由程序员定义的、在管程内互斥的操作。管程中包括一组变量的声明和对这些变量操作的子程序和函数的实现
- 管程结构确保每次只有一个进程在管程内活动
- 定义：管程是一种程序结构，结构内的多个子程序形成的多个工作线程互斥访问共享资源
- 可以把管程的定义理解为类似一个类的定义，与一般的类不同之处是管程有条件变量可以控制进程之间的同步
- 管程中需要定义一些额外的同步机制，这些可由条件condition结构提供。condition x,y;条件变量仅有的操作是wait()和signal();当某进程通过管程请求临界资源而未满足时，管程调用wait原语使该进程等待，并将它排在等待队列上;当另一进程访问完并释放之后，管程调用signal原语唤醒等待队列中的(队首)进程;

6.3 信号量的应用

互斥
- 实现互斥很简单，初始一个二进制信号量为1，在临界区分别加上wait(mutex)和signal(mutex)即可
描述前驱关系
同步
- 两进程合作问题三要素：信号量设置、信号量初值、算法描述
- 信号量：同一信号量P、V必须成对出现，互斥信号量必须成对出现在一个程序中，资源信号量出现在不同程序中，多个wait()的顺序是：同步在前、异步在后

6.4 管程

利用管程解决P-C问题

建立一个管程，其中包含两个过程

put(item)：生产者利用该过程将自己生成的消息放到了缓冲池；缓冲池满的时候进入等待
get(item)：消费者利用该过程获得一个消息，缓冲池空的时候进入等待
count: 缓冲池中消息个数

c++

moniter pc{
    int in,out,count;
    condition empty,full;
    item buffer[n];
    void put(item x);
    void get(item x);
    void init(){
        in = 0;
        out = 0;
        count = 0;
    }
}

两个过程的使用

使用管程的目的就是简化时序，对信号量简化。生产者只需要生产然后put()，消费者只需要get()然后消费，不需要考虑等待

c++

//Producer
do{
    ...
    produce an item in nextp;
    pc.put(nextp);
    ...
}while(1);

c++

//Consumer
do{
    ...
    pc.get(nextp);
    consume the item in nextp;
    ...
}while(1);

实现put()和get()

c++

void put(item i){
    //缓冲区满的时候进入等待
    if(count >= n){
        empety.wait();
    }
    buffer[in] = i;
    in = (in+1)%n;
    count++;
    //有等待则唤醒，没有则不修改
    full.signal();
}

c++

void get(item i){
    //缓冲区空,等待缓冲区满
    if(count <= 0){
        full.wait();
    }
    i = buffer[out];
    out = (out+1)%n;
    count--;
    //如果有生产者等待，则唤醒
    empty.signal();
}

哲学家就餐问题
- 筷子的分配由管程来控制，哲学家只管申请和放回筷子
- dp.pickup(i)如果饥饿并且左右两只筷子空闲则吃饭否则等待
- dp.putdown(i)放下筷子测试左右邻居是否在等待，如果在等待则唤醒
总结
- 使用管程的时候每个进程都不需要考虑别的进程怎么样、临界资源怎么样，而是把这些考虑留给了内部实现

6.5 例题

概念
- race condition（竞争条件）
- critical resource（临界资源）
- critical section（临界区）
- atomic operation（原子操作）
- semaphore（信号量）
- wait & signal
- monitor（管程）
- busy waiting（忙等）
进程同步与互斥问题

ch6 进程同步 ​

6.1 临界区问题 ​

6.2 解决方案 ​

6.3 信号量的应用 ​

6.4 管程 ​

6.5 例题 ​

ch6 进程同步

6.1 临界区问题

6.2 解决方案

6.3 信号量的应用

6.4 管程

6.5 例题