操作系统中的排队模型

2025年1月7日 | 阅读16分钟

操作系统中的排队模型用于分析、控制和优化系统中完成的任务的执行。这些模型利用排队论的思想，测量任务到达时间、服务周期和系统容量等参数，以帮助预测和优化性能。这些模型旨在减少延迟、最大化吞吐量并将资源有效地分配给等待队列中的任务。这些数学框架对于设计能够有效管理工作负载并确保在不同计算环境中正确维护最佳性能的健壮系统至关重要。

然而，我们可以观察到某个时间点上CPU突发和I/O突发的分布，并创建一个数学方法来识别正面CPU突发的可能性。同样，可以近似系统中文本的到达时间。使用数学模型分析各种系统的性能导致了排队概念的发展，这是算术的一个分支。

排队理论（模型）的基本思想等同于计算机机器的模型。每台 PC 机都描绘成一组具有自己队列的服务器，其中包括 CPU 和 I/O 设备。本文讨论了操作系统内的排队系统。

排队的需求

操作系统中排队模型的核心和必要性在于有效的任务和进程管理。

资源分配

CPU 时间、内存和 I/O 设备等资源是有限的。排队模型确保这些资产（资源）能够在相互竞争的进程和任务之间公平有效地分配。
需求：如果没有排队模型，作业可能会以无序的方式竞争资源，从而导致低效、延迟以及特定方法的资源短缺。

任务优先级排序

并非所有任务都是平等的。有些任务必须立即完成，而另一些则可以等待。排队模型提供任务优先级，确保关键任务（任务）能够快速处理。
需求：低优先级进程可能会在没有优先级的情况下垄断系统资源，从而导致高优先级和时间敏感方法出现延迟。

资源争用解决方法

复杂系统中的任务同时竞争多种资源，如 CPU 时间、内存和 I/O 系统。这些排队模型解决了任务（作业）获取所需资源的竞争条件。
需求：如果没有排队模型，资源争用可能会导致冲突、延迟和机器不稳定，从而导致应用程序失败或无响应。

多任务处理和并行处理

在现代计算环境中，必须同时运行多个任务。排队方法通过允许作业共享资源和并发执行来实现多任务处理。
需求：没有强大的排队模型，多任务处理和并行处理可能难以实现，从而限制了当前运行系统的能力。

死锁预防和解决

排队模型包含用于检测和解决死锁的方法，死锁发生在策略在等待资源时同时停滞时。它保持了机器的稳定性。
需求：死锁可能导致系统崩溃和无响应。排队模型对于阻止和减少这些关键问题至关重要。

系统稳定性和效率

排队模型有助于操作系统保持平均平衡和性能。它们避免了资源耗尽，并确保进程能够及时完成其生命周期。
需求：如果未使用合适的排队模型，操作系统可能会面临整体性能瓶颈、系统故障和意外行为的风险。

排队系统的组成部分

排队机器，称为排队模型或设备，由许多重要的添加剂组成，它们协同工作以控制和优化任务或实体通过设备执行。这些元素有助于有效和公平地完成任务。

到达过程（输入源）

到达过程表示任务或实体如何进入排队系统。它建立了新作业分配的模式和费用。到达技术可能是确定性的（在正常周期内发生到达）或随机的（根据概率分布出现到达）。

队列（等待线）

队列是任务等待CPU的区域。它是一种临时存储作业直到可以处理的设备。队列的数量大小和容量，并遵循“先进先出”（FIFO）概念，该概念规定先到达的作业（任务）先被服务。

服务器设施（服务器或服务器）

服务器设施是处理排队任务的速率。它表示任务所寻求的资源，例如 CPU、网络链接或客户支持人员。多个服务器可以并行运行以在许多排队结构中服务任务。

服务调度（调度策略）

系统字段，也称为调度策略或服务规则，定义了从队列中选择作业进行突发的顺序。先进先出 (FCFS)、轮转法、优先级调度和最短作业优先 (SJF) 是不常见的调度规则。突发区域的选择对机器性能有主要影响。

退出流程

退出过程指定了任务在被服务后移动到何处，以及任务（作业）如何离开队列系统。任务可能会退出设备，返回队列进行额外处理，或采取另一预设路径。

队列长度

队列持续时间是任何给定时间点队列中就绪的进程数量。长队列会导致延迟和资源竞争。因此，队列持续时间是重要的整体性能指标。

这些添加剂概述了整个排队系统的行为和性能。特殊排队系统可能具有卓越的特征和属性，具体取决于实用性和要求。分析和优化这些添加剂对于在包括计算机网络、客户服务中心、制造和交通运输在内的多个区域构建高效排队系统至关重要。

服务器数量

排队系统中的服务器数量是影响任务或实体如何处理以及系统运行效率的重要因素。服务器数量定义了可以同时处理多少作业。

