DragonFly (the new BSD on the sky) has a new concept for implementing {critical sections}[CriticalSections], called Serializing Tokens.

Before I talk about kernel threads, let me clarify that kernel threads are the same as kernel level threads. A kernel level thread (or kernel thread) does not neccessarily run in privileged mode, but is part of the kernel. Threads running in privileged mode are called kernel-mode threads or better: privileged threads. Privileged mode = protected mode on x86, or supervisor mode on some other architectures like 68k.

Each light-weight kernel thread (LWKT) in DragonFly can hold zero or more serializing tokens. The LWKT scheduler guarantees that a running thread is not preempted by any other thread holding the same serializing token. If a thread blocks or yields (= giving up it’s time-slice), then the LWKT scheduler is allowed to run a thread that has a serializing token in common with the blocking or yielding thread (or one with no token in common). Thus, when a thread blocks or yields, it automatically leaves it’s critical section until it is running again, and it is responsible for all possible harm that may result due to leaving the critical section.

According to Matt Dillon, using serializing tokens, "there are theoretically no unresolvable deadlock situations". But livelocks can happen (in the initial implementation). The following code example demonstrates this (pseudo Ruby-code):

# serializing token T
T = Token.new

# thread A with token T
A = Thread.new(T) {
  loop do
    # neither block, nor yield
  end
}

# thread B with token T
B = Thread.new(T) {
  ...
}

If thread A is started before B, then thread B will never get scheduled to run as long as thread A is running. And in the example above, thread A is running forever.

In a multi-threaded kernel (or more generally in any multi-threaded application), you sometimes have to prevent two or more threads from reading or writing to the same data structure. Otherwise unexpected results may appear, depending on the order in which the threads run (race conditions). Sections of code that are not allowed to be in execution by more than one thread are called critical sections.

Example (in pseudo Ruby code):

# global data
$AMOUNT = 1000

critical_section {
  amount = $AMOUNT
  amount += 10
  $AMOUNT = amount
}

Imagine that the critical section in the example above could be entered and executed by two threads A and B. First, thread A enters the section and executes the first two lines, but before it can write the result back to the global variable, it gets preempted by thread B. Thread B now reads the current value of $AMOUNT, which is at this time still 1000. Thread B is not interrupted and finishs the section by writing back it’s new calculated result of 1010 to $AMOUNT. Now, thread A comes back to life and proceeds with it’s execution where it was interrupted by thread B (before the last line) and writes it’s result (which is 1010, too) into the $AMOUNT variable.

Clearly, the result is wrong! It should be 1020! And if there would have be no interruption of thread A by thread B, the result would be 1020. These kinds of errors are very hard to find, as in 99.999% of all cases the correct result is calculated.

Critical sections are usually implemented with mutexes. See SyncPrim for more about this topic and synchronization in general.

start summary::

There are lots of different mechanisms for preventing unwanted concurrent data-access, which might lead to race-conditions. Ordered from low to high-level some of them are:

1. Semaphores
2. Monitors
3. Tuple Spaces
4. Join Calculus
5. Data-Flow Synchronization

end summary::

The last three are not only used for synchronization purposes, but also for communcation.

Semaphores

Semaphores are the most basic building block for synchronization. But it’s hard to use them in large, complex applications.

Monitors

Monitors instead are a synchronization construct (usually) built into the language. It’s behaviour is very similar to that of a mutex, but unlike a mutex which can be used in a very fine-grained manner, monitors are tied to methods. This fact might lead to increased use of condition variables and to more synchronization overhead.

Furthermore, monitors make the language much more complex, and introduce implicit assumptions. My knowledge of Java’s concurrency primitives is too little, but would you be able to tell, without looking at the specs, whether or not it’s possible to access an instance variable declared as public inside a synchronized class? This is exactly the point why C or C++ does not have monitors, as it is impossible to decide whether another object has access to a public instance variable, whose access should be serialized. I strongly believe in the pure OO way followed by Eiffel & Co (Smalltalk, Sather, Ruby …), where objects react solely on messages (methods) and instance variables are not direclty accessible from outside of the object, only through methods (a good compiler can then optimize the method-call away, e.g. similar what inline does in C++)

