Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-04-19
2003-03-18
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S159000, C707S793000, C707S793000
Reexamination Certificate
active
06535949
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is directed to the field of data storage and retrieval in portable electronic devices typically having limited processing and memory capabilities, such as two-way wireless paging computers, PDAs, P/PCs, H/PCs, etc. More particularly, the present invention provides a portable electronic device having a software-implemented log-structured file system for storing and retrieving data from an electrically-erasable flash memory store. The system preferably stores data in at least one log as a plurality of contiguous variable-length records. The invention also provides memory mapped pointer access to the individual data records. Alternatively, certain implementations of the invention provide: (1) a plurality of logs for storing records that change at different relative frequencies in order to improve system performance; and (2) storing multiple versions of the data records in the log.
2. Description of the Related Art
Portable electronic devices are typically characterized by limited electrical power, limited processing capability and limited storage capacity. Since these devices are portable, they must also be light-weight and small. Thus, it is desirable to provide such a portable electronic device with a memory storage medium that is low power, small in size, high-capacity, and rugged. Semi-conductor chip memories have proven useful in meeting these requirements.
Particularly useful for this application is flash memory. Flash memory is a type of electrically-erasable programmable read-only memory. Flash is a non-volatile memory characterized by a plurality of memory cells implemented with a floating-gate field effect transistor (“FET”). An electrical charge can be permanently trapped on the floating gate of the FET, thus effecting a write operation to the memory cell. Trapping a charge on the floating gate (“programming”) requires only modestly more time than charging the gate of an FET used in dynamic random access memory (“RAM”), and requires no special control circuitry. However, removing the trapped charge (“erasing”) takes significantly longer for flash, and requires expensive on-chip circuitry. In currently available flash memories, this erase time may be as much as two orders of magnitude slower than the programming time. As a result, flash manufacturers provide a fine-grain mechanism for imparting charges to the floating gate, perhaps as small as a few bytes at a time, and a coarse-grain mechanism for removing charge from the floating gate, perhaps a block of many kilobytes.
Presently known portable electronic devices have file systems that store data in a flash memory using intermediate block-sized RAM buffers to store active data (i.e., the RAM buffer is at least as large as one block of flash memory). Updates to the data are performed in the RAM buffer. Reads are performed by accessing the RAM buffer. Periodically, the contents of the RAM buffer replaces the contents of the particular flash memory block to which it is temporarily referenced. Another flash block can then be read into the RAM if different data becomes active.
These types of portable electronic devices suffer from many disadvantages. First, these systems are prone to lose data. If important data is stored in the RAM buffer (a volatile storage media) and has not been programmed into the flash device, and power is lost, then the important data is also lost. In order to cure this problem, these devices must flush the RAM buffer(s) to flash memory before committing a transaction, and as a result they typically flush the RAM buffer(s) at frequent rates. But this results in low write-efficiency to the flash memory since a buffer flush requires an erase step and a programming step for the entire flash block. The frequency of flushing the buffer may additionally result in shorter lifetime for the flash, which degrades as the number of erases increases. Secondly, a large amount of RAM is required in these systems since current flash memory devices include large block sizes, typically on the order of 64 Kbytes or greater. The overhead cost in accessing the flash through RAM buffers also extends to applications operating on the portable device. These applications must also maintain RAM buffers in order to read and write to the RAM buffers in the file system. Thus even more RAM is required to support the file system. More RAM results in increased cost and size of the portable electronic device. And finally, these devices typically exhibit low read efficiency because of the overhead in calling the operating system, performing a context switch, possibly changing protection domains, and in trying to decide if the most up to date copy of the data is in RAM or the flash memory.
Therefore, there remains a general need in this field for a portable electronic device having a data storage and retrieval system for storing data in flash memory that overcomes the many disadvantages of the presently known devices.
SUMMARY OF THE INVENTION
A portable electronic device is provided that includes a log-structured file system implemented in flash memory. The log-structured file system preferably includes a write function for storing contiguous data records to the flash memory in the form of at least one data log, although alternatively, the system may write data records to the flash memory using a plurality of data logs that may be arranged in parallel, hierarchically, or both. The data records are preferably linked together in a linked-list structure, including a record header for maintaining link data, and the linked records may further form a plurality of files that may also be linked together in a linked-list structure. The log-structured file system also preferably includes a read function for retrieving data records from the one or more logs using a plurality of memory mapped pointers, which may be stored in an associated RAM index, or which may be implemented as an index stored in the flash memory. A clean-log function is also provided for eliminating inactive records from the log so that new data can be added.
The various functions included with the log-structured file system are preferably implemented as at least three software modules, a read module, a write module and a clean-log module, although other modules and configurations are possible. The portable electronic device may further include a two-way RF transceiver for sending and receiving data from the device, and may also include a plurality of application programs that are configured to interact with the log-structured file system and as other software modules for controlling the operation of the portable electronic device.
According to one aspect of the invention, a portable electronic device is provided that includes a microprocessor, an electrically erasable flash memory store, a two-way radio-frequency transceiver, and a log-structured file system for storing data in the flash memory store. In this aspect of the invention, the log-structure file system includes: (a) a write software module for writing data to the flash memory as a sequence of contiguous records; (b) a read software module for reading data from the flash memory using a plurality of memory mapped pointers into the flash memory store; and (c) a clean-log software module for cleaning inactive records from the flash memory store in order to make room for additional data. The microprocessor preferably executes the software modules of the log-structured file system in order to write data to the flash memory, read data from the flash memory, and clean inactive records from the flash memory, and also controls sending and receiving data from the portable electronic device via the two-way radio-frequency transceiver.
Another aspect of the invention provides a portable electronic device including a log-structured file system for storing a log of contiguous data records in a flash memory store, and for reading data from the flash memory store using a plurality of memory mapped pointers that reference the individual data records. Additionally,
Choi Woo H.
Jones Day
Kim Matthew
Meyer, Esq. Charles B.
Pathiyal, Esq. Krishna K.
LandOfFree
Portable electronic device having a log-structured file... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Portable electronic device having a log-structured file..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Portable electronic device having a log-structured file... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016209