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

1、OPERATING SYSTEM REVIEWCHAPTER 11操作系統(tǒng)定義：操控硬件的程序，用戶與硬件的媒介，分配控制資源2操作系統(tǒng)目標(biāo)：方便性（convenience），有效性（efficiency），（可擴(kuò)充性開(kāi)放性）3操作系統(tǒng)作用：資源管理（處理機(jī)管理，儲(chǔ)存器管理，設(shè)備管理，文件管理，用戶接口）；服務(wù)用戶（提供接口）4操作系統(tǒng)分類(1)批處理(batch)：自動(dòng)性，沒(méi)有交互性。自動(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í)性，對(duì)時(shí)間有嚴(yán)格的要求，對(duì)安

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)對(duì)資源要合理的分配和使用。共享資源有互斥共享方式和同時(shí)訪問(wèn) 方式?；コ庠L問(wèn)方式是指當(dāng)一個(gè)進(jìn)程占有資源時(shí)，其他進(jìn)程不能同時(shí)再使用這個(gè)資源，必須得等到資

3、源被放棄時(shí)再使用。同時(shí)訪問(wèn)方式是指如程序段和磁盤(pán)等資源，可以由進(jìn)程交替訪問(wèn)。(3)虛擬性(Virtual):  虛擬是指通過(guò)某種技術(shù)把物理實(shí)體轉(zhuǎn)換成若干個(gè)邏輯對(duì)應(yīng)物。例如，地址空間具有虛擬性，它是由內(nèi)存空間通過(guò)劃分段表/頁(yè)表技術(shù)轉(zhuǎn)換而來(lái)的。(4)異步性(Asynchronism):  異步性是指進(jìn)程只要在相同的環(huán)境下，無(wú)論多少次運(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è)級(jí)接口(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)程序級(jí)接口(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ǎn)單結(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、對(duì)應(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è)概念來(lái)描述系統(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)識(shí)符；處理機(jī)狀態(tài)（CPU現(xiàn)場(chǎng)）；進(jìn)程調(diào)度信息：狀態(tài)、優(yōu)先級(jí)、時(shí)間、事件；進(jìn)程控制信息：地址、通信信息、資源。Program counter指明進(jìn)程的下一條指令CPU registers 中斷發(fā)生時(shí)，所有的寄存器需要被存儲(chǔ)。CPU-scheduling info 包括進(jìn)程優(yōu)先級(jí)，進(jìn)程隊(duì)列指針等調(diào)度信息Memory-management info 包括基本寄存器的值，頁(yè)表等信息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)過(guò)程，而程序則是進(jìn)程運(yùn)行的靜態(tài)文本。（2）一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，同一個(gè)程序也可能由幾個(gè)進(jìn)程同時(shí)執(zhí)行。（3）程序可長(zhǎng)期保存，而進(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、作為擁有資源的基本單位，而線程只擁有少量必不可少的資源，但它可以訪問(wèn)所屬進(jìn)程的資源（4）系統(tǒng)開(kāi)銷方面：進(jìn)程切換要涉及到進(jìn)程環(huán)境的切換，開(kāi)銷較大，而線程間切換只需保存和設(shè)置少量的寄存器內(nèi)容，開(kāi)銷遠(yuǎn)小于進(jìn)程切換開(kāi)銷進(jìn)程的控制(1) 進(jìn)程控制由操作系統(tǒng)內(nèi)核完成(2) 內(nèi)核通過(guò)執(zhí)行相應(yīng)的原語(yǔ)(primitive)來(lái)實(shí)現(xiàn)進(jìn)程的控制(3) 進(jìn)程控制原語(yǔ)：創(chuàng)建，終止，阻塞，喚醒，掛起，激活創(chuàng)建原語(yǔ)完成以下工作：申請(qǐng)一個(gè)空PCB，初始化PCB中項(xiàng)目，把PCB插入就緒隊(duì)列撤消原語(yǔ)完成以下工作：根據(jù)ID在PCB鏈中查找相應(yīng)PCB，檢查進(jìn)程狀態(tài)。若是執(zhí)行狀態(tài)則終止進(jìn)程；終止其子進(jìn)程；回收資源；撤銷PCB阻塞原語(yǔ)：當(dāng)

12、出現(xiàn)阻塞事件，將狀態(tài)改為阻塞狀態(tài)，進(jìn)入阻塞隊(duì)列喚醒原語(yǔ)：將阻塞進(jìn)程喚醒，狀態(tài)改為READY，插入就緒隊(duì)列。掛起原語(yǔ)：進(jìn)程從內(nèi)存轉(zhuǎn)到外存，改變相應(yīng)狀態(tài)激活原語(yǔ)：進(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í)進(jìn)程。引入目的：提高系統(tǒng)效率，提高資源利用率，減少進(jìn)程并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，使操作系統(tǒng)有更好的并發(fā)性。(一個(gè)進(jìn)程中的所有線共享同樣的code,data,file，比如一個(gè)web server，對(duì)于所有的reques

13、t，反應(yīng)幾乎一樣，若為每個(gè)request新創(chuàng)建一個(gè)進(jìn)程，會(huì)造成code,data,file的重復(fù)，造成空間，時(shí)間資源的浪費(fèi))線程包括：線程ID，當(dāng)前指令指針(PC)，寄存器集合，堆棧。用戶級(jí)線程和內(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)核線程，額外開(kāi)銷大，限制應(yīng)用程序的性能)Many to many: many user level threads to a smaller or equal number of kernel threads.(開(kāi)銷不大，而且線程可以并發(fā))CHAPTER 5三級(jí)調(diào)度(1)高級(jí)調(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)低級(jí)調(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)中級(jí)調(diào)度：Mid-term scheduler: remove processes

