Maoni Stephens et al.

Patent Trials and Appeals Board

Apr 8, 2020

13269634 - (D) (P.T.A.B. Apr. 8, 2020)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
13/269,634 10/10/2011 MAONI STEPHENS 333654.01 2983
69316 7590 04/08/2020
MICROSOFT CORPORATION
ONE MICROSOFT WAY
REDMOND, WA 98052
EXAMINER
ROLAND, GRISELLE CORBO
ART UNIT PAPER NUMBER
2158
NOTIFICATION DATE DELIVERY MODE
04/08/2020 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address(es):
chriochs@microsoft.com
usdocket@microsoft.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte MAONI STEPHENS and PATRICK DUSSUD
Appeal 2018-005982
Application 13/269,634
Technology Center 2100
Before JUSTIN BUSCH, BETH Z. SHAW, and SCOTT E. BAIN,
Administrative Patent Judges.

BAIN, Administrative Patent Judge.
DECISION ON APPEAL
Appellant1 appeals under 35 U.S.C. § 134(a) from the Examiner’s
decision to reject claims 1–20, which constitute all claims pending in the
application. We have jurisdiction under 35 U.S.C. § 6(b).
We reverse.

1 We use the word Appellant to refer to “applicant” as defined in 37 C.F.R.
§ 1.42(a). Appellant identifies the real party in interest as Microsoft
Technology Licensing, LLC. Appeal Br. 1.
Appeal 2018-005982
Application 13/269,634
2
BACKGROUND
The Claimed Invention
The invention relates to memory storage techniques, and specifically,
to minimizing computational overhead in certain “heap storage” techniques.
Spec. ¶¶ 1–2. As described in the Specification, heap storage is a set of
memory locations used by objects that are dynamically allocated during
program execution. Id. ¶ 1. As a program executes, heap storage is
allocated from free memory space, and released “explicitly” or “implicitly”
when memory locations are no longer used. Id. When heap storage is
released explicitly, “the memory locations are added to a pool of free
memory space.” Id. Allocated heap storage that is no longer accessed by a
program is called “garbage,” and “garbage collection” is the “process of
reclaiming the memory locations” no longer accessed by the program. Id.
According to the Specification, a potential drawback of heap storage
is that garbage collection “adds considerable overhead to a program since
the garbage collector has to keep track of the objects that are referenced and
then has to release the unreferenced objects on the fly.” Id. ¶ 2. The present
invention aims to “minimize the computational overhead of [the] garbage
collector” in a heap storage arrangement, while sustaining the performance
of the program. Id.
Claims 1, 9, and 15 are independent. Claim 1 is representative of the
invention and the subject matter in dispute, and reads as follows:
1. A computer-implemented method, comprising:
storing onto a mark stack, by a first garbage collector
thread, a partially-marked object reference having a pair of
consecutive entries in the mark stack, one entry of the pair
representing a parent object and a second entry of the pair
Appeal 2018-005982
Application 13/269,634
3
representing a child object reference, the mark stack accessible
by multiple garbage collector threads concurrently, the child
object reference comprises a location of a reference of the
parent object that has not been marked;
searching the mark stack, by a second garbage collector
thread, for a partially-marked object reference, the first garbage
collector thread different from the second garbage collector
thread; and
stealing from the mark stack, by the second garbage
collector thread, the partially-marked object reference by
replacing the child object reference with a stolen value.
Appeal Br. 13 (Claims Appendix) (emphases added).
References
The references relied upon by the Examiner are:
Name Reference Date
Flood et al. US 6,826,583 B1 Nov. 30, 2004
Ylonen US 2009/0327372 A1 Dec. 31, 2009

