SOFT3410 Tutorial 8 Synchronisation 2
We will be looking into more synchronisation primitives and patterns in this tutorial
Question 1: Memory Fencing
Using the following source code, observe the effects of compiling your application using -O0 and -O2. Do you observe any errors in the behaviour with the application when executing it? Attempt to send an interrupt signal to this process.
#include
#include
#include
#include
int notified = 1;
void notifyme(int signo) { notified = 0;
}
int main(int argc, char** argv) {
signal(SIGINT, notifyme);
while(notified);
return 0; }
If you mark the following variable as volatile, do you observe any changes to your code? Discuss what kind of optimisation is being applied to your program.
1
Question 2: Dining philosophers
Assume that there are N philosophers sitting at a round table. A single chopstick is placed between two adjacent philosophers.
Every philosopher is either thinking or eating. However, a philosopher needs both chopsticks (to the left and to the right) to start eating. They are not allowed to acquire chopsticks that are not immediately adjacent to them. Complete the following program so that each philosopher is able to eat.
struct args { pthread_mutex_t lock; unsigned int id;
};
void* dine(void* arg) {
const unsigned id = *((unsigned *) arg); while (true) {
// TODO: Acquire two chopsticks first
// the ith philosopher can only reach
// the ith and (i + 1)th chopstick printf(“Philosopher %u is eating\n”, id);
}
return NULL; }
int main(void) {
unsigned args[THINKERS];
pthread_t thinkers[THINKERS]; pthread_mutex_t chopsticks[THINKERS];
// create the chopsticks
for (size_t i = 0; i < THINKERS; i++) {
if (pthread_mutex_init(chopsticks + i, NULL) != 0) {
perror("unable to initialize mutex");
return 1; }
}
// launch threads
for (size_t i = 0; i < THINKERS; i++) {
args[i] = i;
if (pthread_create(thinkers + i, NULL, dine, args + i) != 0) {
perror("unable to create thread");
return 1; }
}
SOFT3410 Synchronisation 2
Concurrency Page 2 of 7
// wait for threads to finish
for (size_t i = 0; i < THINKERS; i++) {
if (pthread_join(thinkers[i], NULL) != 0) {
perror("unable to join thread");
return 1; }
}
// remove the chopsticks
for (size_t i = 0; i < THINKERS; i++) {
if (pthread_mutex_destroy(chopsticks + i) != 0) {
perror("unable to destroy mutex");
return 1; }
}
return 0; }
Question 3: Semaphore philosophers
We have previously solved the dining philosophers problem by using a locking hierarchy. This time, use a semaphore for the table that only allows N/2 philosophers to eat at a time.
SOFT3410 Synchronisation 2
Concurrency Page 3 of 7
Question 4: Optimistic Locking
Optimistic locking will check for a conflict at the point of transaction, if no conflict exists, the trans- action will occur, if a conflict occurs, the modification will be attempted again from the beginning.
Given the following code, change the insert and remove functions to search for the node that is to be changed and the predecessor node. Stage the changes to the data structure, afterwards, lock the nodes and verify the data has not changed after locking both the predecessor and current node.
struct linkedlist_node { linkedlist_node* next; int* data;
size_t length; pthread_mutex_t lock;
};
struct linkedlist { linkedlist_node* head; size_t size;
};
struct linkedlist_node* listlist_node_new(int* data,
size_t length, linkedlist_node* next) {
struct linkedlist_node* node = malloc(sizeof(struct linkedlist_node)); node->data = data;
node->length = length;
node->next = next;
return node;
}
struct linkedlist* linkedlist_new() {
struct linkedlist* list = malloc(sizeof(struct linkedlist)); list->head = NULL;
list->size = 0;
return list;
}
SOFT3410 Synchronisation 2
Concurrency Page 4 of 7
void linkedlist_insert(struct linkedlist* list, size_t index, int* data, size_t length) {
if(list && data) {
if(list->head != NULL) { if(index > 0) {
size_t current_idx = 1;
struct linkedlist_node* current = list->head; while(current->next && current_idx < index) {
current = current->next;
current_idx++;
}
struct linkedlist_node* next = current->next; struct linkedlist_node* n = listlist_node_new(
data,
length,
next
);
current->next = n;
} else {
//move head
struct linkedlist_node* next = list->head; struct linkedlist_node* n = listlist_node_new(
data,
length,
next
);
list->head = n;
}
} }
}
void linkedlist_get(struct linkedlist* list, size_t index, int** data, size_t* length) {
if(list && data && length) {
size_t current_idx = 0;
struct linkedlist_node* current = list->head; while(current && current_idx < index) {
current = current->next;
current_idx++;
}
*data = current->data;
*length = current->length;
}
}
SOFT3410 Synchronisation 2
Concurrency
Page 5 of 7
void linkedlist_remove(struct linkedlist* list, size_t index, int** data, size_t* length) {
if(list && data && length) {
struct linkedlist_node* current = list->head; size_t current_idx = 0;
while(current && current_idx < index) {
current = current->next;
}
*data = current->data;
*length = current->length;
free(current);
} }
void linkedlist_destroy(struct linkedlist* list) { if(list) {
struct linkedlist_node* current = list->head; struct linkedlist_node* temp = NULL; while(current) {
temp = current;
free(temp->data);
free(temp);
} }
}
Compare your performance of optimistic locking with your coarse grained implementation.
SOFT3410 Synchronisation 2
Concurrency Page 6 of 7
Question 5: Read-Write Locking On Dynamic Array – Homework
You have been tasked with implementing a read-write dynamic array. Any add or remove function will be a write operation while a get function will be considered a read operation.
You will need to arrange different test cases that will look into different read-write ratios. Your test cases should check that you can correctly add, remove, insert and retrieve elements from the dynamic array and your functions are thread safe.
Afterwards, implement benchmarks with the following read-write ratios with your data structure and compare against your coarse grained implementation. Consider giving your data structure a set num- ber of elements at the beginning
• 10% Write, 90% Read • 40% Write, 60% Read • 50% Write, 50% Read • 60% Write, 40% Read • 90% Write, 10% Read
struct dynamic_array;
struct dynamic_array* dynamic_array_new(size_t initial_capacity);
void dynamic_array_add(struct dynamic_array *ary, void*value);
void* dynamic_array_get(struct dynamic_array *v, size_t index);
void* dynamic_array_remove(struct dynamic_array *ary, size_t index);
void dynamic_array_destroy(struct dynamic_array* ary);
• Construct test cases with different number of elements
• Using the test cases, measure and record the execution time of the data structure • Record these results and graph and compare your data structure
• Write a conclusion and explain your observations
For your submission, your code submission must be uploaded onto USYD Github under the repo name soft3410hw8. We will only consider the last submission before 11:59pm, 2nd November, 2020.
For your submission, your report must be submitted to canvas via TurnitIn. You must submit your report to canvas portal by 11:59pm, 2nd November, 2020.
SOFT3410 Synchronisation 2
Concurrency Page 7 of 7