1 of 69

DISTRIBUTED COMPUTING

Sunita Mahajan, Principal, Institute of Computer Science, MET League of Colleges, Mumbai

Seema Shah, Principal, Vidyalankar Institute of Technology, Mumbai University

2 of 69

Chapter - 6�Distributed System Management

3 of 69

Topics

Introduction
Resource management
Task assignment approach
Load balancing approach
Load sharing approach
Process management in a distributed environment
Process migration
Threads
Fault tolerance

4 of 69

Introduction

5 of 69

Categories of Distributed System management

Resource management
Process management
Fault tolerance

6 of 69

Resource Management

7 of 69

Process scheduling techniques

Task assignment approach
Load balancing approach
Load sharing approach

8 of 69

Example: Google system

Load balancing by using least loaded server
Proximity routing
Fault masking

9 of 69

Desirable features of a good global scheduling algorithm

No apriori knowledge about processes to be executed
Ability to make dynamic scheduling decisions
Flexible
Stable
Scalable
Unaffected by system failures

10 of 69

Task Assignment Approach

11 of 69

Task assignment

Minimize IPC costs
Less turnaround time for process completion
High degree of parallelism
Efficient usage of all system resources

12 of 69

Graph theoretic deterministic algorithm

A system with m CPUs and n processes has any of the following three cases:

m=n: Each process is allocated to one CPU
m<n: Some CPUs may remain idle or work on earlier allocated processes
m>n: There is a need to schedule processes on CPUs, and several processes may be assigned to each CPU.

13 of 69

Example of graph theoretic deterministic algorithm-1

Weighted graph

Each node is a process
Each arc is message flowing between two processes

14 of 69

Example of graph theoretic deterministic algorithm-2

15 of 69

Centralized heuristic algorithm

Also called Top down algorithm
Allocated processing capacity fairly

2

16 of 69

Hierarchical algorithm

Works between two levels in a group
Top of the tree is truncated into a committee which manages fault tolerance

17 of 69

Load Balancing Approach

18 of 69

Load balancing Taxonomy

Improve resource utilization

19 of 69

Issues in designing in load balancing algorithms

Deciding policies for:

Load estimation
Process transfer
Static information exchange
Location
Priority assignment
Migration limitation

20 of 69

Policies for Load estimation

Parameters:

Time dependent
Node dependent

21 of 69

Policies for Process transfer

Threshold policy

Static
Dynamic

22 of 69

Location policies

Used to select destination node

23 of 69

State information exchange

Dynamic policy
Decision based on state information

24 of 69

Priority assignment

To schedule local and remote processes at a node

25 of 69

Migration limiting policies

Uncontrolled policy
Controlled policy

26 of 69

�Load Sharing Approach �

27 of 69

Issues in designing load sharing algorithms

Load estimation policies
Process transfer policies
Location policies
State information exchange policies

28 of 69

Location policies-1

Decides whether sender or receiver node process is to be migrated

29 of 69

Location policies-2

Sender initiated algorithms make scheduling decisions at process arrival epoch
Receiver initiated algorithms make scheduling decisions at process departure epochs

30 of 69

State information exchange policies

Broadcast
Poll

31 of 69

Process Management In A Distributed Environment

32 of 69

Functions of distributed process management

Process migration

change of location and execution of a process from current processor to the destination processor

33 of 69

Desirable features of a good process migration mechanism

Transparency
Minimal interference
Minimal residual dependencies
Efficiency
Robustness
Ability to communicate between co processes of the job

34 of 69

Process Migration

35 of 69

Steps involved in process migration

Freezing process on the source node
Starting process on the destination node
Transporting process address space on destination node
Forward the messages addressed to migrated processes

36 of 69

Mechanism

37 of 69

Freezing process on source node

Blocking sequence:

Blocking the process immediately
Wait for I/O operations to complete and then block the process.

Track information about open files
Create an empty process on the destination node
Transfer the migrant process and address space
Restart process on destination node

38 of 69

Address space transport mechanisms-1

Process address space:

Process state: PCB information
Process address space: Program code, data and stack

39 of 69

Address space transport mechanisms-2

Total freezing:

Process execution stopped during address space transfer

40 of 69

Address space transport mechanisms-3

Pre transfer:

Address space is transferred while process continues to run on source node
Highest priority in scheduling

41 of 69

Address space transport mechanisms-4

Transfer-on –reference:

Process state is transferred while address space is transferred on demand

42 of 69

Message forwarding

Track and forward messages which have arrived on source node after process migration

43 of 69

Handle communication between cooperating processes

Avoid separation of coprocesses

Home node concept

Deployed in Sprite system

44 of 69

Process migration in heterogeneous systems

Handling floating point numbers

Different sized exponents in XDR format
Handling overflow and underflow
Handling Mantissa
Handling signed infinity and zero representations

45 of 69

Advantages of process migration

Reduce average response time of heavily loaded nodes
Speed up of individual jobs
Better utilization of resources
Improve reliability of critical processes
Improving system security

46 of 69

Threads

47 of 69

Process v/s threads

Analogy:

Thread is to a process as process is to a machine

48 of 69

Comparison

49 of 69

Thread models

Dispatcher worker model
Team model
Pipeline model

50 of 69

Thread: Dispatcher worker model

51 of 69

Thread: Team model

52 of 69

Thread: Pipeline model

53 of 69

Design issues in threads

Thread semantics

Thread creation, termination

Thread synchronization
Thread scheduling

54 of 69

Thread synchronization

Execution in Critical region

Use binary semaphore

55 of 69

Threads scheduling

Priority assignment facility
Choice of dynamic variation of quantum size
Handoff scheduling scheme
Affinity scheduling scheme
Signals used for providing interrupts and exceptions

56 of 69

Implementing thread package

User level approach

Kernel level approach

57 of 69

Comparison of thread implementation-1

58 of 69

Comparison of thread implementation-2

59 of 69

Threads and Remote execution

RPC
RMI and Java threads

60 of 69

RPC execution

61 of 69

Threads are created on the fly

62 of 69

�Fault Tolerance �

63 of 69

Component faults

Transient faults
Intermittent faults
Permanent faults

∞

Mean time to failure = ∑ kp (1-p) ^k-1

k=1

Mean time to failure = 1/p

64 of 69

System failures

Fail silent faults / fail stop faults
Byzantine faults

65 of 69

Use of redundancy

Information redundancy
Time redundancy
Physical redundancy

Active replication
Primary backup methods

66 of 69

Active replication-1

State machine approach

(TMR -Triple Modular Redundancy)

67 of 69

Active replication-2

68 of 69

Primary backup

Uses two machines :

Primary and backup

Uses limited number of messages such that these messages go only to the primary server and no ordering is required

69 of 69

Summary

Introduction
Resource management
Task assignment approach
Load balancing approach
Load sharing approach
Process management in a distributed environment
Process migration
Threads
Fault tolerance