Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Disk Storage Access Exercises. Show all posts
Showing posts with label Disk Storage Access Exercises. Show all posts

## Buffer pages required for external sorting of a file in database

Question:
Let us suppose that you have a file with 8500 pages and 3 available buffer pages. If you use external sorting to sort the above said file, answer the following questions;
a) How many runs will you produce in the first pass?
b) To sort the entire file, how many passes do you need?
c) How much is involved in terms of I/O cost to sort the file?
d) If you like to sort the file in just two passes, then what is the number of buffer pages you need?

Solution:
a) If Nf is the number of file pages and Nb is the number of available buffer pages then the first pass requires Nf/Nb [ceiling(Nf/Nb)] sorted runs.
For our case,
Number of file pages, Nf = 8500
Number of available buffer pages, Nb = 3
The number of sorted runs in the first pass = ⌈8500/3⌉ = 2834 runs

b) The number of passes required to sort the entire file can be calculated using the equation ⌈logNb-1Nf/Nb⌉⌉+1.
Number of passes to sort complete file = ⌈log2⌈8500/3⌉⌉+1
= ⌈log22834⌉+1 = 9 passes

c) Since each page is read and written once per pass, the total number of page I/Os for sorting the file is 2 * Nf * (#passes):
Total I/O cost for sorting the file = 2 * 8500 * 9 = 1,53,000

d) In Pass 0, Nf/Nbruns are produced. In Pass 1, we must be able to merge this many runs; i.e., Nb − 1 ≥ Nf/Nb. This implies that Nb must at least be large enough to satisfy Nb * (Nb − 1) ≥ Nf; this can be used to guess at Nb, and the guess must be validated by checking the first inequality. Thus;
with 8500 pages in the file, Nb = 93 satisfies both inequalities, but Nb = 92 does not. So we need 93 buffer pages to sort the entire file in just two passes.

[Note: to find the value of Nb, factorize the equation Nb * (Nb-1) = Nf which can be written as a quadratic equation Nb2-Nb-Nf = 0. The equation to be solved is Nb2 - Nb - 8500 = 0]

*********

buffer pages required for external sorting
number of passes required to complete sorting of a file using external sorting
external sorting technique in database
number of runs required for each pass in external sorting
I/O cost involved in sorting the entire file

## Find the number of disk blocks in a given hard disk in DBMS data storage

Question:
Following are the characteristics of a hard disk; Sector size of 512 bytes, 16 sectors per track, 16384 tracks per surface, 4 double sided platter, and 4096 bytes per block. Find the number of blocks in that disk.

Solution:
Let us find the total capacity of given disk in bytes.
A track has 16 sectors each of which is 512 bytes in size.
Capacity of a track      = Sector size * Number of sectors
= 512 * 16 = 8192 bytes.
There are 16384 tracks in a surface of a disk platter.
Capacity of one surface of disk platter = No. of tracks * Capacity of a track
= 16384 * 8192 = 134217728 bytes
Capacity of one double sided platter = 134217728 * 2 (2 sides per disk)
= 268435456 bytes
There are 4 double sided platters.
Capacity of the hard disk = Capacity of one disk platter * No. of disk platters
= 268435456 * 4
= 1073741824 bytes
It is given that the block size is 4096.
The number of blocks = (capacity of the hard disk) / (block size)
= 1073741824/4096 = 262144 blocks

The hard disk with the given characteristics will have 262144 blocks.

*************

find number of blocks in a hard disk drive
calculate the size of hard disk in bytes
find the capacity of a disk platter

## Saturday, February 10, 2018

### Find the disk capacity, rotational latency, and number of cylinders, how to calculate the disk capacity, how to calculate the number of cylinders if number of tracks are known, how to compute the rotational latency

