第一章：操作系統(tǒng)概論

1. 操作系統(tǒng)的目的：方便性锋谐，有效性坪哄，擴(kuò)展性

2. 操作系統(tǒng)的特點：并發(fā)行，共享性挠轴，虛擬性传睹，異步性

   引入操作系統(tǒng)的目的是使程序并發(fā)執(zhí)行，其并發(fā)行是通過分時得以實現(xiàn)的

   并發(fā)：指兩個或多個事件在同一時間間隔內(nèi)發(fā)生

   并行：兩個或多個事件在同一時刻發(fā)生

3. 分時操作系統(tǒng)：交互性岸晦，多路性欧啤，獨(dú)立性，及時性

   實時操作系統(tǒng)(硬實時和軟實時)：及時性启上，可靠性

4. 內(nèi)核態(tài)和用戶態(tài)

5. 系統(tǒng)調(diào)用和庫函數(shù)的區(qū)別：庫函數(shù)是語言或應(yīng)用程序的一部分邢隧，可以運(yùn)行在用戶空間中；系統(tǒng)調(diào)用是操作系統(tǒng)的一部分碧绞，是內(nèi)核提供給用戶的程序接口府框，運(yùn)行在內(nèi)核空間中；許多庫函數(shù)會使用系統(tǒng)調(diào)用來實現(xiàn)功能讥邻，沒有使用系統(tǒng)調(diào)用的庫函數(shù)迫靖，執(zhí)行效率通常比系統(tǒng)調(diào)用高，因為系統(tǒng)調(diào)用需要進(jìn)行上下文的切換以及狀態(tài)的轉(zhuǎn)換

第二章：進(jìn)程管理

1. 死鎖預(yù)防和死鎖避免的區(qū)別（49頁）

   死鎖預(yù)防：破壞互斥條件兴使，破壞請求和保持條件(預(yù)先靜態(tài)分配所有資源)系宜，破壞不可剝奪條件(資源可剝奪)，破壞循環(huán)等待條件(資源統(tǒng)一編號)

   死鎖避免：在資源的動態(tài)分配過程中,用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)发魄，從而避免死鎖,一般使用銀行家算法

2. 產(chǎn)生死鎖的充要條件以及如何預(yù)防死鎖和解決死鎖 (49頁)

   四個必要條件構(gòu)成產(chǎn)生死鎖的充要條件盹牧，

   死鎖預(yù)防：破壞產(chǎn)生死鎖的四個必要條件

   解決死鎖：資源剝奪,撤銷進(jìn)程,進(jìn)程回退

3. PCB的主要存儲內(nèi)容是什么？為什么說PCB是進(jìn)程存在的唯一標(biāo)志 (23頁)

   PCB用于保存進(jìn)程運(yùn)行期間的相關(guān)數(shù)據(jù)励幼，主要保存進(jìn)程描述信息汰寓，進(jìn)程控制和管理信息，資源分配信息和處理機(jī)相關(guān)信息

   在進(jìn)程整個生命周期中苹粟，系統(tǒng)總是通過PCB對進(jìn)程進(jìn)行控制有滑，系統(tǒng)是通過PCB感知進(jìn)程的存在。

4. 哲學(xué)家進(jìn)餐問題中嵌削，有左右撇子的存在是否會發(fā)生死鎖毛好？

   不會發(fā)生死鎖望艺，因為破壞了產(chǎn)生死鎖的四個必要條件之一：循環(huán)等待條件

5. 什么是死鎖？如何預(yù)防死鎖肌访？ (48.,49頁)

   死鎖：兩個或者多個進(jìn)程在執(zhí)行過程中找默，由于競爭資源或者推進(jìn)順序不當(dāng)而造成的一種阻塞現(xiàn)象，若無外力作用吼驶，它們都將無法推進(jìn)下去

   預(yù)防死鎖：破壞互斥條件惩激，破壞請求和保持條件(預(yù)先靜態(tài)分配所有資源)，破壞不可剝奪條件(資源可剝奪)旨剥，破壞循環(huán)等待條件(資源統(tǒng)一編號)

6. 描述在當(dāng)前運(yùn)行進(jìn)程改變時咧欣，操作系統(tǒng)進(jìn)行進(jìn)程切換的步驟浅缸？ ( 26頁)

   切換過程：

   1. 保存當(dāng)前進(jìn)程的上下文環(huán)境
   2. 對運(yùn)行進(jìn)程的PCB進(jìn)行更新轨帜，并移入相應(yīng)的隊列
   3. 選擇其它進(jìn)程運(yùn)行
   4. 更新選擇進(jìn)程的PCB，包括將其狀態(tài)改為運(yùn)行狀態(tài)
   5. 對存儲器管理數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新
   6. 恢復(fù)被選擇進(jìn)程移除時處理機(jī)的狀態(tài)

7. 寫出P(S)操作的主要操作步驟 (38頁)

   (1)S=S-1

   (2)若S>=0,繼續(xù)執(zhí)行衩椒；否則阻塞該進(jìn)程蚌父，并將它插入該信號量的等待隊列中

   V(S)的主要步驟：

   1. S=S+1
   2. 若S>0,繼續(xù)執(zhí)行；否則從該信號等待隊列中移除第一個進(jìn)程毛萌，使其變?yōu)榫途w狀態(tài)苟弛，并插入就緒隊列中

8. 闡述對于互斥臨界區(qū)的管理要求。 (38頁)

   為了實現(xiàn)進(jìn)程互斥阁将，可以使用軟件方法也可以使用硬件方法膏秫，但所有的同步機(jī)制都應(yīng)該遵循以下四條準(zhǔn)則：

   1. 空閑讓進(jìn)：臨界區(qū)空閑時允許一個進(jìn)程進(jìn)入臨界區(qū)
   2. 忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須繼續(xù)等待
   3. 有限等待：對請求訪問的進(jìn)程應(yīng)保證能在有限時間內(nèi)進(jìn)入臨界區(qū)
   4. 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時，應(yīng)立即釋放處理器做盅，防止忙等待

