Intro to Multithreading

Beginner’s Guide

Ayush Ranjan
Dec 30, 2017 · 10 min read

Welcome to my first blog here! Yeah I am as excited to write this as you are to read. ;D Well I am a sophomore studying Computer Science and Mathematics at the University of Illinois — Urbana Champaign. Good to meet you!

This was my third semester of college and everyone was so pumped as the career fairs were approaching. (Getting internship offers is a big deal right?) There were a series of career fairs and I ended up applying to more than 60 companies. :O (Yeah, I overdid it) I thought I was under-qualified and was hoping some company would be interested in me. Turns out I underestimated myself! I got interview offers from 22 different companies! I was so excited I interviewed with all of them and ended up giving around 40 interviews (phone call, screen share and on-site combined).

How did I prepare? Worked a lot on algorithms and data structures through Hackerrank and Cracking the Coding Interview. All of those interviews went well… till the point they asked me questions on topics I knew. After you crack the initial interview rounds, you are bombarded with questions from more advanced topics like Multi-Threading and Networking. Around 40% of my interviewers asked me something on multi-threading and I would be like “I am yet to study these topics.” (Yeah, it was embarrassing ;D)

I went home, intrigued about what all this was all about. Multi-Threading seemed like a buzz word to me. It surely was in demand and had importance in real world. But what was it? How should I learn it? Where do I start? This blog documents my own journey of learning the basics of Multi-Threading. Hope this helps you get started too! Lets begin by answering the three fundamental questions… What, Why, How.


What is multi-threading?

A thread is an execution context, which is all the information a CPU needs to execute a stream of instructions.

That is my favourite definition from Stack Overflow. A thread basically runs an independent set of instructions to perform a certain job. Intuitively, the thread dies out (terminates) when the program it executes terminates. You have control over what instructions the thread would run, when to start, pause, continue or kill its execution and what priority the thread holds relative to others. Isn’t that simple? A thread ain’t a buzz word anymore. :)

While solving real world problems, we come across various occasions where we want to run multiple jobs concurrently (discussed in the next section). So we create multiple threads, define them with different jobs to perform and run them together. That is all we need to do. Rest of what happens in the background is abstracted away from you. It is the job of the CPU to jump between executing threads, allocate resources to each, decide when to switch and which thread to switch to based on priority.

This is exactly what multi-threading is, the ability of a CPU to run multiple threads at the same time. Wiki says:

In computer architecture, multithreading is the ability of a central processing unit (CPU) or a single core in a multi-core processor to execute multiple processes or threads concurrently, appropriately supported by the operating system.

That being said, lets answer the infamous interview question: What is the difference between a thread and a process? If you are giving a tech interview, you are most likely to come across this question. We know what a thread is. A process is broader than a thread in its definition.

It is an instance of a program currently being executed and depending on the OS, it might be comprised of multiple threads running concurrently (shown in the image). The fundamental difference is that threads contained within a process share the same memory space while different processes have completely separate memory spaces. This is what makes threads lighter in comparison to a processes. Therefore, a thread can also be defined as a subset of a process.

Some other differences can be highlighted too. Threads within the same process can communicate with one another very easily while processes have to use more complex mechanisms. Easy thread communication is what helps us implement thread synchronisation efficiently. (discussed in later section) Having easy communication, threads within the same process can exercise considerable control over others while processes can only control child-processes. This is what makes threads dependent and processes independent in terms of memory and control. Since threads are light-weight, their creation is also much faster than that of a process. There surely are more differences but we will not be covering them in this post. Hope that gave you some insight into what multi-threading is and introduced the basic terminology used!


Why do we need Multi-Threading?

  1. So that a computer can multi-task! Any OS needs to perform so many different tasks at the same time. On Snapchat, when you snap a huge video to someone, you can still keep going through stories while that snap is being sent in the background. Computers have to multi-task all the time so that the user doesn’t have to wait until a task is completed.
  2. So that the CPU can utilise multiple cores and improve performance. Its hard to find a laptop today which runs on a single processor. This enables the CPU to solve a problem which can be divided into sub-problems (running on different threads) that can be solved independently on different processors (parallelisation) and hence boost performance.

However, a single processor cannot execute two instructions in parallel at any given moment. It can alternate between threads but we will need more cores for executing multiple instructions at the exact same time. Even in a hyper-threaded system (where one core acts like two virtual (logical) cores), one physical core will only be executing the instruction of one of the cores it represents at any given moment.

Hence, we can infer from above that the technique of multi-threading and multi-processing improves performance only if there are multiple cores.


How to code it?

I am going to walk you through some basics of multi-threading in JAVA (since its one of the most commonly used languages and I personally find it a good starting point). The good news is that you don’t have to worry about how and when to switch between threads and to allocate them efficiently to the hardware available. What we have to do is, given a problem identify how we can break it into sub-problems which are mutually independent and then deploy each of those tasks on separate threads.

In JAVA, you can create threads in two ways:

  1. Construct a thread object by passing an object that extends Runnable interface as a parameter in the constructor. Thread thread = new Thread(someRunnableObject). To implement Runnable interface you will need to override the run() method.
  2. Make an object extend Thread class and override the run() method.
class WannaBeThread extends Thread {    @Override
public void run() {
// add code to perform what ever task
}
}

To start running the thread you just need to do thread.start() . Pretty easy right? To demonstrate how threads are being executed simultaneously and not sequentially, I have written this simple program. Before running it, look through the code. It creates two threads which just print their own ID few number of times. These two threads are run one after the other. If the CPU was not multi-tasking, it would complete running the first thread and only then start executing the second. This is not quite what will happen!

