KR100806343B1

KR100806343B1 - 플래시 메모리를 포함한 메모리 시스템 및 그것의 맵핑테이블 관리 방법

Info

Publication number: KR100806343B1
Application number: KR1020060101961A
Authority: KR
Inventors: 천원문; 이양섭
Original assignee: 삼성전자주식회사
Priority date: 2006-10-19
Filing date: 2006-10-19
Publication date: 2008-02-27
Also published as: US20080098195A1

Abstract

본 발명은 플래시 메모리를 포함한 메모리 시스템 및 그것의 맵핑 테이블 관리 방법에 관한 것이다. 본 발명에 따른 메모리 시스템은 파일 시스템; 상기 파일 시스템으로부터 논리적 어드레스를 입력받고, 상기 논리적 어드레스를 물리적 어드레스로 변환하는 플래시 변환 레이어; 및 상기 변환된 물리적 어드레스를 입력받는 플래시 메모리를 포함한다. 여기에서, 상기 플래시 변환 레이어는 상기 플래시 메모리의 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)임을 표시한 플래그 정보와, 상기 메모리 블록의 시작 페이지를 지정한 오프셋 정보를 갖는다. 본 발명에 의하면, 메모리의 공간을 크게 늘리지 않으면서, 페이지 복사 횟수 및 블록 소거 횟수를 크게 줄일 수 있다.

Description

플래시 메모리를 포함한 메모리 시스템 및 그것의 맵핑 테이블 관리 방법{MEMORY SYSTEM INCLUDING FLASH MEMORY AND MAPPING TABLE MANAGEMENT METHOD THEREOF}

도 1은 일반적인 플래시 메모리를 사용하는 메모리 시스템의 하드웨어 구조를 보여주는 블록도이다.

도 2는 일반적인 플래시 메모리를 사용하는 메모리 시스템의 소프트웨어 구조를 보여주는 블록도이다.

도 3은 일반적인 혼합 맵핑 방법을 수행하는 메모리 시스템을 보여주는 블록도이다.

도 4는 도 3에 도시된 메모리 시스템의 혼합 맵핑 방법을 예시적으로 설명하기 위한 다이어그램이다.

도 5는 본 발명에 따른 혼합 맵핑 동작을 사용하는 메모리 시스템을 보여주는 블록도이다.

도 6은 도 5에 도시된 메모리 시스템의 맵핑 테이블 관리 방법을 예시적으로 보여주는 도표이다.

도 7은 도 5에 도시된 메모리 시스템의 혼합 맵핑 동작을 예시적으로 설명하기 위한 다이어그램이다.

* 도면의 주요 부분에 대한 부호 설명 *

300, 400; 메모리 시스템 310, 410; 파일 시스템

320, 420; 플래시 변환 레이어 330, 430; 플래시 메모리

321, 421; 블록 맵핑 테이블 322; 페이지 맵핑 테이블

422; 랩-어라운드 페이지 맵핑 테이블 423; 랜덤 페이지 맵핑 테이블

본 발명은 플래시 메모리를 사용한 메모리 시스템에 관한 것으로, 더욱 상세하게는 메모리 시스템 및 그것의 맵핑 테이블 관리 방법에 관한 것이다.

최근 디지털 카메라, MP3 플레이어, 핸드폰, PDA 등과 같은 휴대 장치가 많이 사용되고 있다. 플래시 메모리는 저전력, 비휘발성, 고집적 등의 특성으로 인해 이러한 휴대 장치에 많이 사용되고 있다. 특히, 플래시 메모리의 용량이 크게 늘어나면서 디스크를 플래시 메모리로 대체하는 경향이 많아지고 있다.

플래시 메모리는 물리적 특성으로 인하여 쓰기 전 소거(erase-before-write) 연산을 수행한다. 즉, 플래시 메모리는 섹터(sector, 보통 512 바이트)에 쓰기 동작을 수행할 경우, 그 섹터가 속한 블록(block)을 소거한 다음에, 쓰기 동작을 수행한다. 따라서 플래시 메모리는, 섹터에 덮어 쓰기(over write)를 수행할 수 있는 하드 디스크에 비하여, 동일한 I/O에 대해 더 많은 시간을 필요로 한다. 또한, 플래시 메모리는 동일한 블록에 대해 10만 번 정도의 소거 동작을 수행하면, 더 이상 사용할 수 없다. 따라서 플래시 메모리는 특정 블록에 대해 소거 동작이 반복되는 것을 피해야 한다.

플래시 변환 레이어(Flash Translation Layer; FTL)는 플래시 메모리의 이러한 단점을 극복하고, 플래시 메모리를 효율적으로 관리하기 위한 소프트웨어이다. 플래시 변환 레이어(FTL)는 파일 시스템(File System)으로부터 논리적 섹터 번호(Logical Sector Number; LSN)를 입력받고, 이를 물리적 섹터 번호(Physical Sector Number; PSN)로 변환한다. 물리적 섹터 번호(PSN)는 실제 플래시 메모리에서 사용할 어드레스이다.

플래시 변환 레이어(FTL)는 위와 같은 어드레스 변환을 위해 어드레스 맵핑 테이블(Address Mapping Table)을 갖는다. 어드레스 맵핑 테이블은 랜덤 액세스 메모리(RAM)에 저장된다. 어드레스 맵핑 테이블에는 논리적 어드레스(Logical Address) 및 이에 대응하는 물리적 어드레스(Physical Address)가 표시되어 있다. 어드레스 맵핑 테이블은 맵핑 단위에 따라 그 크기가 달라질 수 있으며, 맵핑 단위에 따라 다양한 맵핑 방법을 갖는다.

