KR101329068B1 - 블록 관리를 가지는 비휘발성 메모리 - Google Patents

Abstract

블록 소거 가능 메모리 어레이를 포함하는 비휘발성 메모리 시스템에서, 기록들은 블록들의 특정 분류를 위하여 개별적으로 유지된다. 하나 또는 그 이상의 리스트들은 블록들을 위하여 유지되고, 개별 리스트는 디스크립터 값에 따라 순서가 매겨진다. 상기 순서가 매겨진 리스트들은 디스크립터 값에 의해 블록을 빨리 식별하게 한다.

Description

블록 관리를 가지는 비휘발성 메모리{NONVOLATILE MEMORY WITH BLOCK MANAGEMENT}

이 출원은 반도체 플래시 메모리 같은 재프로그램 가능한 비휘발성 메모리 시스템들의 작동, 및 특히 메모리 어레이의 개별 소거 가능 블록들의 관리에 관한 것이다.

호스트 시스템들, 메모리 시스템들 및 다른 전자 시스템들의 외부 인터페이스들을 통하여 통신되는 데이터를 어드레스하는 두 개의 주 기술들이 있다. 그중 하나에서, 시스템에 의해 생성되거나 수신된 데이터 파일들의 어드레스들은 데이터의 논리 블록들(이후 "LBA 인터페이스"라 함) 측면에서 시스템을 위하여 형성된 연속적인 논리 어드레스 공간의 개별 범위들에 맵핑된다. 어드레스 공간 크기는 통상적으로 시스템이 처리할 수 있는 전체 어드레스들의 범위를 커버하기에 충분하다. 일실시예에서, 자기 디스크 저장 드라이브들은 이러한 논리 어드레스 공간을 통하여 컴퓨터들 또는 다른 호스트 시스템들과 통신한다. 이 어드레스 공간은 디스크 드라이브의 전체 데이터 저장 용량을 처리하기에 충분한 크기를 가진다.

플래시 메모리 시스템들은 가장 일반적으로 퍼스널 컴퓨터, 카메라 또는 등등 같은 다양한 호스트들과 탈착 가능하게 접속되지만, 상기 호스트 시스템들 내에 도 내장될 수 있는 메모리 카드 또는 플래시 드라이브 형태로 제공된다. 메모리에 데이터를 기입할 때, 호스트는 통상적으로 고유 논리 어드레스들을 섹터들, 클러스터들 또는 메모리 시스템의 연속적인 가상 어드레스 공간 내 데이터의 다른 유니트들에 할당한다. 디스크 작동 시스템(DOS)과 같이, 호스트는 메모리 시스템의 논리 어드레스 공간내 어드레스들에 데이터를 기입하고, 상기 어드레스들로부터 데이터를 판독한다. 메모리 시스템내 제어기는 호스트로부터 수신된 논리적 어드레스들을 데이터가 실제로 저장되는 메모리 어레이내 물리적 어드레스들로 번역하고, 그 다음 이들 어드레스 번역들의 트랙을 유지한다. 메모리 시스템의 데이터 저장 용량은 적어도 메모리 시스템을 위하여 정의된 전체 논리 어드레스 공간을 통하여 어드레스할 수 있는 데이터 양만큼 크다.

현재 상업적 플래시 메모리 시스템들에서, 소거 유니트의 크기는 데이터의 다중 섹터들을 저장하기 위하여 충분한 메모리 셀들의 블록으로 증가되었다. 정말로, 많은 데이터 페이지들은 하나의 블록에 저장되고, 하나의 페이지는 데이터의 다중 섹터들을 저장할 수 있다. 게다가, 둘 또는 그 이상의 블록들은 메타블록들 처럼 종종 함께 작동되고, 상기 블록들의 페이지들은 메타페이지들처럼 논리적으로 함께 링크된다. 데이터의 많은 섹터들을 포함할 수 있는 데이터의 페이지 또는 메타페이지는 함께 기입 및 판독되어, 작동 병렬성을 증가시킨다. 상기 큰 용량 작동 유니트들은 효율적 작동에서 문제에 봉착한다.

설명을 용이하게 하기 위하여, 특정하게 지정되지 않으면, 여기에 사용된 용어 "블록"은 메타블록들이 특정 시스템에 사용되는지 여부에 따라 소거 블록 유니 트이거나 다중 블록 "메타블록"이라 불리는 것으로 의도된다. 유사하게, 여기에서 "페이지"는 시스템 구성에 따라 단일 블록내 프로그래밍 유니트 또는 메타블록내 "메타페이지"일 수 있다.

메모리 시스템에 대한 현재 널리 보급된 LBA 인터페이스가 사용될 때, 메모리가 접속되는 호스트에 의해 생성된 파일들은 인터페이스의 논리 어드레스 공간 내에 고유 어드레스가 할당된다. 그 다음 메모리 시스템은 통상적으로 논리 어드레스 공간 및 메모리 물리 블록들의 페이지 사이 데이터를 맵핑한다. 메모리 시스템은 논리 어드레스 공간이 물리적 메모리에 맵핑되지만 호스트가 이를 인식하지 못하는 방법의 트랙을 유지한다. 호스트는 논리 어드레스 공간 내 데이터 파일들의 어드레스들의 트랙을 유지하지만 메모리 시스템은 이런 맵핑 지식을 거의 또는 전혀 가지지 않고 작동한다.

제 2의 사용된 두 개의 시스템 인터페이스 기술들에서, 전자 시스템에 의해 생성되거나 수신된 데이터 파일들은 고유하게 식별되고 그 데이터는 파일내 오프셋들에 의해 논리적으로 어드레스된다. 이런 어드레싱 방법의 형태는 컴퓨터들 또는 다른 호스트 시스템들과, "스마트 카드"로서 공지된 제거 가능한 메모리 카드 사이에서 사용된다. 스마트 카드들은 통상적으로 식별, 뱅킹, 매장 구입, ATM 액세스 및 등등을 위하여 소비자들에 의해 사용되고, 플래시 메모리 카드들 및 플래시 드라이브들과 비교할 때 작은 양의 메모리를 포함한다.

상기된 특허 출원들에서, 데이터 파일은 호스트에 의해 할당된 파일네임에 의해 대량 저장 플래시 메모리 시스템에서 식별되고 파일의 데이터는 파일(이후 " 직접적인 데이터 파일 인터페이스") 내 오프셋 어드레스들에 의해 액세스된다. 그 다음 메모리 시스템은 데이터의 각각의 섹터 또는 다른 유니트가 속하는 호스트 파일을 안다. 여기에 논의된 파일 유니트는 순차적 논리 오프셋 어드레스들을 가짐으로써 순서가 매겨지고, 메모리 시스템이 접속되는 호스트 계산 시스템에서 작동하는 애플리케이션 프로그램에 의해 생성되고 고유하게 식별되는 데이터 세트이다.

4개의 실용 특허 출원들(출원 번호 11/382,224; 11/382,228; 11/382,232; 11/382,235, 2006년 5월 8일 출원됨)은 블록들의 리스트들이 메모리 시스템의 작동 동안 액세스를 위하여 유지되는 기술들을 기술한다. 리스트상 개별 엔트리들은 메모리 블록들 및 그들의 어드레스들의 파라미터들을 포함한다. 리스트내 엔트리는 관련된 블록의 물리적 어드레스, 또는 엔트리내에 기록된 블록 파라미터의 값에 따라 선택될 수 있다. 본 설명은 플래시 메모리내 지정된 블록내에 하나 또는 그 이상의 데이터 블록들의 리스트를 저장하고, 엔트리내 필드의 정보 콘텐트를 바탕으로 리스트내 특정 엔트리에 액세스하는 것에 관한 것이다.

상기 기술은 둘 또는 그 이상의 리스트들의 모든 블록의 정보를 포함하는 순서가 매겨지지 않은 기록들의 저장을 위해 지정된 블록내 논리 페이지들의 일부를 사용한다. 다른 페이지들은 블록들에 대한 콘텐트 어드레스 가능 파라미터만을 포함하는 엔트리들의 리스트들, 및 블록의 전체 기록에 대한 포인트에 사용된다. 이들 리스트들 내부의 엔트리들은 파라미터 값들의 순서로 저장되고, 특정 파라미터 값을 가진 엔트리는 빠르게 액세스될 수 있다. 상기 리스트들은 블록들에 대한 순서가 매겨지지 않은 기록들에 대한 디렉토리 형태로서 작동한다.

블록 소거 가능 비휘발성 메모리에서, 그들이 포함하는 개별 블록들 및 데이터상에 최신 정보를 유지하는 것은 충분한 메모리 관리를 허용한다. 블록들이 하나 또는 그 이상의 파일들, 무용(obsolete) 데이터, 및 소거 공간의 유효 데이터 혼합을 포함하는 경우, 상기 블록들은 매우 복잡할 수 있다. 그러나, 블록 단위로 상기 데이터의 트랙을 유지함으로써, 특정 메모리 시스템 작동들, 특히 메모리 어레이에서 사용되지 않는 공간의 재생(reclaim)은 효율적으로 수행될 수 있다. 사용되지 않는 공간(무용 데이터 또는 사용될 수 없는 소거 공간을 포함하는 공간)의 재생은 블록 단위로 발생한다(여기서 블록은 소거 단위이다). 유효 데이터의 카피를 감소시키기 위하여 효율적인 순서로 블록들상 블록 재생 작동들을 수행하는 것은 바람직하다. 블록 재생 순서를 결정하기 위하여, 블록들이 하나 또는 그 이상의 디스크립터(descriptor) 값들의 순서로 랭크되는 것이 유용하고, 여기서 디스크립터 값은 블록내에 저장된 데이터의 적어도 하나의 측면을 나타낸다. 예를들어, 블록들은 최소량의 유효 데이터를 포함하는 블록들이 우선 재생되어 빠르게 식별될 수 있도록 그들이 포함하는 유효 데이터의 양에 의해 순서가 정해질 수 있다.

제 1 실시예에서, 기록들은 필수적으로 모든 블록들을 통해서가 아니고 메모리 어레이내 다양한 블록들에 대해 유지된다. 유효 데이터를 포함하는 블록들은 그들이 소거된 공간(부분 블록들)을 포함하는지, 그렇지 않으면 그들이 무용 데이터(무용 블록들)를 포함하는지 여부에 따라 분류된다. 유일한 무용 데이터(무효한 블록들)만을 가진 블록들 및 단지 소거 공간(소거 블록들) 만을 포함하는 블록들은 개별적으로 분류된다. 기록은 각각의 블록이 이들 분류들 중 하나를 가지게 유지된다. 기록들은 전용 기록 블록들에 유지된다. 게다가, 분류시 블록들은 디스크립터 값에 의해 순서가 매겨지는 리스트들에 리스트된다. 디스크립터 값은 블록내 유효 데이터 양, 블록의 어드레스 또는 몇몇 다른 디스크립터 값일 수 있다. 제 1 예에서 리스트 엔트리들은 대응 기록들에 대한 포인터들을 포함한다.

제 2 예에서, 기록들은 다양한 분류시 블록들을 위하여 유지된다. 분류된 "완전한 공통 블록"은 하나 이상의 파일 데이터를 포함하고 무용 데이터 또는 소거 공간을 포함하지 않은 블록을 위하여 부가된다. 기록들은 전용 기록 블록들의 전용 기록 페이지들에 유지된다. 기록은 블록 어드레스, 포함한 유효 데이터 양, 기입 포인터 위치 등등을 포함하는 대응 블록에 관한 다양한 정보를 포함할 수 있다.

