Scheduling in Distributed Computing Systems: Analysis, Design and Models free download online
Title: Scheduling in Distributed Computing Systems: Analysis, Design and Models Author(s): Deo Prakash Vidyarthi Pages: 300 Publisher: Springer Publication date: 2008 Language: English Format: PDF ISBN-10: 0387744800 ISBN-13: Description: Chapter 1 discusses the possible performance improvement in computing system.
It also addresses how the distributed computing system has evolved over the years
and the issues in DCS research.
Chapter 2 briefs about the distributed computing system. It discusses various architectural
models of DCS. Transparency is one of the biggest issues in the design
of a DCS that gives the DCS a single system image. Chapter 2 points out transparency
issues of the DCS. Fault tolerance and synchronization in the DCS has also
been briefed in chapter 2.
Preface ix
Chapter 3 defines the scheduling problem and identifies the characteristic parameter
for a scheduler. It indicates the task allocation issues. Assumptions and notation,
used in this book, have been kept together at one place in chapter 3.
Chapter 4 addresses the load balancing problem in a DCS. It defines load distribution,
load balancing methodology, migration and also the conflict between load
balancing and task allocation.
Chapter 5 briefs the earlier task allocation models. Propositions, which consider
the precedence amongst the modules of the task and multiprogramming of the individual
nodes, have been proposed in section 5.3 of chapter 5 using list schedule.
In the same chapter an inter module communication reduction model is also proposed
(sec. 5.4), which incurs a heavy penalty in total turnaround time of any task.
Chapter 6 proposes a few Load Balancing Task Allocation (LBTA) models. It discusses
the LBTA strategy and its solution for single and multiple tasks.
Chapter 7 uses the important search technique of GA in proposing two allocation
models, one, which incorporates problem specific knowledge for quick convergence
and the other to maximize the reliability of the DCS with allocation.
Chapter 8 considers the important proposition of multiple tasks allocation and
proposes a few models. In section 8.1, an allocation algorithm based on A* is proposed
and in section 8.2 a new and novel idea of cluster based allocation is proposed.
Cluster based allocation model avoids the priori requirement of execution
x Scheduling in Distributed Computing Systems
time of modules of the task on the processing nodes and thus can be proved to be
very useful model of task allocation. Sections 8.3 and 8.4 deal with the LBTA
strategy using A* and GA respectively.
Chapter 9 proposes few other approaches for task allocation models. These are
hybrid and object oriented models.
Computational Grid is an emerging form of distributed computing. Chapter 10
concentrates on Grid Computing systems and discusses the scheduling problem
for a computational grid. “What are the various issues in Scheduling for Grid
Computing systems?” finds place in chapter 10.
Finally concluding remarks are made in chapter 11. This chapter also discusses the
structure and place of a scheduler in a DCS.
Preface xi
TABLE OF CONTENTS
1 Introduction ........................................................................................................ 1
1.1 Performance Improvement in Computing System....................................... 2
1.2 High Speed Computing and DCS ................................................................ 4
1.3 Evolution of the DCS................................................................................... 6
1.4 Issues in DCS Research ............................................................................... 9
1.5 Organization of the Book........................................................................... 12
BIBLIOGRAPHY............................................................................................ 15
2 An Overview of a Distributed System............................................................. 17
2.1 DCS Architecture Models.......................................................................... 17
2.2 Transparency in DCS................................................................................. 22
2.3 Introduction to Fault Tolerance ................................................................. 25
2.4 Synchronization ......................................................................................... 27
BIBLIOGRAPHY............................................................................................ 29
3 Scheduling Problem......................................................................................... 31
3.1 On Functioning of a DCS .......................................................................... 32
3.2 Desirable Characteristics of a Scheduler ................................................... 34
3.3 Scheduler as a Task Allocator ................................................................... 35
3.4 Task Allocation Issues in DCS .................................................................. 36
3.5 The Task Allocation Problem.................................................................... 38
3.6 Assumptions & Notation ........................................................................... 42
BIBLIOGRAPHY............................................................................................ 44
4 Load Balancing in DCS.................................................................................... 47
4.1 Load Distribution in a DCS ....................................................................... 47
4.2 Load Balancing Methodology ................................................................... 49
4.3 Task Migration........................................................................................... 52
4.4 Threads ...................................................................................................... 55
4.5 Conflicts between TA and LB ................................................................... 55
BIBLIOGRAPHY............................................................................................ 59
5 Known Task Allocation Models ...................................................................... 61
5.1 Early Models.............................................................................................. 62
5.2 Limitations of Earlier Models.................................................................... 72
5.3 Precedence Constrained Task Allocation .................................................. 74
5.4 IMC Cost Reduction using Fuzzy Logic ............................................... 83
BIBLIOGRAPHY............................................................................................ 87
PREFACE............................................................................................................ vii
6 Load Balancing Task Allocation (LBTA) .......................................................89
6.1 Known Load Balancing Strategies...........................................................89
6.2 Issues of LBTA Strategy..........................................................................93
6.3 The LBTA Solution .................................................................................94
6.4 Loads in LBTA for Single Task...............................................................97
6.5 Loads in LBTA for Multiple Tasks............................................................99
BIBLIOGRAPHY..........................................................................................101
7 GA Based Task Allocation Models................................................................103
7.1 Task Allocation using Genetic Algorithm ...............................................105
7.2 Maximizing Reliability of DCS with Task Allocation using GA ............113
BIBLIOGRAPHY..........................................................................................122
8 Allocation of Multiple Tasks in DCS ............................................................125
8.1 Multiple Task Allocation .........................................................................1
Scheduling in Distributed Computing Systems: Analysis, Design and Models free download links:
Title: Scheduling in Distributed Computing Systems: Analysis, Design and Models