Multithreading: meaning and motivation

It is common for the casual programmer to assume that multithreaded is the same as multiprocessor/multicore.  This is not the case, and in this post I hope to clear that up.  One can not talk about multithreading without first defining threads, and before knowing what a thread is you should probably know the proper definition of the word process and how it relates to programs and threads.  Therefore, this post will attempt to explain exactly what one means by the terms thread, multithread, process and program.

What is a process?
A process is an instance of a program running on your computer.  You can think of programs as the code compiled into binary and stored somewhere on your system.  Programs are the blueprint that gives the CPU all instructions necessary to carry out a task.

A process, on the other hand, is the actual instance of that program as it runs on the system.  For example, you have a program called chrome.exe which is the blueprint for how to show web pages, and when you execute that program a process is born.  On a modern operating system, you can have multiple instances of chrome.exe running at the same time.  Each one of these instances are processes.

A process has a memory address space, a process ID, and some state such as the program counter which tells the CPU which instruction of the program this process should execute next, and the stack pointer.

What is a thread?
A thread is in some sense a light weight process.

To motivate the desire to have threads in addition to processes, consider the following scenario.  You are writing a mail server program which takes requests from users, finds their mail box in a file system, then returns some html formatted page displaying their mail box contents.  Naively writing such a program would likely not be able to handle many clients, as each time one user queries the mail server, it cannot accept any requests while the program is searching the disk for that user's mail.

One might think, "no problem, you already said that one program can have any number of processes carrying out its instructions at a given time.  I'll just spawn 10 processes of the mail server at once, and now we can handle 10 simultaneous users".  If you thought that, you'd be on the right track, but there is a serious waste of resources going on here.  Your 10 processes each contain a large chunk of memory (the heap) which is storing the exact same information (the program code).  There is also an issue with inter-process communication.  These ten processes have no way (well, not entirely, but no efficient way) of coordinating efforts because they do not share any memory.  The last point is that switching between programs is quite an expensive operation.  All state has to be stored somewhere and then stored state of the other program must be loaded into memory.  The cost of doing this increases with the amount of state that needs to be stored and loaded.

Threads help mitigate this problem because one single process has a memory address space, and then threads share this memory.  In addition, each thread gets its own stack of memory to keep local variables that can only be used by that particular thread.  Now the program instructions are only stored in memory one time, and each thread keeps a program counter in its own stack to know which part of the program it is supposed to execute next.  Switching between two threads owned by the same process is much faster because state is shared and so requires less loading and storing.

Two threads, one processor
You may have noticed that this entire conversation has not mentioned the existence of multiple processors at all.  This is on purpose, to make clear that multiple threads can still provide speed up on a single processor under certain conditions.

To see why, consider the way in which your old single core computer was able to run more than one program at a time.  It isn't doing anything magic, it's simply giving you the illusion that you are executing all of these processes simultaneously.  What is really happening is that the CPU is very rapidly switching between processes, executing portions of each to give you the feeling that things are happening all at the same time.  Switching between one process and another is called context switching.  The context is the current state of your process, i.e. the memory contents, the program counter, etc.  All of this stuff gets stored, and then another process's state is loaded into the machine registers and is allowed to take over for a few milliseconds.

A single processor machine can benefit from multithreaded programs because some processes are IO bound:  they can not make progress at some points due to waiting on input/output operations such as hard drive reading and writing, network communication, or user inputs.  This was the case for our mail server program.  In these situations, rather than simply wait for its time slice with the processor to expire, it makes sense for this process to give up the rest of its slice to some other process which can make progress.

Now consider how we might speed up that mail server program, armed with our vast knowledge of threads.  If we have two threads, then we can have two program counters for the same process, and thus we can take different paths through the same program for different users.  For example, Ling opens her inbox and Ying immediately follows.  If we have two threads, the one that responds to Ling can run until it sends a request to disk and has to wait.  During the waiting time, Ling's thread can give up the processor and context switch to Ying's thread which can use the CPU while Ling is waiting for the disk request to return.

Multiple Cores
The benefits of multiple threads should be quite obvious when you have multiple processor cores.  In this situation, with single threaded programs only one core can be used at a time, wasting 75% of your throughput on a quad core machine.  Thus, multiple cores can help not only in IO bound applications but CPU bound applications as well.  CPU bound applications are ones that don't spend a lot of time waiting for IO, but require a lot of CPU time.  With these applications, you can use multiple threads to utilize the other cores of your processor to process work in parallel.

With great power comes great responsibility
What I've just talked about is powerful information.  Moore's law is not really true anymore, as processor speeds have not increased much in recent years, but the number of processing units has increased dramatically.  To make use of these extra processors, we need to be able to write multithreaded programs.

However, this is not a simple task at all, so before you go out and blindly start splitting up your processing tasks into multiple threads, be sure to read up on synchronization, and learn it well.  In a later post, I'll talk about the funny things that can  happen when you ignore synchronization in a multithreaded program.

printf("Hello,World!");

#include <stdio.h>

int main(int argc, char ** argv){
  printf("Hello,World!");
  return 0;
}

Welcome to my blog. The main focus of this blog is computer science topics, mostly focused around synchronization and consensus algorithms and code, but will probably also diverge from that topic quite a bit as I'm sort of a scatter-brain.

I'm writing this mostly as a notepad to help express the things I'm learning in a coherent manner. I find that writing about things helps me actually understand them better, and I thought it would be kind of neat if others could also use this as food for thought. There are quite a few developers out there who could use some extra practice and study in synchronization techniques, but do not know to what extent they need this information, so hopefully some of those people will stumble upon this blog and find it useful.

The other purpose of this is to store information and examples that I find important, because I am incredibly forgetful, and while Github's Gists are really neat, this is a slightly richer medium in which I can also summarize key aspects and ideas around the code, rather than just a bunch of code.

If anyone other than myself ever actually reads this, I hope you find it useful and would be extremely appreciative of any feedback on the code samples, thought experiments, and explanations. Improvements can almost always be made.