Locks

Question 1

What is multi-programming?

Answer 1

Doing multiple tasks at the same time using multiple processes.

Question 2

How does multi-programming differ from multi-threading in terms of data transfer?

Answer 2

Multiprogramming uses IPC for processes to communicate with each other. Multithreading shares the memory space.

Question 3

What are the pros and cons of multiprogramming?

Answer 3

Pros: Memory safety protection provided by the OS: since each process runs independently without interfering with the memory space of other processes, there is no risk of accidentally modifying or overwriting someone else’s data. There is also no risk of race condition.

Cons: IPC is difficult to set up

Question 4

What are the pros and cons of multithreading?

Answer 4

Pros: Easy communication

Cons: Racing conditions leading to hard to debug errors. There are also errors like atomicity violation, deadlocks, starvation, etc.

Question 5

When we use multithreading, when does the order of scheduling cause an issue?

Answer 5

When the threads work on shared data

Question 6

Define race condition.

Answer 6

The output of concurrent program depends on the order of operations between threads

Question 7

What is an approach we can use to combat race condition?

Answer 7

Using atomic operations to ensure cooperation between concurrent threads. This is also called synchronization.

Question 8

What is an atomic operation?

Answer 8

An operation that either does not run or runs to completion

Question 9

What does indivisible mean for an atomic operation?

Answer 9

It means the operation cannot be stopped in the middle of running.

Question 10

If there are no atomic operations, can threads still work together?

Answer 10

No

Question 11

Give two examples of atomic operations.

Answer 11

Load and store

Question 12

Describe mutual exclusion.

Answer 12

It ensures that only one thread works on a particular task at a time.

Question 13

What is critical section?

Answer 13

It is a piece of code that only one thread can execute at a time. If we have mutual exclusion, we have a critical section. It is the shared resources such that the OS cannot interrupt when we execute this section.

Question 14

What is a lock?

Answer 14

A lock prevents someone from doing something. Before a thread enters a critical section (accessing shared data), it should lock the task. Once it is done, unlock before leaving. If a task is locked, wait.

Question 15

Does synchronization involve waiting?

Answer 15

Yes

Question 16

What are the two correctness properties? In terms of “too much milk” and in general.

Answer 16

1. Someone buys if needed
2. Never more than one person buys
3. Someone works on the task if needed
4. Never more than one worker executing the same task

Question 17

Explain why the basic strategy fails: if there is no milk and no note, leave a note and go buy milk. Remove note after buying.

Answer 17

After person 1 checked there is no milk, get context switched to person 2, who also checked there is no milk and no notes. Then switch back to person 1, who sees no note, leaves note and goes to buy milk. Then person 2 also leaves note and goes to buy milk.

Question 18

What happens if we leave a note before checking if there is milk or a note?

Answer 18

Starvation. Then there is no point in checking the note because it will always be there. So no one will ever buy milk.

Question 19

Describe using labelled notes.

Answer 19

Before A does anything, it leaves a note A (so if at any point it gets switched to B, B will see that A is on it, so B will not go buy milk). Then A checks for B’s note and check if there is milk. If there is not, A goes to buy. B does the same thing.

Question 20

Will using labelled notes still lead to starvation?

Answer 20

It is possible. If A left its note and before it could check for B’s note, it gets context switched to B. B also leaves its note and gets switched back to A. Then they both see each other’s note and remove their own.

Question 21

What is a solution that works? Explain.

Answer 21

To use a while loop on oner person to keep checking the other person’s note. The person with the while loop has to keep waiting. For B, if there is no note from A, it is safe for B to buy. If there is a note, B just removes its note. For A, it keeps waiting for B to quit so there is no note. Then A can check if there is milk and decide what to do.

Question 22

What is the while loop named?

Answer 22

Busy waiting loop

Question 23

Why is the solution with a busy waiting loop not ideal?

Answer 23

