操作系統(tǒng)復(fù)習(xí)all(共9頁)

1、南理工紫金學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)2班操作系統(tǒng)復(fù)習(xí)資料（lm）第 頁操作系統(tǒng)(co zu x tn)復(fù)習(xí)第一章考點(diǎn)(ko din)：操作系統(tǒng)的定義，基本特性以及主要(zhyo)功能（選擇、填空）定義：操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合理地對(duì)各類作業(yè)進(jìn)行調(diào)度、以及方便用戶使用的程序集合?；咎匦裕翰l(fā)性（最重要特征）、共享性、虛擬性、異步性所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程(線程)共同使用。資源屬性的不同，對(duì)資源共享的方式也不同。實(shí)現(xiàn)資源共享的兩種方式：(1)互斥共享方式(2)同時(shí)訪問方式主要功能：處理器管理、存儲(chǔ)器管理、設(shè)備管理、文件管理、用戶之間的接口第二章考點(diǎn)：

2、進(jìn)程、程序、線程的概念（簡(jiǎn)答）；PCB結(jié)構(gòu)、進(jìn)程狀態(tài)（三種基本狀態(tài)）；進(jìn)程同步和互斥的含義（選擇，填空）；臨界資源、臨界區(qū)、以及同步機(jī)制原則；信號(hào)量P或V操作時(shí)的信號(hào)量值的變化；經(jīng)典進(jìn)程同步問題（綜合題）進(jìn)程的定義：進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程(程序在并發(fā)環(huán)境中的執(zhí)行過程)，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。進(jìn)程的特征動(dòng)態(tài)性 并發(fā)性 獨(dú)立性異步性 進(jìn)程結(jié)構(gòu) PCB進(jìn)程控制塊-動(dòng)態(tài)特征的集中反映程序段-描述要完成的功能數(shù)據(jù)段-操作對(duì)象及工作區(qū)程序的定義：是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語言編寫的命令序列的集合。線程的定義：它是一個(gè)基本的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單元，由線程ID、

3、程序計(jì)數(shù)器、寄存器集合和堆棧組成。線程是進(jìn)程中的一個(gè)實(shí)體，一個(gè)進(jìn)程中包含(bohn)多個(gè)線程，他們可以利用進(jìn)程所擁有的資源，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。PCB（進(jìn)程控制塊）結(jié)構(gòu)：為了描述和控制進(jìn)程的運(yùn)行(ynxng)，系統(tǒng)為每個(gè)進(jìn)程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)-進(jìn)程控制塊，它是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。在進(jìn)程控制(kngzh)塊中，主要包含四方面信息：進(jìn)程標(biāo)識(shí)符、處理機(jī)狀態(tài)、進(jìn)程調(diào)度信息、進(jìn)程控制信息。進(jìn)程三種基本狀態(tài)：就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)就緒-執(zhí)行 執(zhí)行-阻塞 阻塞-就緒 執(zhí)行-就緒進(jìn)程的同步：進(jìn)程間共同完成一項(xiàng)任務(wù)時(shí)直接發(fā)生相互作用的關(guān)系。同步進(jìn)程間具有合作

4、關(guān)系；在執(zhí)行時(shí)間上必須按照一定的順序協(xié)調(diào)進(jìn)行；進(jìn)程的互斥：并發(fā)執(zhí)行的多個(gè)進(jìn)程由于競(jìng)爭(zhēng)同一資源而產(chǎn)生的相互排斥的關(guān)系。進(jìn)程間相互合作的關(guān)系是同步關(guān)系，而對(duì)資源爭(zhēng)用的關(guān)系是互斥關(guān)系。若干進(jìn)程使用同一臨界資源時(shí)必須互斥執(zhí)行。臨界資源：一次僅允許一個(gè)進(jìn)程使用的共享資源如：打印機(jī)、磁帶機(jī)、表格臨界區(qū)：在每個(gè)進(jìn)程中訪問臨界資源的那段程序;進(jìn)程必須互斥進(jìn)入臨界區(qū)；同步機(jī)制原則:空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待信號(hào)量P操作（wait）、V操作（signal）時(shí)時(shí)的信號(hào)量值的變化：Wait操作：申請(qǐng)一個(gè)單位資源procedure wait(S) var S:semaphore;/*定義記錄型信號(hào)量*/ b

5、egin S.value:=S.value-1; /*如果資源不足則阻塞該進(jìn)程*/ if S.value0 then block(S.L); endSignal操作：釋放一個(gè)單位資源procedure Signal(S) var S:semaphore;/*定義記錄型信號(hào)量*/ begin S.value:=S.value+1; /*如果(rgu)阻塞隊(duì)列中有進(jìn)程，則喚醒該進(jìn)程*/ if S.value0 then wakeup(S.L); endS.value 0時(shí)，代表系統(tǒng)中可用資源(zyun)的數(shù)目；S.values2 S2 b=a+3;A=0(信號(hào)量)P1 p2S1; P(A);V(A

6、); S2;第三章考點(diǎn)：作業(yè)經(jīng)歷的三級(jí)調(diào)度各種調(diào)度算法基本思想，計(jì)算周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間死鎖概念、產(chǎn)生原因以及死鎖的必要條件，死鎖的預(yù)防、避免處理方法（簡(jiǎn)答，填空）銀行家算法（作業(yè)）處理機(jī)調(diào)度的層次（三級(jí)調(diào)度）：高級(jí)調(diào)度（創(chuàng)建）、低級(jí)調(diào)度（找進(jìn)程執(zhí)行）、中級(jí)調(diào)度（激活掛起）短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法基本思想：從后備隊(duì)列中選擇一個(gè)或多個(gè)若干運(yùn)行時(shí)間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行。高優(yōu)先權(quán)優(yōu)先調(diào)度算法基本思想：從后備隊(duì)列中選擇優(yōu)先級(jí)高的的作業(yè)調(diào)入內(nèi)存運(yùn)行。4.死鎖的概念：多個(gè)進(jìn)程在運(yùn)行過程中因競(jìng)爭(zhēng)資源而造成的一種僵局。 各并發(fā)進(jìn)程彼此等待對(duì)方擁有的資源，且在得到對(duì)方資源前不釋放自己的資源。死鎖產(chǎn)生原因：

7、競(jìng)爭(zhēng)資源。 資源（打印機(jī)、公用隊(duì)列）數(shù)目不能滿足進(jìn)程的需要； 進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源(zyun)的順序不當(dāng)，也同樣會(huì)導(dǎo)致進(jìn)程死鎖。競(jìng)爭(zhēng)資源引起(ynq)死鎖：可剝奪和非可剝奪性資源 競(jìng)爭(zhēng)(jngzhng)非可剝奪性資源 競(jìng)爭(zhēng)臨時(shí)性資源產(chǎn)生死鎖的必要條件：(1) 互斥條件 (2) 請(qǐng)求和保持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件 7.處理死鎖的基本方法(1) 預(yù)防死鎖。-摒棄“請(qǐng)求和保護(hù)”條件互斥條件（ 錯(cuò) ）請(qǐng)求和保持條件（ 對(duì) ）不剝奪條件（ 對(duì) ）環(huán)路等待條件（ 對(duì) ）預(yù)防死鎖的方法 1.摒棄“請(qǐng)求和保持”條件 解決方案（and型信號(hào)量）AND型信號(hào)量

8、基本思想：將進(jìn)程在整個(gè)運(yùn)行中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后一起釋放。 2.摒棄“不剝奪”條件 解決方案（強(qiáng)制回收） 3.摒棄“環(huán)路等待”條件 解決方案（資源按序分配策略）(2) 避免死鎖。-銀行家算法 (3) 檢測(cè)死鎖。 (4) 解除死鎖。-剝奪資源死鎖的解除常采用的兩種方法：剝奪資源（基本方法）撤銷進(jìn)程系統(tǒng)不發(fā)生死鎖，滿足不等式：n(k-1)+1m（n是進(jìn)程個(gè)數(shù)，k是進(jìn)程所需最大資源數(shù)，m是系統(tǒng)提供資源數(shù)）8.銀行家算法(1)可利用資源向量Available；(2) 最大需求矩陣Max；(3) 分配矩陣Allocation；(4) 需求(xqi)矩陣Need；Needi

9、,j=Maxi,j-Allocationi,j 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示(biosh)進(jìn)程Pi需要K個(gè)Rj類型的資源。Pi發(fā)出資源請(qǐng)求后，按下述步驟進(jìn)行檢查： (1)如果(rgu)RequestijNeedi,j，轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2)如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej:=Availablej-Requestij Allocationi,

10、j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才將資源分配給進(jìn)程Pi；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 安全性算法 (1) 設(shè)置兩個(gè)向量：工作向量Work:系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work:=Available; Finish:系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi:=false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:

11、=true。 (2) 從進(jìn)程集合中找到滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成， 并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj:=Worki+Allocationi,j; Finishi:=true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 對(duì)待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測(cè)和解除。典型的銀行家算法屬于避免死鎖，摒棄“請(qǐng)求和保護(hù)”條件屬于預(yù)防死鎖，而剝

