# Distributed Systems
## Memory model

Every process in Unix has an address space that looks like this:
Remember the low memory is at the top, and the high memory is at the bottom. So when items are added to the stack, and it grows upwards, each element has a lower memory address.

## Unix processes
### fork is your friend

You should know what this does:
The call to fork creates a new process with an entire new address space. That means a copy is made of everything: new global vars, new text code, new heap, and new stack. Even object dynamically allocated with malloc are copied. Remember that the pointers to those dynamically-allocated objects are set based on relative addressing, so even the new copied memory is allocated somewhere else, the pointers into the heap still work.

### process states

The four most popular UNIX process states are ready, waiting, running, and zombie. The first three are easy. Zombie processes are child processes that have completed and are waiting for their parents to clean them up. Usually parents clean up completed (zombie) child processes by calling wait or waitpid.
If the parent process dies before the child process finishes, eventually the root process will come around and clean them up.

## Pipes
### simple example

So, after fork, if each process has its own memory space, how to set up communication? With pipes! Each process may have its own file descriptor table, but they still reference the same files.
Example pipe code, where child reads and parent writes:
NOTE: feel free to add in all that error-checking goodness, but try to keep the point obvious
Study and understand the above code.

### Implementing a very simple shell with pipes

We've all done stuff like this at the command line:
But how does that work? In MS-DOS, this functionality was implemented sort of like this:
The three tasks were run sequentially, rather than concurrently. This is bad if the output of the first program is enormous, and this setup certainly can't handle an infinite stream of data.
You can implement the ls -l | sort | head stuff in C. To keep it manageable, the following code implements "ls | wc -l" instead:
TODO: talk more about how execv works.

### Implementing I/O redirection with pipes

Another classic:
How can you do?
TODO: finish
err?

## Threads

wikipedia thread article
Threads share memory, processes don't. They both allow programs to do multiple things simultaneously (concurrently). Most of the time on Linux, when people talk about threads, they're really talking about POSIX threads, aka pthreads.

### Simple pthread example

Example pthread code:
This is a slice of the output:
Hopefully the main point is jumping out at you. Foo and bar alternately increment up the global integer i.

#### Exercise

Rewrite the above code to use fork and create two processes rather than two threads. Then find what is the maximum value of i and explain the difference with this threaded version.

### Kernel threads vs. user threads

pthreads are kernel-space threads, meaning that the OS scheduler is aware of the multiple threads. Each thread has an entry in the OS schedule table.
There are also user-level threads, where the kernel is unaware of the threads. The process must handle scheduling itself. User-level threads require two-level scheduling:
One user-level thread can block all the other threads for the process if the programmer isn't careful. If a user-level thread makes some blocking system call, then the OS will suspend that process until that system call returns.
User threads have the advantage of allowing switching between threads in a process much more quickly than kernel-level threads. The process does the context-switching itself.

### Solaris hybrid threads

Sun Solaris version 2.3 offered hybrid threads which attempt to combine the speed of user-level threads with the advantages of kernel-level threads. The hybrid threads minimize the OS scheduling cost of switching between threads at the kernel level, but they also allow a thread to make a blocking system call without blocking the entire process.
The system allowed for threads and lightweight processes. The OS scheduler only saw the lightweight processes. Each thread is attached to a lightweight process. Threads can share a process, so one application with multiple threads may appear to the OS scheduler as a single process.
In a program with two threads both bound to a single process, if thread 1 makes a blocking system call, then the OS will block the process. Meanwhile, in order to allow thread 2 to still run, the OS will create new process, detach thread 2 from the first process, and then attach it to the new process.

### critical sections and mutexes

