塔尖上功德

1-1-1 電腦系統的形成

電腦是甚麼? 電腦=軟體+硬體

硬體看得到摸得著, 軟體是甚麼?

電腦與家電: 1. 硬體是電腦實際執行工作的實體,如何控制硬體? 2. 一般家電的控制方式:利用開關、電路、面板,例如電燈、吹風機、洗衣機,功能固定,無法擴充. 3. 家電和電腦的比較:電腦功能的多樣性,取決於軟體的種類vs.家電簡便易操作.

電腦的運作與控制: 1. 軟體命令硬體工作,軟體也就是程式,因為有軟體,所以才能讓用途一般化. 2. 軟體的功能:接收人類的命令,將指令傳達給電腦完成工作,擔任人與電腦間的橋梁. 3.軟體分為系統軟體和應用軟體.

1-1-2 程式的執行

電腦的核心元件: 1. 中央處理器,CPU:電腦的大腦,會運算與控制周邊硬體. 2. 主記憶體: CPU要處理的資料、要執行的程式,都要存放在這裡. 3. 硬碟: 大空間的儲存體,可以儲存大量的程式和資料.

程式執行的程序: 1. CPU執行程式,處理資料:程式和資料要先放到主記憶體裡. 2.CPU執行機器語言:不同的CPU可執行的指令不相同,所以機器語言是和硬體相依的. 3. 機器語言是01組合而成的指令:機器語言不方便人們使用,人們直接撰寫機器語言嗎?

組合語言: 設計人們較容易使用的語言來解決機器語言的問題→組合語言; 組合語言如何翻譯成機器語言? →組譯器

我們知道，CPU 只負責計算,本身不具備智慧。你輸入一條指令(instruction),它就執行一次,然後停下來,等待下一條指令。這些指令都是二進位制的,稱為操作碼(opcode),比如加法指令就是00000011。編譯器的作用,就是將高階語言寫好的程式,翻譯成一條條操作碼。

對於人類來說,二進位制程式是不可讀的,根本看不出來機器幹了什麼。為了解決可讀性的問題,以及偶爾的編輯需求,就誕生了組合語言。要把這些文字指令翻譯成二進位制,這個步驟就稱為assembling,完成這個步驟的程式就叫做assembler。它處理的文字,自然就叫做aseembly code。標準化以後,稱為assembly language,縮寫為asm,中文譯為組合語言。組合語言,英文名為「Assembly Language」。是一種與硬體有著密切關係的低階語言,並且根據CPU(中央處理器)或單晶片所使用之指令集的不同,組合語言的語法也不相同。

1-2-1 組譯器與巨集處理器

組譯器: 1. 組譯器翻譯組合語言為機器語言:組譯器通常也與機器相依,組譯器如何產生的? 2. 組合語言與機器語言的面貌: 組合語言使用助憶碼

簡短的字串稱作輔助記憶碼(Mnemonics),或簡稱易記碼、助憶碼，為英文單字的前面幾個字母或縮寫。例如：Add代表「加」、Sub代表「減」、Inc代表「累加」、Mov代表「移動」。由於CPU只認得機器碼,因此組合語言所撰寫的程式依然需要經由組譯器(Assembler)來轉譯為機器碼,這部分在稍後會做介紹。組合語言和機器語言一樣,是直接對CPU的暫存器(Register)進行操作,依然屬於低階語言,具機器依存性。

組譯器的使用: 1. 撰寫組合語言程式 2. 利用組譯器將程式翻譯成目的碼 3. 透過連結程式進行連結產生可執行檔 4. 執行: 利用作業系統,載入器將可執行檔載入執行

組譯器用來將組合語言使用的原始檔(.asm)翻譯成含有機器碼的二進制目的碼(Object Code)。

組合語言(Assembly)→組譯程式(Assembler)→機器碼的目的程式(Object)

巨集處理器: 1. 組合語言是低階的程式語言 2. 使用巨集可使組合語言的撰寫更為容易 3. 甚麼是巨集? 將一段程式碼定義成巨集,可以讓程式可讀性提高,巨集可使用參數,巨集可重複使用.

1-2-2 載入器與連結器

載入器: 1. 目的程式:由組譯器編譯出來的可執行程式,內容包含指令與資料. 2. 載入器的工作:分配程式在記憶體中的位置,結合兩個或多個目的程式並提供相互參考資訊,將目的程式重定址,實際將程式載入記憶體中以待執行

連結器用來將一個或多個目的碼檔案連結函式庫為一個可執行檔案。

1-2-3 作業系統

作業系統的角色:

作業系統功能:1. 人與電腦溝通的橋樑 2. 電腦開機後第一個執行的軟體 3. 負責管理電腦中的各項硬體資源 4. 負責把人類對電腦指派的工作一一交付執行,回報結果. 5. 呼叫與啟動應用軟體與工具.

常見的作業系統: 1. Windows作業系統→Windows 95,98, me, 2000, XP, Vista... 2. UNIX類作業系統→Solaris, HP UX, FreeBSD... →Linux: RedHat, Debian, Fedora, Slackware, Suse... 3. MacOS作業系統

補充:

高階語言是目前最常見的程式語言,一行高階語言的敘述式就相當於低階語言的多行指令,比低階語言更容易撰寫,語法也跟人類所使用的英文接近。相較於受硬體束縛頗大的低階語言,高階語言不會受到不同CPU的影響,具有非機器依存(Machine-independent)的特性,可以在不同機器間移植,但不一定能在不同操作系統(Operating System)上編譯或執行。使用高階語言所撰寫的程式,必須透過直譯器(Interpreter)或是編譯器(Compiler)轉換成電腦看得懂的機器碼(Machine Code),CPU才能執行。

編譯程式(Compiler)：將高階語言的原始程式轉為機器碼的目的程式。不同的高階語言有不同的翻譯器。

原始程式→翻譯程式→機器碼的目的程式

直譯程式(Interpreter)：也稱為解釋程式，主要將高階語言的原始程式轉為機器碼，並且執行。而直譯即是將原始程式一條一條翻譯後執行，每翻譯一條就執行一條。

原始程式→直譯程式→機器目的碼

1-3-1-1 掌握系統的運作

作業系統的主要資源: 系統的特徵,執行的程式,儲存空間,程式的管理

探索系統的運作狀況: 系統指令,了解執行的指令與占用的資源,了解儲存空間的使用狀況,了解相關的介面與周邊裝置,了解系統服務的狀況

1-3-1-2 從實做中思考(Windows 10家用版)

1. 系統內容: 點選本機按右鍵→選內容→選進階系統設定

2. 工作管理員: 功能為查看系統中的程式執行列表、主記憶體的使用追蹤、CPU使用率追蹤與網路使用情形的追蹤; 開啟同時按下++

3. 磁碟管理工具: 開始→設定→系統→儲存空間

4. 安裝或解除程式:

1-3-2-1 系統管理設定

第一次使用電腦或是裝置時的設定: 開機的設定,網路設定,顯示的設定,印表機的設定,驅動程式

常見的設定: 使用者的設定,個別程式的設定,系統的登錄(registry)

1-3-2-2 系統管理自己來

2-1-1 何謂作業系統(參考1-2-3 內容)

2-1-2 作業系統功能與組織架構

作業系統的功能: 處理器processor的管理、記憶體memory的管理、檔案file的管理、裝置device的管理

作業系統的組織架構: 1. 使用者 2. 應用程式 3. 核心層(kernel) 4. 硬體

作業系統的主要成員: user command interface, memory manager, device manager, file manager, processor manager.

2-1-3 作業系統的型態

作業系統的分類: 1. 批次系統batch system, 2. 分時系統timesharing, 3. 個人電腦作業系統 4. 行動裝置上的作業系統 5. 即時系統real-time, 6. 嵌入式作業系統embedded operating systems

批次系統batch system: 早期的大型電腦使用讀卡機card reader,使用者把程式和資料打到有孔卡中,由操作員依序地一份一份的程式和資料送到讀卡機讀入電腦中執行。由於電腦的處理速度遠超過讀卡機的機械速度,CPU經常處於閒置的狀態。作業系統的主要工作是安排程式依序執行到結束的過程,這種環境稱為批次系統batch system。批次系統的設計很單純,算得上是一種優點,但是並不符合後來越來越複雜的要求。

分時系統: 批次系統並未讓使用者與電腦有直接互動的機會,對於使用者來說,只能等待程式跑出結果來。我們現在常用的視窗作業系統是容許互動的,這是分時系統的由來。分時的意思是把CPU的時間切割,使CPU不會被一個程式拖得太久。分時系統具有多工multitasking的能力,雖然一般電腦的CPU只有一個,但在分時的效果下,好像很多程式都一起同時進行中。

個人電腦作業系統: 個人電腦約在1970年代出現,然後逐漸普及,之前在大型電腦上發展的作業系統很容易移植到個人電腦的平台上。從分時系統的角度來看,一台電腦可供多人使用multi-user,而且可以同時執行多個程式,也就是多工的能力。早期個人電腦並沒有足夠的效能平板電腦與來支援多人多工multi-user multitasking的環境。到1980年代,UNIX系統在個人電腦平台上逐漸成熟以後,其他的作業系統才把多人多工的能力建立起來。

行動裝置上的作業系統: 所謂的「電腦」在行動與無線通訊的時代已經產生了很大的變化。具有電腦特徵的裝置越來越多,尤其是可攜式的設備,例如筆記型電腦、平板電腦與手機等,這些設備也都需要作業系統。Android, iOS或是Windows mobile等都屬於這一類的作業系統。

即時系統: 有些作業系統的功能是比較特殊的,只適用於某些場合,例如即時系統real-time system. 電腦必須在時控條件time constraints容許的範圍內完成工作,否則可能會導致難以控制的後果。

嵌入式作業系統: 嵌入式系統embedded system早期比較常見於一些工業用途的設備中,特別是有即時需求的應用。近年來逐漸應用於資訊家電中,不但應用的領域擴大了,發展也更為迅速。一般的可攜式裝置與網路裝置,有很多都使用了嵌入式系統,有穩定而且尺寸小的特性,能在面積極小的元件上完成特定的功能。

2-2-1 行程process的定義

行程process: 電腦系統中進行運算的基本單元。電腦裡頭可能同時有好多個行程在工作,作業系統必須好好的管理這些行程。透過作業系統的指令可以看到電腦系統中正在執行的程式。

記憶體中行程的內容結構:

1. text section包括程式碼、程式計數program counter與處理器暫存器registers的內容。

2. data section儲存全域變數

3. heap在行程執行期間機動地分配給該行程的記憶體空間

4. stack儲存一些暫存的資料,例如函數參數、傳回的位址return address與區域變數等。

行程的內涵: 1. 執行的目標程式碼object code, 2. 程式執行時所用到的資料 3. 程式執行時所需要的資源resources 4. 行程執行時的狀態status of execution.

2-2-2 行程狀態轉換

行程管理: 多個程式載入主記憶體等候執行,如何將CPU公平而有效地分配給各個程式共同使用,這就是行程管理的主題。負責這項任務的就是行程管理程式process manager。

行程狀態process state:

1. 新建new:程式被讀取載入主記憶體形成一個新行程

2. 就緒ready: 等待分配使用CPU時間以執行程式

3. 執行running: 取得CPU執行程式碼

4. 等待blocked: 行程等待特殊事件的發生或等待輸出/入工作完成

5. 結束done: 程式執行完成工作

狀態的轉換: ◙結束狀態:行程完成工作,進入done狀態 ◙返回就緒狀態:因某種原因被暫停suspend執行,返回ready狀態 ◙進入等待狀態:當行程等待特殊事件發生或需要進行輸出/入處理,為了不浪費CPU時間,行程先進入等待blocked狀態,待特殊事件發生或完成I/O動作,行程將重返就緒ready狀態,進入佇列等待被執行 ◙持續執行:特殊的行程,系統允許它持續佔有CPU.

行程內容: 被執行的機器碼 執行時所需使用的資料 執行時所需使用的資源 堆疊 行程的狀態

行程狀態保持的資訊: 在行程狀態轉換之時,系統要保存的資訊有該行程描述資料、程式目前執行的位址、暫時性產生的資料,保存的資訊的目的,便於再次取得CPU使用權時,後續執行時可有效地掌控所有的資訊。

行程狀態轉換: 作業系統考量以下因素,抉擇一個行程改變它的狀態→各行程狀態、系統環境狀態、資源使用狀態、所發生的事件。

2-2-3

CPU排程作業: CPU排程設計追求的目的→在公平原則下分享CPU資源、CPU的運用可達最高效能、盡量縮短每一個行程等候的時間。

常見的排程演算法: 先進先執行(first-come first-serviced, FCFS)、最短工作優先(shortest job first, SJF)、優先權排程(priority scheduling)、循環分時(round robin scheduling)、多層次優先權(multi-level queues).

先進先執行(first-come first-serviced, FCFS): 最簡單的排程方法,根據行程進入就緒佇列的順序,先來的先執行,這種方式似乎好像我們在銀行臨櫃排隊的情況,如果碰到前面有一個人申辦十分繁瑣的業務,排序在後面的人就必須耐心等待,整個佇列平均等待的時間將加長。

最短工作優先(shortest job first, SJF): 選擇需要CPU服務時間最短的行程優先執行,這種方式可以佇列中平均等待的時間縮短縮短,對於需要CPU服務時間較久的行程而言,將被一再順延。

優先權排程(priority scheduling): 每一個佇列中等待的行程都被授予一個優先權,排程管理程式計算並選擇優先最高的行程先執行,系統對優先權低而且等待較久的行程,會適時調整優先權。

循環分時(round robin scheduling): 排程方式中最常用的一種,將CPU的處理時間以一個固定的單位(time slot),循環地平均分給就緒佇列中的每一個行程,依順序執行中的行程,當次被分配的CPU時間用完,就必須將CPU使用權交給佇列中的下一個行程。time slot長短的設計會影響執行效能和狀態轉換的頻率!

多層次優先權(multi-level queues): 多層次優先權排程是優先權排程的延伸,它設置多個佇列,不同的佇列擁有不同的優先權,排程管理程式將優先權一樣的行程放在同一佇列,各佇列擁有各自的排程法則。不同的佇列又該如何分配CPU的使用權? 一般有兩種做法: 較高優先權的佇列較優先獲得CPU的使用權;設定分配的比率,依比率將CPU的使用權分配給各佇列。

2-2-4 死結探討

哲學家用餐問題: 假設有五位哲學家圍坐在一張圓形餐桌旁,做以下兩件事情之一：吃飯,或者思考。吃東西的時候,他們就停止思考,思考的時候也停止吃東西。餐桌中間有一大碗義大利麵,每位哲學家之間各有一支餐叉。因為用一支餐叉很難吃到義大利麵,所以假設哲學家必須用兩支餐叉吃東西。他們只能使用自己左右手邊的那兩支餐叉。

死結狀況的發生: 如果五個大佬同時都喊餓啊餓啊,五個人都拿起了叉子,結果悲劇的發現沒有一個人能吃到兩個叉子的飯,吃飯不用兩個叉子又怎麼能叫吃飯呢?不吃了！老子等兩個叉子出現！大佬氣無叉而等待(執行緒氣無資源而計算機死鎖)

死結形成的原因: 1. 互斥條件mutual exclusion：執行緒對資源的訪問是排他性的,如果一個執行緒對佔用了某資源,那麼其他執行緒必須處於等待狀態,直到資源被釋放。

2. 佔有和等待hold and wait：執行緒T1至少已經保持了一個資源R1佔用,但又提出對另一個資源R2請求,而此時,資源R2被其他執行緒T2佔用,於是該執行緒T1也必須等待,但又對自己保持的資源R1不釋放。

3. 不間斷no preemption：執行緒已獲得的資源,在未使用完之前,不能被其他執行緒剝奪,只能在使用完以後由自己釋放。

4. 循環等待circular wait：在死鎖發生時,必然存在一個“程序-資源環形鏈”,即：{p0,p1,p2,...pn},程序p0(或執行緒)等待p1佔用的資源,p1等待p2佔用的資源,pn等待p0佔用的資源。(最直觀的理解是,p0等待p1佔用的資源,而p1而在等待p0佔用的資源,於是兩個程序就相互等待)

死結的預防策略: 1. 偵測的原則在於遇到系統可能在不安全的狀態下,原則上絕不再分配資源。 2. 復原: 當發現行程長久停滯,便可執行偵測演算法,判定真正發生死結。使用復原的方法,將系統復原到沒有死結前的狀態。

ex. 服務生解法、資源分級解法、髒叉子請求法

2-3-1 記憶體的階層架構

電腦的儲存媒體: 1. 原級儲存媒體primary storage, 2.次級儲存媒體secondary storage.

記憶體管理程式的主要目標: 1. 管理主記憶體的分享sharing, 2.降低記憶體的存取時間access time.

記憶體設計主要的要求: 系統的硬體與軟體設計應儘量讓主記憶體的存取時間縮短。主記憶體越大則系統可運用的資源越充裕,使用虛擬記憶體的技巧可以讓主記憶體用起來好像比實際的容量為大。主記憶體的成本要合理,應只占電腦成本的一小部分。

2-3-2 記憶體管理基本概念

