Operating Systems

ECEG-5202

MEMORY MANAGEMENT
Outline
▪Introduction
▪Memory partitioning
▪Paging
▪Segmentation

December 20, 2022 MEMORY MANAGEMENT 2

Introduction
Uniprogramming system
◦ Main memory is divided into two
◦ For the OS (resident monitor, kernel)
◦ For the program currently being executed

Multiprogramming system
◦ “User” part of memory must be further subdivided to accommodate
multiple processes
◦ The sub-division is carried out dynamically by OS
=> Memory management

December 20, 2022 MEMORY MANAGEMENT 3

Introduction…
Memory management
◦ Involves swapping blocks of data from secondary storage

◦ If only a few processes can be kept in main memory, then much of the time
all processes will be waiting for I/O and the CPU will be idle

◦ Memory needs to be allocated efficiently in order to pack as many processes

into memory as possible

December 20, 2022 MEMORY MANAGEMENT 4

Introduction…
Terminologies

December 20, 2022 MEMORY MANAGEMENT 5

Introduction…
Requirements
◦ What memory management intends to satisfy
◦ Relocation
◦ Protection
◦ Sharing
◦ Logical organization
◦ Physical organization

December 20, 2022 MEMORY MANAGEMENT 6

Introduction…
Requirements…
◦ Relocation
◦ Memory is generally shared among a number of processes
◦ The programmer does not know
◦ Where the program will be placed in memory when it is executed
◦ Which other programs will be resident in main memory at the
time of execution of the programmer’s program
◦ The program may be swapped to disk and return to main memory
at a different location (relocated)

December 20, 2022 MEMORY MANAGEMENT 7

Introduction…
Requirements…
◦ Relocation…
◦ Memory references in code (for
both instruction and data) must
be translated to the actual
physical memory address,
reflecting the current location of
the program in main memory

December 20, 2022 MEMORY MANAGEMENT 8

Introduction…
Requirements…
◦ Protection
◦ Processes should not be able to reference memory locations in
another process for reading or writing purpose without permission
◦ Impossible to check absolute addresses at compile time to assure
protection
◦ Programs could be relocated
◦ Address references must be checked at run time by hardware

December 20, 2022 MEMORY MANAGEMENT 9

Introduction…
Requirements…
◦ Sharing
◦ Flexibility to allow several processes to access a same portion of
main memory
◦ Processes executing the same program should be allowed to
access the same copy of the program rather than have their own
separate copy
◦ Cooperating processes may need to share access to the same
data structure

December 20, 2022 MEMORY MANAGEMENT 10

Introduction…
Requirements…
◦ Logical organization
◦ Users write programs in modules with different characteristics
◦ Instruction modules are execute-only
◦ Data modules are either read-only or read/write
◦ Some modules are private others are public
◦ To effectively deal with user programs, the OS and hardware should support a
basic form of module to provide the required protection and sharing
◦ Advantage
◦ Modules can be written and compiled independently
◦ Different degrees of protection can be given to different modules
◦ Sharing on a module level corresponds to user’s way of viewing the problem
◦ Easy for user to specify the sharing that is desired

December 20, 2022 MEMORY MANAGEMENT 11

Introduction…
Requirements…
◦ Physical organization
◦ Hierarchy of memory : secondary memory, primary memory
◦ Moving information between these two levels of memory is a major concern of
memory management
◦ Highly undesirable and impractical to leave this responsibility to the application
programmer. Why?
1. The main memory available for a program plus its data may be insufficient
◦ Overlay: various modules can be assigned the same region of memory, with a
main program being responsible for switching the modules in and out as needed
◦ Even with the aid of compiler tools, overlay programming wastes programmer
time
2. At time of coding, programmer doesn’t know how much space will be available
or where that space will be

December 20, 2022 MEMORY MANAGEMENT 12

Introduction…
Goals of memory management
◦ Memory management shouldn’t block any process
◦ All processes should be able to run
◦ Space overhead of the memory manager must be
reasonable
◦ It should be as minimum as possible
◦ CPU time used by the memory manager should be
reasonable
◦ It should be as minimum as possible

December 20, 2022 MEMORY MANAGEMENT 13

Memory partitioning
Principal operation of memory management
◦ To bring processes into main memory for execution by
the processor
Memory partitioning is simple but old approach
used to manage memory
Memory partitioning is not used in modern OSs
Two types of memory partitioning
◦ Fixed partitioning
◦ Dynamic partitioning

