亞線(xiàn)程和動(dòng)態(tài)亞線(xiàn)程樹(shù)的設計與研究

摘　要：提出了一種對線(xiàn)程進(jìn)行合理分組的方法,即亞線(xiàn)程技術(shù),并提出了動(dòng)態(tài)亞線(xiàn)程樹(shù)的設計思想和運行機制。 

關(guān)鍵詞：多線(xiàn)程 亞線(xiàn)程 動(dòng)態(tài)亞線(xiàn)程 

多線(xiàn)程是近年來(lái)非常流行的一項編程技術(shù)。尤其是在網(wǎng)絡(luò )傳輸和資源共享軟件的設計中,在多媒體的采集和處理、并行計算、并行處理等方面,更是由于高效性和可靠性要求而使線(xiàn)程技術(shù)得到廣泛使用。多線(xiàn)程技術(shù)保證了程序模塊間的分離度,而且可通過(guò)合理劃分功能模塊而減少通信量,實(shí)現廣泛的數據共享,從而使系統性能得到很大提高。 

但是,隨著(zhù)線(xiàn)程數目的增多,共享數據的管理將變得相當復雜。線(xiàn)程的增多導致對共享數據區的訪(fǎng)問(wèn)非常頻繁,從而增加了系統的額外開(kāi)銷(xiāo)。為此,本文提出了基于線(xiàn)程分組的亞線(xiàn)程機制。 

在設計中,只要分組合理,亞線(xiàn)程之間的調用就不會(huì )過(guò)于頻繁,從而可減少多個(gè)線(xiàn)程頻繁訪(fǎng)問(wèn)共享數據而引起的混亂。由此,亞線(xiàn)程機制可以有效地提高系統性能,同時(shí)保證數據的安全。
 
1 亞線(xiàn)程機制的設計思想 

1.1 亞線(xiàn)程和亞線(xiàn)程樹(shù) 

亞線(xiàn)程在結構上是基于線(xiàn)程的分組。每個(gè)亞線(xiàn)程由一定數目的線(xiàn)程和共享數據組成。編程時(shí),把互相之間有緊密關(guān)系或存在頻繁通信關(guān)系的線(xiàn)程及共享數據分到同一個(gè)亞線(xiàn)程中。亞線(xiàn)程內部的互相調用和通信幾乎不受限制,只有亞線(xiàn)程之間的訪(fǎng)問(wèn)會(huì )受到一定限制。 

一般說(shuō),線(xiàn)程是被個(gè)別創(chuàng )建的。在亞線(xiàn)程機制中,每個(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)程機制中,采用亞線(xiàn)程樹(shù)來(lái)實(shí)現總體設計。亞線(xiàn)程樹(shù)是程序中所有亞線(xiàn)程構成的樹(shù)形結構。在這種樹(shù)形結構中,一個(gè)亞線(xiàn)程通常從屬于其它亞線(xiàn)程。所以,在構建一個(gè)新的亞線(xiàn)程時(shí),必須指定它從屬于哪個(gè)亞線(xiàn)程。若未指定,則會(huì )自動(dòng)歸屬于根亞線(xiàn)程。這樣,一個(gè)應用程序中的所有亞線(xiàn)程最終都會(huì )直接或間接歸屬于根亞線(xiàn)程。亞線(xiàn)程樹(shù)結構如圖1所示。

圖1 亞線(xiàn)程樹(shù)狀結構圖

在采用進(jìn)程-線(xiàn)程結構的應用程序中,亞線(xiàn)程是介于進(jìn)程和線(xiàn)程之間的中間結構。實(shí)驗表明,由于亞線(xiàn)程的加入,使系統效率得到很大提高。

1.2亞線(xiàn)程機制的具體實(shí)例

在本課題組完成的863項目《遠程機器人控制系統》中采用了進(jìn)程-線(xiàn)程結構,在此基礎上加入了亞線(xiàn)程后,形成進(jìn)程-亞線(xiàn)程-線(xiàn)程機制。
 
此系統主要功能是:通過(guò)圖像傳輸和命令傳輸,對遠程機器人進(jìn)行相應控制,并通過(guò)加密技術(shù)實(shí)現對信息的即時(shí)加密。系統采用Client/Server結構。表1和表2分別為Server端和Client端的線(xiàn)程和亞線(xiàn)程列表。

