基于《計算機操作系統(tǒng)》(第四版)總結(jié)：

OS引論、進程描述與控制、處理機調(diào)度與死鎖、存儲器管理、虛擬存儲器、輸入輸出系統(tǒng)、文件系統(tǒng)

1、目標(biāo)：方便性、有效性、可擴充性、開放性

2、作用：

　　1、作為用戶與計算機硬件系統(tǒng)之間的接口

　　2、作為計算機系統(tǒng)資源的管理者

　　3、實現(xiàn)對計算機資源的抽象

3、發(fā)展過程：

　　1、人工操作方式：用戶獨占全機，CPU等待人工操作--帶（卡）裝卸

　　2、脫機輸入/輸出方式：事先將裝有用戶程序和數(shù)據(jù)的紙帶裝入紙帶輸入機，外圍機控制，把紙帶內(nèi)容輸入到磁帶上（類似于磁盤），CPU需要時，從磁帶高速調(diào)入內(nèi)存。反之類同。

　　　　優(yōu)點：減少了CPU的空閑時間、提高了I/O速度

　　3、單道批處理：首先監(jiān)督程序?qū)⒋艓У谝粋€作業(yè)裝入內(nèi)存，運行控制權(quán)在該作業(yè)，處理完改作業(yè)后，控制權(quán)回到監(jiān)督程序，然后進行重復(fù)過程，系統(tǒng)自動對作業(yè)成批處理。（內(nèi)存始終只保持一道作業(yè)---單道批處理）

　　　　缺點：內(nèi)存浪費，不能充分利用系統(tǒng)資源

　　4、多道批處理：所提交的作業(yè)先存入外存，排成“后備隊列”，再由作業(yè)調(diào)度程序按算法從隊列調(diào)若干作業(yè)入內(nèi)存。

　　　　優(yōu)缺點：資源利用率高、系統(tǒng)吞吐量大、平均周轉(zhuǎn)時間長、無交互能力

　　5、分時系統(tǒng)：作業(yè)直接進入內(nèi)存，采用輪轉(zhuǎn)運行方式，系統(tǒng)配置一個多路卡（實現(xiàn)分時多路復(fù)用），及時接收用戶終端命令（數(shù)據(jù)）。

　　　　特征：多路性、獨立性、及時性、交互性

　　6、實時系統(tǒng)：系統(tǒng)能及時響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)的協(xié)調(diào)一致的運行。

　　　　特征：多路性（周期性信息采集，多個對象或執(zhí)行機構(gòu)進行控制）、獨立性、及時性、交互性、可靠性（多級容錯措施）

4、基本特征：

　　1、并發(fā)：引入進程，并行并發(fā)，系統(tǒng)程序獨立并發(fā)執(zhí)行，提高資源利用率，增加系統(tǒng)吞吐量。

　　2、共享：

　　　?、倩コ夤蚕恚欢螘r間內(nèi)只允許一個進程訪問資源（臨界資源）。

　　　?、谕瑫r共享，允許一段時間內(nèi)多進程“同時”訪問。

　　3、虛擬：提高通信信道的利用率--“虛擬”技術(shù)，通過“空分復(fù)用”或“時分復(fù)用”，將一條物理信道（實）變?yōu)槿舾蓷l邏輯信道（虛）。

　　　　空分復(fù)用：利用存儲器的空閑空間分區(qū)域存放和運行其他的多道程序

　　　　時分復(fù)用：利用處理機的空閑時間運行其他程序

　　4、異步：進程以不可預(yù)知的速度向前推進。

5、主要功能：

　　1、處理機管理功能：

　　　　①進程控制：創(chuàng)建和撤銷進程，分配資源、資源回收，控制進程運行過程中的狀態(tài)轉(zhuǎn)換。

　　　　②進程同步：多進程運行進行協(xié)調(diào)--進程互斥（臨界資源上鎖）、進程同步。

　　　?、圻M程通信：實現(xiàn)相互合作之間的進程的信息交換。

　　　　④調(diào)度：作業(yè)調(diào)度，進程調(diào)度。

　　2、存儲器管理功能：為多道程序的運行提供良好的環(huán)境，提高存儲器的利用率，方便用戶使用，并能從邏輯上擴充內(nèi)存。

　　　?、賰?nèi)存分配：靜態(tài)分配、動態(tài)分配。

　　　?、趦?nèi)存保護：各在其內(nèi)存空間內(nèi)運行（設(shè)兩界限寄存器），互不干擾。

　　　?、鄣刂酚成洌旱刂房臻g中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中與之對應(yīng)的物理地址。

　　　?、軆?nèi)存擴充：借助于虛擬存儲技術(shù)，邏輯上擴充內(nèi)存容量。

　　3、設(shè)備管理功能：完成用戶進程提出的I/O請求，為其分配所需I/O設(shè)備，完成指定I/O操作；提高CPU和I/O設(shè)備的利用率，提高I/O速度，方便用戶使用I/O設(shè)備。

　　　?、倬彌_管理

　　　?、谠O(shè)備分配

　　　?、墼O(shè)備處理：設(shè)備驅(qū)動程序，用于實現(xiàn)CPU和設(shè)備控制器之間的通信。

　　4、文件管理功能：對用戶文件和系統(tǒng)文件進行管理以方便用戶使用，并保證文件的安全性。

　　　?、傥募鎯臻g的管理：為文件分配合理外存空間，文件存儲空間的使用情況。

　　　　②目錄管理：為每個文件建立一個目錄項。

　　　　③文件的讀/寫管理和保護

　　5、操作系統(tǒng)與用戶之間的接口：用戶接口，程序接口

6、微內(nèi)核操作系統(tǒng)：

　?、賰?nèi)核足夠小

　　②基于客戶/服務(wù)器

　?、邸皺C制與策略分離”原理

　　④面向?qū)ο蠹夹g(shù)

二、進程的描述與控制

1、前趨圖：用于描述程序執(zhí)行先后順序 P1->P2，是指一個有向無循環(huán)圖。

　　程序的順序執(zhí)行：按照某種先后次序順序執(zhí)行，僅當(dāng)前一程序執(zhí)行完后，才運行后一段程序。

　　　　順序性、封閉性、可在現(xiàn)性

　　　　輸入操作I->計算操作C->打印操作P

　　程序的并發(fā)執(zhí)行：間斷性、失去封閉性、不可再現(xiàn)性

2、進程

　　1、定義：

　　　　程序的一次執(zhí)行，順序執(zhí)行時所發(fā)生的活動，是具有獨立功能的程序在一個數(shù)據(jù)集合上的運行過程，系統(tǒng)資源調(diào)配的獨立單位。

　　2、實體：

　　　　即進程，由程序段、相關(guān)的數(shù)據(jù)段和PCB組成，所謂創(chuàng)建和撤銷進程實際是對其中的PCB的創(chuàng)建和撤銷。（PCB：進程控制塊Process Control Block）

　　3、特征：

　　　?、賱討B(tài)性 ②并發(fā)性 ③獨立性 ④異步性

3、進程的三種基本狀態(tài)：就緒、執(zhí)行、阻塞狀態(tài)（阻塞原因：I/O請求、申請緩沖區(qū)失敗等）

　　1、進程狀態(tài)的轉(zhuǎn)換：

　　2、進程的掛起suspend：進程處于靜止?fàn)顟B(tài)，暫停執(zhí)行（執(zhí)行狀態(tài)下掛起），暫不接受調(diào)度（就緒狀態(tài)下掛起）。是基于系統(tǒng)和用戶的需求。

　　3、進程的激活active：先將進程從外存調(diào)入內(nèi)存，檢查進程現(xiàn)行狀態(tài)，靜止-->活動

4、進程控制塊PCB：

　　1、記錄系統(tǒng)所需，用于描述進程的當(dāng)前情況以及管理進程運行的全部信息，是操作系統(tǒng)中記錄型數(shù)據(jù)結(jié)構(gòu)。

　　2、作用：一個在多道程序環(huán)境下不能獨立運行的程序成為一個能獨立執(zhí)行的基本單位，一個能與其他進程并發(fā)執(zhí)行的進程。

　　3、三種組織方式：

　　　?、?a>線性方式：將系統(tǒng)中所有的PCB都組織在一張線性表中，查表

　　　?、阪溄臃绞剑喊丫哂邢嗤瑺顟B(tài)進程的PCB分別通過PCB中的鏈接字鏈接成一個隊列

　　　?、鬯饕绞剑焊鶕?jù)所有進程狀態(tài)的不同，建立索引表

5、并發(fā)進程間的相互制約關(guān)系：

　?、匍g接相互制約關(guān)系：進程間對類臨界資源的間接相互制約關(guān)系，為保證進程有序運行，此類資源必須由系統(tǒng)實施統(tǒng)一分配（即用戶使用前，應(yīng)先提出申請）。

　?、谥苯酉嗷ブ萍s關(guān)系：源于某些進程（隸屬于同一應(yīng)用程序）之間為完成同一項任務(wù)而相互合作（相互間喚醒激活--制約）。

6、臨界資源：

　　　　一次僅允許一個進程使用的資源（如打印機、磁帶機等），進程間互斥來實現(xiàn)對臨界資源的共享。

　　臨界區(qū)：每個進程中訪問臨界資源的那段代碼，進程互斥地進入自己的臨界區(qū)，對臨界資源訪問

　　　?、龠M程進入臨界區(qū)前，對臨界資源進行檢查是否正被訪問---進入?yún)^(qū)

　　　?、谌粑幢辉L問，進入臨界區(qū)對該資源訪問，并設(shè)置“正被訪問”的標(biāo)志---臨界區(qū)

　　　　③臨界區(qū)后面代碼，將臨界區(qū)“正被訪問”的標(biāo)志恢復(fù)為“未被訪問”的標(biāo)志---退出區(qū)

　　　?、艹M入?yún)^(qū)（entry）、臨界區(qū)（critical）、退出區(qū)（exit）代碼，其余代碼---剩余區(qū)

7、同步機制應(yīng)遵循的原則：

　　1、為實現(xiàn)進程互斥地進入自己的臨界區(qū)

　　2、空閑讓進、忙則等待、有限等待、讓權(quán)等待

8、信號量機制：解決進程同步問題（進程同步工具）

　?、僬托盘柫浚罕硎举Y源數(shù)目的整型量（S），僅原子操作wait（S）和signal（S）可訪問，執(zhí)行時不可中斷。（分別被稱為P、V操作）

　　②記錄型信號量：在代表資源數(shù)目的整型變量value基礎(chǔ)，增加一個進程鏈表指針list，用于鏈接所有等待進程。不存在“忙等”的進程同步機制。

　?、跘ND型信號量：將進程運行所需所有資源，一次性全部分配給進程，待進程使用完后再一起釋放。

　?、苄盘柫考篈ND型信號量基礎(chǔ)上，對進程所申請的所有資源以及每類資源不同的資源需求量，在一次P、V原語操作中完成申請或釋放。

9、管程

　　1、管程機制：

　　　?、俟蚕碣Y源的數(shù)據(jù)結(jié)構(gòu)

　　　　②對該共享數(shù)據(jù)結(jié)構(gòu)實施操作的一組過程所組成的資源管理程序，共同構(gòu)成的一個操作系統(tǒng)的資源管理模塊。

　　“一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)?！?/span>

　　2、管程的組成：

　　　?、俟艹痰拿Q

　　　?、诰植坑诠艹痰墓蚕頂?shù)據(jù)結(jié)構(gòu)說明

　　　?、蹖υ摂?shù)據(jù)結(jié)構(gòu)進行操作的一組過程

　　　　④對局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句

