數字系統與資料表示法

1、數字系統與資料表示法,電腦的基本單位,電腦，顧名思義，它必須是有電才有腦的，它是由許多電子電路所組合而成，它以1代表開，而以0代表關。 對於任一條電路，它只能有導電1或不導電0兩種狀況，這也構成了電腦的基本單位，我們稱它為位元(Bit)，而這種只有0或1兩種狀態的系統就叫二進位系統(binary system)。,電腦的基本單位,在日常生活中，我們習慣於使用十進位 (由0、1、2至9所組成，逢10就進位)。 舉例而言，若班上有52位同學，使用十進位只要二位數就夠了，因為十進位的二位數可代表0到99，共有100種狀況。 而在電腦中呢? 因為它使用二進位(由0至1所組成，逢2就進位)，故一位數只能

2、代表兩種狀況，二位數只能代表四種狀況，請看右表： 所以，班上有52位同學，若要用二進位來編座號，那至少得要有六位數才夠。,電腦的基本單位,現在請看看您的鍵盤，鍵盤上的AZ共有二十六個字元，小寫的az又有二十六個字元，09有十個字元，再加上特殊符號(! # % char name; int score5; student100,int a; int *p; a=10; P=,變數的範疇(scope),靜態範疇 依程式本身，變數的實際位置來決定。 動態範疇 依程式執行時，副程式的呼叫順序來決定。 副程式sub1並未定義 x 的值為10。 如果採用“靜態範疇”規則，印出的 x = ? 為什麼？ 如果

3、採用“動態範疇”規則，印出的 x = ? 為什麼？,PROGRAM main INTEGER x; PROCEDURE sub1 BEGIN PRINT x; END PROCEDURE sub2 INTEGER x; BEGIN x=20; CALL sub1; END BEGIN x=10; CALL sub2; END,副程式參數傳遞法,形式參數 副程式本身所定義的參數名稱及型態 實際參數 呼叫者(主程式)呼叫副程式時，所附上一些該有的參數。,void swap(int a, int b) int t; t=a; a=b; b=t; main ( ) int x=5, y=10; swa

4、p (x,y); Printf(“%d,%d”.x,y); ,形式參數,實際參數,副程式參數傳遞法,Call by Value (傳值) 僅將主程式實際參數的值，copy給副程式的形式參數，主程式實際參數的值不會改變，沒有side effect (副作用) 。 C語言只有call by value,5,x,10,y,5,a,10,b,void swap(int a, int b) int t; t=a; a=b; b=t; main ( ) int x=5, y=10; swap (x,y); Printf(“%d,%d”.x,y); ,5,t,/ 10,/ 5,副程式參數傳遞法,Call b

5、y Address (傳址) 又稱“Call by Reference” 將只程式實際參數的位址，傳給副程式的形式參數，主程式實際參數的值可能改變，有side effect (副作用) 。 C+採用Call by Address,5,x,1000,10,y,1500,1000,a,1500,b,/ 10,/ 5,位址,void swap(int a, int b) int t; t=a; a=b; b=t; main ( ) int x=5, y=10; swap (x,y); Printf(“%d,%d”.x,y); ,1000,t,1500 /,/ 1000,副程式參數傳遞法,Call b

6、y Name (傳名) 以實際參數的名稱取代形式參數(早期的做法)，有side effect(副作用)。,void swap(int a, int b) int t; t=a; a=b; b=t; main ( ) int x=5, y=10; swap (x,y); Printf(“%d,%d”.x,y); ,5,x,10,y,5,a,10,b,5,t,/ 10,/ 5,/ x,/ y,/ 10,/ 5,副程式參數傳遞法,Call by Value/Result 取代Call by Address，因為在分散式環境裡，主副程式的address 配置不同，所以不能用Call by Addres

7、s，有side effect (副作用)。,void swap(int a, int b) int t; t=a; a=b; b=t; main ( ) int x=5, y=10; swap (x,y); Printf(“%d,%d”.x,y); ,5,x,10,y,5,a,10,b,5,t,/ 10,/ 5,10 /,5 /,副程式參數傳遞法,Homework_8 請分別以下列參數傳遞法 call by value call by address call by name call by value/result 寫出右列程式之最後輸出結果。,program main(input，outp

8、ut)； procedure p(x，y，z)； begin y：=y1； z：=zx； end； begin a：=2； b：=3； p(a+b，a，a)； print a=，a； end,副程式參數傳遞法,請分別以下列參數傳遞法 call by value call by address call by name call by value/result 寫出右列程式之最後輸出結果。,main( ) int a5=2,4,6,8,10; int x=1; f(x,ax); print “x=“, x; print a0,a1,a2,a3,a4; void f(int i, int j )

9、i=3; j=100; ,作業系統簡介,作業系統(Operating System)的目的,方便的人機介面 命令列介面：Command line，如DOS 圖形化使用者介面：GUI (Graphic User Interface)，如Windows XP，Mac OS等 有效的管理資源 Memory：虛擬記憶體(virtual memory) Processor：程序排程(process scheduling) Device：死結 (dead lock) Information：檔案(file) Others：載入(loader)，鏈結(linker)，庫存程式(library)，公用程式(u

10、tility),計算機作業方式,Batch(批次)：將程式及資料事先準備好(一疊卡片，一個.bat檔)交給電腦一次完成。 適用於周期性，時效要求低的作業。如：聯考閱卷，稅務申報等。 Real Time(即時)：輸入資料後立即處理，並在一定時限內產生輸出。(Response time 時限) 用於Special-Purpose電腦系統，如飛機自動導航/駕駛系統，證卷交易系統。(事關人命，金錢交易),計算機作業方式,On-Line(線上作業) Off-Line(離線作業) I/O設備與主機有實體連線，能立即作I/O處理，為Real time的必要條件。 變化：分散式系統中，電腦透過網路，與系統取得

11、連線。 Time-Sharing(分時作業) Multiprogramming的一種，各程式分配一段時間輪流交替執行，為最普遍的執行方式(公平，簡單，效果不錯) Multiprogramming：電腦Memory內有2個以上互不相關的程式可同時被執行，CPU交替執行之，使得User產生電腦專屬執行某一程式的錯覺。,由OS控制,計算機作業方式,Multiprogramming(多工程式處理)-1970s 同時(currently)執行數個程式(以軟體方式)，各個程式感覺是同時執行。 Multiprocessing(多元處理)-1970s 同時(simultaneously)執行數個程式(以硬體方

12、式)，格個程式真正是同時執行。 Multitasking(多工處理)-1980s 電腦Memory內有2個以上屬於同一程式的工作(task)可被同時執行。 Task：執行一個特定功能的一段程序(副程式) Multithreading(多序執行)-1990s 如Java,Virtual Memory虛擬記憶體,優點 使User的程式不受實際Memory容量的限制。 Memory內部程式/資料的保護。 Memory內部資訊的共享(sharing)。 作法 Demand Page(分頁)：以Mem的使用為主，將程式/資料分成等量大小(頁)，沒有fragment(碎片)。 Demand Segment

13、(分段)：以程式的保護為主，根據程式性質，分成數個大小不同的區段(段)，有fragment (碎片)。,Virtual Memory虛擬記憶體,Page Fault 代換策略 FIFO (First In First Out) 先進先出，最直觀，效果差 LRU (Least Recently Used) 最近最久未用，合理 Optimal 最晚才會再用，最佳，理論上限 Random：實際上使用,CPU,Main Memory,Page frame,Page frame,Page frame,Page frame,Hard Disk,Page 1,Page 2,Page 3,Page 4,Pag

14、e 5,Page 6,Page 7,Page 8,Page 9,Page 10,某段程式或一段資料,例：CPU需要順序(頁參考順序)：1,3,6,9,10,4,7,Page 1,Page 3,Page 6,Page 9,？ Page Fault,Page Fault 代換策略實作,FIFO(先進先出) 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3,0,0,0,0,3,3,3,3,5,5,5,2,2,2,2,5,5,1,1,1,1,4,4,4,4,6,6,6,3,3,3,3,6,2,2,2,2,2,1,1,1,7,7,7,7,4,4,4

15、,共發生 page fault ()= 次,3,4,1,5,6,7,2,3,4,5,6,0,15,自我練習,FIFO(先進先出) 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4,共發生 page fault ()= 次,0,Page Fault 代換策略實作,LRU(最近最久未用) Least Recently Used 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3,0,共發生 page fault ()= 次,3,15,0,3,3,3,1,1,1,7,7,7,7,7,7,6,

16、0,1,1,1,4,4,4,5,5,5,2,2,2,4,4,4,1,2,2,2,2,2,2,6,6,6,3,3,3,5,5,2,4,1,5,6,7,2,3,4,5,6,0,自我練習,LRU(最近最久未用) Least Recently Used 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4,共發生 page fault ()= 次,Page Fault 代換策略實作,Optimal(取代最晚才會再用的) 效果最好理論上限，但不可行 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3

17、,0,共發生 page fault ()= 次,12,0,0,0,3,4,4,4,4,4,4,4,4,4,4,5,5,1,1,1,1,1,1,1,5,6,7,7,7,7,7,7,6,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,4,5,6,7,3,5,6,0,自我練習,Optimal(取代最晚才會再用的) 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4,共發生 page fault ()= 次,Process Management (程序管理),Process (程序) 一段執行中的程式碼(a program in e

18、xecution) Process 的 STD (State Transition Diagram) 狀態轉換圖,User1 submit Job1,User2 submit Job2,Usern submit Jobn,Job Queue,Ready,Ready Queue,RUN,WAIT,Time out,等I/O完成,I/O已完成,Memory,Disk,：Long-term scheduler (長程排程器),Complete,：Short-term scheduler (短程排程器),：Medium-term scheduler (中程排程器),Process Management

19、 (程序管理),Process Scheduler (程序排程器)的目標System Balance (系統平衡) 程序大致可分為 I/O bound：大多數時間在做I/O，如Word。 CPU bound：大多數時間在跑CPU，如TV game。 Scheduler(排程器)為使CPU，I/O同時忙碌，故以I/O bound process(程序)為優先選擇。,Process Management (程序管理),Process 的排程策略 Non-Preemptive(不可插隊式) FCFS (First Come First Serve)：先來先做 SJF (Shortest Job Fi

20、rst)：最短先做 Preemptive(可插隊式) RR (Round-Robin)：啄木鳥/Time-sharing，適用於一般電腦。 SRTF (Shortest Remaining Time First)：最短剩餘時間優先。 解釋名詞： Average Turnaround Time：平均迴轉時間 程序從進入ready queue後，到全部完成的平均時間。 Average Waiting Time：平均等待時間 程序從進入ready queue後，到全部完成的平均等待時間。,Process Scheduling 程序排程,Non-Preemptive (不可插隊式) FCFS 先來先做

21、 (First Come First Serve),p4 p3 P2 p1,3,0,5,7,10,14,19,23,Average Waiting Time,Average Turnaround Time,代表process已經進入ready queue中等待，但尚未執行,代表process進入CPU中開始執行,=(0+(10-3)+(14-5)+(19-7)/4=7#,=(10+(14-3)+(19-5)+(23-7)/4=12.75#,自我練習,Non-Preemptive (不可插隊式) FCFS 先來先做 (First Come First Serve),p4 p3 P2 p1,Ave

22、rage Waiting Time=？,Average Turnaround Time=？,Process Scheduling 程序排程,Non-Preemptive (不可插隊式) SJF 最短先做 (Shortest Job First),p4 p3 P2 p1,3,0,5,7,10,14,18,23,Average Waiting Time =(0+(10-3)+(18-5)+(14-7)/4=6.75#,Average Turnaround Time =(10+(14-3)+(23-5)+(18-7)/4=12.5#,自我練習,Non-Preemptive (不可插隊式) SJF 最

23、短先做 (Shortest Job First),p4 p3 P2 p1,Average Waiting Time=？,Average Turnaround Time=？,Process Scheduling 程序排程,Preemptive (可插隊式) SRTF 剩餘最短時間先做 (Shortest Remaining Time First),p4 p3 P2 p1,3,0,5,7,11,16,23,Average Waiting Time =(16-3)+0+(11-5)+0)/4=4.75#,Average Turnaround Time =(23-0)+(7-3)+(16-5)+(11

24、-7)/4=10.5#,自我練習,Preemptive (可插隊式) SRTF 剩餘最短時間先做 (Shortest Remaining Time First),p4 p3 P2 p1,Average Waiting Time=？,Average Turnaround Time=？,Process Scheduling 程序排程,Preemptive (可插隊式) RR 啄木鳥 (Round-robin),p4 p3 P2 p1,3,0,5,7,10,14,23,Average Waiting Time =(12+(1+4)+(3+6+4)+(5+4)/4=9.75#,Average Turn

25、around Time =(22+(12-3)+(23-5)+(20-7)/4=15.5#,Time slice(時間間隔)=2,2,4,6,8,12,18,22,20,16,自我練習,Preemptive (可插隊式) RR 啄木鳥 (Round-robin),p4 p3 P2 p1,Average Waiting Time=？,Average Turnaround Time=？,Device Management (設備管理),Device (設備)分為 Dedicated(專屬)：如printer, tape Shared(共用)：如Memory, Disk Race Condition

26、(競賽現象) 當O.S安排程式使用資源的次序不當所產生的錯誤現象。 (將專屬的Device當成共用的Device使用，就會產生Race Condition) 如：將一台printer當成共用Device，2個以上的程式同時要求列印時，會產生什麼狀況？ 解決之道： 程式中加入“要求printer”及“釋放”指令 對專屬Device做Mutual Exclusion(互相排斥)控制,Device Management (設備管理),Process 1,要求printer,要求tape,釋放tape,釋放printer,Process 2,要求tape,要求printer,釋放tape,釋放prin

27、ter,P1,P2,printer,tape,等,等,Dead lock (死結),Dead lock (死結),Dead lock 發生之四大必要條件(缺一不可) Mutual Exclusion (互斥) Hold scanf(“%d”, ,主程式,.Obj,0 1 2 3 ,S1 S2 call scanf mov x,ax,a,x,程式段,資料段,20000,20001,Logical/virtual address,Compiler,30001,.exe,0 1 2 3 ,S1 S2 call 20001 mov 35301,ax,a,x,程式段,資料段,20000,25101,35

28、101,Linker,scanf( ),20001,25100, 定位 鏈結,定位：決定程式各模組之位置關係 鏈結：解決程式跨段參考的問題,其他系統之管理,.exe,0 1 2 3 ,S1 S2 call 20001 mov 35301,ax,a,x,程式段,資料段,20000,25101,35101,scanf( ),20001,25100,Linker, 定位 鏈結,Loader, 重定位(改位址) 載入(copy),memory,100000 100001 100002 ,S1 S2 call 120001 mov 135301,ax,a,x,程式段,資料段,120000,125101,

29、135101,scanf( ),120001,125100,A.exe,B.exe,執行,Physical/real address,重定位：根據實際載入位址，調整指令或資料的位址 載入：載入程式,數位邏輯簡介,學習數位邏輯的目的,電腦硬體以0，1來運作，通常 01 Volts(伏特)視為邏輯值”0”。 35 Volts(伏特)視為邏輯值”1”。 13 Volts(伏特)視為不穩定狀態(轉換狀態) 電腦硬體由許多的邏輯電路組合而成。 以布林(Boolean)函數及相關的布林代數來代表邏輯電路的運作及功能。 常用邏輯閘的介紹 運用邏輯閘來實現布林函數的功能 如何簡化布林函數以降低所需邏輯閘，進而

30、降低製造成本。,布林函數,布林函數的組成 二元變數：A,B,C，其值只可能為 0，1。 常數： 0，1。 括號及等號：(, ), , , , , =。 邏輯運算符號：AND, OR, NOT。 AND 運算 以 XY 或 XY 或 XY表示 若 F = XY (F 等於 X AND Y) 時 當X和Y的值均為1時，F的值才等於1。,真值表,布林函數,OR 運算 以 X+Y 表示 若 F = X+Y (F 等於 X OR Y) 時 當X和Y的值只要有一個為1時，F就等於1。 NOT 運算 以 X 或 X 表示 若 F = X (F 等於 NOT X) 時 F的值與X的值相反。,真值表,真值表,布

31、林函數,例：試說明 F(X,Y,Z) = XY+YZ+XYZ When F 的值會等於 1？ 當 X的值=1 且 Y的值=1 ; or 當 Y的值=0 且 Z的值=1 ; or 當 X的值=0 且 Y的值=1 且 Z的值=0 上述三種情況皆不發生，F 的值就等於 0 可寫成 F = XY+YZ+XYZ,當 X的值=0 且 Y的值=0 ; or 當 Y的值=1 且 Z的值=0 ; or 當 X的值=1 且 Y的值=0 且 Z的值=1 上述只要有一種情況發生時，F 的值就等於 1 上述三種情況皆不發生，F 的值就等於 0,練習：試說明 F = XY+YZ+XYZ,布林函數,例：試寫出 F = XY

32、+YZ+XYZ 的真值表,1,1,1,1,1,0,0,0,練習：試寫出 F = XY+YZ+XYZ 的真值表,0,1,1,1,1,0,0,1,布林函數,若已知某布林函數之真值表如下，試寫出該布林函數。,F=XYZ,+XYZ,+XYZ,+XYZ,+XYZ,F 也可以描述如下：, 當 X=0, Y=0, Z=1 時 or, 當 X=1 時,上述 2 個情況之一發生時，F=1, F = XYZ + X,布林函數,練習：若已知某布林函數之真值表如下，試寫出該布林函數。,F=XYZ+XYZ+XYZ, F 也可以 = YZ + XYZ,心得： 某布林函數，與其對應的真值表一定唯一 某真值表，與之對應的布林

33、函數不是唯一,布林代數,恆等式 (重要) X + 0 = X X 1 = X X + 1 = 1 X 0 = 0 X + X = X X X = X X + X = 1 X X = 0 X = X,X + Y = Y + X X Y = Y X X + (Y + Z) = (X + Y) + Z X (Y Z) = (X Y) Z X (Y + Z) = X Y + X Z X + (Y Z) = (X + Y) (X + Z) X + Y = X Y X Y = X + Y,布林代數,例1. 試化簡 F = XYZ + XYZ +XZ,練習1. 試化簡 F = X + XY,解答： F =

34、X + XY = X(1 + Y) = X 1 = X#,解答： F = XYZ + XYZ + XZ = XY(Z + Z) + XZ = XY 1 + XZ = XY + XZ#,布林代數,例2. 試化簡 F = XY + XY,練習2. 試化簡 F = X + XY,解答： F = X + XY = (X + X)(X + Y) = 1 (X + Y) = X + Y#,解答： F = XY + XY = X(Y+Y) = X 1 = X#,布林函數之標準型態,積項之和 SOP (Sum Of Product) F = ABC+ABC+ABC+ABC = m(3,5,6,7) 和項之積

35、POS (Product Of Sum) F = (A+B+C)(A+B+C)(A+B+C)(A+B+C) = M(0,1,2,4),0,1,2,3,4,5,6,7,利用卡諾圖做布林函數的化簡,試化簡 F(X,Y) = XY + XY,0,1,2,3,F=m(1,3),0,1,2,3,由卡諾圖可知： 當Y=1時，不論X=0或1，F皆等於 1 F = Y,練習：試化簡 F(X,Y) = X + XY,F(X,Y)=m(2,3),0,1,2,3,當X=1時，不論Y=0或1，F皆等於1 F = X,利用卡諾圖做布林函數的化簡,試化簡 F(X,Y,Z) = m(1,3,5,6,7),0,1,2,3,由

36、卡諾圖可知： 當Z=1時，不論X=0或1， Y=0或1，F 皆等於 1 當X=1且Y=1時，不論Z=0或1，F皆等於1 F = Z +XY,練習：試化簡 F(X,Y,Z) = m(2,3,4,6,7),當Y=1時，不論X=0或1，Z=0或1，F皆等於1 當X=1且Z=0時，不論Y=0或1，F皆等於1 F = Y + XZ,YZ,4,5,6,7,0,1,2,3,YZ,4,5,6,7,利用卡諾圖做布林函數的化簡,試化簡 F(A,B,C,D) = m(0,2,5,7,8,10,13,15),0,1,由卡諾圖可知： 當B=1且D=1時，不論A=0或1，C=0或1，F皆等於 1 當B=0且D=0時，不論

37、A=0或1，C=0或1，F皆等於1 F = BD +BD,CD,3,2,4,5,7,6,8,9,11,10,15,14,12,13,利用卡諾圖做布林函數的化簡,試化簡 F(W,X,Y,Z) = WXYZ+WXY+WXZ+YZ,0,1,當X=1且Y=0時，不論W=0或1，Z=0或1，F皆等於1 當W=1且X=1時，不論Y=0或1，Z=0或1，F皆等於1 當Y=1且Z=0時，不論W=0或1，X=0或1，F皆等於1 F = XY +WX +YZ,YZ,3,2,4,5,7,6,8,9,11,10,15,14,12,13,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,輔助記憶體,磁碟的

38、構造,磁區(sector),磁軌(track),讀寫頭,磁柱(cylinder),磁碟之存取時間,磁碟之存取時間 access time= seek time + rotation time + transfer time,seek time：將讀寫頭移到資料所在的磁軌上方所需的時間 讀寫頭自最外圈移到最內圈所需時間的一半。 rotation time：資料所在磁區回轉至讀寫頭下方所需的時間 磁碟回轉一圈所需時間的一半。 transfer time：資料在磁碟與記憶體之間傳輸所需的時間 其中以 seek time 最為耗時！,磁碟之存取時間,例：有一磁碟機轉速為3600rpm，資料轉移(data trans