Flash real-time operating system for small embedded applications

• US 7,571,275 B2
• Filed: 08/31/2005
• Issued: 08/04/2009
• Est. Priority Date: 08/31/2005
• Status: Active Grant

• Current Assignee: Hamilton Sundstrand Corporation (Raytheon Technologies Corporation d/b/a RTX)
• Original Assignee: Hamilton Sundstrand Corporation (Raytheon Technologies Corporation d/b/a RTX)
• Inventors: Nelson, Les
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): BRADLEY, MATTHEW A
• Application Number:
  US11/216,749
• Publication Number:
  US 20070050535A1
• Time in Patent Office: 1,434 Days
• Field of Search: 711/103
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks

Abstract

A flash real time operating system for embedded applications employing flash memory is capable of storing and accessing individual bytes of data corresponding to a particular logical address in real time. The operating system writes data bytes to sequential physical blocks within the flash memory. Physical blocks written with data bytes corresponding to the same logical address are connected by a linked list, which is dynamically modified to reduce access times required to read and write data to the flash memory. The operating system also monitors the number of physical blocks written with data within each physical sector. When one physical sector reaches its storage capacity, the operating system transfers the physical blocks holding valid data from the old physical sector to a new, previously erased physical sector.

Claims

1. A byte-oriented method of utilizing flash memory, the byte-oriented method comprising:

writing a new byte of data corresponding to a first logical address to a current physical block in the flash memory identified by location data stored to a write pointer;

writing the location data stored by the write pointer to a frame vector area of a first previous physical block written with data bytes corresponding to the first logical address if a first number of intervening physical blocks between the first previous physical block and the current physical block have been written with data bytes corresponding to the first logical address;

writing the location data stored by the write pointer to a standard vector area of a second previous physical block written with data bytes corresponding to the first logical address if the first number of intervening physical blocks have not been written with data bytes corresponding to the first logical address, wherein writing the location data to either the frame vector area or the standard vector area results in the current physical block being added to a dynamic linked list of physical blocks written with data bytes corresponding to the first logical address; and

incrementing the location data stored to the write pointer to identify an unwritten physical block immediately following the current physical block.

2. The byte-oriented method of claim 1, further including:

writing the location data stored by the write pointer to a super-frame vector area of a third previous physical block written with data bytes corresponding to the first logical address if a second number of intervening physical blocks between the third previous physical block and the current physical block have been written with data bytes corresponding to the first logical address.

3. The byte-oriented method of claim 1, further including:

locating a most recently written physical block written with current data bytes corresponding to the first logical address.

4. The byte-oriented method of claim 3, further including:

reading a current byte of data located within the most recently written physical block based on a particular logical address selected from a range of logical addresses including the first logical address.

5. The byte-oriented method of claim 3, further including:

selecting from the current data bytes valid data bytes written to the most recently written physical block and corresponding to logical addresses not being updated by the new byte of data being written with respect to the first logical address, and

adding the valid data bytes to the new byte of data to be written to the current physical block to ensure the valid data bytes corresponding to the logical addresses not being updated are retained when writing the new byte of data corresponding to the first logical address to the current physical block.

6. The byte-oriented method of claim 3, wherein locating a most recently written physical block written with data bytes corresponding to the first logical address includes:

a. locating a first physical block written with data bytes corresponding to the first logical address based on the first logical address, wherein the first physical block represents a beginning of the dynamic linked list corresponding to the first logical address;

b. accessing the first physical block written with data corresponding to the first logical address, wherein the first physical block becomes a currently accessed physical block;

c. locating a first intervening physical block in the dynamic linked list written subsequent to the currently accessed physical block and corresponding to the first logical address based on values stored in the frame vector area of the currently accessed physical block;

d. accessing the first intervening physical block written with data bytes corresponding to the first logical address, wherein the first intervening physical block becomes the currently accessed physical block;

e. repeating steps ‘

c ’ and

‘

d ’

until the frame vector area of the currently accessed physical block has no values in the frame vector area;

f. locating a second intervening physical block in the dynamic linked list written successively after the currently accessed physical block and corresponding to the first logical address based on values stored in the standard vector area of the currently accessed physical block;