To run it, copy it into a file named SimpleThreadDemo.java, cd into the directory where that file exists, compile it with javac SimpleThreadDemo.java and run it with java SimpleThreadDemo. Now check the output. You should be noticing the the thread IDs being printed alternate in irregular intervals. This effectively shows that the two threads are being executed concurrently. You can to tweak the parameters NUM_PRINT and NUM_THREADS and play around.

Issues with multi-threading

There are many possible issues that arise from concurrency. Some are:

  1. Visibility Issues: When some data is changed but another thread reading that data concurrently is unaware of the change.
  2. Access Issues: When multiple threads access and change the same shared data. (Example shown below)

These issues can lead to liveness failure (the program stops reacting, eg. dead locks) and safety failures (incorrect data is produced, eg. race conditions). In this post I will only be covering one of these issues in detail and how we can avoid it because I feel its really important .

In the previous example, the tasks performed by the two threads were completely independent. But what happens when two threads are dependent in terms of modifying the same object? That leads to one of the most common problems in multi-threading, race conditions.

A race condition occurs when two or more threads can access shared data and they try to change it at the same time.

The thread scheduling algorithm can switch between threads at anytime. It can switch while executing a statement that has not completed completely also. Lets take an example of a simple object which just holds an integer and we have two different threads incrementing the same object. The statement adderObject.val += inc; is executed in three atomic instructions: read val, increment it, write it back to object. The thread scheduler will not wait for all three instructions to complete and might just switch threads when the value is only read or incremented but not written back. Bad things can happen here…

For example, think of thread A and B incrementing adder object.

// adder.val = 10
A reads val as 10
A increments val (in temporary variable) by 1
// threads switch
B reads val as 10
B increments val (in temporary variable) by 1
B writes back to val. val now holds 11.
// threads switch
A writes back to val. val now holds 11.

After both threads increment the adder, it finally only holds 11 when its supposed to hold 12. Don’t believe me? See for yourself! I have written this program which demonstrates this issue. Look through the code but don’t worry if you don’t understand it completely, we will come to it. Just follow the code on how it will be executed with all the boolean parameters on top of the file being false.

We just create one Adder object, initiate two threads with the same object and run the threads together. Each thread adds 0, 1, …, LIMIT to the adder. After both the threads terminate we calculate the correct value that the adder should contain and check the difference which represents error here. Try it yourself! Same as before use javac Synchronisation.java and java Synchronisation to run the file.

NOTE : SYNCHRONIZE = false and THREAD_ID_OUTPUT = true does not give the expected output! Because System.out.println() is a heavy IO operation, it automatically synchronises the two threads outputting.

Run it a couple of times, you will be astonished by the magnitude of errors! Try playing around with the LIMIT. But how do we solve this issue?

Synchronisation

Now lets look at a slightly more advanced yet extremely important topic which helps us avoid race conditions. Getting a hang of synchronisation is imperative to write ‘thread-safe’ applications. In the above example, we would want both the threads to be cognisant of all previous modifications made to the adder and we would want only one thread to be incrementing adder at a time. This is exactly what the synchronized keyword does in JAVA.

You can protect code with synchronisation in two ways:

  1. Synchronized method: You can define a function with the keyword like: public synchronized void foo(...). This ensures that only one thread can enter this method at a time and other threads wanting to use this function will have to wait until the first thread leaves it.
  2. Synchronized block: You can use this if you only want to protect a block of code. This block has to be ‘locked’ or guarded by any object called the lock. All the blocks protected by the same object will only be executed by one thread at a time. The syntax is: synchronized (object) { /* code */ }.

Now go to Synchronisation.java and change SYNCHRONIZE_ADDER = true and see how the program flow will change. You should be noticing that the signature of add method now being executed includes the synchronized keyword. This ensures that while one thread is incrementing the adder, the other cannot interrupt it mid-execution (like shown above) and produce a race condition. The threads can not switch until all the atomic operations pertaining to val += inc; are completed. And hence we successfully avoid any race conditions! Run the file to see the error to be zero! You can set THREAD_ID_OUTPUT = true; to see how the threads switch.

You could alternatively solve this problem by calling the method addSumToLimit within a synchronised block and locking it with the adder object so that only one thread can be calling that method on an adder. I have included that in my code. Set SYNCHRONIZE_ADDER = false and SYNCHRONIZE_CALL_TO_METHOD = true and see how the flow changes. This would ensure that only one thread calls addSumToLimit at a given time and the other will have to wait for the entire method to execute completely. However, this would mean that there are no race conditions but the threads are not essentially alternating. Verify this using THREAD_ID_OUTPUT = true. This is not different from normal sequential programming you see.

Therefore, such decisions on when, what and how to synchronise can be critical. You should try to synchronise the very root of the race condition. For example in the above demonstration, two increments to the same adder by two different threads was acceptable irrespective of their order. We just had to ensure they don’t cut each other out mid-execution and hence we just had to synchronise the increment function not the entire addSumToLimit function.


This brings us to the end of this blog! Hope you enjoyed reading it and I wish you gained something from this. To learn more about me visit my website! Feel free to leave comments and suggestions below! See you next time! :)

Ayush Ranjan

Written by

Computer Science enthusiast. Into software development and data science. Love learning new things and appreciate new ideas. Learn more about me at ayushr.com !

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade