Lecture 4 Notes written by Ziaurehman Amini & Alyssa K. Marteja
How to Organize an Operating System

An ideal operating system must be able to “talk” to you (i.e. take and understand user input),
utilize devices such as disks, keyboard, and networks, handle multiple users and run even the flakiest applications.
The following are ideas and problems one must consider when organizing an OS.

1. Modules

One way to organize an OS and simplify complexity is by breaking it up into well-defined pieces called modules that can communicate with one another.
Unfortunately, modularity cannot do the job alone. Modules are just code and do not tell how the OS will truly behave when used.

2. Object-Oriented

An OS must also organize the data being operated on. Within each module, data can also be broken up into pieces and therefore,
the OS can be perceived as one big object-oriented program. However, if one flaky class is present in the OS, the whole system may crash.
In other words, the OS does not scale in the presence of any unreliable applications.

 

One must create an OS that is robust to avoid such disastrous events. In order to do so, one must ask what sort of application problems
should an OS worry about being able to handle?

Possible Problems When Dealing with Applications

·         Data is stored in and/or loaded from objects it should not.

·         Memory leakage; the application allocates resources that is unnecessary.

·         The application runs an infinite loop.

·         Application attempts to access memory and devices that are not there (i.e. pointer points to NULL).

·         The application is too big for the system.

With these problems in mind, what is the best way to go about solving them? The universal method is to build a virtual system on top
of the real system so that applications, if defective, only impair the virtual layer.

3. Fundamental Abstractions

A. Link Application Programming Interface (Link API)

This protocol consists of applications communicating over a network through links. The primitives that run in the virtual system are send() and receive().

B. Memory Application Programming Interface (Memory API)

This API deals with storing in (i.e. *p = v) and loading from (i.e. v = *p) memory.

C. Interpreter = code + p + ep + data

Interpreters are active elements of a computer system; they perform the actions that constitute computations.

 

Virtualization: x86 Emulator

The simplest form of using a virtual layer to protect against defective applications is writing an x86 emulator
that will look for the previously mentioned application problems and that will make sure an instruction follows the rules.

1. Performance
   This is a reliable method, however, the problem – and a big problem at that – is its performance. For example,
   the emulator uses a halting code like waiting for 100s to solve the issue of infinite loops and although this works,
   is extremely slow. This problem can be solved by having the emulator see the first instructions that have
   unproblematic code, execute those, and only emulate those that do not follow the rules.
2. Hardware Support
   By using hardware support, emulating is nearly as fast as using bare hardware.

         =>Emulated IP = hardware IP
        =>The hardware support is used to detect dangerous instructions. When an encounter occurs,
            the hardware must stop executing and let the operating system handle it.

The Virtualizable Processor

With a virtualizable processor, dangerous instructions should be rare (i.e. 1/1 Million instructions, great for
performance) and do not get executed without software intervention.

When such an instruction is encountered, the hardware sees it, traps it in the operating system and the kernel takes
control and decides what to do. It is up to the kernel whether or not the hardware should proceed and it can change instructions
by terminating them, continuing them, or alternating the applications.

Types of Instructions

Privileged Instructions - DANGEROUS

1. Invalid instructions to applications
2. HALT
3. INT - pretends there is a hardware interrupt

        => example INT k, k = [0,255]
        => can execute privileged instructions, unlike JMP protected transfer of controlin which the kernel can then execute privileged
              instructions and apps cannot. If apps could, they would be able to do anything and the chances of damaging the system would greatly increase.
        => See “What does an INT do?”

Non-privileged Instructions

1. ADD
2. SUB
3. MUL, etc

The OS can execute all instructions while applications can execute non-privileged instructions only.

 

What does an INT do?

Linux Kernel Convention

%eax    syscall #
%ebx    arg 1
%ecx    arg 2
%edx    arg 3
%esi    arg 4
%edi    arg 5
%ebp    arg 6

Below is an example of what takes place when INT 128 is called.

pushes SS        (start stack segment)
(onto    esp       (stack pointer)
stack)   eflags
             cs        (code segment)
             eip       (instruction pointer)
             error code

The steps taken above is automatically done by the hardware and the routine ends using the RETI function which pops the INT 128
list above and signals the flag that it is no longer in privilege mode. A simple note to remember:

              RETI:RET :: INT:CALL

The problem with INT and RETI however it is that it very slow compared to CALL and RET. This is because of their heavy weight
operating. However, they wall off applications which is necessary.

ABI: Application Binary Interface

An ABI describes the low level interface between a program and the OS or another program. Specifically, ABI deals with data types
(i.e. their sizes and layouts), function calling and returning conventions, system calls etc.

An OS can be built in a layered way, in which each level deals with a different issue and/or device. x86 supports 4 levels. However,
Linux deals with only two layers, one for privileged and one for non-privileged instructions. In other words, it is only concerned about levels 0 and 3.

          

Looking at the ABI, the OS kernel blocks applications from executing privileged instructions and controls application access to the certain resources:
ALUs, memory cache, primary memory, I/O devices, Time, and registers. For example, after the OS allows it, an application can use any of its own registers
directly but is completely blocked from the registers of other applications.

But how does the OS kernel keep track on which registers belong to which application? The answer is a process descriptor table. This structure
records the states of all resources of all applications running and helps the kernel choose which registers, devices, and memory space an application is allowed to access.

The Process Descriptor Table

