# 2022q1 Homework5 (quiz6)

contributed by < [tommy2234](https://github.com/tommy2234) >

題目連結 [quiz6](https://hackmd.io/@sysprog/linux2022-quiz6)

## 測驗 1

### Overview

這支程式會建立多個 producer 和 comsumer ，也就是 reader threads and writer threads ，為了避免 race condition ，我們必須建立一些 mutex lock 和 spin lock 以確保讀寫的過程正確。

int main()
{
    mutex_init(&lock);
    mutex_init(&rwlock);
    spin_init(&print_lock);

    atomic_init(&n_readers_in, 0);
    atomic_init(&n_writers_in, 0);

    thread_t readers[5], writers[5];
    for (int i = 0; i < 5; i++) {
        thread_create(&readers[i], f1, NULL);
        thread_create(&writers[i], f2, NULL);
    }

    for (int i = 0; i < 5; i++) {
        thread_join(writers[i], NULL);
        thread_join(readers[i], NULL);
    }

    return 0;
}

### Read-Write Locks
模擬 Read 和 Write 的函式分別為 f1() 和 f2()

static void f1(void)
{
    mutex_acquire(&lock);
    if (++n_readers == 1)
        mutex_acquire(&rwlock);
    mutex_release(&lock);

    safe_printf(&print_lock, "Reader process in\n");
    atomic_fetch_add(&n_readers_in, 1);
    mutex_acquire(&lock);
    if (--n_readers == 0)
        mutex_release(&rwlock);
    mutex_release(&lock);

    atomic_fetch_sub(&n_readers_in, 1);
    safe_printf(&print_lock, "Reader process out\n");
}

static void f2(void)
{
    mutex_acquire(&rwlock);
    atomic_fetch_add(&n_writers_in, 1);
    safe_printf(&print_lock, "Writer process in\n");
    mutex_release(&rwlock);

    atomic_fetch_sub(&n_writers_in, 1);
    safe_printf(&print_lock, "Writers process out\n");
}

Read-Write locks 的運作模式類似 pthread 的 rwlock ，其邏輯如下：
1. 在沒有 writer 持有 rwlock 的情況下 ，可以同時有多個 readers 持有 rwlock 。
2. 當有一個 writer 持有 rwlock 時，其他所有 readers and writers 都無法持有 rwlock。

- 因此從 11, 12 行可以看到，最後一個 reader 完成讀取後必須負責釋放 rwlock。
- 並且在對紀錄 reader 和 writer 數量的變數進行增減時，都必須使用 atomic 指令一步完成（9, 15, 22, 26 行），因為他們顯然是 shared resource

### Creating threads
thread 的建立是透過 clone() system call 。
一個 thread 被建立之後，其相關資訊會被紀錄在 node_t 之中，也就是 thread control block (TCB) ，並且加入一個由 TCB 組成的 linked-list 。

/**
 * @brief Node in the TCB of the thread
 */
typedef struct __node {
    unsigned long int tid, tid_copy;
    void *ret_val;
    struct __node *next;
    funcargs_t *fa;
} node_t;

/**
 * @brief Singly-linked list of thread control blocks (TCB)
 */
typedef struct {
    node_t *head, *tail;
} list_t;

#### Clone system call
clone() 的 prototype 如下

int clone(int (*fn)(void *), void *stack, int flags, void *arg, 
          pid_t *parent_tid, void *tls, pid_t *child_tid);

parent_tid 和 child_tid 分別是在 parent 和 child 的 memory 中儲存 child tid 的位置。
我們對兩者都填入 &node->tid ，由於設定的 flag mask 中加入了 CLONE_PARENT_SETTID ，可以得知 child tid 將填入 parent_tid 參數所指定的位址。
> CLONE_PARENT_SETTID (since Linux 2.5.49)
Store the child thread ID at the location pointed to by parent_tid (clone()) or cl_args.child_tid (clone3()) in the parent's memory.

#define CLONE_FLAGS                                                     \
    (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | \
     CLONE_SYSVSEM | CLONE_PARENT_SETTID | CLONE_CHILD_CLEARTID)

### Spin lock VS mutex lock
spin lock 和 mutex lock 的實做方式有所不同，spin lock 採用的是 busying waiting ，而 mutex lock 則採用 sleep 的方式。

為何 spin lock 要採用 busy waiting 的方式不斷佔用 cpu 資源呢？

當一個 thread 只需要被 blocked 一小段時間，採用 spin lock 可以避免 cpu context switch 所帶來的 overhead ，這正是 spin lock 所適用的場景。