Threads and Mutex

Question 1

What is a thread?

Answer 1

A thread is similar to a process: It can execute code but threads are within a process. The main difference is that threads share the same address spaces but each thread has its own stack

Question 2

Why can the usage of threads be useful?

Answer 2

• Parallel: Work parallel on big data
• I/O: One thread can do I/O while the other is working somehting else
• Periodical: Periodical work can be done by a thread in the background

Question 3

What is a “critical section”?

Answer 3

A critical section is getting used by multiple threads/processes and is prone to race conditions. It must therefore be protected somehow.

Question 4

What are 2 ways of dealing with critical sections? Which one is preferable?

Answer 4

• Atomicity: Use HW based atomic operations
• Synchronization primitives: Combination of OS and HW based operations to safe critical section.
  Atomicity is too costly, therefore the 2nd.

Question 5

For what do we use locks? (1 sentence)

Answer 5

To prevent a critical section from being executed by two threads.

Question 6

How does a mutual exclusion lock (mutex) work?

Answer 6

2 stated:

• locked
• unlocked

Question 7

What are coarse-grained and fine-grained locking strategies?
- What is the problem with larger ciritcal sections that gets locked?

Answer 7

• coarse-grained: Include more code in the lock as critical section
• fine-grained: Only include the absolute minimum of code as critical section
• Locking large section normally reduces the concurrency (even until no more concurrency is doable)

Question 8

HW-based lock-support: Disabling Interrupts: Name 2 things why this is a bad idea.

Answer 8

• OS looses control: If an endless loop is in the lock noone can help you.
• Fails for multiple CPUs: Interrupts are per CPU

Question 9

HW-based lock-support: A simple flag variable

• How does it work?
• What are the problems?

Answer 9

• Uses a variable: If 0 it is free, if 1 it is taken. Method unlock spins until it is free.
• Race conditions
• Spin-waits: Uses CPU time basically for nothing

Question 10

What is the Test-and-Set Instruction?

Answer 10

The first atomic HW instruction for building locks. Returns old value and sets the pointer to new value.

Question 11

HW-based lock-support: A valid spin lock

• What is difference to a simple flag variable?
• Does this fix all problems of a simple flag variable?

Answer 11

• It uses an atomic instruction for the unlock function (to be more specific: It uses Test-and-Set)
• It fixes the correctness issue, but it is still not fair (Thread may spin forever and starve).

Question 12

Explain the HW Operation “Compare-and-Swap”

Answer 12

Atomic operation, Compares a value to an expected value. If it is the same it replaces the value with another value.

Question 13

Explain the HW Operation “Load-Linked, Store Conditional”

Answer 13

Two instructions work together atomically:

1. LoadLinked: Loads a value
2. StoreConditional: Only modifies the value if the value wasn’t modified since it was loaded by LoadLinked()

Question 14

Explain the HW Operation “Fetch and Add”

Answer 14

Atomic operation, takes a value increments it and returns the old value

Question 15

• How is a “Ticket Lock” implemented?

- Is it better than the other locks mentioned?

Answer 15

• Lock has 2 variables: Turn and ticket (both 0)
• Lock uses fetchAndAdd(ticket).
• Yes because it is correct and because it provides fairness (Ticket system).