Memory Management Flashcards
What are the main aspects that distinguish a memory management strategy?
- Sequence of operation
- Size of pieces
- Representation of allocation
- Fragmentation
- Allocation strategies (with free pieces)
- (Re)-integration
Describe Sequence of Operation approaches
It is the action of allocation and release of memory.
- In same order: queuing approaches, FIFO
- In reverse order: Batch approaches, LIFO
- in arbitrary order: general approach
Describe size of pieces concepts
- Constant size: NUM = 1 (unit size)
- Multiple of constant size: NUM = k (unit size)
- Give size of partitions: NUM = k_1, k_2, k_3
- Arbitrary size: NUM = x
Describe the concept of representation of allocation, give two examples
- How allocation of memory is represented: Using a vector or table
- Where is allocation of memory represented: Separated or Integrated
In a separated representation by table: information about allocation is stored in a table that is sorted by address and/or length
In an integrated representation by vector: allocation information/pieces identify themselves, specify their lengths and provide pointer to next element of free list. The pointer to next free elements of memory can be sorted by address (next closest free address) or length (next longest free address list)
Example: Main Memory is represented with words of 32 bits
Describe the concept of fragmentation
Usually memory is allocated for multiple of units where requests are rounded up to the next multiple of units.
- Internal fragmentation: The unused parts of the allocated memory.
- External fragmentation: Overall amount of free memory can satisfy a request but because of the dynamic of allocation and release of pieces, the layout of the free memory can not satisfy a request.
Describe Memory Allocation Strategies and their characteristics
- First Fit Strategy: Search the free list from start and take the first piece of free memory that satisfies the request (low effort, external fragmentation, concentration of allocated memory at beginning of memory space, increased search effort in loaded situations).
- Next Fit Strategy, Rotating First Fit Strategy: Cyclic search of list that starts from point of last allocation (like First Fit but without concentration at beginning of memory space leading to slightly reduced search effort).
- Best Fit Strategy: Allocate the smallest piece of memory that satisfies the request. If sorted by address the whole free list will be searched therefore list should be sorted by size of piece of free memory to avoid long search times. Allows for reduced external fragmentation but may produces very small pieces of free memory that can not be used for any future requests.
- Nearest Fit Strategy: Provided with favored address, search with First Fit from that address.
Describe the concept of Re-integration
It is the process of joining up free memory pieces together when one in the middle is released. It can happen instantly after release or delayed.
Describe a ring buffer
- Allocation and release in same direction
- Fix length of pieces
- No search needed
- No external fragmentation
- Automatic and immediate reintegration
Describe a Stack
- Allocation and release in inverse direction (LIFO)
- Arbitrary length of pieces
- No search needed
- Little external fragmentation
- Automatic and immediate reintegration
Describe Vector based approach
- Allocation and release in arbitrary direction
- Fixed length with k * unit size
- Search for first fitting piece
- Internal and external fragmentation
- Automatic and immediate reintegration
Describe boundary tag system and its optimizations techniques.
The boundary tag includes labels for:
* free pieces: free label, length of free piece, pointer to next/previous free piece.
* used pieces: used label, length of used piece.
The labels are at the beginning / end of the free and used pieces
- Operation in arbitrary order
- Allocation of pieces with arbitrary size (length)
- Integration of management and representation of pieces (doubly linked list sorted by size of pieces).
- Best Fit search strategy
- External fragmentation
- Explicit immediate reintegration using length labels to check with neighboring pieces (immediate integration into linked list).
Optimizations:
- Transform external fragmentation to internal fragmentation by merging requested piece and small piece.
- Avoid integration of small pieces into the free list but merge them with released
- Reduce cost of search on arbitrary order of allocation and release from O(n) by changing the free list into a binary tree
Describe Buddy System
- Allocation and release in arbitrary order:
- allocation: Check for next value with power of two, take first entry of list. In case of empty list, take first entry of next list with bigger pieces, cut piece in half and insert second half into list of original size and take remaining for request.
- release: determine buddy of piece to be released. if buddy is used, insert piece into buddy’s free list. In case buddy is free, join both piece and buddy) and insert emerged piece into next free list.
- Allocation of pieces with unit size of 2^0, 2^1, 2^2, …, 2^k.
- Separated representation: Array of heads of free lists for pieces with same size
- Limited search costs
- Internal and external fragmentation: Amount of internal fragmentation can be fairly large.
- Explicit reintegration: Pieces split in one action by joined by release
What is an address space and what is the difference between logical and physical address spaces?
An address space is a contiguous set of addresses.
A logical address space is the program address space (from the view of a thread/program) while the physical address space is defined by the width of the address bus.
What is problem when not using logical memory?
How does paging solve it (structure, + and -)
How does segmentation solve it (structure, + and -)
Memory management is the responsibility of dividing the memory among the various processes.
The fundamental goal of memory management is to make optimal use of memory by minimizing internal and external fragmentation. At a moment, a single process is loaded into memory. Partition main memory into a set of non-overlapping memory regions called partitions.
Memory can be allocated in contiguous or non-contiguous memory/partitions. Paging and Segmentation are parts of the non-contiguous allocation of memory i.e. it is a memory management technique
Paging:
Paging is a memory allocation method that allows a process’s physical address space to be non-contiguous.
Physical memory is divided into fixed-sized blocks called frames, and logical memory space is divided into fixed-sized blocks called pages.
Paging separates logical and physical addresses, with logical addresses consisting of a page number and offset, and physical addresses consisting of a frame number and offset.
The page table base register (PTBR) refers to a process’s page table, and the page table length register (PTLR) indicates the size of the page table.
Every new process creates a separate page table, which is stored in physical memory and contains the base address of each page.
Characteristics of paging include no external fragmentation, non-contiguous memory allocation, and potential internal fragmentation on the last page of a process.
Advantages of paging include effective memory management, simplicity in partitioning, and simple and inexpensive memory allocation.
Disadvantages of paging include internal fragmentation, address translation using specialized hardware, and longer memory access times.
Segmentation:
Segmentation divides the virtual address space of a process into variable-sized segments that correspond to logical units of the program. Segments must be loaded into memory before a program can run. Address mapping is done with a segment table, indicated by the segment-table base register (STBR) and the segment-table length register (STLR). Advantages of segmentation include no internal fragmentation, efficient translation, and the ability to protect and share different segments. Disadvantages of segmentation include external fragmentation and expensive memory management. The program's main function, utility functions, data structures, and so on are all contained within a program segment. The segment table is smaller than the table used in paging, and the OS keeps a segment map table and a list of free memory blocks for each process.
What is the difference between regular page table and inverted page table?
In virtual memory management, a page table is a data structure used by the operating system to store the mapping between logical and physical addresses of a process. A regular page table stores the mapping information for each page of the process in a separate table entry, which means that for a process with a large number of pages, the page table can become very large.
On the other hand, an inverted page table is a page table implementation that maintains a single table for all the processes in the system. Rather than having a separate table entry for each page of a process, an inverted page table has an entry for each physical frame in memory, which stores the process ID and page number that maps to that frame. This means that the size of the page table is proportional to the number of physical frames in memory rather than the number of pages in the process.
The main advantage of the inverted page table is that it can reduce the memory overhead associated with maintaining a separate page table for each process. However, it is more complex to implement and requires additional processing time for page table lookups, as it requires a search through the entire table to find the mapping for a given process and page number.
