Mastering Concurrency Programming with Java 8 E-Book

Javier Fernandez Gonzalez

• Herausgeber: Packt Publishing
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 520

Veröffentlichungsjahr: 2016

Beschreibung

Master the principles and techniques of multithreaded programming with the Java 8 Concurrency API

About This Book

• Implement concurrent applications using the Java 8 Concurrency API and its new components
• Improve the performance of your applications or process more data at the same time, taking advantage of all of your resources.
• Construct real-world examples related to machine learning, data mining, image processing, and client/server environments

Who This Book Is For

If you are a competent Java developer with a good understanding of concurrency but have no knowledge of how to effectively implement concurrent programs or use streams to make processes more efficient, then this book is for you.

What You Will Learn

• Design concurrent applications by converting a sequential algorithm into a concurrent one
• Discover how to avoid all the possible problems you can get in concurrent algorithms
• Use the Executor framework to manage concurrent tasks without creating threads
• Extend and modify Executors to adapt their behavior to your needs
• Solve problems using the divide and conquer technique and the Fork/Join framework
• Process massive data sets with parallel streams and Map/Reduce implementation
• Control data-race conditions using concurrent data structures and synchronization mechanisms
• Test and monitor concurrent applications

In Detail

Concurrency programming allows several large tasks to be divided into smaller sub-tasks, which are further processed as individual tasks that run in parallel. All the sub-tasks are combined together once the required results are achieved; they are then merged to get the final output. The whole process is very complex. This process goes from the design of concurrent algorithms to the testing phase where concurrent applications need extra attention. Java includes a comprehensive API with a lot of ready-to-use components to implement powerful concurrency applications in an easy way, but with a high flexibility to adapt these components to your needs.

The book starts with a full description of design principles of concurrent applications and how to parallelize a sequential algorithm. We'll show you how to use all the components of the Java Concurrency API from basics to the most advanced techniques to implement them in powerful concurrency applications in Java.

You will be using real-world examples of complex algorithms related to machine learning, data mining, natural language processing, image processing in client / server environments. Next, you will learn how to use the most important components of the Java 8 Concurrency API: the Executor framework to execute multiple tasks in your applications, the phaser class to implement concurrent tasks divided into phases, and the Fork/Join framework to implement concurrent tasks that can be split into smaller problems (using the divide and conquer technique). Toward the end, we will cover the new inclusions in Java 8 API, the Map and Reduce model, and the Map and Collect model. The book will also teach you about the data structures and synchronization utilities to avoid data-race conditions and other critical problems. Finally, the book ends with a detailed description of the tools and techniques that you can use to test a Java concurrent application.

Style and approach

A complete guide implementing real-world examples with algorithms related to machine learning, data mining, and natural language processing in client/server environments. All the examples are explained in a step-by-step approach.

Leseprobe

Table of Contents

Mastering Concurrency Programming with Java 8

Credits

About the Author

About the Reviewers

www.PacktPub.com

eBooks, discount offers, and more

Why subscribe?

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Errata

Piracy

eBooks, discount offers, and more

Questions

1. The First Step – Concurrency Design Principles

Basic concurrency concepts

Concurrency versus parallelism

Synchronization

Immutable object

Atomic operations and variables

Shared memory versus message passing

Possible problems in concurrent applications

Data race

Deadlock

Livelock

Resource starvation

Priority inversion

A methodology to design concurrent algorithms

The starting point – a sequential version of the algorithm

Step 1 – analysis

Step 2 – design

Step 3 – implementation

Step 4 – testing

Step 5 – tuning

Conclusion

Java concurrency API

Basic concurrency classes

Synchronization mechanisms

Executors

The Fork/Join framework

Parallel streams

Concurrent data structures

Concurrency design patterns

Signaling

Rendezvous

Mutex

Multiplex

Barrier

Double-checked locking

Read-write lock

Thread pool

Thread local storage

The Java memory model

Tips and tricks to design concurrent algorithms

Identify the correct independent tasks

Implement concurrency at the highest possible level

Take scalability into account

Use thread-safe APIs

Never assume an execution order

Prefer local thread variables over static and shared when possible

Find the more easily parallelizable version of the algorithm

Using immutable objects when possible

Avoiding deadlocks by ordering the locks

Using atomic variables instead of synchronization

Holding locks for as short a time as possible

Taking precautions using lazy initialization

Avoiding the use of blocking operations inside a critical section

Summary

2. Managing Lots of Threads – Executors

An introduction to executors

Basic characteristics of executors

Basic components of the executor framework

First example – the k-nearest neighbors algorithm

K-nearest neighbors – serial version

K-nearest neighbors – a fine-grained concurrent version

K-nearest neighbors – a coarse-grained concurrent version

Comparing the solutions

The second example – concurrency in a client/server environment

Client/server – serial version

The DAO part

The command part

The server part

Client/server – parallel version

The server part

The command part

Extra components of the concurrent server

The status command

The cache system

The log system

Comparing the two solutions

Other methods of interest

Summary

3. Getting the Maximum from Executors

Advanced characteristics of executors

Cancellation of tasks

Scheduling the execution of tasks

Overriding the executor methods

Changing some initialization parameters

The first example – an advanced server application

The ServerExecutor class

The statistics object

The rejected task controller

The executor tasks

The executor

The command classes

The ConcurrentCommand class

Concrete commands

The server part

The ConcurrentServer class

The RequestTask class

The client part

The second example – executing periodic tasks

The common parts

The basic reader

The advanced reader

Additional information about executors

Summary

4. Getting Data from the Tasks – The Callable and Future Interfaces