16、 from memory and later reintroduce it into memory. 把內(nèi)存中的進(jìn)程swap出去再swap進(jìn)來(lái)調(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í)進(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(多級(jí)隊(duì)列)：根據(jù)進(jìn)程的性質(zhì)將就緒隊(duì)列分為幾個(gè)隊(duì)列，每個(gè)隊(duì)列有不同的調(diào)度算法，隊(duì)列與隊(duì)列之間的調(diào)度一般為優(yōu)先級(jí)調(diào)度或時(shí)間片。Multilevel Feedback-Queue(多級(jí)反饋隊(duì)列)：主流OS使用此算法。與多級(jí)隊(duì)列算法不同的是，多級(jí)反饋隊(duì)列允許進(jìn)程轉(zhuǎn)移到其他隊(duì)列。因此多級(jí)反饋隊(duì)列還要設(shè)計(jì)進(jìn)程的升級(jí)與降級(jí)規(guī)則。（此處還有多處理機(jī)的調(diào)度，線程的調(diào)度）CHAPTER 6基本概念臨界區(qū)（critical section）：一段代碼，用來(lái)修改臨界資源，只能有一個(gè)進(jìn)程處于臨界區(qū)進(jìn)入?yún)^(qū)（entry section）：請(qǐng)求進(jìn)入臨

18、界區(qū)的程序退出區(qū)（exit section）：緊跟著臨界區(qū)后的程序剩余區(qū)（remainder section）：剩下的程序解決臨界區(qū)問(wèn)題的三個(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)中等待。對(duì)于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ū)，滿足有限等待。信號(hào)量（Semaphore）與PV操作信號(hào)量：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操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作/當(dāng)為互斥操作時(shí)，它們處于同一進(jìn)程/當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)/對(duì)于前后相連的兩個(gè)P(S1)和P(S2) ，順序是至關(guān)重要的:同步P操作應(yīng)該放在互斥P操作前,而兩個(gè)V操作順序則無(wú)關(guān)緊要信號(hào)量實(shí)現(xiàn)互斥為臨

22、界資源設(shè)置一個(gè)互斥信號(hào)量mutex，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語(yǔ)之間信號(hào)量實(shí)現(xiàn)同步P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作三個(gè)經(jīng)典問(wèn)題（1）生產(chǎn)者消費(fèi)者（2）讀者寫(xiě)者（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)上的一組操作過(guò)程，這組互斥操作的過(guò)程，能同步進(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)檎?。CHAPTER 7 DEADLOCK死鎖(deadlock)的概念計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或兩個(gè)以上的進(jìn)程由于競(jìng)爭(zhēng)資源而造成的一種互相等待的現(xiàn)象（僵局），如無(wú)外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。死鎖產(chǎn)生原因眾多進(jìn)程競(jìng)爭(zhēng)有限資源；進(jìn)程推進(jìn)順序不合適。死鎖產(chǎn)生的必要條件互斥

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

