Memory management — theory with your laptop sharing its RAM between gcc, spotify, campus and onedrive (and the 4 KiB I thought were 4000 bytes)

In the IC2 mock exam I got a paging question that looked like a gift: 4 KiB pages, logical address 6700 and a table where page 1 was in frame 9. I did it in my head: “4 KiB is 4000 bytes, so 6700 is page 1 with offset 2700”, and wrote with total confidence 9 · 4000 + 2700 = 38700. Zero points. A KiB is 1024 bytes, so a 4 KiB page holds 4096: 6700 = 1 · 4096 + 2604, and the physical address was 9 · 4096 + 2604 = 39468. I had the page and the frame right, and I still failed because I did not know how big a page is.

Today we are going to understand how the operating system shares RAM between processes without them stepping on each other: contiguous memory (with its base and limit registers and its holes), segmentation and paging, the TLB that keeps all this from being painfully slow, and the problem of how much space the page table takes. Our usual example: your laptop on a study night, with gcc compiling, spotify playing, the campus site open in the browser and onedrive uploading your notes. We come from Concurrency and synchronization, where processes shared variables on purpose; here the OS makes sure they do not share memory by accident. When you finish, practice with the exam-style memory management exercises.

Why memory has to be managed

Main memory (RAM) is a set of cells referenced by a linear address: the first one is 0, the next one 1, and so on up to the last. For a program to run, its code and its data have to be loaded in RAM, at least partly. And the OS kernel lives there too.

With a single program it would be easy. But your laptop is a multitasking system: memory has to be shared between all the processes, and each one has its own memory space (instructions, data and stack).

Look at the picture: gcc, spotify and campus are already in, and onedrive wants to get in. That is where the two problems of memory management come from:

1. Capacity: RAM may not have room for all the processes that want to run.
2. Protection: a process could access, by mistake or on purpose, the area of another process or the area of the OS.

Requirements, goals and key concepts

The OS has three requirements to meet:

Requirement	What it means
Controlling overlap	Processes must not collide in memory, but they can share areas when they want to
Protection	A process must not read another process’s private memory or the OS data
Relocation	Turning the logical addresses of the process into physical addresses

And two groups of goals, which are asked separately in the exam:

• Performance: make the most of main memory, keep several processes loaded without the system collapsing and let a program run without being completely in RAM.
• Protection and sharing: protect the OS from illegal accesses, protect the space of each process and let several processes share memory areas (to communicate or to avoid repeating code, like a library).

Finally, three key concepts that will appear all over this topic:

• Relocation: letting a program live in any area of physical memory.
• Fragmentation: the free holes left behind as memory is allocated and released, which sometimes are useless.
• Access time: memory management mechanisms must not make each access much slower.

From practica.c to memory: address binding

When you write int cont; in practica.c, cont is a symbolic address: a name. At some point that name has to become a number of a RAM cell. When? It depends on the stage of the program’s life cycle where it happens.

The compiler produces the object module, the linker joins it with other objects and libraries into an executable, and the loader puts it in memory. Addresses can be fixed at any of those stages:

When they are fixed	Type	Consequence
At compile time	Absolute addresses	The program only works in a fixed area of RAM: it is not relocatable
At load time	Static relocation	The loader adjusts the addresses once; after that the process cannot move
At run time	Dynamic relocation	The hardware translates on every access; the process can be moved whenever needed

What we want is a compiler that does not generate final addresses, but relocatable ones, resolved later. The later, the more freedom.

Logical addresses, physical addresses and the MMU

Dynamic relocation needs two kinds of address and a translator:

• Logical (or virtual) address: the one the CPU generates when running the program.
• Physical address: the one that reaches the memory chip.
• MMU (memory management unit): the hardware device that translates logical addresses into physical ones.

The simplest MMU is a base register: it is added to every logical address. Imagine gcc is loaded starting at 300 KiB of RAM (300 · 1024 = 307200):

gcc believes its memory starts at 0. When it asks for address 1500, the MMU works out 307200 + 1500 = 308700, and that is what reaches RAM. If tomorrow the OS moves gcc somewhere else, it only has to change the base register: gcc does not even notice.

