Chapter 3

Memory Management
3.1 Basic memory management
3.2 Swapping
3.3 Virtual memory
3.4 Design issues for paging systems
3.5 Implementation issues
3.6 Segmentation

1
Memory Management

2
 Memory Management
• Ideally programmers want memory that is
– large
– fast
– non volatile
• Memory hierarchy
– small amount of fast, expensive memory – cache
– some medium-speed, medium price main memory
– gigabytes of slow, cheap disk storage
• Memory manager handles the memory hierarchy

3
 Basic Memory Management
Monoprogramming without Swapping or Paging (No abstraction)

Mainframes, minicomputer Handheld, embedded PC

Three simple ways of organizing memory

- an operating system with one user process 4
 Basic Memory Management
Running Multiple Programs Without a Memory Abstraction

Figure 3-2. Illustration of the relocation problem. (a) A 16-KB program. (b) Another 16-KB program.
(c) The two programs loaded consecutively into memory.

5
 Basic Memory Management
Multiprogramming with Fixed Partitions

• Fixed memory partitions

– (a) separate input queues for each partition
– (b) single input queue
6
 Basic Memory Management
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

7
 Basic Memory Management
Dynamic relocation using a relocation register

8
 Basic Memory Management
Relocation and Protection
• Cannot be sure where program will be loaded in
memory
– address locations of variables, code routines cannot be
absolute
– must keep a program out of other processes’ partitions
• Use base and limit values
– address locations added to base value to map to physical
addr
– address locations larger than limit value is an error

9
 Basic Memory Management
Relocation and Protection
• Relocation registers used to protect user processes
from each other, and from changing operating-
system code and data
– Base register contains value of smallest
physical address
– Limit register contains range of logical
addresses – each logical address must be less
than the limit register
– MMU maps logical address dynamically

10
 Basic Memory Management
HW address protection with base and limit registers

11
 Swapping (1)
Schematic View of Swapping

12
 Swapping (2)

• Memory allocation changes as

– processes come into memory
– leave memory
• Shaded regions are unused memory
• External Fragmentation – total memory space exists to satisfy a request, but
it is not contiguous
• Internal Fragmentation – allocated memory may be slightly larger than
requested memory; this size difference is memory internal to a partition, but
not being used

13
 Swapping (3)

• (a) Allocating space for growing data segment

• (b) Allocating space for growing stack & data segment

14
 Swapping (4)
Multiple-partition allocation

• Multiple-partition allocation
– 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
– Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
– There are two ways to keep track of memory usages
• Memory Management with Bit Maps
• Memory Management with Linked Lists

15
 Swapping (4)
Multiple-partition allocation

Memory Management with Bit Maps

• (a) Part of memory with 5 processes, 3 holes
– tick marks show allocation units
– shaded regions are free
• (b) Corresponding bit map
• (c) Same information as a list

16
 Swapping (5)
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
• Next fit: Start seaching the list from the place where it
left off last time
• 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 better than worst-fit in terms of
speed and storage utilization

17
1. Xem PC của chúng ta: (CPU) Cache, Ram,
HDD: capacity, price.
2. List 4 Operating systems in PC environments
– Market shares? Which one having the maximum
market share value?
– Reasons to make that one become the best one?
3. List 4 Operating systems in Smart Phone
environments
– The same questions as above ones.

18
Virtual Memory
Paging

19
 Virtual Memory
• Virtual memory – separation of user logical memory from
physical memory.
– Only part of the program needs to be in memory for
execution
– Logical address space can therefore be much larger than
physical address space
– Allows address spaces to be shared by several processes
– Allows for more efficient process creation
• Virtual memory can be implemented via:
– Demand paging
– Demand segmentation

20
Virtual Memory
Paging

21
 Virtual Memory
Paging

The position and function of the MMU

22
 Virtual Memory
Paging
• Virtual address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available
• Divide physical memory into fixed-sized blocks called Page
frames (size is power of 2, between 512 bytes and 8,192
bytes)
• 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
• Internal fragmentation

23
 Virtual Memory
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 number page offset
p d
m-n n

– Page offset (d) – combined with base address to define

the physical memory address that is sent to the memory
unit
– For given logical address space 2m and page
size 2n
24
Virtual Memory
Paging Hardware

25
 Virtual Memory
Paging: Example

The relation between

virtual addresses
and physical
memory addres-
ses given by
page table

26
 Virtual Memory
Page Tables: Example

Internal operation of MMU with 16 4 KB pages 27

 Virtual Memory
Two-level page tables

• 32 bit address with 2 page table fields

• Two-level page tables
28
29
 Virtual Memory
Typical page table entry

Typical page table entry

30
 Virtual Memory
Implementation of Page Table

• Page table is kept in main memory

• Page-table base register (PTBR) points to the page table
• Page-table length register (PRLR) indicates size of the
page table
• In this scheme every data/instruction access requires two
memory accesses. One for the page table and one for the
data/instruction.
• The two memory access problem can be solved by the use
of a special fast-lookup hardware cache called associative
memory or translation look-aside buffers (TLBs)

31
 Virtual Memory
Paging Hardware With TLB