대표적인 맵핑 방법으로, 페이지 맵핑 방법(page mapping method), 블록 맵핑 방법(block mapping method), 그리고 혼합 맵핑 방법(hybrid mapping method)이 있다. 페이지 맵핑 방법은 페이지 단위로 맵핑 테이블을 만들고, 논리적 페이지를 물리적 페이지로 변환하는 방법이다. 블록 맵핑 방법은 블록 단위로 맵핑 동작을 수행하는 방법이다. 혼합 맵핑 방법은 페이지 맵핑 방법과 블록 맵핑 방법을 동시에 사용하는 방법이다.

일반적으로 하나의 메모리 블록은 수십 또는 수백 개의 페이지로 구성된다. 따라서 페이지 맵핑 방법을 사용할 경우에, 맵핑 테이블의 크기는 블록 맵핑 방법을 사용할 때보다 수십 또는 수백 배 증가하게 된다. 즉, 페이지 맵핑 방법은 맵핑 테이블을 사용하는 데 너무 많은 메모리 공간을 필요로 한다는 단점을 갖는다.

반면, 블록 맵핑 방법은 블록 단위로 맵핑 동작을 수행하기 때문에, 페이지 맵핑 방법에 비해 맵핑 테이블의 크기를 줄일 수 있는 장점을 갖는다. 그러나 블록 맵핑 방법에 의하면, 블록 내에 쓰여질 페이지의 위치가 고정되기 때문에, 많은 머지(merge) 연산을 수행해야 한다는 단점을 갖는다.

혼합 맵핑 방법은 로그 블록(log block)에 대해서는 페이지 맵핑 방법을 사용하고, 데이터 블록(data block)에 대해서는 블록 맵핑 방법을 사용한다. 혼합 맵핑 방법은 두 가지 맵핑 방법을 모두 사용함으로, 맵핑 테이블의 크기를 줄임과 동시에, 머지 연산의 횟수를 줄일 수 있다.

여기에서, 로그 블록은 일종의 쓰기 버퍼와 같은 기능을 한다. 즉 쓰기 동작 시에, 데이터 블록에 저장될 페이지 데이터는 먼저 로그 블록에 저장된다. 로그 블록 및 이에 대응하는 데이터 블록(이하, 구 데이터 블록, old data block)에 저장된 페이지 데이터는 머지 연산을 통해 새 데이터 블록(new data block)에 저장된다. 머지 연산 후에, 로그 블록 및 데이터 블록은 소거된다.

이와 같이 혼합 맵핑 방법을 사용하면, 복수의 페이지 복사 및 복수의 블록 소거 동작이 수행된다. 예를 들어, 하나의 블록이 4개의 페이지로 구성되어 있다고 가정하면, 위의 예에서 4번의 페이지 복사 및 2번의 블록 소거 동작이 수행된다. 혼합 맵핑 방법을 사용함에 있어서, 많은 수의 페이지 복사 및 블록 소거 동작은 전체 메모리 시스템의 성능을 저하하는 요인이 되고 있다.

본 발명의 목적은 혼합 맵핑 방법을 사용함에 있어서, 불필요한 페이지 복사 및 블록 소거 동작을 줄일 수 있는 메모리 시스템 및 그것의 맵핑 테이블 관리 방법을 제공하는 데 있다.

본 발명에 따른 메모리 시스템은 파일 시스템; 상기 파일 시스템으로부터 논리적 어드레스를 입력받고, 상기 논리적 어드레스를 물리적 어드레스로 변환하는 플래시 변환 레이어; 및 상기 변환된 물리적 어드레스를 입력받는 플래시 메모리를 포함한다. 여기에서, 상기 플래시 변환 레이어는 상기 플래시 메모리의 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)임을 표시한 플래그 정보와, 상기 메모리 블록의 시작 페이지를 지정한 오프셋 정보를 갖는다.

실시예로서, 상기 플래시 변환 레이어는 논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블; 및 상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블을 포함한다. 상기 블록 맵핑 테이블은 순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보; 및 상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보를 갖는다. 상기 블록 맵핑 테이블은 임의 위치 방식(out-of-place order)임을 표시하는 제 3 플래그 정보를 더 갖는다. 상기 플래시 변환 레이어는 상기 임의 위치 방식에 사용될 오프셋 정보를 저장하기 위한 랜덤 페이지 맵핑 테이블을 더 포함한다.

본 발명은 메모리 시스템의 맵핑 테이블 관리 방법에 관한 것이다. 상기 메모리 시스템은 파일 시스템; 상기 파일 시스템으로부터 논리적 어드레스를 입력받고, 상기 논리적 어드레스를 물리적 어드레스로 변환하는 플래시 변환 레이어; 및 상기 변환된 물리적 어드레스를 입력받는 플래시 메모리를 포함한다.

