网工 进程管理

进程管理中的死锁是指两个或更多进程相互等待对方释放资源，从而导致所有进程都无法继续执行的情况。为了避免或解决死锁问题，操作系统通常采用预防、避免、检测和恢复等策略。

死锁的四个必要条件

死锁的发生必须满足以下四个必要条件：

  1. 互斥条件：至少有一个资源必须被独占使用。
  2. 请求与保持条件：一个已经保持至少一个资源的进程可能请求新的资源。
  3. 不可抢占条件：已经分配给进程的资源不能被抢占，只能由拥有进程显式释放。
  4. 循环等待条件：存在一个进程-资源的环形链。

总结:系统中有N个并发进程，若规定每个进程需要申请R个某类资源，则当系统提供K=N*(R-1)+1个同类资源时，无论采用何种方式申请使用，一定不会发生死锁。

如果是3各进程请求2个资源时，则至少需要3*（2-1）+1 =4

死锁的处理策略

处理死锁的策略通常包括预防、避免、检测和恢复四个方面：

  1. 预防：
    • 通过破坏上述四个必要条件之一来预防死锁的发生。
    • 例如，可以采用以下方法：
      • 破坏互斥条件：不太实用，因为许多资源必须独占使用。
      • 破坏请求与保持条件：进程一次性请求所有资源。
      • 破坏不可抢占条件：允许资源被抢占。
      • 破坏循环等待条件：通过资源分配图或资源编号来避免循环等待。
  2. 避免：
    • 在分配资源之前，先检查资源分配是否会导致死锁。
    • 使用安全算法来判断分配资源后系统是否处于安全状态。
    • 例如，银行家算法就是一个经典的资源分配算法，它可以确保系统始终处于安全状态。
  3. 检测：
    • 定期检查系统是否处于死锁状态。
    • 使用资源分配图来检测是否存在死锁环路。
    • 如果检测到死锁，需要采取措施来解决。
  4. 恢复：
    • 一旦检测到死锁，需要采取措施来解除死锁。
    • 方法包括：
      • 剥夺资源：从一些进程中剥夺资源分配给其他进程。
      • 撤销进程：终止一些进程以释放其占用的资源。
      • 回退：让进程回退到之前的状态，释放一些资源。

死锁处理示例

假设我们有两个进程 P1 和 P2，它们分别需要获取资源 R1 和 R2。P1 先获取 R1，然后尝试获取 R2，而 P2 先获取 R2，然后尝试获取 R1。这样就形成了一个死锁环路。

预防策略示例

  • 如果采用一次性请求所有资源的策略，那么 P1 和 P2 都需要在启动时请求所有需要的资源。如果资源不可用，则进程等待，直到所有资源都可用为止。

避免策略示例

  • 使用银行家算法来分配资源。在资源分配之前，检查分配资源后系统是否仍然安全。如果安全，则分配资源；如果不安全，则拒绝分配。

检测和恢复策略示例

  • 定期检查资源分配图是否存在环路。如果检测到死锁，可以选择撤销进程 P1 或 P2，或者从其中一个进程中剥夺资源来打破环路。

总结

  • 预防：通过破坏死锁的必要条件之一来避免死锁。
  • 避免：在分配资源之前检查是否会导致死锁。
  • 检测：定期检查系统状态，以确定是否存在死锁。
  • 恢复：一旦检测到死锁，采取措施解除死锁状态。

进程的PV操作是用于同步进程间通信的一种机制，也称为信号量机制。PV操作是由荷兰计算机科学家Edsger W. Dijkstra提出的，其中P操作（Proberen，尝试）用于请求资源，V操作（Verhogen，增加）用于释放资源。PV操作主要用于解决进程间的同步问题，尤其是临界区问题。

信号量的概念

信号量是一个整型变量，它用来表示资源的数量或状态。信号量的值可以是非负数，也可以是负数。信号量的值大于0表示资源可用，小于0表示等待资源的进程数量。

PV操作的定义

  • P操作：尝试获取资源。P操作会将信号量减1。如果信号量变为负数，则进程进入阻塞状态，等待资源可用。
    • 如果S > 0，则S = S – 1，进程继续执行。
    • 如果S ≤ 0，则将进程的状态置为等待状态，并将其插入到信号量S的等待队列中。
  • V操作：释放资源。V操作会将信号量加1。如果信号量为负数，则唤醒等待队列中的一个进程。
    • 如果S < 0，则从S的等待队列中唤醒一个进程。
    • 如果S ≥ 0，则S = S + 1。

