[lkml]   [2002]   [Aug]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Analysis for Linux-2.5 fix/improve get_pid(), comparing various approaches
    On Friday 09 August 2002 11:36 am, Andries Brouwer wrote:

    !!!!!!!!!!! You are in a different space !!!!!!!!
    All work was done under the assumption of 16-bit pid_t.
    I stated yesterday already that for NumTasks substantially smaller
    than the pid_t supported size, this won't be a problem
    as your analysis states and my data also states.

    You have two choices
    (a) move Linux up to 32-bit pid_t
    (b) stick within the current 16-bit discussion.

    > On Fri, Aug 09, 2002 at 07:22:08AM -0400, Hubertus Franke wrote:
    > > Particulary for large number of tasks, this can lead to frequent exercise
    > > of the repeat resulting in a O(N^2) algorithm. We call this : <algo-0>.
    > Your math is flawed. The O(N^2) happens only when the name space for pid's
    > has the same order of magnitude as the number N of processes.
    > Now consider N=100000 with 31-bit name space. In a series of
    > 2.10^9 forks you have to do the loop fewer than N times and
    > N^2 / 2.10^9 = 5. You see that on average for each fork there
    > are 5 comparisons.
    > For N=1000000 you rearrange the task list as I described yesterday
    > so that each loop takes time sqrt(N), and altogether N.sqrt(N)
    > comparisons are needed in a series of 2.10^9 forks.
    > That is 0.5 comparisons per fork.
    > You see that thanks to the large pid space things get really
    > efficient. Ugly constructions are only needed when a large fraction
    > of all possible pids is actually in use, or when you need hard
    > real time guarantees.
    > Andries

    -- Hubertus Franke (
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:27    [W:0.037 / U:0.824 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site