The Stack Overflow podcast is back! Listen to an interview with our new CEO.
26

The trick to making this work is "paging." When bringing data from a hard disk into physical memory, you don't just bring a few bytes. You bring an entire page. 4k bytes is a very common page size. If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper. If you have a 48 bit address space and 4096 byte pages, ...


22

I think I see your confusion. The TLB and the data cache are two separate mechanisms. They are both caches of a sort, but they cache different things: The TLB is a cache for the virtual address to physical address lookup. The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables. ...


14

Actually, what you've described confuses ballooning and 'same-page-merging'. I'll try to elaborate on the two to make the distinction apparent. Memory ballooning This is a trick to make sure that some of the memory allocated to the guest virtual machine remains usable by another guest or the host itself (caches, etc). It's done in the following way: The ...


9

I think this example can clarify all your doubts. For example: Assumes main memory is empty at the start page reference sequence is: 3 2 3 0 8 4 2 5 0 9 8 3 2 one reference bit per frame (called the "used" bit) P U 3 P U 2 P U 3 P U 0 P U 8 P U 4 +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | ...


8

I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them. TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense. Look ahead buffers on the other ...


8

Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames. Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice. Imagine a system with four frames with the reference history of 0, 4, 3, ...


8

A computer typically has vastly more hard disk space that RAM. To compensate for limitations in the size of RAM, the operating system reserves part of the disk to use as additional RAM. This is called virtual memory. The RAM and the virtual memory are then divided into even chunks called pages. From the programmer's perspective, there is a large amount of ...


7

There are 3 common strategies to handle this: 1. Hypervisor traps system calls from guest: The hypervisor checks whether the privileged instruction(effectively system call) came from the guest OS itself, or from a user-space program within the guest OS. If it's the former case, then the hypervisor will actually forward the call to the hardware, although ...


7

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details. x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as ...


7

If a reference arrives for a page already in memory, then the replacement algorithm doesn't get invoked at all. The clock replacement algorithm is trying to achieve some of the benefits of LRU replacement, but without the massive overhead of manipulating the LRU bits on every page hit. A page can be in one of three states: Present in memory and the ...


7

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local ...


6

The operating system (with help from the CPU) keeps a page table, which is a mapping of each virtual page for to the physical page it is mapped to. The page table also includes a bit for whether a particular page is currently mapped. For every load and store instruction the hardware walks the page table (or at least a cached portion of it.) If the virtual ...


6

The values for base and limit must be stored in registers somewhere; it would be highly inefficient to read these from memory on every memory access. The distinction between "CPU" and "MMU" isn't really an important one on the old Cray vector architectures, and also isn't really important today. This is more about older microprocessors where a "processor" ...


5

The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this: The hardware feature on modern computers that has the most drastic effect on the performance of algorithms is paging. Quicksort actually does not perform badly in a virtual memory situation (see [2]) ...


5

Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things: DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from ...


5

A faulting prefetch is one which (as gnasher729's answer notes) generates any translation (e.g., invalid page table entry), permission, or other fault (e.g., ECC failure, data watchpoint match) associated with the access. Such a prefetch acts as if the memory location was accessed normally. For data accesses such a prefetch can be provided by software on ...


5

There's a line of research that studies how to store sensitive data in the CPU's registers instead of RAM. Here's a seminal paper: TRESOR Runs Encryption Securely Outside RAM. Tilo Müller, Felix C. Freiling, Andreas Dewald. Usenix Security 2011. There's also work in storing sensitive data in the cache. Here are two of the seminal papers: CARMA: A ...


4

First of all, you are fundamentally confusing the purpose of RAM and hard disk. RAM is the only part of memory that CPU can access. Hard disk exists to expand the capacity of RAM as well as store the data permanently (data on RAM is transient). How it works - The computer generates an executable and stores it in the hard disk. It is just a passive program ...


4

The concept of “job pool” refers to a batch processing system, where jobs are queued to be executed when resources are available. The job pool contains both jobs that are currently executing and jobs that have been scheduled but are not yet being executed. Ancient computers (and some mainframes that are still in operation) worked this way. When a job is ...


4

Well, this is the entire point of "virtual memory". When your program runs, the OS makes it believe it has all the memory just for itself. That is, addresses 1 to 10,000 (say), are all empty and ready for this program to use. If you run two programs, each one of them gets its own space - each one can access address 1 to 10,000 without any interference ...


4

The fork primitive makes a copy of the process. From within the processes, the parent and the child are almost identical; the few differences are the return value of the fork primitive and a few characteristics such as the process ID. Copy-on-write is an implementation optimization. It isn't visible from inside the process. You'd need to look inside the ...


4

It's unclear what you mean. A prefetch is faulting exactly when the actual access to the same data would be faulting. On the other hand, hardware that allows pre-fetches might not actually implement the faults, but only fault if there is an actual access. This is very useful if the official semantics of the prefetch is "no operation", allowing prefetches ...


4

You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available. A page is a block of memory; a thread is a sequence of instructions to be executed.


4

The typical scenario where this kind of incoherence can occur is when the page table has been changed. In this case, an invalid PTE has become valid; perhaps the area of address space has been allocated, or a page has been swapped in. "But", I hear you say, "why wasn't the TLB entry flushed when the PTE changed?" Well, it probably was, but the change may ...


4

Often the effective address is the sum of a small constant and a value from a register. Not always, so this trick does not always apply. The trick then is to make a gamble: access the TLB based on just the value from the register, in parallel with adding the offset to it. Usually the small offset won't change the page being accessed, if that works out then ...


3

The CPU knows nothing about swapping. This is performed by the operating system. When a memory access takes place, the MMU consults page tables to find the physical address that is associated to a virtual address. Each page tables contains a number of descriptors that explain to the MMU what the physical address is. A page fault occurs when the descriptor ...


3

For x86 if the hardware page table walker tries to load a page table entry from a speculative access (or hinted by a prefetch instruction) and the Present Bit is zero, then a page-fault exception is generated (Intel® 64 and IA-32 Architectures Software Developer’s Manual, Vol. 3A, 4.7 PAGE-FAULT EXCEPTIONS). The OS then handles this exception by using OS-...


3

The virtual addresses must be canonical, the top 16 bits are all copies of the 48th bit. Using a non-canonical address (in the sense of using it as an address) generates a #GP. See also, the manual, volume 3, chapters 3 and 4. That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large ...


3

When we are using Virtual Memory, we are translating from a Virtual Address Space to a Physical Address Space. To understand why it requires $2^{35}$ entries, consider the page size. In order to byte address $8$KB, we require $2^{13}$ entries. If we consider the Virtual Address given to us of $48$ bits, this gives us $48-13=35$ bits. These are the bits that ...


3

The term virtual memory applies as soon as there is a mapping from logical (process specific) addresses to physical one. The mapping may be as simple as adding a base to the logical address to get the physical one or as complex as the segmentation followed by paging of x86. The representation you show seems to assume the first.


Only top voted, non community-wiki answers of a minimum length are eligible