Lec6: 进程同步

race condition#

​ 像上面这种多个进程并发访问和操作统一数据并且执行结果和特定访问顺序有关，称为 race condition（竞争条件）。为了防止竞争条件，需要确保一次只有一个进程可以操作变量 counter。为了做出这种保证，要求进程按照一定的方式来同步。

​ 实际上，想产生 race condition，有以下条件：

1. 多个进程
2. 进程之间共享内存
3. 至少有一个进程有写操作

test_and_set#

​ 这个原子操作的定义如下：

1
 boolean TestAndSet (boolean *target)
2
  {
3
       boolean rv = *target;
4
       *target = TRUE;
5
       return rv:
6
  }

​ 用它来实现的锁代码如下所示：

1
while (true) {
2
  while ( TestAndSet (&lock ));   // do nothing
3

4
  //    critical section
5

6
  lock = FALSE;
7

8
   //      remainder section
9

10
}

Swap#

​ 定义：

1
void Swap (boolean *a, boolean *b)
2
  {
3
    boolean temp = *a;
4
    *a = *b;
5
    *b = temp:
6
  }

​ 实现：

1
while (true)  {
2
  key = TRUE;
3
  while ( key == TRUE)
4
    Swap (&lock, &key );
5

6
    //  critical section
7

8
    lock = FALSE;
9

10
    //  remainder section
11

12
}

Compare_and_swap#

​ 定义：

1
int compare_and_swap(int *value, int expected, int new_value)
2
{
3
  int temp = *value;
4
  if (*value == expected)
5
  *value = new_value;
6
  return temp;
7
}

​ 实现：

1
while (true){
2
  while (compare_and_swap(&lock, 0, 1) != 0)
3
  ; /* do nothing */
4
  /* critical section */
5
  lock = 0;
6
  /* remainder section */
7
}

Bounded-waiting with compare-and-swap#

1
while (true) {
2
  waiting[i] = true;
3
  key = 1;
4
  while (waiting[i] && key == 1)
5
    key = compare_and_swap(&lock,0,1);
6
  waiting[i] = false;
7
  /* critical section */
8
  j = (i + 1) % n;
9
  while ((j != i) && !waiting[j])
10
    j = (j + 1) % n;
11
  if (j == i)
12
    lock = 0;
13
  else
14
    waiting[j] = false;
15
  /* remainder section */
16
}

Usage as General Synchronization Tool#

​ 操作系统通常区分计数信号量（Counting semaphore ）和二进制信号量（Binary semaphore）

• Counting semaphore – integer value can range over an unrestricted domain
• 计数信号量通常用于控制访问具有多个实例的某种资源。信号量的值就是可用资源数量。
• Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement
  • Also known as mutex locks
  • 事实上，可以使用二进制信号量来实现互斥。
• Can implement a counting semaphore S as a binary semaphore
• Provides mutual exclusion

1
Semaphore S;  // initialized to 1
2
wait (S);
3
  // Critical Section
4
signal(S);

​ 注意，上面的例子中，Semaphore S 被设置成了1，用于表示可以进临界区的名额。

​ 下面是使用 Semaphore 的一个例子：

​ 上面的操作实现了两个任务的先后执行。

​ 实际上，上面这个例子还提示了我们，信号量的初值是非常重要的。

Semaphore Implementation#

​ 想要实现 Semaphore，最简单的方法就是使用 busy waiting。

​ 为了解决busy waiting，我们需要操作系统给我们实现两种操作：sleep(block)、wakeup，具体的思想是，当一个进程执行操作wait()并且发现信号量的值部位正的时候，他必须等待。然而，该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放到和信号量相关的等待队列中，并且将这个进程状态切换成等待状态。

• With each semaphore there is an associated waiting queue. Each semaphore has two data items:
  • value (of type integer)
  • pointer to a linked-list of PCBs.
• Two operations (provided as basic system calls):
  • block (sleep) – place the process invoking the operation on the appropriate waiting queue.
  • wakeup – remove one of processes in the waiting queue and place it in the ready queue.

​ 代码如下：

​ 一般来说，默认semaphore是使用这种方式实现的。

Deadlock and Starvation#

​ 死锁和饥饿是两个经典的问题。

• Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

​ 上面是死锁的一个例子。具体来说，假设Po执行wait(S)，接着P执行wait(Q)。当Po执行wait(Q)时，它必须等待，直到P执行signal(Q)。类似地，当P执行wait(S)时，它必须等待，直到Po执行signal(S)。由于这两个操作signal()都不能执行，这样P。和 P就死锁了。

