文档章节

lamport面包店算法简介

go4it
 go4it
发布于 2017/09/07 22:44
字数 1201
阅读 12
收藏 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
粉丝 70
博文 819
码字总数 691271
作品 0
深圳
私信 提问
分布式系统几种典型一致性算法简述

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

毛爷爷夸我帅
2016/05/05
110
0
操作系统复习笔记(一)

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

嗯哼9925
2017/12/27
0
0
Paxos分布式一致性算法简介和Apache ZooKeeper的概念映射

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

foodon
2014/12/16
0
2
过年回家,如何告诉亲戚自己的工作真不是修电脑的

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

大数据文摘
01/02
0
0
mnesia里的lamport clock

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

hncscwc
2013/09/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Impala和Hive集成Sentry、Kerberos认证

关于 Kerberos 的安装和 HDFS 配置 kerberos 认证,请参考 HDFS配置kerberos认证。 关于 Kerberos 的安装和 YARN 配置 kerberos 认证,请参考 YARN配置kerberos认证。 关于 Kerberos 的安装和...

hblt-j
11分钟前
0
0
Ubuntu 18.04 PostgreSQL 11 apt 默认安装某些问题解析

首先默认安装软件(本文以PostgreSQL 11.1为例,其他版本类似)。 sudo apt install postgresql-11 等待软件自动安装并完成配置,启动服务。 服务状态如下: vmware@vmware-virtual-machine:...

白豆腐徐长卿
24分钟前
1
0
一步步动手实现高并发的Reactor模型 —— Kafka底层如何充分利用多线程优势去处理网络I/O与业务分发

一、从《Apeche Kafka源码剖析》上搬来的概念和图 Kafka网络采用的是Reactor模式,是一种基于事件驱动的模式。熟悉Java编程的读者应该了解Java NIO提供了Reactor模式的API。常见的单线程Jav...

Anur
27分钟前
1
0
数字信号处理各种处理及图象

https://wenku.baidu.com/view/b1bb67f1f90f76c661371a75.html?sxts=1544696459935

whoisliang
31分钟前
1
0
rabbitmq学习

使用docker安装rabbit docker run -d --hostname my-rabbit --name rabbit -p 8080:15672 rabbitmq:management--hostname:指定容器主机名称--name:指定容器名称-p:将mq端口号映射到本地...

元谷
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部