Como são gerados os PIDs?

No * nix, os PIDs são identificadores exclusivos para processos em execução. Como são gerados os PIDs? É apenas um número inteiro incrementado ou uma estrutura mais complexa, como uma lista? Como eles são reciclados? Com a reciclagem, quero dizer que, quando um processo termina, o PID será reutilizado por outro processo.

Como a wikipedia diz,

No Unix, os IDs de processo geralmente são alocados sequencialmente, começando em 0 e aumentando para um valor máximo que varia de sistema para sistema. Quando esse limite é atingido, a alocação é reiniciada em zero e aumenta novamente. No entanto, para isso e passes subsequentes, quaisquer PIDs ainda atribuídos aos processos são ignorados.

portanto, é realmente uma política muito simples para "geração", basta incrementar um contador e "reciclar", basta agrupar o número no valor máximo e continuar incrementando até encontrar um número que foi atribuído a um processo que terminou e tem foi removido da tabela de processos.

Algumas implementações do Unix, como o AIX, usam uma política menos simples, consulte, por exemplo, esta FAQ .

Varia.

A maioria dos sistemas simplesmente mantém uma contagem do último PID gerado, adiciona um (quebra automática no número máximo, como 65535 ou um pouco menor - geralmente a quebra ocorre em 65000 ou mesmo 60000) e verifica se o número não está em uso no momento ( repetindo se o PID ainda estiver em uso - portanto, o PID 1, o kernel, ainda está lá e não é "reemitido").

Outros sistemas preocupados com segurança geram um número aleatoriamente e verificam se ele não está em uso.

A qualquer momento, é garantido que todos os números PID são únicos.

Quanto à parte de reciclagem da questão, lembre-se de que um pid não fica disponível assim que o processo com esse pid termina. O pid não fica disponível até que o pai desse processo colete o status de término de seu filho por meio de alguma forma da chamada do sistema wait (). Uma criança que é demitida, mas cujo pai não emitiu uma espera, é chamada de zumbi e geralmente aparece no ps como extinta. É possível que um pai mal-comportado passe fome no sistema de pids se lançar filhos e não esperar () por eles.

Se o pai de um processo morrer antes de coletar o status de um filho, tudo bem. A criança é herdada pelo init, que garante que a espera () seja emitida e o pid seja reciclado.

Eles são números de sequência e agrupam (em um valor específico do SO) se o sistema estiver funcionando por tempo suficiente. Os números nunca são reutilizados, a menos que sejam gratuitos no momento fork().