　　管程被請求和釋放資源的進程所調(diào)用。

10、經(jīng)典進程同步問題（使用信號量方法解決）

　　生產(chǎn)者-消費者問題

　　哲學(xué)家進餐問題

　　讀者-寫者問題

11、進程通信的類型：

　　①共享存儲器系統(tǒng)：相互通信的進程“共享數(shù)據(jù)結(jié)構(gòu)”或“共享存儲區(qū)”。

　　②管道通信系統(tǒng)：“管道”（pipe）是指用于連接一個讀進程和一個寫進程以實現(xiàn)彼此間通信的一個共享文件。借花獻佛-管道通信。

　?、巯鬟f系統(tǒng)：將通信上網(wǎng)數(shù)據(jù)封裝在消息中，通過一組通信命令在進程間傳遞消息，完成進程間的數(shù)據(jù)交換。直接通信方式和間接（郵箱）通信方式。

　?、芸蛻魴C-服務(wù)器系統(tǒng)：套接字、遠程過程調(diào)用、遠程方法調(diào)用。

12、線程：“輕級進程”，作為調(diào)度和分派的基本單位，是程序執(zhí)行流的最小單位。

進程與線程間的異同：

　?、僬{(diào)度性：線程是作為調(diào)度和分派的基本單位，進程只作為資源擁有的基本單位。

　?、诰€程上下文切換比進程上下文切換快得多。

　　③并發(fā)性：進程間可并發(fā)執(zhí)行，線程（無論在同一進程與否）間也可并發(fā)執(zhí)行。

　?、軗碛匈Y源：進程擁有系統(tǒng)資源，線程僅有一點必不可少、保證獨立運行的資源。多個線程可共享本進程所擁有的資源。

　?、莳毩⑿裕和贿M程中的不同線程之間的獨立比不同進程之間的獨立性低得多。

　　⑥系統(tǒng)消耗：進程的創(chuàng)建或撤銷的系統(tǒng)消耗“明顯大于”線程的創(chuàng)建或撤銷的系統(tǒng)消耗。

三、處理機調(diào)度與死鎖

1、處理機調(diào)度的層次：

　　①高級調(diào)度：（長程調(diào)度或作業(yè)調(diào)度），調(diào)度對象是作業(yè)，主要功能是根據(jù)算法決定將外存后備隊列中的某些作業(yè)調(diào)入內(nèi)存，創(chuàng)建進程、分配必要資源，并將入就緒隊列。

　?、诘图壵{(diào)度：（短程調(diào)度或進程調(diào)度），調(diào)度對象是進程，主要功能是根據(jù)算法決定內(nèi)存就緒隊列中的某個進程應(yīng)獲得處理機，并由分派程序給選中的進程分派處理機。

　　③中級調(diào)度：（內(nèi)存調(diào)度），內(nèi)存中暫不能運行的進程調(diào)至外存（掛起狀態(tài)），待條件齊全且內(nèi)存空閑，中級調(diào)度，就緒進程重回內(nèi)存（就緒狀態(tài)）入就緒隊列。

2、處理機調(diào)度算法的目標(biāo)：

　?、俟餐繕?biāo)：資源利用率、公平性、平衡性、策略強制執(zhí)行

　　②批處理系統(tǒng)的目標(biāo)：平均周轉(zhuǎn)時間、系統(tǒng)吞吐量高、處理機利用率高

　?、鄯謺r系統(tǒng)的目標(biāo)：響應(yīng)時間快、均衡性

　　④實時系統(tǒng)的目標(biāo)：截止時間的保證、可預(yù)測性

3、作業(yè)：通常的程序 數(shù)據(jù) 作業(yè)說明書。

　　1、作業(yè)控制塊：作業(yè)標(biāo)識 用戶名稱 用戶賬號 作業(yè)類型 作業(yè)狀態(tài) 調(diào)度信息 資源需求 資源使用情況 ……。管理和調(diào)度作業(yè)。

　　2、作業(yè)運行的三個階段（三種狀態(tài)）：收容階段（后備狀態(tài)）、運行階段（運行狀態(tài)）、完成階段（完成狀態(tài)）。

4、作業(yè)調(diào)度算法：

　?、傧葋硐确?wù)（FCFS）：先后次序進行調(diào)度（作業(yè)調(diào)度、進程調(diào)度）。

　?、诙套鳂I(yè)優(yōu)先（SJF）：作業(yè)（或進程）越短（估計運行時間短），優(yōu)先級越高。

　?、鄹唔憫?yīng)比優(yōu)先級調(diào)度算法：既考慮作業(yè)的等待時間，有考慮作業(yè)的運行時間，既照顧短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善處理機調(diào)度的性能。

　　　　R p優(yōu)先級=（等待時間 要求服務(wù)時間）/要求服務(wù)時間=響應(yīng)時間/要求服務(wù)時間

5、進程調(diào)度機制：

　　①任務(wù)：保存處理機的現(xiàn)場信息、按某種算法選取進程、把處理機分配給進程

　?、诨静糠郑号抨犉鳌⒎峙善?、上下文切換器

　?、圻M程調(diào)度方式：非搶占方式、搶占方式

6、輪轉(zhuǎn)調(diào)度算法原理：

　　根據(jù)FCFS，使用輪轉(zhuǎn)法處理，讓每一個就緒隊列上的進程每次運行一個時間片（若就緒隊列上有n個進程，每個進程每次大約獲得1/n的處理機時間）。

　　時間的片的確定：略大于一次典型交互所需時間。

7、多級反饋隊列調(diào)度算法：

　　①設(shè)置多個就緒隊列：每個隊列賦予不同的優(yōu)先級、不同大小的執(zhí)行時間片。

　?、诿總€隊列都采用FCFS算法

　?、郯搓犃袃?yōu)先級調(diào)度

