# 作業系統工程-期末Project報告
## Mutex(互斥鎖)
### 互斥鎖概述
1. 問題 : 在多任務情況下，當任務1正在訪問資源時，在任務1尚未結束的情況下任務2突然來訪問資源，就可能會導致race hazard(or race condition)問題。

2. 解決方案 : 使用互斥鎖來控制可使用資源的任務。互斥鎖是一種用於同步訪問資源的鎖定機制。只有一個任務可以獲得互斥鎖。這意味著存在與互斥鎖關聯的所有權，並且只有所有者才能釋放互斥鎖。

3. 大致使用過程如下 :
(1) 互斥鎖先做初始化。
(2) 任務1想訪問資源，先獲得並且佔有互斥鎖，然後開始進行訪問。
(3) 任務2也想訪問資源，也要獲得互斥鎖，但被任務佔有了，所以只能等待。
(4) 任務1訪問完畢，釋放互斥鎖，任務2被喚醒，得到並佔有互斥鎖，然後開始訪問資源。
(5) 任務2訪問完畢，釋放互斥鎖。

### 程式碼個人解析與理解 (此處程式碼移植於參考資料[3])
以下程式碼(mutex.h)段落是Mutex Control Block。
在這個struct dos_mutex中，宣告由上到下依序分別等待互斥鎖的數量、任務的優先級、互斥鎖的擁有者(其資料型態源自於task.h的Task Control Block(TCB))以及等待互斥鎖的任務列表(其資料型態源自於list.h的Task List Control Block(TLCB))。

struct dos_mutex {
    dos_uint16          mutex_count;
    dos_uint16          mutex_priority;
    dos_task_t          mutex_owner;
    dos_task_list_t     mutex_pend_list;
};
typedef struct dos_mutex * dos_mutex_t;

以下程式碼為創建mutex的函式。
(1)此函式是屬於動態分配內存模式，意思是在函式內部會分配內存。
(2)宣告一個struct dos_mutex資料型態的變數並命名mutex，接著分配記憶體空間給mutex。
(3)檢查是否有分配成功，否則就印出"mutex is null"訊息並回傳0。
(4)使用memset來對mutex的一段記憶體區塊全部設定為0，並將mutex結構內部的所有變數做初始化處理。最後回傳mutex。

dos_mutex_t dos_mutex_create(void)
{
    dos_mutex_t mutex;
    mutex = dos_mem_alloc(sizeof(struct dos_mutex));
    if (mutex == DOS_NULL) {
        DOS_LOG_ERR("mutex is null\n");
        return DOS_NULL;
    }
    memset(mutex, 0, sizeof(struct dos_mutex));
    mutex->mutex_count = 0;
    mutex->mutex_owner = DOS_NULL;
    mutex->mutex_priority = 0;
    dos_task_list_init(&(mutex->mutex_pend_list));
    return mutex;
}

以下程式碼為刪除mutex的函式(回傳的資料型態dos_err其實就是signed int)。
(1)如果mutex不為空，則繼續執行，反之，輸出"the mutex to be deleted is null"，回傳DOS_NOK(在dos_def.h定義為無符號整數1，其在此代表有錯誤)。
(2)在mutex不為空情況下，使用dos_task_list_is_empty()函式(來自list.c的函式)去檢查待定互斥鎖的任務列表是否為真，若為真則將mutex的一段記憶體區塊全部設定為0，接著把mutex釋放掉，最後回傳DOS_OK(在dos_def.h定義為無符號整數0，其在此代表沒有問題)；反之，則輸出"there are tasks in the mutex pend list"，最後回傳DOS_NOK。

dos_err dos_mutex_delete(dos_mutex_t mutex)
{
    if (mutex != DOS_NULL) {
        if (dos_task_list_is_empty(&(mutex->mutex_pend_list))) {
            memset(mutex,0,sizeof(struct dos_mutex));
            dos_mem_free(mutex);
            return DOS_OK;
        } else {
            DOS_LOG_WARN("there are tasks in the mutex pend list\n");
            return DOS_NOK;
        }
    } else {
        DOS_LOG_WARN("the mutex to be deleted is null\n");
        return DOS_NOK;
    }
}

