内功修炼之操作系统学习（三：同步、通信及死锁）

内功修炼之操作系统学习三：同步、通信及死锁

进程并发性是指一组进程的执行在时间上是重叠的。所谓时间重叠是指一个进程执行第一条指令是在另一个进程执行完最后一条指令之前开始的。从宏观上来看，并发性反映一个时间段内有几个进程都处于运行态但尚未结束的状态。从微观上来看，任一时刻仅有一个进程的一个操作在处理器上执行。

现代计算机硬部件能同时进行工作，程序的编制决定不同硬部件并行工作的能力。好的程序能够充分发挥设备的并行工作能力，从而提高计算机系统的效率。

一个程序被分成若干可同时执行的小程序的程序设计方法称为并发程序设计。多个进程相互协作、相互制约。

并发进程可能是无关的，也可能是交互的，无关的并发进程是指它们分别在不同的变量集上操作，一个进程的执行与其他并发进程的进展无关。交互的进程共享某些变量，一个进程的执行可能会影响其他进程的执行结果，因此交互的并发进程之间具有制约关系，它们之间的执行必须有所控制，否则将会出现不正确的结果。

时间无关：多个进程执行的相对次序不影响最终结果。

并发进程的无关性是进程的执行与时间无关的一个充分条件，这由Bernstein提出，假设：

R(p1);程序p1执行期间所引用的变量集。

W(P1);程序p1执行期间所改变的变量集。

若两个进程能满足Bernstein条件，

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)=φ,则称并发进程的执行与时间无关。

并发程序设计实在多道程序设计的基础上发展起来的，它可以充分发挥硬件的并行性，消除处理器和设备的互等现象，提高系统效率。计算机硬部件能并发工作仅具备提高效率的可能性，并行工作的实现还需要软件技术来发挥，这种技术就是并发程序设计。

两个交互的并发进程，一个进程对另一个进程的影响往往是不可预期的，甚至是无法再现，因为它们执行的相对速度不可预测，可以出现与时间有关的各种错误。有两种形式：一结果不唯一。二永远等待。

多道程序设计中的额进程存在两种基本的关系：竞争和协作。线程的关系也类似。

竞争又称互斥，是指若干进程因相互争夺独占资源而产生的竞争制约关系。由于竞争资源的独立进程不交换信息，一个进程的执行可能影响到竞争资源的其他进程。如果有一个正在访问独占资源，另一个进程不得不等待，极端的情况下，被阻塞的进程永远得不到访问权。资源竞争会引发两个问题：一是死锁：每个进程都获得部分资源而不释放，同时还需要其他进程所占有的资源，导致相互等待的现象。二是饥饿，一个进程由于其他进程总是优先于它，而被无限期拖延，不能执行。

协作又称同步,是指为完成共同任务的并发进程，基于某个条件来协调其活动，因为需要在某些位置上排定执行的而等待、传递信号或消息所产生的协作制约关系。当一个进程到达关键点后，在尚未得到伙伴进程发来的消息或信号之前阻塞自己，当协作者发来信息号或消息后方被唤醒并继续执行。

进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，也是对进程使用资源的次序的一种协调。信号量、锁、管程、消息及其他软硬件机制都可被用作进程和线程请求和释放的资源。多数同步机制主要用于内核层。

能解决进程同步问题的技术一定可以解决进程互斥。

并发进程中与共享变量有关的程序段称为临界区(Criticalsection)。共享变量所代表的资源成为临界资源。与共享变量有关的临界区分散在各个并发进程的程序段中，当一个进程在临界区执行时，就会阻止另一个进程进入相同的临界区。各进程对共享变量的访问是互斥的。

临界区是一段程序，针对每个进程而言，每个进程都有自己的临界区，互不相关。

临界区调度的原则：互斥使用，有空让进，忙则等待，优先等待，择一而入，算法可行。

著名的生产者消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。

有n个生产者和m个消费者，在具有k个单位缓冲区内操作。Pi,ci都是并发进程，只要缓冲区未满，生产者进程pi就会不断生产产品到缓冲区。只要缓冲区非空，消费者进程就不断从缓冲区取产品。生产者和消费者共享缓冲区，但是出现错误的结果并不是因为此，而是它们访问缓冲区的速度不匹配。我们需要调整并发进程的推进速度，并发进程进程的这种制约关系称为进程同步。