PV操作的应用

PV操作可以用于解决多种同步问题，包括但不限于：

  1. 临界区问题：
    • 临界区是指进程中访问共享资源的那段代码。
    • 使用信号量和PV操作可以确保一次只有一个进程访问临界区。
    • 通常使用一个初始值为1的信号量S来实现互斥访问。
  2. 生产者-消费者问题：
    • 生产者进程生成数据并放入缓冲区，消费者进程从缓冲区中取出数据。
    • 使用两个信号量：一个表示缓冲区中可用数据的数量（initially 0），另一个表示缓冲区中可用空间的数量（initially buffer size）。
    • 生产者在生产数据前执行P操作（尝试获取空闲空间），在生产数据后执行V操作（释放空间）。
    • 消费者在消费数据前执行P操作（尝试获取数据），在消费数据后执行V操作（释放数据）。
  3. 读者-写者问题：
    • 多个读者可以同时读取共享资源，但写入时不允许其他读者或写者访问。
    • 使用两个信号量：一个用于控制写者（initially 0），另一个用于控制读者的数量（initially 0）。

示例代码

下面是一个使用PV操作解决临界区问题的简单示例：

import threading

# 创建一个信号量
semaphore = threading.Semaphore(1)

def critical_section():
    semaphore.acquire()  # P操作
    # 执行临界区代码
    print(f"{threading.current_thread().name} is in the critical section.")
    semaphore.release()  # V操作

def process_function():
    # 其他非临界区代码
    critical_section()
    # 其他非临界区代码

# 创建多个线程
threads = []
for i in range(5):
    thread = threading.Thread(target=process_function)
    threads.append(thread)
    thread.start()

# 等待所有线程完成
for thread in threads:
    thread.join()

总结

PV操作是实现进程间同步的重要手段，通过信号量和P/V操作可以有效地解决临界区问题、生产者-消费者问题等多种同步问题。在现代操作系统中，PV操作被广泛应用于多线程编程和并发控制中。

示例

1、某企业生产流水线M 共有两位生产者，生产者甲不断地将其工序上加工的半成品放入半成品箱，生产者乙从半成品箱取出继续加工。假设半成品箱可存放n 件半成品，采用PV 操作实现生产者甲和生产者乙的同步可以设置三个信号量S、S1 和S2，其同步模型如下图所示

信号量S 是一个互斥信号量，初始值为（22）；S1、S2 的初始值分别为（23）

这里成品箱看作控制信号量（互斥信息号量）其初始值为1 ，s1,s2的初值分别为n 和0 。

2、假设系统中有n个进程共享3台打印机，任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制n个进程使用打印机，则相应信号量S的取值范围为____(1)____；若信号量S的值为-3，则系统中有____(2)____个进程等待使用打印机。 

在使用PV（也称为P和V，或者wait和signal）操作来同步进程对共享资源（如打印机）的访问时，信号量是一个非常重要的工具。信号量可以用来确保多个进程不会同时访问同一资源，从而避免冲突。

信号量 S 的取值范围

我们有3台打印机，所以信号量 S 的最大值应该是3，表示所有打印机都可用。当一个进程开始使用打印机时，它会执行P(S)操作，这将使信号量的值减1。当进程完成并释放打印机时，它会执行V(S)操作，这将使信号量的值加1。

因此，信号量 S 的取值范围取决于以下几个因素：

  1. 所有打印机都没有被使用时，S = 3。
  2. 当所有打印机都被占用且还有进程在等待时，S 的值会变为负数，其绝对值表示正在等待的进程数量。

如果没有任何进程在等待，也没有任何打印机被占用，那么S = 3。如果有1台打印机被占用，那么S = 2；如果有2台打印机被占用，那么S = 1；如果有3台打印机都被占用但没有进程等待，那么S = 0。如果已经有进程开始等待，那么S 的值就会小于0，每多一个等待的进程，S 的值就减少1。

所以信号量S 的取值范围为3，2，1，0，-1，…-（n-3)

信号量 S 取 -3 的含义

如果信号量 S 的值是 -3，这意味着所有的3台打印机都被占用了，并且除了已经占用打印机的进程外，还有3个额外的进程正在等待使用打印机。因此，此时有3个进程正在等待。

Table of Contents

→ Index