Queueing device for the selection of requests for access to a storage medium

Claim 2

A queueing device for use with at least a single cyclical storage medium for selecting the optimum request for execution from a queue of such requests based on minimum latency time comprising means for converting each of said requests to information conveying the desired physical shaft position of said cyclical storage medium, means associated with said storage medium for providing information as to the actual shaft position thereof at any given time, means operatively connected to receive concurrently said desired and actual shaft positions and for generating therefrom a delta value indicative of the difference in said positions, said latter means being further adapted to continuously and repetitively generate delta values for all of said requests and for retaining the smallest delta value generated consistent with a predetermined threshold, said smallest delta value representing said optimum request for execution.

Claim 3

A queueing device as defined in claim 1 wherein said cyclical storage medium is a magnetic disk, each face of said disk being divided into a predetermined number of annular zones each having a plurality of tracks, each track comprising a plurality of segments which represent the smallest addressable units of data on said face, each of said segments being designated by an address number, a queuer timing track on each disk face having recorded thereon a plurality of sector marks in uniform spaced-apart relation commencing from a disk revolution timing point which serves as a reference.

Claim 4

A queueing device as defined in claim 2 wherein said means for providing information as to the actual shaft position of said magnetic disk comprising magnetic sensing means disposed in proximity to said disk face for reading said sector marks, and counter means coupled to said sensing means for accumulating the number of sector marks read by said sensing means during each disk revolution, the accumulated number of sector marks in said counter means representing at any given time the time equivalent of the actual angular disk shaft position with respect to said timing point, circuit means responsive to said sensing means for generating a clear pulse at the end of each disk revolution and for applying said clear pulse to said counter means to effect the resetting thereof.

Claim 5

A queueing device as defined in claim 3 wherein said request includes the disk address, the latter being a member of an address continuum ranging in value from zero to a number equal to the number of disk segments minus one.

Claim 6

In a data processing system having at least one cyclical storage means, a queueing device comprising a memory for storing access requests to said cyclical storage means, means for converting said access requests into corresponding desired physical shaft positions for said cyclical storage means, each of said storage means having a plurality of sector marks recorded thereon at uniformly spaced predetermined intervals, sensing means for continuously detecting the presence of said sector marks commencing with a reference point on said storage means, counter means coupled to said sensing means for providing a count at any given time of the number of sector marks which have been detected relative to said reference point, actual shaft position register means for storing said count, the accumulated number of sector marks representing the time equivalent of the actual shaft position of said cyclical storage means with respect to said reference point, said sensing means including means for resetting said counter means at the completion of each cycle of said storage means, delta generator and comparator means operatively connected to receive said desired shaft positions corresponding to said access requests and the actual shaft positions from said actual shaft position register means, said delta generator and comparator means comparing said desired position with said actual shaft position and generating a delta value representing the difference between the two positions, register means included within said delta generator and comparator means for storing delta values and the memory address of the corresponding requests, said delta generator and comparator means performing a continuous and repetitive evaluation of the deltas of all of the corresponding access requests stored in said memory, whereby at any given time said last-mentioned register means store the smallest delta value corresponding to the optimum access request from the standpoint of minimum latency, and the corresponding address in memory of said request.

Claim 7

In a data processing system having at least one cyclical storage means, a queueing device comprising a memory for storing access requests to said cyclical storage means, means for converting said access requests into corresponding desired physical shaft positions for said cyclical storage means, each of said storage means having a plurality of sector marks recorded thereon at uniformly spaced predetermined intervals, sensing means for continuously detecting the presence of said sector marks commencing with a reference point on said storage means, counter means coupled to said sensing means for providing a count at any given time of the number of sector marks which have been detected relative to said reference point, actual shaft position register means for storing said count, the accumulated number of sector marks representing the time equivalent of the actual shaft position of said cyclical storage means with respect to said reference point, said sensing means including means for resetting said counter means at the completion of each cycle of said storage means, delta generator and comparator means operatively connected to receive said desired shaft positions corresponding to said access requests and the actual shaft positions from said actual shaft position register means, said delta generator and comparator means comparing said desired position with said actual shaft position and generating a delta value representing the difference between the two positions, register means included within said delta generator and comparator means for storing delta values and the memory address of the corresponding requests, said delta generator and comparator means performing a continuous and repetitive evaluation of the deltas of all of the corresponding access requests stored in said memory, whereby at any given time said last-mentioned register means store the smallest delta value corresponding to the optimum access request from the standpoint of minimum latency, and the corresponding address in memory of said request.

