P2L4 Thread Design Considerations - Data Structures And Management

Question 1

Threads can be supported at ____ level, at _____ level, or both.

Answer 1

Threads can be supported at user level, at kernel level, or both.

Question 2

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.

Answer 2

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.

Question 3

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.

Answer 3

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.

Question 4

Three ways user-level threads can be mapped onto the underlying kernel level-threads:

__________
__________
__________
Pros and cons?

Answer 4

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

Question 5

To the user level threads, each kernel level thread looks like a _____.

Answer 5

To the user level threads, each kernel level thread looks like a CPU.

Question 6

Single threaded process. All of the information for this process such as:

______
______
______
is contained in the PCB

Answer 6

Single threaded process. All of the information for this process such as:

stack
register
virtual address mapping
is contained in the PCB

Question 7

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.

Answer 7

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.

Question 8

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.

Answer 8

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.

Question 9

Many to One:

Here the PCB contains the _______ _______ ________ as well as the _____ and _________ information for the kernel level thread.

Answer 9

Many to One:

Here the PCB contains the virtual address mappings as well as the stack and register information for the kernel level thread.

Question 10

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 _______

Answer 10

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

Question 11

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

Answer 11

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

Question 12

Multiple processes

We need to maintain a relationships among these data structures:

____ _____ _____ structures
______ ______ _____
_____ _____ ______ structures

Answer 12

Multiple processes

We need to maintain a relationships among these data structures:

user level thread structures
process control blocks
kernel level thread structures

Question 13

Light process state is …..

Answer 13

information specific to a certain kernel thread (signal mask/sys call args)

Question 14

Hard process state is …..

Answer 14

information that applies to all threads within a process (virtual address mappings)

Question 15

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.

Answer 15

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.

Question 16

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.

Answer 16

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.

Question 17

Give 4 reasons to split up the PCB to multiple data structures

Answer 17

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

Question 18

What is the name of the data structure that describes the process that the kernel thread is running?

Answer 18

task_struct (in the kthread_worker structure)

struct kthread_worker {
spinlock_t lock;
struct list_head work_list;
struct task_struct *task;
struct kthread_work *current_work;
};

Question 19

What is the name of the kernel thread structure that’s used in Linux?

Answer 19

kthread_worker

struct kthread_worker {
spinlock_t lock;
struct list_head work_list;
struct task_struct *task;
struct kthread_work *current_work;
};

Question 20

What is task_struct?

struct kthread_worker {
spinlock_t lock;
struct list_head work_list;
struct task_struct *task;
struct kthread_work *current_work;
};

Answer 20

Describes the process that the kthread_worker (kernel thread) is running

Question 21

What’s does this structure represent?

struct kthread_worker {
spinlock_t lock;
struct list_head work_list;
struct task_struct *task;
struct kthread_work *current_work;
};

Answer 21

a Linux kernel thread

Question 22

Sun OS

Each kernel level threads that is executing on behalf of a _____ level thread has a _______ ______ data structure associated with it.

Answer 22

Each kernel level threads that is executing on behalf of a user level thread has a lightweight process (LWP) data structure associated with it.

Question 23

When a thread is a created, the library returns a ________

Is it a direct pointer to the thread data structure? No it’s an ….

Answer 23

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.

Question 24

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.

Answer 24

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.

Question 25

What’s the problem and solution for compact memory representation where the user library does not control stack growth?

Answer 25

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.

Question 26

Why is a thread id an index into an array of thread pointers and not a direct pointer to the thread?

Answer 26

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.

Question 27

User Level Structures in Solaris 2.0: The thread data structure contains different fields for:

______ context
r______
signal ____
p______
_____ pointer
thread local _____
s____

Answer 27

execution context
registers
signal mask
priority
stack pointer
thread local storage
stack

Question 28

What is this information?

list of kernel level threads
virtual address space
user credentials
signal handlers

Answer 28

Information about the process

Maintained by the kernel

