Process State Transitions

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

# View process states with ps
ps aux | head -1
# USER  PID %CPU %MEM    VSZ   RSS TTY   STAT  START   TIME COMMAND
 
# STAT column meanings:
# S = Interruptible sleep (waiting for event)
# D = Uninterruptible sleep (usually I/O)
# R = Running or runnable (on run queue)
# T = Stopped (by signal or debugger)
# Z = Zombie (terminated but not reaped)
 
# Find all uninterruptible (D state) processes
ps aux | awk '$8 ~ /D/'
# These processes are stuck waiting for I/O
# Common for slow NFS mounts or failing disks
 
# Count processes in each state
ps -eo stat | sort | uniq -c | sort -rn
#  150 S   <- Sleeping (interruptible)
#   23 R   <- Running/runnable  
#    5 D   <- Uninterruptible sleep
#    2 Z   <- Zombies
 
# Detailed scheduling info for sleeping process
cat /proc/<pid>/status | grep State
# State:  S (sleeping)
 
# What is a process waiting for?
cat /proc/<pid>/stack
# Shows kernel stack trace - reveals blocking call

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
52
53
54
55
56
57
58
59
60
61
62

// Common blocking system calls and their wait conditions
 
// FILE I/O BLOCKING
ssize_t n = read(fd, buf, size);
// Blocks until: data available, EOF, or error
// Wait queue: associated with the file descriptor / device
 
ssize_t n = write(fd, buf, size);
// Blocks until: buffer space available or error
// Can block on slow devices, full pipes, network congestion
 
// NETWORK BLOCKING  
int client = accept(sockfd, NULL, NULL);
// Blocks until: incoming connection arrives
// Server spends most time blocked here
 
ssize_t n = recv(sockfd, buf, size, 0);
// Blocks until: data arrives on socket
// May block indefinitely waiting for peer
 
int result = connect(sockfd, addr, len);
// Blocks until: connection established or fails (timeout)
// TCP handshake takes multiple round-trips
 
// SYNCHRONIZATION BLOCKING
pthread_mutex_lock(&mutex);
// Blocks until: mutex becomes available
// May block indefinitely if holder doesn't release
 
sem_wait(&semaphore);
// Blocks until: semaphore count > 0
// Classic producer-consumer synchronization
 
// PROCESS BLOCKING
pid_t pid = wait(&status);
// Blocks until: any child terminates
// Parent often waits for children to complete
 
int result = pause();
// Blocks until: signal is delivered
// Unconditional block waiting for signal
 
// TIMER BLOCKING
unsigned remain = sleep(5);
// Blocks for: specified seconds
// Returns early if signal interrupts
 
int result = nanosleep(&req, &rem);
// Blocks for: specified nanoseconds
// Higher precision than sleep()
 
// MULTIPLEXED BLOCKING
int ready = select(nfds, &reads, &writes, &excepts, &timeout);
// Blocks until: any of multiple FDs is ready, or timeout
// Foundation of event-driven I/O
 
int ready = poll(fds, nfds, timeout);
// Similar to select, different interface
 
int nready = epoll_wait(epfd, events, max, timeout);
// Linux-specific, scalable event interface
// Efficiently handles thousands of connections

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

// Linux wait queue implementation
// Simplified from include/linux/wait.h and kernel/sched/wait.c
 
// Wait queue head - attached to the resource being waited on
struct wait_queue_head {
    spinlock_t lock;               // Protects the list
    struct list_head head;         // List of waiting processes
};
 
// Wait queue entry - one per waiting process
struct wait_queue_entry {
    unsigned int flags;            // WQ_FLAG_* flags
    struct task_struct *private;   // The process waiting
    wait_queue_func_t func;        // Wakeup function
    struct list_head entry;        // Links into wait_queue_head
};
 
// Typical blocking pattern: wait_event macro
#define wait_event(wq_head, condition)                          \
do {                                                            \
    if (condition)                                              \
        break;                                                  \
    DEFINE_WAIT(wait);                                          \
    for (;;) {                                                  \
        prepare_to_wait(&wq_head, &wait, TASK_INTERRUPTIBLE);   \
        if (condition)                                          \
            break;                                              \
        schedule();  /* Block here until woken */               \
    }                                                           \
    finish_wait(&wq_head, &wait);                               \
} while (0)
 
// Add process to wait queue and set state
void prepare_to_wait(wait_queue_head_t *wq, 
                     wait_queue_entry_t *wait, 
                     int state) {
    spin_lock(&wq->lock);
    
    // Only add to queue if not already there
    if (list_empty(&wait->entry))
        list_add(&wait->entry, &wq->head);
    
    // Set process state to sleeping
    set_current_state(state);
    
    spin_unlock(&wq->lock);
}
 
// Wake up processes on a wait queue
void wake_up(wait_queue_head_t *wq) {
    wait_queue_entry_t *curr;
    
    spin_lock(&wq->lock);
    
    list_for_each_entry(curr, &wq->head, entry) {
        // Call the wakeup function for each waiter
        curr->func(curr, TASK_NORMAL, 0, NULL);
    }
    
    spin_unlock(&wq->lock);
}
 
// Default wakeup function
int default_wake_function(wait_queue_entry_t *wait) {
    // Move process from waiting to ready
    return try_to_wake_up(wait->private, TASK_NORMAL);
}

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

// Pseudocode for read() system call implementation
// Shows the blocking path in detail
 
