際際滷

際際滷Share a Scribd company logo

Sequential Concurrency ... WHAT ???

Download as PPTX, PDF
Jitendra Chittoda
Jitendra Chittoda

Using the ThreadPool, we cannot ensure the execution order of the tasks. There are few situations as per the industry needs, where we need to ensure the task execution order. StripedExecutorService class we are developing, would ensure the task execution order. Example: On an Exchange server we have many products on which users can trade. Transactions on a single product should be performed in FIFO order as per the business needs, and there are many products of such type. So along with maintaining the sequential order of execution of tasks for A product, we are also processing tasks sequentially for other product B as well concurrently. We would be showing Heinz Kabutz implementation.

1 of 31
Download to read offline
Jitendra Chittoda, Member Development Department @ ION Trading India Pvt. Ltd. Co-leader Delhi and NCR Java User Group (DaNJUG) Email: jitendra@chittoda.com Twitter: @JChittoda Blog: http://chittoda.com Sequential Concurrency. WHAT ??? 08 May 20131 JavaOne India 2013 : COM1240
Delhi & NCR JUG (DaNJUG) 08 May 20132 30+ Members Looking for more active members Meetup.com, Groups If your friends are in Delhi NCR, please spread the word
Agenda What is ThreadPool Benefits of using ThreadPool What we cant achieve with ThreadPool Why & Where ? Sequential Concurrency Fundamentals SerialExecutor StripedExecutorService Design Features Current State 08 May 20133
ThreadPool 08 May 20134
Benefits of ThreadPool 08 May 20135 Pre-initialized pool of threads Reusable threads Configurable
What we cant achieve with ThreadPool 08 May 20136 As per the business requirement, sometimes you may want to process Tasks in specific order. Tasks execution order is not maintained by the normal ThreadPools Processing Not Ordered Processing of a Task is not ordered, you can say its uncertain.
08 May 20137
Why? Industry Examples 08 May 20138 Exchange trading Processing of trades on an instrument. Train Reservations Ticket booking requests for a train must be processed in FIFO order. Multi Tenancy Each tenant want some specific execution to be ordered
Where ? 08 May 20139 First saw in 2007 then in 2010 and in 2011 November 2011: Started writing my own implementation, published a blog on http://chittoda.com November 2012: http://www.javaspecialists.eu/archive/Issue206.html Heinz got 5 different implementations after this issue.
Sequential Concurrency Fundamentals 08 May 201310 Identification Maintaining Order Sequential Processing No Dependency
Sequential Concurrency Fundamentals 08 May 201311 Identification Maintain the sequence based on some Stripe or Key Stripe: An object which is common among the Tasks those needs to be processed in sequence.
Sequential Concurrency Fundamentals 08 May 201312 Maintaining Order Maintain the sequential ordering tasks FIFO Order
Sequential Concurrency Fundamentals 08 May 201313 Sequential Processing Process tasks of a Stripe in sequence To maintain this we assign one and only one Thread to a Queue.
Sequential Concurrency Fundamentals 08 May 201314 No Dependency Tasks of one Stripe-X should not be dependent on Tasks of another Stripe-Y
Sequential Concurrency 08 May 201315 12 132 Pool of Threads Queue of Stripe StripedExecutorServic e T- 1 T- 2 T- 3
Executor JavaDoc 08 May 201316 Many Executor implementations impose some sort of limitation on how and when tasks are scheduled. The executor below serializes the submission of tasks to a second executor, illustrating a composite executor. class SerialExecutor implements Executor { Queue<Runnable> tasks = new ArrayDeque<>(); Executor executor; Runnable active; SerialExecutor(Executor executor) { this.executor = executor; }
SerialExecutor 08 May 201317 public void execute(final Runnable r) { tasks.offer(new Runnable() { public void run() { try { r.run(); } finally { scheduleNext(); } } }); if (active == null) { scheduleNext(); } }
SerialExecutor 08 May 201318 protected void scheduleNext() { if ((active = tasks.poll()) != null) { executor.execute(active); } }
Pool of SerialExecutor 08 May 201319 SerialExecutor maintain the sequence of the tasks assigned to it and process them in sequence. Using single queue. BUT we need pool of SerialExecutor, so that we can concurrently execute tasks of two or more Striped Queues
Implementation Details 08 May 201320 1) Identification Stripe: We are using Object as Stripe, you can define your own. 2) Maintain Order With separate Queue based on Stripe. SerialExecutor is maintaining a Queue 3) Sequential Processing Handled by SerialExecutor 4) No Dependency Handled by SerialExecutor
Design 08 May 201321
08 May 201322
08 May 201323
Inside StripedExecutorService 08 May 201324 class SerialExecutor implements Executor { private BlockingQueue<Runnable> tasks = new LinkedBlockingQueue<>(); private Runnable active; private final Object stripe; private SerialExecutor(Object stripe) { this.stripe = stripe; }
08 May 201325 public void execute(final Runnable r) { lock.lock(); try { tasks.add(new Runnable() { public void run() { try { r.run(); } finally { scheduleNext(); } } }); if (active == null){ scheduleNext(); } } finally { lock.unlock(); } }
Inside StripedExecutorService 08 May 201326 private void scheduleNext() { lock.lock(); try { if ((active = tasks.poll()) != null) { executor.execute(active); terminating.signalAll(); } else { removeEmptySerialExecutor(stripe, this); } } finally { lock.unlock(); } }
08 May 201327 private final ExecutorService executor; private final Map<Object, SerialExecutor> executors = new IdentityHashMap<>(); public void execute(Runnable command) { lock.lock(); try { Object stripe = getStripe(command); if (stripe != null) { SerialExecutor ser_exec= executors.get(stripe); if (ser_exec == null) { executors.put(stripe, ser_exec= new SerialExecutor(stripe)); } ser_exec.execute(command); } else { executor.execute(command); } } finally { lock.unlock(); } }
Features 08 May 201328 Non striped tasks can also be handled with SES Queues gets created when required No memory leaks in terms of the Queues. Queues gets removed once all tasks are finished.
Current State 08 May 201329 Work In Progress Several other implementations available, but no one passes the tests written for StripedExecutorService Performance
References 08 May 201330 Delhi & NCR JUG https://groups.google.com/d/forum/dncrjug GitHub : https://github.com/kabutz/striped-executor-service Dr. Heinz Kabutz Newsletter http://www.javaspecialists.eu/archive/Issue206.html http://www.javaspecialists.eu/ Blog http://chittoda.com
08 May 201331

More Related Content

Sequential Concurrency ... WHAT ???

  • 1. Jitendra Chittoda, Member Development Department @ ION Trading India Pvt. Ltd. Co-leader Delhi and NCR Java User Group (DaNJUG) Email: jitendra@chittoda.com Twitter: @JChittoda Blog: http://chittoda.com Sequential Concurrency. WHAT ??? 08 May 20131 JavaOne India 2013 : COM1240
  • 2. Delhi & NCR JUG (DaNJUG) 08 May 20132 30+ Members Looking for more active members Meetup.com, Groups If your friends are in Delhi NCR, please spread the word
  • 3. Agenda What is ThreadPool Benefits of using ThreadPool What we cant achieve with ThreadPool Why & Where ? Sequential Concurrency Fundamentals SerialExecutor StripedExecutorService Design Features Current State 08 May 20133
  • 5. Benefits of ThreadPool 08 May 20135 Pre-initialized pool of threads Reusable threads Configurable
  • 6. What we cant achieve with ThreadPool 08 May 20136 As per the business requirement, sometimes you may want to process Tasks in specific order. Tasks execution order is not maintained by the normal ThreadPools Processing Not Ordered Processing of a Task is not ordered, you can say its uncertain.
  • 8. Why? Industry Examples 08 May 20138 Exchange trading Processing of trades on an instrument. Train Reservations Ticket booking requests for a train must be processed in FIFO order. Multi Tenancy Each tenant want some specific execution to be ordered
  • 9. Where ? 08 May 20139 First saw in 2007 then in 2010 and in 2011 November 2011: Started writing my own implementation, published a blog on http://chittoda.com November 2012: http://www.javaspecialists.eu/archive/Issue206.html Heinz got 5 different implementations after this issue.
  • 10. Sequential Concurrency Fundamentals 08 May 201310 Identification Maintaining Order Sequential Processing No Dependency
  • 11. Sequential Concurrency Fundamentals 08 May 201311 Identification Maintain the sequence based on some Stripe or Key Stripe: An object which is common among the Tasks those needs to be processed in sequence.
  • 12. Sequential Concurrency Fundamentals 08 May 201312 Maintaining Order Maintain the sequential ordering tasks FIFO Order
  • 13. Sequential Concurrency Fundamentals 08 May 201313 Sequential Processing Process tasks of a Stripe in sequence To maintain this we assign one and only one Thread to a Queue.
  • 14. Sequential Concurrency Fundamentals 08 May 201314 No Dependency Tasks of one Stripe-X should not be dependent on Tasks of another Stripe-Y
  • 15. Sequential Concurrency 08 May 201315 12 132 Pool of Threads Queue of Stripe StripedExecutorServic e T- 1 T- 2 T- 3
  • 16. Executor JavaDoc 08 May 201316 Many Executor implementations impose some sort of limitation on how and when tasks are scheduled. The executor below serializes the submission of tasks to a second executor, illustrating a composite executor. class SerialExecutor implements Executor { Queue<Runnable> tasks = new ArrayDeque<>(); Executor executor; Runnable active; SerialExecutor(Executor executor) { this.executor = executor; }
  • 17. SerialExecutor 08 May 201317 public void execute(final Runnable r) { tasks.offer(new Runnable() { public void run() { try { r.run(); } finally { scheduleNext(); } } }); if (active == null) { scheduleNext(); } }
  • 18. SerialExecutor 08 May 201318 protected void scheduleNext() { if ((active = tasks.poll()) != null) { executor.execute(active); } }
  • 19. Pool of SerialExecutor 08 May 201319 SerialExecutor maintain the sequence of the tasks assigned to it and process them in sequence. Using single queue. BUT we need pool of SerialExecutor, so that we can concurrently execute tasks of two or more Striped Queues
  • 20. Implementation Details 08 May 201320 1) Identification Stripe: We are using Object as Stripe, you can define your own. 2) Maintain Order With separate Queue based on Stripe. SerialExecutor is maintaining a Queue 3) Sequential Processing Handled by SerialExecutor 4) No Dependency Handled by SerialExecutor
  • 24. Inside StripedExecutorService 08 May 201324 class SerialExecutor implements Executor { private BlockingQueue<Runnable> tasks = new LinkedBlockingQueue<>(); private Runnable active; private final Object stripe; private SerialExecutor(Object stripe) { this.stripe = stripe; }
  • 25. 08 May 201325 public void execute(final Runnable r) { lock.lock(); try { tasks.add(new Runnable() { public void run() { try { r.run(); } finally { scheduleNext(); } } }); if (active == null){ scheduleNext(); } } finally { lock.unlock(); } }
  • 26. Inside StripedExecutorService 08 May 201326 private void scheduleNext() { lock.lock(); try { if ((active = tasks.poll()) != null) { executor.execute(active); terminating.signalAll(); } else { removeEmptySerialExecutor(stripe, this); } } finally { lock.unlock(); } }
  • 27. 08 May 201327 private final ExecutorService executor; private final Map<Object, SerialExecutor> executors = new IdentityHashMap<>(); public void execute(Runnable command) { lock.lock(); try { Object stripe = getStripe(command); if (stripe != null) { SerialExecutor ser_exec= executors.get(stripe); if (ser_exec == null) { executors.put(stripe, ser_exec= new SerialExecutor(stripe)); } ser_exec.execute(command); } else { executor.execute(command); } } finally { lock.unlock(); } }
  • 28. Features 08 May 201328 Non striped tasks can also be handled with SES Queues gets created when required No memory leaks in terms of the Queues. Queues gets removed once all tasks are finished.
  • 29. Current State 08 May 201329 Work In Progress Several other implementations available, but no one passes the tests written for StripedExecutorService Performance
  • 30. References 08 May 201330 Delhi & NCR JUG https://groups.google.com/d/forum/dncrjug GitHub : https://github.com/kabutz/striped-executor-service Dr. Heinz Kabutz Newsletter http://www.javaspecialists.eu/archive/Issue206.html http://www.javaspecialists.eu/ Blog http://chittoda.com