Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper describes the content of a one-term advanced undergraduate course being developed in the Department of Electrical Engineering at Princeton University. As the title suggests, the course is approached through theory and models, not through case studies. My experience is not only that students find the more traditional case-study approach intellectually unsatisfying and often confused or confusing, but they find that a little formalism helps them to see precisely what is the intellectual content of a discussion. My goal is not to teach them systems programming; it is instead to help them develop mathematical modeling techniques which prove useful in understanding and evaluating systems and their problems. Using this approach, I have successfully taught to juniors material. I have often seen reserved for graduate students.

REFERENCES

• 1: ACM. Proceedings of Symposium on Storage Allocation. CACM 4, 10 (Oct 1961).These papers argue the cases and techniques for static and dynamic storage allocation. They provide a complete picture of the state of considered thought on storage allocation as of 1961.
• 2: ACM. Proceedings of Symposium on Operating Systems Principles. (Gatlinburg, Tenn., Oct 1967). Some of the papers appear in CACM 11, 5 (May 1968).These papers provide collectively a summary of the ideas through the middle 1960's. The session titles are: virtual memory, memory management; extended core memory systems; philosophies of process control; system theory and design; computer communications and networks.
• 3: ACM. Proceedings of Symposium on Data Communications. (Pine Mt., Georgia, Oct. 1969).These papers provide a summary of the 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; software implications.
• 4: ACM. Proceedings of Second Symposium on Operating Systems Principles. (Princeton University, Oct 1969).These papers provide collectively a summary of ideas through the late 1960's. The session titles are: general principles of operating system design; virtual memory implementation; process management and communication; systems and techniques; instrumentation and measurement.
• 5: ACM. Proceedings of the Project MAC Conference on Concurrent Systems and Parallel Computation. (Wood's Hole, Mass., June 1970). To appear.These papers cover various aspects of parallel computation, such as Petri Net theory, program schemata, and speed-independent asynchronous circuits. A complete bibliography of relevant literature is included.
• 6: Alexander, M.T. Time Sharing Supervisor Programs (Notes). Univ. of Michigan Computing Center (May 1969).A comparison of four systems: the Michigan MTS, Multics, CP/67 and TSS/360.
• 7: 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]
• 8: Belady, L.A. A Study of Replacement Algorithms for virtual Storage Computers. IBM Sys. J. 5, 2 (1966), 78-101.A detailed empirical study covering several aspects of program behavior besides those relating to paging algorithms.
• 9: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 10: Coffman, E.G. Jr., and Klein rock, L. Computer Scheduling Methods and Their Counter measures. AFIPS 1968 SJCC Proc., 11-21.A review of the basic time sharing scheduling models and results, and of ways to gain high priority for service.
• 11: Corbato, F.J. PL/I as a Tool for Systems Programming. MIT Project Mac Report MAC-M-378 (July 1968).Argues the case for a high-level operating systems programming language and gives Multics experience with PL/I.
• 12: Corbato, F.J., Dagget, M.M., and Daley, R.C. An Experimental Time Sharing System. AFIPS 1962 FJCC Proc., 335. (Also in R3).Overview of CTSS (Compatible Time Sharing System) at MIT, including the proposal for the multilevel feedback queue.
• 13: Corbato, F.J., and Vyssotsky, V.A. Introduction and Overview of the Multics System. AFIPS 1965 FJCC Proc., 306. (Also in R3).A description of the hardware and software facilities for the Multics system at MIT.
• 14: Creech, B.A. Implementation of Operating Systems. Digest 1970 IEEE International Convention, IEEE Publ. 70 C 15, 118-119. Stresses the importance of a programming language for systems programming, and reports experience with Burroughs B6500 system.
• 15: Critchlow, A.J. Generalized Multiprogramming and Multiprocessing Systems. AFIPS 1963FJCC Proc., 107-126.A review tracing the evolution of multiprogramming and multiprocessing concepts through the early 1960's.
• 16: Crisman, P.A. (ed.) The Compatible Time Sharing System: A Programmer's Guide. MIT Press (1965). The complete description and specification of CTSS.
• 17: 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]
• 18: Daley, R.C., and Neumann, P.G A General Purpose File System for Secondary Storage. AFIPS 1965 FJCC Proc., 213. Describes a file directory hierarchy structure, its use and conventions, and implementation problems.
• 19: 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]
• 20: Denning, P.J. Equipment Configuration in Balanced Computer Systems. IEEE Trans. C-18, (Nov 1969), 1008-1012. (Also Il).Some aspects of designing systems with understandable behavior are defined and applied to the equipment configuration problem.
• 21: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 22: 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]
• 23: 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]
• 24: Dennis, J.B. Programming Generality, Parallelism, and Computer Architecture. IFIPS Cong. Proc. (1968); MIT Project MAC Computation Structures Group Memo No. 32 (Aug 1968). Defines "programming generality" and explores its consequences in system design.
• 25: Dennis, J.B. Future Trends in Time Sharing Systems. MIT 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."
• 26: 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]
• 27: 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]
• 28: Dijkstra, E.W. Cooperating Sequential Processes. Programming Languages. (F. Genuys, ed.) Academic Press (1968), 43-112.The first study of parallel processes, including a well illustrated and complete development of the minimum requirements on the coordination and synchronization primitives.
• 29: 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]
• 30: Gaver, D.P. Statistical Methods for Improving Simulation Efficiency. Carnegie-Mellon Univ., Management Sci Res. Grp Rpt No. 169 (Aug 1969).Discusses a number of methods for shortening the computation time of simulation.
• 31: 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]
• 32: Habermann, A.N. On the Harmonious. Cooperation of Abstract Machines. Ph.D. Dissertation, Technische ogeschool Eindhoven, Netherlands, Dept. of Mathematics (1967).A formal model for cooperating parallel processes using finite state machines; includes the "banker's algorithm" for preventing system deadlock.
• 33: 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]
• 34: 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]
• 35: 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]
• 36: Horning, J.J., and Randell, B. Structuring Complex Processes. IBM T.J. Watson Research Center Report RC2459 (May 1969).A formal model for the definition, control, and composition of processes.
• 37: IEEE. Proceedings of 1969 Computer Group Conference. IEEE Trans. C-18, 11, (Nov 1969).Of interest is the session "computer system models and analysis."
• 38: 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]
• 39: Kilburn, T., Edwards, D.B.G., Lanigan, M.J., and Sumner, F.H. One-Level Storage System. IRE Trans. EC-ll, Apr 1962), 223.The first detailed description of the paging mechanism on the Atlas computer system, including the loop-detecting "learning" paging algorithm.
• 40: Kleinrock, L. A Continuum of Time Sharing Scheduling Algorithms. AFIPS 1970 SJCC Proc.A large class of time sharing schedulers is defined in terms of piecewise linear priority time functions.
• 41: Lampson,B.W. Dynamic Protection Structures. AFIPS 1969 FJCC Proc., 27-38.An exposition of the programming implications and power of a "capability" system of protection.
• 42: Liptay, J.S. The Cache. IBM Sys. J. 7, 1 (1968).A description of the cache store on the IBM 360/85.
• 43: 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]
• 44: 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]
• 45: Session "Resource Sharing in Computer Networks" in AFIPS 1970 SJCC Proc. 543-598.
• 46: Parkhill, D. The Challenge of the Computer Utility. Addison-Wesley (1966).A good description of the issues, philosophy, methods, hopes, and fears extant during the early 1960's, when enthusiasm for the computer utility ran high.
• 47: 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]
• 48: B. Randell, A note on storage fragmentation and program segmentation, Communications of the ACM, v.12 n.7, p.365-ff., July 1969 [doi>10.1145/363156.363158]
• 49: 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]
• 50: Rosen, S. (ed.) Programming Systems and Languages. McGraw-Hill (1967).A collection of "classic" papers in programming language design, definition, assemblers, compilers, and operating systems to 1966.
• 51: 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]
• 52: 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]
• 53: Robert F. Rosin, Contemporary Concepts of Microprogramming and Emulation, ACM Computing Surveys (CSUR), v.1 n.4, p.197-212, Dec. 1969 [doi>10.1145/356556.356559]
• 54: J. H. Saltzer, TRAFFIC CONTROL IN A MULTIPLEXED COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1966
• 55: Sammet 7 J.E. Programming Languages. Prentice-Hall (1969).Encyclopedic coverage, comparing and contrasting over 100 programming languages.
• 56: 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]
• 57: Selwyn, L.L. Computer Resource Accounting in a Time Sharing Environment. AFIPS 1970 SJCC Proc., 119-129.A description of the management, accounting, and pricing systems of CTSS-Iike systems. Should be read in conjunction with W9, S6.
• 58: William F. Sharpe, The Economics of Computers, Columbia University Press, New York, NY, 1972
• 59: 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]
• 60: Trimble, George. Time Sharing Bibliography. Computing Reviews 9, (May 1968).
• 61: E. C. Van Horn, COMPUTER DESIGN FOR ASYNCHRONOUSLY REPRODUCIBLE MULTIPROCESSING, Massachusetts Institute of Technology, Cambridge, MA, 1966
• 62: 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]
• 63: Richard W Watson, Timesharing system design concepts (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1970
• 64: Wegner, P. (ed.) Introduction to Systems Programming. Academic Press (1964).A collection of some "class-c" papers on operating system inciples during the early 1960's.
• 65: Peter. Wegner, Programming Languages, Information Structures, and Machine Organization., McGraw Hill Text, 1968
• 66: Wilkes, M.V. Slave Memories and Dynamic Storage Allocation. IEEE Trans. EC-14, (1965), 270-271.Proposes an automatic multilevel memory, the predecessor of the "cache store" {L2}.
• 67: 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]
• 68: M. V. Wilkes, Time Sharing Computer Systems, Elsevier Science Inc., New York, NY, 1975
• 69: Wilkes, M.V. A Model for Core Space Allocation in a Time Sharing System. AFIPS 1969 SJCC Proc., 265-271.Uses experience with time sharing systems to develop a minimal relationship between processor and core allocation policies.
• 70: M. V. Wilkes, The Growth of Interest in Microprogramming: A Literature Survey, ACM Computing Surveys (CSUR), v.1 n.3, p.139-145, Sept. 1969 [doi>10.1145/356551.356553]
• 71: Wilkes, M.V., and Hartley, D.F. The Management System - A New Species of Software? Datamation (Sep 1969), 73-75.Outlines the motivation and requirements for a management system, and illustrates with the Cambridge University Multiple-Access System. Should be read in conjunction with S4, S6.
• 72: 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:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

General Terms:
Design, Theory