Threads

Question 1

What is a thread/process represented by? And what is the structure of this representation?

Answer 1

a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.

It is represented by a special data structure, called the thread control block (TCB). It contains relevant information about the thread:
- Thread characteristics: thread ID, program name
- State information: instruction counter, stack pointer, register contents
- Management data: Priority, rights, statistics

Question 2

What are the data structures used to store and manage the TCBs?

Answer 2

Single scalars, static long array, variably long linked list, tree, inverted table, ..

Question 3

How to efficiently manage multiple TCBs?

Answer 3

Form subsets of TCBs with regards to important attribute values (such as grouping threads of the same state together)

Question 4

What is the difference between static and dynamic OSs handling threads?

Answer 4

In static OSs, all threads are known in advance and are statically defined. TCBs are declared as program variables and are used for a specific application and are all generated by a configuration program once.

In dynamic OSs, the threads are created and deleted by kernel operations (create_thread (id, initial values) which create a TCB and initialize the thread and delete_thread(id, final values) which return the final values and delete the TCB).

Question 5

What is a thread’s address space?

Answer 5

A logical address space of a thread is the space of its valid addresses, which it can access. Relative addressing and address translation (using the MMU) allow to have an arbitrary number of logical address spaces that can be mapped to physical address space, leading to mutual protection of address spaces.

Question 6

What is a Unix process?

Answer 6

It is an address space that contains at least one thread. So we use the term thread directly.

Question 7

What is thread switching?

Answer 7

It means that the processor stops executing the current thread (its instruction sequence) and continues with the execution of another thread.

Question 8

What is switching by jumping?

Answer 8

It is where we insert a jump instruction directly into the thread that jumps into another thread. This is however very inflexible and applicable only in very special cases.

Question 9

Why is thread switching costly?

Answer 9

Because we have to memorize the continuation address in the interrupted thread, selection of the next thread. And the processor must hold on to essential parts of the interrupted thread description that must not get lost (during a register reload).

Question 10

Memorizing continuation address

Answer 10

Store the address of the next instruction of the interrupted thread to be executed in the interrupted thread in a dedicated variable called ni (next instruction) of the TCB

Question 11

What are the criteria for selecting the next thread?

Answer 11

Number of threads, order of arrival, priority of each thread (urgency).

Question 12

Describe simple next thread selection with priority.

Answer 12

Threads are ordered with regards to their execution order or priority. Newly arriving threads are inserted into the priority sequence according to the chosen order. The threads can be organized in a priority queue with two dimensions where there are groups of equal priority.

Question 13

What is a processor register in relation to threads?

Answer 13

Threads use arithmetic registers of the processor to store intermediate results.

Question 14

What happens to the register when switching thread by jump?

Answer 14

Its content will be lost (overwritten) so switch by jump can only be used when the contents of the register will no longer needed and the new thread does not expect valid register contents.

Question 15

What is a thread context?

Answer 15

It is the complete thread specific information that is stored in the processor registers (content of arithmetic registers, index registers, processor state, contents of address registers, segment tables, access control information, etc..)

Question 16

What happens to the thread context when switching a thread?

Answer 16

It must be saved as part of the switching and restored when the thread is resumed. Constant data that is available in the TCB does not need to be saved.

Question 17

What is thread switching by saving the thread context referred to? What are its characteristics and how to make it efficient?

Answer 17

It is context switch and it is the most time consuming part of the thread switch. To speed it up, processor can provide several sets of registers such that a thread switch does not require storing the thread context back to memory or provide a special instructions that allowing storing the complete thread context in one instruction.

Question 18

Describe the thread switching sequence?

Answer 18

SWITCH -> save context of t_run -> select t_next -> save next instruction of t_run in t_run.ni -> jump to t_next.ni -> t_run = t_next -> load context of t_run

Question 19

What is thread control in the context of the “Procedure” switch?

Answer 19

It means that each thread gets and gives up control within the switch procedure code at exactly the same point.

Question 20

Describe the implementation of the “Procedure” switch and highlight what thread has control?

Answer 20

CT: current thread
NT: next thread
procedure switch(NT:thread)

control: CT
save context of CT

CT.sp = SP, SP = NT.sp (change stack pointer)

control: NT
load context of NT
return to NT (next instruction of NT)

Question 21

What is automatic switching? And what does it require?

Answer 21

Realistically, it is not possible nor reasonable to explicitly insert switching points into the threads. Therefore, automatic thread switching is more desirable. To that end, we require a clock (timer), a hardware device that offers: specifying a deadline (timer set) and an interrupt on timeout. This allows programs to remain unchanged as the thread switch is triggered from outside the program and can happen at any arbitrary point in time.

Question 22

What is conditioned switching?

Answer 22

There could arise a situation where a continuation of the thread processing is not possible (thread waiting for input data), instead of wasting time, processor can switch to another thread. This is called conditioned switching.

