Real-time feasibility systems and methods

Patent metadata

Field	Value
Publication number	US-11042404-B2
Application number	US-201815923171-A
Country	US
Kind code	B2
Filing date	Mar 16, 2018
Priority date	Mar 16, 2018
Publication date	Jun 22, 2021
Grant date	Jun 22, 2021

Abstract

A real-time feasibility device includes circuitry configured to sort tasks into a first scheduling priority order; split the sorted tasks into a first subset which can be scheduled using an inexact condition test and a second subset which cannot be scheduled using the inexact condition test; test the first subset using the inexact condition test; sort the tested first subset into a second scheduling priority order; sort the second subset into a third scheduling priority order; filter out one or more tasks of the second subset which cannot be scheduled using the inexact condition test or the exact condition test; test remaining tasks of the second subset using the exact condition test; sort the tested remaining tasks of the second subset into a fourth scheduling priority order; and execute the sorted and tested first subset and the sorted and tested remaining tasks of the second subset.

First claim

The invention claimed is:

1. A method of determining real-time rate-monotonic scheduling feasibility of tasks of an asynchronous transfer mode communication network and executing feasible tasks, the method comprising:
sorting, via a sorter engine of a pre-emptive real-time processor, a set of tasks of the asynchronous transfer mode communication network into a first scheduling priority order in a descending order of priority based on activation rates of the tasks of the set of tasks;
splitting, via a splitter engine of the pre-emptive real-time processor, the sorted set of tasks into a first subset which can be scheduled using an inexact condition test and a second subset which cannot be scheduled using the inexact condition test, wherein the inexact condition test is an LL-bound test;
transferring a first enhanced data packet having a first set of processing instructions from the sorter engine to a feasibility tester engine;
testing, via the feasibility tester engine, the first subset according to the first set of processing instructions using the inexact condition test;
sorting, via the sorter engine of the pre-emptive real-time processor, the tested first subset into a second scheduling priority order in a descending order of priority based on activation rates of the tasks of the tested first subset;
sorting, via the sorter engine of the pre-emptive real-time processor, the second subset into a third scheduling priority order in an ascending order of priority based on activation rates of the tasks of the second subset;
determining, via circuitry of the pre-emptive real-time processor, whether the second subset can be scheduled using an exact condition test if a calculated response-time for each task of the second subset is less than a corresponding deadline;
filtering out one or more tasks of the second subset which cannot be scheduled using the inexact condition test or the exact condition test;
transferring a second enhanced data packet having a second set of processing instructions from the sorter engine to the feasibility tester engine;
testing, via the feasibility tester engine of the pre-emptive real-time processor, remaining tasks of the second subset according to the second set of processing instructions using the exact condition test, wherein the exact condition test is a response time analysis (RTA) test;
sorting, via the sorter engine of the pre-emptive real-time processor, the tested remaining tasks of the second subset into a fourth scheduling priority order;
executing, via an execution engine of the pre-emptive real-time processor, the sorted and tested first subset; and
executing, via the execution engine of the pre-emptive real-time processor, the sorted and tested remaining tasks of the second subset.

2. The method of claim 1 , wherein the fourth scheduling priority is sorted into a descending order of activation rates of the sorted remaining tasks of the second sub set.

3. The method of claim 1 , which excludes a hyperbolic exact test applied to the tasks.

Assignees

• Univ Imam Abdulrahman Bin Faisal

Inventors

• Alrashed Saleh

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title