PV操作经典例题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

一、前言🚀🚀🚀

修BUG的程序员

二、正文☀️☀️☀️

1.有一阅览室，共有100个座位。读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。

在描述阅览室读者进程的同步问题时，我们需要确保在任何时候，座位的占用状态都被正确地反映出来，即当一个读者进入时，他们应该能够找到一个空座位并登记，而当他们离开时，他们应该注销自己的登记，以便其他读者可以使用该座位。

empty：表示空闲座位的数量。初始化为100，因为阅览室有100个座位。
mutex：用于保护对座位登记表的互斥访问。初始化为1，因为登记表在任何时候只能被一个读者访问。
semaphore empty = 100; // 空闲座位数量  

semaphore mutex = 1;   // 互斥信号量，保护登记表  
  
// 读者进程  
void reader_process() {  
    while (true) { // 假设读者进程不断循环  
        P(empty);   // 等待一个空闲座位（wait操作）  
        P(mutex);   // 请求对登记表的互斥访问  
          
        // 在这里登记座位和读者姓名  
        // ...  
          
        V(mutex);   // 释放对登记表的互斥访问（signal操作）  
          
        // 读者阅读...  
          
        P(mutex);   // 再次请求对登记表的互斥访问  
          
        // 在这里注销座位和读者姓名  
        // ...  
          
        V(mutex);   // 释放对登记表的互斥访问（signal操作）  
        V(empty);   // 释放一个座位（signal操作）  
          
        // 读者离开...  
    }  
}

在这个伪代码中，P操作（wait）用于等待信号量变为非零值，并将其减一。如果信号量的值为零，则P操作会阻塞，直到信号量的值变为非零。V操作（signal）用于将信号量的值加一，并唤醒等待在该信号量上的一个或多个进程（如果有的话）。

注意，由于登记表是共享的，我们需要使用mutex信号量来确保在任何时候只有一个读者可以修改它。这通过在修改登记表之前和之后分别执行P(mutex)和V(mutex)来实现。

此外，还要注意，虽然在实际应用中读者进程可能不会无限循环，但在这个例子中，我们假设它们会不断循环以简化描述。在实际应用中，读者进程可能会在阅读后终止，或者等待某个事件（如新的书籍到达）来触发它们再次进入阅览室。

2、有一只铁笼子，每次只能放入一只动物，猎手向笼子里放入老虎，农民向笼子里放入猪；动物园等待取笼子里的老虎，饭店等待取笼子里的猪。现请用wait和signal操作写出能同步执行的程序。

empty：表示笼子是否为空，初始化为1（因为开始时笼子是空的）。
tigerReady：表示笼子里是否有老虎准备好被取走，初始化为0
（因为开始时没有老虎）。
pigReady：表示笼子里是否有猪准备好被取走，初始化为0
（因为开始时没有猪）。

猎手

void hunter() {  
    while (true) {  
        // 假设这里猎手捕获了一只老虎  
        // ...  
  
        P(empty); // 等待笼子为空  
        // 将老虎放入笼子  
        // ...  
  
        V(tigerReady); // 标记老虎已准备好  
    }  
}

农民

void farmer() {  
    while (true) {  
        // 假设这里农民准备好了一只猪  
        // ...  
  
   P(empty); // 等待笼子为空  
        // 将猪放入笼子  
        // ...  
  
   V(pigReady); // 标记猪已准备好  
    }  
}

动物园

void zoo() {  
    while (true) {  
        P(tigerReady); // 等待老虎准备好  
        // 从笼子中取出老虎  
        // ...  
  
        V(empty); // 标记笼子为空  
    }  
}

这个设计确保了以下同步条件：

猎手只能在笼子为空时将老虎放入。
农民也只能在笼子为空时将猪放入。
动物园只能在老虎准备好时取出老虎。
饭店只能在猪准备好时取出猪。
每次取出动物后，笼子都被标记为空，以便下一个动物可以被放入。

需要注意的是，虽然这个程序模型可以同步地执行，但在实际应用中，我们还需要考虑错误处理、线程/进程间的通信机制（如果这是在多线程或多进程环境中实现的），以及可能的死锁或饥饿情况。此外，由于这是一个无限循环的模型，实际实现时可能需要某种形式的退出条件或中断机制。

3、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题

(1)用PV操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

(2)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

1. 为了用PV操作（也称为P操作和V操作，或wait和signal操作）来管理这些并发进程（购票者），我们需要定义一个信号量来控制售票厅内的购票者数量。这个信号量可以命名为sem_tickets。

semaphore sem_tickets = 20; // 初值为20，表示售票厅最多可容纳20名购票者

sem_tickets 的值大于0：表示售票厅内当前还可以容纳的购票者数量。
sem_tickets 的值为0：表示售票厅内已经满员，达到最大容纳量，外面的购票者需要等待。
sem_tickets 的值小于0（在PV操作下通常不会出现负值，但理论上如果发生超卖，可能会是负值）：表示售票厅外等待进入的购票者数量（绝对值）。但在正常情况下，我们通过合适的PV操作可以避免这种情况。

购票者进入售票厅的PV操作：

P(sem_tickets); // 等待sem_tickets大于0，然后将其减1  
// 进入售票厅购票  
...

购票者离开售票厅的PV操作：

V(sem_tickets); // 将sem_tickets加1，表示售票厅内空出一个位置

(2) 若欲购票者最多为n个人，信号量sem_tickets的可能变化范围如下：

最大值：n，表示售票厅的最大容纳量。
最小值：0，表示售票厅已满，没有空闲位置供新的购票者进入。
但是，考虑到可能有购票者在售票厅外等待，信号量的实际最小值可以是负数，其绝对值表示等待进入的购票者数量。但在正常情况下，我们不希望信号量出现负值，因为这可能表示发生了超卖或其他异常情况。因此，在正常情况下，信号量的变化范围是：

