GroupBlog

1、进程之间的两种相互制约关系

（1）间接相互制约关系（互斥关系）

同处于一个系统中的进程，通常都共享着某种资源，如共享CPU、共享I/O设备等，所谓间接相互制约即源于这种资源共享，使系统中本来没有关系的进程因竞争资源产生了制约关系。

（2）直接制约关系（同步关系）

这种制约主要源于进程间的合作。比如输入、计算、输出。在运行过程中，某进程可能要在某些同步点上等待另一伙伴（协作进程）为它提供消息，在未获得消息之前，该进程处于等待状态，获得信息后被唤醒进入就绪态，才能被执行。

几个概念：

互斥：两个进程不能同时使用同一资源
死锁：指多个进程互不相让，都得不到足够的资源
饥饿：指一个进程一直得不到资源（其他进程可能轮流占用资源）

2、临界资源和临界区

进程的互斥是由于共享资源而引起的，为了描述这类情况，引入了临界资源和临界区的概念。

临界资源：系统中一次只允许一个进程访问的资源。如I/O设备、共享文件、共享变量等。

临界区：并发执行的进程中，访问临界资源的必须互斥执行的代码段叫临界区。

3、进程同步机制

（1）概念：

多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。

（2）进程同步机制应遵循的准则

a)空闲让进：当临界资源处于空闲状态时，允许相应的进程立即进入自己的临界区
b)忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
c)有限等待：对要求进入临界区的进程，应保证在有限时间内能进入自己的临界区
d)让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

4、临界区的互斥访问

1.可把一个访问临界资源的循环进程描述如下：

repeat
enter section
//进入区：进程在进入临界区之前，应先对预访问的临界资源进行检查，看它是否正被访问，如果没有则进入临界区对其进行访问，并设置它为正被访问状态
critical section
//临界区
exit section
退出区：将临界区正被访问的标志恢复为未被访问的标志
remainder section
until false;

2.实现方法

a)软件方法：比较复杂，需要较高的编程技巧
b)硬件指令
c)信号量机制

5、信号量(Semaphores)机制

1.整型信号量

将信号量定义为一个整形量S；S<=0表示资源已被占用；S>0表示资源可用。信号量S只能通过两个标准原子操作wait(S)和signal(S)来实现，它们在执行时是不可中断的。

wait(S)：while S<=0 do；      //请求资源
S：S-1；
signal(S)：S：S+1；        //释放资源
进入区执行wait(S)操作，退出区执行signal(S)，例如：
var s:integer；   s：=1；
parbegin
p1：begin            p2：begin
……                  ……
wait(s)；                wait(s)；
临界区代码；          临界区代码；
signal(s)；          signal(s)；
……                  ……
end；                end；
parend

2.记录型信号量

在整型信号量机制中的wait操作，只要是信号量S<=0，就会不断地测试，因此使进程进入“忙等”状态。记录型信号量机制采取了“让权等待”的策略，这时又会出现多个进程等待访问同一临界资源的情况。因此除了有一个用于代表资源数目的整型变量value外，还有一个进程链表指针，用于链接上述所有的等待进程。
记录型信号量可描述为：

type semaphore=record
value：integer；
L：list if process；
end

wait(S)可描述为：

procedure wait(S)                       //请求资源
var S： semaphore；
begin
S.value:=S.value-1；     // 相应的资源减少一个
if S.value<0 then block(S.L) ；
//小于0，该类资源已分配完毕，进程自我阻塞，放弃处理机，并插入到信号量链表S.L中。此时，S.value的绝对值表示在链表中已阻塞进程的个数
end

signal(S)可描述为： //释放资源

procedure signal(S)
var S: semaphore；
begin
S.value:=S.value+1;             //资源数目加一个
if S.value<=0 then wakeup(S.L)；     
//仍然<=0表示在链表中仍有等待资源的进程被阻塞，应唤醒链表中的第一个等待进程
end

如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

3.ADD型信号量

当某进程要先获得多种临界资源后才能执行时，容易处于僵持状态（死锁）。AND同步机制的基本思想是：将进程在整个运行中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放，只要尚有一个资源未能分配给进程，其他所有可能为之分配地资源也不给它。

Swait(S1,S2,……Sn)
if  S1>=1 and …and Sn>=1  then
    for i:=1 to n do 
    Si=Si-1；
    endfor
else
    自我阻塞，插到第一个Si<1的队列Si.L，并将程序计数定位到Swait操作的起点
endif

Ssignal(S1,S2,……Sn)
if  S1>=1 and …and Sn>=1  then
    for i:=1 to n do 
    Si=Si+1；
    endfor

4.信号量集

集，说明是不止一个，前面讲的记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量加一或者减一，即每次只能获得或者释放一个资源，而当一次需要N个资源时，便要进行N次wait(S)操作，显然很低效；还有一种情况是，当资源低于某一下限值时不予分配，这样每次分配前都需要测试该资源的数量。
当一次需要申请n种资源且资源Si申请di个资源，该类资源的可用数目低于某下限值ti时不予分配，这样就需要对ADD信号机制进行扩充，形成信号量集机制。

Swait(S1,t2,d1,……Sn,tn,dn)
if  S1>=t1 and …and Sn>=tn  then
    for i:=1 to n do 
    Si=Si-di；
    endfor
else
    自我阻塞，插到第一个Si<ti的队列Si.L，并将程序计数定位到Swait操作的起点
endif

Ssignal类似。

信号量集的特殊情况：

a)AND信号量是所有ti、di都等于1的特例
b)Swait(S，d，d)一个信号量，每次申请d个，低于d个不分配
c)Swait(S，1，1)退化为一般记录型信号量，但操作有差别
d)Swait(S，1，0)特殊信号量，当S>=1时，允许多个进程进入特定区；当S变位0后，将阻止任何进程进入特定区，相当于一个开关。

整型和一般记录型信号量是先减再分配，ADD和信号量集是先判断后减。

6、信号量机制的作用

1）使用信号量实现进程间的互斥

为临界资源设置一个互斥信号S，并设其初值为1，在每个进程中将临界区代码置于wait(S)和aignal(S)原语之间。

2）使用信号量实现进程间的同步

前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成。
为每个前趋关系设置一个互斥信号量S，其初值为0。

3）利用信号量实现前趋关系

当进程P1中有语句S1，进程P2中有语句S2两个并发执行希望S1执行后再执行S2，要实现这种前趋关系只需共享一个共用信号量S并赋初值0，将signal(S)放在语句S1后，而在S2之前插入wait(S)。

7、wait-signal操作讨论

1）信号量的物理含义

S>0：表示有S个资源可用
S=0：表示无资源可用
S<0：绝对值表示等待队列或链表中的进程个数
信号量的初值应大于等于0
wait(S)：申请一个资源
signal(S)：时放一个资源

2）wait-signal操作必须成对出现

互斥操作时，它们同处一进程
同步操作时，不在同一进程出现

3）wait-signal操作的优缺点

优点：简单而且表达能力强，可解决任何同步互斥问题
缺点：不够安全；使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