Two-Level 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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

/*
 * Two-Level Threading Model Implementation Concepts
 * 
 * This pseudocode illustrates how a Two-Level threading library 
 * manages both bound and unbound threads.
 */
 
#include <pthread.h>
#include <stdbool.h>
 
/* Thread attributes for Two-Level threading */
typedef enum {
    THREAD_SCOPE_PROCESS,    /* Unbound: competes with other user threads */
    THREAD_SCOPE_SYSTEM      /* Bound: competes with all system threads */
} thread_scope_t;
 
typedef struct {
    thread_scope_t scope;    /* Bound or unbound */
    int stack_size;          /* Stack size (smaller for unbound typically) */
    int priority;            /* Thread priority (only meaningful if bound) */
    int cpu_affinity;        /* CPU affinity mask (only meaningful if bound) */
} thread_attr_t;
 
typedef struct user_thread {
    thread_attr_t attr;
    void *stack;
    void *(*start_routine)(void *);
    void *arg;
    
    /* For unbound threads */
    struct user_thread *next_runnable;
    int current_lwp;         /* Which LWP is currently running this, or -1 */
    
    /* For bound threads */
    struct kernel_thread *bound_kthread;  /* Dedicated kernel thread, or NULL */
    
    bool is_bound;
    thread_state_t state;
} user_thread_t;
 
typedef struct kernel_thread {
    pthread_t pthread;       /* Underlying OS thread */
    user_thread_t *running;  /* Currently running user thread (bound) */
    bool is_pool_member;     /* True if part of unbound pool */
    bool is_dedicated;       /* True if dedicated to a bound thread */
} kernel_thread_t;
 
/* Global state */
kernel_thread_t pool_kthreads[MAX_POOL_SIZE];
int pool_size;
user_thread_t *unbound_ready_queue;
pthread_mutex_t scheduler_lock;
 
/*
 * Create a new user thread with specified scope
 */
int thread_create(user_thread_t **thread, thread_attr_t *attr,
                  void *(*start_routine)(void *), void *arg) {
    
    user_thread_t *ut = malloc(sizeof(user_thread_t));
    ut->start_routine = start_routine;
    ut->arg = arg;
    ut->attr = *attr;
    ut->state = RUNNABLE;
    
    if (attr->scope == THREAD_SCOPE_SYSTEM) {
        /*
         * BOUND THREAD: Create a dedicated kernel thread
         * 
         * This is essentially One-to-One semantics for this thread.
         * The user thread is permanently attached to this kernel thread.
         */
        ut->is_bound = true;
        ut->bound_kthread = malloc(sizeof(kernel_thread_t));
        ut->bound_kthread->is_dedicated = true;
        ut->bound_kthread->is_pool_member = false;
        ut->bound_kthread->running = ut;
        
        /* Create the actual OS thread */
        pthread_attr_t pthread_attr;
        pthread_attr_init(&pthread_attr);
        
        /* Set OS-level priority if specified */
        if (attr->priority != 0) {
            struct sched_param param;
            param.sched_priority = attr->priority;
            pthread_attr_setschedparam(&pthread_attr, &param);
            pthread_attr_setinheritsched(&pthread_attr, PTHREAD_EXPLICIT_SCHED);
        }
        
        /* Create dedicated OS thread running this user thread */
        pthread_create(&ut->bound_kthread->pthread, &pthread_attr,
                      bound_thread_wrapper, ut);
        
        /* Set CPU affinity if specified */
        if (attr->cpu_affinity >= 0) {
            cpu_set_t cpuset;
            CPU_ZERO(&cpuset);
            CPU_SET(attr->cpu_affinity, &cpuset);
            pthread_setaffinity_np(ut->bound_kthread->pthread,
                                  sizeof(cpuset), &cpuset);
        }
        
    } else {
        /*
         * UNBOUND THREAD: Add to the Many-to-Many pool
         * 
         * This thread will be scheduled by the user-level scheduler
         * onto whichever pool kernel thread is available.
         */
        ut->is_bound = false;
        ut->bound_kthread = NULL;
        ut->current_lwp = -1;
        
        /* Allocate (small) stack for unbound thread */
        ut->stack = malloc(attr->stack_size);
        initialize_stack(ut);
        
        /* Add to user-level ready queue */
        pthread_mutex_lock(&scheduler_lock);
        ut->next_runnable = unbound_ready_queue;
        unbound_ready_queue = ut;
        
        /* Wake a pool thread if any are idle */
        wake_idle_pool_thread();
        pthread_mutex_unlock(&scheduler_lock);
    }
    
    *thread = ut;
    return 0;
}
 
/*
 * Wrapper for bound threads - runs directly on dedicated kernel thread
 */
void *bound_thread_wrapper(void *arg) {
    user_thread_t *ut = (user_thread_t *)arg;
    
    /* Bound thread executes directly - no user-level scheduling */
    void *result = ut->start_routine(ut->arg);
    
    /* Thread complete - cleanup dedicated kernel thread */
    ut->state = TERMINATED;
    return result;
}
 
/*
 * Pool thread main loop - runs unbound threads via Many-to-Many scheduling
 */
void *pool_thread_loop(void *arg) {
    kernel_thread_t *kthread = (kernel_thread_t *)arg;
    
    while (true) {
        user_thread_t *ut = get_next_unbound_thread();
        
        if (ut != NULL) {
            /* Context switch to this unbound user thread */
            ut->current_lwp = kthread - pool_kthreads;
            kthread->running = ut;
            
            switch_to_user_thread(kthread, ut);
            
            /* Returned from user thread */
            kthread->running = NULL;
            handle_unbound_thread_return(ut);
        } else {
            /* No work - park and wait for new threads */
            wait_for_work(kthread);
        }
    }
}
 
