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

BySergio Alejandro Medina Ospina
ExercisesFrom scratchIC228 min read

In a practice exam I got the most famous calculation of the topic: 5 ns TLB, 60 ns RAM and 90 % hits. I wrote 0.9 · 65 + 0.1 · 120 = 70.5 ns and moved on, very pleased with myself. The teacher crossed it out: on a miss the TLB is also checked before going to the table, so a miss costs 5 + 60 + 60 = 125 ns, and the result is 71 ns. Half a nanosecond of difference and the whole question wrong.

Here is the whole memory management topic in exam format: a test with every type of question, five calculations with boxes that mark themselves and four open questions with their model answer. The questions are original: they cover the same as the IC2 exam, with other data and other wording. If you first want to see the calculations solved step by step, there is the memory management guided practice.

How to use this article

  1. Do the test without looking at the theory. Each question has its own “Check” button and, at the end, you will see your mark out of 10.
  2. In multiple-choice questions, every wrong tick subtracts, as in the exam. If you are not sure, better leave it.
  3. Calculations are done with paper and a calculator: write the numbers in the boxes (comma or point both work).
  4. Always read the explanation, even when you get it right: many include the trick to go faster.

Before you start, keep three facts at hand: 4 KiB = 4096 = 2^12, a TLB miss is TLB + table + data, and accesses with a hierarchy are levels + 1. With that, half of the calculations are done.

Test: memory management

31 questions in every exam format: single choice, multiple choice that subtracts, true or false, gaps, matching, ordering and short answer.

Question 1Single choice

While running gcc, the CPU asks to read position 1500 of its memory. What kind of address is that 1500?

  1. A logical (or virtual) address
  2. A physical address
  3. A frame address
  4. A symbolic address
Solution

Answer: A logical (or virtual) address

Logical or virtual address: the one the CPU generates. Physical address: the one the memory chip receives. The MMU sits between the two.

Question 2Single choice

What does the MMU do?

  1. It translates the logical addresses the CPU generates into physical addresses
  2. It decides which process gets the CPU
  3. It copies blocked processes to disk
  4. It compiles symbolic addresses into binary
Solution

Answer: It translates the logical addresses the CPU generates into physical addresses

The MMU (memory management unit) is a hardware device: if the OS did the translation in software on every access, the computer would be extremely slow.

Question 3Multiple · wrong ticks subtract

Which of these are problems that memory management has to solve in a multitasking system?

  1. RAM may not have room for all the processes that want to run
  2. A process may read or write in the area of another process or of the OS
  3. Processes must only access the areas the OS has allowed them
  4. The hard disk filling up with temporary files
  5. The CPU running instructions too fast
Solution

Answer: RAM may not have room for all the processes that want to run · A process may read or write in the area of another process or of the OS · Processes must only access the areas the OS has allowed them

The two big problems are lack of capacity (not everything fits) and protection (each process in its own area). The third option is the same idea seen from the OS.

Question 4Multiple · wrong ticks subtract

Which ones are performance goals of memory management (not protection goals)?

  1. Making the most of main memory
  2. Keeping several processes loaded without the system collapsing
  3. Letting a program run without being completely in main memory
  4. Making the most of secondary memory
  5. Letting several processes share a library
Solution

Answer: Making the most of main memory · Keeping several processes loaded without the system collapsing · Letting a program run without being completely in main memory

Performance = getting the most out of RAM. Protecting the OS and each process, and letting areas be shared, is the other group of goals: protection and sharing.

Question 5Match

Match each key concept with what it means:

Relocation
Fragmentation
Access time

Definitions:

  • Free holes left between allocated areas that end up being useless
  • A program can live in any area of physical memory
  • Each process has its own copy of the kernel
  • Memory management must not make each access much slower
Solution
  • Relocation → A program can live in any area of physical memory
  • Fragmentation → Free holes left between allocated areas that end up being useless
  • Access time → Memory management must not make each access much slower

They are the three key concepts of the topic. The extra option is false: the kernel is in RAM only once.

Question 6Order

Put the life cycle of practica.c in order, up to when it runs:

  1. Source program
  2. Linking
  3. Executable program
  4. Object module
  5. Execution
  6. Compilation
  7. Loading into memory
Solution

Correct order:

  1. Source program
  2. Compilation
  3. Object module
  4. Linking
  5. Executable program
  6. Loading into memory
  7. Execution

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 so it can run.

Question 7Fill in the gaps

Fill in the gaps:

For a program to be placed anywhere in RAM, the compiler generates ____ addresses, which are not ____. If the loader converts them when the program is loaded, relocation is ____; if the hardware translates them while it runs, it is ____.

Words:

  • final
  • dynamic
  • symbolic
  • static
  • relocatable
  • absolute
Solution

For a program to be placed anywhere in RAM, the compiler generates relocatable addresses, which are not final. If the loader converts them when the program is loaded, relocation is static; if the hardware translates them while it runs, it is dynamic.

With absolute addresses the program could only go to a fixed area: it would not be relocatable. Dynamic relocation is the one the MMU does on every access.

Question 8True or false

About base and limit registers:

  1. They delimit the memory area the process is allowed to work in.
  2. If the address is outside the area, the request goes out to the bus and memory rejects it.
  3. An illegal access raises an exception.
  4. The check is only done in user mode: the kernel can touch all of memory.
Solution
  • T — They delimit the memory area the process is allowed to work in.
  • F — If the address is outside the area, the request goes out to the bus and memory rejects it.
  • T — An illegal access raises an exception.
  • T — The check is only done in user mode: the kernel can touch all of memory.

The illegal access never reaches the bus: the checking circuit stops it first and an exception is raised. In kernel mode there is no check.

Question 9Short answer

spotify is loaded with base register 52000. The CPU issues logical address 730. What physical address comes out of the MMU?

Solution

Answer: 52730

Physical = base + logical = 52000 + 730 = 52730 (assuming 730 is smaller than the limit).

Question 10Fill in the gaps

Fill in the gaps about shared libraries:

A shared library is loaded the first time some process calls one of its functions; that is why it is called ____. In Windows they are called ____. Calls go through an ____ table managed by the OS, and even if ten processes use it there is only ____ in memory.

Words:

  • one copy
  • DLLs
  • indirect
  • ten copies
  • dynamic linking
  • static linking
  • direct
Solution

A shared library is loaded the first time some process calls one of its functions; that is why it is called dynamic linking. In Windows they are called DLLs. Calls go through an indirect table managed by the OS, and even if ten processes use it there is only one copy in memory.

In Unix and GNU/Linux they are called shared libraries (.so). If memory is very full, the OS can remove the ones nobody references.

Question 11Single choice

gcc is running, spotify is playing and onedrive has been blocked for 20 minutes waiting for the network. If room has to be made with swapping, what goes to disk?

  1. The image of onedrive, because it has been blocked for a long time
  2. gcc’s, because it is the one using the most CPU
  3. The OS kernel, which is the biggest
  4. None: swapping only exists in systems without multiprogramming
Solution

Answer: The image of onedrive, because it has been blocked for a long time

Swap out = write the image of a blocked process to disk; swap in = bring it back when it is needed again. Its cost is the time of those copies.

Question 12Short answer

What is the acronym of the contiguous memory technique with fixed-size partitions decided when the OS boots?

Solution

Answer: MFT

MFT: fixed partitions, rigid but very efficient. Its evolution, MVT, creates variable-size partitions with a dynamic list of holes.

Question 13Match

Match each allocation policy with the hole it picks (among the ones that are big enough):

First fit
Best fit
Worst fit

Definitions:

  • The first one it finds when walking the list
  • The biggest of all
  • The one closest to the kernel
  • The one that leaves the smallest free remainder
Solution
  • First fit → The first one it finds when walking the list
  • Best fit → The one that leaves the smallest free remainder
  • Worst fit → The biggest of all

Best fit has a risk: it keeps leaving tiny remainders that are no use to anyone.

Question 14Single choice

What is known about the performance of the three policies?

  1. First fit and best fit perform about the same, and better than worst fit
  2. Worst fit is the best, because it leaves big remainders
  3. Best fit is always the fastest
  4. The three always give the same result
