Storage being freed must still be replaced into its area of origin, but this is a manageable problem.
The freeing thread could simply block. It could place the pointer to be freed onto a list for that
area and let the thread holding the lock take care of doing the freeing on its way out. We could
dedicate a special thread to the task of returning freed storage to its proper location. A variation on
a theme for this design involves using a small hashtable that maps the TID to a specific malloc
area, reducing the amount of searching involved.
These are a few of the most common problems that we have seen. There are two points worthy of
note: (1) There are many viable solutions to every problem; and (2) no one solution is optimal for
all aspects of a problem. Each of the three versions of malloc() is fastest in some situation.
Although Java does not have trylock methods, virtually the same effect may be accomplished
by locking the array of pointers and including an "in use" bit. As of the writing of this topic,
several people were working on different variations of this last solution. We will probably see
them in later operating system releases by the different vendors.
Manipulating Lists
Now we are going to take a look at some designs for a program that adds, removes, and searches
for entries on a singly linked list (Figure 12-4). The program creates a list of people with their
salaries. One set of threads is going to search down that list looking for friends of Bil's, and give
those people raises. Another set of threads is going to search down the list looking for people
whom Dan detests and remove those people from the list. There may be some overlap of Bil's
friends and Dan's enemies.
Figure 12-4. Friends/Enemies: Basic Design
To make the program a bit more interesting (and emphasize certain issues), we will associate a
delay time with each raise and liquidation. These delays may represent the time to write to disk or
to do additional computation. For this purpose we'll make a call to sleep(). On Solaris, the
minimum sleep time is 10 ms (it's based on the system clock), which is typical for most OSs. The
main question we'll be asking is: "For a given configuration of CPUs, delay times, list length, and
number of threads giving raises and performing deletions, which design is best?" For different
configurations we'll get different answers.
Basic Design
Search WWH :
