雜記

https://ithelp.ithome.com.tw/users/20112132/ironman/1884?page=1

1. 沒特別說 IO一律想成blocking IO
2. Big O c找夠大 n就從1
3. T(n)=T(n/3)+T(n^0.5)+n =>theta(n)
   (根號太小 直接忽略）
4. T(n)=2T(n/2)+n/log^2n => theta(n)
5. Qn=bipartite
6. Real-time需要Interrupt-driven
7. A file descriptor created in a user-level process may refer to a file or a network socket
8. DMA可以負責兩個memory-mapped裝置間的傳輸且不需要透過main memmory
9. Hazard detection unit要當作萬能的
10. AVL高度h至少需要Fh+2 -1個點 F0=0
11. Red black tree高度最高2log(n+1)
12. Lw sw 之間不一定有load use
13. 除非前rt 等於後rs
14. Set the timer of day value不是特權指令
15. Light-weight virtualization(docker) 1-100頁
    提供程式執行的環境
    所有container執行同一份kernel
    優點 效能更好 可以一次跑很多container 映像檔小 移轉性強 開發管理運行容易 所需成本低 可快速啟動大量container
    缺點 無法執行多個OS 較不安全 隔離性差 系統環境修改成本高
16. ISR determines the cause of the interrupt, performs the necessary processing, performs a state restore, and executes a return from interrupt instruction.
17. Implicit threading usually use many to many
18. Many to many 製作複雜
19. Win32 WaitForSingleObject()等待某事件發生
20. Many to many solaris 2
21. Java thread沒有自動共享Mem 用start()創 join合併
22. System call 有的OS的kernel也會呼叫
23. UNIX-like OS有的不用修改kernel也能增加system call
24. RR 平均等待時間通常很長
25. windows xp/2000 non-preemptive;NT preemptive
26. 死結四個條件相依
27. Cooperative scheduling= non-preemption
28. Memory Compression即使用一個free frame儲存其他幾個frame壓縮後的資訊，當它們被替換掉後存取發生page fault，可解壓縮回來
29. Buddy https://www.itread01.com/content/1545587642.html
    主因：kernel data大小是變動的怕內碎以及有的device會跟記憶體直接互動所以需要連續記憶體空間
    優點:可快速找到連續記憶體區塊
    缺點:內碎
30. Prefetching記憶體程度平行 同時減少MP MR
31. non-blocking cache增加頻寬與減小MP
32. multi-banked cache增加頻寬
33. Pretch分sequential跟stride
34. 因va與pa的page offset皆同=>使用page offset同時存取cache及TLB
35. Buffer使用原因

1. 匹配兩層記憶體之間速度差的問題
2. 設備之間有不同傳輸量大小，做為緩存
3. Copy Semantic。考慮write()，會先把user要寫入的資料copy到kernel buffer。避免還沒寫入user便已更改user端的內容。可用vmmap及copy-on-write來達到同樣效果並更有效率

36. Windows用Message passing實作I/O
37. Compiler產生Absolute code
38. 2 bit的動態預測狀態改變前必須錯兩次(課本)
39. misprediction can be caused by getting the branch history of wrong branch when indexing the branch history tabler
40. 經由PTLR來檢查page address是否合法，若不合法發出trap通知OS
41. virtual mem透過copy-on-write或vfork()加速process建立
42. File handle指向open file table中的file位置
    File pointer指向最後讀寫位置
43. Pure code(reentrant code)可被作業系統任意中斷且被其他process呼叫時不會出錯的程式碼。
44. LRU減少Conflict miss
45. 樹狀的file system可以允許不同使用者之間的互相存取檔案
46. Two-level用MFD記錄不同使用者，接者用UFD保存各使用者的檔案
47. Acyclic-Graph Directories允許共通目錄。透過link來實作(系統保存結構時會忽略)。或者透過直接複製兩個目錄實作。
48. Access control list與rwx衝突時，前面為準
49. Memory sharing可以透過對同一個檔案做讀寫或者page table指向同一個frame
50. mmap把file對應到process的address space。若沒有mmap，file一樣會memory map但對應到kernel address space
51. virtual memory Less I/O needed to load or swap programs into memory
52. 可不可逆與可不可對角沒有關係
53. Tree不可空 BT可 forest大於等於0顆樹
54. Hamilton圖不保證有Euler circuit(K33)反之也一樣
55. Simulations have shown that both first fit and best fit are more efficient than worst fit in terms of both time and storage utilization. Neither first fit nor best fit is clearly best in terms of storage utilization, but first fit is generally faster.
56. Extent用來解決連續性配置的的缺點(外碎及檔案擴充)。紀錄檔案的block位置數量及指向下一個extent的指標
57. Extent把block分成一個一個群組，每個群組是連續的block。連續性配置的時候先分配一個extent，如果檔案成長大小的話再分配給他一個extent。extent之間用link list連結
58. 把多個block組成一個cluster以減少pointer佔整個block的比例
59. Direct-mapped贏fully=>假設只有兩個block
    0 1 2 4 1 0 1 2 4 1
60. RB Tree孤兒顏色不改
61. 所有點Deg大於等於(n-1)/2則圖連通
62. Loser Tree root上面要在一個節點儲存最小值
63. Rotation time=Latency time
64. G與G bar不同時不連通
65. Write through搭配Write allocate時，若發生write miss， penalty只有計算block搬入cache，不需再計算寫穿的MP
66. Named Pipe=FIFO
67. 在SPECweb99，Throuput比response time重要，也就是在自己電腦response time重要於throughput
68. Huffman若最大值小於最小值兩倍，則與Fixed-length code有相同的表現
69. d-arr huffman若不滿d個兒子，從下一層找最大的來補，下一層不夠再找下下層，直到最下層的父點，然後補dummy node, weight是0，而dummy node可省略不畫
70. Transaction atomicity

Transaction:資料庫執行中的一個基本單位，內含對資料庫的多個操作
而Atomicity指的就是一個Transaction內的操作一次全做或全部不做

71. database使用indexed
72. Critical section software現在不適用因為compiler會重排指令
73. Monitor is typically suppored programming language
74. Semaphore is typically supported as system call
75. AVL刪除需要O(logn)的旋轉
76. Leftist tree root到最右邊的外部節點為S(root)，則內部節點數至少2^S(root)-1。因此S(root)<=log(n+1)
77. Second best mst:收集沒有被選到的邊到集合B，接著針對B的每一邊(u,v)，找出MST中u到v之最大邊的權重W，W-w(u,v)取最小
78. SSD因為沒有讀寫頭移動的部分 排班演算法對於SSD影響較小 因此使用簡單的FCFS就好
79. False Sharing:共享資料時，當兩個不相干變數位於同一個區塊，存取一個變數可能導致區塊資料的異動，進而影響另一個變數的值