Chapter 13 Disk Storage Basic File Structures and Hashing CHAPTER 13 DISK STORAGE BASIC FILE STRUCTURES AND HASHING Answers to Selected Exercises 13 23 Consider a disk with the following characteristics these are not parameters of any particular disk unit block size B 512 bytes interblock gap size G 128 bytes number of blocks per track 20 number of tracks per surface 400 A disk pack consists of 15 double sided disks a What is the total capacity of a track and what is its useful capacity excluding interblock gaps b How many cylinders are there c What is the total capacity and the useful capacity of a cylinder d What is the total capacity and the useful capacity of a disk pack e Suppose the disk drive rotates the disk pack at a speed of 2400 rpm revolutions per minute what is the transfer rate in bytes msec and the block transfer time btt in msec What is the average rotational delay rd in msec What is the bulk transfer rate see Appendix B f Suppose the average seek time is 30 msec How much time does it take on the average in msec to locate and transfer a single block given its block address g Calculate the average time it would take to transfer 20 random blocks and compare it with the time it would take to transfer 20 consecutive blocks using double buffering to save seek time and rotational delay Answer a Total track size 20 512 128 12800 bytes 12 8 Kbytes Useful capacity of a track 20 512 10240 bytes 10 24 Kbytes b Number of cylinders number of tracks 400 c Total cylinder capacity 15 2 20 512 128 384000 bytes 384 Kbytes Useful cylinder capacity 15 2 20 512 307200 bytes 307 2 Kbytes d Total capacity of a disk pack 15 2 400 20 512 128 153600000 bytes 153 6 Mbytes Useful capacity of a disk pack 15 2 400 20 512 122 88 Mbytes e Transfer rate tr total track size in bytes time for one disk revolution in msec tr 12800 60 1000 2400 12800 25 512 bytes msec block transfer time btt B tr 512 512 1 msec average rotational delay rd time for one disk revolution in msec 2 25 2 12 5 msec bulk transfer rate btr tr B B G 512 512 640 409 6 bytes msec f average time to locate and transfer a block s rd btt 30 12 5 1 43 5 msec Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley 1 Chapter 13 Disk Storage Basic File Structures and Hashing 2 g time to transfer 20 random blocks 20 s rd btt 20 43 5 870 msec time to transfer 20 consecutive blocks using double buffering s rd 20 btt 30 12 5 20 1 62 5 msec a more accurate estimate of the latter can be calculated using the bulk transfer rate as follows time to transfer 20 consecutive blocks using double buffering s rd 20 B btr 30 12 5 10240 409 6 42 5 25 67 5 msec 13 24 A file has r 20000 STUDENT records of fixed length Each record has the following fields NAME 30 bytes SSN 9 bytes ADDRESS 40 bytes PHONE 9 bytes BIRTHDATE 8 bytes SEX 1 byte MAJORDEPTCODE 4 bytes MINORDEPTCODE 4 bytes CLASSCODE 4 bytes integer and DEGREEPROGRAM 3 bytes An additional byte is used as a deletion marker The file is stored on the disk whose parameters are given in Exercise 4 18 a Calculate the record size R in bytes b Calculate the blocking factor bfr and the number of file blocks b assuming an unspanned organization c Calculate the average time it takes to find a record by doing a linear search on the file if i the file blocks are stored contiguously and double buffering is used and ii the file blocks are not stored contiguously d Assume the file is ordered by SSN calculate the time it takes to search for a record given its SSN value by doing a binary search Answer a R 30 9 40 9 8 1 4 4 4 3 1 113 bytes b bfr floor B R floor 512 113 4 records per block b ceiling r bfr ceiling 20000 4 5000 blocks c For linear search we search on average half the file blocks 5000 2 2500 blocks i If the blocks are stored consecutively and double buffering is used the time to read 2500 consecutive blocks s rd 2500 B btr 30 12 5 2500 512 409 6 3167 5 msec 3 1675 sec a less accurate estimate is s rd 2500 btt 30 12 5 2500 1 2542 5 msec ii If the blocks are scattered over the disk a seek is needed for each block so the time is 2500 s rd btt 2500 30 12 5 1 108750 msec 108 75 sec d For binary search the time to search for a record is estimated as ceiling log 2 b s rd btt ceiling log 2 5000 30 12 5 1 13 43 5 565 5 msec 0 5655 sec 13 25 Suppose only 80 of the STUDENT records from Exercise 13 24 have a value for PHONE 85 for MAJORDEPTCODE 15 for MINORDEPTCODE and 90 for DEGREEPROGRAM and we use a variable length record file Each record has a 1 byte field type for each field occurring in the record plus the 1 byte deletion marker and a 1 byte end ofrecord marker Suppose we use a spanned record organization where each block has a 5 byte pointer to the next block this space is not used for record storage Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Chapter 13 Disk Storage Basic File Structures and Hashing 3 a Calculate the average record length R in bytes b Calculate the number of blocks needed for the file Answer a Assuming that every field has a 1 byte field type and that the fields not mentioned above NAME SSN ADDRESS BIRTHDATE SEX CLASSCODE have values in every record we need the following number of bytes for these fields in each record plus 1 byte for the deletion marker and 1 byte for the end of record marker R fixed 30 1 9 1 40 1 8 1 1 1 4 1 1 1 100 bytes For the fields PHONE MAJORDEPTCODE MINORDEPTCODE DEGREEPROGRAM the average number of bytes per record is R variable 9 1 0 8 4 1 0 85 4 1 0 15 3 1 0 9 8 4 25 0 75 3 6 16 6 bytes The average record size R R fixed R variable 100 16 6 116 6 bytes The total bytes needed for the whole file r R 20000 116 6 2332000 bytes b Using a spanned record organization with a 5 byte pointer at the end of each block the bytes available in each block are B 5 512 5 507 bytes The number of blocks needed for the file are b ceiling r R B 5 ceiling 2332000 507 4600 blocks compare this with …