CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

On Minimum Variance CPU-Scheduling Algorithm for Interactive Systems using Goal Programming

by Anas Jebreen Atyeeh Husain
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 135 - Number 11
Year of Publication: 2016
Authors: Anas Jebreen Atyeeh Husain
10.5120/ijca2016908550

Anas Jebreen Atyeeh Husain . On Minimum Variance CPU-Scheduling Algorithm for Interactive Systems using Goal Programming. International Journal of Computer Applications. 135, 11 ( February 2016), 51-59. DOI=10.5120/ijca2016908550

@article{ 10.5120/ijca2016908550,
author = { Anas Jebreen Atyeeh Husain },
title = { On Minimum Variance CPU-Scheduling Algorithm for Interactive Systems using Goal Programming },
journal = { International Journal of Computer Applications },
issue_date = { February 2016 },
volume = { 135 },
number = { 11 },
month = { February },
year = { 2016 },
issn = { 0975-8887 },
pages = { 51-59 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume135/number11/24097-2016908550/ },
doi = { 10.5120/ijca2016908550 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:35:33.735573+05:30
%A Anas Jebreen Atyeeh Husain
%T On Minimum Variance CPU-Scheduling Algorithm for Interactive Systems using Goal Programming
%J International Journal of Computer Applications
%@ 0975-8887
%V 135
%N 11
%P 51-59
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Improving response time is considered a fundamental objective in interactive environments. CPU scheduling aimed mainly to optimize the response time by minimizing its average in order to attain faster responses to users’ requests. However, for interactive systems, reasonable and predictable services are more preferred than faster responses but highly variable. Delivering service in a timely manner at less variable response time is an issue that has been addressed in this paper. A goal programming (GP) model is proposed to perform CPU scheduling at minimum variance and low response time. The GP method determines the optimal process in the ready queue that best minimizes the variance to be executed first. A simulation system that can generate varied scheduling situations was developed and several tests were conducted. The performance of the proposed GP scheduling method is measured and compared to the other related scheduling methods. The evaluation results show that the GP scheduling method can provide predictable and reasonable service and it performs scheduling at minimum variance and lower response time. The GP method outperforms the other related methods with varying degrees.

References
  1. A. Silberschatz, P. B. Galvin, and G. Gagne, Operating system concepts. (John Wiley & Sons, 2013).
  2. S. Kato, Y. Ishikawa, and R. Rajkumar, CPU scheduling and memory management for interactive real-time applications. Real-Time Systems, Vol. 47, n. 5, pp. 454–488, 2011.
  3. A. S. Tanenbaum, and H. Bos, Modern operating systems. (Prentice Hall Press, 2014).
  4. M. A. Al-Husainy, Best-job-first CPU scheduling algorithm. Information Technology Journal Vol. 6, n. 2, pp. 288-293, 2007.
  5. I. Qureshi, 2014. CPU Scheduling Algorithms: A Survey. International Journal of Advanced Networking and Applications, 5(04): 1968-1973.
  6. S. Almakdi, M. Aleisa, and M. Alshehri, Simulation and Performance Evaluation of CPU Scheduling Algorithms. International Journal of Advanced Research in Computer and Communication Engineering, Vol. 4, n. 3, pp. 1-6, 2015.
  7. Y. Etsion, D. Tsafrir, and D. G. Feitelson, Process prioritization using output production: scheduling for multimedia. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), Vol. 2, n. 4, pp. 318-342, 2006.
  8. U. Schwiegelshohn, Preemptive weighted completion time scheduling of parallel jobs. SIAM Journal on Computing, Vol. 33, n. 6, pp. 1280-1308, 2004.
  9. Ramamritham, K., and Stankovic, J., Scheduling algorithms and operating systems support for real-time systems. Proceedings of the IEEE, (Page: 55-67 year of publication: 1994).
  10. Turek, J., Ludwig, W., Wolf, J. L., Fleischer, L., Tiwari, P., Glasgow, J.,and Yu, P. S., 1994. Scheduling parallelizable tasks to minimize average response time. Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, PP: 200-209.
  11. Cotton, I. W., 1977. Cost-benefit analysis of interactive systems. Computer Networks, 1(6), 311-324.
  12. A. Wierman, 2007. Scheduling for today’s computer systems: Bridging theory and practice. Unpublished dissertation in partial fulfillment of the requirements for the degree of PhD, Carnegie Mellon University, Pittsburgh.
  13. R. Geist, R. Allen, and R. Nowaczyk, Towards a model of user perception of computer systems response time. ACM SIGCHI Bulletin, Vol. 17, SI, pp. 249-253, 1986.
  14. Im, S., Kulkarni, J., and Moseley, B., Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time. Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, (Page: 155-160 year of publication: 2015).
  15. R. Krishnaswamy, Broadcast Scheduling: Minimizing Average Response Time. Encyclopedia of Algorithms, (Reference Work Entry), pp: 1-5.
  16. R. A. Kulkarni, and S. H., Patil, A survey on improving performance of Real Time Scheduling for Cloud Systems. International Journal for Innovative Research in Science and Technology, Vol. 1, n. 7, pp. 171-173, 2015.
  17. Li, Q., Wu, W., Zhou, X., Sun, Z., and Huang, J., R-FirstFit: A Reservation Based First Fit Priority Job Scheduling Strategy and Its Application for Rendering. Proceedings of the IEEE 17th International Conference on Computational Science and Engineering, CSE, (page: 1078-1085, 2014).
  18. G. You, X. Wang, and Y. Zhao, A Dynamic Requests Scheduling Model Based on Prediction in Multi-core Web Server. In: Internet of Vehicles – Technologies and Services, Lecture Notes in Computer Science, pp: 304-312, 2014. ISBN: 978-3-319-11166-7. DOI: 10.1007/978-3-319-11167-4_30
  19. S. M. Mostafa, and S. Kusakabe, Towards Minimizing Processes Response Time in Interactive Systems. International Journal of Computer Science and Information Technology Research, IJCSITR, Vol. 1, n. 1, pp. 65-73, 2013.
  20. G. You, and Y. Zhao, A weighted-fair-queuing, WFQ-based dynamic request scheduling approach in a multi-core system. Future Generation Computer Systems, Vol. 28, n. 7, pp. 1110-1120, 2012.
  21. Zhang, S., Wu, H., Wang, W., Yang, B., Liu, P., and Vasilakos, A. V., 2011. Distributed workload and response time management for web applications. Proceedings of the 7th International Conference on Network and Services Management, (page: 198-206 year of publication: 2011).
  22. C. Chekuri, S. Im, and B. Moseley, Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor. Theory of Computing, Vol. 8, n. 1, pp. 165-195, 2012.
  23. J. Chang, Online Broadcast Scheduling: Minimizing the Maximum Response Time. Theory of computing, Vol. 8, SI, pp. 165-195, 2012.
  24. C. Chekuri, S. Im, & B. Moseley, Minimizing maximum response time and delay factor in broadcast scheduling. In: Algorithms - ESA, Lecture Notes in Computer Science, pp: 444-455. ISBN: 978-3-642-04127-3.
  25. A. Wierman, and M. Harchol-Balter, Classifying scheduling policies with respect to higher moments of conditional response time. ACM SIGMETRICS Performance Evaluation Review, Vol. 33, n. 1, pp. 229-240, 2005.
  26. Hoxmeier, J. A., and DiCesare, C., System response time and user satisfaction: An experimental study of browser-based applications. Proceedings of AMCIS, (Page: 347 year of publication:2000).
  27. B. G. Dellaert, and B. E. Kahn, How tolerable is delay?: Consumers’ evaluations of internet web sites after waiting. Journal of interactive marketing, Vol. 13, n. 1, pp. 41-54, 1999.
  28. M. K. Hui, and L. Zhou, How Does Waiting Duration Information Influence Customers' Reactions to Waiting for Services. Journal of Applied Social Psychology, Vol. 26, n. 19, pp. 1702-1717, 1996.
  29. D. Raz, B. Avi-Itzhak, & H. Levy, Locality of reference and the use of sojourn time variance for measuring queue unfairness. SIGMETRICS Perform. Eval. Rev., Vol. 33, n. 2, pp. 39–41, 2005.
  30. S. Im, 2012. Online scheduling algorithms for average flow time and its variants. Unpublished dissertation in partial fulfillment of the requirements for the degree of Doctor of Philosophy, University of Illinois, Urbana-Champaign.
  31. A. Wierman, Fairness and scheduling in single server queues. Surveys in Operations Research and Management Science, Vol. 16, n. 1, pp. 39-48, 2011.
  32. D. F. Galletta, R. Henry, S. McCoy, and P. Polak, Web site delays: How tolerant are users?. Journal of the Association for Information Systems, Vol. 5, n. 1, pp. 1-28, 2004.
  33. B. Shneiderman, Designing the user interface: strategies for effective human-computer interaction. Applied Ergonomics. Vol. 24, n. 4, pp. 295, 2003.
  34. Chandio, A. A., Xu, C. Z., Tziritas, N., Bilal, K., and Khan, S. U., A comparative study of job scheduling strategies in large-scale parallel computational systems. Proceedings of the 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, IEEE, (page: 949-957 year of publication: 2013).
  35. R. Krishnaswamy, Broadcast Scheduling: Minimizing Average Response Time. Encyclopedia of Algorithms, (Reference Work Entry), pp: 1-5.
  36. Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., and Pruhs, K., Scheduling jobs with varying parallelizability to reduce variance. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’10, (page: 11-20 year of publication: 2010)
  37. U. Schwiegelshohn, W. Ludwig, J. L. Wolf, J. Turek, and P. S. Yu, Smart SMART bounds for weighted response time scheduling. SIAM Journal on Computing, Vol. 28, n. 1, pp. 237-253, 1998.
  38. J. Edmonds, Scheduling in the dark. Theoretical Computer Science, Vol. 235, n. 1, pp. 109-141, 1999.
  39. L. Cherkasova, Scheduling strategy to improve response time for web applications. In: High-Performance Computing and Networking, Lecture Notes in Computer Science, Springer Berlin Heidelberg. pp: 305-314, 1998. ISBN: 978-3-540-64443-9.
  40. I. A. Rai, G. Urvoy-Keller, & E. W. Biersack, Analysis of LAS scheduling for job size distributions with high variance. ACM SIGMETRICS Performance Evaluation Review, Vol. 31, n. 1, pp. 218-228, 2003.
  41. R. Gandhi, S. Khuller, Y. A. Kim, and Y. C. J. Wan, Algorithms for minimizing response time in broadcast scheduling. Algorithmica, Vol. 38, n. 4, pp. 597-608, 2004.
  42. M. Ubale, and M. Rahaman,. Improving the Performance of CPU Scheduling in Interactive Systems. International Journal of Advanced Research in Computer Science, Vol. 4, n. 1, pp. 25-28, 2013.
  43. P. M. Broadwell, Response time as a performability metric for online services. Computer Science Division, University of California. 2004.
  44. N. Bansal, and K. R. Pruhs, 2010. Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service. SIAM Journal on Computing, Vol. 39, n. 7, pp. 3311–3335, 2010.
  45. R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of scheduling. (Courier Corporation 2012). 978-1306365451.
  46. M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal, Size-based scheduling to improve web performance. ACM Transactions on Computer Systems, Vol. 21, n. 2, pp. 207-233, 2003.
  47. N. Bansal, and M. Harchol-Balter, Analysis of SRPT scheduling: Investigating unfairness. ACM, Vol. 29, n. 1, pp. 279-290, 2001.
  48. Waldspurger, C. A., and Weihl, W. E., Lottery scheduling: Flexible proportional-share resource management. of the 1st USENIX conference on Operating Systems Design and Implementation, USENIX Association, (pp: 1-11 year of publication: 1994).
  49. S. F. Yashkov, Mathematical problems in the theory of shared-processor systems. Journal of Soviet mathematics, Vol. 58, n. 2, pp. 101-147, 1992.
  50. P. Singh, A. Pandey, and A. Mekonnen,,. Varying Response Ratio Priority: A Preemptive CPU Scheduling Algorithm, VRRP. Journal of Computer and Communications, Vol. 3, n. 4, pp. 40-51, 2015.
  51. N. kumar, and Nirvikar, Performance improvement using CPU Scheduling Algorithm. International Journal of Emerging Trends of Technology in Computer Science, Vol. 2, n. 2, pp. 110-113, 2013. Retrieved from http://www.ijettcs.org/V2I2.html
  52. A. J. Husain, New Roll-Up Operator for Non-Additive Numeric Measure Summarization. Contemporary Engineering Sciences, Vol. 6, n. 8, pp. 393 – 402, 2013.
  53. Kiran, R. S., Babu, P. V., and Krishna, B. M., Optimizing CPU scheduling for real time applications using mean-difference round robin (MDRR) algorithm. Proceedings of the 48th Annual Convention of Computer Society of India, Springer, (page: 713-721 year of publication: 2014).
  54. R. S. Chang, J. S. Chang, and P. S. Lin, An ant algorithm for balanced job scheduling in grids. Future Generation Computer Systems, Vol. 25, n. 1, pp. 20-27, 2009.
  55. V. Gupta, M. Burroughs, & M. Harchol-Balter, Analysis of scheduling policies under correlated job sizes. Performance Evaluation, Vol. 67, n. 11, pp. 996-1013, 2010.
Index Terms

Computer Science
Information Sciences

Keywords

CPU scheduling Goal programming Interactive systems Response time Variance in response time

Powered by PhDFocusTM