基本內(nèi)容
埃德斯加·狄克斯特拉 ——最先察覺“goto有害”的計算機(jī)科學(xué)大師 首屆計算機(jī)先驅(qū)獎獲得者中有一位荷蘭的計算機(jī)科學(xué)家埃德斯加·狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因最早指出“goto是有害的”以及首創(chuàng)結(jié)構(gòu)化程序設(shè)計而聞名于世。事實(shí)上，他對計算機(jī)科學(xué)的貢獻(xiàn)并不僅僅限于程序設(shè)計技術(shù)。在算法和算法理論、編譯器、操作系統(tǒng)諸多方面，狄克斯特拉都有許多創(chuàng)造，作出了杰出貢獻(xiàn)。1983年，ACM為紀(jì)念Communications of ACM創(chuàng)刊25周年，評選出從1958—1982年的四分之一個世紀(jì)中在該雜志上發(fā)表的25篇有里程碑意義的論文，每年一篇，狄克斯特拉一人就有兩篇入選，是僅有的這樣的兩位學(xué)者之一(另一位是英國學(xué)者C．A．R．Hoare，也是計算機(jī)先驅(qū)獎獲得者)�！ 〉铱怂固乩�1930年5月11日生于荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學(xué)家和發(fā)明家，曾擔(dān)任荷蘭化學(xué)會主席。他母親則是一位數(shù)學(xué)家。狄克斯特拉的少年時代是在德國法西斯占領(lǐng)軍的鐵蹄下度過的。由于食物短缺，他被送到鄉(xiāng)下他父親的一個朋友那里去。納粹德國投降后，1945年7月，十分虛弱的狄克斯特拉才和家人重新團(tuán)聚。狄克斯特拉原打算學(xué)法律，畢業(yè)后到聯(lián)合國工作，為維護(hù)世界和平服務(wù)。但他中學(xué)畢業(yè)時，數(shù)理化成績都特別好，因此他父親說服了他，1948年進(jìn)萊頓大學(xué)學(xué)習(xí)數(shù)學(xué)與物理。在學(xué)習(xí)理論物理的過程中，狄克斯特拉發(fā)現(xiàn)這個領(lǐng)域中的許多問題都需要進(jìn)行大量復(fù)雜的計算，于是決定學(xué)習(xí)計算機(jī)編程。1951年，他自費(fèi)赴英國參加了劍橋大學(xué)舉辦的一個程序設(shè)計培訓(xùn)班，學(xué)習(xí)在EDSAC(Electronic Delay Storage Automatic Calculator，這是由另一位首屆計算機(jī)先驅(qū)獎獲得者威爾克斯主持設(shè)計與開發(fā)的世界上第一臺存儲程序式電子計算機(jī))上的編程方法，這使他成為世界上第一批程序員之一。第二年，阿姆斯特丹數(shù)學(xué)中心了解到這一情況，擬聘他為兼職程序員。狄克斯特拉開始時有些猶豫，因?yàn)槭澜缟袭?dāng)時還沒有“程序員”這一職業(yè)。數(shù)學(xué)中心的計算部主任、Algol語言的設(shè)計者之一、荷蘭的計算技術(shù)先驅(qū)維京格爾藤(A．van Wijingaarden，1916—1987，因在設(shè)計Algol 68時，為解決上下文有關(guān)性這一難題而提出了一種具有很強(qiáng)描述能力的新的文法，稱做二級文法又稱W文法而聞名。他是1986年計算機(jī)先驅(qū)獎獲得者之一，也曾對另一位首屆計算機(jī)先驅(qū)獎獲得者N．Wirth的研究產(chǎn)生過影響)對他說，目前程序設(shè)計雖然還沒有成為學(xué)科，不被重視，但既然計算機(jī)已經(jīng)有了，正處于開創(chuàng)階段，你未來就有可能使程序設(shè)計成為一個受人尊敬的學(xué)科。這段話說動了狄克斯特拉，使他接受了這個職位，而且越干越有興趣，這樣，他在第二年就結(jié)束了在萊頓大學(xué)的學(xué)業(yè)，成為數(shù)學(xué)中心全日制的工作人員，從此進(jìn)入計算機(jī)領(lǐng)域，并且正如維京格爾藤所預(yù)言的那樣，逐漸成為該領(lǐng)域的知名專家，創(chuàng)造出了許許多多的“第一”�！ �1956年，他成功地設(shè)計并實(shí)現(xiàn)了在有障礙物的兩個地點(diǎn)之間找出一條最短路徑的高效算法，這個算法被命名為“狄克斯特拉算法”，解決了機(jī)器人學(xué)中的一個十分關(guān)鍵的問題，即運(yùn)動路徑規(guī)劃問題，至今仍被廣泛應(yīng)用，被認(rèn)為是利用“貪心法”(greedy method)設(shè)計算法的一個成功范例�！ �1959年，在數(shù)學(xué)中心將他們原先的ARMAC計算機(jī)進(jìn)行升級的過程中，狄克斯特拉設(shè)計了一種處理程序，成功地解決了“實(shí)時中斷”（real-time interrupt)問題。狄克斯特拉的博士論文就是以此為課題完成的，并在阿姆斯特丹大學(xué)通過論文答辯而獲得博士學(xué)位�！ �1960年8月，Algol 60文本推出剛剛半年多，狄克斯特拉和他在數(shù)學(xué)中心的同事仲納凡爾特(J．A．Zonneveld)一起就率先實(shí)現(xiàn)了世界上第一個Algol 60編譯器，比歐美其他各國學(xué)者實(shí)現(xiàn)Algol 60早一年還多。這一成就引起各國計算機(jī)學(xué)者的驚嘆，并因此奠定了狄克斯特拉作為世界一流計算機(jī)學(xué)者在科學(xué)界的地位�！ �1962年，狄克斯特拉離開數(shù)學(xué)中心進(jìn)入位于荷蘭南部的艾恩德大學(xué)(Eindhoven Technical University)任數(shù)學(xué)教授。在這里，X8計算機(jī)的開發(fā)，設(shè)計與實(shí)現(xiàn)了具有多道程序運(yùn)行能力統(tǒng)——THE Multiprogramming System。THE是艾恩德霍芬技荷蘭文Technische Hoogeschool Eindhoven的詞頭縮寫。狄克THE這個系統(tǒng)中所提出的一系列方法和技術(shù)奠定了計算作系統(tǒng)的基礎(chǔ)，尤其是關(guān)于多層體系結(jié)構(gòu)、順序進(jìn)程之間的斥機(jī)制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出并為以后的操作系統(tǒng)如UNIX等所采用的。為了在單處理機(jī)的情況下確定進(jìn)程(process)能否占有處理機(jī)，狄克斯特拉將每個進(jìn)程分為“就緒”(ready)、“運(yùn)行”(running)和“阻塞”(blocking)三個工作狀態(tài)。由于在任一時刻最多只有一個進(jìn)程可以使用處理機(jī)，正占用著處理機(jī)的進(jìn)程稱為“運(yùn)行”進(jìn)程。當(dāng)某進(jìn)程已具備了使用處理機(jī)的條件，而當(dāng)前又沒有處理機(jī)供其使用，則使該進(jìn)程處于“就緒”狀態(tài)，當(dāng)運(yùn)行進(jìn)程由于某種原因無法繼續(xù)運(yùn)行下去時，就停止其占用處理機(jī)，使之進(jìn)入“阻塞u2019u2019狀態(tài)，待造成其退出運(yùn)行的條件解除，再進(jìn)入“就緒”狀態(tài)。而對系統(tǒng)中所有同時運(yùn)行的進(jìn)程之間所存在的相互制約的同步(synchronization，指為了避免錯誤，在一個進(jìn)程訪問共享數(shù)據(jù)時，另一個進(jìn)程不訪問該數(shù)據(jù))和互斥(mutually-exclusive，指兩個進(jìn)程不能同時在一個臨界區(qū)中使用同一個可重復(fù)使用的資源，諸如讀寫緩沖區(qū))兩個關(guān)系，狄克斯特拉巧妙地利用火車運(yùn)行控制系統(tǒng)中的“信號燈”(semaphore，或叫“信號量”)概念加以解決。所謂信號燈，實(shí)際上就是用來控制進(jìn)程狀態(tài)的一個代表某一資源的存儲單元。例如，P1和P2是分別將數(shù)據(jù)送入緩沖B和從緩沖B讀出數(shù)據(jù)的兩個進(jìn)程，為了防止這兩個進(jìn)程并發(fā)時產(chǎn)生錯誤，狄克斯特拉設(shè)計了一種同步機(jī)制叫"PV操作”，P操作和V操作是執(zhí)行時不被打斷的兩個操作系統(tǒng)原語。執(zhí)行P操作P(S)時信號量S的值減1，若結(jié)果不為負(fù)則P(S)執(zhí)行完畢，否則執(zhí)行P操作的進(jìn)程暫停以等待釋放。執(zhí)行V操作V(S)時，S的值加1，若結(jié)果不大于0則釋放一個因執(zhí)行P(S)而等待的進(jìn)程。對P1和凹可定義兩個信號量S1和S2，初值分別為1和0。進(jìn)程P1在向緩沖B送人數(shù)據(jù)前執(zhí)行P操作P(S1)，在送人數(shù)據(jù)后執(zhí)行V操作V(S2)。進(jìn)程P2在從緩沖B讀取數(shù)據(jù)前先執(zhí)行P操作P(S2)，在讀出數(shù)據(jù)后執(zhí)行V操作V(S1)。當(dāng)P1往緩沖B送入一數(shù)據(jù)后信號量S1之值變?yōu)?，在該數(shù)據(jù)讀出后S1之值才又變?yōu)?，因此在前驅(qū)數(shù)未讀出前后續(xù)數(shù)不會送入，從而保證了P1和P2之間的同步。我國讀者常常不明白這一同步機(jī)制為什么稱做PV操作，原來這是狄克斯特拉用荷蘭文定義的，因?yàn)樵诤商m文中，通過叫passeren，釋放叫，VRIJGEVEN，PV操作因此得名。這是在計算機(jī)術(shù)語中不用英語表達(dá)的極少數(shù)的例子之一。
