Unit 3

Memory
Management
Background
• Memory consists of a large array of bytes, each with its own
address. The CPU fetches instructions from memory.
• After the instruction has been executed on the operands,
results may be stored back in memory.
Basic Hardware for Memory Management

• Main memory and the registers built into the processor itself
are the only general-purpose storage that the CPU can access
directly.
• Each process has a separate memory space.
• Memory space protects the processes from each other
• Protection by using two registers, a base and a limit registers
• The base register holds the smallest legal physical memory
address; the limit register specifies the size of the range.
• For example, if the base register holds 300040 and the limit
register is 120900, then the program can access all addresses
from 300040 to 420939 .
• Protection of memory space is accomplished by having the
CPU hardware
• Any attempt by a program executing in user mode to access
operating-system memory or other users’ memory results in a
trap to the operating system, which treats the attempt as a
fatal error
Address Binding

• The Association of program instruction and data to the actual

physical memory locations is called the Address Binding.
• A program resides on a disk must be brought into memory
• As the process is executed, it accesses instructions and data
from memory.
• When the process terminates, and its memory space is
declared available.
Types of Address Binding

• Compile Time
• Load Time
• Execution Time or Dynamic
Compile time

• if you know that a user process will reside starting at location

R, then the generated compiler code will start at that location
i.e. absolute code can be generated.
• If, at some later time, the starting location changes, then it
will be necessary to recompile this code.
• The MS-DOS .COM-format programs are bound at compile
time.
Load time

• Compiler must generate relocatable code

• In this case, final binding is delayed until load time.
• If the starting address changes, we need only reload the user
code
Execution time

• If the process can be moved during its execution from one

memory segment to another, then binding must be delayed
until run time.
• Special hardware must be available for this scheme to work
• Most general-purpose operating systems use this method.
Logical Versus Physical Address Space

• An address generated by the CPU is commonly referred to as

a logical address
• An address seen by the memory unit is commonly referred to
as a physical address.
• The compile-time and load-time address-binding methods
generate identical logical and physical addresses.
• the execution-time address-binding scheme results in
differing logical and physical addresses.
• In this case, we usually refer to the logical address as a virtual
address.
• The set of all logical addresses generated by a program is a
logical address space.
• The set of all physical addresses corresponding to these
logical addresses is a physical address space.
• In the execution-time address-binding scheme, the logical and
physical address spaces differ.
• The run-time mapping from virtual to physical addresses is
done by a hardware device called the memory-management
unit (MMU).
• The base register is now called a relocation register. The value
in the relocation register is added to every address generated
by a user process
• For example, if the base is at 14000, an access to location 346
is mapped to location 14346.
Dynamic Loading

• To obtain better memory-space utilization, we can use

dynamic loading.
• With dynamic loading, a routine is not loaded until it is called.
• All routines are kept on disk in a relocatable load format. The
main program is loaded into memory and is executed.
• When a routine needs to call another routine, the calling
routine first checks to see whether the other routine has been
loaded.
• If it has not, the relocatable linking loader is called to load the
routine into memory
Swapping

• A process must be in memory to be executed.

• A process, however, can be swapped temporarily out of
memory to a backing store and then brought back into
memory for continued execution
• Swapping makes it possible for the total physical address
space of all processes to exceed the real physical memory of
the system, thus increasing the degree of multiprogramming
in a system.
Contiguous Memory Allocation

• The main memory must accommodate both the operating

system and the user processes.
• The memory is usually divided into two partitions:
• One for the operating system and one for the user processes.
• Therefore need to consider how to allocate available memory
to the processes
• In contiguous memory allocation, each process is contained
in a single section of memory
Memory Protection
• Before discussing memory allocation, we must discuss the
issue of memory protection.
• Each logical address must be within the range specified by the
limit register.
• The MMU maps the logical address by adding the value in the
relocation register.
• This mapped address is sent to memory
Memory Allocation

