西安交通大學(xué)操作系統(tǒng)復(fù)習(xí)

1、OPERATING SYSTEM REVIEWCHAPTER 11操作系統(tǒng)定義：操控硬件的程序，用戶與硬件的媒介，分配控制資源2操作系統(tǒng)目標(biāo)：方便性（convenience），有效性（efficiency），（可擴(kuò)充性開放性）3操作系統(tǒng)作用：資源管理（處理機(jī)管理，儲(chǔ)存器管理，設(shè)備管理，文件管理，用戶接口）；服務(wù)用戶（提供接口）4操作系統(tǒng)分類(1)批處理(batch)：自動(dòng)性，沒有交互性。自動(dòng)從一個(gè)job轉(zhuǎn)移到另一個(gè)job。(2)分時(shí)(time-sharing)：允許多個(gè)用戶同時(shí)使用，CPU在多個(gè)進(jìn)程之間輪轉(zhuǎn)，可及時(shí)響應(yīng)用戶需求。(3)實(shí)時(shí)(real-time)：實(shí)時(shí)性，對時(shí)間有嚴(yán)格的要求，對安

2、全性要求高。(4)通用：同時(shí)具有兩種或以上性質(zhì)的操作系統(tǒng)。5操作系統(tǒng)特征(1)并發(fā)性(Concurrence): 并發(fā)是指兩個(gè)或者多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生，在單處理機(jī)系統(tǒng)中，宏觀上多道程序同時(shí)執(zhí)行，微觀上各個(gè)程序交替運(yùn)行。并發(fā)與并行不同，并行是指兩個(gè)或者多個(gè)事件在同一時(shí)刻發(fā)生。并發(fā)程序具有間斷性、失去封閉性和不可再現(xiàn)性等特征。(2)共享性(Sharing): 共享是指在一段時(shí)間內(nèi)多個(gè)并發(fā)進(jìn)程交替使用有限的計(jì)算機(jī)資源，共同享有計(jì)算機(jī)資源，操作系統(tǒng)對資源要合理的分配和使用。共享資源有互斥共享方式和同時(shí)訪問 方式?；コ庠L問方式是指當(dāng)一個(gè)進(jìn)程占有資源時(shí)，其他進(jìn)程不能同時(shí)再使用這個(gè)資源，必須得等到資

3、源被放棄時(shí)再使用。同時(shí)訪問方式是指如程序段和磁盤等資源，可以由進(jìn)程交替訪問。(3)虛擬性(Virtual):  虛擬是指通過某種技術(shù)把物理實(shí)體轉(zhuǎn)換成若干個(gè)邏輯對應(yīng)物。例如，地址空間具有虛擬性，它是由內(nèi)存空間通過劃分段表/頁表技術(shù)轉(zhuǎn)換而來的。(4)異步性(Asynchronism):  異步性是指進(jìn)程只要在相同的環(huán)境下，無論多少次運(yùn)行，都會(huì)得到相同的結(jié)果。6相關(guān)技術(shù)(1)多道程序技術(shù)(multiprogramming)l 定義：當(dāng)CPU正在處理的job需要等到I/O響應(yīng)時(shí)，CPU并不會(huì)閑置，而是轉(zhuǎn)去處理下一個(gè)job，直到之前的job在處理完IO后拿回CPU使用權(quán)。不可與用戶交

4、互。l 優(yōu)點(diǎn)：提高CPU利用率，控制并發(fā)。(2)分時(shí)技術(shù)(time-sharing/multitasking)定義：logical extension of multiprogramming. The cpu executes multiple jobs by switching among them, but the switch so frequently that the users can interact with each program while it is running.CHAPTER 21操作系統(tǒng)接口(1)作業(yè)級接口(Command interface)：l 命令行(co

5、mmand line interface)l 批處理(batch):規(guī)定一種特殊的文件，通常該文件有特殊的擴(kuò)展名，用戶可預(yù)先把一系列命令組織在該文件中，一次建立多次執(zhí)行l(wèi) GUI：make mouse-based-window-and-menu system as interface(2)程序級接口(Program interface)系統(tǒng)調(diào)用(system call) 定義:system call provide an interface to the service made available by the operating system.操作系統(tǒng)內(nèi)核提供的服務(wù)的接口。分類：進(jìn)程管理p

6、rocess control文件操作file manipulation設(shè)備管理device manipulation信息維護(hù)information maintenance進(jìn)程通信communication2操作系統(tǒng)結(jié)構(gòu)(OS Structure)(1)簡單結(jié)構(gòu)(MS-DOS, original unix)l MS-DOS：interfaces and levels of functionality are not well separated.leave base hardware accessible.l UNIX：series of interfaces and device driver

7、s. Monolithic structure is difficult to implement.(2)分層結(jié)構(gòu)(layered):從資源管理的角度出發(fā)，把操作系統(tǒng)分為若干層次，在某一層上只能調(diào)用低層次上的代碼，使模塊的調(diào)用更加有序。有利于系統(tǒng)維護(hù)和可靠。(3)微內(nèi)核結(jié)構(gòu)(microkernel):去除內(nèi)核中不必要的部分，將這些部分在用戶模式下實(shí)現(xiàn)，從而只給內(nèi)核最基本的功能。微內(nèi)核提供給客戶程序與運(yùn)行在用戶空間的各種服務(wù)提供通信(communication).MACHCHAPTER 3引入進(jìn)程原因在多道程序設(shè)計(jì)的環(huán)境下，程序是并發(fā)執(zhí)行的，它破壞了程序的封閉性和可再現(xiàn)性，使得程序和計(jì)算不再一一

8、對應(yīng)且由于資源共享，導(dǎo)致在各個(gè)程序之間可能存在相互制約的關(guān)系，出現(xiàn)了許多新的特征：動(dòng)態(tài)性、并發(fā)性、獨(dú)立性和異步性。程序(進(jìn)程)并發(fā)的特點(diǎn):間斷性失去了封閉性不可再現(xiàn)性程序這個(gè)靜態(tài)概念已經(jīng)不能如實(shí)反映程序活動(dòng)的這些特征。為此引入進(jìn)程這個(gè)概念來描述系統(tǒng)和用戶的活動(dòng)。進(jìn)程的概念：程序的一次執(zhí)行進(jìn)程的特性：(1)動(dòng)態(tài)性：有生命周期(2)并發(fā)性：并發(fā)執(zhí)行(3)獨(dú)立性：獨(dú)立獲得資源、獨(dú)立運(yùn)行單位(4)異步性：推進(jìn)速度不可預(yù)知道、執(zhí)行結(jié)果不確定(5)結(jié)構(gòu)性：由程序段、數(shù)據(jù)段和PCB組成進(jìn)程的狀態(tài)(process state)：進(jìn)程的組成程序(text section),數(shù)據(jù)(data section),PC

9、B(process control blocks)PCB的定義：記錄OS所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息，是進(jìn)程存在的唯一標(biāo)志，常駐內(nèi)存。PCB的內(nèi)容：進(jìn)程標(biāo)識符；處理機(jī)狀態(tài)（CPU現(xiàn)場）；進(jìn)程調(diào)度信息：狀態(tài)、優(yōu)先級、時(shí)間、事件；進(jìn)程控制信息：地址、通信信息、資源。Program counter指明進(jìn)程的下一條指令CPU registers 中斷發(fā)生時(shí)，所有的寄存器需要被存儲(chǔ)。CPU-scheduling info 包括進(jìn)程優(yōu)先級，進(jìn)程隊(duì)列指針等調(diào)度信息Memory-management info 包括基本寄存器的值，頁表等信息Accounting info 記錄進(jìn)程運(yùn)

10、行的時(shí)間，使用了多少CPU等IO status info 包括分配給進(jìn)程的設(shè)備進(jìn)程與程序的區(qū)別聯(lián)系（1）進(jìn)程是程序的一次執(zhí)行，是一個(gè)動(dòng)態(tài)的概念；而程序是一組有序的指令， 是一種靜態(tài)的概念。即進(jìn)程是程序執(zhí)行的動(dòng)態(tài)過程，而程序則是進(jìn)程運(yùn)行的靜態(tài)文本。（2）一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，同一個(gè)程序也可能由幾個(gè)進(jìn)程同時(shí)執(zhí)行。（3）程序可長期保存，而進(jìn)程是有生命周期的。（4）進(jìn)程是并發(fā)實(shí)體, 而程序則不是。進(jìn)程與線程的區(qū)別聯(lián)系（1）調(diào)度方面：線程作為調(diào)度分派的基本單位，而進(jìn)程則是資源分配和調(diào)度的一個(gè)基本單位；（2）并發(fā)性方面：進(jìn)程之間可以并發(fā)，一個(gè)進(jìn)程的多線程之間也可并發(fā)執(zhí)行；（3）擁有資源方面：進(jìn)程

