Using Concurrency and Parallelism Effectively – I

The aim of this book is to show both students and practitioners that concurrent and parallel programming does not need to be as hard as it is often portrayed and in fact is often easier than building the equivalent sequential system. This will be achieved by presenting a set of example systems that demonstrate the underlying principles of parallel system design based upon real world examples. Each chapter will discuss the complete implementation of such a system, rather than presenting fragments of solutions. The approach will therefore be founded in principled engineering rather than a detailed exploration of the scientific underpinning. The science has been explored in many books but these have not demonstrated the engineering aspects of actually designing and building parallel systems.

For the purposes of this book; Concurrent means a system built from a set of processes that execute on a single processor. Parallel means that more than one processor is used to execute the processes and these communicate over some form of network. Within a parallel system it is likely that some of the processors will run some processes concurrently.

The book will use as its underpinning parallel environment a package called JCSP (Communicating Sequential Processes for Java) that is available under the LGPL software licence from the University of Kent, Canterbury UK (Welch, 2002) (Welch, 2013). This package implements the Communicating Sequential Process concepts developed by Professor Hoare some 30 years ago (Hoare, 1978) in a form that makes them easily accessible to the programmer. The book’s emphasis is on the engineering of parallel systems using these well-defined concepts without delving into their detailed theoretical aspects. The JCSP package essentially hides Java’s underlying thread model from the programmer in a manner that allows easy implementation of concurrent and parallel systems. It is immaterial whether a process is executed concurrently or in parallel, the process definition remains the same. The JCSP implementation is essentially a re-implementation of the occam programming language (Inmos Ltd, 1988) developed for the Inmos Transputer. (Wikipedia, 2013).

The underlying theory for JCSP is based upon Hoare’s Communicating Sequential Processes (Hoare, 1985) (Hoare, 1978) and is still the subject of research and development. CSP allows the designer to reason about the behaviour of their system, provided they use some well-defined patterns. In this book we shall be creating designs that use these design patterns to ensure that our designs behave correctly.

Understanding the principles behind parallel processing is an increasingly important skill with the advent of multi-core processors. Much effort has been made by processor manufacturers to hide the underlying parallel design techniques by providing tools that will take an existing code and extract some parallelism from it. This hides the real need to actually design and build parallel systems from the outset. Far too many people have been put off concurrent and parallel programming because they believe that they have to understand the underlying thread model supplied as part of the language or operating system environment. The goal of the book is to dispel all these misconceptions and show that parallel systems can be built quite easily with a very few simple design patterns and that such parallel systems can be easily implemented on a single processor or a collection of networked processors. Furthermore the advent of multi-core processors means that we can now start to build genuinely parallel systems for the commonest desktop workstations in which we can exploit the inherent parallelism more. The extension to a network of multi-core processors becomes even easier. Equally important is that the same design principles can be used to build mobile systems that permit interactions between mobile devices and fixed services using wireless (wi-fi) and Bluetooth technology.

1. A Challenge – Thinking Parallel
   1. Concurrency and Parallelism
   2. Why Parallel?
   3. A Multi-player Game Scenario
   4. The Basic Concepts
   5. Summary
2. Producer Consumer: A Fundamental Design Pattern
   1. A Parallel Hello World
   2. Hello Name
   3. Processing Simple Streams of Data
   4. Summary
   5. Exercises
3. Process Networks: Build It Like Lego
   1. Prefix Process
   2. Successor Process
   3. Parallel Copy
   4. Generating a Sequence of Integers
   5. Testing GNumbers
   6. Creating a Running Sum
   7. Generating the Fibonacci Sequence
   8. Generating Squares of Numbers
   9. Printing in Parallel
   10. Summary
   11. Exercises
4. Parallel Processes: Non Deterministic Input
   1. Reset Numbers
   2. Exercising ResetNumbers
   3. Summary
   4. Exercises
5. Extending the Alternative: A Scaling Device and Queues
   1. The Scaling Device Definition
   2. Managing A Circular Queue Using Alternative Pre-conditions
   3. Summary
   4. Exercises
6. Testing Parallel Systems: First Steps
   1. Testing Hello World
   2. Testing the Queue Process
   3. The Queue Test Script
   4. Summary
   5. Exercises
7. Deadlock: An Introduction
   1. Deadlocking Producer and Consumer
   2. Multiple Network Servers
   3. Summary
   4. Exercises
8. Client-Server: Deadlock Avoidance by Design
   1. Analysing the Queue Accessing System
   2. Client and Server Design Patterns
   3. Analysing the Crossed Servers Network
   4. Deadlock Free Multi-Client and Servers Interactions
   5. Summary
   6. Exercises
9. External Events: Handling Data Sources
   1. An Event Handling Design Pattern
   2. Utilising the Event Handing Pattern
   3. Analysing Performance Bounds
   4. Simple Demonstration of the Event Handling System
   5. Processing Multiple Event Streams
   6. Summary
   7. Exercises
10. Deadlock Revisited: Circular Structures
    1. A First Sensible Attempt
    2. An Improvement
    3. A Final Resolution
    4. Summary
11. Graphical User Interfaces: Brownian Motion
    1. Active AWT Widgets
    2. The Particle System – Brownian Motion
    3. Summary
    4. Exercises
12. Dining Philosophers: A Classic Problem
    1. Naïve Management
    2. Proactive Management
    3. A More Sophisticated Canteen
    4. Summary
13. Accessing Shared Resources: CREW
    1. CrewMap
    2. The DataBase Process
    3. The Read Clerk Process
    4. The Write Clerk Process
    5. The Read Process
    6. The Write Process
    7. Creating the System
    8. Summary
    9. Challenge
14. Barriers and Buckets: Hand-Eye Co-ordination Test
    1. Barrier Manager
    2. Target Controller
    3. Target Manager
    4. Target Flusher
    5. Display Controller
    6. Gallery
    7. Mouse Buffer
    8. Mouse Buffer Prompt
    9. Target Process
    10. Running the System
    11. Summary