Ncr Corporation

Lsi Logic Corporation

At&t Global Information Solutions Company

Symbios, Inc.

Robert A DeMoss

Keith B DuLac

Mahmoud K Jibbe

Donald Roman Humlicek

Elmer A Hoyer

Merle E Furry

A method, system, and data structure for encoding a block of data with redundancy information and for correction of erasure type errors in the block using the redundancy data. In particular, the invention is particularly applicable to disk array storage subsystems which are capable of recovering from total or partial failures of one or two disks in the disk array. Still more specifically, the invention is applicable to RAID level 6 storage devices. A given data block of data is translated into a code block of n.sup.2 elements including 2n XOR parity elements for redundancy. Each code block is manipulated as a square matrix, of n.sup.2 elements with parity elements along the major diagonals of the matrix and data elements in the remainder of the matrix. Each parity element is a dependent variable whose value is the XOR sum of the (n-2) data elements in a minor diagonal which intersects it. If the elements in any one or two columns or one or two rows are erased, their values can be generated from the other elements in the matrix. The invention therefore allows for recovery from data loss resulting from complete failure of any one or two disks in the disk array. Further, since the invention recovers all erased elements in any one or two rows, it allows recovery from data loss resulting from correlated partial failure of all disks in the disk array. Still further, the invention allows recovery from many uncorrelated failure patterns in the storage domain of disk drives in a disk array.

Block coding method and system for failure recovery in disk arrays

Methods and associated apparatus for improving the fairness of bus allocation in association with standard SCSI bus arbitration. The present invention provide a plurality of time slots each of which define a delay period following the SCSI specified minimum period before arbitration is allowed to begin. Each device which requires arbitration on the SCSI bus pseudo-randomly selects one of the time slots before attempting SCSI bus arbitration. The device then delays the associated period of time before commencing SCSI bus arbitration. At any time before the end of the delay period, if the device senses that the SCSI bus has again become busy, then the device has already lost the arbitration without actually competing therefore. A second device, having selected a time slot with a shorter delay period, has won control of the SCSI bus before the first device attempted arbitration. The time slots are selected with a probability associated with each slot. To reduce the maximum added delay in arbitration, heuristic methods are applied to reduce the number of time slots and assign the probabilities to each slot for use by each SCSI. A first preferred embodiment assigns probabilities for up to seven SCSI devices sharing four time slots. A second preferred embodiment assigns probabilities for up to fourteen SCSI devices sharing five time slots. The methods of the present invention may be embodied in control programs operable within the SCSI devices or in mounting components (boards, cables and canisters) which physically and electronically connect the devices to a SCSI bus.

Method and apparatus for improving fairness in SCSI bus arbitration

A method and corresponding controller apparatus for creating, updating and maintaining mapping information in a virtual mass storage subsystem. A request to manipulate a virtual block or cluster identifies a particular virtual block number. The virtual block number is mapped to a first physical block number by a direct calculation. A header data structure contained in the first physical block contains mapping information to locate other physical blocks associated with the virtual cluster. In addition to the header data structure, the first physical block contains a portion of the stored data for the corresponding virtual cluster. Additional physical blocks which stored the data of the virtual cluster are located from the mapping information in the header of the first physical block. The methods of the present invention provide improved performance and reduced buffer memory requirements in the virtual mass storage controller circuits of the subsystem as compared to prior approaches.

Method for virtual to physical mapping in a mapped compressed virtual

A method for reducing the apparent response time for write I/O operations initiated by a host system to a RAID level 3, 4 or 5 disk array including a spare disk drive. The disclosed method comprises the steps of (1) saving write data received by the disk array from the host system directly to the spare drive, (2) issuing a write complete status signal to the host system indicating completion of the host write I/O operation, thus freeing the host processor to perform other functions, and (3) transferring the data saved to the spare drive to the active drives within the array. This third step may be executed at any convenient time following the second step. For example, in systems where a host processor functions as the array controller, this third step may be delayed while higher priority tasks are executed. In systems where the disk array includes an array controller, the array controller coordinates the execution of this third step with other controller or array operations to optimize array operation. In additiona, the data from multiple write I/O opertions may be accumulated to the spare drive prior to the step of transferring the data saved to the spare drive to the other, active, drives within the array.

Fast write I/O handling in a disk array using spare drive for buffering

An improved method for updating data and parity information in a RAID level 4 or 5 disk array employing a read-modify-write (RMW) process for updating data and parity information. During normal RMW operations, the old data and old parity information to be updated are read from disk, new parity is generated, and the new parity information and new data written to disk. The improved RMW method separates the execution of data read and write operations from the execution of parity read, generation and write operations to permit greater efficiency in the utilization of the drives within the array. The method identifies the disk drives containing the data and parity to be updated and places the proper read and write requests into the I/O queues for the identified data and parity drives, scheduling parity operations; i.e. reading old parity information from the parity drive, generating new parity information and writing the new parity information to the parity drive; for execution when best accommodated in the I/O queue for the parity drive, following the read of old data from the data drive.

Delayed initiation of read-modify-write parity operations in a raid

An encoder and a decoder is provided with each being usable independently of each other for improving the dynamic range of clipped speech digital systems by providing amplitude components to the clipped digital signal. The encoder processes an audio input signal along two signal paths, the first signal path including a clipper and digitizer means for forming a digitized clipped signal. The second signal path includes a rectifier, envelope detector and digitizing means for forming a digitized signal having amplitude components. Both digitized signals may then be transmitted to the decoder for reconstruction or stored for reconstruction at a later time.

Growing community of inventors

Wichita, KS, United States of America

Robert A DeMoss