『操作系统』 进程的描述与控制 Part2 进程同步

文章目录

• 2.4 进程同步
• • 2.4.1 进程同步的基本概念
  • • 1、两种制约关系
    • 2、临界资源
    • 3、临界区
    • 4、同步机制应遵循的规则
    • 练习题
    • • 练习题
  • 2.4.2 实现互斥的软硬件方法
  • • 算法1
    • 算法2
    • 算法3
    • 算法4
    • • 练习题
    • 硬件设施
    • • 练习题
      • 练习题
  • 2.4.3 信号量机制及应用
  • • 1.整型信号量
    • 2.记录型信号量
    • • 练习题
    • 3.AND型信号量
    • 4. 信号量集
• 2.5 经典的进程同步问题
• • 生产者-消费者问题
  • • 问题描述：
    • 1.利用记录型信号量解决生产者—消费者问题
    • • 练习题
  • 读者-写者问题
  • • 问题描述：
    • 解法一
    • • 常规解法
      • 2.利用信号量集解决读者-写者问题
      • 练习题
  • 哲学家就餐问题
  • • 问题描述
    • 1. 利用记录型信号量解决哲学家进餐问题
    • • 方法1：增加一个信号量s，控制同时请求进餐人数， 初值为4.
      • 方法2、利用AND信号量机制解决哲学家进餐问题
      • 方法3:奇偶号区别对待
    • Wait/Signal原语对信号量的操作可以分为三种情况
    • • 情况一
      • 情况二
      • 情况三

2.4 进程同步

2.4.1 进程同步的基本概念

1、两种制约关系

（1）直接： 相互制约关系源于进程合作，表现为： 进程—进程 （同步：合作完成任务的关系！） 为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。 这种制约主要源于进程间的合作。 发生在相关进程之间 eg:

• 同步进程间具有合作关系
• 在执行时间上必须按一定的顺序协调进行 （2）间接： 相互制约关系源于资源共享,表现为： 进程—资源—进程 （互斥：竞争使用资源的关系！） 发生在任何进程之间 互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系！
• 互斥进程彼此在逻辑上是完全无关的
• 它们的运行不具有时间次序的特征

2、临界资源

一次仅允许一个进程使用的共享资源 生产者—消费者问题：

• 有一群生产者进程生产产品供给消费者进程消费；
• 为使两者并发执行，在两者之间设置具有n个缓冲区的缓冲池；
• 生产者每生产一个产品就放入一个缓冲区中；
• 消费者从缓冲区中取产品消费；
• 生产者进程和消费者进程都以异步方式运行；
• 但它们在某些点上必须保持同步。

输入指针加1表示为 in:=(in+1)mod n
输出指针加1表示为out:=(out+1)mod n
当out=in时表示缓冲池空
(in+1)mod n=out时表示缓冲池满。

//生产者进程和消费者进程共享的变量：
int  n;
typedef struct {……} item;
item  buffer[n];
int in, out;
int counter;

//生产者
Producer(){ 
  while(1){
     …
     produce an item 
         in nextp;  
     …
     while(counter==n) 
         do no-op;
     buffer[in]=nextp;
     in=in+1 mod n;
     counter++;
  }}

//消费者
Consumer(){
  while(1){
     while(counter==0) 
         do no-op;
     nextc=buffer[out];
     out=out+1 mod n;
     counter--;
     consume the item
          in nextc;
  }
}

锁操作原语： 为某临界资源设置一把锁W(布尔量)， 设：当W=1时，表示锁是关闭的； 当W=0时，表示锁已打开。

则开锁、关锁原语如下：

//关锁：
Lock(W):  
   while(W==1);
   W=1;
//开锁：
unLock(W):  
   W=0;

3、临界区

• 每个进程中访问临界资源的那段程序
• 进程必须互斥进入相关临界区

进入区:对欲访问的临界资源进行检查，若此刻未被访问，设正在访问的标志 临界区:访问临界资源 退出区:将正在访问的标志恢复为未被访问的标志 剩余区:其余部分

4、同步机制应遵循的规则

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

练习题

一、选择题 1. 下列关于临界区和临界资源说法正确的有©。 I.银行家算法可以用来解决临界区(Critical Section)问题。 II.临界区是指进程中用于实现进程互斥的那段代码。 III.公用队列属于临界资源。 IV.私用数据属于临界资源。 A.I、II B. I、IV C.只有III D.都错

