WO2002054237A3 - Methods and apparatus for slack stealing with dynamic trheads - Google Patents

Methods and apparatus for slack stealing with dynamic trheads Download PDF

Info

Publication number
WO2002054237A3
WO2002054237A3 PCT/US2001/017738 US0117738W WO02054237A3 WO 2002054237 A3 WO2002054237 A3 WO 2002054237A3 US 0117738 W US0117738 W US 0117738W WO 02054237 A3 WO02054237 A3 WO 02054237A3
Authority
WO
WIPO (PCT)
Prior art keywords
slack
consumed
time
tasks
rate
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US2001/017738
Other languages
French (fr)
Other versions
WO2002054237A2 (en
Inventor
Pamela A Binns
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Honeywell International Inc
Original Assignee
Honeywell International Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US09/751,955 external-priority patent/US7140022B2/en
Application filed by Honeywell International Inc filed Critical Honeywell International Inc
Priority to EP01939818A priority Critical patent/EP1433054A2/en
Priority to JP2002554867A priority patent/JP2004533667A/en
Publication of WO2002054237A2 publication Critical patent/WO2002054237A2/en
Anticipated expiration legal-status Critical
Publication of WO2002054237A3 publication Critical patent/WO2002054237A3/en
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G06F9/4887—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues involving deadlines, e.g. rate based, periodic

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Debugging And Monitoring (AREA)

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 lowerest rate last. Slack is made available to tasks in more than one partition. All slack belongs to a common system-wide pool of slack. Also described are a computer system and various methods that perform slack scheduling in a time-partioned system.
PCT/US2001/017738 2000-12-29 2001-06-01 Methods and apparatus for slack stealing with dynamic trheads Ceased WO2002054237A2 (en)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP01939818A EP1433054A2 (en) 2000-12-29 2001-06-01 Methods and apparatus for slack stealing with dynamic trheads
JP2002554867A JP2004533667A (en) 2000-12-29 2001-06-01 Method and apparatus for slack steel with dynamic threads

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/751,955 US7140022B2 (en) 2000-06-02 2000-12-29 Method and apparatus for slack stealing with dynamic threads
US09/751,955 2000-12-29

Publications (2)

Publication Number Publication Date
WO2002054237A2 WO2002054237A2 (en) 2002-07-11
WO2002054237A3 true WO2002054237A3 (en) 2004-04-01

Family

ID=25024230

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2001/017738 Ceased WO2002054237A2 (en) 2000-12-29 2001-06-01 Methods and apparatus for slack stealing with dynamic trheads

Country Status (3)

Country Link
EP (1) EP1433054A2 (en)
JP (1) JP2004533667A (en)
WO (1) WO2002054237A2 (en)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2219112A3 (en) * 2009-01-23 2012-08-15 Imec Method and system for operating in hard real time
CN101710292B (en) * 2009-12-21 2013-03-27 中国人民解放军信息工程大学 Reconfigurable task processing system, scheduler and task scheduling method
JP5689239B2 (en) 2010-02-03 2015-03-25 昭和シェル石油株式会社 Gasoline engine and diesel engine oil
US10768984B2 (en) 2015-06-11 2020-09-08 Honeywell International Inc. Systems and methods for scheduling tasks using sliding time windows
US9465664B1 (en) * 2015-09-09 2016-10-11 Honeywell International Inc. Systems and methods for allocation of environmentally regulated slack

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
ATLAS, A; BESTAVROS, A: "Slack Stealing Job Admission Control", TECHNICAL REPORT, 2 May 1998 (1998-05-02), BOSTON UNIVERSITY, pages 1 - 14, XP001173165 *
BINNS P: "Incremental rate monotonic scheduling for improved control system performance", REAL-TIME TECHNOLOGY AND APPLICATIONS SYMPOSIUM, 1997. PROCEEDINGS., THIRD IEEE MONTREAL, QUE., CANADA 9-11 JUNE 1997, LOS ALAMITOS, CA, USA,IEEE COMPUT. SOC, US, 9 June 1997 (1997-06-09), pages 80 - 90, XP010232467, ISBN: 0-8186-8016-4 *
DAVIS, R I: "Approximate Slack Stealing Algorithms for Fixed Priority Pre-emptive Systems", TECHNICAL REPORT YCS 217, November 1993 (1993-11-01), UNIVERSITY OF YORK, XP002263065 *
LEHOCZKY, J P; RAMOS-THUEL, S: "Scheduling Periodic and Aperiodic Tasks Using the Slack Stealing Algorithm", ADVANCES IN REAL TIME SYSTEMS, 1995, pages 172 - 195, XP001176715 *
RIPOLL I ET AL: "AN OPTIMAL ALGORITHM FOR SCHEDULING SOFT APERIODIC TASKS IN DYNAMIC-PRIORITY PREEMPTIVE SYSTEMS", IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, IEEE INC. NEW YORK, US, vol. 23, no. 6, 1 June 1997 (1997-06-01), pages 388 - 399, XP000727454, ISSN: 0098-5589 *
TIA; LIU; SHANKAR: "Aperiodic Request Scheduling in Fixed-Priority Preemptive Systems", TR UIUCDCS-R-94-1859, July 1994 (1994-07-01), UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN, pages 1 - 40, XP001176710 *

Also Published As

Publication number Publication date
EP1433054A2 (en) 2004-06-30
JP2004533667A (en) 2004-11-04
WO2002054237A2 (en) 2002-07-11

Similar Documents

Publication Publication Date Title
Luo et al. Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems
Aydin et al. Energy-aware partitioning for multiprocessor real-time systems
WO2001020446A3 (en) Method for time partitioned application scheduling in a computer operating system
US5628013A (en) Apparatus and method for allocating processing time in a frame-based computer system
Kato et al. Portioned EDF-based scheduling on multiprocessors
WO2002054238A3 (en) Methods and apparatus for sharing slack in a time-partitioned system
WO2005069155A3 (en) Method and apparatus for task schedulin in a multi-processor system based on memory requirements
Dudani et al. Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints
CN101470519A (en) Apparatus and method for controlling power management
EP0794481A3 (en) Multitask processing system with variable clock rate for power saving
CA2200929A1 (en) Periodic process scheduling method
Zhang et al. Energy aware fixed priority scheduling for real time sporadic task with task synchronization
CA2471426A1 (en) Apparatus and method of dynamically repartitioning a computer system in response to partition workloads
EP1376352A3 (en) Spin-Yielding in Multi-Threaded Systems
CN109324891A (en) A kind of periodic duty low-power consumption scheduling method of ratio free time distribution
WO2004006098A3 (en) Method and system for real-time multitasking
US20060015876A1 (en) Light weight context switching technique
WO2002054237A3 (en) Methods and apparatus for slack stealing with dynamic trheads
Burns et al. A Practical Method for Increasing Processor Utilisation
Bhatti et al. An inter-task real time DVFS scheme for multiprocessor embedded systems
WO2001035209A3 (en) Modified move to rear list system and methods for thread scheduling
Tsai et al. Scheduling multiple scientific and engineering workflows through task clustering and best-fit allocation
Holenderski et al. An efficient hierarchical scheduling framework for the automotive domain
Niu et al. A hybrid static/dynamic dvs scheduling for real-time systems with (m, k)-guarantee
Dong et al. Flexible mixed-criticality scheduling with dynamic slack management

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AL AM AT AU AZ BA BB BG BR BY CA CH CN CR CU CZ DE DK DM EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK SL TJ TM TR TT TZ UA UG UZ VN YU ZA ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GW ML MR NE SN TD TG

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2001939818

Country of ref document: EP

ENP Entry into the national phase

Ref country code: JP

Ref document number: 2002 554867

Kind code of ref document: A

Format of ref document f/p: F

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

WWP Wipo information: published in national office

Ref document number: 2001939818

Country of ref document: EP