# 作業系統
###### tags:`考研`
[NTHU-OCW周志遠教授](https://www.youtube.com/watch?v=7EOttqasc5U&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV)
## CH0 Historical
### mainframe system**大型主機**
> 大型主機是針對一般交易需求與多工環境而打造的高可用度集中式系統，超級電腦則是為了高密度浮點運算而最佳化的分散式運算平台
>
better reliability security
**batch** systems 批次(一批一批)
initialize 初始化

**缺點drawbacks:**
1. one job at a time
2. no interaction between users and jobs
3. CPU is often **idle閒置**:
i/o speed << CPU speed
輸出入設備太慢
### multi-programing提升資源使用率:
**overlap I/O & computation**

**spooling**(simultaneous peripheral operations online):
CPU和 I/O的時間能重疊;做好後再通知I/O
--->還不能互動，依然是batch、一次一個

### time-sharing system:
interactive system
很頻繁地在CPU與I/O之間交換，不一定會馬上執行完全部

**何時切換工作?switch job when:**
1. finish
2. waiting I/O
3. **a short period of time**

OS tasks:
* virtual memory
* file system & diak management
* process **synchronization同步**:**需要規則** & deadlock
### 電腦歷程
#### personal computers
* convenience and responsiveness-GUI 圖形化介面
* different types of OS:windows、MacOS、Unix、Linux

**parallel system平行系統**
* Throughput 量大
* economical
* reliability可靠
* 分類
* SMP:Symmetric **multiprocessor system**
對稱多處理器系統
* AMP
非對稱多處理系統
在超大型系統中更常見

**multi-core processor多核:單CPU內，有多個計算核心**

**Many-core**
例如:GPU

比較:
multiprocessor system:電腦上有多個插槽、多個CPU
multi-core:一個CPU裡有多個核心
Many-core:一張卡，CPU卡里有多個core核心

**記憶體連接的方式
Memory Access Architecture :**
* Uniform memory access(UMA)
* non-uniform(NUMA)不均勻
* 

#### Distributed systems分散式系統:
又稱loosely coupled system﹐
透過網路(I/O阜或network)連結很多電腦
每個處理器都有其自己的記憶體***local memory***
puurpose目的:
1. rescoure sharing
2. load sharing 分擔工作量
3. relibility 可靠因為每一台電腦是獨立的，壞掉不會影響他人，可以備份在多台電腦
Architecture架構:
* **client-server**:
透過伺服器端控制
server becomes the *bottleneck* and single failure point服務器成為瓶頸和單一故障點
* **peer-to-peer:**

#### clustered system叢集:
把很多台電腦接起來

架構分類:
緊密:在一個電腦裡
松散:跨網路

依使用角度區分>>>>
1. **real-time os**
不是立刻做，確保每個行程在死線前完成doesn't mean speed,but ***keeping deadlines***
* Soft:盡量完成、依優先權priority分配
* Hard:必須完成、錯過會失敗a fundamental failure
2. multimedia system
3. Handheld/Embedded systems手持/嵌入式
Battery consumption
Slow processors

:::info
- [ ] 複習
:::

## CH1 Introduction
### What's an OS?
電腦系統的4個組成:
* Hardware
* OS:control & coordinate協調 the use of the hardware/resources
* Application:solve the somputing problems
* User

**os**
1. Resource allocator
2. Control program
3. **kernel**
permanent永恆的 software that **controls/abstracts hare\dware resources for user applications**

goals:
1. convience方便
2. efficient高效
是contradictory矛盾的
**System API are the only interface between user applications and hardware**

### Computer-System Organization
One or more CPUs, device controllers connect through **common bus** providing access to shared memory.
**concurrent execution**

[](https://ithelp.ithome.com.tw/m/articles/10224708)
* Each device controller is in charge of a particular device type
* Each device controller has a ==**local buffer**== 本地緩衝區
* **I/O is from the device to controller’s local buffer**
* CPU moves data from/to memory to/from local buffers in device controllers

### Interrupts I/O 系統中斷
* Busy/wait is very inefficient
CPU can’t do other work while testing device
Hard to do simultaneous I/O
* ==Interrupts== allow a device to **change the flow of control in the CPU**
Causes subroutine call to handle device
**I/O需要CPU時發出 ==**硬體中斷**== 通知OS，打斷CPU正執行的事將資源分給I/O**

1. 設備驅動 啟動 I/O
CPU 執行檢查指令之間的中斷
3. 啟動 I/O
4. 輸入就緒，輸出 完成，或錯誤 產生中斷信號
5. CPU接收中斷，將控制轉移到 中斷處理程序
6. 中斷處理程序 處理數據，從中斷返回
7. CPU恢復處理 中斷的任務

**interrupts:**
* Modern ==OS are interrupt driven==
* The occurrence of an event is signaled by an interrupt from either hardware or software.
* **Hardware** may trigger an interrupt at any time by sending a ==**signal**== to CPU
* Software may trigger an interrupt either by an **error** (division by zero or invalid memory access) or by a user request for an operating system **service** ==**(system call)**==
* **Software interrupt** also called ==**trap**==

#### 硬體中斷 (ex. switch case)

#### 軟體中斷

不管是軟體中斷或硬體中斷,interrupt都需要
1. 紀錄被打斷的位址address
2. interrupt vector指標 與 interrupts handler中斷處理程序
若兩個程序一直相互切換>>需要紀錄很多東西
3. 在處理另一個中斷時禁用傳入中斷以防止丟失中斷

### Storage-Device Hierarchy
1. 儲存的Hierarchy等級制度:
暫存器>快取>主記憶體>...>磁盤>磁帶
* speed
* cost
* volatility揮發性
會不會斷電就遺失資料?
2. ==**main memory**==**只有放在主記憶體裡CPU才可以直接使用**
3. Secondary storage:提供大型不易遺失的儲存裝置
4. RAM: Random Access Memory隨機存取存儲器
讀取任何位置的時間都相同

#### Disk磁碟
* Positioning time (random access time)=seek time (cylinder) + rotational latency (sector)
* 定位時間（隨機存取時間）=尋道時間（柱面）+旋轉延遲（扇區）

#### Caching
* Information in use ==**copied**== from **slower** to **faster** storage temporarily
* 使用的資料從較慢的儲存空間<font color="#f00">**複製**</font>到較快的 **(不是搬移)**
暫時性的，就算隨時砍掉都不會造成資料的遺失
**如何確保資料一致性?consistency**
* Faster storage (cache) checked first to determine if information is there.更快的快取，首先檢查資料是否存在
* If it is,information used directly from the catch.是，直接使用找到的快取
* If not, data copied to cahe and used there.否，一層層將資料複製到cahe並在那使用

* 所以有時候從系統上來看快取反而會變慢(要一層層找)，但因使用者習慣(人在用電腦)，快取還是比較適合使用的
ex.處理巨量資料，用完就丟不再用，就不用快取

### Hardware potection硬體保護
執行時如何保護資料不會亂跑，不是指中毒
不影響其他programs。
有些動作只有OS能做>>需要去區分OS
硬體不能更改 所以由硬體做一些基本的事，再用軟體控制

#### Dual mode雙模
* User mode
* Monitor(Kernerl mode):OS執行的instruction指令
**用中斷interrupt控制/切換兩種模式**
特權指令privileged instruction:只能在kernerl mode執行(目的:保護電腦)
使用者不能直接執行，需要較system call
#### I/O protection
因為I/O都是共用的，所以I/O全部都要保護
* All I/O instructions are privileged instructions
* memory也要保護>>避免指令被串改
#### memory potection
確保以下都正常:中斷的指標、中斷服務、確保資料可取得、避免被覆蓋>>>>位址要正確
硬體提供兩種暫存器:
* base register:開始的位址
* limit register:有多長
* 要修改register也是**特權指令**
如果超過位址(memory outside)就無效
#### cpu potection
避免 一隻程式霸佔CPU(infinite loop)
硬體支援:
* **Timer**:
* 由OS控制時間長短**也是特權指令**
* 實現time sharing

:::info
- [ ] 複習
何謂雙模模式? privileged instruction判斷標準?(會不會危害到電腦的運作)
CPU protection ?
memory protection ?
* 1.8: What is the purpose of interrupt? How does an interrupt differ from trap? Can traps be generated intentionally by a user program? If so, for what purpose?
* 1.10: some computer systems do not provide a privileged mode of operation in hardware. Is it possible to construct a secure operating system for these computer systems? Give arguments both that it is and that it is not possible.
* Why dual mode operation can protect system?

:::

==**[作業系統 Nachos 安裝](https://jeffprogrammer.wordpress.com/2016/10/31/%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-nachos-%E7%B0%A1%E4%BB%8B/)**== 點擊到教學網站>>>
[](https://www.youtube.com/watch?v=eLQU3zlpoRQ&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=14)

## CH2 OS strcuture
### OS services服務
* User interface
* Program Execution
* I/O operations
* File-system manipulation
* Communication
* Error detection
* Resource allocation
* Accounting
* Protection and security

#### User interface(人)
1. CLI: ==**shell**== command-lline interpreter(**CSHELL、BASH**)
2. GUI: icons圖標

#### Commmunication Models:
take place using either **message passing訊息傳遞** or **shared memory共用記憶體**
Msg Passing: A copy到os kernel 再傳到 B
shared memory: 要先用system code 創造一塊共用的空間 缺點:死結

---
### systwm call vs API

==**systwm call**==
* os interface to a running program
* software interrupt軟體中斷
* 通常是組合語言Assembly language

==**API**== :application program interface
方便使用者寫program
* Users mostly program against API instead of system call
* Commonly implemented by language libraries, e.g., **C Library**
* API可能1對0或多個system call
Math API functions, such as abs(), don’t need to involve system call

**為什麼要在system call上再加API?**
1. Portability
2. Efficiency:**Not all functions require OS services or involve kernel**
3. Simplicity

system call傳遞參數(Parameters)的方式:
1. 暫存器 Pass parameters in registers
2. 指標(傳位址)
3. 自訂stack

### system structure
人的目標:好用/好學/可靠/安全/(互動)快速
系統設計:好設計/好用/好維護/可靠/高效率
1. simple OS:only one or tow levels of code
un-safe,difficult to enhance
2. layered OS:
Less efficient, difficult to define layers
第n層的可以去call 0~-1層的，容易維護
3. microkernel OS微核心:核心只負責溝通(用message passing)和定義不同模組modulus/模組運行在user space
4. modular OS:模組都在kernal modules
Most modern OS implement **kernel modules**
Uses object-oriented approach
Each core component is separate
Each talks to the others over known interfaces
Each is **loadable** as needed within the kernel
[實作參考1](https://courses.linuxchix.org/kernel-hacking-2002.html) [參考2](https://en.wikibooks.org/wiki/The_Linux_Kernel/Modules)
5. virtual machine虛擬機:分成很多層
優點:protection/**compatibility兼容性**/research and development/cloud computing雲端計算
種類:
* full virtualization全虛擬機:
believe they are running on bare hardware but in fact are running inside a user-level application
Run in user mode as an application on top of OS

* para 平行/同時:
* java virtual machine:

:::info
- [ ] 複習

* What are the two communication models provided by OS?
* What is the relationship between system calls, API and C library?
* Why use API rather than system calls?
* What is the difference between the layer approach, the modular approach and microkernel?
* What are the advantages of using virtual machine?
:::

## CH3 Processes 行程
**目錄**
* **Process Concept** 甚麼是process
* **Process Scheduling** 排班/誰先誰後
* **Operations on Processes** 執行/如何creat process
* **Interprocess Communication** creat完成後process如何溝通

---
### 3.1 processing concept :
我寫程式progarm/programming:被動的，存在硬碟上
執行程式process/processing:主動的，**在記憶體裡執行** 的program

**process includes:**
1. 程式碼**code segment**
2. **data section** - global variables全域變數
3. ==**stack**== 堆疊、變動的- temporary local variables and functions
4. **heap** 變動的- dynamic allocated variables or classes
5. program counter,register content紀錄當前的活動、**狀態**
6. A set of associated **resources** (e.g. open file handlers)

補充[記憶體漏洞 Memory Leak](https://ithelp.ithome.com.tw/questions/10190491)

### thread執行緒:
* lightweight輕量級的 process
* basic unit of CPU utilization GPU使用的基本單位
* 是 OS 分配 CPU 時間的對象
* 可以共用空間
* ==同一個process裡的thread共用== :All **threads belonging to the same process share** ==code section== , ==data section== , and ==OS resources== (e.g. open files and signals)
* 有自己的register暫存器(執行的位址不同)But each thread has its own **thread ID, program counter, ==register set== , and a ==stack==**
data是share的 所以在寫[multi-thread-programing多執行緒](https://mropengate.blogspot.com/2015/01/operating-system-ch4-multithread.html)時就用全域變數來做溝通(只要用指標point不會被OS擋

### 3.2 process state狀態
* new
* ready:在ready Queue佇列裡排隊
* running
* waiting
* terminated

**由OS schedular行程排班來負責分配ready到running**

:::info
:::

在任何時刻，任何處理器上只有一個process在running
However, many processes may be ready or waiting.

### 3.3 process control block( ==PCB== )
行程控制區塊:紀錄剛剛的資訊(在哪個狀態);由OS產生
* ==process state== :running or waiting ..
* ==program counter== :目前執行的位址
* ==CPU registers==
* CPU scheduling information(e.g. priority)
* Memory-management information(e.g. base/limit register)
* I/O status information
* Accounting information

### 3.4 Context Switch
==把cpu上正在執行的process交換==
Kernel saves the state of the old process and loads the saved state for the new process
1. interrupt or system call
2. 把 被中斷的process的;P0 狀態存到PCB
3. reload 要插隊的process P1的狀態存入
4. 執行P1
* 交換的時間其實是浪費overhead，P1 or P2都在idle
* 不能不換，為了管理跟sharing，讓CPU可以share給每個process
* switch的時間depend on:
1. memory speed
2. number of register
3. **existence of special instructions** ex.a single instruction to save/load all registers
4. **hardware support**:==multiple sets of registers==

:::info
- [ ] 複習

1. What’s the definition of a process?
2. What’s the difference between process and thread?
3. What’s PCB? its contents?
* Process state
* Program counter
* CPU registers
4. The kinds of process state?
New, Ready, Running, Waiting, Terminated
5. What’s context switch?
:::

### 3.5 Process Scheduling
* ==**Multiprogramming**==: CPU runs process at all times to **maximize CPU utilization**提高cpu的使用率

* ==**Time sharing**==: switch CPU frequently such that **users** can **interact** with each program while it is running

* Processes will have to wait until the CPU is free and can be re-scheduled

Process Scheduling Queues:
* Processes migrate between the various queues (i.e. switch among states)
* Job queue (New State) – set of **all processes in the system**
* Ready queue (Ready State) – set of all processes residing in main memory, ==ready and waiting to execute==
* Device queue (Wait State)– set of processes ==waiting for an I/O device==

### 3.6 Schedulers
---
[[影片講解片段_再看一次](https://youtu.be/N9hCtVGF76M?t=402)]
virtual memory:將disk上的空間當作memory space使用>>>job swapping

==**long-term schedular**== :電腦memory裡面到底有幾個program/你new的程式到底能不能放進memory裡
* Control **degree of multiprogramming**
* 執行頻率較低Execute less frequently (e.g. invoked only when a process leaves the system or **once several minutes**)
* Select a **good mix of CPU-bound & I/O-bound** processes to increase system overall performance.讓CPU和IO之間盡量重合overlap
* UNIX/NT: no long-term scheduler
* Created process placed in memory for short-term scheduler
* Multiprogramming degree is bounded by hardware limitation (e.g., # of terminals) or on the self-adjusting nature of users
* **當記憶體夠大或有虛擬記憶體後 功能就減弱** >>>由medi-term schedular取代

==**short_term schedular**== :取決於timer或是使用者呼叫system call
* Execute quite frequently (e.g. once per 100ms)
* Must be efficient:
* if 10 ms for picking a job, 100 ms for such a pick>>> overhead = 10 / 110 = 9%
* ready queue排班的演算法要有效率，不能算太久

==**medium-term schedular**== :再disk和memory之間做切換 **swap in** or **swap out**，為了控制degree of muitiprograming
* free up memory 釋放記憶體
* 協調memory與I/O(可以選擇哪些要放到disk)
* Most modern OS doesn’t have medium-term scheduler because having sufficient physical memory or using virtual memory

---

### 3.7 Operations on Processes
**使用者如何去==creat process== 讓他們之間可以溝通**
peocess的識別證**pid**
看>>>[Operations on Processes](/_MpmJksPRMGqm0xwbXNAzA)

**Process Creation:**
* 資源歸屬
* 父子分享全部
* 分享部分 subset子集
* 不分享
* 執行順序
* 並行執行execute concurrently(由OS決定)
* 兒子先行(父被打斷)
* memory裡的位址空間
* 兒子複製老爸的
* 載其他的

**```fork()```**:用來建立 child process、產生兒子的PCB...
**```execlp()```**:把 child 原來的 memory content 做 reset，放新的 program 進去，載入特定 binary code 到 memory 中執行。

* **計算會fork()多少個process?**

:::info
- [ ] 複習

* What’s long-term scheduler? features?
* What’s short-term scheduler? features?
* What’s medium-term scheduler? features?
* What’s the different between duplicate address space and load program? Their commands?

:::

---

### 3.4 interprocess communication進程間通信
==讓process內部之間可以溝通==
IPC:
[here](https://youtu.be/VbZUSpJzJmo?t=112)