# 【Linux】並行程式設計: 排程器原理筆記

## 前言
:::info
錄影內容
[排程器原理（上)](https://www.youtube.com/watch?v=Y2uYOsRev7o&t=29s)
:::

[Scheduling Internals](https://tontinton.com/posts/scheduling-internals/)
Scheduling動畫說明，說明Scheduler如何安排任務，
* Deadline
* 每個任務要在特定時間內執行完
* Limit Runtime
* CPU執行同一個任務時間有限

## Concurrency 並行

概念為一種程式架構，將程式拆分成多個可獨立執行運作的工作，以**並行不悖**說明最好，例如像是驅動程式都可獨立運作，但不需要平行化，在 Concurrent 中，工作可拆分成「獨立執行」的部份，於是「可以」讓很多事情一起做，但「不一定」要真的同時做。但 Parallelism 著重規劃， 將能夠並行的程式，分配給不同硬體單元，使其同時執行。
* 拆開多個的工作不一定要同時運行
* 多個工作在單核 CPU 上運行

> 指同時進行，不會互相妨礙。語本《禮記．中庸》。 例你白天讀書，晚上工作，這兩件事可以並行不悖。


## Parallelism 平行

指的是程式執行時候，同時執行多個程式。
Concurrency 可能會用到 Parallelism，但不一定要用 Parallelism 才能達成 Concurrency
* 程式會同時執行 (例如：分支後，同時執行，再收集結果)
* 一個工作在多核 CPU 上運行


## Concurrency vs Parallelism

[參考來源](https://medium.com/mr-efacani-teatime/concurrency%E8%88%87parallelism%E7%9A%84%E4%B8%8D%E5%90%8C%E4%B9%8B%E8%99%95-1b212a020e30)

## Synchronization 同步處理
確保多個執行單元運作並存取資源時，執行結果不會因為單個執行單元執行的先後順序去影響結果，而導致錯誤發生。

## Coroutine(協程、協同程序)
協程是一種用戶態的輕量級線程，可以想成一個線程裡面可以有多個協程，而協程的調度完全由用戶控制，協程也會有自己的registers、context、stack等等，並且由協程的調度器來控制說目前由哪個協程執行，哪個協程要被 block 住。當前任務進行時，如果有額外任務切入，就會是否切換到新任務。

coroutine可以藉由`setjmp`/`longjmp`在C語言中實做出來

## Preemptive and Non-preemptive
- [ ] To Do

## Event Driven Progamming 事件驅動程式
以事件來觸發程式繼續處理或者暫停的概念

## [Race Condition](https://en.wikipedia.org/wiki/Race_condition)

在程式設計中，有可能因為兩個不同線程同時存取到相同記憶體空間，造成不可預期的輸出，這邊稱作 **race condition** ，表示兩個 Thread 在競爭同一筆資料並修改。

## [Deal Lock](https://en.wikipedia.org/wiki/Deadlock)

死鎖（Deadlock）的定義是指在 Multi-Thread 或 Multi-Program 的計算機系統中，若干進程或線程因相互等待對方持有的資源而陷入一種無限等待的狀態，導致這些進程或線程無法繼續執行

### Dead Lock 四大充要條件(必要條件)
* Mutual Exclusion
資源只能同時分配給一個行程，無法多個行程共享
* Hold and wait rocess
手上可以握有資源並等待其它process的資源
* No preemption process
手上的資源只能是自願放掉的，不能被其它process搶走
* Circular wait
存在多個 process(P0, P1, …, Pn) 互相等待資源，而且等待的方式如下圖的Resource Allocation Graph 形成一個環。(有 circular wait 並不代表一定有 deadlock，但如果所有資源皆為 single instance 又有 cycle 則必然 deadlock)

## Program vs. Process vs. Thread 概念差異

### Program 程式
Program意思就是我們平常在寫的程式碼，也就是藍圖
* 相同 Program 的 Process 可以同時存在多個
* 我們可以在同一個電腦跑很多個相同的程式(Program)

### Process 程序
Process 就是實際上當 Program 被 loading 進入到記憶體，每一段程式碼都有可能會被 cpu 所執行，Process就是將 Program 這個藍圖跑起來
* 每一個 Program 在實體化的時候，至少會是一個 Process
* Process 是 Program 的實體(真正被宣告並使用)
* 對於 OS 來說，它是資源分配的最小單位
* 每一個 Process是互相獨立的(不會彼此存取相關的變數)
* Process 本身不是基本執行單位，而是Thread(執行緒)的容器

### Thread 執行緒
* Thread是程式碼片段實際的執行者，存取 Process, OS Resources 的記憶體
* 執行程式碼時， thread 會將變數保存在 stack 中，stack 會在程式 runtime 執行，但在 thread 中 stack 只有自己可以使用，不能與其他 thread共享
* heap 則不一樣，可以被任何的 thread 取用
* 一個 Process 至少有一個 thread，被稱作 **main thread**，Threads 在Process 中會分享其記憶體空間，使用 Shared memory space(heap)，來與其他Thread進行溝通
* 對於 OS 來說，它是執行的最小單位，也就是CPU的最小的執行單位
* 同一個 Process 會同時存在多個 Thread
* 同一個 Process 底下的 Thread 共享資源(heap)，如記憶體、變數等，不同的 Process 則否
* 在多執行緒中 (Multi-threading)
* 兩個執行緒若同時存取或改變全域變數(Global Variable)，則可能發生 **同步(Synchronization)** 問題
* 若執行緒之間互搶資源，則可能產生 **死結(Deadlock)**，同樣的，如何避免或預防上述兩種情況的發生，依然是 OS 所關注並改善的。

## Multi-Threading 多執行緒
* 在一個 process 中可以有多個thread以**concurrently(並行)** 或 **parallelism(平行)** 的方式運作
* 當一個 thread 有 memory leak，可能會耗盡其他 thread 的資源，進而導致process停滯
* 由於 Multi-threading的情況下，不同 thread會共享記憶體資源，在同一時間點只能一個thread去存取某個資料，以特定順序 Multiple threads 稱作 scheduling

## Multi-processing vs Multi-threading


## Process/Thread Pool 進(線)程池
* 帶有一堆thread，有需要就進去取用thread，不用重新建立來增加效能