METHOD AND APPARATUS IMPLEMENTED IN PROCESSORS FOR REAL-TIME SCHEDULING AND TASK ORGANIZATION BASED ON RESPONSE TIME ORDER OF MAGNITUDE

• US 20160321111A1
• Filed: 07/12/2016
• Published: 11/03/2016
• Est. Priority Date: 10/04/2012
• Status: Active Grant

• Current Assignee: Dickson, Lawrence J.
• Original Assignee: Dickson, Lawrence J.
• Inventors: Dickson, Lawrence J.
• Granted Patent: US 9,645,853 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A task scheduling method is disclosed, where each processor core is programmed with a short list of priorities, each associated with a minimum response time. The minimum response times for adjacent priorities are different by at least one order of magnitude. Each process is assigned a priority based on how its expected response time compares with the minimum response times of the priorities. Lower priorities may be assigned a timeslice period that is a fraction of the minimum response time. Also disclosed is a task division method of dividing a complex task into multiple tasks is; one of the tasks is an input gathering authority task having a higher priority, and it provides inputs to the other tasks which have a lower priority. A method that permits orderly shutdown or scaling back of task activities in case of resource emergencies is also described.

Claims

1. A method implemented in a processor having one or more logical cores for programming a major task which has a defined response time requirement between one or more inputs and outputs depending upon such inputs, comprising:

subdividing the major task into one first task and one or more second tasks, the first task having a higher priority than the second tasks, the first task having an associated first response time requirement, each second task defining a second output and having an associated second response time requirement, so that the outputs of the major task are produced within the defined response time requirement of the major task;

the first task receiving input and timing from one or more sources and using them to create one or more packets with data and timing for corresponding second tasks; and

each of the second tasks receiving a packet and producing outputs based on the data and timing contained in the received packet and a state received previously by the second task to produce the second output, wherein the data and timing contained in the packet received by the second task, together with the state received previously by the second task, produces enough state to enable the second task to produce the second output within the second response time requirement.

2. A method implemented on a computer for executing tasks, comprising:

executing a first task, the first task having a first required output depending on an input, and a required response time between the input and the first required output, including;

(a) executing first predefined program code of the first task; and

(b) upon reception of a shutdown or modification signal by the first task, wherein the shutdown signal is received before the first required output is produced;

(b1) executing second predefined program code of the first task, the second program code defining a second required output which is different from the first required output;

(b2) producing the second required output within the required response time of the first task without producing the first required output while reducing an amount of resources being utilized by the task; and

(b3) if the shutdown or modification signal was a shutdown signal, shutting down the first task after producing the second required output; and

executing a second task, the second task being executed both before and after the first task receives the shutdown or modification signal and responds to that signal by outputting the second required output and in the case of a shutdown signal by shutting down, wherein after the first task receives the shutdown or modification signal, the second task utilizes resources previously utilized by the first task, without redefining any required output of the second task.