Chapter-One-操作系統(tǒng)概述

1、精選優(yōu)質(zhì)文檔-傾情為你奉上Chapter One 操作系統(tǒng)概述操作系統(tǒng)概念：操作系統(tǒng)是指控制和管理整個(gè)計(jì)算機(jī)系統(tǒng)的硬件和軟件資源，并合理組織和調(diào)度計(jì)算機(jī)的工作和資源分配，是最基本的系統(tǒng)軟件。特征：并發(fā)、共享（兩個(gè)最基本的特征）、虛擬、異步。并發(fā)：指同一時(shí)間間隔內(nèi)發(fā)生，區(qū)別于并行。微觀上分時(shí)地交替執(zhí)行。 功能：是計(jì)算機(jī)系統(tǒng)資源（處理機(jī)、存儲(chǔ)器、文件、設(shè)備）的管理者用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口：命令接口（允許用戶直接使用）（1）聯(lián)機(jī)（交互式）命令接口（適用于分時(shí)or實(shí)時(shí)）（2）脫機(jī)（批處理）命令接口程序接口（=系統(tǒng)調(diào)用命令）GUI（圖形接口調(diào)用系統(tǒng)命令）注：在多道程序環(huán)境下，處理機(jī)的分配和運(yùn)行都

2、以進(jìn)程（或線程）為單位。系統(tǒng)調(diào)用是由操作系統(tǒng)提供給用戶的，它只能通過用戶程序間接使用。操作系統(tǒng)的發(fā)展：批處理>分時(shí)>實(shí)時(shí)>網(wǎng)絡(luò)和分布式批處理（缺點(diǎn)：沒有交互能力）單道批處理>順序性（CPU大量時(shí)間在空閑等待I/O） 多道批處理（失去封閉性）> 制約性、間斷性、共享性特點(diǎn)：多道、宏觀上并行，微觀上串行。分時(shí)系統(tǒng)：（以時(shí)間片為單位）允許多個(gè)用戶以交互的方式使用計(jì)算機(jī) 特點(diǎn)：同時(shí)性、交互性、獨(dú)立性、及時(shí)性分時(shí)系統(tǒng)能較快、及時(shí)接收并處理命令，快速響應(yīng)用戶。（通常采用優(yōu)先級(jí)+非搶占式調(diào)度算法）分時(shí)系統(tǒng)中，時(shí)間片一定時(shí)，用戶數(shù)越多，響應(yīng)時(shí)間越長(zhǎng)。實(shí)時(shí)系統(tǒng)：在某個(gè)時(shí)間限制內(nèi)完成

3、某些緊急任務(wù)而不需時(shí)間片排隊(duì)特點(diǎn)：及時(shí)性、可靠性（通常采用搶占式優(yōu)先級(jí)高者優(yōu)先算法）網(wǎng)絡(luò)（網(wǎng)絡(luò)資源共享）和分布式：區(qū)別是在分布式中，若干計(jì)算機(jī)相互協(xié)同完成同一任務(wù)系統(tǒng)調(diào)用（運(yùn)行在核心態(tài)）（涉及設(shè)備、文件、進(jìn)程、內(nèi)存）用戶程序凡是與資源有關(guān)的操作（存儲(chǔ)分配、I/O、管理文件）都必須通過系統(tǒng)調(diào)用。過程：傳遞系統(tǒng)調(diào)用參數(shù)>執(zhí)行陷入（trap）指令（用戶態(tài)）>執(zhí)行系統(tǒng)調(diào)用相應(yīng)服務(wù)程 序（核心態(tài)）>返回用戶程序系統(tǒng)調(diào)用功能是操作系統(tǒng)向用戶程序提供的接口注：系統(tǒng)調(diào)用是一種特殊公共子程序?qū)Ｐ?專注-專業(yè)陷入指令是唯一一個(gè)只能在用戶態(tài)執(zhí)行，而不可在核心態(tài)執(zhí)行的指令。廣義指令：也就是系統(tǒng)調(diào)用命

4、令（可能在用戶態(tài)調(diào)用，但處理必須在核心態(tài)）用戶程序（用戶自編or系統(tǒng)外層應(yīng)用程序）工作在用戶態(tài)；內(nèi)核程序工作在核心態(tài)。 特權(quán)指令：只能在核心態(tài)運(yùn)行的指令如：I/O指令、置中斷指令、存取用戶內(nèi)存保護(hù)的寄存器、送程序狀態(tài)字（可區(qū)分目態(tài)、管 態(tài)）到程序狀態(tài)字寄存器。（包括系統(tǒng)調(diào)用類、時(shí)鐘類、中斷和原語(yǔ)指令，清內(nèi)存、分配系統(tǒng)資源、修改虛擬存儲(chǔ)里的頁(yè)表段表、修改用戶訪問權(quán)限等）中斷和異常：引入中斷技術(shù)的初衷是提高多道程序運(yùn)行環(huán)境中CPtt的利用率中斷的分類：內(nèi)中斷（異常、例外、陷入trap）（不可被屏蔽！）自愿中斷指令中斷：訪管指令（只能用戶態(tài)使用） 強(qiáng)迫中斷硬件故障（缺頁(yè)）軟件中斷（非法操作碼、地址越

5、界、算數(shù)溢出、虛存系統(tǒng)缺頁(yè)以及專門的陷入）外中斷（強(qiáng)迫中斷）外設(shè)請(qǐng)求：I/O結(jié)束、時(shí)鐘中斷人的干預(yù)：用戶按ESC or 退出鍵注：區(qū)分內(nèi)/外中斷看信號(hào)來(lái)源：CPU內(nèi)部/外部。訪管中斷：用戶程序在用戶態(tài)下要使用特權(quán)指令（由訪管中斷引起）引起的中斷。用戶程序需要輸入/輸出時(shí)（I/O），調(diào)用OS提供的接口，此時(shí)引起訪管中斷。 所有中斷都是在核心態(tài)下執(zhí)行的?。ㄟM(jìn)程切換、對(duì)資源的釋放）用戶態(tài)（發(fā)生中斷 or 異常）>核心態(tài) （通過硬件、系統(tǒng)調(diào)用、訪管指令實(shí)現(xiàn)） 核心態(tài)（使用特權(quán)指令）>用戶態(tài) （通過中斷返回指令）注：中斷系統(tǒng)（OS必需）和地址映射需要硬件支持，進(jìn)程調(diào)度不需要。原語(yǔ)處于最底層；

