what is the need for valid/invalid bit in paged memory technique?

Question

How is the valid/invalid bit in paged memory useful? I am not able to understand the significance. Is it also somehow used to share the processes among different users.

Answer 1

In a typical multilevel page table implementation on a typical modern operating system, any attempt to access memory for a page whose page table entry set to "invalid" (typically 0) causes a page fault. This is a hardware trap which transfers control to the operating system.

The most obvious use for this is to represent a region of address space for which there is genuinely nothing there. When a user-space application starts, it will have some of its virtual address space allocated (e.g. for program text, data, BSS, stack, etc). Additional memory (e.g. memory for heap storage or memory-mapped files) needs to be requested from the operating system. This means that a lot of the address space of the process is "blank", and any attempt to access those addresses should fail. The page table entries for these addresses are therefore marked as invalid.

(As an aside, most modern operating systems also use this to support the NULL pointer in C. The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system. Even the first 1MB is not unknown.)

An alternative way to think of the validity bit is that if a program tries to access an invalid page, this causes a trap to the operating system. So the question you might want to ask is: Why would an operating system want that?

One use is to represent a page which is valid (in the sense that it is correct for the user program to access that address) but not currently backed by a physical page. For example:

• Demand-paged memory, where the address represents part of a memory-mapped file (that might include the program that is running), or a page that has been swapped to secondary storage. In this case, attempting to access the memory causes the operating system to read in the data before the program continues.
• Most modern operating systems support zero-fill memory. When an application allocates memory, the typical default is that this is not backed by physical memory until it is first used. The way this is supported by using the invalid bit.
• A related idea is copy-on-write memory, which is used (for example) to implement fork() in Unix.

And there are a bunch of related operating system housekeeping-like tasks for which manipulating the valid bit is useful. For example:

• Paging out memory requires detecting what pages have been recently used so that infrequently used pages can be paged out. One way to do this is to mark the page as invalid for a short time. If the page is used in that time, operating system knows that it was accessed because a page fault occurred. (Modern Intel CPUs have a more efficient mechanism for this, but the valid bit works if you're using a CPU where that isn't supported.)
• An operating system will often mark a dirty page (e.g. a modified page which represents a memory-mapped file) as invalid while it is being flushed to secondary storage. Any program which tries to modify a page which is in the process of being flushed should wait until the write is complete, so that the data being written is in a known state.
• Operating systems can use the validity bit to help debuggers. Many modern debuggers let you set a breakpoint which fires if a certain variable is read or modified. One way to implement this is through the page fault mechanism.

Basically, any time that it would be useful to handle a memory operation by trapping to the operating system is a time when it would be useful to mark a page as invalid.