December 20, 2022 MEMORY MANAGEMENT 14

Memory partitioning…
Fixed partitioning
◦ “User” memory is divided into N non-overlapping
regions called partitions
◦ Two alternatives
◦ Equal-size partition
◦ Unequal-size partition
◦ Difficulties with equal-size partition
◦ Program could be too big to fit into the partition
◦ Programmer must design the program with the use of
overlays
◦ Main memory utilization is extremely in efficient
◦ Internal fragmentation

December 20, 2022 MEMORY MANAGEMENT 15

Memory partitioning…
Fixed partitioning …
◦ Placement algorithm
◦ Equal-size partitioning
◦ If there is an available partition, a process can be loaded into that
partition
◦ Because all partitions are of equal size, it does not matter which
partition is used
◦ If all partitions are occupied by blocked processes, choose one process
to swap out to make room for the new process
◦ Which one to swap out is scheduling decision

December 20, 2022 MEMORY MANAGEMENT 16

Memory partitioning…
Fixed partitioning…
◦ Placement algorithm…
◦ Unequal-size partitioning
◦ Two approaches
◦ Use of multiple queue
◦ Assign each process to the smallest partition
within which it will fit
◦ Requires a scheduling queue for each partition
◦ Has minimal overhead
◦ Advantage
◦ Processes are assigned in such a way as to
minimize wasted memory within a partition
◦ Problem
◦ Some queues will be empty if no process
within a size range is present
December 20, 2022 MEMORY MANAGEMENT 17
Memory partitioning…
Fixed partitioning…
◦ Placement algorithm…
◦ Unequal-size partitioning…
◦ Use of a single queue
◦ The smallest available partition that will hold the process is selected
◦ If there is no free slot, swap out of the smallest partition that will hold
the incoming process
◦ Advantage (general)
◦ Simple and require minimal OS software and processing overhead
◦ Disadvantages
◦ Number of partitions dictate number of active processes
◦ Small jobs will not utilize partition space efficiently (internal
fragmentation)
◦ Used in IBM mainframe OS, OS/MT (Multiprogramming with a Fixed
Number of Tasks)

December 20, 2022 MEMORY MANAGEMENT 18

Memory partitioning…
Dynamic partitioning
◦ Overcomes some of the difficulties with fixed partitioning
◦ Partitions are of variable length and number
◦ Each process is allocated exactly as much memory as it requires
◦ Used in IBM mainframe OS, OS/MVT (Multiprogramming with a Variable Number of Tasks)
◦ Leads to a situation in which there are a lot of holes in memory
◦ Example
◦ A hole of 4M is left after loading 3 processes
◦ Several holes are created as more processes are swapped

December 20, 2022 MEMORY MANAGEMENT 19

Memory partitioning…
Dynamic partitioning…

◦ The holes , which are formed in main memory are called external
fragmentation
◦ Solution
◦ Compaction
◦ Shifts processes so they are contiguous and all free memory is in one block

December 20, 2022 MEMORY MANAGEMENT 20

Memory partitioning…
Dynamic partitioning…
◦ Disadvantage of compaction
◦ It is time consuming procedure
◦ Wastes processor time

◦ Note
◦ Compaction implies the need for a dynamic relocation capability
◦ Must be possible to move a program from one region to another in main
memory without invalidating the memory references in the program

December 20, 2022 MEMORY MANAGEMENT 21

Memory partitioning…
Dynamic partitioning…
◦ Placement algorithm
◦ Used to decide which free block that is equal to or larger than the process size to
allocate
◦ Goal
◦ To reduce usage of compaction which is time and CPU consuming
◦ Possible algorithms
◦ Best-fit
◦ Choose smallest block that is closest in size to the request
◦ Scans all available blocks
◦ First-fit
◦ Scans and choose first block from beginning of memory
◦ Next-fit
◦ Scans and choose the next available block from last placement
December 20, 2022 MEMORY MANAGEMENT 22
Memory partitioning…
Dynamic partitioning…
◦ Placement algorithm…
◦ Example
◦ Memory configuration
before and after
allocation of 16KB block
using best-fit, first-fit and
next-fit

December 20, 2022 MEMORY MANAGEMENT 23

Memory partitioning…
Dynamic partitioning…
◦ Placement algorithm…
◦ Which of these approaches is best, depends on
◦ Exact sequence of process swapping that occurs
◦ The size of those processes
◦ General comment
◦ Next-fit
◦ Often leads to allocation of the largest block at the end of
memory
◦ Compaction may be required more often (as it breaks the
largest block into smaller pieces quickly)