表1 Server端的線(xiàn)程和亞線(xiàn)程列表 

表2 Client端的線(xiàn)程和亞線(xiàn)程列表

圖2 遠程機器人控制系統Server端亞線(xiàn)程樹(shù)結構

圖3 遠程機器人控制系統Client端亞線(xiàn)程樹(shù)結構

在Client端,程序運行后,每連接一個(gè)機器人站點(diǎn)就建立一個(gè)進(jìn)程。每個(gè)進(jìn)程中的亞線(xiàn)程結構如圖3所示。各亞線(xiàn)程的構建方法與Server端類(lèi)似。 

加入亞線(xiàn)程機制后,亞線(xiàn)程間的數據訪(fǎng)問(wèn)受到限制。例如文字發(fā)送、接收線(xiàn)程和S/C同步線(xiàn)程基本不訪(fǎng)問(wèn)加密解密的文件,亞線(xiàn)程管理器甚至可以禁止這些線(xiàn)程去訪(fǎng)問(wèn)傳輸的文件。又如,對傳輸的視頻數據,除了Server端的圖像采集、壓縮和傳送線(xiàn)程,以及Client端的圖像接收、解壓縮和顯示線(xiàn)程外,不能被其他任何線(xiàn)程訪(fǎng)問(wèn)。這樣,通過(guò)亞線(xiàn)程機制優(yōu)化了整個(gè)應用程序的運行,并保證了數據的安全。此外,由于主要操作都歸為亞線(xiàn)程內部操作,所以,大大提高了程序執行的效率。 

1.3 亞線(xiàn)程機制的特點(diǎn) 

亞線(xiàn)程機制的特點(diǎn)是,允許對一個(gè)亞線(xiàn)程中的所有線(xiàn)程同時(shí)操作。例如,可通過(guò)調用相應的方法來(lái)設置其中所有線(xiàn)程的優(yōu)先級,也可以啟動(dòng)或阻塞所有線(xiàn)程。 

亞線(xiàn)程機制的另一重要特點(diǎn)是為安全性提供了很好前提。它通過(guò)分組來(lái)區分不同安全級別的線(xiàn)程,對不同亞線(xiàn)程中的線(xiàn)程進(jìn)行不同處理,還可以通過(guò)亞線(xiàn)程的分層結構來(lái)支持不對等安全措施。在亞線(xiàn)程機制中,一個(gè)線(xiàn)程只能修改所屬亞線(xiàn)程樹(shù)中的其它線(xiàn)程,這種修改包括修改線(xiàn)程優(yōu)先級別和掛起或喚醒線(xiàn)程等操作。 

由于一個(gè)亞線(xiàn)程只能訪(fǎng)問(wèn)那些從自己的根亞線(xiàn)程樹(shù)分支出來(lái)的線(xiàn)程,而不能訪(fǎng)問(wèn)其他任何線(xiàn)程。因此,可有效保證數據的安全。
 
2 動(dòng)態(tài)亞線(xiàn)程樹(shù)的運行機制 

動(dòng)態(tài)亞線(xiàn)程樹(shù)是對亞線(xiàn)程機制的進(jìn)一步優(yōu)化,它通過(guò)在亞線(xiàn)程結構基礎上加入亞線(xiàn)程管理器和動(dòng)態(tài)亞線(xiàn)程機制來(lái)實(shí)現。
 
2.1亞線(xiàn)程管理器 

亞線(xiàn)程管理器的功能是對亞線(xiàn)程進(jìn)行調控,它獨立于所有亞線(xiàn)程。 

具體設計時(shí),亞線(xiàn)程管理器由一個(gè)表格和一個(gè)控制組件構成。表格紀錄各種信息,具體內容隨應用程序不同而異。例如,包括亞線(xiàn)程間的交互信息,整個(gè)系統中包含的線(xiàn)程和亞線(xiàn)程名,各線(xiàn)程和亞線(xiàn)程對應的父亞線(xiàn)程名,線(xiàn)程及亞線(xiàn)程之間的通信次數和頻率等?？刂平M件則根據這些信息做出相應的調整。
 
