| Physical Memory | |
| 0: | A |
| 1: | B |
| 2: | Data1 |
| 3: | Data2 |
| 4: | Data3 |
| Page Table P1: | |
| 0: | 2 (private data) |
| 1: | 0 (shared data A) |
| Page Table P2: | |
| 0: | 3 (private data) |
| 1: | 0 (shared data A) |
| 2: | 1 (shared data B) |
| Page Table P3: | |
| 0: | 4 (private data) |
| 0: | 1 (shared data B) |
After swapping out all pages assigned for process P1 we don't need a page table for P1 any longer. Also, we need to invalidate the entry for page A in page table for P2.
| Physical Memory | |
| 0: | ---- |
| 1: | B |
| 2: | ---- |
| 3: | Data2 |
| 4: | Data3 |
| Page Table P2: | |
| 0: | 3 (private data) |
| 1: | invalid |
| 2: | 1 (shared data B) |
| Page Table P3: | |
| 0: | 4 (private data) |
| 1: | 1 (shared data B) |
Once, you've swapped P1 back into memory, we have to update all page tables which are sharing data with this process. Observe that the memory allocation might be different from the initial one:
| Physical Memory | |
| 0: | Data1 |
| 1: | B |
| 2: | A |
| 3: | Data2 |
| 4: | Data3 |
| Page Table P1: | |
| 0: | 0 (private data) |
| 1: | 2 (shared data A) |
| Page Table P2: | |
| 0: | 3 (private data) |
| 1: | 2 (shared data A) |
| 2: | 1 (shared data B) |
| Page Table P3: | |
| 0: | 4 (private data) |
| 0: | 1 (shared data B) |
In order to maintain coherence between page tables the operating system needs to invalidate all page table entries which are refering to a page once that page gets swapped out. Whenever a shared page is swapped back into memory, all the processes sharing this page need to update their page tables.
This can be efficiently implemented using pointers as aliases for shared pages: Store in a page table the usual pointer to the physical memory for non-shared pages. For shared pages, keep a pointer to a special shared node. This nodes contains either a pointer to the location of the shared page in physical memory, NULL if that page isn't contained in memory.
The diagramm below shows such a structure for a shared page between process 1 and process 2. (Logical page 1 of process 1 and logical page of process 2 are aliassed.)
Process 1 |
+-------+ | P
| 0: | shared node | h
| 1: ----------------> +--------+ | y
| 2: | | -----------> s
+-------+ +--> +--------+ | i
| | c
Process 2 | | a
+-------+ | | l
| 0: | | |
| 1: | | | M
| 2: | | | e
| 3: -------------+ | m
+-------+ |
Whenever we need to invalidate a shared page, we set the shared node
pointer to NULL. Whenever we swap back a shared page into the memory,
we set the shared node pointer to the new memory location.
The following things happen at a page fault: 1) checking the TLB: page not in TLB (+ t_tlb) 2) checking the Page Table: page not in memory (+ t_memory_access) 3) Transfer page from disk and update both, the TLB and the page table (+ t_access_transfer) The time for all of this is accummulated as access/transfer time. 4) check TLB successfully (+ t_tlb) 5) get memory entry. (+ t_memory_access)
T = 0.8 * 1.1us + 0.18 * 2.1us + 0.02 * 20 002.2us = 401.302us The effective access time is 401.302 micro seconds.