KR100908637B1 - 플래시 메모리의 데이터 관리방법 - Google Patents

Abstract

플래시 메모리의 데이터를 관리하기 위한 방법이 개시된다. 플래시 메모리의 페이지에 프로그래밍하는 횟수를 최소화하기 위해 버퍼 상에 할당된 각각의 페이지에는 우선순위 플래그가 부여된다. 우선순위 플래그의 부여에 의해 각각의 페이지는 데이터의 기록이 가능한 경우와 기록이 불가능하여 추방 가능한 페이지로 구분된다. 또한, 빈 공간 리스트에 새롭게 추가되는 페이지는 빈 공간 리스트의 첫 번째 페이지로 설정되지 아니한다. 따라서 데이터가 기록되는 페이지에는 빈 공간이 존재하지 않을 때까지 데이터의 기록이 가능해진다. 빈 공간이 존재하지 않는 페이지에는 구별되는 우선순위 플래그가 설정되고, 이후의 동작에 의해 버퍼로부터 추방된다.

플래시 메모리, 페이지, 프로그래밍, 소거, 버퍼, 빈 공간 리스트

Description

플래시 메모리의 데이터 관리방법{Method of Managing Data of Flash Memory}

본 발명은 플래시 메모리의 데이터를 관리하기 위한 방법에 관한 것으로, 더욱 상세하게는 데이터의 갱신 시에 최소한의 프로그래밍 동작을 통해 데이터를 관리할 수 있는 방법에 관한 것이다.

플래시 메모리는 비휘발성 메모리(nonvolatile memory)의 일종으로 전원이 차단되는 경우에도 저장된 데이터가 소멸하지 않는 특성을 가진다. 이러한, 플래시 메모리는 그 구조상 낸드 플래시 메모리와 노아 플래시 메모리로 구분된다.

특히, 낸드 플래시 메모리는 셀 어레이로 구성되며, 셀 어레이는 다수의 블록들로 구성된다. 또한, 각각의 블록은 다수의 페이지로 이루어진다. 플래시 메모리의 동작은 크게 읽기, 프로그래밍, 소거 동작으로 나누어진다. 특히, 낸드 플래시 메모리는 그 하드웨어적인 구조상, 소거 동작은 블록 단위로 이루어지며, 프로그래밍 및 읽기 동작은 페이지 단위로 이루어진다. 즉, 소거 동작과 프로그래밍 동작은 그 단위가 서로 상이하므로 이에 관련된 데이터의 관리가 별도로 이루어진다. 예컨대, 플래시 메모리를 하드디스크처럼 사용하기 위해서는, 기록되는 데이터의 물리적 어드레스와 논리적 어드레스를 독립적으로 관리하는 어드레스 매핑 동작 등이 요구된다.

또한, 낸드 플래시 메모리의 경우, 프로그래밍은 Hot-Carrier Injection을 통해 이루어지고, 소거동작은 F-N(Fowler-Nordheim) Tunneling 현상을 이용하여 이루어진다. 또한, 읽기 연산은 각각의 셀의 문턱전압의 변화를 감지하는 것을 통해 이루어진다. 따라서 프로그래밍 동작은 읽기 연산에 비해 속도가 느린 특성을 가진다.

만일, 플래시 메모리에 데이터를 갱신하고자 하는 경우, 기존의 DRAM과는 달리 소거 동작이 먼저 수행되어야 한다. 즉, 새로운 데이터로 기존의 페이지를 갱신하고자 하는 경우, 기존의 데이터가 프로그램 된 페이지가 속한 블록을 소거하고, 해당하는 페이지에 새로운 데이터를 프로그래밍 하여야 한다. 특히, 소거 동작은 플래시 메모리의 구조상 오버헤드가 매우 큰 동작이다. 통상의 경우, 플래시 메모리의 제조사가 보장하는 소거 연산의 횟수는 10만 번 이하로 제한된다. 이러한 소거 연산을 최소화하여 플래시 메모리의 동작 수명을 향상시키기 위해서는, 프로그래밍 동작의 횟수가 감소되어야 한다. 이는 일반적으로 프로그래밍 이전에 소거 동작이 선행되어야 하기 때문이다.