以下程式碼為獲取mutex的函式。
(1)宣告一個Task Control Block (源自於task.h)變數為task，先確認mutex是否為空或是否當前正在中斷，若為真，輸出文字後回傳DOS_NOK，反之，則繼續執行。
(2)呼叫dos_get_current_task()函式(源自於task.c)獲取當前的任務指派給變數task。
(3)判斷等待互斥鎖的數量是否為零，若為零，則將mutex struct內的變數部份進行遞增(mutex_count)與將task相關變數指派給它(mutex_priority、mutex_owner)，然後回傳DOS_OK。
(4)若當前有任務在佔用互斥鎖，則將等待互斥鎖的數量增加(此判斷式應該是其他任務想要獲取互斥鎖，然而當前任務正在佔有)，然後回傳DOS_OK。
(5)判斷系統調度是否被鎖定(dos_scheduler_is_lock()源自於sys.c所定義)或是否阻塞(timeout)，其中一個條件為真，則回傳DOS_NOK。
(6)若是欲獲取互斥鎖的任務優先級大於當前任務的優先級，則進入dos_set_task_priority()函式(源自於task.c)，其作用是進行優先級繼承，也就是說暫時設定當前任務的優先級為欲獲取互斥鎖的任務的優先級，等到當前任務結束後釋放互斥鎖，它就恢復為原來的優先級。
(7)呼叫dos_task_wait()函式(源自於task.c)，其作用是設定任務狀態為suspend，並將任務插入等待列表並休眠。
(8)呼叫dos_scheduler()函式(源自於task.c)，進行系統調度。
(9)最後一個判斷式目的是在恢復任務的運作，藉由DOS_RESET_TASK_STATUS()函式(源自於task.h所定義)將任務狀態值歸零，並於DOS_SET_TASK_STATUS()函式(源自於task.h所定義)設定任務狀態為Ready，最後使用dos_task_item_del()函式(源自於list.c)將任務從等待任務列表中刪除。

dos_err dos_mutex_pend(dos_mutex_t mutex, dos_uint32 timeout)
{
    dos_task_t task;
    dos_uint32 pri;
    if ((mutex == DOS_NULL) || (dos_context_is_interrupt())) {
        DOS_LOG_WARN("unable to continue to pend the mutex, the mutex is null or is currently in the interrupt context\n");
        return DOS_NOK;
    }
    task = (dos_task_t)dos_get_current_task();
    pri = dos_interrupt_disable();
    if (mutex->mutex_count == 0) {
        mutex->mutex_count++;
        mutex->mutex_priority = task->priority;
        mutex->mutex_owner = task;
        dos_interrupt_enable(pri);
        return DOS_OK;
    }
    if (mutex->mutex_owner == task) {
        mutex->mutex_count++;
        dos_interrupt_enable(pri);
        return DOS_OK;
    }
    if ((timeout == 0) || (dos_scheduler_is_lock())) {
        dos_interrupt_enable(pri);
        return DOS_NOK;
    }
    if (mutex->mutex_priority > task->priority) {
        dos_set_task_priority(mutex->mutex_owner, task->priority);
    }
    dos_task_wait(&mutex->mutex_pend_list, timeout);
    dos_interrupt_enable(pri);
    dos_scheduler();
    if (task->task_status & DOS_TASK_STATUS_TIMEOUT) {
        pri = dos_interrupt_disable();
        DOS_RESET_TASK_STATUS(task, (DOS_TASK_STATUS_TIMEOUT | DOS_TASK_STATUS_SUSPEND));
        DOS_SET_TASK_STATUS(task, DOS_TASK_STATUS_READY);
        dos_task_item_del(&(task->pend_item));
        dos_interrupt_enable(pri);
        return DOS_NOK;
    }
    return DOS_OK;
}