8、最早截止時間優(yōu)先EDF（earliest deadline first）調(diào)度算法：根據(jù)任務(wù)的截止時間確定優(yōu)先級，截止時間愈早的優(yōu)先級愈高，具有最早截止時間的任務(wù)排隊列首，優(yōu)先分配處理機。

　　最低松弛度優(yōu)先LLF（least laxity first）調(diào)度算法：根據(jù)任務(wù)的緊急（松弛）程度，緊急程度愈高的優(yōu)先級愈高，優(yōu)先執(zhí)行處理。

9、死鎖

　　1、死鎖的定義：如果一組進程中的‘每一個進程’都在等待僅由該組進程中的‘其它進程’才能引發(fā)的‘事件’，那么該組進程是死鎖的（Deadlock）。

　　2、死鎖的必要條件（缺一不可）：

　　　　①互斥條件：進程分配到的資源互斥性使用，資源只能被一個進程占用，其他請求該資源的進程只能等到被用完釋放。

　　　　②請求和保持條件：進程已占有某資源，又提出新資源請求，而該資源被占，則進程請求被阻塞，已得資源保持。

　　　?、鄄豢蓳屨紬l件：進程已得資源不可被搶占。

　　　?、苎h(huán)等待條件：存在一個進程的資源循環(huán)鏈。

　　3、死鎖的處理方法：

　　　?、兕A(yù)防死鎖：設(shè)置限制條件，破壞死鎖四個必要條件。

　　　?、诒苊馑梨i：在資源的動態(tài)分配過程中，去防止系統(tǒng)進入不安全狀態(tài)。

　　　?、蹤z測死鎖：允許進程死鎖，但檢測機構(gòu)檢測死鎖發(fā)生，措施解決。

　　　?、芙獬梨i：撤銷某些進程，回收它們的資源分配給處于阻塞狀態(tài)的進程，使其能繼續(xù)運行。

10、預(yù)防死鎖的方法：破壞死鎖四個必要條件

　　互斥條件是非共享設(shè)備所必須的----主要破壞其他三條件

　?、倨茐摹罢埱蠛捅３帧睏l件：第一種協(xié)議，所有進程運行前申請過程所需的全部資源；第二種協(xié)議，允許一個進程獲得初期所需資源便開始運行，過程中逐步釋放分配給自己的且用畢的資源，再請求新的所需資源。

　?、谄茐摹安豢蓳屨肌睏l件：新的資源請求得不到滿足時，釋放已經(jīng)保持的所有資源，待需之時再申請。

　?、燮茐摹把h(huán)等待”條件：對系統(tǒng)所有資源類型進行線性排序，并賦予不同的序號。

11、安全序列：（P1，P2，……，P n）

　　安全狀態(tài)：系統(tǒng)能按某種進程推進順序（P1，P2，……，P n）為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順利的完成。

12、利用銀行家算法避免死鎖的方法

四、存儲器管理

1、存儲器的層次結(jié)構(gòu)：

　?、貱PU寄存器：寄存器

　?、谥鞔妫▋?nèi)存）：高速緩存、主存儲器、磁盤緩存

　?、圯o存：固定磁盤，可移動存儲介質(zhì)

　　可執(zhí)行存儲器：寄存器、主存（掉電信息丟失）---屬于操作系統(tǒng)存儲管理負責(zé)分配、回收，以及提供存儲層次間數(shù)據(jù)移動的管理機制。

2、用戶程序在系統(tǒng)中運行，先將其裝入內(nèi)存，在將其轉(zhuǎn)變位一個可執(zhí)行程序

　?、倬幾g：由編譯程序?qū)τ脩粼闯绦蚓幾g，形成若干個目標(biāo)模塊。

　?、阪溄樱河涉溄映绦?qū)⒁唤M目標(biāo)模塊及其所需庫函數(shù)鏈接，形成一個完整的裝入模塊。

　?、垩b入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。

　　1、程序的裝入（地址的變換）

　　　　①絕對裝入方式：（系統(tǒng)小，單道程序）編譯時知道程序?qū)Ⅰv留在內(nèi)存的位置，將產(chǎn)生絕對地址（即物理地址）的目標(biāo)代碼。絕對裝入程序按照已知地址將裝入模塊裝入內(nèi)存，不需對地址修改。

　　　?、诳芍囟ㄎ谎b入方式：裝入時，對目標(biāo)程序中指令和數(shù)據(jù)的各地址重定位（虛擬地址到內(nèi)存地址映射）。（靜態(tài)重定位）

　　　　③動態(tài)運行時的裝入方式：裝入程序?qū)⒀b入模塊裝入內(nèi)存后，不對裝入模塊進行地址變換（邏輯地址轉(zhuǎn)換為物理地址），而是推遲到程序真正要執(zhí)行時才進行。（動態(tài)地址重定位）

　　2、程序的鏈接

　　　　①靜態(tài)鏈接方式：程序運行前，先將各目標(biāo)模塊及其所需庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開。

　　　　②裝入時動態(tài)鏈接：邊裝入邊鏈接。

　　　　③運行時動態(tài)鏈接：對某些目標(biāo)模塊，在程序執(zhí)行中需要時，才對其進行鏈接。

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

　?、賳我贿B續(xù)分配：（單道程序環(huán)境下）將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅供OS使用，用戶區(qū)僅裝用戶程序（獨占）。

　?、诠潭ǚ謪^(qū)分配：（多道程序環(huán)境下）將整個用戶空間劃分為若干個固定大小的區(qū)域。被劃分幾個分區(qū)便允許幾個程序并發(fā)運行而不會互相干擾。

　　③動態(tài)分區(qū)分配：根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間。（數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表、空閑分區(qū)鏈；算法：順序式搜索算法；操作：分配內(nèi)存、回收內(nèi)存）

