Lecture 06: Concurrency

CE216: Fundamental Topics in Programming

Asst. Prof. Dr. M. Çağkan Uludağlı
Prepared by: Assoc. Prof. Dr. Kaya Oğuz
Operating Systems and An Illusion

● What is a process?
● A process is a program in execution.
● Here is “Notepad.exe” sitting on the
disk.
● But three notepad processes are
currently running on the system,
alongside others.
● How can they all run at the same
time?
Operating Systems and An Illusion
● Operating systems were multitasking long before multiple processors.
● Even with a single processor, it is possible to have multiple processes running
on the OS.
● This is done by running all of them a very short time (called a quantum time),
and switching between them very quickly.
● When you start a process, it gets in a “queue” - and the OS takes care of who
should run next.
● The switching is referred as “context switching” - the operating system
stores all the information about the current process, loads the other process,
and runs it for a while. OS repeats this so fast, it feels like they are running at
the same time!
Processes
● Processes are handled by the operating system (as I’ve said so many times
so far, but for good reason) and each process uses the computer resources in
their own quantum time.
● Each process has its own memory space, too.
○ Without going into much detail, this memory is provided as a virtual memory.
○ Basically, the OS allocates some part of the memory to the process and remaps the memory
blocks so that each has its own location 0, for example.
● Processes are clearly separated, but a time comes when two processes have
to talk to each other.
● This is called “interprocess communication (IPC)”
● They do so by a shared space; either a place in memory or a file.
Processes

● While it is the operating system’s job to manage the CPU assignment if there
are multiple CPUs or cores, some libraries give us the control; so that we can
divide a task between several CPUs.
○ When there are one million records to process, the OS cannot actually make intelligent
assumptions about how you would like to distribute the workload among the CPUs.
● We can create a process by running the executable.
● C has “fork” and “wait” functions which forks the current process into two
processes.
● Let us see the C code first.
C
1. #include <stdio.h>
2. #include <unistd.h>
3.
4. int main(int argc, char** argv) {
5. printf("This is our C program!\n");
6. printf("I'll fork this, but let me create some variables first.\n");
7. int a = 12;
8. int b = 13;
9.
10. printf("Calling fork!");
11. pid_t pid = fork();
12. if(pid == 0) {
13. printf("This is the child process! pid is %d\n", pid);
14. a = 22;
15. printf("Value of a in child: %d\n", a);
16. } else {
17. sleep(1);
18. printf("This is the parent process! pid is %d\n", pid);
19. a = 42;
20. printf("Value of a child in %d\n", a);
21. }
22. printf("This line will print in both parent and child: %d\n", a);
23. return 0;
24. }
C

1. #include <stdio.h>
2. #include <unistd.h>
3.
4. int main(int argc, char** argv) {
5. printf("This is our C program!\n");
6. printf("I'll fork this, but let me create some variables first.\n");
7. int a = 12;
8. int b = 13;
9.
10. printf("Calling fork!\n");
11. pid_t pid = fork();
12. if(pid == 0) {
13. printf("This is the child process! pid is %d\n", pid);
14. a = 22;
15. printf("Value of a in child: %d\n", a);
16. } else {
17. sleep(1);
18. printf("This is the parent process! pid is %d\n", pid);
19. a = 42;
20. printf("Value of a child in %d\n", a);
21. }
22. printf("This line will print in both parent and child: %d\n", a);
23. return 0;
24. }
Processes

● Notice that, a new memory space has been created for the forked process.
● Processes are called to be “heavyweights” - starting a process is costly
because you register it with the operating system, allocate CPU cycles and
memory spaces, etc.
● Additionally, it is very challenging to make them work on a single task.
● The reason we have multiple processes is to get each process work on part of a task.
● This requires a lot of setup just to get the processes read and write to memory or disk.
● So, we have threads.
Threads

● Threads are lightweight “processes.”

● Actually, they are not processes, they are workers inside a process.
Threads

● Threads are lightweight “processes.”

