A Taxonomy of Schedulers – Operating Systems, Clusters and Big Data Frameworks

A Taxonomy of Schedulers – Operating Systems, Clusters and Big Data Frameworks

Leszek Sliwko

Contact

α Axis Applications Limited

A Taxonomy of Schedulers – Operating Systems, Clusters and Big Data Frameworks

Article Fingerprint

ReserarchID

CSTB0BTI6

A Taxonomy of Schedulers – Operating Systems, Clusters and Big Data Frameworks Banner

AI TAKEAWAY

Connecting with the Eternal Ground

Abstract

This review analyzes deployed and actively used workload schedulers’ solutions and presents a taxonomy in which those systems are divided into several hierarchical groups based on their architecture and design. While other taxonomies do exist, this review has focused on the key design factors that affect the throughput and scalability of a given solution, as well as the incremental improvements which bettered such an architecture. This review gives special attention to Google’s Borg, which is one of the most advanced and published systems of this kind.

References

93 Cites in Article

Reference Format

(2000). Apache Aurora.
Nick Marathon (2018). Ocean Shipping Container Availability Report 10-10-2012.
Chris Gaffney (2002). Geophysical survey in archaeological field evaluation. David A, Linford N, Linford P, English Heritage Publishing, 2008. Pages: 59. – English Heritage, Customer Services Department, PO Box 569, Swindon SN2 2YP. Product Code 51430. PDF version available on line at http://www.english‐heritage.org.uk/upload/pdf/GeophysicsGuidelines.pdf.
Christer Bergsten (2001). News from Nordic mathematics education.
(2017). Top500 List.
(2015). Torque from 10,000 Feet.
Yair Amir,Baruch Awerbuch,Amnon Barak,R Borgstrom,Arie Keren (2000). An opportunity cost approach for job assignment in a scalable computing cluster.
R Arpaci-Dusseau,A Arpaci-Dusseau (2015). Fail-stutter fault tolerance.
Luiz Barroso,J Dean,U Holzle (2003). Web search for a planet: the google cluster architecture.
Luca Becchetti,Stefano Leonardi,Alberto Marchetti-Spaccamela,Guido Schäfer,Tjark Vredeveld (2006). Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm.
Sergey Blagodurov,Sergey Zhuravlev,Alexandra Fedorova,Ali Kamali (2010). A case for NUMA-aware contention management on multicore systems.
Bode,David Brett,Ricky Halstead,Zhou Kendall,David Lei,Jackson (2000). The Portable Batch Scheduler and the Maui Scheduler on Linux Clusters.
Thomas Bonald,Laurent Massoulié,A Proutière,J Virtamo (2006). A queueing analysis of max-min fairness, proportional fairness and balanced fairness.
Eric Boutin,Wei Jaliyaekanayake,Bing Lin,Jingren Shi,Zhengping Zhou,Ming Qian,Lidong Wu,Zhou (2014). Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing.
Yingyi Bu,Bill Howe,Magdalena Balazinska,Michael Ernst (2010). HaLoop.
James Bulpin (2005). Operating system support for simultaneous multithreaded processors.
Brendan Burns,Brian Grant,David Oppenheimer,Eric Brewer,John Wilkes (2016). Borg, Omega, and Kubernetes.
Matthew Campbell (2017). Dundas, Sir Henry Matthew, (17 May 1937–24 June 1963).
Fernando Corbató,Marjorie Merwin-Daggett,Robert Daley (1962). An experimental time-sharing system.
Jonathan Corbet (2004). The staircase scheduler.
Jonathan Corbet (2007). The Rotating Staircase Deadline Scheduler.
James Corbett,Jeffrey Dean,Michael Epstein,Andrew Fikes,Christopher Frost,Jeffrey John Furman,Sanjay Ghemawat (2013). Spanner: Google's globally distributed database.
Jeffrey Dean,Sanjay Ghemawat (2010). MapReduce.
Ulrich Drepper (2007). What every programmer should know about memory.
Yoav Etsion,Dan Tsafrir (2005). A short survey of commercial cluster batch schedulers.
Ian Foster,Carl Kesselman (1997). Globus: a Metacomputing Infrastructure Toolkit.
Ian Foster,Carl Kesselman,Steven Tuecke (2001). The anatomy of the grid: Enabling scalable virtual organizations.
Edgar Gabriel,Graham Fagg,George Bosilca,Thara Angskun,Jack Dongarra,Jeffrey Squyres,Vishal Sahay,Prabhanjan Kambadur,Brian Barrett,Andrew Lumsdaine,Ralph Castain,David Daniel,Richard Graham,Timothy Woodall (2004). Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation.
Wolfgang Gentzsch (2001). Sun Grid Engine: towards creating a compute power grid.
Sanjay Ghemawat,Howard Gobioff,Shun-Tak Leung (2003). The Google file system.
I Gog (2012). Motherwell, Prof. William Branks, (born 10 May 1947), Alexander Williamson Professor of Chemistry (first incumbent), University College London, 1993–2012, now Emeritus; Visiting Researcher, Imperial College London, since 2012.
Andrew Grimshaw (1990). The Mentat Run-Time System: Support for Medium Grain Parallel Computation.
Andrew Grimshaw,Anh Nguyen-Tuong,William Wulf (1994). Campus-Wide Computing: Early Results Using Legion at the University of Virginia.
Taylor Groves,Jeff Knockel,Eric Schulte (2009). BFS vs. CFS -Scheduler Comparison.
Volker Hamscher,Uwe Schwiegelshohn,Achim Streit,Ramin Yahyapour (2000). Evaluation of Job-Scheduling Strategies for Grid Computing.
Johnson Hart (1997). Win32 systems programming.
Pat Helland,Harris Ed (2011). Cosmos: Big Data and Big Challenges.
Benjamin Hindman,Andy Konwinski,Matei Zaharia,Ali Ghodsi,Anthony Joseph,Randy Katz,Scott Shenker,Ion Stoica (2011). Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center.
Michael Isard,Mihai Budiu,Yuan Yu,Andrew Birrell,Dennis Fetterly (2007). Dryad.
Michael Isard,Vijayan Prabhakaran,Jon Currey,Udi Wieder,Kunal Talwar,Andrew Goldberg (2009). Quincy.
David Jackson,Quinn Snell,Mark Clement (2001). Core algorithms of the Maui scheduler.
M Jones,Tim (2009). Inside the Linux 2.6 Completely Fair Scheduler -Providing fair access to CPUs since 2.6.23.
Kannan,Mark Subramanian,Peter Roberts,Dave Mayes,Joseph Brelsford,Skovira (2001). Workload management with LoadLeveler.
Judy Kay,Piers Lauder (1988). A fair share scheduler.
Dalibor Klusáček,Hana Rudová (2010). EFFICIENT GRID SCHEDULING THROUGH THE INCREMENTAL SCHEDULE‐BASED APPROACH.
Dalibor Klusáček,Václav Chlumský,Hana Rudová (2013). Planning and Optimization in TORQUE Resource Manager.
Con Kolivas (2016). Denying Service.
Klaus Krauter,Rajkumar Buyya,Muthucumaru Maheswaran (2002). A taxonomy and survey of grid resource management systems for distributed computing.
Sanjeev Kulkarni,Nikunj Bhagat,Maosong Fu,Vikas Kedigehalli,Christopher Kellogg,Sailesh Mittal,Jignesh Patel,Karthik Ramasamy,Siddarth Taneja (2015). Twitter Heron.
Leslie Lamport (1998). The part-time parliament.
Willis Lang,Jignesh Patel (2010). Energy management for MapReduce clusters.
Ian Lewis,David Oppenheimer (2017). Advanced Scheduling in Kubernetes.
Michael Litzkow,M Livny,M Mutka (1988). Condor-a hunter of idle workstations.
Xunyun Liu,Rajkumar Buyya (2017). D-Storm: Dynamic Resource-Efficient Scheduling of Stream Processing Applications.
Jean-Pierre Lozi,Baptiste Lepers,Justin Funston,Fabien Gaud,Vivien Quéma,Alexandra Fedorova (2016). The Linux scheduler: a decade of wasted cores.
Nathan Marz (2011). A Storm is coming: more details and plans for release.
John Mccullough,Yuvraj Agarwal,Jaideep Chandrashekar,Sathyanarayan Kuppuswamy,Alex Snoeren,Rajesh Gupta (2011). Evaluating the effectiveness of model-based power characterization.
Ismael Moreno,Paul Garraghan,P Townend,Jie Xu (2013). An Approach for Characterizing Workloads in Google Cloud to Derive Realistic Resource Utilization Models.
Derek Murray,Malte Schwarzkopf,Christopher Smowton,Steven Smith,Anil Madhavapeddy,Steven Hand (2011). CIEL: a universal execution engine for distributed data-flow computing.
Nitin Naik (2016). Building a virtual system of systems using Docker Swarm in multiple clouds.
Chandandeep Pabla,Singh (2009). Completely fair scheduler.
Edson Padoin,Marcio Castro,Laercio Pilla,Philippe Navaux,Jean-Francois Mehaut (2014). Saving energy by exploiting residual imbalances on iterative applications.
Jose Pascual,Javier Navaridas,Jose Miguel,-Alonso (2009). Effects of topology-aware allocation policies on scheduling performance.
Frederic Pinel,Johnatan Pecero,Pascal Bouvry,Samee Khan (2011). A Review on Task Performance Prediction in Multi-core Based Systems.
Eduardo Pinheiro,Ricardo Bianchini,Enrique Carrera,Taliver Heath (2001). Dynamic Cluster Reconfiguration for Power and Performance.
Florin Pop,C Dobre,G Godza,V Cristea (2006). A Simulation Model for Grid Scheduling Analysis and Optimization.
Biplob Ray,Morshed Chowdhury,Usman Atif (2017). Is High Performance Computing (HPC) Ready to Handle Big Data?.
Maria Rodriguez,Rajkumar Buyya (2017). A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments.
Sarood,Phil Osman,Ehsan Miller,Laxmikant Totoni,Kale (2012). Cool" Load Balancing for High Performance Computing Data Centers.
Malte Schwarzkopf,Andy Konwinski,Michael Abd-El-Malek,John Wilkes (2013). Omega.
Madhavapeddi Shreedhar,George Varghese (1995). Efficient fair queueing using deficit round robin.
Ajit Singh (2017). New York Stock Exchange Oracle Exadata -Our Journey.
Leszek Sliwko (2018). Information technology. Cloud computing. Interacting with cloud service partners (CSNs).
Sucha Smanchat,Kanchana Viriyapant (2015). Taxonomies of workflow scheduling problem and techniques in the cloud.
Larry Smarr,Charles Catlett (2003). Metacomputing.
Douglas Thain,Todd Tannenbaum,Miron Livny (2005). Distributed computing in practice: the Condor experience.
Linus Torvalds (2001). Just For Fun: The Story of an Accidental Revolutionary Linus Torvalds with David Diamond.
Ankit Toshniwal,Siddarth Taneja,Amit Shukla,Karthik Ramasamy,Jignesh Patel,Sanjeev Kulkarni,Jason Jackson,Krishna Gade,Maosong Fu,Jake Donham,Nikunj Bhagat,Sailesh Mittal,Dmitriy Ryaboy (2014). Storm@twitter.
Rinki Tyagi,Santosh Gupta (2018). A Survey on Scheduling Algorithms for Parallel and Distributed Systems.
Vinod Vavilapalli,Arun Murthy,Chris Douglas,Sharad Agarwal,Mahadev Konar,Robert Evans,Thomas Graves,Jason Lowe,Hitesh Shah,Siddharth Seth,Bikas Saha,Carlo Curino,Owen O'malley,Sanjay Radia,Benjamin Reed,Eric Baldeschwieler (2013). Apache Hadoop YARN.
Abhishek Verma,Luis Pedrosa,Madhukar Korupolu,David Oppenheimer,Eric Tune,John Wilkes (2015). Large-scale cluster management at Google with Borg.
Tom White (2012). Hadoop: The definitive guide.
C Wong,I Tan,R Kumari,J Lam,W Fun (2008). Fairness and interactive performance of O(1) and CFS Linux kernel schedulers.
Deepak Vohra (2017). Scheduling Pods on Nodes.
Pamela Vagata,Kevin Wilfong (2014). Scaling the Facebook data warehouse to 300 PB.
Andy Yoo,Morris Jette,Mark Grondona (2003). SLURM: Simple Linux Utility for Resource Management.
Jia Yu,Rajkumar Buyya (2005). A taxonomy of scientific workflow systems for grid computing.
Matei Zaharia,Dhruba Borthakur,Joydeep Sen Sarma,Khaled Elmeleegy,Scott Shenker,Ion Stoica (2009). Delay scheduling.
Matei Zaharia,Mosharaf Chowdhury,Michael Franklin,Scott Shenker,Ion Stoica (2010). Spark: Cluster computing with working sets.
Matei Zaharia,Tathagata Das,Haoyuan Li,Timothy Hunter,Scott Shenker,Ion Stoica (2012). Discretized Streams: A Fault-Tolerant Model for Scalable Stream Processing.
Muhammad Zakarya,Lee Gillam (2017). Energy efficient computing, clusters, grids and clouds: A taxonomy and survey.
Petar Zecevic,Marko Bonaci (2016). Spark in Action.
Zhuo Zhang,Chao Li,Yangyu Tao,Renyu Yang,Hong Tang,Jie Xu (2014). Fuxi.

