Memory Management

Memory Partitioning
Free space management techniques
Paging
Virtual Memory
Page Replacement
Swapping concept
Memory Partitioning
 Divide the memory into several parts each part called as partitions.
 Memory allocation in case of multiprogramming environment.
 Operating System keeps record of occupied as well as free memory.
 When process enter into ready state, operating system check status of
partition.
 Different scheduling algorithm for process to enter into system
Advantages
1. Useful for multiprogramming environment.
2. It is easy to access data from partitions.
3. Easy to access the partitions.
4. Partitions can be dynamic or fixed. This provide flexibility
Memory Partitioning Continue…
 Memory partitioning types
1. Static memory partitioning
2. Dynamic memory partitioning
Memory Partitioning Continue…
Static memory partitioning (Fixed partitioning)
 Fixed size
 If process assigned to memory is less in size, then remaining space
cannot be used by any other process.

Static partition table

Static memory partitioning (Fixed partitioning) continue….
 Advantages:
1. Partition size is fixed and can be easily accessible for the
processes those matches with the partition size.
2. Implementation is easy ( no complex algorithm is required)

 Disadvantage
1. Memory is wastage
2. Internal fragmentation
Memory Partitioning Continue…
Dynamic memory partitioning (Variable partitioning)
 Partition is done based on requirement of process length or size of process is
called as dynamic memory partitioning.
Process in ready queue the OS checks for available enough size partition in
memory.
Partition is larger than required then partition is divided. Then process is kept
in appropriate part of memory and remaining partition of memory added in the
partition available list.
Example. Suppose we have a memory 128 MB out of that memory 32 MB
occupied by operating system remaining 96 MB memory of user process.
Dynamic memory partitioning (Variable partitioning) continue …
Dynamic memory partitioning (Variable partitioning) continue …

 In this way many small partition get created, which may be very small in size.
 This types of small partitions remain unutilized. This is known as external
fragmentation.
 Advantage
1. Partitions are made as per the process length.
2. Memory wastage is very less.
3. Maximum part of memory is utilized
 Disadvantage
1. External fragmentation
2. Compaction
Concept of Compaction
 Compaction shuffles the free memory locations together in one
large block. Compaction is not always possible.

Concept of Compaction continue….

 If static memory allocation done then it is not possible to

implement compaction.
 Another problem occurs while searching the size of process to
allocate the memory i.e. to fit the process of ‘n ’ size into ‘n’ size of
partition.
 There is three methods used for searching available for partition.
1. First fit
2. Best fit
3. Worst
Concept of Compaction continue….
 First fit: Allocate the first block that big enough. Searching can
start either at the beginning of the set of holes or at the location
where the previous first-fit search ended. We can stop searching as
soon as we find a free block that is large enough.
 Best fit: Allocate the smallest block that is big enough. We must
search the entire list, unless the list is ordered by size.
 Worst fit: Allocate the largest block. We must search the entire list,
unless it is sorted by size.
Free space management

 Free-space list
• Records all free disk blocks which is not allocated to some file or
directory.
• Space is removed- New file allocated space.
• Space is added – File is deleted.

 Free space management techniques

 Bit Vector (Bitmap)
 Linked List
Bit Vector or Bitmap
 The free-space list is implemented as bit map or bit vector.
 Each block is represented by bit 1 or 0
 If block is free, the bit is 1
 If the block is allocated, the bit is 0.
 Example. Consider a disk address 2, 3, 4, 8, 9 currently block allocated
 The free-space bit map would be

Block are allocated 2,3,4,8,9

Disk block 0 1 2 3 4 5 6 7 8 9 10
Bitmap 1 1 0 0 0 1 1 1 0 0 1
 1.3 GB disk with 512 bytes blocks would need a bit map of over 332 KB to
track its free blocks.
 1 TB disk with 4 KB blocks requires 32 MB to store its bit map.
 1 PB file system would take 32-GB bitmap just to manage its free space.
Linked List
 In linked list is to link together all the free disk blocks, keeping a
pointer to the first free block in a special location on the disk.
 This first block contains a pointer to the next free block, and so on.
 Example free block are 2,3,4,5,8,9,10,11,12,13,17,18,25,26 and 27
were free block and the rest of the blocks were allocated.
 Keep a pointer to block 1 as the first free block, block 2 would
contain a pointer of block 3 and so on…
 This scheme is not efficient; to traverse the list, we must read each