11、作為擁有資源的基本單位，而線程只擁有少量必不可少的資源，但它可以訪問所屬進(jìn)程的資源（4）系統(tǒng)開銷方面：進(jìn)程切換要涉及到進(jìn)程環(huán)境的切換，開銷較大，而線程間切換只需保存和設(shè)置少量的寄存器內(nèi)容，開銷遠(yuǎn)小于進(jìn)程切換開銷進(jìn)程的控制(1) 進(jìn)程控制由操作系統(tǒng)內(nèi)核完成(2) 內(nèi)核通過執(zhí)行相應(yīng)的原語(primitive)來實(shí)現(xiàn)進(jìn)程的控制(3) 進(jìn)程控制原語：創(chuàng)建，終止，阻塞，喚醒，掛起，激活創(chuàng)建原語完成以下工作：申請一個(gè)空PCB，初始化PCB中項(xiàng)目，把PCB插入就緒隊(duì)列撤消原語完成以下工作：根據(jù)ID在PCB鏈中查找相應(yīng)PCB，檢查進(jìn)程狀態(tài)。若是執(zhí)行狀態(tài)則終止進(jìn)程；終止其子進(jìn)程；回收資源；撤銷PCB阻塞原語：當(dāng)

12、出現(xiàn)阻塞事件，將狀態(tài)改為阻塞狀態(tài)，進(jìn)入阻塞隊(duì)列喚醒原語：將阻塞進(jìn)程喚醒，狀態(tài)改為READY，插入就緒隊(duì)列。掛起原語：進(jìn)程從內(nèi)存轉(zhuǎn)到外存，改變相應(yīng)狀態(tài)激活原語：進(jìn)程從外存轉(zhuǎn)到內(nèi)存，改變相應(yīng)狀態(tài)CHAPTER 4線程(thread)定義：A thread is a basic unit of CPU utilization.處理機(jī)調(diào)度的基本單位，是進(jìn)程內(nèi)的一個(gè)可調(diào)度實(shí)體，又稱輕量級進(jìn)程。引入目的：提高系統(tǒng)效率，提高資源利用率，減少進(jìn)程并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使操作系統(tǒng)有更好的并發(fā)性。(一個(gè)進(jìn)程中的所有線共享同樣的code,data,file，比如一個(gè)web server，對于所有的reques

13、t，反應(yīng)幾乎一樣，若為每個(gè)request新創(chuàng)建一個(gè)進(jìn)程，會(huì)造成code,data,file的重復(fù)，造成空間，時(shí)間資源的浪費(fèi))線程包括：線程ID，當(dāng)前指令指針(PC)，寄存器集合，堆棧。用戶級線程和內(nèi)核支持線程：(1)用戶線程(user thread)：存在于用戶空間中，其創(chuàng)建、撤消和切換都不需系統(tǒng)支持。(2)內(nèi)核支持線程(kernel thread)：是依賴于內(nèi)核的，其創(chuàng)建、撤消和切換都是由內(nèi)核實(shí)現(xiàn)的。Multithreading modelsMany to one: many user level threads to one kernel thread.(因?yàn)橹挥幸粋€(gè)線程可以access內(nèi)

14、核，因此多個(gè)線程不可以同時(shí)在多個(gè)內(nèi)核上運(yùn)行)One to one: each user thread to a kernel thread(多個(gè)線程可以在多個(gè)內(nèi)核上同時(shí)運(yùn)行，一個(gè)阻塞也不會(huì)影響其他，但每一個(gè)用戶線程均要?jiǎng)?chuàng)立一個(gè)內(nèi)核線程，額外開銷大，限制應(yīng)用程序的性能)Many to many: many user level threads to a smaller or equal number of kernel threads.(開銷不大，而且線程可以并發(fā))CHAPTER 5三級調(diào)度(1)高級調(diào)度：Long-term scheduler (job-scheduler): select a

15、 process from the pool and loads them into memory for execution.從job pool里選一個(gè)進(jìn)程加載在內(nèi)存里(2)低級調(diào)度：Short term scheduler (CPU-scheduler): select a process from the processes in memory that are ready to execute and allocates the CPU to the process.從內(nèi)存中選擇一個(gè)進(jìn)程給CPU執(zhí)行(3)中級調(diào)度：Mid-term scheduler: remove processes

16、 from memory and later reintroduce it into memory. 把內(nèi)存中的進(jìn)程swap出去再swap進(jìn)來調(diào)度時(shí)機(jī)(1)現(xiàn)運(yùn)行進(jìn)程任務(wù)完成或出現(xiàn)異常(2)現(xiàn)運(yùn)行進(jìn)程因某種原因由執(zhí)行變成阻塞狀態(tài)(3)時(shí)間片用完(4)采用可剝奪調(diào)度方式時(shí)，有更高優(yōu)先級進(jìn)程進(jìn)入就緒隊(duì)列調(diào)度參數(shù)(scheduling criteria)周轉(zhuǎn)時(shí)間(turnaround time)等待時(shí)間(waiting time)響應(yīng)時(shí)間(response time)調(diào)度算法FCFS(first-come first-serve)SJF(shortest-job-first)Priority(優(yōu)先權(quán)

17、調(diào)度)Round-Robin(時(shí)間片輪轉(zhuǎn))Multilevel Queue(多級隊(duì)列)：根據(jù)進(jìn)程的性質(zhì)將就緒隊(duì)列分為幾個(gè)隊(duì)列，每個(gè)隊(duì)列有不同的調(diào)度算法，隊(duì)列與隊(duì)列之間的調(diào)度一般為優(yōu)先級調(diào)度或時(shí)間片。Multilevel Feedback-Queue(多級反饋隊(duì)列)：主流OS使用此算法。與多級隊(duì)列算法不同的是，多級反饋隊(duì)列允許進(jìn)程轉(zhuǎn)移到其他隊(duì)列。因此多級反饋隊(duì)列還要設(shè)計(jì)進(jìn)程的升級與降級規(guī)則。（此處還有多處理機(jī)的調(diào)度，線程的調(diào)度）CHAPTER 6基本概念臨界區(qū)（critical section）：一段代碼，用來修改臨界資源，只能有一個(gè)進(jìn)程處于臨界區(qū)進(jìn)入?yún)^(qū)（entry section）：請求進(jìn)入臨

18、界區(qū)的程序退出區(qū)（exit section）：緊跟著臨界區(qū)后的程序剩余區(qū)（remainder section）：剩下的程序解決臨界區(qū)問題的三個(gè)要求互斥(Mutual exclusion)：保證安全有空讓進(jìn)(Progress)：保證資源利用率有限等待(Bounded waiting)：防止饑餓Peterson算法(1) 只能控制兩個(gè)進(jìn)程(2) 程序P0: flag0 = true; turn = 1; while (flag1 = true && turn = 1) / busy wait / critical section flag0 = false; / end of cr

19、itical sectionP1: flag1 = true; turn = 0; while (flag0 = true && turn = 0) / busy wait / critical section flag1 = false; / end of critical section(3) 程序分析滿足互斥：如果兩個(gè)進(jìn)程都在臨界區(qū)，則FLAGi=FLAGj=1。但turn必然會(huì)取0或1中的一個(gè)，因此必有一個(gè)while滿足條件，故必有一個(gè)進(jìn)程在while循環(huán)中等待。因此假設(shè)錯(cuò)誤，不可能有兩個(gè)進(jìn)程同時(shí)在臨界區(qū)。滿足有空讓進(jìn)和有限等待：假設(shè)Pi已經(jīng)準(zhǔn)備好進(jìn)入臨界區(qū)，正在whi

20、le循環(huán)中等待。對于Pj的以下三種情況：l 若Pj未準(zhǔn)備好，則FLAGj = 0，那么Pi的while條件不再滿足，進(jìn)入臨界區(qū)。l 若Pj準(zhǔn)備好了，且也在while循環(huán)中，則turn = 0, 那么Pi的while條件不再滿足，進(jìn)入臨界區(qū)。l 若Pj剛出臨界區(qū)，則FLAGj = 0，那么Pi的while條件不再滿足，進(jìn)入臨界區(qū)。因此，只要Pj不在臨界區(qū)了，Pi就可以進(jìn)入臨界區(qū)，因此滿足有空讓進(jìn)；當(dāng)Pj執(zhí)行完臨界區(qū)，Pi就可以進(jìn)入臨界區(qū)，滿足有限等待。信號量（Semaphore）與PV操作信號量：A Semaphore is a special integer variable, it can

21、be accessed only through two standard atomic operations。P操作( wait)：request a resourceWait(S) while S <= 0 ; / no-opS-;V操作( signal)：release a resourcesignal (S) S+;/P.V操作必須成對出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作/當(dāng)為互斥操作時(shí)，它們處于同一進(jìn)程/當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)/對于前后相連的兩個(gè)P(S1)和P(S2) ，順序是至關(guān)重要的:同步P操作應(yīng)該放在互斥P操作前,而兩個(gè)V操作順序則無關(guān)緊要信號量實(shí)現(xiàn)互斥為臨

22、界資源設(shè)置一個(gè)互斥信號量mutex，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間信號量實(shí)現(xiàn)同步P.V操作必須成對出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作三個(gè)經(jīng)典問題（1）生產(chǎn)者消費(fèi)者（2）讀者寫者（3）哲學(xué)家吃米飯While (true) wait ( chopsticki ); wait ( chopStick (i + 1) % 5 ); / eat signal ( chopsticki ); signal (chopstick (i + 1) % 5 ); / think管程（Monitor）的定義：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程調(diào)用的在該數(shù)

