操作系统复习笔记（三）——Process synchronization

Process Synchronization 1

• IPC(Interprocess communication)
  协作的进程需要 IPC

三种 IPC 模型

进程通信可以通过

• shared memory 共享内存
• pipe 管道
• message passing 消息传递

Message passing

• 建立一个 communicate link(physical/logical)
• 通过 send/receive 交换

直接通信，对称寻址 Direct communication-symmetric addressing

• 进程必须互相知道对方名字
  • send(P,message)
  • receive(Q,message)
• 自动建立了 link 两个进程间只有一条，一条链路只有两个进程

直接通信，非对称寻址

• 发送时指明了名字，接收只有 id
  • send(P,message)
  • receive(id,message)
    例如：共享打印机

直接通信的缺点：必须知道对方的名字，局限了模块化

间接通信

• 消息从中介取，往中介发 mailbox or ports
  • send(A,message)
  • receive(A,message)

每个 mailbox 都有独立 id
一条链路连接多个进程

IPC synchronization

• Blocking send ：直到上一个消息被接收时才会发下一个消息
• Non-blocking send ：随时发
• Blocking receive ：一个消息来的时候 receiver 才工作
• Non-blocking receive ：随时取

Non-blocking 和 blocking receive 是最常见的

IPC buffering

link 的消息队列容量

• Zero capacity 队列长度=0
• Bounded capacity 队列长度=n
• Unbounded capacity 队列长度=\infty

Critical-Section Problem 临界区问题

对于共享数据的并行访问可能导致数据的不一致

Race condition 竞争条件

多个进程同时访问操作文件，最终结果取决于最后执行的指令
为了避免竞争条件，并行的进程必须是 mutual exclusion 互斥的

互斥

• 如果一个进程正在使用一个共享文件或变量，其他进程不能做同样的事

The critical-section problem

每个进程拥有的操作共享数据的代码称为 critical section 临界区。要保证当一个进程执行时它的临界区代码时，其他进程不能执行临界区代码

解决方案：
在执行之前加点条件，判断能否执行，执行完毕后解锁

do{
    entry section   //执行前判断
        crical section
    exit section    //执行完毕后解锁
        reminder section
}

解决临界区问题需要满足

• Mutual Exclusion 互斥
• Progress 前进原则
  如果没有临界区代码在执行，有一个进程想进入临界区是，应当允许
• Bounded wait 有限等待
  想进入临界区的在有限时间内总能进入

例 火车问题

前提

有两列相向而行的火车需要在某个地点占用同一段铁轨，如何保证两车进入不会相撞，且两车都能正常运行

算法 1 交替进入

int turn;
turn=i  //Pi可以进入

Pi

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

满足互斥，但不满足前进原则（只有一辆车运行的情况下）

算法 2 flag each process 给每个进程都标记

boolean flag[2];
flag[i]=true;

Pi

do {
    flag[i]=true;
    while(flag[j]); //空循环等待j
    /* critical sectioon */
    flag[i]=false;
    /* remainder */
} while(1);

如果两个同时刻到，那么都进不去，不满足 Bounded waiting

算法 3 1 和 2 的组合

do {
    flag[i]=true;
    turn=j; //先把机会让给另外一个
    while(flag[j] && turn==j);  //如果另外一个也到了，就空循环等待
    /* critical section */
    flag[i]=false;
    /* remainder section */
} while(1);

三个要求都满足

Process Synchronization 2

Synchronization tools for IPC

• Synchronization hardware
• Semaphores
• Critical Regions
• Monitors

Synchronization hardware 硬件同步

很多系统提供了硬件对于临界区代码的支持

• 单处理器可以禁止中断，使当前运行代码不会被抢占
• 在多处理器上上述方案效率太低

现代计算机提供了特别的 原子的(atomic) 硬件指令

• 检查和修改字的内容
• 或交换两个字的内容

TestAndSet Instruction 检查和修改指令 自旋锁

方法：

boolean TestAndSet(boolean *target) {
    boolean rv=*target;
    *target=true;
    return rv;
}

初始化：

boolean lock=false;

执行时：

do{
    while(TestAndSet(&lock));
    //critical section
    lock=false;
    //remainder section
}

Swap Instruction

操作两个数据，与指令 TestAndSet 一样原子执行

