操作系统概念——进程间同步

第五章 进程间同步

5.1 背景
race condition: 多个并发协同进程操作共享的数据,结果依赖于执行的顺序(语义混乱).
需要可靠的进程间同步/协调机制.

5.2 临界区访问
临界区机制需要解决下面三个问题:
1. 互斥访问:同一时间只有一个进程在临界区内执行
2. 可启动:总有进程能进入临界区,并且做选择时间有界(不会整体停滞)
3. 有限等待:当一个进程发起请求后,一定能在某个有限时间内进入临界区(不饿死)

5.3 Peterson方案
基于软件的临界区访问解决方案,主要在于指导和参考意义:

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);

    // critical section

    flag[i] = false;

    // remainder section
} while (true);

说明:
2个进程并发(i=0,1),flag[i]表示进程i将尝试进入临界区,turn == j表示允许进程j进入临界区(互相谦让).
互斥访问:turn只能取1个值,最终获得许可(谦让)的1方才可进入临界区.
有限等待:当i方结束临界区后,在等待的j方要么因对方还没有重新尝试,要么因对方设置了许可(turn=j),所以一定可以进入.

5.4 硬件同步指令
现代硬件系统提供一些原子指令可以使用锁机制来实现临界区:
test_and_set指令:

//test_and_set原子指令逻辑
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

//使用test_and_set实现临界区访问, lock初始化为false
do {
    while (test_and_set(&lock))
        ; /* do nothing */

    /* critical section */

    lock = false;

    /* remainder section */
} while (true);

compare_and_swap指令:

//compare_and_swap原子指令逻辑
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

//使用compare_and_swap实现临界区访问,lock初始化为0
do {
    while (compare_and_swap(&lock, 0, 1) != 0)
        ; /* do nothing */

    /* critical section */

    lock = 0;

    /* remainder section */
} while (true);

注意以上简单实现方式不满足临界区的有限等待条件.

5.5 互斥锁Mutex
系统提供的软件层互斥访问工具,基于硬件指令实现.

acquire() {
    while (!available)
        ; /* busy wait */
    available = false;;
}

release() {
    available = true;
}

//critical section using mutex lock
do {
    acquire();
    //critical section
    release();
    //remainder section
} while (true);

注意到这是一种忙等实现,一般也叫spinlock自旋锁,好处是不需要上下文切换开销,
但需要持续消耗cpu,因此仅适用于临界区时间很短锁竞争程度很低的场景.

5.6 信号量Semaphores
提供一种资源记账机制,可用于更复杂的同步协作场景.
一般分为二元信号量和多元信号量两类,前者和Mutex类似可用于互斥访问场景,也可用于运行时指定代码依赖顺序;后者多用于有限资源竞争.
和Mutex不同信号量可以由不同的进程对其做wait(P)和singal(V)操作.
信号量的非忙等实现:基于进程的阻塞和唤醒,操作系统做切换调度,适用于长时间占用资源的场景.

//每个semaphore有一个其上的进程等待队列,一般是PCB链表
typedef struct {
    int value;
    struct process *list;
} semaphore;

//wait操作
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        //add this process to S->list;
        block();
    }
}

//signal操作
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        //remove a process P from S->list;
        wakeup(P);
    }
}

注意此时value可以为负,其绝对值含义为当前等待该信号量资源的进程个数.
block和wakeup一般为OS提供的系统调用,等待队列采用FIFO可以防止饿死.
被wakeup的进程不一定马上执行,取决于cpu调度.
SMP系统上,对wait和signal原子操作本身可以采用基于compare_and_swap的临界区保护实现(单处理器的话关闭中断即可).
此时虽然同样引人了自旋等待,但由于wait和signal临界区很简短,因此遇到被占用而进入忙等的情形极少发生.

死锁问题:一个进程集合中,每个进程都在等待集合中的另一个进程的某个事件发生.
无限期等待(饿死)和死锁不同 (活锁?).

优先级逆转问题:当一个高优先级在等待一个低优先级资源锁的时候,后者被一个中优先级的进程抢占了,反转了执行优先级.
优先级继承:低优先级进程占用相关资源时临时获得高优先级进程的priority,防止上述抢占发生。资源释放后优先级重置.

5.7 经典进程同步问题
生产-消费者问题:

int n; //buffer数量
semaphore mutex = 1; //互斥共享buffer访问
semaphore empty = n; //空buffer资源
semaphore full = 0; //满buffer资源

