Abstract
A trace-driven model is used to study the effects of various schedulers and deadlock control algorithms in a general-purpose operating system. Jobs’ requests for resources are extracted from a production load and used to drive a detailed simulation program. The simulation results show that the preemptive deadlock control algorithms give consistently good performance in terms of CPU utilization. The bankers algorithm and the detection and recovery deadlock control algorithms are susceptible to “knotting” (holding of resources by a blocked process) when there is no preemption, but their performance can be improved significantly by 1) allowing a moderate amount of preemption and 2) by forcing the job scheduler to limit the number of jobs competing for resources. When “knotting” is limited by either of the above methods, non-preemptive jobs scheduling improves CPU utilization. This paper extends and develops previous work and summarizes the interaction between some characteristics of job schedulers and deadlock control algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Coffman, E. G., Elphick, M., and Shoshani, A., System deadlocks, Computing Surveys 3, 2 (June 1971), 67.
Holt, R. C., On deadlock in computer systems. Ph.D. dissertation, Department of Computer Science, Cornell University, Ithaca, N.Y., January 1971.
Shoshani, A., and Coffman, E. G. Detection and prevention of deadlocks. Fourth Annual Princeton Conf. on Information Sciences and Systems, Princeton, N. J., March 1970.
Habermann, A. N., Prevention of system deadlocks. Comm. ACM 12, 7 (July 1969), 373.
Sherman, S. W., Trace-driven modeling studies of the performance of computer systems. Ph. D. dissertation, Department of Computer Sciences, University of Texas, Austin, Texas, 1972.
Sherman, S. W. and Browne, J. C., Trace-driven modeling: Review and overview. Symposium on the Simulation of Computer Systems, Gaithersburg, Md., June 1973.
Sherman, S. W., Baskett, F., and Browne, J. C., Trace-driven modeling and analysis of CPU scheduling in a multi-programming system. Comm. ACM 15, 12 (Dec. 1972), 1063.
Sherman, S. W., Howard, J. H., and Browne, J. C., A comparison of deadlock prevention schemes using a trace-driven model. Sixth Princeton Conf. on Information Sciences and Systems, Princeton, N. J., March 1972, p. 604.
Sherman, S. W., Howard, J. H., and Browne, J. C., A study of response times under various deadlock algorithms and job schedulers. 1974 ACM National Conf., San Diego, Cal.
Thornton, J. E., Design of a Computer: The CDC 6600. Scott, Foresman and Co., Glenview, Ill., 1970.
Howard, J. H., A large-scale dual operating system. 1973 ACM National Conf., Atlanta, Ga., p. 242.
Johnson, D. S., A process-oriented model of resource demands in large multiprocessing computer utilities. Ph.D. dissertation, Department of Computer Sciences, The University of Texas, Austin, Texas, 1972.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1975 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Sherman, S.W., Howard, J.H., Browne, J.C. (1975). Trace Driven Studies of Deadlock Control and Job Scheduling. In: Siefkes, D. (eds) GI-4.Jahrestagung. Lecture Notes in Computer Science, vol 26. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-40087-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-662-40087-6_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-39104-4
Online ISBN: 978-3-662-40087-6
eBook Packages: Springer Book Archive