互斥算法的性能指标

---

互斥是一个程序对象，它与以下条件相关：不允许两个并发进程同时处于同一临界区。它用于防止发生竞争条件。如果当前进程正在访问临界区，则它会阻止其他并发进程进入该区域。简而言之，在任何一个时刻，只有一个进程被授权执行临界区。

互斥的性能指标有哪些？

程序对象互斥描述了不允许两个并发进程同时在一个临界区中执行的需求。它被提出用于服务于竞争环境。如果当前进程正在使用临界区，则其他并发进程无法访问它。换句话说，在任何一个时刻，只有一个进程被允许执行临界功能。

执行分布式互斥的通用方法

基于令牌的技术

基于令牌的方法通过站点共享一个特殊的授权（也称为权限消息）。只要站点拥有令牌，就可以访问其临界区，并在临界区完成之前保留令牌。由于令牌是唯一的，因此可以确保互斥。从这个角度来看，算法与网站提供搜索令牌的方式有着根本的不同。在令牌环算法中，令牌在进程或线程的环形结构中依次传递。只有拥有令牌的进程或线程才能访问共享资源。集中式令牌算法利用中央机构来处理令牌分发。分布式令牌算法以去中心化的方式在进程或线程之间分发令牌。

非基于令牌的技术

为了选择哪个站点将接下来到达临界区，站点之间至少需要发送两轮增量通信。当由其本地写入器声明的公告发生时，站点进入临界区。基于仲裁的方法 - 在基于仲裁的策略中，每个站点都必须获得一个站点的重要子集（称为仲裁）的批准。当两个站点同时请求访问临界区时，仲裁旨在确保在任何一个时刻只有一个请求填充临界区。

四个指标

为了评估互斥扩展中指标的成功，可以使用许多性能指标。此数字表示程序尝试访问必须从磁盘调入的页面的次数，因为该页面实际上不在内存中。如果页面失效率过高，则系统可能花费过多的时间将页面交换进出内存，这可能会影响系统性能。以下是互斥扩展的指标。

消息复杂度

通过网站完成 CS 所需的消息数量。消息复杂度表示可以在任何给定边缘上传输的最大消息数。分布式算法的时间复杂度通常定义为直到最终节点完成该过程的轮数。

同步延迟

站点离开 CS 到下一个站点到达 CS 之间的时间间隔。同步延迟被测量为平均消息延迟 T [8]，并且是站点离开 CS 到下一个站点加入 CS 之间的时间间隔。存在基于令牌或非基于令牌的分布式互斥算法。

响应时间

发送查询消息到 CS 后完成请求所需的时间。响应时间包括提交请求、在计算机中处理请求以及将结果发送回终端所需的时间。反应时间通常用于评估智能系统的性能。

系统效率

（CS）是系统满足需求的速率。必须构建操作系统以允许快速开发、测试和实施新的系统功能，同时保持服务。

低负载和高负载性能

负载由完成关键部分的传入请求数表示。低负载发生在每个关键区域有多个请求时。当持续存在挂起的请求时，就会发生高负载。如果发生高负载，则在请求完成后，站点会立即开始操作以满足下一个关键需求。在高负载条件下，目标仅在极少数情况下处于非活动状态。简单的数学推理可用于有效地记录几种互斥算法在低负载和高负载下的性能测量结果。总的来说，低负载和高负载性能指标对于评估系统或应用程序的可靠性和有效性都至关重要，因为它们阐明了系统在各种使用场景下的运行方式以及如何对其进行优化以适应不断增长的需求。

互斥的要求

不应该有死锁：站点不应该无限期地等待挂起的消息到来。

没有饥饿

需要一个阈值，低于该阈值，一个站点不能重复运行临界区，而另一个站点则等待而不执行临界区。

容错

它应该自动识别自己的故障，并继续操作，几乎没有中断。操作系统对硬件或软件故障做出响应的过程称为容错。根据此定义，容错是指系统即使在出现错误或故障时也能继续运行的能力。

指标对互斥的有效性有什么影响？

互斥算法通常提供最优和最差性能特征。在最佳情况下，增益条件有利，使得性能指标达到最大值。大多数常见禁止计算的最佳反应时间估计是 2T E-返回消息延迟以及关键段执行时间。在互斥算法中，最佳和最差情况通常分别对应于低负载和高负载。例如，当负载极低和极高时，可以分别获得最佳和最差响应时间；在某些互斥算法中，当负载极低和极高时，可以分别创建最佳和最差消息流量。所选指标会极大地影响互斥算法的有效性。

例如，如果指标侧重于减少系统的平均响应时间，则互斥方法可能会优先考虑快速锁定获取。这可能会导致争用增加，并且某些进程的等待时间更长。另一方面，如果指标侧重于最大化吞吐量，则互斥方法可能会优先考虑允许更多进程同时进入其临界区，这可能会导致更多冲突和更长的总执行时间。

结论

互斥算法几乎总是提供最优和最差性能的指标。在最佳情况下，获胜条件非常有利，使得关键性能指标达到最大值。正在处理对关键部分的访问请求。在非基于令牌的方法中，时间戳的顺序很重要。因此，确保了公平性。在与基于令牌的算法相比时，它们在交互中的公平性。非基于令牌的算法需要消息。没有完美的算法，因为每个算法都有优点和缺点。它不是基于令牌的，因此不需要令牌来访问 CS。这种方法被称为基于权限的算法。