Abstract – On the Criteria To Be Used in Decomposing Systems into Modules

        這篇文章主要在敘述如何透過模組化一個系統,使得其在開發上更有彈性與快速,且在開發階段可以更加容易地理解系統各部分,這篇文章中所謂的『模組化』是在作者所提出的幾項原則下對一個系統做分解,搭配作者提出的例子-KWIC index (Key Word In Context index)的兩種分解方式,來理解非傳統的分化相較於傳統的方式有什麼樣的優點。
        近期(根據文章著作年代,應該是1972)的模組化程式設計發展,主要著重在程式碼撰寫的技巧和組譯技術的改進,然而對於多數的系統開發而言,最常使用的則是高度模組化程式。
        對於模組化程式設計,我們期望可以達到三個效果:
(1)   分工及縮短開發時程
(2)   彈性的功能調整
(3)   更容易地了解整個系統
        模組』的概念,並不是指『子程序、函式、方法』,而是指一個工作分配單元,而『模組化』則是指各個模組運作之前所需要考量的設計決策(Design Decision),主要是以系統階層的設計為決策方向,也就是思考有哪些決策會影響超過一個模組。
        文中以KWIC index為例,提出了兩種模組化的方法,第一種模組化方式將系統切割成五個模組:InputCircular ShiftAlphabetizingOutputMaster Control,其中前四個模組是有使用順序的,第五個模組主要用來控制其他四個模組與處理錯誤訊息、空間配置等等;第二種模組化方式將系統切割成六個模組:Line StorageInputCircular ShiftAlphabetizerOutputMaster Control,其中前五個模組是針對各自獨立的設計決策做切割,而沒有前後的使用順序,第六個模組同樣是運來控制其他模組。
        首先比較這兩個模組化方式,兩者的差異最主要是在切割工作的方法,雖然兩種模組化方式都相對的減低了程式的撰寫與管理,但是作者認為第一種模組化方式太過於保守,而第二種模組化方式則在許多Class Project中被成功的應用。
        作者提出了一些可能在不同情況下影響設計決策的變動因素:輸入格式是否將每一行都存在核心中(stored in core)是否將四個位元包裝成一個字組(word)是否要為circular shift建立索引是否要照字母順序建立表格,這些變動都可能會受限於某個模組。
        在某一些版本的系統中還會額外加入符號表(symbol table)模組,這個模組會在Line Storage中被使用到,但是對系統來說是不會察覺到的。
        個別開發(Independent Development)的角度來看,第一種模組化方式的介面(即各個模組)太過於複雜,第二種模組化方式的介面相對上較抽象,這使得後者在決策與開發上會比較容易進行,這也就是模組化設計中強調的『抽象化』。
        對於模組的理解(comprehensibility),我們有必要去了解alphabetizercircular shifterinput 三個模組,作者認為『要了解一個系統,必須從系統整體來看』這個觀點,在第二種模組化方式上並不成立。
        經過以上的例子與比較,作者提出了一項準則,第一種模組化事實上是按照系統的運作流程去進行切割,因此他認為這樣的模組化方式並不完善,而第二種模組化方式並非照著運作流程切割,而是採用了『資訊隱藏(Information hiding)為準則,針對各個設計決策去分割系統為多個模組單元(介面),有點類似物件導向程式設計方法中的『封裝』,對模組而言,彼此之間不會知道或影響其他模組的內部運作方法與設計考量。
        對於Circular Shift模組,我們還可以為List指定一個順序,使得程式在三種情況下可以更有效率:最新定義的circular shift所代表的行號都存在表格中、沒有任何的list被引用兩次、存在一個額外的函式讓我可以得知從原始行號shift多少次,在規定了順序以後,我們不必去更動定義,就可以提供更多的資訊。
        其他各模組可能隱藏的資訊例如:系統內部的資料結構、模組或副程式的呼叫順序、作業系統佇列中的控制區塊格式、字元編碼、字母順序、相似資料、特定項目會處理的資料序列…等等。
        考量程式的效率與實作時,因為第二種模組化方式的各介面可能在系統運作中不同的階段內被呼叫,如果呼叫的序列太複雜,會產生重複切換模組的負擔(repeat switching overhead),相形之下第一種模組化方式的各個模組只在特定階段被呼叫使用,因此較無這個問題,如果要改進這個負擔,在多數的例子中,組譯器會在副程式中插入一些程式碼,其他也有在程式中使用高效率切換方法或是高度專門化的例子。
        模組化的技巧在編譯器或直譯器中也有所應用,因為在許多的編譯器或直譯器中,有許多功能模組的實作也採用了資訊隱藏的方式,例如暫存器操作、搜尋演算法、直譯規則等等的決策(或理解為實作方式),這些決策會以模組化方式實作,並隱藏這些決策的實作方法。
        從第二種模組化方式的例子中,我們還可以看到介面之間具有『階層結構』(Hierarchical Structure),作者對系統模組化後具有階層結構提出了幾個優點,一個好處是可以簡化部分的系統實作,因為這些部份的功能可以由較低層次的模組提供,類似物件導向中『繼承』的概念,另一個則是可以簡化較高層次的設計,但是仍然保有可用性與有效性,事實上,第一種模組化方式也可以具有階層結構,階層結構乾淨分割是系統結構中兩個需要但獨立的性質。
       總結作者的觀點,他建議在進行一連串困難的或是變動性大的設計決策時,模組化需要考量到的重點是對其他模組的資訊隱藏,因為在多數的情況下,模組化過程並不會與系統運作流程密切吻合,而設計決策的時間也會超過執行的時間,所以若要有效率的實作出模組化系統,我們不應該去思考一個模組中要有幾個功能或副程式,而是去思考如何讓個副程式與主程式在不同模組間能夠良好的組合。

