計算機組織

為了讓CPU存取指令或是資料能夠更加的快速
因此導入了記憶體階層的觀念 將常用到的資料放在快速存取的區域
Cache是個很好的例子,它具有以下的特性
1.Small Size (Smaller is faster)
2.Fast access(L1 cache ~10 ns)
3.More expensive(Static RAM)

There are some principles & trade-off for designing cache
1.What is the size of a block?
The bigger the size , the more transferring time , but make use of locality.

2.

Mid-term

頁替換演算法


假設說，因為最近忙於寫報告，需要用到一些參考資料，所以要到圖書館去借書
這時候問題來了，我要參考的書籍有10本，但是圖書館限制說學生總共只能借4本書，而且借書、還書每一次只能1本
所以有6本書我"暫時"沒辦法借到，等到日後要用再來借，這時候我會希望說想出一個辦法，能夠跑最少次圖書館（因為圖書館很遠），而把我要參考的書都借到 手，完成我的報告。根據這個作為出發點，可以想出幾個方法：

例如我需要用到的書單編號是（分頁要求的順序）：1、2、3、4、2、1、5、6、7、5、4、3

不管怎麼做，都有一個基本原則：先察看自己身上有沒有該參考書，沒有的話代表說要跑圖書館去借了（類似置換的動作）。

FIFO 先進先出：最簡單的方法

我的借書單（分頁表），一開始雙手空空，順序是 1、2、3、4、2、1、5、6、7、5、 4、3

位置	1	2	3	4	1	1	2	3	4	4	4	1
順序	1	2	3	4	2	1	5	6	7	5	4	3
格子(Frame)1	1	1	1	1	1	1	5	5	5	5	5	5
格子(Frame)2		2	2	2	2	2	2	6	6	6	6	6
格子(Frame)3			3	3	3	3	3	3	7	7	7	7
格子(Frame)4				4	4	4	4	4	4	4	4	3
總計	1	2	3	4	4	4	5	6	7	7	7	8
註解

也就是說，我要跑8次圖書館才能借齊所要用到書

以上廢話，可略
======================================================================================================================
Second Chance + FIFO Ver1 ： 最簡單的版本

原則：

1.當分頁被載入的時候，參考位元設成1， 表示多了一次機會，如果需求的分頁在分頁表中，參考位元也設為1
2.當要存取的分頁不在分頁表中，從 頭到尾掃瞄參考位元，遇 到1 設為0， 遇到0則替換調這一頁， 掃完了再從頭到尾掃一次
3.替換上來的那一頁，參考位元設為1

例子：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6

	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
分 頁 表	1	1	1	1	1	1	5	5	2	2	2	3	3	3	3	3	1	1	1	6
		2	2	2	2	2	2	6	6	6	6	6	6	6	6	6	6	6	3	3
			3	3	3	3	3	3	3	1	1	1	1	1	1	2	2	2	2	2
				4	4	4	4	4	4	4	4	4	7	7	7	7	7	7	7	7
參 考 位 元	1	1	1	1	1	1(0)	1	0	1	0	0	1	0	0	1	0	1	1	0	0
		1	1	1	1	1(0)	0	1	1	0	1	1	0	1	1	0	0	0	1	0
			1	1	1	1(0)	0	0	0	1	1	1	0	0	0	1	1	1	1	1
				1	1	1(0)	0	0	0	0	0	0	1	1	1	1	1	1	1	0
總 計	1	2	3	4	4	4	5	6	7	8	8	9	10	10	10	11	12	12	13	14
註							A	B	C

A.當要載入第5頁的時候，第5頁不在分頁表中，因為前面一欄的參考位元是1111(藍色部分)，掃瞄過一次之後就變成0000(刮號的部分)，
再重新掃瞄發現第一個0，就把它替換出去，接著把第5頁換進來，參考位元設為1，所以變成1000(紫色部分)

B.當要載入第6頁，第6頁不在分頁表中，前面的參考位元是1000(紫色部分)，掃瞄過一次，把第一個參考位元設成0，發現第二個參考位元為0，把它置 換出去，其他的參考位元不動，把第6頁換進來，參考位元設為1，所以變成0100(黃色部分)