Claim 8

A queueing device as defined in claim 5 wherein said cyclical storage means is a magnetic disk, each face of said disk being divided into a predetermined number of annular zones each having a plurality of tracks, each track comprising a plurality of segments, each of said segments being designated by distinct address numbers.

Claim 9

A queueing device as defined in claim 6 wherein each of said access requests includes the disk address which is a member of an address continuum ranging in value from zero to a number equal to the total number of disk segments minus one.

Claim 10

A queueing device as defined in claim 7 wherein said means for converting said access requests into corresponding physical shaft positions for a magnetic disk comprises arithmetic address converter means for deriving from said disk address the identification of the actual address number of the desired segment as counted from said reference point, said arithmetic address converter means further converting said address number of said desired segment into the corresponding shaft position of said magnetic disk taking into account the physical parameters of the disk and the zone of the address number, said last mentioned shaft position representing an angular address point measured from said disk reference point and being expressed in terms of a number representing the sector marks which would have to pass said sensing means as counted from said reference point, said delta generator and comparator means utilizing said number representing the desired address point on the disk face in combination with the actual disk position number also expressed in terms of accumulated sector marks, for valid latency comparison of different requests stored in said memory.

Claim 11

A queueing device as defined in claim 8 wherein said arithmetic address converter means comprises an accumulator, means for reading out the disk address number stored in said memory and for placing the disk address in said accumulator to initiate a multiradix conversion phase, an adder/subtractor operatively connected to said accumulator for performing successive subtractions on said disk address number, said subtraction utilizing as parameters the number of segments present in each disk face, track and zone wherein each of said parameters is successively subtracted from said disk address number to determine the desired disk face, track, zone and segment number, decoding phase and timing controls coupled to said adder/subtractor for providing count pulses indicative of the subtractive steps required for each of said parameters, output counter/register means operatively connected to said phase and timing controls for storing said count pulses which provide information as to the desired disk face, track and zone, said accumulator storing at the termination of said multiradix conversion phase the acTual address number of the desired segment as counted from said reference point, said arithmetic address converter further performing a multiplication process in a segment number-to-time conversion phase, control counter means for directing said multiplication process, configuration and parameter section means operatively connected to provide information as to the characteristics of the disk being utilized, means for selecting a suitable multiplication factor based upon said disk characteristics and the zone information derived in said multiradix conversion phase, said multiplication factor being equal to the number of sector marks which can be contained in an arc equivalent to that subscribed by said desired segment, means for multiplying the actual address number of said desired segment with said multiplication factor, the product of said multiplication being a converted segment number representing the number of sector marks from said reference point of the disk to the desired disk access point, and providing a measure of desired absolute shaft position.

Claim 12

A queueing device as described in claim 9 wherein said arithmetic address converter also includes a segment register for storing the converted segment number content of said accumulator at the end of said segment number-to-time conversion phase, said converted segment number being expressed in binary coded decimal format, means for causing end-around shifting of the segment number stored in said segment register to execute a binary coded decimal-to-binary conversion phase.

Claim 13