//producer
do {
    . . .
    /* produce an item in next produced */
    . . .
    wait(empty);
    wait(mutex);
    . . .
    /* add next produced to the buffer */
    . . .
    signal(mutex);
    signal(full);
} while (true);

//consumer
do {
    wait(full);
    wait(mutex);
    . . .
    /* remove an item from buffer to next consumed */
    . . .
    signal(mutex);
    signal(empty);
    . . .
    /* consume the item in next consumed */
    . . .
} while (true);

读者-写着问题:
第一类读者-写者问题:当没有写者占用互斥锁时,新的读者请求始终能得到满足,除非互斥锁已经被写者占有,
即新的读者不会因为有写者正在等锁而开始等待先前的读者完成.
第一类读者-写者问题倾向于让读者执行,但并不是说读者会优先写者抢到锁,如写者释放锁时,可能是某个排队的读者先抢到锁,
也可能是某个排队的写者先被唤醒,取决于具体的调度实现.

//第一类读者-写者问题信号量实现
//writer process structure
do {
    wait(rw_mutex);
    . . .
    /* writing is performed */
    . . .
    signal(rw_mutex);
} while (true);

//reader process structure
do {
    wait(mutex); //mutex用于count互斥访问
    read_count++; //read_count用于计算当前读者数量
    if (read_count == 1)
        wait(rw_mutex);  //rw_mutex为读写互斥锁,第一个读者获取
    signal(mutex);
    . . .
    /* reading is performed */
    . . .
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw mutex); //最后一个读者释放互斥锁
    signal(mutex);
} while (true);

第二类读者-写者问题是指总是优先满足写请求,既当有写者等待时,其他等待读者不能优先获得锁.
第一类读者-写者问题可能会饿死写者,第二类可能会饿死读者;存在一些变体问题提出了解决方法.
读写锁:从读者-写者问题中抽象出来的互斥工具,获取琐时需要制定模式(read/write),读模式共享读访问,写模式互斥.
读写锁一般实现较重,因此适用于读多写少的场景.

哲学家圆桌就餐问题:
主要代表一类有限共享资源进程间合理分配问题,如何防止死锁和饿死?
一个可能死锁的示意:

//Not Dead-Lock Free!
semaphore chopstick[n]; 
do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % n]);
    . . .
    /* eat for awhile */
    . . .
    signal(chopstick[i]);
    signal(chopstick[(i+1) % n]);
    . . .
    /* think for awhile */
    . . .
} while (true);

例如当所有人同时拿起左边的筷子时就死锁了.
解决死锁的几个方案:
a) 只允许n-1个哲学家就餐 (增大资源或减少进程)
b) 如果不能同时拿起一双筷子,则都放下(资源整体获取)
c) 非对称化:如奇数编号的哲学家先拿左筷子,偶数编号的哲学家先拿右筷子 (资源获取顺序)
然后即使不产生死锁仍有可能有饿死的问题,需要另外考虑.

5.8 Monitors
Monitor是一类基于ADT类型的语言层面并发编程辅助工具,ADT的状态部分即多进程环境中并发访问的数据,
各进程通过ADT的函数接口操作共享数据,Monitor的特性是保证同一时间只有一个进程在执行ADT的函数(Monitor区域).
Monitor主要解决开发者因信号量等使用不当造成较难调试和复现的时序问题,试图通过上层封装降低编程难度,保证正确的并发操作时序.
一般会配合引入条件变量通知机制(x.wait()/x.signal())以达到更实用的同步控制能力.

例如,采用5.7小节末b方案的哲学家问题的Monitor示意实现:

//哲学家进餐,Monitor实现
enum {THINKING, HUNGRY, EATING} state[5]; 

monitor DiningPhilosophers
{
    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();  //如果不能同时拿起左右一双筷子,就先等着
    }

    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;
            self[i].signal();    //两边的筷子可用,开吃
        }
    }

    initialization code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

注意Monitor本身保证了多进程互斥访问其函数(后面讨论实现),因此不会有2个人同时进入pickup成功.

关于Monitor特性的实现,互斥访问可以用二元信号量(Mutex),但同时要考虑引入了条件变量后导致的行为变化:
condition x;
x.wait(); //P1进程在x上等待条件满足通知
x.signal(); //P2通知x上等待的进程,如果等待队列为空则无任何影响

考虑P1进入等待时,可能需要释放其占有的Mutex,否则其他进程无法进入Monitor进而产生P1需要的条件.
当P2调用了x.signal()后,谁接着执行的问题:
a) P1被唤醒执行,则P2必须进入等待,直到P1退出Monitor区域或者进入了另一个等待;因为根据定义,P1和P2不能同时在Monitor区域执行.
b) P2接着执行,直到其退出Monitor区域或者进入了另一个等待后,再唤醒P1.
一般如果担心x映射的条件可能会立即发生改变,则应优先执行P1,即上面的a).

