Demand Paging Swapping Frames

Question

Disclaimer: This question is related to my operating systems class. However, it's not for any specific homework question. I'm just trying to understand.

Here's what I think I know about demand paging so far. Each process has its own paging table. This table contains an index of the logical address, its corresponding physical address, and a valid/invalid bit which indicates whether the page is currently loaded into main memory.

When a page is accessed, if the valid/invalid bit is set to valid, then the page is simply accessed in main memory via the logical address entry in the table. If the page is not contained in physical memory, then a page fault is generated. This causes the program to try and load the page into memory.

The system first checks if the requested address is valid. If not, then the process is terminated. If the address is valid, then the system checks for free frames. If a free frame is found, then the system loads the requested data from the disk and places it in the free frame. The valid/invalid bit is set to valid in the paging table, the logical address is set to the previously free frame, and the program can continue executing.

If no free frames are present, then the system must swap out a currently used frame and place the requested data in the frame. The system an algorithm such as LRU, MRU, etc. to determine which page to swap out. The system swaps out the old page, loads in the new page and then returns control to the process.

Here's My Question: When the full frame is swapped out, how does the valid/invalid bit of a paging table which accesses this frame get set? That is, how does the system know that the paging table of a process access the frame which is being swapped out?

Here's an example. Suppose there are two process, each with paging tables of size 2 and a physical memory of size 2. Let the paging tables of the processes be as follows:

Process A virtual memory:

Address  Contents
0        'A'
1        'B'

Process B virtual memory:

Address  Contents
0        'C'
1        'D'

Process A paging table:

Logical  Physical  Valid/Invalid
0        0         Valid
1        0         Invalid

Process B paging table:

Logical  Physical  Valid/Invalid
0        1         Valid
1        0         Invalid

Main memory:

Address  Contents
0        'A'
1        'C'

Now suppose Process A attempts to access its logical address of B. The system swaps out the contents of main memory address 1 and swaps in 'D'. How does the system know to set the valid/invalid bit to invalid for the logical address of 0 in Process's B paging table?

Answer 1

There are more control fields either in the page tables themselves or elsewhere in the OS kernel to distinguish between a memory range that has no mapping at all (has never been allocated/mapped or has been freed/unmapped) and a memory range that points to a memory location that's been swapped out. In both cases the range cannot be accessed and an access results in a page fault, but the OS handles this page fault differently in these cases. In the former it terminates the process. In the latter it tries to bring the data back to the memory and restore the mapping to a state in which the data can be accessed.

The OS knows where pages of the physical memory are used. It either scans page tables to find that out or consults its own data structures that it maintains. If the OS needs to steal a page from a process, it saves it (if it's been modified), it alters the mapping so that process can no longer directly access this page without the OS intervention, then reuses this page elsewhere, e.g. in a different process by filling it with the right data and mapping it appropriately so that process can access the data.