If threads are going to share vars, you need to be careful they don't both try to alter memory simultaneously.
Consider this classic C code:
This looks like one operation (add one to i), but it translates to three operations in assembly code:
Read the C programming appendix in this book for more information on how to convert a C program to assembly using gcc.
Since threads share memory, it is possible for one thread to start to do something, then get suspended by the OS scheduler.
Imagine if two threads exist and i is a global integer, initially set to 99. Each thread wants to increment up i by one, so each thread will do the three assembly steps above. After we are finished, we expect to find i set to 101.
First thread 1 starts:
Now, imagine at this point the OS scheduler suspends thread 1 and starts thread 2:
And then, the OS allows thread 1 to finish:
So now you see how two threads accessing common variables can be risky. The worst part about this bug is that it will be inconsistent and hard to reproduce. The i++ statement is called a critical section because we need to makes sure that only one thread has access to the variable in that section.
One solution is to use some kind of lock, like this, in each thread:
Then if thread1 gets suspended, and thread2 starts, it will block on the lock(ilock) call. To do this for real, we can use mutexes. A mutex is like a semaphore that only has values of 1 or 0. The threads in this code will lock and unlock a mutex before trying to increment up i, so you avoid the above problem.
That's it!
Another solution to this problem is to use a "increment" instruction that really is atomic. (The "lock" and "unlock" functions use just such an atomic instruction). Such atomic functions (and how they can be used to avoid data corruption and deadlocks) are discussed at Wikipedia:Lock-free and wait-free algorithms.

### Producer and Consumer model

This hobgoblin shows up all the time in the real world. The chef makes bowls of soup for the diner. The chef has to wait for the diner to ask for soup, and the diner has to wait for the chef to announce the soup is ready. If you ain't careful, you can end up with a deadlock which is just as nasty as it sounds.
A deadlock involves two processes (p1 and p2) and two resources (r1 and r2). Each process needs exclusive access to both resources to finish. The deadlock happens when p1 holds r1 and waits for r2 to be released, and p2 holds r2 and waits for r1. As you can see, neither process can continue.
This pseudocode illustrates how to set up a producer/consumer system and not fear deadlocks:

## Shared memory

System V provides shared memory. One process can allocate some memory as shared memory, then other processes can attach to that memory, and these processes can communicate.
one process can use shmget to allocate memory. then that process can use shmat to aim a pointer at that memory.
another process can use shmat to attach a pointer to that same memory.
shmdt will detach the pointer from shared memory.
shmctl can be used to free the allocated memory.
You can use ipcs to check on any allocated shared memory, which is a nice way to check if your program freed all allocated memory. ipcrm will delete allocated shared memory.

## Signals

Signals are neat. When you hit Ctrl+C to kill a process, you're really sending SIGINT to that process. Similarly, Ctrl+Z sends SIGTSTP and `kill -9 pid` sends the 9th signal, SIGKILL. The full listing of available signals is in the seventh section of the manual pages (`man -s 7 signal`).

### signal handlers

When a process receives a signal, the corresponding function is invoked. In the case of SIGKILL, the function causes the code to exit. Many of these signals can be trapped and reassigned to a custom function as illustrated in the following code:
Compile and run the program above and then try to kill it with Ctrl+c. Now, try to kill the program with `kill -s SIGKILL pid`.
When Ctrl+c is pressed, the process is sent the SIGINT signal; however instead of terminating, the custom function sighandler is invoked. Since the SIGKILL signal is not trapped, the code exited normally.
The signal function will not let you write a handler for SIGKILL.
In HP-UX, after the signal arrives, the signal handler is forgotten for that signal. So, often inside the signal handler, it re-registers it self as the handler:
In Linux, this is not necessary.

### sigalarm

The SIGALRM signal can be raised by the alarm function, so it's a good way to generate a signal inside your program. The below code illustrates:
This program will run until you kill it.

### Signals and setjmp/longjmp