ssize_t sys_read(int fd, char __user *buf, size_t count) {
    struct file *file = get_file(fd);
    struct device *dev = file->device;
    
    // 1. Check if data is already buffered
    if (device_has_data(dev)) {
        // Fast path: data available, no blocking
        ssize_t n = copy_to_user(buf, dev->buffer, count);
        return n;
    }
    
    // 2. No data available - must wait
    // Submit I/O request to device
    submit_io_request(dev, count);
    
    // 3. Block until data arrives
    DEFINE_WAIT(wait);
    
    for (;;) {
        // Add ourselves to device's wait queue
        prepare_to_wait(&dev->wait_queue, &wait, 
                       TASK_INTERRUPTIBLE);
        
        // Double-check if data arrived while setting up
        if (device_has_data(dev))
            break;
        
        // Check for pending signals (interruptible sleep)
        if (signal_pending(current)) {
            finish_wait(&dev->wait_queue, &wait);
            return -EINTR;  // Interrupted by signal
        }
        
        // Actually block - give up CPU
        // Process state changes: Running → Waiting
        schedule();
        
        // We return here when woken up
        // Loop back to check if condition is met
    }
    
    // 4. Remove from wait queue
    finish_wait(&dev->wait_queue, &wait);
    
    // 5. Data is now available
    ssize_t n = copy_to_user(buf, dev->buffer, count);
    
    return n;
}
 
// In the device driver's interrupt handler:
irqreturn_t device_interrupt_handler(int irq, void *dev_id) {
    struct device *dev = dev_id;
    
    // Device completed I/O, data is ready
    dev->data_ready = true;
    
    // Wake up anyone waiting on this device
    wake_up(&dev->wait_queue);
    // All waiters moved: Waiting → Ready
    
    return IRQ_HANDLED;
}

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

#include <sys/epoll.h>
#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
 
// Event-driven server using epoll
int main() {
    int epfd = epoll_create1(0);
    
    // Add server socket
    struct epoll_event ev;
    ev.events = EPOLLIN;
    ev.data.fd = server_socket;
    epoll_ctl(epfd, EPOLL_CTL_ADD, server_socket, &ev);
    
    struct epoll_event events[MAX_EVENTS];
    
    while (1) {
        // Block until any registered FD has events
        // This single process can handle thousands of connections
        int nready = epoll_wait(epfd, events, MAX_EVENTS, -1);
        // Process blocks here until:
        // - A client sends data
        // - A new connection arrives
        // - A write becomes possible
        
        for (int i = 0; i < nready; i++) {
            int fd = events[i].data.fd;
            
            if (fd == server_socket) {
                // New connection - accept it
                int client = accept(server_socket, NULL, NULL);
                // Set non-blocking and add to epoll
                fcntl(client, F_SETFL, O_NONBLOCK);
                ev.events = EPOLLIN | EPOLLET;
                ev.data.fd = client;
                epoll_ctl(epfd, EPOLL_CTL_ADD, client, &ev);
            } else {
                // Client ready for I/O - handle it
                // Non-blocking read won't block since epoll
                // said it's ready
                handle_client(fd);
            }
        }
    }
}

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <pthread.h>
#include <semaphore.h>
 
// Example: Blocking on a mutex
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
 
void critical_section() {
    // If lock is held by another thread, we BLOCK here
    // Thread moves to Waiting state until lock is released
    pthread_mutex_lock(&lock);
    
    // ... critical section work ...
    
    pthread_mutex_unlock(&lock);
    // Other waiting threads may now wake up
}
 
// Example: Blocking on a semaphore (producer-consumer)
sem_t items;
 
void consumer() {
    for (;;) {
        // If semaphore count is 0, BLOCK here
        // Wait until producer adds an item
        sem_wait(&items);
        
        consume_item();
    }
}
 
void producer() {
    for (;;) {
        produce_item();
        
        // Increment semaphore, potentially waking consumer
        sem_post(&items);
    }
}
 
// Example: Blocking on condition variable
pthread_mutex_t cv_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
int ready = 0;
 
void waiter() {
    pthread_mutex_lock(&cv_lock);
    
    while (!ready) {
        // Release lock and block atomically
        // Thread waits until signaled AND lock reacquired
        pthread_cond_wait(&cv, &cv_lock);
        // When we return, we hold lock again
    }
    
    process_data();
    pthread_mutex_unlock(&cv_lock);
}
 
void signaler() {
    pthread_mutex_lock(&cv_lock);
    ready = 1;
    pthread_cond_signal(&cv);  // Wake one waiter
    // pthread_cond_broadcast(&cv);  // Wake ALL waiters
    pthread_mutex_unlock(&cv_lock);
}

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

# System-wide I/O wait percentage
top -bn1 | grep Cpu
# Shows: %us user, %sy system, %wa I/O wait
 
# If %wa (I/O wait) is high, processes are blocking on I/O
 
# Per-device I/O statistics
iostat -x 1
# avgqu-sz: Average queue length (processes waiting)
# await: Average wait time (ms)
# %util: Device utilization
 
# Find processes in I/O wait (D state)
ps aux | awk '$8 ~ /D/ {print}'
# These processes are blocked on I/O
 
# What is a specific process waiting for?
cat /proc/<pid>/wchan
# Shows the kernel function where process is sleeping
 
# More detail with stack trace
cat /proc/<pid>/stack
# Shows full kernel stack trace
 
# Monitor block layer I/O
sudo bpftrace -e 'tracepoint:block:block_rq_insert { 
    @[comm] = count(); 
}'
# Shows which processes are issuing I/O
 
# I/O wait breakdown by process
pidstat -d 1
# Shows per-process disk I/O and wait states