CS 111 - OS Organization

Scribe Notes for 10/15/2014

OS Organization Goals

• Ease of interface - The user should have access to a "nice" and simple API.
• Reliability/Robustness - The system should make little to no assumptions and should not crash from unexpected input.
• Efficiency - The system should with high performance with little performance
• Mutability/Flexibiliy - The system should be useful in several situations and should be easily modified and/or expanded.
• Security - Users should not be able to access "inner" properties of the system.

3 Fundamental Abstractions for Systems

Memory API

Memory is the sytem abstraction that deals with remembering data for future computations. In its simplest form, the Memory API has two fundamental operations, named Write and Read.

        
        // p represents a pointer to some data in memory and v represents a piece of data

        // Write

        *p = v

        // Read

        (*p) // Used inside an expression

        
        

Some issues with the memory API that must be addressed are the following, which will be expanded upon in later lectures:

• Total Size - The memory abstraction may be scaled as far as the total size of physical memory may allow
• Word Size - A word (normally a small integer number of bytes) must be defined
• Coherence - Whether the most recent Read is the same as the most recent Write and the presence of atomicity (The assumption that every memory operation is executed completely before or after another memory operation). While these properties seem obvious for physical memory, issues such as concurrent users and delay may threaten the integrity of these assumptions.
• Speed - Throughput and latency (often called access time) of physical memory are limiting factors that affect the abstraction
• Volatility - Refers to the persistence of data in physical memory depending on whether or not a power supply is presence.
• Linear vs. Associative Addressing - The mechanism for memory accesses may be linear (the address space is composed of consecutive integers) or associative (maps higher-level names to the underlying linear address space). Some constructs such as cache may be implemented with associative addressing, which imposes in either hardware or software an "associative layer" that maps higher-level names to the lower-level addresses.

Interpreters API

        
        v = f(p)
        // p is the input program
        // f is the interpreter to which the program is given
        // v is the answer output by the interpreter
        
        

The interpreter abstraction describes the actions taking place in a system. By layering several instances of this abstraction in both hardware and software, extremely high-level processes may be realized, such as from machine-level instructions to a word processor. To achieve efficiency, the interpreters API also requires hardware support, which is seen in such instances as the CPU. The API is defined by 3 properties:

• Instruction Pointer - Indicates where in a program the interpreter should find its next instruction
• Environment Pointer - Indicates the state of the environemnt on which the interpreter acts
• Repertoire - A mapping from an input instruction to the set of behaviors the intepreter should exhibit upon receiving that instruction.

The connections between successive layers of interpreters abstractions may be extablished using interrupts. In this sense, upon reaching an interrupt instead of executing the next instruction a different program takes control of the interpreter, thereby changing out the interpreter's instruction and environment pointer

The Interpreters API should also be "safe". The definition of "safe" depends on both what sort of restrictions on access should be imposed onto the user as well as how much performance should be achieved using the API. Balancing these aspects requires virtualizing the processor and controlling how much direct hardware support for the user should be integrated into the API.

Priority in Virtualization

1. ALU (Arithmetic Logic Unit); Registers - User code should have direct to the ALU and registers at full speed. This sort of hardware support is crucial to the interpreters API to achieve desired behavior. The presence of cache should have no effect on the program's behavior other than on its speed.
2. Primary RAM - The user should have full access to some physical memory. Through virtualization of memory, such restrictions may be enforced.
3. I/O - Relative to other instructions, I/O is extremely slow. Because it is already so slow, giving the user no direct access and sacrificing performance makes no significant difference.

Link API

The link abstraction allows communication between distributed machines by passing messages, the main advantage of which is that machines may be located anyhere. By abstracting the OS from the machine, the kernel can be located anywhere. For example, Macintosh OS X relies heavily on the link API.

As with the former two abstractions, the Link API is simply defined:

          
            Send(link_name, outgoing_buffer)

            Receive(link_name, incoming_buffer)
          
        

A significant disadvantage, however, is that data to be sent on communication links must be serialized, meaning it must be in a specific format such as XML, which may not be possible for all data types such as pointers. Such a high-level abstraction will naturally come with performance issues as well.

An Object-Oriented Operating System?

An approach to implementing an operating system is an OO approach such as that of Windows. We may write classes for I/O, buses, memory, and the interpreter, but as with most OO approaches we suffer a performance price.

Layering

Operating systems make sure that application access intructions properly. Some instructions are dangerous if performed maliciously. For example, the halt and catch fire command stops the fan and let the computer burn or using the read and write commands on global memory where they can access memory outside of the program, which is bad normally. Therefore, we need to check an instruction before execution. However, if all the instructions are checked and performed, the computer would be ridiculously slow. So, we classify the instructions into two types:

• Unprivileged instruction
• Privileged instruction

Unprivileged instructions are the safe instructions. They are executed on the hardware without check. Privileged instructions are the dangerous ones. They need to be checked before execution. Thus, they are passed to the kernel to ask for its permission to run, so the kernel can decide whether or not run the command. The kernel then uses system calls to perform the instructions. This strategy is called layering.

There are two ways of visualizing layering.

Wedding cake diagram

