Lecture Notes for Concurrent Programming

29 July 2003 - One-Way Messages

Outline

• Shared variables vs. messages

• Buffering threads and runnables

  • Messages and active messages

• Open Calls

• Thread-per-Message Structure

• Thread Problems

  • Executors

  • Worker Threads

  • Design Choices

  • Events

  • Timers

• Polling and Event-Drive I-O

Shared Variables vs. Messages

• Communicating with shared variables is hard.

  • The sender and receiver have to coordinate.

    • Is it there yet? Is it gone yet?

  • Thread scoping may not match variable scoping.

    • Flat and unstructured vs. controlled and hierarchical

• Instead, share synchronization mechanisms.

  • The synchronization follows the thread structure.

  • Threads can have simplified but more general data exchange.

  • This is similar to using buffers.

  • The data exchanged is generically known as a message.

Buffering Threads

• Extend Threads to include a message buffer.

  class MessageBuffer
  
    private Queue msgs
  
    synchronized void send(Object o)
      msgs.put(o)
      notify()
  
    synchronized Object receive()
      while (msgs.size() < 1) wait()
      return msgs.get()
  
  
  class BufferedThread
  extends Thread
  
    private MessageBuffer msgs
  
    BufferedThread(MessageBuffer m)
      msgs m
  
    void send(Object msg)
      msgs.send(msg)
  

Buffered Runnables

• The Runnable needs access to the message.

  class Worker
  implements Runnable
  
    final MessageBuffer msgs
  
    Worker(MessageBuffer msgs)
      this.msgs = msgs
  
    void run() 
      while true
        msg = msgs.receive()
        // work on msg
  

• The interface between the buffered Thread and Runnable can get messy.

Message Formats

• Messages may contain arbitrary content.

  • Generally, the content is either data or code.

• The receiver interprets and operates on data.

  • Commands to execute, event notifications.

• The receiver executes code.

  • Subroutines or function objects, Runnables.

• Sending code is more general, sending data can be more efficient.

  • It depends on the code and data sizes.

Message Traffic

• Message traffic among threads can be arbitrary.

  • All that's required is a thread reference.

• The request response pattern is typical.
  

• one-way messages are requests with no replies.

  • The sender doesn't care or can't handle a response.

    • Log file entries; hardware sensors.

  • The reply may get forwarded to a third party.

    • And so becomes another one-way message.
    

Open Calls

• A thread receiving many messages may rely on a helper.

  • A form of boss-worker structure, but with only one worker.

• How does one receiver one helper help matters?
  

  • Receiving-decoding can overlap execution.

• The one-reference messages eliminate synchronization.

  • The boss hands-off the message to the worker.

• Message hand-off with no synchronization is an open call.

Thread-per-Message Structure

• Why stop at one worker? Why not create a worker for each message.

  • Now the boss becomes a simple message dispatcher.

  • This is known as the thread-per-message structure.

• Threads per message decrease latency and improve throughput.

  • Particularly when message computations are I-O bound, or there are multiprocessors.

• However, too much of a good thing can be bad.

  • Too many threads may clobber performance via management overhead.

  • Message computation may not cover individual thread overhead.

Active Messages

• An active message contains code to be run by the receiver.

  class ActiveMessage
    ActiveRunnable runMe
    // other data for Runnable
  

• An active Runnable probably needs state to operate on.

  class ActiveRunnable
  implements Runnable
  
    private final ActiveMessage myHome
  
    ActiveRunnable(ActiveMessage msg)
      myHome = msg
  
    void run() 
      // work on myHome.data
  

• The receiver extracts the Runnable and runs it.

    ActiveMsg msg = (ActiveMsg) msgs.receive()
    (new Thread(msg.runMe)).start()
  

Thread Problems

• Java threads may not be the best tool for the job.

  • Thread provides a lean interface, with no extra parameters.

• What could be better than threads?

  • Threads may have high set-up and tear-down costs.

  • Thread churn may create hostile cache and virtual memory patterns.

• Recycling threads helps solve these problems.

  • Create and destroy costs are amortized over many executions.

  • Repeated thread use can burn-in the cache for better performance.

