Operating System Design - Main Memory

Protection

 

Need to ensure that process can only access those addresses in it address space

 

`

Base register : Starting point of a process

Limit register : Range of a process region

If context switching occurs to another process, the new process's address information, base and limit information are updated via the PCB

 

Address binding

 

The process of converting a logical address to a physical address is called address binding

It means that all addresses are replaced with absolute address and loaded into a fixed part of the main memory.

 

Compile time : If memory location known a priori, absolute code can be generated, must recompile code if starting location chages

Load time : Must generate relocatable code(logical) if memory location is not known at compile time

Execution time : Binding delayed until run time if the process can be moved during its execution from on memory segment to another

It maps logical address space to physical address space

 

Logical & Physical address

 

Logical address(Virtual address) : generated by the CPU

Physical address : address seen by the memory unit

 

Logical and physical addresses are the same in compile-time and load-time address-binding schemes

Logical and physical addresses differ in execution-time aaddress-binding scheme

 

Memory-Management Unit

 

The base register now called relocation register (It is added to every address generated by a user process)

The user program deals wihht logical addresses (It never sees the real physical addresses)

 

Dynamic Loading

 

Routine is not loaded until it is called

Better memory-space utilization (unused routine is never loaded)

All routines kept on disk in relocatable load format

No specail support from the operating system is required (It just provideing libraries)

 

Dynamic Linking

 

Linking is not postponded until execution time

Stub used to locat the appropriate memory-resident library routine

Operating system checks if routine is in processes' memory address

 

Contiguous Allocation

 

Main memory usually into two partitions (OS and user process)

 

Variable Partition

 

Operating system maintain information about allocated partitions, free partitions(hole)

 

Dynamic storage-allocation problem

 

First-fit : Allocate the first hole that is big enough

Best-fit : Allocate the smallest hole that is big enough; must search entire list; produces the smallest leftover hole

Worst-fit : Allocate the largest hoe ; must search search  (Produces the largest leftover hole)

 

First-fit, best-fit better than worst-fit in terms of speed and storage utilization

 

Fragmentation

 

External Fragmentation : total memory space exists to satisfy a request, but it is not contiguous (can reduce my compaction)

Internal Fragmentation : allocated memory may be slightly larger than requested memroy (size difference is internal fragmentation)

 

Paging

 

Physical address space of a process can be noncontiguous => Process is allocated physical memory whenever the latter is available

 

Divide physical memory into frames

Divide logical memory into pages

Set up a page table to translate logical to physical addresses

Backing store likewise split into pages

 

Still have Internal fragmentation

 

Address generated by CPU(Logical address) is divided into:

Page number(p) : used as an index into a page table which contains base address of each page in physical memory

Page offset(d) : combined with base address to define the physical memory address that is sent to the memory unit

 

Implementation of page table

 

Page-table base register (PTBR) points to the page table

Page-table length register (PTLR) indicates size of the page table

 

One for the page table and one for the data/instruction

 

Two memory access problem can be solved by special fast-lookup hardware cache called translation look-aside buffers(TLBs)(associative memory)

 

TLB(Translation Look-Aside Buffer)

 

Some TLBs store address-space identifiers(ASIDs) in each TLB entry - unique identifiers each process to prove address-space protection for that process (Otherwise need fo fulsh at every context switch)

 

TLB hit can be reached to physical address immediately

On a TLB miss, value is loaded into the TLB for fast access next time

 

Effective Access Time

 

EAT = hit ratio * p1 nanosecond + (1 - hit ratio) * p2 nanosecond

 

Memory Protection

 

"valid" indicates that the associated page is in the process' logical address space, and is thus a legal page

"invalid" indicates that the page is not in the process' logical address space

 

Any violations result in a trap

 

Shared Pages

 

One copy of read-only (reentrant) code shared among processes

 

Shared pages should share the same frame and should not be confused in the page table that translates them, so they should not exist anywhere

 

Structure of the page table

 

Don't want to allocate that contiguously in main memory

 

solution : Hierarchical Page Table

Break up the logical address space into multiple page tables (two level paging)

Memory access time increases as the level increases

 

solution : Hashed Page Table

 

Create a table structure using a hash function that can reduce page entry itself (O(1))

The virtual page number is hashed into a page table

The page table contains a chain of elements hashing to the same location

Each element contains the virtual page number, the value of the mapped page frame, a pointer to the next element

Especially useful for sparse address spaces

 

solution : Inverted page table

 

Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages

Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs

 

Oracle SPARC Solaris

 

Two hash table. one for kernel one for all user processes

TLB holds transalation table entries(TTEs) for fast hardware lookups

TTE next to TSB
TSB has a very short search time

 

Swapping

 

A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution

System maintains a ready queue of ready to run processes which have memory images on disk

When swapping happend, context switch time very high.

Swap only when free memory extremely low