ITEC801 Introduction to Distributed Systems

This assessment item is to be an individual work and accounts for 10% of the total mark (100) of the unit. Your task in this stage is to analyse and compare three simple scheduling algorithms (FF, BF and WF) with respect to the following performance metrics (but not limited to)

1. (total) cost

2. Resource utilisation

3. Time (waiting time and execution time and/or turnaround time) The three basic scheduling algorithms are based on memory allocation policies in operating systems (i.e., FF, BF and WF). They have already been implemented in ds-client. In order to use a particular algorithm, you need to specify the algorithm as a command line argument of dsclient, e.g., ./ds-client -a ff for First-Fit. Your analysis and comparison can be conducted based on simulation logs/results. To help conduct this, you have been provided with sample configurations. However, your analysis/comparison should not be limited to simulation results with them. In other words, you are free to make changes to supplied ones and/or create new ones. “Suggested” headings Student details: Name and SID Introduction (up to 1 page): a short introduction of your report including the aim(s) of this report and brief background on the topic of this assignment. This might include a short description of

1. Brief introduction of job/resource scheduling including its importance in distributed systems (e.g., data centres),

2. Performance metrics, i.e., how the quality of scheduling algorithms (or schedules) can be measured Scheduling algorithms (up to 3 pages): review/analyse/compare FF, BF and WF algorithms with respect to 1. Algorithm design

2. Pros and cons of three algorithms in a tabular form

3. Performance Conclusion (a half page): you may summarise the report discussing what can be done to improve. References (1/3 pages) Deliverables The submission is to be a single compressed file containing the following.

1. Your report 2. Everything necessary to run simulations to reproduce your results as follows: a. Configuration files b. .jobs files c. Simulation log files * ENSURE the name of each .jobs and the name of simulation log file match the corresponding configuration file, e.g., ds-config02.jobs and ds-config02- ff.log for ds-config02.xml with First-Fit (ff). The concise description of each of the three algorithms in the form of a pseudo-code is shown below. • First-Fit (FF) For a given job ji, 1. Obtain server state information 2. For each server type i, si , from the smallest to the largest

3. For each server j, si,j of server type si, from 0 to limit - 1 // j is server ID

4. If server si,j has sufficient available resources to run job ji then

5. Return si,j

6. End If

7. End For

8. End For

9. Return the first Active server with sufficient initial resource capacity to run job ji • Best-Fit (BF) For a given job ji,

1. Set bestFit and minAvail to very large number (e.g., INT_MAX)

2. Obtain server state information

3. For each server type i, si , in the order appear in system.xml

4. For each server j, si,j of server type si, from 0 to limit - 1

5. If server si,j has sufficient available resources to run job ji then

6. Calculate the fitness value fsi,j,ji

7. If fsi,j,ji < bestFit or (fsi,j,ji == bestFit and available time of si,j <minAvailTime) then

8. Set bestFit to fsi,j, ji

9. Set minAvail to available time of si,j

10. End If

11. End If

12. End For

13. End For

14. If bestFit is found then

15. Return the server with bestFit

16. Else

17. Return the best-fit Active server based on initial resource capacity

18. End If • Worst-Fit (WF) For a given job ji,

1. Set worstFit and altFit to very small number (e.g., INT_MIN)

2. Obtain server state information

3. For each server type i, si , in the order appear in system.xml

4. For each server j, si,j of server type si, from 0 to limit - 1

5. If server si,j has sufficient resources readily available to run job ji then

6. Calculate the fitness value fsi,j,ji

7. If fsi,j,ji > worstFit and si,j is immediately available then

8. Set worstFit to fsi,j,ji

9. Else If fsi,j, ji > altFit and si,j is available in a short definite amount of time then

10. Set altFit to fsi,j, ji

11. End If

12. End If

13. End For

14. End For

15. If worstFit is found then Introduction to Distributed Systems    

16. Return the server with worstFit

17. Else If altFit is found then

18. Return the server with altFit

19. Else

20. Return the worst-fit Active server based on initial resource capacity

21. End If * The fitness value of a job to a server is defined as the difference between the number of cores the job requires and that in the server. Note that when ‘RESC All’ is used, the available time of an Active server is always -1 regardless of its available resource capacity. In this case, if the server has sufficient available resources, -1 is interpreted as the current time, i.e., the server is available immediately. Marking scheme (in percentage) 85 to 100 Work in this band presents a full and comprehensive account of all requirements outlined above. In particular, the thorough, accurate and clear analysis and comparison of three algorithms should be evident in the report based on simulation results with a comprehensive set of test cases. All deliverables and formatting required, including naming convention of files, must be present complying with instructions in Stage 2 guide. 75 to 84 Work in this band presents a clear account of all requirements outlined above. In particular, the clear and comprehensive analysis and comparison of three algorithms should be evident in the report based on simulation results with a set of representative test cases. All deliverables and formatting required, including naming convention of files, must be present complying with instructions in Stage 2 guide. 65 to 74 Work in this band presents the good understanding of three algorithms with solid analysis based on a set of test cases. All deliverables and formatting required, including naming convention of files, must be present complying with instructions in Stage 2 guide. 50 to 64 Work in this band presents the clear understanding of three algorithms with appropriate analysis. All deliverables and formatting required, including naming convention of files, must be present complying with instructions in Stage 2 guide.