• One of the simplest methods for allocating memory is to

divide memory into several fixed-sized partitions.
• Each partition may contain exactly one process.
• In this partition method, when a partition is free, a process is
selected from the input queue and is loaded into the free
partition.
• When the process terminates, the partition becomes available
for another process.
• In the variable-partition scheme, the operating system keeps
a table indicating which parts of memory are available and
which are occupied.
• Initially, all memory is available for user processes and is
considered one large block of available memory, a hole.
• the memory blocks available comprise a set of holes of
various sizes
• When a process arrives and needs memory, the system
searches the set for a hole that is large enough for this
process.
• If the hole is too large, it is split into two parts.
• If the new hole is adjacent to other holes, these adjacent
holes are merged to form one larger hole.
• There are many solutions to this problem.
• The first-fit, best-fit, and worst-fit strategies are the ones
most commonly used to select a free hole from the set of
available holes.
• First fit. Allocate the first hole that is big enough.
• Best fit. Allocate the smallest hole that is big enough.
• Worst fit. Allocate the largest hole.
Fragmentation

• Fragmentation is a problem in operating system when the

processes are loaded and removed from memory, the free
memory space is broken into little pieces.
• These small blocks cannot be allotted to new process,
resulting in low memory use.
• Types of fragmentation
– Internal
– External
Internal fragmentation
• Suppose a process P of 3MB size arrives, and it is given a 4MB
memory block. As a result, the 1MB free space in this block
stays unused, and it can't be used for the allocation of
memory to another process. It is called internal
fragmentation.
External fragmentation
• External fragmentation exists when there is enough total
memory space to satisfy a request but the available spaces
are not contiguous.
• Example: Consider the following memory status.
• Process P of size 45kb arrives. You can see that there is
sufficient space (50 KB) to run a process (need 45KB), but the
memory is not contiguous.
• One solution to the problem of external fragmentation is
compaction, by combining all free memory into a single large
block.
• The larger memory block is used to allocate space based on
the requirements of the new processes.
• This method is also known as defragmentation.
Segmentation
• Segmentation is a memory management scheme that
supports user view of memory.
• A logical address space is a collection of segments.
• A segment is a logical unit such as main program, procedure,
function etc.
• Each segment has a name and a length
• The addresses specify both the segment name and the offset
within the segment.
• Segments are numbered and are referred to by a segment
number, rather than by a segment name.
• Thus, a logical address consists of <segment-number, offset>
Segmentation Hardware/Architecture
• Each entry in the segment table has a segment base and a
segment limit
• The segment base contains the starting physical address
• The segment limit specifies the length of the segment
• A logical address consists of two parts: a segment number, s,
and an offset into that segment, d
• The segment number is used as an index to the segment table
• The offset d of the logical address must be between 0 and the
segment limit. If not, addressing error sent to the operating
system
• When an offset is legal, it is added to the segment base to
produce the address in physical memory
Paging

• Paging involves breaking physical memory into fixed-sized

blocks called frames and breaking logical memory into blocks
of the same size called pages.
• When a process is to be executed, its pages are loaded into
any available memory frames from the backing store.
• The backing store also divided into fixed-sized blocks that are
the same size as the frames
Paging hardware
• Every address generated by the CPU is divided into two parts:
a page number (p) and a page offset (d)
• The page number is used as an index into a page table
• The page table contains the base address of each page in
physical memory.
• This base address is combined with the page offset to define
the physical memory address
• The page size is defined by the hardware
• The size of a page is a power of 2, varying between 512 bytes
and 1 GB per page, depending on the computer architecture
• When a process arrives in the system to be executed, its size,
expressed in pages
• Each page of the process needs one frame
• Thus, if the process requires n pages, at least n frames must
be available in memory
• Operating system is managing physical memory, it must be
aware of the allocation details of physical memory— which
frames are allocated, which frames are available, how many
total frames there are, and so on.
• This information is generally kept in a data structure called a
frame table.