One-to-One Model

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/*
 * Thread creation in the One-to-One Model
 * 
 * This example traces what happens when you create a POSIX thread
 * in a modern One-to-One implementation like Linux NPTL.
 */
 
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
 
/* Thread function to demonstrate kernel thread identity */
void *thread_function(void *arg) {
    int thread_num = *(int *)arg;
    
    /*
     * Key insight: In One-to-One, each pthread has its own
     * kernel thread ID (TID). We can query it directly:
     */
    pid_t tid = syscall(SYS_gettid);  /* Get this thread's kernel ID */
    pid_t pid = getpid();              /* Get process ID (same for all threads) */
    
    printf("Thread %d: pthread_t = %lu, kernel TID = %d, PID = %d
",
           thread_num, (unsigned long)pthread_self(), tid, pid);
    
    /*
     * The kernel TID proves this thread exists at the kernel level.
     * It can be scheduled independently, preempted, and will appear
     * in /proc/[pid]/task/[tid] on Linux.
     */
    
    /* Do some work... */
    sleep(1);
    
    return NULL;
}
 
int main(void) {
    pthread_t threads[4];
    int thread_args[4];
    
    printf("Main thread: TID = %ld, PID = %d
", 
           syscall(SYS_gettid), getpid());
    
    /*
     * Each pthread_create() call triggers:
     * 1. A clone() system call with CLONE_THREAD flag
     * 2. Kernel allocates thread control block (task_struct)
     * 3. Kernel allocates kernel stack (typically 8-16KB)
     * 4. Thread added to scheduler's ready queue
     * 5. New thread may immediately preempt creator
     */
    for (int i = 0; i < 4; i++) {
        thread_args[i] = i;
        
        /* This system call creates a REAL kernel thread */
        int result = pthread_create(&threads[i], NULL, 
                                    thread_function, &thread_args[i]);
        if (result != 0) {
            fprintf(stderr, "Failed to create thread %d
", i);
            return 1;
        }
    }
    
    /* Wait for all threads */
    for (int i = 0; i < 4; i++) {
        pthread_join(threads[i], NULL);
    }
    
    return 0;
}
 
/*
 * Sample output (TIDs will vary):
 * 
 * Main thread: TID = 1234, PID = 1234
 * Thread 0: pthread_t = 140123456789760, kernel TID = 1235, PID = 1234
 * Thread 1: pthread_t = 140123448397056, kernel TID = 1236, PID = 1234
 * Thread 2: pthread_t = 140123440004352, kernel TID = 1237, PID = 1234
 * Thread 3: pthread_t = 140123431611648, kernel TID = 1238, PID = 1234
 * 
 * Note: Each thread has a unique kernel TID, but shares the same PID.
 * These are real kernel-scheduled entities, visible in:
 *   - /proc/1234/task/ (one directory per TID)
 *   - top -H (shows individual threads)
 *   - ps -eLf (lists all threads)
 */

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

/*
 * Demonstration: Parallel Matrix Multiplication with One-to-One Threading
 * 
 * This example shows how One-to-One threading enables true parallelism.
 * We multiply two 1000x1000 matrices using varying thread counts.
 */
 
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 1000  /* Matrix dimension */
 
double A[N][N], B[N][N], C[N][N];
int num_threads;
 
typedef struct {
    int start_row;
    int end_row;
} thread_args_t;
 
/* Each thread computes a portion of rows */
void *matrix_multiply_worker(void *arg) {
    thread_args_t *args = (thread_args_t *)arg;
    
    for (int i = args->start_row; i < args->end_row; i++) {
        for (int j = 0; j < N; j++) {
            C[i][j] = 0.0;
            for (int k = 0; k < N; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    
    return NULL;
}
 
double parallel_multiply(int thread_count) {
    pthread_t threads[thread_count];
    thread_args_t args[thread_count];
    
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    
    /* Divide rows among threads */
    int rows_per_thread = N / thread_count;
    
    for (int i = 0; i < thread_count; i++) {
        args[i].start_row = i * rows_per_thread;
        args[i].end_row = (i == thread_count - 1) ? N : (i + 1) * rows_per_thread;
        
        /*
         * Each pthread_create creates a KERNEL thread.
         * These kernel threads can run truly in parallel
         * on separate CPU cores.
         */
        pthread_create(&threads[i], NULL, matrix_multiply_worker, &args[i]);
    }
    
    for (int i = 0; i < thread_count; i++) {
        pthread_join(threads[i], NULL);
    }
    
    clock_gettime(CLOCK_MONOTONIC, &end);
    
    double elapsed = (end.tv_sec - start.tv_sec) + 
                     (end.tv_nsec - start.tv_nsec) / 1e9;
    
    return elapsed;
}
 
int main(void) {
    /* Initialize matrices with random values */
    srand(42);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = (double)rand() / RAND_MAX;
            B[i][j] = (double)rand() / RAND_MAX;
        }
    }
    
    printf("Matrix multiplication: %dx%d matrices
 
", N, N);
    printf("Threads  Time(s)    Speedup
");
    printf("-------  --------   -------
");
    
    double base_time = 0;
    
    for (int threads = 1; threads <= 16; threads *= 2) {
        double time = parallel_multiply(threads);
        
        if (threads == 1) {
            base_time = time;
            printf("%-7d  %-8.3f   1.00x
", threads, time);
        } else {
            double speedup = base_time / time;
            printf("%-7d  %-8.3f   %.2fx
", threads, time, speedup);
        }
    }
    
    /*
     * Sample output on 8-core system:
     * 
     * Matrix multiplication: 1000x1000 matrices
     * 
     * Threads  Time(s)    Speedup
     * -------  --------   -------
     * 1        4.523      1.00x
     * 2        2.315      1.95x
     * 4        1.189      3.80x
     * 8        0.621      7.28x
     * 16       0.598      7.56x  (diminishing returns beyond core count)
     * 
     * This scaling is IMPOSSIBLE with Many-to-One threading!
     */
    
    return 0;
}

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

/*
 * Demonstration: Measuring One-to-One Thread Creation Overhead
 * 
 * This program creates threads in batches and measures the cost.
 * It demonstrates why One-to-One is unsuitable for extremely
 * high thread counts.
 */
 
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/resource.h>
 
void *empty_thread(void *arg) {
    /* Thread does nothing - we're measuring creation overhead */
    return NULL;
}
 
void measure_thread_creation(int num_threads) {
    pthread_t *threads = malloc(sizeof(pthread_t) * num_threads);
    
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    
    /* Create all threads */
    for (int i = 0; i < num_threads; i++) {
        int result = pthread_create(&threads[i], NULL, empty_thread, NULL);
        if (result != 0) {
            printf("Failed at thread %d: resource exhausted
", i);
            num_threads = i;  /* Use actual count for cleanup */
            break;
        }
    }
    
    clock_gettime(CLOCK_MONOTONIC, &end);
    double creation_time = (end.tv_sec - start.tv_sec) + 
                          (end.tv_nsec - start.tv_nsec) / 1e9;
    
    /* Join all threads */
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (int i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    double join_time = (end.tv_sec - start.tv_sec) + 
                      (end.tv_nsec - start.tv_nsec) / 1e9;
    
    /* Memory usage */
    struct rusage usage;
    getrusage(RUSAGE_SELF, &usage);
    
    printf("%8d threads: create=%.3fs (%.1fμs/thread), "
           "join=%.3fs, peak_mem=%ldKB
",
           num_threads, creation_time, 
           (creation_time / num_threads) * 1e6,
           join_time, usage.ru_maxrss);
    
    free(threads);
}
 
int main(void) {
    printf("One-to-One Thread Creation Overhead
 
");
    
    /*
     * Test with increasing thread counts.
     * Watch for:
     * 1. Increasing per-thread creation time (scheduler overhead)
     * 2. Memory usage scaling
     * 3. Eventual failure at high counts
     */
    
    int counts[] = {100, 1000, 5000, 10000, 20000, 50000};
    int num_tests = sizeof(counts) / sizeof(counts[0]);
    
    for (int i = 0; i < num_tests; i++) {
        measure_thread_creation(counts[i]);
    }
    
    /*
     * Sample output on Linux system with 32GB RAM:
     * 
     * One-to-One Thread Creation Overhead
     *
     *      100 threads: create=0.002s (16.7μs/thread), join=0.001s, peak_mem=5432KB
     *     1000 threads: create=0.021s (20.5μs/thread), join=0.012s, peak_mem=14568KB
     *     5000 threads: create=0.118s (23.6μs/thread), join=0.072s, peak_mem=51208KB
     *    10000 threads: create=0.267s (26.7μs/thread), join=0.159s, peak_mem=98632KB
     *    20000 threads: create=0.612s (30.6μs/thread), join=0.347s, peak_mem=193476KB
     *    50000 threads: Failed at thread 32751: resource exhausted
     * 
     * Key observations:
     * - Per-thread creation time increases with count (scheduler overhead)
     * - Memory grows roughly linearly (~10KB kernel per thread)
     * - System limits cap maximum thread count
     */
    
    return 0;
}