5. Memory Management¶

Notes¶

Most operating systems (for example Windows and Linux) use Segmentation with Paging. A process is divided into segments and individual segments have pages.ref
Memory Allocations techniques:
- Contiguous:
  - Contiguous static allocation. ref
  - Contiguous dynamic allocation. ref
- Non-contiguous:
  - Paging.
  - Multi-level paging.
  - Inverted Paging.
  - Segmentation.
  - Segmentation with paging.
Paging reduces external fragmentation. Segmentation reduces internal fragmentation.
Logical Address. is generated by the CPU while a program is running. It is a virtual address. It is the address that the program sees. It needs to be converted to a physical address before it can be used.
Logical Address Space. is the set of all possible logical addresses that can be generated by a program.
Memory Management Unit (MMU). is a hardware component that translates logical addresses to physical addresses.
Physical Address. is the address that is used by the hardware to access the memory. Processes do not see physical addresses; they see logical addresses which are translated by the MMU to physical addresses before they are used.
Physical Address Space. is the set of all possible physical addresses that correspond to the logical address space of a process.
Data structures are used in address translation:
- Page Table(PT). Per-process. A map from a logical page number to the physical frame number. One page table per process.
- Inverted Page Table(IPT). Per-frame. A map from a physical frame number to the logical page number. One inverted page table for the entire physical memory. ref
- Hashed Page Table(HPT). ref
- Translation Look-aside Buffer(TLB): faster, smaller. A tag-value associative array (map).
Types of segmentation:
- Simple segmentation. segmentation of the main memory, all generated segments reside in the main memory.
- Virtual memory segmentation. segmentation of the virtual memory, all generated segments reside in the virtual memory.

Difference between fine-grained and coarse-grained SIMD architecture ¹¶

