常考计算机操作系统面试习题（四）

1. Peterson 算法伪代码

2. 信号量生产者消费者问题分析

3. 注释 Peterson 主函数并分析输出结果

4. 用 fork 创建子进程的程序

1. Peterson 算法伪代码

题目：

写出 Peterson 算法的伪代码。

参考答案：

// 定义变量
boolean flag[2];     // 表示每个线程是否希望进入临界区
int turn;            // 表示轮到哪个线程进入临界区// 线程 i 的代码
do {flag[i] = true;  // 表示线程 i 希望进入临界区turn = j;        // 将权利让给线程 jwhile (flag[j] && turn == j) {// 等待线程 j 完成临界区}// 临界区// ...flag[i] = false; // 离开临界区// 剩余区// ...
} while (true);

说明：

Peterson 算法是用于两个线程的同步算法，保证了互斥和死锁避免。

flag[i] 表示线程 i 是否希望进入临界区。
turn 变量表示当前轮到哪个线程进入临界区，确保不会发生竞争条件。

2. 信号量生产者消费者问题分析

题目：

注释以下代码，并说明三个信号量的含义，以及 A 和 B 哪个是生产者进程，哪个是消费者进程。

semaphore full = 0, empty = n, mutex = 1;A: 
do {… produce an item in nextp …wait(empty);wait(mutex);add nextp to buffer;signal(mutex);signal(full);
} while (1);B: 
do {wait(full);wait(mutex);… remove an item from buffer to nextc …signal(mutex);signal(empty);… consume the item in nextc …
} while (1);

参考答案：

注释代码：

semaphore full = 0;    // 表示缓冲区中的产品数，初始值为 0。
semaphore empty = n;   // 表示缓冲区的空位数，初始值为 n（缓冲区大小）。
semaphore mutex = 1;   // 用于实现对缓冲区操作的互斥访问，初始值为 1。

进程 A 是生产者：

produce an item in nextp; 生产一个产品并将其存储在 nextp。
wait(empty); 确保缓冲区有空位可以存放新产品。
wait(mutex); 确保对缓冲区的互斥访问。
add nextp to buffer; 将产品添加到缓冲区。
signal(mutex); 释放对缓冲区的互斥访问。
signal(full); 增加缓冲区中产品的计数。

进程 B 是消费者：

wait(full); 确保缓冲区中有可供消费的产品。
wait(mutex); 确保对缓冲区的互斥访问。
remove an item from buffer to nextc; 从缓冲区中取出产品到 nextc。
signal(mutex); 释放对缓冲区的互斥访问。
signal(empty); 增加缓冲区的空位计数。
consume the item in nextc; 消费产品。

3. 注释 Peterson 主函数并分析输出结果

题目：

注释以下 Peterson 主函数的每行程序，并分析程序可能的输出结果。

boolean flag[2];
flag[0] = false;
flag[1] = false;
int turn;do {flag[i] = true;turn = j;while (flag[j] && turn == j) {}// 临界区flag[i] = false;// 剩余区
} while (1);

参考答案：

注释代码：

boolean flag[2];        // 定义两个标志位，用于表示线程是否希望进入临界区。
flag[0] = false;        // 初始化标志位，表示线程 0 初始时不希望进入临界区。
flag[1] = false;        // 初始化标志位，表示线程 1 初始时不希望进入临界区。
int turn;               // 定义变量，用于指示当前轮到哪个线程进入临界区。

flag[i] = true;         // 线程 i 表示希望进入临界区。
turn = j;               // 将优先权交给线程 j。
while (flag[j] && turn == j) {}  // 如果线程 j 也希望进入临界区且优先级是 j，则等待。

// 临界区：执行线程 i 的临界区代码。
flag[i] = false;        // 线程 i 退出临界区。

// 剩余区：线程 i 执行非临界区代码。

程序输出分析：

Peterson 算法保证了互斥性：只有一个线程能进入临界区，两个线程不会同时进入临界区。
死锁避免：通过 turn 变量的使用，确保没有线程因互相等待而永远阻塞。
饥饿避免：因为 turn 变量的轮换机制，确保了每个线程都会有机会进入临界区。

4. 用 fork 创建子进程的程序

题目：

写一个程序，完成以下功能：用 fork 创建子进程，若失败，输出 “failed”，程序退出；在子进程中输出 “child”；在父进程中等待子进程返回后，输出 “parent”。

参考答案：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>int main() {pid_t fpid;  // 定义进程号变量fpid = fork();  // 创建子进程if (fpid < 0) {  // fork 返回值小于 0 表示创建失败printf("failed\n");exit(-1);  // 退出程序} else if (fpid == 0) {  // fork 返回值等于 0 表示当前是子进程printf("child\n");} else {  // fork 返回值大于 0 表示当前是父进程wait(NULL);  // 等待子进程结束printf("parent\n");}return 0;
}

程序运行结果：