DOC PREVIEW
UT Dallas CS 6360 - 17th chapter soultion

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 13: Disk Storage, Basic File Structures, and Hashing Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. 1CHAPTER 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 msecChapter 13: Disk Storage, Basic File Structures, and Hashing Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. 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).Chapter 13: Disk Storage, Basic File Structures, and Hashing Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. 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


View Full Document

UT Dallas CS 6360 - 17th chapter soultion

Documents in this Course
Ch22(1)

Ch22(1)

44 pages

Ch21

Ch21

38 pages

Ch19

Ch19

46 pages

Ch18

Ch18

25 pages

Ch17

Ch17

21 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch05

Ch05

34 pages

Ch22

Ch22

45 pages

Ch21

Ch21

38 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch16

Ch16

17 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

34 pages

Ch06

Ch06

43 pages

Ch05

Ch05

34 pages

Ch04

Ch04

39 pages

Ch03(2)

Ch03(2)

36 pages

Ch02

Ch02

33 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

lab-manual

lab-manual

215 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch17

Ch17

25 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch04(1)

Ch04(1)

43 pages

Ch07

Ch07

40 pages

Ch03

Ch03

42 pages

Ch01

Ch01

36 pages

Ch02

Ch02

38 pages

Ch05

Ch05

41 pages

Ch06

Ch06

47 pages

Ch08

Ch08

39 pages

Ch17

Ch17

25 pages

Ch18

Ch18

24 pages

Ch09

Ch09

42 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04(1)

Ch04(1)

43 pages

Ch03

Ch03

42 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Load more
Download 17th chapter soultion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 17th chapter soultion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 17th chapter soultion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?