最大值：n
最小值：0

4.在这个问题中，我们需要通过信号量（Semaphore）和P（wait）、V（signal）操作来确保在任何时候，只有一名音乐爱好者能够同时拥有听音乐的三种必需品：随身听、音乐磁带和电池。由于酒吧老板一次只能出售两种物品，我们需要设置合适的信号量来同步这个过程。

tape_available：表示是否有音乐磁带可用，初始化为1（因为一开始酒吧里有音乐磁带）。
player_available：表示是否有随身听可用，初始化为1（因为一开始酒吧里有随身听）。
battery_available：表示是否有电池可用，初始化为1（因为一开始酒吧里有电池）。
listening：表示是否有人在听音乐，初始化为0（因为一开始没有人听音乐）。

音乐爱好者想要听音乐的步骤将涉及以下操作：

等待三种物品中的任意两种可用（假设他们每次来酒吧时只带了他们没有的物品）。
请求第三种物品。
开始听音乐，并设置listening为1表示正在听。
听音乐结束后，释放所有物品，并设置listening为0。

semaphore tape_available = 1;  
semaphore player_available = 1;  
semaphore battery_available = 1;  
semaphore listening = 0;  
  
void music_lover(int type) {  
    // type 表示音乐爱好者的类型：0 = 只有随身听, 1 = 只有磁带, 2 = 只有电池  
    int other_items = 0; // 用于记录已获取的物品数量  
  
    while (true) {  
        if (type == 0) { // 只有随身听  
            P(player_available);  
            if (tape_available.value > 0 && battery_available.value > 0) {  
                P(tape_available);  
                P(battery_available);  
                other_items = 2;  
            }  
        } else if (type == 1) { // 只有磁带  
            P(tape_available);  
            if (player_available.value > 0 && battery_available.value > 0) {  
                P(player_available);  
                P(battery_available);  
                other_items = 2;  
            }  
        } else if (type == 2) { // 只有电池  
            P(battery_available);  
            if (player_available.value > 0 && tape_available.value > 0) {  
                P(player_available);  
                P(tape_available);  
                other_items = 2;  
            }  
        }  
  
        if (other_items == 2) { // 确保了有三种物品  
            P(listening); // 确保没有其他人正在听音乐  
            // 听音乐...  
            // 听音乐结束  
            V(listening); // 释放听音乐信号  
  
            // 释放所有物品  
            V(player_available);  
            V(tape_available);  
            V(battery_available);  
            other_items = 0;  
        }  
  
        // 如果因为缺少其他物品而未能开始听音乐，则释放已获取的物品  
        if (other_items < 2) {  
            if (other_items & 1) { // 假设只获取了随身听或磁带  
                V(type == 0 ? player_available : tape_available);  
            }  
            if (other_items & 2) { // 假设只获取了电池  
                V(battery_available);  
            }  
        }  
    }  
}

注意：上述伪代码中有一些简化和假设，特别是关于other_items的处理和条件判断。在实际实现中，可能需要更复杂的逻辑来确保每次只释放正确的物品，并且需要处理所有可能的并发情况。此外，由于音乐爱好者可能会同时到达酒吧，因此可能还需要额外的同步机制来确保公平性和避免死锁。

5、某银行有人民币储蓄业务由n个柜员负责有1台取号机。每个顾客进入银行后先取一个号若有人取号则需等他人取完后才能取,取到号后等待叫号当一个柜员人员空闲下来就叫下一个号。试用P、V操作正确编写柜台人员和顾客进程的程序

semaphore mutex = 1;：用于控制对取号机的互斥访问，确保一次只有一个顾客可以取号。
semaphore queue = 0;：表示等待队列中的人数，初始为0，因为开始时没有顾客等待。每当一个顾客取号后，该信号量增加；每当一个柜员叫号后，该信号量减少。

顾客进程

procedure customer() {  
    P(mutex); // 请求对取号机的互斥访问  
    // 这里可以加入生成新号码的逻辑，但为了简化，我们假设号码是自动递增的  
    // 并且柜台系统已经维护了这个号码  
    print("Customer got a number");  
    V(mutex); // 释放取号机  
  
    P(queue); // 等待被叫号  
    print("Customer is being served");  
    // 模拟服务过程  
    // ...  
  
    // 服务完成，顾客离开  
}

柜员进程

procedure teller() {  
    while (true) {  
        // 柜员进行其他准备工作或等待  
        // ...  
  
        // 假设柜员已经准备好服务下一个顾客  
        if (顾客等待条件) { // 在实际中，这可能需要通过其他机制来检测，比如检查等待队列长度  
            V(queue); // 叫下一个号，让等待队列中的一个顾客得到服务  
            // 柜员开始为顾客服务  
            // ...  
  
            // 服务完成后，柜员回到等待下一个顾客的状态  
        }  
  
        // 可能还有其他的柜员任务  
        // ...  
    }  
}

注意：上述伪代码中的“顾客等待条件”是一个简化的说法，实际上柜员进程可能通过其他方式（如检查queue信号量的值）来决定是否应该叫号。然而，在标准的信号量用法中，queue的增加是由顾客进程通过P(mutex)后完成的，而减少（即叫号）是由柜员进程通过V(queue)完成的。

此外，如果银行系统需要跟踪具体的号码，那么可能还需要一个共享的全局变量（如current_number）来记录下一个将被叫到的号码，以及相应的同步机制来安全地更新这个变量。

三、总结🍓🍓🍓