상기 메모리 시스템의 맵핑 테이블 관리 방법은 상기 논리적 어드레스를 입력받고, 상기 물리적 어드레스를 찾는 단계; 상기 물리적 어드레스에 해당하는 메모리 블록 내의 페이지 순서가 랩-어라운드 방식임을 표시하는지를 확인하는 단계; 상기 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)인 경우에, 상기 메모리 블록의 시작 페이지를 찾는 단계; 및 상기 메모리 블록 내의 페이지 순서를 알고, 원하는 페이지를 읽는 단계를 포함한다.

실시예로서, 상기 플래시 변환 레이어는 상기 플래시 메모리의 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)임을 표시한 플래그 정보와, 상기 메모리 블록의 시작 페이지를 지정한 오프셋 정보를 갖는다. 상기 플래시 변환 레이어는 논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블; 및 상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블을 포함한다. 상기 블록 맵핑 테이블은 순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보; 및 상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보를 저장한다.

다른 실시예로서, 상기 메모리 블록 내의 페이지 순서가 순차 위치 방식(in- place order)인 경우에, 원하는 페이지를 읽는 단계를 더 포함한다. 상기 플래시 변환 레이어는 상기 순차 위치 방식(in-place order)임을 표시한 플래그 정보를 갖는다. 상기 플래시 변환 레이어는 상기 플래그 정보를 블록 맵핑 테이블에 기록한다.

또 다른 실시예로서, 상기 플래시 변환 레이어는 논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블; 상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블; 및 임의 위치 방식에 따른 오프셋 정보를 저장하기 위한 랜덤 페이지 맵핑 테이블을 포함한다. 상기 블록 맵핑 테이블은 상기 순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보; 상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보; 및 상기 임의 위치 방식(out-of-place order)임을 표시하는 제 3 플래그 정보를 갖는다.

이하, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 발명의 기술적 사상을 용이하게 실시할 수 있을 정도로 상세히 설명하기 위하여, 본 발명의 바람직한 실시예를 첨부된 도면을 참조하여 설명하기로 한다.

도 1은 일반적인 플래시 메모리를 사용하는 메모리 시스템의 하드웨어 구조를 보여주는 블록도이다. 도 1을 참조하면, 메모리 시스템(100)은 중앙처리장치(110), 랜덤 액세스 메모리(120), 그리고 낸드 플래시 메모리(130)를 포함한다. 어드레스 맵핑 동작을 위한 플래시 변환 레이어(FTL)는 랜덤 액세스 메모리(120)에 저장된다.

낸드 플래시 메모리(130)는 당업자에게 잘 알려진 바와 같이, 스트링 구조(string structure)를 갖는 복수의 메모리 셀로 구성된다. 이러한 메모리 셀들의 집합을 셀 어레이(cell array)라고 부른다. 낸드 플래시 메모리(130)의 메모리 셀 어레이는 복수의 메모리 블록(memory block)으로 구성된다. 각각의 메모리 블록은 복수의 페이지(page)로 구성된다. 각각의 페이지는 하나의 워드 라인을 공유하는 복수의 메모리 셀로 구성된다.

낸드 플래시 메모리(130)는 읽기 및 쓰기 동작의 단위와 소거 동작의 단위가 다르다. 즉, 낸드 플래시 메모리(130)는 메모리 블록 단위로 소거 동작을 수행하고, 페이지 단위로 읽기 및 쓰기 동작을 수행한다. 또한, 낸드 플래시 메모리(130)는 다른 반도체 메모리 장치와 달리 겹쳐 쓰기(over write)를 지원하지 않는다. 따라서 낸드 플래시 메모리(130)는 쓰기 동작 전에 소거 동작을 수행한다.

낸드 플래시 메모리(130)의 이와 같은 특성으로 인해, 낸드 플래시 메모리(130)를 하드 디스크처럼 사용하기 위해서는, 읽기/쓰기/소거 동작에 대한 별도의 관리가 필요하다. 플래시 변환 레이어(Flash Translation Layer; 이하 FTL이라 함)는 이러한 목적으로 개발된 시스템 소프트웨어이다.

낸드 플래시 메모리(130)는 데이터 영역, 로그 영역, 그리고 메타 영역을 포함한다. 데이터 영역은 복수의 데이터 블록으로 구성되며, 사용자 데이터를 저장한다. 로그 영역은 하나 또는 그 이상의 로그 블록으로 구성된다. 로그 블록은 특정 데이터 블록에 할당되어 진다.

특정 데이터 블록에 데이터를 쓰고자 하는 경우, 데이터는 특정 데이터 블록 에 직접 쓰여 지는 것이 아니라, 할당되어 있는 로그 블록에 먼저 저장된다. 그 다음에, 머지(merge) 동작을 통해, 로그 블록의 유효한 페이지와 데이터 블록의 유효한 페이지가 새로운 데이터 블록으로 복사된다. 머지 동작이 수행되면, 맵핑 정보가 변경되는데, 변경된 맵핑 정보는 메타 영역에 저장된다.

도 2는 일반적인 플래시 메모리를 사용하는 메모리 시스템의 소프트웨어 구조를 보여주는 블록도이다. 도 2를 참조하면, 플래시 변환 레이어(FTL, 220)는 애플리케이션(205) 또는 파일 시스템(210)으로부터 논리적 어드레스를 입력받고, 이를 물리적 어드레스로 변환한 다음에, 변환한 물리적 어드레스를 낸드 플래시 메모리(230)로 제공한다.

