Virtual Memory

Partitioning of memory is as a job that is brought into memory, it must be allocated a portion of the memory, this is its partition. Partitions can be fixed size of variable sized

– Fixed size:

This is a rigid size divisions of memory

Process is assigned to smallest available partition it fits into

Process can be very wasteful of memory

– Variable size

Allocate a process to only as much memory as it needs

Other memory can be used for other processes

Efficient use of memory but, over time, can lead to large numbers of little left over pieces of free memory -- too small to use

Must consider use of memory compaction

• Effect of partitioning

Since a process can be swapped in and out of memory and end up in different partitions, addressing within the process must not be tied to specific physical memory addresses

– Program/process addresses are logical ones with respect to the starting address of the

program itself

– Processor hardware must convert the logical address reference of the program into a physical address that the machine can operate on

– In effect this is a form of index addressing -- base addressing -- where the base address is the first address of the program.

Effect of partitioning

• Paging is to subdivide memory into small fixed-size “chunks” called frames or page frames
• Divide programs into same sized chunks, called pages
• Loading a program in memory requires the allocation of the required number of pages
• Limits wasted memory to a fraction of the last page
• Page frames used in loading process need not be contiguous

– Each program has a page table associated with it that maps each program page to a memory page frame

– Thus, logical addresses in a program are interpreted as a physical address -- page frame number and an offset within the page

• Principle for allocation of free page frames

Allocation of free pages

• Address mapping in a paging system

The more sophistiated way of mapping address from the address space onto the actual memory address is possible. Principle of address mapping in a paging system is shown in Figure 15.3 .

The address that the program can refer is called the virtual address space, the actual hardwired (pgysical) memory address is called the physical address space.

Address mapping in a paging system

• The implementation of paging systems permit true multiprogramming systems through the use of virtual memory / demand paging

– Only the program pages that are required for the execution of the program are actually loaded -- hence the “demanded” concept

– Only a few (of the many potential) pages of any one program might be in memory at a time

– Many “active” programs can have pages -- increasing the degree of multiprogramming

• With demand paging, it is possible for a program consisting of more pages than can (ever) fit into memory to run

– This is presents a virtual memory system that seems unlimited in size to the programmer

– Significantly simplifies program development

• Page tables can be large and are themselves subject to being stored in

secondary storage. Only a small portion will be kept in main memory

• To reduce size of a page table consider

– Using a 2-level page table:

Entry in first level point to a table at the second level

First level is small -- in many cases the size of a single page

– Use an inverted table structure: A hashing function maps a page request

into an inverted table that is used by all processes. One structure is usec for all processes and virtual pages

• It would seem that each virtual address reference causes 2 memory accesses

– An access to get to the page table

– An access to get the actual data page

• To avoid this delay, use a special cache to hold page table information
• Every memory access requires

– Trying to find frame reference in TLB

– If not there, go to page table in memory

– With frame identified, check the cache to see if it is there,

– If not there, get from main memory or retrieve from disk

• Operation of paging and TLB

Operation of paging and TLB TLB and cache operation

• Principle of Replacemenr Policy

- If there is an unused page frame, it can be loaded into it

- If all page frames are in use, one must be selected for replacement

- If it has been altered, the page to be replaced must be copied back to secondary

storage

• Page replacement algorithms

Similar to the ones discussed in caching, the following algorithms have been used

LRU

FIFO

Random, etc.

In addition to partitioning and paging, segmentation can be used to subdivide

memory

– Programmer subdivides the program into logical units called segments

Programs subdivided by function

Data array items grouped together as a unit

– Advantages

Simplifies data structure handling

Supports code modification and maintenance

Supports sharing code segments

Provides a degree of protection

– Memory reference is in the form of a segment ID and an offset

– Segmentation can be combined with paging in a segment ID, page number, page offset scheme

Resume of management

– Partitioning

– Paging

– Segmentation

– Segmentation and paging