學習筆記：計算機組織與結構（2）

補數     r補數
                  rⁿ-N
            (r-1)補數
                  rⁿ-N-r^-m
數碼檢查
   漢明碼
   CRC
           多項式
    同位元
           奇同位
           偶同位
    定數
  



大(正負) vs. 小(正負)

MIPS to Machine
       
     RA = RB + RC
add $t0, $s0, $s1
slt $t0, $s0, $s1
     RA   RB   RC

    INS OP FUNC         

    add  0-  32 RB RC RA     0 Register

 /  sub  0-  34 RB RC RA     0 Register

R

 \  slt  0-  42 RB RC RA     0 Register 

    sll  0-   0  0 RB RA SHAMT Register

    jr   0-   8 31           0 Register

                ra

    lw  35      RB RA [ ADDR ] Base/Displacement

    sw  43      RB RA [ ADDR ] Base/Displacement

 /

I   addi 8      RB RA [ DATA ] Immediate
 \
    beq  4      RA RB [ADDR/4] PC relative

    bne  5      RA RB [ADDR/4] PC relative

 /

J   j    2      [   ADDR/4   ] Pseudo direct

 \  jal  3      [   ADDR/4   ] Pseudo direct

    INS OP FUNC

學習筆記：計算機組織與結構（1）

R-format
    Register addressing
I-format
    Base/Displacement addressing
    Immediate addressing
    PC relative addressing   
J-format
   Pseudo direct addressing

Register

 0    $zero

 1    $at

 2- 3 $v0-$v1

 4- 7 $a0-$a3

 8-15 $t0-$t7

16-23 $s0-$s7

24-25 $t8-$t9

26-27 $k0-$k1

28    $gp

29    $sp

30    $fp

31    $ra

Assembly language

add $t0, $s0, $s0

add $t0, $t0, $t0 # sll $t0, $s0, 2
add $t0, $t0, $s1
lw  $t1, 0($t0)

學習筆記：演算法（1）

演算法的定義，是在有限的時間內，
使用一步一步的程序來執行某項工作。

在評估演算法的執行時間時，
會掉入繁複的細節中，
因此發展了漸進式表示法，
讓我們可以描述最主要影響執行時間的主要因素，
而不必掉入「某執行時間為常數的程式，究竟需要多少基本運算」 這種細節，

「Big-O」表示法

f(n)≦cg(n) 通常讀作「f(n) is big-Oh of g(n)」

其意義是，某個n的函數的常數倍(c)，
「小於或等於」另一個函數，
並在n趨近於無窮大時(足夠大時)，漸近於該函數。

在big-O表示法中，我們不喜歡包含常數項或低次項，
雖然那也正確，但是我們都極力要求最簡式。

以下的比喻，可以用來說明漸進表示法的精神：
一個飢餓的遊客在鄉間道路上駕駛了很長時間的車 ，
碰巧遇到了一個剛從市場走回家的農夫，
這個駕駛問農夫還要多久可以買到東西吃，
農夫告訴他「不會超過十二個小時」。

這個答案並沒有錯，但是如果農夫回答「再開幾分鐘就到了」，
如此會更精確，也更有幫助。

big-O表示法中，已經含有「小於或等於」的概念，
因此「f(n)=O(g(n))」的講法雖然常見，卻不完全正確，
而應該用「f(n)是O(g(n))」來理解會更為合適。

學習筆記：作業系統（1）

作業系統的主要目的：

1. 作為使用者(user)與電腦溝通、易於使用的介面環境
2. 提供使用者程式(user-program)一個易於執行的環境
3. 適當地分配資源(resource)，期望達到公平有效的運用
4. 監督程序(process)的執行過程，避免非法或無意不當的使用所造成的危害

作業系統演進的關鍵概念：

自動安排工作順序(Automatic job sequencing)
常駐監督器(Resident monitor)
剛開始時控制權在監督器身上，接著堅督器將控制權交給應用程式，
待應用程式執行結束後，再將控制權交給下一個應用程式。

緩衝裝置(Buffer)

線外處理(Off-line operation)
用磁帶機取代讀卡機和列表機

線上同時週邊處理(Spooling)
Simultaneous Peripheral Operation On-line

作業系統的服務項目
執行程式
輸出輸入
檔案系統維護(File-system manipulation)
錯誤偵測

資源分配
記帳
保護措施