9. 程序順序執(zhí)行：順序性缤削，封閉性，可再現(xiàn)性

   程序并發(fā)執(zhí)行：間斷性吹榴，失去封閉性亭敢，不可再現(xiàn)性

10. 進(jìn)程與程序的本質(zhì)區(qū)別：進(jìn)程是動態(tài)的，程序是靜態(tài)的

11. 進(jìn)程的特點：動態(tài)性图筹，并發(fā)行帅刀，獨(dú)立性，異步性远剩，結(jié)構(gòu)性

12. 進(jìn)程的組成：PCB扣溺，數(shù)據(jù)段，程序段

13. 就緒瓜晤，執(zhí)行锥余，阻塞之間的轉(zhuǎn)換(阻塞不能變?yōu)閳?zhí)行)

14. 進(jìn)程創(chuàng)建原語：用戶登錄，作業(yè)調(diào)度活鹰，請求服務(wù)哈恰，應(yīng)用請求

15. 進(jìn)程的撤銷(終止)：正常結(jié)束或者異常結(jié)束

16. 進(jìn)程通信：共享存儲只估，消息傳遞(原語),管道通信

17. 線程：用戶級線程和內(nèi)核級線程的區(qū)別

18. 進(jìn)程和線程的區(qū)別：

    資源：進(jìn)程是擁有系統(tǒng)資源的基本單位，線程不擁有系統(tǒng)資源着绷，但可以訪問其隸屬進(jìn)程的系統(tǒng)資源

    調(diào)度：在傳統(tǒng)操作系統(tǒng)中蛔钙，進(jìn)程是擁有資源和獨(dú)立調(diào)度的基本單位；在引入線程的操作系統(tǒng)中荠医，線程是獨(dú)立調(diào)度的基本單位吁脱，進(jìn)程是擁有資源的基本單位；同一進(jìn)程中線程切換不會引起進(jìn)程切換彬向，不同進(jìn)程中線程切換會引起進(jìn)程切換

    并發(fā)性：同一進(jìn)程中多個線程之間可以并發(fā)執(zhí)行兼贡，提高了系統(tǒng)的并發(fā)行

    系統(tǒng)開銷：線程切換只需要保存少量信息和設(shè)置少量寄存器內(nèi)容，開銷型薜ā遍希；進(jìn)程切換遠(yuǎn)大于線程切換的開銷

19. 周轉(zhuǎn)時間：作業(yè)完成時間-作業(yè)提交時間

    平均周轉(zhuǎn)時間：做個作業(yè)周轉(zhuǎn)時間之和/作業(yè)個數(shù)

    帶權(quán)周轉(zhuǎn)時間：作業(yè)周轉(zhuǎn)時間/作業(yè)運(yùn)行時間

    平均帶權(quán)周轉(zhuǎn)時間：多個作業(yè)帶權(quán)周轉(zhuǎn)時間之和/作業(yè)個數(shù)

    提，開里烦，運(yùn)凿蒜，完，周轉(zhuǎn)胁黑，帶權(quán)周轉(zhuǎn)

20. 作業(yè)調(diào)度算法：先來先服務(wù)算法(FCFS)废封，短作業(yè)優(yōu)先算法(SJF)，優(yōu)先級調(diào)度算法丧蘸，高響應(yīng)比調(diào)度算法(R=(等待時間+運(yùn)行時間)/運(yùn)行時間)

    進(jìn)程調(diào)度算法：先來先服務(wù)算法(FCFS)漂洋，短作業(yè)優(yōu)先算法(SJF)，優(yōu)先級調(diào)度算法力喷，時間片輪轉(zhuǎn)調(diào)度算法刽漂，多級反饋隊列調(diào)度算法

21. 臨界區(qū)和臨界資源的區(qū)別
    臨界區(qū)：每個進(jìn)程中訪問臨界資源的一段代碼
    臨界資源：必須互斥訪問的系統(tǒng)資源

22. 同步，互斥冗懦，以及二者之間的關(guān)系

    同步：多個相互合作的進(jìn)程爽冕，在一些關(guān)鍵點上需要相互等待或者相互交換信息，這種相互制約關(guān)系稱為同步

    互斥：若多個進(jìn)程要求訪問臨界資源披蕉，而臨界資源一次只能讓一個進(jìn)程訪問颈畸，因而產(chǎn)生的競爭關(guān)系成為互斥

    關(guān)系：互斥是進(jìn)程同步的一種特殊情況，互斥也是為了達(dá)到讓進(jìn)程之間協(xié)調(diào)推進(jìn)的目的

    互斥實現(xiàn)方法：硬件方法(中斷屏蔽没讲，硬件指令)眯娱，軟件方法(天勤P50)

23. 記錄型信號量的數(shù)據(jù)結(jié)構(gòu)以及PV操作基本算法 (38頁)

24. 經(jīng)典的同步與互斥問題：生產(chǎn)者-消費(fèi)者，讀寫者爬凑，哲學(xué)家進(jìn)餐徙缴，吸煙者，理發(fā)者，水果問題

25. 管程的相關(guān)知識點

26. 死鎖的定義于样，死鎖產(chǎn)生的兩個原因疏叨，死鎖產(chǎn)生的四個必要條件 (P48頁)

27. 處理死鎖的方法：鴕鳥算法，預(yù)防死鎖穿剖，避免死鎖蚤蔓，檢測以及解除死鎖

