Thread.md (5669B)
1 # Thread 2 3 **Source:** CS 6200 4 5 **Chapter:** P2L2 6 7 **Definition:** A thread is an active entity that executes a unit of a process. 8 9 Threads are part of the same virtual address space as the process that contains them, but each thread has a per-thread execution context, contained within the process control block. 10 11 Threads have a non-zero overhead, but they have a lesser overhead than processes because they don't require their own address spaces, only their own execution contexts. Additionally, threads can use shared variables in the same address space for communication between threads which is cheaper than the IPC alternatives. 12 13 ## Single CPU Benefits 14 15 If idle time is greater than the cost of context switching twice it makes sense to context switch to another thread (or process). Since creating the new virtual to actual address space mapping is one of the most costly parts of context switching between processes, using threads can be more efficient than using processes. 16 17 ## Needed to Support Threads 18 19 ### Data Structure 20 21 A thread type should include a thread identifier, register values (PC, SP, registers), the stack, and additional attributes. These additional attributes can be used by a thread management system to better schedule thread execution. 22 23 ### Creation / Management 24 25 Below is one solution to thread management / creation: 26 27 - Fork(proc, args) 28 - This call creates a thread that will execute the procedure proc with the arguments args 29 - This is **not** the Unix syscall Fork. 30 - The new thread data structure is initialized with PC = proc and stack = args 31 - Join(thread) 32 - When a parent thread calls join with the child thread ID, the parent will be blocked until the child completes 33 - Join will return the results from the child to the parent thread in a well-defined location in memory 34 - All resources allocated for the child will be freed 35 36 ### Synchronization 37 38 - [Mutexes](Mutex.md) are useful for synchronizing access to memory used by different processes at the same time. 39 40 ## Kernel and User-Level 41 42 ### Kernel 43 44 Kernel level threads are managed by the kernel and the kernel level scheduler. As such, it is up to the Kernel to do the mapping to physical CPU cores. 45 46 ### User-Level 47 48 User-level threads are implemented by software libraries. 49 50 #### One-to-one 51 52 In the one-to-one model user-level threads are mapped directly to kernel level threads. This means the OS can see the user-level threads and can do synchronization. 53 54 The drawback is that each operation must go through the kernel via a syscall (can be slow). Also, since we rely on the kernel, we are limited by the kernel level policies (e.g. limits on # of threads or scheduling options). 55 56 #### Many-to-one 57 58 User level threads are all mapped to the same kernel level thread. This is implemented by a threading library. 59 60 The benefit is portability because everything is done in the library, without concern for the underlying kernel. We also don't have to do lots of costly syscalls. 61 62 A drawback is the OS doesn't know about these threads so blocking calls will block the entire process. 63 64 #### Many-to-many 65 66 This is a system where some user-level threads are mapped to some kernel level threads. This can take advantage of the benefits from both approaches above. 67 68 Despite this, more complex coordination between the user-level thread manager and the kernel must be implemented. 69 70 ## Patterns 71 72 ### Boss-worker 73 74 The boss is responsible for assigning work to the workers. The workers are then responsible for completing their subset of the work (this work can be generalized or specialized to take advantage of locality). A downside of this is the throughput of the system can be limited by the boss thread. 75 76 We often implement this with a queue where the boss adds to the queue and the workers pop from the queue. This requires synchronization, but limits the work required by the boss because it doesn't have to track the state of each worker. 77 78 With this pattern, we have a pool of workers (threads) which can be defined statically or dynamically. 79 80 ### Pipeline 81 82 Threads are assigned to a subtask of the system. The entire task is then done by a pipeline of threads. 83 84 This takes advantage of locality and allows processing many tasks at the same time, but the throughput is limited by the weakest link in the pipeline. To combat these inequalities, we can use a thread pool to increase the threads for a given step. 85 86 ### Layered 87 88 Each layer has a group of related subtasks. Each full task must pass up and down through all layers as the logical groupings of subtasks needn't be ordered. 89 90 ## Thread Management 91 92 Consider a process with 4 user-level threads which will only be running on 2 kernel-level threads at any given time. When the process starts, the kernel will give the process some number of kernel-level threads. The process can then request another kernel level thread with the `set_concurrency` syscall from the kernel. 93 94 If the above process blocked both threads with IO operations, it would be useful for the other user-level threads to step in and execute their functionality instead of blocking both kernel level threads. To do this, the kernel can send a signal to the user-level library, informing it the threads have blocked. The library can then look at it's run queue and request more kernel level threads to continue execution. Once IO completes, the kernel might notice one of the threads has remained idle for some time. As such, the kernel may notify the user-level library that the thread may no longer be used by the process. 95 96 **Pinning:** is when a user-level thread requests to be associated with a singular kernel-level thread.