深入探讨操作系统进程管理：同步互斥与高并发问题解析（下篇）

投资移民2024-11-19 10:43:38金太阳移民

深入探讨操作系统进程管理：同步互斥与高并发问题解析（下篇）

其实深入探讨操作系统进程管理：同步互斥与高并发问题解析（下篇）的问题并不复杂，但是又很多的朋友都不太了解，因此呢，今天小编就来为大家分享深入探讨操作系统进程管理：同步互斥与高并发问题解析（下篇）的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！

看一下：进程通信和——管道通信的例子。

进程通信-管道通信

读过程和写过程同时进行。由于并发必然导致异步，因此“写数据”和“读数据”这两个操作的执行顺序是不确定的。实际应用中，必须按照“写入数据——读取数据”的顺序执行。如何解决这个异步问题，就是《进程同步》中讨论的内容。

同步也称为直接限制关系，是指两个或多个进程之间为完成某项任务而建立的限制关系。这些流程需要在某些位置协调其工作顺序。进程之间的直接制约关系源于进程之间的相互配合。

进程互斥

进程的“并发”需要“共享”的支持。每个并发执行的进程不可避免地需要共享一些系统资源（例如内存，以及打印机和相机等I/O设备）。

有两种分享方式：

互斥共享模式：虽然系统中的某些资源可以提供给多个进程，但在一段时间内只允许一个进程访问该资源；同时共享模式：系统中的某些资源允许在一段时间内被多个进程“同时”访问。我们将一段时间内只允许一个进程使用的资源称为关键资源。许多物理设备（例如相机和打印机）都是关键资源。此外，还有许多变量、数据、内存缓冲区等都是关键资源。

对关键资源的访问必须是互斥的。互斥关系，又称间接限制关系。进程互斥是指当一个进程访问某个关键资源时，另一个想要访问该关键资源的进程必须等待。当前正在访问关键资源的进程在其他进程可以访问该关键资源之前结束其访问并释放该资源。

临界区的互斥访问

对关键资源的互斥访问在逻辑上可以分为以下四个部分：

对关键部分的互斥访问

临界区是进程中访问临界资源的代码段。入口区和出口区是负责实现互斥的代码段。临界区域也可以称为“临界部分”。

有一个问题：如果一个进程暂时无法进入临界区，那么该进程是否应该一直占用处理器呢？有没有可能进程永远无法进入临界区？

为了在保证系统整体性能的同时实现对关键资源的互斥访问，需要遵循以下原则：

有空的时候让进来。当临界区空闲时，可以立即允许请求进入临界区的进程进入临界区；如果忙，就会等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；有限的等待。对于请求访问的进程，应保证其能够在有限的时间内进入临界区（保证其不会饿死）；让右边等待。当进程无法进入临界区时，应立即释放处理器，防止进程忙等待。概括

进程互斥的软件实现方法（很多，可以跳过）

进程互斥的软件实现

“单标法”

算法思路：两个进程访问临界区后，会将使用临界区的权限转移给另一个进程。也就是说，每个进程进入临界区的权限只能由另一个进程授予。

单标法

说明：turn的初始值为0，即一开始只允许0号进程进入临界区。如果P1先在处理器上运行，就会一直卡在5，直到P1的时间片用完，才会发生调度，切换到P0上的处理器运行。代码1不会卡在P0上，P0可以正常访问临界区，当P0正在访问临界区时立即切换回P1，P1仍然会卡在5上。只有当P0在退出区变为1后，P1能否进入临界区。

缺点：只能通过按P0 ->P1 ->P0 ->P1 ->. 依次访问它。这种必要的“回合访问”带来的问题是，如果进程允许进入临界区此时是P0，而P0从来没有访问过临界区，那么虽然此时临界区是空闲的，但是不允许P1访问它。

因此，单标方式的主要问题在于：违反了“自由进入”的原则。

《双标检验法》

