丁德武

（池州學院 數(shù)學與計算機科學系，安徽 池州 247000）

近年來，研究人員發(fā)現(xiàn)現(xiàn)實世界中的大多數(shù)復雜系統(tǒng)都可以用網(wǎng)絡來描述，即：使用節(jié)點來表示系統(tǒng)中的元素，使用連線來表示它們之間的關系[1]。在過去的十數(shù)年間，眾多的復雜網(wǎng)絡模型吸引了研究人員濃厚的興趣，也引領了諸如數(shù)學、物理學、生物學和社會學等多個學科領域的快速發(fā)展[1-2]。但是，計算機科學特別是軟件工程領域的復雜網(wǎng)絡研究還處于初期階段，當前的研究內容主要包括：對軟件系統(tǒng)的內部拓撲結構進行實證分析；對軟件系統(tǒng)的復雜性進行度量和評估；學習軟件系統(tǒng)的形成和演化過程；等等[3-4]。

圖1 一個簡單的函數(shù)調用圖

一般地，可以用節(jié)點表示大型軟件系統(tǒng)中的函數(shù)，用連線表示函數(shù)之間的調用關系（圖1）[5]。這種函數(shù)調用圖可以用來反映軟件系統(tǒng)中函數(shù)之間的調用關系，在程序理解、程序分析、軟件測試與維護等眾多軟件工程領域都有著廣泛的應用[5]，是該領域的一種重要復雜網(wǎng)絡模型[3-4]。本文從復雜網(wǎng)絡的角度，使用函數(shù)調用圖分析了Linux內核的源代碼結構，完成了對其內部重要拓撲結構特征的實證分析，同時也使用幾種主流的中心化分析方法考察了其中的關鍵函數(shù)。

1 Linux內核函數(shù)調用圖

我們首先獲取了一個Linux內核源碼，隨后以節(jié)點表示函數(shù)，節(jié)點間的連線表示函數(shù)之間的調用關系，構造了Linux內核的函數(shù)調用圖，該模型包含了12390個節(jié)點和 33553條連線[6]。隨后，我們依據(jù)復雜網(wǎng)絡的蝴蝶結結構特征，將Linux內核的函數(shù)調用圖分解成如下4個部分：巨強連通體，底物子集，產物子集和孤立子集?？紤]到復雜網(wǎng)絡的巨強連通體部分是網(wǎng)絡中最大的強連通分支，它決定了整個復雜網(wǎng)絡的拓撲結構特征；同時，為了使問題簡化，文章主要考察Linux內核的函數(shù)調用圖的巨強連通體部分，該部分包含了637個節(jié)點和1415 條連線（圖 2）。

圖2 Linux內核函數(shù)調用圖的巨強連通體部分

2 復雜網(wǎng)絡分析

2.1 重要結構特征

我們首先分析了Linux內核函數(shù)調用圖的巨強連通體部分的兩個重要結構特征：

（1）小世界性質，即網(wǎng)絡的平均路徑長度較小[7]。我們計算了該部分所有可達節(jié)點間的路徑長度（圖3），隨后計算出該網(wǎng)絡的平均路徑長度，結果為21。可見盡管網(wǎng)絡規(guī)模非常大，但是網(wǎng)絡的可達節(jié)點間的平均路徑長度較小，因此該網(wǎng)絡是一種特殊的小世界網(wǎng)絡。

圖3 Linux內核函數(shù)調用圖的巨強連通體部分的路徑長度分布圖

（2）無尺度性質，即節(jié)點的度分布P(k)遵循函數(shù)P(k)=ak-r(a>0，r>0)[7]。為了分析Linux內核函數(shù)調用圖的巨強連通體部分的度分布情況，我們首先統(tǒng)計了網(wǎng)絡中各節(jié)點的連接度（入度，出度，和總的度）。然后，根據(jù)這些數(shù)據(jù)，繪制出了網(wǎng)絡度分布的log-log圖（圖4）。得到的網(wǎng)絡連接度分布符合冪律分布，表明這些網(wǎng)絡均具有比較明顯的無尺度特性，是無尺度網(wǎng)絡。

圖4 Linux內核函數(shù)調用圖的巨強連通體部分的度分布圖

3.2 關鍵函數(shù)分析

