bits.

FREE CONTRIBUTION CHRONOLOGY · 1961–1969

From batch to dialogue

What must change for a computer to become a responsive, shared, dependable medium?

The historical question

Time-sharing multiplexed scarce compute; Sketchpad made state directly manipulable; Engelbart demonstrated linked collaborative work; Apollo software used priorities and restartable tasks to survive overload.

Interactivity is a system property created by scheduling, representation, feedback, collaboration, and failure policy, not by a display alone.

Responsiveness is a scheduling property

Suppose three ready tasks A, B, and C each need 30 ms of CPU work. Running A to completion before B begins makes C wait 60 ms before its first CPU turn. Round-robin scheduling with a 10 ms quantum lets C begin after approximately 20 ms, ignoring scheduling overhead. Total required CPU work is still 90 ms. Better initial response does not mean less total work.

Human interaction adds another boundary. A command should produce feedback that tells the user whether it was received, whether work is still in progress, and whether a state change succeeded. Fast visual feedback can coexist with a long background operation. Without clear state, users may repeat a command and accidentally trigger duplicate work.

Time-sharing, graphical manipulation, collaboration, and priority-based recovery addressed different parts of this problem. A graphical display alone does not create responsive interaction. Scheduling determines who runs; representation determines what can be selected and changed; feedback exposes state; overload policy chooses what to defer or discard. Evaluate a system with a concrete workload, including slow operations and errors, rather than only a smooth demonstration.

What the evidence does not establish

Demonstrations make a future visible, but deployment also depends on hardware cost, institutions, training, standards, and production engineering.

Reconstruction exercise

Compare C’s first service time under completion-order scheduling and 10 ms round robin. Add a 2 ms switching cost and explain the tradeoff qualitatively.

Worked solution

With no switching overhead, C first runs at 60 ms in completion order and 20 ms in round robin. A2 ms transition cost increases time spent outside useful task execution; frequent switches can improve access latency while reducing throughput. Exact totals depend on whether the initial dispatch and final switch are counted, so state that convention before calculating. The scheduling objective must say whose delay matters.

Test the limits and transfer the idea

1. Scheduling trace · allow 30 minutes

Improve a short task without reducing total work

Task A arrives at 0 and needs 90 ms CPU; task B arrives at 10 ms and needs 5 ms. A context switch between different tasks costs 1 ms, including a switch after one finishes; no overhead is charged when the only ready task continues. Compare nonpreemptive FIFO with round robin of quantum 10 ms, choosing waiting B when A's first quantum ends. Give B's start/completion times and A's completion time. Separate B's response delay from total CPU work.

Get a starting hint

The arrival at 10 ms coincides with A's first quantum boundary; place the switch before B runs.

Compare your reasoning with the worked solution

FIFO runs A from 0 to 90, switches during 90–91, then runs B until 96. B waits 81 ms for first service and completes 86 ms after arrival; A completes at 90. Round robin runs A from 0 to 10, switches 10–11, and runs B 11–16. A resumes after the switch 16–17 and finishes its remaining 80 ms at 97. B's first-service delay is 1 ms and its arrival-to-completion time is 6 ms. Useful CPU work stays 95 ms, but round robin uses two switches rather than one. Corbató's oral history is primary participant testimony; this explicit schedule is a modern model and not a measured CTSS trace.

Check your reasoning

  • Places switches consistently and computes all completion times.
  • Separates waiting/response from useful work and overhead.
  • States the historical status of the schedule.

2. Priority and resource analysis · allow 30 minutes

An overload policy needs a schedulability argument

In a fictional 100 ms control interval, navigation needs 40 ms, stabilization 35 ms, radio processing 20 ms, and an optional display refresh 30 ms. All are ready at the start and share the interval deadline; ignore preemption overhead. Can all finish? Which stated optional work can be deferred to preserve mandatory work? Now a low-priority display routine holds a lock needed by navigation for 10 ms before navigation can run. Explain why naming priorities alone no longer proves the deadline.

Get a starting hint

First sum work under the simplified model, then account for blocking outside the intended mandatory schedule.

Compare your reasoning with the worked solution

All work totals 125 ms, so it cannot fit in 100. Deferring the 30 ms display leaves 95 ms mandatory work and five milliseconds of slack, so a feasible sequential schedule exists in the no-overhead model. A ten-millisecond blocking interval before useful mandatory work would push completion to 105 ms, missing the deadline. The design must avoid that blocking, bound it within available slack, or change work/deadlines. Priority inheritance can reduce some blocking mechanisms but does not magically shorten an unavoidable critical section. NASA's Apollo history is evidence about its actual team and software decisions; these task names, costs and lock scenario are invented. Transferring the principle requires an explicit worst-case execution and resource analysis, not copying an achievement slogan.

Check your reasoning

  • Finds 125 ms overload and 95 ms mandatory demand.
  • Accounts for blocking against five milliseconds of slack.
  • Distinguishes a priority policy from a complete timing proof.

Check your understanding

What does a smaller time slice generally trade against responsiveness?

  • The existence of memory
  • More frequent scheduling overhead
  • The number of source-code variables
Explanation

With no switching overhead, C first runs at 60ms in completion order and 20ms in round robin. A2ms transition cost increases time spent outside useful task execution; frequent switches can improve access latency while reducing throughput. Exact totals depend on whether the initial dispatch and final switch are counted, so state that convention before calculating. The scheduling objective must say whose delay matters.

Sources and further reading