December 20, 2022 MEMORY MANAGEMENT 24

Memory partitioning…
Dynamic partitioning…
◦ Placement algorithm…
◦ General comment…
◦ First-fit
◦ Simplest and fastest
◦ Favors allocation near the beginning
◦ Tends to create less fragmentation than Next-fit
◦ May litter the front end with small free partitions that need to be searched over
on each subsequent first-fit pass
◦ Best-fit
◦ Usually the worst
◦ Searches for smallest block that satisfies the requirement
◦ Main memory quickly forms holes too small to hold any process
◦ Compaction generally needs to be done more often

December 20, 2022 MEMORY MANAGEMENT 25

Memory partitioning…
Buddy system
◦ Drawbacks of fixed and dynamic partitioning schemes
◦ Fixed partitioning system
◦ Limits the number of active processes
◦ Uses space inefficiently if there is poor match between available
partition size and process size
◦ Dynamic partitioning system
◦ Complex to maintain
◦ Has the overhead of compaction
◦ Compromise between the two
◦ Buddy system

December 20, 2022 MEMORY MANAGEMENT 27

Memory partitioning…
Buddy system…
◦ Memory blocks are available in size of 2k
where L <= K <= U
2L= smallest size of block allocatable
2U= largest size of block allocatable
(generally, the entire memory available)

December 20, 2022 MEMORY MANAGEMENT 28

Memory partitioning…
Buddy system…
◦ We start with the entire block of size 2U
◦ When a request of size S is made
If 2U-1 < S <= 2U then
allocate the entire block of size 2U
Else
split this block into two buddies, each of size 2U-1

If 2U-2 < S <= 2U-1

then allocate one of the 2 buddies
Else
one of the 2 buddies is split again

◦ This process is repeated until the smallest block greater or equal to S is generated
◦ Two buddies are joined whenever both of them become unallocated

December 20, 2022 MEMORY MANAGEMENT 29

Memory partitioning…
Buddy system…
◦ Example

December 20, 2022 MEMORY MANAGEMENT 30

Memory partitioning…
Relocation
◦ A process may occupy different main memory locations during its lifetime
◦ Reasons
◦ Swapping and compaction
◦ Problem
◦ Physical memory references by a process cannot be fixed

December 20, 2022 MEMORY MANAGEMENT 31

Memory partitioning…
Relocation….
◦ Solution
◦ Distinguishing between
◦ Logical address and physical address
◦ Logical address
◦ Reference to a memory location independent of the current assignment of data to memory
◦ A translation must be made to a physical address before the memory access can be achieved
◦ Compilers produce code in which all memory references are logical addresses
◦ Example
◦ Relative address
◦ The address is expressed as a location relative to some known point, usually a value in a
processor register
◦ Physical address (absolute address)
◦ Is an actual location in main memory

December 20, 2022 MEMORY MANAGEMENT 32

Memory partitioning…
Relocation….
◦ Address translation
◦ Relative address is the most frequent type of logical address used
◦ Modules are loaded in main memory with all memory references in relative form
◦ Physical addresses are calculated “on the fly” as the instructions are executed
◦ For adequate performance, the translation from relative to physical address must be done by
hardware

December 20, 2022 MEMORY MANAGEMENT 33

Memory partitioning…
Relocation….
◦ Address translation…
◦ When a process is assigned to the running state
◦ A base register gets loaded with the starting physical address of the process
◦ A bound register gets loaded with the process’s ending physical address
◦ When a relative addresses is encountered,
◦ Relative address is added with the content of the base register to obtain the physical address
◦ Physical address is compared with the content of the bound register
◦ If address is within bounds, the instruction execution may proceed
◦ Otherwise an interrupt is generated

December 20, 2022 MEMORY MANAGEMENT 34

Memory partitioning…
Relocation….
◦ Address translation…

December 20, 2022 MEMORY MANAGEMENT 35

Paging
Main memory is partitioned into equal fixed-sized chunks (of relatively
small size) called frames
Each process is also divided into chunks of the same size called pages
The process pages can thus be assigned to the available chunks in main
memory called frames (or page frames)
Advantage
◦ A process does not need to occupy a contiguous portion of memory

December 20, 2022 MEMORY MANAGEMENT 36