概念: ◎程式執行的先決條件必須先在入主記憶體 ◎主記憶體空間有限,它是一項珍貴的資源 ◎主記憶體的大小有限,資源共享原則下,通常無法將所有等待執行中行程的程式碼完全載入,只好隨著程式的執行把使用到的程式碼和資料動態性地載入。

主記憶體實體位址: 將主記憶體以位元組byte為單位,依組成順序從數字0開始編號,實際主記憶體位址稱為實體位址physical address,行程執行時,CPU中位址暫存器存放的是程式的實體位址

程式邏輯位址: 程式經過編譯後對每一個指令都產生了位址編號,這個指令位址稱為邏輯位址logical address. 為了讓主記憶體空間能彈性運用而設計了重新定址功能;系統重新定址,程式載入時不必限制在一定的主記憶體位址區段。

重新定址功能: 每次載入程式時,指令重新定址,將程式邏輯位址與主記憶體實體位址產生對應關係。

記憶體管理: ◎如何讓記憶體有效共享? ◎在多行程共用資源的情況下,如何決定程式碼的進出? 在記憶體管理設計時要選擇適合的記憶體配置策略,以達成兩項主要目標: 1. 妥善管理主記憶體資源的分享sharing, 2. 有效降低記憶體的存取時間access time.

2-3-3 記憶體配置策略

動態 vs. 靜態記憶體分配: 記憶體管理程式必須把記憶體空間有效地分配給所有的行程共用,分配的方式可以分成兩大類→靜態的固定分割區塊: 在作業系統的組態設定時,將主記憶體空間分割成固定大小的區塊,然後分別分配給各行程。依照動態決定分配空間: 系統分配剛好符合行程需求的記憶體空間,所分配到的記憶體區塊大小是變動的。

記憶體配置: 行程的程式碼依動態配置原則,分段載入主記憶體;已載入的程式碼區段,因執行完成或是系統管理上的需要而被要求移出主記憶體;各程式碼進出之間,主記憶體位址空間變成不連續區段,針對主記憶體有效運用,程式碼移出與載入,管理程式必須要有所抉擇。

主記憶體配置的策略: ◎最佳配置best fit→從所有可用的主記憶體區段中選擇最接近且符合行程需求的區塊,其目的在於:若有剩餘或許是一些小片段 ◎最差配置worst fit→從所有可用的主記憶體區段中選擇最大且符合行程需求的區塊,其目的在於:若有剩餘不會是一些小片段,或許還可供其他行程使用 ◎最先配置first fit→從所有可用的主記憶體區段中選擇第一塊而且符合行程需求的區塊,其目的在於:節省尋找與比對的時間

2-3-4 認識虛擬記憶體

基本觀念: 生意好的餐廳有所謂的翻桌率,也就是在同一段進餐時間,同一桌可能可以陸續讓好幾組客人依序用餐;所以餐廳即使只有10張桌面,可能一個中午出了30桌的菜量。電腦的記憶體空間也有限,為了服務更多的處理元,作業系統也採用了類似的概念:處理元執行時需要的資料放置到記憶體中,即使有的放不下,也暫時放到磁碟,等需要用到時再想辦法移到記憶體中。

隨時分頁demand paging的方法: 可以讓一個程式在完全沒有載入到只記憶體中的情況下,依然能夠繼續執行;如此一來,程式佔有空間的大小就比較沒有限制,這種技術稱為虛擬記憶體virtual memory,分頁本身在系統的安排下,能夠在磁碟與主記憶體中移動,讓使用者覺得執行的程式一直都在主記憶體中。

程式分段: 早期的程式設計者要想辦法讓程式寫得不佔有那麼多空間,後來有人想到可以把程式分段,這些段落也稱為overlay,需要用到的段落就搬到主記憶體。雖然系統可以做到overlay在磁碟與主記憶體之間的搬移,但是對於程式設計者來說,程式的分段實在是煞費苦心。overlay的觀念引發了後來虛擬記憶體的觀念。

虛擬記憶體的技術: 可以分成分頁法paging與分段法segmentation兩大類。虛擬記憶體要靠記憶體管理程式與處理器的合作,記憶體管理程式追蹤分頁與分段的使用,處理器則需要在適當的時機產生中斷interrupt,處理虛擬位址。

2-3-5 虛擬記憶體技術

虛擬位址與實體位址: 作業系統設計可以選擇不同形式的虛擬記憶體,從使用者觀點在虛擬位址與實體位址之間,對應方式有兩種主要架構: 分頁法paging與分段法segmentation.

分段法: 程式設計者自訂的個體entity,分段可以當成一個獨立的邏輯單元,它決定程式的分割方式,產生大小不一的分段,例如: 將一個函式訂為一個分段. 每一個分段都是連續的線性空間,實際運作上,分段本身就成為虛擬記憶體管理員在主記憶體與次記憶體之間移動資料的單位。

分頁法: 分頁法將虛擬記憶體視為一個大型、連續的線性空間,由n個儲存格序列組成,儲存格就是虛擬記憶體被切割成固定大小的分頁pages, 實體記憶體也被設定成分頁大小相同的頁框page frame,分配給同一個行程的分頁框不必在連續的位址上,分頁對應表page map會建立虛擬空間與實體空間之間分與分頁框的對應關係。

動態載入dynamic loading: 虛擬記憶體管理程式要支援動態載入的功能,執行時期把虛擬位址與實體位址連結起來,虛擬記憶體管理員要負責載入引用的物件,同時重建所謂的位址轉換對應關係address translation map.

動態載入說明: 例如當程式執行到某一段指令時,偵測到該物件不在實體記憶體中,引用到的物件位於虛擬記憶體位址空間時,系統會依設計策略而啟動一連串的處理程序,把物件載入到主記憶體,同時重新定義對應關係。

動態載入策略: 包括了一些重要機制,位址對缺機制address mapping mechanisms、安置策略placement strategies、替換策略replacement strategies、負載控制load control、共享方式sharing.

位址對缺機制address mapping mechanisms: 設計概念性位址對照處理程序,可將行程中邏輯位址轉換成程式碼載入的實體位址。

安置策略placement strategies: 行程執行中要存取虛擬記憶體空間內的指令或資料,該部分必須移入實體記憶體, 有效能地決定要在那一個位置載入所需要的虛擬記憶體空間區段。

替換策略replacement strategies: 當虛擬記憶體的程式指令需要載入主記憶體,但是主記憶體沒有足夠的空間來接納,虛擬記憶體管理程式就要決定如何將目前存在於實體記憶空間中某個行程的程式碼移出,或移出部分的頁或段,讓出較多的空間。

負載控制load control: 為了發揮記憶體空間效能,採用動態載入的方式,行程執行時,實際需要使用的區段或分頁才進行載入的動作,程式碼頻繁地載入/移出會影響效能。行程越多,能分配到的主記憶體資源越少,負載控制策略就是決定應該何時該增加作用中的行程數目,何時該減少行程數目。

共享方式sharing: 在某些特殊情況下,2個或2個以上的行程共享記憶體中相同的分頁或分段,例如:共同呼叫相同的函式,具有共享的規劃將可增加記憶體使用效能。

2-4-1 電腦檔案的概念

檔案的由來: 1. 存放資料的單位 2. 對於使用者來說,在跟作業系統接觸的過程中最常遇到的就是檔案file. 3. 檔案可以用來儲存程式與資料 4. 通常作業系統都會含有一個檔案系統,主掌檔案與目錄directory的管理,例如微軟公司Windows作業系統中的[檔案總管]

檔案的用途: 使用者可以透過檔案來儲存資料,長時間保存的文件可以放在檔案中歸檔,程式語言利用檔案來儲存可執行的程式碼,幾乎各種場合中都有用到檔案的機會,Microsoft Windows環境的[檔案總管]裡看到的幾乎都是檔案.

檔案的概念: 實體概念 vs. 邏輯觀點

2-4-2 檔案系統的階層模型

模型I: 使用者/檔案系統/ I/O系統, 模型II: 檔案與目錄/邏輯區塊/實體裝置上的位址

檔案的觀念: 電腦必須把資料儲存在各種類型的儲存媒體上,包括記憶體、硬碟或是隨身碟等,儲存媒體的種類與運作的機制雖然不同,但對於使用者來說,都可把資料的集合看成檔案,然後由作業系統負責將檔案的內涵對應儲存媒體上儲存的資料,檔案是儲存在次級儲存媒體上的,檔案被開啟使用時,資料才會搬到記憶體中。

2-4-3 檔案的基本特徵

檔案的屬性特徵: 1. 檔案名稱: 一般使用者所知道的該檔案的名稱(符號的檔案名稱) 2. 所有者owner: 建立檔案的行程所屬的使用者,檔案的所有權ownership有時候可以經由系統轉移 3. 使用者user: 目前打開檔案的所有行程 4. 檔案鎖file locks: 可用來鎖定檔案進行讀或寫的動作 5. 目前的狀態: 記載檔案目前使用的狀態 6. 是否可共享sharable: 決定是否多個行程可以同時開啟檔案使用

