I am reading up on threading and concurrency issues lately. Blogging seems to be an interesting way to write down what I read and to clarify my thoughts a bit.


Prologue: Why concurrency?

We certainly love our devices to process multiple tasks at the same time. If we want to download a file, read a book and play music, we probably don’t want to do them one by one.

For practical purposes though, it is unnecessary for our computer to truly, concurrently download a file, display your book, and play music at the same time.

  • When I display a pdf for you to read, most of the time the computer sits there waiting for your next instructions, such as next page, previous page and so on. Unless you keep flipping the pages of the book and so on, the computer doesn’t have to do anything, after the first rendering of the page.
  • If I spend 50% of each second downloading a file, and the other 50% for other tasks, the file would still be downloaded.
  • To play music, I need to send a number of samples to my speaker every second. For each second, if I can produce and send the number of samples to my speaker needed in 0.01s, then I would have 0.99s for other tasks.

All the figures above are not meant to be accurate, but the idea is that if we can switch between tasks quick enough, practically speaking it would look like the computer is handling several tasks all at once. So practically the real question is then

How can we make process in multiple tasks at the same time?

1. Terminologies

When dealing with concurrency issues, there are several keywords that are used ubiquitously that were a little confusing to me at first. Let us first clarify what they mean.

Multitasking vs multiprocessing

Multitasking means you want to make progress in multiple tasks at the same time. This does not mean that at each instant, we really are executing instructions for separate tasks simultaneously – we can certainly do part of task A, switch to work on part of task B, switch to work on part of task C, come back to task A to finish it up, and so on. Our illustration earlier on downloading a file/displaying a book/playing music is one example of this.

On the other hand, Multiprocessing does mean we are trying to perform several tasks at the same time, by using multiple processors. Most computers these days have multiple-core CPUs, meaning that the CPU itself has multiple processing units/processor. If we execute different processes/tasks on each processor, we are multiprocessing.

Threads vs processes

We were already using the word process, but let us be a bit more precise now.

A process is basically an executable program loaded in the memory. Think of each process as a separate container – it has its own address space, memory, and so on. Nonetheless, processes can still talk to each other, for example by files, sockets, and so on. (Remark: processes can actually share memory, typically when one process is forked by another. As a first iteration of the picture though, this point can probably be ignored.)

Within one process though, we may still want to multi-task. Look at any multiplayer game – the computer needs to process what your character does, as well as talking to the server to see what other characters do. This leads us to threading.

A thread is an execution context ( reads: a sequence of instructions, together with the context of when/with what are these instructions executed ), that can be scheduled. A thread lives in a process, and a process can have multiple threads. All these threads will share the same resources as the process itself. Nonetheless, each threads may still maintain its own call stack to store context, local variables, and so on.

2. Multithreading

Multithreading is a way to achieve multitasking, by coordinating several threads of instructions to execute a task. In a multi-player game situation, we may have three threads in the most naive case:

  • One thread handling user input
  • One thread communicates with server to get the latest version of the whole game
  • One thread renders the latest version of the game.

Even if we have only one CPU, if we can coordinate these three threads well – so that we switch between threads at suitable time – it would look as if we handle these three tasks at the same time.

A basic model for coordinating threads is:

  • Each thread has a runnable task, and a state.
    • New: an initialized thread which is not started yet.
    • Runnable: A thread which is ready to run.
    • Running: A thread which is running/being executed right now.
    • Blocked: A thread which is waiting for completion of another thread to continue.
    • Dead: A thread is terminated, either because it has finished execution, or it gets interrupted.
  • The thread states can be modeled as below:

 

Screen Shot 2017-07-25 at 1.08.41 PM
Picture taken from Maryland CMSC 132 lectures.

Thread scheduling

An important part of this process is scheduling, which is the step of deciding which thread to run when the CPU is available.

Some concerns scheduling have to take into account include:

  • Fairness. If multiple threads are trying to run, it is possible that one thread never actually runs (sometimes called starving), because another thread gets selected each time. Fairness means we try to avoid this situation.
  • Priority. Different threads may have different priorities that we should account for.
  • Deadlines. Must a thread be executed before a certain time?
  • Throughput, i.e. the number of threads that finish running per unit time.
  • Efficiency – e.g. minimizing overhead of scheduler, context switching etc.

The two most basic categories for scheduling algorithms are

  • Non-preemptive scheduling. This means that once a thread starts to execute, it would end unless the thread finishes running and terminate/voluntarily yields the control of CPU.This can be a bad thing – if a time-intensive task is running while a higher-priority task comes up, we will not be able to stop the running thread to execute the higher-priority task first.
  • Pre-emptive scheduling. This means that the current executing thread may be interrupted.

There are many scheduling algorithms available, see here for a general introduction.

3. Some issues with multi-threading

There are some issues/tools we need to be aware of when we use multiple threads.

  • Data Race/Race conditions. Since multiple threads within a process share data, they may try to modify same data at the same time, and that could be a problem.
  • Thread signaling. If we try to split up a task among several threads, a situation like this may happen:
    • thread A does something, and pass the result to thread B.
    • thread B processes whatever it gets from thread A, and passes back to thread A.
    • thread A continues its execution.
      This means that thread B would need to signal thread A that the task is done, so that thread A wakes up and continues the process.

We will look at strategies to deal with these two issues in a future post.

 

One thought on “Multithreading I

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