Background: Memory Hierarchy

◼ CPU can directly access

main memory and registers
only But, programs and data
are stored in disks.
◼ So, a program and its data
must be brought (from disk)
into memory
◼ Memory Hierarchy
⚫ Cache: small, fast, expensive;
SRAM
⚫ Main memory: medium-speed;
DRAM
⚫ Disk: slow, cheap, non-volatile
storage

1
 Memory Management

▪ Techniques to manage Main memory

efficiently
▪ Provides multitasking facility
▪ Responsible for memory allocation, de-
allocation and keep track for each
location
▪ Basic techniques:
• Fixed/Static Partitioning
• Variable/Dynamic Partitioning Systems
Engineering Department, QUEST, Nawabshah 14CS

2
 Fixed Partitioning

Partition of main memory into a set of non-

overlapping memory regions called partitions

Problems in Fixed Partitioning

▪ Main memory use is inefficient.
▪ A program occupies an entire partition
which can cause internal fragmentation.

Fixed partitions can be of equal or unequal sizes

Equal-size partitions. If there is an available
partition, a process can be loaded into that
partition
▪ because all partitions are of equal size, it
does not matter which partition is used.
▪ Doesn’t require any allocation policy
▪ Fast and easy
▪ Result internal fragmentation
▪ Leftover space in partition after program 3
assignment is called internal fragmentation
 Unequal-size partitions
(Multiple queues)

• Assign each process to the

smallest partition within which it
will fit.
• A queue exists for each partition
size.
• Tries to minimize internal
fragmentation.
• Some queues might be free while
other might be loaded

4
 Unequal-size partitions
(Single queues)

• The smallest available partition

that will hold the process is
selected.
• increases the level of
multiprogramming at the expense
of internal fragmentation.

5
 Variable Partitioning

▪ When a process arrives, OS allocates memory from a hole

large enough to accommodate it
▪ Hole – block of available memory;
▪ holes of various size are scattered throughout memory
▪ Operating system maintains information about:
a) allocated partitions b) free partitions (holes)
▪ increases the level of multiprogramming at the expense of
internal fragmentation

6
 Fragmentation

• External Fragmentation
OS
– Total memory space exists to satisfy a request, but it is
not contiguous
– Memory space left between two or more allocated process 9
processes process 10
• Internal Fragmentation
– Allocated memory may be slightly larger than requested process 2
memory;
– The size difference in memory internal to a partition, but
not being used.
• How can we reduce external fragmentation
– Compaction: Move memory to place all free memory
together in one large block,
• possible only if relocation is dynamic and address binding
is done at execution time

7
 Memory Hole/Allocation Management

▪ It is required to keep track of used and unused memory spaces

▪ Techniques:
• Bit-map: It uses a table where 0 represent empty spaces & 1 represents used spaces.
• Linked List: Every node contains 4 fields, 1st to show Process (P) or Memory-Hole
(H), 2nd to show starting address of P/H, 3rd to present length of P/H and 4th field
contains address of next node

8
 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
▪ Best-fit: Allocate the smallest hole that is big enough;
▪ Must search entire list, unless ordered by size
▪ Produces the smallest leftover hole

▪ Worst-fit: Allocate the largest hole;

▪ Must also search entire list
▪ Produces the largest leftover hole

▪ First-fit and best-fit are better than worst-fit in terms of speed and
storage utilization. But all suffer from fragmentation

9
Buddy System Allocation

10
Buddy System Allocation

11
Buddy System Allocation

12
 Simple/Basic Paging
▪ Divide physical memory into fixed-sized chunks/blocks called frames.
▪ Divide logical memory into blocks of same size pages.
▪ The process pages can be assigned to any free frames in main memory.
▪ Pages can be allocated in noncontiguous frames.
▪ MMU is a hardware device that maps logical (virtual) address to physical
address. In a simple MMU, the value in the dynamic relocation register (base) is
added to every address generated by a user process at the time it is sent to
memory

13
 Simple/Basic Paging Requirements

