Address space sparsity and fine granularity

ABSTRACT

To fully exploit the potential of large address spaces, e.g. 2⁶⁴-byte, the sparsity problem has to be solved in an efficient manner. Current address translation schemes either cause enormous space overhead (page table trees) or do not support address space structuring, object grouping and mixed page sizes (inverted page tables). Furthermore, an essential handicap of current virtual address spaces is their coarse granularity. It restricts the concept's relevance to low level OS technology. Without this constraint, mapping could be a vertically integrating paradigm, useful on all levels from hardware up to application programming.Guarded page tables help solving both problems. They permit significant extensions of the current programming model without performance degradation: sparse occupation and coarse-grain (4K) pages can be handled by purely conventional hardware; fine-grain (down to 16-byte) pages without fine-grain aliasing become also possible using conventional cache and TLB technology combined with stochastically colored allocation. Unrestricted aliasing and unlimited user level mapping without performance degradation may become possible by hardware innovation.

REFERENCES

• 1: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 2: [2] J. B. Carter, A. L. Cox, D. B. Johnson, and W. Zwanepoel. Distributed operating systems based on a protected global virtual address space. In 3rd IEEE Workshop on Workstation Operating Systems, pages 75-79, Key Biscayne, FL, April 1992.
• 3: [3] J. S. Chase, H. M. Levy, M. J. Freely, and E. D. Lazowska. Sharing and protection in a single address space operating system. Technical Report 93-04-02, Univ. of Washington, Dept. of Computer Science, Seattle, WA, 1993.
• 4: Jeffrey S. Chase , Henry M. Levy , Edward D. Lazowska , Miche Baker-Harvey, Lightweight shared objects in a 64-bit operating system, conference proceedings on Object-oriented programming systems, languages, and applications, p.397-413, October 18-22, 1992, Vancouver, British Columbia, Canada
• 5: Tzi-cker Chiueh , Randy H. Katz, Eliminating the address translation bottleneck for physical address cache, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.137-148, October 12-15, 1992, Boston, Massachusetts, United States
• 6: [6] G. Heiser, K. Elphinstone, S. Russell, and G. R. Hellestrand. A distributed single address-space operating system supporting persistence. SCS&E Report 9302, Univ. of New South Wales, School of Computer Science, Kensington, Australia, March 1993.
• 7: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.106-119, December 05-08, 1993, Asheville, North Carolina, United States
• 8: Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.175-186, October 12-15, 1992, Boston, Massachusetts, United States
• 9: [9] J. Liedtke. Some theorems about guarded page tables. Arbeitspapiere der GMD No. 792, German National Research Center for Computer Science (GMD), Sankt Augustin, 1993.
• 10: [10] J. Liedtke. Guarded page tables, unpublished, March 1994.
• 11: [11] J. Liedtke. Mmu impacts on system architecture, unpublished, June 1994.
• 12: [12] J. Liedtke. Page table structures for fine-grain virtual memory. IEEE Technical Committee on Computer Architecture Newsletter, pages xx-xx, xx 1994. also published as Arbeitspapier der GMD No. 872, German National Research Center for Computer Science (GMD), Sankt Augustin, 1993.
• 13: [13] J. Liedtke. Some theorems about restricted guarded page tables. Arbeitspapiere der GMD No. 834, German National Research Center for Computer Science (GMD), Sankt Augustin, 1994.
• 14: [14] J. Liedtke. Verfahren und Vorrichtung zum Umsetzen einer virtueillen Adresse in eine reale Adresse. Deutsches Patentamt, München, February 1994. Patent application P 44 05 845.4.
• 15: [15] J. Liedtke. A virtually indexed cache with efficient synonym handling. Arbeitspapiere der GMD No. 829, German National Research Center for Computer Science (GMD), Sankt Augustin, 1994.
• 16: Toshio Okamoto , Hiaeo Segawa , Sung Ho Shin , Hiroshi Nozue , Ken-ichi Maeda , Mitsuo Saito, A Micro-Kernel Architecture for Next Generation Processor, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.83-94, April 27-28, 1992
• 17: [17] M. Shapiro. Structure and encapsulation in distributed systems: The proxy principle. In 6th International Conference on Distributed Computing Systems, Cambridge, MA, May 1986.
• 18: [18] C. Yarvin, R. Bukowski, and T. Anderson. Anonymous rpc: Low-latency protection in a 64-bit address space. In Summer Usenix Conference, pages 175-186, Cincinnati, OH, June 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Measurement, Performance, Theory