Peterson算法:一种形象的分析

2023-10-19 06:50

本文主要是介绍Peterson算法:一种形象的分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Peterson算法

      • 在学习算法前的一些基础
        • 1. PeterSon算法是干什么的?
        • 2. PeterSon算法的实现(可以先不看)
      • 证明算法满足互斥、前进、有限等待要求
        • 1.首先我们考虑只用令牌不用登记簿的情况
        • 2. 我们再考虑只有登记簿的情况
        • 3. 同时存在令牌和登记簿的方案(即Peterson算法)
          • 互斥性证明
          • 前进性证明
          • 有限等待证明

在学习算法前的一些基础

1. PeterSon算法是干什么的?
  • PeterSon算法是基于软件的临界区问题的解答
  • 并且,所有临界区问题的解答必须满足三项要求:互斥、前进、有限等待
  • PeterSon算法适用于两个进程在临界区和剩余区交替执行。
2. PeterSon算法的实现(可以先不看)

首先,Peterson算法需要在两个进程 P 1 P_1 P1 P 2 P_2 P2之间共享两个数据项

int turn; // 令牌,值为1或2,表示哪个进程可以进入临界区
boolean flag[2];//登记簿,数组,flag[i]==true表示进程Pi想要进入临界区

PeterSon算法中, P i P_i Pi的结构

do{flag[i] = TRUE;turn = j;while(flag[j] && turn == j);//临界区flag[i] = FALSE;//剩余区
}while(TRUE);

PeterSon算法中, P j P_j Pj的结构

do{flag[j] = TRUE;turn = i;while(flag[i] && turn == i);//临界区flag[i] = FALSE;//剩余区
}while(TRUE);

证明算法满足互斥、前进、有限等待要求

1.首先我们考虑只用令牌不用登记簿的情况

在这里插入图片描述
在理想情况下,假设进程 P i P_i Pi首先获得令牌,正好进程 P i P_i Pi也要进入临界区,执行完之后运行turn = j,把令牌给 P j P_j Pj。如此循环往复。

但是,这个算法不符合上述三原则中的前进原则。考虑这样一种情况,进程 P i P_i Pi(左边)获得了令牌,即 P i P_i Pi可以进入临界区。但是它不想进(不执行代码),一直拿着令牌不给进程 P j P_j Pj,这会导致临界区没有进程执行时, P j P_j Pj想进入临界区却不被允许。

这种问题可以比喻为房客A和B,只有一间公共厕所(临界区)。两个人只有一把钥匙(令牌)。当A有钥匙时,可以打开厕所门,处理完之后把钥匙再给B。但是,A有时候拿到钥匙却不想上厕所,这是B想去却没有钥匙。

2. 我们再考虑只有登记簿的情况

在这里插入图片描述
在理想情况下,如果进程 P i P_i Pi想要申请进入临界区,就令自己的登记簿flag[i] = true。这是查询是否flag[j] = true,如果进程 P j P_j Pj的登记簿为true,就表示进程 P j P_j Pj仍在临界区执行。进程 P i P_i Pi等待,直到flag[j] = false,进程 P i P_i Pi进入临界区,执行完代码后把自己的登记簿改为false。如此循环往复。

但是,如果进程 P i P_i Pi和进程 P j P_j Pj同时申请进入临界区,那么就会出现flag[i] = true且flag[j] = true的情况,即两进程互相“谦让”,陷入无限循环之中,出现临界区没有进程执行,但却有进程想要进入临界区的情况,不符合前进原则

还是那两个房客,两人发现钥匙没用之后,决定在厕所门上放两个牌子(登记簿),如果牌子正面朝外(表示对应的人在里面),如果反面朝外则表示没有人。在绝大多数时候,这种方案可以正常执行。如果A想去上厕所,会先把自己的牌子正面朝上,之后看B的牌子,如果B在里面则等待,B出来之后,会翻一下自己的牌子,A见B的牌子反面朝外,则进门上厕所。

直到有一天,A和B想要同时上厕所,都把自己的牌子翻到正面朝外,两人面面相觑,互相谦让,都想让对方先上厕所。如此循环往复,两人一直都上不了厕所。

