Dynamic Networks Everything I described so far is common to CSP (Communicating Sequential Processes) and the Actor model. Here’s what makes actors more general: Connections between actors are dynamic. Unlike processes in CSP, actors may establish communication channels dynamically. They may pass messages containing references to actors (or mailboxes). They can then send messages to those actors. Here’s a Scala example: receive { case (name: String, actor: Actor) => actor ! lookup(name) } The original message is a tuple combining a string and an actor object. The receiver sends the result of lookup(name) to the actor it has just learned about. Thus a new communication channel between the receiver and the unknown actor can be established at runtime. (In Kilim the same is possible by passing mailboxes via messages.)
This post is an overview of the concurrency features of Java 7. This includes the Fork/Join Framework, the TransferQueue and the ThreadLocalRandom class
We've discussed differences between parallel, computational systems and concurrent, event handling systems. Areas of differences include:
Determinism: desirable vs impossible
Sign of parallel safety: same results vs correct results
Parallelism bugs: easy to pinpoint vs impossible to define
Queues: implementation detail vs part of the interface
Preemption: nearly useless vs nearly essential
In an earlier post I mentioned that one goal of the new introductory curriculum at Carnegie Mellon is to teach parallelism as the general case of computing, rather than an esoteric, specialized subject for advanced students. Many people are incredulous when I tell them this, because it immediately conjures in their mind the myriad complexities…
With the advent of multi-core processors concurrent programming is becoming indispensable. Scala's primary concurrency construct is actors. Actors are basically concurrent processes that communicate by exchanging messages. Actors can also be seen as a form of active objects where invoking a method corresponds to sending a message. The Scala Actors library provides both asynchronous and synchronous message sends (the latter are implemented by exchanging several asynchronous messages). Moreover, actors may communicate using futures where requests are handled asynchronously, but return a representation (the future) that allows to await the reply. This tutorial is mainly designed as a walk-through of several complete example programs Our first example consists of two actors that exchange a bunch of messages and then terminate. The first actor sends "ping" messages to the second actor, which in turn sends "pong" messages back (for each received "ping" message one "pong" message).
CUDA lets you work with familiar programming concepts while developing software that can run on a GP This is the first of a series of articles to introduce you to the power of CUDA -- through working code -- and to the thought process to help you map applications onto multi-threaded hardware (such as GPUs) to get big performance increases. Of course, not all problems can be mapped efficiently onto multi-threaded hardware, so part of my thought process will be to distinguish what will and what won't work, plus provide a common-sense idea of what might work "well-enough". "CUDA programming" and "GPGPU programming" are not the same (although CUDA runs on GPUs). CUDA permits working with familiar programming concepts while developing software that can run on a GPU. It also avoids the performance overhead of graphics layer APIs by compiling your software directly to the hardware (GPU assembly language, for instance), thereby providing great performance.
The result is a unified concurrency model providing both thread abstractions and event abstractions. We implemented the unified concurrency model in Haskell Our implementation demonstrates how to use these techniques by building an application-level thread library with support for multiprocessing and asynchronous I/O mechanisms in Linux. The thread library is type-safe, is relatively simple to implement, and has good performance. Application-level threads are extremely lightweight (scaling to 10,000,000 threads!) and our scheduler, which is implemented as a modular and extensible event-driven system, outperforms NPTL in I/O benchmarks.
This is an Erlang solution to "The Santa Claus problem", % as discussed by Simon Peyton Jones (with a Haskell solution using % Software Transactional Memory) in "Beautiful code". % He quotes J.A.Trono "A new exercise in concurrency", SIGCSE 26:8-10, 1994.
ATS is a PL with a highly expressive type system from the framework Applied Type System. Both dependent types and linear types are available in ATS. The current implementation of ATS (ATS/Anairiats) is written in ATS itself. It can be as efficient as C/C++ and supports * Functional programming. ATS uses eager call-by-value eval, it also supports lazy call-by-need evaluation. Linear types in ATS can often make FP run with high efficiency * Imperative programming. While features considered dangerous in other languages (e.g., explicit pointer arithmetic and explicit memory mgmt) are allowed in ATS, the type system of ATS is still able to guarantee that no run-time errors can occur * Concurrent programming. ATS, equipped with a multicore-safe implementation of garbage collection, can support multithreaded programming through the use of pthreads and parallel let * Modular programming. The module system of ATS is largely infuenced by that of Modula-3
Various concurrency primitives have been added to sequential programming languages, in order to turn them concurrent. Prominent examples are concurrent buffers for Haskell, channels in Concurrent ML, joins in JoCaml, and handled futures in Alice ML. Even though one might conjecture that all these primitives provide the same expressiveness, proving this equivalence is an open challenge in the area of program semantics. In this paper, we establish a first instance of this conjecture. We show that concurrent buffers can be encoded in the lambda calculus with futures underlying Alice ML. Our correctness proof results from a systematic method, based on observational semantics with respect to may and must convergence.
We introduce a new lambda calculus with futures, Lambda(fut), that models the operational semantics of concurrent statically typed functional programming languages with mixed eager and lazy threads such as Alice ML, a concurrent extension of Standard ML. Lambda(fut) is a minimalist extension of the call-by-value lambda-calculus that is sufficiently expressive to define and combine a variety of standard concurrency abstractions, such as channels, semaphores, and ports. Despite its minimality, the basic machinery of Lambda(fut) is sufficiently powerful to support explicit recursion and call-by-need evaluation. We present a static type system for Lambda(fut) and distinguish a fragment of Lambda(fut) that we prove to be uniformly confluent. This result confirms our intuition that reference cells are the sole source of indeterminism.
Peng Li's 2008 PhD dissertation, First, this dissertation presents a Haskell solution based on concurrency monads. This approach provides clean interfaces to both multithreaded programming and event-driven programming in the same application, but it also does not require native support of continuations from compilers or runtime systems. Then, this dissertation investigates for a generic solution to support lightweight concurrency in Haskell, compares several possible concurrency configurations and summarizes the lessons learned. The paper's summary explains what I like most about it: the project ... solves a systems problem using a language-based approach. Systems programmers, Haskell implementors and programming language designers may each find their own interests in this dissertation. Even if concurrency isn't your thing, section 6.3 describes the author's findings on the pros and cons of both purity and laziness in a systems programming context.
I didn't see anyone post them yet, so here are the slides from Tim Sweeney's POPL talk entitled "The Next Mainstream Programming Languages: A Game Developer's Perspective". I know Tim and I aren't the only game developers who follow LtU, and I figure even non-game developers might find them quite interesting!
concurrent paradigm, namely functional programming extended with threads and ports, which I call multi-agent dataflow programming. * The declarative concurrent subset (no ports) has no race conditions and can be programmed like a functional language. The basic concept is dataflow synchronization of single-assignment variables. A useful data structure is the stream, a list with dataflow tail used as a communication channel. * Nondeterminism can be added exactly where needed and minimally, by using ports - a named stream to which any thread can send. * All functional building blocks are concurrency patterns. Map, fold, filter, etc., are all useful for building concurrent programs. * Concurrent systems can be configured in any order and concurrently with actual use of the system. * Designing concurrent programs is any declarative part of the program can be put in own thread, loosening the coupling between system's parts * The paradigm is easily extended
Kamaelia - Concurrency made useful, fun In Kamaelia you build systems from simple components that talk to each other. This speeds development, massively aids maintenance and also means you build naturally concurrent software. It's intended to be accessible by any developer, including novices. What sort of systems? Network servers, clients, desktop applications, pygame based games, transcode systems and pipelines, digital TV systems, spam eradicators, teaching tools, and a fair amount more :)
The Little Book of Semaphores is a free (in both senses of the word) textbook that introduces the principles of synchronization for concurrent programming. In most computer science curricula, synchronization is a module in an Operating Systems class. OS textbooks present a standard set of problems with a standard set of solutions, but most students don't get a good understanding of the material or the ability to solve similar problems. The approach of this book is to identify patterns that are useful for a variety of synchronization problems and then show how they can be assembled into solutions. After each problem, the book offers a hint before showing a solution, giving students a better chance of discovering solutions on their own. The book covers the classical problems, including "Readers-writers," "Producer-consumer", and "Dining Philosophers." In addition, it collects a number of not-so-classical problems
Communication and Concurrency Lectures take place Monday and Thursday 14.00-14.50 in Appleton Tower, room M1, and are given by Colin Stirling. The syllabus of this module can be viewed in HTML through the Course Guide Background Reading: Milner's book "Communication and Concurrency, Prentice-Hall 1989" is important. Here is some background reading on ordinary, list, and tree (=structural) induction: ps pdf The Wikipedia article on Modal Logic makes interesting background reading. Note that there is a pointer to, but no article for, Hennessy-Milner logic: maybe you would like to write it?
with Philippa Gardner, Term 1, 2007/2008. Recommended Textbooks R. Milner. Communicating and Mobile Systems: the pi-Calculus. Cambridge University Press, various editions. (Introductory) D. Sangiorgi and D. Walker. The pi-Calculus: a Theory of Mobile Processes. Cambridge University Press, 2001. Online References and Tutorials A Calculus for Mobile Processes (Parts I/II) (by Robin Milner, Joachim Parrow, and David Walker). Also available from this site: [ Part I] [ Part II] The Polyadic Pi-Calculus: A Tutorial (by Robin Milner). Also available from this site: [(Postscript)] An Introduction to the Pi-calculus (by Joachim Parrow) A Brief Introduction to Applied Pi (by Peter Sewell) Asynchronous process calculi: the first-order and higher-order paradigms (Tutorial) (by Davide Sangiorgi)
Disco is an oss implementation of the Map-Reduce framework for distributed computing. Disco supports parallel computations over large data sets on unreliable cluster of computers. The Disco core is written in Erlang. Users of Disco typically write jobs in Python, which makes it possible to express even complex algorithms or data processing tasks often only in tens of lines of code. This means that you can quickly write scripts to process massive amounts of data. Disco was started at Nokia Research Center as a lightweight framework for rapid scripting of distributed data processing tasks. This far Disco has been succesfully used, for instance, in parsing and reformatting data, data clustering, probabilistic modelling, data mining, full-text indexing, and log analysis with hundreds of gigabytes of real-world data. Linux is the only supported platform but you can run Disco in the Amazon's Elastic Computing Cloud.
We have designed, implemented, and evaluated AtomCaml, an extension to Objective Caml that provides a synchronization primitive for atomic (transactional) execution of code. A first-class primitive function of type (unit->'a)->'a evaluates its argument (which may call other functions, even external C functions) as though no other thread has interleaved execution. Our design ensures fair scheduling and obstruction-freedom. Our implementation extends the Objective Caml bytecode compiler and run-time system to support atomicity. A logging-and-rollback approach lets us undo uncompleted atomic blocks upon thread pre-emption, and retry them when the thread is rescheduled. The mostly functional nature of the Caml language and the Objective Caml implementation's commitment to a uniprocessor execution model (i.e., threads are interleaved, not executed simultaneously) allow particularly efficient logging.
JoCaml is Objective Caml plus (&) the join calculus, that is, OCaml extended for concurrent and distributed programming. The new JoCaml is a re-implementation of the now unmaintained JoCaml by Fabrice Le Fessant. With respect to this previous implementation, main changes are: * Numerous syntax changes, we believe the new syntax to be cleaner. * Disparition of mobility features, sacrified for the sake of OCaml compatibility. * Much better compatibility with Objective Caml. o Source compatibility is about 99%, there are three new keywords (def, reply and spawn) ; or and & should definitely not be used as boolean operators. o Binary compatibility for matching versions.
RP has extremely good performance and scalability properties. Many uses of RP in the Linux Kernel have resulted in several orders of magnitude performance improvement compared to locking and transactional memory. Is it easy to program with? RP is not difficult to program with. Allowing each execution sequence to proceed using its own view of memory, by default, simplifies concurrent programming because it prevents memory from changing spontaneously. Threads are guaranteed to observe coherent memory, i.e., memory will contain values that were actually written at some time in the past. Read paths also exhibit deterministic performance characteristics, since they can not block or retry. This feature simplifies programming of time-sensitive systems. Nevertheless, RP is a new programming paradigm with a new interface and there are several ways to misuse it. Read Copy Update (RCU), an early example of RP, has seen extensive use in the Linux Kernel at over 2000 uses
One of those things I have to do fairly often in multithreaded programming is send off a whole bunch of threads to do their thing while I do something else on the main thread until they’re done. For example, imagine you’re downloading a bunch of images from the web, you don’t want to call httpGet one image right after another, because network resources are slow and processing them takes up almost no CPU time. But on the other hand, forkIO doesn’t return anything, so a thread thunk will have to put its contents somewhere you can access them later. Thus, my short, simple solution, far too small to bother putting up on Hackage: module Control.Concurrent.Future where import Control.Concurrent future :: IO a -> IO (MVar a) future thunk = do ref <- newEmptyMVar forkIO $ thunk >>= putMVar ref return ref forceAll :: [MVar a] -> IO [a] forceAll = mapM takeMVar