12、奪資源是解除死鎖的基本方法。第四章考點(diǎn)：動(dòng)態(tài)(dngti)分區(qū)分配思想、算法、回收基本分頁系統(tǒng)(xtng)的地址轉(zhuǎn)換過程基本分段系統(tǒng)的地址(dzh)轉(zhuǎn)換過程段頁式存儲(chǔ)管理系統(tǒng)的原理虛擬存儲(chǔ)的概念頁面置換算法的原理（OPT、FIFO、LRU）動(dòng)態(tài)分區(qū)分配思想：當(dāng)有進(jìn)程需分配，以進(jìn)程為單位在內(nèi)存中找到相等大小的空間進(jìn)行切割。動(dòng)態(tài)分區(qū)分配算法：首次適應(yīng)算法FF（每次從頭開始）循環(huán)首次適應(yīng)算法（找到下次的位置）最佳適應(yīng)算法（容量以從小到大順序）最壞適應(yīng)算法（容量以從大到小順序）快速適應(yīng)算法（分類搜索）回收內(nèi)存情況1：與插入點(diǎn)的前一個(gè)空閑區(qū)F1相鄰接情況2：與插入點(diǎn)的后一個(gè)空閑區(qū)F1相鄰接情況3：同時(shí)與

13、插入點(diǎn)的前、后兩個(gè)空閑區(qū)相鄰接情況4：既不與F1鄰接，又不與F2鄰接基本分頁系統(tǒng)的地址轉(zhuǎn)換過程分頁地址中的地址結(jié)構(gòu)如下：31 12 11 0頁號(hào)P位移量W位移量W又稱頁內(nèi)地址：每頁大小：212=4KB地址空間中最多有：220=1M頁邏輯地址A 頁面大小L 頁號(hào)P 頁內(nèi)地址d基本分段系統(tǒng)的地址轉(zhuǎn)換過程31 16 15 0段號(hào)段內(nèi)地址允許一個(gè)作業(yè)最多有64K個(gè)段每個(gè)段的最大長度為64KB邏輯地址A 頁面大小L 頁號(hào)P 頁內(nèi)地址d段頁式存儲(chǔ)管理系統(tǒng)(xtng)的原理分段(fn dun)和分頁原理結(jié)合；先將用戶(yngh)進(jìn)程分成若干個(gè)段；再把每個(gè)段分成若干個(gè)頁，并為每個(gè)段賦予一個(gè)段名；段號(hào)(S)段內(nèi)

14、頁號(hào)(P)頁內(nèi)地址(W)作業(yè)地址空間和地址結(jié)構(gòu)三次訪問內(nèi)存第一次訪問段表，從中取得頁表起始地址；第二次訪問頁表，從中取出該頁所在的物理塊號(hào)，并將該塊號(hào)與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次真正訪問數(shù)據(jù)或指令；虛擬存儲(chǔ)的概念（局部性原理）虛擬存儲(chǔ)器，是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器的實(shí)現(xiàn)方法 建立在離散分配的存儲(chǔ)管理方式基礎(chǔ)上分頁請(qǐng)求系統(tǒng)請(qǐng)求分段系統(tǒng)8.頁面置換算法的原理（OPT、FIFO、LRU）最佳置換算法（OPT）-離得最遠(yuǎn)淘汰最佳置換算法選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面；先進(jìn)先

15、出(FIFO)頁面置換算法-最先進(jìn)內(nèi)存的淘汰淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。最近最久未使用(LRU)置換算法 -左邊最遠(yuǎn)淘汰由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近的我將來”的近似，選擇最近最久未使用的頁面予以淘汰；第五章考點(diǎn)：I/O控制方式緩沖管理種類Spooling技術(shù)磁盤調(diào)度算法（FCFS、SSTF、SCAN、CSCAN）1.I/O控制方式程序(chngx)I/O方式CPU要不斷地測(cè)試I/O設(shè)備的狀態(tài)，因?yàn)樵贑PU中無中斷機(jī)構(gòu)，使I/O設(shè)備無法向CPU報(bào)告(bogo)它已完成了一個(gè)字符的輸入操作。 中斷(zhngdun)驅(qū)動(dòng)I/

