Memory Management and Virtual Memory

Memory management techniques allow several processes to share memory. When several processes are in memory they can share the CPU, thus increasing CPU utilization.

Address Binding: Binding of instructions and data to memory addresses.

Compile time: if process location is known then absolute code can be generated.
Load time: Compiler generates relocatable code which is bound at load time.
Execution time: If a process can be moved from one memory segment to another then binding must be delayed until run time.

Dynamic Loading:

Routine is not loaded until it is called.
Better memory-space utilization;
Unused routine is never loaded.
Useful when large amounts of code are needed to handle infrequently occurring cases.
No special support from the operating system is required; implemented through program design.

Dynamic Linking:

Linking postponed until execution time.
Small piece of code, stub, used to locate the appropriate memory-resident library routine.
Stub replaces itself with the address of the routine, and executes the routine.
Operating system needed to check if routine is in processes’ memory address

Overlays: This techniques allow to keep in memory only those instructions and data, which are required at given time. The other instruction and data is loaded into the memory space occupied by the previous ones when they are needed.

Swapping: Consider an environment which supports multiprogramming using say Round Robin (RR) CPU scheduling algorithm. Then, when one process has finished executing for one time quantum, it is swapped out of memory to a backing store.

The memory manager then picks up another process from the backing store and loads it into the memory occupied by the previous process. Then, the scheduler picks up another process and allocates the .CPU to it.

Memory Management Techniques

The main memory must accommodate both the operating system and the various user processes. The parts of the main memory must be allocated in the most efficient way possible.

There are two ways for memory allocation as given below

Single Partition Allocation: The memory is divided into two parts. One to be used by as and the other one is for user programs. The as code and date is protected from being modified by user programs using a base register.

Multiple Partition Allocation: The multiple partition allocation may be further classified as

Fixed Partition Scheme: Memory is divided into a number of fixed size partitions. Then, each partition holds one process. This scheme supports multiprogramming as a number of processes may be brought into memory and the CPU can be switched from one process to another.

When a process arrives for execution, it is put into the input queue of the smallest partition, which is large enough to hold it.

Variable Partition Scheme: A block of available memory is designated as a hole at any time, a set of holes exists, which consists of holes of various sizes scattered throughout the memory.

When a process arrives and needs memory, this set of holes is searched for a hole which is large enough to hold the process. If the hole is too large, it is split into two parts. The unused part is added to the set of holes. All holes which are adjacent to each other are merged.

There are different ways of implementing allocation of partitions from a list of free holes, such as:

first-fit: allocate the first hole that is big enough
best-fit: allocate the smallest hole that is small enough; the entire list of holes must be searched, unless it is ordered by size
next-fit: scan holes from the location of the last allocation and choose the next available block that is large enough (can be implemented using a circular linked list)

Disadvantages of Memory Management Techniques

The above schemes cause external and internal fragmentation of the memory as given below

External Fragmentation: When there is enough total memory in the system to satisfy the requirements of a process but the memory is not contiguous.
Internal Fragmentation: The memory wasted inside the allocated blocks of memory called internal fragmentation.

e. g., consider a process requiring 150 k, thus if a hold of size 170 k is allocated to it the remaining 20 k is wasted.

Compaction: This is strategy to solve the problem of external fragmentation. All free memory is placed together by moving processes to new locations.

Paging:

It is a memory management technique, which allows the memory to be allocated to the process wherever it is available.
Physical memory is divided into fixed size blocks called frames.
Logical memory is broken into blocks of same size called pages.
The backing store is also divided into same size blocks.
When a process is to be executed its pages are loaded into available page frames.
A frame is a collection of contiguous pages.
Every logical address generated by the CPU is divided into two parts: The page number (P) and the page offset (d).
The page number is used as an index into a page table.

Each entry in the page table contains the base address of the page in physical memory (f).
The base address of the Pth entry is then combined with the offset (d) to give the actual address in memory.

Paging Example:

Implementation of Page Table:

Page table is kept in main memory.
Page-table base register (PTBR) points to the page table.
Page-table length register (PRLR) indicates size of the page table.
In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)

Associative Memory:

Frame number is available within memory.
Each entry in memory has two portions: Page number and frame number.

Paging Hardware With TLB:

Effective Access Time
Let Associative Lookup = t time unit,

Assume memory cycle time is 1 microsecond

Hit ratio: percentage of times that a page number is found in the associative registers; ration related to

number of associative registers.

Hit ratio = h

Effective Access Time (EAT) EAT = (1 + t) h + (2 + t)(1 – h) = 2 + t – h

Memory Protection: Memory protection implemented by associating protection bit with each frame.

Valid-invalid bit attached to each entry in the page table:

“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.

Example:

Page Table Structure:

Hierarchical Paging: Break up the logical address space into multiple page tables.

Example: Two level paging

Hashed Page Tables: The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.
Inverted Page Tables: One entry for each real page of memory. Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.

Paging Advantages :

Allocating memory is easy and cheap
Any free page is ok, OS can take first one out of list it keeps
Eliminates external fragmentation
Data (page frames) can be scattered all over PM
Pages are mapped appropriately anyway
Allows demand paging and prepaging
More efficient swapping
No need for considerations about fragmentation
Just swap out page least likely to be used

Paging Disadvantages :

