11001周志遠教授作業系統｜第2C講 Ch0:Historical Prospective

(音樂) 我們剛才講了幾個 term 跟定義 如果大家很難跟現實的電腦 這個連結在一起的話 我們重新來看一次 如果今天去買一個電腦的時候 什麼樣子你會說它是一個 multi-processor 的 computer system 什麼時候會說是 multi-core 什麼時候會說是 many-core 所以 multi-processor 的意思就是 你買來一台電腦 如果你們打開來 你把機殼打開來 看見裡面有多個 CPU 或者是可以計算的 像我們後來講到的 GPU 的插槽的話 那個就是 multi-processor computer system 了 也就是說每一個人買來的這個 CPU 或 GPU 也好 或是任何 processor 的這種 最新的 processor 的這些 unit 也好 如果你可以在上面插多個 你可以看見很多個插槽的話 這個就是俗稱的 multi-processor 所以它還是在 你還是一台電腦嘛對不對 然後你還是 motherboard 上連接起來的 那這個就叫 multi-processor 了 那所謂的這個 many-core 的意思 指的就是 只是單一一個 processor 喔 對不對 所以就像我們電腦 我們可以插兩個 CPU 四個 CPU 但你一個 CPU 裡面 如果就有多個計算核心的話 這個就叫做 multi-core processor 所以它本身還不能算是一個 computer system 它只是這個 processor 裡面 有 multiple-core 那我們就稱之為 multi-core processor 了 所以兩個結合起來就是 你可以有一個 multi-processor 的 computer system 上面你再插 multi-core 的

processor 在裡頭 那你的核心數就可以不斷增加了 可以嗎 所以當然就更緊密啦 因為它是在同一個 chip 上面 就有這些計算核心了 那到了這個 many-core processor 的意思就是 你可以講就像 CPU 一樣 所以它就是一個 single processor 那但是這個 device 這個 single device 裡面 它就有非常非常多的 core 它自己本身就像是一個小型的電腦系統一樣 但是它在整個電腦你買的電腦裡面 它仍舊是你看見的就是這邊看見的 一張卡然後你就可以插上去 所以我一個電腦裡面 現在最新的對不對 你可能可以插 8 張 GPU 的卡片在上面 幫你做計算 那每一張 GPU 卡 它並不是只是 multi-core 這樣子 它當然也不是一個 chip 它是一個整個就像一個 就像自己一個小型系統一樣 但是它裡面就可以整進 一百多個 core 在裡面 那這個就是所謂的 many-core 了 它就可以這個擠進非常非常多的 一個 single processor 但它的數量 是遠比傳統的要多 那它之所以多就一定代表什麼呢 它的 hardware design 上其實是有非常大的 revolution 就是整個是其實是重新做過的 或者是它的 instruction 的這個方式 處理的方式其實跟傳統的 我們俗稱的 general purpose 的 CPU 是不一樣的 那這個就是 many-core 的 processor 那這個其實是很新的 所以你會看見它的形態是很多樣化的 就像我們說有些人最早期就是直接用 GPU 你就把它當作一個 many-core processor 到了 Intel 對不對 他們設計了這個 Xeon Phi 出來 那甚至於這個我們剛才還沒講到是這個 TILE64 這也是這幾年開始新的

完全全新的一些 architecture 所以你會看見它裡面放的 真的是傳統的 CPU 囉 所以根本就沒有做調整 可是它在它的 interconnect 就這個 chip 上面的 network 上 做了很大的功夫 所以讓這些 core 它在去同時運作的時候 它的這些 bus line 這些溝通的時候 讀取資料的時候 它不會撞在一起 不然你把很多東西塞在這麼小的一個空間裡面 其實你很多會 share 嘛 但是 share 當然可以減省很多成本 可以讓比如說距離變短 可是你相對要去這個處理的問題就是 怎麼樣可以讓它的 congestion 可以減少 不然你會發現大家你等我我等你 根本就是只是在 idle 而已 所以你以為你跑了 64 個 CPU 在裡面 搞到最後等於只有一個 CPU 在運作一樣 那就沒有達到效果了 所以這是非常複雜的東西 但這個是這幾年來 很多很多的研究跟未來的發展在這邊 好可以齁 所以這個就是 many-core 的 processor 了 所以你買來就是單一一個 processor 而已 所以一台電腦可能還是可以通常還是可以插入非常多個 processor 在裡頭 好那我們剛才是從 processor 的角度 去看一個系統的建構 從一個很單純的一個到變得非常多個的各種型態 那這邊還有另外一個方式可以去看電腦系統的運作 到底是長什麼樣子 那就是從 memory 因為我們知道計算就是計 processor 的 memory 嘛 所以以 memory 這邊來看的話 我們這些 multi-processor 的 computer system 它的系統架構在 memory 這邊通常就是會分成這兩大類 UMA跟 NUMA 也就是差別在於像我們剛才看到的 這些系統一定都有多個 CPU 那你的 memory 當然也要 share 囉 因為這是基本定義

但是當你的 CPU 越來越多的時候 你要怎麼樣讓這些 memory 在這些 CPU 之間 share 那它的架構就會分成這兩大類 那所謂的 uniform 就像看圖上就是很明顯 意思就是大家都接上去就對了 所以不分任何的區隔 也就是所有人都用同樣的方式接到這個 memory 上面去 那這就叫做 uniform memory access 或者簡稱就是 UMA 那這樣的系統 當然最適合的就是我們常見的這些 SMP 因為就是大家都一樣 簡單來講 所以當我們說 uniform 的時候 指的並不只是說連接的方式 重點是它 memory 的 access time 這個才是重點 就是 memory access time 必須要相同 也就是說我今天的這個程式 我不管是 run 在 CPU 哪一個 CPU 甚至於哪一個 CPU 的哪一個 core 上面 它的 memory access 的速度是相同的 這就叫做 uniform 所以它就用叫 uniform 指的其實是這個速度是相同的 所以大部分的電腦 比較單純基本的電腦 當然都是用這樣子的形式 那這樣的電腦還有一個好處就是 你在程式執行的時候 其實使用者不必太在意我的程式 到底執行在哪一個 CPU 因為他們都會看見的是相同的效能 所以這就是一般的 UMA 那各位的電腦還有手機 我相信都是這個樣子 就是這種很基本的架構 那 again 當你的 scale 變大 當你為了這些效能 你要增加更多的計算核心 更多的 CPU 到你的電腦系統的時候 你就會發現你的 memory 開始是 bottleneck 了 因為如果是這樣的接法 意思就是你所有的人 可能都要去搶 某一個 memory 的

channel 或是 bus 所以很容易就一樣的道理 當你的 CPU 這些東西增加的時候 它就會開始有更多的 congestion 在裡頭 那就會變慢 所以所謂的 NUMA non-uniform 的概念 again 就是在這個圖看到的 這是什麼意思 所以當我們要管理 東西越來越多的時候 最好的 solution 就是 hierarchy 所以你就會看見 在這樣的電腦系統裡面 我們會把 CPU 就切成四個區域 在這個例子裡 每一個地方我就有一塊 memory 在那裡 這塊 memory 就等於是 這些 CPU 的 local memory 一樣 其他的方案就是 remote 的 memory 所以這是一個 hierarchy 意思就是說這個 CPU 同一個區塊 它 access 這個 memory 的速度 一定會比較快 因為它是直接嘛 那如果你要連到 其他的 memory 還是可以 因為這個電腦是 shared 所以 memory 大家都連得到 但是差別在於 這邊會畫條線的原因就在於 這個 CPU 要 access 這塊 memory 的時候 它要先跟這塊 memory 的 controller 先溝通 才能夠去 access 所以它不是直接 就是間接的意思 這樣的好處 很想的只是因為 hierarchy 所以你可以建構更大的電腦了 就像這邊例子這邊只有 四個 CPU 嘛 我下面就有 16 個 所以自然你可以想見 它是可以 scale 變得更大

但是缺點是什麼 可以說成這個缺點 因為你要 remote access 所以你的路線比較長 所以你會發現你的 access time memory 的 access time 變得不同了 也就是 non-uniform 也就是 local 會比較快 remote 比較慢 所以這就變成 non-uniform 的原因了 那 這樣的話結果就變成 你在執行程式的時候 或說你在 allocate memory 的時候 其實你要注意到 如果你想要你的效能達到最好 其實你擺在哪邊是有差別的 對不對 如果今天程式 run 在左上角這邊 那我 memory 卻 allocate 在右下角 可以啊 會喔 有可能喔 尤其是 OS 又不幫你管理的話 只要看到有空間 我就丟過去的話 就會變成 remote access 那你的速度就會一定會變慢 對不對 那如果你知道這個 這個系統架構的話 執行程式的時候 你就可以好的 OS 它就自動就幫你管理了 或者是至少它有一些 flag control 的方式 讓使用者在執行你的程式的時候 它可以告訴 OS 然後指定 我的程式要 run 在哪 或者說我在 allocate memory 的時候 我只能 allocate memory 從我的 local memory 這邊 要空間 就是我寧可就是等 等到這邊有空間 我才去做 allocation 的動作 這些都是可以的 那所以你就可以去控制它 來去得到 make sure 你在這個電腦上執行的效能 是達到最好的 好所以這個 NUMA 各位當然有見

可能不常見 但是其實在所有的 高效能計算系統多半 是這個樣子 多半是用 NUMA 的架構 只要非常講求 效能然後 scale 大的電腦 都是用這樣的架構在 run 所以其實 未來或許各位也有機會用到 其實要注意一下 到底這個 computer system 是 NUMA 的架構還是 UMA 的 那 NUMA 的話其實 是 OS 要做的事情或使用者 對這個程式執行 效能上就要更加的注意 其實會有很大的差異在那邊 好 好 那我們剛才這就介紹完 所謂的 tightly coupled 所以雖然好像很多 很複雜 但其實 它都是在同一台電腦 box 裡面的 就是你買來大概 就是一個 server 那裡面就有那樣子形形色色各式各樣的 架構 好 那接下來 我們就介紹 distributed system 所以也就是所謂的 loosely coupled 電腦系統 那所謂的 loosely 對不對 定義是什麼 簡單來講就是 它是透過網路 所以就是透過 internet 去連結的 所以就是把很多 電腦透過網路線把它 連結在一起了 所以這個其實以一般的 像學校 我們常常 去做的事情就是這樣 我們把電腦把它串在一起 變成一個 去做 同樣事情的一個電腦系統 就變成一個所謂的分散式的 系統 就像我們說internet 廣義來講 如果你把 internet 看成一個系統 是可以的 而且它就是一個分散式的電腦系統 對不對 透過這些 cable 去把它連結起來的 好 那 這樣子的連結 跟之前的 最大差別 一個是連結的方式不同 對不對 另外一個很重要

就是它的 memory memory 的這個 定義 它就變成全部是 local 也就是每一台電腦都有 memory 可是他們是不會 share 的 對不對 所以就像 我們今天透過網路可以連到別的 電腦 不代表別人可以直接 去使用我 memory 的 我電腦上 的 memory 的空間啊 對不對 一定要透過我的程式 我的 OS 我才能去使用 所以其實他們 是分開的 所以這就是 distribute system 跟之前我們看到的系統最大的 差別 那這樣子的電腦系統的目的 也跟之前也會蠻不一樣 之前我們都講的都是效能 對不對 performance 所以一直增加計算核心 但這個方式雖然也可以增加 計算核心啦 可是更常見 的主要原因是在於這些幾個 對不對 像是 resource sharing 為什麼我們會上網 其實是為了在 sharing resource 或者是 information 對不對 所以我去你那邊去抓照片 我去抓東西 抓檔案 等等 這都是 resource 的 sharing 那第二個原因就是要做 load 的 balancing 或是 sharing 所以今天如果我很多台 電腦的話 那 我有很多台電腦的目的就是因為 當有一台電腦的工作量太多 的時候 我可以把 這件四個工作讓另外一台電腦 幫我去分擔 也就是直接把它 移過去就對了 所以我就可以讓大家 我會有人 有人這個太多 的工作量 然後在那邊等很久 可以讓大家可以平分 所以大家可以同時把事情做完 那 第三個 我們剛才說 parallel的 system 也有提到 reliability 啦 但是其實 distributed system

才是真正 最注重 reliability 這一塊 什麼叫 reliability 呢 也就是 同樣就是讓我的系統 不會因為有一些 fail 的發生和 crash 掉 讓它很可靠 很 reliable 像是資料 不會掉 或是我程式不會 被 kill 掉 那為什麼分散式系統 比較容易做到 因為每一台電腦 是獨立的嘛 對不對 所以我們知道 相對之下 電腦跟電腦之間 其實它只是連結 在做這個資訊的溝通 所以當一台電腦壞掉的時候 其實 通常是不會 其實是不會影響到另外一台電腦的 所以現在很多 分散式系統 或是大家有聽過 什麼 cloud computing 對不對 就是用很多台電腦的目的是什麼 就是要實現 reliability 所以任何一台電腦壞掉沒關係 我就把它這件事情交給另外一台 有一台電腦壞掉 我就把這件事情 交給另外一台 或者說我的資料 我可以備份在很多台電腦 對不對 所以 很多台電腦同時壞掉機率 這其實是蠻低的 那如果是 parellel processing的這個 processor的系統 畢竟是同一台 machine 所以你可以說 如果 memory box 比如說 壞掉 那當然就真的整台電腦 都毀了 對不對 所以它 reliability 能夠做到的程度是很有限的 但是 如果是一個分散式系統 它根本就是不同電腦 每一個人有自己的 memory 有自己的 disk 對不對 所以當然它的 reliability就可以做到比較高 好 所以很多分散式系統現在 也都是為了這個目的 好 那分散式 系統的架構呢 它簡單分 就比較單純一點 就是 所謂的 peer-to-peer 跟 client-server 這兩個大家

也太常見了 所以大家應該 要稍微知道一點 因為其實 一定大家常常在用了 那 client-server 簡單來講就是 master-slave嘛 對不對 所以一看 大家就知道 也就是這怎麼系統運作 有一個 server 在哪裡 其他人呢 都是所謂的 client 或是 worker 也就是透過 server 的控制 它才能知道它要去做什麼事情 所以所有的事情都必須要 透過 server centralized 的一個 control 這就是所謂的 client-server 那這個 大家很常用到啊 譬如說 FTP 對不對 大家常常在 傳 FTP 都知道我要先 我是架 FTP 的 server 還是我是架 FTP 的 client 對不對 所以是很明確的 一個人是 server 一個是 client 至於資料的流向 那是另外一回事 但是它整個運作 是有一個是 server 它是能夠 控制這個整個連線 是能夠去運作的 這台電腦 就是 server 好 那這樣的架構 通常就是很容易 比較容易去建起來 像大家如果去學習 比如一些網路的課 可能有些作業 就會請大家 寫這種溝通的 的一個 network 的系統 出來 對不對 但是這樣 系統的壞處當然也很明顯 就是 server 往往就是一個 bottleneck 所以很多分散式系統 他們當然還是選擇了 用 client-server 的架構 去建 尤其是我們說 雲端計算那些 Google, Microsoft 的那些 cloud 去管一個

data center 的時候 因為方便 所以他們還是用 client-server 但是他們會下 很多的功夫 比如說 server 沒有人說它只能是一台電腦 對不對 我其實也可以用 十台電腦當做 server 也就是說他們的角色 是 server 但是這個角色這件事情 我還是可以用分散式的方式 讓十台電腦 去做處理 所以比如說有一台 server 如果毀了 可能有一台 master server 它壞掉了 我可以立刻把它 這個職權交給 backup 的 server 那這樣我就可以達到 對 reliability 但是我還是 一樣其實是 server-client 的架構 所以中間有很多 中間的 solution 在那邊 但基本上 它這種方式是比較容易架構的 但是 failure 怎麼樣去 make sure 因為 server 意思就是說 如果 server 沒了 那真的整個 系統就不能動了 對不對 所以我必須要處理這個問題 另外就是這邊畢竟是 所有的 workload 都進來 所有的工作量都要透過 server 所以 server 成為會效能的 一個 bottleneck 那有沒有什麼 其他的方式可以把它 至少減輕它的工作量 比如說能做 真的需要計算的部分 可能還是 都讓這些 client 去做 然後 server 它要去溝通 要去處理的事情 都是最重要 但是都是最簡短 最輕鬆 或是最快 可以做完的事情 所以這就有 很多設計在裡頭了 好 那相對於 client-server 在分散式的 這個系統裡面 另外一個做法 就叫做

