Concurrency: Multi-Tasking & Synchronization

Question 1

What is a race condition?

Answer 1

• Race Condition(data race)
  ○ Unprotected timing of execution.
  ○ The result of such a program would be indeterminate:
  sometimes it produces the correct result but sometimes the results are different and are likely wrong.

Question 2

What is a critical section?

Answer 2

○ Critical Section
Code routine that accesses a shared resource/data, if unprotected, might yield incorrect result. Might lead to race condition

Question 3

What is mutual exclusion? Why does it avoid race condition

Answer 3

• Mutual Exclusion(mutex)
  ○ Atomicity is guaranteed under mutex
  ○ Lock(Synchronization primitive)
  § Acquire:
  □ When a thread needs to use a shared resource(critical section), it must first get control (a lock) to enter the protected code area, ensuring no other thread can use it at the same time. If multiple threads try to get the lock, only one can get it and the rest must wait.
  § Release:
  After the thread has finished using the shared resource, it must unlock or release the control so that other threads can use the resource.

Question 4

How can we get mutual exclusion?

Answer 4

Atomicity of the critical section

Question 5

How is atomicity achieved?

Answer 5

Locks- Condition variables- Channels etc

Question 6

What are some of the problems with atomicity/mutual exclusion?

Answer 6

Where one thread must wait for another to complete some action before it continues. This interaction arises, for example, when a process performs a disk I/O and is put to sleep; when the I/O completes, the process needs to be roused from its slumber so it can continue.

Question 7

How does the lock mechanism work?

Answer 7

We can use a special lock variable to protect data- All threads accessing a critical section share a lock- One threads succeeds in locking - owner of lock- Other threads that try to lock cannot proceed further until lock is released by the owner

Question 8

What are the goals of locks?

Answer 8

Fairness: Every thread gets a chance to acquire the lock, preventing indefinite waiting.

Low Overhead: Acquiring, releasing, and waiting for the lock uses minimal resources for efficiency.

Question 9

What are some of the different types of locks?

Answer 9