Paging…
Example
◦ Process B is swapped out (e)
◦ Load a new process D with 5 pages. Can D be loaded in memory?
◦ Yes, see (f)
◦ Observation
◦ Process D doesn’t hold contiguous frames
◦ No external fragmentation

December 20, 2022 MEMORY MANAGEMENT 37

Paging…
How can we reference data?
◦ Logical address
◦ Is a single base address register enough?
◦ No
◦ OS maintains a page table for each process
◦ Page table
◦ Shows the frame location for each page of the process
◦ Used to translate logical addresses to physical addresses
◦ Example: page table during (f) of previous example
◦ OS also maintains a single free frame list

December 20, 2022 MEMORY MANAGEMENT 38

Paging…
Logical addressing
◦ Within the program logical address consists
◦ Page number
◦ Used as an index into a page table which contains base address of
each page in physical memory
◦ Offset within the page
◦ Combined with base address to define the physical memory address
◦ For convenience
◦ Page size and frame size are a power of 2
◦ Example
◦ If 16 bits addresses are used and page size = 1K, we need 10 bits for
offset and have 6 bits available for page number
◦ Then the 16 bit address obtained with the 10 least significant bit as
offset and 6 most significant bit as page number is a location relative to
the beginning of the process

December 20, 2022 MEMORY MANAGEMENT 39

Paging…
Address translation
p = page number
d= page offset

December 20, 2022 MEMORY MANAGEMENT 40

Paging…
Address translation…
◦ Example

December 20, 2022 MEMORY MANAGEMENT 41

Paging…
Advantage of using a page size that is a power of 2
◦ Logical address scheme is transparent to
◦ The programmer
◦ The assembler
◦ The linker
◦ Logical address (page number, offset) of a program is identical to its relative address
◦ Simplifies implementation of a function in hardware to perform a dynamic address
translation at run time

December 20, 2022 MEMORY MANAGEMENT 42

Segmentation
Used to subdivide user program into a number of segments
Unlike frames and pages, segments could be of different sizes
◦ There is no simple relationship between logical addresses and
physical addresses

Segmentation is visible to the programmer

◦ Provided as a convenience to organize programs logically (e.g.,
data in one segment, code in another segment)
◦ Programmers must be aware of segment size limit

December 20, 2022 MEMORY MANAGEMENT 43

Segmentation…
OS maintains a segment table for each process
Segment table entry contains
◦ Starting physical addresses of each segment in main memory
◦ Length of that segment (for protection)

When a process enters the running state, the address of its segment table is
loaded into a special register used by the memory management hardware

December 20, 2022 MEMORY MANAGEMENT 44

Segmentation…
Address translation
◦ Consider a logical address of s + d bits
s bits are the segment number
d bits are the offset
◦ Steps
1. Extract the segment number as the leftmost s bits of the logical address
2. Use the segment number as an index into the process segment table to find the
starting physical address of the segment
3. Compare the offset, expressed in the rightmost d bits, to the length of the segment
◦ If the offset is greater than or equal to the length, the address is invalid
4. Sum the starting physical address of the segment with the offset to get the desired
physical address

December 20, 2022 MEMORY MANAGEMENT 45

Segmentation…
Address translation…
◦ Segmentation hardware

December 20, 2022 MEMORY MANAGEMENT 46

Segmentation…
Example
◦ Segment 1, offset 752

December 20, 2022 MEMORY MANAGEMENT 47

Virtual memory-overview
Limitation of previous approaches
◦ Require that an entire process be in memory before it can execute
Virtual memory
◦ Involves separation of logical memory as perceived by users from physical
memory

Benefits of virtual memory

◦ Allows programs to be larger than the physical memory
◦ Less I/O would be needed to load or swap user programs into memory
◦ Abstracts memory into large, uniform array of storage
◦ Allows processes to share files
◦ Allows execution of processes that are not completely in memory
◦ More programs could be run at the same time

December 20, 2022 MEMORY MANAGEMENT 48

Virtual memory-overview…
Why is it not necessary to have all code in memory?
◦ Part of a program that handle unusual error condition may never be
executed
◦ Arrays, lists, and tables are often allocated more memory than they actually
need
◦ Some features of a program may be used rarely

December 20, 2022 MEMORY MANAGEMENT 49

Acknowledgment
These slides are adopted from the slides of
Surafel Lemma Abebe (Ph. D.)

Here, I would like to acknowledge and thank him for allowing me to

customize and use the slides for this course.

December 20, 2022 MEMORY MANAGEMENT 50