2.2動(dòng)態(tài)亞線(xiàn)程機制 

大多數情況下,在線(xiàn)程的整個(gè)生命周期中,基本功能、通信對象以及處理對象都較固定,因此,亞線(xiàn)程機制可以有效地優(yōu)化應用程序的執行效率。但有時(shí)有些線(xiàn)程的通信對象不固定,處理的對象也不固定。如果將這樣的線(xiàn)程永久歸入某一個(gè)亞線(xiàn)程,就會(huì )降低程序的執行效率。
 
動(dòng)態(tài)亞線(xiàn)程機制可以較好地解決這個(gè)問(wèn)題。動(dòng)態(tài)亞線(xiàn)程機制的核心是可以動(dòng)態(tài)地調整亞線(xiàn)程樹(shù)的內部結構。采用這種機制后,一個(gè)線(xiàn)程調用其它亞線(xiàn)程中的對象或者與其他亞線(xiàn)程通信后,相關(guān)線(xiàn)程的標識符和通信次數會(huì )被根亞線(xiàn)程管理器紀錄下來(lái)。若此后多次發(fā)生類(lèi)似的通信,亞線(xiàn)程管理器就會(huì )據此對亞線(xiàn)程樹(shù)進(jìn)行調整,將該線(xiàn)程歸入聯(lián)系最多的亞線(xiàn)程中。另外,如果兩個(gè)亞線(xiàn)程之間出現頻繁通信,那么亞線(xiàn)程管理器會(huì )經(jīng)過(guò)評測和判斷來(lái)合并兩個(gè)亞線(xiàn)程。 

圖4 動(dòng)態(tài)亞線(xiàn)程的運行機制 

圖4是采用動(dòng)態(tài)亞線(xiàn)程機制時(shí),亞線(xiàn)程樹(shù)調整結構的簡(jiǎn)單示例。從圖4中可以看到,亞線(xiàn)程管理器統計結果中,線(xiàn)程6和亞線(xiàn)程1中的線(xiàn)程通信為20+15+17=42次,遠遠大于與亞線(xiàn)程2內部的通信。這種情況下,亞線(xiàn)程管理器通過(guò)評測機構會(huì )得出應該調整結構的判斷,于是將線(xiàn)程6歸入亞線(xiàn)程1中。 

具體說(shuō),亞線(xiàn)程的調整有以下幾種類(lèi)型: 
①一段時(shí)間內,T1不屬于Y2,但線(xiàn)程T1和亞線(xiàn)程Y2的通信明顯比較頻繁,這種情況下,T1應歸入Y2。 
② 一段時(shí)間內,線(xiàn)程T1與多個(gè)亞線(xiàn)程的通信都很頻繁,這種情況下應將線(xiàn)程T1復制到那些亞線(xiàn)程中,即在相應的亞線(xiàn)程中重新創(chuàng )建與T1相同的線(xiàn)程,并進(jìn)行相應規劃。 
③ 一段時(shí)間內,兩個(gè)亞線(xiàn)程Y1和Y2的相互通信非常頻繁,則將兩個(gè)亞線(xiàn)程進(jìn)行合并。 

隨著(zhù)多線(xiàn)程的廣泛應用,越來(lái)越需要有一種合理的管理機制來(lái)管理多線(xiàn)程以免造成調度的混亂。
 
亞線(xiàn)程機制可以有效地管理應用程序內部多個(gè)線(xiàn)程之間的相互訪(fǎng)問(wèn)和調度。對應的樹(shù)狀結構保證了數據訪(fǎng)問(wèn)和信息交互的安全。通過(guò)動(dòng)態(tài)調整亞線(xiàn)程內部結構以及整個(gè)亞線(xiàn)程樹(shù)的樹(shù)狀結構,又可以動(dòng)態(tài)優(yōu)化多線(xiàn)程應用程序的整體性能。
 
參考文獻 
1 Ian Foster. The Nexus Approach to Integrating Multithre-ading and Communication. Journal of   Parallel and Dis-tributed 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 Par-allel 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 Multi-Discipline. Multiple-Processor
  Scheduling Framework for IRIX, 1995