Question 23

Describe thread switching due to end of time slice where there is no detailed clock interrupt handling and no other thread switching events.

Answer 23

03_threads slides: 53,60, 66, 75

Question 24

What is a kernel stack?

Answer 24

The kernel stack is part of the kernel space. Hence, it is not directly accessible from a user process. Whenever a user process uses a syscall, the CPU mode switches to kernel mode. During the syscall, the kernel stack of the running process is used.

Question 25

Why do we need switching prevention? Describe a problem that may arise due to interleaved execution.

Answer 25

Automatic switching may occur at exactly the same time when a voluntary or other switching is taking place which can lead to unwanted behavior and errors. Therefore, during switching, we need to make sure that no additional switching is triggered. The errors may occur because kernel OPs often work on same data structures and when a kernel OP is interrupted by another kernel OP, it may lead to errors.

Interleaved execution problem: diagram at 03_threads slide 78

Question 26

What is a solution to avoid problems that arise due to interleaved execution? What is this called?

Answer 26

Define sections of the kernel as critical sections. A critical section is then safe because interleaving can be excluded, meaning that kernel operations can not be executed in an interleaved fashion but are executed until completion. Therefore, when a thread is within a critical section, no other thread is allowed to enter a critical section that is in conflict. Therefore, all possible places of conflict in OS kernels need to be identified and protected as critical sections. This is called mutual exclusion. because the kernel has large # of critical sections, we can put the whole kernel under mutual exclusion.

Question 27

How to realize kernel exclusion? Describe solutions in each of the four cases?

Answer 27

Case 1: Single processor system without interrupts -> there is no reason to leave a kernel OP before completion -> No measure required.

Case 2: Single processor system with interrupts -> critical kernel OP is bracketed by a disable interrupt and an enable interrupt

Case 3: Multiprocessor system without interrupts -> introduce a kernel lock using a an atomic test-and-set instruction. When a thread enters critical section, it enables the kernel lock so that other threads that attempt to enter their critical section check that lock and do not enter their critical section as they repeatedly check the kernel lock value (busy waiting) until the lock is freed from the initial thread that was in critical section (reset) and the awaiting thread are allowed to enter their critical section. Kernel OPs are usually short so this time wasted waiting is tolerated.

Case 4: Multiprocessor system with interrupts -> Both techniques from Case 2 and Case 3 are implemented. But here we first have to disable the interrupts and then acquire the kernel lock. Other solutions are discussed in 03_threads slides 84 and 85

Question 28

Why do we need thread states?

Answer 28

When switching from one thread to another, we do not know that the thread we are switching to is also blocked or not (awaiting for some I/O operation for example), then we have to keep switching until finding a resumable thread which is a waste of time. Therefore we group threads depending on their states.

Question 29

What the the thread states?

Answer 29

• State running: threads that are currently executed on the processor.
• State ready: ready to be executed but have to wait for processor to become free.
• State waiting: blocked because they wait for some external event.

We can define the states as attributes in the TCB of each thread or as membership in a list/set of threads.

Question 30

What are the kernel OPs for thread state change operations?

Answer 30

• Relinquish: voluntary switch to another thread. current thread changes its state from running to ready.
• Assign: take the next thread from the ready set to resume its OPs on processor. ready -> running
• Block: state switch from running to waiting or blocked. This happens because the current execution of thread in processor must not resume until a certain condition is met.
• Deblock: event occurs for which a blocked/waiting thread waited for it, change its state from waiting to ready.

Question 31

How to handle thread states in a dynamic state where the set of threads if variable?

Answer 31

We distinguish between active and inactive threads, when a thread is created it is resting (inactive) until it gets activated and becomes ready. Ready threads can also get deactivated and they must become inactive before they get deleted.

Question 32

Describe preemption in the context of thread switching. What are the 4 cases where a thread gives up execution?

Answer 32

Not all threads are of equal importance/urgency. So when a thread with a higher priority than the running threads enters the ready queue, the running thread is preempted by the thread with the higher priority. This is the 4th case where a thread gives up executed. Other 3 cases are when a running thread relinquishes, forced to give up execution by clock interrupt or is blocked for some condition it is waiting for.

Question 33

How to check preemption?

Answer 33

Preemption requires that no ready thread has a higher priority than a running one unless the higher priority thread just enters the ready queue (by the operations of relinquish, deblock and activate) in which we execute a thread switch. If that is the case, we switch to the more urgent thread.

Question 34

What is an idle thread, why do we need it and what are its properties and how can we represent it?

Answer 34

Idle thread: thread that has no instructions being executed.

Why we need it? If all threads are blocked, processor has nothing to do, so the idle thread becomes running.

Its properties: must not stop, has lowest priority, must be preemptable at any time.

Representation: endless loop (energy waste), dynamic stop (special instruction with no memory access but can react to external signals, disabling parts of the processor and saving energy)