Memory 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)

In an IC2 mock exam I had a segment table and three logical addresses to translate. The first two came out fine. The third was ⟨1, 400⟩, with segment 1 at base 6300 and limit 400, and I added without thinking: 6300 + 400 = 6700. When it was marked, the answer said «exception». The segment has 400 bytes, from offset 0 to 399, so 400 is already outside. My physical address pointed at the first byte of another segment, exactly what the MMU must prevent. Since then, before adding anything, I check.

This is the guided practice for memory management. In the memory management theory you saw the MMU, contiguous memory, segmentation, paging and the TLB, with gcc spread over the laptop’s frames. Here we solve four problems step by step, as in the written part and the test calculations: translating addresses with paging (in decimal and hexadecimal), translating with segmentation checking the limit, computing the effective access time with a TLB and an exercise in the exam format (page table size and the three fits). Afterwards, in the memory management exercises, it is your turn.

Before you start

It helps to be clear about:

• That 1 KiB is 1024 bytes and that page sizes are powers of 2.
• Paging: logical address = ⟨page, offset⟩, with page = address / page size (integer division) and offset = the remainder; physical = frame × size + offset.
• Segmentation: ⟨segment, offset⟩; physical = base + offset only if offset < limit.
• The TLB formula: $t = h\,(T + M) + (1 – h)\,(T + 2M)$.

If any of them sounds shaky, go over the theory before carrying on.

How to solve a memory problem

The four problems follow the same four-step method:

1. Convert the sizes to bytes (or to powers of 2) and note the base each address is in.
2. Split the address into its two fields: page and offset, or segment and offset.
3. Check and translate: in segmentation, the limit first; in paging, that the page exists in the table. Then replace or add.
4. Check the result: that the physical address falls inside the corresponding frame or segment, and that the offset has not changed.

Problem 1: translating with paging

Statement. a) With 2 KiB pages, translate the logical address 5000 with this page table: page 0 → frame 3, page 1 → frame 11, page 2 → frame 7, page 3 → frame 4. b) With 4 KiB pages, translate 0x1A3C knowing that page 0 is in frame 0x2 and page 1 in frame 0x5.

The idea

The MMU does not add anything to the logical address: it splits it in two. The offset inside the page goes through as it is; only the page number is replaced by the frame number. In decimal you split by dividing by the page size; in hexadecimal, if the page is $2^{12}$, by cutting off the last three digits.

Step by step

a) 2 KiB = 2048 bytes.

Page 2 is in frame 7:

b) 4 KiB = $2^{12}$ bytes: the 12 low bits (three hex digits) are the offset.

Page 1 is in frame 0x5, so the physical address is the frame followed by the same offset: 0x5A3C. No multiplication: in hexadecimal, $5 \cdot \mathrm{0x1000} + \mathrm{0xA3C} = \mathrm{0x5A3C}$.

Check

• a) The offset must be smaller than the page size: 904 < 2048. And the physical address falls inside frame 7, which goes from 14336 to 16383.
• b) The last three digits of the physical address are the same as those of the logical one (A3C): the offset does not change.
• In decimal, 0x1A3C = 6716 = 1 · 4096 + 2620, and 0x5A3C = 23100 = 5 · 4096 + 2620: it adds up.

Questions you might ask

Why is the base not added, as in segmentation? Because pages and frames have the same size and are aligned: it is enough to swap the page number for the frame number. That is why paging is so cheap in hardware.

What if the page is not in the table (or its valid bit is 0)? The MMU raises an exception. With virtual memory, it is a page fault and the operating system brings it from disk (you see it in the next topic).

How many bits does the offset have with 2 KiB pages? 11, because $2^{11} = 2048$. In a 16-bit address that would leave 5 for the page: 32 pages.

Why did the theory’s 4 KiB example give an offset of 2604? Because 4 KiB is 4096 bytes, not 4000. Using powers of 10 instead of powers of 2 is the most expensive mistake in this topic.

Try it yourself

• Translate the logical addresses 2047 and 2048 of part a). Why do they land in such different frames if they only differ by 1?
• With 4 KiB pages, what page and offset does 0x3FFF have?