6、不可分割的指令序列；運(yùn)行時(shí)間短，調(diào)用頻繁PV操作是一種低級(jí)的進(jìn)程通信語(yǔ)言，由兩個(gè)不可中斷的過程組成，并非系統(tǒng)調(diào)用。體系結(jié)構(gòu)：大內(nèi)核（高性能；結(jié)構(gòu)混亂）、微內(nèi)核（內(nèi)核功能少；在用戶態(tài)、核心態(tài)之間切換頻繁，性能低；結(jié)構(gòu)清晰；添加系統(tǒng)服務(wù)時(shí)不必修改內(nèi)核；使系統(tǒng)更可靠）Chapter Two 進(jìn)程管理進(jìn)程概念：進(jìn)程（動(dòng)態(tài)）是資源分配的一個(gè)獨(dú)立單位。程序：靜態(tài)進(jìn)程的特征：動(dòng)態(tài)性（最基本）、并發(fā)性（重要特征）、獨(dú)立性、異步性、結(jié)構(gòu)性（進(jìn)程實(shí) 體（進(jìn)程映像）由程序段、數(shù)據(jù)段、PCB三部分組成）注：進(jìn)程的組織（結(jié)構(gòu)性）：PCB、程序段（多個(gè)進(jìn)程可運(yùn)行同一程序）、數(shù)據(jù)段PCB是進(jìn)程存在的唯一標(biāo)志。主要包括了：進(jìn)

7、程描述信息（ID）、進(jìn)程控制（優(yōu)先級(jí)）和管理信息、資源分配和處理機(jī)相關(guān)（不重要）。二進(jìn)制代碼和常量放在正文段；動(dòng)態(tài)分配的存儲(chǔ)區(qū)在數(shù)據(jù)堆段；臨時(shí)用的變量在數(shù)據(jù)棧段。進(jìn)程的狀態(tài)：運(yùn)行、就緒、阻塞、創(chuàng)建、結(jié)束運(yùn)行>阻塞（等待）主動(dòng)阻塞阻塞>就緒 被動(dòng)喚醒注：在可剝奪OS中，當(dāng)有更高優(yōu)先級(jí)的進(jìn)程就緒時(shí)，調(diào)度程序?qū)⒄趫?zhí)行的進(jìn)程>就緒態(tài)，讓更高優(yōu)先級(jí)的執(zhí)行。就緒態(tài)：進(jìn)程已處于準(zhǔn)備運(yùn)行的狀態(tài)（只缺CPU了?。┻M(jìn)程切換：（區(qū)別于調(diào)度！切換是執(zhí)行行為，而調(diào)度是決策行為）：時(shí)間片用完、主動(dòng)放棄 處理機(jī)、被更高優(yōu)先級(jí)的進(jìn)程剝奪注：進(jìn)程切換的過程包括更新PCB信息引起創(chuàng)建進(jìn)程的操作：終端用戶登錄系

8、統(tǒng)、作業(yè)調(diào)度、系統(tǒng)提供服務(wù)、用戶程序的應(yīng)用請(qǐng)求注：用戶進(jìn)程被創(chuàng)建后，隨著運(yùn)行的正?；虿徽＝Y(jié)束而撤銷。（進(jìn)程是有一定生命周期 的?。┻M(jìn)程的終止：異常結(jié)束：存儲(chǔ)區(qū)越界、保護(hù)錯(cuò)、非法指令、特權(quán)指令錯(cuò)、I/O故障 正常結(jié)束：任務(wù)已完成 外界干預(yù)（人為、OS干預(yù)、父進(jìn)程的請(qǐng)求or終止）阻塞（等待資源）：請(qǐng)求資源失敗、等待某操作的完成、數(shù)據(jù)未到達(dá)、無(wú)事可做等喚醒（資源到達(dá)）：I/O操作已完成 or 數(shù)據(jù)已到，調(diào)用喚醒原語(yǔ)進(jìn)程的通信一個(gè)進(jìn)程不能直接訪問另一個(gè)進(jìn)程的地址空間共享存儲(chǔ)（互斥訪問）：低級(jí)方式：基于數(shù)據(jù)結(jié)構(gòu)的共享；高級(jí)方式：基于存儲(chǔ)區(qū)消息傳遞：直接通信方式：接收進(jìn)程從消息隊(duì)列中取得消息； 間接通信

9、方式：將消息掛到某個(gè)中間實(shí)體（郵箱）管道通信：利用一種特殊的pipe文件連接兩個(gè)進(jìn)程。管道只能采用半雙工通信，某一時(shí)間段內(nèi)只能實(shí)現(xiàn)單向傳輸。如果要實(shí)現(xiàn)雙向同時(shí)通信，則需 設(shè)置兩個(gè)管道。（原理：Chapter 5緩沖區(qū)）注：從管道讀數(shù)據(jù)是一次性操作，數(shù)據(jù)一旦被讀取，它就從管道中被拋棄線程線程的引入：減小程序的時(shí)空開銷，提高程序并發(fā)執(zhí)行的程度，提高系統(tǒng)效率線程是程序執(zhí)行的最小單元，并不擁有任何系統(tǒng)資源（進(jìn)程才有），是獨(dú)立調(diào)度的基本單 位。同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程的切換；切換到另一進(jìn)程中的線程才會(huì)切換。同一進(jìn)程或者不同進(jìn)程內(nèi)的線程都可以并發(fā)執(zhí)行。用戶級(jí)線程：所有工作都由應(yīng)用程序完成，無(wú)需內(nèi)

