臺灣博碩士論文加值系統

隨著電子技術的不斷演進，消費性電子產品逐漸向多功能、小型化的方向去發展。嵌入式裝置也隨之蓬勃發展。為了充分發揮嵌入式裝置的性能，必需有效率地使用其有限的系統資源如CPU、記憶體等，設計良好的嵌入式作業系統就顯得非常的重要。
本實驗室開發了一套元件化嵌入式作業系統，叫做LyraOS。而LyraOS 中的網路元件LyraNET，將Zero-Copy 的概念設計在網路機制中，藉由這種方式減少網路傳輸過程中的資料複製，可以降低CPU 的處理時間以及減少記憶體的使用，亦可大幅增加網路的傳輸效能。LyraNET 提供了兩種Zero-Copy 網路機制：Simple Copy Elimination 與Enhanced Copy Elimination。兩者都是藉由DMA 與修改過的TCP/IP 通訊協定軟體，來達到避免資料複製的目的。LyraNET 和LyraOS 過去都是在DJGPP 開發環境中被開發出來的。為了能夠得到GCC 豐富的社群資源，LyraOS 先前已被移植到GCC 開發環境之下。而本論文的目的之一是將LyraNET 也移植到GCC 開發環境之下，並整合進LyraOS。然而，當初LyraOS 使用的開發環境其所使用的版本目前都已經過於老舊，不利於後續的開發與維護。所以我們分別將GCC 與GNU binutils 版本更新至4.4.5 與2.20.1-r1。
在本論文中，我們除了將LyraNET 移植到GCC 開發環境上並與LyraOS 整合，我們亦探討嵌入式作業系統的記憶體管理方式，因為嵌入式系統的資源通常都是很有限的，必需對記憶體做有效率的管理與使用。為了進一步提昇LyraNET 的記憶體使用效率，我們參考了Linux Slab allocator 的概念，實作了LyraOS object cache allocator，我們儘可能的減少記憶體碎斷(fragmentation) 來改進LyraOS 原先使用的Power of 2 的記憶體配置方式。當用於LyraNET 之中時，可以大大地節省網路傳輸過程中所耗費的記憶體資源。

As the evolving of electronic technology, consumer electronics are getting smaller and of diverse functions. The development of embedded systems also follows this trend. To maximize the strength of embedded systems, a well-designed embedded operating system is very important and should be designed to effectively utilize the limited system resources.
Our laboratory has developed a component-based embedded operating system named
LyraOS[1]. The network component of LyraOS, LyraNET[5], employs the concept of
Zero-Copy for reducing data copying in the process of network transmission. As a
consequence, CPU processing time and memory usage can thus be reduced. The
performance of network transmission can be greatly improved as well. LyraNET provides two kinds of Zero-Copy mechanisms: Simple Copy Elimination and Enhanced Copy Elimination. Both mechanisms avoid data copying by using DMA and modified TCP/IP communication stack. In the past, LyraNET and LyraOS were developed in the DJGPP[15] development environment. For the rich community resources of GCC[10], LyraOS has been transplanted from DJGPP development environment to GCC. One goal of our thesis is to transplant LyraNET from DJGPP development environment to GCC and integrate it with LyraOS. However, the version of these development environments our laboratory used is outdated. That impedes the work of developing and maintaining LyraNET in the future. Therefore, we update the version of GCC and GNU Binutils[18] to 4.4.5 and 2.20.1-r1, respectively.
In this thesis, besides transplanting LyraNET from DJGPP to GCC, we also study the
memory management methods of embedded systems. Since the system resource of an
embedded system is quite limited, memory should be utilized effectively. To improve the memory utilization of LyraNET, we refer to the concept of Linux Slab allocator and implement an object cache allocator which tries to reduce memory fragmentation as possible. It is also designed to improve the Power of two memory allocation method used in LyraOS. Using object cache allocator, LyraNET can save lots of memory space in network transmission as a result.

第一章 簡介 1
第二章 背景技術與相關研究 4
2.1 開發環境相關研究 4
2.1.1 GCC 4
2.1.2 DJGPP 5
2.1.3 GNU Binutils 5
2.2 LyraOS簡介 6
2.3 記憶體管理方式 7
2.3.1 Power of two記憶體管理機制 7
2.3.2 Buddy System 9
2.3.3 Linux slab allocator 13
2.4 相關研究 14
第三章 LyraOS網路機制 18
3.1 LyraNET 18
3.2 Zero-Copy機制 18
3.3 Simple Copy Elimination 28
3.4 Enhanced Copy Elimination 31
3.5 Page Swapping 和 Page Remapping 34
第四章 LyraNET的移植 36
4.1 DJGPP開發環境到GCC開發環境 36
4.2 Makefile的改寫 37
4.3 Compile Error及Warning Messages的處理 40
4.4 Link error Messages的處理 43
第五章 增進LyraOS記憶體管理機制之效能的實作 44
5.1 LyraOS記憶體管理機制 45
5.1.1 LyraOS實體記憶體管理機制 46
5.1.2 LyraOS動態記憶體管理機制 47
5.2 LyraOS object cache allocator記憶體管理機制之實作 50
5.3 LyraNET記憶體使用方式之改進 61
第六章 實驗環境與效能評估 64
6.1 實驗環境 64
6.2 記憶體使用量的評估 66
第七章 結論與未來工作 72