23、據(jù)結(jié)構(gòu)上的一組操作過程，這組互斥操作的過程，能同步進(jìn)程和改變管程中的數(shù)據(jù)。 管程實(shí)現(xiàn)互斥：外部等待隊(duì)列。一個(gè)管程的程序在運(yùn)行一個(gè)線程前會(huì)先獲取互斥鎖，直到完成線程或是線程等待某個(gè)條件被滿足才會(huì)放棄互斥鎖。管程實(shí)現(xiàn)同步：內(nèi)部設(shè)置條件變量。一個(gè)條件變量就是一個(gè)線程隊(duì)列(queue), 其中的線程正等待某個(gè)條件變?yōu)檎妗HAPTER 7 DEADLOCK死鎖(deadlock)的概念計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或兩個(gè)以上的進(jìn)程由于競爭資源而造成的一種互相等待的現(xiàn)象（僵局），如無外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。死鎖產(chǎn)生原因眾多進(jìn)程競爭有限資源；進(jìn)程推進(jìn)順序不合適。死鎖產(chǎn)生的必要條件互斥

24、使用（Mutual exclusion）不可剝奪（No preemption）請求保持（Hold and wait） 環(huán)路等待（Circular wait）解決死鎖的方案（1）設(shè)計(jì)無死鎖的系統(tǒng)：預(yù)防、避免（2）允許出現(xiàn)死鎖然后排除：檢測并解除（3）置之不理資源分配圖（resource-allocation graph）中的概念辨析沒有環(huán)路，則沒有死鎖有環(huán)路，可能有死鎖也可能沒有若每種資源只有一個(gè)實(shí)例，有環(huán)路就有死鎖死鎖的預(yù)防破壞四個(gè)必要條件之一，通常是破壞第三、四個(gè)條件。（1）資源的靜態(tài)分配方法：進(jìn)程運(yùn)行前一次性申請全部資源,破壞請求和保持條件.（2）資源的順序分配法：系統(tǒng)的全部資源進(jìn)行編號，

25、只允許按編號順序遞增地申請，破除環(huán)路待。（3）一個(gè)已占有資源的進(jìn)程,若要申請新的資源，必須先放棄已占有的資源，破壞請求保持條件。死鎖的避免每當(dāng)進(jìn)程申請資源時(shí)，都根據(jù)一定的算法判斷是否安全安全狀態(tài)：當(dāng)多個(gè)進(jìn)程動(dòng)態(tài)申請資源時(shí)，系統(tǒng)按某一順序逐次地為每個(gè)進(jìn)程分配所需資源，使每個(gè)進(jìn)程都可以在最終得到最大需求量后依次順利完成。不安全狀態(tài)：可能死鎖避免死鎖的關(guān)鍵：讓系統(tǒng)在動(dòng)態(tài)分配資源的過程中，不要進(jìn)入不安全狀態(tài)銀行家算法死鎖的解除：刪除法：刪除死鎖進(jìn)程，將其資源分給其他進(jìn)程剝奪法：剝奪某些進(jìn)程的資源CHAPTER 8 MAIN MEMORY一些概念l 邏輯地址：an address generated b

26、y cpul 物理地址：an address seen by the memory unitl 內(nèi)存管理單元(MMU-memory management unit): 包括一個(gè)基地址寄存器(relocation register)和一個(gè)加法器，在程序運(yùn)行時(shí)map虛擬地址到物理地址。l Compiler bind symbolic address to reloacatable addressl Loader/linkage editor bind relocatable address to absolute address重定位動(dòng)態(tài)重定位：在程序執(zhí)行期間每次訪問內(nèi)存之前進(jìn)行重定位。這種變換是

27、靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。通常采用重定位寄存器，其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址，而地址空間中的代碼在裝入過程中不發(fā)生變化。靜態(tài)重定位：在目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的邏輯地址改成物理地址。對每個(gè)程序來說，這種地址變換只是在裝入時(shí)一次完成，在程序運(yùn)行期間不再進(jìn)行重定位。內(nèi)存為程序分配空間的四種方式（1） 連續(xù)分配方式（contiguous memory allocation）單一連續(xù)分配固定分區(qū)分配：分區(qū)容量和數(shù)目固定不變，大小可不等，每個(gè)分區(qū)容納一道作業(yè)可變分區(qū)分配：動(dòng)態(tài)分區(qū)，作業(yè)裝入內(nèi)存時(shí)才建立分區(qū)（根據(jù)作業(yè)的大?。?四種動(dòng)態(tài)分區(qū)分配算法：l 首次

