用權重參照計數演算法執行主動物件垃圾收集

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：144

、訪客IP：3.141.35.60

姓名

宋定遠(Ting-yuan Sung) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

用權重參照計數演算法執行主動物件垃圾收集
(Actor Garbage Collection Using Weighted Reference Counting.)

相關論文

★ 以伸展樹為基礎的Android Binder Driver	★ 應用增量式學習於多種農作物判釋之研究
★ 應用分類重建學習偵測航照圖幅中的新穎坵塊	★ 一個建立在平行工作系統上的動態全球計算平台
★ 一個動態負載平衡之最大可能性估算計算架構	★ 利用多項系統負載資訊進行動態P2P系統重組的策略研究
★ 基於Hadoop系統的雲端應用程式特徵擷取與計算監測架構	★ 適用於大型動態分散式系統的調適性計算模型
★ 一個提供彈性虛擬資料中心的雲端服務平台	★ 雲端彈性虛擬機房服務平台之資源控管中心
★ 一個適用於自動供應雲端系統的動態調適計算架構	★ 線性相關工作與非相關工作的探索式排程策略
★ 適用於大資料集高效率的分散式階層分群演算法	★ 混合雲端環境上的多重代理人動態調適計算管理架構
★ 基於圖形的平行化最小生成樹分群演算法	★ 基於密度的超立方體覆蓋之啟發式演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著計算資源成本的降低和網際網路的普及，建置分散式系統的門檻已大大的降低了，許多以分散式計算為基礎的新型服務也應運而生，因此設計分散式系統時對於自動化管理和可程式化的需求也因此而提高了；為了提高實作分散式系統時的便利性我們引入了主動物件計算模型的概念，希望能藉此降低實作分散式程式的困難度。此外，我們也建議使用自動化記憶體管理機制來減輕人為控制可能產生的風險並進而提昇系統的穩定度。
然而，主動物件計算模型的特性可能會使垃圾收集機制發生誤差，例如，不同步訊息傳遞會使垃圾收集演算法產生競賽情況，這會降低自動化記憶體管理的正確性。因此為了使垃圾收集機制能完全整合在主動物件計算模型之中，我們提出了權重參照計數演算法，並針對可能的錯誤做了必要的修改。最後，我們會藉由比較使用各種垃圾收集機制時程式的執行速度和可用記憶體的容量來彰顯權重參照計數演算法的成效。

摘要(英)

In the past decade, the cost of computational resources is getting lower
while the computing power of them is getting better. Meanwhile, Internet
connects numerous computational resources and promotes the use of
distributed computing. To facilitate the development of distributed
computing applications, automatics resource management and
programmability are critical to help build distributed systems. Automatic
garbage collection simplifies memory management and improves
programmability. It reclaims garbage memory cells automatically and has
been used in many distributed programming languages such as Java. The
idea of automatics garbage collection can apply to the actor model, a
distributed model that reasons about distributed systems with the properties
of encapsulated state, autonomous computing, and asynchronous
communication. Unfortunately, the properties of the actor model prevent
direct use of traditional garbage collection algorithms in actor-based
systems.
In this thesis, we present a distributed actor garbage collection algorithm
and implement it in an actor-based programming language, SALSA. The
algorithm adopts weighted reference counting of traditional distributed
garbage collection because it generates few systems messages. We add new
mechanisms in the algorithm to support distributed actor garbage collection
which generates the same number of system messages as that of the
traditional weighted reference counting algorithm. Our experimental results
show that our implementation is practical for actor-based systems.

關鍵字(中)

★ 主動物件計算計算模型
★ 權重參照計數
★ 垃圾收集

關鍵字(英)

★ Actor Model
★ Garbage Collection
★ Weighted Reference Counting

論文目次

第一章　緒論　..........................................　1
1.1　垃圾收集(Garbage　Collection,　GC)　...............　3
1.2　簡介權重參照計數　.................................　5
1.3　研究動機　.........................................　6
1.4　研究目的　.........................................　7
1.5　研究挑戰　.........................................　8
1.6　研究成果與貢獻　..................................　10
1.7　文章架構　........................................　10
Related　Work　........................................　11
第二章　主動物件垃圾定義　.............................　13
2.1　意圖運算　........................................　15
2.2　主動物件垃圾的操作型定義　........................　17
第三章　主動物件的權重參照計數演算法　.................　23
3.1　分散式垃圾收集演算法的可行性　....................　24
3.2　權重參照計數演算法　..............................　26
3.2.1　訊息保護機制　..................................　31
第四章　系統實作　.....................................　35
4.1　SALSA　程式語言　.................................　35
4.1.1　主動物件系統架構　..............................　36
4.2　實作權重參照計數演算法於SALSA　...................　41
第五章　實驗數據　.....................................　45
5.1　執行時間　........................................　46
5.2　可用記憶體容量的變化　............................　48
結論與未來方向　.......................................　51
參考文獻　.............................................　52

參考文獻

