Chapter 3 – Memory Management

1. Swapping ----------------------------------------------------------page no: 1

2. Memory compaction ----------------------------------------------page no: 2
3. Overlay’s --------------------------------------------------------------page no: 2
4. Virtual memory -----------------------------------------------------page no: 3
5. Internal operations of MMU -------------------------------------page no: 6
6. Page table ------------------------------------------------------------page no: 7
7. Structure of page table entry ------------------------------------page no: 7
8. Speeding up of paging ---------------------------------------------page no: 8
9. Transaction look aside buffer ------------------------------------page no: 8
10. Multilevel page table ----------------------------------------------page no: 10
11. Inverted page table -----------------------------------------------page no: 12
12.Shared pages -------------------------------------------------------page no: 13
13.Segmentations -----------------------------------------------------page no: 14
14. Pure segmentation -----------------------------------------------page no: 16
15.Segmentation with paging in MULTICS----------------------page no: 17

Swapping

The total amount of RAM needed by all the processes is often much more than
can fit in memory.

On window or LINUX systems 40 -60 process or more may be started up when the
computer is booted.

When a windows application is installed, if often issues commands so that on

subsequent system boots, a process will be started that check for updates.

Such process can easily occupy 5 -10 MB of memory

Background process such as incoming email, network connections and many

other things

The above things just before the user programs started

1
 User applications can run from 50 to 200 MB of memory and even more

So keeping all the process all time in the memory is impossible, because large
amount of memory space is needed

Two general approaches to deal memory overload are swapping bringing in each
process running it for a while then putting back on the disk

Idle processes are mostly stored on the disk

The other approach is virtual memory, allows programs to run even when they
are only partially in main memory

Initially only process A is in memory. Then processes B and C are created or

swapped in from disk.

A is swapped out of disk. Then D comes in and B goes out. Finally A comes in
again. Now A is in new location.

Swapping creates multiple holes in memory; it is possible to combine them in big

hole by moving downward as far as possible. This technique is known as memory
compaction.

Figure 1 Memory allocation changes as processes come into memory and leave
it
A memory configuration in which space for growth has been allocated to two
processes.

If processes can have two growing segments

2
for example data segment being used as a heap for variables that are
dynamically allocated and released

stack segment for normal local variable and return addresses.

In next figure a stack at the top of its allocated memory that is growing downward
and a data segment just beyond the program text that is growing upward

The memory between them can be used for either segments

Overlays

Split programs into little pieces called overlays

A program is divided as overlay 0, overlay 1 & so on..

Overlay manager load the program into memory

Initially overlay 0 is loaded when it is finished it tells the overlay manager to load
the next one for execution

Overlays where kept in disk and were swapped in and out of memory

Swapping overlay was done by OS

Breaking into pieces is done by programmer, which is a complex task

Many programmers are not good at it, time consuming error prone, etc..

To overcome the above issues we are into the concept of virtual memory

Virtual memory

Each program has its own address space, which is broken into chunks called
pages

Each page is a contiguous range of addresses

These pages are mapped onto physical memory to run

3
When some parts of address space is in physical memory the H/W performs
necessary mapping on the fly

When some parts of address space is not in physical memory the OS is alerted to
get the missing information and execute the instruction that has failed.

Paging is a technique used by Virtual memory

Any computer program reference a set of memory address when a program

executes an instruction like

MOV REG 1000

Copy the contents of memory address 1000 REG and vice versa

Address can be generated using indexing, base register segment register and
other ways

Program generated address space called virtual address and forms the virtual
address space

MMU that maps the virtual address on to the physical address

Figure 2 The position and function of the MMU. Here the MMU is shown as
being a part of the CPU chip
A computer s that generates 16 bit addresses from o to 64KB these are called the
virtual address

4
The computer has only 32KB of physical memory

64KB programs can be written they cannot be loaded into memory in their
entirety and run

A copy of program core image upto 64KB must be present on disk so that pieces
can be brought in as needed

Virtual address space is divided into fixed size units called pages

Corresponding units in the physical memory called page frames

Pages and page frames are generally same size

With 64KB of virtual pages and 8 page frames

0k -4k means that virtual or physical address in that are 0 to 4095

4k – 8k means 4096 - 8191