Elevator Scheduling (1)

下午去吃飯回來搭電梯時,因為電梯剛好在二樓,我就直接按鈕進去了

當我到了六樓,一出來就發現有人在等電梯,我突發奇想,思考一個可能性,就是會不會他們其實剛好正要按電梯按鈕,但是就只是差那麼個幾秒鐘,導致我先搶到電梯了?

那麼假如今天剛好相反過來,我慢了一點,電梯明明在二樓,我就只能眼睜睜看著它先到六樓再下來載我嗎?

我開始思考延遲電梯反應時間的可能性

讓可能只是誤差非常小的時間範圍內,可以讓慢了一點的我還是可以先搭到電梯,然後到了六樓以後再換六樓的人搭下來,結果光是在Word上邊寫邊想就花了我兩個小時左右的時間,以下是我的思考結果,之前在圖書館搭電梯就曾經對三部電梯的調度提過問題,可惜當時沒有那麼無聊好好思考和紀錄,現在就可以當參考了

有聽過電梯演算法 (Elevator Algorithm),還有個有名的人物 Theresa Christy,會不會其實這個問題早就克服了呢?

情境:目前電梯正位於1F,當一位使用者正準備按下電梯向上按鈕進入電梯,由於6F亦有乘客愈搭乘電梯下樓,假設兩造於相差半秒內的時間按下電梯按鈕,事實是6F乘客較晚按下按鈕,則電梯可能因為反應時間快速,使得收到6F訊號以後立即向上,1F乘客需等待6F使用者下樓以後方可上樓

