A computer implemented method includes executing a user space partition first real-time task from a real-time task queue on a real-time kernel thread executing on a computing core of a computer, wherein the real-time kernel thread is scheduled by an operating system scheduler, pre-empting the first real-time task via a user space partition real-time task scheduler in response to a task switch signal, saving a first real-time task context, loading a user space second real-time task context for use by the real-time kernel thread via the user space partition real-time task scheduler, and executing the second real-time task from the real-time task queue on the real-time kernel thread.

TECHNICAL FIELD

The present disclosure is related to scheduling real-time tasks, and in particular to a user space real-time scheduler.

BACKGROUND

Many network applications utilize user space code to accomplish reactive programming with high parallelism. To accelerate the code, some systems bypass the kernel. User space runtimes may have a scheduler to schedule user space code, referred to, in the aggregate, as work load. The user space scheduler is usually just a façade around a kernel level scheduler. Since the user space scheduler is in user space, the capabilities of the user space scheduler are limited, and often kernel features are relied on, which can incur large context switching costs.

Some frameworks implement a lightweight task model by multiplexing one kernel thread into multiple running tasks. The drawback of method is that applications must work in a cooperative manner, sometimes requiring modification of each application by including program logic to avoid exceptions. Real-time sensitive application performance can be impacted by a lower priority task that is running or a busy task that prevents a real-time task from running.

SUMMARY

According to one aspect of the present disclosure, a computer implemented method includes executing a user space partition first real-time task from a real-time task queue on a real-time kernel thread executing on a computing core of a computer, wherein the real-time kernel thread is scheduled by an operating system scheduler, pre-empting the first real-time task via a user space partition real-time task scheduler in response to a task switch signal, saving a first real-time task context, loading a user space second real-time task context for use by the real-time kernel thread via the user space partition real-time task scheduler, and executing the second real-time task from the real-time task queue on the real-time kernel thread.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the first real-time task context and the second real-time task context comprise differences from a real-time kernel thread context. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the real-time task context differences comprise 15 or fewer register values managed by a real-time task scheduler executing on the computer.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the real-time kernel thread is scheduled by an operating system scheduler for execution on the computing core, wherein the operating system scheduler handles switching kernel threads. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the computing core is dedicated to executing the real-time kernel thread. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein execution of the first real-time task is interrupted by execution of the second real-time task due to the second real-time task having a higher priority.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein execution of the first real-time task is interrupted in response to an execution time threshold being met to allow switching to another real-time task in the real-time task queue.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein each real-time task is created with an associated priority. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein each real-time task is created with an associated scheduling policy.

According to one aspect of the present disclosure a computer implemented method for preemptively scheduling real-time tasks in a user space partition of a core processor. The method includes queuing multiple real-time tasks in a real-time task queue in the user space partition, preempting a first user space partition real-time task being executed by a real-time task kernel thread executing on the core processor of the computer wherein the real-time task kernel thread is scheduled by an operating system scheduler, saving registers of the preempted first user space partition real-time task, and loading a second real-time task context for execution by the real-time task kernel thread executing on the core processor.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the preempted first real-time task registers comprise a context of the first real-time task that comprises differences from a real-time task kernel thread context.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein real-time task context differences comprise 15 or fewer register values managed by a real-time task scheduler executing on the computer. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the real-time task kernel thread is scheduled by an operating system scheduler for execution on the core processor, wherein the operating system scheduler handles switching kernel threads.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the core processor is dedicated to executing the real-time kernel thread. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the preempted first real-time task execution is interrupted by the new real-time task due to the second real-time task having a higher priority.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein each real-time task is created with an associated priority and an associated scheduling policy.

According to a further aspect of the present disclosure, a device includes memory storage comprising instructions and one or more processors in communication with the memory. The one or more processors execute the instructions to perform operations for preemptively scheduling real-time tasks in a user space partition of one or more core processors. The operations include queuing multiple real-time tasks in a real-time task queue in the user space partition, preempting a first user space partition real-time task being executed by a real-time task kernel thread executing on the core processor, wherein the real-time task kernel thread is scheduled by an operating system scheduler, saving registers of the preempted first user space partition real-time task, and loading a second real-time task context for execution by the real-time task kernel thread executing on the core processor.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the one or more core processors are partitioned between real-time and non-real-time task workloads. Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the preempted real-time task registers comprise a context of the first real-time task that comprises differences from a real-time task kernel thread context, and wherein the real-time task context differences comprise 15 or fewer register values managed by a real-time task scheduler executing on the core processor.