28. 預(yù)防死鎖：破壞四個必要條件，靜態(tài)分配糊余，可剝奪秀又，資源編號

29. 死鎖避免：安全狀態(tài)，不安全狀態(tài)贬芥，死鎖之間的關(guān)系吐辙，銀行家算法(矩陣)

30. 資源分配圖，死鎖定理蘸劈，解除死鎖(資源剝奪昏苏，進(jìn)程撤銷，進(jìn)程回退)

計算題大題考點：

1. 進(jìn)程/作業(yè)調(diào)度算法分析進(jìn)程的調(diào)度順序昵时，周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間
2. 多個進(jìn)程并發(fā)執(zhí)行計算CPU的利用率捷雕，程序執(zhí)行結(jié)果
3. 銀行家算法得出安全序列
4. PV大題

第三章：內(nèi)存管理

1. 抖動的原因椒丧，怎樣解決（80頁）

   抖動定義：在頁面置換過程中壹甥，剛剛換出的頁面馬上又要換入主存，剛剛換入的頁面馬上又要換出主存壶熏，這種頻繁的頁面調(diào)度行為叫做抖動

   抖動原因：某個進(jìn)程頻繁訪問的頁面數(shù)高于可用的物理塊數(shù)

   解決方案：增加物理快句柠，選擇適當(dāng)?shù)捻撁嬷脫Q算法

2. 什么是虛擬存儲器？如何實現(xiàn)頁式虛擬存儲器棒假？(75頁)

   虛擬存儲器：是指具有請求調(diào)入和置換功能溯职，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲系統(tǒng)；其內(nèi)存容量與物理內(nèi)存無關(guān)帽哑，主要受限于計算機(jī)地址結(jié)構(gòu)和可用磁盤容量

   頁式虛擬存儲器：指在分頁系統(tǒng)基礎(chǔ)上谜酒，增加了請求調(diào)頁，頁面置換和部分裝入功能所形成的妻枕。它允許只裝入部分頁面僻族，以后再通過調(diào)頁和頁面置換功能，把即將運(yùn)行的頁面調(diào)入內(nèi)存屡谐，同時把暫時不需要的頁面置換到外存述么。實現(xiàn)請求調(diào)頁和置換功能還需要一定的硬件和軟件支持。

3. 什么是臨界資源愕掏，死鎖度秘，和哲學(xué)家進(jìn)餐問題？(37,48頁)

   臨界資源：必須互斥使用的系統(tǒng)資源為臨界資源

   死鎖：多個進(jìn)程因競爭資源或執(zhí)行時推進(jìn)順序不當(dāng)而導(dǎo)致處于堵塞的現(xiàn)象若無外力作用饵撑，將永久處于這種狀態(tài)剑梳。

4. 在存儲器管理中唆貌，什么時重定位技術(shù)，為什么要引入重定位技術(shù)垢乙？(60頁)

   重定位：將地址空間中的邏輯地址轉(zhuǎn)換為物理地址,源程序經(jīng)過編譯鏈接產(chǎn)生的裝入模塊是從0開始編址的挠锥，是相對地址；在裝入內(nèi)存時侨赡，分配到的內(nèi)存起始地址一般不為0蓖租，故實際物理地址和裝入模塊中的相對地址不同，為保證程序正常運(yùn)行羊壹，需要進(jìn)行重定位蓖宦。

5. 在分頁存儲管理系統(tǒng)中，頁表的主要作用是什么油猫？大的邏輯地址空間給頁設(shè)計帶來了什么新的問題稠茂？應(yīng)該如何解決？（68頁）

   頁表作用：用來記錄進(jìn)程中的每個頁面和對應(yīng)頁框的信息

   大的邏輯地址空間會導(dǎo)致進(jìn)程的頁表增大情妖，裝入連續(xù)的地址空間難度變大睬关。

   可以通過多級頁面機(jī)制解決這個問題，對頁表進(jìn)行分頁毡证，將頁表離散的存儲,未離散的頁表再建立頁表电爹，也可引入虛擬頁式存儲，提高內(nèi)存的利用率

6. 操作系統(tǒng)中什么是虛擬存儲器料睛？為什么要引入虛擬存儲技術(shù)丐箩？ (75頁)

   虛擬存儲器：是指具有請求調(diào)入和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲系統(tǒng)恤煞；其內(nèi)存容量與物理內(nèi)存無關(guān)屎勘，主要受限于計算機(jī)地址結(jié)構(gòu)和可用磁盤容量

   引入目的：提高系統(tǒng)的內(nèi)存利用率和系統(tǒng)的吞吐量

7. 簡述基本分頁存儲管理和請求分頁存儲管理的異同之處 (67,76頁)

   基本分頁：系統(tǒng)將每個程序按固定大小分成若干頁，每頁對應(yīng)一個物理塊號居扒，程序的所有頁面都被裝入到內(nèi)存中

   請求分頁：程序仍被分成若干頁概漱，但僅裝入程序運(yùn)行所必須的頁面。當(dāng)需要某個頁面時喜喂，再請求從外部調(diào)入瓤摧。如果沒有空閑空間，則利用置換技術(shù)進(jìn)行頁面的淘汰和置換

8. 解釋頁式存儲管理中為什么要設(shè)置頁表和快表 (68,69頁)

   頁表：為了在作業(yè)執(zhí)行過程中精確的查找邏輯地址與物理地址的對應(yīng)關(guān)系夜惭，系統(tǒng)為每個作業(yè)建立一張頁表姻灶，指出邏輯地址中的頁號與物理塊中的塊號的對應(yīng)關(guān)系

   快表：為了提高存取速度，系統(tǒng)設(shè)置了快表用來存放部分頁面诈茧，可以一次訪問主存完成讀寫操作产喉，大大縮短地址轉(zhuǎn)換時間，提高查找速度

