Address space

Why this matters

Run the same program twice and look at the address of one global variable in both processes. It turns out to be the same, even though these are obviously different cells in memory.

The questions get harder. How can the compiler hard-code a specific address at all if it does not know where the program will be loaded? And why does a process that touches someone else’s address get SIGSEGV instead of reading someone else’s data?

All three have one answer: the address a program works with is not an address in the memory chip.

Prerequisites. The MMU and execution modes (module 2), sections of the address space (module 6).

Two addresses

The process sees and uses the logical address, and the CPU forms it while executing an instruction. The memory controller receives the physical one.

Between them sits the MMU, the memory management unit. This is hardware that converts one address into the other on every memory access, billions of times per second. Neither the kernel nor the compiler takes part in this.

Everything else follows from that. Two processes can have the same logical address mapped to different physical ones, and so they do not see each other. A logical address with no mapping causes a hardware exception, which is where SIGSEGV comes from. And the kernel can move a process in memory just by changing the mapping, without the process even noticing.

When an address becomes final

Addresses can be bound at three different stages. At compile time, and then the program is tied to a specific location forever: that is how .COM worked in MS-DOS. At load time, when addresses are fixed once at startup. Or at run time, when the address is translated anew every time.

Only the third option needs hardware support from the MMU, but it gives you everything at once: protection, relocation, and virtual memory.

The simplest MMU: base and limit

Historically the first hardware solution was a pair of registers. The base register held the physical address where the process’s region started, the limit register held its size.

On every access the hardware did two things:

if logical_address >= limit  →  hardware exception
physical_address = base + logical_address

One check and one addition are enough to get two things at once: protection, because the process cannot reach past its limit, and relocatability, because changing the base is enough to move the process without it noticing anything. The registers themselves are accessible only in kernel mode, so a process cannot raise its own limit.

The scheme has one limitation, but a serious one: all of the process’s memory has to lie in one contiguous piece.

Allocation in contiguous regions

If every process needs a contiguous region, the kernel has to find one somewhere. Historically two approaches were tried.

Fixed-size partitions divide memory into N regions in advance. Simple, but a 3 MB process in an 8 MB partition wastes five megabytes. Such losses inside an allocated region are called internal fragmentation.

Variable-size partitions allocate a region exactly the size of the request. Internal fragmentation disappears, but a different kind appears.

External fragmentation

The nastiest property of external fragmentation: the system refuses memory while having plenty of it. There is enough free memory; what is missing is a contiguous region.

Processes come and go, leaving holes of various sizes behind. After a while there is a lot of free memory, but all of it is scattered in pieces smaller than any meaningful request.

When there are several holes, you have to decide which one gets the new process. There are three classic strategies:

Strategy	Rule	In practice
First fit	the first hole it fits into	fastest, decent result
Best fit	the smallest sufficient one	leaves many tiny unusable holes
Worst fit	the largest one	the worst of the three by every measure

The name “best fit” sounds convincing, but it brings no gain: by cutting from the smallest sufficient hole, this strategy leaves a remainder that is useless for anything, every time. In how densely they fill memory, it and first fit come out about even, but first fit is noticeably faster, because it does not have to scan the whole list of holes each time.

There is also compaction: shift all processes up against each other and gather the free space into one region. It works, but it costs copying all of the used memory, and it is possible only when addresses are bound at run time. For a system with gigabytes of memory this is unacceptably expensive.

The conclusion that starts the next module

External fragmentation is not caused by a bad algorithm: it is inevitable as long as the contiguity requirement holds.

So the requirement itself has to go: let a process’s memory be scattered across physical memory, and keep the address space contiguous only in appearance. The mechanism that does this is called paging.

How it actually works in Linux

cat /proc/self/maps

The logical address mappings of the current process. On the left are ranges of logical addresses, then the access permissions, and on the right what stands behind them. There are no physical addresses here at all: they are not available to the process.

sh -c 'cat /proc/self/maps | head -3'; sh -c 'cat /proc/self/maps | head -3'

Two runs of the same program give different base addresses because of ASLR (module 16). Without it the addresses would match.

cat /proc/meminfo | grep -E '^(MemTotal|MemFree|MemAvailable|Mapped)'

MemTotal is physical memory. The sum of the logical address spaces of all processes can be many times larger: an address space is not memory.

ps -eo pid,vsz,rss,comm --sort=-vsz | head -5

VSZ shows the size of the logical address space, RSS how much of it actually resides in physical memory. A VSZ tens of times larger than RSS is normal; there is no leak here.

Common misconceptions

“The address in a pointer is a location in the memory chip.” It is a logical address. What corresponds to it physically is known only to the MMU, and the answer may well change between two accesses.

“VSZ shows how much memory a process uses.” What it shows is the size of the address space, including parts that will never be used. Memory consumption is shown by RSS, and even that is inflated by shared libraries.

“Internal and external fragmentation are the same thing.” Internal is an unused remainder inside an allocated region. External is free memory between regions, too small to be used.

“Best fit is the best strategy.” The name is misleading: in how it fills memory it is no better than first fit, and it takes more time, because it scans the whole list of holes every time.

“Fragmentation can be beaten with a better algorithm.” Not as long as a process’s memory has to be contiguous. It was beaten by dropping the contiguity requirement itself.

Check yourself

1. Two copies of the same program show the same address for a global variable. Why do they not interfere with each other?

The kernel copies the variable between processesIt is a logical address; the MMU maps it to different physical addresses for each processThe variable is stored on diskThe second copy gets its own copy only on write

2. There is 180 MB of free memory in three regions of 60, 50 and 70. A process asks for 140 MB. What happens?

The process gets the memory; the kernel puts the regions togetherPlacement is impossible without compaction: this is external fragmentationThe process gets 70 MB and runsThe swap file kicks in

3. What does the hardware do on every access in the base-and-limit scheme?

Looks the address up in the page tableCompares the logical address with the limit and adds the baseAsks the kernel for permissionChecks file access permissions

4. A 3 MB process is placed in a fixed-size 8 MB partition. What are the lost 5 MB called?

External fragmentationInternal fragmentationCompactionA memory leak

5. A process has a VSZ of 12 GB and an RSS of 200 MB, with 8 GB of physical memory. Is this a problem?

Yes, the process has exceeded the amount of memoryNo: VSZ is the size of the address space, not memory consumed; 200 MB is actually in useYes, swap needs to be increasedNo, but the process is bound to crash soon

6. Why does the best fit strategy lose to first fit in practice?

It is slower and leaves many small unusable remaindersIt does not guarantee memory protectionIt works only with fixed-size partitionsIt requires compaction after every allocation

Lab

A4 — your own memory allocator. An implementation of malloc on top of mmap with first fit and best fit strategies, with fragmentation measured on a real request profile. The difference between theory and the measured result here is usually surprising.

Sources

• OSTEP: Address Spaces, Address Translation, Free Space Management
• Silberschatz, Operating System Concepts, chapter 9
• man 5 proc — the section on /proc/[pid]/maps and smaps