peer-to-peer 了 也就是沒有 server 所以叫做 peer-to-peer 因為意思就是 每一個人都是 peer 就是同僚或同仁的意思 所以大家都是相同的角色 就像各位同學之間 修同一堂課 大家都是 peer 的這個角色 所以並沒有做區分 誰是 master 誰是 slave 那為什麼他們還能溝通 那就是代表你在寫 peer-to-peer 的這個系統上 你會制定一些 protocol 或者是 rule 或 policy 讓他們 follow 這個 protocol 他就可以溝通了 那這樣的做法 最重要的就是 沒有 single point of value 所以今天任何一台電腦 死了或離開這個系統 peer-to-peer 的系統 一定都可以繼續的運作 因為他也沒有什麼特別的 大家都只是來來去去都可以 他沒有任何一個人是必要的 在這個系統裡 甚至只要兩台電腦 在這裡 他就成為一個 peer-to-peer 的系統 所以他非常的 reliable 基本上他就不會 因為任何一個電腦 會影響整個系統的運作 那他的 loading 通常 也就很 balance 因為大家都可以 共同的去做同樣的事情 那這樣的系統 其實各位也常常在用 尤其是去 網路上 如果你去抓 看電影啊 或 streaming 的 service 對不對 現在這個 網路實在太發達了 我相信大家 要去看球賽或什麼 一定都去網路上找一找就有了 那這些系統 全部都是 peer-to-peer 所以你可以想見那些影片的量 是很大的 然後全世界的人 比如說都在看奧運 我在看世界盃 然後大家都要看同樣的 content 所以當然不可能每一個人都從 一個 server 那邊 把資料

copy 過來囉 其實是大家互相去 share 就近的點 然後就去讀取那些 檔案 去分擔這個 load 所以很多的 streaming 的 尤其網路上 streaming 的系統 都是 peer-to-peer 那 尤其啊 其實 again internet 對不對 我們說 你就把 internet 想 其實它的確是 一個系統 它的確就是一個分散式系統 那 internet 就是 標準的 peer-to-peer 所以其實 internet 我們知道它是大家 不知道早前有沒有看過這個電影 阿諾演的這個 魔鬼終結者嘛 對不對 所以它的敵人是誰? Skynet Skynet 什麼 其實就是 internet 那真實就是如此 internet 是不會被 shut down 的 真的是 並不是任何 一個國家 任何一個 organization 在管理 internet 可是到處你都 可以上網 對不對 然後這 internet 它最厲害的地方 就在於它永遠不會 break 你可能你自己 local 你可能沒辦法連上 internet 各種原因 但是 internet 永遠存在 你唯一把 internet 消滅掉的方式就是把 所有這個 連在一起的所有電腦 全部把它給拿掉 但這 當然是不太可能的 所以從這邊就可以看到 peer-to-peer 其實是非常 powerful 的 好 很好 所以大部分 的網路上的 其實很多 是透過這樣的 架構去建立的 好 那 根據連結的

方式是剛才那兩種 那 常常在分散式 系統這邊 大家也還會聽到 的幾個 term 我們就稍微 介紹一下 第一個就是 cluster 對不對 所以我們都要知道 叢集電腦 那就是所謂的 cluster 的 system 那 cluster system 它其實 是屬於一種分散式系統 因為我們知道 cluster 它其實就是把很多 電腦連結在一起 所以 符合分散式系統的 定義 那但是它又在 分散式系統裡面比較 這個它算一個 subset 比較特殊的一種系統 那這種系統特殊的點在哪 就在於它的網路的連結 通常是 local area 也就是說它的網路 比如說它的網路的 bandwidth 或是它 使用的網路線是比較好的 所以它的溝通可以再 快一點 因為我們知道 internet 可能很遠嘛 從台灣連到 美國 至少也要 delay 相對就會比較久 送一個訊息 的 delay 那 cluster 它當然它在同一個 通常它就在同一個區塊區域 那同一個機房 比如說 所以它們都是非常 近的在一起 所以你就可以去 建這些所謂的 local area 的 network 所以它的傳輸速度 重點就是 傳輸速度可以再更快一點 因為畢竟傳輸還是 很花時間的 這只要稍微知道就好 有興趣的自己去查啦 怎麼樣可以讓它 最快勒 目前最新的 technology 叫做 InfiniBand 這已經用了好幾 過去十年了 自從它出來之後 我知道大家在 宿舍你也可以 build cluster 因為大家都用 Ethernet 對不對 我相信大家都有經驗 但是 這些比較 high performance

