International Computers Limited

Albert Stephen Hilditch

Ian Gregory Colloff

Colin Michael Thomson

Nasser Siddiqi

Steve Robert Pettifer

A distributed data processing system has a deadlock detection mechanism for detecting a potential deadlock involving a cyclic chain of dependencies between transactions. The system also has a deadlock doublechecking mechanism for confirming that all the dependencies in the potential deadlock chain are co-existent. If deadlock is confirmed, action is taken to break the deadlock. The deadlock doublechecking mechanism operates by marking the dependencies in the cyclic chain with a unique existence number, and subsequently checking that the existence number of each dependency in the cyclic chain is unchanged. Marking the dependencies may be performed by propagating a probe message, containing a unique probe existence number, and associating this probe existence number with each dependency visited by said marker probe.

Deadlock detection mechanism for data processing system, with doublechecking to confirm that detected deadlock is non-spurious

An n-way set-associative cache (where n is an integer greater than 1), includes a replacement mechanism for selecting a cache line for replacement. Each cache line has an associated priority tag indicating a user-defined priority for that cache line The replacement mechanism comprises an apparatus for selecting a cache line with the lowest user-defined priority in a current set of cache lines, and apparatus (e.g. based on recency of usage) for choosing between cache lines of equal priority if there is more than one cache line with said lowest user-defined priority in the current set.

Cache replacement mechanism

A RAID system includes an array of disk units, with data mapped on to the disks as a series of stripes, each containing data and parity chunks. The data chunks of each stripe are located on radially more outer parts of the disks and the parity chunks of each stripe are located on radially more inner parts of the disks. As a result, the amount of head movement for read operations is reduced, which improves the read performance. Successive chunks within each stripe are physically located at successively more radially inward positions on successive disks, so that each stripe has a helical configuration. Mirroring can be considered as a special case in which the number of data chunks is equal to the number of parity chunks, and the parity consists of a simple replication of the data. In this case, data is written to the outermost half of a first disk and to the innermost half of a second disk, and is read from the first disk.

Disk array with parity data storage on the radially inner part of each

Each node of a distributed (multi-node) data processing system, which includes a plurality of shared data storage disks, has a respective incremental backup bit-file containing one bit for each datablock of the shared disks. The bits are initially set to logical 0. When a node writes data to a datablock the respective bit is reset to logical 1. Upon an incremental backup requirement, one node reads all of the bit-files, forms the logical OR thereof and forms a respective new bit-file. The blocks whose bits equal 1 in this new bit-file are then backed up. The bit-files are stored in the node main memories for quick access and will be lost upon node failure. However if a redo log is maintained, bit-files can be reconstructed.

Incremental disk backup

A cache memory contains a number of RAMs. The RAMs are addressed by independent hashing functions, so as to access a set of locations, one in each RAM. If the required data item is resident in the addressed set, it is accessed. Otherwise, the least-recently used location in the set is selected for overwriting with data from main memory. The contents of the RAM location that is about to be overwritten are saved, and then used to access the memory again in order to address a further set of locations. If any of this further set of locations is less recently used than the saved contents, the saved contents are loaded back into that location.

Growing community of inventors

Wokingham, United Kingdom

Albert Stephen Hilditch