어드레스 변환을 위한 맵핑 테이블은 도 1에 도시된 랜덤 액세스 메모리(120)에 저장된다. 맵핑 방법에는 맵핑 단위에 따라 여러 가지 방식이 있다. 예를 들면, 페이지 단위로 맵핑 동작을 수행하는 페이지 맵핑 방법(page mapping method), 블록 단위로 맵핑 동작을 수행하는 블록 맵핑 방법(block mapping method), 그리고 두 가지를 모두 사용하는 혼합 맵핑 방법(hybrid mapping method)이 있다.

페이지 맵핑 방법은 페이지 맵핑 테이블을 위해 많은 메모리 공간을 필요로 한다는 단점을 갖는다. 블록 맵핑 방법은 메모리 공간을 줄일 수 있지만, 많은 머지(merge) 동작을 수행한다는 단점을 갖는다. 혼합 맵핑 방법은 로그 블록(log block)에 대해서는 페이지 맵핑 방법을 사용한다. 혼합 맵핑 방법은 두 가지 맵핑 방법을 사용함으로, 맵핑 테이블의 크기를 줄임과 동시에, 머지 연산의 횟수를 줄 일 수 있다.

도 3은 일반적인 혼합 맵핑 방법을 수행하는 메모리 시스템을 보여주는 블록도이다. 도 3을 참조하면, 메모리 시스템(300)은 파일 시스템(310), 플래시 변환 레이어(320), 그리고 플래시 메모리(330)를 포함한다.

플래시 변환 레이어(320)는 파일 시스템(310)으로부터 논리적 섹터 번호(Logical Sector Number; LSN)를 입력받는다. 플래시 변환 레이어(320)는 맵핑 테이블을 사용하여 논리적 섹터 번호(LSN)를 물리적 섹터 번호(Physical Sector Number; PSN)로 변환한다. 플래시 변환 레이어(320)는 물리적 섹터 번호(PSN)를 플래시 메모리(330)로 제공한다.

도 3을 참조하면, 플래시 변환 레이어(320)는 블록 맵핑 테이블(321) 및 페이지 맵핑 테이블(322)을 포함한다. 여기에서, 페이지 맵핑 테이블(322)은 로그 블록의 페이지 맵핑을 위한 것이다. 로그 블록의 페이지 쓰기 동작 및 혼합 맵핑 동작은 도 4를 참조하여, 상세히 설명된다.

도 4는 도 3에 도시된 메모리 시스템의 혼합 맵핑 방법을 예시적으로 설명하기 위한 다이어그램이다. 도 4에서, 로그 블록(410) 및 데이터 블록(420)은 각각 4개의 페이지로 구성된다고 가정한다. 그리고 로그 블록(410)은 데이터 블록(420)에 할당되어 있다고 가정한다.

먼저, 쓰기 요청(write request)이 들어오면, 플래시 변환 레이어(도 3 참조, 320)는 데이터 블록(420)에 할당되어 있는 로그 블록(410)이 존재하는지를 검사한다. 검사 결과, 할당된 로그 블록(410)이 존재하면, 할당된 로그 블록(410)에 페이지 쓰기 동작을 수행한다. 만약, 할당된 로그 블록이 존재하지 않으면, 새로운 로그 블록을 할당받아 소거 동작을 수행한 다음에, 페이지 쓰기 동작을 수행한다.

도 4를 참조하면, 파일 시스템(도 3 참조, 310)은 2번, 3번, 0번, 1번 논리적 페이지 순서로 쓰기 요청을 하고 있다. 여기에서, 1번 논리적 페이지는 데이터는 데이터 블록(420)의 두 번째 물리적 페이지(이하, 제 2 물리적 페이지라 함)에 저장되어 있다.

2번 논리적 페이지에 대한 쓰기 요청이 들어오면, 로그 블록(410)의 첫 번째 물리적 페이지(이하, 제 1 물리적 페이지라 함)에 대한 쓰기 동작이 수행된다. 다음으로, 3번 논리적 페이지에 대한 쓰기 요청이 들어오면, 로그 블록(410)의 제 2 물리적 페이지에 대한 쓰기 동작이 수행된다. 그리고 0번 논리적 페이지에 대한 쓰기 요청이 들어오면, 로그 블록(410)의 세 번째 물리적 페이지(이하 제 3 물리적 페이지라 함)에 대한 쓰기 동작이 수행된다.

이때, 전체 로그 블록이 부족하여, 로그 블록(410)을 자유 블록(free block)으로 만들어야 하는 상황이 발생한다면, 플래시 변환 레이어(320)는 머지 동작을 수행한다. 즉, 로그 블록(410)의 제 1 내지 제 3 물리적 페이지에 저장된 2번, 3번, 0번 논리적 페이지와 데이터 블록(420)의 제 2 물리적 페이지에 저장된 1번 논리적 페이지는 새로운 데이터 블록(430)으로 복사된다.

먼저, 논리 블록(410)의 0번 페이지가 새로운 데이터 블록(430)의 제 1 물리적 페이지에 복사된다. 다음에, 데이터 블록(420)의 1번 페이지가 새로운 데이터 블록(430)의 제 2 물리적 페이지에 복사된다. 다음에, 논리 블록(410)의 2번 및 3 번 페이지가 새로운 데이터 블록(430)의 제 3 및 제 4 물리적 페이지에 복사된다. 다음에, 로그 블록(410) 및 데이터 블록(420)은 소거된다.