一般地，復雜網(wǎng)絡中的關鍵元素可以通過網(wǎng)絡的中心化分析得到。這里，復雜網(wǎng)絡中節(jié)點的中心化程度主要是指依據(jù)一定原則為其分配的一個函數(shù)。當前已經提出多種中心化分析方法，例如：度中心化分析指標用網(wǎng)絡中每個節(jié)點的連線數(shù)來確定節(jié)點的重要程度，介數(shù)中心化分析指標用通過某節(jié)點的最短路徑數(shù)量來確定節(jié)點的重要程度，而緊密度中心化分析指標可用于識別網(wǎng)絡的核心和外圍部分，等等[8]。但是，研究表明單一的中心化分析指標往往是不太可靠的，需要綜合考慮多種中心化分析指標。這里，我們以度、介數(shù)和緊密度中心化分析指標考察了Linux內核函數(shù)調用圖的巨強連通體部分的關鍵節(jié)點，并綜合加以分析。

依據(jù)度中心化分析指標（這里是總的度，表1給出了入度與出度的結果），排在前20位的關鍵函數(shù) 是 ：printk，warn_on_slowpath，kmem_cache_free，put_page，kfree，kmem_cache_alloc，do_exit，do_filp_open，_cond_resched，__alloc_pages_internal，dput， futex_lock_pi， schedule， mntput_no_expire，audit_log_exit，mutex_unlock，up_read，wake_up_process，handle_mm_fault和 mutex_lock.

表1 Linux內核函數(shù)調用圖的巨強連通體部分的入度與出度中心化

依據(jù)介數(shù)中心化分析指標（圖5），排在前20位的關鍵函數(shù)是：schedule，math_state_restore，__switch_to，do_group_exit，do_exit，__alloc_pages_internal，cache_grow，cache_alloc_refill，kmem_getpages，kmem_cache_alloc，group_send_sig_info，check_kill_permission，__audit_signal_info，send_sigio，send_sigio_to_task，print_oops_end_marker，extract_entropy，kill_fasync，get_random_bytes 和__kill_fasync.

圖5 Linux內核函數(shù)調用圖的巨強連通體部分的介數(shù)中心化

依據(jù)緊密度中心化分析指標（圖6），排在前20位 的 關 鍵 函 數(shù) 是 ：do_exit，do_group_exit，math_state_restore，exit_mm，futex_wait，do_futex，futex_lock_pi，__switch_to，do_filp_open，schedule，get_user_pages， handle_mm_fault， sys_futex，rwsem_down_failed_common， audit_log_exit，__link_path_walk， audit_free， rt_mutex_slowlock，ptrace_stop和 filp_open。

圖6 Linux內核函數(shù)調用圖的巨強連通體部分的緊密度中心化

顯然，不同的中心化指標確定的關鍵節(jié)點是不同的，我們從中選出最少有兩種中心化指標同時確定其為關鍵節(jié)點的函數(shù)，它們是：do_exit，schedule，__alloc_pages_internal，__switch_to，audit_log_exit，do_filp_open，do_group_exit，futex_lock_pi，handle_mm_fault，kmem_cache_alloc 和 math_state_restore.

3 小結

當前，復雜網(wǎng)絡已經被成功應用于數(shù)學、物理學、生物學和社會學等多個學科領域[1-2]。本文考察了復雜網(wǎng)絡在軟件工程領域的應用[3-4]。我們使用函數(shù)調用圖[5]分析了Linux內核的源代碼結構，完成了對其內部重要拓撲結構特征的實證分析，同時也使用度、介數(shù)和緊密度中心化分析指標等幾種主流的中心化分析方法考察了其中的關鍵函數(shù)。

[1]Newman M E J.Complex systems:A survey[J].Am.J.Phys.，2011，79:800-810.

[2]Barabasi A L.Scale-free networks:a decade and beyond[J].Science，2009，325:412-413.

[3]Jenkins S and Kirk S R.Software architecture graphs as complex networks:A novel partitioning scheme to measure stability and evolution[J].Information Sciences，2007，177:2587-2601.

[4]李兵，馬于濤，劉靖，等.軟件系統(tǒng)的復雜網(wǎng)絡研究進展[J].力學進展，2008，25:805-814.

[5]Ryder B G.Constructing the call graph of a program[C]//IEEE transactions on software engineering，1979，SE-5:216-226.

[6]Yan K K，F(xiàn)ang G，Bhardwaj N，et al.，Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks[J].PNAS，2010，107:9186-9191.

[7]Wang X F and Chen G R.Complex networks:small-world，scale-free and beyond[J]//IEEE Circuits and Systems Magazine，2003(3):6–20.

[8]丁德武，劉濤，陸克中.復雜網(wǎng)絡的中心化及其在代謝網(wǎng)絡中的應用[J].計算機與應用化學，2008，25:1508-1510.