Solution

Answer: First fit and best fit perform about the same, and better than worst fit

Real systems use more elaborate algorithms; Linux, for example, uses the buddy system.

Question 15True or false

About fragmentation and compaction:

  1. There can be more free memory in total than a process asks for and still no way to give it.
  2. Compaction works the same with static relocation as with dynamic relocation.
  3. Compacting takes time, because blocks of memory have to be copied.
  4. Splitting the process (segmentation or paging) is another way to fight fragmentation.
Solution
  • T — There can be more free memory in total than a process asks for and still no way to give it.
  • F — Compaction works the same with static relocation as with dynamic relocation.
  • T — Compacting takes time, because blocks of memory have to be copied.
  • T — Splitting the process (segmentation or paging) is another way to fight fragmentation.

Compacting moves processes, so it is only possible if their addresses are translated at run time: dynamic relocation.

Question 16Multiple · wrong ticks subtract

What are the advantages of segmentation?

  1. It reduces fragmentation compared with contiguous memory
  2. It lets a segment be shared between processes, such as the code of a DLL
  3. It lets segments be protected, for example marked as read-only or as code
  4. It removes fragmentation completely
  5. It needs no help from the hardware
Solution

Answer: It reduces fragmentation compared with contiguous memory · It lets a segment be shared between processes, such as the code of a DLL · It lets segments be protected, for example marked as read-only or as code

Drawbacks: the compiler works with two-dimensional addresses, hardware is needed, each access is slower and its effectiveness depends on how the program is split.

Question 17Single choice

With segmentation, what does an address generated by the CPU look like?

  1. A ⟨segment, offset⟩ pair
  2. A ⟨page, offset⟩ pair
  3. A single linear number
  4. A ⟨pid, frame⟩ pair
Solution

Answer: A ⟨segment, offset⟩ pair

The compiler identifies the segments, the loader places each one in an area and the MMU translates with the segment table (a base and limit pair per segment).

Question 18Short answer

In paging, what are the pieces of physical memory called, which have the same size as pages?

Solution

Answer: Frames

Page = piece of logical memory; frame = piece of physical memory. Since they have the same size, any free frame is good for any page.

Question 19Fill in the gaps

Fill in the gaps:

Translating in paging means finding out which ____ holds each page of the process. The ____ does it by looking up the process’s ____, which is in ____ memory. That is why, without help, each memory access costs ____ RAM accesses.

Words:

  • three
  • two
  • main
  • secondary
  • page table
  • MMU
  • segment
  • frame
Solution

Translating in paging means finding out which frame holds each page of the process. The MMU does it by looking up the process’s page table, which is in main memory. That is why, without help, each memory access costs two RAM accesses.

One access to read the table entry and another one for the data. The TLB exists precisely to save the first one.

Question 20Single choice

What happens with fragmentation in paging?

  1. External fragmentation disappears, but there is internal fragmentation in the last page of each process
  2. Internal fragmentation disappears, but external remains
  3. Both disappear
  4. Both remain as in contiguous memory
Solution

Answer: External fragmentation disappears, but there is internal fragmentation in the last page of each process

A 13000-byte process with 4 KiB pages takes 4 pages (16384 bytes): 3384 allocated bytes nobody uses. That is internal fragmentation.

Question 21Short answer

What does the PTBR acronym stand for (RBTP in the Spanish notes)?

Solution

Answer: Page-table base register

The PTBR points to the page table in RAM. Its partner, the PTLR (page-table length register), says how many entries it has and is used to detect out-of-range pages.

Question 22Multiple · wrong ticks subtract

Which mechanisms protect access to pages?

  1. Read, write and execute bits in each entry
  2. The valid bit
  3. The page-table length register (PTLR)
  4. The inverted page table, where only valid pages appear
  5. The TLB
  6. The dirty bit
Solution

Answer: Read, write and execute bits in each entry · The valid bit · The page-table length register (PTLR) · The inverted page table, where only valid pages appear

With protection bits you can have, for example, read and execute only code, and read and write data.

