Method and device for scheduling communication schedulable unit

• US 9,471,372 B2
• Filed: 03/21/2013
• Issued: 10/18/2016
• Est. Priority Date: 03/21/2013
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Chen, Begood, Wang, Jun
• Primary Examiner(s): RONI, SYED A
• Application Number:
  US14/778,033
• Publication Number:
  US 20160179571A1
• Time in Patent Office: 1,307 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4818 Priority circuits therefor
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: H04W 72/1215 for collaboration of different radio technologies

Abstract

Communication schedulable units (CSUs) belonging to different owners in a radio communication device are scheduled to use multiple processors. The CSUs under different owners can be processed in parallel by the different processors. A global CSU list and an owner waiting list are maintained. The global CSU list may include the CSUs waiting to be processed and the CSUs are ordered according to the time stamps of the CSUs. The owner waiting list may include the owners that have no CSU being processed and the owners are ordered according to the time stamps of their respective earliest CSUs waiting to be processed in the global CSU list. When one of the processors finishes processing a first CSU of a first owner, a CSU to be processed next is scheduled according to the CSU time order and the CSU affinity, based on the global CSU list and the owner waiting list.

Claims

1. A method of scheduling communication schedulable units, CSUs, belonging to different owners in a radio communication device using multiple processors, wherein the CSUs can be processed in parallel by at least two of the processors, comprising:

maintaining a global CSU list and an owner waiting list, wherein the global CSU list includes CSUs waiting to be processed and in the global CSU list, the CSUs waiting to be processed are ordered according to time stamps of the CSUs waiting to be processed, wherein the owner waiting list includes owners that have no CSU being processed by the processors and in the owner waiting list the owners that have no CSU being processed are ordered according to time stamps of their respective earliest CSUs waiting to be processed in the global CSU list; and

when one of the processors finishes processing a first CSU of a first owner, scheduling a CSU to be processed next by the processor according to the order of the CSUs by the time stamps and CSU affinity, based on the global CSU list and the owner waiting list,

wherein the scheduling comprises;

obtaining a second CSU waiting to be processed that belongs to the first owner, the second CSU has a minimum time stamp among the CSUs waiting to be processed that belong to the first owner;

locating a head owner from the owner waiting list, the head owner'"'"'s earliest CSU waiting to be processed has a minimum time stamp among the owners in the owner waiting list;

locating a third CSU in the global CSU list which is the head owner'"'"'s earliest CSU waiting to be processed;

calculating a disparity between a first time stamp of the second CSU and a second time stamp of the third CSU; and

when the disparity that the first time stamp is later than the second time stamp exceeds a predefined threshold, inserting the first owner back to the owner waiting list according to the first time stamp, removing the head owner from the owner waiting list and processing the third CSU of the head owner by the processor, otherwise processing the second CSU by the processor.

2. The method according to claim 1, wherein CSUs belonging to a same owner in the global CSU list are linked together.

3. The method according to claim 2, comprising:

when the CSUs belonging to a same owner are directly adjacent in the global CSU list, unlinking CSUs other than the CSU having a minimum time stamp among the CSUs belonging to the same owner from the global CSU list.

4. The method according to claim 1, comprising maintaining a CSU-owner index list linking the owner waiting list with the global CSU list, wherein individual index items in the CSU-owner index list are sequentially indexed by respective consecutive ranges of CSUs in the global CSU list, in terms of CSU order in the global CSU list, and one CSU in the global CSU list only index one index item,

wherein the individual index items sequentially index one or more consecutive owners in the owner waiting list, in terms of owner order in the owner waiting list, and one index item only index one of the owners in the owner waiting list,

wherein a particular owner and the CSU range including the particular owner'"'"'s earliest CSU are indexed by a same one of the index items;

and

wherein the inserting the first owner back to the owner waiting list according to the first time stamp comprises;

locating directly a first index item indexed by the second CSU of the first owner in the CSU-owner index list, locating directly a third owner indexed by the first index item, placing the first owner directly behind the third owner in the owner waiting list if the time stamp of the first owner'"'"'s earliest CSU waiting to be processed is later than that of the third owner '"'"'s earliest CSU waiting to be processed;

otherwise placing first owner directly prior to the third owner.

5. The method according to claim 4, wherein consecutive index items indexing one of two adjacent owners in the owner waiting list are divided into two parts, a first part of index items index a former of the two adjacent owners and a second part of index items index the latter of the two adjacent owners.

6. The method according to claim 4, wherein a length of a CSU range corresponding to each index item is uniformly set to K, which is a positive integer.

7. The method according to claim 4, the method comprises:

after inserting the first owner back to the owner waiting list, updating the index items in the CSU-owner index list, wherein the first index item will index the first owner.

8. The method according to claim 7, wherein after inserting the first owner back to the owner waiting list, if the first index item has been used to insert another owner back to the owner waiting list before, creating a new index item and inserting the new index item into the CSU-owner index list directly behind the first index item if the time stamp of the first owner'"'"'s earliest CSU waiting to be processed is later than that of the third owner'"'"'s earliest CSU waiting to be processed;

