Multithreading in C++ - The Entire Multithreaded Garbage Collector
(Page 10 of 11 )
The entire multithreaded version of the garbage collector is shown here. Call this file gcthrd.h.
// A garbage collector that runs as a back ground task.
#include <iostream>
#include <list>
#include <typeinfo>
#include <cstdlib>
#include <windows.h>
#include <process.h>
using namespace std;
// To watch the action of the garbage collector, define DISPLAY.
// #define DISPLAY
// Exception thrown when an attempt is made to
// use an Iter that exceeds the range of the
// underlying object.
//
class OutOfRangeExc {
// Add functionality if needed by your application.
};
// Exception thrown when a time-out occurs
// when waiting for access to hMutex.
//
class TimeOutExc {
// Add functionality if needed by your application.
};
// An iterator-like class for cycling through arrays
// that are pointed to by GCPtrs. Iter pointers
// ** do not ** participate in or affect garbage
// collection. Thus, an Iter pointing to
// some object does not prevent that object
// from being recycled.
//
template <class T> class Iter {
T *ptr; // current pointer value
T *end; // points to element one past end
T *begin; // points to start of allocated array
unsigned length; // length of sequence
public:
Iter() {
ptr = end = begin = NULL;
length = 0;
}
Iter(T *p, T *first, T *last) {
ptr = p;
end = last;
begin = first;
length = last - first;
}
// Return length of sequence to which this
// Iter points.
unsigned size() { return length; }
// Return value pointed to by ptr.
// Do not allow out-of-bounds access.
T &operator*() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return *ptr;
}
// Return address contained in ptr.
// Do not allow out-of-bounds access.
T *operator->() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return ptr;
}
// Prefix ++.
Iter operator++() {
ptr++;
return *this;
}
// Prefix --.
Iter operator--() {
ptr--;
return *this;
}
// Postfix ++.
Iter operator++(int notused) {
T *tmp = ptr;
ptr++;
return Iter<T>(tmp, begin, end);
}
// Postfix --.
Iter operator--(int notused) {
T *tmp = ptr;
ptr--;
return Iter<T>(tmp, begin, end);
}
// Return a reference to the object at the
// specified index. Do not allow out-of-bounds
// access.
T &operator[](int i) {
if( (i < 0) || (i >= (end-begin)) )
throw OutOfRangeExc();
return ptr[i];
}
// Define the relational operators.
bool operator==(Iter op2) {
return ptr == op2.ptr;
}
bool operator!=(Iter op2) {
return ptr != op2.ptr;
}
bool operator<(Iter op2) {
return ptr < op2.ptr;
}
bool operator<=(Iter op2) {
return ptr <= op2.ptr;
}
bool operator>(Iter op2) {
return ptr > op2.ptr;
}
bool operator>=(Iter op2) {
return ptr >= op2.ptr;
}
// Subtract an integer from an Iter.
Iter operator-(int n) {
ptr -= n;
return *this;
}
// Add an integer to an Iter.
Iter operator+(int n) {
ptr += n;
return *this;
}
// Return number of elements between two Iters.
int operator-(Iter<T> &itr2) {
return ptr - itr2.ptr;
}
};
// This class defines an element that is stored
// in the garbage collection information list.
//
template <class T> class GCInfo {
public:
unsigned refcount; // current reference count
T *memPtr; // pointer to allocated memory
/* isArray is true if memPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
/* If memPtr is pointing to an allocated
array, then arraySize contains its size */
unsigned arraySize; // size of array
// Here, mPtr points to the allocated memory.
// If this is an array, then size specifies
// the size of the array.
GCInfo(T *mPtr, unsigned size=0) {
refcount = 1;
memPtr = mPtr;
if(size != 0)
isArray = true;
else
isArray = false;
arraySize = size;
}
};
// Overloading operator== allows GCInfos to be compared.
// This is needed by the STL list class.
template <class T> bool operator==(const GCInfo<T> &ob1,
const GCInfo<T> &ob2) {
return (ob1.memPtr == ob2.memPtr);
}
// GCPtr implements a pointer type that uses
// garbage collection to release unused memory.
// A GCPtr must only be used to point to memory
// that was dynamically allocated using new.
// When used to refer to an allocated array,
// specify the array size.
//
template <class T, int size=0> class GCPtr {
// gclist maintains the garbage collection list.
static list<GCInfo<T> > gclist;
// addr points to the allocated memory to which
// this GCPtr pointer currently points.
T *addr;
/* isArray is true if this GCPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
// If this GCPtr is pointing to an allocated
// array, then arraySize contains its size.
unsigned arraySize; // size of the array
// These support multithreading.
unsigned tid; // thread id
static HANDLE hThrd; // thread handle
static HANDLE hMutex; // handle of mutex
static int instCount; // counter of GCPtr objects
// Return an iterator to pointer info in gclist.
typename list<GCInfo<T> >::iterator findPtrInfo(T *ptr);
public:
// Define an iterator type for GCPtr<T>.
typedef Iter<T> GCiterator;
// Construct both initialized and uninitialized objects.
GCPtr(T *t=NULL) {
// When first object is created, create the mutex
// and register shutdown().
if(hMutex==0) {
hMutex = CreateMutex(NULL, 0, NULL);
atexit(shutdown);
}
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
p = findPtrInfo(t);
// If t is already in gclist, then
// increment its reference count.
// Otherwise, add it to the list.
if(p != gclist.end())
p->refcount++; // increment ref count
else {
// Create and store this entry.
GCInfo<T> gcObj(t, size);
gclist.push_front(gcObj);
}
addr = t;
arraySize = size;
if(size > 0) isArray = true;
else isArray = false;
// Increment instance counter for each new object.
instCount++;
// If the garbage collection thread is not
// currently running, start it running.
if(hThrd==0) {
hThrd = (HANDLE) _beginthreadex(NULL, 0, gc,
(void *) 0, 0, (unsigned *) &tid);
// For some applications, it will be better
// to lower the priority of the garbage collector
// as shown here:
//
// SetThreadPriority(hThrd,
// THREAD_PRIORITY_BELOW_NORMAL);
}
ReleaseMutex(hMutex);
}
// Copy constructor.
GCPtr(const GCPtr &ob) {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
p = findPtrInfo(ob.addr);
p->refcount++; // increment ref count
addr = ob.addr;
arraySize = ob.arraySize;
if(arraySize > 0) isArray = true;
else isArray = false;
instCount++; // increase instance count for copy
ReleaseMutex(hMutex);
}
// Destructor for GCPTr.
~GCPtr();
// Collect garbage. Returns true if at least
// one object was freed.
static bool collect();
// Overload assignment of pointer to GCPtr.
T *operator=(T *t);
// Overload assignment of GCPtr to GCPtr.
GCPtr &operator=(GCPtr &rv);
// Return a reference to the object pointed
// to by this GCPtr.
T &operator*() {
return *addr;
}
// Return the address being pointed to.
T *operator->() { return addr; }
// Return a reference to the object at the
// index specified by i.
T &operator[](int i) {
return addr[i];
}
// Conversion function to T *.
operator T *() { return addr; }
// Return an Iter to the start of the allocated memory. Iter<T> begin() {
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter<T>(addr, addr, addr + size);
}
// Return an Iter to one past the end of an allocated array.
Iter<T> end() {
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter<T>(addr + size, addr, addr + size);
}
// Return the size of gclist for this type
// of GCPtr.
static int gclistSize() {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
unsigned sz = gclist.size();
ReleaseMutex(hMutex);
return sz;
}
// A utility function that displays gclist.
static void showlist();
// The following functions support multithreading.
//
// Returns true if the collector is still in use.
static bool isRunning() { return instCount > 0; }
// Clear gclist when program exits.
static void shutdown();
// Entry point for garbage collector thread.
static unsigned __stdcall gc(void * param);
};
// Create storage for the static variables.
template <class T, int size>
list<GCInfo<T> > GCPtr<T, size>::gclist;
template <class T, int size>
int GCPtr<T, size>::instCount = 0;
template <class T, int size>
HANDLE GCPtr<T, size>::hMutex = 0;
template <class T, int size>
HANDLE GCPtr<T, size>::hThrd = 0;
// Destructor for GCPtr.
template <class T, int size>
GCPtr<T, size>::~GCPtr() {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
p = findPtrInfo(addr);
if(p->refcount) p->refcount--; // decrement ref count
// Decrement instance counter for each object
// that is destroyed.
instCount--;
ReleaseMutex(hMutex);
}
// Collect garbage. Returns true if at least
// one object was freed.
template <class T, int size>
bool GCPtr<T, size>::collect() {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
bool memfreed = false;
list<GCInfo<T> >::iterator p;
do {
// Scan gclist looking for unreferenced pointers.
for(p = gclist.begin(); p != gclist.end(); p++) {
// If in-use, skip.
if(p->refcount > 0) continue;
memfreed = true;
// Remove unused entry from gclist.
gclist.remove(*p);
// Free memory unless the GCPtr is null.
if(p->memPtr) {
if(p->isArray) {
delete[] p->memPtr; // delete array
}
else {
delete p->memPtr; // delete single element
}
}
// Restart the search.
break;
}
} while(p != gclist.end());
ReleaseMutex(hMutex);
return memfreed;
}
// Overload assignment of pointer to GCPtr.
template <class T, int size>
T * GCPtr<T, size>::operator=(T *t) {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, if the new address is already
// existent in the system, increment its
// count. Otherwise, create a new entry
// for gclist.
p = findPtrInfo(t);
if(p != gclist.end())
p->refcount++;
else {
// Create and store this entry.
GCInfo<T> gcObj(t, size);
gclist.push_front(gcObj);
}
addr = t; // store the address.
ReleaseMutex(hMutex);
return t;
}
// Overload assignment of GCPtr to GCPtr.
template <class T, int size>
GCPtr<T, size> & GCPtr<T, size>::operator=(GCPtr &rv) {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, increment the reference count of
// of the new object.
p = findPtrInfo(rv.addr);
p->refcount++; // increment ref count
addr = rv.addr;// store the address.
ReleaseMutex(hMutex);
return rv;
}
// A utility function that displays gclist.
template <class T, int size>
void GCPtr<T, size>::showlist() {
if(WaitForSingleObject(hMutex, 10000)==WAIT_TIMEOUT)
throw TimeOutExc();
list<GCInfo<T> >::iterator p;
cout << "gclist<" << typeid(T).name() << ", "
<< size << ">:\n";
cout << "memPtr refcount value\n";
if(gclist.begin() == gclist.end()) {
cout << " -- Empty --\n\n";
return;
}
for(p = gclist.begin(); p != gclist.end(); p++) {
cout << "[" << (void *)p->memPtr << "]"
<< " " << p->refcount << " ";
if(p->memPtr) cout << " " << *p->memPtr;
else cout << " ---";
cout << endl;
}
cout << endl;
ReleaseMutex(hMutex);
}
// Find a pointer in gclist.
template <class T, int size>
typename list<GCInfo<T> >::iterator
GCPtr<T, size>::findPtrInfo(T *ptr) {
list<GCInfo<T> >::iterator p;
// Find ptr in gclist.
for(p = gclist.begin(); p != gclist.end(); p++)
if(p->memPtr == ptr)
return p;
return p;
}
// Entry point for garbage collector thread.
template <class T, int size>
unsigned __stdcall GCPtr<T, size>::gc(void * param) {
#ifdef DISPLAY
cout << "Garbage collection started.\n";
#endif
while(isRunning()) {
collect();
}
collect(); // collect garbage on way out
// Release and reset the thread handle so
// that the garbage collection thread can
// be restarted if necessary.
CloseHandle(hThrd);
hThrd = 0;
#ifdef DISPLAY
cout << "Garbage collection terminated for "
<< typeid(T).name() << "\n";
#endif
return 0;
}
// Clear gclist when program exits.
template <class T, int size>
void GCPtr<T, size>::shutdown() {
if(gclistSize() == 0) return; // list is empty
list<GCInfo<T> >::iterator p;
#ifdef DISPLAY
cout << "Before collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
for(p = gclist.begin(); p != gclist.end(); p++) {
// Set all remaining reference counts to zero.
p->refcount = 0;
}
collect();
#ifdef DISPLAY
cout << "After collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
}
Next: Using the Multithreaded Garbage Collector >>
More C++ Articles
More By McGraw-Hill/Osborne
|
 This article is taken from chapter three of The Art of C++, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072255129). Check it out at your favorite bookstore. Buy this book now.
|
|