9. 編譯：將源碼編譯為機(jī)器碼(若干目標(biāo)模塊/程序段)

   鏈接(靜態(tài)鏈接，裝入時動態(tài)鏈接曾沈，運(yùn)行時動態(tài)鏈接)：將各個模塊的相對地址統(tǒng)一編址得到邏輯地址(裝入模塊)

   裝入(絕對裝入这嚣，靜態(tài)重定位，動態(tài)重定位)：將代碼段邏輯地址與物理地址通過重定位機(jī)制轉(zhuǎn)換后裝入內(nèi)存

10. 重定位：將程序的邏輯地址轉(zhuǎn)換為物理地址的過程

11. 內(nèi)存擴(kuò)充：虛擬存儲器塞俱，覆蓋姐帚，交換技術(shù)

12. 邏輯地址與物理地址

    邏輯地址：將程序段從頭到尾逐一編號后所得到的序號為邏輯地
    物理地址：將內(nèi)存單位進(jìn)行逐一編號后所得的到的序號為物理地址

13. 內(nèi)存保護(hù)方法：界限寄存器方法(上下界寄存器，基址和限長寄存器)障涯，存儲保護(hù)鍵

14. 覆蓋和交換技術(shù)(內(nèi)存擴(kuò)充)

    覆蓋：覆蓋技術(shù)目的在于節(jié)約內(nèi)存罐旗，將內(nèi)存分為常駐段和覆蓋段，覆蓋段又可以分為多個覆蓋段唯蝶，其大小和數(shù)量是由程序的結(jié)構(gòu)來決定的九秀，由程序員來具體劃分(針對同一個程序)

    交換：把暫時不用的某個程序及數(shù)據(jù)部分或全部從內(nèi)存移到外存或相反

15. 內(nèi)存分配方式：連續(xù)分配管理方式和非連續(xù)分配管理方式

    連續(xù)分配管理方式分類：

    1. 單一連續(xù)分配：簡單，無外部碎片粘我，可以采用覆蓋技術(shù)鼓蜒；但只能用于單用戶，單任務(wù)操作系統(tǒng)中征字，有內(nèi)部碎片都弹，存儲器利用率極低
    2. 固定分區(qū)分配(分區(qū)大小相等,分區(qū)大小不等)：無外部碎片，用于控制多個相同對象的控制系統(tǒng)匙姜，可用于多道程序設(shè)計
    3. 動態(tài)分區(qū)分配：存在外部碎片
       動態(tài)分區(qū)數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表畅厢，空閑分區(qū)鏈
       動態(tài)分區(qū)算法：
       首次適應(yīng)算法(每次從鏈?zhǔn)组_始查找滿足的空閑塊分配)
       下次適應(yīng)算法(從上次查找的位置開始查找滿足分配的空閑塊進(jìn)行分配)
       最佳適應(yīng)算法(空閑塊從小到大排列，每次從最小的開始查找最適合的)
       最壞適應(yīng)算法(與最佳相反搁料，每次查找最大的空閑塊分配)

    非連續(xù)分配管理方式分類：(將內(nèi)存劃分為塊)

    1. 基本分頁存儲管理方式：進(jìn)程劃分為頁或详；無外部碎片，有內(nèi)部碎片郭计；邏輯地址結(jié)構(gòu)：頁號+頁內(nèi)偏移 一維地址空間； 兩次訪問內(nèi)存椒振，得到數(shù)據(jù)

    2. 基本分段存儲管理方式：將進(jìn)程劃分為段昭伸，無內(nèi)部碎片,有外部碎片；邏輯地址結(jié)構(gòu)：段號+段內(nèi)偏移 二維地址空間澎迎；兩次訪問內(nèi)存庐杨，得到數(shù)據(jù)

    3. 段頁式存儲管理方式：進(jìn)程劃分為段，段劃分為頁夹供，有內(nèi)部碎片灵份；邏輯地址結(jié)構(gòu)：段號+頁號+頁內(nèi)偏移泽艘；三次訪問內(nèi)存甩卓，得到數(shù)據(jù)

16. 段與頁的區(qū)別 (73頁)

17. 拼接技術(shù)：將分散的多個小空閑塊鏈成一個大的空閑塊(緊湊或緊縮)

18. 動態(tài)重定位分區(qū)分配算法=動態(tài)分區(qū)分配算法+拼接技術(shù)

19. 虛擬內(nèi)存(需要硬件和軟件支持)

    功能：部分裝入，請求調(diào)入谎倔，置換功能

    特點：離散性，多次性氛什，對換性莺葫，虛擬性

20. 局部性原理：

    空間局部性：指在較短時間內(nèi)程序趨向于訪問最近訪問過的內(nèi)存地址附近的內(nèi)存

    時間局部性：指在較短時間內(nèi)程序趨向于在不久的將來再次訪問最近剛訪問過的內(nèi)存地址

21. 虛擬內(nèi)存管理方式：
    (1). 請求分頁存儲管理方式：基本分頁存儲管理+虛擬內(nèi)存的三個特點
    有內(nèi)部碎片，無外部碎片枪眉；兩次訪問內(nèi)存捺檬，得到數(shù)據(jù)

    頁面置換算法：最佳置換算法,先進(jìn)先出置換算法(會產(chǎn)生Belady異常),最近最久未使用算法(LRU)

    時鐘置換算法(CLOCK/NRU)：缺頁置換后，修改標(biāo)志位贸铜，然后下移堡纬；未缺頁，跳到該位置蒿秦，修改標(biāo)志位隐轩，指針不下移

    第二次機(jī)會算法(改良CLOCK)：讀寫位，替換順序 -> 00渤早，01职车，10，11

    頁面分配策略：固定分配局部置換鹊杖，可變分配全局置換悴灵，可變分配局部置換

    頁面調(diào)入策略：預(yù)調(diào)頁策略，請求調(diào)頁策略

    從何處調(diào)入頁面：系統(tǒng)擁有足夠的對換空間(對換區(qū))骂蓖，系統(tǒng)缺少足夠的對換空間(要修改->對換區(qū)积瞒，不修改->文件區(qū))，UNIX方式(未運(yùn)行->文件區(qū)登下，運(yùn)行過->對換區(qū))

    (2). 請求分段存儲管理：有外部碎片茫孔，無內(nèi)部碎片；兩次訪問內(nèi)存被芳，得到數(shù)據(jù)