The Rejections on Appeal
Claims 1–4, 6–12, 15, 16, and 20 stand rejected under pre-AIA
35 U.S.C. § 102 as being anticipated by Flood. Final Act. 3–13.
Claims 5, 13, 14, and 17–19 stand rejected under pre-AIA 35 U.S.C.
§ 103 as being unpatentable over Flood and Ylonen. Final Act. 13–18.
DISCUSSION
We have reviewed the Examiner’s rejections in light of Appellant’s
arguments presented in this appeal. Arguments which Appellant could have
made but did not make in the Briefs are deemed to be waived. See 37 C.F.R.
§ 41.37(c)(1)(iv). On the record before us, we are persuaded of error.
Rejection Under 35 U.S.C. § 102
Appeal 2018-005982
Application 13/269,634
4
Appellant argues the Examiner erred in finding Flood discloses a
garbage collector thread storing onto a mark stack “a partially marked object
reference” including a parent object reference and child object reference
wherein the “child object reference comprises a location of a reference of the
parent object that has not been marked,” as recited in claim 1. Appeal
Br. 5–7 (emphases added); Reply Br. 2–5. Appellant contends that the
passage of Flood cited by the Examiner, which describe storing references in
a “work-to-be-completed queue,” disclose only objects that are marked,
contrary to the foregoing limitations in claim 1. Appeal Br. 5–6. We agree.
The Examiner relies on Flood’s disclosure of a garbage collector
copying reachable objects in the “FROM” semi-space of the heap into the
“TO” semi-space of the heap, and “updat[ing] the root pointer.” Ans. 2–5
(citing Flood 12:57–14:12, Figs. 5A, 5B, 5C, 5D). The Examiner finds:
Asynchronously, thread 2 copies root C into “to” memory and
updates the root pointer. Each root corresponds to a parent
object of the pair. The threads scan each root and discover
references to D (reference 45). The reference to object D is
equivalent to the child object reference that have not been
marked. Both speculatively allocating blocks D' and D" within
their local allocation buffers (LABs). The "To" intermediate
memory location contains partially marked objects because they
have not yet all been copied. D' And D" were speculatively
allocated. After the speculative allocation, threads t1 and t2
both read the word in D that would contain the forwarding
pointer and observe that none is present. In order to resolve the
contention between t1 and t2 for who is to copy D, both t1 and
t2 attempt a CAS instruction to insert the forwarding pointer in
D. Only one of these CAS instructions will succeed and only
the thread performing the successful CAS will actually copy D.
That thread copies D to its new location, and the other thread
updates its references to that location. In this case, say that t1
does so first. Thread t1 copies D to D,' updates the reference in
B' 55 and leaves behind in the location of D a forwarding
Appeal 2018-005982
Application 13/269,634
5
pointer. With reference to FIGS. 5c and 5d, thread t2 is second
to execute its CAS on D, but t2 finds that another thread has
handled D since the newly written forwarding pointer in D will
not match that in the CAS instruction executed by t2. However,
t2's CAS operation returns the newly written forwarding points
to D,' and, so, t2 updates the reference pointer 60 in C' to point
to D' and de-allocates the block D" 49 that was previously
allocated for copying D by t2. Thread t1 finds a reference 57 in
01 to object E. and copies E to E' again leaving a forwarding
pointer in location E and updating the pointer in D' to point to
E' 59. When Band C have been copied, to the "to" memory,
they are considered partially marked objects because they are
roots with references to other objects that have not yet been
copied.
Ans. 3–4 (sic.).
We cannot discern, from the foregoing findings or elsewhere in the
record, however, any disclosure of a child object that “comprises a location
of a reference of the parent object that has not been marked,” as recited in
claim 1 (emphasis added). As Appellant argues, the Examiner appears to
equate an object that has not (yet) been copied with an “unmarked”
reference. Reply Br. 3. Even if the foregoing objects are interpreted as
“unmarked,” however, the Examiner does not explain how such objects
include “a location of a reference of the parent object,” as recited in claim 1.
Moreover, the passages of Flood cited by the Examiner describe
“reachable objects,” which, as Appellant argues, cannot be the claimed
unmarked references because they are “reclaimed and added to the pool of
free memory space.” Reply Br. 4; Flood 3:35–38. As disclosed in Flood:
mutator work threads share heap memory. At least a portion of
this shared memory is partitioned into semi-spaces referred to
herein as "from" and "to" spaces. Reachable objects (here
defined to include any "work tasks" or "live objects, " etc.) are
stored as they are 35 created by mutator threads in "from"
space, and a later garbage collection cycle will transfer the
Appeal 2018-005982
Application 13/269,634
6
reachable objects pointed to by a root source into "to" space
.… Between any two garbage collection cycles, all objects are
allocated in one semi-space ("from" space), leaving the other
semi-space ("to" space) free. When the garbage-collection cycle
occurs, objects identified as reachable are "evacuated," i.e.,
copied compactly into the "to" semi-space from the "from"
semi-space, which is then considered free.…the threads.
Contention is resolved by atomic instructions. The heap is
broken into a young and an old generation where semi-space
copying employing local allocation buffers is used to collect the
reachable objects in the young section.

Flood 3:31–38, 4:31–37 (emphases added), Abstract; Reply Br. 3–4. As
Appellant argues, the Examiner has not sufficiently explained how the
foregoing reachable object of flood can constitute an “unmarked reference”
as recited in claim 1.
For the foregoing reasons, we are persuaded of error regarding the
anticipation rejection of claim 1. For the same reasons, we are persuaded of
error regarding the rejection of independent claims 9 and 15, which include
limitations commensurate in scope with the disputed limitation of claim 1,
and dependent claims 2–4, 6–8, 10–12, 16, and 20. Accordingly, we do not
sustain the anticipation rejection of claims 1–4, 6–12, 15, 16, and 20.
Rejection Under 35 U.S.C. § 103
Remaining claims 5, 13, 14, and 17–19 all are dependent claims, and
are rejected as obvious over the combination of Flood and Ylonen. The
Examiner does not find that Ylonen (or its teachings in combination with
Flood) cures the deficiencies regarding independent claims 1, 9, and 15,
discussed above. Accordingly, for the same reasons as discussed above, we
are persuaded of error as to the obviousness rejection. We, therefore, do not
sustain the obviousness rejection.
Appeal 2018-005982
Application 13/269,634
7
SUMMARY
In summary:
Claims
Rejected
35 U.S.C.
§
Reference(s)/Basis Affirmed Reversed
1–4, 6–12,
15, 16, 20
102 Flood 1–4, 6–12,
15, 16, 20
5, 13, 14,
17–19
103 Flood, Ylonen 5, 13, 14,
17–19
Overall
Outcome
1–20
DECISION
We reverse the Examiner’s decision rejecting claims 1–20.

REVERSED