2. 我们把在一段时间内，只允许一个进程访问的资源，称为临界资源，因此，我们可以得出下列结论，正确的结论是(D)。 A. 对临界资源是不能实现资源共享的 B. 为临界资源配上相应的设备控制块后，便能被共享 C. 对临界资源应采取同时访问方式，来实现共享 D. 对临界资源，应采取互斥访问方式，来实现共享

3. 一个正在访问临界资源的进程由于申请等待I/O操作而被阻塞时（③） ①可以允许其他进程进入与该进程相关的临界区 ②不允许其他进程进入任何临界区 ③可以允许其他就绪进程抢占处理器，继续运行 ④不允许任何进程抢占处理器

4. 进程间的基本关系为（B）。 A．相互独立与相互制约 B．同步与互斥 C．并行执行与资源共享 D．信息传递与信息缓冲

5. 进程间的同步与互斥，分别表示了各进程间的（D）。 A.相互独立与相互制约 B.动态性与独立性 C.不同状态 D.协调与竞争

6. 若干进程之间相互合作，共同完成一项任务,进程的这种关系称为(D)。 A.互斥 B.并发 C.异步 D.同步

7. 下列哪一种场景问题只包含进程互斥问题？©。 A.两个进程通过一个缓冲区传递数据 B.田径场的四百米接力比赛 C.一个进程读文件，一个进程写文件 D.公共汽车上司机和售票员的工作配合

8. 多个进程并发执行时，各个进程应互斥进入其临界区，所谓临界区是指©。 A.一段数据区 B.一种同步机制 C.一段程序 D.一个缓冲区

9. 由于并发进程执行的随机性，一个进程对另一个进程的影响是不可预测的，甚至造成结果的不正确，（A）。 A.造成不正确的因素与时间有关 B.造成不正确的因素只与进程占用的处理机有关 C.造成不正确的因素只与执行速度有关 D.造成不正确的因素只与外界的影响有关

二、判断题 1. 处于临界区的进程是不可中断的。（×） 解析： 临界区是指访问该临界资源的那段程序代码。 进程互斥是指不允许多个进程同时进入相关临界区，但并没有禁止一个进程对临界资源的访问与另一个进程非临界区代码并发执行， 即：对临界区的执行不是原语。

2. 临界区就是临界资源所在的地址。（×） 解析： 临界区是进程访问临界资源的那段代码。

3. 当两个或多个进程访问同一个临界资源时，每个进程的临界区都是相同的。（×） 解析：

• 每个进程对临界资源如何访问，与进程的功能有关，而与临界资源及互斥同步管理是无关的。
• 不可认为，临界资源相同，访问这些资源的代码就一定相同。

三、简答题 1. 进程的互斥和同步有什么异同点？试举例说明。

• 进程的同步与互斥是指进程在推进时的相互制约关系。
• 进程同步源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。
• 进程互斥源于资源竞争，是进程之间的间接制约关系。

可以简单理解为:同步是协作,互斥是竞争

2. 什么叫原语？ 答：在操作系统中，往往设计一些完成特定功能的、不可中断的过程，这些不可中断的过程称为原语。

与时间有关的错误 若一种错误的发生与进程的推进速度及外界影响有关，且进程间存在共享变量，则称这种错误为与时间有关的错误。 发生与时间有关的错误的原因： (1) 进程交叉执行。 (2) 涉及公共变量(x)。

练习题

1.[2011考研题 32]有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1, P2对x减1。加1和减1操作的指令序列分别如下所示。

//加1操作                             //减1操作
load R1,x  /*取x到寄存器R1中.*/       load R2, x
inc R1								 dec R2
store x,R1 /*将R1的内容存入x*/        store x, R2

两个操作完成后，x的值© A.可能为-1或3 B.只能为1 C.可能为0、1或2 D.可能为-1、0、1或2

解析： 执行①②⑧④⑤⑥结果为1,执行①②④⑤⑥⑧结果为2,执行④⑤①②⑧⑥结果为0，结果-1无法得到。

2. 对下列程序段：

X:=0;Y:=0;
Cobegin
   Begin
     X:=1;      ……①
     Y:=Y+X; ……②
   End
Coend

当这个程序执行完时，变量X 和Y 的值有可能为： Ⅰ. X=4,Y=2 Ⅱ. X=1,Y=3 Ⅲ. X=4,Y=6 请选出下列答案中唯一正确的一个（D） (A)Ⅰ (B)Ⅰ和Ⅱ ©Ⅱ和Ⅲ (D)Ⅰ、Ⅱ和Ⅲ