Question 23Multiple · wrong ticks subtract

If smaller pages are used, what happens?

  1. Internal fragmentation goes down
  2. The page table has more entries
  3. External fragmentation goes down
  4. The page table takes less space
  5. The TLB hit rate goes up
Solution

Answer: Internal fragmentation goes down · The page table has more entries

Small page: less waste in the last page, but a bigger table. Big page: the opposite.

Question 24Fill in the gaps

Complete the definition of the TLB:

The TLB is a small ____ ____ inside the processor that stores some entries of the page table. Looking it up is almost as fast as reading the CPU ____, and it is used to translate ____ addresses into ____ ones without reading the page table.

Words:

  • logical
  • cache
  • symbolic
  • physical
  • registers
  • secondary
  • direct
  • associative
Solution

The TLB is a small associative cache inside the processor that stores some entries of the page table. Looking it up is almost as fast as reading the CPU registers, and it is used to translate logical addresses into physical ones without reading the page table.

Associative = it searches the page in all its entries at once. That is why it is so fast and why it is small (from 4 to 64 entries in real processors).

Question 25Single choice

In each TLB entry, what is the key and what is the value?

  1. Key: logical page number. Value: frame number
  2. Key: frame number. Value: page number
  3. Key: full physical address. Value: the data
  4. Key: pid. Value: the process’s page table
Solution

Answer: Key: logical page number. Value: frame number

TLB hit: the logical page is among the keys and its frame comes out. TLB miss: it is not; the page table is read and the pair is stored in the TLB.

Question 26True or false

About the TLB:

  1. On a context switch it has to be flushed or loaded with the entries of the incoming process.
  2. In real systems it is normal to hit between 80 % and 98 % of the time.
  3. If the TLB is full, a miss forces it to be emptied completely.
  4. With a TLB hit there is no need to access RAM.
Solution
  • T — On a context switch it has to be flushed or loaded with the entries of the incoming process.
  • T — In real systems it is normal to hit between 80 % and 98 % of the time.
  • F — If the TLB is full, a miss forces it to be emptied completely.
  • F — With a TLB hit there is no need to access RAM.

If it is full, one entry is replaced (the oldest, the least used, a random one…). And a hit saves the table access, but the data is still in RAM: one access.

Question 27Short answer

A TLB answers in 4 ns, RAM in 50 ns and hits happen 80 % of the time (one-level table). What is the mean effective access time, in ns?

Solution

Answer: 64

Hit: 4 + 50 = 54 ns. Miss: 4 + 50 + 50 = 104 ns. Effective: 0.8·54 + 0.2·104 = 43.2 + 20.8 = 64 ns.

Question 28Order

Put in order what happens on a TLB miss with one-level paging:

  1. p is searched in the TLB and it is not there
  2. The data is accessed in RAM
  3. The (p, frame) pair is stored in the TLB
  4. The physical address (frame, d) is built
  5. Entry p of the page table is read in RAM
  6. The CPU generates the logical address (p, d)
Solution

Correct order:

  1. The CPU generates the logical address (p, d)
  2. p is searched in the TLB and it is not there
  3. Entry p of the page table is read in RAM
  4. The (p, frame) pair is stored in the TLB
  5. The physical address (frame, d) is built
  6. The data is accessed in RAM

Two RAM accesses: the table and the data. Next time that page is used, if it is still in the TLB, it will be a hit.

Question 29Match

Match each solution to the page table size with its idea:

Hierarchical paging
Inverted table
Hashed page table

Definitions:

  • A single global table with one entry per RAM frame
  • One table per segment with base and limit
  • The page table itself is split into pages, in several levels
  • The entry is found with a hash function of the page number
Solution
  • Hierarchical paging → The page table itself is split into pages, in several levels
  • Inverted table → A single global table with one entry per RAM frame
  • Hashed page table → The entry is found with a hash function of the page number

The “easy” solution would be a bigger page, but it increases internal fragmentation.

Question 30Short answer

With 4-level hierarchical paging, how many main memory accesses are needed to read a piece of data if the translation is not in the TLB?