保護的設定: 決定檔案的所有者與使用者能對檔案進行的操作

其他的屬性: 包括檔案的大小、檔案類型、建立的時間、上回使用的時間、使用的次數與檔案在儲存裝置上存取的細節等資訊。

檔案名稱的組成: 假如作業系統知道檔案的類型,很自然就會選擇適合的處理方式,從副檔名file extension可以判定檔案的類型,通常應用軟體會訂定所處理的檔案的副檔名,作業系統也可以將某種應用系統跟特定的副檔名關聯起來。

2-4-4 檔案的種類

2-4-5 檔案的操作

系統對於檔案的處理: 檔案開啟以後,檔案管理員會紀錄檔案的使用狀態。由於同一個檔案可能被多個行程共用,所以每組行程與檔案的使用關係的狀態都必須分別記錄。除了檔案的描述資訊儲存在磁碟上之外,還要另外再記錄相關的動態資訊。

檔案的操作: 1. 建立檔案 2. 開啟檔案(檔案名稱):以檔案名稱來開啟檔案,更新檔案描述中的資料,將檔案位置重設為0,並傳回檔案指定名稱file IDentifier. 3. 關閉檔案(檔案指定名稱): 以檔案指定名稱為參數,釋出檔案描述資料結構與其他相關的資源. 4. 讀取( 檔案指定名稱、緩衝區、長度):將指定長度的檔案資料拷貝到緩衝區中,同時傳回完成讀取後的檔案位置(file position). 5. 寫入( 檔案指定名稱、緩衝區、長度):將指定長度的資料拷貝從緩衝區寫入目前的檔案位置中,同時傳回完成寫入後的檔案位置(file position). 6. 搜尋( 檔案指定名稱、檔案位置): 將目前的檔案位置改成指定的檔案位置,隨後的讀寫操作從新的檔案位置開始. 7. 刪除檔案

2-4-6 檔案與目錄

檔案的組織方式: 一個作業系統中可能有多個甚至多種檔案系統,由於檔案系統中的檔案會累積得越來越多,需要透過一種方式把眾多的檔案組織起來。目錄directory就是組織檔案的一種方式,微軟Windows作業系統的檔案總管就是運用目錄與檔案行程的樹狀結構。

2-4-7 檔案空間配置

檔案資料儲存: 電腦檔案大部分儲存在磁碟,經常以磁帶、光碟來備份資料,磁碟格式化以後規劃實體區塊為資料儲存單位;從使用者的角度看檔案,它是完整而且連續的個體,實際上存放到儲存媒體上的資料,並不一定是使用連續的區塊。

檔案空間的配置考量: 資料存放到媒體並不一定是使用連續的區塊,選擇那一個可用的磁碟實體區塊儲存,協助檔案讀取、寫入及其他資料的存取

空間的配置方法: 連續配置法continuous allocation、鏈結串列配置法linked list allocation、索引配置法indexed allocation.

連續配置法continuous allocation: 檔案直接映射到一連串連續的磁碟實體區塊,檔案資訊存於檔案描述器中,這種配置法非常簡單,很容易實現檔案的讀取,對檔案刪除/插入中間紀錄時比較不具彈性。

鏈結串列配置法linked list allocation: 將磁碟實體區塊利用鏈結方式組織起來,配置的實體區塊不必相連,檔案管理系統將指標指向檔案的第一個區塊,藉由每一個鏈結的區塊設定的向前指標,只到邏輯上的下一個區塊。

這種方式解決了連續配置法需要連續區塊存放的問題,但是每個區塊都要建立指標,會形成空間上的浪費,萬一指標鏈結損壞將造成不可挽救的情況。

索引配置法indexed allocation: 檔案建立時配置一個索引區塊,藉由索引組織可以直接存取檔案紀錄,索引也可以是多層次結構。

UNIX的檔案組織: 採用三層式的索引機制每個檔案描述器(i-Node)包含將邏輯檔映射到磁碟區塊的13個項目,前10個項目直接指向存放內容大小為512byte的區塊;如果空間仍不符需要,第11項可擴展一層128個區塊,加上先前10個區塊合計有138個區塊; 儲存空間需求超過138∙512bytes時,第12項則擴展2層可達128²(16348)個區塊;同理,對於超大檔案則可由第13項擴展2層可達128³(2097152)個區塊。

2-5-1 I/O系統簡介

電腦周邊裝置: 概括可分為資料傳輸裝置communication devices,(包括輸入裝置input devices,輸出裝置output devices),儲存裝置storage devices.

周邊裝置的功能: ◎輸入/輸出裝置傳送與轉換資訊(人類社會使用類比形式的資訊電腦內部儲存數位形式的資料) ◎電腦處理資料產生結果的儲存

輸入/輸出管理: 電腦系統硬體配置上,不論內部或外部裝置都要以合適的匯流排界面連接。不同的匯流排、不同的設備各有不同的傳輸資訊速度。各種裝置擁有不同產生和接收資料的速度、單位、可靠度、資料傳輸方向(輸入、輸出、雙向)。作業系統必須支援這些功能、特性差異極大的裝置,管理及協調資料傳送的順暢。

I/O系統簡介: 電腦系統中資料傳輸裝置與儲存裝置都稱為I/O裝置,作業系統作業系統中直接與這些裝置互動的部分稱為I/O系統,許多I/O裝置是獨立運作;任何一項裝置運作都能夠同時與其他裝置並行運作,並且隨時可與CPU相互傳遞訊號及資料。

I/O系統主要的功能: ◎追求系統最佳效能 ◎CPU運轉之時,可以兼顧到所有的I/O裝置(對任何裝置提出I/O請求,可以迅速處理減少該裝置閒置時間; 不能花費太多時間去服務各項裝置)

2-5-2 I/O系統的階層模型

I/O基本觀念: 電腦系統裡的CPU和其他的控制單元(或稱控制器controller)是以匯流排連接在一起。每個控制單元負責管理某種裝置,CPU和裝置之間資料的流通必須經由控制單元來協調,CPU和裝置之間資料的流動就是所謂「輸入」和「輸出」的作業,也簡稱為I/O。

I/O系統的階層式模式: 1. 裝置驅動程式 2. I/O系統界面

2-5-3 裝置管理之溝通方式

裝置管理之溝通: I/O系統架構中,裝置控制器扮演CPU和裝置之間溝通的角色。在輸入和輸出的作業中,CPU如何與裝置控制器傳送訊息,主要有三種方式: 輪詢polling, 中斷interrupt, 直接記憶體存取DMA Direct Memory Access.

輪詢polling: 在這種模式下,CPU負責重複讀取和測試裝置控制器的busy旗標,來明確掌握I/O裝置是否已經完成所指派的資料傳輸工作;由CPU要執行周邊裝置與主記憶體之間資料搬移的工作。這兩項工作造成CPU很大的負擔。

中斷interrupt: 設計一整機制可減輕CPU的負擔→形成在處理I/O資料傳輸的時候,暫停該行程,另外讓其他行程可以在這段時間使用CPU;在硬體的設計上,CPU提供了一條中斷請求線路interrupt request line,當CPU執行完指令時都會檢查該條線路上的訊號,如果有中斷請求,CPU會把目前執行的狀態先儲存起來,跳到中斷處理程序interrupt handler routine開始執行,完成後再回到中斷前的指令繼續執行。

所謂中斷請求就是由某些外部裝置發給CPU的一種硬體訊號。

直接記憶體存取DMA: 採用輪詢或中斷的方式,CPU都必須負責主記憶體和裝置控制器資料緩衝區之間來回搬運資料。在處理慢速率裝置時,CPU在傳送資料間可以處理上千的指令,對CPU效能負擔影響不大。對於快速裝置而言,對CPU而言額外負擔很大,為了減輕CPU進行I/O的負擔,在電腦系統的設計上可以加入一個具有獨立處理器的裝置,叫做直接記憶體存取控制器DMA controller.

DMA讓裝置控制器可以傳輸資料給主記憶體,或從主記憶體中取得資料,透過DMA,CPU只要下達傳輸指令,實際的工作都由DMA執行。

2-5-4 作業系統層次的裝置管理

作業系統層次的裝置管理: 周邊裝置功能及資料存取速度有很大的差異性,下層的驅動程式與個別裝置具有緊密對應關係,上層I/O子系統提供作業系統層次的裝置管理,I/O子系統安排資源的分配,以期作業順利完成。

I/O子系統一般性的設計: 緩衝Buffering, I/O排程,快取記憶體Cache, 周邊並行Spool.

