Return to Answer

added 2166 characters in body

Source Link

edited Aug 28 at 23:41

51.8k
4
79
121

Appendix: PID collision probabilities

It's been brought to my attention that people doubt the "PIDs can collide" argument, quoting a space of 2²² possible PIDs.

Collision between any two PIDs chosen (Birthday Problem)

That is a rather small space. Making the assumption that every one of these PIDs is chosen equally likely (thus, modelling things better than they are), we hit the expected number of newly chosen PIDs before we get the first collision between any two PIDs after trying but approximately 1.25·√(2²²) = 1.25 · 2¹¹ = 2560 PIDs.

Collision between one specific PID and a later chosen PID

Even if we just say

I don't care whether there's any collision, I want the time where it becomes more likely that we have a collision this one particular PID than that we have no collision

(which is very valid!), then we can do the following:

The probability to not have a collision is (2²²-1) out (2²²) for every newly chosen PID,

P = (2²²-1)/(2²²)=1 - 2⁻²².

Now, the probability of not choosing our desired PID twice in a row is P². The probability for not choosing it n times in a row is Pⁿ. So. If we want to know

at the point where Pⁿ = 50% = 0.5, what's the n?

We apply the logarithm to both sides of the equation Pⁿ = 0.5, and get

log(Pⁿ)=log(0.5)

Then, thanks to logarithm arithmetic rules

log(Pⁿ) = n·log(P) = log(0.5),

we divide by log(P) and get n=log(0.5)/log(P), which is, rounded, n=2907270.

Times to collisions

If we assume that our servers spawns but 10 new processes per second (which isn't even much for a desktop usage, and very little for something that might e.g. spawn an image converter, or process emails through filters etc), we get:

Case	number of PIDs before expected collision	time to expected collision at 10 PID/s	… at 100 PID/s
Collision between any two PIDs	2560	256 s, i.e., < 5 minutes	< 30s
Collision with a fixed PID	2907270	290727 s, i.e., 80 hours 45 minutes	8 hours

Appendix: PID collision probabilities

It's been brought to my attention that people doubt the "PIDs can collide" argument, quoting a space of 2²² possible PIDs.

Collision between any two PIDs chosen (Birthday Problem)

Collision between one specific PID and a later chosen PID

Even if we just say

I don't care whether there's any collision, I want the time where it becomes more likely that we have a collision this one particular PID than that we have no collision

(which is very valid!), then we can do the following:

The probability to not have a collision is (2²²-1) out (2²²) for every newly chosen PID,

P = (2²²-1)/(2²²)=1 - 2⁻²².

Now, the probability of not choosing our desired PID twice in a row is P². The probability for not choosing it n times in a row is Pⁿ. So. If we want to know

at the point where Pⁿ = 50% = 0.5, what's the n?

We apply the logarithm to both sides of the equation Pⁿ = 0.5, and get

log(Pⁿ)=log(0.5)

Then, thanks to logarithm arithmetic rules

log(Pⁿ) = n·log(P) = log(0.5),

we divide by log(P) and get n=log(0.5)/log(P), which is, rounded, n=2907270.

Times to collisions

Case	number of PIDs before expected collision	time to expected collision at 10 PID/s	… at 100 PID/s
Collision between any two PIDs	2560	256 s, i.e., < 5 minutes	< 30s
Collision with a fixed PID	2907270	290727 s, i.e., 80 hours 45 minutes	8 hours

Source Link

answered Aug 28 at 15:39

Marcus Müller

51.8k
4
79
121

TL;dr

if you have a list of PIDs you need to kill, you need to change where you're getting that list from to start these processes through your system's job manager. Then you get convenient functionality to stop the process, and only these, exactly at the point you want, without problems. This has been a long-time established standard methodology, as keeping around lists of PIDs has always been problematic.

The longer story

This will be the unpopular answer that says "you don't", so I considered keeping it in the comments, but it's become clear that it's far too much and far too nuanced for comments, and should actually be understood as answering the question rather than commenting on it:

I'd personally advocate for avoiding killing things by PID unless you can guarantee it's the actual same process that hasn't stopped yet and another process has taken the PID¹; for short-running things, this might be OK, but if between creation of the original process with the PID and you killing it are hours, you're seriously running the risk of hitting the wrong process.

You'd generally want to have a parent/child relationship between the process you kill, because then you can hold a permanent, unambiguous handle to exactly that process, but bash has no ways of becoming the parent of a list of jobs identified by PID².

So, only correct³ approach would seem to be to be to instruct the parent of the processes you want to kill to kill them. Now, every Linux, BSD, Solaris-derivative or Mac OS system forever has a init system who's the parent to services – and that's literally its job. So, instead of shifting around PID lists, you need to talk to your specific service manager⁴.

¹ exactly the reason we have pidfd on Linux these days: the PID space is just too small, and chances are too high that a PID gets reused. FreeBSD has procdesc's pdfork(), pdkill() for this, Solaris/Illumos has the OG procopen()/procrun() API that allows unambiguous handles to processes.

This isn't a new idea – PIDs have been visibly not a good method of describing a single process for a couple of decades now. Linux is kind of late to the game there.

² With the pidfd API, you can exchange pidfd between processes via domain sockets, which are referring to exactly one process, and only that one, ever, but bash doesn't support any of that. Neither getting of pidfds, nor handling domain sockets, nor exchanging file file descriptors across such.

³ "correct", as in: provably not killing a newer process that we didn't mean

⁴ That service manager doesn't have to be your init system – there's orthogonal systems for other kinds of services, think docker/podman, or slurm, or printer job queues