디렉토리는 개별 기록이 빠르게 발견되게 제공된다. 디렉토리의 엔트리는 기록 페이지 및 기록 페이지내 대응 기록의 위치를 식별한다. 디렉토리는 블록 어드레스에 의해 순서가 매겨진 디렉토리 엔트리들을 가지며 디렉토리 블록내 전용 디렉토리 페이지들에 유지된다. 디렉토리 페이지들은 오버랩핑되지 않은 블록 어드레스 범위들을 포함한다. 하나의 디렉토리 페이지는 하나 이상의 기록 페이지에 대한 포인터들을 포함할 수 있다. 그러나, 기록 페이지는 하나의 디렉토리 페이지의 엔트리에 의해 포인트된 기록들만을 포함한다. 따라서, 기록 페이지의 기록들이 업데이트될 때, 단지 하나의 디렉토리 페이지는 업데이트될 필요가 있다.

디렉토리 블록들은 또한 하나 또는 그 이상의 리스트들을 포함할 수 있다. 리스트의 엔트리는 블록 어드레스 및 디스크립터 값을 포함하고 리스트내 엔트리들은 디스크립터 값에 의해 순서가 매겨진다. 예시적인 디스크립터 값은 블록내 유효 데이터 양이다. 리스트들은 블록내 데이터를 바탕으로 재생 또는 다른 목적들을 위하여 블록을 선택하기 위한 편리한 방식을 제공한다. 예를 들어, 최소 양의 유효 데이터를 가진 무용 블록은 디스크립터 값으로서 유효 데이터 양을 사용하는 무용 블록들의 리스트 내 제 1 엔트리이다. 이 블록은 리스트가 재생 작동을 위한 큐를 제공하도록 재생을 위해 리스트로부터 빠르게 식별될 수 있다. 다른 예들에서, 특정 디스크립터 값을 가진 블록은 찾아질 수 있다. 이것은 적당한 리스트 페이지상에서 이진 검색을 수행함으로써 빠르게 식별될 수 있다.

제 3 실시예에서, 기록은 언제든 비휘발성 메모리 어레이의 각각의 블록을 위하여 유지된다. 이 경우, 디렉토리 페이지는 블록 어드레스에 순차적으로 순서가 매겨진 엔트리들을 가진 고정된 블록 어드레스 범위에 대한 엔트리들을 포함한다. 이것은 디렉토리 페이지 내에서 미리 결정된 오프셋으로 특정 블록을 위한 엔트리를 제공하기 때문에, 엔트리들은 그들이 인용하는 블록의 블록 어드레스를 포함하지 않는다.

리스트들을 관리 및 액세스하는 기술들이 플래시 데이터 파일 인터페이스와 함께 작동하는 플래시 메모리에 사용하기 위하여 여기에 기술되었지만, 이들 기술들은 다른 애플리케이션에서 다른 형태의 리스트들에 사용될 수 있다.

도 1은 제 1 실시예에 따른 블록 분류 테이블을 도시한다.

도 2는 제 1 실시예에 따른 기록 블록의 페이지들을 도시한다.

도 3은 도 2의 기록 블록의 개별 페이지의 상세한 도면을 도시한다.

도 4는 제 2 실시예에 따른 블록 분류 테이블을 도시한다.

도 5는 블록 기록 블록에서 대응 블록 기록에 포인팅하는 블록 디렉토리 블록내 블록 디렉토리 엔트리를 도시한다.

도 6은 디렉토리 블록의 페이지 구조의 일부 상세도를 도시한다.

도 7A는 기록 인덱스 및 디렉토리 인덱스를 포함하는 도 6의 블록 디렉토리 페이지의 구조를 도시한다.

도 7B는 도 6의 무용 블록 리스트 페이지의 구조를 도시한다.

도 8은 기록 블록의 페이지 구조의 일부 상세도를 도시한다.

도 9는 도 8의 기록 페이지의 구조를 보다 상세히 도시한다.

도 10은 블록 기록들 및 관련 구조들의 업데이트를 겪는 디렉토리 블록 및 기록 블록을 도시한다.

상기된 특허 출원에 기술된 직접적인 데이터 파일 저장 기술들은 개별 블록들의 사용에 관련된 미리 정의된 값들을 가진 엔트리들이 선택된 블록들의 리스트들을 형성한다. 이들 블록 리스트들의 콘텐트 어드레스 가능 검색을 위한 기술은 여기에 사용된다. 이 설명은 도 1-3을 참조한다.

도 1은 콘텐츠들을 바탕으로 메모리 셀 블록들의 분류를 도시하는 테이블이다. 실제로 메모리 시스템의 모든 블록들은 도시된 바와 같이 분류될 것이다. 3개의 각각의 리스트들은 이 실시예에서 유지된다: 부분 블록들 중 하나, 무용 블록 들에 대한 다른 하나 및 소거 블록들에 대한 제 3 블록.

이 실시예에서 구성된 블록들의 타입은 다음과 같다:

"프로그램 블록"은 부분적으로 프로그램되고, 단지 하나의 파일의 유효 데이터를 포함한다. 몇몇 소거 용량은 블록에 남는다. 몇몇 무용 데이터를 또한 포함할 수 있다.

"공통 블록"은 부분적으로 프로그램되고, 둘 또는 그 이상의 파일들의 유효 데이터를 포함하고, 몇몇 소거 용량은 남는다. 또한 몇몇 무용 데이터를 포함할 수 있다.

"충만한 공통 블록"은 완전히 프로그램되고 둘 또는 그 이상의 파일들의 유효 데이터를 포함한다. 또한 몇몇 무용 데이터를 포함할 수 있다.

"파일 블록"은 완전히 프로그램되고, 단일 파일의 유효 데이터를 포함한다. 또한 몇몇 무용 데이터를 포함할 수 있다.

"무효 블록"은 유효 데이터를 포함하지 않는다. 무효 블록은 적어도 몇몇 무용 데이터를 포함하고 소거 용량을 포함하지만 임의의 유효 데이터를 포함하지 않는다.

블록의 총 용량이 프로그램되지 않고 데이터를 수용하기 위하여 이용 가능한 "소거 블록". 소거 블록에 데이터가 없다. 메모리가 충만하거나 거의 데이터로 충만한 때, 소거 블록들의 지정된 최소 수의 풀(pool)은 통상적으로 사용되는 블록들내에 존재하는 사용되지 않은 용량을 연속적으로 재생함으로써 유지된다.

본 실시예에 대해, 상기 타입을 가진 블록들은 다음과 같이 3 가지의 등급으 로 분류된다:

"부분 블록"은 몇몇 프로그램되지 않은 용량, 하나 또는 그 이상의 파일들의 유효 데이터를 포함하고 몇몇 무용 데이터를 포함할 수 있다. 프로그램 블록 및 공통 블록은 부분 블록들의 예들이다.

"무용 블록"은 몇몇 무용 데이터를 포함하는 파일 블록이거나 충만한 공통 블록이다. 무용 블록은 임의의 소거된 용량을 포함하지 않고, 유효 및 무용 데이터 모두를 포함한다.

"소거 블록"은 데이터를 가지지 않은 블록인 동일한 이름의 블록 타입과 동일한 정의를 가진다.

이들 분류들이 메모리 어레이의 모든 블록들을 커버하지 않는 것이 주의되고, 몇몇 블록들은 이들 분류들 외에 남아있을 수 있고 상기 블록들은 본 실시예의 리스트들에 나타나지 않는다.

저장 용량을 재생하기 위한 블록을 선택할 때, 블록들(유효 데이터 용량)의 유효 데이터 양은 일차적인 요인이다. 블록상 재생 작동이 다른 블록에 유효 데이터를 카피하는 것을 요구하기 때문에, 최소 양의 유효 데이터를 가진 블록들은 우선 선택된다. 이것은 데이터 카피가 시간 소비적이고 데이터를 프로그램 및 판독하기 위하여 메모리 시스템의 유효 작동과 인터페이스할 수 있기 때문이다. 이렇게 어느 정도 카운터링하는 것은 데이터를 저장하기 위하여 소거되고 이용할 수 있는 용량의 상당 부분을 보유하는 블록들에 대해 바람직하다. 그러므로, 보다 많이 이용되는 소거 저장 용량을 가진 블록들은 재생에 의해 발생하는 저장 공간의 증가 가 더 적기 때문에 재생 작동을 위하여 바람직하지 않다. 이런 특정 실시예의 부분 및 무용 블록 리스트들은 그들이 포함하는 유효 데이터 양(페이지들의 수) 및 소거되어 남아있는 양(페이지들의 수)을 기초로 블록들을 분류하기 위하여 사용된다. 이들 리스트들이 여기에 기술된 목적은 재생 작동에 영향을 받을 하나의 블록을 한번에 선택하는 것이다.

블록 리스트들의 타입들 및 액세스

부분 블록 리스트(P-리스트)는 시스템의 모든 부분 블록에 대한 엔트리를 포함한다; 즉, 몇몇 유효 데이터 및 몇몇 소거 용량 모두를 포함하는 모든 블록. 또한 몇몇 무용 데이터를 포함할 수 있다.

무용 블록 리스트(O-리스트)는 부분 블록 리스트에 엔트리를 가지지 않는 무용 데이터를 포함하는 시스템에 매 블록에 대한 엔트리를 포함한다.

소거 블록 리스트(E-리스트)는 시스템의 모든 소거 블록에 대한 엔트리를 포함한다.

플래시 메모리 작동의 특정 실시예에서, 다음 블록 리스트들은 유지된다:

P(V)-리스트 : 블록들에 저장된 유효 데이터 용량에 따라 순서가 정해진 엔트리들을 가진 부분 블록 리스트;

P(A)-리스트 : 블록들의 블록 어드레스에 따라 순서가 정해진 엔트리들을 가진 부분 블록 리스트;

O(V)-리스트 : 블록들에 저장된 유효 데이터 용량에 따라 순서가 정해진 엔트리들을 가진 무용 블록 리스트;

O(A)-리스트 : 블록들의 블록 어드레스에 따라 순서가 정해진 엔트리들을 가진 무용 블록 리스트; 및

E-리스트 : 소거 블록 리스트.

P(V)-리스트, 0(V)-리스트, P(A)-리스트 및 0(A)-리스트는 블록 기록들의 공통 세트에 대한 "디렉토리들"로서 작동한다. 재생 블록을 선택하기 위하여, 가장 낮은 유효 데이터 용량 값들을 가진 엔트리들은 P(V)-리스트 및 O(V)-리스트로부터 판독된다. 액티브 블록을 선택하기 위하여, 타겟 값보다 작거나 같은 가장 높은 유효 데이터 용량 값을 가진 엔트리는 P(V)-리스트로부터 판독된다. 소거 블록을 선택하기 위하여, E-리스트상 제 1 엔트리는 리스트로부터 판독 및 제거된다.

P-리스트 또는 0-리스트의 엔트리를 업데이트하기 위하여, 타켓 블록 어드레스를 가진 엔트리는 P(A)-리스트 또는 O(A)-리스트로부터 판독된다.

블록 리스트들에 대한 저장 기술

