第三章--同步与互斥

我们一日日度过的所谓的日常，实际上可能是接连不断的奇迹。

同步与互斥

进程同步

异步性：进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的，不可预知的速度向前推进。

如何解决异步性，就是进程同步讨论的内容。

同步，亦称直接制约关系，它是指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是原语它们之间的相互合作。

进程互斥

临界资源：一个时间段内只允许一个进程使用的资源。

对于临界资源的访问，必须要互斥的访问。

互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源。

对于临界资源的互斥访问，可以在逻辑上分为如下四个部分：

1
2
3
4
5
6
do {
    entry section;       //进入区
    critical section;    //临界区
    exit section;        //退出区
    remainder section;   //剩余区
} while(true)
  • 进入区：检查是否可以进入临界区。若可进入，则设置正在访问临界资源的标志(上锁)，以阻止其他进程同时进入临界区。
  • 临界区：真正访问临界资源的代码。
  • 退出区：负责解除正在访问临界资源的标志。(解锁)
  • 剩余区：做其他处理。

进程互斥设计原则：

  • 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
  • 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
  • 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区。
  • 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

p0进程：

1
2
3
4
while (turn != 0);  // ①
critical section;   // ②
turn = 1;           // ③
remainder section;  // ④

p1进程：

1
2
3
4
while (turn != 1);  // ⑤ 进入区
critical section;   // ⑥ 临界区
turn = 0;           // ⑦ 退出区
remainder section;  // ⑧ 剩余区

这是什么sb算法。。。

缺陷：

  • 违背空闲让进的原则：当p0打印一次后，将标志位记为1。而如果1不需要执行打印任务，而p0需要再次打印时，p0会被阻塞。

双标志先检查法

算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 flag[0] = true意味着0号进程现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i]设置为 true，之和开始访问临界区。

p0进程：

1
2
3
4
5
while (flag[1]);    // ①
flag[0] = true;     // ②
critical section;   // ③
flag[0] = false;    // ④
remainder section;

p1进程：

1
2
3
4
5
while (flag[0]);    // ⑤ 如果此时 P0 想进入临界区，P1 就一直循环等待
flag[1] = true;     // ⑥标记为 P1 进程想要进入临界区
critical section;   // ⑦ 访问临界区
flag[1] = false;    // ⑧ 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

核心思想：在自己使用前， 检查是否有别人在用。

缺陷：

  • 违反了忙则等待的原则：按照①⑤②⑥③⑦的顺序执行，p0和p1会同时进入临界区。

原因：进入区的检查和上锁两个处理不是一气呵成的。检查后，上锁前可能发生进程切换。

双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先检查后上锁，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此人们又想到先上锁后检查的方法，来避免上述问题。

p0进程：

1
2
3
4
5
flag[0] = true;     // ①
while (flag[1]);    // ②
critical section;   // ③
flag[0] = false;    // ④
remainder section;

p1进程：

1
2
3
4
5
flag[1] = true;     // ⑤ 标记为 P1 进程想要进入临界区
while (flag[0]);    // ⑥ 如果 P0 也想进入临界区，则 P1 循环等待
critical section;   // ⑦ 访问临界区
flag[1] = false;    // ⑧ 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

可能发生死锁

缺陷：

  • 违背了空闲让进和有限等待的原则：若按照①⑤②⑥…的顺序执行，会发生死锁。各个进程都无法访问临界资源。

Peterson算法

算法思想：结合双标志法、单标志法的思想，如果双方都争着想进入临界区，那可以让进程尝试”孔融让梨”(谦让)。做一个有礼貌的进程。

p0进程：

1
2
3
4
5
6
flag[0] = true;                 // ① 主动争取
turn = 1;                       // ② 主动谦让
while (flag[1] && turn == 1);   // ③ 检查对方是否也想用，且最后一次是不是自己说了客气话
critical section;               // ④
flag[0] = false;                // ⑤
remainder section;

p1进程：