This code calls the SIGALARM handler when the process receives the SIGALARM signal, and then inside the handler, jumps out of the handler without returning.
There's an issue that might not be obvious. After a process gets a signal, then it calls the signal handler. If another signal comes in while the first signal is still being processed, the process will ignore that second signal. The OS "blocks" the signal while the handler is running.
When the handler finishes, as part of its return, the OS allows the process to get new signals.
If we jump out of a function with longjmp, then the signal handler will never return, and the process will never hear any new signals of that type coming in. However, don't worry! You can manually unblock the signal and then jump out.
This alternate handler shows how:
You can use the functions sigsetjmp and siglongjmp to jump out of a signal handler and optionally reset the signal mask. The below code shows an example. You'll have to use Ctrl-C to end the program:

### Signals and pause

If you want to wait for an event, but don't want to resort to some kind of spin lock, you can use the pause function to suspend a running process until a signal occurs.
Example code:
Also notice that the second print statement casts the function sh to an integer, and also casts the address of sh as an integer. Here's the output of the program:
Notice that sh after being cast to an integer is the same as the address of sh. That 134513700 is the memory address in the text section of the sh function. Although it may seem a little strange at first, from the OS point of view, functions are really just another kind of data.

## Message passing

message passing is distinct from communication via pipes because the receiver can select a particular message from the message queue. With pipes, the receiver just grabs some number of bytes off the front.
The type arg allows priority scheduling. If the 4th arg of msgrcv is > 0, then system will find the first message with the type equal to that specified 4th arg.
If type is < 0, then system will find the first message with the lowest type where type is below the absolute value of type.
If we have these messages:
Then type -250 would return B.
The following two programs show message passing.
mpi1.c:
mpi2.c:
Now compile mpi1.c into mpi1 and compile mpi2.c as mpi2:
Now run mpi1 in background and then run mpi2:

## All about the stack

This section describes what happens in the stack and registers when one function calls another function and passes a few parameters.
Imagine we have this C code:
Behind the scenes, first c gets pushed, then b, then a, then the return address of the calling function. This is what the stack looks like (the stuff at the top was the most recently pushed object):

### segfaults revealed!

We've all seen this lovely error:
Most of the time, you find out something like is the problem:
After this command: char ss[3]; the stack can fit three characters into one 4-byte word.
Now watch what happens when the strcpy command fills in the stack:
So hopefully it is more clear what a segfault is. Your program is trying to hop to a memory address outside the process memory, and the OS puts the smack down.

## Networking
### OSI reference

7 layers:
* application
* presentation
* session
* transport
* network
* data link
* physical
In Unix, the first three (application, presentation, and session) are often bundled together.
Imagine that a network looks like this:
If a process (application) on A wants to communicate with a process on B, this is sort of what happens:
The transport layer adds A's port and B's RPC server port.
The network layer adds A's IP address and B's IP address.
Any communication from A must go through the two routers first.
The data link layer adds A's mac address and router 1's mac address.
The physical layer converts the frame into the physical signal.
When the message is received by router 1, the frame is read in and sent to the bottom of the OSI model. Router 1's mac address is removed and replaced with Router 2's mac address.

## The UNIX file system
### Inodes

Each directory is actually a file. That file lists the names of files and subdirectories in that directory. It associates names to inodes.
Each inode has the following data:
* userID
* groupID
* mode
* timestamp (accessed, created, modified all tracked separately)
* link count
* file size
* direct pointers to 10 data blocks that contain file contents
* single indirect pointer to a data block that points to data blocks that contain the file contents
* double indirect pointer to a data block ...

### Addressing

