[[384581]]

問題一、操作系統的基本特征

1、并發

并發指一段時間內能同時運行多個程序，并行指同一時刻能運行多個指令。操作系統通過引入進程和線程，使得程序能夠并發運行。

2、共享

共享是指系統中的資源可以被多個并發進程共同使用。它主要有兩種共享方式：互斥共享和同時共享。多個應用并發執行的時候，宏觀上要體現出它們在同時訪問資源的情況，而微觀上要實現它們的互斥訪問。比如說我們說到的內存。

3、虛擬

虛擬技術把一個物理實體轉換為多個邏輯實體。利用多道程序設計技術(程序的交替運行)，讓每個用戶都覺得有一個計算機專門為他服務。主要有兩種虛擬技術：時間復用技術和空間復用技術。

時間復用技術是指多個進程能在同一個處理器上并發執行，讓每個進程輪流占用處理器，每次只執行一小個時間片并快速切換。

空分復用技術值將物理內存抽象為地址空間，每個進程都有各自的地址空間。當需要一個地址空間時，如果沒有那就執行頁面置換算法。

4、異步

異步指進程不是一次性執行完畢，而是走走停停，以不可知的速度向前推進。但只要運行的環境相同，OS需要保證程序運行的結果也要相同。

問題二、進程與線程的本質區別、以及各自的使用場景(重要)

1、進程

進程是資源分配的基本單位。就好比是手機上的一個個應用程序。

2、線程

線程是獨立調度的基本單位。一個進程中可以有多個線程，它們共享進程資源。

3、進程和線程的理解

QQ 和瀏覽器是兩個進程，瀏覽器進程里面有很多線程，例如 HTTP 請求線程、事件響應線程、渲染線程等等，線程的并發執行使得在瀏覽器中點擊一個新鏈接從而發起 HTTP 請求時，瀏覽器還可以響應用戶的其它事件。

4、進程和線程的區別

(1)資源分配

進程是資源分配的基本單位，但是線程不擁有資源，多個線程可以共享進程資源。

(2)資源調度

在同一進程中，線程的切換不會引起進程切換，從一個進程中的線程切換到另一個進程中的線程時，會引起進程切換。就好比是打開了QQ，又打開了瀏覽器。

(3)系統開銷

線程不占用系統資源，比進程開銷更小效率更高。這是因為創建或撤銷進程時，系統都要為之分配或回收資源，如內存空間、I/O 設備等，切換進程時候，還要保存CPU狀態。

(4)對于一些要求同時進行而又共享某些變量的并發操作來說，只能用多線程，不能用多進程。

問題三：進程的幾種狀態

進程主要是三種狀態。

(1)就緒。進程已經獲得了除CPU以外的所有所需資源，等待分配CPU資源

(2)運行。已獲得了CPU資源，進行運行。處于運行態的進程數<=CPU核心數

(3)阻塞。進程等待某些條件，在條件滿足前無法執行

在這里我們最主要的是狀態之間的切換，比如說阻塞狀態是不能到運行狀態的。

問題四：常見的進程同步方式和線程同步方式

1、進程同步的方式

(1)為什么要進程同步

多進程雖然提高了系統資源利用率和吞吐量，但是由于進程的異步性可能造成系統的混亂。進程同步的任務就是對多個相關進程在執行順序上進行協調，使并發執行的多個進程之間可以有效的共享資源和相互合作，保證程序執行的可再現性。

(2)同步機制需要遵循的原則：

空閑讓進：當沒有進程處于臨界區的時候，應該許可其他進程進入臨界區的申請

忙則等待：當前如果有進程處于臨界區，如果有其他進程申請進入，則必須等待，保證對臨界區的互斥訪問

有限等待：對要求訪問臨界資源的進程，需要在有限時間呃逆進入臨界區，防止出現死等

讓權等待：當進程無法進入臨界區的時候，需要釋放處理機，邊陷入忙等

(3)進程同步的方式：原子操作、信號量、管程。

2、線程同步方式