The wedding cake diagram shows a logical view of how this works. it shows on the bottom the hardware level, which only the system calls can reach. It shows how the unprivilaged code can be reached directly by the user, while there is an a layer above the unprivilaged commands where the user first bypasses the kernel before they get tot he hardware. Above this, there can be added more layers before the actuall user where the user gets pretend code that ends up calling the real code after bypassing a few layers.

Ring diagram

The ring diagram is another way of representing the same thing. Each additional ring represents a possible layer that can be used before the actuall apps the user is able to see.

Operating System + Virtualizable Processor

This virtualizable processor let you support a process

Process: Program running in isolation (on a virtual interpreter)

By using virtual processors, we can run several processes all at once by jumping from one to another. This can be done as we store the state of a process and switch to another, and then come back to the original later.

Accessing Memory

Each process has its own view of memory.

In between two processes, there are parts of the memory that are different, and some parts that are shared. Areas of memory like the C libraries and innate commands of the kernel are shared, as represented int he picture above by 'cat' executable and C library. These shared memory is read-only memory. Other parts of memory, like I/O buffers, and the stack is represented for each process individually. These are considered private for each process and can be rewritten by the respective process it belongs to.

To create a child process from a currently running process, the fork() command can be used.

pid_t fork(void);

pid_t p = fork();

pid_t is an innate C type used to describe process IDs.

This fork function will return to the child 0, in the code above p=0 for the child.On the other hand, it will return to the parent process the process ID of the child.

If there is an error, such as it cant create any more processes, it will return -1.

if(fork() == 0)
  printf("I'm a child\n");
else
  printf("I'm a parent\n");

Fork bomb

refers to endlessly making new processes untill the program can't continue(fork returns -1)

Example

while(fork() == 0)
  continue;

This will cause every new process made to create a child process of its own and go on linearly untill it returns a -1 and sett errno.

Another example is:

while(true)
  fork();

Which will break faster than the previous example.

PROCESS TABLE

Your computer has only one physical cpu, while it can run more then one processes at the same time. How does it happen?

In order for a single processor to run multiple processes it has to switch mid-process between the different processes. To do that, between every switch, it keeps track of the current process by storing its state and registers to memory (the process table) while loading the next process's state and registers to start running.

The process table above shows how the processor stores processes while they are not in use. The rows in the table represent the different process by their ID whilethe collumns represent which part of the process state is being stored, such as all the registers and the process state. A process not in use (process 12 in the table) holds values we do not care about, junk memory. A process like this could be used when fork is called. When fork is called, it copies most of the process state from the caller to the new process, which is chosen from one of the unused processes. Registers like esp and eax will not be copied directly. esp since the new process will have a stack of its own somewhere else in memory, and eax since fork() will return a 0 to the child and the process ID of the child back to the parent(the fork is shown by process 23 and 52).

Changing between one process and another works similar to:

read(file_descriptor,buffer,1000) //save the current process
INT 0x80 //resume some other process with a state of runnable process

In order to destroy a process, nothing needs to be done on the programmer side, processes destroy themselves.

This system call below is used to exit a process once we are done with it. The intiger that is passed in as an argument is the exit status of the program.

_exit(int);

The exit function below is the one more commonly used in programs. This exit function is a library function that first flushes the output buffers and then calls the _exit system call after.

_Noreturn void exit(int);

The noreturn clause is used to signify that this function will not return, so there is no need to make any special preparations for it (for example, there is no need to set up the return address in the stack, since it will never be used).

An exit status of 0 is considered a success, while any other exit status (from 1-255) is considered some form of error.

When a process exits, its process state is changed to that of a zombie, which means that int he process table, all the values other than the exit status which we still care about is considered junk.

Once the waitpid command is called on the exited process, its memory is finnaly freed, and its state changes to that of an unused process, so the process ID can be reused. It is in a way works similarly to a process destructor. While the process is waiting on another process, its state is shifted to blocked, and this allows another process to run in the meanwhile without having the process that called waitpid have to use processing power.

pid_t waitpid(pid_t,int*,int);

waitpid takes in as its first argument the process ID of the waited-for process. Its second argument is the location used to store the exit status of the waited-for process. The third argument is flags used with waitpid. Something like WNOHANG which makes it so we no longer wait for the process, but rather if it did not yet exit, we kill it and put a 0 for the return value, if it did exit in time, this function returns normally. waitpid return -1 if an error occures and the process ID of the child process whose status is reported if it succeeds.

true.c
int main(void){
  return 0; 
}

The cat excecutable is made of some glue code that is used to tie it back to the overall process that called it when it is done running and object code cat.o that represents cat's main program linked in the excecutable. The glue code is something like a:

exit(main(~~,~~));

where it takes the return value of the main function for cat and uses it as the exit status.

PIPE

The pipe command bounds a queue of bytes stored in kernel memory.

int pipe(int file_descriptor[2]);

Pipe takes in as an argument an array of 2 elements of type int and uses them as a file descriptor (1 read, 1 write). The reading hangs if there was no data written yet or it gives the data stored there if there is some. pipe can be used with fork in order for a child and parent to communicate with one another.