Introduction: Religion, Philosophy, and Science

Mathematics, science, logic, and related subjects have their roots in philosophy. In turn, philosophy arose from questions raised by religion. Such questions include:

Where do we come from? [What are our origins? Who made us?]
Who and what are the gods? [How do humans relate to the divine?]
How can we worship and obey the gods? [How should we live? What is justice? What is the highest good?]
How should we relate to each other? [How can we form religious communities?]
Where are we going? [What is death? Why do we die? Is there an afterlife?]

Ethics, Physics, and Logic

Stoicism was a school of philosophy founded in Athens around 300 B.C., not long after the death of Socrates (469-399 BC).

Stoic philosophers divided knowledge into three branches:

ἔθος
Ethics: justice, right and wrong, good and evil, customs, law, etc.
λόγος
Logic: Thinking, reasoning, deducing, calculating, and language
φύσις
Physics: Nature, matter, motion, the physical and the metaphysical, form, shape

All of the above are aspects of computer science and science in general.

Ethics

Course Description for CSC 152:

“An introduction to computer science. This course covers problem-solving methods and algorithm development; the design, coding, debugging, and documentation of computer programs.”

It would be naive to assume that technology and science merely solve our problems.

Science cannot solve the age-old problems of the human condition. Consider current events — has science been able to stop the chaos? Not at all. In fact, in many ways science adds to the chaos — consider Social Darwinism, nuclear weapons, napalm, radioactive waste, toxic substances, etc. Science, war, and politics are intertwined.

Ethics can teach us how to question and criticize scientists, military leaders, and politicians — the people who have influence and power.

The future may be worse, not better. HYPER REALITY illustrates how technology and dystopia can coincide.

Logic and Mathematics

Logic, philosophy, and mathematics are close-knit fields. C.S. Peirce is but one example of a philosopher who was also a logician and a mathematician.

In fact, logic has its roots in ancient Greece. The Stoic philosophers developed truth functional logic, for example. Arguably, Plato developed the conceptual framework for modern logic.

Going back even further in history, we have the Egyptians — in many ways, they laid the foundations for Western thought, including mathematics.

For example, Egyptian fractions are fractions in which the numerator is one. They express the idea that a unit can be divided into parts.

The One and the Many: This is the underlying principle not only of mathematics, but (Plato and others would argue) of everything.

For example, consider:

One book has many pages
One classroom has many students
One folder holds many documents
One word contains many letters, one letter contains many parts
One number comprises many units

Physics

Five classes of materials for calculating and computing:

Flesh: hands, fingers (“digits”), people who compute

Wood and Stone: e.g. the abacus
Metal: e.g. calculating machines invented by philosophers and mathematicians such as Pascal and Leibniz in the 17th century

Electro-mechanical devices: machines invented by Zuse, Aiken, Stibitz, etc. in the 20th century

Electronics: Colossus, ABC, ENIAC, etc. [1]

Images

A 19th-century Chinese abacus. Numbers are entered by sliding beads toward the crossbar; each of the upper beads represents 5, while the lower beads represent 1. The number shown above is 7,230,189 [2].

Electronic Numerical Integrator and Computer, or ENIAC, became operational in 1946 at The Moore School of Electrical Engineering at the University of Pennsylvania. It was designed and used for military purposes such as calculating artillery range tables and the construction of weapons of mass destruction [2].

“Programming ENIAC was a one-way ticket to the madhouse. You did not sit down at a computer terminal and type in the instructions; instead, you set thousands of switches and plugged in hundreds of cables (like the cables on old telephone operator consoles) by hand, one at a time. In general, it took about two days to set up ENIAC to carry out a program.” — S. Augarten in [2].

Although designed for artillery calculations, the ENIAC’s first job “was a large and complex calculation of the feasibility of a proposed design for the H-bomb ... The calculation, a mathematical model of an H-bomb explosion, was enormous, with thousands of steps for the program and a million punch cards for the data. Since ENIAC could not store programs or remember more than twenty ten-digit numbers ... the program had to be solved in stages, an exceedingly cumbersome process” — S. Augarten in [2].

Linux and Bash

Online Linux Emulators

Bash

The name bash is an abbreviation of Bourne Again SHell, a Unix command-line interface designed by Brian Fox in 1989. It is a replacement of the original Unix shell, sh, which was developed by Steve Bourne in 1977. Below we see that bash is one of many command line shells, all of which have a lineage that traces back to sh [3].

Bash Commands for Linux

which bash

lscpu 

pwd

ls
    ls -r
    ls -t
    ls -l
    ls -a
    ls -rtl


cd
     cd /bin
     cd .. 
     cd

mkdir

touch

mv

cp

tree

echo
    echo "hello"
    echo "hello" > hello.txt [> is output redirection]

cat
    cat hello.txt
    cat hello.txt test.txt

history
    history 10
    history 100
    history | less
    cd ; vi .bash_history

_____

Week 3:

More on directories:

     $ ls -rtla
     ...
     drwxr-xr-x   1 root root  200 Jan 30 12:08 ..
     drwxr-xr-x   1 root root  200 Jan 30 12:08 .

. is the current directory.
.. is the parent directory.

~ is the user’s home directory. Example:

     $ cd ~
     demo@mx1:~
     $ pwd
     /home/demo

Note that cd is a short cut for cd ~.

/ is the root directory (the directory at the highest level). Thus, cd / changes 
to this directory.

_____

Installation:

sudo allows a permitted user to execute a shell command as the superuser — i.e., as the 
“root” user. Typically, when installing packages using apt, yum, pkg, etc., we need 
to use this command.

     Examples:

          $ sudo apt update
          $ sudo apt install tcpdump

          $ sudo apt update
          $ sudo apt install xxd

_____

Observations:

The Zen of Python:

     >>> import this

     Beautiful is better than ugly.
     Simple is better than complex.
     There should be one — and preferably only one — obvious way to do it.

We can debate whether the above is true of Python. But clearly the opposite is true of *nix, 
which is:

   * Not beautiful but ugly (or at least awkward).
   * Not simple but complicated, and unnecessarily so.
   * Often there is more than one way to do something in *nix, with each way being obscure 
     or counter-intuitive. This breeds inconsistency and confusion.

          For example, there are three commands for obtaining help in *nix: man, 
          info, and help. Try using these on ls and cd.

          Consider commands such as cat, rm, date — why not 
          print, delete, and time?


In short, *nix is archaic, counter-intuitive, and inconsistent. However, we should know how 
to use *nix because:

  * It is free and, to a large extent, open source. For this reason alone it is preferable 
    over other operating systems.
  * It works, and if you know how to use it, it sometimes works well.

In any case, we should be wary of hyperbole such as Eric Raymond’s 17 Unix Rules. 
If, for example, Unix programming is “simple,” why are there 17 rules? 

Finally, consider the following: there are *at least* five ways of writing a for loop 
in Bash:

     $ for ((i = 0; i < 10; i++)); do echo $i; done

     $ for i in `seq 10`; do echo $i; done

     $ for i in $(seq 10); do echo $i; done

     $ for i in {1..10} ; do echo $i ; done

     $ for ((i = 0; i < 10; i++))
     > do
     > echo $i
     > done

Variables in Bash

After setting the value of a variable, we access the value by prefixing the variable name with $. 

Example:

     $ #space matters

     $ i = 10
     i: command not found

     $ i=10

     $ echo i
     i

     $ echo $i
     10

Loops

As stated above, there are many ways of implementing loops in Bash. Here is one way:

     $ for ((i=0; i<10; i++)); do echo i is $i; done

We can execute file operations within a loop. Example:

     $ for ((i=0; i<5; i++)); do touch tmp$i; done

To execute multiple commands in a loop, write the commands within do...done and separate
each command with ;. Example:

     $ for ((i=0; i<5; i++)); do touch tmp$i; echo tmp$i touched; done

Writing Bash Scripts

MX Linux typically includes several text editors, including:

   vi or vim (powerful but difficult to learn)
   nano (easy to use, and it runs within a terminal window)
   featherpad (uses a GUI and also easy to use; similar to Notepad in Windows)

Let's start with a very simple script, call it test.sh:

     #!/usr/bin/bash

     for ((i = 0; i < 5; i++))
     do 
        sleep 1 # sleep 1 second
        echo i is $i
     done

Now, let's try to run the script:

     $ test.sh
     test.sh: command not found

The problem here is that we need to specify the path, as so:

     $ ./test.sh
     bash: ./test.sh: Permission denied