A queueing device as defined in claim 7 wherein said delta generator and comparator means comprises an adder/subtractor, means for reading said desired and actual shaft position information into said adder/subtractor, the latter performing a subtraction of the actual shaft position from the desired shaft position, a positive remainder from the subtraction representing a new delta value, a negative remainder being indicative of a condition wherein the delta spans said reference point, said adder/subtractor being responsive to such condition by performing a subtraction of said actual shaft position from the total number of sector marks appearing on said disk face and further performing an addition of the remainder of said last mentioned subtraction to said desired shaft position to produce said new delta value, said delta generator and comparator means further comprising a delta optimizer subtractor for subtracting said new delta value from the previous delta value stored in said delta generator and comparator register means, and logic means operatively connected to the output of said delta optimizer subtractor for testing whether the new delta value exceeds a predetermined threshold and is in fact a valid delta.

Claim 14

In an electronic computer having as a subsystem at least a storage unit including a plurality of rotating storage means, electronic unit means connected to said storage unit for effecting the storage and retrieval of information therefrom and control unit means operatively connected to and controlling the operation of said electronic unit means, at least one queueing device comprising a queuer stack for storing control words which represent access requests to read from or write into said rotating storage means, a queuer stack register operatively connected to said queuer stack for receiving control words to be written into or read from said queuer stack, stack control means operatively connected to said queuer stack for providing overall supervision of the writing into and reading from said queuer stack, said stack control means including a top-of-the-stack register and a queuer address register, said top-of-the-stack register providing an indication of the extent to which the queuer stack is occupied by registering the topmost occupied position of the stack, means for decrementing the top-of-the-stack register by one in response to the addition of each control word to the queuer stack, said queuer address register pRoviding a pointer to the queuer stack location of current interest in the queueing process, arithmetic address converter means coupled to said queuer stack register for receiving those portions of said control word which define the desired electronic unit means and the address of the storage means to be accessed, said arithmetic address converter means operating upon said last-mentioned address and converting it into the corresponding desired shaft position of the rotating storage means associated with said desired electronic unit means, means for storing the information representing said desired shaft position in said queuer stack register, actual shaft position counter and register means operatively connected for receiving information representing the actual shaft positions of said storage means, delta generator and comparator means operatively connected to receive said desired shaft position from said queuer stack register and said actual shaft position from said actual shaft position register means, said delta generator and comparator means including delta register means and queuer stack address register means, said delta generator and comparator means being adapted for comparing said desired and actual shaft positions and for generating a delta which represents the difference between the two positions, said delta generator and comparator means further comprising logic means for comparing said last-mentioned delta with the delta stored in said delta register means as a result of the preceding comparison of desired and actual shaft positions, the deltas of all of said control words being continuously and repetitively compared in like manner and the smallest delta consistent with a predetermined threshold value being considered the optimum and being retained in said delta register means, said queuer stack address register means storing the queuer stack address of the control word corresponding to said optimum delta, the optimum delta and its corresponding queuer stack address representing at any given time the access request in the queuer stack which has minimum acceptable latency and is therefore the best possible choice for the contemplated read or write operation.

Claim 15

