Linux Operating System

C7 行程管理

1. 行程控制塊，其中與行程管理、存盤器管理和檔案管理有關的一些欄位，執行緒組識別符號，

• Linux為每一個行程建立行程控制塊，又稱行程描述符

  • 用一個task_struct型別的資料結構表示

    task_struct{
    	thread_info   // 基本資訊
    	mm_struct     // 虛擬記憶體描述符
    	fs_struct     // 指向檔案系統資訊
    	files_struct  // 行程打開的檔案
    	signal_struct // 所接受的信號
    	dentry	      // 指向目錄結構的指標
    }

  • 包含了與行程相關的所有資訊

• 每個行程有一個唯一的行程識別符號PID

  • 新創建的通常是PID+1
  • 使用pidmap_array位圖管理PID號(分配和空閑)

• 執行緒組識別符號

  • pid_t tgid
  • 同一執行緒組中所有輕權行程tgid相同

• PID哈希表

2. 與行程創建有關的函式：fork( )、vfork( )、clone( )系統呼叫

• fork()函式
  • 傳統的UNIX創建子行程系統呼叫函式
  • 呼叫sys_fork()和do_fork()
  • 創建成功后,子行程使用寫時復制技術共享父行程的資源
• vfork()
  • sys_vfork()和do_fork()
  • 創建成功后, 暫時掛起父行程, 直到子行程退出或執行新程式
• clone()創建輕權行程
  • sys_clone()和do_fork()
  • 輕權行程可以共享父行程在內核的很多資料結構,如頁表, 打開信號表
• do_fork()
  • 負責處理以上三種系統呼叫,也負責實作內核行程的創建

3. 理解行程切換的程序，涉及到頁目錄表、核心堆疊、硬體背景關系

• 行程切換(行程背景關系切換):

  • 暫停正在CPU上運行的行程, 恢復已就緒的某個行程
  • 行程切換只發生在核心態

• 程序:

  • 第一步, 切換頁目錄表以安裝一個新的地址空間
  • 第二步, 切換核心堆疊和硬體背景關系
  • 保存將要切換出的行程的硬體背景關系*(儲存到核心堆疊)**，用將要切換進來的行程的硬體背景關系來代替，*

• 硬體背景關系:

  • 盡管每個行程可以擁有屬于自己的地址空間，但是所有行程必須共享CPU暫存器，因此，在恢復一個行程的執行前，內核必須確保每個暫存器裝入了掛起行程時的值

  • 行程恢復執行前必須裝入暫存器的那一組資料成為硬體背景關系

  • 涉及到大部分暫存器,但是eax ebx等通用暫存器還是存在核心堆疊中

4. 行程調度方式，行程調度時機，

• 可搶先式的動態優先級調度

  • 內核完全可重入
  • 無論行程處于用戶態還是核心態,都可能被搶占CPU, 從而保證高優先級行程及時執行
  • 基于行程過去行為的啟發式演算法
    • 確定把行程看作批處理行程還是互動行程

• 行程分為三類:

  • 批處理行程: 后臺程式: 編譯, 科學計算等
  • 互動式行程: shell, 文本編輯, 圖形界面
  • 實時行程: 實時監測, 音視頻等, 有很強的調度需求

• 普通行程的調度: (基本:100~139)

  • 分時行程
  • 照顧到基本時間片和動態優先級
  • 新行程繼承父行程的靜態優先級; 也會動態調整優先級(依賴于行程的過去行為)

• 實時行程的調度: (基本: 1~99)

  • 相同優先級 - 時間片輪轉
  • 不同優先級 - FIFO

• 互動式行程:

  • 動態優先數≤3×靜態優先數 /4+28, 否則為批處理

• 調度時機:

  • 出現了更高優先級的實時行程
  • 行程阻塞
  • 行程停止運行或殺死
  • 自愿放棄處理機
  • 時間片用完

5. Linux 有很多內核執行緒，了解 0 號行程和 1 號行程的作用，

• 0號行程:

  • 所有行程的祖先行程,又叫idle行程或swapper行程.
  • 每個CPU都有一個0號行程
  • 行程描述符存放在init_task變數中

• 1號行程

  • 由0號行程創建的內核執行緒init
  • 1號行程創建后,執行init()函式, 完成內核的初始化
  • 與0號行程共享每個行程所有的內核資料結構
  • 在系統關閉前一直存在,創建和監控OS的所有用戶態行程

C8 存盤器管理

1. 行程地址空間的劃分？管理行程私有地址空間的資料結構？指向映射檔案物件的指標欄位？指向行程頁目錄表的指標欄位？

• 行程地址空間的劃分:
  • 32位/x86, 每個地址空間4GB, 彼此互相獨立
    • 私有空間前3G, 公有空間后1G內核虛空間
• 資料結構:
  • 虛擬記憶體區域數較少: 單鏈表
  • 虛擬記憶體區域數較多: 紅黑樹
• 指標欄位:
  • 虛擬記憶體描述符mm_struct

2. Linux 堆的管理：malloc( )，free( )

• malloc(size): 請求size位元組的動態記憶體, 回傳起始虛地址
• calloc(n,size): 請求元素大小為size, 長度為n的陣列
• realloc(ptr,size)
• free(addr): 釋放malloc()或者calloc()分配的起始虛地址為addr的記憶體空間

3. 管理物理記憶體頁框的資料結構？ 記憶體管理區 zone 結構，伙伴系統？磁區頁框分配器分配頁框的程序

• struct_page: 頁框(幀)描述符, 存放在mem_map陣列中

• 三個管理區zone:

  • ZONE_DMA：包含低于16MB的常規記憶體 頁框，用于對老式的基于ISA設備的DMA支持.

  • ZONE_NORMAL：包含高于16MB且低于896MB的常規記憶體頁框.

  • ZONE_HIGHMEM：包含從896MB開始的高端物理頁框，內核不能直接訪問這部分頁框，在64位體系結構上，該區總是空的.

  • 每個區域內, 除了留出小部分用于每CPU頁框高速快取,(滿足CPU的請求), 其他由伙伴系統管理

• 伙伴系統:

  • 管理連續的空閑記憶體頁框, 以解決外碎片 (已分配區域之外的or之間的) 問題，
  • 分配程序:
    • 連接1,2,4,8,…,1024個連續頁框的鏈表
    • 若請求8個,則在8個的鏈表中找. 之后依次向更大的鏈表中找.
    • 若在更大的中找到,則分為幾部分重新練到鏈表中

4. 理解 slab 分配器的原理，slab 分配器的作用？

• slab分配器用于為只有幾十或幾百個位元組的 小記憶體區分配記憶體，如，file物件，
• 為什么需要slab
  • 伙伴系統以頁為單位, 對于內核來說力粒度還是太大了
    • 為用戶提供任意大小的記憶體
  • 原理:
    • 為某一模塊預先申請一定記憶體備用(從磁區頁框分配器獲得幾組連續空閑頁框), 從而無需每一次都從系統中分配記憶體,而是從預留的記憶體中取出一部分使用. 這樣能夠大大提高記憶體申請速度.
    • 每一個請求的記憶體稱為物件
  • slab著色: 利用空閑未用的位元組數對slab進行著色**，把slab中的一些空閑區域從末尾移到開頭**
  • kernel → slab → budy → pages

5. 行程頁表建立的時機？了解頁目錄表項或頁表項所包含的欄位，邏輯地址的劃分，利用兩級頁表實作地址轉換的程序，

• 二級頁表

• 建立的時機: 訪問時才建立(節約記憶體)

• 頁表: (頁框4096, 32位)

  • 頁框物理地址20位
  • 其他(Present(是否在記憶體), accessed(訪問位), dirty(正在寫), r/w(權限), user/supervisor, pcd, pwt, pagesize, global)

• 邏輯地址劃分:

  • 頁目錄索引 - 10位
  • 頁表索引 - 10位
  • 頁內偏移 - 12位

• 程序:

• Cr3: 基址暫存器

6. 請求調頁，所缺的頁可能存放的地方，

• 把頁框的分配一直推遲到行程要訪問的頁不在RAM中時引起一個缺頁例外，才將所需的頁調入記憶體，(有缺頁"請求"是才調頁)

7. 了解盤交換區空間的管理方法，

• 盤交換區用來存放從記憶體暫時換出的資料頁 (顧名思義,交換區)
• 每個盤交換區都由一組4KB的頁槽組成
• 第一個頁槽用來存放該交換區的有關資訊，有相應的描述符
• 盡力把換出的頁面相鄰存盤(減少尋道時間)
  • 存放在磁盤磁區中的交換區只有一個子區， 存放在普通檔案中的交換區可能有多個子區， 原因是磁盤上的檔案不要求連續存放

C9~10 檔案系統

1. Ext2 檔案卷的布局？各部分的作用是什么？

• Ext2檔案卷的布局:
  • 引導塊: 讀入并啟動OS, 只有根目錄的引導塊才起作用
  • 超級塊: 資源管理資訊
    • 索引節點綜述, 盤塊總數, 空閑塊技術, 空閑索引節點數, 每組盤塊數
    • 盤塊大小, 每組索引節點數, 索引節點結構大小
  • 塊組描述符
    • 盤塊位圖的塊號, 索引節點位圖的塊號
  • 索引節點位圖: 管理控制資訊
    • 只有塊組0包含的超級快和組描述符才被內核使用; 在一致性檢查時把塊0的拷貝到后續塊中

2. Linux 系統把一般的檔案目錄項分成哪兩部分？這樣做的好處是什么？

• 分為簡單目錄項和索引節點
• 簡單目錄項包含了檔案名和索引節點號等， 可以提高檔案目錄的檢索速度，
• 系統只保留一個索引節點，就可實作多條路徑共享檔案，減少資訊冗余，

3. Linux 檔案系統的索引節點中，索引表劃分成幾級？計算檔案最大長度

   檔案的索引表是如何增長的？要求能夠利用索引表實作將檔案中的位元組地址轉換成檔案的物理塊的操作，

• 索引表：i_block欄位是一個有15個指標元素的陣列，每個元素占4B，共60B，

• 存放檔案邏輯塊號與相應物理塊號之間的映射關系，

  • 每個指標指向一個檔案目錄

• 分為四級:

• 小型檔案: 最初的12個元素是直接索引項，給出檔案最初的 12個邏輯塊號對應的物理塊號
• 中型檔案: 索引12是一次間接索引塊，是一個存放盤塊號的 一維陣列，對應的檔案邏輯塊號從12到 b / 4 + 11 b/4 + 11 b/4+11，b是盤塊大小，每個邏輯塊號占4B，
• 大型檔案: 索引13是二次間接索引塊，對應的檔案邏輯塊號 從 b / 4 + 12 b/4+12 b/4+12到$ (b/4)^2+(b/4)+11$，
• 巨型檔案: 索引14是三次間接索引塊，對應的檔案邏輯塊號 從 ( b / 4 ) 2 + ( b / 4 ) + 12 (b/4)^2+(b/4)+12 (b/4)2+(b/4)+12到 ( b / 4 ) 3 + ( b / 4 ) 2 + ( b / 4 ) + 11 (b/4)^3+(b/4)^2+(b/4)+11 (b/4)3+(b/4)2+(b/4)+11，
• 其中 b b b為一個盤塊以位元組為單位的大小,每個盤塊用四個位元組表示

舉個栗子:

資料塊大小4KB,

• 小型: 12 ? 4 K B = 48 K B 12 * 4KB = 48KB 12?4KB=48KB
• 中型: ( 4 / 1 ) ? 4 K B = 4 M B (4/1)*4KB = 4MB (4/1)?4KB=4MB
• 大型: ( 4 / 1 ) 2 ? 4 K B = 4 G B (4/1)^2*4KB = 4GB (4/1)2?4KB=4GB
• 巨型: ( 4 / 1 ) 3 ? 4 K B = 4 T B (4/1)^3*4KB = 4TB (4/1)3?4KB=4TB

4. 硬鏈接和符號鏈接的區別？

• 硬鏈接：多個檔案項指向一個檔案
  • 所有目錄項inode指向同一索引節點
• 軟連接：存盤真實檔案的邏輯名稱.
  • 它不與檔案的索引節點建立鏈接，可以跨檔案系統（當為一個檔案 建立符號鏈接時，索引節點的硬鏈接計數 不改變）

5. Linux 檔案系統如何管理空閑存盤空間？

磁盤塊和索引節點的分配和回收;

檔案的資料塊和其索引節點盡量在同一個塊組中，

檔案和它的目錄項盡量在同一個塊組中 ; 父目錄和子目錄盡量在同一個塊組中，

每個檔案的資料塊盡量連續存放，

• 結構: 磁區(MBR, GPT) - Group - block(引導 + …) - 索引節點 - 索引節點表 - physical

6. VFS 通用檔案模型中的四個主要物件？為什么可以支持眾多的檔案卷

• VFS: 虛擬檔案系統

  • 使得Linux具有操作其他OS檔案系統的能力
    

• 主要是想: 引入通用檔案模型,可以支持所有的檔案系統

• VFS的四個主要物件:

  • 超級塊物件: 代表已安裝的檔案系統,存放管理和控制資訊
    • 存放在FCB中, 即一個暗黃好的檔案系統建立一個超級塊物件
  • 索引節點物件: 打開檔案對應的檔案控制塊FCB
    • 每個檔案都有一個索引節點物件,唯一索引節點號,標識檔案系統中的一個特定檔案
  • 目錄項物件:代表一個目錄項
    • 目錄項與對應檔案進行連接的資訊
  • 檔案物件: 行程和打開的檔案之間的互動資訊

7. Linux 系統中，行程打開一個磁盤檔案要涉及哪些資料結構？它們各有哪些關 鍵欄位？他們的作用是什么?

Struct tast_struct{ 
    struct fs_struct *fs; //指向檔案系統資訊 
    struct files_struct *files; //指向行程打開檔案資訊
}
struct fs_struct { 
    atomic_t count; // 共享該結構的行程數 
    struct dentry *root, *pwd; //每個行程的當前作業目錄和根目錄，通過這兩個目錄與檔案系統進行互動， 
    struct vfsmount *rootmnt; //根目錄下安裝 的檔案系統物件 
    struct vfsmount *pwdmnt; //當前目錄下安 裝的檔案系統物件
}
struct files_struct { 
    struct file **fd; // 指向檔案物件指標陣列的 指標 
    struct file *fd_array[ ];//檔案物件指標陣列
}// 每個行程最多打開 1024個檔案

8. 一個檔案在使用與不用時各占用系統哪些資源？

9. 了解安裝表的作用

• 安裝需要通過mount函式實作，將檔案系統安裝到根檔案系統的某個目錄節點上，將安裝點與被安裝文 件系統資訊保存在已安裝檔案系統描述符vfsmount結構中，形成鏈式安裝表
• 安裝表功能是保存已安裝檔案系統描述符