/*! @page uhood_switch Process Synchronizations and Context Switching
-@section uhood_switch_DES SimGrid as a Discrete Event Simulator
+@tableofcontents
+
+@section uhood_switch_DES SimGrid as an Operating System
SimGrid is a discrete event simulator of distributed systems: it does
not simulate the world by small fixed-size steps but determines the
a computation) and jumps to this date.
A number of actors executing user-provided code run on top of the
-simulation kernel[^kernel]. When an actor needs to interact with the simulation
-kernel (eg. to start a communication), it issues a <i>simcall</i>
-(simulation call, an analogy to system calls) to the simulation kernel.
-This freezes the actor until it is woken up by the simulation kernel
-(eg. when the communication is finished).
-
-The key ideas here are:
+simulation kernel. The interactions between these actors and the
+simulation kernel are very similar to the ones between the system
+processes and the Operating System (except that the actors and
+simulation kernel share the same address space in a single OS
+process).
+
+When an actor needs to interact with the outer world (eg. to start a
+communication), it issues a <i>simcall</i> (simulation call), just
+like a system process issues a <i>syscall</i> to interact with its
+environment through the Operating System. Any <i>simcall</i> freezes
+the actor until it is woken up by the simulation kernel (eg. when the
+communication is finished).
+
+Mimicking the OS behavior may seem over-engineered here, but this is
+mandatory to the model-checker. The simcalls, representing actors'
+actions, are the transitions of the formal system. Verifying the
+system requires to manipulate these transitions explicitly. This also
+allows to run safely the actors in parallel, even if this is less
+commonly used by our users.
+
+So, the key ideas here are:
- The simulator is a discrete event simulator (event-driven).
- In order to move forward in (simulated) time, the simulation kernel
needs to know which actions the actors want to do.
- - As a consequence, the simulated time can only move forward when all the
- actors are blocked, waiting on a simcall.
+ - The simulated time will only move forward when all the actors are
+ blocked, waiting on a simcall.
+
+This leads to some very important consequences:
- - An actor cannot synchronise with another actor using OS-level primitives
+ - An actor cannot synchronize with another actor using OS-level primitives
such as `pthread_mutex_lock()` or `std::mutex`. The simulation kernel
would wait for the actor to issue a simcall and would deadlock. Instead it
- must use simulation-level synchronisation primitives
+ must use simulation-level synchronization primitives
(such as `simcall_mutex_lock()`).
- - Similarly, it cannot sleep using `std::this_thread::sleep_for()` which waits
- in the real world but must instead wait in the simulation with
- `simcall_process_sleep()` which waits in the simulation.
+ - Similarly, an actor cannot sleep using
+ `std::this_thread::sleep_for()` which waits in the real world but
+ must instead wait in the simulation with
+ `simgrid::s4u::Actor::this_actor::sleep_for()` which waits in the
+ simulation.
- The simulation kernel cannot block.
Only the actors can block (using simulation primitives).
-## Futures
+@section uhood_switch_futures Futures and Promises
-### What is a future?
+@subsection uhood_switch_futures_what What is a future?
-We need a generic way to represent asynchronous operations in the
-simulation kernel. [Futures](https://en.wikipedia.org/wiki/Futures_and_promises)
-are a nice abstraction for this which have been added to a lot languages
-(Java, Python, C++ since C++11, ECMAScript, etc.).
-
-A future represents the result of an asynchronous operation. As the operation
-may not be completed yet, its result is not available yet. Two different sort
-of APIs may be available to expose this future result:
-
- * a <b>blocking API</b> where we wait for the result to be available
- (`res = f.get()`);
+Futures are a nice classical programming abstraction, present in many
+language. Wikipedia defines a
+[future](https://en.wikipedia.org/wiki/Futures_and_promises) as an
+object that acts as a proxy for a result that is initially unknown,
+usually because the computation of its value is yet incomplete. This
+concept is thus perfectly adapted to represent in the kernel the
+asynchronous operations corresponding to the actors' simcalls.
- * a <b>continuation-based API</b>[^then] where we say what should be
- done with the result when the operation completes
- (`future.then(something_to_do_with_the_result)`).
-C++11 includes a generic class (`std::future<T>`) which implements a blocking API.
-The [continuation-based API](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0159r0.html#futures.unique_future.6)
-is not available in the standard (yet) but is described in the
-[Concurrency Technical
-Specification](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0159r0.html).
+Futures can be manipulated using two kind of APIs:
-### Which future do we need?
+ - a <b>blocking API</b> where we wait for the result to be available
+ (`res = f.get()`);
-We might want to use a solution based on `std::future` but our need is slightly
-different from the C++11 futures. C++11 futures are not suitable for usage inside
-the simulation kernel because they are only providing a blocking API
-(`future.get()`) whereas the simulation kernel <em>cannot</em> block.
-Instead, we need a continuation-based API to be used in our event-driven
+ - a <b>continuation-based API</b> where we say what should be done
+ with the result when the operation completes
+ (`future.then(something_to_do_with_the_result)`). This is heavily
+ used in ECMAScript that exhibits the same kind of never-blocking
+ asynchronous model as our discrete event simulator.
+
+C++11 includes a generic class (`std::future<T>`) which implements a
+blocking API. The continuation-based API is not available in the
+standard (yet) but is [already
+described](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0159r0.html#futures.unique_future.6)
+in the Concurrency Technical Specification.
+
+`Promise`s are the counterparts of `Future`s: `std::future<T>` is used
+<em>by the consumer</em> of the result. On the other hand,
+`std::promise<T>` is used <em>by the producer</em> of the result. The
+producer calls `promise.set_value(42)` or `promise.set_exception(e)`
+in order to <em>set the result</em> which will be made available to
+the consumer by `future.get()`.
+
+@subsection uhood_switch_futures_needs Which future do we need?
+
+The blocking API provided by the standard C++11 futures does not suit
+our needs since the simulation kernel <em>cannot</em> block, and since
+we want to explicitly schedule the actors. Instead, we need to
+reimplement a continuation-based API to be used in our event-driven
simulation kernel.
-The C++ Concurrency TS describes a continuation-based API.
-Our future are based on this with a few differences[^promise_differences]:
+Our futures are based on the C++ Concurrency Technical Specification
+API, with a few differences:
- * The simulation kernel is single-threaded so we do not need thread
- synchronisation for out futures.
+ - The simulation kernel is single-threaded so we do not need
+ inter-thread synchronization for our futures.
- * As the simulation kernel cannot block, `f.wait()` and its variants are not
- meaningful in this context.
+ - As the simulation kernel cannot block, `f.wait()` is not meaningful
+ in this context.
- * Similarly, `future.get()` does an implicit wait. Calling this method in the
+ - Similarly, `future.get()` does an implicit wait. Calling this method in the
simulation kernel only makes sense if the future is already ready. If the
future is not ready, this would deadlock the simulator and an error is
raised instead.
- * We always call the continuations in the simulation loop (and not
- inside the `future.then()` or `promise.set_value()` calls)[^then_in_loop].
+ - We always call the continuations in the simulation loop (and not
+ inside the `future.then()` or `promise.set_value()` calls). That
+ way, we don't have to fear problems like invariants not being
+ restored when the callbacks are called :fearful: or stack overflows
+ triggered by deeply nested continuations chains :cold_sweat:. The
+ continuations are all called in a nice and predictable place in the
+ simulator with a nice and predictable state :relieved:.
-### Implementing `Future`
+ - Some features of the standard (such as shared futures) are not
+ needed in our context, and thus not considered here.
-The implementation of future is in `simgrid::kernel::Future` and
-`simgrid::kernel::Promise`[^promise] and is based on the Concurrency
-TS[^sharedfuture]:
+@subsection uhood_switch_futures_implem Implementing `Future` and `Promise`
-The future and the associated promise use a shared state defined with:
+The `simgrid::kernel::Future` and `simgrid::kernel::Promise` use a
+shared state defined as follows:
@code{cpp}
enum class FutureStatus {
}
template<class T>
-T simgrid::kernel::SharedState<T>::get()
+T simgrid::kernel::FutureState<T>::get()
{
if (status_ != FutureStatus::ready)
xbt_die("Deadlock: this future is not ready");
}
@endcode
-## Generic simcalls
+@section uhood_switch_simcalls Implementing the simcalls
+
+So a simcall is a way for the actor to push a request to the
+simulation kernel and yield the control until the request is
+fulfilled. The performance requirements are very high because
+the actors usually do an inordinate amount of simcalls during the
+simulation.
+
+As for real syscalls, the basic idea is to write the wanted call and
+its arguments in a memory area that is specific to the actor, and
+yield the control to the simulation kernel. Once in kernel mode, the
+simcalls of each demanding actor are evaluated sequentially in a
+strictly reproducible order. This makes the whole simulation
+reproducible.
-### Motivation
-Simcalls are not so easy to understand and adding a new one is not so easy
-either. In order to add one simcall, one has to first
-add it to the [list of simcalls](https://github.com/simgrid/simgrid/blob/4ae2fd01d8cc55bf83654e29f294335e3cb1f022/src/simix/simcalls.in)
-which looks like this:
+@subsection uhood_switch_simcalls_v2 The historical way
+
+In the very first implementation, everything was written by hand and
+highly optimized, making our software very hard to maintain and
+evolve. We decided to sacrifice some performance for
+maintainability. In a second try (that is still in use in SimGrid
+v3.13), we had a lot of boiler code generated from a python script,
+taking the [list of simcalls](https://github.com/simgrid/simgrid/blob/4ae2fd01d8cc55bf83654e29f294335e3cb1f022/src/simix/simcalls.in)
+as input. It looks like this:
@code{cpp}
# This looks like C++ but it is a basic IDL-like language
# (one definition per line) parsed by a python script:
-void process_kill(smx_process_t process);
+void process_kill(smx_actor_t process);
void process_killall(int reset_pid);
-void process_cleanup(smx_process_t process) [[nohandler]];
-void process_suspend(smx_process_t process) [[block]];
-void process_resume(smx_process_t process);
-void process_set_host(smx_process_t process, sg_host_t dest);
-int process_is_suspended(smx_process_t process) [[nohandler]];
-int process_join(smx_process_t process, double timeout) [[block]];
+void process_cleanup(smx_actor_t process) [[nohandler]];
+void process_suspend(smx_actor_t process) [[block]];
+void process_resume(smx_actor_t process);
+void process_set_host(smx_actor_t process, sg_host_t dest);
+int process_is_suspended(smx_actor_t process) [[nohandler]];
+int process_join(smx_actor_t process, double timeout) [[block]];
int process_sleep(double duration) [[block]];
smx_mutex_t mutex_init();
// Simcall number:
e_smx_simcall_t call;
// Issuing actor:
- smx_process_t issuer;
+ smx_actor_t issuer;
// Arguments of the simcall:
union u_smx_scalar args[11];
// Result of the simcall:
};
@endcode
-Then one has to call (manually:cry:) a
-[Python script](https://github.com/simgrid/simgrid/blob/4ae2fd01d8cc55bf83654e29f294335e3cb1f022/src/simix/simcalls.py)
-which generates a bunch of C++ files:
+When manually calling the relevant [Python
+script](https://github.com/simgrid/simgrid/blob/4ae2fd01d8cc55bf83654e29f294335e3cb1f022/src/simix/simcalls.py),
+this generates a bunch of C++ files:
* an enum of all the [simcall numbers](https://github.com/simgrid/simgrid/blob/4ae2fd01d8cc55bf83654e29f294335e3cb1f022/src/simix/popping_enum.h#L19);
Then one has to write the code of the kernel side handler for the simcall
and the code of the simcall itself (which calls the code-generated
-marshaling/unmarshaling stuff):sob:.
+marshaling/unmarshaling stuff).
In order to simplify this process, we added two generic simcalls which can be
used to execute a function in the simulation kernel:
}
@endcode
-### Blocking simcall
+### Blocking simcall {#uhood_switch_v2_blocking}
The second generic simcall (`simcall_run_blocking()`) executes a function in
the SimGrid simulation kernel immediately but does not wake up the calling actor
if (SIMIX_is_maestro())
xbt_die("Can't execute blocking call in kernel mode");
- smx_process_t self = SIMIX_process_self();
+ smx_actor_t self = SIMIX_process_self();
simgrid::xbt::Result<T> result;
simcall_run_blocking([&result, self, &code]{
});
@endcode
-### Asynchronous operations
+### Asynchronous operations {#uhood_switch_v2_async}
We can write the related `kernelAsync()` which wakes up the actor immediately
and returns a future to the actor. As this future is used in the actor context,
it is a different future
-(`simgrid::simix::Future` instead of `simgrid::kernel::Furuere`)
+(`simgrid::simix::Future` instead of `simgrid::kernel::Future`)
which implements a C++11 `std::future` wait-based API:
@code{cpp}
{
if (!valid())
throw std::future_error(std::future_errc::no_state);
- smx_process_t self = SIMIX_process_self();
+ smx_actor_t self = SIMIX_process_self();
simgrid::xbt::Result<T> result;
simcall_run_blocking([this, &result, self]{
try {
instead of one to do the same job (one in `kernelAsync()` and one in
`.get()`).
-## Representing the simulated time
-
-SimGrid uses `double` for representing the simulated time:
-
-* durations are expressed in seconds;
-
-* timepoints are expressed as seconds from the beginning of the simulation.
-
-In contrast, all the C++ APIs use `std::chrono::duration` and
-`std::chrono::time_point`. They are used in:
-
-* `std::this_thread::wait_for()` and `std::this_thread::wait_until()`;
-
-* `future.wait_for()` and `future.wait_until()`;
-
-* `condvar.wait_for()` and `condvar.wait_until()`.
-
-We can define `future.wait_for(duration)` and `future.wait_until(timepoint)`
-for our futures but for better compatibility with standard C++ code, we might
-want to define versions expecting `std::chrono::duration` and
-`std::chrono::time_point`.
-
-For time points, we need to define a clock (which meets the
-[TrivialClock](http://en.cppreference.com/w/cpp/concept/TrivialClock)
-requirements, see
-[`[time.clock.req]`](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf#page=642)
-working in the simulated time in the C++14 standard):
-
-@code{cpp}
-struct SimulationClock {
- using rep = double;
- using period = std::ratio<1>;
- using duration = std::chrono::duration<rep, period>;
- using time_point = std::chrono::time_point<SimulationClock, duration>;
- static constexpr bool is_steady = true;
- static time_point now()
- {
- return time_point(duration(SIMIX_get_clock()));
- }
-};
-@endcode
-
-A time point in the simulation is a time point using this clock:
-
-@code{cpp}
-template<class Duration>
-using SimulationTimePoint =
- std::chrono::time_point<SimulationClock, Duration>;
-@endcode
-
-This is used for example in `simgrid::s4u::this_actor::sleep_for()` and
-`simgrid::s4u::this_actor::sleep_until()`:
-
-@code{cpp}
-void sleep_for(double duration)
-{
- if (duration > 0)
- simcall_process_sleep(duration);
-}
-
-void sleep_until(double timeout)
-{
- double now = SIMIX_get_clock();
- if (timeout > now)
- simcall_process_sleep(timeout - now);
-}
-
-template<class Rep, class Period>
-void sleep_for(std::chrono::duration<Rep, Period> duration)
-{
- auto seconds =
- std::chrono::duration_cast<SimulationClockDuration>(duration);
- this_actor::sleep_for(seconds.count());
-}
-
-template<class Duration>
-void sleep_until(const SimulationTimePoint<Duration>& timeout_time)
-{
- auto timeout_native =
- std::chrono::time_point_cast<SimulationClockDuration>(timeout_time);
- this_actor::sleep_until(timeout_native.time_since_epoch().count());
-}
-@endcode
-
-Which means it is possible to use (since C++14):
-
-@code{cpp}
-using namespace std::chrono_literals;
-simgrid::s4u::actor::sleep_for(42s);
-@endcode
-
## Mutexes and condition variables
-## Mutexes
-
-SimGrid has had a C-based API for mutexes and condition variables for
-some time. These mutexes are different from the standard
-system-level mutex (`std::mutex`, `pthread_mutex_t`, etc.) because
-they work at simulation-level. Locking on a simulation mutex does
-not block the thread directly but makes a simcall
-(`simcall_mutex_lock()`) which asks the simulation kernel to wake the calling
-actor when it can get ownership of the mutex. Blocking directly at the
-OS level would deadlock the simulation.
-
-Reusing the C++ standard API for our simulation mutexes has many
-benefits:
-
- * it makes it easier for people familiar with the `std::mutex` to
- understand and use SimGrid mutexes;
-
- * we can benefit from a proven API;
-
- * we can reuse from generic library code in SimGrid.
-
-We defined a reference-counted `Mutex` class for this (which supports
-the [`Lockable`](http://en.cppreference.com/w/cpp/concept/Lockable)
-requirements, see
-[`[thread.req.lockable.req]`](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf#page=1175)
-in the C++14 standard):
-
-@code{cpp}
-class Mutex {
- friend ConditionVariable;
-private:
- friend simgrid::simix::Mutex;
- simgrid::simix::Mutex* mutex_;
- Mutex(simgrid::simix::Mutex* mutex) : mutex_(mutex) {}
-public:
-
- friend void intrusive_ptr_add_ref(Mutex* mutex);
- friend void intrusive_ptr_release(Mutex* mutex);
- using Ptr = boost::intrusive_ptr<Mutex>;
-
- // No copy:
- Mutex(Mutex const&) = delete;
- Mutex& operator=(Mutex const&) = delete;
-
- static Ptr createMutex();
-
-public:
- void lock();
- void unlock();
- bool try_lock();
-};
-@endcode
-
-The methods are simply wrappers around existing simcalls:
-
-@code{cpp}
-void Mutex::lock()
-{
- simcall_mutex_lock(mutex_);
-}
-@endcode
-
-Using the same API as `std::mutex` (`Lockable`) means we can use existing
-C++-standard code such as `std::unique_lock<Mutex>` or
-`std::lock_guard<Mutex>` for exception-safe mutex handling[^lock]:
-
-@code{cpp}
-{
- std::lock_guard<simgrid::s4u::Mutex> lock(*mutex);
- sum += 1;
-}
-@endcode
-
### Condition Variables
Similarly SimGrid already had simulation-level condition variables
@endcode
-## Notes
-
-[^kernel]:
-
- The relationship between the SimGrid simulation kernel and the simulated
- actors is similar to the relationship between an OS kernel and the OS
- processes: the simulation kernel manages (schedules) the execution of the
- actors; the actors make requests to the simulation kernel using simcalls.
- However, both the simulation kernel and the actors currently run in the same
- OS process (and use same address space).
-
-[^then]:
-
- This is the kind of futures that are available in ECMAScript which use
- the same kind of never-blocking asynchronous model as our discrete event
- simulator.
-
-[^sharedfuture]:
-
- Currently, we did not implement some features such as shared
- futures.
+## Notes
[^getcompared]:
blocks after having set a continuation to wake the actor when the future
is ready.
-[^promise_differences]:
-
- (which are related to the fact that we are in a non-blocking single-threaded
- simulation engine)
-
-[^promise]:
-
- In the C++ standard library, `std::future<T>` is used <em>by the consumer</em>
- of the result. On the other hand, `std::promise<T>` is used <em>by the
- producer</em> of the result. The consumer calls `promise.set_value(42)`
- or `promise.set_exception(e)` in order to <em>set the result</em> which will
- be made available to the consumer by `future.get()`.
-
-[^then_in_loop]:
-
- Calling the continuations from simulation loop means that we don't have
- to fear problems like invariants not being restored when the callbacks
- are called :fearful: or stack overflows triggered by deeply nested
- continuations chains :cold_sweat:. The continuations are all called in a
- nice and predictable place in the simulator with a nice and predictable
- state :relieved:.
-
[^lock]:
`std::lock()` might kinda work too but it may not be such as good idea to
