P2L4: Thread Design Considerations

Question 1

Name the conceptual data structures that are needed in the user and kernel space for a thread abstraction (should not be all in on process-level PCB). Not for SunOs.

Answer 1

• User thread structure (user-level thread ID, user-level stack pointer, user-level registry values)
• PCB with “hard”process state (virtual address mappings)
• PCB with “light”process state ( only relevant for a subset of user-level threads** that are currently scheduled on ONE kernel level thread - signal mask + syscall arguments)
• Struct for the Kernel level thread (point to hard process state PCB for virtual address mappings (shared) , own stack + own register values such as program counter)
• CPU struct

Question 2

Why does a modern OS typically maintain the information about the execution context of processes and threads in the system in several data structures?

Answer 2

The datastrucuture for the PCB of a process are split up!

• Overhead: smaller memory footprint. Shared data can be referenced instead of copied.
• Scalability: Fat datastructure is large + needs to be copied for each thread (even though they share information) when created newly
• Performance: Context switch faster (less data to save and reload from memory. Not the virtual address space)
• Flexibility: To many parallel writers if only one datastructure
  
  • makes locking inefficient
• User-level thread library only needs to update a smaller portion (not the whole PCB) via well-defined interface from user level

Question 3

Name examples when Kernel and Userspace need to coordinate for thread management

Answer 3

• Kernel signals thread librarybefore blocking thread => ULT library can use system call to create additional kernel thread
• Kernel notify thread library that it removed one kernel level thread (e.g idling too much)

Question 4

What is the difference between CPU/Thread Pinning and bound threads?

Answer 4

• Bound Thread -> One ULT is assigned to only one Kernel level thread (or LWP in solaris case)
• CPU / Thread Pinning -> Kernel Thread pinned to particular CPU (CPU sets cgroup controller)

Question 5

What is a disadvantage of having both user and kernel threads

Answer 5

Lack of visibility between kernel and ULT library requires coordination via signals and special system class.
1:1 model helps here.

Question 6

Name problems in multi-threaded OS’es that stem from the lack of visibility between kernel and user level threads.

Answer 6

• ULT library does not know when Kernel level thread blocks due to IO => might have more user-level threads to run concurrently (NEEDS IMPROVEMENT AS THE ULT knows that the UL thread code does some blocking stuff!)
• ULT library does not know when kernel decides to remove an idling thread
• Kernel preempts kernel thread that runs critical user-level thread => other user thread wait for mutex lock to clear => kernel unaware of mutex data structures)

Question 7

Name examples when the ULT library scheduler in invoked/executed.

Answer 7

• ULTs yield (Scheduler in library needs to schedule another ULT to run on kernel thread)
• Timer set by ULT expire (time slice is up for ULT, need to preempt)
• ULT call library functions (lock, unlock, …)
• Blocked ULTS are runnable
• Coordination between kernel & ULT thread library (kernel sends signals)

Question 8

What is a problem in thread management (user & kernel space interaction) specific to multicore CPUs?

Answer 8

Video 13.

CPU 1 needs to signal CPU2 to invoke the user level scheduler when a condition (such as released lock) in thread executing on CPU1 changed.

Why: might need to preempt UL thread currently executing on KLT and schedule another UL thread with higher priority.

Question 9

What are adaptive mutexes for and when does it make sense to use them?

Answer 9

Adaptive mutex = spin lock.
Just burn CPU cycles to wait for mutex to be freed.
Makes sense when:
- Mutex will soon be released / short critical section (need to have idea of kind of critical section associated with mutex)
- Multiple CPUs/Cores where stuff can execute IN PARALLEL

Question 10

Interrupt vs. Signal

Answer 10

• Interrupt generated by external component (hardware, timer, other CPU!)
• Signal triggered by CPU itself and software running on it
• Which interrupts exist depend on the HARDWARE vs. Signals are dependent on OS
• Interrupts always asynchronous vs either asynchronous or synchronous (process accesses memory it should not - send SIGSEGV right away)
• Interrupts are delivered to a CPU vs. Signals are delivered to A PROCESS

Question 11

Similarities Interrupt & Signal

Answer 11

• Have uniqeue ID
• can both be masked (cool!)
• Have a handler routine
  
  • Interrupt handlers set for entire system by OS
  • Signal handlers set per process (by user code)

Question 12

What are asynchronus signals and name two examples.

Answer 12

