package picos

Picos — Interoperable effects based concurrency

Introduction

Picos, or pico-scheduler framework, is a framework for building interoperable elements of effects based cooperative concurrent programming models. Such models include elements such as

• schedulers that multiplex large numbers of user level fibers to run on a small number of system level threads,
• mechanisms for managing fibers and for structuring concurrency,
• communication and synchronization primitives, such as mutexes and condition variables, message queues, STMs, and more, and
• integration with low level asynchronous IO systems.

Picos is not intended to be an application level concurrent programming library or framework. If you are looking for a library or framework for programming concurrent applications, then Picos is probably not what you are looking for.

If you are the author of an application level concurrent programming library or framework, then Picos should not fundamentally be competing with your work. However, Picos and libraries built on top of Picos probably do have overlap with your work and making your work Picos compatible may offer benefits:

• You may find it useful that Picos provides parallelism safe building blocks for cancelation, which is a particularly tricky problem to get right.
• You may find it useful that you don't have to reinvent many of the basic communication and synchronization abstractions such as mutexes and condition variables, promises, concurrent bounded queues, channels, and what not.
• You may benefit from further non-trivial libraries, such as IO libraries, that you don't have to reimplement.
• Potential users of your work may be reassured and benefit from the ability to mix-and-match your work with other Picos compatible libraries and frameworks.

Of course, interoperability does have some costs. It takes time to understand Picos and it takes time to implement Picos compatibility. Implementing your programming model elements in terms of Picos primitives may not give ideal results. To address concerns such as those, a conscious effort has been made to keep Picos as minimal and unopinionated as possible.

Understanding cancelation

A central idea of Picos is to provide a collection of building blocks for parallelism safe cancelation. Consider the following characteristic example:

Mutex.protect mutex begin fun () ->
  while true do
    Condition.wait condition mutex
  done
end

Assume that the fiber executing the above computation might be canceled, at any point, by another fiber running in parallel. How could that be done both effectively and safely?

• To be effective, cancelation should take effect as soon as possible. In this case, cancelation should take effect even during the Mutex.lock inside Mutex.protect and the Condition.wait operations when the fiber might be in a suspended state awaiting for a signal to continue.
• To be safe, cancelation should not leave the program in an invalid state or cause the program to leak memory. In this case, the ownership of the mutex must be transferred to the next fiber or be left unlocked and no references to unused objects must be left in the mutex or the condition variable.

Picos allows Mutex and Condition to be implemented such that cancelation may safely take effect at or during calls to Mutex.lock and Condition.wait.

Cancelation in Picos

The Fiber concept in Picos corresponds to an independent thread of execution. A fiber may explicitly forbid or permit the scheduler from propagating cancelation to it. This is important for the implementation of some key concurrent abstractions such as condition variables, where it is necessary to forbid cancelation when the associated mutex is reacquired.

Each fiber has an associated Computation. A computation is something that needs to be completed either by returning a value through it or by canceling it with an exception. To cancel a fiber one cancels the computation associated with the fiber.

Before a computation has been completed, it is also possible to attach a Trigger to the computation and also to later detach the trigger from the computation. A trigger attached to a computation is signaled as the computation is completed.

The Trigger concept in Picos is what allows a fiber to be suspended and later resumed. A fiber can create a trigger, add it to any shared data structure(s), and await for the trigger to be signaled. The await operation, which is implemented by the scheduler, also, in case the fiber permits cancelation, attaches the trigger to the computation of the fiber when it suspends the fiber. This is what allows a fiber to be resumed via cancelation of the computation.

The return value of await tells whether the fiber was resumed normally or due to being canceled and the caller then needs to properly handle either case. After being canceled, depending on the concurrent abstraction being implemented, the caller might need to e.g. remove references to the trigger from the shared data structures, cancel asynchronous IO operations, or transfer ownership of a mutex to the next fiber in the queue of the mutex.

The architecture of Picos

The core concepts of Picos are

• Trigger — ability to await for a signal,
• Computation — a cancelable computation, and
• Fiber — an independent thread of execution,

that are implemented in terms of the effects

• Trigger.Await — to suspend and resume a fiber,
• Computation.Cancel_after — to cancel a computation after given period of time,
• Fiber.Current — to obtain the unique handle of the current fiber,
• Fiber.Yield — to cooperatively request rescheduling the current fiber, and
• Fiber.Spawn — to start new fibers,

that can be used to implement many kinds of higher level concurrent programming facilities.

Picos compatible

The idea is that in OCaml 5, effects based schedulers provide their own handlers for the Picos effects. By handling the Picos effects a scheduler becomes Picos compatible and allows any libraries built on top of Picos to be used with the scheduler.

Implemented in Picos

A scheduler is just one element of a concurrent programming model. Separately from making a scheduler Picos compatible, one may choose to implement other elements of the programming model, e.g. a particular approach to structuring concurrency or a particular collection of communication and synchronization primitives, in terms of the Picos primitives. Such elements can then be used on any Picos compatible scheduler.

Design goals and principles

• Simple: Picos should be kept as simple as possible.
• Minimal: Picos should be kept minimal. The dependency footprint should be as small as possible. Convenience features should be built on top of the framework.
• Safe: Picos should be designed with safety in mind. The implementation must be data race free. The framework should promote and always allow proper resource management.
• Unopinionated: Picos should not make strong design choices that are controversial.
• Flexible: Picos should allow higher level libraries as much freedom as possible to make their own design choices.

The documentation of the concepts includes design rationale for some of the specific ideas behind their detailed design.

Constraints Liberate, Liberties Constrain

Picos aims to be unopinionated and flexible enough to allow higher level libraries to provide many different kinds of concurrent programming models. While it is impossible to give a complete list of what Picos does not dictate, it is perhaps illuminating to explicitly mention some of those:

• Picos does not implement capability-based security. Higher level libraries with or without capabilities may be built on top of Picos.
• Picos never cancels computations implicitly. Higher level libraries may decide when cancelation should be allowed to take effect.
• Picos does not dictate which fiber should be scheduled next after a Picos effect. Different schedulers may freely use desired data structures (queues, work-stealing deques, stacks, priority queues, ...) and, after handling any Picos effect, freely decide which fiber to run next.
• Picos does not dictate how fibers should be managed. It is possible to implement both unstructured and structured concurrent programming models on top of Picos.
• Picos does not dictate which mechanisms applications should use for communication and synchronization. It is possible to build many different kinds of communication and synchronization mechanisms on top of Picos including mutexes and condition variables, STMs, asynchronous and synchronous message passing, actors, and more.
• Picos does not dictate that there should be a connection between the scheduler and other elements of the concurrent programming model. It is possible to provide those separately and mix-and-match.
• Picos does not dictate which library to use for IO. It is possible to build direct-style asynchronous IO libraries on top of Picos that can then be used with any Picos compatible schedulers or concurrent programming models.

Let's build an incredible ecosystem of interoperable concurrent programming libraries and frameworks!

Modules reference

We first open the Picos module

open Picos

and define a simple scheduler for running the examples in this document on OCaml 4

let run main =
  Picos_threaded.run ~forbid:false main

using the basic thread based scheduler and on OCaml 5

let run main =
  Picos_fifos.run ~forbid:false main

using the basic effects based scheduler that come with Picos as samples.

Auxiliary modules

Core modules

Please note that the example code snippets in this documentation may e.g. use the Domain and Unix modules in order to be able to describe Picos concepts in isolation in the absence of a Picos compatible scheduler.