Solution

Answer: 5

One per table level plus the data: 4 + 1 = 5. With two levels (32-bit x86) it is 3; with three levels, 4.

Question 31Single choice

In an inverted page table, what does entry number 9 store?

  1. Which process (pid) and which logical page are in frame 9
  2. Which frame holds page 9 of the current process
  3. The base and limit of segment 9
  4. The 9 most used pages in the system
Solution

Answer: Which process (pid) and which logical page are in frame 9

There is one entry per real frame. It saves a lot of memory, but searching for the (pid, page) pair is slow: a hash function is used and the TLB is relied on. PowerPC, UltraSPARC and IA-64 have used it.

In questions about goals and problems, ticking the options that talk about secondary memory. Memory management in this topic is about main memory, RAM.

Step-by-step calculations

Five exercises like the ones in the exam. Do the maths on paper before typing: the explanation of each one has every step.

Question 1Calculation

16-bit logical addresses and 4 KiB pages. The page table of spotify is 0 → 7, 1 → 3, 2 → 11, 3 → 14. Translate each address (offset and physical address, in decimal):

AddressPageOffsetFramePhysical
0x2B10
0x0044
0x1FFF
0x3800
Solution
AddressPageOffsetFramePhysical
0x2B10228321147888
0x0044068728740
0x1FFF14095316383
0x3800320481459392

With 4 KiB = 2^12, the 12 low bits are the offset and the 4 high bits the page; in hexadecimal, the first digit is the page. For example, 0x2B10 = 11024 = 2·4096 + 2832: page 2, offset 2832. The table says frame 11, so the physical address is 11·4096 + 2832 = 47888 (0xBB10).

The offset never changes during translation: only the page is replaced by the frame. 0x1FFF is the last byte of page 1 (offset 4095).

Question 2Calculation

Work out the time of a TLB hit, of a miss and the mean effective time (in ns) of each system. System D uses two-level paging:

SystemTLB (ns)RAM (ns)Hit rateLevels
A1010080 %1
B25095 %1
C48075 %1
D56090 %2
SystemHitMissEffective
A
B
C
D
Solution
SystemHitMissEffective
A110210130
B5210254.5
C84164104
D6518577

Hit = TLB + RAM (the data). Miss = TLB + one access per table level + the data. Effective = h·hit + (1 − h)·miss.

A: 0.8·110 + 0.2·210 = 88 + 42 = 130. B: 0.95·52 + 0.05·102 = 49.4 + 5.1 = 54.5. C: 0.75·84 + 0.25·164 = 63 + 41 = 104.

D: with two levels, a miss costs 5 + 60 + 60 + 60 = 185 ns, so 0.9·65 + 0.1·185 = 58.5 + 18.5 = 77 ns: 6 ns more than with one level (71).

Question 3Calculation

Free holes, in this order: 150, 600, 250, 350 and 520 KiB. A (240), B (500), C (140) and D (370) arrive. For each policy, write the size of the hole it picks at that moment (0 if it does not fit):

ProcessFirstBestWorst
A (240)
B (500)
C (140)
D (370)
Solution
ProcessFirstBestWorst
A (240)600250600
B (500)520520520
C (140)150150360
D (370)06000

First fit: A goes into the first one that fits (600 → 360 left), B into 520, C into 150 and D (370) no longer fits, because the biggest hole is 360: the holes are 0, 360, 250, 350 and 20.

Best fit: A picks the tightest one, 250 (10 left); B, 520; C, 150; D, 600 (230 left): they all fit, because the big hole was still whole.

Worst fit: A takes the biggest, 600 (360 left); B, 520; C, the biggest left, 360 (220 left); D does not fit: the holes are 150, 220, 250, 350 and 20.

Notice that worst fit breaks the big hole first and then has none left for D.

Question 4Calculation

Work out the page bits, the number of entries and the size of the page table of one process (in KiB) with a one-level table:

CaseAddressPageEntry
132 bits4 KiB4 B
232 bits16 KiB4 B
324 bits1 KiB2 B
420 bits512 B4 B
CasePage bitsEntriesTable (KiB)
1
2
3
4
Solution
CasePage bitsEntriesTable (KiB)
12010485764096
2182621441024
3141638432
41120488

