阿裡巴巴-作業系統

記憶體管理

• 簡述程序切換的流程

如果想要從A程序切換到 B 程序，必定要先從使用者态切換到核心态，因為這個切換的工作你不能讓使用者程序去實作，不然當 CPU 在使用者程序手上的時候，他可以選擇一直執行，不讓出 CPU，這肯定是不允許的。是以作業系統需要先挂起正在占用 CPU 的 A 程序，才能切換到 B 程序。

由于從使用者态切換到核心态的時候，CPU 是在使用者程序手中，是以這個是通過硬中斷來實作的。在從使用者态切換到核心态之前需要儲存使用者程序的上下文，以便下一次執行時可以繼續之前的工作。

這個上下文就是程序執行的環境，包括所有的寄存器變量，程序打開的檔案、記憶體資訊等。一個程序的上下文可以分為使用者級上下文，寄存器上下文，系統級上下文。使用者級上下文存儲的是使用者程序的記憶體資料以及堆棧資料等；寄存器上下文是一些通用寄存器；系統級上下文是核心棧、PCB (程序控制塊)等。

• 程序在位址空間中會劃分為哪些區域

這個問題在我之前的工作中其實還是有所涉及的，我來簡單講一下把檔案加載到記憶體中的一個過程，以 Window 平台為例吧，PE 檔案我比較熟，在 PE 檔案中，有一個叫節的概念，節是PE檔案中存放代碼和資料的基本單元，用以存儲不同類型的資料，比如 data 節、code 節等，一個節的所有原始資料必須加載到連續的記憶體空間裡，這也就造成了在虛拟位址空間中的區塊劃分。

在虛拟位址空間中會按照節劃分為代碼段、資料段、未初始化的資料段以及堆棧這些區塊。

• 棧與堆有什麼差別

我們常說堆棧堆棧，其實堆棧是兩個不同的概念，最直覺的了解，堆是由使用者來控制的，我們可以使用 malloc 這種指令來在堆中申請記憶體，而棧是由作業系統控制的，在棧中存儲的是這個程序的局部變量等，比如我們用 malloc 來申請一塊記憶體，記憶體本身是在堆中開辟的，而指向這塊記憶體的指針存儲在棧中。

作業系統為什麼分核心态和使用者态，這兩者之間如何切換

涉及公司：拼多多實習生

因為在CPU的指令中，有一些是非常危險的，比如清理記憶體、設定時鐘等，如果所有的程式都能使用，就可能造成系統的崩潰，是以，CPU 将指令分為特權指令和非特權指令，對于那些危險的指令，隻允許作業系統使用。CPU 的特權級别有四級，從 Ring0 到 Ring3，正常使用時一般隻有兩級，即使用者态的 Ring3 和核心态的 Ring0。Ring3 狀态不能通路 Ring0 的位址空間，包括代碼和資料。

• 使用者态切換到核心态的三種方式

1. 系統調用（系統調用是通過軟中斷實作的）
2. 中斷（硬）
3. 異常

• malloc的實作機制

malloc 本質上是維護了一個記憶體空閑連結清單，每次我們調用 malloc 申請空間的時候，連結清單就會從頭開始周遊，來尋找一個合适的空閑記憶體空間，然後把這個空間給分割開，一部分配置設定給使用者，另一部分繼續标注為空閑，而當沒有足夠大的空閑塊時，malloc 就會通過系統調用來申請更多的記憶體塊。而我們調用 free 來釋放記憶體塊的時候，該記憶體塊就會回到連結清單中，并且相鄰的記憶體塊會被合并。

搜尋空閑塊的算法主要有首次适配、下一次适配、最佳适配，首次适配即第一次找到足夠大的記憶體塊就配置設定，但這樣會産生很多的記憶體碎片，也是以第二次适配被提出來緩解這個問題。另一個極端則是最佳适配，即找到一塊剛好大于我們所需記憶體大小的記憶體塊，這種做法一方面耗時長，另一方面也會産生一些極小的記憶體碎片。

這兩種思路可以看出是在性能和空間使用率上尋找一個平衡點，在工程中實際上有很多這種沒有完美解決方案，隻能尋找平衡的問題。

• 虛拟位址怎麼映射到實體位址

虛拟位址的構成為頁目錄索引 (10位) +頁表索引 (10位) +表内偏移 (12位)

以 win32 系統為例，頁目錄和頁表都為 1024 個，頁表大小為 4KB，一共是 4G 的虛拟記憶體空間

而從虛拟位址映射到實體位址實際上就是通過頁目錄和頁表的索引找到記憶體頁。

在頁表項中有一位标志位，用來辨別包含此資料的頁是否在實體記憶體中，如果在的話，就直接做位址映射，否則，抛出缺頁中斷，作業系統會把次資料頁調入記憶體。

• socket 程式設計中怎麼處理并發請求

對多線程的處理與單線程不同的位置在于各個不同的程序可能會通路相同的資源，如果是對資源進行修改的話，就需要用到鎖

• 簡述 IO 多路複用