　?、軇討B(tài)可重定位分配：系統(tǒng)對內(nèi)存進行“緊湊”使若干程序移位，用該程序在內(nèi)存的新起始地址去置換原來的起始地址。（獲得新起始地址--動態(tài)重定位：系統(tǒng)中增設(shè)一個重定位寄存器存放程序和數(shù)據(jù)在內(nèi)存的起始地址，程序執(zhí)行時，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的）

　　碎片：因為內(nèi)存中出現(xiàn)不相鄰的小分區(qū)，而形成的不能被利用的小分區(qū)。

　　緊湊：通過移動內(nèi)存中作業(yè)的位置，把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法。

4、動態(tài)分配分區(qū)算法：基于順序搜索

　　依次搜索空閑分區(qū)鏈上的空閑分區(qū)，尋找一個其大小滿足要求的分區(qū)。

　?、偈状芜m應(yīng)（FF）算法：要求空間分區(qū)鏈以地址遞增的次序鏈接。分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至大小滿足要求，按照作業(yè)大小從該空閑分區(qū)劃分內(nèi)存空間給請求者，余下的留在空閑鏈中。

　?、谘h(huán)首次適應(yīng)（NF）算法：從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找。設(shè)置起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)，采用循環(huán)查找方式。

　?、圩罴堰m應(yīng)（BF）算法：要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。（容易形成許多難以利用的碎片）

　?、茏顗倪m應(yīng)（WF）算法：掃描整個空閑分區(qū)表或鏈表，挑選一個最大的空閑區(qū)，分割一部分存儲空間給作業(yè)使用。

5、離散存儲管理方式：

　　連續(xù)分配方式形成的許多“碎片”，不進行“緊湊”，利用離散的方式，將一個進程直接分散地裝入到許多不相鄰接的分區(qū)中。

　?、俜猪摚簩⒂脩舫绦虻牡刂房臻g分為若干個固定大小的區(qū)域（稱“頁”），相應(yīng)地，內(nèi)存空間也分為若干個物理塊（頁框），頁和塊的大小相同。離散分配。

　?、诜侄危簩⒂脩舫绦虻牡刂房臻g分為若干個大小不同的段，每段可定義一組相對完整的信息，以段為單位離散分配。

　?、鄱雾撌剑悍猪摵头侄蜗嘟Y(jié)合。（目前應(yīng)用較廣泛）

6、分頁存儲管理方式（含義）

　?、夙撁妫簩⑦M程的邏輯地址空間分成若干個頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。

　?、谖锢韷K：將內(nèi)存的物理地址空間分成若干個塊，并為各塊加以編號，從0開始，如0#塊、#1塊等。

　?、鄣刂方Y(jié)構(gòu)：前一部分為頁號P，后一部分為位（偏）移量W（頁內(nèi)陸址）。

　?、茼摫恚河涗浵鄳?yīng)頁在內(nèi)存中對應(yīng)的物理塊號，實現(xiàn)從頁號到物理塊號的地址映射。

7、進程在運行期間，需要對程序和數(shù)據(jù)的地址進行變換，即將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。

　　地址變換方式：設(shè)置地址變化機構(gòu)---利用頁面映射表（頁表），將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號，實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。

　　快表：在地址變換機構(gòu)中增設(shè)一個具有并行查尋能力的特殊高速緩沖寄存器。

8、分段系統(tǒng)的基本原理：

　　用戶程序的地址空間分段，分段地址中的地址結(jié)構(gòu)：段號-段內(nèi)陸址

　?、僭谙到y(tǒng)中設(shè)置段表寄存器，用于存放段表始址和段表長度。

　?、谶壿嫷刂分械亩翁朣與段表長度TL比較。

　?、廴鬝>TL，段號太大，訪問越界，產(chǎn)生越界中斷信號。

　　④若S<TL，未越界，根據(jù)段表始址和該段段號，計算出該段對應(yīng)段表項的位置，從中讀出該段在內(nèi)存的起始地址。

　　⑤檢查比較段內(nèi)陸址d和該段的段長SL。

　?、奕鬱>SL，發(fā)出越界中斷信號。

　?、呷鬱<SL，未越界，段基址 段內(nèi)陸址=要訪問的內(nèi)存物理地址。

9、分頁系統(tǒng)和分段系統(tǒng)的區(qū)別：

　?、夙撌切畔⒌奈锢韱挝唬猪撓到y(tǒng)是系統(tǒng)管理的需要，對用戶不可見。

       段是信息的邏輯單位，分段系統(tǒng)是為滿足用戶的需要。

　?、陧摰拇笮」潭ㄇ矣上到y(tǒng)決定。

  　　  段的長度不固定，決定于用戶所編寫的程序，根據(jù)信息的性質(zhì)劃分的。

　?、鄯猪摰挠脩舫绦虻刂房臻g是一維的。

　　   分段的用戶程序地址空間是二維的。（分段是用戶的行為，程序員標(biāo)示一個地址時，既需給出段名，也需給出段內(nèi)陸址。）

10、段頁式存儲管理的基本思想：

　　分頁系統(tǒng)能有效地提高內(nèi)存的利用率；分段系統(tǒng)能反映程序的邏輯結(jié)構(gòu)，便于段的共享與保護。將分頁與分段兩種存儲方式結(jié)合，形成段頁式存儲管理方式。
　　段頁式存儲管理系統(tǒng)，作業(yè)的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然后再將每段分成若干個大小相等的頁。對于內(nèi)存空間也分成大小相等的頁，內(nèi)存的分配以頁為單位。

五、虛擬存儲器

1、程序運行時的局部性原理：一較短時間內(nèi)，程序執(zhí)行僅局限于某個部分，所訪問的存儲空間也僅局限于某個區(qū)域。

　?、贂r間局限性：程序中存在大量的循環(huán)操作。

　?、诳臻g局限性：程序的順序執(zhí)行，導(dǎo)致訪問區(qū)域局限。

2、虛擬存儲器

　　1、定義：具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。（邏輯容量由內(nèi)存容量和外存容量之和決定，運行速度接近于內(nèi)存速度。）