Offset bits = log2 of the page size (4 KiB → 12, 16 KiB → 14, 1 KiB → 10, 512 B → 9). Page bits = address bits − offset bits. Entries = 2^page bits. Size = entries × bytes per entry.

Row 1: 32 − 12 = 20 bits, 2^20 = 1,048,576 entries × 4 B = 4 MiB = 4096 KiB. Row 2: making the page four times bigger (from 4 to 16 KiB) removes 2 bits and divides the table by 4: 1024 KiB. Row 3: 2^14 × 2 B = 32 KiB. Row 4: 2^11 × 4 B = 8 KiB.

Question 5Calculation

Segment table of campus: 0 (base 6000, limit 2500), 1 (1200, 800), 2 (15000, 4000) and 3 (9500, 1000). Translate each ⟨segment, offset⟩ address. If the access is illegal, write “exception”:

AddressLimitPhysical
⟨0, 1200⟩2500
⟨1, 900⟩800
⟨2, 3999⟩4000
⟨3, 1000⟩1000
⟨1, 50⟩800
Solution
AddressLimitPhysical
⟨0, 1200⟩25007200
⟨1, 900⟩800exception
⟨2, 3999⟩400018999
⟨3, 1000⟩1000exception
⟨1, 50⟩8001250

First the offset is compared with the limit of its segment; only if it is smaller is the base added.

⟨0, 1200⟩: 1200 < 2500 → 6000 + 1200 = 7200. ⟨1, 900⟩: 900 ≥ 800 → exception. ⟨2, 3999⟩: the last valid byte, 15000 + 3999 = 18999. ⟨3, 1000⟩: 1000 is not smaller than 1000 → exception (the limit is the size: valid offsets go from 0 to 999). ⟨1, 50⟩: 1200 + 50 = 1250.

To translate with 4 KiB pages, write the address in hexadecimal: the first digit (of 16 bits) is the page and the last three, the offset. 0x2B10 → page 2, offset 0xB10. If the frame is 11 (0xB), the physical address is 0xBB10, and in decimal 11 · 4096 + 2832 = 47888.

In segmentation, accepting an offset equal to the limit. With limit 1000 the valid ones go from 0 to 999: ⟨3, 1000⟩ is an exception.

Open questions

Write your answer in the box and then compare it with the model answer and with the list of what the marker looks for. There is no automatic mark: you mark yourself.

Question 1Open answer

Explain the difference between static and dynamic relocation. Why does only dynamic relocation allow memory to be compacted?

Solution

Model answer:

The compiler generates relocatable addresses, which are not final. Relocation means turning them into physical addresses, and the difference is when it is done.

In static relocation the conversion is done by the loader, once, when the program is loaded into memory. From then on the process’s addresses are physical and fixed: if the process were moved, they would point to the old area.

In dynamic relocation the process keeps its logical addresses and the hardware (the MMU) translates them on every access, for example by adding a base register: physical = base + logical.

Compacting means moving processes to join the free holes. With dynamic relocation it is enough to copy the process and change its base register; with static relocation every one of its addresses would have to be fixed, which cannot be done.

What the marker looks for:

  • Relocation = turning logical addresses into physical ones
  • Static: done by the loader, once, at load time
  • Dynamic: done by the MMU on every access (base register)
  • Compacting moves processes: it only works if changing the base is enough
Question 2Open answer

Compare segmentation and paging: how the process is split, what the logical address looks like, which table the MMU uses and what fragmentation each one has.

Solution

Model answer:

Both are non-contiguous memory techniques: the process is split and each piece can go to a different area of RAM.

In segmentation the pieces are logical and of variable size (code, data, stack…). The address is ⟨segment, offset⟩ and the MMU uses a segment table with a base and a limit per segment: if the offset is smaller than the limit, physical = base + offset; otherwise, exception. It reduces external fragmentation, but does not remove it, and makes it easy to share and protect whole segments.