Introducing the Callable and Future interfaces

The Callable interface

The Future interface

First example – a best-matching algorithm for words

The common classes

A best-matching algorithm – the serial version

The BestMatchingSerialCalculation class

The BestMachingSerialMain class

A best-matching algorithm – the first concurrent version

The BestMatchingBasicTask class

The BestMatchingBasicConcurrentCalculation class

A best-matching algorithm – the second concurrent version

The word exists algorithm – a serial version

The ExistSerialCalculation class

The ExistSerialMain class

The word exists algorithm – the concurrent version

The ExistBasicTasks class

The ExistBasicConcurrentCalculation class

The ExistBasicConcurrentMain class

Comparing the solutions

Best-matching algorithms

Exist algorithms

The second example – creating an inverted index for a collection of documents

Common classes

The Document class

The DocumentParser class

The serial version

The first concurrent version – a task per document

The IndexingTask class

The InvertedIndexTask class

The ConcurrentIndexing class

The second concurrent version – multiple documents per task

The MultipleIndexingTask class

The MultipleInvertedIndexTask class

The MultipleConcurrentIndexing class

Comparing the solutions

Other methods of interest

Summary

5. Running Tasks Divided into Phases – The Phaser Class

An introduction to the Phaser class

Registration and deregistration of participants

Synchronizing phase changes

Other functionalities

First example – a keyword extraction algorithm

Common classes

The Word class

The Keyword class

The Document class

The DocumentParser class

The serial version

The concurrent version

The KeywordExtractionTask class

The ConcurrentKeywordExtraction class

Comparing the two solutions

The second example – a genetic algorithm

Common classes

The Individual class

The GeneticOperators class

The serial version

The SerialGeneticAlgorithm class

The SerialMain class

The concurrent version

The SharedData class

The GeneticPhaser class

The ConcurrentGeneticTask class

The ConcurrentGeneticAlgorithm class

The ConcurrentMain class

Comparing the two solutions

The Lau15 dataset

The Kn57 dataset

Conclusions

Summary

6. Optimizing Divide and Conquer Solutions – The Fork/Join Framework

An introduction to the Fork/Join framework

Basic characteristics of the Fork/Join framework

Limitations of the Fork/Join framework

Components of the Fork/Join framework

The first example – the k-means clustering algorithm

The common classes

The VocabularyLoader class

The Word, Document, and DocumentLoader classes

The DistanceMeasurer class

The DocumentCluster class

The serial version

The SerialKMeans class

The concurrent version

Two tasks for the Fork/Join framework – AssignmentTask and UpdateTask

The ConcurrentKMeans class

The ConcurrentMain class

Comparing the solutions

The second example – a data filtering algorithm

Common parts

The serial version

The SerialSearch class

The SerialMain class

The concurrent version

The TaskManager class

The IndividualTask class

The ListTask class

The ConcurrentSearch class

The ConcurrentMain class

Comparing the two versions

The third example – the merge sort algorithm

Shared classes

The serial version

The SerialMergeSort class

The SerialMetaData class

The concurrent version

The MergeSortTask class

The ConcurrentMergeSort class

The ConcurrentMetaData class

Comparing the two versions

Other methods of the Fork/Join framework

Summary

7. Processing Massive Datasets with Parallel Streams – The Map and Reduce Model

An introduction to streams

Basic characteristics of streams

Sections of a stream

Sources of a stream

Intermediate operations

Terminal operations

MapReduce versus MapCollect

The first example – a numerical summarization application

The concurrent version

The ConcurrentDataLoader class

The ConcurrentStatistics class

Job information from subscribers

Age data from subscribers

Marital data from subscribers

Campaign data from nonsubscribers

Multiple data filter

Duration data from nonsubscribers

People aged between 25 and 50

The ConcurrentMain class

The serial version

Comparing the two versions

The second example – an information retrieval search tool

An introduction to the reduction operation

The first approach – full document query

The basicMapper() method

The Token class

The QueryResult class

The second approach – reduced document query

The limitedMapper() method

The third approach – generating an HTML file with the results

The ContentMapper class

The fourth approach – preloading the inverted index

The ConcurrentFileLoader class

The fifth approach – using our own executor

Getting data from the inverted index – the ConcurrentData class

Getting the number of words in a file

Getting the average tfxidf value in a file

Getting the maximum and minimum tfxidf values in the index

The ConcurrentMain class

The serial version

Comparing the solutions

Summary

8. Processing Massive Datasets with Parallel Streams – The Map and Collect Model

Using streams to collect data

The collect() method

The first example – searching data without an index

Basic classes

The Product class

The Review class

The ProductLoader class

The first approach – basic search

The ConcurrentStringAccumulator class

The second approach – advanced search

The ConcurrentObjectAccumulator class

A serial implementation of the example

Comparing the implementations

The second example – a recommendation system

Common classes

The ProductReview class

The ProductRecommendation class

The recommendation system – the main class

The ConcurrentLoaderAccumulator class

The serial version

Comparing the two versions

The third example – common contacts in a social network

Base classes

The Person class

The PersonPair class

The DataLoader class

The concurrent version

The CommonPersonMapper class

The ConcurrentSocialNetwork class

The ConcurrentMain class

The serial version

Comparing the two versions

Summary

9. Diving into Concurrent Data Structures and Synchronization Utilities

Concurrent data structures

Blocking and non-blocking data structures

Interfaces

BlockingQueue

BlockingDeque

ConcurrentMap

TransferQueue

Classes

LinkedBlockingQueue