Longer memory access times (page table lookup)
Can be improved using TLB
Guarded page tables
Inverted page tables
Memory requirements (one entry per VM page)
Improve using Multilevel page tables and variable page sizes (super-pages)
Guarded page tables
Page Table Length Register (PTLR) to limit virtual memory size
Internal fragmentation

Virtual Memory

Separation of user logical memory from physical memory. It is a technique to run process size more than main memory. Virtual memory is a memory management scheme which allows the execution of a partially loaded process.

Advantages of Virtual Memory

The advantages of virtual memory can be given as
Logical address space can therefore be much larger than physical address space.
Allows address spaces to be shared by several processes.
Less I/O is required to load or swap a process in memory, so each user can run faster.

Segmentation

Logical address is divided into blocks called segment i.e., logical address space is a collection of segments. Each segment has a name and length.
Logical address consists of two things < segment number, offset>.
Segmentation is a memory-management scheme that supports the following user view of memory. All the location within a segment are placed in contiguous location in primary storage.

Segmentation Advantages :

No internal fragmentation
May save memory if segments are very small and should not be combined into one page.
Segment tables: only one entry per actual segment as opposed to one per page in VM
Average segment size >> average page size
Less overhead.

Segmentation Disadvantages :

External fragmentation.
Costly memory management algorithms.
Segmentation: find free memory area big enough.
Paging: keep list of free pages, any page is ok.
Segments of unequal size not suited as well for swapping.

Demand Paging: Virtual memory can be implemented by using either of the below.

Demand paging
Demand segmentation

Demand paging is combination of swapping and paging. With demand paged virtual memory, pages are only loaded when they are demanded during program execution. As long as we have no page faults, the effective access time is equal to the memory access time. If however, a page fault occurs, we must first read the relevant page from disk and then access the desired word.

Effective Access Time

Effective access time = [((1 – p) × ma) + (p × page fault time))]

Here, rna = Memory access time, p = The probability of page fault (0 ≤ p ≤ 1)

If p = 0, it means no page faults.

If P = 1, every reference is a fault.

We expect p to be close to zero that is there will be only few page faults

Page Replacement

In a multiprogramming environment, the following scenario often results. While execution of a process, page fault occurs and there are no free frames on the free frame list. This is called over allocation of memory and results due to increase in the degree of multiprogramming. Page replacement is a technique to solve this problem.

Page Replacement Algorithms: In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated.

First In First Out (FIFO)

A FIFO replacement algorithm associates with each page, the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen.

It is not strictly necessary to record the time, when a page is brought in. We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory we insert it at the tail of the queue.

Example

Consider the following frames:a,b,c,a,d,c,a. Assume frame size of 3 (three physical frames in main memory), determine the number of page fault using FIFO.

Optimal Page ReplacementThe number of page fault is 5.

It has the lowest page fault rate of all algorithms and will never suffer from Belady’s anomaly. This algorithm replaces the page that will not be used for the longest period of time. This algorithm gives a lowest page fault rate. It is very difficult to implement because, if requires future knowledge about the usage of the page.

Beladys’ Anomaly For some page replacement algorithms, the page fault rate may increase as the number of allocated frames increases. This phenomenon known as Belady’s anomaly.

Example: Consider the following frames: a,b,c,a,d,c,a

and a frame size of 3 (three physical frames in main memory), determine the number of page fault using Optimal

Least Recently Used (LRU) Page ReplacementThe number of page fault is 4, which is less than FIFO.

In this, we use the recent past as an approximation of the near future, then we can replace the page that has not been user for the longest period of time.

Each page table entry has a counter
whenever a page is referenced, copy the clock into the counter
when a page needs to be replaced, search for a page with the smallest counter value
This is expensive
Stack is used: To keep a stack of page numbers in a double link form when a page is referenced, move it to the top. The page number at the bottom of the stack indicates the page to be replaced.

Example: Consider the following frames: a, b, c, a, d, c, a, b

and a frame size of 3 (three physical frames in main memory), determine the number of page fault using LRU.

The number of page fault is 5.

Working Set: WS model is based on the assumption of locality.

A collection of pages a process is actively referencing to run a program efficiently, its working set of pages must be in main memory. Otherwise, excessive paging activities might occur. WS is used to keep track the active pages and is appropriate to the pages’ locality.

Working Set Storage Management Policy: Seek to maintain the working sets of active processes in main memory. At time t, W(t,w) = set of pages referenced during the interval t-w to t. w is called the working set size

The size of WS will affect the performance:

If w is too small, will not encompass working set
If w is too large, will encompass several localities
If w is very large, will encompass the entire program
Working set changes as a process executes
The process demand pages in its working set one page at a time
Process gradually receives enough storage to hold working set
At this point, storage use stabilizes

Frame Allocation: The maximum number of frames tha1 can be allocated to a process depend on the size of the physical memory (i.e., total number of frames available). The minimum number of frames which can be allocated to a process depend on the instruction set architecture.

Thrashing

A process is said to be thrashing when it is spending more time in paging (i.e., it is generating a lot of page faults) than executing.
Thrashing causes low CPU utilisation. The processes which are thrashing queue up for the paging device.
The CPU schedule sees the empty ready queue and tries to increase the degree of multiprogramming by introducing more processes in the system. These new Degree of multiprogramming processes cause more page faults and increase the length of the queue for the paging device.