Scribe Notes - 10/15/2014

OS Organization

October 15, 2014

Bartholomew Elliott, Mitchell Herndon, and Austin Pineda

What are our goals in organizing an operating system?

Ease of interface, use, and simplicity
Reliability and robustness
Efficiency (battery, memory, speed)
Mutability and flexibility
Security

What have we got? Three fundamental abstractions for systems...

1) Memory API

*p = v; //to write data from v
v =(*p); //to read data into v

Some problems with this abstraction include: How do we know the total size of memory? How do we know the word size for this system since it's not universal? How do we account for throughput and latency of the memory devices? How do we keep track of volatile memory? Does the system have linear addressing (treats memory as a large array) or associative addressing (treats memory as retrievable data)? Most importantly, memory coherence (and data atomicity) is a key variable to keep track of on a system.

2) Interpreters API

v = f(p);

In this example v is the result received from calling the interpreter f on a program p. Another way to represent this API is with one pointer that looks at the instructions it should complete (ip) and another that tells it information about the environment it's working in (ep). The machine can read both of these and execute instructions accordingly.

However, there are some drawbacks to this abstraction as well. We have to balance the systems efficiency with the requirement of hardware (specifically a virtualizable processor). You should be able to jump between different environments (processes) without crashing the whole system. You need to ensure safety by being able to catch processes from doing unsafe things (like a "halt and catch fire" instruction or an infinite loop).

"It's interpreters all the way down!" -Paul Eggert, 2014

3) Link API

send(linkname, buffer_data);
receive(linkname, buffer_data);

This is the main type of system with which OSX is implemented; it allows systems to communicate with each other by passing messages to one another. This type of system can be easily generalized, which allows the system to send data wherever it wants. So, the kernel can be anywhere as long as data is sent to the right place. However, data has to be split into buffers, and the constant sending of data results in a performance slowdown. It's also impossible to send pointers to data over a network because the memory isn't shared.

"What if I asked you to build me an OS at the end of CS32?" -Paul Eggert, 2014

Well, at the end of CS32, all we kenw was object-oriented programming (C++). So this forces us to build an OS as an object-oriented program. This would involve a class each for the I/O bus, memory, an interpreter, etc.. Believe it or not, this is how Windows was made. But C++ simply doesn't run as fast as C. It doesn't provide the same opportunity for optimization. For this reason, it's not very practical.

"Come on, we want steep learning curves here!" -Paul Eggert, 2014

Virtualization:

Layering:

OS + Virtualizable Processor

Combining an operating system with a virtualizable processor allows you to support something called a process. In Linux, we define a process as a program that's running in isolation on a virtual interpreter. To create a process, you use the fork function:

pid_t fork(void);

where pid_t stands for the ID of the process. This function returns 0 if the process is a child, and a positive number if the process is a parent. You cannot actually destroy a process. The only way for one to end is for the process itself to call:

_Noreturn void exit(int exit_status);

There are two types of exit functions: a system call (_exit(int exit_status) and a library function call (exit(void)). The system call doesn't flush output before returning, while the library function does - the system call is a more immediate and severe way to end a process. So what do we do when we want to wait for a process to complete? There's a function called

pid_t waitpid(pid_t wait_for_process, int* loc_to_store_status, int flags);

This is sort of like a destructor for a process, since exit doesn't delete process table entries. When a process exits, but hasn't been deleted from the process table, we call it a zombie, because the data in the row is still valid even though the process has ended.

The Garden of Fork()ing Paths

Since each individual process runs on its own virtual interpreter, there needs to be some way to organize all the different processes executing at the same time. Suppose, for example, we only have one physical CPU and we want to run many processes at once. We would have to simulate multiple processors. Because we only have one set of registers and one ALU, we have to store old process data in something called a process table:

Each row in the table represents a single process, and contains information such as its registers, exit status, and process ID. When you fork a process, the new child copies the data from its parent's row, except for the %eax register (because the call to fork returns different values for parent and child). However, the fork function can also be used as an exploit, or a fork bomb. By infinitely forking, every new process contributes more fork calls to the attack. Eventually the process table fills up and the CPU crashes.
The process table can also be used to save a process' registers when the CPU switches processes. An example of this is a call to the read function. In this case, the CPU saves its current process' register data to the process table and resumes some other process, instead of simply waiting for read to return.

Accessing Memory

Each process has its own view of memory, which is specific to that process. This diagram shows two processes and their individual views of memory, and how they relate to the physical memory.

"Cat is my favorite program. It copies data like crazy. I love copying data." -Paul Eggert, 2014

Pipes in Linux

There is a function called

int pipe(int fd[2]);

Its parameter is an array of two file descriptors - one for read and one for write. The function for reading either hangs if there is no data, or gives data if there is any. The function for writing hangs if the buffer is full, or writes the data otherwise.