Parallel Programming - CPP

Parallel Programming?

Parallel programming is when the program executes multiple tasks at the same time. In this case, exists three main aspects:

1. Efficiency?
2. Synchronization
3. Communication

THREAD

Threads are a subset of a process with an independent path of execution. The OS schedules threads for execution.

Thread Lifecycle

Efficiency?

To increase efficiency the idea is the program or data in groups that can be executed independently. One common strategy used is divide-and-conquer, as seen in state machines.?

Synchronism?

In the real world, not all activities can be executed full-independently, which creates the problem of synchronism between activities. When we have a set of operations that must be executed without interruption this is named a critical region or section.?

To solve those problems we have a set of strategies. Here we will focus on Mutex and Semaphore.?

Mutual Exclusion - Mutex

Mutex is used to protect critical sections, these states make use of lock and unlock tasks. For example the relay race. The previous task(Back runner) will lock the next task(front runner) from the start of the activity, only when the back runner passes the baton(Unlock) the front runner can start the task.??

Mutex is part of C++ Standard since C++17.

CODE IMPLEMENTATION

SEMAPHORE

A semaphore is a synchronization mechanism to control access to shared resources. Unlike mutex, can be applied by multiple threads at the same time. But must include a track to count how many times it has been acquired or released.

Acquire()

• If the counter is positive, decrement counter
• If the counter is zero, wait until available

Release()

• Increment counter
• Signal waiting thread

CODE IMPLEMENTATION

PROBLEMS

Parallel programming is a very delicate way of development. If you write a code without precautions you can deal with some problems:

1. Deadlock
2. Starvation
3. Race condition

DEADLOCK

This problem occurs when two or more task waits for the resource that the other is holding or if a thread tries to lock a mutex that is already locked it will enter into a waiting list for that mutex which results in something called deadlock.

STARVATION

Occurs when a thread is unable to gain access to a necessary resource. A process or a thread is perpetually denied the resources it needs.

DATA RACE

Can occur when two or more different threads concurrently access the same memory location. To prevent you need to ensure mutual exclusion for the shared resource.

RACE CONDITION

Is a flaw in the timing or order of a program's execution that causes incorrect behaviour.

SOLUTIONS

The solution for those problems is based on protecting the critical section of the code. Two possible solutions have already been mentioned, mutex and semaphore. Now we will explore some other synchronization solutions.

Conditional Variables

Queue or container of threads waiting for a certain condition. Associated with a mutex, implement a higher level construct called monitor.

The monitor can implement three operations:

1. wait(): Automatically release the lock on the mutex. Go to sleep and wait for the queue. Re-acquire the lock when woken up.
2. signal(): Wake up one thread from the conditional variable queue. Also called notify all or wake all.
3. Broadcast(): Wake up all threads from condition variable queue. Also called notify all or wake all.

Barrier

Prevents a stopping point for a group of threads from proceeding until enough threads have reached the barrier.

Final considerations:

I hope you enjoy this article, if you want to know more about those topics in the end of the article you can find some good references.

In case of doubts, let me know if i can help!

May the force be with you my friend!

REFERENCES

https://devopedia.org/deadlock

https://darkdrag0nite.medium.com/race-condition