跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.86) 您好!臺灣時間:2025/02/09 00:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:紀柏雄
研究生(外文):Bo-Shiung Chi
論文名稱:使用馬可夫決策過程來改善Android記憶體使用效率
論文名稱(外文):Improving Android Memory Utilization using Markov Decision Processes
指導教授:楊正仁楊正仁引用關係
指導教授(外文):Cheng-Zen Yang
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:30
中文關鍵詞:馬可夫決策過程記憶體管理
外文關鍵詞:Markov Decision ProcessedMemory Management
相關次數:
  • 被引用被引用:0
  • 點閱點閱:401
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在Android系統中,資源管理的問題對使用表現有重要影響。而在眾多的資源當中,記憶體管理是影響最直接的部分。根據我們的觀察,Android系統當中的記憶體管理機制是基於最近最少使用演算法(LRU) 去管理記憶體回收。此外,並使用垃圾回收機制(Garbage Collection) 去回收空閒頁的記憶體。然而,由於在有限的記憶體空間中有越來越多的應用程式會被執行,目前的記憶體管理機制會造成應用程式載入時間拉長。因此在本論文中,我們使用馬可夫決策過程(Markov Decision Processes) 提出了一個預測式的記憶體管理機制,來改善Android系統上記憶體使用效率。本論文研究主要達成以下兩項貢獻:第一,基於馬可夫決策過程的記憶體管理機制可以有效率的在Android系統上提升記憶體使用率。第二,能有效減少後續執行應用程式時所需要的載入時間。

In Android, resource management has significant impacts on system performance. Especially, memory management is the most crucial. According to our observations, current memory management in Android is based on the Least Recently Used (LRU) algorithm to claim for more free memory space. In addition, it uses a Garbage Collection (GC) mechanism to perform memory recycling. If numerous applications are executed in the limited memory space, currently Android may suffer from the lengthened loading problem. Therefore, in this research we propose a predictive memory management scheme using the Markov Decision Processes (MDP) model to improve the memory utilization. The proposed scheme has two following contributions: (1) the MDP-based memory management can efficiently improve the memory utilization in Android, and (2) it can effectively reduce the loading time while many applications are executed.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Memory Management in Android . . . . . . . . . . . . . . . . . . . . . 6
2.2 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Memory Management Tools for Android . . . . . . . . . . . . . . . . . . 9
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Predictive Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Queuing Time Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Overview of Markov Decision Processes . . . . . . . . . . . . . . . . . . 15
3.4 MDP-based Memory Management . . . . . . . . . . . . . . . . . . . . . 16
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Experiments and Performance Analysis . . . . . . . . . . . . . . . . . . . . . 20
4.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.1 Experiment I: Memory Utilization Improvements . . . . . . . . . 21
4.2.2 Experiment II: Transition Probability Thresholds . . . . . . . . . 23
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

