Process Interaction

System calls

System calls are about how processes interact with the OS. Most (if not all) OS provides and API(Application Program Interface) for the process to talk to OS. It provides a way of calling facilities/services in kernel, and is not the same as a normal function call.

The OS has almost exclusive control over all hardware on the system. What this means is even if you want to do something as simple as printf, it needs to call the OS to print something onto the screen. Other more obvious cases include when we open/write/read a file.

This is not normal function call as we need to change from user to kernel mode (since OS has to access hardware and various part of memory that normal processes cannot access). In a normal function call, the process remains at user mode.

Unix vs Windows

Different OS has different APIs. For example, Unix follows the POSIX standards, which is relatively simple at about ~100 OS calls. It is used by just about every unix-type OS like MacOS.

While macOs make avail entire posix api, some are not implemented. e.g. semaphores. Though you can create, when you use, it pops up correctly but functions do nothing so the program fails. So just because the OS has the API available, it doesn't mean they are implemented.

Windows on the other hand uses Win API, which are different across different window versions. So they add new calls for new capabilities nad some window versions may drop support for older calls not being used. This is very complex with ~1000 calls.

Unix System Calls

In C/C++ programs, system calls can be invoked almost directly. There are 2 ways of invoking system calls.

• Library version: When we have the same name n parameter as the underlying system call. In this case, the library version acts as a function wrapper (also called a binding to call the API).
• User friendly library version: The library acts as a function adapter.

printf

printf allows us to specify format string but itself does not actually write to screen. Instead, it makes a OS call to a function known as write (more primitive than printf as it requires info to be in a series of bytes (byte stream)).

So printf is an adapter by taking the format string and our information, laying everything nicely into a series of bytes then calling write to write to screen. It simplifies calls by doing the formatting for you.

Examples

#include <unistd.h>
#include <stdio.h>

int main()
{
    int pid;

    pid = getpid();

    printf("processid = %d\n", pid);

    return 0;
}

getpid() gets the process id for the process and calls printf to print the process id. It is a function wrapper as it has exactly same param and name as underlying OS call and it gives a convenient high level way of making the OS call.

printf() is function adapter by processing before calling write.

How do we actually make system calls? What goes on behind our function adapters?

Firstly, the user program invokes the library call (which is just a normal function call) using the normal function call mechanism. However, the library call is actually quite complex e.g. a lot of getpid has to be implemented in assembly code as it has to place a system call number in a designated location, usually a register.

The system call number specifies what action to take. After which, the library executes a special instruction TRAP which switches CPU from user to kernel mode.

Once in kernel mode, the appropriate OS handler is called (sys call number put into register earlier is used as an index) and the bit of code known as the dispatcher will use this index and call the correct function to execute the system call. This is similar to the vectored interrupt.

System call handler is executed which carries out actual request, and when call handler is ended, control is returned back to the library and we switch back from kernel to user mode. After which, the library can then return to the user program (via normal function return mechanism).

Illustration

Here we have main that calls getpid, and we have getpid() itself. getpid makes use of assembly language to put the syscall number into a register. All thing OS can do identified by syscall number (not same as pid, just tells os what to do)

switch to kernelOSswitch to userreturn

syscall number is placed into some register x then getpid executes TRAP, which triggers the OS and a switch to kernel mode.

The OS itself has a dispatcher and the actual systemcall handler for this particular module . There will be a call handler for printing to screen, reading from keyboard, and in this case getting the process id.

Control is handed to dispatcher, dispatcher looks at content of register x and calls the appropriate systemcallhandler.

When system call completes, control is handed back to the dispatcher and back to the getpid function, where we make a switch from kernel back to user mode.

Finally, getpid returns to main.

Exception and Interrupts

What are exceptions? When you execute instructions e.g. add sub etc. (not high level instructions), it can cause exceptions. Generally speaking, it is some kind of error. Some error include:

• Arithmetic errors
  • overflow/underflow
  • division by zero
• Memory error
  • illegal memory access/segmentation fault (when process access memory belonging to another process)
  • mis-alignment memory access (instructions can only be loaded at word boundaries i.e. address divisible by 4, if not then is a mis-align memory access which triggers bus error)

An important property of exceptions is that it is synchronus -- they occur due to an instruction execution. In other words, it will always be aligned with the instruction.

When there is an exception, similar to OS calls, the OS also has special bits of code that handle exceptions. An exception handler is executed automatically, similar to a forced function call.

