[논문]실시간 시스템에서의 플래시 메모리 저장 장치를 위한 적응적 가비지 컬렉션 정책

박송화; 이정훈; 이원오; 김희언

doi:10.14372/iemek.2017.12.3.121

[국내논문] 실시간 시스템에서의 플래시 메모리 저장 장치를 위한 적응적 가비지 컬렉션 정책
A Adaptive Garbage Collection Policy for Flash-Memory Storage System in Embedded Systems 원문보기

대한임베디드공학회논문지 = IEMEK Journal of embedded systems and applications, v.12 no.3, 2017년, pp.121 - 130

박송화 (LIG Nex1) , 이정훈 (LIG Nex1) , 이원오 (LIG Nex1) , 김희언 (LIG Nex1)

Abstract ▼ AI-Helper

NAND flash memory has advantages of non-volatility, little power consumption and fast access time. However, it suffers from inability that does not provide to update-in-place and the erase cycle is limited. Moreover, the unit of read/write operation is a page and the unit of erase operation is a block. Therefore, erase operation is slower than other operations. The AGC, the proposed garbage collection policy focuses on not only garbage collection time reduction for real-time guarantee but also wear-leveling for a flash memory lifetime. In order to achieve above goals, we define three garbage collection operating modes: Fast Mode, Smart Mode, and Wear-leveling Mode. The proposed policy decides the garbage collection mode depending on system CPU usage rate. Fast Mode selects the dirtiest block as victim block to minimize the erase operation time. However, Smart Mode selects the victim block by reflecting the invalid page number and block erase count to minimizing the erase operation time and deviation of block erase count. Wear-leveling Mode operates similar to Smart Mode and it makes groups and relocates the pages which has the similar update time. We implemented the proposed policy and measured the performance compare with the existing policies. Simulation results show that the proposed policy performs better than Cost-benefit policy with the 55% reduction in the operation time. Also, it performs better than Greedy policy with the 87% reduction in the deviation of erase count. Most of all, the proposed policy works adaptively according to the CPU usage rate, and guarantees the real-time performance of the system.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 실시간 임베디드 시스템에서 저장 장치로 사용되는 NAND 플래시 메모리를 위한 AGC 기법을 제안하였다.
본 논문에서는 표 2, 그림 5와 같이 시스템의 CPU 사용률에 따라 3가지 모드로 동작하는 적응적 가비지 컬렉션 (AGC) 정책을 제안한다
이에 본 논문에서는 NAND 플래시 메모리를 저장장치로 사용하는 임베디드 시스템에서 실시간성을 보장하고 효율적인 지움 연산 및 지움 균등을 고려한 적응적 가비지 컬렉션 정책 (AGC: Adaptive Garbage Collection)을 제안한다. 제안한 정책은 임베디드 시스템의 CPU 사용률에 따라 3가지 모드 (Fast Mode, Smart Mode, Wear-leveling Mode)로 동작하며, 각 모드는 CPU 사용률에 따라 지움 연산 속도와 지움 균등을 고려한 가비지 컬렉션을 수행한다.
이에 본 논문에서는 플래시 메모리를 저장장치로 사용하는 임베디드 시스템에서 지움 연산의 효율성과 플래시 메모리의 수명뿐만 아니라 실시간성 보장을 위하여 CPU 사용률에 따라 적응적 가비지 컬렉션을 수행하는 기법을 제안한다.

제안 방법

