Task Scheduling in Distributed Systems : Model and prototype

Distributed systems is a collection of entities that cooperate to solve a problem that otherwise a single entity would not be able to solve. The use of heavy algorithms has been growing and therefore have distributed computation systems arisen. To make the best use of a distributed computation system task allocation and task scheduling algorithms has been developed. Task allocation is the process of allocating tasks to the best suitable processors of the system while task scheduling is used to determine the execution order of tasks. In some cases task scheduling also incorporate allocation process. A task is the smallest entity that can be scheduled and can be a process or a thread. Tasks are often bunched together as jobs which can include an arbitrary number of tasks. In this thesis has a general model and prototype been created which can be used in a variety of distributed systems and handle a wide range of tasks which includes tasks with execution order and deadlines. The model has been created using the best methods examined during a literature study which include the use of batch sampling, late binding and fair scheduling. A bare bone prototype has been created from the model which includes some core functionality and has been tested in regards to throughput and how balanced load it is. The throughput tests showed that the model does not lose throughput when tasks with execution order is scheduled and the load test showed that the system is fairly balanced. An evaluation of the model has been performed which shows that it works well in distributed systems and can handle a variety of tasks. The prototype has been has been tested in a small test environment which shows that it works well in smaller environments with similar requirements.Ett distribuerat system är en samling av enheter som arbetar tillsammans för att lösa ett problem som en ensam enhet inte skulle kunna lösa själv. Användningen av tunga algoritmer har ökat och därför har distribuerade beräkningssystem skapats. För att ta vara på de resurser som finns i de distribuerade beräkningssystemen har uppgiftsallokering och schemaläggningsalgoritmer skapats. Uppgiftsallokering försöker allokera uppgifter till de bästa processorerna och schemaläggning bestämmer körordningen på uppgifterna. I vissa fall hanterar schemaläggningen också allokeringen av uppgifter. En uppgift är den minsta enhet som kan schemaläggas och kan vara processer eller trådar. Uppgifter kan läggas ihop till ett så kallat jobb som innehåller en mängd uppgifter. I denna uppsatts har en generell modell och prototyp skapats som kan användas i en mängd olika distribuerade system och kan hantera de olika egenskaper som uppgifter kan innehålla. Dessa egenskaper kan till exempel vara körordning eller deadline. Den framtagna modellen har skapats utifrån de bästa granskade metoderna under en literaturstudie. Den framtagna modellen har skapats utifrån de schemaläggnings-metoder som granskats vid edn literaturstudie och visat sig ha de bästa egenskaperna, dvs går att anpassa till en generall lösning, skalbara, felsäkra och snabba. Några av de använda metoderna innefattar batch sampling, late binding och fair scheduling. Utifrån den skapade modellen har en prototyp implementerats som innehåller de mest väsentliga delarna av modellen. Prototypen har testats genom att mäta genomströmmningen av uppgifter samt hur bra fördelad är uppgifterna mellan arbetarna av systemet. Testet för genomströmmningen visade att när uppgifter med körordning används sänks inte genomströmmningen av uppgifter och lastbalanseringen visade att arbetarna har ungefär lika stor last genom körningen. En evaluering av modellen har utförts som visa att modellen fungerar bra i distribuerade system samt kan hantera en mängd olika uppgifter. Prototypen har testats i en liten miljö och visats fungera bra för mindre miljöer med liknande behov