Interrups

Interrupts are similar to exceptions yet quite different. Interrupts are caused by an external event (which interrupts execution of a program). In your cpu there are usully a series of lines aka interrupt requests. For simplicity, we assume they are on cpu itself. These are hardware lines connected to various devices e.g. keyboard.

When a key is pressed, keyboard hardware raise the IRL from low to high. When the CPU sees that the request line is high, it knows the hardware has asked for attention.

Intel

In intel cpu, these interrupt request lines are part something known as interrupt vector controllers.

Another key piece of equipment that uses interrupt lines is the timer. It is behind how our OS can run even when our process runs. A timer is a piece of hardware that triggers interrups at fixed intervals (different from clock that synchronize hardware). It produces low to high at fixed intervals e.g. 1ms

So interrupt requets lines are used by the hardware to ask for attention from the CPU. If you recall from CS2100, the instruction execution cycle goes thru 5 stages (fetch, decode, execute, memory writeback). Usually, interrupt service request checking is done at the end of writeback stage. The CPU checks all hardware lines and see which is high to perform necessary actions

Generally since hardware runs independent of software, interrupts are asynchronus and can occur in the middle of an instruction. (when you press a key, the rate you press is independent of instruction execution) So the event that occurs is independent of program execution.

Similar to exceptions, when interrupts occur, the program execution is suspended and an interrupt handler is executed automatically -- based on which interrupt line is triggered, the OS executes the appropriate interrupt handler. So every bit of hardware has its own interrupt handler.

void f() {
    ...
    statement s1;
    ...
}

Let's take a look at an example. At this point, function f is executing and is at statement s1. It is useful to think of s1 as a machine level instruction instead of a high level as high level is broken down into multiple machine level instructions.

While executing s1 a interrupt (caused by hardware, independent of program execution)/exception occurs (casued by instruction, synchronus to that instruction)

In both cases, the OS transfers control to a handler routine automatically. What the handler does is it saves register/CPU state (same reason that functions have to save the values of the registers, i.e. when handler completes and returns control to f, it has to have register values intact and not altered in any way)

It then performs whatever it has to do (the handler routine), restore the register/CPU state and perform a return from interrupt, which casues control to be handed back to f.

Program execution should resume and generally may behave as if nothing happened. (especially for interrupts)

Interrupt Handler

Now you may wonder -- if there are different handlers for different interrupts, each in a different memory location. How does the CPU know which handler to invoke?

We have various interrupt process lines which are scanned to see which are high. The CPU then consults the interrupt vector table based on the lines. For exceptions, the CPU will consult the vector table to find address of appropriate handler based on exception number.

Once it has found the address of the appropriate handler, it performs what is pretty much a function call. It saves the PC, load the address of handler which causes it to execute, then when we return from interrupt, the saved PC is loaded back to the PC, causing execution to resume after the interrupt.

This is different from a normal function return as it usually achnowledge the interrupt to hardware.

The hardware raise the line from low to high then when we execute return from interrupt, CPU can force line from high to low , so hardware knows its request has been processed.

keyboard

When a keyboard key is hit, it triggers an interrupt request. The CPU saves the current PC, consults the vector table and invokes the handler for the keyboard. The handler read char from keyboard, perform return from interrupt to tell the keybaord char has been read.

Process abstraction in Unix

We will take a look at how unix implements system calls. Processes in Unix include: - identification (PID) - information about processes (unix command ps) - Process state: running, sleeping, stopped, zombie - Parent PID - Cumulative CPU time (total CPU time used so far) - creation and termination - parent-child synchronization (process can create a child).

The amt of CPU time used can be used by scheduler to decide whether a process should run and how much time the process should be given. For a process that has used a lot of CPU time, the unix scheduler can decide to not run process yet and give other processes a chance to run.

Another important use of CPU time is that if u make use of cloud services like digital ocean etc, if u use beyond a certain amount of CPU time you'll be charged extra.

fork

One of the posix calls in unix is fork(). It allows us to create a new process, and returns either pid of newly created (to the parent) process or 0 to the child.

#include <unistd.h>    /* header */
#include <sys/types.h> /* files */

int fork();           /* syntax */

Note that header files can by system dependant, so you may want to 'man fork' to find the correct files.

Fork create new process (child) which is an exact duplicate -- same code and same address space, but data is a COPY (not shared) of the parent, even for global variables. So the child process is a duplicate of the current executable image.

