# Communication、Synchronization、IPC、Message Queues

###### tags: `EOS`
Lec13-14 嵌入式作業系統

## Semaphore / mutex

- 可由一個以上的 thread 取得或釋放
- 可以用來做同步或互斥鎖


### 結構

`include/linux/semaphore.h`

struct semaphore {
    raw_spinlock_t        lock;
    unsigned int        count;
    struct list_head    wait_list;
};

https://ithelp.ithome.com.tw/articles/10213633

1. 盡可能使用 spin_lock
1. 在絕對不允許被搶佔的地方使用 raw_spin_lock
1. 如果 Critical Section 夠小，使用 raw_spin_lock

* count 允許多少資源進入 CS
* struct list_head wait_list 一個雙向的 Linked List，這邊用作排隊使用，規則是 FIFO(First-In-First-Out)，記錄所有正在睡眠的

### Types of Semaphores

- Binary semaphores
- Counting semaphores
- Mutual-exclusion (mutex) semaphores

#### Binary semaphores

左：互斥鎖
右：同步

#### Counting semaphores

左：保護相同資源，只給幾個人用
右：同步用，等所有人都到

##### Bounded vs. Unbounded Count
- Unbounded: maximum value that can be held by the count’s data type 受限於資料型別
- Unsigned integer vs. unsigned long value
- Bounded: Maximum count

#### Mutual-exclusion (mutex) semaphores

特殊的 Binary semaphores


1. ownership
2. recursive access
- 如果不支援 1. ownership、2. recursive access 同一支 task x 會被自己的函式鎖住。

3. task deletion safety 使用 mutex 時，task deletion locks 會防止 task 被刪除
4. protocols for avoiding mutual exclusion problems
優先序顛倒問題

解決辦法
- Priority inheritance protocol
• Priority of lower priority task is raised to that of higher priority task 低的繼承高的優先序，讓他釋放資源
• Priority of raised task is lowered to original value a/f releasing mutex 釋放完再降低優先序
- Ceiling priority protocol
• Priority of task that acquires mutex is set to the highest priority 低的變最高
• When mutex is released, the priority is lowered to its original value 使他釋放

==三個 semaphore 的差異性在哪？ 有資源時值是多少？ mutex 有哪幾個特性？==

`counting 只給 n 個人用相同資源，有可用資源值會是正數。 mutex 值為 0 時為 unlocked ，只能給一個 task 用 ， 且同一個 task 內的 function 都可以重複用資源，有 lock 可以防止被刪除 ， 使用 繼承優先序 或 置頂優先序 避免優先序顛倒。
`

### Common Semaphore Use 用途

wait 優先，但是會等 signal 釋放旗幟
1. Waiting-and-signal synchronization **B**
1. Multiple-task wait-and signal synchronization **B**
1. Single shared-resource-access synchronization **B**
1. Recursive shared-resource-access synchronization **M**
1. Multiple shared-resource-access synchronization **C**

1、2 同步用。3、4、5 溝通用。

#### Waiting-and-Signal synchronization

同步，雖然沒溝通但可以藉由 signal 釋放旗幟使 wait 開始


tWaitTask ( )
{
    :
    Acquire binary semaphore token
    :
}

tSignalTask ( )
{
    :
    Release binary semaphore token
    :
}

#### Multiple-Task Wait-and-Signal
flush: 所有 wait 一起跑

#### Single Shared-Resource-Access


保護資源 binary semaphore 從 1 開始
- 但可能被別人打開，除非用 mutex

tAccessTask() {
    :
    Acquire binary semaphore token
    Read/Write to shared resource
    Release binary semaphore token
    :
}

#### Recursive Shared-Resource-Access

tAccessTask ()
{
   :
   Acquire mutex  ->lock+1
   Access shared resource
   Call Routine A
   Release mutex  ->lock+3 -3 移除mutex
   :
}

Routine A ()
{
   :
   Acquire mutex  ->lock+2
   Access shared resource
   Call Routine B
   Release mutex  ->lock+3 -2
   :
}

Routine B ()
{
   :
   Acquire mutex  ->lock+3
   Access shared resource
   Release mutex  ->lock+3 -1
   :
}

#### Multiple Shared-Resource-Access

- #eq shared resources: 2
- #access tasks: 3

## Message queue

每段元素大小固定，一次放一段訊息，可能會有剩餘空間

- empty state -> receiving task waiting list (lined up comsumers)
- full state -> sending task waiting list

### States

### memory use

兩個process在中間共用，複製資料兩次

### Storage

* System Pools 共用
* Private Buffers 專用

### Receiving Messages

* Destructive read 常見
* Non-destructive read 可重複讀取，少見

### Use

1. Non-Interlocked, One-Way Data Communication

2. Interlocked 雙向 , One-Way Data Communication
* 同步：
* binary semaphore (0): ACK
* 收到一個訊息後 binary semaphore (1)


3. Interlocked, Two-Way Data Communication
* 有去有回

4. Broadcast Communication
* 支援 Non-destructive read 可重複讀取的電腦才能廣播

## Pipe


UNSTRUCTURED: 讀的大小不定

#include <unistd.h>

//int pipe(int filedes[2]);
pipe(fd)
write(fd[1],
read(fd[0],

data-producing task and a dataconsuming
task

### Pipe vs. Message Queue

- Pipe store a stream of bytes.
- Pipe does not support priority
- Pipe supports select operation

select 觀察有限時間 pipe 有沒有可用的讀寫

==message queue 和 pipe 差異性和應用？==

## Shared memory

`man 2 shmget` (2: syscall)

#include <sys/ipc.h>
#include <sys/shm.h>

//allocates a System V shared memory segment
int shmget(key_t key, size_t size, int shmflg);

函數傳入值
- key
* 0(IPC_PRIVATE)：會建立新共享內存對象
* 大於0的32位整數：視參數shmflg來確定操作。通常要求此值來源於ftok返回的IPC鍵值

- size
* 大於0的整數：新建的共享內存大小，以字節為單位
* 0：只獲取共享內存時指定為0

- shmflg
* 0：取共享內存標識符，若不存在則函數會報錯
* IPC_CREAT：當shmflg&IPC_CREAT為真時，如果內核中不存在鍵值與key相等的共享內存，則新建一個共享內存；如果存在這樣的共享內存，返回此共享內存的標識符
* IPC_CREAT | IPC_EXCL：如果內核中不存在鍵值與key相等的共享內存，則新建一個消息隊列；如果存在這樣的共享內存則報錯

函數返回值
* 成功：返回共享內存的標識符
* 出錯：-1，錯誤原因存於error中