Third Generation Computer Systems

ABSTRACT

The common features of third generation operating systems are surveyed from a general view, with emphasis on the common abstractions that constitute at least the basis for a “theory” of operating systems. Properties of specific systems are not discussed except where examples are useful. The technical aspects of issues and concepts are stressed, the nontechnical aspects mentioned only briefly. A perfunctory knowledge of third generation systems is presumed.

REFERENCES

• A1: ABATE, J.; AND H. DUBNER. "Optimizing the performance of a drum-like storage." IEEE Trans. Computers C-18, 11 (Nov. 1969), 992-997. A description and analysis of the shortestaccess-time-first queueing discipline, which minimizes the accumulated latency time of requests for rotating-medium auxiliary stores.
• A2: ACM. "Storage Allocation Symposium" (Princeton, N.J., June 1961). Comm. ACM 4, 10 (Oct. 1961). These papers argue the cases and techniques for static and dynamic storage Mloeation. They provide a picture of the state of considered thought on storage allocation as of 1961.
• A3: ACM. "Proc. Symposium on Operating System Principles" (Gatlinburg, Tenn., Oct. 1967). Some of the papers appear in Comm. ACM 11, 5 (May 1968). These papers provide, collectively, a summary of the ideas through the mid 1960s. The session titles are: Virtual Memory, Memory Management, Extended Core Memory Systems, Philosophies of Process Control, System Theory and Design, and Computer Networks and Communications.
• A4: ACM. Proc. Symposium on Problems in the Optimization of Data Communications Systems (Pine Mr., Ga., Oct. 1969). These papers provide a summary of ideas on computer data communications and networks as of 1969. The session titles are: Advanced Networks; Advances in Data Communications Technology; Preprocessors for Data Communications; Legal, Political, and Privacy Considerations; Graphic Displays and Terminals; Systems Optimization; Human Factors; and Software Implications.
• A5: ACM. Proc. 2nd Symposium on Operating Systems Principles. (Princeton Univ., Oct. 1969). These papers provide, collectively, a summary of ideas through the late 1960s. The session titles include : General Principles of Operating Systems Design; Virtual Memory Implementation; Process Management and Communications; Systems and Techniques; and Instrumentation and Measurement.
• A6: ACM. Record of the Project MAC Conf. on Concurrent Systems and Parallel Computation (Wood's Hole, Mass., June 1970). These papers deal with various aspects of parallel computation, such as Petri Net theory, program schemata, and speed-independent computation. A complete bibliography of pertinent literature is included.
• A7: ACM. Proc. Symposium on System Performance Evaluation (Harvard Univ., Cambridge, Mass., April 1971). These papers deal with various aspects of the performance evaluation problem. The session titles are: Instrumentation, Queueing Theoretic Models, Simulation Models, Measurement and Performance Evaluation, and Mathematical Models.
• A8: ALEXANDER, M. T. "Time sharing supervisor programs (notes)." Univ. Michigan Computer Center, May 1969. A comparison of four systems: the Michigan Time Sharing System (MTS), MULTICS, CP/ 67, and TSS/360.
• A9: B. Arden , D. Boettner, Measurement and performance of a multiprogramming system, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961101]
• B1: BELADY, L. A. "A study of replacement algorithms for virtual storage computers." IBM Systems J . 5, 2 (1966), 78-101. A detailed empirical study covering properties of program behavior manifested through demand paging algorithms. Various algorithms are compared for different memory and page sizes. An optimal algorithm, MIN, is proposed.
• B2: A. Bensoussan , C. T. Clingen , R. C. Daley, The multics virtual memory, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961069]
• B3: A. J. Bernstein , J. C. Sharp, A policy-driven scheduler for a time-sharing system, Communications of the ACM, v.14 n.2, p.74-78, Feb. 1971 [doi>10.1145/362515.362520]
• B4: BRINCH HANSEN, P. (ED.). RC-4000 software multiprogramming system. A/S Regnecentralen, Falkoner Alle 1, Copenhagen F, Denmark, April 1969. The description of the RC-4000 system: its philosophy, organization, and characteristics.
• B5: Per Brinch Hansen, The nucleus of a multiprogramming system, Communications of the ACM, v.13 n.4, p.238-241, April 1970 [doi>10.1145/362258.362278]
• B6: Jeffrey Buzen, Analysis of system bottlenecks using a queueing network model, Proceedings of the SIGOPS workshop on System performance evaluation, p.82-103, January 1971 [doi>10.1145/800024.808355]
• C1: E. G. Coffman , M. Elphick , A. Shoshani, System Deadlocks, ACM Computing Surveys (CSUR), v.3 n.2, p.67-78, June 1971 [doi>10.1145/356586.356588]
• C2: COFFFMAN, E. G., JR.; AND L. KLEINROCK. "Computer scheduling methods and their countermeasures." In Proe. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N.J., 11-21. A review of the basic time-sharing scheduling models and results, and of ways to gain high priority for service.
• C3: CORBATO, F .J . "PL/I as a tool for systems programming." Datamation 15, 5 (May 1969), 68-76. Argues the case for a high-level systems programming language, and recounts the MUL- TICS experience with PL/I.
• C4: CORBATo, F. J.; M. MERWIN-DAGGET; AND R. C. DALEY. "An experimental time sharing system." In Proc. AFIPS 1962 SJCC, Vol. 21, Spartan Books, New York, 335-344. Also in {R2}. Overview of the CTSS (Compatible Time Sharing System) at MIT, including the proposal for the multilevel feedback queue.
• C5: CORBATO, F. J.; AND V. A. VYSSOTSKY. "Introduction and overview of the MULTICS system." In Proc. AFIPS 1965 FJCC, Vol. 27, Pt. 1, Spartan Books, New York, 185-196. Also in {R2}. A description of the hardware and software facilities for the MULTICS (MULTiplexed Information and Computing Service) system at MIT.
• C6: CREECtt, B.A. "Implementation of operating systems." In IEEE 1970 Internatl. Convention Digest, IEEE Publ. 70-C-15, 118-119. Stresses the importance of a programming language for systems programming, and reports experience with the Burroughs B6500.
• C7: CRITCHLOW, A. J. "Generalized multiprogramming and multiprocessing systems." In Proc. AFIPS 1963 FJCC, Vol. 24, Spartan Books, New York, 107-126. A review tracing the evolution of multiprogramming and multiprocessing techniques and concepts through the early 1960s.
• C8: CRISMAN, P. A. (ED.). The compatible time sharing system: a programmer's guide. MIT Press, Cambridge, Mass., 1965. The complete description and specification of CTSS.
• D1: Robert C. Daley , Jack B. Dennis, Virtual memory, processes, and sharing in MULTICS, Communications of the ACM, v.11 n.5, p.306-312, May 1968 [doi>10.1145/363095.363139]
• D2: DALEY, R. C.; AND P. G. NEUMANN. "A general-purpose file system for secondary storage." In Proc. AFIPS 1965 FJCC, Vol. 27, Pt. 1, Spartan Books, New York, 213-229. Describes a file directory hierarchy structure, its use and conventions, and implementation problems.
• D3: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• D4: DENNING, P .J . "Thrashing: its causes and prevention." In Proc. AFIPS 1968 FJCC, Vol. 33, Pt. 1, AFIPS Press, Montvale, N.J., 915-922. A definition of, and explanation for, thrashing (performance collapse due to overcommitment of main memory) is offered, using the working set model {D3} as a conceptual aid. Some ways of preventing thrashing are discussed.
• D5: DENNING, P. J. "Equipment configuration in balanced computer systems." IEEE Trans. Computers C-18, 11 (Nov. 1969), 1008-1012. Some aspects of designing systems with understandable behavior are defined and applied to the equipment configuration problem.
• D6: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• D7: Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
• D8: Jack B. Dennis, A position paper on computing and communications, Communications of the ACM, v.11 n.5, p.370-377, May 1968 [doi>10.1145/363095.363147]
• D9: DENNIS, J. B. "Programming generality, parallelism, and computer architecture." In Proc. IFIP Cong. 1968, Vol. 1, North-Holland Publ. Co., Amsterdam, 484-492. (Also in MIT Project MAC Computation Structures Group Memo No. 32.) Defines "programming generality"--the ability to construct programs from collections of modules whose internal operations are unknown-and explores its consequences in system design.
• D10: DENNIS, J.B. "Future trends in time sharing systems." MIT Project MAC Computation Structures Group Memo No. 36-1, June 1969. Classifies time-sharing systems and emphasizes the importance of programming generality in achieving the "information utility" and in solving the "software problem."
• D11: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• D12: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• D13: DIJKSTRA, E.W. "Cooperating sequential processes." In Programming languages, F. Genuys (Ed.), Academic Press, New York, 1968, 43-112. The first study of parallel processes and concurrent programming, including a well-illustrated and complete development of the minimum requirements on the coordination and synchronization control primitives.
• D14: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• F1: E. Fuchs , P. E. Jackson, Estimates of distributions of random variables for certain computer communications traffic models, Communications of the ACM, v.13 n.12, p.752-757, Dec. 1970 [doi>10.1145/362814.362830]
• G1: R. Stockton Gaines, An operating system based on the concept of a supervisory computer, Proceedings of the third ACM symposium on Operating systems principles, p.17, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806494]
• G2: GAVER, D .P . "Statistical methods for improving simulation efficiency." Carnegie-Mellon Univ., Pittsburgh, Pa., Management Science Research Group Report No. 169, Aug. 1969. Discusses a number of methods for shortening the computation time of simulations by improving the rate of convergence.
• G3: Robert M. Graham, Protection in an information processing utility, Communications of the ACM, v.11 n.5, p.365-369, May 1968 [doi>10.1145/363095.363146]
• G4: GRAHAM, G. S. "Protection structures in operating systems." Master of Science Thesis, Univ. Toronto, Toronto, Ont., Canada, Aug. 1971. A detailed investigation of Lampson's recta-theory {L2} and its system implications, together with its application to Project SUE at the University of Toronto.
• H1: A. N. Habermann, Prevention of system deadlocks, Communications of the ACM, v.12 n.7, p.373-ff., July 1969 [doi>10.1145/363156.363160]
• H2: HAVENDER, J. W. "Avoiding deadlock in multitasking systems." IBM Systems J. 7, 2 (1968), 74 84. Treats some of the deadlock problems encountered in OS/360, and proposes the "ordered resource usage" method of preventing deadlock.
• H3: Lance J. Hoffman, Computers and Privacy: A Survey, ACM Computing Surveys (CSUR), v.1 n.2, p.85-103, June 1969 [doi>10.1145/356546.356548]
• H4: Richard Craig Holt, On deadlock in computer systems, 1971
• H5: HORNING, J. J.; AND B. RANDELL. "Structuring complex processes." IBM Thomas J. Watson Research Center Report RC-2459, May 1969. A formal, state-machine-oriented nlodel for the definition, control, and composition of processes.
• I1: IBM. "Operating System 360 concepts and facilities." In Programming Systems and Languages {R2}, 598-646. Excerpts from IBM documentation on the structure and operation of OS/360.
• I2: IEEE. "Proc. 1969 Computer Group Conference." IEEE Trans. Computers C-18, 11 (Nov. 1969). Of interest is the session on "Computer system models and analysis."
• I3: Edgar T. Irons, Experience with an extensible language, Communications of the ACM, v.13 n.1, p.31-40, Jan. 1970 [doi>10.1145/361953.361966]
• J1: John B. Johnston, The contour model of block structured processes, ACM SIGPLAN Notices, v.6 n.2, February 1971 [doi>10.1145/1115880.1115883]
• K1: KILBURN, T.; D. B. G. EDWARDS; M. J. LANI- GAN; AND F. H. SUMNER. "One-level storage system." IRE Trans. EC-11 (April 1962), 223- 238. The first detailed description of the paging mechanism on the Atlas Computer, including the loop-detecting "learning" algorithm for page replacement.
• K2: Stephen R. Kimbleton , Charles G. Moore, A probabilistic framework for system performance evaluation, Proceedings of the SIGOPS workshop on System performance evaluation, p.337-361, January 1971 [doi>10.1145/800024.808366]
• K3: KLEINROCK, L. "A continuum of time sharing scheduling algorithms." In Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., 453-458. A piecewise linear priority function is associated with each job, and the scheduler runs the job or jobs of highest priority. A job enters the system with zero priority, it gains priority while waiting according to a "waiting slope," and i t gains priority while running according to a "serving slope." A two-dimensional plane displays the possible combinations of the two slopes and the corresponding scheduling algorithms.
• L1: LAMPSON, B.W. "Dynamic protection structures." In Proc. AFIPS 1969 FJCC, Vol. 35, AFIPS Press, Montvale, N.J., 27-38. An exposition of the programming implications and power of a system of protection based on the capability idea {D11} with hardware similar to that discussed in {W6}.
• L2: LAMPSON, B.W. "Protection." In Proc. 5th Annual Princeton Conf., Princeton Univ., March 1971. A generalized model for protection systems, incorporating an "access matrix" and nonforgeable "domain identifiers," is proposed. Existing protection systems are shown to be special cases. Properties of "correct" protection systems are treated.
• L3: LIPTAV, J. S. "Structural aspects of the System/360 model 85: the cache." IBM Systems J . 7, 1 (1968), 15 21. A description of the organization and behavior of the cache store on the IBM 360/85.
• M1: M. H. MacDougall, Computer System Simulation: An Introduction, ACM Computing Surveys (CSUR), v.2 n.3, p.191-209, Sept. 1970 [doi>10.1145/356571.356574]
• M2: MATTSON, R. L.; J. GECSEI; D. R. SLUTZ ; AND I. L. TRAIGER. "Evaluation techniques for storage hierarchies." IBM Systems J . 9, 2 (1970), 78-117. The concept of "stack algorithm" as a model for paging algorithms is introduced and its properties studied. Efficient algorithms are derived for determining the "success funct i o n " versus memory size for a given paging algorithm. Priority, optimal, and random-replacement algorithms are shown to be stack algorithms.
• M3: John McCarthy , Fernando J. Corbató , Marjorie M. Daggett, The linking segment subprogram language and linking loader, Communications of the ACM, v.6 n.7, p.391, July 1963 [doi>10.1145/366663.366702]
• M4: J. M. McKinney, A Survey of Analytical Time-Sharing Models, ACM Computing Surveys (CSUR), v.1 n.2, p.105-116, June 1969 [doi>10.1145/356546.356549]
• N1: Norman R. Nielsen, The allocation of computer resources—is pricing the answer?, Communications of the ACM, v.13 n.8, p.467-474, Aug. 1970 [doi>10.1145/362705.362707]
• P1: PARKHILL, D. The challenge of the computer utility. Addison-Wesley Publ. Co., Reading, Mass., 1966. A good description of the issues, philosophy, methods, hopes, and fears t h a t existed during the early 1960s, when enthusiasm for the computer utility ran high.
• P2: P. C. Poole , W. M. Waite, Machine independent software, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961063]
• R1: B. Randell , C. J. Kuehner, Dynamic storage allocation systems, Communications of the ACM, v.11 n.5, p.297-306, May 1968 [doi>10.1145/363095.363138]
• R2: ROSEN, S. (ED.). Programming systems and languages. McGraw-Hill, New York, 1967. A collection of "classic" papers on programming language design, definition, assemblers, compilers, and operating systems to 1966.
• R3: Saul Rosen, Electronic Computers: A Historical Survey, ACM Computing Surveys (CSUR), v.1 n.1, p.7-36, March 1969 [doi>10.1145/356540.356543]
• R4: Robert F. Rosin, Supervisory and Monitor Systems, ACM Computing Surveys (CSUR), v.1 n.1, p.37-54, March 1969 [doi>10.1145/356540.356544]
• S1: J. H. Saltzer, TRAFFIC CONTROL IN A MULTIPLEXED COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1966
• S2: Jean E. Sammet, Programming Languages: History and Fundamentals, Prentice-Hall, Inc., Upper Saddle River, NJ, 1969
• S3: D. Sayre, Is automatic “folding” of programs efficient enough to displace manual?, Communications of the ACM, v.12 n.12, p.656-660, Dec. 1969 [doi>10.1145/363626.363629]
• S4: Michael D. Schroeder, Performance of the GE-645 associative memory while Multics is in operation, Proceedings of the SIGOPS workshop on System performance evaluation, p.227-245, January 1971 [doi>10.1145/800024.808361]
• S5: SELWYN, L.L. "Computer resource accounting in a time-sharing environment." In Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., 119-129. A description of the management, accounting, and pricing systems of CTSS-like systems. Should be read in conjunction with {N1, $7,w8}.
• S6: William F. Sharpe, The Economics of Computers, Columbia University Press, New York, NY, 1972
• S7: I. E. Sutherland, A futures market in computer time, Communications of the ACM, v.11 n.6, p.449-451, June 1968 [doi>10.1145/363347.363396]
• T1: TRIMBLE, G., JR. "A time-sharing bibliography." Computing Reviews 9, 5 (May 1968), 291-301.
• V1: E. C. Van Horn, COMPUTER DESIGN FOR ASYNCHRONOUSLY REPRODUCIBLE MULTIPROCESSING, Massachusetts Institute of Technology, Cambridge, MA, 1966
• W1: W. M. Waite, The mobile programming system: STAGE2, Communications of the ACM, v.13 n.7, p.415-421, July 1970 [doi>10.1145/362686.362691]
• W2: Wegner, P. (Ed.). Introduction to systems programming. Academic Press, New York, 1964. A collection of some "classic" papers on operating systems principles and design during the early 1960s.
• W3: Peter. Wegner, Programming Languages, Information Structures, and Machine Organization., McGraw Hill Text, 1968
• W4: WILKES, M. V. "Slave memories and dynamic storage allocation." IEEE Trans. Computers C-14 (1965), 270-271. Proposes an automatic multilevel memory system, the predecessor of the "cache store" {L3}.
• W5: Maurice V. Wilkes, Computers Then and Now, Journal of the ACM (JACM), v.15 n.1, p.1-7, Jan. 1968 [doi>10.1145/321439.321440]
• W6: M. V. Wilkes, Time Sharing Computer Systems, Elsevier Science Inc., New York, NY, 1975
• W7: WILKES, M.V. "A model for core space allocation in a time sharing system." In Proc. AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N.J., 265-271. Uses experience with time-sharing systems to develop a minimal relationship between processor and core allocation policies.
• W8: WILKES, M. V.; AND D. F. HARTLEY. "The management system--a new species of software?" Datamation 15, 9 (Sept. 1969), 73-75. Outlines the motivation and requirements for a management system as illustrated by the Cambridge University Multiple Access System. Should be read in conjunction with {N1, S5, S7}.
• W9: M. V. Wilkes, Automatic load adjustment in time-sharing systems, Proceedings of the SIGOPS workshop on System performance evaluation, p.308-320, January 1971 [doi>10.1145/800024.808364]
• W10: William A. Wulf, Performance monitors for multi-programming systems, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961105]

INDEX TERMS

Primary Classification:
  A. General Literature