Now, we have another problem. By default, scripts are not executable. 
We need to use chmod to change the script's permissions so 
that the user of the file (i.e., the file's owner) can execute it:

     $ chmod u+x test.sh

Now we can run the script:

     $ ./test.sh
     i is 0
     i is 1
     i is 2
     i is 3
     i is 4

Q: How would we write a script to create 5 subdirectories named tmp0 ... tmp4?

Background Processes

Consider the following:

     $ cat test2.sh
     #!/usr/bin/bash

     for ((i=0; i<250; i++))
     do
        sleep 1 #sleep 1 second
        echo i is $i >> out
     done

     $ ./test2.sh

While the script is running, we are unable to enter new commands in the current
terminal. 

If, for example, we wanted to list running processes with the ps command,
we would need to do so in another terminal. While test2.sh is running, open 
another terminal and run the following:

     $ ps
         PID TTY          TIME CMD
        8213 pts/0    00:00:00 bash
       20490 pts/0    00:00:00 ps

If we want a list of all processes, we use ps -e. We can use grep
to get a shorter list:

     $ ps -e | grep sh
           5 ?        00:00:00 slub_flushwq
          66 ?        00:00:00 zswap-shrink
        4815 ?        00:00:00 ssh-agent
        7320 pts/1    00:00:00 bash
        8213 pts/0    00:00:00 bash
       12194 pts/2    00:00:00 bash
       20262 pts/1    00:00:00 test2.sh

We can use the kill command to terminate test2.sh from another terminal.

If we want to continue using the same terminal without killing test2.sh, we 
can run the script in the background, like so:

$ ./test2.sh &
[1] 21360
demo@mx1:~/wk3b

Then, at the prompt, we can use either jobs or ps to see that 
test2.sh is currently running:

     $ jobs
     [1]+  Running                 ./test2.sh &

     $ ps
         PID TTY          TIME CMD
        7320 pts/1    00:00:00 bash
       21360 pts/1    00:00:00 test2.sh
       21377 pts/1    00:00:00 sleep
       21378 pts/1    00:00:00 ps

We can kill a job running in the background as follows:

     $ jobs
     [1]+  Running                 ./test2.sh &

     $ kill %1

Note that processes running in the background are not synchronized.
Consider:

     $ cat a1.sh
     #!/usr/bin/bash

     while (true) 
     do 
        sleep 0.1
        echo 'Alice' >> out
     done

     $ cat a2.sh
     #!/usr/bin/bash

     while (true) 
     do 
        sleep 0.1
        echo 'Liddell' >> out
        echo >> out
     done

     $ (./a1.sh &); (./a2.sh &)

We would expect to see the following in the file out:

     Alice
     Liddell

     Alice
     Liddell

     Alice
     Liddell

     ...

Since a1.sh and a2.sh are not synchronized, however, we 
may see something very different.

Expressions in Bash

If Bash made sense, we would expect the following to assign 5
to $i:

     $ i=(3+2)
     demo@mx1:~

However, this is the result:

     $ echo $i
     3+2

We need to use $((...)) to evaluate expressions: 

     $ i=$((3+2))
     $ echo $i
     5

Conditionals in Bash use the following format:

     if [ condition ]; then: 
          statements
     fi

Examples:

     if [ $((x % 2)) == 0 ]; then
          echo “Number is Even”
     fi


     if [ $((x % 2)) == 0 ]; then
          echo “x is even.”
     else
          echo "x is odd."
     fi

C

C is also known as ANSI C, ISO C and GNU C. We will focus on the latter. There are a few differences between GNU C and the other standards, but we need not worry about them for now.

C is known in some circles as “the new B” — it is a descendant of the language B (circa 1970), which in turn is a descendant of Basic Combined Programming Language, or BCPL (circa 1960).

C has always been married to Unix — in fact, it was first developed for Unix running on a DEC PDP-11 minicomputer at Bell Labs in 1972 [4]. Bash’s core utilities — ls, touch, echo, and the like — are written in C.

Unlike languages such as Python, Lua, and the like, C is a compiled language. In fact, when we compile C code using a compiler such as gcc, there are four stages:

1. Preprocessing: Comments are removed, included files are expanded, etc. 2. Compiling: Source code is converted into assembly language 3. Assembling: Assembly language is converted into machine language (the "object code"). The result is an “ELF” (Executable and Linkable Format) file. We can view the contents of an ELF file using the readelf -h command. 4. Linking: Libraries, preprocessing code, etc. are linked to the object code. The result is an executable file (a.out is the default name of this file).

We can see the results of 1-4 in separate files if we use the --save-temps option, like so:

$ echo -e '#include <stdio.h>\nvoid main() { printf("Alice"); }' > alice.c $ gcc --save-temps alice.c $ ls -rt -1 a-alice* a.out a-alice.i a-alice.s a-alice.o a.out

Q: Which of the above files are binary? What do we see when we examine each file? Use hexdump to examine binary files.

Let's now consider a simple program that illustrates some basics:

$ cat sum.c #include <stdio.h> void main (void) { int x; int y = 5; int sum; x = 120; sum = x + y; printf("sum: %d \n", sum); } $ gcc sum.c $ ./a.out sum: 125

Note the following:

* Every C program must have at least one function, main(). * Every simple statement in C must end with a semicolon. * The type of every variable must be declared (e.g. int x; declares x as an integer). * A variable may be set when it is declared (e.g. int y = 5;). * { and } are used to define a function block.

Also note that as long as we define the function main, we have a C program. The following produces a valid C program in eight bytes:

$ echo -n "main(){}" > m.c

In general, the format for functions in C is:

return_type function_name (type parameter1, type parameter2, ...) { local variable declarations statements }

Example:

int sum (int x, int y) { return (x+y); }

Here is an example of how we can call a function:

#include <stdio.h> void print_name () { printf("Alice Liddell\n"); } void main() { print_name(); }

The header file stdio.h contains standard input/output function declarations and it is needed for calling printf.

GCC includes useful libraries for string processing, file operations, threads, and many other tasks. For now, however, we will be using low-level C functions — this is the best way to learn how C works at a basic level. It is also a good way to learn more about the operating system within which our code operates.

Let’s consider a simple task: open and then read a text file one byte at a time, and send each byte to the standard output (stdout). We will do this using four low-level C functions:

open and close read and write

The function declarations for the above are included in fcntl.h and unistd.h. Thus, we need to include these files in our source code, as will be shown below.

For this example, we will create a one-word text file:

$ echo "Alice" > alice.txt

Q: "Alice" comprises five characters, but ls -l indicates a file length of six bytes — why?*

Now, let's look at the C code that will accomplish our task:

#include <fcntl.h> /* for open */ #include <unistd.h> /* for read, write, close */ int main() { int source = open("alice.txt", O_RDONLY); char c; int bytes_read; do { bytes_read = read(source, &c, 1); write(STDOUT_FILENO, &c, 1); } while (bytes_read != 0); close(source); }

The first argument of write is the destination (in this case, standard output — i.e., the terminal), the second is a pointer to a memory location that is to be written, and the third argument is the number of bytes to write.

We specify the standard output using STDOUT_FILENO — this in fact is simply a constant defined in a header file, unistd.h. Here are the key lines of this file:

/* Standard file descriptors. */ #define STDIN_FILENO 0 /* Standard input. */ #define STDOUT_FILENO 1 /* Standard output. */ #define STDERR_FILENO 2 /* Standard error output. */

This is common practice in C — we use predefined constants in place of integers. This makes our code more readable and intuitive. However, if we are not worried about compatibility across *nix systems, we are free to use integer values instead of named constants. Thus, these two write statements are equivalent:

write(STDOUT_FILENO, &c, 1); write(1, &c, 1);

Now, let's move on to some basic programming constructs. As you can see below, for loops in C are not unlike loops in Bash:

int i; for (i = 0; i < 5; i++) { ... }

Note that since C is a typed language, we need to specify a variable's type before we can use it. In this course, we will mainly work with two types:

int (integer): occupies 4 bytes of memory char (character): occupies 1 byte of memory

In fact, both of the above are integer types — char (assuming it is unsigned) is an integer with a range of 0 to 255 (00000000 to 11111111 in binary). While char is typically used to represent ASCII characters, it can be utilized as an integer type as well. For a complete list of primitive data types, see section 2.1 of The GNU C Reference Manual — observe that char is listed as an integer type in 2.1.1.

C also has while loops. For example:

$ cat while-loop.c void main() { int i = 0; while (i < 5) { i++; } }

It's worthwhile to examine the assembly language for this code:

$ gcc --save-temps while-loop.c $ cat a-while-loop.s .file "while-loop.c" .text .globl main .type main, @function main: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 movl $0, -4(%rbp) jmp .L2 .L3: addl $1, -4(%rbp) .L2: cmpl $4, -4(%rbp) jle .L3 nop nop popq %rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size main, .-main .ident "GCC: (Debian 12.2.0-14) 12.2.0" .section .note.GNU-stack,"",@progbits

Q: Given that 'jle' = 'jump if less or equal', how is the while loop implemented?

Let's use the above to perform a simple image processing task. First, download this ASCII image.

How can we use C to read the file one byte at a time and copy each byte to a new file? We can do so using C's write function, which mirrors the read function:

$ cat copy.c #include <fcntl.h> #include <unistd.h> int main() { int source = open("alice-ascii.txt", O_RDONLY); int dest = open("alice-ascii-copy.txt", O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR); char c; int bytes_read; do { bytes_read = read(source, &c, 1); write(dest, &c, 1); } while (bytes_read != 0); close(source); close(dest); }

Q: There are two flaws in the code above — what are they? The first concerns the while loop. The second concerns a limitation of the close function (see NOTES in man 2 close).

O_WRONLY | O_CREAT sets write permissions on the file and indicates that the file should be created if it does not exist. (see man 2 open).

S_IRUSR | S_IWUSR sets user read and write permissions on the file (see /usr/include/fcntl.h). Note that S_ is for file status (see man 2 stat) while _I is for inode.

Q: How can we modify copy.c so that it inverts the ASCII image by replacing "." with "#" and "#" with "."? Write the inverted image to a file named alice-ascii-inverted.txt [note: this is now an in-class exercise].

Let’s now consider another data type in C, arrays. An array declaration has three parts:

1. The data type of each element (e.g. int, char, etc.) 2. The name of the array 3. The number of elements in brackets

Here are some examples:

int x[100]; /* array of 100 integers */ char name[25]; /* array of 25 characters */ int z[5] = {1,2,3,4,5}; /* array with initial values set */

Arrays are useful for storing and manipulating the contents of a file. For example:

$ echo "Alice" > alice.txt $ cat read-array.c #include <fcntl.h> #include <unistd.h> int main() { int fd; char buffer; int size = 5; char name[size]; fd = open("alice.txt", O_RDONLY); for (int i = 0; i < size; i++) { read(fd, &buffer, 1); /* One byte (i.e., one character in "Alice") is read from the file */ name[i] = buffer; /* The byte is copied into the array */ } /* Now we can do what we like with the file contents using the array. For example: */ for (int i = 0; i < size; i++) write(STDOUT_FILENO, &name[i], 1); close(fd); }

The above code can be made more concise (e.g., the second loop is not needed), but we’ve spelled things out for clarity.

Below is an illustration of how bytes can be read into an array. As each byte or character is read, the data is stored in a new memory cell.

What, exactly, is a memory cell? It’s important to note that typically we deal with virtual memory, not “physical memory." The latter term, in fact, comprises a large family of many kinds of memory. For example, laptops and mobile devices use LPDDR, Low-Power Double Data Rate memory. A diagram of the architecture of LPDDR is available at https://t.ly/ax222 (p. 3). As we can see from the description, LPDDR comprises “high-speed CMOS” operating at a low voltage to conserve battery power. It is also important to note that physical memory has its own “control logic” — we should not assume that memory is static, as if it were merely passive data awaiting to be manipulated.

In any case, with virtual memory we are dealing with an abstraction of physical memory. The operating system, MX Linux in this case, provides an interface to physical memory by means of virtual memory.

As with physical memory, virtual memory is divided into units or cells, each of which has an “address.” Typically, it is much more efficient to work with addresses rather than data. For example, consider the following C program:

$ cat memory.c int main() { char *c = "CHAPTER I. Down the Rabbit-Hole ... Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, “and what is the use of a book,” thought Alice “without pictures or conversations?” So she was considering in her own mind (as well as she could, for the hot day made her feel very sleepy and stupid), whether the pleasure of making a daisy-chain would be worth the trouble of getting up and picking the daisies, when suddenly a White Rabbit with pink eyes ran close by her. There was nothing so very remarkable in that; nor did Alice think it so very much out of the way to hear the Rabbit say to itself, “Oh dear! Oh dear! I shall be late!” (when she thought it over afterwards, it occurred to her that she ought to have wondered at this, but at the time it all seemed quite natural); but when the Rabbit actually took a watch out of its waistcoat-pocket, and looked at it, and then hurried on, Alice started to her feet, for it flashed across her mind that she had never before seen a rabbit with either a waistcoat-pocket, or a watch to take out of it, and burning with curiosity, she ran across the field after it, and fortunately was just in time to see it pop down a large rabbit-hole under the hedge."; }

This is a simple program with one string, but the string itself is long. How is it handled? When we look at the assembly code for the above, pay attention to leaq:

$ cat a-memory.s .file "memory.c" .text .section .rodata .align 8 .LC0: .ascii "CHAPTER I. Down the Rabbit-Hole ... Alice was beginning to g" .ascii "et very tired of sitting by her sister on the bank, and of h" .ascii "aving nothing to do: once or twice she had peeped into the b" .ascii "ook her sister was reading, but it had no pictures or conver" .ascii "sations in it, \342\200\234and what is the use of a book,\342" .ascii "\200\235 thought Alice \342\200\234without pictures or conve" .ascii "rsations?\342\200\235 So she was considering in her own mind" .ascii " (as well as she could, for the hot day made her feel very s" .ascii "leepy and stupid), whether the pleasure of making a daisy-ch" .ascii "ain would be worth the trouble of getting up and picking the" .ascii " daisies, when suddenly a White Rabbit with pink eyes ran cl" .ascii "ose by her. There was nothing so very remarkable in that; no" .ascii "r did Alice think it so very much out of the way to hear the" .ascii " Rabbit say to itself, \342\200\234Oh dear! Oh dear! I shall" .ascii " be late!\342\200\235 (when she thought it over afterwards, " .ascii "it occurred to her that she ought to have wondered at this, " .ascii "but at the time it all seemed quite natural); but when the R" .ascii "abbit actually took a watch out of its waistcoat-pocket, and" .ascii " looked at it, and then hurried on, Alice started to her fee" .ascii "t, for it flashed across her mi" .string "nd that she had never before seen a rabbit with either a waistcoat -pocket, or a watch to take out of it, and burning with curiosity, she ran across the field after it, and fortunately was just in time to see it pop down a large rabbit-hole under the hedge." .text .globl main .type main, @function main: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 leaq .LC0(%rip), %rax movq %rax, -8(%rbp) movl $0, %eax popq %rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size main, .-main .ident "GCC: (Debian 12.2.0-14) 12.2.0" .section .note.GNU-stack,"",@progbits

The block of bytes, which comprises the first three paragraphs of Alice’s Adventures in Wonderland, is stored in memory as a string. However, rather than manipulating the entire string, the assembly code merely uses the label .LC0 — in effect, an address — to refer or point to the block of bytes.

The first three letters of leaq stand for “Load Effective Address." In this case, it is loading the address of our block of bytes into RAX, a 64-bit register in the CPU. In this way, RAX stores not the string itself but a memory address that “points to” the massive string.

We can work in the same way with C code by using pointers. These are very similar to labels in assembly language. Simply put, a pointer is the memory address of a variable or data structure, such as a string or an integer or an array. In fact, in the above C code, char *c = ... defines a pointer. This is the purpose of the asterisk — it indicates that c is not a single character or an array of characters, but rather a pointer to such.

To make this more clear, we’ve added output statements to our C program. Using printf, we can print the value of c or we can print c itself, which is a pointer or memory address:

$ cat memory.c #include <stdio.h> int main() { char *c = "CHAPTER I. Down the Rabbit-Hole ... Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, “and what is the use of a book,” thought Alice “without pictures or conversations?” So she was considering in her own mind (as well as she could, for the hot day made her feel very sleepy and stupid), whether the pleasure of making a daisy-chain would be worth the trouble of getting up and picking the daisies, when suddenly a White Rabbit with pink eyes ran close by her. There was nothing so very remarkable in that; nor did Alice think it so very much out of the way to hear the Rabbit say to itself, “Oh dear! Oh dear! I shall be late!” (when she thought it over afterwards, it occurred to her that she ought to have wondered at this, but at the time it all seemed quite natural); but when the Rabbit actually took a watch out of its waistcoat-pocket, and looked at it, and then hurried on, Alice started to her feet, for it flashed across her mind that she had never before seen a rabbit with either a waistcoat-pocket, or a watch to take out of it, and burning with curiosity, she ran across the field after it, and fortunately was just in time to see it pop down a large rabbit-hole under the hedge."; printf("The value of c as an ASCII character: %c \n", *c); printf("The address of this value: %p \n", c); printf("c + 1, the next address: %p \n", c + 1); printf("c + 2: %p \n", c + 2); }

The value of c is the first letter of the string: C. However, when c itself is printed, the result is a memory address in hexadecimal. This is because c is, in fact, a pointer. Here is the output:

The value of c as an ASCII character: C The address of this value: 0x55eb17709008 c + 1, the next address: 0x55eb17709009 c + 2: 0x55eb1770900a

As shown below, c points to the first byte of the string, c + 1 points to the second byte, and so forth. Thus, we can perform “pointer arithmetic” — adding one to a pointer brings us to the next memory cell.

Now, let's say we have the reverse — i.e., not a pointer to a value, but the value itself (a character, a number, etc.). We can obtain the address of the value through the & operator. Here is a summary of the operators:

* Dereference: given a pointer or address, obtain the value stored at the address. & Refer, address, or point to: given a value (e.g. an integer stored in memory), obtain its address.

Q: What is the output of the following, assuming it is wrapped in main()?

Q: How can we print out the entire string above using pointer arithmetic?

int x = 5; printf( "%d \n", x ); printf( "%p \n", &x ); printf( "%d \n", *&x ); printf( "%p \n", &*&x );

Threads

It is easy to confuse threads with programs. As our textbook explains, a program is a set of instructions while a thread is the execution of a program's instructions:

“Even for single-threaded programs, this distinction matters. If a program contains a loop, then a very short program could give rise to a very long thread of execution. Also, running the same program ten times will give rise to ten threads, all executing one program” (p. 21).

Unlike source code, programs, and sets of instructions, “each thread has a lifetime” (p. 21). We can understand this better using a metaphor. If, for example, I will give a speech and I write down my speech on paper beforehand, then the written speech, we may say, is “fixed” or “static” — it does not flow or change.** If we compare this to delivering my speech by reading it aloud to an audience, then the spoken speech is like a process: it has a “lifetime,” it begins and ends, etc. This is analogous to a program on the one hand and a thread which executes the program on the other.

Why use threads? We use them primarily for two reasons:

Reaction
Capacity

Reaction (or “responsiveness”) allows an operating system to react or respond to something that is external, such as a human user or another system on the network, even while the operating system is busy executing other programs. For example, in a drone, one thread can maintain current altitude while another thread accepts and decrypts radio signals from a remote user.

Capacity (or “resource utilization”) allows an operating system to use multiple hardware resources at the same time. For example, while the threads of a virus scanner are busy scanning a hard drive, another thread can perform complex image processing using the CPU or GPU. Here is an illustration from our textbook (p. 31):

As indicated above, concurrency is a key concept — two or more threads can operate at the same time. This may be compared to threads which operate sequentially — i.e., one after another. Concurrency can be very powerful, in part because it saves time.

For now, we will focus on the first item in the list above, reaction. We may think of a video game with graphics that require complex calculations and image processing. Both the CPU and the GPU may be used for these calculations. How, then, can input from the player be accepted and processed? If we can create a thread that waits for and accepts input (e.g. via the keyboard or mouse), then one thread can handle the graphics while another thread handles input.

Below we have a text-based game that employs the same concept, one thread for input, one thread for gameplay:

#include <unistd.h> #include <stdlib.h> /* includes system() */ #include <stdio.h> #include <pthread.h> #include <termios.h> /* function declarations */ void *t_get_key (void *arg); void *t_sleep (void *arg); /* global variables */ /* variables declared outside of main() are global in C */ const int HOLES = 5; int hole1, hole2; char key = 0; int score = 0; float interval = 1000000; int update = 0; /* pthread: POSIX compliant threads */ pthread_t thr_input; pthread_t thr_sleep; /* main */ int main() { char cmd[125]; /* used for Bash commands */ /* use system (stdlib.h) to execute a Bash command */ /* here, we reset the game area by removing all holes; they will be recreated below */ system("rm -r hole*"); /* make new holes */ for (int i = 0; i < HOLES; i++) { sprintf(cmd, "mkdir ./hole%d",i); system(cmd); } /* create two threads: thr_input and thr_sleep */ pthread_create (&thr_input, NULL, t_get_key, NULL); pthread_create (&thr_sleep, NULL, t_sleep, NULL); /* instakey (no enter key required); from StackOverflow at https://t.ly/qbmmS */ static struct termios oldt, newt; tcgetattr( STDIN_FILENO, &oldt); newt = oldt; newt.c_lflag &= ~(ICANON); tcsetattr( STDIN_FILENO, TCSANOW, &newt); while(1) { /* update: a global variable that is set to 1 (or true) if a change has been made in t_sleep */ if (update) { sprintf(cmd, "clear; tree --noreport hole*;echo;echo 'Press to catch, to exit';echo;echo Score: %d", score); system(cmd); update = 0; } /* break out of loop if the x key has been pressed */ if (key == 'x') break; } /* instakey: restore the previous terminal settings */ tcsetattr( STDIN_FILENO, TCSANOW, &oldt); return(0); } /* end main() */ /* thread to accept input from keyboard */ void *t_get_key (void *ptr) { while (1) { key = getchar(); /* if the space key has been pressed, check if Alice's hole is equal to Rabbit's hole; if so, increment score, etc. */ if (key == ' ' && (hole1 == hole2)) { score++; update = 1; interval -= 0.1 * interval; /* if x key pressed, exit via main() */ } else if (key == 'x') { break; } } } /* thread that sleeps for a while, then moves Alice and Rabbit to random holes */ void *t_sleep (void *ptr) { while(1) { /* sleep for [interval] microseconds (there are 1 million microseconds in 1 second) */ usleep(interval); char cmd[125]; /* remove Alice and Rabbit from their current holes */ sprintf(cmd, "rm ./hole%d/Rabbit ./hole%d/Alice",hole1,hole2); system(cmd); /* re-insert Alice and Rabbit in new, random holes */ hole1 = random() % HOLES; sprintf(cmd, "touch ./hole%d/Rabbit",hole1); system(cmd); hole2 = random() % HOLES; sprintf(cmd, "touch ./hole%d/Alice",hole2); system(cmd); /* using a global variable, we indicate to main() that a change has been made so that the screen should be refreshed */ update = 1; } }

The above can be downloaded directly via Bash as follows:

$ wget www.pub22.net/csc425/alice-game.c

Q: How can we modify one of the threads so that every time space is pressed while Alice is not in the same hole as Rabbit, the score decreases and the speed increases?

Threads and Image Processing

Before we discuss how threads can be used to manipulate images, let’s consider a simple animation in the form of a GIF (Graphics Interchange Format) file:

Note that the above is a derivative of a static image, Alice, by Ennya7 — it was modified using Krita, an open-source digital painting tool.

How was the static image converted into an animation? In essence, an animated GIF image is a set of static images, just as the frames of a film comprise a motion picture. In this case, we have five static images, each of which has a different shade of white or yellow. Here are the static images lined up in a row:

When the above images or “frames” are combined into a single image, the effect is an Alice who changes into different shades of yellow, thus giving a ghostly, flickering effect.

There is much more that can be done, however. The above suffices as a simple example to demonstrate the principles of animated images.

Let’s now consider a relatively complex animation. In the following animated GIF image, Alice is imploding along with the moon and sky behind her:

There is a lot of complicated image manipulation going on here, but such manipulation is not too difficult if we use an image processing tool such as ImageMagick. ImageMagick is a suite of powerful tools that give us the ability to perform all kinds of “magic,” including the imploding Alice above. It comes pre-installed on many if not most Linux systems (including MX Linux), and it can be run from Bash using the convert command. For example, the following command was used to convert the five frames of the flickering, ghostly Alice into the animated GIF image:

convert -delay 15 e1.xpm e2.xpm e3.xpm e4.xpm e5.xpm alice-yellow.gif

Let’s now take a look at the code that was used to create the implosion just above:

#include <stdio.h> /* for string operations, printing, etc. */ #include <stdlib.h> /* for system, etc. */ #include <pthread.h> /* POSIX (Portable Operating System Interface [for Unix]) threads */ /* Based in part on https://t.ly/DJ5w2 */ void *modify_img (void *ptr); const int THR_AMT = 85; int main() { pthread_t thread_id[THR_AMT]; int thread_return[THR_AMT]; int thread_arg[THR_AMT];/* the argument that will be passed to each thread’s function, modify_img */ /* Create THR_AMT threads */ for (int i = 0; i < THR_AMT; i++) { thread_arg[i] = i; thread_return[i] = pthread_create( &thread_id[i], NULL, modify_img, (void *) &thread_arg[i]); printf(" Thread %d returns: %d\n", i, thread_return[i]); } /* The following “joins” each newly-created thread to the current thread, i.e. the execution of the current program. * The result is that the current thread will not exit — i.e., the execution of main() will not end — until * all other threads joined to it have ended. See man pthread_join. */ for (int i = 0; i < THR_AMT; i++) pthread_join( thread_id[i], NULL ); /* Use system to interface with Bash and run convert to create the animated GIF file */ system("convert -delay 15 ./implosion-frame0*png ./alice-implode.gif"); return (0); } void *modify_img (void *ptr) { char cmd[125]; int *m = (int *)ptr; /* Convert the argument, ptr, to an integer pointer */ /* Use system to implode a frame of the animation. Each thread runs this command * with a different level of implosion on a single frame. */ sprintf(cmd,"convert -implode %f ./alice-moon.xpm ./implosion-frame%03d.png", *m * 0.025 , *m); printf("Thread %d: %s\n", *m, cmd); system(cmd); }

Here is some of the output of the program above:

Thread 0 returns: 0 Thread 0: convert -implode 0.000000 ./alice-moon.xpm ./implosion-frame000.png Thread 1 returns: 0 Thread 2 returns: 0 Thread 3 returns: 0 Thread 4 returns: 0 Thread 4: convert -implode 0.100000 ./alice-moon.xpm ./implosion-frame004.png Thread 2: convert -implode 0.050000 ./alice-moon.xpm ./implosion-frame002.png Thread 3: convert -implode 0.075000 ./alice-moon.xpm ./implosion-frame003.png Thread 5 returns: 0 Thread 6 returns: 0 Thread 7 returns: 0 Thread 8 returns: 0 Thread 9 returns: 0 Thread 10 returns: 0 ...

Try this yourself in a working directory with the following:

$ wget www.pub22.net/csc425/alice-moon.xpm
$ wget www.pub22.net/csc425/implode-alice.c
$ gcc implode-alice.c
$ ./a.out

Here are just a few things you can do with ImageMagick; you may wish to experiment with these and other commands:

Convert to charcoal drawing: convert -charcoal 2 alice.png alice-charcoal.png Specify number of colors in image (reduces file size): convert -colors 2 alice.png alice-reduced-colors.png Blur: convert -blur 0x8 alice.png alice-blurred.png Change light levels: convert -auto-level alice.png alice-levels.png Change B+W threshold: convert -black-threshold 50% alice.png alice-threshold.png Convert to XPM: convert alice.png alice-bitmap.xpm

Thread Synchronization

When we have multiple threads accessing or changing the same data, corruption can occur. The data may be misread or changed at the wrong time, for example. Here is a C program that illustrates this:

#include <pthread.h> #include <fcntl.h> #include <unistd.h> void *read_txt(); void *write_txt(); const char START = 2; /* ASCII STX: Start of Text */ const char END = 3; /* ASCII ETX: End of Text */ char g_byte = START; /* a global variable accessed by all threads */ int main() { pthread_t thr_read; pthread_t thr_write; int thread_return; /* create thread for reading and exit if error */ thread_return = pthread_create(&thr_read, NULL, read_txt, NULL); if (thread_return != 0) return(thread_return); /* create thread for writing and exit if error */ thread_return = pthread_create(&thr_write, NULL, write_txt, NULL); if (thread_return != 0) return(thread_return); /* Join each newly-created thread to the current thread */ pthread_join(thr_read, NULL); pthread_join(thr_write, NULL); return (0); } /* Read from the source file one byte at a time */ void *read_txt() { int fd; int bytes_read; fd = open("./alice-ch1.txt", O_RDONLY); while (1) { bytes_read = read(fd, &g_byte, 1); if (!bytes_read) { g_byte = END; break; } } close(fd); pthread_exit(NULL); /* A clean way to terminate a thread */ } /* Write a copy of the source file one byte at a time */ void *write_txt() { int fd; fd = open("./copy.txt", O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR); while(1) { if (g_byte == END) break; else { write(fd, &g_byte, 1); } } fsync(fd); close(fd); pthread_exit(NULL); }

Source: http://www.pub22.net/csc425/reader-writer-flawed.c

Compare the original file (the file that is being read) with the corrupted copy:

Original
Copy

What happened? The problem is that thr_read and thr_write are not synchronized. More specifically, sometimes the reader is faster than the writer, and the latter omits some of the characters. Sometimes we have the reverse: the writer is faster than the reader, and the same character is repeated. The result is not a copy but a corrupted version of the original.

Given the above, thread synchronization is key. Here is how we can redesign the above program so that the reader thread and the writer thread operate in unison:

#include <pthread.h> #include <fcntl.h> #include <unistd.h> void *read_txt(); void *write_txt(); const char START = 2; /* ASCII STX: Start of Text */ const char END = 3; /* ASCII ETX: End of Text */ const char ACK = 6; /* ASCII ACK: Acknowledge */ char g_byte = START; /* a global variable accessed by all threads */ int main() { pthread_t thr_read; pthread_t thr_write; int thread_return; /* create thread for reading and exit if error */ thread_return = pthread_create(&thr_read, NULL, read_txt, NULL); if (thread_return != 0) return(thread_return); /* create thread for writing and exit if error */ thread_return = pthread_create(&thr_write, NULL, write_txt, NULL); if (thread_return != 0) return(thread_return); /* Join each newly-created thread to the current thread */ pthread_join(thr_read, NULL); pthread_join(thr_write, NULL); return (0); } /* Read from the source file one byte at a time */ void *read_txt() { int fd; int bytes_read; fd = open("./alice-ch1.txt", O_RDONLY); while (1) { if (g_byte == ACK) { bytes_read = read(fd, &g_byte, 1); if (!bytes_read) { g_byte = END; break; } } } close(fd); pthread_exit(NULL); /* A clean way to terminate a thread */ } /* Write a copy of the source file one byte at a time */ void *write_txt() { int fd; fd = open("./copy.txt", O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR); while(1) { if (g_byte != ACK) { if (g_byte == END) break; else { write(fd, &g_byte, 1); g_byte = ACK; } } } fsync(fd); close(fd); pthread_exit(NULL); }

Source: http://www.pub22.net/csc425/reader-writer-corrected.c

In the program above, whenever a byte is written, the writer thread will set the global variable to ACK — i.e., it “acknowledges” that a byte has been written — thus, the reader thread can then read in a new byte and the process repeats. Without the acknowledgment, the reader thread will simply wait. This prevents the corruption described above.

Let’s now apply synchronized threads to an ASCII art image:

Black Widow ASCII Image

The following inverts the image using synchronized threads:

#include <pthread.h> #include <fcntl.h> #include <unistd.h> void *read_txt(); void *write_txt(); const char START = 2; /* ASCII STX: Start of Text */ const char END = 3; /* ASCII ETX: End of Text */ const char ACK = 6; /* ASCII ACK: Acknowledge */ char g_byte = START; /* a global variable accessed by all threads */ int main() { pthread_t thr_read; pthread_t thr_write; int thread_return; /* create thread for reading and exit if error */ thread_return = pthread_create(&thr_read, NULL, read_txt, NULL); if (thread_return != 0) return(thread_return); /* create thread for writing and exit if error */ thread_return = pthread_create(&thr_write, NULL, write_txt, NULL); if (thread_return != 0) return(thread_return); /* Join each newly-created thread to the current thread */ pthread_join(thr_read, NULL); pthread_join(thr_write, NULL); return (0); } /* Read from the source file one byte at a time */ void *read_txt() { int fd; int bytes_read; fd = open("./black-widow-haunted-past.txt", O_RDONLY); while (1) { if (g_byte == ACK) { bytes_read = read(fd, &g_byte, 1); if (!bytes_read) { g_byte = END; break; } } } close(fd); pthread_exit(NULL); /* A clean way to terminate a thread */ } /* Invert the image */ void *write_txt() { int fd; char black = ' '; char dot = '.'; fd = open("./black-widow-haunted-past-inverted.txt", O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR); while(1) { if (g_byte != ACK) { if (g_byte == END) break; else { if (g_byte == black) write(fd, &dot, 1); else if (g_byte == dot) write(fd, &black, 1); else write(fd, &g_byte, 1); g_byte = ACK; } } } fsync(fd); close(fd); pthread_exit(NULL); }

Source: http://www.pub22.net/csc425/black-widow.c

Here is the output:

Inverted Black Widow ASCII Image

Lack of Synchronization

In Chapter 4, our textbook states:

“When two or more threads operate on a shared data structure, some very strange malfunctions can occur if the timing of the threads turns out precisely so that they interfere with one another.” (Hailperin Section 4.2)

This is only part of the story. There may not be interference per se between threads — though this is often the case — but lack of coordination. Each thread may operate as it should without interference from other threads, but if the threads do not operate at the right times in relation to each other, corruption or failure can occur. We saw this in the first version of the threaded reader-writer program above.

Before we discuss this further, note well: lack of synchronization can have dreadful consequences. Hailperin uses a vivid and notorious example from medical science to bring home the point:

“... inconsistency [of race conditions] may not sound so terrible, but what if a similar inconsistency occurred in a medical setting, and one variable recorded the drug to administer, while the other recorded the dose? Can you see how dangerous an inconsistency could be? Something very much like that happened in a radiation therapy machine, the Therac-25, with occasionally lethal consequences. (Worse, some patients suffered terrible but not immediately lethal injuries and lingered for some time in excruciating, intractable pain.) (Hailperin Section 4.2)

Remember that science adds to the chaos — death and destruction are its twin sisters (see Ethics above). In some cases, the damage done by science and technology is deliberate (consider ENIAC and the hydrogen bomb); often, however, harm is a consequence of incompetence, as in this case. All too often, the profit motive and avarice result in cutting corners — to a large extent, medical science is a lucrative business, as is war.

Race Conditions, Mutexes, and Monitors

Races between threads can occur when two threads use the same data without any means of ensuring that one and only one thread uses the data at any given moment. In the reader-writer example, we saw that when the reader and writer threads have access to g_byte at the same time, data corruption occurs. Essentially, the problem is that the two threads do not co-operate; i.e., they are not synchronized.

The corrected version of the program is an example of synchronized threads that use a simple mechanism for preventing races. By means of ASCII — originally designed as a communications code — one thread has exclusive access to the data structure (in this case, a single byte) at any given moment. When the reader is reading a new byte and modifying g_byte, the writer waits. When the writer is accessing g_byte and writing, the reader waits.

We may say that g_byte is “locked” by the reader thread when it has exclusive access to it — i.e., the writer thread is locked out and prevented from accessing g_byte while the reader has access to it. In other words, the reader “holds” g_byte when it has exclusive access to it. This is called a mutual exclusion lock, or mutex for short.

In POSIX, we have built-in mechanisms for incorporating mutexes into C programs. We will illustrate the usefulness of POSIX mutexes with the following. Let’s say we wish to produce something akin to a triangle, as so:

Let’s also assume that we wish to use two threads to perform this task more quickly (we may imagine a much greater amount of output, but we will use a very simple example in this case for clarity). In the following C program, the two writer threads will work simultaneously to produce rows of the triangular shape using a global variable, g_counter:

#include <unistd.h> #include <fcntl.h> #include <pthread.h> pthread_t thr_writer1; pthread_t thr_writer2; int g_counter = 0; const int dot = 46; /* ASCII code for period */ const int newline = 10; /* ASCII code for new line */ void *print_dots() { while (g_counter < 25) { g_counter++; for (int i = 0; i < g_counter; i++) write(STDOUT_FILENO, &dot, 1); write(STDOUT_FILENO, &newline, 1); } pthread_exit(NULL); } int main(void) { int thread_return; thread_return = pthread_create(&thr_writer1, NULL, print_dots, NULL); if (thread_return != 0) return(thread_return); thread_return = pthread_create(&thr_writer2, NULL, print_dots, NULL); if (thread_return != 0) return(thread_return); pthread_join(thr_writer1, NULL); pthread_join(thr_writer2, NULL); return 0; }

Source: http://www.pub22.net/csc425/triangle-flawed.c

Here is the output after running the program three times. In the second case, the output is, in fact, correct — this makes the problem all the more misleading. Often, race conditions do produce the expected results, and this can make debugging very difficult.

. .. ... .... ..... ...... ....... ........ ......... .......... ........... .................... .............. ............... ................ ................. .................. ................... .................... ..................... ...................... ....................... ........................ ......................... .................. . .. ... .... ..... ...... ....... ........ ......... .......... ........... ............ ............. .............. ............... ................ ................. .................. ................... .................... ..................... ...................... ....................... ........................ ......................... . .. ... .... ..... ...... ....... ........ ......... .......... ........... ............ ............. .............. ............... ................ ................. .................. ................... .......................... .................................... ........ ........................................ .......... ....................

We can solve the problem above by using POSIX mutexes, as follows:

#include <unistd.h> #include <fcntl.h> #include <pthread.h> pthread_t thr_writer1; pthread_t thr_writer2; pthread_mutex_t mtx_lock; int g_counter = 0; const int dot = 46; /* ASCII code for period */ const int newline = 10; /* ASCII code for new line */ void *print_dots() { pthread_mutex_lock(&mtx_lock); while (g_counter < 25) { g_counter++; for (int i = 0; i < g_counter; i++) write(STDOUT_FILENO, &dot, 1); write(STDOUT_FILENO, &newline, 1); } pthread_mutex_unlock(&mtx_lock); pthread_exit(NULL); } int main(void) { int thread_return; if (pthread_mutex_init(&mtx_lock, NULL) != 0) return(1); thread_return = pthread_create(&thr_writer1, NULL, print_dots, NULL); if (thread_return != 0) return(thread_return); thread_return = pthread_create(&thr_writer2, NULL, print_dots, NULL); if (thread_return != 0) return(thread_return); pthread_join(thr_writer1, NULL); pthread_join(thr_writer2, NULL); pthread_mutex_destroy(&mtx_lock); return 0; }

Source: http://www.pub22.net/csc425/triangle-mutex.c

With the above program, through the magic of mutexes we consistently get the right output — we are fighting chaos rather than feeding it.

In object-oriented languages, we have a special implementation of mutexes known as monitors. Monitors are mutexes that obey the following three rules, as stated in our textbook:

All state variables within an object should be kept private, accessible only to code associated with that object.

Every object (that might be shared between threads) should contain a mutex as an additional field ...

Every method of an object (except private ones used internally) should start by locking that object’s mutex and end by unlocking the mutex immediately before returning ... (Hailperin 4.3.2)

We should note that in addition to mutexes and monitors, semaphores are also widely used. However, we should keep in mind the following:

For most purposes, semaphores are less natural [than mutexes and monitors], resulting in more error-prone code. In those applications where they are natural ... they result in very succinct, clear code. That is probably not the main reason for their continued use, however. Instead, they seem to be hanging on largely out of historical inertia, having gotten a seven- to nine-year head start over monitors. (Semaphores date to 1965, as opposed to the early 1970s for monitors.) (Hailperin Section 4.6)

Thread Efficiency

It is easy to assume that threads add speed: the more threads we have, the faster our program. However, all too often threads do not increase but decrease efficiency and speed. In many cases the decrease is caused by thread overhead. It takes time to create, maintain, and coordinate threads. Many of the above programs would operate faster without threads — aside from their educational purpose these programs have little practical value.

There is an interesting discussion about thread slowdown here. These remarks in particular bear repeating:

... Imagine you have a corridor that you can fit four people down, side by side. You want to move all the rubbish at one end, to the other end. The most efficient number of people is 4.

If you have 1-3 people then you’re missing out on using some corridor space. If you have 5 or more people, then at least one of those people is basically stuck queueing behind another person all the time. Adding more and more people just clogs up the corridor, it doesn’t speed up the activity. (EightBitTony at StackOverflow)

Simply put, too many cooks in the kitchen spoil the stew. More is not always better.

Nonetheless, there are situations where threads can indeed produce a noticeable speedup. The following program, which uses three threads to produce three animations, is significantly faster than the equivalent program that does not use threads.

#include <unistd.h> #include <fcntl.h> #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <string.h> pthread_t thr_1; pthread_t thr_2; pthread_t thr_3; const int amt = 25; void *mod0() { char cmd[125]; for (int i = 0; i < amt * 4; i++) { sprintf(cmd, "convert -swirl %d ./bw.png /tmp/swirl%03d.png", i*6, i); system(cmd); sprintf(cmd, "convert -composite ./sky.png /tmp/swirl%03d.png /tmp/swirl%03d.png", i, i); system(cmd); } system("convert -delay 15 -dispose previous /tmp/swirl* bw-swirl.gif"); pthread_exit(NULL); } void *mod1() { char cmd[125]; for (int i = 0; i < amt * 2; i++) { sprintf(cmd, "convert -implode %f ./bw.png /tmp/implode%03d.png", (i+0.3)*0.07, i); system(cmd); sprintf(cmd, "convert -composite ./sky.png /tmp/implode%03d.png /tmp/implode%03d.png", i, i); system(cmd); } system("convert -delay 15 -dispose previous /tmp/implode* bw-implode.gif"); pthread_exit(NULL); } void *mod2() { char cmd[125]; for (int i = 0; i < amt * 3; i++) { sprintf(cmd, "convert -background 'rgba(0,0,0,0)' -rotate %d ./bw-norope.png /tmp/rotate%03d.png", i*5, i); system(cmd); sprintf(cmd, "convert -composite ./sky.png /tmp/rotate%03d.png /tmp/rotate%03d.png", i, i); system(cmd); } system("convert -delay 15 -dispose previous /tmp/rotate* bw-rotate.gif"); pthread_exit(NULL); } int main(void) { int thread_return; system("rm /tmp/*png"); thread_return = pthread_create(&thr_1, NULL, mod0, NULL); if (thread_return != 0) return(thread_return); thread_return = pthread_create(&thr_2, NULL, mod1, NULL); if (thread_return != 0) return(thread_return); thread_return = pthread_create(&thr_3, NULL, mod2, NULL); if (thread_return != 0) return(thread_return); pthread_join(thr_1, NULL); pthread_join(thr_2, NULL); pthread_join(thr_3, NULL); return 0; }

Source files:
http://www.pub22.net/csc425/thread-modify-img.c
http://www.pub22.net/csc425/bw.png
http://www.pub22.net/csc425/sky.png

Here is the original image — a derivative of the 1970s-era Black Widow — that is animated using ImageMagick:

The output comprises the following set of animated GIF images, each of which is merged with a starry sky background:

Here is how the threaded program compares with the equivalent non-threaded program:

$ gcc -Wall thread-modify.c ; time ./a.out ; ls -l *gif real 1m34.077s user 1m48.456s sys 0m36.419s -rw-r--r-- 1 demo demo 1624580 Mar 23 19:39 bw-implode.gif -rw-r--r-- 1 demo demo 3175955 Mar 23 19:39 bw-rotate.gif -rw-r--r-- 1 demo demo 5286641 Mar 23 19:39 bw-swirl.gif demo@mx1:~/lab/c/threads/black-widow-colors/thread-speed-test $ gcc -Wall nothread-modify.c ; time ./a.out ; ls -l *gif real 2m8.942s user 1m44.468s sys 0m30.199s -rw-r--r-- 1 demo demo 1624580 Mar 23 19:41 bw-implode.gif -rw-r--r-- 1 demo demo 3175955 Mar 23 19:42 bw-rotate.gif -rw-r--r-- 1 demo demo 5286641 Mar 23 19:40 bw-swirl.gif

If we add printf statements to each of the above programs we can see how the threads of the faster program are interwoven:

Threaded Program Output
Non-threaded Program Output

Deadlocks

Previously we discussed one of the drawbacks of threads: slowdown caused by thread overhead. There is another, equally nefarious, drawback: deadlock. In fact, deadlock is pernicious: in many ways, it is more difficult to detect than your typical bug. A program may run perfectly well for quite some time before a deadlock occurs.

But what, precisely, is deadlock? Like so many other things in computer science, deadlock is a reflection of realities that are part of the human condition. Here is an example that many if not most of us have experienced:

Antonio sends a letter to his long lost friend from childhood, Natasha. Due to the cryptic nature of his message, Natasha is hesitant and puzzled, and does not know how to reply. She makes several attempts to write a response, but no matter what she writes, she is plagued by self-doubt. After writing a series of drafts, she gives up, and decides to wait for a follow-up from Antonio. “Perhaps his next letter, if indeed he writes one, will set things straight,” she muses to herself.

Antonio, however, continues to wait for a reply from Natasha. He considers writing a follow-up — after all, perhaps Natasha, through some unfortunate set of circumstances, never received his letter to begin with. Yet, he too is plagued by doubt. After all, it is unlikely that Natasha did not, in fact, receive his letter, and sending a second letter may give Natasha the wrong impression. He decides to wait. “Perhaps Natasha just needs time to think,” he tells himself.

And so, both parties play a waiting game of sorts, each hoping for a message from the other.

How many of us have not experienced something like the above?

“Good things come to those who wait” — there is much truth in this adage. However, this does not apply to operating systems, and we need to find ways of avoiding deadlocks, or ending them when they occur.

Types of Deadlocks

There are many types of deadlocks, and these types can be divided into the following “families”:

Producer-Consumer Reader-Writer No-Starve Mutex Dining Philosophers Cigarette Smokers

The above list was taken from Chapter 4 of The Little Book of Semaphores, which provides detailed descriptions and solutions to each problem. Below we will discuss two.

The Dining Philosophers problem is a classic in computer science. Invented by Dijkstra in 1965, it shows how cycles can produce deadlocks. Consider the following diagram:

Above, each "philosopher" is represented by five threads, T0 ... T4. Each philosopher or thread can do its work only when it “holds” both of the "forks" to its left and right. The following quote from page 87 of The Little Book of Semaphores lists the constraints of the Dining Philosophers problem:

• Only one philosopher can hold a fork at a time [mutual exclusion]. • It must be impossible for a deadlock to occur [this is key]. • It must be impossible for a philosopher to starve waiting for a fork [all threads must operate]. • It must be possible for more than one philosopher to eat at the same time [insure concurrency].

The question is, how can we satisfy all of the above? First, we need to know precisely how deadlock can occur. Here is a C program that shows how deadlocks can result from the problem described above. We have abstracted the problem — "philosophers" are threads and "forks" are items — for various reasons. Note that the following program also includes a solution:

#include <unistd.h> #include <stdio.h> #include <stdlib.h> #include <pthread.h> const int THR_AMT = 5; const int MAX_TURNS = 550; const int DEADLOCK = 0; pthread_mutex_t mtx_lock; /* Below, *I* is an array representing five items ("forks"): whenever a thread * ("a philosopher") locks an item, we set the index of I to the thread ID. * For example, if Thread 1 uses Items 1 and 2, then I[1] = 1 and I[2] = 1. * The value -1 indicates that no thread has locked the item. */ char I[5] = {-1,-1,-1,-1,-1}; /* Here, *usage* stores the total turns of item pair usage by each thread. As per * the classic problem, we assume that both adjacent items must be locked by a * thread before they can be "used." */ int usage[5] = {0,0,0,0,0}; int turn = 0; void print_headings() { printf("\n────────────"); printf("\nTurn Items"); printf("\n 01234\n\n"); } void print_status() { /* What follows is a locked area: the mutex prevents race conditions with * the variable *turn* and insures against the risk of corrupted output. */ pthread_mutex_lock(&mtx_lock); if (turn < MAX_TURNS) { if (turn % 25 == 0) print_headings(); printf("%4d ",turn); for (int i = 0; i < 5; i++) { if (I[i] != -1) { printf("%d",I[i]); } else { printf("."); } } printf("\n"); turn++; } pthread_mutex_unlock(&mtx_lock); } void *get_resources(void *ptr) { int *thread_id = (int *)ptr; /* Here we get the addresses of the current thread's adjacent items * (i.e., the "right" and "left" "forks.") */ char *right = &I[*thread_id]; char *left = &I[(*thread_id + 1) % 5]; /* The following is our core logic. * Set DEADLOCK to 1 to see how the classic problem results in deadlock. * Set DEADLOCK to 0 to see a solution using random numbers. */ while (turn < MAX_TURNS) { usleep(25000); /* A philosopher "thinking" */ if (DEADLOCK) { /* lock items if possible */ if (*right == -1) *right= *thread_id; if (*left == -1) *left = *thread_id; if ((*right == *thread_id) && (*right == *left)) { /* use items */ usleep(25000); usage[*thread_id]++; /* unlock items */ *right = -1; *left = -1; } print_status(); } /* Below, if a random number from 0-4 equals the current thread ID, * the current thread will unlock whatever items it holds, if any. * Otherwise, adjacent items are locked and held, if possible. */ if (!DEADLOCK) { if (rand() % 5 == *thread_id) { if (*right == *thread_id) *right = -1; if (*left == *thread_id) *left = -1; } else { if (*right == -1) *right= *thread_id; if (*left == -1) *left = *thread_id; } if ((*right == *thread_id) && (*right == *left)) { print_status(); /* use items */ usleep(25000); usage[*thread_id]++; /* unlock items */ *right = -1; *left = -1; } } } /* A clean exit */ pthread_exit(NULL); } int main(void) { int thread_return; int thread_arg[THR_AMT]; pthread_t T[THR_AMT]; for (int i = 0; i < THR_AMT; i++) { thread_arg[i] = i; thread_return = pthread_create(&T[i], NULL, get_resources, (void *) &thread_arg[i]); if (thread_return != 0) return(thread_return); } for (int i = 0; i < THR_AMT; i++) pthread_join(T[i], NULL); /* Print summary of thread usage using the variable *usage*: */ printf("\n"); for (int i = 0; i < THR_AMT; i++) printf("Thread %d total turns of usage: %d\n", i, usage[i]); return 0; }

Source: dining-philosophers.c

The output produced by the above:

Without randomness (DEADLOCK = 1)
With randomness (DEADLOCK = 0)

With deadlock, output ends in the following cycle (each thread locks the item to its "right"):

... ──────────── Turn Items 01234 525 01234 526 01234 527 01234 528 01234 529 01234 530 01234 531 01234 532 01234 533 01234 534 01234 535 01234 536 01234 537 01234 538 01234 539 01234 540 01234 541 01234 542 01234 543 01234 544 01234 545 01234 546 01234 547 01234 548 01234 549 01234 Thread 0 total turns of usage: 6 Thread 1 total turns of usage: 7 Thread 2 total turns of usage: 6 Thread 3 total turns of usage: 6 Thread 4 total turns of usage: 6

With the solution, however, the output ends like this:

... ──────────── Turn Items 01234 525 00233 526 0022. 527 41.33 528 41133 529 411.4 530 40224 531 .0.33 532 00.33 533 ...33 534 00.33 535 4.124 536 41124 537 00.33 538 00.33 539 ..22. 540 4.224 541 .11.. 542 01133 543 00... 544 4.134 545 .0.33 546 00.33 547 4.1.4 548 411.4 549 00... Thread 0 total turns of usage: 107 Thread 1 total turns of usage: 115 Thread 2 total turns of usage: 105 Thread 3 total turns of usage: 113 Thread 4 total turns of usage: 111

Note how the solution relies on randomness — chance — to break the deadlock. This method often works outside of computer science as well.

Here is another example of a deadlock problem, this time with a program that has practical value — it generates three-panel stories using a combination of Bash and C. Below, the writer and reader threads both need access to LINES, an array of random line numbers that is needed to produce the text of each panel. Deadlock can easily occur.

#include <unistd.h> #include <stdlib.h> #include <fcntl.h> #include <pthread.h> #include <stdio.h> #include <time.h> #define DEADLOCK 0 #define IMAGE_AMOUNT 25 #define WAITING 0 #define WORKING 1 #define FINISHED 2 pthread_t thr_1; pthread_t thr_2; int lines_index = 0; int s; /* semaphore */ int s_writer_init = 5; /* semaphore initial value for writer thread */ int s_reader_init = 15; /* semaphore initial value for reader thread */ int LINES[IMAGE_AMOUNT]; char reader_status = WAITING; pthread_mutex_t mtx_lock; void thread_report(int thread) { if (!thread) printf("Writer: LINES: "); else printf("Reader: LINES: "); for (int i = 0; i < lines_index; i++) printf("."); printf("\n"); } void *writer() { while (reader_status != FINISHED) { if (reader_status != WORKING) { pthread_mutex_lock(&mtx_lock); s = s_writer_init; while (1) { if (!DEADLOCK) /* Here, s acts as a semaphore. Every time we loop within the mutex, the semaphore * decrements by 1. When s is zero, we break out of the loop, the lock is released, * and now the reader thread has an opportunity to access LINES, etc. */ if (--s == 0) { break; reader_status = WORKING; } if (lines_index < IMAGE_AMOUNT) { LINES[lines_index++] = rand() % 2055; thread_report(0); } } pthread_mutex_unlock(&mtx_lock); } } printf("Writer done.\n"); pthread_exit(NULL); } void make_img(int line, int panel) { char cmd[250]; sprintf(cmd,"bash ./addtext.sh %d %d", panel, line); printf("Reader: %s\n", cmd); system(cmd); } void *reader() { int img_id = 0; int images_generated = 0; while (images_generated < IMAGE_AMOUNT) { reader_status = WORKING; pthread_mutex_lock(&mtx_lock); s = s_reader_init; while (1) { if (!DEADLOCK) if (--s == 0) { reader_status = WAITING; break; } if (lines_index > 0 && images_generated++ < IMAGE_AMOUNT) { thread_report(1); make_img(LINES[--lines_index], img_id++); } } pthread_mutex_unlock(&mtx_lock); } reader_status = FINISHED; printf("Reader done.\n"); pthread_exit(NULL); } int main(void) { int thread_return; int mutex_return; char cmd[250]; /* Seed the random number generator with time. */ srand(time(NULL)); mutex_return = pthread_mutex_init(&mtx_lock, NULL); if (mutex_return) { printf("Mutex init error: %d\n", mutex_return); return(1); } thread_return = pthread_create(&thr_1, NULL, writer, NULL); if (thread_return != 0) return(thread_return); thread_return = pthread_create(&thr_2, NULL, reader, NULL); if (thread_return != 0) return(thread_return); pthread_join(thr_1, NULL); pthread_join(thr_2, NULL); pthread_mutex_destroy(&mtx_lock); /* Combine panel images into stories: */ for (int panel = 0; panel < IMAGE_AMOUNT; panel++) { if (panel > 2 && panel % 3 == 0) { sprintf(cmd,"convert /tmp/panel%d.png /tmp/panel%d.png /tmp/panel%d.png +append /tmp/story%d.png", panel-2, panel-1, panel, panel / 3); printf("cmd: %s\n", cmd); system(cmd); } } system("mkdir -p ./stories"); system("cp /tmp/story*png ./stories"); printf("Done.\n"); return 0; }

Updated 4/3/24

Sources:
story-semaphore-read-write.c
addtext.sh
phrases.txt [Source: A Polyglot of Foreign Proverbs by Henry G. Bohn (1857)]
barbie0.png
barbie1.png
barbie2.png
barbie3.png
barbie4.png

When DEADLOCK is set to 1 (i.e., when semaphores are not used), the writer thread locks LINES to do its work, but never releases its hold — the reader thread never has an opportunity to read LINES and create the images. By using a semaphore, the writer thread eventually releases its hold on LINES, and the reader thread can do its work.

Quite a few stories are generated when deadlock is prevented; here are a few of the more interesting ones, each of which conveys a useful (albeit cryptic) message:

Always remember: art, philosophy and religion have the highest value for us — science is their handmaiden.

Memory

We begin this section of the course with a seminal passage from ancient philosophy. The source of this passage is Plato’s dialogue Phaedrus (c. 370 BC) — here, Socrates describes an Egyptian invention — “γράμματα” — that underlies everything we do in computer science:

Σωκράτης:
ἤκουσα τοίνυν περὶ Ναύκρατιν τῆς Αἰγύπτου γενέσθαι τῶν ἐκεῖ παλαιῶν τινα θεῶν, οὗ καὶ τὸ ὄρνεον ἱερὸν ὃ δὴ καλοῦσιν Ἶβιν: αὐτῷ δὲ ὄνομα τῷ δαίμονι εἶναι Θεύθ. τοῦτον δὴ πρῶτον ἀριθμόν τε καὶ λογισμὸν εὑρεῖν καὶ γεωμετρίαν καὶ ἀστρονομίαν, ἔτι δὲ πεττείας τε καὶ κυβείας, καὶ δὴ καὶ γράμματα. βασιλέως δ' αὖ τότε ὄντος Αἰγύπτου ὅλης Θαμοῦ περὶ τὴν μεγάλην πόλιν τοῦ ἄνω τόπου ἣν οἱ Ἕλληνες Αἰγυπτίας Θήβας καλοῦσι, καὶ τὸν θεὸν Ἄμμωνα, παρὰ τοῦτον ἐλθὼν ὁ Θεὺθ τὰς τέχνας ἐπέδειξεν, καὶ ἔφη δεῖν διαδοθῆναι τοῖς ἄλλοις Αἰγυπτίοις: ὁ δὲ ἤρετο ἥντινα ἑκάστη ἔχοι ὠφελίαν, διεξιόντος δέ, ὅτι καλῶς ἢ μὴ καλῶς δοκοῖ λέγειν, τὸ μὲν ἔψεγεν, τὸ δ' ἐπῄνει. πολλὰ μὲν δὴ περὶ ἑκάστης τῆς τέχνης ἐπ' ἀμφότερα Θαμοῦν τῷ Θεὺθ λέγεται ἀποφήνασθαι, ἃ λόγος πολὺς ἂν εἴη διελθεῖν: ἐπειδὴ δὲ ἐπὶ τοῖς γράμμασιν ἦν, “τοῦτο δέ, ὦ βασιλεῦ, τὸ μάθημα,” ἔφη ὁ Θεύθ, “σοφωτέρους Αἰγυπτίους καὶ μνημονικωτέρους παρέξει: μνήμης τε γὰρ καὶ σοφίας φάρμακον ηὑρέθη.”

ὁ δ' εἶπεν: “ὦ τεχνικώτατε Θεύθ, ἄλλος μὲν τεκεῖν δυνατὸς τὰ τέχνης, ἄλλος δὲ κρῖναι τίν' ἔχει μοῖραν βλάβης τε καὶ ὠφελίας τοῖς μέλλουσι χρῆσθαι: καὶ νῦν σύ, πατὴρ ὢν γραμμάτων, δι' εὔνοιαν τοὐναντίον εἶπες ἢ δύναται. τοῦτο γὰρ τῶν μαθόντων λήθην μὲν ἐν ψυχαῖς παρέξει μνήμης ἀμελετησίᾳ, ἅτε διὰ πίστιν γραφῆς ἔξωθεν ὑπ' ἀλλοτρίων τύπων, οὐκ ἔνδοθεν αὐτοὺς ὑφ' αὑτῶν ἀναμιμνῃσκομένους: οὔκουν μνήμης ἀλλὰ ὑπομνήσεως φάρμακον ηὗρες. σοφίας δὲ τοῖς μαθηταῖς δόξαν, οὐκ ἀλήθειαν πορίζεις: πολυήκοοι γάρ σοι γενόμενοι ἄνευ διδαχῆς πολυγνώμονες εἶναι δόξουσιν, ἀγνώμονες ὡς ἐπὶ τὸ πλῆθος ὄντες, καὶ χαλεποὶ συνεῖναι, δοξόσοφοι γεγονότες ἀντὶ σοφῶν.” Socrates:
I heard, then, that at Naucratis, in Egypt, was one of the ancient gods of that country, the one whose sacred bird is called the ibis, and the name of the god himself was Theuth. He it was who invented numbers and arithmetic and geometry and astronomy, also draughts and dice, and, most important of all, writing. Now the king of all Egypt at that time was the god Thamus, who lived in the great city of the upper region, which the Greeks call the Egyptian Thebes, and they call the god himself Ammon. To him came Theuth to show his inventions, saying that they ought to be imparted to the other Egyptians. But Thamus asked what use there was in each, and as Theuth enumerated their uses, expressed praise or blame, according as he approved or disapproved. The story goes that Thamus said many things to Theuth in praise or blame of the various arts, which it would take too long to repeat; but when they came to writing, “This invention, O king,” said Theuth, “will make the Egyptians wiser and will improve their memories; for it is an elixir of memory and wisdom that I have discovered.”

But Thamus replied, “Most ingenious Theuth, one man has the ability to beget arts, but the ability to judge of their usefulness or harmfulness to their users belongs to another; and now you, who are the father of writing, have been led by your affection to ascribe to written words a power the opposite of that which they really possess. For this invention will produce forgetfulness in the minds of those who learn to use it, because they will not practice their memory. Their trust in writing, produced by external characters which are no part of themselves, will discourage the use of their own memory within them. You have invented an elixir not of memory, but of reminding; and you offer your pupils the appearance of wisdom, not true wisdom, for they will read many things without instruction and will therefore seem to know many things, when they are for the most part ignorant and hard to get along with, since they are not wise, but only appear wise.

The key points of the above are the following:

Africa and the Near East are, as they say, the “cradle of civilization.” Writing, which was invented not only in Egypt but Mesopotamia — the area between the Tigris and Euphrates — is but one example. In many ways, the Egyptians laid the foundation of Western philosophy and science. Plato certainly recognized this, though we moderns easily forget.
Writing, like so many other inventions, originally served a religious purpose (see the introduction above). In fact, the Ancient Greek word for hieroglyphics, ἱερογλυφικὰ, translates as “sacred carvings” — divine words written into stone. Modern writing is but a pale shadow of something we once had.
Even in the time of Socrates and Plato, however, writing was considered to be a double-edged sword: the passage from the Phaedrus quoted above describes writing as φάρμακος — poison or sorcery. It is only a semblance of memory and knowledge. It can lead us astray if we are not careful.

The discoveries of ancient Egypt — though often overlooked — have laid the groundwork for modern science and mathematics. I would not be writing these words, and you would not be reading them, without these discoveries. Yet — and this is crucial — we should consider the possibility that writing is, as Socrates argues in the Phaedrus, a “false” kind of memory. Writing is a simulation of memory, just as computation (including so-called “AI”) is a simulation of thought. Memory, like thought, is alive — it is not a human invention but the opposite: it is something that makes invention possible.

With the above in mind, we conclude that memory in its true form serves a religious and philosophical purpose. Information stored in RAM and other physical media is not real memory, it is only a simulation.

However, even simulations can be powerful and beneficial, so long as we do not forget what they really are. Regardless, as explained below, in computer science we make a distinction between “virtual memory” and “physical memory.” Even the latter is not memory in the true sense of the word. The distinction is useful but artificial.

What, then, is virtual memory, and what is its purpose? Hailperin answers these questions as follows:

The essence of virtual memory is to decouple the addresses that running programs use to identify objects from the addresses that the [physical] memory uses to identify storage locations. The former are known as virtual addresses and the latter as physical addresses (p. 229).

We should keep in mind that “objects” should be understood as data structures — after all, C and many other languages are not inherently object-oriented: they are more primitive and hence more powerful for precisely this reason.

Ultimately, as mentioned before, we are simply dealing with voltage levels in CMOS transistors — “on” and “off" as shown below:

Source: Digital Logic at UTexas

In short, we either have 3.3 volts or we do not. These voltage levels are translated into “on” and “off” which are in turn translated into “zeros” and “ones” — “bits” — by the hardware and the operating system. These “bits” may or may not be organized into high-level constructs. However, at the very least they are organized into basic structures such as bytes.

To use an example that is familiar to all of us, each byte in the Standard Code of the ANSI X3.4-1977 matrix is, in fact, a structure, and these bytes in turn are organized into a larger structure, the matrix itself, “the Code”:

Let us return to the topic of memory addresses. As Hailperin explains, from a hardware perspective there are two contexts to keep in mind when we think about addresses: The CPU and physical memory.

First Context: The Central Processing Unit

The CPU needs to distinguish between values stored in memory. It does so by using addresses as names. Recall that in Assembly, labels are used as addresses for data structures such as strings. In fact, a label is a symbolic name for a memory location. To see how this works, download and compile the following C program using the --save-temps option:

Source: strings.c

.file "strings.c" .text .section .rodata .LC0: .string "Alice" .LC1: .string "Ina" .text .globl main .type main, @function main: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $16, %rsp leaq .LC0(%rip), %rax movq %rax, -8(%rbp) leaq .LC1(%rip), %rax movq %rax, -16(%rbp) jmp .L2 .L3: movq -8(%rbp), %rax leaq 1(%rax), %rdx movq %rdx, -8(%rbp) movl $1, %edx movq %rax, %rsi movl $1, %edi call write@PLT .L2: movq -8(%rbp), %rax movzbl (%rax), %eax testb %al, %al jne .L3 jmp .L4 .L5: movq -16(%rbp), %rax leaq 1(%rax), %rdx movq %rdx, -16(%rbp) movl $1, %edx movq %rax, %rsi movl $1, %edi call write@PLT .L4: movq -16(%rbp), %rax movzbl (%rax), %eax testb %al, %al jne .L5 movl $0, %eax leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size main, .-main .ident "GCC: (Debian 12.2.0-14) 12.2.0" .section .note.GNU-stack,"",@progbits

Note how each of the strings — the first names of Alice Liddell and her sister Ina — is given a label, LC0 and LC1, respectively. Note also how leaq — “Load Effective Address” — relies on these labels. The key point is that an address may or may not be a number, but in any case addresses are names, and therefore numbers may also be used as names. Numbers are, essentially, symbols.

As we approach the lower levels, e.g. machine language, addresses are numbers that serve as names. Think of a list in Python. The index of each element in a list serves as a name that allows us to locate each element. Moreover, since the names of each element in the list are integers, we can use arithmetic to manipulate the names systematically.

In C, we have something similar with arrays. Hailperin states:

All the array elements are stored at consecutive virtual addresses. That allows the virtual address of any individual element to be computed from the base virtual address of the array and the element’s position within the array (p. 210).

An array name in C is, in fact, a pointer to the first element of the array. Since the value of a pointer is a number — i.e., an address — we can use pointer arithmetic to traverse the array. The following serves as a simple illustration:

Source: strings-pointer.c

Ex.: Download the C program above and compile it. What is the output? Keep in mind that a string in C is an array of characters.

Second Context: Physical Memory

In this context, addresses are not names but locations of memory cells. In other words, addresses in this context locate cells that contain data. Addresses used by physical memory are known as physical addresses — these are to be distinguished from virtual addresses.

In today’s operating systems, virtual memory relies on sets of virtual addresses known as pages. A page, we may say, is a unit of memory in the virtual address space. Each page in virtual memory corresponds to a block of physical memory — the latter is a page frame.

The size of a page is typically about 4K — i.e., 4096 bytes. However, this is not always the case. There are many factors that determine page size on a given system, including the OS distribution one happens to be using. In any case, we can determine the distribution and page size of our system like so:

$ uname -a Linux mx1 6.1.0-13-amd64 #1 SMP PREEMPT_DYNAMIC Debian 6.1.55-1 (2023-09-29) x86_64 GNU/Linux $ getconf PAGESIZE 4096

Uses for Virtual Memory

Section 6.2 of our textbook describes various uses of virtual memory, among which are the following:

Private Storage (6.2.1) Controlled Sharing (6.2.2) Flexible Memory Allocation (6.2.3) Sparse Address Spaces (6.2.4) Persistence (6.2.5) Demand-Driven Program Loading (6.2.6) Efficient Zero Filling (6.2.7) Disk Memory (6.2.8)

More generally, two of the more important uses of virtual memory are the following

1. Virtual memory allows processes to use the same names for different locations in physical memory. 2. Virtual memory allows processes to use different names for the same location in physical memory.

We can illustrate (1) as follows. Keeping in mind that a number can be a name, consider two processes, each of which uses the names 0, 1, and 2 to refer to copies of data structures (represented as shapes), as illustrated by Hailperin in Fig. 6.3 (p. 211):

Here, each shape represents a data structure stored in memory. In virtual memory, each process uses the same names — i.e., 0, 1 and 2 — for its own private copies of these structures. These names, however, are mapped to different locations in physical memory. We may understand it like so:

Process A Virtual Address 0: Physical Memory Address 0 Process A Virtual Address 1: Physical Memory Address 1 Process A Virtual Address 2: Physical Memory Address 2 Process B Virtual Address 0: Physical Memory Address 3 Process B Virtual Address 1: Physical Memory Address 4 Process B Virtual Address 2: Physical Memory Address 5

For example, consider a text editor such as vi. We may have several instances of vi running at the same time, with each instance holding a different text in its buffer. These instances may refer to the text being edited as text or t0 (or similar; the names have been simplified for the sake of clarity). Yet, for each instance of vi, the same name or virtual address maps to a separate area of physical memory.

The reverse may also be the case: a single region of physical memory may be shared by multiple processes, with each process having its own name or address for the shared region. As Hailperin states:

It should be possible for two processes to use the same virtual address to refer to different physical addresses [as shown in the above example] or to use different virtual addresses to refer to the same physical address (p. 232).

In addition to the above, virtual memory also allows the OS to interface with a variety of hardware — i.e., different types of physical memory. The Linux kernel documentation (v. 6.9.0-rc3) states:

... physical memory is not necessarily contiguous; it might be accessible as a set of distinct address ranges. Besides, different CPU architectures, and even different implementations of the same architecture have different views of how these address ranges are defined.

All this makes dealing directly with physical memory quite complex and to avoid this complexity a concept of virtual memory was developed (Memory Management: Concepts Overview)

Virtual memory is an abstraction of physical memory — as such it hides the details of the underlying hardware. The translation of a virtual address to a physical address is handled by the OS in conjunction with the Memory Management Unit (MMU).

The MMU is a physical device and is typically (though not always) a component of the CPU (see note three below). The following figures from our textbook illustrate this:

Source: Hailperin p. 210

Source: Hailperin p. 212

The first figure above shows a system without an MMU; in this case, the CPU directly accesses physical memory. The second figure shows how a system with an MMU maps virtual addresses to physical addresses.

Virtual memory also serves to protect physical memory from malicious attacks. On this issue, the description section of mem(4) in the system manual is telling. Why is “RAM access not allowed”? Physical memory was accessible in earlier versions of the Linux kernel. This was possible not only through kernel interfaces such as /dev/mem, but also through /proc/[pid]/pagemap.

The Linux kernel documentation states that /proc/[pid]/pagemap “lets a ... process find out which physical frame each virtual page is mapped to.” However:

Since Linux 4.0 only users with the CAP_SYS_ADMIN capability can get PFNs ... Starting from 4.2 the PFN field is zeroed if the user does not have CAP_SYS_ADMIN. Reason: information about PFNs helps in exploiting Rowhammer vulnerability (Examining Process Page Tables).

Rowhammer works at the hardware level — i.e., physical memory — to disrupt operating systems and processes:

Modern DRAM chips suffer from a vulnerability commonly known as RowHammer ... RowHammer is caused by repeatedly accessing (i.e., hammering) one or more (aggressor) memory rows. Hammering a row creates electromagnetic interference between the aggressor row and its physically-neighboring (victim) rows (“Fundamentally Understanding and Solving RowHammer” p. 1).

Thus, a process that can determine the physical addresses used by the operating system can undermine the system by repeatedly accessing data at those addresses. This is one reason why the Linux kernel conceals physical addresses.

Nonetheless, /proc is useful. For example, the following C program shows how /proc/[pid]/maps can be used to determine the virtual address range of processes:

Source: proc-maps.c

File Systems

Key concepts as described in Practical File System Design with the Be File System (pp. 8-9):

Disk: A permanent storage medium of a certain size. A disk also has a sector or block size, which is the minimum unit that the disk can read or write. The block size of most modern hard disks is 512 bytes. Block: The smallest unit writable by a disk or file system. Everything a file system does is composed of operations done on blocks. A file system block is always the same size as or larger (in integer multiples) than the disk block size. Partition: A subset of all the blocks on a disk. A disk can have several partitions. Volume: The name we give to a collection of blocks on some storage medium (i.e., a disk). That is, a volume may be all of the blocks on a single disk, some portion of the total number of blocks on a disk, or it may even span multiple disks and be all the blocks on several disks. The term “volume” is used to refer to a disk or partition that has been initialized with a file system. Superblock: The area of a volume where a file system stores its critical volumewide information. A superblock usually contains information such as how large a volume is, the name of a volume, and so on. Metadata: A general term referring to information that is about something but not directly part of it. For example, the size of a file is very important information about a file, but it is not part of the data in the file. I-node: The place where a file system stores all the necessary metadata about a file. The i-node also provides the connection to the contents of the file and any other data associated with the file. The term “i-node” (which we will use in this book) is historical and originated in Unix. An i-node is also known as a file control block (FCB) or file record. Extent: A starting block number and a length of successive blocks on a disk. For example an extent might start at block 1000 and continue for 150 blocks. Extents are always contiguous. Extents are also known as block runs. Attribute: A name (as a text string) and value associated with the name. The value may have a defined type (string, integer, etc.), or it may just be arbitrary data.

From the same source, we have the following information:

The most important information stored in an i-node is the connection to the data in the file (i.e., where it is on disk). An i-node refers to the contents of the file by keeping track of the list of blocks on the disk that belong to this file. A file appears as a continuous stream of bytes at higher levels, but the blocks that contain the file data may not be contiguous on disk. An i-node contains the information the file system uses to map from a logical position in a file (for example, byte offset 11,239) to a physical position on disk (pp. 10-11).

Here is an illustration of the above:

Giampaolo explains extents as follows:

Another technique to manage mapping from logical positions in a byte stream to data blocks on disk is to use extent lists. An extent list is similar to the simple block list described previously except that each block address is not just for a single block but rather for a range of blocks. That is, every block address is given as a starting block and a length (expressed as the number of successive blocks following the starting block). The size of an extent is usually larger than a simple block address but is potentially able to map a much larger region of disk space (p. 16).

Some useful commands: ls -i [prints the index number of each file] df -T [shows file system type; see Squashfs 4.0 Filesystem for information on squashfs] lsblk [list block devices] sudo dumpe2fs /dev/loop1 [dump ext2/ext3/ext4 file system information] sudo blockdev --getbsz /dev/loop0 [print the blocksize of a block device in bytes] sudo dumpe2fs -h /dev/loop0

In Linux and kindred operating systems, the /dev directory serves as an interface to devices such as hard drives, printers, keyboards, video cards, and the like. Not unlike /proc, pseudo-files in /dev represent devices as files. Device drivers transfer data from and to devices through these files.

Essentially, /dev files fall into two categories:

Character Device (c): I/O comprises a series of bytes (hence, the term "serial"). Serial and parallel ports, terminal devices, mice and keyboards are examples. Bytes are read as a stream; random access is not possible.
Block Device (b): I/O comprises fixed-size blocks; random access (e.g. reading data in the middle of a file) is possible. Disk drives are examples.

Devices in Linux are classified and identified using two numbers:

Major Device Number: the device driver corresponding to a device type
Minor Device Number: individual devices controlled by a single driver

Baeldung explains the above as follows:

A more detailed and direct way we can identify device files in the /dev directory is by using the device’s major and minor numbers. For example, disk devices have a major number of 8, which assigns them as SCSI block devices. Note that the SCSI subsystem manages all PATA and SATA hard drives. This is because the old ATA subsystem is not maintainable due to the poor quality of its code. As a result, hard drives that would previously be designated as hd[a-z] are now referred to as sd[a-z] ...

SCSI is a microprocessor-controlled smart bus. It allows us to add up to 15 peripheral devices to the computer. These devices include hard drives, scanners, USB, printers, and many other devices. It stands for small computer system interface.

Source: Baeldung: What Is /dev/sda in Linux?

Ex.: Perform the following commands and examine the output: 1. cd /dev; ls -l | less 2. cat /proc/devices 3. sudo fdisk -l

Selected /dev files:

/tty*: terminal emulators and serial ports /sd*: hard disk (see above) /dev/input/by-path: keyboard and mouse /dev/video*: video camera /dev/bus/usb: USB ports /dev/loop*: loop-back device

It is worth noting that tty is short for teletypewriter — primitive terminals. An example from 1982 can be seen here. More information is available here.

Also of note are /dev/null, /dev/zero, and /dev/random — these are pseudo-devices that are very useful in Linux.

A loop-back device is a simulation of a block device such as a CD drive or a hard disk drive. For example, a loop device can emulate Linux installed on a CD or hard drive. A loop-back device can host a virtual file system just as a disk drive can host an actual file system.

Ex.: Perform the following commands to mount a disk image (i.e., a file system) using a loop device: cd /tmp dd if=/dev/zero of=/tmp/disk-image count=25000 mkfs.ext4 disk-image sudo mkdir /dev/loop25 sudo mount -o loop disk-image /dev/loop25/ See LOOP-DEVICE SUPPORT in man(8) mount.

Notes:

* Note that sudo apt install xxd; xxd -br alice.txt will show the bits of each byte (you can also use hexdump and convert the hexadecimal output into binary). You can then look up the bits for the last byte of alice.txt in the Standard Code at ANSI X3.4-1977 using the instructions in Section 3. Clarification is provided in Section 5.2 (p. 10) of the Code.

** But we should never forget that even writing changes as well, given that it decays. This is also true of programs and source code: magnetic storage media — tapes, discs, etc. — decay, just as paper disintegrates and ink fades. Everything that is physical decays, including the human body.

*** Despite claims to the contrary, many systems do not have memory management units — these include mainframes, microcontrollers, and embeded systems. These systems manage and secure physical memory by other means. In fact, some operating systems, including Linux, provide support for non-MMU (or "nommu") systems; see No-MMU Memory Mapping Support at kernel.org.

References:

1. Raúl Rojas and Ulf Hashagen, editors, The First Computers: History and Architectures. The MIT Press (2000).

2. Stan Augarten, Bit by Bit: An Illustrated History of Computers. W.W. Norton & Co. (1984).

3. M. Jones, “Evolution of Shells in Linux: From Bourne to Bash and Beyond.” IBM (2011).

4. Johnson, S.C. and Ritchie, D.M. “UNIX Time-Sharing System: Portability of C Programs and the UNIX System.” The Bell System Technical Journal, Vol. 57, No. 6, 1978: p. 2024. URL: http://www.pub22.net/csc425/bell57-6-1978.pdf.

Misc URLs:



Exploiting Rowhammer (Vanderbilt)

Linux Kernel Documentation: Examining Process Page Tables

History of Unix (UC)

UNIX : System V Release 4 Manual

Unix Programmer's Manual (1974)

Why POSIX shell scripts? [20210310161500] (rwxrob)

Intro. to ELF Headers

Rachel Blevins on "The Donor Class"