Performance analysis of FCFS and improved FCFS scheduling algorithms for dynamic real-time computer systems

摘要

A study is made of the performance of FCFS (first-come, first-served) and improved FCFS scheduling algorithms for dynamic real-time computer systems in which tasks arrive as a random process and each task has a laxity specifying the maximum time a task can wait for the service. The general solution for M/M/1 systems in which the FCFS or an improved FCFS scheduling algorithm is used is obtained. In particular, explicit expressions for the unfinished work distribution, the task loss ratio, and the CPU utilization for M/M/1+M systems are derived. The last M in M/M/1+M means that the task laxity is exponentially distributed. The steady-state performance of those systems depends not only on the offered load rho (as in the non-real-time arena), but also on the normalized mean laxity, which is equal to the mean laxity divided by the mean service time. An analysis also shows that using the improved FCFS scheduling algorithm results in significant improvement over using the original FCFS algorithm. In many circumstances, the improved FCFS has almost identical or very similar performance to that of the minimum-laxity-first (MLF) algorithm, which has been shown to be optimal. The advantage of the improved FCFS algorithm is that it takes O(1) time while the MLF algorithm needs O(log n) time.