Memory Management

Objectives
• To provide a detailed description of various ways of organizing
memory hardware
• To discuss various memory-management techniques, including
paging and segmentation
• To provide a detailed description of the Intel Pentium, which
supports both pure segmentation and segmentation with paging
Background
• Program must be brought (from disk) into memory and placed within a process
for
it to be run
• Main memory and registers are only storage CPU can access directly
• Memory unit only sees a stream of addresses + read requests, or address + data
and write requests
• Register access in one CPU clock (or less)
• Main memory can take many cycles, causing a stall
• Cache sits between main memory and CPU registers
• Protection of memory required to ensure correct operation
Base and Limit Registers
• A pair of base and limit registers define the logical address space
• CPU must check every memory access generated in user mode to be sure it is between base
and limit for that user
Binding of Instructions and Data to Memory
• Address binding of instructions and data to memory addresses
can happen at three different stages
✔ Compile time: If memory location known a priori,
absolute code can be generated; must recompile code if
starting location changes
✔ Load time: Must generate relocatable code 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
one memory segment to another
✔ Need hardware support for address maps (e.g., base
and limit registers)
Logical vs. Physical Address Space
• The concept of a logical address space that is bound to a separate physical
address space is central to proper memory management
✔ Logical address – generated by the CPU; also referred to as virtual address
✔ 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 (virtual) and physical addresses differ in
execution-time address-binding scheme
• Logical address space is the set of all logical addresses generated by a program
• Physical address space is the set of all physical addresses generated by a
program
• The user program deals with logical addresses; it never sees the real physical addresses
✔ Execution-time binding occurs when reference is made to location in memory
✔ Logical address bound to physical addresses
Dynamic relocation using a relocation register
• Memory Management Unit (MMU) is a hardware
device that at run time maps virtual to
physical address
• 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
• 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
• OS can help by providing libraries to implement dynamic
loading
Dynamic Linking
• Static linking – system libraries and program code combined by the loader
into the binary program image
• 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
 Swapping
• A process can be swapped temporarily out of memory to a backing
store, and then brought back into memory for continued execution
✔ Total physical memory space of processes can exceed physical memory

• Backing store – fast disk large enough to accommodate copies of

all memory images for all users; must provide direct access to these
memory images

• System maintains a ready queue of ready-to-run processes which

have memory images on disk

✔ If next processes to be put on CPU is not in memory, need to swap out a

process and swap in target process

 Swapping (Cont’d)
• Major part of swap time is transfer time; total transfer time is directly
proportional to the amount of memory swapped
✔ 100MB process swapping to hard disk with transfer rate of 50MB/sec
✔ Swap out time of 2000 ms
✔ Plus swap in of same sized process
✔ Total context switch swapping component time of 4000ms (4 seconds)

• Modified versions of swapping are found on many systems (i.e.,

UNIX, Linux, and Windows)

✔ Swapping normally disabled
✔ Started if more than threshold amount of memory allocated
✔ Disabled again once memory demand reduced below threshold
Contiguous Allocation
• Main memory must support both OS and user processes
• Limited resource, must allocate efficiently
• Main memory usually into two partitions:
⮚ Resident operating system
⮚ User processes
⮚ Each process contained in single contiguous section of memory
• In contiguous memory allocation, each process is contained in a single section of memory that is
contiguous to the section containing the next process.
In Class Practice#1
Consider following memory and a list of processes, how all these processes get executed? All processes
arrive at time 0.

Process Memory Burst Time

650 K 9
1000 K 4
250 K 19
800 K 7
400 K 14
Multiple-partition allocation
■ Multiple-partition allocation
● Variable-partition sizes for efficiency
● Hole – block of available memory; holes of various size are scattered throughout memory
● When a process arrives, it is allocated memory from a hole large enough to accommodate it
● Process exiting frees its partition, adjacent free partitions combined
● Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes?

• First-fit: Allocate the first hole that is big enough. Searching can start either at the beginning of the
set of holes or at the location where the previous first-fit search ended. We can stop searching as
soon as we find a free hole that is large enough.

• Best-fit: Allocate the smallest hole that is big enough. We must search the entire list, unless
the list is ordered by size. This strategy produces the smallest leftover hole.

• Worst-fit: Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size.
This strategy produces the largest leftover hole, which may be more useful than the smaller leftover
hole from a best-fit approach.

• Simulations have shown that both first fit and best fit are better than worst fit in terms of
decreasing time and storage utilization. Neither first fit nor best fit is clearly better than the other in
terms of storage utilization, but first fit is generally faster
In Class Practice #2
Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB (in order), how
would the first-fit, best-fit, and worst-fit algorithms place processes of size 115 KB, 500 KB, 358 KB, 200
KB, and 375 KB (in order)?
 Fragmentation

• External Fragmentation – total memory space exists to satisfy a request, but it is not
contiguous
• Reduce external fragmentation by compaction
✔ Shuffle memory contents to place all free memory together in one large block
✔ Compaction is possible only if relocation is dynamic, and is done at execution time
• Another possible solution to the external-fragmentation problem is to permit the logical
address space of the processes to be noncontiguous, thus allowing a process to be
allocated physical memory wherever such memory is available.
• Two complementary techniques achieve this solution : segmentation and paging.
 Segmentation

