Algorithm Homework (Java)

CS-350 - Fundamentals of Computing Systems

Homework Assignment #5 Due on October 30, 2018 at 3:30 pm

Prof. Renato Mancuso, Prof. Azer Bestavros

Renato Mancuso Azer Bestavros

1

CS-350 - Fundamentals of Computing Systems::Homework Assignment #5 Problem 1

Job ID Job Length Arrival time

1 9 0

2 4 2

3 7 1

4 5 4

Table 1: Job parameters.

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) The schedule produced by SRT. Try to use the same notation as in the lecture notes.

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

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

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

e) Which algorithm achieves better fairness? Motivate your answer.

2

CS-350 - Fundamentals of Computing Systems::Homework Assignment #5 Problem 2

Request Cylinder ID

R1 61

R2 25

R3 86

R4 65

R5 73

R6 94

R7 55

R8 37

R9 42

Table 2: Parameters of considered disk requests, in order of arrival.

Problem 2

Consider a disk, and a set of operations on disk blocks being requested by a set of applications. Each request

targets a cylinder ID. There are 100 cylinders in the disk, with IDs 0 to 99. For instance, the request (42)

targets cylinder 42, while request (12) targets cylinder 12. The disk head moves upward when moving from

a cylinder with lower ID to a cylinder with higher ID; downward otherwise. At a given point in time, the

requests reported in Table 2 in their order of arrival are in the queue of pending requests, and no further

requests will arrive.

a) Assuming a C-SCAN scheduler, what is the order in which the requests in Table 2 will be served if the

initial position of the disk head is on cylinder 70?

b) A request is considered “ready” if the cylinder ID where the disk head is currently positioned is within

[-5, +5] from the cylinder ID of the considered request. For instance, if the disk head is at cylinder

23, the request (18) is ready. Conversely, request (29) is not ready. Use First-Ready, First-Come-

First-Served (FR-FCFS) to schedule the disk requests. If more than one request is ready, the one with

closest cylinder ID is picked. The initial head position is again 70.

c) Compare the schedules obtained at the previous steps. Which approach yields lower head movement

in this particular case?

d) Assume that it takes 2 time units to complete an operation once the disk head is on the right cylinder,

and that it takes 1 time units to move the disk head by 1 cylinder in any of the directions (e.g. going

from cylinder 50 to cylinder 40 takes 10 time units). At what time will the last request in the schedule

complete under C-SCAN?

3

CS-350 - Fundamentals of Computing Systems::Homework Assignment #5 Problem 3

Problem 3

An autopilot (AP) is comprised of three sense-and-actuate routines for three different subsystems: (i) absolute

position; (ii) attitude; and (iii) way-point navigation. For absolute positioning, the AP needs to receive

and process GPS data that arrives at 10 Hz. Attitude is computed by relying on data from the Inertial

Measurement Unit (IMU) at 100 Hz. Finally, way-point navigation (WPN) needs to recompute a new

trajectory at 20 Hz.

a) Assume that the system scheduler is EDF. Also assume that we want to use third-party software for

IMU and GPS interface. We benchmarked these components and it turns out that: the WCET for

IMU-related processing is 4 ms; and that the WCET for GPS-related processing is 20 ms. What is the

constraint on the processor time for WPN-related computation?

b) You developed your WPN module and computed that it has a WCET of 0.5 ms. You really want to

make sure that your AP does not crash. Would you stick to EDF or switch to RM? Motivate your

answer.

c) Considering the same WPN’s WCET (0.5 ms), you now want to use another third-party library that

is internally structured as a set of tens of periodic tasks. The manufacturer tells you that on your

particular processor, the aggregated utilization of the library’s tasks is 10%. Which system scheduler

would you use? Motivate your answer.

4

CS-350 - Fundamentals of Computing Systems::Homework Assignment #5 Problem 4

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) Write 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.

Apart from implementing the hash(...) 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 the representation in decimal format of

a number to hash.

It is responsibility of the main(...) function to internally invoke the implemented hash(...) function

only once and print its result.

b) 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.

Submission Instructions: in order to submit this homework, please structure your files in the following

way. In a global folder called hw5, create two subfolders with names pdf and src respectively.

The solutions for Problem 1-3 should be provided in PDF format and placed inside the pdf folder. The file

names will be part1.pdf, part2.pdf and part3.pdf. If your solution for a single problem spans through

multiple files, add a suffix to order the various files. For instance, if your solution for Problem 2 is divided

in 3 files, the pdf folder will contain the files part2 1.pdf, part2 2.pdf, and part2 3.pdf.

To submit your code, place all the .java files inside the src folder. Make sure they compile and run correctly

according to the provided instructions. The first round of grading will be done by running your code.

Finally, use gsubmit to submit the entire hw5 directory. You can submit your homework multiple times until

the deadline. Only your most recently updated version will be graded.

5