Problem 2: segmentation with limits

Statement. A process’s segment table is:

Segment	Base	Limit
0 (code)	1400	1000
1 (stack)	6300	400
2 (data)	4300	1100

Translate the logical addresses ⟨0, 430⟩, ⟨1, 400⟩ and ⟨2, 1099⟩.

The idea

Each segment has its size (the limit), so the valid offset goes from 0 to limit − 1. The MMU always does the same thing in this order: it checks that the offset is smaller than the limit and, only if it is, adds the base. Otherwise, exception, and the process accesses nothing.

Step by step

Address	Offset < limit?	Physical
⟨0, 430⟩	430 < 1000: yes	1400 + 430 = 1830
⟨1, 400⟩	400 < 400: no	exception
⟨2, 1099⟩	1099 < 1100: yes	4300 + 1099 = 5399

Check

• 1830 is between 1400 and 2399 (segment 0). 5399 is between 4300 and 5399: it is exactly the last byte of segment 2.
• ⟨1, 400⟩ would give 6700, which no longer belongs to segment 1 (which ends at 6699).

Questions you might ask

Why is 1099 valid and 400 not, if both are «the size minus something»? Because segment 2’s limit is 1100 (1099 is the last valid one) and segment 1’s is 400 (the last valid one is 399). The comparison is always strict: less than the limit.

What if the MMU added first and checked afterwards? It would give the same result for valid addresses, but checking against the physical address is harder (you would need to know where each segment ends in memory). Checking the offset against the limit is a single comparison.

Can segments be in any order in RAM? Yes: 0 at 1400, 2 at 4300 and 1 at 6300. Each one is a contiguous block, but the process does not need to be all together. That is why segmentation suffers from external fragmentation.

What if the segment does not exist (⟨3, 10⟩)? The segment number is compared with the table size: if it is larger, there is also an exception.

Try it yourself

• Translate ⟨0, 999⟩, ⟨0, 1000⟩ and ⟨2, 0⟩.
• What minimum limit would segment 1 need for ⟨1, 400⟩ to be valid?

Problem 3: the TLB and the effective access time

Statement. A paged system has a 5 ns TLB and an 80 ns memory. a) Work out the effective access time with a hit rate of 90 % and of 98 %. b) How long would it take without a TLB? c) And with a two-level table and 90 % hits?

The idea

Every access always goes through the TLB. On a hit, we already have the frame and only need to read the data: one memory access. On a miss, we have to read the page table entry in memory and then the data: two accesses (with a two-level table, three). The effective time is the weighted mean.

Step by step

a) On a hit: $5 + 80 = 85$ ns. On a miss: $5 + 2 \cdot 80 = 165$ ns.

b) Without a TLB, each access is two memory accesses: $2 \cdot 80 = 160$ ns. The TLB at 90 % brings it down to 93: almost half.

c) With two levels, a TLB miss costs three accesses (two table entries and the data): $5 + 3 \cdot 80 = 245$ ns.

Check

• The result must lie between the hit case (85) and the miss case (165): 93 and 86.6 do.
• As the hit rate goes up, the time goes down towards 85: with 100 % it would be exactly 85.
• With two levels only the miss cost changes; a hit still costs 85.

Questions you might ask

Why is the TLB also added on a miss? Because the TLB is always looked up first: only after missing do you go to the table. Some designs look up in parallel, but in the topic (and in the exam) it is added.

Why does the TLB work with so few entries? Because of locality: in a short interval, the program uses few pages, and the TLB keeps exactly those.

Which matters more, making the TLB go from 5 to 2 ns or raising hits from 90 to 98 %? With 2 ns and 90 %: $0.9 \cdot 82 + 0.1 \cdot 162 = 90$ ns. Raising hits gives 86.6: in this system, hitting pays off more than being fast.

Is this the same as the effective time with page faults? It is the same idea of a weighted mean, but with very different numbers: a page fault costs milliseconds. You see it in the next topic.

Try it yourself

• What hit rate is needed for the effective time to be 90 ns with the 5 ns TLB?
• Repeat part c) with a three-level table.

