# 研究所 計算機組織
## ==disk access time==




## ==disk free space mgt==
### ==bit vector==

### ==link list==
### ==grouping==

### ==counting==


## ==File allocation method==

### ==contigous allocation==

### ==linked allocation==

### ==FAT==

### ==index allocation==

### ==i node(FCB)==


## ==disk scheduling algorithm==
### ==fcfs==


### ==sstf==



### ==scan==



### ==c scan==


### ==look==


### ==c look==


## ==stripping==

## ==提升可靠度==
### ==mirror==

### ==parity check==


## ==RAID==
### ==RAID 0==
:::info
只有block stripping
:::

### ==RAID 1==
:::info
就是 mirror
:::

### ==RAID 2==
:::info
就是 mirror 少一個 disk
:::
### ==RAID 3==
:::info
1. bit stripping
2. parity check
:::

### ==RAID 4==
:::info
1. block stripping
2. parity check
:::

### ==RAID 5==
:::info
1. block stripping
2. parity check
3. parity check block 分散儲存
:::

### ==RAID 6==
:::info
1. 可防止多部disk死掉，仍可恢復
:::

### ==RAID 1+0 優於 0+1==


## ==formatting==


## ==raw io==


## ==bootstrap loader==

## ==bad sector處理==

### ==mark bad sector==


### ==spare sector==



### ==sector slipping==


## ==swap space mgt==


## ==file open file close==
:::info
1. physical directory 在 Disk
2. open file table 在 kernel memory
:::
### ==open file==


### ==file close==


## ==unix semantic、session semantic、immutable semantic==
:::info
1. unix semantic : 不管任何時間點內容一致
2. session semantic : 存取不限制 、 內容不一致
3. immutable semantic : read only
:::

## ==file protection==



## ==working set==

## ==AMAT、EMAT==




## ==RISC、CISC比較==

## ==Belady anomaly==
:::info
FIFO分業替換有
:::

## ==pipeline、single cycle、multi cycle效能比較==



## ==1 bit adder==

## ==1 bit ALU==



:::info
* ***virtural memory 用 write back*** 不用 write through
* 用write back ***read miss will produce write***

* RISC allow designer to ***increase register set***
* RISC 較適合 pipeline
:::
## ==乘法==
## ==BOOTH乘法==

## ==Guard round==



## ==ULP==


## ==傳統乘法==

## ==硬體友善乘法==


## ==動態分支預測錯誤次數==


## ==control hazard解決方法==

## ==軟體解決control hazard==
:::info
插Nop
:::

:::info
把branch的比較往前挪，但daata hazard會變嚴重
1. 在原本的mem stage => 3個Nop
2. 往前到exe stage => 2個Nop
3. 往前到id stage => 1個Nop

:::

## ==beq 前面是 lw停兩個clock==


## 硬體解決
:::info

:::

## ==全猜不跳，猜錯損失一指令==

## ==static branch prediction==


## ==static branch prediction==

## ==dynamic branch prediction==




## ==branch target buffer 、branch prediction buffer、branch histary table==




## ==data path==

### ==簡化記法==


### ==IF==
:::info
instruction mem 和 data mem分開
:::

### ==R type==

### ==lw==


### ==sw==


### ==beq==


### ==R type與mem reference==

### ==brench + R type + mem reference==


### ==+MUX==


### ==ALU op控制ALU control 、ALU control控制ALU==



### ==各種instruction要花多少時間==


### ==控制信號==




### ==PLA==


## ==single cycle multi cycle clock cycle time 比較==






## ==各種指令必經的路徑==


## ==struatual hazard==

## ==hazard 解決方法==



## ==load used data hazard==


## ==有data hazard CPI算法==


## ==RAW、WAW、WAR資料相依性==
:::info
不用管兩個指令離多遠
:::



## ==效能==


## ==R-type、I-type、J-type==
:::danger
1. R-type : slt 、 **jr** 、 sll
2. I-type : lw 、 sw 、 sll
3. J-type : j 、 jal
:::


## ==branch和jump可跳的範圍==


## ==multiprogramming、multitasking、degree of multiprogramming==
:::danger
multiprogramming :

1. 如果用不到CPU就給別人用
2. 提高CPU利用率
3. 讓CPU盡量忙碌

multitasking :

1. multiprogramming的延伸
2. 加上在***多個process間經常切換***

degree of multiprogramming :