10、核干涉。多線程模型：多對(duì)一模型：缺點(diǎn)>一個(gè)線程阻塞會(huì)導(dǎo)致整個(gè)進(jìn)程都被阻塞 注：線程包含CPU現(xiàn)場(chǎng)，可以獨(dú)立執(zhí)行程序。只有內(nèi)核級(jí)線程才是處理機(jī)分配的單位！CPtt調(diào)度作業(yè)調(diào)度（高級(jí)DD）：內(nèi)存與輔存（外存）之間的DD；對(duì)于每個(gè)進(jìn)程只調(diào)入/調(diào)出一次。 調(diào)入建立PCB，調(diào)出才撤銷PCB。內(nèi)存DD（中級(jí)DD）：將暫時(shí)不運(yùn)行的進(jìn)程調(diào)至外存等待。引入中級(jí)DD為了提高內(nèi)存利用率和吞吐量（調(diào)到外存等待的進(jìn)程狀態(tài)為掛起態(tài)）進(jìn)程DD（低級(jí)DD）：內(nèi)存>CPU，是OS中最基本的一種DD；一般OS中必須配置，使用頻率很高。帶權(quán)周轉(zhuǎn)時(shí)間=作業(yè)周轉(zhuǎn)T/作業(yè)實(shí)際運(yùn)行T 不能進(jìn)行進(jìn)程調(diào)度/切換的情況：處理中斷過程

11、中進(jìn)程在OS內(nèi)核程序臨界區(qū)>需要獨(dú)占式訪問共享資源（不能進(jìn)行進(jìn)程DD但還是能進(jìn)行CPU調(diào)度！前提：不能破壞臨界資源使用規(guī)則）需要完全屏蔽中斷的原子操作（不可分割！連中斷都要屏蔽，DD更別說了）（如：加鎖、解鎖、中斷現(xiàn)場(chǎng)保護(hù)/恢復(fù)） 應(yīng)該進(jìn)行進(jìn)程調(diào)度/切換的情況：發(fā)生引起DD的條件且當(dāng)前進(jìn)程無(wú)法繼續(xù)執(zhí)行下去（非剝奪方式）中斷or trap處理結(jié)束后，返回被中斷進(jìn)程的用戶態(tài)程序執(zhí)行現(xiàn)場(chǎng)前，可以馬上進(jìn)行DD與切換。（剝奪方式）調(diào)度方式：剝奪式（搶占）、非剝奪式（非搶占）剝奪式：當(dāng)某個(gè)更緊急的進(jìn)程要CPU時(shí)，立即暫停正在執(zhí)行的進(jìn)程，先分給更緊急的。（必 須遵循一定規(guī)則，如：優(yōu)先權(quán)、SJF or

12、時(shí)間片）優(yōu)點(diǎn)：提高系統(tǒng)吞吐率和響應(yīng)效率非剝奪式：一旦CPU分配給一個(gè)進(jìn)程，該進(jìn)程保持CPU直到終 止 or 轉(zhuǎn)換到等待態(tài)。特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷?。贿m用于批處理，不能用于分時(shí) or 實(shí)時(shí)！調(diào)度算法：FCFS、SJF、優(yōu)先級(jí)DD、高響應(yīng)比優(yōu)先、時(shí)間片輪轉(zhuǎn)、多級(jí)反饋隊(duì)列DD。FCFS：屬于不可剝奪算法！特點(diǎn)：算法簡(jiǎn)單；有利于CPU繁忙型作業(yè)，不利于I/O繁忙型作業(yè)。SJF：會(huì)產(chǎn)生饑餓現(xiàn)象，是調(diào)度策略問題。（默認(rèn)”非搶占”，也有搶占式） 特點(diǎn)：平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少！優(yōu)先級(jí)DD：靜態(tài)優(yōu)先級(jí)：優(yōu)先級(jí)在創(chuàng)建進(jìn)程時(shí)確定，整個(gè)運(yùn)行期間不變動(dòng)態(tài)優(yōu)先級(jí)：隨著進(jìn)程執(zhí)行時(shí)間增加，其優(yōu)先權(quán)下降。高響應(yīng)比優(yōu)先

13、：Rp=(waitT+ServeT)/ServeT時(shí)間片輪轉(zhuǎn)（隊(duì)列的思想）：主要適用于分時(shí)系統(tǒng)；絕對(duì)可搶占；時(shí)間片過大時(shí)，相當(dāng)于FCFS注：I/O型作業(yè)優(yōu)先權(quán)高于計(jì)算型作業(yè)！I/O作業(yè)要及時(shí)完成，無(wú)法長(zhǎng)期保存輸入/輸出的數(shù)據(jù)。處理機(jī)DD算法不影響作業(yè)執(zhí)行或輸入/輸出操作的時(shí)間，只影響作業(yè)在就緒隊(duì)列中等待所花的時(shí)間。（即DD算法優(yōu)劣只需考慮等待時(shí)間）進(jìn)程同步臨界資源（獨(dú)占資源）：一次僅允許一個(gè)進(jìn)程訪問使用的資源（如：打印機(jī)、共享變量、共享緩沖區(qū)、公用隊(duì)列）共享資源：磁盤存儲(chǔ)介質(zhì)、可重入代碼（一次可供多個(gè)進(jìn)程使用，不允許任何修改的代碼>共享程序）臨界區(qū)：進(jìn)程中訪問臨界資源的那段代碼注：進(jìn)程處

14、于臨界區(qū)時(shí)，不能進(jìn)行進(jìn)程DD，但是能進(jìn)行處理機(jī)/CPU調(diào)度！但要不能破壞臨界資源使用規(guī)則同步機(jī)制遵循的原則：空閑讓進(jìn)忙則等待有限等待讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)釋放處理器實(shí)現(xiàn)臨界資源互斥的基本方法：（以下都不滿足”讓權(quán)等待”?。┸浖?jiǎn)螛?biāo)志法（只能按順序進(jìn)入）雙標(biāo)志法（同時(shí)進(jìn)入臨界區(qū)）雙標(biāo)后檢測(cè)（可能造成饑餓）Petersons 算法（雙重，主動(dòng)謙讓，將”鑰匙”送給對(duì)方，最終只有一個(gè)可通過）P73方四行代碼硬件：TestAndSet（原子操作） or Swap（簡(jiǎn)單了解） 特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單；適用于多處理機(jī)；不滿足”讓權(quán)等待”信號(hào)量整型信號(hào)量：表示資源數(shù)量 （不滿足”讓權(quán)等待”）記錄型信號(hào)

