Messages in this thread | | | Date | Sun, 22 Mar 1998 02:38:08 +0100 | From | Alexander Kjeldaas <> | Subject | pidhash: fork()+exit()+waitpid() in *constant time* |
| |
We have done some initial measurements on a new scheme for hashing process groups and session ids. This removes all uses of for_each_task in fork and exit [we did a new version of get_pid, it might be faster or slower than the original - it's hard to say]. The initial measurements shows that in 2.1.90, a program doing fork and waiting on the child (which only does exit()), behaves _linearly_ with the number of other processes on the system. 2.1.90 with a new "pidhash" scheme doesn't have this weakness and runs out test in _constant_ time. This means that the overhead of having 2000 running processes have no effect on fork(), exit() or waitpid().
median times on a ppro300/128MB, new scheme (2.1.90+pidhash+mmrepair): fork()+exit()+waitpid() = 49089 cycles running 10 background processes. fork()+exit()+waitpid() = 50194 cycles running 2000 background processes.
median times on a ppro300/128MB, old scheme (2.1.90+mmrepair): fork()+exit()+waitpid() = 52923 cycles running 10 background processes. fork()+exit()+waitpid() = 271301 cycles running 2000 background processes.
[full graph: ftp://ftp.guardian.no/pub/free/linux/pidhash.gif ]
The new pidhash scheme uses the fact that a process is a member of a process group which in turn is a member of a session. The tasks in the tasklist are sorted so that all processes in the same process group are grouped together, and process groups belonging to a session are grouped together. The first task in a pgrp or session is called the "fake" pgrp/session-leader. In many cases, the fake session-leader will be the same as the real leader, and this might be enforced in a later version of the patch.
pids, pgrps and sessions are all hashed in the _same_ hashtable. This means that a process calling setsid() will not get any extra hash-entries since its pid is already hashed. When a real session leader dies, and there is still tasks in the session, a new fake [in this case a real "fake"] task is hashed in the original session's place. A process can thus have a maximum of 3 hashentries in the pidhashtable by having pid!=pgrp!=session and being fake session leader and fake pgrp leader.
The following new functions are defined:
for_each_task_in_pgrp(p, pgrp) - traverse a pgrp for_each_task_in_session(p, session) - traverse a session find_task_by_pgrp(pgrp) - find fake pgrp leader find_task_by_session(session) - find fake session leader
On fork, we link the new task after its parent instead of at the end of the list. On setpgid and setsid, we so some trickery to move the task in the tasklist. In many cases, we don't move the task at all (first in a pgrp, last in a pgrp, first in a session and last in a session are candidates for this optimization).
To remove one of the for_each_tasks in exit required a different change. When a task is ptraced, the parent changes to the ptracing process. The tasks sibling-pointers are destroyed (or relinked into the new ptracing parent process) which makes the parent-child tree implemented by pointers in task_struct unreliable as information about your own children. When a process dies and we set its children's parent to init, we thus have to do a for_each_task instead of using these unreliable pointers. To fix this problem, we introduce a member in the task_struct called 'ptraced_children' which indicates the number of children currently being ptraced. In most cases this will be 0 and we can use the child-pointers and only have to do a for_each_task in the rare case when a child is ptraced.
What we "really" wanted to do was to implement random pids, but the previous scheme made it difficult to implement them efficiently :-) With the new scheme we only have to look in the pidhash to see if a pid is taken or not. You're not allowed to allocate a pid which is used by a process group or a session leader, so in the old scheme we had to traverse all tasks to double check.
astor
-- Alexander Kjeldaas, Guardian Networks AS, Trondheim, Norway http://www.guardian.no/ [unhandled content-type:application/x-gunzip]
| |