Memory Management

Part -1

Prachi Pandey
C-DAC Bangalore
prachip@cdac.in

Prachi Pandey, C-DAC Bangalore

 Basics of computer memory
 Need for Memory Management
 Memory hierarchy
 Techniques: Memory Allocation and Address Translation
 Memory Allocation
 Continuous/Contiguous Allocation
o Fixed/Static Partitioning
o Variable/Dynamic Partitioning
o Internal and External Fragmentation, Compaction
o Memory Allocation Techniques: First Fit, Best Fit, Worst Fit

Prachi Pandey, C-DAC Bangalore

 Basic unit of memory is bit.
 A bit is a single unit of digital information and is represented
either as 0 or a 1.
 Everything in a computer’s memory takes the form of bits i.e.
0’s and 1’s.
 Files and programs consists of millions of these bits.
 These are all processed in the CPU or central processing unit.
 CPU acts as the computer’s brain.

Prachi Pandey, C-DAC Bangalore

Prachi Pandey, C-DAC Bangalore
Prachi Pandey, C-DAC Bangalore
 As the number of bits to be processed grows exponentially, the
need for memory management becomes essential.
 The following factors provide the basis of memory management:
◦ Size – More the better
◦ Cost – Less the better
◦ Speed – More the better
 If we try to increase the size, the speed of access to data will
decrease.
 We need to find an optimal solution which will provide the
desired results.
 Memory management is one of the most important features of the
operating system because it affects the execution time of process
directly

Prachi Pandey, C-DAC Bangalore

 Program must be brought (from disk) into memory and
placed within a process for it to be run
 Main memory and registers are the only storage CPU
can access directly
 Memory unit only sees a stream of:
◦ addresses + read requests, or
◦ address + data and write requests
 Register access is done 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
 Address Space:

Address: 2k bytes

k bits

 What is 210 bytes (where a byte is abbreviated as “B”)?

◦ 210 B = 1024B = 1 KB (for memory, 1K = 1024, not 1000)
 How many bits to address each byte of 4KB page?
◦ 4KB = 4×1KB = 4× 210= 212 12 bits (or log2 4)
 How much memory can be addressed with 20 bits? 32 bits? 64 bits?
 The memory hardware doesn't know what a
particular part of memory is being used for
 User processes must be restricted so that they only
access memory locations that "belong" to that
particular process.
 This is usually implemented using a base register
and a limit register for each process.
 Every memory access made by a user process is
checked against these two registers, and if a
memory access is attempted outside the valid
range, then a fatal error is generated.
 The OS has access to all existing memory
locations, as this is necessary to swap users' code
and data in and out of memory. It should also be
obvious that changing the contents of the base and
limit registers is a privileged activity, allowed only
to the OS kernel.
Address binding of instructions and data to memory addresses can happen at
three different stages

 Compile Time - If it is known at compile time where a program will reside in

physical memory, then absolute code can be generated by the compiler,
containing actual physical addresses. However if the load address changes at
some later time, then the program will have to be recompiled. (DOS)
 Load Time - If the location at which a program will be loaded is not known at
compile time, then the compiler must generate relocatable code, which
references addresses relative to the start of the program. If that starting address
changes, then the program must be reloaded but not recompiled.
 Execution Time - If a program can be moved around in memory during the
course of its execution, then binding must be delayed until execution time.
 Static linking – system libraries and program code
combined by the linker into single executable
 Dynamic linking – linking postponed until execution time
 Small piece of code, stub, used to locate the appropriate
memory-resident library routine
 Stub replaces itself with the address of the routine, and
executes the routine
 Operating system checks if routine is in processes’ memory
address
 Dynamic linking is particularly useful for libraries
 System also known as shared libraries
 Consider applicability to patching system libraries
 Program operates in an address space that is
distinct from the physical memory space of the
machine

0x000…

Processor Memory
translator
Registers

0xFFF…
 All programs are stored in secondary memory/storage.
 To execute the programs, we need to load them into RAM
 The maximum number of processes in the SECONDARY
RAM is the degree of multi-programming. P1
P2
P3
P4
RAM
P5
P1
P6
P5
P7
P10
P8
P9
P10
P11
Prachi Pandey, C-DAC Bangalore
 A process must be loaded into memory in order to execute.
• If there is not enough memory
available to keep all running
processes at the same time, some
processes who are not currently
using the CPU may have their
memory swapped out local disk
called backing store.
• If compile-time/ load-time address
binding is used, then processes must
be swapped back into the same
memory location from which they
were swapped out. If runtime binding
is used, then processes can be
swapped back into any available
location.
 The problem the OS has is how best to manage the
memory resource, that is how and when to divide the
memory into blocks and how and when to allocate
the blocks to processes.

 Challenges:
 Memory Allocation
 Memory Protection
 Garbage Collection
 IO Support
 Swapping, fragmentation and compaction

Prachi Pandey, C-DAC Bangalore

 MEMORY ALLOCATION TECHNIQUES

CONTIGUOUS NON-CONTIGUOUS

PAGING

FIXED VARIABLE
PARTITION PARTITION SEGMENTATION
SCHEME SCHEME

Prachi Pandey, C-DAC Bangalore

 Number of partitions are fixed.
 Partitions are made before the execution or during system
configure.
 Size of each partition may or may not be same.
 Hence, we have two types to fixed partitioning:
o Equal size partitions
o Unequal size partitions
 Contiguous allocation of memory is done and hence spanning
is not allowed.

Prachi Pandey, C-DAC Bangalore

External Internal
Fragmentation Fragmentation

P5 – 8MB OS

P1 – 7MB P1 – 7MB 8MB

1MB
4MB
P2- 4MB 8MB
P2 – 4MB

