SOFT3410 Tutorial 7 Atomics
You have a quiz today and we will look into atomics
Question 1: Atomic Operations, Counting and Stacks
As we have noted prior, race conditions occur when we have more than one thread mutating shared memory. Atomics actually allow us to deal with this situation by making the write visible to other threads, this occurs in a single operation on the hardware itself.
Simply start by writing a program where multiple threads will increment the shared counter.
atomic_int counter = 0; void increment() {
}
atomic_fetch_add(&counter, 1);
• Set up your threads and a worker function to continually increment the counter, observe the result at the end of execution
• What do you observe with this code?
• Do you observe significant performance differences between single threaded, lock-free and lock-based solutions to this problem?
1
Question 2: Atomic Stack
Construct a linked stack data structure which is where the last node pushed would be the first node to be popped. Try and make your stack a generic stack that can be associated with any data type.
struct stack_node; struct stack;
/**
* @return stack, returns a new stack object on the heap
*/
struct stack* stack_new(); /**
* Pushes a new object on the stack, this will be at the
* top of the stack.
* @param stack
* @param data
*/
void stack_push(struct stack*, void* data); /**
* Pops the last element from the top of the stack.
* @param stack
* @return object, object at the top of the stack
*/
void* stack_pop(struct stack*); /**
* Destroys the stack, deallocates any memory associated with it.
* @param stack
*/
void stack_destroy(struct stack*);
Once you have constructed stack, consider how you can apply atomic operations to the stack? How
could you make your stack usable from multiple threads without using locks.
• You will need to use a atomic_compare_exchange_* function for this task • What should you do if the operation fails?
• Discuss how you would implement the push and pop operation of your program
SOFT3410 Atomics
Concurrency Page 2 of 3
Question 3: Test and Set Lock – Homework
Using what you have learned from atomic operations and write your own lock mechanism. Use the following scaffold to start building your test and set spinlock.
struct tas; /**
* @pram taslock, initialises the handle for the taslock
*/
void tas_init(struct tas*); /**
* Locks, operation should be successful if the lock is valid.
* If the lock is invalid, the lock operation returns a non-zero integer
* tas lock that is currently in a locked state will keep threads waiting.
* @param taslock
* @return success
*/
int tas_lock(struct tas* t); /**
* Unlocks, operation should be successful is the lock is valid.
* If the lock is invalid, unlock operation returns a non-zero integer.
* @param taslock
* @return success
*/
int tas_unlock(struct tas* t); /**
* Destroys the tas lock, puts it in an invalid state
* @param taslock
*/
void tas_destroy(struct tas* t);
If the test and set lock has been initialised, the lock and unlock functions should return the value 0 to
indicate a success. Non-zero is reserved for errors regarding the lock.
• Construct your test and set spinlock
• Construct a test suite to ensure that it can handle multiple threads and applied to normal lock object
For your submission, your code submission must be uploaded onto USYD Github under the repo name soft3410hw7. We will only consider the last submission before 11:59pm, 25th October, 2020.
SOFT3410 Atomics
Concurrency Page 3 of 3