發表文章

目前顯示的是 十月, 2007的文章

簡易用C語言求方程式的根

最近有不少人向我求救,原因不外乎是學校的報告、作業,而其中最令人覺得有趣的,就是關於數值方法的程式撰寫的問題。而講到用電腦處理數學運算,大多數人的直覺一定是使用 MATLAB 來實作其程式。是的,課堂上所教所講的就是 MATLAB,在處理各種數學問題和方程式,MATLAB 都有完整的函式指令和功能,只要熟悉,可以很輕易的能夠達成各種數學任務。不過最好笑的是,教授雖然教的是 MATLAB,但考的卻是 C 和 Fortran,要求學生的報告、作業也都是 C 和 Fortran,這讓一群學生都傻了眼,不知道該怎麼辦。

先暫且不管課本中是否附有 MATLAB 的程式碼,對於一群只上過幾門程式語言課的人,仍然無法輕易將程式轉用 C 或 Fortran 來寫。像是這樣一個用C語言求方程式的根的程式,就是許多人的問題:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>

#define F(x) sin(10*x)+cos(3*x)

double f(double x) {
return F(x);
}

int sign(double x) {
if (x<0)
return -1;
else if (x>0)
return 1;
else
return 0;
}

void incsearch(double xmin, double xmax, int ns)
{
int i,n;
double space,current,ans;

current = xmin;
space = (xmax - xmin) / (ns-1);

for (i=0;i<ns-1;i++) {
if (sign(f(current))!=sign(f(current+space))) {
printf("%.4f\t%.4f\n", current, current+space);
}
current += space;
}
}

int main(int argc, char *argv[])
{
int n…

OrzMicrokernel tasks.asm 建立新工作函式註解

因為每天花在 Orz Microkernel 上的時間不多,而且這次的程式片斷比較長,所以讓我多花了幾天的時間做整理,直到現在才大約有個較完整的註解。繼續依順續閱讀 main.asm 中可以看到,在工作初始化多工機制和工作狀態的資料結構之後,就開始連續載入並新增 6 個工作到我們的工作清單中,main.asm 呼叫 tasks.asm 裡的 CreateTask 函式來新增工作。

以下是程式碼和詳細註解:
;--------------------------------------------------------------------------------------
; 建立新的工作 CreateTask
;;;; 輸入值: EAX = 工作的開始位址, EBX = 工作所佔的記憶體大小, ECX = 工作的堆疊大小
;;;; EDX = 工作的資料大小, ESI = 工作名稱指標
;;;; 返回值:若進位旗標 CF=1 則表示建立新工作失敗,否則 EAX = 工作編號
;;;; 會影響到的暫存器:EAX, EBX, ECX, EDX, ESI, EDI, EBP

CreateTask:
mov [taskNamePtr], esi ; 設 taskNamePtr 為工作的名稱
mov [taskBegin], eax ; 設 taskBegin 為工作的開始位址
mov [copySize], ebx ; 設 copySize 為工作所佔的記憶體大小
add ebx, ecx ; EBX 加工作的堆疊大小
add ebx, edx ; EBX 加工作的資料大小
mov [taskSize], ebx ; taskSize = 所佔記憶體 + 堆疊大小 + 資料大小

mov ebx, [tasksCount] ; 設定 EBX 為目前工…

Gmail 輸人不輸陣,免費空間快速爆增

這幾天瑣事繁多,令我閒不得半刻,所以有空的時間最多只能上網看看信件、檢查有無回應文章。不過就在這兩天登入信箱的時候,我發現 Google 開始有非常大的動作,那就是空間爆增了!截至這篇文章為止,我的信箱可用空間已達 3.7 GB!

回憶過去我選擇了 Gmail 來當我的私人信箱,就是因為它在操作介面上設計簡單輕便、且空間大﹝在 Gmail 剛推出 2GB 時其他免費信箱還只有5MB、10MB﹞。可是到了今天這時候,Hotmail 已經開始擴充到 5GB 的免費空間,Yahoo 也不斷有擴大空間的改進,令 Gmail 當初的空間已經不夠看了!可想而知, Gmail 的大容量吸引力就這樣開始慢慢消退。

但是,這幾天發現,我的信箱容量開始以每日約 200 MB 的速度增加,從2.9GB、3.1GB、3.3GB一直到今天的3.7GB,似乎還有繼續快速往上發展的趨勢,真是期待它會增加到什麼樣的地步。看來 Gmail 輸人不輸陣,似乎打算跟其他家服務商拼了。 :)

