DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending in this application.
Response to Arguments
Applicant’s arguments regarding the rejections of claims 1-20 under 35 U.S.C. 112b have been fully considered and some are persuasive. Some of the rejections have been withdrawn. New 35 U.S.C. 112b rejections are applied to claims 1-6 and 14-20.
Applicant's arguments regarding the 35 U.S.C. 103 rejections of claims 1-20 have been fully considered but are unpersuasive.
Regarding the 35 U.S.C. 103 rejection, the applicant argues the following in the remarks:
Hung does not disclose that waituntil(P) waits on a condition variable.
In Hung, the waituntil(P) statement does not include the derived predicate but instead provides the global predicate.
Examiner has thoroughly considered Applicant' s arguments, but respectfully finds them unpersuasive for at least the following reasons:
As to point (a), the examiner respectfully disagrees. Figure 4 of Hung shows that predicate P is a condition variable.
As to point (b), the examiner argues that the derived predicate is just a different format in which the global predict is written and that the derived predicate evaluates the same logic.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-6 and 14-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
As per claim 1:
Lines 9-11 recite “indicating whether the wait on the change to the condition variable by the first thread, on the change to the condition variable” but this language is redundant and unclear.
As per claims 2 and 4 (line numbers refer to claim 2):
Line 5 recites “while first thread is in the non-runnable state” but lines 15-16 and 19 recite “the third thread is in the non-runnable state” so it is unclear if the first thread or the third thread is in the non-runnable state.
As per claim 14:
Lines 5-6 recite “waiting on the change to the condition variable” but lines 16-17 recite “the wait the condition” so it is unclear if there is a wait on the condition or condition variable.
As per claim 15:
Line 4 recites “another thread” but it unclear what this refers to since claim 14 which claim 15 depends upon recites individual threads of a plurality of threads and a different thread.
As per claim 19:
Lines 3-4 recite “the condition” but it is unclear what it refers to.
Claims 2-6 and 15-20 are dependent claims of 1 and 14 and they fail to resolve the deficiencies of claims 1 and 14, so they are rejected for the same reasons as claims 1 and 14.
.
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, 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 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Marathe et al. (US 20120311273 A1 herein Marathe) in view of Hung et al. (Automatic-Signal Monitors with Multi-object Synchronization hereinafter Hung).
Marathe and Hung were cited in a previous office action.
As per claim 1, Marathe teaches a system, comprising:
at least one processor (Fig. 9, 930 processor(s));
a memory, comprising program instructions that when executed by the at least one processor cause the at least one processor to implement a multi-threaded application configured to (Fig. 9, 910 memory, 920 program instructions; [0080] Recall that the application consists of a client transaction that collaborates with a concurrent database transaction to process a request atomically; [0052] multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; [0083] a consumer (i.e. a database thread 630)… a producer (i.e. a client thread 610); [0109] In some embodiments, system memory 910 may include program instructions 920, which may include a transaction support library 955. Program instructions 920 may also include a compiled application 925, which may include executable program code specifying one or more atomic transactions):
request, by a first thread of the multi-threaded application over a programmatic interface, to wait on a change to a condition variable, a function that, when executed, returns a value indicating whether the wait on the change to the condition variable, by the first thread on the change to the condition variable is to be terminated, and wherein the programmatic interface and the function are different (Fig. 4; [0090] lines 4-6 the existing Java monitors API may be leveraged in the implementation of the txwait, txnotify, and txnotifyAll methods; [0046] In some embodiments, a transaction calling a wait method (e.g., txwait) on a transaction condition variable (e.g., an xCondition) may be added to the wait list of the transaction condition variable; [0083] lines 2-4 a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty; claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction pending notification of a notification event from a notify method of the transaction condition variable; the notifier transaction invoking the notify method of the transaction condition variable, wherein the notify method notifies the waiter transaction of a notification event; and in response to receiving the notification of the notification event, the waiter transaction: resuming execution; claim 7 wherein said resuming execution comprises evaluating a condition of a transaction communicator object; [0014] lines 16-18 waiter transaction may evaluate a condition of a transaction communicator object and may invoke the wait method a second time; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0055] lines 2-21 a notifier subsequently waits on a condition of a communicator object or transaction condition variable that is satisfied by the transaction it previously notified…both transaction A and transaction B have access to a transaction condition variable X and a transaction condition variable Y. In this example, transaction A (for which events and/or operation are shown along timeline 410) invokes a wait method of transaction condition variable X (at time 411) and is suspended shortly thereafter (at time 413). At some point subsequent to transaction A invoking the wait method of transaction condition variable X (e.g., at time 421), transaction B invokes a notify method of transaction condition variable X, notifying transaction A of this notification event. In response to the notification, execution of transaction A is resumed; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution; [0109] lines 5-9 executable program code specifying one or more atomic transactions that perform accesses to one or more transaction communicator objects and/or transaction condition variables, and which may include calls to functions of transaction support library; [0077] However, in such implementations, a consumer waiting for an item to be produced may simply "spin" until the queue is nonempty, and then the consumer could claim the item; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); The programmatic interface is different from the function because the programmatic interface is an API and the function evaluates a condition variable.);
place the first thread in a non-runnable state (claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction); and
execute, by a thread of the multi-threaded application, the function to determine whether the wait on the change to the condition variable by the first thread should be terminated, and responsive to the executing ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution; [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time;):
leave the first thread in the non-runnable state responsive to determining that the wait on the change to the condition variable, by the first thread, should not be terminated ([0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 12-21 In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended…a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event; [0080] Recall that the application consists of a client transaction that collaborates with a concurrent database transaction to process a request atomically; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0073] the CIT may read a value of the communicator object to determine whether it is an expected or desired value; [0083] one or more of the database threads 630 are waiter transactions;); and
place the first thread in a runnable state responsive to determining that the wait on the change to the condition variable, by the first thread, should be terminated ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied…For example, consider a simple condition synchronization idiom in which X is a transaction condition variable, and one thread executes a waiter transaction; [0100] lines 6-12 The CIT checks for a desired condition on a communicator object, as in 810. For example, the CIT may read a value of the communicator object to determine whether it is an expected or desired value. If the condition is met, shown as the positive exit from 820, the CIT may reset the communicator object value, continue execution; [0080] Recall that the application consists of a client transaction that collaborates with a concurrent database transaction to process a request atomically; [0083] one or more of the database threads 630 are waiter transactions; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution).
Marathe fails to teach wherein the request comprises a function that, when executed, returns a value indicating whether the wait on the change to the condition variable, by the first thread, on the change to the condition variable is to be terminated; execute, by a second thread, the function while the first thread in in the non-runnable state to determine whether the wait on the change to the condition variable by the first thread should be terminated.
However, Hung teaches wherein the request comprises a function that, when executed, returns a value indicating whether the wait on the change to the condition variable, by the first thread, on the change to the condition variable is to be terminated; execute, by a second thread, the function while the first thread in in the non-runnable state to determine whether the wait on the change to the condition variable by the first thread should be terminated (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument. The thread waits if the condition is false and our system will signal it automatically when the condition has become true; Section IV.B. paragraph 1 for any global predicate P, we can derive a predicate P^…For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition…Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section I paragraph 2 Many applications require a certain action to be taken only if a condition that spans multiple objects is true. We call such a condition, a global condition or a global predicate; Section I paragraph 1 multiple threads waiting on that condition).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Marathe with the teachings of Hung to promote efficiency (see Hung abstract allows efficient monitoring of the conditions).
As per claim 2, Marathe and Hung teach the system of claim 1. Marathe specifically teaches wherein the multi-threaded application is further configured to ([0052] multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0098] This programming idiom may be typical for single-producer, multiple-consumer applications):
request, by a third thread of the multi-threaded application over the programmatic interface, to wait on the change to the condition variable while the first thread is in the non-runnable state, function that, when executed, returns another value indicating whether the wait by the third thread on the change to the condition variable is to be terminated, and wherein the programmatic interface and the function are different (Fig. 6, 630 database threads; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; abstract 8-14 A waiter transaction may invoke a wait method of a transaction condition variable, be added to a wait list for the variable, and be suspended pending notification of a notification event from a notify method of the variable. A notifier transaction may invoke a notify method of the variable, which may remove the waiter from the wait list, schedule the waiter transaction for resumed execution; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter…and in response to receiving the notification of the notification event, the waiter transaction: resuming execution; claim 7 wherein said resuming execution comprises evaluating a condition of a transaction communicator object; [0095] lines 1-11 If the attempt to commit transaction A is unsuccessful (i.e. if transaction A aborts), shown as the positive exit from 750, the method may include determining whether there are any other transactions waiting for a notification for the transaction condition variable that were waiting at the time transaction A received its notification, as in 760. For example, if the version identifier value logged by another one of the transactions on the wait list for the transaction condition variable indicates that the other transaction (as another thread) was waiting on notification for the transaction condition variable when transaction A received its notification; [0090] lines 5-6 Java monitors API (as programmatic interface) may be leveraged in the implementation of the txwait; [0083] lines 2-4 a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty; [0046] In some embodiments, a transaction calling a wait method (e.g., txwait) on a transaction condition variable (e.g., an xCondition) may be added to the wait list of the transaction condition variable; [0077] However, in such implementations, a consumer waiting for an item to be produced may simply "spin" until the queue is nonempty, and then the consumer could claim the item; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions; [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; The programmatic interface is different from the function because the programmatic interface is an API and the function evaluates a condition variable.), and
responsive to the request: place the third thread in the non-runnable state ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter); and
execute the function to determine whether the wait on the change to the condition variable by the third thread on the condition should be terminated, and responsive to the executing: leave the third thread in the non-runnable state responsive to determining that the wait on the change to the condition variable should not be terminated ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 12-21 In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended…a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable); and
place the third thread in the runnable state responsive to determining that the wait on the change to the condition variable should be terminated ([0046] lines 14-18 If a transaction invokes a method to notify all transactions that are waiting on a given transaction condition variable (e.g., txnotifyAll), then all transactions on the wait list may be notified, removed from the wait list, and scheduled for execution; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied).
Additionally, Hung teaches wherein the request by the third thread comprises another function that, when executed, returns another value indicating whether the wait by the third thread on the change to the condition variable is to be terminated, and wherein the programmatic interface and the other function are different; execute the other function while the third thread is in the non-runnable state (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true).
As per claim 3, Marathe and Hung teach the system of claim 2. Marathe specifically teaches wherein the multi-threaded application is further configured to submit, over the programmatic interface, a request to broadcast the change to the condition variable to the first thread and the third thread ([0046] lines 14-18 If a transaction invokes a method to notify all transactions that are waiting on a given transaction condition variable (e.g., txnotifyAll), then all transactions on the wait list may be notified, removed from the wait list, and scheduled for execution; [0090] lines 26-28 txnotifyAll method may simply apply the txnotify method on all of the waiters for a target xCondition; [0083] lines 8-13 a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0055] lines 2-5 a notifier subsequently waits on a condition of a communicator object or transaction condition variable that is satisfied by the transaction it previously notified; [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; [0083] a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620; ; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads)).
As per claim 4, Marathe and Hung teach the system of claim 1. Marathe teaches wherein the multi-threaded application is further configured to: request, by a third thread of the multi-threaded application over the programmatic interface to wait on the change to the condition variable while the first thread is in the non-runnable state, a function that, when executed, returns another value indicating whether the wait by the third thread on the change to the condition variable is to be terminated, and wherein the programmatic interface and the function are different (Fig. 6, 630 database threads; claim 11 A system comprising: one or more processors; and memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform: executing a plurality of concurrent transactions, wherein the plurality of transactions comprises a waiter transaction and a notifier transaction; the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction pending notification of a notification event from a notify method of the transaction condition variable; the notifier transaction invoking the notify method of the transaction condition variable, wherein the notify method notifies the waiter transaction of a notification event; and in response to receiving the notification of the notification event, the waiter transaction: resuming execution; claim 15 The system of claim 11, wherein said resuming execution comprises evaluating a condition of a transaction communicator object; [0095] lines 1-11 If the attempt to commit transaction A is unsuccessful (i.e. if transaction A aborts), shown as the positive exit from 750, the method may include determining whether there are any other transactions waiting for a notification for the transaction condition variable that were waiting at the time transaction A received its notification, as in 760. For example, if the version identifier value logged by another one of the transactions on the wait list for the transaction condition variable indicates that the other transaction (as another thread) was waiting on notification for the transaction condition variable when transaction A received its notification; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0090] lines 4-6 the existing Java monitors API may be leveraged in the implementation of the txwait, txnotify, and txnotifyAll methods; [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; [0077] However, in such implementations, a consumer waiting for an item to be produced may simply "spin" until the queue is nonempty, and then the consumer could claim the item; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable); The programmatic interface is different from the function because the programmatic interface is an API and the function evaluates a condition of a transaction communicator object.), and
responsive to the request: place the third thread in the non-runnable state ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter); and
execute the function responsive to determining that the wait on the change to the condition variable, by the first thread should not be terminated; leave the third thread in the non-runnable state responsive to determining that the wait on the change to the condition variable should not be terminated ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied); and
place the third thread in the runnable state responsive to determining that the wait on the change to the condition variable should be terminated ([0046] lines 14-18 If a transaction invokes a method to notify all transactions that are waiting on a given transaction condition variable (e.g., txnotifyAll), then all transactions on the wait list may be notified, removed from the wait list, and scheduled for execution; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied).
Additionally, Hung teaches the request by the third thread comprises another function that, when executed, returns another value indicating whether the wait by the third thread on the change to the condition variable is to be terminated, and wherein the programmatic interface and the other function are different; execute the other function while the third thread is in the non-runnable state responsive to determining that the wait on the change to the condition variable should not be terminated; leave the third thread in the non-runnable state responsive to determining that the wait on the change to the condition variable should not be terminated; place the third thread in the runnable state responsive to determining that the wait on the change to the condition variable should be terminated (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true).
As per claim 5, Marathe and Hung teach the system of claim 4. Marathe specifically teaches wherein the multi-threaded application is further configured to submit, over the programmatic interface, a request to signal the change to the condition variable to at least one of the first thread and the third thread ([0046] lines 5-11 When a transaction invokes a notify (as signal) method (e.g., txnotify) on a transaction condition variable (e.g., an xCondition), the runtime may determines whether there are any transactions on the wait list of the transaction condition variable. If so, the notifier transaction (e.g., via the runtime) may notify such a transaction, removing it from the wait list, and scheduling it for execution (i.e. for resumed execution; [0049] lines 7-14 each transaction condition variable may be associated with a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable; [0053] lines 17-19 a notify method that signals a single transaction of the notification (e.g., the first one of the waiter transactions on the wait list); [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied (as change); [0083] lines 2-4 a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty; [0090] lines 4-6 the existing Java monitors API may be leveraged in the implementation of the txwait, txnotify, and txnotifyAll methods; [0055] lines 2-5 a notifier subsequently waits on a condition of a communicator object or transaction condition variable that is satisfied by the transaction it previously notified; [0098] This programming idiom may be typical for single-producer, multiple-consumer applications; [0083] a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads);).
As per claim 6, Marathe and Hung teach the system of claim 1. Marathe specifically teaches wherein the multi-threaded application is further configured to: request, by a third thread of the multi-threaded application over the programmatic interface, to wait on the change to the condition variable, wherein to implement the additional request to wait on the condition variable the multi-threaded application is configured to: generate function that, when executed, returns another value indicating whether the wait on the change to the condition variable is to be terminated; request the wait on the change to the condition variable (Fig. 6, 630 database threads; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; [0083] lines 2-4 a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty; [0090] lines 4-6 the existing Java monitors API may be leveraged in the implementation of the txwait, txnotify, and txnotifyAll methods; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0053] lines 11-17 a transaction B (which, with respect to the particular transaction condition variable is a notifier transaction) may call a notify method of the transaction condition variable, as in 320. Note that this notify method may be a notify-all method (in which case it may notify all waiter transactions on the wait list associated with the transaction condition variable of the notification event); [0098] This programming idiom may be typical for single-producer, multiple-consumer applications;).
Additionally, Hung teaches generate another function that, when executed, returns another value indicating whether the wait on the change to the condition variable is to be terminated; the request comprising the other function (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true).
As per claim 7, Marathe teaches a method, comprising: requesting by a first thread to wait on a change to a condition variable, instructions that, when performed, indicate whether the first thread is to be unblocked ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions);
blocking the first thread (claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction); and
performing the instructions ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0102] lines 1-4 since the communicator object now includes the value that meets the desired condition, the waiter CIT may detect that the condition is met, reset the communicator object value, continue execution);
leaving the first thread blocked responsive to the instructions indicating that the first thread should not be unblocked (Fig. 5; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0073] the CIT may read a value of the communicator object to determine whether it is an expected or desired value;); and
unblocking the first thread responsive to the instructions indicating that the first thread should be unblocked ([0100] lines 6-12 The CIT checks for a desired condition on a communicator object, as in 810. For example, the CIT may read a value of the communicator object to determine whether it is an expected or desired value. If the condition is met, shown as the positive exit from 820, the CIT may reset the communicator object value, continue execution; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied).
Marathe fails to teach requesting by a first thread to wait on a change to a condition variable, the request comprising instructions that, when performed, indicate whether the first thread is to be unblocked; performing the instructions by a second thread while the first thread is blocked.
However, Hung teaches requesting by a first thread to wait on a change to a condition variable, the request comprising instructions that, when performed, indicate whether the first thread is to be unblocked; performing the instructions by a second thread while the first thread is blocked (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Marathe with the teachings of Hung to promote efficiency (see Hung abstract allows efficient monitoring of the conditions).
As per claim 8, Marathe and Hung teach the method of claim 7. Marathe teaches further comprising: requesting by a third thread to wait on the change to the condition variable, instructions that, when performed, indicate if the third thread is to be unblocked ([0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event); [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads));
blocking the third thread ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter);
leaving the third thread blocked responsive to the instructions indicating that the third thread should not be unblocked ([0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 12-21 In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended…a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0073] the CIT may read a value of the communicator object to determine whether it is an expected or desired value); and
unblocking the third thread responsive to the instructions indicating that the third thread should be unblocked ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied…For example, consider a simple condition synchronization idiom in which X is a transaction condition variable, and one thread executes a waiter transaction; [0100] lines 6-12 The CIT checks for a desired condition on a communicator object, as in 810. For example, the CIT may read a value of the communicator object to determine whether it is an expected or desired value. If the condition is met, shown as the positive exit from 820, the CIT may reset the communicator object value, continue execution).
Additionally, Hung teaches requesting by a third thread to wait on the change to the condition variable comprising other instructions that, when performed, indicate if the third thread is to be unblocked; performing the other instructions by the second thread while the other thread is blocked; leaving the third thread blocked responsive to the other instructions indicating that the third thread should not be unblocked; unblocking the third thread responsive to the other instructions indicating that the third thread should be unblocked (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true; Section I paragraph 2 the system to wake the thread up whenever the global condition becomes true).
As per claim 9, Marathe and Hung teach the method of claim 8. Hung teaches wherein the blocking, performing, leaving and unblocking are performed by an fourth thread, responsive to a request to broadcast the change to the condition variable (Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument. The thread waits if the condition is false and our system will signal it automatically when the condition has become true; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 1 for any global predicate P, we can derive a predicate P^…For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition…Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.C. paragraph 2 threads waiting on global predicates must analyze their predicates and keep records before they go to a waiting state).
As per claim 10, Marathe and Hung teach the method of claim 7. Marathe teaches further comprising: requesting by a third thread to wait on the change to the condition variable while the first thread is blocked, wherein the request by the third thread to wait on the change to the condition variable, instructions that, when performed, indicate if the third thread is to be unblocked (Fig. 6, 630 database threads; claim 11 A system comprising: one or more processors; and memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform: executing a plurality of concurrent transactions, wherein the plurality of transactions comprises a waiter transaction and a notifier transaction; the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction pending notification of a notification event from a notify method of the transaction condition variable; the notifier transaction invoking the notify method of the transaction condition variable, wherein the notify method notifies the waiter transaction of a notification event; and in response to receiving the notification of the notification event, the waiter transaction: resuming execution; [0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied);
blocking the third thread ([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter);
performing the instructions responsive to the instructions indicating that the first thread should not be unblocked, and responsive to performing the instructions: leaving the third thread blocked responsive to the instructions indicating that the third thread should not be unblocked (([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; [0074] In the example illustrated in FIG. 5, if the desired condition on the communicator object is not met, shown as the negative exit from 520, the CIT may call a wait method of a transaction condition variable; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied); and unblocking the third thread responsive to the instructions indicating that the third thread should be unblocked ([0046] lines 14-18 If a transaction invokes a method to notify all transactions that are waiting on a given transaction condition variable (e.g., txnotifyAll), then all transactions on the wait list may be notified, removed from the wait list, and scheduled for execution; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied).
Additionally, Hung teaches wherein the request to wait on the change to the condition variable comprises other instructions that, when performed, indicate if the third thread is to be unblocked; performing the other instructions while the third thread is blocked, and responsive to performing the other instructions: leaving the third thread blocked responsive to the other instructions indicating that the third thread should not be unblocked; and unblocking the third thread responsive to the other instructions indicating that the third thread should be unblocked (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true).
As per claim 11, Marathe and Hung teach the method of claim 10. Hung teaches wherein the blocking and performing are performed by a second thread, responsive to a request to signal the change to the condition variable (Section I paragraph 2 the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument. The thread waits if the condition is false and our system will signal it automatically when the condition has become true; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 1 for any global predicate P, we can derive a predicate P^…For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition…Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.C. paragraph 2 threads waiting on global predicates must analyze their predicates and keep records before they go to a waiting state).
As per claim 12, Marathe and Hung teach the method of claim 7. Marathe teaches further comprising: requesting by a third thread to wait on the change to the condition variable, wherein performing the requesting by the third thread to wait on the change to the condition variable comprises submitting a request to wait on the change to the condition variable, instructions that, when performed, indicate that the third thread is to be unblocked (([0052] lines 16-18 multiple threads (which may include one or more notifier transactions, waiter transactions, and/or background threads); [0014] lines 7-11 it may evaluate a condition of a transaction communicator object. In such embodiments, in response to determining that the condition is not met, the waiter transaction may invoke the wait method of the transaction condition variable a second time; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied).
Additionally, Hung teaches the requesting by the third thread to wait on the change to the condition variable comprises submitting a request to wait on the change to the condition variable comprising other instructions that, when performed, indicate that the third thread is to be unblocked (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV paragraph 1 when a thread exits a monitor or goes into waiting state, it checks whether there is some thread waiting on a condition that has become true. If at least one such waiting thread exists, it signals that thread. The predicate evaluation is crucial in deciding which thread should be signaled; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true).
As per claim 13, Marathe and Hung teach the method of claim 7. Marathe specifically teaches wherein the request to wait on the change to the condition variable further comprises additional instructions to perform an operation in a critical section ([0083] lines 2-4 a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty; [0082] lines 6-8 a consumer may use a single CIT (designated as a txcommatomic block) to dequeue a node from the queue (if the queue is not empty); Dequeuing is a critical section because threads access a shared resource.).
As per claim 14, Marathe teaches one or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors cause the one or more processors to implement (Fig. 9, 930 processor(s), 910 memory, 920 program instructions):
evaluating, responsive to a change to a condition variable for individual threads of a plurality of threads waiting on the change to the condition variable, a respective condition (claim 1 the waiter transaction invoking a wait method of a transaction condition variable, wherein the transaction condition variable is a condition variable for which transaction isolation has been relaxed; suspending execution of the waiter transaction pending notification of a notification event from a notify method of the transaction condition variable; the notifier transaction invoking the notify method of the transaction condition variable, wherein the notify method notifies the waiter transaction of a notification event; and in response to receiving the notification of the notification event, the waiter transaction: resuming execution; claim 7 wherein said resuming execution comprises evaluating a condition of a transaction communicator object; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable). In response to calling the wait method, the transaction may be added to the wait list for the transaction condition variable, as in 120. At this point, the waiter transaction may be suspended pending such a notification, as in 130. In various embodiments, a waiter transaction that is suspended may not be scheduled for further execution until it is "woken up" by a notification (e.g., a signal that is passed to the waiter transaction indicating that a notification event has occurred, or that the waiter transaction has been scheduled to resume execution in response to a notification event). In other words, execution of any operations in the waiter transaction that follow the invocation of the wait method in sequential order may be blocked until and unless such notification is received. In response to the waiting transaction being notified of the notification event, it may resume execution, as in 140; [0067] In some embodiments, and in keeping with the spirit of condition synchronization, the implementation of transaction condition variables may allow a waiting thread to be de-scheduled until it is notified. In some embodiments, the implementation may retain the appearance of isolation for the communicator-isolating transactions within which transaction condition variables are accessed; [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0092] As previously noted, in the event of aborting waiters, the system may in some embodiments be configured to forward notifications (and establish corresponding dependencies) correctly. In such embodiments, a version number (stored as a value of a numeric "version" indicator) may be included in each xCondition, and its value may be incremented during a txwait call. In some embodiments, each waiter may log an indication (or identifier) of all the xConditions it has waited on in its own xCondition-list; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable).).
Marathe fails to teach wherein the individual threads of the plurality of threads respectively comprise instructions that when executed, indicate if the waiting on the change to the condition variable of the respective thread is to be terminated, and wherein evaluating the respective condition for a particular thread of the plurality of threads comprises: executing, by a different thread, the instructions of the particular thread while the particular thread is waiting on the change to the condition variable; and terminating the wait on the change to the condition variable of the particular thread responsive to the instructions indicating that the wait on the condition, by the particular thread, should be terminated.
However, Hung teaches wherein the individual threads of the plurality of threads respectively comprise instructions that when executed, indicate if the waiting on the change to the condition variable of the respective thread is to be terminated, and wherein evaluating the respective condition for a particular thread of the plurality of threads comprises: executing, by a different thread, the instructions of the particular thread while the particular thread is waiting on the change to the condition variable; and terminating the wait on the change to the condition variable of the particular thread responsive to the instructions indicating that the wait on the condition, by the particular thread, should be terminated (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Hung teaches that individual threads of the plurality of threads respectively comprise instructions since different threads wait on different predicates.).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Marathe with the teachings of Hung to promote efficiency (see Hung abstract allows efficient monitoring of the conditions).
As per claim 15, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 14. Hung specifically teaches wherein evaluating the respective condition for the particular thread further comprises: executing the respective instructions of another thread of the plurality of threads not waiting on the change to the condition variable while the particular thread is waiting on the change to the condition variable to determine whether the wait on the change to the condition variable, by the other thread, is to be terminated; terminating the wait on the change to the condition variable, by the other thread, responsive to determining that the wait on the change to the condition variable, by the other thread, should be terminated (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true).
As per claim 16, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 15. Marathe teaches wherein the evaluating the respective conditions on which the individual threads of the plurality of threads are performed responsive to receiving a request to broadcast a change of the condition variable ([0053] lines 11-17 a transaction B (which, with respect to the particular transaction condition variable is a notifier transaction) may call a notify method of the transaction condition variable, as in 320. Note that this notify method may be a notify-all method (in which case it may notify all waiter transactions on the wait list associated with the transaction condition variable of the notification event); [0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0092] As previously noted, in the event of aborting waiters, the system may in some embodiments be configured to forward notifications (and establish corresponding dependencies) correctly. In such embodiments, a version number (stored as a value of a numeric "version" indicator) may be included in each xCondition, and its value may be incremented during a txwait call. In some embodiments, each waiter may log an indication (or identifier) of all the xConditions it has waited on in its own xCondition-list; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable)).
As per claim 17, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 14. Hung specifically teaches wherein evaluating the respective condition for the particular thread further comprises: executing the respective instructions of another thread of the plurality of threads while the other thread is waiting on the change to the condition variable responsive to determining that the wait on the change to the condition variable, by the particular thread, should not be terminated; terminating the wait on the change to the condition, by the other thread, responsive to the execution of the respective instructions of the other thread indicating that the wait on the change to the condition, by the other thread, should be terminated (Fig. 2; Fig. 4; Figure 4 shows that predicate P is a condition variable; Section IV.C. paragraph 14 The symbol • indicates a condition variable; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true).
As per claim 18, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 17. Marathe teaches wherein the evaluating the respective conditions on which the individual threads of the plurality of threads are waiting on the change to the condition variable is performed responsive to receiving a request to signal the evaluating a change to the condition variable ([0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0053] lines 11-17 a transaction B (which, with respect to the particular transaction condition variable is a notifier transaction) may call a notify method of the transaction condition variable, as in 320. Note that this notify method may be a notify-all method (in which case it may notify all waiter transactions on the wait list associated with the transaction condition variable of the notification event); 0083] In this example, which relies on transaction condition variables, a consumer (i.e. a database thread 630) may call a wait method of a transaction condition variable when it finds the queue to be empty. As per the retry-on-wait semantics described herein, calling the wait method may essentially abort the consumer's CIT (which is designated as a txcommatomic block), and may force it to wait for a notification. In this example, a producer (i.e. a client thread 610) may always invoke a notify method when it adds a new node to the producer-consumer queue 620. The underlying condition variable implementation may determine which (if any) database thread 630 will receive the notification (i.e. if one or more of the database threads 630 are waiter transactions); [0092] As previously noted, in the event of aborting waiters, the system may in some embodiments be configured to forward notifications (and establish corresponding dependencies) correctly. In such embodiments, a version number (stored as a value of a numeric "version" indicator) may be included in each xCondition, and its value may be incremented during a txwait call. In some embodiments, each waiter may log an indication (or identifier) of all the xConditions it has waited on in its own xCondition-list; [0060] lines 1-4 when a thread is notified after waiting on a transaction condition variable, it may read some data to determine whether the condition it was waiting for has indeed been satisfied; [0049] lines 8-26 a list of waiter transactions (i.e. a list of transactions that have invoked the wait method of the transaction condition variable and that are currently waiting for a notification from a notify method of the transaction condition variable)).
As per claim 19, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 14. Hung specifically teaches wherein each of the plurality of threads comprises additional associated instructions to be executed in a critical section, and wherein evaluating the condition for the particular thread of the plurality of threads further comprises executing the additional associated instructions of the particular thread (Fig. 2; Section I paragraph 2 require that the Queue class contain a nonblocking method isEmpty (), and then check the conditions of both the queues continually. For this example, we support a construct waituntil(!Ql.isEmpty() | | ! Q2. isEmpty ()), which requires the system to wake the thread up whenever the global condition becomes true; Section I paragraph 5 If a thread has to wait (block) for a certain condition to become true, programmers can use the waituntil (P) statement with the condition as an argument; Section I paragraph 8 a thread must wait when queue srcQ is empty or queue destQ is full. We use waituntil (P) in line 17 for global conditional synchronization. For put InAQueue, we use the OR construct so that a producer is able to put an item in Ql or Q2 depending on whichever queue is not full; Section IV.B. paragraph 2 Suppose there are some threads waiting on a global predicate P that has become true; Section IV.B. paragraph 1 For example, the global predicate P=(! Q1. isEmpty () || ! Q2. isEmpty ()&& (!Q3.isFull() || !Q4.isFull()) has a corresponding P^=(w^∨x^)∧(y^∨z^). Our system can decide if threads waiting on P should be signaled based on the evaluation of P^. Any thread T that acquires monitor Mi needs to update P^ before releasing Mi by setting the values of atomic Boolean variables related to Mi. After T updates the variables, it releases monitor Mi, evaluates P^, and decides whether to signal threads waiting on P. For example, consider the global predicate (!Q1.isEmpty())&&! Q2.isEmpty()) || ! Q3.isFull()). It has a corresponding P=(x^∧y^)∨z^, where every variable is set as false by a thread waiting on the condition. Suppose T1 accesses Q1 and determines that ! Q1. isEmpty () is true. Before T1 releases Q1, it updates P^ by setting x^ as true. P^ is still false since y^ is false. T1 does not signal any thread waiting on P. Thread T2 then accesses Q2 and finds that !Q2. isEmpty () has become true. T2 updates P^ by setting y^ as true and signals a thread waiting on P since P^ has become true; Section IV.C. paragraph 2 The idea behind the records is that a global predicate is false because some of its clauses are false. The global predicate can become true only if those clauses become true. We call these clauses critical; Section I paragraph 5 Every method of a monitor is a critical section. If programmers need a critical section across multiple monitor objects).
As per claim 20, Marathe and Hung teach the one or more non-transitory computer-accessible storage media of claim 14. Marathe specifically teaches wherein the condition variable is one of a plurality of condition variables ([0092] lines 7-9 each waiter may log an indication (or identifier) of all the xConditions it has waited on; [0026] transaction condition variables. A transaction condition variable (sometimes referred to herein as an xCondition)).
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HSING CHUN LIN whose telephone number is (571)272-8522. The examiner can normally be reached Mon - Fri 9AM-5PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Aimee Li can be reached at (571) 272-4169. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/H.L./Examiner, Art Unit 2195
/Aimee Li/Supervisory Patent Examiner, Art Unit 2195
Prosecution Insights