When the program tries to access address ZERO using the instruction MOV REG 0

Virtual address 0 is sent to MMU

MMU sees the virtual address page falls in page ZERO (0 – 4095)

According to mapping is page frame 2 (8192 - 12287)

It thus transforms address to 8192 and output address to 8192 on the bus

5
Thus MMU has mapped all virtual address between zero and 4095 to physical
address 8192 to 12287

MOVE REG 8192 is effectively moved to 24576

Virtual address 20500 is 20 byte from the start of virtual page 5, 20480 – 24575
mapped on to 12308 - 16383

MOV REG 32780 the page is unmapped which is noticed by MMU it causes the
CPU to TRAP the OS, this trap is called the pagefault

it finds the little used page frame or the job just completed or oldest job running
the memory for long time, remove the content from the memory then write
content in the disk

6
example if OS decided to force to leave that page frame, it would load the virtual
page 8 at physical address 8192 and rate 2 changes to the MMU

First it would mark virtual page1 as unmapped to trap any future access to Virtual
address between 4096 to 8191

Second it would replace cross in virtual page 8 entry as 1

When trap is re executed it will map virtual address 32780 to physical address
4180 (4096+12)

Figure 3 Internal operation of MMU with 16 4 KB pages

Following table for the decimal value 8196 of virtual address from which physical
address is to be formed

3276 1638 819 409 204 102 51 25 12 6 3 1 8 4 2 1

8 4 2 6 8 4 2 6 8 4 2 6
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0

7
0 0 1 0

First 4 bits 0010 points to page table 2,

0 0 0 0 0 0 0 0 0 1 0 0

next 12 bits offset which is attached along with, 3 bits of the pointer decimal
value 6 as follows

4 2 1
1 1 0

1638 8192 409 2048 1024 51 256 128 64 32 16 8 4 2 1

4 6 2
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0

The above table forms the physical address 24580

Page table

The purpose page table is to map virtual page onto page frame

Virtual address is split to a virtual page number higher order bits and offset lower
order bits

With 16 bits address and a 4 KB page size

Upper 4 bits specify one of the 16 virtual page

Lower 12 bits specify the byte offset (0 to 4096)

Virtual page number is used as an index into the page table

From the page table entry, the page frame number is found

Page frame number is attached to higher order end of the offset

8
Replacing the virtual page frame number to form a physical address that can be
sent to memory

Structure of page table entry

Figure 4 Typical page table entry

Present bit / absent bit: if the bit is 1, the entry is valid if it is not 0 entry is not
valid it is not available in memory

Protection bit: tells what kinds of action are permitted, it contains 1 bit either 0
/1. 0 – read, 1 – write only

Modified bits

Keep track of page usage

When a page is written, the hardware automatically set the modified bit

This bit will have some values, when the OS decide to reclaim the page frame

If the page is modified called as dirty it is written back to disk

If the page is not modified called as clean which means abandoned

Referenced bits

Is set whenever a page is referred either for reading or for writing, its value is to
help the OS choose a page to evict (force to leave) when a pagefault occurs

Last bit allows caching to be disabled for the page.

Speeding up of paging

Two reasons for speeding up of paging

9
 1. Mapping from virtual address to physical address must be fast
2. If virtual address space is large the page table will be large

Virtual to physical mapping must be done on every memory reference

All instructions come from memory and many of them reference operands in
memory

One or two or more page table reference per instruction

If an instruction execution takes 1 nsec, the page table lookup must be done in
<0.2 nsec to avoid mapping uneasy

4 KB page size a 32 bit address space has 1 million address space, then for 64 bit
address space the page table must have 1 million entries

Each process needs its own page table

Simple design, single page table consisting array of fast h/w register with one
entry for each virtual page indexed virtual page number

Transaction look aside buffer

TLB is a scheme for speeding up paging and for handling large virtual address
space

1 byte instruction that copies one register to another

Without paging the instruction makes only one memory reference to fetch the
instruction

With paging atleast two additional memory will be needed to access the page
table

In general most of the programs tend to refer only small number of pages very
often

Only small fraction of the page table entries are heavily read, the remaining are
rarely used

10
TLB sometimes called associative memory, it can have 64 entries maximum and a
minimum of 8 entries

In TLB each entry consist of following information