OrzMicrokernel tasks.asm 初始化多工機制和工作狀態的資料結構

main.asm 在設定完顯示模式後,緊接著就是開始初始化多工機制。我們將配置一塊記憶體來存放所有工作的名稱、執行狀態﹝包括各種暫存器的內容﹞,在 Orz Microkernel 中,工作數量被限制為 64 個,它被定義在 define.asm 裡頭。

程式碼和詳細註解:
InitTasks:
mov ecx, MAX_TASKS ; 設 ECX 為最大工作數量﹝定義在 define.asm﹞
mov ebp, tasks ; 設定工作狀態記錄所在位址﹝定義在tables.asm﹞
xor eax, eax ; 將 EAX 歸零

InitTasks0:
mov [ebp + s_task.taskID], eax ; 初始化工作狀態記錄編號
add ebp, s_task.msize ; 移到下一個工作狀態記錄的開頭
loop InitTasks0 ; 重覆工作狀態記錄初始化 ecx 次
ret


從上面程式碼看到的 s_task,是工作狀態記錄的資料結構,它被定義在 task.asm 的開頭:
; 使用虛擬指令 RESB、RESD 宣告不含初值的資料結構 s_task
struc s_task
.taskID: resd 1 ; 工作編號 Dword(2 Bytes)
.state: resb 1 ; 工作狀態 Dword(1 Byte)
.newTick: resd 1 ; need for state=STATE_SLEEP

.queue: resd (MAX_TASKS + 1)
.qFirst: resd 1
.qLast: resd 1

.s_taskID: resd 1
.s_message: resd 1
.s_dataPtr: resd 1
.s_dataSize: resd 1

.ta…

OrzMicrokernel video.asm 切換顯示模式的註解

依照 Orz Microkernel 在 main.asm 的核心啟動流程來看,在轉換到保護模式並做了最基本的初始化之後,就會 call SetVideoMode 來切換顯示模式到 320x200。關於這部份,比較複雜的是牽涉到 BIOS 中斷,由於在保護模式之下無法使用 BIOS INT,所以特別額外在 realmode.asm 寫了在保護模式下處理此類中斷的呼叫函式﹝關於 realmode.asm 的註解日後補上﹞。

程式碼和詳細註解:
;------------------------------------------------------------------------------
; 文字模式﹝80x25,16色﹞:AL=0
; 圖形模式﹝320x200,256色﹞:AL=1

SetVideoMode:
and al, al
jnz SetVideoMode0 ; 若 AL 不為 0 則呼叫 SetVideoMode0

mov [rmode_ax], WORD 0x03 ; 文字模式
mov al, 0x10 ; 中斷 10H

; 在保護模式下舊有的中斷向量表已被 IDT 代替
; 導致 BIOS 中斷在保護模式下無法使用
; 故 BIOS 中斷得在真實模式執行
; 因此特別在 realmode.asm 中設計一個處理真實模式中斷的函式
jmp RmodeInt ; 呼叫在 realmode.asm 的 RmodeInt 處理中斷

SetVideoMode0:
dec al ; AL=AL-1
jnz SetVideoMode1 ; 若 AL 不為 0 則呼叫 SetVideoMode1 返回

mov [rmode_ax], WORD 0x13 ; 圖形模式
mov al, 0x10 ; 中斷 10H
jmp RmodeInt ; 呼叫在 realmode.asm 的 Rm…

OrzMicrokernel bit32.asm 進入保護模式後的核心初始化

OrzMicrokernel 在 bit16.asm 完成了轉換成保護模式的工作,緊接著會跳到 bit32.asm 初始化核心和設定硬體中斷周期。最重要的是,從跳轉到這檔案後,就可以開始使用 32 位元的各種延伸暫存器以及更大的記憶體定址,但前題是:我們得先將新的暫存器區段位址設定好,因為暫存器設定還是處於在真實模式時的狀態。

程式碼和詳細註解:
[BITS 32]
; Intel 處理器的設計是以 dword 為單位來存取記憶體,所以記憶體位址定為 4 的倍數。
align 4 ; 設定所有資料的起始位址都是 4 的倍數
Begin32c:
; 初始化暫存器區段
mov ax, kernel_data - _GDT ; 從 tables.asm 的 kernel_data 開始
mov ds, ax
mov es, ax
mov fs, ax
mov gs, ax
mov ss, ax
mov esp, 0x2FFFF ; 堆疊暫存器設在 2MB 記憶體後

call TestMemory ; 呼叫 mm.asm 的子程式測試記憶體

mov edi, memMap ; 初始化索引暫存器
; memMap 記憶體大小有0x20000=128KB
mov ecx, 0x100 / 32 ; 計數器設為 256/32=8
xor eax, eax ; 將 eax 歸零
dec eax
rep stosd ; 每次從 EAX 中複製 4 Bytes 到 EDI
; 複製 8 次

mov ecx, 0x20000 / 4 - (0x100 / 32) …

OrzMicrokernel bit16.asm 核心前置動作並轉換到保護模式的註解

bit16.asm 是 OrzMicrokernel 從真實模式轉換到保護模式的部份。保護模式是作業系統必要的運作環境,因為保護模式支援了 4GB 的實體記憶體定址、可擴充的記憶體分頁機制、多重任務機制、特權級等多工作業系統會用到的各種機制。

詳細程式碼和註解:
[BITS 16]
[ORG KERNEL_START]

Start:
; 初始化暫存器區段
mov ax, cs
mov ds, ax
mov es, ax
mov ss, ax ; 初始化堆疊區段
mov sp, 0x0000 ; 堆疊指標暫存器歸零

; 準備開始切換到保護模式
cli ; 禁用中斷以免干擾初始化
cld ; 設定字串處理時由低住址往高位址
call PrepareIRQs ; 呼叫 irqs.asm 的副程式以初始化 IRQ

; A20 位址線控制器:
; 早期 8086 的 CPU 只有 20 bits 的位址匯流排,只能定址到 1MB 的記憶體
; 因此,如果試圖存取超過 1MB 的記憶體,將會回到位址零重新定位循環下去
; 所以,要打開 A20 位址線,讓電腦可以定址大於 1MB 的記憶體
call A20En ; 呼叫 irqs.asm 的副程式
; 以打開 A20 位址線

lgdt [_GDT - KERNEL_START] ; 載入 GDT:_GDT 在 tables.asm
lidt [_IDTR - KERNEL_START] ; 載入 IDT:_IDTR 在 tables.asm

; 切換到保護模式
; 切換成保護模式的方法:將 CR0 的 PE 欄位(Bit0)設為 1
;
; 控制暫存器 CR0…

OrzMicrokernel boot.asm 啟動磁區定義和程式初始化註解

OrzMicrokernel 的 boot.asm 是針對 1.44 MB 磁碟片所設計的,採用的是 FAT12 ﹝注意不是 FAT16 或 FAT32﹞的檔案系統,所以,在啟動磁區的部份的定義上比較簡單且單純。另外,這次註解的內容主要是程式一開始的部份,包括初始化、在螢幕上顯示一段文字等。

程式碼與詳細註解:
Base:
jmp short Begin ; 從 Begin 執行
nop ; 空執行

; 啟動磁區格式
oem db 'OrzMicro' ; 廠商軟體名
bytesPerSector dw 0x0200 ; 設每磁區的大小為 512 Bytes
sectPerCluster db 0x02 ; 每磁叢的磁區數
resSectors dw 0x01 ; FAT 前的磁區數
; ﹝開機記錄所佔用的磁區數﹞
fatCopies db 0x02 ; FAT 表總數
rootEntCnt dw 0x0070 ; 根目錄的最大檔案數
totalSectors dw 0x05A0 ; 邏輯磁區總數
media db 0xF9 ; 磁碟種類
sectPerFat dw 0x0003 ; 每個 FAT 表的磁區數
sectPerTrack dw 0x0009 ; 每磁軌的磁區數
heads dw 0x0002 ; 磁頭數﹝面數﹞
hiddenSectors dd 0 ; 隱藏磁區數
sectorHuge dd 0 ; 保留 4 Bytes
drive db …

