Realising concurrency

Introduction

Concurrent programming is a challenge of nowadays modern applications. There are many ways to realise concurrency, with HeavyweightProcesses?, or with LightweightProcesses? (aka threads), to have PreemptiveScheduling? (also called implicit scheduling) or CooperativeScheduling? (also called explicit scheduling) and so on.

This document presents some opinions and thought I gathered on some mailing lists (Io languages and Stackless, namely), plus some personal thought on how concurrency can be implemented.

Discussion

On multi-processor real threading vs interacting processes

I am quoting a mail from the Stackless ML [1]

 > I've been designing a large-scale server at work that could benefit
 > from running multiple threads in python simultaneously - aka real
 > threading, not the sequential-execution threading provided by the
 > standard python.

 (...)

 My personal taste is a bit different: I think it is more efficient
 to have free-running, disjoint interpreters, and to make object
 access between threads explicit, involving locks. This would allow
 to let the available CPUs? run at full speed as long as their
 computation is local, and only to involve some special communication
 wrappers run when information is interchanged.

 (...)

 My vision is about tasklets, which are run by a number of
 Python processes, one for each processor. These tasklets
 should be able to migrate, like "nomad tasks", to the
 processor with the smallest work-load.

This is exactly the perspective of Piranhas regarding multi-processor execution model: we have one or more kernels (only one per process) per processor. Kernels do not share memory, but rather synchronise important data.

If an agent requires to make some processing with specific data, it will either remotely manipulate the data, or (better, but depends on the distribution and load balancing policy) migrate to the kernel that contains most of the required resources, to minimise the resource (network, cpu) consumed in the remote communication mechanism.

In a follow-up to this message, Christian (Tismer), said the following thing:

 I also do believe that an algorithm that *tries*
 to keep information as local as possible, is also superior than
 others, which are requiring access to the whole "world" all the time.
 There will of course exist counter-examples, of whom to hear
 I'd be very glad and thankful.

Which I consider a good justification for the above model, in some way. If we consider that remote resource access is much more expensive than local resource access, this would think that the interacting process model is bad : because shared resources are not local, they have to be accessed through SHM or remote procedures -- threads would simply share the information, using locks to protect it from concurrent access. On the other hand if we take more care and the design and try to group resources locally and make the agents migrate to places where the resource is, we could consider the above as a good justification for the interacting process model.

Here is a quote (11-Jul-2003) from Steve Dekorte on the Io language Mailling list. The mail was entitled *Futures well suited for safe native threading?*:

 While it would be nice to make use of the extra processor, at most this 
 would give a 2x speedup, while using coros instead of OS threads can 
 result in 10-100x(or more) speed up over using many threads (Io 
 effectively already has "hyper" threads through the use of coroutines.) 
 Also, OS threads in the same process are a nightmare. If you really 
 need the extra processor, I'd suggestion using an Io VM instance for 
 each processor and giving each it's own thread or process and having 
 them communicate via sockets(ideally, using distributed objects). 
 Another nice thing about this model is that it scales as it doesn't 
 matter if the processes are on the same machine.

Again, using OS threads to support multiprocessor seems like some difficult, and maybe not that efficient. Sometimes OS threads can be effective, most notably when there is a few context switches and a few threads (see follow-ups on the Io ML).