Method and apparatus for providing a preemptive task scheduling scheme in a real time operating system

• US 9,606,833 B2
• Filed: 03/24/2015
• Issued: 03/28/2017
• Est. Priority Date: 04/09/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Indukuri, Venakata Raju, Vrind, Tushar, Somu Kandaswamy, Balaji, Udava, Raju Siddappa
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): Wu, Junchun
• Application Number:
  US14/667,204
• Publication Number:
  US 20150293793A1
• Time in Patent Office: 735 Days
• Field of Search: 718/103
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

Method and apparatuses are provided for providing preemptive task scheduling for a Real Time Operating System (RTOS). A two-level priority is assigned to each task that is created. The two-level priority includes a kernel priority and a user-defined priority. A priority bitmap corresponding to the kernel priority is created. A priority bit in the priority bitmap is enabled. The priority bit indicates a status of a respective task.

Claims

1. A method of providing preemptive task scheduling for a Real Time Operating System (RTOS), the method comprising:

assigning a two-level priority to each task that is created, the two-level priority comprising a kernel priority and a user-defined priority;

creating a priority bitmap corresponding to the kernel priority;

enabling a priority bit in the priority bitmap, the priority bit indicating a status of a respective task; and

executing the task based on the priority bit,

wherein the kernel priority is a unique incremental number that is assigned to each task being created through a predefined protocol,

wherein the user-defined priority is the general task priority as defined by the user and can be any number within an allowed priority range for a task scheduler, and

wherein each task can be mapped to a bit in the priority bitmap on a one-to-one basis.

2. The method of claim 1, further comprising:

disabling the priority bit in the priority bitmap,

wherein enabling the priority bit indicates that the task is ready for execution and disabling the priority bit indicates that the respective task is suspended.

3. The method of claim 1, wherein the status of each respective task is one of ready for execution and suspended.

4. The method of claim 1, wherein assigning the two-level priority comprises at least one of:

assigning each task a unique kernel priority;

assigning the kernel priority for one or more tasks based on a value of the user-defined priority; and

assigning the kernel priorities for two or more tasks having a same user-defined priority based on an order of task creation.

5. The method of claim 1, further comprising:

prioritizing tasks for execution based on a task creation order, if two or more tasks having a same user-defined priority are ready for execution at an instant of time.

6. The method of claim 1, wherein executing the task based on the priority bit comprises:

identifying a highest priority task for execution, where the highest priority task for execution has a least significant bit in the priority bitmap.

7. The method of claim 1, further comprising:

allocating at least two bits for each task in the priority bit map, a first bit of the at least two bits being a signal bit and a second bit of the at least two bits being a task priority bit;

prioritizing signals ahead of tasks based on the allocation of the signal bit and the task priority bit; and

invoking at least one of a signal handler or resume task based on a value of a next highest priority in the priority bitmap.

8. The method of claim 7, further comprising;

representing the priority bitmap in a reverse order;

where a Most Significant Bit (MSB) of the priority bitmap represents a highest priority task and a Least Significant Bit (LSB) of the priority bitmap represents a lowest priority task; and

identifying, by a task scheduler, the value of the next highest priority using a single cycle instruction.

9. The method of claim 1, further comprising:

creating and initializing one or more tasks; and

assigning a Default Communication Entity (DCE) to each task of the one or more tasks.

10. The method of claim 9, further comprising:

allowing a task to exit without storing task content, when the task self-relinquishes.

11. An apparatus for providing preemptive task scheduling for a Real Time Operating System (RTOS) comprising:

a memory;

a processing unit coupled to the memory and configured to;

assign a two-level priority to each task that is created, the two-level priority comprising a kernel priority and a user-defined priority;

create a priority bitmap corresponding to the kernel priority;

enable a priority bit in the priority bitmap, the priority bit indicating a status of a respective task; and

execute the task based on the priority bit,

wherein the kernel priority is a unique incremental number that is assigned to each task being created through a predefined protocol,

wherein the user-defined priority is the general task priority as defined by the user and can be any number within an allowed priority range for a task scheduler, and

wherein each task can be mapped to a bit in the priority bitmap on a one-to-one basis.

12. The apparatus of claim 11, wherein the processing unit is further configured to disable the priority bit in the priority bitmap, wherein enabling the priority bit indicates that the respective task is ready for execution and disabling the priority bit indicates that the task is suspended.

13. The apparatus of claim 11, wherein assigning the two-level priority is based on at least one of:

assigning each task a unique kernel priority;

assigning the kernel priority for one or more tasks based on a value of the user-defined priority; and

assigning kernel priorities for two or more tasks having a same user-defined priority based on an order of task creation.

14. The apparatus of claim 11, wherein the processing unit is further configured to:

prioritize tasks for execution based on a task creation order, if two or more tasks having a same user-defined priority are ready for execution at an instant of time.

15. The apparatus of claim 11, wherein the processing unit is further configured to:

allocate at least two bits for each task in the priority bitmap, a first bit of the at least two bits being a signal bit and a second bit of the at least two bits being a task priority bit;

prioritize signals ahead of tasks based on the allocation of the signal bit and the task priority bit; and

invoke at least one of a signal handler or resume task based on a value of a next highest priority in the priority bit map.

16. The apparatus of claim 11, wherein the processing unit is further configured to:

create and initialize one or more tasks; and

assign a Default Communication Entity (DCE) to each task of the one or more tasks.

17. A communication device for providing preemptive task scheduling for a Real Time Operating System (RTOS), comprising:

one or more non-transitory computer-readable media; and

a processor which, when executing one or more programs stored on the one or more non-transitory computer-readable media;

assign a two-level priority to each task that is created, the two-level priority comprising a kernel priority and a user-defined priority;

create a priority bitmap corresponding to the kernel priority;

enable a priority bit in the priority bitmap, the priority bit indicating a status of a respective task;

execute the task based on the priority bit,

wherein the kernel priority is a unique incremental number that is assigned to each task being created through a predefined protocol,

wherein the user-defined priority is the general task priority as defined by the user and can be any number within an allowed priority range for a task scheduler, and

wherein each task can be mapped to a bit in the priority bitmap on a one-to-one basis.