2 – Concepts And Facts

Thread Pool Overview

So I hope you have a basic idea of what a thread is. I’m not going to go into too much detail, but Wikipedia can do wonders. What I’m going to do here is create a Task-based Thread Pool. The concept is like this:

  1. I have n threads.
  2. I have a queue of tasks.
  3. I’m going to have a thread grab a task and run it. Once the task is complete, it will go grab another.
  4. If there are no tasks, the thread will sit and idle until a new task enters the queue.

That’s a very rough explanation, so lets go into more detail.

Task Parallelism

Like I said, I used to think that I would put whole systems on a single thread, which would ultimately be a waste of a perfectly good thread. Each thread works in parallel, and when you’re making a game or any other massive project, you’ll need all the resources you can get your hands on (as long as they don’t kill performance). Take this pseudocode for instance:

This would be equivalent to putting an entire system on a thread:

if(pThread == Thread[0])
	doWorkA();
else if(pThread == Thread[1])
	doWorkB();

Simplistic, yes, but you see how each work function hogs up the entire thread? It will only do that work on that thread. What we want is to do work on the first available, so we can get the most use out of each system in our game. This is an example of Task-Based Threading:

pThreadPool->AddTaskToQueue(doWorkA);
pThreadPool->AddTaskToQueue(doWorkB);
...
[Inside the thread pool]
for(int i = 0; i < ActiveThreadsCount; ++i)
{
	if(pThread->currentTask = NULL)
	{
		TASK* task = qTaskQueue.front();
		qTaskQueue.pop_front();
		pThread->currentTask = task;
	}
}

We send each task to the threadpool, and the threadpool will delegate the task to the first available thread. The threadpool will process all running threads, and when one is finished the work, then the thread will grab a new task

Now, as you can see, the work that I’m sending the threads are functions (function pointers to be more precise).

Thread-Saftey First!

The most frustrating part about multithreading is keeping all your variables “thread-safe.” To be thread-safe means that a task executes successfuly while running simutaneously on multiple threads. Though the concept may sound simple enough, thread-safety is the key challenge of multithreading.

A thread is considered safe when:

  • The only variables it uses are allocated on the stack
  • The task only depends on arguments passed in, and
  • The subroutines it calls all have the same properties

But there are cases where a thread can be unsafe. Key indicators are:

  • Accessing global variables or the heap
  • Allocating or freeing memory that has a global scope
  • Indirect access to data (example: pointers, handles, etc.)
  • any side-effects (example, a function that returns 0, and also modifies a global variable)

Here are several ways to be thread-safe:

  • Reenterant Task – A reenterant task is a task that can be partially executed, then reentered by another thread, then resumed by the original task. Reenterant tasks:
    • Must not hold global or static non-constant data
    • Must not return a memory address to static or global non-constant data
    • Must work only with data provided by the caller
    • Must not rely on locks to singleton resources
    • Must not modify its own code (unless the thread has its own storage)
    • Must not call non-reentrant functions
  • Implementing a reentrant function/task is pretty standard, just as long as you follow the rules. All reentrant functions/tasks are thread-safe, but not all thread-safe tasks are reenterant.

     

  • Mutual Exculsion(Mutex) – Data is serialized by using special mechanisms to make it so only one thread can write to one thread at a time. Mutexes are often not used in game development due to the fact that they block to execute a task, which could cause adverse effects, and they run the danger of causing race conditions, deadlocks, livelocks, starvation, and other thread-related problems if they are not implemented correctly.
  •  

  • Thread-local Storage – Variables are localized so each thread has its own copy, making the variable thread-safe. Common usage of thread-local variables are thread index numbers or thread error codes.
  •  

  • Atomic Operations – Explained below.
  •  

Thread-safety is the main challenge of multithreading, and can be the bane of existance for many a programmer. But don’t fret! With careful implementation, you’ll be able to use one of the strongest resources your computer has to offer!

Volatile != Atomic

References: Wikipedia: Volatile, Wikipedia: Atomic operation

Most people working with threads will come across the volatile keyword and think it’s needed for thread-based programming – Not so! There’s a difference between using the volatile keyword and being atomic.

So what does volatile do? volatile prevents a variable from being optimized by the compiler. For example, we have:

static int foo;
void bar(void)
{
	foo = 0;
	while (foo != 255) {}
}

That’s what we put into our IDE. However, when our compiler reads it, it’ll notice that foo is never being modified inside that while loop. Therefore, the compiler realizes the while loop is infinite, and change it to (something similar to) while (1) {} instead.

But! If we declare volatile before foo, the compiler will not preform the optimization. This is handy if you want the compiler to always check the variable. volatile was never intended to be used in synchronization, but can be handy in other cases.

So then what does it mean to be atomic? What is atomic? When I say “to be atomic” I mean “I have a set of operations here, and if even one fails, the whole thing fails, and I return to my previous state.” Being atomic is not easy to implement, but it’s not hard to understand. Lets say I have a 64-bit value that gets read from 2 32-bit memory locations, and we have 2 processes running, both modifying that 64-bit value. Process 1 takes the first 32-bits and modifies it, but before it can modify the next 32-bits, process 2 comes along and modifies the value. Now that value is neither the new or old value, but some junked hybrid value.

An atomic operation could be thought of, functionally, as a type of lock like a critical section (which, in itself, is an atomic operation), but the key difference is an atomic operation is minimally-blocking, making it difficult to implement, and a great improvement is not always guaranteed, could create added overhead, or it could be overly-complicated for the effort.

Does this mean not to use volatile or atomic operations? Well, ask yourself that question – for the system or object or task you’re working on, do you think you would need it? Perhaps you want to make a volatile bool bIsLocked in your thread, and add that to your atomic operation for that massive networking task – who knows? It all depends on the situation you have at hand.

Lock and Lockless

So locking is the best way to protect data? Not really. Locking does protect data from being overwritten by another thread, but if another thread tries to access the data while it’s locked, the thread will be blocked and have to wait until the data is unlocked (So, what happens when a thread locks data and doesn’t unlock it, and another thread tries to process that data? Deadlock will occur).

So am I now telling you locking is bad? Not at all. Locking, when used correctly and minimally, can be all that you really need. However, if your project gets to the point where your threadpool is now overly blocking (causing performance to drop dramatically) then you’ll want to look into Lockless algorithms.

I’m not using any Lock-less algorithms in this tutorial – reason being is that the scope of this thread pool doesn’t necessarily require it, and 2 because it’s very difficult to wrap you mind around. There is no standard way to perform some of the necessary operations for locklessness on all platforms. Maybe one day I’ll work on a lockless library, but until then, the algorithms in this tutorial will do fine.

So, you pretty much have a grasp on core concepts in threading, and what we’re trying to accomplish in the thread pool.

Now it’s time to start development of the thread pool.

>> Next, Step 1: Utilities, Locks and Algorithms >>

Advertisements

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