Ex Parte McKenneyDownload PDFPatent Trial and Appeal BoardSep 19, 201311854840 (P.T.A.B. Sep. 19, 2013) Copy Citation UNITED STATES PATENT AND TRADEMARK OFFICE ____________ BEFORE THE PATENT TRIAL AND APPEAL BOARD ____________ Ex parte PAUL E. MCKENNEY ____________ Appeal 2011-002793 Application 11/854,840 Technology Center 2100 ____________ Before DENISE M. POTHIER, LYNNE E. PETTIGREW, and IRVIN E. BRANCH, Administrative Patent Judges. POTHIER, Administrative Patent Judge. DECISION ON APPEAL STATEMENT OF THE CASE Appellant appeals under 35 U.S.C. § 134(a) from the Examiner’s rejection of claims 1-20. We have jurisdiction under 35 U.S.C. § 6(b). We affirm-in-part. Invention Appellant’s invention relates to a technique for implementing a mutual exclusion mechanism known as a “read-copy update” (RCU) to Appeal 2011-002793 Application 11/854,840 2 increase the speed of RCU grace period detection. See Spec. 1:8-11. Claim 1 is reproduced below with emphasis: 1. A method for fast path detection by an updater of a grace period for deferring the destruction of a shared data element by said updater until pre-existing references to said shared data element are removed, comprising: checking for the presence of readers that are accessing said shared data element without using locks to exclude other updaters; terminating grace period detection to initiate deferred destruction of said data element if there are no readers accessing said shared data element; and if there are readers accessing said shared data element, implementing a lock and checking again for the presence of said readers. The Examiner relies on the following as evidence of unpatentability: Paul E. McKenney et al., Read-Copy Update 1-221 (2001), available at http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (“McKenney”). The Rejection Claims 1-20 are rejected under 35 U.S.C. § 102(b) as anticipated by McKenney. Ans. 3-6. THE CONTENTIONS Regarding illustrative independent claim 1, the Examiner finds that McKenney discloses checking for readers accessing a shared data element without the use of locks through the use of counters. See Ans. 7-8 (citing § 6.1). The Examiner further finds McKenney teaches implementing a lock with a deletion function. See Ans. 9-10. 1 Twenty-two printed pages of this reference were provided, and these page numbers correspond sequentially to the pages provided. Appeal 2011-002793 Application 11/854,840 3 Appellant argues McKenney does not mention checking for the presence of readers without using locks. App. Br. 12; Reply Br. 4-5. Appellant further asserts that McKenney does not mention implementing a lock if there are no readers accessing the shared data element and checking again for the presence of readers. App. Br. 12-13; Reply Br. 5-6. ISSUES Under § 102, has the Examiner erred in rejecting claim 1 by finding that McKenney discloses (1) checking for the presence of readers that are accessing said shared data element without using locks, and (2) if there are readers accessing said shared data element, implementing a lock and checking again for the presence of said readers? ANALYSIS Based on the record before us, we find no error in the Examiner’s rejection of independent claim 1. Appellant argues Figure 8 in McKenney does not mention checking for the presence of reader without using locks or excluding other updaters. App. Br. 12. The Examiner additionally relies on section 6.1 of McKenney and the use of two counters. Ans. 8. Here, McKenney discusses a Tornado/K42 Design RCU that periodically checks a non-current generation for the value of zero, which indicates that all associated operations, including read operations (e.g., readers) in some embodiments, have terminated. McKenney § 6.1. Similar to Appellant’s process of examining counter values to check for readers (see Ans. 7), this section demonstrates McKenney checks for readers that are accessing a shared data element. Appeal 2011-002793 Application 11/854,840 4 Appellant also asserts that McKenney fails to disclose this process occurs without using locks or excluding other updaters. App. Br. 12; Reply Br. 5. We are not persuaded. Notably, section 6.1 does not discuss locks. See McKenney §6.1. Also, as the Examiner explains (Ans. 8-9), McKenney discusses using quiescent states to detect when all operations are completed at the end of a grace period. McKenney § 1, page 2, column 2, full paragraphs 1-3. We thus disagree with Appellant’s assertion that McKenney “is referring to how readers access shared data for reading” and “does not have anything to do with grace period detection[.]” Reply Br. 5. McKenney further describes the use of quiescent states as pessimistic and states that a pessimistic approach determines whether a given data structure (e.g., a shared data element) is no longer referenced without using locks. McKenney § 1, page 2, column 2, full paragraph 3. McKenney also states that the Tornado/K42 Design can implement quiescent states. McKenney § 1, page 3, column 1, full paragraph 5. Thus, McKenney discloses an embodiment in which checking for read operations (e.g., examining a counter value) does not use locks to exclude other updaters. In the Reply Brief, Appellant asserts that McKenney in § 6.1 only discusses one counter in arguing McKenney does not teach checking for readers. See Reply Br. 4-5. Given that claim 1 fails to recite any counters, we find this argument is unpersuasive. Appellant further contends McKenney fails to disclose implementing a lock if there are readers accessing the shared data element and checking again for the presence of readers. App. Br. 12-13. Again, we disagree. As the Examiner notes (Ans. 9-10), McKenney discusses permitting pre- existing operations to proceed in an old state before completing an update, Appeal 2011-002793 Application 11/854,840 5 which involves deleting or freeing a shared data element only after all existing references to data elements have been removed. See Ans. 9-10 (citing § 1, page 3, column 2, paragraph 1 and page 5, column 1, full paragraph 2 and § 2.4, column 2, full paragraph 1). In particular, the delete function arranges for a specified element to eventually be freed up (§ 1, page 3, column 2, full paragraph 4) by using a lock that waits for a grace period before freeing up a memory block (§ 2.2, page 5, column 1, full paragraph 2). McKenney thus discloses, during the deletion function, an element may not be able to be freed up immediately because of concurrent operation (e.g., read operations). McKenney § 2, page 4, column 1, paragraph 1 and § 2.4, column 2, paragraph 1. Appellant also illustrates that this lock occurs prior to the grace period detection (e.g., during read operations). See Reply Br. 6 (stating “[t]he locking implemented . . . is performed prior to the grace period detection[.]” Thus, McKenney discloses an embodiment in which a lock is implementing while readers are accessing a shared element. Moreover, McKenney teaches periodically checking for a value (e.g., zero) to see if all operations have terminated (e.g., checking again for the presence of readers). See McKenney § 6.1; see also Ans. 10 (quoting this passage). McKenney also discusses advancing the generation sequence a second time during role reversal of generations to assure that all operations have terminated. See McKenney § 6.1. Both of these are forms of rechecking for the readers. McKenney thus discloses checking again for the presence of readers as recited. The Examiner additionally discusses Figures 7A-B of the present disclosure labeled “Prior Art.” See Ans. 10-11. We do not rely on this teaching in affirming the Examiner’s rejection and need not determine Appeal 2011-002793 Application 11/854,840 6 whether this feature is necessarily a part of McKenney’s disclosed RCU. However, Figures 7A and B teach that the “lock the counter” feature at step 56 and checking again for readers at step 70 is conventional, indicating that this feature was known by ordinarily skilled artisans to be used after detecting readers. See Spec. 16:13-19; 17:12-17; Figs. 7A-B. For the foregoing reasons, Appellant has not persuaded us of error in the rejection of independent claim 1 and independent claims 8 and 14 not separately argued. See App. Br. 16. Claims 2, 9, and 15 Claim 2 recites the checking step comprising consulting a pair of counters that readers manipulate when accessing the shared data element. Contrary to Appellant’s assertion (see Reply Br. 7), the Examiner cites to section 6.1 of McKenney to disclose this recitation. Ans. 5. Appellant admits section 6.1 of McKenney discusses counters but argues McKenney fails to discuss counters that readers manipulate. App. Br. 13. We disagree. As the Examiner explains (Ans. 11-12), McKenney discloses incrementing and decrementing a counter when operations begin and end and two generation counters that are associated with operations. McKenney § 6.1. Given that an operation can be a read operation (e.g., a reader), McKenney discloses that readers manipulate counters. Also, in contrast with the statement in the Appeal Brief (App. Br. 13), Appellant admits that Tornado/K42 counters, addressed above and in McKenney (§ 6.1; § 1, page 3, column 1, full paragraphs 1 and 5), are manipulated by readers. See Reply Br. 7 (citing pages 3 and 15 of McKenney). Thus, McKenney discloses counters that readers manipulate. Appeal 2011-002793 Application 11/854,840 7 For the foregoing reasons, Appellant has not persuaded us of error in the rejection of claim 2 and claims 9 and 15 not separately argued. See App. Br. 16. Claims 3, 10, and 16 Claim 3 depends from claim 2 and further recites that the checking includes summing the counters. The Examiner relies on the global current generation that is incremented based on a comparison with snapshot counters to disclose this limitation. Ans. 5. Appellant argues that there is no disclosure of checking for readers by summing counters. App. Br. 14. We agree with Appellant. The passage cited by the Examiner (Ans. 5) discusses copying counters to “snapshot” counters. McKenney § 6.2, page 17. When any counter differs from the snapshot, the CPU’s bit is cleared. Id. If its bit is the last one set, McKenney further discusses incrementing a global current generation. Id. However, these discussions do not address summing the counters (e.g., two generation counters) discussed above in connection with claim 2. Furthermore, the Examiner has not demonstrated that McKenney’s pair of counters discussed in § 6.1 are summed. See Ans. 5, 12. For the foregoing reasons, Appellant has persuaded us of error in the rejection of claim 3 and claims 10 and 16 which recite commensurate limitations. Appeal 2011-002793 Application 11/854,840 8 Claims 4-7, 11-13, and 17-202 Clams 4-7, 11-13, and 17-20 depend directly or indirectly from claims 3, 10, and 16. Because we reverse the Examiner’s anticipation rejection of claims 3, 10, and 16, we likewise will not sustain the rejections of claims 4-7, 11-13, and 17-20. CONCLUSION Under § 102, the Examiner did not err in rejecting claims 1, 2, 8, 9, 14, and 15 but erred in rejecting claims 3-7, 10-13, and 16-20. DECISION The Examiner’s decision rejecting claims 1-20 is affirmed-in-part. No time period for taking any subsequent action in connection with this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv). AFFIRMED-IN-PART msc 2 Should prosecution continue the Examiner should consider whether claims 14-20 are statutory under § 101. See Spec. 19:11-16 (indicating “media” includes propagation signal or medium); see also In re Nuijten, 500 F.3d 1346, 1357 (Fed. Cir. 2007). Copy with citationCopy as parenthetical citation