Note: Descriptions are shown in the official language in which they were submitted.
S
--1--
This invention relates to means and methods for allocatiny
resources in an electronic digital data processing system.
As is well known, an important function performed
within a data processing system having multi-programming
and/or multiprocessing capabilities is the allocation of -the
available resources to the various data processing operations
being performed. The manner and efficiency of this
allocation of resources can have a significant impact on
system performance and economy.
A primary object of the present invention is to provide
particularly useful and advantageous apparatus for allocating
resources in a data processing system.
According to the present invention there is provided for use
in a data processing system,resource allocation apparatus compris
ing: storage means indicating the free and assigned states of a
plurality of resources, said storage means including a plurality
of portions, each portion indicating the free and assigned states
of a particular predetermined plurality of said plurality o~
resources; a plurality of individually addressable memories,
each memory being addressed by a respective one of said portions
and being operative in response thereto for providing a corres-
ponding memory output including free resource identifying
signals which identify at least a predetermined plurality of
the free resources indicated by the applied portion, the memory
outputs from said memories also including a plurality of selection
signals; and a plurality of selection means to which said memory
outputs are applied, each selection means receiving particular
ones of said free resource identifying signals and said selection
signals and being operative in response thereto so that the out-
puts of said section means select a particular predeterminedplurality of the free resources identified by said free resource
identifying signals.
Embodimen~s of the invention will now be described, by way
of example, with reference to the accompanying drawings in
which:
;
5~S
. ~
FrG. 1 is a schematic and electrical diagram
illustrating a preerred embodiment of the invention.
FIG. 2 is a schematic and electrical diagram
illustrating details o~ the FIG. 1 embodiment.
FIG. 3 is a series of tables illustrating the
operation of the multiplexers in FIG. 2.
Like numerals refer to like elements throughout the drawings.
~eferring to ~IG. 1, illustrated therein is a preferred
embodiment of register allocation apparatus in accordance with
the inventionn ~s shown, an allocation register 10 is provided
whose states indicate the free and assigned states of a plurality
of assignable registers. For the purposes of this description
and by way of example, it will be assumed t~at there are sixteen
registers Rl to R16 available for assignment. Accordingly, the
allocation register 10 will be assumed to contain sixteen bit
storage elements rl - rl6 respectively corresponding to the
assignable registers ~1 - R16/ wherein a "1" value of a bit
storage element is used to indicate that its corresponding
resister is unavailable for assignment, while a "0" value indicat
es that the corresponding register is free and thus available for
assignment. It will further be assumed by way of example that,
at a particular point in timej the sixteen bit elements rl - rl6
of the allocation register 10 have the respective values
0101010001101010 shown in FIG~ 1. Thus, register 10 in FIG.l
indicates that the seven registers R2, R4, R6, R10, Rll, R13 and
R15 are free registers.
As indicated in FIG. 1, the first eight bit storage
elements rl - r8 of the-allocation register 10 are applied
as an address to a first memory 15 and the second eight bik
storage elements r9 - rl6 are applied as an address to a
second memory 20. Each of these memories 15 and 20 may
typically be a PROM (programmable read only memory).
Generally, the construction and operation of the preferred
embodiment of FIG. 1 is such that appropriate portions of the
selected memory words read out from memories 15 and 20
s
-
.. 3
(in response to ~he respective addresses provided by the
allocation register 10) are applied to a comparator 25 for
determining whether a sufficient number of free registers
are available for a newly activated task, and are also
5 applied to a plurality of mul~iplexers 30 for identifying a
particular number of free registers av~ilable for
assignment ~o a newly activated task based on the current
state of the elements rl - rl~; of the allocation register 10,
These ~ree register identifications and a corresponding task
10 identification n~nber are stored in a register mapper 4n
so that, when the regis~er mapper 40 i5 accessed during task
execution, these ~egister identiications are read out and
appliQd 'co a register file 45 for accessing the identified
re~ isters O
The construction and operation of FIG. 1 will now
be ~onsidered in mvre detail with reference to FIG. 2, For
this purpose, and by way of example, it will be assumed that
each task requires a maximum of five free registers.
Accordingly, multiplexers 30 in FIG. 1 are shown in FIG~ 2
as comprising the five multiplexers 31 - 35 whose outputs
Ml - M5 are binary nu~bers identifying five particular free
re~isters available for assignment to a newly activated task
based on the current states of the hit storage elements of
the allocation register 10. For the illustrated embodim~nt
of FIGo 2~ it is asss~ned that these five free registers
identified by the multiplexer outputs Ml M5 are the five
lowest n~nbered ~ree registers currently available~ which,
in conformanee with ~he s~ates of ~he alloca~ion regist~r 10,
are registers R2, R4, R6~ R10 and Rll.
In order ~o permit the mapping of memories 15 and
20 to be readily understood, FIG. 2 illustrates examples of
the par icular selected m~mory words W-A and ~;B read out
from memories 15 and 20, respectivel~, in response to the
. ~ 'I --
illustrated states of their correspond ing portions of the
allocation register 10 sho~n in FIG. 1. It will be
understood that, for greater clarity, decimal numbers are
used in FI~. :2 to indicate the contents of ~he various
5 memory word portions; however, ~hese dec~mal. numbers are
preferably stored in binary ~orm in memories 15 and 2 0 .
It will also be understood that the selected memory word
W-A from memory 15 provides d~ta relative to registers
Rl ~ R8 ~since memory 15 is addressed by el~ments rl r8 f
10 reg ister 10 ), while the m~nory w~rd W B from memory 20
provides data relative to registers R9 - R16 (since memory 20
iS addressed by elements r9 - rl~; of reg ister 10 ) . Thus,
proceeding from left to right, the left-most portion of each
memory word contains a number (designated SA for memory
15 word W-A and S~s for memory word W-B~ indi::ating the 'cotal
number of free registers in accordance with the states of
the re~pective elements of the allocation register 10 in
PIG. 1. The next portion of each memory word ~designated lA,
2A, 3A~ 4A, 5A for m~mory word W-A and lB, 2B, 3B" 4F~, SB
for memory word W-B) identifies ~also in accordance with its
respective elements of register 10) up to ive free ~e~isters
be~inning with the lowe~t number free register; an ~X"
indi~ates that no additional free registers are av~ilable
~esides those indicated and may typically have a WdoD't
caren value ~uch a~ ~0~ (since there is no ~0~ reqister)~
Thus, for memory w~rd W-A in FIG~ 2, SA properly
indicates a total of three fr*e registers for W-A, and SB
properly indica~es a ~otal of four free regis~ers ~or W B.
Also, lAt 2~ and 3A of memory w~rd W-A respectively identify .
30 the three free registers 2, 4 and 6 indicated by elements
rl r8 f register lOi while 4A and 5A are properly
indicated as "X" (don~t c:are~ values ~since elements rl ~ r8
indica'ce no other free registers). ~n a similar manner~
s
5 --
lB, 2B, 3B, 4B of memory word W-B respectively identify the
four free registers 10, 11,, 13 and 15 indicated by elements
r~ - rl6 of register 10, while 5B ind~.cates a "don't care"
val~le ( since el~nents r~3 - rl6 indicat:e no other free
reg i s ter s ) .
It wil 1 be noted in FI(;,, 2 that memory word W-A
additionally includes portions designated as m1, m2, m3, m4
and m5, These portions could alternatively be included
with memory word W-B or they could be spl it up ~etween the
two memory words. As indicated in FIG. 2, these ml~ m2, m3,
m~ and m5 portions are respectively appl ied as selection
signals to multiplexers Ml, M2, M3, M4 and MS, and different
pluralities of portions lA to SA and lB to SB of memory
words W-A and W~B are respectively applied as register
identification input signals to each of multiplexers Ml - M5,
As is to be expeeted, the si~e of each of the multiplexers
M1 - M5 and the number of bits required for each f ~1 - m5
are dependent on the number of L~ to 5A and lB to 5B input
applied to ea~h multiplexer.
~he choice of the values of ml - m5 and the
particular pluralities of portions lA to 5A and lB to 5B to
be applied to each of multiplexers Ml - M5 in FIG. 2 is based
on obtaininy, at 'che multiplexer outputs, identifications of
a particular group of free reg isters for a~signment to each
newly activated task~ In the preferrPd embodiment, this
particular ~roup of free registers is ~hosen as the five
lowest n~nbered free registers which~ for the exemplary
~tates of the allocation regi~ter 10 illustrated in ~G. 1,
are registers R2, R4, R6~ R10 and Rll as indicated at the
3û multiplexer outputs in ~ . 2. The tables of FIG. 3 s~t
forth the oFeration of ~he multiplexers Ml ~ M5 in response
to the respectiv~ ml - mS and lA to 5A and lB to 5B signals
applied thereto ~as sho~n in FIG~ ~), whereby the fiYe
-- 6
lowest numbered free registers are idPntified at the
multiplexer outputs~
The tables of FIG. 3 will now be considered in
more d~tail wi~h specific reference ~o the exemplary values
o the memory words W-A and W-B illustrated in FIGo 2J
It will be understood from FXGS. 2 and 3 that
multiplexer Ml has only the two inputs 1~ and lB from
memory words W-A and W-B applied ~hereto so that its selection
input ml need only be a single bi~. Since lA of memory word
1~ W-A contains a ~2n identifying R~ as the lowest number free
register~ the value of ml for word W-A is chosen as a ~0" to
~ause the content~ of lA (which identifies register R2 as a
free regi~ter3 to be selected as the output of multiplexer
Ml" In this regard, it is to be noted that the respective
ml~ m2~ m3, m4~ m~ inputs for the multiplexers Ml ~ MS in the
preferred embodiment are chosen so that each multiplexer
selects the lowest numbered input of the particular plurality
of lA 5A and lB - 5B inputs applied thereto which
identifies a free register, with an ~A~ input being selected
ahead of a "B" input.
As indicated in FIG. 2 multiplexer M2 has the three
?nputs 2A, lB and 2B of memory word W-A and W-B applied .
thereto so that m2 requires two bits for selecting among 2A9
lB and 2By as illustrated in the multiplexer M2 t~ble in
~5 FIG. 3~ Since 2A of memory word W-A contains a ~4~
identifying R4 as a free register, m2 for word W-A is chosen
a~ ~00~ to cause the contents of 2~.(which identifies
register R4 as a free regi ter) to be selected as t~e output
of multiplexer M2.
Multiplexer M3 in FIG. 2 has the four inputs 3A~
lB, 2B, 3B from memory w~rds W-A and W-B applied hereto
which, like m2~ requires a t~o bit m3 input for selection as
illustrated in FIG. 3~ Since 3A of memory word ~-A contains
5~
7 --
, . .
a "6" identifying R6 as a free register, m3 for word W-A is
chosen as "00" to cause the contents of 3A ~which
identifies register R6 as a free register) ~o be selec~e~
as the output of multiplexer M3.
Multiplexer M4 in FIG. 2 has the fiue inputs qA; lB,
2B, 3B, 4B from memory w~rds W-A and W-B applied thereto
which requires a three bit m4 input for selection as
illustrated in FI~ 3. The first frPe register identified
by the inputs applied to M4 is indicated by lB which contains
1~ a ~0~ identifying register R10 as a free register. Thus~ in
accordance with FIGo 3t m~ is chosen as ~001" to cause the
contents of lB to be selected as the output of multiplexer M40
The remaining multiplexer M5 in FI~o 2 has the six
inputs 5A~ lB, 2B, 3B, 4B, 5B from memory words W-A and W-B
lS ~pplied thereto which~ like m4, requires a three bit m
input for selection as illustrated in FIG. 3. The first free
register identified by the inputs applied to M5 is indicated
by 2B which contains arl "~1" id~ntifying register R11 as a
free register. Thus, in accordance with FIG. 3, m5 is chosen
as 010 (which is "2" in decimal) to cause the contents of 2B
to be selected as the output of multiplexer M5.
Referring bac}c to F~G. 1, it will be seen that the
free register identi~ications provided at the output o the
mult~plexers 30 are applied to an update circuit 50 along
with the n~nber of free registers required by th~ task.
The update circuit 50 responds to these inputs by provid ing
an output to the allocation register 10 which up~ates the
val ues of the storage elements rl rl6 accord ingly~,
Baving described how selection of the five lowes~
n~3nbered free registers is a~c~mplished in the preferred
embodiment illustra ed in FIGS. 1-3, it will next be
considered how the situation is handl~d by the preferred
embodiment when there are insufficient free registers
available for assignment to a newly activated task.
,
..
r`~.3:~S
~8--
It will be remembered that the SA and SB portions of memory
words W-A and w-s con-tain the total number of free re~isters
indicated by -their respective portions of the allocation register
10 in FIG. 1. Accordingly, these SA and SB values are applied to
the comparator 25 which also receives an input indicating the
number of free registers required by a newly initiated task. The
comparator 25 compares the sum of SA and Ss with the number of
free registers required by the task.If insufficient free registers
are available, the comparator 25 produces a HOLD signal which is
used to cause the task to wait until sufficient free registers
are available.
It will be seen that in the preferred embodimen-t, the princi-
ples of the invention are applied to the function of allocating
registers required ~or use by a plurality of tasks being concurr-
ently performed by a data processing system. Typically, thesystem provides a predetermined number of registers which are
allocatable for use by a plurality of active tasks. In the pre-
ferred embodiment, an updatable list of free and assigned regis-
ters is maintained and, as each task is activated, specially
provided register selection apparatus responsive to this list
selects a predetermined numher of free registers for assignment
to the task. If insufficient free registers are available for
use by a newly activated task, it is signalled to remain in a
"hold" state.
In the preferred embodiment, the register selection appara-
tus includes a plurality of specially mapped memories to which
respective portions of the updatable list of free and assigned
r~gisters are applied as memory addresses for reading out select-
ed ~emory words. These selected memory words identify available
free registers and also provide appropriate logic for controlling
a plurality of multiplexers to which the selected memory words
are applied. These multiplexers operate to select a particular
plurality of the available free registers for assignment to each
newly activated task where sufficient free registers are avail-
able to meet the task's requirements. The sufficiency of freeregisters for a newly activated task is determined by comparing
the number of free registers required by a task with the total
number of free registers which the selected memory words indicate
are available. If insufficient free registers are available for
~5~.S
. 9
assignment to a task, the comparator provides a "hold" signal for
use in placing the task in a "hold" state.
The combination of the list of free and unassigned registers,
the specially mapped memories and the multiplexers, as briefly
described above, provide for register allocation in a highly
advantageous and economical manner which is well suited for use
in a multiprogramming and/or multiprocessing environment.
Although the description provided herein has ~een directed
to a particular preferred embodiment, it is to be understood
that many modifications and variations in structure, arrangement,
components, operations and use are possible without departing
from the spirit of the invention. The present invention should
accordingly be considered as encompassing all such possible
modifications and variations coming within the scope of the
appended claims.