Download References

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

Leszek Sliwko. 2019. \u201cA Taxonomy of Schedulers – Operating Systems, Clusters and Big Data Frameworks\u201d. Global Journal of Computer Science and Technology - B: Cloud & Distributed GJCST-B Volume 19 (GJCST Volume 19 Issue B1): .

More Citation Formats

Select Citation Style:

Download Citation

Download Article

GJCST Volume 19 Issue B1
Pg. 25- 40

Explore Journals Explore Volume Read This Issue

Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Keywords

Not Found

Classification

GJCST-B Classification: I.2.8

Submission ReceivedDecember 16, 2018
Peer Review Double Blind
Handling Editor
Accepted January 1, 2019
Published January 15, 2019

Version of record

v1.2

Issue date

March 14, 2019

Language

Experiance in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

View in VR

Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

View in 3D

Article Matrices

Total Score: 131

Country: United Kingdom

Subject: Global Journal of Computer Science and Technology - B: Cloud & Distributed

Authors: Leszek Sliwko (PhD/Dr. count: 0)

View Count (all-time): 324

Total Views (Real + Logic): 5645

Total Downloads (simulated): 1430

Publish Date: 2019 03, Thu

Monthly Totals (Real + Logic):

Month 1: 22 views
Month 2: 39 views
Month 3: 40 views
Month 4: 57 views
Month 5: 28 views
Month 6: 28 views
Month 7: 26 views
Month 8: 54 views
Month 9: 55 views
Month 10: 46 views
Month 11: 40 views
Month 12: 36 views
Month 13: 15 views
Month 14: 34 views
Month 15: 38 views
Month 16: 37 views
Month 17: 44 views
Month 18: 35 views
Month 19: 39 views
Month 20: 48 views
Month 21: 21 views
Month 22: 43 views
Month 23: 26 views
Month 24: 27 views
Month 25: 37 views
Month 26: 29 views
Month 27: 33 views
Month 28: 30 views
Month 29: 29 views
Month 30: 42 views
Month 31: 43 views
Month 32: 24 views
Month 33: 22 views
Month 34: 48 views
Month 35: 40 views
Month 36: 20 views
Month 37: 28 views
Month 38: 26 views
Month 39: 36 views
Month 40: 27 views
Month 41: 44 views
Month 42: 28 views
Month 43: 39 views
Month 44: 28 views
Month 45: 19 views
Month 46: 24 views
Month 47: 27 views
Month 48: 30 views
Month 49: 40 views
Month 50: 46 views
Month 51: 14 views
Month 52: 46 views
Month 53: 16 views
Month 54: 32 views
Month 55: 29 views
Month 56: 42 views
Month 57: 32 views
Month 58: 40 views
Month 59: 42 views
Month 60: 32 views
Month 61: 20 views
Month 62: 37 views
Month 63: 31 views
Month 64: 27 views
Month 65: 35 views
Month 66: 28 views
Month 67: 25 views
Month 68: 33 views
Month 69: 28 views
Month 70: 47 views
Month 71: 35 views
Month 72: 31 views
Month 73: 38 views
Month 74: 32 views
Month 75: 24 views
Month 76: 42 views
Month 77: 50 views
Month 78: 54 views
Month 79: 45 views
Month 80: 29 views
Month 81: 35 views
Month 82: 12 views
Month 83: 49 views
Month 84: 40 views
Month 85: 73 views

Total Views: 5645

Total Downloads: 1430

2026 Trends

Published Article

Our website is actively being updated, and changes may occur frequently. Please clear your browser cache if needed. For feedback or error reporting, please email [email protected]