플래시 메모리에 저장되는 데이터의 관리 방법은 데이터의 삽입, 삭제, 배치 등을 결정하는 자료구조이다. 이러한 데이터의 관리 방법으로는 논-클러스터링 방법(non-clustering method)이 있다. 논-클러스터링 방법은 기록되는 데이터의 키 값을 고려하지 않고, 빈 공간이 존재하는 페이지에 데이터를 저장하는 방법이다. 일반적으로 빈 공간이 존재하는 것으로 판정된 페이지들 중 첫 번째 페이지에 데이터는 저장된다. 또한, 빈 공간이 존재하는 것으로 판정된 페이지들은 빈 공간 리스트(free space list)에 의해 관리된다.

도 1은 종래의 빈 공간 리스트를 설명하기 위한 개념도이다.

도 1을 참조하면, 빈 공간 리스트에 의해 관리되는 페이지는 페이지 1, 페이지 2, 페이지 3 및 페이지 4의 순으로 이루어진다. 만일, 페이지 1에 저장된 데이터가 삭제되는 경우, 페이지 1에는 새로운 빈 공간이 발생한다. 따라서 페이지 1은 빈 공간 리스트에 추가되어야 한다. 이 때, 페이지 1은 빈 공간 리스트의 시작 부분에 추가된다. 또한, 새로운 데이터가 추가되는 경우, 추가되는 데이터는 빈 공간 리스트의 첫 번째 페이지인 페이지 1에 저장된다.

도 2는 데이터의 삽입이 있는 경우, 종래의 논-클러스터링 방법을 설명하기 위한 프로우 차트이다.

도 2를 참조하면, 삽입될 데이터가 발생(S10)하면, 새로운 데이터가 삽입될 페이지가 버퍼 상에 존재하는 지를 확인한다(S20). 상기 버퍼는 프로세서와 메모리 사이의 속도차이를 보완해주는 역할을 수행한다. 따라서 컴퓨터의 메인 메모리의 일부 영역을 버퍼로 사용하거나, 플래시 메모리 내에 별도로 추가된 메모리를 버퍼로 사용할 수 있다.

또한, 버퍼 상에 존재하는 페이지는 플래시 메모리의 실제 페이지가 버퍼 상에 존재하는 것이 아니라, 플래시 메모리의 해당하는 페이지를 구성하는 특정 어드레스 및 상기 특정 어드레스에 저장된 데이터를 지칭한다. 즉, 버퍼는 실제 플래시 메모리의 페이지에 데이터를 기록하기 위해 해당하는 페이지의 어드레스에 적합한 데이터를 추가하거나, 삭제한다.

이어서, 해당하는 페이지가 버퍼 상에 존재하는 경우, 별도의 처리 과정 없이 페이지에 새로운 데이터를 저장한다(S30).

만일 해당하는 페이지가 버퍼에 존재하지 않는 경우, 버퍼에 페이지를 올리는 과정이 필요하다. 즉, 메모리의 페이지가 가지는 용량을 버퍼에서 설정하는 과정이 필요하다. 이 때, 버퍼에 해당하는 페이지를 설정할 수 있는 공간이 있는지를 판단한다(S40).

만일, 버퍼에 해당하는 페이지를 설정할 공간이 충분한 경우, 해당하는 페이지를 버퍼에 설정하고(S50), 새로운 데이터를 페이지에 기록한다(S30).

만일, 버퍼에 충분한 공간이 존재하지 않는 경우, 버퍼에 여유 공간을 확보하기 위해 특정의 페이지를 버퍼로부터 추방(flush)하는 과정이 필요하다. 추방을 위해서는 먼저 추방될 페이지를 선택하는 동작이 선행되어야 한다. 이처럼 추방될 페이지를 선택하는 알고리즘을 버퍼 교체 알고리즘(buffer replacement algorithm)이라 하고, 추방되는 페이지를 희생자(victim) 페이지라 한다. 희생자 페이지를 선정한 경우(S60), 희생자 페이지에 내용의 변경이 있는지를 확인한다(S70).

