Java Reference
In-Depth Information
are to the same sector). Carefully define under what conditions the batch
method is more efficient than the interactive method.
8.16 Assume that a virtual memory is managed using a buffer pool. The buffer
pool contains five buffers and each buffer stores one block of data. Memory
accesses are by block ID. Assume the following series of memory accesses
takes place:
5 2 5 12 3 6 5 9 3 2 4 1 5 9 8 15 3 7 2 5 9 10 4 6 8 5
For each of the following buffer pool replacement strategies, show the con-
tents of the buffer pool at the end of the series, and indicate how many times
a block was found in the buffer pool (instead of being read into memory).
Assume that the buffer pool is initially empty.
(a) First-in, first out.
(b) Least frequently used (with counts kept only for blocks currently in
memory, counts for a page are lost when that page is removed, and the
oldest item with the smallest count is removed when there is a tie).
(c) Least frequently used (with counts kept for all blocks, and the oldest
item with the smallest count is removed when there is a tie).
(d) Least recently used.
(e) Most recently used (replace the block that was most recently accessed).
8.17 Suppose that a record is 32 bytes, a block is 1024 bytes (thus, there are
32 records per block), and that working memory is 1MB (there is also addi-
tional space available for I/O buffers, program variables, etc.). What is the
expected size for the largest file that can be merged using replacement selec-
tion followed by a single pass of multiway merge? Explain how you got your
answer.
8.18 Assume that working memory size is 256KB broken into blocks of 8192
bytes (there is also additional space available for I/O buffers, program vari-
ables, etc.). What is the expected size for the largest file that can be merged
using replacement selection followed by two passes of multiway merge? Ex-
plain how you got your answer.
8.19 Prove or disprove the following proposition: Given space in memory for a
heap of M records, replacement selection will completely sort a file if no
record in the file is preceded by M or more keys of greater value.
8.20 Imagine a database containing ten million records, with each record being
100 bytes long. Provide an estimate of the time it would take (in seconds) to
sort the database on a typical desktop or laptop computer.
8.21 Assume that a company has a computer configuration satisfactory for pro-
cessing their monthly payroll. Further assume that the bottleneck in payroll
processing is a sorting operation on all of the employee records, and that