緩衝Buffering: 緩衝區是一種硬體暫存器或是主記憶規劃出來的特定區塊,用來存放行程產生的資料,或是複製取用資料,可以解決資料傳送與接收間的問題。

需要緩衝區處理有三個理由: 1. 資料傳送與接收兩端速率不一致,利用緩衝處理可避免資料遺失 2. 資料傳送與接收兩端資料單位大小不同,利用緩衝處理可以將資料組合或切割 3. 緩衝區是主記憶體的特定區,當生產行程產出資料置入緩衝區時,消費資料的行程不必佔用記憶體;相反的情況,當行程從緩衝區消費資料時,生產行程不必佔用記憶體,兩者均可增加記憶體使用率。

I/O排程: I/O子系統追求系統效能,公平地執行I/O動作,盡量減少平均的等待時間,I/O排程設計每一個I/O裝置建立一個請求佇列,I/O請求置入各裝置佇列等候,排程程式scheduler依照排程法則,優先順序來調整佇列中各請求的次序。

排程法則: 裝置具有不同的特性,排程法則不盡相同,基本上要求: 所有的I/O請求必須在有限度的等待時間內完成;每個佇列內的I/O請求,平均等候時間盡量縮短;裝置都能在最快速時間內處理完I/O請求操作。

快取記憶體Cache: 為了提升資料存取的效率而設置快取記憶體;從周邊裝置讀取資料一般速度緩慢,如果將讀取的資料複製在存取速度較快的快取記憶體中,遇到資料需要重複讀取的情況時,可直接從存取速度較快的地方取得,便可加快I/O速度。

周邊並行Spool: ex. 同一時間有多個行程都要輸出資料給印表機,I/O系統該如何處理才能印出正確資料(有些I/O裝置進行I/O動作時,必須依序而不可交錯方式輸入/輸出資料; 作業系統採用周邊並行Spool設計)。在磁碟中設定一個區塊,建立印表機佇列,當行程列印資料時,不會將資料送往印表機,而是將資料寫到印表機佇列檔案(虛擬印表機),因此多個行程同時並行列印已不成問題,接著由印表機佇列依序將資料輸出至印表機。

2-6-1 使用者的識別與管理

存取控制access control與系統安全: 使用者持有的證明、使用者所知道的事物,例如密碼password、使用者本身的特徵

認識密碼: 密碼是非常好用的身分辨識方法,除了可用在一般系統登入的帳號與密碼的組合之外,還可以當作存取某種資源的鑰匙,或是取得某些權限的門檻。密碼管制有很多缺點,一旦密碼被猜到或洩漏出去,就完全失去了保護的功能,有很多方法可以用來改善密碼的問題。存取控制是保護系統的一種方式,也是系統安全的基礎。

2-6-2 內部保護機制

使用者帳號的種類: 匿名anonymous, 一般使用者帳號user account, 管理者帳號administrator account.

為什麼要保護? 會對一個作業系統進行存取的是使用者、行程與外來的程式,所謂的存取就是使用系統所管理的資源,例如CPU、檔案、記憶體、印表機等。作業系統必須對資源採取保護的機制才能確保任何的存取都是合法經過授權的。

保護的另外一層涵義: 作業系統中會有很多活動中的行程,各有使用的資源與執行的空間,系統必須確定行程的活動空間不會彼此糾結,造成執行上的謬誤或是系統停擺,這也是保護機制必須處理的問題。

存取權限的階層: 指令階層的存取、系統階層的存取

指令或行程對記憶體的存取: CPU內暫存器的資料, I/O裝置控制器內暫存器的資料, 主記憶體儲存的資料　

3-0 本章摘要

• 為什麼需要學程式語言?

• 程式語言的由來與演進

• 程式語言的組成與分類

• 程式的處理方式

• 程式語言的控制語法

• 程式設計的環境

3-1 為什麼需要學程式語言?

基本觀念: 和電腦溝通的「程式語言」是一種截然不同的溝通方式,唯有具備了這種語言能力之後,才能告訴電腦如何解決現實世界裡的各種問題。和電腦溝通的主要動機是使電腦能替我們工作。

和電腦溝通的過程: 所要進行的工作或是要解決的問題必須有很明確地描述,同時也有預期達成的結果,接下來可以把工作進行的程序詳細的寫出來,最後只要把這些程序轉化為以程式語言寫成的程式program,就可以交由電腦來幫我們完成所要進行的工作。

最主要的關鍵: 了解所要完成的工作; 如何以電腦了解的語言來描述進行這些工作的程序。

如何設計程式語言? 描述能力expressive power, 容易使用.

3-2 程式語言的由來與演進

電腦執行的基本運算: 算術arithmetic運算、邏輯logical運算

1加到100的運算問題: sum=0; for i=1 to 100; sum=sum+i;

3-2-1 程式語言的由來

程式語言對電腦的影響: 指令循序地執行,改變儲存於記憶體中的資料,藉此完成工作,當凡紐曼架構中執行的指令不同時,其功能也就不一樣,這是很重要的發現。電腦的功能就和一般的電器不一樣,電腦有多元化的功能,而一般電器的功能是固定的。

3-2-2 程式語言的演進

幾種著名的程式語言: 用來解決科學計算問題的FORTRAN是很多理工專業的人最早接觸的程式語言; COBOL Common Business Oriented Language在商業應用的資料處理上,跟著IBM的大型主機一起盛行; ALGOL ALGorithmic Oriented Language的出現產生了以BNF來表示程式語言語法的方式; LISP程式的執行完全是函數function的計算,整個程式看起來就像一個大串列list; PASCAL語言是結構化程式設計Structured programming盛行的主要助力,也是1980年代電腦語言課程最常用的程式語言; Prolog是有名的人工智慧語言; smalltalk也是一種相當特殊的語言,以物件導向模型Object oriented model為基礎。

3-3 程式語言的組成與分類

3-3-1-1 程式的組成

基本觀念: 程式語言可用來描述演算法,使其能在電腦上執行。程式語言最主要的組成是語法syntax和語意semantics. 語法代表程式語言所提供的語言內容,會決定程式寫出來的外觀,像英文的單字就可以看成是英文的文法。語意代表各種語法所描述的功能,以及被執行時會產生的作用。

以PASCAL程式行為例: X和Y代表程式變數program variable的名稱,在語法上使用了指定assignment的描述,即符號「:=」,在語意上表示將Y的值指定給X,執行的時候,系統會把儲存在Y位址上的值寫入X位址. X:=Y;

程式的組成: 程式program是由符號symbol組合而成的,假如從電腦檔案的角度來看,程式儲存在檔案中,裡面的符號就是由各種字元組合而成的。一般的原始程式source program多半是純文字的檔案,而且以英文為主。

3-3-1-2 BNF表示法

貝諾爾格式BNF, Backus Naur Form: 文法必須用適當的方式來描述,著名的BNF就是描述程式語言文法的一種方式。三角括弧中的符號(即<>中的符號)代表非終結符號,不在三角括弧內的符號即為終結符號。所有出現在文法規則中的終結符號必須是有效valid的語言符號。方括弧([ ])代表其中的符號可用可不用。波浪括弧({ })代表其中的符號可重複出現。

BNF表示法的實例: 兩條文法規則說明一個有效的語法可由[x]y{ <money> }組成,非終結符號money可以是10, 20或是30. 垂直分隔線(|)代表「或」的意思。從這兩條文法規則中可以看到x, y, 10, 20, 30為終結符號, goal為目標符號。

文法必須遵守的法則: 1. 非終結符號在文法規則的左半部必須至少出現過一次,這樣我們才知道非終結符號由那些其他的符號組成。2. 目標符號不能出現在任何文法規則的右半部,因為目標符號是由其他的非終結符號及終結符號來描述的,也是一個有效語法的代稱。

3-3-1-3 程式流程圖

運算式的文法:

1. <運算子句>::=<運算式>=

2. <運算式>::=<數值>[<運算元><運算式>]

3. <數值>::=[<正負號>]<位元組>[<位元組>]

4. <位元組>::=<位元>[<位元組>]

5. <位元>::=0|1|2|3|4|5|6|7|8|9

6. <正負號>::=+|-

7. <運算元>::=+|-|*|/

運算公式的推演: 從目標符號開始,也就是<運算子句>,把25-37=當成一個<運算子句>,依照規則1,25-37必須是一個運算式,因為這樣25-37=才能取代成規則1右邊的表示法。依照規則2, 25可看成一個數值, -37可拆成運算元-與運算式37. 依照規則3與規則4,發現25的確是個數值。依照規則2,可繼續將37看成是數值3、運算元與運算式7的組合(單一的數值也可看成是一個運算式). 25-37=

