DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

The software you build is only as secure as the code that powers it. Learn how malicious code creeps into your software supply chain.

Apache Cassandra combines the benefits of major NoSQL databases to support data management needs not covered by traditional RDBMS vendors.

Generative AI has transformed nearly every industry. How can you leverage GenAI to improve your productivity and efficiency?

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Related

  • Filtering Java Collections via Annotation-Driven Introspection
  • Mastering Thread-Local Variables in Java: Explanation and Issues
  • Unlocking Performance: Exploring Java 21 Virtual Threads [Video]
  • Implementing Infinite Scroll in jOOQ

Trending

  • 5 Subtle Indicators Your Development Environment Is Under Siege
  • Event-Driven Architectures: Designing Scalable and Resilient Cloud Solutions
  • Chat With Your Knowledge Base: A Hands-On Java and LangChain4j Guide
  • Mastering Advanced Traffic Management in Multi-Cloud Kubernetes: Scaling With Multiple Istio Ingress Gateways
  1. DZone
  2. Software Design and Architecture
  3. Integration
  4. Implementing Filter and Bakery Locks in Java

Implementing Filter and Bakery Locks in Java

By 
Furkan Kamaci user avatar
Furkan Kamaci
·
Apr. 28, 15 · Interview
Likes (2)
Comment
Save
Tweet
Share
8.8K Views

Join the DZone community and get the full member experience.

Join For Free

In order to understand how locks work, implementing custom locks is a good way. This post will show how to implement Filter and Bakery locks at Java (which are spin locks) and will compare their performances with Java's ReentrantLock. Filter and Bakery locks satisfies mutual exclusion and are starvation free algorithms also, Bakery lock is a first-come-first-served lock [1].

For performance testing, a counter value is incremented up to 10000000 with different lock types, different number of threads and different number of times. Test system configuration is: Intel Core I7 (has 8 cores – 4 of them are real), Ubuntu 14.04 LTS and Java 1.7.0_60.

Filter lock has n-1 levels which maybe considered as “waiting rooms”. A thread must traverse this waiting rooms before acquiring the lock. There are two important properties for levels [2]:

1) At least one thread trying to enter level l succeeds.
2) If more than one thread is trying to enter level l, then at least one is blocked (i.e., continues to wait at that level).

Filter lock is implemented as follows:

/**
 * @author Furkan KAMACI
 */
public class Filter extends AbstractDummyLock implements Lock {
    /* Due to Java Memory Model, int[] not used for level and victim variables.
     Java programming language does not guarantee linearizability, or even sequential consistency,
     when reading or writing fields of shared objects
     [The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
     */
    private AtomicInteger[] level;
    private AtomicInteger[] victim;

    private int n;

    /**
     * Constructor for Filter lock
     *
     * @param n thread count
     */
    public Filter(int n) {
        this.n = n;
        level = new AtomicInteger[n];
        victim = new AtomicInteger[n];
        for (int i = 0; i < n; i++) {
            level[i] = new AtomicInteger();
            victim[i] = new AtomicInteger();
        }
    }

    /**
     * Acquires the lock.
     */
    @Override
    public void lock() {
        int me = ConcurrencyUtils.getCurrentThreadId();
        for (int i = 1; i < n; i++) {
            level[me].set(i);
            victim[i].set(me);
            for (int k = 0; k < n; k++) {
                while ((k != me) && (level[k].get() >= i && victim[i].get() == me)) {
                    //spin wait
                }
            }
        }
    }

    /**
     * Releases the lock.
     */
    @Override
    public void unlock() {
        int me = ConcurrencyUtils.getCurrentThreadId();
        level[me].set(0);
    }
}

Bakery lock algorithm maintains the first-come-first-served property by using a distributed version of the number-dispensing machines often found in bakeries: each thread takes a number in the doorway, and then waits until no thread with an earlier number is trying to enter it [3].

Bakery lock is implemented as follows:

/**
 * @author Furkan KAMACI
 */
public class Bakery extends AbstractDummyLock implements Lock {
    /* Due to Java Memory Model, int[] not used for level and victim variables.
     Java programming language does not guarantee linearizability, or even sequential consistency,
     when reading or writing fields of shared objects
     [The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
     */
    private AtomicBoolean[] flag;
    private AtomicInteger[] label;

    private int n;

    /**
     * Constructor for Bakery lock
     *
     * @param n thread count
     */
    public Bakery(int n) {
        this.n = n;
        flag = new AtomicBoolean[n];
        label = new AtomicInteger[n];
        for (int i = 0; i < n; i++) {
            flag[i] = new AtomicBoolean();
            label[i] = new AtomicInteger();
        }
    }