1. Information about page, includes virtual page number

2. A bit is set when modified
3. Protection code
4. Physical page frame in which page located
5. A bit that indicates the entry is valid or not valid

Virtual address is presented to MMU for translation

Hardware checks to see if it’s virtual page number is present in TLB by comparing
it to all the entries simultaneously

If valid match is found and access does not violate the protection bits, the page
frame is directly taken from TLB

if it’s virtual page number is present but instruction trying to write on a read only
page, a protection fault is generated

In case if virtual page number is not in TLB the MMU detects a miss

Software TLB management

TLB entries are loaded by the OS

When TLB miss occurs, instead of MMU just going to fetch, it just generate a TLB
fault and throw the problem to the OS

The system must find the page and load the entry into TLB and restart the
execution / instruction

To improve the performance, TLB misses should be reduced, so the OS should

figure out the likely pages to be loaded next and preloaded them

Example

11
Client and server communication

Client send request to server

Now client should be ready in case if the server is going to ask any kind of request
(predict and preload information’s that may be asked by server)

Now client reply to server (predicts and preload information’s that may be asked
by client)

Softmiss it occurs when a page referenced is not in TLB but available in memory

Hardmiss it occurs when a page is not in TLB and also not in memory, a disk
access is required to bring in the page which takes several milliseconds,

Hardmiss is much slower than softmiss

Page table for large memory

Multilevel page tables

32 Bit virtual address

PT1 (10 bit) PT2 (10 bit) offset

Multilevel page tables is to avoid keeping all the page tables in the memory

Suppose a process needs 12 MB

Stack 4 MB
Data 4 MB
Program 4 MB

Top level page table with 1024 entries, corresponding to 10 bit PT1

When the virtual address is presented to MMU

12
MMU extract the PT1 field and uses this value as an index into the top level page
table

Each of these 1024 entries represents 4M because the entire virtual address
space is divided into chunks of 4096 bytes

The entry located into the top level page table yields the address or page frame
number of selected second level page table

Entry 0 points to the page table of the program text

Entry 1 points to the page table of the data segment

Entry 1023 points to the page table for the stack

Shaded entries are not used

PT2 field is used as an index into the selected second level page table to find the
page frame number for the page itself

13
 Example a 32 bit virtual address 0x000403004

The MMU first uses PT1 to index into top level page table and obtain entry 1
which corresponds to 4M to 8M

The MMU next uses PT2 to index into second level page table just found and
extract entry 3 which corresponds to 12288 to 16383 within its 4M chunk

This entry contains the page frame number of the page contains the virtual
address 0x000430004

If the page is not in memory, the present / absent bit in the page table entry will
be zero, causing a page fault.

If the page is in memory page frame number is taken from the second level page
table is combined with offset to construct physical address

The physical address is put on the bus and sent to memory

Inverted page table

When process p refer a virtual page vp, the hardware can no longer find the
physical page by using vp as an index into the page table

Instead it must search the entire IPT for an entry (p, vp)

Futher this search must be done on every memory reference will slower the
machine’s progress

The only way is to use TLB because it holds heavily used pages.

Search can be done with the help of hash tables, hashed on the virtual address

All virtual pages currently in memory have the same hash value changed together

14
The average chain will be only one entry long greatly speeding up mapping, once
the page frame number has found the new (virtual page and process) pair is
entered in the TLB

Shared pages

It is more efficient to share the pages to avoid having two copies of the same page
in memory at the same time, the problem is that not all pages are sharable in
particular the pages that are read-only such as program text, can be shared, but
data pages cannot be shared

If separated address space for instructions (program text) I- spaces and D- spaces
(data) are used, two or more process can use the page tables for their I- space but
different page table for their D- spaces.

Each process will have two pointers in its process table

One to I space and second to D space table

When the scheduler chooses to run it uses these pointers to locate the
appropriate page tables and sets up the MMU using them.

15
 Figure 5 two processes sharing the same program sharing its page table

Suppose process A and B are both running the editor and sharing its pages.

If the scheduler decides to move A from memory, evicting all its pages and filling
the empty memory frames with other programs, will cause B to generate large
number of pagefaults.

Another issue is that when pages are shared in very few then no issues, in case
pages are shared more than hundred’s searching all the page tables is very
expensive

