Dijkstra and Hoare did not separate concurrency into distinct domains of synchronisation and communication. Dijkstra addressed communication via shared state and synchronising operations, whereas Hoare established interaction as the foundation of a compositional behavioural model.
The similar names Cooperating Sequential Processes and Communicating Sequential Processes may suggest a misleading contrast: that Dijkstra’s processes synchronise while Hoare’s communicate. In fact, Dijkstra explicitly employed the language of communication, encompassing mechanisms such as semaphores (the famous producer-consumer algorithm). Some kernels will even compose and provide Message Queues objects with semaphores (like XINU).
Hoare, by contrast, made communication events the central vocabulary for describing concurrent systems. Both approaches focus on coordination, differing primarily in what each model treats as fundamental.
The more meaningful distinction lies not between communication and synchronisation, but between state-centred cooperation and interaction-centred behaviour.
Coordination Comes First
Concurrent tasks coordinate to protect shared state, transfer data, signal events, and establish execution order. Distinct mechanisms can serve the same purpose (for instance, a one-slot queue can replace a binary semaphore, a classic example). The relevant engineering question is not the categorical classification of a primitive, but rather the specific contract it establishes, such as retained state, capacity, ownership, wake-up rules, blocking, timeout, and ordering.
Cooperating Sequential Processes: State and Discipline
Dijkstra’s EWD 123 introduces loosely connected sequential processes. He asserts that cooperating processes must communicate and subsequently examines common variables, mutual exclusion, semaphores, producer-consumer buffers, deadlock, and correctness.
The central focus of this approach is state and operational discipline. Correctness depends on the representation of shared objects, the indivisibility of operations, and the preservation of required properties across all possible interleavings. While execution can be described as a sequence of events, the model retains the shared state that these events modify.
Communicating Sequential Processes: Behaviour and Composition
Hoare’s 1978 Communicating Sequential Processes (CSP) introduced a concurrent programming language in which a fixed set of named processes used synchronous input and output directed at each other. The source or destination was a process name rather than an independent queue object. Communication was completed through matching input and output operations.
CSP subsequently evolved into a process algebra. Processes are characterised by the events they may participate in and are composed using operators for sequencing, choice, parallelism, hiding, and refinement. The communication primitive does not assume the existence of a buffer; instead, a buffer can be explicitly represented as a stateful process that receives, stores, and forwards. This approach shifts the focus of reasoning from protecting shared state to describing and comparing process behaviour. The classical, untimed CSP models discussed here abstract away CPU priorities and execution costs. While these factors may be significant in implementation, they are not included in the semantic abstraction used to define traces, failures, divergence, or refinement.
The Difference, Without the False Dichotomy
| Question | Dijkstra’s cooperating processes | Classical CSP |
| Primary abstraction | Shared state plus disciplined operations. | Processes composed through events. |
| Communication | Common variables, semaphores, buffers, and conditions. | Synchronous interactions between processes. |
| Correctness focus | Mutual exclusion, invariants, progress, and deadlock. | Traces, failures, divergence, and refinement. |
| Buffering | An explicit protected or shared-state object. | An explicitly modelled process. |
| CPU priority | Part of the implementation and analysis when relevant. | Abstracted from the untimed core models. |
Why am I talking about CSP?
RK0 is not a CSP and does not implement a process algebra. RK is a fixed-priority real-time kernel supporting statically initialised tasks and optional pool-backed dynamic task creation. Shared memory remains available.
The kinship is architectural: RK0 makes coordination contracts that are stable and have little to no overlap. Event flags, semaphores, mutexes with optional priority inheritance, bounded message queues, task-owned ports, channels, and the Most-Recent Message protocol have distinct rules for retention, ownership, capacity, copying, blocking, and wake-up.
Those distinctions are substantive. To name a few: a full/empty message queue (mailbox) may block a sender/receiver; MRM publishes and retrieves the most recently published message; a semaphore counts availability; a mutex transfers ownership; a port binds a message queue to an exclusive receiving task; a channel represents an invocation relationship; a periodic sleep might preserve phase or run count if drifting.
Going further, as it is a word particularly relevant for CSP, an RK_CHANNEL (a Call Channel) is a bounded request-pointer queue with one server. kChannelCall enqueues a request descriptor and blocks the caller until kChannelDone is signalled by the callee. kChannelAccept lets the server receive the request and temporarily adopt the caller’s effective priority (inspired by QNX). The descriptor carries request and response pointers.
At the application level, this resembles a synchronous procedure call, but it is not CSP rendezvous. Requests may queue; the server is a scheduled task; bounded timeouts exist; and completion has explicit priority and memory-pool effects. The useful similarity is that the requester-server relationship is explicit.
Finishing: Where Real Time Changes the Model
In classical CSP, an event is defined as an abstract, observable occurrence: the model records that an interaction occurred and constrains its timing, but typically omits details of the scheduler and data-structure operations required for implementation. In contrast, RK0 implements interactions through specific kernel services, whose execution may involve queue operations, bounded capacity, blocking, timeout handling, waiter selection, priority inheritance or adoption, and interference from higher-priority tasks.
These implementation details serve as inputs to fixed-priority response-time analysis. Consequently, RK0’s value proposition is not “CSP in C,” but rather the provision of explicit coordination contracts within a scheduler whose costs and blocking behaviour can be systematically analysed. Some kernels are strictly message-passing kernels and cannot be classified as a CSP algebra – Mach, MINIX, QNX, L4, to name a few.
RK0 does not prohibit shared memory, does not reduce all coordination to rendezvous, and is not strictly a message-passing kernel. Instead, it provides differentiated primitives designed to make architectural intent explicit. This approach reflects the intuition that a concurrent system should be understood through the interactions among its tasks, combined with the priorities, blocking rules, and operational semantics characteristic of a real-time kernel.
Leave a Reply