이와 같이, 혼합 맵핑 방법에 의하면, 로그 블록(410)과 데이터 블록(420)의 유효한 페이지(valid page)는 머지 동작에 의해 새로운 데이터 블록(430)으로 복사된다. 새로운 데이터 블록(430)에는 0번 페이지부터 3번 페이지까지 순차적으로 쓰여 진다. 하나의 블록에 0번 페이지부터 순차적으로 쓰여 지는 것을 순차 위치 방식(in-place order)라고 한다. 반면에, 하나의 블록에 페이지들이 임의로 쓰여 지는 것을 임의 위치 방식(out-of-place order 또는 random-place order)라고 한다.

쓰기 요청이 0번, 1번, 2번, 3번 논리적 페이지 순서이면, 이들 논리적 페이지는 로그 블록(410)의 제 1 내지 제 4 물리적 페이지에 순차적으로 쓰여 진다. 로그 블록(410)에 쓰여진 페이지들은 별도의 페이지 복사 없이 곧바로 데이터 블록으로 등록될 수 있다. 이것은 로그 블록(410)이 순차 위치 방식(in-place order)에 맞게 페이지를 배열하고 있기 때문이다.

그러나 쓰기 요청이 임의적일 때에는, 페이지 순서를 맞추기 위한 페이지 복사 과정이 반드시 필요하게 된다. 도 4의 예에서는, 4번의 페이지 복사 과정이 필요하다. 또한, 페이지 복사 후에는 로그 블록(410)과 데이터 블록(420)에 대한 2번의 소거 동작이 필요하다.

이상에서 설명한 바와 같이, 혼합 맵핑 방법을 사용한다 해도, 페이지 순서를 맞추기 위해 많은 수의 페이지 복사 과정이 필요하다. 또한, 페이지 복사 후에는 로그 블록과 데이터 블록을 소거하기 위해 두 번의 블록 소거 동작이 필요하다.

본 발명은 혼합 맵핑 방법의 이러한 문제점을 해결하기 위한 것이다. 본 발명은 임의 위치 방식(out-of-place order) 중 일부에 대해, 순차 위치 방식(in-place order)처럼 처리함으로, 페이지 복사 횟수 및 블록 소거 횟수를 줄인다. 본 발명에 의하면, 페이지 복수 횟수 및 블록 소거 횟수가 줄어들기 때문에 전체 메모리 시스템의 성능이 크게 향상된다. 이하에서는 본 발명에 따른 메모리 시스템 및 그것의 혼합 맵핑 방법에 대해 상세하게 설명된다.

도 5는 본 발명에 따른 혼합 맵핑 동작을 사용하는 메모리 시스템을 보여주는 블록도이다. 도 5를 참조하면, 메모리 시스템(400)은 파일 시스템(410), 플래시 변환 레이어(420), 그리고 플래시 메모리(430)를 포함한다.

플래시 변환 레이어(420)는 파일 시스템(410)으로부터 논리적 섹터 번호(LSN)를 입력받고, 맵핑 테이블을 사용하여 논리적 섹터 번호(LSN)를 물리적 섹터 번호(PSN)로 변환한다. 플래시 변환 레이어(420)는 물리적 섹터 번호(PSN)를 플래시 메모리(430)로 제공한다.

도 5를 참조하면, 플래시 변환 레이어(420)는 블록 맵핑 테이블(421) 이외에, 랩-어라운드 페이지 맵핑 테이블(422)과 랜덤 페이지 맵핑 테이블(423)을 더 포함한다. 여기에서, 랜덤 페이지 맵핑 테이블(423)은 임의 위치 방식(out-of-place order) 방식에 따른 페이지 변환을 지정한 것이다. 랜덤 페이지 맵핑 테이블(423)은 도 6을 참조하여 상세히 설명된다.

랩-어라운드 페이지 맵핑 테이블(422)은 랩-어라운드 방식(wrap-around order)에 따른 페이지 변환을 지정한 것이다. 여기에서, 랩-어라운드 방식(wrap- around order)이란 페이지 위치 순서가 순차적으로 증가하되, 시작 페이지가 0번이 아닌 것을 의미한다. 예를 들어, 하나의 블록이 4개의 페이지로 구성되어 있다면, 랩-어라운드 방식(wrap-around order)에는 다음과 같은 경우가 있다.

1) 1번 페이지 -> 2번 페이지 -> 3번 페이지 -> 0번 페이지

2) 2번 페이지 -> 3번 페이지 -> 0번 페이지 -> 1번 페이지

3) 3번 페이지 -> 0번 페이지 -> 1번 페이지 -> 2번 페이지

랩-어라운드 방식(wrap-around order)은 순차 위치 방식(in-place order)과 마찬가지로 순차적으로 쓰여 진다. 다만, 시작 페이지가 0번 페이지가 아닐 따름이다. 도 3 및 도 4에 도시된 혼합 맵핑 방법에서는 랩-어라운드 방식(wrap-around order)의 경우에도 임의 위치 방식(out-of-place order)과 마찬가지로 처리된다. 즉, 도 4에 도시된 바와 같이, 4번의 페이지 복사와 2번의 블록 소거 동작이 수행된다.

