COMMISSIONER'S DECISION
Section 2' Deadlock Detection for a Computer System
Applicant's interaction of elements to remove deadlock conditions during operation
present a system residing in a patentable area. Rejection withdrawn.
This decision deals with Applicant's request for review by the Commissioner
of Patents of the Final Action on application 224,786 (Class 354-234) filed
April 16, 1975, assigned to Honeywell Information Systems Inc. entitled
DEADLOCK DETECTION AND PREVENTION MECHANISM FOR A COMPUTER SYSTEM. The
inventors are Charles W. Bachman and Jacques Bouvard. The Examiner in
charge issued a Final Action on July 20, 1978 refusing to allow the
application.
The application relates to a data processing system in which a plurality of
elements interact to provide a control arrangement for avoiding deadlocks
in an operation wherein plural processes operate and compete for common
resources. The deadlock detection means as described on pages 23, 24, and
47-56 is shown in figures 1B, and 1F to 1L. To implement the deadlock
detection means, dynamic interaction of the various elements of the system
relies on the provision of control signals from the decoder device in
figure 13b to a central processing unit (CPU). The semaphore data
structures of figures 16a to 16p provide intercommunication between
multiple programs operating in parallel. The term semaphore architecture
is used to describe the elements and arrangements presented by the tables
3A to 3C and 5A to SF (program language), figures 1a and 1c to 1e, figures
16a to 16p (the data shown residing in the memory of the CPU), figures 15
and 19 (block registers), and the schematic diagrams in figures 17 and 18
(showing the interlinking of the registers). Flow diagrams of the firmware
supporting the semaphore architecture are found in figures 20a to 20f. The
overall system is shown in figures 2a and 2b and the computer processing
unit structure therein is elaborated on in figures 13a to 13c. The
hardware memory for the system is set out in figures 3 to 12.
From the lengthy description in the application it is seen that several
drawings are involved in illustrating the operation to obtain Applicant's
results. For sake of brevity therefore, we have not reproduced any
drawings. We have however, reviewed all the drawings in assessing the
nature of the subject matter in the application.
In the Final Action the Examiner does not consider the firmware and
hardware of the system disclosed by Applicant to be apparatus, contending
instead they are data and data structure. The Examiner believes the
specification fails to indicate how the system should be built. On this
point, he has required submission of clear evidence to show the invention
has been reduced to a definite and practical shape. Although he has
indicated there is novelty presented by the microprogram and the data
structure of the semaphore firmware, he believes the claims are contrary to
the guidelines in the Commissioner's Decision published in the Patent
Office Record of August 1, 1978.
In arguing his specifications and drawings provide a clear description of
the means of making the invention to a person of ordinary skill in the art,
Applicant refers to Ernest Scragg & Sons Ltd. v Leesona Corp'n. (1964) 26
Fox Pat. C. 1 where Thorson, J. said:
"The submission thus put forward should not be accepted. It is
settled law that a patent specification is not insufficient by
reason of the fact that a competent workman of ordinary skill
in the art to which the invention relates may have to make
trials or experiments in order to accomplish the result of the
invention, if such trials or experiments are not themselves
inventions and the competent workman can accomplish the desired
result by folowing the teaching of the specification. The
specification is sufficient if it enables him to put the
invention into practice and sufficient directions are given to
him to enable him to know what trials or experiments he may
have to make and how to make them." (Applicant's emphasis)
Applicant asserts that implementation of the invention may be made in
firmware controlled general computing systems "... having a hardware
architecture of a type illustrated by figures 2a and 2b." In his response
he gives as examples the General Electric Series 600, Honeywell Level 64,
and IBM 360 and 370 systems, saying many of these were available before the
filing date of the application. He adds his invention "... operates within
the confines of the computer disclosed", noting the type was commercially
available from Honeywell Systems Inc. at the time of the invention.
Applicant refers to a control store unit 1301 and to statements stored
therein, provided in Tables 5G-5J, for example. He points out his
invention is a control means for avoiding deadlocks.He indicates the
uniqueness provided by the control store is due to the microprogramming
which he argues is in the form of hardware. To illustrate hardware is
present, he refers to a book, "Microprogramming: Principles and Practices"
by Samir S. Husson. From the book, Applicant illustrates why he believes
firmware and microprogramming as referred to in his application is not
equivalent to software and software programming, in particular stressing
the microprogrammer deals with the structure of the computer, for example,
gates, registers and structural aspects of information flow. The Applicant
draws attention to the hardware nature of the semaphores placed in
particular locations, by explaining that the hardware formats and
configurations in the system remain in place even though the data changes.
He argues the conventional programmer is concerned with the language in
which the program is formed. For the firmware descriptions of the deadlock
cases which are present in the disclosure, Applicant contends these are
found in Tables SG-SJ.
Retarding his claims, Applicant considers they are not directed to a
mathematical formula or algorithm, nor a computer program nor an algorithm
which is program implemented. He believes they represent a combination of
internal and external memory registers, and a firmware control unit
including a microprogrammed ROM, the microprogram being the means for
hardware implementation of the deadlock detection system.
The issues before the Board are whether or not the application sets forth
subject matter that is within the definition of Section 2 of the Act, and
whether or not the specification is sufficient in view of Section 36(1).
Claim 1 reads:
In combination with a multiprogram computer system having a
plurality of resources and also having a plurality of
processes, each process capable of assuming a running, ready,
wait or suspended state, a deadlock detection system for
detecting the situation wherein any first of said processes is
waiting for a resource which can never become available to said
any first of said processes, said deadlock detection system
comprising:
(a) first means for requesting on behalf of said any first
of said processes the assignment of any first of said resources
to said any first of said processes;
(b) second means coupled to said first means for causing
said any first of said processes to assume the wait-state and
wait for the requested said any first of said resources if said
any first of said resources is assigned to any second of said
processes and not currently available;
(c) third means, coupled to said first and second means,
for examining the owner-member relationship of each process
that is waiting on some resource; and,
(d) forth means, coupled to said third means, for
determining when said any of said second processes is waiting
for any second of said resources which is already assigned to
said any first of said processes.
We find guidance in assessing the computer-related subject matter of this
application, from Schlumberger Canada Ltd. v Commissioner of Patents (1981)
56 C.P.R. 204. It is to be noted this decision was not available to the
Applicant nor to the Examiner at the date of the Final Action. Pratte, J.
commented as follows:
In order to determine whether the application discloses a
patentable invention, it is first necessary to determine what,
according to the application, has been discovered.
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 determining what has been discovered, we find an architecture or
computer structure which includes a combination of software, firmware, and
hardware elements to make use of multiple processes relying on common
resources. The application refers to a serious problem occurring when
demands from the multiple processes for one resource occur simultaneously.
The first process to seize the resource controls it, and the others have to
wait, their operations thus becoming stalled. Further, should one or more
of the stalled processes have a resource that is wanted by the first
process that is using the first resource, the system points out a stalemate
occurs, known as deadlock or deadly embrace.
The Applicant identifies pages 46 to 55 as describing deadlock detection
mechanism, and figures 1B and 1F to 1L, and to figures in the group 13A to
13C, and the group 16A to 16P as showing it. He says the description on
pages 56 to 112 together with the showing by figures 2a to 13c, and 14a to
14h, provide a system for practicing the invention. He contends figures
16A to 16P show semaphore data structures illustrating the interlinking of
hardware memory registers into a firmware control. Applicant says his
combination of structure avoids interferences between processes so that
each may run apparently independently. He advises that should deadlock be
detected, one process may be restarted while the remainder continue to run
in parallel. He believes that due to his features the availability of data
is increased, and production loss limited to those processes restarted
after deadlock detection. Applicant remarks that the invention is the
combination of the deadlock mechanism and the semaphore structure.
We are impressed by the operation provided by the interaction of the
elements that are said to remove deadlock during the running of a computer
that would cause it to cease operation. We are persuaded by Applicant's
arguments and reasoning, and his cross linking of the elements to
demonstrate how his device prevents a deadlock situation.
We note the Examiner recognized certain parts of the device as firmware and
hardware, and that he considered there was no patentable combination. As
guided by Schlumberger in determining 'What' has been disclosed, we are
unable to agree with the Examiner`s analysis. We find Applicant's
structure does relate a combination of elements working cooperatively in a
device that we believe lies in a patentable area. We see the invention
relates to a field of endeavor that is more than merely determining useful
information from calculations.
We note the discussion during the prosecution centers primarily on the
nature of the subject matter, not its definition. We see Applicant's
arguments, prior to and in response to, the Final Action stress the claims
are not directed to a mere mathematical algorithm. As additional claims
were included with the response to the Final Action, an opportunity to
assess the claimed matter should be provided. We make no finding
therefore with respect to any of the claims other than that they are
directed to patentable subject matter. Should there be an issue concerning
the claimed subject matter, then Applicant's request for a Hearing might be
significant.
We recommend the rejection of the application be withdrawn and that the
aplication be returned to normal prosecution.
M.G. Brown S.D. Kot
Patent Appeal Board Member
I concur with the findings and the recommendation of the Patent Appeal
Board. Accordingly, I withdraw the refusal of the application and remand
it for prosecution consistent with the findings.
J.H A. Gari‚py
Commissioner of Patents
Dated at Hull Quebec
this 10th day of April 1986
Smart & Biggar
Box 2999, Station D
Ottawa. Ontario
K1P 5Y6