Virtual Memory Management

Created by Frank.

1. What is virtual memory?

Fig. Virtual address space

In user's view, we see memory of processes is a continuous range of addresses. With 32-bit virtual address width, virtual address space of a process can be up to 4 GB, which is too large compared with physical memory.

Several processes can be executed simultaneously, so the number of virtual addresses is even greater.

Theoretically, the physical memory can not hold a program that has a larger memory capacity it, such processes therefore can not be executed. So how do the computer can run large memory multiple programs with a such meager memory.

To solve this problem, we use virtual memory and virtual memory techniques. This task belongs to the operating system and some hardware devices in computer system.

Virtual memory management is a very important issue because the limit of memory storage and the memory management techniques are very difficult and abstract.

Although programmers only see the application through a contiguous virtual address space, which is much easier than physical address, understanding of memory management mechanisms will help us to programming better, specially handling memory problems.

Distinguish some concepts:

• Virtual address space (of a process): Each process has a address space and it is totally virtual. Virtual address space include all addresses a process can access, it can not access addresses of others. This address space is continuous and starts at 0x00..00. (this strip is 32 bit in common 32 bit and 64 bit Linux and Windows Systems). Notice process address space we see as Fig 1a-b is address rather than memory.
• Logical address/Physical address: Logical address is generated by CPU, is virtual and physical address is generated by Memory Management Unit (MMU is hardware device) and it is actual address on main memory. We need translate logical address to physical address to execute processes, MMU will do this.
• Physical memory: is main memory/RAM (different from disk)
• (Main) Memory management: is techniques which manage virtual and physical address space and translate virtual address to physical address.
• Virtual memory: Virtual memory is a technique that allows the execution of processes that are not completely in memory. In virtual memory, we have to use a part of disk (or fast drive) as memory. it is known as swap space. Swap space is secondary store which contains waiting-for-execution portion of process. In view of storage, total virtual memory capacity equal sum of RAM and swap space.

The difference between virtual memory and normal memory:

• Normal memory: require an entire process be in memory before it can execute, so size of process is limited by physical memory size.
• Virtual memory: does not require entire process be in memory before it can execute

2. The advantages and disadvantages of virtual memory

The Advantages:

• The primitive benefit of virtual memory is can run one/many process with a much larger size than available physical memory. Each user will use less memory, so more processes can run simultaneously, it increases the CPU and throughput
• In virtual memory, there is a technique allows load only necessary pages into memory when executing the program. it saves time and memory.
• Virtual memory allows to share memory easier between processes (Shared Mem is one facilities of IPC programming)
• Virtual memory provide effective mechanism for process creation.
• This technique frees programmers from concerns about memory-storage limitations and concentrate programming.

The Disadvantages

• Virtual memory will be slower, embedded system and system that require special processing time do not use virtual memory.
• Virtual memory can cause I/O faults in run time
• One difficulty of virtual memory is the complexity of algorithms

3. Factors affect virtual memory

Because manage virtual memory was role of OS and MMU, so both of OS and system hardware architecture affect virtual memory.

• Depend on the support of computer architecture (Intel Pentium, Intel Core I...) and the operating system (Linux, Windows...)
• Memory and swap space access speed affect performance of virtual memory (one solution is inserting high speed memory between CPU and RAM), expect "effective access time" equal to memory access time
• Memory techniques affect virtual memory performance
• Virtual memory management techniques affect virtual memory performance.

4. Memory management techniques

In this section, we discuss some memory management techniques:

• Contiguous Memory Allocation
• Paging
• Segmentation
• Combinations of paging and segmentation (Not mentioned here)

After that, we will compare the algorithms in some respects.

What is swapping?

Swapping of two processes using a disk as a baking store

A process must be in memory to be executed. A process, however, can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution The biggest problem of swapping is transfer time between main memory and backing store.

In virtual memory, backing store is called swap space

4.1. Contiguous Memory Allocation

Contiguous Memory Allocation is a common method to allocate main memory.

In Contiguous Memory Allocation, each process is contained in a single contiguous section of memory.

Memory mapping

Use relocation register and limit register

Hardware support for relocation and limit registers

Fix-sized partitions:

• Each partition may contain exactly one process => the degree of multiprogramming is bound the number of partitions
• When a partition is free, a process is selected from the input queue and is loaded into the free partition
• When the process terminates, the partition becomes available for another process

Variable partitions:

• OS keeps a table indicating which parts of memory are available and which are occupied
• Memory contains a set of holes of various sizes
• when processes are put into an input queue, OS account the memory requirements of each process and amount of available memory space in determining which processes are allocated memory

Allocation methods:

• First-fit
• Best-fit
• Worst-fit

What is fragmentation?

• Both the first-fit and best-fit suffer from external fragmentation

External fragmentation:

• When processes are loaded and removed from memory, the free memory space is broken into little pieces.
• External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous, storage is fragmented into large number of small holes.
• External fragmentation can be reserve. In worst case, there is a block of free memory between every two processes.
• One solution for external fragmentation problem is compaction but it is expensive
• Other solution for external fragmentation problem: Paging and Segmentation

Internal fragmentation:

• Internal fragmentation exists when physical memory is broken into fixed size blocks and allocate memory in units based on blocks size. So memory allocated to a process may be slightly larger than the requested memory. The difference between these 2 numbers is internal fragmentation

4.2. Paging

Paging model of logical and physical memory

First, we distinguish some concepts:

• Page: physical memory is broken into fixed-sized blocks called frames
• Frame: logical memory is broken into blocks of same size called pages
• Logical address is divided into 2 parts: page number + page table

Logical address structure

page table structure