Question 29

What is this information?

user level registers
system call arguments
resource usage info
signal masks

Answer 29

Light weight process

Data that is relevant for some subset of the user threads in a given process.

Question 30

What is this information?

kernel-level registers
stack pointer
scheduling info
pointers to associated LWPs, and CPU structures

Answer 30

information held by the kernel level thread

Question 31

Why is the information in the kernel level thread is not swappable?

Answer 31

The kernel level thread has information about an execution context that is always needed. There are operating system services (for example, scheduler) that need to access information about a thread even when the thread is not active.

As a result, the information in the kernel level thread is not swappable.

The LWP data does not have be present when a process is not running, so its data can be swapped out.

Question 32

The information in the _______________ is not swappable, becaues it has information about an execution context that is always needed For example: _______ information.

Information in the ______________ data does not have to be present when the process is ___ running. So its data can be swapped out.

Answer 32

The information in the kernel level thread is not swappable, becaues it has information about an execution context that is always needed For example: scheduling information.

Information in the light weight process (LWP) data does not have to be present when the process is not running. So its data can be swapped out.

Question 33

What is this information?

current thread
list of kernel level threads
dispatching & interrupt handing information

Answer 33

CPU data structure

Question 34

Describe the pointers in this diagram

Each ______________ structure points to:

the _______________________ that it corresponds to.

and the _____, which is ________.​

Answer 34

Each kernel level thread structure points to:

the light weight process that it corresponds to.
and the stack, which is swappable.​

Question 35

Describe the pointers in this diagram

A process data structure has information about the _______
and points to the _______________________
and points to a _______________________

Answer 35

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.

Question 36

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?

Answer 36

set_concurrency system call: application requests another kernel thread:

notification signal: kernel notifies the user-level library before it blocks the kernel-level threads.

Question 37

What does pthread_setconcurrency(0) do?

Answer 37

instructs the underlying implementation to manage concurrency as it finds appropriate

Question 38

In the pthreads library, which function sets the concurrency level?

Answer 38

The pthread_setconcurrency() function informs the implementation of
the application’s desired concurrency level, specified in new_level.
The implementation takes this only as a hint: POSIX.1 does not
specify the level of concurrency that should be provided as a result
of calling pthread_setconcurrency().

   Specifying new_level as 0 instructs the implementation to manage the
   concurrency level as it deems appropriate.

Question 39

What does a ‘bound’ thread mean?

Question 40

The kernel sees:

________________ threads
_______
_______
The user level library sees:

________________ threads
Available________________

Answer 40

The kernel sees:

Kernel level threads
CPUs
Kernel level scheduler
The user level library sees:

User level threads
Available kernel level threads

Question 41

The kernel sees:

________________ threads
_______
_______
The user level library sees:

________________ threads
Available________________

Answer 41

The kernel sees:

Kernel level threads
CPUs
Kernel level scheduler
The user level library sees:

User level threads
Available kernel level threads

Question 42

What is a ‘bound’ thread?

and when is it useful?

Answer 42

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.

Question 43

Are mutex variables and wait queues visible to the kernel?

Answer 43

No, they are user level constructs

Question 44

What’s one solution to the lack of thread management visibility? (kernel not seeing user library state..)

Answer 44

1:1 mappings

Question 45

The process jumps to the user level library scheduler when:

_______________ explicitly yield
_______ set by the by UL library _______
ULTs call library functions like _____ or _____
blocked threads become ______
The library scheduler may also gain execution in response to certain _______ from timers and/or the kernel.

Answer 45

The process jumps to the user level library scheduler when:

ULTs explicitly yield
Timer set by the by UL library expires
ULTs call library functions like lock/unlock
blocked threads become runnable
The library scheduler may also gain execution in response to certain signals from timers and/or the kernel.

Question 46

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

Answer 46

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!

Question 47

What is an adaptive mutex?

Answer 47

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.

Question 48

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.

Answer 48

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.