A computer operating system stores files on a hard disk. Five large files of siz

Question

A computer operating system stores files on a hard disk. Five large files of sizes 18, 23, 12, 125, and 45 MB are to be stored. Contiguous blocks of storage are available with size 25, 73, 38, and 156 MB, and each file must be stored in one contiguous block. In this problem we will explore an integer programming algorithm to assign files to storage blocks.

(a) In order to reserve large contiguous blocks of storage for future use, we want to store each file in the smallest available block large enough to hold the file. Define the cost of storing file i in block j to be the size of block j, and determine the assignment of files to blocks that minimizes the total cost. Use the five-step method, and model as an integer programming problem.

(b) Suppose that the 12 MB file expands to 19 MB. How does this effect the optimal solution found in part (a)? How much can this 12 MB file expand before the optimal solution changes?

(c) Suppose that the 18 MB file and the 23 MB file are to be stored in the same block, since they are used by the same program. How does this affect the optimal solution found in part (a)?

(d) One “greedy” algorithm for allocating blocks to files is to place each file in the first available block that is large enough to hold it. Apply this algorithm (by hand) and compare to the results of part (a). Is the IP solution found in part (a) significantly better than the results of the greedy algorithm?

(e) Why not just maximize the size of the largest remaining contiguous block of storage? Can this optimization problem be solved as an IP?

Explanation / Answer

a) using five-step method,

Step1: identifying the problem statement that is file I must be put into block j in such a way that it fits into block j appropriately.

Step2: Analysing the problem statement and trying to make out the in depth analysis of the required Solution to be brought out which here can be referred to as placing the files into contiguous blocks such as to reserve large contiguous blocks of storage for future use.

Step3:Trying to figure out the ways in which various decisions can be made by discussing with the customer or another any other alternative ways of making independent decisions.

Step4: Looking into the various ways in which the problem can be resolved.Here we can have various ways in our problem statement can be solved-

Alternative 1:

1.File with 23 size can be put into storage block with size 25

File with 45mb and 12mb can be put into block with size 73.

File with 125mb and 18mb can be put into 156 block size.

Alternative 2:

File with 12mb size can be put into 25mb block

File with 45mb,18mb can put into block with 73 size

File with 125 mb,23 mb can be put into 156 block size

Step 5: Choosing the best suited alternative,in this case alternative 2 of the above 2 ways is beat suited as large contiguous blocks can be reserved.

b) Even if 12mb file expands to 19mb there would be no much effect on the optimal solution found in part a) as it can fit into the first block with size 25.until and unless the file size exceeds 25mb size ,there would be no effect on the optimal solution.

c)If 18mb and 23mb files are to be put into same block the optimal solution of a) would not be that good to proceed and the entire storage methodology needs to be changed in all blocks.

d) The optimal solution that we found in a) would be similar to the one we arrive when we apply greedy approach as we have put the files into storage blocks in such a way that we are greedy to reserve storage blocks.

e)In terms of any expansions with respect to file size that expands we can go further with maximising the storage block size as per requirement.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.