電腦江湖闖蕩記

一、基本概念
  一.OS 之定義
    OS 為使用者和硬體溝通的介面，並滿足：
    1. efficiency (有效率的管理資源)
    2. user friendly (友善的使用者介面)
  二.job 的種類
    1. CPU Bound
      需 CPU 之比例大於需 I/O 之比例。例：科學計算 
    2. I/O Bound
      需 I/O 之比例大於需 CPU 之比例。例：列印
    (note)CPU 要挑選 I/O Bound 的工作優先執行；I/O 設備要挑選 CPU Bound 工作優先執行。
  三.各種 system
    1. Batch(批次)
      1- 定義：將相同或類似的 job 集中一次讓 CPU 處理。
      2- 目標：為了提高 CPU 的效率。
      3- 缺點：不適合交談式的環境。例：提款機
    2. multiprogramming
      1- 定義：允許在 memory 中同時存在多個 process。
      2- 目標：為了提高 CPU 的效率。
      3- 方法：當某個 process 需等候 I/O 或等候某個事件發生，為了避免 CPU idle，CPU 選擇其他 process 來執行。
    3. time sharing
      1- 定義：為 multiprogramming 的一種，在選擇 process 時使用 round-robin，即每一個 process 只能用 CPU 一個 time slice，一但時間到了，就切換給其他 process。
      2- 優點：適合用在交談式和多使用者的環境。
  四.distributed system
    1. tightly-coupled
      1- 有很多 CPU
      2- 共用 memory、OS 和週邊設備
      3- CPU 採用 share memory
      4- 依 CPU 能力分兩種： 
        a. symmetric (CPU 能力相同)
        b. asymmertric (CPU 能力不同)
    2. loosely-coupled
      1- 每個 CPU 有自己的 OS、memory 和週邊設備
      2- 溝通用網路和 message passing 
      3- 分兩種：
        a.client-server：client 和 server 要求 service 
        b.peer to peer：在 network 上能力相同，可接受 service，也可提供 service。
  五.real time system
    1.特徵：在此系統中，對於完成 process 之 time 有嚴格限制。
    2.分兩種：
      1- soft：確保優先權高之 job 最先被完成。
      2- hard：在限時內必完成，否則視為失敗。


二、系統架構 
  一.處理 I/O 的形式
    當某個正在擁有 CPU 資源之 process p，要作 I/O，系統的處理方式：
    1.輪詢式(polling)
      cons：CPU 會花很多時間檢查 I/O，花較少時間在 process 上。
      此法適合慢速 I/O 設備。例：printer，keyboard，mouse。
    2.Interrupt I/O
      I/O 完成時發出 "I/O complete" 給 OS，以提示進行下一步動作。
    3.DMA (Direct Memory Access)
      1.DMA controler 負責 CPU 和 memory 間傳輸，不需 CPU 參與監督，CPU 使用率上升。
      2.適合高效率的 I/O device。例：disk
      3.利用 cycle stealing 技巧。
        在 CPU 一定不會 access memory 之 cycle，才作 memory 與 I/O 之間的傳輸。


三、Interrupt 探討
  一.Interrupt 分類
    1.Interal：CPU 本身執行到不合法的指令時發出。例：除以零。
    2.external：CPU 外之 device 發出。例：I/O complete。
    3.software：User Program 要 OS 提供服務時，才發出此種中斷。(systme call)
  二.Interrupt 與 Trap(含要求 service 和運算有誤)
    前者是由硬體發出，後者是由軟體發出。
  三.Interrupt 是以階層方式執行的。(priority hierarchy)


四.系統保護
  一.保護實施之前提：dual mode
  二.I/O 保護：避免 I/O device 被不當使用，將所有 I/O operation 設為特權指令。
  三.CPU 保護：避免 CPU 被 Process 無限期佔用。
    幫正在使用 CPU 的 Process 設定 timer 倒數，待時間到強制釋放 CPU。
  四.Memory 保護：
    避免 Process 使用不屬於自己的 memory 空間。使用 base reg 和 limit reg，若存取之 memory address：
    1.小於 base reg
    2.大於 base reg + limit reg
    則視為非法存取。
五.Virtual Mechine
  (待續) 

一、進制
  一.k→10 
  二.10→k 
  三.2^a→2^b
二、整數
  一.unsigned
  二.signed
    1.signed magnitude
    2. 1's 補數
    3. 2's 補數
三、float:IEEE 754
四、文字表示法
  一.文字 & 符號 
    1.ASCII
    2.EDCBIC
    3.Unicode
  二.數字編碼