▪ Need to keep track of all free frames.

▪ To run a program of size n pages, need to find n
free frames and load program.
▪ Need to set up a page table to translate logical to
physical pages/addresses.
▪ Internal fragmentation possible only for the last
page.
▪ No external fragmentation possible

14
Page-Table & Free-Frame list

15
 Logical address in paging

▪ The logical address becomes a relative

▪ If16 bits addresses are used with page
▪ size = 1K, then 10 bits for offset and 6 bits available for
page number.
▪ Address translation from logical to physical is done
with help of page table.
▪ page table helps to obtain the physical address (frame
number, offset).

16
 Address Translation Scheme

▪ Logical address generated by CPU is divided into two parts:

– Page number (p) – used as an index into a page table which contains the base
address of each page in physical memory.
– Page offset/displacement (d) – combined with base address to define the
physical memory address
▪ If16 bits addresses are used with page size = 1K, then 10 bits for offset and 6 bits
available for page number.

17
Logical-to-Physical Address Translation in Paging

18
 Implementing Page Table

1. Keep Page Table in main memory:

▪ Page-table base register (PTBR) points to the page table.
▪ Page-table length register (PTLR) indicates size of the page table.
▪ Every data/instruction access requires two memory accesses
▪ one for the page table
▪ one for the data/instruction.
2. Keep Page Table in hardware (in MMU)
▪ Expensive if page table is large
▪ Faster but costly

19
 Implementing Page Table

3. Combination:
▪ Special fast-lookup hardware cache called Associative Memory
(Registers) or Translation Lookaside Buffer (TLB).
▪ enables fast parallel search:

▪ Address translation (p, d)

▪ If p is in associative register, get frame #
▪ else., get frame # from page table in memory.

20
Paging Hardware With TLB

21
 Memory Protection

• Memory protection
implemented by associating
a 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.

22
 Shared Pages

• Shared code:
– One copy of read-only code
shared among processes (i.e.,
text editors, compilers, window
systems).
– Shared code must appear in
same location in the logical
address space of all
processes.
• Private code and data:
– Each process keeps
separate copy of code and
data.
– The pages for the private
code and data can in the
logical address space
23
 Swapping
• A process can be swapped
temporarily out of memory to a
backing store, and then brought
back into memory for continued
execution

– Backing store – large enough to

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

– Roll out, roll in – swapping variant

used for priority-based scheduling
algorithms; lower-priority process
is swapped out so higher-priority
process can be loaded and
executed
• Swapping can free up memory for
additional processes.
24
 Virtual Memory

◼ A process must be in physical memory

⚫ How to run a large program that does not fit into physical memory?
⚫ Observation: Not all code or data needed at the same time
 Error handling codes
 Big arrays with max size
 Some options might not be needed at least at the same time
◼ Virtual memory
⚫ Allows execution of processes that are not completely in the
main memory
 What are the benefits of executing a program which is partially in memory?

◼ Virtual memory can be implemented via:

⚫ Demand paging
⚫ Demand segmentation 25
 Benefits of Virtual Memory
◼ User will have a very large logical address space
◼ User can execute programs larger than physical memory
◼ Especially helpful in multiprogrammed systems
⚫ Multiple processes can be executed concurrently because
⚫ Each process occupies small portion of memory
 The only part of the program needs to be in physical memory is the
one that is needed for execution at a given time
◼ Less I/O to load or swap user programs
◼ Physical Memory de/allocation
⚫ Allows address spaces to be shared by several processes
⚫ Allows for more efficient process creation
⚫ Keep recently used content in physical memory
⚫ Move less recently used stuff to disk
26
⚫ Movement to/from disk handled by the OS
 Virtual Memory
◼ Separation of user logical memory 2N
from physical memory
◼ Addresses local to the process Auxiliary
◼ Can be any size → limited by # of bits regions

in address (32/64)
◼ Virtual memory >> physical memory
◼ Holes are part of virtual address space Stack
but require actual physical pages
(frames) only when needed for
growing heap stack or shared libs etc.
Heap

