q5

Question 1

What is the basic idea of locks?

Answer 1

Ensure that any critical section executes as if it were a single atomic instruction.

Question 2

What is a lock variable’s state when it is available?

Answer 2

No thread holds the lock.

Question 3

What happens when a thread calls lock() on a lock that is already held?

Answer 3

It will not return while the lock is held by another thread.

Question 4

What is the purpose of the unlock() routine?

Answer 4

To change the state of the lock to available (free) again.

Question 5

What is pthread_mutex_t?

Answer 5

The name that the POSIX library uses for a lock.

Question 6

What is the benefit of using different locks for different variables?

Answer 6

Increases concurrency by allowing more threads to be in locked code at once.

Question 7

What are the basic criteria for evaluating locks?

Answer 7

• Mutual exclusion
• Fairness
• Performance

Question 8

What is the problem with controlling interrupts for critical sections?

Answer 8

Turning off interrupts for extended periods can lead to lost interrupts and serious system problems.

Question 9

What is the purpose of the test-and-set instruction?

Answer 9

To support the creation of simple locks by providing atomic operations.

Question 10

What does the Compare-And-Swap instruction do?

Answer 10

Tests whether the value at the address is equal to expected and updates it if so.

Question 11

True or False: Spin locks provide fairness guarantees.

Answer 11

False.

Question 12

What is a simple approach to avoid spinning in locks?

Answer 12

Yield the CPU to another thread when going to spin.

Question 13

What function does park() serve?

Answer 13

Puts a calling thread to sleep.

Question 14

What is the structure of a lock_t in the context of using queues?

Answer 14

• int flag;
• int guard;
• queue_t *q;

Question 15

What is the role of the guard in the lock_t structure?

Answer 15

To protect the queue.

Question 16

What happens when a thread calls lock() on a lock_t that is already held?

Answer 16

The thread spins until it can acquire the lock.

Question 17

Fill in the blank: The lock is acquired when the flag in lock_t is set to _______.

Answer 17

1

Question 18

What is the consequence of too much spinning in hardware-based spin locks?

Answer 18

Wastes an entire time slice doing nothing but checking a value.

Question 19

Why is hardware support needed for locks?

Answer 19

To provide atomic instructions necessary for mutual exclusion.

Question 20

What is the purpose of the function lock(lock_t *m)?

Answer 20

To acquire a lock using a spinlock mechanism and queue management

The function spins to acquire the lock and uses a queue to manage waiting threads.

Question 21

What does the TestAndSet function do in the lock function?

Answer 21

It attempts to set the guard lock and returns the previous value

This is used to check if the lock is already held by another thread.

Question 22

What happens if the lock is successfully acquired in the lock function?

Answer 22

m->flag is set to 1 and m->guard is set to 0

This indicates that the lock is now held by the current thread.

Question 23

What occurs when the lock is not available in the lock function?

Answer 23

The current thread is added to the queue and calls park()

This puts the thread to sleep until it can acquire the lock.

Question 24

What is the purpose of the unlock(lock_t *m) function?

Answer 24

To release the lock held by the current thread

It also manages the queue of waiting threads.

Question 25

What does the function queue_empty(m->q) check in the unlock function?

Answer 25

It checks if there are any threads waiting for the lock ## Footnote If the queue is empty, it indicates no threads are waiting.

Question 26

What is the significance of the setpark() system call in the locking mechanism?

Answer 26

It indicates that a thread is about to park, allowing for quicker wakeup if interrupted ## Footnote This prevents threads from sleeping indefinitely.

Question 27

What are futexes and where are they used?

Answer 27

Futexes are fast user-space mutexes used by Linux ## Footnote They allow for efficient lock management and sleeping threads.

Question 28

What does the futex_wait(address, expected) function do?

Answer 28

It puts the calling thread to sleep if the value at address matches expected ## Footnote If it doesn't match, the call returns immediately.

Question 29

What happens in the mutex_lock(int *mutex) function when the lock is acquired?

Answer 29

The high bit of the mutex is cleared, indicating it is locked ## Footnote This is done using atomic operations.

Question 30

What does atomic_add_zero(mutex, 0x80000000) check in the mutex_unlock function?

Answer 30

It checks if there are any other threads waiting for the mutex ## Footnote This operation targets the high bit which indicates lock status.

Question 31

What is the concept of a two-phase lock?

Answer 31

A locking mechanism that spins briefly before sleeping if the lock cannot be acquired ## Footnote It combines spinning and sleeping to optimize performance.

Question 32

What are the two phases of a two-phase lock?

Answer 32

* First phase: The lock spins hoping to acquire it * Second phase: The caller sleeps if the lock is not acquired ## Footnote This allows for a balance between busy waiting and efficient sleeping.

Question 33

What hardware support is mentioned for implementing locks?

Answer 33

* Test-and-set (RISC-V) * Compare-and-swap (SPARC, x86) ## Footnote These are atomic operations that facilitate lock mechanisms.

Question 34

What OS support is provided for locking mechanisms?

Answer 34

* park() * unpark() * setpark() * futex ## Footnote These functions help manage thread sleeping and waking efficiently.