만일, 희생자 페이지에 내용의 변경이 없으면, 버퍼에서 희생자 페이지를 추방하고, 새로운 페이지를 버퍼에 설정한다(S50).

또한, 버퍼 교체 알고리즘을 통해 선택된 희생자 페이지에 내용의 변경이 있는 경우, 희생자 페이지의 데이터는 프로그래밍 동작을 통해 플래시 메모리의 해당 하는 페이지에 기록된다(S80). 플래시 메모리에 희생자 페이지의 데이터가 반영된 후, 희생자 페이지는 버퍼로부터 추방되고, 버퍼에는 새로운 페이지가 할당된다(S50).

그러나 상술한 논-클러스터링 방법은 페이지에 데이터를 더 기록할 수 있음에도 불구하고, 프로그래밍 연산을 수행하는 경우가 발생한다. 이는 기존의 버퍼 교체 알고리즘이 페이지 내의 빈공간의 크기를 고려하지 않고, 빈 공간이 있음에도 불구하고 희생자 페이지로 선정하기 때문이다.

도 3a 내지 도 3f는 종래의 버퍼 교체 알고리즘을 통해 프로그래밍 동작을 수행하는 과정을 도시한 개념도이다.

도 3a를 참조하면, 버퍼(100)에 설정된 페이지 1에 데이터가 삽입된다. 즉, 플래시 메모리(120)의 페이지 1에 대한 읽기 연산을 통해, 페이지 1이 버퍼에 올라오면, 버퍼(100)에서는 데이터가 페이지 1에 삽입된다. 만일, 버퍼(100)의 페이지 1이 희생자 페이지로 선정되면, 도 3b와 같이 플래시 메모리(120)에 대한 프로그래밍 동작이 수행된다. 프로그래밍 동작이 수행되어 페이지 1의 데이터가 플래시 메모리(120)에 기록되면, 버퍼(100)에 할당된 페이지 1은 삭제된다. 만일, 페이지 3에 빈 공간이 발생되고, 이에 데이터를 기록하는 경우, 도 3c와 같이 페이지 3은 버퍼(100)로 올라온다.

또한, 페이지 1에 빈 공간이 존재하는 경우, 새로운 데이터가 페이지 1에 기록될 수 있다. 따라서 도 3d에 도시된 바와 같이 읽기 동작을 통해 플래시 메모리(120)의 페이지 1은 다시 버퍼(100)로 올라오며, 버퍼(100)의 페이지 1에는 새로 운 데이터의 기록이 수행된다. 버퍼(100)의 페이지 1에서 데이터의 저장이 수행된 후, 페이지 1이 희생자 페이지로 선정되면, 도 3e에 도시된 바와 같이 다시 페이지 1에 대한 프로그래밍 동작이 수행되어야 한다. 계속해서 도 3f처럼 페이지 3에 빈 공간이 발생되고, 해당하는 페이지에 데이터를 기록하여야 하는 경우, 플래시 메모리(120)의 페이지 3의 영역은 버퍼(100)에서 읽기 동작을 통해 설정된다.

상술한 바와 같이, 논-클러스터링 방법에서는 데이터가 삽입되는 횟수만큼 페이지의 프로그래밍 동작이 발생할 수 있다. 이러한 잦은 프로그래밍 동작으로 인해 데이터를 버퍼에 기록하는 시간이 지연되며, 플래시 메모리에서의 소거 동작이 증가되어 플래시 메모리의 수명이 단축되는 문제가 발생된다.

이를 해결하기 위해서는 데이터가 삽입되는 페이지에는 최대한 많은 데이터가 삽입되도록 한 다음, 프로그래밍 연산이 수행되는 버퍼 교체 알고리즘이 요청된다 할 것이다.

상술한 문제점을 해결하기 위해 본 발명의 목적은 데이터의 프로그래밍 동작 횟수를 최소화할 수 있는 플래시 메모리의 데이터 관리방법을 제공하는데 있다.