A’s code is different from B’s. This becomes difficult when there are lots of threads and each of them has a slightly different code. It wastes CPU time since A is just waiting. It is also very complex and hard to convince one that it works without loopholes.

Question 24

What is the best solution for the milk problem?

Answer 24

Use “lock.Acquire()” to acquire a task and use “lock.Release()” to release once done.

Question 25

What is the code between lock.Acquire() and lock.Release() called?

Answer 25

Critical section

Question 26

What is wrong with putting threads to sleep?

Answer 26

Wasting CPU resources

Question 27

What is a naive implementation of locks?

Answer 27

When the lock is acquired, disable interrupts. When the lock is released, enable interrupts.

Question 28

What is the issue with the naive implementation of locks?

Answer 28

If we get into an infinite loop after acquiring a lock, the OS cannot interrupt to get us out. The system will stay hanging and unresponsive until it restarts.

Question 29

What are some problems of implementing locks with interrupts?

Answer 29

It does not work well on multiprocessors. On multiprocessor systems, this approach does not provide synchronization because disabling interrupts on one core does not affect others. It does nothing to stop other processors from accessing shared resources. Disabling interrupts also makes it time consuming to communicate between processors.

Question 30

What is an approach that can be used in both uniprocessor and multiprocessors?

Answer 30

Atomic read-modify-write instructions

Question 31

Who offers doing these instructions atomically?

Answer 31

The hardware

Question 32

test&set is an example of read-modify-write instructions. Describe how it works.

Answer 32

1) Set a variable lock to 0 if the lock is free, 1 if the lock is locked.
2) Given the mem address of the lock, read the value at the address and save it somewhere, e.g. result.
3) Rewrite the value with 1 at the address. (It sets to 1 no matter what the state of the lock is)
4) Return the value we read initially
So, if we get 0 back, we acquired the lock (the lock was available when we got to it). If we get 1 back, we failed to lock the lock.

Question 33

When we use test&set, what does test&set read and set if we have a free lock?

Answer 33

It reads 0 and sets the value to 1.

Question 34

What about when we have a busy lock?

Answer 34

It reads 1 and sets the value to 1.

Question 35

How do we determine if we succeeded in acquiring the lock with test&set?

Answer 35

We look at the value it returns.

Question 36

If we implement locks with test&set, within the acquire step, we would have a while(test&set(&my_lock)) loop. What is wrong with this implementation?

Answer 36

All threads will run this code and only one thread will succeed in acquiring the lock. Meanwhile, all the other threads are kept busy waiting, consuming resources.

Question 37

What are the pros of this implementation of busy-waiting?

Answer 37

1) No blocking interrupts
2) User code can use this lock through system calls
3) Works on multiprocessors

Question 38

What are the cons of busy-waiting?

Answer 38

1) Wasting resources when threads consume cycles waiting
2) Priority inversion

Question 39

What is priority inversion?

Answer 39

Each thread has a priority and the OS expects a high priority thread to run first. If a low priority thread gets access to the resources first, the OS gives it the highest priority and waits until it finishes while no one can interrupt. Then a high priority task will be waiting for the lock to be released, but the low priority one holding the lock cannot release the resources because a medium-priority task preempts it and runs instead.

Question 40

Why is priority inversion bad?

Answer 40

1) Priority inversion disrupts the expected behavior of priority scheduling. High-priority tasks are expected to preempt lower-priority tasks, but inversion violates this principle, leading to erratic and hard-to-debug system behavior.

2) High priority tasks often have a tight deadline so busy-waiting would cause them to miss their deadlines.

Question 41

What are the other two rules of using locks? 1) Locks should be initially free. 2) Always acquire a lock before accessing shared data

Answer 41

3) Always release the lock after finishing with shared data
4) Never access shared data without a lock

Question 42

Who can release a lock?

Answer 42

The lock owner

Question 43

Should the lock owner throw the lock for others to release?

Answer 43

No, never.