Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-09-05
2004-07-06
Kim, Hong (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S103000, C711S005000, C711S203000, C711S168000, C711S170000, C365S185110, C365S185290, C365S185330
Reexamination Certificate
active
06760805
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an improved system for storing and retrieving information in flash memory systems, and more particularly to a system that organizes and manages data written to large page flash memory devices.
2. Description of the Related Art
As will be appreciated by those skilled in the art, electrically erasable and programmable read-only memories (EEPROMs) comprised of flash-type, floating-gate transistors have been described in the art and are presently commercially available. These so-called flash memories are non-volatile memories similar in functionality and performance to EPROM memories, with an additional functionality that allows an in-circuit, programmable, operation to erase blocks of the memory. In a typical flash memory, however, it is not practical to rewrite a previously written area of the memory without a prior block erase of the area.
In a typical computer system, the operating system program is responsible for data management of the data storage devices that are a part of the system. A necessary, and usually sufficient, attribute of a data storage device is to achieve compatibility with the operating system program, such that the operating system can read data from these devices, and write data to any location in these data storage medium. Thus, typical flash memories are not compatible with typical existing operating system programs, since data cannot be written to an area of flash memory in which data has previously been written, unless the area is first erased.
Software mechanisms have been proposed in the art that allow a flash memory to be managed by existing computer operating programs, without modification of the operating system program. However, these prior art programs operate the flash memory as a “write once read many” device. Such known software mechanisms, however, cannot recycle previously written memory locations. When all locations are eventually written, the memory cannot be further used without specific user intervention.
Considering the limitations of flash memory erasing and rewriting, the requirement for a software management system to manage these functions of the flash memory device is imperative. Such a system has been disclosed, for example, in U.S. Pat. No. 5,404,485 of Ban, Amir, filed on Mar. 5, 1993, which is incorporated by reference as if fully set forth herein.
Furthermore, there is a need to enable page-mode devices exemplified by the NAND and AND technologies, to be reorganized when no more unwritten physical units are available. Such a need has been answered by a method for organizing a flash memory, in which the size of the memory portion for reading or writing data, such as a page, differs from the size of the smallest portion for erasing, such as a unit. A Flash file system optimized for page-mode flash technologies has been disclosed, for example, in U.S. Pat. No. 5,937,425 of Ban, Amir, filed on Oct. 16, 1997, which is incorporated by reference as if fully set forth herein. According to both the Ban '425 invention and the present invention, the term “page” is defined as the smallest chunk of data to be written in one operation, and the term “unit” is defined as the smallest chunk of data to be erased in one operation (with a unit containing one or more pages).
Most operating systems (OS) in use today logically organize their file storage systems based on a basic logical data unit of a “sector”, which is the smallest amount of data which is read or written by the OS from/to the storage device, be it a magnetic hard disk or a flash memory disk. The most common size of a sector is today 512 bytes, even though other sizes are possible. Because there is some fixed system overhead associated with each read or write operation (regardless of its size), it is more efficient for the OS to handle larger chunks of data, and many OS therefore define such larger chunks (sometimes called “clusters”) which combine several sectors into one larger logical entity. Still, at the lowest level of accessing the hardware, the basic unit is still the sector.
For many flash memory disks, the device's physical structure is quite suitable for this OS structure, as the 512-bytes chunk is a basic physical attribute of the flash devices. For example, NAND flash devices physically read and write data in chunks of 512 bytes. Even if there is only a need for reading a single byte, it is still necessary to read 512 bytes from the flash array into an internal buffer within the flash chip, and then access the single desired byte. As a result, using sectors of 512 bytes is relatively efficient in operating systems accessing file systems residing on such flash disks. The flash management systems mentioned above all operate in this way.
Recently, however, there have been announcements of major flash vendors of future devices in which the basic chunk for reading and writing will no longer have basic reading/writing chunk sizes of 512 bytes, but rather have larger size chunks. One such example is Samsung (www.samsung.com—23Fl.-Ka, Taepyung-ro, Chung-gu, Seoul, Korea), who have announced their future K9F1G08U0M-YCB0 1 Gbit device, which has a 2 Kbyte basic read/write page size. Toshiba (www.toshiba.com—Toshiba Corporation, 1—1 Shibaura 1-chome Minato-ku, Tokyo 105-8001, Japan) also announced that it will offer a similar device soon. As the operating systems that will use these devices will still remain based on 512 bytes logical sectors, some performance and/or reliability problems might arise. For example, assume that the OS instructs the flash management system to write 4 data sectors that share the same physical page. Since the write requests are dictated by the requirements of the SW application, we cannot rely on the 4 sectors being written together, and in many cases they will not. Therefore these write requests will typically be executed in 4 separate calls. In the previous situation (of 512 bytes pages), as can be seen in
FIG. 1
, there is no interference between the 4 write commands, and each sector will be written into a separate flash page independently of the others. However, in the 2K-page case, the 4 sectors share a physical page, and it might not be allowed to write 4 times to the same page without erasing it, thus making the trivial solution of simply writing 4 times into the same page unacceptable. For example, the Samsung device mentioned above only guarantees 3 write operations (known in the technical literature as “Partial Page Programming” or “PPP”) before having to erase the page. Of course, it is possible to achieve the above write actions by never writing twice into the same page, and for each request of writing a sector into a page already containing another sector, designate a new page, and write both new and existing data into it. However, this method, as can be seen in
FIG. 2
, will result in terrible performance hit. In the above example of writing 4 sectors into the same page, if they arrive one by one, the logic of this brute-force method of avoiding the violation of the PPP spec will lead to the following sequence of events:
a. First sector write request arrives
b. Data of first sector is written into first page
c. Second sector write request arrives
d. A second page is designated, first sector is read from first page, and data of first and second sectors is written into second page
e. Third sector write request arrives
f. A third page is designated, first and second sectors are read from second page, and data of first second and third sectors is written into third page
g. Fourth sector write request arrives
h. A fourth page is designated, first second and third sectors are read from third page, and data of all four sectors is written into fourth page
Therefore, one sector will be written 4 times, another sector 3 times, still another two times, and only the last to be written is written once (without mentioning the extra read operations needed for copying the previously existing sectors into their new locations).
Therefore there is c
Friedman Mark M.
Kim Hong
M-Systems Flash Disk Pioneers Ltd.
LandOfFree
Flash management system for large page size does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flash management system for large page size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flash management system for large page size will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3188187