1
2
3
4
5
6
flag[1] = true;                 // ⑥ 表示自己想进入临界区
turn = 0;                       // ⑦ 可以优先让对方进入临界区
while (flag[0] && turn == 0);   // ⑧ 对方想进，且最后一次是自己"让梨"，那自己就循环等待
critical section;               // ⑨ 
flag[1] = false;                // ⑩ 访问完临界区，表示自己不想访问临界区了
remainder section;

Peterson算法用软件方法实现了解决进程互斥的问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

Bakery算法

Bakery算法适用于n >= 2 个进程之间的同步。

算法思想：再进程进入临界区之前，必须先领取一个号码牌(ticket)

  • 排队原则：拥有最小号码的进程被允许进入临界区
  • 发号机制：编程方案总是生成非递减的号码牌。
  • 冲突解决：如果两个进程P_i和P_j获得了相同的号码牌，则通过比较它们的进程ID号来打破僵局，进程ID号较小的进程优先。

共享数据结构：

  1. boolean choosing[n]：一个布尔数组
    • choosing[i] = true 表示进程P_i开始或希望申请一个票号。
    • 初始时所有元素初始化为false
  2. int number[n]：一个整数数组
    • number[i]是进程P_i获得的票号。number[i] > 0表示P_i需要进入临界区
    • 初始时所有的元素都初始化为0

执行逻辑：

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
Process P[i]:   // i 表示进程编号

while (true) {
  
    choosing[i] = true;		//申请取号
    number[i] = 1 + max(number[0..N-1]);   // 取一个比当前最大票号大的号码
    choosing[i] = false;	//区号完成

    // 等待条件：其他进程取号完成，并且它们的票号优先级不比自己高
    for j in 0..N-1, j != i {
        while (choosing[j]) { /* 等待进程 j 取号完成 */ }
        while (number[j] != 0 
               && (number[j], j) < (number[i], i)) {
            /* 等待进程 j 先进入临界区 */
        }
    }

    // ---- Critical Section ----
    // 在这里执行需要互斥的操作
    do_critical_work();

    // ---- Exit Section ----
    number[i] = 0;   // 释放票号，表示退出临界区

    // ---- Remainder Section ----
    do_noncritical_work();
}

进程互斥的硬件实现方法

中断屏蔽方法

实现原理：利用”开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就是不发生进程切换，因此不可能发生两个同时访问临界区的情况)。

1
2
3
4
5
...
关中断
临界区
开中断
...

优点：简单高效

缺点：

  • 不适用于多处理机
  • 只适用于操作系统内核进程，不适用于用户进程。(特权指令)

TestAndSet指令

实现原理：

  • 为每个临界资源设置一个布尔变量 lock，其初值为 false。
  • CPU提供专门的硬件指令 TestAndSet，允许对一个字(lock)的内容进行原子操作的检测和修正。
  • TestAndSet函数的作业是测试布尔变量 lock的值，返回 lock原来的值，然后立即将其设置为 true。

TestAndSet等效C代码：

1
2
3
4
5
6
7
8
// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true 表示已加锁, false 表示未加锁
bool TestAndSet (bool *lock){
    bool old;
    old = *lock;    // old用来存放lock原来的值
    *lock = true;   // 无论之前是否已加锁，都将lock设为true
    return old;     // 返回lock原来的值
}

实际上以上逻辑是由硬件完成的，因此可以一瞬间完成，不用担心两个进程同时返回false。

使用TestAndSet：

1
2
3
4
5
// 以下是使用 TSL 指令实现互斥的算法逻辑
while (TestAndSet (&lock)); // "上锁" 并 "检查"
临界区代码段...
lock = false;               // "解锁"
剩余区代码段...

优点：

  • 实现简单，无需像软件实现方法严格检查逻辑漏洞。
  • 适用于多处理机环境。

缺点：忙等待，不满足让权等待

Swap指令

别名Exchange指令，或简称XCHG指令

