4. Synchronization

Question 1

What do threads do?

Answer 1

Threads abstract and multiplex the CPU

Question 2

How does the OS create the illusion of concurrency?

Answer 2

The OS quickly switches the processors between multiple threads of execution

Question 3

Why is the illusion of concurrency both powerful and useful?

Answer 3

It helps us to think about how to structure our applications, and it hides latencies caused by slow hardware devices (like waiting for keyboard input).

Question 4

Briefly define the coordination problem that multi-threaded concurrency creates.

Answer 4

How do we enable efficient communication between the multiple threads involved in coordinating a single task?

Question 5

Briefly define the correctness problem that multi-threaded concurrency creates.

Answer 5

How do we ensure that shared state (memory, files) remains consistent when being accessed by multiple threads concurrently?

Question 6

What is the difference between concurrency and parallelism?

Answer 6

Concurrency is about dealing with lots of things at once (independently executing processes).

Parallelism is about doing lots of things at once (simultaneous execution of possibly related computations).

Question 7

For an OS to achieve concurrency, what must be by default true about threads?

Answer 7

They must be able to be run in any order. They must be allowed to be stopped and restarted at any time. They must be able to remain stopped for any amount of time.

This is all assuming that no explicit synchronization techniques have been employed. Example: protecting a critical region with a lock, making it impossible for another thread to execute that section while another thread is within it.

Question 8

What is a race condition?

Answer 8

When the output of a process is unexpectedly dependent on timing or other events

Ex: A condition that occurs when two or more threads can access shared data and try to change it at the same time. Threads can be started and stopped at any moment, so it is possible that one thread checks a piece of memory for a condition, but before executing its desired operation to/with that data, it is stopped and another thread changes that data first. Now the initial check that the first thread made is incorrect, but the thread does not know that. In short, a race condition exists when the unknowable order of access that threads make to a shared resource impacts the outcome of execution.

Question 9

What is concurrency?

Answer 9

The illusion that multiple things are happening at once. (Requires stopping or starting any thread at any time)

Question 10

What is atomicity?

Answer 10

The illusion that a set of separate actions occurred all at once.

Question 11

How is atomicity achieved?

Answer 11

This requires not stopping certain threads at certain times or not starting certain threads at certain times.

i.e. providing some limited control to thread over their scheduling

Question 12

What is a critical section?

Answer 12

A critical section contains a series of instructions that only one thread can be executing at any given time

This set of instructions will look atomic with respect to other threads executing code within the critical section

Question 13

What is mutual exclusion?

Answer 13

Only one thread should be executing in the critical section at one time.

Question 14

What is progress?

Answer 14

All threads should eventually be able to proceed through the critical section

Question 15

What is performance (as it relates to a critical section)?

Answer 15

We want to keep critical sections as small as possible (to improve performance) without sacrificing correctness

Question 16

What are the three requirements of a critical section?

Answer 16

Mutual exclusion, progress, and performance

Question 17

What are the two possible approaches to implementing critical sections?

Answer 17

A “don’t stop” policy, where threads cannot be de-scheduled while they are in a critical region (works on uniprocessors)

A “don’t enter” policy, where threads cannot enter a critical section while another thread is executing in it (works on multicore systems).

Question 18

List 3 special hardware instructions which are guaranteed to be atomic across all cores.

Answer 18

Test-and-set, compare-and-swap, load-link and store-conditional

Question 19

What does the test-and-set hardware instruction do?

Answer 19

Write to a memory location and return its old value

Question 20

What does the compare-and-swap hardware instruction do?

Answer 20

Compare the contents of a memory location to a given value. If they are the same, set the variable to a new given value.

If the value had been updated by another thread in the meantime, the write would fail.

Question 21

What does the load-link and store-conditional hardware instruction do?

Answer 21

load-link and store-conditional (LL/SC) are a pair of instructions used in multithreading to achieve synchronization. Load-link returns the current value of a memory location, while a subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link. Together, this implements a lock-free atomic read-modify-write operation.

Question 22

What is busy waiting?

Answer 22

Threads wait for the critical section by “pounding on the door”, executing the check it is waiting on repeatedly. Thread checks for its entire time-slice if necessary and continues checking once it is rescheduled. Only stops checking when it is given access to the resource.

Question 23

Why is busy waiting especially bad on a single core system?

Answer 23

Busy waiting prevents the thread in the critical section from making progress!

(But wont it simply be descheduled once it runs out of time?)

Question 24

What is a lock?

Answer 24

A synchronization primitive used to implement critical sections.
Threads acquire a global lock when entering a critical section and release it when leaving. Only one thread can hold a lock at a time, so if a critical section is bounded by a lock_acquire and lock_release, only one thread will be able to execute that section at a time.

If a thread tries to acquire a lock that is currently held, it will go to sleep (be descheduled) until the lock is released

Question 25

What is a spinlock?

Answer 25

It is a lock, because it guards a critical section. It is a spinlock because the thread busy-waits over the critical section protected by a spinlock (the lock keeps spinning).

Question 26

What happens if we call lock_acquire() while another thread is in the critical section?

Answer 26

The thread acquiring the lock must wait until the thread holding the lock calls lock_release()

Question 27

How do threads wait for a lock?

Answer 27

Either actively (repeat some check until the lock is released) or passively (go to sleep until lock_release wakes thread from the wait_channel).

Question 28

Why can’t a thread spin at the threshold of a critical section on a uniprocessor system?

Answer 28

On single core systems, nothing can change unless we allow another thread to run

Question 29

On a multicore system, how do we decide if a thread should busy wait (spin) or go to sleep?

Answer 29

It depends on the length of the critical section. We have to balance the length of the critical section against the overhead of a context switch.

Question 30

How does one thread signal to a waiting thread that it has exited the desired critical section?

Answer 30

Lock_release() can be considered a signal from the thread inside to other threads indicating that they can proceed.

In order to receive this signal, a thread must be sleeping.

Question 31

What is a condition variable?

Answer 31

A signaling mechanism which allows a thread to cv_wait until a condition is true and for an executing thread to cv_notify waiting threads when the condition becomes true.

Question 32

What feature do condition variables provide that locks cannot?

Answer 32

Condition variables can convey information about the state of the world that locks cannot. Locks simply communicate if another thread is currently in the critical section. Condition variables monitor state and will allow (or disallow) threads based on whatever condition(s) the user wants.

Ex. If a buffer is full, threads are allowed to withdraw data but not add. If a buffer is empty, threads can add but not withdraw. etc…

Question 33

Why are condition variables a synchronization mechanism?

Answer 33

We need to be sure that the condition being checked does not change between checking it and deciding to wait