block, which requires substantial I/O time.
Example free block are 2,3,4,5,8,9,10,11,12,13,17,18,25,26 and
27 were free block and the rest of the blocks were allocated.
Base and Limit Registers

 Base register: The base register holds the smallest legal physical
memory address
 Limit register: The limit register specifies the size of the rang.
Fig. Hardware address protection with base and limit
register
Logical and Physical Address

• Physical Address: Memory unit address is called as

physical address.
• Logical Address: CPU generated address is called as logical
address.
• The set of all logical addresses generated by a program is a
logical address space.
• The set of all physical addresses corresponding to those
logical addresses is a physical address space.
Concept of Paging
 Paging is a memory management scheme that permits the physical
addresses space of a process to be noncontiguous.
 Paging avoid external fragmentation and the need of compaction.
 Frames: The breaking physical memory into fixed sized blocks
called frames.
 Pages: The breaking logical memory into blocks of same size
called pages.
 When a process is to be executed, its pages are loaded into any
available memory frames from their source ( a file system or the
backing store)
 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.
Concept of Paging continue…..
 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 that is sent to the memory unit.
Concept of Paging continue…..
Concept of Paging continue…..
Concept of Paging continue…..
Segmentation

 Memory-management scheme that supports user view of memory

 A program is a collection of segments. A segment is a logical unit
such as:
main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays
User’s View of a Program
Logical View of Segmentation
1

4
1

3 2
4

user space physical memory space

Segmentation Architecture

 Logical address consists of a two tuple:

<segment-number, offset>,
 Segment table – maps two-dimensional physical addresses;
each table entry has:
◦ base – contains the starting physical address where the
segments reside in memory
◦ limit – specifies the length of the segment
 Segment-table base register (STBR) points to the segment
table’s location in memory
 Segment-table length register (STLR) indicates number of
segments used by a program;
segment number s is legal if s < STLR
Segmentation Hardware
Example of Segmentation
Virtual Memory Management
 Virtual memory is a technique that allows the execution of
processes that are not completely in memory.
 The program can be larger than physical memory.
 Entire program not need to load while execution
 Example: Program contain multiple conditional code, declaration
large array , certain routines in program.
 Allows address spaces to be shared by several processes
Virtual Memory That is Larger Than Physical Memory


Virtual-address Space
Shared Library Using Virtual Memory
Demand paging
 Bring a page into memory only when it is needed
◦ Less I/O needed
◦ Less memory needed
◦ Faster response
◦ More users

 Page is needed  reference to it

◦ invalid reference  abort
◦ not-in-memory  bring to memory
 Lazy swapper – never swaps a page into memory unless page will
be needed
◦ Swapper that deals with pages is a pager
Transfer of a Paged Memory to Contiguous Disk Space
Valid-Invalid Bit
 With each page table entry a valid–invalid bit is associated
(v  in-memory, i  not-in-memory)
 Initially valid–invalid bit is set to i on all entries
 Example of a page table snapshot:


Frame # valid-invalid bit
v
v
v
v
i
….

i
i
page table

 During address translation, if valid–invalid bit in page table entry

is I  page fault
Page Table When Some Pages Are Not in Main Memory
Page Fault
 If there is a reference to a page, first reference to
that page will trap to operating system:
page fault
1. Operating system looks at another table to decide:
◦ Invalid reference  abort
◦ Just not in memory
2. Get empty frame
3. Swap page into frame
4. Reset tables
5. Set validation bit = v
6. Restart the instruction that caused the page fault
Page Fault (Cont.)
 Restartinstruction
◦ block move

◦ auto increment/decrement location

Steps in Handling a Page Fault
Page Replacement

 Prevent over-allocation of memory by modifying page-

fault service routine to include page replacement

 Use modify (dirty) bit to reduce overhead of page

transfers – only modified pages are written to disk

 Page replacement completes separation between logical

memory and physical memory – large virtual memory
can be provided on a smaller physical memory
Need For Page Replacement
Basic Page Replacement
1. Find the location of the desired page on disk

2. Find a free frame:

- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim
frame

3. Bring the desired page into the (newly) free

frame; update the page and frame tables

4. Restart the process

Page Replacement
Page replacement algorithm
 FIFO Page Replacement
FIFO replacement algorithm associates with each page the time when
that page was brought into memory. When a page must be replaced,
the oldest page is chosen.
Page replacement algorithm
 Optimal Page Replacement
Replace the page that will not be used for the longest period of time.
Page replacement algorithm
 LRU Page Replacement
Replace the page that has not been used for the longest period of
time.