Parallel programming and developing fast solutions for your slow programs using threads

Nowadays it’s common to hear about multi-core devices and how better they are because of the parallel processing power they offer, but how does it really work, and how can you develop programs that take advantage of it?

Developing parallel programs can greatly improve performance of a program, by allowing for multiple things to happen at the same time. But, sometimes, it’s also more complicated and brings a lot of problems with it, requiring some special techniques to avoid having concurrency problems.

I will be using C language with POSIX nomenclature, for a standard and low-level approach of this problem, allowing you to get a better understanding on how it really works.

The basics

To develop parallel software one must know its core fundamentals. The most important one is threads of execution. A thread is a sequence of instructions that are taken in a precise order and is independent from other threads. When you’re writing normal programs, there’s only one thread of execution. In a parallel program, there are as many as you like, thanks to the way how operative systems are developed (they are amazing, really).

An example of how threads behave

Threads allow you to explore the ability to program with a different mindset: allowing things to happen at the same time. It’s much faster to allow some operations to be realized at the same time if they aren’t connected until the end: imagine 4 blocks with slots where numbers are inserted and your objective is to sort the numbers in each block. If you were by yourself, you would start sorting each block individually, which would take a long time. But if you had 3 more friends, each one of you could sort each block individually and it’s much faster.

Although it looks very straightforward, there are many problems that come from the use of this type of programming. As the one developing a system that uses parallel programming, you must take precautions when dealing with parts of your application that are critical (for example, that share the same memory resources).

These problems come because of how threads were designed: they coexist in the same program, therefore they share the same code and heap memory. Stack memory is not shared, but may overlap in case of high usage (very unlikely to happen), because they belong to the same process and have the same memory area designated to them. If you don’t know much about memory, you should first take a look at this post. Besides sharing the whole memory, there is another, temporal, problem. The processor can, at any time, remove the thread from execution so that it can perform another task and resuming that task at a later time.

This program could be optimized so that it uses threads! Try and do it yourself

Developing your first multi-threaded program

Using threads in C language is really simple: there’s a data structure (pthread_t) that represents 1 thread to be executed by the processor, and there’s a set of functions that do operation over them. Here’s an example:

A very simple program: threads are created and destroyed.

As you can see, there are two important functions that were used: pthread_create and pthread_join. These allow the programmer to create and to wait for a thread’s result, respectively.

By running the program multiple times, we will get different results. This is one of the laws of parallel programming: the order in which threads are executed can’t be determined. One of the things that you can notice is that all the “Hello!” messages will display before the “All the threads have been successfully terminated”. This is because there is only one thread alive at that time: the thread which is executing the main function.

fn needs to return a pointer so that the compiler doesn’t return errors. The second argument in pthread_join can be used to get the return value of the function a thread has executed.

Understanding and fixing shared memory problems

One of the problems that was mentioned earlier was shared memory. This problem happens because it is impossible to know in which order the threads will be executed. Therefore, some problems that didn’t happen before will now happen.

Let’s suppose this example where there is a structure called Account, and you’re the creator of this bank. One of the rules you create is: clients cannot have negative money. Therefore, you create the following structure and function and, to improve performance, create threads to manage all the requests that your clients send you.

If two threads try to take money from the same account, will it be okay?

Without the knowledge to avoid certain situations, you will create some problems that wouldn’t happen before. After some time has passed since you placed your bank online, you notice that some people are being able to exploit your code and they can start having negative money in their account.

The problem is that, the processor can, at any timeif, remove the thread from execution to execute other tasks. This opens up a chance for a problem you didn’t want to happen.

Because there is no safety, the bank account will lose money!

As you can see, both threads will remove money from the account while only one actually could. This will make the account have negative money, something you tried really hard to avoid.

To avoid these problems from happening there are some structures that can be used. Each one offers different approaches to different problems. In this article I will talk about the mutex. The way the mutex works is, it locks a desired area for only 1 task. Any other task that tries to access the area must wait for the current task inside it to release the mutex, and then they can lock it again.

For a mutex to be good it needs to fulfill certain needs:

  • Safety — Only 1 thread at a time can hold the mutex.
  • Avoid deadlocks — If multiple threads try to lock the mutex, then at least one of them must be able to lock it.
  • Avoid starvation — If a thread tries to lock it, it will eventually get it (it will not stay infinitely waiting)

Both deadlocks and starvation are common problems when developing multi-threaded applications.

How to use the mutex

Creating a mutex is as easy as creating a thread — there is a structure and functions that do that for you. And now we can fix the previous problem:

Very simple!

Now each account has a mutex, allowing each account to be accessed individually: before accessing the said account, each thread must first lock it. Only after they will access it, making it guaranteed that there won’t be problems like before.

Now your bank is totally safe and people can’t exploit it anymore because of your extra measures to protect it!

If you still want to know more…

A mutex is one of the simplest ways to fix these problems but there are other solutions to it, like semaphores and condition variables. All that they do can be done with mutexs, but they are easier to use in certain specific problems.

Knowing how to manipulate these structures is very important so that you can create big applications which require these approaches. One of the languages that take a big advantage of multi-threading is GoLang. Check it out if you feel motivated!

Do not hesitate to contact me if you have any question about this topic as I will do my best to help you understand it! You can comment on this post and I will answer you or you can find me online in Twitter!

read original article here