文法分析parsing的程序: 由上而下的文法分析從目標符號開始,試著推演出含有終結符號的表示法,得到全部是由終結符號組成的字串。BNF表示法不適合用來描述一般的自然語言,例如大家日常所交談的口語。BNF所適合描述的文法稱為與上下文無關的文法context-free grammar,單純的取代法則與上下文無關。一般口語使用的是與上下文有關的文法。

3-3-2 程式語言的分類

程式語言方法論: 命令式的imperative, 函數式的functional, 邏輯式logical, 物件導向object-oriented.

方法論與運算模型: 命令式的程式語言以下指令的方式引導程式的執行,像Pascal, C等都屬於這一類的語言,大多數的開發語言都具有這種特徵。物件導向式的程式語言多了物件object及類別class的觀念,同時也加上了一些物件導向式的特性,smalltalk, C++就屬於物件導向式的程式語言。以C++來說,和C非常類似,原本就具有命令式語言的特徵,只是又比C多了物件導向的特性。

以一段LISP的小程式為例:

另外一種常見的分類方式: 宣告式的declarative, 程序式的procedural.

3-3-3 實例:運算式的文法

運算式的文法:

1. <運算子句>::=<運算式>=

2. <運算式>::=<數值>[<運算元><運算式>]

3. <數值>::=[<正負號>]<位元組>[<位元組>]

4. <位元組>::=<位元>[<位元組>]

5. <位元>::=0|1|2|3|4|5|6|7|8|9

6. <正負號>::=+|-

7. <運算元>::=+|-|*|/

25-37=運算公式: 從目標符號開始,也就是<運算子句>,把25-37=當成一個<運算子句>,依照規則1, 25-37必須是一個運算式,因為這樣25-37=才能取代成規則1右邊的表示法。依照規則2, 25可看成一個數值, -37可拆成運算元-與運算式37. 依照規則3與規則4,發現25的確是個數值。依照規則2,可繼續將37看成是數值3、運算元與運算式7的組合(單一的數值也可看成是一個運算式).

認識BNF表示法: BNF的表示法是一種描述程式語言語法的中介語言metalanguage,整個表示法行程了語言的文法grammar. 這套文法必須定義出每個非終結符號的取代規則,有一個特別的非終結符號叫做目標符號,當我們寫好一個程式準備檢查這個程式是否符合文法規則時,可議把整個程式當作目標符號,然後看看能否利用文法規則把整個程式變成終結符號的組合。

推演的過程: 以文法右邊定義來取代左邊符號的過程也叫做推演derive或產生generate,結果是確定目標符號是否能夠經由推演的過程完全由終結符號所取代。文法本身其實規定了有那些終結符號是屬於語言可以接受與詮釋的符號,以及終結符號能以甚麼樣的順序出現在程式中。

3-3-4 文法的流程圖syntax diagram

BNF的表示法:

判定下面的句子是否合乎上面的文法:

I-own-her-21232-dollars. (V)

I-lend-you-12600-dollars. (V)

you-own-him-25-dollars. (X)

I-lend-her-255. (V)

3-3-5 程式語言的分類

程式語言演進的歷程: 第一代程式語言→第二代程式語言→第三代程式語言

從程式語言採用的方法論Paradigm來分類: 比較容易找到同一類的語言→命令式的imperative, 函數式的functional, 邏輯式logical, 物件導向object-oriented. 這些方法論決定了程式語言的運算模型model of computation.

常見的語言及其方法論: 命令式的程式語言以下指令的方式引導程式的執行,像Pascal, C等都屬於這一類的語言,大多數的開發語言都具有這種特徵。物件導向式的程式語言多了物件object及類別class的觀念,同時也加上了一些物件導向式的特性,smalltalk, C++就屬於物件導向式的程式語言。以C++來說,和C非常類似,原本就具有命令式語言的特徵,只是又比C多了物件導向的特性。

Prolog: 邏輯式程式語言的一種,利用語法來描述事實facts及推理的規則rules,程式執行時就以邏輯的理論為根本,以事實為基礎,用規則來推理出更多的結論。

另外一種常見的分類方式: 把程式語言分成宣告式的declarative, 與程序式的procedural兩大類. 宣告式的語言不必詳述運算的步驟,像資料庫系統常用的結構化查詢語言SQL, Structured Query Language就是一種宣告式的語言。程序式的語言一步一步描述運算的過程,像Pascal, C, C++等就可算是宣告式的程式語言,這一類的語言能將各種運算描述得非常清楚,具有運算上的完整性Computational completeness.

3-3-6 LISP語言

一段LISP的小程式為例:

程式的涵義: 整段程式以字串定義了factorial(a)這個函數, cond的指令代表條件式的選擇, ((<a 0) nil)表示若a<0 則傳回nil, ((=a 0) 1)表示若a=0則傳回1, (t (times a (factorial (minus a 1))))代表若執行factorial函數則傳回的結果是afactorial(a-1), 這是當前面a<0 和a=0都不成立時factorial會傳回的結果。因此factorial(5)執行的結果為120.

3-4-1 原始程式處理的方式

一般程式被處理的過程: 直譯interpret、編譯compile,處理的目的是讓程式能轉換成可以在電腦上執行的型式。

延伸思考: 通常編譯時期會花掉一些時間,但是編譯完以後的程式執行起來會比直譯的情況有效率。一旦程式除錯完畢,只要編譯過一次,就可反覆地執行,直譯程式則每次執行都要再直譯一次。大多數的程式語言在處理上大多仍採取編譯的方式,不管是直譯器或編譯器,我們都把它們歸類成系統程式system program. 各種硬體平台和作業系統都會支援一些程式語言的直譯與編譯程式,作為程式開發之用。

3-4-2 編譯compilation流程

基本觀念: 一個程式的基本組成是象徵符號token,一種程式語言的token可以用regular expressions來制定。regular expressions無法描述巣狀的結構nested constructs,因而有context-free grammar的使用,也就是BNF的表示法。從理論基礎來看,scanner算是一種可決定的有限自動機DFA, Deterministic Finite Automata,功能是辨識程式中的token. Parser是一種下推式的自動機PDA, Push-down Automata,功能是辨識程式中的context-free syntax.

3-4-3 與連結binding相關的決定

與連結binding相關的決定: 語言設計的時候,語言製作的時候,寫程式的時候,編譯compile時期,連結link時期,載入load時期,執行run時期。

延伸思考: 靜態連結static binding表示連結發生在執行時期之前;假如連結發生在執行時期則稱為動態連結dynamic binding. 連結的時間binding times在程式語言的設計上是很重要的問題,提早的連結時間early binding times有助於提升程式效能,延後的連結時間late binding times則容許比較大的彈性。

3-5-1 常見的控制結構:

順序sequencing: 敘述statements或運算式expression依照既定的順序來執行,通常以在程式中出現的順序為執行的順序。

選擇selection: 依照執行時期所得到的條件condition來決定該執行哪一個敘述,也稱為交替alternation.

反復iteration: 重複執行某一段程式碼,可設定執行的次數或是以條件condition來決定是否繼續執行。

遞迴recursion: 程式自己呼叫自己或是運算式自己用來定義自己的情況稱為遞迴。

程序抽象化procedural abstraction: 將一些控制結構寫成的副程式以名稱來代稱與引用,甚至用來定義其他的副程式,這種方式稱為程序抽象化。

並行concurrency: 多個程式片段同時執行的情況,所謂的「同時執行」在電腦中有幾個不同的涵義,有可能分別在不同的處理器上真正地同時執行,或是在相同的處理器上交錯地interleave執行。

控制結構與運算模型: 不確定性nondeterminacy也算是一種流程的控制方式,也就是讓敘述或運算式的執行順序不確定unspecified. 順序sequencing的控制結構在命令式的imperative、 von Neumann與物件導向式的程式語言中是基本的執行控制方式。函數式的程式語言則主要與運算式的取值evaluation順序有關。邏輯程式設計則沒有像上述的結構那麼明顯的控制結構,執行時由推演的法則來主導。

運算式的取值evaluation: 對於函數式的functional程式語言來說,運算式expression是組成程式的主要單位,程式執行時的運算以這些運算式的取值為主。對於命令式的imperative程式語言來說,主要是透過對變數的數值的改變當作運算的主軸。

純函數式的程式語言 vs. 命令式的程式語言: 純函數式的程式語言所用的運算式可能取得的值和它所在的運算環境有關,跟取值的時間先後無關,這種特性也叫引用透明化referentially transparent. 命令式的程式語言則是以副效應為運算的主要手段,也就是說,運算的先後次序對於結果會有影響的。

3-5-2 副程式的觀念

抽象化abstraction的機制: 可以簡化複雜的觀念與事物。常見的有資料抽象化data abstraction與控制抽象化control abstraction. 副程式subroutine是達成控制抽象化的一種機制。

傳值呼叫call by value與傳址呼叫call by reference: f(a);

傳值呼叫call by value: 在傳值呼叫中,傳遞的參數a的值會指定給對應的正式參數,兩者之間沒有其他關係,例如這個值在f中被改變了,也不影響a的值。

傳址呼叫call by reference: 在傳址呼叫中,傳遞的參數a所指向的位址會傳給對應的正式參數,兩者指向相同的位址,假如這個位址值在f中被改變了,則a所代表的值也跟著改變了。

與副程式相關的進階觀念: 多元副程式polymorphic subroutines, 容器container的概念,通用副程式generic subroutines.

3-5-3 指定assignment敘述

純函數式的程式語言 vs. 命令式的程式語言: 純函數式的程式語言所用的運算式可能取得的值和它所在的運算環境有關,跟取值的時間先後無關,這種特性也叫引用透明化referentially transparent. 命令式的程式語言則是以副效應為運算的主要手段,也就是說,運算的先後次序對於結果會有影響的。

基本觀念: 純粹的函數式的程式語言以運算式為程式建立的主要單位,所謂的運算完全以運算式的取值expression evaluation來表示,運算式取值後得到的結果提供給周圍的環境surrounding context繼續進行運算。對於命令式的imperative程式語言來說,運算的過程會改變記憶體中所儲存的值,指定assignment敘述就是用來達成這樣的效果,標準的指定敘述把值指定給一個引用的變數,讓變數所代表的記憶體位址儲存所指定的值。

副效應side effect是甚麼呢? 在程式語言中,任何的語法結構construct若是除了傳回值之外還有其他會影響後續程式執行結果的效應,就稱之為副效應。以指定值的語法來說,由於會改變變數variable的值,自然會影響後續的運算結果,這就是算有副效應。

運算的先後順序: 以一般的算術運算來說,乘與除的運算在優先順序上比加與減來得高,結合性則多半已從左到右為原則。學習一種語言程式的時候,必須要針對這些特性,看看程式語言所支援的是甚麼樣的規則。

指定敘述: X=Y; Y=A+X;

第一個敘述中的Y代表Y的值;第二個敘述中的Y則代表Y的位。符合一般位值模型value model的描述。

位值模型: 代表值value的表示式都稱為右值r-value, 代表位置location的表示式都稱為左值l-value,變數會因為所處的地方不一樣而有不同的詮釋。

垂直性orthogonality是甚麼意思呢? 在程式語言的設計中,一般會希望語言本身的特徵限制越少越好,例如資料形式data types的定義從簡易的到複雜的,最好有一般化的法則,不要有太多的特例。語言的各種語法與功能最好不要互相牽制,各自獨立的話比較不會造成困擾,這樣的語言特性就叫做垂直性orthogonality.

3-5-4 順序sequencing

基本觀念: 在一般命令式的程式語言中,程式行的順序也代表執行的順序,有時候會用像begin...end或是(與)把一連串的程式行組合起來當成一個複合的敘述compound statement,假如再加上之前的宣告,就可以看成一個程式方塊block. 在複合的敘述執行完成時,最後一行的敘述結果往往是我們看到的結果。

3-5-5 選擇selection與反復iteration

基本觀念: 選擇selection的控制結構通常都出現在if-then-else的語法,if後面通常會跟著一個代表條件condition的運算式,由該條件取值的結果來決定執行then還是else後面的程式片段。巢狀的(nested)if敘述利用多個if來行程比較複雜的分岔branch,可以用控制流程圖來表示執行的順序。

常見的迴路: 列舉式的控制迴路enumeration-controlled loop, 邏輯式的控制迴路logically controlled loop.

3-5-6 非結構化的流程unconstructed flow

結構化程式設計的特徵: 由上而下的設計top-down design, 程式碼模組化modularization, 使用資料結構。

非結構化的流程: 組合語言assembly language使用跳躍jump的指令來達到執行流程的控制;後來有些程式語言提供go to的語法,跟jump的意義差不多,使用了go to之後,程式的執行流程可能會變得難以追蹤,偵錯不容易;Java就完全禁止go to的使用,在1970年代新興起的結構化程式設計就主張揚棄go to的使用。

3-6 程式設計的環境

與程式設計相關的輔助功能: 直譯程式interpreter與編譯程式compiler可以幫助程式的開發,程式設計的環境可能還有其他的工具來輔助程式設計者;與系統相關的有assembler、debugger、preprocessor與linker等程式,大多數的程式語言在撰寫時需要編輯程式editor.

完善的程式開發環境: 做簡單的語法上的檢查,顯示提示文字幫助程式設計者找到要用的語法,讓使用者在程式中快速的來回瀏覽,找到需要修改或新增的地方;程式組態的檢查管理configuration management,例如各程式模組的相關性與編譯的先後紀錄。

整合式的integrated開發環境: 把所支援的功能都集合起來,形成一個完整的程式開發環境;像微軟的Visual Studio、Borland Delphi等都算是整合式的開發環境IDE, Integrated Development Enviroment,讓程式的開發從設計一直到完成一個系統都在同一套軟體中完成,在這些開發環境中,程式設計反而成為整個系統開發中的一部分,扮演次要的角色。

3-7 延伸思考: ◎如何學習程式語言? 1. 了解語法涵義,資料型態,語法指令 2. 如何處理、測試、檢查、偵錯... 3. 解決問題的思維 ◎如何學習程式設計? 思考問題的本質,用甚麼方法解決!

4-0 本章摘要

• 資料庫系統的歷史

• 資料庫系統的定義

• 資料庫系統的組成

• 資料庫的安全

• 資料倉儲

• 資料庫技術的未來發展

4-1-1 資料的組織與涵義

基本觀念: 資料庫database可以定義為大量資料的集合,這些資料有各種不同的類別,用來描述真實世界的人、事與物。由於資料量大,必須透過有效的組織與管理才能使用,資料庫管理系統DBMS, DataBase Management System,就是用來管理資料庫的軟體系統。要讓資料庫運用於實際的工作與生活上,可以透過資料庫管理系統來開發應用程式。完整的應用程式能解決人類的各種問題,例如財物資訊的管理就可以逐漸發展成一個應用系統。

有組織與涵義的資料: 圖形的轉化、文字的組織

資料的組織與涵義: 資料合成為資訊,資訊的呈現,資料的組織

4-1-2 資料的層級

資料的層級: 電腦對於資料的處理是在各種不同的層次下進行的。各層次中資料的形式與組織各不相同,從較小的單元到大的聚集都有,可以看成是資料,例如位元、位元組、字元、紀錄、檔案、資料庫、資料超市、資料倉儲等。這些資料的組織都有特定的用途。

位元和位元組: 位元代表電子電路中傳送的0與1的信號,是資料最基本的單位。單一的位元很少用來表達有涵義的資訊,通常會把位元集合成位元組byte來表示有用的資訊。通常電腦系統會用標準化的對應表來將位元組轉換成資料項目,譬如ASCII表就可以把位元組對應到英文字母。

字元與字串: 位元組經過對應表的轉換會得到字元character. 任何可以從鍵盤輸入到電腦中的按鍵,都算是字元,例如0到9的數字,英文大小寫字母,標點符號等。有些字元是系統內定的,不見得所有的字元都在螢幕上看得到外觀。字元集合起來可形成字串string,可能代表人名,觀念,或是各種事物。在這個層次所看到的資料,其實都屬於基本的資料型態,譬如文字、數字等。

檔案: 資料紀錄的數量一多起來,就產生了管理上的問題;多筆資料紀錄可以用檔案將這些資料紀錄放置在一起。作業系統裡基本的資料單位就是檔案file,檔案的種類很多,不見得是用來儲存資料紀錄的。檔案代表比較多的資料的聚集,衍生出很多不同的格式。

資料庫: 資料庫是大量資料的集合,資料庫和檔案是有差異的;資料庫強調資料的共享、資料的一致性、資料使用的多元化與資料安全,這些需求無法純粹透過檔案系統來完成。資料庫系統建立在檔案系統之上,資料仍舊儲存在檔案中,只是儲存和處理的方式是依照資料庫的要求來設計的。各種層級的資料都需要某種軟體系統來管理,所以檔案需要檔案系統來管理,而資料庫則要由資料庫系統來管理。

資料倉儲與資料超市: 資料庫系統支援各種線上的作業,在各種應用中發揮了資料處理自動化的功能。資料庫普及以後,人們發現資料的使用可以進一步地精緻化例如連鎖商店經營的分析,可能要把歷史資料也拿出來分析,而且資料應該來自各連鎖店,而不是單一的商店。在新需求的推動下,出現了資料倉儲data warehouse的技術,資料倉儲建立在資料庫的基礎上,以所追求的事實為導向,彙集相關的資料,包括歷史資料在內。資料超市data mart伴隨著資料倉儲而發展,主要功能是將資料倉儲內的資料再分門別類,支援更專門的用途。