● Actually, they are not processes, they are workers inside a process.
● Since they are within a process,
○ they are not governed by the operating system,
■ so, they require their own libraries
○ they do not have their own memory space, but they share memory with other threads,
■ good for communication, but challenging
○ costs much less to create them when compared to processes.
Threads

● Threads are very commonly used.

● They are very easy to use, but they require some extra care because there is
no guarantee when and in what order they will run, like processes.
● When do we use them?
○ to divide up a large task into more manageable pieces,
○ for background tasks, such as writing a large file to disk, downloading resources, checking for
changes,
● Some of these are very common in web applications.
● The browser fetches all resources on separate threads, so that you can keep
scrolling the web page while it is still downloading some images.
● Some web requests run “asynchronously” and your code has to “wait.”
Threads

● All programming languages have their own thread implementations.

● In C and C++, we use “pthreads”.
● In Python, there is a “threading” library.
● In Java, we have a Thread class, and a Runnable interface.
● Check documentation for your programming language. The principles remain
the same.
● Let’s discuss Java.
Threads

● To create and run a thread in Java, we can

○ either extend the Thread class,
○ or implement the Runnable interface.
● Since Java supports single inheritance, we usually stick to Runnable
interface, but we can use either, there is no difference.
● Even if you don’t use threads, there is a “main thread” - which starts with the
main method.
● Let’s see some code.
MyThread.java
1. public class MyThread extends Thread {
2. private String tname;
3.
4. public MyThread(String n) {
5. tname = n;
6. }
7.
8. @Override
9. public void run(){
10. for(int i=0;i<100;i++) {
11. System.out.println(tname + " is counting : " + i);
12. }
13. }
14.}
Main
1. public class App {
2. public static void main(String[] args) throws Exception {
3. System.out.println("Hello, World!");
4. MyThread m1 = new MyThread("Thread 1");
5. MyThread m2 = new MyThread("Thread 2");
6.
7. m1.start();
8. m2.start();
9. }
10.}
Output

● For the first example, I have extended the Thread class and overwritten
public void run().
● I used a String variable to give the thread a name.
● In the main, I’ve created two MyThread objects, m1 and m2.
● I start m1, then m2.
● Notice that I do not call run(), but start().
● What will the output be?
 Hello, World!
Thread 1 is counting :0
Thread 1 is counting :1
Thread 1 is counting :2

Output Thread 1 is counting

Thread 1 is counting
Thread 1 is counting
:3
:4
:5
Thread 2 is counting :0
Thread 2 is counting :1
Thread 2 is counting :2

● The code for m2 will also run in parallel! Thread 1 is counting

Thread 2 is counting
Thread 1 is counting
:6
:3
:7

● As soon as the line m1.start() is evaluated, the execution of the Thread 1 is counting
Thread 1 is counting
:8
:9
Thread 2 is counting :4

main thread continues to next line without waiting for m1.start() to Thread 1 is counting
Thread 2 is counting
: 10
:5
Thread 2 is counting :6
finish. Thread 2 is counting
Thread 1 is counting
:7
: 11

● This is because a new “thread” is started, and the job for that line
Thread 1 is counting : 12
Thread 1 is counting : 13
Thread 2 is counting :8
Thread 2 is counting :9
is complete. Its job was to set up the thread and let it run. Thread 2 is counting
Thread 2 is counting
: 10
: 11

● So, here’s the output - this will be different every time I run it Thread 2 is counting
Thread 2 is counting
: 12
: 13
Thread 1 is counting : 14

because we are not in control of the order of execution. This is Thread 2 is counting
Thread 2 is counting
: 14
: 15
Thread 2 is counting : 16
very important. Thread 2 is counting
Thread 2 is counting
: 17
: 18
Thread 2 is counting : 19
Thread 2 is counting : 20
Thread 2 is counting : 21
Thread 2 is counting : 22
Thread 2 is counting : 23
Thread 1 is counting : 15
Runnable

● How about Runnable interface?

● Actually, we use Runnable much more often, because it is likely that the class will have other
super classes.
● The class does not have much difference, but we still need thread objects to
run the objects with a runnable interface.
● Here’s the code:
Runnable Interface