OrzMicrokernel boot.asm 磁碟內容參數的詳細註解

這是 OrzMicrokernel 裡 boot.asm 磁碟內容參數的部分,這部份比較直觀且不涉及硬體裝置的操作和定義,只要了解磁碟的資料配置結構,很容易就能了解其中的運作。

程式碼包括詳細註解:
;-----------------------------------------------
; 計算各項磁碟內容參數
;
; 計算磁區位置:
; 1. FAT表磁區
; 2. 根目錄磁區
; 3. 資料磁區
;
; 計算 FAT 檔案系統資訊:
; 1. FBD 所佔磁區數量
;-----------------------------------------------
;
; 磁碟資料結構:[開機記錄磁區][隱藏磁區][FAT表磁區][根目錄磁區][資料磁區]
; [FAT表磁區] 是由許多 FAT 表所構成
; [根目錄磁區] 是由許多 FBD 所構成
; FBD(檔案描述區塊):大小為 32Bytes
; 每個檔案都有自己的 FBD,記錄檔案名稱、建檔日期、檔案大小等資料

; 計算 FAT 的開始位置
; 方法:跳過隱藏磁區和開機磁區
; hiddenSectors = [高位元 2Bytes][低位元 2Bytes]
mov si,[hiddenSectors] ; 低位元給 SI
mov di,[hiddenSectors+2] ; 高位元給 DI
add si,[resSectors] ; 跳過隱藏磁區加開機記錄所佔用的磁區數
adc di,0 ; DI:SI = 第一個 FAT 表的開始位置
mov [fatStart],si ; 用 fatStart 保存 FAT 的開始位置
mov [fatStart+2],di

; 計算根目錄磁區的開始位置
; 方法:跳過 FAT 表磁區
; FAT 表的總數 x 每個表的磁區數 = 所有 FAT 表的磁區總數
mov al,[fatCopies] ; AL = FAT 表總數
xor ah,ah …

OrzMicrokernel 陪我度過颱風天的阿宅生活

最近幾次少數能以『強烈的颱風』身份影響並登陸台灣的,大概就屬這次的颱風了。還沒登陸,風就已經重擊了家裡的窗戶,呼呼砰砰聲搞得我醒著做事覺得煩、睡也睡不好。前兩天晚上去逛敦南誠品,在去的路上,風狂野的在短短一個街口,就把我的雨傘給吹成奇形怪狀﹝比翻過來還可怕﹞,後來回家時只好淋著雨一身濕答答的走回停車處。在被風玩弄之後,我就決定這兩天不出門了,弄得自己閒得發荒,一直在家當阿宅 Orz。

我突然想起前陣子 Jserv 寫的 OrzMicrokernel,一直沒能好好的找個時間去讀它,所以,藉著這次颱風過境,就好好品嘗一下了﹝笑﹞。一切果然如同大家所說, OrzMicrokernel 真的是簡潔有力,是一個作業系統設計的優良範例,它的設計非常直觀易懂;可是我也有聽到一群朋友,看得要死還是看不大懂 OrzMicrokernel 。搞半天,原來他們對組合語言並不是說非常熟悉,還有對磁碟 LBA、CHS、FAT12 等等這種格式定義很陌生!不過也難怪,大多人平時寫程式都太高階了,早就忘了電腦是怎麼動起來的。

尋思如果很多想了解的人,都卡在對組合語言的一點不熟悉和資料結構定義這種問題上,導致無法踏入 OrzMicrokernel 的話,那真的是太可惜了。所以,無聊到極點的我,就決定開始幫 OrzMicrokernel 逐行中文註解,希望從組合語言指令用法開始加註說明,還有說明重要的資料結構﹝註解寫起來比程式碼還多行,驚!﹞。為了說明的完全清晰正確,我還重新查資料驗證自己的觀念,生怕有一點遺漏。

以下是 boot.asm 讀取磁區的註解片段:

