田园幻想乡

Appearance

点击分享

2.4 进程同步 ​

目录 ​

进程的 2 中相互制约关系：

  1. 间接相互制约关系：主要是由于资源的互斥使用造成的
  2. 直接相互制约关系：主要是由于进程的合作关系造成的

临界区和临界资源 ​

临界区是一段访问共享资源的代码，这段代码中的数据会被共享，临界区的访问是互斥的，即同一时间只允许一个进程进入临界区。

eg：多个函数访问一个全局变量，这个全局变量就是临界资源，访问这个全局变量的函数就是临界区。

eg：文件也是临界资源，访问文件的函数也是临界区。

同步机制应规范： ​

  1. 空闲让进：如果临界区空闲，就应该立即让进程进入临界区
  2. 忙则等待：如果临界区被占用，就应该等待
  3. 有限等待：如果有多个进程等待进入临界区，那么应该保证这些进程都能进入临界区，而不是让其中一个进程无限等待
  4. 让权等待：如果进程不能进入临界区，就应该释放 CPU，让其他进程执行，而不是无限等待

实现方法 ​

软件方法因为一些问题比较不方便，所以一般使用硬件方法。如硬件方法中的中断屏蔽、原子操作、硬件指令等。

关中断（中断屏蔽） ​

关闭系统的中断，让调度程序无法调度其他进程，从而保证临界区的互斥访问。

问题：

  1. 关中断会影响系统的正常运行，极大的降低了系统的并发性
  2. 多处理机系统中，关中断只能保证单个处理机中的临界区互斥访问，无法保证多个处理机中的临界区互斥访问

Test-and-Set | 硬件指令 ​

核心思想：使用一个硬件指令，这个指令可以原子地读取一个内存单元的值，并将这个内存单元的值置为 1，这个指令的返回值是这个内存单元的原始值。

c
// 查询临界区是否空闲
TestAndSet(bool *lock) {
    bool initial = *lock;
    *lock = true;
    return initial;
}

lock 是一个布尔变量，初始值为 false，表示临界区空闲，当值为 true 时，表示临界区被占用。

使用方法：

C
// 定义一个临界区标记
bool lock = false;
// 进程被调度到CPU上
// code
// 想要进入临界区，先查询临界区是否空闲，如果空闲，就进入临界区，否则等待，直到临界区空闲或者时间片用完
while (TestAndSet(&lock)) {
    // 临界区被占用，等待，循环
}
// 临界区空闲，进入临界区
// code
// 退出临界区，将临界区标记为false
lock = false;
// code

问题：

  1. 当资源被占用的时候会不断地去测试，造成“忙等待”，浪费 CPU 资源

Swap | 硬件指令 ​

核心思想：使用一个硬件指令，这个指令可以原子地交换两个内存单元的值。

C
// 交换两个变量的值
Swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

使用方法：

C
// 定义一个临界区标记
bool lock = false;
// 进程被调度到CPU上
// code
// 定义一个用于交换的变量
key = true;
do {
    // 交换临界区标记和交换变量的值
    swap(&lock, &key);
    // 如果交换变量的值为true，说明临界区被占用，等待，循环
}while (key == true);
// 进入临界区
// code临界区操作
// 退出临界区，将临界区标记为false
lock = false;

问题：

  1. 不符合“让权等待”，因为进程在等待的时候，一直占用 CPU 资源

信号量机制 ​

使用信号量来处理让权等待的问题。

信号量是一个整型/记录型变量，可以对它进行两种操作：P 操作和V 操作。

P 操作也会写成 wait()，用于申请一个资源，如果资源已经被占用，就等待。

V 操作也会写成 signal()，用于释放一个资源。

整型变量和前面的类似，不再赘述。

记录型变量 ​

记录型变量是一个记录，记录中包含了两个数据项：值和一个指针。

我们这里用 C 语言来实现记录型变量。

WARNING

底层实现并不是用 C 语言，这里只是为了方便理解。

C
// 记录型变量
typedef struct {
    int value; // 记录型变量的值
    struct process *L; // 指向一个进程队列，用于存放在等待的进程
} semaphore;

P 操作 ​

C
// 传入需要操作的信号量
P(semaphore *s) {
    s->value--;
    // 当信号量的值小于0时，说明资源被占用，需要等待
    if (s->value < 0) {
        // 将进程插入到等待队列中
        // 阻塞进程
        block(S->L);
        // 这里的block()函数就是阻塞原语，用于阻塞进程，该进程在此进入阻塞状态，直到被唤醒
    }
}

V 操作 ​

C
// 传入需要操作的信号量
V(semaphore *s) {
    s->value++;
    // 当信号量的值小于等于0时，说明有进程在等待，需要唤醒
    if (s->value <= 0) {
        // 将进程从等待队列中移除
        // 唤醒进程，从阻塞状态进入就绪状态，目标进程在下次调度时会被调度到CPU上，就可以进入临界区了
        // 只会唤醒一个进程，如果有多个进程在等待，那么只会唤醒一个，其他的进程还是会在等待队列中
        wakeup(S->L);
    }
}

信号量的使用 ​

C

