Paging

COMP124 Lectures 2021-05-06

Paging is the physical division of a program’s (or segment’s) address space into equal-sized blocks, called pages.

• Each page resides within a page frame in the real memory.
• Pages which are consecutive in the address space (virtual memory) need not occupy consecutive page frames in real memory.
• Very similar to the way files are stored in equal size blocks in a file system.

Page Mapping

Pages are stored in a virtual address space and are mapped to frames in real memory.

graph LR
subgraph Virtual
0[Page 0]
1[Page 1]
x[Page x]
end
subgraph Real
j[Frame J]
i[Frame I]
k[Frame K]
end
0 --> i
1 --> j
x --> k

Translation of virtual addresses (used by programs) into real addresses is performed by hardware. This is via a per-process page table.

Paged Memory

graph LR
br[Page Table Base Register]

subgraph PageTable
ptb[Beginning]
pfa[Page Frame Address]
end
br --> ptb
pfa --> pb
subgraph Page
pb[Beginning]
pa[Page Address]
end
subgraph VirtualAddress
hb[High Bits]
lb[Low Bits]
end
hb --> pfa
lb --> pa

The virtual address points to the page frame address using it’s high bits. The low bits of the virtual address are used as an offset in the page to point to the byte required.

Virtual Addressing

graph TD
subgraph VirtualAddress
vpa[Virtual Page Number]
ipa["In-page Address"]
end

This split isn’t always 50/50.

Data in memory is found from the virtual address using the following method:

1. The page table is found using the page table base register (PTBR).
2. Virtual page number indexes the page table to produce a real page address.
3. The in-page address indexes the real bytes inside the page.

Paging Example

flowchart LR
	subgraph lm [Logical Memory]
		subgraph lm1 [ ]
		lm0[0] --- lma[A]
		1 --- lmb[B]
		2 --- lmc[C]
		3 --- lmd[D]
		end
		subgraph lm2 [ ]
		lm4[4] --- lme[E]
		5 -.- lmf[F]
		6 --- lmg[G]
		7 --- lmh[H]
		end
	end

	subgraph va[Virtual Address]
	a[10]
	b[01]
	end

	subgraph pt[Page Table]
	ptl0[0] --> ptr5[5]
	ptl1[1] --> ptr6[6]
	ptl2[2] --> ptr0[0]
	ptl3[3] --> ptr2[2]
	end

	a --> ptl2

	subgraph pm [Physical Memory]
		subgraph 0
		pm00[0] --- pme[E]
		pm01[1] -.- pmf[F]
		pm02[2] --- pmg[G]
		pm03[3] --- pmh[H]
		end
		subgraph 4
		pm40[0] --- pma[A]
		pm41[1] --- pmb[B]
		pm42[2] --- pmc[C]
		pm43[3] --- pmd[D]
		end
		subgraph ...
		end
	end

	ptr0 ---> 0
	b --> pm01

Segmentation vs Paging

• Segmentation:
  • Logical division of address space.
  • Varying sized units.
  • Units are visible to the program.
• Paging:
  • Physical division of address space.
  • Fixed-size units.
  • Units bear no relation to program structure.

Either may be used a a basis for a swapping system.

Memory could be both segmented and paged via the use of multiple tables.

Advantages of Paging

• Fixed-size units make space allocation simpler.
• Normal fragmentation is eliminated.
  • There is some internal fragmentation (space wasted within frames).

Intel x86 MMU

This feature supports segmentation with paging:

1. CPU generates logical addresses, which are passed to the segmentation unit.
2. The segmentation unit produces a virtual address, which is passes to the paging unit.
3. The paging unit generates physical addresses in main memory.

The CPU is doing this every time an instruction needs to access memory to get or store some data.