3. [2016考研真题30]进程p1和p2均包含并发执行的线程，部分伪代码描述如下所示： 下列选项中， 需要互斥执行的操作是© A．a=1与a=2 B．a=x与b=x C．x+=1 与 x+=2 D．x+=1 与 x+=3 解析：

//进程P1
int x=0;
thread1()
{   
    int a;
    a=1;x+=1;
}
thread2()
{   
    int a;
    a=2;x+=2;
}

//进程P2
int x=0;
thread3()
{   
     int a;
     a=x;x+=3;
}
thread4()
{   
     int b;
     b=x;x+=4;
}

4. 思考题： (1) 进程并发执行一定会导致结果不唯一吗？ 答： 进程并发执行可能会导致结果不唯一。 (2) 在什么情况下会顺利执行？ 答： 串行访问共享资源。 (3) 在什么情况下可能会出现错误？ 答： 同时访问共享资源。

5. 为什么说进程同步问题关系到OS的成败？ 答：

• 进程同步问题若处理不当，有可能产生种种“与时间有关性错误”，导致用户程序运行结果的不正确；
• 这种OS显然是不成功的，是用户不敢使用的。

2.4.2 实现互斥的软硬件方法

• 软件实现方法就是在进入区设置和检查一些标志来判断是否有进程在临界区，如果已有进程在临界区，则等待；
• 进程离开临界区后则在退出区修改标志。
• 关键问题是设置什么标志和如何检查标志。
• 设有两进程Pi和Pj共享一个临界资源R；
• 用软件方法使进程Pi和Pj互斥访问资源R。

算法1

设立一个公用整型变量 turn：初值为i；描述允许进入临界区的进程标识；

• 在进入区循环检查是否允许本进程进入： turn为i时，进程Pi可进入；
• 在退出区修改允许进入的进程标识： 进程Pi退出时，改turn为进程Pj的标识j；

//进程一
while (turn != i);
  critical section
turn = j;
  remainder section

//进程二
while (turn != j);
  critical section
turn = i;
  remainder section

优点： 互斥访问临界资源； 缺点： 强制轮流进入临界区； 违背“空闲让进”原则！

算法2

设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE。

• 先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程的临界区标志为true；
• 在退出区修改本进程的临界区标志为false；

//进程一
while (flag[j]);
   flag[i] = TRUE;
   critical section
   flag[i] = FALSE; 
   remainder section

//进程二
while (flag[i]);
   flag[j] = TRUE;
   critical section
   flag[j] = FALSE; 
   remainder section

优点： 不用交替进入，可连续使用； 缺点： 不能互斥进入，违背“忙则等待”原则

算法3

类似于算法2，与算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。

//进程一
flag[i] = TRUE; 
while (flag[j]);
   critical section
   flag[i] = FALSE;
   remainder section

//进程二
flag[j] = TRUE; 
while (flag[i]);
   critical section
   flag[j] = FALSE;
   remainder section

优点： 可以防止同时进入临界区； 缺点： Pi和Pj可能都进入不了临界区，出现“死等”现象；违背了“有限等待”的原则。

算法4

同时使用flag[]和turn； flag标志表示进程是否希望进入临界区或已在临界区，turn用于进程间的互相谦让。

//进程一
flag[i] = true;turn=j;
while (flag[j]&&turn==j);
   critical section
   flag[i] = false;
   remainder section

//进程二
flag[j] = true;turn=i;
while (flag[i]&&turn==i);
   critical section
   flag[j] = false;
   remainder section

• 在进入区先修改后检查，并检查并发修改的先后；
• 检查对方flag，如果不在临界区则自己进入——空闲则入；
• 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入——先到先入，后到等待；
• Flag解决了“互斥”问题，turn解决了“饥饿”问题。

练习题

1.[2010年考研试题 27]进程 P0 和 P1 的共享变量定义及其初值为： boolean flag[2]； int turn=0； flag[0]=FALSE；flag[1]=FALSE； 若进程 P0 和 P1 访问临界资源的类 C 伪代码实现如下：

void P0()   //进程 P0 
{
   while(TRUE) { 
       flag[0]=TRUE; turn=1; 
       while(flag[1]&&(turn==1)) ; 
       临界区; 
       flag[0]=FALSE; 
  } 
} 

void P1()   //进程 P1 
{
   while(TRUE) {
       flag[1]=TRUE; turn=0; 
       while(flag[0]&&(turn==0)) ; 
       临界区; 
       flag[1]=FALSE; 
   } 
}

