§2.2–2.3Virtualizing Memory … Concurrency

The CPU demo showed one resource being multiplied into many. This page runs the same experiment on memory — and then breaks something, on purpose, with threads.

2.2 Virtualizing Memory

The model of physical memory presented by modern machines is very simple: memory is just an array of bytes. To read, you name an address; to write (or update), you name an address and supply data. That’s the whole interface.

Programs use it constantly. Every data structure a program keeps lives in memory, reached by loads, stores, and other memory-touching instructions. And don’t forget the program itself lives there too — the fetch in fetch–decode–execute is a memory access on every single instruction.

The book’s second program, mem.c (Figure 2.3), allocates memory and slowly counts in it:

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int
main(int argc, char *argv[])
{
    int *p = malloc(sizeof(int));                        // a1
    assert(p != NULL);
    printf("(%d) address pointed to by p: %p\n",
            getpid(), p);                                // a2
    *p = 0;                                              // a3
    while (1) {
        Spin(1);
        *p = *p + 1;
        printf("(%d) p: %d\n", getpid(), *p);            // a4
    }
    return 0;
}

Figure 2.3: A Program That Accesses Memory (mem.c)

It allocates an int (line a1), prints the address of that memory (a2), stores zero into it (a3), then loops: sleep a second, increment, print (a4). Each print also includes the PID pid Process identifier — a unique number naming a running process. defined in ch. 2 — open in glossary — the process identifier, unique per running program:

prompt> ./mem
(2134) address pointed to by p: 0x200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5
^C

Unremarkable — the memory landed at address 0x200000 and counts upward. Now run two instances at once:

prompt> ./mem &; ./mem &
[1] 24113
[2] 24114
(24113) address pointed to by p: 0x200000
(24114) address pointed to by p: 0x200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
(24113) p: 4
(24114) p: 4
...

Figure 2.4: Running The Memory Program Multiple Times

Both processes allocated memory at the same address — 0x200000 — and yet each updates its value independently, as if the other didn’t exist. Watch it happen:

This is the OS virtualizing memory — the same trick as virtualizing the CPU, applied to a different resource. Each process gets its own private virtual address space address space A process's private virtual view of memory, which the OS maps onto physical memory. defined in ch. 2 — open in glossary (usually just address space), which the OS somehow maps onto the machine’s physical memory. An address like 0x200000 is only meaningful within a process; the running program believes it has physical memory all to itself. The reality: physical memory is one shared resource, managed by the operating system.

2.3 Concurrency

The third theme: concurrency concurrency The problems that arise when working on many things at once within the same memory space. defined in ch. 2 — open in glossary — the book’s umbrella term for the host of problems that arise when working on many things at once in the same program. These problems appeared first inside the OS itself (as you just saw, it juggles many processes at once), but they are no longer the OS’s private headache: modern multi-threaded programs hit exactly the same issues.

Meet threads.c (Figure 2.5):

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

volatile int counter = 0;
int loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        counter++;
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "usage: threads <value>\n");
        exit(1);
    }
    loops = atoi(argv[1]);
    pthread_t p1, p2;
    printf("Initial value : %d\n", counter);

    Pthread_create(&p1, NULL, worker, NULL);
    Pthread_create(&p2, NULL, worker, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("Final value   : %d\n", counter);
    return 0;
}

Figure 2.5: A Multi-threaded Program (threads.c)

main creates two threads thread A function running within the same memory space as other functions, with more than one active at a time. defined in ch. 2 — open in glossary — think of a thread as a function running within the same memory space as other functions, with more than one active at a time. Both threads run worker(), which just increments a shared counter loops times. (Pthread_create, with a capital P, is the book’s wrapper that calls pthread_create and checks the return code.)

Each of the two workers increments the counter loops times, so with loops = 1000 you’d predict a final value of 2000 — and you’d be right:

prompt> gcc -o thread thread.c -Wall -pthread
prompt> ./thread 1000
Initial value : 0
Final value   : 2000

With loops = N, the answer should always be 2N. Should be. Turn the dial up:

prompt> ./thread 100000
Initial value : 0
Final value   : 143012     // huh??
prompt> ./thread 100000
Initial value : 0
Final value   : 137298     // what the??

Not 200,000 — and a different wrong answer each run. (Run it enough times and it will occasionally even be right.) Nothing in the source changed; only timing did.

The culprit is the innocent-looking counter++. It is not one operation but three instructions: load the counter from memory into a register, increment the register, store it back. Because those three do not execute atomically atomic Executing all at once, indivisibly — what a multi-instruction sequence like counter++ is not. defined in ch. 2 — open in glossary — all at once, indivisibly — a switch between threads at the wrong moment silently loses an update. Step through one such moment:

With 100,000 loops per thread, the timer interrupt lands mid-increment over and over — each time erasing one update. How many land there differs run to run, which is exactly why the wrong answers differ run to run.

Next: the third and final piece — what happens when the power goes out, and why file systems exist.