Consider a disk with an average seek time of 10ms, average rotational delay of 5ms, and a transfer time of 1ms for a 4K page. Assume that the cost of reading/writing a page is the sum of these values (i.e., 16ms) unless a sequence of pages is read/written. In this case the cost is the average seek time plus the average rotational delay (to find the first page in the sequence) plus 1ms per page (to transfer data). You are given 320 buffer pages and asked to sort a file with 10,000,000 pages.
1. Why is it a bad idea to use the 320 pages to support virtual memory, that is, to ‘new' 10,000,000*4K bytes of memory, and to use an in-memory sorting algorithm such as Quicksort?
2. Assume that you begin by creating sorted runs of 320 pages each in the first pass. Evaluate the cost of the following approaches for the subsequent merging passes:
(a) Do 319-way merges.
(b) Create 256 ‘input' buffers of 1 page each, create an ‘output' buffer of 64 pages, and do 256-way merges.
(c) Create 16 ‘input' buffers of 16 pages each, create an ‘output' buffer of 64 pages, and do 16-way merges.
(d) Create eight ‘input' buffers of 32 pages each, create an ‘output' buffer of 64 pages, and do eight-way merges.
(e) Create four ‘input' buffers of 64 pages each, create an ‘output' buffer of 64 pages, and do four-way merges.