[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Benchmarking JFFS2

> 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.

Jarkko Lavinen

To unsubscribe from this list: send the line "unsubscribe jffs-dev" in
the body of a message to majordomo@xxxxxxx.com