상기 목적을 달성하기 위한 본 발명은, 플래시 메모리의 페이지 할당되는 데이터를 관리하는 방법에 있어서, 버퍼 상에 할당된 페이지에 우선순위 플래그를 설정하는 단계; 상기 우선순위 플래그를 반영하여 희생자를 선정하는 단계; 및 새롭게 빈 공간이 발생한 페이지를 빈 공간 리스트의 첫 번째 페이지로의 설정을 회피하여 추가하는 단계를 포함하는 플래시 메모리의 데이터 관리 방법을 제공한다.

본 발명에 따르면, 프로그래밍 동작 및 소거 동작에 따른 로드가 매우 큰 플래시 메모리에서는 데이터들이 삽입되는 페이지에는 가능한 많은 데이터들이 삽입된 이후에 프로그래밍 동작이 수행되어야 한다. 따라서 각각의 페이지에 데이터의 기록에 따른 빈 공간이 발생되지 않도록 데이터를 관리한다. 이를 통하여 프로그래밍 동작의 횟수는 감소되며, 프로그래밍 횟수의 감소는 소거 동작의 감소로 이어진다. 이러한 소거 동작의 감소는 플래시 메모리의 수명을 연장시킨다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 형태를 가질 수 있는 바, 특정 실시 예들을 도면에 예시하고 본문에 상세하게 설명하고자 한다. 그러나 이는 본 발명을 특정한 개시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 각 도면을 설명하면서 유사한 참조부호를 유사한 구성요소에 대해 사용하였다.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥 상 가지는 의미와 일치하는 의미를 가지는 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.

이하, 첨부한 도면들을 참조하여, 본 발명의 바람직한 실시 예를 보다 상세하게 설명하고자 한다.

실시예

본 발명에 따른 버퍼 교체 알고리즘에서는 데이터가 삽입되는 페이지에는 우선순위 플래그(priority flag)가 설정된다. 따라서 희생자 페이지의 선정 시, 우선순위 플래그를 고려한다.

상기 우선순위 플래그는 데이터가 삽입되는 페이지 또는 희생자 페이지로 선택되어 추방 될 수 있는 페이지를 나타낸다. 즉, 버퍼 상에 설정된 각각의 페이지에 빈 공간이 존재하는 경우와 빈 공간이 존재하지 않는 경우를 구별하여 우선순위 플래그를 설정한다.

예컨대, 특정의 페이지에 새로운 데이터가 삽입되는 경우, 해당하는 페이지의 우선순위 플래그는 1로 설정된다. 우선순위 플래그가 1로 설정된 페이지는 희생자 페이지를 선택하는 과정에서 제외된다. 만일 해당 페이지에 더 이상 데이터를 삽입할 수 있는 공간이 없는 경우에는 해당 페이지의 우선순위 플래그는 0으로 설정된다. 우선순위 플래그가 0으로 설정된 페이지는 버퍼의 공간에 여유가 없는 상태에서 새로운 페이지를 할당하여야 하는 경우, 버퍼로부터 추방된다.

또한, 빈 공간 리스트에 새로운 페이지가 추가되는 경우, 빈 공간 리스트의 시작 부분을 제외한 다른 부분에 새로운 페이지가 추가된다.

도 4a 내지 도 4c는 본 발명의 바람직한 실시 예에 따라 버퍼 교체 알고리즘을 이용한 빈 공간 리스트의 관리방법을 도시한 개념도들이다.

도 4a를 참조하면, 먼저 페이지 1(200)이 빈 공간 리스트의 시작 부분에 해당한다. 또한, 페이지 1(200)에 이어서 페이지 7(210)이 빈 공간 리스트에 의해 관리된다.

도 4b를 참조하면, 페이지 3에 새롭게 빈 공간이 발생하는 경우, 페이지 3(220)은 빈 공간 리스트에 추가되어야 한다. 추가되는 페이지 3(220)은 빈 공간 리스트의 시작 부분에 삽입되지 아니하고, 다른 부분에 삽입된다. 예컨대, 상기 도 4b에서는 리스트의 두 번째에 삽입된다.