(1)互斥(信號)量，每個時刻只有一個線程可以訪問公共資源。只有擁有互斥對象的線程才能訪問公共資源，互斥對象只有一個，一個時刻只能有一個線程持有，所以保證了公共資源不會被多個線程同時訪問。

(2)信號量，允許多個線程同時訪問公共資源。當時控制了訪問資源的線程的最大個數。

(3)事件 in windows(條件變量 in linux)。通過通知的方式保持多線程的同步，還可以方便的實現多線程優先級的比較

(4)臨界區。任意時刻只能有一個線程進入臨界區，訪問臨界資源。

問題五、進程間的通信方式

windows和linux是不一樣的。

問題六、進程任務調度算法的特點以及使用場景

(1)時間片輪轉調度算法(RR)：給每個進程固定的執行時間，根據進程到達的先后順序讓進程在單位時間片內執行，執行完成后便調度下一個進程執行，時間片輪轉調度不考慮進程等待時間和執行時間，屬于搶占式調度。優點是兼顧長短作業;缺點是平均等待時間較長，上下文切換較費時。適用于分時系統。

(2)先來先服務調度算法(FCFS)：根據進程到達的先后順序執行進程，不考慮等待時間和執行時間，會產生饑餓現象。屬于非搶占式調度，優點是公平，實現簡單;缺點是不利于短作業。

(3)優先級調度算法(HPF)：在進程等待隊列中選擇優先級最高的來執行。

(4)多級反饋隊列調度算法：將時間片輪轉與優先級調度相結合，把進程按優先級分成不同的隊列，先按優先級調度，優先級相同的，按時間片輪轉。優點是兼顧長短作業，有較好的響應時間，可行性強，適用于各種作業環境。

(5)高響應比優先調度算法：根據“響應比=(進程執行時間+進程等待時間)/ 進程執行時間”這個公式得到的響應比來進行調度。高響應比優先算法在等待時間相同的情況下，作業執行的時間越短，響應比越高，滿足段任務優先，同時響應比會隨著等待時間增加而變大，優先級會提高，能夠避免饑餓現象。優點是兼顧長短作業，缺點是計算響應比開銷大，適用于批處理系統。

問題七、死鎖的原因、必要條件、死鎖處理、手寫死鎖代碼、java是如何解決死鎖的

1、死鎖的原因

在兩個以上的并發進程中，如果每個進程都持有某種資源而又等待其他進程釋放他們持有的資源，在未改變這種狀態前，誰都無法推進，則發生了死鎖。就好比是對方相互拿著自己需要的資源，都不釋放自己的。

2、產生死鎖的四個必要條件

(1)互斥。一個資源一次只能被一個進程占有

(2)請求與保持。一個進程因為請求資源而阻塞時，不釋放自己持有的資源

(3)非剝奪。無法在進程結束前剝奪它對資源的所有權

(4)循環等待。若干進程收尾相接形成環形等待關系

3、死鎖處理

(1)預防死鎖。破壞后三個條件中的一個即可(互斥是非共享設備的特性，無法更改)：

(2)死鎖避免。避免死鎖并不是事先采取某種限制措施破壞死鎖的必要條件，而是再資源動態分配過程中，防止系統進入不安全狀態，以避免發生死鎖，比如銀行家算法、系統安全狀態、安全性算法。

(3)死鎖的檢測與解除：資源分配圖死鎖定理死鎖解除。

4、死鎖代碼

(1)使用信號量實現生產者-消費者

為了同步生產者和消費者的行為，需要記錄緩沖區中物品的數量。數量可以使用信號量來進行統計，這里需要使用兩個信號量：empty 記錄空緩沖區的數量，full 記錄滿緩沖區的數量。其中，empty 信號量是在生產者進程中使用，當 empty 不為 0 時，生產者才可以放入物品;full 信號量是在消費者進程中使用，當 full 信號量不為 0 時，消費者才可以取走物品。

#define N 100 
typedef int semaphore; 
semaphore mutex = 1; 
semaphore empty = N; 
semaphore full = 0; 
 