Physical address = base address + page offset

Hardware: page table (each process has a page table)

paging hardware

Protection: read only, write-only or execute-only….

Valid-invalid bit in one of these bits attached to each entry in the page table

valid (v) and invalid (i) in page table 

Shared page:

• The sharing of memory among process on a system is similar to the sharing of the address space of a task by threads and as a method of interprocess communication.
• Can share: code (must be reentrant), data, compilers, window systems, run-time libraries, database systems, and so on.

sharing of code in a paging environment

4.3. Segmentation 

One problem with Paging is separation of user’s view of memory from actual physical memory. Segmentation is a memory-management scheme that supports this user view of memory.

Hardware: segment table, includes segment base and segment limit

• segment base: contains the starting physical address where the segment reside in memory
• segment limit: specifies the length of the segment

A logical address space is a collection of segments, each segment consists of 2 quantities:

<segment number, offset> (s,d on Figure)

* segment number is an entry of segment table to determine the base address
* offset specifies the position in segment

physical address = base + offset

segmentation hardware 

example of segmentation

Normally, the user program is compiled, and the compiler automatically constructs segments reflecting the input program.

A C compiler might create separate segments for the following:

• the code
• global variables
• the heap, from which memory is allocated
• the stack used by each thread
• the standard C library

Libraries that are linked in during compile time might be assigned separate segments. The loader would take all these segments and assign them segment numbers

4.4. Compare the advantages and disadvantages among algorithms

Table 1. Compare the advantages and disadvantages among memory management algorithms

Algorithm	Advantages	Disadvantages
Contiguous memory allocation	·         Support fast sequential and direct access ·         Provide a good performance ·         The number of disk seek is require is minimal	·         Fragmentation
Paging	·         Allows jobs to be allocated in non-contiguous memory locations ·         Memory used more efficiently; more jobs can fit	·         Addresss resolution causes increased overhead ·         Internal fragmentation still exists, though in last page ·         Requires the entire job to be stored in memory location ·         Size of page is crucial (not too small, not too large)
Segmentation	·         Internal fragment is removed because each job is divided into segments of different sizes, so no space is wasted	·         Difficulty managing variable-length segments in secondary storage ·         External fragment

5. Virtual Memory Management

virtual memory is larger than physical memory 

shared pages using virtual memory

Virtual memory is a technique that allows the execution of processes that are not completely in memory . The major advantage of this scheme is that programs can be larger than physical memory The large blank space between the heap and the stack is part of the virtual address space but will require actual physical pages only if the heap or stack grows.

5.1. Demand paging 

How an executable program might be the load from disk into memory?

one option is to load the entire program in physical memory at program execution time

Demand paging means that never load unnecessary pages into memory. It loads only needed pages into memory in run time.

A demand-paging system is similar to a paging system with swapping, but demand paging uses pager rather than swapper because we are now viewing a process as a sequence of pages, rather than as one large contiguous address space.

So how? when a process is swapped in, Pager guesses which pages will be used before the process is swapped out again .

Benefits: decreasing the swap time and the a mount of physical memory needed.

but problem: page fault

Page table when some pages are not in main memory

Steps in handling a page fault

 Performance of demand paging

formula: 

effective access time = (1-p) x memory access time + p x page fault time 

* where pis page fault rate 
* if p = 0, effective access time = memory access time (expected)

Example:

memory access time = 200ns

page fault time = 8 miliseconds

=> effective access time = (1-p) x 200 + p x 8000000 = 200 + 7999800 x p

* if p = 1/1000 then effective access time = 40 memory access time s => too slow
* if we want performance degradation to be less than 10 percent, then p<0.0000025

The advantages and disadvantages of Demand Paging

• Advantages: Job no longer constrained by size of physical memory (concept of virtual memory) and Utilizes memory more efficiently than previous schemes
• Disadvantages: Increased overhead caused by the tables and page interrupt

5.2. Copy-on-write

When creating a process by fork() system call.

• traditional: fork() worked by creating a copy of the parent's address space for the child, duplicating the pages belongs to the parent
• problem: child process invoke the exec() system call immediately after creation => the copy address space in unnecessary

Copy-on-Write: allows the parent and child process initially to share the same pages

before process 1 modify page C

after process 1 modify page C

Example:

initially, child process and parent process share same pages (A, B, C)

when the child attempts to modify a page containing portions of the stack (Page C), OS will create a copy of page C (copy of page C), mapping it into the address space of the child process

the child process will modify page "copy of page C" , page C need be marked as copy-on-write

vfork() system call:

• is a variation of fork()
• is intended to be used when the child process call exec()
• don't use copy-on-write
• parent process is suspended and the child uses the address space of the parent.

5.3. Page replacement

when? in demand paging mechanism, when over-allocating, there is no free frame in physical memory

Need for page replacement

the efficient access time increase because of two page transfer (one out and one in)

page replacement

graph of page fault versus number of frames

two major problems in demand paging:

• frame-allocation algorithm in multiple processes memory
• page-replacement algorithm when over-allocating (so that least error page)

Example:

tracing a particular process, we might record the following address sequence:

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103

0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

this sequence is reduced to the following reference string: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 (3 pages are 1, 4, 6)

* if we have 3 or more free frames, we would have only 3 faults (first reference for each page)
* if we have only one free frames, we would have 11 faults (replacement with every reference)

References

Gagne, Silbersrchatz and Galvin, The Operating System Concepts (9th Ed)
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
https://en.wikipedia.org/wiki/Virtual_memory,
https://www.scribd.com/doc/59018943/Advantages-and-Disadvantages-of-Virtual-Memory-Management-Schemes