도 4c를 참조하면, 새로운 데이터가 삽입되는 경우, 데이터의 삽입은 빈 공간 리스트에서 첫 번째 페이지인 페이지 1(200)에서 발생된다. 따라서 페이지 1(200)에 새로운 데이터가 모두 기록되어 페이지 1(200)에 빈 공간이 존재하지 않을 때까지, 데이터의 기록은 계속된다. 또한, 데이터의 삽입에 의해 페이지 1(200)에 빈 공간이 존재하지 않으면, 페이지 1(200)의 우선순위 플래그는 0으로 설정된다.

또한, 버퍼 교체 알고리즘은 빈 공간이 발생된 페이지를 버퍼 상에 어떻게 설정하는가에 대한 것이다.

만일, 데이터를 기록하기 위해 새로운 페이지가 버퍼에 할당되어야 하는 경우, 먼저 버퍼에 새로운 페이지를 올릴 공간이 있는 지를 확인한다.

새로운 페이지를 올릴 공간이 있는 경우에는 빈 공간 리스트의 시작 부분의 페이지를 버퍼에 올린다.

또한, 새로운 페이지를 버퍼에 올릴 공간이 부족한 경우, 버퍼 교체 알고리즘을 수행하여 희생자 페이지를 선정한다.

상기 버퍼 교체 알고리즘에서 우선순위 플래그가 0인 페이지는 버퍼로부터 추방된다. 즉, 우선순위 플래그가 0인 페이지는 플래시 메모리에 프로그래밍 되고, 새로운 페이지는 추방된 페이지를 대체하여 할당된다. 우선순위가 플래그가 0인 페이지는 데이터가 기록되는 페이지가 아니거나 페이지 내에 데이터가 삽입될 빈 공간이 존재하지 않는 페이지이다.

만일, 새로운 페이지에 데이터가 삽입되어야 하는 경우, 추방된 페이지를 대체하여 할당되는 새로운 페이지는 빈 공간 리스트의 시작 부분에서 할당된다.

따라서 기존의 빈 공간 리스트에서 시작 부분의 페이지에 데이터의 삽입이 일어나고, 시작 부분의 페이지에 빈 공간이 존재하는 경우, 시작 부분의 페이지에는 다른 데이터가 기록될 수 있다. 즉, 시작 부분의 페이지에 빈 공간이 존재하지 않을 때까지 데이터의 기록이 수행되며, 빈 공간이 존재하지 않은 경우에는 우선순위 플래그는 0으로 설정된다.

특히, 도 4c에 도시된 바와 같이, 페이지 1(200)에 새로운 데이터를 삽입하는 과정에서, 페이지 3(220)에 빈 공간이 발생하는 경우, 페이지 3(220)은 빈 공간 리스트의 시작 부분에 삽입되지 않으므로, 빈 공간 리스트의 시작 부분인 페이지 1(200)에는 지속적인 데이터의 삽입이 가능해진다.

종래의 경우, 페이지 3(220)에 빈 공간이 발생하면, 페이지 3(220)이 빈 공간 리스트의 시작 부분으로 설정되고, 페이지 3(220)에서 데이터의 삽입이 발생한다. 따라서 이전의 시작 페이지인 페이지 1(200)에 빈 공간이 있음에도 불구하고 새로운 데이터가 페이지 1(200)에 더 이상 기록되지 아니하고, 우선순위 플래그가 1로 설정되는 문제가 발생하였다. 그러나 본 발명에 따를 경우, 빈 공간이 발생된 페이지는 리스트의 중간에 삽입되므로, 기록중이거나 기록예정인 페이지에서는 빈 공간이 존재하지 않을 때까지 지속적인 데이터의 기록이 가능해진다.

이후에, 우선순위 플래그가 0로 설정되고, 빈 공간이 존재하지 않는 페이지는 버퍼 교체 알고리즘을 통해 희생자 페이지로 선정된다. 희생자 페이지로 선정된 빈 공간이 존재하지 않는 페이지는 프로그래밍 동작을 통해 플래시 메모리에 기록된다. 따라서 종래에 비해 빈번한 프로그래밍 동작에 의한 플래시 메모리의 수명 단축은 방지된다.

