CST 334 Week 3 (27/100)

 Josh Goldberg

CST 334-40_2262

Mar 24, 2026

This week was a study on memory management. We covered address spaces, the C memory API, address translation with base & bounds, segmentation, free space management, and paging. 

There are three address spaces a program cares about: code, heap, and stack. The code holds executable instructions, heap has dynamically allocated memory, and the stack has local variables and other things that are automatically generated by the compiler and used in execution. Between the heap and the stack is free space, and the two grow towards each other. To solve the problems of address generation, protection, and capacity, the OS gives virtual memory to programs. It allows for many processes to use RAM without conflict. Programs are unaware that the addresses they use are virtual. The virtualization must be fast, and virtual memory must be isolated per process. 

The main API functions are malloc() and free(). malloc() makes an allocation on the heap. Free releases the allocation. They must match 1:1. Double free, or allocating without freeing, leads to problems. There are other functions like calloc() that zeroes the allocation and realloc() that resizes an allocation.

Base and bounds is one way to translate physical addresses to virtual addresses. The physical address of memory is the virtual address plus a base. The bounds is the size of the process’s virtual address space. All processes have the same sized address space, and each space is contiguous in physical memory, and each space fits within physical memory. The base and bounds are set in registers in the MMU and are privileged. Any out of bounds access wlll trap. This method is very fast because only one addition instruction is required. The OS must find free physical memory, set the base and bounds registers, manage context switches by saving a process’s base and bounds, reclaim physical memory after process ends, and manage access traps. The limitation of base and bounds is that there can be a lot of wasted memory.

Segmentation uses a separate base and bounds for each address space: code, heap, and stack. This reduces the waste. A virtual address offset now has two bits to identify the segment and the remainder for the offset. To check if an address is valid, now the segment must be taken into account. Another benefit is that we can restrict operations per segment to prevent writing to the code segment and prevent execution of heap and stack, which are important for security. We can also optimize uses if there are multiple instances of the same program running because they can share the code segment since it is protected from modification.

To pick where to place segments we use a free space management strategy. The fastest is first fit, which finds the first available chunk that is big enough for the segment. Best fit finds the smallest chunk that is big enough. Worst fit finds the largest available chunk. Depending on the strategy, the list of free chunks can be sorted differently to optimize lookup. There are downsides to each strategy: frist fit leaves small fragments at the front of the list, best fit creates a lot of very small unusable fragments, and worst fit leave a lot of large fragments.

Paging divides all memory into fixed size chunks. Virtual chunks are pages and physical chunks are page frames, and they are the same size. This makes free space management easier and better manages fragmentation. A virtual address has a virtual page number (VPN) and an offset. A Frame has a Physical Frame Number (PFN) and an offset. To translate a virtual address to a physical one, split the virtual address into VPN and offset. The VPN is the index to the page table and is used to lookup the PFN. PFN + offset = physical address. The Page Table Entry (PTE) has some metadata to help with access patterns, protection, and caching strategies to speed up the lookups.

Abstraction is one of the key duties of the operating system. This week was all about abstracting the physical memory for users. There are simple ways and less simple ways. Depending on the purpose and use of the operating system might determine what strategy is used. Paging is used in all modern operating systems and it seems to work mostly fine, but we still see page faults. Even with these clever and simple techniques, there are still real challenges in making abstractions reliable.