Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS-350 - Fundamentals of Computing Systems

Homework Assignment #5

Problem 1

Consider the mix of jobs with parameters described in Table 1. Assume that ties (if any) are broken by scheduling jobs with lower ID first. Compute the following:

a) Assume that the system is idle at time 0, and that all the jobs in Table 1 also arrived at time 0 (instead of what reported in the table). In this case, what would be the time required by a generic work-conserving scheduler to complete all the jobs? Motivate your answer.

b) With the same assumptions as in Question a), propose a scheduler that would complete processing of all the jobs at a later time than what computed above.

c) From now on, consider the job parameters as given in Table 1. Draw the schedule produced by SRT. Try to use the same notation as in the lecture notes.

d) Draw the schedule produced by HSN. Try to use the same notation as in the lecture notes.

e) Draw the schedule produced by SJN. Try to use the same notation as in the lecture notes.

f) Draw the schedule produced by Round-Robin. Try to use the same notation as in the lecture notes.

g) Which algorithm achieves better performance in terms of average response time? Motivate your answer.

h) If each preemption inreoduced an overhead of 0.01 time units, what would be the total preemption overhead for the scheduling strategies (SRT, HSN, SJN, RR) considered above?

Problem 2

Consider the schedule in Figure 1 and answer the following questions. The “dot” in the figure indicates completion of a job, while an up-arrow indicates arrival.

a) What are the parameters (e.g. arrival time, length) of the jobs in this system. Use the task/job notation provided in class and in the notes.

b) What scheduling algorithm is being used to produce the schedule in Figure 1? Motivate your answer.

c) Provide a step-by-step explanation of the decision made by the scheduler at time 11.

d) Use the same job parameters derived above and plot the schedule that would be produced by SJN on the same job parameters.

e) Assume once again SJN scheduling and that there is no more arrival of jobs for tasks 2 through 5. Consider instead that the arrival pattern of jobs of task 1 will repeat every T time units — i.e., every T time units, we wuld see the same release pattern of j1,1 and j1,2 that we see starting from time 0. What is the largest T that would cause starvation for j5?

Problem 3

A single-cpu web server is trying to be smart about the way it schedules processing for incoming page requests. The web server is running a sharing hosting service with three websites deployed on it. As page requests come in for the three websites, the web server classifies the requests depending on the page they target. It then tries to schedule the pending requests for each of the websites using Shortest Job Next. But the server does not know the future! This means that it needs to estimate, for each class of requests, how long the next request will last based on what it observed in the past.

Table 2 reports the ground truth on the actual runtime of a series of 5 requests per website and their arrival times. Remeber: the webserver scheduler does not know the exact length of a job reported in the table until the job has completed. Also assume that when the scheduler has no knowledge of the requests at all, it will default to schedule a request for website 1 first, then website 2, and so on. This is also the priority ordering in case of any tie. Remeber also that if at any time there is more than one ready request for the same website that is ready, the FIFO ordering is followed.

a) Assume an impossible webserver that is able to foresee the future (the oracle server!), what would be the order in which the various requests are processed? Produce a time plot of the resulting schedule that goes until the last request has been completed.

b) Now consider a realistic scheduler without clairvoyance capabilities. What is the resulting schedule if the server tries to predict the length of the next request directed to each website using an exponentially weighted moving average with parameter α = 0.5? Show your work where it is clear at every step of the way how the scheduler it making predictions and taking decisions.

c) Compare now the two schedules produced above. Did not knowing the future caused a performance degradation in terms of average response time?

d) Once again compare the two schedules and focus on the website that statistically receives shorter-lived requests. How was the slowdown of the requests for this website impacted by the scheduler’s inability to predict the future?

e) Without repeating the steps above, and focusing only on the difference between predictions and ground truth (prediction error), can we find a better value for α? Analyze the average prediction error for the case considered above, and then for 0.3 and 0.8. Which one of the three cases you expect to be in closer match with what you drew in Part a)

Problem 4

Code: In this problem you will write two functions to work with MD5 hashes. The first function takes a number and computes a MD5 hash. The second function takes a MD5 hash and returns the number that, when hashed, produces the hash in input.

a) Start by writing a Java class namely Hash.java that implements number hashing logic. The class should have a method with the following prototype: String hash(int to_hash), produces the MD5 hash string for the integer number provided in input. Internally, the integer should be converted to a string that represents the number in decimal format, and then hashed using the MD5 cryptographic hash.

For instance, the return value of hash(12345) should be “827ccb0eea8a706c4c34a16891f84e7b”. You are allowed to use Java libraries for the computation of MD5 hashes.

Next, write a Java class namely UnHash.java that implements number de-hashing (a.k.a. hash cracking) logic. The class should have a method with the following prototype: int unhash(String to_unhash), produces an integer from a hash string in input. The integer produced in output should be such that its MD5 hash corresponds to the hash string to_unhash.

For instance, the return value of unhash(‘‘01cfcd4f6b8770febfb40cb906715822’’) should be 54321. You are allowed to use Java libraries for the computation of MD5 hashes.

Apart from implementing the unhash(...) method, the class should also include a public static void main(String [] args) function. The main(...) function should accept 1 parameter from the calling environment. The parameter is a string that contains an hash string to crack.

It is responsibility of the main(...) function to internally invoke the implemented unhash(...) function only once and print its result in decimal format.

b) Using the code written in the previous part, work on being able to crack a list of MD5 hashes from a file. For this part, write a Java class called Dispatcher.java. The input data (list of hashes to crack) is given in a file. The path to the file is passed as the only parameter by the calling environment. The input file is structured as a list of MD5 hashes to crack, one per line, with each line terminated with a newline (\n) character.

It is the job of the dispatcher to (1) read the input file; (2) invoke the unhash(...) procedure written for the first part for each of the hashes in the input file. The result of each of the unhash operations, i.e. the cracked hashes, should be printed in output, with a single line per decoded hash. Apart from the list of decoded hashes, nothing else should be printed in output.

Submission Instructions: in order to submit this homework, please follow the instructions below for exercises and code.

The solutions for Problem 1-3 should be provided in PDF format, placed inside a single PDF file named hw5.pdf and submitted via Gradescope. Follow the instructions on the class syllabus if you have not received an invitation to join the Gradescope page for this class. You can perform a partial submission before the deadline, and a second late submission before the late submission deadline.

The solution for Problem 4 should be provided in the form of Java source code. To submit your code, place all the .java files inside a compressed folder named hw5.zip. Make sure they compile and run cor-rectly according to the provided instructions. The first round of grading will be done by running your code. Use CodeBuddy to submit the entire hw5.zip archive at https://cs-people.bu.edu/rmancuso/courses/cs350-fa21/scores.php?hw=hw5. You can submit your homework multiple times until the deadline. Only your most recently updated version will be graded. You will be given instructions on Piazza on how to interpret the feedback on the correctness of your code before the deadline.