Protection with base and limit

With the base register we already have relocation. For protection a limit register is added: the size of the area the process can use. In user mode, a circuit checks every address before it goes out to the bus:

If gcc has an area of 210 KiB (215040 bytes), logical address 1500 passes the check (1500 < 215040) and becomes 308700. Address 250000 does not: an exception is raised and the access never reaches memory. You already saw these registers in the hardware topic; here you understand why they exist.

Dynamic linking and swapping

Two more tricks to save memory before getting into allocation techniques.

Dynamic linking (shared libraries). Loading a code module is delayed until it is used for the first time. In Windows they are DLLs (dynamic link libraries) and in Unix and GNU/Linux, shared libraries (libc.so, libm.so). The library is loaded when some process calls one of its functions, and calls go through an indirect table managed by the OS. If ten processes use libc, there is only one copy in memory. And if RAM is very tight, the OS can remove the ones nobody references.

Swapping. If a process has been blocked for a long time, its memory is taken without being useful. The idea: write its image to disk (swap out) and bring it back when it has to resume (swap in).

Historically it was the way to get multiprogramming with very little RAM (in the extreme case, a single process in memory and a swap on every context switch). Its problem is the time spent copying whole images. To soften it, while one process is being swapped the others keep running, and several swap areas on different disks can be used to make several copies at once.

Contiguous memory: MFT and MVT

The simplest way to share RAM: each process takes a single block in one piece. There are two variants:

• MFT (fixed-size partitions): partitions are decided when the OS boots and do not change. A very rigid technique, but very efficient.
• MVT (variable-size partitions): the evolution of MFT. Free space is handed out to measure, with a dynamic list of holes. More flexible, but more complex.

With MVT, the OS keeps two structures:

• A table of reserved areas: for each area, start address, size and the process it belongs to.
• A list of free holes: for each hole, start address and size.

When a process asks for memory, it asks for a specific size. The OS looks for a hole that is big enough, gives it to the process and whatever is left goes back to the list of holes. Protection is still the same base and limit pair.

First, best and worst fit

When several holes would do, which one is given? There are three allocation policies:

• First fit: walk the list and give the first hole greater than or equal to the request.
• Best fit: give the hole that leaves the smallest remainder. Risk: it keeps leaving remainders so small they are useless.
• Worst fit: always give the biggest hole.

On the laptop there are five free holes of 120, 480, 210, 300 and 560 KiB, and, in this order, gcc (210), spotify (430), campus (110) and onedrive (470) arrive. The simulator in Check it with Python applies the three policies to the same data:

Follow the first-fit row: gcc goes into the first hole where it fits, the 480 one (270 left). spotify (430) does not fit in 270, nor 210, nor 300, and goes to the 560 one. campus, to the 120 one. When onedrive (470) arrives, the biggest hole left is 300: no room. Worst fit fails in the same way, because gcc breaks the 560 hole. Only best fit places all four: gcc goes exactly into the 210 one and leaves the 560 hole untouched for onedrive.

Policy	Looks for	Advantage	Drawback
First fit	The first one that fits	Fast: it does not walk the whole list	It keeps chopping up the first holes
Best fit	The one that leaves the least	Keeps the big holes	Walks the whole list; leaves tiny remainders
Worst fit	The biggest	Leaves big remainders (useful, in theory)	Breaks the big holes very early

External fragmentation, internal fragmentation and compaction

Look at how memory ends up after first fit:

There are 920 KiB free and onedrive only asks for 470, but they are split into pieces of 10, 270, 210, 300 and 130. None of them is enough. That is external fragmentation: free memory that exists but is not in one piece.

One solution is compaction: moving processes to gather all the holes into one. It has two drawbacks:

• It is only possible with dynamic relocation, because processes change their physical address (it is enough to change their base register).
• It takes a lot of time: whole blocks of memory have to be copied.

The other solution is to stop requiring the process to be in one piece: split it. That is non-contiguous memory, with its two techniques, segmentation and paging.

Segmentation

Idea: break the process into several segments, which are its logical pieces: code, data, stack… With the right hardware, each segment can go to a different area of RAM.

In the picture, gcc has three segments: code (3200 bytes), data (1500) and stack (2000). In RAM they are apart and in another order, and the segment table stores where each one starts (base) and how big it is (limit). The work is split like this:

• The CPU works with two-part addresses: ⟨segment, offset⟩.
• The compiler identifies the segments of the program and generates segmented addresses.
• The OS loader places each segment in a memory area.
• The MMU translates ⟨segment, offset⟩ into linear addresses with the segment table, which is a table of base and limit registers.

Translating a segmented address

The translation is the base and limit one, but with a pair per segment:

1. The segment number is used to find its row in the table.
2. Check that the offset is smaller than the limit. If not, exception.
3. Physical = base + offset.

⟨1, 600⟩ is the data segment (base 4000, limit 1500): 600 < 1500, physical 4000 + 600 = 4600. ⟨2, 2500⟩ is the stack (limit 2000): 2500 ≥ 2000, exception.

Segmentation
Advantages	Reduces fragmentation; lets processes share segments (a DLL can be a segment in the tables of several processes); lets segments be protected (read only, execute only for code segments)
Drawbacks	The compiler and the linker work with a two-dimensional space; it needs hardware; each access is slower (the table must be checked); it does not remove fragmentation completely; its effectiveness depends on how the process is split

Paging

Paging is the technique that gets rid of external fragmentation for good. The idea:

• The program is split into fixed-size pages (for example, 4 KiB).
• RAM is divided into page frames of the same size.
• Each page can go to any free frame, whether or not they are next to each other.
• The MMU links each logical page with its physical frame using the process’s page table.

The four pages of gcc are in frames 5, 9, 2 and 12: out of order and separated by frames of other processes. It does not matter. Since pages and frames have the same size, any free frame is good for any page: there can no longer be a free hole that is too small.

Managing free space becomes very simple: it is enough to know which frames are free. The OS keeps it in a page frame table, which can be implemented as a bitmap (one bit per frame: free or taken) or as a list of free frames. When a four-page process arrives, four frames are taken from the list and written into its table.

Splitting the address into page and offset

Every logical address is split into a page number and an offset inside the page. If the page is 2^n bytes, the n low bits are the offset and the rest, the page. On the laptop we use 16-bit logical addresses and 4 KiB = 2^12 byte pages: 4 page bits and 12 offset bits.

To translate 0x1A2C:

1. In binary, 0001 1010 0010 1100. The top 4 bits, 0001, are page 1. The bottom 12, 1010 0010 1100 = 2604, the offset.
2. The page table says page 1 is in frame 9 (1001).
3. The 4 page bits are replaced by the frame bits, and the offset is copied as is: 1001 1010 0010 1100 = 0x9A2C.

In decimal it is the same calculation: 0x1A2C = 6700 = 1 · 4096 + 2604, and the physical address is 9 · 4096 + 2604 = 39468. The formulas are:

• page = logical address // page size
• offset = logical address % page size
• physical = frame · page size + offset

Internal fragmentation in paging

Paging is not perfect. If gcc takes 13000 bytes, it needs 4 pages of 4 KiB (16384 bytes), and the last one is almost empty:

4 · 4096 − 13000 = 3384 bytes allocated that nobody uses. Since the waste is inside the page, it is internal fragmentation. With 1 KiB pages, gcc would take 13 pages and only lose 13 · 1024 − 13000 = 312 bytes, but its table would have 13 entries instead of 4.

Page size	Internal fragmentation	Page table
Small	Lower (less is lost in the last page)	Bigger (more pages, more entries)
Big	Higher	Smaller

The page table in RAM: two accesses for every one

Where is the page table stored? In old machines such as the DEC PDP-11 (16-bit addresses, 8 KiB = 2^13 pages), the address had 3 page bits and the table, with 2^3 = 8 entries, fitted in fast CPU registers. Today tables are huge (a 20 MB process with 1 KiB pages needs 20K entries), so the table lives in main memory, and the CPU has two registers to find it:

• PTBR (page-table base register), in Spanish RBTP: where the table starts in RAM.
• PTLR (page-table length register), in Spanish RLTP: how many entries it has.

The problem is obvious: to read one piece of data, two RAM accesses are needed, one to the page table and one to the data. Every program would run twice as slow. The solution is the TLB.

The TLB: a shortcut for translation

The TLB (Translation Lookaside Buffer) is a small associative cache inside the processor that stores a few entries of the page table. Looking it up is almost as fast as reading a CPU register. It is there to speed up translation and avoid accesses to the page table.

How does it work?

• It stores key/value pairs ⟨logical page, physical frame⟩.
• To translate page P, P is searched in all the TLB entries at once (that is why it is associative).
• TLB hit: P is there; its frame is obtained and there is no need to look at the page table.
• TLB miss: P is not there; the page table in RAM is read and the ⟨P, frame⟩ pair is stored in the TLB for next time.

With a 5 ns TLB and a 60 ns RAM, a hit costs 5 + 60 = 65 ns (the TLB and the data) and a miss, 5 + 60 + 60 = 125 ns (the TLB, the table and the data).

The TLB access by access

The simulator in Check it with Python translates eleven gcc accesses with a TLB of only 2 entries. When it is full and there is a miss, the least recently used entry leaves:

Follow the “TLB after” column:

Access	What happens
0x0004	Miss: the TLB is empty. (0→5) goes in
0x0FF0	Hit: it is page 0 too
0x1A2C	Miss: (1→9) goes in; there are now two entries
0x0100	Hit on page 0, which becomes the most recent
0x3000	Miss with the TLB full: (1→9), the least used, leaves and (3→12) goes in
0x5008	Page 5 is not in the table: exception, it is not translated

In the end, 7 hits out of 10 valid accesses: 70 %. Page 0 is used so often that it never leaves the TLB. That is locality: programs use the same few pages over and over again, and that is why a tiny TLB hits so often.

Effective access time

With a hit rate h, the mean effective memory access time is:

t = h · (TLB + RAM) + (1 − h) · (TLB + RAM + RAM)

The class example: 5 ns TLB, 60 ns RAM and 90 % hits:

t = 0.9 · (5 + 60) + 0.1 · (5 + 60 + 60) = 58.5 + 12.5 = 71 ns

Only 11 ns more than a direct RAM access, compared with the 120 ns it would cost without a TLB. In our simulator, at 70 %, it comes to 0.7 · 65 + 0.3 · 125 = 45.5 + 37.5 = 83 ns.

Real processors hit between 80 % and 98 % of the time, with very small TLBs: 22 entries in the Motorola 68030, 32 in the Intel 80486 and between 4 and 64 in Intel Skylake (2015).

Special TLB situations

• Miss with the TLB full: an entry has to be replaced. Which one? The oldest, the least used, a random one… In our simulator, the least recently used.
• Context switch: gcc’s translations are no good for spotify (its page 0 is in another frame). The TLB has to be flushed or loaded with the contents of the process entering the CPU.

Protection in paging

Paging also protects:

• Protection bits in every table entry: read, write and execute. That way code can be read and execute only, and data, read and write.
• Protection against accesses outside the logical space of the process.

For the second one there are three possible measures:

• The PTLR: if the page number is not smaller than the table length, exception.
• The valid bit: entries that do not belong to pages of the process are marked as invalid.
• The inverted page table, where only valid pages appear.

That is what happened with 0x5008 in the trace: page 5 does not belong to gcc and the translation ends in an exception.

The size of the page table

Let’s do the maths with a 32-bit architecture and 4 KiB pages:

12 offset bits, so 20 page bits are left: 2^20 = 1,048,576 entries. If each entry takes 4 bytes, the table of a single process takes 4 MiB. With 48 or 64-bit addresses it is much worse.

The “easy” solution is a bigger page: with 4 MiB pages there would be 10 page bits and a 4 KiB table… at the cost of skyrocketing internal fragmentation. The serious solutions are three: hierarchical paging, inverted page table and hashed page table.

Hierarchical paging

The page table itself is paged, and a hierarchy of levels is formed. In 32-bit Intel x86, the address is split into 10 + 10 + 12 bits:

• p1 (10 bits) indexes the outer table (primary), which says where the inner table is.
• p2 (10 bits) indexes that inner table (secondary), which gives the frame.
• d (12 bits) is the offset inside the frame.

Where is the saving? Only the inner tables the process really uses need to be kept. The price: without a TLB hit, three accesses to RAM are needed (two tables and the data), so the TLB becomes even more necessary. In general, with a hierarchy of n levels it takes n + 1 accesses.

64-bit x86 uses up to four levels (page map level 4, page directory pointer table, page directory and page table, 9 bits each, plus 12 offset bits; bits 63 to 48 are unused) and 4 KiB, 2 MiB or 1 GiB pages.

Inverted page table

It turns the idea around: instead of one table per process with one entry per page, there is a single global table with one entry per real frame of RAM. Entry K says which logical page is in frame K and which process (pid) it belongs to.

The CPU issues ⟨pid, page, offset⟩. The ⟨pid, page⟩ pair is searched in the table, and the position where it appears is the frame. In the picture, ⟨412, 1⟩ (gcc, page 1) is at position 9: the physical address is ⟨9, 0xA2C⟩, the same 0x9A2C as before.

• Advantage: a huge memory saving, because the size of the table depends on RAM, not on the number of processes.
• Drawback: searching the table is very slow. TLB hits are relied on, or it is implemented as a hash table. It has been used in PowerPC, UltraSPARC and IA-64.

Contiguous, segmentation and paging, side by side

	Contiguous (MVT)	Segmentation	Paging
Pieces	One	Logical segments, variable size	Fixed-size pages
Logical address	A number	⟨segment, offset⟩	⟨page, offset⟩
Translation	base + logical (if < limit)	base[s] + d (if d < limit[s])	frame[p] · size + d
External fragmentation	Yes	Less, but yes	No
Internal fragmentation	No	No	Yes, in the last page
Visible to the programmer?	No	Yes: they are the parts of their program	No

Common mistakes

Check it with Python

Two short simulators with fixed data, run once. You can copy them and run them with python3.

Simulator 1: translation with paging and a TLB

gcc has the four pages of the table in the picture (0 → 5, 1 → 9, 2 → 2, 3 → 12), pages are 4 KiB and the TLB has 2 entries. The simulator translates eleven addresses, counts the hits and works out the mean time in two ways: measuring access by access and with the formula.

# Address translation with paging and a 2-entry TLB (fixed data)
PAGE = 4096                         # 4 KiB pages = 2**12 → 12 offset bits
TABLE = {0: 5, 1: 9, 2: 2, 3: 12}   # page table of gcc: page → frame
T_TLB, T_RAM = 5, 60                # ns: looking at the TLB and one RAM access
accesses = [0x0004, 0x0FF0, 0x1A2C, 0x1004, 0x0100, 0x3000, 0x3FFC, 0x0200, 0x5008, 0x3010, 0x0008]
tlb = []                            # (page, frame) pairs; the first is the least used
hits = valid = total_ns = 0
print(f'{"logical":<8}  {"page":>4}  {"offset":>6}   {"TLB":<9}  {"frame":>5}  {"physical":>8}  {"ns":>4}')
for laddr in accesses:
    p, d = divmod(laddr, PAGE)      # p = 4 high bits, d = 12 low bits
    frame = next((m for (q, m) in tlb if q == p), None)
    if frame is not None:           # hit: the TLB already knew the frame
        tlb.remove((p, frame)); tlb.append((p, frame))
        status, ns = 'hit', T_TLB + T_RAM               # TLB + the data
        hits += 1
    elif p in TABLE:                # miss: the page table in RAM must be read
        frame = TABLE[p]
        status, ns = 'miss', T_TLB + T_RAM + T_RAM      # TLB + table + the data
        if len(tlb) == 2:
            tlb.pop(0)              # TLB full: the least used leaves (LRU)
        tlb.append((p, frame))
    else:                           # the page is not in the table: illegal access
        print(f'0x{laddr:04X}    {p:>4}  {d:>6}   {"exception":<9}  {"-":>5}  {"-":>8}  {"-":>4}')
        continue
    paddr = frame * PAGE + d        # the offset is copied as is
    valid += 1; total_ns += ns
    print(f'0x{laddr:04X}    {p:>4}  {d:>6}   {status:<9}  {frame:>5}  {"0x%04X" % paddr:>8}  {ns:>4}')
