Operating System (Process Synchronization)

Table of Contents

1 进程同步简介

简单地说,进程是执行中的程序。

这里主要讨论同步问题,进程同步和线程同步的基本原理相同,故将不特意区分进程和线程。

本文主要参考:操作系统概念(第六版)

1.1 进程基本状态——运行、就绪、阻塞

1962年,狄克斯特拉离开数学中心进入位于荷兰南部的Eindhoven Technical University任数学教授。在这里,他参加了X8计算机的开发,设计与实现了具有多道程序运行能力的操作系统——THE Multiprogramming System (后面简称THE)。狄克斯特拉在THE系统中所提出的一系列方法和技术奠定了计算机现代操作系统的基础,尤其是关于多层体系结构,顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。

为了在单处理机的情况下确定进程能否占有处理机,狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。
“运行”、“就绪”、“阻塞”三个状态的说明:
(1) 由于在任一时刻最多只有一个进程可以使用处理机,正占用着处理机的进程称为“运行”进程。
(2) 当某进程已具备了使用处理机的条件,而当前又没有处理机供其使用,则使该进程处于“就绪”状态。
(3) 当运行进程由于某种原因无法继续运行下去时,就停止其占用处理机,使之进入“阻塞”状态,待造成其退出运行的条件解除,再进入“就绪”状态。

1.2 进程同步两个基本问题——互斥和同步

广义的进程同步包含两个概念:“互斥”和“同步”:

  • 互斥是指某一资源同时只允许一个访问者对其进行访问,具有 唯一性和排它性 。但互斥无法限制访问者对资源的访问顺序,即访问是无序的。
  • 同步是指在互斥的基础上(大多数情况),通过其它机制实现访问者对资源的 有序访问 。比如,进程A产生数据,而进程B打印数据,显然进程B在打印之前必须等待,直到进程A已经产生一些数据。

2 竞争条件和临界区

两个或多个进程(线程)读写某些共享数据,最后的结果和进程(线程)运行的精确时序相关,这称为 竞争条件(race condition)

例如:两个线程对“同一个全局变量进行加一操作”,如果没有任何保护措施,则全局变量的最终结果取决于线程运行的精确时序,这就是竞争条件。

Table 1: 两线程对“同一个全局变量进行加一操作”的可能情况1
Thread 1 Thread 2 Integer value
    0
read value   0
increase value   0
write back   1
  read value 1
  increase value 1
  write back 2
Table 2: 两线程对“同一个全局变量进行加一操作”的可能情况2
Thread 1 Thread 2 Integer value
    0
read value   0
  read value 0
increase value   0
  increase value 0
write back   1
  write back 1

如何避免竞争条件呢?实际上凡是涉及共享内存、共享文件以及其它共享资源的情况下都可能出现类似的错误,要避免竞争条件,关键在于找到某种方法来阻止多个进程同时读写共享的数据。

为了用一种抽象的方式对避免竞争条件的问题进行描述,我们引入临界区域(critical region)或临界区(critical section)的概念。
对共享内存、共享文件以及其它共享资源进行访问的程序片断,多个进程(线程)同时执行这个程序片断会导致竞争条件的产生,这个程序片断就是临界区域(critical region)或临界区(critical section)。

要避免竞争条件,我们需要设计一种算法使得两个进程不可能同时处于临界区中,这称为 临界区问题

参考:操作系统概念(第六版),7.2节 临界区域问题

2.1 好解决方案的三个要求(互斥/有空让进/有限等待)

一个比较好的临界区问题的解决方案应该满足下面三个要求:
(1) 互斥 :临界区内最多只有一个进程在运行,这是最基本的要求。
(2) 有空让进 :如果没有进程处于临界区内且有进程希望进入临界区,则只有那些不处于剩余区(remainder section)的进程可以决定哪个进程获得进入临界区的权限。也就是 在临界区外运行的进程不得阻塞其他进程进入临界区。 这个要求也称为“前进”要求。
(3) 有限等待 :不得使进程无限期等待进入临界区。

在描述算法时,我们只定义用于同步目的的变量,只描述一种典型的进程,它具有图 1 所示的通用结构。