Swap指令使用硬件实现的，执行的过程不允许被中断，只能一气呵成。

Swap等效C逻辑

1
2
3
4
5
6
7
// Swap 指令的作用是交换两个变量的值
Swap (bool *a, bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

使用Swap指令：

1
2
3
4
5
6
7
8
// 以下是用 Swap 指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while (old == true)
    Swap (&lock, &old);
临界区代码段...
lock = false;
剩余区代码段...

逻辑上看，Swap和TSL并无太大区别。

优点：

  • 实现简单，无需像软件实现方法严格检查逻辑漏洞。
  • 适用于多处理机环境。

缺点：忙等待，不满足让权等待

锁

解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 acquire()获得锁，而函数 release()释放锁。

每个互斥锁有一个布尔变量 available，表示锁是否可用。如果锁是可用的，调用 acquire()会成功，且锁不再可用。当一个进程获取不可用的锁时，会被阻塞，直到锁被释放。

1
2
3
4
5
6
7
8
9
acquire() {
    while (!available)       // 忙等待
    	;
    available = false;       // 获得锁
}

release() {
    available = true;        // 释放锁
}

acquire()和 release()的执行必须是原子操作，因此互斥锁通常采用硬件机制实现。

缺点：

  • 忙等待：当有一个进程在临界区中，其他任何进程在进入临界区时必须连续循环调用 acquire()。

像这样需要连续循环忙等的互斥锁，还可以称为自旋锁(spin lock)。

常见自旋锁：

  • TSL指令
  • swap指令
  • 单标志法

虽然这里我们将忙等待列为一个缺点，这是因为忙等待违反了”让权等待”这一原则。

但是在一些情况下，忙等待也有自己的优势，如：

  • 在多核处理器中，并且上锁时间很短时。

大多数情况下，为了提高处理器并行效率，我们往往会尽可能的精细锁的范围。这样使得每个锁的上锁时间很短。此时线程等待解锁的时间可能小于切换进程上下文的时间。所以效率反而更高。

这也导致自旋锁更适用于多处理器的系统。可以减少却换进程上下文的频率。

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

原语：只能一气呵成，不可被中断的程序。

  • 原理：开关中断指令。

信号量：其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

一对原语：

S为传入参数，此处是信号量。

  • wait(S)/P(S)
  • signal(S)/V(S)

wait、signal原语简称为P、V操作。

整形信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

对于整形信号量，我们只能有三种操作：

  • 初始化：初始化信号量的数量
  • P操作：申请一个资源S，如果资源不够就阻塞等待
  • V操作：释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。
1
2
3
4
5
6
7
8
9
10
int S = 1; // 初始化整型信号量S，表示当前系统中可用的打印机资源数

void wait (int S) { // wait原语，相当于“进入区”
    while (S <= 0); // 如果资源数不够，就一直循环等待
    S=S-1;         // 如果资源数够，则占用一个资源
}

void signal (int S) { // signal原语，相当于“退出区”
    S=S+1;           // 使用完资源后，在退出区释放资源
}

使用资源：

1
2
3
4
5
6
进程P0:
...
wait(S);
使用打印机资源；
signal(S);
...

缺点：

  • 忙等待，不满足让权等待，若无法获得锁，会阻塞在wait原语中。

记录型信号量

整形信号量的缺陷是存在忙等问题，因此人们又提出了”记录型信号量”，即用记录型数据结构表示的信号量。

1
2
3
4
5
/* 记录型信号量的定义 */
typedef struct {
    int value;               // 剩余资源数
    struct process *L;       // 等待队列
} semaphore;

原语：

1
2
3
4
5
6
7
8
9
10
11
12
13
void wait(semaphore S){
    S.value--;		//有一个进程请求了该资源，数量-1
    if(S.value < 0){	//小于0则资源已经分配完
   	block(S.L);	//阻塞进程
    }
}

void signal (semaphore S){
    s.value++;		//有一个进程释放资源，数量+1
    if(S.value <= 0){	//小于等于0则还有进程没有得到资源
	wakeup(S.L);	//唤醒一个进程将资源分配给他
    }
}

block()：block原语使进程从运行态进入阻塞态。并把进程挂到信号量S的等待队列(阻塞队列)中。

wakeup()：wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。

该机制遵循了让权等待的原则。不会出现忙等现象。

信号量机制实现进程互斥

  1. 分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应该放在临界区)
  2. 设置互斥信号量mutex，初值为资源数量
  3. 在进入区P(mutex)——申请资源。
  4. 在退出区V(mutex)——释放资源。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*信号量机制实现互斥*/
