Note: Descriptions are shown in the official language in which they were submitted.
BACKGROUND OF THE INVENTION
...._ ~ _ . .
The present invention relates to data processing systems
and more particularly to queue structures which may be utilized
in such systems.
Queue structures are used primarily for -th~ management of
data ~trucutres, without the necessity for movin~ bulk inormation
around in data processing systems, by use of a pointer or header.
The queue is used to schedule tasks which are performed on a
priority basis. Thi5 is done dynamically during proces~ing.
Proce~sing is conducted within a task being performed rather than
scheduling such processing. Queues are also used in communication
buffers for queuing calls. The structures of the present invention
may be managed on a last-in, irs~-out (LIFO) or on a first~in,
first-out (FIFO~ basis. Quaues may also be utilized to maintain a
list of free working memory ordered by size or by address~ The
order of removal of the queues is independent of the order of
ins~rtion. Tn the prior art, it has been known to utilize what
has been called an associative memory in order to acco~nodate the
queulng ~tructures. ~This associative memory technique although
theore~ically appealing is in actual practive unsuited to
handle such queuing tasks due to the relatively high cost and
slow access time~ In the prior art, as taught in the United
States Patent Number 3,449,722, issued June 10, 1969, a new and
improved queuing scheme for multiprocessing systems was described
~5 in which program requests which cannot be immediately operated on
are temporarily stored so that upon the freeing of an originally
busy processor section, the oldest queued program request for the
particular processor section would be accommodated. Such United
States patent suggested the use of a common ~ueue for each such
section in the system which could be separately accessed, thereby~
.
,' . ~ ,,~ , ~,k
by use o th~ common queue~ having established a capability of a
string of requests relative to each of the processor sections
comprising the data processing system, and thereby avoiding undue
e~penditure for hardware which is required b~ such queues. In
such queuing structures in data processing syst~ms it is, however,
important to provide such queuing structure in a manner such that
the queue or frames which are inserted in a list of such queues or
frames may be accessed, i.e., enqueued or dequeued, in any manner
dependent or independent of the priority of the tasks or subtasks
identified by such queues.
It is accordingly a primary object of the present invention
to provide an improved queue structure for use in a data process-
ing system by which the queue structure may be accessed for
enqueuing or dequeuing based on the priority of the frames in such
queue structure or independent of the priority of such Prames,
or ba~ed on the address of such Prames
SUMMARY OF THE INVENTION
~ The above stated object and other objects are achieved
according to the present invention by providing a data processing
system which includes a queue structure which comprises at least
one list ~which may be empty) of priority frames coupled with a
common controi framer the priority frame including a location
for a priority number, a location Por à first pointer to another
one oP the Priority fxames and one or more locations for including
.. .. . .... . . .. .. ........
further information associated with ~quch priorit~ frames~ The contrQl
'
--3--
frame include~ a location for a control word which allows
or disallo~s access to the li t of priority frames, and,
in~ludes a first frame point~r for pointing to the
first one of the priority frames and a last frame pointer for
pointing to the last one of the priority fr,ames in such list.
Each of the priority frames may have difference priorities
associated therewith as indicated by the priority numher. The
queue structura further comprises apparatus for coupling the
priority frames together. The queue structure also comprises
apparatus for placing new ones of such priority frames in such
list in a position determined by the priority numher, and
further logic is provided for retrieving one of such priority ,
frames fEom such list in accordance with or independent,of
~he priority number.
15 ' BRIEF DESCRIPTION OF THE DRAWINGS
The above and other objects of the present invention are
achieved in the illustrative embodiment as described with respect
to the Figures in which: ,
Figure 1 is a block diagxam of a data processing system
utilized in conjunction with the queue structure of the present
invention;
Figure 2 is a detailed block diagram of th~ microprocesor
which is~ used in the data processing system of the present invention;
Figures 3 ~hrough 14 illustrate the manner in which ~he
queue structure of the present invention may have fxames ~ueued or
.
dequeue~; and
Figures 14A through 14D illustrate detailed flow diagrams of
~he operation of the present invention.
.
-4-
ii8
DETAILED DESCRIPTIO OF THE PI~FPERRI~D EMBODIMENT
In the queue management system of the present invention,
a queue capahility is provided that facilitates handling
of ordered lists of frames. A frame may include a frame priority
number, a next frame pointer, and an associated data structure.
Each list is identified by a lock frame which contains a lock
word and, in addition, a head pointer and a tail pointer. This
is shown in Fiyure 3. Only one lock frame and associated list
o~ frames is shown in Figuxe 3, however, it should be understood
that morP than one lock ~rame and associated lists of frames may
be included in the system. Each threaded list may be associated
with a particular task or a number of tasks, thus, these parallel
queue structures, each geaded by a lock frame, may be for different
tasks or the same task, or for different operations. The queue
structure is built for a particular purpose, and when the data
processing sy~stem indicates that it desires a certain queue, it
is usually ready to deal with it, i.e., to operate on the data struc-
ture associated therewith. If the system desires to address a
different threadea list, then it merely changes the address in a
particular one of the registers in the system to point to a new
.. ,
lock fxame. The composition of the data structure is not relevant
to the present invention, however, it may include data which has been
stored away during an operation included in a task, or, in fact, the
data structure may be bothing more than another pointer to another
location where the actual data is beinq stored~ ~ -
There are basically fourinstructions included in
the queue system, two for enqueuing, i.e.,placing a framç in ~he
list, and two fox dequeuing, i.e.,taking a frame~from the list. They
will be descrLbed hereinafter. The lock word is used to insure
that only one data processing unit is accessing a partic~lar
--5--
6~
queue as indicated by a particular lock frame at any given -time.
Each queue instruction will cause a scan of the frame from
the head toward the tail of the list. There is one exception
which shall be hereinafter described.
The scan operation will continue until the conditions of
the particular command are met by a so-called hit, or until the
last frame in the list is reached without a hit, or until an
interrupt occurs in the system. When the so-called hit occurs,
or if the last frame is reached without a hit, the frame is
linked into or out of the list as appropriate, depending upon
whether it is an enqueue or dequeue instruction. If an interrupt
occurs, the central processing unit will stop the scan and
operate on the interrupt condition.
As previously mentioned there are four basic instructions
in the queue system of the prssent in~sntion. They are the ~ !
queue-on-head instruction (QOH)~ queue-on-tail instruction ~QOT),
the dequeue-on-head instruction (DQH) and the dequeue-on-address
1nstruction (DQA). The QOI~ instruction is used to lin]c a new
frame into the list before the first ~rame that has the same
priority number,~or befors the first frame that has a numerically
highex priority number, or as th la~t frame if no equal or
greater priority is found. The QOT instruction lin]cs a new frame
into ths list aftsr the~ 1ast f.rame that hss thè same priority
number, or be~ore the first frame that has a numerically hi~her
; 25~ priority number,~ or~as the 1ast frams if no equal or grsater
priority is found.~ If the new frame has the lowsst pxiority
-6-
that can be given in the system, then the scan operation is
bypassed and the new frame is linked after the last frame. The
DQH instruction is used to unlink the first frame from the list
whose priority value equals or is numerically greater than a
priority value indicated by the system. This value is indicated
in a specific register as shall be hereinafter described. The
DQA instruction unlinks a rame whose priority word address
exactly matches an address indicated in the 5y5tem . This address
i5 indicated in a specifis register as shall be described
hereinafter
The operation of the queue structure including the linking
and unlinking operation, and including a flow chart illustrating
such operation, shall be discussed hereinafter. At this point~
the data processing unit architecture in which the queue system of
the inVentiQn operates shall be discussed.
A block diagram of the data processing system used in the
queue system of the present lnvention is shown in Figure l.
Further details of such data processing system may be found in
U. S. Patent Number 4,047,247, issued September 6r 1977. The
system includes a control store 10 which inclucles by way of
example 512 locations, each location including 56 bits. Each
such location i~ capable o storing a firmware word, such ~lrm-
ware words being used to control various hardware operations
within the data processor. It i5 understood that the numbex of
su~h locations andjor firmware words and the number of bits in
such words may be incre~s d or decreased. Operation of a control
store and the~instruction decoding thereof is shown in the ar~icle
entitled, "Designing Optimized Microprogrammed Control Sections
for ~icroproGessors", by G. W. Schultz, appearing at page 119 of
the Aprilr 1974 issue of Computer Design magazin9~
'
--7--
Also included in the data processor i5 a register and
logic unit (RALU) 12 which is sometimes referred to as the
microprocessor. Figure 2 is a block diagram of the RALU 12
illustrating the details ~hereof. In general, the RALU is
divided into four areas whi~h include a register file, shift
logic, arith~mtic logic, and control logic. The register file
includes data registers, working registers and base xegisters~
The shift logic is used during shifk operations and normal
transfers of data. The arithmetic logic includes various latches
ox buffers, multiplexers~ inverters and an adder unit. The con
trol logic of the ~ALU includes selector logic for selecting that
portion of data to be operated upon.
The central processor includes various registers some of
which are not essential to the present invention, but which will
lS be generally discussed for background purposes. The status/
security register 14 contains the system status and security
keys. This register includes bit fields which indicate whether
the system is in the pri~ileged state ~P~ or whether it
is in the user state. During the user state, specified instruc-
tions will ent~r a so-called trap routine instead of being
executed. The register 14 also includes a field for indicating
the I.D. number o~ the processor, and is set during system con-
figuration. The register 14 also includes a field for indicating
he interrupt priority level of the central processor.
The current running program in the central processor can be
interrrupted by any device which requests a level number which is
lower than ~he level number of the running program, wherein the
`~ :
lowest level number indicates a process and/or device which is
~ -8-
least interruptable. Such interrupt structure is shown in
U. S. Patent No. 4,020,471, issued April 26, 1977.
The indicator register (I) 16 contains the
program status indica~ors. This register 16 includes
various fields among which are included ~ields for indicating
the results of any comparison which was made in the system, and
indication or status of the last peripheral device which was
interrogated, and a field to indicate the state of the last bit
tested.
The Ml register 13 contains trap enable mode control keys,
which include a field for enabling a trace trap (i.e., a trap
which assists in tracing a computer program's operation) for
jump and branch instructions.
The program counter (P register) 20 is by way o~ example
a 16 bit register which normally contains the address of the
instruction currently baing executed. The Y register 22, i.e.,
the memory address re~ister, is also by way of example a 16 bit
reqister that normally contains the address of data to be
acaessed in memory. ~he bus data register ~BD) 24 is also by
way of example a 16 bit register that receives bus data from
the receiver logic 26-R for distribution throughout the processor
v1a the internal bua 28. The interrupt register (L) 30 is also
by way of example a~16~bit register that recei~es a channel
number and level of an interrupting device via the re~eiver logic
26-R.
The XB register 32~is by way of example a ~our bit
register that is used~for bit and byte indexin~ within the pro-
cessor~ The outpu~of~this register 32 is couple~ to both the
:: : : : ~
intexnal bu~ 28 and the decoder logic 34. The instruction
: ~ :
_g_
reyister (F) 36 is by way of example a 16 bit register that
holds the instruction word as it is received from a memory which
may be coupled to the external bus.
The constant generator log.ic 40 is coupled to provide
specific constants to the multiplexer 42 for use in association
with the processor's firmware included within control store lO.
Decoder logic 34 includes a four to 16 bit mult.iplexer that is
used to generate a mask for bit operations. That isl one out
of 16 bits is selected for testing for use hy the finmware
lQ included in control s~ore lO. ~he input twin logis 44 provides
the capability of eith~r duplicating the most significant (left
hand) character (byte) or performlng a straight through transer
from the intPrnal bus 28 to the RALU 12. Output twin logic 61
provides similar capabilities.
The internal bus control logic 48~ as specified by
the firmware word in control store 10, gates the
contents of selected processor registers onto the internal bus
28 via the kri-st~te logic 42. Multipl xer logic 42 includes
the logic by which data is tr~nsmitted to the internal hus ~8r
with only one input enabled for trans~er at any given time.
Test logic 50 selects by way of example one of 64 possible
test conditions, as specified by the firmware word.
Depending upon whether the tested condition is true or alse,
the signal (TSTRUE or TSTRUE) is transmitted to the next address
generation logic 52~ The processor utilizes one:of two me*hods
to generate the next ~irmware addxe~. The first method uses
bits of the control:store word to form the next
address. These~bits may ~or example comprise a lO bit address
field (next address, NA) that can directly address one o
10-
potentially 1,0~4 control store locatlons. The second method
obtains the next address from logic circuitry that contains
several preassigned addresses. The address selected is
determined basically by a decode of the F register 36 contents
and the control store 10 outputs.
The internal bus (BI) 28 is by way of e~ample 16 bits
wide and is primarily used to transfe.r data among the pro-
cessor's registers. Memory addresses and data are also
transferred to the external bus via the internalbus 28. The
address bus 56 is by way of example 16 bits wide and
is used to transfer the addresses for the input and output and
memory read or write cycles ~o the logic ~6- T. The
transceiver logic 26 ~26R and 26T) include logic circuitry whlch
is the only interface between the central processor and the
external bus. ~11 data, address and interrupt signals must pass
through the transceiver logic 26. Such transceiver logic 26 as
well as the operation of the external bus is described in U, S~
Patent No. 4,030,075, issued June 14~ 1977.
~ The select modi~ier logic (SM) 58 determines which bits
: 20 of the F register 36 (if any3 are us~d to modify the register
~ile seleation performed b~ the LS and RS fields, i.e., the
left select and right select ~ields o~ the control store word
o~ control store 10. The SM logic 58 gates F register bits 1
through 3, lO through 11, 13 through 15, or 12 through 15,
depending upon the firmware woxd, to both the left and
right selector logic, i.e., LS logic 60 and RS logic 6~.
Tha LS and RS logic use the selector modifier 58 output
and the contents of the firmware word for register selection.
:
;~
`
6 8
The external bus provides a common communication path
or interface among all units, including memoryt of the system.
The external bus is asynchxonous in design and units of varying
speed are operated efficiently on he system with thxee types
o communication permitted~ namely, memory transfe.rs, input/
output trans~ers, and interrup~s. The external bus may have
coupled thereto, the central processor, a memory unit, pexipheral
device controlIers, communications controllers and the like. The
above noted registers, etc., are further described in a Honeywell
Inform~tion Systems Inc. publicaticn dated January, 1976, entitled,
"Honeywell Level 6 Minicomputer Handbook'l, order number AS22.
Now referring to Pigure 2, the register and logic unit
~RALU) 12 is illustrated in detail. RALU 1~ may comprise four
Model 6701 Microcontrollers manufactured by Monolithic Memori~s
Inc. and de:scrl~ed in their publication therefor dated August,
1974~ As indicated hereinbefore, the RALU 12 is divided into
~four basic areas, more particularly a register ~ile, shift logic,
axithmetic logic, and aontrol logic. First reerring to the
register file 70, it includ~s the data registers Dl through D7,
the working registers DO (or D) and E, and base registers B1
throu~h B7. Registers D1 through D7 are by way o~ example 16
: ~ : bit word operand reg:isters, with bit zero belng considered the
most significant bit. Registexs D and E are also by way of
example 16 bît registers and are used ~or manipulating data
during firmware operations, ths register D is sometlmes used to
hold a copy of the contents~of:the instruction regi~ter (F).36~
: ` : :: :
: The base registe~s~are~also by way of exampl:e 16 bit address
: :
- ~
-12-
registers that can be used for formulating addresses by pointing
to any procedure, data or arbi~rary location in the system.
Multiplexer shi~t logic 80 and 82 primarily include two
16 bit multiplexers that are used for both shift operations and
normal transfers of data. An additional 16 bit register (Q) 76
is provided for double operand shifts. Data can be shifted left
or right by one bit between the multiplexers and any data
register within the register file 70. The Q xegister 76
sometimes contains an unindexed address and the E register (BO)
contains an index value
The arithmetic logic is compxise~ of two 16 bit latch
circuits 84 and 86, two two-to-Dne mu~tiplexers 88 and 90, two
16 bit inverters 92 and 94, addex unit g6 and an output multi-
plex~r 98. The latches associa~ed with input L.100 receive data
from the register fLle 70 as selected by the left selector logic
60. Similarly, the latches as~ociated within input ~ 102 receive
data from the register file 70 as selected by the right selector
logic 62. Outputs from these latches feed both the two-to~on~
multiplexers 88 and 90 respectively and the output multiplexer
2d 98. The left~hand multlplexer 8B receives data from the internal
bus 28 via input D104 and the latche~ 8~ associated with input L 100
The right-hand multiplexer 90 receives data from the Q register
76 via inputQ106 and the latches 86 associated with input ~ 10~.
The outputs from :these multiplexers ~ are ~ed through inverters
92 and 94 respectlvely to ~he respec~ive L and R inpu~s of -~he adder
unit 96. ~he adder unit 96 provides all arithmetic and logical opera
tions. In addition~to the L and R inputs, an additional input
:
-~3-
is provided rom control store word bit 16 tcarry inject).
The adder 96 vutput is fed to both the output multiplexer 98
and the input multiplexers/shift logi~ 80 and 82. The output
multiplexer 98 is the main output from the ~ALU 12. Data from
the output multiplexer 98 is provided to the internal bus 28
for distribution throughout the processor.
The ollowing is a further discussion with respect to the
processor and operation that is depicted in Figures 1 and 2.
The central processor is organized around a single internal bus
28 whi.ch connects most of the processor elements to each other and
to the external bus via receivers 2~ R and transmitters 26-T~
As indicated hereinbefore, the Y xeyister 22 is the memory
address register and the F register 36 is utili2ed to receive
an instruction word during instruction fetches. Various
bits on the internal bus 28 are used a~ inputs to the test logic
50 for use in making firmware branching decisions. The informa-
~ion co~tained in such various bits from the internal bus 28 can
be stored in the test logic 50 and any one of various hardware
control flip--flops 54. The internal hus 28 is also an input to
the RALU 12.
The internal blls 28 is driven or controlled by several
elements including the aonstan~ generator 40 which operates
under firmware control, the RALU 12, the byte selection register
(XB~ 3~2 which i~ loaded by a shifting from the RALU 12.
~5 The current microinstruction is dynamically available at the
output of the control store 10 and ls partially decodad with
various logical el~ments and is then used to provide operations
:: with respect to ~he remaining~element~ in the sy~tem. The next
address generator lagic 52 utiliz~s the next address field in
-14~
$~
the control stor~ word, iOe., the firmware word,and generates
a new address dependent thereon and dependent upon test c~di-
tions provided by test logic 50~ The control store 10 advances
to the next address once per processor clock cycle which may be
in the order of a few hundred nanoseconds.
Having described the architeckure of the data processing
system in which the queue system of the present invention may
be used, the ~unctional o~eration of such queua system will now
be discussed following which a detailed flow diagram of the
queue syskem of the present invenkion will be discussed.
By the present invention, the queue rames are arranged in an
ordered priority list in increasing order. The threaded list of
fr~mes is arranged as shown in Figuxe 3 with the first frame,
called the lock rame, including a lock, a head pointer (or a
first frame pointer) and a tail pointer (or a last frame pointer)~
Each o~ the frames,of which our are shown by way of example,
have a given priority of which priority ~3i,, two "4" priorities
and a priority 7 are shown. The head pointer points to the
framP having priorlty 3, 3 to 4, 4 to 4, and 4 to 7, with the
?O priorL~y 7 ~rame pointing back to the lock fram~. The tail
pointer of the lock frame points to the priority 7
frame, i.e., the last or tail frame. Thus, as can be seen,
ther~ may be rames included which have the same priority.
If a new priority frame is to be added to the queue and if
such frame has a priority of 4, khis 4 priorit~ frame is inserted
either before the two 4 priority~frames or after, but not in
hetween. If i~ is;a new priority number which is to be inserted,
such as five, then~it would ~e inserted between the l~s~ (closest to
the tail o the queue structure~ 4 priority and the 7 priority
fra~e. The frames are only r moved from the haad side,
.
-15-
i.e., closest to the lock frame, so therefore if a frame having
priority 4 is requested from the threaded list of ~ueues then
the priority 4 fram~ closest to the lock frame is taken.
There are four instructions which are provided in order
to either enqueue or dequeue frames to and from the list
rsspectively. They are queue-on-head (QOH~, queue-on-tail (QOT),
dequeue-from-head (DQH), and dequeue by-address (DQA). The queues
are presumed to be stored in main memory. By way of explana~
tion, and as shown in Figure ~, if there are no frames associated
with a particular lock frame, then the head pointer and tail
pointer both point back to the lock word of the same lock frame.
The base register B2, which is located in the co~mercially avail-
able microprocessor chip as shown in Figure 2, is shown pointing
to the lock frame. -
As shown in Figure 5, by way of example, the address
utilized is indicated to be address 456. In addition to re~ister
B2, which has address 456 stored ~herein, register Bl, also in
the microprocessor chip, includes the number addrass of the frame
to be inserted, which is here shown to be 123. The D5 re~ister,
20~ also in the microprocessor chipj is used as a priority register,
here shown to have a priority of 60 stored th~rein~
Now with reference to the queue-on-head instruction, the
operation thereof is as follows. The firmware on execution of
QOH breaks the connections shown for the lock fxame without
:
additionaL frames, as shown in Figure 4. Successlvely thereafter,
the number 123 is stored in the head pointer location, as well as
in the tail pointer~location of the lock frame. The number 456
is stored in the;forward pointer location of the new ~rame and
the priority value~60 is stored ln the priority location also of
the new frame so that the lock frame and new frame are now shown
coupled as shown in Figure 6.
-16-
In further discussion of the operation of the QOH
instruction, assume that at a later time, ~he system assigns the
priority number of a second frame to be inserted in the queue struc-
ture, ~o 70t Bl (the address of the new frame) to 888, and a~sume
s B2 remains at 456, which is the address of the lock frame, at
which time another QOM instruction is executed. Based on this,
the ~ueue structure looks as shown in Figure 7. Thus, as can be
seen~ since the priority equals 70, this is added after -the
irst new frame which has a priority of 60. As can also be seen,
the head pointer in the lock frame remains pointing to the first
new frame, however, the tail pointer of the loc~ frame now points
to the second new rame. In addition, the forward pointer in
the first new frame now points to address 888, the address o
the second new frame.
By way of further example, assume that another QOH
instruction is executed. This time the priority number in
register D5 is e~ual to 50 with the address of the third new
frame, as indicated in register Bl, sat to be 222, with B2
still having address 4S6. ~fter~execution of this QOH, the
lock frame and the three~new frames are coupled as shown in
Figure 8. As will be noted from Figure 8, the third new frame
is coupled between the lock frame and the frame previously
inserted wit~ a priority of 60.
.
Now with réference to Figure 9, assume another QOH instruc-
tion is executed, this time with another frame having a priority
of ~t whose address is 275, to be inserted in the queue struc-
ture~ In this case, since i~ is a ~OH instruction, this frame
: wi71 be inserted before the frame with a priorit~ o~ 60 which :: :
was previously inserted. ~Accordingly,~thè queue structure will
be changed from Figu.~e 8 to that shown in Figure 9, so that the
: -17-
~ ~,r~
third new frame has its pointer changed to point to the fourth
new frame, with the fourth new rame pointing to the first ne~
frame. Otherwise, the queue structure of Figure 9 resembles
that of Figure 8.
The above sequence of opera ions described the manner in
which the queue structure is built up by use of successive QOH
instructions. The following will describe two QOT instructions,
assuming a kase structur~ existing as shown in Figure 8, and
assuming a QOT instruction for inserting a frame having a
priority of 50 with an address of 220 as indicated in register
Bl, and still assuming that regi~ter B2 points ~o the same lock
frame with the address 456. Accordingly, the fifth new fr~me
having such priority of 50 will be inserted after the already
existing frame having a priority of 50 previously referenced as
the third new frame. In such case, the third new frame will
have its pointer changed to point to the fifth new frame by
replacing the address 123 with the address 220, and the fifth
new Erame pointer will point by address I23 to the first new
rame, it being again noted that ~he fourth new fxame referenced
~20 in Figure 9 is not shown in Figure 10 for purpose of ease of
illustration only. Thus, in this case, for QOT instruction,
the new frame is inserted after the existing frame having the
same priority nw~ber, whereas in Figure 9, with the QOH instruc-
tion, the new frame having the priority number 60 was inserted
before the existLng fr~me having the same priority, that is, the
new frame was inserted clos~r to the lock frame in that case
(the QO~I instruction).
Now with re~erence to Figure ll, there is a special case
in which the QOT instruction may be used where the priority of
the frame does not matter. That is, there is a situation which
-18
may allow a savings in time in setting up the queue structure,
where, in fact, the priority of the new frame does not matter.
This instruction is referred to as a QOT instruction having a
priority with the highest number, in this case referred to as priority
number FFFF (hexidecimal). In this case, such priority .i5 placed
at the end of the queue list, after the second new frame in
this example, which requires therefore that the pointer of the
second new ~rame point to this sixth new frame with the pointer
in such sixth new frame pointing back to the lock word in ~he
lock frame. In addition, the lock frame tail pointer will be
changed to point to the sixth new frame, which, in this case,
has an address indicated to be 380.
In addition to the QOH and QOT instruction, there are
dequeue instructions, and, more particularly, the DQH instruc-
lS tion and the DQA instruction. Figure 12 illustrates an example
of the DQH instruction wherein a frame is to be removed. In
this case, by way of example, and w~ith a reference to ~igure 8
; as an existing structure at the time the DQH instruction is
recelved, the DQH lnstruction indicates that it wants to remove
from the queue~list a frame whose priority number is 55 or
greater, a~ indicated in register D5. In such case, therefore, the
first frame having a priority equal to or greater than 55 is the
first new frame, having a priority of 60. In such case, such
~rame i9 removed, the;remalning frames, i.e., the third new frame
is coupled to point ~o the second ~ew frame, with the tail pointer
of the lock frame, as well as the ~irst frame pointer of the lock
frame, remaining the same.
Wi h xeerence to the DQ~ instruction, assume that the
DQA instruction d2sires to remove from the queue structure
a frame whose address is 222, as indic;ated in base register
Bl. In such case,~therefore, and with
.
- 1 9 -
reference to Figure 8, it i5 ~he third new rame which will be
removed, which, in this case, had a priority o 50, but as
explained, this priority does not have any influence on the DQ~
instruction. Thus, upon removing the third new frame whose address is
222~ the queue structuxe remains as shown in Figure 13, with the first
new frame and the second new frame only, with the only change
in the lock frame being that the first frame pointer is changed
to point to the irst new frame rather than the third new ~rame
which has been removed. The f~rst new frame remains pointing
to the second new framel which in turn points back to the lock
frame.
Now referring to Figure 14, the operation of the queue
system of the present invention will be discussed in further
detail by use of flow diagrams. Such flow diagrams depict the
opera~ion of the data processing system of Figure l, and, more
paxticularly, the manner in which the control store words or
firmware words are organlzed and implemented in order to provide
:the enqueue and dequeue operations in accordance with the fQUr
instructions of:the queue~system o.f the present invention.
20~ Now:referring to Figure I4A, the manner in which the QOH
instruction operates and the ~irmware implementation thereof is
shown. At block 200 the QOH instruction is entered following
which the address in re~ister B2 o~ the RALU 1~, as more particu-
larly shown in Figure 2, i9 utilized to address the lock word,
25~ which~in:accordan~e~;wlth~block~ 202 is read and the
hardware lock is set. The hardware lock structu`re is specifically
:: ~ . shown and descri~ed in United States Patent No. 4~`000,4B5, issued
on Decembe~ 28, 1976~, and~èn~itled~"DATA~P~OCESSIN~ SYSTEM PRO-:
VIDING~LOCKED~OPERATION~OF~S~ARED~ RESOURC~S". A~ter the op~a~
30~ : ~tion o~ block 202 is per~ormed~r~decision block 204 is entered
at which point a decision is made as to whether the hardware lock
was on prior to the execution of block 202. If the lock was on,
th~n block 202 is reentered. IE the hardware lock was ofE, the
software lock is set by writing binary ONEs into the software lock
S word as shown in block 236. The interaction of the hardware and
software locks is not relevant to the purpose of the present inven-
tion, but is used in the implementation illustrated to provide con-
tinuous protection of the queue structure in a multiple processor
environment. At this point, the hardware lock is cleared. A test
is then made as to whether the software lock was on prior to the
operation of block 206, as shown in block 208. If the answex to
decision block 208 is Yes/ then the C~indicator i3 cleared to a
binary ZER~ a~ indicated in block 210, ollowing which there is an
exit from this process as indicated in block 212. The C~indicator
is included in the I register 16 and is utilized to indicate whether
or not the scan has been tried and completed, or whether it was
unable to be completed. I the scan is completed, the C-indicator
will be set to a binary ONE. If the software locX was not on, then
block 214 is entered.
At this point, block 214 indicates that register B0 will,
depending upon ~he instruction, be loaded with a certain value.
If it is a QO~ instruction, then the B0 will be loaded with the
contents of DS, whereas if it i5 a QOT instruction, then B0 will
be loaded with the value o~ DS incremented by one. As has been
indicated, register D5 contains the priority number and accord-
ingly during the QOT instruction, this priority number is
incremented by one;~before placing lt into the B0 registerO The
B0 register i~ utili~ed as shall be discussed hereinafter.
Block 216 is then entered at which time the contents of
register B2 are pla~ed in register A0~- A0
which is another reg1ster which may be ~ound in the m~croprocessor
logic of Figure 2. As will be recalled, register B2 contains
the address o the~locX word in the lock frame. This address is
-21-
placed in regi~ter AO in order to be ~bl~ t~, m~lni ~ .la~ 3~ V~l I U~`
as shall be seen, wlthout distur~lny the conte~iltC; of re~ ;t:(~r ~12
~ollow.ing thls, the Y and Q reyisters are each lu~ded Wl.t~l Lhe value
of B2 incremented by one. In the ne~t step~ as sh~wn in ~lock 21~,
the question is answered as to whether or not the contents of regi~ter
BO are equal to Z~O~ If the answer ls Yes, then block 217 is entered
by which the contents of the register are increased in ~alue ~y ti~e
address si~e ~ollowing which ~he tail poi.nter .is placed in reyister
~0~ The mi~s ~peration i~ ~then entered a9 :Lndi~ked by bl~ck 224. IE
howe~er the answer to block 215 was a No, then in ~he ne~t step a.
shown in block 218, khe pointer 1~ read ~rom the memory locat..ton
indicated by the Y xagist~r. This new p~lnter i.s then placed ln the
Y r~gi~te~ a~ in~ica~ed ln b~oak 2~0~ r~hi~ m~m~ry i~ a mamQry whi.ch
i~ aoupl~d to the proc2sæ~r o~ Figure 1 ~la the exte~nal ~u a~ shvwn
in Unit~d S~a~8~ Patent Mo. 4,030,07g, .is~uad June l4, 1977~
Th~ new polnt~r i~ ~hen cvmpared With a value :Ln r~g.t~t~r
B2 as indica~ed in block ~22. If ther~ is compari~on, then thlS
indica~es a mis~ ~ikua~ion as indica~d by block 2~4, whi~h mi~
sltuati~n operatas in ac~ordance with the ~ow diagram Ln
~igure ~4C. If th~re Ls no comparlson~ th~n block 226 1~ ente~ed
at whiah tlme the prio~i~y wo~d o:~ the na2~ r~m~ ead~ followlng
which `the contents o~ th~ Y ~3gist;er are ~ompar~d with ~hb c~ontents o:~
th~ gi~t~ hls ~ompari~csn i~ p~rtlculaxly applic~ble in
~he DQA lns tructio~ hu~ he que~ ~iorl i~ th~n ask~d a~ to
2S wh~l:he~ or not thls 1~ a D~A in~ruc~.tor~ lndicated :ln :~lock
228. ~ lt i~, then ~h~ ~u~s~ion .t~ asked, a3 indi~atPd in
blo~ 230, a9 ~o whe~h3r o~ no~ ~he aont~nkl o.~ ~he ~ ~es~i~ter
are ~qU~ o th~ ~ont~n~3 o 331 ~y:Lster~ ~ the answ~r i~ ~3s,
~then th~r~ is ~ hl~ ~ituat~on, as incllcated by ~lock 232, and~
acco~d~ngly,~ ~he :~low ~l~gram o~ Flg~r~ 14s i~ ~n~er~d. I~ ~h~
~answ~r to bloaJ~: 230 ls ~:Ja, ~h~3n l:loa~ 236 i~3 entered, a~ ~hall
~e her~ scribsd ~ h~ an~w~r ~ hl~ak 2 ~ 8 ~
1.~., thi~ i~ nt1~ a D~A in~xtu~:~ion~ ~hen bl~ak ~4 ;1~ ~n~3red
ak whl~h ~imé tha ~alu~ ~ the prio.rit~ wor~ comp~f3d w.i th th~
content~ o re~is~er :~0. I~ ~u~h ac~mpæi~on p;~duces an ~u~l o~
6~
grea~er ~han indication, then the hit ~ituation i5 in~icated~
then the operation of Figure 14B proceeds. If such comparison
indicates a less than situation, that is the value of the
priority word is less than the value of the contents of register
B0, then block 236 is entered. At this time, the contents o
the Y address register are placed in the ~0 register,
following which the Y register is incremented by one. The
determination of whe~her there is an interrupt situation is then
made as indicated in block 238. If there is an interrupt
situation, then the operation of Figure 14A is exited, as
indicated by block 240, at which ~ime the operation of Figure 14D
proceeds. If there is no interrupt, then, in fact/ block 218 is
entered again wherein a pointer is read from the memory location
indicated by register Y, which, as indicated by block 236~ has
lS been incremented by one.
Now referring to Figure 14B, the situation whert~in a hit
situation is encountered, as indicated in Figure 14A, shall be
described Initially block 242 is entered, at which time the
contents o~ the Y register are placed in register B0 and the
Y register is incremented by one, following which there is a
requirement that the naturt~ o~ the operation, i.e., the instruc
tion, must be determined as indicated by~the decision block 244.
If this is a QOH or QOT instruction, then block 246 is entered.
It is herein noted that block 246 has another input which is
received from Figure 14C during the mLss operation. Thus, when
block 246 is entered the contents of regis-ter Bl are placed in
the Y register, ~ollowlng which the priority word is written
from r~gister ~5 into the memory location indicated by r~gister
Bl, ~ollvwing which the~Y register is lncreltlented by one Blt~ck
3~ 248 ~is then entered, at which time the poLn~er is written f`rt~m
:
-23-
register B0 into the memory location addressed by the value in
register Bl incremented by one. The instruction bein~ operated
upon is then queried, as indicated by block 250, and if it is a QOH
or QOT instruction, block 252 is entered at which time the
contents of the A0 ~egister are incremented by one and
placed in the Y register. The contents of register Bl are then
placed in register B0. Block 254 is then entered at which time
the pointer is written from register ~0 into the memory location
addressed by register Y~ The C indicator in the I reglster is
then set to a binary ON~ as indicated by block 256, which, as
indicated her~inbefore, indicates that the scan has been com-
pleted. Following this~ the opexation o~ Figure 14B is exited
as indicated by block 240. The operation then contlnues as
indicated in Figure 14D.
lS The preceding paragraph has described the operation where-
in the instruction has been a QOH or QOT instruction. If the
operation is a DQH instruction or a DQA instructionr then the
initial decision block with respect thereto, i.e., block 244,
branches to the operation indiaated in-block 260. At this
tlme the contents of register B0 are placed in register Bl and
the G and L indicators are set in order to, for example, indicate
whether the frame was unlinked or whether no match was found, or
whether the unlinked frame was the flrst whose priority
- equalled the~contents of register D5, or whether the unlinked
frame was the irst whose priority exceeded the value in register
D5. Following this, the pointer is read from the memory location
ind~cated by the Y ~egister and is placed in regi~ter B0. The
contents of ~he A0~registe~i incremented by one,
is placad in register Y. Following the ~pera-
3~ tion of block 260, as in~icated in block 26~, the ~uesti~n is
:: :
~24-
asked as to whether the contents of register B0 are equal to
the contents of register B2. Thus, the value of the pointer,
which is read from the memory location pointed to by khe Y
register, is compared with the address of the lock word in the
lock frame. If they are equal, then the operation of block 248
is followed, but if not equal, the operation of block 254 is
followed. If there was an ~qual comparison, as indicated by
block 262 and this was a DQE~ or a DQA instruction, then block
250 will branch to block 264 by which the contents o~ the Q
register incremented by cne are placed in the Y register, follow
ing which the A0 register contents will be placed in the
B0 register. Following this operation, the operation indicated
by block 254 is entered.
Having described a situation as indicated in Figure 14B
wherein a so-called hit occurs, Figure 14C will now be described
for tha~ situation in which a so-called miss occurs as indicated
by block 224. Foll~wing the entry into this miss operation,
block 270 is entered by which the C-indicator is set to a
binary ONE~ As indicated hereinbeore, the fact that the
C indicator is set to a binary ONE means that the scan has been
tried and that the instruction need not be done again. Thus,
the operation~for that instruction is complete at least for the
present time. Following this, the question is~then asked in
block ~72 as to which operation this is. If ik is a QOH or QOT
instruction, then block 274 is entered at which time the value
(e.g., one or two words~
in the Q register plus the address size/is used to address the
tail pointer, following which the contents of the ~l register
are written into the tail pointer. Fol}owing this, the contents
of the B2 register are placed in reg~ster ~0O ~t this point,
junctlon A is entered, whiah junction or point A may be seen a~
-25-
an entry point to block 246 in Figure 14B~ The operation then
continues as indicated in block 246. If this were a DQH or DQA
instruction, as indicated hy block 272, then block 276 is
entered at which time the G and L indicators are set appropriately.
Finallyr the operation exits as indicated by block 240.
Now referring to Figure 14D, the manner in which each o~
such operations exits, as indicated by block 240, shall be dis-
cussed. ~t block 280, the software lock is read and
the hardware lock is set. The question is then asked, as
indicated in block 282, as to whether or not the hardware lock
was on, prior to the setting action indicated in block ~80. If
the hardware lock was on, as indicated by a Yes answer to
block 282, then block 280 is reentered. If the hardware lock
was off, as indicated by a No answer, bloc]c 284 is entered
whereby binary ZEROs are written into the software lock word
and the hardware lock is cleared. The question is then asked7
as indicated in block 286, as to whether or not the~C-indicator
equals a binary ON~ or ZERO~ If C is equal to a ONE, this means
that this is the end of the instriction. If C is e~ual to a ZERO
this indicates the need for decrementing the program counter
by one, as indicated in block 288, ~ollowing which the instruc-
tion is also indicated to end.
The m~nner in which the four generic operations of the
queue structure o~ the present invention operate, has been seen.
Use of a lock frame including the lock word therein has also been
seen. As has been shown, this lock word, sometimes referred to
as the so~tware lock, is checked when starting the operation of
any of the four generic instructions~ and at such time the lock
word is locked, by setting to the appropri~te hinary ~alu~
-2~-
However, if i~ had already been locked, the instruction
is exited and is not reentered unti] the lock word is unlocked,
since in fact, by indicating that the lock word i5 locked,
this means that there is another operation being performed
with respect to the coupled queue struc~ure, which operation
should not be disturbed. When the operation is completed, the
lock word is unlocked. Thus, the queue structure is locked,
i.e., the lock word indicates that the queue structure should
not be disturbed, and is so locked during thP scan operation
and as the various pointers in the rames are being swapped
and/or updatedO In general, the hardware lock previously
referred to is set and is then unset (the haxdware lock is not
set during the scan operation) so as to insure that no more
than one process being executed in the data processing system
may check the software lock at any given time, thereby avoiding
an incorrect answer as to the status of the lock woxd in the
lock frame. There may be more than one software lock for each
hardware lock, i.e., there may be more than one threaded list
of frames with each having a lock frame and included lock word.
By use of such lock words, synchronization for multiprocessing
units is provided~
Having described the invention, what is claimed as new
and novel and for which is it desired to secure Letters Patent
is:
: ~ :
-27-
