文档章节

lamport面包店算法简介

go4it
 go4it
发布于 2017/09/07 22:44
字数 1201
阅读 9
收藏 0
点赞 0
评论 0

Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。由莱斯利·兰波特发明。

算法类比

Lamport把这个并发控制算法非常直观地类比为顾客去面包店采购。

  • 面包店一次只能接待一位顾客的采购。
  • 已知有n位顾客要进入面包店采购,按照次序安排他们在前台登记一个签到号码。该签到号码逐次增加1。
  • 顾客根据签到号码的由小到大的顺序依次入店购货。
  • 完成购买的顾客在前台把其签到号码归0。如果完成购买的顾客要再次进店购买,就必须重新排队。

这个类比中的顾客就相当于线程,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点,存在两个线程获得相同的签到号码的情况,这是因为两个线程几乎同时申请排队的签到号码,读取已经发出去的签到号码情况,这两个线程读到的数据是完全一样的,然后各自在读到的数据上找到最大值,再加1作为自己的排队签到号码。

为此,该算法规定如果两个线程的排队签到号码相等,则线程id号较小的具有优先权。

原理

Lamport时间戳原理如下:

  • 每个事件对应一个Lamport时间戳,初始值为0
  • 如果事件在节点内发生,时间戳加1
  • 如果事件属于发送事件,时间戳加1并在消息中带上该时间戳
  • 如果事件属于接收事件,时间戳 = Max(本地时间戳,消息中的时间戳) + 1

5个原则

  • 为了请求资源,进程A发送消息(Tm:A)给所有的其他进程,并且把这个消息放到进程队列中,Tm是消息的时间戳
  • 当进程B接收到了进程A的(Tm:A)请求后,会把它放到自己的请求队列,然后发送一个带时间戳的确认消息给A
  • 为了释放资源,进程A移除所有(Tm:A)的请求消息,然后发送带时间戳的A释放资源请求消息给其他所有的进程
  • 当进程B接收到进程A释放资源的请求,它会移除队列中任意的(Tm:A)的资源请求
  • 当满足以下两个条件时,进程A会被分配该资源:
    • a)有一个(Tm:A)的请求,按照=>关系排在队列第一位;
    • b)A接收到了一个时间戳大于Tm的来自所有其他进程的消息

代码示例

private void processRevcMsg(Message m) throws InterruptedException {
        // 原理4 如果事件属于接收事件,时间戳 = Max(本地时间戳,消息中的时间戳) + 1
        clock.update(m.getTimestamp());
        lastSendMap.put(m.getFrom(), m);
        switch (m.getMsgType()) {
            case REQUEST_RES:
                // rule 2 当进程B接收到了进程A的(Tm:A)请求后,会把它放到自己的请求队列,然后发送一个带时间戳的确认消息给A
                addMessageToReqMap(m);
                Message ackMsg = new Message(pid, m.getMsgId(), MessageType.REQUEST_ACK, clock.time());
                // send ack to sender
                sendToTargetProcess(ackMsg,m.getFrom());
                break;
            case REQUEST_ACK:
                break;
            case RELEASE_RES:
                // rule 4 当进程B接收到进程A释放资源的请求,它会移除队列中任意的(Tm:A)的资源请求
                dropMessageFromReqMap(m);
                break;
            default:
                break;
        }
        tryToAcquireResource();
    }

    private void tryToAcquireResource() {
        synchronized (reqMap) {
            if(!reqMap.containsKey(pid) || reqMap.get(pid).isEmpty()){
                return ;
            }

            Message myMessage = reqMap.get(pid).get(0);
            int acceptCount = 1;

            // rule 5 当满足以下两个条件时,进程A会被分配该资源:a)有一个(Tm:A)的请求,按照=>关系排在队列第一位;b)A接收到了一个时间戳大于Tm的来自所有其他进程的消息

            // condition (ii) of rule 5
            // A接收到了一个来自所有其他进程的消息,而且时间戳大于Tm
            for (Map.Entry<Integer, Message> entry : lastSendMap.entrySet()) {
                if (entry.getKey() == pid) {
                    continue;
                }
                if (isFirstEarlier(myMessage, entry.getValue())) {
                    acceptCount++;
                }else{
                    return ;
                }
            }
            if (!coordinator.hasAcceptedAll(acceptCount)){
                return;
            }

            // condition (i) of rule 5
            // 有一个Tm:A的请求,按照=>关系排在队列第一位
            for (Map.Entry<Integer, List<Message>> entry : reqMap.entrySet()) {
                if (entry.getKey() != pid && !entry.getValue().isEmpty()) {
                    if (!isFirstEarlier(myMessage, entry.getValue().get(0))) {
                        return;
                    }
                }
            }

            // remove this request message
            final Message firstMsg = reqMap.get(pid).remove(0);
            workingPool.execute(new Runnable() {
                public void run() {
                    coordinator.acquire(firstMsg.getMsgId(), pid, firstMsg.getTimestamp());
                    // emulate owning resources for a long time
                    try {
                        Thread.sleep(50L);
                        // rule 3 为了释放资源,进程A移除所有(Tm:A)的请求消息,然后发送带时间戳的A释放资源请求消息给其他所有的进程程
                        coordinator.release(firstMsg.getMsgId(), pid, firstMsg.getTimestamp());
                        Message releaseMsg = new Message(pid, firstMsg.getMsgId(),MessageType.RELEASE_RES, clock.time());
                        sendToOtherProcesses(releaseMsg);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }

                }
            });
        }
    }