Text
0
27
Virtual Memory That is Larger Than
Physical Memory

28
 Recall: Paging and Page Systems

◼ Virtual (logical) address -

………
⚫ Divided into pages -

28–32K 3 2 28–32K
◼ Physical memory 24–28K
24–28K 2
⚫ Divided into frames 20–24K 1 0 20–24K

◼ Page vs. Frame 16–20K 0 16–20K

12–16K - 3 12–16K
⚫ Same size address blocks
8–12K - 8–12K
⚫ Unit of mapping/allocation
4–8K - 1 4–8K

◼ A page is mapped to a frame 0–4K -

0–4K

⚫ All addresses in the same virtual

Virtual (Logical) Physical
page are in the same physical
memory memory
frame → offset in a page
29
.
An Example of Virtual/Physical Addresses

◼ Example:
How many
⚫ 64 KB virtual memory (16-bit) pages?
⚫ 32 KB physical memory (15-bit)
How many
⚫ 4 KB page/frame size (12-bit) as offset (d) frames?
Virtual address: Page #:4bits Offset: 12 bits
16 bits

Address
Translation

Physical address: Frame #:3bits Offset: 12 bits

15 bits
30
 Demand Paging

◼ Bring a page into memory

only when it is needed
⚫ Less I/O needed
⚫ Less memory needed
⚫ Faster response
⚫ More users

◼ Page is needed 
reference to it
⚫ Valid in memory  use it
⚫ invalid reference  abort
⚫ not-in-memory  bring to
memory
31
 Valid-Invalid Bit
◼ With each page table
entry a valid–invalid bit
is associated
v  in-memory,
i  not-in-memory)
◼ Initially valid–invalid bit
is set to i on all entries
◼ During address
translation,
if valid–invalid bit in
page table entry
is i  page fault (trap)

32
 Page Fault
1. Reference to a page,
If Invalid reference  abort
2. If not in memory, page
fault occurs (trap to OS)
3. Operating system
allocates an empty frame
4. Swap page into frame
5. Reset page tables,
set validation bit = v
6. Restart the instruction
that caused the page fault

33
Performance of Demand Paging

34
 Page Replacement
◼ To prevent over-allocation of memory, modify page-fault
service routine to include page replacement, which finds
some page in memory and swaps it out
◼ Same page may be brought into memory several times
◼ We need algorithms to minimize the number of page faults

◼ Include other improvement, e.g., use modify (dirty) bit to

reduce overhead of page transfers – only modified pages
are written to disk

◼ Page replacement completes separation between logical

memory and physical memory – large virtual memory can
be provided on a smaller physical memory
35
Need For Page Replacement

36
 Basic Page Replacement

◼ Find the location of the

desired page on disk
◼ If there is a free frame, use it
◼ If there is no free frame, use a
page replacement algorithm
1. Select a victim frame, swap it
out (use dirty bit to swap out only
modified frames)

2. Bring the desired page into

the (newly) free frame;
3. update the page and frame
tables

◼ Restart the process

37
 Page Replacement Algorithms

◼ How to select the victim frame?

⚫ You can select any frame, the page replacement will work;
⚫ but the performance???
◼ So we want an algorithms that gives the lowest page-fault rate
◼ Evaluate an algorithm by running it on a particular string of
memory references (reference string) and compute the
number of page faults on that string
In all our examples, we will have 3 frames and the following
reference string

38
 First-In-First-Out (FIFO) Algorithm
◼ Maintain an FIFO buffer
⚫ + The code used before may not be needed
⚫ - An array used early, might be used again and again
◼ Easy to implement
◼ Belady’s Anomaly: more frames  more page faults

39
 Optimal Algorithm
◼ Replace page that will not be used for longest period of time

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1 1
2 2
3 3
4 X 5
 Least Recently Used (LRU) Algorithm
◼ Use recent past as an approximation of the future
◼ Select the page that is not used for a long time…
⚫ OPT if you look at from backward
◼ Hard to implement (why?)

41