Problem 4: an exercise in the exam format

In the written part and in the test calculations of IC2, page table size and contiguous allocation with first, best and worst fit come up. Marking values showing the sums and the state of the holes after each allocation. This exercise is original and written in that format.

Exercise. a) A system has 32-bit logical addresses, 8 KiB pages and 4-byte table entries. How many entries does a process’s page table have and how much space does it take? b) Memory has holes of 150, 400, 220, 500 and 120 KiB, in that order. Processes A (180 KiB), B (350 KiB), C (90 KiB) and D (420 KiB) arrive in this order. Say which hole each one goes into with first fit, best fit and worst fit.

Process	First fit	Best fit	Worst fit
A (180)	___	___	___
B (350)	___	___	___
C (90)	___	___	___
D (420)	___	___	___

The idea

a) The offset takes the bits needed to cover a page and the rest are page bits: each combination is an entry. b) For each process, in order, look at the list of holes as it has been left after the previous one: first fit takes the first that fits, best fit the smallest that fits and worst fit the largest.

Step by step

a) 8 KiB = $2^{13}$ bytes: 13 offset bits, so $32 – 13 = 19$ page bits are left.

b) Initial holes: 150, 400, 220, 500 and 120.

First fit: A (180) does not fit in 150; it goes into the 400 (220 left). B (350): 150 no, 220 no, 220 no, 500 (150 left). C (90): fits in the first one, 150 (60 left). D (420): no hole reaches 420 (60, 220, 220, 150, 120): waits.

Best fit: A (180): the ones that fit are 400, 220 and 500; the smallest, 220 (40 left). B (350): 400 and 500; the 400 (50 left). C (90): 150, 500 and 120 fit; the 120 (30 left). D (420): the 500 (80 left).

Worst fit: A (180): the largest, 500 (320 left). B (350): the 400 (50 left). C (90): the largest is now the one with 320, which was the 500 (230 left). D (420): no hole reaches it (150, 50, 220, 230, 120): waits.

Process	First fit	Best fit	Worst fit
A (180)	400	220	500
B (350)	500	400	400
C (90)	150	120	500
D (420)	waits	500	waits

Check and how it is marked

• a) Check with the other sum: $2^{32}$ bytes of logical space divided by $2^{13}$ per page gives $2^{19}$ pages.
• b) After each allocation, write the full list of holes. If a hole is used twice (like the 500 one in worst fit), it must have room for both: 500 − 180 = 320 ≥ 90.

Marking values seeing the bits of each field in a) and the state of the holes after each process in b). Here, interestingly, best fit is the only one that places all four: first and worst fit break up the big hole too early.

Try it yourself

• Repeat part a) with 4 KiB pages and 8-byte entries.
• With first fit, in what order would the processes have to arrive for all four to fit?

Common mistakes in this practice

• Using powers of 10: 1 KiB is 1024 bytes, not 1000.
• Adding in paging: the page is replaced by the frame; the offset does not change.
• Not checking the segment’s limit, or checking with «≤».
• Forgetting the TLB on the miss path, or the table access.
• Using the initial list of holes for every process instead of the one being left.
• Not checking that the physical address falls inside its frame or segment.

Check it with Python

This program does the sums of the four problems. The page() function is the MMU’s division, and fit() uses up the holes for each process with the three rules.

# Memory management on paper: paging, segmentation, TLB, table size and fits.
KiB = 1024
def page(dl, size, table):
    p, d = divmod(dl, size)                    # page = quotient, offset = remainder
    return p, d, table[p] * size + d
print("paging 2 KiB, 5000:", page(5000, 2 * KiB, {0: 3, 1: 11, 2: 7, 3: 4}))
p, d, f = page(0x1A3C, 4 * KiB, {0: 0x2, 1: 0x5})
print(f"paging 4 KiB, 0x1A3C: page {p}, offset {d:#05x}, physical {f:#06x}")