SIMD :
- Stands for Single Instruction Multiple Data. (according to Flynn’s classification, see more here: https://www.geeksforgeeks.org/computer-architecture-flynns-taxonomy/)
- It exists in computers with multiple processing elements that perform the same operation on multiple data points simultaneously.
Granularity: The degree to which a program is broken down into its constituent parts. It has two types:
- Fine-grained: The program is broken down into many small parts.
- Coarse-grained: The program is broken down into a few large parts.

	Fine-grained	Coarse-grained
Computation time	less time is needed (since there are more threads)	more time is needed to execute the program
Parts	large number of small parts	few number of large parts
Parallelism	high	low
Grain size	small (2- 500 instructions)	large (+1000 instructions)
Parallelism types	Instruction Level Parallelism - Loop Level Parallelism	Sub-program - Program Level Parallelism
Load balancing	needed	not needed
Cost	high	low
Concept	Multithreaded architecture (future)	single-threaded architecture (past)

Tools to detect memory leaks ²¶

A Memory Leak occurs when a piece of memory is allocated (e.g. using malloc()) and never freed although it is no longer needed. This can happen when a pointer to the allocated memory is lost, or when the memory is not freed after use.
A Buffer Overrun occurs when a program writes more data into a memory buffer than it was allocated to hold. This can happen when a program writes past the end of an array, or when a program writes past the end of a string.
Memory leaks are a greater problem in embedded systems since they have limited memory and run for a long time without rebooting.
Tools to monitor memory in Linux:
1. MemWatch. https://sourceforge.net/projects/memwatch
2. Valgrind. https://valgrind.org/
3. MemLeax. https://github.com/WuBingzheng/memleax
4. Collecting core dump using abrt or abrt-addon-ccpp.
5. Using default tools such as sar, vmstat, pmap, meminfo, free, top, ps, etc.
Examples of memory leaks:

///////////////////////////////// Example 1: Lost pointer  //////////////////////////////////
char *ptr1 = (char *)malloc(100);
char *ptr2 = (char *)malloc(100);

ptr1 = ptr2; // ptr1 is lost, nothing is pointing to it nor freeing it

/** To fix this, we must free ptr1 before assigning ptr2 to ptr1 **/

free(ptr1);
free(ptr2); // ptr2 is freed twice, since the both pointers point to the same memory address

Virtual memory in operating system ³¶

Virtual Memory :
- is a storage allocation scheme in which secondary memory can be addressed as though it were part of the main memory.
- The capacity of virtual memory is limited by the addressing scheme used and the size of both main and secondary memory.
- All memory addresses in the process are logical addresses that are translated by the MMU to physical addresses before they are used (at runtime).
- A process can be divided into segments. Each segment is a contiguous set of logical addresses. These segments are not contiguous in physical memory. using address translation and segments table; the physical address of each segment is determined.
Paging on demand:
- A page got swapped into the main memory on Page Fault. ref
- Page fault service time = the time needed to raise a page fault + the time needed to swap the page into the main memory + the time needed to translate the logical address to the physical address + the time needed to access the physical address.
Swapping:
- Swapping a process out means removing all of its pages from the main memory, or marking them so that they will be removed by the normal page replacement process.
- Suspending a process ensures that it is not runnable while it is swapped out.
Thrashing:
- A process that is swapping in and out of the main memory too frequently is said to be thrashing.
- The swapping in/out overhead is too high, and the process is not able to make progress.
- Causes:
  - A high number of processes running in the system. (too many processes in main memory means too many pages to swap out then swap in).
  - A full main memory. (all frames are full, whenever a page is swapped in, another replacement page must be swapped out).
- Recovery of Thrashing:
  - use a good page replacement algorithm.
  - close some processes.
  - the system must not swap in pages after a threshold number of page faults.
  - temporarily suspend the thrashing processes.
Page replacement algorithm. an algorithm that decides which page must be swapped out in replacement of a page that is swapped in.
Page fault. a page fault occurs when a process tries to access a page that is not in the main memory. The page fault service routine is responsible for swapping that page into the main memory, then the process can continue its execution.
Types of Page replacement algorithms:
- FIFO: simple, swap the first page in the queue out, and put the new page in its place.
- Optimal Page Replacement: the page that will not be used for the longest time is swapped out.
- Least Recently Used (LRU): the page that was least recently used is swapped out.
- Most Recently Used (MRU): the page that was most recently used is swapped out.

How to identify memory leaks ⁴¶

Effects of memory leaks:
- reduces the availability and reliability of the system.
- reduces the performance of the system.
Ways to detect memory leaks:
- Profiling tools.
- Intelligent logging.
When running out of memory, a segmentation fault occurs.

Operating system - memory management ⁵¶

Memory management. is a function of the OS. It is responsible for managing main (primary) and secondary (disk or swap) memory. It keeps track of every single memory location in the system (occupied or free). It also keeps track of the processes that are using the memory and their memory requirements.
Process Address space. is the set of logical addresses of a process.
Types of memory addresses:
- Symbolic addresses: Usually variable names, constants, and labels; they exist in the source code; they are used by the programmer to refer to memory locations. They are not used by the computer.
- Relative addresses: At the compilation time; the compiler transforms the symbolic addresses into relative addresses. They are used by the compiler to refer to memory locations. They are not used by the computer.
- Physical addresses: At the loading time; they are generated by the loader.
virtual and physical addresses are the same during compilation and loading time. But they are different during execution time.
In single partition memory allocation (contiguous):
- Relocation register. is a register that contains the base address of the process. aka. the physical address of the first bit of the process in the main memory.
- Limit register.
  - is a register that contains the size of the process in the main memory. aka. the total number of bits (registers) of the process in the main memory.
  - It can be used to find the physical address of the last bit of the process in the main memory. (physical address of the last bit = relocation register + limit register - 1).
  - sometimes it may hold the physical address of the last bit instead of the size.
Fragmentation:
- Internal Fragmentation: unused space inside a partition that is allocated to a process. Can be reduced by compaction or shuffling memory contents to place all free memory together in one large block.
- External Fragmentation: unused space between partitions. (the total size of the free partitions is not enough to satisfy the memory request of a process). Can be reduced by effectively assigning the smallest partition but large enough for the process.

macOS Monterey memory leak. Solutions you can try! ⁶¶

Solutions for memory leak in MacOs Monterey:
- Put the mouse pointer size to the smallest.
- Restart Finder.
- Limit the use of the Control center.
- Configure monitor display settings to use less contrast and disable unusual scaling.

14. Memory API ⁷¶

Types of memory:
- Stack memory: allocated at compile time. automatically allocated and deallocated.
- Heap memory: allocated at run time. allocations and deallocations are manual. usually holds pointers variables.
malloc can be used as:

 // allocate a memory of size double, and casting the pointer to a double pointer
double *d = (double *) malloc(sizeof(double));
// sizeof(double) got replaced by 8 at `compile time`, that's why we know the size of d before loading the process
malloc(strlen("hello") + 1); // the +1 is necessary for the end-of-string character

free(d); // free the memory allocated for d

Segmentation fault. is a type of error that occurs when a program tries to access a memory location that it is not allowed to access, or that does not exist. aka. no memory is allocated.
buffer overflow. is a type of error that occurs when a program tries to write data outside the memory that has been allocated for it. aka. writing data beyond the buffer’s boundary. aka. not enough memory is allocated.
uninitialized read. memory is allocated by malloc, but no value is assigned to it. aka. no value in that allocated memory yet. It is a good practice to default the value after allocating memory.
memory leak. never free the memory allocated by malloc. aka. the memory is not deallocated although it is no longer needed.
dangling pointer. a pointer that points to a memory location that has been freed. aka. the memory is deallocated, but the pointer is still used after freeing.
double free. free the same memory twice. aka. the memory is deallocated twice.
invalid frees. free a memory that is not allocated by malloc. aka. the memory is not allocated by malloc, but it is freed.
Functions to ask for more memory:
- malloc: allocate memory of a given size.
- mmap: creates an anonymous heap chunk within the process address space.
- calloc: allocate memory of a given size and initialize it to zero.
- realloc: creates a new memory block of a given size and copies the contents of the old block to the new block.

15. Address Translation ⁸¶

physical address = virtual address + base
address translation happens at runtime, that’s why it is called dynamic allocation.
MMU:
- is a hardware component (part of the CPU), it contains the base and limit registers and other components to translate the virtual address to the physical address.

Hardware requirements for memory allocation and address translation¶

Privileged (kernel) vs User mode support. Probably some single-bit register in the CPU indicating the current mode. Processes must not be able to access the MMU registers or modify them (processes run on user mode, which is not privileged enough).
Registers that hold the base and limit values. Probably two registers in the CPU.
Special instructions (methods) to analyze a virtual address generated by the process and decide if it is legal or not.
Special instructions (methods) for the OS to access and modify the MMU registers. Must be in kernel mode. This is needed when moving a process from one memory partition to another.
Special Instructions to handle exceptions. raise interrupts (exceptions), The OS must then handle those exceptions. Some common interrupts:
- Out-of-bounds access: the virtual address is larger than the limit register.
- If the user process tries to access/modify the MMU registers.

OS (software) requirements for memory allocation and address translation¶

Functions to find a suitable memory space for a process address space when the process is being created.
Functions to reclaim memory from terminated processes.
Functions to track busy/free memory space.
Functions to handle base/limit register changes correctly when context switching.
- There are only one MMU registers per CPU, when context switching, the OS must save the old base/limit registers into the PCB of the previous process and load the new base/limit registers of the next process onto the MMU registers.
- If the process is not running, OS may decide to re-arrange memory partitions to reduce fragmentation. So the OS may copy the contents of the process memory to a new memory location and it must update the base/limit registers of the process in the process PCB correctly.
Exception handlers.

16. Segmentation ⁹¶

Started in the 1960s. Sometimes called sparse address space.
Instead of having one base and limit registers per process, we have one base and limit registers per segment which is a logical division of the process address space.
The entire address space does not need to be contiguous. The segments can be scattered in memory. but every single segment must be contiguous.
As a simple approach, we can have three segments per process: code, data (heap), and stack segments. Each of them has its own size and base/bound registers. This will stop wasting memory space between stack and heap segments, and allow each of them to grow independently.
To know which segment the virtual address belongs to, the virtual address is divided into two parts: segment number and offset. The segment number is used to index the segment table to get the base and limit registers of the segment. The offset is added to the base register to get the physical address.
Segment:
- Contiguous logical division of the process logical address space.
- The Segment number is used to index the segment table to get the base and limit registers of the segment.
- The virtual address is divided into two parts: segment number and offset. The offset is added to the base register to get the physical address.
- Segments have a maximum size, that is configured by the OS, and cannot be exceeded. If the segment size is to exceed that constant, a new segment may be generated and added to the segment table.
- A Segment may grow forward or backward, if it grows forward, the offset is added to the base register. If it grows backward, the offset is subtracted from the base register.
- The direction of growth for each segment is saved within the segment table entry for that segment.
- protection bit is also part of the segment table entry. It is used to indicate if the segment is read-only or read-write.
- Setting a segment to read-only (eg. code segment) will prevent the process from modifying the code segment, and make this segment safely sharable between other segments (since no segment can write to it).
OS required support for segmentation:
- Maintaining a Segment table is a data structure that holds the base and limit registers of each segment. It is stored in the process PCB.
- When switching between processes, the OS must save the old segment table into the PCB of the previous process and load the new segment table of the next process.
- Functions to support the segment’s ability to grow forward or backward. The OS must update the base and limit registers of the segment in the segment table correctly.
- Functions to manage free space within the memory.
Example of a segment table entry:

Segment table entry

17. Free Space Management ¹⁰¶

Free List.
- Free space management is done by a data structure called the free list and a process called the allocator.
- It contains a list of (address and size pairs) of free memory blocks.
- When a process requests memory that is smaller than any free block, the allocator splits the free block into two parts: the first part is allocated to the process, and the second part is added to the free list again as a new free block.
- When a process terminates and its memory is freed (reclaimed), the allocator will merge the freed block with any adjacent free blocks. This is called coalescing.
- When allocating memory, the allocator will put a header before the allocated chunk that contains the metadata of the chunk (size, magic number, etc.). This is called overhead. The actual allocated memory starts after the header.
- When freeing memory, the allocator will check the magic number in the header to make sure that the memory is not corrupted. Then picks up the size of the chunk from the header and frees the header and actual memory; then adds them to the free list.
Strategies for managing free space:
- Best Fit. Traverse through all free list entries, and pick the one that is smallest and larger than the requested memory.
- Worst Fit. Traverse through all free list entries, and pick the one that is largest and larger than the requested memory. Then split the largest free block, allocate the requested memory, and add the remaining free block to the free list again.
- First-fit the allocator will search the free list from the beginning and pick the first free block that is large enough to hold the requested memory.
- Next Fit. The allocator will start searching the free list from the last free block that was allocated. This will reduce the number of free list entries that the allocator has to traverse through.
- Segregated lists.
  - If there is a trend of requested memory sizes (eg. 20% of processes request 1KB, 30% request 2KB, 40% request 4KB, and 10% request 8KB), we can have a free list for each size.
  - This will reduce the number of free list entries that the allocator has to traverse through.
  - When a process terminates, the freed memory will be added to the correct free list.
  - We still need a general free list for the remaining memory sizes.
  - Internal and external fragmentation both are minimized.
- Body allocation.
  - When a memory is requested, Find a free block that is large to hold the requested memory and the header.
  - Then divide it by 2 until you reach a size that’s just 1 division away from the requested memory size.
  - Split the free block into 2 parts, allocate the requested memory, and add the remaining free block to the free list again.

References¶

DivyankSinghSikarwar. (2020, January 6). Difference between fine-grained and coarse-grained SIMD architecture. GeeksforGeeks. Retrieved July 8, 2022, from https://www.geeksforgeeks.org/difference-between-fine-grained-and-coarse-grained-simd-architecture/ ↩
5 useful tools to detect memory leaks with examples. (2021, June 12). GoLinuxCloud. https://www.golinuxcloud.com/how-to-find-memory-leaks/#:~:text=A%20memory%20leak%20occurs%20when,deleted%2C%20lost%2C%20or%20overwritten ↩
GeeksforGeeks. (2021, September 21). Virtual memory in operating system. Retrieved July 8, 2022, from https://www.geeksforgeeks.org/virtual-memory-in-operating-system/ ↩
Janani. (2022, April 7). How to identify memory leaks. Atatus. https://www.atatus.com/blog/how-to-identify-memory-leaks/ ↩
Operating system - memory management. (n.d.). tutorialspoint. https://www.tutorialspoint.com/operating_system/os_memory_management.htm ↩
Wong, A. (2021, December 12). macOS monterey memory leak : Solutions you can try! Tech ARP. https://www.techarp.com/software/macos-monterey-memory-leak-fixes/#:~:text=The%20memory%20leak%20quietly%20eats,than%20100%20GB%20of%20memory ↩
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/ Chapter 14 - Memory-API. ↩
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/ Chapter 15 - Address Translation. ↩
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/ Chapter 16 - Segmentation. ↩
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/ Chapter 17 - Free Space Management. ↩

5. Memory Management¶

Notes¶

Difference between fine-grained and coarse-grained SIMD architecture 1¶

Tools to detect memory leaks 2¶

Virtual memory in operating system 3¶

How to identify memory leaks 4¶

Operating system - memory management 5¶

macOS Monterey memory leak. Solutions you can try! 6¶

14. Memory API 7¶

15. Address Translation 8¶

Hardware requirements for memory allocation and address translation¶

OS (software) requirements for memory allocation and address translation¶

16. Segmentation 9¶

17. Free Space Management 10¶

References¶

Difference between fine-grained and coarse-grained SIMD architecture ¹¶

Tools to detect memory leaks ²¶

Virtual memory in operating system ³¶

How to identify memory leaks ⁴¶

Operating system - memory management ⁵¶

macOS Monterey memory leak. Solutions you can try! ⁶¶

14. Memory API ⁷¶

15. Address Translation ⁸¶

16. Segmentation ⁹¶

17. Free Space Management ¹⁰¶