Memory Flashcards
Physical Memory AKA
RAM
Memory needs to be
subdivided
Memory hierarchy
Registers, cache, main memory, solid state disk, magnetic disk
Memory management is an _ task under _
optimization task under constraints
Fixed-partition Allocation divides memory into
Fixed-size partitions
Fixed-partition allocation, each partition contains
exactly one process
In fixed-partition allocation, the degree of multiprogramming is bound by
the number of partitions
In fixed-partition allocation, what happens when a process terminates
The partition becomes available for other processes
Internal Fragmentation
Allocated memory may be slightly larger than requested memory
internal fragmentation size difference
is memory internal to a partition but not being used
Variable-partition scheme (dynamic) process
When a process arrives, search for a hole large enough for this process
Variable-partition scheme (dynamic) hole definition
Block of available memory; holes of various size are scattered throughout memory
In Variable-partition scheme (dynamic), how much memory is allocated
Only as much memory as needed
in Variable-partition scheme (dynamic), what does the OS maintain information about?
Allocated Partitions
Free partitions (hole)
External Fragmentation
Total memory space exists to satisfy a request, but it is not contiguous
What could fixed-partition allocation lead to?
Internal Fragmentation
What could Variable-partition scheme (dynamic) lead to?
External Fragmentation
How to reduce External Fragmentation?
Compaction
External Fragmentation 50% rule
number of holes = .5 * number of occupied blocks
Compaction
Shuffle memory contents to place all free memory together in one large block
Compaction is only possible when? and at done when?
It is only possible if relocation is dynamic and is done at execution time
First-fit
Allocate the first hole that is big enough
Best-fit
Allocate the smallest hold that is big enough
Best fit must do what?
Search entire list, unless ordered by size
What will best-fit produce?
The smallest leftover hole
Worst-fit
Allocate the largest whole
Next-fit
Starts each search at the point of the last allocation (round robin)
What must worst-fit do?
Search the entire list
Worst-fit produces
The largest leftover hole
Which dynamic storage-allocation is fastest?
First-fit
Physical memory (RAM)
Hardware Structure consisting of a linear sequence of words
Word
Fixed size unit of data, usually 4 bytes
Logical Address Space
An abstraction of physical memory, consisting of a sequence of imaginary memory locations [0: m-1]
Source Module
A program or program component written in a symbolic language like C or assembly, that must be translated by a compiler or assembler into executable machine code
Source Module to object module
Translation
Object module(s) to Load Module
Linking
Object Module
The Machine language output of a compiler or assembler from a source module.
Load Module
A program or combination of programs in a form ready to be loaded into main memory and executed
Load Module on disk to Load module in memory
Loading
What are system libraries
collections of precompiled and reusable code that provide foundational functionality to the operating system and applications
Addresses in a source program are usually
Symbolic
What does a compiler do to these symbolic addresses
A compiler binds these symbolic addresses to relocatable addresses
What does the linkage editor or loader do to the relocatable addresses
It binds the relocatable addresses to absolute addresses
What does each binding do
It maps from one address space to another
Source program address example
int count;
Relocatable address example
100 bytes from the beginning of this module
Each process has
A separate memory space
Which two registers provide address protection between processes
Base Register
Limit Register
Absolute address example
74014
Memory-Management Unit (MMU)
Hardware Device that maps logical to physical address
Base Register
Smallest legal address space
Limit Register
Size of the legal range
In MMU, what is special about the value in the relocation register (base) register?
It is added to every address generated by a user process at the time it is sent to memory
Which program deals with logical addresses?
User Program
Does the user program ever see the real physical address?
No
What does the CPU hardware compare?
Every address generated in user mode with the registers
What will an attempt to access other processes’ memory do?
It will be trapped and cause a fatal error
Logical Address
An integer in the range [0: m-1] that identifies a word in a logical address space
What do the compiler/assembler and linker assume the logical address space start with at load time?
Address 0
Relocation
The act of moving a program component from one address space to another
Static relocation
Binds all logical addresses to physical addresses prior to execution
Dynamic relocation
Postpones the binding of a logical address to a physical address until the addressed item is accessed during execution
Segmentation
Memory-management scheme that supports user view of memory
A program is a collection of
segments
two tuple in each logical address
<segment-number, offset>
Segment table
Maps two-dimensional physical addresses
Each table entry in segment table has
Base - contains the starting physical address where the segments reside in memory
limit - specifies the length of the segment
Segment-table base register (STBR)
points to the segment table’s location in memory
Segment-table length register (STLR)
indicates the length (limit) of the segment
Sharing of segments
Share code/editor segment but have different data segment
Can physical address space of a process be noncontiguous?
Yes
[physical] frames
divide physical memory into fixed-size blocks
[logical] pages
Divide logical memory into blocks of same size
How to run a program of size n pages?
find n free frames and load program
Paging address translation is dividing address generated by cpu into
Page number (p)
Page offset (d)
Page number (p)
Used as an index into a page table which contains base address of each page in physical memory
Page offset (d)
Combined with base address to define the physical memory address that is sent to the memory unit
Paging
Noncontiguous allocation of memory
Shared pages – shared code
One copy of read-only (reentrant) code shared among processes
Must appear in the same location in the logical address space of all processes
Shared pages – private code and data
Each process keeps a separate copy of the code and data
Can appear anywhere in the logical address space
Page table is kept in
main memory
Page table base register (PTBR) points to
page table
Page-table length register (PLTR) indicates
size of the page table
What two memory accesses does the paging scheme in every data/instruction access require?
One for page table and one for data/instruction
How can the two memory access problem be solved?
Fast lookup hardware cache called associative memory or translation lookaside buffers (TLBs)
How big is TLB?
64 to 1024 entries
What happens on TLB miss
Value is loaded into the TLB for faster access next time
How to solve TLB problem when switching processes?
Need to flush at every context switch
Or store address-space identifiers in each TLB entry to uniquely identify each process and provide address-space protection for that process
How much faster is TLB than memory access
An order of magnitude
Hierarchical Page Tables
Break up the logical address space into multiple page tables
Two-level paging: logical address is divided into
Page number
Page offset
Two-level paging: Page number is divided into
Page table index (within the outer page directory)
Page index (within the inner page table)
Intel IA-32 Architecture support both
Segmentation and segmentation with paging
Who generates logical address?
CPU
Where is selector given to?
Segmentation unit
What does segmentation unit produce?
Linear Address
What is linear address given to?
Paging unit
What does paging unit produce?
Physical Address in main memory
What can be the size of each page
anything of the power of 2
