Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Before Unix: Early History of Time-Sharing

Jade Allen
November 04, 2016

Before Unix: Early History of Time-Sharing

Most technologists are familiar with the outlines of the Unix origin story. This talk examines what happened before Unix. Where did the concept of time-sharing come from? What were early implementations of the ideas? How did they influence Unix?

Jade Allen

November 04, 2016
Tweet

More Decks by Jade Allen

Other Decks in Technology

Transcript

  1. Whirlwind š Research started in 1944. Navy wanted to build

    a flight simulator to train new pilots. š Team started with an analog computer (but it was too slow and unreliable) š Inspired by ENIAC, decided to work on an electronic digital computer š Parallel digital computer (20,000 ops/second) in 1952 š Design goal of 50,000 ops/second š Memory system was too slow.
  2. “What the computer business needs, has needed, and will probably

    always need is a bigger, better, and faster storage device.” Robert Everett, 1952 [1]
  3. Early computer memory š Whirlwind required 2,000 16 bit words

    of memory š But in the late 40s/early 50s only two types of memory had that much capacity: š Delay line memory š Electrostatic memory
  4. Delay line memory š Roots in WWII radar technology š

    Sequential access. š Bits are represented by sound waves in a medium (usually mercury) which are constantly regenerated and recirculated š Highly temperature sensitive (40C/100F)
  5. Electrostatic memory š Random access š Modified cathode ray tube

    š Set an electrostatic charge on a field of phosphors. š Each lasted about 1 month and cost $1,000. ($10,000 in 2016 dollars) š Each tube could store 1 bit.
  6. Magnetic core memory š Random access š Iron toroid given

    magnetic charge š Reliable š Fast š Cheap(er)
  7. John McCarthy š Invented LISP š Invented garbage collection š

    Involved with ALGOL committee š ACM Turing Award, 1971. š Joined MIT as a research fellow, 1956.
  8. “Time-sharing… meant an operating system that permits each user of

    a computer to behave as though he were in sole control of a computer, not necessarily identical with the machine on which the operating system is running.” John McCarthy, 1983 [2]
  9. Batch Operation š Jobs would be punched on card deck

    and run through a secondary system to magnetic tape. š The tape would be run through the primary system one after another serially. š Output would go to a line printer or another magnetic tape, then printed later š Made developing software very difficult, as one single error would most likely cause an entire run to be wasted. Could take hours or days to try again.
  10. “Computers were originally developed with the idea that programs would…

    solve general problems and… most of the computer time would be spent running these standard programs with new sets of data… The actual situation is much closer to the opposite extreme.” John McCarthy, 1959 [4]
  11. “[Morse] also did not fully appreciate timesharing. He thought it

    was just another thing. At least initially, he did not see it as revolutionary. The appreciation of timesharing was directly proportional to the amount one personally programmed. The more you personally programmed, the more you knew what it meant…” Fernando Corbato, 1990 [3]
  12. Timeline McCarthy arrives at MIT as a research fellow. Proposes

    modifying MIT’s IBM 704 to use interrupts to process user input. MIT asks IBM to modify its installation with its “real time package” developed for Boeing to process wind-tunnel data. 1957 1960 1959
  13. Timeline IBM delivers a 709 with the real time modifications.

    McCarthy demonstrates interactive LISP session with a flexowriter terminal. Hebert Teager joins MIT, takes over time-sharing project from McCarthy. Teager’s proposals do not convince his colleagues. McCarthy calls his ideas “vague” and “ambitious.”[2] Prof. Christopher Strachey publishes a paper entitled “Time Sharing in Large, Fast Computers” for the IFIP conference in Paris. The paper mainly deals with the idea of “multi-programming” (aka concurrency) not McCarthy’s idea of a “virtual computer.” 1957 1960 1959
  14. Timeline McCarthy starts consulting with Bolt, Berenek and Newman (BBN).

    Explains his ideas about timesharing to several principals (including J.C.R. Licklider) and engineers at Digital Equipment (DEC). DEC donates a PDP-1 to MIT to work on a timesharing system by Jack Dennis and his students. 1957 1960 1959
  15. Timeline MIT Computation Center run by Professor Philip Morse begins

    work on a prototype time sharing system using Teager’s 3 modified flexowriter terminals. This programming effort is led by a young post-doc named Fernando Corbato. A time-sharing system is demonstrated in primitive form by Corbato. [8] 1957 1960 1959 1961
  16. Timeline Corbato’s team demonstrates a functional prototype of a system

    that comes to be known as CTSS (Compatible Time Sharing System) in 1962. It enters regular production usage in 1963. [3] McCarthy leaves MIT and goes to Stanford. 1957 1960 1959 1961 1962
  17. Fernando Corbató š US Navy electronics specialist during WWII š

    BA Physics, Cal Tech, 1950 š PhD Physics MIT, 1956 š Post-doc working on Whirlwind š Joined Computation Center as its Asst. Deputy Director, 1957 š Lead designer on Multics, lead programmer on CTSS š ACM Turing Award 1990
  18. [6]

  19. “I still don't understand where all the computer time goes

    in time-sharing installations, and neither does anyone else.” John McCarthy, 1983 [2]
  20. Compatible? š The prototype ran on the Computing Center’s IBM

    709. š The timesharing supervisor ran in core and in the background, other batch oriented jobs could be executed (as they had always done.) š In this way the time-sharing system was “compatible” with the batch jobs already available.
  21. Effort and size š Corbato was the lead. Other programmers

    included Marjorie Merwin-Daggett and Robert Daley. (See co-authors for [5].) š Contemporary compilers of the day were 11-16,000 words (1 word is usually 18 bits) š CTSS supervisor was 12,000 words + 6,000 words for command programs. [7] š [11] has a great introduction how “everyday” users could interact with the system. (Commands included: login, input, edit, load, start) š (This slide deck by itself is almost 100MB including all picture and videos.)
  22. “Most of the battles of creating CTSS involved solving problems

    which at the time did not have standard solutions.” - Fernando Corbato, 1990 [8]
  23. I got 99 problems… š Memory protection (of the supervisor

    and other user’s programs from a user program) š I/O device sharing/multiplexing š Saving and restoring user program state between time slices (called “quanta” in [5]) š Related problem: how much time does a user get? š “Satisfactory” computer responsiveness [5] (200 ms is suggested.)
  24. Breakthrough success… š“For the first time users had persistent online

    storage of programs and data.” š“Remote operation became the norm.” š“[CTSS] suddenly made it especially convenient for users to share and exchange information among themselves.“ [8]
  25. “[T]hen-new transistors and large random- access disk files were absolutely

    critical to the success of time-sharing. The previous generation of vacuum tubes was simply too unreliable for sustained real- time operation…” Fernando Corbato, 1990 [8]
  26. And yet… š“[Users who endured hours of waiting between batch

    jobs] were suddenly restless when response times were more than a second.” š“A one-level file system, suddenly began to chafe.” š“The more we did, the more users wanted.” [8]
  27. “[W]hen you have a multitude of novel issues to contend

    with while building a system, mistakes are inevitable.” Fernando Corbato, 1990 [8] (See [9] for more context)
  28. Multics Myth Busting šIt was a failed system. šIt was

    never completed. šIt was never used in production.
  29. Why? š The CTSS development team felt the need to

    ”do timesharing right” [3] š CTSS had a simple design and the popularity of it did not scale well. š The team of MIT spent a significant amount of time finding industrial partners for a new timesharing hardware and software platform. (GE and Bell Telephone Labs)
  30. Firsts š Memory segments (e.g., pages) in hardware and software,

    š Privilege “rings” around the supervisor (protect memory access), š Virtual memory system (including the idea of “swap”), š Mapping files to virtual memory, š Hardware system could be composed of multiple CPUs, RAM and storage devices. š Wrote the system in a high level language (PL/I) [8,10]
  31. Why did it take so long? š The project team

    came from three different organizations (MIT, GE/Honeywell, Bell Telephone Lab) with different priorities and goals. š There was no BDFL – weak ideas had to be “proven” weak – teams might spend months or weeks working on an idea only to abandon it. š The design was often unnecessarily complex. š No one had ever tried to design an operating system like this before. š There was no full featured functional PL/I compiler until 1967. š PL/I itself had good design ideas and really bad design ideas. (You might call it the Javascript of its day: ubiquitous with many traps.)
  32. “We all learned. That was a brutal period when we

    discovered that we had built a monster. We had several instances of that inside Multics…Yes, one of the problems was that we were all kind of young and naïve. We couldn’t see that we had built something that was too complicated. Only under the duress of realizing it was awful did we dig in and realize it didn’t have to be that way.” - Fernando Corbato, 2006 [12]
  33. “[I]t is that trial and error aspect of system synthesis,

    which I think is the major factor that people underestimate and a huge amount of... the difference between engineering projects to me is the degree that the participants have done it before. If they have done it before it's a piece of cake sometimes; if they have never done it before it can be a hellish adventure.” - Fernando Corbato, 1990 [3]
  34. “In retrospect, [PL-1] was a monstrosity to be trying to

    use to design a system. But our first conviction was we absolutely had to have a compiler language. And I think that one was still dead right. The next problem was that we wanted one that was relatively advanced and flexible and there weren't many choices in those days. And the third key ingredient was that Doug McIlroy and Bob Morris at Bell Labs, who had considerable language expertise and who wanted to take responsibility for the language effort, were quite persuaded that PL-1 was a good choice.” - Fernando Corbato, 1990 [3]
  35. Multics Myth Busting šIt was a failed system. šIt was

    never completed. šIt was never used in production. [9]
  36. “The Unix system was a reaction to Multics. Even the

    name was a joke…[Thompson’s] strategy was clear– Start small and build up the ideas one by one as he saw how to implement them well. As we all know, Unix has evolved and become immensely successful.” - Fernando Corbato, 1990 [8]
  37. Other interesting time-sharing systems šJules Schwartz SDC system (1963) [13]

    šDartmouth Time Sharing System (1964) [14] šProject GENIE 1967 - (Butler Lampson) [15] šTENEX/TOPS-20 (BBN) 1972 [16]
  38. Bibliography š [1]: R . R . Everett: The Whirlwind

    I Computer, Review of Electronic Digital Computers, Joint Computers American Institute of Electrical Engineers- Institute of Radio Engineers Conference, pp. 70-74, February, 1952. š [2]: J. McCarthy: Reminiscences on the History of Timesharing, http://www- formal.stanford.edu/jmc/history/timesharing/timesharing.html š [3]: A. Norberg: Oral history of Fernando Corbato, Babbage Institute, University of Minnesota, 1990. http://hdl.handle.net/11299/107230 š [4]: J. McCarthy: A Time Sharing Operator Program for our Projected IBM 709, memorandum, 1959. http://www-formal.stanford.edu/jmc/history/timesharing-memo.html
  39. Bibliography š [5]: F.J. Corbato: An Experimental Time Sharing System,

    Proceedings of the SJCC 1962. http://larch-www.lcs.mit.edu:8001/~corbato/sjcc62/ š [6]: Timesharing: A solution to computer bottlenecks, 1963. https://www.youtube.com/watch?v=Q07PhW5sCEk š [7]: Saltzer, J.H.: CTSS Technical Notes, 1966, Project MAC Technical Report TR-16. š [8]: Corbato, F.J.: On Building Systems that Will Fail (1990 Turing Award Lecture), Communications of the ACM, September 1991, p72-83. š [9]: Van Vleck, T: The IBM 7094 and CTSS, http://www.multicians.org/thvv/7094.html
  40. Bibliography š [10]: Wilkes, M.V.: Operating Systems in a Changing

    World. Invited Talk SOSP14, 1993. š [11]: Corbato, F.J., et al.: CTSS Programmers Guide, MIT Press, 1963. š [12]: Webber, S: Oral History of Fernando Corbato, Computer History Museum, 2006. š [13]: Norberg, A.: Oral History of Jules Schwartz, Babbage Institute, University of Minnesota, 1989. š [14]: Bull, G.M.: The Dartmouth Time Sharing System, Elias Horwood Publishers, 1980.
  41. Bibliography š [15]: Lampson, B.W.: A User Machine in a

    Time-Sharing System, Proceedings of the IEEE, December 1966, p1766-1774. š [16]: Bobrow, D.G. et al: TENEX, A Paged Time Sharing System for the PDP-10, Communications of the ACM, March 1972, p135-143.