4-1-3 資料來自何方? 往何處去?

思考問題: 資料到底來自何方? 儲存在哪裡? 可以傳遞到甚麼地方? 對於不同的層級資料而言,這些問題都有不同的答案。

資料的處理與流向: 以字元和字串來說,可能由程式中的指定語法將字元或字串指定給程式變數,然後利用檔案的輸出輸入指令把字元或字串寫入檔案中。以資料倉儲而言,裡頭的資料可能來自網路上其他的資料庫,所以資料從網路上傳輸過來,依照資料倉儲的定義送往儲存裝置。各種層級的資料之間有很密切的關係;相同的資料用不同的方式來組合和包裝,會形成各種不同層級的資料。中間的處理依賴各種軟體程式與硬體的儲存設備來完成,有的還要靠網路的軟硬體來幫忙。

延伸思考: 以後大家遇到了任何資料,都可以判斷該資料來自哪一個層級? 是從哪兒來的?(如何產生的?) 會送往何處? (儲存在那裡或被誰所用?)

4-1-5 資料倉儲與資料超市

位元和位元組: 位元代表電子電路中傳送的0與1的信號,是資料最基本的單位。單一的位元很少用來表達有涵義的資訊,通常會把位元集合成位元組byte來表示有用的資訊。不同的組合可以對應到不同的資料項目data item. 資料項目是一種比位元層次要高的資料單位,可能代表一個字母或一個數字。 通常電腦系統會用標準化的對應表來將位元組轉換成資料項目。

檔案: 資料紀錄可能記載了很多人事資料,形成多筆資料紀錄,這時候可以用檔案將這些資料紀錄放置在一起。使用過電腦的人都知道作業系統裡基本的資料單位就是檔案file,檔案的種類很多,不見得是用來儲存資料紀錄的。

資料庫: 資料庫是大量資料的集合,資料庫和檔案是有差異的;資料庫強調資料的共享、資料的一致性、資料使用的多元化與資料安全,這些需求無法純粹透過檔案系統來完成。資料庫系統建立在檔案系統之上,資料仍舊儲存在檔案中,只是儲存和處理的方式是依照資料庫的要求來設計的。

資料倉儲與資料超市: 資料的使用可以進一步地精緻化;可能要把歷史資料也拿出來分析,資料倉儲建立在資料庫的基礎上,以所追求的事實為導向,彙集相關的資料,包括歷史資料在內。資料超市data mart伴隨著資料倉儲而發展,主要功能是將資料倉儲內的資料再分門別類,支援更專門的用途。一般來說資料倉儲的資料量最大。

4-1-4 資料庫系統的歷史

4-2-1 資料庫系統與檔案系統

基本觀念: 資料庫系統可以看成是資料庫、資料庫管理系統與應用系統的組合;檔案系統雖然也具有組織與儲存資料的功能,和資料庫系統比較起來,卻有一些根本的差異。檔案本身缺乏結構化的資料組織能力。

比較的項目	檔案系統	資料庫系統
與作業系統的關聯	常附屬其中	建立於作業系統之上
所支援的介面與系統	程式語言或指令介面	應用系統與資訊系統
資料的組織	平坦	結構化
資料的單位	位元或字元的集合	紀錄與資料結構化的集合
價格	較低	較高
系統的特徵與結構	介面較不親和但結構比較簡單	介面親和但結構比較複雜

4-2-2 資料庫系統的特徵

1. 資料庫提升了資訊共享的效率 2. 降低資料的重複性3. 使相同的資料足以支援多元化的應用 4. 提升資料的安全性

檔案系統無法提供的功能: 細微的資料控管、資料的多人共用共享機制

4-2-3 資料庫系統與其他系統

4-3 資料庫系統的組成與架構

資料庫系統 vs. 檔案系統: 資料庫系統在很多場合下,必須仰賴檔案系統的支援。資料庫在儲存裝置中主要是以檔案的形式存在,在使用上異於文件檔案或是程式檔案。資料庫管理系統賦予資料庫檔案特殊的結構,使其適用於大量資料的存取、查詢,應用系統則為這些資料注入了涵義與外觀。

資料庫系統的功能性架構:

理論模型化	功能性層次	功能性組成
應用系統資料模型	應用系統層	使用者介面、應用程式介面與查詢語言
程式模型	執行層
資料庫模型		交易異動處理管理員
		資料庫核心
	表示層	資料管理員
儲存模型	儲存層	儲存管理員

資料庫系統的特性: 資料庫系統在縝密的分層分工的架構下,讓大量的資料以多元化的面貌呈現給使用者,配合應用系統的需求,做有彈性的運用。資料庫系統同時供多人存取使用的資料單位可以是一個很小的紀錄record,有異於一般的檔案系統以整個檔案作為分享的單位。因為有此特性,資料庫系統提升了資料的可用性availability,讓很多人能同時使用資料庫,不必擔心衝突的發生。

4-4 從市場上的產品系統來看料庫系統的發展

市場上資料庫管理系統的種類: 市場上資料庫管理系統的種類非常多,但是每一種產品的適用對象會有一些差異。以關聯式資料庫管理系統來說,大型用戶與小型用戶會採用的資料庫管理系統就有很大的差異。例如Oracle, Sybase與informix等屬於大型用戶常使用的關聯式資料庫管理系統。Microsoft Access或者是早期的Visual FoxPro與dBase就比較偏向小型用戶會採用的資料庫管理系統。在價格上往往有很大的差異。

Oracle: 公司於1977年建立,當時的名稱是Software Development Laboratories,而且市場上還沒有商業化的關聯式資料庫管理系統的產品。Oracle公司的名稱正式確立以後,隨後就發展出第一個進入市場的關聯式資料庫系統。

Oracle的發展: 雖然Oracle開始的時候是以關聯式資料庫系統起家的,後來的發展卻變得越來越多元化,包括資料庫的開發與管理工具、查詢與分析工具、資料倉儲與資料採擷的軟體等。這些軟體工具都能和Oracle的資料庫系統整合在一起。在商業應用方面, Oracle提供了ERP, CRM等企業資訊系統的產品,以及商業智慧Business Intelligence的工具。

Sybase: 公司於1984年成立於美國加州,創辦人為Mark Hoffman和Bob Epstein. 1984年Sybase第一代SQL Server 10問世,將關聯式資料庫管理系統運用於線上交易處理OLTP及主從架構Client-Server architecture的領域,引進多緒multi-thread的技術,運用了儲存程序stored procedure、遠端程序呼叫RPC、觸發元Trigger等技術。Sybase最有名的發展是在美國華爾街銀行市場的高佔有率,1995年Sybase合併Powersoft,成為全球第六大的軟體供應商。目前已被SAP公司併購。

微軟公司提供的資料庫管理系統的軟體: Microsoft Access與Microsoft SQL Server都是微軟公司提供的資料庫管理系統的軟體。Microsoft Access屬於Microsoft office軟體的一部分,比較屬於一般個人用的資料庫軟體,微軟公司曾經推出的Small business pack的應用軟體就是以Access為底下的資料庫管理系統。Microsoft SQL Server屬於比較高階的資料庫管理系統的軟體,有跟Oracle和Sybase等資料庫大廠競爭的味道,在資料庫軟體的市場上也有很高的佔有率。

4-5 資料庫系統的應用與未來的發展

資料庫技術未來發展的關鍵: 資料模型的進化、與相關科技的整合、與其他資訊系統的整合與互通

資料模型的進化: 物件導向資料模型突破了關聯式資料模型在描述複雜性資料的限制。綜合物件導向與關聯式二者特性的資料模型,同時繼承優點,又能取得關聯式資料庫系統的市場優勢。可以預期各類資料模型的持續演化及交互影響,以及配合新科技所做的調適。

與相關科技的整合: 資料庫的應用廣泛,與其他科技的關係密切;網路技術衍生出分散式資料庫系統,多媒體資料促成了多媒體資料庫系統的發展;硬體技術的進步增加了超大型資料庫系統的效率與可行性。

與其他資訊系統的整合與互通: 隨著網際網路的普及,以及資料庫管理系統市場的多元化;未來的資訊系統會在異質性的情況下合作,因此也產生了整合的需要。雲端技術與大數據big data的發展也要仰賴資料庫的技術。

4-6 延伸學習

1. 多大量的資料稱得上資料庫? 當資料量變大的時候,以使用與效率來評估

2. 資料庫系統的種類? 從功能與應用來看...

3. 如何學習資料庫系統? 書上的原理描述觀念與方法;實務上如何運用與管理才是重點