五、圖形 bitmap


//================================================================================================================================================ 


因為電腦只能儲存 0 和 1，所以必須將各式各樣的資料 encode(編碼)以進行儲存。同時，將 0 和 1 的訊息 decode(解碼)回原本資料。
一、數字系統
  一.數字表示法
    一個 C 進制的數字 B，可將其表示為 B(c)。
  二.k 進制之數字
    若有一數字[a(n)a(n-1)a(n-2)...a(2)a(1)a(0)](k)，其中a(i)代表此數字之某一位數且其加權值是 k^i。
  三.常用進制：2,8,16
    二進位(binary)，八進位(octal)，十進位(decimal)，十六進位(hexadecimal)
  四.進制轉換
    1.k 進制轉十進制
      依定義轉換即可
    2.十進制轉 k 進制
      整數部份除 k 取餘數、小數部份乘 k 取整數
    3. 2^a 轉 2^b
      先用 a 個 bit 表示，在以每一組 b 個 bit 組合。
二、整數表示法
  所有正數的表示法均相同，有差別的僅在負數部份。
  一.unsigned
    用 n 個 bit 表示一整數，以 binary 的方始儲存。範圍：0～2^n-1
  二.signed magnitude
    方法：第一個位元儲存正負，後面則以一般二進位方式儲存 
    範圍：2^(n-1)-1 ～ -(2^(n-1)-1)
    優點：易讀複數部份的值
    缺點：減法需另外設計、有兩個零
  三. 1's complement 
    方法：將所有位元反向
    範圍：2^(n-1)-1 ～ -(2^(n-1)-1)
    優點：減法運算可以用加法實現
    缺點：有兩個零
    減法運算：（求 A-B） 
      a.將 B 取 1's 的補數，得 B'
      b.算出 A + B'
      c.若有 end-round-carry 則 ans = A + B'+ 1，否則 ans = A + B'
        end-round-carry : 最高位的加法運算是否有進位 
  四. 2's complement
    方法：將所有位元反向後在加 1
    範圍：2^(n-1)-1 ～ -2^(n-1)
    優點：減法運算可以用加法實現、只會有一個零 
    減法運算：（求 A-B） 
      a.將 B 取 2's 的補數，得 B'
      b.算出 A + B'
  (note)在做同號相加的運算時，需注意 Overflow
三、浮點數表示法
  一.IEEE 754 normalization
    一個實數在正規化後會符合以下條件
    1.將小數點移動 k 個 bit，使其變成 1.xxx (hidden-1)
    2.在乘上 2^k (往左移：k 取正，往右移：k 取負)
  二.excess-k 表示法 (超 k 表示法)
    在 excess-k 表示法下，用 k 來表示零，用 k+1 來表示 1，用 k-1 來表示 -1。在 32 位元下，通常在 8 位元下 k 取 127。
    用 excess-k 可以比較容易比較正負數的大小。
  三.IEEE 754
    0   ：sign，0 為正，1 為負。
    1~ 8：指數。使用 excess-127。
    9~31：值的區域。使用 hidden-1。
四、文字表示法
  一.ASCII：英文字母、符號、控制碼、表格。
  二.EBCDIC：大型電腦專用編碼(MainFrame)，萬國碼。
  三.Unicode：萬國碼，也可稱為 UTF-8。 
五、數字表示法
  一.BCD
    方法：將 0~9 以 binary 編碼（一般的 2 進位）。
  二.2421
    1.共 4 個 bit，分別代表 2,4,2,1。
    2. 0~4 的第一個 bit 是 0，5~9 的第一個 bit 是 1。
    3.其值為要編碼之數字值
      0：0000 , 1：0001 , 2：0010 , 3：0011 , 4：0100
      9：1111 , 8：1110 , 7：1101 , 6：1100 , 5：1011
    4.自互補式編碼（簡稱：自補碼）
  三.84-2-1
    1.共 4 個 bit，分別代表 8,4,-2,-1。
    2. 0~4 的第一個 bit 是 0，5~9 的第一個 bit 是 1。
    3.其值為要編碼之數字值
      0：0000 , 1：0111 , 2：0110 , 3：0101 , 4：0100
      9：1111 , 8：1000 , 7：1001 , 6：1010 , 5：1011
    4.自互補式編碼（簡稱：自補碼）
  四.excess-3
    1.自互補式編碼（簡稱：自補碼）
  五.gray code
    1.相鄰的編碼只差一個 bit
      0：0000 , 1：0001 , 2：0011 , 3：0010 , 4：0110
      5：0111 , 6：0101 , 7：0100 , 8：1100 , 9：1101