• Normally, when a program is compiled, the compiler automatically

constructs segments reflecting the input program.
• A program is a collection of segments
• A segment is a logical unit such as:
main program
procedure
function
method
object
local variables, global variables
common block
stack
symbol table
arrays
Logical View of Segmentation
Segmentation Architecture:

• Logical address consists of a two tuple:

<segment-number, offset>

• Segment table – maps two-dimensional physical addresses; each table entry has:
• base – contains the starting physical address where the segments reside in memory
• limit – specifies the length of the segment

• Segment-table base register (STBR) points to the segment table’s location in memory

• Segment-table length register (STLR) indicates number of segments used by a program:

segment number s is legal if s < STLR

• Since segments vary in length, memory allocation is a dynamic storage-allocation problem

Segmentation Hardware
Paging
• Physical address space of a process can be noncontiguous; process is allocated physical
memory whenever the latter is available
✔ Avoids external fragmentation
✔ Avoids problem of varying sized memory chunks
• Divide physical memory into fixed-sized blocks called frames
✔ Size is power of 2, between 512 bytes and 16 Mbytes
• Divide logical memory into blocks of same size called pages
• Keep track of all free frames
• To run a program of size N pages, need to find N free frames and load program
• Set up a page table to translate logical to physical addresses
• Backing store likewise split into pages
• Still have Internal fragmentation
Address Translation Scheme
• Address generated by CPU 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

page number page offset

p d
m -n n
✔ For given logical address space 2m and page size 2n
✔ p is an index into the page table and d is the displacement within the page.
Paging Hardware
Paging Model of Logical and Physical Memory
Paging Example

n=2 and m=4 32-byte memory and 4-byte pages

Paging (Cont.)
• Calculating internal fragmentation
✔ Page size = 2,048 bytes
✔ Process size = 72,766 bytes
✔ 35 pages + 1,086 bytes
✔ Internal fragmentation of 2,048 - 1,086 = 962 bytes
✔ Worst case fragmentation = 1 frame – 1 byte
Paging Hardware With Translation Look-aside
Buffer(TLB)
Effective Access Time
Hit ratio – percentage of times that a page number is found in the associative
registers; ratio related to number of associative registers

Example:
Consider hit ratio = 80%, memory access time : 100 ns ,
Effective Access Time (EAT)
• EAT = TLB hit time* hit_ratio + TLB miss time* (1- hit_ratio)
• EAT = 0.80 x 100 + 0.20 x 200 = 120ns

• Consider more realistic hit ratio = 99%, 100ns for memory access
• EAT = 0.99 x 100 + 0.01 x 200 = 101ns
Hierarchical Page Tables
• Break up the logical address space into multiple page tables
• A simple technique is a two-level page table
• We then page the page table
Hierarchical Page Tables (Cont’d)

Address Translation
Scheme

Two Level Page Table

Scheme
Two-Level Paging Example
• A logical address (on 32-bit machine with 1K page size) is divided into:
✔ a page number consisting of 22 bits
✔ a page offset consisting of 10 bits

• Since the page table is paged, the page number is further divided into:
✔ a 12-bit page number
✔ a 10-bit page offset

• Thus, a logical address is as follows:

• where p1 is an index into the outer page table, and p2 is the displacement within the page
of the inner page table
 Inverted Page Table
• An inverted page table has one entry for each real page (or frame) of memory.
• Each entry consists of the virtual address of the page stored in that real
memory location, with information about the process that owns the page.
<process-id, page-number, offset>

Inverted Page Table

Architecture
 Homework Question #1
Consider a computer system with a 32-bit logical address and 8-KB page size. The
system supports up to 1 GB of physical memory. How many entries are there in each
of the following?

a) A conventional, single-level page table

b) An inverted page table

#2
Consider following segment table , which following logical address will produce trap addressing error?
a) 0, 265
b) 1, 19
c) 2, 1024 Segment No. Base Limit

d) 3, 100 0 1219 365

e) 4, 543 1 100 250

2 1650 1024

3 355 115

4 2048 650
#3

A 1200 KB memory is managed using variable partitions but no compaction. It currently has three
partitions of sizes 158 KB , 215 KB and 127KB respectively. What is the smallest allocation request in KB
that could be denied?
#4
Consider a logical address space of 2,048 pages with a 4-KB page size,
mapped onto a physical memory of 512 frames.

a. How many bits are required in the logical address?

a. b. How many bits are required in the physical address

#5
Assuming a 1-KB page size, what are the page numbers and offsets for the
following address references (provided as decimal numbers):

a. 3085

b. 42095

c. 650000
 #6
• Consider a paging system with the page table stored in memory. a. If a memory
reference takes 50 nanoseconds:

a) how long does a paged memory reference take?

b) If we add TLBs, and if 75 percent of all page-table references are found in the
TLBs, what is the effective memory reference time? (Assume that finding a page-
table entry in the TLB stakes 2 nanoseconds, if the entry is present.)
#7
Considering following memory, what is the minimum data movement required to perform compaction?