void producer() { 
    while(TRUE) { 
        int item = produce_item(); 
        down(&empty); 
        down(&mutex); 
        insert_item(item); 
        up(&mutex); 
        up(&full); 
    } 
} 
 
void consumer() { 
    while(TRUE) { 
        down(&full); 
        down(&mutex); 
        int item = remove_item(); 
        consume_item(item); 
        up(&mutex); 
        up(&empty); 
    } 
} 

(2)使用管程實現生產者-消費者

// 管程 
monitor ProducerConsumer 
    condition full, empty; 
    integer count := 0; 
    condition c; 
 
    procedure insert(item: integer); 
    begin 
        if count = N then wait(full); 
        insert_item(item); 
        count := count + 1; 
        if count = 1 then signal(empty); 
    end; 
 
    function remove: integer; 
    begin 
        if count = 0 then wait(empty); 
        remove = remove_item; 
        count := count - 1; 
        if count = N -1 then signal(full); 
    end; 
end monitor; 
 
// 生產者客戶端 
procedure producer 
begin 
    while true do 
    begin 
        item = produce_item; 
        ProducerConsumer.insert(item); 
    end 
end; 
 
// 消費者客戶端 
procedure consumer 
begin 
    while true do 
    begin 
        item = ProducerConsumer.remove; 
        consume_item(item); 
    end 
end; 

(3)讀寫問題

允許多個進程同時對數據進行讀操作，但是不允許讀和寫以及寫和寫操作同時發生。一個整型變量 count 記錄在對數據進行讀操作的進程數量，一個互斥量 count_mutex 用于對 count 加鎖，一個互斥量 data_mutex 用于對讀寫的數據加鎖。

typedef int semaphore; 
semaphore count_mutex = 1; 
semaphore data_mutex = 1; 
int count = 0; 
 
void reader() { 
    while(TRUE) { 
        down(&count_mutex); 
        count++; 
        if(count == 1) down(&data_mutex); // 第一個讀者需要對數據進行加鎖，防止寫進程訪問 
        up(&count_mutex); 
        read(); 
        down(&count_mutex); 
        count--; 
        if(count == 0) up(&data_mutex); 
        up(&count_mutex); 
    } 
} 
 
void writer() { 
    while(TRUE) { 
        down(&data_mutex); 
        write(); 
        up(&data_mutex); 
    } 
} 

(4)哲學家就餐問題

五個哲學家圍著一張圓桌，每個哲學家面前放著食物。哲學家的生活有兩種交替活動：吃飯以及思考。當一個哲學家吃飯時，需要先拿起自己左右兩邊的兩根筷子，并且一次只能拿起一根筷子。

下面是一種錯誤的解法，考慮到如果所有哲學家同時拿起左手邊的筷子，那么就無法拿起右手邊的筷子，造成死鎖。

#define N 5 
 
void philosopher(int i) { 
    while(TRUE) { 
        think(); 
        take(i);       // 拿起左邊的筷子 
        take((i+1)%N); // 拿起右邊的筷子 
        eat(); 
        put(i); 
        put((i+1)%N); 
    } 
} 

為了防止死鎖的發生，可以設置兩個條件：

• 必須同時拿起左右兩根筷子;
• 只有在兩個鄰居都沒有進餐的情況下才允許進餐。

#define N 5 
#define LEFT (i + N - 1) % N // 左鄰居 
#define RIGHT (i + 1) % N    // 右鄰居 
#define THINKING 0 
#define HUNGRY   1 
#define EATING   2 
typedef int semaphore; 
int state[N];                // 跟蹤每個哲學家的狀態 
semaphore mutex = 1;         // 臨界區的互斥 
semaphore s[N];              // 每個哲學家一個信號量 
 
void philosopher(int i) { 
    while(TRUE) { 
        think(); 
        take_two(i); 
        eat(); 
        put_two(i); 
    } 
} 
 