单服务器（M/M/1）

在单服务器排队设备中，使用单服务器来处理作业。它表示为M/M/1，其中“M”表示马尔可夫（无记忆）到达过程，而“1”表示单服务器。
任务（作业）：在此设置中，任务是单独处理的；如果一个任务正在被服务，其他任务必须在队列中等待。服务器利用率至关重要，其值通常用 (rho) 表示。
优点：单服务器排队系统由于其简单性和易于评估，是模拟简单系统的流行选择。

多服务器（M/M/c）

在多个服务器排队系统中，有 c 个服务器来执行任务。它表示为M/M/c，其中“c”表示服务器的数量。
任务（作业）：多个服务器可以处理更多并发作业，从而导致更短的队列长度和等待时间。任务根据所选的调度策略分配给可用的服务器。
优点：多服务器可同时提高系统吞吐量，降低拥塞风险。它们适用于到达率更高且突发时间各不相同的情况。

无限服务器（M/M/*）

在无限服务器排队模型中，有无数服务器可用于处理任务。它表示为M/M/*。
任务（作业）：由于有数量众多的服务器，任务或可用的作业将不会在队列中等待。它们一到就立即处理，从而缩短等待间隔并减少拥塞。
无限服务器在到达率极高的情况下非常有用，例如计算机网络中的数据包处理，因为延迟是不可容忍的。

服务器计数可变性（M/M/c/c）

某些系统中的服务器数量可能取决于调用。这种服务器计数可变性可以表示为M/M/c/c，其中“c”表示可能可用的服务器的最大数量。
任务（作业）：服务器数量根据需求动态调整，确保在高峰和低谷时段实现高效、有用的资源利用。
优点：此方法通过减少低需求期间的利用不足并缓解高峰期间的拥塞来优化有用的资源分配。

排队机器中服务器的数量由特定要求、可用资源和预计作业到达模式决定。在设计高效排队系统时，应考虑高吞吐量、响应时间、资源利用率和系统稳定性等问题。

排队系统中的服务器数量由具体要求、可用资源和预期的作业到达模式决定。在设计足够的排队系统时，必须考虑目标吞吐量、响应时间、资源利用率和系统稳定性。

排队系统性能指标

排队系统或模型性能测量用于评估系统运行情况。以下是排队结构的一些流行性能指标：

利用率（ρ - Rho）

利用率是排队概念中的一个关键统计数据，它显示了排队设备中的服务器使用情况。它估计服务器用于处理作业的时间百分比，这对于评估设备性能和资源利用率至关重要。
利用率是一个无量纲的矩阵，表示排队系统中任务或实体的平均到达率（λ）与服务器的平均服务率（μ）之比。
公式：ρ = λ / μ
当利用率达到一时，服务器接近其最大能力。

平均等待时间

在排队理论中，平均就绪（等待）时间表示为W。它是关键的整体性能矩阵。它测量任务或实体在排队设备中被服务之前在队列中等待的平均次数。平均等待时间是系统如何管理任务到达和处理之间时间的关键矩阵。

公式：W=L/λ，其中 L 是平均队列长度，λ 是任务的平均到达时间。

平均等待时间在实际资源分配决策中很重要。它指导服务器或资源的分配，使您能够减少任务延迟。
等待时间受调度技术的影响，例如先进先出（FCFS）或优先级调度，具体取决于系统要求。

系统中的平均客户数量

排队理论中的另一个广泛指标是“系统中的平均客户数量”，通常表示为L。该指标估计任何时候排队系统中的平均作业或实体数量，包括正在被服务和正在队列（队列）中等待的。此矩阵对于分析系统效率、资源分配和性能很重要。

公式：L=λ⋅W，其中

λ 是任务的平均到达时间，W 是队列中的平均就绪时间。

任务到达时间、服务器的服务时间以及队列中的平均等待时间都会影响系统中的客户数量。

线中客户的平均数量

在排队理论中，“线中客户的平均数量”，通常缩写为L(q)，是一个广泛的整体性能矩阵。该矩阵估计任何时候排队系统中的平均作业或实体数量，特别是那些不在服务中的就绪队列中的实体。了解此统计数据对于分析排队系统效率、确定队列持续时间以及优化资源分配至关重要。

任务的到达时间、服务器的突发时间以及排队系统处理任务的效率都会影响L。
较高的到达时间、较长的等待周期或较慢的服务时间会导致更高的 L 值。

吞吐量

吞吐量是排队模型和系统分析中的一个关键指标。它测量排队设备在给定时期内处理、完成或服务任务或实体的速率。吞吐量是衡量设备效率和能力的重要指标。

吞吐量表示为吞吐量是排队设备在特定时间内有效接近或完成任务、客户或实体的速率。
X=λ-L，是任务的平均到达时间，L 是系统中任务的平均数量（包括队列中的任务和正在服务的任务）。
组织不断衡量和披露吞吐量，以确保设备的整体性能符合目标和需求。

响应时间

在排队概念和系统评估中，响应时间，也称为周期时间，是一项至关重要的整体性能参数。它测量任务或实体在排队模型中完成处理所需的时间，从进入设备到在队列中就绪、被服务以及退出队列。响应时间是系统效率和过程处理速度的全面指标。

等待时间（在队列中花费的时间）和突发时间（被服务的时间）是反应时间的两项基本功能。
通过减少等待时间和到达时间，可以实现更短的响应实例。
在排队系统中，最小化响应时间是一个典型的优化目标。策略示例包括优化调度方法、提高服务器潜力或调节项目到达模式。

队列符号

肯德尔符号

它通过一组符号来表示队列的各种属性。它由 3 个字母组成，每个字母代表队列的一个不同功能。第一个字母代表外观程序，第二个字母代表到达系统，第三个字母代表服务器数量。例如，M/M/1 队列包含泊松分布（由字母 M 表示）、指数突发时间分布（也由字母 M 表示）和一台服务器（由数字 1 表示）。

A/S/n 符号

在此符号中，A 表示到达间隔时间概率分布，S 表示突发时间分布，n 表示服务器数量。

这些符号广泛用于排队概念和分析，因为它们可以快速掌握队列的功能并选择合适的数学模型来表示和分析排队系统。

队列技术

队列规则或技术是定义队列中任务或实体选择 CPU 分配顺序的规则或技术。它们也称为调度规则或调度算法。队列规则通过管理作业通过排队系统的流程，对系统性能、公平性和响应能力有很大影响。

先进先出 (FCFS)

任务按到达顺序服务。
FCFS 简单易行。然而，它通常不会导致最有效的系统整体性能。它可能导致“队首”阻塞，即当一个大型系统导致其后任务延迟时。

后进先出 (LCFS)

LCFS 与 FCFS 完全相反。最后到达的任务首先被服务。
虽然 LCFS 在某些情况下可能有用，例如正面的笔记本电脑网络协议，但它不如 FCFS 常见。

最短作业优先 (SJF)

对于立即到达的作业，SJF 选择突发时间最短的作业。它试图减少等待时间并提高系统性能。

优先级调度

每个任务都被分配一个优先处理时间，用于使用优先级调度。优先级任务优先于低优先级任务。
优先级调度可以确保关键任务立即得到处理，但如果管理不当，也可能导致低优先级作业饿死。

轮转法

在轮转法调度中，任务按周期性结构处理，每个任务获得预定的服务时间片（量子），然后移至队列中的下一个任务。
RR 通常用于分时系统，可能提供公平的资源访问；然而，对于具有不同服务时间要求的任务，它可能不是最有效的。

优先队列

优先队列为不同的优先级级别维护单独的队列，允许优先任务首先得到服务。
此技术允许任务优先级灵活，通常用于实时系统和社区游客管理。

多级反馈

多级反馈队列是一种多级队列，其中作业可以根据其行为在队列之间移动。需要大量 CPU 时间的任务可能会被移至低优先级队列。

使用的队列区域决定了排队系统的具体目标和追求。每个系统或模型都有优点和缺点。

排队模型

[M/M/1]: //FCFS 队列系统

M/M/1:FCFS 队列系统是一个排队模型技术，包含两个基本要素：M/M/1 排队模型和 FCFS（先进先出）队列调度。

M/M/1 排队模型是一个传统的排队模型，包含以下组件：

“M”表示马尔可夫（无记忆）到达系统，通常建模为泊松过程。它描述了任务或实体如何随时间进入系统。
“M”表示马尔可夫（无记忆）服务系统，通常用指数分布表示。它表示一旦任务开始，服务所需的时间。

数字“1”表示处理角色的单个服务器。
主要功能包括：
到达间隔时间呈指数分布（任务到达之间的时间长度）。
突发时间呈指数分布（完成任务所需的时间）。
一个单独的服务器按 FCFS 顺序执行作业。
有可能有无限的队列用于等待完成的作业。
M/M/1: FCFS 队列系统结合了 M/M/1 排队范例和 FCFS 队列主题。
任务通过具有指数到达间隔的泊松过程输入系统。
任务到达时间呈指数计算，任务在单个服务器上按到达顺序处理。
当服务器忙碌时任务到达，它会被排队并在 FCFS 顺序中被服务。
可以使用各种分析技术计算这些矩阵，包括排队方程、马尔可夫链分析，甚至数值方法。在M/M/1 排队模型案例中，可以获得这些测量的封闭式解决方案，这使得评估非常简单。
可以通过改变到达时间、突发时间或服务器数量来优化M/M/1: FCFS 队列系统的性能，以满足正面的性能目标。
排队概念提供了用于计算和优化系统整体性能指标的分析技术。

[M/M/1]: N//FCFS 系统（队列长度有限系统）

[M/M/1]: N//FCFS 系统，通常称为有限队列长度系统，是 M/M/1 排队模型的一个版本，它采用 FCFS（先进先出）队列区域。在此模型中，排队系统具有有限的队列长度，表示为“N”，这意味着设备最多只能在队列中容纳一定数量的任务。

“M”表示马尔可夫（无记忆）到达系统，它描述了任务或实体如何随时间到达系统，并经常被建模为泊松过程（分布）。
“M”表示马尔可夫（无记忆）服务系统，通常表示为指数分布，它表示一旦任务开始，服务所需的时间。
术语“1”表示处理任务的单个服务器。
指数到达间隔、指数服务实例、单个服务器和可能无限的队列长度都是关键因素。
在[M/M/1]:N//FCFS 系统中，任务按照到达顺序服务，如同常规 FCFS 队列系统一样，遵循“先进先出”原则。
当作业到达系统且队列未满时，它被完成。如果队列已满，则根据系统规则拒绝或重定向任务。
具有最大容量为“N”个作业的有限队列的存在是[M/M/1]: N//FCFS 的一个区别。当队列已满时，传入的作业可能会被拒绝或遭受其他待遇，例如丢失或重路由。
队列持续时间受设备缓冲传入作业的能力限制。
为了满足某些性能需求，可以通过改变到达时间、服务速率、服务器数量或队列长度来优化 [M/M/1]: N//FCFS 设备。整体性能。
排队概念提供了用于计算和优化设备性能指标的分析方法。
由于系统资源有限，计算这些性能指标可能需要比 M/M/1 版本更棘手的分析方法。

M/D/1 队列

M/D/1 队列模型描述了一个具有单个服务器(1)、可预测的突发时间(D)和马尔可夫（无记忆）到达技术的排队系统(M)。此排队模型是更传统的M/M/1范例的简化变体，其到达实例与指数分布相反，是确定性分布的。

到达过程（M）

M/D/1 队列模型中的到达过程是马尔可夫的，这表示任务到达是无记忆的。此到达技术通常建模为泊松过程（分布）。
泊松过程描述了具有固定平均到达率(λ)的随机到达。

服务时间 (D)

与到达实例遵循指数分布的M/M/1模型不同，M/D/1 模型中的到达实例是可预测的。这表明每个任务完成所需的时间相同。
恒定时间 (d) 表示确定性到达时间。

M/D/1 架构经常解决先进先出 (FCFS) 队列字段。任务按照接收顺序完成，遵循“先进先出”方法。

M/D/1 排队模型应用于任务实例被认为是常规和确定性的情况，重点是了解设备行为，包括：

固定时间信息传输网络。
生产操作中的稳定周期实例。
执行定期或计划任务的系统。

M/M/c 队列

M/M/c 队列模型是一个著名的排队系统，它说明了任务或实体通过泊松过程(M)到达系统，由 'c' 个相同服务器(c)服务，并且任务（作业）具有指数分布的到达实例(M)，平均服务率为(λ)。此技术可用于分析多服务器系统的整体性能。

到达时间（M）

M/M/c 队列的到达过程遵循泊松分布，这是一种无记忆过程，具有稳定的平均到达率(λ)。
泊松技术模拟了随时间变化的随机到达。

服务时间（M）

M/M/c 模型中的到达时间遵循指数分布，该分布也是无记忆的，并且具有平均突发时间(μ)。
服务器实例是一个服务器完成一项操作所需的时间。

服务器数量

M/M/c 中的“c”表示可以同时处理工作的相同服务器的数量。
多个服务器的可用性允许并行工作，提高系统容量并减少等待时间。

队列调度

M/M/c 模型通常遵循先进先出 (FCFS) 队列调度，其中任务按照它们到达的顺序处理，遵循“先进先出”原则。

M/M/c 队列比 M/M/1 队列更复杂的模型，并且整体性能测量是通过许多近似和数值技术计算的。此外，当服务器数量很多时，就像许多商业和电信系统中一样，该系统可以建模为 M/M/c 队列。

结论

作为一个科学框架，排队模型使公司能够做出数据驱动的决策，以提高系统整体性能，减少等待时间，并优化资源分配。排队概念为分析和改进实时系统提供了多种工具，无论是在呼叫中心、制造流程、计算机网络还是客户服务中心。它使公司和机构能够提供更高效、响应更快的服务，从而使客户受益。

下一个主题Tenex-operating-system