ConcurrentLinkedQueue

LinkedBlockingDeque

ConcurrentLinkedDeque

ArrayBlockingQueue

DelayQueue

LinkedTransferQueue

PriorityBlockingQueue

ConcurrentHashMap

Using the new features

First example with ConcurrentHashMap

The forEach() method

The search() method

The reduce() method

The compute() method

Another example with ConcurrentHashMap

An example with the ConcurrentLinkedDeque class

The removeIf() method

The spliterator() method

Atomic variables

Synchronization mechanisms

The CommonTask class

The Lock interface

The Semaphore class

The CountDownLatch class

The CyclicBarrier class

The CompletableFuture class

Using the CompletableFuture class

Auxiliary tasks

The main() method

Summary

10. Integration of Fragments and Implementation of Alternatives

Big-block synchronization mechanisms

An example of a document clustering application

The four systems of k-means clustering

The Reader system

The Indexer system

The Mapper system

The Clustering system

The main class of the document clustering application

Testing our document clustering application

Implementation of alternatives with concurrent programming

The k-nearest neighbors' algorithm

Building an inverted index of a collection of documents

A best-matching algorithm for words

A genetic algorithm

A keyword extraction algorithm

A k-means clustering algorithm

A filtering data algorithm

Searching an inverted index

A numeric summarization algorithm

A search algorithm without indexing

A recommendation system using the Map and Collect model

Summary

11. Testing and Monitoring Concurrent Applications

Monitoring concurrency objects

Monitoring a thread

Monitoring a lock

Monitoring an executor

Monitoring the Fork/Join framework

Monitoring a Phaser

Monitoring a stream

Monitoring concurrency applications

The Overview tab

The Monitor tab

The Threads tab

The Sampler tab

The Profiler tab

Testing concurrency applications

Testing concurrent applications with MultithreadedTC

Testing concurrent applications with Java Pathfinder

Installing Java Pathfinder

Running Java Pathfinder

Summary

Index

Mastering Concurrency Programming with Java 8

Mastering Concurrency Programming with Java 8

Copyright © 2016 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the authors, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

First published: February 2016

Production reference: 1220216

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham B3 2PB, UK.

ISBN 978-1-78588-612-6

www.packtpub.com

Credits

Author

Javier Fernández González

Reviewers

Antonio Gomes Rodrigues

Bradley Symons

Tagir Valeev

Commissioning Editor

Dipika Gaonkar

Acquisition Editor

Tushar Gupta

Content Development Editor

Shali Deeraj

Technical Editor

Gaurav Suri

Copy Editor

Dipti Mankame

Project Coordinator

Kinjal Bari

Proofreaders

Safis Editing

Indexers

Priya Sane

Graphics

Kirk D'Penha

Production Coordinator

Shantanu N. Zagade

Cover Work

Shantanu N. Zagade

About the Author

Javier Fernández González is a software architect with almost 15 years' experience with Java technologies. He has worked as a teacher, researcher, programmer, analyst, writer, and now as an architect in all types of projects related to Java, especially J2EE. As a teacher, he has taught over 1,000 hours of training in basic Java, J2EE, and Struts framework. As a researcher, he has worked in the field of information retrieval, developing applications in order to process large amounts of data in Java and has been a part of several journal articles and conference presentations as a coauthor. In recent years, he has worked on developing J2EE web applications for various clients from different sectors (public administration, insurance, healthcare, transportation, and so on). Currently, he is working as a software architect at Capgemini, which includes developing and maintaining applications for an insurance company. Also, he is the author of the book Java 7 Concurrency Cookbook, Packt Publishing.

To Nuria, Paula, and Pelayo, for your infinite love and patience.

About the Reviewers