15、量：s.value<0時(shí)（=0也不算是等待！），|s.value|代表鏈表中已被阻塞的該信號(hào)進(jìn)程的數(shù)目（即等待進(jìn)入臨界區(qū)的）遵循了”讓權(quán)等待”原則信號(hào)量機(jī)制實(shí)現(xiàn)同步與互斥互斥：設(shè)置互斥信號(hào)量mutex，初值為1。semaphore mutex=1;同步：必須保證”一前一后”（前V后P）執(zhí)行的操作。設(shè)置同步信號(hào)量S，初值為0。 注：同步：要為每一對(duì)前驅(qū)關(guān)系各設(shè)置一個(gè)信號(hào)量。P、V操作必須成對(duì)出現(xiàn)題 型 ： 生 產(chǎn) 者 消 費(fèi) 者 ： semaphore mutex = 1; /互斥信號(hào)量semaphore empty = n; /同步信號(hào)量，空閑緩沖區(qū)的數(shù)量semaphore full =

16、 0; /同步信號(hào)量，產(chǎn)品的數(shù)量（非空緩沖區(qū)的數(shù)量）多生產(chǎn)者多消費(fèi)者：P081吃蘋果吃橘子吸煙者問題：P085semaphore mutex = 1; /（桌子）互斥信號(hào)量>但是此題不需要！ semaphore offer1 = 0; /同步互斥量，桌子上組合1的數(shù)量semaphore finish = 0; /表示抽煙完成的信號(hào)int i = 0; /對(duì)i取余然后V(offer)，用于實(shí)現(xiàn)”輪流”抽煙（根據(jù)題目要求）讀者寫者：P082（讀寫公平法略繁）semaphore mutex = 1; /對(duì)count=0時(shí)進(jìn)行保護(hù)，實(shí)現(xiàn)第一個(gè)讀者和第二個(gè)一起semaphore rw = 1; /

17、保證讀者寫者互斥訪問文件int count = 0; /讀進(jìn)程的數(shù)量哲學(xué)家進(jìn)餐死鎖定義：多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的互相等待原因：競(jìng)爭(zhēng)系統(tǒng)資源（不可剝奪資源）；獨(dú)占資源分配不當(dāng)進(jìn)程推進(jìn)順序非法；請(qǐng)求和釋放資源的順序不當(dāng) or 信號(hào)量使用不當(dāng)死鎖的必要條件：互斥；不剝奪；請(qǐng)求和保持；循環(huán)等待（任一條件不滿足時(shí)則不發(fā)生死鎖）不剝奪：未使用完之前不能被其他進(jìn)程強(qiáng)行奪走，只能是主動(dòng)釋放！請(qǐng)求和保持：保持資源時(shí)又請(qǐng)求被其他進(jìn)程占有的資源，對(duì)已獲得的資源保持不放。死鎖的處理策略：死鎖預(yù)防（通過設(shè)立限制條件，破壞四個(gè)必要條件，但互斥無(wú)法破壞，超級(jí)少見?。㏒POOLing技術(shù)：把互斥資源改造為允許共享使用包括：

18、采用靜態(tài)分配法，一次申請(qǐng)完全部資源；采用順序資源分配法，按編號(hào)死鎖避免：在資源動(dòng)態(tài)分配過程中，用一些算法防止系統(tǒng)進(jìn)入不安全狀態(tài)。 包括：銀行家算法（Max、Allocation、Need、Available）死鎖檢測(cè)：資源分配圖（當(dāng)不可完全化簡(jiǎn)時(shí)為死鎖狀態(tài)）；死鎖定理死鎖解除：資源剝奪法（被動(dòng)）撤銷進(jìn)程 進(jìn)程回退法（主動(dòng)釋放）注：出現(xiàn)環(huán)路不一定都會(huì)導(dǎo)致死鎖。死鎖and饑餓（不安全狀態(tài)）：都是由資源分配策略不當(dāng)引起死鎖發(fā)生進(jìn)程數(shù)>=2（互相等待）饑餓不一定是死鎖，但是至少一個(gè)進(jìn)程被無(wú)限期推遲。Chapter Three 內(nèi)存管理內(nèi)存是用于存放數(shù)據(jù)的硬件。程序執(zhí)行前需要先放到內(nèi)存中才能被CP

19、tt處理。內(nèi)存管理：更好地支持多道程序并發(fā)執(zhí)行，提升系統(tǒng)性能，通過虛擬技術(shù)從邏輯上擴(kuò)充內(nèi)存注：1字節(jié)=2字程序執(zhí)行過程：編譯、鏈接、裝入鏈接（鏈接時(shí)形成邏輯地址）：靜態(tài)鏈接：將各目標(biāo)模塊及庫(kù)函數(shù)連城一個(gè)完整可執(zhí)行程序，以后不再拆開裝入時(shí)動(dòng)態(tài)鏈接：邊裝入，邊鏈接（早期多道批處理）運(yùn)行時(shí)動(dòng)態(tài)鏈接：需要用到時(shí)才鏈接（現(xiàn)代操作系統(tǒng)）裝入：（將邏輯地址轉(zhuǎn)換為物理地址）絕對(duì)裝入：編譯時(shí)產(chǎn)生絕對(duì)地址。程序中邏輯地址與實(shí)際內(nèi)存地址完全相同；只適用于單 道程序環(huán)境可重定位裝入（靜態(tài)重定位）：地址變換通常在裝入時(shí)一次完成特點(diǎn)：一個(gè)作業(yè)進(jìn)入內(nèi)存，必須分配其要求的全部?jī)?nèi)存空間。在運(yùn)行期間就不能再移動(dòng)位置。沒有足夠內(nèi)存

