CMPT 300 Operating Systems I (D100)
Main Memory – Part 1
Tianzheng Wang
SFU Computing Science
* Some materials based on those from Janice Regan, Keval Vora and Mohamed Hefeeda, Operating Systems 9th/10th ed, Operating Systems: Three Easy Pieces.
Simon Fraser University
Recap: Memory Hierarchy
• CPU directly accesses CPU caches, main memory and persistent memory
• Programs must be loaded to main memory for execution
CMPT 300 2
h
ig
h
er
lo
w
er
Cost per bit &
Performance
sm
al
le
r
Capacity
la
rg
er
Volatile SRAM
L1 Cache
Registers
L2 Cache
L3 Cache
Main memory
Persistent
memory
Flash/disk
CPU
Non-volatile
Volatile DRAM
~4 cycles
~10 cycles
~60 cycles
20-50ns
50-100ns
us, ms…
1 cycle
Simon Fraser University
Systems in the Early Days
Everything physical
• OS starts at physical address 0
• Occupies the first N (e.g., 64K) bytes
• Application uses the remaining memory space
• Run one user program at a time
Not efficient!
• Low resource utilization
CMPT 300 3
Simon Fraser University
Multiprogramming and Time Sharing
• Keep multiple processes in memory
• Switch between processes for interactivity
Protection/isolation between processes needed
Solution: address space
CMPT 300 4
Simon Fraser University
Address Space
Easy-to-use abstraction of physical memory
• Provide an illusion that each process uses the whole memory space
• Provide isolation between processes
• Efficiently use memory space
• Each process has its own address space
• Starts from 0
• Ends at max memory possible
• E.g., 2^32 for 32-bit machines,2^64 for 64-bit machines
➔ “Virtual address”
CMPT 300 5
Simon Fraser University
Address Translation
CMPT 300 6
0
Max
Physical memory
Process 1
Process 2
Process 3
0
Max
0
Max
0
Max
Simon Fraser University
Address Space
7CMPT 300
int global = 0;
int main (int arg)
{
float local;
char *ptr;
ptr = malloc(100);
local = 0;
local += 10*5;
printf(“%x\n”, ptr);
printf(“%x at \n”, &ptr);
printf(“%x at \n”, &local);
printf(“%x at \n”, &global);
return 0;
}
Dynamically
allocated
Global variables
Program code
Local variables
Return address
All addresses used here are virtual (logical) addresses
Applications have no direct access to memory using physical addresses
Simon Fraser University
First Attempt: Base and Limit Registers
A base and a limit register define the logical address space
• Physical address = Base + Virtual Address
• Base: starting address in memory (physical)
• Virtual address: offset into the address space
• Supported by memory management unit (MMU)
• Privileged instructions for modifying these registers
CMPT 300 8
Simon Fraser University
First Attempt: Base and Limit Registers
A base and a limit register define the logical address space
• Physical address = Base + Virtual Address
• Base: starting address in memory (physical)
• Virtual address: offset into the address space
CMPT 300 9
Need OS support
(handle out-of-bound)
Simon Fraser University
First Attempt: Base and Limit Registers
A base and a limit register define the logical address space
• Physical address = Base + Virtual Address
Limitations:
• Logical address space cannot be larger than physical
address space
• I.e., entire process fits in memory
• Logical address space must be stored contiguously
• May waste space
• Space between heap and stack
Better alternative: segmentation
CMPT 300 10
Simon Fraser University
Segmentation: Generalized Base+Limit
Programmer’s view of memory:
• A program is a collection of segments
• A segment is a logical unit such as:
• Main program
• Functions, procedures
• Method
• Object
• Local variables, global variables
• Stack
• Symbol tables
• Arrays
Segmentation: Have a base + limit pair per logical segment
CMPT 300 11
Simon Fraser University
Segmentation: Generalized Base+Limit
Have one base + limit pair per logical segment
CMPT 300 12
1
3
2
4
user space
1
4
2
3
physical memory space
<0, 16KB>
<16KB, 16KB>
<64KB, 10KB>
<74KB, 32KB>
LimitBase
Simon Fraser University
Segmentation Architecture
• Logical address has the form:
• Segment table
• Maps logical address to physical address
• Each entry has
• Base: starting physical address of segment
• Limit: length of segment
CMPT 300 13
Simon Fraser University
Segmentation Hardware
CMPT 300 14
s: segment # (high-order bits)
d: offset into the segment
Example:
Simon Fraser University
Segmentation Example
CMPT 300 15
Simon Fraser University
Issues in Segmentation
Issue 1: Need to save and restore segment registers upon context switch
Issue 2: Managing free spaces:
• Segments vary in length
• OS needs to find free space in memory for new address space
• This can lead to external fragmentation
• Physical memory becomes full of small holes of free spaces
• Hard to allocate new segments or grow existing ones
• Holes have different sizes and scattered in the memory
• Need space management solutions
CMPT 300 16
Which hole to choose
for a process?
Simon Fraser University
Summary
• Address space
• Easy-to-use abstraction of memory
• Gives processes the illusion that it owns the entire system
• Provides isolation and protection between processes
• Basic approach: base and limit registers
• Base: starting physical address
• Limit: size of segment
• Need privileged instructions to modify base and limit registers
• Various limitations
• Segmentation: generalized base+limit registers approach
• One pair of base+limit registers per segment
• Main issue: external fragmentation
CMPT 300 17