하나 또는 그 이상의 블록들 또는 메타블록들은 바로 이전 섹션에서 식별된 블록 리스트들상 블록들에 관련된 정보의 저장을 위하여 할당된다. 이들은 기록 블록들로서 공지되었고, 하나의 페이지의 유니트들에 기입되거나 업데이트된다. 콘텐트 어드레싱은 기록 블록들의 정보에 사용된다.

각각의 기록 블록은 고정된 수의 논리 페이지들을 포함하고, 상기 페이지들 각각은 다음 이용 가능한 물리적 페이지에 재기재함으로써 업데이트될 수 있다. 다수의 논리 페이지들은 리스트들의 블록들을 위한 정보를 포함하는 기록들을 저장하기 위하여 할당된다. 이들은 기록 페이지들로서 공지되어 있다.

하나의 기록은 블록 리스트들 내 모든 블록에 존재한다. 기록 페이지들 및 상기 기록 페이지들 내 기록들은 임의의 순서일 수 있다. 다른 블록 리스트들 내 블록들을 위한 기록들은 독립적으로 유지될 필요가 없다. 무용 기록들은 기록 페이지들내에 존재하고, 블록 리스트들에 부가된 블록들에 대한 새로운 기록들에 의해 대체될 수 있다. 기록은 다른 정보와 함께 블록의 물리적 어드레스 및 블록 내 유효 데이터 양(유효 데이터 용량)을 정의하는 값을 포함한다.

하나 또는 그 이상의 논리적 페이지들은 개별 블록 리스들 중 하나 내의 블록들을 식별하는 엔트리들을 저장하기 위하여 할당된다. 이들은 리스트 페이지들로서 공지된다. 독립된 리스트 페이지들은 다른 블록 리스트들을 위하여 사용된다. 리스트 페이지의 각각의 엔트리는 기록 페이지 내 블록을 위한 기록에 대한 포인터와 함께 관계된 블록의 물리적 어드레스 또는 블록 내 유효 데이터 용량(또는 블록 내 데이터와 연관된 몇몇 다른 값)의 값인 디스크립터 값을 포함한다. 다른 블록 리스트에 대한 다른 리스트 페이지의 각각에서 두 개의 리스트 엔트리들은 기록이 관계된 블록이 두 개의 블록 리스트들에 나타나면 동일한 기록을 나타낼 수 있다.

블록 리스트들 내 엔트리들은 블록들에 대한 기록들의 공통 세트에 "디렉토리 엔트리들"로서 작동한다.

부분 블록 리스트 또는 무용 블록 리스트에 대한 리스트 페이지의 엔트리들은 디스크립터들의 순서로 저장된다. 엔트리들은 밀접하게 패키지된 포맷으로 기입되고, 리스트 페이지에서 기입되지 않은 엔트리 위치들은 최종 엔트리가 기입된 후 정상적으로 존재한다. 리스트 페이지들은 디스크립터들의 비오버랩핑 범위들을 저장한다. 만약 리스트 페이지가 풀이면, 엔트리들은 리스트 페이지로서 새로운 논리 페이지를 할당함으로써 두 개의 리스트 페이지들로 분할될 수 있다. 유사하게, 만약 인접한 디스크립터 범위들을 가진 두 개의 리스트 페이지들의 엔트리들의 수가 임계치 미만이면, 두 개의 리스트 페이지들은 하나로 결합될 수 있다. 기록 블록에 대한 하나의 인덱스는 각각의 리스트 페이지의 제 1 엔트리에 대한 디스크립터들을 포함한다.

블록 어드레스에 대한 타켓 값 또는 유효 데이터 용량을 가진 부분 블록 리스트 또는 무용 블록 리스트의 엔트리는 기록 블록 인덱스로부터 적당한 디스크립터 범위를 가진 리스트 페이지를 식별하고, 플래시로부터 상기 페이지를 판독하고, 타켓 엔트리에 대한 페이지내 선형 또는 이진 검색을 수행함으로써 발견될 수 있다. 그 다음 타켓 블록에 대한 기록은 이런 엔트리에 의해 식별된 기록 페이지로부터 판독될 수 있다.

소거 블록 리스트에서 블록들에 대한 엔트리들은 그들이 기입되는 순서를 유지하는 리스트 페이지 내에 저장될 수 있다. 소거 블록들은 항상 리스트에서 가장 오래된 엔트리로서 선택된다.

기록 블록의 구조

블록 리스트들에서 참조된 블록들에 대한 모든 엔트리들 및 인덱싱 정보는 플래시 메모리의 하나 또는 그 이상의 기록 블록들에 포함된다. 기록 블록은 메타블록이고 페이지의 유니트에서 업데이트된다.

기록 블록은 다음 특징들을 가진다:

1. 모든 타입의 블록 리스트들은 단일 기록 블록에서 함께 저장될 수 있다.

2. 만약 요구되면 다중 기록 블록들은 사용될 수 있다.

3. 기록 블록은 본 실시예에서 블록의 물리적 페이지들의 수의 25%로서 정의된 논리 페이지들의 지정된 수를 가진다.

4. 가장 최근에 기입된 페이지에서 기록 블록 인덱스 섹션은 물리적 페이지에 각각의 논리적 페이지에 대한 맵핑을 제공한다.

5. 논리 페이지는 다음 이용 가능한 물리적 페이지에 재기입에 의해 업데이트될 수 있다.

6. 논리 페이지는 블록 리스트들 또는 블록들의 기록들에 사용된 임의의 페이지 타입들에 할당될 수 있다.

7. 기록 블록은 압축되고 충만할 때 소거 블록에 재기입된다.

예시적인 기록 블록의 구조는 도 2에 도시된다.

기록 블록 인덱스

기록 블록 인덱스는 기록 블록의 각각의 페이지의 섹션으로서 존재한다. 이것은 가장 최근에 기입된 페이지에서만 유효하다. 기록 블록 인덱스는 논리 페이지 번호에 따라 순서가 매겨진 각각의 가능한 논리 페이지에 대한 엔트리를 포함한다. 각각의 엔트리는 3 필드들을 가지며, 상기 3 필드들은 하기와 같다:

1. 페이지 타입을 식별하는 수치 코드:

a. P(V)-리스트 페이지;

b. P(A)-리스트 페이지;

c. 0(V)-리스트 페이지;

d. 0(A)-리스트 페이지;

e. E-리스트 페이지;

f. 기록 페이지; 및

g. 할당되지 않은 논리 페이지.

2. 페이지내 제 1 엔트리 값. 이것은 형성되고 캐쉬될 각각의 P(V), P(A), 0(V) 및 O(A) 리스트 페이지 유형의 값들의 범위를 허용한다.

3. 논리 페이지가 맵핑되는 물리적 페이지에 대한 포인터.

기록 페이지

기록은 리스트들의 엔트리 리스트를 가진 하나의 블록에 관련된 모든 요구된 정보를 포함하고, 기록 페이지에 저장된다. 기록 페이지는 다음과 같이 3개의 섹션들로 분할된다:

1. 엔트리 상태;

2. 기록들; 및

3. 공통 블록 기록들.

엔트리 상태 섹션은 각각의 기록이 사용중인지, 또는 새로운 블록에 할당을 위하여 이용 가능한지 여부를 가리키는 비트맵을 포함한다. 기록 섹션은 리스트들의 모든 블록에 대해 고정된 크기의 엔트리를 가지며, 필드들은 다음과 같은 속성들을 정의한다:

1. 블록 어드레스;

2. 블록 내 유효 데이터의 용량;

3. 블록 내 페이지 기입 포인터의 위치;

4. 블록 내 제 1 데이터 그룹에 대한 필드ID;

5. 데이터가 블록 내에 존재하는 파일들의 총 수; 및

6. 블록을 위해 존재하는 임의의 공통 블록 기록에 대한 오프셋. 0의 값은 공통 블록 기록이 없다는 것을 나타낸다.

공통 블록 기록 섹션은 가변 크기들을 가진 엔트리들을 가지며, 필드들은 다음과 같이 공통 블록의 다른 파일ID를 정의한다:

1. 공통 블록 내 각각의 추후 데이터 그룹을 위한 파일ID; 및

2. 기록 표시기의 단부.

기록 페이지는 블록들이 블록 리스트들로부터 제거되게 하는 무용 엔트리들을 포함할 수 있다. 상기 기록은 리스트들에 부가된 새로운 블록들에 재할당될 수 있다.

기록 블록 내 논리 페이지 수 및 하나의 블록에 할당된 페이지 내 기록 수는, 그들이 기록을 참조하기 위하여 리스트 페이지들에 의해 사용될 때 일반적으로 변화하지 않는다. 그러나, 블록에 대한 기록을 동일한 리스트 페이지 내 다른 기록 번호로, 다른 리스트 페이지로, 또는 다른 기록 블록으로 이동시키는 것은 가능하다. 만약 블록에 대한 기록이 이동되면, 임의의 리스트 엔트리들에서 포인터들은 이에 따라 업데이트 되어야 한다.

기록 페이지가 변경되고 재기입될 때, 공통 블록 기록들은 공통 블록 기록들에 대한 오프셋의 임의의 변화들을 반영하기 위하여 업데이트된 임의의 무용 공간 및 기록들을 제거하기 위하여 압축될 수 있다.

기록들 및 공통 블록 기록들 사이의 경계는 동적이다.

예시적인 블록 기록 페이지의 구조는 도 3에 도시된다.

리스트 페이지

리스트 페이지는 디스크립터 값들에 의해 정의된 순서로 블록들에 대한 엔트리들의 세트를 포함한다. 유효 데이터 용량은 P(V)-리스트 및 O(V)-리스트의 엔트리들내 디스크립터이고, 블록 어드레스는 P(A)-리스트 및 O(A)-리스트 내 엔트리들의 디스크럽터이다.

유효 엔트리들은 리스트 페이지 내 엔트리 위치들의 인접한 세트를 차지하지만, 완전한 페이지를 충전할 필요가 없다. 상기 세트 내에는 무용 엔트리들이 없고, 디스크립터 값들은 인접할 필요가 없다.

리스트 페이지 내 엔트리들은 디스크립터 필드내 값들의 순서이다. 디스크립터 값들의 범위는 임의의 다른 리스트 페이지 내 디스크립터 값들의 범위와 오버랩핑하지 않는다.

블록 리스트에 부가되었던 블록에 대한 엔트리가 삽입될 필요가 있을 때, 새로운 블록에 대한 디스크립터 값을 포함하는 디스크립터 범위를 가진 리스트 페이지는 식별된다. 새로운 엔트리는 디스크립터 범위의 적당한 위치에 삽입되고, 리스트 페이지는 재기입된다. 엔트리가 제거되어야 할 때, 리스트 페이지는 엔트리 없이 압축되고 재기입된다.

충만하게 된 리스트 페이지에 대한 부가가 이루어져야 할 때, 빈(free) 논리 페이지는 새로운 리스트 페이지로서 할당되고 충만한 리스트 페이지의 디스크립터 범위는 두 개의 이용 가능한 리스트 페이지들에 기입된 두 개의 대략 동일한 비오버랩핑 범위들로 분할된다.

인접한 디스크립터 범위들을 가진 두 개의 리스트 페이지들 내 유효 엔트리들의 총 수가 임계 값(이 예에서 리스트 페이지의 엔트리 위치들 수의 70%) 미만으로 떨어질 때, 두 개의 리스트 페이지들의 범위들은 결합되고 두 개의 리스트 페이지들 중 하나에 기입된다. 그 다음 다른 사용되지 않은 페이지는 빈 논리 페이지가 된다.