则并发执行进程 P0 和 P1 时产生的情形是 (D)。 A．不能保证进程互斥进入临界区，会出现“饥饿”现象 B．不能保证进程互斥进入临界区，不会出现“饥饿”现象 C．能保证进程互斥进入临界区，会出现“饥饿”现象 D．能保证进程互斥进入临界区，不会出现“饥饿”现象

2.以下是解决进程互斥进入临界区的一种解法:

P:...... 
pturn = true;
while (qturn) ;
   临界区操作
pturn = false;
  ......
其中，pturn、qturn的初值为false

Q:......    
qturn = true;
while (pturn) ;
   临界区操作
qturn = false;
   ......

如果P、Q两个进程同时想进入临界区，那么会发生下面哪一种情形？(A) A.P和Q都进入不了临界区 B.P和Q都进入了临界区 C.P先进入临界区，Q再进入临界区 D.Q先进入临界区，P再进入临界区

硬件设施

1.关中断 过程:

关中断;
    临界区;
开中断;
其余部分;

特点： 简单、高效！

存在问题:

• 代价高，限制了处理器交替执行各进程的能力；
• 对多处理器结构，关中断不能保证互斥;
• 适用于操作系统本身，不适于用户进程。

2.专用的机器指令 (1)测试并设置(Test_and_Set)指令

设Lock为全局布尔变量,初值为false;
TS指令定义(逻辑):
Boolean TS(boolean  *lock) {
   boolean old=*lock;
   *lock=true;
   return old;
}
使用TS实现互斥: 
Do {
     While (TS(&Lock));
      临界区;
     lock=false;
      剩余区
   }

TS指令的功能是读出指定标志后把该标志设置为真;

(2)对换(Swap)指令

Swap指令定义：
void Swap(boolean *a, boolean *b) 
{
boolean temp=*a;
*a = *b;
*b=temp ;
}

3.利用Swap实现进程互斥

• 每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key
• 进程要使用临界资源时将会首先将自己的key置为true

key = TRUE;
do{
   swap(&lock,&key);
}while(key);
   临界区
lock=FALSE;

练习题

1.[2016考研题]使用TSL（Test and Set Lock）指令实现进程互斥的伪代码如下所示：

Do{
  ……
  whie(TSL(&lock));
  critical section;
  lock=FALSE;
  ……
}while(TRUE);

下列与该实现机制相关的叙述中，正确的是：(B) A.退出临界区的进程负责唤醒阻塞态进程 B.等待进入临界区的进程不会主动放弃CPU C.上述伪代码满足“让权等待”的同步准则 D.whie(TSL(&lock))语句应在关中断状态下执行

4、硬件方法的评价 优点 适用于任意数目的进程; 简单高效且易于证明; 可以使用多个变量支持多个临界区; 缺点 忙等待; 可能饿死； 可能死锁-优先级反转/倒置 ；

练习题

**1.**下列哪种方式不支持多处理器环境下的互斥（A）。 A.中断禁用 B.专用机器指令 C.信号量 D.管程

**2.**试分析临界区的大小与系统并发性之间的关系。 答：

• 关于同一组变量的临界区是不能并发执行的；
• 临界区越大，并发性越差；
• 因而编写并发程序应尽量缩小临界区范围。

**3.**设： CR1是关于一组共享变量SV1的临界区，CR2是关于另一组共享变量SV2的临界区，当进程P1进入CR1时，进程P2是否可以进入CR2? 为什么? 答： 可以。

• 因为互斥是针对同一资源（变量）的
• 多个进程同时进入关于不同变量的临界区不会引起与时间有关的错误。

4.利用锁操作既可以实现进程间的互斥，也能实现进程间的同步，对吗？ 答： 错误。

2.4.3 信号量机制及应用

概念： 信号量是一个仅能由原语对其进行操作的整型变量或记录型变量。之所以称其为信号量，来源于交通管理中的信号灯的概念。

信号量又叫信号灯（ semaphore ），表示资源的实体，除初值外其值仅能由Wait/Signal (P/V,down/up,sleep/wakeup)原语操作来改变。操作系统利用信号量对进程和资源进行控制和管理。

信号量代表可用资源实体的数量。

信号量

• 一般说来，信号量的值与相应资源的使用情况有关；
• 其初值表示系统中某类资源的数目；
• 除了初值外，信号量的值仅由Wait/Signal操作改变；
• 在信号量上只能进行三个操作： 初始化(非负数)、 Wait操作、Signal操作

Wait、Signal操作是原语

• Wait操作 ：申请一个单位的资源
• Signal操作：释放一个单位的资源

1.整型信号量

