6.5 Applying Specialized Parallel Counters

Although the exact limit counter implementations in Section [*] can be very useful, they are not much help if the counter's value remains near zero at all times, as it might when counting the number of outstanding accesses to an I/O device. The high overhead of such near-zero counting is especially painful given that we normally don't care how many references there are. As noted in the removable I/O device access-count problem on page [*], the number of accesses is irrelevant except in those rare cases when someone is actually trying to remove the device.

One simple solution to this problem is to add a large ``bias'' (for example, one billion) to the counter in order to ensure that the value is far enough from zero that the counter can operate efficiently. When someone wants to remove the device, this bias is subtracted from the counter value. Counting the last few accesses will be quite inefficient, but the important point is that the many prior accesses will have been counted at full speed.

Quick Quiz 6.46: What else had you better have done when using a biased counter? End Quick Quiz

Although a biased counter can be quite helpful and useful, it is only a partial solution to the removable I/O device access-count problem called out on page [*]. When attempting to remove a device, we must not only know the precise number of current I/O accesses, we also need to prevent any future accesses from starting. One way to accomplish this is to read-acquire a reader-writer lock when updating the counter, and to write-acquire that same reader-writer lock when checking the counter. Code for doing I/O might be as follows:



  1 read_lock(&mylock);
  2 if (removing) {
  3   read_unlock(&mylock);
  4   cancel_io();
  5 } else {
  6   add_count(1);
  7   read_unlock(&mylock);
  8   do_io();
  9   sub_count(1);
 10 }


Line 1 read-acquires the lock, and either line 3 or 7 releases it. Line 2 checks to see if the device is being removed, and, if so, line 3 releases the lock and line 4 cancels the I/O, or takes whatever action is appropriate given that the device is to be removed. Otherwise, line 6 increments the access count, line 7 releases the lock, line 8 performs the I/O, and line 9 decrements the access count.

Quick Quiz 6.47: This is ridiculous! We are read-acquiring a reader-writer lock to update the counter? What are you playing at??? End Quick Quiz

The code to remove the device might be as follows:



  1 write_lock(&mylock);
  2 removing = 1;
  3 sub_count(mybias);
  4 write_unlock(&mylock);
  5 while (read_count() != 0) {
  6   poll(NULL, 0, 1);
  7 }
  8 remove_device();


Line 1 write-acquires the lock and line 4 releases it. Line 2 notes that the device is being removed, and the loop spanning lines 5-7 wait for any I/O operations to complete. Finally, line 8 does any additional processing needed to prepare for device removal.

Quick Quiz 6.48: What other issues would need to be accounted for in a real system? End Quick Quiz

Paul E. McKenney 2011-12-16