45,59 €
Mehr erfahren.
- Herausgeber: Packt Publishing
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Master the principles to make applications robust, scalable and responsive
About This Book
- Implement concurrent applications using the Java 9 Concurrency API and its new components
- Improve the performance of your applications and process more data at the same time, taking advantage of all of your resources
- Construct real-world examples related to machine learning, data mining, natural language processing, and more
Who This Book Is For
This book is for competent Java developers who have basic understanding of concurrency, but knowledge of effective implementation of concurrent programs or usage of streams for making processes more efficient is not required
What You Will Learn
- Master the principles that every concurrent application must follow
- See how to parallelize a sequential algorithm to obtain better performance without data inconsistencies and deadlocks
- Get the most from the Java Concurrency API components
- Separate the thread management from the rest of the application with the Executor component
- Execute phased-based tasks in an efficient way with the Phaser components
- Solve problems using a parallelized version of the divide and conquer paradigm with the Fork / Join framework
- Find out how to use parallel Streams and Reactive Streams
- Implement the “map and reduce” and “map and collect” programming models
- Control the concurrent data structures and synchronization mechanisms provided by the Java Concurrency API
- Implement efficient solutions for some actual problems such as data mining, machine learning, and more
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. Java 9 includes a comprehensive API with lots of ready-to-use components for easily implementing powerful concurrency applications, but with high flexibility so you can adapt these components to your needs.
The book starts with a full description of the design principles of concurrent applications and explains how to parallelize a sequential algorithm. You will then be introduced to Threads and Runnables, which are an integral part of Java 9's concurrency API. You will see how to use all the components of the Java concurrency API, from the basics to the most advanced techniques, and will implement them in powerful real-world concurrency applications.
The book ends with a detailed description of the tools and techniques you can use to test a concurrent Java application, along with a brief insight into other concurrency mechanisms in JVM.
Style and approach
This is a complete guide that implements real-world examples of algorithms related to machine learning, data mining, and natural language processing in client/server environments. All the examples are explained using a step-by-step approach.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 603
Veröffentlichungsjahr: 2017
Ähnliche
Second Edition
BIRMINGHAM - MUMBAI
Mastering Concurrency Programming with Java 9
Second Edition
Copyright © 2017 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 author, 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
Second edition: July 2017
Production reference: 1140717
ISBN 978-1-78588-794-9
www.packtpub.com
Credits
Author
Javier Fernandez Gonzalez
Copy Editor
Safis Editing
Reviewer
Miro Wengner
Project Coordinator
Vaidehi Sawant
Commissioning Editor
Kunal Parikh
Proofreader
Safis Editing
Acquisition Editor
Nitin Dasan
Indexer
Rekha Nair
Content Development Editor
Nikhil Borkar
Graphics
Abhinash Sahu
Technical Editor
Subhalaxmi Nadar
Production Coordinator
Melwyn Dsa
About the Author
Javier Fernandez Gonzalez is a software architect with almost 15 years of experience working with Java technologies. He has worked as a teacher, researcher, programmer, analyst, writer, and he now works as an architect in all types of projects related to Java, especially J2EE. As a teacher, has taken over 1,000 hours of training sessions in basic Java, J2EE, and the Struts framework. As a researcher, has worked in the field of information retrieval, developing applications for processing large amounts of data in Java, and he has participated in several journal articles and conference presentations as a coauthor. In recent years, has worked on developing J2EE web applications for various clients from different sectors (public administration, insurance, healthcare, transportation, and , many more). Currently, he works as a software architect. He is the author of Java 7 Concurrency Cookbook, Mastering Concurrency Programming with Java 8, First Edition, and Java 9 Concurrency Cookbook, Second Edition.
About the Reviewer
Miro Wengner has been a passionate JVM enthusiast since the moment he joined Sun Microsystems in 2002. He truly believes in distributed system design, concurrency, and parallel computing. One of Miro's biggest hobbies is the development of autonomous systems. He is one of the coauthors of and main contributors to the Java open-source project Robo4J. The Robo4J project's goal is to have a fun and outstanding experience in IoT application development.
Miro earns his daily bread by working on distributed web applications in a senior position.
www.PacktPub.com
For support files and downloads related to your book, please visit www.PacktPub.com.
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.comand 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://www.packtpub.com/mapt
Get the most in-demand software skills with Mapt. Mapt gives you full access to all Packt books and video courses, as well as industry-leading tools to help you plan your personal development and advance your career.
Why subscribe?
Fully searchable across every book published by Packt
Copy and paste, print, and bookmark content
On demand and accessible via a web browser
Customer Feedback
Thanks for purchasing this Packt book. At Packt, quality is at the heart of our editorial process. To help us improve, please leave us an honest review on this book's Amazon page at https://www.amazon.com/dp/1785887947.
If you'd like to join our team of regular reviewers, you can e-mail us at [email protected]. We award our regular reviewers with free eBooks and videos in exchange for their valuable feedback. Help us be relentless in improving our products!
Table of Contents
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
Questions
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
Tips and tricks for designing concurrent algorithms
Identifying the correct independent tasks
Implementing concurrency at the highest possible level
Taking scalability into account
Using thread-safe APIs
Never assume an execution order
Preferring local thread variables over static and shared when possible
Finding the easier 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
Working with Basic Elements - Threads and Runnables
Threads in Java
Threads in Java - characteristics and states
The Thread class and the Runnable interface
First example: matrix multiplication
Common classes
Serial version
Parallel versions
First concurrent version - a thread per element
Second concurrent version - a thread per row
Third concurrent version - the number of threads is determined by the processors
Comparing the solutions
Second example - file search
Common classes
Serial version
Concurrent version
Comparing the solutions
Summary
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
Second example - concurrency in a client/server environment
Client/server - serial version
The DAO part
The command part
The server part
Client/version - 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
Getting the Most from Executors
Advanced characteristics of executors
Cancellation of tasks
Scheduling the execution of tasks
Overriding the executor methods
Changing some initialization parameters
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
The concrete commands
The server part
The ConcurrentServer class
The RequestTask class
The client part
Second example - executing periodic tasks
The common parts
The basic reader
The advanced reader
Additional information about executors
Summary
Getting Data from 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
Word exists algorithm - a serial version
The ExistSerialCalculation class
The ExistSerialMain class
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
Running Tasks Divided into Phases - The Phaser Class
An introduction to the Phaser class
Registration and deregistration of participants
Synchronizing phase change
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
Lau15 dataset
Kn57 dataset
Conclusions
Summary
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 SerialMain 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 features
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
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
Customers from the United Kingdom
Quantity from the United Kingdom
Countries for product
Quantity for product
Multiple data filter
Highest invoice amounts
Products with a unit price between 1 and 10
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
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
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
Asynchronous Stream Processing - Reactive Streams
Introduction to reactive streams in Java
The Flow.Publisher interface
The Flow.Subscriber interface
The Flow.Subscription interface
The SubmissionPublisher class
The first example - a centralized system for event notification
The Event class
The Producer class
The Consumer class
The Main class
The second example - a news system
The News class
The publisher classes
The Consumer class
The Main class
Summary
Diving into Concurrent Data Structures and Synchronization Utilities
Concurrent data structures
Blocking and non-blocking data structures
Concurrent 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
Variable handles
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
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 the Stream API
Monitoring concurrency applications
The Overview tab
The Memory tab
The Threads tab
The Classes tab
The VM summary tab
The MBeans tab
The About tab
Testing concurrency applications
Testing concurrent applications with MultithreadedTC
Testing concurrent applications with Java Pathfinder
Installing Java Pathfinder
Running Java Pathfinder
Summary
Concurrency in JVM - Clojure and Groovy with the Gpars Library and Scala
Concurrency in Clojure
Using Java elements
Reference types
Atoms
Agents
Refs
Delays
Futures
Promises
Concurrency in Groovy with the GPars library
Software transactional memory
Using Java elements
Data parallelism
The fork/join processing
Actors
Agent
Dataflow
Concurrency in Scala
Future objects in Scala
Promises
Summary
Preface
Nowadays, computer systems (and other related systems, such as tablets or smartphones) allow you to do several tasks at the same time. This is 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, and 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 applications with very 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 a lot of tasks
The Phaser class, to execute tasks that can be divided into phases
The fork/join framework, to execute that tasks that solve a problem using the divide and conquer technique
The Stream API, to process big sources of data, including the new reactive streams
Concurrent data structures, to store the data in concurrent applications
Synchronization mechanisms, to organize concurrent tasks
However, the Java concurrency API includes much more--a methodology to design concurrency applications, design patterns, tips and tricks to implement good concurrency applications, the tools and techniques to test concurrency applications, and ways to implement concurrency applications in other languages for the Java Virtual Machine, such as Clojure, Groovy, and Scala.
What this book covers
Chapter 1, The First Step - Concurrency Design Principles, covers the design principles of concurrency applications. You will also learn the possible problems of concurrency applications and a methodology to design them, accompanied by some design patterns, tips, and tricks.
Chapter 2, Working with Basic Elements - Threads and Runnables, explains how to work with the most basic elements to implement concurrent applications in the Java language: the Runnable interface and the Thread classes. With these elements, you can create a new execution thread that will be executed in parallel with the actual one.
Chapter 3, Managing Lots of Threads - Executors, covers the basic principles of the Executor framework. This framework allows you to work with lots of threads without creating or managing them. We will implement the k-nearest neighbors algorithm and a basic client/server application.
Chapter 4, Getting the Most from Executors, explores some advanced characteristics of Executors, including the cancellation and scheduling of tasks to execute a task after a delay or every certain period of time. We will implement an advanced client/server application and a news reader.
Chapter 5, Getting Data from Tasks - The Callable and Future Interfaces, explains how to work in an Executor with tasks that return a result using the Callable and Future interfaces. We will implement a best-matching algorithm and an application to build an inverted index.
Chapter 6, Running Tasks Divided into Phases - The Phaser Class, explains how to use the Phaser class to execute tasks that can be divided into phases in a concurrent way. We will implement a keyword extraction algorithm and a genetic algorithm.
Chapter 7, Optimizing Divide and Conquer Solutions - The Fork/Join Framework, explores the use of 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. We will implement the k-means clustering algorithm, a data filtering algorithm, and the merge-sort algorithm.
Chapter 8, Processing Massive Datasets with Parallel Streams - The Map and Reduce Model, explains 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 you will learn many more functions of streams. We will implement a numerical summarization algorithm and an information retrieval search tool.
Chapter 9, Processing Massive Datasets with Parallel Streams - The Map and Collect Model, explores 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. We will implement a tool for searching data without indexing, a recommendation system, and an algorithm to calculate the list of common contacts of two persons on a social network.
Chapter 10, Asynchronous Stream Processing – Reactive Streams, explains how to implement a concurrent application using reactive streams that defines a standard for asynchronous stream processing with non-blocking back pressure. The basic principles of this kind of streams are defined at http://www.reactive-streams.org/, and Java 9 provides the basic interfaces necessary for its implementation.
Chapter 11, Diving into Concurrent Data Structures and Synchronization Utilities, covers 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 12, Testing and Monitoring Concurrent Applications, explains 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.
Chapter 13, Concurrency in JVM – Clojure and Groovy with the Gpars Library and Scala, explores how to implement concurrent applications in other languages for the Java Virtual Machine. You will learn how to use the concurrent elements provided by the Clojure and Scala programming languages and the GPars library with the Groovy programming language.
What you need for this book
To follow this book, you need basic to medium-level 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 wants to become an expert user of the Java concurrency API in order to develop optimized applications that take advantage of all the hardware resources of computers, 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 modify() method is not atomic and the Account class is not thread-safe."
A block of code is set as follows:
public void task2() { section2_1(); commonObject2.notify(); commonObject1.wait(); section2_2();}
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: "The Classes tab shows you information about the class loading"
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 for this book from your account at http://www.packtpub.com. 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 Windows
Zipeg / iZip / UnRarX for Mac
7-Zip / PeaZip for Linux
The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Mastering-Concurrency-Programming-with-Java-9-Second-Edition. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!
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/supportand 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.
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.
The First Step - Concurrency Design Principles
Users of computer systems are always looking for better performance of their systems. They want to get higher quality videos, better video games, and faster network speeds. 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 called 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 concepts
Possible problems in concurrent applications
A methodology to design concurrent algorithms
Java Concurrency API
Concurrency design patterns
Tips 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 for these concepts. The most accepted definition talks about concurrency as being when you have more than one task in a single processor with a single core. In this case, 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 as being when you have more than one task running simultaneously on different computers, processors, or cores inside a processor.
Another definition talks about concurrency being when you have more than one task (different tasks) that run simultaneously on your system. Yet another definition discusses parallelism as being when you have different instances of the same task that run simultaneously over different parts of a dataset.
The last definition talks about parallelism being when you have more than one task that runs simultaneously in your system and talks about concurrency as a way to explain the different techniques and mechanisms the programmer has 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 finished
Data access synchronization
: When two or more tasks have access to a shared variable and only one of the tasks can access the variable
A concept closely related to synchronization is critical section. A critical section is a piece of code that can be only executed by one task at a time because of its access to a shared resource. Mutual exclusion is the mechanism used to guarantee this requirement and can be implemented in different ways.
Keep in mind that synchronization helps you avoid some errors you might have with concurrent tasks (they will be described later in this chapter), but it introduces some overhead to your algorithm. You have to calculate the number of tasks very carefully, which can be performed independently without intercommunication you will have 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 from 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 perhaps 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. A mutex can help you to avoid race conditions by protecting a critical section.
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 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 non-blocking, compare-and-swap (CAS) primitive of the data is immutable, so you can use that code in a concurrent application without any problems.
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 one.
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 that has 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 that doesn't need 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 on 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, it is used when the tasks are running on different computers. When tasks needs to communicate with another, it sends a message that follows a predefined protocol. This communication can be synchronous if the sender keeps it 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. Incorrect use of the synchronization mechanisms can create 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 or 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 another thread that is waiting for another shared resource that must be free by one of the first ones. It happens when four conditions happen simultaneously in the system. They are the Coffman 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
.
Some mechanisms exist 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 whether 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 the Coffman 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 so it is able to decide whether it can start its execution or not.
Livelock
A livelock occurs when you have two tasks in your system 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 doesn't have 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 the algorithm. Of course, we could 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 whether 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 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, and initializes some objects; all these 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 code
The 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 into 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, 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 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 should 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 12, 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 improvements between the parallel and the sequential versions of the algorithm: Here,
T
sequential
is the execution time of the sequential version of the algorithm and
T
concurrent
is the execution time of the parallel version.
Amdahl's law
: 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's law proposes that when you have more cores available, bigger problems can be solved at 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 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 with better performance of an algorithm can be a bad starting point to parallelize it. If you start parallelizing an algorithm and you find yourself in trouble because you cannot 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 less errors.
Portability
: Your parallel algorithm should be executed on different platforms with minimum changes. As in this book you will use Java, this point will be very easy. With Java, you can execute your programs on every operating system without any changes (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 every available core so your algorithm is 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 Concurrency API are:
The Thread class
: This class represents all the threads that execute a concurrent Java application
The Runnable interface
: This is another way to create concurrent applications in Java
The ThreadLocal class
: This is a class to store variables locally to a thread
The 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 resource
Synchronize different tasks at a common point
The following mechanisms are the most important synchronization mechanisms:
The synchronized keyword
: The
synchronized
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
that separates the 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 the 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 at 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 to create tasks and send them to the executor. The main classes involved in this framework are:
The Executor and ExecutorService interface
: This includes the
execute()
method 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 tasks
ScheduledThreadPoolExecutor
: This is a special kind of executor to allow you to execute tasks after a delay or periodically
Executors
: This is a class that facilitates the creation of executors
The Callable interface
: This is an alternative to the
Runnable
interface - a separate task that can return a value
The 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 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 tasks
ForkJoinTask
: This is a task that can be executed in the
ForkJoinPool
class
ForkJoinWorkerThread
: This is a thread that is going to execute tasks in the
ForkJoinPool
class
Parallel streams
Streams and lambda expressions were 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 the processing of 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 that 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 have been thought of to work with Lambda expressions. Most of stream methods accept a lambda expression as a parameter. This allows you to implement a more compact version of 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 add race conditions to your application. If you modify them from several threads and race conditions occur, you may experience various exceptions (such as, ConcurrentModificationException and ArrayIndexOutOfBoundsException), silent data loss, or your program may even get 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 into 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. It returns a null value or throws an exception.
These are some of the data structures:
ConcurrentLinkedDeque
: This is a non-blocking list
ConcurrentLinkedQueue
: This is a non-blocking queue
LinkedBlockingDeque
: This is a blocking list
LinkedBlockingQueue
: This is a blocking queue
PriorityBlockingQueue
: This is a blocking queue that orders its elements based on their priority
ConcurrentSkipListMap
: This is a non-blocking navigable map
ConcurrentHashMap
: This is a non-blocking hash map
AtomicBoolean
,
AtomicInteger
,
AtomicLong
, and
AtomicReference
: These are atomic implementations of the basic Java data types
Concurrency design patterns
In software engineering, a design pattern is a solution to a common problem. This solution has been used many times, and it has proved to be an optimal solution to the problem. You can use them to avoid 'reinventing the wheel' every time you have to solve one of these problems. Singleton or Factory are examples of common design patterns used in almost every application.
Concurrency also has its own design patterns. In this section, we describe some of the most useful concurrency design patterns and their implementation in the Java language.
Signaling
This design pattern explains how to implement the situation where a task has to notify an event to another task. The easiest way to implement this pattern is with a semaphore or a mutex, using the ReentrantLock or Semaphore classes of the Java language or even the wait() and notify() methods included in the Object class.
See the following example:
public void task1() { section1(); commonObject.notify(); } public void task2() { commonObject.wait(); section2(); }
Under these circumstances, the section2() method will always be executed after the section1() method.
Rendezvous
This design pattern is a generalization of the Signaling pattern. In this case, the first task waits for an event of the second task and the second task waits for an event of the first task. The solution is similar to that of Signaling, but in this case, you must use two objects instead of one.
See the following example:
public void task1() { section1_1(); commonObject1.notify(); commonObject2.wait(); section1_2(); } public void task2() { section2_1(); commonObject2.notify(); commonObject1.wait(); section2_2(); }
Under these circumstances, section2_2() will always be executed after section1_1() and section1_2() after section2_1(). Take into account that if you put the call to the wait() method before the call to the notify() method, you will have a deadlock.
Mutex
A mutex is a mechanism that you can use to implement a critical section, ensuring the mutual exclusion. That is to say, only one task can execute the portion of code protected by the mutex at once. In Java, you can implement a critical section using the synchronized keyword (that allows you to protect a portion of code or a full method), the ReentrantLock class, or the Semaphore class.
Look at the following example:
public void task() { preCriticalSection(); try { lockObject.lock() // The critical section begins criticalSection(); } catch (Exception e) { } finally { lockObject.unlock(); // The critical section ends postCriticalSection(); }
Multiplex
The Multiplex design pattern is a generalization of the Mutex. In this case, a determined number of tasks can execute the critical section at once. It is useful, for example, when you have multiple copies of a resource. The easiest way to implement this design pattern in Java is using the Semaphore class initialized to the number of tasks that can execute the critical section at once.
Look at the following example:
public void task() { preCriticalSection(); semaphoreObject.acquire(); criticalSection(); semaphoreObject.release(); postCriticalSection(); }
Barrier
This design pattern explains how to implement the situation where you need to synchronize some tasks at a common point. None of the tasks can continue with their execution until all the tasks have arrived at the synchronization point. Java Concurrency API provides the CyclicBarrier class, which is an implementation of this design pattern.
Look at the following example:
public void task() { preSyncPoint(); barrierObject.await(); postSyncPoint(); }
Double-checked locking
This design pattern provides a solution to the problem that occurs when you acquire a lock and then check for a condition. If the condition is false, you have the overhead of acquiring the lock ideally. An example of this situation is the lazy initialization of objects. If you have a class implementing the Singleton design pattern, you may have some code like this:
