DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Remarks
The present application having Application No. 18/757,299 filed on 6/27/2024 presents claims 21-40 for examination.
Claims 1-20 have been canceled via preliminary amendment.
The present application is a continuation of, and claims priority to, US Patent Application No. 18/341,588, filed June 26,2023, which is a continuation of U.S. Patent Application No. 17/547,505, filed December 10, 2021, now U.S. Patent No 11,726,838, which is a continuation of, and claims priority to, U.S. Patent Application No. 16/1791,178 (now issued patent US 11,221,891 B2), filed on February 14, 2020; which is a continuation of, and claims priority to U.S. Patent Application No. 15/298,090 filed on October 19, 2016, now issued U.S. Patent No. 10,565,024 B2.
Examiner Notes
Examiner cites particular columns and line numbers in the references as applied to the claims below for the convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested that, in preparing responses, the applicant fully consider the references in entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner.
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
Priority
As required by M.P.E.P. 201.14(c), acknowledgement is made of applicant’s claim for priority based on parent U.S. Patent Application No. 16/791,178, filed on February 14, 2020 and U.S. Patent Application No. 15/298,090, filed on October 19, 2016.
Drawings
The applicant’s drawings submitted are acceptable for examination purposes.
Information Disclosure Statement
As required by M.P.E.P. 609, the applicant’s submissions of the Information Disclosure Statements dated 09/13/2024 and 11/18/2024 are acknowledged by the examiner and the cited references have been considered in the examination of the claims now pending.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 21-23, 28-30 and 35-37 are rejected under 35 U.S.C. 103 as being unpatentable over Andrew Michael Jones (US 2003/0061224 A1) (hereinafter Jones) in view of Dice et al. (US 2014/0258645 A1) (hereinafter Dice).
As per claim 21, Jones discloses A computer-implemented method, comprising: performing, responsive to a thread of a multithreaded application requesting allocation of a lock, adding a node representing the thread to a queue (e.g. Jones: [0001] the present invention relates to a processing system/method having means for storing a plurality of items defining a queue. [Fig. 1] [0024] the system comprises four CPUs 2-8 respectively. Each of these CPUs is arranged to execute a different stream of instructions…Each stream is referred to as a thread. Each thread may wish to perform a queue operation on a queue data structure which resides in a system memory 10. [0038-0039] the queue used in embodiments of the present invention is a link list. A single reader looks after the top of the list which corresponds to the head of the queue and the multiple writers append items to the bottom of the list which corresponds to the tail of the queue…each item in the list contains pointer to the next item on the list. Jones teaches a thread performing a queue operation and appending/adding an item/node to a linked-list queue.), comprising: executing an atomic swap instruction to add the node representing the thread to a tail of the queue (e.g. Jones: [0038] discloses the multiple writers append items to the bottom of the list which corresponds to the tail of the queue. [0043] discloses each time a writer wants to add an item to the queue, a pointer to the item with the back pointer is swapped with the new item…The items are added to the queue in the order in which their associated swaps were received by the memory controller which controls access to the memory area in which the queue reside. [0044] The swap operation is one which performs an atomic read-modify-write of a data item in the memory/queue. [0059-0061] In the code, lines 7-15 provide a C like functional definition of the swap primitive. This function is performed atomically. [code lines 1-18] provide a definition of a swap primitive…the writer routine [code line 42] ”PrevBack = swap(Back,item); /*make back point to item*/. Thus, Jones teaches an atomic swap instruction that exchanges a pointer to the new item with the back pointer, thereby making the new item the tail of the queue; and using atomic swap instruction to insert/add new item/node at the tail/back of the queue.); responsive to a result of the atomic swap instruction indicating that no nodes are present in the queue, setting an indication that the node is at the head of the queue (e.g. Jones: [0059, code lines 33-58] “41 item->next = NULL ; 42 PrevBack = swap(Back,item) ; /* make back point to item */ 43 if (PrevBack != NULL) { /* queue has been used */ 44 terminal = swap(PrevBack->next,item) ; 45 switch(terminal) 46 base NULL /* queue was non- empty */ 47 break; 48 case DONE /* queue was empty */ 49 front = item ; 50 reschedule(reader) ; 51 break ; 52 default /* queue is invalid */ 53 exit (1) ; 54 } 55 else { /* list in initial state */ 56 front = item ; 57 Run(reader) ; 58 }” [0064] “The writer process is described in lines 33 to 58 and describes how items are added to the queue. The item is declared and initialised in lines 34 to 41. One of the key operations is defined in line 42. Here a pointer to the item to be inserted is swapped witty the back pointer making this item the end of the queue. There are now two possibilities based on the state of the previous value of the back pointer. If it was previously null then the queue has moved out of its initial state as indicated in line 43. In line 44, the node which was tail of the list immediately prior. to the inserted item has its next field made to point to the inserted item. This effectively adds the inserted item onto the end of the list. If this next field is null, then the queue was not empty and nothing more needs to be done. If on the other hand, this field has the value done, then the queue is previously empty. The writer can infer that the reader is de-scheduled and hence writes a pointer to its item into the front pointer making this item into the head of the queue before rescheduling this reader process in lines 49 and 50. In the event that the writer finds a queue in it. initial state, line 55, it writes a pointer to its item into the front pointer (line 56) to make this item the head of the queue before running the reader process for the first time in line 57.” Explanation: The swap returns a previous value (terminal) indicating whether the queue was empty (DONE) or non-empty. When terminal indicates an empty queue (DONE) or initial state, Jones sets front = item, making the inserted node the head of the queue. This corresponds to “result…indicating that no nodes are present in the queue” and “setting an indication that the node is at the head of the queue.”); and responsive to the result of the atomic swap instruction indicating that one or more nodes are present in the queue, linking the node to a predecessor node identified by the result of the atomic swap instruction (e.g. Jones: [0059] [0064] “26 if (successor==NULL) 27 deschedule( ) ; 28 else 29 front = successor ; 30 } 31 32 } 33 void insert (text) 34 char *text; /* the data to be written */ 35 { 36 struct node *item; /* allocation omitted */ 37 struct node *PrevBack ; 38 struct node *terminal ; 39 40 item->data = text ; 41 item->next = NULL ; 42 PrevBack = swap(Back,item) ; /* make back point to item */ 43 if (PrevBack != NULL) { /* queue has been used */ 44 terminal = swap(PrevBack->next,item) ; 45 switch(terminal) 46 base NULL /* queue was non- empty */ 47 break;” “ In line 44, the node which was tail of the list immediately prior. to the inserted item has its next field made to point to the inserted item. This effectively adds the inserted item onto the end of the list. If this next field is null, then the queue was not empty and nothing more needs to be done.” The previous value PrevBack returned by the swap identifies “the node which was tail of the list immediately prior to the inserted item.” Jones then updates that node’s next field to point to the new item, effectively linking the new node to the predecessor node identified by the swap result when the queue is non-empty.).
Jones discloses a multithreaded application, executing atomic swap instructions, determining whether the queue is empty or non-empty, thread adding items to a queue and linking the item/node to a predecessor item/node as claimed. Jones does not expressly disclose “a thread of a multithreaded application requesting allocation of a lock,” “adding a node representing the thread.”
However, Dice expressly disclose discloses performing, responsive to a thread of a multithreaded application requesting allocation of a lock, adding a node representing the thread to a queue (e.g. Dice: [Abstract] [0008] “An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer… A thread of an application that wishes to acquire the lock (for reading or writing) may invoke a locking procedure to insert a new node in the list of nodes.” [0087] discloses method may include the thread inserting its node as the new tail of the ordered list. A thread wishing to access a critical section protected by a lock inserts a node into the ordered list of nodes representing threads that have acquired or wish to acquire the lock. Also see [0009] [0030] [0037][Figs. 7A-7K][0059-0067].).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Jones by incorporating the teaching of Dice because Dice provides a specific and useful application for Jone’s known atomic-swap queue insertion technique. Jones already teaches hot to atomically insert a node at the tail of a queue, detect whether the queue was empty, and link the new node to the prior tail when the queue was not empty. Dice teaches that a lock-acquisition structure may be implemented as an ordered list of nodes representing threads that hold or desire a lock, with a tail pointer. Combining Dice into Jones would advantageously adapt Jones’s insertion mechanism to a lock queue so that thread nodes can be enqueued efficiently when a thread requests allocation of a lock, while preserving Jones’ atomic empty/non-empty handling and predecessor linking. In other words, Dice supplies the lock-waiter use case, and Jones supplies the atomic swap enqueue mechanism; their combination yields a predictable and scalable lock-queue insertion structure. Under KSR, applying a known lock-node queue structure of Dice to the known queue-insertion technique of Jones would have been obvious because it is a substitution of one known concurrent queue insertion technique into another known concurrent lock queue, with the predictable benefit of efficient atomic tail insertion and reduced contention.
As per claim 22, the combination of Jones and Dice discloses The method of claim 21 [See rejection to claim 21 above], wherein the queue comprises a linked list of zero or more nodes, wherein the tail of the queue comprises: a pointer to a last node in the queue if the linked list comprises one or more nodes; or a NULL value if the linked list comprises zero nodes (e.g. Jones: [0038] discloses queue data structure used in embodiments of the present invention is a link list. [0039] “ The queue is provided with two pointers 24 and 26. In particular, there is a front pointer 24 which indicates the head of the queue and a back pointer 26 which indicates the tail of the queue. The front and back pointer each comprise two parts. The first identifies which item is at the front and back of the queue respectively and the second part identifies if the item pointed to is done, has a valid pointer or a null pointer.” [0045] “The initial stare is distinguished by either or both of the front and back pointers being null. The queue is empty if the pointer slot of the item pointed to by the back pointer has the value done in its field. The list is not empty if the front pointer points to the first item and the back pointer points to the last item on the list which has the value null in its pointer slot.” Also see [0059, code lines 1-58]. Jones expressly teaches a linked-list queue with head and tail pointers, where the tail identifies the last node in a non-empty queue and can be null/done in the empty queue state. Dice: [0030] [0036-0037] [0039] [0045, code lines 1-52] [0059-0066].).
As per claim 23, the combination of Jones and Dice discloses The method of claim 21 [See rejection to claim 21 above], wherein setting the indication that the node is at the head of the queue further comprises: setting a head of the queue to identify the node; and setting an indicator within the node to identify that the node is at the top of the queue (e.g. Jones: [0063-0064] “ If on the other hand, this field has the value done, then the queue is previously empty. The writer can infer that the reader is de-scheduled and hence writes a pointer to its item into the front pointer making this item into the head of the queue before rescheduling this reader process in lines 49 and 50. In the event that the writer finds a queue in it. initial state, line 55, it writes a pointer to its item into the front pointer (line 56) to make this item the head of the queue” Also see [0038] [0050] [0059, code lines 49-50]. Also see Dice: [0050]).
As per claims 28-30, these are system claims having similar limitations as cited in method claims 21-23, respectively. Thus, claims 28-30 are also rejected under the same rationale as cited in the rejection of rejected claims 21-23, respectively.
As per claims 35-37, these are medium claims having similar limitations as cited in method claims 21-23, respectively. Thus, claims 35-37 are also rejected under the same rationale as cited in the rejection of rejected claims 21-23, respectively.
Claims 24, 31 and 38 are rejected under 35 U.S.C. 103 as being unpatentable over Andrew Michael Jones in view of Dice and further in view of Christopher P. Ruemmler (US 2008/0184238 A1) (hereinafter Ruemmler).
As per claim 24, the combination of Jones and Dice discloses The method of claim 23 [See rejection to claim 23 above], wherein adding the node representing the thread to the queue (e.g. Jones: [0038] discloses the multiple writers append items to the bottom of the list which corresponds to the tail of the queue. [0043] discloses each time a writer wants to add an item to the queue, a pointer to the item with the back pointer is swapped with the new item…The items are added to the queue… Dice: [Abstract] [0008] “An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer… A thread of an application that wishes to acquire the lock (for reading or writing) may invoke a locking procedure to insert a new node in the list of nodes.” [0087] discloses method may include the thread inserting its node as the new tail of the ordered list. As discussed above, Jones teaches queue insertion by threads using an atomic swap to append an item/node to the tail of a linked-list queue. Dice teaches that the ordered list contains nodes representing threads that hold or desire to acquire the lock, and that such nodes are inserted into the list as part of the lock protocol.).
The combination of Jones and Dice does not expressly disclose determining that the thread should not be placed in an active set of threads requesting allocation of the lock, and wherein the queue comprises a passive set of threads that are respectively not able to actively contend for the lock.
However, Ruemmler discloses wherein adding the node representing the thread to the queue is performed responsive to determining that the thread should not be placed in an active set of threads requesting allocation of the lock, and wherein the queue comprises a passive set of threads that are respectively not able to actively contend for the lock (e.g. Ruemmler: [0003] discloses when a thread is placed in the sleep state, the thread is deactivated by a scheduler until a given event occurs such as, for example, the expiration of sleep time period. In the sleep state, the thread is typically placed in a queue of threads waiting for the lock. When a thread is placed in the sleep state, the thread does not consume processor time. [0016-0020] discloses a scheduler can dynamically place any thread in a busy waiting state [active set] or a sleep state [passive set]. [0021-0022] [0027-0028] A scheduler can dynamically decides whether a requester will be allowed to busy-wait or instead go into the sleep state based on the current number of allowed busy waiters or the presence of waiters when the lock is released. When the busy-wait ceiling is zero, a contending thread will go into the sleep state, and when the ceiling permits, the thread becomes a busy waiter. This is a direct functional analogue to deciding whether a thread should be in the active contending set or non-contending sleep state.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Ruemmler with Jones and Dice because Jones and Dice already teach a nod-based lock queue for threads that wish to acquire a lock, while Ruemmler teaches a known a known technique for controlling which threads should be allowed to be active for lock contention versus passive based on runtime contention conditions. Applying Ruemmler’s busy-wait/sleep selection to the Jones/Dice queue would predictably improve throughput and reduce wasted processing power by limiting the number of threads actively contending for the lock (see Ruemler [0017] [0020].). Thus, A POSITA would have recognized that the passive/active split in Ruemmler is a natural extension of the queue-based lock structures of Jones/Dice, because all three references address lock acquisition and contention management among threads. The combination would have required only a straightforward substitution of one known contention-management policy for another within the same locking framework.
As per claim 31, this is a system claim having similar limitations as cited in method claim 24. Thus, claim 31 is also rejected under the same rationale as cited in the rejection of rejected claim 24.
As per claim 38, this is a medium claim having similar limitations as cited in method claim 24. Thus, claim 38 is also rejected under the same rationale as cited in the rejection of rejected claim 24.
Allowable Subject Matter
Claims 25-27, 32-34, 39 and 40 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
The following prior art made of record and not relied upon is cited to establish the level of skill in the applicant’s art and those arts considered reasonably pertinent to applicant’s disclosure. See MPEP 707.05(c).
Venkatasubramanian (US 2003/0236816 A1) – discloses “A spin-yield cycle includes spinning, unsuccessfully acquiring the lock, yielding the processor, and being transferred to the run queue, normally at its end. For example, thread 110W(1), while waiting for a lock, spins for some time, then tries to acquire the lock. If thread 110W(1) acquires the lock, then thread 110W(1) becomes a thread 110L that has a lock and prevents other threads from acquiring the same lock. However, if thread 110W(1) cannot acquire the lock, then thread 110W(1) yields the spin-yield processor 130(1) for use by another waiting thread 110W, and is transferred to the run queue waiting to again run or spin on a spin-yield processor. Thread 110W(1) then repeats spinning, trying to acquire the lock, yielding the processor, and being transferred to the run queue several times, up to a thresholdt.sub.2 at which time thread 110W(1) is put in the sleep queue. Similar to the above-discussed thresholdt.sub.1, threshold t.sub.2 may be in real time or in other time units. In one embodiment, thread 110W(1) repeats the spin-yield cycles on the same spin-yield processor, e.g., processor 130(1).”
Calciu et al. (2013/0290967 A1; US 8,966,491 B2) – discloses maintaining an active queue of threads and a passive queue of threads, where current owner of the lock hands off lock ownership to another thread from the active queue of threads. When the list of threads in the active queue becomes empty, the threads from the passive queue are enqueued into the active queue. The lock owners may rotate or swap the active and passive lists, and may release the lock to other threads in the active queue. Fig. 8 discloses a method for managing access to a critical section of code or a shared resource using a NUMA-aware lock that includes such active and passive lists of waiters is illustrated by the flow diagram in FIG. 8. As illustrated in this example, the method may include a thread on an active list of waiting threads (i.e. a list of threads waiting to acquire a cluster-specific lock for a critical section of code or shared resource) acquiring the cluster-specific lock and acquiring a global shared lock for the critical section of code or shared resource (as in 810). In this example, threads arriving at the cluster-specific lock subsequent to the thread acquiring the global shared lock may enqueue on a passive list of waiting threads (i.e. an alternate list of threads that are waiting to acquire the cluster-specific lock), as in 820. In other words, each cluster-specific lock associated with a critical section of code or shared resource may include two lists of waiting threads: an active list, and a passive list. If there are no other threads on the active waiting list for the same cluster (or once the active list has been depleted), shown as the negative exit from 840, the method may include the passive list becoming active list and vice versa (as in 850). In this case, threads that arrive at the cluster-specific lock subsequent to this swap may enqueue on the newly empty passive list (i.e. the list that was formerly the active list, but that has been depleted). The method may also include the thread that holds the cluster-specific lock releasing the global shared lock and then releasing the cluster-specific lock, as in 880. In other words, once there are no additional threads waiting on the active list for the cluster-specific lock, the thread holding the cluster-specific lock may cause the active and passive lists to be swapped and may give up the global shared lock to enable the potential subsequent acquisition of the global shared lock by a thread executing on the same or another cluster.
AI et al. (US 2016/0092280 A1) – discloses A method for operating a lock in a computing system having plural processing units and running under multiple runtime environments is provided. When a requester thread attempts to acquire the lock while the lock is held by a holder thread, determine whether the holder thread is suspendable or non-suspendable. If the holder thread is non-suspendable, put the requester thread in a spin state regardless of whether the requester thread is suspendable or non-suspendable; otherwise determines whether the requester thread is suspendable or non-suspendable unless the requester thread quits acquiring the lock. If the requester thread is non-suspendable, arrange the requester thread to attempt acquiring the lock again; otherwise add the requester thread to a wait queue as an additional suspended thread. Suspended threads stored in the wait queue are allowable to be resumed later for lock acquisition.
Duvuru et al. (US 9,830,200 B2) – discloses access to the shareable resource is controlled by a passive lock comprising a sequence of an outer busy lock and an inner busy lock, a first one of said concurrently executing thread wanting exclusive control of the shareable resource acquiring the outer busy lock, followed by the inner busy lock, the system further comprising: on releasing control of the passive lock, means for said first one of said concurrently executing thread to acquire the inner busy lock and determine the number of concurrently executing threads waiting for exclusive control of the shareable resource; and wherein, responsive to a determination that the number of concurrently executing threads waiting for exclusive control of the shareable resource exceeds a pre-determined value, for said first concurrently executing thread passing ownership of the passive lock and the inner busy lock to the concurrently executing thread located at the front of a system ready queue.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Hiren Patel whose telephone number is (571) 270-3366. The examiner can normally be reached on Monday to Friday 9:30 AM to 6:00 PM.
If attempts to reach the above noted Examiner by telephone are unsuccessful, the Examiner’s supervisor, Emerson Puente, can be reached at the following telephone number: (571) 272-3652.
The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300. Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free)?
July 25, 2026
/HIREN P PATEL/Primary Examiner, Art Unit 2196
Prosecution Insights