# 2024q1 Homework (quiz10)
contruibuted by <`ICARUSHERALD96500`>
## 第十週測驗
**測驗二**
> 參考 [並行程式設計](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-hazard-pointer)
>
並行程式中，多支程式存取共用記憶體時，需要考慮寫入關係的先後順序，也就是 race condition。並且由於作業系統由於為分時系統的設計（time sharing），使用者難以保證並行程式之間執行的先後順序，即一支程式在進入 critical seciton 時，不免被 context switch，隨即變切換另一隻程式執行。而原本在執行的程式對尚未對主記憶體中的變數進行修改時就已經被搶佔。造成資訊前後不連續。
為解決該問題，使用 lock 似乎是簡單且直觀的方法。想要進入 critical section 的程式必須競爭該 lock 才能順利進入 cs。但是這樣又會導致多支並行程式中，僅有一支可以順利進入，而效率下降。而對於 lock-free 的機制而言就需要自行處理記憶體釋放的問題
結構體：
```c
struct lfq_node {
void *data;
union {
struct lfq_node *next;
struct lfq_node *free_next;
};
bool can_free;
};
struct lfq_ctx {
alignas(64) struct lfq_node *head;
int count;
struct lfq_node **HP; /* hazard pointers */
int *tid_map;
bool is_freeing;
struct lfq_node *fph, *fpt; /* free pool head/tail */
/* FIXME: get rid of struct. Make it configurable */
int MAX_HP_SIZE;
/* avoid cacheline contention */
alignas(64) struct lfq_node *tail;
};
```
lock-free queue node 的結構：
```graphviz
digraph structs {
node [shape=record];
struct_lfq_node [label="{lfq_node | data: void* | {union | next: struct lfq_node* | free_next: struct lfq_node*} | can_free: bool}"];
}
```
lock-free queue handler 結構
```graphviz
digraph structs {
node [shape=record];
struct_lfq_ctx [label="{struct lfq_ctx | head: struct lfq_node* | count: int | HP: struct lfq_node** | tid_map: int* | is_freeing: bool | fph: struct lfq_node* | fpt: struct lfq_node* | MAX_HP_SIZE: int | tail: struct lfq_node*}"];
}
```
**運作機制**
```graphviz
digraph structs {
node [shape=record];
struct_lfq_node1 [label="{lfq_node | {union | next: struct lfq_node* | free_next: struct lfq_node*} | can_free: bool}"];
struct_lfq_node2 [label="{lfq_node | {union | next: struct lfq_node* | free_next: struct lfq_node*} | can_free: bool}"];
struct_lfq_node3[label="{lfq_node | {union | next: struct lfq_node* | free_next: struct lfq_node*} | can_free: bool}"];
struct_lfq_ctx [label="{lfq_ctx }"];
struct_lfq_ctx -> struct_lfq_node1 [label="head, tail, fph, fpt"];
}
```
```graphviz
digraph structs {
node [shape=record];
struct_lfq_node [label="{struct lfq_node | data: void* | {union | next: struct lfq_node* | free_next: struct lfq_node*} | can_free: bool}"];
struct_lfq_ctx [label="{struct lfq_ctx | head: struct lfq_node* | count: int | HP: struct lfq_node** | tid_map: int* | is_freeing: bool | fph: struct lfq_node* | fpt: struct lfq_node* | MAX_HP_SIZE: int | tail: struct lfq_node*}"];
struct_lfq_ctx -> struct_lfq_node [label="head, tail, fph, fpt"];
struct_lfq_ctx -> HP [label="HP"];
struct_lfq_ctx -> tid_map [label="tid_map"];
}
```
首先 `tmp->can_free` 以及 `node->free` 均被設定為 `true`
```c
int lfq_init(struct lfq_ctx *ctx, int max_consume_thread)
{
struct lfq_node *tmp = calloc(1, sizeof(struct lfq_node));
if (!tmp)
return -errno;
struct lfq_node *node = calloc(1, sizeof(struct lfq_node));
if (!node)
return -errno;
tmp->can_free = node->can_free = true;
memset(ctx, 0, sizeof(struct lfq_ctx));
ctx->MAX_HP_SIZE = max_consume_thread;
ctx->HP = calloc(max_consume_thread, sizeof(struct lfq_node));
ctx->tid_map = calloc(max_consume_thread, sizeof(struct lfq_node));
ctx->head = ctx->tail = tmp;
ctx->fph = ctx->fpt = node;
return 0;
}
```
## 問題
:::info
**問題**
>If a process does not complete its full timeslice before it is preempted, then
it goes back in the ready queue. If it does run to the end of the timeslice, it
is placed in the expired array instead.-> chap. 2.2.3
**為什麼會發生還沒到時間中斷而 process 就被搶佔?**
Linus $O(1) scheduler$ : active 與 expire array，當 process 進入 CPU 執行後，分為兩種情況:1.'If it does run to the end of the timeslice, it is placed in the expired array instead.'，該 process 在使用完被分配到的 CPU 時長後，遭到時間中斷，接著被放到 expire array 等待 priority 被重新調整。 2. 'process does not complete its full timeslice before it is preempted' ，此時 process 尚未完全使用所被分配到的 CPU 時長就遭到搶佔，但我目前不清楚有甚麼情況會發生還沒到時間中斷就被搶占。是 hardware 或 Exception Interrupt 嗎?
```graphviz
digraph ProcessState {
node [shape=ellipse];
// Define the nodes
New [label="New"];
Ready [label="Ready Queue"];
CPU [label="CPU"];
Expire [label="expire array"];
// Define the edges
New -> Ready [label="admit"];
Ready -> CPU [label="dispatch"];
CPU -> Expire [label="time Interrupt"]
CPU -> Ready [label="??preempted before time slice??"];
Expire -> Ready [label="A new priority is given"]
}
```
:::
:::info
**問題**
在閱讀[並行程式設計: Atomics 操作](/OVPTyhEPTwSHumO28EpJnQ)，關於 MESI 與 MOESI 兩種協定的差異，MOESI 相對於 MESI，將資料狀態 `shared` 拆解為，`Owner` 與 `Shared` 兩種。旨在避免每次發送 Probe read 讀到一個狀態為 Modified 的 cacheline 時，就要將資料更新回主記憶體，但將資料寫回主記憶體非常浪費時間。因此 MOESI 更改為發送 Probe read 並且 hit 之後，將 CPU0 cacheline 由 Modified 變為 Owner。
既然是要避免在 Probe read 遇到 `Modified` 時，將資料更新回主記憶體。為什麼不直接在 MESI 協議上直接取消該機制就好，反而需要新增一個 `Owner` 狀態。並且由 MOESI 協議的作法似乎不同 CPU 之間的 cacheline 可以互相存取，無須透過主記憶體。因此想請問若在 MESI protocol 當中直接取消每次發送 Probe read 讀到一個狀態為 Modified 的 cacheline 時，就要將資料更新回主記憶體的機制的影響是什麼？因為在教材舉例 MOESI protocol 中，就沒有寫回主記憶體。
>5. CPU1 想對 Block 0 進行讀取，它會發 Probe read 給 CPU0，接著 CPU0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，CPU1 直接從 CPU0 讀取資料，並將其 cacheline 狀態設定成 Shared，而 CPU0 上的 cacheline 狀態則會從 Modified 變為 Owner。
>透過上述案例我們可發現，整個過程中並沒有涉及到任何將 cache 中資料更新回主記憶體的動作，因此，MOESI protocol 成功解決要將資料寫回主記憶體的問題。
:::
:::info
問題
在[並行程式設計: Hazard pointer](/1qjBY-JZR8GHCjQADDJdcQ) 當中提到下列程式碼，旨在取得non-active 狀態的 hazard pointer，但為什麼在 `if(p->active_||!CAS(&p->active_,0,1))` 會需要使用`p->active`、`!CAS(&p->active_,0,1)`兩種判斷式? 但其判斷的最終條件都是 `active==1`。
```c
// Acquires one hazard pointer
static HPRecType * Acquire() {
// Try to reuse a retired HP record
HPRecType * p = pHead_;
for (; p; p = p->pNext_) {
if (p->active_ ||
!CAS(&p->active_, 0, 1))
continue;
return p;
}
```
:::
## 參考
與我同組的同學：[youri1017](https://hackmd.io/@Yourui/linux2024-quiz10)
Sign in with Wallet
Connect another wallet