Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

Liu, C. L., & Layland, J. W. (1973). Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. ACM, 20(1), 46-61.

Type

Journal article

Intellectual base

Primary research

Year

1973

Volume

20

Issue

1

Pages

46-61

DOI

10.1145/321738.321743

DOI registrant

Association for Computing Machinery

Link

https://www.cs.ru.nl/~hooman/DES/liu-layland.pdf

Cited from

operations_research

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Scheduling
  • … process scheduling for multiprogramming (1950s-1960s); Liu and Layland's (1973) rate-monotonic and EDF analysis for hard real-time systems, proving EDF optimal for preemptive scheduling of independent periodic tasks; and modern kernel schedulers like Linux CFS (Completely Fair Scheduler, kernel 2.6.23+).

    Supported in partVerified against the publisher's abstract

    The publisher abstract backs the 1973 rate-monotonic and deadline-driven (EDF) analysis — a fixed-priority utilization bound and full utilization under dynamic deadline priorities — but not the sentence's other clauses.

    “It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines.”

    Read by an automated reader; not a human review. How support was checked

Domain-specific

• Fixed-Priority Pre-emptive Scheduling
  • Liu and Layland explicitly distinguish such priorities, assigned once for a task, from dynamic priorities that can change from request to request.

Mechanisms

• Deadline Queue
  • Its strength is legibility and provable behavior when the system is not overloaded: earliest-deadline-first is optimal at meeting deadlines whenever a feasible schedule exists, and it makes "too long" a first-class property of the queue rather than an afterthought.

    This sourceEstablishes earliest-deadline scheduling's optimal deadline-feasibility property within the paper's stated real-time task model.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 3 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://doi.org/10.1145/321738.321743 ×1

Registry ID ref:27f9a3805417 · see in the full table