Spin lock (thread ligge å venta i en for loop(spinne til den fe tilgang til locken)- Sleep lock(Thread sleeps until lock is free. Sleeping results in more idle time)

Question 10

What is a spin lock? What is a sleep lock?

Answer 10

Spins until lock is acquired| - While loops

Instead of spinning for a lock, a contending thread could simply give up the CPU and check back later- Yield() moves thread from running to ready state

Question 11

When should we use locks?

Answer 11

A lock should be acquire before accessing any variabel or data structure that is shared between multiple threads of a process

Question 12

What is the difference between a fined and coarse-grained lock?

Answer 12

One big lock for all shared data(Coarse grained locks) vs separate locks(fined locks)

Question 13

What are the positives and negatives of fine-grained locks?

Answer 13

Fine grained allows more parallelism| - Multiple fine-grained locks may be harder to manage

Question 14

What are the advantages and disadvantages of coarse-grained locks?

Answer 14

Slower| - Easier to manage

Question 15

Why do we want to use sleeping locks?

Answer 15

CPU Waste: When threads continuously check for a spinlock’s availability (known as spinning), they use up CPU resources without doing any productive work.
Extended Blocking: The problem worsens if a thread holding a spinlock is blocked for a long time, leading to even more CPU waste by the threads waiting for the spinlock.

Question 16

What are the advantages and disadvantages of spin locks?

Answer 16

Provides mutual exclusion- spin locks don’t provide any fairness guarantees- Spin locks, in the single CPU case, performance overheads can be quite painful

Question 17

How does Compare-and-swap work for locking?

Answer 17

it simply checks if the flag is 0 and if so, atomically swaps in a 1 thus acquiring the lock

Question 18

How does Load-Linked and Store-Conditional for locking work?

Answer 18

Load-Linked: This works like a regular load instruction. It just takes a value from memory and puts it in a register.
Store-Conditional: This is where it gets special. It will update the memory only if no other updates to the same memory address have happened since the load-linked. If there’s been an update in between, the store-conditional won’t go through.

Question 19

How does Fetch-And-Add for locking work?

Answer 19

Fetch-and-add instruction atomically increments a value while returning the old value at a particular address.- Unlock is accomplished simply by incrementing the turn such that the next waiting thread (if there is one) can now enter the critical section

Question 20

Why are condition variables used?

Answer 20

Condition variables are used to make threads wait for certain conditions to become true before they continue execution, ensuring proper sequencing and coordination in concurrent operations.

Question 21

How do condition variables work?

Answer 21

Condition variables allow threads to wait in a queue for a certain condition. When the condition is met, another thread signals the condition variable to wake up one or all waiting threads.

Question 22

How do we check a condition using condition variables?

Answer 22

In a while loop| We do this to avoid corner cases of thread being woken up even when condition not true

Question 23

What is a semaphore?

Answer 23

Semaphore is a variable with an underlying counter - Synchronization primitive like condition variable- Acts like a lock- Shared between threads

Question 24

How does a semaphore work?

Answer 24

A semaphore with a value of 1 acts like a mutex lock. Here’s how it works:

Thread 1 decreases the counter to enter the critical section, locking it.

After finishing its task, Thread 1 increases the counter, unlocking it.
Now, Thread 2 can enter and do the same.

Question 25

Why are semaphores special?

Answer 25

Can be used to set order of execution between threads like Condition Variables

Question 26

What are some of the concurrency bugs?

Answer 26

We have two:- Deadlock bugs (trying to share access same resource, but stops to function)- Non deadlock bugs

Question 27

What is a deadlock bug? What is a non-deadlock bug?

Answer 27

A deadlock bug is that threads cannot execute any further and wait for each other

When threads execute without proper synchronization, it can lead to atomicity bugs. This means they might complete their tasks in an overlapping manner, resulting in incorrect or unexpected results, even though no deadlock occurs.

Question 28

How can we fix a non-deadlock bug?

Answer 28

To fix a non-deadlock bug, ensure proper synchronization of threads, use locks or atomic operations to manage shared resources, and correctly sequence thread execution.

Question 29

How can a deadlock occur?

Answer 29

Mutual Exclusion: Only one thread can use a resource at a time.
Hold-and-Wait: A thread holds a resource and waits for another.
No Preemption: Resources can’t be taken back forcibly from a thread.
Circular Wait: Threads form a loop, each waiting for a resource held by the next in line.

Question 30

How can we prevent circular wait (deadlock bug)?

Answer 30

Aquire locks in a certain fixed order| - Total ordering must be followed

Question 31

How can we prevent hold-and-wait (deadlock bug)?

Answer 31

To avoid deadlocks:

Processes must request all resources at once.
Processes with resources must release them before asking for new ones, then re-request all resources together.

However, this can lower concurrency and performance.

Question 32

How can we generally avoid deadlock bugs and what to do if one occurs?

Answer 32

Deadlock avoidance: if OS know which process needs which lock, it can schedule the processes so that deadlock does not occur.- Detect and recover: reboot system or kill deadlock process.

Question 33

How do we calculate average response time?

Answer 33

Steps:- Calculate each process response time- Add them all together and divid it by the number of processes.

Question 34

Explain the term temporal locality?

Answer 34

Temporal locality: Programs often re-access the same instructions or data shortly after their initial use, like in loops or frequently used data structures. Caching these helps improve performance.

Question 35

Explain the term spatial locality?

Answer 35

Spatial locality: Programs typically access data close to recently used data. For example, sequential instructions or nearby data fields are often used together. Caches leverage this by loading blocks of data, not just single locations, for efficiency.

Question 36

Belady’s anomaly occurs when?

Answer 36

The number of page faults increase despite adding more page frames.Will ONLY happen with FIFO page scheduling algorithm.Will NOT happen with LRU, LFU or Optimal page scheduling algorithms.

Question 37

What is a Thread Control Block (TCB)?

Answer 37

Answer: TCB is a data structure in operating systems that contains thread-specific information like scheduling properties and time slice lengths.

Question 38

How does a thread context switch differ from a process context switch?

Answer 38

Answer: A thread context switch is more lightweight than a process context switch because the address space remains the same, eliminating the need to switch to a different Page Table.

Question 39

What is the key difference between a Process Control Block (PCB) and a Thread Control Block (TCB)?

Answer 39

Answer: While PCB contains overall process information, TCB contains specific details for each individual thread within a multi-threaded process.

Question 40

Why are thread context switches considered more efficient?

Answer 40

Answer: Thread context switches are more efficient because they don’t require changing the address space, unlike process context switches.

Question 41

What kind of information is stored in a TCB?

Answer 41

Answer: A TCB stores thread-specific information such as the thread’s Program Counter (PC), register values, scheduling properties, and time slice lengths.

Question 42

Does a multi-threaded process have both a PCB and TCBs?

Answer 42

Answer: Yes, a multi-threaded process has a PCB for overall process information and separate TCBs for each thread’s specific details.

Question 43

Question: In POSIX thread APIs, what are the functions and purposes of pthread_create(), pthread_join(), pthread_exit(), and synchronization primitives like pthread_mutex_() and pthread_cond_()?

Answer 43

pthread_create(): Initiates a new thread with designated attributes, beginning its execution at a specific routine. The thread that calls this function becomes the parent of the newly created child thread.
pthread_join(): Used to wait for a specified thread to complete its execution, effectively ‘joining’ it back to the main flow.
pthread_exit(): Allows a thread to end its own execution. A thread function’s return implicitly triggers pthread_exit().
Synchronization Primitives (pthread_mutex_(), pthread_cond_()): Tools in pthreads for managing safe access to shared resources. Mutexes (pthread_mutex_()) ensure one-thread-at-a-time access to a resource, while condition variables (pthread_cond_()) facilitate waiting for and signaling specific conditions among threads.