| Methods and apparatus for sharing slack in a time-partitioned system -> Monitor Keywords |
|
|
  Methods and apparatus for sharing slack in a time-partitioned systemUSPTO Application #: 20080028415Title: Methods and apparatus for sharing slack in a time-partitioned system Abstract: In a multitasking system executing real-time harmonic and dynamic tasks having various priority levels, slack is stolen from both timeline and reclaimed slack to enable the execution of high priority non-essential tasks on a best efforts basis. Counts of the amount of slack consumed, slack reclaimed, and periodic compute time consumed are maintained by individual priority level and dynamically updated at certain times. Idle time is calculated by priority level. Available slack is calculated, and slack is allocated and consumed by rate, with the highest rate first and the lowest rate last. Slack is made available to tasks in more than one time partition. All slack belongs to a common system-wide pool of slack obtained from any one or more of the time partitions. Common slack can also be time-shared by static, non-harmonic tasks residing in different time partitions. Also described are a computer system and various methods that perform slack scheduling in a time-partitioned system. (end of abstract)
Agent: Honeywell International Inc. - Morristown, NJ, US Inventors: Pamela A. Binns, Aaron R. Larson USPTO Applicaton #: 20080028415 - Class: 718107000 (USPTO) Related Patent Categories: Electrical Computers And Digital Processing Systems: Virtual Machine Task Or Process Management Or Task Management/control, Task Management Or Control, Process Scheduling, Multitasking, Time Sharing The Patent Description & Claims data below is from USPTO Patent Application 20080028415. Brief Patent Description - Full Patent Description - Patent Application Claims
RELATED APPLICATIONS [0001] The present application is related to the following applications, which are assigned to the same assignee as the present application: [0002] Ser. No. 09/312,592, entitled "Task Scheduling and Message Passing"; [0003] Ser. No. 08/914,924, entitled "Slack Scheduling for Improved Response Times of Period Transformed Processes"; and [0004] Ser. No. 08/915,415, entitled "Slack Scheduling Applied to Incremental Periodic Processes" (now abandoned). [0005] The present application is also related to the following application, which is assigned to the same assignee as the present application and which was filed on even date herewith: [0006] Ser. No. 09/751,955, entitled "Methods and Apparatus for Slack Stealing With Dynamic Threads". COPYRIGHT NOTICE/PERMISSION [0007] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright .COPYRGT.1999, Honeywell, Inc., All Rights Reserved. TECHNICAL FIELD [0008] The present invention relates generally to task scheduling within a multitasking system and, in particular, to determining available slack and allocating slack to high priority non-critical tasks. BACKGROUND [0009] Computer processes are often subdivided into a variety of functions which may be executed as tasks in serial and/or parallel fashion. These computer processes can be used to gather and act upon information, and to bring about some result in response to the information. These functional task systems find use in a variety of important environments. Examples may include monitor and control of an industrial process, such as a power generation and distribution system, or monitor and control of complex equipment, such as an aircraft or spacecraft. [0010] In real-time systems, such as those mentioned above, execution of tasks can include both periodic tasks and aperiodic tasks. One known way of executing periodic tasks is to use rate monotonic scheduling (RMS). The classical RMS formulation is for strictly periodic task sets. To specify a periodic task set, each of n tasks, say .tau..sub.i, where 1.ltoreq.i.ltoreq.n, is associated with a period T.sub.i and a worst case compute time C.sub.i. Each task .tau..sub.i will be dispatched and executed at the rate 1/T.sub.i, and in worst case it will consume processor time equal to C.sub.i at each dispatch. Each task is implicitly assigned a priority which is determined by its rate (or equivalently, the inverse of its period), with priority equal to the ranking of the rate. [0011] The RMS scheduler schedules periodic tasks having hard deadlines. Viable real-time systems must also be capable of executing aperiodic tasks, which can have hard deadlines or soft deadlines. It is desirable for a task scheduling system to schedule a mixture of periodic and aperiodic tasks in such as way that all periodic task deadlines are met and the response times for the aperiodic tasks are as small as possible. [0012] In "An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems", John P. Lehoczky and Sandra Ramos-Thuel, Real-Time Systems Symposium, IEEE Proceedings, December, 1992, there is described a slack-stealing algorithm. This algorithm creates a passive task which, when prompted for service, attempts to make time for servicing aperiodic tasks by "stealing" all the processing time it can from the periodic tasks without causing their deadlines to be missed. This is equivalent to "stealing slack" from the periodic tasks. The slack-stealing algorithm was demonstrated to provide substantial improvements in the response times for aperiodic tasks. In addition, the slack stealing algorithm was described as further improved by cooperating with a reclaiming algorithm that makes available for aperiodic service any processing time unused by the periodic tasks when they require less than their worst-case execution times. [0013] It is known in prior data processing systems to employ time partitioning, wherein time is divided into partitions, and each partition is guaranteed a certain amount of execution time. Time partitioning is useful in encapsulating the effects of timing faults within a time partition. Time fault isolation can significantly reduce system development and maintenance costs, since only tasks within a time partition need to be checked for timing correctness. However, in known time partitioning systems, a disadvantage is that unused processing time in one partition is not made available to tasks in other time partitions, resulting in unused processor capacity. [0014] Thus there is a significant need in the art for a task scheduler that can find slack in a time-partitioned system and make it available to tasks in more than one time partition. SUMMARY [0015] The invention deals with task scheduling for a set of periodic and aperiodic tasks, in an environment wherein threads are executing in a time-partitioned system. [0016] In one embodiment, the invention provides a data processing system that executes tasks in different time partitions. The invention further provides a method of scheduling tasks that includes determining available slack. The available slack can include timeline and/or reclaimed slack. The invention further includes allocating slack to non-essential tasks in different time partitions. [0017] In another embodiment, the invention provides a time-partitioned system that includes a processor. A plurality of tasks are operating on the processor. Each task of the plurality of tasks is of a task type selected from the group consisting of essential and non-essential. Each task of the plurality of tasks has associated with it at least one worst case execution time. The time-partitioned system further includes an executive in communication with the processor and controlling dispatching of tasks on the processor. The executive includes a first module that determines available slack, and the executive further includes a second module that allocates available slack to non-essential tasks in different time partitions. In one embodiment, the time-partitioned system is a flight control system. [0018] In yet another embodiment, the invention provides a machine-readable medium having instructions stored thereon capable of causing a processor to carry out a method. The method includes scheduling tasks to execute in different time partitions, determining available slack (such as timeline and/or reclaimed slack), and allocating slack to non-essential tasks in different time partitions. BRIEF DESCRIPTION OF THE DRAWINGS Continue reading... Full patent description for Methods and apparatus for sharing slack in a time-partitioned system Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Methods and apparatus for sharing slack in a time-partitioned system patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Methods and apparatus for sharing slack in a time-partitioned system or other areas of interest. ### Previous Patent Application: Efficient processing of operator graphs representing three-dimensional character animation Next Patent Application: System and method for controlling local computer applications using a web interface Industry Class: Electrical computers and digital processing systems: virtual machine task or process management or task management/control ### FreshPatents.com Support Thank you for viewing the Methods and apparatus for sharing slack in a time-partitioned system patent info. IP-related news and info Results in 2.45807 seconds Other interesting Feshpatents.com categories: Software: Finance , AI , Databases , Development , Document , Navigation , Error |
||