void Swap(boolean *a,boolean *b) {
    boolean temp=*a;
    *a=*b;
    *b=temp;
}

初始化：

boolean lock=false;

执行时：

do {
    key=true;
    while(key==true)
        Swap(&lock, &key);
    //critical section
    lock=false;
    //remainder
} 

Semaphores 信号量

Dijkstra 提出
信号量 一个整形变量，只能通过两个标准原子操作：

• wait()
• signal()

wait(s):

while(s<=0)
;   //no-operation
s--;

signal(s):

s++

在 wait()和 signal()操作中，对信号量的修改必须是原子的，即当一个进程修改信号量值时，不能有其他进程同时修改同一信号的值

初始化：

int matex=1;

Critical section of n processes

do {
    wait(mutex);
    //critical section
    signal(mutex);
    //remainder section
} while(1);

两种类型的信号量

• 计数信号量的值域不受限制，用来表示可用资源的数量
• 二进制信号量的值只能为 0 或 1

信号量实现的分析

主要缺点是 忙等待(busy waiting)

忙等待

当一个进程位于其临界区内时，其他想进入临界区的进程必须连续循环等待，浪费了 CPU 时钟。也称为自旋锁。

解决方法

为了克服忙等待，可以使用阻塞并放入等待队列的操作。通过 wakeup()来重新执行

定义一个新结构

typedef struct {
    int value;
    struct process *List;
} semaphore;

• Block operation: block()
• Wakeup operation: wakeup()

新的信号量操作定义

wait(semaphore *S){
    S.value--;
    if(S.value<0) {
        block();    //add this process to S.List
    }
}

signal(semaphore *S) {
    S.value++;
    if(S.value<=0) {
        wakeup(P);  //remove a process P from S.List
    }
}

Bounded-Buffer Problem 可用计数信号量来解决

Deadlock and Starvation 死锁与饥饿

• Deadlock: 两个或多个进程无限地等待一个事件
• Starvation: 无限期阻塞

Critical Regions 临界域

一种高层同步结构

Monitor 管程

另一种高层同步结构

比信号量更高的抽象。或者说并没有这种实体存在于系统或编程语言中,更多的是一种机制，一种解决方法，但是编程语言和操作系统都提供了实现管程的重要部件条件变量

管程就是管理一组共享变量的程序。主要有一下几部分组成

mutex // 一个互斥锁，任何线程访问都必须先获得mutex

condition //一个或者多个，每个条件变量都包含一个等待队列

balabala //共享变量及其访问方法

特点

• 采用面向对象方法，简化线程同步
• 同一时刻仅有一个线程在管程中工作
• 可临时放弃管程的访问权，叫醒一个在等待队列中的线程，这是其他方法都没有的(原子锁和信号量一旦进入临界区就必须执行完临界区代码才能退出)，而实现这一点采用的就是条件变量

类型

• Hansan 管程
• Hoare 管程

实现

管程类型提供了一组由程序员定义的、在管程内互斥的操作

monitor monitor-name {
    shared variable declarations
    procedure body P1() {   }
    procedure body Pn() {   }
    {initialization code}
}

同一时刻管程内只有一个进程在活动，因此不需显式地编写同步代码

条件变量

为了让进程在管程内等待，必须声明一些 condition 类型的变量，即条件变量

条件变量两种操作

• x.wait() 进程挂起
• x.signal() 被挂起的进程重新活动

注意

这里的 wait 和 P 操作是不一样的，最大的不同就是他一定会将自己阻塞同时释放锁。而 signal 如果没有等待线程相当于一个空操作。而且 numWaiting 不可能为负数

Process Synchronization 3

一些经典的同步问题

1. 读写者问题

前提条件

1. 写者、读者互斥访问文件资源。
2. 多个读者可以同时访问文件资源。
3. 只允许一个写者访问文件资源。

两种情况

1. 读者优先

• 没有读者会因为有一个写者在等待而去等待其他读者的完成
• 写者执行写操作前，应该让所有读者和写者退出
• 除非有一个写者在访问临界区，其他情况下，读者不应该等待

2. 写者优先

如果一个写者等待访问对象，那么不会有新读者开始读操作

读者优先的实现

初始化变量

BINARY_SEMAPHORE wrt=1;
BINARY_SEMAPHORE mutex=1;
int readcount=0;