그러나 본 발명에 따른 메모리 시스템(400)은 랩-어라운드 페이지 맵핑 테이블(422)을 구비함으로, 랩-어라운드 방식(wrap-around order)을 순차 위치 방식(in-place order)처럼 처리한다. 본 발명에 의하면, 도 4의 예에서, 1번의 페이지 복사와 1번의 블록 소거 동작이 수행된다. 이는 도 7을 참조하여 상세히 설명된다.

도 6은 도 5에 도시된 메모리 시스템의 맵핑 테이블 관리 방법을 예시적으로 보여주는 도표이다. 도 6(a)는 블록 맵핑 테이블, 도 6(b)는 랩-어라운드 페이지 맵핑 테이블, 도 6(c)는 랜덤 페이지 맵핑 테이블, 그리고 도 6(d)는 물리적 블록 의 페이지 위치를 보여준다.

도 6(a)를 참조하면, 블록 맵핑 테이블은 논리적 블록 번호(Logical Block Number; LBN), 물리적 블록 번호(Physical Block Number; PBN), 플래그 정보를 갖는다. 도 6(a)에서 참고(Note)에는 플래그 정보에 따른 페이지 위치 방식이 도시되어 있다.

플래그(Flag) 0은 순차 위치 방식(in-place order)을 뜻한다. 플래그(Flag) 1은 랩-어라운드 방식(wrap-around order)을 뜻한다. 그리고 플래그(Flag) 2는 임의 위치 방식(out-of-place order)을 뜻한다. 즉, 블록 맵핑 테이블은 페이지 위치 방식을 정의한 플래그 정보를 갖는다.

여기에서, 순차 위치 방식(in-place order)은 0번 페이지부터 시작하기 때문에, 오프셋(offset) 정보를 필요로 하지 않는다. 그러나 랩-어라운드 방식(wrap-around order)은 시작 페이지를 정의해 주어야 한다. 그리고 임의 위치 방식(out-of-place order)은 페이지 순서를 정의해 주어야 한다.

도 6(b)는 랩-어라운드 페이지 맵핑 테이블을 보여준다. 도 6(b)를 참조하면, 물리적 블록 번호 400은 오프셋 1을 갖는다. 이는 물리적 블록 번호 400의 시작 페이지가 1번 페이지임을 뜻한다. 물리적 블록 번호 500은 오프셋 2를 갖는다. 이는 물리적 블록 번호 500의 시작 페이지가 2번 페이지임을 뜻한다. 즉, 물리적 블록 번호 500의 제 1 물리적 페이지에는 2번 논리적 페이지가 쓰여 진다. 물리적 블록 번호 600은 오프셋 3을 갖는다. 이는 물리적 블록 번호 600의 시작 페이지가 3번 페이지임을 뜻한다. 물리적 블록 번호 400 내지 600의 페이지 위치는 도 6(d) 에 구체적으로 도시되어 있다.

도 6(c) 랜덤 페이지 맵핑 테이블을 보여준다. 랜덤 페이지 맵핑 테이블에는 임의 위치 방식(out-of-place order)에 따른 페이지 순서가 정의되어 있다. 도 6(c)를 참조하면, 물리적 블록 번호(PBN) 700에 대한 오프셋 정보는 0, 3, 2, 1이다. 따라서 물리적 블록 번호(PBN) 700의 제 1 내지 제 4 물리적 페이지에는 0번, 3번, 2번, 1번 페이지가 쓰여 진다. 물리적 블록 번호(PBN) 800에 대한 오프셋 정보는 1, 3, 2, 0이다. 따라서 물리적 블록 번호(PBN) 800의 제 1 내지 제 4 물리적 페이지에는 1번, 3번, 2번, 0번 페이지가 쓰여 진다. 물리적 블록 번호 700 및 800의 페이지 위치는 도 6(d)에 구체적으로 도시되어 있다.

이하에서는 도 6에 도시된 맵핑 테이블을 참조하여, 페이지 읽기 동작이 설명된다.

먼저, 1번 블록의 2번 페이지에 대한 페이지 읽기 동작이 설명된다. 플래시 변환 레이어(FTL)는 블록 맵핑 테이블을 참조하여, 1번 논리적 블록 번호(LBN)에 대응하는 200번 물리적 블록 번호(PBN)를 찾는다. 플래시 변환 레이어(FTL)는 플래그 정보를 확인한다. 도 6(a)에서, 1번 논리적 블록 번호(LBN)에 대응하는 플래그(Flag)는 0이다. 이것은 200번 물리적 블록 번호(PBN)는 순차 위치 방식(in-place order)에 따라 페이지가 배열되어 있음을 뜻한다. 따라서 200번 물리적 블록 번호(PBN)의 1번 페이지가 읽혀진다.

다음으로, 4번 블록의 2번 페이지에 대한 페이지 읽기 동작이 설명된다. 플래시 변환 레이어(FTL)는 블록 맵핑 테이블을 참조하여, 4번 논리적 블록 번 호(LBN)에 대응하는 500번 물리적 블록 번호(PBN)를 찾는다. 플래시 변환 레이어(FTL)은 4번 논리적 블록 번호(LBN)에 대응하는 플래그(Flag) 1을 확인한다. 이것은 500번 물리적 블록 번호(PBN)는 랩-어라운드 방식(wrap-around order)에 따라 페이지가 배열되어 있음을 뜻한다.

