4.5 同步和P-V操作

4.5.1 同步和互斥的概念

进程的互斥关系

例子

进程的互斥关系

• 多个进程由于共享了独占性资源，必须协调个进程对资源的存取顺序：确保没有两个或以上的进程同时进行存取操作。

• 互斥和资源共享相关

• 资源：临界资源

• 存取操作区域：临界区

进程的同步关系

若干合作进程为了完成一个共同的任务，需要相互协调运行步伐，一个进程开始某个操作之前必须要求另一个进程已经完成某个操作，否则前面的进程只能等待。

进程同步的例子：司机和售票员

司机和售票员之间的操作属于同步关系

• 司机：起步、行驶、停车
• 售票员：关门、售票、开门

同步关系

• 司机起步前售票员先关门，否则等待
• 售票员开门前司机先停车，否则等待

进程同步关系——另一种解释

合作进程中某个操作之间需要满足某种先后关系或某个操作能否进行需要满足某个前提条件，否则只能等待。

互斥关系属于特殊的同步关系

4.5.2 P-V操作概念

信号灯的概念

信号灯时一种卓有成效的进程同步机制

1965年荷兰学者Dijkstra提出

信号灯用于进程同步的基本思想

进程在运行过程中受信号灯状态控制，并能改变信号灯状态

• 进程受控制：信号灯的状态可以阻塞或唤醒进程
• 改变信号灯：信号灯的状态可以被进程改变

信号灯机制

数据结构

• 信号灯变量定义为一个二元矢量\((S,q)\)
• S：整数，处置非负（S又称信号量）
• q：PCB队列，初值为空集

struct SEMAPHORE {
  int S; 	//整数，初值非负
  pointer_PCB q;	//队列：进程PCB指针，初值空集
}

信号灯的操作

两个操作

• P操作（函数或过程，P(S,q)）
• V操作（函数或过程，V(S,q)）

P，V是荷兰语

• Passeren通过
• Vrijgeveb释放

P操作的原理（P(S,q)、P(S)）

提示：P操作可能使得进程在调用处阻塞

提示2：S初值很重要

• S的值减1
• 若差大于或等于零，则进程继续
• 若差小于零，则该进程阻塞并加入到队列q中，并转调度函数

P(S, q) {
  S = S - 1;
  if (S < 0) {
    Insert(Caller, q);
    Block(Caller);
    转调度函数();
  }
}

V操作的原理（V(S,q)、V(S)）

提示：V操作可能会唤醒一个阻塞的进程

• S值加1
• 若和大于零，则该进程继续
• 若和小于或等于零，则该进程继续同时从q中唤醒一个进程

V(S, q) {
  S = S + 1;
  if (S < 0) {
    Remove(q, pid);
    Wakeup(pid);
  }
}

4.5.3 P-V操作解决互斥问题

实质是实现对临界区的互斥访问

允许最多一个进程处于临界区

应用过程

• 进入临界区之前先执行P操作；（可能阻塞当前线程）
• 离开临界区之后再执行V操作；（可能唤醒某个进程）

S的初值要设置合理

例子：3个进程Pa、Pb、Pc。CSa、CSb、CSc是临界区

Pa() {
  P(mutex);
  CSa
  V(mutex);
}
Pb() {
  P(mutex);
  Csb
  V(mutex);
}
Pc() {
  P(mutex);
  CSc
  V(mutex);
}

main() {
  // 信号量mutex
  int mutex = 1;
  cobegin	// 并发
  Pa();
  Pb();
  Pc();
  coend	// 并发结束
}

4.5.4 P-V操作解决互斥问题

同步问题实质

• 当运行条件不满足时，能让进程暂停

• 运行条件满足时，能让进程立即继续

P-V操作应用于进程同步的基本思路

• 暂停当前进程：在关键操作之前执行P操作
  • 必要时可暂停
• 继续进程：在关键操作之后执行V操作
  • 必要时唤醒合作进程
• 定义有意义的信号量S，并设置合适的初值
  • 信号量S能明确地表示“运行条件”

实现同步的例子：司机和售票员

司机：

• 起步
• 行驶
• 停车

售票员

• 关门
• 售票
• 开门

关键操作

1. 一个操作的运行需要条件
2. 一个操作的完成与否影响到另外一个操作能否运行

同步要求

• 只有售票员关门后，司机才能起步
• 只有在自己停车后，售票员才能关门

// 门是否关好？0:没有，1:关好
int S1 = 0;
// 车是否停稳？0：没有，1:停稳
int S2 = 0;

// 司机进程
while (true) {
  P(S1);
  qibu();
  xingshi();
  tingche();
  V(S2);
}

// 售票员进程
while (true) {
  guanmen();
  V(S1);
  shoupiao();
  P(S2);
  kaimen();
}

4.5.5 经典同步问题

经典同步问题1：生产者消费者问题

一群生产者（Producer）向一群消费者（Consumer）提供产品（数据），共享缓冲区

规则

1. 不能向满缓冲区存产品
2. 不能从空缓冲区取产品
3. 每个时刻仅允许1个生产者或消费者存或取1个产品（互斥）

int empty = 5; // 信号量：缓冲区中空位的个数，初值5
int full = 0;	// 信号量：缓冲区数据的个数，初值0
int mutex = 1;	// 信号量：缓冲区互斥使用，初值1，可用

producer_i() {
  while (TRUE) {
    生产一个数据;
    P(empty);		// empty--
    P(mutex);
    存1个数据到缓冲区;
    V(mutex);
    V(full);		// full++
  }
}

consumer_j() {
  while (TRUE) {
    P(full);	// full--
    P(mutex);
    从缓冲区取1个数据;
    消费/处理数据;
    V(mutex);
    V(empty);	// empty++
  }
}

4.5.6 读者和编者同步问题

问题描述：

有一本书

• 有读者读书；有多个读者
• 有编者编书；有多个编者

要求

• 允许多个读者同时读
• 不允许读者、编者同时操作
• 不允许多个编者同时操作

/*
	如何实现：
	编者之间的互斥
	编者和读者之间的互斥
	读者之间不互斥
*/
int editor = 1;	// 互斥量：编者对编者和读者的互斥
int ReadCount = 0;	// 读者计数
int mutex = 1;		// 互斥量：ReadCount时临界资源

Reader_i() {
  while (true) {
    P(mutex);
    ReadCount++;
    if (ReadCount == 1)
    	P(editor);
    V(mutex);
    读书；
    P(mutex);
    ReadCount--;
    if (ReaderCount == 0)
    	V(editor);
    V(mutex);
  }
}

Editor_i() {
  while (true) {
    P(editor);
    编书;
    V(editor);
  }
}

小结

信号灯机制P-V操作解决同步问题

• 区分关键操作或运行条件或影响
• 关键操作之前P操作
• 关键操作之后V操作

生产者—消费者问题

• 同步和互斥混合

读者—写者问题

• 互斥问题