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

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

@[toc]

2.4 进程同步

2.4.1 进程同步的基本概念

1、两种制约关系

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

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

2、临界资源

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

  • 有一群生产者进程生产产品供给消费者进程消费；
  • 为使两者并发执行，在两者之间设置具有 n 个缓冲区的缓冲池；
  • 生产者每生产一个产品就放入一个缓冲区中；
  • 消费者从缓冲区中取产品消费；
  • 生产者进程和消费者进程都以异步方式运行；
  • 但它们在某些点上必须保持同步。
    在这里插入图片描述
1
2
3
4
输入指针加1表示为 in:=(in+1)mod n
输出指针加1表示为out:=(out+1)mod n
当out=in时表示缓冲池空
(in+1)mod n=out时表示缓冲池满。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//生产者进程和消费者进程共享的变量：
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 时，表示锁已打开。

则开锁、关锁原语如下：

1
2
3
4
5
6
7
//关锁：
Lock(W):
   while(W==1);
   W=1;
//开锁：
unLock(W):
   W=0;

3、临界区

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

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

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

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

练习题

一、选择题
1. 下列关于临界区和临界资源说法正确的有(C)。
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. 下列哪一种场景问题只包含进程互斥问题？(C)。
A.两个进程通过一个缓冲区传递数据
B.田径场的四百米接力比赛
==C.一个进程读文件，一个进程写文件==
D.公共汽车上司机和售票员的工作配合

8. 多个进程并发执行时，各个进程应互斥进入其临界区，所谓临界区是指(C)。
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
2
3
4
//加1操作                             //减1操作
load R1,x  /*取x到寄存器R1中.*/       load R2, x
inc R1								 dec R2
store x,R1 /*将R1的内容存入x*/        store x, R2

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

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

2. 对下列程序段：

1
2
3
4
5
6
7
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)Ⅰ 和 Ⅱ
(C)Ⅱ 和 Ⅲ
==(D)Ⅰ、Ⅱ 和 Ⅲ==

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

1
2
3
4
5
6
7
8
9
10
11
12
//进程P1
int x=0;
thread1()
{
    int a;
    a=1;x+=1;
}
thread2()
{
    int a;
    a=2;x+=2;
}
1
2
3
4
5
6
7
8
9
10
11
12
//进程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；
1
2
3
4
5
6
7
8
9
10
11
//进程一
while (turn != i);
  critical section
turn = j;
  remainder section

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

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

算法 2

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

  • 先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程的临界区标志为 true；
  • 在退出区修改本进程的临界区标志为 false；
1
2
3
4
5
6
7
8
9
10
11
12
13
//进程一
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 的区别在于先修改后检查。可防止两个进程同时进入临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
//进程一
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 用于进程间的互相谦让。

1
2
3
4
5
6
7
8
9
10
11
12
13
//进程一
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 伪代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.以下是解决进程互斥进入临界区的一种解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.关中断
过程:

1
2
3
4
关中断;
    临界区;
开中断;
其余部分;

特点：
简单、高效！

存在问题:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
设Lock为全局布尔变量,初值为false;
TS指令定义(逻辑):
Boolean TS(boolean  *lock) {
   boolean old=*lock;
   *lock=true;
   return old;
}
使用TS实现互斥:
Do {
     While (TS(&Lock));
      临界区;
     lock=false;
      剩余区
   }

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

(2)对换(Swap)指令

1
2
3
4
5
6
7
Swap指令定义：
void Swap(boolean *a, boolean *b)
{
boolean temp=*a;
*a = *b;
*b=temp ;
}

3.利用 Swap 实现进程互斥

  • 每个临界资源设置一个公共布尔变量 lock，初值为 FALSE。每个进程设置一个私有布尔变量 key
  • 进程要使用临界资源时将会首先将自己的 key 置为 true
1
2
3
4
5
6
key = TRUE;
do{
   swap(&lock,&key);
}while(key);
   临界区
lock=FALSE;

练习题

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

1
2
3
4
5
6
7
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.整型信号量

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

1
2
3
4
5
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)之间即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 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 的指针。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 型信号量

1
2
3
4
5
6
7
8
9
10
11
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. 信号量集

1
2
3
4
5
6
7
8
9
10
11
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。

1
2
3
4
5
6
7
8
9
10
//进程一
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）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//供者进程
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
2
3
4
5
6
7
8
9
10
11
12
生产者：
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
2
3
4
5
6
7
8
9
10
11
12
生产者：
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
2
3
4
5
6
7
8
9
10
11
12
生产者：
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
2
3
4
5
6
7
8
9
10
11
12
生产者：
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;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void reader(void)
{
    while (1) {
    ……
    Wait (w);
      读操作
    Signal(w);
    ……
    }
}

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

常规解法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
读者：
……
	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，用于写者与其他进程的互斥操作！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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，用于在写者进程到达后封锁后续的读者进程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 个进程可同时进行读操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 位哲学家的活动可描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
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 同步问题。

1
2
3
4
5
6
7
8
9
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 位哲学家的活动可描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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(非临界资源)。

  • 对于两个并发进程竞争临界资源，S 只有 1、0、-1 三个取值:

      s=1：无进程进入临界区；
  s=0：有一个进程进入临界区；
  s=-1: 有一个进程在临界区，另一个进程等待进入临界区。

  • 对于 n 个并发进程竞争临界资源，信号量 S 可取值的范围是：
    1 ～ -(n-1)，当 S<0 时，表示有一个进程已进入临界区，而且还有|Ｓ|个进程正在等待进入临界区，它们处于等待队列中。

  • 对于互斥信号量，每一进程均可对其进行 Wait、Signal 操作。

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

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

情况一

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

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

情况二

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

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

情况三

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

1
2
3
4
5
6
7
Wait(s1);
    程序段1；
Signal(s2);

Wait(s2);
    程序段2；
Signal(s1);
操作系统
『操作系统』 进程的描述与控制 Part2 进程同步
https://chiamzhang.github.io/2024/06/29/『操作系统』 进程的描述与控制 Part2 进程同步/
Author
Chiam
Posted on
June 29, 2024
Licensed under