Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK
From: Martin Mares (mj@ucw.cz)
Date: Thu Sep 19 2002 - 14:27:58 EST
- Next message: Ingo Molnar: "[patch] generic-pidhash-2.5.36-J2, BK-curr"
- Previous message: Bond, Andrew: "RE: TPC-C benchmark used standard RH kernel"
- In reply to: Ingo Molnar: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Next in thread: Richard B. Johnson: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Reply: Richard B. Johnson: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Reply: Pavel Machek: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Hello, world!\n
> nevertheless we do lock up for 32 seconds if there are 32K PIDs allocated
> in a row and last_pid hits that range - regardless of pid_max. (Depending
> on the cache architecture it could take significantly more.)
What about randomizing the PID selection a bit? I.e., allocate PIDs
consecutively as long as they are free; if you hit an already used
PID, roll dice to find a new position where the search should be
continued. As long as the allocated fraction of PID space is reasonably
small, this algorithm should be very quick in average case.
Another possible solution: Divide PID space to blocks and for each
block, keep a counter of PID's available in this block and when
allocating, just skip blocks which are full. Runs in O(sqrt(PID space
size)) in the worst case.
Have a nice fortnight
--
Martin `MJ' Mares <mj@ucw.cz> http://atrey.karlin.mff.cuni.cz/~mj/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
This message is transmited on 100% recycled electrons.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
- Next message: Ingo Molnar: "[patch] generic-pidhash-2.5.36-J2, BK-curr"
- Previous message: Bond, Andrew: "RE: TPC-C benchmark used standard RH kernel"
- In reply to: Ingo Molnar: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Next in thread: Richard B. Johnson: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Reply: Richard B. Johnson: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Reply: Pavel Machek: "Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK"
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
This archive was generated by hypermail 2b29
: Mon Sep 23 2002 - 22:00:27 EST