Memory Management
Introduction
A program resided on a disk as a binary executable file (.exe). to be executed the program must
be loaded into memory and placed within a process for it to be run.
JOB QUEUE Ready QUEUE Memory
Processes in JOB QUEUE are put in Read queue to be loaded in memory .
Binding Instructions and data to memory
Binding instructions and data to memory addresses can happen at three stages
Compile-Time: this is absolute code any changes to code the whole program must be
recompiled .
Load-Time : happen when loading module or system library .compiler must generate
relocatable code.
Execution Time : if the process can be moved during its execution from one memory
segment to another , example creating object of class or dynamically load modules or system
library . And its need hardware support such as (base and limit registers ) .
Processing User program (application )
source code Assembler /compiler Object file
Compile Time
Object module 2
Linker RunTime library
Object module 3
Load-Time
Dynamic loaded
Memory
system library
RunTime (execution time)
Types of address space
Physical Address : address seen by the memory only .
Logical Address : address generated by the CPU ,also referred to as virtual address (not real
address ) .
Mapping Virtual address to physical address
MMU is hardware device that maps virtual to physical address in runtime mapping .
How it works ?
It has value in the relocation /base register that is added to every address generated by a user
process at the time is sent to memory .
MMU mapping Base Register + logical Address = physical address
Note : MS-DOS used 4 relocation registers
Swapping
A process is swapped temporary out of memory to secondary storage like HDD , and then
brought back into memory to continue execution .
Swapping requires :
Fast secondary storage
Large secondary storage
Must provide direct access
Swapping is used for : priority -based scheduling algorithms : where lower-priority process is
swapped out and higher-priority is swapped in Or the memory is full .
Note : Transfer time it takes more time than swapping .
Contiguous memory allocation
Operating system
User Processes (applications)
Memory
Single – partition allocation
All processes share same memory space , and its has two registers .
Relocating-register : is used to protect user processes from each other , and from changing the
operating system code and data.
And It has value of smallest physical address .
Limit register : contains range of logical addresses – each logical address must be less than the
limit register .
CPU logical address Logical Yes
address < +
limit relocating
register
No
Error
Mutliple-partition
Each process has its own partition .
Hole : block of available memory , and they vary in size are scattered throughout memory .
The hole must be greater or equal the process size .
OS maintains information about:
Allocated partitions
Free partitions (hole)
Example :
Process Memory Time
1 600 10
2 1000 5
3 300 20
4 700 8
5 500 15
OS
OS 400
P1
P4
P3
P1 400
1000
1000
P2
2000 1700
P3 2300
2560 2560
We cant insert partition of the memory in hole because its contiguous .
Memory allocation strategies
First -fit : allocate the first hole that is big enough .
Best-fit : allocate the smallest hole that is big enough , must search entire list .
Best-fit = Ascending order + First-fit .
Worst-fit : allocate the largest hole , must also search the entire list .
Worst-fit = descending order + First-fit .
Note : fist-fit is faster
First-fit + best-fit better storage utilization
Fragmentation
When processes is swapped out of memory , the pieces free memory are scattered into large
number of small holes the problems are called
External fragmentation
Total memory space exists to satisfy a request , but it is not contiguous .
Solution :External fragmentation is solved by Compaction , paging , Segmenation
Compaction : is possible only if relocation is dynamic and done in execute time. And its very
expensive .
Algorithm : move processes location to make all the smalls holes contiguous .
Paging: make address space of a process non-contagious , thus process is allocated physical
memory whenever it is available .
Frames : divide the physical memory into fixed-size blocks
Pages : divide logical memory into blocks of same size called page .
FrameSize = page size
OS maintains :
Keep track of all free frames
To run program of size n pages , need to find n free frames
Set up a page table to translate logical to physical address
Logical address Page number
Page offset
Page 0 Pnumber Frame Number Frame 1
1 1
2 2 Frame 2
Page 1
Page number : index to page table
Page offset : combined with base address to define physical memory address
Mapping Logicalphysical in paging
To map we need :
page size
memory size
page table
Algorithm :
1) convert page size and memory size to 2 power n
2) power of memory size – power of page size to divide address to page number and
offset .
3) convert logical to binary
4) page number section points to the frame using page table
5) physical address = frame * framSize + offset
example
page size = 4-bytes Page number frame number
memory size = 32-bytes 1 5
2 6
3 1
4 2
convert logical address 13 physical address
1) memory size = 25 and page size = 22
2) 5 -2 = number of page number digits
3) Convert logical address to binary = 13 =
0 1 1 0 1
Page number = 3 frame =2
4) Physical address = 2*4+1 = 9
Advantages of paging
There is no external fragmentation
Internal fragmentation is minimized (on average ½ frame waste )
Small frames reduce internal fragmentation , but increase the size of page table
Structure of page table
Simplest case
each page has register .
advantages : very fast ( fastest case)
limitation : high cost because registers is expensive
it works very well when the page table is small
Case #2
One Page table register (PTBR) points to the page table for that process , PTBR changed by the
OS whenever a process is dispatched , or context-switching
Note : every access now requires 2 memory access
1) One access to get the page table entry
2) One more to get the data/instruction stored
Case #3 Translation look -aside buffer (associative register)
Reduce case #2 to single memory access
Hit -ratio : pages that contains register
Miss -ratio : pages that doesn’t contains register
Miss -ratio = 100% - Hit -ratio
Example : if we have 80% hit -ratio ,20% miss -ratio
If the time to search page that contains assosicative register = 20 ns
And to access memory =100 ns
EAT (effective Access Time ) : (0.8 * (100+20)) + (0.2*(200+20)) = 140 ns =EAT
Note : when hit-ratio increase the EAT decrease
Memory protection
Associating protection bit with each frame in page table
Valid -bit : indicate that the page is in the process logical address space . and is indicated by
“V”
Invalid-bit : indicate that the page is not in the process logical address space . and its
indicated by “I”.
Multilevel paging
Was used to solve the problem when the page table size is very large and cant be stored in
main memory . by paging the page table .
Logical address Page number outer
Page number inner
Page offset
Shard pages
Pages can be shared among processes, not all pages can be shared they must be
“ Reentrant code “ only read
ED1 3
3
Data1 4
4
Process A Process A page table
Main memory
ED1 3
Data2 4
Process B page table
Process B
Example : if system supports 40 users , each one executes a text editor .
If the text editor consist of 150k of code and 50k data.
If pages not shared
= 40*200= 8000k
If code is reentrant “shared”
40*50k + 150K = 2150 K
Segmentation
Is similar to paging in partition the process , except in segmentation partitioning is based on
user’s view of memory ( each partition size is different ) .
Stack Segment Number Limit Base
0 1000 1400
1 400 6300
SQRT
Segment table
Print
Process A
Limit : is the size of the segment
Base : starting address of the segment
Mapping logical to physical address
Segment Number Limit Base
0 600 219
1 400 6300
Segment table
Convert 0430 to physical address ?
Segment 0 limit = 600 , 430 < 600 true , then add 430 to base = 430+219=649
Internal fragmentation
Allocated memory may be slightly larger than requested memory , so the process takes the
entire hole .
Virtual – memory
Technique that allows to execute process that may not be completed in memory
Only part of the program needs to be in memory for execution
Virtual memory is much larger than physical memory
Virtual memory is implemented by:
Demand paging
Demand segmentation
Demand paging
How it works? Bring a page into memory only when it is needed
Advantages :
Less I/O needed
Less memory needed
Faster response
More users
Difference between paging and demand paging ?
Demand Paging : is similar to paging but there is swapping .
Note : when brining page from secondary storage to memory , and there is no free frame the
OS make swap in -out .
Page fault when brining page from secondary storage to memory . and set the invalid -valid
bit
Page fault steps (handling) :
1) If there is ever a reference to page , the OS will bring the Page from HDD to Memory
2) OS look at the page table to decide :
If invalid reference abort
Or its is not in memory
3) Get empty free frame
4) If memory is not full , swap page into memory
5) Reset table , vaild bit = 1
6) Execute
What happen in page fault when there is no free frame ?
Page replacement algorithm . algorithm must result in minimum number of page faults
Page replacement algorithm
1) Find the location of the desired page on disk
2) Find free Frame :
a) If there is free frame use it
b) If there is no free frame , use a page replacement algorithm to select victim frame .
3) Put the page into the new frame
4) Update the page table and frame table
5) Restart process to execute instructions
When memory size increases the page fault numbers become lower .