3 가지 기법에 대해 동일한 환경에서 동일한 파일 연산을 수행하도록 하였으며 가비지 컬렉션 수행 시점도 동일하도록 하였다.
제안한 AGC 기법은 3 가지 모드의 가비지 컬렉션을 가지며, 시스템의 실시간성을 보장하기 위하여 시스템의 CPU 사용률에 따라 적응적으로 동작 모드를 선택한다. CPU 사용률이 높은 경우에는 Fast Mode로 동작하여 지움 연산의 효율성만을 고려하며, CPU 사용률이 낮은 경우에는 Wear-leveling Mode로 동작하여 지움 연산의 효율성 및 지움 균등을 고려하고 이후에 수행될 지움 연산의 효율성을 위하여 유효 페이지의 그룹화를 통해 갱신 경향이 유사한 페이지들을 재배치하도록 하였다. Smart Mode는 지움 연산의 효율성 및 지움 균등을 고려 하지만 유효 페이지의 그룹화 과정은 수행하지 않으므로 Wear-leveling Mode 보다 플래시 처리 속도를 빠르게 하였다.
각 기법의 지움 균등 효과를 비교하기 위하여 그림 13과 같이 블록 횟수 분산을 비교하였다. Greedy 정책은 연산 처리 속도는 가장 빨랐으나 지움 균등을 고려하지 않아 연산이 수행될수록 블록 지움 횟수 분산도 증가하였다.
첫 번째 단점을 극복하기 위해서는 일반적으로 갱신 연산이 발생했을 때 다른 공간에 새로운 데이터를 쓰고 이전의 데이터는 무효화시키는 방법을 사용한다. 그리고 새로운 공간 확보를 위해서는 무효화된 데이터를 가지고 있는 블록들에 대해서 가비지 컬렉션(Garbage Collection)을 수행한다. 두 번째 단점을 극복하기 위해서는 블록의 지움 횟수를 고려하여 블록을 관리한다.
본 논문에서 제안하는 적응적 가비지 컬렉션 정책은 지움 연산의 효율성과 균등 지움을 고려하기 위하여 블록 상태 정보, 페이지 상태 정보 및 자유 블록 정보를 관리한다.
제안한 AGC 기법은 3 가지 모드의 가비지 컬렉션을 가지며, 시스템의 실시간성을 보장하기 위하여 시스템의 CPU 사용률에 따라 적응적으로 동작 모드를 선택한다. CPU 사용률이 높은 경우에는 Fast Mode로 동작하여 지움 연산의 효율성만을 고려하며, CPU 사용률이 낮은 경우에는 Wear-leveling Mode로 동작하여 지움 연산의 효율성 및 지움 균등을 고려하고 이후에 수행될 지움 연산의 효율성을 위하여 유효 페이지의 그룹화를 통해 갱신 경향이 유사한 페이지들을 재배치하도록 하였다.
제안한 기법의 성능 평가를 위하여 표 5의 연산이 랜덤하게 발생하도록 하고, 연산 수행 및 가비지 컬렉션에 소요된 시간을 측정하였다.
이에 본 논문에서는 NAND 플래시 메모리를 저장장치로 사용하는 임베디드 시스템에서 실시간성을 보장하고 효율적인 지움 연산 및 지움 균등을 고려한 적응적 가비지 컬렉션 정책 (AGC: Adaptive Garbage Collection)을 제안한다. 제안한 정책은 임베디드 시스템의 CPU 사용률에 따라 3가지 모드 (Fast Mode, Smart Mode, Wear-leveling Mode)로 동작하며, 각 모드는 CPU 사용률에 따라 지움 연산 속도와 지움 균등을 고려한 가비지 컬렉션을 수행한다.
갱신 빈도가 낮아 Age가 높은 페이지들도 동일 블록에 저장하며, 쓰기 블록으로 지움 횟수가 높은 블록을 할당한다. 즉, 지움 횟수가 높은 블록에 갱신 빈도가 낮은 데이터를 저장하여 해당 블록이 지움 블록으로 선택될 확률을 낮추도록 한다. 그림 8에서 Wear-leveling Mode는 Age가 높은 페이지들의 복사를 위해서 자유 블록 중 지움 횟수가 가장 적은 블록 20을 쓰기 블록으로 할당하고, Age가 낮은 페이지들의 복사를 위해서는 지움 횟수가 가장 높은 블록 15를 쓰기 블록으로 할당한다.

데이터처리

제안한 기법의 성능을 평가하기 위하여 기존의 Greedy 정책, Cost-benefit 정책의 성능과 비교하였다. 3 가지 기법에 대해 동일한 환경에서 동일한 파일 연산을 수행하도록 하였으며 가비지 컬렉션 수행 시점도 동일하도록 하였다.

이론/모형

본 논문에서 제안한 적응적 가비지 컬렉션 정책의 성능을 평가하기 위하여 SSD Extension for DiskSim Simulation을 참고하였으며 [9, 10], 시뮬레이션 환경은 표 3과 같다.

