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