CSE2008 – Operating Systems
Dr. Venkata Rami Reddy Ch
[Link] Professor
School of Computer Science & Engineering
VIT-AP University
Module-4: Memory Management
• static and dynamic memory, memory allocation to a process, continuous
memory allocation, non-contiguous memory allocation, swapping and
relocation, paging, segmentation, paging with segmentation.
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
Memory management
• A main memory is an array of addressable words.
• Memory management is the process of
• Allocating main memory to user programs
• Deallocating that memory when it is no longer needed
• Protecting each user’s memory area from other user programs
Main memory usually into two partitions:
• Resident operating system, usually held in high
memory
• User processes then held in low memory
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
Memory management techniques
1. Contiguous Memory Allocation
2. Segmentation
3. Paging
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
continuous memory allocation
• Each process is allocated a single contiguous block of memory
• In contiguous memory allocation, each process contained in a single
contiguous section of memory
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
CMA Techniques
Fixed Partitioning
• Memory is divided to fixed-sized partitions
• Each partition holds one process.
• Any process whose size is less than or equal to the
partition size can be loaded into an available partition
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
CMA Techniques
Dynamic Partitioning
• Partitions are created dynamically
based on process size
• Memory is divided into dynamically so
that size of each partition equals to
the size of loaded process.
• Process is allocated exactly as much
memory as it requires
• Hole – block of available memory;
• holes of various sizes are scattered
throughout memory
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
Memory Allocation Algorithms
1. First-fit
2. Best-fit
3. Worst-fit
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
First-fit
• Allocate the first hole that is big enough
• Begins to scan memory from the beginning and chooses the first available
block that is large enough
• We can stop searching as soon as we find a free hole that is large enough.
• Ex: Process P1=357 KB
Memory allocation for Process P1 using First-fit
Best-fit
• Allocate the smallest hole that is big enough;
• We must search entire list, unless ordered by size
• This strategy produces the smallest leftover hole
• chooses the block that is closest in size to the request
Ex: Process P1=357 KB
Memory allocation for Process P1 using Best-fit
Worst-fit
• Allocate the largest hole;
• We must also search the entire list
• This strategy produces the largest leftover hole
• First-fit and best-fit better than worst-fit in terms of speed and storage
utilization
Ex: Process P1=357 KB
Memory allocation for Process P1 using Worst-fit
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
Dr. Venkata Rami Reddy Ch , Sr. Assistant Professor, SCOPE
Allocation using First-fit
P1=357 KB
P2=210 KB
P3=468 KB
P4=491 KB
Allocation using Best-fit
P1=357 KB
P2=210 KB
P3=468 KB
P4=491 KB
Allocation using Worst-fit
P1=357 KB
P2=210 KB
P3=468 KB
P4=491 KB
Problem-2
Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB
(in order), how would each of the first-fit, best-fit, and worst-fit algorithms
place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?Which
algorithm makes the most efficient use of memory?
a. First-fit:
b. Best-fit:
P1=212 KB, P2=417 KB, P3=112 KB, P4=426 KB
1. 212K is put in 300K partition
2. 417K is put in 500K partition
3. 112K is put in 200K partition
4. 426K is put in 600K partition
c. Worst-fit:
P1=212 KB, P2=417 KB, P3=112 KB, P4=426 KB
1. 212K is put in 600K partition
2. 417K is put in 500K partition
3. 112K is put in 388K partition
4. 426K must wait
In this example, best-fit turns out to be the best.
Fragmentation
• It is a phenomenon in which storage space is used inefficiently.
Internal Fragmentation
• It is a phenomenon in which there is wasted space internal to partition due to
size of loaded process is smaller than the partition size.
• It occurs in fixed partitioning
External Fragmentation
• It exists when there is a total memory space exists to satisfy a request, but
available space is not contiguous
• It occurs in dynamic partitioning and segmentation
Example:
Suppose memory has holes: 100 KB, 300 KB, 200 KB
Process requests= 250 KB
• Can’t be allocated even though total free memory = 600 KB → external fragmentation.
Segmentation
User’s View of a Program
• Segmentation is a memory management technique
where a program is divided into variable-sized logical
segments.
• A program is a collection of segments
• A segment is a logical unit such as:
main program
method
object
local variables, global variables
stack
symbol table
arrays
Segmentation
• When the user program is compiled, and the compiler automatically
constructs segments reflecting the input program.
• A C compiler might create separate segments for the following:
1. The code
2. Global variables
3. The heap, from which memory is allocated
4. The stacks used, by each thread
5. The standard C library
Segmentation Hardware
• Segmentation hardware is the part of the computer’s memory management unit
(MMU) that supports segmentation.
Segmentation Hardware
Components of Segmentation Hardware:
Segment Table
• Each process has a segment table.
• Stores information for each segment:
Base Address → starting physical address of the segment in memory.
Limit (Length) → size of the segment.
• Logical address consists of a two tuple:
<segment-number, offset>,
• The segment number is used as an index to the segment table.
• The offset d must be less than the segment limit.
• When an offset is legal, it is added to the segment base to produce the address in
physical memory of the desired byte.
Memory allocation in segmentation.
Address Translation in Segmentation
Logical Address = ( Segment number (s) , Offset (d) )
Steps:
[Link] generates (s, d).
[Link] segment table entry for s:
1. Get Base Address and Limit.
[Link] d ≥ Limit → Trap: segmentation fault.
[Link],
Physical Address = Base Address + d.
Example
•Segment Table:
• Seg 0 → Base = 2000, Limit = 600
• Seg 1 → Base = 4000, Limit = 1000
Logical Address = (1, 500)
•Check: 500 < 1000 ✅
•Physical Address = 4000 + 500 = 4500
Problems on segmentation
A system uses segmentation for memory management. The segment table is given below:
Segment No. Base Address Length
0 4000 300
1 6000 800
2 9000 1000
Given the following logical addresses in the form (segment number, offset), compute the
corresponding physical addresses. If the offset is greater than or equal to the segment
length, report a Segment Fault.
Logical Addresses:
1. (0, 250)
2. (1, 700)
3. (2, 1200)
4. (0, 350)
•Logical Address = (Segment No., Offset) Segment Table
•Physical Address = Base Address of that segment + Offset Segment Base Leng
•Condition: If offset ≥ length, it causes a Segment Fault. No. Address th
0 4000 300
Logical Addresses
1 6000 800
1.(0, 250)
Segment 0 → Base = 4000, Length = 300 2 9000 1000
Offset = 250 < 300 ✅ valid
Physical Address = 4000 + 250 = 4250 4. (0, 350)
2. (1, 700) • Segment 0 → Base = 4000, Length = 300
Segment 1 → Base = 6000, Length = 800 • Offset = 350< 300 ❌ invalid
Offset = 700 < 800 ✅ valid • Result = Segment Fault
Physical Address = 6000 + 700 = 6700
✅ Final Answers
3. (2, 1200) 1.(0, 250) → 4250
• Segment 2 → Base = 9000, Length = 1000 2.(1, 700) → 6700
• Offset = 1200 < 1000 ❌ invalid 3.(2, 1200) → Segment Fault
• Result = Segment Fault 4.(0, 350) → Segment Fault
Drawbacks of Segmentation
1. External Fragmentation
2. Complex Memory Allocation
3. Unequal Segment Sizes
4. Overhead of Segment Table
5. Protection and Sharing Complexity
6. Difficulty in Compaction
External Fragmentation in segmentation.
• Segmentation suffers with External Fragmentation
• When processes are loaded and removed, free memory gets divided into scattered
holes.
• A new segment might be larger than any single hole, even if the total free memory is
enough
Why Segmentation Suffers External Fragmentation?
• Segments are not fixed size (variable).
• Each segment needs a continuous block of memory.
• As processes come and go, free blocks are scattered, leaving gaps.
Example:
Suppose memory has holes: 100 KB, 300 KB, 200 KB
Process requests segment = 250 KB
Can’t be allocated even though total free memory = 600 KB → external fragmentation.