Lock free bounded queue
JDK 1.5 was first step towards adding serious concurrency support to java, it changed the way you write concurrent program and in other version 1.6, 1.7 etc more concurrency support.
One of the important building block for concurrent programming is Queue, java has lot of them ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue.
I am sure you will find one Queue that will fit your need!
Locks are used in most of the queue for managing concurrent access to data structure because of obvious reason of simplicity to use, lock based strategy makes it difficult to develop low latency system, it could result in priority inversion, context switching, deadlock etc
Alternate way is using Non Blocking Algorithm , which is bit difficult to develop, one of the non blocking algorithm is lock free algorithm
Java added support for look free via java.util.concurrent.atomic package, so now time for some action with lock free api.
Java 1.5+ has lock free queue ConcurrentLinkedQueue, which is very fast but it is unbounded and such type queue can be very risky to use real application because most of the time queue is not balanced, it is either full or empty and if it is unbounded then system can run out of resource.
I will implement lock free bounded queue and measure it performance against lock based bounded queue(ArrayBlocking), lock free unbounded queue(ConcurrentLinkedQueue). I chose these queue because they are fastest queue available in JDK.
Number Game
Test Envinorment Details
OS : Windows 7, 64 bit
Processor : Intel (R) Core(TM) i7-2820QM CPU @ 2.30 GHz
Processor Arch : Sandy Bridge , 4 physical cores/8 threads
For this test 10 Million message was added to queue using single producer and consumer number are in range of 1 to 5, non blocking call(offer/poll) call is used to produce/consume message from queue, performance is best when there is 1 consumer and as number of consumer increase performance degrades, so it is evident that contention is the culprit.
Cpu Usage
Cpu usage for LockFreeBoundedQueue
Cpu usage for ArrayBlockingQueue
From CPU usage it is clear that contention is causing drop in cpu usage and with lock free queue CPU usage is in acceptable range.
Test Code of LockFreeBoundedQueue
Link To Code
Above code is just an idea to demonstrate that how powerful non blocking algorithm can be. This code can be enhanced to add more feature like multiple producer, support for blocking call put/take.
Before adding blocking support(put/take) to queue we have to think about blocking strategy, there are couple of option spinning, hybrid spinning etc.
JDK 1.5 was first step towards adding serious concurrency support to java, it changed the way you write concurrent program and in other version 1.6, 1.7 etc more concurrency support.
One of the important building block for concurrent programming is Queue, java has lot of them ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue.
I am sure you will find one Queue that will fit your need!
Locks are used in most of the queue for managing concurrent access to data structure because of obvious reason of simplicity to use, lock based strategy makes it difficult to develop low latency system, it could result in priority inversion, context switching, deadlock etc
Alternate way is using Non Blocking Algorithm , which is bit difficult to develop, one of the non blocking algorithm is lock free algorithm
Java added support for look free via java.util.concurrent.atomic package, so now time for some action with lock free api.
Java 1.5+ has lock free queue ConcurrentLinkedQueue, which is very fast but it is unbounded and such type queue can be very risky to use real application because most of the time queue is not balanced, it is either full or empty and if it is unbounded then system can run out of resource.
I will implement lock free bounded queue and measure it performance against lock based bounded queue(ArrayBlocking), lock free unbounded queue(ConcurrentLinkedQueue). I chose these queue because they are fastest queue available in JDK.
Number Game
Test Envinorment Details
OS : Windows 7, 64 bit
Processor : Intel (R) Core(TM) i7-2820QM CPU @ 2.30 GHz
Processor Arch : Sandy Bridge , 4 physical cores/8 threads
For this test 10 Million message was added to queue using single producer and consumer number are in range of 1 to 5, non blocking call(offer/poll) call is used to produce/consume message from queue, performance is best when there is 1 consumer and as number of consumer increase performance degrades, so it is evident that contention is the culprit.
Cpu Usage
Cpu usage for LockFreeBoundedQueue
Cpu usage for ArrayBlockingQueue
From CPU usage it is clear that contention is causing drop in cpu usage and with lock free queue CPU usage is in acceptable range.
Test Code of LockFreeBoundedQueue
Link To Code
Above code is just an idea to demonstrate that how powerful non blocking algorithm can be. This code can be enhanced to add more feature like multiple producer, support for blocking call put/take.
Before adding blocking support(put/take) to queue we have to think about blocking strategy, there are couple of option spinning, hybrid spinning etc.
Your algorithm has a bug. In the offer, you can go ahead and commit to the write, but while you do that, your queue grows and gets full. If that happens, you'll end up overwriting the most recent data.
ReplyDeleteThanks for it. I will fix that or if you have any suggestion then let me know .
DeleteCool men and women inscribe, the world wide web is incredibly salubrious moreover remarkable, We shall present find associated with the globe. serrurier bruxelles
ReplyDelete