An execution/sleep scheduling policy for serving an additional job in priority queueing systems

ABSTRACT

In a priority-based computer system, besides the regular jobs, an additional job (refereed to as job A) is invoked infrequently but requires a significant amount of CPU time. To avoid CPU hogging, job A receives (up to) a fixed amount of CPU time whenever it is served. When the time expires, job A immediately relinquishes the CPU and puts itself to sleep for a period of time. By doing so, jobs with low priority may be processed in a timely manner. When the sleep time is over, job A is awakened and waits to resume service according to its priority. Then, the whole process is repeated until job A service is completed. In this paper, such an execution/sleep (ES) scheduling policy is analyzed for serving job A in a nonpreemptive priority queuing system. The Laplace Transforms are derived for: (i) the conditional response time of job A and (ii) the response time for jobs with priorities higher and lower than job A. This work is motivated by the ES policy in a switching system in which job A is invoked in response to the failure of signaling links. The proposed model is applicable to other real-time computer systems, and the modeling techniques can be applied or generalized to analyzing other scheduling policies in which timers are involved.

REFERENCES

• 1: ~COHEN, J.W. On up- and down-crossings. J At?pL Prob. 14 (1977), 405 410.
• 2: B. T. Doshi, Queueing systems with vacations—a survey, Queueing Systems: Theory and Applications, v.1 n.1, p.29-66, 1986 [doi>10.1007/BF01149327]
• 3: ~EISENBERG, M. Queues with periodic service and changeover time. Oper. Res. 20 (1972), ~440-451.
• 4: A. Federgruen , L. Green, Queueing systems with service interruptions, Operations Research, v.34 n.5, p.752-768, Sept.-Oct. 1986 [doi>10.1287/opre.34.5.752]
• 5: ~FEDERGRUEN, A., AND GREEN, L. Queueing systems with service interruptions II. Nat,aiRes. ~Logistics 35 (1988), 345 358.
• 6: ~FREDERICKS, A. A., FARRELI~, B. L., AND DEMA10, D. F. Approximate analysis of a ~generalized clocked schedule. AT&T Tech. J. 64 (1985), 597-615.
• 7: ~FUHRMANN, S. W., AND COOPER, R.B. Stochastic decompositions in the M/G/1 queue with ~generalized vacations. ()per Res. 33 (1985), 1117 1129.
• 8: ~HE't MAN, D.P. A priority queueing system with server interference. SlAM J. Appl. Math. 17 ~(1969), 74-82.
• 9: ~HEYMAN, D. P., AND SOBEL, M.J. Stochasttc Models in Operattotzs Research. Vol. 1, Stochastzt ~Processes and Operatt.ng Characte;isttcs. McGraw-Hill, New York, 1982.
• 10: ~KELt.^, O., AND YECH~^LI, U. Priorities in M/G/1 queue with server vacations. Nat,al Res. ~Logistzcs 35 (1988), 23-34.
• 11: ~KLE~NROCK, L. Qt~cttetng Systems. Vol. 2, CornputerApphcatioHs. John Wiley & Sons, New ~York, 1976.
• 12: ~LEUNG, K. K. Cyclic-service systems with probabilistically-limited service. IEEE J. Select. ~Areas Commun. 9 (1991), 185-193.
• 13: Hanoch Levy , Leonard Kleinrock, A queue with starter and a queue with vacations: delay analysis by decomposition, Operations Research, v.34 n.3, p.426-436, May-June 1986 [doi>10.1287/opre.34.3.426]
• 14: ~LEVY, Y., AND YECHIAH, U. Utilization of idle time in an M/G/1 queueing system. ~Manage. Sci, 22 (1975), 202-211.
• 15: ~OTT, T.J. On the M/G/I queue with additional inputs. J. Appl. Prob. 21 (1984), 129-142.
• 16: ~OfT, T.J. The single-server queue with independent GI/G and M/G input streams. Adv. ~Appl. Prob. 19 (1987), 266-286.
• 17: ~SAraN, I. Equilibrium behavior of a stochastic system with secondary input. J. Appl. Prob. 8 ~(1971), 252-260.
• 18: ~SAHIN, I., AND BHAT, U.N. A stochastic system with scheduled secondary inputs. Oper Res. ~16 (1971), 436-446.
• 19: ~S^NDHU, D., AND POSNER, M. J.M. A priority M/G/1 queue with application to voice/data ~communication. Europ. J. Oper. Res. 40 (1989), 99-108.
• 20: ~SCH^SSBEROER, R. A broad analysis of single server priority queues with two independent ~input streams, One of them Poisson. Adv. Appl. Prob. 6 (1974), 666-688.
• 21: Bhaskar Sengupta, A queue with service interruptions in an alternating random environment, Operations Research, v.38 n.2, p.308-318, Mar–Apr. 1990 [doi>10.1287/opre.38.2.308]
• 22: ~SH^NTHIKUMAR, J. G. Analyses of priority queues with server control. OPSEARCH 27 ~(1984), 183-192.
• 23: J. George Shanthikumar, On stochastic decomposition in M/G/1 type queues with generalized server vacations, Operations Research, v.36 n.4, p.566-569, July-August 1988 [doi>10.1287/opre.36.4.566]
• 24: ~SH^NTmKUMAR, J.G. Level crossing analysis of priority queues and a conservation identity ~for vacation models. Naval Res. Logistics 36 (1989), 797-806.
• 25: ~TAI4ACS, L. Introduction to the Theory of Queues. Oxford Univ. Press, New York, 1962.
• 26: ~WOLFF, R.W. Poisson arrivals see time averages. Oper. Res. 30 (1982), 223-23t.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Performance, Theory

Keywords:
performance evaluation, priority queues, response times, server vacation models, time-limited service, waiting times