六、錯誤檢查碼與更正碼
  一.parity bit
    1.parity bit 分成 odd parity 和 even parity，使用 parity bit 的資料會在後面加上一個 parity bit，使得 string 中 1 的個數符合 odd 或 even。 
    2.若錯誤一個位元，則可發現錯誤；若錯誤兩個位元，可能會無法發現錯誤。
    3.可檢查出資料是否有誤，但無法進行更正。
  二.CRC (Cycle Redundant Check)
    1.作法：
      a.協調出 p 
      b.求出 r = m / p ( m 為欲傳之資料) 
      c.送出 m + r 
      d.算出 m / p 之餘數
      e.判斷是否為 r 
  三.Hamming Code
    1.Hamming Distance
      相同長之兩個 string 之對應位元的相異數量，即為 Hamming Distance。
    2.若兩個 code word 間之 Hamming Distance 至少差 d，則：
      a.若錯誤的 bit 數小於 d-1 個，則可發現有誤。
      b.若錯誤的 bit 數小於 (d-1)/2 個，則可更正。
七、圖形表示法
  一.結構
    由長乘寬個 pixel 所構成，一個 pixel 可表示 2^n 種 color
  (note)表現顏色的方式：
    1.RGB 色光三原色(紅色 Red,綠色 Green,藍色 Blue)
    2.CYMK 色彩三原色+黑色(青色 Cyan,粉紅色 Magenta,黃色 Yellow,黑色 Black)

重點樹狀圖(只列大重點)

一、范紐曼架構 & 五大單元
二、記憶單元
  一.記憶體種類
    1.主/輔
    2.揮發/非揮發
  二.單位計算
    1.Bit/Byte/KB/MB...
    2.記憶體大小
三、Bus
  一.address bus
  二.control bus
  三.data bus
四、CPU
  一.組成元件
  二.指令集
    1.RISC
    2.CISC
  三.指令週期

//================================================================================================================================================

重點整理

一、范紐曼架構 & 五大單元
  范紐曼架構有三大項規則：
  一.程式和資料均存在記憶體中（內儲式）
  二.程式碼是循序執行(sequential)
  三.電腦分成五大單元(單元間用bus溝通)
    1.Input Unit
    2.Memory Unit
    3.Control Unit
    4.Arithmltic & Logic Unit (ALU)
    5.Output Unit

二、記憶單元
  一.記憶體種類
    1.主/輔
      1-主記憶體可分為：
        a.RAM
          電容式，需反覆充電才可保留資料，在不混淆的情況下可叫 Main Memory。較 ROM 慢、耗電、便宜
        b.ROM
          正反器式，資料不需電力保存，在不混淆的情況下可叫 cache。較 RAM 快、省電、昂貴(每單位約為 RAM 的幾千倍)
      2-輔記憶體(Second Memory)：主要是 Disk
    2.揮發/非揮發
      當斷電時，資聊存在與否，消失者為揮發式，反之則為非揮發式
  二.單位計算
    1.基本記憶體單位：bit
    2.常用記憶體單位
      1- 1 byte = 2^3 bit
      2- 1 KB = 2^10 bytes
      3- 1 MB = 2^20 bytes
      4- 1 GB = 2^30 bytes
      5- 1 TB = 2^40 bytes
      6- 1 PB = 2^50 bytes
      7- 1 EB = 2^60 bytes
    (Note)在買記憶體或是硬碟時，記憶體在商店通常以1024為單位，但是硬碟會以1000為單位。
    3.可表示的資料量
      1-用 1 bit，可表示 2^1=2 種的值
      2-用 2 bit，可表示 2^2=4 種的值
      3-用 n bit，可表示 2^n 種的值
      4-若要表示 k 種值，至少需要 cell(log2(k)) 個 bit
    4.常用時間單位
      1-second
      2- 1 ms = 10^-3 sec
      3- 1 us = 10^-6 sec
      4- 1 ns = 10^-9 sec
      5- 1 ps = 10^-12 sec
  三.資料/指令需先載入記憶體中方可執行/運算
  四.Cache：用來增加系統效能，為一介於 CPU 及 Main Memory 之間的記憶體，其速度大於 CPU，小於 Main Memory，會儲存部份 Main Memory 的內容。
    當 CPU 需要資料時：
      1.先檢查 Cache 中是否有所需的資料，若有則跳步驟 2，若無則跳步驟 3
      2.從 Cache 中讀取資料到 CPU
      3.從 Main Memory 中讀取資料到 CPU，並且多讀一些資料放進 Cache
    因為范紐慢架構的循序式規則，所以在目前的指令執行完時，極有可能繼續執行下一個指令，故可以預先多讀一些資料放進 Cache
  五.Memory Hierarchy
    register-cache-main memory-disk-DVD/CD
      1.越左邊容量越小，反之越大 
      2.越左邊速度越快，反之越慢 
      3.越左邊價格越貴，反之越便宜 
  六.Disk
    1.結構
      arm 的前面有 head，arm 的數量與圓盤的面數相等，圓盤的每一面上有成同心圓狀的 track(磁軌)，每一個 track 均可分成同等份且同大小的 sector(磁區)
      (磁軌寬度內外不同，所以才會同大小)，不同盤子的同一層 track，叫做 cylinder(磁柱)
    2.容量計算：面數(= head 的數量) * 磁軌數(= cylinder 的數量) * 磁區數 * 單位磁區容量(= CPU 的 Word)
    3.存取時間計算(access time)
      disk access time 為下列三者之和 
        1-seek time
          把 arm 移動到指定 track 所需時間，因為此值為不定值，所以計算時採平均值(從內圈到外圈所需時間的一半)
        2-rotation time
          把 sector 轉到 head 下所需的時間，因為此值為不定值，所以計算時採平均值(從圓盤轉一圈所需時間的一半)
        3-transfer time 
          讀取資料所需的時間，讀取一個 sector 所需的時間為定值
      最耗時間的是 seek time，其次是 rotation time，最快的為 transfer time 

