---
# System prepended metadata

title: Communication、Synchronization、IPC、Message Queues
tags: [EOS]

---

# Communication、Synchronization、IPC、Message Queues 

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

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

![](https://i.imgur.com/eR0Ai77.png)

### 結構

`include/linux/semaphore.h`

```c
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


左：互斥鎖
右：同步
![](https://i.imgur.com/Ifpr5Dw.png)

#### Counting semaphores

左：保護相同資源，只給幾個人用
右：同步用，等所有人都到
![](https://i.imgur.com/bRpqXb8.png)

##### 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

![](https://hackmd.io/_uploads/H1w0PPm82.png)

1. ownership
2. recursive access
    - 如果不支援 1. ownership、2. recursive access 同一支 task x 會被自己的函式鎖住。
    ![](https://i.imgur.com/qV0z1sg.png)

3. task deletion safety 使用 mutex 時，task deletion locks 會防止 task 被刪除 
4. protocols for avoiding mutual exclusion problems
優先序顛倒問題
![](https://i.imgur.com/1c0oxXZ.png)

    解決辦法
    - 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 開始

![](https://i.imgur.com/kwkhKXm.png)
```c=
tWaitTask ( )
{
    :
    Acquire binary semaphore token
    :
}

tSignalTask ( )
{
    :
    Release binary semaphore token
    :
}
```
#### Multiple-Task Wait-and-Signal
flush: 所有 wait 一起跑
![](https://i.imgur.com/lojK7db.png)

#### Single Shared-Resource-Access

![](https://i.imgur.com/IfsVAXj.png)

保護資源 binary semaphore 從 1 開始
- 但可能被別人打開，除非用 mutex
```c=
tAccessTask() {
    :
    Acquire binary semaphore token
    Read/Write to shared resource
    Release binary semaphore token
    :
}
```

#### Recursive Shared-Resource-Access
![](https://i.imgur.com/QR46hkH.png)

```c=
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
![](https://i.imgur.com/bqC2LW6.png)

## Message queue

![](https://i.imgur.com/P8hJ2nC.png)
每段元素大小固定，一次放一段訊息，可能會有剩餘空間

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

### States
![](https://i.imgur.com/z3hLsI2.png)

### memory use

兩個process在中間共用，複製資料兩次
![](https://i.imgur.com/BZFfA7F.png)

### Storage

* System Pools 共用
* Private Buffers 專用

### Receiving Messages

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

### Use

1. Non-Interlocked, One-Way Data Communication
    ![](https://i.imgur.com/hmfulvl.png)

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

        ![](https://i.imgur.com/hUqPis4.png)


3. Interlocked, Two-Way Data Communication
    * 有去有回
    ![](https://i.imgur.com/jgTmWXZ.png)

4. Broadcast Communication
    * 支援 Non-destructive read 可重複讀取的電腦才能廣播
    ![](https://i.imgur.com/hEK1sc4.png)

## Pipe

![](https://i.imgur.com/GdSJXGQ.png)

UNSTRUCTURED: 讀的大小不定

```c=
#include <unistd.h>

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

![](https://i.imgur.com/4EOoZDo.png)
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

![](https://i.imgur.com/b4mwcD0.png)
select 觀察有限時間 pipe 有沒有可用的讀寫

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

## Shared memory

`man 2 shmget` (2: syscall)

```c=
#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中