网站的时间对齐应该怎么做,在线 建站单页面网站带后台,jsp网站开发流程,自己做网站怎么盈利目录
前言
逻辑时钟讲解
算法类比为面包店内取号
Lamport算法的时间戳原理
Lamport算法的5个原则
举例说明
算法实现
参考文献 前言 在并发系统中#xff0c;同步与互斥是实现资源共享的关键Lamport面包店算法作为一种经典的解决并发问题的算法#xff0c;它的实现原…目录
前言
逻辑时钟讲解
算法类比为面包店内取号
Lamport算法的时间戳原理
Lamport算法的5个原则
举例说明
算法实现
参考文献 前言 在并发系统中同步与互斥是实现资源共享的关键Lamport面包店算法作为一种经典的解决并发问题的算法它的实现原理和应用是每个探索并发控制的人必须要了解的知识点Dijkstra于1965年提出的基于共享存储的临界区互斥访问问题Dijkstra提出了基于对内存单元的原子性读写实现的方案然而Lamport指出Dijkstra的方案会因为节点在临界区内失效而导致系统死锁在其于1974年发表的文章A New Solution of Dijkstra’s Concurrent Programming Problem中Lamport提出了完全基于软件实现的解决方案被称为“面包店算法”Lamport面包店算法是一种经典的分布式系统中互斥访问共享资源的算法用来解决多个线程并发访问一个共享的单用户资源的互斥问题因其设计思想类似于面包店中取号排队的方式因此被称为面包店算法面包店算法模拟面包店内取号服务的模式实现了先来先服务的的互斥访问这个算法也可以称为时间戳策略或者叫做Lamport逻辑时钟 逻辑时钟讲解 这里先陈述一下这个逻辑时钟的内容是一种在分布式系统中对事件进行时间戳排序的方法在其中定义了因果关系称为before例如before在航班满员航班可预订这里“事件预订”before“航班满员”预订和满员就形成了因果关系现实世界中确定事件预订发生在事件满员之前需要预订发生在比满员更早的时间因果关系是一个事件因和第二个事件果之间的作用关系其中后一个事件被认为是前一个事件的结果一般来说一个事件是很多原因综合产生的结果而且原因都发生在较早的时间点而在分布式系统中有时不可能说两个事件中的一个首先发生关系“happened before”只是系统中事件的部分排序我们用分布式系统中的事件的先后关系用“-”符号来表示例如若事件a发生在事件b之前那么a-b该关系需要满足下列三个条件 1-如果a和b是同一进程中的事件a在b之前发生则a-b2-如果事件a是消息发送方b是接收方则a-b3-对于事件a、b、c如果有a-bb-c则有a-c注意对于任何一个事件aa-a都是不成立的也就是说关系-是反自反的有了上面的定义我们也可以定义出“并发”(concurrent)的概念了 对于事件a、b如果a-bb-a两个都不成立那么a和b就是并发的直观上上面的-关系非常好理解即“xxx在xxx之前发生”也就是说一个系统在输入I1下如果有a-b那么对于这个系统的同一个输入I1无论重复运行多少次a也始终发生在b之前如果在输入I1下a和b是并发的则表示在同一个输入I1下的不同运行中a可能在b之前也可能在b之后也可能恰好同时发生也就是说并发并不是指一定同时发生而是表示一种不确定性-和并发的概念就是我们理解一个系统时最基础的概念之一了有了上面的概念我们可以给系统引入时钟了这里的时钟就是lamport逻辑时钟一个时钟本质上是一个事件到实数假设时间是连续的的函数这个函数将每个事件映射到一个数字代表这个事件发生的时间形式一点来说对于每个进程Pi都有一个时钟Ci这个时钟将该进程中的事件a映射到Ci(a)对于一个事件b假设b属于进程Pj那么C(b)Cj(b)这里插一句从这个定义也可以看到大师对分布式系统的理解分布式系统中不存在一个“全局”的实体在该系统中每个进程都是一个相对独立的实体它们有自己的本地信息本地Knowledge而整个系统的信息则是各个进程的信息的一个聚合有了时钟的一个“本质定义”还不够我们需要考虑什么样的时钟是一个有意义的或者说正确的时钟其实有了前文的-关系的定义正确的时钟应满足的条件已经十分明显了时钟条件对于任意两个事件ab如果a-b那么C(a)C(b)注意反过来讲这个条件可不成立如果我们要求反过来也成立即“如果a-b为假那么C(a)C(b)也为假”那就等于要求并发事件必须同时发生这显然是不合理的结合前文-关系的定义我们可以把上面的条件细化成如下两条 1-如果a和b是进程Pi中的两个事件并且在Pi中a在b之前发生那么Ci(a)Ci(b)2-如果a是Pi发送消息mb是Pj接收消息m那么Ci(a)Cj(b)上面就定义了合理的逻辑时钟显然一个系统可以有无数个合理的逻辑时钟实现逻辑时钟也相对简单只要遵守两条实现规则就可以了 1-每个进程Pi在自己的任何两个连续的事件之间增加Ci值2-如果事件a是Pi发送消息m那么在m中应该带上时间戳TmCi(a)如果b是进程Pj接收到消息m那么进程Pj应该设置Cj为大于max(Tm,Cj(b))有了上面逻辑时钟的定义我们现在可以为一个系统中所有的事件排一个全序就是使用事件发生时的逻辑时钟读数进行排序读数小的在先当然此时可能会存在两个事件同时发生的情况如果要去除这种情况方法也非常简单如果a在进程Pi中b在进程Pj中Ci(a)Cj(b)且i j那么a在b之前形式化一点我们可以把系统事件E上的全序关系“”定义为假设a是Pi中的事件b是Pj中的事件那么ab当且仅当以下两个条件之一成立 1-Ci(a)Cj(b)2-Ci(a)Cj(b) 且 i j 算法类比为面包店内取号 Lamport把上面这些数理逻辑时钟的概念以非常直观地类比为顾客去面包店采购面包店只能接待一位顾客的采购step1已知有n位顾客要进入面包店采购安排他们按照次序在前台登记一个签到号码该签到号码逐次加1step2根据签到号码的由小到大的顺序依次入店购货step3完成购买的顾客在前台把其签到号码归0如果完成购买的顾客要再次进店购买就必须重新排队这个类比中的顾客就相当于线程而入店购货就是进入临界区独占访问该共享资源由于计算机实现的特点存在两个线程获得相同的签到号码的情况这是因为两个线程几乎同时申请排队的签到号码读取已经发出去的签到号码情况这两个线程读到的数据是完全一样的然后各自在读到的数据上找到最大值再加1作为自己的排队签到号码为此该算法规定如果两个线程的排队签到号码相等则线程id号较小的具有优先权进入临界区 已经拿到排队签到号码的线程要轮询检查自己是否可以进入临界区即检查n个线程中自己是否具有最小的非0排队签到号码或者自己是具有最小的非0排队签到号码的线程中id号最小的可以用伪代码表示上述检查 非临界区 一旦线程在临界区执行完毕需要把自己的排队签到号码置为0表示处于非临界区把该算法原理与分布式系统相结合即可实现分布式锁注意这个系统中需要引入时钟同步博主的意见是可以采用SNTP实现时钟同步非权威仅供参考 Lamport算法的时间戳原理 由部分排序可知问题的关键点在于节点间的交互要在事件发生顺序上达成一致而不是对于时间达成一致所以逻辑时钟指的是分布式系统中用于区分时间发生顺序的机制从某种意义上来讲现实世界的物理时间其实是逻辑时钟的特例分布式系统中按是否存在节点交互可分为三类事件节点内部发送事件接收事件每个事件对应一个Lamport时间戳初始值为0如果事件在节点内发生时间戳1如果事件属于发送事件时间戳1并在消息中带上该时间戳如果事件属于接收事件时间戳Max本地时间戳消息中的时间戳1 Lamport算法的5个原则 通过五条规则定义算法为了方便起见假设每个规则定义的操作形成单个事件 为了请求资源进程A发送消息(Tm:A)给所有的其他进程并且把这个消息放到进程队列中Tm是消息的时间戳当进程B接收到了进程A的(Tm:A)请求后会把它放到自己的请求队列然后发送一个带有时间戳的确认消息给A为了释放资源进程A移除所有(Tm:A)的请求消息然后发送带时间戳的A释放资源请求消息给其他所有的进程当进程B接收到进程A释放资源的请求它会移除队列中任意的(Tm:A)的请求资源当满足以下两个条件时进程A会被赋予资源 1-有一个(Tm:A)的请求按照关系排在队列第一位(它在队列中其他请求(为了定义我们定义一个消息使用发送消息的事件来识别))2-A接收到了一个时间戳大于Tm的来自所有其他进程的消息 举例说明 在下面这幅图中我们可以看到现在有三个进程请求临界资源分别是P1P2P3在P2时间戳33时时间戳1P2将34写入自己的队列P2发送request信号分别给三个进程 在P3时间戳38时P3收到P2的request信号将34写入自己的队列P3时间戳1向P2发送时间戳为39的reply信号 在P1时间戳40时P1时间戳1P1将41写入自己的队列P1发送request信号分别给三个进程此时P1还没有收到P2的请求信号 在P1时间戳42时P1收到P2的request信号将34写入自己的队列P1时间戳1向P2发送时间戳为43的reply信号 在P2收到其中一个进程的reply信号后因为队头是自己的时间戳所以P2进入临界区开始使用资源 在P3时间戳42时P3收到P1的request信号将41写入自己的队列P3时间戳1向P1发送时间戳为43的reply信号 在P2时间戳42时P2收到P1的request信号将41写入自己的队列P2时间戳1向P1发送时间戳为43的reply信号 在P2时间戳48时向其他两个进程发送release信号并将其在本地队列中释放也在其他队列中释放 现在我们可以通过这个时空图回顾一下上述过程 注意到在本地时间44P2或许开始使用资源因为它已经收到来自P1值为41的时间戳的消息比P2值为34的时间戳的需求消息更大此算法按照“发生在先”关系的顺序授予资源(无优先级倒置) 算法实现 定义 数组Choosing[i]为真表示进程i正在获取它的排队登记号数组Number[i]的值是进程i的当前排队登记号如果值为0表示进程i未参加排队不想获得该资源规定这个数组元素的取值没有上界正在访问临界区的进程如果失败规定它进入非临界区Number[i]的值置0即不影响其它进程访问这个互斥资源代码 细节讨论 每个线程只写它自己的Choosing[i]、Number[i]只读取其它线程的这两个数据项这个算法不需要基于硬件的原子(atomic)操作实现即它可以纯软件实现使用Choosing数组是必须的假设不使用Choosing数组那么就可能会出现这种情况 设进程i的优先级高于进程j(即ij)两个进程获得了相同的排队登记号(Number数组的元素值相等)进程i在写Number[i]之前被优先级低的进程j抢先获得了CPU时间片这时进程j读取到的Number[i]为0因此进程j进入了临界区随后进程i又获得CPU时间片它读取到的Number[i]与Number[j]相等且ij因此进程i也进入了临界区这样两个进程同时在临界区内访问可能会导致数据腐烂(data corruption)算法使用了Choosing数组变量使得修改Number数组的元素值变得“原子化”解决了上述问题具体实现时可以把上述伪代码中的忙等待(busy wait)换成交出线程的执行权例如yield操作 参考文献 Original PaperOn his publications pageLamport has added some remarks regarding the algorithm
