`

Sequential Lock in Java

阅读更多

1 Overview
   Linux内核中常见的同步机制有Atomic Operation,Spin Locks,Semaphore,Mutex等。其中Spin Locks和Semaphore都支持读/写锁。此外,Linux内核还支持一种更轻量级的读/写锁定机制:Sequential Lock。跟其它读/写锁定机制相比,Sequential Lock有以下特点:

  • 在获取锁时偏向写锁。只要他人不持有写锁,那么获得写锁的操作总是能够成功。
  • 读操作时不需要获得锁(即读操作永远不会被阻塞),然而在有些情况下读操作需要重试。
  • Sequential Lock更轻量级,可伸缩性相对更好。

2 Linux Kernel's Implementation
   以下是2.6版本的内核中,Sequential Lock的实现:

typedef struct {
  unsigned sequence;
  spinlock_t lock;
} seqlock_t;

static inline void write_seqlock(seqlock_t *sl)
{
  spin_lock(&sl->lock);
  ++sl->sequence;
  smp_wmb();
}

static inline void write_sequnlock(seqlock_t *sl)
{
  smp_wmb();
  sl->sequence++;
  spin_unlock(&sl->lock);
}

static __always_inline unsigned read_seqbegin(const seqlock_t *sl)
{
  unsigned ret = sl->sequence;
  smp_rmb();
  return ret;
}

static __always_inline int read_seqretry(const seqlock_t *sl, unsigned iv)
{
  smp_rmb();
  return (iv & 1) | (sl->sequence ^ iv);
}

   以上代码中,通过使用spin lock保证了write操作的原子性。需要注意的是,Linux spin lock是非可重入锁,这也是read_seqretry方法中可以通过(iv & 1)判断一个写操作是否正在进行中的原因。此外,Linux spin lock只能保证原子性,为了避免由于编译器或者处理器对指令的重排序(例如x86平台不会对写操作重排序,但是可能会对读操作进行重排序)所导致的潜在问题,seqlock使用memory barrier(smp_wmb和smp_rmb)保证了内存可见性。

   seqlock的用法如下:
   To define a seqlock:

seqlock_t mr_seq_lock = DEFINE_SEQLOCK(mr_seq_lock);

   The write path:

write_seqlock(&mr_seq_lock);
/* write lock is obtained... */
write_sequnlock(&mr_seq_lock);

   The read path:

unsigned long seq;
do {
  seq = read_seqbegin(&mr_seq_lock);
  /* read data here ... */
} while (read_seqretry(&mr_seq_lock, seq));

 

  seqlock的典型使用场景如下:

  • 跟读操作的数量相比,写操作的数量很少。
  • 在锁获取时,希望写操作优先。

  使用seqlock的注意事项:

  • 读操作耗时应比较短,否则容易导致过多次的读重试。
  • 由于在读的过程中写操作可能正在修改数据,因此读操作可能会读取到某种不一致的状态。所以进行读取时,需要保护性的验证,以避免因读取不一致的错误数据导致错读。

3 Sequential Lock in Java
   本想自己实现一个Java版本的Sequential lock,但是在Google了之后发现Makoto YUI已经提供了一比较好的实现,在其基础之上稍加改动之后的实现如下:

public final class SequentialLock {
    //
    private volatile int counter;

    /**
     * 
     */
    public int readBegin() {
        return this.counter;
    }

    public boolean readRetry(int v) {
        return (v & 1) == 1 || this.counter != v;
    }
    
    public synchronized void writeLock() {
        //
        if((this.counter & 1) != 0) {
            throw new IllegalStateException("sequential lock is NOT reentrantable");
        }
        
        //
        ++this.counter;
    }
    
    public synchronized void writeUnlock() {
        ++this.counter;
    }
} 

   首先,SequentialLock不是可重入的。其次由于读操作没有获得锁,因此读写之间需要额外的机制以保证内存可见性:对其volitle counter成员变量的读写保证了Sequential Lock保护的数据之间的happens bofore语义。

4 Reference
   Linux Kernel Development 3rd Edition, Robert Love

分享到:
评论

相关推荐

    Advanced Topics in Java

    in Java), linked lists, stacks, queues, recursion, random numbers, files (text, binary, random access, indexed), binary trees, advanced sorting methods (heapsort, quicksort, mergesort, Shell sort), ...

    Non sequential model in zemax

    非顺序光线追踪(Non-Sequential Ray Tracing)是光学设计软件ZEMAX中的一项高级功能,与传统的顺序光线追踪相比,它提供了更为复杂且灵活的光线处理方式。在顺序光线追踪模式下,光线必须按照预定义的顺序通过一...

    Online Learning and Sequential Anomaly Detection in Trajectories

    Detection of anomalous trajectories is an important problem in the surveillance domain. Various algorithms based on learning of normal trajectory patterns have been proposed for this problem. Yet, ...

    Context_aware Sequential Recommender

    role in modeling user behaviors, various sequential recom- mendation methods have been proposed. Methods based on Markov assumption are widely-used, but independently com- bine several most recent ...

    Sequential Analysis - Hypothesis Testing and Changepoint Detection

    时间序列分析——The main focus of this book is on a systematic development of the theory of sequential hypothesis testing (Part I) and changepoint detection (Part II). In Part III, we briefly describe...

    83个数据挖掘算法 java 源码 和 jar文件

    SPMF is an open-source data mining mining library written in Java, specialized in pattern mining. It is distributed under the GPL v3 license. It offers implementations of 82 data mining algorithms ...

    Sequential Monte Carlo in C++

    **序贯蒙特卡洛(Sequential Monte Carlo, SMC)**是一种统计计算方法,用于解决在高维度或复杂概率模型中的采样问题。它也被称为粒子滤波器,尤其在贝叶斯推断和动态系统建模中广泛应用。SMC通过一系列的采样步骤来...

    Mining Sequential Patterns

    Mining Sequential Patterns

    gsp.rar_GSP CBA数据挖掘_GSP in java_gsp java_序列模式

    GSP(Generalized Sequential Pattern)算法是序列模式挖掘中的一种经典方法,尤其在理解用户行为、市场趋势以及各种时间序列数据中有着广泛的应用。下面将详细阐述GSP算法以及其在Java环境下的实现。 GSP算法,...

    闭包搜索算法java编程

    Sequential events in a single computation are not concurrent. For example, if a particular computation performs the operations identified by events 1, 2 and 3 in that order, then clearly and 1 ! 2 and...

    datastage Sequential File Stage

    DataStage Sequential File Stage是ETL(提取、转换、加载)过程中用于处理文本文件的一个关键组件。这个stage专门设计用于读取和写入简单的文本文件,它具有灵活性和可配置性,能够适应各种数据处理需求。以下是对...

    Processor Arch-Sequential

    ### Processor Architecture: Sequential Implementation #### 引言 处理器架构(Processor Architecture)是计算机系统的核心组成部分之一,它定义了处理器的设计原则和技术实现方式。本篇内容将深入探讨处理器...

    Java 9 for Programmers (Deitel Developer Series) 完整高清azw3版

    level language, this book applies the Deitel signature live-code approach to teaching programming and explores the Java® 9 language and APIs in depth. The book presents concepts in fully tested ...

    Sequential在浏览器中可视化JavaScript代码执行的环境

    Sequential 是一个专为JavaScript开发者设计的工具,它允许用户在浏览器环境中直观地观察和理解代码的执行过程。这个创新的平台提供了一种序列化的视图,使开发者可以更深入地了解代码的每一步操作,对于学习、调试...

    基于STM32F103ZET,移植LWIP协议栈,sequential编程接口实现TCP客户端

    在本文中,我们将深入探讨如何在STM32F103ZET微控制器上移植LWIP(Lightweight IP)协议栈,并利用sequential编程接口来实现一个TCP客户端。STM32F103ZET是意法半导体(STMicroelectronics)推出的基于ARM Cortex-M3...

    米哈游笔试题目-Java方向.docx

    myNodePath = zookeeper.create(lockPath + "/lock-", new byte[0], Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL); } public void unlock() throws Exception { zookeeper.delete(myNodePath, -1); ...

    Sequential Minimal Optimization for SVM

    **标题解析:Sequential Minimal Optimization for SVM** Sequential Minimal Optimization(SMO)是一种用于训练支持向量机(Support Vector Machines,简称SVM)的有效算法。SVM是一种监督学习模型,广泛应用于二...

Global site tag (gtag.js) - Google Analytics