cluster 或者 super computer 它們 用的就是 InfiniBand 大家自己去查 速度就會快個十倍 價錢也是十倍以上 這是相對的嘛 但是有付出它真的有得到 它真的是很快 所以真的很講求電腦 這個效能的電腦 你去看 幾乎都是用 InfiniBand 了 那為什麼 InfiniBand 快勒 其實我們這堂課 會教 就叫做 RDMA 就是我們 剛才提到 I/O 嘛 怎麼樣 快 有一些技巧在裡面 InfiniBand 就用了 這個大家已經很常用在 電腦系統裡面的 所謂的 DMA 的這個技術 但它把它擴展到 跨網路線 所以當然 I/O 就快 好 這大家看一下就好 這沒有那麼重要 cluster 當然也有分 asymmetric 跟 symmetric 就是很多台電腦 十台電腦有一台可能是 master 或者是 symmetric 就是所有的人就是沒有去分 這個稍微看一下就好 這個比較不重要 好 所以啊 統整一下 我們剛才介紹了 各式各樣的一些名詞 其實是非常常見的 所以希望大家對於系統這個領域 如果一些基本了解的話 剛剛介紹的這些名詞要 稍微記一下 然後它的定義 它的意義要稍微知道 能夠區分 那我用的圖來統整簡單來講 就是一開始我們看見的 single-core computer system 就像最早期的 PC 然後咧你把它擴展一下 就變成擁有 multi-core 的系統 所以你可能只有一個 CPU 但那個 CPU 就有很多個 core 就像手機 對不對 那你可以再擴展一下 就變成 現在比較常見的 PC 或者說 server 這些

伺服器 你會發現你的主機板上不會只有一個 CPU 的插槽 其實你可以插好幾個 甚至於你可以插 GPU 或是 CPU 或是插不同的一些 co-processor 這些就叫做 multi-processor 的系統 所以它不是只有一個 processor 它可以插很多樣化 然後很多數量的 再往外走 你就會發現 一台電腦是有限制的 我的主機板再怎麼做也就是那樣的空間 所以如果你想要 更多的計算量的話 怎麼辦,那就是用 cluster 所以我就把很多台電腦 把它湊在一起 那就變成我們常見的所謂的 cluster 那 cluster 咧,通常還是我們剛才說的 就是它至少都還是用 local area 就是比較近 然後比較好的網路去把它串起來 而且通常 cluster 做的事情就是它 所有上面灌的軟體跟管理者 是單一的 就像我們實驗室,很多實驗室都有 建自己的 cluster 去做計算 那上面灌的 OS 可能都長得一模一樣 對不對,然後可能 都是用同樣的方式在做管理 但是咧,如果你 再往外走,就會變成 最 general 我們說的分散式系統 那就完全沒限制 反正在電腦跟電腦之間能夠 溝通去完成一件事情 那就是分散式系統 就像 internet 或是說我們說雲端計算 那些 data center 我們聽過 這個資料中心 它整個是非常大的 一個 scale,那就變成所謂的分散式系統了 好,所以電腦跟電腦之間差異性 簡單來講就會變得非常的大 所以我們剛才說的 tightly coupled 啊, loosely coupled 簡單來講就是你在一個 box 裡面 還是多個 box,box 就是一個 machine 的意思 所以如果是 tightly 通常就是 你把它放在一個 box 裡面的 machine loosely 就會跨網路了 好 (音樂)