[1] Android, “Android Market,” 2011, online: https://market.android.com/, accessed
12-July-2011.
[2] Brian T. Bennett and Vicent J. Kruskal, “LRU Stack Processing,” IBM Journal of
Research and Development, vol. 19, no. 4, pp. 353–357, Jul. 1975.
[3] Khaled M. Bugrara, Youfang Pan, and Paul Walton Purdom, Jr., “Exponential Aver-
age Time for the Pure Literal Rule,” SIAM Journal on Computing, vol. 18, no. 2, pp.
409–418, Apr. 1989.
[4] Li-Pin Chang, Tei-Wei Kuo, and Shi-Wu Lo, “Real-Time Garbage Collection for
Flash-Memory Storage Systems of Real-Time Embedded Systems,” ACM Transac-
tions on Embedded Computing Systems, vol. 3, no. 4, pp. 837–863, Nov. 2004.
[5] Tang Lung Cheung, Kari Okamoto, Frank Maker III, Xin Liu, and Venkatesh Akella,
“Markov Decision Process (MDP) Framework for Optimizing Software on Mobile
Phones,” in Proceedings of the 7th ACM International Conference on Embedded
Software (EMSOFT ’09), 2009, pp. 11–20.
[6] Asit Dan and Don Towsley, “An Approximate Analysis of the LRU and FIFO Buffer
Replacement Schemes,” in Proceedings of the 1990 ACM SIGMETRICS Conference
on Measurement and Modeling of Computer Systems, 1990, pp. 143–152.
[7] Hossein Falaki, Ratul Mahajan, Srikanth Kandula, Dimitrios Lymberopoulos,
Ramesh Govindan, and Deborah Estrin, “Diversity in Smartphone Usage,” in Pro-
ceedings of the 8th International Conference on Mobile Systems, Applications, and
Services (MobiSys ’10), 2010, pp. 179–194.
[8] Google, “Google Android Developers,” 2011, online: http://developer.android.com/
index.html, accessed 12-July-2011.
[9] Yusuf Hasan, Wei-Mei Chen, J. Morris Chang, and Bashar M. Gharaibeh, “Up-
per Bounds for Dynamic Memory Allocation,” IEEE Transactions on Computers,
vol. 59, no. 4, pp. 468–477, Apr. 2010.
[10] Qiying Hu and Wuyi Yue, Markov Decision Processes with their Applications, ser.
Advances in Mechanics and Mathematics. Springer, 2008, vol. 14.
[11] Leslie Pack Kaelbling, Michael L. Littman, and AndrewW. Moore, “Reinforcement
Learning: A Survey,” Journal of Artificial Intelligence Research, vol. 4, pp. 237–
285, 1996.
[12] Fei Kong, Pin Tao, Shi Qiang Yang, and Xiao Li Zhao, “Genetic Algorithm Based
Idle Length Prediction Scheme for Dynamic Power Management,” in Proceedings of
the IMACS Multiconference on Computational Engineering in Systems Applications,
2006, pp. 1437–1443.
[13] Moulay Driss Mechaoui, Asma Cherif, Abdessamad Imine, and Fatima Bendella,
“Log Garbage Collector-based Real Time Collaborative Editor for Mobile Devices,”
in Proceedings of the 6th International Conference on Collaborative Computing:
Networking, Applications and Worksharing, 2010.
[14] Earl Oliver, “A Survey of Platforms for Mobile Networks Research,” ACM SIGMOBILE
Mobile Computing and Communications Review, vol. 12, no. 4, pp. 56–63,
Feb. 2008.
[15] Elizabeth J. O’Neil, Patrick E. O’Neil, and Gerhard Weikum, “The LRU-K Page
Replacement Algorithm for Database Disk Buffering,” in Proceedings of the 1993
ACM SIGMOD International Conference on Management of Data (SIGMOD ’93),
1993, pp. 297–306.
[16] Gerardo Pelosi and Giuseppe Psaila, “SMaC: Spatial Map Caching Technique for
Mobile Devices,” in Proceedings of the 25th ACM Symposium on Applied Computing
(SAC ’10), 2010, pp. 1829–1830.
[17] Arno Puder, “Cross-Compiling Android Applications to the iPhone,” in Proceedings
of the 8th International Conference on the Principles and Practice of Programming
in Java, 2010, pp. 69–77.
[18] Moinuddin K. Qureshi and Yale N. Patt, “Utility-Based Cache Partitioning: A Low-
Overhead, High-Performance, Runtime Mechanism to Partition Shared Caches,” in Proceedings of the 39th Annual IEEE/ACM International Symposium on Microar-
chitecture (MICRO 39), 2006, pp. 423–432.
[19] Tracey J. Regan, Iadine Chades, and Hugh P. Possingham, “Optimally Managing
under Imperfect Detection: A Method for Plant Invasions,” Journal of Applied Ecol-
ogy, vol. 48, no. 1, pp. 76–85, Feb. 2011.
[20] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, Operating System Con-
cepts, 8th ed. John Wiley & Sons,2009.
Sons, 2009.
[21] Willie Teng, “Android Smartphone Shipments to Surpass 55 Million Units
Worldwide in 2010, says Digitimes Research,” Aug. 2010, accessed 12-July-2011.
[Online]. Available: http://www.digitimes.com/news/a20100817VL201.html
and Xiaoyan Xiang, “Flash Memory Manage-
ment Based on Predicted Data Expiry-Time in Embedded Real-time Systems,” in
Proceedings of the 23rd ACM Symposium on Applied Computing (SAC ’08), 2008,
pp. 1477–1481.
[23] Lei Yang, Robert P. Dick, Haris Lekatsas, and Srimat Chakradhar, "CRAMES: Compressed RAM for Embedded System," in Proceedings of the 3rd IEEE/ACM/I-FIP International Conference on Hardware/software Codesign and System Synthe-
sis (CODES+ISSS ’05), 2005, pp. 93–98.

電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top