The child only differs in its own PID, Parent PID (PPID) and fork() return value.

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main()
{
    printf("I am ONE\n");
    fork();
    printf("I am seeing DOUBLE\n");

    return 0;
}

The above program first prints I am ONE. Then, it forks and has a parent and child process. Both parent and child resumes at the statement immediately after the fork, and both prints I am seeing DOUBLE.

A common usage is to use the parent/child process differently. For example, the parent spawn off a child to carry out some work, while itself is ready to take another order.

Web server

A common usage is in web servers. The parent can be waiting for http(s) calls. When a request comes in, the parent spawns a child to take over conection to serve client. Meanwhile, parent continues waiting for another http call and spawns more child if got another http connection etc.

But now how do we know if we are the parent of child (since there are different things to do)? We can make use of the return value of fork (for parent, it returns the PID (non-zero value) and for child returns 0)

    ...
    int result;

    result = fork();

    // both parent and child will have exact copy of code here
    if (result != 0) {
        // executes in parent which result is child PID
        printf("P: My id is %i\n", getpid());
        printf("P: Child id is %i\n", result);
    } else {
        // executes in child which result is 0
        printf("C: My id is &i\n", getpid());
        printf("C: Parent id is %i\n", getppid());
    }

Another thing about fork is that it has independent memory spaces. Aft fork, both parent and child have exact same code, variables but in diff spaces. (each has own version)

    ...
    int var = 1234;
    int result;

    // both parent and child will have exact copy of code here
    if (result != 0) {
        // executes in parent which result is child PID
        printf("P: Var is %i\n", var); // 1234
        var++
        printf("P: Var is %i\n", var); // 1235
    } else {
        // executes in child which result is 0
        printf("C: Var is &i\n", var); // 1234
        var--
        printf("C: Var is %i\n", var); // 1233
    }

The key thing here is that parent and child has their own version of var and result and thus execute differently.

Actually, fork() itself is not very useful -- you still need to provide the full code for the child process. What if we want to execute another existing program instead?

exec

To do that, we can make use of an exec() (it is a family of calls with many variants, which do exactly the same thing, but take in different arguments). We will focus on execl.

exec variants

Other variants include execl, execle, execlp, execlv, execv. Those that has v takes in environment variables such as PATH, which OS uses to locate executable files.

Command line argument in C

In C, you can pass arguments to a program. For example, a.exe 1 2 3 hello. But how do we access these arguments? main(int argc, char* argv[]) takes in 2 parameters argc and argv. It may seem strange why main takes in parameters when we cannot actually call main, but the OS calls main and pass in these arguments.

argc tells you the number of command line arguments (including program name itself, so 5 in our above example) and argv is a char strings array and each element in argv is a C character string containing individual command line arguments.

int main(int argc, char* argv[])
{
    int i;

    for (i = 0; i < argc; i++ ) {
        printf("arg %i: %s\n", i, argv[i]);
    }
    return 0
}

Here, we have a for loop which iterates over all the elements in argv. %s is used for string (from argv[i]) while %i is used for int from i. The output will be like below

a.out 123 hello world

arg 0: a.out
arg 1: 123
arg 2: hello
arg 3: world

Note that arg 0 is always the name of the program.

execl

What the exec family does is replace current executing process image with a new one. What this means is whatever code that was in the child will be replaced by code in the program you execl. So there is code replacement but PID and other information remains intact.

#include <unistd.h> // header file

int execl(const char *path, const char arg0*, ... const char *argN, NULL); // syntax

The first argument will be the path to program to execute, 2nd is the name of program and the rest are series of args to pass in (variable length of arguments), terminated by a NULL Note that the path can be relative or absolute, and that program name and path may not be the same.

int main()
{
    execl("/bin/ls", "ls", "-l", NULL);
}

// exactly same as executing "ls -l" 

fork and exec

How do we use both? By combining the two mechanisms, we can spawn off a child process, where the child process can do exec which replace its process image with the image of the pogram it is executing. Meanwhile, parent process still arnd can still accept another request. Funfact, this is how your OS shell works!

Windows

To run windows, you will click on the windows icon then a program name. The windows shell will spawn a new process and take its program and replace the process image with this program process image. eanwhile, the windows shell can now accept new requests to run other programs.

