2017q1 Homework4 (phonebook-concurrent)

contributed by <zmke>

開發環境

OS: Ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel® Core™ i5-4200H CPU @ 2.80GHz
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K

Toward Concurrency

處理器因為散熱和耗電的問題，速度的提升已經趨緩，使用 multicore processor 是使效能進步的另一個方法，前提是程式開發者必須知道如何有效運用 multicore processor

Concurrency vs. Paralleism

concurrency: 將程式拆成多個可以獨立運作的工作，但拆開的工作不一定要同時執行，可以是交錯執行
paralleism: 指同時執行多個工作。 concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency

Mutexes vs. Semaphores

mutex 和 semaphore 是可以交換的？
- mutex 和 semaphore 在實作上有一些相似之處，但兩者必須以不同的方式使用
- semaphore 正確的用法是從一個任務發送訊號到另一個任務
- mutex 總是按照 taken and release 的順序執行，但 semaphore 是 signal or wait 不是兩件事都做; one task is the producer of the event signal; the other the consumer.
- an example of mutex and semaphore

    /* Task 1 */
   mutexWait(mutex_mens_room);
      // Safely use shared resource
   mutexRelease(mutex_mens_room);

    /* Task 2 */
   mutexWait(mutex_mens_room);
      // Safely use shared resource
   mutexRelease(mutex_mens_room);


    /* Task 1 - Producer */
    semPost(sem_power_btn);   // Send the signal

    /* Task 2 - Consumer */
    semPend(sem_power_btn);  // Wait for signal

Priority Inversion
- 就算是正確地使用 mutex 來保護共享資源也可能會造成 priority inversion ，使 priority 高的工作無法如預期執行
- 多數的 RTOS 使用 preemptive scheduler ，會中斷 priority 低的工作讓 priority 較高的工作能優先執行，若被中斷的工作拿著需要優先執行的工作所需要的資源，會使工作無法如預期執行，高 priority 的工作必須 pending 等持有資源的工作完成
- When a medium-priority task preempts a lower-priority task using a shared resource on which the higher-priority task is pending. If the higher-priority task is otherwise ready to run, but a medium-priority task is currently running instead, a priority inversion is said to occur.
  在 Task L 完成之前， Task M preempt Task L ，造成 Task H 持續 pending
- 多數的 priority inversion 不會造成嚴重傷害，頂多就是讓工作延遲，但有時候可能會產生對系統來說關鍵性的問題。 1997 年 Mars Pathfinder 計劃中，在火星上進行探測的小車車透過一對高 priority 的程式來管理用來溝通各個設備的 dats bus ，就在共享資源被的 mutex 被低 priority 的氣象任務佔用的時候，有一連串 medium-priority 的工作 preempt 氣象任務，造成 bus distribution manager 沒辦法在時間內完成任務，最後倒置系統重置
- 關於 priority reversion 的研究有產出兩種解法 priority inheritance 和 priority ceilings
- priority inheritance : a lower-priority task inherit the priority of any higher-priority task pending on a resource they share
- priority ceilings : associates a priority with each resource; the scheduler then transfers that priority to any task that accesses the resource. resource 的 priority 設定成目前使用者中最高的 priority 再往上一級，當任務完成後回到原本的 priority

    void TaskA(void)
    {
        ...
        SetTaskPriority(RES_X_PRIO);
        // Access shared resource X.
        SetTaskPriority(TASK_A_PRIO);
        ...
    }

Reference

Toward Concurrency
LanKuDot 筆記