P(V)-리스트 및 O(V)-리스트에 대한 리스트 페이지의 엔트리 필드들은 다음과 같다:

1. 블록 내 유효 데이터 용량; 및

2. 기록 페이지 내 블록 기록에 대한 포인터. 기록 페이지는 리스트 페이지와 동일한 기록 블록들 내에 있을 필요가 없다.

P(A)-리스트 및 O(A)-리스트에 대한 리스트 페이지 엔트리 필드들은 다음과 같다.

1. 블록 어드레스; 및

2. 기록 페이지 블록 기록에 대한 포인터. 기록 페이지는 리스트 페이지와 동일한 기록 블록 내에 있을 필요가 없다.

E-리스트에 대한 리스트 페이지 엔트리의 필드는 다음과 같다:

1. 블록 어드레스.

기록들에 대한 액세스 시퀀스

다음 단계들의 시퀀스는 P-리스트 또는 O-리스트의 타켓 블록에 대한 기록을 액세스하기 위하여 사용된다.

1. 타켓 리스트로서 P(V)-리스트, O(V)-리스트, P(A)-리스트 또는 O(A)-리스트 정의.

2. 기록 블록 내에 가장 최근에 기입된 페이지로부터 기록 블록 인덱스 판독. 이 정보는 캐쉬에 이미 존재할 수 있다.

3. 단계 1에서 정의된 타켓 리스트의 타켓 디스크립터 값에 대한 리스트 페이지에 할당된 논리 페이지 수 결정.

4. 기록 블록으로부터 단계 3에서 결정된 논리 페이지 수 판독.

5. 타켓 블록에 대한 엔트리를 판독하기 위하여 단계 4에서 판독된 리스트 페이지 검색.

6. 단계 5에서 판독된 엔트리에 의해 정의된 바와 같은 기록 블록으로부터 기록 페이지 판독.

7. 단계 6에서 판독된 기록 페이지로부터 타켓 블록에 대한 기록 판독.

제 2 실시예

제 2 실시예에서, 상기된 제 1 실시예에서와 같이, 특정 블록들은 그들이 포함하는 데이터에 따라 개별적으로 분류되고 기록들은 이들 블록들에 유지된다. 리 스트들은 블록 내에 저장된 데이터에 관련된 디스크립터 값에 따라 순서가 정해져 유지된다. 블록 내 유효 데이터의 양은 이러한 디스크립터 값의 예이다. 그러나, 블록들을 관리하기 위하여 사용된 몇몇 구조들 및 방법들은 제 2 실시예에서 다르다. 제 1 및 제 2 실시예들의 구조들 및 방법들은 대안으로서 판단되고, 양쪽 실시예들로부터 구조들 및/또는 기술들의 다양한 결합들은 본 개시물의 일부로서 고려된다. 제 2 실시예는 제 1 실시예와 차이점에 중점을 두고 기술된다. 따라서, 양쪽 실시예들에서 공통인 엘리먼트들은 제 2 실시예와 관련하여 다시 상세히 기술되지 않는다.

제 2 실시예에서 블록 분류는 "완전한 공통 블록" 분류의 부가를 가지며 제 1 실시예와 동일하다. 도 4는 부가적인 분류 "완전한 공통 블록"을 제외하고 도 1과 유사한 블록 분류 테이블을 도시한다. 기록 엔트리들은 각각의 블록이 블록 분류 "부분 블록", "무용 블록", "소거 블록" 또는 "완전한 공통 블록"을 가지도록 유지된다. 분류, "완전한 공통 블록"은 임의의 소거된 용량을 포함하지 않고 임의의 무용 데이터를 포함하지 않은 공통 블록들에 사용된다. 완전한 공통 블록(CCB) 기록들은 모든 완전한 공통 블록에 대한 블록 기록과 함께 유지된다. 완전한 공통 블록들은 그들이 재생에 이용 가능한 공간(소거 공간이나 무용 공간이 아님)을 포함하지 않기 때문에 작동들을 재생하기 위하여 일반적으로 사용되지 않는다. 그러나, 완전한 공통 블록 내 몇몇 데이터가 사용되지 않을 때(obsolete), 블록은 무용 블록으로서 재분류되고 재생 작동을 겪을 수 있다. 상기 재분류가 발생할 때, 블록 내에 저장된 데이터에 관련한 정보를 포함하는 블록 기록은 요구된다. 이 정보 는 블록에 사전 존재하는 CCB 기록 엔트리로부터 이용 가능하다. 따라서, 완전한 공통 블록들 상에 기록들을 유지함으로써, 완전한 공통 블록으로부터 무용 블록으로 전이는 블록에 대한 기록을 생성하기 위한 정보를 검색하는 무거운 부담없이 발생할 수 있다.

도 1 및 4의 분류 방법들은 예시적이고 다른 방법들은 또한 고려된다. 일실시예(이후에 논의됨)에서, 기록은 한번에 메모리 어레이 내 모든 블록들에 유지된다. 따라서, 부가적인 블록 분류는 무용 데이터를 가지지 않는 파일 블록들을 위하여 도 4의 테이블에 부가될 수 있다. 다른 실시예들에서, 도 4의 몇몇 분류 방법들은 필요하지 않을 수 있다. 예를 들어, 기록들은 소거 블록들 또는 무효 블록들에 유지되지 않을 수 있다. 다른 실시예들에서, 블록들은 도 4와 다른 블록 타입들로 분할될 수 있다. 도 4의 블록 타입들이 특정 메모리 관리 방법들에 편리하지만, 다른 메모리 관리 방법들은 다른 블록 타입들을 사용할 수 있다는 것이 이해될 것이다.

기록은 도 4의 테이블에 리스트된 블록 분류 중 하나로 모든 블록에 유지된다. 다른 블록 분류들을 가진 블록들에 대한 기록들은 동일한 페이지에 함께 저장된다. 본 실시예에서, 전용 블록 기록 블록들은 블록 기록들만을 저장하여 유지된다. 기록 블록들의 개별 기록 엔트리들에 대한 액세스를 용이하게 하기 위하여, 블록 디렉토리는 유지된다. 블록 디렉토리 및 블록 기록들은 플래시 메모리 블록들의 개별 세트들에 저장된다(단일 블록이 블록 디렉토리 및 블록 기록 페이지 모두를 포함할 수 있는 제 1 실시예와 다름). 도 5는 블록 기록 블록(509)에서 대응 블록 기록(507)의 위치에 대한 포인터(505)를 포함하는 디렉토리 블록(503)의 블록 디렉토리 엔트리(501)를 도시한다. 블록 디렉토리 엔트리(501)는 또한 블록 어드레스(506)를 포함한다.

블록 디렉토리는 엔트리가 블록 기록들 내에 존재하는 각각의 블록에 대해 하나의 블록 디렉토리를 포함한다. 블록 디렉토리 엔트리들은 블록 어드레스 값들의 비오버랩핑 범위들에 저장되고, 각각의 범위는 개별 블록 디렉토리 페이지에 할당된다. 하나의 범위 내의 엔트리들은 블록 어드레스 값에 따라 순서가 정해진다. 타켓 블록 어드레스에 대한 블록 디렉토리 엔트리는 단일 블록 디렉토리 페이지를 판독하고 페이지 내에서 이진 검색을 수행함으로써 발견될 수 있다. 따라서, 블록 디렉토리는 블록 어드레스에 따라 특정 블록 기록 엔트리를 배치하기 위한 편리한 방식을 제공한다.

몇몇 애플리케이션들에서, 블록 어드레스와 다른 기준으로 블록을 검색하는 것이 바람직하다. 몇몇 경우들에서, 블록들에 저장된 데이터와 연관된 디스크립터 값들은 상기 검색에 사용될 수 있다. 예를 들어, 재생을 위하여, 최소량의 유효 데이터를 가진 부분 블록을 식별하는 것은 바람직할 수 있다. 상기 하나의 블록을 발견하기 위한 하나의 방식은 블록이 최소량의 유효 데이터를 포함한 것을 결정하기 위하여 모든 블록들에 대한 기록 엔트리들을 검색하는 것이다. 그러나, 상기 검색은 상당한 부담을 부가한다. 대안은 그들이 포함하는 유효 데이터 양(유효 데이터 용량)에 따라 순서가 정해진 블록들의 리스트들을 유지하는 것이다. 따라서, 블록들이 포함한 유효 데이터 양의 순서로 리스트되는 경우, 최소량의 유효 데이터 를 가진 블록을 식별하는 것은 리스트에서 제 1(또는 최종) 엔트리를 판독하는 간단한 문제이다. 유사하게, 만약 유효 데이터의 특정 양을 가진 블록이 요구되면, 이진 검색은 상기 블록을 빠르게 식별할 수 있다. 블록 내에 저장된 유효 데이터 양은 리스트 엔트리의 디스크립터 값에 의해 제공된다. 상기 디스크립터 값은 블록 내에 저장된 데이터를 기술한다. 이것은 블록의 물리적 위치를 기술하는 블록 어드레스(제 1 실시예에서 디스크립터 값으로서 사용됨)와 대조된다.

두 단계 검색 처리를 통합한 메카니즘은 블록에서 유효 데이터 양의 기록 필드 내에 정의된 디스크립터 값에 따라 블록 기록을 액세스하기 위하여 제공된다. 이런 콘텐트 어드레싱 메카니즘이 사용될 수 있는 블록 분류를 위한 유효 데이터 용량 값들을 포함하는 엔트리들은 블록 디렉토리 내 개별 리스트 페이지들에 저장된다. 이들 블록 리스트 엔트리들은 유효 데이터 용량 값들의 비오버랩핑 범위들에 저장되고, 각각의 범위는 개별 블록 리스트 페이지에 할당된다. 하나의 범위 내의 엔트리들은 유효 데이터 용량 값들에 따라 순서가 정해진다. 각각의 블록 리스트 엔트리는 블록 디렉토리 엔트리를 명확하게 식별하는 블록 어드레스를 포함한다. 블록 리스트 엔트리(511)는 블록 어드레스(506)와 동일한 블록 어드레스(513)를 포함하여 블록 디렉토리 엔트리(501)를 식별한다. 블록 리스트 엔트리(511)는 블록 어드레스(513)를 가진 블록에 대한 유효 데이터 용량(515)을 포함한다. 타켓 유효 데이터 용량 값에 대한 블록 디렉토리 엔트리는 단일 리스트 페이지를 판독하고 타켓 유효 데이터 용량 값을 가진 엔트리를 발견하기 위하여 페이지 내 이진 검색을 수행하고, 그 다음 단일 디렉토리 페이지를 판독하고 타켓 블록 어드레스를 가진 엔트리를 발견하기 위하여 디렉토리 페이지 내 이진 검색을 수행함으로써 발견될 수 있다.

이진 검색은 페이지의 디스크립터 값 범위 중간 엔트리에서 검색하는 것을 의미한다. 조사되는 디스크립터 값과 엔트리의 디스크립터 값의 비교를 바탕으로, 검색은 페이지의 반쪽으로 제한된다. 이런 반쪽 페이지의 중간에서의 엔트리는 유사하게 검사되고 상기 검색은 페이지의 1/4로 제한된다. 연속적인 단계들 후, 하나 또는 그 이상의 엔트리들은 조사되는 디스크립터 값을 가진 것이 발견된다. 다른 실시예들에서, 보다 정교한 이진 검색 알고리듬들은 사용될 수 있다. 몇몇 실시예들에서, 이진 검색은 필요하지 않은데, 그 이유는 조사된 디스크립터 값은 리스트에서 최하위(또는 최상위)이기 때문이다. 따라서, 리스트의 제 1(또는 최종) 엔트리)는 선택된다.

