Disk scheduling

[Toyakoyo]

Hello,everyone!

I have been suffer from a problem as tile says.

I have no idea to solve this problem.

I hope anyone who can help me! Thanks.

The following is the question:

In this project, you are going to invent a minimal seek-distance disk scheduler under a given QOS constraint t. We can formulate this problem into a one-to-one mapping problem as follows. Assume that the total number of disk references is N. There are two sequences, the requested sequence, {A1, A2, …, AN}, and the scheduled sequence, {R1, R2, …, RN}. In the requested sequence, the i-th element Ai represents the disk address of the i-th requested access. In the scheduled sequence, the j-th element Rj represents that the j-th scheduled access is the Rj-th requested access in the requested sequence. According to the definition of Rj as well as the given QOS constraint t,both 1≤Rj≤N and j-t≤Rj≤j+t must be satisfied for all 1≤j≤N. The objective function of the minimal seek-distance disk scheduler is:

                    min{Σ(ARj -AR(j-1)},for j=1,to j=N;
                    R0=0,AR0=A0=0;

There are two inputs in your program, the requested sequence (ex: "access.in") and the QOS constraint t. There are also two outputs in your program, the scheduled sequence ("access.out") and the total seek-distance.

Can anyone help me? Thanks.
If you can not find the min distance,you can find the next min distance.
Not always the min distance.

[rubberman]

Time to visit your teaching assistant for some help I think. This is a variant of an elevator seek algorithm, so you might want to look at this:

http://en.wikipedia.org/wiki/Elevator_algorithm

and this:

http://en.wikipedia.org/wiki/Disk_scheduling

[Toyakoyo]

Thanks.
But I still can not to figure out the solution to this problem!
QQ

[rubberman]

That's why it's called school work - it is supposed to be work! :-) Since I'm not getting your degree, why should I spend an inordinate amount of time to do the grunt work? The math is simple enough, and you need to think through the problem, looking at it logically - you have a disc that you need to seek and grab data when you are presented with a number of logical sectors that some application or other wants to access. Reordering the sectors to read in the most efficient manner based upon where you are at the moment is the first part of the problem. Then you need to modify that algorithm to apply quality-of-service metrics that should be available from the application along with the sectors it wants. Not simple, but not difficult either.

So, putting on my "Mister Professor" hat, what is your first step?

[Toyakoyo]

Do you mean that I still can use elevator algorithm ?
I want to find the smallest number in the first section.
So I can search the no-decreasing numbers.
But if I confront the number is at the edge of the section, how can I choose the next number?
Thanks.

[rubberman]

What if your read heads are already at the high end of the device? Why seek back to the beginning to start reading? You need to factor that into the algorithm, which is what elevator seeking does. At the root, this is an elevator algorithm, but it needs to be modified by the QOS data that you get, so as to give priority to the higher QOS data, but not starve the other data.