32
 Virtual Memory
TLBs – Translation Lookaside Buffers

A TLB to speed up paging

33
 Virtual Memory
Page Fault

1. If there is a reference to a page, Just not in

memory: page fault,
2. Trap to operating system:
3. Get empty page frame, Determine page on backing
store
4. Swap page from disk into page frame in memory
5. Modifies page tables, Set validation bit = v
6. Restart the instruction that caused the page fault

34
 Virtual Memory
Steps in Handling a Page Fault

35
 Virtual Memory
Page Replacement Algorithms
• What happens if there is no free frame?
• Page replacement – find some page in
memory, but not really in use, swap it out
– algorithm
– performance – want an algorithm which will
result in minimum number of page faults
• Same page may be brought into memory
several times

36
 Virtual Memory
Basic Page Replacement
1. Find the location of the desired page on disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim frame
3. Bring the desired page into the (newly) free
frame; update the page and frame tables
4. Restart the process

37
Virtual Memory
Page Replacement

38
 Virtual Memory
Page Replacement Algorithms

39
• Example: the process has 5 pages, and is allocated in 3 frames

40
41
• Example: the process has 5 pages, and is allocated
in 3 frames

42
      
  
 
43
44
45
46
 Virtual Memory
Design issues: Local versus Global Allocation Policies

• (a) Original configuration

• (b) Local page replacement
• (c) Global page replacement
47
 Virtual Memory
Design issues: Page Frame Allocation

Page fault rate as a function of the number of

page frames assigned
48
 Virtual Memory
Design issues: Page Size (1)
Small page size
• Advantages
– less internal fragmentation
– better fit for various data structures, code sections
– less unused program in memory
• Disadvantages
– programs need many pages, larger page tables

49
 Virtual Memory
Design issues: Separate Instruction and Data Spaces

• One address space

• Separate I and D spaces
50
 Virtual Memory
Design issues: Shared Pages

Two processes sharing same program sharing its page table

51
 Virtual Memory
Implementation Issues
Operating System Involvement with Paging
Four times when OS involved with paging
1. Process creation
 determine program size
 create page table
2. Process execution
 MMU reset for new process
 TLB flushed
3. Page fault time
 determine virtual address causing fault
 swap target page out, needed page in
4. Process termination time
 release page table, pages

52
 Virtual Memory
Implementation Issues
Page Fault Handling (1)

1. Hardware traps to kernel

2. General registers saved
3. OS determines which virtual page needed
4. OS checks validity of address, seeks page frame
5. If selected frame is dirty, write it to disk

53
 Virtual Memory
Implementation Issues
Page Fault Handling (2)
6. OS brings schedules new page in from disk
7. Page tables updated
8. Faulting instruction backed up to when it began
9. Faulting process scheduled
10. Registers restored, Program continues

54
 Virtual Memory
Implementation Issues
Separation of Policy and Mechanism

Page fault handling with an external pager 55

Virtual Memory
Segmentation

56
 Virtual Memory
Segmentation (1)

• One-dimensional address space with growing tables

• One table may bump into another 57
 Virtual Memory
Segmentation (2)

Allows each table to grow or shrink, independently

58
 An example of Segmentation
stack
1400
procedure procedure
segment 3 2400
limit base
segment 0 symbol 0 1000 1400
3200
table 1 400 6300 stack
function
2 400 4300
segment 4 4300
sqrt 3 1100 3200 main
main program 4 1000 4700
4700
segment 1 segment symbol table
segment 2 table
5700

6300 function sqrt

logical address space
physical memory space
59
Segmentation Hardware

60
 Segmentation translation
• Virtual address: <segment-number, offset>
• Segment table maps segment-number to segment
information
– Base: starting address of segment in physical memory
– Limit: length of segment
– Addition metadata inlcudes protection bits
• Limit & protection checked on each access
• 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.
61
 Virtual Memory
Segmentation (3)

Comparison of paging and segmentation 62

 Virtual Memory
Implementation of Pure Segmentation (4)

(a)-(d) Development of checkerboarding

(e) Removal of the checkerboarding by compaction
63
 Virtual Memory
Segmentation with Paging: Pentium (1)

64
 Virtual Memory
Segmentation with Paging: Pentium (2)

A Pentium selector
GDT (Global Descriptor Table), LDT (Local Descriptor Table)

65
 Virtual Memory
Segmentation with Paging: Pentium (3)

66
 Virtual Memory
Segmentation with Paging: Pentium (4)

• Pentium code segment descriptor

• Data segments differ slightly
67
 Virtual Memory
Segmentation with Paging: Pentium (5)

68
 Virtual Memory
Segmentation with Paging: Pentium (6)

Conversion of a (selector, offset) pair to a linear address

69
 Virtual Memory
Segmentation with Paging: Pentium (7)

Mapping of a linear address onto a physical address

70
 Virtual Memory
Segmentation with Paging: Pentium (8)

71
Pentium address translation

1 1 1
0 0 2

Can cover up to 4
MB
physical address
72
space
 Virtual Memory
Segmentation with Paging: Pentium (9)

Level

Protection on the Pentium

73