28、適應(yīng)(first fit):allocate the first holel 最佳適應(yīng)(best fit):allocate the smallest holel 最差適應(yīng)(worst fit): allocate the largest holel Next fit: 從剛剛分配出的內(nèi)存開始查找合適的hole分配可重定位分區(qū)分配：重定位寄存器(relocation register)、緊湊技術(shù)（把進(jìn)程統(tǒng)一移向一邊）（2） 基本分頁存儲(chǔ)管理方式(paging) 分頁引入：動(dòng)態(tài)分區(qū)方式產(chǎn)生“外碎片”，采用緊湊技術(shù)要付出很大開銷，于是引入了頁式存儲(chǔ)管理。分頁定義A memory-managemen

29、t scheme that permits the physical address space of fitting memory to be noncontiguous.分頁原理：l 將物理內(nèi)存分割為等份，叫做物理塊(frame)，大小一般為2的次方l 將邏輯地址分割為等份，叫做頁(page)，大小與frame相等l 建立page與frame的關(guān)系映射，叫做頁表(page table)，頁表在內(nèi)存里。l 地址轉(zhuǎn)換是在進(jìn)程執(zhí)行過程中進(jìn)行的。分頁的地址變換過程當(dāng)一個(gè)進(jìn)程轉(zhuǎn)入執(zhí)行狀態(tài)時(shí)，其頁表的始址和長度從其PCB中裝入頁表寄存器。當(dāng)進(jìn)程要訪問某個(gè)邏輯地址中的指令或數(shù)據(jù)時(shí)，地址變換機(jī)構(gòu)自動(dòng)地將邏

30、輯地址分為頁號和頁內(nèi)地址兩部分，并將頁號與頁表寄存器中的頁表長度比較，若頁號不小于頁表長度，便產(chǎn)生越界中斷，否則以頁號為索引，去檢索頁表，從中得到該頁的物理塊號，送入物理地址寄存器與頁內(nèi)地址拼接，形成物理地址。快表(TLB-translation look-aside buffer)為了提高訪問速度，存放被頻繁訪問的頁面的頁表項(xiàng)。先查快表，沒有查到再查頁表。快表很小，訪問很快，造價(jià)高。內(nèi)存訪問時(shí)間的計(jì)算(effective access time)Effective access time = 快表命中率*（快表時(shí)+內(nèi)存時(shí)）+（1-快表命中率）*（快表時(shí)+2*內(nèi)存時(shí)）（3） 基本分段存儲(chǔ)管理方

31、式(segmentation)硬件實(shí)現(xiàn)定義：a memory-management scheme that support the user view of memory. A logical address space is a collection of segments. Each has a name and a length.（4） 段頁式存儲(chǔ)管理方式對換技術(shù)(swapping)定義：把主存中暫時(shí)不能運(yùn)行的進(jìn)程調(diào)出到外存,以便騰出足夠的內(nèi)存空間，再將具備運(yùn)行條件的進(jìn)程調(diào)入內(nèi)存。作用：從邏輯上擴(kuò)充內(nèi)存空間,從而使整個(gè)系統(tǒng)資源利用率提高.整體對換:以進(jìn)程為單位,進(jìn)程對換部分對換:頁面對換

32、,分段對換碎片(fragmentation)內(nèi)部碎片(internal fragmentation)：已被分配出去的內(nèi)存空間大于請求所需的空間外部碎片(external fragmentation)：還沒有被分配出去但由于太小而無法分配給新進(jìn)程的空閑塊分區(qū)的保護(hù)：(1)界地址寄存器一對界地址寄存器存放分區(qū)的上、下界地址，物理地址需滿足如下關(guān)系：上界地址寄存器內(nèi)容<= 物理地址 <=下界地址寄存器內(nèi)容(2)基址限長寄存器(base register and limit register):這兩個(gè)寄存器只有os才可以修改 基址寄存器: 分區(qū)的首址 限長寄存器: 作業(yè)地址空間的長度物理地

33、址 基址寄存器內(nèi)容 <= 限長寄存器內(nèi)容(3)分頁管理中在頁表中的每一項(xiàng)設(shè)置保護(hù)位CHAPTER 9VIRTUAL MEMORY虛擬內(nèi)存(virtual memory)具有請求調(diào)入功能和置換功能、能從邏輯上對內(nèi)存容量加以擴(kuò)充的存儲(chǔ)器系統(tǒng)稱為虛擬存儲(chǔ)器Virtual memory is a technique that allows the execution of processes that may not be completely in memory.Virtual memory is the separation of user logical memory from physi