semaphore mutex=1;  //初始化信号量

P1(){
    ...
    P(mutex);   //使用临界资源前需要加锁
    临界区代码段...
    V(mutex);   //使用临界资源后需要解锁
    ...
}

P2(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

此处我们简写了信号量的初始化，变量 semaphore表示记录型信号量。并非整形信号量。

注意：

  • 对不同临界资源需要设置不同的互斥信号量。
  • P、V操作必须成对的出现。

信号量机制实现进程同步

进程同步：让各进程按照要求有序的推进。

  1. 分析什么地方需要实现”同步关系”，即必须保证”一前一后”执行的两个操作。
  2. 设置同步信号量S，初始化为0。
  3. 在”前操作”后执行V(S)，表示资源已经就绪。
  4. 在”后操作”前执行P(S)，申请”前操作”这一资源。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*信号量机制实现同步*/
semaphore S=0;  //初始化同步信号量，初始值为0

P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}

P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

保证了代码4一定在代码2之后执行。

进程的前驱关系

进程P1中有代码S1，进程P2中有代码S2，……，进程P6中有代码S6。

按照如下前驱图所示的顺序执行：

1761873069442

将每一条线，当作一个进程同步问题。

  1. 为每一对前驱关系各设置一个同步信号量。
  2. 在”前操作”之后对相应的同步信号量执行V操作。
  3. 在”后操作”之前对相应的同步信号量执行P操作。

1761873294825

生产者-消费者问题

问题：

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。

生产者消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥的访问。

1761874429285

分析前驱关系：

  1. 缓冲区没满->生产者生产

    以产品为资源进行建模，P操作表示消费一个产品，V操作表示生产一个产品，用于限制消费者在没有产品时不再消费。

    1761874623067

  2. 缓冲区没空->消费者消费

    再以缓冲区为资源进行建模。用于限制生产者在没有空位时不再继续生产。

    1761874643287

分析互斥关系：

  1. 进程之间访问缓冲区互斥。
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
// 解决生产者-消费者问题

semaphore mutex = 1;  // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;  // 同步信号量，表示空闲缓冲区的数量 (初始值为缓冲区总大小 n)
semaphore full = 0;   // 同步信号量，表示产品的数量，即非空缓冲区的数量 (初始值为 0)

producer () {
    while(1){
        生产一个产品;
        P(empty);       // 消耗一个空闲缓冲区
        P(mutex);
        把产品放入缓冲区;
        V(mutex);
        V(full);        // 增加一个产品 (非空缓冲区)
    }
}

consumer () {
    while(1){
        P(full);        // 消耗一个产品 (非空缓冲区)
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);       // 增加一个空闲缓冲区
        使用产品;
    }
}

实现互斥的P操作一定要在实现同步的P操作之后。否则可能发生死锁。

多生产者-多消费者问题

问题模型：

卓子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子。儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

1761959900092

互斥关系分析：

  • 队缓冲区(盘子)的访问要互斥的进行。

同步关系：

  • 父亲将苹果放入盘子后，女儿才能取苹果。
  • 母亲将橘子放入盘子后，儿子才能取橘子。
  • 只有盘子为空时，父亲或母亲才能放入水果。

信号量定义：