g. accessing the second intervening physical block written with data bytes corresponding to the first logical address, wherein the second intervening physical block becomes the currently accessed physical block; and

h. repeating steps ‘

f ’ and

‘

g ’

until the standard vector area of the currently accessed physical block contains no values stored in the standard vector area, wherein when the standard vector area of the currently accessed physical block contains no values, then the currently accessed physical block is the most recently written physical block corresponding to the first logical address.

7. The byte-oriented method of claim 1, further including:

monitoring how many physical blocks within a first physical sector are written with data bytes, wherein the first physical sector is assigned to a first logical address range; and

transferring valid data bytes written to the first physical sector to a second physical sector when a number of physical blocks written to the first physical sector exceeds a threshold value.

8. The byte-oriented method of claim 7, wherein transferring valid data bytes from the first physical sector to a second physical sector includes:

assigning the first logical address range to the second physical sector;

writing new data corresponding to logical addresses within the first logical address range to physical blocks within the second physical sector;

locating valid physical blocks within the first sector having valid data written with respect to each of the logical addresses within the first range of addresses; and

transferring the valid data located in the valid physical blocks written with respect to each of the logical addresses within the first logical address range to the physical blocks within the second physical sector.

9. A method of utilizing flash memory, the method comprising:

assigning logical address ranges to physical sectors, wherein each of the logical address ranges is assigned to one of the physical sectors, and wherein the physical sectors outnumber the logical address ranges resulting in some of the physical sectors being unassigned;

writing data bytes corresponding to a logical address range to physical blocks located within an assigned physical sector, wherein a set of physical blocks written with data bytes corresponding to a particular logical address within the logical address range are connected by a dynamic linked list corresponding to the particular logical address;

monitoring how many of the physical blocks within the assigned physical sector have been written with data;

assigning the logical address range to the new physical sector;

transferring valid data bytes stored in the physical blocks within the assigned physical sector to a new physical sector when the physical blocks within the assigned physical sector written with data exceeds a threshold value; and

erasing the assigned physical sector after valid data bytes have been transferred from the assigned physical sector to the new physical sector.

10. The method of claim 9, wherein writing data bytes corresponding to a logical address range to physical blocks located within an assigned physical sector includes:

writing current data bytes corresponding to a first logical address within the logical address range to a first physical block identified by location data stored in a write pointer;

adding the first physical block to a first linked list corresponding to the first logical address; and

incrementing the location data stored in the write pointer to identity a next available unwritten physical block.

11. The method of claim 10, wherein adding the first physical block to a first linked list corresponding to the first logical address includes:

linking the first physical block to a first previously written physical block if a first number of intervening physical blocks have been written with respect to the first logical address;

linking the first physical block to a second previously written physical block if the first number of intervening physical blocks has not been written and a second number of intervening physical blocks has been written with respect to the first logical address; and

linking the first physical block to a third previously written physical block if the first and second number of intervening blocks has not been reached.

12. The method of claim 9, further including accessing a most recently written physical block corresponding to the particular logical address using the dynamic linked list, wherein accessing the most recently written physical block includes:

a. locating a first physical block written with data corresponding to the particular logical address based on the particular logical address, wherein the first physical block represents a beginning of the linked list corresponding to the particular logical address, wherein the first physical blocks becomes a current physical block;

b. accessing a first subsequent physical block written with respect to the particular logical address based on location data stored to a first vector area of the current physical block, wherein the first subsequent physical block and the current physical block are separated by a first number of intervening physical blocks written with respect to the particular logical address, and wherein the first subsequent physical block becomes the current physical block;

c. repeating step ‘

b’

until the current physical block has no location data stored in the first vector area;

d. accessing a second subsequent physical block written with respect to the particular logical address based on location data stored to a second vector area of the current physical block, wherein the second subsequent physical block and the current physical block are separated by a second number of intervening physical blocks written with respect to the particular logical address, and wherein the second subsequent physical block becomes the current physical block;

e. repeating step ‘

d’

until the current physical block has no location data stored in the second vector area;

f. accessing a third subsequent physical block written with respect to the particular logical address based on location data stored to a third vector area of the current physical block, wherein the third subsequent physical block is written successively after the current physical block, and wherein the third subsequent physical block becomes the current physical block; and

