当前位置：首页 > news >正文

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

news 2025/7/10 2:59:42

第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算法：第一个著名的正确解决两个进程临界区问题的软件方法。

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

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

进程 $P_{i}\left (i == 0or 1\right )$ 和进程 $P_{j}\left (j == 0or 1\right )$ 的结构如下。

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）// 这里可以添加非临界区代码
}

互斥证明

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