　　2、特征：

　　　?、俣啻涡裕鹤鳂I(yè)無須一次性地全部裝入內(nèi)存運行，允許被分多次調(diào)入內(nèi)存運行，即只需將當(dāng)前要運行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可開始運行。（基礎(chǔ)：離散分配存儲管理方式）

　　　?、趯Q性：作業(yè)運行時程序和數(shù)據(jù)無須一直常駐內(nèi)存，允許作業(yè)運行時進行換進、換出，即進程運行期間允許那些暫不使用的代碼數(shù)據(jù)從內(nèi)存調(diào)至外存的對換區(qū)（換出），待需要時再將其調(diào)回至內(nèi)存（換進）。有效提高內(nèi)存利用率。

　　　?、厶摂M性：能夠從邏輯上擴充內(nèi)存容量，虛擬內(nèi)存容量（實際內(nèi)存容量?。瑢崿F(xiàn)小內(nèi)存運行大作業(yè)，改善內(nèi)存利用率，提高并發(fā)程度，增加系統(tǒng)吞吐量。

　　虛擬存儲器的實現(xiàn)：請求分頁系統(tǒng)or請求分段系統(tǒng)

3、請求分頁系統(tǒng)：硬件支持、實現(xiàn)請求分頁的軟件

　　硬件支持：

　　　?、僬埱箜摫頇C制：請求頁表增加四個字段作為請求分頁的數(shù)據(jù)結(jié)構(gòu)。（請求分頁系統(tǒng)中頁表諸項：頁號 物理塊號 狀態(tài)位P 訪問字段A 修改位M 外存地址）

　　　　②缺頁中斷機構(gòu)：每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時，產(chǎn)生缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存。

　　　?、鄣刂纷儞Q機構(gòu)：分頁系統(tǒng)地址變換機構(gòu)基礎(chǔ)上為實現(xiàn)虛擬存儲器，增加功能（如產(chǎn)生和處理缺頁中斷、從內(nèi)存換出一頁……）。

4、頁面調(diào)入策略：

　　1、何時調(diào)入：預(yù)調(diào)頁策略（一次調(diào)入若干相鄰頁）、請求調(diào)頁策略（需要時提出請求）

　　2、從何處（外存）調(diào)入：對換區(qū)（存放對換頁面）、文件區(qū)（存放文件--未運行過的頁面）、UNIX方式（該系統(tǒng)允許頁面共享--進程請求頁面可能被其他進程調(diào)入內(nèi)存，直接共享）

　　3、調(diào)入過程：

　　　每當(dāng)程序所要訪問的頁面未在內(nèi)存（存在位為“0”）

　　　?、傧駽PU發(fā)缺頁中斷

　　　?、谥袛嗵幚沓绦虮Ａ鬋PU環(huán)境去分析中斷原因

　　　?、坜D(zhuǎn)入缺頁中斷處理程序

　　　　④通過查找頁表得到該頁所在外存物理塊

　　　?、萑魞?nèi)存未滿，啟動磁盤I/O，調(diào)該缺頁入內(nèi)存，修改頁表

　　　?、奕魞?nèi)存已滿，置換算法將內(nèi)存中一頁換出，調(diào)該缺頁入內(nèi)存，修改頁表

　　　置該頁面存在位為“1”，頁表項寫入快表。

　　4、缺頁率：進程運行過程中，訪問頁面成功的次數(shù)S，訪問頁面失敗的次數(shù)F

　　　　缺頁率f=F/（S F）

5、頁面置換算法：

　?、僮罴阎脫Q：淘汰的頁面是以后永不使用的或在未來很長時間里不再被訪問的。（保證獲得最低的缺頁率，但目前無法預(yù)知未來，難以實現(xiàn)，作為標(biāo)準(zhǔn)用來評價其他算法）

　?、谙冗M先出：淘汰在內(nèi)存中駐留時間最久的頁面。（性能較差）

　?、圩罱罹梦词褂茫焊鶕?jù)頁面調(diào)入內(nèi)存后的使用情況，記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，淘汰現(xiàn)有頁面中t值大的。

　　④Clock算法：循環(huán)地檢查各頁面的應(yīng)用情況，最近未用算法。

　　⑤頁面緩沖算法：采用可變分配和局部置換方式的內(nèi)存分配策略，系統(tǒng)為每個進程分配一定數(shù)目的物理塊的同時自己保留一部分空閑物理塊。在內(nèi)存中設(shè)置一個空閑物理塊鏈表（用于分配給頻繁發(fā)生缺頁的進程）、設(shè)置一個修改頁面鏈表（已修改的頁面不立即換出至外存，而是將其所在物理塊掛在修改頁面鏈表的末尾）

6、“抖動”的含義：進程的大部分時間用于頁面的換進/換出，幾乎無法去做任何有效的工作。

　　原因：系統(tǒng)運行的進程過多，分配給每個進程的物理塊少，不能滿足進程正常運行的基本要求，運行過程中，頻繁缺頁。

六、輸入輸出系統(tǒng)

1、I/O系統(tǒng)的基本功能：

　?、匐[藏物理設(shè)備的細節(jié)：對設(shè)備加以適當(dāng)?shù)某橄?，以隱藏掉物理設(shè)備的實現(xiàn)細節(jié)。

　?、谂c設(shè)備的無關(guān)性：對設(shè)備抽象化使用。

　?、厶岣咛幚頇C和I/O設(shè)備的利用率：盡可能地讓處理機和I/O設(shè)備并行操作。

　　④對I/O設(shè)備進行控制：驅(qū)動程序的功能。（控制方式：輪詢的可編程I/O方式、中斷的可編程I/O方式、直接存儲器訪問方式、I/O通道方式）

　?、荽_保對設(shè)備的正確共享：獨占設(shè)備（打印機、磁帶機）、共享設(shè)備（磁盤）

　　⑥錯誤處理：臨時性錯誤，重試操作；持久性錯誤，向上層報告。

