Return to Homework Assignments
Homework Assignment #1
Due: October 15, 1999
- Consider the Hybrid Partition algorithm for file allocation in parallel
disk arrays discussed in class. The algorithm assumes that for a given
batch of files to be allocated the heat and service time of each file is
known. Provide a dynamic version of this algorithm which, similar to the
greedy algorithm, uses only the information about the heat of the files
which have been allocated already and for which statistics have been collected
already. You should still assume that the requests are for entire files and
hence the service times of the files to be allocated are known in advance.
- An alternative to performing dynamic load balancing via disk cooling is to
perform periodically a rebalancing operation whereby a number of extents (files)
are reallocated at the same time. The objective of such an algorithm is to
minimize the amount of data moved and to obtain a new load balance as good as
possible. Hint: make use of the greedy heuristic in reallocating the data.
- A problem with LH* is that whenever a split needs to be executed all the
records at a server (bucket) need to be examined in order to determine which
stay at the current server and which have to be moved to a new server. You are
to propose an improved scheme which should help solve this problem. You may
assume that each bucket at a server fits in random access memory. The objective
is to design an internal data structure at each server which can be combined
with the global (distributed) file structure. Illustrate your scheme with
an example.
THURS Oct 7, 1999