In paging the pieces have a fixed size (pages) and RAM is divided into frames of the same size. The address is ⟨page, offset⟩ and the MMU uses a page table that gives the frame of each page: physical = frame · size + offset. There is no external fragmentation (any free frame will do), but there is internal fragmentation in the last page.

Segmentation respects how the programmer sees their program; paging is invisible to them and much easier to manage.

What the marker looks for:

  • Variable size (segments) versus fixed size (pages)
  • ⟨segment, offset⟩ and ⟨page, offset⟩
  • Segment table (base and limit) versus page table (frame)
  • Segmentation: reduces external. Paging: no external, some internal
Question 3Open answer

What is the TLB and why is it needed? Explain what happens on a hit and on a miss, and work out the effective time with a 5 ns TLB, a 60 ns RAM and 90 % hits.

Solution

Model answer:

In current systems the page table is in main memory, so every access of a program would cost two RAM accesses: one to read the table entry and another one for the data.

The TLB is a small associative cache inside the processor that stores ⟨logical page, frame⟩ pairs. When translating, the page is searched in all its entries at once. If it is there (hit), the frame is obtained without reading the table and RAM is only accessed for the data. If it is not (miss), the page table is read, the address is built and the translation is stored in the TLB, replacing an entry if it is full.

Hit: 5 + 60 = 65 ns. Miss: 5 + 60 + 60 = 125 ns. Effective time: 0.9 · 65 + 0.1 · 125 = 58.5 + 12.5 = 71 ns, very close to the 60 ns of a direct access.

On a context switch the TLB is flushed or loaded with the entries of the incoming process, because the translations of one process are no good for another.

What the marker looks for:

  • Problem: two RAM accesses for every access
  • TLB: associative cache of ⟨page, frame⟩ pairs
  • Hit and miss well explained (and the TLB update)
  • Correct calculation: 71 ns
Question 4Open answer

With 32-bit addresses and 4 KiB pages, how big can a process’s page table be (4-byte entries)? Explain two solutions to that problem and their drawback.

Solution

Model answer:

4 KiB = 2^12, so there are 12 offset bits and 32 − 12 = 20 page bits: 2^20 = 1,048,576 entries. At 4 bytes per entry, the table takes 4 MiB per process, and with 48 or 64-bit addresses it would be much worse.

Hierarchical paging: the table itself is paged. In 32-bit x86 the address is split into 10 + 10 + 12 bits: an outer table points to inner tables, and only the inner tables the process uses exist. Drawback: without a TLB hit three RAM accesses are needed (levels + 1), so the TLB becomes even more necessary.

Inverted page table: a single table for the whole system, with one entry per frame saying which process (pid) and which page are in it. It saves a huge amount of memory, but searching for the ⟨pid, page⟩ pair is slow; it is solved with a hash table and by relying on the TLB.

The easy solution, a bigger page, shrinks the table but increases internal fragmentation.

What the marker looks for:

  • Calculation: 20 page bits, 2^20 entries, 4 MiB
  • Hierarchical paging and its cost in accesses
  • Inverted (or hashed) table and its cost in searching
  • Mention of bigger pages and internal fragmentation

In the exam, open questions are mostly rewarded for using the exact vocabulary (dynamic relocation, MMU, segment table, frame, TLB hit and miss, internal fragmentation) and backing it up with an example with numbers.

The whole topic in one picture

If you can explain this picture, you know the topic. Go over it before the exam:

Topic 9 summaryThe MMU translates and protects; three techniques: contiguous (base and limit, fits, external fragmentation), segmentation (segment table) and paging (page table, TLB, internal fragmentation).The whole topic in one pictureCPUlogical addr.MMUtranslates and protects on every accessContiguous· base + limit· MFT / MVT· first/best/worst· external frag.· → compactionSegmentation· ⟨s, d⟩· segment table· d < limit[s]· physical = base[s] + d· share, protectPaging· ⟨p, d⟩· page table· physical = frame·size + d· TLB: 2 → 1 access· internal frag.t = h·(T+M) + (1−h)·(T+2M)table = 2^page_bits × entryTo shrink the table: hierarchical paging (levels + 1 accesses), inverted table or hashing.
If you can explain this picture from memory, the topic test holds no secrets.

