Patent GB-1340003-A (GB)
Title: Queueing device for the selection of requests for access to a storage medium
IPC: G06F3/06
Filed: 1971-06-17
Abstract: 1340003 Disc/drum access queuer BURROUGHS CORP 17 June 1971 [29 June 1970] 28384/71 Heading G4C  A queueing device adapted for use with a cyclical data store, e.g. a magnetic disc, includes a means for converting each of a number of access requests into information indicative of the desired physical location in the store of the area required for the access, means for determining the actual physical location of the store approaching the read/write transducers, and a means for generating a delta value for each access request indicating the difference between the desired and actual locations and for determining the smallest delta value, above a minimum threshold, in order to determine the optimum access request. General.-The specification describes various arrangements of disc stores and queueing devices in some detail. Briefly however a disc storage file may consist of an electronic control unit and one or more storage units each of which may consist of four discs mounted on a common shaft. Each disc face may be divided into three annular zones with 50 tracks in each zone, each track being divided into a number of segments, one segment representing the smallest accessible unit of stored data. A timing track is provided having equally spaced timing marks which are used to step a counter in order to determine the actual position of the disc relative to a reference position. The counter is reset each time the reference position passes the read head. The addresses of data in the file form a contiuum from (in this case) 0 to 127,199 (i.e. 78 segments/ track, 50 tracks in each of three zones on each face of 4 discs). In addressing the file the largest multiple of 127,200 which is less than the specified address is determined in order to select the appropriate set of four discs. The product of the largest multiple times 127,200 is subtracted from the given address to obtain a remainder. There are 127,200/8 segments/disc face (i.e. 15,900) so to determine the required disc face the largest multiple of 15,900 which is less than (or equal to) the appropriate address is determined. The process is then repeated using the numbers 318 and 78 in order to determine the zone and track required, the final remainder specifying the required segment. The addressing continues with a segment number-time conversion (followed by BCD-binary conversion) in order to establish in binary the position of the required segment in terms of the number of timing pulses between the reference point and the required segment. The hardwave involved in the above calculations is described. A number equal to the number of segments/disc is subtracted (by complement addition) from the disc address until the remainder is sufficiently small. The procedure is repeated for the number of segments/ disc face &c. as described above until an actual address number of the desired segment relative to the reference point is obtained. End carries from the complement addition can be anticipated by inserting an input carry into the part of the adder servicing the least significant bit. The end carry is then used to determine whether a successful subtraction (i.e., one not producing a negative result) can be performed. The various numbers, e.g. number segments/disc face &c. are provided by a replaceable read only store so that various disc configurations can be handled easily. The segment-time conversion is performed by multiplying the segment number by the number of timing pulses/segment, the multiplication being by conventional addition and shift, and the BCD-B conversion by rounding off the segment number and performing endaround shifting via BCD-B gating. The final result is transferred to the queuer stack register 48 in the queueing device. Parity checking is mentioned. Queueing device.-The desired segment positions for each access request in the queue are fed successively to adder/subtractor 11, the numbers being accessed by incrementing an address register. If the result of a subtraction of the actual position reached from the first desired position is positive then the result represents the value for that access request. If the result is negative then the actual position reached is subtracted from the total number of timing marks/disc face and the result added to the desired position to produce the value. The calculated value is then compared with the smallest previously found value. The new value is, if it is smaller than the previous smallest value, compared to a threshold which represents the minimum response time of the accessing system and if it is larger replaces the previous smallest and is stored in the register. The process is then repeated for all the access requests. The above procedure is repeated each time a new access request is received or the access request associated with the smallest value is executed. The access requests are stored in queuer register 48 which is a register stack which includes a register which specifies the uppermost filled register in the stack. If the stack is full new access requests are refused. Various arrangements of queueing devices and disc stores are described. In one embodiment each of two queueing devices is primarily associated with a respective set of disc store control units. In the event of a failure of one device the other device takes over its functions. Access by each queueing device to the control units is by means of code words, the words designating the control units normally associated with the other device being locked-out until required. Alternatively a single device may be associated with the two sets of control units, the devices in each case having two optimum access request registers.