Asynchonous Signals => result from some action outside the process.

SIGALARM (timer expired)
SIGINT
SIGKILL (coming from other CPU)

Question 13

What are synchronus signals and name two examples.

Answer 13

result from an operation ON the thread

• SIGFPE (divide by zero)
• SIGSEGV

Question 14

Can a interrupt be masked and if yes, does the Kernel do that?

Answer 14

Yes it can be. Kernel / OS is not involved. Instead the Hardware interrupt route will not deliver interrupt to CPU.

Question 15

What types/categories of signals exist?

Answer 15

Real time Signals (reliable)
- n raised signals cause n handler executions

One Shot (unreliable)

• n signals pending (masked by process) == 1 signal pending
• handler routine have to be reinstalled by handler itself

Question 16

Name a caveat of One Shot signals

Answer 16

handler routine have to be reinstalled by handler itself => subsequent signals might get lost if not quickly enough re-installed.

Question 17

Name a situation when it makes sense to mask interrupts or threads.

Answer 17

To prevent a deadlock with mutexes.

Happens when handler routine tries to lock mutex that is already locked by the interrupted thread.

Question 18

How can a deadlock in signal/interrupt handlers with mutexes be prevented?

Answer 18

Executing handlers in dedicated threads.

Question 19

When are interrupts in dedicated threads useful?

Answer 19

• Prevent deadlock in handler routine
  => Allow handler code running in thread to use any mutex and have high complexity (can be blocked, can wait etc.) without having to worry about deadlocks
• Optimize performance (SunOS Paper)
  => Overhead in extra instruction to decide whether to create thread + create it is offset by not having to mask/unmask mutexes in the handler running in the originally interrupted thread context. (Optimize for common cause)

Question 20

What are the characteristics of the top half in the interrupt handler routine?

Answer 20

Non-blocking, fast execution

Question 21

What are the characteristics of the bottom half in the interrupt handler routine?

Answer 21

Arbitrary complexity (mutexes etc., can be blocked), executed in thread (e.g to avoid possible deadlocks.)

Question 22

Describe a problem with signal masks between UL threads and LWPs or KLTs

Answer 22

Kernel does not know UL threads & therefore which of them should receive signals (UL thread can have them masked in UL struct).

Per-Process kernel level signal handler table contains the start address of the library handler (instead of a global one) that does the multiplexing.

ULT library global handler optimizes to avoid mahal signal mask updates in the Kernel and instead operates on a UL signal mask.
This optimizes for the common cause: Signal mask updates happen often (cheaper on UL mask without signal call). Signals do not happen often.

Question 23

What is the difference between a Trap and an Interrupt?

Answer 23

Unanswered: See: https://piazza.com/class/ksj1dzntsni27l?cid=824

Question 24

Under which circumstances should the m:1 model for threads be used?

Answer 24

TODO

Question 25

What are the advantages of the m:n model for threads?

Answer 25

TODO

Question 26

Name the advantages of the 1:1 threading model

Answer 26

TODO: explicitly in lecture! –> king because it reduces complexity of m:n ->
–> complete!!

• increases visibility
  
  • cannot just block the only executing thread which other UL threads depend on (knows all threads and can easily create new KL threads for concurrency)
  • no need to signal when KLT is removed so that UL threading lib can create new KLT (always 1:1)
• reduces need for communication for sending signals from kernel to right user level thread (kernel does not know signal mask in user)

Question 27

What are the states in the lifetime of a thread in OSlaris?

Answer 27

Active, Runnable, Sleeping, Stopped, Zombie

Question 28

What are advantages/ why to Zombie threads &process exists?

Answer 28

• Minimize cost of thread exit (free stack) => deferred to later.
• Speed up further thread creation: freed stacks put in cache of available stacks => smart AF!!!

Question 29

What is important in respect to critical sections / synchronisation in signal handlers?

Answer 29

• Solaris: Signal-safe critical section +> ALL asynchronous signals should be masked during such critical section (otherwise execution might jump into signal handler in the middle of critivcal section - tough!)
• Interrupt handlers use separate threads to execute complicated code incl. blocking on synch. variables.

Question 30

What is priority inversion. How is it prevented in SolarisOS?

Answer 30

• In computer science,priority inversionis a scenario in[scheduling] in which a high priority[task] is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that high priority tasks can only be prevented from running by higher priority tasks.
• Prevented by dispatch queue which is a Priority Queue