Virtual memory
Previously, we talked about virtualization
static data
Copyright By PowCoder代写 加微信 powcoder
Virtual memory
static data
Virtual memory
static data
Virtual memory
static data
Virtual memory
Previously, we’ve talked about sharing the processor.
The Machine 2
How about sharing DRAM?
Reviews: abstractions we’ve learned so far …
Process — the abstraction of a machine
Thread — the abstraction of a processor
Virtual memory — the abstraction of the memory
Why: If we expose memory directly to the processor (I)
What if my program needs more memory?
0f00bb27 509cbd23 00005d24 0000bd24 2ca422a0 130020e4 00003d24 2ca4e2b3
00c2e800 00000008 00c2f000 00000008 00c2f800 00000008 00c30000 00000008 00c2e800 00000008 00c2f000 00000008
InstructionsInstructions Data
Why: If we expose memory directly to the processor (II)
What if my program runs on a machine with a different memory size?
0f00bb27 00c2e800
00000008 00005d24 00c2f000 0000bd24 00000008
2ca422a0 130020e4 00000008
00003d24 00c30000 2ca4e2b3 00000008
Memory Memory
Instructions Data
Why: If we expose memory directly to the processor (III)
What if both programs need to use memory?
Instructions Data
Instructions Data
The virtual memory abstraction Segmentation
Demand paging
Making demand paging efficient Swapping
The Virtual Memory Abstraction
instruction
instruction
Virtual memory
0x80000000
0x80008000
tual Memory Space
rtual Memory Space
Instructions Data
Instructions Data
software/programmer
The operating system and hardware work together to handle the mapping between virtual memory addresses and real/ physical memory addresses
Virtual memory
An abstraction of memory space available for programs/ Programs execute using virtual memory address
#define _GNU_SOURCE
Demo revisited
Process A’s Mapping Table
&a = 0x601090
#include
Process B’s Mapping Table
#include
#include
#include
#include
#include
#include
int main(int argc, char *argv[])
int i, number_of_total_processes=4;
number_of_total_processes = atoi(argv[1]);
for(i = 0; i< number_of_total_processes-1 && fork(); i++);
srand((int)time(NULL)+(int)getpid());
fprintf(stderr, "\nProcess %d is using CPU: %d. Value of a is %lf and address of a is %p\n”,getpid(), cpu, a, &a);
sleep(10);
fprintf(stderr, "\nProcess %d is using CPU: %d. Value of a is %lf and address of a is %p\n”,getpid(), cpu, a, &a);
How to map from virtual to physical? Let’s start from segmentation
The compiler generates code using virtual memory addresses
Segmentation
The OS works together with hardware to partition physical memory
space into segments for each running application
The hardware dynamically translates virtual addresses into physical
memory addresses
Segmentation
current segment
(CS): data
load 0x8 0
0x20000000
0x40000000
Segment Table
0x40000000
0x40000000 + 0x8
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
00c2e800 00000008
00c2f000 00000008
00c2f800 00000008
00c30000 00000008
00000000 00000000
00000000 00000000
= 0x40000008
Segment Table
0x20000000
Data Instructions
Instructions Data Instructions
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
current segment
(CS): code
load 0x20000008
0 0x20000000
0x40000000
00c2e800 00000008
00c2f000 00000008
00c2f800 00000008
00c30000 00000008
00000000 00000000
00000000 00000000
Segment Table
0x40000000
This belongs to
another process!
0x40000008 =
+ 0x20000008
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
0x20000000
egment Table
0x20000000
Data Instructions
Instructions Data Instructions
current segment
(CS): code
load 0x20000008
is offset < bound?
0f00bb27 509cbd23
a segmentation fault (often shortened to
130020e4 00005d24 0000bd24 segfault0)0,0ra03isde2d4 by hardware with memo2ryca422a0 130020e4
2ca4e2b3 0x20000000 00003d24 2ca4e2b3 protection, when the software has
00c2e800 0f0
attempted to access a restricted area of
memory00(ac2mf0e0m0ory access violation).
Segment Table
00c2e800 00000008
00c2f000 00000008
Segment Table
0bb27 509cbd23
05d24 0000bd24
422a0 130020e4
00003d24 2ca4e2b3
0x20000000
0x40000000
00c2f800 00000008
00c30000 00000008
0x30000000
Bound 00000008
0x40000000
0x40000000
Yes— proceed
No— segmentati on fault!!!
Data Instructions
Instructions Data Instructions
Now, make sure you login to Poll Everywhere (through the App or the website) with UCRNetID
Now, you have about 90 seconds to answer the question!
Regarding segments, how many of the followings are correct?
! Eachsegmentmustoccupycontiguousphysicalmemorylocations
" Thesystemmustallocateandreservethephysicalmemorylocationsfora segment whenever the program using that segment is scheduled
# Anapplicationcanpre-allocatealargesegmentbutturnoutnotusingeverybyte in the segment
$ Thesystemmaynotbeabletoallocatespaceforasegmenteventhoughthe total capacity of available physical locations is sufficient
Efficiency of Segmentation
https://www.pollev.com/hungweitseng close in
Now, it’s time to discuss with your surroundings (with masks on) — and make sure you vote again after the discussion!
Internal fragment
0 0x20000000
0x40000000
0x20000000 0x20000000
Segment Table
0 0x20000000
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
00c2e800 00000008
00c2f000 00000008
00c2f800 00000008
00c30000 00000008
00000000 00000000
00000000 00000000
0x40000000 0x30000000
Segment Table
We waste some space in the allocated segment
0x40000000
Data Instructions
Instructions Data Instructions
External fragment
Segment Table
0 0x20000000
0x40000000
0x40000000
Even though we have space, we still cannot map data section!
0x20000000 0x20000000
0x40000000
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
0f00bb27 509cbd23
00005d24 0000bd24
2ca422a0 130020e4
00003d24 2ca4e2b3
00c2e800 00000008
00c2f000 00000008
00c2f800 00000008
00c30000 00000008
00000000 00000000
00000000 00000000
Segment Table
0x20000000
0x40000000
0x30000000
Data Instructions
Instructions Data Instructions
each of this is a fix-sized page
Instructions Data
Instructions Data
Paging: partition virtual/physical memory spaces into fix-sized
Page fault
instruction
VirtualA f m u a pe
each of this is a fix-sized page
Page fault!
Instructions Data
Instructions Data
Page fault
Paging: partition virtual/physical memory spaces into fix-sized Page fault: when the requested page cannot be found in the
physical memory — created the demand of allocating pages!
Demand paging
instruction
0x80000000
instruction
each of this is a fix-sized page
0x80008000
Page fault!
Virtual A s Space for Ch m Page fault! u a pple Music
Page fault!
Page fault!
Instructions Data
Instructions Data
Demand paging
Paging: partition virtual/physical memory spaces into fix-sized Page fault: when the requested page cannot be found in the
Demand paging: Allocate a physical memory page for a virtual memory page when the virtual page is needed (page fault occurs)
There is also shadow paging used by embedded systems, mobile phones — they load the whole program/data into the physical memory when you launch it
physical memory — created the demand of allocating pages!
Segmentation v.s. demand paging
How many of the following statements is/are correct regarding
segmentation and demand paging?
! Segmentscancausemoreexternalfragmentationsthandemandpaging
" Pagingcanstillcauseinternalfragmentations
# Theoverheadofaddresstranslationinsegmentationishigher
$ Consecutivevirtualmemoryaddressmaynotbeconsecutiveinphysical address if we use demand paging
A. 0 B. 1 C. 2 D. 3 E. 4
https://www.pollev.com/hungweitseng close in
Segmentation v.s. demand paging
How many of the following statements is/are correct regarding
! Segmentscancausemoreexternalfragmentationsthandemandpaging
segmentation and demand paging?
" Pagingcanstillcauseinternalfragmentations
# Theoverheadofaddresstranslationinsegmentationishigher
— the main reason why we love paging! — within a page
— you need to provide finer-grained mapping in paging — you may need to handle page faults!
$ Consecutivevirtualmemoryaddressmaynotbeconsecutiveinphysical address if we use demand paging
A. 0 B. 1 C. 2
We haven’t seen pure/true implementation of segmentations for a while, but we still use segmentation fault errors all the time!
Address translation in demand paging
Demand paging
instruction
instruction
each of this is a fix-sized page
0x80000000
0x80008000
Page fault!
Page fault!
Page fault!
Virtual A s Space for Ch m Page fault! u a pple Music
Instructions Data
Instructions Data
Address translation
Processor receives virtual addresses from the running Virtual address space is organized into “pages”
Virtual address
code, main memory uses physical memory addresses
The system references the page table to translate addresses
Each process has its own
page table
The page table
content is maintained by OS
Page table
Physical address
In addition to valid bit and physical page #, the page table may also store
Reference bit Modified bit Permissions
virtual page number
0x 0 0 0 0 B
0x D E A D B
physical page number
page offset
page offset
valid access
permission
Assume that we have 32-bit virtual address space, each page is 4KB, each page table entry is 4 bytes, how big is the page table for a process?
A. 1MB B. 2MB C. 4MB D. 8MB E. 16MB
Size of page table
https://www.pollev.com/hungweitseng close in
Size of page table
Assume that we have 32-bit virtual address space, each page
is 4KB, each page table entry is 4 bytes, how big is the page
table for a process? A. 1MB
D. 8MB E. 16MB
The size of each entry in the page table
Number of entries in the page table
! = 4 ! 1 M = 4 MB What if we have 16 processes?
4MB*16=64MB
— we need a separate page table for each process
Assume that we have 64-bit virtual address space, each page is 4KB, each page table entry is 8 bytes (64-bit addresses), what magnitude in size is the page table for 32 processes?
A. MB — 220 Bytes B. GB—230Bytes C. TB — 240 Bytes D. PB—250Bytes E. EB—260Bytes
Size of page table
https://www.pollev.com/hungweitseng close in
Assume that we have 64-bit virtual address space, each page is 4KB, each page table entry is 8 bytes (64-bit addresses), what magnitude in size is the page table for 32 processes?
A. MB — 220 Bytes
B. GB—230Bytes 8bytes!264 B =23B!264 B =255 B=32PB
Size of page table
C. TB — 240 Bytes 4 KB 212 B
D. PB—250Bytes
32 PB ! 32 = 260B = 1 EB
E. EB—260Bytes
— memory access overhead
Address translation (cont.)
Page tables are too large to be kept on the chip (millions of Instead, the page tables are kept in memory
entries) — space overhead: surpasses cache capacity
— space overhead: can be bigger than physical main memory when address space is large
Smaller page tables
Conventional page table
Virtual Address Space
— must be consecutive in the physical memory
0xFFFFFFFFFFFFFFFF
— like a big segment! — difficult to find a spot
— simply too big to fit in memory if address space is large!
264 B page table entries/leaf nodes 212 B
“Paged” page table
0xFFFFFFFFFFFFFFFF
Heap Virtual Address Space Stack
Break up entries into pages!
Each of these occupies exactly a page
212 B Thesenodesarespreadout,
— 23 B = 29 PTEs per node how to locate them in the memory? Otherwise, you always need to find more
than one consecutive pages — difficult!
These are nodes are not presented
if they are not referenced at all — save space
Allocate page table entry nodes “on demand”
https://en.wikipedia.org/wiki/B-tree#/media/File:B-tree.svg
Break the virtual page number into several pieces
If one piece has N bits, build an 2N-ary tree
Only store the part of the tree that contain valid pages Walk down the tree to translate the virtual address
Hierarchical page table
level 1 index
level 2 index
physical p57age #
Two-level, 4KB, 10 bits index in each level If we are accessing 0x1006000 now...
10 bits 10 bits offset = 12 bits
0000000100 0000000110 000000000000
Page table walking example
0x7fffffffe000
emory page in 0x7fffffffe000
1001010 000000000000
physical page #
Hierarchical Page Table
0xFFFFFFFFFFFFFFFF
Heap Virtual Address Space Stack
"log29 264 B # = "log29252# = 6 levels 212 B
264 B 212 B
These are nodes are not presented astheyarenotreferencedatall.
page table entries/leaf nodes (worst case)
How many levels do we need?
Assume that our sy
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com