Review: Concurrency Problems

Concurrency Problems

---

---

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups

Scenarios

Name	Comment
Map/Reduce: scheduler + workers	Leetcode: Web Crawler Multithreaded
Claim ownerhip of a single resource	Leetcode: Traffic Light Controlled Intersection
Dining Philosophers problem	Avoid deadlock and starvation Leetcode: The Dining Philosophers
ABA problem	Leetcode: Building H2O
Producer-consumer problem	a.k.a the bounded-buffer problem
Cigarette smokers problem	Assume a cigarette requires 3 ingredients: tobacco, paper, and matches
Readers-writers problem	Read/write access the same shared resource at one time
Sleeping barber problem	Keep a barber working when there are customers, resting when none

Concepts

Name	Comment
Synchronization primitives	mutex, semaphore
Interaction and communication	Shared memory communication/Message passing communication
Actor model
Asynchronous I/O
Reference	Wikipedia: Concurrent computing

Semaphore

The Semaphore is used for blocking thread level access to some part of the physical or logical resource. A semaphore contains a set of permits; whenever a thread tries to enter the critical section, it needs to check the semaphore if a permit is available or not.

If a permit is not available (via tryAcquire()), the thread is not allowed to jump into the critical section; however, if the permit is available the access is granted, and the permit counter decreases.

Once the executing thread releases the critical section, again the permit counter increases (done by release() method).

We can specify a timeout for acquiring access by using the tryAcquire(long timeout, TimeUnit unit) method.

We can also check the number of available permits or the number of threads waiting to acquire the semaphore.

We can implement a Mutex like data-structure using Semaphore. 

Following code snippet can be used to use implement a semaphore:

static Semaphore semaphore = new Semaphore(10);
 
public void execute() throws InterruptedException {
 
    LOG.info("Available permit : " + semaphore.availablePermits());
    LOG.info("Number of threads waiting to acquire: " + 
      semaphore.getQueueLength());
 
    if (semaphore.tryAcquire()) {
        try {
            // ...
        }
        finally {
            semaphore.release();
        }
    }
 
}

See all concurrency problems: #concurrency.

• Review: Concurrency Problems
• LeetCode: Web Crawler Multithreaded
• Leetcode: Traffic Light Controlled Intersection
• Leetcode: The Dining Philosophers
• Leetcode: Range Sum Query 2D – Immutable
• Leetcode: Print Zero Even Odd
• Leetcode: Print in Order
• Leetcode: Print FooBar Alternately
• Leetcode: Fizz Buzz Multithreaded
• Leetcode: Design Bounded Blocking Queue

See more blog_posts.

---