플래시 변환 레이어(FTL)는 도 6(b)에 도시되어 있는 랩-어라운드 페이지 맵핑 테이블을 참조한다. 도 6(b)를 참조하면, 500번 물리적 블록 번호(PBN)에 대한 오프셋 정보는 2이다. 따라서 500번 물리적 블록 번호(PBN)에는 2번, 3번, 0번, 1번 페이지 순서로 배열되어 있다. 따라서 500번 물리적 블록 번호(PBN)에 있는 3번 페이지가 읽혀진다.

마지막으로, 6번 블록의 2번 페이지에 대한 읽기 동작이 설명된다. 플래시 변환 레이어(FTL)는 블록 맵핑 테이블을 참조하여, 6번 논리적 블록 번호(LBN)에 대응하는 700번 물리적 블록 번호(PBN)를 찾는다. 플래시 변환 레이어(FTL)는 6번 논리적 블록 번호(LBN)에 대응하는 플래그(Flag) 2를 확인한다. 이것은 700번 물리적 블록 번호(PBN)는 임의 위치 방식(out-of-place order)에 따라 페이지가 배열되어 있음을 뜻한다.

플래시 변환 레이어(FTL)는 도 6(c)에 도시되어 있는 랜덤 페이지 맵핑 테이블을 참조한다. 도 6(c)를 참조하면, 700번 물리적 블록 번호(PBN)에 대한 오프셋 정보는 0, 3, 2, 1이다. 따라서 700번 물리적 블록 번호(PBN)에는 0번, 3번, 2번, 1번 페이지 순서로 배열되어 있다. 따라서 700번 물리적 블록 번호(PBN)에 있는 3번 페이지가 읽혀진다.

도 6(d)에는 각각의 물리적 블록 번호에 대한 페이지 위치 방식이 도시되어 있다. 물리적 블록 번호(PBN) 100 내지 300은 플래그(Flag) 0이므로, 순차 위치 방식(in-place order)따라 페이지가 배열되어 있다. 물리적 블록 번호(PBN) 400 내지 600은 플래그(Flag) 1이므로, 랩-어라운드 방식(wrap-around order)에 따라 페이지가 배열되어 있다. 그리고 물리적 블록 번호(PBN) 700 및 800은 플래그(Flag) 2이므로, 임의 위치 방식(out-of-place order)에 따라 페이지가 배열되어 있다.

도 7은 도 5에 도시된 메모리 시스템의 혼합 맵핑 동작을 예시적으로 설명하기 위한 다이어그램이다. 도 4에 도시된 맵핑 방법에 의하면, 4번의 페이지 복사와 2번의 블록 소거 동작이 수행된다. 그러나 도 7에 도시된 맵핑 방법에 의하면, 1번의 페이지 복수와 1번의 블록 소거 동작이 수행된다.

도 7에 도시된 바와 같이, 로그 블록(510)의 제 1 내지 제 3 물리적 페이지에는 2번, 3번, 0번 페이지가 쓰여져 있고, 데이터 블록(520)의 제 2 물리적 페이지에는 1번 페이지가 쓰여져 있다. 여기에서, 페이지 위치 순서가 2번, 3번, 0번, 1번이면, 랩-어라운드 방식(wrap-around order)이 된다.

이러한 경우에, 본 발명에서는 데이터 블록(520)의 제 2 물리적 페이지에 저장된 1번 페이지가 로그 블록(510)의 제 4 번 물리적 페이지에 복사된다. 그리고 로그 블록(510)은 새로운 데이터 블록으로 등록된다. 로그 블록(510)은 블록 맵핑 테이블 및 랩-어라운드 페이지 맵핑 테이블에, 플래그 1, 오프셋 2를 갖는 새로운 데이터 블록으로 등록된다. 데이터 블록(520)은 소거된다. 따라서, 도 5에 도시된 메모리 시스템(400)은 한 번의 페이지 복사와 1번의 블록 소거 동작을 수행한다.

한편, 본 발명에 따른 메모리 시스템은 메모리의 공간이 충분할 경우에는 랜덤 페이지 맵핑 테이블을 추가할 수도 있다. 본 발명에 따른 메모리 시스템은 랩-어라운드 방식(wrap-around order)을 순차 위치 방식(in-place order)과 동일하게 처리한다. 본 발명에 의하면, 머지 연산에 필요한 페이지 복수 횟수 및 블록 소거 횟수를 크게 줄일 수 있다.

본 발명은 플래그 정보 및 오프셋 정보를 참조하여 읽기 동작을 수행하기 때문에, 도 4에 도시된 것처럼 페이지 순서를 맞출 필요가 없다. 본 발명에 의하면, 페이지 복사 횟수와 블록 소거 횟수가 줄어들기 때문에 메모리 시스템의 성능이 크게 향상된다.

또한, 블록 맵핑 테이블은 플래그 정보를 기록하기 위해 2비트 정도의 메모리 공간만을 더 필요로 한다. 또한, 랩-어라운드 페이지 맵핑 테이블은 오프셋 정보를 기록하기 위해 1비트 내지 2비트 정도의 메모리 공간만을 필요로 한다. 따라서 본 발명에 따른 메모리 시스템 및 그것의 맵핑 테이블 관리 방법은 메모리의 공간을 크게 늘리지 않으면서, 페이지 복사 횟수 및 블록 소거 횟수를 크게 줄일 수 있다.

