E Lesson 6 635

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

M.C.A 2 All right are reserved with CU-IDOL PARALLEL AND DISTRIBUTED COMPUTING Course Code: MCA635 Semester: Third SLM Unit : 6 E-Lesson: 6 www.cuidol.in Unit-6 (MCA635)

Resource Management 33 OBJECTIVES INTRODUCTION Student will be able to : In this unit we are going to learn about the global scheduling algorithm. List the desirable features of global scheduling algorithm Describe the task assignment approach Under this unit you will also understand the Task Assignment approach. Explain load balancing approach This Unit will also make us to understand Describe load sharing approach Load balancing and load sharing approaches. www.cuidol.in Unit-6 (MCA635) INASllTITriUgThEt aOrFeDreISsTeArNveCdE AwNitDh OCNUL-IIDNOE LLEARNING

TOPICS TO BE COVERED 4 6.1 Introduction 6.2 Desirable Features of global Scheduling Algorithm 6.3 Task Assignment Approach 6.4 Load-balancing Approach 6.5 Load Sharing Approach www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

INTRODUCTION 5 • A resource can be a logical, such as a shared file, or physical, such as a CPU (a node of the distributed system). • One of the functions of a distributed operating system is to assign processes to the nodes (resources) of the distributed system such that the resource usage, response time, network congestion, and scheduling overhead are optimized. • Resource manager of a distributed system schedules the processes to optimize combination of resources usage, response time, network congestion, scheduling overhead. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Desirable Features of Global 6 scheduling algorithm • Dynamic in nature: • Process assignment decisions should be dynamic, I.e., be based on the current load of the system and not on some static policy. • It is recommended that the scheduling algorithm possess the flexibility to migrate a process more than once because the initial decision of placing a process on a particular node may have to be changed after some time to adapt to the new system load. • Quick decision making capability: • Heuristic methods requiring less computational efforts (and hence less time) while providing near- optimal results are preferable to exhaustive (optimal) solution methods. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Desirable Features of Global scheduling 7 algorithm • Balanced system performance and scheduling overhead: • Algorithms that provide near-optimal system performance with a minimum of global state information (such as CPU load) gathering overhead are desirable. • Stability: • Fruitless migration of processes, known as processor thrashing, must be prevented. • Scalability: • A scheduling algorithm should scale well as the number of nodes increases. An algorithm that makes scheduling decisions by first inquiring the workload from all the nodes and then selecting the most lightly loaded node has poor scalability. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Desirable Features of Global scheduling 8 algorithm • Fault tolerance: • A good scheduling algorithm should not be disabled by the crash of one or more nodes of the system. Also, if the nodes are partitioned into two or more groups due to link failures,the algorithm should be capable of functioning properly for the nodes within a group. • Fairness of service: • Global scheduling policies that blindly attempt to balance the load on all the nodes of the system are not good from the point of view of fairness of service. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Task Assignment 9 Approach • Each process is viewed as a collection of tasks. These tasks are scheduled to suitable processor to improve performance. This is not a widely used approach because: • It requires characteristics of all the processes to be known in advance. • This approach does not take into consideration the dynamically changing state of the system. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Task Assignment 10 Approach • In this approach, a process is considered to be composed of multiple tasks and the goal is to find an optimal assignment policy for the tasks of an individual process. • The following are typical assumptions for the task assignment approach: • Minimize IPC cost (this problem can be modeled using network flow model) • Efficient resource utilization • Quick turnaround time • A high degree of parallelism www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Load Balancing 11 Approach • Type of Load-balancing Algorithms • Static versus Dynamic • Static algorithms use only information about the average behavior of the system Static algorithms ignore the current state or load of the nodes in the system Dynamic algorithms collect state information and react to system state if it changed Static algorithms are much more simpler Dynamic algorithms are able to give significantly better performance www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

12 • Load-balancing Approach Type of Static Load-balancing Algorithms • Deterministic versus Probabilistic • Deterministic algorithms use the information about the properties of the nodes and the characteristic of processes to be scheduled Probabilistic algorithms use information of static attributes of the system (e.g., number of nodes, processing capability, topology) to formulate simple process placement rules Deterministic approach is difficult to optimize Probabilistic approach has poor performance. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

13 • Load-balancing Approach Type of Dynamic Load-balancing Algorithms • Centralized versus Distributed • Centralized approach collects information to server node and makes assignment decision • Distributed approach contains entities to make decisions on a predefined set of nodes Centralized algorithms can make efficient decisions, have lower fault-tolerance Distributed algorithms avoid the bottleneck of collecting state information and react faster. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

