Week 8

Question 1

What is concurrency?

Answer 1

The ability of our machine to handle and execute multiple different tasks at seemingly same time.

Question 2

At the process level, programmers can manage concurrency using __________

Answer 2

threading

Question 3

Unless explicitly synchronized, processes/threads may:
Be run in _________
Be stopped and restarted at ________
Remain stopped for _____________

Answer 3

any order

any time

arbitrary lengths of time

Question 4

Why is the operating system one of the most difficult concurrent programs to write?

Answer 4

It is multiplexing access to hardware resources and therefore sharing a great deal of state between multiple processes.

It frequently uses many threads to hide hardware delays while servicing devices and application requests.

Lots of shared states plus alot of threads.

Question 5

What is a race condition?

Answer 5

A race condition is when the output of a process is unexpectedly dependent on timing or other events.

Question 6

Processes contain ________ , multiple ____ can be executing concurrently within a single process.

Answer 6

threads

Question 7

A process thread can be thought of as …

Answer 7

an abstraction of the CPU state

Question 8

Both processes and threads are used for concurrency. What do they do?

Answer 8

Processes allow for concurrency to be managed at the OS level

Threads allow for concurrency to be managed at the process level.

Question 9

Why use threaeds instead of separate processes?

Answer 9

When the program needs cheap communication.

Lowers the cost of a context switch

Gives the programmer additional control over concurrent execution.

Question 10

Communication between threads tends to use ________ objects in memory

Answer 10

Communication between threads tends to use shared objects in memory.

Question 11

Thread stacks and local variables are intended to be _________

Answer 11

Thread stacks and local variables
are intended to be private

Question 12

What is the difference between concurrency and atomicity?

Answer 12

Concurrency: the illusion that multiple things are happening at once. (requires stopping or starting any thread at any time.

Atomicity: the illusion that a set of separate actions occurred all at once.

Question 13

What is a critical section?

Answer 13

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

> This series of instructions should look atomic with respect to other
threads.

Question 14

What are these critical section requirements?

Mutual Exclusion

Progress/Fairness

Performance

Answer 14

> Mutual Exclusion: this is the most basic property. Only one thread
should be executing in the critical section at one time.

> Progress/Fairness: all threads should eventually be able to proceed through the critical section.

> Performance: we want to keep critical sections as small as
possible without sacrificing correctness.

Question 15

How do we enforce critical sections?

There are 2 possible approaches.

Answer 15

> Don’t stop: On uniprocessors a single thread can prevent other threads from executing in a critical section by simply not being descheduled.

> Don’t enter: More generally we need a way to force other threads—potentially running on other cores—not to enter the
critical section while one thread is inside. How do we do this? Locks!

Question 16

What is a lock?

Answer 16

A lock is just another variable in your program.

A lock is either free/unlocked/available or held/acquired/locked by exactly one thread.

If a thread holds a lock then they are (presumably) in the critical section

Question 17

What are the 3 things that we care about when evaluating locks?

Answer 17

• Correctness (i.e., Mutual Exclusion): this is the most basic property. Only one thread should be executing in the critical
  section at one time.
• Progress (i.e., fairness): all threads should eventually be able to proceed through the critical section.
• • Performance: what is the overhead of the lock? How is it affected by multiple processors?

Question 18

What is test and set?

Answer 18

Test-and-set: write a memory location and return its old value.

Question 19

What is a spinlock?

Answer 19

Lock for the fact that it guards the critical section.

spin describing the process of acquiring it.

Spinlocks are rarely used on their own to solve synchronization problems, but are commonly used to build more useful
synchronization primitives.

Question 20

Are spin lock…
correct?
fair?
performant?

Answer 20

Are spin locks correct? Yes, they provide mutual exclusion.

Are spin locks fair? No, they don’t employ any mechanism to ensure other threads get to execute.

Are spin locks performant? Sometimes…

Question 21

SPIN LOCKS

When should we go to sleep?

When should we spin?

Answer 21

Sleep if the critical section is long.

Spin if the critical section is short.

Question 22

What is a busy waiting.

Answer 22

Busy waiting: threads wait for the critical section by pounding on the door, executing the test-and-set repeatedly.

Bad on a multicore system. Worse on a single core system! Busy waiting prevents the thread in the critical section from making progress!

Question 23

What is compare and swap.

Answer 23

It will test whether the stored value is equal to some test value. If so, update the the
stored value to some new value.

Compare-and-swap is more powerful than test-and-set, but in the simple case of spin locks the code and behavior is essentially the same.

These are often used for lock-free synchronization.

Question 24

What is load-linked and store-conditional.

Answer 24

First, load a value from memory
using the load-link instruction.

> Second, store a value into that address using store-conditional, but only if the value at that address hasn’t been modified in the meantime.

• Again, we can use these instructions to implement a spin lock

Question 25

What is fetch and add?

Answer 25

Automatically increments a value while returning the old value.

We can use fetch-and-add to build a lock
with fairness: a ticket lock

Question 26

True or false, we can solve the performance problems of spin locks with just hardware.

Answer 26

False. We can’t solve the performance problems of spin locks just with hardware,
we have to rely on the OS.

Question 27

What does yield() do?

Answer 27

The system call yield() allows a thread to deschedule itself, moving the
thread from the running state to the ready state.

Question 28

What does fetch and add do?

Answer 28

fetch-and-add: automatically increments a
value while returning the old value.

• We can use fetch-and-add to build a lock with fairness: a ticket lock.