Optionally, in any of the preceding aspects, a further implementation of the aspect includes wherein the preempted real-time task execution is interrupted by the new real-time task due to the new real-time task having a higher priority and wherein each real-time task is created with an associated priority and an associated scheduling policy.

DETAILED DESCRIPTION

In many computer systems, memory may be divided into kernel space and user space. User space is a set of memory locations where user applications and processes run. The kernel manages the applications and keeps applications from interfering with each other. The kernel has access to all of memory. Applications in the user space access the kernel only via a limited set of system calls, which are then scheduled by a kernel scheduler to schedule execution of the applications from the user space.

Real-time tasks in the user space may involve interaction with a user, such as many different transactions. Transactions may involve a user's interaction with many different programs, from word processing, spreadsheet, browsers, and other programs. It can be important to generate fast responses to the user interactions. The scheduling of real-time tasks should be done in a manner to ensure service level agreements are satisfied and the user is satisfied with service, especially in network applications, in which computers may be providing services to multiple users.

To facilitate effective scheduling of real-time tasks, a user-space task scheduler preemptively schedules user-space tasks from a user-space task queue onto a user-space real-time thread that may be used for multiple user-space tasks without time consuming thread swapping. The real-time task thread is scheduled by a kernel scheduler to run on one of multiple CPU cores. The user-space task scheduler ensures that user-space task contexts, which are much smaller than thread contexts, may be efficiently swapped to provide service level agreement compliance.

The real-time user-space tasks are basically small functions that may be more easily switched. Their context, managed at the task scheduler level, may include the differences from the thread context as opposed to the entire context of the thread being saved and reloaded for each task switch. A thread context may be 2 Mbytes in size, compared to an example user-space task context of about 2 Kbytes. Thread context switching may utilize thousands of instruction cycles, while less than 100 instruction cycles may be used to switch the user-task context, saving significant computing resources.

FIG. 1is a block diagram of a system100having four core central processing units (CPUs)110,112,114, and116. More or fewer cores may be used in further embodiments. Each core in an example embodiment may run an operating system having a scheduler120that schedules various threads that run on the CPUs. Thread125is a real-time (RT) thread that is used for running user space threads. RT threads may be referred to as real-time threads at least because there may be certain service level agreements (SLA) that specify how quickly RT tasks should complete. A normal thread130runs normal tasks that may not have an SLA. Both threads125and130are shown as running on CPU110, and are scheduled by the scheduler120. The scheduler120may be a Linux OS (operating system) scheduler in one embodiment.

CPU112is shown as running normal thread132, CPU114is running RT thread134, and CPU116is running RT thread136. Note that in some embodiments, the RT threads may be pinned to a particular CPU to ensure that the RT thread is not switched out for a normal thread. Pinning is shown for CPUs112,114, and116where only one type of thread is running on the respective CPUs. Note that the threads are kernel threads, which may be thought of as heavy weight threads due to their relatively large contexts that are saved each time the scheduler120swaps, or changes which thread is running on their respective CPU.

In one embodiment, RT tasks may be selected to ensure that they are lightweight tasks, and have a user-space context of about 2 Kbytes or less, referred to as a user-space context constraint. Note that the user-space context constraint may be higher in further embodiments. The user-space context constraint for an RT task may be expressed as a percentage of a thread context, and may range from 5% to 15% or higher of a thread context in one embodiment. in further embodiments, the user-space context constraint may be a function of SLAs and the relative costs of context switching.

