6-10 Flashcards
What is memory virtualization?
(3)…
- OS virtualizes its physical memory
- OS provides an illusion of memory space per each process
- It is as if each process can access the entire memory space
Memory virtualization benefits:
(3)…
• Ease of use in programming
• Memory efficiency in terms of time and space
• The guarantee of isolation for processes as well as OS
- Protection from errant accesses of other processes
Early OSes:
• Load __ in memory
- Poor utilization and efficiency
only one process
Multiprogramming and Time Sharing: Load multiple processes in memory: (3)... Causes an important protection issue: ...
- Execute one for a short while
- Switch processes between them in memory
- Increase utilization and efficiency;
• Errant memory accesses from other processes
Address Space:
The OS creates an __ of physical memory
• The address space contains all the information about a running process
- program code, heap, stack and etc.
Address Space: Code: (1)... Heap: (1)... Stack: (2)...
1. Code • Where instructions live 2. Heap • Dynamically allocate memory - malloc in C - new in Java 3. Stack • Store return addresses or values • Contain local variables and arguments to functions
Virtual Address:
Every address in a running program is __.
OS translates the __ to __.
virtual;
virtual address;
physical address
—
#include [LTS]stdio.h>
#include [LTS]stdlib.h>
// Compile with: gcc -Og -no-pie -o print_address print_address.c
int main(int argc, char *argv[]){
int x = 3; // allocated on the stack frame of main()
printf(“location of code : %p\n”, (void *) main);
printf(“location of heap : %p\n”, (void *) malloc(1));
printf(“location of stack : %p\n”, (void *) &x);
return x; // so compiler doesn’t optimize x away
}
• The output in 64-bit Linux machine:
9/23/2019 CMPU 335 – Operating Systems 8
location of code : 0x4005c7
location of heap : 0x1623670
location of stack : 0x7fff633fbe54
Memory Virtualization Overview:
(4)…
• Just like the CPU, memory is virtualized
• Every address generated by a user program is a virtual address
• Virtual memory provides the illusion of a large private address space to
programs
- For instructions and data
• The OS, with help from the hardware translates each virtual memory
address to an actual physical address
- Protects and isolates processes from each other
- And from the kernel
Memory Virtualizing with Efficiency and Control:
In memory virtualizing, efficiency and control are attained by __.
• E.g., registers, TLB (Translation Look-aside Buffer)s, page-table
• Control means no process is allowed to access any memory but its own
Address Translation:
Mechanism: __
• Hardware transforms __
• The desired information is actually stored in a __
hardware-based address translation;
a virtual address to a physical address;
physical address
The OS must get involved at key points to set up the hardware
• The OS manages __
• Keeps track of __
memory;
which locations are free and which are in use
Example: Address Translation
void func() int x = 3000; x = x + 3; // this is the line of code we are interested in ...
(3)…
- Load a value from memory
- Increment it by three
- Store the value back into memory
Example: Address Translation
void func() int x = 3000; x = x + 3; // this is the line of code we are interested in
Assembly:
…
128 : movl 0x0(%ebx), %eax ; load 0+ebx into eax
132 : addl $0x03, %eax ; add 3 to eax register
135 : movl %eax, 0x0(%ebx) ; store eax back to mem
• Presume that the address of ‘x’ has been place in ebx register
• Load the value at that address into eax register
• Add 3 to eax register
• Store the value in eax back into memory
—
5 memory references just to add 3 to a number!:
• Fetch instruction at address 128
• Execute this instruction (load from address 15KB)
• Fetch instruction at address 132
• Execute this instruction (no memory reference)
• Fetch the instruction at address 135
• Execute this instruction (store to address 15 KB)
- Base and bounds also called __
* Bounds register also called __
dynamic relocation;
limit register
Dynamic (Hardware base) Relocation:
When a program starts running, the OS decides __.
• Sets the base register accordingly
𝑝ℎ𝑦si𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = __
• Every virtual address must not be greater than __
where in physical memory a process should be loaded;
𝑣𝑖𝑟𝑡𝑢𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 + 𝑏𝑎𝑠e;
bound and negative:
0 ≤ 𝑣𝑖𝑟𝑡𝑢𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 < 𝑏𝑜𝑢𝑛𝑑s
Relocation and Address Translation:
128 : movl 0x0(%ebx), %eax
(2)…
• Fetch instruction at address 128 (virtual address):
32896 = 128 + 32𝐾𝐵(𝑏𝑎𝑠𝑒)
• Execute this instruction
- Load from address 15KB (virtual address)
47𝐾𝐵 = 15𝐾𝐵 + 32𝐾𝐵(𝑏𝑎𝑠𝑒)
Two ways to check Bounds:
(2)…
- Either hold the size of the address space or the physical address of the end of the address space
- Depends on whether you bounds check before or after translation
The OS must take action to implement base-and-bounds approach
• Three critical junctures:
(3)…
• When a process starts running:
- Finding space for address space in physical memory
• When a process is terminated:
- Reclaiming the memory for use
• When context switch occurs:
- Saving and storing the base-and-bounds pair
OS Issues: When a Process Starts Running
- The OS must find __
- free list : __
a room for a new address space;
A list of the range of the physical memory which are not in use
OS Issues: When a Process Is Terminated
• The OS must __
put the memory back on the free list
OS Issues: When Context Switch Occurs:
• The OS must __
- In __
save and restore the base-and-bounds pair;
process structure or process control block (PCB)
Address Translation Overview:
- Extend limited direct execution with address translation
(1) … - Hardware support is necessary
(2) … - Base and bounds is efficient and offers protection
(2) …
- Extend limited direct execution with address translation
• Can control each and every memory access from a process - Hardware support is necessary
• Process has no idea memory references are being translated
• Part of the memory management unit (MMU) of a processor - Base and bounds is efficient and offers protection
• Suffers from internal fragmentation due to fixed-sized slots
• This leads us to segmentation, a generalization of base and bounds
Inefficiency of the Base and Bound Approach:
(3)…
- Big chunk of “free” space
- “free” space takes up physical memory
- Hard to run when an address space does not fit into physical memory
Segment is just a __.
contiguous portion of the address space of a particular length
• Logically-different segments: code, stack, heap
Each segment can be placed in __
• __ exist per each segment
different parts of physical memory;
Base and bounds
Address Translation on Segmentation:
𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = __
• The offset of virtual address 100 is __
- The code segment starts at __
𝑜𝑓𝑓𝑠𝑒𝑡 + 𝑏𝑎𝑠e;
100;
virtual address 0 in address space
The offset of virtual address 4200 is (4200 – 4096) = 104
• The heap segment starts at virtual address __ in address space
4096
Referring to Segment:
Explicit approach:
__
• Divide the address space into segments based on the top few bits of virtual address
Segmentation Fault or Violation:
…
• If an illegal address such as 7KB which is beyond the end of heap is referenced, the OS occurs segmentation fault
- The hardware detects that address is out of bounds
Referring to Stack Segment:
• Stack grows backward • Extra hardware support is needed - The hardware checks which way the segment grows - 1 positive direction - 0 negative direction
• To calculate negative offset
- Get virtual address segment offset (offset bits from addr.)
- Subtract offset from maximum segment size to get negative offset
- Subtract negative offset from base to get physical address
Support for Sharing:
Segments can be shared between __
(2)…
address spaces
• Code sharing is still in use in systems today
• With extra hardware support
Extra hardware support adds __
• A few more bits per segment to indicate __
protection bits;
permissions of read, write, and execute
Coarse-Grained means __
• e.g., __
segmentation in a small number;
code, heap, stack
Fine-Grained segmentation allows more __.
(2)…
• To support many segments, hardware support with a segment table (kept in memory) is required
• OS could better learn which segments are in use to utilize memory efficiently
External Fragmentation:
__.
(2)…
little holes of free space in physical memory that make it difficult to allocate new segments
• There are 24KB free, but not in one contiguous segment
• The OS cannot satisfy the 20KB request
Compaction:
__.
(3)…
rearranging the exiting segments in physical memory • Compaction is costly - Stop running process - Copy data to somewhere - Change segment register value
Segmentation Summary
(5)…
• Allows for dynamic relocation
• Better support for large address spaces
- Avoids internal fragmentation
• Segmentation is fast
- Well suited to hardware
- Base and bound registers for each segment
- Optional protection bits for each segment
• External fragmentation is still a major concern
• Still not flexible enough
- E.g., large but sparsely-used heap
Concept of Paging:
Paging…
splits up the virtual address space into fixed-sized units called pages
• Compare to segmentation: variable size of logical segments(code, stack, heap, etc.)
Concept of Paging: Physical memory is also split into some number of pages called a __.
• Virtual pages and page frames are __ size
page frame;
all the same
Paging Advantages:
(2)…
- Flexibility
• Supports the abstraction of address effectively
• No assumptions on how the heap and stack are used - Simplicity
• The page in the address space and the page frame are the same size
• Ease of free-space management
• Easy to allocate and keep a free list
Paging Advantages:
(2)…
- Flexibility
• Supports the abstraction of address effectively
• No assumptions on how the heap and stack are used - Simplicity
• The page in the address space and the page frame are the same size
• Ease of free-space management
• Easy to allocate and keep a free list
Paging Example:
(3)…
- 128-byte physical memory with 16 bytes page frames
- 64-byte address space with 16 bytes pages
- Page table maps virtual pages to physical pages - Per process data structure that maps virtual pages to physical pages
Address Translation:
Two components in the virtual address:
(2)…
- VPN: virtual page number
* Offset: offset within the page
What Is In The Page Table?:
The page table is __.
• Simplest form: __.
just a data structure that is used to map the virtual address to physical address;
a linear page table, an array
What Is In The Page Table?:
The OS indexes the array by __ and looks up the __.
In addition to the Physical Frame Number, each page table entry has some __.
VPN;
page table entry;
status flags
Common Page Table Entry Flags:
(5)…
- Valid Bit: Indicating whether the particular translation is valid
- Protection Bits: Indicating whether the page could be read from, written to, or executed from
- Present Bit: Indicating whether this page is in physical memory or on disk (swapped out)
- Dirty Bit: Indicating whether the page has been modified since it was brought into memory
- Reference Bit (Accessed Bit): Indicating that a page has been accessed
Valid Bit
Indicating whether the particular translation is valid
Protection Bits
Indicating whether the page could be read from, written to, or executed from
Present Bit
Indicating whether this page is in physical memory or on disk (swapped out)
Dirty Bit
Indicating whether the page has been modified since it was brought into memory
Reference Bit (Accessed Bit)
Indicating that a page has been accessed
Example: x86 Page Table Entry • P: \_\_ • R/W: \_\_ • U/S: \_\_ • A: \_\_ • D: \_\_ • G, PAT, PCD, PWT: \_\_ • PFN: \_\_
- P: present
- R/W: read/write bit
- U/S: supervisor
- A: accessed bit
- D: dirty bit
- G, PAT, PCD, PWT: Used for caching
- PFN: the page frame number
A Memory Trace:
• Example: A Simple Memory Access
int array[1000];
…
for (i = 0; i < 1000; i++)
array[i] = 0;
• Compile and execute:
gcc –o array array.c –Wall –o
./array
• Resulting Assembly code:
…
# i in %eax # array in %edi 0x1024 movl $0x0,(%edi,%eax,4) 0x1028 incl %eax 0x102c cmpl $1000,%eax 0x1030 jne 0x1024
Paging: Too Slow:
• To find a location of the desired PTE, the __ is needed
• For every memory reference, paging requires the OS to perform __
• How do we speed up memory access?
- __
• Next up: Introducing the TLB (Translation Lookaside Buffer)
- A purpose-built cache for page table lookups
starting location of the page table;
one extra memory reference;
Caching to the rescue!
Faster Translations:
Paging can lead to high performance overheads:
…
• Every memory access needs to read an entry in the page table
- Stored in memory!
- Doubles the number of memory accesses in the system!
• Need to make page table lookups go faster. What techniques have we seen before to speed up memory access?
(2)…
- Caching to the rescue!
2. Smaller and faster memory that holds a portion of the page table for a process
Making page table access is so important to overall system performance that a dedicated purpose-built cache is used:
(2)…
- Called Translation Lookaside Buffer (TLB) for historic reasons
- A better name would be address-translation cache
TLB:
(2)…
- Part of the chip’s memory-management unit(MMU)
* A hardware cache of popular virtual-to-physical address translation
Accessing An Array:
(3)…
• 10 4-byte integers starting at virtual address 100 • 8-bit virtual address space • 16 byte pages - 4-bits offset - 4-bits VPN
Temporal Locality
An instruction or data item that has been recently accessed will likely be reaccessed soon in the future
Spatial Locality
If a program accesses memory at address x, it will likely soon access memory near x
Who Handles The TLB Miss?
(2)…
- Hardware handles the TLB miss entirely (e.g., X86)
2. OS handles the TLB miss (e.g., ARM)