22. 工作集概念 (81頁)

23. 缺頁中斷：中斷返回后應(yīng)執(zhí)行被中斷的那條指令

計算題考點分析：

1. 基本分頁： 求有效訪問時間(秒s,毫秒ms,微妙us,納秒ns進(jìn)制為1000)

   沒有快表：訪問內(nèi)存的次數(shù)

   有快表：(快表t+內(nèi)存t)命中率+(快表t+2內(nèi)存t)(1-命中率)

2. 請求分頁：求有效訪問時間

   訪問頁在主存中缰贝，且在快表中：快表t+內(nèi)存t

   訪問頁在主存中，不在快表中：快表t+內(nèi)存t+修改快表t+內(nèi)存t

   訪問頁不在主存中：快表t+內(nèi)存t+缺頁t+快表t+內(nèi)存t

   缺頁率和命中率：(快表t+內(nèi)存t)命中率+[(快表t+內(nèi)存t+內(nèi)存t)(1-缺頁率)+(快表t+內(nèi)存t+缺頁t+內(nèi)存t)缺頁率](1-命中率)

   注意：一級頁表需要兩次訪問內(nèi)存畔濒，二級頁表需要三次訪問內(nèi)存

3. 內(nèi)存計算中的地址處理

   十進(jìn)制：邏輯地址/頁面大小=頁號 邏輯地址%頁面大小=頁內(nèi)偏移

   十六進(jìn)制：化為二進(jìn)制剩晴，找出頁號位數(shù)(高幾位)和頁內(nèi)偏移位數(shù)(低幾位)

   然后找到物理塊號化為二進(jìn)制拼接頁內(nèi)偏移=物理地址

   1. 根據(jù)頁面置換算法計算缺頁率，缺頁次數(shù)
   2. 根據(jù)每頁大小侵状，頁表項大小赞弥，地址位數(shù)；計算頁表級數(shù)
   3. 計算指令物理地址：找出頁號趣兄，頁內(nèi)偏移
   4. 段頁式存儲管理：段首地址+段號去從段表中找到頁號绽左，段表中的頁號加上頁號找到物理塊號，物理塊號*每塊大小+頁內(nèi)偏移=物理地址

第四章：文件管理

1. 系統(tǒng)怎樣實現(xiàn)文件共享（97頁）

   基于索引結(jié)點的共享方式(硬鏈接)：不同目錄下使用相同索引結(jié)點艇潭，在索引結(jié)點中再增加一個計數(shù)值來統(tǒng)計指向該索引結(jié)點的目錄項個數(shù)拼窥，只有計數(shù)值為1時才可刪除該索引結(jié)點戏蔑，若計數(shù)值大于1刪除時把計數(shù)值減1即可，增加共享時計數(shù)值加1

   優(yōu)點：實現(xiàn)文件的異名共享

   缺點：當(dāng)文件被多個用戶共享時闯团，文件擁有者不能刪除文件

   【在硬連接中辛臊，目錄項中只有文件名，指向的是共同的索引結(jié)點房交，索引結(jié)點再指向文件彻舰，所以一個文件名修改索引結(jié)點，其他所有文件名的索引結(jié)點都被修改了候味，因為所有文件名指向同一個索引結(jié)點】

   利用符號鏈接實現(xiàn)文件共享(軟連接)：把共享文件的路徑副本復(fù)制過來刃唤，并且只有在文件試圖去訪問時才會更新其路徑副本。

   優(yōu)點：解決了文件擁有者不能夠刪除共享了的文件的問題

   缺點：當(dāng)其他用戶要訪問共享文件時白群，需要逐層查找目錄尚胞，開銷較大

2. 什么是文件的混合索引結(jié)構(gòu)？其主要優(yōu)點是什么帜慢？ (93頁)

   混合索引結(jié)構(gòu)：多種索引分配方式相結(jié)合而形成的一種分配方式笼裳，如直接地址加單級索引分配或兩級索引分配

   優(yōu)點：支持隨機(jī)訪問，易于文件的增刪粱玲，沒有外部碎片

3. 文件的物理結(jié)構(gòu)主要有連續(xù)結(jié)構(gòu)躬柬，連接結(jié)構(gòu)和索引結(jié)構(gòu)，請分別簡述他們的優(yōu)缺點. （ 89頁）

   連續(xù)結(jié)構(gòu)：
   優(yōu)點：實現(xiàn)簡單抽减，可以隨機(jī)訪問磁盤允青，訪問速度快
   缺點：需要連續(xù)的存儲空間，易產(chǎn)生碎片卵沉，磁盤利用率低颠锉，不利于文件的動態(tài)增長，插入和刪除

   鏈接結(jié)構(gòu)：
   優(yōu)點：不要求連續(xù)的存儲空間史汗，磁盤利用率高琼掠，有利于文件的動態(tài)擴(kuò)充，插入和刪除
   缺點：只適合順序訪問存取速度慢淹办，文件數(shù)據(jù)塊之間靠指針鏈接可靠性差

   索引結(jié)構(gòu)：
   優(yōu)點：支持順序和隨機(jī)訪問眉枕，查找效率高，有利于文件刪除
   缺點：索引表會占用額外的存儲空間