整型变量; 除初始值外，仅能通过两个原语来访问。

Wait操作  wait(S):	 
              while(S<=0) do no-op; 
              S=S-1;
Signal操作  signal(S):	  
               S=S+1;

Wait、Signal操作是原子操作,不可中断。 利用信号量实现进程互斥的方法： 为使多个进程互斥的访问某临界资源，须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问资源的临界区CS置于wait(mutex)和signal(mutex)之间即可。

 semaphore mutex=1;
 main(){
    cobegin{
        process 1: while(1)
        {  
           wait(mutex);                                                  
           critical section
           signal(mutex);                          
           remainder section
        }
        process 2: while(1)
        {  
           wait(mutex);
           critical section
           signal(mutex);
           remainder section
         }
    }coend
}

2.记录型信号量

整型信号量未遵循“让权等待”原则，导致“忙等”。 记录型信号量： 一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，另一个是指向PCB的指针。

• 信号量是一个二元组
• 一般由两个成员组成：数组和指针

记录型信号量： 包含两个数据项，一个是计数值域，另一个是与该信号量对应的进程阻塞队列首指针域。 信号量数据结构的定义：

struct semaphore
{
   int value;
   PCB *L;     //进程队列指针
}

void  Wait(struct semaphore s)
{
   s.value--;//申请一个单位的资源
   if(s.value<0)block(s.L)
   //若信号量计数值小于0，
   //表示无资源，则阻塞等待,
   //重新调度；否则调用进程继续。
}

void  Signal(struct semaphore s)
{
   s.value++;//释放一个单位的资源
   if(s.value<=0)wakeup(s.L)
   //若信号量计数值小于等于0
   // 表示有进程在等待该资源，
   //唤醒一个等待者。
}

信号量的值是与相应资源的使用情况有关的。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，则其绝对值表示等待使用该资源的进程数，即在该信号量队列上排队的PCB的个数。

• 每个信号量s除一个整数值s.value（计数）外，还有一个进程等待队列s.L，登记阻塞在该信号量的各个进程的标识;
• 信号量只能通过初始化和两个标准的原语来访问；
• 初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）, 若为非负值表示当前的空闲资源数， 若为负值其绝对值表示当前等待临界区的进程数。

利用记录型信号量实现进程互斥

• 分析并发进程的关键活动，划定临界区
• 设置信号量 mutex，初值为1
• 在临界区前实施 Wait(mutex)
• 在临界区后实施 Signal(mutex)

semaphore mutex=1;
main() {
   cobegin{
      Process 1
         while(1){
            wait(mutex);
            critical section
            signal(mutex);
            remainder section
         }
      Process 2
         while(1){
            wait(mutex);
            critical section
            signal(mutex);
            remainder section
         }
   }coend
}   

互斥信号量的取值范围: 记录型信号量：

• 当2 个进程互斥访问临界资源时：1，0，-1
• 当n 个进程互斥访问临界资源时：1，0，-1，-2，…，-（n-1)

整型信号量：

• Mutex的取值范围永远是1，0

Wait/signal 操作的物理意义 wait操作： 申请一个单位的资源 signal操作：释放一个单位的资源

信号量值>0：表示可用资源的数量； 信号量值<0：其绝对值代表等待使用该资源的进程数。

练习题

1. 采用信号量操作管理相关临界区时，若信号量的值可能在[-1,1]之间变化，则与相关临界区有联系的进程个数是（B）。 A 1 B 2 C 3 D 4

2. 用信号量及Wait、Signal操作管理临界区时，若信号量mutex的初值为1，当mutex的等待队列中有k（k > 1）个进程时，信号量的当前值为（A） A. -k B. k-1 C. 1-k D. k

3. n个并发进程通过初值为1的信号量s共享资源R，当n个进程都通过wait(s)申请访问资源R时，信号量s的值为（D）。 A. 0 B. n C. -n D. -(n-1)

4. 与共享资源R相关的信号量s初值为4，经过多次wait和signal操作后s当前值为-2,此时获得R的进程数是（B）。 A. 2 B. 4 C. 0 D. 6

5. 设与某资源R关联的信号量为s，若这个资源最多允许3个进程同时访问，当有5个进程申请访问R时， 采用wait和signal操作来实现同步，则信号量s的取值范围是（C）。 A. 0≤s≤3 B. 0≤s≤5 C. -2≤s≤3 D. 2≤s≤5

6. 在使用信号量及Wait、Signal操作机制解决问题时，进程执行一次Wait操作，意味着该进程(B)。 A.正在使用一个资源 B.申请分配一个资源 C.准备释放一个资源 D.需要共享一个资源

