Could you tell me about virtual memory, page fault, and LRU algorithm?

  • 0

    I heard of this during the interview of Synology Inc, which is a Taiwanese corporation that specializes in NAS appliances, and try to translate it. Hope it helps :)

  • 1

    Briefly speaking, the concept of virtual memory is to use your hard disk storage as some kind of extension of RAM, so a computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that's set up to emulate the computer's RAM. The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using disk. Second, it allows us to have memory protection, because each virtual address is translated to a physical address.

    Virtual memory is commonly implemented by demand paging. It can also be implemented in a segmentation system. Demand segmentation can also be used to provide virtual memory. A demand paging system is quite similar to a paging system with swapping where processes reside in secondary memory and pages are loaded only on demand, not in advance. When a context switch occurs, the OS does not copy any of the old program’s pages out to the disk or any of the new program’s pages into the main memory Instead, it just begins executing the new program after loading the first page and fetches that program’s pages as they are referenced. While executing a program, if the program references a page which is not available in the main memory because it was swapped out a little ago, the processor treats this invalid memory reference as a page fault and transfers control from the program to the OS to demand the page back into the memory.

    Least Recently Used or LRU algorithm is a kind of page replacement algorithms, which are the techniques using which an OS decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages. For the strategy of LRU, page which has not been used for the longest time in main memory is the one which will be selected for replacement. It's easy to implement, keep a list, and replace pages by looking back into time.

  • 2

    virtual memory:

    • mapping of virtual addresses to physical memory addresses done by the CPUs MMU (memory management unit) based on information from the operating system.
    • each process has it's own virtual address space which allows for isolation of memory among processes and therefore increases the overall stability of a system
    • since each process has it's own virtual memory, processes that grow their memory usage get still a continuous address space (which is a big advantage for heap management etc...)
    • the operating system can swap out memory pages from the main memory to a page file and free physical memory - transparent for the process (except a heavy delay when the process access that memory again)

    a page fault:

    • occurs when the CPU access a swapped out address. An interrupt is raised by the hardware and the OS is reading in the missing pages.
    • sometimes occurs when a virtual address is accessed that doesn't exist at all. In such cases the operating system usually terminates the process assuming an error (program, memory, ...)


    • stands for least recently used.
    • it's a common algorithm used to manage caches in a way that elements that have been accessed (read/write) recently are kept in the cache while elements not being used lately are purged from cache if the memory is needed. This algorithm is applied for swapping out pages, to secondary storage, like disc.

    LRU algorithm in general are used to manage the more valuable primary storage for frequent use and extend the storage space with less valuable secondary storage.
    From CPU point this is Cache/Memory
    From an OS point this is Memory/Disc
    From an application point this is often Memory/Disc/Network, whereas this is changing as networks catch up with physical discs...

    It's interesting to notice how L1,L2 cache, Memory and Disc behave in terms of size and speed on commodity hardware:

    • L1 cache: 1 ns
    • L2 Cache: 4 ns
    • Main memory: 100ns / 100 GB/s
    • SSD: 20ns / 8'000 MB/s
    • Disc: 8.000 ns / 100 MB/s continuous read
    • Network: 100 - 1000 MB/s

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.