海大作業系統(上)

內容節錄於：蔡國輝教授的課程。

測驗檢討

ch1

1. 作業系統的歸類

作業系統是軟體程式，管控電腦的軟硬體資源。

2. Concurrently 與 simultaneously

• Concurrently：事件剛好同時進行。
• Simultaneously：發生事件的時間有緊密關聯。

disk controller與network interface controller-> Simultaneously

電腦同時執行多個應用-> Concurrently

西洋棋車輪戰-> Concurrently

目的：OS需同時管理多個程序及同時運作的硬體。

3. 非同步(Asynchronous)與 同步(Synchronous) 及 interrupt

• 非同步(Asynchronous)：接收到需求，不用一直等到需求完成再執行其他需求
• 同步(Synchronous)：必須等待對方完成動作，才能執行其他事情。

差別：發送需求的人是否需要等到需求完成後，才可以執行其他事情。

• 跟CPU無關　→　Asynchronous：來源是外部。
  如鍵盤、I/O、disk、Device Driver。
• 時序與CPU同步　→　Synchronous：CPU執行的指令與程序。

-> Asyn 會使用interrupt(類似External interrupt)。

Synchronous interrupt分為兩類：

• Processor-detected exceptions：執行普通的指令後，發生異常(overflow、out of range、除以零)引發中斷。
  Faults(違規)：違法操作，比如寫入沒有寫入權限的檔案。
  Traps(陷阱)：原本在執行的程式，因interrupt被trap到OS中。
• Programmed exceptions：執行特定的指令引發中斷。

interrupt

• 過程：

發生event → 產生signal → solve

• Polling
  CPU命令裝置執行 → "CPU等它完成並不斷詢問" → 直到收到完成訊號 → CPU處理後續
• Interrupt
  CPU命令裝置執行 → "CPU去處理其他事情" → 設備完成後發出 "中斷" → CPU處理後續

• 目的：

1. 要從一個process到另一個process。
2. 跳出無限迴圈。
3. 需要反應外界的event(執行ISR)。
   ex. Device需要引起CPU的注意，讓CPU來幫Device做事。

分為External與Internal：

• 外部 External：由CPU周邊(I/O Device)引發
• 內部 Internal：由CPU本身的不合法使用引發(Debug、Divide-by-zero、overflow)

4. 什麼情況下有中斷信號

• 網路線被拔掉(由硬體引發的External interrupt)
• 本身的電腦網卡收到封包(由硬體引發的External interrupt)

5. 一個行程只有20%的時間使用CPU，要讓CPU的使用率達到65%，至少需要載入幾個行程到記憶體

一個行程：

$0.8\mathrm{閒}\mathrm{置}$
兩個行程：

${0.8}^2\mathrm{閒}\mathrm{置}$
三個行程：

${0.8}^3\mathrm{閒}\mathrm{置}$
n個行程：

${0.8}^n\mathrm{閒}\mathrm{置}$
當

${0.8}^n\le 0.35$時，使用率為65%，n即為答案。

6. multi-programming系統

能夠同時執行多個程序的系統

• Passive：透過事件中斷，執行多個程序，由OS接受到中斷後切換
• Active：透過system clock更換執行的程序，由OS每段時間自主切換。

差別：OS是被動還是主動去切換執行的程序。

---

ch2

1. User mode 與 Kernel mode

User mode：有限制的模式，避免使用者產生無法回復的錯誤。
Kernel mode：Kernel取得系統的控制權。可以執行特權指令(Privileged Instruction)。

特權指令：I/O instruction、修改Timer、關閉中斷、修改Base/limit register

• 同一個使用者行程，有時會執行使用者程式碼，有時也會執行OS的程式碼。
• 使用者行程執行的時候，不一定都在user mode裡。

user space 與kernel space 是兩塊隔絕的記憶體空間，無法直接引用
透過register、stack、table傳遞

14. 特權指令

Set value of timer. Y
Read the clock. Y or N
Clear memory. Y or N
Issue a trap instruction. N
Turn off interrupts. Y
Modify entries in device-status table. Y
Switch from user to kernel mode. Y or N
Access I/O device. Y

3. 程式設計師，更需要了解API勝過system call。

• System Call : OS專屬， 移植性較差，研究OS必要
• API : 跨越多個OS ， 移植性較高，寫程式必要
  

4. write data to memory 並非特權指令

記憶體的保護交由MMU(Memory Management Unit, 內存管理單元)

7. 檔案總管也需要透過system call來操作檔案(改名字)。

