Distributed Programming
Lecture 02 - Processes, Threads and
Synchronization
Edirlei Soares de Lima
<edirlei.lima@universidadeeuropeia.pt>
Programs and Processes
•
•
What is a computer program?
–
Is a sequence of instructions for performing specific tasks or solve
specific problems;
–
Static entity (an .exe file on Windows);
What is a process?
–
Is an instance of a computer program that is being executed (more
than one process can run the code of the same program);
–
Dynamic entity that changes its internal state while running the
program code;
Compilation Process
Process Model
(
(
(
a) Multiprogramming four programs (the CPU switches back and forth
from process to process).
b) Conceptual model of four independent, sequential processes (its
easier to think that the processes are running in (pseudo) parallel).
c) Only one program is active at once.
Process States
•
•
•
Running (actually using the CPU at that instant).
Ready (runnable; temporarily stopped to let another process run).
Blocked (unable to run until some external event happens).
Threads
•
Each process has an address space and a single thread of
control.
–
However, in many situations it is desirable to have multiple threads of
control in the same address space running in parallel.
•
•
Multiple threads can exist within one process, executing
concurrently and sharing resources.
Threads are faster to create and destroy than processes (10 to
1
00 times faster) and take advantage of multiple CPU cores.
Threads
Threads – Examples
•
Word Processor:
Threads – Examples
•
Web Server:
Threads in C++: Simple Example
#
#
include <iostream>
include <thread>
void ThreadFunc()
{
std::cout << "Hello Thread World!" << std::endl;
}
int main()
{
std::thread *mythread = new std::thread(ThreadFunc);
mythread->join();
free(mythread);
std::cout << "End Program!" << std::endl;
return 0;
}
Threads in C++: Race of Threads
#
#
#
include <iostream>
In this way, we don’t need
include <thread>
to indicate the namespace
include <vector>
all the time.
using namespace std;
void ThreadFunc(int threadID)
{
for (int i = 1; i < 10; i++)
{
cout << "Thread " << threadID << " - Lap " << i << endl;
this_thread::sleep_for(chrono::milliseconds(rand() % 1000));
}
cout << "Thread " << threadID << " Arrived! " << endl;
}
...
Threads in C++: Race of Threads
...
int main()
{
srand(time(NULL));
vector<thread> *allthreads = new vector<thread>();
for (int i = 0; i < 5; i++)
{
allthreads->push_back(thread(ThreadFunc, i));
}
for (int i = 0; i < 5; i++)
{
allthreads->at(i).join();
}
free(allthreads);
cout << "End Program!" << endl;
return 0;
}
Threads in C++: Race of Threads
•
What is wrong with the results?
–
Threads are printing their messages at the same time!
–
This problem is know as “Race Condition”. It occurs when two or more
processes are reading or writing some shared data (in this case, the
console).
Race Conditions
•
How do we avoid race conditions?
–
The key to preventing problems like this is to find some way to prohibit
more than one process from reading and writing the shared data at
the same time.
•
•
We need a way of making sure that if one process is using a
shared variable or file, the other processes will be excluded
from doing the same thing.
The part of the program where the shared data is accessed is
called the critical region or critical section.
Race Conditions
•
Naive solution: Lock Variables
–
Consider having a single, shared (lock) variable, initially 0. When a
process wants to enter its critical region, it first tests the lock. If the
lock is 0, the process sets it to 1 and enters the critical region. If the
lock is already 1, the process just waits until it becomes 0.
int lock = 0;
void ThreadFunc(int threadID){
for (int i = 1; i < 10; i++){
bool lap = false;
while (lap == false){
if (lock == 0){
lock = 1;
cout << "Thread " << threadID << " - Lap " << i << endl;
lock = 0;
lap = true;
}
}
...
Race Conditions – Naive Solution
•
It solves the problem?
–
It reduces the chances, but don’t solve completely the problem…
Why?
–
The race condition now occurs if the second process modifies the lock
just after the first process has finished the lock check.
Race Conditions – Mutual Exclusion
•
Solution: Mutex
.
#
.
..
include <mutex>
..
mutex mymutex;
void ThreadFunc(int threadID){
for (int i = 1; i < 10; i++){
mymutex.lock();
cout << "Thread " << threadID << " - Lap " << i << endl;
mymutex.unlock();
this_thread::sleep_for(chrono::milliseconds(rand() % 100));
}
mymutex.lock();
cout << "Thread " << threadID << " Arrived! " << endl;
mymutex.unlock();
}
Race Conditions – Mutual Exclusion
•
Mutex solves the problem:
–
What happens to the other threads while one is inside the critical region?
• Busy-waiting! (wasting a lot of CPU time).
Exercise 1
1
) Implement a program in C++ to sum the values of each row
of a 5x5 matrix and display the results on screen.
–
The sum must be computed in parallel using threads. Each thread
must be responsible for computing the sum of a single row.
–
The matrix can be statically declared. Example of 3x3 matrix:
int mymatrix[3][3] = {{10,20,30},{40,50,60},{70,80,90}};
Exercise 2
2
) Implement a program in C++ to multiply the values of an
array (with 1000 int values) by a scalar and display the
resulting array on screen.
–
The multiplication process must be done in parallel using 10 thread,
where each thread must be responsible for multiplying 100 elements
of the array by the scalar.
–
The results of the multiplications must be stored in another array.
Threads in C++: Example 2
•
Supposing that x * x is a very costly operation (it's not, but use
your imagination). Can we parallelize the calculation of the
sum of squares up to a certain number?
Threads in C++: Example 2
int cont = 0;
void square(int x)
{
cont += x * x;
}
int main()
{
vector<thread> *allthreads = new vector<thread>();
for (int i = 1; i <= 20; i++){
allthreads->push_back(thread(square, i));
}
for (int i = 1; i <= 20; i++){
allthreads->at(i - 1).join();
}
free(allthreads);
cout << "Count = " << cont << endl;
return 0;
}
Threads in C++: Example 2
•
If you run the program, chances are it outputs 2870 (which is
the correct answer). But after few executions, you probably
will see some wrong results:
–
If you never see a wrong result, your computer is running the thread
code too fast. You can “solve” this by adding a sleep time to the thread
code: this_thread::sleep_for(chrono::microseconds(1));
Threads in C++: Example 2
•
•
This is caused by another race condition. Why it happens?
Example:
// Thread 1
// Thread 2
int temp1 = cont;
// temp1 = 0
// temp2 = 0
// temp2 = 4
// temp1 = 1
// cont = 1
// cont = 4
int temp2 = cont;
temp2 += 2 * 2;
temp1 += 1 * 1;
cont = temp1;
cont = temp2;
–
We end up with cont as 4, instead of the correct 5.
Threads in C++: Example 2
•
We can also solve this problem using mutex:
.
#
.
..
include <mutex>
..
mutex mymutex;
void square(int x)
{
mymutex.lock();
cont += x * x;
mymutex.unlock();
}
Threads in C++: Example 2
•
C++ offers an even nicer abstraction to this problem: atomic
–
The main characteristic of atomic objects is that access to this
contained value from different threads cannot cause race conditions.
.
#
.
..
include <atomic>
..
atomic<int> cont(0);
void square(int x)
{
cont += x * x;
}
Threads in C++: Example 2
•
C++ provides an even higher level of abstraction that avoids
the concept of threads altogether and uses tasks instead.
Simple example:
#
#
include <iostream>
The async construct uses an object pair called a
include <future>
promise and a future: the future is linked to the
promise and can at any time try to retrieve the
value (get()). If the promise hasn't been fulfilled
yet, it will simply wait until the value is ready.
using namespace std;
int square(int x){
return x * x;
}
int main(){
future<int> mytask = async(launch::async, square, 10);
int value = mytask.get();
cout << "The thread returned " << value << endl;
return 0;
}
Threads in C++: Example 2
•
We can solve the sum of squares problem using tasks:
#include <iostream>
#include <vector>
#include <future>
using namespace std;
int square(int x)
{
return x * x;
}
...
Threads in C++: Example 2
int main()
{
vector<future<int>> *alltasks = new vector<future<int>>();
for (int i = 1; i <= 20; i++)
{
alltasks->push_back(async(launch::async, square, i));
}
int cont = 0;
for (int i = 1; i <= 20; i++)
{
cont += alltasks->at(i - 1).get();
}
free(alltasks);
cout << "Count = " << cont << endl;
return 0;
}
Condition Variables
•
•
Sometimes, its useful to be able to have one thread wait for
another thread to finish processing something before doing
its task.
–
To do that, we need a way to send signals between threads.
Naive solution:
–
Use a global boolean variable that is set to true when we want to send
the signal. The other thread would then run a loop that checks if
variable is true and stops looping when that happens.
–
Problem: the receiving thread will be running a loop at full speed
(wasting a lot of CPU time).
Condition Variables: Naive Solution
#
#
include <iostream>
include <thread>
using namespace std;
int producedData = 0;
bool notified = false;
void Assigner()
{
this_thread::sleep_for(chrono::seconds(2));
producedData = 42;
notified = true;
}
void Reporter()
{
while (!notified) { /*do nothing */ }
cout << "Data: " << producedData << endl;
}
Condition Variables: Naive Solution
int main()
{
thread assigner(Assigner);
thread reporter(Reporter);
assigner.join();
reporter.join();
return 0;
}
–
–
It works, but the while loop in the reporter thread will be running a
loop at full speed (wasting a lot of CPU time).
Better solution: C++ condition variables
C++ Condition Variables
#
#
#
#
include <iostream>
include <thread>
include <condition_variable>
include <mutex>
using namespace std;
condition_variable mycondvar;
mutex mymutex;
int producedData = 0;
void Assigner()
{
this_thread::sleep_for(chrono::seconds(2));
producedData = 42;
mycondvar.notify_one();
}
...
C++ Condition Variables
...
void Reporter()
{
unique_lock<mutex> lock(mymutex);
mycondvar.wait(lock);
cout << "Data: " << producedData << endl;
}
int main()
{
thread assigner(Assigner);
thread reporter(Reporter);
assigner.join();
reporter.join();
return 0;
}
Producer-Consumer Problem
•
Game Scenario:
–
Two independent NPCs share a common container of resources (e.g.
food, ammo, etc.) with a limited capacity.
–
–
–
–
The producer task is to gather resources and put it in the container.
The consumer task it to remove resources from the container.
Both can only handle one piece of resource at a time.
The problem is to ensure that the producer never tries to put
resources in when the container is full and the consumer never tries to
remove resources from the container when it is empty.
Producer-Consumer Problem
Producer-Consumer Problem
•
Examples of Applications:
–
Factory scenario:
•
Robots hang parts coming from a production line on a rack.
•
Robot operators pick one part at a time from the rack to assemble the
final product.
–
Web service:
•
The web service receives http requests for data, places the request into an
internal queue.
•
Worker thread pulls the work item from the queue and performs the
work.
Producer-Consumer: Deadlock Problem
PRODUCER:
CONSUMER:
1
2
3
4
5
. if buffer is full
. go to sleep
1. if buffer is empty
2. go to sleep
2
1
3
. put new item in buffer 3. remove item from buffer
. if buffer has 1 item
. wake consumer
4. if buffer has free slots
5. wake producer
DEADLOCK!
Producer-Consumer: Base Code
#include <iostream>
#include <thread>
#include <queue>
using namespace std;
queue<int> resources;
int totalConsumed = 0;
int totalProduced = 0;
bool producionDone = false;
void Producer()
{
for (int i = 0; i < 500; i++)
{
resources.push(i);
totalProduced++;
}
producionDone = true;
}
Producer-Consumer: Base Code
void Consumer(){
while (!producionDone){
while (!resources.empty()){
resources.pop();
totalConsumed++;
}
}
}
int main(){
thread producer(Producer);
thread consumer(Consumer);
producer.join();
consumer.join();
cout << "Total Produced: " << totalProduced << endl;
cout << "Total Consumed: " << totalConsumed << endl;
cout << "Total Container: " << resources.size() << endl;
return 0;
}
Producer-Consumer Problem
•
Problem:
–
What is wrong with the code?
Exercise 3
3
) Correct the problems in the implementation of Producer-
Consumer using condition variables and mutexes.
–
Ensure that the producer never tries to put resources in when the
container is full (define a constant to represent the capacity of the
container).
–
A simple mutex can solve the problem, but is not the best solution
(busy waiting problem). Use condition variables to synchronize the
threads.
Further Reading
•
Tanenbaum, A. S., Bos, H., (2014). Modern Operating Systems (4th
edition), Pearson. ISBN: 978-0133591620.
–
Chapter 2: Processes and Threads