臺灣博碩士論文加值系統

虛擬化技術可將數個作業系統合併於一台實體機器上同時執行。它源自於過往利用數個單一使用者作業系統，建立一個多使用者分時作業系統。存在已久的虛擬化技術也與時俱進。除了在伺服器端的應用外，隨著嵌入式處理器能力的進步，虛擬化技術被更加廣泛地應用在不同類型的系統。由於這些新興應用的多元性，我們需要發展新的設計方法，以便將這些系統的特性一併納入考量。在這篇論文中，我們提出利用軟硬體協同設計來優化虛擬化環境的想法，並以優化記憶體虛擬化為例，展示軟硬體協同設計對於優化虛擬化環境的潛能。基於過往的研究，我們認為記憶體子系統是虛擬化環境中主要的效能瓶頸之一。因此我們以特定類別的虛擬化環境作為範例，專注針對其環境的記憶體虛擬化之優化。首先，我們以定量分析的方法，評估記憶體虛擬化的影響。隨後我們提出一個記憶體虛擬化的優化方式，並以正式證明進行定性分析；同時結合軟體擬真與硬體模擬，進行定量分析。實驗結果指出我們提出的方法效能勝過現有的方法。這個研究也指出運用軟硬體協同設計進行優化，在新興應用的虛擬化環境中深具潛力。

Virtualization is a technology enabling consolidation of multiple operating systems into a single physical machine. It originated from the need to create a multi-user time-sharing operating system based on multiple single-user operating systems. This long-lasting technology has evolved constantly. In addition to the popular applications for server-side virtualization, the advances of the capabilities of embedded processors make virtualization available on various systems much wider than before. The diversity of the target systems demands new design approaches considering the characteristics of the systems. In this dissertation, we propose the idea of optimizing virtualization environments through hardware/software co-design, and demonstrate the potential power of hardware/software co-design through the development of a new optimization technique for memory virtualization. Based on the existing studies, we recognize the memory subsystem as a major bottleneck of a virtualization environment. Therefore, we concentrate our efforts on optimizing memory virtualization for a specific type of virtualization environments as a working example. We first present a quantitative analysis of the impacts of memory virtualization. We then propose an optimized memory virtualization technique along with a comprehensive evaluation including the qualitative analysis with a formal proof and the quantitative analysis based on software emulation and hardware simulation. The results suggest the proposed technique outperforms the existing technique. The research points out hardware/software co-design is a promising direction for optimizing virtualization for the emerging applications.

摘要 i
Abstract ii
1 Introduction 1
1.1 Overview ................................. 2
1.2 Challenges of the Emerging Applications of Virtualization . . . . . . . 6
1.3 Scope................................... 8
1.4 Contributions ............................... 10
1.5 DissertationOutline............................ 12
2 Background 13
2.1 VirtualizationEnvironment........................ 13
2.2 Operating-system-levelVirtualization .................. 16
2.3 MemoryVirtualization .......................... 17
2.3.1 NestedPaging .......................... 18
2.3.2 VariantsofNestedPaging .................... 20
3 Literature Review 24
4 A Non-invasive Analysis of the Impacts of Memory Virtualization 29
4.1 Design................................... 30
4.1.1 PageTableTracing........................ 33
4.1.2 FormatoftheTraceFiles..................... 36
4.1.3 ImplementationConsiderations ................. 38
4.2 Evaluation................................. 42
4.2.1 Methodology ........................... 42
4.2.2 Results .............................. 47
4.2.3 PenaltyoftheStage2Translation ................ 50
4.3 Summary ................................. 52
5 oPT: An Optimized Two-stage Page Translation 53
5.1 Design................................... 54
5.1.1 ComparisonwithNestedPaging................. 57
5.1.2 ImplementationConsiderations ................. 59
5.2 ProofofCorrectness ........................... 63
5.3 Evaluation with Software Emulation on a VMM-independent
Environment ............................... 70
5.3.1 Methodology ........................... 70
5.3.2 Results .............................. 72
5.4 Evaluation with the Non-invasive Analysis Framework on a Practical VirtualizationEnvironment........................ 79
5.5 Relaxation................................. 83
5.6 Summary ................................. 84
6 Micro-Level Evaluation of oPT with Hardware Metrics 86
6.1 Methodology ............................... 87
6.1.1 FPGATechnology ........................ 88
6.2 DesignofthePrototypes ......................... 89
6.2.1 bTLB............................... 89
6.2.2 ExtendedMMU ......................... 91
6.3 Post-routeSimulation........................... 95
6.4 Remarks.................................. 98
7 Conclusions 100
7.1 SummaryoftheResults.......................... 101
7.2 ResearchLimitationsandFutureWork.................. 102
Bibliography 104