7. 在使用信号量及Wait、Signal操作机制解决问题时，一个进程执行Signal操作意味着( )。 A.该进程从等待队列进入就绪队列 B.可能有另一个进程从等待队列进入就绪队列 C.该进程从磁盘调入内存 D.可能有另一个进程从磁盘被调入内存

8. 当一个进程因在互斥信号量s上执行signal（s）操作而唤醒另一个进程时，则执行signal操作后s的取值范围是（D）。 A. 大于0 B. 大于等于0 C. 小于0 D. 小于等于0

9. 例：多个进程对信号量S进行了5次 wait操作，2次signal操作后，现在信号量的值是 -3，问与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？ 答： 解：因为S的当前值是-3，因此与S相关的处于阻塞状态的进程有3个； 设初值为X，因为每进行一次wait(S)操作，S的值都减1，每执行1次signal操作S的值加1，则：X-5+2=-3, X=0

3.AND型信号量

SWait(S1, S2, …, Sn)
    if (S1 >=1 && … && Sn>=1)
        for( i=1;i<=n;i++)
           Si= Si -1 ;
    else
      Place the process in the waiting queue associated with the first Si found with Si <1,and set the program counter of this process to the beginning of Swait operation

SSignal(S1, S2, …, Sn)
    for (i=1;i<=n;i++)
       Si= Si +1 ;
       Remove all the process waiting in the queue associated with  Si into the ready queue

4. 信号量集

SWait(S1, t1, d1, …, Sn, tn, dn)
    if (S1>= t1 && … && Sn>= tn )
        for (i=1;i<=n;i++)
           Si= Si - di ;
    else
       Place the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait Operation

SSignal(S1, d1, …, Sn, dn)
    for( i=1;i<=n;i++)
       Si= Si +di ;
       Remove all the process waiting in the queue associated with  Si into the ready queue 

一般信号量集的几种特殊情况

• Swait(S, d, d)，只有一个信号量S，允许每次申请d个资源，若现有资源数少于d，不予分配。
• Swait(S, 1, 1)，蜕化为一般的记录型信号量(S>1时)或互斥信号量(S=1时)。
• Swait(S, 1, 0)，当S>=1时，允许多个进程进入某特定区，当S<1时，阻止任何进程进入特定区，相当于可控开关。

三种信号量的比较 整型信号量->记录型信号量->信号量集机制

信号量的应用 (1) 利用信号量实现互斥

• 用于实现进程之间的互斥；
• 初值反映了公有资源的数量；
• 只要把临界区置于Wait和Signal之间，即可实现进程间的互斥；

eg:设互斥信号量为mutex (MUTual Exclusion)初值为1。

//进程一
Wait(mutex);
   critical section
Signal(mutex);
   remainder section
//进程二
Wait(mutex);
   critical section
Signal(mutex);
   remainder section

说明

• 为临界资源设置一个互斥信号量mutex，其初值为1
• 在每个进程中将临界区代码置于Wait(mutex)和Signal(mutex)原语之间
• 必须成对使用Wait和Signal原语：遗漏Wait原语则不能保证互斥访问，遗漏Signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）
• Wait、Signal原语不能次序错误、重复或遗漏

(2)用信号量实现简单同步

• 同步（私有）信号量：用于实现进程间的同步，初值为0或为某个正整数n；
• 仅允许拥有它的进程对其实施Wait操作；
• Signal操作由其合作进程来实施！

(3)利用信号量来描述前趋关系 设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。 需要为进程P2设置一个信号量S，表示前趋是否完成，并赋予其初值为0。

2.5 经典的进程同步问题

生产者-消费者问题

相互合作的进程关系的一种抽象。

问题描述：

若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。

1.利用记录型信号量解决生产者—消费者问题

• 假定在生产者和消费者之间的公用缓冲池具有n个缓冲区；
• 可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；
• 利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量；
• 假定这些生产者和消费者相互等效且互斥使用缓冲池。

例1：供者和用者通过一个单缓冲区达到同步

解答： 设2个信号量： empty—空缓冲区数（初值为1） full—满缓冲区数（初值为0）

//供者进程
while(1)
{     
    Wait（empty）;
       将信息送入缓冲区；
    Signal（full）;
}

//用者进程
while(1)
{    
   Wait（full）;
      从缓冲区取出信息；
   Signal（empty）;
}