    /**
     * Acquires the lock.
     */
    @Override
    public void lock() {
        int i = ConcurrencyUtils.getCurrentThreadId();
        flag[i].set(true);
        label[i].set(findMaximumElement(label) + 1);
        for (int k = 0; k < n; k++) {
            while ((k != i) && flag[k].get() && ((label[k].get() < label[i].get()) || ((label[k].get() == label[i].get()) && k < i))) {
                //spin wait
            }
        }
    }

    /**
     * Releases the lock.
     */
    @Override
    public void unlock() {
        flag[ConcurrencyUtils.getCurrentThreadId()].set(false);
    }

    /**
     * Finds maximum element within and {@link java.util.concurrent.atomic.AtomicInteger} array
     *
     * @param elementArray element array
     * @return maximum element
     */
    private int findMaximumElement(AtomicInteger[] elementArray) {
        int maxValue = Integer.MIN_VALUE;
        for (AtomicInteger element : elementArray) {
            if (element.get() > maxValue) {
                maxValue = element.get();
            }
        }
        return maxValue;
    }
}

For such kind of algorithms, it should be provided or used a thread id system which starts from 0 or 1 and increments one by one. Threads' names set appropriately for that purpose. It should also be considererd that: Java programming language does not guarantee linearizability, or even sequential consistency, when reading or writing fields of shared objects [4]. So, level and victim variables for Filter lock, flag and label variables for Bakery lock defined as atomic variables. For one, who wants to test effects of Java Memory Model can change that variables into int[] and boolean[] and run algorithm with more than 2 threads. Than, can see that algorithm will hang for either Filter or Bakery even threads are alive.

To test algorithm performances, a custom counter class implemented which has a getAndIncrement method as follows:

/**
 * gets and increments value up to a maximum number
 *
 * @return value before increment if it didn't exceed a defined maximum number. Otherwise returns maximum number.
 */
public long getAndIncrement() {
    long temp;
    lock.lock();
    try {
        if (value >= maxNumber) {
            return value;
        }
        temp = value;
        value = temp + 1;
    } finally {
        lock.unlock();
    }
    return temp;
}

There is a maximum number barrier to fairly test multiple application configurations. Consideration is that: there is a piece amount of work (incrementing a variable up to a desired number) and with
different number of threads how fast you can finish it. So, for comparison, there should be a “job” equality. This approach also tests unnecessary work load with that piece of code:

if (value >= maxNumber) {
    return value;
}

for multiple threads when it is compared an approach that calculating unit work performance of threads (i.e. does not putting a maximum barrier, iterating in a loop up to a maximum number and than dividing last value to thread number).

This configuration used for performance comparison:

Threads
1,2,3,4,5,6,7,8
Retry Count
20
Maximum Number
10000000
This is the chart of results which includes standard errors:


First of all, when you run a block of code within Java several time, there is an internal optimization for codes. When algorithm is run multiple times and first output compared to second output this optimization's effect can be seen. First elapsed time mostly should be greater than second line because of that. For example:

currentTry = 0, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 500 (ms)
currentTry = 1, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 433 (ms)

Conclusion:

From the chart, it can bee seen that Bakery lock is faster than Filter Lock with a low standard error. Reason is Filter Lock's lock method. At Bakery Lock, as a faired approach threads runs one by one but at Filter Lock they computes with each other. Java's ReentrantLock has best when compared to others.

On the other hand Filter Lock gets worse linearly but Bakery and ReentrantLock are not (Filter lock may have a linear graphic when it run with much more threads). More thread count does not mean less elapsed time. 2 threads maybe worse than 1 thread because of thread creating and locking/unlocking. When thread count starts to increase, elapsed time gets better for Bakery and ReentrantLock. However when thread count keep going to increase than it gets worse. Reason is real core number of the test computer which runs algorithms.

Source code for implementing filter and bakery locks in Java can be downloaded from here: https://github.com/kamaci/filbak

[1] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.31.-33.

[2] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.28.

[3] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.31.

[4] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.

Java (programming language) Threading Filter (software)

Published at DZone with permission of Furkan Kamaci, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Filtering Java Collections via Annotation-Driven Introspection
  • Mastering Thread-Local Variables in Java: Explanation and Issues
  • Unlocking Performance: Exploring Java 21 Virtual Threads [Video]
  • Implementing Infinite Scroll in jOOQ

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!