Threads + Synchronization

Question 1

Difference between process & thread

Answer 1

Processes have separate virtual address spaces, threads share the same virtual address space

Question 2

Which memory segment is not shared across threads

Answer 2

Stack memory - each thread gets its own stack

Question 3

Data Race Problem

Answer 3

Multiple threads accessing and writing to the same memory at the same time, overwriting each others’ result

Question 4

Non-deterministic outcome

Answer 4

The output of a non-deterministic program can be different each time it is run

Question 5

Race Condition

Answer 5

A condition in which the correctness of a program depends on the timing/order of operations

Question 6

Mutex lock

Answer 6

Mutual Exclusion lock - a primitive that allows only one thread to hold it

Question 7

Blocking

Answer 7

A thread “waits” until the resource it is trying to access is free. We can’t control the order of threads that are waiting for the lock.

Question 8

Atomicity

Answer 8

All code that is locked by a lock is atomic, i.e. all sub-operations would run as if they were a single operation, with no interference from other threads
“all or nothing” - runs all operations or none

Question 9

Serialization

Answer 9

Using a lock serializes operations, only one thread can run operations guarded by a lock

Question 10

Interleaving

Answer 10

Operations run from different threads are interleaved in some order, we can’t control the order in which different threads run

Question 11

Thread safe function

Answer 11

A function that doesn’t access shared resources or provides proper protection for critical sections

Question 12

Re-entrant function

Answer 12

Produces the correct output even when called again while being executed, therefore doesn’t use any shared variables

Question 13

Deadlock

Answer 13

A set of threads hold a resource and wait to acquire a resource held by a different thread

Question 14

Conditions for deadlock to occur

Answer 14

1. Hold and wait - a thread is holding one resource and waiting for another
2. Circular waiting - a set of threads is waiting for a resource held by the next thread
3. Mutual exclusion
4. No preemption - resource only released voluntarily by thread holding it

Question 15

Livelock

Answer 15

A set of threads are still actively executing instructions but don’t make any progress

Question 16

Producer-Consumer pattern

Answer 16

One set of threads is producing data, another set of threads is consuming data

Question 17

Condition variable primitive

Answer 17

Allows a thread to send a notification to the condition variable, and another thread can listen for updates from the condition variable

Question 18

pthread_cond_signal vs pthread_cond_broadcast

Answer 18

signal wakes up a single thread waiting on the condition, broadcast wakes up all threads waiting on it. broadcast should be used if waiting threads do different things

Question 19

Semaphore

Answer 19

A lock primitive with a “count” that allows multiple threads to grab the same lock

Question 20

Read-Write Lock

Answer 20

A lock that allows either unlimited readers or a single writer but not both (XOR)

Question 21

What primitive to use w/ Producer-Consumer w/ Bounded Buffer problem

Answer 21

Semaphore -