MFGC: Minimal First Garbage Collection for Monitoring of Context-Aware Victim Selection
Main Article Content
Abstract
SSDs based on NAND flash are becoming a feasible secondary storage option for many computer systems. Because NAND flash memory is dif- ferent from regular HDDs, flash-based SSDs frequently have an interface layer known as Flash Translation Layer (FTL). Garbage collection tech- nique is required to free up space. Garbage collection policy is primarily concerned with cleaning costs and wear-leveling. To achieve the above design principles, we have proposed an effective minimal first garbage col- lection termed as MFGC. MFGC manages the blocks in the list, sorted in descending order of erase count. This list is divided into two regions: preference region and alternate region. The adaptive window for victim selection is used, which adapts dynamically as the cleaning cost changes. After the victim selection, effective data identification of valid hot page and valid cold page is done based on threshold and redistribution of them is done to free blocks. A Series of trace simulations is performed to evaluate the performance of proposed approach with other existing approaches. MFGC outperforms GR, CB, CAT, CATA and MCSGC by 85.5%, 77.1%,61.7%, 56.7% and 43.5% respectively.The outcome of the simulation demonstrates that our approach is superior to others in terms of erase and copy operations as well as wear leveling of blocks.
Article Details
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
References
A. Leventhal, "Flash storage memory," Communications of the ACM, vol. 51, no. 7, pp. 47–51, 2008.
O. Kwon and K. Koh, "Swap space management technique for portable consumer electronics with nand flash memory," IEEE Transactions on Consumer Electronics, vol. 56, no. 3, pp. 1524–1531, 2010.
H.-L. Li, C.-L. Yang, and H.-W. Tseng, "Energy-aware flash memory man- agement in virtual memory system," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 16, no. 8, pp. 952–964, 2008.
P. Yang, N. Xue, Y. Zhang, Y. Zhou, L. Sun, W. Chen, Z. Chen, W. Xia, J. Li, and K. Kwon, "Reducing garbage collection overhead in SSD based on workload prediction," in 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19), 2019.
C. Du, Y. Yao, J. Zhou, and X. Xu, "Vbbms: A novel buffer management strategy for nand flash storage devices," IEEE Transactions on Consumer Electronics, vol. 65, no. 2, pp. 134–141, 2019.
Narayan, Vipul, and A. K. Daniel. "IOT based sensor monitoring system for smart complex and shopping malls." Mobile Networks and Management: 11th EAI International Conference, MONAMI 2021, Virtual Event, October 27-29, 2021, Proceedings. Cham: Springer International Publishing, 2022.
Narayan, Vipul, and A. K. Daniel. "FBCHS: Fuzzy Based Cluster Head Selection Protocol to Enhance Network Lifetime of WSN." ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal 11.3 (2022): 285-307.
Narayan, Vipul, and A. K. Daniel. "RBCHS: Region-based cluster head selection protocol in wireless sensor network." Proceedings of Integrated Intelligence Enable Networks and Computing: IIENC 2020. Springer Singapore, 2021.
Narayan, Vipul, and A. K. Daniel. "A novel approach for cluster head selection using trust function in WSN." Scalable Computing: Practice and Experience 22.1 (2021): 1-13.
M. Santarini, "Nand versus nor-which flash is best for bootin'your next system?," Edn, vol. 50, no. 21, pp. 41–49, 2005.
S. L. Min and E. H. Nam, "Current trends in flash memory technology," in Proceedings of the 2006 Asia and South Pacific Design Automation Conference, pp. 332–333, 2006.
W. Bux and I. Iliadis, "Performance of greedy garbage collection in flash-based solid-state drives," Performance Evaluation, vol. 67, no. 11, pp. 1172–1186, 2010.
A. Kawaguchi, S. Nishioka, and H. Motoda, "A flash-memory based file system.," in USENIX, pp. 155–164, 1995.
M.-L. Chiang and R.-C. Chang, "Cleaning policies in mobile computers using flash memory," Journal of Systems and Software, vol. 48, no. 3, pp. 213–231, 1999.
Kuo, Tei-Wei, et al. "Special issues in flash." 2008 IEEE/ACM International Conference on Computer-Aided Design. IEEE, 2008.
Ma, Dongzhe, Jianhua Feng, and Guoliang Li. "A survey of address translation technologies for flash memories." ACM Computing Surveys (CSUR) 46.3 (2014): 1-39.
Chang, Li-Pin. "On efficient wear leveling for large-scale flash-memory storage systems." Proceedings of the 2007 ACM symposium on Applied computing. 2007.
Hu, Xiao-Yu, Robert Haas, and Eleftheriou Evangelos. "Container marking: Combining data placement, garbage collection and wear levelling for flash." 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, 2011.
Wang, Chundong, and Weng-Fai Wong. "Observational wear leveling: an efficient algorithm for flash memory management." Proceedings of the 49th Annual Design Automation Conference. 2012.
Lee, Sungjin, Dongkun Shin, and Jihong Kim. "BAGC: Buffer-aware garbage collection for flash-based storage systems." IEEE Transactions on Computers 62.11 (2012): 2141-2154.
Ji, Seunggu, and Dongkun Shin. "An efficient garbage collection for flash memory-based virtual memory systems." IEEE Transactions on Consumer Electronics 56.4 (2010): 2355-2363.
Liu, Jiakun, and Wonyong Sung. "COPR: a cost-oriented recycling policy for flash translation layer." IEEE Transactions on Consumer Electronics 56.2 (2010): 673-681.
Wang, Meng, et al. "An efficient NAND flash garbage collection algorithm based on area and block operation." 2012 Second International Conference on Intelligent System Design and Engineering Application. IEEE, 2012.
Murugan, Muthukumar, and David HC Du. "Rejuvenator: A static wear leveling algorithm for NAND flash memory with minimized overhead." 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST). IEEE, 2011
L. Han, Y. Ryu, and K. Yim, "Cata: A garbage collection scheme for flash memory file systems," in International Conference on Ubiquitous Intelligence and Computing, pp. 103–112, Springer, 2006.
S.-H. Hwang, J. H. Choi, and J. W. Kwak, "Migration cost sensitive garbage collection technique for non-volatile memory systems," IEICE TRANSACTIONS on Information and Systems, vol. 99, no. 12, pp. 3177– 3180, 2016.
Jung, Sanghyuk, and Yong Ho Song. "LINK-GC: a preemptive approach for garbage collection in NAND flash storages." Proceedings of the 28th Annual ACM Symposium on Applied Computing. 2013.
Tsao, Che-Wei, Yuan-Hao Chang, and Ming-Chang Yang. "Performance enhancement of garbage collection for flash storage devices: An efficient victim block selection design." Proceedings of the 50th Annual Design Automation Conference. 2013.
Gao, Congming, et al. "Exploiting parallelism in I/O scheduling for access conflict minimization in flash-based solid state drives." 2014 30th Symposium on Mass Storage Systems and Technologies (MSST). IEEE, 2014.
Kwon, Ohhoon, et al. "FeGC: An efficient garbage collection scheme for flash memory based storage systems." Journal of Systems and Software 84.9 (2011): 1507-1523.
Mitzenmacher, Michael. "The power of two choices in randomized load balancing." IEEE Transactions on Parallel and Distributed Systems 12.10 (2001): 1094-1104.
Kwon, Ohhoon, Yeonseung Ryu, and Kern Koh. "An efficient garbage collection policy for flash memory based swap systems." Computational Science and Its Applications–ICCSA 2007: International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Proceedings, Part I 7. Springer Berlin Heidelberg, 2007.
Ahn, Sungyong, et al. "A compressed file system manager for flash memory based consumer electronics devices." IEEE Transactions on Consumer Electronics 59.3 (2013): 544-549.
Lin, Wen-Huei, and Li-Pin Chang. "Dual greedy: Adaptive garbage collection for page-mapping solid-state disks." 2012 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2012.
Liu, Jun, et al. "A novel hot data identification mechanism for NAND flash memory." IEEE Transactions on Consumer Electronics 61.4 (2015): 463-469.
Luojie, Xiang, and Brian M. Kurkoski. "An improved analytic expression for write amplification in NAND flash." 2012 International Conference on Computing, Networking and Communications (ICNC). IEEE, 2012.
Desnoyers, Peter. "Analytic modeling of SSD write performance." Proceedings of the 5th Annual International Systems and Storage Conference. 2012.
Xu, Guangxia, Manman Wang, and Yanbing Liu. "Swap-aware garbage collection algorithm for NAND flash-based consumer electronics." IEEE Transactions on Consumer Electronics 60.1 (2014): 60-65.
Yan, Hua, and Qian Yao. "An efficient file-aware garbage collection algorithm for NAND flash-based consumer electronics." IEEE Transactions on Consumer Electronics 60.4 (2014): 623-627.
Wu, Suzhen, et al. "Cagc: A content-aware garbage collection scheme for ultra-low latency flash-based ssds." 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2021.
Koller, Ricardo, and Raju Rangaswami. "I/O deduplication: Utilizing content similarity to improve I/O performance." ACM Transactions on Storage (TOS) 6.3 (2010): 1-26.
Bucy, John S., and Gregory R. Ganger. The DiskSim simulation environment version 3.0 reference manual. School of Computer Science, Carnegie Mellon University, 2003.
FIU IODedup traces. http://iotta.snia.org/traces/391.
Narayan, Vipul, et al. "7 Extracting business methodology: using artificial intelligence-based method." Semantic Intelligent Computing and Applications 16 (2023): 123.
Narayan, Vipul, et al. "A Comprehensive Review of Various Approach for Medical Image Segmentation and Disease Prediction." Wireless Personal Communications 132.3 (2023): 1819-1848.
Mall, Pawan Kumar, et al. "Rank Based Two Stage Semi-Supervised Deep Learning Model for X-Ray Images Classification: AN APPROACH TOWARD TAGGING UNLABELED MEDICAL DATASET." Journal of Scientific & Industrial Research (JSIR) 82.08 (2023): 818-830.
Narayan, Vipul, et al. "Severity of Lumpy Disease detection based on Deep Learning Technique." 2023 International Conference on Disruptive Technologies (ICDT). IEEE, 2023.
Saxena, Aditya, et al. "Comparative Analysis Of AI Regression And Classification Models For Predicting House Damages İn Nepal: Proposed Architectures And Techniques." Journal of Pharmaceutical Negative Results (2022): 6203-6215.
Kumar, Vaibhav, et al. "A Machine Learning Approach For Predicting Onset And Progression"“Towards Early Detection Of Chronic Diseases “." Journal of Pharmaceutical Negative Results (2022): 6195-6202.
Chaturvedi, Pooja, Ajai Kumar Daniel, and Vipul Narayan. "Coverage Prediction for Target Coverage in WSN Using Machine Learning Approaches." (2021).
Chaturvedi, Pooja, A. K. Daniel, and Vipul Narayan. "A Novel Heuristic for Maximizing Lifetime of Target Coverage in Wireless Sensor Networks." Advanced Wireless Communication and Sensor Networks. Chapman and Hall/CRC 227-242.