Skip to main content

Concurrency, Parallelism and Threads

Updated 13 min readMarkdown

So far, we have built a foundation around process creation and management (Process and Process API) and how the OS safely switches between them (Limited Direct Execution).

A fundamental problem which is still actively researched is how to reduce idle CPU cycles and utilise your compute with maximum efficiency? The answer largely lies in the three concepts which we will discuss in this blog.

How processes runs on CPU

We wont go deep inside this, but the key point here is there are several registers which keeps track of what process is running, what is happening inside that process. One of those register is Program counter(PC) which stores the address of the instruction which needs to be executed next. There are other registers too, like General purpose registers which hold temporary data, intermediate calculation results etc. Stack/Base pointers which are used to setup the stack frame for a process, Status/flag registers which helps in simulating loops/conditions in code. For a particular process the state of these registers is stored in a data structure called Process Control Block(PCB), when a context switch happens PCB plays a important role in letting the process run from where it left by again initialising the register's values from PCB.

Concurrency

Imagine there are 3 programs A,B,C all of them take 5 minutes to finish and has no blocking state so they utilise the CPU for 100% of their execution time. If we run them in a sequential manner they will take 15 minutes to finish but a User would find A to be finished in 5 minutes and will perceive that C took 15 minutes. To solve this we can implement a time sharing approach so each program gets a finite amount of time to run a portion of it and then another program takes over for some time. So now A runs for a very short time(milli seconds) then B then C and this happens until all of them finishes. What advantage it brings to us? Nothing but a perceived notion that all 3 programs were running simultaneously and it gives the User a better fair experience in some manner.

We can stop here and call this concurrency, as concurrency has nothing to do with parallelism and its not guaranteed that concurrency would bring us a performance enhancement. Lets see how much time it took to finish the 3 tasks now, its >15 minutes as now we also have to account the context switch overhead between them. So instead of solving our original problem of using compute with more efficiency, we used it in a less efficient manner.

But in practise this is not the case, our assumption of having a program with no blocking I/O is not practical as to have a non-deterministic program we will have some form of I/O. So now we have a lot of CPU cycles where our program just waits and not do anything, in these cycles we want that other programs should run which are in the queue and this will eventually make our time <15 minutes, also our context switch overhead will be compensated as the idle CPU cycles will be far more than the cycles lost in Context switch. But how would this happen we need a orchestrator for this, here OS comes into play. As we discussed before this will all happen with the help of PCB and context switch, every time a process needs to run the OS will load all of its registers values from PCB to registers, Program counter will help the process to resume from where it was interrupted.

But how will we ensure that OS gets the runtime it want for all this once we have given the control to the running process? Every time a process wants to do a I/O it need to use a system call(APIs given by OS) as I/O is a privileged operation and can only be done by OS(kernel). So this is a point where the control is with OS and at this point the OS before giving the control back to the process can first give it to the scheduling service which can see which process needs to be run as our process may have gone into a waiting/blocked state and even if not, still any other process can be give the runtime before our process through which the system call was made. These are all CPU-scheduler's strategy which I will write a blog in future. But there's a big problem what if a process falls into a infinite loop without any system-call or a program with malicious intent which never raises an interrupt?
Now our OS will never get back the control and we will eventually lose the control to our system as we can't run any other process.

This does not have a software-level solution, at hardware level we have a timer embedded into CPU which ensures that once the timer is finished it will eventually raise a interrupt and the control will go to OS. We have 2 types of scheduling strategies here preemptive and non-preemptive, in preemptive scheduling OS ensures that it resets the timer once it has the control and see which process needs to be run now, it may forcibly interrupt and pause a currently running process moving it from the Running state back to the Ready state—before it has finished its execution.

This concludes the Concurrency part, concurrency is basically dealing with a lot of things at once in such a manner that it maximises the CPU usage. It also ensures that system is in control of OS and CPU is fairly distributed among all process even if some processes has fewer blocking cycles.

Parallelism

Now what if we have a lot of programs such that our system is spending more time doing context switches rather than doing useful work? This state is called CPU thrashing where it spends more time managing tasks than executing them.

Now we need true Parallelism i.e. true hardware support, we want to run programs in parallel rather switching between them. This is where multi core systems are useful, now if we have N core system we can potentially run N tasks in parallel and still a lot more than N tasks concurrently on these N cores. Now each core is a CPU in itself containing its own registers needed to run a program, so now instead of a single Program counter we have multiple PC one for each core. Can we achieve true parallelism on single core architecture? No, we may feel the illusion of it because concurrency in itself feels like parallelism to naive eyes.

Keep a note that Concurrency in itself still happens on each core and even after having multiple cores, we can attain CPU thrashing. However single core can still attain certain form of parallelism like instruction pipelining and SIMD(Single Instruction Multiple Data) vector instructions, we will discuss these topics in future blogs.

Threads

Now why do we need threads and where do they come in this discussion?

Until now we were assuming process as the fundamental unit of execution but But in modern operating systems, that isn't actually true: threads are the true fundamental unit of execution.

Understanding threads in isolation can be tricky, so the easiest way to grasp them is by contrasting them directly with processes. The single biggest distinguishing factor comes down to memory: processes are strictly isolated from one another, whereas threads share the same address space.

• Processes (Strict Isolation): Every process gets its own private virtual address space. Process A cannot accidentally (or maliciously) read or overwrite Process B's memory. This isolation makes processes safe and independent, but it also makes creating them and switching between them expensive.

