Linking, Loading, Virtual Memory

Loading and Linking

Linker 
A program consist of number of module these are linked to resolve any references between them
static libraries are linked at this time
Takes as input collection of modules are prepares a load module, each symbolic address within each module are changed relative to final load module and this final module is then loaded

Dynamic Linker
It is possible to defer some linkage functions
so load module will contain unresolved references to other programs
Load time Dynamic linking
load module is read into memory and any  unresolved references causes loader to find module, load it and alter the references to relative address
requires dynamic library to loader

Runtim dynamic linking
At the time when call is made to unresolved reference then it is brought in memory
these are shareable module so if its already in the memory linking is done to that.
DLL in windows are example


Loading

Loading is to move the program into memory where it has its associated PCB stack
Absolute loading
all absolute references, module always loaded at same memory location
assignment of addresses can be done by programmer or at compile time

Relative loading
memory address are relative to start of program
compiler or assembler does not produce absolute addresses instead relative
so module can be loaded in any memory location

Dynamic Runtime loading
Since swapping part of program is possible in virtual memory relative address wont work if next time part of program is allocated some other space in memory
so instead of calculating relative address at load time, calculations are deferred  until instruction is actually executed

Segmentation
user and associated data divided into segments
can be different length segments
segment number+offset
all program segments are loaded if no virtual memory
eliminates external segmentation suffers from internal segmentation
visible to user unlike paging
Segment table for each process that keep starting address of segment along with 
size of that segment because segments are of variable size so to check the valid address

TLB
virtual memory access requires at least two memory access one for PTE and one for actual data frame access
 with TLB,high speed cache for PTE, most recently used page table entries can be used to find the frame number If its not there then
1)access page table
2)
If page is in memory then update TLB and CPU genrates physical address
If page table is not in memory(checked with present bit in PTE) then its page fault and 
trap to OS save the state of current process and transfer control to page fault handler
 i)read page from disk more process from running to blocked state
 ii)if no memory available then replace memory page to make space
 iii)update page table and more process from blocked to running

we cannot index TLB with page number because it holds only some of the page table entries so TLB holds both page number and PTE
In TLB  associative mapping is done that is all entries are checked simuiltaneoulsy


Page size
Small page size : less internal fragmentation,optimizes the use of main memory, more pages will be required per process hence larger page table, more pages means only part of page table can be in memory so number of page faults will double including the page table access from disk.
Large page size: disk device transfers efficiently

Virtual Memory
allows only part of process to be in memory
program size can be larger than all available memory
differences:Fetch policy,Demand Paging,Prepaging

Page replacement

Optimal page replacement policy clairvoyant or belady optimal
replace the page for which the time to next reference is longest
least page faults
impossible to implement, so used as benchmark
looks in the future  and finds out of present frames which will be used last or never

Least Recently used policy
replace page in memory that has not been referenced for longest time
decides on  principle of locality
looks in the past and find out of present frames which was used last
so a page reference string S with LRU and  page string reverse(S) with Optimal will give same result
difficult to implement
stack implementation Or counter implementation possible
stack algorithms does not suffers from belady anomaly like optimal and LRU
LRU does nearly as good as Optimal

solving LRU problems
mark the alphabet that are present in memory as they come
look to the left of new alphabet which alphabet in memory is to most left
replace that

First In First Out policy
without looking at the past or future it replaces pages in round robin order
a circular buffer
simplest easy to implement
in other words looks a the present page frames and replace the one that has been for longest time
suffers from belady anomaly that is increasing page frame increases page fault instead of decreasing.

How to solve FIFO page replacement problem
write the alphabet one below other until faults
when page fault cross the first alphabet and place new at last

Thrashing
more paging activity
solution is to use local replacement algorithm instead of global, process cannot steal frames from other process

//go through the counter based implementation and other algorithm that uses reference bits