8. 打開powerpoint使用那些system call

createProcess(), open(), read()

System call分為：
Process Control：fork(), wait()
File Management：open(), read(), write(), close()
Device Management：ioctl()
Information Maintenance：getpid()
Communication：socket()

13. system call 查表

%eax 是 x86_32 的 register
%eax == 0x26h 為第38號的系統呼叫：rename
register需要輸入 %ebx(oldname) 與 %ecx(newname)

int 0x80為中斷常式，對應的是system call。

---

ch3

1. Context switch

從process A 切換到 B 的過程中
kernel memory保存目前running process的狀態PCB
(行程的狀態、CPU register、stack、記憶體相關資訊、已開檔案。)
並載入下一個Process的PCB。
稱為Context switch

去讀取上一次執行時的狀態。

2. fork()

建立程序的新副本，達到多工處理。

• fork()產生兩個獨立的行程。
• 執行的程式與計數器都一樣。
• 起始值一樣，但變數相互獨立。
• local variable經過fork()後，在父子行程間是相互獨立的。

差別：return value of fork()

• For parent, the return value is child’s PID
• For child, the return value is 0

exit()：讓OS回收程序所使用的資源。
wait()：讓行程等待另一個行程完成才執行，可以避免zombi。

3. 子行程通常會先結束

4. Process的記憶體

包含stack、heap、data、text。
stack與heap是動態成長

5. 行程狀態

• running轉變為waiting
  I/O：行程等待使用者輸入
  Event-Wait：行程發出讀取檔案的要求，行程發出wait()。
• new：將 process 載入記憶體並初始化。
• ready：由於 CPU 的 core 有限，因此 process 在載入之後會先被存放在佇列（ready queue）中等待執行。
• running：程式執行中。
• waiting：程式執行的過程中，會遇到 I／O 需求，此時就會進入等待狀態，等 I／O 需求完成後再回到執行狀態 。
• terminated：程式執行完成，歸還資源。

ready status -> ready queue
waiting status -> device queue

6. OS記錄行程狀態的用途

• 排程(scheduling)時只需考慮ready狀態的行程。
• 可以讓使用者查詢行程狀態

12. importance hierarchy

foreground process, visible process, service process, background process, empty process, 資源緊繃的時候, 由重要性來決定從哪一個行程回收資源。

13 zombie and orphan process

zombie被收回的過程

• zombie process
  child process結束，沒有人去接住他的回傳值，導致child process還卡在process table(不占用CPU與記憶體)
• orphan process
  parent process已經終止，但child process還在執行。(無意：父進程崩潰、有意：長時間的服務進程)

---

ch4

1. 單核心不具備平行處理parallelism

2. thread

OS中運算的最小單位。

• 一個行程可以有多個thread
• 每個thread各有不同的起點與歷程
• 有自己的執行狀態(running, ready, waiting)
• 有自己私有的儲存(local variables)
• 有自己的context (registers, stack, …)
• 與同屬相同行程的thread 分享data section(static global variable), 檔案

共用Global variables
共用Process的資源：像Heap memory

3. 兄弟 sibling threads

• sibling threads：同一行程的threads
• 如果是sibling threads，切換thread只需要thread context switch
• 而不同行程的轉換會需要process context switch

4. Virtually all contemporary operating systems support kernel threads.

5. It is possible to create a thread library without any kernel-level support.

透過Thread Libraries提供的API
能夠新增和管理threads。
存在user space 或 kernel-level由OS調用

7. User-Level Thread(ULT)

Kernel 只認得 Process 不知道 Thread
倚靠user space的Thread Libraries
管理threads

優點

• switch 快，無須讓kernel參與
• 任何OS都可，library可以跨平台

缺點

• 一個thread waiting, 整個process waiting
• 同一行程的兩個ULTs，無法被兩個CPU分別執行

---

ch5

1. Scheduling

• Preemptive：搶先
• FCFS(FIFO)：先進先出

1. 公平
2. No Starvation
3. Non-preemptive
   
   

• SJF(Shortest Job First)：不可搶先

1. Average waiting time最小
2. 不公平
3. long-burst-time job可能有starvation
4. Non-preemptive

• SRT(Shortest Remaining Time First)：搶先
  
  

1. 更多的context switch
2. 不公平
3. 排班效率更好
4. starvation
5. preemptive

• Round-Robin：輪流執行time quantum=2
  

  

• Priority Scheduling

1. 不公平
2. 可以Preemptive or Non-Preemptive
3. Starvation
4. 可與RR結合(同樣priority RR)