// 定义一个信号量
semaphore s;
// 初始化信号量的值为1
s.value = 1;

// 进程被调度到CPU上
// code
// 进入临界区，申请资源，如果资源被占用，该进程就会被阻塞，直到资源被释放
P(&s);
// code
// 退出临界区，释放资源
V(&s);
// code

pv 操作的经典习题 | CSDN

使用 PV 操作实现前趋关系 | CSDN

AND 型信号量 ​

为什么需要 AND 型信号量？因为交叉访问资源会导致死锁。

死锁问题模拟

C
// 定义两个信号量
semaphore s1, s2;
// 初始化信号量的值为1
s1.value = 1;
s2.value = 1;

// 现在又两个进程，进程A和进程B，都要访问临界资源s1和s2

process A

P(&s1);
P(&s2);

process B

P(&s2);
P(&s1);

死亡回放：

  1. A 访问 s1 并占用
  2. B 访问 s2 并占用
  3. A 访问 s2，被阻塞
  4. B 访问 s1，被阻塞
  5. A 和 B 都在等待对方释放资源，造成死锁

噔噔咚

解决方法：使用 AND 型信号量

AND 型信号量的特点：只有当所有的信号量都可用时，进程才能进入临界区。

使用 SP()和 SV()来代替 P()和 V()。

C
// SP()/Swait()操作
SP(s1,s2,...,sn) {
    // while循环保证在被唤醒的时候，会再次进行判断
    while(true){
        // 如果所有的信号量都可用，就进入临界区
        if(s1.value > 0 && s2.value > 0 && ... && sn.value > 0){
            for (int i = 0; i < n; i++) {
                si.value--;
            }
            break;
        }
        else{
            // 进程被阻塞，等待被唤醒
            for (int i = 0; i < n; i++) {
                // 进程指针将被插入到遇到的第一个不可用的信号量的等待队列中
                // eg s1可用，s2不可用，那么进程指针将被插入到s2的等待队列中，当s2被释放的时候，进程指针将被唤醒，再次进行判断
                // 再次进行判断的原因是，进程在被释放后调用前，其他进程可能已经进入临界区了，所以需要再次进行判断
                if (si.value <= 0) {
                    block(si.L);
                }
            }

        }
    }
}

// SV()/Ssignal()操作
SV(s1,s2,...,sn) {
    for (int i = 0; i < n; i++) {
        si.value++;
        if (si.value <= 0) {
            // 唤醒进程，从阻塞状态进入就绪状态，目标进程在下次调度时会被调度到CPU上，就可以进入临界区了
            wakeup(si.L);
        }
    }
}

使用方法：

C
// 定义两个信号量
semaphore s1, s2;

// 进程被调度到CPU上
// code
// 进入临界区，需要同时申请s1和s2，如果s1或者s2被占用，该进程就会被阻塞，直到s1和s2都可用
SP(&s1, &s2);
// code
// 退出临界区，释放s1和s2
SV(&s1, &s2);
// code

信号量集 ​

目前的 P 和 V 操作每次只能操作 1 个信号量，如果需要操作多个信号量，就需要多次调用 P 和 V 操作，这样容易出错，比如造成死锁（连续 2 个 P(s1)，但 s1 本来就剩 1 个了）。

同时为了保证系统的安全性，部分信号量在值小于一定值的时候，就不予分配资源。

信号量集对 AND 信号量机制进行了扩充，解决了这个问题

C
SP(s1,t1,d1,...,sn,tn,dn){
    // ti表示资源分配下限，资源值如果小于这个值就不分配了
    // di表示需要分配的资源数
    while(true){
        // 需要同时满足信号量资源大于ti和di
        if(s1.value > t1 && s1.value > d1 && ... && sn.value > tn && sn.value > dn){
            for (int i = 0; i < n; i++) {
                si.value -= di;
            }
            break;
        }
        else{
            for (int i = 0; i < n; i++) {
                if (si.value <= ti || si.value <= di) {
                    block(si.L);
                }
            }
        }
    }
}

SV(s1,d1,...,sn,dn){
    for (int i = 0; i < n; i++) {
        si.value += di;
        if (si.value <= 0) {
            wakeup(si.L);
        }
}

使用方法：

C

SP(s1,1,1,s2,1,2);

SP(s1,2,1,s2,1,2);

信号量集的特殊情况：

C
SP(S,d,d)

SP(S,1,1)
// 等价于P(S)

SP(S,1,0)
// 一个检查，如果S的值大于1，就允许程序继续执行，否则就阻塞
// 可以视为和资源值有关的开关，但不会消耗资源

管程（管理程序） ​

管程是一种进程间的同步和互斥工具，是一种高级的同步工具。

就是把对资源的操作封装到一个类中，然后通过调用类的方法来操作资源。一般这个工作由语言本身来完成，比如 C++ 中的文件流，Java 中的线程池等。

管程的组成：

  1. 管程的名称
  2. 局部于管程的共享数据结构说明
  3. 对共享数据进行操作的一组过程
  4. 对局部于管程的共享数据进行初始化的一段代码

Copyright © 2022 田园幻想乡 浙ICP备2021038778号-1