Fairness in processor scheduling in time sharing systems

ABSTRACT

Loosely, fairness is the assurance of granting each request, from a set of requests, within a predetermined bounded time even though the request scheduling primitives are unfair or random. The fairness property has been studied, in solutions to the mutual exclusion problem, from theoretical point of view. Many fair solutions to the mutual exclusion problem have been proposed in recent years. This paper presents one illustration to show how the concepts of fairness could be incorporated in processor scheduling in time sharing systems. First, it looks at some shortcomings associated with the round robin scheduler used in the time sharing systems, and then presents a fair version of the round robin scheduler.

REFERENCES

• 1: [1] I. Adiri and B. Avi-Itzhak, A time-sharing queue, Manag. Sci., Vol. 15(11), 1969, p. 639-657.
• 2: 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]
• 3: U. Narayan Bhat , Richard E. Nance, Busy Period Analysis of a Time-Sharing System Modeled as a Semi-Markov Process, Journal of the ACM (JACM), v.18 n.2, p.221-238, April 1971 [doi>10.1145/321637.321643]
• 4: [4] P.R. Blevins and C.V. Ramamoorthy, Aspects of dynamic adoptive operating systems, IEEE Tran. on Computer, Vol. 25(7), 1970, p. 713-725.
• 5: James E. Burns , Paul Jackson , Nancy A. Lynch , Michael J. Fischer , Gary L. Peterson, Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable, Journal of the ACM (JACM), v.29 n.1, p.183-205, Jan. 1982 [doi>10.1145/322290.322302]
• 6: E. G. Coffman, Jr., Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping, Journal of the ACM (JACM), v.15 n.3, p.341-353, July 1968 [doi>10.1145/321466.321467]
• 7: Stuart A. Friedberg , Gary L. Peterson, An efficient solution to the mutual exclusion problem using weak semaphores, Information Processing Letters, v.25 n.5, p.343-348, July 10, 1987 [doi>10.1016/0020-0190(87)90210-9]
• 8: S. Haldar , D. Subramanian, An efficient solution to the mutual exclusion problem using unfair and weak semaphore, ACM SIGOPS Operating Systems Review, v.22 n.2, p.60-66, April, 1988 [doi>10.1145/43914.43920]
• 9: [9] L. Kleinrock, Analysis of time-shared processor, Naval Res. Linguistics Quart., Vol. 2(1), (1964), p. 59-73.
• 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: [11] L. Kleinrock, Queuing Systems, Volume II: Computer Applications, Wiley, N. York, 1976.
• 12: 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]
• 13: Richard E. Nance , U. Narayan Bhat , Billy G. Claybrook, Busy Period Analysis of a Time-Sharing System: transform inversion, Journal of the ACM (JACM), v.19 n.3, p.453-463, July 1972 [doi>10.1145/321707.321716]
• 14: James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 15: [15] R.L. Rivest and V.R. Pratt, The mutual exclusion problem for unreliable processes: preliminary report, 17th Annual symposium on Foundation of Computer Science, Houston, Tex, 1976, p. 1-8.
• 16: [16] K.D. Ryder, A heuristic approach to task despatching, IBM system Journal, Vol. 9(3), 1970, p. 189-198.
• 17: 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]
• 18: Stephen Sherman , Forest Baskett, III , J. C. Browne, Trace-driven modeling and analysis of CPU scheduling in a multiprogramming system, Communications of the ACM, v.15 n.12, p.1063-1069, Dec. 1972 [doi>10.1145/361598.361626]
• 19: Stuart E. Madnick , John J. Donovan, Operating Systems, McGraw-Hill, Inc., New York, NY, 1974

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

General Terms:
Design, Measurement, Performance, Theory