Question:
Consider a disk with a sector size of 512 bytes, 1000 tracks per surface, 25 sectors per track, 5 double-sided platters, and average seek time of 10 msec. Choose the correct answer for the following;
(i) capacity of tracks in bytes,
(ii) number of cylinders the disk has,
(iii) the average rotational latency if disk rotates at 5400 rpm.
(a) 12.5 K, 1000, 5.5 msec
(b) 25 K, 2000, 11 msec
(c) 12.5 K, 1000, 11 msec
(d) 25 K, 1000, 100 msec

(a) 12.5 K, 1000, 5.5 msec

Given,
Sector size (minimum storage unit of a hard drive) – 512 bytes
Number of double sided disk platters - 5
(One can read/write on both sides in a Double sided platters unlike DVD for example)
Number of tracks per each side of each disk platter – 1000
Number of sectors per track – 25
Average seek time – 10 msec
The time needed for moving head of a disk drive from one track to another is the seek time. The average of many seeks is average seek time.
(i) Capacity of track can be calculated as follows;
Capacity of track = bytes/track = bytes/sector * sectors/track
= 512 bytes/sector * 25 sectors/track = 12800 bytes
= 12800/1024 KB = 12.5 KB

(ii) The number of cylinders is the same as the number of tracks on each platter.
Number of cylinders = Number of tracks = 1000

(iii) Maximum rotational delay can be calculated as follows;
Maximum rotational delay = (1/rpm) * 60
= (1/5400) * 60 = 0.011 seconds or 11 msec
Average rotational latency is half of the rotation time, ie., 5.5 msec

## Find the number of records and record size for storing data in one disk block, How to calculate block size, How to calculate record size, calculate the number of records fit in one disk block in database management system

### Question:

6. Suppose blocks of 1024 bytes are used to store variable-length records. The fixed part of the block header is 24 bytes, and includes a count of the number of records. In addition, the header contains a 4-byte pointer (offset) to each record in the block. The first record is placed at the end of the block, the second record starts where the first one ends, and so on. The size of each record is not stored explicitly, since the size can be computed from the pointers.
(i) How many records of size 50 bytes could we fully fit (no spanning) in such a block? (The block is designed to hold variable size records, but these records by coincidence happen to be all the same size.)
(ii) Suppose we want to store 20 records in the block, all of the same fixed size. What is the size of such records?
(iii) Now assume the block layout is changed to accommodate only fixed size records. In this case, the block header is still 24 bytes and contains the common length of the records in the block.
How many records of size 50 bytes could we fully fit in such a block?

(a) 20 records, 50 bytes, 20 records
(b) 18 records, 46 bytes, 20 records
(c) 20 records, 46 bytes, 25 records
(d) 50 records, 50 bytes, 20 records

(b) 18 records, 46 bytes, 20 records

(i) Given,
Block size – 1024 bytes
Block header size – 24 bytes
Record size – 50 bytes
Pointer to each record – 4 bytes
Number of records = floor {Block size / records} ----- Eq. 1
But in the given case, we need to consider the block size after deducting the header size. And for each record we need to add 4 bytes pointer size because it is given that pointer for each record. Hence Eq 1 is now as follows;
Number of records = floor {(Block size – Header size) / (Record size + Pointer size)}
Number of records = floor { (1024 – 24) / (50 + 4)} = 18 records

(ii) For finding the size of record, we need to find the size left with us in each block. When we deduce the block header size and the size required for 20 pointers from block size, what we get is the size completely available for storing records.
(Block size – Header size – 4*20) will give us the available block space
Number of records = floor { (1024 – 24 – 4 * 20) / x}
20 = floor { (1024 – 24 – 4 * 20) / x}
x = floor { (1024 – 24 – 4 * 20) / 20} = floor{980/20} = 46 bytes

(iii) In this case, the record size becomes fixed. Hence, we do not need pointers to each record. The extra memory 4 bytes can be saved. The number of records can be calculated using Eq. 1 as follows;
Number of records = floor {(Block size – Header size) / Record size}
Number of records = floor { (1024 – 24) / 50} = 20 records

## Featured Content

### Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery