A Generalized Multi-Entrance Time-Sharing Priority Queue

ABSTRACT

A generalized multi-entrance and multipriority M/G/1 time-sharing system is dealt with. The system maintains many separate queues, each identified by two integers, the priority level and the entry level The arrival process of users is a homogenous Poisson process, while service requirements are identically distributed and have a finite second moment. Upon arrival a user joins one of the levels, through the entry queue of this level. In the (n, k)-th queue, where n is the priority level and k is the entry level, a user is eligible to a (finite or infinite) quantum of service. If the service requirements of the user are satisfied during the quantum, the user departs, and otherwise he is trans- ferred to the end of the (n + 1, k)-th queue for additional service. When a quantum of service is completed, the highest priority nonempty level is chosen to be served next; within this level the queues are scanned according to the priority of their entry level, and the user at the head of the highest priority nonempty queue is chosen to be served. In such a priority discipline, preferred users always get an improved service, though the service of all users is degraded in proportion to their service requirements. Expected flow times and expected number of waiting users are derived and then specialized to the head-of-the-line M/G/1 priority discipline (in which quanta have infinite length and service is uninterrupted) and to the FB_n time-sharing system. Finally, the generalized multientrance and multipriority time-sharing discipline is (numerically) compared with several other time-sharing systems.

REFERENCES

• 1: Igal Adiri, A Dynamic Time-Sharing Priority Queue, Journal of the ACM (JACM), v.18 n.4, p.603-610, Oct. 1971 [doi>10.1145/321662.321675]
• 2: Igal Adiri, A Note on Some Mathematical Models of Time-Sharing Systems, Journal of the ACM (JACM), v.18 n.4, p.611-615, Oct. 1971 [doi>10.1145/321662.321676]
• 3: kDIRI, I , AND AW-ITZHAK, B. A time-sharing queue. Manage. Scz. 15, 11 (1969), 639-657.
• 4: kDIRI, I., AND AVI-ITZHAK, B. A time-sharing model with many queues. Oper. Res 17, 6 (1969),
• 5: BABAD, J. M Price scheduling in a time-sharing queueing system Tech. Rep. 73-178, Dep. of Comput. Sci , Cornell U., Ithaca, N.Y., 1973.
• 6: Edward G. Coffman , Leonard Kleinrock, Feedback Queueing Models for Time-Shared Systems, Journal of the ACM (JACM), v.15 n.4, p.549-576, Oct. 1968 [doi>10.1145/321479.321483]
• 7: CONWAY, R. W, MAXWELL, W. L., AND MILLER, L.W. Theory of Scheduling. Addison-Wesley, Reading, Mass., 1967.
• 8: KLmNROCK, L. Analysis of time-shared processor. Naval Res. Log~st. Quart. 2, 1 (1964), 59-73.
• 9: Leonard Kleinrock, Time-shared Systems: a theoretical treatment, Journal of the ACM (JACM), v.14 n.2, p.242-261, April 1967 [doi>10.1145/321386.321388]
• 10: L. Kleinrock , R. R. Muntz, Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System, Journal of the ACM (JACM), v.19 n.3, p.464-482, July 1972 [doi>10.1145/321707.321717]
• 11: 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]
• 12: A. L. Scherr, AN ANALYSIS OF TIME-SHARED COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1965
• 13: SCHRAGE, L.E. The queue M/G/1 with feedback to lower priority queues. Manage, Sci. 13 (1967), 466-474.
• 14: Jack E. Shemer, Some Mathematical Considerations of Time-Sharing Scheduling Algorithms, Journal of the ACM (JACM), v.14 n.2, p.262-272, April 1967 [doi>10.1145/321386.321389]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Measurement, Performance, Theory