void take_two(int i) { 
    down(&mutex); 
    state[i] = HUNGRY; 
    test(i); 
    up(&mutex); 
    down(&s[i]); 
} 
 
void put_two(i) { 
    down(&mutex); 
    state[i] = THINKING; 
    test(LEFT); 
    test(RIGHT); 
    up(&mutex); 
} 
 
void test(i) {         // 嘗試拿起兩把筷子 
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) { 
        state[i] = EATING; 
        up(&s[i]); 
    } 
} 

問題八：線程實現的兩種方式，各有什么優缺點

問題九、內存管理的方式：段式、頁式、段頁式。比較他們的區別

操作系統中的內存管理有三種，段式頁式段頁式。

1、為什么需要三種管理方式

由于連續內存分配方式會導致內存利用率偏低以及內存碎片的問題，因此需要對這些離散的內存進行管理。引出了三種內存管理方式。

2、分頁存儲管理

(1)基本分頁存儲管理中不具備頁面置換功能，因此需要整個程序的所有頁面都裝入內存之后才可以運行。

(2)需要一個頁表來記錄邏輯地址和實際存儲地址之間的映射關系，以實現從頁號到物理塊號的映射。

(3)由于頁表也是存儲在內存中的，因此內存數據需要兩次的內存訪問(一次是從內存中訪問頁表，從中找到指定的物理塊號，加上頁內偏移得到實際物理地址;第二次就是根據第一次得到的物理地址訪問內存取出數據)。

(4)為了減少兩次訪問內存導致的效率影響，分頁管理中引入了快表，當要訪問內存數據的時候，首先將頁號在快表中查詢，如果在快表中，直接讀取相應的物理塊號;如果沒有找到，那么訪問內存中的頁表，從頁表中得到物理地址，同時將頁表中的該映射表項添加到快表中。

(5)在某些計算機中如果內存的邏輯地址很大，將會導致程序的頁表項會很多，而頁表在內存中是連續存放的，所以相應的就需要較大的連續內存空間。為了解決這個問題，可以采用兩級頁表或者多級頁表的方法，其中外層頁表一次性調入內存且連續存放，內層頁表離散存放。相應的訪問內存頁表的時候需要一次地址變換，訪問邏輯地址對應的物理地址的時候也需要一次地址變換，而且一共需要訪問內存3次才可以讀取一次數據。

3、分段存儲管理

分頁是為了提高內存利用率，而分段是為了滿足程序員在編寫代碼的時候的一些邏輯需求(比如數據共享，數據保護，動態鏈接等)。

(1)分段內存管理當中，地址是二維的，一維是段號，一維是段內地址;

(2)其中每個段的長度是不一樣的，而且每個段內部都是從0開始編址的。由于分段管理中，每個段內部是連續內存分配，但是段和段之間是離散分配的，因此也存在一個邏輯地址到物理地址的映射關系，相應的就是段表機制。段表中的每一個表項記錄了該段在內存中的起始地址和該段的長度。段表可以放在內存中也可以放在寄存器中。

(3)訪問內存的時候根據段號和段表項的長度計算當前訪問段在段表中的位置，然后訪問段表，得到該段的物理地址，根據該物理地址以及段內偏移量就可以得到需要訪問的內存。由于也是兩次內存訪問，所以分段管理中同樣引入了聯想寄存器。

4、分段和分頁的對比

(1)頁是信息的物理單位，是出于系統內存利用率的角度提出的離散分配機制;段是信息的邏輯單位，每個段含有一組意義完整的信息，是出于用戶角度提出的內存管理機制

(2)頁的大小是固定的，由系統決定;段的大小是不確定的，由用戶決定

(3)頁地址空間是一維的，段地址空間是二維的

5、段頁存儲方式

先將用戶程序分為若干個段，然后再把每個段分成若干個頁，并且為每一個段賦予一個段名稱。這樣在段頁式管理中，一個內存地址就由段號，段內頁號以及頁內地址三個部分組成。

