High-Performance Java Platform Computing: Multithreaded and Networked Programming

About

Features

Description

• The clear, practical guide to Java threads and concurrency
• Proven design patterns and extensive code library
• Expert techniques for optimizing networked/distributed applications
• Avoiding deadlocks, race conditions, and synchronization problems

Threading, concurrency, and beyond: Your crystal-clear Java performance guide and code library!

Threading and concurrency are crucial to building high-performance Java applications — but they have a reputation for complexity. High-Performance Java Computing thoroughly demystifies them, helping developers leverage threading and concurrency to solve a wide variety of performance problems — especially in networked, distributed applications. This book delivers practical solutions, proven design patterns, and a rigorously tested code library: everything you need to build optimized Java software for technical, business, and e-Commerce applications. Coverage includes:

• Java 2 Threads classes: daemon threads, thread control, scheduling, and more
• Solving the key problems of parallelism: deadlocks, race conditions, and synchronization
• Advanced techniques for optimizing concurrent code
• Java monitors, parallelizing loops, and parallel execution of subroutines in shared memory
• New design patterns for distributed application development

There's never been a more accessible, practical guide to Java multi-threading, concurrency, and other high-performance techniques. When performance really matters, turn to High-Performance Java Computing — and find the solution you're searching for!

Sample Content

Downloadable Sample Chapter

Click here for a sample chapter for this book: 0130161640.pdf

Table of Contents

1. Foundations.

The von Neumann Machine. Flynn's Taxonomy. Control-Memory Taxonomy. Speedup and Efficiency. Amdahl's Law. Scalability. Problems of Parallelism. Grain Size. Starvation. Deadlock. Flooding and Throttling. Layout. Latency. Scheduling. Programming Techniques. Chapter Wrap-up. Exercises.

Why Is Multithreading Useful? Overview of the Java Threads Classes. Thread: The Class Responsible for Thread Creation and Execution. Runnable: Making Threads Without Extending the Thread Class. Hello World: A First Example of Multithreading. Implementing Interfaces and Extending Classes: What's the Deal? Concepts. A Little Bit of History. Some Definitions. Multiprogramming vs Multitasking. Concurrency vs Parallelism vs Distribution. Threads vs Processes. Kernel-level vs User-level Threads. Quick Tour of Java Threads Functions. Construction. Daemon Threads. Thread Control. Very Useful Static Methods. Thread Synchronization. Cooperative Multitasking. Prioritized Scheduling. Miscellaneous Status Methods. Methods Not Covered Here. Exercises.

Know Your Enemy! Race Conditions. Egoist: A First Study in Race Conditions. A Word on Priorities. What Is a Race Condition? Race0 Class. Critical Sections and Object Locking. Race1 Class-Fixing Race0 with Synchronization. Conditions. Motivating the Need for Conditions. Key Object Methods Needed to Work with Conditions in Java. File Copying: A Producer-Consumer Example. Locks-Binary Semaphores: An Example of Using Conditions. Race2: Reworked Race1 Using Locks. Classic Synchronization Mechanisms. Counting Semaphore. Barrier. Futures. Deadlock. What Is Deadlock? How to Know When Deadlock Has Hit You? Four Conditions of Deadlock. A Classic Example: Dining Philosophers. Chapter Wrap-up. Exercises.

Real Monitors and Java Monitors. Class Monitor in the Thread Package. Monitor's Methods. Interface MonitorCondition's Methods. Interface MonitorLock. Examples using Monitor Objects. SimpleFuture. SharedTableOfQueues. Implementation of Monitor, Condition, and MonitorLock. Monitor Entry and Exit. Monitor.Condition. Monitor.Lock. The Multiple Reader-Writer Monitors. Policies. Entering and Leaving the Critical Sections. The Single-Reader-Writer Monitor. The Readers-Preferred Monitor. The Writers-Preferred Monitor. The Alternating Readers-Writers Monitor. The Take-a-Number Monitor. Chapter Wrap-up. Exercises.

Creating and Joining. Example: Trapezoidal Numeric Integration. RunQueue. RunQueue Methods. RunQueue Implementation. Recursive Shell Sort: RunQueues and SimpleFutures. Accumulator. Accumulator Operations. Patterns of Use of Accumulators. Using Accumulators. Numeric Integration. TerminationGroup. Combinatorial Search. The 0-1 Knapsack Problem. Parallel Depth-first Search for the Knapsack Problem. Knapsack2. PriorityRunQueue. Branch-and-Bound with Priority Run Queues. Branch and Bound for 0-1 Knapsack. A Purer Branch-and-Bound 0-1 Knapsack. Chapter Wrap-up. Exercises.

Chore Graphs. Gathering Chores into Threads. Example: Warshall's Algorithm. Static Scheduling. Dynamic Scheduling. Example: Longest Common Subsequence. Example: Shell Sort. Chapter Wrap-up. Exercises.