2、I/O系統(tǒng)的層次結(jié)構(gòu)：

　?、儆脩魧覫/O軟件：用于實現(xiàn)用戶與I/O設(shè)備交互。

　?、谠O(shè)備獨立性軟件：用于實現(xiàn)用戶程序與設(shè)備驅(qū)動器的統(tǒng)一接口、設(shè)備命令、設(shè)備保護、以及設(shè)備分配與釋放等。（設(shè)備無關(guān)的I/O軟件）

　?、墼O(shè)備驅(qū)動程序：與硬件直接相關(guān)，用來具體實現(xiàn)系統(tǒng)對設(shè)備發(fā)出的操作指令，驅(qū)動I/O設(shè)備工作。

　?、苤袛嗵幚沓绦颍河糜诒Ｗo被中斷進程的CPU環(huán)境，轉(zhuǎn)入相應(yīng)的中斷處理程序進行處理，處理完后恢復(fù)現(xiàn)場，并返回到被中斷的進程。

　?、萦布篒/O設(shè)備。

3、設(shè)備控制器的基本功能：

　?、俳邮蘸妥R別命令：相應(yīng)的控制寄存器，存放接收的命令和參數(shù)，進行譯碼。

　?、跀?shù)據(jù)交換：CPU與控制器之間、控制器與I/O設(shè)備之間，數(shù)據(jù)交換。

　　③標(biāo)識和報告設(shè)備的狀態(tài)：控制器記錄設(shè)備的狀態(tài)供CPU了解。

　?、艿刂纷R別：控制器中配置地址譯碼器，識別其所控制的設(shè)備的地址。

　　⑤數(shù)據(jù)緩沖區(qū)：主機速率高，I/O設(shè)備速率低，暫存數(shù)據(jù)匹配速率再進行數(shù)據(jù)傳送。

　?、薏铄e控制：I/O設(shè)備傳來的數(shù)據(jù)，設(shè)備控制器進行差錯檢測，若錯，將差錯檢測碼置位，并向CPU報告，CPU處理，數(shù)據(jù)作廢，重新傳送。

4、I/O通道：特殊處理機，處于CPU和設(shè)備控制器之間，具有執(zhí)行I/O指令的能力，并通過執(zhí)行通道程序來控制I/O操作。（指令類型單一、與CPU共享內(nèi)存）

　　通道類型：

　　　?、僮止?jié)多路通道：按字節(jié)交叉方式工作的通道。

　　　?、跀?shù)組選擇通道：按數(shù)組方式進行數(shù)據(jù)傳送的數(shù)組選擇通道，可連高速設(shè)備。（易出現(xiàn)獨占通道現(xiàn)象，利用率低）

　　　?、蹟?shù)組多路通道：字節(jié)多路通道和數(shù)組選擇通道相結(jié)合，按數(shù)組方式進行。

5、中斷：I/O設(shè)備向CPU發(fā)來中斷信號，CPU暫停正執(zhí)行的程序，保護現(xiàn)場，轉(zhuǎn)而執(zhí)行該I/O設(shè)備的中斷處理程序，執(zhí)行完后，返回斷點，繼續(xù)執(zhí)行原程序。（外中斷）

　　中斷向量表：存放中斷處理程序的入口地址于中斷向量表中的表項中。每種設(shè)備配以相應(yīng)的中斷處理程序，一個設(shè)備的中斷請求規(guī)定一個中斷號，一個中斷號直接對應(yīng)中斷向量表中的一個表項。（I/O設(shè)備發(fā)中斷請求信號，中斷控制器確定中斷號，查找中斷向量表，取其中斷處理程序的入口地址，轉(zhuǎn)入執(zhí)行該程序）

6、中斷處理程序：

　?、贉y定是否有未響應(yīng)的中斷信號

　?、诒Ｗo被中斷進程的CPU環(huán)境

　?、坜D(zhuǎn)入相應(yīng)的設(shè)備處理程序

　?、苤袛嗵幚?/span>

　　⑤恢復(fù)CPU的現(xiàn)場并退出中斷

7、設(shè)備驅(qū)動程序：I/O系統(tǒng)的高層與設(shè)備控制器之間的通信程序。

　?、俳邮哲浖l(fā)來的命令和參數(shù)，將其中的抽象要求轉(zhuǎn)換為與設(shè)備相關(guān)的低層操作系列。

　?、跈z查用戶I/O請求的合法性，了解I/O設(shè)備工作狀態(tài)，傳遞與I/O設(shè)備操作有關(guān)的參數(shù)，設(shè)置設(shè)備的工作方式。

　?、郯l(fā)出I/O命令，若設(shè)備空閑，啟動I/O設(shè)備，完成指定操作；若設(shè)備忙碌，將請求塊掛在設(shè)備隊列上等待。

　?、芗皶r響應(yīng)設(shè)備控制器發(fā)來的中斷請求，根據(jù)其中斷類型，調(diào)用相應(yīng)的中斷處理程序進行處理。

8、對I/O設(shè)備的控制方式：

　　①使用輪詢的可編程I/O方式：不斷循環(huán)測試狀態(tài)寄存器中的忙/閑標(biāo)志busy。

　?、谑褂弥袛嗟目删幊蘄/O方式：CPU中斷處理，I/O設(shè)備可與CPU并行工作。

　?、壑苯哟鎯ζ髟L問方式：利用DMA控制器的直接存儲器訪問方式。

　?、躀/O通道控制方式：DMA方式的發(fā)展，進一步減少CPU的干預(yù)，實現(xiàn)CPU、通道、I/O設(shè)備三者的并行操作。

9、設(shè)備無關(guān)軟件：應(yīng)用程序中所用的設(shè)備，不局限于使用某個具體的物理設(shè)備。

　?、僭O(shè)備驅(qū)動程序的統(tǒng)一接口

　?、诰彌_