1
2
3
4
semaphore mutex = 1; 	//实现盘子的互斥访问
semaphore apple = 0;	//盘子中有几个苹果
semaphore orange = 0;	//盘子中有几个橘子
semaphore plate = 1;	//盘子中的剩余空间

各进程的P、V操作：

父亲线程：

1
2
3
4
5
6
7
8
9
10
dad (){
    while(1){
	准备一个苹果;
	P(plate);
	P(mutex);
	把苹果放入盘子;
	V(mutex);
	V(apple);
    }
}

母亲线程：

1
2
3
4
5
6
7
8
9
10
mom (){
    while(1){
	准备一个橘子;
	P(plate);
	P(mutex);
	将橘子放入盘子;
	V(mutex);
	V(orage);
    }
}

女儿线程：

1
2
3
4
5
6
7
8
9
daughter (){
    while(1){
	P(apple);
	P(mutex);
	将苹果拿出盘子;
	V(mutex);
	V(plate);
    }
}

儿子线程：

1
2
3
4
5
6
7
8
9
sun (){
    while(1){
	P(orange);
	P(mutex);
	将苹果取出盘子；
	V(mutex);
	V(plate);
    }
}

在此题中，由于本题的缓冲区大小为1，所以在任意时刻，apple、orange、plate三个同步信号量中最多只有一个是 1。因此最多只有一个进程的P操作不会被阻塞。所以可以不设置mutex信号量与互斥锁，也可以正常运行。

读者写者问题

问题：

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问数据时则可能导致数据不一致的错误。因此要求：

  1. 允许多个读者可以同时对文件执行读操作；
  2. 只允许一个写者往文件中写信息；
  3. 任一写者在完成写操作之前不允许其他读者或写者工作；
  4. 写者执行写操作前，应让已有的读者和写者全部退出；

互斥关系分析：

  • 写进程与写进程互斥
  • 写进程与读进程互斥
  • 读进程与读进程不互斥

信号量定义：

1
2
3
semaphore rw=1;
int count = 0;
semaphore mutex = 1;

写进程：

1
2
3
4
5
6
7
write (){
    while(1){
	P(rw);	//写之前加锁
	写文件...;
	V（rw); //写完了解锁
    }
}

读进程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
reader (){
    while(1){
	P(mutex);	//使各进程互斥的访问count
	if(count == 0)	//由第一关读进程负责上锁
	    P(rw);
	count++;	//访问文件的进程数+1
	V(mutex);
	读文件...;
	P(mutex);	//各进程互斥访问count
	count--;	//访问文件的读进程数-1
	if(count == 0)	//由最后一个进程负责解锁
	    V(rw);
	V(mutex);
    }
}

潜在问题：只要有读进程还在读，写进程就需要一直阻塞等待，可能”饿死”。

因此在这种算法中，读进程是优先的。

如何解决：读写公平法

信号量定义：

1
2
3
4
semaphore rw=1;
int count = 0;
semaphore mutex = 1;
semaphore w = 1;

写者进程：

1
2
3
4
5
6
7
8
9
10
write (){
    while(1){
	P(w)
	P(rw);	//写之前加锁
	写文件...;
	V（rw); //写完了解锁
	V(w);
    }
}

读进程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
reader (){
    while(1){
	P(w);
	P(mutex);	//使各进程互斥的访问count
	if(count == 0)	//由第一关读进程负责上锁
	    P(rw);
	count++;	//访问文件的进程数+1
	V(mutex);
	V(w);
	读文件...;
	P(mutex);	//各进程互斥访问count
	count--;	//访问文件的读进程数-1
	if(count == 0)	//由最后一个进程负责解锁
	    V(rw);
	V(mutex);
    }
}

用一个信号量w，来确定线程的服务顺序。在每个进程想要进程读写操作时，通过向信号量w进行申请，来将自己挂载到服务排队队列中。

  • 读进程：读进程拿到w锁后，无需做额外操作，直接释放即可。锁会传递给下一个申请服务的进程。
  • 写进程：写进程拿到w锁后，后续的读进程将被阻塞，挂载到信号量w的排队队列中。