g. repeating step ‘

f’

until the current physical block has no location data stored in the third vector area, wherein when the current physical block has no location data stored in the third vector area, the current physical block represents the most recently written physical block written with respect to the particular logical address.

13. The method of claim 9, wherein transferring valid data bytes stored in the physical blocks within the assigned physical sector to a new physical sector when the physical blocks within the assigned physical sector written with data exceeds a threshold value includes:

a. assigning the logical address ranges to the new physical sector;

b. accessing a current physical block most recently written with data bytes corresponding to a current logical address identified by a sector transfer pointer if data bytes corresponding to the current logical address have previously been written to the first sector;

c. writing data bytes stored in the current physical block corresponding to the current logical address identified by the sector transfer pointer to a new physical block located within the second physical sector;

d. incrementing the sector transfer pointer to identify a next logical address to be transferred, wherein the next logical address becomes the current logical address; and

e. repeating steps ‘

b’

through ‘

d’

until data bytes corresponding to each logical address has been transferred.

14. An embedded system, comprising:

a flash memory comprising a plurality of physical sectors, each of the plurality of physical sectors including a plurality of physical blocks and a block index;

a controller connected to the flash memory and running an operating system, wherein the operating system includes;

means for writing new data corresponding to a first logical address to a current physical block in a first physical sector of the flash memory identified by location data stored to a write pointer;

means for storing the location data stored by the write pointer to an area of the block index corresponding to the first logical address if data corresponding to the first logical address has not been previously written to this sector;

means for storing the location data stored by the write pointer to a previously written physical block holding data corresponding to the first logical address if data corresponding to the first logical address has been previously written to the physical sector, wherein each of the plurality of physical blocks includes a frame vector area to store a first location of a subsequently written physical block and a standard vector area to store a second location of a successively written physical block such that physical blocks holding data corresponding to the first logical address are linked by a dynamic linked list; and

means for incrementing the location data stored by the write pointer to identify an unwritten physical block immediately following the current physical block.

15. The embedded system of claim 14, wherein the means for storing the location data:

writes the location of the current physical block to a frame vector area of a first previous physical block written with data corresponding to the first logical address if a number of intervening physical blocks between the first previous physical block and the current physical block have been written with respect to the first logical address; and

writes the location of the current physical block to the standard vector area of a second previous physical block if the threshold number of intervening physical blocks written with respect to the first logical address has not been reached.

16. The embedded system of claim 15, wherein the operating system further includes:

a means for locating a most recently written physical block corresponding to the first logical address;

a. uses location data stored in the frame vector area of a first physical block to locate subsequently written physical blocks corresponding to the first logical address and separated by a number of intervening physical blocks corresponding to the first logical address;

b. repeats step ‘

a’

until the frame vector area of a subsequently written physical block is located with no data in the frame vector area;

c. uses location data stored in the standard vector area to locate successively written physical blocks corresponding to the first logical address; and

d. repeats step ‘

c’

until the standard vector area of a successively written physical block is located with no data in the standard vector area, wherein the successively written physical block with no data in the standard vector area represents the most recently written data corresponding to the first logical address.

17. The embedded system of claim 14, wherein the operating system further includes:

means for transferring data from the first physical sector to a second physical sector when a number of physical blocks written to the first physical sector exceeds a threshold value.

18. The embedded system of claim 17, further including:

a sector transfer pointer initialized to a beginning of the block index, wherein the beginning of the block index represents a first logical address assigned to the physical sector, wherein the means for transferring data from the first physical sector to a second physical sector;

a. locates a most recently written physical block corresponding to a logical address identified by the sector transfer pointer if data bytes corresponding to the logical address have previously been written to the first sector;

b. writes data bytes stored in the most recently written physical block corresponding to the logical address identified by the sector transfer pointer to a new physical block located within the second physical sector;

c. increments the sector transfer pointer to identify the next logical address to be transferred; and

d. repeats steps ‘

a’

through ‘

c’

until data bytes corresponding to each logical address has been transferred.

19. The embedded system of claim 17, wherein said embedded system is part of a data memory module (DMM).

20. The embedded system of claim 19, wherein said embedded system is part of a DMM on an aircraft.