os_proc_sync_typical_process.png

Figure 1: 典型进程的通用结构

2.2 两进程临界区问题的解决办法(Peterson算法)

为简化问题,只考虑同一时间仅有两个进程的临界区问题解决办法。两个进程分别标记为 \(P_0\) 和 \(P_1\) ,为了方便,当一个进程用 \(P_i\) 表示时,另一个进程用 \(P_j\) 表示,即有 \(j = 1 - i\) 。

一种直观的解法(严格轮换法)是,让两个进程共享一个整数变量turn,初始值为0(或者1),用于记录“轮到”哪个进程进入临界区。进程0离开临界区时,它将turn的值设置为1,以便允许进程1进入临界区;进程1离开临界区时,它将turn的值设置为0,以便允许进程0进入临界区。如图 2 所示。

os_proc_sync_strict_alternation.jpg

Figure 2: 严格轮换法(注:while循环体是空语句)。a)进程P0,b)进程P1。

不过,严格轮换法仅满足“互斥”和“有限等待”要求,不满足“有空让进”的要求。比如,当进程0离开临界区后,无法立刻再进入临界区(除非进程1进入一次临界区后,把turn修改为0)。

1981年,G.L.Peterson发现了一种互斥算法可解决两进程的临界区问题,它同时满足“互斥”,“有空让进”,“有限等待”这三个要求,称为 Peterson算法 ,如图 3 所示。 在Peterson算法出现之前,T.Dekker已经提出了解决两进程临界区问题的算法,称为 Dekker算法 。不过由于Peterson算法非常简洁,使得Dedder算法不再有任何新意。

Peterson算法的思路是:进程共享两个变量:

boolean flag[2];   // 初始必须都为FALSE
int turn;          // 初始值无所谓,但两个进程初始值要不相同

为了进入临界区,进程 \(P_i \; (i=0,1)\) 首先设置flag[i]的值为TRUE,且设置turn的值为 \(j \; (j=1-i)\) ,从而表示如果另一个进程希望进入临界区,那么它能进入。如果两个进程同时试图进入,那么turn会几乎在同时设置成 \(i\) 和 \(j\) 。只有一个赋值语句的结果会被保持,另一个也会发生,但会立即被重写。最终的turn值决定了哪个进程能被允许先进入临界区。
当 \(P_i\) 退出临界区时,它会设置flag[i]为FALSE,以允许进程 \(P_j\) 进入临界区(进程 \(P_j\) 进入临界区前会先测试flag[i],当它为TRUE时 \(P_j\) 会一直等待)。

os_proc_sync_peterson.jpg

Figure 3: Peterson算法(注:while循环体是空语句)。a)进程P0,b)进程P1。

说明1: 采用Peterson算法时,当进程 \(P_0\) 进入了临界区,如果它停留在临界区的时间比较长,此时进程 \(P_1\) 也要进入临界区,则它会一直不停地测试while中的条件,这会浪费CPU资源。
说明2:图 3 所示算法中,子图a)中对turn的赋值并不一定要写为“turn=1”,只要它和下一行while中的测试“turn==1”一致就行。比如,在赋值时可以写为“turn=3”,测试时写为“turn==3”即可,当然这个值要和图b)中的不相同。在某些参考资料中,也可能见到如图 4 所示的Peterson算法,它也是正确的。

os_proc_sync_peterson_2.jpg

Figure 4: Peterson算法的其它形式

2.3 多进程临界区问题的解决办法(Lamport面包店算法)

前面介绍的Peterson算法可以解决两个进程的临界区问题。这里将介绍 Lamport面包店算法 它可解决多进程临界区问题。

Lamport面包店算法是一种用于面包店、冰淇淋店、熟食店、摩托车登记处等必须在混乱中找到顺序的场合中的调度算法。该算法为分布式环境而开发,但是这里只关心与集中式环境有关的算法特性。