The threads are fed tasks from one or more queues,140,142,144,146, and148. Queue140is an RT task queue that queues RT tasks for running on RT thread125. Queue142is a normal task queue that queues normal tasks for running on thread130. RT task queue140may have multiple priority queues as indicated at P1150to PN152. Thus, there are N different priority levels for RT tasks, with a priority queue for each level. Similarly, normal task queues142and144also have a similar priority normal task queues as indicated at154,156and158,160respectively. RT task queues146and148have the same structure of multiple priority queues as indicated by priority queues162,164and166,168respectively. Scheduler120schedules normal tasks on normal threads from the normal tasks queues.

In one embodiment, system100includes a pre-emptive lightweight (LW) task scheduler170, shown between the threads and the queues. The LW task schedule170is used to feed tasks from the RT queues to the RT threads, outside the control of the scheduler120. LW task schedule170gives the user space the ability to select tasks to meet SLA commitments by both scheduling RT tasks separately from normal tasks, as well as preempting a currently running RT task by saving its LW context, suspending the currently running task. A different RT task may then be run on the same RT thread, such as an RT task having a higher priority. Once the higher priority task is complete, the preempted RT task may then be continued by loading the saved LW context into the RT thread.

In some embodiments, multi-core support may include both strict core partitioning and core sharing between real-time and non-real-time tasks. In strict core partitioning, one group of cores runs only RT threads and another group of cores runs only normal threads. In core sharing, one or more cores may each run RT threads and normal threads. The ability to support multiple cores in this manner provides for the ability to have fine grained CPU allocation based on RT and non-RT needs. In the shared core case, an RT thread can preempt a general thread to provide RT guarantees.

FIG. 2is a block diagram of a system200illustrating further detail of pre-emptive LW task scheduler170. The references numbers inFIG. 2are consistent with those ofFIG. 1for like elements. LW task scheduler170has scheduling algorithms210and reschedule logic215. Scheduling algorithms210select tasks from the RT task queues140and schedule the tasks via a worker thread220as RT thread125. The worker thread220comprises user space code logic for performing LW pre-emptive user space scheduler170such that an execution context for the user-space tasks is provided. Worker thread220manages the light weight contexts of the user space tasks, providing a second level of scheduling over the scheduler120that schedules the threads125and130. All code running on the CPUs is controlled by scheduler120, with scheduling of LW tasks abstracted using LW task scheduler170via worker thread220. Thus, scheduler120will schedule worker thread220, whereas LW scheduler170schedules the LW tasks on worker thread220.

When an RT task is preempted, the reschedule logic215takes over to copy the LW context and suspend the task. The reschedule logic215also restores the suspended task when the preempting task is complete. Normal tasks may be scheduled by the scheduler120from normal task queues142and executed via worker thread225as a normal thread130.

FIG. 3is a flowchart illustrating a computer implemented method300of switching RT tasks via a preemptive scheduler. Method300begins by executing a first real-time task from a real-time task queue on a real-time kernel thread executing on a computing core of the computer at operation310. Operation320saves a first real-time task context responsive to a task switch signal. A second real-time task context is loaded at operation330for use by the real-time kernel thread. Operation340executes the second real-time task from the real-time task queue.

In one embodiment, the first real-time task context and the second real-time task context comprise differences from a real-time kernel thread context. The real-time task context differences may comprise 15 or fewer register values managed by a real-time task scheduler executing on the computer.

The real-time kernel thread may be scheduled by an operating system scheduler for execution on the computing core. The operating system scheduler handles switching kernel threads. The computing core is dedicated to executing the real-time kernel thread.

In one embodiment, the first real-time task execution may be interrupted by the second real-time task due to the second real-time task having a higher priority, which may be specified at creation. A scheduling policy may also be specified on creation of the real-time task. The first real-time task execution may he interrupted responsive to an execution time threshold being met to allow switching to another real-time task in the real-time task queue.

FIG. 4is a flowchart illustrating a method400for preemptively scheduling real-time tasks in a user space partition of a core processor executing an RT task kernel thread. Multiple real-time tasks are queued in a real-time task queue at operation410. At operation420, a currently executing real-time task is preempted on a real-time task kernel thread executing in user space of the core processor of the computer. Registers of the preempted real-time task are saved at operation430. Execution of the real-time task may be suspended and a new real-time task context is loaded at operation440for execution on the real-time task kernel thread executing in the user space partition of the core processor.

