Adaptive scheduling technique for mission critical systems

• US 6,728,749 B1
• Filed: 09/05/2000
• Issued: 04/27/2004
• Est. Priority Date: 09/05/2000
• Status: Expired due to Fees

• Current Assignee: United States Department Of Health And Human Services
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Richardson, Paul C.
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US09/655,628
• Time in Patent Office: 1,330 Days
• Field of Search: 709/200, 709/201, 709/203, 709/217, 709/218, 709/219, 709/220, 709/223, 709/224, 709/226, 709/227
• US Class Current: 709/200
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

An improved scheduling system which normally schedules the operation of number of functions using a shared resource based on time considerations is modified so as to provide a means to predict when the system has a condition that may cause the system to operate below the level required to operate all the functions. When the warning condition is triggered, the scheduler shifts to value based system where critical systems are given priority based on their criticality to the survival of the system.

Claims

1. An improved method of scheduling the processing of a plurality of different systems that require the usage of a shared resource, for processing a plurality of different system messages, the messages having a deadline value before which they should be processed, using a scheduling algorithm that schedules using a time based protocol using the deadline value comprising the steps of:

designing a resource that has an excess capacity such that it is capable of operating on all the systems messages in a timely fashion so that all systems served by the resource will have all messages of all the systems acted upon before each individual message deadline requirement under normal conditions;

assigning each of the systems a mission critical or non critical rating based on the effect of a given systems degradation on the continued ability of the system to function;

decrementing the deadline values of each mission critical system by an amount equal to a worst case blocking time to absorb a portion of the unused capacity under normal operating conditions;

apportioning any remaining capacity of the shared system among the mission critical systems, to absorb any remaining capacity, of the shard resource to determine a proto-scheduling deadline for all the mission critical systems;

assigning value functions to the mission critical systems, each mission critical systems having a function related to its performance characteristics;

monitoring the shared resource as it schedules the messages using the time based algorithm the monitoring having means to determine when the mission-critical systems will be scheduled late based on the proto-deadline previously calculated;

shifting to a value based scheduling system where the messages for mission critical systems are scheduled for use of the shared resource based on the value assigned by the value function the shared resource being scheduled based on the value function until the systems has run one full cycle of all mission critical systems within the limits of the proto-scheduling deadline at which time the scheduling will be returned to the time based mode and all systems will be returned to the normal state.