Memory Management
Background
• Program must be brought (from disk) into memory and placed
within a process for it to be run
• Main memory and registers are only storage CPU can access
directly
• Memory unit only sees a stream of addresses + read requests,
or address + data and write requests
• Register access in one CPU clock (or less)
• Main memory can take many cycles, causing a stall
• Cache sits between main memory and CPU registers
• Protection of memory required to ensure correct operation
Logical vs. Physical Address Space
Logical address – generated by the CPU; also
referred to as virtual address CPU
Physical address – address seen by the memory
unit
• Logical address space is the set of all logical
addresses generated by a program
• Physical address space is the set of all
physical addresses generated by a program
Base and Limit Registers
• A pair of base and limit registers define the logical address
space
• CPU must check every memory access generated in user
mode to be sure it is between base and limit for that user
Hardware Address Protection with Base and Limit Registers
• OS loads the base & limit reg.
• Privileged instruction
ADDRESS BINDING
The Address Binding refers to the mapping of computer
instructions and data to physical memory locations. Both logical
and physical addresses are used in computer memory. It assigns a
physical memory region to a logical pointer by mapping a
physical address to a logical address known as a virtual address.
There are mainly three types of address binding in the OS.
These are as follows:
[Link] Time Address Binding
[Link] Time Address Binding
[Link] Time or Dynamic Address Binding
Compile Time Address Binding
This binding is done at compilation time by the compiler. In
order to translate a high level language program into
corresponding machine language program, the compiler must
assume where in memory each machine instructions and data
will be placed during the execution.
As the actual program start address in the memory of the
program is not known in advance, the compiler maps all the
machine instructions to some absolute memory addresses
starting from memory location 0.
The loader simply accepts the machine language text and places
it into memory as prescribed by the compiler.
Load time Address Binding
• During the compilation time, a compiler binds the
instructions and symbolic addresses in highlevel
language program to absolute addresses starting usually
from 0000H.
• But however, in any system, the lower portion of the
memory is reserved for operating system and are not
available for user processes.
• The loader must perform the relocation of the program
by loading the instructions and data from new origin
depending the availability of the free space in the
memory.
• Thus, new addresses are assigned at load time.
Execution Time or Dynamic
Address Binding
• For some reasons , an executing program may need to be
relocated from its current locations in memory to new
area.
• For eg: a process is swapped out of memory and brought
back after a long time .
• In such case the memory management unit of OS
performs the necessary relocation.
• The process is moved during its execution time from one
memory segment to another, thus address binding must
be performed dynamically at run time.
Logical and Physical Addresses
in an Operating System
A logical address is generated by CPU while a program is running. Since a logical
address does not physically exists it is also known as a virtual address. This address
is used as a reference by the CPU to access the actual physical memory location.
Memory-Management Unit maps logical address to its corresponding physical
address.
A physical address identifies the physical location of a specific data element in
memory. The user never directly deals with the physical address but can determine
the physical address by its corresponding logical address. The user program
generates the logical address and believes that the program is running in this logical
address space, but the program needs physical memory for its execution, therefore,
the logical address must be mapped to the physical address by the MMU before the
addresses are used. The term physical address space is used for all physical
addresses corresponding to the logical addresses in a logical address space.
MMU as a relocation register
Base register now called relocation register
Page Replacement Algorithms in Operating
Systems
In an operating system that uses paging for memory management, a page replacement
algorithm is needed to decide which page needs to be replaced when a new page comes in.
Page Fault: A page fault happens when a running program accesses a memory page that is
mapped into the virtual address space but not loaded in physical memory. Since actual
physical memory is much smaller than virtual memory, page faults happen. In case of a page
fault, Operating System might have to replace one of the existing pages with the newly
needed page. Different page replacement algorithms suggest different ways to decide which
page to replace. The target for all algorithms is to reduce the number of page faults.
First In First Out (FIFO):
This is the simplest page replacement algorithm. In this algorithm, the
operating system keeps track of all pages in the memory in a queue, the
oldest page is in the front of the queue. When a page needs to be
replaced page in the front of the queue is selected for removal.
• Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3
page frames. Find the number of page faults.
• Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the
empty slots —> 3 Page Faults.
• when 3 comes, it is already in memory so —> 0 Page Faults. Then 5
comes, it is not available in memory so it replaces the oldest page slot i.e 1.
—>1 Page Fault. 6 comes, it is also not available in memory so it replaces
the oldest page slot i.e 3 —>1 Page Fault. Finally, when 3 come it is not
available so it replaces 0 1 page fault.
• Belady’s anomaly proves that it is possible to have more page faults when
increasing the number of page frames while using the First in First Out
(FIFO) page replacement algorithm. For example, if we consider reference
strings 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4, and 3 slots, we get 9 total page faults,
but if we increase slots to 4, we get 10-page faults.
Optimal Page replacement
In this algorithm, pages are replaced which would not be used for the longest
duration of time in the future.
Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page
frame. Find number of page fault.
• Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty
slots —> 4 Page faults
0 is already there so —> 0 Page fault. when 3 came it will take the place
of 7 because it is not used for the longest duration of time in the future.—
>1 Page fault. 0 is already there so —> 0 Page fault. 4 will takes place
of 1 —> 1 Page Fault.
• Now for the further page reference string —> 0 Page fault because they
are already available in the memory.
Optimal page replacement is perfect, but not possible in practice as the
operating system cannot know future requests. The use of Optimal Page
replacement is to set up a benchmark so that other replacement algorithms
can be analyzed against it.
Least Recently Used:
In this algorithm, page will be replaced which is least recently used.
Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4
page frames. Find number of page faults.
•
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots
—> 4 Page faults
0 is already their so —> 0 Page fault. when 3 came it will take the place of
7 because it is least recently used —>1 Page fault
0 is already in memory so —> 0 Page fault.
4 will takes place of 1 —> 1 Page Fault
Now for the further page reference string —> 0 Page fault because they are
already available in the memory.
Most Recently Used (MRU):
In this algorithm, page will be replaced which has been used recently.
Belady’s anomaly can occur in this algorithm.