25、只允許按編號(hào)順序遞增地申請(qǐng)，破除環(huán)路待。（3）一個(gè)已占有資源的進(jìn)程,若要申請(qǐng)新的資源，必須先放棄已占有的資源，破壞請(qǐng)求保持條件。死鎖的避免每當(dāng)進(jìn)程申請(qǐng)資源時(shí)，都根據(jù)一定的算法判斷是否安全安全狀態(tài)：當(dāng)多個(gè)進(jìn)程動(dòng)態(tài)申請(qǐng)資源時(shí)，系統(tǒng)按某一順序逐次地為每個(gè)進(jìn)程分配所需資源，使每個(gè)進(jìn)程都可以在最終得到最大需求量后依次順利完成。不安全狀態(tài)：可能死鎖避免死鎖的關(guān)鍵：讓系統(tǒng)在動(dòng)態(tài)分配資源的過(guò)程中，不要進(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í)行期間每次訪問(wèn)內(nèi)存之前進(jìn)行重定位。這種變換是

27、靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。通常采用重定位寄存器，其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址，而地址空間中的代碼在裝入過(guò)程中不發(fā)生變化。靜態(tài)重定位：在目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的邏輯地址改成物理地址。對(duì)每個(gè)程序來(lái)說(shuō)，這種地址變換只是在裝入時(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)存開(kāi)始查找合適的hole分配可重定位分區(qū)分配：重定位寄存器(relocation register)、緊湊技術(shù)（把進(jìn)程統(tǒng)一移向一邊）（2） 基本分頁(yè)存儲(chǔ)管理方式(paging) 分頁(yè)引入：動(dòng)態(tài)分區(qū)方式產(chǎn)生“外碎片”，采用緊湊技術(shù)要付出很大開(kāi)銷，于是引入了頁(yè)式存儲(chǔ)管理。分頁(yè)定義A memory-managemen

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