Linux的IO通路通常是先将資料拷貝到作業系統的核心緩沖區，然後再從核心緩沖區拷貝到應用程式的位址空間。在這兩個階段中，有不同的 IO 方式，主要分為阻塞 IO、非阻塞 IO、異步 IO 以及 IO 多路複用。

阻塞 IO 即當資料還未準備好，也就是資料還在作業系統的核心緩存區時，使用者程序就會一直阻塞，等待資料從作業系統核心緩沖區拷貝到應用程式的位址空間。阻塞IO在這兩個階段都是阻塞的。

非阻塞 IO 則是如果資料還沒準備好，作業系統會給應用程式傳回一個 error，并不阻塞應用程式，而一般應用程式會持續詢問核心資料是否準備好，是以從另一個角度來說也是阻塞的。

而異步 IO 才是真正的不阻塞，當使用者程式發起read後，作業系統會立即進行回複，這樣使用者程式就可以去做其他事情，當資料被拷貝到使用者程式的地中空間後，作業系統會給使用者程式發一個信号，而使用者程式可以采用回調函數的方式對這個信号進行響應。

IO 多路複用則是允許一個程式同時等待多個檔案描述符，當任意一個檔案描述符就緒，select 函數就會傳回，當然 IO 多路複用在本質上還術語阻塞IO，隻不過可以同時進行多個 IO 操作。

Linux 的 IO 多路複用機制中有 select、poll、epoll 三種，

select 和 poll 的時間複雜度都是 O(n),因為他們都是在對IO清單進行輪詢，不同點在于 select 能監視的檔案描述符有上限，一般為 1024，當然這個是在 Linux 核心中進行的宏定義，是可以修改的，而 poll 是基于連結清單來存儲的，是以沒有這個上限。

而 epoll 是基于事件驅動的，是以不需要輪詢，epoll 會把事件和每一個IO流對應起來。并且 epoll 是通過一塊共享記憶體來實作核心空間和使用者空間的通信的，比起 select 和 poll 的大量資料拷貝效率更高。

不過 lect 的優點在于相容不同的作業系統，而 poll 和 epoll 都隻能在 linux 上使用。

• 簡述程序通信的各種方法

程序間通信的方式通常分為管道、系統 IPC、套接字三種，其中管道有無名管道、命名管道，系統 IPC 有消息隊列、信号、共享記憶體

無名管道的本質是在核心緩沖區的環形隊列，每次讀取資料後緩沖區都會移動，并且無名管道隻能在有親緣關系的程序間使用

命名管道則以檔案的形式存在，由于有一個路徑名，使用沒有親緣關系的程序間也可以使用命名管道

消息隊列是存放在核心中的消息連結清單，具有特定的格式，支援多種資料類型，且允許多個程序進行讀寫

信号是軟體層次上對中斷機制的一種模拟，是一種異步通信方式，并且信号可以在使用者空間程序和核心之間直接互動

共享記憶體顧名思義就是兩個進行對同一塊記憶體進行讀寫，是最快的 IPC 形式，但不适合大量的資料傳輸

Socket 是對 TCP/IP 協定族的封裝，不僅可以用于本機上的程序間通信，更多的被用于網絡通信中

程序線程管理

程序的互斥與同步

在作業系統中，程序是占有資源的最小機關，對于那種隻能同時被一個程序持有的資源我們稱為臨界資源，對于臨界資源的通路，必須是互斥的。（對于；臨界資源的通路過程分為：進入區、臨界區、退出區、剩餘區）

而程序之間通路臨界資源時可以構成同步與互斥兩種關系，同步即兩個程序的資源通路必須是先後關系，比如經典的生産者消費者問題，讀者寫着問題。而互斥則是兩種在進行資源搶到，比如購票問題。

通常在軟體層面可以使用替換算法來實作，即每個程序持有一個标志，每次當使用資源時則将自己的标志與資源的标志互換，如果在互換的過程中發現自己獲得的标志是正在使用的狀态，則在此循環等待。這種方法的缺點在于每個程序都需要進行循環等待，比較低效。是以一般是通過硬體層面的信号量即PV操作來實作程序的臨界資源管理。

• 死鎖的解決方法

死鎖的産生是在這樣一種環境中：比如我們有兩個程序AB，他們都需要資源1和資源2，當程序A持有資源1，進線程B持有資源2的時候，他們都需要對方手上的程序，而一般作業系統又不允許搶占，這個時候就發生了死鎖。

從這個例子中其實可以總結出死鎖的幾個必要條件：

1. 一個資源隻能被一個程序所占有，不能共享
2. 一個線程請求資源失敗時，它會等待而不是釋放
3. 一個線程在釋放資源之前其他程序不能搶奪資源
4. 循環等待

從死鎖産生的原因未明可以設計一些方法去避免死鎖的發生

1.靜态配置設定資源，一開始就把一個程序所需的全部資源都配置設定給它，但這樣會降低資源的使用效率

2.允許搶占，需要設定程序的不同優先級，高優先級的程序可以搶占低優先級的程序的資源

3.把資源進行編号，申請資源必須按照資源的編号順序來申請

如果死鎖已經發生了，就需要去解開死鎖，其本質思想就是配置設定資源打破循環等待

• 程序排程算法

• 頁面排程算法