減少資源回收負擔兼顧程序公平性的固態硬碟調度器

A GC-aware fairness scheduler for SSD

王綸(Lun Wang)

指導教授 ： 楊佳玲

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201703489

摘要

固態硬碟是當前主流的儲存裝置，而在多進程系統中，公平資源分配是一件需要考慮的事情。現有的公平調度器都設計再主機端，然而程序公平性卻有可能會因為固態硬碟觸發垃圾回收而被破壞。我們發現現有的主機公平調度器並沒有考量到垃圾回收帶來的負擔，並導致太慢處理硬碟的資源再分配。這篇論文考量將公平性延伸到儲存裝置內部，並設計一個讓程序不會承擔太多額外的垃圾回收負擔。另外為了讓主機端的調度器能夠及時針對垃圾回收有所反應，我們讓固態硬碟主動告知主機一些資訊，以便讓主機調度器能夠正確分配硬碟資源給各個程序。實驗結果顯示，所設計的機制可以再達到公平性的同時也增加吞吐量。

關鍵字

固態硬碟 ； 調度器 ； 垃圾回收 ； 公平性 ； 多進程系統

並列摘要

Solid-state disk (SSD) drives are the mainstream solutions for massive data storage today. For modern computer systems, fair resource assignment is a critical design consideration and has drew great interests in recent years. Although there are several fairness I/O schedulers proposed on the host side for SSDs, process fairness could still be dramatically degraded if garbage collection (GC) is triggered in the device side. We found that existing host-side I/O schedulers cannot achieve fairness because they did not consider the GC cost and update the assigned resource with GC cost too late. This paper proposed a novel device side I/O scheduling strategy in SSD controllers to achieve true fairness working with existing I/O schedulers of SSDs. This work is the first to consider fairness down to the device level. The proposed scheduling approach can guarantee that the processes will suffer little GC overhead if the processes barely introduce GCs. Experimental results with a wide range of workloads verify that the proposed technique can achieve fairness as well as improve the throughput significantly.

並列關鍵字

solid state disk ； scheduler ； garbage collection ； fairness ； multi-process system

參考文獻

[5] L.-P. Chang, T.-W. Kuo, and S.-W. Lo. Real-time garbage collection for flash memory storage systems of real-time embedded systems. ACM Transactions on Embedded Computing Systems (TECS), 3(4):837–863, 2004.

[11] J. Lee, Y. Kim, G. M. Shipman, S. Oral, F. Wang, and J. Kim. A semi-preemptive garbage collector for solid state drives. In Performance Analysis of Systems and Software (ISPASS), 2011 IEEE International Symposium on, pages 12–21. IEEE, 2011.

[13] S.-H. Park, D.-g. Kim, K. Bang, H.-J. Lee, S. Yoo, and E.-Y. Chung. An adaptive idle-time exploiting method for low latency nand flash-based storage devices. IEEE Transactions on Computers, 63(5):1085–1096, 2014.

[1] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M.S. Manasse, and R. Panigrahy. Design tradeoffs for ssd performance. In USENIX Annual Technical Conference, volume 8, pages 57–70, 2008.

[2] O. Application. I/o. umass trace repository, 2007.