算法思路：设置一个布尔数组flag[]。数组中的每个元素用于标记每个进程是否愿意进入临界区。例如“flag[0]=true”表示0号进程P0现在要进入临界区。每个进程在进入临界区之前，首先检查是否有其他进程想要进入临界区。如果不是，则将其相应的标志flag[i]设置为true，然后开始访问临界区。

双标法

缺点：如果按照152637.的顺序执行，P0和P1会同时访问临界区。因此，双标志先检查方法的主要问题是：违反了“先忙后等待”原则。原因是“检查”和“锁定”入口区域这两个过程并不是一次性完成的。 “检查”之后，可能会在“锁定”之前发生进程切换。

《双标事后检验法》

算法思想：双标记优先检查方法的修改版本。前一种算法的问题在于，它先“检查”，然后“锁定”，但这两个操作不能一次完成，这就导致了两个进程同时进入临界区的问题。因此，人们也想到了先“加锁”，再“检查”的方法来避免上述问题。

双标后检查法

如果按照1526.的顺序执行，P0和P1都无法进入临界区。因此，双标志后检查方式虽然解决了“忙时等待”的问题，但却违反了“自由进入”和“有限等待”原则，会因为每个进程都无法访问而造成“饥饿”现象两个进程都在竞争进入临界区，但最终都没有进入临界区。

《彼得森算法》算法思想：结合了双标记法和单标记法的思想。如果双方都在争夺进入临界区，可以让进程尝试“孔融让位”（谦让）。制定一个礼貌的流程。

彼得森算法

谁最后说出“最善意的话语”，谁就失去了采取行动的优先权。 eg: 过年了，某阿姨会给你压岁钱。阿姨：乖，接受你的愿望吧~你：不用了，阿姨，我接受你的愿望。阿姨：对阿姨来说，你还是个孩子，就接受吧。结束.

Peterson算法采用软件方法解决进程互斥问题，遵循空闲时让步、忙时等待、有限等待三个原则，但仍然没有遵循让步和等待原则。

Peterson的算法相比之前的三个软件解决方案来说是最好的，但仍然不够好。

进程互斥软件实现总结

进程互斥-中断屏蔽方法的硬件实现

进程互斥的硬件实现方法

《中断屏蔽方法》

中断屏蔽方法

优点：简单高效

缺点：不适用于多处理器；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，如果用户随意使用这组指令将是非常危险的）

进程互斥的硬件实现-TestAndSet指令

“测试并设置命令”

简称TS指令，有的地方也称为TestAndSetLock指令，或者TSL指令。 TSL指令是在硬件中实现的。执行过程不允许被中断，只能一次性完成。下面是用C语言描述的逻辑：

TestAndSet 指令

解释：如果一开始lock为false，那么TSL返回的旧值就是false，不满足while循环条件，所以直接跳过循环，进入临界区。如果一开始lock为true，则执行TLS后old返回的值为true。如果满足while循环条件，就会继续循环，直到当前访问临界区的进程在退出区域被“解锁”。

与软件实现方式相比，TSL指令将“锁定”和“检查”操作变成了硬件中的一站式原子操作。

优点：实现简单，不需要像软件实现方法那样严格检查是否存在逻辑漏洞；它适用于多处理器环境

缺点：不满足“给予和等待”原则。暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，导致“忙等待”。

进程互斥的硬件实现-Swap指令

“交换命令” 有些地方也称为交换命令，简称XCHG命令。 Swap指令是用硬件实现的，执行过程不允许中断，只能一次性完成。下面是用C语言表达的逻辑：

交换命令

从逻辑上来说，Swap 和TSL 没有太大区别。他们都记录此时临界区是否已经被锁定（记录在old变量中），然后将锁定标志lock设置为true，最后检查old。如果old 为false ，则说明之前没有其他进程锁定过临界区，因此可以跳出循环，进入临界区。

优点：实现简单，不需要像软件实现方法那样严格检查是否存在逻辑漏洞；它适用于多处理器环境