哲学家吃饭问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

1762340296938

思路：

  • 使用互斥锁，对于拿筷子这一动作进行上锁。确保拿筷子这一动作是一气呵成的。在一个哲学家拿起两个筷子开始进行吃饭前，不会有第二个哲学家进行拿筷子这一动作。确保不会出现每个哲学家各拿了一根筷子的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

Pi(){
    while(1){
	P(mutex);
	P(chopstick[i]);
	P(chopstick[(i+1)%5]);
	V(mutex);
	吃饭...;
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	思考...;
    }
}

其他思路：

  • 限制最多允许四个哲学家同时进餐。
  • 要求奇数号哲学家先拿起左边筷子，然后再去拿右手筷子。而偶数号哲学家正好相反。

理发师睡觉问题

理发师状态与顾客行为 ：

  • 理发师闲置 ：如果没有顾客，理发师就 睡觉 。
  • 顾客到来 (理发师忙碌) ：
  • 如果等待室的 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
27
28
29
30
// 理发师
void Barber(void) {
    while (true) {
        wait(customers);     /* 如果无等待顾客，则睡觉 */
        wait(mutex);         /* 服务顾客，将等待顾客数减1 */
        waitingN := waitingN - 1;
        signal(mutex);
        signal(barber);      /* 理发师召唤1个等待顾客，开始理发 */
        cut_hair()
    }
}

// 顾客
Void Customers(void) {
    wait(mutex);

    if (waitingN < CHAIRS) {
        /* 判断是否有空椅子，等待 */
        waitingN := waitingN + 1;
        signal(customers);  /* 通知理发师，有等待顾客 */
        signal(mutex);

        wait(barber);       /* 请求理发师为自己服务 */
        get_hair()
    }
    else {
        /* 如果客满无空椅子，离开 */
        signal(mutex)
    }
}

管程Monitors

信号量机制存在的问题：编写程序困难、易出错

定义与基本特征

管程是一种特殊的软件模块，由以下部分组成：

  1. 局部于管程的共享数据结构说明
  2. 对该数据结构进行操作的一组过程
  3. 对局部于管程的共享数据设置初始值的语句
  4. 管程的自定义名称

管程类似于一个面向对象编程中的类。

  • 有成员变量
  • 有操作成员变量的方法

管程的基本特征：

  1. 局部于管程的数据只能被局部于管程的过程所访问
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

人话翻译：

  • 进程想要访问管程中的数据结构，只能通过调用管程提供的方法进行访问。
  • 同一操作同时只允许一个进程进入执行。

使用C代码的管程示例：

管程定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
monitor ProducerConsumer
    condition full, empty; //条件变量用来实现同步 (排队)
    int count=0; //缓冲区中的产品数
    void insert (Item item) { //把产品item放入缓冲区
        while (count == N)		//如果产品满了，则等待
            wait (full);
        count++;
        insert_item(item);
        if (count == 1)		//如果产品从0到1，则唤醒一个消费者进程
            signal(empty);
    }
    Item remove () { //从缓冲区中取出一个产品
        while (count == 0)		//如果产品为空进行等待
            wait (empty);
        count--;
        if (count == N-1)	//如果产品之前为满，则唤醒一个生产者进程
            signal(full);
        return remove_item();
    }
end monitor

管程的使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//生产者进程
producer (){
    while(1){
        item = 生产一个产品;
        ProdecerConsumer.insert (item);		//调用管程存储产品
    }
}

//消费者进程
consumer (){
    while(1){
        item = ProdecerConsumer.remove ();	//调用管程获取产品
        消费产品item;
    }
}

insert和remove进程间也互斥

由编译器负责实现各进程互斥的进入管程中的过程。