注意： 1.每个进程中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。 2.对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但处于不同的进程中。 3.在每个进程中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起进程死锁。 4.对同一个信号量的wait与signal可以不在同一个进程中。 5.对任何信号量的wait与signal操作必须配对，同一进程中的多对wait与signal语句只能嵌套不能交叉。

练习题

1. 在生产者/消费者问题中，假设有5个生产者，5个消费者共享容量为8的缓冲空间，则实施互斥访问缓冲空间的信号量初始值为（B）。 A. 0 B. 1 C. 5 D. 8

2. 在生产者/消费者问题中，用s表示实施互斥的信号量，e表示与缓冲区空闲空间数量相关的信号量，n表示与缓冲区中数据项个数相关的信号量，下列生产者和消费者的操作（生产者和消费者可并发执行），不可能产生死锁的是（D）。 A.

生产者：
1.  wait(s);
2.  wait(e);
3.  append();
4.  signal(n);
5.  signal(s);
消费者：
6.  wait(s);
7.  wait(n);
8.  take();
9.  signal(e);
10.signal(s);	 

B.

生产者：
1. wait(s);
2. wait(e);
3. append();
4. signal(n);
5. signal(s);
消费者：
6.  wait(n);
7.  wait(s);
8.  take();
9.  signal(s);
10.signal(e);

C.

生产者：
1. wait(e);
2. wait(s);
3. append();
4. signal(s);
5. signal(n);
消费者：
6.  wait(s);
7.  wait(n);
8.  take();
9.  signal(e);
10.signal(s);

D.

生产者：
1. wait(e);
2. wait(s);
3. append();
4. signal(s);
5. signal(n);
消费者：
6.  wait(n);
7.  wait(s);
8.  take();
9.  signal(s);
10. signal(e);

读者-写者问题

问题描述：

多个进程共享一个数据区，这些进程分为两组：

• 读者进程：只读数据区中的数据
• 写者进程：只往数据区写数据 要求满足条件：
• 允许多个读者同时执行读操作
• 不允许多个写者同时操作
• 不允许读者、写者同时操作

读者－写者问题，它为数据库访问建立了一个模型。

解法一

为共享数据库设互斥信号量w=1;

void reader(void) 
{ 
    while (1) { 
    …… 
    Wait (w); 
      读操作 
    Signal(w); 
    …… 
    } 
} 

void writer(void) 
{ 
    while (1) { 
    …… 
    Wait(w); 
      写操作 
    Signal(w); 
    …… 
    } 
} 

常规解法

信号量： W = 1 控制互斥访问共享数据对象 R =1 控制读者互斥访问读者计数器 计数器： RC = 0 当前活动的读者数

读者：
……				
	Wait(R); 			
	  if(RC== 0) Wait(W);
	  RC=RC+1；
	Signal(R); 
	   读数据对象;		 	
	Wait(R);
	  RC=RC-1；
	  If (RC== 0) Signal(W);
	Signal(R);
……

写者：
……
	Wait(W);
	  对数据对象写;
	Signal(W);
……

2.利用信号量集解决读者-写者问题

• 增加一个限制：最多允许N个读者同时读。
• 因此，引入信号量L，并赋予其初值N，通过执行Swait(L,1, 1)操作，来控制读者的数目。
• 每当有一个读者进入时，就要先执行Swait(L,1, 1)操作，使L的值减1。
• 当有N个读者进入读后，L便减为0，第N +1个读者要进入读时，必然会因Swait(L,1, 1)操作失败而阻塞。
• 引入信号量w，用于写者与其他进程的互斥操作！

int  N;
semaphore L=N, w=1;
main(){   
   cobegin{   
      reader(){  
         while(1){
            Swait(L, 1, 1);
            Swait(w, 1, 0);
            ...
              read;
            ...
            Ssignal(L, 1);
         }
      }
      writer(){
         while(1){  
            Swait(w, 1, 1; L, N, 0);
               perform write operation;
            Ssignal(w, 1);
         }
      }
   }coend
}

防止写者长期等待 为了读写公平，我们增加一个信号量s，用于在写者进程到达后封锁后续的读者进程。

semaphore s=1;
main()
{ 
   cobegin{ 
      reader{ 
	     wait(s);
         wait(R);
           rc=rc+1;
           if(rc==1)wait(W);
         signal(R);
         signal(s);
           reading the file;
         wait(R);
           rc=rc-1;
           if(rc==0)signal(W);
         signal(R);
       }
      writer{ 
         wait(s);
         wait(W);
           Writing the file;
         signal(W);
         signal(s);
      }
   }coend;
}