缺点：不满足“给予和等待”原则。暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，导致“忙等待”。

进程互斥的硬件实现

JAVA 并发包 CAS 实现

《JAVA并发包CAS实现，Swap指令的利用》

CAS的底层实现离不开处理器的支持。 C++的底层代码，其实核心代码就是一条带有lock前缀的cmpxchg指令，即lock cmpxchg dword ptr [edx], ecx。

交换指令：CMPXCHG、XCHG

用于比较和交换操作数，CPU 对CAS 的原始支持是非原子的，并且首先用于单核CPU。

用于交换两个操作数。它是原子的，CPU会自动添加LOCK前缀。

锁前缀：

作用：CPU保证其修改的指令的原子性。实现依赖内存排序模型来确保读指令是有序的；通过总线锁或缓存一致性，保证修改指令操作的数据一致性：当访问的数据在系统内存中时，通过总线锁实现原子性；当访问的数据在处理器的缓存中时，通过缓存一致性协议实现原子性；

举个栗子：

volatile关键字有两个作用，一是保证线程可见性，二是禁止指令重排序。如果Java的DCL中返回的变量没有用volatile修饰，那么另一个线程可能会因为指令重排而获得一个未完全初始化的对象。

当易失性修饰的变量所在代码段成为热点并被JIT编译成汇编代码时，会添加LOCK前缀，以禁止指令重排，保证数据一致性；具体细节可以参考一篇博文“https://www.cnblogs.com/ITPower/p/13580691.html”

信号量机制

这个信号量非常抽象。到底是什么？

“什么是信号量”

信号量就是在互斥区域门口放置一个盒子。盒子里装有固定数量的小球。每个线程来的时候，都会从盒子里取出一个小球，然后去互斥区挥手。当你高兴的时候，把球放回盒子里。如果一根线过来并接触到盒子，则不会留下任何球。如果你不拿球，就不让进去。那么你只能站在门口，等一根线出来，放回一个球，然后再进去。这样，由于数量小球是固定的，互斥区域的最大线程数也是固定的，不会出现一次性进入的线程太多而导致互斥区域拥挤的情况。这是使用信号量来限制并发。在其他情况下，球是一次性的。当线拿走一个球并进入门时，它就会扔掉球。这样，球用完就没了。然而，其他一些线程（一般称为生产者）会时不时地来回往盒子里多放几个球，以便新的线程（一般称为消费者）可以进入。将球放入线程中是信号量同步功能。这就是生产者-消费者模型。

信号量实际上是一个变量（可以是整数或结构体）。可以使用信号量来表示系统中某种资源的数量。例如，如果：系统中只有一台打印机，则可以设置一个初始值。信号量为1。

《信号量的实现》

当我们前面讨论过程控制时，我们花了很多时间讨论原语。信号量机制利用原始操作。前面我们看进程互斥的软件实现时，各种编码方式、各种名称，其实主要是因为读写操作不是原子操作。由于原语可以保证原子操作，所以在这里使用它们会更好。但仅此而已。

一对原语： wait(S) 原语和signal(S) 原语。原语可以理解为我们自己写的函数。函数名称分别为wait 和signal。括号中的信号量S实际上是调用时传递的函数。一个输入参数。

《信号量函数》

信号量可以实现互斥、进程同步和进程前驱关系。一个信号量对应一个资源。

信号量的值=该资源的剩余数量（如果信号量的值小于0，则说明此时有进程在等待该资源）； P(S)——申请一个资源S，如果资源不够，则阻塞等待； V(S)—— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程；信号量可以实现互斥、进程同步、进程前驱关系。以前驱关系的实现为例：

过程P1中有语句代码S1，P2中有语句代码S2，P3中有语句代码S3……，P6中有语句代码S6。这些代码需要按照以下前驱图：所示的顺序执行

信号量控制过程的前驱关系

代码实现如下：

信号量控制过程的前驱关系代码实现

