什麼是操作系統?
什麼是操作系統? 為什麼說C / C++ 更底層 ? 電腦裏只有一個CPU, 多線程是怎麼實現的 ?
一些簡單口胡, 也算對本學期的學習做一個總結
一言蔽之, 操作系統是管理下層硬體, 為上層軟體提供統一的, 容易理解的抽象API的 軟體 .
硬體是什麼樣的 ? - 馮諾依曼結構
CPU
CPU是一臺計算機的大腦. 負責運算和管理整個計算機. 你可以簡單把它看成能接收CPU指令, 做出相應動作的電路板.我們會討論的典型的指令如下.(順便, 如果你想知道你寫的代碼是怎麼變成CPU指令的, 你需要知道的是編譯原理)
#運算
ADD 1, 2
#訪問內存, 把內存地址addr處的數據放入寄存器
Mov addr, %eax
這裡寫的其實是彙編語言, 它和CPU指令其實是一回事. 彙編語言是給人看的, 所以寫成英文記號, CPU指令是電路看的, 所以實際上是一串二進位串, 或者更直接一點, 是一串高低電平. 一條彙編語言和一條CPU指令是一一對應的, 我們接下來不會區分這兩個名詞.
存儲結構
關於存儲結構, 我們需要記住的是: 有多個級別的存儲, 越快的越貴, 因而越快的容量越小(當然, 如果你有錢, 那你就可以為所欲為地使用最快的存儲設備).為什麼我們會在乎存儲結構讀取的快慢呢? 因為CPU的時間是非常寶貴的, 我們不希望每次CPU訪問內存的時候都浪費很多時間等待存儲設備. 就像你點外賣不喜歡等待一樣, 操作系統工程師也不喜歡CPU等待.
CPU寄存器
圖中Register, 讀寫速度可以認為和CPU運算一樣快, 讀取Register內的數據幾乎可以認為不花費時間.斷電失去數據.
Cache
這是比較複雜的一部分, 我們待會兒返回來講
內存
圖中Main memory部分. 就是我們熟知的電腦內存啦. 現在你的筆記本的內存一般是 4-16GB. 但是訪問內存也比訪問寄存器耗時得多, 你可以在圖中看見大概是十倍時間.斷電失去數據.
硬碟
圖中Magnetic disk部分, 最近幾年火起來的SSD就是一種硬碟. 就像你可能知道的一樣, SSD, 或者叫做固態硬碟, 比傳統的機械硬碟快很多, 但是讀寫速度依然比內存慢得多. 從圖中你可以看到, 大概慢了三個數量級
磁帶
老掉牙的東西啦. 一般只用很老的老項目使用了.我們這次不討論它.
輸入輸出設備
包括計算機和人交互的一切介面. 鍵盤, 滑鼠, 屏幕, 網卡等等.
好了, 關於計算機硬體, 我們就說這麼多了. 如果你有一點暈, 沒關係! 你只需要大概記住這兩條就可以了:
- 只有CPU會計算
- 存儲設備是多級的. 從寄存器到內存到硬碟, 速度越來越慢, 容量越來越大
為什麼你需要操作系統?
假設你是一個程序員, 你寫了一個C程序
int main() {
int a = 1;
int b = 2;
int c = a + b;
printf(%d, c);
return 0;
}
你的程序經過編譯大概變成了這樣的CPU指令
# 初始化a和b , mov指令把前一個操作數的值賦值給後一個操作數
Mov 1, a
Mov 2, b
# %開頭的是CPU寄存器, 你可能還記得它是最快最小的存儲設備, 我們要把a和b從內存裏拿出來, 放進寄存器裏
# 接下來Add指令才能工作
Mov a, %eax
Mov b, %ecx
# 加兩個寄存器的值, 和寫入後一個寄存器中, 在這裡是寫入eax寄存器
Add %ecx, %eax
# 把這個值寫回內存
Mov %eax, c
#列印, 即把內存裏的值送到顯示器,這裡涉及一系列系統調用，現在先不管
指令送進內存, CPU從內存裏讀取指令(讀取指令和執行指令是CPU硬體實現的), 執行.訪問內存, 執行計算. 一起看起來都很美好. 看起來我們不需要一個操作系統.
沒錯! 恭喜你發現一個驚天大祕密! 我們就是不需要操作系統!
如果我們的程序就一直這麼簡單的運行, 那可能的卻不需要. 可這不符合我們對現代計算機的認知. 瀏覽器和音樂播放器是兩個不同的程序,為什麼你能一邊刷網頁一邊聽歌? 一定是這兩個程序一起運行了, 可是按說你只有一個CPU, 一套內存, 只能跑一個程序, 為什麼你能同時運行好幾個程序呢?
是的, 這就是操作系統最基本的功能, 操作系統負責管理CPU和內存, 讓每一個程序都覺得自己是獨立運行的.
操作系統怎麼做到的? 虛擬化
虛擬化這個詞可能和大數據和雲計算一起在你的耳邊回蕩已久. 其實它就是欺騙和造假的另一個說法. 還記得我們說過, "要讓每一個程序認為自己是獨立運行的"嗎? 我們怎麼辦呢, 我們假造一系列運行需要的硬體, 讓每個程序都覺得自己佔有了硬體, 正在獨立運行. 而且讓它們的執行互不幹擾
進程
進程是欺騙的開端. 一個進程就是可以讓一個程序感覺自己正在獨立運行的所有環境. 想一想, 一個程序運行大致需要做什麼?
- CPU要執行程序指定的CPU指令
- 執行的過程中必然要訪問內存
- 執行的過程可能要與人交互
所以一個進程也圍繞著虛擬出一個CPU, 一份內存展開.
CPU虛擬-分時復用
怎麼虛擬出一個CPU呢? 好辦, CPU運行速度比人能察覺的快得多. 它可以在兩個進程中間切換, 這一個瞬間給你顯示網頁, 下一個瞬間給你播放音樂. 對,事實就是這樣的, 你的CPU在負責給你唱歌的時候,只是在數十個任務中時不時唱一句, 但是你會覺得音樂是連續的.
虛擬內存
這是比較複雜而且比較細節的一節. 我希望我能講明白為什麼要虛擬內存, 解決思路大概是什麼樣的, 現在的方案做到了什麼事情.至於實現細節其實不那麼重要. 我建議閱讀的時候考慮先跳過 "怎麼實現虛擬內存管理" 一節.
為什麼要虛擬內存?
你剛剛可能就開始困惑, CPU只有一個, 在確定時間只能執行一條CPU指令, 的確可以說是隻能執行一個程序, 可是我有16GB大內存, 為什麼不能同時執行多個程序?
是這樣的, 我們重新看這兩句CPU指令
Mov a， %eax
Mov b， %ebx
我們剛剛說這兩句CPU指令把a和b分別讀入寄存器. 這是不準確的. 內存是不知道誰是a誰是b的, 內存只能由一個確定的地址, 訪問內存裏特定的一塊地方. 存儲器是按地址訪問、線性編址的空間,像一條數軸
我們假設自己擁有一個4GB的內存. 每Byte是一個最小讀取單位. 一個內存地址由32bit 二進位數描述(你會發現剛好能定址4GB) , 剛剛兩句CPU指令可能會是這樣
#0x是表達16進位數的一個習慣, 不用在乎細節, 我這裡只是想表達它是一個確定的地址
Mov 0x00，%eax
Mov 0x04，%ecx
在這兩條CPU指令運行之前, a和b就被放在那個地址了.(這個事情也是操作系統保證的, 我們晚點談)
繞了這麼一大圈, 問題終於出現了, 程序員寫代碼的時候能考慮自己的程序運行的時候是不是和別人一起運行嗎? 或者說, 程序員能夠一開始就知道自己的數據被放到什麼地方, 從而更改自己的代碼嗎?
不行. 每一個程序員寫代碼的時候, 總是假設只有自己的程序在運行,(如果不這樣, 編程會變得異常困難) 對應到內存上, 每一個程序員總是假設計算機的4G內存全部屬於他.所以他會從0x00處開始使用內存.
這段對你來說可能有一點難理解. 因為你編程的時候好像從來沒有考慮過內存的事. 在大部分高級語言實現裏, 程序員是不能直接看見內存的. 這是同為高級語言, 我們說C更加底層的原因之一. 在這裡, 你需要記住的是編譯器也不能做到這樣的事情.
說到這裡, 你可能有點明白問題在哪裡了, 問題在於數據放在內存的什麼位置, 在程序運行之前就寫定了.
好了, 假設我們有一個程序A, A裏的數據被放在0x00地址, 又有一個程序B, B裏的數據也被放在0x00位置. 他們要同時運行, 怎麼辦? 內存的空間放得下兩個程序的數據, 但是我們通過訪問0x00的時候, A程序和B程序都希望訪問到自己的數據, 如果他們一起運行, 內存0x00處到底應該放什麼呢?
所謂虛擬內存, 就是給每個進程一個它自己的映射關係F, 使 $$ 物理內存地址 = F (虛擬內存地址) $$ A和B都在訪問自己的0x00, 但是由於他們的映射關係F不同, 這兩個訪問會訪問不同的物理地址(內存的真正的地址).為什麼要叫虛擬化呢? 因為程序A和B(或者說開發A和B的程序員) 是看不到這個映射關係的. (從時間關係上也沒法看到, 這個映射關係到程序運行的時候才真正確定下來) , 他們就是認為整個機器的4GB內存都屬於他, 他訪問內存使用的全是虛擬內存地址.
操作系統分配和管理這個映射關係
你可能會好奇, 那每一個進程需要的數據到進程運行前一刻才導入內存行不行呢? 運行進程A就把進程A需要的數據全部導入內存, 到需要切換到進程B的時候才把B的數據導入內存行不行呢? 不行, 因為CPU比內存快得多, 這種方式會導致每次CPU切換任務的時候浪費大量的時間把數據填入內存, 那CPU運行多快都沒用了.所有的時間都浪費在等內存了.
怎麼實現虛擬內存管理
我們繞了好大的圈子, 終於說明白了問題在哪. 我們再描述一下我們的問題:
- 我們得給所有每一個的進程一個虛擬的內存映射, 讓它認為從
0x00開始所有的內存都屬於自己, 每一個進程都可以使用從0到4GB的內存空間. - 分配和管理這個映射關係, 讓每一個進程都能訪問到他想要的數據 (這並不簡單 , 舉例說一個一個進程認為自己把數據a保存在
0x04處, 操作系統得做兩件事情來保證他能訪存到) - 把數據a保存在真實的內存的某個地方, 假設是
0x08. - 給進程映射管理裏添加一條F(
0x04) =0x08 - 保證每個進程的訪存不相互幹擾. 更具體一點, 保證進程A不能訪問到進程B在內存中的數據(不然網頁雲音樂就能監視你所有的應用使用情況了)
接下來我要談論具體的方案了, 這部分細節多, 很難避免講的又臭又長, 我建議你可以先跳過去, 或者先看看圖瞭解個大概, 總之我對這一節能不能寫好最沒有把握
在談論具體的方案之前, 你需要先記住這幾個概念: (太不公平了! 我還什麼都沒解決就要記住這麼多概念)
- 32位系統和64位系統: 內存是按Byte訪問的(即訪問內存0讀出的是第0byte,即第0bit到第7bit).所謂32位系統就是指, 內存編址是由一個32bit的數字確定的. 你會發現32bit能描述的最大地址空間就是4GB, 我們基本是基於32位系統做討論.
- 內存虛擬地址, 每個獨立運行的進程看見的內存的地址, 也是編寫應用程序的程序員"看見的"地址.
- 內存物理地址, 數據被實際上保存的地址, CPU訪存的時候, 內存接到的真正的訪存地址( 如果你覺得他們沒有區別, 直接停止閱讀聯繫我, 我上面一定沒寫好)
- 現代解決方案一共有兩套, 兩套解決方案都是需要特殊硬體協助的. 雖然我們強調操作系統是軟體, 但是它會需要和一些特殊的, 應用程序員看不見的硬體打交道. 關於內存管理, 這些特殊硬體都是CPU生產商做在CPU裏的, 是CPU提供的功能.
現代解決方案有兩套, 分別叫做段式管理和頁式管理.你會發現其實他們挺相似. Windows採取的是段式管理 + 頁式管理.Linux採取的是純頁式管理.
段式管理
? 段式管理示意圖
段式管理是比較容易想到的方案. 在這個方案基於一個簡單的映射關係F $$ F : 物理地址 = 虛擬地址 + 基地址偏移 $$ 每個進程訪問的虛擬地址只要加上基地址偏移就能得到數據在內存中物理地址
為了高效實現, 我們需要藉助兩個特殊硬體的幫助
- 段基址寄存器(你還記得寄存器是什麼嗎? 是CPU身邊的存儲介質, CPU訪問它的時間可以忽略不記, 就像你記在大腦裏的知識一樣), 寄存器裏保存一個進程的基地址偏移量, 每次CPU執行到訪問內存的CPU指令的時候, CPU自動加上基地址偏移, 這樣就實現了虛擬地址到物理地址的轉換
- 段長度寄存器: 這個寄存器是保證進程獨立運行的, 每個進程都要申請好自己要使用的內存最大值, 保存在這個寄存器裏, 接下來如果CPU在執行一條訪問內存的CPU指令的時候發現該指令在訪問的地址超過最大值, CPU拒絕執行這條指令. 比如說如果我們作為進程A嘗試訪問一個很大的數字, 這個數字已經超過A申請的運行內存(黃色部分), 那麼這次訪問內存就會被拒絕.
整個訪問內存的流程就是這樣
MMU: Memory management unit, CPU的一部分, 負責和內存管理相關的硬體, 我們剛剛說的檢查訪問是否合法, 添加基地址偏移這些過程都是它去做的.
邏輯地址: 虛擬地址
操作系統的工作就是了解用戶進程申請多少內存, 分配內存, 維護段表(段表裡維護著所有最近可能運行的進程的基地址偏移和最大訪存長度), 總之就是保證每一個進程都能找到自己的物理內存的一切雜活.
頁式管理
你會意識到, 段式管理是建立在運行前申請和分配內存機制之上的.如果你想在進程運行的過程中申請內存, 段式管理就會變得很困難. 可是C/C++確實支持動態分配(C中的malloc, C++中的new), 這部分內存是在運行中才知道需要分配的.( C/C++的靜態數據和動態分配的區別就在這裡, 普通數組長度必須是一個常數, 就是因為這部分長度必須在編譯的時候就確定下來.從而在運行前申請好. 而動態分配的數組長度可以是一個表達式, 即可以在運行到那一句代碼的時候才決定申請內存空間大小).所以我們需要一個可以方便地在運行的時候分配內存空間的方案.
在討論頁式管理的虛擬地址->物理地址映射關係之前, 我們先想一想, 最靈活的映射關係是什麼樣的? 不藉助任何公式, 簡單的記錄每一條映射記錄 應該是最靈活的. 用python說, 就是我們有一個dict 記錄每一個虛擬地址應該映射到某個物理地址.
dict_virtualaddr2pysicaladdr = {
virtualaddr0 : pysicaladdr0,
virtualaddr1 : pysicaladdr1,
virtualaddr2 : pysicaladdr2,
}
但是真的這麼存的話, 需要太多的空間存儲映射關係了. 那麼我們怎麼辦呢? 我們把每4KB的內存空間劃分為一個頁, 從內存0x00處開始給頁編號. 即0x00000000--0x00000FFF是第0頁, 0x00001000-0x00001FFF是第1頁. 你可能已經發現了, 一個32bit的地址, 截前20bit就是頁號.
那麼我們就可以稍微更改一下我們的dict了
dict_virtualpage2pysicalpage = {
virtualpage0 : pysicalpage0,
virtualpage1 : pysicalpage1,
virtualpage2 : pysicalpage2,
}
進程訪問一個32bit的虛擬內存地址的時候, 先用前20bit找到他的物理頁, 再用後12bit作為在頁內的偏移量訪問內存. ( 這個過程實際上是這樣, MMU負責從虛擬地址的前20bit找到物理頁, 這個物理頁也能被20bit長的數字描述, 然後把後12bit連接到得到的物理頁後面, 就得到了要訪問的物理地址)
你會發現頁內偏移是不變的.
操作系統為每一個進程維護它的dict. 確保一切正常運行.
頁式管理如何滿足動態分配呢? 操作系統維護著一個鏈表, 表上的是還空閑的物理頁(每一個節點代表一個物理頁), 每一次進程申請內存(無論是運行前還是運行中) , 操作系統計算進程需要幾個頁, 從空閑鏈表上取下相應數目的物理頁, 把映射關係保存到對應進程裏)
? 頁式管理內存分佈示意圖, 進程A使用了3個頁, 進程B使用了2個頁.
在頁式管理中, 我們需要的特殊硬體叫做cr3寄存器.
我們剛剛保存的dict_virtualpage2pysicalpage, 這個東西叫做頁表, MMU(如果你突然記不得它是什麼, 記住它是CPU裏的一個硬體, 就負責處理內存訪問)需要知道正在運行中的進程的頁表在哪裡, 沒錯, 就是存在cr3寄存器裏.操作系統負責在每一次進程切換的時候更新cr3寄存器.
我們再來想一想, 頁式管理能保證進程獨立運行嗎? 具體一點說,它能保證進程A訪問不到進程B的數據嗎? 只要操作系統維護得當, 這是很容易做到的, 只要保證A進程的頁表使用的物理頁面和B進程使用的物理頁面不同就行. 你會意識到這涉及到空閑頁面的分配和回收.
真實的情況比這個稍微複雜一點, 具體而言, 在32位系統中, 頁表是兩級的, 0-10位在一級頁表中尋找二級頁表入口, 11-20位定址到物理頁面. 如果有人和你談什麼兩級頁表什麼B+樹頁表, 那大概就是在說這個事情, 也很好理解, 大概就是圖這個樣子
? 頁式管理訪存方式
? 真實情況: 二級頁表訪存
你會意識到, 頁式管理機制把一次簡單的訪問內存變成了三次. (訪問一級頁表一次, 訪問二級頁表一次, 訪問數據一次) 這使得性能大幅下降, 等一次內存訪問我們都很難忍受, 等三次是非常過分的事情, 這個我們會有東西去解決, 就是我們談馮諾依曼結構的時候跳過沒談的cache.
好了, 到現在, 我們談論的虛擬化可以告一段落了. 還記得我們一開始為什麼要談論虛擬化嗎? 我們想讓每一個應用都覺得它在佔有硬體, 獨立的在運行, 為此我們創造了進程的概念, 進程是一個應用程序運行需要的環境, 我們為一個進程分時復用了CPU, 虛擬出了只屬於它的內存映射, 這樣我們的程序就能獨立地跑起來了.
進程和線程
我們已經討論過什麼是進程了. 一個進程是一個應用程序獨立運行需要的虛擬環境, 比較術語的說法是: 進程是資源分配的單位. (什麼是資源呢? CPU時間, 內存空間, 一個程序運行需要的所有硬體都叫做資源, 你會發現操作系統就是做資源管理的) 在一段時間內, 可能有多個應用程序要求運行, 這個時候, 操作系統決定什麼時候誰應該運行. 這個過程叫做進程調度.
進程調度
你已經發現操作系統能夠營造"多個進程共同運行"的假象了.我們再理一理這個假象是怎麼製造出來的.
進程切換
我們只有一套硬體, 只能有一個進程運行在其上. 操作系統決定哪個進程現在得到運行的權利. 假設我們同時提交了三個進程A,B,C要運行. 這三個進程進入操作系統的就緒隊列, 操作系統可以從中選一個開始運行(依據調度演算法),假設我們現在選取A運行 .在A進程運行的過程中, 操作系統可以切入, 停下A(你可能想像, 這需要把A的當前寄存器保存在內存某處, 以便等等A繼續運行) , 選取B, 讓B運行(如果你還記得上一節虛擬內存的內容, 這裡需要將B的頁表入填入CPU的cr3寄存器中華) . 這個過程叫做進程的切換.
進程狀態
進程狀態主要是表示現在進程是否在運行的, 理論上可能有這麼幾種狀態:
- 運行 進程佔據硬體, 正在運行
- 就緒 進程處在隨時可以運行的狀態, 等待操作系統選中
- 阻塞 進程因為等待某個事件, 到條件成熟之前都不能繼續運行, 比如進程等待硬碟讀取, 或者進程等待網路消息
- 掛起 之前三個狀態的進程, 他們的數據和代碼都是在內存中的, 有時候內存不夠用, 我們可以把某個進程的代碼和數據寫入硬碟, 從而清空它佔據的那部分內存, 這樣的進程狀態叫做掛起
這只是理論上的進程狀態，實際上依據操作系統的不同， 實現的進程狀態會有所區別。
為什麼需要調度?
操作系統是一個大而且複雜的軟體, 軟體中沒有功能是先於需求產生的, 當你看到操作系統的某個特性的時候, 可以先想一想, 沒有它行不行? 這樣可能有助於你瞭解功能. 那麼沒有調度行不行呢?
假如操作系統不調度， 進程A， B， C就依據提交的順序一一運行， A運行完， B開始運行， 這樣行不行呢？ 行。 正確性是毋庸置疑的。但是效率會有一些問題， 假如A在運行中讀了硬碟， CPU就有一直等到磁碟數據返回， 才能繼續工作， CPU的時間是非常寶貴的， 我們不希望等待， 所以我們做了一個機制， A讀硬碟的時候，操作系統介入， 把A的狀態改為阻塞， 在就緒的進程（B和C） 中選擇一個運行（假設是B）。 直到A讀取的硬碟返回數據， 操作系統再把A的狀態改成就緒， 等待下一次選到它運行。 這樣， CPU就可以去跑B的程序， 而不至於等待。 你會意識到， 有了調度， A， B， C都運行完需要的時間減少了。
進程怎麼調度有很多標準（比如是盡量公平的讓每個進程運行相同的時間， 還是某個進程有優先順序應該運行更長的時間）, 依據不同的標準又有很多的調度演算法. 通常跑在你我計算機上的調度機制叫做時間片輪轉.時間片輪轉基於這麼一個統計規律: 一個進程(一個計算任務) 中, 只有前2-8 毫秒是計算密集的, 換言之只有這段時間是需要CPU的， 接下來進程就很可能要讀硬碟， 或者等待網路了。 基於此， 我們設定一個時間片（一般是5毫秒），每間隔一個時間片， 操作系統打斷一次運行的進程， 進行一次進程切換。
你會意識到， 時間片輪轉只設定了每個進程每次能運行多長時間（一個時間片）， 並沒有解決如何在就緒進程隊列中選一個開始運行的問題。 解決這個問題的東西叫做進程調度演算法 。我們不打算在這裡討論進程調度演算法，其實很多情況下簡單的先來先服務就能工作得不錯。
線程
什麼是線程呢？ 你作為程序員可能已經接觸了一些多線程編程的概念。 比如伺服器為每一個TCP連接創建一個線程，他們總是告訴你多線程比單線程快， 但也有所謂「線程安全問題」， 那麼什麼是線程呢？
我們回到進程切換， 從進程A切換到進程B的時候， 需要更改CPU的cr3寄存器， 從而更改虛擬內存映射，假設兩個進程共享一套虛擬內存， 這部分的開銷是不是就可以省去？ （實際上省去的開銷不只是更改一個寄存器這麼簡答， cache會清空，而這個硬體是保證我們高速訪問內存的關鍵， 我們往後會談論一下cache）
答案是肯定的。 那麼下一個問題就是， 什麼樣的計算任務是需要在同一套內存映射下做不同計算的？ 或者說的更貼近程序員一點， 什麼樣的計算任務是需要在同一套數據下跑不同代碼的？ 你會發現這種情況還蠻多。 比如說遊戲就是這樣， 所有的人物都在一個環境下， 每一個人物的行為需要單獨計算。
好了， 你可能意識到什麼是線程了。 線程就是共享虛擬內存映射的進程， 實際上， 多個線程從屬於一個進程， 這些線程都共享進程的虛擬內存映射。 但是每個線程在計算調度上是獨立的。 舉個例子， 一個遊戲進程擁有ABCD四個線程， 代表4個人物， 計算人物行為這個任務就變成了在操作系統ABCD四個線程中間調度（線程調度和我們剛剛談論的進程調度幾乎完全一致， 只是更節省時間）。實際上， 線程纔是調度的單位。 操作系統在做調度的時候， 考慮的是某個線程是不是應該開始運行了。 （你會發現這打破了你剛剛進程那裡理解到的知識。 事情就是這樣， 操作系統是一個不斷生長的東西， 很多東西都是縫縫補補產生的）
這是底下真正發生了什麼， 那麼一個上層的程序員看見的線程是什麼樣子的呢？ 一個程序員為他的計算任務申請了多個線程， 給每一個線程指定計算任務（比如計算某個人物的行為， 或者向網路發送什麼信息）， 然後他就可以認為這些線程全都在並行的，同時的執行了。 這是操作系統提供的抽象。
線程安全問題
線程安全問題發生在一個這樣的場景下： 多個線程需要讀寫同一個數據， 而且這樣的讀寫是需要以某種順序進行的，但是編程人員沒有寫出足夠好的代碼保證運行時候一定是這個順序。 最典型的例子就是搶票問題， 假設兩個線程A，B分別服務兩個人的訂票需求， 這時候內存裏有一個數字left表示剩餘票數量， 假設我們這個時候只有一張票了，A和B的行為如下
# 節點 0
if(left > 0):
# 節點 1
left = left - 1
# 節點 2
return "訂票成功"
else
return "沒有剩餘票"
正確的線程運行順序是A先運行(假設A先到), A返回訂票成功, B再運行, B這時候發現已經沒有剩餘票, B訂票失敗. 但是我們剛剛聊過調度的機制很多時候是時間片輪轉, 這個時候就可能出現這樣的順序: A運行到節點1, 這時候發生了線程調度, 切換到B, B查看left == 1, B訂票成功, 然後調度回A繼續運行, A繼續訂票, 也訂票成功. 我們只有一張票, 但是兩個乘客都訂票成功了.
有一些機制可以讓你避免這樣的問題, 它們可能叫做"信號量", "臨界區", 或者"原子操作" , 大的思路都是設定一個代碼區域, 在這個區域中不允許操作系統調度. 比如這個問題, 只要指定節點0到節點2之間不允許調度發生(不允許線程切換)就能解決. 但是線程安全問題是很難完美解決的. 而且出了問題也很難debug(因為難以重現發生錯誤時候的線程運行順序). 這是線程的弊端.(go語言中內置了一個叫做協程的機制, 聽說可以解決這個問題, 但是我還沒學會)
談談cache
從我們的存儲結構層級開始
我們剛剛已經談過, CPU寄存器的讀取速度是內存的十倍, 這意味著每次我們想要把數據讀入寄存器, 都需要等待很長時間, 粗略的估計, 我們認為讀取CPU寄存器的時間不影響CPU指令的執行, 那麼我們大概可以認為CPU執行一條指令的時間和讀取CPU寄存器的時間相同, 這麼估計的話每次從內存讀取數據, CPU等待的時間足夠它執行十次計算, 這不是我們願意看見的.
程序的局部性原理
舉一個類似的情況, 假設你在圖書館裡, 正在為了寫你的某一篇論文傷神. 你每次寫到不確定的地方就站起來去圖書館的書架上查書, 查書這個動作非常耗費你的時間, 這時候你可能會借走幾本你最需要的書放在你手邊, 當你需要查書的時候, 優先從手邊的書裏查.如果把內存裏的數據比作圖書館裡的藏書, 你借到手邊的書就是cache.你能從上圖中看見cache的讀取速度遠快於內存, 就像你翻手邊的書總比去圖書館書架上查書要快一樣.因為你的論文總是有某個確定的(還很可能是狹窄的)主題, 當你查書的時候, 你借到手邊的幾本書能覆蓋你絕大部分的需求, cache基於同樣的原理工作, 某一段代碼需要的數據很可能只是內存裏的一小部分, 只要這一部分都放進cache裏,我們就不用每次都訪問內存了, 這樣程序運行的速度能大大加快.
程序的局部性原理主要包括兩條:
- 時間局部性, 程序訪問過的數據短時間內很可能再次訪問
- 空間局部性, 程序傾向於訪問剛剛訪問過的數據的附近的數據.
舉一個簡單的例子, 假如你想把某個列表裡的數字列印5遍, 代碼如下
T = [1, 2, 3, 4, 5]
for i in range(5):
for num in T:
print(num)
時間局部性指的是列表T裏的元素1在第一次訪問之後馬上就要被第二次訪問, 我們只要保證第二次訪問的時候1在cache裏, 就能減少訪問內存的時間開銷.
同樣的, 假設列表T裏的元素是順序擺放在內存裏的, 空間局部性指的是訪問完元素1之後馬上要訪問元素2,實際上最好的情況是我們在訪問元素1的時候就把整個列表T讀入cache中.
你可以把cache理解為一個硬體實現的dict, key是在內存地址, value是數據.每次我們訪問內存的時候, 就順手多拿出附近的數據放在cache裏(硬體可以把傳輸的帶寬做大一點, 一次性並行地讀取很多數據), 這樣就能顧及到空間局部性. 時間局部性是由替換演算法決定的, 現在最流行的替換演算法是最不頻繁替換, 思路是在cache中有一個bit標記某個數據是不是被訪問了,這個bit一段時間刷一次零, 每訪問一次就置1, 當我們需要覆蓋cache裏的數據的時候, 覆蓋那些對應bit為0的數據. 這個演算法能大概地替換出訪問不是那麼頻繁的數據(或者說訪問頻繁的數據更可能留在cache中) .為什麼不真的開一個整數去計數訪問次數呢? 因為cache裏的存儲空間很貴, 而且現在的演算法就夠好了, 精細地追蹤訪問情況意味著更多的變數要維護, 意味著時間開銷更大.
程序的局部性原理是比時間複雜度更細節一些的演算法時間估計思路, 同樣的時間複雜度, 實現得更有局部性的演算法速度肯定更快. 這個理論可以部分解釋為什麼都是O(log(n))的演算法, 某些排序就是比另一些快. 但是我從來沒有見到過在寫程序的時候真的需要去考慮程序局部性的項目. 現代編譯器已經非常智能, 可以優化一些簡單的情況(比如矩陣乘法), 而且很多時候把程序寫對就已經不容易了.
補充一個八卦, 上課時候老師聊到, 求交集演算法中有一個例子:
求A和B集合的交集, 實際上是這麼做的:
對每一個元素a屬於A, 查找a是不是在B中.
這樣就變成一個查找問題, 在集合B中查找元素a, 這個時候從演算法上來說二分查找的速度遠超過順序查找, 但是二分查找訪問內存是沒有局部性的.(你很容易想像, 二分查找訪問是跳來跳去的), 在有cache加成之後,順序查找的速度會超過二分查找. 搜索引擎中的類似演算法都是採用順序查找.
講這個事情的老師是個靠譜人, 但是我自己不太相信,可能背景沒說清楚, 畢竟複雜度差距擺在那裡
談cache是因為這個東西無處不在, 它是一個通用的解決思路, 面向的是這麼一個問題:
我們有兩個讀寫速度有較大差異的存儲介質, 我們想要把兩種介質組合起來使用, 但是又想要讀寫速度相對快一些.
說著說著你就會發現存儲介質層級表裡還有一個類似的關係: 內存 -- 硬碟
沒錯, 為了提高讀寫硬碟的速度. 我們也做了一個cache一樣的東西, 只是這個東西是軟體做的. 操作系統會管理一個叫做頁緩存的東西, 存儲在內存的某個部分, 每次讀寫硬碟的時候就做一些剛剛說過cache會做的工作. 實際上你調用write函數, 函數在把你要寫的東西寫進頁緩存裏就返回了.(不然你每次調用write函數會等待更長的時間) .這些內容真正寫入硬碟的時間是操作系統定的. 這是早年windows安全彈出U盤之前不能拔出U盤的原因, 你申請安全彈出的時候, 操作系統會趕緊把相關的頁緩存寫進U盤裡, 如果你在安全彈出之前就拔出了U盤, 那頁緩存裏的數據可能還沒有寫進U盤裡, 你以為複製成功的文件實際上可能並沒有真正寫入U盤.(現在這個問題修復了, windows發現你是U盤之後寫就跳過頁緩存直接寫入U盤了, 所以你大概率試不出來)
好了. 談完cache之後, 你可能更理解線程切換比進程切換快在哪裡了, 從進程A切換到進程B, cache是需要清空的. 這是進程運行獨立要求的. 如果cache不清空, B就能訪問到A的數據了, 這是我們在設計進程的時候一定要避免的. 從屬於同一個進程的線程C和D, 因為他們本來就共享同一個虛擬內存映射, 本來也應該互相能夠訪問對方使用的數據, 所以這個時候cache是不用清空的.
中斷和系統調用
中斷和系統調用解決的是計算機和各種外設交互的問題.
我們在進程一節已經說過操作系統能調度進程, 把正在運行的進程停下來, 換另一個進程開始執行. 這在你和朋友尬聊不下去,只好拿出手機瘋狂在微博, 微信和嗶哩嗶哩之間反覆跳躍的時候經常發生.
在我之前的敘述中, 你會覺得操作系統是一個無所不能的老大哥, 隨時都在監視你的計算機使用, 但是我們談過, 操作系統只是軟體而已, 操作系統想要提供服務, CPU必須跑操作系統的代碼, 和普通的進程沒什麼差別.
那麼問題就來了, 在兩個進程切換中間, 操作系統確實接管了, 可是它什麼時候接管的呢? 或者從硬體的角度上來說. CPU怎麼怎麼知道需要跑操作系統的代碼了?
中斷
中斷是一個硬體實現的機制, CPU能接收外界的信號, (你可以認為是一個整數), 根據整數在中斷向量表中選擇一項, 跳轉到對應的中斷處理函數.
中斷是允許其他設備和CPU交互的機制, 每次你點擊屏幕, 中斷就會發生, 這個時候操作系統介入, 判斷你點擊的是某個app, 去切換進程.
總結一下, 中斷是操作系統接管的機會, 但是不是所有中斷都會跳到操作系統接管. 一個中斷髮生之後CPU跑什麼代碼是由中斷向量表決定的. 這需要硬體工程師和操作系統工程師的協調.
除去人機交互, 中斷也廣泛應用於硬碟讀取, 網卡交互等等事情, 每次讀取硬碟就是給硬碟一個讀取坐標, 硬碟把數據讀出來, 發起中斷,告訴CPU它讀完了. 這樣的好處是CPU在硬碟尋找數據的過程中可以去做別的事情.
系統調用
系統調用是一種特殊的中斷. 它發生在應用進程想要操作系統為它提供服務的時候. 比如read和write函數. 應用不用管一系列的頁緩存, 硬碟等等東西, 它只需要調用read, 這個時候軟體產生一個中斷, 操作系統介入為它完成接下來的事情. 網路相關的事情也是這樣實現的, 應用程序只需要調用send和recv 函數就可以了.像這樣, 操作系統告訴你它能夠提供什麼服務的一類東西就叫做操作系統的API. 因為操作系統是C語言實現的, 提供的這類API一般也是C語言.
文件系統
應用程序讀文件是怎麼樣子的?
with open(D:\lion_ide\py_1\material.txt) as file:
data = file.read(100)
應該分兩步:
- 提供一個路徑(相對或者絕對), 打開文件.
- 提供一個數字, 表示需要讀取多少位元組.
對應的,用戶看見的文件系統應該包括兩個部分:
- 一顆文件樹, 盤符是樹根(windows這種允許多個盤符的文件系統就是多顆文件樹,Linux就只有一顆文件樹 ).文件樹的枝丫就是路徑, 你總能由一個路徑找到一個指定的文件(要不然就能確定它不存在). 你能使用相對路徑是因為每個進程會保存一個自己的默認路徑, 相對路徑是相對它而言, 比如python的相對路徑是
.py文件所在的路徑, C和C++的相對路徑是編譯鏈接生成的最後的.exe文件所在路徑(當然你使用集成開發環境的話會有一些不一樣, visual studio 的默認路徑就是它的工程文件夾). - 一個文件的抽象. 文件被抽象成一維的結構. 有一個文件的開頭, 有一個
EOF結束標誌, 中間就是一根數軸. 你讀取的時候只需要聲明自己想從哪裡開始讀取, 讀取多少個位元組. (很多時候你不需要提供自己想從哪裡開始讀取, 是因為每一個進程都保存一個自己打開文件的當前文件指針, 你不顯式提供從哪裡開始, 操作系統就自動從保存的文件指針處開始)
這是文件系統提供給你的抽象, 文件系統需要面對的硬體是什麼情況?
硬碟的結構可以認為是二維的. 碟片是圓形的, 按照極坐標描述, 沿著極軸的方向劃分不同的磁軌, 沿著極角劃分扇區.讀寫磁碟的時候提供的就是一個(磁軌, 扇區) 二元組, 其實就是一個極坐標下的坐標.
文件系統得想辦法在磁碟上做出你看見的抽象.
推薦閱讀：