16、O控制方式在I/O設(shè)備輸入每個(gè)數(shù)據(jù)的過程中，無須CPU干預(yù)，可使CPU與I/O設(shè)備并行工作。僅當(dāng)輸完一個(gè)數(shù)據(jù)時(shí)，才需CPU花費(fèi)極短的時(shí)間去做些中斷處理。使CPU和I/O設(shè)備都處于忙碌狀態(tài)，從而提高了整個(gè)系統(tǒng)的資源利用率及吞吐量。直接存儲(chǔ)器訪問（DMA） I/O控制方式數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，即在CPU與I/O設(shè)備之間，每次傳送至少一個(gè)數(shù)據(jù)塊；數(shù)據(jù)傳送是從設(shè)備直接送入內(nèi)存的，或者相反；僅在傳送一個(gè)或多個(gè)數(shù)據(jù)塊的開始和結(jié)束時(shí)，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在控制器的控制下完成。I/O通道控制方式 I/O通道方式是DMA方式的發(fā)展，它可進(jìn)一步減少CPU的干預(yù)，即把對(duì)一個(gè)數(shù)據(jù)塊的讀(或?qū)?為單位

17、的干預(yù)，減少為對(duì)一組數(shù)據(jù)塊的讀(或?qū)?及有關(guān)的控制和管理為單位的干預(yù)。 2.緩沖管理種類單緩沖用戶發(fā)出I/O請(qǐng)求；OS在主存中分配一緩沖區(qū)用于暫存用戶輸入的一行數(shù)據(jù)；輸入期間，用戶進(jìn)程被掛起以等待數(shù)據(jù)輸入完畢；輸出時(shí)，用戶進(jìn)程將一行數(shù)據(jù)輸入到緩沖區(qū)后，繼續(xù)執(zhí)行處理，當(dāng)戶用已有第二行數(shù)據(jù)輸出時(shí)，如果第一行數(shù)據(jù)尚未被提取完畢，則用戶進(jìn)程阻塞；雙緩沖也稱緩沖對(duì)換輸入時(shí)，將數(shù)據(jù)送入第一緩沖區(qū)，裝滿后便轉(zhuǎn)向第二緩沖區(qū)。同時(shí)，從第一緩沖區(qū)中移出數(shù)據(jù)，并送入用戶進(jìn)程，接著由CPU對(duì)數(shù)據(jù)進(jìn)行計(jì)算；雙緩沖，系統(tǒng)處理一塊數(shù)據(jù)的時(shí)間可以粗略地認(rèn)為是Max(C，T)。如果CT，則可使CPU不必等待設(shè)備輸入；循環(huán)緩沖多

18、個(gè)緩沖區(qū)；多個(gè)指針；緩沖池于既可用于輸入又可用于輸出的公用(gngyng)緩沖池，其中至少應(yīng)含有以下三種類型的緩沖區(qū): 空(閑)緩沖區(qū)； 裝滿輸入(shr)數(shù)據(jù)的緩沖區(qū)； 裝滿輸出(shch)數(shù)據(jù)的緩沖區(qū)。Spooling技術(shù)是關(guān)于慢速字符設(shè)備如何與計(jì)算機(jī)主機(jī)交換信息的一種技術(shù)，通常稱為“假脫機(jī)技術(shù)”。 共享打印機(jī) 當(dāng)用戶進(jìn)程請(qǐng)求打印輸出時(shí)， SPOOLing系統(tǒng)同意為它打印輸出，但并不真正立即把打印機(jī)分配給該用戶進(jìn)程，而只為它做兩件事： 由輸出進(jìn)程在輸出井中為之申請(qǐng)一個(gè)空閑磁盤塊區(qū)， 并將要打印的數(shù)據(jù)送入其中； 輸出進(jìn)程再為用戶進(jìn)程申請(qǐng)一張空白的用戶請(qǐng)求打印表，并將用戶的打印要求填入其中， 再將該表掛到請(qǐng)求打印隊(duì)列上。 4.磁盤調(diào)度算法（FCFS、SSTF、SCAN、CSCAN）先來先服務(wù)（FCFS）算法按訪問請(qǐng)求到達(dá)的先后次序服務(wù)最短尋道時(shí)間優(yōu)先（SSTF）算法優(yōu)先選擇距當(dāng)前磁頭最近的訪問請(qǐng)求進(jìn)行服務(wù)，主要考慮尋道優(yōu)先掃描（SCAN）算法當(dāng)設(shè)備無訪問請(qǐng)求時(shí)，磁頭不動(dòng)；當(dāng)有訪問請(qǐng)求時(shí)，磁頭按一個(gè)方向移動(dòng)，在移動(dòng)過程中對(duì)遇到的訪問請(qǐng)求進(jìn)行服務(wù)；然后判斷該方向上是否還有訪問請(qǐng)求，如果有則繼續(xù)掃描；否則改變移動(dòng)方向，并為經(jīng)過的訪問請(qǐng)求服務(wù)，如此反復(fù)。循環(huán)掃描（C