4. 考慮文件系統(tǒng)的外存分配,簡述什么是連續(xù)分配方式和索引分配方式怜森？(89頁)

   連續(xù)分配：指創(chuàng)建文件時,需要給文件分配一組連續(xù)的盤塊

   索引分配：為文件的每個分區(qū)單獨(dú)建立一張索引表，該索引表記錄了分配給該文件的所有塊號

5. 簡述用位示圖進(jìn)行文件存儲空間管理的思想和這種方法的優(yōu)缺點?（99頁）

   思想：利用二進(jìn)制的一位來表示磁盤中一個塊的使用情況谤牡，若磁盤空閑用1表示副硅，否則用0表示；從而得到一張位示圖表翅萤，反映了所有磁盤塊的信息

   優(yōu)點：很容易找到一個連續(xù)的空閑塊

   缺點：整個磁盤的位示圖文件較大恐疲，在磁盤空閑塊較少時腊满，搜索空間塊浪費(fèi)一些時間

6. 什么是順序文件？說明順序文件的優(yōu)缺點 (88頁)

   順序文件：文件中的記錄按照某種順序排列所形成的文件

   優(yōu)點：可以隨機(jī)存取培己，存取效率高

   缺點：文件較大時碳蛋，檢索效率低下，增加和刪除記錄比較麻煩

7. 文件的邏輯結(jié)構(gòu)：指一個文件的結(jié)構(gòu),是一系列的邏輯記錄的組成的順序關(guān)系

   無結(jié)構(gòu)文件：流式文件

   有結(jié)構(gòu)文件：順序文件省咨，索引文件肃弟，索引順序文件，直接文件零蓉，散列文件

8. 文件的物理結(jié)構(gòu)：指文件在外存上的存儲組織形式笤受，與外存的分配有關(guān)

   外存分配方式：連續(xù)分配，鏈接分配(隱式鏈接,顯示鏈接)敌蜂，索引分配(單級索引,兩級索引),混合索引(直接地址,一次間接地址,多次間接地址)

9. 文件系統(tǒng)：操作系統(tǒng)中與文件管理有關(guān)的軟件和數(shù)據(jù)集合

   目的：提高存儲空間利用率箩兽，減少存儲時間

11. 文件目錄：文件名與物理地址的對應(yīng)關(guān)系，是一個文件章喉，存儲在外存中是文件目錄項/文件控制塊的有序集合
    功能：實現(xiàn)文件按名存取汗贫，提高檢索速度，允許文件同名秸脱，允許文件共享

12. 文件控制塊和索引結(jié)點

    文件由文件控制塊落包，文件體兩部分組成，文件體就是文件本身撞反，文件控制塊是為了描述該文件由操作系統(tǒng)生成的

    文件控制塊：文件名妥色，文件結(jié)構(gòu)，文件物理位置遏片，存取控制信息嘹害，管理信息

    索引結(jié)點：文件控制塊 - 文件名

13. 文件保護(hù)：訪問控制矩陣，訪問控制表吮便，用戶權(quán)限表笔呀，口令與密碼

14. 空閑存儲空間管理：空閑表法，位示圖法髓需，空閑塊鏈接法许师，鏈接索引塊

15. 磁盤調(diào)度算法：

    先來先服務(wù)(FCFS)：按請求順序進(jìn)行調(diào)度

    最短尋道時間(SSTF)：可能會產(chǎn)生饑餓

    掃描算法(SCAN)：電梯調(diào)度算法 LOOK為SCAN的優(yōu)化->不會走到端點

    循環(huán)掃描算法(C-SCAN)：C-LOOK為C-SCAN的優(yōu)化 -> 不會走到端點

16. 磁盤讀寫操作時間：尋道時間+延遲時間+傳輸時間

    尋道時間：磁頭移動到指定磁道時間：T=m*n+s

    延遲時間：從磁道定位到某一扇區(qū)時間：T=1/2r r為轉(zhuǎn)速

    傳輸時間：讀取數(shù)據(jù)時間：T=b/rN b為每次所讀字節(jié)數(shù)，N為一個磁道上的字節(jié)數(shù)

17. 磁盤->盤面->磁道(同心圓)->扇區(qū)(環(huán)的弧)

    柱面號 · 盤面號 · 扇區(qū)號

計算題考點：

1. 混合索引分配：直接地址僚匆，一級間接地址微渠，二級間接地址，三級間接地址

   求地址空間大羞掷蕖：目錄項逞盆，各級地址大小相加

   讀取某個文件要訪問磁盤次數(shù)：直接地址為1次，一級間接地址為2次松申，以此類推

2. 計算n個柱面云芦，m個磁道俯逾，p個扇區(qū)；計算文件的第x個邏輯記錄存放在那個柱面舅逸，那個磁道桌肴，那個扇區(qū)；

   從0開始編址：柱面=x除mp 磁道=(x模mp)除m 扇區(qū)：(x模mp)模m

3. 計算順序存放文件的讀取時間：文件記錄數(shù)*一轉(zhuǎn)時間+一塊的處理時間

   交叉數(shù)據(jù)存儲：(數(shù)據(jù)讀取時間+處理時間+間隔時間)*(文件記錄數(shù)-1)+ 一塊的處理時間

4. 磁盤調(diào)度算法計算請求隊列移過的磁道數(shù)目(注意最短尋道可能隨時轉(zhuǎn)向問題)

第五章：設(shè)備管理

