State Transitions - Learning Module

Loading content...

0/227

Admit: New → Ready

From Creation to Eligibility

Every process begins its life as a collection of static instructions on disk—a program waiting to be executed. The moment a user double-clicks an application icon, types a command in the terminal, or another process spawns a child, a remarkable transformation begins. The operating system must convert that dormant executable into a living, schedulable entity.

This transformation is the Admit transition: the passage from the New state to the Ready state. It represents the moment when the kernel acknowledges a process's existence and declares it eligible for CPU time. Understanding this transition is fundamental to grasping how operating systems manage process creation, resource allocation, and system admission policies.

What You Will Learn

By the end of this page, you will understand the complete lifecycle of the Admit transition—from the initial fork() or CreateProcess() call through PCB initialization, memory allocation, resource assignment, admission control decisions, and final placement in the Ready queue. You'll see how the kernel orchestrates this transition and why admission control policies matter for system stability.

The New State Defined

Before examining the transition itself, we must clearly understand what the New state represents. A process in the New state is a partially constructed entity—it exists in the kernel's consciousness but isn't yet ready for execution.

What characterizes the New state:

When a process enters the New state, the kernel has begun creating necessary data structures but hasn't completed all initialization tasks. The process exists as a kernel object, but it's not yet a candidate for CPU scheduling. Think of it as a construction site where the foundation is being laid—the structure exists, but it's not habitable.

Process Characteristics in the New State
Aspect	Status in New State	Completion Required
Process ID (PID)	Assigned	No
Process Control Block (PCB)	Allocated but partially initialized	Yes - fields must be populated
Address Space	Being constructed	Yes - segments must be mapped
Memory Pages	Allocation in progress	Yes - initial pages must be loaded
File Descriptors	Inheritance pending	Yes - must be copied from parent
Credentials	Being established	Yes - UID/GID must be set
CPU Context	Uninitialized	Yes - initial register values needed
Ready Queue Membership	Not present	Yes - must be inserted for scheduling

The New state exists because process creation is not atomic:

Creating a process involves numerous steps that cannot all complete instantaneously. The New state provides a conceptual holding area during this initialization phase. Some operating systems treat this state as very transient (lasting microseconds), while others may keep processes in New longer due to admission control policies.

Visibility of New state processes:

In most Unix-like systems, you rarely observe processes in the New state because the creation is fast. However, tools like ps may occasionally show a process created but not yet running if you're quick enough. On systems with strict admission control (like batch processing systems), processes may reside in New state waiting for approval.

Historical Context

In early batch systems, the New state was called the 'Submitted' or 'Spooled' state. Jobs would wait in this state while the operating system decided when to admit them based on resource availability. Modern interactive systems compress this waiting period significantly, but the conceptual state remains important for understanding the complete process lifecycle.

Triggering the Admit Transition

The journey from New to Ready begins when a process creation request enters the kernel. This request can originate from multiple sources, each with different semantics and implications.

Process Creation Triggers

•System Initialization (Boot) — During boot, the kernel spawns essential system processes (init/systemd, kernel threads). These are admitted immediately with high priority.
•User Request — Interactive shell commands, GUI application launches. The shell calls fork() followed by exec(), or the window manager initiates CreateProcess().
•Process Spawning (fork/clone) — An existing process creates a child. The parent's context becomes the template for the child's initialization.
•Batch Job Submission — In server or HPC environments, job schedulers submit processes for execution. Admission may be deferred based on resource availability.
•Operating System Services — Kernel components may spawn helper processes or kernel threads for specific tasks.

The fork() system call in detail:

On Unix-like systems, the fork() system call is the primary mechanism for process creation. When a process calls fork(), the kernel must:

Verify the calling process has permission to create children
Check system-wide process limits haven't been exceeded
Allocate a new PID and PCB
Copy (or prepare to copy-on-write) the parent's address space
Initialize the child's state based on the parent's state
Return twice: once in the parent (with child's PID) and once in the child (with 0)

fork_example.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
 
int main() {
    printf("Parent process (PID: %d) about to fork\n", getpid());
    
    // At this point, the parent is in Running state
    pid_t pid = fork();
    
    if (pid < 0) {
        // fork() failed - system resource limits or permissions issue
        perror("fork failed");
        return 1;
    }
    
    if (pid == 0) {
        // Child process - just transitioned from New to Ready,
        // now in Running (since we're executing)
        printf("Child process (PID: %d) now running\n", getpid());
        printf("  Parent PID from child's view: %d\n", getppid());
        // Child inherits file descriptors, environment, etc.
    } else {
        // Parent process - continues in Running
        printf("Parent: created child with PID %d\n", pid);
        
        // Parent waits for child to complete
        int status;
        waitpid(pid, &status, 0);
        printf("Parent: child exited with status %d\n", 
               WEXITSTATUS(status));
    }
    
    return 0;
}

The Hidden Complexity

While fork() appears simple from the programmer's perspective, the kernel performs extensive work behind the scenes. Modern implementations use copy-on-write (COW) to defer the expensive memory copying, making the New → Ready transition faster. But the conceptual steps—PCB creation, resource allocation, queue insertion—still occur.

Kernel Actions During Admit

The Admit transition is orchestrated entirely by the kernel. When transitioning a process from New to Ready, the kernel executes a precise sequence of operations. Understanding this sequence reveals the complexity hidden behind seemingly simple process creation.

Converting Mermaid diagram...

Detailed breakdown of each step:

Step-by-Step Kernel Operations

•PID Allocation — The kernel assigns a unique Process ID from its PID namespace. This involves consulting a bitmap or counter to find an unused PID. On Linux, PIDs wrap around after reaching the maximum (default 32768, configurable to ~4 million).
•PCB Creation — The kernel allocates memory for the Process Control Block (task_struct in Linux). This is typically allocated from a dedicated slab cache for efficiency. The PCB is the kernel's handle to everything about the process.
•PCB Field Initialization — Critical fields are set: process state (initially NEW), parent PID, creation timestamp, default signal handlers, initial scheduling parameters. For forked processes, many fields are copied from the parent.
•Address Space Setup — The kernel creates a new virtual address space. For fork(), this involves setting up copy-on-write mappings to the parent's pages. For exec(), it prepares to load the executable's segments.
•Initial Memory Allocation — The kernel maps the program's text (code), data, and BSS segments. Stack space is allocated. On-demand paging means not all pages are physically loaded yet.
•Resource Inheritance/Initialization — File descriptors are duplicated (for fork) or set to defaults. IPC resources, credentials (UID, GID, capabilities), and resource limits are established.
•Credential Setup — The process's effective user ID, group ID, and privilege capabilities are set based on the executable's permissions and parent's credentials.
•Ready Queue Insertion — Finally, the process is added to the Ready queue, making it visible to the scheduler. The process state changes from NEW to READY.

Atomicity Considerations

The Admit transition must be carefully synchronized. If the kernel inserted a process into the Ready queue before completing initialization, the scheduler might select it for execution, causing undefined behavior. The kernel uses internal locks and state checks to ensure a process is fully initialized before becoming schedulable.

PCB Initialization Deep Dive

The Process Control Block is the nucleus of process management. During the Admit transition, the kernel populates this structure with everything needed for scheduling, memory management, and resource tracking. Let's examine the key components initialized during this phase.

PCB Fields Initialized During Admit
Field Category	Specific Fields	Initialization Action
Identity	pid, tgid, parent pid, process group, session	Assigned unique values; parent info copied from caller
State	state, exit_state, flags	Set to TASK_NEW initially, flags indicate creation mode
Scheduling	priority, static_prio, policy, sched_class	Set from parent or defaults; policy inherits or uses default
Memory	mm_struct pointer, address space limits	New mm_struct created; limits inherited from parent
CPU Context	thread_struct (registers, stack pointer)	Initialized for first execution in user space
Timing	start_time, utime, stime	Creation time recorded; CPU times zeroed
File System	fs_struct, files_struct	Current directory inherited; file table duplicated
Signals	signal_struct, sighand_struct, blocked mask	Handler table initialized; inherited blocked signals
Credentials	cred, real_cred	UID/GID from parent or executable's setuid/setgid
Resource Limits	signal->rlim[]	Limits (max files, stack size, etc.) inherited from parent

The Linux task_struct in context:

In Linux, the PCB is implemented as task_struct, one of the largest and most complex structures in the kernel (over 700 bytes, containing pointers to numerous sub-structures). During the Admit transition (in copy_process() called by fork()), the kernel performs a careful dance:

Allocate thread info and stack — Each process needs kernel stack space
Copy task_struct — Start with parent's structure as template
Initialize unique fields — PID, timestamps, and accounting info
Duplicate or share resources — Based on clone flags (CLONE_FILES, CLONE_VM, etc.)
Set up scheduler data — Enqueue in appropriate scheduling class

pcb_initialization_pseudocode.c
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Simplified view of process creation in Linux kernel
// Actual implementation in kernel/fork.c is ~2000 lines
 
struct task_struct* copy_process(unsigned long clone_flags,
                                  unsigned long stack_start,
                                  struct pt_regs *regs) {
    struct task_struct *p;
    
    // Step 1: Allocate new task_struct from slab cache
    p = dup_task_struct(current);
    if (!p)
        goto fail_allocation;
    
    // Step 2: Initialize unique identity
    p->pid = alloc_pid();      // Unique PID assignment
    p->tgid = p->pid;          // Thread group leader is self
    p->parent = current;        // Parent is calling process
    p->real_parent = current;
    
    // Step 3: Initialize state as NEW (not schedulable yet)
    p->state = TASK_NEW;       // Process in New state
    
    // Step 4: Copy or share resources based on flags
    if (!(clone_flags & CLONE_FILES))
        copy_files(p);         // Independent file descriptors
    if (!(clone_flags & CLONE_VM))
        copy_mm(p);            // Copy-on-write address space
    copy_signal_handlers(p);   // Signal disposition
    copy_credentials(p);       // UID/GID/capabilities
    
    // Step 5: Initialize scheduling parameters
    p->sched_class = fair_sched_class;
    p->prio = current->prio;   // Inherit priority
    p->static_prio = current->static_prio;
    
    // Step 6: Initialize timekeeping
    p->start_time = ktime_get_ns();
    p->utime = p->stime = 0;   // No CPU time yet
    
    // Step 7: Set up CPU context for first switch
    copy_thread(p, regs);      // Set up initial register state
    
    // Step 8: Transition New → Ready
    p->state = TASK_RUNNABLE;  // Now in Ready state
    wake_up_new_task(p);       // Add to run queue
    
    return p;
    
fail_allocation:
    return ERR_PTR(-ENOMEM);
}

The Clone Flags Mechanism

Linux's clone() system call (which underlies fork()) uses flags to control what's shared vs copied. CLONE_VM shares address space (for threads), CLONE_FILES shares file descriptors, CLONE_SIGHAND shares signal handlers. This flexibility allows fork(), vfork(), and pthread_create() to all use the same underlying mechanism with different flag combinations.

Memory Allocation During Admit

Memory management during the Admit transition is a critical and complex operation. The kernel must establish a complete virtual address space while being efficient about physical memory usage. Modern systems use sophisticated techniques to minimize the overhead of process creation.

Address Space Components

•Text Segment — Executable code, mapped read-only from the executable file. Usually shared with other instances of the same program.
•Data Segment — Initialized global and static variables. Copied from executable, made writable.
•BSS Segment — Uninitialized globals. Mapped to zero-filled pages on demand.
•Heap — Dynamic allocations. Initially minimal; grows with malloc() calls.
•Stack — Function call frames. Allocated at process creation; grows downward on demand.
•Shared Libraries — Mapped from .so files. Text is shared; data is copy-on-write.

Optimization Techniques

•Copy-on-Write (COW) — Fork doesn't copy physical pages immediately. Both parent and child share pages until one writes.
•Demand Paging — Pages are loaded from disk only when accessed. Initial page table entries are marked invalid.
•Shared Text — Multiple processes running the same program share code pages in physical memory.
•Page Table Cloning — Fork copies page table entries, not actual pages. Very fast operation.
•Memory-Mapped Executables — Executables are mmap'd, allowing the page cache to serve code pages.

Copy-on-Write: The Key to Fast Fork:

Copy-on-write is the optimization that makes fork() viable in modern systems. Without COW, forking a 1GB process would require copying 1GB of memory—taking hundreds of milliseconds and consuming substantial physical memory. With COW:

Fork() marks all writable pages as read-only in both parent and child
Both processes share the same physical pages initially
When either process writes to a page, a page fault occurs
The kernel allocates a new physical page, copies the content, and resumes
Only pages that are actually modified are ever copied

For processes that fork() and immediately exec() (the common case), COW means almost no memory is ever copied—the child's address space is completely replaced before any COW faults occur.

Memory Overhead: Fork Without vs With COW
Scenario	Without COW	With COW	Improvement
Fork 100MB process (immediate exec)	100MB copied, 100ms	~0MB copied, <1ms	100x faster
Fork 1GB process (child reads only)	1GB copied, 1000ms	~0MB copied, <1ms	1000x faster
Fork 1GB process (child modifies 10MB)	1GB copied, 1000ms	10MB copied, 10ms	100x faster
Fork 1GB process (child modifies 1GB)	1GB copied, 1000ms	1GB copied on demand	Same total, better distribution

Memory Efficiency in Practice

COW is why you can have hundreds of shell processes (each forked from bash) on a system with limited RAM. They share most of their memory pages. Only when a process modifies data does it get its own private copy of those specific pages. This sharing is transparent to applications—each believes it has its own private memory.

Admission Control Policies

Admission control determines whether and when a process in the New state should be promoted to Ready. While desktop systems typically admit processes immediately, many production environments implement sophisticated admission policies to prevent resource exhaustion and ensure quality of service.

Types of Admission Control

•Immediate Admission — Default on interactive systems. Processes are admitted as soon as basic initialization completes. Provides responsive user experience but may lead to overload.
•Resource-Based Admission — Processes are admitted only if sufficient resources (memory, file descriptors, etc.) are available. Prevents over-commitment but may cause creation failures.
•Load-Based Admission — Admission delayed when system load is high. Used in batch systems and container orchestrators. Smooths workload peaks.
•Priority-Based Admission — Higher-priority processes admitted before lower-priority ones. Ensures important workloads aren't blocked by less critical ones.
•Quota-Based Admission — Users or groups have limits on concurrent processes. Prevents runaway fork bombs and ensures fairness.
•Time-Based Admission — Batch jobs scheduled for specific time windows. Common in HPC and mainframe environments.

Linux resource limits (rlimits):

Linux implements admission control through resource limits. When fork() is called, the kernel checks several limits:

RLIMIT_NPROC: Maximum processes for this user. If exceeded, fork() returns -EAGAIN.
Kernel parameters: pid_max (maximum PIDs), threads-max (maximum kernel threads).
Memory: If not enough memory for basic structures, fork() fails with -ENOMEM.
Cgroup limits: Container environments can limit processes per cgroup.

These checks happen before significant resources are allocated, failing fast if limits would be exceeded.

admission_control_example.sh
Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# View current process limits
ulimit -a
 
# Check user's maximum process limit
ulimit -u
# Example output: 63704
 
# Set maximum processes for current shell and children
ulimit -u 100
 
# View system-wide limits
cat /proc/sys/kernel/pid_max      # Maximum PID value
# Example: 4194304
 
cat /proc/sys/kernel/threads-max  # Maximum total threads
# Example: 126407
 
# View cgroup process limits (if using systemd)
cat /sys/fs/cgroup/user.slice/user-1000.slice/pids.max
# Example: max (unlimited) or specific number
 
# Demonstrate fork failure due to limit
ulimit -u 5  # Set very low limit
# Now try to run many processes
for i in {1..10}; do
    sleep 100 &
done
# Output: bash: fork: retry: Resource temporarily unavailable

Fork Bombs and Protection

A fork bomb is a process that continuously forks children, exponentially consuming process slots until the system becomes unresponsive. Admission control prevents this: setting RLIMIT_NPROC to a reasonable value (e.g., 1000 per user) ensures that even a runaway fork bomb only affects that user and eventually fails when hitting the limit.

Ready Queue Insertion

The final step of the Admit transition is inserting the process into the Ready queue. This seemingly simple operation involves careful coordination with the scheduler and has implications for when the new process will first receive CPU time.

Ready queue structures:

Modern operating systems don't use a single Ready queue. Instead, they maintain sophisticated data structures optimized for their scheduling algorithms.

Linux's Completely Fair Scheduler (CFS) uses:

A red-black tree per CPU, ordered by 'virtual runtime'
New processes are inserted with a virtual runtime slightly ahead of the current minimum
This gives new processes a fair chance to run soon, but doesn't let them jump the queue

Windows uses:

Per-processor ready queues organized by priority level
32 priority levels, each with its own queue
New processes enter the queue for their priority level

Converting Mermaid diagram...

Scheduling considerations for new processes:

When a new process is admitted, the scheduler must decide several things:

Which CPU's queue? On SMP systems, the kernel chooses a CPU to minimize load imbalance. It may consider:
- Cache locality (prefer parent's CPU for fork, since parent's data may be cached)
- CPU load (choose a less busy CPU)
- NUMA topology (prefer node-local memory)
Queue position? The new process shouldn't unfairly jump ahead of processes that have been waiting. CFS gives new processes a slight bonus but not excessive advantage.
Immediate preemption? If the new process has higher priority than the currently running process, the scheduler sets a flag to trigger preemption at the next safe point.
Wake-up latency? How quickly should the new process get CPU time? Interactive processes benefit from quick wake-up.

The Child Runs First Optimization

Linux typically gives the child process priority to run before the parent after fork(). This optimization helps when the child immediately calls exec(): it can begin loading the new program while the parent continues, maximizing parallelism. If the parent ran first and touched shared pages, those pages would need to be copied for the child.

Ready Queue Properties by Scheduling Class
Scheduling Class	Queue Structure	New Process Placement	Priority Boost
Real-Time FIFO	Per-priority linked list	End of priority queue	None - runs until blocked
Real-Time RR	Per-priority linked list	End of priority queue	None - gets full time slice
CFS (Normal)	Red-black tree by vruntime	Vruntime = min + slice/2	Small boost for interactivity
Idle	Simple queue	End of queue	Only runs when nothing else needs CPU

Platform-Specific Implementations

The Admit transition is a universal concept, but its implementation varies significantly across operating systems. Let's compare how different platforms handle process admission.

Linux Process Creation:

System calls: fork(), vfork(), clone() - all implemented via kernel_clone()
Key function: copy_process() in kernel/fork.c
State transition: TASK_NEW → TASK_RUNNABLE
Queue insertion: wake_up_new_task() adds to CFS run queue

Unique characteristics:

Extensive use of copy-on-write
Clone flags allow fine-grained resource sharing
Namespaces allow process isolation
Cgroups provide resource limiting

linux_fork_sequence.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Simplified call sequence for fork() in Linux
// User space
fork()  // libc wrapper
 
// Kernel space (simplified)
sys_fork()
  → kernel_clone(SIGCHLD, 0, ...)
    → copy_process(...)           // Create PCB, copy resources
      → dup_task_struct()         // Allocate task_struct
      → alloc_pid()               // Get PID
      → copy_mm()                 // Set up address space (COW)
      → copy_files()              // Duplicate file descriptors
      → copy_thread()             // Initialize CPU context
    → wake_up_new_task(p)         // Admit: add to run queue
      → activate_task()
        → enqueue_task()          // Insert in scheduler queue
      → check_preempt_curr()      // Maybe preempt current

Key Implementation Differences

The fundamental difference is that Unix systems use fork()+exec() to create new processes (copying then replacing), while Windows uses CreateProcess() (creating fresh). Fork is elegant and enables powerful patterns like process supervisors and shell pipelines, but Windows' approach can be more efficient for simply launching new programs since it avoids the copy phase entirely.

Summary: The Complete Admit Transition

We've traced the complete journey of a process from creation to schedulability. Let's consolidate the key concepts of the Admit transition.

Key Takeaways

•New → Ready is the Admit transition — It represents the moment a process becomes eligible for CPU scheduling.
•The New state is transitional — Processes exist in New while kernel data structures are being initialized. This phase is typically very brief on modern systems.
•Creation can be triggered multiple ways — System boot, user commands, fork(), and batch submission all ultimately lead to process creation.
•Kernel performs extensive initialization — PID allocation, PCB creation, address space setup, resource inheritance, and credential establishment all occur before admission.
•Copy-on-write makes fork() efficient — Without COW, fork() would be prohibitively expensive for large processes.
•Admission control prevents resource exhaustion — Limits on processes, memory, and other resources prevent runaway process creation from destabilizing the system.
•Ready queue insertion completes the transition — The process becomes visible to the scheduler and may preempt currently running processes.
•Platform implementations vary — Unix fork()+exec() differs fundamentally from Windows CreateProcess(), but both achieve the same end: a running process.

Looking ahead:

With processes successfully admitted to the Ready queue, the next question becomes: how does a process go from waiting in the Ready queue to actually executing on a CPU? This is the Dispatch transition—the handoff from Ready to Running state—which we'll explore in the next page.

Page Complete

You now understand the Admit transition (New → Ready) in comprehensive detail—from the initial creation request through kernel initialization, memory allocation, admission control, and finally Ready queue insertion. Next, we'll examine how the scheduler dispatches processes from Ready to Running.

Admit: New → Ready

From Creation to Eligibility

What You Will Learn

The New State Defined

What characterizes the New state:

Process Characteristics in the New State
Aspect	Status in New State	Completion Required
Process ID (PID)	Assigned	No
Process Control Block (PCB)	Allocated but partially initialized	Yes - fields must be populated
Address Space	Being constructed	Yes - segments must be mapped
Memory Pages	Allocation in progress	Yes - initial pages must be loaded
File Descriptors	Inheritance pending	Yes - must be copied from parent
Credentials	Being established	Yes - UID/GID must be set
CPU Context	Uninitialized	Yes - initial register values needed
Ready Queue Membership	Not present	Yes - must be inserted for scheduling

The New state exists because process creation is not atomic:

Visibility of New state processes:

Historical Context

Triggering the Admit Transition

The journey from New to Ready begins when a process creation request enters the kernel. This request can originate from multiple sources, each with different semantics and implications.

Process Creation Triggers

•System Initialization (Boot) — During boot, the kernel spawns essential system processes (init/systemd, kernel threads). These are admitted immediately with high priority.
•User Request — Interactive shell commands, GUI application launches. The shell calls fork() followed by exec(), or the window manager initiates CreateProcess().
•Process Spawning (fork/clone) — An existing process creates a child. The parent's context becomes the template for the child's initialization.
•Batch Job Submission — In server or HPC environments, job schedulers submit processes for execution. Admission may be deferred based on resource availability.
•Operating System Services — Kernel components may spawn helper processes or kernel threads for specific tasks.

The fork() system call in detail:

On Unix-like systems, the fork() system call is the primary mechanism for process creation. When a process calls fork(), the kernel must:

Verify the calling process has permission to create children
Check system-wide process limits haven't been exceeded
Allocate a new PID and PCB
Copy (or prepare to copy-on-write) the parent's address space
Initialize the child's state based on the parent's state
Return twice: once in the parent (with child's PID) and once in the child (with 0)

fork_example.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
 
int main() {
    printf("Parent process (PID: %d) about to fork\n", getpid());
    
    // At this point, the parent is in Running state
    pid_t pid = fork();
    
    if (pid < 0) {
        // fork() failed - system resource limits or permissions issue
        perror("fork failed");
        return 1;
    }
    
    if (pid == 0) {
        // Child process - just transitioned from New to Ready,
        // now in Running (since we're executing)
        printf("Child process (PID: %d) now running\n", getpid());
        printf("  Parent PID from child's view: %d\n", getppid());
        // Child inherits file descriptors, environment, etc.
    } else {
        // Parent process - continues in Running
        printf("Parent: created child with PID %d\n", pid);
        
        // Parent waits for child to complete
        int status;
        waitpid(pid, &status, 0);
        printf("Parent: child exited with status %d\n", 
               WEXITSTATUS(status));
    }
    
    return 0;
}

The Hidden Complexity

Kernel Actions During Admit

Converting Mermaid diagram...

Detailed breakdown of each step:

Step-by-Step Kernel Operations

•PID Allocation — The kernel assigns a unique Process ID from its PID namespace. This involves consulting a bitmap or counter to find an unused PID. On Linux, PIDs wrap around after reaching the maximum (default 32768, configurable to ~4 million).
•PCB Creation — The kernel allocates memory for the Process Control Block (task_struct in Linux). This is typically allocated from a dedicated slab cache for efficiency. The PCB is the kernel's handle to everything about the process.
•PCB Field Initialization — Critical fields are set: process state (initially NEW), parent PID, creation timestamp, default signal handlers, initial scheduling parameters. For forked processes, many fields are copied from the parent.
•Address Space Setup — The kernel creates a new virtual address space. For fork(), this involves setting up copy-on-write mappings to the parent's pages. For exec(), it prepares to load the executable's segments.
•Initial Memory Allocation — The kernel maps the program's text (code), data, and BSS segments. Stack space is allocated. On-demand paging means not all pages are physically loaded yet.
•Resource Inheritance/Initialization — File descriptors are duplicated (for fork) or set to defaults. IPC resources, credentials (UID, GID, capabilities), and resource limits are established.
•Credential Setup — The process's effective user ID, group ID, and privilege capabilities are set based on the executable's permissions and parent's credentials.
•Ready Queue Insertion — Finally, the process is added to the Ready queue, making it visible to the scheduler. The process state changes from NEW to READY.

Atomicity Considerations

PCB Initialization Deep Dive

PCB Fields Initialized During Admit
Field Category	Specific Fields	Initialization Action
Identity	pid, tgid, parent pid, process group, session	Assigned unique values; parent info copied from caller
State	state, exit_state, flags	Set to TASK_NEW initially, flags indicate creation mode
Scheduling	priority, static_prio, policy, sched_class	Set from parent or defaults; policy inherits or uses default
Memory	mm_struct pointer, address space limits	New mm_struct created; limits inherited from parent
CPU Context	thread_struct (registers, stack pointer)	Initialized for first execution in user space
Timing	start_time, utime, stime	Creation time recorded; CPU times zeroed
File System	fs_struct, files_struct	Current directory inherited; file table duplicated
Signals	signal_struct, sighand_struct, blocked mask	Handler table initialized; inherited blocked signals
Credentials	cred, real_cred	UID/GID from parent or executable's setuid/setgid
Resource Limits	signal->rlim[]	Limits (max files, stack size, etc.) inherited from parent

The Linux task_struct in context:

Allocate thread info and stack — Each process needs kernel stack space
Copy task_struct — Start with parent's structure as template
Initialize unique fields — PID, timestamps, and accounting info
Duplicate or share resources — Based on clone flags (CLONE_FILES, CLONE_VM, etc.)
Set up scheduler data — Enqueue in appropriate scheduling class

pcb_initialization_pseudocode.c
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Simplified view of process creation in Linux kernel
// Actual implementation in kernel/fork.c is ~2000 lines
 
struct task_struct* copy_process(unsigned long clone_flags,
                                  unsigned long stack_start,
                                  struct pt_regs *regs) {
    struct task_struct *p;
    
    // Step 1: Allocate new task_struct from slab cache
    p = dup_task_struct(current);
    if (!p)
        goto fail_allocation;
    
    // Step 2: Initialize unique identity
    p->pid = alloc_pid();      // Unique PID assignment
    p->tgid = p->pid;          // Thread group leader is self
    p->parent = current;        // Parent is calling process
    p->real_parent = current;
    
    // Step 3: Initialize state as NEW (not schedulable yet)
    p->state = TASK_NEW;       // Process in New state
    
    // Step 4: Copy or share resources based on flags
    if (!(clone_flags & CLONE_FILES))
        copy_files(p);         // Independent file descriptors
    if (!(clone_flags & CLONE_VM))
        copy_mm(p);            // Copy-on-write address space
    copy_signal_handlers(p);   // Signal disposition
    copy_credentials(p);       // UID/GID/capabilities
    
    // Step 5: Initialize scheduling parameters
    p->sched_class = fair_sched_class;
    p->prio = current->prio;   // Inherit priority
    p->static_prio = current->static_prio;
    
    // Step 6: Initialize timekeeping
    p->start_time = ktime_get_ns();
    p->utime = p->stime = 0;   // No CPU time yet
    
    // Step 7: Set up CPU context for first switch
    copy_thread(p, regs);      // Set up initial register state
    
    // Step 8: Transition New → Ready
    p->state = TASK_RUNNABLE;  // Now in Ready state
    wake_up_new_task(p);       // Add to run queue
    
    return p;
    
fail_allocation:
    return ERR_PTR(-ENOMEM);
}

The Clone Flags Mechanism

Memory Allocation During Admit

Address Space Components

•Text Segment — Executable code, mapped read-only from the executable file. Usually shared with other instances of the same program.
•Data Segment — Initialized global and static variables. Copied from executable, made writable.
•BSS Segment — Uninitialized globals. Mapped to zero-filled pages on demand.
•Heap — Dynamic allocations. Initially minimal; grows with malloc() calls.
•Stack — Function call frames. Allocated at process creation; grows downward on demand.
•Shared Libraries — Mapped from .so files. Text is shared; data is copy-on-write.

Optimization Techniques

•Copy-on-Write (COW) — Fork doesn't copy physical pages immediately. Both parent and child share pages until one writes.
•Demand Paging — Pages are loaded from disk only when accessed. Initial page table entries are marked invalid.
•Shared Text — Multiple processes running the same program share code pages in physical memory.
•Page Table Cloning — Fork copies page table entries, not actual pages. Very fast operation.
•Memory-Mapped Executables — Executables are mmap'd, allowing the page cache to serve code pages.

Copy-on-Write: The Key to Fast Fork:

Fork() marks all writable pages as read-only in both parent and child
Both processes share the same physical pages initially
When either process writes to a page, a page fault occurs
The kernel allocates a new physical page, copies the content, and resumes
Only pages that are actually modified are ever copied

For processes that fork() and immediately exec() (the common case), COW means almost no memory is ever copied—the child's address space is completely replaced before any COW faults occur.

Memory Overhead: Fork Without vs With COW
Scenario	Without COW	With COW	Improvement
Fork 100MB process (immediate exec)	100MB copied, 100ms	~0MB copied, <1ms	100x faster
Fork 1GB process (child reads only)	1GB copied, 1000ms	~0MB copied, <1ms	1000x faster
Fork 1GB process (child modifies 10MB)	1GB copied, 1000ms	10MB copied, 10ms	100x faster
Fork 1GB process (child modifies 1GB)	1GB copied, 1000ms	1GB copied on demand	Same total, better distribution

Memory Efficiency in Practice

Admission Control Policies

Types of Admission Control

•Immediate Admission — Default on interactive systems. Processes are admitted as soon as basic initialization completes. Provides responsive user experience but may lead to overload.
•Resource-Based Admission — Processes are admitted only if sufficient resources (memory, file descriptors, etc.) are available. Prevents over-commitment but may cause creation failures.
•Load-Based Admission — Admission delayed when system load is high. Used in batch systems and container orchestrators. Smooths workload peaks.
•Priority-Based Admission — Higher-priority processes admitted before lower-priority ones. Ensures important workloads aren't blocked by less critical ones.
•Quota-Based Admission — Users or groups have limits on concurrent processes. Prevents runaway fork bombs and ensures fairness.
•Time-Based Admission — Batch jobs scheduled for specific time windows. Common in HPC and mainframe environments.

Linux resource limits (rlimits):

Linux implements admission control through resource limits. When fork() is called, the kernel checks several limits:

RLIMIT_NPROC: Maximum processes for this user. If exceeded, fork() returns -EAGAIN.
Kernel parameters: pid_max (maximum PIDs), threads-max (maximum kernel threads).
Memory: If not enough memory for basic structures, fork() fails with -ENOMEM.
Cgroup limits: Container environments can limit processes per cgroup.

These checks happen before significant resources are allocated, failing fast if limits would be exceeded.

admission_control_example.sh
Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# View current process limits
ulimit -a
 
# Check user's maximum process limit
ulimit -u
# Example output: 63704
 
# Set maximum processes for current shell and children
ulimit -u 100
 
# View system-wide limits
cat /proc/sys/kernel/pid_max      # Maximum PID value
# Example: 4194304
 
cat /proc/sys/kernel/threads-max  # Maximum total threads
# Example: 126407
 
# View cgroup process limits (if using systemd)
cat /sys/fs/cgroup/user.slice/user-1000.slice/pids.max
# Example: max (unlimited) or specific number
 
# Demonstrate fork failure due to limit
ulimit -u 5  # Set very low limit
# Now try to run many processes
for i in {1..10}; do
    sleep 100 &
done
# Output: bash: fork: retry: Resource temporarily unavailable

Fork Bombs and Protection

Ready Queue Insertion

Ready queue structures:

Modern operating systems don't use a single Ready queue. Instead, they maintain sophisticated data structures optimized for their scheduling algorithms.

Linux's Completely Fair Scheduler (CFS) uses:

A red-black tree per CPU, ordered by 'virtual runtime'
New processes are inserted with a virtual runtime slightly ahead of the current minimum
This gives new processes a fair chance to run soon, but doesn't let them jump the queue

Windows uses:

Per-processor ready queues organized by priority level
32 priority levels, each with its own queue
New processes enter the queue for their priority level

Converting Mermaid diagram...

Scheduling considerations for new processes:

When a new process is admitted, the scheduler must decide several things:

Which CPU's queue? On SMP systems, the kernel chooses a CPU to minimize load imbalance. It may consider:
- Cache locality (prefer parent's CPU for fork, since parent's data may be cached)
- CPU load (choose a less busy CPU)
- NUMA topology (prefer node-local memory)
Queue position? The new process shouldn't unfairly jump ahead of processes that have been waiting. CFS gives new processes a slight bonus but not excessive advantage.
Immediate preemption? If the new process has higher priority than the currently running process, the scheduler sets a flag to trigger preemption at the next safe point.
Wake-up latency? How quickly should the new process get CPU time? Interactive processes benefit from quick wake-up.

The Child Runs First Optimization

Ready Queue Properties by Scheduling Class
Scheduling Class	Queue Structure	New Process Placement	Priority Boost
Real-Time FIFO	Per-priority linked list	End of priority queue	None - runs until blocked
Real-Time RR	Per-priority linked list	End of priority queue	None - gets full time slice
CFS (Normal)	Red-black tree by vruntime	Vruntime = min + slice/2	Small boost for interactivity
Idle	Simple queue	End of queue	Only runs when nothing else needs CPU

Platform-Specific Implementations

The Admit transition is a universal concept, but its implementation varies significantly across operating systems. Let's compare how different platforms handle process admission.

Linux Process Creation:

System calls: fork(), vfork(), clone() - all implemented via kernel_clone()
Key function: copy_process() in kernel/fork.c
State transition: TASK_NEW → TASK_RUNNABLE
Queue insertion: wake_up_new_task() adds to CFS run queue

Unique characteristics:

Extensive use of copy-on-write
Clone flags allow fine-grained resource sharing
Namespaces allow process isolation
Cgroups provide resource limiting

linux_fork_sequence.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Simplified call sequence for fork() in Linux
// User space
fork()  // libc wrapper
 
// Kernel space (simplified)
sys_fork()
  → kernel_clone(SIGCHLD, 0, ...)
    → copy_process(...)           // Create PCB, copy resources
      → dup_task_struct()         // Allocate task_struct
      → alloc_pid()               // Get PID
      → copy_mm()                 // Set up address space (COW)
      → copy_files()              // Duplicate file descriptors
      → copy_thread()             // Initialize CPU context
    → wake_up_new_task(p)         // Admit: add to run queue
      → activate_task()
        → enqueue_task()          // Insert in scheduler queue
      → check_preempt_curr()      // Maybe preempt current

Key Implementation Differences

Summary: The Complete Admit Transition

We've traced the complete journey of a process from creation to schedulability. Let's consolidate the key concepts of the Admit transition.

Key Takeaways

•New → Ready is the Admit transition — It represents the moment a process becomes eligible for CPU scheduling.
•The New state is transitional — Processes exist in New while kernel data structures are being initialized. This phase is typically very brief on modern systems.
•Creation can be triggered multiple ways — System boot, user commands, fork(), and batch submission all ultimately lead to process creation.
•Kernel performs extensive initialization — PID allocation, PCB creation, address space setup, resource inheritance, and credential establishment all occur before admission.
•Copy-on-write makes fork() efficient — Without COW, fork() would be prohibitively expensive for large processes.
•Admission control prevents resource exhaustion — Limits on processes, memory, and other resources prevent runaway process creation from destabilizing the system.
•Ready queue insertion completes the transition — The process becomes visible to the scheduler and may preempt currently running processes.
•Platform implementations vary — Unix fork()+exec() differs fundamentally from Windows CreateProcess(), but both achieve the same end: a running process.

Looking ahead:

Page Complete