article

Free access

A task-scheduling algorithm for a multiprogramming computer system

Authors:

K. L. Krause,

V. Y. Shen,

H. D. SchwetmanAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 7, Issue 4

Pages 112 - 118

https://doi.org/10.1145/957195.808058

Published: 01 January 1973 Publication History

PDF eReader

Abstract

This paper presents a description and analysis of a task scheduling algorithm which is applicable to third generation computer systems. The analysis is carried out using a model of a computer system having several identical task processors and a fixed amount of memory. The algorithm schedules tasks having different processor-time and memory requirements. The goal of the algorithm is to produce a task schedule which is near optimal in terms of the time required to process all of the tasks. An upper bound on the length of this schedule is the result of deterministic analysis of the algorithm. Computer simulations demonstrate the applicability of the algorithm in actual systems, even when some of the basic assumptions are violated.

References

[1]

Graham, R. L. "Bounds on Multiprocessing Timing Anomalies," SIAM J. on Applied Math. (17, 2) Mar. 1969, (416-429).

Crossref

Google Scholar

[2]

Kleinrock, L. "A Continuum of Time-Sharing Scheduling Algorithms," Proceedings SJCC (36) 1970, (453-458).

Google Scholar

[3]

Muntz, R. R., Coffman, E. G., Jr. "Preemptive Scheduling of Real Time Tasks on Multiprocessor Systems," JACM (17, 2) Apr. 1970, (324-338).

Digital Library

Google Scholar

[4]

Denning, P. J. "The Working Set Model for Program Behaviour," CACM (11,5) May, 1968, (323-333).

Digital Library

Google Scholar

[5]

Chen, Y. E., Epley, D. L. "Memory Requirements in a Multiprocessing Environment," JACM (19,1) Jan. 1972, (57-69).

Digital Library

Google Scholar

[6]

Krause, K. L. "Analysis of Computer Scheduling with Memory Constraints," Ph.D. Dissertation, Computer Sciences Dept., Purdue University, July, 1973.

Digital Library

Google Scholar

[7]

Abell, V. A., S. Rosen, and R. E. Wagner, "Scheduling in a General Purpose Operating System," Proceedings FJCC (37) 1970, (89-96).

Google Scholar

Cited By

View all

Naruszko APrzybylski BRządca K(2021)A Log-Linear -Approximation Algorithm for Parallel Machine Scheduling with a Single Orthogonal ResourceEuro-Par 2021: Parallel Processing10.1007/978-3-030-85665-6_10(151-166)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85665-6_10
Edis EOguz COzkarahan I(2013)Parallel machine scheduling with additional resources: Notation, classification, models and solution methodsEuropean Journal of Operational Research10.1016/j.ejor.2013.02.042230:3(449-463)Online publication date: Nov-2013
https://doi.org/10.1016/j.ejor.2013.02.042
Kroes MPetrica LCotofana SBlott MCoello Coello C(2020)Evolutionary bin packing for memory-efficient dataflow inference acceleration on FPGAProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389808(1125-1133)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389808
Show More Cited By

Index Terms

A task-scheduling algorithm for a multiprogramming computer system
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Multiprocessing / multiprogramming / multitasking
        Scheduling
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

A task-scheduling algorithm for a multiprogramming computer system
SOSP '73: Proceedings of the fourth ACM symposium on Operating system principles

This paper presents a description and analysis of a task scheduling algorithm which is applicable to third generation computer systems. The analysis is carried out using a model of a computer system having several identical task processors and a fixed ...
Scheduling algorithms for multiprogramming in a hard-real-time environment
Readings in hardware/software co-design

The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program function that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper ...
An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems

This paper addresses the problem of preemptive scheduling on parallel-task systems. A parallel-task system consists of several independent tasks, each of which can be executed on one or more processors. Du and Leung introduced the problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 7, Issue 4

October 1973

136 pages

ISSN:0163-5980

DOI:10.1145/957195

Issue’s Table of Contents

SOSP '73: Proceedings of the fourth ACM symposium on Operating system principles
January 1973
137 pages
ISBN:9781450373746
DOI:10.1145/800009
Chairmen:
Herbert Schorr,
Alan Perlis,
Peter Weiner,
W. Donald Frazer

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1973

Published in SIGOPS Volume 7, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
665
Total Downloads

Downloads (Last 12 months)117
Downloads (Last 6 weeks)29

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Naruszko APrzybylski BRządca K(2021)A Log-Linear -Approximation Algorithm for Parallel Machine Scheduling with a Single Orthogonal ResourceEuro-Par 2021: Parallel Processing10.1007/978-3-030-85665-6_10(151-166)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85665-6_10
Edis EOguz COzkarahan I(2013)Parallel machine scheduling with additional resources: Notation, classification, models and solution methodsEuropean Journal of Operational Research10.1016/j.ejor.2013.02.042230:3(449-463)Online publication date: Nov-2013
https://doi.org/10.1016/j.ejor.2013.02.042
Kroes MPetrica LCotofana SBlott MCoello Coello C(2020)Evolutionary bin packing for memory-efficient dataflow inference acceleration on FPGAProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389808(1125-1133)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389808
Helander JSigurdsson S(2005)Self-Tuning Planned Actions Time to Make Real-Time SOAP RealProceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing10.1109/ISORC.2005.51(80-89)Online publication date: 18-May-2005
https://dl.acm.org/doi/10.1109/ISORC.2005.51
Krause KShen VSchwetman H(1975)Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer SystemsJournal of the ACM10.1145/321906.32191722:4(522-550)Online publication date: 1-Oct-1975
https://dl.acm.org/doi/10.1145/321906.321917
Kafura DShen VBrown RGlaze D(1974)Scheduling independent processors with different storage capacitiesProceedings of the 1974 annual conference - Volume 110.1145/800182.810397(161-166)Online publication date: 1-Jan-1974
https://dl.acm.org/doi/10.1145/800182.810397

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations