作業系統讀寫者問題實驗報告_作業系統知識點總結

使用者态和核心态

使用者态和核心态的差別？

明白這兩個概念之前，我們得知道使用者空間和核心空間。

使用者空間：指的就是使用者可以操作和通路的空間，這個空間通常存放我們使用者自己寫的資料等。

核心空間：是系統核心來操作的一塊空間，這塊空間裡面存放系統核心的函數、接口等。

在使用者空間下執行，我們把此時運作的程式的這種狀态成為使用者态，而當這段程式執行在核心的空間執行時，這種狀态稱為核心态。

當一個任務(程序)執行系統調用而陷入核心代碼中執行時，我們就稱程序處于核心狀态。此時處理器處于特權級最高的(0級)核心代碼。當程序處于核心态時，執行的核心代碼會使用目前的核心棧。每個程序都有自己的核心棧。

當程序在執行使用者自己的代碼時，則稱其處于使用者态。即此時處理器在特權級最低的使用者代碼中運作。當正在執行使用者程式而突然中斷時，此時使用者程式也可以象征性地處于程序的核心态。因為中斷處理程式将使用目前程序的核心态。

延伸閱讀：核心态與使用者态是作業系統的兩種運作級别，跟intel cpu沒有必然聯系，intel cpu提供Ring0-Ring3三種級别運作模式，Ring0級别最高，Ring3級别最低。Linux使用了Ring3級别運作使用者态。Ring0作為核心态，沒有使用Ring1和Ring2.Ring3不能通路Ring0的位址空間，包括代碼和數量。Linux程序的4GB空間，3G-4G這1G部分大家是共享的，是核心态的位址空間，這裡存放在整個核心代碼和所有的核心子產品，以及核心所維護的資料。使用者運作一程式，該程式所建立的程序開始是運作在使用者态的，如果要執行檔案操作，網絡資料發送等操作，必須通過write，send等系統調用，這些系統會調用核心中的代碼來完成操作，這時，必須切換到Ring0，然後進入1G的核心位址空間去執行這些代碼完成操作，完成後，切換Ring3，回到使用者态。這樣，使用者态的程式就不能随意操作核心位址空間，具有一定的安全保護作用。

使用者态和核心态的轉換

什麼時候從使用者态切換到核心态？

使用者态切換到核心态的3種方式？

(1)系統調用

這是使用者程序主動要求切換到核心态的一種方式，使用者程序通過系統調用申請作業系統提供的服務程式完成工作。

而系統調用的機制其核心還是使用了作業系統為使用者特别開放的一個中斷來實作，該中斷是程式人員自己開發出的一種正常的異常，這個異常具體就是調用int $0x80的彙編指令，這條彙編指令将産生向量為0x80的程式設計異常。(軟中斷)

(2)異常

當CPU在執行運作在使用者态的程式時，發現了某些事件不可知的異常，這是會觸發由目前運作程序切換到處理此

異常的核心相關程式中，也就到了核心态，比如缺頁異常(硬中斷)。

(3)外圍裝置的中斷

當外圍裝置完成使用者請求的操作之後，會向CPU發出相應的中斷信号，這時CPU會暫停執行下一條将要執行的指令，轉而去執行中斷信号的處理程式，如果先執行的指令是使用者态下的程式，那麼這個轉換的過程自然也就發生了有使用者态到核心态的切換。比如硬碟讀寫操作完成，系統會切換到硬碟讀寫的中斷處理程式中執行後續操作等。

程序和線程

什麼是線程和程序?

程序是一個在記憶體中運作的應用程式。每個程序都有自己獨立的一塊記憶體空間，一個程序可以有多個線程，比如在Windows系統中，一個運作的xx.exe就是一個程序。

線程是程序中的一個執行任務(控制單元)，負責目前程序中程式的執行。一個程序至少有一個線程，一個程序可以運作多個線程，多個線程可共享資料。

程序與線程的差別

線程具有許多傳統程序所具有的特征，故又稱為輕型程序(Light—Weight Process)或程序元；而把傳統的程序稱為重型程序(Heavy—Weight Process)，它相當于隻有一個線程的任務。在引入了線程的作業系統中，通常一個程序都有若幹個線程，至少包含一個線程。

根本差別：程序是作業系統資源配置設定的基本機關，而線程是處理器任務排程和執行的基本機關

資源開銷：每個程序都有獨立的代碼和資料空間(程式上下文)，程式之間的切換會有較大的開銷；線程可以看做輕量級的程序，同一類線程共享代碼和資料空間，每個線程都有自己獨立的運作棧和程式計數器(PC)，線程之間切換的開銷小。

包含關系：如果一個程序内有多個線程，則執行過程不是一條線的，而是多條線(線程)共同完成的；線程是程序的一部分，是以線程也被稱為輕權程序或者輕量級程序。

記憶體配置設定：同一程序的線程共享本程序的位址空間和資源，而程序之間的位址空間和資源是互相獨立的

影響關系：一個程序崩潰後，在保護模式下不會對其他程序産生影響，但是一個線程崩潰整個程序都死掉。是以多程序要比多線程健壯。

執行過程：每個獨立的程序有程式運作的入口、順序執行序列和程式出口。但是線程不能獨立執行，必須依存在應用程式中，由應用程式提供多個線程執行控制，兩者均可并發執行

通信方面：線程間可以通過直接讀寫同一程序中的資料進行通信，但是程序通信需要借助

IPC

。

Java中的記憶體配置設定：一個程序中可以有多個線程， 多個線程共享程序的堆和方法區(JDKI · 8 之後的元空

間) 資源， 但是每個線程有自己的程式計數器、虛拟機棧和本地方法棧。

總結：線程是程序劃分成的更小的運作機關， 一個程序在其執行的過程中可以産生多個線程。線程和進

程最大的不同在于基本上各程序是獨立的， 而各線程則不一定， 因為同一程序中的線程極有可能會互相

影響。線程執行開銷小， 但不利于資源的管理和保護；而程序正相反。

孤兒程序和僵屍程序有什麼差別？

• 孤兒程序就是說一個父程序退出，而它的一個或多個子程序還在運作，那麼這些子程序将成為孤兒程序。孤兒程序将被

  init

  程序(程序

  ID

  為

  1

  的程序)所收養，并由

  init

  程序對它們完成狀态收集工作。因為孤兒程序會被

  init

  程序收養，是以孤兒程序不會對系統造成危害。
• 僵屍程序就是一個子程序的程序描述符在子程序退出時不會釋放，隻有當父程序通過

  wait()

  或

  waitpid()

  擷取了子程序資訊後才會釋放。如果子程序退出，而父程序并沒有調用

  wait()

  或

  waitpid()

  ，那麼子程序的程序描述符仍然儲存在系統中，這種程序稱之為僵屍程序。僵屍程序通過

  ps

  指令顯示出來的狀态為

  Z

  。系統所能使用的程序号是有限的，如果産生大量僵屍程序，可能會因為沒有可用的程序号而導緻系統不能産生新的程序。如果要消滅系統中大量的僵屍程序，隻需要将其父程序殺死，此時僵屍程序就會變成孤兒程序，進而被

  init

  程序所收養，這樣

  init

  程序就會釋放所有的僵屍程序所占有的資源，進而結束僵屍程序。

什麼是守護程序？ 守護程序是運作在背景的一種特殊程序，它是獨立于控制終端的，并周期性地執行某些任務。

線程有哪兩種？

• 使用者級線程(

  user level thread

  )：對于這類線程，有關線程管理的所有工作都由應用程式完成，核心意識不到線程的存在。在應用程式啟動後，作業系統配置設定給該程式一個程序号，以及其對應的記憶體空間等資源。應用程式通常先在一個線程中運作，該線程被成為主線程。在其運作的某個時刻，可以通過調用線程庫中的函數建立一個在相同程序中運作的新線程。使用者級線程的好處是非常高效，不需要進入核心空間，但并發效率不高。
• 核心級線程(

  kernel level thread

  )：對于這類線程，有關線程管理的所有工作由核心完成，應用程式沒有進行線程管理的代碼，隻能調用核心線程的接口。核心維護程序及其内部的每個線程，排程也由核心基于線程架構完成。核心級線程的好處是，核心可以将不同線程更好地配置設定到不同的CPU，以實作真正的并行計算。

事實上，在現代作業系統中，往往使用組合方式實作多線程，即線程建立完全在使用者空間中完成，并且一個應用程式中的多個使用者級線程被映射到一些核心級線程上，相當于是一種折中方案。

程序間通信的方式

1. 管道/ 匿名管道( Pipes ) ：用于具有親緣關系的父子程序間或者兄弟程序之間的通信
2. 有名管道(Names Pipes) ：匿名管道由于沒有名字， 隻能用于親緣關系的程序間通信。為了克服這個缺點， 提出了有名管道。有名管道嚴格遵循先進先出( f 計st first out) 。有名管道以磁盤檔案的方式存在， 可以實作本機任意兩個程序通信。
3. 信号(Signal) ：信号是一種比較複雜的通信方式， 用于通知接收程序某個事件已經發生；
4. 消息隊列(Message Queuing)消息隊列是消息的連結清單， 具有特定的格式， 存放在記憶體中并由消息隊列辨別符辨別。管道和消息隊列的通信資料都是先進先出的原則。與管道( 無名管道：隻存在于記憶體中的檔案；命名管道：存在于實際的磁盤媒體或者檔案系統) 不同的是消息隊列存放在核心中， 隻有在核心重新開機( 即， 作業系統重新開機) 或者顯示地删除一個消息隊列時， 該消息隊列才會被真正的删除。消息隊列可以實作消息的随機查詢， 消息不一定要以先進先出的次序讀取， 也可以按消息的類型讀取· 比FIFO 更有優勢。消息隊列克服了信号承載資訊量少， 管道隻能承載無格式位元組流以及緩沖區大小受限等缺。
5. 信号量(semaphores) ：信号量是一個計數器， 用于多程序對共享資料的通路， 信号量的意圖在于程序間同步。這種通信方式主要用于解決與同步相關的問題并避免竟争條件。
6. 共享記憶體(Shared memo (y) ：使得多個程序可以通路同一塊記憶體空間， 不同程序可以及時看到對方程序中對共享記憶體中資料的更新。這種方式需要依靠某種同步操作， 如互斥鎖和信号量等。可以說這是最有用的程序間通信方式。
7. 套接字(sockets) ：此方法主要用于在用戶端和伺服器之間通過網絡進行通信。套接字是支援TCP/IP 的網絡通信的基本操作單元， 可以看做是不同主機之間的程序進行雙向通信的端點， 簡單的說就是通信的兩方的一種約定， 用套接字中的相關函數來完成通信過程。

參考：https://www.jianshu.com/p/c1015f5ffa74

線程間的同步方式

線程同步是兩個或多個共享關鍵資源的線程的并發執行。應該同步線程以避免關鍵的資源使用沖突。作業系統一般有下面三種線程同步的方式：

1. 互斥量(Mutex) ：采用互斥對象機制， 隻有擁有互斥對象的線程才有通路公共資源的權限。因為互斥對象隻有一個， 是以可以保證公共資源不會被多個線程同時通路。比如Java 中的synchronized 關鍵詞和各種Lock 都是這種機制。
2. 信号量(semphares) ：它允許同一時刻多個線程通路同一資源， 但是需要控制同一時刻通路此資源的最大線程數量
3. 事件(Event) :Wait/Notify: 通過通知操作的方式來保持多線程同步， 還可以友善的實作多線程優先級的比較操

程序的排程算法

你知道作業系統中程序的排程算法有哪些嗎？

為了确定首先執行哪個程序以及最後執行哪個程序以實作最大CPU 使用率， 計算機科學家已經定義了

一些算法， 它們是，

• 先到先服務( FCFS ) 排程算法：從就緒隊列中選擇一個最先進入該隊列的程序為之配置設定資源， 使它立即執行并一直執行到完成或發生某事件而被阻塞放棄占用CPU 時再重新排程。

• • 非搶占式的排程算法，按照請求的順序進行排程。
  • 有利于長作業，但不利于短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。
  • 對

    I/O

    密集型程序也不利，因為這種程序每次進行

    I/O

    操作之後又得重新排隊。

• 短作業優先( SJF ) 的排程算法：從就緒隊列中選出一個估計運作時間最短的程序為之配置設定資源，使它立即執行并一直執行到完成或發生某事件而被阻塞放棄占用CPU 時再重新排程。

• • 非搶占式的排程算法，按估計運作時間最短的順序進行排程。
  • 長作業有可能會餓死，處于一直等待短作業執行完畢的狀态。因為如果一直有短作業到來，那麼長作業永遠得不到排程。

• 時間片輪轉排程算法：時間片輪轉排程是一種最古老， 最簡單， 最公平且使用最廣的算法， 又稱RR(Round robin) 排程。每個程序被配置設定一個時間段， 稱作它的時間片， 即該程序允許運作的時間。當時間片用完時，由計時器發出時鐘中斷，排程程式便停止該程序的執行，并将它送往就緒隊列的末尾，同時繼續把

  CPU

  時間配置設定給隊首的程序。

• • 時間片輪轉算法的效率和時間片的大小有很大關系：
  • 因為程序切換都要儲存程序的資訊并且載入新程序的資訊，如果時間片太小，會導緻程序切換得太頻繁，在程序切換上就會花過多時間。
  • 而如果時間片過長，那麼實時性就不能得到保證。

• 多級回報隊列排程算法：前面介紹的幾種程序排程的算法都有一定的局限性。如短程序優先的排程算法， 僅照顧了短程序而忽略了長程序。多級回報隊列排程算法既能使高優先級的作業得到響應又能使短作業( 程序) 迅速完成。因而它是目前被公認的一種較好的程序排程算法，UNIX 作業系統采取的便是這種排程算法。
• 優先級排程· 為每個流程配置設定優先級， 首先執行具有最高優先級的程序， 依此類推。具有相同優先級的程序以FCFS 方式執行。可以根據記憶體要求， 時間要求或任何其他資源要求來确定優先級。

大核心和微核心的差別

• 大核心，就是将作業系統的全部功能都放進核心裡面，包括排程、檔案系統、網絡、裝置驅動器、存儲管理等等，組成一個緊密連接配接整體。大核心的優點就是效率高，但是很難定位

  bug

  ，拓展性比較差，每次需要增加新的功能，都要将新的代碼和原來的核心代碼重新編譯。
• 微核心與單體核心不同，微核心隻是将操作中最核心的功能加入核心，包括

  IPC

  、位址空間配置設定和基本的排程，這些東西都在核心态運作，其他功能作為子產品被核心調用，并且是在使用者空間運作。微核心比較好維護和拓展，但是效率可能不高，因為需要頻繁地在核心态和使用者态之間切換。

分時系統和實時系統的差別

• 分時系統(

  Sharing time system

  )就是系統把

  CPU

  時間分成很短的時間片，輪流地配置設定給多個作業。它的優點就是對多個使用者的多個作業都能保證足夠快的響應時間，并且有效提高了資源的使用率。
• 實時系統(

  Real-time system

  )是系統對外部輸入的資訊，能夠在規定的時間内(截止期限)處理完畢并做出反應。它的優點是能夠集中地及時地處理并作出反應，高可靠性，安全性。
• 通常計算機采用的是分時，就是多個程序／使用者之間共享

  CPU

  ，從形勢上實作多任務。各個使用者／程序之間的排程并非精準度特别高，如果一個程序被鎖住，可以給它配置設定更多的時間。而實時作業系統則不同，軟體和硬體必須遵從嚴格的時間限制，超過時限的程序可能直接被終止。在這樣的作業系統中，每次加鎖都需要仔細考慮。

靜态連結和動态連結的差別

• 靜态連結就是在編譯期間，由編譯器和連接配接器将靜态庫內建到應用程式内，并制作成目标檔案以及可以獨立運作的可執行檔案。靜态庫一般是一些外部函數與變量的集合。
• 靜态庫很友善，但是如果我們隻是想用庫中的某一個函數，卻仍然得把所有的内容都連結進去。一個更現代的方法是使用共享庫，避免了在檔案中靜态庫的大量重複。
• 動态連結可以在首次載入的時候執行，也可以在程式開始執行的時候完成。這個是由動态連結器完成，比方标準

  C

  庫(

  libc.so

  ) 通常就是動态連結的，這樣所有的程式可以共享同一個庫，而不用分别進行封裝。

程序有哪些狀态

• 在五狀态模型裡面，程序一共有

  5

  中狀态，分别是建立、就緒、運作、終止、阻塞。
• 運作狀态就是程序正在

  CPU

  上運作。在單處理機環境下，每一時刻最多隻有一個程序處于運作狀态。
• 就緒狀态就是說程序已處于準備運作的狀态，即程序獲得了除

  CPU

  之外的一切所需資源，一旦得到

  CPU

  即可運作。
• 阻塞狀态就是程序正在等待某一事件而暫停運作，比如等待某資源為可用或等待

  I/O

  完成。即使

  CPU

  空閑，該程序也不能運作。

運作态→阻塞态：往往是由于等待外設，等待主存等資源配置設定或等待人工幹預而引起的。

阻塞态→就緒态：則是等待的條件已滿足，隻需配置設定到處理器後就能運作。

運作态→就緒态：不是由于自身原因，而是由外界原因使運作狀态的程序讓出處理器，這時候就變成就緒态。例如時間片用完，或有更高優先級的程序來搶占處理器等。

就緒态→運作态：系統按某種政策選中就緒隊列中的一個程序占用處理器，此時就變成了運作态。

什麼是上下文切換

對于單核單線程

CPU

而言，在某一時刻隻能執行一條

CPU

指令。上下文切換(

Context Switch

)是一種将

CPU

資源從一個程序配置設定給另一個程序的機制。從使用者角度看，計算機能夠并行運作多個程序，這恰恰是作業系統通過快速上下文切換造成的結果。在切換的過程中，作業系統需要先存儲目前程序的狀态(包括記憶體空間的指針，目前執行完的指令等等)，再讀入下一個程序的狀态，然後執行此程序。

什麼是死鎖

在兩個或多個并發程序中，如果一個程序集合中的每個程序都在等待隻能由該程序集合中的其他程序才能引發的事件，那麼該程序集合就産生了死鎖。

死鎖産生有哪些條件

死鎖産生的根本原因是多個程序競争資源時，程序的推進順序出現不正确。

• 互斥：每個資源要麼已經配置設定給了一個程序，要麼就是可用的。
• 占有和等待：已經得到了某個資源的程序可以再請求新的資源。
• 不可搶占：已經配置設定給一個程序的資源不能強制性地被搶占，它隻能被占有它的程序顯式地釋放。
• 環路等待：有兩個或者兩個以上的程序組成一條環路，該環路中的每個程序都在等待下一個程序所占有的資源。

怎麼解決死鎖

對于死鎖，主要有

4

種解決政策。

鴕鳥政策

就是直接忽略死鎖。就像鴕鳥遇到危險的時候，把頭埋在沙子裡，假裝根本沒發生問題。因為解決死鎖問題的代價很高，是以鴕鳥政策這種不采取任務措施的方案會獲得更高的性能。當發生死鎖時不會對使用者造成多大影響，或發生死鎖的機率很低，可以采用鴕鳥政策。大多數作業系統，包括

Unix

，

Linux

和

Windows

，處理死鎖問題的辦法僅僅是忽略它。

死鎖預防

死鎖預防是指通過破壞死鎖産生的四個必要條件中的一個或多個，以避免發生死鎖。

• 破壞互斥：不讓資源被一個程序獨占，可通過假脫機技術允許多個程序同時通路資源；
• 破壞占有和等待：有兩種方案，

• • 已擁有資源的程序不能再去請求其他資源。一種實作方法是要求程序在開始執行前請求需要的所有資源。
  • 要求程序請求資源時，先暫時釋放其目前擁有的所有資源，再嘗試一次擷取所需的全部資源。

• 破壞不可搶占：有些資源可以通過虛拟化方式實作可搶占；
• 破壞循環等待：有兩種方案：

• • 一種方法是保證每個程序在任何時刻隻能占用一個資源，如果要請求另一個資源，必須先釋放第一個資源；
  • 另一種方法是将所有資源進行統一編号，程序可以在任何時刻請求資源，但要求程序必須按照順序請求資源。

死鎖避免

為了避免因為預防死鎖而導緻所有線程變慢，死鎖避免采用了與死鎖預防相反的措施。它允許三個必要條件，但通過算法判斷資源請求是否可能導緻循環等待的形成并相應決策，來避免死鎖點的産生。是以，其前提是知道目前資源使用的整體情況，以及申請資源線程本身所占有的資源細節。

判斷和決策中，主要使用兩種避免方法。

• 線程啟動拒絕：如果一個線程的請求會引發死鎖，則不允許其啟動。
• 資源配置設定拒絕：如果一個線程增加的資源請求會導緻死鎖，則不允許此申請。

整體來看，死鎖避免是從資源和線程互相間關系着手，避免形成循環等待是其主要任務。

死鎖檢測和恢複

可以允許系統進入死鎖狀态，但會維護一個系統的資源配置設定圖，定期調用死鎖檢測算法來檢測途中是否存在死鎖，檢測到死鎖發生後，采取死鎖恢複算法進行恢複。

死鎖檢測方法如下：

• 在資源配置設定圖中，找到不會阻塞又不獨立的程序結點，使該程序獲得其所需資源并運作，運作完畢後，再釋放其所占有的全部資源。也就是消去該程序結點的請求邊和配置設定邊。
• 使用上面的算法進行一系列簡化，若能消去所有邊，則表示不會出現死鎖，否則會出現死鎖。

檢測到死鎖後，就需要解決死鎖。目前作業系統中主要采用如下幾種方法：

• 取消所有死鎖相關線程，簡單粗暴，但也确實是最常用的
• 把每個死鎖線程復原到某些檢查點，然後重新開機
• 連續取消死鎖線程直到死鎖解除，順序基于特定最小代價原則
• 連續搶占資源直到死鎖解除

有哪些磁盤排程算法

先來先服務

• 按照磁盤請求的順序進行排程。
• 優點是公平和簡單。缺點也很明顯，因為未對尋道做任何優化，使平均尋道時間可能較長。

最短尋道時間優先

• 優先排程與目前磁頭所在磁道距離最近的磁道。
• 雖然平均尋道時間比較低，但是不夠公平。如果新到達的磁道請求總是比一個在等待的磁道請求近，那麼在等待的磁道請求會一直等待下去，也就是出現饑餓現象。一般來說，兩端的磁道請求更容易出現饑餓現象。

電梯算法

• 也叫

  SCAN

  掃描算法。電梯算法就是說讀寫磁頭總是保持一個方向運作，直到該方向沒有請求為止，然後改變運作方向。
• 因為考慮了移動方向，是以所有的磁盤請求都會被滿足，解決了最短尋道時間優先的饑餓問題。

什麼是虛拟記憶體

虛拟記憶體就是說，讓實體記憶體擴充成更大的邏輯記憶體，進而讓程式獲得更多的可用記憶體。虛拟記憶體使用部分加載的技術，讓一個程序或者資源的某些頁面加載進記憶體，進而能夠加載更多的程序，甚至能加載比記憶體大的程序，這樣看起來好像記憶體變大了，這部分記憶體其實包含了磁盤或者硬碟，并且就叫做虛拟記憶體。

什麼是分頁系統

分頁就是說，将磁盤或者硬碟分為大小固定的資料塊，叫做頁，然後記憶體也分為同樣大小的塊，叫做頁框。當程序執行的時候，會将磁盤的頁載入記憶體的某些頁框中，并且正在執行的程序如果發生缺頁中斷也會發生這個過程。頁和頁框都是由兩個部分組成的，一個是頁号或者頁框号，一個是偏移量。分頁一般是有硬體來完成的，每個頁都對應一個頁框，它們的對應關系存放在一個叫做頁表的資料結構中，頁号作為這個頁表的索引，頁框号作為頁表的值。作業系統負責維護這個頁表。

分頁和分段有什差別

• 分頁對程式員是透明的，但是分段需要程式員顯式劃分每個段。
• 分頁的位址空間是一維位址空間，分段是二維的。
• 頁的大小不可變，段的大小可以動态改變。
• 分頁主要用于實作虛拟記憶體，進而獲得更大的位址空間；分段主要是為了使程式和資料可以被劃分為邏輯上獨立的位址空間并且有助于共享和保護。

頁面替換算法有哪些

在程式運作過程中，如果要通路的頁面不在記憶體中，就發生缺頁中斷進而将該頁調入記憶體中。此時如果記憶體已無空閑空間，系統必須從記憶體中調出一個頁面到磁盤對換區中來騰出空間。

最佳算法

所選擇的被換出的頁面将是最長時間内不再被通路，通常可以保證獲得最低的缺頁率。這是一種理論上的算法，因為無法知道一個頁面多長時間不再被通路。

先進先出

選擇換出的頁面是最先進入的頁面。該算***将那些經常被通路的頁面也被換出，進而使缺頁率升高。

LRU

雖然無法知道将來要使用的頁面情況，但是可以知道過去使用頁面的情況。

LRU

将最近最久未使用的頁面換出。為了實作 LRU，需要在記憶體中維護一個所有頁面的連結清單。當一個頁面被通路時，将這個頁面移到連結清單表頭。這樣就能保證連結清單表尾的頁面是最近最久未通路的。因為每次通路都需要更新連結清單，是以這種方式實作的

LRU

代價很高。

時鐘算法

時鐘算法使用環形連結清單将頁面連接配接起來，再使用一個指針指向最老的頁面。它将整個環形連結清單的每一個頁面做一個标記，如果标記是

，那麼暫時就不會被替換，然後時鐘算法周遊整個環，遇到标記為

1

的就替換，否則将标記為

的标記為

1

。

Linux檔案系統是怎麼樣的

Linux

檔案系統裡面有檔案和目錄，組成一個樹狀的結構，樹的每一個葉子節點表示檔案或者空目錄。每個檔案基本上都由兩部分組成：

• inode

  ：一個檔案占用一個

  inode

  ，記錄檔案的屬性，同時記錄此檔案的内容所在的

  block

  編号；

• block

  ：記錄檔案的内容，檔案太大時，會占用多個

  block

  。

除此之外還包括：

• superblock

  ：記錄檔案系統的整體資訊，包括

  inode

  和

  block

  的總量、使用量、剩餘量，以及檔案系統的格式與相關資訊等；

• block bitmap

  ：記錄

  block

  是否被使用的位圖。

當要讀取一個檔案的内容時，先在

inode

中查找檔案内容所在的所有

block

，然後把所有

block

的内容讀出來。

硬連結和軟連結有什麼差別

• 硬連結就是在目錄下建立一個條目，記錄着檔案名與

  inode

  編号，這個

  inode

  就是源檔案的

  inode

  。删除任意一個條目，檔案還是存在，隻要引用數量不為 。但是硬連結有限制，它不能跨越檔案系統，也不能對目錄進行連結。
• 符号連結檔案儲存着源檔案所在的絕對路徑，在讀取時會定位到源檔案上，可以了解為

  Windows

  的快捷方式。當源檔案被删除了，連結檔案就打不開了。因為記錄的是路徑，是以可以為目錄建立符号連結。

常見的幾種記憶體管理機制

作業系統的記憶體管理機制了解嗎？記憶體管理有哪幾種方式？

簡單分為連續配置設定管理方式和非連續配置設定管理方式這兩種。連續配置設定管理方式是指為一個使用者程式配置設定

一個連續的記憶體空間， 常見的如塊式管理。同樣地， 非連續配置設定管理方式允許一個程式使用的記憶體分

布在離散或者說不相鄰的記憶體中， 常見的如頁式管理和段式管理。

• 塊式管理：遠古時代的計算機操系統的記憶體管理方式。将記憶體分為幾個固定大小的塊， 每個塊中隻包含一個程序。如果程式運作需要記憶體的話， 作業系統就配置設定給它一塊， 如果程式運作隻需要很小的空間的話， 配置設定的這塊記憶體很大一部分幾乎被浪費了。這些在每個塊中未被利用的空間， 我們稱之為碎片。
• 頁式管理：把主存分為大小相等且固定的一頁一頁的形式， 頁較小， 相對相比于塊式管理的劃分力度更大， 提高了記憶體使用率， 減少了碎片。頁式管理通過頁表對應邏輯位址和實體位址。
• 段式管理：頁式管理雖然提高了記憶體使用率， 但是頁式管理其中的頁實際并無任何實際意義。段式管理把主存分為一段段的， 每一段的空間又要比一頁的空間小很多。但是， 最重要的是段是有實際意義的， 每個段定義了一組邏輯資訊， 例如， 有主程式段MAIN 、子程式段× 、資料段D及棧段S 等。段式管理通過段表對應邏輯位址和實體位址。
• 段頁式管理機制：段頁式管理機制結合了段式管理和頁式管理的優點。簡單來說段頁式管理機制就是把主存先分成若幹段， 每個段又分成若幹頁，也就是說段頁式管理機制中段與段之間以及段的内部的都是離散的。

參考：https://blog.nowcoder.net/n/42ee220483414f37952ef71f604a7ff5