2021q1 Homework4 (quiz4)

# 2021q1 Homework4 (quiz4) contributed by < `iLeafy11` > ###### tags: `linux2021` ## Thread Pool Workflow > TODO: The graphic that embedded in HackMD :::danger The graphic remain undone. :::  :::danger Text content too. ::: ## Source The code has been separated into three parts: * thread.h * thread.c * main.c So the following Makefile are defined for compiling the C code by using the GNU C Compiler, also available for detecting memory leak or segmentation fault by using valgrind. ### Makefile: ``` CC:=gcc -Wall -pthread obj:=pi eval pi: thread.o main.c $(CC) thread.o main.c -o pi -lm dthread: dthread.o main.c $(CC) dthread.o main.c -o pi -lm test: valgrind --leak-check=full --show-leak-kinds=all -s ./pi eval: $(CC) eval.c -o eval -lm clean: rm -f *.o $(obj) ``` ### `thread.h` ```c typedef struct __tpool_future *tpool_future_t; typedef struct __threadpool *tpool_t; /** * Create a thread pool containing specified number of threads. * If successful, the thread pool is returned. Otherwise, it * returns NULL. */ tpool_t tpool_create(size_t count); /** * Schedules the specific function to be executed. * If successful, a future object representing the execution of * the task is returned. Otherwise, it returns NULL. */ tpool_future_t tpool_apply(tpool_t pool, void *(*func)(void *), void *arg); /** * Wait for all pending tasks to complete before destroying the thread pool. */ int tpool_join(tpool_t pool); /** * Return the result when it becomes available. * If @seconds is non-zero and the result does not arrive within specified time, * NULL is returned. Each tpool_future_get() resets the timeout status on * @future. */ void *tpool_future_get(tpool_future_t future, unsigned int seconds); /** * Destroy the future object and free resources once it is no longer used. * It is an error to refer to a destroyed future object. Note that destroying * a future object does not prevent a pending task from being executed. */ int tpool_future_destroy(tpool_future_t future); ``` For `thread.h`, strutures and functions are declared as prototype for implementing thread pool. Two structures has been declared: * `struct __tpool_future` - the structure is required for holding the result value by the completed task. * `struct __threadpool` - the structure contains the information for the thread pool, including the pointer threads, how many threads are created, and also the jobqueue. ### `thread.c` In `thread.c`, those structures and functions need to be well-defined. #### Enumeration **`enum __future_flags`** ```c enum __future_flags { __FUTURE_RUNNING = 01, __FUTURE_FINISHED = 02, __FUTURE_TIMEOUT = 04, __FUTURE_CANCELLED = 010, __FUTURE_DESTROYED = 020, }; ``` Purpose: * The `__future_flags` enumeration is defined for setting the state of the structure `struct __tpool_future`. By setting the state, we are capable of organizing the operations properly in a multithreaded environment. * With each enum flag values are assigned power of 2, it allows the enumeration to represent a collection of each flags, and toggling them by using bitwise operations. #### Structures **`struct __threadtask`** ```c typedef struct __threadtask { void *(*func)(void *); void *arg; struct __tpool_future *future; struct __threadtask *next; } threadtask_t; ``` Members: * `void *(*func)(void *)` - A function pointer point to the target task function to be called (call-back function). * `void *arg` - A pointer of the argument to be passed to the function where the function pointer `func` point to. * `struct __tpool_future *future` - A pointer point to the structure `struct __tpool_future`, which will hold the result of completed task. * `struct __threadtask *next` - A pointer point to the another `struct __threadtask`, which allows the structure to form a singly linked list. Purpose: * It is an implementation of a linked list that listing a series pf tasks. * The tasks including the call-back function to be executed, the argument to be passed to the call-back function, and also the future object for holding the task result. **`struct __jobqueue`** ```c typedef struct __jobqueue { threadtask_t *head, *tail; pthread_cond_t cond_nonempty; pthread_mutex_t rwlock; } jobqueue_t; ``` Members: * `threadtask_t *head, *tail` - A pointer that points to a structure `threadtask_t`, which indicates the implementation of a queue structure (last in fist out). * `pthread_cond_t cond_nonempty`, `pthread_mutex_t rwlock` - The pthread condition variable and mutex lock allow the program to run in a multithreaded environment. Purpose: * This structure is the implementation of jobqueue used for listing thread pool. The queue structure (FIFO) is needed for retaining the sequence of the task jobs. * Also, considering running in a multithreaded environment, the mutex lock and the condition variable is necessarily required. **`__tpool_future`** ```c struct __tpool_future { int flag; void *result; pthread_mutex_t mutex; pthread_cond_t cond_finished; }; ``` Members: * `int flag` - An integer type flag is needed for setting the state. (Has mentioned in [Enumeration](#Enumeration) * `void *result` - The Pointer points to the result value that being calculated by the task function. Purpose: * This structure is required for holding the result value that returned by the completed tasks. * Also, the mutex lock and condition variable is needed for running the program in a multithreaded environment. **`__threadpool`** ```c struct __threadpool { size_t count; pthread_t *workers; jobqueue_t *jobqueue; }; ``` Members: * `size_t count` - An integer variable that holds the numbers of the workers (threads). * `pthread_t *workers` - A pointer that points to an array of POSIX threads. * `jobqueue_t *jobqueue` - A pointer that points to a `jobqueue_t` structure, which is the implementation of the jobqueue. Purpose: * This structure is the implementation of a thread pool. The tasks will put on the jobqueue, and the workers will be the threads that execute the tasks. #### Functions **`tpool_future_create()`** ```c static struct __tpool_future *tpool_future_create(void) { struct __tpool_future *future = malloc(sizeof(struct __tpool_future)); if (future) { future->flag = 0; future->result = NULL; pthread_mutex_init(&future->mutex, NULL); pthread_condattr_t attr; pthread_condattr_init(&attr); pthread_cond_init(&future->cond_finished, &attr); pthread_condattr_destroy(&attr); } return future; } ``` * This function will dynamically allocate memory in size of `struct __tpool_future`, then will initialize the value for each members of the structure. * The return value will be the pointer points to the space being allocated previously. **`tpool_future_destroy()`** :::success Refer to the explaination of [Enumeration](#Enumeration), for each flag not affecting each others, we can simply rewrite the `if` condition all by the bitwise operations instead of using any logical operators. ```diff int tpool_future_destroy(struct __tpool_future *future) { if (future) { pthread_mutex_lock(&future->mutex); - if (future->flag & __FUTURE_FINISHED || - future->flag & __FUTURE_CANCELLED) { + if (future->flag & (__FUTURE_FINISHED | + __FUTURE_CANCELLED | + __FUTURE_TIMEOUT)) { pthread_mutex_unlock(&future->mutex); pthread_mutex_destroy(&future->mutex); pthread_cond_destroy(&future->cond_finished); free(future); } else { future->flag |= __FUTURE_DESTROYED; pthread_mutex_unlock(&future->mutex); } } return 0; } ``` To note that the code is incomplete, so we need to consider the situation when the `__FUTURE_TIMEOUT` flag is turned on, and the timeout future object will not receive any result value, so it should be considered to be destroyed. ::: **`tpool_future_get()`** ```c void *tpool_future_get(struct __tpool_future *future, unsigned int seconds) { pthread_mutex_lock(&future->mutex); /* turn off the timeout bit set previously */ future->flag &= ~__FUTURE_TIMEOUT; while ((future->flag & __FUTURE_FINISHED) == 0) { if (seconds) { struct timespec expire_time; clock_gettime(CLOCK_MONOTONIC, &expire_time); expire_time.tv_sec += seconds; int status = pthread_cond_timedwait(&future->cond_finished, &future->mutex, &expire_time); if (status == ETIMEDOUT) { future->flag |= __FUTURE_TIMEOUT; pthread_mutex_unlock(&future->mutex); return NULL; } } else pthread_cond_wait(&future->cond_finished, &future->mutex); } pthread_mutex_unlock(&future->mutex); return future->result; } ``` * This function will get the result content from the future object of the finished tasks. * The while loop keep checking whether the task is finished, the function keep waiting until receive a `cond_finished` broadcast from the function `jobqueue_fetch()`, then will leave the loop and `return` the value of the result `future->result`. * But if the whole process is run out of the given time (`second`), the flag `__FUTURE_TIMEOUT` will be turned on then the function will `return NULL`. * Before `return` the value of pointer to the future object (whether is `NULL` or not), we unlock the future mutex lock. This allows the function `tpool_future_destroy()` to do their work. **`jobqueue_create()`** ```c static jobqueue_t *jobqueue_create(void) { jobqueue_t *jobqueue = malloc(sizeof(jobqueue_t)); if (jobqueue) { jobqueue->head = jobqueue->tail = NULL; pthread_cond_init(&jobqueue->cond_nonempty, NULL); pthread_mutex_init(&jobqueue->rwlock, NULL); } return jobqueue; } ``` * This function will dynamically allocate memory in size of `jobqueue_t`, then will initialize the value for each members of the structure. * The return value will be the pointer points to the space being allocated previously. **`jobqueue_destroy()`** ```c static void jobqueue_destroy(jobqueue_t *jobqueue) { threadtask_t *tmp = jobqueue->head; while (tmp) { jobqueue->head = jobqueue->head->next; pthread_mutex_lock(&tmp->future->mutex); if (tmp->future->flag & __FUTURE_DESTROYED) { pthread_mutex_unlock(&tmp->future->mutex); pthread_mutex_destroy(&tmp->future->mutex); pthread_cond_destroy(&tmp->future->cond_finished); free(tmp->future); } else { tmp->future->flag |= __FUTURE_CANCELLED; pthread_mutex_unlock(&tmp->future->mutex); } free(tmp); tmp = jobqueue->head; } pthread_mutex_destroy(&jobqueue->rwlock); pthread_cond_destroy(&jobqueue->cond_nonempty); free(jobqueue); } ``` * This function will run through the jobqueue and work on each element in different ways by checking its member `future` about its state `future->flag` individually. * If the `future` object of the job is labelled `__FUTURE_DESTROYED`, just simply destory the object. * Otherwise, label the future object of the job `__FUTURE_CANCELLED`. * Then free the memory of the job. * At last, free the whole jobqueue. :::warning Question: * The above code is questionable since the code `tmp->future->flag |= __FUTURE_CANCELLED;` doesn't actually do anything. * So does that mean the `else` statement is redundant? Or should it be existed for some other reasons? Then what is it or what are they? > The code was incomplete, and you have to improve it. > Always hack the program once you found something weird. Think of the functional cancellation operations. > :notes: jserv ::: **`__jobqueue_fetch_cleanup()`** ```c static void __jobqueue_fetch_cleanup(void *arg) { pthread_mutex_t *mutex = (pthread_mutex_t *) arg; pthread_mutex_unlock(mutex); } ``` reference: https://elias.rhi.hi.is/libc/Cleanup-Handlers.html :::info TODO ::: **`jobqueue_fetch()`** ```c static void *jobqueue_fetch(void *queue) { jobqueue_t *jobqueue = (jobqueue_t *) queue; threadtask_t *task; int old_state; pthread_cleanup_push(__jobqueue_fetch_cleanup, (void *) &jobqueue->rwlock); while (1) { pthread_mutex_lock(&jobqueue->rwlock); pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &old_state); pthread_testcancel(); while (!jobqueue->tail) pthread_cond_wait(&jobqueue->cond_nonempty, &jobqueue->rwlock); pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old_state); if (jobqueue->head == jobqueue->tail) { task = jobqueue->tail; jobqueue->head = jobqueue->tail = NULL; } else { threadtask_t *tmp; for (tmp = jobqueue->head; tmp->next != jobqueue->tail; tmp = tmp->next) ; task = tmp->next; tmp->next = NULL; jobqueue->tail = tmp; } pthread_mutex_unlock(&jobqueue->rwlock); if (task->func) { // reduce branch pthread_mutex_lock(&task->future->mutex); if (task->future->flag & __FUTURE_CANCELLED) { pthread_mutex_unlock(&task->future->mutex); free(task); continue; } else { task->future->flag |= __FUTURE_RUNNING; pthread_mutex_unlock(&task->future->mutex); } void *ret_value = task->func(task->arg); pthread_mutex_lock(&task->future->mutex); if (task->future->flag & __FUTURE_DESTROYED) { pthread_mutex_unlock(&task->future->mutex); pthread_mutex_destroy(&task->future->mutex); pthread_cond_destroy(&task->future->cond_finished); free(task->future); } else { task->future->flag |= __FUTURE_FINISHED; task->future->result = ret_value; pthread_cond_broadcast(&task->future->cond_finished); pthread_mutex_unlock(&task->future->mutex); } free(task); } else { pthread_mutex_destroy(&task->future->mutex); pthread_cond_destroy(&task->future->cond_finished); free(task->future); free(task); break; } } pthread_cleanup_pop(0); pthread_exit(NULL); } ``` * This function will fetch the tasks (jobs) repeatly from the jobqueue when the jobqueue is not empty. * When the jobqueue is however empty, then the function will wait until the jobqueue is available. * After successfully fetching a task, check the task function pointer, if it is a `NULL`, then just simply detroy its future object. * if the task function pointer has been succesfully assigned to the correct task function (which means it can't be `NULL`), then start work on the task. * By checking the flag of the future object of the tasks, each tasks will be executed in different ways. (Will leave the detail of this part unexplained since the implementation of it is incomplete, we'll discuss them later in `Improvement`) * The local variable `void *ret_value` will hold the value that returned from the task function. If the task is successfully done, then the result value of the future object of the task will be assigned to the value of the `ret_value`. ## Improvement & Questions ### Idea 1: Modify the linked list data structure of the jobqueue Rewrite the queue structure by using the circular doubly linked list that mentioned in [quiz2 - Question 1](https://hackmd.io/MGK7E7F4QlOAXX9kOEyY7w?view#%E6%B8%AC%E9%A9%97-1). In fact, it is the data structure used in Linux kernel ([include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)). ```c #include "list.h" ``` The reasons for using a circular doubly linked list for implementing the jobqueue is as follows: 1. By making it circular, we just need the head of list since the last element are connected to the head. 2. We don't need to bother to deal with the edge cases - the insertion/deletion of a list when the queue is empty. 3. Because it is a circular doubly linked list, so we get constant time complexity when operating the insertion/deletion of the queue. (Singly linked list (whether circular or non-circular) can also get constant time complexity, but it needs another pointer points to the last element, which may lead to 2.) #### Structure ```diff typedef struct __threadtask { void *(*func)(void *); void *arg; struct __tpool_future *future; - struct __threadtask *next; + struct list_head list; /* a doubly linked list structure */ } threadtask_t; typedef struct __jobqueue { - threadtask_t *head, *tail; + struct list_head head; + size_t size; pthread_cond_t cond_nonempty; pthread_mutex_t rwlock; } jobqueue_t; ``` #### Function **`jobqueue_create()`** ```diff static jobqueue_t *jobqueue_create(void) { jobqueue_t *jobqueue = malloc(sizeof(jobqueue_t)); if (jobqueue) { - jobqueue->head = jobqueue->tail = NULL; + INIT_LIST_HEAD(&jobqueue->head); + jobqueue->size = 0; pthread_cond_init(&jobqueue->cond_nonempty, NULL); pthread_mutex_init(&jobqueue->rwlock, NULL); } return jobqueue; } ``` **`jobqueue_destroy()`** ```diff static void jobqueue_destroy(jobqueue_t *jobqueue) { - threadtask_t *tmp = jobqueue->head; + threadtask_t *tmp; + struct list_head *curr, *next; - while (tmp) { - jobqueue->head = jobqueue->head->next; + list_for_each_safe(curr, next, &jobqueue->head) { + list_remove(curr); + tmp = list_entry(curr, threadtask_t, list); pthread_mutex_lock(&tmp->future->mutex); if (tmp->future->flag & __FUTURE_DESTROYED) { pthread_mutex_unlock(&tmp->future->mutex); pthread_mutex_destroy(&tmp->future->mutex); pthread_cond_destroy(&tmp->future->cond_finished); free(tmp->future); } else { tmp->future->flag |= __FUTURE_CANCELLED; pthread_mutex_unlock(&tmp->future->mutex); } free(tmp); - tmp = jobqueue->head; } pthread_mutex_destroy(&jobqueue->rwlock); pthread_cond_destroy(&jobqueue->cond_nonempty); free(jobqueue); } ``` **Add new function: `jobqueue_pop()`** ```c static void *jobqueue_pop(void *queue) { jobqueue_t *jobqueue = (jobqueue_t *) queue; struct list_head *target = jobqueue->head.next; list_remove(target); jobqueue->size--; return (void *) target; } ``` * This is the implementation of `pop()` of the circular doubly linked list queue. * This operation is just simply delete the head element of the queue, so as we can imagine, the `push()` of the queue will be the function `list_add_tail()` defined in the header file `list.h`. **`jobqueue_fetch()`** ```diff static void *jobqueue_fetch(void *queue) { ... while (1) { ... - while (!jobqueue->tail) + while (list_empty(&jobqueue->head)) pthread_cond_wait(&jobqueue->cond_nonempty, &jobqueue->rwlock); pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old_state); /* pop queue */ - if (jobqueue->head == jobqueue->tail) { - task = jobqueue->tail; - jobqueue->head = jobqueue->tail = NULL; - } else { - threadtask_t *tmp; - for (tmp = jobqueue->head; tmp->next != jobqueue->tail; - tmp = tmp->next) - ; - task = tmp->next; - tmp->next = NULL; - jobqueue->tail = tmp; - } + struct list_head *node = (struct list_head *) jobqueue_pop(jobqueue); + task = list_entry(node, threadtask_t, list); ... } pthread_cleanup_pop(0); pthread_exit(NULL); } ``` :::success The following marked code is the operation of popping out the node `tmp` from the tail of the jobqueue, note that the linked list has been implemented by using a singly linked list data structure, and the time complexity of the code is $O(n)$. ```diff static void *jobqueue_fetch(void *queue) { ... while (1) { ... if (jobqueue->head == jobqueue->tail) { ... } else { - threadtask_t *tmp; - for (tmp = jobqueue->head; tmp->next != jobqueue->tail; - tmp = tmp->next) - ; - task = tmp->next; - tmp->next = NULL; - jobqueue->tail = tmp; } ... } ``` In fact, that "`queue_pop()`" operation implementation - "`list_delete_tail()`" in a singly linked list, can be improved to "`list_delete_head()`" using the same data structure. The time complexity can actually reach $O(1)$. So one of the advantages of using a circular doubly linked list is, guarantee this kind of operations run in $O(1)$ time complexity no matter how naive we implement it - whether list-head or list-tail, it rarely goes wrong. ::: **`tpool_apply()`** ```diff struct __tpool_future *tpool_apply(struct __threadpool *pool, void *(*func)(void *), void *arg) { ... if (new_head && future) { ... - if (jobqueue->head) { - new_head->next = jobqueue->head; - jobqueue->head = new_head; - } else { - jobqueue->head = jobqueue->tail = new_head; - pthread_cond_broadcast(&jobqueue->cond_nonempty); - } + switch (jobqueue->size) { + case 0: + list_add_tail(&new_node->list, &jobqueue->head); + pthread_cond_broadcast(&jobqueue->cond_nonempty); + break; + default: + list_add_tail(&new_node->list, &jobqueue->head); + break; + } + jobqueue->size++; ... } ... } ``` ### Questions **`tpool_future_create()`** ```diff static struct __tpool_future *tpool_future_create(void) { struct __tpool_future *future = malloc(sizeof(struct __tpool_future)); if (future) { future->flag = 0; future->result = NULL; pthread_mutex_init(&future->mutex, NULL); - pthread_condattr_t attr; - pthread_condattr_init(&attr); - pthread_cond_init(&future->cond_finished, &attr); - pthread_condattr_destroy(&attr); + pthread_cond_init(&future->cond_finished, NULL); } return future; } ``` :::warning Question: What is the purpose of red-marked code since the green-marked code actually works in this program? > Did you check the manual of POSIX Thread? If so, you will figure out the attributes on mutex lock and condition variable. Also, read the materials carefully. > https://hackmd.io/@sysprog/concurrency > :notes: jserv ::: :::success Actually, I've checked the manual of POSIX Thread several times. I was just thinking of, am I supposed to rewrite the program in this way. If it does, then the space cost for storing the variable `pthread_condattr_t attr` is not affected since its default value is still `NULL` when initialized. It can actually save resources from the memory cost of variables and also the function calls. ::: **`tpool_future_destroy()`** ```diff int tpool_future_destroy(struct __tpool_future *future) { if (future) { pthread_mutex_lock(&future->mutex); - if (future->flag & __FUTURE_FINISHED || - future->flag & __FUTURE_CANCELLED) { + if (future->flag & (__FUTURE_FINISHED | + __FUTURE_CANCELLED | + __FUTURE_TIMEOUT)) { pthread_mutex_unlock(&future->mutex); pthread_mutex_destroy(&future->mutex); pthread_cond_destroy(&future->cond_finished); free(future); } else { future->flag |= __FUTURE_DESTROYED; pthread_mutex_unlock(&future->mutex); } } return 0; } ``` :::warning Question: * After deleting following code, the program will still run normally without popping out any errors, warnings or memory leak message from valgrind. So why this `if` `else` statement is needed? * What is the purpose of this kind of design of the code? Is it related to the case when `pthread_create()` is failed? * By testing the case of timeout, the `if` statement actually being succuesfully accessed. ```diff int tpool_future_destroy(struct __tpool_future *future) { if (future) { pthread_mutex_lock(&future->mutex); if (future->flag & (__FUTURE_FINISHED | __FUTURE_CANCELLED | __FUTURE_TIMEOUT)) { pthread_mutex_unlock(&future->mutex); pthread_mutex_destroy(&future->mutex); pthread_cond_destroy(&future->cond_finished); free(future); - } else { - future->flag |= __FUTURE_DESTROYED; - pthread_mutex_unlock(&future->mutex); - } } return 0; } ``` * So in main function, delete the line `tpool_future_destroy(futures[i]);` will not receive any memory leak message from valgrind. Is it supposed to be like this? ```diff int main() { int bbp_args[PRECISION + 1]; double bbp_sum = 0; tpool_t pool = tpool_create(4); tpool_future_t futures[PRECISION + 1]; for (int i = 0; i <= PRECISION; i++) { bbp_args[i] = i; futures[i] = tpool_apply(pool, bbp, (void *) &bbp_args[i]); } for (int i = 0; i <= PRECISION; i++) { double *result = tpool_future_get(futures[i], 0 /* blocking wait */); bbp_sum += *result; - tpool_future_destroy(futures[i]); free(result); } tpool_join(pool); printf("PI calculated with %d terms: %.15f\n", PRECISION + 1, bbp_sum); return 0; } ``` ::: **`enum __future_flags`** ```diff enum __future_flags { - __FUTURE_RUNNING = 01, __FUTURE_FINISHED = 02, __FUTURE_TIMEOUT = 04, __FUTURE_CANCELLED = 010, __FUTURE_DESTROYED = 020, }; ``` :::warning Question: * The flag `__FUTURE_RUNNING = 01` is redundant since it will not trigger any operations or functions. * So in `jobqueue_fetch()`, the line `task->future->flag |= __FUTURE_RUNNING;` isn't really affect anything. * Is the flag `__FUTURE_RUNNING` really uneccesary? ```diff static void *jobqueue_fetch(void *queue) { ... if (task->func) { pthread_mutex_lock(&task->future->mutex); if (task->future->flag & __FUTURE_CANCELLED) { pthread_mutex_unlock(&task->future->mutex); free(task); continue; } else { - task->future->flag |= __FUTURE_RUNNING; pthread_mutex_unlock(&task->future->mutex); } ... break; } } } ``` ::: **`jobqueue_fetch()`** ```diff static void *jobqueue_fetch(void *queue) { ... pthread_cleanup_pop(0); + return NULL; - pthread_exit(NULL); } ``` :::warning Question: * The original code `pthread_exit(NULL);` will receive a memory leak message from valgrind, but if change the line to `return NULL;`, the memory leak problem seemed to be fixed. * Is that a really is the solution to this problem? Or it is actually not a problem by receiving the memory leak message from valgrind in this case? > Use [Thread Sanitizer](https://github.com/google/sanitizers) to figure out the underlying problems. > :notes: jserv ::: :::success The Program doesn't receive any warnings from the Thread Sanitizer, so it might not be a problem in this case. ::: :::warning The life time of jobqueue. function **`tpool_join()`** .. ::: ### Idea 2: Complete the program by introducing the shutdown/cancellation operations to the thread pool #### Structure ```diff struct __threadpool { size_t count; + int shutdown; pthread_t *workers; jobqueue_t *jobqueue; }; ``` #### Function :::info TODO: Idea of using `container_of` macro to find which specific worker is working on the jobqueue at that particular time. ::: ```diff - static void *jobqueue_fetch(void *queue) + static void *jobqueue_fetch(void *queue, int worker_id) ``` :::info TODO: The implementation of the above idea. ::: ### Idea 3: Using a ring buffer to replace the linked list queue structure. The advantages of using a ring buffer to replace the linked list queue structure: 1. We don't have to dynamically allocate / free memory every time when adding / deleting tasks. (Also can avoid memory fragmentation when running the program in a super long time, but generally we don't worry about the case) 2. Array generally performs better than linked list when it comes to speed. Cons: 1. The condition where the ring buffer is full is involved. 2. Two indices are required for indicating two positions where the producer applying the tasks and where the consumer fetching them. ### Idea 4: Atomic operation implementing lock-free version :::info TODO: ::: ## Methods of computing PI ### Leibniz’s Formula #### Implementation in C ### Bailey–Borwein–Plouffe formula #### Implementation in C ### Why use BBP's instead of Leibniz's

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.