下面算法即可实现同等优先。 其中信号量W，初值为1，用于写者与其他写者或读者之间的互斥； 另一信号量L，初值为n，表示系统中最多有n个进程可同时进行读操作。

semaphore W=1,L=N;
main(){
  cobegin
  {
     Reader(){
	    while(1){ 
		   wait(W);             //是否有写者正在写或请求写操作
           wait(L);             //读者是否可以读
           signal(W);           //允许写者申请写的权利
             ...
             perform read operation;
             ...
           signal(L);           //出来一个读者
        }
     }
	 writer(){
        while(1){
           wait(W);                     //申请写操作
           for(i=1;i<=n;i++) wait(L);   //是否有读者正在读？保证正在工作的读者读完后再执行写操作
             perform write operation;
           for(i=1;i<=n;i++) signal(L); //恢复L的初值
           signal(W);                   //唤醒被阻塞的读者或写者
        }
     }coend  
  }
}

练习题

1. 在读者/写者问题中，用R表示读者，W表示写者，下列每个序列从左到右表示进程到达的先后顺序，当采用读者优先方案时，序列（C）可能存在写者饥饿问题。 A. RRRW B. WRRR C. RWRR D. WRRW

哲学家就餐问题

问题描述

五位哲学家围桌而坐 哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。 每人必须获得左右两支筷子才能进餐。

1. 利用记录型信号量解决哲学家进餐问题

放在桌子上的筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组。 semaphore chopstick[5]; 所有信号量均被初始化为1。

死锁解决方法：

• 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。——限制并发执行的进程数。
• 仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。——采用信号量集。
• 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。——保证总会有一个哲学家能同时获得两只筷子而进餐。

方法1：增加一个信号量s，控制同时请求进餐人数， 初值为4.

第i 位哲学家的活动可描述为：

while(true){
   wait(s);
   wait(chopstick[ i ]);
   wait(chopstick[ ( i +1) %5] );
      ...
       eat;
      ...
   signal(chopstick[ i ]);
   signal(chopstick[ ( i +1) % 5] );
   signal(s);
   ...
   think;
}

方法2、利用AND信号量机制解决哲学家进餐问题

在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐。本质上是AND同步问题。

semaphore chopstick[5] ={1, 1, 1, 1, 1};
Process i()
  {   while(true){
         think;
         Swait(chopstick[ ( i +1) % 5] , chopstick[ i ] );
         eat;
         Ssignal(chopstick[ ( i +1) % 5] , chopstick[ i ] );     
     }
}

方法3:奇偶号区别对待

第i 位哲学家的活动可描述为：

while(true){
      if (i%2!=0) {
        wait(chopstick[ i ]);
        wait(chopstick[ ( i +1) % 5] );  }
      else {
        wait(chopstick[( i +1) % 5] ); 
        wait(chopstick[ i]);  }
        ...
        eat;
        ...
        signal(chopstick[ i ]);
        signal(chopstick[ ( i +1) % 5] );
        ...
        think;
      }
}

关于信号量的进一步说明 1. 记录型信号量可以用于两个进程，也可以用于多个进程，既可以用于互斥，也可以用于同步。当互斥与同步共存时，一般来说，用于互斥的信号量上的Wait操作总是在后执行。 2. 用于互斥，常称为互斥（或公用）信号量，其初值为1(临界资源)或n(非临界资源)。

3. 如果用于同步，多采用私用信号量，也称为资源信号量，其初值视资源数而定。它联系一组并发进程，只允许拥有它的进程对其实施Wait操作。 4. 作为资源信号量，当S>0时，其值表示可用资源的数量，执行一次Wait操作意味着请求分配一个单位的资源；若S<=0，表示已无资源，申请资源的进程被阻塞，并排入信号量S的等待队列中，执行一次Signal操作，意味着释放一个单位的资源。

Wait/Signal原语对信号量的操作可以分为三种情况

情况一

把信号量视为一个加锁标志位，实现对一个临界资源的互斥访问。 实现过程：

Wait(mutex);// mutex的初始值为1
临界区;
Signal(mutex);
非临界区；

情况二

把信号量视为是某种类型的共享资源的剩余个数，实现对一类（N个）共享资源的互斥访问。 实现过程：

Wait(R);// R的初始值为该资源的个数N 
访问该共享资源;
Signal(R);
其余部分；

情况三

把信号量作为进程间的同步工具 。 实现过程：

Wait(s1);
    程序段1；
Signal(s2);           

Wait(s2);
    程序段2；
Signal(s1);