Java Reference
In-Depth Information
an external sorting algorithm is used. The company's payroll program is so
good that it plans to hire out its services to do payroll processing for other
companies. The president has an offer from a second company with 100
times as many employees. She realizes that her computer is not up to the
job of sorting 100 times as many records in an acceptable amount of time.
Describe what impact each of the following modifications to the computing
system is likely to have in terms of reducing the time required to process the
larger payroll database.
(a) A factor of two speedup to the CPU.
(b) A factor of two speedup to disk I/O time.
(c) A factor of two speedup to main memory access time.
(d) A factor of two increase to main memory size.
8.22 How can the external sorting algorithm described in this chapter be extended
to handle variable-length records?
8.8
Projects
8.1 For a database application, assume it takes 10 ms to read a block from disk,
1 ms to search for a record in a block stored in memory, and that there is
room in memory for a buffer pool of 5 blocks. Requests come in for records,
with the request specifying which block contains the record. If a block is
accessed, there is a 10% probability for each of the next ten requests that the
request will be to the same block. What will be the expected performance
improvement for each of the following modifications to the system?
(a) Get a CPU that is twice as fast.
(b) Get a disk drive that is twice as fast.
(c) Get enough memory to double the buffer pool size.
Write a simulation to analyze this problem.
8.2 Pictures are typically stored as an array, row by row, on disk. Consider the
case where the picture has 16 colors. Thus, each pixel can be represented us-
ing 4 bits. If you allow 8 bits per pixel, no processing is required to unpack
the pixels (because a pixel corresponds to a byte, the lowest level of address-
ing on most machines). If you pack two pixels per byte, space is saved but
the pixels must be unpacked. Which takes more time to read from disk and
access every pixel of the image: 8 bits per pixel, or 4 bits per pixel with
2 pixels per byte? Program both and compare the times.
8.3 Implement a disk-based buffer pool class based on the LRU buffer pool re-
placement strategy. Disk blocks are numbered consecutively from the begin-
ning of the file with the first block numbered as 0. Assume that blocks are