Lamport面包店算法的思想: 在进入商店时,每个客户接收一个号码。具有最小号码的客户先得到服务。然而,面包店算法不能保证两个进程(客户)不会收到同样的号码。在出现相同号码时,具有最小名称的进程先得到服务。即如果 \(P_i\) 和 \(P_j\) 收到同样号码,且 \(i < j\) ,那么 \(P_i\) 先得到服务。 由于进程名称是唯一的,所以这个算法是完全确定的。

进程之间共享下面数据:

boolean choosing[n];  //表示进程是否正在抓号。初值为false。若进程Pi正在抓号,则choosing[i]=true
int number[n];        //记录进程获得的号码。初值为0。若number[i]=0,则表示进程Pi没有抓号

为了方便,用符号 “(a, b) < (c, d)” 表示 “a < c” 或者 “a == c && b < d” 。

采用Lamport面包店算法,进程 \(P_i\) 的结构如图 5 所示。

os_proc_sync_bakery_algorithm.jpg

Figure 5: Lamport面包店算法,进程Pi的结构

Lamport面包店算法的最多等待次数为 \(n-1\) 。

参考:操作系统概念(第六版),7.2

2.4 多进程临界区问题的解决办法(Eisenberg-Mcguire算法)

在Lamport发明面包店算法之前,Eisenberg和Mcguire提出过解决 \(n\) 个进程临界区问题的解决,称为 Eisenberg-Mcguire算法

和Lamport面包店算法一样,Eisenberg-Mcguire算法的最多等待次数也为 \(n-1\) 。这里不介绍它,可参考:操作系统概念(第六版),习题7.5

2.5 借助硬件的临界区问题解决办法

前面介绍的那些方法都是临界区问题的软件解决方案,我们还可以利用硬件提供的指令来更有效地解决临界区问题。

可以借助下面这些硬件指令解决临界区问题:
(1) 测试并设置(Test-and-Set);
(2) 获取并增加(Fetch-and-Increment);
(3) 交换(Swap);
(4) 比较并交换(Compare-and-Swap,CAS);
(5) 加载链接/条件存储(Load-Linked/Store-Conditional,LL/SC)。

参考:
操作系统概念(第六版),7.3 同步硬件
现代操作系统(原书第3版),2.3.3 忙等待的互斥

2.5.1 Test-and-Set

TestAndSet 指令的语义如下所示:

// TestAndSet指令的语义(这里仅是语义介绍,硬件保证它原子地执行)
boolean TestAndSet(boolean *lockPtr) {
    boolean oldValue;

    oldValue = *lockPtr;
    *lockPtr = true;

    return oldValue;
}

硬件保证TestAndSet原子地执行。因此,在多处理器环境中,如果两个指令TestAndSet同时执行在不同的CPU上,那么它们会按任意顺序来顺序地执行。

如果硬件支持指令TestAndSet,那么可以这样实现互斥:声明一个bool变量lock,初始化为false,进程 \(P_i\) 的结构如图 6 所示。

os_proc_sync_testandset_mutex.jpg

Figure 6: 使用TestAndSet实现互斥

不过,图 6 所示的实现并不满足“有限等待”的要求。

使用指令TestAndSet可以设计出满足临界区问题解决方案三个要求(互斥/有空让进/有限等待)的实现。进程之间共享下面数据:

boolean waiting[n];   //初始化为false
boolean lock;         //初始化为false

进程 \(P_i\) 的结构如图 7 所示。

os_proc_sync_testandset_satisfies_all_requirements.jpg

Figure 7: 使用TestAndSet解决临界区问题,进程Pi结构

关于图 7 所示算法为什么可以满足临界区问题解决方案三个要求可以参考:操作系统概念(第六版),7.3 同步硬件

3 信号量

信号量及对应的PV原语的概念是由荷兰科学家Dijkstra于1965年提出的。信号量常被用于保证对多个资源进行同步访问。

3.1 PV原语

信号量的值仅能由P操作和V操作来改变。P操作和V操作是不可中断的程序段,称为原语。在荷兰文中,“通过”叫Passeren,“释放”叫Vrijgeven,PV操作因此得名。后文将用wait表示P操作,signal表示V操作。

