What is the price paid for the vast virtual address space provided to programmers for their applications? Or in other words, what is the overhead due to virtual memory?

Is there any other overhead from implementing virtual memory, beyond memory consumed by the kernel?

  • $\begingroup$ What do you mean by "OS Kernel is the overhead in Virtual Memory implementation". $\endgroup$ – babou Dec 12 '14 at 22:55
  • $\begingroup$ I was looking at this picture here eduunix.ccut.edu.cn/index2/html/linux/… Quoting from the article: As you can see in Figure 2-6, the kernel occupies a quarter of the virtual address space starting from address 0xC0000000. This region is also known as "kernel space." The rest of the address space is occupied by application-specific text, data, and library mappings. This is also known as "user space." $\endgroup$ – user141865 Dec 13 '14 at 0:36
  • 1
    $\begingroup$ The kernel requires whatever space it requires. I am not sure I undrstand the intent of this dioagram without the context of the book (Kernel space seems really large). You may consider that overhead, but it is not due to virtual memory. When you ask "What are the overhead of Virtual Memory implementation?", you are asking for the extra cost due to the fact that virtual memory is being used, not what application or other code is using that virual memory. $\endgroup$ – babou Dec 13 '14 at 0:59
  • $\begingroup$ babou, I guess you're right. I should double check with my professor. So, if I understand your answer in the post below correctly, you're saying that the major extra cost of implementing VM is loading some part of the recently used virtual address in the physical memory? This question has 5 points, so my guess is my professor were looking for 5 different key points in the answer. $\endgroup$ – user141865 Dec 13 '14 at 1:14
  • 1
    $\begingroup$ Well. I cannot know what your professor wanted. I did not follow that class. The cost of pages faults and the risk of thrashing is the first thing that comes to mind. It is an overhead in execution time, which you pay for saving on the cost of fast memory. That is a very classical trade-off. May-be your teacher wants you to discuss the issue. Try to search the web and read some documents or books. Your teacher may expect references to the documents you read (good practice anyway), so you have to show you did. Virtual memory is a form of caching, so there may be info regarding caching generally $\endgroup$ – babou Dec 13 '14 at 1:22

One major overhead of virtual memory is that virtual pages that are being used in the current computation have to be loaded in physical memory, which usually means also transferring out another page back on disk. Since this is costly, you want to avoid doing it too often. Hence an important concept is the locality of programs: though a program may have to use considereable space, you try to organize the program so that only a much smaller part of memory is used at any time, a smaller part that evolves only slowly.

THis concerns the code being executed, but also the data used. And data is often orders of magnitude larger than the code. So, a program handling large amounts of data will often be organized so as to improve the locality of the data organisation in memory (but this depends also on what the code does with the data). As a consequence, too naive a use of classical textbook algorithms may result in very slow programs, because of too many page faults.

I guess there are tools to analyze the locality of programs, or to optimize them to improve it. A specific example is the design of garbage collectors, which have developed various techniques to improve data locality by reorganizing the information, and which are of course design to explore the memory in a very local way, for example by looking in priority at pages the main program has already loaded in physical memory.

Programs with bad locality spend too much time loading pages compared to actual computing time. This is called thrashing.

  • $\begingroup$ Hey, great explanation! I guess the question is a little bit ambiguous or maybe too broad. As you can see on my comment above, I thought the overhead of implementing VM would be the "kernel space", which was basically the reserved space in virtual address, that could not be used by the user. But, your answer made me thinking that, in terms of hardware, the overhead of implementing VM could be TLB (for virtual-physical memory translation). Is there any other overhead you have in mind? $\endgroup$ – user141865 Dec 13 '14 at 1:01
  • $\begingroup$ You are correct that the TLB is a form of hardware overhead ... though the term is not quite proper since VM is all the TLB can do ... it is intended for that. But it does cause an overhead in the cost of the hardware ... well, the cost of the chip. But how much is that today. $\endgroup$ – babou Dec 13 '14 at 1:14
  • $\begingroup$ TLB misses have a performance (and energy) cost (especially given physically tagged caches, which could be avoided with a Single Address Space OS). Memory used for page tables cannot be used for actual data. Cache aliasing becomes a potential problem, constraining design choices (again SASOSes avoid this issue). There is also the general problem of leaky abstraction, where the details one is not supposed to care about (being hidden behind the abstraction) introduce a perceptible problem. $\endgroup$ – Paul A. Clayton Dec 13 '14 at 4:23
  • $\begingroup$ One other type of overhead is the RAM required to store page tables. $\endgroup$ – Pseudonym Dec 13 '14 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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