Cheat sheet: memory management

The essentials in 30 seconds

  • The CPU generates logical addresses; the MMU translates them into physical ones on every access, and protects along the way.
  • Static relocation: done by the loader at load time. Dynamic: done by the hardware at run time (lets processes move and memory be compacted).
  • Contiguous: one block per process, base and limit, MFT or MVT, fits and external fragmentation.
  • Segmentation: ⟨s, d⟩, segment table with base and limit; reduces external fragmentation.
  • Paging: ⟨p, d⟩, equal pages and frames, page table; no external, but internal fragmentation.
  • TLB: associative cache of ⟨page, frame⟩ that avoids reading the table in RAM.

I want… / How / Result

I want…HowExample
Physical with a base registerbase + logical (if logical < limit)52000 + 730 = 52730
Page and offsetlogical // size, logical % size6700 → 1 and 2604 (4096-byte pages)
Physical with pagingframe · size + offset9 · 4096 + 2604 = 39468
Physical with segmentationbase[s] + d (if d < limit[s])⟨1, 600⟩ with base 4000 → 4600
TLB hit timeTLB + RAM5 + 60 = 65 ns
TLB miss timeTLB + RAM · (levels + 1)5 + 60 + 60 = 125 ns
Effective timeh · hit + (1 − h) · miss0.9 · 65 + 0.1 · 125 = 71 ns
Page bitsaddress bits − log2(page size)32 − 12 = 20
Table size2^page bits × bytes per entry2^20 × 4 B = 4 MiB
Accesses with a hierarchylevels + 1 (without a TLB hit)4 levels → 5

Calculation templates

ExerciseDataResult
Translation (4 KiB pages)0x2B10, table 2 → 11page 2, offset 2832, physical 47888 (0xBB10)
Effective timeTLB 4, RAM 50, 80 %0.8 · 54 + 0.2 · 104 = 64 ns
Effective time, 2 levelsTLB 5, RAM 60, 90 %0.9 · 65 + 0.1 · 185 = 77 ns
Fitsholes 150, 600, 250, 350, 520; A 240, B 500, C 140, D 370first and worst: D does not fit; best: all fit
Table size32 bits, 16 KiB, 4 B18 bits, 262144 entries, 1024 KiB
Internal fragmentation13000 B in 4 KiB pages4 pages, 3384 B wasted

Quick comparison

ContiguousSegmentationPaging
PiecesOneVariable, logicalFixed
External frag.YesLessNo
Internal frag.No (MVT)NoYes
TableBase and limitSegment tablePage table

Symptom / Likely cause

SymptomLikely cause
The physical address does not end in the same three hex digits as the logical oneYou changed the offset: only the page is replaced by the frame
You get an offset like 2700 with 4 KiB pagesYou divided by 4000 instead of 4096
The effective time comes out half a ns shortYou did not add the TLB on the miss
There is plenty of free memory and the process does not fitExternal fragmentation: no hole is big enough
⟨s, d⟩ with d equal to the limit gives you an addressThe limit is the size: d must be strictly smaller
With 3 levels you count 3 accessesThe data access is missing: levels + 1 = 4

Before you hand it in, ask yourself

  1. Did I use 1024 (and not 1000) when going from KiB to bytes?
  2. Did I compare with the limit before adding the base?
  3. Does the TLB miss include the TLB time, each table level and the data?
  4. Am I talking about external or internal fragmentation, and does it match the technique (contiguous, segmentation or paging)?

All clear? Go back to the memory management theory if something went wrong. In the next topic comes virtual memory: what happens when a process does not fit completely in RAM and a page has to be chosen to leave.

Keep goingAll Operating systems articles

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

Ready for the exam?IC2 theory mock exam — first midterm, second midterm or the full exam, with your real mark and a review of every mistake (as if you were in the exam room)

Data Science and Engineering student at ULPGC. I explain what I learn
at university the way I wish it had been explained to me: with its
doubts, its mistakes and the path to the solution.

Keep learning