C.當要載入第2頁，第2頁不在分頁表中，前面的參考位元是0100(黃色部分)，掃瞄過一次，第一個參考位元是0，把它置換出去，
其他的參考位元不動，把第2頁換進來，參考位元設為1，所以變成1100(橙色部分)

其他以此類推，所以總共會有14次分頁錯誤


Second Chance + FIFO Ver2 ：多了指標，13次分頁錯誤

原則上，比第一個版本多了一個指標，記錄上一次被替換掉的參考位元的位置
如果要求的分頁不在分頁表中，並不是從頭掃到尾，而是從指標所指定

原則：

1.當分頁被載入的時候，參考位元設成1， 表示多了一次機會
如果需求的分頁在分頁表中，參考位元也設為1

2.當要存取的分頁不在分頁表中，從指標所指定的位置開始掃瞄參考位元，遇 到1 設為0， 遇到0則替換調這一頁， 掃完了再從頭到尾掃一次

3.替換上來的那一頁，參考位元設為1

	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
分 頁 表	1	1	1	1	1	1	5	5	5	5	5	3	3	3	3	3	1	1	1	1
		2	2	2	2	2	2	6	6	6	6	6	7	7	7	7	7	7	3	3
			3	3	3	3	3	3	2	2	2	2	2	6	6	6	6	6	6	6
				4	4	4	4	4	4	1	1	1	1	1	1	2	2	2	2	2
指 標(1)	2	3	4	1	1	1	2	3	4	1	1	2	3	4	4	1	2	2	3	3
參 考 位 元	1	1	1	1	1	1(0)	1	1	1	1	1	1	1	1	1	1	1	1	1	1
		1	1	1	1	1(0)	0	1	1	1	1	0	1	1	1	1	0	0	1	1
			1	1	1	1(0)	0	0	1	1	1	0	0	1	1	1	0	0	0	1
				1	1	1(0)	0	0	0	1	1	0	0	0	0	1	0	1	1	1
總 計	1	2	3	4	4	4	5	6	7	8	8	9	10	10	10	11	12	12	13	13

指標指的是下一個要被替換的分頁位置，初始值為1


Second Chance + LRU 改良版：這個有點複雜，不要太深入研究，錯誤率也不是最少的XD

	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
分 頁 表	1	1	1	1	1	1	1	1	1	1	1	3	3	3	3	3	3	3	3	3
		2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	1	1	1	1
			3	3	3	3	5	5	5	5	5	5	5	6	6	6	6	6	6	6
				4	4	4	4	6	6	6	6	6	7	7	7	7	7	2	2	2
載 入 時 間	0	1	2	3	4	0	1	2	3	4	5	0	1	2	0	1	2	3	4	5
		0	1	2	0	1	2	3	0	1	2	3	4	5	6	0	0	1	2	3
			0	1	2	3	0	1	2	3	4	5	6	0	1	2	3	4	5	6
				0	1	2	3	0	1	2	3	4	0	1	2	3	4	0	1	2
參 考 位 元	1	1	1	1	1	1(0)	0	0	0	0	0	1	1	1	1	1	0	0	0	0
		1	1	1	1	1(0)	0	0	0	0	0	0	0	0	0	0	1	1	1	1
			1	1	1	1(0)	1	1	1	1	1	1	0	1	1	1	0	0	0	0
				1	1	1(0)	0	1	0	0	0	0	1	1	1	1	0	1	1	1
總 計	1	2	3	4	4	4	5	6	6	6	6	7	8	9	9	9	10	11	11	11

Memory

□ 何謂Belady Anomaly？

布雷第異常是由於頁替換演算法中採用FIFO(先進先出)的置換方式，導致實體記憶體雖然配給此行程的Frame數增加了，但是分頁錯誤的次數並沒有減少，反而增加的現象。

□ Demand Paging

需求分頁，其主要的精神是只有當行程需要某一頁的資料時才載入，好處是不用把整個行程載入到記憶體，可以節省記憶體空間，讓其他的行程可以使用。

□ Dynamic linking

動態連結，即先在一個程式所參考、利用到的程式庫副程式(libraries sub-routing)中先做一個記號(Stub)，此記號為一小段程式，指示如何去尋找該副程式，當執行到記號之處，此記號會被取代成副程式的記憶體位址，再去檢查副程式是否在記憶體，若不在才做載入的動作。

□ 何謂純程式碼(Pure Code)??