每个进程都需要申请和释放自己相应的资源。

信号量解法生产者-消费者问题信号量解法多生产者-多消费者问题信号量解法哲学家就餐问题信号量解法读者-写下这个问题

管程

《为什么引入监视器》

信号量机制的问题：编程困难，容易出错；进程提供自己的同步操作，P(S)和V(S)操作大量分散在各个进程中，管理困难，容易出现死锁。

能否设计一种机制，让程序员在写程序时不再需要关注复杂的PV操作，让写代码变得更加简单？

1973年，Brinch Hansen首次在编程语言（Pascal）中引入了“管道”组件：一种先进的同步机制。

《工艺定义和基本特征》

引用专业书籍：中对监视器的介绍，当使用监视器实现进程同步时，当某个进程通过监视器请求关键资源但无法满足时，监视器调用wait原语让进程等待，并进入等待队列。只有当另一个进程完成访问并释放资源后，监视器才会调用信号原语来唤醒等待队列中的领导进程。然而，考虑一种情况：当进程调用监视器时，它会在监视器中被阻塞或挂起，直到阻塞或挂起的原因被消除为止；在此期间，如果进程不释放监视器，其他进程将无法进入管进程，被迫等待很长时间。为了解决这个问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件（原因）可能有多种，因此在monitor进程中设置多个条件变量，并在monitor进程中智能地执行对这些条件变量的访问。

来自维基百科的简单定义：监视器（英语：Monitor，又称监视器）是一种程序结构，该结构内的多个子程序（对象或模块）形成的多个工作线程对共享资源具有互斥的访问权限。这些共享资源通常是硬件或一组变量。监视器意识到，在同一时刻，最多有一个线程正在执行监视器的某个子例程。与通过修改数据结构实现互斥访问的并发编程相比，监视器的实现很大程度上简化了编程。

监视器提供了一种机制，线程可以暂时放弃互斥访问，等待满足某些条件，然后重新获得执行权以恢复其互斥访问。

监视器仅保证同一时刻只有一个进程在监视器中处于活动状态，即监视器中定义的操作仅被一个进程（由编译器实现）同时调用。然而，这并不能保证该过程将按照设计进行。它是顺序执行的，所以需要设置条件变量，让进入监视器而不能继续执行的进程阻塞自己。

监视器是由这些部分组成的特殊软件模块：

监视器本地共享数据结构的描述；一组对数据结构进行操作的过程；为监视器本地共享数据设置初始值的语句；显示器有一个名字。管材工艺的基本特点：

监视器本地的数据只能由监视器本地的进程访问；进程只需调用监视器内的过程即可进入监视器访问共享数据；同一时间进程中只允许一个进程执行监视器内的内部函数。《监视器如何解决互斥和同步问题》

监视器如何解决互斥和同步问题：

互斥问题：

tube进程是互斥的，tube进程提供了一个入口等待队列：它存储等待进入synchronized代码块的线程； tube进程的互斥是由编译器保证的。同步问题：在监视进程和等待/唤醒操作中设置条件变量来解决同步问题。

条件变量（Java中理解为锁对象本身）等待操作：允许进程和线程对条件变量进行等待（此时应先释放监视器的使用权，否则其他线程和进程将得不到使用权）；将线程存储在条件变量的等待队列中。信令操作：还可以通过发送信号来唤醒等待条件变量的进程和线程（唤醒等待队列中的线程）

synchronized 底层原理-管程

synchronized是语法糖，会被编译器编译成：1monitorenter和2个monitorexit（正常退出1个，异常退出1个）。正常退出的monitorenter和monitorexit之间就是synchronized包裹的代码。

调用代码

Java对象和监视器关联图

Synchronized 是一个重量级锁，它存储指向监视器的指针。 Monitor（又称为监视器），在Java中是ObjectMonitor（在JVM源码中用C++实现）来实现监视器。

底层同步

同步内部实现流程：

