Memory, for a round

What is the difference between the stack and the heap?

The stack holds one frame per function call that has not returned yet: its locals and where to go back to. Taking a frame is moving one pointer, and returning moves it back, so the memory is gone the moment the call ends, whatever still points at it. The heap holds blocks that live until someone frees them, which is why a block can outlive the call that made it, and why somebody has to own it. The heap costs more per allocation because an allocator has to find a free block of the right size.

What happens, step by step, when a program reads a virtual address?

The address splits into a page number and an offset inside the page. The page table is looked up for that page. If it names a physical frame, the frame number and the offset make the physical address and the read goes ahead. If it does not, the hardware raises a page fault; the kernel finds a free frame, fills it from wherever the page lives (a file, the swap area, or zeros for memory never written), records the mapping, and the read is retried. A second read of the same page is a lookup and nothing more.

Why can an allocation fail when there is enough free memory?

Because free memory is not one number. An allocator needs one contiguous block, and the free bytes can be scattered in holes that are each too small: 8 bytes free in four holes of 2 cannot serve a request for 4. Beyond fragmentation, the process can hit its own address-space limit (RLIMIT_AS, which makes mmap and brk fail with ENOMEM), or the kernel can be configured not to overcommit, in which case the total promised to every process is capped. Say which of these you would check first and how.

What should I do when a process is swapping?

First confirm it: vmstat reports si and so, the memory swapped in from disk and out to disk per second, and sustained non-zero values mean pages are going back and forth. Then find whose working set, the pages a process keeps using, outgrew memory, and choose between making it smaller, reading memory in a better order so fewer pages are needed at once, running fewer copies of the process, or adding memory. Adding swap space does not help: it lets more pages wait on disk, and waiting on disk is the problem.

Why does the order you read an array in change how fast it is?

Memory moves between levels in blocks: pages between disk and RAM, and smaller lines between RAM and the processor’s caches. Reading in the order the data is laid out uses every byte of a block before moving on, so each block is fetched once. Reading across the layout touches a new block on nearly every read. On this page a 4 by 4 grid with two frames of memory costs 4 page faults read by rows and 16 read by columns: the same sixteen reads, in another order.