In an electronic computer having as a subsystem at least a storage unit including a plurality of rotating storage means, electronic unit means connected to said storage unit for effecting the storage and retrieval of information therefrom and control unit means operatively connected to and controlling the operation of said electronic unit means, at least one queueing device comprising a queuer stack for storing control words which represent access requests to read from or write into said rotating storage means, a queuer stack register operatively connected to said queuer stack for receiving control words to be written into or read from said queuer stack, stack control means operatively connected to said queuer stack for providing overall supervision of the writing into and reading from said queuer stack, said stack control means including a top-of-the-stack register and a queuer address register, said top-of-the-stack register providing an indication of the extent to which the queuer stack is occupied by registering the topmost occupied position of the stack, means for decrementing the top-of-the-stack register by one in response to the addition of each control word to the queuer stack, said queuer address register pRoviding a pointer to the queuer stack location of current interest in the queueing process, arithmetic address converter means coupled to said queuer stack register for receiving those portions of said control word which define the desired electronic unit means and the address of the storage means to be accessed, said arithmetic address converter means operating upon said last-mentioned address and converting it into the corresponding desired shaft position of the rotating storage means associated with said desired electronic unit means, means for storing the information representing said desired shaft position in said queuer stack register, actual shaft position counter and register means operatively connected for receiving information representing the actual shaft positions of said storage means, delta generator and comparator means operatively connected to receive said desired shaft position from said queuer stack register and said actual shaft position from said actual shaft position register means, said delta generator and comparator means including delta register means and queuer stack address register means, said delta generator and comparator means being adapted for comparing said desired and actual shaft positions and for generating a delta which represents the difference between the two positions, said delta generator and comparator means further comprising logic means for comparing said last-mentioned delta with the delta stored in said delta register means as a result of the preceding comparison of desired and actual shaft positions, the deltas of all of said control words being continuously and repetitively compared in like manner and the smallest delta consistent with a predetermined threshold value being considered the optimum and being retained in said delta register means, said queuer stack address register means storing the queuer stack address of the control word corresponding to said optimum delta, the optimum delta and its corresponding queuer stack address representing at any given time the access request in the queuer stack which has minimum acceptable latency and is therefore the best possible choice for the contemplated read or write operation.

Claim 16

A queueing device as defined in claim 12 wherein said queuer stack for storing control words is a modular memory.

Claim 17

A queueing device as defined in claim 12 wherein said plurality of rotating storage means comprise a plurality of magnetic disks, each disk face being divided into a plurality of annular zones each having a plurality of tracks, each track comprising a plurality of segments, each of said segments having an address number commencing with the first track of the first zone of the first disk face and progressing to the first track of the last zone of said first disk face and then proceeding in like manner with the second through the last track of said first disk face and then from said first disk face through all of the disk faces of said magnetic disks to the last disk face in the last storage unit of said subsystem, whereby the highest disk address number refers to the last segment of the last track of the last zone on the last disk face of the last storage unit, a dead-space interposed between the last segment and the first segment in any given track, queuer timing tracks on the respective disk faces of said magnetic disks having recorded thereon in homologous fashion a plurality of sector marks in uniform spaced-apart relation commencing from a common fiducial point on the disk faces.

Claim 18

A queueing device as defined in claim 14 further comprising a magnetic read head positioned in proximity to each of said magnetic disks for reading said sector marks, each said storage unit including said actual shaft position counter means for accumulating the number of sector marks read by said read head during a disk revolution, said actual shaft position register means being operatively connected to said counter means for storing said accumulated count, said count representing tHe time equivalent of the actual angular disk shaft position with respect to said fiducial point, circuit means associated with said read head for generating a clear pulse during said dead-space and for applying said clear pulse to said counter means to effect the resetting thereof.

Claim 19

A queueing device as defined in claim 15 wherein each of said control words comprises the disk address which defines the desired electronic unit means and the desired storage unit, disk face, zone, track and segment, and further comprises the function code involved in the definition of the particular operation to be performed, and the memory link which points to an address in the main memory of said electronic computer wherein the disk operation is defined.

Claim 20

A queueing device as defined in claim 16 wherein said arithmetic address converter means comprises an accumulator, means for reading out the disk address portion of said control words and for placing said disk address in said accumulator to initiate a multiradix conversion phase, an adder/subtractor operatively connected to said accumulator for performing successive subtractions on said disk address, said adder/subtractor initially subtracting from said disk address a number equalling the segments per storage unit as the largest parameter, the subtraction involving said largest parameter taking place until the remainder is less than said parameter, said adder/subtractor performing similar operations on the successively smaller parameters namely, segments per disk face, track and zone, decoding phase and timing controls coupled to said adder/subtractor for providing count pulses indicative of the subtractive steps required for each of said parameters, output counter/register means operatively connected to said phase and timing controls for storing said count pulses which provide information as to the desired disk face, track and zone, said accumulator storing at the termination of said multiradix conversion phase the actual address number of the desired segment as counted from said fiducial point, said arithmetic address converter further performing a multiplication process in a segment number-to-the-time conversion phase, control counter means for directing said multiplication process, configuration and parameter section means operatively connected to provide information as to the characteristics of the disk being utilized, means for selecting a suitable multiplication factor based upon said disk characteristics and the zone information derived in said multiradix conversion phase, said multiplication factor being equal to the number of sector marks which can be contained in an arc equivalent to that subscribed by said desired segment, means for multiplying the actual address number of said desired segment with said multiplication factor, the product of said multiplication being a converted segment number representing the number of sector marks from said reference point of the disk to the desired disk access point, and providing a measure of desired absolute shaft position.

