3 – Thread Pool Step 1: Utilities, Locks and Algorithms

Utilities:

We’re going to set up some classes and type definitions for use through-out the thread pool. These will be our utility objects, stored in the kmp::threading::utility namespace. For this project, we only have 2 objects in our Utility namespace: a function pointer typedefined as KMTaskFunc and an abstract base class entitled IKMTaskData. Lets have a look:

namespace utility
{
	//Class Interfaces
	class IKMTaskData
	{
	public:
		IKMTaskData() {}
		IKMTaskData(const IKMTaskData&) {}
		IKMTaskData& operator = (const IKMTaskData&) {}
		virtual ~IKMTaskData() = 0 {};
	};

	//Type Definitions
	typedef void (*KMTaskFunc)(IKMTaskData*);

}

These 2 objects are actually the heart of the thread pool, believe it or not (if you don’t: OK, fine, enjoy your busted thread pool). Here is an overview on how the KMTaskFunc and IKMTaskData work inside the thread pool.

KMTaskFunc

This function pointer is going to be the task we want to put on another thread. You can define this function anywhere inside your program* – the thread pool itself will be set up to accept a function pointer to send to the threads.

The task function pointer we’ve set up here is returning void. You could have it return another value, but you would need to set up a way to get that value back from the threads, which is pretty tedious, so we’ll stick to the basics. The only parameter is a pointer to the ABC IKMTaskData.

IKMTaskData

A problem with threading is the passing of data, especially shared data. Because of paralellism, threads that share a variable could modify it or access it at the same time (as I’ve said on page 2). A method around this is to give the thread classes local storage of the data they need to complete the task, filled out with data from the exact moment they were created that won’t be modified by other threads (meaning: avoid using pointers).

To do this effectively, we have our IKMTaskData. When you’re developing you tasks, you’ll create child classes the derive from this ABC, Adding in members and such that your task will need, to pass along to the threads. When sending this task to the thread pool, the pool will cast your class to the IKMTaskData. Inside or your task, you’ll cast it back to your child object, and grab all the yummy data goodness you loaded into it. Simple.

* Note: If your task function pointer is a member function inside a class, it won’t work; the function must be static in order to work correctly. A method around this is to create a static member function in your class, and in your child IKMTaskData class, have a pointer to this. Inside that static function, you would call the task you wanted to multithread.

Example:

First, create the task child object, adding whatever members you’ll need.

class taskData : IKMTaskData
{
	public:
	A* ptr_A;
	int _a;
	int _b;
	...
	...
}

Define our class, with the task that gets called by the thread, and the task that does the actual work.

class A
{
	void task(int a, int b)
	{
		//Do Stuff...
	}
	static void STATIC_TASK(IKMTaskData* data)
	{
		taskData* myData = (taskData*)data;
		A* myClass = myData->ptr_A;
		myClass->task(myData->_a, myData->_b);
	}
	...
	...
}

Then, somewhere inside of class A…

...
...
pthreadpool->AddTask(STATIC_TASK, new taskData(this, 100, 6));
...
...

Locking

KMLock

Locking is one of the more powerful tools we have when developing multithreaded applications, but it’s also a double-edged sword when abused. Locking, in terms of threading, prevents other threads from running a segment of code while it’s “locked” and will block all other threads until the segment is Unlocked. That’s very helpful if you have sensitive data that should only be modified by one thread at a time…

But it can slow you down. How? Think about it: you’re blocking the other threads from processing code (assuming other threads want to process the same code all at once). You create a bottle neck. However, if you keep the segment small enough, and don’t use locks like a madman, you’ll be fine. In the event that you make a game to the scale of Crysis or World of Warcraft, and you’re locking so much your game is moving at 6 FPS, then you may want to consider looking into lockless algorithms (and, I warn you, locklessness is a pain).

So here’s a glimpse at the KMLock class we use in the thread pool.

class KMLock
{
private:
	CRITICAL_SECTION m_critsec;
public:
	KMLock()
	{
		::InitializeCriticalSection(&m_critsec);
	}
	~KMLock()
	{
		::DeleteCriticalSection(&m_critsec);
	}
	void Lock()
	{
		::EnterCriticalSection(&m_critsec);
	}
	void Unlock()
	{
		::LeaveCriticalSection(&m_critsec);
	}
protected:
};

For the locks, we’re just using Windows Critical Sections (maybe one day I’ll change it to use a more cross-platform implemntation, but for now that is fine). Use this class wisely and sparingly; don’t lock what doesn’t need to be.

Algorithms

KMQueue

To make this simple: *SPOILER ALERT!* our Thread Pool class is going to contain a task queue. Once one our threads goes idle, it will check the task queue, and pop off the next task and run it. That’s how the heart beats in our thread pool (unless you’re the guy who chose to be the “nonbeliever” earlier).

So why did I make a queue? I used Critical Sections earlier, and Windows has the STD library!

Let me tell you something: the current C++ STD library isn’t thread-safe (but the STD library coming in C++0x is); there’s no locking, no compare-and-swaps – nothing. That’s why I’ve researched what’s called a Two-Lock Queue by Maged M. Michael and Michael L. Scott. You can find the PDF they wrote on it here for more information -> 1996 PODC Queues. I’m going to just run down the quick-and-dirty basics with you.

Our problem here is we’ll have a time when one thread will try modifying the queue while another thread is. They’ll run into problems like trying to delete data while another thread is accessing it, or the ABA problem. Our simplistic solution requires just 2 locks and a false head.

Our queue is comprised of nodes. The nodes are simple: a templated TYPE for the item in the node, and a next pointer. Our queue has 4 members: a head node pointer, a tail node pointer, a KMLock for the head, and a KMLock for the tail.

In the constructor, we create our first node. Why? This node is going to be a dummy node. A problem occurs when 2 threads try to access the same data. One thread can delete the data while the other thread thinks the data is still valid. The other thread tries to use the deleted data and BAM! Zombie thread. So what we do is we use the head pointer as an “invalidation data container.” When we call pop() on the queue, instead of popping off the head and returning the data from the head, we get the data from the heads’ next, then pop the head and move the heads next into the head position. Confusing, but by doing this, we allow for the possiblity for 2 threads to try to access the head. So if one thread gets the head while another is accessing it, the head in the queue is moved to an invalidation container instead of getting totally deleted, so both values are still valid. The heads get deleted on the next pop. (If you still don’t get it (and I don’t blame you) read the whitepaper a few times and look at the code. You’ll facepalm once you get it).

The locks are simple to understand in their logic. They’re just there so one thread can be pushing while another thread is popping. both provide protection to their specified nodes so no 2 threads can try to push() or pop() at the same time.

Then there’s the empty() function, which checks if the queue is empty. if the head node has a next, the queue is not empty. If it’s just the head, then it is (remember, the head is just an invalid dummy). This is the most exciting function in the whole project. Not.

>> Next, Step 2: Setting Up theThreads >>

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s