April 1999
SW204: SOFTWARE AND FILES DESIGN

QUESTION 4

Total Marks: 20 Marks

 Click here to access other questions

GRADE A
Sample student's solutions are indicated in green.
Return to Question 4

 
Randomizing algorithms are routines or programs that compute the address of a record on the basis of its key value.

 
(a) List the two objective of randomizing algorithms. [2]
Objectives of randomizing algorithms
- to produce address for each possible key.
- to produce even distribution and speed of address location.

 
(b) Self-addressing with key conversion is one approach to indirect addressing. Assume a file in which there are 10 records in each block, the number of the first block in the storage area in use is 1500, and the lowest key value in the set is 12000. Given a record with key number 13874, derive its location. [4]
b = ((13874 - 12000)/10 )+ 1500
   = 187r4 +1500
   = 1687 r4                      b = block

p = 4+1 = 5                      p =position

Therefore, they key number 13874 can be found at block 1687 at position 5.

 
(c) Describe four ways of reducing the search time in a indexed sequential file. [8]
Ways to reducing the search time in an indexed sequential file.
  1. Hold highest level index in main memory
    so that long head movement can be prevented and reduced access time.
  2. If highest level index is being too large to be held in main memory, hold highest level index in fast device,
    fixed head disk would improved the speed and there is no contention between cylinder and highest index.
  3. If fast devices are not available, then had it in separate device.
    This can be reduced head contention and improve system performance.
  4. If file is single disk, position it in the center of file area.
    This can prevent long head movement.

 
(d) For each of the following, identify whether the system is in a consistent or an inconsistent state. If the system is in an inconsistent state, explain why this is so, and how the inconsistency may be resolved.
(i)  
Block No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In Use 1 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0
Free 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1

 

 [2]
Inconsistent state
- Block number 2 : missing block where block no. 2 is not occur in either table.
- solution : add to tree list.
- it can caused by crash
- it will be waste of space.

 
(ii)  
Block No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In Use 1 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0
Free 0 0 1 0 2 0 0 0 0 1 1 0 0 0 1 1

 

 [2]
Inconsistent state
- Block no. 4 : Duplicate block in tree list.
- where block no. 4 occur twice in tree list.
- this can only occur in list that is already a linked list, not possible for bit map.
- solution : rebuilt tree list.

 
(iii)  
Block No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In Use 1 1 0 1 0 2 1 1 1 0 0 1 1 1 0 0
Free 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1

 

 [2]
Inconsistent state
- Block no. 5 : duplicate data block
- when same data block present in 2 different files
- if removed 2 files, 2 blocks will be added to tree list twice.
- Solutions - add to free space, copy the content of block no. 5 into it, insert the copy into one of the files.