相關數據假設:
按鈕時間差 0.5 sec
電梯反應時間 0.1 sec (電梯接收到按鈕訊號並判斷該打開門讓1F乘客進入或是上樓的處理時間)
電梯自 1F  6F運行時間 15 sec
電梯門開門或關門時間 2 sec
乘客進或出電梯時間(在此假設兩樓層各只有一位乘客,且在進入電梯後立刻按下樓層按鈕) 2 sec
1F乘客 P1
6F 乘客 P6
電梯完成運送兩位乘客抵達愈前往樓層總耗時
= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開
= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間
= 0.1 + 15 x 3 (上樓2次,下樓1次) +  2 x 5 (*1) + 2 x 4 (兩位乘客各進與出1次) 
= 63.1 sec
乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層*2):
P1 等待時間
= 電梯運行至6F + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + P1進出總時間 + 電梯於1F開關門總時間 + 電梯運行至6F + 電梯於6F 開門時間 (*3)
= (15 – 0.4 (*4))+ 2 x 2 (開關各一次) + 2 x 2 (6F進,1F出) + 15 + 2 x 2 (1F進,6F出) + 2 x 2 (開關各一次) + 15 + 2
= 62.6 sec
P6等待時間
= 電梯反應時間 + 電梯運行至6F時間 + 電梯於6F開關門總時間 + P6進出總時間 + 電梯運行至1F + 電梯於1F開門時間
= 0.1 + 15 + 2 x 2 + 2 x 2+ 15 + 2
= 40.1 sec
平均等待時間 = (63 + 40.1) ÷ 2 = 51.55 sec
改善想法:由以上討論可發現,電梯反應時間對於一位乘客的等待時間影響並不是很大,所以假如增加電梯反應時間至1 sec,企圖使電梯可在較慢的乘客也按下電梯按鈕以後,再做出判斷(因為較慢的乘客會是在0.5sec時按下按鈕,電梯則是在1sec時完成判斷),如此一來,便可以於第一次由1F運行至6F時服務1F乘客抵達6F
改善後電梯完成運送兩位乘客抵達愈前往樓層總耗時
= 第一位乘客按下按鈕 至 送最後一位乘客抵達樓層並開啟門使其離開
= 電梯反應時間 + 電梯總運行時間 + 電梯開關門總時間 + 乘客進出電梯時間
= 1 + 15 x 2 (上下樓各1次) +  2 x 5 (*5) + 2 x 4 (兩位乘客各進與出1次) 
= 49 sec
乘客等待時間(從乘客按下按鈕開始至乘客抵達愈前往樓層):
P1 等待時間
= 電梯反應時間(*6) + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F時間 + 電梯於 6F 開門時間
= 0.5 + 2 x 2 + 2 x 2 + 15 + 2
= 25.5 sec
P6等待時間
= 電梯反應時間 + 電梯於1F開關門總時間 + P1進出總時間 + 電梯運行至 6F 時間 + 電梯於6F 開關門時間 + P6 進出總時間 + 電梯運行至1F 時間 + 電梯於 1F 開門時間
= 1 + 2 x 2 + 2 x 2 + 15 + 2 x 2 + 2 x 2 + 15 + 2
= 49 sec
改善後平均等待時間 = (25.5 + 49) ÷ 2 = 37.25 sec
 ———————————————————————————————————— 
*1  第一次抵達6F,開與關各一次,接著抵達1F,開與關各一次,第二次抵達6F,僅計算開門時間,故計一次,所以總共是5次
*2 與作業系統討論的不同,這裡的討論包含了運送乘客時間(CPU Turnaround Time)      
*3 P1因為較慢按下按鈕,此時電梯已經完成反應,因此P1無須等待電梯反應時間       
*4 電梯開始移動是第一個乘客按下之後的0.1秒,從這0.1秒到第二位乘客按下按鈕間的0.4秒,電梯已經移動了一段時間,所以要從電梯運行至6F的15秒鐘扣掉這0.4秒
*5 因為電梯會判斷成應該先在1F開門載客,所以於1F開與關各一次,抵達6F開與關各一次,第二次回到1F時開門一次
*6 對於P1而言,他按下按鈕的時間是電梯反應時間開始之後過了0.5秒,因此實際上他的等待時間只有0.5秒

Shell 內建命令 (Shell Built-in Command)

Shell Built-in Command 是指與 shell code 寫在一起編譯成,屬於 shell 這個 program 本身功能的指令,在Windows中稱為 internal command,例如:cd, exit, umask, alias 等等,這種內建在 shell 程式碼內的功能無法在 shell 中使用 execv() 去呼叫外部程式的方式執行


