How do I...

UNO Execution Model

Introduction

The UNO execution model presented here is rather simple. It is build on four abstractions: threads, method execution steps, method calls, and time.

For simplicity (but without loss of generalization), assume a fixed, infinite set of threads. Conceptually, a thread transitions over time from being immaterial, to being active, to being done. See UNO Object Life Cycle Model for related material.

An active thread progresses by executing invocations of UNO interface methods. A method invocation is modelled as a (probably infinite) sequence of steps, where each step is either a local computation or a method call. Execution of a method finishes (the method call returns) after all its steps have been executed sequentially. (In practice, the exact sequence of steps of a method invocation will typically not be known until the method invocation is actually executed, but that is irrelevant here.) Initially, there is one active thread; how that thread is started is not covered here.

The local computation steps of a method invocation are not covered any further here; they are language-binding dependent. There are four sorts of method call steps:

A direct call synchronously starts to execute a new method invocation within the same thread. Once that method call returns, execution of the calling method invocation continues.
A spawning call asynchronously executes a new method invocation in a new thread. Execution of the calling method invocation immediately continues within the original thread. The new method invocation is executed in another, previously immaterial thread (that becomes active). Once that method call returns, the new thread transitions from being active to being done.
An asynchronous call is like a spawning call in that it executes a new method invocation in a new thread, and execution of the calling method invocation continues immediately. The difference is that execution of the spawned method invocation does not start until any previous asynchronous call originating from the calling thread has returned. (That is, for a given thread and a given point in time, there is at most one other thread that is executing an asynchronous call originating from the first thread.)
A synchronous call combines features of a direct call and an asynchronous call: It starts to execute a new method invocation within the same thread, but it blocks the current thread until any previous asynchronous call originating from that thread has returned.

We will see that invocations of UNO interface methods (normal or one-way) can be modelled as direct calls, synchronous calls, and asynchronous calls. Spawning calls are never used to model interface method invocations. Rather, they can be considered as language-binding–specific extensions.

Formal Specification

For any set S, let seq(S) stand for the set of arbitrary-length, ordered sequences over S. An element of seq(S) is written as ⟨s₁, …, s_k⟩, where k ≥ 0 and each s_i ∈ S. The notation ⟨r₁, …, r_j⟩ • ⟨s₁, …, s_k⟩ := ⟨r₁, …, r_j, s₁, …, s_k⟩ represents concatenation.

Let Step := DirectCalls ∪ SpawningCalls ∪ AsyncCalls ∪ SyncCalls be the disjoint union of all possible method calls (local computation steps can be ignored here). A method call is recursively represented as the sequence of method call steps that constitute the method invocation; that is, DirectCalls, SpawningCalls, AsyncCalls, SyncCalls ⊆ seq(Step).

Let Th be a fixed, infinite set of threads.

Information about threads that changes over time is encoded by the following functions that depend on time t:

The state of a thread, encoded as State_t: Th → {immaterial, waiting, active}. The waiting state is used to represent threads that have been spawned by an asynchronous call, and which have to wait for other outstanding asynchronous calls to return before they can become active. Also note that we do not need an extra done state here, active with an empty stack is used instead.
The stack of a thread, encoded as Stack_t: Th → seq(seq(Step)). A stack is represented as a sequence of executions. An execution represents the sequence of future steps a method invocation will execute.
Threads spawned by outstanding asynchronous calls made from a thread, encoded as Outstnd_t: Th → seq(Th).

Initial state:

for all h ∈ Th, State₀(h) := immaterial
for all h ∈ Th, Stack₀(h) := ⟨⟩
for all h ∈ Th, Outstnd₀(h) := ⟨⟩

Transitions:

start: h ∈ Th, ∀h′ ∈ Th. State_t(h′) = immaterial→
State_{t + 1}(h) := active
Stack_{t + 1}(h) := ⟨e⟩, for some e ∈ seq(Step)
direct call: h ∈ Th, State_t(h) = active, Stack_t(h) = ⟨⟨c⟩ • e⟩ • ee, c ∈ DirectCalls →
Stack_{t + 1}(h) := ⟨c, e⟩ • ee
spawning call: h ∈ Th, State_t(h) = active, Stack_t(h) = ⟨⟨c⟩ • e⟩ • ee, c ∈ SpawningCalls,
h′ ∈ Th, State_t(h′) = immaterial →
Stack_{t + 1}(h) := ⟨e⟩ • ee
State_{t + 1}(h′) := active
Stack_{t + 1}(h′) := ⟨c⟩
async call: h ∈ Th, State_t(h) = active, Stack_t(h) = ⟨⟨c⟩ • e⟩ • ee, c ∈ AsyncCalls,
h′ ∈ Th, State_t(h′) = immaterial →
Stack_{t + 1}(h) := ⟨e⟩ • ee
Outstnd_{t + 1}(h) := Outstnd_t(h) • ⟨h′⟩
State_{t + 1}(h′) := waiting
Stack_{t + 1}(h′) := ⟨c⟩
sync call: h ∈ Th, State_t(h) = active, Stack_t(h) = ⟨⟨c⟩ • e⟩ • ee, c ∈ SyncCalls, Outstnd_t(h) = ⟨⟩ →
Stack_{t + 1}(h) := ⟨c, e⟩ • ee
return: h ∈ Th, State_t(h) = active, Stack_t(h) = ⟨⟨⟩⟩ • ee →
Stack_{t + 1}(h) := ee
async unblock: h ∈ Th, Outstnd_t(h) = ⟨h′⟩ • hh,
h′ ∈ Th, State_t(h′) = waiting →
State_{t + 1}(h′) := active
async done: h ∈ Th, Outstnd_t(h) = ⟨h′⟩ • hh,
h′ ∈ Th, State_t(h′) = active, Stack_t(h′) = ⟨⟩ →
Outstnd_{t + 1}(h) := hh

The invocation of a normal (not one-way) UNO interface method can be modelled as either a synchronous call or a direct call. Modelling it as a synchronous call is preferred (to maintain the general properties of asynchronous calls, see below), but there can be cases where a direct call is chosen for performance reasons. For example, method invocations within one language binding are often implemented as direct, language-binding–specific function calls, which can be very fast.

The invocation of a one-way UNO interface method can be modelled as an asynchronous call, a synchronous call, or a direct call. Modelling it as an asynchronous call is generally preferred. Again, modelling it as a direct call is mainly allowed to exploit performance advantages for intra–language-binding calls. Allowing to model it as a synchronous call appears to be a natural consequence of allowing to model it as a direct call.

Problems

Ideally, invocations of normal UNO interface methods would always be modelled as synchronous calls, and invocations of one-way UNO interface methods would always be modelled as asynchronous calls. Additionally allowing weaker calls (direct calls for normal method invocations, synchronous and direct calls for one-way method invocations) has some undesirable consequences:

It is not guaranteed that a one-way method invocation is executed concurrently with the calling thread. For example, the following pseudo-code will not work if the call to m() is a synchronous or direct call:
```
  // body of some method:
  ...
  call one-way method m();
  trigger event E;
  ...

  // body of one-way method m():
  ...
  wait for event E;
  ...
```
Also, if the call to m() is a synchronous call, and there are any outstanding asynchronous calls originating from the current thread, the thread will unexpectedly block at the call to m() until all outstanding asynchronous calls have returned.
Generally, it should hold that no two independent one-way method invocations originating from the same thread are executed concurrently. However, the current way of implementing UNO environments and bridges breaks that guarantee. Consider the following pseudo-code:
```
  // body of some method:
  ...
  call one-way method m1();
  call normal method m2();
  ...

  // body of normal method m2():
  ...
  call one-way method m1();
  ...
```
Assume that both calls to the one-way method m1() are asynchronous calls, made through remote UNO bridges (e.g., using URP bridges). If the call to the normal (not one-way) method m2() is a synchronous call, it will block until the first call to m1() has returned, so the second call to m1() cannot overlap with the first one. Even if the call to m2() is a direct call, and both calls to m1() are made through the same URP bridge instance, URP will guarantee that the two calls to m1() are executed sequentially. But if the call to m2() is a direct call, and the two calls to m1() are made through different URP bridge instances, the guarantee will be violated.
This for example happens when the first call to m1() and the call to m2() are made from a C++ language environment (with a C++–URP bridge making the asynchronous remote call to m1()), the call to m2() is an in-process switch to a Java language environment (via a JNI bridge, as a direct call), and the second asynchronous remote call to m1() is then made through a Java–URP bridge.
The formal specification could be updated to more faithfully model the current behaviour. Sketch: The notion of a synchronization group would need to be introduced. Every asynchronous or synchronous call would be tagged with a specific synchronization group, and the single value Outstnd_t(h) of a thread h would be replaced by a set of values, one for each synchronization group involved. Asynchronous and synchronous calls originating from one thread would then only be synchronized within a single synchronization group, not across different synchronization groups.

The free and open productivity suite

UNO Execution Model

Introduction

Formal Specification

Problems