That monitors need not be built into the language is demonstrated by the next example:

require "monitor"

mon = Monitor.new         # create Monitor object
cond1 = mon.new_cond      # create new condition variable
cond2 = mon.new_cond      # create another new cv

Thread.start do
  mon.synchronize do
    # inside the monitor
    ...
    cond1.wait
    ...
    cond2.signal
    ...
  end # leave monitor
end

# proceed with next thread here...

The advantage of this approach is, that you can have multiple monitors inside your objects, each one acting on another set of methods. And, you can decide yourself when a monitor should be entered, which needn’t be the begin of a method. Cross-object monitors are possible as well.

The example above didn’t showed the use of monitors in combination with methods. Now, in Ruby, this becomes even easier:

class Queue
  include MonitorMixin

  def initialize
    super()           # initalize Monitor
    @cond = new_cond  # create cv
  end

  def get
    synchronize { ... @cond.wait  ... }
  end

  def put
    synchronize { ... @cond.signal ... }
  end
end

Tuple Spaces

Parts of this section are taken from my book "Ruby Developers Guide", Chapter 5.

A TupleSpace is a space or kind of database in which you can store arbitrary tuples of any length and type (may of course depend on the implemention). Three operations are defined on a TupleSpace:

in

Removes a matching tuple from the TupleSpace and returns it to the caller.

rd

Same as in but does not remove the tuple from the TupleSpace.

out

Puts a tuple into the TupleSpace where it is stored until a matching in operation is issued.

All three operations are performed atomically, that is, they are thread-safe. Pattern-matching is used to specify which tuples to fetch from the TupleSpace. Multiple identical tuples are allowed inside a TupleSpace, similar as multiple tokens are allowed to sit in a place for a general S/T petrinet.

Producer-Consumer Example using TupleSpaces

An implementation in Ruby is given below. Note that the methods write and take are used for in and out respectively.

require "rinda/tuplespace"

ts = TupleSpace.new

# init with 2 credits
2.times { ts.write ['credit'] }

# producer thread
Thread.new {
  loop do
    ts.take ['credit']

    sleep 1
    puts "P: car produced"

    ts.write ['car']
    puts "P: car delivered"
  end
}

# consumer thread
Thread.new {
  loop do
    ts.write ['credit']
    puts "C: car ordered"

    ts.take ['car']
    puts "C: car received"

    sleep 3
  end
}

Both the consumer and the producer thread synchronize to each other using a TupleSpace. The tokens in the "Cars" place (see figure below) are represented in the TupleSpace by car tuples, and the "Credit" tokens by credit tuples. The other places of the petrinet are not used in the TupleSpace example.

With Rinda, Ruby’s version of Linda, we used in the example above, it’s very easy to even distribute the TupleSpace accross a TCP/IP network. Just replace the second line with the following two lines:

DRb.start_service
ts = DRbObject.new(nil, "druby://host_running_ts:0")

Then start anywhere on the network a remote TupleSpace:

require "rinda/tuplespace"

DRb.start_service("druby://hostname:0", TupleSpace.new)
gets   # [return] to exit

Rinda and DRb (Distributed Ruby) are part of the Ruby distribution. DRb is comparable to Java’s RMI (Remote Method Invocation), but is (a) much easier to use, and (b) written in pure Ruby in around 500 lines (the full package with lots of other useful libraries including SSL, ACLs, different object id converters, is around 2500 lines).

Join Calculus

The Join Calculus is similar to a TupleSpace where you can wait on a set of tuples at once. Only if the join condition of a function is fulfilled (usually this means waiting for more than one tuple) it is executed.

JoCaml

JoCaml is a dialect of Objective Caml and implements the Join Calculus. It is best suited for concurrent and distributed applications.

In the example below, we define a concurrent counter.

let def count! n | inc () = count (n+1) | reply to inc
     or count! n | get () = count n | reply n to get
;;

