Friday, June 8, 2007

Threading in UIs.

Today's Problem

Andrew Stopford asked me a question today about the role of Threading in UI design. He pointed out that this topic is not very often discussed in treatises on UI design patterns such as MVC. I concur. Here are some thoughts of mine.

Threading Is Just An Engine

Firstly, I don't believe we should get too caught up with threading. Threading is just the engine used to maintain state and interleave execution of sequential processes. The problem with program design isn't usually that we have lots of threads running concurrently, it's that we have multiple Actors running around doing stuff.

Actors Run Around Doing Stuff

Let's say Alice and Betty both head down the hall to buy coffee from the vending machine. Alice gets there first. She whips out her changepurse and starts tediously counting out nickels and dimes. Betty arrives later but she's smarter. She has a dollar coin tucked behind her ear for just such coffee emergencies. Several things can happen here:

  • Betty might queue up behind Alice and be stuck waiting for awhile to gain access to the vending machine.
  • Betty might barge in front of Alice and buy her coffee first.
  • Betty might wait for Alice but just as Alice finishes Colin rushes in between her and the machine and starts counting out his change. Next it's Dennis, then Elmo and Francine.
  • Betty might wait for Alice but suddenly Medusa shows up and petrifies Alice right in front of the vending machine. So much for coffee this millenium.
  • Betty might wait for Alice only to discover that the vending machine is broken or out of coffee when she gets her turn.
  • Alice and Betty may pay for their coffee using the honor system in a nearby deposit box. They both drop in $1 then queue up to get coffee from the machine. After Alice gets her cup, Betty discovers that there's no more coffee. Unfortunately, she cannot void her transaction because the deposit box is locked.
  • The coffee machine might be equipped with a special extra serving station for just such occasions so Alice and Betty both get their coffee at the same time!
  • etc...

The real issue here is that multiple independent actors must share common resources through at least part of the transaction. Moreover, their actions effect the state of these resources and must be reconciled with the effects of other actors.

Zen and The Art of Model-View-Controller Maintenance

So what happens to our hypothetical UI when we've got multiple actors running around doing stuff? The View is observing the Model and dutifully informing the user about what's happening. The Controller is updating Model in response to user actions. Background threads are playing music, downloading files, crunching numbers and updating the Model as they progress. The Model needs to somehow coordinate all of the concurrent observers and actors. The View needs to be able to handle updates to the Model that are triggered by multiple actors (possibly in different threads). The Controller needs to be able to carry out transactions exactly as they was intended the instant the user clicked on some button despite everything else going on.

Wow! This is hard stuff! We need to step back and take a deep breath and meditate on what's going on here. The Actors in the system need to perform consistent transactions upon the Model. The Observers in the system need to preceive a consistent Model state at all times. Sooner or later everything hits the Model. Ah!

Designing Models for Concurrent Use

Everything depends on the Model. It follows that the design of the Model will dictate how the system behaves. Here are a few different approaches.

Note: These are all names and patterns I have just made up.

Option 1: Shared Model

The simplest way to make a Model safe for concurrent access is to add locks. Actors lock portions of the Model for the duration of a transaction. Observers lock portions of the Model while they read state and update themselves. The implementation probably involves reader/writer locks managed by the Model.

  • Pro: Existing models can easily be retrofitted for shared use by judicious application of locks.
  • Pro: Does not require any fancy or complicated framework support.
  • Con: Single point of failure.
  • Con: Priority inversion is rampant. An unimportant background task can trump an important foreground task or cause the application to become unresponsive.

Option 2: Transacted Model

Another solution is to negotiate for access to a Share Model on behalf of delimited transactions. These transactions are often called Jobs. Each Actor in the system may start up any number of Jobs. The Jobs have associated Scheduling Rules that determine whether they can safely be run concurrently or if they must be sequenced because they require exclusive access to common resources. Ordinarily, the user is unaware of these Jobs floating around except perhaps in the way of progress monitors or busy indicators that may be floating around. However, when the user attempts to initiate a Job that cannot be run immediately, the UI enters a modal state to inform the user that the Job has been blocked from executing because it conflicts with other Jobs already running. Often the user can then choose to cancel the Job, put it in the background or wait for it to complete. So there is still just a single Shared Model floating around but transactions are reified explicitly and can be controlled.

  • Remark: This is how Eclipse managed background jobs.
  • Pro: Provides more control than the plain Shared Model.
  • Pro: Jobs always run through to completion unless they are cancelled or encounter an error.
  • Pro: Jobs can be prioritized to avoid priority inversion. Unimportant background jobs can even be pre-empted, deferred or canceled to preserve responsiveness.
  • Con: This requires a lot more sophistication because each transaction must be declared as a job.

Option 3: Transacted Model With Snapshots

This is a refinement of the previous model. We still represent transactions explicitly as jobs. However, instead of having one common Shared Model, we provide each transaction with a Snapshot. The Snapshot captures the state of the Shared Model at the time the transaction began. The transaction periodically checkpoints or commits the changes made to its Snapshot back to the Shared Model. If a conflict occurs, the transaction may be rolled back and possibly retried. This pattern trades implementation complexity for reduced locking in the common case.

  • Pro: Read-only transactions initiated by Views cannot block read-write transactions initiated by Actors.
  • Pro: Views can spend more time updating their state from a Snapshot and still be guaranteed to observe a fully consistent state.
  • Con: Much more complex implementation (unless you're doing functional programming).
  • Con: It's not always clear what to do if a conflict occurs during transaction commit.

Option 4: Intentional Model

One idea is to add transitional states to the system. For example, when the Controller of the music player sends a request to the music playing loop to Stop, the Shared Model may enter a "stopping" state. Eventually the Shared Model will transition to the "stopped" state when the music playing loop actually does stop.

This technique works by enabling all transactions to be performed atomically by reflecting their intentions upon the Shared Model. The Shared Model enters a transitional state until the intentions are carried out. This eliminates some of the contention that might normally occur with a standard Shared Model because it only needs to be locked long enough to record the intentions.

  • Pro: In practice this works very well when the number of transitional states is small.
  • Pro: Locking overhead can be dramatically reduced.
  • Con: This is not really sophisticated enough to handle some cases well.
  • Con: All Actors and Observers now need to handle more states.

Option 5: Replicated Model

Another trick is to replicate the state across all Actors. For example, the Controller of a music playing application may maintain state about whether the play and pause actions are enabled. The music playing loop running in the background has its own state about whether the music is actually playing or not. The Controller and the music playing loop send messages to each other asynchronously to update their copy of the Replicated Model. Periodically they may rendezvous synchronously as well.

  • Remark: This is the keystone of Communicating Sequential Processes (CSP) architecture.
  • Pro: This approach is easiest to understand. Each component in the system encapsulates its own model state that it keeps up to date through interactions with other components.
  • Con: Some models cannot be replicated easily.
  • Con: Because there is no authoritative Shared Model, race conditions during asynchronous updates are particularly problematic.

How to Choose

It depends. What responsiveness guarantees do you want to provide to the user? How important is it that the progress of competing Actors be reified and controlled? How much contention do you expect and how badly will it impact the desired user experience? Do you have adequate framework support? How much sophistication can you manage in your UI layer?


Eric said...

i'm very interesting in you server side plug-in rchitecture,especially in the nested Container,how to implement it?could you show some detail?thanks

Jeff Brown said...

Catch me on MSN sometime at and we can talk about it.