【操作系统专业课】第二次作业

第1题（进程同步与互斥）

使用二值信号量实现 n 个进程之间的互斥。

---

1. 定义一个二值信号量 mutex= 1。

二值信号量：二值信号量只有两种取值，0 （资源已被占用）和 1（资源可用）。

2. 进程进入临界区前的操作：每个进程在进入临界区之前，都需要执行 P(mutex) 操作。

P 操作的定义如下：

• 若 mutex 的值大于 0，则将 mutex 的值减 1，进程可以进入临界区。

• 若 mutex 的值等于 0，则进程会被阻塞，进入等待队列，直到 mutex 的值大于 0 时被唤醒。

当进程成功执行 P(mutex) 操作后，即获得了对临界区资源的访问权，可以进入临界区执行相应的操作。

3. 进程在临界区内的操作：临界区是指一次只允许一个进程访问的代码段，在这里实现对共享资源的互斥访问。

4. 进程离开临界区后的操作：当进程完成在临界区内的操作后，需要执行 V(mutex) 操作来释放对临界区资源的占用。

V 操作的定义如下：

• 将 mutex 的值加 1。

• 如果有进程在等待队列中等待访问临界区资源（即 mutex 的值在执行 V 操作之前为 0），则唤醒等待队列中的一个进程，使其可以进入临界区。

第2题（进程同步与互斥）

证明 Dekker 算法满足临界区问题的三个要求

Dekker算法：第一个著名的正确解决两个进程临界区问题的软件方法。

两个进程和共享以下变量：

boolean flag[2];   //进程i,j的标志位:代表两个不同进程（线程）是否准备好进入临界区等相关状态
int turn;   //决定哪个进程优先（两个都为T时看他）

进程和进程的结构如下。

while (true) {   //持续尝试进入临界区flag[i] = true;  //i进程有进入临界区的意愿while (flag[j]) {  //j进程是否有进入临界区的意愿if (turn == j) {  //然后进一步检查 turn 的值，如果 turn 指向另一个进程（j）flag[i] = false;   //当前进程（i）会先放弃自己的请求（flag[i] = false）while (turn == j) {}   //然后等待直到 turn 不再指向另一个进程flag[i] = true;   //之后重新设置自己的标志位（flag[i] = true）turn = j;   //并且将 turn 让给另一个进程（turn = j）}}// 这里可以添加临界区代码flag[i] = false;       //最后再次放弃自己的请求（flag[i] = false）// 这里可以添加非临界区代码
}

---

互斥证明

假设进程进入了临界区，那么在它进入临界区之前，一定是执行了 flag[i] = true，并且要么 flag[j] == false，要么 flag[j] == true 且 turn!= j。

如果 flag[j] == false，说明进程此时没有进入临界区的意愿，也就不会与同时进入临界区。

如果 flag[j] == true 且 turn!= j，那么根据算法，当有进入临界区的意愿时，由于 turn 不指向它，它会被阻塞在相应的循环中，无法进入临界区。

同理，当进程进入临界区时，也能得出类似结论。所以，该算法保证了任何时刻最多只有一个进程能进入临界区，满足互斥要求。

有空让进证明

当临界区空闲时，即没有进程在临界区内，此时 flag[0] 和 flag[1] 都为 false。

假设此时进程想要进入临界区，它会执行 flag[i] = true，然后由于 flag[j] == false，它可以直接进入临界区，不会被阻塞。

因此，只要临界区空闲，有进程请求进入临界区时，该进程就能进入临界区，满足有空让进的要求。

有限等待证明