　　③錯誤報告

　?、芊峙渑c釋放專用設(shè)備

　?、萏峁┡c設(shè)備無關(guān)的塊大小

10、Spooling技術(shù)--假脫機技術(shù)

　　利用一道程序模擬脫機輸入時的外圍控制機功能，把低速I/O設(shè)備的數(shù)據(jù)傳送到高速磁盤上（脫機輸入），再利用另一道程序脫機輸出時的外圍控制機功能，把高速磁盤的數(shù)據(jù)傳送到低速輸出設(shè)備上（脫機輸出）。

　　在聯(lián)機情況（主機直接控制脫機輸入、輸出）下實現(xiàn)的同時外圍操作的技術(shù)。

　　特點：

　　　?、偬岣逫/O的速度。

　　　　②將獨占設(shè)備改造為共享設(shè)備。

　　　?、蹖崿F(xiàn)虛擬設(shè)備功能。

11、緩沖區(qū)：暫存儲區(qū)域，I/O設(shè)備與處理機交換數(shù)據(jù)的場所。

　　類型：

　　　?、賳尉彌_區(qū)：每當(dāng)用戶進程發(fā)出一I/O請求時，OS在內(nèi)存中為其分配一緩沖區(qū)。

　　　?、陔p緩沖區(qū)：生產(chǎn)者緩沖區(qū)、消費者緩沖區(qū)。

七、文件系統(tǒng)

1、文件系統(tǒng)：OS存儲和管理文件信息，方便用戶對文件的存取、共享和保護等，有效提高系統(tǒng)資源的利用率。

2、文件的類型：

　　1、按用途分類：

　　　　①系統(tǒng)文件：系統(tǒng)軟件

　　　?、谟脩粑募河脩舻奈募?/span>

　　　　③庫文件：標(biāo)準(zhǔn)子例程及常用的例程

　　2、按文件中數(shù)據(jù)的形式分類：

　　　?、僭次募涸闯绦蚝蛿?shù)據(jù)

　　　?、谀繕?biāo)文件：源程序經(jīng)過編譯，尚未鏈接的目標(biāo)代碼“.obj”

　　　?、劭蓤?zhí)行文件：目標(biāo)代碼經(jīng)過鏈接后的文件“.exe”

　　3、按存取控制屬性分類：

　　　?、僦粓?zhí)行文件

　　　?、谥蛔x文件

　　　　③讀寫文件

　　4、按組織形式和處理方式分類：

　　　　①普通文件：由ASCII碼或二進制碼組成的字符文件

　　　?、谀夸浳募河晌募夸浗M成的文件（檢索執(zhí)行下屬文件）

　　　?、厶厥馕募合到y(tǒng)中的各類I/O設(shè)備

3、文件系統(tǒng)的層次結(jié)構(gòu)：文件系統(tǒng)接口>對對象進行操縱和管理的軟件集合>對象及其屬性

　　①文件系統(tǒng)接口：命令接口、程序接口

　　②對對象進行操縱和管理的軟件集合：（核心）層次組織結(jié)構(gòu)

　?、蹖ο蠹捌鋵傩裕何募⒛夸?、磁盤存儲空間

4、文件操作：

　?、僮罨镜奈募僮鳎簞?chuàng)建、刪除、讀、寫文件，設(shè)置文件的讀/寫位置

　?、谖募摹按蜷_”和“關(guān)閉”操作：用戶和文件的連接建立和斷開

　?、墼试S用戶直接設(shè)置和獲得文件的屬性，文件共享

5、文件的組織方式：

　?、夙樞蛭募阂幌盗杏涗洶错樞蜻M行存取操作，文件信息隊列排列。

　?、谒饕募航?yīng)關(guān)系的索引表，與主文件構(gòu)成索引文件。

　?、鬯饕樞颍簽槊恳粋€文件建立一張索引表，為一組記錄中的第一個記錄建立一個索引表項。

6、文件結(jié)構(gòu)

　　1、文件目錄：數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，供檢索時使用。

　　2、文件控制塊FCB：基本信息、存取控制信息、使用信息。

　　3、索引節(jié)點：每一個索引節(jié)點保存文件系統(tǒng)中的一個文件系統(tǒng)對象的元信息數(shù)據(jù)，但不包括數(shù)據(jù)內(nèi)容或者文件名。

7、目錄分類：

　　1、簡單目錄：單級文件目錄，在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項---按名存?。夸涰棧何募⑽募U展名、文件長度、文件類型、文件物理地址、文件說明、狀態(tài)位）

　　2、兩級目錄：主文件目錄（一級，用戶名、指向子目錄指針），用戶文件目錄（二級，文件控制塊）。

　　3、樹形目錄：樹形結(jié)構(gòu)目錄，主目錄被稱為‘根目錄’（唯一），每個文件和每個目錄只能有一個父目錄，子目錄被稱為‘樹節(jié)點’，數(shù)據(jù)文件被稱為‘樹葉’。

8、路徑名：從主目錄開始，把全部目錄文件名與數(shù)據(jù)文件名依次用“/”連接起來，構(gòu)成數(shù)據(jù)文件唯一的路徑名。

　　1、當(dāng)前目錄：當(dāng)前訪問工作的目錄。

　　2、相對路徑名：從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名。

　　3、絕對路徑名：從根目錄開始的路徑名。

9、文件共享方式：

　?、儆邢驘o循環(huán)圖：允許每個文件都可以有多個父目錄。

　?、谒饕?jié)點：文件的物理地址及其他的文件屬性等信息放在索引節(jié)點中，文件目錄中只設(shè)置文件名及指向相應(yīng)索引節(jié)點的指針。

　?、鄯栨溄樱烘溄痈改夸洝?/span>

10、影響文件安全的因素：人為、系統(tǒng)、自然

　　確保文件系統(tǒng)的安全性：存取控制機制、系統(tǒng)容錯機制、建立后備系統(tǒng)