大學部的OS記得今天要上課，記得提問
243 views
Skip to first unread message
ＯＳ大叔
Oct 30, 2023, 9:25:52 PM10/30/23
to 中正資工，作業系統概論
提問的網址是
然後今天可能會大著大家把「大綱」，也就是到目前為止的「學習脈絡」、「知識點」、「知識地圖」走過一次
習五
ＯＳ大叔
Oct 31, 2023, 12:58:57 AM10/31/23
to 中正資工，作業系統概論
1. 概論
硬體方面
什麼是DMA
什麼是中斷
什麼是polling，現代化作業系統怎樣實現polling(牽扯到軟體了)
CPU怎樣認識周邊裝置，多半是利用MMIO，裝置可以將自己的控制、狀態、資訊等，映射到CPU的記憶體空間，可以透過 load, store 指令存取記憶體或者裝置
雙模式執行。CPU有二個模式，將記憶體分成page或者seg.，每一塊記憶體（page or seg.）有不一樣的讀寫執行的權限要求。例如有些記憶體只允許kernel mode存取。
切換模式。從user mode切換到kernel mode，CPU會同時的(atomically)修改模式及IP（instruction pointer），例如切換到IP=0x8000的位置並變成核心模式
從kernel mode切換回user mode，CPU會依照kernel的指示，一次性的修改模式（變成user mode）及IP（由kernel指定）
軟體方面
驅動程式分成top half ＆ bottom half。top half是發生中斷時硬體要立即執行的中段向量服務函數（interrupt service routine），這部分程式碼較短，通常是讓硬體可以立即啟動下一個IO動作即可。bottom是可以延後執行的部分，例如把收進來的封包解碼，並複製到應用程式中。通常由kernel thread執行。
硬碟被虛擬化成 檔案系統＋目錄系統
Linux的「目錄系統」包含了各種資訊，有些資訊是硬碟上的檔案。也些資訊是電腦中的其他部件，例如CPU的溫度。因此 Linux 的目錄系統更像是「將資訊命名歸類的系統」
2. 作業系統結構
Linux在多核心（cpu core）的情況下會執行幾個kernel。Linux 很像是執行於特權模式（dual mode, privileged mode, kernel）的一群函數及資料結構。他們會被上層的應用程式呼叫（system call），也會被底層的driver呼叫（根源是interrupt）。這些函數及資料結構都是thread safe。就如同一個process有多個thread那樣。因此 Linux kernel是一個
對programmer來說：提供一個「平台」，可以開發應用程式（gdb，這需要作業系統的配合），讓軟體獨立執行（安全、穩定），可以讓CPU與IO的使用率變高（通常透過增加平行度，例如：load balance）。因為scheduling and buffering，可能會增加latency。
對Linux而言system call，是把所需要的服務及參數都放到暫存器。例如：write會是
//wirte(fd=9, char* buf, int size)
rdx = size;
rsi = buf;
rdi = 9;
rax = 1; //write的服務編號
VDSO，透過記憶體共享技術（後面會介紹）將核心中的資料同時分享給一個或者多個應用程式。最常見的是系統時間。以VDSO實作的system call其overhead等於function call
3. 行程與執行緒
目的：將要交給電腦的工作變成「一份又一份」（例如：word, excel），OS可以同時執行多個工作。為了增加CPU或者IO的使用率並且節約context switch的成本，讓應用程式裡面有多個thread。這是因為context switch的主要成本來自於切換時，CPU要「熱身」將許多cache 的資料換成自己所需要的資料。同一個process間的執行序共用記憶體，因此不用切換記憶體的內容，也就不會有切換後大量cache miss的問題。
為什麼越多應用程式或者執行緒可能會提高IO效率。主要是讓IO與CPU同時運作。此外有些IO在批次處理時比較快，例如SSD(對比於同樣工作，一個做完再做下一個)
thread local storage是什麼？
Linux的執行緒模型是one to one
many-to-many有時候會有比較好的效果，例如：這群執行緒間彼此等待（lock-unlock），可以透過user space library將控制權在這些互相等待的行程間切換。如果是one-to-one則需要使用system call（futex），優化空間較小
4. cpu scheduling
要怎樣決定「接下來要執行哪一個thread或者task」
記下，ready-running-waiting的那個圖
cpu scheduling不只影響每個task獲得的cpu time的量，而且也會影響i/o的效率。讓i/o的task越早開始做，那麼cpu與i/o的平行度才會高
cpu scheduling還需要考慮cache的效應。除此之外，大小核心、省電等也需要考慮
SJF在平均完成時間方面是最好的。
如果一個task會發出io的話，最好time quantium夠大，讓這個task盡量的都是自願放棄cpu，而非不自願（time quantium用完）（注：getrusage()中的ru_nivcsw; /* involuntary context switches */）
2.4 透過觀察「在一段時間內每個task的cpu 使用量」，使用量低的代表他跑去做io了，屬於io bound，因此可以動態調高他的優先權
2.4 的主要缺點，在多核心的情況下，所有core共用一個run queue，這個run queue就存取就變成效能瓶頸
2.6 在架構上的改善，每個core一個run queue，比較不會造成效能瓶頸。允許kernel thread檢查每個run queue的ready task的個數（注意，不是task的總數）以做task migration。為了支援task migration即使core存取自己的ready queue（run queue）也要先上鎖（lock-unlock）
O(1)也是根據「在一段時間內每個task的cpu 使用量」，決定是否為io-bound
ＣＦＳ的核心目的是：越高優先權在一段時間中可以獲得更多的cpu time，並且『『獲得cpu time的頻率增加』』
ＣＦＳ每次在cpu上執行的時間大致上是固定的(time quantium)，然後再重新到ready queue排隊，不一定要從隊伍的最後面開始排隊，優先權高的從中間插隊
ＣＦＳ的插隊準則是（目標是）應該獲得的cpu time與已經獲得的cpu time差距越大，越可以插隊到前面
EEVDF的插隊準則是：每個task每隔一段時間可以獲得1個time quantium。就像是自己有好幾台摩托車，每隔一段時間要保養，因為現在的錢不夠，要優先保養已經超出保養期限很久的
EEVDF比CFS在服務品質上（更高優先權、更絲滑的執行）更好
5. synchronization
舉例說明什麼是race condition
間單的數據可以直接用硬體解決，例如：atomic_load(int*);
volatile和atomic_xxx的差別？volatile只是保證：存取變數時compiler一定會編譯出load & store這二個指令
「理論上」正確解決 critical section的三個條件
用 while (cmp_xchg(lock_var...);...; lock_var=0; 寫出一個最簡單的lock unlock(不需要滿足bounded waiting)
正確的、完整的了解peterson's sol. 尤其是flag、turn的順序及意義
硬體方面
什麼是DMA
什麼是中斷
什麼是polling，現代化作業系統怎樣實現polling(牽扯到軟體了)
CPU怎樣認識周邊裝置，多半是利用MMIO，裝置可以將自己的控制、狀態、資訊等，映射到CPU的記憶體空間，可以透過 load, store 指令存取記憶體或者裝置
雙模式執行。CPU有二個模式，將記憶體分成page或者seg.，每一塊記憶體（page or seg.）有不一樣的讀寫執行的權限要求。例如有些記憶體只允許kernel mode存取。
切換模式。從user mode切換到kernel mode，CPU會同時的(atomically)修改模式及IP（instruction pointer），例如切換到IP=0x8000的位置並變成核心模式
從kernel mode切換回user mode，CPU會依照kernel的指示，一次性的修改模式（變成user mode）及IP（由kernel指定）
軟體方面
驅動程式分成top half ＆ bottom half。top half是發生中斷時硬體要立即執行的中段向量服務函數（interrupt service routine），這部分程式碼較短，通常是讓硬體可以立即啟動下一個IO動作即可。bottom是可以延後執行的部分，例如把收進來的封包解碼，並複製到應用程式中。通常由kernel thread執行。
硬碟被虛擬化成 檔案系統＋目錄系統
Linux的「目錄系統」包含了各種資訊，有些資訊是硬碟上的檔案。也些資訊是電腦中的其他部件，例如CPU的溫度。因此 Linux 的目錄系統更像是「將資訊命名歸類的系統」
2. 作業系統結構
Linux在多核心（cpu core）的情況下會執行幾個kernel。Linux 很像是執行於特權模式（dual mode, privileged mode, kernel）的一群函數及資料結構。他們會被上層的應用程式呼叫（system call），也會被底層的driver呼叫（根源是interrupt）。這些函數及資料結構都是thread safe。就如同一個process有多個thread那樣。因此 Linux kernel是一個
對programmer來說：提供一個「平台」，可以開發應用程式（gdb，這需要作業系統的配合），讓軟體獨立執行（安全、穩定），可以讓CPU與IO的使用率變高（通常透過增加平行度，例如：load balance）。因為scheduling and buffering，可能會增加latency。
對Linux而言system call，是把所需要的服務及參數都放到暫存器。例如：write會是
//wirte(fd=9, char* buf, int size)
rdx = size;
rsi = buf;
rdi = 9;
rax = 1; //write的服務編號
VDSO，透過記憶體共享技術（後面會介紹）將核心中的資料同時分享給一個或者多個應用程式。最常見的是系統時間。以VDSO實作的system call其overhead等於function call
3. 行程與執行緒
目的：將要交給電腦的工作變成「一份又一份」（例如：word, excel），OS可以同時執行多個工作。為了增加CPU或者IO的使用率並且節約context switch的成本，讓應用程式裡面有多個thread。這是因為context switch的主要成本來自於切換時，CPU要「熱身」將許多cache 的資料換成自己所需要的資料。同一個process間的執行序共用記憶體，因此不用切換記憶體的內容，也就不會有切換後大量cache miss的問題。
為什麼越多應用程式或者執行緒可能會提高IO效率。主要是讓IO與CPU同時運作。此外有些IO在批次處理時比較快，例如SSD(對比於同樣工作，一個做完再做下一個)
thread local storage是什麼？
Linux的執行緒模型是one to one
many-to-many有時候會有比較好的效果，例如：這群執行緒間彼此等待（lock-unlock），可以透過user space library將控制權在這些互相等待的行程間切換。如果是one-to-one則需要使用system call（futex），優化空間較小
4. cpu scheduling
要怎樣決定「接下來要執行哪一個thread或者task」
記下，ready-running-waiting的那個圖
cpu scheduling不只影響每個task獲得的cpu time的量，而且也會影響i/o的效率。讓i/o的task越早開始做，那麼cpu與i/o的平行度才會高
cpu scheduling還需要考慮cache的效應。除此之外，大小核心、省電等也需要考慮
SJF在平均完成時間方面是最好的。
如果一個task會發出io的話，最好time quantium夠大，讓這個task盡量的都是自願放棄cpu，而非不自願（time quantium用完）（注：getrusage()中的ru_nivcsw; /* involuntary context switches */）
2.4 透過觀察「在一段時間內每個task的cpu 使用量」，使用量低的代表他跑去做io了，屬於io bound，因此可以動態調高他的優先權
2.4 的主要缺點，在多核心的情況下，所有core共用一個run queue，這個run queue就存取就變成效能瓶頸
2.6 在架構上的改善，每個core一個run queue，比較不會造成效能瓶頸。允許kernel thread檢查每個run queue的ready task的個數（注意，不是task的總數）以做task migration。為了支援task migration即使core存取自己的ready queue（run queue）也要先上鎖（lock-unlock）
O(1)也是根據「在一段時間內每個task的cpu 使用量」，決定是否為io-bound
ＣＦＳ的核心目的是：越高優先權在一段時間中可以獲得更多的cpu time，並且『『獲得cpu time的頻率增加』』
ＣＦＳ每次在cpu上執行的時間大致上是固定的(time quantium)，然後再重新到ready queue排隊，不一定要從隊伍的最後面開始排隊，優先權高的從中間插隊
ＣＦＳ的插隊準則是（目標是）應該獲得的cpu time與已經獲得的cpu time差距越大，越可以插隊到前面
EEVDF的插隊準則是：每個task每隔一段時間可以獲得1個time quantium。就像是自己有好幾台摩托車，每隔一段時間要保養，因為現在的錢不夠，要優先保養已經超出保養期限很久的
EEVDF比CFS在服務品質上（更高優先權、更絲滑的執行）更好
5. synchronization
舉例說明什麼是race condition
間單的數據可以直接用硬體解決，例如：atomic_load(int*);
volatile和atomic_xxx的差別？volatile只是保證：存取變數時compiler一定會編譯出load & store這二個指令
「理論上」正確解決 critical section的三個條件
用 while (cmp_xchg(lock_var...);...; lock_var=0; 寫出一個最簡單的lock unlock(不需要滿足bounded waiting)
正確的、完整的了解peterson's sol. 尤其是flag、turn的順序及意義
ＯＳ大叔 在 2023年10月31日 星期二上午9:25:52 [UTC+8] 的信中寫道：
ＯＳ大叔
Oct 31, 2023, 1:09:19 AM10/31/23
to 中正資工，作業系統概論
ＯＳ大叔
Oct 31, 2023, 4:19:46 AM10/31/23
to 中正資工，作業系統概論
Reply all
Reply to author
Forward
0 new messages