한편, 본 발명의 상세한 설명에서는 구체적인 실시예에 관하여 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한도 내에서 여러 가지 변형이 가능함은 물론이다. 그러므로 본 발명의 범위는 상술한 실시예에 국한되어 정해져서는 안되며 후술하는 특허청구범위 뿐만 아니라 이 발명의 특허청구범위와 균등한 것들에 의해 정해져야 한다.

이상에서 살펴본 바와 같이, 본 발명에 따른 메모리 시스템 및 그것의 맵핑 테이블 관리 방법에 의하면, 메모리의 공간을 크게 늘리지 않으면서, 페이지 복사 횟수 및 블록 소거 횟수를 크게 줄일 수 있다.

Claims

파일 시스템;

상기 파일 시스템으로부터 논리적 어드레스를 입력받고, 상기 논리적 어드레스를 물리적 어드레스로 변환하는 플래시 변환 레이어; 및

상기 변환된 물리적 어드레스를 입력받는 플래시 메모리를 포함하되,

상기 플래시 변환 레이어는 상기 플래시 메모리의 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)임을 표시한 플래그 정보와, 상기 메모리 블록의 시작 페이지를 지정한 오프셋 정보를 갖는 메모리 시스템.
제 1 항에 있어서,

상기 플래시 변환 레이어는

논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블; 및

상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블을 포함하는 메모리 시스템.
제 2 항에 있어서,

상기 블록 맵핑 테이블은 상기 메모리 블록에 대한 플래그 정보를 저장하는 메모리 시스템.
제 2 항에 있어서,

상기 블록 맵핑 테이블은

순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보; 및

상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보를 갖는 메모리 시스템.
제 4 항에 있어서,

상기 블록 맵핑 테이블은 임의 위치 방식(out-of-place order)임을 표시하는 제 3 플래그 정보를 더 갖는 메모리 시스템.
제 5 항에 있어서,

상기 플래시 변환 레이어는 상기 임의 위치 방식에 사용될 오프셋 정보를 저장하기 위한 랜덤 페이지 맵핑 테이블을 더 포함하는 메모리 시스템.
제 1 항에 있어서,

상기 플래시 메모리는 낸드 플래시 메모리인 것을 특징으로 하는 메모리 시스템.
메모리 시스템의 맵핑 테이블 관리 방법에 있어서:

상기 메모리 시스템은

파일 시스템;

상기 파일 시스템으로부터 논리적 어드레스를 입력받고, 상기 논리적 어드레스를 물리적 어드레스로 변환하는 플래시 변환 레이어; 및

상기 변환된 물리적 어드레스를 입력받는 플래시 메모리를 포함하고,

상기 메모리 시스템의 맵핑 테이블 관리 방법은

상기 논리적 어드레스를 입력받고, 상기 물리적 어드레스를 찾는 단계;

상기 물리적 어드레스에 해당하는 메모리 블록 내의 페이지 순서가 랩-어라운드 방식임을 표시하는지를 확인하는 단계;

상기 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)인 경우에, 상기 메모리 블록의 시작 페이지를 찾는 단계; 및

상기 메모리 블록 내의 페이지 순서를 알고, 원하는 페이지를 읽는 단계를 포함하는 맵핑 테이블 관리 방법.
제 8 항에 있어서,

상기 플래시 변환 레이어는 상기 플래시 메모리의 메모리 블록 내의 페이지 순서가 랩-어라운드 방식(wrap-around order)임을 표시한 플래그 정보와, 상기 메모리 블록의 시작 페이지를 지정한 오프셋 정보를 갖는 맵핑 테이블 관리 방법.
제 9 항에 있어서,

상기 플래시 변환 레이어는

논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블; 및

상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블을 포함하는 맵핑 테이블 관리 방법.
제 10 항에 있어서,

상기 블록 맵핑 테이블은

순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보; 및

상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보를 저장하는 맵핑 테이블 관리 방법.
제 8 항에 있어서,

상기 메모리 블록 내의 페이지 순서가 순차 위치 방식(in-place order)인 경우에, 원하는 페이지를 읽는 단계를 더 포함하는 맵핑 테이블 관리 방법.
제 12 항에 있어서,

상기 플래시 변환 레이어는 상기 순차 위치 방식(in-place order)임을 표시한 플래그 정보를 갖는 맵핑 테이블 관리 방법.
제 13 항에 있어서,

상기 플래시 변환 레이어는 상기 플래그 정보를 블록 맵핑 테이블에 기록하는 맵핑 테이블 관리 방법.
제 8 항에 있어서,

상기 플래시 변환 레이어는

논리적 블록 어드레스를 물리적 블록 어드레스로 변환하기 위한 블록 맵핑 테이블;

상기 메모리 블록의 시작 페이지를 지정하기 위한 오프셋 정보를 저장하는 랩-어라운드 페이지 맵핑 테이블; 및

임의 위치 방식에 따른 오프셋 정보를 저장하기 위한 랜덤 페이지 맵핑 테이블을 포함하는 맵핑 테이블 관리 방법.
제 15 항에 있어서,

상기 블록 맵핑 테이블은

상기 순차 위치 방식(in-place order)임을 표시하는 제 1 플래그 정보;

상기 랩-어라운드 방식임을 표시하는 제 2 플래그 정보; 및

상기 임의 위치 방식(out-of-place order)임을 표시하는 제 3 플래그 정보를 갖는 맵핑 테이블 관리 방법.