concurrent systems - modrpc/info GitHub Wiki

Table of Contents

Concurrency: Overview

Theories and Models

Data Process Networks

Kahn Process Network

  • G. Kahn. The Semantics of A Simple Language for Parallel Programming. IFIP'74
  • Wikipedia: https://en.wikipedia.org/wiki/Kahn_process_networks (very nice)
  • concurrent processes communicate through one-way FIFO channels with unbounded capacity (Details)
    • nonblocking send: need buffering
    • blocking read: peeking FIFO not allowed
    • channel is only shared between two processes: one consumer, one producer -- no multiple consumers/producers
    • a process cannot wait on multiple channels at once
  • Semantics:
    • process defines a mapping from input sequences to output sequences (c.f. strings to strings)
    • Scheduling algorithm does not affect behavior -- deterministic
  • Simulation (or Scheduling):
    • Let n processes be given.

Synchronous Dataflow (SDF)

Kurshan's Coordinating Processes

Actor Model of Computation

Process Calculi

CSP

  • C. A. R. Hoare. Communicating Sequential Processes. CACM'78
  • Communication:
    • explicit unbuffered channels for message passing
    • blocking send/blocking recv ==> requires rendezvous
  • Guarded command (Dijkstra-style w/ nondeterminacy)

Pi-calculus (and CCS)

Modeling Streams

  • Reactive systems are open systems and need to respond to a continual stream of stimuli from an environment which which they cannot synchronize.
  • Some argue that streams and functions on streams are a natural way to model reactive systems.
  • Two ways to model streams:
    • Recursive cons-model (Landin): defines streams recursively e.g. using cons-like list constructors -- treats them functionally using lazy semantics
      • Can be thought of as (Python) generator -- coroutine that may be considered to be a particular method of representing a list in which the creation of each list element is delays until it is actually needed.
      • Scheme models streams as two-element cell -- car contains the value of the head of the stream and cdr contains the procedure that computes the rest of the stream
      • I-structures used in dataflow languages
    • Channels: not functional because it is modified by appending new elements to it

Practices

Caltech Martin's Method

SystemC

SCEMI

SystemVerilog

Concurrency constructs

PL/I

  • entries, events, tasks, fork, join, wait, delay

Concurrent Pascal

  • class: has private var and procedures; class instance can be used by only one process
  • monitor: has private vars and procedures; monitor instance can be shared by processes
  • process: always-process
  • Wikipage: contains bounded buffer example

CSP

  • parbegin: fork-join
  • input/output: process-to-process (not process-channel-process, which is more flexible)
    • no automatic buffering: blocking input/output

Concurrent/Asynchronous Programming

Future vs Promises

Direct vs Continuation-passing style 

var running = true;    // Set false to stop.
while (running) {
  var time = await window.animationFrame;
  context.clearRect(0, 0, 500, 500);
  context.fillRect(time % 450, 20, 50, 50);
}
var running = true;    // Set false to stop.
tick(time) {
  context.clearRect(0, 0, 500, 500);
  context.fillRect(time % 450, 20, 50, 50);
  if (running) window.animationFrame.then(tick);
}
window.animationFrame.then(tick);

Ⓜ️ mv

⚠️ **GitHub.com Fallback** ⚠️