34、cal memory.請求分頁(demand paging)定義：基本分頁的基礎(chǔ)上增加請求調(diào)頁功能 和頁面置換功能。作業(yè)被調(diào)度投入運(yùn)行前，只裝入部分頁面到內(nèi)存，其他各頁，根據(jù)請求而被裝入。頁表增加以下內(nèi)容：存在位P、訪問字段A、修改位M、外存地址。地址變換過程頁面置換算法(page replacement algorithm)l FIFO：換出去最老的一頁l 理想頁面置換算法OPT(optimal page replacement)：換出去在reference string中最遠(yuǎn)的頁，也就是未來最后才出現(xiàn)頁l 最久未使用算法LRU(least-recently-used)：換出去最久沒有被使用

35、的頁，可以用counter 或 stack 來實(shí)現(xiàn)。l LRU近似算法a) 附加引用位算法(additional reference bit)：每個(gè)頁設(shè)置8個(gè)附加位，每次引用時(shí)右移（丟掉末尾，首位補(bǔ)一或補(bǔ)零，置換出八位數(shù)字最小的那個(gè)頁）b) 二次機(jī)會(huì)算法(second chance)：設(shè)置一個(gè)附加位，換出附加位是0的，附加位是1的給一次機(jī)會(huì)，然后置0c) 增強(qiáng)型二次機(jī)會(huì)算法(enhanced second chance)：設(shè)置兩個(gè)附加位，一個(gè)表示引用一個(gè)表示修改。顛簸(thrashing)定義：頁面頻繁地調(diào)入或換出，CPU利用率低下解決方案：l 采用局部置換：若一個(gè)進(jìn)程開始顛簸，采用局部置換，

36、不會(huì)使其它進(jìn)程也發(fā)生顛簸l 給進(jìn)程提供足夠的物理塊：根據(jù)進(jìn)程執(zhí)行的局部模型，來確定進(jìn)程真正需要多少物理塊l 一種更加直接的防止顛簸的方法是控制缺頁頻率（ Page-Fault Frequency ）工作集模型(working-set model)：用參數(shù)定義一個(gè)工作集窗口，如果工作集窗口中的頁面不再活躍，移動(dòng)工作集。預(yù)調(diào)頁(prepaging):當(dāng)一個(gè)新進(jìn)程開始進(jìn)入內(nèi)存時(shí)，會(huì)發(fā)生很多缺頁中斷。可以使用工作集模型，在掛起一個(gè)進(jìn)程時(shí)記錄下工作集，然后resume時(shí)先調(diào)入工作集里所有的頁。CHAPTER 10FILE-SYSTEM INTERFACE文件定義具有文件名的一組相關(guān)信息的集合。A fil

37、e is a named collection of related information that is recorded on secondary storage.文件的屬性信息(file attributes)Name identifier location type protection size time, date, and user identification文件的操作(file operations): 用戶通過文件系統(tǒng)提供的系統(tǒng)調(diào)用實(shí)施文件的操作l 創(chuàng)建文件：分配磁盤空間，創(chuàng)建文件目錄入口l 寫文件：從目錄中找到文件地址，置寫指針l 讀文件：在文件目錄中找到文件入口，置讀

38、指針l 文件指針重定位(repositioning within a file)l 刪除文件：在目錄中找到文件，釋放磁盤空間，刪除文件目錄信息l 刪除文件內(nèi)容(truncating a file)文件的邏輯結(jié)構(gòu)(file structure)分為有結(jié)構(gòu)文件（記錄式文件）、無結(jié)構(gòu)文件（流式文件）。記錄式文件：順序文件：記錄通常是定長的，順序存?。凰饕募河涗浲ǔＪ亲冮L的，方便直接存?。凰饕樞蛭募呵岸叩慕Y(jié)合，減少了索引表所占的空間文件的訪問方式(access method)順序訪問（磁帶模型）/隨機(jī)訪問（磁盤模型）/索引表訪問目錄(directory)：即文件夾,是用來記錄每個(gè)文件在磁盤上

39、的地址的數(shù)據(jù)結(jié)構(gòu).它保存的不是用戶數(shù)據(jù),而是關(guān)于文件及文件系統(tǒng)的信息,即文件夾里面存放的是從文件到文件所在磁盤地址的映射. FCB的有序集合，其中的每個(gè)FCB叫作一個(gè)目錄項(xiàng)。目錄管理的目標(biāo)：實(shí)現(xiàn)按名存取文件，提供快速的目錄查詢手段以提高對文件的檢索速度，并能為文件的共享和重名提供方便。目錄結(jié)構(gòu)單級目錄結(jié)構(gòu)；l 兩級目錄結(jié)構(gòu)： 一級稱為主文件目錄（MFD），給出用戶名，用戶子目錄所在的物理位置；二級稱為用戶文件目錄（UFD，又稱用戶子目錄），給出該用戶所有文件的FCBl 多級目錄結(jié)構(gòu)：當(dāng)前目錄（工作目錄）、絕對路徑、相對路徑；當(dāng)前目錄(current directory):contain mos

