第十三章同步互斥

文章目录

同步互斥的背景
1. 原子操作
2. 进程的交互关系
同步方法

同步互斥的背景

同步互斥是操作系统中协调进程协作与相互关系的一种机制。对于并发的进程，存在多个进程共享资源的情形，那么这时进程执行就会存在不确定性与不可重现性；然而，进程并发执行具有节约资源(共享)、高速等优点，因此为了使并发的进程能够正确运行，操作系统使用了同步互斥机制。

原子操作

一次不存在任何中断与失败的操作。

操作系统需要利用同步互斥机制在并发执行的同时，保证一些操作是原子操作。

实现同步互斥机制最简单有效的方案为利用两个原子操作实现一个锁：

Lock.Acquire()：在锁释放前请求锁的进程一直处于等待状态；如果多于一个进程都在等待同一个锁，在锁释放之后，只有一个进程能够获得锁。
Lock.Release()：解锁并唤醒一个等待中的进程。

事实上，这就是用两个原子操作的锁放在一段需要是原子操作的代码两端，使这段代码的执行是原子操作。开头的锁操作称为进入临界区，代码后的解锁操作称为退出临界区。

进程的交互关系

根据进程相互感知程度的不同，进程之间的交互分为3种关系，如下表所示：

相互感知的程度	交互关系	进程间的影响
相互不感知(完全不了解其他进程的存在)	独立	进程间的操作互不影响
间接感知(双方与第三方交互，如共享资源)	通过共享进行协作	进程的结果依赖于共享资源的状态
直接感知(双方直接交互，如通信)	通过通信进行协作	进程的结果依赖于从其他进程获取的信息

此时进程间会出现如下三种状态。

互斥：一个进程占用资源，其他的进程不能使用该资源；
死锁：多个进程各自占用部分资源，形成循环等待；
饥饿：进程一直得不到资源。

同步方法

为了保证只有一个进程进入临界区执行，需要在进入临界区之前检查进程是否能够进入临界区，若可以进入，接下来设置相应”进入临界区”的标志。进程使用完资源之后，退出临界区，去除相应”进入临界区”的标志。

综上，临界区的访问规则为空闲则入、忙则等待、有限等待与让权等待(可选)。

禁用硬件中断

没有中断，没有上下文切换，因此没有并发。

硬件将中断处理延迟到中断被启用之后；
现代计算机体系结构都提供指令来实现禁用中断；

因此，进入临界区就是禁用所有中断并保存标志位；退出临界区就是启用所有中断并恢复标志位。禁用硬件中断可有效实现同步互斥，但是也有如下局限性：

禁用中断后，进程无法被停止；会使整个操作系统暂停，导致其他进程处于饥饿状态；
临界区执行时间可能很长；

因此，禁用硬件中断的方法须小心使用。

基于软件的同步

复杂(需要两个进程间的共享数据项)，是一个忙等待(浪费CPU时间)。

高级抽象的同步方法

原子操作指令1：测试与置位指令(TS指令)——从内存单元读取值并返回，期间将内存单元置1；

该指令的伪代码操作如下：

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

原子操作指令2：交换指令(exchange)，顾名思义，交互内存中的两个值。

基于上述两个原子操作指令，来实现锁。

使用TS指令实现锁：

class Lock{
    bool value;
}

Lock::__init__(){
    value=false;
}

Lock::Acquire(){
    while (TS(& value)){
        //run
    }
}

Lock::Release(){
    value=false;
}

但是上述实现是一种忙等待，改进如下：

//增加一个等待队列
class Lock{
    bool value;
    WaitQuene q;
}

Lock::__init__(){
    value=false;
    q=NULL;
}

//当进程申请不到资源时，进入等待队列，执行进程调度
Lock::Acquire(){
    while (TS(& value)){
        q.add(current);
        schedule();
    }
}

//当占用资源的进程使用完资源后，释放锁，并且将某个等待的进程从等待队列中移除并将其唤醒
Lock::Release(){
    value=false;
    current=q.remove();
    wakeup(current);
}

coming

天行健君子以自强不息