Process Abstraction

To create processes, we have something called process abstraction. This model tells us we have 3 context in the process -- memory, hardware and OS. Processes also require management, so we have the process control block and process table.

But, why do we care about processes? We want our system to be able to run multiple things at once to efficiently use our hardware. However, switching between 2 programs can lead to problems (programs using same registers, messing up results)

When switching between programs, you have to:

• Store information of current register values program A uses
• When program B starts, the values saved from register B will be copied into the registers (restored from memory) while those of A are stored in memory
• Process executes

thus, we need an abstraction (process) to describe a running program (contains information). There are 2 important context when managing processes -- hardware (set of registers) and memory (information on where data is).

The 4 key topics are:

• Process Abstraction: Data maintained about a running program in order to manage it, e.g. saving and restoring context, maintaining information about CPU time used by process
• Process Scheduling: How to decide what process to run next
• IPC and Synchronization: How to get multiple process to communicate
• Alternative to Processes: Light-weight process (Threads), managing less processes with efficient use of CPU

A process/task/job is a dynamic abstraction for program execution it includes information about processes which changes as it runs. e.g. as program run, register and memory content change, close open files, OS contents change.

Memory context	Hardware Context	OS Context
code, data	registers, PC, stack & frame pointer, status regsiter	process properties, resource used

OS Context

OS context has information about processes (process properties) and resource used by process. Another big thing is file information (when you open a file, the OS tracks which file is open bby who and at which point is the process in).

Here, we have a sample C program and assembly code:

int i = 0;
i = i + 20;

where the MIPS-like assembly code looks something like this:

1024 addi $1, $0, 0 
1028 sw $1, 4096 // initialise i to 0
1032 lw $2, 4096 // load i to s2
1036 addi $3, $2, 20 // add 20 to i
1040 sw $3, 4096 // write back to i (mom location 4096)

here we have machine instructions addi, sw etc. (that occupy memory location 1024-1040) and data/var (i, occupy mem location 4096). So our running program occupies 2 parts of memory.