1. public class MyThread implements Runnable { // that’s all for the class
2. private String tname;
3.
4. public MyThread(String n) {
5. tname = n;
6. }
7.
8. @Override
9. public void run(){
10. for(int i=0;i<100;i++) {
11. System.out.println(tname + " is counting : " + i);
12. }
13. }
14. }
Main

1. public class App {

2. public static void main(String[] args) throws Exception {
3. System.out.println("Hello, World!");
4. MyThread m1 = new MyThread("Thread 1");
5. MyThread m2 = new MyThread("Thread 2");
6.
7. Thread t1 = new Thread(m1);
8. Thread t2 = new Thread(m2);
9. t1.start();
10. t2.start();
11. }
12. }
Parallelism vs Concurrency

● Just because we have a process or a thread, it does not mean that they will
run on a separate processor (that is, “in parallel”).
● Most of the time the OS is responsible for assigning processes to its CPUs.
● Here’s an example computer:

● How the OS handles the performance and efficiency cores is not up to us.
● We can, however, do parallel computing, in the sense that we can say which
process or thread will be run on which CPU.
Parallelism vs Concurrency
● That is why parallelism and concurrency is related but not the same.
● We can have concurrency on a single CPU, by taking turns on each process, making it feel
like they are running at the same time.
● However, we need more than one CPU (or CPU core) to have parallelism.
● We will not delve into further detail, but there are two APIs that you may look
into:
○ OpenMP - a C/C++ API that supports multi-platform shared-memory multiprocessing
programming.
○ CUDA - which is a parallel computing platform and API that allows software to use certain
types of graphics processing units (GPUs) for accelerated general-purpose processing
(GPGPU).
● These libraries require careful programming to handle the data they are
operating on.
Threads

● Back to threads.
● Now that we know how to start a thread and run code in parallel, let’s think
about some use cases.
● Simplest use case is when the thread is assigned an independent task.
○ This is everyone’s favourite! You start the thread and when it is done, it is done…
● For example, consider a text editor:
● You want to save the current file: do it in a thread so that your user interface will continue to be
responsive.
● Saving the file is independent, the job is simply to write the content of the text area into a file.
● If the file is large, then you may notice the performance improvement.
Threads

● The second use case is to assign a task to each thread, let them compute,
then receive their data…
● This is the case in, say, genetic algorithms.
● In genetic algorithms, we have a “population” (=list) of “individuals” (=array of
values) and a “fitness function” (=it is just a function, really).
● We generate these “individuals” randomly, and we want to find out how “fit”
they are.
● Since each individual is independent of another, we can evaluate each in
parallel with the fitness function.
Threads

● Since the software cannot decide how to distribute these tasks, so we have to
distribute them intelligently.

● Let’s say there are a 1000 individuals. How should we distribute them?
● Let’s stick to 4 threads.
● So, you will divide the problem into 4 tasks, 250 individuals each, and compute
their fitness values.
The Genetic Algorithm

● Let’s say that we want to find the values a, b, c, and d, which will make the
following function, f(x), “0” for x=3.

f(x) = ax3 + bx2 + cx + d

27a + 9b + 3c + d

● We generate random values for a, b, c, and d, and call them solutions.

● Our fitness function will replace a, b, c, d and assign a “fitness value” to them:
the closer the value to 0, the better the fitness.
The Classes

● A class called Individual can handle the random values for a, b, c and d.
● In the main method, we will create 1000 of these individuals.
● We will create a GAThread class, which will handle 250 of these arrays.
● Then we will start four threads at the same time.
● Let’s go over the classes before other details.
Individual
1. import java.util.Random;
2.
3. public class Individual {
4. private int a;
5. private int b;
6. private int c;
7. private int d;
8. private int fitness;
9.
10. public Individual() {
11. Random r = new Random(System.currentTimeMillis());
12. a = r.nextInt(3);
13. b = r.nextInt(3);
14. c = r.nextInt(3);
15. d = r.nextInt(3);
16. }
17.
18. public int getA() { return a; }
19. public int getB() { return b; }
20. public int getC() { return c; }
21. public int getD() { return d; }
22. public void setFitness(int f) { fitness = f; }
23. public int getFitness() { return fitness; }
24. }
GAThread