Antonio Gomes Rodrigues has worked with high-traffic websites, traders applications, Cloud applications, and so on. He has experience of working with many performance tools, such as JProfiler, Yourkit, VisualVM, Dynatrace, AppDynamics, Introscope, NewRelic, JMeter, LoadRunner, and so on. To put in place, he has worked on performance strategies, load testing, training, troubleshooting, and so on. He shares his knowledge in his French blog (http://arodrigues.developpez.com/), conferences, and book reviews.

I would like to thank my wife Aurélie for her support and my child Timothée.

Bradley Symons graduated with a BSc (Hons) degree in Computer Science and has gained the Oracle Java Professional Programmer certification. His current occupation is as a Java server-side developer, but he has previously worked with a variety of languages, including Ruby and Python. With over a decade of coding experience, he has worked for a variety of business sectors, including AI, Finance, Travel, and Entertainment. He is highly interested in Spring, AOP, and concurrency. Currently, he is learning Cuba among other recent developments within the Java world. He is well-regarded as an avid follower of coding best practices, refactoring patterns, and TDD. He personally expresses his admiration for the technical contributions from the legendary Martin Fowler.

I would like to thank Jim Combes, my old team lead, for offering me the role as a Java Developer and allowing my enthusiastic interest in Java to grow and develop over the years.

Tagir Valeev, PhD, is a research assistant in A.P. Ershov Institute of Informatics Systems, Novosibirsk, Russia, and a lead developer in Development Group Ltd., Novosibirsk, Russia. He is a Java programming professional, a contributor to the FindBugs project (Java static analysis tool), and the author of the StreamEx project, which enhances the Java 8 Stream API. He is also officially an OpenJDK author, contributing enhancements and bug fixes in Stream API implementation. He answered many questions on StackOverflow related to Stream API and Java concurrency.

Big thanks to my wife Ekaterina and my son Artyom, for support and patience which helped me so much to finish the reviewing.

www.PacktPub.com

eBooks, discount offers, and more

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at <[email protected]> for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters and receive exclusive discounts and offers on Packt books and eBooks.

https://www2.packtpub.com/books/subscription/packtlib

Do you need instant solutions to your IT questions? PacktLib is Packt's online digital book library. Here, you can search, access, and read Packt's entire library of books.

Why subscribe?

Fully searchable across every book published by PacktCopy and paste, print, and bookmark contentOn demand and accessible via a web browser

Preface

Nowadays, computer systems (and other related systems, such as tablets or smartphones) allow you to do several tasks simultaneously. This can be possible because they have concurrent operating systems that control several tasks at the same time. You can also have one application that executes several tasks (read a file, show a message, or read data over a network) if you work with the concurrency API of your favorite programming language. Java includes a very powerful concurrency API that allows you to implement any kind of concurrency application with little effort. This API increases the features provided to programmers in every version. Now, in Java 8, it has included the stream API and new methods and classes to facilitate the implementation of concurrent applications. This book covers the most important elements of the Java concurrency API, showing you how to use them in real-world applications. These elements are as follows:

The executor framework, to control the execution of lots of taskThe Phaser class, to execute tasks that can be divided into phasesThe Fork/Join framework, to execute the tasks that solve a problem using the divide and conquer techniqueThe stream API, to process big sources of dataConcurrent data structures, to store the data in concurrent applicationsSynchronization mechanisms, to organize concurrent tasks

However, it includes much more: a methodology to design concurrency applications, design patterns, tips and tricks to implement good concurrency applications, and tools and techniques to test concurrency applications.

What this book covers

Chapter 1, The First Step – Concurrency Design Principles, will teach you the design principles of concurrency applications. They will also learn the possible problems of concurrency applications and a methodology to design them followed by some design patterns, tips, and tricks.

Chapter 2, Managing Lots of Threads – Executors, will teach you the basic principles of the executor framework. This framework allows you to work with lots of threads without creating or managing them. You will implement the k-nearest neighbors algorithm and a basic client/server application.

Chapter 3, Getting the Maximum from Executors, will teach you some advanced characteristics of executors, including cancelation and scheduling of tasks to execute a task after a delay or every certain period of time. You will implement an advanced client/server application and a news reader.

Chapter 4, Getting Data from the Tasks – The Callable and Future Interfaces, will teach you how to work in an executor with tasks that return a result using the Callable and Future interfaces. You will implement a best-matching algorithm and an application to build an inverted index.

Chapter 5, Running Tasks Divided into Phases – The Phaser class, will teach you how to use the Phaser class to execute tasks that can be divided into phases in a concurrent way. You will implement a keyword extraction algorithm and a genetic algorithm.

Chapter 6, Optimizing Divide and Conquer Solutions – The Fork/Join Framework, will teach you how to use a special kind of executor optimized by those problems that can be resolved using the divide and conquer technique: the Fork/Join framework and its work-stealing algorithm. You will implement the k-means clustering algorithm, a data filtering algorithm, and the merge-sort algorithm.

Chapter 7, Processing Massive Datasets with Parallel Streams – The Map and Reduce Model, will teach you how to work with streams to process big datasets. In this chapter, you will learn how to implement map and reduce applications using the stream API and much more functions of streams. You will implement a numerical summarization algorithm and an information retrieval search tool.

Chapter 8, Processing Massive Datasets with Parallel Streams – The Map and Collect Model, will teach you how to use the collect() method of the stream API to perform a mutable reduction of a stream of data into a different data structure, including the predefined collectors defined in the Collectors class. You will implement a tool to search data without indexing, a recommendation system, and an algorithm to calculate the list of common contacts of two persons in a social network.

Chapter 9, Diving into Concurrent Data Structures and Synchronization Utilities, will teach you how to work with the most important concurrent data structures (data structures that can be used in concurrent applications without causing data race conditions) and all the synchronization mechanisms included in the Java concurrency API to organize the execution of tasks.

Chapter 10, Integration of Fragments and Implementation of Alternatives, will teach you how to implement a big application made by fragments of concurrent applications with their own concurrency techniques using shared memory or message passing. You will also learn different implementation alternatives to the examples presented in the book.

Chapter 11, Testing and Monitoring Concurrent Applications, teaches you how to obtain information about the status of some of the Java concurrency API elements (thread, lock, executor, and so on). You will also learn how to monitor a concurrent application using the Java VisualVM application and how to test concurrent applications with the MultithreadedTC library and the Java Pathfinder application.

What you need for this book

To follow this book, you need basic knowledge of the Java programming language. A basic knowledge of concurrency concepts is welcome too.

Who this book is for

If you are a Java developer who knows the basic principles of concurrent programming but you want to get an expert knowledge of the Java concurrency API to develop optimized applications that takes advantage of all the hardware resources of computers, then this book is for you.

Conventions

In this book, you will find a number of text styles that distinguish between different kinds of information. Here are some examples of these styles and an explanation of their meaning.

Code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles are shown as follows: "The Product class stores the information about a product."

A block of code is set as follows:

if (problem.size() > DEFAULT_SIZE) { divideTasks(); executeTask(); taskResults=joinTasksResult(); return taskResults; } else { taskResults=solveBasicProblem(); return taskResults; }

New terms and important words are shown in bold. Words that you see on the screen, for example, in menus or dialog boxes, appear in the text like this: "Leave the default value and click on the Next button."

Note

Warnings or important notes appear in a box like this.

Tip

Tips and tricks appear like this.

Reader feedback

Feedback from our readers is always welcome. Let us know what you think about this book—what you liked or disliked. Reader feedback is important for us as it helps us develop titles that you will really get the most out of.

To send us general feedback, simply e-mail <[email protected]>, and mention the book's title in the subject of your message.

If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, see our author guide at www.packtpub.com/authors.

Customer support

Now that you are the proud owner of a Packt book, we have a number of things to help you to get the most from your purchase.

Downloading the example code

You can download the example code files from your account at http://www.packtpub.com for all the Packt Publishing books you have purchased. If you purchased this book elsewhere, you can visit http://www.packtpub.com/support and register to have the files e-mailed directly to you.

You can download the code files by following these steps:

Log in or register to our website using your e-mail address and password.Hover the mouse pointer on the SUPPORT tab at the top.Click on Code Downloads & Errata.Enter the name of the book in the Search box.Select the book for which you're looking to download the code files.Choose from the drop-down menu where you purchased this book from.Click on Code Download.

Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:

WinRAR / 7-Zip for WindowsZipeg / iZip / UnRarX for Mac7-Zip / PeaZip for Linux

Errata

Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you find a mistake in one of our books—maybe a mistake in the text or the code—we would be grateful if you could report this to us. By doing so, you can save other readers from frustration and help us improve subsequent versions of this book. If you find any errata, please report them by visiting http://www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details of your errata. Once your errata are verified, your submission will be accepted and the errata will be uploaded to our website or added to any list of existing errata under the Errata section of that title.

To view the previously submitted errata, go to https://www.packtpub.com/books/content/support and enter the name of the book in the search field. The required information will appear under the Errata section.

Piracy

Piracy of copyrighted material on the Internet is an ongoing problem across all media. At Packt, we take the protection of our copyright and licenses very seriously. If you come across any illegal copies of our works in any form on the Internet, please provide us with the location address or website name immediately so that we can pursue a remedy.

Please contact us at <[email protected]> with a link to the suspected pirated material.

We appreciate your help in protecting our authors and our ability to bring you valuable content.

eBooks, discount offers, and more

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at <[email protected]> for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks.

Questions

If you have a problem with any aspect of this book, you can contact us at <[email protected]>, and we will do our best to address the problem.

Chapter 1. The First Step – Concurrency Design Principles

Users of computer systems are always looking for better performance for their systems. They want to get higher quality videos, better video games, and faster network speed. Some years ago, processors gave better performance to users by increasing their speed. But now, processors don't increase their speed. Instead of this, they add more cores so that the operating system can execute more than one task at a time. This is named concurrency. Concurrent programming includes all the tools and techniques to have multiple tasks or processes running at the same time in a computer, communicating and synchronizing between them without data loss or inconsistency. In this chapter, we will cover the following topics:

Basic concurrency conceptsPossible problems in concurrent applicationsA methodology to design concurrent algorithmsThe Java concurrency APIThe Java memory modelConcurrency design patternsTips and tricks to design concurrency algorithms

Basic concurrency concepts

First of all, let's present the basic concepts of concurrency. You must understand these concepts to follow the rest of the book.

Concurrency versus parallelism

Concurrency and parallelism are very similar concepts. Different authors give different definitions to these concepts. The most accepted definition talks about concurrency when you have more than one task in a single processor with a single core and the operating system's task scheduler quickly switches from one task to another, so it seems that all the tasks run simultaneously. The same definition talks about parallelism when you have more than one task that run simultaneously at the same time, in a different computer, processor, or core inside a processor.

Another definition talks about concurrency when you have more than one task (different tasks) running simultaneously on your system. One more definition discusses parallelism when you have different instances of the same task running simultaneously over different parts of a dataset.

The last definition that we include talks about parallelism when you have more than one task that runs simultaneously in your system and talks about concurrency to explain the different techniques and mechanisms programmers have to synchronize with the tasks and their access to shared resources.

As you can see, both concepts are very similar and this similarity has increased with the development of multicore processors.

Synchronization

In concurrency, we can define synchronization as the coordination of two or more tasks to get the desired results. We have two kinds of synchronization:

Control synchronization: When, for example, one task depends on the end of another task, the second task can't start before the first has finishedData access synchronization: When two or more tasks have access to a shared variable and only one of the tasks can access the variable at any given time

A concept closely related to synchronization is critical section. A critical section is a piece of code that can be only executed by a task at any given time because of its access to a shared resource. Mutual exclusion is the mechanism used to guarantee this requirement and can be implemented by different ways.

Keep in mind that synchronization helps you avoid some errors you can have with concurrent tasks (they will be described later in this chapter), but it introduces some overhead to your algorithm. You have to calculate very carefully the number of tasks, which can be performed independently without intercommunication in your parallel algorithm. It's the granularity of your concurrent algorithm. If you have a coarse-grained granularity (big tasks with low intercommunication), the overhead due to synchronization will be low. However, maybe you won't benefit all the cores of your system. If you have a fine-grained granularity (small tasks with high intercommunication), the overhead due to synchronization will be high and maybe the throughput of your algorithm won't be good.

There are different mechanisms to get synchronization in a concurrent system. The most popular mechanisms from a theoretical point of view are:

Semaphore: A semaphore is a mechanism that can be used to control the access to one or more units of a resource. It has a variable that stores the number of resources that can be used and two atomic operations to manage the value of the variable. A mutex (short for mutual exclusion) is a special kind of semaphore that can take only two values (resource is free and resource is busy), and only the process that sets the mutex to busy can release it.Monitor: A monitor is a mechanism to get mutual exclusion over a shared resource. It has a mutex, a condition variable, and two operations to wait for the condition and to signal the condition. Once you signal the condition, only one of the tasks that are waiting for it continues with its execution.

The last concept related to synchronization you're going to learn in this chapter is thread safety. A piece of code (or a method or an object) is thread-safe if all the users of shared data are protected by synchronization mechanisms, a nonblocking compare-and-swap (CAS) primitive or data is immutable, so you can use that code in a concurrent application without any problem.

Immutable object

An immutable object is an object with a very special characteristic. You can't modify its visible state (the value of its attributes) after its initialization. If you want to modify an immutable object, you have to create a new one.

Its main advantage is that it is thread-safe. You can use it in concurrent applications without any problem.

An example of an immutable object is the String class in Java. When you assign a new value to a String object, you are creating a new string.

Atomic operations and variables

An atomic operation is a kind of operation that appears to occur instantaneously to the rest of the tasks of the program. In a concurrent application, you can implement an atomic operation with a critical section to the whole operation using a synchronization mechanism.

An atomic variable is a kind of variable with atomic operations to set and get its value. You can implement an atomic variable using a synchronization mechanism or in a lock-free manner using CAS, which doesn't need any synchronization.

Shared memory versus message passing

Tasks can use two different methods to communicate with each other. The first one is shared memory, and normally it is used when the tasks are running in the same computer. The tasks use the same memory area where they write and read values. To avoid problems, the access to this shared memory has to be in a critical section protected by a synchronization mechanism.

The other synchronization mechanism is message passing and normally is used when the tasks are running in different computers. When a task needs to communicate with another, it sends a message that follows a predefined protocol. This communication can be synchronous if the sender is blocked waiting for a response or asynchronous if the sender continues with their execution after sending the message.

Possible problems in concurrent applications

Programming a concurrent application is not an easy job. If you incorrectly use the synchronization mechanisms, you can have different problems with the tasks in your application. In this section, we describe some of these problems.

Data race

You can have a data race (also named race condition) in your application when you have two or more tasks writing a shared variable outside a critical section—that's to say, without using any synchronization mechanisms.

Under these circumstances, the final result of your application may depend on the order of execution of the tasks. Look at the following example:

package com.packt.java.concurrency; public class Account { private float balance; public void modify (float difference) { float value=this.balance; this.balance=value+difference; } }

Imagine that two different tasks execute the modify() method in the same Account object. Depending on the order of execution of the sentences in the tasks, the final result can vary. Suppose that the initial balance is 1000 and the two tasks call the modify() method with 1000 as a parameter. The final result should be 3000, but if both tasks execute the first sentence at the same time and then the second sentence at the same time, the final result will be 2000. As you can see, the modify() method is not atomic and the Account class is not thread-safe.

Deadlock

There is a deadlock in your concurrent application when there are two or more tasks waiting for a shared resource that must be free from the other, so none of them will get the resources they need and will be blocked indefinitely. It happens when four conditions happen simultaneously in the system. They are Coffman's conditions, which are as follows:

Mutual exclusion: The resources involved in the deadlock must be nonshareable. Only one task can use the resource at a time.Hold and wait condition: A task has the mutual exclusion for a resource and it's requesting the mutual exclusion for another resource. While it's waiting, it doesn't release any resources.No pre-emption: The resources can only be released by the tasks that hold them.Circular wait: There is a circular waiting where Task 1 is waiting for a resource that is being held by Task 2, which is waiting for a resource being held by Task 3, and so on until we have Task n that is waiting for a resource being held by Task 1.

There exist some mechanisms that you can use to avoid deadlocks:

Ignore them: This is the most commonly used mechanism. You suppose that a deadlock will never occur on your system, and if it occurs, you can see the consequences of stopping your application and having to re-execute it.Detection: The system has a special task that analyzes the state of the system to detect if a deadlock has occurred. If it detects a deadlock, it can take action to remedy the problem. For example, finishing one task or forcing the liberation of a resource.Prevention: If you want to prevent deadlocks in your system, you have to prevent one or more of Coffman's conditions.Avoidance: Deadlocks can be avoided if you have information about the resources that are used by a task before it begins its execution. When a task wants to start its execution, you can analyze the resources that are free in the system and the resources that the task needs to decide that it can start its execution or not.

Livelock

A livelock occurs when you have two tasks in your systems that are always changing their states due to the actions of the other. Consequently, they are in a loop of state changes and unable to continue.

For example, you have two tasks—Task 1 and Task 2—and both need two resources: Resource 1 and Resource 2. Suppose that Task 1 has a lock on Resource 1, and Task 2 has a lock on Resource 2. As they are unable to gain access to the resource they need, they free their resources and begin the cycle again. This situation can continue indefinitely, so the tasks will never end their execution.

Resource starvation

Resource starvation occurs when you have a task in your system that never gets a resource that it needs to continue with its execution. When there is more than one task waiting for a resource and the resource is released, the system has to choose the next task that can use it. If your system has not got a good algorithm, it can have threads that are waiting for a long time for the resource.

Fairness is the solution to this problem. All the tasks that are waiting for a resource must have the resource in a given period of time. An option is to implement an algorithm that takes into account the time that a task has been waiting for a resource when it chooses the next task that will hold a resource. However, fair implementation of locks requires additional overhead, which may lower your program throughput.

Priority inversion

Priority inversion occurs when a low-priority task holds a resource that is needed by a high-priority task, so the low-priority task finishes its execution before the high-priority task.

A methodology to design concurrent algorithms

In this section, we're going to propose a five-step methodology to get a concurrent version of a sequential algorithm. It's based on the one presented by Intel in their Threading Methodology: Principles and Practices document.

The starting point – a sequential version of the algorithm

Our starting point to implement a concurrent algorithm will be a sequential version of it. Of course, we can design a concurrent algorithm from scratch, but I think that a sequential version of the algorithm will give us two advantages:

We can use the sequential algorithm to test if our concurrent algorithm generates correct results. Both algorithms must generate the same output when they receive the same input, so we can detect some problems in the concurrent version, such as data races or similar conditions.We can measure the throughput of both algorithms to see if the use of concurrency gives us a real improvement in the response time or in the amount of data the algorithm can process in a time.

Step 1 – analysis

In this step, we are going to analyze the sequential version of the algorithm to look for the parts of its code that can be executed in a parallel way. We should pay special attention to those parts that are executed most of the time or that execute more code because, by implementing a concurrent version of those parts, we're going to get a greater performance improvement.

Good candidates for this process are loops where one step is independent of the other steps or portions of code that are independent of other parts of the code (for example, an algorithm to initialize an application that opens the connections with the database, loads the configuration files, initialize some objects. All the previous tasks are independent of each other).

Step 2 – design

Once you know what parts of the code you are going to parallelize, you have to decide how to do that parallelization.

The changes in the code will affect two main parts of the application:

The structure of the codeThe organization of the data structures

You can take two different approaches to accomplish this task:

Task decomposition: You do task decomposition when you split the code in two or more independent tasks that can be executed at once. Maybe some of these tasks have to be executed in a given order or have to wait at the same point. You must use synchronization mechanisms to get this behavior.Data decomposition: You do data decomposition when you have multiple instances of the same task that work with a subset of the dataset. This dataset will be a shared resource, so if the tasks need to modify the data you have to protect access to it by implementing a critical section.

Another important point to keep in mind is the granularity of your solution. The objective of implementing a parallel version of an algorithm is to achieve improved performance, so you should use all the available processors or cores. On the other hand, when you use a synchronization mechanism, you introduce some extra instructions that must be executed. If you split the algorithm into a lot of small tasks (fine-grained granularity), the extra code introduced by the synchronization can provoke performance degradation. If you split the algorithm into fewer tasks than cores (coarse-grained granularity), you are not taking advantage of all the resources. Also, you must take into account the work every thread must do, especially if you implement a fine-grained granularity. If you have a task longer than the rest, that task will determine the execution time of the application. You have to find the equilibrium between these two points.

Step 3 – implementation

The next step is to implement the parallel algorithm using a programming language and, if it's necessary, a thread library. In the examples of this book, you are going to use Java to implement all the algorithms.

Step 4 – testing

After finishing the implementation, you have to test the parallel algorithm. If you have a sequential version of the algorithm, you can compare the results of both algorithms to verify that your parallel implementation is correct.

Testing and debugging a parallel implementation are difficult tasks because the order of execution of the different tasks of the application is not guaranteed. In Chapter 11, Testing and Monitoring Concurrent Applications, you will learn tips, tricks, and tools to do these tasks efficiently.

Step 5 – tuning

The last step is to compare the throughput of the parallel and the sequential algorithms. If the results are not as expected, you must review the algorithm, looking for the cause of the bad performance of the parallel algorithm.

You can also test different parameters of the algorithm (for example, granularity or number of tasks) to find the best configuration.

There are different metrics to measure the possible performance improvement you can obtain parallelizing an algorithm. The three most popular metrics are:

Speedup: This is a metric for relative performance improvement between the parallel and the sequential versions of the algorithm:

Here, Tsequential is the execution time of the sequential version of the algorithm and Tconcurrent is the execution time of the parallel version.

Amdahl's law: This is used to calculate the maximum expected improvement obtained with the parallelization of an algorithm:

Here, P is the percentage of code that can be parallelized and N is the number of cores of the computer where you're going to execute the algorithm.

For example, if you can parallelize 75% of the code and you have four cores, the maximum speedup will be given by the following formula:

Gustafson-Barsis' law: Amdahl's law has a limitation. It supposes that you have the same input dataset when you increase the number of cores, but normally, when you have more cores, you want to process more data. Gustafson law proposes that when you have more cores available, bigger problems can be solved in the same time using the following formula:

Here, N is the number of cores and P is the percentage of parallelizable code.

If we use the same example as before, the scaled speedup calculated by the Gustafson law is:

Conclusion

In this section, you learned some important issues you have to take into account when you want to parallelize a sequential algorithm.

First of all, not every algorithm can be parallelized. For example, if you have to execute a loop where the result of an iteration depends on the result of the previous iteration, you can't parallelize that loop. Recurrent algorithms are another example of algorithms that can be parallelized for a similar reason.

Another important thing you have to keep in mind is that the sequential version of an algorithm with better performance can be a bad starting point to parallelize it. If you start parallelizing an algorithm and you find yourself in trouble because you don't easily find independent portions of the code, you have to look for other versions of the algorithm and verify that the version can be parallelized in an easier way.

Finally, when you implement a concurrent application (from scratch or based on a sequential algorithm), you must take into account the following points:

Efficiency: The parallel algorithm must end in less time than the sequential algorithm. The first goal of parallelizing an algorithm is that its running time is less than the sequential one, or it can process more data in the same time.Simplicity: When you implement an algorithm (parallel or not), you must keep it as simple as possible. It will be easier to implement, test, debug, and maintain, and it will have fewer errors.Portability: Your parallel algorithm should be executed on different platforms with minimal changes. As in this book you will use Java, this point will be very easy. With Java, you can execute your programs in every operating system without any change (if you implement the program as you must).Scalability: What happens to your algorithm if you increase the number of cores? As mentioned before, you should use all the available cores, so your algorithm should be ready to take advantage of all available resources.

Java concurrency API

The Java programming language has a very rich concurrency API. It contains classes to manage the basic elements of concurrency, such as Thread, Lock, and Semaphore, and classes that implement very high-level synchronization mechanisms, such as the executor framework or the new parallel Stream API.

In this section, we will cover the basic classes that form the concurrency API.

Basic concurrency classes

The basic classes of the Java concurrency API are:

The Thread class: This class represents all the threads that execute a concurrent Java applicationThe Runnable interface: This is another way to create concurrent applications in JavaThe ThreadLocal class: This is a class to store variables locally to a threadThe ThreadFactory interface: This is the base of the Factory design pattern that you can use to create customized threads

Synchronization mechanisms

The Java concurrency API includes different synchronization mechanisms that allow you to:

Define a critical section to access a shared resourceSynchronize different tasks in a common point

The following mechanisms are considered to be the most important synchronization mechanisms:

The synchronized keyword: Thesynchronized keyword allows you to define a critical section in a block of code or in an entire method.The Lock interface: Lock provides a more flexible synchronization operation than the synchronized keyword. There are different kinds of Locks: ReentrantLock, to implement a Lock that can be associated with a condition; ReentrantReadWriteLock, which separates read and write operations; and StampedLock, a new feature of Java 8 that includes three modes for controlling read/write access.The Semaphore class: The class that implements the classical semaphore to implement synchronization. Java supports binary and general semaphores.The CountDownLatch class: A class that allows a task to wait for the finalization of multiple operations.The CyclicBarrier class: A class that allows the synchronization of multiple threads in a common point.The Phaser class: A class that allows you to control the execution of tasks divided into phases. None of the tasks advance to the next phase until all of the tasks have finished the current phase.

Executors

The executor framework is a mechanism that allows you to separate thread creation and management for the implementation of concurrent tasks. You don't have to worry about the creation and management of threads, only about creating tasks and sending them to the executor. The main classes involved in this framework are:

The Executor and ExecutorService interface: They include methods common to all executors.ThreadPoolExecutor: This is a class that allows you to get an executor with a pool of threads and optionally define a maximum number of parallel tasksScheduledThreadPoolExecutor: This is a special kind of executor to allow you to execute tasks after a delay or periodicallyExecutors: This is a class that facilitates the creation of executorsThe Callable interface: This is an alternative to the Runnable interface—a separate task that can return a valueThe Future interface: This is an interface that includes the methods to obtain the value returned by a Callable interface and to control its status

The Fork/Join framework

The Fork/Join framework defines a special kind of executor specialized in the resolution of problems with the divide and conquer technique. It includes a mechanism to optimize the execution of the concurrent tasks that solve these kinds of problems. Fork/Join is specially tailored for fine-grained parallelism as it has a very low overhead in order to place the new tasks into the queue and take queued tasks for execution. The main classes and interfaces involved in this framework are:

ForkJoinPool: This is a class that implements the executor that is going to run the tasksForkJoinTask: This is a task that can be executed in the ForkJoinPool classForkJoinWorkerThread: This is a thread that is going to execute tasks in the ForkJoinPool class

Parallel streams

Streams and Lambda expressions are maybe the two most important new features of the Java 8 version. Streams have been added as a method in the Collection interface and other data sources and allow processing all elements of a data structure, generating new structures, filtering data and implementing algorithms using the map and reduce technique.

A special kind of stream is a parallel stream which realizes its operations in a parallel way. The most important elements involved in the use of parallel streams are:

The Stream interface: This is an interface that defines all the operations that you can perform on a stream.Optional: This is a container object that may or may not contain a non-null value.Collectors: This is a class that implements reduction operations that can be used as part of a stream sequence of operations.Lambda expressions: Streams has been thought to work with Lambda expressions. Most stream methods accept a lambda expression as a parameter. This allows you to implement a more compact version of the operations.

Concurrent data structures

Normal data structures of the Java API (ArrayList, Hashtable, and so on) are not ready to work in a concurrent application unless you use an external synchronization mechanism. If you use it, you will be adding a lot of extra computing time to your application. If you don't use it, it's probable that you will have race conditions in your application. If you modify them from several threads and a race condition occurs, you may experience various exceptions thrown (such as, ConcurrentModificationException and ArrayIndexOutOfBoundsException), there may be silent data loss or your program may even stuck in an endless loop.

The Java concurrency API includes a lot of data structures that can be used in concurrent applications without risk. We can classify them in two groups:

Blocking data structures: These include methods that block the calling task when, for example, the data structure is empty and you want to get a value.Non-blocking data structures: If the operation can be made immediately, it won't block the calling tasks. Otherwise, it returns the null value or throws an exception.

These are some of the data structures:

ConcurrentLinkedDeque: This is a non-blocking listConcurrentLinkedQueue: This is a non-blocking queueLinkedBlockingDeque: This is a blocking listLinkedBlockingQueue: This is a blocking queuePriorityBlockingQueue: This is a blocking queue that orders its elements based on its priorityConcurrentSkipListMap: This is a non-blocking navigable mapConcurrentHashMap: This is a non-blocking hash mapAtomicBoolean, AtomicInteger, AtomicLong, and AtomicReference: These are atomic implementations of the basic Java data types

The Java memory model

When you execute a