Segmentation

 Each program is divided into blocks of unequal size but with semantics
meaning.

 Example: Code, global variables, local variables, stack,

 Contiguous memory is allocated for each segment for the exact amount
needed.

 A logical address is two dimensional with segment number and offset in

segment.

16
  Each process has a segment table that specifies where the segments are
allocated.

Segmentation Properties

 Segments are constructed according to user semantics.

 This easily enables segment sharing and protection according to user

semantics.

 External fragmentation exists. Less severe compared with dynamic

allocation because average size of each segment is smaller (several in one
process).

Segmentation with Paging

 Exploiting good properties of paging:

o No external fragmentation
o faster allocation.

 Exploiting good properties of segmentation:

o Sharing.
o Protection.

A complier has many tables that are built up as compilation proceeds, possibly
including

1. The symbol table, contains names and attributes of variables

2. Source text being saved for the printed listing
3. Constant table contains all the integers and floating point used
4. Parse tree contains syntactic analysis of the program
5. Stack used for procedural call within the compiler

Each of first four tables grow continuously as the compilation proceeds

17
 Figure 6 In one dimensional address space with growing tables
The last one grows and shrinks in unpredictable ways during compilation

Consider if a program is having larger variables then usual and rest of the things
are limited

The allocated space for the symbol table may fill up, there are may be lots of
rooms in other tables

The compiler issue a message by saying compilation can’t be done due to lot of
variables.

Taking spaces of unused tables and giving it to one needed.

A straightforward way is to provide the mechanism with many completely

independent address space called segments

Each segment consist of address from 0 to maximum

Different segments do have different lengths

Segment length may change during execution

The length of the stack segment may increase, when something is pushed on to
the stack and decreased whenever something is popped of the stack

Each segment can grow and shrink independently without disturbing others

18
To specify an address a program must supply a two part address, a segment
number and an address within the segment

A segment is a logical entity, which the programmer is aware of and uses as a

logical entity

A segment must contain a procedure or an array or a stack or a collection of

variables

It does not contain a mixture of different types

Pure segmentation

Figure 7 development of checkerboarding

Physical memory containing 5 segments

Segment 1 is evicted and segment 7 is smaller is put in its place

Between segment 7 and segment 2 is an unused area that is hole

Segment 4 is replaced by segment 5

Segment 3 is replaced by segment 6

After the segment has been running for a while, memory will be divided into
number of chunks some containing segments some contains holes, this is called
checkerboarding or external fragmentation.

Waste memory can be dealt by compaction.

19
Segmentation with paging in MULTICS

If segments are large it is impossible to keep in main memory in their complete

run time

This leads to idea of paging them, so only those pages that are actually needed
have to be around.

Several significant systems have supported paged segments

MULTICS provide virtual memory of 218 segments which is more than 2,50,000

Each segment is 65536 (36 bit) word long

Designers treat each segment as virtual memory and to page it

Each MULTICS program has a segment table with one descriptor per segment
table

The are many many entries in the table, the segment table itself is a segment and
is paged

A segment descriptor contains an indication of whether segment is in memory or

not.

If any part of segment is in memory, the segment is considered to be in memory

and its page table will be in memory

If segment is in memory, its descriptor contains 18 bit pointer to its page table,
segment size, protection bits etc…

20
Physical addresses are 24 bits

Pages are 64 bytes, only 18 bits are needed to store a page table address

Each segment is an ordinary VAS

An address in MULTICS consists of two parts: segment and the address within the
segment

The address within the segment is further divided into a page number and a word
within the page

When memory reference occurs the following algorithm works.

21
 1. Segment number is used to find the segment descriptor
2. Check is made to see the segment page table is in memory, if
not in memory a segment fault occurs, if protection is violated
a fault TRAP occurs.
3. Page table entry for requested virtual page is checked, if page
is not in memory page fault is generated, if in memory the
address is extracted from the entry
4. The offset is added to give the memory address, where the
WORD is located
5. Finally the READ or WRITE is taken place

Register is used to locate the descriptor segment, page table which points to the
page of the descriptor segment

22
When the address is presented the hardware checks the virtual address is in TLB if
yes get the page frame number directly from the TLB and forms the actual
address

The address of 16 most recently reference pages are kept in the TLB

23