L10 & L11

Question 1

Explain how a binary sempahore works.

Answer 1

Binary semaphore: a single shared variable whose value is used to protect a shared resource

If the variable is 1, the resource is free. If the variable is 0, the resource is not free.

Operations: wait(var) takes the lock, signal(var) releases the lock

Question 2

How does tas affect the shared variable in a binary semaphore?

Answer 2

The variable is now the logical inverse of the standard definition.

If the variable is 0, the resource is free. If the variable is 1, the resource is not free.

Question 3

How does tas achieve atomicity for critical code?

Answer 3

Test-and-set locks access to memory from other processors.

Question 4

How does tas waste bus cycles?

Answer 4

If S is busy and is wanted by another thread, the semaphore will wait continuously in a loop until S is free.

Question 5

List examples of synchronisation primitives. What do they have in common?

Answer 5

• Test-and-set instruction
• Fetch-and-add (returns the value of a memory location and increments it)
• Compare-and-swap

They are read-modify-write instructions that lock the snoopy bus during their execution

Question 6

How can atomicity be achieved without holding the bus until completion?

Answer 6

Load-linked: core keeps some state for the load (load linked flag and saves the address)

Store-conditional: only succeeds if load linked linked flag set

Question 7

When is the load linked flag cleared?

Answer 7

when another core writes to the locked address