Since each inode has 10 direct address pointers, if a file is small enough to fit on 10 data blocks or less, then the inode can use direct addressing.
If we assume that we use 4 bytes to specify the disk address, then we can have 2$^{32}$ different addresses. If we set the data block size to 4 kb, then one data block can hold 1000 addresses. So, with single indirect addressing, we can point to a file that uses 1000 data blocks of data.
Therefore, the maximum allowed file size for single indirect addressing (assuming 4kb data blocks and 4byte addresses) is 4 megabytes (1000 data blocks * 4 kb per data block).
Easy formula: data block size / disk address = max file size.
Of course, in double or triple (or quadruple, quintuple, etc.) addressing, you just gotta take the analysis out further.
| File Size | Blocks Used |
| 1 block | 1 block used via direct addressing. |
| 11 blocks | 12 blocks used: 10 blocks of data via direct addressing, 1 block for indirect addressing, and 1 for data. |
| 150 blocks | 10 blocks via direct addressing, 1 + 128 blocks through single addressing, 1 + 1 + 12 1 double indirect + indirect + 12 data blocks |
There are advantages and disadvantages of small vs. large data blocks. Lots of small files and big data blocks causes low utilization. For example, your .vimrc file may only have 300 bytes of data, but it has to use at least one data block, so if your data block is 4kb in size, well, that's a lot of wasted space.
However, small blocks lead to big files being scattered out across lots of data blocks, and so the hard drive reader has to skip all over the place gathering up the data. Large data blocks reduce fragmentation.
As the number of blocks per file increases, disk IO cost increases.

### Linking

Each directory has a table that maps file names to inode numbers. A file can have any number of names associated with it. Each inode keeps track of its link count. The command rm foo.txt edits the directory and removes the entry that maps foo.txt to a particular inode. If that inode has zero links, then it is deleted.
You might want to read the man page for ln at this point to understand the difference between soft and hard links.

### RAID

Compared to a monolithic system, a distributed system can have a much lower chance that the system will fail today—even though the distributed system has a much higher chance that one part will fail today. High-availability distributed systems use techniques inspired by RAID (redundant array of inexpensive disks) to tolerate a failure in any one part, without loss of data or functionality.
For more details, see
* minimizing hard disk drive failure and data loss
* LPI Linux Certification/Configuring RAID

### The set-user-ID bit

The set-user-ID bit (sometimes shortened to setuid or simply suid) alters how the OS handles permissions. For example, the chsh command allows a user to change her login shell, like from bash to tcsh. The login shell for each user is stored in /etc/passwd, but users don't have write access. So how can a user run chsh and change that file? The answer is with suid bits. Look at the permissions on chsh:
So, what is that s in there for? That, my friend, is the set-user-ID bit, which means that this program runs as if it were executed by root.
A program with the setuid bit set (or the similar setgid bit) will be run with the privileges of the program's owning user or group respectively.

## Remote Procedure Calls

Remote procedure calls (RPC) are a way hiding all the details of running a process on a far away remote machine.
If A wants to make a remote procedure call on host B, then A needs B's RPC server port.
An RPC frame includes:
* function number
* parameters
The command rpcinfo will list what RPC services are running on the machine.
Generally developing RPC program involves eight steps:
* Build and test conventional application.
* Divide the program by choosing a set of procedures to move to a remote machine. Place the selected procedures in a separate file.
* Write a rpcgen specification file for the remote program. Choose a program number and version number. The specification file should be named with a .x suffix. For example, a remote database program could have a spec file of rdb.x.
* Run rpcgen command to check the specification file. If the file is valid, rpcgen will generate source code that will be used to build the client and server. Example:
will generate 4 output files: rdb.h rdb_clnt.c rdb_svc.c rdb_xdr.c
* Write stub interface routines for the client and server side. You can use the code developed in step 1. For example, you might write a rdb.c file that handles the client interface, and a rdb_svc_proc.c to handle the work on the server side.
* Compile and link the client program.
* Compile and link the server program.
* Start server and invoke client.

## Distributed Algorithms

Properties of distributed algorithms
* Information can be scattered among machines.
* Each process makes decisions based on local information.
* Machines can share information.
* A single point of failure should not cause the entire system to crash.
* Machines can't rely on a single common clock or global time.
A simple example of how non-global clocks cause problems:
* you compile foo.c (via make) to foo.o on machine A.
* you log in to machine B, which has a clock that is 15 minutes behind B.
* You edit foo.c again, then run make. make compares the timestamp on foo.o to foo.c and foo.o is still newer, so make will not recompile foo.o.

### Synchronization