当消费者发现缓冲区空时，即count==0后被调度程序暂停执行。生产者进程被调度往缓冲区内添加产品，当它发现此时counter==1,想当然的认为消费者进程是因为没有产品可取已经被挂起。于是唤醒消费者，由于消费者进程并未睡眠，唤醒信号丢失。当调度程序调度消费者进程执行时，由于已经判断过缓冲区为空，消费者进程睡眠。此后生产者不断往缓冲区添加产品，直到添加满后睡眠。两进程都在睡眠，造成所有进程永远处于睡眠状态。

最常用的同步机制是信号量、pv操作、管程和消息传递。

两个或更多进程通过信号量展开交互。一个进程在某一点上被迫停止执行直至接收到某一信号。p，v操作用来发送和接收信号量。

信号量在操作系统中主要用于封锁临界区，进程同步及维护资源计数。

信号量semaphore是一个结构体，

typedefstructsemaphore

{

intvalue;//信号量值。

structpcb*list;//信号量队列指针。存储pcb。

};

value为整型变量，初始化时赋值，list是等待使用此信号量的进程队列的头指针，初始状态为空队列。

P(s)：将信号量value值减一。若结果小于0，则执行此操作的进程被挂起，排入与此信号量有关的list所指的队列中。若结果仍大于0，则该进程继续执行。

V(s)：将信号量的值加一。若结果不大于0（说明有进程在等待），则执行此操作的进程从信号量s有关的队列中释放一个进程，使其转为就绪态。

除了初始赋值之外，信号量仅能由同步原语p和v进行操作。

1：信号量在初始时刻的初始值表示在挂起进程前，对信号量可施行的p操作数，也即信号量的值代表可用的资源数。

2：若信号量为负值，其绝对值表示此时在此信号量队列之中等待的进程个数。

3：P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作。

信号量和p，v操作可用来解决进程互斥问题。因为互斥的进程同步的一种，凡是能解决进程同步的策略都可以用来解决进程互斥。同步信号量决定能否工作，互斥信号量决定是否有人在工作。先进程并发编程时要先检测同步信号，再检测互斥信号量，且次序不能不能改变。

用信号量和p，v操作管理并发进程互斥进入临界区的一般形式为：

Semaphoremutex=1;

ProcessPI()

{

P(mutex)

{

//临界区

}

V(mutex);

}

当有进程在临界区时，mutex为0或负值，否则mutex值为1，因为只有一个进程可用P操作把mutex减至0，故可保证互斥操作。其他试图进入临界区的进程会因为执行P(mutex)而阻塞。

信号量解决生产者消费者问题（单缓冲区）

IntB;//缓冲区。

Semaphoreempty=1;//可用缓冲区数。标示缓冲区是否为空。

Semaphorefull=0;//缓冲区可用的产品数。标示缓冲区是否满。

Voidproducer()

{

While(1)

{

Produce();

P(empty);

Append()toB;

V(full);

}

}

Voidconsumer（）

{

While(1)

{

P(full);

Take()fromB;

V(empty);

Consume();

}

}

消费者和生产者问题，使用了两个信号量，empty用来表示当前空的缓冲区个数，full用来表示可以取产品的缓冲区个数。初始时empty等于缓冲区的个数。full当然就是0。一定要注意生产者消费者可能都有多个线程，使用一个信号量是不能完成生产者消费者同步工作的。

对于单缓冲区，不存在生产者和消费者同时访问缓冲区的情况。而对于多个缓冲区情况会稍微复杂些，有可能存在同时访问缓冲区的情况，这是不被允许的。需要采取措施防止此种操作。可以采用信号量也可以使用互斥量。

ItemB[k];

Semaphoreempty=k;

Semaphorefull=0;

Semaphoremutex=1;

Inti=0;

Intout=0;

Voidproducer()

{

Produce();

P(mutex);

P(empty);

AppendtoItem[in];

In++=%k;

V(full);

V(mutex);

}

Voidconsumer()

{

P(mutex);

P(full);

TakefromItem[out];

Out++=%k;

V(empty);

V(mutex);

}

上述是针对多缓冲区的操作，P(muex)和V(mutex)必须成对出现，它们之间的就是进程临界区。上述代码存在问题：当缓冲区存满k件产品时，此时empty=0，mutex=1,full=k;此后生产者又生产了一件产品，当它向缓冲区存放产品时将在P(empty)上等待，此时empty=-1，由于此时mutex=0，已经占有了缓冲区，消费者会在p(full)上等待。这就导致了互相等待的情况。所有在使用信号量和PV操作实现进程同步时，特别要当心P操作的顺序，而V操作的顺序无关紧要。无论何时应先判断同步信号，再判断互斥信号。下面是改正后的代码。

