丁德武

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

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

圖1 一個(gè)簡(jiǎn)單的函數(shù)調(diào)用圖

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

1 Linux內(nèi)核函數(shù)調(diào)用圖

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

圖2 Linux內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分

2 復(fù)雜網(wǎng)絡(luò)分析

2.1 重要結(jié)構(gòu)特征

我們首先分析了Linux內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的兩個(gè)重要結(jié)構(gòu)特征：

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

圖3 Linux內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的路徑長(zhǎng)度分布圖

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

圖4 Linux內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的度分布圖

3.2 關(guān)鍵函數(shù)分析

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

依據(jù)度中心化分析指標(biāo)（這里是總的度，表1給出了入度與出度的結(jié)果），排在前20位的關(guān)鍵函數(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內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的入度與出度中心化

依據(jù)介數(shù)中心化分析指標(biāo)（圖5），排在前20位的關(guān)鍵函數(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內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的介數(shù)中心化

依據(jù)緊密度中心化分析指標(biāo)（圖6），排在前20位 的 關(guān) 鍵 函 數(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內(nèi)核函數(shù)調(diào)用圖的巨強(qiáng)連通體部分的緊密度中心化

顯然，不同的中心化指標(biāo)確定的關(guān)鍵節(jié)點(diǎn)是不同的，我們從中選出最少有兩種中心化指標(biāo)同時(shí)確定其為關(guān)鍵節(jié)點(diǎn)的函數(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 小結(jié)

當(dāng)前，復(fù)雜網(wǎng)絡(luò)已經(jīng)被成功應(yīng)用于數(shù)學(xué)、物理學(xué)、生物學(xué)和社會(huì)學(xué)等多個(gè)學(xué)科領(lǐng)域[1-2]。本文考察了復(fù)雜網(wǎng)絡(luò)在軟件工程領(lǐng)域的應(yīng)用[3-4]。我們使用函數(shù)調(diào)用圖[5]分析了Linux內(nèi)核的源代碼結(jié)構(gòu)，完成了對(duì)其內(nèi)部重要拓?fù)浣Y(jié)構(gòu)特征的實(shí)證分析，同時(shí)也使用度、介數(shù)和緊密度中心化分析指標(biāo)等幾種主流的中心化分析方法考察了其中的關(guān)鍵函數(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)的復(fù)雜網(wǎng)絡(luò)研究進(jìn)展[J].力學(xué)進(jìn)展，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]丁德武，劉濤，陸克中.復(fù)雜網(wǎng)絡(luò)的中心化及其在代謝網(wǎng)絡(luò)中的應(yīng)用[J].計(jì)算機(jī)與應(yīng)用化學(xué)，2008，25:1508-1510.