Picos — Interoperable effects based concurrency

Introduction

Picos is a systems programming interface between effects based schedulers and concurrent abstractions. Picos is designed to enable an ecosystem of 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
• integrations 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 the Picos interface may not always 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 concurrent abstractions. Two phrases, Picos compatible and Implemented in Picos, 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 interface 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 interface. 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 interface.
• Safe: Picos should be designed with safety in mind. The implementation must be data race free. The interface 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 interface.

• Picos A systems programming interface between effects based schedulers and concurrent abstractions.

^{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_lwt Direct style Picos compatible interface to Lwt for OCaml 5.
• Picos_lwt_unix Direct style Picos compatible interface to Lwt with Lwt_unix for OCaml 5.
• Picos_randos Randomized multi-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 interface and for testing your own libraries implemented in Picos.}

Scheduler agnostic libraries

These are examples of libraries implemented in Picos.

• Picos_structured Basic structured concurrency primitives for 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.

^{These libraries are both meant to serve as examples of what can be done and to also provide practical means for programming with fibers. Hopefully there will be many more libraries implemented in Picos like these providing different approaches, patterns, and idioms for structuring concurrent programs.}

^{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 interface 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_mpscq Lock-free 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.