Beyond Physical Memory - Mechanisms
We've assumed that every address space of every running process fits into memory, we will now relax this assumptions, and assume that we wish to support many concurrently running large address space.
To support large address spaces, the OS needs a place to stash away portions of address spaces that currently aren't in great demand, currently the most used place to stash this is the hard drive, we call this stash portion the swap space.
Swap space
A space on the disk for moving pages back and fort, we swap pages out of memory to this space, and we swap pages into memory from this space.
Example
We have a 3 page physical memory and an 8-page swap space. We also have 3 processes (Proc 0, Proc 1 and Proc 2) and they are actively sharing physical memory, there's also a 4th process that has all his pages on the swap space, hence is not running.
The present bit
On our page table entry, we need to ad a bit entry that represents if the desired page is either on swap space or in physical memory.
- If the present bit is set to one, it means the page is present in physical memory and everything goes as "normal"
- If the present bit is set to zero, the page is not in memory, but rather on disk somewhere, this causes a page fault. On page fault, the OS needs to handle this exception via a page-fault handler.
The page fault
There are two type of systems on TLB misses:
- Hardware managed TLBs
- Software managed TLBs On both of them, there OS has a page-fault handler, this will swap the page into memory in order to service the page fault.
How does the OS finds the pages on swap space
- The OS could use the bits in the PTE normally used for data such as the PFN of the page for a disk address
- When the OS finds a page-fault, it looks for the in the PTE to find the address on disk and issues the request to disk to fetch the page into memory
- When the I/O completes, the OS updates the page table to mark the page as present, it updates the PFN field on the PTE to the proper in memory location and retry the instruction
What if memory is full?
When the memory is full, the OS might choose to kick out some pages to swap space in order to free up some space on memory. The policy to do this is known as page-replacement policy
Page fault control flow
What the hardware does during translation
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit (no need to translate by accessing memory)
if (CanAccess(TlbEntry.ProtectBits) == True)
Offset = VirtualAddress & OFFSET_MASK
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
Register = AccessMemory(PhysAddr)
else
RaiseException(PROTECTION_FAULT)
else // TLB Miss
PTEAddr = PTBR + (VPN * sizeof(PTE))
PTE = AccessMemory(PTEAddr)
if (PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else
if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else if (PTE.Present == True)
// assuming hardware-managed TLB
TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
RetryInstruction()
else if (PTE.Present == False)
RaiseException(PAGE_FAULT)
What the OS does upon a page fault
PFN = FIndFreePhysicalPage()
if (PFN == -1) // No free page found
PFN = EvictPage()
DiskRead(PTE.DiskAddr, PFN) // Sleep (waiting for I/O)
PTE.present = True // Update page table with present bit and translation (PFN)
PTE.PFN = PFN
RetryInstruction() // Retry instruction