/*
 * Yield for unbound threads - gives scheduler opportunity to switch
 */
void thread_yield(void) {
    user_thread_t *current = get_current_thread();
    
    if (current->is_bound) {
        /*
         * Bound thread: yield is a kernel operation
         * Let OS scheduler decide what runs next
         */
        sched_yield();
    } else {
        /*
         * Unbound thread: yield to user-level scheduler
         * Switch to another unbound thread on this pool thread
         */
        current->state = RUNNABLE;
        
        pthread_mutex_lock(&scheduler_lock);
        current->next_runnable = unbound_ready_queue;
        unbound_ready_queue = current;
        pthread_mutex_unlock(&scheduler_lock);
        
        /* Return to pool thread loop to schedule next */
        switch_to_scheduler();
    }
}

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

/*
 * POSIX Thread Scope Example
 * 
 * Demonstrates how to create bound vs unbound threads using 
 * the standard POSIX API. Note: On Linux (NPTL), both scopes 
 * are One-to-One, but this API was designed for Two-Level systems.
 */
 
#include <pthread.h>
#include <stdio.h>
 
void *high_priority_work(void *arg) {
    /* This thread needs guaranteed scheduling */
    printf("Bound thread executing
");
    return NULL;
}
 
void *bulk_worker(void *arg) {
    /* This thread can share resources */
    printf("Unbound thread executing
");
    return NULL;
}
 
int main(void) {
    pthread_t bound_thread, unbound_thread;
    pthread_attr_t attr;
    
    /* Create a bound (system scope) thread */
    pthread_attr_init(&attr);
    
    /*
     * PTHREAD_SCOPE_SYSTEM: Request a dedicated kernel thread
     * 
     * On Two-Level systems (old Solaris, HP-UX):
     *   - Creates a dedicated LWP for this thread
     *   - Thread is scheduled by kernel scheduler
     *   - Can set real-time priority, CPU affinity
     * 
     * On One-to-One systems (Linux NPTL, Windows):
     *   - All threads are already system scope
     *   - This is the default behavior
     */
    pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
    pthread_create(&bound_thread, &attr, high_priority_work, NULL);
    
    /* Create an unbound (process scope) thread */
    pthread_attr_init(&attr);
    
    /*
     * PTHREAD_SCOPE_PROCESS: Can share kernel thread with other threads
     * 
     * On Two-Level systems:
     *   - Thread is multiplexed onto a pool of LWPs
     *   - Scheduled by user-level library, not kernel
     *   - Lightweight but less predictable latency
     * 
     * On One-to-One systems:
     *   - May fail or be ignored (NPTL only supports SYSTEM)
     *   - Linux typically returns ENOTSUP for PROCESS scope
     */
    int result = pthread_attr_setscope(&attr, PTHREAD_SCOPE_PROCESS);
    if (result == ENOTSUP) {
        printf("Process scope not supported, using system scope
");
        pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
    }
    pthread_create(&unbound_thread, &attr, bulk_worker, NULL);
    
    pthread_join(bound_thread, NULL);
    pthread_join(unbound_thread, NULL);
    
    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

package main
 
import (
    "fmt"
    "runtime"
    "sync"
)
 
/*
 * Go's LockOSThread: Two-Level Model in Modern Go
 * 
 * By default, goroutines are not bound to OS threads (M:N).
 * LockOSThread binds the goroutine to its current OS thread,
 * creating bound-thread semantics for that specific goroutine.
 */
 
func main() {
    var wg sync.WaitGroup
    
    // Regular goroutines - unbound, multiplexed (M:N)
    for i := 0; i < 100; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            // This goroutine may run on any OS thread
            // Runtime freely migrates between threads
            doWork(id)
        }(i)
    }
    
    // Bound goroutine - locked to OS thread
    wg.Add(1)
    go func() {
        defer wg.Done()
        
        /*
         * LockOSThread: Bind this goroutine to its current OS thread
         * 
         * Use cases:
         * - CGO calls to C code that uses thread-local storage
         * - GUI toolkit integration (Cocoa, GTK require main thread)
         * - OpenGL contexts (thread-specific)
         * - Calling Windows APIs that require specific threading
         * 
         * This goroutine will NOT be migrated to other OS threads.
         * The OS thread will NOT run other goroutines while locked.
         */
        runtime.LockOSThread()
        defer runtime.UnlockOSThread()
        
        fmt.Println("Bound goroutine: running on dedicated OS thread")
        
        // This is now effectively One-to-One for this goroutine
        // Good for: CGO, thread-local state, OS-thread-specific APIs
        callOsThreadSensitiveCode()
    }()
    
    wg.Wait()
}
 
func doWork(id int) {
    // Simulated work
    _ = id * 2
}
 
func callOsThreadSensitiveCode() {
    // Placeholder for thread-sensitive operations
    fmt.Println("Executing OS-thread-sensitive code safely")
}
 
/*
 * This demonstrates Two-Level thinking in a modern context:
 * 
 * - 100 "unbound" goroutines share GOMAXPROCS OS threads (M:N)
 * - 1 "bound" goroutine has a dedicated OS thread (1:1)
 * 
 * Most work is efficient M:N, but when needed, we can 
 * guarantee OS thread dedication for specific goroutines.
 */