Skip to main content

Lab 5 part 2: Synchronization

Due: November 24 @ 10:00 PM

In this part you'll be making a spin semaphore.

Setup​

Ensure you're in the ece353 directory within VSCode. Make sure you have the latest skeleton code from us by running: git pull upstream main.

This will create a merge, which you should be able to do cleanly. If you don't know how to do this read Pro Git. Be sure to read chapter 3.1 and 3.2 fully. This is how software developers coordinate and work together in large projects. For this course, you should always merge to maintain proper history between yourself and the provided repository. You should never rebase in this course, and in general you should never rebase unless you have a good reason to. It will be important to keep your code up-to-date during this lab as the test cases may change with your help.

Part 2: Basic Spin Semaphore​

Thanks to Yang Su for the initial version of the lab, and Tianchen Zhang for editing and contributing test cases.

You can run: cd bss to begin this part of lab.

Task​

You will be implementing a spin semaphore. A semaphore contains a single value that can be incremented by post or decreased by wait if the value is above zero. When the wait encounters a non-positive value, a spin semaphore will spin until the value is above zero instead of making the thread sleep. Hence, the semaphore you are implementing will be different from the POSIX implementation.

You will implement the following two functions in bss/src/bss.c:

void bss_post(int* bss);
void bss_wait(int* bss);

void bss_post(int* bss);​

This function should increase the value in the semaphore by one every time it is called.

void bss_wait(int* bss);​

This function should decrease the value in the semaphore by one every time it is called. When the value is not positive, it will not deduct the value until it is above zero.

Tips​

Note that the semaphore is only ONE integer. Be aware that multiple threads can attempt to update the semaphore at the same time. Therefore, certain portions of the functions need to be atomic. The following API might be useful for your implementation:

__atomic_load_n
__atomic_store_n
__atomic_exchange_n
__atomic_compare_exchange_n
__atomic_fetch_add_n
__atomic_fetch_sub_n

You need to specify a memory model for each of these atomic operations. Memory models determine constraints on the memory order when compilers reorder instructions. In a relaxed memory model, memory operations can be shuffled. On the other hand, a strict memory model requires the memory operations to be executed in the order specified by the program.

In this lab, you may use __ATOMIC_RELEASE on all store operations, __ATOMIC_ACQUIRE on all load operations, and __ATOMIC_ACQ_REL on operations involving both load and store. When using compare and exchange, you may use the strong variation by specifying the argument weak as false.

Detailed specifications are listed on this webpage: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

Grading​

This part of the lab is worth 50 marks, each test case is worth 10 points. Run meson test -C build to run the test cases for Part 2.

Submission​

Simply push your code using git push origin main (or simply git push) to submit it. You need to create your own commits to push, you can use as many as you'd like. You'll need to use the git add and git commit commands. Push as many commits as you want, your latest commit that modifies the lab files counts as your submission. For submission time we will only look at the timestamp on our server. We will never use your commit times (or file access times) as proof of submission, only when you push your code to the course Git server.