操作系统

进程同步与进程互斥

Posted by JimWang on 2021-02-04

进程同步与进程互斥

进程互斥

进程互斥也称为间接制约关系，进程间对临界资源的访问，必须是互斥的执行。指一个进程进入临界区访问临界资源的时候，其他进程只能等待。

1
2
3
4
5
6
do {
    entry section;  // 进入区 检查是否可以进入临界区，可以进入，设置访问临界资源的标志，防止其他进程进入
    critical section; // 临界区  访问临界资源的代码
    exit section;    // 退出区  负责解除临界资源访问标志
    reemainder section; // 剩余区  其他处理
} while(true);

进程互斥的原则

为了实现对临界资源的互斥访问，同时保证系统的整体性能，需要遵循以下的原则：

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

四种进程互斥的软件实现

单标志法

image-20210206145713137

在进入临界区之前做检查。可能发生的事情就是turn1，而p0进程一直不进入临界区。不符合空闲让进原则

双标志先检查

image-20210206145806437

通过bool数组记录线程想要进入临界区的意愿

可能出现的问题：flag[0]和flag[1]同时为false，两个线程同时进入了临界区。不符合忙则等待原则

双标志后检查

image-20210206150345015

先加锁，后检查。

可能出现的问题：两边同时加锁，不遵循空闲让进，有限等待，可能出现饥饿

Peterson算法

image-20210206150449086

flag用来表示想进临界区的意愿，turn表示谁先进。如果此时flag[1]是true，并且turn1.说明P1线程想进，并且他可以先进。那么p1就先进，p0线程在while循环

会发生的问题：不遵循让权等待，会发生忙则等待。P0不能进入临界区，但是由于要while循环检测，不能放弃cpu

进程互斥的硬件实现方式

中断屏蔽

利用“开关中断指令”实现（同原语的思想），在某个进程访问临界区 到 临界区访问结束 都不允许被中断，也就是不能发生进程的切换。

关中断 --> 临界区 --> 开中断

优点：简单高效

缺点：不适用于多处理机系统（一个处理机关中断，不会影响其他处理机对临界区的访问）。只适合于操作系统内核进程，不适用于用户进程。（开关中断属于特权指令）

TestAndSet(TS\TSL指令)

TSL指令由硬件实现，执行过程不允许被中断。

image-20210206150954517

如果临界区被使用lock的值就是true，old=true，就会一直是true，进程一直在等待。反之，lock是false，就会返回false，停止阻塞，并且在返回之前lock也已经被重新上锁。

**适用于多处理环境。不满足让权等待。**一样的问题，等待中，会一直while循环

Swap指令(XCHG指令)

Swap指令由硬件实现，执行过程不允许被中断。

image-20210206151211192

他有TSL类似，循环等到lock释放的时候

适用于多处理环境。不满足让权等待。

信号量机制及实现进程同步、互斥

进程互斥的四种软件实现方式和三种硬件方式都不能做到让权等待

可以通过使用信号量机制来解决。

数值信号量

image-20210206151418135

记录型信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//记录型信号量定义
typedef struct {
	int value;   // 剩余资源数
    struct process *L; // 等待队列
} semaphore;
// 进程需要使用资源时，通过wait原语申请
void wait(semaphore S) {
	S.value--;
    if (S.value < 0) {
    	block(S.L); // 如果资源数量不足，就将等待队列里的都放入阻塞态
    }
}
// 进程使用完成资源后，使用signal原语释放
void signal(semaphore S) {
	S.value++;
    if (S.value <= 0) {
    	wakeup(S.L); // 资源又有了，就唤醒
    }
}
  • 如果剩余的资源数不够，使用block原语使进程从运行态进入到阻塞态，并把挂到信号量S的等待队列。
  • 释放资源之后，若还有别的进程等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞转为就绪态。

实现了让权等待。

信号量实现互斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*信号量机制实现互斥*/
semaphore mutex = 1;  // 初始化信号量，也就是锁

P1() {
    P(mutex); // 使用临界资源，加锁
    /*临界区代码*/
    V(mutex); // 使用完毕，释放锁
}

P2() {
    P(mutex); // 使用临界资源，加锁
    /*临界区代码*/
    V(mutex); // 使用完毕，释放锁
}

互斥信号量mutex，初始值为1，说明该临界区，同时只能有一个进程访问。

注意：对于不同的临界区资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P操作就不能对邻接资源互斥访问，缺少V操作，就会导致资源永远都不会释放，等待进程永不会被唤醒。

信号量实现同步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
*信号量机制实现同步*/
semaphore S = 0;  // 初始化信号量

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

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

如果P2线执行，P需要消耗信号量，而此时是0，因此阻塞等待。P1执行完代码2，执行好V，S++后才会唤醒P2进程。




FRIENDS