1
$\begingroup$

I was reflecting on what I learned about demand paging and I have a question:
In demand paging, we have entries in the page table only for frames that are present in physical memory. So I was wondering how could a page fault (not because of a bug , occur in such a state).
In my class we where shown an image :
enter image description here

My confusion comes from the definition of demand paging. If every entry in the page table exists in physical memory then how could an invalid (not present in memory) entry exist in page table and cause a trap?
But then again, I thought to myself: Maybe when we need to replace a page and we exchange it with another one we do not replace the entry in the page table as well as we do with the frame but we change it's valid bit to invalid and we add a new entry for the page that we just brought from disk. So basically, we these page replacements the page table of a process grows in time .
Is that right? Is that what happens? If so why we call it page replacement and not frame replacement?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I'm going to refer you to my previous answer on this topic. I went through a number of situations where even if a page table entry (PTE) correctly refers to a page frame in memory, marking the PTE as invalid still makes sense.

There are two views of a virtual address space: the CPU's view (which is implemented by the page table mechanism), and the operating system's view, which involves a bunch of additional data structures and concepts that the CPU's page translation hardware doesn't see.

These additional data structures are not included in your diagram, but they are extremely important. The vast majority of CPUs don't have a concept of "swap", or "memory-mapped file", or any of those other high-level ideas that we use virtual memory for. Those are entirely implemented by operating systems.

When a PTE is marked as invalid, it is invalid from the CPU's point of view. From the operating system's point of view, it may well be a perfectly valid mapping. Assuming the program isn't buggy, it probably is.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I read your answer . I did not think about your point on OS frequently changing bits to invalid to see which page is not-recently used (I've been taught a relative algorithm ''Second chance'' I think is called).. I still have one question: When we say that we are going to replace a page, do we also mean we are going to replace the entry in the page table? Or are we only talking about exchanging it with a frame in physical memory, marking the page of the old one as invalid and adding a new entry in the page table for the frame that just came from disk? $\endgroup$
    – tonythestark
    Jul 7, 2021 at 13:07
0
$\begingroup$

As to terminology, page frame and page is normally two terms which refer to the same thing (a physical page/frame).

Demand paging doesn't mean that the page tables are not present in memory. Demand paging means that the actual pages/frames are not present in memory.

More often than anything, the page tables of a process should be filled according to how much memory is available. For example, on a system with 4GB of memory, the page tables should span 4GB. This is for security reasons. If the page tables are not filled completely, then a certain process A could access the memory of another process. This is due to the fact that, when the page tables are not filled completely, an address can be translated to anything (because anything could happen to be in memory at the time of translation). It is one of the mechanism of paging which allows great hardware isolation of one process to other processes.

Each entry of every page tables have a present bit. When the MMU of the processor attempts to access a page which isn't present, it triggers a page fault. The kernel thus takes the page on the hard-disk and loads it to main memory (unless the page wasn't supposed to be accessed in which case it kills the process).

Every executable today supports virtual memory. The virtual memory in use by a process is specified in the executable directly. The kernel thus uses that to determine if a process should have access to a specific address. It determines the ranges of virtual addresses that a process has access to in the executable.

In demand paging, the kernel just leaves the executable on the hard-disk and builds a memory map of the process. Then, when the process is given a CPU to run (by the scheduler triggered by a timer interrupt), the kernel jumps to its entry point. When the process starts executing, it triggers a page fault immediately. The kernel thus looks in its memory map for that process and determines that the access was legal according to the ranges of virtual addresses that the process has access to. It will thus put the accessed page in main memory reading it from the executable and then put the process back on the run queue.

Your assumption that the page tables are not filled is wrong. The page tables are filled. The entries are just marked as not present. I don't know about Linux or Windows. What I would do, if I wrote something like that, is I would fill all page tables of a process with zeroes. On page fault, I would then check whether the address access was zero and kill the process if it is the case.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "page frame and page is normally two terms which refer to the same thing" That's not true. Normally, a page is a region of virtual address space, and a page frame is a region of physical memory. $\endgroup$
    – Pseudonym ♦
    Jul 7, 2021 at 2:25
  • $\begingroup$ This is only terminology and can be interchanged sometimes in books or online articles. I used both terms to refer to an actual "page frame" in my answer and it still is quite clear and concise. $\endgroup$
    – user123
    Jul 7, 2021 at 4:04
  • $\begingroup$ I'm not disputing your answer, which made it clear in the context of the way you were using the terminology. However, I have never seen any textbook or technical book on the topic of CPU architecture or operating systems which used the terms "page" and "page frame" interchangeably. I'm sure they must exist, but it is nonstandard in any context where the distinction between "virtual page" and "physical page" matters. $\endgroup$
    – Pseudonym ♦
    Jul 7, 2021 at 5:19
  • 1
    $\begingroup$ Anyway thanks for correcting me. I've looked it up and you are right. I should make the distinction. $\endgroup$
    – user123
    Jul 7, 2021 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.