信号量(Semaphore)是一个资源计数器,(1) 当某进程获取某信号量时,信号量计数首先减1,如果计数小于0,那么该进程被阻塞(这个过程是wait操作);(2) 当某进程释放某信号量时,信号量计数首先加1,如果计数大于或等于0,那么唤醒某个阻塞的进程并执行之(这个过程是signal操作)。

显然,对于信号量,有:
(1) 如果信号量m大于0,表示还有m个资源可以访问,此时信号量进程等待队列中没有进程被阻塞,新的进程访问资源也不会被阻塞;
(2) 如果信号量m等与0,表示没有资源可以访问,此时信号量进程等待队列中没有进程被阻塞,但新的进程访问资源会被阻塞;
(3) 如果信号量m小于0,表示没有资源可以访问,此时信号量进程等待队列中有|m|个进程被阻塞,新的进程访问资源会被阻塞。

3.2 信号量及PV操作的简单实现及信号量应用

下面是信号量的简单语义实现。

typedef int semaphone;
semaphone S = N;                  // 信号量S初始化为可用资源的个数。如果用于互斥,则初始化为1

void wait(semaphone *ptrSem) {    // 即P操作,要实现为原子地,这里仅是介绍其语义
    while ((*ptrSem) <= 0) {
        ;                         // 忙等待,浪费CPU资源,后文将介绍更高级的实现
    }
    (*ptrSem)--;
}

void signal(semaphone *ptrSem) {  // 即V操作,要实现为原子地,这里仅是介绍其语义
    (*ptrSem)++;
}

可以用信号量解决 \(n\) 个进程的临界区问题,这 \(n\) 个进程共享一个信号量mutex,并初始化为1。每个进程的组织结构为:

do {
    wait(&mutex);
    // critical section
    signal(&mutex);
    // remainder section
} while (1);

还可以使用信号量解决其它进程同步问题。假如,考虑有两个并发进程:进程 \(P_1\) 有语句S1,而进程 \(P_2\) 有语句S2,假设 要求只有在S1执行后之后才执行S2。 利用信号量很容易地实现这一要求。办法如下:让进程 \(P_1\) 和 \(P_2\) 共享一个共同的信号量synch,且初始化为0。在进程 \(P_1\) 的语句S1后插入语句“signal(&synch);”,而有进程 \(P_2\) 的语句S2前插入语句“wait(&synch);”。即:

// P1
    S1;
    signal(&synch);
    // others

// P2:
    wait(&synch);
    S2
    // others

由于synch初始化为0,所以只有当进程 \(P_1\) 调用signal(&synch);(即执行S1后),才会执行S2。

3.3 信号量及PV操作的高级实现

前面介绍的信号量简单实现的主要缺点是“忙等待”。如,当一个进程位于其临界区内时,任何其他试图进入临界区的进程都会连续地执行空循环(即wait实现中的while语句)。如果进程待在临界区的时间比较长,这会大大浪费CPU资源。

为了克服“忙等待”导致浪费CPU资源,可修改信号量操作wait(P操作)和signal(V操作)的定义。当一个进程执行wait操作时,发现信号量不为正,则它必须等待。然而,该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放入到与信号量相关的等待队列中,且该进程的状态被切换成阻塞状态。接着,控制被转到CPU调试程序,以选择另一个进程来执行。
一个进程阻塞且等待信号量S,可以在其他进程执行signal操作之后被重新执行。该进程的重新执行是通过wakeup操作来进行的,该操作会让进程回到就绪状态。

为了实现这样定义的信号量,可以将信号量定义为:

typedef struct {
    int value;
    struct process *L;
} semaphore;

每个信号量都有一个整数值和一个进程链表,当一个进程必须等待信号量时,就加入到进程链表上。操作signal会从等待进程链表中取一个进程以唤醒。
信号量操作wait和signal可按如下来定义:

void wait(semaphore *ptrSem) {     // 即P操作,要实现为原子地,这里仅是介绍其语义
    ptrSem->value--;
    if (ptrSem->value < 0) {
        add this process to ptrSem->L;
        block();                    // 使当前进程进入阻塞状态,不会浪费CPU资源
    }
}