The count! is an asynchronous channel, which means that an invocation will return immediatly back to the caller and does not return any value. Each asynchronous channel can be seen as a named tuple in a TS. A synchronous channel (without an !) instead blocks the caller until the execution terminates, or if it’s definition is used in a join pattern like count! n | inc (), the reply to directive must be used to return to the caller of inc.

Now, let’s use the counter. We first have to initialize it by issuing spawn { count 0 }. In TupleSpace-terms, this would store a ["count!", 0] tuple in the TS. To increase the counter we then issue an inc() operation. If there’s a count! tuple (as there is), this triggers the execution of the first line of the definition of our counter, and consumes the count! tuple, binding the n in the definition to the tuple’s value (0 in our case). It then proceeds with executing the right hand side of the definition (everything after the =). The vertical bar separating the count (n+1) and reply to inc means that both terms are executed in parallel, i.e. in different threads. With the count (n+1), we store back the increased tuple to the TS, similar as we did at the beginning with the value zero, and with reply to inc we return to the caller of inc. Exactly the same happens when calling get (except that it returns the current counter value to the caller).

The count! channel is used as both a mutex and a storage for the counter value.

Join Patterns for Ruby

This is my implementation of Join Patterns for Ruby using a TupleSpace provided by Rinda. You can get it here. It’s nothing more than a proof of concept and should not be used for serious development.

Below we implement the concurrent counter in Ruby.

js.let_def "count! n | inc ()" do
  send "count!", @n+1
  reply_to "inc"
end

js.let_def "count! n | get ()" do
  send "count!", @n
  reply_to "get", @n
end

# initialize counter with 4
js.send "count!", 4

# you now can increment from everywhere

js.send "inc"
js.send "inc"

p (js.send "get") # => 6

Data-Flow Synchronization

Mozart/Oz

Mozart/Oz is a multi-paradigm language which uses data-flow for thread synchronization. One of it’s features are logic variables. A logic variable is either bound to a value or unbound. Once it is bound, it stays bound forever (inside it’s scope).

This type of variable is often used in functional languages, with the difference that variables in most of these languages (Haskell, ML) are always bound to some value.

Now, if you access an unbound variable in Mozart/Oz, the accessing thread will block until a value gets bound to it (from another thread of course). See the example below:

declare Cond1 Cond2 in

% Thread T1
thread
   {Show 'T1 a'}
   {Delay 1000}    % Wait a second
   Cond1 = true    % signal Cond1
   if Cond2 then   % wait for Cond2
      {Show 'T1 b'}
   end
end

% Thread T2
thread
   if Cond1 then   % wait for Cond1
      {Show 'T1'}
   end
   Cond2 = true    % signal Cond2
end

The output would be:

'T1 a'
'T1'
'T1 b'

This is only a very primitve example that uses logic variables as signal semaphores. Of course you can do a lot more with them, and very elegantly. If you’re interested, have a look at the Mozart/Oz manual, which provides you with many good examples.

PACT XPP

The PACT processor is another good example of data driven synchronization, this time implemented in hardware. It consists of an array of say, 32x32 cells, where each cell itself is configurable (FPGA) as either an ALU with a specific funtion, a register or another computation unit. An ALU cell for example has two inputs (two operands) and one output (result). Those inputs and outputs can be connected to other inputs and outputs of other cells.

As soon as data comes in from outside the processor, it flows through this network. Data may branch-off and flow in real-parallel (not quasi!) through different parts of the processor at the same time, or join back later into a single path.

So there may be situations, where an ALU is waiting for a second operand to complete its computation. But as it is usually not known during compile time when a packet arrives, a signaling mechanism is used at runtime to tell the ALU when an operand arrives at an input. Only if both operands are available, it begins its work and produces after n cycles a result on the output channel.

It may also happen that one path to input A of an ALU is much longer than the path to input B of the same ALU. This leads to a block of the whole short path to input B until the ALU has taken the packets from it’s inputs (it’s very similar to the consumer/producer problem). So the network inside the PACT processor can be seen and perfectly modeled as a petrinet, where each place only accepts one token. It might even be (long time since I read the PACT manual) that there are buffers between the outputs and inputs of the cells, so that the short path of the above example would not block immediatly if there is a packet-jam somewhere.