###### tags: `operating system` `thu` `note`

# OS-Final (PIC) Memory

## Chapter 9. Main Memory
### 9.1.1 Basic Hardware
#### 圖為硬體使用兩暫存器來防止CPU送出不存在的位置。
---

### 9.1.2 Address Binding
#### 一般的使用者程式會經過下面的流程
- Compiler: 在這裡，Compiler會將變數跟可分配的記憶體位置做連結。
- Linker or Loader: 他們會將可分配的記憶體位置跟實體的記憶體位置做連結。
---
### 9.2 Continguous Memory Allocation
#### 有三種分配策略:
- First fit
- Best fit
- Worst fit
#### 雖然First fit可能最快，但可能會導致記憶體空間的Fragmentation(破碎化)

---
### 9.3 Paging
#### 下圖為Paging table的示意圖。
#### MMU將logical address轉換為physical address的步驟如下:
- 使用Page number $p$定位到page table
- 取出page table上的frame number $f$
- 將logical address中的page number $p$取代為physical address中的frame number $f$。

---
logical memory (虛假的)
* ex:
1. 6: 01 | 10 (01: f6, 10: 3rd byte)
2. 13: 11 | 01 (11: f2, 01: 2nd byte)
3. 10: 10 | 10 (10: f1, 10: 3rd byte)
* 前面看page table, 後面看logical memory(+1)
* 右邊0, 4, 8 ...可以視為f0, f1, f2...

TLB (translation look-aside buffer)
Hit ratio = 在 page number 找到 interset 的百分比
ex:
Suffer a 20-percent slowdown in average memory-access
time (from 10 to 12 nanoseconds). For a 99-percent hit ratio:

effective access time 
    = 0.99 * 10 + 0.01 * 20
    = 10.1 nanoseconds

* vaild-invaild bit: 觸發ISR

* 按順序填填看

### 9-4 Page Table



IA-32（Intel Architecture 32-bit），也被稱為x86或IA-32，是由Intel開發的處理器架構。它是原始x86架構的32位擴展，被廣泛應用於個人電腦和伺服器。IA-32架構定義了指令集、記憶體管理和其他關鍵功能，使軟體能夠在相容的處理器上運行。


#### IA-32 Paging
IA-32 Paging 使用了兩層或三層的頁表結構，而不是單層的頁表。這樣可以將虛擬地址空間劃分為更小的區域，減少每個頁表的大小和記憶體佔用

Page Address Extension（PAE）技術通過將虛擬地址擴展到36位元，從而可以對應到最多64GB的物理記憶體空間, 並且也將頁目錄（Page Directory）和頁表（Page Table）中的地址欄位擴展為64位元


## Chapter 10. Virtual Memory
#### Page Replacement Algorithm
- https://www.scaler.com/topics/operating-system/page-replacement-algorithm/
- FIFO: First In First Out
換掉一開始的值
- FILO: First In Last Out(stack)
FIFO的相反
- Optimal Page Replacement
往後看，將長期用不到的page給交換出去
- LRU: Least Recently Used
往前看，以最近不常使用的page交換掉，用過去推測未來。

**Enhanced Second-Chance Algorithm**
先把1改成0 $\rightarrow$ 繞一圈回來第一個1就會選他

- LFU: Least Frequently Used
- MFU: Most Frequently Used

#### 而重複發生Page Fault我們就稱這個系統為**Thrashing**

CPU utilization:
1. 整個程式進入記憶體
2. 只有一部分進入paging，要一直interrupt

將記憶體分為一個個固定大小的區塊，稱為slab。每個slab可以容納一定數量的特定大小的物件。當需要分配物件時，系統會從相應大小的slab中分配一個空間，當物件不再需要時，將其釋放回slab中。
在分配物件時，不需要動態地分配和釋放記憶體，而是從已經預分配好的slab中進行分配，且每個slab的大小是固定的，所以可以有效地利用記憶體空間，減少碎片化。


***貼圖上來加點描述很難嗎? 貼頁碼有甚麼用( $\downarrow$ )***

## Chapter 11. Mass-Storage Structure
### 11.1.1 Hard Disk Drives
#### 圖為傳統硬碟的架構及部件名稱圖

### 11.2.2 SCAN Scheduling
照時間服務

邊走邊服務


#### C-SCAN Scheduling
先撞一邊後馬上在撞另一邊做 **單向** 服務


## Chapter 12. I/O Systems
### 12.2.3 Interrupts
#### 圖為CPU執行I/O request的流程圖。

#### 圖為CPU透過DMA(Direct Memory Access)進行I/O作業的流程

#### 圖為同步及非同步I/O的流程。
- 同步：直接等到I/O完成
- 非同步：先做別的事，等I/O完成再繼續資料的處理。

#### 圖為透過system call存取I/O的流程

#### 圖為UNIX I/O kernel 結構
左邊是檔案，右邊是網路
(per-process open-file table 可以對到PCB的list of open files)

#### 圖為一個I/O request的一生。

## OS File System PPT

**上圖可對應至課本3.1.3 figure 3.3 PCB 中的 list of open files**
### An entry of Active
* File table
1. access right
1. process count
1. R/W pointer
1. i-node table entry
* i- node table
* reference count
* device address
* owner ID
* group ID
* last user R/W

### System call
* open()
1. 最多20 file，超過return -1
2. file name 是否在 i-node table
* 有: 讀
* 沒有: return -1
3. 檢查權限
* 沒有: return -1
4. 分配 A-i table & copy data (AITE)
5. 分配 A-F table & copy data (AFTE)
7. 分配 U-Ofile table in PCB (UOE)
8. 連結AITE-AFTE-UOE
* write()
1. 根據fd(system call)access AFTE
2. 檢查權限
* 拒絕: return -1
3. 從適當 AFTE 的 write pointer 寫入資料
* read()
1. 根據fd(system call)access AFTE
2. 檢查權限
* 拒絕: return -1
3. 讀取 user buffer read pointer 的資料

* create()
1. 分配一個當前的空目錄
2. 填入資料
3. 寫入到 disk
4. system call open()
* close()
1. follow fd()去 access 適當 AFTE from user's U-Ofile
2. process count == 0
* 斷開 AFTE & AITE
* if (reference == 0)
* 把 AITE 放回i- node table in disk

(如果!= 0 就算了)