The RunDelayed Interface. Futures. FutureFactory. Chore-programming Techniques. Job Jars. Chore Graphs. Macro Dataflow. Flow of Control. Macro Dataflow Examples: Vector Addition. Continuations to Separate Operand Fetch from Operation. Static Dataflow Style and Storing Operands in Instructions. Fetching in Continuations. Chore examples: Warshall's Algorithm. WarshallDF1 and Warshall's Algorithm in Dataflow. WarshallC1 through WarshallC3: Chores, But Not Dataflow. Chapter Wrap-up. Exercises.

TerminationGroup. Barrier. BarrierFactory. AccumulatorFactory. Parallel Quicksort. Shell Sort. Chapter Wrap-up.

Shared Tables of Queues. Methods. Implementing Synchronizations Using a Shared Table of Queues. Indexed Keys. Implementing More Synchronizations and Shared Structures. Reactive Objects. Communicating through a Shared Table of Queues. Future Queues. Methods. Implementation of FutureQueue. Example of FutureQueue: The Queued Readers-Writers Monitor. Future Tables. Chapter Wrap-up. Exercises.

The Streams Abstraction. Building Your Own Stream. Caesar Cipher: Very Basic Encryption. Chapter Wrap-up. Exercises.

Exploring the Client Side. Services: The Internet Story. Destination Sendmail. Java Networking: Socket and InetAddress. Where Are the Services? A Kind and Gentle Introduction to the Server Side. Iterative Servers. Simple Messaging Architecture. The Message Class. DateService and DateClient SMA Style. Chapter Wrap-Up. Exercises.

Generic Mailbox Invocations. GMI: Goals and Design Overview. Callable: An Interface for Accepting Communication. CallMessage: An Abstract Class for Marshalling and Unmarshalling! RemoteCallServer. RemoteCallServerDispatcher. MemoServer. MemoClient. Vector Inner Product. Trapezoidal Integration. Warshall's Algorithm. Chapter Wrap-up. Exercises.

Preface

Preface

This is a book about programming high-performance multithreaded applications using the Java language.

Multithreading and multiprogramming, long heralded as useful ideas in the computing literature, have been the focus of numerous textbooks on operating systems, parallel and distributed computing, and, most, recently Java. Yet a key question remains unanswered: Why would one really use threads in the first place?

Our book attacks this question from the bottom up and the top down. Beginning with the bottom-up discussion, threads have been created with the primary goal of improving performance of software applications. At a low level, a thread is much like a process, but differs from processes in one key respect: resource consumption. This is because threads, unlike processes, share common code and data, thus having a lower cost of creation and context-switching overhead.

On the other hand, the low-level focus on threads-the mechanism-has much to do with why threads have not achieved widespread usage in applications. Threads do allow great advances in performance to be made, but not without some up-front program structuring. The fact that all threads share data structures can in many cases lead to poor performance, due to synchronization costs.

To answer the question posed earlier, we believe multithreading exists primarily to allow performance gains to be realized, particularly on scalable hardware platforms, such as parallel supercomputers, workstation clusters, and symmetric multiprocessor (SMP) systems. Our book emphasizes programming techniques and packages for high-end computing (often called the "server side" in the business world). We are concerned with using the power available on multiprocessor computers and computer networks to perform computations rapidly.

This book was conceived as a natural follow-up to a successful series of short courses we offered at the Illinois Institute of Technology and elsewhere to working professionals and graduate students alike. Additionally, between us we have approximately two decades of relevant teaching and research experience in the fields of high-performance computing, object-oriented systems, programming languages, and operating systems.

Our research in high-performance computing and languages has always focused on facilitating the development of concurrent, parallel, and distributed software, going back as far as 1988, when we first began working together on the Message Driven Computing (MDC) environment. We have developed a number of working programming languages and libraries to support such software development. All of the work we did in the past, however, was done in the C, Icon, and C++ programming languages. For this book, we have reworked many of our ideas into a form more suitable for the practicing software engineer, while fully exploiting the power of a true object language such as Java.

With its built-in support for concurrency via a monitorlike abstraction, Java makes concurrent programming easier for programmers than languages such as C and C++. We will discuss how monitors are adequate for solving many problems in concurrency, particularly the so-called classical synchronization problems, which have been well documented in operating-systems textbooks. As more complex libraries and software systems are developed, the evidence gathered supports the proposition that monitors, much like other low-level mechanisms for synchronization, break down. Monitors, despite being a higher-level mechanism for supporting concurrency, present the same problems as found in "less sophisticated" environments such as C and C++ (where low-level threads libraries, such as pthreads and Win32 threads, are used). We refer in the text to these problems (race conditions and deadlocks) as enemies. We present stategies for dealing with these enemies and a number of higher-level frameworks that enable the programmer to worry less often about them.

