AN OPTIMAL SCHEDULING ALGORITHM FOR PREEMPTABLE REAL-TIME TASKS

被引：1

作者：

KIM, YS

机构：

[1] Electronics and Information System Center, Korea Academy of Industrial Technology, Seoul, 152-020, 371-36, Karibong-dong, Kuro-ku

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 50卷 / 01期

关键词：

REAL-TIME SYSTEMS; SCHEDULING; ALGORITHMS;

D O I：

10.1016/0020-0190(94)90043-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

An optimal scheduling algorithm is presented for real-time tasks with arbitrary ready times and deadlines in single processor systems. The time complexity of the algorithm is O(n log n), which improves the best previous result of O(n(2)). Furthermore, the lower bound of the worst-case time complexity of the problem is shown to be of O(n log n) and therefore the time complexity of the presented algorithm is shown to be the lower bound.

引用

页码：43 / 48

页数：6

共 13 条

[1]

Blazewicz J., 1976, MODELING PERFORMANCE

[2]

Cheng Sheng, 1988, TUTORIAL HARD REAL T, P150

[3]

Dertouzos M., 1974, P IFIP C

[4]

FRIEDMAN N, 1972, 13TH P IEEE S SWITCH, P139

[5] SOME SIMPLE SCHEDULING ALGORITHMS [J].

HORN, WA .

NAVAL RESEARCH LOGISTICS, 1974, 21 (01) :177-185

[6]

Horowitz E., 1978, FUNDAMENTALS COMPUTE

[7]

KISE H, 1978, OPER RES, V26

[8]

Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

[9]

LAWER EL, 1973, MANAGEMENT SCI, V19

[10]

Lenstra J.K., 1977, COMPLEXITY MACHINE S

← 1 2 →