segs = {0: (1400, 1000), 1: (6300, 400), 2: (4300, 1100)}   # segment: (base, limit)
for s, d in ((0, 430), (1, 400), (2, 1099)):
    base, limit = segs[s]
    print(f"segment ⟨{s}, {d}⟩:", base + d if d < limit else "exception (offset >= limit)")

T, M = 5, 80                                  # ns of the TLB and of RAM
for h in (0.9, 0.98):
    print(f"TLB h={h}: {h * (T + M) + (1 - h) * (T + 2 * M):.1f} ns")
print(f"no TLB: {2 * M} ns; two levels, h=0.9: {0.9 * (T + M) + 0.1 * (T + 3 * M):.1f} ns")

bits, pg, entry = 32, 8 * KiB, 4
n = 2 ** (bits - pg.bit_length() + 1)         # entries = 2^(address bits - offset bits)
print(f"table: 2^{bits - pg.bit_length() + 1} = {n} entries x {entry} B = {n * entry // (1024 * 1024)} MiB")

def fit(holes, procs, rule):
    h, out = list(holes), []
    for name, t in procs:
        fits = [i for i, x in enumerate(h) if x >= t]
        if not fits: out.append(f"{name}: waits"); continue
        i = {"first": fits[0], "best": min(fits, key=lambda i: h[i]), "worst": max(fits, key=lambda i: h[i])}[rule]
        out.append(f"{name}->{holes[i]}"); h[i] -= t
    return out, h
for rule in ("first", "best", "worst"):
    print(rule, *fit([150, 400, 220, 500, 120], [("A", 180), ("B", 350), ("C", 90), ("D", 420)], rule))

Output (run once):

paging 2 KiB, 5000: (2, 904, 15240)
paging 4 KiB, 0x1A3C: page 1, offset 0xa3c, physical 0x5a3c
segment ⟨0, 430⟩: 1830
segment ⟨1, 400⟩: exception (offset >= limit)
segment ⟨2, 1099⟩: 5399
TLB h=0.9: 93.0 ns
TLB h=0.98: 86.6 ns
no TLB: 160 ns; two levels, h=0.9: 101.0 ns
table: 2^19 = 524288 entries x 4 B = 2 MiB
first ['A->400', 'B->500', 'C->150', 'D: waits'] [60, 220, 220, 150, 120]
best ['A->220', 'B->400', 'C->120', 'D->500'] [150, 50, 40, 80, 30]
worst ['A->500', 'B->400', 'C->500', 'D: waits'] [150, 50, 220, 230, 120]

Things to notice:

1. divmod(dl, size) gives the page (quotient) and the offset (remainder) at once: that is all the MMU does before looking at the table.
2. In part b) of Problem 1, Python writes the numbers in hexadecimal with :#05x and :#06x: the offset 0xa3c appears the same in the logical and the physical address.
3. The second segmentation address comes out as an exception because the condition is d < limit, strict.
4. In fit(), the list h subtracts what is allocated; at the end it prints how the holes are left with each rule.

If you want to see the virtual memory of this same process, there is the next topic: virtual memory and page replacement.

Summary

• Paging: divide by the page size, swap the page for the frame, keep the offset.
• In hexadecimal and with $2^{12}$ pages, the last three digits are the offset.
• Segmentation: check offset < limit and, only then, add the base.
• TLB: $t = h\,(T + M) + (1 – h)\,(T + 2M)$; with more levels, more accesses on a miss.
• Page table: $2^{\text{page bits}}$ entries times the size of each.
• Fits: each process with the holes left over; best fit does not always leave more room, but here it places them all.

Checklist: have you practised it?

• Have you done the four problems on paper before reading the step by step?
• Can you split an address in decimal and in hexadecimal?
• Do you check the limit before adding the base?
• Can you write both TLB paths and weight them?
• Have you checked the problems with the Python program?
• Have you tried the «Try it yourself» tasks without looking at the theory?

If you answered yes to almost everything, you are ready for the memory management exercises, with a test on the whole topic and calculations with boxes that mark themselves. See you there!

Next step: exercisesMemory management — exam-style exercises with addresses to translate, a TLB that hits and holes that are not enough (and the half nanosecond I lost by not adding the TLB)

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