doc

© 著作权归作者所有

共有 人打赏支持
go4it
粉丝 50
博文 647
码字总数 438010
作品 0
深圳
分布式系统几种典型一致性算法简述

在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解。在思考和翻阅资料后,通俗地把一致性...

毛爷爷夸我帅 ⋅ 2016/05/05 ⋅ 0

操作系统复习笔记(一)

1.整型信号量是一个整数变量,除初始化外,对其只能执行两个操作,即wait(s)和signal(s),也叫p(s)和v(s)操作,均是原语操作,用来实现进程的同步,互斥. 2.记录型信号量 type semaphore = record ...

嗯哼9925 ⋅ 2017/12/27 ⋅ 0

Paxos分布式一致性算法简介和Apache ZooKeeper的概念映射

Paxos是一个基于消息传递的一致性算法,近几年被广泛应用于分布式计算中,Google的Chubby,Apache的Zookeeper都是基于它的理论来实现的,Paxos还被认为是到目前为止唯一的分布式一致性算法,...

foodon ⋅ 2014/12/16 ⋅ 2

mnesia里的lamport clock

mnesia使用"wait-die"机制预防死锁,"wait-die"是基于时间戳的,mnesia采用了lamport clock算法作为"wait-die"机制的时间戳。 Lamport clock是解决分布式系统中事件发生时序的一种方式。 La...

hncscwc ⋅ 2013/09/23 ⋅ 0

过年回家,如何告诉亲戚自己的工作真不是修电脑的

     作者:Mischa von Nachtigal   编译:萌艺、魏子敏   对大多数人来说,新年意味着和家人团聚、大餐、闲聊。而对于技术从业者,新年聚餐还意味着,家人对你工作的关心,以及在你...

大数据文摘 ⋅ 01/02 ⋅ 0

一致性算法探寻(扩展版)12

10 Related work There have been numerous publications related to consensus algorithms, many of which fall into one of the following categories: Lamport’s original description ......

戴的天 ⋅ 2015/08/12 ⋅ 0

互联网人回老家上餐桌,如何向亲戚朋友解释自己的工作?

编者按:对于互联网从业者来说,每次过节回老家都是一种煎熬。当老家的亲戚朋友问起工作来,自己根本解释不清,最后对方只淡淡地说一句“跟王二傻子一样,在工厂打工呗”,让人欲哭无泪。其实...

嘿你好夏天 ⋅ 2017/11/29 ⋅ 0

libQtCassandra 0.4.7 发布

libQtCassandra 0.4.7 包含一些小的 bug 修复和一个大的变革,Lamport bakery 算法实现了 Cassandra 锁。 libQtCassandra 是一个高级的 C++ 库用来访问 Cassandra 这个 NoSQL 服务器,使用 ...

oschina ⋅ 2013/01/28 ⋅ 0

互联网人回老家上餐桌,如何向亲戚朋友解释自己的工作?

做互联网?啥意思?反正就是跟王二傻子一样,在工厂打工呗? 编者按:对于互联网从业者来说,每次过节回老家都是一种煎熬。当老家的亲戚朋友问起工作来,自己根本解释不清,最后对方只淡淡地...

嘿你好夏天 ⋅ 2017/11/29 ⋅ 0

Paxos算法 -- 学习

Paxos算法解决的问题是保证分布式系统每次执行的操作强一致性。在其他文档也提到这个算法适合高带宽低延迟网络,如果是低带宽网络可以选择PNUTS模式 。每次执行Paxos算法都是相对独立的,Pax...

bobo_lin ⋅ 2012/07/24 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 17分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部