3. Preemptive system,哪些事件會觸發CPU scheduler?

Preemptive

• Waiting 🡪 Ready
• Running 🡪 Waiting
• New 🡪 Ready
• Running 🡪 Terminated

有程序進入就需比較優先序
所以只要有進入ready或Running離開，皆會觸發scheduler

Non-Preemptive

• Running 🡪 Waiting
• Running 🡪 Terminated

只有Running的程序離開時，才會觸發scheduler

• 優缺點
  Preemptive
  優點：有彈性、效率較高、適用於real-time system和time-sharing system。
  缺點：context-switch的次數頻繁、容易使priority低的process發生starvation。
  Non-Preemptive
  優點：公平、可預測
  缺點：沒有彈性(工作時間短的需要等待時間長的)、較沒有效率

10. Disk scheduler

Disk scheduler使用Disk queue：被挑中的行程可存取disk
Disk scheduler應該優先挑選CPU bound行程：average waiting(for disk)time比較短

---

ch5

6. virtual machine

7. I/O-burst 與 CPU-burst

有9個CPU bursts，正常情況下，會有 8 個I/O bursts順利執行完畢。
會進入ready queue 9次以上

13. Solaris Scheduling

Multilevel Feedback Queues

---

2021 mid

2. open-source operating system
   有利：人人都可以維護與監督(更穩定與安全)、更多的衍伸作品(比如基於linux內核的Android、ubuntu、)
   免費的資源能讓電腦公司用更低的成本建構伺服器、開發軟體。
   讓用戶不需要花錢就能用穩定的系統。

不利：影響商用或是授權軟體的發展
因為開源系統是免費的，會影響到販賣作業系統的公司。

3. RR priority
4. preemptive, non-preemptive

討論區

• 使用者程式(User Program):使用者執行的程式或軟體
• 系統程式(System Program):與作業系統相關，用以控制硬體的程式
• 作業系統(Operating System):負責掌控電腦的資源，是使用者跟硬體之間的橋樑

int main(){   
int i;   
for(i = 0;i < 3; i++) {
     if(fork() == 0) {fork(); fork(); fork()}
  }
 }

9+8x9+8x(9+8x9)=729

ch1課堂筆記

中斷 (Interrupt)

• 過程：

發生event → 產生signal → solve

• Polling
  CPU命令裝置執行 → "CPU等它完成並不斷詢問" → 直到收到完成訊號 → CPU處理後續
• Interrupt
  CPU命令裝置執行 → "CPU去處理其他事情" → 設備完成後發出 "中斷" → CPU處理後續

• 目的：

1. 要從一個process到另一個process。
2. 跳出無限迴圈。
3. 需要反應外界的event(執行ISR)。
   ex. Device需要引起CPU的注意，讓CPU來幫Device做事。

Interrupt根據來源分為兩類：

1. 跟CPU無關　→　Asynchronous：如鍵盤、IO、disk、Device Driver。
2. 跟CPU有關　→　Synchronous：CPU執行的指令與程序。

• Synchronous：

1. Processor-detected exceptions：
CPU執行的指令與偵測狀況

• Faults(違規)：修正錯誤。
• Traps(除錯)：找出錯誤的地方與程式，跟Debugger有關。
• if 情況可修正->修正
  else -> 行程會被殺掉

2. Programmed exceptions：
一個軟體指令，專門處理System Calls。

• ISR(Interrupt Service Routine or Interrupt Handler)

1. 保留會使用的暫存器。
2. 中斷處理完成：發出EOI(End of interrupt)command
   給PIC(programmable interrupt controller)，讓CPU處理這個Interrupt。
3. 為Device提供服務。
4. 恢復暫存器。
5. 發出Iret指令(Interrupt Return) 代表結束->回復原狀。

---

Computer System

Operating System

• 對使用者更友善：順利執行應用程式
• 管理硬體更效率：管理與分配資源

兩種功能：

1. resources allocator
控管所有資源
2. control program
管理程序的執行

---

Computer Startup

Firmware：Bios

---

Storage Hierarchy

• Caching
• Device Driver

電腦運作模型

DMA

讓CPU可與週邊裝置的工作同時進行
把週邊裝置的協調交給DMA

Cycle Sealing

讓DMA能夠完整控制BUS
避免與CPU之間發生衝突

1. 向CPU申請使用BUS
2. CPU核准
3. 取用BUS的所有權

---

Process management

Program Counter：

透過OS管理行程的啟用與關閉

---