System for real-time scheduling in an asynchronous transfer mode communication network

Patent metadata

Field	Value
Publication number	US-11573825-B2
Application number	US-202117205065-A
Country	US
Kind code	B2
Filing date	Mar 18, 2021
Priority date	Mar 16, 2018
Publication date	Feb 7, 2023
Grant date	Feb 7, 2023

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 real-time system for determining rate-monotonic scheduling feasibility of tasks of an asynchronous transfer mode communication network and executing feasible tasks, comprising:
a pre-emptive real-time database; and
a pre-emptive real-time processor having circuitry configured to:
sort 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;
split 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:
transfer a first enhanced data packet having a first set of processing instructions from a sorter engine to a feasibility tester engine;
test the first subset according to the first set of processing instructions using the inexact condition test;
sort 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:
sort 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;
determine 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;
filter out one or more tasks of the second subset which cannot be scheduled using the inexact condition test or the exact condition test;
transfer a second enhanced data packet having a second set of processing instructions from the sorter engine to the feasibility tester engine;
test 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;
sort the tested remaining tasks of the second subset into a fourth scheduling priority order;
execute the sorted and tested first subset:
execute the sorted and tested remaining tasks of the second subset; and
transfer and retrieve data to and from the pre-emptive real-time database.

2. The system of claim 1 , wherein the system comprises a uniprocessor system.

3. The system of claim 1 , configured to be executed with one of an operating system scheduler, cloud-based gaming, robotics, avionics, or vehicles.

4. The system of claim 1 , wherein the pre-emptive real-time processor includes the sorter engine, a splitter engine, the feasibility tester engine, and an execution engine.

5. The system of claim 1 , wherein the pre-emptive real-time database includes a plurality of priority lists, a plurality of divided test lists, and a plurality of test results.

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