COMMISSIONER'S DECISION
NON STATUTORY; SEC. 2 - RELEASING A DEAD LOCK STATE IN DATA PROCESSING
A system for releasing a dead lock state during data processing utilizing several
components interacting to release one task from a resource and permitting another
task to use that resource is not an algorithm.
Final Action: Reversed
****************************
This decision deals with Applicant's request that the Commissioner of
Patents review the Examiner's Final Action on application 310,026 (Class
354-230.8). The application was filed August 24, 1978, by Fujitsu Ltd.
and is entitled SYSTEM FOR AUTOMATICALLY RELEASING A DEAD LOCK STATE
IN A DATA PROCESSING SYSTEM. The inventor is R. Kikuchi. The Examiner
in charge issued a Final Action refusing the application.
The application relates to releasing a dead lock state in a data process-
ing system wherein a plurality of tasks compete for the use of a plurality
of resources. In figure 3 reproduced below, a dead lock exists when a
task X which is using resource 2A also has to occupy resource 2B but cannot
because resource 2B is occupied by task Y, and when task Y has to use
resource 2A but cannot because 2A is occupied by task X. Processing is
thereby held up. To remove dead lock, task X is withdrawn from 2A and
another resource 2C is made available to it. This may be achieved, should
2C be occupied by a task, by data buffer 3Y restoring the previous contents
to 2C, and by releasing from 2C whatever task may have been there. Task X
as stored in queue table 8-1 is transferred to key TC and then to resource
2C. Then task Y is able to use resource 2A. The processing of task X
using 2A is thus delayed, but the processing system continues operation.
<IMG>
In the Final Action, the Examiner poses the question "...where does the
novelty lie?" and provides two observations, it "...lies in an algorithm
or program rather than apparatus", and it "...lies in the information stored
in the memory (i.e. the key table and the registration tables)". He critic-
izes the disclosure for not containing novel apparatus, however, he concedes
the claims are directed to a system.
In making his case that patentable matter is present in the application, the
Applicant said in his response (in part) as follows:
...
That which the Applicants regard as their invention is not the
information stored in memory, as suggested by the Examiner, but
the combination of two specific data storage devices with an
examining means and a releasing means interrelated in the manner
set forth in claim 1. The particular data which gay be stored
in the storage devices is material to the invention.
... In the embodiment of Figure 3, the buffers are separate and
discrete components electronically connected to the central
processing unit 5. In the same manner, the waiting task
control table 4 could be a discrete, separate electrical
component electrically connected to the central processing
unit.
...
The issue before the Board is whether or not the application presents
patentable subject matter in view of Section 2 of the Act.
Claim 1 reads:
1. A system for automatically releasing a dead lock state
in a data processing system, wherein a plurality of tasks
including a first task and other tasks commonly use a plural-
ity of resources, comprising:
a waiting task control table storing means, one for each given
task, for storing information corresponding to said each given
task in a waiting state due to occupation of a certain one of
said resources by a certain one of said other tasks, and
a storing before image data buffer means, one for each given
task, for storing before image data every time the content of one
of said resources is modified by said each given task, and
said system including examining means, operatively connected
to said waiting task control table storing means, responsive
to said each given task in the waiting state for examining
the waiting states of the other tasks in accordance with the
contents of said waiting task control table storing means
corresponding thereto, said examining means judging whether
or not the waiting state of said other tasks is due to the
occupation of said resource by said each given task, and
said system including releasing means responsive to said wait-
ing state of said other tasks due to occupation of said
resource by said each given task for releasing the occupation
of said resource by said each given task, wherein the
processing of said other tasks in accordance with the content of
said before image data buffer means occurs prior to processing
said first task.
In reviewing the prosecution, we find it useful to refer to statements in
Schlumberger Canada Ltd. v The Commissioner of Patents 56 CPR at 204 (1981).
In that decision involving computer-related subject matter, Pratte J. made
these comments:
in order to determine whether the application discloses
a patentable invention, it is first necessary to deter-
mine what, according to the application, has been dis-
covered.
and
I am of opinion that the fact that a computer is or
should be used to implement discovery does not change
the nature of that discovery
In his arguments, Applicant says that his structure is an assembly of inter-
acting parts which function to determine when a dead lock elate occurs, and
also coact to release that state and permit the data processing system to
continue. The system contains resources, tasks which use the resources,
and data buffers used at certain times during the process to store before
image data from the resources. He says that figure 3 shows that the before
image data buffers are separate and discrete components, and form no part of
the main memory nor of the central processing unit. In the application he
relates how these elements function with the other elements such as the key
table, the holding queue table, and the registration table for tasks, to
detect and note when the resource elements are in use and by what task,
and he then describes how to release from a resource a task that is forming
part of a dead lock state, and to set it aside for later processing.
Applicant further argues that the task registration table, and the key
means and the queue table forming part of the examining means, such as found
in claims 1 to 11, relate to a patentable advance in the apparatus itself.
It is clear that Applicant has described the various steps in carrying out
his discovery, and we see also that he has provided an assembly of elements
to achieve a release of a dead lock state in a processing system. We are
satisfied that Applicant's discovery presents an arrangement of computing
apparatus which falls within the confines of Section 2 of the Act.
Turning to the claims, we note the Examiner has acknowledged they are direct-
ed to a system, and commented he was not suggesting they were directed to
an algorithm. Accordingly, bearing in mind no prior art has been cited,
end having determined the subject matter to be acceptable in view of Section
2, we find no reason not to accept the claims for being directed to Applicant's
system.
In summary, keeping in mind the guidance given by the Schlumberger decision,
we have reviewed the application to determine Applicant's discovery. At
the same time we have given careful consideration to the objections made in
the Final Action and to Applicant's submission. We find Applicant's system
is for releasing a dead lock state during data processing and includes
several components interacting to release one task from a resource and
permit another task to use that resource. We do not find the subject matter
to be a program or an algorithm. Further, we are persuaded that Applicant's
arguments have properly addressed the issue and have overcome the Examiner's
objections. We are satisfied therefore the application falls within the
ambit of Section 2.
In view of the above findings, we believe a Hearing would be unnecessary.
We recommend the rejection of the application be withdrawn and the application
returned to the Examiner for continued prosecution.
A. McDonough M.G. Brown S. D. Kot
Chairman Assistant Chairman Member
Patent Appeal Board
I concur with the findings and the recommendation of the Patent Appeal Board.
Accordingly, I withdraw the Final Action and return the application for prose-
cution consistent with the recommendation.
J.H.A. Gari‚py Agent for Applicant
Commissioner of Patents McFadden, Fincham & Co.
251 Bank St.
Suite 503
Dated at Hull, Quebec Ottawa, Ont.
K2P 1X3
this 6th. day of May, 1985