純程式碼又稱做可重進入程式碼(Reentrant Code)，這種程式碼在執行期間不能被其他的程序所修改，有利於需求分頁的記憶體管理方式，因為一旦純程式碼被載入到記憶體之後就固定住了，多個行程可以共用同樣的程式碼，而不需要每個行程都複製相同的程式碼。

□ 為何要使用TLB(Translation Look-aside Buffer)的硬體機制？

一般來說，當行程要存取資料的時候，會先到記憶體查詢分頁表，之後再從分頁表當中取得資料的實體記憶體位址，如此需要兩次的記憶體存取，速度較慢。

使用TLB可以加快存取的速度，因為它是由關連式高速記憶體組成。當行程要參照某個分頁時，會先到TLB查詢分頁記錄，若Hit à只需一次記憶體存取

若Miss à兩次記憶體存取，平均來說，會比一般兩次記憶體存取來的快。

□ 比較內部斷裂跟外部斷裂

內部斷裂：採用分頁法會有此現象，由於分頁的大小固定，若要配置給行程足夠的分頁數量，通常會有某一頁部份的空間沒有被完全的利用，分頁形成的內部斷裂所浪費的空間較小。

外部斷裂：由於行程的搬進搬出而造成記憶體的空間不連續，雖然斷裂的空間加起來的大小足夠容納別的行程，但是無法利用，這些空間就被浪費掉了。

當採取分段的時候，因為把行程以邏輯劃分成不同的功能區段，這些區段大小都不固定，所以分段形成的斷裂問題比較嚴重。

□ 在記憶體管理中何謂翻轉現象

翻轉現象即過度的頁替換現象，由於行程所擁有的Frame不夠，所以經常產生分頁錯誤，頻繁的進行I/O的動作，CPU排班程式以為CPU利用度不高，而載入更多的行程，更加重了分頁錯誤的情形。解決方式可以採用分頁錯誤頻率的方式，這個方法制訂了錯誤率的上下限，如果錯誤率達到上限，則多分配一個Frame給該行程，若錯誤率過低，則移走一個Frame。

【也可以採用工作集(Working Set)的方式解決，不過比較難寫】

□何謂分頁錯誤(Page fault)??舉出三種寫程式若不注意較容易發生分頁錯誤的情形

分頁錯誤是因為行程佔用的空間較大，無法整個載入到記憶體當中，因此被切割成許多分頁，OS通常只做部分的載入，因此，當一個行程需要用到的分頁不在實體記憶體當中，就造成了分頁錯誤，並引發OS的中斷去做額外的處理。

程式當中容易造成分頁錯誤的情況有

1. 使用GOTO指令

2. 過度使用指標

3. 如果電腦是row-major，但是迴圈以Column方式先進行寫入的話

如果這樣寫：

int array[100][100];

For (int j=0 ; j<100;j++){

For (int i=0;i<100;i++){

array[i][j] = i+j;

}

}

Introduction2

演算法的設計通常有一些策略

1.Recursion <==> Divide & Conqure 將一個很複雜的問題切割成許多Subset，一個一個去解決
之後將Subset的結果合併起來 (DS 中通常需要Stack來支援) 是屬於Top-down的方式

2.Dynamic Programming 屬於bottom-up的方式，先解決小問題，之後再考慮較大的問題
看看目前的最佳解是否會比前一次的最佳解還要好，如果有，則取代原先的解 (需要Queue & Table 來記錄整個流程)

3.Greedy Method 屬於bottom-up的方式，找出每個小問題的最佳解(Local)，再一步步往上做，之後得到的是整體的最佳解(Global)，一般來說會牽涉到Backtracking

ex:如何找出 Top 2 Biggest element?
宣告一個陣列，每兩個一組去做比較，贏的人往上走，類似贏家樹，走到最上面的那一個element is Maximal
往後退一個的就是第二大的元素

演算法設計完成通常都要被驗證是否正確 ==> 使用數學歸納法
之後分析演算法的時間複雜度：
1.Worst Case
2.Average Case
3.Amortized Analysis ==> 將比較不常用的Operation 跟其他的Operation 去做成本的分攤
ex: 如果有一資料結構提供下列運算
Inset an element cost O(1)
Search an element cost O(lgN)
Delete an element cost O(n)
因為Delete較不常使用，所以跟Insert動作去分攤成本