[1]LyraOS homepage, http at http://163.22.20.123/joannaResearch/LyraOS/index.htm.
[2]Z. Y. Cheng, M. L. Chiang, and R. C. Chang, “A Component Based Operating System for Resource Limited Embedded Devices”, IEEE International Symposium on Consumer Electronics (ISCE’2000), HongKong, Dec. 5-7, 2000.
[3]Bor-Yeh Shen and Mei-Ling Chiang, “A Server-side Pre-linking Mechanism for Updating Embedded Operating System Dynamically”, accepted by Journal of Information Science and Engineering, 2010.
[4]J. W. Chuang, K. S. Sew, M. L. Chiang, and R. C. Chang, “Integration of Linux Communication Stacks into Embedded Operating Systems”, International Computer Symposium (ICS’2000), ChaiYi, Taiwan, R.O.C., Dec. 6-8, 2000.
[5]Mei-Ling Chiang and Yun-Chen Lee, “LyraNET: A Zero-Copy TCP/IP Protocol Stack for Embedded Systems”, Real-Time Systems, Vol. 34, No. 1, pp. 5-18, Sep. 2006.
[6]H. K. Ting, C. R. Lo, M. L. Chiang, and R. C. Chang, “Adapting LINUX VFAT Filesystem To Embedded Operating Systems”, International Computer Symposium (ICS’2002), HwaLian, Taiwan, R.O.C., 2002.
[7]Mei-Ling Chiang and Ching-Ru Lo, “LyraFILE: A Component-Based VFAT File System for Embedded Systems”, International Journal of Embedded Systems, Vol. 2, Nos. 3/4, pp. 248-259, 2006.
[8]Chi-Wei Yang, Paul C. H. Lee, and R. C. Chang, “Reuse Linux Device Drivers in Embedded Systems”, Proceeding of the 1998 International Computer Symposium (ICS’98), Taiwan, 1998.
[9]Chun-Hui Chen, LyraDD: Design and Implementation of the Device Driver Model for Embedded Systems, Master Thesis, Department of Information Management, National Chi-Nan University, June 2004.
[10]GCC, the GNU Compiler Collection, http://gcc.gnu.org/.
[11]ARM architecture overviews, http://www.arm.com/products/CPUs/index.html.
[12]Alpha Architecture Reference Manual, http://download.majix.org/dec/alpha_arch_ref.pdf.
[13]The SPARC Architecture Manual Version 8, http://www.sparc.org/standards/V8.pdf.
[14]Intel x86-based architecture, http://www.intel.com/products/processor/index.htm.
[15]DJGPP, http://www.delorie.com/djgpp/.
[16]ELF Manual, http://www.skyfree.org/linux/references/ELF_Format.pdf.
[17]GNU, GRUB Project, http://www.gnu.org/software/grub/.
[18]GNU Binutils, http://www.gnu.org/s/binutils/.
[19]The GNU Assembler, http://tigcc.ticalc.org/doc/gnuasm.html.
[20]Using ld, The GNU linker, http://www.math.utah.edu/docs/info/ld_toc.html.
[21]Jean-Philippe Fassino, Jean-Bernard Stefani, Julia L. Lawall, and Gilles Muller, “Think: A Software Framework for Component-based Operating System Kernels”, Proceeding ATEC’02 Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, 2002.
[22]P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles, “Dynamic Storage Allocation, A Survey and Critical Review”, International Workshop on Memory Management, pp. 1-116, 1995.
[23]Claudia Salzberg Rodriguez, Gordon Fischer, and Steven Smolski, The Linux® Kernel Primer: A Top-Down Approach for x86 and PowerPC Architectures, Prentice Hall PTR, 2005-9-21.
[24]Hong Min, Sangho Yi, Yookun Cho, and Jiman Hong, “An efficient dynamic memory allocator for sensor operating systems”, Proceedings of the ACM symposium on Applied computing (SAC’07), 2007.
[25]Anthony J. Massa, Embedded Software Development with eCos, Prentice Hall PTR, 2002-11-25.
[26]μC/OS-II website, http://www.micrium.com/page/products/rtos/os-ii.
[27]Jean J. Labrosse, MicroC OS II: The Real Time Kernel, CMP Books, 2002
[28]Kuang-tse Hsiao, “Customized Dynamic Memory Management for Embedded Systems”, Master Thesis, 2009.
[29]Peter A. Steenkiste, “A systematic approach to host interface design for high-speed networks”, Computer, Volume 27, Issue 3, pp. 47-57, March 1994.
[30]3C90xC NICs Technical Reference, http://people.freebsd.org/~wpaul/3Com/3c90xc.pdf.
[31]Robert Mecklenburg, Managing Projects with GNU Make, 3rd edition, O’Reilly Media, November 2004.