FIG. 5is a block flow diagram illustrating a method500of RT task scheduler context switching. The RT task scheduler maintains data structures that store and restore task contexts. Operation begins at510with task A515executing on a RT thread. A switch indication is received, causing a push of extra register contexts at operation520to a current stack of A525. Operation530saves the current stack pointer to the current task data structure. At operation535, the saved stack pointer of the next task is saved into the stack pointer register. The extra register contexts from the new stack, stack of Bat540, is popped at operation545. Method500returns to the returned address saved in the new stack at operation550, and the new task B550is executed by the RT thread.

FIG. 6is a block flow diagram illustrating a method600of context switching via a signal, RTSIG1. A scheduler watchdog function610watches for a queue signal at615, Sigqueue (RTSIG1), indicative of an RT task switch. The signal may be generated due to the need to execute a higher priority task first to satisfy obligations under an SLA in one embodiment, or for any other reason. Detection of the RTSIG1 signal while an RT task1620is executing on a thread invokes an RTSIG1 handler630, which sets a flag: In_signal_handler, and re-enables the RTSIG1 signal. A stack pointer in the. RTSIG1 handler630may be treated as the task1stack pointer. The RTSIG1 handler630saves the task 1 LW context and is suspended.

FIG. 7is a block flow diagram illustrating a method700of rescheduling the preempted task1620. A task2710is currently executing, and upon completion, and responsive to task1being picked to be. rescheduled/switched to, the task1context will be restored back to the suspended RTSIG1 handler630, which will return at725to the task1620.

FIG. 8is a flowchart illustrating a method800of rescheduling a task with concurrency handling and reentrant support. Method800starts at810and at operation815determines if a switch is in progress by detecting if a flag, Switch_in_progress, is zero. If not, it is determined at operation820if Switch_in_progress is1. If yes, the In_signal_handler flag is set to zero and a Pending_switch_by_signal flag is set to 1. The flags act as a locking mechanism for a reschedule call between multiple LW tasks. Since CPU operations are atomic, no further locking mechanism is used in one embodiment. Method800then returns at826. If no at operation820, the method also returns at826.

At operation815, if the Switch_in_progress flag is zero, the Switch_in_progress flag is set to1at operation830, the context of the current task is saved at operation838, the next task is selected, the stack pointer is set to the location of the next task, and the next task's context is restored at operation840. A determination of whether the Pending_switch_by_signal flag is equal to one is then made by operation845. If yes, the Pending_switch_by_signal flag is set to zero, the Switch_in_progress flag is set to zero, and a reschedule function. Reschedule ( ) is called at operation850. The method then returns at853.

If, at845, the Pending_switch by signal flag is not equal to one, the Switch_in_progress flag is set to zero at operation855. At operation860, it is determined if the In_signal_handler flag is 1. if no, the method returns at853. If yes, the In_signal_handler flag is set to 0.

Application interfaces include the following:

Itw_sched_param *get_Itw_sched_param(Itw_task_t *) interface is used to get scheduling parameters of a lightweight task. It may be thought of as a helper to simply retrieve the scheduling parameter for a given LW task

Itw_sched_init(core_list_t * CPU_group_list, bool preemptive) interface is used to initialize the scheduler—allocates CPU cores based on group list and set the pre-emptive flag. Scheduler initialization—core_list_t* CPU_group_list—a set of CPU cores the scheduler will use for LW tasks. Bool preemptive allows or disallows LW task preemption

Scheduling interfaces may include the following:

void reschedule(void) Invoked by a lightweight task to yield CPU.

void reschedsignal(int workID) Trigger a reschedule of a lightweight task by an external system. This mechanism causes a running task to be interrupted and yield its execution so that the scheduler can schedule the next task

void reschedsignalonfault(int workID) Trigger a reschedule of a lightweight task by an external system when the current task is in an exception state (e.g.: time threshold reached). The scheduler will put the current task into a faulty task queue and schedule the next proper task.