1. 緩沖區(qū)的實現(xiàn)方法琉历，緩沖區(qū)的類型和引入緩沖區(qū)的目的(王道278)

   緩沖實現(xiàn)方法：
   ①采用專門的硬件緩沖器
   ②在內(nèi)存劃出一個具有n個單元的專用緩沖區(qū)坠七，以便存放輸入輸出的數(shù)據(jù)

   緩沖區(qū)類型：單緩沖區(qū)，雙緩沖區(qū)善已，循環(huán)緩沖區(qū)灼捂，緩沖池

   引入目的：
   (1)緩和CPU和IO設(shè)備間速度不匹配的矛盾
   (2)減少對CPU的中斷頻率，放寬對中斷響應(yīng)時間的限制
   (3)解決速度粒度不匹配的問題
   (4)提高CPU和IO設(shè)備之間的并行性

2. 什么是設(shè)備獨(dú)立性换团，如何實現(xiàn)悉稠？ (119頁)

   設(shè)備獨(dú)立性：指應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備

   為了實現(xiàn)設(shè)備獨(dú)立性，必須在設(shè)備驅(qū)動程序之上設(shè)置一層設(shè)備獨(dú)立性軟件艘包，用來執(zhí)行所有IO設(shè)備的公用操作的猛，并向用戶層軟件提供統(tǒng)一接口。關(guān)鍵是系統(tǒng)中必須設(shè)置一張邏輯設(shè)備表用來進(jìn)行邏輯設(shè)備到物理設(shè)備的映射,每個表項包括請求分配設(shè)備時想虎，系統(tǒng)為他們分配相應(yīng)的物理設(shè)備卦尊，并在表中建立一個表項.

3. 程序IO控制，中斷驅(qū)動方式舌厨，DMA方式岂却，通道控制方式流程 (109頁)

• 程序IO控制：IO設(shè)備傳輸過程完全由CPU指令來控制完成，需要CPU不斷的去對IO設(shè)備進(jìn)行查詢看是否需要進(jìn)行數(shù)據(jù)傳輸裙椭，如果需要則進(jìn)行讀取躏哩，寫入等操作（IO完全由CPU的程序來控制）
  優(yōu)點：工作過程簡單 缺點：CPU利用率低
  流程圖：給IO模塊發(fā)出讀指令 -> 讀IO模塊的狀態(tài) -> 檢查狀態(tài)(未準(zhǔn)備好則返回上一步繼續(xù)讀取狀態(tài)，準(zhǔn)備好則繼續(xù)下一步) -> 從IO模塊中讀取字 -> 往存儲塊中寫入字 -> 檢查是否完成(未完成則返回第一步揉燃，完成則進(jìn)行下一條指令)
  輪詢方式：CPU與IO設(shè)備進(jìn)行通信扫尺，串行工作

• 中斷驅(qū)動方式：CPU不需要不斷查詢，測試IO設(shè)備炊汤，正驻，而是只有在需要數(shù)據(jù)傳輸時才通過中斷方式通知CPU來執(zhí)行設(shè)備中斷處理程序，將數(shù)據(jù)從寄存器傳送到某一特定地址抢腐。
  優(yōu)點：CPU和IO設(shè)備間可以并行工作姑曙，提高了CPU利用率
  缺點：設(shè)備多時，中斷次數(shù)過多消耗大量CPU時間
  流程圖：給IO模塊發(fā)出讀指令 -> 讀IO模塊的狀態(tài) -> 檢查狀態(tài)(準(zhǔn)備好則下一步) -> 從IO模塊中讀取字 -> 往存儲塊中寫入字 -> 檢查是否完成(未完成則返回第一步迈倍，完成則進(jìn)行下一條指令)
  CPU與IO并行工作

• DMA控制方式：DMA控制器在外存和內(nèi)存之間開辟直接的數(shù)據(jù)交換通道渣磷，僅在一批數(shù)據(jù)傳輸完成后產(chǎn)生中斷，CPU再介入控制
  優(yōu)點：可使CPU與外設(shè)并行授瘦，交換過程中速度加快醋界，不需要CPU的干預(yù)
  缺點：CPU依然要有許多控制，且每臺設(shè)備都需要DMA控制器
  四類寄存器：命令狀態(tài)寄存器CR提完，內(nèi)存地址寄存器MAR形纺，數(shù)據(jù)寄存器DR，數(shù)據(jù)計數(shù)器DC
  流程：設(shè)置MAR和DC的值 -> 啟動DMA傳送命令 -> 挪用存儲器周期傳送數(shù)據(jù)字 -> 存儲器地址增1徒欣，計數(shù)寄存器減1 -> DC=0?(否返回第三步 是繼續(xù)下一步) -> 請求中斷
  在外設(shè)和內(nèi)存之間開辟直接的數(shù)據(jù)交換通路(IO設(shè)備和主存)
  通道控制器：通道是一個具有輸入輸出處理器控制的輸入輸出組件逐样，比DMA更少依賴CPU
  中斷控制方式(字節(jié)后中斷),DMA控制方式(塊后中斷),

• 通道控制方式(自我管理,一個通道控制多個設(shè)備，設(shè)備與內(nèi)存直接交換數(shù)據(jù))
  字節(jié)多路通道：連接多個慢速和中速設(shè)備打肝，以字節(jié)為單位
  數(shù)組選擇通道：連接多臺高速設(shè)備脂新，每次只允許一個設(shè)備傳輸數(shù)據(jù)，通道獨(dú)占粗梭，利用率低
  數(shù)組多路通道：高數(shù)據(jù)傳輸率争便，高通道利用率

  通道控制與DMA的區(qū)別：
  首先，DMA控制方式中需要CPU來控制所傳數(shù)據(jù)塊的大小和傳輸?shù)膬?nèi)存断医，而通道控制方式中這些信息都是由通道來控制管理的滞乙；其次，一個DMA控制器對應(yīng)一臺設(shè)備與內(nèi)存?zhèn)鬟f數(shù)據(jù)鉴嗤，而一個通道可以控制多臺設(shè)備與內(nèi)存的數(shù)據(jù)交換