想要获取监视器的线程首先进入监视器的_EntryList队列并阻塞等待。即遇到synchronized关键字时。如果监视器的_owner 为空，则会将其从队列中删除并为其分配_owner 的值。如果程序中调用了wait()方法，线程就进入_WaitSet队列。注意，我们之前已经讨论过wait 方法。它会释放monitor锁，即将_owner赋值为null，进入_WaitSet队列进行阻塞等待。此时_EntryList中的其他线程就可以获取锁了。当程序中的其他线程调用notify/notifyAll方法时，_WaitSet中的一个线程会被唤醒，这个线程会再次尝试获取监视器锁。如果成功，您将成为显示器的所有者。当程序遇到synchronized关键字的作用域结束时，会将监视器的所有者设置为null并退出。调用的方法自然就是monitor提供的方法，如下所示：

管道提供的方法

死锁

什么是死锁

在并发环境中，进程相互竞争资源、等待对方资源，导致所有进程都被阻塞而无法前进的现象，就是“死锁”。发生死锁后，如果没有外部干预，这些进程将无法继续进行。

死锁、饥饿、死循环的区别

死锁、饥饿和死循环的区别

死锁产生的必要条件

要产生死锁，必须同时满足以下四个条件。只要任一条件不成立，就不会发生死锁。

互斥条件：只有争用必须互斥使用的资源才会导致死锁（如哲学家的筷子、打印机设备）。内存、扬声器等可供多个进程同时使用的资源不会造成死锁（因为进程不需要阻塞等待此类资源）。非剥夺条件：进程获得的资源在用完之前不能被其他进程强行夺走，只能主动释放。请求和保留条件：进程已经维护了至少一个资源，但是提出了新的资源请求，并且该资源被其他进程占用。此时，请求进程被阻塞，但无法维护其现有资源。放。循环等待条件：进程资源存在循环等待链。链中每个进程获得的资源同时被下一个进程请求。

死锁的处理策略

三种策略：

防止死锁。打破僵局的四个必要条件中的一个或多个。避免死锁。使用某种方法阻止系统进入不安全状态，从而避免死锁的检测和释放（银行家算法）。死锁是允许发生的，但是操作系统会负责检测死锁的发生，然后采取一些措施来解除死锁。

预防死锁

防止死锁

使用SPOOLing 技术将您的打印机转变为共享设备.

打印机- 破坏互斥条件

核心是破坏产生死锁的四个必要条件中的一个或多个。

避免死锁-银行家算法

我们看一个借钱的例子：

你是一个成功的银行家，手里有100亿的资金……有3家公司想向你贷款，分别是B公司、A公司、T公司，为了方便，简称为BAT。 B 表示： “兄弟，我最多向你借70 亿.” A 表示： “兄弟，我最多向你借40 亿.” T 表示： “兄弟，我最多借5亿……”然而……世界上有一条不成文的规定。如果你借给公司的总金额没有达到公司的最高要求，那么无论你之前借给公司多少钱，你都无法拿到这笔钱。我回来了……当初BAT三家公司分别向你借了20亿、10亿、30亿……

一开始

第二步，如果BAT再借30亿，就不安全了……那么手里就只剩下10亿了。如果BAT要求再借20亿，那么没有一家公司能够满足其需求。满足.如下：

步骤2

这肯定行不通。这不是银行家，这是马达哈。

《安全顺序》

此场景涉及安全序列。

所谓安全顺序是指如果系统按照这个顺序分配资源，每个进程都能顺利完成。只要能找到安全序列，系统就处于安全状态。当然，可以有多个安全序列。如下图所示，借钱达到安全序列：

安全借钱

第二步，借给A 20亿是安全的，因为存在T->B->A这样的安全顺序。

《银行家算法》

银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时不会无法满足所有客户的需求。这个算法后来被用在操作系统中以避免死锁。

:的核心思想是，当进程申请资源时，首先预测该分配是否会导致系统进入不安全状态。如果会进入不安全状态，则暂时不接受请求，进程会先阻塞等待。

