This chapter might be considered an extension of Chapter 11, “Programming the Perfect Game Loop,” because the subject of multi-threading is related to timing and interrupt programming. These topics might, in fact, be considered precursors to multi-threaded programming. A thread is a set of instructions, usually in a loop, that run in parallel with other sets of instructions (or threads) in a program. In a multitasking operating system, every program has at least one thread—itself—because the operating system breaks down every running process into one or more threads that may take advantage of dual-core or multiple processors in a computer system.
Here is a breakdown of the major topics in this chapter:
What is multi-threading?
The Posix Thread library
Every modern operating system uses threads for essential and basic operation and would not be nearly as versatile without threads. A thread is a process that runs within the memory space of a single program but is executed separately from that program. This section will provide a short overview of multi-threading and how it can be used (fairly easily) to enhance a game. I will not go into the vast details of threaded programming because the topic is too huge and unwieldy to fully explain in only a few pages. Instead, I will provide you with enough information and example code that you will be able to start using threads.
To be multi-threaded, a program will create at least one thread that will run in addition to that program's main loop. Any time a program uses more than one thread, you must take extreme caution when working with data that is potentially shared between threads. It is generally safe for a program to share data with a single thread (although it is not recommended), but when more than one thread is in use, you must use a protection scheme to protect the data from being manipulated by two threads at the same time.
To protect data, you can make use of mutexes that will lock data inside a single thread until it is safe to unlock the data for use in the main program or in another thread. The locking and unlocking must be done inside a loop that runs continuously inside the thread callback function. Note that if you do not have a loop inside your thread function, it will run once and terminate. The idea is to keep the thread running—doing something—while the main program is doing the delegating. You should think of a thread as a new employee who has been hired to alleviate the amount of work done by the program (or rather, by the main thread). To demonstrate, at the end of this section I'll walk you through a multi-threaded example in which two distinct threads control two identical sprites on the screen, with one thread running faster than the other, while the program's main loop does nothing more than blit the double-buffer to the screen.
We disseminate the subject as if it's just another C function, but threads were at one time an extraordinary achievement that was every bit as exciting as the first connection in ARPAnet in 1969 or the first working version of UNIX. In the 1980s, parallel programming was as hip as virtual reality, but like the latter term, it was not to be a true reality until the early 1990s. Multi-threaded programming is the engineer's term for parallel processing and is a solution that has been proven to work. The key to parallel processing came when software engineers realized that the processor is not the focus; rather, software design is. In the words of Agent Smith from The Matrix, “We lacked a programming language with which to construct your world.”
A single-processor system should be able to run multiple threads. Once that goal was realized, adding two or more processors to a system provided the ability to delegate those threads, and this was a job for the operating system. No longer tasked with designing a parallel-processing architecture, engineers in both the electronics and software fields abstracted the problem so the two were not reliant upon each other. A single program can run on a motherboard with four CPUs and push all of those processors to the limit, if that single program invokes multiple threads. As such, the programs themselves were treated as single threads. And yet, there can be many non-threaded programs running on our fictional quad-processor system, and it might not be taxed at all. It depends on what each program is doing.
Math-intensive processes, such as 3D rendering, can eat a CPU for breakfast. But with the advent of threading in modern operating systems, programs such as 3D Studio Max, Maya, Lightwave, and Photoshop can invoke threads to handle intense processes, such as scene rendering and image manipulation. Suddenly, that dual-G5 Mac is able to process a Photoshop image in four seconds, whereas it took 45 seconds on your G3 Mac! Why? Threads.
However, just because a single program is able to share four CPUs, that doesn't mean each thread is an independent entity. Any global variables in the program (main thread) can be used by the invoked threads as long as care is taken that data is not damaged. Imagine 10 children grasping for an ice cream cone at the same time and you get the picture. What your threaded program must do is isolate the ice cream cone for each child, and only make the ice cream cone available to the others after that child has released it. Get the picture?
How does this concept of threading relate to processes? As you know, modern operating systems treat each program as a separate process, allocating a certain number of milliseconds to each process. This is where you get the term “multitasking;” many processes can be run at the same time using a time-slicing mechanism. A process has its own separate heap and stack and can contain many threads. A thread, on the other hand, has its own stack but shares the heap with other threads within the process. This is called a thread group.
The vast majority of Linux and UNIX operating system flavors will already have the pthread library installed because it is a core feature of the kernel. Other systems might not be so lucky. Windows uses its own multi-threading library. Of course, a primary goal of this book is to keep this code 100-percent portable. So what you need is a pthread library that is compatible with the POSIX systems. After all, that is what the “p” in pthreads stands for—POSIX threads. An important thing you should know about the Windows implementation of pthread is that it abstracts the Windows threading functionality, molding it to conform to pthread standards.
There is one excellent open-source pthreads library for Windows systems, distributed by Red Hat, that I have chosen for this chapter because it includes makefiles for Visual C++ and Dev-C++. I have included the compiled version of pthread for Visual C++ and Dev-C++ on the CD-ROM in the pthread folder, as Table 21.1 shows. I recommend copying the lib file to your compiler's lib folder (for Visual C++ 2005, the folder is C:Program FilesMicrosoft Visual Studio 8VC8Lib). The header files (pthread.h and sched.h) should be copied to your compiler's include folder (for Visual C++ 2005, this will be C:Program FilesMicrosoft Visual Studio 8VC8Include). The dll file can reside with the executable or in windowssystem32.
Table 21.1. pthread Library Files
Compiler | Lib | DLL |
|---|---|---|
Visual C++ | pthreadVC.lib | pthreadVC.dll |
Dev-C++ | libpthreadGC.a | pthreadGC.dll |
Although Red Hat's pthread library is open source, I have chosen not to distribute it with the book and have only included the libs, dlls, and key headers. You can download the pthread library and find extensive documentation at http://sources.redhat.com/pthreads-win32. I encourage you to browse the site and get the latest version of pthreads-Win32 from Red Hat. Makefiles are provided so it is easy to make the pthread library using whatever recent version of the sources you have downloaded. If you are intimidated by the prospect of having to compile sources, I encourage you to try. I, too, was once intimidated by downloading open source projects; I wasn't sure what to do with all the files. These packages were designed to be easy to make using GCC or Visual C++. All you really need to do is open a command prompt, change to the folder where the source code files are located, and set the path to your compiler. If you are using Dev-C++, for instance, you can type the following command to bring the GCC compiler online.
path=C:Dev-Cppin;%path%
What next? Simply type make GC and presto, the sources will be compiled. You'll have the libpthreadGC.a and pthreadGC.dll files after it's finished. The GC option is a parameter used by the makefile. If you want to see the available options, simply type make and the options will be displayed.
If you are really interested in this subject and you want more in-depth information, look for Butenhof's Programming with POSIX Threads (Addison-Wesley, 1997). Because the Pthreads-Win32 library is functionally compatible with POSIX threads, the information in this book can be applied to pthread programming under Windows.
I am going to cover the key functions in this section and let you pursue the full extent of multi-threaded programming on your own using the references I have suggested. For the purposes of this chapter, I want you to be able to control sprites using threads outside the main loop. Incidentally, the main function in any Allegro program is a thread too, although it is only a single thread. If you create an additional thread, then your program will be using two threads.
First of all, how do you create a new thread? New threads are created with the pthread_create function.
int pthread_create (
pthread_t *tid,
const pthread_attr_t *attr,
void *(*start) (void *),
void *arg);Yeah! That's what I thought at first, but it's not a problem. Here, let me explain. The first parameter is a pthread_t struct variable. This struct is large and complex, and you really don't need to know about the internals to use it (ignorance is bliss, to quote Cipher from The Matrix). If you want more details, I encourage you to pick up Butenhof's book as a reference.
The second parameter is a pthread_attr_t struct variable that usually contains attributes for the new thread. This is usually not used, so you can pass NULL to it.
The third parameter is a pointer to the thread function used by this thread for processing. This function should contain its own loop, but should have exit logic for the loop when it's time to kill the thread. (I use a done variable.)
The fourth parameter is a pointer to a numeric value for this thread to uniquely identify it. You can just create an int variable and set it to a value before passing it to pthread_create.
Here's an example of how to create a new thread:
int id; pthread_t pthread0; int threadid0 = 0; id = pthread_create(&pthread0, NULL, thread0, (void*)&threadid0);
So you've created this thread, but what about the callback function? Oh, right. Here's an example:
void* thread0(void* data)
{
int my_thread_id = *((int*)data);
while(!done)
{
//do something!
}
pthread_exit(NULL);
return NULL;
}This brings us to the pthread_exit function, which terminates the thread. Normally you'll want to call this function at the end of the function after the loop has exited. Here's the definition for the function:
void pthread_exit (void *value_ptr);
You can get away with just passing NULL to this function because value_ptr is an advanced topic for gaining more control over the thread.
At this point you can write a multi-threaded program with only the pthread_create and pthread_exit functions, knowing how to create the callback function and use it. That is enough if you only want to create a single thread to run inside the process with your program's main thread. But more often than not, you will want to use two or more threads in a game to delegate some of the workload. Therefore, it's a good idea to use a mutex for all your threads. Recall the ice cream cone analogy. Are you sure that new thread won't interfere with any globals? Have you considered timing? When you call rest to slow down the main loop, it has absolutely no effect on other threads. Each thread can call rest for timing independently of the others. What if you are using a thread to blit the double-buffer to the screen while another thread is writing to the buffer? Most memory chips cannot read and write data at the same time. What is very likely is that you'll update a small portion of the buffer (by drawing a sprite, for instance) while the buffer is being blitted to the screen. The result is some unwanted flicker—yes, even when using a double-buffer. What you have here is a situation that is similar to a vertical refresh conflict, only it is occurring in memory rather than directly on the screen. Do you need a dbsync type of function that is similar to vsync? I wouldn't go that far. What I am trying to point out is that threads can step on each other's toes, so to speak, if you aren't careful to use a mutex.
A mutex is a block used in a thread function to prevent other threads from running until that block is released. Assuming, of course, that all threads use the same mutex, it is possible to use more than one mutex in your program. The easiest way is to create a single mutex, and then block the mutex at the start of each thread's loop, unblocking at the end of the loop.
Creating a mutex doesn't require a function; rather, it requires a struct variable.
//create a new thread mutex to protect variables pthread_mutex_t threadsafe = PTHREAD_MUTEX_INITIALIZER;
This line of code will create a new mutex called threadsafe that, when used by all the thread functions, will prevent data read/write conflicts.
You must destroy the mutex before your program ends; you can do so using the pthread_mutex_destroy function.
int pthread_mutex_destroy (pthread_mutex_t *mutex);
Here is an example of how it would be used:
pthread_mutex_destroy(&threadsafe);
Next, you need to know how to lock and unlock a mutex inside a thread function. The pthread_mutex_lock function is used to lock a mutex.
int pthread_mutex_lock (pthread_mutex_t * mutex);
This has the effect of preventing any other threads from locking the same mutex, so any variables or functions you use or call (respectively) while the mutex is locked will be safe from manipulation by any other threads. Basically, when a thread encounters a locked mutex, it waits until the mutex is available before proceeding. (It uses no processor time; it simply waits.)
Here is the unlock function:
int pthread_mutex_unlock (pthread_mutex_t * mutex);
The two functions just shown will normally return zero if the lock or unlock succeeded immediately; otherwise, a non-zero value will be returned to indicate that the thread is waiting for the mutex. This should not happen for unlocking, only for locking. If you have a problem with pthread_mutex_unlock returning non-zero, it means the mutex was locked while that thread was supposedly in control over the mutex—a bad situation that should never happen. But when it comes to game programming, bad things do often happen while you are developing a new game, so it's helpful to print an error message for any non-zero return.
At this point, you have all the information you need to use multi-threading in your own games and other programs. To test this program in a true parallel environment, I used my dual Athlon MP 1.2-GHz system under Windows 2000 and also under Windows XP. I like how XP is more thread-friendly, as the Task Manager shows the number of threads used by each program, but any single-processor system will run this program just fine. Most dual systems should blow away even high-end single systems with this simple sprite demo because each sprite has its own thread. I have seen rates on my dual Athlon MP system that far exceed a much faster Pentium 4 system, but all that has changed with Intel's Hyper-Threading, Pentium D, and even more recent Core Duo technology built into their high-end CPUs. This essentially means that Intel CPUs are thread-friendly and able to handle multiple threads in a single CPU. Processors have boasted multiple pipelines for a decade now, but now those pipelines are optimized to handle multiple threads.
The MultiThread program (shown in Figure 21.1) creates two threads (thread0 and thread1) with similar functionality. Each thread moves a sprite on the screen with a bounce behavior, with full control over erasing, moving, and drawing the sprite on the double-buffer. This leaves the program's main loop with just a single task of blitting the buffer to the screen.
If you are using Visual C++, you'll want to create a new Win32 Application project, add a new source code file called main.c to the project, and then open the Project Settings dialog box, as shown in Figure 21.2.
On the Link tab, you'll want to type in alleg.lib and pthreadVC.lib separated by a space in the Object/Library Modules field, like this:
alleg.lib pthreadVC.lib
If you are using Dev-C++, you'll want to create a new Windows Application C-language project. Open the Project Options dialog box, go to the Parameters tab, and add the following two options:
-lalleg -lpthreadGC
Tip
The process is similar on all compilers. If you are confused as to where the library is added in your project's configuration, refer back to Chapter 2 for a complete rundown on configuring a project for Allegro. You simply add the pthread library to the same place where you add the Allegro library.
Now you are ready to type in the source code for the MultiThread program. This project uses the sphere.bmp image containing the 32-frame animated ball from the CollisionTest project in Chapter 10. The project is located in completed form in the chapter21MultiThread folder on the CD-ROM. Here is the first section of code for the program:
#include <pthread.h>
#include ''allegro.h''
#define MODE GFX_AUTODETECT_FULLSCREEN
#define WIDTH 640
#define HEIGHT 480
#define BLACK makecol(0,0,0)
#define WHITE makecol(255,255,255)
//define the sprite structure
typedef struct SPRITE {
int dir, alive;
int x,y;
int width,height;
int xspeed,yspeed;
int xdelay,ydelay;
int xcount,ycount;
int curframe,maxframe,animdir;
int framecount,framedelay;
}SPRITE;
//variables
BITMAP *buffer;
BITMAP *ballimg[32];
SPRITE theballs[2];
SPRITE *balls[2];
int done;
int n;
//create a new thread mutex to protect variables
pthread_mutex_t threadsafe = PTHREAD_MUTEX_INITIALIZER;As you can see, you just created the new mutex as a struct variable. Really, there is no processing done on a mutex at the time of creation; it is just a value that threads recognize when you pass &threadsafe to the pthread_mutex_lock and pthread_mutex_unlock functions.
The next section of code in the MultiThread program includes the usual sprite-handling functions that you should recognize.
void erasesprite(BITMAP *dest, SPRITE *spr)
{
//erase the sprite
rectfill(dest, spr->x, spr->y, spr->x + spr->width,
spr->y + spr->height, BLACK);
}
void updatesprite(SPRITE *spr)
{
//update x position
if (+ +spr->xcount > spr->xdelay)
{
spr->xcount = 0;
spr->x += spr->xspeed;
}
//update y position
if (++spr->ycount > spr->ydelay)
{
spr->ycount = 0;
spr->y += spr->yspeed;
}
//update frame based on animdir
if (++spr->framecount > spr->framedelay)
{
spr->framecount = 0;
if (spr->animdir = = -1)
{
if (-spr->curframe < 0)
spr->curframe = spr->maxframe;
}
else if (spr->animdir = = 1)
{
if (++spr->curframe > spr->maxframe)
spr->curframe = 0;
}
}
}
//this version doesn't
void bouncesprite(SPRITE *spr)
{
//simple screen bouncing behavior
if (spr->x < 0)
{
spr->x = 0;
spr->xspeed = -spr->xspeed;
spr->animdir *= -1;
}
else if (spr->x > SCREEN_W - spr->width)
{
spr->x = SCREEN_W - spr->width;
spr->xspeed = -spr->xspeed;
spr->animdir *= -1;
}
if (spr->y < 0)
{
spr->y = 0;
spr->yspeed = -spr->yspeed;
spr->animdir *= -1;
}
else if (spr->y > SCREEN_H - spr->height)
{
spr->y = SCREEN_H - spr->height;
spr->yspeed = -spr->yspeed;
spr->animdir *= -1;
}
}
BITMAP *grabframe(BITMAP *source,
int width, int height,
int startx, int starty,
int columns, int frame)
{
BITMAP *temp = create_bitmap(width,height);
int x = startx + (frame % columns) * width;
int y = starty + (frame / columns) * height;
blit(source,temp,x,y,0,0,width,height);
return temp;
}
void loadsprites()
{
BITMAP *temp;
//load sprite images
temp = load_bitmap("sphere.bmp", NULL);
for (n=0; n<32; n++)
ballimg[n] = grabframe(temp,64,64,0,0,8,n);
destroy_bitmap(temp);
//initialize the sprite
for (n=0; n<2; n++)
{
balls[n] = &theballs[n];
balls[n]->x = rand() % (SCREEN_W - ballimg[0]->w);
balls[n]->y = rand() % (SCREEN_H - ballimg[0]->h);
balls[n]->width = ballimg[0]->w;
balls[n]->height = ballimg[0]->h;
balls[n]->xdelay = 0;
balls[n]->ydelay = 0;
balls[n]->xcount = 0;
balls[n]->ycount = 0;
balls[n]->xspeed = 5;
balls[n]->yspeed = 5;
balls[n]->curframe = rand() % 32;
balls[n]->maxframe = 31;
balls[n]->framecount = 0;
balls[n]->framedelay = 0;
balls[n]->animdir = 1;
}
}Now you come to the first thread callback function, thread0. I should point out that you can use a single callback function for all of your threads if you want. You can identify the thread by the parameter passed to it, which is retrieved into my_thread_id in the function listing that follows. You will want to pay particular attention to the calls to pthread_mutex_lock and pthread_mutex_unlock to see how they work. Note that these functions are called in pairs above and below the main piece of code inside the loop. Note also that pthread_exit is called after the loop. You should always provide a way to exit the loop so this function can be called before the program ends. More than likely, all threads will terminate with the main process, but it is good programming practice to free memory before exiting.
//this thread updates sprite 0
void* thread0(void* data)
{
//get this thread id
int my_thread_id = *((int*)data);
//thread's main loop
while(!done)
{
//lock the mutex to protect variables
if (pthread_mutex_lock(&threadsafe))
textout_ex(buffer,font,"ERROR: thread mutex was locked",
0,0,WHITE,0);
//erase sprite 0
erasesprite(buffer, balls[0]);
//update sprite 0
updatesprite(balls[0]);
//bounce sprite 0
bouncesprite(balls[0]);
//draw sprite 0
draw_sprite(buffer, ballimg[balls[0]->curframe],
balls[0]->x, balls[0]->y);
//print sprite number
textout_ex(buffer, font, "0", balls[0]->x, balls[0]->y,WHITE,0);
//display sprite position
textprintf_ex(buffer,font,0,10,WHITE,0,
"THREAD ID %d, SPRITE (%3d,%3d)",
my_thread_id, balls[0]->x, balls[0]->y);
//unlock the mutex
if (pthread_mutex_unlock(&threadsafe))
textout_ex(buffer,font,"ERROR: thread mutex unlock error",
0,0,WHITE,0);
//slow down (this thread only!)
rest(10);
}
// terminate the thread
pthread_exit(NULL);
return NULL;
}The second thread callback function, thread1, is functionally equivalent to the previous thread function. In fact, these two functions could have been combined and could have used my_thread_id to determine which sprite to update. This is something you should keep in mind if you want to add more sprites to the program to see what it can do. I separated the functions in this way to better illustrate what is happening. Just remember that many threads can share a single callback function, and that function is executed inside each thread separately.
//this thread updates sprite 1
void* thread1(void* data)
{
//get this thread id
int my_thread_id = *((int*)data);
//thread's main loop
while(!done)
{
//lock the mutex to protect variables
if (pthread_mutex_lock(&threadsafe))
textout_ex(buffer,font,"ERROR: thread mutex was locked",
0,0,WHITE,0);
//erase sprite 1
erasesprite(buffer, balls[1]);
//update sprite 1
updatesprite(balls[1]);
//bounce sprite 1
bouncesprite(balls[1]);
//draw sprite 1
draw_sprite(buffer, ballimg[balls[1]->curframe],
balls[1]->x, balls[1]->y);
//print sprite number
textout_ex(buffer, font, "1", balls[1]->x, balls[1]->y,WHITE,0);
//display sprite position
textprintf_ex(buffer,font,0,20,WHITE,0,
"THREAD ID %d, SPRITE (%3d,%3d)",
my_thread_id, balls[1]->x, balls[1]->y);
//unlock the mutex
if (pthread_mutex_unlock(&threadsafe))
textout_ex(buffer,font,"ERROR: thread mutex unlock error",
0,0,WHITE,0);
//slow down (this thread only!)
rest(20);
}
// terminate the thread
pthread_exit(NULL);
return NULL;
}The final section of code for the MultiThread program contains the main function of the program, which creates the threads and processes the main loop to update the screen. Note that I have used the mutex in the main loop as well, just to be safe. You wouldn't want the double-buffer to get hit by multiple threads at the same time, which is what would happen without the mutex being called. Of course, that doesn't stop the main loop from impacting the buffer while a thread is using it. That is a situation you would want to take into account in a real game.
//program's primary thread
int main(void)
{
int id;
pthread_t pthread0;
pthread_t pthread1;
int threadid0 = 0;
int threadid1 = 1;
//initialize
allegro_init();
set_color_depth(16);
set_gfx_mode(MODE, WIDTH, HEIGHT, 0, 0);
srand(time(NULL));
install_keyboard();
install_timer();
//create double buffer
buffer = create_bitmap(SCREEN_W,SCREEN_H);
//load ball sprite
loadsprites();
//create the thread for sprite 0
id = pthread_create(&pthread0, NULL, thread0, (void*)&threadid0);
//create the thread for sprite 1
id = pthread_create(&pthread1, NULL, thread1, (void*)&threadid1);
//main loop
while (!key[KEY_ESC])
{
//lock the mutex to protect double buffer
pthread_mutex_lock(&threadsafe);
//display title
textout_ex(buffer, font, "MultiThread Program (ESC to quit)",
0, 0, WHITE, 0);
//update the screen
acquire_screen();
blit(buffer,screen,0,0,0,0,SCREEN_W-1,SCREEN_H-1);
release_screen();
//unlock the mutex
pthread_mutex_unlock(&threadsafe);
//note there is no delay
}
//tell threads it's time
done++;
rest(100);
//kill the mutex (thread protection)
pthread_mutex_destroy(&threadsafe);
//remove objects from memory
destroy_bitmap(buffer);
//delete sprites
for (n=0; n<32; n++)
destroy_bitmap(ballimg[n]);
return 0;
allegro_exit();
}
END_OF_MAIN()This was an advanced chapter that dealt with the awe-inspiring subject of multi-threading, with a tutorial on the POSIX Threads library and Red Hat's Pthreads-Win32 project. The result was an interesting program called MultiThread that demonstrated how to use threads for sprite control. The potential for increased frame-rate performance in a game is greatly encouraged with the use of threads to delegate functionality from a single loop because this provides support for multiple-processor systems.
You can find the answers to this chapter quiz in Appendix A, “Chapter Quiz Answers.”