블록 기록들은 블록 디렉토리 내 엔트리들에 의해 직접적으로 어드레스된다. 블록 기록들의 페이지는 동일하거나 다른 블록 기록 블록의 프로그램되지 않은 위치로 페이지를 이동시키는 판독/변경/기입 작동에 의해 업데이트된다. 페이지의 블록 기록들은 동일한 블록 디렉토리 페이지의 엔트리들에 모두 관련되어야 한다. 그러나, 하나의 디렉토리 페이지는 하나 이상의 블록 기록 페이지에 대한 엔트리들을 포함할 수 있다. 따라서, 블록 기록 페이지는 단일 블록 디렉토리 페이지만의 변경을 위한 결과적인 필요성으로 업데이트될 수 있다.

블록 디렉토리

블록 디렉토리는 블록 단위 어드레스를 식별하고 대응 블록 기록들의 위치들 을 가리키는 엔트리들의 순서가 정해진 수집부이다. 엔트리는 블록 기록이 유지된 각각의 블록에 대한 블록 디렉토리 내에 존재한다. 본 실시예에서, 엔트리는 각각의 부분 블록, 무용 블록, 완전한 공통 블록, 및 소거 블록에 존재한다. 블록 디렉토리는 하나 또는 그 이상의 디렉토리 블록들에 포함된다.

도 6은 무용 블록 및 부분 블록 리스트 페이지들을 포함하는 디렉토리 블록(621)을 도시한다. 도 6은 디렉토리 블록의 디렉토리 페이지들을 또한 도시한다. 각각의 디렉토리 블록은 고정된 수의 논리 페이지들을 포함하고, 상기 논리 페이지들 각각은 다음에 이용 가능한 물리 페이지에 재기입에 의해 업데이트될 수 있다. 유효 엔트리들을 포함하는 페이지는 논리 페이지 번호가 할당된다. 디렉토리내 논리 페이지들의 수는 본 실시예에서 블록의 물리적 페이지들의 수의 25%인 것으로 지정된다. 다른 실시예에서, 다른 제한들은 지정될 수 있다. 디렉토리 블록의 최종 페이지가 기입된 후, 블록은 소거 블록에 모든 유효 페이지들을 기입하고 본래 디렉토리 블록을 소거함으로써 압축된다.

블록 디렉토리 페이지

블록 디렉토리 페이지는 블록 어드레스 값들의 순서로 한 세트의 블록 디렉토리 엔트리들을 포함한다. 블록 디렉토리 페이지(731)의 예는 도 7A에 도시된다. 유효 블록 디렉토리 엔트리들(733)은 블록 디렉토리 페이지(731)의 엔트리 위치들의 인접 세트를 차지하지만, 소거 공간이 남아있을 수 있도록 완전한 페이지를 충전할 필요가 없다. 각각의 블록 디렉토리 페이지는 기록 인덱스(하기에 기술됨)를 포함한다. 여기서, 블록 디렉토리 페이지(731)는 기록 인덱스(735)를 포함한다. 블록 디렉토리 엔트리들(733) 내에는 무용 엔트리들이 없고, 블록 어드레스 값들은 인접할 필요가 없다. 블록 디렉토리 페이지 내 블록 어드레스 값들의 범위는 임의의 다른 블록 디렉토리 페이지 내 블록 어드레스 값들의 범위를 오버랩하지 않는다.

블록에 대한 엔트리가 삽입될 필요가 있을 때, 새로운 블록에 대한 블록 어드레스 값을 포함하는 블록 어드레스 범위를 가진 블록 디렉토리 페이지는 디렉토리 인덱스의 정보로부터 식별된다. 새로운 엔트리는 블록 어드레스 범위의 적당한 위치에 삽입되고, 블록 디렉토리 페이지는 재기입된다. 엔트리가 제거되어야 할 때, 블록 디렉토리 페이지는 엔트리 없이 압축되고 재기입된다.

충만하게 된 블록 디렉토리 페이지에 대한 부가가 이루어져야 할 때, 빈(free) 논리 페이지는 새로운 블록 디렉토리 페이지로서 할당되고 충만된 블록 디렉토리 페이지의 블록 어드레스 범위는 두 개의 이용 가능한 블록 디렉토리 페이지들에 기입된 두 개의 대체로 동일한 비오버랩핑 범위들로 나뉘어진다.

인접한 블록 어드레스 범위들을 가진 두 개의 블록 디렉토리 페이지들에서 유효 엔트리들의 총 수가 임계 값(이 실시예에서 하나의 블록 디렉토리 페이지 엔트리 위치들 수의 70%) 아래로 떨어질 때, 두 개의 블록 디렉토리 페이지들의 범위들은 결합되고 두 개의 블록 디렉토리 페이지들 중 하나에 기입된다. 그 다음 다른 사용되지 않은 페이지는 빈 논리 페이지가 된다.

이 실시예에서 블록 디렉토리 엔트리(737)는 두 개의 필드들을 포함한다: (1) 블록 어드레스; (2) 대응 블록 기록에 대한 포인터. 포인터는 블록 기록 페이 지에 대한 논리 식별자 및 페이지 내 특정 블록 기록의 바이트 오프셋을 식별한다. 블록 기록 페이지 논리 식별자는 동일한 블록 디렉토리 페이지 내 엔트리들에 의해 참조될 수 있는 16 개별 블록 기록 페이지들 중 하나를 식별한다. 이것은 엔트리를 포함하는 블록 디렉토리 페이지 내 기록 인덱스 필드에 의해 물리적 블록 어드레스 및 페이지 번호로 변환된다(converted). 바이트 오프셋은 식별된 블록 기록 페이지 내 블록 기록 위치를 식별한다.

개별 유효 기록 인덱스 필드는 각각의 유효 블록 디렉토리 페이지 및 블록 리스트 페이지에 존재한다. 이것은 블록 기록 페이지들에 대한 논리 식별자들을 물리적 블록 어드레스들 및 블록 기록 페이지들이 배치된 페이지 번호들로 변환하기 위하여 사용된다. 기록 인덱스(735)는 블록 디렉토리 페이지(731)의 임의의 엔트리 내에서 사용된 각각의 논리 식별자에 대해 하나의 엔트리(엔트리 739 같은)를 포함한다. 최대 16의 개별 블록 기록 페이지들은 단일 블록 디렉토리 페이지의 블록 디렉토리 엔트리들에 의해 참조될 수 있다. 그러므로, 4 비트 논리 식별자는 사용된다. 이런 방식에서, 개별 블록 디렉토리 엔트리들은 대응 블록 기록 페이지에 대해 보다 긴 물리적 페이지 위치 대신 4 비트 식별자를 사용할 수 있다. 기록 인덱스 필드는 블록 디렉토리 페이지의 모든 엔트리들에 대한 이들 논리 식별자들을 번역(translate)하기 위하여 사용한다.

유효 디렉토리 인덱스 필드(741)는 가장 최근에 기입된 블록 디렉토리 또는 블록 리스트 페이지에만 존재한다. 이전에 기입된 모든 페이지들의 디렉토리 인덱스 필드 내 정보는 사용되지 않는다(obsolete). 그 목적은 블록 디렉토리 엔트리 들 및 블록 리스트 엔트리들의 순서 매김 및 물리적 페이지들에 논리 페이지들의 맵핑을 지원하는 것이다. 이것은 현재 데이터가 블록 디렉토리 블록의 개별 페이지들에 관련하여 저장되는 구조를 제공한다. 디렉토리 인덱스는 각각의 가능한 논리 페이지에 대해, 논리 페이지 번호에 따라 순서가 매겨진 엔트리(예를 들어 엔트리(743))를 포함한다. 각각의 엔트리는 4개의 필드들을 가진다:

(1) 논리 페이지에 대한 상태 플래그 할당.

(2) 페이지 타입, 예를들어 블록 디렉토리, PB 리스트, 또는 OB 리스트.

(3) 블록 디렉토리 페이지의 제 1 엔트리의 블록 어드레스 또는 리스트 페이지(PB 또는 OB)의 제 1 엔트리의 유효 데이터 용량 값. 이것은 블록 어드레스 범위 또는 각각의 논리 페이지의 유효 데이터 값들이 설정되고 캐쉬되게 한다.

(4) 논리 페이지가 맵핑되는 블록 디렉토리 내 물리적 페이지에 대한 포인터.

블록 리스트 페이지

블록 리스트 페이지는 포함한 데이터를 기술하는 디스크립터 값의 순서로(예를들어, 포함하는 유효 데이터 양) 블록의 단일 분류를 위한 한 세트의 블록 리스트 엔트리들을 포함한다. 블록 리스트 페이지(751)의 예는 도 7B에 도시된다. 본 실시예에서, 블록 리스트 페이지는 PB 리스트 페이지 또는 OB 리스트 페이지일 수 있다. 도 7B는 OB 리스트 페이지(751)를 도시한다. 유효 블록 리스트 엔트리들(753)은 블록 리스트 페이지(751) 내 인접한 엔트리 위치들의 세트를 차지할 수 있지만, 전체 페이지를 충전할 필요가 없다. 블록 리스트 페이지 내에는 일반적으 로 무용 엔트리들이 없다. 블록 리스트 엔트리들(753)은 디스크립터 값에 의해 순서가 정해지지만 디스크립터 값들은 인접할 필요가 없고 반복될 수 있다. 본 실시예에서, 유효 데이터 용량 값들은 인접할 필요가 없고 반복될 수 있다. 블록 리스트 페이지의 디스크립터 값들의 범위는 동일한 블록 분류를 위하여 임의의 다른 블록 리스트 페이지의 디스크립터 값들의 범위와 오버랩하지 않는다.

유효 데이터 용량이 본 실시예에 사용된 디스크립터 값인 동안, 다른 디스크립터 값들은 또한 사용될 수 있다. 예를 들어, 블록 내 소거 용량의 양은 디스크립터 값으로서 사용될 수 있다. 디스크립터 값은 블록들이 재생을 위하여 목표된 순서로 리스트되도록 유효 데이터 양 및 소거 용량의 양의 결합으로부터 유도될 수 있다. 몇몇 경우들에서, 리스트들은 오버랩할 수 있다. 따라서, 동일한 블록은 두 개의 다른 리스트들에 나타날 수 있다. 예를 들어, 블록들은 포함한 유효 데이터의 양 및 (개별 리스트에서) 포함한 소거 공간의 양 모두에 의해 리스트될 수 있다.

블록에 대한 엔트리가 삽입될 필요가 있을 때, 새로운 블록에 대한 유효 데이터 용량 값을 포함하는 유효 데이터 용량 범위를 가진 블록 리스트 페이지는 디렉토리 인덱스의 정보로부터 식별된다. 블록 리스트 페이지는 유효 데이터 용량 값에 따라 페이지의 적당한 위치에 삽입된 새로운 엔트리로 재기입된다. 엔트리가 제거되어야 할 때, 블록 리스트 페이지는 엔트리 없이 새로운 물리적 위치에 재기입된다.

