??? 摘 要： 提出了一種對(duì)線(xiàn)程進(jìn)行合理分組的方法，即亞線(xiàn)程技術(shù)，并提出了動(dòng)態(tài)亞線(xiàn)程樹(shù)的設(shè)計(jì)思想" title="設(shè)計(jì)思想">設(shè)計(jì)思想和運(yùn)行機(jī)制。
??? 關(guān)鍵詞： 多線(xiàn)程? 亞線(xiàn)程? 動(dòng)態(tài)亞線(xiàn)程
?
??? 多線(xiàn)程是近年來(lái)非常流行的一項(xiàng)編程技術(shù)。尤其是在網(wǎng)絡(luò)傳輸和資源共享軟件的設(shè)計(jì)中，在多媒體的采集和處理、并行計(jì)算、并行處理等方面，更是由于高效性和可靠性要求而使線(xiàn)程技術(shù)得到廣泛使用。多線(xiàn)程技術(shù)保證了程序模塊間的分離度，而且可通過(guò)合理劃分功能模塊而減少通信量，實(shí)現(xiàn)廣泛的數(shù)據(jù)共享，從而使系統(tǒng)性能得到很大提高。
??? 但是，隨著線(xiàn)程數(shù)目的增多，共享數(shù)據(jù)的管理將變得相當(dāng)復(fù)雜。線(xiàn)程的增多導(dǎo)致對(duì)共享數(shù)據(jù)區(qū)的訪(fǎng)問(wèn)非常頻繁，從而增加了系統(tǒng)的額外開(kāi)銷(xiāo)。為此，本文提出了基于線(xiàn)程分組的亞線(xiàn)程機(jī)制。
??? 在設(shè)計(jì)中，只要分組合理，亞線(xiàn)程之間的調(diào)用就不會(huì)過(guò)于頻繁，從而可減少多個(gè)線(xiàn)程頻繁訪(fǎng)問(wèn)共享數(shù)據(jù)而引起的混亂。由此，亞線(xiàn)程機(jī)制可以有效地提高系統(tǒng)性能，同時(shí)保證數(shù)據(jù)的安全。
1 亞線(xiàn)程機(jī)制的設(shè)計(jì)思想
1.1 亞線(xiàn)程和亞線(xiàn)程樹(shù)
??? 亞線(xiàn)程在結(jié)構(gòu)上是基于線(xiàn)程的分組。每個(gè)亞線(xiàn)程由一定數(shù)目的線(xiàn)程和共享數(shù)據(jù)組成。編程時(shí)，把互相之間有緊密關(guān)系或存在頻繁通信關(guān)系的線(xiàn)程及共享數(shù)據(jù)分到同一個(gè)亞線(xiàn)程中。亞線(xiàn)程內(nèi)部的互相調(diào)用和通信幾乎不受限制，只有亞線(xiàn)程之間的訪(fǎng)問(wèn)會(huì)受到一定限制。
??? 一般說(shuō)，線(xiàn)程是被個(gè)別創(chuàng)建的。在亞線(xiàn)程機(jī)制中，每個(gè)線(xiàn)程被分到某個(gè)亞線(xiàn)程中，一旦確定，便不再改變。
??? 總之，亞線(xiàn)程可分為根亞線(xiàn)程和普通亞線(xiàn)程兩類(lèi)。最基本的亞線(xiàn)程叫根亞線(xiàn)程。若創(chuàng)建線(xiàn)程時(shí)不指定亞線(xiàn)程，該線(xiàn)程就會(huì)自動(dòng)歸屬于根亞線(xiàn)程。除了根亞線(xiàn)程之外的亞線(xiàn)程都是普通亞線(xiàn)程。
??? 在亞線(xiàn)程機(jī)制中，采用亞線(xiàn)程樹(shù)來(lái)實(shí)現(xiàn)總體設(shè)計(jì)。亞線(xiàn)程樹(shù)是程序中所有亞線(xiàn)程構(gòu)成的樹(shù)形結(jié)構(gòu)" title="樹(shù)形結(jié)構(gòu)">樹(shù)形結(jié)構(gòu)。在這種樹(shù)形結(jié)構(gòu)中，一個(gè)亞線(xiàn)程通常從屬于其它亞線(xiàn)程。所以，在構(gòu)建一個(gè)新的亞線(xiàn)程時(shí)，必須指定它從屬于哪個(gè)亞線(xiàn)程。若未指定，則會(huì)自動(dòng)歸屬于根亞線(xiàn)程。這樣，一個(gè)應(yīng)用程序" title="應(yīng)用程序">應(yīng)用程序中的所有亞線(xiàn)程最終都會(huì)直接或間接歸屬于根亞線(xiàn)程。
??? 亞線(xiàn)程樹(shù)結(jié)構(gòu)如圖1所示。
?
??? 在采用進(jìn)程-線(xiàn)程結(jié)構(gòu)的應(yīng)用程序中，亞線(xiàn)程是介于進(jìn)程和線(xiàn)程之間的中間結(jié)構(gòu)。實(shí)驗(yàn)表明，由于亞線(xiàn)程的加入，使系統(tǒng)效率得到很大提高。
1.2 亞線(xiàn)程機(jī)制的具體實(shí)例
??? 在本課題組完成的863項(xiàng)目《遠(yuǎn)程機(jī)器人控制系統(tǒng)》中采用了進(jìn)程-線(xiàn)程結(jié)構(gòu)，在此基礎(chǔ)上加入了亞線(xiàn)程后，形成進(jìn)程-亞線(xiàn)程-線(xiàn)程機(jī)制。
??? 此系統(tǒng)主要功能是：通過(guò)圖像傳輸和命令傳輸，對(duì)遠(yuǎn)程機(jī)器人進(jìn)行相應(yīng)控制，并通過(guò)加密技術(shù)實(shí)現(xiàn)對(duì)信息的即時(shí)加密。系統(tǒng)采用Client/Server結(jié)構(gòu)。表1和表2分別為Server端和Client端的線(xiàn)程和亞線(xiàn)程列表。
?
?
??? 在Server端，亞線(xiàn)程樹(shù)結(jié)構(gòu)如圖2所示。其中，圖像采集、圖像壓縮和圖像傳送三個(gè)線(xiàn)程的處理對(duì)象都是視頻文件；命令接收和命令執(zhí)行兩個(gè)線(xiàn)程的處理對(duì)象都是命令；文件加密線(xiàn)程和文件解密線(xiàn)程的處理對(duì)象都是文件；文字發(fā)送線(xiàn)程和文字接收線(xiàn)程則負(fù)責(zé)文字通信。基于上述特點(diǎn)，這些線(xiàn)程構(gòu)成了圖2所示的亞線(xiàn)程樹(shù)結(jié)構(gòu)。
?
??? 在Client端，程序運(yùn)行后，每連接一個(gè)機(jī)器人站點(diǎn)就建立一個(gè)進(jìn)程。每個(gè)進(jìn)程中的亞線(xiàn)程結(jié)構(gòu)如圖3所示。各亞線(xiàn)程的構(gòu)建方法與Server端類(lèi)似。
?
??? 加入亞線(xiàn)程機(jī)制后，亞線(xiàn)程間的數(shù)據(jù)訪(fǎng)問(wèn)受到限制。例如文字發(fā)送、接收線(xiàn)程和S/C同步線(xiàn)程基本不訪(fǎng)問(wèn)加密解密的文件，亞線(xiàn)程管理器" title="管理器">管理器甚至可以禁止這些線(xiàn)程去訪(fǎng)問(wèn)傳輸?shù)奈募Ｓ秩?，?duì)傳輸?shù)囊曨l數(shù)據(jù)，除了Server端的圖像采集、壓縮和傳送線(xiàn)程，以及Client端的圖像接收、解壓縮和顯示線(xiàn)程外，不能被其他任何線(xiàn)程訪(fǎng)問(wèn)。這樣，通過(guò)亞線(xiàn)程機(jī)制優(yōu)化了整個(gè)應(yīng)用程序的運(yùn)行，并保證了數(shù)據(jù)的安全。此外，由于主要操作都?xì)w為亞線(xiàn)程內(nèi)部操作，所以，大大提高了程序執(zhí)行的效率。
1.3 亞線(xiàn)程機(jī)制的特點(diǎn)
??? 亞線(xiàn)程機(jī)制的特點(diǎn)是，允許對(duì)一個(gè)亞線(xiàn)程中的所有線(xiàn)程同時(shí)操作。例如，可通過(guò)調(diào)用相應(yīng)的方法來(lái)設(shè)置其中所有線(xiàn)程的優(yōu)先級(jí)，也可以啟動(dòng)或阻塞所有線(xiàn)程。
??? 亞線(xiàn)程機(jī)制的另一重要特點(diǎn)是為安全性提供了很好前提。它通過(guò)分組來(lái)區(qū)分不同安全級(jí)別的線(xiàn)程，對(duì)不同亞線(xiàn)程中的線(xiàn)程進(jìn)行不同處理，還可以通過(guò)亞線(xiàn)程的分層結(jié)構(gòu)來(lái)支持不對(duì)等安全措施。在亞線(xiàn)程機(jī)制中，一個(gè)線(xiàn)程只能修改所屬亞線(xiàn)程樹(shù)中的其它線(xiàn)程，這種修改包括修改線(xiàn)程優(yōu)先級(jí)別和掛起或喚醒線(xiàn)程等操作。
??? 由于一個(gè)亞線(xiàn)程只能訪(fǎng)問(wèn)那些從自己的根亞線(xiàn)程樹(shù)分支出來(lái)的線(xiàn)程，而不能訪(fǎng)問(wèn)其他任何線(xiàn)程。因此，可有效保證數(shù)據(jù)的安全。
2 動(dòng)態(tài)亞線(xiàn)程樹(shù)的運(yùn)行機(jī)制
??? 動(dòng)態(tài)亞線(xiàn)程樹(shù)是對(duì)亞線(xiàn)程機(jī)制的進(jìn)一步優(yōu)化，它通過(guò)在亞線(xiàn)程結(jié)構(gòu)基礎(chǔ)上加入亞線(xiàn)程管理器和動(dòng)態(tài)亞線(xiàn)程機(jī)制來(lái)實(shí)現(xiàn)。
2.1?亞線(xiàn)程管理器
??? 亞線(xiàn)程管理器的功能是對(duì)亞線(xiàn)程進(jìn)行調(diào)控，它獨(dú)立于所有亞線(xiàn)程。
??? 具體設(shè)計(jì)時(shí)，亞線(xiàn)程管理器由一個(gè)表格和一個(gè)控制組件構(gòu)成。表格紀(jì)錄各種信息，具體內(nèi)容隨應(yīng)用程序不同而異。例如，包括亞線(xiàn)程間的交互信息，整個(gè)系統(tǒng)中包含的線(xiàn)程和亞線(xiàn)程名，各線(xiàn)程和亞線(xiàn)程對(duì)應(yīng)的父亞線(xiàn)程名，線(xiàn)程及亞線(xiàn)程之間的通信次數(shù)和頻率等?？刂平M件則根據(jù)這些信息做出相應(yīng)的調(diào)整。
2.2?動(dòng)態(tài)亞線(xiàn)程機(jī)制
??? 大多數(shù)情況下，在線(xiàn)程的整個(gè)生命周期中，基本功能、通信對(duì)象以及處理對(duì)象都較固定，因此，亞線(xiàn)程機(jī)制可以有效地優(yōu)化應(yīng)用程序的執(zhí)行效率。但有時(shí)有些線(xiàn)程的通信對(duì)象不固定，處理的對(duì)象也不固定。如果將這樣的線(xiàn)程永久歸入某一個(gè)亞線(xiàn)程，就會(huì)降低程序的執(zhí)行效率。
??? 動(dòng)態(tài)亞線(xiàn)程機(jī)制可以較好地解決這個(gè)問(wèn)題。動(dòng)態(tài)亞線(xiàn)程機(jī)制的核心是可以動(dòng)態(tài)地調(diào)整亞線(xiàn)程樹(shù)的內(nèi)部結(jié)構(gòu)。采用這種機(jī)制后，一個(gè)線(xiàn)程調(diào)用其它亞線(xiàn)程中的對(duì)象或者與其他亞線(xiàn)程通信后，相關(guān)線(xiàn)程的標(biāo)識(shí)符和通信次數(shù)會(huì)被根亞線(xiàn)程管理器紀(jì)錄下來(lái)。若此后多次發(fā)生類(lèi)似的通信，亞線(xiàn)程管理器就會(huì)據(jù)此對(duì)亞線(xiàn)程樹(shù)進(jìn)行調(diào)整，將該線(xiàn)程歸入聯(lián)系最多的亞線(xiàn)程中。另外，如果兩個(gè)亞線(xiàn)程之間出現(xiàn)頻繁通信，那么亞線(xiàn)程管理器會(huì)經(jīng)過(guò)評(píng)測(cè)和判斷來(lái)合并兩個(gè)亞線(xiàn)程。
??? 圖4是采用動(dòng)態(tài)亞線(xiàn)程機(jī)制時(shí)，亞線(xiàn)程樹(shù)調(diào)整結(jié)構(gòu)的簡(jiǎn)單示例。從圖4中可以看到，亞線(xiàn)程管理器統(tǒng)計(jì)結(jié)果中，線(xiàn)程6和亞線(xiàn)程1中的線(xiàn)程通信為20+15+17=42次，遠(yuǎn)遠(yuǎn)大于與亞線(xiàn)程2內(nèi)部的通信。這種情況下，亞線(xiàn)程管理器通過(guò)評(píng)測(cè)機(jī)構(gòu)會(huì)得出應(yīng)該調(diào)整結(jié)構(gòu)的判斷，于是將線(xiàn)程6歸入亞線(xiàn)程1中。
?
??? 具體說(shuō)，亞線(xiàn)程的調(diào)整有以下幾種類(lèi)型：
??? ①一段時(shí)間內(nèi)，T1不屬于Y2，但線(xiàn)程T1和亞線(xiàn)程Y2的通信明顯比較頻繁，這種情況下，T1應(yīng)歸入Y2。
??? ② 一段時(shí)間內(nèi)，線(xiàn)程T1與多個(gè)亞線(xiàn)程的通信都很頻繁，這種情況下應(yīng)將線(xiàn)程T1復(fù)制到那些亞線(xiàn)程中，即在相應(yīng)的亞線(xiàn)程中重新創(chuàng)建與T1相同的線(xiàn)程，并進(jìn)行相應(yīng)規(guī)劃。
??? ③ 一段時(shí)間內(nèi)，兩個(gè)亞線(xiàn)程Y1和Y2的相互通信非常頻繁，則將兩個(gè)亞線(xiàn)程進(jìn)行合并。
??? 隨著多線(xiàn)程的廣泛應(yīng)用，越來(lái)越需要有一種合理的管理機(jī)制來(lái)管理多線(xiàn)程以免造成調(diào)度的混亂。
??? 亞線(xiàn)程機(jī)制可以有效地管理應(yīng)用程序內(nèi)部多個(gè)線(xiàn)程之間的相互訪(fǎng)問(wèn)和調(diào)度。對(duì)應(yīng)的樹(shù)狀" title="樹(shù)狀">樹(shù)狀結(jié)構(gòu)保證了數(shù)據(jù)訪(fǎng)問(wèn)和信息交互的安全。通過(guò)動(dòng)態(tài)調(diào)整亞線(xiàn)程內(nèi)部結(jié)構(gòu)以及整個(gè)亞線(xiàn)程樹(shù)的樹(shù)狀結(jié)構(gòu)，又可以動(dòng)態(tài)優(yōu)化多線(xiàn)程應(yīng)用程序的整體性能。
參考文獻(xiàn)
1 Ian Foster. The Nexus Approach to Integrating Multithreading and Communication. Journal of Parallel and Distributed Computing, 1996
2 Koray ?魻ner, Luiz Barroso, Sasan Iman, etc. The Design?of RPM: An FPGA-based Multiprocessor Emulator, 1995
3 Ka Wong Chong, Yijie Han,Tak Wah Lam. On the Parallel Time Complexity of Undirected Connectivity and?Minimum Spanning Trees. SODA,ACM-SIAM Symposium? on Discrete Algorithms, 1999
4 Chen Huinan. An Object Oriented Multi-Thread Dialog?Model. The Journal of China Universities of Posts and?Telecommunications,1998；5（1）
5?James M. Barton Nawaf Bitar Silicon, A Scalable MultiDiscipline. Multiple-Processor Scheduling Framework for?IRIX, 1995