2007年4月27日 星期五

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;

}

}

2007年4月7日 星期六

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

依頻率排序