Java is one of the great programming languages of our time. Like many of the great programming languages, a company was behind its development, adoption, and popularity. The sensational marketing blitz was enough to make many of us think that all of the work on languages was now complete, so we could start packing our bags and look for other work. Now that the dust has settled, it is clear that Java does occupy an important space in the marketplace; however, there is a great deal of potential for exploring other programming languages and techniques. The environments in which Java is being considered will require at least a subset of the ideas presented in this book: network appliances, server-side computing, workstation clustering, and parallel systems, to name a few. In this book, our aim is to give the reader some insight into what Java does and does not provide, in terms of support for concurrency. What Java does not provide, we do provide with a working library of Java code that allows the programmer to "operate at a higher-level" (to borrow a phrase from IBM marketing from the OS/2 days).

This book, like all books, does not exist in a vacuum. There are a number of competing books, some of which are appearing in new editions during the next year. We believe our book will be the first of its kind in terms of multithreading and its application to real-world programming. It also provides the following benefits and features:

1. It presents a human-understandable explanation of multithreading, its implementation, and how it works in Java.
2. It helps the programmer to understand the very real problems encountered in concurrent systems, focused on race conditions, deadlock, and problems encountered when introducing parallelism and distribution. This particular aspect of our book brings to life the chapters on concurrency presented in "abstract" OS textbooks, wherein working code examples are seldom, if ever, provided.
3. It helps the programmer to understand the classic synchronization problems, which have suddenly been placed in the spotlight as more and more code is (incorrectly) being written to exploit concurrency.
4. It introduces high-level approaches to shared- and distributed-memory multithreading. This section will be of great interest to those who want to develop multithreaded applications but prefer to work at a higher level.
5. It shows how to extend the threads concept to the network. It shows how to extend the threads model beyond the single Java Virtual Machine (JVM) to a network of JVMs.

We hope you enjoy this book. It has been written to address the needs of a broad audience. There is introductory, intermediate, and advanced material. The book is designed to be progressive and can be used either as a reference or as a companion to a variety of courses. Exercises are provided at the end of each chapter to reinforce the principles.

Speaking of Code

Code for the Tools of Computing thread package is available through our company Web site at http://www.toolsofcomputing.com. You will find links to it on the book sub-Web at http://www.toolsofcomputing.com/JavaThreads. We also provide a number of other useful, free packages via the sub-Web.

The example programs are working examples. We have run all of them. We hope the printed versions are as error free as possible; however, mistakes do occur and bugs are found. We actually use our code for development and will regularly update the site to include the latest code. All of the code is freely available under a GNU LGPL-style license.

The algorithm animations available include parallel sorting algorithms and simulations of multiple readers and writers synchronizing with the monitors shown in "The Multiple Reader-Writer Monitors" on page 110. These animations are applets.

We will maintain an errata forum to report errors and corrections found after publication.

Animations

The Multiple Readers-Writers Simulations Color Codes

The simulations include an array of buttons that indicate the states of the threads accessing the shared structure. The colors of the buttons the threads states:

How to Change the Parameters

You can change the parameters in the multiple readers-writers simulations.

You may choose to have a thread choose randomly each time whether to read or write (the default) or to be always be a reader or always a writer. The "% reads" and "# readers" radio buttons choose which option. You use the corresponding text fields to specify the percent probability of reading or the number of threads that are readers, respectively.

To change any number, edit the field and then type ENTER. The new value will not be stored until ENTER is pressed.

You can choose whether the actual read, write, and rest times are constants or whether they are generated from negative exponential distributions. You are able to specify the times' constant or mean values. If you change the mean read, write, or rest times, you should probably not go much below 200ms; smaller values don't give Java enough time to refresh the display. Constant times give simulations that are easier to understand.

You can change any of the values in the left column. The bottom four text fields on the right are output fields. Although you can change the lower four fields yourself, making manual changes won't have any influence on the simulation.

Experiments

There are several charts in this book showing the performance of parallel algorithms. These charts report experimental runs on an intel dual-processor system running Solaris located in the Java High Performance Computing laboratory at DePaul University in Chicago. The Java system has kernel threads, which allow both processors to execute threads in the same program simultaneously.

The experiments were run from scripts that executed, in random order, the algorithms, problem sizes, and number of threads. This was to avoid potential errors that could occur if the system had different loads at different times. If we did not randomize the order, we might not be seeing the effects of the parameters, but rather of system load. The runs in the scripts were separated with sleep calls in order to prevent Unix from "nicing" our priority down because our process is compute-bound.

Each algorithm-problem size-number of threads combination was run 32 times to allow the use of large-sample statistics.

In some of the summary charts, where we combine several runs, we did not run the experiments again with the same care for randomizing the runs; therefore, these comparisons may be viewed with suspicion, because they may show effects of differing system loads.

Running the Exercises

To run programs for most of the exercises, you will need a multiprocessor and a kernel-threads version of Java (at least if you want to see any kind of performance improvement). Intel dual-processor systems have become inexpensive. Solaris and Linux are reasonable operating systems, as are Windows NT and successors.

Updates

Submit Errata