3. 同时存在令牌和登记簿的方案(即Peterson算法)

在这里插入图片描述

互斥性证明

以进程 P i P_i Pi为例,如果进程 P i P_i Pi想要进入临界区,只有flag[j] = false或turn = i的时候,进程 P i P_i Pi才被允许进入。当进程 P i P_i Pi进入临界区后,flag[i] = true,进程 P j P_j Pj无法进入临界区。

另一种情况,进程 P i P_i Pi P j P_j Pj同时想要进入临界区,flag[i]和flag[j]都为true,但turn只能是i或j,即一个确定的值。也就是说,两个while必定存在一个在无限循环,另一个则不执行,while不执行的进程可进入临界区。

于是,在任何情况下,最多只有一个进程在临界区执行,满足互斥要求

前进性证明

前进性在两个进程的情况下,即证明两进程不会陷入无限循环,互相等待对方。且只有一种陷入无限循环的方法,即两个while同时在无限循环。但这是不可能的,turn这个变量无法同时为i和j,即总有一个进程可以进入临界区,满足前进性要求

有限等待证明

即证明如果进程 P i P_i Pi申请进入临界区,那么进程 P j P_j Pj就不能从临界区出来再进去出来再进去出来再进去。
证明:假设进程 P i P_i Pi的while在循环,进程 P j P_j Pj在临界区执行,当进程 P j P_j Pj出来后,flag[j] = false。同时,进程 P i P_i Pi以光速进入临界区,不给进程 P j P_j Pj再次进去的机会,满足有限等待要求

房客A和B这次决定将钥匙和牌子同时使用,与只使用牌子不同的时,这次他们每次上厕所之前,都会把钥匙给对方。且只有钥匙不在自己手里,自己的牌子正面朝外时,才可以上厕所。

考虑第一种情况的问题,如果A想上厕所,且自己没有钥匙,且B不在厕所里(B的牌子反面朝外),则可以上厕所。如果A想上厕所,钥匙在自己手里,那么便把钥匙给B,只要B不在厕所里面,A同样可以进去,解决了只有钥匙时的问题。

考虑第二种情况,A和B同时想要上厕所,都把自己的牌子翻了过来,当他们正想要互相谦让时,发现钥匙要么在A手上,要么在B手上,那么没有钥匙的一方就可以进入厕所。

这篇关于Peterson算法:一种形象的分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/238053

相关文章

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

java -jar命令运行 jar包时运行外部依赖jar包的场景分析

《java-jar命令运行jar包时运行外部依赖jar包的场景分析》:本文主要介绍java-jar命令运行jar包时运行外部依赖jar包的场景分析,本文给大家介绍的非常详细,对大家的学习或工作... 目录Java -jar命令运行 jar包时如何运行外部依赖jar包场景:解决:方法一、启动参数添加: -Xb

Apache 高级配置实战之从连接保持到日志分析的完整指南

《Apache高级配置实战之从连接保持到日志分析的完整指南》本文带你从连接保持优化开始,一路走到访问控制和日志管理,最后用AWStats来分析网站数据,对Apache配置日志分析相关知识感兴趣的朋友... 目录Apache 高级配置实战:从连接保持到日志分析的完整指南前言 一、Apache 连接保持 - 性

Linux中的more 和 less区别对比分析

《Linux中的more和less区别对比分析》在Linux/Unix系统中,more和less都是用于分页查看文本文件的命令,但less是more的增强版,功能更强大,:本文主要介绍Linu... 目录1. 基础功能对比2. 常用操作对比less 的操作3. 实际使用示例4. 为什么推荐 less?5.

spring-gateway filters添加自定义过滤器实现流程分析(可插拔)

《spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔)》:本文主要介绍spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔),本文通过实例图... 目录需求背景需求拆解设计流程及作用域逻辑处理代码逻辑需求背景公司要求,通过公司网络代理访问的请求需要做请

Java集成Onlyoffice的示例代码及场景分析

《Java集成Onlyoffice的示例代码及场景分析》:本文主要介绍Java集成Onlyoffice的示例代码及场景分析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 需求场景:实现文档的在线编辑,团队协作总结:两个接口 + 前端页面 + 配置项接口1:一个接口,将o