2.4 进程同步
一、进程同步基本概念
1.进程同步的主要任务：是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。
2.两种形式的制约关系
①间接相互制约关系。由于资源共享
②直接相互制约关系。主要由于进程间的合作
3.临界资源：一次仅允许一个进程访问的资源
4.临界区：在每个进程中访问临界资源的那段代码
5.同步机制应遵循的规则（4）
①空闲让进。当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
②忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
③有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
④让权等待。当进程不能进入自己的临界区时，应立即释放处理机。以免进程陷入“忙等”。
二、硬件同步机制（3）
1.关中断
进入锁测试前关闭中断，完成锁测试并上锁后打开中断。
进程在临界区时计算机系统不响应中断，不会引发调度 。
2.Test-and-Set
3.Swap
*硬件指令能有效实现进程互斥，但当临界资源忙碌时，其他访问进程必须不断进行测试，处于“忙等”，不符合让权等待原则。
三、信号量机制（4）
1.整型信号量
wait（S）{
while S＜=0 do no-op
S：= S - 1；
}
signal（S）{
S：= S + 1；
}整型量S：用于表示资源数目。
对于临界资源，S=1。
问题：wait操作中信号量S<=0时，会不停测试，进入“忙等”，未遵循让权等待的原则。
2.记录型信号量
//记录型信号量数据结构
type semaphore = record
value ：integer；
L：list of process；
end
//记录型信号量的wait（S）操作
procedure wait（S）
var S：semaphore；
begin
S.value:＝S.value-1;
if S.value＜0 then block（S.L）;
// S.value＜0，该类资源已经分配完毕，进程必须放弃处理机，自我阻塞。
end
//记录型信号量的signal（S）操作
procedure signal（S）
var S:semaphore；
begin
S.value:＝S.value+1；
if S.value≤0 then wakeup(S.L)；
// S.value≤0 ，在信号量链表中，仍有等待该资源的进程被阻塞。
end互斥型信号量：初值为1的记录型信号量
*整形型信号量与记录型信号量的问题：针对各进程之间只共享一个临界资源而言的。在有些应用场合，是一个进程需要先获得两个或更多的共享资源后方能执行其任务。
*wait(S)或signal(S)操作仅能对信号量施以加1 或减1 操作，意味着每次只能获得或释放一个单位的临界资源。
3.AND型信号量
Swait（S1，S2，...，Sn ） {
while（true）{
if（ S1≥1 and S2≥1 and…and Sn≥1 ）{
for (i = 1 ; i<= n; i++){
Si = Si – 1;
}
break;
}
else{
//某个资源Si得不到满足,把进程放进Si关联的阻塞队列中，然后程序计数器把指针移向wait操作开始
}
}
Ssignal（S1，S2，...，Sn）{
for( i = 1; i<= n; i++ ){
Si = Si+1;
//把S1到Sn关联的阻塞队列全部置空，阻塞队列中的进程直接调度到就绪队列中
}
}4.信号量集
Swait（S1，t1，d1，…，Sn，tn，dn）//tn是资源下限值，dn是需求量，满足ti≥ di
if( S1 ≥t1 &…& Sn≥tn){
for( i =1; i<=n; i++){
Si ＝Si － di;
}
}
else{
//某个资源Si得不到满足,把进程放进Si关联的阻塞队列中，然后程序计数器把指针移向wait操作开始
}
}
Ssignal（S1，d1，...，Sn，dn）{
for( i =1; i<= n; i++){
Si = Si + di；
//把S1到Sn关联的阻塞队列全部置空，阻塞队列中的进程直接调度到就绪队列中
}
}特殊信号量集：
① Swait(S,d,d)：此时信号量集中只有一个信号量S，允许每次申请d个资源。当资源数少于d时，不予分配。
②Swait (S,1,1)：S>1，记录型信号量。S=1时，互斥型信号量。
③Swait(S,1,0）：可控开关，当S>=1时，允许进入，S<1时，不能进入。
四、信号量的应用
1.利用信号量实现进程互斥
①为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量mutex，将各进程访问该资源的临界区CS置于wait（mutex）和signal（mutex）操作之间。
②wait（mutex）和signal（mutex）必须成对出现，资源型信号量同样需要成对出现，但可以分别处于不同的程序中。
2.利用信号量实现前趋关系
P1，P2共享一个信号量S，且初始化为0。在P1中将signal（S）放于语句S1后，在P2中将wait（S）放于语句S2前。即可保证执行顺序：S1->S2。
五、管程机制
虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait（S）和signal（s）。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。
一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
2.5 经典进程的同步问题（3）
一、生产者——消费者问题
生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中取数据。
1.利用记录型信号量解决生产者一消费者问题
int in=0, out=0;
item buffer [n];
semaphore mutex=1, empty=n, full=0;
void producer( );
void consumer( );
void main( ){
cobegin
producer( ); consumer( );
coend
}
void producer( ){
do{
//Produce
wait(empty);
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
}
while(TRUE);
}
void consumer{
do{
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
//Consume
}
while(TRUE);
}2.利用AND信号量解决生产者—消费者问题
int in=0, out=0；
item buffer[n];
semaphore mutex=1;
semaphore empty=n, full=0;
void producer( ){
do{
//Produce
Swait(empty, mutex);
buffer[in] = nextp;
in = (in+1) % n;
Ssignal(mutex, full);
}
while(TRUE);
}
void consumer( ){
do{
Swait(full, mutex);
nextc = buffer[out];
out = (out+1) % n;
Ssignal(mutex, empty);
//Consume
}
while(TRUE);
}二、哲学家就餐问题
1.利用记录型信号量解决（3）
(11条消息) 哲学家进餐伪代码|操作系统_写代码的资资的博客-CSDN博客
2.利用AND信号量解决哲学家进餐问题
semaphore chopstick[5]={1,1,1,1,1};
do{
……;
think;
Sswait(chopstick[(i+1) % 5], chopstick[i]);
eat；
Ssignal(chopstick[(i+1) % 5], chopstick[i]);
}while(TRUE);三、读者——写者问题
允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。
但不允许一个Writer 进程和其他Reader 进程或Writer 进程同时访问共享对象，因为这种访问将会引起混乱。
1.利用记录型信号量解决读者—写者问题
semaphore rmutex=1, wmutex = 1;
int readcount = 0;
void reader( ){
do{
//对readcount操作应互斥
wait(rmutex);
if readcount=0 then wait(wmutex); //若是第一个读者，判断有无写进程
readcount:=readcount+1;
signal(rmutex);
…
perform read operation
…
wait(rmutex);
readcount:=readcount-1;
if readcount=0 then signal(wmutex); //若已无读者，可让writer写
signal(rmutex);
}while(TRUE);
}
void writer( ){
do{
wait(wmutex)；
perform write operation;
signal(wmutex)
}while(TRUE);
}
void main(){
cobegin
reader(); writer();
coend
}2.信号量集解决读者—写者问题
int RN;
Semaphore L=RN, mx=1;
//RN标示同时允许多少读进程存在
void reader( ){
do{
swait(L,1,1);
swait(mx,1,0); //无writer写，mx=1
…
perform read operation;
…
ssignal(L,1);
}while(TRUE);
}
void writer( ){
do{
swait(mx,1,1; L,RN,0); //既无writer写，mx>=1;也无reader读，L>=RN
...
perform write operation;
...
ssignal(mx, 1);
}while(TRUE);
}
void main( ){
cobegin
reader( ); writer( );
coend
}