또한, 본 실시 예에서는 우선순위 플래그를 데이터가 삽입되는 페이지의 상태에 따라 0과 1의 두 가지 등급으로만 구별하였다. 그러나 우선순위를 부여하는 기준을 달리하고, 기준에 따라 여러 단계의 우선순위를 부여하는 것도 가능하다. 특히, 각 페이지 그룹의 최상위 페이지인 루트 페이지에 대해서 최상의 등급을 부여하고, 차상위의 페이지에 대해서는 차상의 등급을 부여하는 방법을 통해, 우선순위에 따라 버퍼 교체 알고리즘을 적용할 수도 있다.

상술한 바와 같이, 버퍼에 할당된 각각의 페이지에 대해 우선순위 플래그를 설정하고, 새로이 빈 공간이 발생된 페이지를 빈 공간 리스트에서 첫 번째 페이지 이외의 리스트에 삽입하는 경우, 새로운 데이터를 기록하는 페이지는 변경되지 아니하고, 빈 공간이 없어질 때까지 기록할 수 있는 이점이 있으며, 데이터의 삽입마다 발생하는 페이지의 프로그래밍 및 이에 따른 소거 동작의 횟수는 최소화될 수 있다. 따라서 빈번한 소거 동작에 의한 플래시 메모리의 수명 저하가 개선된다.

도 1은 종래의 빈 공간 리스트를 설명하기 위한 개념도이다.

도 2는 데이터의 삽입이 있는 경우, 종래의 논-클러스터링 방법을 설명하기 위한 프로우 차트이다.

도 3a 내지 도 3f는 종래의 버퍼 교체 알고리즘을 통해 프로그래밍 동작을 수행하는 과정을 도시한 개념도이다.

도 4a 내지 도 4c는 본 발명의 바람직한 실시 예에 따라 버퍼 교체 알고리즘을 이용한 빈 공간 리스트의 관리방법을 도시한 개념도들이다.

Claims (5)

1. 플래시 메모리의 페이지 할당되는 데이터를 관리하는 방법에 있어서,

   버퍼 상에 할당된 페이지에 우선순위 플래그를 설정하는 단계;

   상기 우선순위 플래그를 반영하여 희생자 페이지를 선정하는 단계;

   상기 희생자 페이지에 기록된 데이터를 상기 플래시 메모리에 프로그래밍하고, 상기 희생자 페이지를 상기 버퍼로부터 추방하는 단계; 및

   빈 공간 리스트에서 첫 번째 페이지 이외의 공간에 상기 플래시 메모리의 페이지를 상기 버퍼에 할당하는 단계를 포함하되, 상기 첫 번째 페이지는 데이터가 기록될 공간이 없을 때까지 수행되고, 상기 버퍼에 새롭게 할당되는 페이지는 데이터가 기록될 수 있는 저장 공간을 가지는 것을 특징으로 하는 플래시 메모리의 데이터 관리방법.
2. 제1항에 있어서, 상기 우선순위 플래그는,

   상기 버퍼 상의 페이지에 빈 공간이 존재하는 경우 및 상기 버퍼 상의 페이지에 빈 공간이 존재하지 않는 경우로 나누어 다른 값으로 설정되는 것을 특징으로 하는 플래시 메모리의 데이터 관리방법.
3. 삭제
4. 제1항에 있어서, 상기 우선순위 플래그가 빈 공간이 없는 페이지를 나타내는 경우, 빈 공간 리스트로부터 추방되는 것을 특징으로 하는 플래시 메모리의 데이터 관리방법.
5. 제4항에 있어서, 상기 빈 공간 리스트로부터의 추방은 상기 빈 공간이 없는 페이지의 데이터를 플래시 메모리에 프로그래밍 하는 것을 특징으로 하는 플래시 메모리의 데이터 관리방법.

Images