Computer Architecture and Operating System

Tree Directory

每個子目錄都可以有自己的子目錄並以此成為一樹狀結構，不允許共享

General Graph

每個目錄都可以指向另一目錄或檔案，可以共享，可以有cycle reference

Acyclic Graph

所有目錄都可以指向另一目錄或檔案，可以共享，需要追蹤reference count

Belady's Anomaly

More page->More page fault, occur in FIFO

Local and Global Replacement in Page

Local : Only swap with its own pages
Gobal : Can swap out other process's page(one thrashing might cause more thrashin)

RAID-0

No redundant, only speed up

RAID-1

Mirror for one disk

RAID-3

Bit-Interleaved Parity, need 4 disk

RAID-5

Block-Interleaved Parity, can cover 1 disk failure, the parity is distributed to other disks

RAID-6

Just like RAID-5 but can tolerant 2 disk failure(P+Q/Double Parity)

RAID-1+0 (RAID-10)

Use RAID-1 first then RAID-0, can also toralent 1 disk failure for each mirror set

Range for a n bits 2's complement number

-(2^{n-1})-(2^{n-1}-1)

BC

ABCD

BC

User和Kernel Thread不會共用哪些東西

Stack/PC/Register

A : Clock is not control signal

B : Data and Instruction Memory
C : Multi-Cycle can reuse hardware
D : Only 1 cycle pipeline need it.

Upon cache misses, to better utilize available hardware resources, CPU usually switches to execute other ready and waiting jobs.

False, cache miss penatly很小不會產生context switch

B 執行減法是二補數 所以最後要再加1 因此CarryIn=1

IEEE754 Denormalized number

mantissa全為0

IEEE754 Normalized Number

mantissa不全為1或0

Spin-Lock

A lock implemented by while loop, aka busy waiting

Processor Affinity

留在同一processor上 以獲得該processor的cache benefit，和load-balance相斥

Both reference bit and modify bit, if being 1, are closed to 0 on a circular round of the page replacement algorithm, as a way to give the second chance.

False, second chance algorithm will reset only reference bit

mmap()

在虛擬記憶體和檔案之間建立一個映射，發生page fault時才會載入

A dynamically loaded kernel module will not be unloaded automatically by the kernel unless explicitly requested

False,閒置過久就會unload

ll(\text{load and linked}) and sc(\text{store conditional})

ll會在處理器中使用一位元監測該記憶體位置，而sc會根據從ll到sc使用間該記憶體位置是否有被修改，如果有則會寫入失敗

AC

True, 但實際為Copy on Write,要等到父或子process改動其data時才會複製

Anonymous Memory為沒有對應檔案的資料，如程式動態分配的記憶體(Heap)，而storage-backed file有對應的檔案，因為可隨時重新讀取，所以除非該page是dirty的，不然不需要swap-back => True

False，page fault由CPU或Memory Management Unit(MMU)發起，非user process

A. True

B. 在WINDOWS下是必須的，但在UNIX不是

C. True

D. 只有使用者會使用到的需要，其他如swap-out space不用

Addressing Modes in MIPS

Register/Direct/Base/PC-Relative/Pseudo-Direct

False, jump可以跳轉到的位置為該PC所在的block內所有位置，和相對位置無關

MIPS

\frac{ClockRate}{CPI*10^{6}}

A fully-associative cache doesn't have conflict miss

True,要有index才會有conflict

IEEE754 Single Precision

1 for sign
8 for mantissa

23 for fraction

D

A
C:在硬體上虛擬層，純軟體

D:要透過Host OS執行的虛擬軟體

B
C:每個執行緒可以複製一份變數為自己所有

B
stack algorithm為一種類型其中包含optimal/LRU

The effectiveness of demand paging is proportional to the page fault rate

True，demand paging的有效存取時間為(1-p)*MA+p*PFR

Difference between Deadlock Prevention/Avoidance

Prevention破壞四個條件
Avoidance如Banker's Algorithm

I. User-Level is faster
II. True
III. True

IV. OS can’t see the User-Level Thread. True
(A)

Pipeline Efficiency =

\frac{Speed\ Up}{Stages}

Para-Virtualization

一種虛擬化技術，其Guest OS知道自己運行在虛擬環境下，透過Hypercall來向Master OS進行System Call，可以減少模擬硬體的性能開銷

Increase Associativity ?

Decrease Conflict
Increase Hit time

Modern OS use ? kernel mapping

1-1，So only has SCS

BGP?

Broad-Gate-Protocol 

ARP?

Address Resolution Protocol

A

Reentrant Lock

Recursive Lock，允許process重複獲得key並維護一counter紀錄key數，避免process在遞迴呼叫時鎖死自己

Fine-grained multithreading

每個clock都會更換可執行的thread來隱藏低延遲的stall

Coarse-grained multithreading

只有在遇到long stall(如IO)才會轉換

Ordinary Pipe

由pipe()建立，只允許單向溝通，需要有父子關係

Named Pipe

由mkfifo()建立並和一般檔案一樣存放在檔案系統中，可雙向溝通，只要知道他所在的位置即可使用

Difference between Interrupt and Exception

Excp來自處理器內部如IO，Int(Trap)來自外部如Page fault

Special case for 1 resource Banker’s Algorithm

an <= b+n, when all process has a-1 resource, the system must ensure that the last 1 resource can be retained.

Convoy Effect

執行時間短的process被時間長的process block，出現在FCFS

vfork()

執行完fork()後立刻執行exec()

Mechanism and Policy

Mechanism為如何做
Policy為做什麼
分開的話可以給予使用者更大的彈性操作而不用更改底層運行邏輯

Priority Inversion

A high priority process is waiting for resources held by low priority process

Log-File System

一種利於write的檔案系統，每次update時只會append到原資料的後面並不覆寫，同時將其位置寫至metadata中以讀取，原本的資料會由Garbage Collection回收

Static/Dynamic Linking

Static將整個程式load進memory中(可能重複)
Dynamic有一stub檢查是否已經有其他程式load過該library了

Booth’s Algorithm

乘數向右移，01加/10減

PCB

1.Process State

2.PC

3.Register

4.CPU Scheduling Information
5.Memory Management Information
6.Accounting Information
7.I/O Status