引入管程的目的为更方便的实现进程互斥和同步：

  1. 需要在管程中定义共享数据；
    • 如生产者消费者中的共享数据
  2. 需要在管程中定义用于访问这些共享数据的”入口”；
    • 如 insert()方法和 remove()
  3. 只有通过这些这些特定的入口才能访问共享数据；
  4. 管程中有很多入口，但是每次只能开放其中一个入口，并且只能让一个进程或线程进入；
  5. 可在管程中设置条件变量以及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时该进程应先释放管程的使用权，也就是让出”入口”)；可通过唤醒操作将等待在条件变量上的进程或线程唤醒；

Java中类似的机制

Java中 synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用：

1
2
3
4
5
6
7
static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    public synchronized void insert(Item item){
  	...
    }
}

死锁

在并发环境下，各进程因竞争资源而造成的一种相互等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是”死锁”。发送死锁后，若无外力干涉，这些进程都将无法向前推进。

概念 区别
死锁 死锁一定是“循环等待对方手里的资源”导致的，因此至少有两个或两个以上的进程同时发生死锁；发生死锁的进程一定处于阻塞态。
饥饿 可能只有一个进程发生饥饿；饥饿的进程既可能是阻塞态（如长期得不到需要的 I/O 设备），也可能是就绪态（长期得不到处理机）。
死循环 可能只有一个进程发生死循环；死循环的进程可以处于运行态，只是无法像期望的那样顺利推进。死锁和饥饿是由于操作系统分配资源策略不合理导致的，而死循环是代码逻辑错误导致的。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。

死锁发生的条件

产生自锁必须同时满足以下四个条件，只要任意条件不成立，死锁就不会发送。

  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。如（哲学家的筷子，打印机设备）。对于可以同时让多个进程使用的资源是不会导致死锁的。
  • 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 请求和保持条件：进程已经保持了一个资源，但是又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

死锁的处理策略

  1. 预防死锁：破坏死锁产生的四个必要条件中的一个或几个
  2. 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁
  3. 死锁的检测和解除：死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

预防死锁

预防死锁就是要在死锁发生前破坏死锁发生的条件。

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

SPOOLing技术：

操作系统可以采用SPOOLing技术把独占设备在逻辑上改造为共享设备。比如用SPOOLing技术将打印机改造为共享设备。

缺点：

  • 不是所有资源都可以改造为共享资源
  • 为了系统安全，有时必须保留 互斥性。

破坏不剥夺条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保留的所有资源，待以后需要时再重新申请。

方案二：当某个进程需要的资源被其他进程所占有时，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级。

缺点：

  • 实现复杂
  • 释放已获得的资源可能造成前一段工作失效。
  • 反复申请释放资源会增加系统开销

破坏请求和保持条件

请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占用，此时进程请求被阻塞，但又对自己已有的资源保持不放。

静态分配方法：

  • 进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求其他任何资源。

缺点：

  • 资源浪费，资源利用率极低
  • 也可能导致进程饥饿

破环循环等待条件

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

顺序资源分配法：

  • 首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源。

原理：已持有大编号资源的进程不可能逆向回来申请小编号的资源，从而不会产生循环等待。

缺点：

  • 不方便增加新设备
  • 进程实际使用资源的顺序可能和编号递增顺序不一致，导致资源浪费。
  • 用户编程麻烦

避免死锁

安全序列

安全序列：如果系统按照这种方式分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这意味着之后可能所有的进程都无法顺利的执行下去。当然如果有一些进程提前归还了一些资源，那系统也可能重新回到安全状态。

如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生死锁。但是如果发生了死锁，则一定是在不安全状态。

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否同意资源分配请求。

银行家算法

安全性算法：

1763887622313

当前剩余资源{3,3,2}>{1,2,2} & {0,1,1}，所以可以先依次满足p1和p3。等待它们返还所有资源。

1763887721242

返还后，剩余资源：{7,4,3}，已经可以满足任意线程的需求量，所以存在安全序列。可以是：

  • {1,3,0,2,4}

此时系统处于安全状态，不可能发生死锁。

代码实现

假设系统中有n个进程，m种资源。