Introduction

演算法簡單來說是一解決問題的方法和步驟，依據Howritz的說法，基本上具有下列的特性：

1.Input 需要有資料的輸入才能計算
2.Definition 每一個步驟要有明確的定義
3.Effective 每一步驟要簡單，要讓人看的懂
4.Efficient 設計的每一步驟盡量要有效率
5.Output 整個流程跑完至少會有一個輸出

一般的說法是，程式 ＝ 演算法 ＋ 資料結構

演算法是應用底層資料結構所設計的物件，並不會太Care底層實作的部分
所以就個人的觀點，演算法是將資料結構抽象化的學科，專注在問題的描述，如何變成電腦可以解決的問題，並且將問題轉成電腦可以理解的語言，之後再用特定的程式語言實作出來，這是演算法關注的焦點。

演算法探討的問題包羅萬象，就電腦的領域來說，大致上可以區分成幾類

1.Search & Sort 是演算法所處理基本的問題
如何將資料做好排序，做好整理，讓人在找資料的時候可以節省很多時間
Sort 的方法有很多種，不同的場合要套用不同的方法

2.Graph Algorithm 圖論的部分，應用也是非常的廣泛
例如找出Shortest Path ， Minimal Spanning Tree，著色問題，
尋找Minimal Cut，很多問題在這一類目前找不出有效率的方法解決

ex: Hami. Cycle ==> Travler 問題 ， 從某一個城市開始出發，試著找出經過所有其他的城市一次，並且回到原出發點，這種被視為NP-Complete的問題，因為要找出存在這樣的一條路徑很困難

ex: 圖形著色問題，相鄰的兩個國家不能同顏色，試問能不能用4種顏色解決這樣的問題 ==> 目前只能一個一個Try

3.String Match 字串比對

MySQL 簡介

MySQL -- 一套關聯式資料庫的管理系統
在windows 模式下可下載 appserv 安裝即可使用
指令以分號作為結束符號

1.常用指令:

登入MySQL
>mysql -u username -p -h hostname

啟動服務
>net start mysql

關閉服務
>net stop mysql

如果啟動服務發生錯誤，可能是my.ini的參數沒有設定好
記得修改正確後放在 windows 目錄下


2.MySQL指令

(1).建立一組帳號密碼
>GRANT ALL ON sampdb.* TO 'sampadm'@'localhost' IDENTIFIED BY 'secret';

sampdb 代表資料庫名稱
sampadm 代表帳號名稱
localhost 代表本機,如果是遠端的資料庫可以輸入主機位址
secret 代表密碼

>\q 即退出

(2)顯示資料

顯示資料庫 >show databases;
選用資料庫 >use databaseName;
顯示資料表 >show tables;

顯示資料表的欄位資訊 >describe tableName;
可以簡寫成 >desc tableName;

查詢資料 >select * from tableName where 條件;

(3)建立資料庫
create database databaseName;

選用資料庫
use databaseName;

建立資料表
create table tableName
(
name varchar(20) not null
);

啟動MYSQL服務系統發生 1067 錯誤的解決方法

解決方法一：
1、檢查你的mysql目錄有沒有給系統的system用戶權限。
2、刪除你的%windows%/my.ini。 （以前裝過mysql，但沒刪除乾淨）
3、檢查你的c：/mysql.cnf文件是否配置正確。

解決方法二：
看C:\Windows（或C:\Winnt）下是否存在一個文件my.ini

如沒有，在系統目錄下（如c:\windows）建一個my.ini 內容如下
[mysqld]
basedir=D:\MYOA3\mysql\
datadir=D:\MYOA\data\
default-character-set=gbk
set-variable=max_connections=1000

集合論

進入離散數學的首要章節，探討了集合和元素之間的關係
集合與集合之間--包含 與 相等 關係
證明相等的方法，只要證明互相包含即可，也就是任給一個元素屬於某個集合A
必屬於某個集合B，另一個方向回來也成立

之後介紹了集合的屬性與運算
屬性包括了 交換性 結合性 分配性
運算包括了 聯集 交集 補集 差集 對稱差
可用文氏圖幫助了解

重要的定理~DeMorgan's Law --> prove : by defination

再來是計算個數與power set
power set is a collection of set such that sets are subsets of AxB