4. 什么是DMA方式斩启？它與中斷方式的主要區(qū)別是什么？(111頁)

   DMA：DMA是直接存儲器存取醉锅。DMA傳輸將數(shù)據(jù)從一個地址空間復(fù)制到另一個地址空間兔簇。當(dāng)CPU初始化這個傳輸動作，動作是由DMA控制器來實行和完成的硬耍，在實現(xiàn)DMA傳輸時垄琐，是由DMA控制器直接掌管總線，在結(jié)束傳輸后默垄，在將控制權(quán)交給CPU

   主要區(qū)別：中斷控制方式在每個數(shù)據(jù)傳輸完成后中斷CPU此虑，而DMA方式則是在所要求傳輸?shù)囊慌鷶?shù)據(jù)全部傳輸完成時才中斷CPU；中斷控制方式的數(shù)據(jù)傳輸在中斷處理時由CPU控制完成口锭，而DMA控制方式則是在DMA控制器下完成朦前；DMA方式以存儲器為核心，中斷控制方式以CPU為核心鹃操；DMA方式傳輸批量數(shù)據(jù)韭寸，中斷控制方式傳輸以字節(jié)為單位

5. 簡述什么是SPOOLING技術(shù) (119頁)

   SPOOLING技術(shù)：是利用專門的外圍控制機(jī)，將低速IO設(shè)備上的數(shù)據(jù)傳輸?shù)礁咚俅疟P上荆隘，或者相反恩伺，又稱假脫機(jī)技術(shù)；可以將獨(dú)占設(shè)備改造成共享的虛擬設(shè)備椰拒，提高獨(dú)占設(shè)備利用率

   輸入井輸出井(磁盤)晶渠，輸入緩沖區(qū)輸出緩沖區(qū)(內(nèi)存)凰荚，輸入進(jìn)程輸出進(jìn)程

   提高IO的速度，將獨(dú)占設(shè)備改造成共享設(shè)備褒脯，實現(xiàn)虛擬設(shè)備功能

6. 物理設(shè)備便瑟，邏輯設(shè)備與邏輯設(shè)備名的好處

   物理設(shè)備：進(jìn)行實際輸入輸出操作的硬件設(shè)備

   邏輯設(shè)備：物理設(shè)備屬性的表示。它并不特指某個具體的物理設(shè)備番川，而是對應(yīng)于一批設(shè)備

   使用邏輯設(shè)備名的好處：增加設(shè)備分配的靈活性到涂；易于實現(xiàn)IO重定向，所謂IO重定向颁督，是指用于IO操作的設(shè)備可以更換践啄，而不必改變應(yīng)用程序。

7. 軟件層次結(jié)構(gòu)： 每類設(shè)備只需要一個設(shè)備驅(qū)動程序

   用戶層IO軟件：進(jìn)行IO調(diào)用沉御，格式化IO屿讽，SPOOLING

   設(shè)備獨(dú)立性軟件：命名，保護(hù)嚷节，阻塞聂儒，緩沖，分配

   設(shè)備驅(qū)動程序：建立設(shè)備寄存器硫痰，檢查狀態(tài)衩婚，磁盤調(diào)度

   中斷處理程序：當(dāng)IO結(jié)束時喚醒驅(qū)動程序

   硬件設(shè)備：執(zhí)行IO操作

8. 設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)

   設(shè)備控制表DCT：

   控制器控制表COCT：

   通道控制表CHCT：

   系統(tǒng)控制表SDT：

計算題：

1. (計算題)內(nèi)存分配和頁面置換

(PV大題)訂票與查詢：可多個查詢者，訂票者和查詢者不可同時操作且要求按請求順序提供服務(wù)(互斥訪問)效斑，訂票者與查詢者不能同時訪問非春，訂票者之間也不可同時訪問，要求按用戶請求次序執(zhí)行操作缓屠。（讀寫者問題）

2. (PV大題)水果盤奇昙，父親放蘋果，母親放橘子敌完，女兒取水果储耐。要求：只有一個人可以操作果盤，只有盤里同時有蘋果和橘子時女兒才可以取水果滨溉，并且同時把兩個水果取走什湘。

3. (計算題)段頁式虛擬存儲器

(PV大題)N個生產(chǎn)者，M個消費(fèi)者晦攒，緩沖區(qū)大小為K(一個互斥信號量和兩個同步信號量)

4. (計算題)二級頁表分頁存儲闽撤，計算邏輯地址結(jié)構(gòu)示意圖和由邏輯地址計算物理地址

(PV大題)南北車道互斥通過(三個互斥信號量和兩個整型記錄變量)

5. (計算題)混合索引文件系統(tǒng)，計算最大單個文件和某個索引結(jié)點文件可能訪問磁盤的次數(shù)

(PV大題)三個進(jìn)程共同使用一個緩沖區(qū),p0產(chǎn)生數(shù),p1計算平方值,p2計算立方值 (full1=0,full2=0,empty1=0,empty2=0)

6. (計算題)虛擬分頁系統(tǒng)計算頁表級數(shù)和設(shè)計頁表使所需頁數(shù)最少

(PV題)爸爸脯颜，兒子哟旗，女兒放水果問題(mutex=1,empty=2,apple=0,orange=0)

7. 請求分頁計算指令的物理地址，磁盤調(diào)度計算磁頭移動的磁道數(shù)，進(jìn)程調(diào)度計算完成/周轉(zhuǎn)/平均周轉(zhuǎn)/帶權(quán)周轉(zhuǎn)時間

8. 頁面置換算法求缺頁中斷次數(shù)