# 2024q1 Homework2 (quiz1+2)
contributed by < [`Ken-LuWeiRu`](https://github.com/Ken-LuWeiRu) >
###### tags: `linux2024`
> [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
## [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 1
#### 程式運作原理
#### 測試
在編譯過程中出現以下訊息
```
$git commit -m "Test q1t1"
Following files need to be cleaned up:
original_q1t1.c
queue.c
original_q1t1.c:124:11: style: Checking if unsigned expression 'n' is less than zero. [unsignedLessThanZero]
if (n <= 0)
^
original_q1t1.c:78:25: style: Local variable 'n' shadows outer variable [shadowVariable]
node_t *n = p;
^
original_q1t1.c:59:9: note: Shadowed declaration
int n = list_length(list);
^
original_q1t1.c:78:25: note: Shadow variable
node_t *n = p;
^
```
重寫 shuffle 和 quick_sort 函數
```c
void shuffle(size_t *array, size_t n)
{
// if (n <= 0) 移除這行,因為 size_t 類型的 n 永遠不會小於零
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
size_t t = array[j];
array[j] = array[i];
array[i] = t;
}
}
void quick_sort(node_t **list)
{
int length = list_length(list); // 更改這裡的變量名,避免與下方的 node_t 變量重名
int value;
int i = 0;
int max_level = 2 * length; // 這裡使用修改後的變量名
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *node_ptr = p; // 修改變量名稱,避免重名
p = p->next;
list_add(node_ptr->value > value ? &right : &left, node_ptr); // 這裡也使用修改後的變量名
}
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
測試
:::spoiler 測試程式碼
```c
int main(int argc, char **argv)
{
node_t *list = NULL;
const int sizes[] = {10000, 50000, 100000}; // 定義不同大小的測試案例
const int num_sizes =
sizeof(sizes) / sizeof(sizes[0]); // 計算測試案例的數量
double elapsed_times[num_sizes]; // 儲存每個測試案例的執行時間
for (int s = 0; s < num_sizes; ++s) {
size_t count = sizes[s];
int *test_arr = malloc(sizeof(int) * count);
// 產生隨機數據
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
// 構建鏈表
for (size_t i = 0; i < count; ++i)
list = list_construct(list, test_arr[i]);
clock_t start = clock(); // 開始計時
quick_sort(&list); // 執行快速排序
clock_t end = clock(); // 結束計時
elapsed_times[s] =
(double) (end - start) / CLOCKS_PER_SEC; // 計算經過時間
assert(list_is_ordered(list)); // 驗證列表是否已排序
list_free(&list); // 釋放列表記憶體
free(test_arr); // 釋放測試陣列記憶體
}
// 輸出每個測試案例的執行時間
for (int i = 0; i < num_sizes; ++i) {
printf("Size %d: %f seconds\n", sizes[i], elapsed_times[i]);
}
return 0;
}
```
:::
輸出
```
Size 10000: 0.001226 seconds
Size 50000: 0.008770 seconds
Size 100000: 0.019222 seconds
```
#### 改寫融入 lab0-c
採用 list.h 進行重構
```c
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> // 加入 time.h 以使用 clock()
#include "list.h" // 匯入 Linux 風格的鏈結串列定義
typedef struct __node {
struct list_head list; // 用於雙向鏈結串列的節點
long value; // 節點存儲的數值
} node_t;
int list_length(struct list_head *head)
{
struct list_head *pos;
int n = 0;
list_for_each (pos, head) {
++n;
}
return n;
}
node_t *list_construct(long n)
{
node_t *node = malloc(sizeof(node_t));
INIT_LIST_HEAD(&node->list); // 初始化 list_head 結構
node->value = n;
return node;
}
void list_free(struct list_head *head)
{
struct list_head *pos, *q;
list_for_each_safe (pos, q, head) {
// 確保 pos 不是指向 list_head 自身,否則將導致 list_entry
// 返回不正確的指針
if (pos != head) {
node_t *tmp_node = list_entry(pos, node_t, list);
list_del(pos);
free(tmp_node);
}
}
}
void quick_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *pivot = head->next;
struct list_head sorted;
INIT_LIST_HEAD(&sorted);
struct list_head *current = NULL, *temp = NULL;
LIST_HEAD(less);
LIST_HEAD(greater);
list_for_each_safe (current, temp, head) {
if (current != pivot) { // 確保當前節點不是 pivot
node_t *node = list_entry(current, node_t, list);
node_t *pivot_node = list_entry(pivot, node_t, list);
if (node->value < pivot_node->value) {
list_move_tail(current, &less);
} else {
list_move_tail(current, &greater);
}
}
}
quick_sort(&less);
quick_sort(&greater);
list_splice(&less, head);
list_splice_tail(&sorted, head);
list_splice_tail(&greater, head);
}
static bool list_is_ordered(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head)) {
return true;
}
node_t *current_node = NULL, *next_node = NULL;
struct list_head *node;
list_for_each (node, head) {
if (node != head) { // 確保節點不是 list_head 自身
current_node = list_entry(node, node_t, list);
if (node->next != head) { // 確保下一個節點不是 list_head 自身
next_node = list_entry(node->next, node_t, list);
if (current_node->value > next_node->value) {
return false;
}
}
}
}
return true;
}
void shuffle(int *array, size_t n)
{
// if (n <= 0)
// return;
// 移除這行,因為 size_t 類型的 n 永遠不會小於零
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
int main(int argc, char **argv)
{
struct list_head list;
INIT_LIST_HEAD(&list);
const int sizes[] = {10000, 50000, 100000};
const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
double elapsed_times[num_sizes];
for (int s = 0; s < num_sizes; ++s) {
size_t count = sizes[s];
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i) {
test_arr[i] = rand() % count;
}
shuffle(test_arr, count);
for (size_t i = 0; i < count; ++i) {
node_t *new_node = list_construct(test_arr[i]); // 使用构造函数
list_add_tail(&(new_node->list), &list);
}
clock_t start = clock();
quick_sort(&list);
clock_t end = clock();
elapsed_times[s] = (double) (end - start) / CLOCKS_PER_SEC;
assert(list_is_ordered(&list));
list_free(&list); // 使用自定义的函数清理内存
free(test_arr);
}
for (int i = 0; i < num_sizes; ++i) {
printf("Size %d: %f seconds\n", sizes[i], elapsed_times[i]);
}
return 0;
}
```
輸出
```
Size 10000: 0.001075 seconds
Size 50000: 0.006973 seconds
Size 100000: 0.015436 seconds
```
### 測驗 2
#### 解釋程式碼
#### 改寫進去lab0-c
我想將 timsort 加進 qtest.c 中
在 qtest.c 加入
```c
int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
const element_t *elem_a = list_entry(a, element_t, list);
const element_t *elem_b = list_entry(b, element_t, list);
return strcmp(elem_a->value, elem_b->value);
}
static bool do_timsort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q) {
report(3, "Warning: Calling timsort on null or empty queue");
return false;
}
if (exception_setup(true)) {
timsort(NULL, current->q, compare);
}
exception_cancel();
return q_show(0) && !error_check();
}
```
並且在 static void console_init() 中加入
```c
ADD_COMMAND(timsort, "Sort queue using timsort algorithm", "");
```
現在就可以在執行 qtest 後輸入 timsort 來排序
#### 撰寫 traces 中的測試文件
#### 改寫進去make test
#### 進行效能比較分析
## [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 1
#### 程式碼解釋
#### 編譯並配置 cgroup
##### [Control Group v2](https://docs.kernel.org/admin-guide/cgroup-v2.html)
##### [linux/kernel/cgroup/cgroup.c](https://github.com/torvalds/linux/blob/master/kernel/cgroup/cgroup.c)
##### [Resource Control in Embedded Linux Systems with cgroups](https://www.sysgo.com/blog/article/resource-control-in-embedded-linux-systems-with-cgroups)
##### [利用 buildroot 與 Qemu 建構簡易 Embedded Linux 環境](https://www.google.com/search?q=Buildroot&oq=Buildroot&gs_lcrp=EgZjaHJvbWUyBggAEEUYOTIGCAEQRRg8MgYIAhAuGEDSAQczMDFqMGoxqAIAsAIA&sourceid=chrome&ie=UTF-8)
### 測驗 2
#### 程式碼解釋
### 測驗 3
#### 程式碼解釋
## ref
https://port70.net/~nsz/c/c11/n1570.html#6.2.5
[ISO/IEC 9899 (a.k.a C99 Standard) ](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
[C11 (ISO/IEC 9899:201x)](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf)
[網頁版](http://port70.net/~nsz/c/c11/n1570.html)
[The Linux Kernel Archives](https://www.kernel.org/)
[cgroup.c](https://github.com/torvalds/linux/blob/master/kernel/cgroup/cgroup.c)