基于信号量的Monitor和condition变量实现示意:

//mutex: Monitor区域互斥锁信号量,初始为1
//next_count: 在进行了signal操作后挂起等待的"唤醒者"进程数量(即上面调用x.signal()的P2)
//next: "唤醒者"等待信号量,初始为0
//x_sem: 用于实现条件变量wait的信号量,初始为0
//x_count: 在x上wait的进程数量

//ADT函数
function F() {
    wait(mutex); //Monitor互斥锁
    ...
    //body of Function
    ...
    if (next_count > 0)
        signal(next);  //如果有,则退出前通知等待中的"唤醒者"..
    else
        signal(mutex);
}

x.wait() {
    x_count++;
    if (next_count > 0)
        signal(next); //本进程要进入等待,如果有其他等待中的"唤醒者"则通知其继续..
    else
        signal(mutex); //让其他进程能进入Monitor区域并通知x
    wait(x_sem);
    x_count--;
}

x.signal() {
    if (x_count > 0) {
        next_count++;
        signal(x_sem);  //唤醒通知
        wait(next); //自身进入"唤醒者"等待队列,目的是等对方执行Monitor区域完毕(退出或睡眠)
        next_count--;
    }
}

唤醒顺序机制:有时在wait时可以指定一个优先级数字(如申请资源时的资源预计占用时长),则多个进程排队的时候优先唤醒数字最小的那个.
如:x.wait(expected_time)

5.9 进程同步系统举例:
Windows:
提供dispatcher objects概念(包括mutex,信号量,事件,定时器等),有signaled state和nonsignaled state两种状态.
只能获取处于signaled状态的锁,当释放时变为nonsignaled,并通知在其上等待的进程,根据object类型决定同时1个还是多个,
如mutex只需通知1个进程,event则通知所有等待该事件的进程.
Windows下另一个机制是临界区对象,即用户态mutex;多处理器下等待临界区对象时会采用spinlock,如果等太久会转为内核mutex并让出cpu,
也即是说只有当资源争夺(contention)程度很高时内核才会介入,而一般情况下都不会太高,因此效果较好.

Linux:
内核是可抢占的,因此提供了一系列同步手段,如整数运算原子操作,主要用于计数器等简单场景.
mutex_lock/mutex_unlock 会让进程进入睡眠/被唤醒.
内核也提供了spinlock和信号量机制,在单处理器下spinlock被内核抢占开关取代:spin_lock->preempt_disable,spin_unlock->preempt_enable.
如果当前任务持有锁,则内核不允许被抢占,thread_info的preempt_count用来计数当前持有的锁的数量.
spinlock仅适用于短时间持有锁的场景,否则用信号量或mutex更加合适.

Solaris:
提供自适应Mutex机制:当等待mutex时,如果持有mutex的进程正在执行,则采用spinlock忙等方式,否则进入睡眠等待对方release(信号量方式).
读写锁实现较重,适合读者很多以及代码段较长的场景.
turnstiles: 用于组织等待同步锁中的进程,采用优先级继承机制防止优先级反转问题发生.

Pthreads同步:
用户空间同步组件库,独立于内核.
主要包括mutex、条件变量、读写锁;一般也提供信号量机制(线程或进程间);特定的实现提供spinlock等其他扩展.

5.10 其他同步方法
事务性内存(Transaction Memory):
从数据库原子性事务启发,在语言层或硬件支持,不用引入锁的概念,更不容易出错,对程序员封装了同步细节.
软件实现(STM):如编译器产生特殊代码,并决定哪些事务块可以并发执行,哪些需要底层互斥机制支持.
硬件实现(HTM):利用硬件cache层次结构和cache一致性协议来处理不同处理器缓存的共享数据冲突问题.

OpenMP:
除了提供并行化编译指令外,也提供并行化代码区内的临界区访问编译指令,临界区可单独命名.
好处是比mutex等更易用,但底层原理类似,程序员同样要自己规划临界区,同样会有死锁等类似问题.

函数式编程语言:
与过程式语言不通,在函数式语言中变量状态是不可改变的(不持续维护),因此不存在race condition、死锁等问题.. (wow!)
如Erlang和Scala,前者即因为并发编程友好而广受关注.

发表评论

电子邮件地址不会被公开。