Locks

Question 1

Explain the term race condition

Answer 1

It is a situation where the correctness of several operations depends on the order in which the operations are executed.

Question 2

Enumerate and explain the requirements for a valid synchronization solution

Answer 2

1. Mutual exclusion: At most one thread can be in the CS at any time
2. Progress: No thread running outside of the CS may block another thread from getting in
3. Bounded Waiting: Once a thread starts trying to enter the CS, there is a bound in the number of times other threads get in
4. Performance: The time overhead added by using the lock for different cases of no/low/high contention

Question 2

Critical Section

Answer 2

CS is a code sequence that might result in a race condition when executed concurrently => protect CS from concurrent execution

Question 3

does disabling interrupts result in mutual exclusion? (advantages and disadvatages)

Answer 3

the kernel only switches threads on interrupts
have per thread do-not-disturb bit
+ easy and convenient in the kernel
- only works in single-core systems: disabling interrupts on one CPU doesn’t affect other CPUs
- only feasible in kernel: user code shouldn’t have the privilege to turn off interrupts (infinite loop, hogging the CPU)

Question 3

Locking with TestAndSet

Answer 3

int TestAndSet (int *old_ptr, int new) {
int old = *old_ptr;
*old_ptr = new;
return old;
}
while (TestAndSet(&lock->flag,1) == 1)

fetch the old value at old_ptr
store new into old_ptr
return the old value
spin-wait while lock is held

Question 4

Locking with CompareAndSwap

Answer 4

int CompareAndSwap (int *addr, int expected, int new) {
int actual = *addr;
if (actual == expected)
*addr = new;
return actual;
}
while(CompareAndSwap(&lock->flag, 0,1) == 1);

Idea: test whether the value at the address specified by ptr is equal to expected; if so, update the memory location pointed by ptr with the new value

Question 5

Lock with Load-linked/Store-conditional

Question 6

Which conditions of synchronization are met with atomic store operations

Answer 6

+ mutual exclusion: only one thread can enter CS
+ progress: only thread within the CS hinders others from getting in
- bounded waiting: no upper bound
- performance: wasted time while spinning on the CPU

Question 7

Spinlock limitations

Answer 7

• if the CS is large or many threads try to enter, spinlocks might not be a good choice as many threads actively wait spinning
• if threads on different cores use the lock
• can behave unexpectedly when processes are scheduled with static priorities

Question 8

Disadvantages of yield() instead of spinning

Answer 8

• the cost of a context switch can be high
• bad performance in case of many threads

Question 9

Disadvantages of busy waiting

Answer 9

• wastes resources when threads wait for locks
• stresses the cache coherence protocol when used across cores
• can cause priority inversion problem

Question 10

What is the idea behind using blocking locks

Answer 10

• threads should sleep on locks if they are occupied
• wake up threads one at a time when lock becomes free

Question 11

Explain two-phase locks

Answer 11

• try to get into the CS with a userspace spinlock (phase 1)
• leave the CS in userspace if no other thread is waiting, otherwise wake up a blocked thread
• if the CS us busy, use a syscall to put the thread to sleep (phase 2)
• the thread is only woken up when the lock becomes free later

Question 12

Explain critical section, entry section, exit section, and remainder section

Answer 12

CS: code region in which a thread accesses some common data such as a shared variable. As soon as one thread is executing inside a CS, no other thread is allowed to execute in the same CS

Entry section: a thread must request permission to enter the critical section

Exit section: signal completion of the CS, so to allow other threads to enter

All other code is called the remainder section

A CS is enclosed by an entry section and an exit section

Question 13

How could a race condition be avoided?

Answer 13

They can be avoided if it is ensured that “critical operations” are performed atomically. To ensure atomicity, a synchronization primitive can be used, e.g. locks. A synchronization primitive ensures that at most one thread can be inside a critical section.

Question 14

Can spinlocks be implemented entirely in user mode?

Answer 14

Yes. To implement a spinlock we only need a simple lock variable and an atomic test-and-set instruction provided by the hardware. As atomic instructions are not privileged, they can be used in user mode.

Question 15

Using a CPU register for a spinlock’s lock variable would be much faster than the implementation with a variable in memory. Why would such a spinlock not work?

Answer 15

Registers are thread local as their contents are replaced on thread switches. However, the lock variable of a spinlock must be shared between threads and thus can’t be placed in a register.

Question 16

What is the idea behind hybrid locks?

Answer 16

They combine the advantages of spinlock (no kernel entry necessary) and mutexes (no busy waiting). Before a thread blocks on the mutex and thus needs to enter the kernel, it first spins a certain time in user mode, trying to acquire the spinlock. This way, the hybrid lock tries to avoid the costly blocking wait in the kernel.