The first part of memory containing mahcine instructions is called text and the part containing gloabl variables is data`.

CS2100 Recap

Components

• Memory: Storage component for instruction and data
• Cache: Duplicate part of the memory for faster access, usually split into instruction cache and data cache
• Fetch Unit: Loads instruction from memory, location indicated by a special register (Program Counter)
• Functional Units: Carry out the instruction execution, dedicated to different instruction type
• Registers: Internal storage for fastest access speed
  • General Purpose Registers: Accessible by user program
  • Special register: PC, Stack Pointer, Frame Pointer, Program Status Word

Basic Instruction Execution

Instruction x is fetched (its location indicated by PC) and dispatched to corresponding functional unit. If applicable, operands are read(usually from memory or GPR), the result is computed and if applicable, value is written (usually to memory or GPR). When completed, PC is updated for next instruction.

An executable(binary) consistes of 2 major components -- instructions and data. When talking about binary, we are essentially talking about the program file e.g. winword.exe on the disk drive. When you open the file in an editor, it has a header beginning with MZ -- magic number that tells OS this is a valid executable file it also tells how much space required for global varoable segment, store initial content of global variables and rest of file stores machine instructions. When sitting in disk drives, all it contains esentially is data and instruction. (MZ also the initials of the person who designed the .exe format)

Under execution,when you run the program, you need much more information like memory context (text and data) done by OS, hardware context(consists of GPR, PC etc.). Other types of memory usage during program execution are needed as well.

Memory Context

Function Call

Things get a bit more complicated with function calls. What if f calls u which calls n?

code fragmentfunction

int i =  0;
i = i + 20;

int g(int i, int j) {
    int a;
    a = i + j
    return a;
}

Looking back at our code fragment... compare it w a function. If both occur in the same program and the left is in main and right is in g, we have 2 copies of i and we have a local variable a which should not be accessible outside of g (and j too).

How do we manage this in the data memory space (how do we allocate memory space) with 2 'i's and prevent main from accessing a and j? It is even worse when f calls g. How does a below map into i of function g?

2 interrelated issues are control flow and data storage.

void f( int a, int b ) {
    int c;
    c = g(a, b);
    ....
}
int g( int i, int j ) {
    int a;
    ......
    return ...;
}

Control FlowData Storage

f called so control handed to f. f executes which calls g and control is handed to g. g executes, control is handed to statement immediately after function call (in f) and when f exits, back to instruction aft function call to f. But how to know where to return to? (must know address of next instruction after the fn call).

Thus, we need to jump to the function body, resume when function call is done and minimally store PC of the caller.

We need to pass parameters to the function, capture return result and may have local var which can have same name as global var. Lifespan of local variables should only be lifespan of function -- once we exit function, it is no longer valid.

Thus, we need a new region of memory that is dynamically used by function invocations.

Stack

We can create stack memory region to solve this problem. It is the memory region to store information for function invocation. When a function is invoked, we create something on the stack called the stack/call frame. It contains the return address of caller (so we know where to go back to), arguments, storage for local variables and others. Once stack frame from stack removed, local vars are no longer accesible.

Now, our memory context consists of stack as well (used to pass data to fn thru stack frame)

Stack Pointer

The top of the stack region(first unused location) is logically indicated by a Stack Pointer. Most CPU has a specialised register (almost always called SP) for this purpose. A stack frame is added on top when a function is invoked (stack "grows" taller) and removed from top when function call ends (stack "shrinks").

Stack Memory illustration

Step 1Step 2Step 3Step 4Step 5

when f is invoked, compiler creates stack frame for f

as f executes, g gets invoked, compiler insert code to create stack frame for g

h is invoked and stack frame created

when h exits, compiler create code to remove stack frame for h

g exits and compiler remove stack frame for g

Stack frame

When f calls g, notice that g has local variables. Thus, the stack frame needs to have space for lacal variables. It also has 2 parameters i and j, and we have to be able to return to the instruction after the call to g so we also store the address in the stack frame. Thus, we have to ensure there is space for local variables, parameters, return instr address (PC) and other info

Suppose a has the value 5 and b has the value 6. 5 is copied into i and 6 into j and exists in parameters portion of the stack frame. After j is created, if a = i+j, code will take value of i and j from stack frame, add them together and write value of result into a in stack frame. When function return, stack frame is removed and none of the vars in g is accessible.

Note that actual argument isn't passed in, its the value passed into the parameters (call by value). The compiler only passes in the values and not arguments.

To generate code to setup stack frame, is haradwae and Programmng Language dependent. It always goes through 2 steps, a setup and a teardown process.

Setup

How do we perform the setup process? We begin with the caller. When the caller wants to call the function, the compiler generates code to pass param w registers/stack. The caller then save return address on stack. Next, we need to perform a jump to the function. There are several ways (call instruction to call function, jal, j)

Once we jump, control is transferred to function (callee). Caller has to save the old stack pointer within function and figure out how much memory is required for local variables then adjust SP to point to new stack top.

Example

Let's say a caller passes in 2 parameters (32bits each) and PC (32 bits). In total, we have 12 bytes. The caller does something like addi $sp $sp 12. This automatically moves SP and allocate and saves 12 bytes. Caller saves return address on stack, write in argumens a and b then control is handed over to function. If function has 1 local var (4 bytes), it will increment SP another 4 bytes and store local var on stack. Now, we have access to local variables on the stack.

Step 1Step 2

c calls g with arguments a and b so values 123 and 456 are copied onto the stack.

Control is handed to g and g allocates space for its local variables and adjust SP.

Tear down

In the tear down, the callee places return result on the stack. It copies over saved value back into SP which will immediately point back to old location. Notice we only move SP up and down. We don't clear the values (this is why we don't assume vars created contain 0 as stack space resued can hold values from previous function)

We return control back to caller, (return PC saved copied back into PC which contains address of the next instruction to be executed). This cause execution to resume at instruction after the function call. Once execution resumes, can make use of return results and continue.

Where the return value goes depends on the way compiler is designed. Here, we assume return result 1158 is on top of stack. The function then restores teh stack pointer and returns control to caller for execution to resume. The code after can access stack to get the result. To access stack, we can use displacement addressing mode (lw $2 20($sp))

This is why in c, we need to declare the types (so we know how much memory to allocate). When we declare function ahead of time, we know how many parameters there are and their types, so compiler know how much memory to declare (compiler predict how much memory is needed on stack and how many local var used and where everything is gonna be. Once we know this, we can just offset from stack pointer)

Frame Pointer

Usually, since we pre-declare our variables and parameters, we know more or less how much stack space needed. So we increment SP to point at the top. But now, we won't know where the original stack frame starts from.

So to solve this, we copy SP into FP then increment SP to reserve space on stack for parameters etc. FP always point to start of frame, so now addresses can take as offset from FP. This means when control is handed over to fuction, when SP moved again to save space for other things, it won't affect access to var since it will have reference from FP (we know the offset).

Why does the funtion change the SP? This could be due to different things such as:

• To allocate space for return result (but can be predicted ahead of time)
• Function must safe registers it uses. (what if main uses $1,3,5 and fn changes these same register?)

When control is returned to main, it may not execute correctly if we don't save. The function could have changed these registers in ways the main cannot predict. Thus when creating a function call, one of the very important things to do at the start is to save all the registers it intends to use. How to know which regisers? Since compiler generates code, it chooses whichh registers and will save both. At the end, compiler will generate code to restore the values.

When function wants to save register val, it must allocate space and move SP. So FP alw point to start of stack frame to calculate this offset. It facilitates access to various parts of the stack frame.

|______|
|______|
|__i___|
|__j___|__FP


lw $2 0($fp) // to access i
lw $3 4($fp) // access j

However, not every architecture/cpu has a FP so you'll need to save SP value somewhere and use that as displacement or be careful.

Saved Registers

Sometimes function has to save registers in the middle of execution (if our function is v big and has a lot of variables, we have a problem -- we only have 32 GPRs of which only some can be used.) When run out of registers, we must create space on stack to copy over some registers to a temporary memory location to allow us to reuse registers for something else. called register spilling

For example, we have x value in $3 which is our last available register. If now we want to use y, we write $3 to the stack and load y into $3. After writing the contents of $3 back to y, we can copy the content from the stack back into $3. This is known as register spilling.

So when GPRs are exhausted, we use memory to temporarily hold the GPR value. The GPR can be reused for other purposes and the value can be restored afterwards.

However, the way it setup and teardown depends on compiler and arhcitectures.

Dynamically Allocated Memory

Dynamically allocated memory is memory acquired during execution e.g. y = (int) malloc sizeof(int) which dynamically allocates 4 bytes.

Dynamically allocated memory

• C: malloc() function call
• C++: new keyword
• Java: new keyword

Unfortunately we cannot use data or stack to store these information. The problem here is firstly, data region stores global variables and they global are alive for the lifetime of program. The OS needs to know how big the space for data segment is but dynamic variables are created at runtime, so the OS dont know how much memory is required so cannot allocate at data.

Storing in the stack region is even worse, as when function exits, local variables are gone as SP has moved away to prevent access. Since dynamic variables shld last until deallocated (not necessarily in the same function), this cannot work. To solve this, we have the heap memory region.

So now we got the 4th memory lcoation known as the eap to store dynamically allocated variables. When malloc called, space is allocated by OS for the new variable.

Heap memory is trickier to manage as memory allocation (how much is required) is not known in advance. Calling malloc(sizeof(int/char/double)) have different size.

Secondly when the variable is created or deallocated is not known in advance.

A tricky scenario as a result is that we can allocate and deallocate memory to create holes. Holes are pockets of free memory in between vars. The worst thing that can happen is that all pockets too small for what we want but in total more than what we need, thus allocation fails. (external fragmentation)