三、Bus
  一.在電腦中，Bus 分三種： 
    1.address bus
      傳送 addr 之資訊 
    2.control bus
      傳送控制訊息 
    3.data bus
      傳送資料，CPU 一次可讀取/寫入的資料量稱為 word，若 data bus 的寬度為 32 位元，則代表 1 word = 4 bytes 
      (Note)若在解題時 word 的資料量沒有特別指定，通常是以 1 byte 代表 
  二.運作原理
    若 CPU 要讀記憶體位置為 1000 的資料
      1.以 control bus 傳送 read 的訊息，並且同時以 addr bus 傳送 1000 
      2.Main Memory 的管理單元收到訊息之後，將 1000 位址的值以 data bus 回傳。 

四、CPU
  一.組成元件
    1.Control Unit
    2.ALU 算術運算單元
    3.Resgister
      其中，Resgister 可分為兩種：
        1-general purpose register
          一般用途。ex：組合語言的 AX、BX
        2-special purpose register
          其內的值對系統運作有特殊意義。
          ex：PC(Program Counter)：儲存下一個指令要執行的位址 
              IR(Instruction Register)：儲存目前要執行的指令
    CPU 可比喻成一個工地，Control Unit 是工頭，ALU 是工人，Resgister 則是倉庫。 
  二.指令集
    1.RISC
      僅提供必要之基本指令，必須由程式設計者自行組合運用。ex: IBM 的 Power PC
    2.CISC(Complex Instruction Set Computer)
      設計各種功能不同的指令，以方便程式設計者使用。ex: Intel 的 Pentium 
    3.比較
      1-RISC 的速度比 CISC 快 
      2-RISC 的指令長度比 CISC 短 
      3-RISC 的暫存器需求比 CISC 多 
      4-RISC 的定址模式比 CISC 少 
  三.指令週期
  四.運作模式
    CPU 在執行指令時：
      1.將指令讀進 IR 中
      2.把 PC 的值往下一個指令移動 
      3.把需要的資料放入 Register 中
      4.運算
  五.評估 CPU 效能的標準
    1.MIPS(Millian Instruction Per Second)：每秒幾百萬個指令數 
    2.MFLOPS(Millian Float Per Second)：每秒幾百萬個浮點數計算 
    3.MHz：clock 每秒振動幾百萬次 
  六.指令 
    1.目的：告訴 CPU 需做什麼事
    2.組成：
      1-operator
      2-operand
    3.格式：op-code(代表進行何種運算) + operand(代表運算對象) 
  七.機器週期(Machine cycle)
    1.Instruction Fetch(提取欲執行的指令存在IR)
    2.Decode(解碼指令的意義)
    3.Fetch Operand(提取所需 Operand )
    4.Execution(執行指令)
    5.Store(存回運算結果)