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 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.

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 the core of 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.

Interoperability

Picos is essentially an interface between schedulers and other elements. Two phrases are used to describe the opposing sides of this contract.

Picos compatible

The idea is that schedulers provide their own handlers for the Picos effects. By handling the Picos effects a scheduler allows any libraries built on top of the Picos concepts to be used with the scheduler. Such a scheduler is then said to be Picos compatible.

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 concepts. Such scheduler agnostic elements can then be used on any Picos compatible scheduler and are said to be Implemented in Picos.

Design goals and principles

The core of Picos is designed and developed with various goals and principles in mind.

• 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!

Libraries

The Picos package is divided into multiple libraries.

Core

The only essential part of the package is the core framework.

• • Picos Framework for interoperable effects based concurrency.

^{Everything else is entirely opt-in and you are free to mix-and-match with any other Picos compatible schedulers and libraries implemented in Picos or develop your own.}

Sample schedulers

These are minimalistic, but fully-functioning, schedulers provided as samples.

• • Picos_fifos Basic single-threaded effects based Picos compatible scheduler for OCaml 5.
• • Picos_threaded Basic Thread based Picos compatible scheduler for OCaml 4.

^{You may find these useful for both understanding the core Picos framework and for testing your own libraries implemented in Picos.}

Scheduler agnostic libraries

These are examples of libraries implemented in Picos.

• • Picos_sync Basic communication and synchronization primitives for Picos.
• • Picos_stdio Basic IO facilities based on OCaml standard libraries for Picos.
• • Picos_select Basic Unix.select based IO event loop for Picos.

^{The IO libraries in this package are built only on top of the standard libraries distributed with OCaml and are hopefully useful for building simple applications. Bindings to asynchronous system IO libraries are outside the scope of this package.}

Auxiliary libraries

These have no dependency to the core Picos framework and are used in the implementation of the other libraries.

• • Picos_domain Minimalistic domain API available both on OCaml 5 and on OCaml 4.
• • Picos_exn_bt Wrapper for exceptions with backtraces.
• • Picos_fd Externally reference counted file descriptors.
• • Picos_htbl Lock-free hash table.
• • Picos_mpsc_queue Multi-producer, single-consumer queue.
• • Picos_rc External reference counting tables for disposable resources.
• • Picos_thread Minimalistic thread API available with or without threads.posix.

^{Some of these libraries might be moved to other packages in the future.}

Conventions

Many operation in the Picos libraries use non-blocking algorithms. Unless explicitly specified otherwise,

• non-blocking operations in Picos are atomic or strictly linearizable (i.e. linearizable and serializable), and
• lock-free operations in Picos are designed to avoid having competing operations of widely different complexities, which should make such operations much less prone to starvation.