20、時(shí)，不能裝入作業(yè)！ 裝入時(shí)把邏輯地址變換為物理地址，裝入后不能改變。動(dòng)態(tài)運(yùn)行時(shí)裝入：不立即轉(zhuǎn)換地址，真正要執(zhí)行時(shí)才進(jìn)行（需要重定位寄存器支持） 特點(diǎn)：動(dòng)態(tài)重定位在作業(yè)執(zhí)行過程中進(jìn)行。程序運(yùn)行前只裝入部分代碼即可運(yùn)行。運(yùn)行期間動(dòng)態(tài)申請(qǐng)分配內(nèi)存，便于程序段的共享。地址重定位（地址映射）邏輯地址（又稱相對(duì)/虛地址）>物理地址（內(nèi)存、絕對(duì)、實(shí)地址） 注：物理地址可以直接尋址；不能直接用邏輯地址在內(nèi)存中讀取信息！ 不同進(jìn)程可以有相同的邏輯地址，但是會(huì)映射倒不同的主存位置上。關(guān)系圖（略）P142重定位寄存器（用來(lái)”+”的，用來(lái)算物理地址）整個(gè)系統(tǒng)僅設(shè)置一個(gè)！ 界地址寄存器（用來(lái)”比”，判斷有無(wú)越界的

21、）覆蓋與交換解決空間不足的問題，但并非物理上擴(kuò)充，是從邏輯上擴(kuò)覆蓋：特點(diǎn)是打破了必須將一個(gè)進(jìn)程的全部信息裝入主存后才能運(yùn)行的限制。（對(duì)用戶不透明，已成歷史）內(nèi)存中能夠更新的地方只有覆蓋區(qū)的段，不在覆蓋區(qū)的段會(huì)常駐內(nèi)存。交換：把處于等待狀態(tài)（或在CPU調(diào)度原則下被剝奪運(yùn)行權(quán)利）的程序從內(nèi)存移到外存（對(duì) 應(yīng)進(jìn)程的中級(jí)調(diào)度），把內(nèi)存空間騰出來(lái)。注：交換技術(shù)主要在不同進(jìn)程（或作業(yè)）之間進(jìn)行，而覆蓋技術(shù)則用于同一進(jìn)程（或作業(yè)）。連續(xù)分配一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間單一連續(xù)分配：無(wú)需內(nèi)存保護(hù)（內(nèi)存中只有一道程序，肯定不會(huì)訪問越界干擾其他程 序）；實(shí)現(xiàn)簡(jiǎn)單；無(wú)外部碎片；可采用覆蓋技術(shù)注：換而言之，多進(jìn)

22、程要保證彼此互不干擾，OS需要通過內(nèi)存保護(hù)來(lái)實(shí)現(xiàn)。 缺點(diǎn)：只適用于單用戶、單任務(wù)的OS中；有內(nèi)部碎片；存儲(chǔ)器利用率低固定分區(qū)分配：最簡(jiǎn)單的一種多道程序存儲(chǔ)管理方式，有內(nèi)部碎片。動(dòng)態(tài)分區(qū)分配：在裝入時(shí)，根據(jù)進(jìn)程的大小動(dòng)態(tài)建立。產(chǎn)生外部碎片。 注：內(nèi)部碎片：分區(qū)大小固定，程序小于固定分區(qū)時(shí)也占用一個(gè)分區(qū)，內(nèi)部浪費(fèi)外部碎片：在所有分區(qū)外的存儲(chǔ)空間會(huì)變成越來(lái)越多的碎片（可以用拼接、緊湊技術(shù)解決， 需要?jiǎng)討B(tài)重定位寄存器支持）分配算法：首次適應(yīng)：空閑分區(qū)以地址遞增的次序鏈接，找大小滿足要求的第一個(gè)分區(qū)最佳適應(yīng)：XX按容量遞增XX最壞適應(yīng)：XX按容量遞減XX鄰近適應(yīng)：循環(huán)首次適應(yīng)算法，分配內(nèi)存時(shí)，從上次查找

23、結(jié)束的位置開始繼續(xù)查找。 注：首次適應(yīng)（First fit）是最簡(jiǎn)單，最好，最快的。最佳適應(yīng)（Best fit）性能通常很差，產(chǎn)生最多外部碎片。分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是：界地址保護(hù)編址空間大小取決于硬件的訪存能力非連續(xù)分配（離散）一個(gè)程序分散地裝入不相鄰的內(nèi)存分區(qū)分頁(yè)存儲(chǔ)：有內(nèi)部碎片；基地址變換由硬件自動(dòng)完成基地址變換機(jī)構(gòu) 有快表（高速緩沖寄存器）TLB 無(wú)快表頁(yè)表：由頁(yè)表項(xiàng)組成。頁(yè)表項(xiàng)：頁(yè)號(hào)P+物理內(nèi)存中的塊號(hào)邏輯地址結(jié)構(gòu)：頁(yè)號(hào)P+頁(yè)內(nèi)偏移頁(yè)表長(zhǎng)度：指的是這個(gè)頁(yè)表中總共有幾個(gè)頁(yè)表項(xiàng)，即總共幾個(gè)頁(yè)；頁(yè)表項(xiàng)長(zhǎng)度：每個(gè)頁(yè)表項(xiàng)占多大的存儲(chǔ)空間；頁(yè)面大?。阂粋€(gè)頁(yè)面占多大存儲(chǔ)空間。物理地址=

24、物理內(nèi)存中的塊號(hào)+頁(yè)內(nèi)偏移（理解：P148便利貼） 注：OS對(duì)內(nèi)存采用頁(yè)式存儲(chǔ)管理時(shí)，所劃分的頁(yè)面大小必須相同。若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要兩次訪問內(nèi)存。（若在快表中找到，則僅需一次）>涉及題型：快表命中率快表的有效性基于局部性原理。多級(jí)頁(yè)表：如N級(jí)頁(yè)表需訪問N+1次頁(yè)表管理中，地址空間是一維的；段式XX是二維的。分頁(yè)管理方式>主要方便操作系統(tǒng)。通過硬件機(jī)制實(shí)現(xiàn)，提高內(nèi)存的利用率，提升性能， 對(duì)用戶透明分段存儲(chǔ)：有外部碎片分段管理方式>考慮用戶和程序員。方便編程、信息保護(hù)和共享、利于動(dòng)態(tài)增長(zhǎng)和動(dòng)態(tài)鏈接地址空間要求段內(nèi)連續(xù)，段間不做要求。 注：內(nèi)存保護(hù)需

25、要由OS與硬件機(jī)構(gòu)合作完成段頁(yè)式管理方式：有內(nèi)部碎片。P154地址變換機(jī)構(gòu)用分段的方式來(lái)分配和管理用戶地址空間；用分頁(yè)的方式來(lái)管理物理存儲(chǔ)空間。 在進(jìn)行地址變換時(shí)，進(jìn)行一次訪問實(shí)際需要三次訪問主存。有快表則兩次。在一個(gè)進(jìn)程中，段表只有一個(gè)，而頁(yè)表可能有多個(gè)。虛擬內(nèi)存管理>從邏輯上擴(kuò)充內(nèi)存（只能基于非連續(xù)分配技術(shù)）屬于高速緩存技術(shù)，基于局部性原理。（即不必裝入全部程序）裝入時(shí)，只需裝一部分，其余留在外存就可以啟動(dòng)；執(zhí)行時(shí)，當(dāng)訪問的信息不在內(nèi)存，則用OS將其調(diào)入內(nèi)存，將暫時(shí)不用的換出至外存（內(nèi)<>外）局部性原理：時(shí)間局部性、空間局部性（理解）注：虛擬存儲(chǔ)器的大小由計(jì)算機(jī)的地址結(jié)構(gòu)

26、決定（CPU地址線數(shù)），并非簡(jiǎn)單的內(nèi)外存相加。容量與主存的實(shí)際大小沒直接關(guān)系，由主存和輔存（硬盤）的容量之和所確定。在虛存的頁(yè)表項(xiàng)中，合法位決定是否會(huì)發(fā)生缺頁(yè)故障。虛擬存儲(chǔ)器三大特征：多次性、對(duì)換性、虛擬性請(qǐng)求分頁(yè)管理方式：虛擬存儲(chǔ)器的實(shí)現(xiàn)，目前最常用 組成：頁(yè)表機(jī)制 地址變換機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)：頁(yè)面不在內(nèi)存時(shí)，產(chǎn)生一個(gè)缺頁(yè)中斷（屬于內(nèi)中斷），請(qǐng)求OS將所缺頁(yè) 調(diào)入（一條指令在執(zhí)行期間可產(chǎn)生多次缺頁(yè)中斷）注：頁(yè)式虛擬存儲(chǔ)管理的主要特點(diǎn)：不要求將作業(yè)同時(shí)全部裝入到主存的連續(xù)區(qū)域頁(yè)面置換算法：最佳置換算法OPT（向后看）先進(jìn)先出FIFO：基于隊(duì)列實(shí)現(xiàn)（會(huì)有Belady異常）最近最久未使用LRU（向前

27、看）特點(diǎn)：是堆棧類算法。性能較好，但需寄存器和棧的硬件支持。（需要對(duì)所有頁(yè)進(jìn)行排序）最近未用NRU（CLOCK）CLOCK置換：（改進(jìn)型淘汰次序，性能接近LRU） 先未被訪問（u=0），未被修改（m=0）；再未被訪問（u=0），已被修改（m=1）；然后（u=1，m=0）；最后（u=1，m=1）。注：LRU和OPT都不可能發(fā)生Belady異常影響缺頁(yè)次數(shù)的因素：分配給進(jìn)程的物理頁(yè)面數(shù)、頁(yè)面本身的大小、程序編程的方法、頁(yè)面 淘汰的算法頁(yè)面分配策略：固定分配局部置換（物理塊數(shù)一定）、可變分配局部置換、可變分配全局置 換（是最易于實(shí)現(xiàn)的物理塊分配和置換策略）駐留集：指請(qǐng)求分頁(yè)存儲(chǔ)管理中給進(jìn)程分配的物理

28、塊的集合。（太小會(huì)導(dǎo)致缺頁(yè)頻繁）二種調(diào)頁(yè)策略：預(yù)調(diào)頁(yè)：用于進(jìn)程首次調(diào)入時(shí)（運(yùn)行前調(diào)入）請(qǐng)求調(diào)頁(yè)：易于實(shí)現(xiàn)，虛存中大多采用此策略。缺點(diǎn)為每次只調(diào)入一頁(yè)（運(yùn)行時(shí)/期間調(diào)入）抖動(dòng)：剛換出的頁(yè)面馬上又要換入內(nèi)存，剛換入的頁(yè)面馬上又要換出內(nèi)存頻繁換入、換出使系統(tǒng)效率低下原因：淘汰算法不合理、物理頁(yè)面太少解決方案（提升系統(tǒng)性能、改進(jìn)CPU利用率）：增加內(nèi)存容量；撤銷部分進(jìn)程；換淘汰算法；減少多道程序的度數(shù)（所有增大交換區(qū)的選項(xiàng)都不要選?。┳ⅲ篎IFO最易發(fā)生抖動(dòng)，但所有頁(yè)面調(diào)度策略都不可能完全避免抖動(dòng)。Chapter Four 文件管理在用戶進(jìn)行輸入、輸入中，以文件為基本單位。在系統(tǒng)運(yùn)行時(shí)，計(jì)算機(jī)以進(jìn)程為

29、基本單位進(jìn)行資源的調(diào)度和分配。注：從系統(tǒng)角度看，文件系統(tǒng)負(fù)責(zé)對(duì)文件的存儲(chǔ)空間進(jìn)行組織、分配，負(fù)責(zé)文件的存儲(chǔ)并對(duì) 存入文件進(jìn)行保護(hù)、檢索。從用戶角度看，操作系統(tǒng)引入文件系統(tǒng)的目的是：實(shí)現(xiàn)對(duì)文件的按名存取。基本操作：創(chuàng)建文件、寫文件、讀文件、文件尋址、刪除、截?cái)鄤?chuàng)建文件步驟：在文件系統(tǒng)中為文件找到空間 在目錄中為新文件創(chuàng)建條目文件的打開：首次打開：系統(tǒng)調(diào)用open將指明文件的屬性從外存拷貝到內(nèi)存打開文件目錄表的一個(gè)表目中 非首次：open根據(jù)文件名搜索目錄（FCB調(diào)入內(nèi)存），并將目錄條目復(fù)制到打開文件表（包含所有打開文件信息的表）。用戶需要一個(gè)文件操作時(shí)，通過打開文件表的索引指定文件，省略了搜索。

