The kernel allocates PIDs in the range of (RESERVED_PIDS, PID_MAX_DEFAULT). It does so sequentially in each namespace (tasks in different namespaces can have the same IDs). In case the range is exhausted, pid assignment wraps around.

Some relevant code:

Inside alloc_pid(…)

for (i = ns->level; i >= 0; i--) {
    nr = alloc_pidmap(tmp);
    if (nr < 0)
        goto out_free;
    pid->numbers[i].nr = nr;
    pid->numbers[i].ns = tmp;
    tmp = tmp->parent;
}

alloc_pidmap()

static int alloc_pidmap(struct pid_namespace *pid_ns)
{
        int i, offset, max_scan, pid, last = pid_ns->last_pid;
        struct pidmap *map;

        pid = last + 1;
        if (pid >= pid_max)
                pid = RESERVED_PIDS;
        /* and later on... */
        pid_ns->last_pid = pid;
        return pid;
}

Do note that PIDs in the context of the kernel are more than just int identifiers; the relevant structure can be found in /include/linux/pid.h. Besides the id, it contains a list of tasks with that id, a reference counter and a hashed list node for fast access.

The reason for PIDs not appearing sequential in user space is because kernel scheduling might fork a process in between your process’ fork() calls. It’s very common, in fact.