; DX:AX = LBA 磁區位置, ES:BX = 緩衝區位址
ReadSector:
; 磁區 CHS 表示法
; 磁碟和磁片的記錄方式『不是』一整面的磁區用完再換面儲存,而是以空心圓柱狀的方式。
; 因為磁片只有簡單兩面,以磁片為例:
; 正確的磁片資料記錄順序為:第零面第零軌、第一面第零軌、第零面第一軌、第一面第一軌...
; 每面的同一軌都用滿後才換下一個磁軌紀錄資料,形狀如同空心圓柱,故稱磁柱(cylinder)。
; 因此以磁片來說,第 0 面第 0 軌和第 1 面第 0 軌就是第 0 磁柱

; 磁區 LBA 表示法
; LBA 編號法是不考慮磁區的實體 CHS 上,純粹將所有磁區統一由 0, 1, 2...編號到最後一個磁區

; …

實作支援多處理器(SMP)操作的程式

其實多核心早已不是新技術,還記得多年前,多處理器架構(SMP)早就廣泛應用在伺服器的硬體上,只是要在頂級的硬體規格才看得到。當時,伺服器專用的 CPU 實在是貴得嚇死人,頂級的伺服器配備兩顆以上的 CPU 後,更是價格喊到天價,就如同今日的 CPU 有『多核心』加持一般,在價格上的氣勢也因此莫名的居高不下。但是,我們真的有用到多處理器﹝多核心﹞架構的好處嗎?就連掌控 CPU 運算的多數程式設計人員大概從不曾想過這個問題,更不用說一般無知的消費者了。

以下是一個指定 CPU 來處理運算的例子:

#include <stdio.h>
#include <stdlib.h>
#include <sched.h>

int main(void) {
cpu_set_t cmask;
unsigned long len = sizeof(cmask);
__CPU_ZERO(&cmask); /* 初始化 cmask */
__CPU_SET(0, &cmask); /* 指定第一個處理器 */

/* 設定自己由指定的處理器執行 */
if (!sched_setaffinity(0, len, &cmask)) {
printf("Could not set cpu affinity for current process.\n");
exit(1);
}

return 0;
}


關鍵的註解

我們使用 __CPU_SET() 指定處理器,你可以指定 0, 1, 2, 3... 等編號來決定使用哪一顆處理器。sched_setaffinity() 是用來將程序轉移到我們所指定的處理器執行,你可以設定程序編號(PID)來選擇要轉移的程序,或是設定 PID 為 0,也就是自己。

後記

指定 CPU 處理運算在實際應用面上,可以將需要大量運算的工作分散給所有的 CPU 同時處理,或是也可以,控制某些特定功能的程式盡量利用同一顆 CPU 的 Cache ,避免資料分散,以增加 Cache 存取的速度。

備註:本文所講的內容是架構在 Linux 2.6 版核心之上的系統。

台灣大哥大的3G就是比較大!

如果有人看過我前一陣子發表的『遠傳 3.5G 山頂洞人專用的大頻寬』,一定知道我把遠傳的大寬頻罵個臭頭,但是,我對3G服務並不死心,我不相信每家業者都跟遠傳一樣如此無恥的欺負消費者,用詐騙的方式取得用戶。所以,這次我在一些因緣際會之下,換了台灣大哥大的3G服務。

不可否認的,台灣大哥大的3G頻寬就是比較大!同樣在板橋江子翠地區,不管任何時候,台灣大哥大都能保持在每秒100KB以上的速度。比起遠傳的速度5、7KB,相差十幾倍不止。在此,我們先不考慮3G訊號覆蓋率,就寬頻大小來說,台灣大哥大比遠傳好太多太多了。

雖然我在這稱讚台灣大哥大的3G比較優質,但是,還是未達到他們號稱3.6Mb的一半,也就是每秒300KB到400KB的一半,在此還是有待加強的。而且,兩家業者比較起來,或許是因為台灣大哥大的3G用戶比較少,所以才有比較大的頻寬也說不定。也就是,求大家不要來搶我的頻寬,等到他們把頻寬備齊完整,你們再來用吧!到時候我一定會公告給大家知道,絕不會一人獨享!