FIG. 9is a block flow diagram illustrating a method900of exception handling. In one embodiment, a task1( ) at910is being performed by a worker thread915, such as an RT thread that is executing on a CPU920. A watchdog function925in scheduler927checks the state of task1( ) periodically as indicated at930to determine if the task has exceeded an execution time quantum or threshold. If so, an exception has been detected, and the watchdog925a function (reschedsignalonfault(workID)) to signal at935the worker thread, giving the function a workID. A signal to the worker thread915is then

sent to cause task1( )910to stop and be placed in a faulty queue by a worker signal handler. The next task2( )at940from the task queue945is rescheduled via reschedule( ). Task2( )will then resume execution.

FIG. 10is a block flow diagram illustrating a method1000of task preemption caused by a new RT task. Reference numbers on like components are the same as those used inFIG. 9. In one embodiment, a task1( ) at910is being performed by a worker thread915, such as an RT thread that is executing on a CPU920. A new RT task, task201010is created while task1( ) is still running. A call to Itwtask_create( ) places task2( )into the proper queue945as indicated at1020. A call is then made to reschedsignal(int workID) while will interrupt the worker thread915and jump to a signal handler. The signal handler calls reschedule( ) and runs the new RT task, task2( ).

FIG. 11is a block diagram illustrating circuitry for implementing a real-time scheduler for real time tasks and for performing methods according to example embodiments. All components need not be used in various embodiments.

One example computing device in the form of a computer1100may include a processing unit1102, memory1103, removable storage1110, and non-removable storage1112. Although the example computing device is illustrated and described as computer1100, the computing device may be in different forms in different embodiments. For example, the computing device may instead be a smartphone, a tablet, smartwatch, or other computing device including the same or similar elements as illustrated and described with regard toFIG. 11. Devices, such as smartphones, tablets, and smartwatches, are generally collectively referred to as mobile devices or user equipment. Further, although the various data storage elements are illustrated as part of the computer1100, the storage may also or alternatively include cloud-based storage accessible via a network, such as the Internet or server based storage.

Processing unit1102may include multiple core processors in one embodiment executing an operating system that includes a kernel thread scheduler. Memory1103may include volatile memory1114and non-volatile memory1108. Computer1100may include—or have access to a computing environment that includes a variety of computer-readable media, such as volatile memory1114and non-volatile memory1108, removable storage1110and non-removable storage1112. Computer storage includes random access memory (RAM), read only memory (ROM), erasable programmable read-only memory (EPROM) or electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technologies, compact disc read-only memory (CD ROM), Digital Versatile Disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium capable of storing computer-readable instructions.

Computer11.00may include or have access to a computing environment that includes input interface1106, output interface1104, and a communication interface1116. Output interface1104may include a display device, such as a touchscreen, that also may serve as an input device. The input interface1106may include one or more of a touchscreen, touchpad, mouse, keyboard, camera, one or more device-specific buttons, one or more sensors integrated within or coupled via wired or wireless data connections to the computer1100, and other input devices. The computer may operate in a networked environment using a communication connection to connect to one or more remote computers, such as database servers. The remote computer may include a personal computer (PC), server, router, network PC, a peer device or other common DFD network switch, or the like. The communication connection may include a Local Area Network (LAN), a Wide Area Network (WAN), cellular, WiFi, Bluetooth, or other networks. According to one embodiment, the various components of computer1100are connected with a system bus1120.

Computer-readable instructions stored on a computer-readable medium are executable by the processing unit1102of the computer1100, such as a program1118. The program1118in some embodiments comprises software that, when executed by the processing unit1102, performs network switch operations according to any of the embodiments included herein. A hard drive, CD-ROM, and RAM are some examples of articles including a non-transitory computer-readable medium such as a storage device. The terms computer-readable medium and storage device do not include carrier waves to the extent carrier waves are deemed too transitory. Storage can also include networked storage, such as a storage area network (SAN). Computer program1118may be used to cause processing unit1102to perform one or more methods or algorithms described herein.

Various embodiments provide for core partitioning between real-time and non-real-time workloads. Two levels of scheduling that multiple kernel thread context into multiple lightweight user space task context and allow user space preemption of lightweight tasks provides a flexible user space real-time scheduler design that ensure the ability to meet service level agreement response commitments for real-time tasks without having to modify an operating system kernel thread scheduler.