# C語言與作業系統觀念(持續更新中)
###### tags: `c` `linux`
---
此篇目的是自我釐清C語言與作業系統的觀念
## 觀念釐清
`*ptr`的\*唸做『value of』 or 『dereference』。
`&ptr`的&唸『address of』。
`**ptr` 的\*\*不能唸『雙指標』，要唸成『pointer to pointer』。
lvalue 是『locator value』，不應該唸成『左值』。
`sizeof(type)` 是"operator"不是function，在**編譯時期計**算出資料型別的大小，常使用 sizeof(array) / sizeof(array[0])取得陣列個數。
C 永遠只有 call by value ，沒有~~call by address~~。
`parameter`: 用於函式宣告。 void swap(int par1,int par2);
`argument` : 用於呼叫函式。 swap(arg1,arg2);
## C雜談
void **(*d) (int &, char **(*)(char *, char **));
[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer?type=view)
* d is a pointer to a function that takes two parameters:
* a reference to an int and
* a pointer to a function that takes two parameters:
* a pointer to a char and
* a pointer to a pointer to a char
* and returns a pointer to a pointer to a char
* and returns a pointer to a pointer to void
---
void ( *signal(int sig, void (*handler)(int)) ) (int);
[How to read this prototype?](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype)
The whole thing declares a function called signal:
* signal takes an int and a function pointer
* this function pointer takes an int and returns void
* signal returns a function pointer
* this function pointer takes an int and returns a void
---
[What is the difference between const int*, const int * const, and int const *?](https://stackoverflow.com/questions/1143262/what-is-the-difference-between-const-int-const-int-const-and-int-const)
Read it backwards (as driven by Clockwise/Spiral Rule):
* `int*` - pointer to int
* `int const *` - pointer to **const int**
* `int * const` - **const pointer** to int
* `int const * const` - const pointer to const int
Now the first const can be on either side of the type so:
* `const int *` == `int const *`
* `const int * const` == `int const * const`
If you want to go really crazy you can do things like this:
* `int **` - pointer to pointer to int
* `int ** const` - a const pointer to a pointer to an int
* `int * const *` - a pointer to a const pointer to an int
* `int const **` - a pointer to a pointer to a const int
* `int * const * const` - a const pointer to a const pointer to an int
總結就是
1. const在*的左邊: 代表pointer指向的變數為常數，不能更改變數的值。
2. const在*的右邊: 代表pointer本身是常數，不能派給他新的記憶體位址。
```
int a = 5, b = 10, c = 15;
const int* foo; // pointer to constant int.
foo = &a; // assignment to where foo points to.
/* dummy statement*/
*foo = 6; // the value of a can´t get changed through the pointer.
foo = &b; // the pointer foo can be changed.
int *const bar = &c; // constant pointer to int
// note, you actually need to set the pointer
// here because you can't change it later ;)
*bar = 16; // the value of c can be changed through the pointer.
/* dummy statement*/
bar = &a; // not possible because bar is a constant pointer.
```
---
```
int a; // 一個整型數
int *a; // 一個指向整數的指標
int **a; // 一個指向指標的指標，它指向的指標是指向一個整型數
int a[10]; // 一個有10個整數型的陣列
int *a[10]; // 一個有10個指標的陣列，該指標是指向一個整數型的
int (*a)[10]; // 一個指向有10個整數型陣列的指標
int (*a)(int); // 一個指向函數的指標，該函數有一個整數型參數並返回一個整數
int (*a[10])(int); // 一個有10個指標的陣列，該指標指向一個函數，該函數有一個整數型參數並返回一個整數
```
---
* 記憶體配置
[C 語言程式的記憶體配置概念教學](https://blog.gtwang.org/programming/memory-layout-of-c-program/) 這篇文章已講得很清楚。
---
* 三元運算子
* x ? a:b
* 如果x為true時運算為a，x為false時運算為b。
---
## Bitwise Operators
[Bitwise Operators in C ](https://www.youtube.com/watch?v=8aFik6lPPaA&ab_channel=NesoAcademy)
---
## 靜態函式庫、共享函式庫與動態函式庫
1. 靜態函式庫（static library）:由.o檔(object files)組成的封裝檔，通常以lib為開頭，副檔名為.a檔.
- 在編譯時期，就把**所有**會用到的程式都一起把包進去
- 優點:在執行時，不會因為缺少檔案而不能執行
- 缺點:檔案較大，每次更新要重新編譯
2. 共享函式庫（shared library）:程式在執行時，才會去載入library，執行檔與share library是分開的，開頭以lib為主，附檔名.so檔.
- 優點:檔案大小較小，更新時執行檔也不需要重新編譯
- 缺點:執行時必須要有.so檔，如果是在機器內執行，機器內也必須有此.so檔
3. 動態載入函式庫（dynamically loaded library）:DL函式庫搭配share library而成，也是.so檔
- 與share library在載入函示庫時有很大的不同，share library式程式**開始**時自動載入函示庫(不一定都會使用到)，dynamically loaded library則是程式**真正**使用時才載入(有用到才載入)
- 使用dlopen開啟library
## Linux 硬連結與軟連結:ln
1. 硬連結: 使用相同的inode建立檔案，ln預設使用硬連結
---
## 作業系統(OS)
### Real-Time OPerating Systems
- Well-defined fixed-time constraints
- "Real-time" doesn't mean speed,but keeping deadlines.
- Guaranteed reponse and reaction times.
- Often used as a control device in a dedicated application:
- Scientific experiments,medical imaging systems,industrial control systems,weapon systems,etc.
### Process
觸發任何一個事件時，系統都會定義成為一個程序，並且給這個程序一個ID，稱為PID，同時依據啟發這個程序的使用者與相關屬性關係，給予這個PID一組有效的權限設定。
* 程式(program): 通常為binary program，放置在儲存媒體中，為實體檔案的形態存在。
* 程序(process): 程式被觸發後，執行者的權限與屬性，程式碼與所需的資料會被載入記憶體中，作業系統並給予這個記憶體內的單元一個識別碼(PID)，可以說程序就是正在運行的程式。
程序的呼叫(fork and exec)
process在linux相關指令，在另一篇[process](https://hackmd.io/gJsPVI89S5-ohNyABwtdLw?view#Process)中。
* 工作管理(job control):當我們登入系統取得bash shell之後，在單一終端機介面下同時進行多個工作的行為管理。
這些工作所觸發的程序必須來自自己shell的子程序
* 前景: 可以控制與下達指令的環境(foreground)。
* 背景: 可以自行運作的工作，無法使用[ctrl]+c來終止，可使用bg/fg呼叫該工作。
* 背景中「執行」的程序不能等待terminal/shell的input。
---
Process 5種狀態
* interrupt
* external interrupt: hardware -> signal
* internal interrupt: bug,overflow
* software interrupt: software -> system call
* context switching(內容轉換): CPU在執行時只能用一個process，要載入其他process，需先將process的內容存下來，在切換另一個process。
* short-term schedular: 從記憶體中挑一個從ready state到running state，合理安排每支程式執行time。
* long-term schedular: 選擇從new->ready決定當前有多少支程式可以執行，避免同時太多程式執行。
* medium-term schedular: 將IO,sleep等耗時的事情移出記憶體，挪出記憶體空間，達到好的空間使用。
---
* Layered OS
```
str[]="Hello" => user space
x = x+2 => user space
file.write(str) => kernal space write就是 system call
y= x+2 => 切回 user space
```
* API VS system call
* API: 使用者介面可以使用的函式庫。
* system call: OS可以使用的函式庫。
---
### Thread (#include<pthread.h>)
* 這篇解得很清楚 [POSIX Thread 介紹](https://hackmd.io/kUAJn1p3SLKpWD9JsY8fMQ?fbclid=IwAR27dhEv-L5nZZv_xm6-4pA02-2CCG_6SzwAXUZk8kYV1b4sACle7HcM4So)
---
**thread最重要的觀念是共享process內的資源(變數、記憶體等)。**
在多執行緒(Multithreading)，如果多個thread同時讀取同一個全域變數，會產生同步(Synchronization)問題。若thread互相搶資源，會造成死結(deadlock)。
[OS - Ch6 同步問題 Synchronization](https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html)
[OS - Ch7 死結 Deadlock](https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html)
[Race Condition](https://zh.wikipedia.org/wiki/%E7%AB%B6%E7%88%AD%E5%8D%B1%E5%AE%B3)
## 作業系統名詞比較
* explain process and thread?
* process(程序):已經load到記憶體裡的program，就是已經在運行的program。
* thread(執行續):process的單位，一個process可以有很多thread並共享資源。
---
* explain deadlock?
* 一組process互相等待對方的資源，造成process無法繼續執行，使CPU使用率大幅下降。
---
* explain mutex amd semaphore?
* mutex只能由上鎖的thread去解鎖，則semaphore沒有這種限制。
* mutex(互斥鎖):只能讓"一個"thread進入[critical section(臨界區段)](https://zh.wikipedia.org/wiki/%E8%87%A8%E7%95%8C%E5%8D%80%E6%AE%B5)，可避免[priority inversion(優先權反轉)](https://zh.wikipedia.org/wiki/%E4%BC%98%E5%85%88%E8%BD%AC%E7%BD%AE)。
* semaphore(旗標):可以讓"多個"thread進入critical section，但會發生priority inversion。
---
* compare Stack amd Queue
* Stack(堆疊):Frist in last out(FILO)。
* Queue(佇列):Frist in frist out(FIFO)。
---
* explain interrupt step
* 暫停目前的process執行，並[context switch](https://tfing.blogspot.com/2019/10/context-switch.html)保存資料 -> 根據interrupt ID查詢interrupt vector，取出對應的[ISR](https://terms.naer.edu.tw/detail/1280775/)地址 -> 到ISR的inital assredd執行該ISR -> ISR complete -> OS 恢復原先中斷的process執行。
---
* explain DMA(Direct Memory Access)
* DMA是一種傳輸方式，繞過CPU到IO device與Memory，CPU有更多時間可以執行process。
---
* explain kernal space amd user space
* kernal space可以控制CPU管理的硬體，比user space更高的權限，user space受到限制，只能做簡單的事情，如果要調用系統資源(I/O作業)，則需要通過system call到kernal space。
---
* explain Blocking/Non Blocking Synchronous/Asynchronous
* Blocking(阻塞):啟動I/O後，APP只能等待，不能繼續往下執行。
* Non Blocking(非阻塞):啟動I/O後，APP可以繼續執行與該次I/O無關的其他指令。
* Synchronous(同步):APP啟動I/O後，此程序會在OS的核心完成I/O後才返回APP。
* Asynchronous(非同步):APP啟動I/O後，OS核心不等待I/O完成，直接返回APP。
[談談對不同I/O模型的理解 (阻塞/非阻塞IO，同步/非同步IO)](https://iter01.com/553431.html)
---
* explain IPC (linux)
* IPC(行程間通訊):至少兩個thread或process之間的通訊方式。
* 信號(signal) 管道(pipe) FIFO 信號量(semphore) Socket ...等等。
[Linux 常見的六大 IPC 通訊方式](https://www.gushiciku.cn/pl/2HVJ/zh-tw)
---
* explain Concurrent(併發) Parallel(並行)
* Concurrent(併發):把task在不同時間交給CPU處理，同一時間task"不同時"進行。
* Parallel(並行):把每一個task交給每個CPU獨力完成，同一時間task"同時"進行。
---
* explain Race condition and critical sections
* Race condition:系統或process的輸出或出現時機不受控制。
* critial sections:程式的某區段在同一時間，只能有"一個"thread執行，否則會錯誤。
---
## 硬體知識補充
### 晶片間通訊協議
常用的通訊有3種，SPI、UART、I2C (**唸"I-squared-C"，不是"I-two-C"**)，詳細資訊點擊超連結。
[Serial Peripheral Interface Bus，SPI](https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E5%91%A8%E9%82%8A%E4%BB%8B%E9%9D%A2) : 是一種用於晶片通信的**同步**串行通信介面規範，主要應用於單晶片系統中。
 
* SCLK（Serial Clock）：串列時脈，由主機發出
* MOSI（Master Output, Slave Input）：主機輸出從機輸入訊號（資料由主機發出）
* MISO（Master Input, Slave Output）：主機輸入從機輸出訊號（資料由從機發出）
* SS（Slave Select）：片選訊號，由主機發出，一般是低電位有效
**優點**
* SPI協定預設是全雙工通信。
* 與漏極開路輸出相反，SPI的推輓輸出可提供良好的訊號完整性和高速度
* 比I²C或SMBus更高的吞吐量 。 不限於任何最大時鐘速度，可實現高速執行
* 完整的傳輸位協定靈活性
* 不限於8位元字
* 任意選擇訊息大小，內容和目的地
* 非常簡單的硬體介面
* 由於電路較少（包括上拉電阻），因此通常比I²C或SMBus的功耗要低，
* 沒有仲裁或相關的失敗模式
* 從站直接使用主時鐘，不需要精密振盪器
* 從站不需要唯一的位址 - 不像I²C或GPIB或SCSI
* 不需要收發器
* IC封裝只使用四個引腳，而電路板布局或連接器則少於並列埠
* 每個器件至多有一個獨特的匯流排訊號（晶片選擇）;其他訊號均可以共享
* 訊號是單向的，允許簡單的電氣隔離
* 簡單的軟體實現
**缺點**
* 即使是三線式SPI，也需要比I²C更多的IC封裝引腳
* 沒有帶內定址; 共享匯流排上需要帶外片選訊號
* 從機不支援流控制 （但主機可以延遲下一個時鐘邊沿以降低傳輸速率）
* 不支援動態添加節點（熱插拔）。
* 沒有從機檢測機制，主機無法檢測是否與從機斷開。
* 通常只支援一個主裝置（取決於裝置的硬體實現）
* 沒有錯誤檢測機制
* 無法進行資料校驗，不定義額外的協定時無法保證一致性。
* 與RS-232 ， RS-485或CAN匯流排相比，它只能處理短距離內的資料傳輸。（距離可以通過使用收發器如RS-422進行擴充）
* 有許多現有的變體，使得很難找到支援這些變體的主機配接器等開發工具。
* 一些變體，如雙路SPI ， 四路SPI和三線SPI是半雙工的。
* 必須通過帶外訊號來實現中斷，或者通過使用類似於USB 1.1和2.0的定期輪詢來類比中斷
（來源：維基百科）
---
[UART](https://zh.wikipedia.org/wiki/UART]https://makerpro.cc/2016/04/understand-what-is-uart/) :
---
[Inter-Integrated Circuit，I2C](http://wiki.csie.ncku.edu.tw/embedded/I2C) : 是一種串列通訊匯流排，使用多主從架構。
* 傳輸資料的串列資料線（SDA）
* 啟動或停止傳輸以及傳送時鐘序列的串列時脈線（SCL）
（來源：維基百科）
---
### [邏輯閘](https://zh.wikipedia.org/wiki/%E9%82%8F%E8%BC%AF%E9%96%98)
## 軟韌/嵌入式工程師面試題型
大部分來源自:[嵌入式筆試面試題目系列（彙總）](https://tw511.com/a/01/26758.html#1_2)、
### 程序與執行緒
* 多程序、多執行緒的優缺點
1. 一個程序死了不影響其他程序，一個執行緒崩潰很可能影響到它本身所處的整個程序。
2. 建立多程序的系統花銷大於建立多執行緒。
3. 多程序通訊因為需要跨越程序邊界，不適合大量資料的傳送，適合小資料或者密集資料的傳送。多執行緒無需跨越程序邊界，適合各執行緒間大量資料的傳送。並且多執行緒可以共用同一程序裡的共用記憶體和變數。
---
* 什麼時候用程序，什麼時候用執行緒
1. 建立和銷燬較頻繁使用執行緒，因為建立程序花銷大。
2. 需要大量資料傳送使用執行緒，因為多執行緒切換速度快，不需要跨越程序邊界。
3. 安全穩定選程序；快速頻繁選執行緒。
---
* Linux 多程序、多執行緒同步（通訊）的方法
1. 程序間通訊(IPC)
* 有名管道/無名管道
* 訊號
* 共用記憶體
* 訊息佇列
* 號誌
* socket
2. 執行緒間通訊
* 號誌
* 讀寫鎖
* 條件變數
* 互斥鎖
* 自旋鎖
---
### C
* static的用法
1. 用static修飾區域性變數：使其變為靜態儲存方式(靜態資料區)，那麼這個區域性變數在函數執行完成之後不會被釋放，而是繼續保留在記憶體中。
2. 用static修飾全域性變數：使其只在本檔案內部有效，而其他檔案不可連線或參照該變數。
3. 用static修飾函數：對函數的連線方式產生影響，使得函數只在本檔案內部有效，對其他檔案是不可見的（這一點在大工程中很重要很重要，避免很多麻煩，很常見）。這樣的函數又叫作靜態函數。使用靜態函數的好處是，不用擔心與其他檔案的同名函數產生干擾，另外也是對函數本身的一種保護機制。
---
* const的用法
1. 用const修飾常數：定義時就初始化，以後不能更改。
2. 用const修飾形參：func(const int a){};該形參在函數裡不能改變。
3. 用const修飾類成員函數：該函數對成員變數只能進行唯讀操作，就是const類成員函數是不能修改成員變數的數值的。
---
* volatile原理與作用
**最佳化**有時一個變數的值改變時，compiler不會直接寫進記憶體中，而是把值放入CPU暫存器，處理結束才放入記憶體，而有時這個變數是其他執行續的依據隨時會改變，而讀取時沒寫進記憶體中，會導致錯誤的結果。
在變數前面使用 volatile可以提醒compiler遇到此變數時不做優化，直接讀取"原始的記憶體位置"。
1. 中斷服務程式中修改的供其它程式檢測的變數。
2. 多工環境下各任務間共享的標誌。
3. 並行裝置的硬體暫存器（如：狀態暫存器）。
---
---
### 作業系統
* 死鎖的原因、條件
產生死鎖的原因主要是：
（1） 因為系統資源不足。 （2） 程序執行推進的順序不合適。 （3） 資源分配不當等。
如果系統資源充足，程序的資源請求都能夠得到滿足，死鎖出現的可能性就很低，否則就會因爭奪有限的資源而陷入死鎖。其次，程序執行推進順序與速度不同，也可能產生死鎖。
這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖。
1. 互斥條件：一個資源每次只能被一個程序使用。
2. 請求與保持條件：一個程序因請求資源而阻塞時，對已獲得的資源保持不放。
3. 不剝奪條件:程序已獲得的資源，在末使用完之前，不能強行剝奪。
4. 迴圈等待條件:若干程序之間形成一種頭尾相接的迴圈等待資源關係。
---
* Semaphore / Mutex /Spinlock (都以Linux角度)
* Semaphore: 處理資源分配，一到**多個**process/thread要進去Critical section，semaphore本身是一個計數器，紀錄有多少個process剩餘或等待，使用資源-1(sem_wait) 釋放資源+1(sem_post)，當counter小於0，要讀取共享資源的process/thread會被block，直到counter為正，另外Semaphore可以由其他process進行釋放。
* Mutex: "主要"使用在multithread中，因為thread共享資源，該資源需要被保護，有了mutex就可以保護critical section，thread拿到mutex才能讀取此global變數並lock保護住，其他thread不能讀取需要等待有mutex的thread結束並釋放lock，把mutex交給下一個排隊的thread，但會有priority inversion的問題要解決。
* Spinlock:一直讀取指定的lock，當lock不能讀取時會polling不斷嘗試，使用spinlock不會產生context switch，process不會休眠，不法執行的process會把cpu分擔出去。
Sign in with Wallet
Connect another wallet