进程同步和互斥

2017-03-23 本文已影响0人棨帆

在描述一个程序时，我们总是认为内部有一个“小人”，可以按程序所规定的步骤来执行程序。然而，在实际的系统中并不是这样。正如之前所讲，即使在程序中所描述的一条简单语句，也是由多条执行指令构成的。

根据系统的设计，在语句执行期间，也有可能发生中断或调度，从而导致和当前进程无关的程序先一步执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程制约，以控制它们的执行速度和对资源的竞争。

互斥

一组并发进程中的一个或多个程序段，因为共享某一个公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。

临界区(critical section)，即每个进程中访问临界资源的那段程序。（临界资源是一次仅允许一个进程使用的共享资源。）每次只准许一个进程进入临界区，进入后不允许其他进程进入。不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。

可以想象一下，进程Ａ和进程 B 共享一台打印机，如果让它们交替使用，那么得到的结果就如拼接画一般。因此，并发进程对临界资源的访问必须作某种限制，否则就可能出现与时间有关的错误，如：联网售票。

进程进入临界区的调度原则：

空闲让进；忙则等待
让权等待；有限等待

如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。

信号量

如何实现并发进程的互斥？

你或许会认为只需把临界区中的各个过程按不同的时间排列调用就好了。但事实并非你想的这么简单，在实现过程中，这会影响系统的执行效率，而且其要求并发进程中的每个进程事先知道其他进程和系统的动作，然而由用户程序执行开始的随机性可知，这是不可能的。

这时，我们需要一种同步机制。一个简易办法是对临界区加锁，即当进程进入临界区后，它将锁上临界区，直到进程退出为止。

这就好比学生开会想使用某个人人都可借用、且不规定使用时间的教室一样，他首先得申请使用教室的权利，然后去开教室组织班级开会，在此期间教室对外是不开放的。这时候如果有其他学生也选这个教室，当他到了教室外面发现教室被锁上了，那只好下次再来看看是不是开门了。

如此反复，浪费时间自不必说，若是有的学生可能来几十次也进不了教室门，但有的学生可能一次就进去了，或是不断进进出出，这便造成不公平现象。

生活中，最直观的办法是，设置一个教室管理员。如果有学生申请使用教室而未能如愿时，教室管理员记下他的名字，并等到教室空缺再通知该学生进入。

1965年，荷兰学者 Dijkstra 提出了信号量的概念。在操作系统中，管理员就是信号量。信号量管理相应临界区的公有资源，它代表可用资源实体。

P、V 原语

信号量的值仅能由 P，V 原语操作改变，操作系统利用它的状态对进程和资源进行管理。（P 和 V 分别来自荷兰语 Passeren 和 Verhoog，相当于英文的 pass 和 increment）

下面是 P、V 原语操作：

P(sem) {
sem = sem - 1;
if (sem < 0) {
    该进程状态置为等待状态
    讲进程的PCB插入相应的等待队列尾部
    sem.queue;
    }
}

V(sem) {
sem = sem + 1;
if (sem < = 0) {
    唤醒相应等待队列 sem.queue 中的一个进程
    改变其状态为就绪状态
    将其插入就绪队列
    }
}

信号量的物理含义：

sem > 0 表示有 sem 个资源可用
sem = 0 表示无资源可用
sem < 0 则 | sem | 表示 sem 等待队列中的进程个数
P(sem)：表示申请一个资源
V(sem)：表示释放一个资源。信号量的初值应该大于等于0

P、V操作必须成对出现，有一个 P 操作就一定有一个 V 操作

当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现

如果 P(sem) 和 P(sem) 两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要。

同步

进程同步：把异步环境下的一组并发进程，因直接制约而互相合作，互相等待，使得各进程按一定的速度运行的过程称为进程间的同步。

进程的互斥实际上是进程同步的一种特殊情况。进程互斥是进程间竞争共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；而进程同步则是涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。

生产者和消费者问题

设生产者进程和消费者进程是互相等效的，其中各生产者进程使用的过程 deposit (data) 和消费者进程使用的过程 remove(data) 可描述如下：

首先，上述生产者--消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：

消费者想接收数据时，有界缓冲区中至少有一个单元是满的；
生产者想发送数据时，有界缓冲区中至少有一个单元是空的。

另外，由于有界缓冲区是临界资源，因此，各生产者进程和消费者进程之间必须互斥执行。

由以上分析我们设公用信号量mutex保证生产者进程和消费者进程之间的互斥,设信号量avail表示有界缓冲区中的空单元数,初值为n;信号量full表示有界缓冲区中的非空单元数,初值为0.信号量mutex表示有界缓冲区中的个数,初值为1。从而有:

deposit(data)
    begin
        P(avial)
        P(mutex)
        送数据入缓冲区某单元
        V(full)
        V(mutex)
    end

remove(data)
    begin
        P(avial)
        P(mutex)
        取缓冲区中某单元数据
        V(full)
        V(mutex)
    end

模拟生产者和消费者，前提：生产和消费共享一个区域。要生产，得有地方才行，即消费的释放；要消费，要已经生产好了才行。

P、V 原语的操作次序要非常小心。一般而言，由于 V 原语是释放资源的，所以可以一任意次序出现。但 P 原语则不然，如果次序混乱，将会造成进程间的死锁。

进程互斥于同步相关内容大致如此，关于死锁问题，下次再聊。

进程同步和互斥

互斥

信号量

P、V 原语

同步

生产者和消费者问题

猜你喜欢

热点阅读