【冼鏡光並行計算講堂】
March 20, 2024上線
March 20, 2024上線
這是並行處理中文精簡版影片的網頁，在此您可以下載每一講的投影片和程式，也有YouTube上影片的連結。
原來的英文版在此，該網頁提供了37集影片、775張投影片、考試題目的解答和討論。
不過，這是為了Concurrent Computing 這門課錄製的完整課程，
因此預備知識、學生進入這門課之前的先修課目等等和國內的頗不相同，所以這一系列以英文發音的影片對國內同學而言或許會有點障礙。
2020年春天回台時在北科大開了這門課，那時COVID疫情初起，上課都得戴口罩頗不舒服，
好在是和北科大同學交流時了解到國內計算機課程的現狀，心想日後把英文版轉錄成中文版應該是件好事。
但是想到這是一件大工程，不太可能在短期內完成，於是就一而再、再而三地想想（真的只有想）停停，進展全無，
反而時間都用在錄製其他課題上（譬如，初等幾何、程式寫作、空拍機以及FPV等等）。
今（2024年）初終於下定決心開始行動，經過2020年初在北科大的經驗後，我打算只錄製精簡版，
把英文版中一些較艱澀或是較困難的部分去掉（您有了基礎再去看英文版就不會有困難）、
並且加上一些對基本概念的進一步補充，這就是「精簡版」的由來。
教這門課是其來有自的。在1980年代早期，因為電腦預算問題而必須把若干個不完全獨立而是靠中間暫時性檔案連繫的程式整合起來，
研究後發現這些程式可以變成一個大程式中的各個task（IBM的術語）、讓它們並行執行，
原本的暫時性檔案全都去掉而換成在記憶體中使用同步方式的溝通。
這個做法略為增加CPU使用時間和系統服務次數，記憶體用量也有增加但不多，但如此做法卻大大地降低掛磁帶和磁碟的次數、
以及執行程式的次數，算起來可以省不少錢。
不過，IBM卻沒有程式語言提供這種能力，而必須使用組合語言和一些集體指令（macro）完成，
這並不難、多讀手冊找出合用的資訊就行了。
有趣的是，或許是台灣在那個時段沒有人在用並行的能力，雖然所有IBM的OS（含OS和DOS）都有這項能力，
但台灣IBM的技術支援部門卻沒有任何一位工程師懂這套技術。所以，我的並行計算的第一步就是因為工作需要自己踏出第一步、
而且還是獨自跌跌撞撞摸索出來的。
不久之後，在淡江電子計算機系兼任、開了一門OS的課，那時在並行計算方面已經有了初步知識，
因此也希望淡江學生在學校就能學會這一套技巧，以便走入職場後可以立即派上用場。
那個時候，我用兩本書做課本，一本是Madnick和Donovan合寫的
Operating Systems做實務上的介紹（下左照片）、另一本是Per Brinch Hansen的Operating System Principles做並行計算的基礎教材（下右照片），事實上Per Brinch Hansen
的書是第一本有系統地探討並行計算、特別是同步結構的教科書。我想這是十分理想的組合。
沒多久，儒林圖書公司希望我能夠把OS這門課的教材寫成書，我的做法是先把Madnick和Donovan的書譯成中文並且加上很多當時的新內容 （譬如VM — Virtual Machine）、然後補上並行計算的同步概念，但很遺憾的是做完一半後就轉向去做其它的計劃了， 這是我一生中沒有完成心願的遺憾，然而這本書的上冊的確是完成了的（下面照片）。
後來出國進修，拿到PhD學位後沒多久又被指派到教OS（必修）的課程。 到了1990年代，並行計算在電腦界並不陌生，而且幾乎任何好OS課本必然都有這樣的一章到兩章。 然而對很多學生來說，並行是一個很遙遠的觀念， 有一些（他校）教授還告訴我不少學生還會懷疑只有一個CPU的電腦怎麼可能同時執行好幾個程式， 因此我和幾位志同道合的同事決定我們可以做點什麼來克服這一項困難。 在美國國科會（NSF — National Science Foundation）和IBM Eclipse Award支助下， 三年內我們拿到了1200多萬台幣的錢解決這個問題。
我們的做法是設計一組架在C++上方的class library，透過和課本上類似的語法讓學生寫作以C++為主的程式 （那時支援並行處理的C++標準還沒出現），再設計一個visualization系統，它和學生的程式分開執行， 而學生程式中和並行與同步有關的活動則是透過class library和visualization相互溝通（學生不必做任何事）。 這套系統就叫做ThreadMentor。 於是，學生程式中並行活動的細節（特別是同步）在visualization系統幫助之下一覽無遺， 而且各同步項目的彼此互動也可以很清楚地顯示出來。 這套系統最先是在Sun的Solaris 系統下發展，後來再移植到Linux，我們也試著弄出一套Windows XP版， 但是Windows下的東西被Microsoft愈弄愈複雜而且系裡頭也沒多少台Windows的機器， 所以我們最先放棄Windows版，由於Sun和Solaris走入歷史，目前就只有Linux版在運作。 因為計劃已經結束多年，也沒有人力繼續維護，所以目前能夠提供給您的是一個Linux RedHat系統下的全部連結完成的 Intel版static image，大多數Linux系統之下都可以正常工作，Windows或macOS之下就只能開 VM（virtual machine）了，我在北科大開課時就用的是VM。
ThreadMentor完成之後沒幾年， 系中開始修訂課程，決定把OS中的並行部分獨立出來變成一門新課Concurrent Computing， 而原本的OS加上其它內容改成選修，當然Concurrent Computing就是OS的先修課。 於是，Concurrent Computing於焉而生， 每年兩個學期都開課，這已經有10多年的歷史。 當年我們系開出這門課主要是因應愈來愈多的平行和並行計算的需求，在開始時縱使是在美國也是很早、很先進的。 十多年後改成中文的精簡版，希望對國內學子有點幫助。
很多年前，我曾經在國內的論壇提倡過並行處理和同步，但老是遭到冷嘲熱諷， 說是就用package和tool就好、不必學這些「低階」的東西， 或是題目做不出來了就說不是我的學生做不出來理所當然，🙄。 還有很多其它的論調就不多說了，很多年過去了，GPU的並行程式寫作應該很熱門才是，但它的根本就是並行計算。 Concurrent Computing這門課沒講到GPU部分， 因為系裡頭還有一門Multicore程式寫作、內含GPU的部分。 以往，Concurrent Computing最後一兩節課會講GPU程式寫作（使用CUDA）， 但後來慢慢地就沒足夠時間講到GPU了。然而，您學會此地的並行概念後跳到GPU部分並不難，因此中文精簡版就沒有這一部分。
以下是各講的影片和投影片，有興趣的朋友不妨有空時來逛逛，看是否有新東西上線。
| 序號 | 內容 | 影片連結 | 投影片和程式 | 上線日期 |
| 1 | 開場白。 我們先定義何謂交錯執行、平行和並行；了解一些歷史背景； 再用兩個Unix命令列運算&和|來實現最簡單的並行作業； 接著我們介紹幾個Unix的命令和重導I/O。 影片結束之前有一個Unix的signal的demo，介紹kill命令和 SIGKILL、 SIGINT、 SIGSTOP和 SIGCONT在命令列上的操作。 | 01-Basics | 投影片41頁 | March 20, 2024 |
| 2 | 作業系統和硬體基本知識。 本集會討論到以下內容：多處理機系統和它的一些歷史、（dual mode execution）、interrupt和trap（插斷、中斷、和陷阱）、叫用系統（system calls）、計時器（timer）、CPU執行機器指令的週期（instruction execution cycle）包含了讀取指令（fetch） — 解碼（decode） — 執行（execute），CPU pipeline（流程）、資料衝突（data hazards）、不能分割（atomic）指令、特權指令（privileged instruction）等等。從這些討論就不難看出並行計算中某些困難的端倪。 | 02-Hardware-OS | 投影片46頁 | May 3, 2024 |
| 3 |
Process 初步：一之二。
本集會討論到以下內容：從原始程式到可執行檔的過程、什麼是一個process、程式的記憶體配置方式（整體資料區、指令區、
heap和stack）、解釋為malloc()和calloc()動態記憶體配置用的heap、以及局部變數使用的stack區域。
了解這些最基本的知識之後， 我們討論一個process在執行時的記憶體配置方式、process 在執行時的可能狀態、process的狀態圖。接著是OS處理process的最基本觀念，包含OS內如何表示一個process、process的調度（scheduling）方式、以及切換環境。這些是本課程的必備知識。 本講第二部份是用Unix系統講解多process（multiprocess）程式寫作。我們會討論 fork()、 exit()和 wait（）函數，並且用例子解說fork()的執行方式和結果；我們也用例子說明fork()產生的process的母-子（parent-child)關係、母和子使用獨立分離的記憶體空間；此外，也提醒在多process程式寫作時printf()所帶來的困擾。最後，我們用若干簡單問題和一道程式習題做結束。 |
03-Process-1 | 投影片70頁 | May 19, 2024 |
| 4 |
Process 初步：二之二。
請先看完上一集，因為它討論到本集所需的預備知識。
本集會討論到以下內容：我們先討論殭屍（zombie）process；接著介紹exec系列的系統叫用、 但我們只討論execvp()， 了解execvp()之後其它exec函數是大同小異的； 其次的重頭戲是Unix中的共用記憶體(Shared Memory)，各獨立執行的process可以透過共用記憶體溝通。最後是一個程式習題，透過它讓您實際使用 fork()、wait()、execvp()和共用記憶體，這道題是用多process實現並行的合併排序。 |
03-Process-2 | 投影片73頁 | July 14, 2024 |
| 5 | Thread（執行線）。 本集會討論到以下內容：我們先用直覺的方式說明何謂執行線，講解使用執行線的好處。接著，我們討論使用人執行線（user thread）和系統執行線（kernel thread）的差異、複線作業（multithreading）模型、和多核心程式寫作的基本觀念。然後，我們再解釋取消執行線、執行線專用、執行線安全的的定義，最後用協同程式（coroutine）和纖維線（fiber）做結束。除此之外，我們還簡單地回顧了process、複程式作業（multiprgramming）和複線作業的早期歷史，並且用比較直覺方式解釋了很難被平行/並行化的理論基礎。 | 05-Threads | 投影片36頁 | July 30, 2024 |
| 6 |
同步（Synchronization）初探。
這是並行計算（Concurrent Computing）中文版的第六集、講解同步（synchronization）的最基本的知識、定義和若干名詞，這些定義和名詞會在往後各集中反覆出現。所以，本集是往後各集的敲門磚，請各位務必弄懂它們的意義。
本集會討論到以下內容：我們先用兩個簡單的例子說明為什麼需要同步，一個使用高階語言敍述的交錯執行、另一者則用機器指令交錯執行。接著，我們定義何謂競爭狀況（race conditio），而且很清楚地指出用機器指令構作執行序列（execution sequence）的必要性。 為了克服競爭狀況，我們引入臨界區（critical section）和互斥（mutual exclusion）的觀念。從互斥出發，我們說明一個臨界區問題的「好」解答的三個要件：互斥（mutual exclusion）、有進展（progress）、和有界等待（bounded waiting）。接著，我們解釋幾個有關的名詞以及它們和「好」解答的要件的關係。最後，我們用兩個簡單問題做結束。 |
06-Sync-Basics | 投影片33頁 | August 6, 2024 |
| 7 |
純軟體解法（一之二）。
這是並行計算（Concurrent Computing）中文版的第七集。第七集是純軟體（也就是不必借助硬體和系統支援就可以在
使用者程式中做到的）解法，這一集介紹三個嚐試，每一個嚐試都引入一個新手法，並且討論是否能滿足互斥、有進展、有界等待三個條件。不過，這三個嚐試或多或少都不能滿足三個條件，但是在三個嚐試中用到的手法巧妙地合併起來就可以得到一個完全滿足三個條件的「好」解法，我們會在第八集中討論。
本集中我們先介紹基本假設，這些假設是合乎我們熟知的軟硬體要件、而不是特別為做軟體解法而設的， 我們談到使用人程式的假設，這些假設其實就是保證使用人程式不會干涉解法中所用的邏輯和變數，也都是合理的。 另外，本集只討論兩個process的解答，至於多過兩個process的解答都相當複雜、不太合適放到大三的課程中。 第一個嚐試使用一個共用變數turn，它指出下一個能進入臨界區的process是誰，不過進入臨界區變成固定順序，固然它實現了互斥、但不能完全滿足其它條件。 第二個嚐試，改用一個有兩個元素的陣列（每一個process使用一個元素）。當一個process對應的邏輯為FALSE表示 該process無意使用臨界區或不在臨界區中，若TRUE則表示該process有意使用或正在使用臨界區中。 於是一個process在進入臨界區前先把自己的邏輯變數定成TRUE、再等待對方的邏輯變數變成FALSE，之後才能進入臨界區； 離開臨界區時把自己的邏輯變數定成FALSE，表示已經離開。這個嚐試也可以做到互斥，但仍然不能完全滿足其它兩個條件， 特別是有限決等時間和有界等待。 第三個嚐試引入「禮讓」的想法，在入口處除了把自己的邏輯變數定成TRUE之外，若發現對方的邏輯變數也是TRUE （想進入或已進入），就把自己的改回FALSE（表示禮讓）、再等待直到對方的變成FALSE為止， 於是再把自己的定成TRUE從新嚐試。出口部分是一樣的，都是把自己的邏輯變數定成FALSE。這個嚐試可以滿足互斥， 但也無法完全滿足其它兩個條件。 雖然如此，三個嚐試使用的手法愈來愈精緻、整合起來之後就會得到一個完全滿足三個條件的正確解法，這是下一講的主題。在結束本集之前，我們還留下兩個習題，給每位做個練習。 |
07-Software-1 | 投影片39頁 | August 19, 2024 |
| 8 |
純軟體解法（二之二）。
這是並行計算（Concurrent Computing）中文版的第八集、是第七集的延續，
兩集都在講解如何用純軟體技巧解決臨界區的問題。第七集討論了三個嚐試，
但都不滿足一個「好」解法的三個條件；第八集把這些觀念融合在一起，
得到歷史上第一個正確而是也是「好」的解答 — Dekker解法。
接著，我們討論一個基於相同思路、但極度化簡的方法：Peterson 解法。 這是目前教科書中最常採用的方法，幾乎每一本作業系統的書都會講解這個方法。 從使用各個變數的方式和思維，Peterson方法和Dekker方法系出同源， 但此地討論的第三個方法卻使用了不同的思維方式。 第三個方法就像我們去餐廳或區公所辦事時先抽個號碼，然後號碼最小的先進去辦事一樣。 然而，在電腦中是有可能若干個process抽到同一個號碼的（除非抽號時有互斥，但互斥卻正是我們要實現的）， 因此得要處理同號的問題。當等著進入臨界區的process都有了號碼之後，號碼最小的進入。這就是Lamport方法， 教科書中一般叫做 麵包店解法（Bakery Algorithm）。 我們討論的三個正確而且「好」解法都是針對兩個process的版本，不過除了Dekker解法之外， Peterson和Lamport解法在開始時就是以n個process為出發點， 而Dijkstra則把Dekker的方法擴充到n個process。 最後，我們提供若干個習題，請各位做個練習。 |
08-Software-2 | 投影片59頁 | September 3, 2024 |
| Total Number of Slides | 397 | |||
最後，有兩組英文發音的教學影片可能會對您有點幫助：
更新記事表