Voidproducer()

{

Produce();

P(empty);

P(mutex);

AppendtoItem[in];

In++=%k;

V(mutex);

V(full);

}

Voidconsumer()

{

P(full);

P(mutex);

TakefromItem[out];

Out++=%k;

V(mutex);

V(empty);

}

读者和写者也是一个经典的并发程序设计问题。有两组并发线程：读者和写者，它们共享文件F。要求：

1：允许多个读者读取文件。

2：只允许一个写者执行写操作。

3：任何写者工作前，必须等待所有读者释放对文件的战友。

4：写者工作时不允许其他读者或写者工作。

仅仅使用信号量并不能解决此问题。必须引入计数器对读者进行计数，专门定义一个互斥信号量用于对计数器的互斥访问。另一个信号量表示是否允许写的信号量。

Intcount=0;

Semaphorewrite=1,mutex=1;

Voidreader()

{

P(mutex);

Count++;

If(count==1)

P(write);//判断是否有写者在对文件进行写操作，有的话读者阻塞。只有第一个读者才进行此判断。

V(mutex);

{

//读文件。

}

P(mutex);

Count--;

If(count==0)

V(write);//当所有读者都退出时释放对文件的占用。只要有读者在占用文件，就不释放对文件的占用。

V(mutex);

}

VoidWriter()

{

P(write);

{

//写文件。

}

V(write);

}

当存在读者时，写者将会被阻塞。且只要有一个读者在读文件时，随后而来的其他读者都允许访问文件，从而导致写者长时间等待，这可能出现饥饿现象。

在windows中P操作和V操作分别对应WaitForSingleObject和ReleaseSemaphore。

为获得被保护资源的访问权，进程或线程要调用一个等待函数并传入信号量的句柄，在内部等待函数会检查信号量的当前资源计数。如果它大于0，那么该函数会把资源计数器减1,调用线程继续执行。如为0，系统会让调用线程进入等待状态。所有这些操作都是原子的。

ReleaseSemaphore递增信号量的资源计数，此时会从信号量等待队列中释放一个线程，将其加入就绪队列使其变为可调度状态。。

进程使用独占型资源必须按照：申请资源、使用资源、归还资源的次序。若资源不可用则申请进程进入等待态。许多情况下进程需要独占方式访问多个资源，当操作系统允许多个进程并发时，可能出现进程永远被阻塞的现象。此现象被称为死锁。产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略、进程对资源的使用要求以及并发进程的推进顺序有关。

如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的时间，而无限期陷入僵持的局面称为死锁。

死锁的解决方法主要有：死锁防止、死锁避免、死锁检测和恢复。这些方法也适用于线程。

产生死锁的条件：

1：互斥条件：存在临界资源，互斥的使用之。

2：占有和等待条件：进程在请求资源得不到满足时，不释放已占有资源。

3：不剥夺条件，已占用的资源只能由拥有它的进程释放，不允许其他进程剥夺。

4：循环等待条件：存在循环等待链。每个进程都在链中等待下一个进程所持有的资源，造成永远等待。

前三个条件是死锁存在的必要条件，不是充分条件。第四个条件是前三个的结果。只要破坏四个条件中的一个，就可以防止死锁。

死锁防止策略：

1：破坏互斥条件。

使资源可同时访问而非互斥使用，也就没有进程会阻塞在资源上，而不会发生死锁。

2：破坏占有和等待条件

静态分配可以解决占有和等待条件。静态分配是指进程必须在执行之前就申请所需要的全部资源，直至所有的资源都得到后才开始执行。但这种策略会严重降低资源利用率。

3：破坏不剥夺条件

剥夺调度能够防止死锁，但只是用于主存和处理器资源。方法是占有资源的进程若要申请新的资源，必须主动释放已占用资源。

4：破坏循环等待条件。

采用层次分配策略，将系统中所有资源排列到不同的层次中，一个进程得到某层的一个资源后，只能再申请较高一层的资源。当进程释放某一层的资源时必须先释放所占用的较高层资源。

各种死锁防止算法能够防止发生死锁，但会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反：如果一个进程当前请求的资源会导致死锁，系统将拒绝启动此进程。如果一个资源分配会导致下一步死锁，系统便拒绝本次分配。

银行家算法是能够避免死锁调度的一种算法。但是它需要在运行前知道所需的资源的最大量，因而缺乏实用价值。