[1]　A.　Vardhan.　Distributed　garbage　collection　of　active　objects:　A　transformation　and　its　applications　to　java　programming.　Master’s　thesis,　UIUC,　Urbana　Champaig,　Illinois,　1998.
[2]　A.　Vardhan　and　G.　Agha.　Using　passive　object　garbage　collection　algorithms.　In　ISMM’02,　ACM　SIGPLAN　Notices,　pages　106-113,　Berlin,　June　2002.　ACM　Press.
[3]　C.　A.　Varela　and　G.　Agha.　Programming　dynamically　reconfigurable　open　systems　with　SALSA.　ACM　SIGPLAN　Notices.　OOPSLA’2001　ACM　Conference　on　Object-Oriented　Systems,　Languages　and　Applications,　36(12):20-34,　Dec.　2001.
[4]　David　F.　Bacon　,　V.　T.　Rajan,　Concurrent　Cycle　Collection　in　Reference　Counted　Systems,　Proceedings　of　the　15th　European　Conference　on　Object-Oriented　Programming,　p.207-235,　June　18-22,　2001.
[5]　D.　I.　Bevan,　Distributed　garbage　collection　using　reference　counting,　in　“Parallel　Architectures　and　Languages　Europe,”　Lecture　Notes　in　Computer　Science,　Vol.　258,　pp.　117-187,　Springer-Verlag,　Berlin/New　York,　1987.
[6]　D.　Kafura,　D.　Washabaugh,　and　J.　Nelson.　Garbage　collection　of　actors.　In　OOPSLA’90　ACM　Conference　on　Object-Oriented　Systems,　Languages　and　Applications,　pages　126-134.　ACM　Press,　October　1990.
[7]　Dmitry　Kogan,　Assaf　Schuster,　Remote　Reference　Counting:　Distributed　Garbage　Collection　with　Low　Communication　and　Computation　Overhead,　Journal　of　Parallel　and　Distributed　Computing,　Volume　60,　Issue　10,　October　2000,　Pages　1260-1292.
[8]　D.　Plainfosee　and　M.　Shapiro,　A　survey　of　distributed　garbage　collection　techniques,　in　“Second　Closed　BROADCAST　Workshop,　Bruxelles,　Belgique,　November　1994,”　Broadcast　Basic　Research　Action.
[9]　F.　Mattern.　Global　quiescence　detection　based　on　credit　distribution　and　recovery.　Inf.　Proc.　Lett.,　30(4):195-200,　1989.
[10]　G.　Agha.　Actors:　A　Model　of　Concurrent　Computation　in　Distributed　Systems.　MIT　Press,　1986.
[11]　Hewitt,　C.　Viewing　control　structures　as　patterns　of　passing　messages.　Journal　of　Artificial　Intelligence,　8(3):323-364,　June　1977.
[12]　JONES,　R.　E.,　AND　LINS,　R.　D.　Garbage　Collection.　John　Wiley　and　Sons,　1996.
[13]　K.　Rokusawa,　N.　Ichiyoshi,　T.　Chikayama,　and　H.Nakashima.　An　Efficient　Termination　Detection　and　Abortion　Algorithm　for　Distributed　Processing　Systems.　In　Proc.　Of　ICPP’　88,　volume1,　pages　18-22,　1988.
[14]　P.　Dickman.　Incremental,　distributed　orphan　detection　and　actor　garbage　collection　using　graph　partitioning　and　Euler　cycles.　In　WDAG’96,　volume　1151　of　Lecture　Notes　in　Computer　Science,　Bologna,　Oct.　1996.　Springer-Verlag.
[15]　P.　Watson　and　I.　Watson,　An　efficient　garbage　collection　scheme　for　parallel　computer　architecture,　in　“Parallel　Architectures　and　Languages　Europe,”　Lecture　Notes　in　Computer　Science,　Vol.　258,　pp.432-443,　Springer-Verlag,　Berlin/New　York,　1987.
[16]　Tomio　Kamada　,　Satoshi　Matsuoka　,　Akinori　Yonezawa,　Efficient　parallel　global　garbage　collection　on　massively　parallel　computers,　Proceedings　of　the　1994　conference　on　Supercomputing,　p.79-88,　December　1994,　Washington,　D.C.,　United　States.
[17]　Worldwide　Computing　Laboratory.　The　SALSA　Programming　Language,　2002.　Work　in　Progress.　http://www.cs.rpi.edu/wwc/salsa/　.
[18]　W.　Wang　and　C.　A.　Varela.　Distributed　garbage　collection　for　mobile　actor　systems:　The　pseudo　root　approach.　In　Advances　in　Grid　and　Pervasive　Computing,　First　International　Conference,　GPC　2006,　volume　3947　of　Lecture　Notes　in　Computer　Science,　pages　360-372.　Springer,　May　2006.
[19]　W.　Yu　and　A.　Cox,　Conservative　garbage　collection　on　distributed　shared　memory　system,　in　“Proc.　Of　the　16th　International　Conf.　on　Distributed　Computing　Systems,　Hong　Kong,　May　1996,”　pp.402-410,　Assoc.　Comput.　Mach.,　New　York.

指導教授

王尉任(Wei-jen Wang)

審核日期

2009-7-23

推文