40、t of the files that are of current interest to the process絕對路徑(absolute path):從根目錄開始到指定文件的路徑；相對路徑(relative path):從當(dāng)前目錄出發(fā)到指定文件的路徑。目錄查詢：系統(tǒng)利用用戶給定的路徑名對目錄進(jìn)行查詢，找到對應(yīng)的FCB或索引結(jié)點(diǎn)，然后找到具體的文件提高目錄檢索效率將文件名和描述信息分開（如UNIX的iNode）哈希表文件的保護(hù)/此處的復(fù)習(xí)PPT不知道哪來的實(shí)現(xiàn)分級的文件保護(hù).第一級是要區(qū)分用戶.第二級是區(qū)分文件的訪問權(quán)限.實(shí)現(xiàn)基于用戶身份的文件保護(hù)的一個(gè)方法是為每個(gè)文件或者目錄增加一個(gè)訪問

41、控制表(access control list),列出不同用戶對該文件或者目錄的訪問權(quán)限.當(dāng)用戶請求訪問一個(gè)文件時(shí),OS首先檢查其訪問控制表,看該用戶有無相應(yīng)的訪問權(quán)限.文件共享/此處的復(fù)習(xí)PPT同樣不知道在說什么CHAPTER 11 FILE-SYSTEM IMPLEMENT文件系統(tǒng)：定義：OS中與文件管理有關(guān)的部分軟件及被它們管理的文件和文件屬性的集合。組成部分A collection of files: storing related dataA directory structure: organizing and providing information about all the

42、 files in the sytemFCB（file-control block）文件控制表：與文件一一對應(yīng)。其基本的內(nèi)容包括文件名、文件的物理地址、文件的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、文件的長度、存取權(quán)限、文件的建立日期、修改日期及時(shí)間、連接計(jì)數(shù)文件主標(biāo)識符等。文件的物理結(jié)構(gòu)（文件在磁盤上的分配方式）l 連續(xù)分配Contiguous allocation方法：每個(gè)文件在磁盤上占據(jù)一片連續(xù)的blocks優(yōu)點(diǎn)：簡單、順序訪問速度快、支持隨機(jī)存取缺點(diǎn)：外碎片、空間利用率低、不利于文件的動(dòng)態(tài)增長l 鏈接分配Linked allocationa) 隱式鏈接：一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通

43、過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊消除了外碎片、允許作業(yè)動(dòng)態(tài)增長；可靠性差、只適于順序訪問b) 顯式鏈接：文件分配表FAT（整個(gè)磁盤只有一張）儲(chǔ)存了鏈接的關(guān)系不支持高效的隨機(jī)存取，F(xiàn)AT表占用空間l 索引分配Indexed allocation每個(gè)文件建立一張索引表，指出分配給該文件的所有物理塊號支持高效隨機(jī)存取、消除了外碎片、允許文件動(dòng)態(tài)增長；但索引表占用較多空間文件存儲(chǔ)空間的管理(free-space management)l 空閑表法(counting)：適用于連續(xù)分配。系統(tǒng)建立一張空閑表，每個(gè)表項(xiàng)對應(yīng)一個(gè)空閑區(qū)，登記的該區(qū)的起始塊號和塊數(shù)等。分配算法：首次適應(yīng)、最佳適應(yīng)等。l 空

44、閑鏈法(linked list)：把空閑塊組織成一個(gè)鏈接文件l 位示圖法(bit vector)：適用于所有分配方式l 成組鏈接法(grouping)：將一個(gè)文件卷的所有空閑盤塊按固定大?。ㄈ缑拷M100塊）分成若干組，并將每組的盤塊數(shù)和該組所有盤塊號記入前一組的最后一個(gè)備用塊內(nèi)，第一組的盤塊數(shù)（可小于100）和該組所有的盤塊號記入超級塊的空閑盤塊號棧中。/文件的物理結(jié)構(gòu)，文件操作的系統(tǒng)實(shí)現(xiàn)，目錄檢索，文件的訪問方式與文件結(jié)構(gòu)之間的關(guān)系。CHAPTER 12DISK ATTACHMENT磁盤訪問的時(shí)間(random access time)包括 尋道時(shí)間(seek time)：磁頭移動(dòng)到指定磁道旋轉(zhuǎn)時(shí)間(rotational latency)：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過數(shù)據(jù)傳輸時(shí)間：數(shù)據(jù)在磁盤與內(nèi)存之間的傳輸