1
$\begingroup$

I do not have any idea how to calculate this, but I do have the data points available.

I have a computer system that has a setting for something -- garbage collection ("gc") -- to occur with p probability on any given time that a certain process runs (I'll call that process "the process").

I have the frequency of the process itself running.

I'd like to know how often, on average, will the gc run based on the probability setting, and how will that change as I increase that setting?

The probability is 1% chance any time "the process" runs, "gc" will be run.

If I know that "the process" runs 1000 times per hour, what is the average frequency that "gc" will run?

Also, I'd love to see a simple equation for this so I can plug in different values for X.

So, in summary:

  • frequency, "f", of "the process" = 1000 times/hour
  • probability, "p", that "gc" will run for any given "the process" = 1%
  • how many times per hour, on average, will "gc" run?
  • Or, how many minutes, on average, between runs of "gc"?
  • Is there a simple formula I can use to change values of "f" and "p" so I can tune the value of "p" with real world data?
$\endgroup$
  • $\begingroup$ Are you assuming that your "process" is instantenous, or does it take some time to run? $\endgroup$ – Aniko Sep 29 '11 at 16:59
  • $\begingroup$ This sounds a bit like homework, as described. $\endgroup$ – John Doucette Sep 29 '11 at 21:54
  • $\begingroup$ @John Doucette: This is not homework; I am not in college. But I do agree that it sounds like homework, probably because it is too basic to be in this particular stackexchange group. However, I am not a data analyst or statistician, and my skill in this area is extremely basic. I am a linux systems administrator trying to tune a process to balance performance against cleanup. $\endgroup$ – JDS Sep 30 '11 at 1:20
  • $\begingroup$ @Aniko: yes, the process is, on average, effectively instantaneous. Assuming it is instantaneous will work for my purposes. $\endgroup$ – JDS Sep 30 '11 at 1:21
  • $\begingroup$ For a process that runs $f$ times per hour on average with a probability $p$ of subsequent garbage collection, then it's immediate that the mean rate of gc is $pf$ times per hour. The mean time between gc runs is exactly $1/(fp)$ (hours per time). The hard part (which you haven't asked, but which is interesting and important) is how to compute the variation of these values. That depends on how the process runs are distributed over time. You get different answers for a regular process (like a clock tick) than for other less-regular processes. $\endgroup$ – whuber Nov 29 '11 at 20:49
1
$\begingroup$

To elaborate on John Doucette's answer that you need to look at the Poisson distribution and that gc will run $f*p = 10$ times per hour on average, you might want to look at the Poisson process as well. This will answer questions such as "What is the distribution of the time between successive runs of gc?"

The times between successive runs of $gc$ (inter-run gaps) are exponentially distributed with an average of $1/(f*p)$ hours $= 6$ minutes between runs. The standard deviation of the inter-run gaps is also $6$ minutes. Note that there is no guarantee that gc will run $10$ times each hour or that the average length of the inter-run gaps measured during one hour will be $6$ minutes. Exponential distribution means that the probability is $e^{-T/6}$ that an inter-run gap will be longer than $T$ minutes. In particular, a longer than average inter-run gap (more than $6$ minutes) has only a $e^{-1} \approx 37\%$ chance of occurring. The median inter-run gap is $6 \ln 2 \approx 4.14$ minutes, that is, over several hours, you should expect half the inter-run gaps to be shorter (and half longer) than $\approx 4.14$ minutes.

Edit: Material added in response to @jbowman's comments

Several different models can be used in this problem. Some of those mentioned below might have been rejected by the OP already, but are included anyway.

  • The main process runs exactly $f = 1000$ times, no more, no less, every hour at equally spaced intervals of one millihour.

    1. Every $\frac{1}{p} = \frac{1}{0.01} = 100$th run of the main process calls gc which thus runs $f*p = 10$ times an hour at $\frac{1}{f*p} = 0.1~\text{hour} = 6$ minute intervals. There is nothing random about all this.

    2. There is a call to gc by exactly one of the processes #$1-$#$100$, exactly one of the processes #$101-$#$200$, and so on, with each call to gc being equally likely to be any of the $100$ choices. Again there are $10$ calls to gc every hour, but now the inter-run gap between two calls to gc is random and can take on value $i$, $1 \leq i \leq 199$ with probability $(100 - |i-100|)\times 10^{-4}$. The histogram is triangular with a peak at $i = 100$. The average inter-run gap is $100$ millihours $= 6$ minutes.

    3. Each of the $1000$ runs of the main process calls gc with probability $p = 0.01$, independently of all other runs of the process. Now the number of calls to gc each hour is a binomial random variable with parameters $(f,p) = (1000,0.01)$ and average value $f*p = 10$. Note that there is no guarantee that gc will run $10$ times each hour anymore. In fact, gc might not run at all, or it might run every millihour. The inter-run gaps are geometric random variables with parameter $p = 0.01$ and the average gap is $1/p = 100$ millihours $= 6$ minutes.

  • The occurence times of the main process are modeled as the arrival times in a Poisson process with arrival rate $f = 1000$ per hour. Note that this does not mean that the main process runs $1000$ times each hour: the number of runs is a Poisson random variable $N$ with parameter $1000$ and average value $E[N] = 1000$.

    1. Every $100$th run of the main process calls gc. Now the number of times that gc runs every hour is $\lfloor N/100 \rfloor$ which is a random variable with average value approximately $10^{-2}E[N] = 10$. For later reference, I note that the times of the calls to gc do not constitute the arrival times of a Poisson process with arrival rate $10$.

    2. Each run of the main process calls gc with probability $p$ independently of all other runs of the main process. This is called Poisson splitting and the times of the calls to gc do constitute the arrival times of a Poisson process with arrival rate $f*p = 10$ per hour. The number of times that gc will run in an hour is a Poisson random variable with parameter $10$ and average value $10$. Once again, there is no guarantee that gc will run $10$ times an hour even if the main process runs far more than $1000$ times. The inter-run gaps for gc are exponential random variables with average value $1/f*p = 0.1$ hour $= 6$ minutes but there is no guarantee that gc will run every $6$ minutes or so.

Under the Poisson regime, it is possible that there will be long gaps between runs of gc, and indeed the main process may well run once in the first minute in an hour and then $999$ times in the last few microseconds of the hour. However, this is highly unlikely. If such a phenomenon is indeed observed several times, a nonhomogeneous Poisson model (with variable arrival rate) might be considered.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The distribution of times between successive runs of gc depends on the distribution of times between the process runs. If the process runs every $k$ clock ticks, then the Exponential will be a reasonable approximation to the actual (discrete) distribution in this case, otherwise, maybe not. (A counterexample: imagine the process runs at 1 minute past the hour, then 999 times between 55 minutes and 59 minutes past the hour. The inter-run gaps of $gc$ would be far from exponential.) $\endgroup$ – jbowman Nov 29 '11 at 21:57
0
$\begingroup$

From what you've written above, it sounds like you want to use a Poisson Distribution:

http://en.wikipedia.org/wiki/Poisson_distribution

with lambda equal to: f*p =# times gc will run per hour (assuming that "p" is just a draw from a uniform distribution)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.