The Illusion of Parallelism

Among the many concepts (and pre-concepts) of computer science, one paradigm in particular has always fascinated me: illusion. In computer science unlike many other sciences you are free to cheat, hide and use all the tricks you want to make the user believe anything. Some patterns on graphical interfaces and user experiences are so devious that they have been strongly criticized by many people1.

One of the “magic tricks” that still fascinates me is the “fake parallelism”. Let’s imagine that we have a single CPU device with only one core and we want to listen to music in the background while we write the new article to be published on a blog. From the basic theory of computer science we know that a single core can perform at most one operation at a time and, except in special cases, it is not possible to have a parallelism between instructions.

A person could think that pressing a key generates a series of connections between CPU and I/O that pauses the “musical” flow: in this case you would hear several pauses between the notes of the musical melody. But this is not the case. If we tried to listen to music on an online platform while writing in any text editor, we would not notice any difference between different moments. So how does this process take place? Is it possible that the machine has more than one core and nobody told us?

This is actually the illusion of parallelism, a principle that makes the user believe that they can run multiple processes at the same time, when in fact they are just several processes that run sequentially and closely together giving the illusion of parallelism. This concept is also called multi-tasking and exploits the slowness of users. As an example, let’s say we have two processes p_1 and p_2. p_1 and p_2 alternate every 10 ms in memory and each of them produces a different tone. The user cannot distinguish the difference of the two musical tones in such a short time, and the mind would actually merge the two tones into one. (Same thing happens with any other type of event of the two processes).

How does the mechanism work? It’s very simple: without going into too many details, the operating system assigns to each process a certain time limit within which they can occupy the CPU, executing program instructions according to the Fetch-Decode-Execute cycle. When the time expires, the operating system (acting as a sort of referee) assigns the same time limit to another process and so on. During the change from one process to another, the so-called context switch occurs. In fact it is not sure that p_1 or p_2 have finished their operations in the moment in which the time expires (in the greater part of the times a process passes various times from ready to execution).

The illusion produced by the operating system creates a parallelism that the user believes in when he wants to perform several different operations. It is evident that over time it was realized that a one-core system could get to execute “simultaneously” a number of processes, up to a limit number. From that point on, efforts were made to adopt multi-core systems that could have more than one CPU available.

Example of illusion

The following examples2 is the perfect one to show better the illusion:

#include <stdio.h>
#include <stdlib.h>

double GetTime() {
    struct timeval t;
    int rc = gettimeofday(&t, NULL);
    assert(rc == 0);
    return (double) t.tv_sec + (double) t.tv_usec/1e6;
}

void Spin(int howlong) {
    double t = GetTime();
    while ((GetTime() - t) < (double) howlong); 
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "usage: ./cpu <string>\n");
        exit(1);
    }
    char *str = argv[1];

    while (1) {
        printf("%s\n", str);
        Spin(1);
    }
    return 0;
}

This code doesn’t do much. In fact, all it does is call Spin(), a function that repeatedly checks the time and returns once it has run for a second. Then, it prints out the string that the user user passed on the command line, and repeats, ad infinitum.

Let’s say we save this file as cpu.c and decide to compile and run it on a system with a single processor.

root@node: gcc cpu.c -o cpu
root@node: ./cpu "A"
A
A
A
A
A
A
^C

Once a second has passed, the code prints the input string passed by the user (in this example, the letter “A”), and continues. CTRL+C to stop execution. Now let’s take it a step further, try running multiple instances of this program using “&”.

root@node: ./cpu A & ./cpu B & ./cpu C & ./cpu D &
[1] 15353
[2] 15554
[3] 15230
[4] 19102
A
B
D
C
A
B
D
C
A
...

Well, now things get a little more interesting. Even though we only have one processor, somehow all four of these programs seem to be running at the same time! How does this magic happen? It turns out that the operating system, with some help from the hardware, is responsible for this illusion, namely the illusion that the system has a very large number of virtual CPUs. Turning a single CPU (or a small set of them) into a seemingly infinite number of CPUs and thus allowing many programs to run simultaneously is what is called CPU virtualization.


  1. These are called dark patterns, but that’s another story. ↩︎

  2. Example taken from “Operating Systems: Three Easy Pieces” by Remzi H. Arpaci-Dusseau. ↩︎