• Threads (Shared Address Space): Multiple threads living inside the same process share the exact same heap, global variables, and code. While each thread still needs its own private Program Counter (PC), registers, and stack to track where it is in execution, they all look at the same underlying memory. Even though Threads share same memory space they don't share CPU state so one PC for each process or per core is not sufficient now, we have multiple PC per process or PC per thread.

As threads share the same memory space, communication between them is easy and happens without kernel intervention.

Now we can see how threads changes our memory space, we have multiple stacks one for each thread, for each thread any stack-allocated variables, parameters, return values, and other things that we put on the stack will be placed in what is sometimes called thread-local storage, i.e., the stack of the relevant thread.. However they may reference to some variables which may not be in their thread and may be on shared heap/stack or even another thread's stack.

Why do we need threads? Imagine if in our code there are 2 functions that are totally independent(for example, one fetches data from a network while another renders a UI) so on a multi-core system we want some way to run them in parallel even though they are part of same program this is called task parallelism where we want 2 tasks to run in parellel. There is one more case imagine we have a large array and we want to perform some operation(like applying a filter to every pixel of an image). on whole array, here also we can execute this operation on whole data in parellel by dividing the array into chunks and performing operation on them in parallel. This is called data parallelism.

So a thread is not a function or piece of code in itself but its a pointer to a piece of code in our Text/Program code section, so now we may think that multiple threads can point to the same piece of instruction or address in memory space and because of this any race condition may happen, but the text section in a memory space is read-only section so its safe for any thread to access any instruction at any given time.

void *mythread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}
int main(int argc, char *argv[]) {
   pthread_t p1, p2;
   int rc;
   printf("main: begin\n");
   Pthread_create(&p1, NULL, mythread, "A");
   Pthread_create(&p2, NULL, mythread, "B");
   // join waits for the threads to finish
   Pthread_join(p1, NULL);
   Pthread_join(p2, NULL);
   printf("main: end\n");
   return 0;
}

In this code block we have created 2 threads both of which executes the same function but with diff arguments. The main thread calls pthread_join(), which waits for a particular thread to complete. It does so twice, thus ensuring T1 and T2 will run and complete before finally allowing the main thread to run again; when it does, it will print “main: end” and exit.

In C, if the main thread returns and exits early without joining, the entire process terminates—killing any running child threads midway through their work. However, this behavior is language- and runtime-dependent. While systems languages like C, C++, and Go immediately tear down the process when main() returns, managed runtimes like Java, C#, and Python distinguish between user (foreground) threads and daemon (background) threads—keeping the process alive until all active user threads have finished running.

The output of above program is non-deterministic as the scheduling of threads in arbitrary and totally depends on the scheduler.

The three traces show different possible execution schedules:

  1. Trace 1: Main creates T1 and T2, then waits for T1. T1 executes and prints A. Then T2 executes and prints B. Main resumes after both threads finish and prints "main: end".
  2. Trace 2: Main creates T1. T1 gets scheduled immediately, prints A, and finishes. Main then creates T2. T2 prints B and finishes. When main calls join() on both threads, they are already finished, so both calls return immediately.
  3. Trace 3: Main creates T1 and T2, then waits for T1. However, T2 gets scheduled first, prints B, and finishes. T1 then executes, prints A, and finishes. Main proceeds after both joins complete and prints "main: end".

There is also the famous counter increment problem in which we have a shared int and we try to increment in 10^7 time by each thread.

static volatile int counter = 0;
void *mythread(void *arg) {
   printf("%s: begin\n", (char *) arg);
   int i;
   for (i = 0; i < 1e7; i++) {
   counter = counter + 1;
   }
   printf("%s: done\n", (char *) arg);
   return NULL;
}
int main(int argc, char *argv[]) {
   pthread_t p1, p2;
   printf("main: begin (counter = %d)\n", counter);
   Pthread_create(&p1, NULL, mythread, "A");
   Pthread_create(&p2, NULL, mythread, "B");
   Pthread_join(p1, NULL);
   Pthread_join(p2, NULL);
   printf("main: done with both (counter = %d)\n", counter);
   return 0;
}

Our expected result is 2*10^7 but when we will run the code the output wont be like this, it is not even deterministic.

We have to understand that the counter increment operation in C is not atomic, the compiler generated assembly for this is not a single instruction.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

The problem with this is that a thread maybe in process of executing these instructions and may have loaded value 50 into eax register but then a timer interrupt goes off and now control went to thread 2 which will do the same load of value 50 into its own eax and will then complete the operation. This will ensure that we have value 51 in out int but now when control goes back to thread 1 it will do the same increment on its eax register as it was loaded earlier as 50 and will again push the value 51 into our int. Eventually what has happened is that we did execute the increment operation twice but the value is only incremented once. This is called a race condition and the section of code which is vulnerable to this is called critical section.

The solution to this is synchronisation primitives(such as locks, mutexes, and atomic operations) which are implemented with the help of hardware support. Synchronisation primitives is a topic in itself and we will cover it in future blogs.

Conclusion

To bring it all back to our opening question: eliminating idle CPU cycles isn't about any single silver bullet. Concurrency keeps the CPU busy during I/O waits, parallelism lets us scale across multiple hardware cores, and threads give us a lightweight way to share memory without heavy process overhead. Of course, shared memory opens the door to race conditions—which brings us directly to our next topic: locks, mutexes, and how hardware helps us tame concurrency.

Resources

https://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf

https://youtube.com/@coredumpped?si=DJxIAwn6z_Nv7SyQ

No comments yet. Be the first to comment.