void signal(semaphore *ptrSem) {    // 即V操作,要实现为原子地,这里仅是介绍其语义
    ptrSem->value++;
    if (ptrSem->value <= 0) {
        remove a process P from ptrSem->L;
        wakeup(P);                  // 使进程P回到就绪状态
    }
}

4 进程同步经典问题

4.1 有限缓冲区问题(生产者——消费者问题)

假设缓冲区大小固定。如果缓冲区为空,那么消费者必须等待;如果缓冲区为满,那么生产者必须等待。

假定缓冲池有n个缓冲项,每个缓冲项能存一个数据项。
信号量mutex提供了对缓冲池访问的互斥要求,并初始化为1。
信号量empty和full分别用来表示空缓冲项和满缓冲项的数量。信号量empty初始化为n;而信号量full初始化为0。

生产者进程和消费者进程的代码如图 8 所示。可以这样来理解代码: 生产者为消费者生产满缓冲项,消费者为生产者生产空缓冲项。

os_proc_sync_producer_consumer.jpg

Figure 8: 用信号量解决生产者——消费者问题

前面讨论的是单生产者和单消费者的情况,如果生产者有多个或消费者有多个,或缓冲区有多个,怎么解决呢?可参考,《UNIX网络编程第2卷:进程间通信(第2版)》第10章。

4.2 读者——写者问题

Readers-Writers problems 是指:一个数据对象(如文件)可以为多个并发进程所共享,有的进程(称为读者)只需要读取共享对象内容,而有的进程(称为写者)需要更新共享对象。如何协调读者和写者?使得多个读者可以同时读文件,但写者在写文件时不允许有读者在读文件,同样读者在读文件时写者也不去能写文件。

4.2.1 第一类读者——写者问题(读者优先,写者可能饥饿)

第一类读者——写者问题是指:读者优先,当无读者时,才允许写者操作(如果读者不断,则写者可能饥饿。)

第一类读者——写者问题可以用下面方式解决。让进程共享以下数据:

semaphore wrt = 1;      // 用于写者互斥,且为第一个进入临界区和最后一个离开临界区的读者所使用。初始化为1。
int readcount = 0;      // 记录有多少个进程正在读对象。初始化为0。
semaphore mutex = 1;    // 用于实现对readcount的互斥访问。初始化为1。

写者进程结构如下:

// 下面是使用信号量解决第一类读者——写者问题时的写者进程结构
do {

  wait(&wrt);

  // 临界区,这里可以安全地进行写操作

  signal(&wrt);

  // 非临界区

} while (1);

读者进程结构如下:

// 下面是使用信号量解决第一类读者——写者问题时的读者进程结构
do {

  wait(&mutex);          // mutex用于实现对readcount的互斥访问
  readcount++;
  if (readcount == 1) {  // 如果这是第一个读者
    wait(&wrt);          // 阻止写进程写
  }
  signal(&mutex);

  // 临界区,这里可以安全地进行读操作

  wait(&mutex);
  readcount--;
  if (readcount == 0) {  // 如果这是最后一个读者
    signal(&wrt);        // 允许写进程写
  }
  signal(&mutex);

  // 非临界区

} while (1);

4.2.2 第二类读者——写者问题(写者优先,读者可能饥饿)

第二类读者——写者问题是指:一旦一个写者到来,它应该尽快对文件进行写操作,而新来到的读者不允许进行读操作(如果写者不断,则读者可能饥饿)。

9 中子图(b)解决了第二类读者——写者问题。为方便比较,子图(a)演示了前面介绍的第一类读者——写者问题的解决方案。图片摘自论文:Courtois, P. J.; Heymans, F.; Parnas, D. L. (1971). "Concurrent Control with Readers and Writers" (其详细说明可参考该论文)。

os_proc_sync_reader_writer.jpg

Figure 9: (a) 读者优先;(b) 写者优先

4.2.3 第三类读者——写者问题(读者写者都不会饥饿)

第三类读者——写者问题是保证读者写者都不会饥饿。这里不介绍。


Author: cig01

Created: <2013-01-05 Sat 00:00>

Last updated: <2017-12-15 Fri 09:28>

Creator: Emacs 25.3.1 (Org mode 9.1.4)