otherwise inserting the new created index item directly prior to the first index owner, then updating the index items in the CSU-owner index list, wherein the new index item will index the first owner.

9. A computer program product comprising a non-transitory computer readable storage medium storing instructions which when run on a radio communication device provided with multiple processors causes the radio communication device to perform the steps of the method according to claim 1.

10. A method of scheduling communication schedulable units, CSUs, belonging to different owners in a radio communication device using multiple processors, wherein the CSUs can be processed in parallel by at least two of the processors, comprising:

maintaining a global CSU list and an owner waiting list, wherein the global CSU list includes CSUs waiting to be processed and in the global CSU list, the CSUs waiting to be processed are ordered according to time stamps of the CSUs waiting to be processed, wherein the owner waiting list includes owners that have no CSU being processed by the processors and in the owner waiting list the owners that have no CSU being processed are ordered according to time stamps of their respective earliest CSUs waiting to be processed in the global CSU list;

when one of the processors finishes processing a first CSU of a first owner, scheduling a CSU to be processed next by the processor according to the order of the CSUs by the time stamps and CSU affinity, based on the global CSU list and the owner waiting list;

deriving one or more sub-owners from a particular owner, wherein each sub-owner owns different parts of CSUs originally belonging to the particular owner, at least part of the CSUs belonging to different sub-owners can be processed in parallel; and

if there are processing dependencies among the CSUs respectively belonging to the different sub-owners;

maintaining a blocking list which includes blocking nodes each standing for a blocked CSU waiting to be processed, the blocking nodes are ordered according to the time stamp of the corresponding blocked CSUs; and

when all the CSUs on which a blocked CSU has processing dependency have been processed, removing the blocking node corresponding to the blocked CSU from the blocking list, and if there is no idle processor available among the multiple processors to process the blocked CSU, inserting the sub-owner owning the blocked CSU back to the owner waiting list based on the position of the blocked CSU in the global CSU list, otherwise processing the blocked CSU directly by using an idle processor.

11. The method according to claim 10, wherein when a plurality of CSUs belonging to different sub-owner have processing dependency on a same predecessor CSU, adding the CSUs other than that having a minimum time stamp among the plurality of CSUs into the blocking list as the blocked CSUs.

12. The method according to claim 10, the method comprises if a particular CSU which will be scheduled to be processed is linked within the global CSU list:

obtaining a third time stamp of the earliest CSU waiting to be processed of the head owner in the owner waiting list;

obtaining a fourth time stamp of ahead blocked CSU with the minimum time stamp among all the blocked CSUs in the blocking list;

comparing the time stamp of the particular CSU with the earlier one between the third time stamp and the fourth time stamp; and

when the time stamp of the particular CSU is later than above said earlier time stamp, unlinking the particular CSU from the global CSU list in a serial manner.

13. A radio communication device having multiple processors and being adapted for scheduling communication schedulable units, CSUs, belonging to different owners wherein the CSUs can be processed in parallel by at least two of the processors, comprising:

a first maintaining unit adapted to maintain a global CSU list and an owner waiting list, wherein the global CSU list includes CSUs waiting to be processed and in the global CSU list, the CSUs waiting to be processed are ordered according to time stamps of the CSUs waiting to be processed, wherein the owner waiting list includes owners that have no CSU being processed by the processors and in the owner waiting list, the owners that have no CSU being processed are ordered according to time stamps of their respective earliest CSUs waiting to be processed in the global CSU list; and

a scheduling unit adapted to, when one of the processors finishes processing a first CSU of a first owner, schedule a CSU to be processed next by the processor according to the order of the CSUs by the time stamps and CSU affinity, based on the global CSU list and the owner waiting list, and further adapted to;

obtain a second CSU waiting to be processed that belongs to the first owner, the second CSU has a minimum time stamp among the CSUs waiting to be processed that belong to the first owner;

locate a head owner from the owner waiting list, the head owner'"'"'s earliest CSU waiting to be processed has a minimum time stamp among the owners in the owner waiting list;

locate a third CSU in the global CSU list which is the head owner'"'"'s earliest CSU waiting to be processed;

calculate a disparity between a first time stamp of the second CSU and a second time stamp of the third CSU; and

when the disparity that the first time stamp is later than the second time stamp exceeds a predefined threshold, insert the first owner back to the owner waiting list according to the first time stamp, remove the head owner from the owner waiting list and process the third CSU of the head owner by the processor, otherwise process the second CSU by the processor.

14. The radio communication device according to claim 13, wherein the CSUs belonging to a same owner in the global CSU list are linked together.

15. The radio communication device according to claim 14, comprising:

a first unlinking unit, when the CSUs belonging to a same owner are directly adjacent in the global CSU list, adapted to unlink CSUs other than the CSU having a minimum time stamp among the CSUs belonging to the same owner from the global CSU list.