충만된 블록 리스트 페이지에 대한 부가가 이루어져야 할 때, 빈 논리 페이 지는 새로운 블록 리스트 페이지로서 할당되고 충만된 블록 리스트 페이지의 유효 데이터 범위는 두 개의 이용 가능한 블록 리스트 페이지들에 기입된 두 개의 대략 동일한 비오버랩핑 범위들로 분할된다.

인접한 범위들을 가진 두 개의 블록 리스트 페이지들에서 유효 엔트리들의 총 수가 미리 결정된 임계 양(예를 들어, 하나의 블록 리스트 페이지에서 엔트리 위치들의 수의 70%) 아래로 떨어질 때, 두 개의 블록 리스트 페이지들의 범위들은 결합되고 두 개의 블록 리스트 페이지들 중 하나에 기입된다. 그 다음 다른 사용되지 않은 페이지는 빈 논리 페이지가 된다.

블록 리스트 엔트리(755)는 두 개의 필드들을 포함한다: (1) 블록 어드레스; (2) 디스크립터 값, 이 실시예에서 블록 내 유효 데이터 양을 가리키는 값. 제 1 예와 달리, 블록 어드레스에 의해 순서가 매겨진 리스트는 없다(비록 디렉토리가 블록 어드레스에 의해 순서가 매겨지지만). 본 실시예에서, 리스트는 디렉토리 엔트리가 발견된 블록 어드레스를 포함하고, 그 다음 대응 기록의 위치를 가리킨다. 따라서, 리스트 엔트리(753)는 이 실시예에서 하나의 기록을 직접 가리키지 않는다. 블록 리스트는 디렉토리 인덱스를 포함할 수 있지만, 오직 가장 최근 기입된 페이지만이 유효 디렉토리 인덱스를 포함한다. 도 7B의 OB 리스트 페이지는 무용 디렉토리 인덱스(757)를 포함한다.

블록 기록들

블록 기록들은 기록들의 수집부이고, 상기 수집부 각각은 블록 어드레스에 의해 식별된 블록에 대한 정보를 포함한다. 하나의 기록은 각각의 블록 디렉토리 엔트리를 위하여 존재한다. 블록 기록들은 블록 디렉토리 엔트리들에 의해 어드레스되고, 블록 디렉토리 페이지는 블록 기록 페이지가 변경될 때 변경되어야 한다.

블록 기록들은 도 8에 도시된 기록 블록(861) 같은 하나 또는 그 이상의 전용 기록 블록들에 포함된다. 제 1 실시예와 달리, 블록 리스트들 및 블록 기록들은 동일한 블록에 함께 저장되지 않는다. 단지 하나의 블록 기록 블록은 블록 기록들이 기입되는 프로그램되지 않은 페이지들을 포함할 수 있다. 모든 블록 기록 정보는 블록 기록 기입 포인터에 의해 식별된 블록 내 다음 프로그램되지 않은 페이지 위치에서 프로그램된다. 블록 내 최종 페이지가 프로그램되었을 때, 블록 기록 기입 포인터는 소거 블록의 제 1 페이지로 이동된다. 블록 기록 블록들은 블록 기록 페이지들이 재기입되도록 하는 무용 페이지들을 포함할 수 있다. 몇몇 실시예들에서, 유효 블록 기록 페이지들은 페이지 내 기록이 사용되지 않을(obsolete) 때마다 블록 기록 페이지가 재기입 되기 때문에 무용 기록들을 포함하지 않는다. 다른 실시예들에서, 무용 기록들은 유효 블록 기록 페이지들에 남을 수 있다. 그러나, 무용 기록들에 대한 디렉토리 엔트리들은 무용 기록들이 액세스되지 않도록 삭제되거나 유효 기록들을 가리키는 엔트리들로 대체된다. 기록 페이지의 무용 기록들은 기록 페이지가 재기입될 때 카피되지 않는다.

블록 기록 페이지는 블록 디렉토리 페이지의 엔트리들과 동일한 순서로 단일 블록 디렉토리 페이지 내 블록 디렉토리 엔트리들에 의해 참조된 한 세트의 블록 기록들을 포함한다. 도 9는 블록 기록 페이지(965)의 예를 도시한다. 블록 디렉토리 페이지는 다중 블록 기록 페이지들을 참조할 수 있다. 블록 기록 페이지의 변경은 단지 단일 블록 디렉토리 페이지의 변경을 위한 당위적인 필요성으로 이루어질 수 있다. 제 1 실시예와 달리, 본 실시예에 따른 블록 기록 페이지는 블록 기록 페이지들이 블록 디렉토리 엔트리들에 의해 직접적으로 식별되기 때문에 블록 기록 인덱스를 포함하지 않는다.

블록 기록 페이지는 페이지를 판독하고, 그 다음 업데이트하거나 하나 또는 그 이상의 블록 기록들을 부가함으로써 변경될 수 있다. 임의의 무용 블록 기록들은 페이지를 압축함으로써 제거되고, 페이지는 블록 기록 기입 포인터에 의해 식별된 위치에서 프로그램된다.

블록 기록 페이지 헤더는 블록 기록 페이지가 연관된 블록 디렉토리 페이지, 및 블록 기록 페이지 내의 블록 기록 정보의 길이에 대한 참조를 저장한다. 블록 기록 페이지 헤더는 또한 블록 기록 페이지가 기입된 시간에 블록 기록 블록들 각각에 존재하는 무용 페이지들의 수의 기록을 저장한다. 이 정보는 가장 최근에 기입된 블록 기록 페이지 헤더에서만 유효하다.

개별 블록 기록 엔트리는 가변 크기를 가진다. 따라서, 완전한 공통 블록에 대한 기록은 소거 블록에 대한 기록보다 클 수 있다. 제 1 실시예와 달리, 개별 공통 블록 기록들 영역이 요구되지 않는다. 본 실시예의 기록 블록은 다음과 같이 블록의 속성을 정의하는 필드들을 가진다:

(1) 블록 어드레스.

(2) 블록 타입, PB, OB, CCB, 또는 EB.

(3) 블록 내 유효 데이터 용량.

(4) 블록 내 페이지 기입 포인터 위치.

(5) 데이터가 블록에 존재하는 필드들의 총 수.

(6) 데이터가 블록 내에 존재하는 각각의 파일에 대한 파일ID들.

다른 실시예들에서, 기록들은 다른 디스크립터 값들을 포함하는 다른 필드들을 포함할 수 있다.

제 2 실시예에서 블록 기록들에 대한 재생 처리

블록 기록들은 하나 또는 그 이상의 기록 블록들에 포함되고 블록 디렉토리 엔트리들에 의해 직접 어드레스된다. 단지 하나의 기록 블록은 새롭거나 업데이트된 블록 기록들을 프로그래밍하기 위하여 이용가능한 소거 페이지들을 포함한다. 모든 다른 기록 블록들에서, 모든 페이지들은 프로그램되었지만, 상기 블록은 완전히 사용되지 않거나 부분적으로 무용된 페이지들을 포함할 수 있다. 무용 블록 기록들에 의해 차지된 용량의 재생은 재생될 다음 블록으로서 하나의 기록 블록을 지정하고, 재생 블록을 소거하기 전에 재생 블록으로부터 블록 기록 기입 포인터에 의해 현재 지정된 페이지로 점진적인 카피에 의해 수행된다.

재생 블록은 기록 블록상 이전 재생 처리가 완료되고 이전 재생 블록이 소거될 때 선택된다. 무용 페이지들 중 가장 높은 수를 가진 기록 블록은 재생 블록으로서 선택된다. 각각의 기록 블록에 대한 무용 페이지들의 수는 가장 최근에 기입된 블록 기록 페이지의 블록 기록 페이지 헤더에 기록된다. 블록 기록 기입 포인터를 포함하는 기록 블록은 재생을 위하여 선택될 수 없다. 선택된 기록 블록은 재생 처리가 완료되고 블록이 소거될 때까지 재생 블록으로서 남아있는다. 그 다 음 소거 블록은 소거 블록 풀에 부가되고 호스트 데이터를 포함하는 임의의 종류의 데이터를 다시 저장하기 위하여 사용될 수 있다. 따라서, 블록은 임의의 시간 동안 전용 기록 블록에 남아있지만 기록 블록으로서 영구적으로 지정되지 않는다.

무용 페이지들을 포함하는 블록 기록 블록들을 재생하는 처리는 버스트들에서 스케쥴된 간격들로 상기 블록으로부터 블록 기록 기입 포인터에 의해 지정된 페이지로 유효 블록 기록들을 포함하는 작은 수의 페이지들을 카피하는 것을 수반한다. 버스트에서 페이지들의 수는 우수한 성능을 위한 메타페이지에 포함된 페이지들의 수이어야 한다. 그러나, 몇몇 경우들에서 보다 작은 수의 페이지들은 한번에 기입될 수 있다. 블록 기록 기입 포인터에서 페이지들을 프로그래밍하는 것은 메타페이지에서 단일 프로그래밍 작동으로서 수행될 수 있다. 재생 블록에서 페이지들의 버스트 카피 작동은 4 메타페이지들에 포함된 페이지 위치들의 수를 통하여 블록 기록 기입 포인터의 진행에 의해 정의된 간격들로 스케쥴될 수 있다. 메타페이지를 프로그램하기 위하여, 기입 포인터는 일반적으로 버스트 카피 작동이 스케쥴될 때 물리적 메타페이지의 제 1 페이지를 가리켜야 한다.

상기된 블록 기록 블록들에 대한 재생 처리와 대조하여, 디렉토리 블록들을 위한 재생 처리는 소거 공간이 디렉토리 블록에 남아있지 않을 때 블록 디렉토리 블록을 압축하는 간단한 문제이다. 블록 디렉토리 블록이 임의의 시간에 최대 25% 유효 페이지들을 가지면(논리 용량은 이 실시예에서 물리 용량의 25%이다), 상기 블록의 압축은 적어도 75% 소거 공간을 가진 블록을 발생시킨다. 압축이 발생할 때, 데이터가 카피된 블록은 무효 블록이 되고 소거 블록이 되도록 소거된다. 그 다음, 블록은 소거 블록 풀에 부가되고 호스트 데이터를 포함하는 임의의 종류의 데이터를 저장하기 위하여 사용될 수 있다. 따라서, 블록은 임의의 시간 동안 전용 디렉토리 블록에 남아있지만 디렉토리 블록으로서 영구적으로 지정되지 않는다.

제 2 실시예의 구조들 업데이트

데이터가 메모리 어레이의 블록에 기입될 때 또는 파일이 삭제될 때, 하나 또는 그 이상의 블록 기록들은 업데이트될 필요가 있을 수 있다. 게다가, 대응 블록 디렉토리 및 리스트 엔트리들은 업데이트될 필요가 있을 수 있다. 도 10에 도시된 바와 같은 다음 처리는 부가적인 유효 데이터가 부분 블록에 저장되어(이미 몇몇 무용 데이터를 포함함) 블록이 무용 블록이 될 때 제 2 실시예의 다양한 구조들을 업데이트하는 것을 도시한다.

(1) 부가적인 데이터를 저장하는 블록 어드레스 검색.

(2) 이 블록에 대해 디렉토리 엔트리(175)를 포함하는 디렉토리 페이지(173)의 물리적 페이지 위치를 결정하기 위하여 블록 디렉토리 블록(170)의 최종 기입 페이지의 디렉토리 인덱스(171)에서 검색.

(3) 블록에 대해 엔트리(175)를 찾기 위하여 디렉토리 페이지(173) 내에서 이진 검색 수행.