30、文件的關(guān)閉：OS從打開文件表中刪除某一條目，回收分配給文件的內(nèi)存空間資源，釋放文件的文件控制塊（FCB）。文件控制塊（FCB）：存放控制文件所需的各種信息的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)”按名存取”。一個(gè)FCB就是一個(gè)文件目錄項(xiàng)，即本身就也被看成一個(gè)文件（相似進(jìn)程中的PCB）文件的邏輯結(jié)構(gòu)：是從用戶觀點(diǎn)出發(fā)看到的文件組織形式文件邏輯上都可以看作連續(xù)的，但在物理設(shè)備上并不完全連續(xù)。文件的物理結(jié)構(gòu)從實(shí)現(xiàn)出 發(fā)。無(wú)結(jié)構(gòu)文件（流式文件）：最簡(jiǎn)單的文件組織形式有結(jié)構(gòu)文件（記錄式文件）：順序文件：批量操作效率高；對(duì)單個(gè)（增刪改查）較困難索引文件：成百上千倍提高訪問速度 索引順序文件 直接文件和散列文件：沒有順序的特性。注

31、：索引表本身是定長(zhǎng)記錄的順序文件對(duì)于含有N個(gè)記錄的順序文件，查找某關(guān)鍵字值的記錄平均需要查找N/2次；在索引順序文件中，需要N次。索引文件&索引順序文件都提高了存取速度，但因?yàn)榕渲盟饕矶黾恿舜鎯?chǔ)空間。散列文件有很高的存取速度，但是會(huì)引起沖突。存放在磁盤上的索引結(jié)點(diǎn)稱為磁盤索引結(jié)點(diǎn)，UNIX中的每個(gè)文件都有一個(gè)唯一的磁盤索引 結(jié)點(diǎn)。目錄結(jié)構(gòu)>目錄管理要實(shí)現(xiàn)”按名存取”；目錄存取的效率直接影響系統(tǒng)性能單級(jí)目錄結(jié)構(gòu)：在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)特點(diǎn)：不便于文件共享；按名存??；文件不允許重名兩級(jí)目錄結(jié)構(gòu)：將文件目錄分成：主文件目錄和用戶文件目錄特點(diǎn)：解決文件

32、重名問題；可以在目錄上實(shí)現(xiàn)訪問限制；缺乏靈活性，不能分類多級(jí)目錄結(jié)構(gòu)（樹型）：方便分類，結(jié)構(gòu)清晰；但增加了磁盤訪問次數(shù)，影響查詢速度； 不便于實(shí)現(xiàn)文件的共享絕對(duì)路徑：從根目錄出發(fā)的路徑。相對(duì)路徑：進(jìn)程對(duì)各文件的訪問都是相對(duì)于當(dāng)前目錄進(jìn)行的。當(dāng)用戶要訪問某個(gè)文件時(shí)，使用相對(duì)路徑標(biāo)識(shí)文件。無(wú)環(huán)圖目錄結(jié)構(gòu)：方便實(shí)現(xiàn)了文件共享。注：僅當(dāng)共享計(jì)數(shù)器為0時(shí)才真正刪除結(jié)點(diǎn)，否則僅刪除請(qǐng)求用戶的共享鏈。（不可刪除非空目錄）文件共享：使多個(gè)進(jìn)程共享同一份文件，系統(tǒng)中只需保留該文件的一份副本基于索引結(jié)點(diǎn)的共享方式（硬鏈接） 索引結(jié)點(diǎn)中存放文件的物理地址和屬性文件目錄中只存放文件名和指向索引結(jié)點(diǎn)的指針鏈接計(jì)數(shù)cou

33、nt：用于表示鏈接到本索引文件上的用戶目錄項(xiàng)的個(gè)數(shù)。 當(dāng)用戶A創(chuàng)建一個(gè)新的文件時(shí)，count=1；B共享該文件時(shí)，count=2。若A不需要此文件，不能將其直接刪除，只能將count-1（此時(shí)B還能使用此文件）；只有當(dāng)count=0，表示沒有用戶使用時(shí)，系統(tǒng)將其負(fù)責(zé)刪除。（理解）利用符號(hào)鏈實(shí)現(xiàn)文件共享（軟連接，類似快捷方式）：刪除文件時(shí)，Link還在注：文件共享是”軟”+”硬”鏈接。硬鏈接就是多個(gè)指針指向一個(gè)索引結(jié)點(diǎn)，保證只要還有一 個(gè)指針指向索引結(jié)點(diǎn)，索引結(jié)點(diǎn)就不會(huì)被刪除；軟連接就是把到達(dá)共享文件的路徑記錄起 來(lái)，訪問時(shí)，根據(jù)路徑尋找文件。（硬鏈接的查找速度比較快）文件保護(hù)>口令保護(hù)、

34、加密保護(hù)、訪問控制訪問控制：為每個(gè)文件和目錄增加一個(gè)訪問控制列表（ACL） 特點(diǎn)：安全性較高；靈活性低；非系統(tǒng)實(shí)現(xiàn)加密保護(hù)：防止文件被竊??；編碼、解碼需要時(shí)間；并沒有控制用戶對(duì)文件的訪問類型特點(diǎn)：安全性較差；靈活性高；由系統(tǒng)實(shí)現(xiàn)注：對(duì)一個(gè)文件的訪問通常由用戶訪問權(quán)限和文件屬性共同控制。對(duì)多級(jí)目錄結(jié)構(gòu)的文件保護(hù)：不僅需保護(hù)單個(gè)文件，還需保護(hù)子目錄內(nèi)的文件，即需目錄保 護(hù)機(jī)制。系統(tǒng)級(jí)安全管理包括：注冊(cè)和登錄。文件系統(tǒng)實(shí)現(xiàn)文件系統(tǒng)的層次結(jié)構(gòu)：（當(dāng)用戶請(qǐng)求訪問某個(gè)文件時(shí)）用戶調(diào)用接口>文件目錄系統(tǒng)>存取控制驗(yàn)證層（FCB里看是否有訪問權(quán)限）>（真正尋址，得到邏輯地址）邏輯文件系統(tǒng)和文

