Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-09-26
2001-01-09
Lintz, Paul R. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06173291
ABSTRACT:
TECHNICAL FIELD OF INVENTION
The invention pertains generally to methods and apparatus for recovering data files from mass data storage devices when file system information is corrupted or missing.
BACKGROUND OF THE INVENTION
The main components of a general purpose, programmable, digital computer, as illustrated by a representative computer
10
shown of
FIG. 1
, are a central processing unit (CPU) or processor
12
for manipulating data according to a program of instructions, and a main or working memory
14
for temporarily storing data, including program instructions. (The term “data” will be used generically, unless the context otherwise indicates, to mean any information in digital form stored by a computer, including, without limitation, program instructions, text, business data and commands.)
Most computers also include one or more mass or high capacity data storage devices for long term storage of data in the form of files. There are many types of mass data storage devices available, including, for example, magnetic and optical tape, magnetic, magneto-optical and optical disks, and solid state (e.g. flash memory). Most, but not all, of these devices and media are non-volatile; i.e. they do not require power to maintain long-term memory. Many can be written to one or more times. In addition to the basic, physical properties of their respective storage media, they differ in manner (sequential versus random) of access, speed of access, cost per unit of data storage and storage capacity, among other characteristics. The type of device selected often depends on the requirements for the particular computer. Unlike the main memory, which stores data in directly accessible small units, i.e. bytes, mass data storage devices are set up to receive and make data available to the CPU in comparatively large blocks. Mass data storage devices are treated as peripheral input/output (I/O) devices, meaning that they and/or their controllers are set up (in hardware, software or both) transfer data in relatively large (e.g. 512 byte) blocks.
Most modern computers utilize at least one or more magnetic disk media for high-capacity storage, as such media currently offers a good combination of speed of access, capacity and cost. In the representative computer of
FIG. 1
the mass data storage devices are a floppy disk drive
16
and its controller
18
, and hard disk drive
20
and its controller
22
. Conventionally, the floppy disk drive receives a removable flexible, magnetic disk
17
. The hard disk drive includes a stack of spatially-separated, stiff, magnetic platters, which are usually fixed, but may also be made removable. The controllers for the respective disk drives translate basic commands received from the CPU into the appropriate actions for that particular disk drive, and control the flow of data to and from the disk drives. Computers will often include other types of mass data storage devices, such as CD-ROM drives and tape drives.
In addition to mass data storage devices, the computer
10
also includes various other peripheral components or I/O devices with which the CPU communicates, including, for example, a keyboard
24
, a video monitor
26
and its graphics adapter
28
. In the simplest form of the computer
10
, the CPU, main memory, the mass data storage devices and the I/O devices communicate over a single system bus, which is designated
30
in the figure. However, most computers use more complex types of bus arrangements for enabling communication between the CPU, the main memory, and the various I/O devices.
There is also a separate, non-volatile, solid state read-only memory
32
for storing what is referred to as the “BIOS” or “Basic Input/Output System,” which is permanently resident software, separate from an operating system. The BIOS software routines, when executed by the CPU, translate certain “calls” from an executing program wanting to access an I/O device, whether it be an operating system or an application program, into a sequence of commands that are provided, or stored in registers of, a particular I/O device or its controller for execution by the controller. By segregating hardware-dependent I/O device access routines from other programs running on the computer, higher level programs, such as operating systems and applications programs, need not be written for specific computer hardware, allowing at least some level of compatibility among different hardware systems. The BIOS also includes software for handling certain types of errors which occur with the I/O devices, as well as instructions for testing various components of the computer when it is powered up and loading an operating system from a disk drive.
Disk drives are physically addressed by the BIOS using a cylinder, head and sector number. A typical hard disk includes multiple platters rotating on a common axis. On each side of each platter are arranged concentric tracks. Tracks having the same diameter or radius lie within a “cylinder.” Each side of each platter is read and written to by a separate a read/write head which moves across the tracks. The head and cylinder numbers uniquely identify a track, and the sector number uniquely identifies one of the sectors within a tract. The cylinder, head and sector (“C,H,S”) address 0,0,1 is always occupied by a partition sector. Hard disks for may be used by a computer to store more than one operating system, which means that more than one type of file system may be used to store files on a hard disk. A hard disk is therefore partitionable into multiple “drives” or “volumes.” The partition sector stores a table specifying the start and end of each partition, or a link to the next partition, as well as some other basic information about the disk. Most operating systems address sectors using a logical block address rather than the C, H, S address. A logical block address (LBA) is a sequential numbering of the sectors within a partition or drive. It is one of the BIOS' functions to translate between the LBA and a physical C,H,S address.
As previously mentioned, data is organized for storage into files. Depending on the size of the file and the size of the sectors in the storage device in which it is stored, files may be stored over one or more sectors of the storage device. It is the job of an operating system, particularly its file system, keep track of what files are stored, and where they are stored, in the storage device. Generally, this file information is also stored in the same device as the files. Some of the information is typically stored in designated sectors or areas set aside for that purpose.
Each operating system has a different file system. The File Allocation Table (FAT) file system is the native file system for IBM-standard personal computers running the MS-DOS®, Windows™ 3.x and Windows™ 95 operating systems of Microsoft Corporation, and it is supported by Microsoft Corporation's Windows-NT. The FAT file system was originally developed for small capacity, floppy disks, but has been extended to be used for today's very large capacity disk drives. The FAT file system has several versions. The ones used by earlier versions of the MS-DOS and Windows 3.x operating systems are generally referred to as the FAT-12 and FAT-16 file systems. Microsoft WINDOWS 95 supports FAT-12, FAT-16 and a 32 bit version called FAT-32. Microsoft Corporation's Windows NT™ operating system utilizes a native file system known NTFS, or New Technology File System, and also supports the HPFS file system developed by IBM for the OS/2® operating system. These systems share, to varying degree, a similar approach to managing files on the disks.
FIGS.
2
a
and
2
b
illustrate, respectively, examples of how the FAT-16 and FAT-32 file systems organize data on a hard disk or other mass data storage device. Each has a partition sector
34
a
starting at C,H,S=0,0,1. (A floppy disk is generally not partitionable, and therefore has no partition sector.) Following each partition sector, there is a bootstrap sector, which starts at a fixed locat
Fleurantin Jean Bolte
Hubbard Marc A.
Lintz Paul R.
PowerQuest Corporation
LandOfFree
Method and apparatus for recovering data from damaged or... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for recovering data from damaged or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for recovering data from damaged or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556019