6. Counting
Keywords: perfbook_html

#
6. Counting

Counting is perhaps the simplest and most natural for a computer to do. However, counting efficiently and scalably on a large shared-memory multiprocessor can be quite challenging. Furthermore, the simplicity of the underlying concept of counting allows us to explore the fundamental issues of concurrency without the distractions of elaborate data structures or complex synchronization primitives. Counting therefore provides an excellent introduction to parallel programming.

This chapter covers a number of special cases for which there are simple, fast, and scalable counting algorithms. But first, let us find out how much you already know about concurrent counting.

Quick Quiz 6.1: Why on earth should efficient and scalable counting be hard? After all, computers have special hardware for the sole purpose of doing counting, addition, subtraction, and lots more besides, don't they??? End Quick Quiz

Quick Quiz 6.2: Network-packet counting problem. Suppose that you need to collect statistics on the number of networking packets (or total number of bytes) transmitted and/or received. Packets might be transmitted or received by any CPU on the system. Suppose further that this large machine is capable of handling a million packets per second, and that there is a systems-monitoring package that reads out the count every five seconds. How would you implement this statistical counter? End Quick Quiz

Quick Quiz 6.3: Approximate structure-allocation limit problem. Suppose that you need to maintain a count of the number of structures allocated in order to fail any allocations once the number of structures in use exceeds a limit (say, 10,000). Suppose further that these structures are short-lived, that the limit is rarely exceeded, and that a ``sloppy'' approximate limit is acceptable. End Quick Quiz

Quick Quiz 6.4: Exact structure-allocation limit problem. Suppose that you need to maintain a count of the number of structures allocated in order to fail any allocations once the number of structures in use exceeds an exact limit (say, 10,000). Suppose further that these structures are short-lived, and that the limit is rarely exceeded, that there is almost always at least one structure in use, and suppose further still that it is necessary to know exactly when this counter reaches zero, for example, in order to free up some memory that is not required unless there is at least one structure in use. End Quick Quiz

Quick Quiz 6.5: Removable I/O device access-count problem. Suppose that you need to maintain a reference count on a heavily used removable mass-storage device, so that you can tell the user when it is safe to removed the device. This device follows the usual removal procedure where the user indicates a desire to remove the device, and the system tells the user when it is safe to do so. End Quick Quiz

The remainder of this chapter will develop answers to these questions.

Subsections

- 6.1 Why Isn't Concurrent Counting Trivial?
- 6.2 Statistical Counters
  - 6.2.1 Design
  - 6.2.2 Array-Based Implementation
  - 6.2.3 Eventually Consistent Implementation
  - 6.2.4 Per-Thread-Variable-Based Implementation
  - 6.2.5 Discussion
- 6.3 Approximate Limit Counters
  - 6.3.1 Design
  - 6.3.2 Simple Limit Counter Implementation
  - 6.3.3 Simple Limit Counter Discussion
  - 6.3.4 Approximate Limit Counter Implementation
  - 6.3.5 Approximate Limit Counter Discussion
- 6.4 Exact Limit Counters
  - 6.4.1 Atomic Limit Counter Implementation
  - 6.4.2 Atomic Limit Counter Discussion
  - 6.4.3 Signal-Theft Limit Counter Design
  - 6.4.4 Signal-Theft Limit Counter Implementation
  - 6.4.5 Signal-Theft Limit Counter Discussion
- 6.5 Applying Specialized Parallel Counters
- 6.6 Parallel Counting Discussion