• Recycling threads is easy, but what about Runnables?

  • Use indirection, the programmer's friend.

Executors

• Executing a Runnable binds it to a Thread and vice versa.
  

• An executor is a Runnable for executing Runnables.

  • Bind an executor to a thread, let the executor run the Runnables.
  

  class ThreadExecutor
  implements Runnable
  
    void run()
      loop
        msg = msgs.receive()
        msg.runMe.run()
  

• Executors have the advantage of separating threads and runnables.

  • Replace threads with something better, if needed.

  • Replace the Runnable too.

Worker Threads

• With replaceable Runnables, we can now cache threads.

  • Caching preserves a productive memory footprint.

  • Reusing them minimizes set-up and tear-down overhead.

• Such threads are called worker threads.

  • Also known as background threads, and sometimes as daemon threads.

    • Java has a different interpretation for daemon threads, though.

• Worker threads may have a boss, or may coordinate among themselves.

  • The boss can create and remove workers, and shuffle messages.

Design Choices

• Be careful in re-creating Java threads as worker threads.

  • But, they can be simpler and more optimized than Java threads.

• Worker threads work best in anonymity.

  • But this re-introduces synchronization again.

• Pool size can be adjusted to match the load.

  • Worker thread resource use is the issue.

• Make sure you cover stopping as well as starting.

  • You have to implement a cancellation protocol too.

Events

• An event is a pure-data message, usually one-way.

• Worker threads act as intermediaries between event producers and event consumers.

  • Producers and consumers could be the same computation.

• An event queue usually separates producers and consumers.

  • Careful implementation also provides one-reference instances.

    • But the queue itself is not a one-reference instance.

• Make sure events are enabled after their event handlers are.

• The event handler should never block.

  • In fact, Events should execute quickly

• Events are lower overhead messages, but are finer grained.

Timers

• Queues can delay execution.

  • This is a problem or a feature.

• If it's a problem, the queue can be managed with time-based priority.

• If it's a feature, execution can be delayed until a particular time.

  • Or can occur every so often.

• Timers let worker threads execute at specified times, or for specified times.

  • Timers may be resident in the queue, or in the workers, or both.

• Daemon threads may rely on timers too.

• Dealing with delays can be a problem.

• Cancellation or rescheduling are options too.

Polling and Event-Drive I-O

• Messages frequently arrive over sockets or other I-O channels.

• I-O costs are often worse than thread costs.

  • Including channel setup and tear-down, as well as transmission costs.

• I-O message supply is often unbounded.

  • The other end runs on arbitrarily many other systems.

• The system may or may not support blocking vs. non-blocking I-O.

• A thread per I-O stream provides low latency and high throughput.

• Under high I-O demands, aggregation may be appropriate to reduce thread overhead.

I-O Driven Structures

• Session-based I-O uses one thread per connection.

  • Provides good latency and throughput.

  • Relatively easy to implement.

  • Doesn't scale well, and may waste resources.

• An event-driven style separates message I-O and processing.

  • A single thread reads all channels, enqueuing messages

  • An arbitrary number of workers dequeue messages and reply.

  • More complex than one thread per connection.

  • Increases latency, but also possibly throughput.

  • Scalable, and even dynamic.

Polling

• Low demand services may get away with only one worker thread.

  • The thread reads the message and then executes it.

• This requires polling in the absence of asynchronous I-O.

  • Blocking on the wrong channel is fatal.

• This scheme doesn't scale well at all.

  • An increase in clients or in client requests swamp the worker quickly.

• Stream-based I-O can deliver partial messages, requiring intermediate storage.

• Request responses should be short.

Points to Remember

• Don't share variables, share synchronization.

  • It's simpler and more flexible.

• Consider Message-based communication among threads.

  • Synchronization becomes an issue, though.

• Rolling your own Runnables can solve Thread problems.

  • More efficient and better tailored execution.

• Organize pools of custom threads.

  • With care, minimal synchronization will be required

• I-O and custom threads work well together.

  • In either event-driven or polling forms.

This page last modified on 29 July 2003.