Contents

1 Introduction 5 1.1 The Extensibility Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Designing For Extensibility 8 2.1 Placing Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Heuristics for Placing Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Maintaining Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Event Delivery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Experimental Implementation 20 3.1 Experimental Apparatus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Process Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Requirements for Application-level Scheduling . . . . . . . . . . . . . . . . . . . . 22 3.4 Extension Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Related Work 27 4.1 Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Interposition Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3 Metaobject protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4 Hierarchical Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Conclusions 30

Bibliography

[1] B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. Fiuczynski, D. Becker, S. Eggers, and C. Chambers. Extensibility, safety and performance in the SPIN operating system. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995.

[2] D. R. Engler. vcode: a retargetable, extensible, very fast dynamic code generation system. In Proceedings of the SIGPLAN ’96 Conference on Programming Language Design and Implementation, May 1996.

[3] D. R. Engler, S.K. Gupta, and M. F. Kaashoek. AVM: application-level virtual memory. In Proc. of the Fifth Workshop on Hot Topics in Operating Systems, May 1995.

[4] D. R. Engler, M. F. Kaashoek, and J. O’Toole Jr. Exokernel: an operating system architecture for application-specif ic resource management. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995.

[5] B. Ford and S. Susarla. Cpu inheritance scheduling. In Proc. of the Second Symposium on Operating Systems Design and Implementation, October 1996.

[6] Michael B. Jones. Interposition agents: Transparently interposing user code at the system interface. In Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles, 1993.

[7] G. Kiczales, J. des Rivieres, and D. G. Bobrow. The art of the metaobject protocol. MIT Press, 1991.

[8] B. W. Lampson. Hints for computer system design. In Proceedings of the Eighth ACM Symposium on Operating Systems Principles, pages 33–48, December 1983.

[9] R. Levin, E. Cohen, W. Corwin, F. Pollack, and W. Wulf. Policy/mechanism seperation in HYDRA. Proceedings of the Fifth ACM Symposium on Operating Systems Principles, pages 132–140, 1975.

[10] M. K. McKusick, K. Bostic, M. J. Karels, and J. S. Quarterman. The Design and Implementation of the 4.4 BSD Operating System. Addison Wesley, 1996.

[11] P. Pardyak and B. Bershad. Dynamic binding for an extensible system. In Proceedings of the Second Symposium on Operating Systems Design and Implementation, October 1996.