h = hits / valid
print(f'TLB hits: {hits}/{valid} = {h:.0%}')
print(f'measured mean time: {total_ns / valid:.1f} ns')
print(f'formula: {h:.2f}·({T_TLB}+{T_RAM}) + {1 - h:.2f}·({T_TLB}+{T_RAM}+{T_RAM}) = {h * 65 + (1 - h) * 125:.1f} ns')

This is its real output:

logical   page  offset   TLB        frame  physical    ns
0x0004       0       4   miss           5    0x5004   125
0x0FF0       0    4080   hit            5    0x5FF0    65
0x1A2C       1    2604   miss           9    0x9A2C   125
0x1004       1       4   hit            9    0x9004    65
0x0100       0     256   hit            5    0x5100    65
0x3000       3       0   miss          12    0xC000   125
0x3FFC       3    4092   hit           12    0xCFFC    65
0x0200       0     512   hit            5    0x5200    65
0x5008       5       8   exception      -         -     -
0x3010       3      16   hit           12    0xC010    65
0x0008       0       8   hit            5    0x5008    65
TLB hits: 7/10 = 70%
measured mean time: 83.0 ns
formula: 0.70·(5+60) + 0.30·(5+60+60) = 83.0 ns

The important pieces:

• divmod(laddr, PAGE) does the integer division and the remainder at once: the page and the offset.
• The list tlb stores (page, frame) pairs ordered from least to most used. On a hit, the pair is removed and appended again at the end (it becomes the most recent); on a miss with the TLB full, tlb.pop(0) removes the first one, the least used. It is a TLB with LRU replacement.
• frame * PAGE + d is the formula of the physical address: the offset is untouched.
• Addresses are printed in hexadecimal with 0x{laddr:04X} so that the trick of the last three digits shows.

What to look at:

1. In every row, the last three hexadecimal digits of the logical and the physical address are the same: 0x1A2C → 0x9A2C, 0x3FFC → 0xCFFC. Only the first one changes (the page for the frame; 12 is C).
2. Misses cost 125 ns and hits 65: a miss is almost twice as expensive.
3. At 0x3000 the TLB is full with pages 1 and 0. Page 1 leaves because page 0 has just been used at 0x0100. If page 1 were requested again afterwards, it would miss.
4. 0x5008 is not translated: page 5 is not in TABLE, so there is no frame and no time, and it does not count for the mean.
5. The measured mean (83 ns) and the formula agree, because the formula is precisely the weighted mean of 65 and 125 with the hit rate (0.70).

Simulator 2: first, best and worst fit

The five holes and four requests of the policies picture. The function choose filters the holes that fit and picks one according to the policy.

# Contiguous allocation (MVT): first, best and worst fit with the same holes (fixed data)
HOLES = [(100, 120), (300, 480), (900, 210), (1200, 300), (1600, 560)]   # (start, size) in KiB
REQUESTS = [('gcc', 210), ('spotify', 430), ('campus', 110), ('onedrive', 470)]


def choose(holes, size, policy):
    valid = [h for h in holes if h[1] >= size]             # only the ones that fit are useful
    if not valid:
        return None
    if policy == 'first':
        return valid[0]                                    # the first one in the list
    if policy == 'best':
        return min(valid, key=lambda h: h[1])              # the one that leaves the least
    return max(valid, key=lambda h: h[1])                  # worst: the biggest