P3 – 8MB P3 – 8MB 8MB

4MB
P4 – 4MB 8MB
P4 – 4MB

Prachi Pandey, C-DAC Bangalore

 Better memory utilization than equal OS
size partition. P1 – 4MB 4MB
 Processes of different sizes can be
accommodated. 4MB 4MB

 Here also we see that 16Mb blocks P2 – 8MB

8MB
have 8MB unused space causing
Internal Fragmentation
P3 – 8MB 8MB
 We have 20 MB space available if
we add all un-used spaces. 8MB

 A new process P6 with size P4 – 8MB 16MB

16MB cannot be allocated space 8MB
causing External Fragmentation.
16MB
P5 - MB

Prachi Pandey, C-DAC Bangalore

 Equal size partitions - It divides the main memory into equal number
of fixed sized partitions.
 Memory use is inefficient, i.e., block of data loaded into memory
may be smaller than the partition causing internal fragmentation.
 Any process whose size is bigger than partition size cannot be
loaded.

 Un-equal Size Partitions - It divides the main memory into un-equal

sized partitions.
 Efficient memory usage than equal size partitioning.
 Still suffers from internal fragmentation.

Prachi Pandey, C-DAC Bangalore

Prachi Pandey, C-DAC Bangalore
 Internal fragmentation - Memory block assigned to process
is bigger. Some portion of memory is left unused, as it
cannot be used by another process.
 Limit in process size as the memory blocks are of fixed
sizes.
 Limitation on degree of multi-programming – number of
partitions are fixed and hence there is hard limit to number
processes that can be loaded into the memory.
 External Fragmentation - Total memory space is enough to
satisfy a request or to reside a process in it, but it is not
contiguous, so it cannot be used.
o Compaction - External fragmentation can be reduced by
compaction or shuffle memory contents to place all free
memory together in one large block.

Prachi Pandey, C-DAC Bangalore

 Partitions are not made before the execution or
during system configure.
 The size of partition will be equal to incoming
process.
 The partition size varies according to the need of the
process so that the internal fragmentation can be
avoided to ensure efficient utilization of RAM.
 Number of partitions in RAM is not fixed and
depends on the number of incoming process and
Main Memory’s size.

Prachi Pandey, C-DAC Bangalore

 OS
P1 –
4 MB
4MB

7 MB
P2 –
7MB

P3 –
16 MB
16MB

P4 – 9MB 9 MB

P4 – 4MB 4 MB

Prachi Pandey, C-DAC Bangalore

 OS
P1 –
4 MB
4MB

7 MB
P2 –
7MB

P3 –
16 MB
16MB

P4 – 9MB 9 MB

P5 – 4MB 4 MB

Prachi Pandey, C-DAC Bangalore

 Available free memory –
8MB
OS

Can we P6 – 8MB 4 MB
allocate space
for P6?
7 MB
P2 –
7MB

P3 –
164MB
16MB

P4 – 9MB 9 MB
External
Fragmentation
4 MB

Prachi Pandey, C-DAC Bangalore

 Advantages
◦ No Internal Fragmentation
◦ No restriction on Degree of Multiprogramming
◦ No Limitation on the size of the process

 Disadvantages
◦ Difficult Implementation: it involves allocation of memory during
run-time rather than during system configure.
◦ External Fragmentation: There will be external fragmentation inspite
of absence of internal fragmentation.

Prachi Pandey, C-DAC Bangalore

How to satisfy a request of size n from a list of free
holes

 First fit
 Best fit
 Worst fit

Prachi Pandey, C-DAC Bangalore

First Fit Memory Allocation
 In this method, first job claims the first available memory with space
more than or equal to it’s size.
 The operating system doesn’t search for appropriate partition but just
allocate the job to the nearest memory partition available with
sufficient size.

 Advantages
o It is fast in processing.
 Disadvantages
o Wastage of memory - smaller processes may be allocated larger
spaces resulting in in-efficiency

Prachi Pandey, C-DAC Bangalore

 OS
P12

P1- 15 MB 25MB
15MB
P14
16 MB
P2 –
16MB 100M
B

P22

20MB
P9

Prachi Pandey, C-DAC Bangalore

10MB
Best Fit Memory Allocation
 The operating system first searches the whole of the memory
according to the size of the given job and allocates it to the closest-
fitting free partition in the memory.

 Advantages
o Memory efficient - allocates the process to the minimum possible
space available in the memory
o Minimal internal fragmentation

 Disadvantages
o Slow Process - Checking the whole memory for each job makes
the working of the operating system very slow.

Prachi Pandey, C-DAC Bangalore

 OS
P12

P1- 16 MB 25MB
8MB
15MB
P14

P2 – 100M
16MB B

15 MB P22
P3 – 8MB
20MB
P9

10MB
Prachi Pandey, C-DAC Bangalore
Worst Fit Memory Allocation
 The process traverses the whole memory and always search for the
largest hole/partition, and then the process is placed in that
hole/partition.

 Advantages
o Since this process chooses the largest hole/partition, therefore
there will be large internal fragmentation. This internal
fragmentation is big enough for other small to be allocated
memory.

 Disadvantages
o Slow Process - Checking the whole memory for each job makes
the working of the operating system very slow.

Prachi Pandey, C-DAC Bangalore

 OS
P12

P1- 25MB
15MB
P14

P2 – 15 MB
100M
16MB 16 MB B
8MB

P22
P3 – 8MB
20MB
P9

10MB
Prachi Pandey, C-DAC Bangalore
Requests from processes are 300k, 25k, 125k, 50k
respectively.
The requests can be satisfied with
A) Best fit
B) First fit 150k

C) Worst fit
D) A & B
E) B & C 350k

F) None

Prachi Pandey, C-DAC Bangalore