jlavi at iki.fi
Mon May 13 04:40:08 EDT 2002
> order of dirty space, then in jffs2_find_gc_block just pick the block
> number $N in that list, where N is exponentially distributed -- high
> chance of being '1', small but non-negligible chance of being near the end
> of the list.
> Does anyone have any ideas on how we'd generate the random number N for
> jffs2_find_gc_block() though?
Starting from the list head, one could produce random numbers x, 0 <= x < 1,
and proceed to the next node only if the x is below a ratio r, 0 < r < 1. One
could repeat the same procedure n times. The probabilities to reach first few
nodes would be p1 = r, p2 = r*(1 - r), p3 = r*(1 - r)^2 and pi = r*(1 - r)^i.
Probability to reach the last node n would be pn = (1 - r)^(n - 1).
For example, if r were 0.9 and the list length 4, p1 = 0.9, p2 = 0.09,
p3 = 0.009 and p4 = 0.001.
Is this too naive approach? This relies perhaps too much on the randomness of
semi-random numbers and might mean only first few nodes are ever picked up
and never nodes from the tail.
More information about the linux-mtd