1. public class GAThread implements Runnable {

2. private Individual[] population;
3. private int start;
4. private int end;
5.
6. public GAThread(Individual[] p, int s, int e) {
7. population = p;
8. start = s; end = e;
9. }
10.
11. private void fitness(Individual i) {
12. i.setFitness(27 * i.getA() + 9 * i.getB() + 3 * i.getC() + i.getD());
13. }
14.
15. @Override
16. public void run() {
17. for(int i=start;i<end;i++) {
18. fitness(population[i]);
19. }
20. }
21. }
Main

1. public class GeneticAlgorithm {

2.
3. public static void main(String[] args) {
4. int SIZE = 1000;
5. Individual[] population = new Individual[SIZE];
6. for(int i=0;i<population.length;i++) {
7. population[i] = new Individual();
8. }
9.
10. Thread t1 = new Thread(new GAThread(population, 0, 250));
11. Thread t2 = new Thread(new GAThread(population, 250, 500));
12. Thread t3 = new Thread(new GAThread(population, 500, 750));
13. Thread t4 = new Thread(new GAThread(population, 750, 1000));
14.
15. t1.start();
16. t2.start();
17. t3.start();
18. t4.start();
19.
20. // at this point, all the work must be done, right? —> NO!
21. System.out.println("All fitness values are calculated.");
22. }
23. }
Remarks

● After all t1 to t4 start() calls, we immediately print “All fitness values are
calculated” - however, this is not true.
● The threads are still running.
● We should wait for them to finish.
● To do so, we should call join on each thread.
● When we call join on a thread object, say t1, the calling thread (in this case
the main thread) waits for t1 to finish.
● Let’s do so.
Main (correct version)
1. public class GeneticAlgorithm {
2.
3. public static void main(String[] args) {
4. int SIZE = 1000;
5. Individual[] population = new Individual[SIZE];
6. for(int i=0;i<population.length;i++) {
7. population[i] = new Individual();
8. }
9.
10. Thread t1 = new Thread(new GAThread(population, 0, 250));
11. Thread t2 = new Thread(new GAThread(population, 250, 500));
12. Thread t3 = new Thread(new GAThread(population, 500, 750));
13. Thread t4 = new Thread(new GAThread(population, 750, 1000));
14.
15. t1.start();
16. t2.start();
17. t3.start();
18. t4.start();
19.
20. // we wait for all threads to finish in the following try block
21. try {
22. t1.join(); t2.join();
23. t3.join(); t4.join();
24. } catch (InterruptedException e) {
25. e.printStackTrace();
26. }
27.
28. // at this point all work must be done.
29. System.out.println("All fitness values are calculated.");
30. }
31. }
Concurrency

● So far we have no problems, because each thread was independent.

● What happens if each thread wants to read or write to the same memory
space - such as a variable or an array?
● This causes problems.
● Consider the following scenario:
Concurrency

● Thread t1 reads the variable v, and gets its value as 1.

● Then, it uses v to make some calculations, and updates it as 3.
● While t1 was working on it, thread t2 reads the same variable as 1, too, and
makes other calculations, and sets it as 4.
● Which is the final correct value?
Concurrency

● If there are multiple threads accessing a certain piece of code that each can
change, then the access must be sequential.
● Such sections should not be parallel, but in sequence. So, we protect the
access to it by programming languages constructs.
● This is called “synchronization.”
● One way to do it is to use “synchronized” methods.
● Another way is to use “Locks”.
● You will learn more about them in the operating systems course!
● For more, please refer to
https://docs.oracle.com/javase/tutorial/essential/concurrency/index.html
References

● Chapter 26, Java How to Program, 10/e (Early Objects), Global Edition, Paul
Deitel and Harvey Deitel. Pearson, ISBN: 9781292018195.
● Other sources.