段頁式內存訪問：系統中設置了一個段表寄存器，存放段表的起始地址和段表的長度。地址變換時，根據給定的段號(還需要將段號和寄存器中的段表長度進行比較防止越界)以及寄存器中的段表起始地址，就可以得到該段對應的段表項，從段表項中得到該段對應的頁表的起始地址，然后利用邏輯地址中的段內頁號從頁表中找到頁表項，從該頁表項中的物理塊地址以及邏輯地址中的頁內地址拼接出物理地址，最后用這個物理地址訪問得到所需數據。由于訪問一個數據需要三次內存訪問，所以段頁式管理中也引入了高速緩沖寄存器。

問題十、虛擬內存的作用

1、虛擬內存存在的意義?

(1)既然每個進程的內存空間都是一致而且固定的，所以鏈接器在鏈接可執行文件時，可以設定內存地址，而不用去管這些數據最終實際的內存地址，這是有獨立內存空間的好處

(2)當不同的進程使用同樣的代碼時，比如庫文件中的代碼，物理內存中可以只存儲一份這樣的代碼，不同的進程只需要把自己的虛擬內存映射過去就可以了，節省內存

(3)在程序需要分配連續的內存空間的時候，只需要在虛擬內存空間分配連續空間，而不需要實際物理內存的連續空間，可以利用碎片。

2、虛擬內存和物理內存的關系

問題十一、頁面置換算法

1、算法講解

(1)最佳置換算法：理想的置換算法。置換策略是將當前頁面中在未來最長時間內不會被訪問的頁置換出去。

(2)先進先出置換算法：每次淘汰最早調入的頁面 。

(3)最近最久未使用算法LRU：每次淘汰最久沒有使用的頁面。使用了一個時間標志。

(4)時鐘算法clock(最近未使用算法NRU)：頁面設置一個訪問位，并將頁面鏈接為一個環形隊列，頁面被訪問的時候訪問位設置為1。頁面置換的時候，如果當前指針所指頁面訪問為為0，那么置換，否則將其置為0，循環直到遇到一個訪問為位0的頁面

(5)改進型Clock算法：在Clock算法的基礎上添加一個修改位，替換時根究訪問位和修改位綜合判斷。優先替換訪問為何修改位都是0的頁面，其次是訪問位為0修改位為1的頁面。

(6)最少使用算法LFU：設置寄存器記錄頁面被訪問次數，每次置換的時候置換當前訪問次數最少的。LFU和LRU是很類似的，支持硬件也是一樣的，但是區分兩者的關鍵在于一個以時間為標準，一個以次數為標準。

(7)頁面緩沖算法PBA：置換的時候，頁面無論是否被修改過，都不被置換到磁盤，而是先暫留在內存中的頁面鏈表里面，當其再次被訪問的時候可以直接從這些鏈表中取出而不必進行磁盤IO，當鏈表中已修改也難數目達到一定數量之后，進行依次寫磁盤操作。

2、java實現LRU算法

public class LRU { 
    public static void main(String[] args) { 
        String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"}; 
        // 內存塊 
        int memory = 3; 
        List<String> list = new ArrayList<>(); 
        for(int i = 0; i < inputStr.length; i++){ 
            if(i == 0){ 
                list.add(inputStr[i]); 
                System.out.println("第"+ i +"次訪問：\t\t" + ListUtils.listToString(list)); 
            }else { 
                if(ListUtils.find(list, inputStr[i])){ 
                    // 存在字符串，則獲取該下標 
                    int index = ListUtils.findIndex(list, inputStr[i]); 
                    // 下標不位于棧頂時，且list大小不為1時 
                    if(!(list.get(list.size() - 1)).equals(inputStr[i]) && list.size() != 1) { 
                        String str = list.get(index); 
                        list.remove(index); 
                        list.add(str); 
                    } 
                    System.out.println("第" + i + "次" + "訪問：\t\t" + ListUtils.listToString(list)); 
                }else{ 
                    if(list.size()>= memory) { 
                        list.remove(0); 
                        list.add(inputStr[i]); 
                        System.out.println("第" + i + "次" + "訪問：\t\t" + ListUtils.listToString(list)); 
                    }else { 
                        list.add(inputStr[i]); 
                        System.out.println("第" + i + "次" + "訪問：\t\t" + ListUtils.listToString(list)); 
                    } 
                } 
            } 
        } 
    } 
} 

