Check out the new USENIX Web site. next up previous
Next: A.2 Derivation of the Up: References Previous: References

A.1 Proof and Extension of the Single Track Model

 

Suppose a disk track contains n sectors, its free space percentage is p, and the free space is randomly distributed. Section 2.1 gives the average number of sectors the disk head must skip before arriving at a free sector:

  tex2html_wrap_inline1183

Proof. Suppose k is the number of free sectors in the track and E(n,k) is the expected number of used sectors we encounter before reaching the first free sector. With a probability of k/n, the first sector is free and the number of sectors the disk head must skip is 0. Otherwise, with a probability of (n-k)/n, the first sector is used and we must continue searching in the remaining (n-1) sectors, of which k are free. Therefore, the expected delay in this case is [1 + E(n-1,k)]. This yields the recurrence:

  tex2html_wrap_inline1183

By induction on n, it is easy to prove that the following is the unique solution to (7)
  tex2html_wrap_inline1183

(6) follows if we substitute k in (8) with pn. tex2html_wrap_inline1183

Formula (6) models the latency to locate a single sector (or a block). To extend it to situations where we need to find multiple disk sectors (or blocks) to satisfy a single file system block allocation, consider the two following examples. First, let us suppose that the host file system writes 4 KB blocks. If the disk allocates and frees 512 B sectors, it may need to locate eight separate free sectors to complete eager writing one logical block. If the disk uses a physical block size of 4 KB instead, although it takes longer to locate the first free 4 KB-aligned sector, it is guaranteed to have eight consecutive free sectors afterwards. In general, suppose the file system logical block size is B and the disk physical block size is b (b<=B), then the average amount of time (expressed in the numbers of sectors skipped) needed to locate all the free sectors for a logical block is:

  equation374

Formula (9) indicates that the latency is lowest when the physical block size matches the logical block size.



Randolph Wang
Tue Jan 5 14:30:32 PST 1999