성능/효과

8배 연산 시간이 더 소요되었으나 블록들의 지움 횟수 편차는 약 87% 감소되었다. Cost-benefit 정책에 비해서는 블록 지움 횟수 편차가 약 9배 크게 발생하였으나 플래시 처리 시간은 2.2배 향상되었음을 확인하였다. 하지만 본 연구에서 제안한 기법은 CPU 사용률에 의해서만 동작 모드를 결정하며 시스템 및 연산의 특성은 고려하지 못하였다.
성능 측정 결과, CPU 사용률에 따른 적응적 가비지 컬렉션 수행으로 CPU 사용률이 높은 경우에는 플래시 처리 시간의 지연을 최소화하고, CPU사용률이 낮은 경우에는 지움 균등을 고려한 가비지 컬렉션을 수행하여 블록의 균등 사용성이 향상되는 것을 확인하였다. Greedy 정책에 비해 약 2.8배 연산 시간이 더 소요되었으나 블록들의 지움 횟수 편차는 약 87% 감소되었다. Cost-benefit 정책에 비해서는 블록 지움 횟수 편차가 약 9배 크게 발생하였으나 플래시 처리 시간은 2.
즉, CPU 사용률이 높은 경우에는 Fast Mode로 동작하여 연산 및 가비지 컬렉션에 소요된 시간이 짧고, CPU 사용률이 낮은 경우에는 Wear-leveling Mode로 동작하여 연산 및 가비지 컬렉션에 소요된 시간이 길다. Smart Mode로 동작한 경우에는 유효페이지 그룹화 과정이 수행되지 않으므로 Wear-leveling Mode보다 연산에 소요된 시간이 짧았다. 다른 기법과 비교하면, 표 6과 같이 연산시간은 Greedy 정책에 비해 약 2.
성능 측정 결과, CPU 사용률에 따른 적응적 가비지 컬렉션 수행으로 CPU 사용률이 높은 경우에는 플래시 처리 시간의 지연을 최소화하고, CPU사용률이 낮은 경우에는 지움 균등을 고려한 가비지 컬렉션을 수행하여 블록의 균등 사용성이 향상되는 것을 확인하였다. Greedy 정책에 비해 약 2.
실험 결과를 통해 제안한 기법이 CPU 사용률에 따른 적응적 가비지 컬렉션을 수행하여 시스템의 실시간성 및 지움 균등을 보장한 것을 확인할 수 있다. 하지만 CPU 사용률에 따라 동작 모드가 결정되므로, 동작 모드를 결정하는 문턱값과 지움 연산의 효율성과 균등 지움의 반영 정도를 결정하는 가중치의 설정이 중요한 요소가 된다.
Cost-benefit 정책은 연산처리 속도는 가장 느렸으나 연산 수행 횟수가 많아지더라도 블록 지움 편차가 적게 증가하였다. 제안한 정책은 CPU 사용률에 따라 지움 균등의 고려도가 달라지며, Greedy 정책과 비교하여 지움 횟수의 분산이 약 87% 감소되었다. 하지만 CPU 사용률이 높은 경우에는 지움 연산의 효율성만을 고려하므로 Cost-benefit 정책에 비해서는 지움 분산이 약 9배 크게 발생하였다.
하지만 CPU 사용률이 높은 경우에는 지움 연산의 효율성만을 고려하므로 Cost-benefit 정책에 비해서는 지움 분산이 약 9배 크게 발생하였다. 제안한 정책이 Cost-benefit 정책에 비하여 지움 균등 효과는 낮으나, 시스템의 실시간성을 보장하는 장점이 있다.
플래시 메모리를 저장장치로 사용하기 위해서는 극복해야 할 두 가지 단점이 있다. 첫째, 플래시 메모리는 데이터 수정 시 본래 주소에 덮어쓰기(update-in-place)가 불가능하다. 플래시 메모리의 각 비트가 단방향으로만 토글링 (toggling)되기 때문에 쓰기 연산 시 지움 연산을 선행해야 한다.

후속연구

향후 본 연구는 CPU 사용률 외의 시스템 특성 및 발생하는 연산의 특성을 고려하고, 가비지 컬렉션 모드 설정을 위한 문턱값과 가중치를 적응적으로 변화시켜 지움 연산의 효율성 및 지움 균등을 더 향상시킬 수 있는 방향으로 나아가야 할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	플래시 메모리란 무엇인가?	플래시 메모리는 일종의 EEPROM (Electrically Erasable and Programmable ROM)으로 전기적으로 데이터를 지우고 다시 기록할 수 있는 비휘발성(non-volatile) 컴퓨터 기억 장치이다. 부피가 작고 가벼우며 소비 전력이 낮고 입출력 속도가 빠를 뿐만 아니라 EEPROM보다 가격이 싼 장점으로 인하여 저장 매체로서 사용이 증가하고 있다 [1].
	플래시 메모리는 게이트 타입과 셀을 구성하는 구조에 따라 어떻게 구분되는가?	플래시 메모리는 게이트 (gate) 타입과 셀 (cell)을 구성하는 구조에 따라 NOR 플래시 메모리와 NAND 플래시 메모리로 구분된다. NOR 플래시 메모리는 버스 형태의 외부 인터페이스를 가지고 있어 바이트 단위의 임의 접근이 가능하고, CPU에 직접 연결되어 CPU가 수행하는 코드를 직접 실행할 수 있다.
	플래시 메모리가 저장 매체로서 사용이 증가하고 있는 이유는 무엇인가?	플래시 메모리는 일종의 EEPROM (Electrically Erasable and Programmable ROM)으로 전기적으로 데이터를 지우고 다시 기록할 수 있는 비휘발성(non-volatile) 컴퓨터 기억 장치이다. 부피가 작고 가벼우며 소비 전력이 낮고 입출력 속도가 빠를 뿐만 아니라 EEPROM보다 가격이 싼 장점으로 인하여 저장 매체로서 사용이 증가하고 있다 [1].

참고문헌 (10)

F. Douglis, R. Caceres, M.F. Kasho, P. Krishnan, K. Li, B. Marsh, J. Tauber, "Storage Alternative for Mobile Computers," Proceedings of the 1st USENIX Symposium on Operating System Design and Implementation, pp. 25-37, 1994.
M.L. Chiang, P.C.H. Lee, R.C. Chang, "Managing Flash Memory in Personal Communication Devices," Proceedings of IEEE Symposium on Consumer Electronics, pp. 177-182, 1997.
M.L. Chiang, R.C .Chang, "Cleaning Policies in Mobile Computers Using Flash Memory," Journal of System and Software, Vol. 48, No. 3, pp. 213-231, 1999.

상세보기
A. Kawaguchi, S. Nishioka, H. Motoda "A Flash-Memory Based File System," Proceedings of 1995 USENIX Technical Conference, pp. 155-164, 1995.
O. Kwon, K. Koh, "Swap-aware Garbage Collection for NAND Flash Memory Based Embedded Systems," Proceedings of IEEE 7th International Conference on Computer and Information Technology, pp. 787-292, 2007.
S.J. Baek, J.M. Choi, "Design and Implementation of MODA Allocation Scheme Based on Analysis of Block Cleaning Cost," Journal of KISE, Vol. 34, No. 11, pp. 599-609, 2007 (in Korean).
S.H. Hwang, J.W. Kwak, "Garbage Collection Techniques for Reduction of Migration Overhead and Lifetime Prolongment of NAND Flash Memory," IEMEK J. Embed. Sys. Appl., Vol. 11, No. 2, pp. 125-134, 2016 (in Korean).
S.H. Kim, J.W. Kwak, "Garbage Collection Method Using Proxy Block Considering Index Data Structure Based on Flash Memory," Journal of KSCI, Vol. 20, No. 6, pp. 1-11, 2015 (in Korean).
V. Prabhakaran, T. Wobber, "SSD Extension for DiskSim Simulation Environment." Microsoft Research 2009.
K9GAG08U0M 2G x 8bit MLC NAND Flash Memory Data Sheet, Samsung Electronics, https://www.samsung.com, 2007.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증