数据结构设计

  • 最大需求矩阵(Max)：$n \times m$ 矩阵。

  • 分配矩阵 (Allocation) : $n \times m$ 矩阵。

  • 需求矩阵 (Need) : $n \times m$ 矩阵。

    $$
    Need = Max - Allocation
    $$

  • 可用资源向量 (Available) : 长度为 $m$ 的一维数组。

  • 请求向量 (Request) : 长度为 $m$ 的一维数组。

算法执行流程

当进程 $P_i$ 发出资源请求 $Request_i$ 时，系统按照以下步骤进行检查和预判：

第一步：检查请求是否合法

  • 判断：$Request_i[j] \le Need[i, j]$
  • 含义：请求的资源不能超过它之前声明的“最大剩余需求”。如果超过，则视为出错（因为它想要的比它承诺的最大值还多）。

第二步：检查系统是否有足够资源

  • 判断：$Request_i[j] \le Available[j]$
  • 含义：系统现有的资源是否足够满足这次请求。如果不够，进程 $P_i$ 必须等待（阻塞）。

第三步：试探性分配 (Trial Allocation)

  • 操作：系统假定把资源分配给 $P_i$，并修改相关数据（这只是为了做预判，并非真的分配）：
    • $$
      Available = Available - Request_i
      $$
    • $$
      Allocation[i, j] = Allocation[i, j] + Request_i[j]
      $$
    • $$
      Need[i, j] = Need[i, j] - Request_i[j]
      $$

第四步：执行安全性算法

  • 操作：检查在完成上述“试探性分配”后，系统是否处于 安全状态 （即是否存在一个安全序列，能保证所有进程都能完成）。
  • 结果判定 ：
  • 若安全 ：正式分配资源。
  • 若不安全 ：撤销之前的试探性修改，恢复数据，让进程 $P_i$ 等待。

死锁的检测和解除

死锁的检测

为了能对系统是否已经发生了死锁进程检测，必须：

  1. 用某种数据结构来保存资源的请求和分配信息。
  2. 提供一种算法，利用上述信息来检测系统是否已经进入死锁状态。

数据结构：资源分配图

两种节点：

  • 进程节点：对应一个进程
  • 资源节点：对应一类资源，一类资源可能有多个

两种边：

  • 进程节点->资源节点：表示进程想申请的资源。
  • 资源节点->进程节点：表示已经为进程分配的资源。

1763974418205

算法：

  1. 在资源分配图中，找出既不阻塞又不是孤点的进程$P_i$(即可以满足资源继续运行直到进程结束的进程)
  2. 消去它所有的请求边和分配边，使之成为孤立的节点。
  3. 进程$P_i$所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
  4. 如果按照上面的方法进行一系列化简后，若能消去图中所有的边，则该图是可完全化简的。

死锁定理：如果某时刻系统的资源分配图是不可完全化简的，那么此时系统死锁。

化简资源分配图后，还连着边的进程就是死锁进程。

1763974958814

p1可以申请到$R_2$资源，所以P1可以继续执行一直到P1结束，然后释放所有资源：

1763975044330

接着P2的资源照样可以得到满足，所以所有的边都可以消去，完全化简。

死锁解除

资源剥夺法：挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些 资源分配给其他死锁进程。但是应该防止被挂起的进程长时间得不到资源而饥饿。

撤销进程法：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。付出代价很大。

进程回退法：让一个或多个进程回退到足以避免死锁的地步。这就要求系统记录进程的历史信息，设置还原点。

如果决定对哪些进程动手：

  • 进程优先级。对低优先级动手
  • 已执行的时间。对少的动手
  • 还要多久完成。对久的动手
  • 进程已经使用了多少资源。对多的动手
  • 进程是交互式的还是批处理式的。对批处理动手
笔记
#操作系统
第三章--同步与互斥
http://blog.ulna520.com/2025/10/28/第三章--同步与互斥_20251028_085904/
Postigita
October 28, 2025
Lizenta