Physical clocks agree with "real time" like Universal Coordinated Time.
Logical clocks don't worry about being accurate to some global standard. Instead, all machines in a system try to agree with each other.
Keeping a local physical clock synchronized is challenging because even if the machine can contact the authoritative time server, there is some propagation delay.
How often does a machine need to request an update from a time server? Assume that the machine has a clock $C$ that increments at rate $dC$.
The UTC clock $t$ increments at rate $dt$.
If $dC/dt=1$ then the local physical clock C is perfect and doesn't need to be updated.
If $dC/dt>1$ then the local physical clock C runs at a faster rate.
If $dC/dt<1$ then the local physical clock C runs at a slower rate then the time server.
$\rho$ represents the maximum drift rate specified by a manufacturer.
$1-\rho <=dC/dt<=1+\rho$
$\delta$ represents the maximum tolerable error. every $\delta /\rho$ period, a machine must request an update.
As the error tolerance $\delta$ increases, update frequency falls. As drift rate $\rho$ goes up, the update frequency goes up also.

## Appendix A: C language overview
### setjmp and longjump

Use these to do what C++, python, Java, etc. does with throwing exceptions. First call setjmp to set a location to jump to. Then other functions can call longjump to exit the current function and how to the location specified in setjmp.

### functions with variable-length arguments

In other words, how does printf(...) work?

### conditional compilation

One example:
In the second compilation, the printf block ain't included.
Another similar trick is used to prevent the same header file from being included repeatedly. It is common for one C program to have multiple .c files which include multiple .h files. You can put this code at the top of your .h file to prevent the same .h file from being included redundantly:

### make and makefiles

Four type of statements are allowed in Makefiles: macros, dependency rules, commands, and comments. Here's a trivial example makefile:
I can run any statement by typing make and the name. Or by default, make will run the first rule it hits if it gets no arg.
Macros are accessible after being declared by either $(CFLAGS) or ${CFLAGS}. $CFLAGS is not valid. If the macro is one letter, like
Then $A is valid. But you should stay away from that anyway, because lots of the single-char macros already have meaning.
Each tab underneath a dependency rule starts a new shell, so if you want to change shell stuff, you gotta do it all on one line:
The output:
BTW, if you want to suppress the default echoing of the commands, put an @ at the beginning:
And here's the output:
How one make command can recursively call make in subdirectories:
This confused me at first. The $@ symbol refers to the target for the rule, in this case, the ${SRCDIR}.
You can use makedepend inside a makefile to resolve all that hairy .h stuff automatically:
TODO: show example before and after Makefile.
If you have lots and lots of files and you want to compile them all into objects, this rule works:

### Converting C to assembly

This will convert your program to assembly code, using GNU syntax. gcc will create a file called try.s
This will convert your code to assembly code using intel syntax. This may only work on intel CPUs.
You can convert try.s to an executable like so:
And you can even compile the executable for use with gdb:
And then you can step through the underlying assembly code in gdb. Hurray!

## Appendix B: Solutions to Exercises
### 4.1.1 POSIX Threads

The task for this exercise was to rewrite the example code to use fork rather than threads. You should have something similar to this:
You were also asked in what way the output was different, and why. In the version that made use of POSIX Threads, the counter was incremented twice each second: once by each thread. When fork was used, it was only incremented once. The reason for this is that when fork is called, the child process writes to its own copy of the counter. When threads are used, however, both threads share their memory space. This means that they are both writing to the same copy of the counter, and it is incremented twice.

## Contributors

Please, give yourself credit if you've made any contributions!
Matthew Wilson Started this textbook in Fall 2004, while enrolled in a graduate comparative operating systems interfaces course at Cleveland State University.
Lachlan Gunn

## Further reading

* Embedded Systems—some of the most widely-distributed systems are embedded systems.
* Embedded Control Systems Design
* Operating System Design—covers some of the low-level details underneath fork, threads, critical sections, monitors, etc.