Wake-up ordering of processing streams using sequential identifiers

• US 10,025,642 B2
• Filed: 11/25/2014
• Issued: 07/17/2018
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Riegel, Torvald
• Primary Examiner(s): Rahman, Fahmida
• Application Number:
  US14/552,734
• Publication Number:
  US 20160147576A1
• Time in Patent Office: 1,330 Days
• Field of Search: None
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Systems and methods for waking up waiting processing streams in a manner that reduces the number of spurious wakeups. An example method may comprise: assigning a first identifier of a sequence of identifiers to a processing stream in a waiting state; receiving a wakeup signal associated with a second identifier of the sequence of identifiers; comparing, by a processing device, the first identifier with the second identifier; and waking the processing stream responsive to determining, in view of comparing, that the processing stream began waiting prior to an initiation of the wakeup signal.

Claims

1. A method comprising:

assigning identifiers of a sequence of identifiers to wakeup signals and to processing streams, the sequence of identifiers representing a chronological order that the wakeup signals are initiated and the processing streams begin waiting, wherein each of the identifiers is exclusively assigned to either a wakeup signal or a processing stream and the sequence of identifiers comprises a first identifier associated with a wakeup signal and a second identifier associated with a processing stream in a waiting state;

receiving the wakeup signal associated with the first identifier after the processing stream associated with the second identifier enters the waiting state;

responsive to the receiving the wakeup signal, comparing, by a processing device, the first identifier associated with the wakeup signal and the second identifier associated with the processing stream to determine that the processing stream began waiting after an initiation of the wakeup signal; and

responsive to the comparing, waking at least one of the processing streams and avoiding waking the processing stream associated with the second identifier that began waiting during a time delay between the initiation of the wakeup signal and the receiving of the wakeup signal.

2. The method of claim 1, wherein determining that the processing stream began waiting after the initiation of the wakeup signal comprises determining that the first identifier is less than the second identifier.

3. The method of claim 1, wherein assigning the second identifier to the processing stream is performed in response to receiving a wait function call to block the processing stream.

4. The method of claim 1, wherein the wakeup signal is initiated by a wakeup function call.

5. The method of claim 1, wherein the first identifier and the second identifier are provided by condition variables.

6. The method of claim 5, further comprising resetting the first identifier responsive to determining that a value of the second identifier exceeds a threshold value, wherein the threshold value is a maximum value provided by the condition variables.

7. The method of claim 1, wherein the first identifier of the wakeup signal is stored in a futex data structure.

8. The method of claim 1, further comprising:

assigning a third identifier to an additional processing stream, wherein the additional processing stream initiates a wait function call after the wakeup signal is initiated but prior to the wakeup signal being received;

determining the third identifier of the additional processing stream is greater than the first identifier; and

processing the wakeup signal without waking up the additional processing stream.

9. The method of claim 8, further comprising:

grouping multiple processing streams into a plurality of groups comprising a first group and a second group, the first group comprising a first processing stream initiating a wait function call prior to the wakeup signal being initiated, and a second group comprises a second processing stream initiating a wait function after the wakeup signal being initiated;

waking up the first processing stream in the first group without waking up the second processing stream in the second group; and

associating the second processing stream with the first group after the first processing stream consumes the wakeup signal.

10. The method of claim 9, wherein associating the second processing stream with the first group is performed after removing one or more waiting processing streams from the first group.

11. The method of claim 9, wherein the first processing stream of the first group and the second processing stream of the second group are executing on a single machine.

12. A system comprising:

a memory; and

a processing device communicably coupled to the memory, the processing device to execute instructions to;

assign identifiers of a sequence of identifiers to wakeup signals and to processing streams, the sequence of identifiers representing a chronological order that the wakeup signals are initiated and the processing streams begin waiting, wherein each of the identifiers is exclusively assigned to either a wakeup signal or a processing stream and the sequence of identifiers comprises a first identifier associated with a wakeup signal and a second identifier associated with a processing stream in a waiting state;

receive the wakeup signal associated with the first identifier after the processing stream associated with the second identifier enters the waiting state;

responsive to the receiving the wakeup signal, compare, by the processing device, the first identifier associated with the wakeup signal and the second identifier associated with the processing stream to determine that the processing stream began waiting after an initiation of the wakeup signal; and

responsive to the comparing, wake at least one of the processing streams and avoiding waking the processing stream associated with the second identifier that began waiting during a time delay between the initiation of the wakeup signal and the receiving of the wakeup signal.

13. The system of claim 12, wherein the processing device further to reset the first identifier responsive to determining that a value of the second identifier exceeds a threshold value, wherein the threshold value is a maximum value.

14. The system of claim 12, wherein the processing device further to:

assign a third identifier to an additional processing stream, wherein the additional processing stream initiates a wait function call after the wakeup signal is initiated but prior to the wakeup signal being received;

determine the third identifier of the additional processing stream is greater than the first identifier; and

process the wakeup signal without waking up the additional processing stream.

15. The system of claim 12, wherein the processing device further to:

group multiple processing streams into a plurality of groups comprising a first group and a second group, the first group comprising a first processing stream initiating a wait function call prior to the wakeup signal being initiated, and a second group comprises a second processing stream initiating a wait function after the wakeup signal being initiated;

wake up the first processing stream in the first group without waking up the second processing stream in the second group; and

associate the second processing stream with the first group after the first processing stream consumes the wakeup signal.

16. A non-transitory machine-readable storage medium storing instructions which, when executed, cause a processing device to execute operations comprising:

assign identifiers of a sequence of identifiers to wakeup signals and to processing streams, the sequence of identifiers representing a chronological order that the wakeup signals are initiated and the processing streams begin waiting, wherein each of the identifiers is exclusively assigned to either a wakeup signal or a processing stream and the sequence of identifiers comprises a first identifier associated with a wakeup signal and a second identifier associated with a processing stream in a waiting state;

receive the wakeup signal associated with the first identifier after the processing stream associated with the second identifier enters the waiting state;

responsive to the receiving the wakeup signal, compare, by a processing device, the first identifier associated with the wakeup signal and the second identifier associated with the processing stream to determine that the processing stream began waiting after an initiation of the wakeup signal; and

responsive to the comparing, wake at least one of the processing streams and avoiding waking the processing stream associated with the second identifier that began waiting during a time delay between the initiation of the wakeup signal and the receiving of the wakeup signal.

17. The non-transitory machine-readable storage medium of claim 16, wherein the instructions further comprise:

reset the first identifier responsive to determining that a value of the second identifier exceeds a threshold value, wherein the threshold value is provided by a maximum value of a condition variable.

18. The non-transitory machine-readable storage medium of claim 16, wherein the instructions further comprising:

assign a third identifier to an additional processing stream, wherein the additional processing stream initiates a wait function call after the wakeup signal is initiated but prior to the wakeup signal being received;

determine the third identifier of the additional processing stream is greater than the second identifier; and

process the wakeup signal without waking up the additional processing stream.

19. The non-transitory machine-readable storage medium of claim 16, wherein the instructions further comprising:

group multiple processing streams into a plurality of groups comprising a first group and a second group, the first group comprising a first processing stream initiating a wait function call prior to the wakeup signal being initiated, and a second group comprises a second processing stream initiating a wait function after the wakeup signal being initiated;

wake up the first processing stream in the first group without waking up the second processing stream in the second group; and

associate the second processing stream with the first group after the first processing stream consumes the wakeup signal.