Claim 21

A queueing device as defined in claim 17 wherein said arithmetic address converter further comprises an electronic unit configuration/total timing pulse number selector coupled to said delta generator and comparator means for furnishing thereto information as to the total number of sector marks per circumference for each disk type employed in said subsystem, said latter information being required for delta calculations in cases where the delta bridges the disk dead-space.

Claim 22

A queueing device as defined in claim 18 wherein said delta generator and comparator means comprises an adder/subtractor, means for reading said desired and actual shaft position information into said adder/subtractor, the latter performing a subtraction of the actual shaft position from the desired shaft position, a positive remainder from the subtraction representing a new delta value, a negative remainder being indicative of a condition wherein the delta spans said dead-sPace, said adder/subtractor being responsive to such condition by performing a subtraction of said actual shaft position from the total number of sector marks appearing on said disk face and further performing an addition of the remainder of said last mentioned subtraction to said desired shaft position to produce said new delta value, said delta generator and comparator means further comprising a delta optimizer subtractor for subtracting said new delta value from the previous delta value stored in said delta generator and comparator register means, and logic means operatively connected to the output of said optimizer subtractor for testing whether the new delta value exceeds a predetermined threshold and is in fact a valid delta.

Claim 23

A computer system having a queueing device as defined in claim 12, further characterized in that another queueing device similar to the first mentioned device is provided therein, the pair of queueing devices having the capability of interfacing with and sharing respective pluralities of sets of electronic unit means, each of said queueing devices being adapted to have a primary and a secondary disk exchange, said primary exchange including those sets of electronic unit means with which a queueing device communicates in a normal mode of operation, said secondary exchange including those electronic unit means with which said last mentioned queueing device does not normally communicate, first circuit means associated with each of said queueing devices for permitting access thereto to sets of electronic unit means on its primary exchange, second circuit means linking said queueing devices to each other whereby a first of said queueing devices is permitted access to sets of electronic unit means on its secondary exchange by way of said first circuit means associated with the second of said queueing devices, means for providing said last mentioned access in the event of failure of said second of said queueing devices, said first of said devices assuming the accessing of all of said pluralities of sets of electronic unit means normally shared by said queueing devices.

Claim 24

A computer system having a pair of queueing devices as defined in claim 20 further characterized in that said first circuit means comprise first and second interface circuit boards associated with each of said queueing devices, means coupling respective sets of electronic unit means to said first and second interface circuit boards of said queueing devices, the sets of electronic unit means associated respectively with said first and second boards of each queueing device being on the primary exchange of the device, a third interface circuit board associated with each of said queueing devices for providing each of said devices with a circuit path for accessing sets of electronic unit means on its secondary exchange respectively by way of said first and second interface circuit boards of the other queueing device.

Claim 25

A computer system having a pair of queueing devices as defined in claim 20 further characterized in that predetermined electronic unit designate codes are provided for securing access for each of said queueing devices to one of said sets of electronic unit means on the primary and secondary exchanges of the device, means associated with each of said queueing devices for ''''locking out'''' those codes designating the sets of electronic unit means on the secondary exchange of the device during normal operation, and means operative upon failure of a queueing device to provide access to sets of electronic unit means on the secondary exchange of the surviving queueing device by ''''unlocking'''' those codes in said last mentioned device which permit said access.