Implementers of virtual memory systems have to make selections among the major theoretical algorithms, such as second chance versus  aging, local versus global page allocation, and demand paging versus prepaging. But they also have to be aware of a number of practical  implementation issues as well. In this section we will consider a few of the common problems and some solutions.

Operating System Involvement with Paging

There are four times when the operating system has paging-related work to do: process creation time, process execution time, page fault  time, and process termination time. We will now briefly study each of these to see what has to be done.

When a new process is created in a paging system, the operating system has to determine how large the program and data will be (initially)  and create a page table for them. Space has to be allocated in memory for the page table and it has to be initialized. The page table need  not be resident when the process is swapped out but has to be in memory when the process is running. Furthermore, space has to be  assigned in the swap area on disk so that when a page is swapped out, it has somewhere to go. The swap area also has to be initialized  with program text and data so that when the new process starts getting page faults, the pages can be brought in. Some systems page the  program text directly from the executable file, thus saving disk space and initialization time. Lastly, information about the page table and  swap area on disk must be recorded in the process table.

When a process is scheduled for implementation, the MMU has to be reset for the new process and the TLB flushed, to get rid of traces of the previously executing process. The new process page table has to be made current, usually by copying it or a pointer to it to some hardware register(s). Optionally, some or all of the process pages can be brought into memory to reduce the number of page faults in the beginning (e.g., it is certain that the page pointed to by the PC will be required).

When a page fault takes place, the operating system has to read out hardware registers to find out which virtual address caused the fault.  From this information, it must compute which page is required and locate that page on disk. It must then find an available page frame to put  the new page, removing some old page if need be. Then it must read the required page into the page frame. Lastly, it must back up the  program counter to have it point to the faulting instruction and let that instruction carry out again.

When a process exits, the operating system must release its page table, its pages, and the disk space that the pages occupy when they are  on disk. If some of the pages are shared with other processes, the pages in memory and on disk can only be released when the last  process using them has ended.

Page Fault Handling

We are at last in a position to explain in detail what happens on a page fault.

The sequence of events is as follows:

1 . The hardware traps to the kernel, saving the program counter on the stack. On most machines, some information about the state of the
current instruction is saved in special CPU registers.

2. An assembly code routine is started to save the general registers and other volatile information, to keep the operating system from  destroying it. This routine calls the operating system as a procedure.

3. The operating system discovers that a page fault has occurred, and tries to discover which virtual page is required. Often one of the  hardware registers contains this information. If not, the operating system must get back the program counter, fetch the instruction, and parse it in software to figure out what it was doing when the fault hit.

4. Once the virtual address that caused the fault is known, the system checks to see if this address is valid and the protection consistent
with the access. If not, the process is sent a signal or killed. If the address is valid and no protection fault has occurred, the system checks  to see if a page frame is free. If no frames are free, the page replacement algorithm is run to select a victim.

5. If the page frame selected is dirty, the page is scheduled for transfer to the disk, and a context switch takes place, suspending the faulting process and letting another one run until the disk transfer has completed. In any event, the frame is marked as busy to prevent it  from being used for another purpose.

6. As soon as the page frame is clean (either immediately or after it is written to disk), the operating system looks up the disk address
where the required page is, and schedules a disk operation to bring it in. While the page is being loaded, the faulting process is still
suspended and another user process is run, if one is available.

7. When the disk interrupt indicates that the page has arrived, the page tables are updated to reflect its position, and the frame is marked  as being in normal state.

8. The faulting instruction is backed up to the state it had when it began and the program counter is reset to point to that instruction.

9. The faulting process is scheduled, and the operating system returns to the (assembly language) routine that called it.

10. This routine reloads the registers and other state information and returns to user space to continue execution, as if no fault had occurred.


virtual memory, operating system, page table, process table, page fault handling