16. The radio communication device according to claim 13, comprising:

a second maintaining unit adapted to maintain a CSU-owner index list linking the owner waiting list with the global CSU list, wherein individual index items in the CSU-owner index list are sequentially indexed by respective consecutive ranges of CSUs in the global CSU list, in terms of CSU order in the global CSU list, and one CSU in the global CSU list only index one index item,

wherein the individual index items sequentially index one or more consecutive owners in the owner waiting list, in terms of owner order in the owner waiting list, and one index item only index one of the owners in the owner waiting list,

wherein a particular owner and the CSU range including the particular owner'"'"'s earliest CSU are indexed by a same one of the index items; and

wherein the scheduling unit is adapted to insert the first owner back to the owner waiting list according to the first time stamp by locating directly a first index item indexed by the second CSU of the first owner in the CSU-owner index list, locating directly a third owner indexed by the first index item, placing the first owner directly behind the third owner in the owner waiting list if the time stamp of the first owner'"'"'s earliest CSU waiting to be processed is later than that of the third owner '"'"'s earliest CSU waiting to be processed;

otherwise placing first owner directly prior to the third owner.

17. The radio communication device according to claim 16, wherein the consecutive index items indexing one of two adjacent owners in the owner waiting list are divided into two parts, a first part of index items index a former of the two adjacent owners and a second part of index items index the latter of the two adjacent owners.

18. The radio communication device according to claim 16, wherein a length of a CSU range corresponding to each index item is uniformly set to K, which is a positive integer.

19. The radio communication device according to claim 16, comprising:

an updating unit, after the first owner is inserted back to the owner waiting list, adapt to update the index items in the CSU-owner index list, wherein the first index item will index the first owner.

20. The radio communication device according to claim 19, wherein after the first owner is inserted back to the owner waiting list, if the first index item has been used to insert another owner back to the owner waiting list before, the updating unit is adapted to create a new index item and insert the new index item into the CSU-owner index list directly behind the first index item if the time stamp of the first owner'"'"'s earliest CSU waiting to be processed is later than that of the third owner'"'"'s earliest CSU waiting to be processed;

otherwise insert the new created index item directly prior to the first index owner, and then update the index items in the CSU-owner index list, wherein the new index item will index the first owner.

21. A radio communication device having multiple processors and being adapted for scheduling communication schedulable units, CSUs, belonging to different owners wherein the CSUs can be processed in parallel by at least two of the processors, comprising:

a first maintaining unit adapted to maintain a global CSU list and an owner waiting list, wherein the global CSU list includes CSUs waiting to be processed and in the global CSU list, the CSUs waiting to be processed are ordered according to time stamps of the CSUs waiting to be processed, wherein the owner waiting list includes owners that have no CSU being processed by the processors and in the owner waiting list, the owners that have no CSU being processed are ordered according to time stamps of their respective earliest CSUs waiting to be processed in the global CSU list;

a scheduling unit adapted to, when one of the processors finishes processing a first CSU of a first owner, schedule a CSU to be processed next by the processor according to the order of the CSUs by the time stamps and CSU affinity, based on the global CSU list and the owner waiting list;

a deriving unit adapted to derive one or more sub-owners from a particular owner, wherein each sub-owner owns different parts of CSUs originally belonging to the particular owner, at least part of the CSUs belonging to different sub-owners can be processed in parallel; and

a blocking unit adapted to, if there are processing dependencies among the CSUs respectively belonging to the different sub-owners, perform the following;

maintaining a blocking list which includes blocking nodes each standing for a blocked CSU waiting to be processed, the blocking nodes are ordered according to the time stamp of the corresponding blocked CSUs; and

when all the CSUs on which a blocked CSU has processing dependency have been processed, removing the blocking node corresponding to the blocked CSU from the blocking list, and if there is no idle processor available among the multiple processors to process the blocked CSU, inserting the sub-owner owning the blocked CSU back to the owner waiting list based on the position of the blocked CSU in the global CSU list, otherwise processing the blocked CSU directly by using an idle processor.

22. The radio communication device according to claim 21, wherein blocking unit is adapted to, when a plurality of CSUs belonging to different sub-owner have processing dependency on a same predecessor CSU, add the CSUs other than that having a minimum time stamp among the plurality of CSUs into the blocking list as the blocked CSUs.

23. The radio communication device according to claim 21, comprising:

a second unlinking unit adapted to, if a particular CSU which will be scheduled to be processed is linked within the global CSU list, perform the following;

obtaining a third time stamp of the earliest CSU waiting to be processed of the head owner in the owner waiting list;

obtaining a fourth time stamp of a head blocked CSU with the minimum time stamp among all the blocked CSUs in the blocking list;

comparing the time stamp of the particular CSU with the earlier one between the third time stamp and the fourth time stamp; and

when the time stamp of the particular CSU is later than above said earlier time stamp, unlinking the particular CSU from the global CSU list in a serial manner.