# 清大OCW 作業系統 筆記

> 希望我能持續下去:D
> 4/19: 我真的要瘋了 真的看不完了 所以我已經放棄全部讀完ㄌ:D

**簽到表:**
| 日期 | 課程 |
| --------- | --------- |
| 113/03/25 | ch0 1A~2D |
| 113/03/27 | ch1 3A |
| 113/04/01 | ch1 3B~4A |
| 113/04/04 | ch1 4B~4D |
| 113/04/12 | ch2 5A~5B |
| 113/04/14 | ch2 5C~5D |
| 113/04/15 | ch2 6A~6B </br> ch3 7A~7B|
| 113/04/19 | ch3 8B~9B |

---

**期中考範圍:** [讀書進度安排](/@ZYuC2002/MidtermProgress)
| 章節 | 影片範圍 | 時間 | 簡報 |
| -------- | -------- | -------- | -------- |
| Ch0(期中不會考?) | 1A~2D (\*6) | - | [Ch0](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap0%EF%BC%90_Operating%20System%20(OS).pdf) |
| Ch1 | 3A~4D (\*6) | 2:14:34 | [Ch1](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%901%EF%BC%BFOperating%20System%20Chap1%20Introduction.pdf) |
| Ch2 | 5A~6B (\*6) (6A、6B各一半) | 2:01:52 | [Ch2](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%902%EF%BC%BFOperating%20System%20Chap2%20OS%20Structure.pdf) |
| Ch3 | 6A~9B (\*10) (6A、6B各一半) | 3:24:16 | [Ch3](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%903%EF%BC%BFOperating%20System%20Chap3%20Processes%20Concept.pdf) |
| Ch4 | 15A~16B (\*4) | 1:26:13 | [Ch4](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%904%CB%8DOperating%20System%20Chap4%20Multithreaded%20Programming.pdf) |
| Ch5 | 16C~18B (\*6) | 2:25:06 | [Ch5](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%905%EF%BC%BFOperating%20System%20%EF%BC%BF.pdf) |
| Ch6 | 18C~21B (\*10) | 4:04:46 | [Ch6](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%906%EF%BC%BFOperating%20System%20Chap6%20%20Process%20Synchronization%20%EF%BC%BF.pdf) |
| Ch7 | 22A~22D (\*4) | 1:29:36 | [Ch7](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%907%EF%BC%8DOperating%20System%20Chap7%20%20Deadlocks%20%EF%BC%BF.pdf) |
| Ch8 | 10A~12B (\*8) | 3:50:56 | [Ch8](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%908%EF%BC%BFOperating%20System%20Chap8%20Memory%20Management%EF%BC%BF.pdf) |
| Ch9 | 13A~14D (\*6) | 2:24:19 | [Ch9](https://ocw.nthu.edu.tw/ocw/upload/141/news/%E5%91%A8%E5%BF%97%E9%81%A0%E6%95%99%E6%8E%88%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1_chap%EF%BC%909%EF%BC%BFOperating%20System%20Chap9%20Virtual%20Memory%20Management.pdf) |

==[考古專區](/4SJPziL1TzqqlvmAgL9u5g)==

---

**期末考範圍:**
| 章節 | 影片範圍 | 簡報 |
| -------- | -------- | -------- |
| Text | Text | Text |

**預計進度:**

---

[課程影片](https://youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX&si=HKYRQ7BPlUeaBWV6)
[講義](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)

[看同一個OS開放式課程的筆記](https://hackmd.io/@tim108108/H1HIlmmRj)

---

[toc]

---

# PART 1 Overview

### Mainframe Systems
- one of the earliest computers
- evolution: batch -> multi-programmimg -> time-shared

#### Batch
- 一次只能處理一個程式
- steps:
1. users submit jobs (program, data, control card) (上圖那些卡片)
2. operator sort jobs with similar requirements (一綑一綑的卡片排順序)
3. **OS simply transfer control from one job to the next**
- drawbacks:
- one job at a time
- no interaction between users and jobs
- CPU is often idle
- I/O速度比CPU慢非常多
- OS doesn't need to make any decision

#### Multi-programmimg
- overlap: 多個program
- keep both CPU and I/O devices working at higher rates
- spooling (Simultaneous Peripheral Operation On-Line)
- I/O is done with no CPU intervention
- CPU just needs to be **notified** when I/O is done
- 用interrupt實現 (Ch1)
- 先把 jobs load 到 memory (Job Scheduling)，再挑 job 到 CPU 去執行 (CPU Scheduling)
- OS tasks
- memory management
- CPU scheduling
- I/O system

#### Time-Sharing (Multi-tasking)
- An interactive system provides direct communication between the users and the system
- CPU switches among jobs **so frequently** that users may interact with programs (一有input就interact)
- Multiple users can share the computer simultaneously
- **switch job** when
- finish
- waiting I/O
- a short period of time
- OS tasks
- virtual memory
- file system & disk management
- process synchronization & deadlock

#### Mainframe System Summary

### Computer-System Architecture

#### Desktop Systems: single processor
personal computers

#### Parallel Systems: multiprocessor (tightly coupled)
- usually communicate through **shared memory**
- 有 shared memory，用 hardware 的方式把它們連起來

##### Processor 角度
1. Multi-Core Processor
2. Many-Core Processor

##### Memory 角度
1. Uniform Memory Access (UMA)
- 所有CPU都用同樣的方式接到memory
- **memory access time 都一樣**
- 最適合SMP
2. Non-Uniform Memory Access (NUMA)
- 每塊 memory 就像是 local memory，其他是 remote memory
- 當CPU想要access其他塊的memory時，需先跟別人的controller溝通 (間接)
- 較大的電腦用 (多CPU)
- local memory比較快，**remote memory比較慢**

##### Symmetric Multiprocessor System (SMP)
- each processor runs the **same** OS
- **most popular**

##### Asymmetric Multiprocessor System (AMP)
- each processor is assigned a specific task
- one master CPU & multiple slave CPUs
- more common in **extremely large systems**

#### Distributed Systems: loosely coupled
- each processor has its own local memory (沒有share memory -> 獨立)
- resource sharing
- load sharing

##### Client-Server Distributed System
- easier to manage and control resources
- **server** becomes the **bottleneck** and single failure point

##### Peer-to-Peer Distributed System
- every machine is identical -> decentralized

##### Clustered Systems
- cluster computers share storage and are closely linked via a **local area network (LAN)** or a **faster interconnect**
- Asymmetric vs. Symmetric Clustering
- asymmetric clustering: one server runs the application while other servers standby
- symmetric clustering: two or more hosts are running application and are monitoring each other

#### System Architecture Summary

### Special-Purpose Systems
#### Real-Time Operating Systems
- 在 deadline 之前做完就好ㄌ (跟名字 real-time 相反)
- deadline: guaranteed response and reaction times
- Soft vs. Hard Real-Time
- Soft real-time requirements: 盡量完成deadline，沒完成也不會怎樣 (根據priorty)
- ex. multimedia streaming (先跑出來框框，再跑出來影片...)
- Hard real-time requirements: 沒完成會有嚴峻的懲罰
- 通常沒有 secondary storage (memory以外的storage)

#### Multimedia Systems
audio and video files

#### Handheld/Embedded Systems
mobile device

### 大總結

## Ch1 Introduction

### What is OS?

#### Computer System

four components:
- User: 人、機器、其他computer
- Application: 定義系統資源用於解決計算問題的方式
- OS: **控制(control)** 和 **協調(coordinate)** hardware/資源的使用
- Hardware: 提供基本計算資源(e.g. CPU、內存、I/O設備)

#### What is an Operating System?
An OS system is the **permanent(永恆的)** software that **controls/abstracts hardware resources** for user applications.

Provides **Applications Programming Interface (API)** for user applications

#### General-Purpose OS
- system library(定義很多的function，package在一起) -> API

#### OS的定義
- 資源分配器: **管理和分配資源**以確保效率和公平
- 控製程序: **控制user program**的執行和**I/O**設備的操作，防止computer出錯和不當使用
- 內核Kernel(kernel就是OS): 一直運行的一個程序(其他都是系統/應用程序)

#### OS的目標
- 方便(使computer system易於使用和計算，適用於小型PC)
- 效率(有效率使用電腦硬體，適用於大型、共享、多用戶系統)

#### OS的重要性
- system API是user application和hardware間的唯一介面
- OS code不能有bug(任何中斷（例如無效訪問）就要重開)
- OS和computer architecture會相互影響

### Computer-System Organization
- 一或多個CPU和device controller透過common bus連接，share memory。
- 運作方式:
- 每個device controller都有一個local buffers
- status/data register -> 因為有讀&寫
- I/O是從device到device controller的local buffers
- CPU將數據從內存移動到device controller的local buffers

#### I/O的操作有兩種:
- Busy/wait output
CPU不斷監控等待I/O，但是**CPU在監控device時不能做其他工作**，很難同時進行其他I/O。
- Interrupt I/O
Interrupt**允許device改變CPU的控制流**，透過改變CPU的控制流在I/O與user process間切換。

#### Interrupt
- Interrupt-Driven I/O
- timeline
**1**和**2**的藍線:
1. I/O的buffer填滿資料 **(1)**
2. I/O發出interrupt
3. I/O把資料丟到CPU的memory **(2)**

- 
- signal by an interrupt from
- hardware **(signal)**: 可以隨時通過向 CPU 發送信號signal來觸發中斷
- software **(trap)**: 可能會因 **error** 或user對OS service的request **(system call)** 而觸發中斷
- common function
- interrupt一般通過 **[interrupt vector](https://zh.wikipedia.org/zh-tw/%E4%B8%AD%E6%96%B7%E5%90%91%E9%87%8F)** (含所有service routine的address(function pointer))，將控制轉移到interrupt service routine (ISR，中斷處理程式)
- 必須記錄被中斷指令的address
- 在處理一個interrupt時，**禁止傳入其他interrupt**，以防 lost interrupt

### Storage-Device Hierarchy
- memory
- main memory: CPU唯一一個可以直接訪問的大型storage (ex. RAM)
- secondary storage: main memory的extension，提供大容量的非揮發性storage (ex. 磁碟*magnetic disk*)
- Disk Mechanism
- 旋轉磁盤，並透過磁頭去去讀取(寫入)磁盤資料
- transfer time = data size / transfer rate
(傳輸時間 = data大小 / 傳輸速度)
- positioning time (random access time) = seek time (cylinder) + rotational latency (sector)
(seek time: 找資料的時間)
- caching
- 使用中的資料**暫時**從較慢的存儲，**複製**到較快的存儲
- **coherency(連貫性)** and **consistency(一致性)** issue
- 更改register中的copy，使其與其他copy不一致
- single task accessing：使用highest level的copy
- multi-task accessing：需要獲取recent的值
- distributed system：difficult, because copies are on different computers

### Hardware Protection
#### Dual-Mode Operation
- shared system resources需要OS保證**不正確的程序不會導致其他程序錯誤執行**
- 提供**hardware support**以區分至少兩種操作模式(最基本的)
- user mode: 來自使用者 **(OS以外的動作)**
- monitor mode(kernel mode): **OS**送出來的instruction
- 在hardware中加入**mode bit**以指定當前模式
- 0: kernel
- 1: user
- 當interrupt/trap或故障發生時，hardware會切換到monitor mode
**(system call (interrupt) -> 執行OS的程式碼)**
- privileged(特權) instructions
- 必須在monitor mode才能執行
- 使用者只能透過system call才能動作

#### I/O Protection
- 所有I/O instructions 都是 privileged instructions
(因為都是shared)

#### Memory Protection
- 保護interrupt vector和interrupt service routines、data access，避免被其他program over-write
- HW support: 超出定義範圍的內存受到保護
看有沒有在 (base) register~(base+limit) register 的範圍內
- base register: 保存最小的合法physical memory address
- limit register: 包含範圍的大小

#### CPU Protection
- 避免user program霸佔CPU，不給OS用
ex. 寫了一個無限迴圈，還是可以按ctrl+c暫停執行程式碼
- HW support - **timer**
- 在指定時間後interrupts computer
- 經過一個clock就遞減
- 當timer=0，就interrupt
- 用於實現**time sharing**
- load-timer(load: load到HW register，override目前的設定) 是一個privileged instruction

## Ch2 System Structures

### OS Services

#### User Interface
- CLI (Command Line Interface)
- 獲取user的指令並執行
- shell: command-line interpreter
- ex. CSHELL, BASH
- GUI (Graphic User Interface)
- usually mouse, keyboard, and monitor
- icon代表文件、programs、actions等
- CLI和GUI的目的相同

#### Communication Models
communication 分成兩大類:
- message passing
1. process A 把資料 copy 到 OS 的 memory
2. process B 從 OS 把資料 copy 到自己這邊
- 為何不能直接 A copy 到 B?
- protection
- shared memory
- 如果要有 shared memory，要先跟 OS 講，透過 system call 建一個 shared memory

### Applications-OS Interface

#### System Calls
- OS唯一的interface
- 通過software interrupt向kernel發出的request
- 通常用組合語言
- passing parameters
- **registers**
- **pointer**: store the parameters in a table in memory, and the table address is passed as a parameter in a register
- push (store) the parameters onto the **stack** by the program, and pop off the stack by operating system

#### API (Application Program Interface)
- user通常針對API寫程式，而非system call (API比system call方便)
- 通常由language libraries實現，例如 C Library (libc)
- 一個API的function call可能需要多個(或0個)system call來完成它
- why use API?
- 簡單
- 可移植性 (API是統一定義的interface)
- 效率 (並非所有功能都需要OS services或涉及kernel)

### System Structure
#### Simple OS Architecture
- only one or two levels of code
- 缺點: 不安全、難改善
- ex. 只有最上面那兩層是OS

#### Layered OS Architecture
- 下層獨立於上層 (第N層只能訪問第0~(N-1)層提供的服務)
外層可以call內層，內層不能call外層
- 優點: 好debug、維護
- 缺點: 效率較差、難定義層

#### Microkernel OS
- microkernel的上面都算是user space
$\rightarrow$ kernel程式碼越少越好 (user space東西越多越好)
- 透過message passing
- 優點: 容易擴展和移植
- 缺點: 效能差 (所有的動作都要再透過kernel)

#### Modular OS Structure
- 現代大多數ㄉOS都有用kernel modules
- 跟microkernel OS的差別: 全部都在**kernel space**
- 用到**object-oriented**的概念
- 每個core component都是獨立的
- 每個module都通過已知interface與其他module溝通

#### Virtual Machine
- 它把hardware和operating system kernel都視為hardware
- VM執行在**user space**
$\rightarrow$ critical instruction (user space和kernel space執行的結果不一樣) 難處理
$\rightarrow$ 當遇到無效的instruction 時，會透過 **interrupt** 去call底層的 kernel space 執行

#### Java Virtual Machine (JVM) (就是Java)
- 已編譯的Java程式是由JVM執行與平台無關的bytecodes
- Just-In-Time(JIT)編譯器可提高性能

# PART 2 Process Management

## Ch3 Process Concept

### Process Concept
- Program vs. Process
- Program:
- 被動ㄉentity
- 只是存在**disk**上，等著被執行的binary file (就4程式碼)
- Process:
- 主動ㄉentity
- 在**memory**裡面
- 正在執行
- a process include
- code segment (text section)
- data section: **global** variables
- stack: **temporary local** variables and functions (方便使用後直接pop掉)
- heap: **dynamic** allocated variables or classes
- current activity (**program counter**, register contents): 管理process的meta data
- a set of associated resources (ex. open file handlers，(檔案的開啟、或是跟OS要某些硬體的控制權)): 相關資源的set
- process in memory
stack和heap的大小會變化

#### Threads
- a.k.a lightweight process，使用CPU的最小單位
(一個process可以切成很多個threads)

- 同process的threads會共用
- code section
- data section
- OS resources (e.g. open files & signals)
- 但以下部份各自獨立
- stack
- register set
- thread ID
- program counter

#### Process State
:star:
- new
- process被創建出來
- 把program load到memory，並將前述記憶體狀態初始化
- ready
- process在memory中等待被指派到哪個processor(CPU核心)
- 在等待被執行的階段，會被放在**queue**當中
- running
- instruction可以被CPU執行ㄌ
- running $\rightarrow$ ready: 為了把主控權還給OS，一段時間(timer)就會interrupt(hardware signal)，把CPU switch給OS **scheduler**
- waiting
- 目前不需要CPU，等其他動作做完才需要，如I/O，完成後再重新放回Ready state
- terminated
- 把資源release掉 (還給OS)

#### Process Control Block (PCB)
記錄process的狀態

當一個process建立時，OS會allocate一個table

- **process state**
- **program counter**
- **CPU registers**
- CPU scheduling information (ex. priority)
- memory management information (ex. base/limit register): 只有process在執行時才會把這兩個值從memory load進CPU的register
- I/O status/information
- accounting information

#### Context Switch
圖中有兩個context switch
0. $P_0$ 正在執行
1. interrupt或system call打斷process
2. 把 $P_0$ 在CPU的state存起來
3. 讀取 $P_1$ 的state
4. $P_1$ 執行

- context switch的過程中，
$\because$ CPU沒有執行任何instrunction，且都會有process idle
$\therefore$ context switch 其實是**overhead**，浪費CPU的資源

### Process Scheduling

#### Process Scheduling Queues
- job queue (New State): 系統中所有的 Process
- ready queue (Ready State): 在main memory中正在及等待執行的process
- device queue (Wait State): 等待event處理(ex.I/O)的process

- queue之間的tail和head會串起來

- ready queue 中的 process 會等待被 load 進 CPU
- wait queue發生的原因
- I/O request (自己發出I/O request)
- time slice expired (time sharing)
- fork a child (create process)
- wait for an interrupt

#### :x:Schedulers (8A先跳過)

### Operations on Processes
#### Tree of Processes
- 每個 process 都會有自己的 unique 的 ID (processor identifier **(pid)**)
- processes 一定可以畫成如下的樹狀結構

#### Process Creation
- 資源之間的關聯性可能如下
- Process 的 Parent 及 Child (**完全**)共享資源
- Child Process **共享部份** Parent 的資源
- Parent 及 Child **完全不**分享資訊
- 兩種可能的執行方式
- Parent 及 Children **同時執行**
- Parent **等到 Children 結束**後才執行 (wating queue)
- :exclamation:兩種可能的記憶體空間
- Child 為 Parent 的**複製** (執行碼、counter 等與 Parent 完全一樣)，透過 sharing variable 溝通 (address 不同)
- 行為、內容物完全一樣，memory addr. 不一樣
- 將特定的 program 丟進 Child 的 code section，重設 counter，讓 Child 變成完全不同狀態的 Process，透過 message passing 溝通

#### UNIX/Linux Process Creation
- fork system call
- create new child process
- duplicate its parent (完全複製、完全一模一樣)
- concurrent execution (沒有先後順序 (不用等))
- child: return value of fork is **0**
- parent: return value of fork is **PID of the child process**
- memory space of fork()
(中fork跟右execlp比較)
- copy-on-wirte技術: runtime時發現值改變，儲存 Child 的與 Parent 的不同處 (child 在執行過程中會慢慢增長)
- fork會比較省空間
- execlp system call
- load a new binary file into memory (reset)
$\rightarrow$ 等於 new child process 在執行完全不同的程式
- wait system call
- parent waits for one of its child processes
$\rightarrow$ 強迫 parent 放到 waiting queue

範例:

#### Process Termination
- exit()
- 把資源還給OS (deallocation)
- parent 可利用 PID(abort) 來中止特定 child process
- cascading termination: killing parent $\rightarrow$ killing all its children

### Interprocess Communication (IPC)
- 定義: 在多個 processes / threads 間 (內部) 溝通的機制

#### Communication Methods
[Ch2 System Structures - OS Services - Communication Models]
- shared memory
- 共用記憶體空間
- 透過 memory 的 address 存取資料
- 優點: 快
- 缺點: synchronization
- **Consumer & Producer Problem**
- producer 負責產生information，
consumer 負責消耗這些數據
- 
- buffer 是大小為 B (有限空間) 的 circular array
- next free: in
- first available: out
- empty: in = out (out 拿光)
- full: (in + 1) % B = out (buffer 放滿了)
- 為了 sync，避免無法判斷 in = out 時是 empty 還是 full，必須使用 in+1 留一個空格
- message passing
- 透過 memory 的 copy，網路或跨電腦的程式通常都是以這種作法溝通
- 使用 send/recv message
- 優點: 沒有 conflict 的問題
- 缺點: 慢 ($\because$ 使用 system call)
- 藉由 Send/Receive 交換資訊
- communication link (這邊只寫logical，懶惰打physical)
- Direct or indirect
- direct $\rightarrow$ 打電話
- 指定要溝通的人是誰
- send(**P**, message) / receive(**Q**, message)
- indirect $\rightarrow$ 寄email
- 不會直接寄到別人手上 (mailbox (底下的A))
- send(**A**, message) / receive(**A**, message)
- Synchronous or asynchronous
- blocking (synchronous)
- blocking send / receive: 很明顯就是會等 message 送完才會繼續送 / return message
- non-blocking (asynchronous)
- non-blocking send / recieve: 很明顯就是不管怎樣都會馬上送 / return message
- buffer implementation
- Automatic or explicit buffering
- socket
- 透過 **IP & Port** 來 identify 使用者，port number 指的就是 process
- 藉由 unstructed stream of bytes 來溝通 (low level)(傳訊息)
- Remote Procedure Calls (RPC)
- 可以呼叫其他的 process 甚至其他電腦的 process
- 參數以及回傳值以 message 傳遞
- 我累了，我要放棄這個東西了 ;)

## Ch4 Multithreaded Programming

## Ch5 Process Scheduling

# PART 3 Process Coordination

## Ch6 Synchronization

## Ch7 Deadlocks

# PART 4 Memory Management

## Ch8 Memory-Management Strategies

## Ch9 Virtual-Memory Management

# PART 5 Storage Management

## Ch10 File System

## Ch11 Implementing File Systems

## Ch12 Mass Storage Structure

## Ch13 I/O Systems