臺灣博碩士論文加值系統

在本研究中，我們對Linux Kernel 3.0之後版本做靜態的複雜網路分析，計算各種網路性質隨時間的變化，並比較這些結果與2.6以前版本之異同。
我們也對整個Linux Kernel網路進行分類，藉由實際的編譯設定，挑選出符合真實情況的網路，並將arch和drivers目錄下的檔案分開討論，經過這些分類，更細部地分析了Linux Kernel網路的結構演化。

In this study, we analyze Linux kernels after version 3.0 by the complex network approach. The evolution of various network quantities such as degree exponents, clustering coefficients, and shortest paths are determined and compared with the results of the previous study for Linux kernels before versions 2.6.
We further reduce the entire Linux kernel networks to smaller networks according to compiler settings to ensure these smaller networks are complete networks for real situations. The networks constructed by files only in the directory of arch or drivers are also considered. These classifications of Linux kernel networks show more details of evolution of Linux Kernel structures.

目錄 i

Abstract iii

摘要 v

圖目錄 vii

第一章 導論 1

第二章 網路性質 3

第一節 網路的基本性質 3
2.1.1 相鄰矩陣 3
2.1.2 平均度數 6
2.1.3 度分佈 6
2.1.4 平均最短路徑長 7
2.1.5 平均群聚係數 8

第二節 基本網路模型 9
2.2.1 隨機網路模型 9
2.2.2 無尺度網路模型 10
2.2.3 小世界網路模型 10

第三章 研究對象與內容 13

第一節 Linux核心介紹 13
3.1.1 Linux起源 13
3.1.2 Linux特性 13
3.1.3 Linux核心結構 14

第二節 Linux 核心網路的定義 16
3.2.1 網路的節點 16
3.2.2 網路的連接 16
3.2.3 網路連接的範例 17

第三節 Linux Kernel網路性質分析 20
3.3.1 Linux Kernel網路大小與連接邊數 20
3.3.2 度分佈(degree distribution) 25
3.3.3 群聚係數(clustering coefficient) 32
3.3.4 平均最短路徑長(shortest path) 33
3.3.5 斜率(slope) 35

第四章 研究總結與未來工作 37

第一節 Linux Kernel網路的研究總結 37
第二節 未來工作 39

參考文獻 41

1. C. R. Myers, Software systems as complex networks Structure, function, and evolvability, Phys. Rev. E 68, 046114 (2003).
2. S. Jenkins and S. R. Kirk, Software architecture graphs as complex networks: A novel partitioning scheme to measure stability and evolution, Inform. Sci. 177, 2587-2601 (2007).
3. X. Zhang, D. Zheng, H. Li, and F. Wang, Analyzing open-source software systems as complex networks, Physica A 387, 6190-6200 (2008).
4. P. Bhattacharya, M. Iliofotou, I Neamtiu, and M. Faloutsos, Graph-based analysis and prediction for software evolution, in 34th ICSE, 419-429 (2012).
5. S. Valverde and R. V. Solé, Network motifs in computational graphs: A case study in software architecture, Phys. Rev. E 72, 026107 (2005).
6. S. Valverde and R. V. Solé, Hierarchical Small Worlds in Software Architecture, in Dynamics of Continuous Discrete and Impulsive Systems: B; Applications and Algorithms 14, 1-11 (2007).
7. L. Subelj and M. Bajec, Community structure of complex software systems: Analysis and applications, Physica A 390, 2968-2975 (2011).
8. K.-Y. Cai and B.-B. Yin, Software execution processes as an evolving complex network, Inform. Sci. 179, 1903-1928 (2009).
9. W. Pan, B. Li, Y. Ma, and J. Liu, Multi-granularity evolution analysis of software using complex network theory, J. Syst. Sci. Complex 32, 1068-1082 (2011).
10. K.-K. Yan, G. Fang, N. Bhardwaj, R. P. Alexander, and M. Gerstein, Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks, PNAS 107, 9186-9191 (2010).
11. 趙振飛, Linux核心程式網路之結構與演進, 東華大學應用物理所碩士論文 (2006).
12. P. Erdős and A. Rényi, On random graphs I., Publ. Math. 6, 290–297 (1959).
13. A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286, 509–512 (1999).
14. A. Clauset, C. R. Shalizi, and M. E. J. Newman, Power-Law Distributions in Empirical Data, Siam Rev. 51, 661-703 (2009).
15. 趙炯, Linux Kernel 完全剖析, 博碩文化 (2005).
16. R. Love, Linux Kernel Development, Addison-Wesley (2010).
17. G. Caldarelli and A. Vespignani, Large Scale Structure and Dynamics of Complex Networks, World Scientific (2007).
18. L. Wang, Z. Wang, C. Yang, L. Zhang, and Q. Ye, Linux Kernels as Complex Networks: A Novel Method to Study Evolution, in Proceedings of the 25th International Conference on Software Maintenance, Edmonton, 41−50 (2009).
19. G. Xiao and Z. Zheng, and H. Wang, Evolution of Linux operating system network, Physica A 466, 249-258 (2017).
20. A. Israeli and G. Feitelson, The Linux kernel as a case study in software evolution, J. Sys. Soft. 83, 485–501, (2010).