The reason it can do that is that the windows shell (which is the parent) monitor mouse clicks and movements. When you run a program, it does windows equivalent of a fork to create a parent and a child. The child executes the windows equivalent of exec and load another image (and now be the running program) while parent continues to monitor mouse clicks etc.

For unix, when you run ls, bash launches a child process which perform exec to execute ls and image of ls replaces child while the parent goes on to receive new commands. This combination of mechanism is the main way to get a new process for running a new program.

Master Process

You may wonder, if every process has a parent, is there a common ancestor? Well, yes! There is a special initial process known as init, which is the 1st process created by kernel close to end of booting sequence. It traditionally has a PID of 1 and it watches other processes and respawns them if needed. If a process dies but is essential, will respawn the process.

fork() produces a process tree with init as the root process. When init starts up, it performs fork() to create children and in turn these forks executes exec to startup important things like inetd and klogd (they run things like internet stack, perform logging)

Another important process it runs is the login process which spawns a child which uses execl to load bash. Bash is usually reside in /bin/bash. If you perform e.g. ls in bash, bash itself will spawn a new child called ls.

Process Termination

But now what if a process wants to terminate? We have a function exit which takes in a status code. In Unix convention, 0 is a normal termination and non-zero indicates a problem. This information is written to the parent process. An important point of exit is that it does not return.

When a process executes exit, it has finished execution. Most of the system resources used by the process are released (e.g. file descriptors - tells which file process uses), memory used by proces etc.

Some basic resources are not released, such as PID and status returned, as they are neede for parent-child synchronization. Other information like CPU time for process accounting are also not released. These remain in the PCB after process exits.

Most programs do not have an explicit exit() call. When main exits, the exit() call is implicitly called. If you return 0, the exit call gets called with 0 (i.e. whatever value you passed). The value is then passed to the parent of the process (if in shell, parent is the shell). The shell can then detect the value to examine if there was an error in the program execution. Open files also get flushed automatically.

file descriptors: tell what files the process release, mem process is using etc

status returned not released + cou usage time remain in process controller

Parent-Child Synchronization

Parent process can wait for the child process to terminate, believe it or not, with the system call wait(int *status). It returns the PID of the terminated child and, if you specified an argument, it also returns the status returned by the child when it called exit.

#include <sys/types.h>
#include <sys/wait.h>

int wait(int *status);

status stores the exit status of the terminated child process, and you can use NULL if you don't want the information.

The behaviour of wait is blocking, so the parent will wait(block) until at least 1 child returns. This call cleans up the remainder of child system resources.

When the child exits, its PID, cpu state and return result remains in proccess control block. When the parent calls wait, this entry is removed from process table. The entire child PCB is removed from process table freeing up space. This is also called killing zombies.

There are other variants of wait like waitpid() which allows you to wait for a specific child and waitid() which waits for any child process to change status.

Now let's take a look at the process interaction in Unix.

breakdown

forkparentchildexit

A fork/exec creates a parent process, usually from shell

The parent itseldf executes fork to create a child process

This child can execute execl to run another program, replacing child image while everything else stays the same (program code and variables etc replaces child). Meanwhile, the parent executes a wait and will block.

Only when the child exits the parent will open up. The child transits into a zombie state (all child resources clean up except pcb entry which contains info about child and return code for parent)

until the parent executes a wait to clean up (cleans up entry in process table) child entry, after which child properly terminates.

Zombies

wait() is the reason we have zombies. It is a process that has already terminated but its PCB entry still exists in the process table. This happens as we may need to pass information from the child to the parent. Information is passed through PCB entry of child.

When parent calls wait, this information is read by parent, where it is then removed. But until parent executes wait, it remains stuck in table (in zombie state). Once the parent executes wait, and PCB is removed, the zombie dies. There is no other way to kill zombies as it is already dead.

There are 2 cases with zombies. If parents process terminates before child, init becomes the pseudo parent of the child process. When it terminates, it sends a signal to init which performs wait to perform a cleanup.

The second way is more troublesome. The child terminates before the parent, and if the parent doesn't call wait before exiting, the PCB entry of the child remains stuck in the process table and will never be removed. The child becomes a zombie process and if this happens often enough, the entire process table becomes full and you cannot create new processes.

In older unix systems, you'll have to do a reboot to clear the table! Luckily, newer unix system are zombie resistant as os runs a program that runs through table and periodically cleanup entried that do not correspond to any process.