[1] R. A. Meyer and L. H. Seawright, “A virtual machine time-sharing system,” IBM Syst. J., vol. 9, no. 3, pp. 199–218, Sep. 1970.
[2] S. Potter, J. Nieh, and M. Selsky, “Secure isolation of untrusted legacy applica- tions,” in Proc. 21st Conference on Large Installation System Administration Con- ference, ser. LISA’07, 2007, pp. 10:1–10:14.
[3] M. Pearce, S. Zeadally, and R. Hunt, “Virtualization: Issues, security threats, and solutions,” ACM Comput. Surv., vol. 45, no. 2, pp. 17:1–17:39, Mar. 2013.
[4] J. Daniels, “Server virtualization architecture and implementation,” Crossroads, vol. 16, no. 1, pp. 8–12, Sep. 2009.
[5] W. Vogels, “Beyond server consolidation,” Queue, vol. 6, no. 1, pp. 20–26, Jan. 2008.
[6] G. Heiser, “The role of virtualization in embedded systems,” in Proceedings of the 1st Workshop on Isolation and Integration in Embedded Systems, ser. IIES ’08. New York, NY, USA: ACM, 2008, pp. 11–16.
[7] J. Shuja, A. Gani, K. Bilal, A. U. R. Khan, S. A. Madani, S. U. Khan, and A. Y. Zomaya, “A survey of mobile device virtualization: Taxonomy and state of the art,” ACM Comput. Surv., vol. 49, no. 1, pp. 1:1–1:36, Apr. 2016.
[8] A. Agarwal, J. Govindaraj, N. Juneja, and V. Naik, “Feasibility study of on-device and in-the-cloud virtualization of mobiles,” in Proceedings of the 5th IBM Collaborative Academia Research Exchange Workshop, ser. I-CARE
’13. New York, NY, USA: ACM, 2013, pp. 5:1–5:4. [Online]. Available: http://doi.acm.org/10.1145/2528228.2528234
[9] T. Gaska, B. Werner, and D. Flagg, “Applying virtualization to avionics systems – the integration challenges,” in 29th Digital Avionics Systems Conference, Oct 2010, pp. 5.E.1–1–5.E.1–19.
[10] Intel,“Applyingmulti-coreandvirtualizationtoindustrialandsafety-relatedappli- cations,” Intel, Tech. Rep., 2009.
[11] F. Reichenbach and A. Wold, “Multi-core technology – next evolution step in safety critical systems for industrial applications?” in Proceedings of the 2010 13th Euromicro Conference on Digital System Design: Architectures, Methods
and Tools, ser. DSD ’10. Washington, DC, USA: IEEE Computer Society, 2010, pp. 339–346. [Online]. Available: http://dx.doi.org/10.1109/DSD.2010.50
[12] A. Moga, T. Sivanthi, and C. Franke, “Os-level virtualization for industrial automation systems: Are we there yet?” in Proceedings of the 31st Annual ACM Symposium on Applied Computing, ser. SAC ’16. New York, NY, USA: ACM, 2016, pp. 1838–1843. [Online]. Available: http://doi.acm.org/10.1145/2851613. 2851737
[13] M.Lee,A.S.Krishnakumar,P.Krishnan,N.Singh,andS.Yajnik,“Supportingsoft real-time tasks in the xen hypervisor,” SIGPLAN Not., vol. 45, no. 7, pp. 97–108, Mar. 2010.
[14] S. Govindan, J. Choi, A. R. Nath, A. Das, B. Urgaonkar, and A. Sivasubramaniam, “Xen and co.: Communication-aware cpu management in consolidated xen-based hosting platforms,” IEEE Trans. Comput., vol. 58, no. 8, pp. 1111–1125, Aug. 2009.
[15] I. Goiri, F. Julia, R. Nou, J. L. Berral, J. Guitart, and J. Torres, “Energy-aware scheduling in virtualized datacenters,” in Proc. 2010 IEEE Int. Conf. on Cluster Computing, ser. CLUSTER ’10, 2010, pp. 58–67.
[16] W.Zhao,Z.Wang,andY.Luo,“Dynamicmemorybalancingforvirtualmachines,” SIGOPS Oper. Syst. Rev., vol. 43, no. 3, pp. 37–47, Jul. 2009.
[17] D.-J.Kang,C.-Y.Kim,K.-H.Kim,andS.-I.Jung,“Proportionaldiski/obandwidth management for server virtualization environment,” in Proc. 2008 Int. Conf. on Computer Science and Information Technology, ser. ICCSIT ’08, 2008, pp. 647– 653.
[18] M. Grund, J. Schaffner, J. Krueger, J. Brunnert, and A. Zeier, “The effects of vir- tualization on main memory systems,” in Proceedings of the Sixth International Workshop on Data Management on New Hardware, ser. DaMoN ’10. New York, NY, USA: ACM, 2010, pp. 41–46.
[19] D.A.PattersonandJ.L.Hennessy,Eds.,ComputerOrganizationandDesignARM Edition: The Hardware Software Interface, 1st ed. Morgan Kaufmann, 2016.
[20] K.G.ShinandP.Ramanathan,“Real-timecomputing:anewdisciplineofcomputer science and engineering,” Proceedings of the IEEE, vol. 82, no. 1, pp. 6–24, Jan. 1994.
[21] G. J. Popek and R. P. Goldberg, “Formal requirements for virtualizable third gen- eration architectures,” Commun. ACM, vol. 17, no. 7, pp. 412–421, Jul. 1974.
[22] R. Uhlig, G. Neiger, D. Rodgers, A. L. Santoni, F. C. M. Martins, A. V. Anderson, S. M. Bennett, A. Kagi, F. H. Leung, and L. Smith, “Intel virtualization technology,” Computer, vol. 38, no. 5, pp. 48–56, May 2005.
[23] “Amd virtualization,” 2014. [Online]. Available: http://www.amd.com/en-us/ solutions/servers/virtualization
[24] ARM, ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile, a.j ed., 2016.
[25] R. P. Goldberg and R. Hassinger, “The double paging anomaly,” in Proceedings of the May 6-10, 1974, National Computer Conference and Exposition, ser. AFIPS
’74. New York, NY, USA: ACM, 1974, pp. 195–199.
[26] F.J.Corbató,M.Merwin-Daggett,andR.C.Daley,“Anexperimentaltime-sharing system,” in Proceedings of the May 1-3, 1962, Spring Joint Computer Conference, ser. AIEE-IRE ’62 (Spring). New York, NY, USA: ACM, 1962, pp. 335–344.
[27] D. Ung and C. Cifuentes, “Machine-adaptable dynamic binary translation,” SIG- PLAN Not., vol. 35, no. 7, pp. 41–51, Jan. 2000.
[28] J. Sugerman, G. Venkitachalam, and B.-H. Lim, “Virtualizing i/o devices on vmware workstation’s hosted virtual machine monitor,” in Proc. General Track: 2002 USENIX Annual Technical Conference, 2001, pp. 1–14.
[29] C. A. Waldspurger, “Memory resource management in vmware esx server,” SIGOPS Oper. Syst. Rev., vol. 36, no. SI, pp. 181–194, Dec. 2002.
[30] D. J. Magenheimer and T. W. Christian, “vblades: Optimized paravirtualization for the itanium processor family,” in Proc. 3rd Conference on Virtual Machine Re- search And Technology Symposium - Volume 3, ser. VM’04, 2004, pp. 6–6.
[31] A. Whitaker, M. Shaw, and S. Gribble, “Denali: Lightweight virtual machines for distributed and networked applications,” in Proceedings of the 2002 USENIX An- nual Technical Conference, 2002.
[32] C.Weng,Z.Wang,M.Li,andX.Lu,“Thehybridschedulingframeworkforvirtual machine systems,” in Proceedings of the 2009 ACM SIGPLAN/SIGOPS Interna- tional Conference on Virtual Execution Environments, ser. VEE ’09. New York, NY, USA: ACM, 2009, pp. 111–120.
[33] B. Pham, J. Veselý, G. H. Loh, and A. Bhattacharjee, “Large pages and lightweight memory management in virtualized environments: Can you have it both ways?” in Proceedings of the 48th International Symposium on Microarchitecture, ser. MICRO-48. New York, NY, USA: ACM, 2015, pp. 1–12.
[34] S.Adabala,V.Chadha,P.Chawla,R.Figueiredo,J.Fortes,I.Krsul,A.Matsunaga, M. Tsugawa, J. Zhang, M. Zhao, L. Zhu, and X. Zhu, “From virtualized resources to virtual computing grids: The in-vigo system,” Future Gener. Comput. Syst., vol. 21, no. 6, pp. 896–909, Jun. 2005. [Online]. Available: http://dx.doi.org/10.1016/j.future.2003.12.021
[35] H. Inoue, J. Sakai, and M. Edahiro, “Processor virtualization for secure mobile terminals,” ACM Trans. Des. Autom. Electron. Syst., vol. 13, no. 3, pp. 48:1–48:23, Jul. 2008.
[36] S.-M.Lee,S.-B.Suh,andJ.-D.Choi,“Fine-grainedi/oaccesscontrolbasedonxen virtualization for 3g/4g mobile devices,” in Proc. 47th Design Automation Confer- ence, ser. DAC ’10, 2010, pp. 108–113.
[37] K. Gudeth, M. Pirretti, K. Hoeper, and R. Buskey, “Delivering secure applications on commercial mobile devices: The case for bare metal hypervisors,” in Proc. 1st ACM Workshop on Security and Privacy in Smartphones and Mobile Devices, ser. SPSM ’11, 2011, pp. 33–38.
[38] L. P. Cox and P. M. Chen, “Pocket hypervisors: Opportunities and challenges,” in
Proc. 8th IEEE Workshop on Mobile Computing Systems and Applications (HOT- MOBILE ’07), ser. HOTMOBILE ’07, 2007, pp. 46–50.
[39] K. Barr, P. Bungale, S. Deasy, V. Gyuris, P. Hung, C. Newell, H. Tuch, and B. Zoppis, “The vmware mobile virtualization platform: Is that a hypervisor in your pocket?” SIGOPS Oper. Syst. Rev., vol. 44, no. 4, pp. 124–135, Dec. 2010.
[40] J. Bickford and R. Cáceres, “Towards synchronization of live virtual machines among mobile devices,” in Proc. 14th Workshop on Mobile Computing Systems and Applications, ser. HotMobile ’13, 2013, pp. 13:1–13:6.
[41] A. Crespo, I. Ripoll, and M. Masmano, “Partitioned embedded architecture based on hypervisor: The xtratum approach,” in Proceedings of the 2010 European Dependable Computing Conference, ser. EDCC ’10. Washington, DC, USA: IEEE Computer Society, 2010, pp. 67–72. [Online]. Available: http://dx.doi.org/10.1109/EDCC.2010.18
[42] F. Bruns, D. Kuschnerus, and A. Bilgic, “Virtualization for safety-critical, deeply-embedded devices,” in Proceedings of the 28th Annual ACM Symposium on Applied Computing, ser. SAC ’13. New York, NY, USA: ACM, 2013, pp. 1485–1492. [Online]. Available: http://doi.acm.org/10.1145/2480362.2480640
[43] M. García-Valls, T. Cucinotta, and C. Lu, “Challenges in real-time virtualization and predictable cloud computing,” J. Syst. Archit., vol. 60, no. 9, pp. 726–740, Oct. 2014. [Online]. Available: http://dx.doi.org/10.1016/j.sysarc.2014.07.004
[44] L. Zhou, S. Wu, H. Sun, H. Jin, and X. Shi, “Supporting parallel soft real-time applications in virtualized environment,” in Proceedings of the 22Nd International Symposium on High-performance Parallel and Distributed Computing, ser. HPDC
’13. New York, NY, USA: ACM, 2013, pp. 117–118. [Online]. Available: http://doi.acm.org/10.1145/2462902.2462926
[45] S. Xi, M. Xu, C. Lu, L. T. X. Phan, C. Gill, O. Sokolsky, and I. Lee, “Real-time multi-core virtual machine scheduling in xen,” in Proceedings of the 14th International Conference on Embedded Software. New York, NY, USA: ACM, 2014, pp. 27:1–27:10. [Online]. Available: http://doi.acm.org/10.1145/2656045. 2656066
[46] M. Drescher, V. Legout, A. Barbalace, and B. Ravindran, “A flattened hierarchical scheduler for real-time virtualization,” in Proceedings of the 13th International Conference on Embedded Software, ser. EMSOFT ’16. New York, NY, USA: ACM, 2016, pp. 12:1–12:10. [Online]. Available: http://doi.acm.org/10.1145/2968478.2968501
[47] K. Adams and O. Agesen, “A comparison of software and hardware techniques for x86 virtualization,” SIGARCH Comput. Archit. News, vol. 34, no. 5, pp. 2–13, Oct. 2006.
[48] N. Bhatia, “Performance evaluation of intel ept hardware assist,” VMware, Tech. Rep., 2009.
[49] R. Bhargava, B. Serebrin, F. Spadini, and S. Manne, “Accelerating two- dimensional page walks for virtualized systems,” in Proc. 13th Int. Conf. on Ar- chitectural Support for Programming Languages and Operating Systems, ser. AS- PLOS XIII, 2008, pp. 26–35.
[50] X. Wang, J. Zang, Z. Wang, Y. Luo, and X. Li, “Selective hardware/software mem- ory virtualization,” SIGPLAN Not., vol. 46, no. 7, pp. 217–226, Mar. 2011.
[51] J.Ahn,S.Jin,andJ.Huh,“Revisitinghardware-assistedpagewalksforvirtualized systems,” in Proc. 39th Annual International Symposium on Computer Architec- ture, ser. ISCA ’12, 2012, pp. 476–487.
[52] J. Gandhi, M. D. Hill, and M. M. Swift, “Agile paging for efficient memory virtu- alization,” IEEE Micro, vol. 37, no. 3, pp. 80–86, 2017.
[53] J. Gandhi, A. Basu, M. D. Hill, and M. M. Swift, “Efficient memory virtualization: Reducing dimensionality of nested page walks,” in Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO-47. Washington, DC, USA: IEEE Computer Society, 2014, pp. 178–189. [Online]. Available: http://dx.doi.org/10.1109/MICRO.2014.37
[54] Y.-C. Lee and C.-W. Hsueh, “An optimized page translation for mobile virtualiza- tion,” in Proc. 50th Annual Design Automation Conference, ser. DAC ’13, 2013, pp. 85:1–85:6.
[55] G. Hoang, C. Bae, J. Lange, L. Zhang, P. Dinda, and R. Joseph, “A case for alter- native nested paging models for virtualized systems,” IEEE Comput. Archit. Lett., vol. 9, no. 1, pp. 17–20, Jan. 2010.
[56] T. W. Barr, A. L. Cox, and S. Rixner, “Translation caching: Skip, don’t walk (the page table),” SIGARCH Comput. Archit. News, vol. 38, no. 3, pp. 48–59, Jun. 2010.
[57] G. Venkatasubramanian, R. J. Figueiredo, R. Illikkal, and D. Newell, “Tmt - a tlb tag management framework for virtualized platforms,” in Proceedings of the 2009 21st International Symposium on Computer Architecture and High Performance Computing, ser. SBAC-PAD ’09. Washington, DC, USA: IEEE Computer Society, 2009, pp. 153–160.
[58] B. Pham, V. Vaidyanathan, A. Jaleel, and A. Bhattacharjee, “Colt: Coalesced large- reach tlbs,” in Proc. 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO-45, 2012, pp. 258–269.
[59] J. Du, N. Sehrawat, and W. Zwaenepoel, “Performance profiling in a virtualized environment,” in Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing, ser. HotCloud’10. Berkeley, CA, USA: USENIX Association, 2010, pp. 2–2.
[60] H. Mousa, K. Doshi, T. Sherwood, and E. Ould-Ahmed-Vall, “Vrtprof: Vertical profiling for system virtualization,” in 2010 43rd Hawaii International Conference on System Sciences, Jan 2010, pp. 1–10.
[61] R. Nikolaev and G. Back, “Perfctr-xen: A framework for performance counter virtualization,” SIGPLAN Not., vol. 46, no. 7, pp. 15–26, Mar. 2011. [Online]. Available: http://doi.acm.org/10.1145/2007477.1952687
[62] J. Stärner and L. Asplund, “Measuring the cache interference cost in preemptive real-time systems,” SIGPLAN Not., vol. 39, no. 7, pp. 146–154, Jun. 2004. [Online]. Available: http://doi.acm.org/10.1145/998300.997184
[63] G. Gracioli, A. Alhammad, R. Mancuso, A. A. Fröhlich, and R. Pellizzoni, “A survey on cache management mechanisms for real-time embedded systems,” ACM Comput. Surv., vol. 48, no. 2, pp. 32:1–32:36, Nov. 2015. [Online]. Available: http://doi.acm.org/10.1145/2830555
[64] F.Bellard,“Qemu,afastandportabledynamictranslator,”inProc.AnnualConfer- ence on USENIX Annual Technical Conference, ser. ATEC ’05, 2005, pp. 41–41.
[65] Xilinx, “the website of xilinx qemu,” http://www.wiki.xilinx.com/QEMU, 2017, accessed: 2017-01-30.
[66] P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, “Xen and the art of virtualization,” SIGOPS Oper. Syst. Rev., vol. 37, no. 5, pp. 164–177, Oct. 2003. [Online]. Available: http://doi.acm.org/10.1145/1165389.945462
[67] M. Cereia and I. C. Bertolotti, “Virtual processors for industrial applications,” in 2005 IEEE Conference on Emerging Technologies and Factory Automation, Sept 2005, pp. 323–330.
[68] Intel,“Achievingreal-timeperformanceonavirtualizedindustrialcontrolplatform: White paper,” Intel, Tech. Rep. 330740, Jul. 2014.
[69] J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper, “The Mälardalen WCET benchmarks – past, present and future,” in WCET2010, B. Lisper, Ed. Brussels, Belgium: OCG, Jul. 2010, pp. 137–147.
[70] FreeRTOS, “the website of freertos,” http://www.freertos.org, 2017, accessed: 2017-01-30.
[71] ARM,ARMCortex-A53MPCoreProcessorTechnicalReferenceManual,r0p4ed., 2016.
[72] D. L. Willick, D. L. Eager, and R. B. Bunt, “Disk cache replacement policies for network fileservers,” Saskatoon, Sask., Canada, Canada, Tech. Rep., 1992.
[73] R. P. Foundation, “the website of raspberry pi,” https://www.raspberrypi.org, ac- cessed: 2017-01-30.
[74] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, no. 1, pp. 46–61, Jan. 1973.