It contains an entry (one row) per process. The row contains, process ID, copy of the stack and virtual registers. This information is primarily useful
for context switching. For context switches, the current register values of the process we are switching from are stored in the virtual registers to save the state
of the process being suspended. The kernel only needs to save and restore the registers it uses. For example, getpid() is cheap to run in an interrupt. 
Similarly, generally the floating point registers don't need to be saved/restored, unless they are being used. The more complex the kernel is the greater the overhead of the syscall is.

 

Application Programming Interface (API) For process manipulation:

Definition: A process is an instance of a computer program. Each process has its own virtual address space and contains one or more threads.

 

Creating a process (forking)

Processes are either created by a parent process or the kernal. When one process creates another, the creator is called the parent and the new process is called the child process.

A process can be created in C using:

              pid_t fork(void);

fork() creates a child process by cloning the parent. By cloning, we mean that the following are copied from the parent process to the child:

1. Registers
2. Signal Handlers
3. VM State
4. eip (the instruction pointer)
5. The file descriptor table

A natural question at this point is, how do you differentiate between the child and the parent if all of the above are the same for both. Fortunately,
fork() returns two different values. To the parent process, it returns the proccess id (pid) of the child process, which will always be a positive integer.
To the child process, it returns 0. In case of an error, fork() will return -1 to the “parent” process.

Some common reasons why fork() may encounter an error

1. There may not be sufficient memory to copy the parents page tables and allocate a task structure for the child process. This refers to
   the EAGAIN (resource temporarily unavailable) error.
2. You have reached the maximum number of processes you can have running at a time. This could occur on the seasnet Linux Servers
   where each uid is allowed a maximum number of processes it can run. On computers where you have administrator privileges, this limit can be changed by editing the RLIMIT_NPROC.
3. You may be out of entries in the Process Descriptor Table.

Destroying a Process

A process can only destroy itself. It may not attempt to terminate another process. In C, a process self-terminates by calling:

              Noreturn void _exit(int status)

The status argument can be 0, EXIT_SUCCESS, EXIT_FAILURE, or any other value. One thing to note here is that while a process can enter a full length
integer as its exit status, its parent will only have the lower 8 bits of status available to it.

 

When a process calls _exit, all of the file descriptors, directory streams, conversion descriptors, message catalog descriptors open in the calling process are closed,
and the process will no longer be scheduled for execution. However, it still occupies an entry in the process descriptor table and the pid is still assigned to it. This is because
the process might have some vital information, like its exit status, to convey to its parent. At this stage, the process is called a zombie. Taking this information from a process after
it becomes a zombie is called reaping.

Right after a process becomes a zombie, if the parent is waiting on it, the parent reaps it. If the parent is not waiting the zombie, it will keep occupying the entry in the
process descriptor table and will continue to hold on to the pid. It is expected, but not always the case, that before exiting, every process will reap all its children.
A parent can wait for its child process to finish executing by calling the C function:

         pid_t waitpid(pid_t pid, int * status, int options);

We see that this function takes three arguments:

1. pid_t pid: This is the process id of the child process it is waiting on. It is often a value returned to the parent by fork()
2. int * status: This is where the child stores its exit status. Remember that only 8 bits of status will be available to the parent.
3. int options: This is usually 0 if the parent simply wants to wait for a certain child process to finish execution and then reap it. However, you can only wait on a process once.
   So if you simply want to reap a child process if it has already terminated, without waiting for it if it is still executing, you can enter the option WNOHANG.

 

Optionally, if instead of waiting for a specific child process to terminate, you want to wait for any child process, you can use the C function:

         pid_t wait();

Earlier, we said that every process would ideally wait for all its children to terminate and reap them before it terminates itself. However, there is nothing in the system to ensure this.
One process can create many other processes and terminate itself without reaping its children. Then when the children eventually self terminate and become zombies, what happens to the
resources that are still allocated them? In this case, the process still has to be reaped. It is conventional for a zombie whose parent has exited to be reparented to “process 1”.

Process 1: In most systems, including Linux, the first process created by the kernel is the init. It contains an important while loop that takes care of zombie processes that are reparented to it:

         while(waitpid(-1, &i, 0)

         continue;

The -1 indicates that we should wait for any process to terminate and reap it when it becomes a zombie.

Here is an example to clarify and show how a process can be created, terminated, and reaped:

void

printdate (void) {

pid_t p = fork(); // Clone current process. Returns pid of child to parent and 0 to child.

switch (p) {

case -1: // fork() will return -1 to the parent if it is unable to create a child process.

error(-1);

break;

case 0: // If successful, fork() will retun 0 to the child process.

// Thus this case will only be executed by the child.

execvp ("/usr/bin/date", (char * [2]) {"date", NULL}); // Code to return date.

error(0);

break;

default {

// This case will be executed by the parent only.

int s;

if (waitpid (p, &s, 0) != p) error(1); // Parent waits for child process. if (WEXITSTATUS(s) != 0) error(2); // If there is no error, the exit status of

// the child process should be 0.

break;

}

}

}

void

error(int errorCode) {

switch (errorCode) {

case -1:

printf( "There was an error creating a child process, perhaps due to lack of resources \n");

break;

case 0:

printf("There was an error using execvp \n");

break;

case 1:

printf("Error waiting for child process \n"); // This could happen if the funtion

// was interrupted by a signal, or if p has already terminated and been

// reaped Or if p does not exist for any other reason.

default {

printf("Child did not terminate with exit status 0 \n"); // Natually, the child will return a

// different exit status if it had an issue.

}

}

}