35、件信息緩沖區(qū)>（邏址變換物址）物理文件系統(tǒng)文件實(shí)現(xiàn)研究文件的物理結(jié)構(gòu)文件的分配方式：連續(xù)分配：要求每個(gè)文件在磁盤上占有一組連續(xù)的塊特點(diǎn)：支持順序訪問和直接訪問；實(shí)現(xiàn)簡(jiǎn)單，存取速度快；文件長(zhǎng)度不宜動(dòng)態(tài)增加（類似于順序表）鏈接分配：采用離散分配的方式顯式：把用于鏈接文件各物理塊的指針從塊末尾提出，顯式地放入內(nèi)存的一張鏈表（文件分 配表FAT>該表在整個(gè)磁盤僅設(shè)一張）中。沒有碎片問題；外存利用率高；支持隨機(jī)訪問 隱式：無(wú)法直接訪問盤塊，只能通過指針順序訪問文件。方便拓展；沒有碎片問題；外存利用率高；只支持順序訪問，不支持隨機(jī)，查找效率低。索引分配：索引塊應(yīng)盡可能?。ㄋ饕?gt;一個(gè)文件

36、分配一張，要占一定空間） 注：m級(jí)索引訪問記錄需訪問磁盤m+1次對(duì)文件的存?。弘S機(jī)存取時(shí)，索引文件速度快；順序存取時(shí)，順序文件速度快。 在磁盤上，最容易導(dǎo)致存儲(chǔ)碎片發(fā)生的物理文件結(jié)構(gòu)是：順序存放。文件的存儲(chǔ)空間管理：實(shí)際上是對(duì)空閑塊的組織和管理空閑表法 空閑鏈表法 位示圖法（要推算出盤塊號(hào)與字號(hào)/位號(hào)相互轉(zhuǎn)換的公式：P230） 成組鏈接法磁盤扇區(qū)：是磁盤可尋址的最小存儲(chǔ)單位一次磁盤讀寫操作時(shí)間由尋道時(shí)間、延遲時(shí)間和傳輸時(shí)間決定。但實(shí)際上存取時(shí)間與磁盤調(diào)度算法密切相關(guān)。調(diào)度算法直接決定了尋道時(shí)間。DD算法：FSFS SSTF：會(huì)產(chǎn)生”饑餓”SCAN（電梯算法）：（只有到了最邊上的磁道才能改變磁頭

37、方向?。┮来蓬^當(dāng)前位置和磁頭移動(dòng)方向C-SCAN：只需要到達(dá)最遠(yuǎn)端的一個(gè)請(qǐng)求即可返回LOOK和C-LOOK：只要到請(qǐng)求磁道的最邊上。注：磁盤是共享設(shè)備，但在每一時(shí)刻，至多只能由一個(gè)作業(yè)啟動(dòng)它。 光盤、磁盤、U盤既可以順序訪問有可以隨機(jī)訪問。磁帶只能順序訪問。Chapter Five I/O管理I/O設(shè)備分類：（按）使用特性：人機(jī)交互、存儲(chǔ)、網(wǎng)絡(luò)通信（按）傳輸速率：低速（鍵盤鼠標(biāo)）、中（打印機(jī)）、高（磁盤光盤）（按）信息交換單位：塊設(shè)備、字符設(shè)備塊設(shè)備：以數(shù)據(jù)塊為單位存?。ù疟P）基本特征：傳輸速率較高；可尋址；可對(duì)他隨機(jī)讀/寫任一塊字符設(shè)備：用于數(shù)據(jù)輸入/輸出。以字符為單位傳輸；無(wú)結(jié)構(gòu)類型（

38、交互式終端機(jī)、打印 機(jī)）基本特征：傳輸速率低；不可尋址；在I/O時(shí)常采用中斷驅(qū)動(dòng)方式I/O控制方式：程序直接控制方式 中斷驅(qū)動(dòng)方式DMA方式：DMA方式是在I/O設(shè)備和主存之間建立一條直接數(shù)據(jù)通路。注：DMA交換方式：I/O設(shè)備與存儲(chǔ)設(shè)備進(jìn)行數(shù)據(jù)交換不經(jīng)過CPU來(lái)完成。（CPU只參與預(yù)處理和結(jié)束過程）通道控制方式：工作過程：向通道發(fā)一條I/O指令，給出通道程序的首地址和要訪問的I/O設(shè)備，通道接到指 令后，執(zhí)行通道程序便可完成CPU指定的任務(wù)，數(shù)據(jù)傳送結(jié)束向CPU發(fā)中斷請(qǐng)求。I/O通道：專門負(fù)責(zé)I/O的處理機(jī)，實(shí)現(xiàn)CPU、通道、I/O三者并行工作注：通道用于實(shí)現(xiàn)內(nèi)存與外設(shè)之間的信息傳輸。通道是一種特殊的處理器，屬于硬件技術(shù)。SPOOLing、緩沖池、內(nèi)存覆蓋都是在內(nèi)存基礎(chǔ)上通過軟件實(shí)現(xiàn)。字節(jié)路通道：用于連接大量低速、中速設(shè)備I/O通道與一般處理機(jī)的區(qū)別：通道指令類型單一；沒有自己的內(nèi)存，通道程序放在主機(jī)內(nèi) 存中，與CPU共享內(nèi)存I/O通道與DMA方式的區(qū)別：DMA：CPU控制傳輸?shù)臄?shù)據(jù)塊大小、傳輸?shù)膬?nèi)存位置；每個(gè)DMA控制器對(duì)應(yīng)一臺(tái)設(shè)備與內(nèi)存?zhèn)鬟f數(shù)據(jù)。通道：上述信息由通道控制，可控制多臺(tái)設(shè)備與內(nèi)存的數(shù)據(jù)交換。注：通道技術(shù)指的是一種硬件機(jī)制磁盤設(shè)備的I