在BAT的例子中，只有一种资源，——美元，但是计算机系统中会有多种资源。算法应该如何扩展以使用多种资源？

示例：单维数字可以扩展为多维向量。例如，系统中有5个进程P0~P4，3种资源R0~R2，初始编号为(10,5,7)，那么某一时刻的情况可以表示为如下：

银行家算法

此时一共分配了(7,2,5)，还剩下(3,3,2)。最大需求和分配的数据可以看作一个矩阵。通过两个矩阵相减，我们可以计算出每个进程需要的最大资源数。

经过比较，发现(3,3,2)可以满足P1和P3，说明无论怎样，这两个进程的资源需求必须依次满足，所以P1和P3一定能够成功执行，并且资源回来了。 P1和P3可以先添加到安全序列中。

银行家算法- 资源要求

(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)，其余P0、P2、P4均可满足。同样，可以将这些进程添加到安全序列中。因此，五个进程都被添加到安全序列中，说明此时系统处于安全状态，暂时不太可能发生死锁。

银行家算法步骤：

检查此时系统剩余可用资源是否还能满足该请求，并进行暂定分配。改变每个数据结构，并使用安全算法来检查这种分配是否会导致系统进入不安全状态。安全算法步骤：

检查当前剩余可用资源是否能够满足进程的最大需求。如果是，则将该进程添加到安全序列中，并回收该进程所持有的所有资源。重复上述过程，看看是否所有进程最终都能加入到安全序列中。

死锁的检测和恢复

不会尝试防止死锁，而是在检测到死锁时采取措施进行恢复。

检测为了检测系统是否发生死锁，

使用一定的数据结构来保存资源请求和分配信息；提供一种算法，利用上述信息来检测系统是否进入了死锁状态。每种类型一种资源的死锁类型

上图是资源分配图，其中方框代表资源节点，圆圈代表进程节点。进程节点向资源节点请求资源；资源指向进程表示资源已经分配给进程，进程指向资源表示进程请求获取。这个资源。

图a可以提取出循环，如图b所示，满足循环等待条件，所以会出现死锁。

每种资源的死锁检测算法都是通过检测有向图中是否存在环来实现的。从一个节点开始，进行深度优先搜索，并标记访问过的节点。如果访问了标记的节点，则说明有向图中存在环，即检测到死锁的发生。

使用与此类似的算法进行检测。当然，在实际实现中，还会有比这更强大的检测算法。

解除死锁的主要方法有：

资源剥夺法。挂起（暂时放到外部内存上）一些死锁进程，抢占其资源，并将这些资源分配给其他死锁进程。但是，您应该防止挂起的进程长时间没有资源而处于饥饿状态。撤消进程方法（或终止进程方法）。强制取消部分甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现起来简单，但付出的代价可能会很高。因为有些进程可能已经运行了很长时间，已经接近结束。一旦终止，他们就会失败并必须重新开始。进程回滚方法。让一个或多个死锁进程充分后退以避免死锁。这就需要系统记录进程的历史信息并设置还原点。上期推荐： 1.操作系统内存管理，高能警告！ 2.操作系统的文件管理，一切皆文件！ 3、操作系统的进程管理（第1部分），无论研究多少并发，都比吃操作系统进程好！

文章参考：网道老师操作系统

如果你还想了解更多这方面的信息，记得收藏关注本站。

404 Not Found

深入探讨操作系统进程管理：同步互斥与高并发问题解析（下篇）

进程互斥

临界区的互斥访问

进程互斥的硬件实现-TestAndSet指令

进程互斥的硬件实现-Swap指令

JAVA 并发包 CAS 实现

信号量机制

管程

synchronized 底层原理-管程

死锁

什么是死锁

死锁、饥饿、死循环的区别

死锁产生的必要条件

死锁的处理策略

预防死锁

避免死锁-银行家算法

死锁的检测和恢复

相关问答

相关推荐