Transcript Ceng 334 - Operating Systems

Chapter 3.2 : Virtual Memory
• What is virtual memory?
• Virtual memory management schemes
• Paging
• Segmentation
• Segmentation with paging
• Page table management
Ceng 334 - Operating Systems
3.2-1
Problems with Memory
Management Techniques so far
1. Unused (wasted) memory due to
fragmentation
2. Memory may contain parts of program
which are not used during a run (ie., some
routines may not be accessed in that
particular run)
3. Process size is limited with the size of
physical memory
Ceng 334 - Operating Systems
3.2-2
Virtual Memory (VM)
Virtual memory of process on disk
Map (translate)
virtual address to real
Real memory of system
Ceng 334 - Operating Systems
3.2-3
Virtual Memory (VM)
• VM is conceptual
• It is constructed on disk
• Size of VM is not limited (usually larger
than real memory)
• All process addresses refer to the VM image
• When the process executes all VM
addresses are mapped on to real memory
Ceng 334 - Operating Systems
3.2-4
Did We Solve the “Problems”?
1. Unused (wasted) memory due to
fragmentation (We’ll see!)
2. Memory may contain parts of program
which are not used during a run
– YES! Virtual memory contents are loaded
into memory on demand
3. Process size is limited with the size of
physical memory
– YES! Process size can be larger than real
memory
Ceng 334 - Operating Systems
3.2-5
(Pure) Paging
• Virtual and real memory are divided into
fixed sized pages
• Programs are divided into pages
• A process address (both in virtual & real
memory) has two components
Page #
Ceng 334 - Operating Systems
Offset within page
3.2-6
Interpretation of an Address
• 16 bits for addressing means that the
memory addressed is 64K bytes (0000 FFFF)
• Suppose page size is 4K bytes (12 bits)
• The virtual memory has 16 pages (4 bits)
• Real memory can have at the most 16 pages
• Example :
address : 7 F
B C
0111 1111 1011 1100
Page #
Ceng 334 - Operating Systems
Offset
3.2-7
The relation between virtual addresses
and physical memory addresses
64K Virtual Memory
32K Real Memory
Ceng 334 - Operating Systems
3.2-8
Paging (Cont.)
• When process pages are transferred from
VM to real memory, page numbers must be
mapped from virtual to real memory
addresses
• This mapping is done by software &
hardware
• When the process is started only the first
page (main) is loaded. Other pages are
loaded on demand
Ceng 334 - Operating Systems
3.2-9
Virtual Memory – Memory Management Unit
The position and function of the MMU
Ceng 334 - Operating Systems
3.2-10
Internal operation of MMU with 16 4 KB pages
Note that virtual
address is 16 bits
(64K virtual memory)
but the physical
address is 15 bits
(32K real memory)
Ceng 334 - Operating Systems
3.2-11
Page Tables
Page Table
0
1
2
3
4
5
6
7
8
Page Table Entry
Page frame #
Page protection
Reference bit
Modification bit
Validity bit
• Index of page table is the virtual page #
Ceng 334 - Operating Systems
3.2-12
Page Table Entry Fields
• Validity bit is set when the page is in
memory
• Reference bit is set set by the hardware
whenever the page is referred
• Modified bit is set whenever the page is
modified
• Page-protection bits set the access rights
(eg., read, write restrictions)
Ceng 334 - Operating Systems
3.2-13
Address Mapping in Paging
Virtual memory address
Page #
Offset within page
Page Table Register
+
PT 1
PT2
Catenate
..
PTn
Real memory address
Page tables of processes
Ceng 334 - Operating Systems
3.2-14
Address Mapping in Paging (Cont.)
• During the execution every page reference
is checked against the page map table entry
• If the validity bit is set (ie., page is in
memory) execution continues
• If the page is not in memory a page fault
(interrupt - trap) occurs and the page is
fetched into memory
• If the memory is full, pages are written back
using a page replacement algorithm
Ceng 334 - Operating Systems
3.2-15
Memory Management Problems :
Re-visit due to paging
1. Unused (wasted) memory due to fragmentation
– ONLY on the last page (Page Break)
2. Memory may contain parts of program which are
not used during a run
– Virtual memory contents are loaded into memory on demand
3. Process size is limited with the size of physical
memory
– Process size can be larger than real memory
• Furthermore, program does not occupy contiguous
locations in memory (virtual pages are scattered in
real memory)
Ceng 334 - Operating Systems
3.2-16
Segmentation
• Pages are fixed in size, segments are
variable sized
• A segment can be a logical entity such as
–
–
–
–
–
Main program
Some routines
Data of program
File
Stack
Ceng 334 - Operating Systems
3.2-17
Segmentation (Cont.)
• Process addresses are now in the form
Segment #
Offset within segment
• Segment Map Table has one entry for each
segment and each entry consist of
– Segment number
– Physical segment starting address
– Segment length
Ceng 334 - Operating Systems
3.2-18
Segmentation (1)
• One-dimensional address space with growing tables
• One table may bump into another
Ceng 334 - Operating Systems
3.2-19
Segmentation (2)
Allows each table to grow or shrink, independently
Ceng 334 - Operating Systems
3.2-20
Segmentation (3)
Comparison of paging and segmentation
Ceng 334 - Operating Systems
3.2-21
Implementation of Pure Segmentation
(a)-(d) Development of fragmentation
(e) Removal of the fragmentation by compaction
Ceng 334 - Operating Systems
3.2-22
Problems with Segmentation
• Similar problems in dynamic partitioning
– Fragmentation in real
memory
– Relocation is necessary
for compaction
Ceng 334 - Operating Systems
3.2-23
Segmentation with Paging
• Segmentation in virtual memory, paging in
real memory
• A segment is composed of pages
• An address has three components
Segment #
Page #
Offset within page
• The real memory contains only the
demanded pages of a segment, not the full
segment
Ceng 334 - Operating Systems
3.2-24
Addressing in Segmentation with
Paging
Segment #
Segment Table
Ceng 334 - Operating Systems
Page #
Page Tables
Offset within page
Pages
3.2-25
Segmentation with Paging: MULTICS (1)
• Descriptor segment points to page tables
• Segment descriptor – numbers are field lengths
Ceng 334 - Operating Systems
3.2-26
Segmentation with Paging: MULTICS (2)
A 34-bit MULTICS virtual address
Ceng 334 - Operating Systems
3.2-27
Segmentation with Paging: MULTICS (3)
Conversion
of a 2-part
MULTICS address into a main memory address
Ceng
334 - Operating
Systems
3.2-28
Segmentation with Paging: MULTICS (4)
• Simplified version of the MULTICS TLB
• Existence of 2 page sizes makes actual TLB more complicated
Ceng 334 - Operating Systems
3.2-29
Segmentation with Paging: Pentium (1)
A Pentium selector
Ceng 334 - Operating Systems
3.2-30
Segmentation with Paging: Pentium (2)
• Pentium code segment descriptor
• Data
segments differ slightly
Ceng 334 - Operating
Systems
3.2-31
Segmentation with Paging: Pentium (3)
Conversion of a (selector, offset) pair to a linear address
Ceng 334 - Operating Systems
3.2-32
Segmentation with Paging: Pentium (4)
Mapping of a linear address onto a physical address
Ceng 334 - Operating Systems
3.2-33
Segmentation with Paging: Pentium (5)
Level
Protection on the Pentium
Ceng 334 - Operating Systems
3.2-34
How Big is a Page Table?
• Consider a full 2 32 byte (4GB) address
space
– Assume 4096 byte (2 12 byte) pages
– 4 bytes per page table entry
– The page table has 2 32/2 12 (= 2 20 )
entries (one for each page)
– Page table size would be 2 22 bytes (or 4
megabytes)
Ceng 334 - Operating Systems
3.2-35
Problems with Direct Mapping?
• Although a page table is of variable length
depending on the size of process, we can
not keep them in registers
• Page table must be in memory for fast
access
• Since a page table can be very large (4MB),
page tables are stored in virtual memory and
be subjected to paging like process pages
Ceng 334 - Operating Systems
3.2-36
How to Solve?
• Two-level Lookup
• Inverted Page Tables
• Translation Lookaside Buffers
Ceng 334 - Operating Systems
3.2-37
Two-Level Lookup
Virtual Address - 32 bits (4 GB)
Directory
Page
Offset
12 bits - 4096 Byte pages
10 bits - 1024 pages
10 bits - 1024 directories
Ceng 334 - Operating Systems
3.2-38
Two-Level Lookup (Cont.)
Dir
Page Offset
+
+
Page Table
Physical Address
Page Directory
Ceng 334 - Operating Systems
3.2-39
Two-Level Lookup (Cont.)
• A process is represented by one or more
entries of the page directory (ie., several
page tables)
• Typically a page table size is set as one page
which makes swapping easier
• This is one of the addressing schemes used
by Intel family of chips (Intel chips can use
paging, segmentation or a combination of
both)
Ceng 334 - Operating Systems
3.2-40
Two-Level Lookup (Cont.)
Second-level page tables
Top-level
page table
• 32 bit address with 2 page table fields
• Two-level page tables
Ceng 334 - Operating Systems
3.2-41
Inverted Page Tables
Page #
Virtual Address
Page #
Offset within page
Page # 101
PID
21
17
76
23
213
32
Process # 17
hash
Hash # 2
3
Hash Table
Page Frame Table
Ceng 334 - Operating Systems
3.2-42
Inverted Page Tables (Cont.)
• The virtual page number is hashed to
point to a hash table
• The hash table contains a pointer to the
inverted page table
• Inverted page table contains page table
entries (one for each real memory
page)
• Entries having the same hash codes are
chained
Ceng 334 - Operating Systems
3.2-43
Inverted Page Tables (Cont.)
• A fixed portion of memory is used for
mapping regardless of the number of
processes or virtual pages
• This approach is used by IBM’s
AS/400 and RISC System/6000
computers
Ceng 334 - Operating Systems
3.2-44
Translation Lookaside Buffer
Virtual Address
Page #
Offset
TLB
TLB Miss
Page
Table
Page Fault
Ceng 334 - Operating Systems
TLB Hit
Frame #
Offset
Real Address
3.2-45
Translation Lookaside Buffer
(Cont.)
• Translation lookaside buffer (TLB) is a
cache for page table entries
• TLB contains page table entries that have
been most recently used
• Whenever the page table is referred (TLB
miss), the page table entry is also copied to
the TLB
• TLB is usually an associative memory
(content addressable memory)
Ceng 334 - Operating Systems
3.2-46
TLBs – Translation Lookaside Buffers
A TLB to speed up paging
Ceng 334 - Operating Systems
3.2-47