for policy in ('first', 'best', 'worst'):
    holes = list(HOLES)                                    # copy: every policy starts the same
    print(f'== {policy} fit')
    for name, size in REQUESTS:
        h = choose(holes, size, policy)
        if h is None:
            free = sum(t for _, t in holes)
            print(f'  {name:<8} {size:>3} KiB → no room (free {free} KiB, largest hole {max(t for _, t in holes)})')
            continue
        i = holes.index(h)
        holes[i] = (h[0] + size, h[1] - size)              # what is left is still a hole
        print(f'  {name:<8} {size:>3} KiB → at {h[0]:>4} (hole of {h[1]}, left {h[1] - size})')
    holes = [h for h in holes if h[1] > 0]
    print('  holes:', ' '.join(str(t) for _, t in holes))

Its real output:

== first fit
  gcc      210 KiB → at  300 (hole of 480, left 270)
  spotify  430 KiB → at 1600 (hole of 560, left 130)
  campus   110 KiB → at  100 (hole of 120, left 10)
  onedrive 470 KiB → no room (free 920 KiB, largest hole 300)
  holes: 10 270 210 300 130
== best fit
  gcc      210 KiB → at  900 (hole of 210, left 0)
  spotify  430 KiB → at  300 (hole of 480, left 50)
  campus   110 KiB → at  100 (hole of 120, left 10)
  onedrive 470 KiB → at 1600 (hole of 560, left 90)
  holes: 10 50 300 90
== worst fit
  gcc      210 KiB → at 1600 (hole of 560, left 350)
  spotify  430 KiB → at  300 (hole of 480, left 50)
  campus   110 KiB → at 1810 (hole of 350, left 240)
  onedrive 470 KiB → no room (free 920 KiB, largest hole 300)
  holes: 120 50 210 300 240

What matters:

• valid keeps only the holes that are big enough; if none is left, the request fails.
• min(..., key=lambda h: h[1]) and max(...) choose by size, which is the second element of each (start, size) pair.
• holes[i] = (h[0] + size, h[1] - size): what is left of the hole starts where the allocated part ends. If what is left is 0, the hole disappears at the end.
• list(HOLES) makes a copy so that the three policies start with the same holes.

What to look at:

1. First fit puts gcc in the 480 hole (the first one where it fits) even though the 210 one was exactly its size.
2. Best fit puts gcc in the 210 one with 0 left: it uses the whole hole.
3. When onedrive does not fit, there are 920 KiB free and the biggest hole is 300: textbook external fragmentation.
4. Worst fit gives the 560 hole to gcc and leaves it at 350; then campus eats part of that remainder. In the end there is no big hole left.

Summary

Concept	In one sentence
Logical / physical address	The one the CPU generates / the one that reaches RAM
MMU	Hardware that translates logical into physical on every access
Static / dynamic relocation	Done by the loader at load time / by the hardware at run time
Base and limit	Physical = base + logical, only if logical < limit; otherwise, exception
MFT / MVT	Partitions fixed at boot / variable with a list of holes
First, best, worst fit	First that fits / the one that leaves the least / the biggest
External / internal fragmentation	Scattered free holes / unused space inside what was allocated
Segmentation	⟨s, d⟩ and a segment table with base and limit
Paging	⟨p, d⟩, pages and frames of the same size, page table
TLB	Cache of ⟨page, frame⟩; t = h·(T+M) + (1−h)·(T+2M)
Table size	2^page bits × entry size
Hierarchical / inverted	The table is paged (levels + 1 accesses) / one entry per frame for the whole system

Three ideas to take away:

1. The MMU translates every access: with base and limit, with a segment table or with a page table, it always checks first and adds (or replaces) second.
2. Splitting the process attacks external fragmentation: segmentation reduces it and paging removes it, at the cost of some internal fragmentation.
3. Paging would double the access time without the TLB, and with big addresses its table would be huge without levels or an inverted table.

Now it is time to prove it. First, in the memory management guided practice we translate addresses and work out the time with a TLB step by step; then, in the exam-style memory management exercises you have a test with every format, five calculations (translating addresses, effective time, fits, table size and segmentation) and open questions. And in the next topic we will take the missing step: virtual memory, which lets processes run even if they do not fit completely in RAM.

Next step: practiceMemory management — practice with guided problems step by step: translating with paging, segmentation with limits, the TLB and an exercise in the exam format (and the physical address I gave for a segment that did not exist)

Did this article help you? Here is how you can support SergioLearns →