Reader:

do {
    wait(mutex);    //Allow 1 reader in entry
    readcount=readcount+1;
    if(readcount==1)
        wait(wrt);  //1st reader locks writer
    signal(mutex);
        //reading operation
    wait(mutex);
    readcount=readcount-1;
    if(readcount==0)
        signal(wrt);    //last reader frees writer
    signal(mutex);
}

Writer:

do {
    wait(wrt);
        //writing operation
    signal(wrt);
}

写者优先的实现

初始化变量

BINARY_SEMAPHORE read=1;    //使有写者进行操作时读者等待
BINARY_SEMAPHORE file=1;    //使文件操作互斥
BINARY_SEMAPHORE mutex1=1;  //使改变readcount的方法互斥
BINARY_SEMAPHORE mutex2=1;  //使改变writecount的方法互斥
int readcount=0;
int writecount=0;

Reader:

do {
    wait(read); //等待直至读者队列没有阻塞，即全部写者都退出，同时自身进入后再次上锁，使后来的读者等待，因为接下来要进行一系列互斥的操作
    wait(mutex1);
    readcount++;
    if(readcount==1)    //第一个读者进入
        wait(file);     //后来的写者无法操作文件，但对后来的读者的文件操作不造成影响
    signal(mutex1);
    signal(read);   //释放
        //read operation
    wait(mutex1);
    readcount--;
    if(readcount==0)
        signal(file);
    signal(mutex1);
}

Writer:

do {
    wait(mutex2);
    writecount++;
    if(writecount==1)   //第一个写者进入
        wait(read); //阻塞读者队列
    signal(mutex2);
    wait(file);
        //write operation
    signal(file);
    wait(mutex2);
    writecount--;
    if(writecount==0)   //最后一个写者退出
        signal(read);   //释放读者队列
    signal(mutex2);
}

哲学家进餐问题

前提条件

5 个哲学家围着桌子吃饭，筷子只有 5 枝，分别在每个哲学家的左手边和右手边。哲学家必须得到两只筷子才能吃饭，要使每个哲学家都能吃到饭，该如何调度

解决方法

只有左右两只筷子都可用时，才允许一个哲学家拿起它们

管程实现

void philosopher(int i) {   //主方法
    while(true) {
        thinking();
        dp.pickup(i);
        eating();
        dp.putdown(i);
    }
}

monitor dp {
    enum{thinking,hungry,eating} state[5];
    condition self[5];
    void pickup(int i) {
        state[i]=hungry;    //设置本人为饥饿状态
        test[i];    //测试左右两个人是否在吃
        if(state[i]!=eating)    //如果需要等待
            self[i].wait();     //进入等待，在pickup方法处阻塞
    }
    void putdown(int i) {
        state[i]=thinking;
        test((i+4)%5);      
        test((i+1)%5);  //本人放下筷子后，状态发生了变化，测试左右两个是否等待吃，如有，则给他们开始吃的机会（但也不一定能马上开始吃）
    }
    void test(int i) {
        if((state[(i+4)%5]!=eating) && (state[i]==hungry) && (state[(i+1)%5]!=eating)) {    //如果左右两个人并没有在吃，而且自己处于饥饿状态
            state[i]=eating;    //设置状态为eating
            self[i].signal();   //释放pickup方法，在philosopher方法中下一步将执行eating操作
        }
    }
    initializationCode() {
        for(int i=0;i<5;i++)
            state[i]=thinking;
    }
}

生产者消费者问题

前提条件

一个生产者，一个消费者，库存有限，如何能持续生产

解决思路

对于生产者，如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒生产者，让它再次将缓存填满。若消费者发现缓存是空的，就去睡觉了。下一轮中生产者将数据写入后就叫醒消费者。

不完善的解决方案会造成“死锁”，即两个进程都在“睡觉”等着对方来“唤醒”。

伪代码

初始化变量：

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲库存空间
semaphore full=0;  //库存初始化为空

生产者进程：

producer ()
{
    while(1)
    {
        produce an item in nextp;  //生产数据
        P(empty);  //获取空闲库存单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //库存数加1
    }
}

消费者进程：

consumer ()
{
    while(1)
    {
        P(full);  //获取库存数单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从库存中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空闲库存数加1
        consume the item;  //消费数据
    }
}