Breaking through the Maximum Process Number

Breaking through the maximum process number restriction in i386-based Linux.
System Initialization

In Linux 2.2.x, some process-management-concerned data structures are initialized when booting the system. The most important of these are GDT and the process list.

When the kernel starts, it must decide the size of GDT. Since two GDT entries must be kept in GDT for each process, the size of GDT is defined by the maximum concurrent process number. In Linux, this number is defined as NR_TASKS at compile time. According to Figure 2, the size of GDT is 10+2(with APM)+NR_TASKS*2.

The process list is actually an array of PCB pointers, defined below:

Struct task_struct *task[NR_TASKS] = {&init_task,};

In the above line, init_task is the PCB of the root process. After inserting this process into the process list, the process management mechanism can begin its work. Note the size of process list is also dependant on NR_TASKS.

Process Creation

In Linux 2.2.x process is created by a system call, fork. The new process is the child process of the original process. Using a clone can create a thread, which is actually a lightweight process. In fact, there is no real thread in Linux 2.2.x. Figure 3 shows how the fork system call works.

Figure 3. Fork System Call

The key steps in fork are:

  1. Create the new process PCB: the kernel allocates two pages for the new process stack, and the PCB is put at the bottom of it.

  2. Insert the new process into the process list: the kernel must find a empty entry from the process list. If the system has reached the maximum concurrent process limit, no empty entry will be found and the system call fails.

  3. Copy parent address space: the child process has its own address space, but first it shares address space with its parent using copy-on-write mechanism. The corresponding GDT descriptor of the new process LDT is also created in this step.

  4. Setting TSS for new process: the TSS of the new process is created in PCB and the corresponding GDT descriptor is also created.


The core of scheduling is the algorithm listed below. But here we just take a look at process switching. In Linux 2.2.x process switch is done in the switch_to function. It works like this:

  1. load new TSS by setting TR

  2. save old FS and GS registers into old PCB

  3. load LDT if needed by new process

  4. load new page tables for new process

  5. load new process FS and GS

Note that the value of TR and LDTR are coming from PCB.

Breakthrough the Maximum Process Number Restriction

What is the maximum process number restriction? According to the above discussion, we can easily find why there is a maximum process number restriction. The NR_TASKS defined in Linux 2.2.x statically defines the maximum concurrent process number at the compile time. NR_TASKS also defined the size of GDT at compile time. As defined in i386 architecture, the maximum size of GDT is 8192*8 bytes, which means it can contain 8,192 descriptors. In Linux 2.2.x, when booting the kernel, GDT is used as described below:

  1. NULL descriptor (entry 0), reserved descriptor (entry 1,6,7)

  2. Kernel code and data descriptors (entry 2,3) and user code and data descriptors (entry 4,5)

  3. APM BIOS descriptors (entry 8-11)

In total, 12 entries are used. And since each process needs two GDT entries, in theory we can get (8192 -12)/2 = 4090 processes running concurrently.

Solution to This Problem

Although GDT size is restricted by hardware, we still can find a solution for this problem. For one CPU, only one process can be running at a certain time. That is to say, it is not necessary to reserve GDT descriptors for all possible processes at all. When a process is about to run, we set its descriptors dynamically.

After analyzing the PCB structure, we can find the TSS and LDT (if any) in it. So when doing a process switch, we can find these two segments by PCB pointer, like this:

TSS: proc->tss

In fact, when doing a process switch, we can find the PCB pointer from the process list. Since both TSS and LDT can be found, keeping them in GDT at all times is unnecessary.

Our solution is to reserve only two GDT descriptors for each CPU, using common entries for all processes. For example, in a machine with two CPUs, four GDT entries are reserved. When process A will run on CPU1, GDT entry three and four will be set to the descriptor of TSS and LDT of process A. Old values of these entries are discarded. Remaining GDT entries are used just the same as the original system.