​ 另一种问题是无限阻塞（indefinite blocking）或饥饿（starvation），即进程无限等待信号量。如果对与信号量相关的链表按照LIFO（后进先出）顺序来增加和删除进程，那么可能发生无限阻塞。

Bounded-Buffer Problem#

​ 这个问题也叫做“生产者-消费者问题”，具体定义如下：

多个生产者和多个消费者共享一个固定大小的缓冲区，必须保证互斥访问，并且不能溢出或取空。

​ 可以使用以下方案来解决：

• N buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0, counting full items
• Semaphore empty initialized to the value N, counting empty items.

​ 代码如下所示：

​ 可以这样理解：

• 生产者检测缓冲区是否是空的，是空的话就进行生产，直到缓冲区满。
• 而消费者检测缓冲区是否满，是满的话就进行消费，直到缓冲区空。
• 为了保证没有生产者和消费者同时运行，需要一个互斥锁mutex。

Readers-Writers Problem#

• A data set is shared among a number of concurrent processes
  • Readers – only read the data set; they do not perform any updates
  • Writers – can both read and write.
• Problem – allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time.
• Shared Data
  • Data set
  • Semaphore mutex initialized to 1, to ensure mutual exclusion when readcount is updated.
  • Semaphore wrt initialized to 1.
  • Integer readcount initialized to 0.

​ 具体来说，就是分为两种成员：reader 和 writer。其中，reader 只能读，但 writer 可读可写。

​ 对于这个问题的解答，可以定义以下数据结构进行同步：

1
semaphore rw_mutex = 1;
2
semaphore mutex = 1;
3
int read_count = 0;

​ 两个进程的代码如下所示：

​ 对于 reader 进程，因为 reader 不仅要和 writer 互斥，reader 之间也需要互斥，所以可以看到代码中为read_count变量添加了互斥锁mutex。

Dining-Philosophers Problem（哲学家就餐问题）#

​ 假设有5个哲学家，他们的生活只是思考和吃饭。这些哲学家共用一个圆桌，每位都有一把椅子。在桌子中央有一碗米饭，在桌子上放着5根筷子。当一位哲学家思考时，他与其他同事不交流。时而，他会感到饥饿，并试图拿起与他相近的两根筷子（筷子在他和他的左或右邻居之间）。一个哲学家一次只能拿起一根筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时拥有两根筷子时，他就能吃。在吃完后，他会放下两根筷子，并开始思考。 ​ 哲学家就餐问题（dining-philosophers problem）是一个经典的同步问题，因为它是大量并发控制问题的一个例子。这个代表型的例子满足：在多个进程之间分配多个资源，而且不会出现死锁和饥饿。

• Shared data
  • Bowl of rice (data set)
  • Semaphore chopstick [5] initialized to 1
• 对于哲学家就餐问题，有两个共享数据：
  • 饭，就是数据集合
  • 5 支筷子，就是锁

​ 一种简单的解决方法是每只筷子都用一个信号量表示，哲学家可以通过wait()获得筷子，也可以通过signal()释放相应的筷子，也就是：

1
  semaphore chopsticks[5]

​ 对应算法如下：

​ 这里我们假定一下事实：

1. 对于编号为i（i=0～4）的哲学家，其左边的筷子编号为i，右边的筷子编号为（(i+1)%5）
2. 哲学家只有拿到两双筷子才可以吃饭

​ 考虑这样的一种情况：所有哲学家同时拿起左边的筷子，此时，5支筷子全部上锁，因此没有哲学家可以拿起右手的筷子，导致死锁。

​ 死锁问题有多种解决措施：

1. 允许最多4个哲学家同时坐在桌子上，避免所有筷子同时消失的情况

   Semaphore semaphore = 4

   

2. 只有一个哲学家的两根筷子都可以使用的时候，他才可以拿起它们（必须在临界区内拿起两根筷子）

   

3. 使用非对称的解决方案：单数的哲学家先拿左边的筷子，双数的哲学家先拿右边的筷子

   

​ 但是，没有死锁的解决方案不一定能消除饥饿。

Monitor#

不讲

Pthreads Synchronization#

• Pthreads API is OS-independent
• It provides:
  • mutex locks
  • condition variables
• Non-portable extensions include:
  • read-write locks
  • spin locks

​ 以下是 Pthreads 的几个常见的函数：

1. pthread_mutex_init(&mutex, NULL)：初始化函数
2. pthread_mutex_lock(&mutex)：上锁函数
3. pthread_mutex_unlock(&mutex)：解锁函数

​ 对于上面的这些函数，在操作正确的时候，返回的值是 0。