NDLI: On means to provide flexibility in scheduling

Please wait, while we are loading the content...

A testbed for investigating real-time Ada issues

Comprehensive scheduling controls for Ada tasking

The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks

On means to provide flexibility in scheduling

A practical application of the ceiling protocol in a real-time system

Priority inversion and its control: An experimental investigation

Improving immediacy in Ada

Asynchronous transfer of control and scheduling problems

Interrupts and Ada

Asynchronous transfer of control in Ada

Communication between Ada programs in DIADEM

Three steps to distribution: partitioning, configuring, and adapting

Ada for distributed systems

Implementation of task types in distributed Ada

Supporting Ada in a distributed environment

Fault tolerant distributed Ada

A new approach to fault tolerance in distributed Ada programs

On means to provide flexibility in scheduling

Content Provider	ACM Digital Library
Author	Liu, J. W. S. Lin, K. J.
Abstract	It is well-known that scheduling tasks to meet deadlines in hard real-time systems is difficult. Algorithms (such as the rate-monotone algorithm [1,2]) that guarantee deadlines are met for wide ranges of task execution times and system load typically do not achieve high processor utilization. On the other hand, algorithms (such as the earliest-deadline-first algorithm [1-4]) that achieve optimal processor utilization may not degrade gracefully in the presence of transient overload.The imprecise computation approach was proposed recently [5-8] as a means to provide flexibility in scheduling. In a system that supports imprecise computations, intermediate results produced by prematurely terminated server processes are made available to their client processes. By making results of poorer quality available when the results of desirable quality cannot be obtained in time, real-time services, possibly of degraded quality, are provided on a timely basis. This approach makes it possible to have scheduling algorithms that guarantee schedulability and achieve high processor utilization while the system load fluctuates.Specifically, in the imprecise computation approach, real-time processes are designed to have the monotone property; a process is said to have this property and is called a monotone process if the accuracy of its intermediate result is non-decreasing as more time is spent to obtain the result. Iterative algorithms, multiphase protocols, and dynamic programming are examples of methods that can be used to implement monotone processes. The result produced by a monotone process when it terminates normally is the desired result; this result is said to be a precise one. External events such as timeouts and failures may cause a process to terminate prematurely. If the intermediate result produced by a server process when it terminates prematurely is saved and made available, the client process may still find the result usable and, hence, acceptable; such a result is said to be an imprecise one. In a system that supports imprecise computations, the intermediate result produced by each server process is recorded at appropriate instances of the process's execution. Programming language constructs are provided to allow the programmer to specify the intermediate result variables to be recorded and the time instants to record them. In addition to the intermediate result variables, the programmer also specifies a set of error indicators. The latest recorded values of the intermediate result variables and error indicators are made available to the client process upon premature termination of the server process. By examining these error indicators, the client process can decide whether an intermediate result is acceptable when the desired, precise result cannot be obtained in time.The imprecise computation approach makes scheduling hard real-time tasks significantly easier for the following reason: To ensure that all deadlines are met requires only that the assigned processor time of every task, i.e. the amount of time during which the processor is assigned to run the task, be equal to or larger than the amount of time required for the task to produce an acceptable result, hereafter referred to as its minimal execution time. The scheduler may choose to terminate a task any time after it has produced an acceptable result. It is not necessary to wait until the execution of the task is finished. Consequently, the amounts of processor time assigned to tasks in a valid schedule can be less than the amounts of time required to finish executing the tasks, commonly referred to as their execution times.The following strategy has been proposed for scheduling hard real-time tasks when imprecise results are available [7,8]: Each task is considered to be consisting of two portions, the mandatory portion and the optional portion. The execution time of its mandatory portion is equal to the minimal execution time of the task, and execution time of the optional portion is equal to the difference between its execution time and its minimal execution time. The mandatory portions are treated by the scheduler as hard real-time tasks the execution of which must be finished by their deadlines, and the optional portions are treated as soft real-time tasks which do not have to be finished. When the scheduling algorithm used is priority-driven, the mandatory portion of every task should be given a priority higher than the priorities of the optional portions of all tasks. This priority assignment ensures that whenever there are tasks ready to run, the processor is assigned to run their mandatory portions. When the mandatory portions of all ready tasks are completed, the spared processor time prior to the deadlines of these tasks is spent to run their optional portions in order to improve the quality of the results produced by the tasks. Several simple heuristic scheduling algorithms based on this general strategy have been designed. These algorithms illustrate that it is possible to guarantee schedulability and optimize processor utilization while keeping the chosen performance measures of result quality high.
Starting Page	32
Ending Page	34
Page Count	3
File Format	PDF
ISBN	0897912950
DOI	10.1145/58612.59372
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1988-06-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in