什麼是作業系統? 為什麼說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
- 配置設定和管理這個映射關系, 讓每一個程序都能通路到他想要的資料 (這并不簡單 , 舉例說一個一個程序認為自己把資料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申請的運作記憶體(黃色部分), 那麼這次通路記憶體就會被拒絕.
整個通路記憶體的流程就是這樣
: 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_idepy_1material.txt') as file:
data = file.read(100)
應該分兩步:
- 提供一個路徑(相對或者絕對), 打開檔案.
- 提供一個數字, 表示需要讀取多少位元組.
對應的,使用者看見的檔案系統應該包括兩個部分:
- 一顆檔案樹, 盤符是樹根(windows這種允許多個盤符的檔案系統就是多顆檔案樹,Linux就隻有一顆檔案樹 ).檔案樹的枝丫就是路徑, 你總能由一個路徑找到一個指定的檔案(要不然就能确定它不存在). 你能使用相對路徑是因為每個程序會儲存一個自己的預設路徑, 相對路徑是相對它而言, 比如python的相對路徑是
.py
.exe
- 一個檔案的抽象. 檔案被抽象成一維的結構. 有一個檔案的開頭, 有一個
EOF
這是檔案系統提供給你的抽象, 檔案系統需要面對的硬體是什麼情況?
硬碟的結構可以認為是二維的. 盤片是圓形的, 按照極坐标描述, 沿着極軸的方向劃分不同的磁道, 沿着極角劃分扇區.讀寫磁盤的時候提供的就是一個(磁道, 扇區) 二進制組, 其實就是一個極坐标下的坐标.
檔案系統得想辦法在磁盤上做出你看見的抽象.