1. mem 中 process 的數量
:::

## ==long term、short term、mid term scheduler==
:::danger
* med term會將低多工度
* med term會在mem不夠時swap out、mem夠時在swap in

:::

## ==process記憶體結構==

## ==k級管線可提速k倍==

## ==kernal thread的數量與idle關係==

# ==incresase ILP==


## ==increase pipeline depth==


## ==multiple issue==

## ==static multiple issue、dynamic multiple issue==

## ==各種提升ILP的方法==


## ==speculation==

## ==loop unrolling==

## ==dynamic scheduling==



## ==data consistent==
:::info
要透過write through write back解決
:::

### ==refrence bit是甚麼==
:::danger
refrence bit 用於 second chance algorithm
set by hardware
:::

## ==SRAM、DRAM==


## ==邏輯左移、算術左移(右移)差別==


:::info
注意:算術左移錯了
算術左移會和邏輯左移一樣

:::
## ==Segmentation faults==

## ==elapsed time==



## ==不同型態指令集==








## ==754例外==


## ==最大最小非正規數==
:::danger
**不能用正規畫的攻勢算**
:::



## ==guard round sticky ULP==

## ==Big-Endian 與 Little-Endian==


## ==從公式計算的 Block 編號從位址分割得出的索引不一樣==



## ==pooling interrupt DMA==

## ==IO瓶頸==





## ==安德定理==

## ==MIPS==



## ==waiting time 、turnaround time 、respone time==


## ==Convoy effect==
:::danger
FIFO會有
:::

## ==CPU scheduling==




## ==cpu ulitization==


## ==ASMP SMP==


## ==load balancing==

## ==soft affinity 、 hard affinity==
:::danger
1. soft affinity: 不一定不會移轉到其他CPU
2. hard affinity: 一定不會移轉到其他CPU 例如:LINUX
:::

## ==cpu scheduler種類==


## ==process communication的兩種方式==


## ==split cache 、 combine cache比較==







## ==各種快取改變對miss rate的影響==



## ==時間 空間區域性==



## ==符號數表示==
:::danger

2's compliment 沒有 -0
:::


## ==address binding==
:::danger
虛擬記憶體位置對應到實體位置
:::


## ==dynamic loading 、dynamic linking==




## ==pageing 用於 address binding==


:::danger
TLB用於address binding
:::

## ==AMAT==
:::danger
用在快取的對應
:::



## ==EMAT==
:::danger
用在將虛擬位置對應到實體位置
:::



## ==page table 與 TLB ==

## ==階層式page==

## ==page 與 TLB 用於虛擬記憶體執行過程==

## ==IPT 反轉分業表==
:::danger
1. 會無法共用記憶體或分業
2. 增加轉址時間(要search)
3. 系統中只會有一個反轉分業表
4. 每個process有自己的分業表
:::





## ==segment==


## ==EMAT in VM==


## 分業替換
### ==addition refrence bit algorithm==
:::danger
加了addition refrence bit
:::


### ==second chance algorithm==
:::danger
加了refrence bit
:::


### ==NRU : enhance chance algorithm==
:::danger
加了refrence bit 、modify bit
:::


## ==copy on write==
:::danger
一開始parent 和 child公用
有修改時再把有影響的改到新的frame

* fork有
* vfork沒有
:::

## ==fragmentation 和 segmentation 不同==
:::danger
* fragmentation 碎裂
* segmentation 分段
:::

## ==deadlock 必要條件==


## ==處理deadlock==
:::danger
假裝死結永不發生也是一種方法
:::
### ==deadlock prevention==
#### ==deadlock prevention 破 circular waiting==



#### ==deadlock prevention 破 hold and wait==


### ==deadlock avoidence==

### ==safe state==
:::danger
unsafe不一定是deadlock
:::


### ==deadlock detection==
:::danger
每次要求都會同意
定期用banker檢查是否有死結
如果有就回復
:::

## ==最多能有多少個process一起，不會產生deadlock==

## ==critical section solution==
:::danger
software :
1. peterson's solution
2. bakery's solution
3. dekker's solution
4.
hardware :
1. test_and_set()
2. swap()
3. compare_and_swap()
**三個功能都相同
都不滿足bounded waiting**
:::


## ==IPC message passing==

## ==pipe==




## ==blocking nonblocking message passing==





## ==thread table==


## ==thread共用 page table、TLB==