14 • Load-balancing Approach Type of Distributed Load-balancing Algorithms • Cooperative versus Non-cooperative • In Non-cooperative algorithms entities act as autonomous ones and make scheduling decisions independently from other entities. In Cooperative algorithms distributed entities cooperate with each other Cooperative algorithms are more complex and involve larger overhead Stability of Cooperative algorithms are better. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Issues in Designing Load-balancing 15 Algorithms • 1. Load estimation policy: determines how to estimate the workload of a node. • 2. Process transfer policy: determines whether to execute a process locally or remote. • State information exchange policy: determines how to exchange load information • among nodes. • Location policy: determines to which node the transferable process should be sent. • Priority assignment policy: determines the priority of execution of local and remote processes. • Migration limiting policy: determines the total number of times a process can migrate. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

Load Sharing Approach 16 • Load sharing means one can split the traffic from a network to be transported by different routers (paths). • That’s exactly what Cisco does with MHSRP. • The document on Configuring Multi chassis Multilink PPP states that when it tells it to configure half of the hosts with one default gateway and the second half with the other. • Load sharing is inherent to the forwarding process of a router to share the forwarding of traffic, if the routing table has multiple paths to a destination. • If equal paths, the forwarding process will decide the manner of forwarding and forward packets based on the load-sharing algorithm used. • This still bears the possibility of unbalanced forwarding. • If unequal paths, the traffic is distributed inversely proportionally to the cost of the routes. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 1. The systems which allow only one process execution at a time, are called ____________. 17 (a) uniprogramming systems (b) uniprocessing systems (c) unitasking systems (d) none of the mentioned 2. In operating system, each process has its own ____________. (a) address space and global variables (b) open files (c) pending alarms, signals and signal handlers (d) all of the mentioned 3. In Unix, Which system call creates the new process? (a) fork (b) create (c) new (d) none of the mentioned 4. A process can be terminated due to ____________. (a) normal exit (b) fatal error (c) killed by another process (d) all of the mentioned Answers: 1.(b) 2. (d) 3. (a) 4.(d) www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 18 5. What is the ready state of a process? (a) when process is scheduled to run after some execution (b) when process is unable to run until some task has been completed (c) when process is using the CPU (d) none of the mentioned 6. What is interprocess communication? (a) communication within the process (b) communication between two process (c) communication between two threads of same process (d) none of the mentioned 7. A set of processes is deadlock if ____________. (a) each process is blocked and will remain so forever (b) each process is terminated (c) all processes are trying to kill each other (d) none of the mentioned Answers: 5. (a) 6. (b) 7.(a) www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 19 8. A process stack does not contain ____________. (b) Local variables (a) Function parameters (d) PID of child process (c) Return addresses 9. Which system call returns the process identifier of a terminated child? (a) wait (b) exit (c) fork (d) get 10. The address of the next instruction to be executed by the current process is provided by the ____________. (a) CPU registers (b) Program counter (c) Process stack (d) Pipe Answers: 8.(d) 9.(a) 10.(b) www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

SUMMARY Resource manager of a distributed system schedules the processes to optimize combination of 20 resources usage, response time, network congestion, scheduling overhead.There are three techniques for scheduling processes of a distributed system: 1. Task Assignment Approach, in which each process submitted by a user for processing is viewed as a collection of related tasks and these tasks are scheduled to suitable nodes so as to improve performance. 2. Load-balancing approach, in which all the processes submitted by the users are distributed among the nodes of the system so as to equalize the workload among the nodes. 3. Load-sharing approach, which simply attempts to conserve the ability of the system to perform work by assuring that no node is idle while processes wait for being processed. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTIONS 21 Q1. Descrive the desirable features of Global scheduling algorithm. 6 Ans: Desirable Features of Global scheduling algorithm are- Dynamic in nature, Quick decision making capability, Balanced system performance and scheduling overhead, Stability, Scalability, Fault tolerance, Fairness of service. Q2. Explain the issues in Designing Load-balancing algorithms. 15 Ans: The issues in Designing Load-balancing algorithms are - Load estimation policy, Process transfer policy, Location policy, Priority assignment policy, Migration limiting policy. Q3. List the functions of resource manager of a distributed system. Ans: Resource manager of a distributed system schedules the processes to optimize combination of resources usage, response time, network congestion, scheduling overhead. www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

REFERENCES 22  M.R. Bhujade, “Parallel Computing”, 2nd edition, New Age International Publishers 2009.  Andrew S. Tanenbaum and Maarten Van Steen, “Distributed Systems: Principles and Paradigms, 2nd edition, Pearson Education, Inc., 2007, ISBN: 0-13-239227-5.  George Coulouris, Jean Dollimore, Tim Kindberg, “Distributed Systems: Concepts and Design” (4th Edition), Addison Wesley/Pearson Education. Pradeep K Sinha, “Distributed Operating Systems: Concepts and design”, IEEE computer society press www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL

23 THANK YOU www.cuidol.in Unit-6 (MCA635) All right are reserved with CU-IDOL