30、輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，并將頁(yè)號(hào)與頁(yè)表寄存器中的頁(yè)表長(zhǎng)度比較，若頁(yè)號(hào)不小于頁(yè)表長(zhǎng)度，便產(chǎn)生越界中斷，否則以頁(yè)號(hào)為索引，去檢索頁(yè)表，從中得到該頁(yè)的物理塊號(hào)，送入物理地址寄存器與頁(yè)內(nèi)地址拼接，形成物理地址。快表(TLB-translation look-aside buffer)為了提高訪問(wèn)速度，存放被頻繁訪問(wèn)的頁(yè)面的頁(yè)表項(xiàng)。先查快表，沒(méi)有查到再查頁(yè)表?？毂砗苄?，訪問(wèn)很快，造價(jià)高。內(nèi)存訪問(wèn)時(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） 段頁(yè)式存儲(chǔ)管理方式對(duì)換技術(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)資源利用率提高.整體對(duì)換:以進(jìn)程為單位,進(jìn)程對(duì)換部分對(duì)換:頁(yè)面對(duì)換

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

33、址 基址寄存器內(nèi)容 <= 限長(zhǎng)寄存器內(nèi)容(3)分頁(yè)管理中在頁(yè)表中的每一項(xiàng)設(shè)置保護(hù)位CHAPTER 9VIRTUAL MEMORY虛擬內(nèi)存(virtual memory)具有請(qǐng)求調(diào)入功能和置換功能、能從邏輯上對(duì)內(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.請(qǐng)求分頁(yè)(demand paging)定義：基本分頁(yè)的基礎(chǔ)上增加請(qǐng)求調(diào)頁(yè)功能 和頁(yè)面置換功能。作業(yè)被調(diào)度投入運(yùn)行前，只裝入部分頁(yè)面到內(nèi)存，其他各頁(yè)，根據(jù)請(qǐng)求而被裝入。頁(yè)表增加以下內(nèi)容：存在位P、訪問(wèn)字段A、修改位M、外存地址。地址變換過(guò)程頁(yè)面置換算法(page replacement algorithm)l FIFO：換出去最老的一頁(yè)l 理想頁(yè)面置換算法OPT(optimal page replacement)：換出去在reference string中最遠(yuǎn)的頁(yè)，也就是未來(lái)最后才出現(xiàn)頁(yè)l 最久未使用算法LRU(least-recently-used)：換出去最久沒(méi)有被使用

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

36、不會(huì)使其它進(jìn)程也發(fā)生顛簸l 給進(jìn)程提供足夠的物理塊：根據(jù)進(jìn)程執(zhí)行的局部模型，來(lái)確定進(jìn)程真正需要多少物理塊l 一種更加直接的防止顛簸的方法是控制缺頁(yè)頻率（ Page-Fault Frequency ）工作集模型(working-set model)：用參數(shù)定義一個(gè)工作集窗口，如果工作集窗口中的頁(yè)面不再活躍，移動(dòng)工作集。預(yù)調(diào)頁(yè)(prepaging):當(dāng)一個(gè)新進(jìn)程開(kāi)始進(jìn)入內(nèi)存時(shí)，會(huì)發(fā)生很多缺頁(yè)中斷?？梢允褂霉ぷ骷Ｐ?，在掛起一個(gè)進(jìn)程時(shí)記錄下工作集，然后resume時(shí)先調(diào)入工作集里所有的頁(yè)。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): 用戶通過(guò)文件系統(tǒng)提供的系統(tǒng)調(diào)用實(shí)施文件的操作l 創(chuàng)建文件：分配磁盤(pán)空間，創(chuàng)建文件目錄入口l 寫(xiě)文件：從目錄中找到文件地址，置寫(xiě)指針l 讀文件：在文件目錄中找到文件入口，置讀

38、指針l 文件指針重定位(repositioning within a file)l 刪除文件：在目錄中找到文件，釋放磁盤(pán)空間，刪除文件目錄信息l 刪除文件內(nèi)容(truncating a file)文件的邏輯結(jié)構(gòu)(file structure)分為有結(jié)構(gòu)文件（記錄式文件）、無(wú)結(jié)構(gòu)文件（流式文件）。記錄式文件：順序文件：記錄通常是定長(zhǎng)的，順序存取；索引文件：記錄通常是變長(zhǎng)的，方便直接存??；索引順序文件：前二者的結(jié)合，減少了索引表所占的空間文件的訪問(wèn)方式(access method)順序訪問(wèn)（磁帶模型）/隨機(jī)訪問(wèn)（磁盤(pán)模型）/索引表訪問(wèn)目錄(directory)：即文件夾,是用來(lái)記錄每個(gè)文件在磁盤(pán)上

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

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

41、控制表(access control list),列出不同用戶對(duì)該文件或者目錄的訪問(wèn)權(quán)限.當(dāng)用戶請(qǐng)求訪問(wèn)一個(gè)文件時(shí),OS首先檢查其訪問(wèn)控制表,看該用戶有無(wú)相應(yīng)的訪問(wèn)權(quán)限.文件共享/此處的復(fù)習(xí)PPT同樣不知道在說(shuō)什么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）文件控制表：與文件一一對(duì)應(yīng)。其基本的內(nèi)容包括文件名、文件的物理地址、文件的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、文件的長(zhǎng)度、存取權(quán)限、文件的建立日期、修改日期及時(shí)間、連接計(jì)數(shù)文件主標(biāo)識(shí)符等。文件的物理結(jié)構(gòu)（文件在磁盤(pán)上的分配方式）l 連續(xù)分配Contiguous allocation方法：每個(gè)文件在磁盤(pán)上占據(jù)一片連續(xù)的blocks優(yōu)點(diǎn)：簡(jiǎn)單、順序訪問(wèn)速度快、支持隨機(jī)存取缺點(diǎn)：外碎片、空間利用率低、不利于文件的動(dòng)態(tài)增長(zhǎng)l 鏈接分配Linked allocationa) 隱式鏈接：一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通

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

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