P2L4 Thread Design Considerations - Data Structures and Management Flashcards
Threads can be supported at ____ level, at _____ level, or both.
Threads can be supported at user level, at kernel level, or both.
Supporting threads at the kernel level means, …… To do this, the OS ______ maintains some ________, for our threads of data structure to represent threads, and it performs all of the operations like ______, __________, et cetera, in order to allow these threads to share the_______ resources.
Supporting threads at the kernel level means, that the OS kernel itself is multithreaded. To do this, the OS kernel maintains some abstraction, for our threads of data structure to represent threads, and it performs all of the operations like synchronizations, scheduling, et cetera, in order to allow these threads to share the physical resources.
Supporting threads at the user level means that there is a user-level ______, that is linked with the application, and this ______ provides all of the ___________ in the runtime support for threads.
Supporting threads at the user level means that there is a user-level library, that is linked with the application, and this library provides all of the management in the runtime support for threads.
Three ways user-level threads can be mapped onto the underlying kernel level-threads:
- __________
- __________
- __________
Pros and cons?
Three ways user-level threads can be mapped onto the underlying kernel level-threads:
- one-to-one
- many-to-one,
- many-to-many
Pros and cons - TODO
To the user level threads, each kernel level thread looks like a _____.
To the user level threads, each kernel level thread looks like a CPU.
Single threaded process. All of the information for this process such as:
- ______
- ______
- ______
is contained in the PCB
Single threaded process. All of the information for this process such as:
- stack
- register
- virtual address mapping
is contained in the PCB
One-to-One
All of the information for this process is contained in the ____. Whenever the process makes a system call, it traps it into the kernel.
Assuming ___ CPU.
One-to-One
All of the information for this process is contained in the PCB. Whenever the process makes a system call, it traps it into the kernel.
Assuming 1 CPU.
Many-to-many
We don’t want to recreate all of the information in PCB for the multiple kernel level threads so we ____ the PCB.
The PCB will still contain the_______ ________
while another data structure will keep information about the ____ and _____ pointers of the kernel level threads.
Many-to-many
We don’t want to recreate all of the information in PCB for the multiple kernel level threads so we split the PCB.
The PCB will still contain the virtual mappings
while another data structure will keep information about the stack and register pointers of the kernel level threads.
Many to One:
Here the PCB contains the _______ _______ ________ as well as the _____ and _________ information for the kernel level thread.
Many to One:
Here the PCB contains the virtual address mappings as well as the stack and register information for the kernel level thread.
If the process links in a user level threading library, that library will need some way to represent threads, so that it can track thread ________ use and make decisions about thread _______ and synchronization.
The library will maintain some user level thread data structure containing:
- thread _______
- thread _______
- thread _______
If the process links in a user level threading library, that library will need some way to represent threads, so that it can track thread resource use and make decisions about thread scheduling and synchronization.
The library will maintain some user level thread data structure containing:
- thread ids
- thread registers
- thread stacks
Multiple processes relationships
The user level library keeps track all of the user level ______ for a given process.
The OS keeps track of the ______ level threads that execute on behalf of the process.
For each _____ level thread, the OS keeps track of the processes on whose behalf it executes
Multiple processes
The user level library keeps track all of the user level threads for a given process.
The OS keeps track of the kernel level threads that execute on behalf of the process.
For each kernel level thread, the OS keeps track of the processes on whose behalf it executes
Multiple processes
We need to maintain a relationships among these data structures:
- ____ _____ _____ structures
- ______ ______ _____
- _____ _____ ______ structures
Multiple processes
We need to maintain a relationships among these data structures:
- user level thread structures
- process control blocks
- kernel level thread structures
Light process state is …..
information specific to a certain kernel thread (signal mask/sys call args)
Hard process state is …..
information that applies to all threads within a process (virtual address mappings)
We can split up the information in the process control block into ____ process state which is relevant for ___ user level threads in a given process, and _____ process state that is only relevant for a subset of user level threads associated with a particular _____ level thread.
We can split up the information in the process control block into hard process state which is relevant for all user level threads in a given process, and light process state that is only relevant for a subset of user level threads associated with a particular kernel level thread.
If two kernel level threads belong to the same process … information relevant to all threads includes:
the _____ ______ ________ while information relevant to each thread specifically can include things like ______ or system call ________.
When we context switch among the two kernel level threads, we want to preserve some portion of the PCB and swap out the rest.
If two kernel level threads belong to the same process … information relevant to all threads includes:
the virtual address mapping while information relevant to each thread specifically can include things like signals or system call arguments.
When we context switch among the two kernel level threads, we want to preserve some portion of the PCB and swap out the rest.
Give 4 reasons to split up the PCB to multiple data structures
Better scalability: smaller data structures, maintained with pointers
Less overhead: If it’s one big structure, then you need a private copy for each thread even though they may share data. With pointers it’s easy to share datat
Better performance: save and restore only what needs to change on context switch
Easier customization: User-level library only needs to update a portion of the state for customized behavior
What is the name of the data structure that describes the process that the kernel thread is running?
task_struct (in the kthread_worker structure)
struct [kthread\_worker](https://elixir.bootlin.com/linux/v3.17/ident/kthread_worker) { [spinlock\_t](https://elixir.bootlin.com/linux/v3.17/ident/spinlock_t) lock; struct [list\_head](https://elixir.bootlin.com/linux/v3.17/ident/list_head) work\_list; struct [task\_struct](https://elixir.bootlin.com/linux/v3.17/ident/task_struct) \*[task](https://elixir.bootlin.com/linux/v3.17/ident/task); struct [kthread\_work](https://elixir.bootlin.com/linux/v3.17/ident/kthread_work) \*[current\_work](https://elixir.bootlin.com/linux/v3.17/ident/current_work); };
What is the name of the kernel thread structure that’s used in Linux?
kthread_worker
struct [kthread\_worker](https://elixir.bootlin.com/linux/v3.17/ident/kthread_worker) { [spinlock\_t](https://elixir.bootlin.com/linux/v3.17/ident/spinlock_t) lock; struct [list\_head](https://elixir.bootlin.com/linux/v3.17/ident/list_head) work\_list; struct [task\_struct](https://elixir.bootlin.com/linux/v3.17/ident/task_struct) \*[task](https://elixir.bootlin.com/linux/v3.17/ident/task); struct [kthread\_work](https://elixir.bootlin.com/linux/v3.17/ident/kthread_work) \*[current\_work](https://elixir.bootlin.com/linux/v3.17/ident/current_work); };
What is task_struct?
struct [kthread\_worker](https://elixir.bootlin.com/linux/v3.17/ident/kthread_worker) { [spinlock\_t](https://elixir.bootlin.com/linux/v3.17/ident/spinlock_t) lock; struct [list\_head](https://elixir.bootlin.com/linux/v3.17/ident/list_head) work\_list; struct [task\_struct](https://elixir.bootlin.com/linux/v3.17/ident/task_struct) \*[task](https://elixir.bootlin.com/linux/v3.17/ident/task); struct [kthread\_work](https://elixir.bootlin.com/linux/v3.17/ident/kthread_work) \*[current\_work](https://elixir.bootlin.com/linux/v3.17/ident/current_work); };
Describes the process that the kthread_worker (kernel thread) is running
Sun OS
Each kernel level threads that is executing on behalf of a _____ level thread has a _______ ______ data structure associated with it.
Each kernel level threads that is executing on behalf of a user level thread has a lightweight process (LWP) data structure associated with it.
When a thread is a created, the library returns a ________
Is it a direct pointer to the thread data structure? No it’s an ….
When a thread is a created, the library returns a thread id. This id is not a direct pointer to the thread data structure, but is rather an index into an array of thread pointers.
The amount of memory needed for a thread data structure is often almost entirely known __________.
This allows for ______ representation of threads in memory: basically, one right after the other in a _________ section of memory.
The amount of memory needed for a thread data structure is often almost entirely known up front.
This allows for compact representation of threads in memory: basically, one right after the other in a continuous section of memory.
What’s the problem and solution for compact memory representation where the user library does not control stack growth?
However, the user library does not control stack growth. With this compact memory representation, there may be an issue if one thread starts to overrun its boundary and overwrite the data for the next thread. If this happens, the problem is that they error won’t be detected until the overwritten thread starts to run, even though the cause of the problem is the overwriting thread.
The solution is to separate information about each thread by a red zone. The red zone is a portion of the address space that is not allocated. If a thread tries to write to a red zone, the operating system causes a fault.
Why is a thread id an index into an array of thread pointers and not a direct pointer to the thread?
Because if there is a problem with the thread, the value at the index can change to say -1 instead of the pointer just pointing to some corrupt memory.
Describe the pointers in this diagram
Each ______________ structure points to:
- the _______________________ that it corresponds to.
- and the _____, which is ________.
Each kernel level thread structure points to:
- the light weight process that it corresponds to.
- and the stack, which is swappable.
Describe the pointers in this diagram
- A process data structure has information about the _______
- and points to the _______________________
- and points to a _______________________
- A process data structure has information about the user
- and points to the virtual address mapping data structure.
- It also points to a list of kernel level threads.
Describe two ways that user level threads and kernel interact.
In other words, how do user level library and the kernel overcome the lack of insight into each other?
set_concurrency system call: application requests another kernel thread:
notification signal: kernel notifies the user-level library before it blocks the kernel-level threads.
What does a ‘bound’ thread mean?
What is a ‘bound’ thread?
and when is it useful?
The user level library can request that one of its threads be bound to a kernel level thread. This means that this user level thread will always execute on top of a specific kernel level thread.
This may be useful if in turn the kernel level thread is pinned to a particular CPU.
Give and example of when an OS would send a signal from the context of one thread on one CPU to the context of the other thread on the other CPU
Priorities of user level threads: P3 > P2 > P1
- Currently, T2 is holding the mutex and is executing on one CPU.
- T3 wants the mutex, and is currently blocking.
- T1 is running on the other CPU.
- At some point, T2 releases the mutex and T3 becomes runnable.
- T1 needs to be preempted, but we make this realization from the user level thread library as T2 is unlocking the mutex. We need to preempt a thread on a different CPU!
What is an adaptive mutex?
Mutexes which sometimes block and sometimes spin are called adaptive mutexes. These only make sense on multiprocessor systems, since we only want to spin if the owner of the mutex is currently executing in parallel to us.
Mutexes which sometimes block and sometimes spin are called _______ mutexes. These only make sense on ___________ systems.
- For example: T1 holds the mutex and is executing on one CPU.
- T2 and T3 are blocked.
- T4 is executing on the another CPU, and wishes to lock the mutex.
The normal behavior would be to place T4 on the queue associated with the mutex. However, on a multiprocessor system where things can happen in parallel, it may be the case that by the time T4 is placed on the queue, T1 has released the ______ . If the critical section is very short, the more efficient case for T4 is not to block, but just to _____ (trying to acquire the mutex in a ____). If the critical section is long, it makes more sense to _______ (that is, be placed on a queue and retrieved at some later point in time). This is because it takes CPU cycles to spin, and we don’t want to burn through cycles for a long time.
Mutexes which sometimes block and sometimes spin are called adaptive mutexes. These only make sense on multiprocessor systems.
For example: T1 holds the mutex and is executing on one CPU. T2 and T3 are blocked. T4 is executing on the another CPU, and wishes to lock the mutex. The normal behavior would be to place T4 on the queue associated with the mutex. However, on a multiprocessor system where things can happen in parallel, it may be the case that by the time T4 is placed on the queue, T1 has released the mutex. If the critical section is very short, the more efficient case for T4 is not to block, but just to spin (trying to acquire the mutex in a loop). If the critical section is long, it makes more sense to block (that is, be placed on a queue and retrieved at some later point in time). This is because it takes CPU cycles to spin, and we don’t want to burn through cycles for a long time.