(4) 기록 인덱스(177)의 정보와 함께 엔트리(175)의 논리 식별자로부터 이런 블록에 대한 기록(183)을 포함하는 블록 기록 블록(181)의 물리적 페이지(179) 결정. 수신된 어드레스에 대응하는 정확한 기록(183)을 발견하기 위해 디렉토리 엔트리(175)의 오프셋 사용.

(5) 기록(183)으로부터 블록의 분류 결정. 부가적인 데이터의 저장으로 인해 분류가 변경되는지 여부 결정. 여기서, 블록은 부분 블록이고 부가적인 데이터는 무용 블록이 되도록 블록 내 남아있는 공간을 채운다.

(6) 다른 타입의 블록, 유효 데이터, 페이지 기입 포인터 위치 등등을 반영하기 위하여 업데이트된 현재 블록에 대한 기록(183)과 함께 기입 포인터(185)에 의해 표시된 위치에 기록 페이지(183)의 콘텐츠 카피.

(7) 블록 디렉토리 블록(170)의 다음 이용 가능한 물리적 페이지에 디렉토리 페이지(173) 카피. 기록 페이지의 새로운 물리적 위치를 반영하기 위하여 업데이트된 엔트리 및 기록 인덱스로 새로운 디렉토리 페이지 기입. 또한, 새로운 물리 페이지의 디렉토리 인덱스 업데이트.

(8) 블록에 대한 엔트리(189)를 포함하는 부분 블록 리스트 페이지(187)의 물리적 페이지 위치를 결정하기 위하여 디렉토리 인덱스를 다시 검색. (몇몇 다른 경우들은 하나 이상의 리스트를 찾을 수 있다).

(9) 현재 블록과 동일한 디스크립터 값을 가진 리스트 엔트리(189)를 발견하기 위하여 페이지(187)의 이진 검색 수행. 만약 하나 이상의 리스트 엔트리가 디스크립터 값을 가지면, 블록 어드레스에 의해 모든 매칭 엔트리들을 검색.

(10) 삭제된 현재 블록에 대한 엔트리(189)를 가진 새로운 위치에 부분 블록 리스트 페이지(187) 카피. 새로운 부분 블록 페이지는 부분 블록 페이지에 대한 새로운 물리적 위치를 가진 업데이트된 디렉토리 인덱스를 포함한다.

(11) 현재 블록(도시되지 않음)의 유효 데이터 양을 포함하는 블록 범위 당 유효 데이터를 커버하는 무용 블록 리스트 페이지의 물리적 페이지 위치를 결정하기 위하여 디렉토리 인덱스를 다시 검색.

(12) 무용 블록 리스트 페이지 카피, 블록에서 현재 유효 데이터 양에 따라 적당한 오프셋으로 현 블록에 대해 새로운 엔트리 부가. 새로운 무용 블록 리스트 페이지는 무용 블록 리스트(도시되지 않음)에 대한 새로운 위치를 가리키는 업데이트된 디렉토리 인덱스를 포함한다.

상기 단계들은 도시된 순서로 필수적으로 수행되지 않는다. 몇몇 단계들은 병렬로 수행될 수 있다. 예를 들어, 업데이트된 무용 블록 리스트 페이지 및 업데이트된 부분 블록 리스트 페이지의 기입은 메타블록 기입의 일부로서 병렬일 수 있다.

상세한 제 3 실시예

제 3 실시예에서, 기록은 언제든 메모리 어레이의 각각의 블록에 유지된다. 이것은 블록들의 하나 또는 그 이상의 부가적인 분류들을 포함하고, 예를 들어 무용 데이터를 포함하지 않는 파일 블록들에 대한 부가적인 분류가 도 4에 도시된 제 2 실시예의 분류에 부가될 수 있다. 비록 각각의 블록에 대한 기록을 유지하는 것이 유지된 기록들의 총 수에 부가되지만, 보다 간단한 구조들이 사용될 수 있게 한다. 제 3 실시예는 각각의 블록에 대한 기록을 가지는 것과 별개로 제 2 실시예와 유사하게 작동할 수 있다.

예를 들어, 기록들이 모든 블록을 위하여 유지되는 경우, 디렉토리 엔트리들은 또한 모든 블록을 위하여 유지된다. 디렉토리 엔트리들은 고정되고 균일한 크 기를 가진다. 따라서, 디렉토리 페이지는 블록 어드레스에 의해 순차적으로 순서가 매겨진 고정된 수의 엔트리들을 포함할 수 있다. 따라서, 각각의 디렉토리 페이지는 고정된 블록 어드레스 범위를 커버한다. 하나의 페이지 내 엔트리들이 블록 어드레스에 따라 미리 결정된 오프셋들을 가지기 때문에, 각각의 엔트리의 블록 어드레스를 독립적으로 기록할 필요가 없다. 특정 블록에 대한 디렉토리 엔트리를 발견하는 것은 블록을 포함하는 블록 어드레스 범위를 커버하는 디렉토리 페이지를 발견하고, 그 다음 디렉토리 페이지의 제 1 엔트리의 블록 어드레스 및 목표된 블록 어드레스 사이의 차에 의해 제공된 오프셋으로 상기 페이지 내 엔트리로 진행하는 문제이다. 따라서, 디렉토리 페이지의 이진 검색이 필요하지 않다. 대조하여, 기록들은 일반적으로 크기면에서 가변하여, 기록 페이지는 고정된 수의 엔트리들을 항상 유지하지 않는다. 이전 실시예들과 달리, 본 실시예에서 기록들은 엔트리가 임의의 리스트에 존재하지 않는 블록들에 유지될 수 있다.

메모리의 각각의 블록에 대한 기록을 유지하는 것은 몇몇 애플리케이션들에서 편리하다. 예를 들어, 디스크립터들은 블록의 물리적 특성들과 관련하여 유지될 수 있다. 상기 디스크립터의 하나의 예는 소거 카운트이다. 소거 카운트는 특정 블록이 소거된 횟수를 가리키고 소모 레벨링에 사용될 수 있다. 하나 또는 그 이상의 리스트들은 소거 카운트에 따른 블록들을 정할 수 있다. 선택적으로, 기록은 블록이 소거된 최종 시간으로부터 시간 스탬프를 포함하여, 블록들은 최종 소거 이후 시간에 의해 리스트에 주문될 수 있다.

비록 본 발명의 다양한 측면들이 예시적인 실시예들과 관련하여 기술되었지 만, 본 발명의 첨부된 청구항들의 전체 범위 내서 보호되는 것이 이해될 것이다.

Claims (34)

1. 비휘발성 재프로그램 가능 메모리 시스템에 있어서,

   비휘발성 메모리 회로로서,

   블록의 페이지로 데이터를 재프로그래밍하기 전에 함께 삭제된 메모리 셀의 블록으로 그룹화된 메모리 셀 어레이로서, 상기 블록은 삭제 유닛이고, 상기 페이지는 기록 유닛이며, 상기 블록은 물리 블록 어드레스에 의해 식별되는, 상기 메모리 셀 어레이와,

   상기 메모리 셀에 연결 가능하여, 상기 메모리 셀이 삭제 및 프로그램될 수 있는 판독, 기록, 및 삭제 회로를

   포함하는, 비휘발성 메모리 회로와,

   상기 메모리 셀 어레이와 작동 가능하게 연결된 제어기 회로로서, 상기 제어기 회로는 상기 메모리 회로와 상기 메모리 시스템의 외부 사이에서 데이터의 전달을 관리하고 상기 메모리 회로에서 호스트 데이터의 저장을 관리하는, 상기 제어기 회로를

   포함하고,

   상기 제어기 회로는,

   상기 메모리 회로와 상기 메모리 시스템의 외부 사이에서 데이터를 전달하기 위한 인터페이스 회로와,

   프로세싱 회로로서,

   상기 인터페이스 회로를 통해 상기 메모리 시스템 외부로부터 데이터를 수신하고 상기 수신된 데이터를 하나 이상의 블록으로 저장하는 단계와,

   상기 메모리 셀 어레이의 관리 데이터를 유지하는 단계와,

   제 2 리스트에 나타난 순서로 상기 제 2 리스트에서 복수의 블록 중 개별 블록에 저장된 데이터 상에서 상기 판독, 기록, 및 삭제 회로 중 하나 이상을 사용하는 작동이 수행되도록 하는 단계를

   포함하는 방식으로 작동하는, 프로세싱 회로를

   포함하고,

   상기 관리 데이터는,

   복수의 블록을 위한 복수의 기록(record)으로서, 상기 기록은, 상기 블록의 어드레스에 의해 식별된 바와 같이 상기 기록이 속하는 복수의 블록 중 하나에 저장된 데이터의 서로 다른 면(aspect)의 복수의 디스크립터(descriptor) 값을 개별적으로 포함하고, 상기 제어기 회로는 해당 블록에서 유효 데이터의 양인 기록에 제 1 디스크립터의 값을 기록하도록 작동하고, 또한 해당 블록에서 삭제 용량의 양인 기록에 제 2 디스크립터의 값을 기록하도록 작동하는, 상기 복수의 블록을 위한 복수의 기록과,

   복수의 블록의 어드레스에 의해 포인터(pointer)를 포함하는 제 1 리스트로서, 상기 포인터는 하나의 블록의 어드레스를 수신하는 것에 응답하여 블록 중 하나에 대한 기록 중 하나의 메모리 셀 어레이 내에서 위치를 개별적으로 가리키고, 상기 포인터는 각각의 복수의 블록의 어드레스의 순서로 포인터의 리스트에 위치한, 상기 제 1 리스트와,

   해당 기록은 적어도 상기 제 1 및 제 2 디스크립터의 값을 포함하는 복수의 블록의 어드레스를 포함하는 상기 제 2 리스트로서, 상기 제 2 리스트에서 복수의 블록의 어드레스는 해당 기록에서 상기 제 1 디스크립터의 값의 순서로 위치하는, 상기 제 2 리스트와,

   해당 기록이 적어도 해당 블록에서 일정량의 유효 데이터와 해당 블록에서 일정량의 무용 데이터의 디스크립터 값을 적어도 포함하는 복수의 블록의 어드레스를 포함하는 제 3 리스트로서, 상기 제어기는 해당 블록에서 유효 데이터의 양의 값의 순서로 상기 제 3 리스트에 복수의 블록의 어드레스를 두도록 추가 동작하는, 상기 제 3 리스트를

   포함하는, 비휘발성 재프로그램 가능 메모리 시스템.
