2024-05-17
藏龙卧虎
00
请注意,本文编写于 153 天前,最后修改于 148 天前,其中某些信息可能已经过时。

目录

简介
进程调度常见模式
先来先服务调度
短作业优先调度
优先级调度
时间片轮转调度
多级反馈队列调度
PV操作
定义
信号量
P操作
V操作
PV操作的工作流程
PV操作的应用
PV操作举例:同步模型
PV操作距离:异步模型
总结:PV操作
互斥(Mutual Exclusion)
同步(Synchronization)
异步(Asynchronous Execution)
事件通知(Event Notification)
资源计数(Resource Counting)
条件同步(Conditional Synchronization)
总结

简介

进程调度是一个操作系统中的重要部分,进程调度的方式一般决定了操作系统的性质。

进程调度是操作系统在多个进程之间分配CPU时间的一种机制。常见的进程调度模式包括以下几种:

  • 先来先服务调度(First-Come, First-Served, FCFS)
  • 短作业优先调度(Shortest Job Next, SJNShortest Job First, SJF)
  • 优先级调度(Priority Scheduling
  • 时间片轮转调度(Round Robin, RR)
  • 多级反馈队列调度(Multilevel Feedback Queue, MLFQ)

进程调度常见模式

先来先服务调度

  • 概念:按照进程到达的顺序进行调度,先到达的进程先分配CPU。
  • 优点:实现简单、公平。
  • 缺点:可能导致“短进程等待长进程”问题,即“等待时间长”(convoy effect),无法保证紧急进程的及时处理。

短作业优先调度

  • 概念:优先调度预计运行时间最短的进程。
  • 优点:减少平均等待时间。
  • 缺点:需要准确预测进程的运行时间,可能导致“饥饿”问题(长作业长时间得不到调度)。

优先级调度

  • 概念:根据进程的优先级进行调度,优先级高的进程先分配CPU。
  • 优点:可以保证重要任务的及时处理。
  • 缺点:可能导致低优先级进程“饥饿”问题,需要引入优先级提升机制。

时间片轮转调度

  • 概念:每个进程按照固定时间片轮流占用CPU。
  • 优点:公平、响应时间短,适合交互式系统。
  • 缺点:时间片大小的选择影响系统性能,时间片过大类似于FCFS,时间片过小则增加上下文切换的开销。

多级反馈队列调度

  • 概念:将进程放入多个队列,每个队列有不同的优先级和时间片,进程可以在队列之间动态调整。
  • 优点:兼顾公平性和响应时间,可动态调整优先级,适应多种工作负载。
  • 缺点:实现复杂,需要合理设置队列和调度策略。

PV操作

定义

PV操作 是一种用于进程同步的原语,由荷兰计算机科学家 Edsger Dijkstra 引入。PV操作主要用于信号量(Semaphore)的实现,信号量是一种用于控制对共享资源访问的同步机制。

信号量

  • 定义:信号量是一个整数,用于表示可用资源的数量。信号量可以是计数信号量(Counting Semaphore)或二进制信号量(Binary Semaphore)。
  • 类型:
    • 计数信号量:允许多个进程同时访问一定数量的资源。
    • 二进制信号量:类似互斥锁(Mutex),只有0和1两个值,用于实现互斥。

P操作

定义:P操作(Proberen,测试/减),P用于请求资源,将信号量的值减1。
语法:P(S),其中S是信号量。
代码解释:

c
void P(Semaphore S) { S.value--; if (S.value < 0) { // 将进程加入等待队列 block(); } }

V操作

定义:V操作(Verhogen,释放/加):用于释放资源,将信号量的值加1。
语法:V(S),其中S是信号量。
代码解释:

c
void V(Semaphore S) { S.value++; if (S.value <= 0) { // 唤醒等待队列中的一个进程 wakeup(); } }

PV操作的工作流程

  1. 请求资源(P操作):进程调用P操作尝试获取资源。如果信号量的值大于0,表示资源可用,信号量值减1,进程继续执行。如果信号量的值小于或等于0,表示资源不可用,进程被阻塞并加入等待队列。
  2. 释放资源(V操作):进程调用V操作释放资源。信号量的值加1。如果信号量的值小于或等于0,表示有进程在等待资源,从等待队列中唤醒一个进程。

PV操作的应用

PV操作广泛应用于解决经典同步问题,如:

  1. 生产者-消费者问题:通过信号量控制生产者和消费者对缓冲区的访问,避免缓冲区溢出和空转。
  2. 读者-写者问题:通过信号量实现读者和写者对共享资源的协调,确保数据一致性和并发性。
  3. 哲学家进餐问题:通过信号量控制哲学家对叉子的访问,避免死锁和资源争用。

PV操作举例:同步模型

同步模型中的PV操作常见应用场景:生产者-消费者问题:

一个工厂有多个生产者和多个消费者。生产者将生产的物品放入共享的缓冲区(如仓库),消费者从缓冲区取出物品进行加工。为了防止缓冲区溢出(生产者生产速度过快)或空转(消费者消费速度过快),需要使用PV操作进行同步。

PV操作在此场景中的作用:

  • P操作(wait, Proberen):在生产者尝试向缓冲区放入物品之前,执行P操作检查缓冲区是否有空闲空间(empty信号量),如果没有空闲空间,生产者将被阻塞,等待消费者取走物品释放空间。
  • V操作(signal, Verhogen):在消费者取出物品后,执行V操作通知缓冲区有空闲空间了(empty信号量),从而允许被阻塞的生产者继续生产并放入物品。

对于生产者来说:

  • P(empty):检查是否有空闲空间,如果没有空闲空间,生产者等待。
  • P(mutex):进入临界区,保证对缓冲区的操作是互斥的。
  • 向缓冲区放入物品。
  • V(mutex):离开临界区。
  • V(full):增加缓冲区已满物品的计数,通知消费者有新物品可取。

对于消费者来说:

  • P(full):检查是否有物品可取,如果没有物品,消费者等待。
  • P(mutex):进入临界区,保证对缓冲区的操作是互斥的。
  • 从缓冲区取出物品。
  • V(mutex):离开临界区。
  • V(empty):增加缓冲区空闲空间的计数,通知生产者可以放入新物品。

PV操作的作用:

PV操作在这个场景中确保了生产者和消费者对缓冲区的访问是协调的,防止缓冲区溢出或空转,从而实现同步操作。

PV操作距离:异步模型

我们以网络请求处理的过程来讲解PV操作在异步模型中的应用:

一个服务器处理多个客户端的网络请求。每个请求被放入一个请求队列中,由多个工作线程异步处理这些请求。为了确保请求队列的访问是安全的,并且工作线程不会在队列空时无谓地忙等待,需要使用PV操作进行同步。

PV操作在此场景中的作用:

  • P操作:工作线程在尝试处理请求之前,执行P操作检查请求队列是否为空(requests信号量),如果为空,工作线程将被阻塞,等待新的请求到达。
  • V操作:当新的请求到达时,执行V操作通知工作线程有新请求可处理(requests信号量)。

在网络请求中,当客户端请求到达时:

  • P(mutex):进入临界区,保证对请求队列的操作是互斥的。
  • 将请求放入队列。
  • V(mutex):离开临界区。
  • V(requests):增加请求队列中请求的计数,通知工作线程有新请求可处理。

实际工作线程处理请求:

  • P(requests):检查请求队列是否有请求,如果没有请求,工作线程等待。
  • P(mutex):进入临界区,保证对请求队列的操作是互斥的。
  • 从请求队列中取出请求。
  • V(mutex):离开临界区。
  • 处理请求。

PV操作的作用:

PV操作在这个场景中确保了工作线程对请求队列的访问是安全的,并且避免了队列空时工作线程的忙等待,从而实现异步操作的高效处理。

总结:PV操作

在各种不同的应用模型中,PV操作(信号量操作)在协调进程或线程的行为,保证资源的安全和高效利用方面起着重要作用。以下是PV操作在互斥、同步、异步等常见应用模型中的作用总结:

互斥(Mutual Exclusion)

作用:确保多个进程或线程在同一时间段内只能有一个能够访问共享资源,防止资源竞争和数据不一致。

  • P操作(wait):进程在进入临界区前执行P操作,如果信号量为0,进程阻塞,等待信号量大于0。
  • V操作(signal):进程离开临界区后执行V操作,增加信号量的值,通知等待队列中的一个进程可以进入临界区。

应用场景举例:

  • 多线程程序访问共享数据结构(如链表、队列、堆栈等)。
  • 文件系统中多个进程对同一文件的读写操作。

同步(Synchronization)

作用:协调多个进程或线程的执行顺序,确保它们按特定顺序或条件执行,解决生产者-消费者问题等经典同步问题。

  • P操作:在生产者向缓冲区放入物品之前,检查是否有空闲空间,若无空闲空间,生产者阻塞等待。
  • V操作:在消费者从缓冲区取出物品之后,增加空闲空间的信号量,通知生产者可以继续生产。

应用场景举例:

  • 生产者-消费者问题。
  • 读者-写者问题,确保读者和写者对共享资源的访问按特定顺序进行。

异步(Asynchronous Execution)

作用:处理异步事件和请求,确保事件或请求队列的安全访问,避免忙等待,提高资源利用率。

  • P操作:工作线程在处理请求之前,检查请求队列是否为空,若为空,线程阻塞等待新请求。
  • V操作:当新请求到达时,通知工作线程有新的请求可处理。

应用场景举例:

  • 多线程服务器处理客户端请求。
  • 事件驱动的系统,处理异步I/O操作。

事件通知(Event Notification)

作用:实现进程或线程之间的事件通知机制,确保在特定事件发生时通知相关进程或线程。

  • P操作:进程等待特定事件的发生,信号量为0时阻塞。
  • V操作:事件发生后,通知等待队列中的进程。

应用场景举例:

  • 多线程GUI应用程序,线程等待用户输入事件。
  • 操作系统中进程等待I/O完成事件。

资源计数(Resource Counting)

作用:管理和分配有限的资源,确保资源不被超额使用,控制资源的并发访问。

  • P操作:进程请求资源,检查资源是否可用,若资源不可用,进程阻塞。
  • V操作:进程释放资源,增加资源的信号量,通知等待的进程资源可用。

应用场景举例:

  • 数据库连接池管理。
  • 多任务操作系统中的设备资源管理。

条件同步(Conditional Synchronization)

作用:基于特定条件的同步机制,确保在特定条件满足时进程或线程继续执行。

  • P操作:进程等待条件满足,信号量为0时阻塞。
  • V操作:条件满足后,通知等待队列中的进程。

应用场景举例:

  • 线程池中工作线程等待任务队列中的任务。
  • 复杂工作流系统中的任务依赖管理。

总结

PV操作主要用于确保多进程或多线程环境下的资源安全、高效利用和执行顺序正确。在这些应用场景中,P操作用于等待和检查条件,而V操作用于通知和释放资源,二者共同协作实现进程或线程间的协调和同步。

如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:DingDangDog

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!