int main()
{
    …
     if( strcmp(cmd, “cd") == 0)
            cd(pathname);
    …
}

void cd(char *pathname)
{ … chdir(… pathname …) … }


這種命令的執行速度會比 external program 快,因為省去了 program loading 這段 overhead,但是因為這些功能的程式碼是寫在 shell 中,所以如果修改或更新了任何功能的程式碼,就必須將整個 shell program 重新 compile 一次

那麼是什麼樣的命令適合實作成 builtin 呢?

舉個例子來說明,像是 cd 這個命令,用途是在不同的目錄間移動,實作方式大致上是使用 chdir() 這個函式,不過我們討論的不是實作的方法,而是這個函式的運作方式,對大部分的作業系統而言,當一個 Process 開啟一個檔案(目錄也是一個檔案)時,OS會為該 Process 建立他自己的 Process Table,其中就包含了現行工作目錄的資訊,而 chdir() 就是用來讓呼叫它的 Process 在執行期間移動自己的現行目錄

我們知道,cd 這個命令主要是用來改變目前的工作目錄,而這個工作目錄是屬於目前這個 Process 自己知道的資訊,其他 Process 不會知道也不需要知道

當一個 Process 呼叫一個 function ,這個 function 基本上只會對呼叫它的 Process 有作用

如果我們把 cd 實作成一個外部程式,也就是說,寫一個命名為 cd.c 的 program 並且編譯後程式名稱為 cd,當然,cd.c 中呼叫了 chdir() 這個函式,那麼當 shell process 使用 execv() 呼叫了這個外部程式後,這個外部程式便開始執行,注意!因為 cd 也是一個程式,根據對 Process 的定義,cd 被執行後,也會是一個 Process,也就是說,現在同時有兩個不同的 Process 在系統中執行,又據前一段所言,因為呼叫 chdir() 的 Process 是 cd,所以 chdir() 只會對 cd process 有作用,也就是會切換 cd process 的工作目錄,如此一來,shell 的工作目錄還是維持不變

因此如果我們希望使用者在 shell 輸入 cd 以後,可以改變 shell 的工作目錄,則必須在 shell process 中呼叫 chdir() ,這就是之所以要將 cd 實作成內建命令的原因

像是 umask(改變建檔時檔案權限遮罩)、exit (呼叫 exit() 終止 shell 這個 Process)、alias…都是差不多的原因,因為建檔時對檔案的權限設定使用的遮罩是個別 process 的東西,因此需要在各Process 內使用;因為要結束 shell 自己這個 process,是呼叫 exit(),如果採用呼叫外部程式,那只會結束那個外部的程式 (那個程式被執行起來後用來結束自己 ……. ~"~? )

總結一下,由這些例子可知,要實作為 built-in 的基本概念就是『這個命令只會對使用它的 process 本身有影響』,像是 ls,純粹只是對一個目錄進行開啟、讀取與列印內容,對使用這個命令的 Process 並沒有影響;像是 mv,也只是對一個檔案進行移動,對 Process 的參照不會有影響,所以這些命令沒有必要做成內建命令

環境變數 Path 的應用

(小兒科篇,單純覺得這樣應用很有趣 !!! ^ω^)

相信大部分的人都寫過 Java,在安裝完 JDK 以後,都一定要做一件事情,也就是到我的電腦去把 javac.exe 和 java.exe 這兩個執行檔所在的目錄 bin 這個相對路徑加入系統的環境變數中,甚至有些系統中會自動幫你加入,所以很多人只知道要這麼做,好讓你在使用命令提是字元編譯和執行 java 程式的時候可以直接輸入 java 和 javac 對原始碼進行處理,不過其實這個 Path 的用途最主要是用來讓系統搜尋 “指令程式" 用的。

一般我們在命令提示字元輸入的指令,大部分都是作業系統自動在所有 Path 變數中指定的目錄下尋找與輸入的指令名稱相同的可執行檔或批次檔,並執行它工作,所以 Java 的環境變數才會要求要把 javac.exe 和 java.exe 所在的目錄 bin (這個名稱的目錄底下一般都存放可執行檔)路徑給加入到 Path 中。

根據這樣的道理,我們可以在任何一個目錄中開一個資料夾


接著複製這個目錄的絕對路徑
把它加入環境變數中 (注意要以 “;" 分號隔開,在 Linux 系統中是用 “:" 冒號)
然後我們可以編寫一個 C 程式,經過編譯以後產生一個執行檔,把執行檔放到這個資料夾底下
接著我們就可以開啟命令提示字元,直接輸入 “指令" (執行檔程式名稱) 
OS:感覺很像是寫系統程式來擴充系統的功能,不過我想真正的系統程式應該不是這麼簡單的吧?! 哈哈哈!!! XDDDDDDD



兩岸計算機科學用語對照 (sorted by English)

大陸用字 台港澳用字 英文
算法 演算法 algorithm
匯編 組合 assembly
激活 啟用 activation
數組 陣列 array
字節 位元組 byte
比特 位元 bit
總線 匯流排 bus
二叉 二元 binary
計算機 電腦 computer
調用 呼叫 call
芯片 晶片 chip
數據 資料 data
數據庫 資料庫 database
數據鏈路 資料鏈結 data link
調試器 除/偵錯工具 debugger
默認 預設 default
數碼 數位 digital
硬盤 硬碟 disk
差錯 誤差 error
文件流 檔案流 file stream
函數 函式 function
gate
哈希表 雜湊表 hash table
頭文件 標頭檔 header file
硬件 硬體 hardware
注入 植入 injection
集成電路 積體電路 integrated cirtuit
擴展卡 介面卡 interface card
接口 介面 interface
互聯網 網際網路 internet
內核 核心 kernel
鏈表 鏈結串列 linked list
線性表 線性串列 linear list
巨集 macro
主板 主機板 mother board
內存/存儲 記憶體 memory
菜單 目錄 menu
移動 行動 mobile
網絡 網路 network
正則 正規 normalize
溢出 溢位 overflow
操作 運作 operation
面向對象 物件導向 object-oriented
操作系統 作業系統 operating system
分組 封包 packet
概率 機率 possibility
程序 程式 program
程序員 程式設計師 programmer
編程 程式設計/寫程式 programming
過程 程序 procedure
進程 行程 process
指針 指標 pointer
物理層 實體層 physical layer
隊列 佇列 queue
註冊表 登錄檔 register
寄存器 暫存器 register
遠程 遠端 remote
正則表達式 正規表示式 regular express
服務器 伺服器 server
序列 數列 sequence
軟件 軟體 software
堆棧 堆疊 stack
子程序 副程式 subroutine
線程 執行緒/緒程 thread
偽代碼 虛擬碼 pseudo code
遍歷 走訪 traverse
跳轉 路徑轉換

截取自-左飛<程式揭秘-從C/C++程式碼探索電腦系統的運作原理>書中一文『卓越的程式設計之道』

社會上也有很多像"XXX電腦"的培訓機構那樣專門開設一些如 “Java軟體工程師"、".NET軟體工程師" 等的課程,其目的就是為了讓受訓者能夠掌握在某些環境下進行軟體發展的技能。軟體發展或者編寫程式碼的確是一項技術,而程式設計則是一門藝術。技術和藝術的區別不言而喻!其結果是這類從業者,即使她們擁有了一定的程式設計經驗,但大多數也只是在 “軟體工廠" 中做些類似 “零件組裝" 的工作。這就是中國和世界的差距!中國沒有微軟(Microsoft),沒有谷歌(Google),也沒有甲骨文(Oracle)。當然,或許你也能羅列出幾個你心目中的民族科技龍頭企業,但相對於這些巨頭而言,中國的企業仍然不能與之相提並論。這些公司之所以能夠在世界範圍內呼風喚雨,最重要的是他們有著自己的核心技術和無窮的創新能力!
千萬不要把軟體產業和IT產業混為一談。正確的說,軟體產業應當是IT產業的一部分,而且是處在技術"下游"的那部分!中國的 “軟體工廠"也只能用別人的 Visual Studio 或者 Eclipse 進行著大量重複而簡單的生產,即使是C、C++、C#或者是 Java 這些耳熟能詳的程式設計語言也沒有一個是中國人發明的。專科水準再稍加訓練就足以勝任軟體工廠的實際邊也程式碼工作了。

先有雞還是先有蛋?Compiler vs Program

這學期準備要修 編譯器設計,我想到一個之前逢甲資工的老頭問我的一個問題,同時這也是他們編譯器老師問的問題:

先有 Compiler 還是先有程式?

其實同樣的問題也出現在作業系統上面,因為作業系統也是由程式所設計出來的,例如UNIX就是用C語言所編寫出來的。

針對這個問題我找了為基百科和一些網頁資料,我認為應該是先有程式,才有編譯器,因為去看電腦發展的歷史,很早期的電腦(真的是很早期),或是更精確一點說是計算機,其實是沒有程式的,是以純機械原理模擬出運算能力,而晶體管(transistor)發明以後,機械進入的電子的時代,電子電機工程開始興起,也就產生了數位系統。

第一次是聽補教界的名師洪逸在課堂上說的,後來在<Pirate of Silicon Valley>中看到比爾蓋茲和賈伯斯他們真的是這樣寫程式而印象深刻,後來發展出的打洞卡(Punch Card),電腦先輩們都必須利用打卡的方式控制機器,而這也就是最早的程式語言,也就是為什麼影片中兩位大老會想要說服當時的電腦大廠接受他們開發的作業系統,作業系統本身也是程式,也是由程式語言創作出來的,基於這個概念,因此編譯器也是後來才有的。

另一個可以支持這個說法的還有一點,那就是高階程式語言是在後期才出現的,早期的電腦由打卡控制提升到指令控制時,幾乎都是接近於機器碼的組合語言(Assembly Language),而高階語言經過編譯器編譯以後都是轉譯成組合語言,再轉譯成機器碼,這也就是為什麼組合語言比較難學,卻也是最直接能與硬體做互動的原因。