21

I'm looking for some canonical, simple concurrency problems, suitable for demonstrating usage of a library for concurrent computations I'm working on.

To clarify what I mean by "concurrency": I'm interested in algorithms that utilize non-deterministic communicating processes, not in e.g. making algorithms like quicksort run faster by spreading the work over multiple processors. This is how I'm using the term.

I know about the Dining Philosophers Problem, and that would be acceptable, but I wonder whether there are any more convincing but equally simple problems.

Improve this question
0

5 Answers 5

Reset to default
13

Producer-Consumer problem.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

6

I generally use a simple "bank account transfer" scenario. For example I posted one such trivial case in this question on transactions.

It's a good case for exposition because:

  • Everyone understands the business problem.
  • It emphasises the importances of transactions in a concurrent environment.
  • You can easily extend the scenario (e.g. what if you want to calculate the sum of all current account balances while transactions are taking place?)

To demonstrate your concurrency library, you could probably start a thread running millions of transactions in this kind of scenario, and demonstrate how other threads can still see a consistent view of the world etc.

Improve this answer

1 Comment

Thanks! Though it's a bit dry, I think this one is the best of the answers so far.
3

I don't think there is a standard first program for demonstrating that concurrency is working, like "Hello world" for sequential programs.

More typical for concurrency are programs that demonstrate problems, for example concurrent counters that lose some counts without proper synchronization. Or random transfers between bank accounts that cause a deadlock if locking is done naively. (I did these when playing with Java concurrency.)

One thing that demonstrates concurrency and is relatively simple is to count cooperatively: The concurrent threads (or whatever) have an internal counter, which they send out to each other, and set to what they receive plus one. (I did that with three LEGO Mindstorms RCX over infrared some years ago, worked nicely.)

BTW: The "Hello world" of the embedded programmer is the blinking LED.

Improve this answer

1 Comment

Especially if you make it blink "HELLO WORLD" in Morse.
3

There used to be a sample Java applet (quite possibly still is) that you used to test what scheduling algorithm your JVM and underlying OS use. It animated two (or optionally more? can't remember) bars gradually filling up, each animated by a different thread at the same priority.

An equivalent that prints:

red 1 red 2 green 1 red 3 green 2

etc to the console, seems to me to be the closest thing in spirit to the bare bones nature of "hello, world". That is, "can I make the computer do something useless but visible?"

So in each thread you'd want a series of pauses (either busy-loops or sleeps, up to you, and which you choose might affect the output depending how your concurrency is scheduled), each followed by some output. You might want to synchronize the output -- not really essential, but if a line were to be broken up by the scheduler it would be awkward to read.

Then if your concurrency model is co-operative (either neolithic threads, or perhaps something co-routine-based), you have to add suitable yields as well, to prevent the red bar filling before the green bar starts. That tells you that you've successfully made your concurrent code interleave.

Improve this answer

Comments

1

You can ray trace "Hello" and "World" in separate threads. Or animate "Hello" while "World" is raytracing.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.