2. 제 1항에 있어서, 복수의 블록 중 개별 블록에 저장된 데이터 상에서 수행될 상기 제어기 회로 작동은 상기 개별 블록으로부터 삭제된 공간을 구비한 다른 블록으로 유효 데이터를 복사하고, 이후 상기 개별 블록을 삭제하는 단계를 포함하는, 비휘발성 재프로그램 가능 메모리 시스템.
3. 제 1항에 있어서, 상기 제어기 회로는, 상기 제 2 디스크립터의 값을 포함하는 해당 기록을 갖는 상기 제 3 리스트로부터 블록을 추가로 빠뜨리는, 비휘발성 재프로그램 가능 메모리 시스템.
4. 비휘발성 재프로그램 가능 메모리 시스템에 있어서,

   비휘발성 메모리 회로로서,

   블록의 페이지로 데이터를 재프로그래밍하기 전에 함께 삭제된 메모리 셀의 블록으로 그룹화된 메모리 셀 어레이로서, 상기 블록은 삭제 유닛이고, 상기 페이지는 기록 유닛이며, 상기 블록은 물리 블록 어드레스에 의해 식별되는, 상기 메모리 셀 어레이와,

   상기 메모리 셀에 연결 가능하여, 상기 메모리 셀이 삭제 및 프로그램될 수 있는 판독, 기록, 및 삭제 회로를

   포함하는, 비휘발성 메모리 회로와,

   상기 메모리 셀 어레이와 작동 가능하게 연결된 제어기 회로로서, 상기 제어기 회로는 상기 메모리 회로와 상기 메모리 시스템의 외부 사이에서 데이터의 전달을 관리하고 상기 메모리 회로에서 호스트 데이터의 저장을 관리하는, 상기 제어기 회로를

   포함하고,

   상기 제어기 회로는,

   상기 메모리 회로와 상기 메모리 시스템의 외부 사이에서 데이터를 전달하기 위한 인터페이스 회로와,

   프로세싱 회로로서,

   상기 인터페이스 회로를 통해 상기 메모리 시스템에 의해 수신된 데이터를 복수의 블록에 저장하는 단계와,

   상기 메모리 셀 어레이의 관리 데이터를 유지하는 단계와,

   제 2 및 제 3 리스트에 나타난 순서로 상기 복수의 블록 중 개별 블록에 저장된 데이터 상에서 상기 메모리 시스템의 동작을 수행하기 위해 상기 판독, 기록, 및 삭제 회로 중 하나 이상에 의해, 어드레스가 상기 제 2 및 제 3 리스트 상에 있는 블록이 액세스되도록 하는 단계를

   포함하는 방식으로 작동하는, 프로세싱 회로를

   포함하고,

   상기 관리 데이터는,

   복수의 블록을 위한 복수의 기록(record)으로서, 상기 기록은, 상기 블록의 어드레스에 의해 식별된 바와 같이 상기 기록이 속하는 복수의 블록 중 개별 블록 내에 일정량의 삭제 데이터, 일정량의 무용 데이터, 및 일정량의 삭제 용량의 표시를 개별적으로 포함하는, 상기 복수의 블록을 위한 복수의 기록과,

   복수의 블록의 어드레스에 의해 포인터(pointer)를 포함하는 제 1 리스트로서, 상기 포인터는 하나의 블록의 어드레스를 수신하는 것에 응답하여 블록 중 하나에 대한 기록 중 하나의 메모리 셀 어레이 내에서 위치를 개별적으로 가리키고, 상기 포인터는 각각의 복수의 블록의 어드레스의 순서로 포인터의 리스트에 위치한, 상기 제 1 리스트와,

   해당 기록은 적어도 유효 데이터와 삭제 용량의 양의 값을 포함하는 복수의 블록의 어드레스를 포함하는 상기 제 2 리스트로서, 상기 제 2 리스트에서 복수의 블록의 어드레스는 해당 기록에서 유효 데이터의 양의 순서로 위치하는, 상기 제 2 리스트와,

   해당 기록이 적어도 유효 데이터와 무용 데이터의 양의 값을 포함하지만 삭제된 용량의 양은 포함하지 않는 복수의 블록의 어드레스를 포함하는 상기 제 3 리스트로서, 상기 제 3 리스트에서 상기 복수의 블록의 어드레스는 해당 기록에서 유효 데이터의 양의 순서로 위치하는, 상기 제 3 리스트를

   포함하는, 비휘발성 재프로그램 가능 메모리 시스템.
5. 제어기 회로와 메모리 회로를 갖는 비휘발성 메모리 시스템을 작동시키는 방법으로서,

   상기 메모리 회로는, 블록의 페이지로 데이터를 재프로그래밍하기 전에 함께 삭제된 메모리 셀의 블록으로 그룹화된 메모리 셀을 포함하고, 상기 블록은 삭제 유닛이고, 상기 페이지는 기록 유닛이며, 판독, 기록, 및 삭제 회로는 상기 메모리 셀에 연결 가능하고, 상기 블록은 물리 블록 어드레스에 의해 식별되며, 상기 제어기 회로는, 상기 메모리 시스템이 통신하는 호스트와 상기 메모리 회로 사이에서 데이터의 전달을 관리하고 상기 메모리 회로 상에서 호스트 데이터의 저장을 관리하는, 비휘발성 메모리 시스템을 작동시키는 방법에 있어서,

   상기 기록 회로를 사용하여 복수의 블록에서 상기 제어기 회로를 통해 상기 메모리 시스템에 의해 수신된 데이터를 저장하는 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 상기 복수의 블록 중 해당 블록에 대해 복수의 기록을 유지하는 단계로서, 상기 기록은, 상기 블록의 어드레스에 의해 식별되는 바와 같이 상기 기록이 속하는 복수의 블록 중 하나에 저장된 데이터의 서로 다른 양상의 적어도 제 1, 제 2, 및 제 3 디스크립터의 값을 개별적으로 포함하고, 상기 제 1 디스크립터는 해당 블록에서 일정량의 유효 데이터이고, 상기 제 2 디스크립터는 해당 블록에서 일정량의 삭제된 용량이며, 상기 제 3 디스크립터는 해당 블록에서 일정량의 무용 데이터인, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 상기 복수의 블록의 어드레스에 의해 포인터를 포함하는 제 1 리스트를 유지하는 단계로서, 상기 포인터는 상기 하나의 블록의 어드레스를 수신하는 것에 응답하여 블록 중 하나의 블록에 대해 기록 중 하나의 기록의 상기 메모리 시스템 내 위치를 개별적으로 가리키고, 포인터는 각각의 복수의 블록의 어드레스의 순서로 포인터의 리스트에 위치한, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 해당 기록이 적어도 상기 제 1 및 제 2 디스크립터의 값을 포함하는 복수의 블록의 어드레스를 포함하는 제 2 리스트를 유지하는 단계로서, 상기 제 2 리스트에서 상기 복수의 블록의 어드레스는 해당 기록에서 상기 제 1 디스크립터의 값의 순서로 위치한, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 해당 기록이 적어도 상기 제 1 및 제 3 디스크립터의 값을 포함하는 복수의 블록의 어드레스를 포함하는 제 3 리스트를 유지하는 단계로서, 상기 제 3 리스트에서 상기 복수의 블록의 어드레스는 해당 기록에서 상기 제 1 디스크립터의 값의 순서로 위치한, 상기 유지 단계와,

   판독, 기록, 및 삭제 회로 중 하나 이상을 사용하여, 상기 제 2 리스트에 나타난 순서로 상기 제 2 리스트에서 상기 복수의 블록 중 개별 블록에 저장된 데이터 상에서 상기 메모리 시스템의 작동을 수행하는 단계를

   포함하는, 비휘발성 메모리 시스템을 작동시키는 방법.
6. 제 5항에 있어서, 상기 메모리 시스템의 작동을 수행하는 단계는, 상기 개별 블록으로부터 삭제된 공간을 구비한 다른 블록으로 유효 데이터를 복사하고, 이후 상기 개별 블록을 삭제하는 단계를 포함하는, 비휘발성 메모리 시스템을 작동시키는 방법.
7. 제 5항에 있어서, 상기 제 3 리스트는, 상기 제 2 디스크립터의 값을 포함하는 해당 기록을 갖는 상기 복수의 블록의 어드레스를 빠뜨리는, 비휘발성 메모리 시스템을 작동시키는 방법.
8. 제 5항에 있어서, 상기 제 2 리스트는, 상기 제 3 디스크립터의 값을 포함하는 해당 기록을 갖는 상기 복수의 블록의 어드레스를 빠뜨리는, 비휘발성 메모리 시스템을 작동시키는 방법.
9. 제어기 회로와 메모리 회로를 갖는 비휘발성 메모리 시스템을 작동시키는 방법으로서,

   상기 메모리 회로는, 블록의 페이지로 데이터를 재프로그래밍하기 전에 함께 삭제된 메모리 셀의 블록으로 그룹화된 메모리 셀을 포함하고, 상기 블록은 삭제 유닛이고, 상기 페이지는 기록 유닛이며, 판독, 기록, 및 삭제 회로는 상기 메모리 셀에 연결 가능하고, 상기 블록은 물리 블록 어드레스에 의해 식별되며, 상기 제어기 회로는, 상기 메모리 시스템이 통신하는 호스트와 상기 메모리 회로 사이에서 데이터의 전달을 관리하고 상기 메모리 회로 상에서 호스트 데이터의 저장을 관리하는, 비휘발성 메모리 시스템을 작동시키는 방법에 있어서,

   상기 기록 회로를 사용하여 복수의 블록에서 상기 제어기 회로를 통해 상기 메모리 시스템에 의해 수신된 데이터를 저장하는 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 상기 복수의 블록에 대해 복수의 기록을 유지하는 단계로서, 상기 기록은, 상기 블록의 어드레스에 의해 식별되는 바와 같이 상기 기록이 속하는 복수의 블록 중 개별 블록 내에 일정량의 유효 데이터, 일정량의 무용 데이터, 및 일정량의 삭제 용량의 표시를 개별적으로 포함하는, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 상기 복수의 블록의 어드레스에 의해 포인터를 포함하는 제 1 리스트를 유지하는 단계로서, 상기 포인터는 상기 하나의 블록의 어드레스를 수신하는 것에 응답하여 블록 중 하나의 블록에 대해 기록 중 하나의 기록의 상기 메모리 시스템 내 위치를 개별적으로 가리키고, 포인터는 각각의 복수의 블록의 어드레스의 순서로 포인터의 리스트에 위치한, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 해당 기록이 적어도 유효 데이터와 삭제 용량의 양의 값을 포함하는 복수의 블록의 어드레스를 포함하는 제 2 리스트를 유지하는 단계로서, 상기 제 2 리스트에서 상기 복수의 블록의 어드레스는 해당 기록에서 유효 데이터의 양의 순서로 위치한, 상기 유지 단계와,

   상기 제어기 회로에 의해 상기 메모리 회로의 제 1 블록에서 해당 기록이 적어도 유효 데이터와 무용 데이터의 양의 값을 포함하지만 삭제 용량의 양은 갖지 않는 복수의 블록의 어드레스를 포함하는 제 3 리스트를 유지하는 단계로서, 상기 제 3 리스트에서 상기 복수의 블록의 어드레스는 해당 기록에서 유효 데이터의 양의 순서로 위치한, 상기 유지 단계와,

   판독, 기록, 및 삭제 회로 중 하나 이상을 사용하여, 상기 제 2 및 제 3 리스트에 나타난 순서로 상기 복수의 블록 중 개별 블록에 저장된 데이터 상에서 상기 메모리 시스템의 작동을 수행하기 위해 어드레스가 상기 제 2 및 제 3 리스트에 있는 블록에 액세스하는 단계를

   포함하는, 비휘발성 메모리 시스템을 작동시키는 방법.
10. 삭제
11. 삭제
12. 삭제
13. 삭제
14. 삭제
15. 삭제
16. 삭제
17. 삭제
18. 삭제
19. 삭제
20. 삭제
21. 삭제
22. 삭제
23. 삭제
24. 삭제
25. 삭제
26. 삭제
27. 삭제
28. 삭제
29. 삭제
30. 삭제
31. 삭제
32. 삭제
33. 삭제
34. 삭제

Images