問題十二、靜態鏈接和動態鏈接

應用程序有兩種鏈接方式，一種是靜態鏈接，一種是動態鏈接。

1、基本概念

所謂靜態鏈接就是在編譯鏈接時直接將需要的執行代碼拷貝到調用處，優點就是在程序發布的時候就不需要的依賴庫，也就是不再需要帶著庫一塊發布，程序可以獨立執行，但是體積可能會相對大一些。

所謂動態鏈接就是在編譯的時候不直接拷貝可執行代碼，而是通過記錄一系列符號和參數，在程序運行或加載時將這些信息傳遞給操作系統，操作系統負責將需要的動態庫加載到內存中，然后程序在運行到指定的代碼時，去共享執行內存中已經加載的動態庫可執行代碼，最終達到運行時連接的目的。

2、windows和linux區別

windows:

在windows上大家都是DLL是動態鏈接庫，里面是一系列可執行的代碼，開發過windows程序的人可能還知道有另外一種形式的庫，就是LIB，大家可能普遍認為LIB就是靜態庫，至少我之前是這么認為的，但是在實際的開發過程中，糾正了我這個錯誤的想法。LIB形式的文件可能會有兩種形式，這里并不排除第三種形式。1：包括符號表和二進制可執行代碼，也就是傳統意義上理解的靜態庫，可以被靜態連接。2：只有符號表，也就是只有動態庫的符號導出信息，通過這些信息可以在程序運行時定位到動態庫中，最終實現動態連接。

linux:

在linux上大家也都知道SO是動態庫，類似于windows下的DLL，實現方式也是大同小異，同時開發過linux下程序的人也都知道另外一種形式的庫就是A庫，同樣道理普遍認為是和SO對立的，也就是靜態庫，不然沒道理存在啊，呵呵。但是事實區卻不是如此，A文件的作用和windows下的LIB文件作用幾乎一樣，也可能會有兩種形式，和windows下的lib文件一樣，在此就不在贅述。

3、靜態鏈接庫的優點

(1) 代碼裝載速度快，執行速度略比動態鏈接庫快;

(2) 只需保證在開發者的計算機中有正確的.LIB文件，在以二進制形式發布程序時不需考慮在用戶的計算機上.LIB文件是否存在及版本問題，可避免DLL地獄等問題。

4、動態鏈接庫的優點

(1) 更加節省內存并減少頁面交換;

(2) DLL文件與EXE文件獨立，只要輸出接口不變(即名稱、參數、返回值類型和調用約定不變)，更換DLL文件不會對EXE文件造成任何影響，因而極大地提高了可維護性和可擴展性;

(3) 不同編程語言編寫的程序只要按照函數調用約定就可以調用同一個DLL函數;

(4)適用于大規模的軟件開發，使開發過程獨立、耦合度小，便于不同開發者和開發組織之間進行開發和測試。

5、不足之處

(1) 使用靜態鏈接生成的可執行文件體積較大，包含相同的公共代碼，造成浪費;

(2) 使用動態鏈接庫的應用程序不是自完備的，它依賴的DLL模塊也要存在，如果使用載入時動態鏈接，程序啟動時發現DLL不存在，系統將終止程序并給出錯誤信息。而使用運行時動態鏈接，系統不會終止，但由于DLL中的導出函數不可用，程序會加載失敗;速度比靜態鏈接慢。當某個模塊更新后，如果新模塊與舊的模塊不兼容，那么那些需要該模塊才能運行的軟件，統統撕掉。這在早期Windows中很常見。

本文轉載自微信公眾號「愚公要移山」，可以通過以下二維碼關注。轉載本文請聯系愚公要移山公眾號。