以下程式碼為釋放mutex的函式。
(1)宣告一個Task Control Block (源自於task.h)變數為task，先確認mutex是否為空或是否當前正在中斷，若為真，輸出文字後回傳DOS_NOK，反之，則繼續執行。
(2)呼叫dos_get_current_task()函式(源自於task.c)獲取當前的任務指派給變數task。
(3)若是等待mutex數量為0或者mutex擁有者並非當前的任務，其中之一為真，則輸出錯誤訊息並回傳DOS_NOK。
(4)條件式 : --(mutex->mutex_count)!=0，意思是當此任務要釋放mutex，而等待mutex數量會減少，若等待mutex的數量減少到0，則會跳過這個判斷式。
(5)判斷是否有優先級繼承發生，若是有，則恢復這個任務原本的優先級。
(6)最後一個判斷式是先檢查等待互斥鎖的任務列表是否為空；若為空，則分別將mutex_priority和mutex_owner進行歸零和清空；反之，呼叫dos_get_first_task()函式(源自於task.c)來取得等待mutex的列表中第一個Task Control Block，將其內部的變數部份進行遞增(mutex_count)與將task相關變數指派給它(mutex_priority、mutex_owner)
(7)呼叫dos_task_wake()函式(源自於task.c)主要讓任務從等待mutex的任務列表中移除，並將其狀態修改為ready。
(8)呼叫dos_scheduler()函式(源自於task.c)，進行系統調度。

dos_err dos_mutex_post(dos_mutex_t mutex)
{
    dos_task_t task;
    dos_uint32 pri;
    if ((mutex == DOS_NULL) || (dos_context_is_interrupt())) {
        DOS_LOG_WARN("unable to continue to post the mutex, the mutex is null or is currently in the interrupt context\n");
        return DOS_NOK;
    }
    task = (dos_task_t)dos_get_current_task();
    pri = dos_interrupt_disable();
    if ((mutex->mutex_count == 0) || (mutex->mutex_owner != task)) {
        DOS_LOG_WARN("unable to continue to post the mutex, the mutex is not be held, or the owner is not the current task\n");
        dos_interrupt_enable(pri);
        return DOS_NOK;
    }
    if (--(mutex->mutex_count) != 0) {
        dos_interrupt_enable(pri);
        return DOS_OK;
    }
    if (mutex->mutex_owner->priority != mutex->mutex_priority) {
        dos_set_task_priority(mutex->mutex_owner, mutex->mutex_priority);
    }
    if (!dos_task_list_is_empty(&(mutex->mutex_pend_list))) {
        task = dos_get_first_task(&(mutex->mutex_pend_list));
        mutex->mutex_priority = task->priority;
        mutex->mutex_count++;
        mutex->mutex_owner = task;
        dos_task_wake(task);
        dos_interrupt_enable(pri);
        dos_scheduler();
    } else {
        mutex->mutex_priority = 0;
        mutex->mutex_owner = DOS_NULL;
    }
    dos_interrupt_enable(pri);
    return DOS_OK;
}

### 結論
1.藉由這個互斥鎖程式(mutex.c)，學習到何為搶占式多任務處理，何為優先級反轉與繼承。互斥鎖可以用於任務與任務間的同步，但互斥鎖更多的是用於臨界資源的訪問。
2.同時也觀察到其他題目(task manager/timer/mailbox/message queue/event)的程式碼中都有create和delete相關函式；還有，所有題目都會使用到task manager的定義與函式，然而在這個互斥鎖程式中，task manager的定義與函式主要是用來處理任務優先級的問題。
3.互斥鎖的優點:在給定時間內，只有一個任務在執行，因此無競爭問題，並且確保資料一致性。
互斥鎖的缺點:(1)如果一個任務獲得一個鎖，並進入休眠狀態或被搶占，那麼另一個任務可能無法向前移動，這可能導致飢餓。(2)實現可能會導致忙著等待的狀態，從而浪費CPU時間。(3)某個時間內只允許一個任務訪問某個資源。

## 參考資料
##### [1] https://zh.wikipedia.org/zh-tw/
##### [2] http://rtos.100ask.org/freeRTOS%E6%95%99%E7%A8%8B/index.html
##### [3] https://github.com/jiejieTop/DoraOS
##### [4] https://www.geeksforgeeks.org/