第一章 概述操作系統(tǒng)的定義：是一個(gè)大型的程序系統(tǒng)，它負(fù)責(zé)計(jì)算機(jī)的全部軟硬件資源的分配，調(diào)度工作，控制并協(xié)調(diào)并發(fā)活動(dòng)，實(shí)現(xiàn)信息的存取及保護(hù)，它提供用戶接口，使用戶獲得更好的工作環(huán)境，操作系統(tǒng)使整個(gè)計(jì)算機(jī)實(shí)現(xiàn)了高效率及高度自動(dòng)化。操作系統(tǒng)屬于應(yīng)用軟件。操作系統(tǒng)的基本功能1）人-機(jī)交互界面：用戶可直接使用鍵盤命令或Shell命令語(yǔ)言，調(diào)用操作系統(tǒng)內(nèi)部功能模塊（系統(tǒng)調(diào)用）2）資源管理：文件管理、存儲(chǔ)管理、設(shè)備管理、處理器管理、作業(yè)管理操作系統(tǒng)的分類1）單用戶操作系統(tǒng)：一個(gè)用戶獨(dú)占計(jì)算機(jī)系統(tǒng)資源，系統(tǒng)所有軟硬件資源全為一個(gè)用戶服務(wù)，單獨(dú)地執(zhí)行該用戶提交的一個(gè)任務(wù)；優(yōu)點(diǎn)：操作系統(tǒng)簡(jiǎn)單，易被人們掌握；缺點(diǎn)：系統(tǒng)資源未能充分利用；2）批處理操作系統(tǒng)：采用批量化處理作業(yè)技術(shù)的操作系統(tǒng)單道批處理系統(tǒng)多道批處理系統(tǒng)二者區(qū)別：?jiǎn)蔚蓝嗟纼?nèi)存使用每次一個(gè)作業(yè)每次多個(gè)作業(yè)（充分利用內(nèi)存）作業(yè)次序順序，先進(jìn)先出無(wú)確定次序共同特征 用戶與他的作業(yè)之間沒(méi)有交互作用，不能直接控制其作業(yè)的運(yùn)行；作業(yè)成批處理；多道程序執(zhí)行自動(dòng)化，充分利用系統(tǒng)資源。（3）實(shí)時(shí)操作系統(tǒng)：對(duì)隨機(jī)發(fā)生的外部事件能做出及時(shí)的響應(yīng)并對(duì)其進(jìn)行處理的操作系統(tǒng)特點(diǎn)：a.較少有人為干預(yù)的監(jiān)督和控制系統(tǒng)；b.軟件依賴于應(yīng)用的性質(zhì)和實(shí)際使用的計(jì)算機(jī)類型；c.專用系統(tǒng)：許多實(shí)時(shí)系統(tǒng)是專用系統(tǒng)。d.實(shí)時(shí)控制：實(shí)時(shí)系統(tǒng)用于控制實(shí)時(shí)過(guò)程，要求對(duì)外部事件的迅速響應(yīng)，具有較強(qiáng)的中斷處理機(jī)構(gòu)。e. 高可靠性：實(shí)時(shí)系統(tǒng)用于控制重要過(guò)程，要求高度可靠，具有較高冗余。如雙機(jī)系統(tǒng)。f.事件驅(qū)動(dòng)和隊(duì)列驅(qū)動(dòng)：實(shí)時(shí)系統(tǒng)的工作方式：接受外部消息，分析消息，調(diào)用相應(yīng)處理程序進(jìn)行處理。g.可與通用系統(tǒng)結(jié)合成通用實(shí)時(shí)系統(tǒng)：實(shí)時(shí)處理前臺(tái)作業(yè)，批處理為后臺(tái)作業(yè)。應(yīng)用：監(jiān)督生產(chǎn)線，流水線生產(chǎn)的連續(xù)過(guò)程，監(jiān)督病人的臨界功能，監(jiān)督和控制交通燈系統(tǒng)，監(jiān)督和控制實(shí)驗(yàn)室的實(shí)驗(yàn)，監(jiān)督軍用飛機(jī)的狀態(tài)等；（4）分時(shí)操作系統(tǒng)：多個(gè)用戶分享使用同一臺(tái)計(jì)算機(jī)，把計(jì)算機(jī)的系統(tǒng)資源進(jìn)行時(shí)間上的分割，即將整個(gè)工作時(shí)間分成一個(gè)個(gè)的時(shí)間段，每個(gè)時(shí)間段稱為一個(gè)時(shí)間片；特點(diǎn)：a.同時(shí)性：若干個(gè)終端用戶可以同時(shí)使用計(jì)算機(jī),共享系統(tǒng)資源，提高了資源利用率；獨(dú)立性：用戶彼此獨(dú)立，互不干擾；及時(shí)性：用戶的請(qǐng)求能在較短的時(shí)間內(nèi)得到響應(yīng)；交互性：用戶能進(jìn)行人機(jī)對(duì)話，聯(lián)機(jī)地調(diào)試程序，以交互方式工作，加快了調(diào)試時(shí)間；5）網(wǎng)絡(luò)操作系統(tǒng)：提供網(wǎng)絡(luò)通信和網(wǎng)絡(luò)資源共享功能的操作系統(tǒng)特點(diǎn)：a.系統(tǒng)中任意兩臺(tái)計(jì)算機(jī)可以通過(guò)通信來(lái)交換信息系統(tǒng)中各臺(tái)計(jì)算機(jī)五主次之分系統(tǒng)的資源為所有用戶所共享系統(tǒng)中若干臺(tái)計(jì)算機(jī)可以互相協(xié)作來(lái)完成一個(gè)共同任務(wù)功能：處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理、文件管理，提供高效、可靠的網(wǎng)絡(luò)通信能力，提供多種網(wǎng)絡(luò)服務(wù)功能分布式操作系統(tǒng)是一種特殊的網(wǎng)絡(luò)操作系統(tǒng)處理器狀態(tài)，特權(quán)非特權(quán)指令，程序狀態(tài)字（1）處理器狀態(tài)a.管態(tài)：操作系統(tǒng)管理程序運(yùn)行的狀態(tài)；b.目態(tài)：用戶程序運(yùn)行的狀態(tài)；（2）指令a.特權(quán)指令：操作系統(tǒng)中只能由操作系統(tǒng)使用的指令,控制中斷屏蔽的某些指令，清主存指令，建立存儲(chǔ)保護(hù)指令等等。b.非特權(quán)指令：操作系統(tǒng)和用戶都可以使用的指令說(shuō)明：當(dāng)處理器處于管態(tài)時(shí)，可以執(zhí)行全部的指令（包括特權(quán)指令），使用所有資源，并具有改變處理器狀態(tài)的能力，當(dāng)處理器處于目態(tài)時(shí)，就只能執(zhí)行非特權(quán)指令。（4）程序狀態(tài)字：用來(lái)指示處理器狀態(tài)，控制指令執(zhí)行順序，并且保留和指示與相應(yīng)程序有關(guān)的系統(tǒng)狀態(tài)第二章 處理器管理多道程序并發(fā)執(zhí)行的特點(diǎn)1）程序執(zhí)行時(shí)的資源共享性；2）程序失去了封閉性和可再現(xiàn)性；3）并發(fā)程序之間的相互制約性；3.進(jìn)程1）進(jìn)程的定義：進(jìn)程是能和其他程序并發(fā)執(zhí)行的程序段在某數(shù)據(jù)集合上的一次運(yùn)行過(guò)程，它是系統(tǒng)資源分配和調(diào)度的一個(gè)獨(dú)立單位；☆（2）進(jìn)程與程序間的區(qū)別：a.程序是一組指令的集合，它只規(guī)定了運(yùn)行活動(dòng)時(shí)所要完成的功能，本身沒(méi)有運(yùn)行的含義，因此程序是靜態(tài)的概念，而進(jìn)程是一段程序的一次運(yùn)行活動(dòng)，它的著眼點(diǎn)是活動(dòng)，運(yùn)行，過(guò)程，因此進(jìn)程是動(dòng)態(tài)概念；b.進(jìn)程是一個(gè)獨(dú)立調(diào)度并能和其他進(jìn)程并行運(yùn)行的單位，而程序通常不能作為獨(dú)立調(diào)度進(jìn)行的單位；C.一個(gè)程序運(yùn)行在兩個(gè)不同數(shù)據(jù)集合上，就是兩個(gè)不同的進(jìn)程，因此進(jìn)程和程序不存在一一對(duì)應(yīng)關(guān)系，一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程，反之，一個(gè)進(jìn)程至少要對(duì)應(yīng)一個(gè)程序，或?qū)?yīng)多個(gè)程序，多個(gè)進(jìn)程也可以對(duì)應(yīng)相同的程序；3）進(jìn)程的組成：a.程序b.數(shù)據(jù)集合c.進(jìn)程控制塊（PCB）4）進(jìn)程的三種基本狀態(tài)：(P48習(xí)題2.4)a.就緒狀態(tài)：進(jìn)程已得到除CPU以外的全部資源，是一旦獲得CPU就可以執(zhí)行的狀態(tài)；b.執(zhí)行狀態(tài)：進(jìn)程已獲得必要的資源并占有 CPU，正在執(zhí)行的狀態(tài)；阻塞狀態(tài)：進(jìn)程因等待某一事件而暫不能執(zhí)行的狀態(tài)；☆（5）進(jìn)程的三態(tài)轉(zhuǎn)換：資源滿足且獲得CPU就緒執(zhí)行時(shí)間片用完等待事件已發(fā)生等待事件發(fā)生阻塞6）進(jìn)程控制的任務(wù)：對(duì)系統(tǒng)中所有進(jìn)程從創(chuàng)建到消亡的全過(guò)程實(shí)行有效的管理和控制；7）原語(yǔ)：由若干條機(jī)器指令構(gòu)成的程序模塊，它是用于完成特定功能的一段程序.為了保證操作的正確性原語(yǔ)在執(zhí)行期間不可分割；（一旦開始執(zhí)行，直到完畢之前，是不允許中斷的）8）進(jìn)程控制原語(yǔ)：a.創(chuàng)建原語(yǔ)b.撤銷原語(yǔ)c.阻塞原語(yǔ)d.喚醒原語(yǔ)進(jìn)程調(diào)度1）進(jìn)程調(diào)度的概念：系統(tǒng)按照一定算法把CPU動(dòng)態(tài)分配給就緒隊(duì)列中的某個(gè)進(jìn)程，并使之執(zhí)行（在批處理系統(tǒng)中）；2）進(jìn)程調(diào)度的層次：a.高級(jí)調(diào)度：按照某種原則從外存上的后備作業(yè)中選一個(gè)或幾個(gè)進(jìn)入內(nèi)存， 并為其運(yùn)行做好有關(guān)準(zhǔn)備工作；b.中級(jí)調(diào)度：負(fù)責(zé)內(nèi)外存之間的進(jìn)程對(duì)換，以解決內(nèi)存緊張問(wèn)題，即將內(nèi)存中處于等待狀態(tài)的某些進(jìn)程調(diào)到外存對(duì)換區(qū)以騰出空間，再將外存對(duì)換區(qū)中已具備運(yùn)行條件的進(jìn)程重新調(diào)入內(nèi)存準(zhǔn)備運(yùn)行；c.低級(jí)調(diào)度：決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理器， 并實(shí)際執(zhí)行將處理器分配給該進(jìn)程的工作（批處理系統(tǒng)和分時(shí)系統(tǒng)都必須配備） ；（3）進(jìn)程調(diào)度的功能：a.保護(hù)當(dāng)前正在執(zhí)行的進(jìn)程的現(xiàn)場(chǎng)，將程序狀態(tài)寄存器，指令計(jì)數(shù)器及所有通用寄存器的內(nèi)容放到特定單元保存起來(lái)；b.查詢，登記和更新進(jìn)程控制表 PCB中的相應(yīng)表項(xiàng)，根據(jù)表項(xiàng)中的內(nèi)容和狀態(tài)，按一定的算法，從就緒進(jìn)程中選擇一個(gè)，并把 CPU分給它；c.恢復(fù)被調(diào)度到的進(jìn)程的原來(lái)現(xiàn)場(chǎng)，從而使它按上次放棄 CPU時(shí)的狀態(tài)繼續(xù)運(yùn)行；4）進(jìn)程調(diào)度的方式：a.剝奪（搶占）式b.非剝奪（搶占）式5）進(jìn)程調(diào)度的常用算法：☆時(shí)間片輪轉(zhuǎn)法（剝奪式）：把CPU按時(shí)間片，按順序賦予就緒隊(duì)列中的每一個(gè)進(jìn)程，即就緒隊(duì)列中各進(jìn)程輪流占用CPU執(zhí)行一定時(shí)間，若某個(gè)進(jìn)程在規(guī)定時(shí)間片內(nèi)未執(zhí)行完畢，也必須釋放CPU，并把CPU分配給下一個(gè)進(jìn)程；☆優(yōu)先級(jí)調(diào)度：把處理器分配給就緒隊(duì)列中具有最高優(yōu)先級(jí)的進(jìn)程；a.靜態(tài)優(yōu)先級(jí)：在進(jìn)程創(chuàng)建時(shí)即被確定，在以后執(zhí)行的過(guò)程中不在改變（確定依據(jù)：進(jìn)程類型，進(jìn)程對(duì)資源的需求，用戶要求的優(yōu)先級(jí)）；b.動(dòng)態(tài)優(yōu)先級(jí):在進(jìn)程的執(zhí)行期間按某種原則不斷修改進(jìn)程的優(yōu)先級(jí)，優(yōu)先級(jí)一般素進(jìn)程的等待時(shí)間，占用CPU的時(shí)間的變化而變化?！疃嘀仃?duì)列輪轉(zhuǎn)法：把時(shí)間片輪轉(zhuǎn)法中的單就緒隊(duì)列改為雙就緒隊(duì)列或多就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先權(quán)；（特點(diǎn)：先來(lái)先服務(wù)；獲得CPU的優(yōu)先權(quán)按序數(shù)上升而遞減，而時(shí)間片的長(zhǎng)度按序數(shù)上升而遞增；CPU）；線程（1）線程的定義：線程是進(jìn)程中的一個(gè)實(shí)體，它是比進(jìn)程更小的能夠獨(dú)立運(yùn)行的基本單位；2）引入線程的意義：為了減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使操作系統(tǒng)具有更好的開發(fā)性；(P48習(xí)題2.9)☆（3）線程與進(jìn)程的區(qū)別：a.線程是進(jìn)程的一部分，它是進(jìn)程的一個(gè)執(zhí)行單元，通常，一個(gè)進(jìn)程含有若干線程，至少要有一個(gè)線程，一個(gè)進(jìn)程的多個(gè)線程都在進(jìn)程的地址空間里活動(dòng)；b.在引入線程的操作系統(tǒng)中，資源分配的對(duì)象是進(jìn)程，而不是線程，進(jìn)程仍是擁有資源的一個(gè)獨(dú)立單位，它擁有自己的資源，一般而言，線程除有少量必不可少的資源外不擁有系統(tǒng)資源，線程使用的資源是進(jìn)程分到的資源；c.在引入線程的操作系統(tǒng)中，調(diào)度的基本單位是線程而不是進(jìn)程；d.進(jìn)程之間可以并發(fā)執(zhí)行，而一個(gè)進(jìn)程中的每個(gè)線程之間亦可以并發(fā)執(zhí)行，而且在并發(fā)執(zhí)行過(guò)程中，也需要協(xié)作同步；第三章 存儲(chǔ)管理存儲(chǔ)管理1）存儲(chǔ)管理的功能：a.存儲(chǔ)空間的分配和回收b.地址映射和重定位c.存儲(chǔ)共享和保護(hù)d.主存擴(kuò)充2）存儲(chǔ)分配的三種方式a.直接存儲(chǔ)分配方式：在程序設(shè)計(jì)過(guò)程中，或匯編程序?qū)υ闯绦蜻M(jìn)行編譯時(shí)，所用的是實(shí)際物理地址，以確保各程序所用的地址之間互不重疊；b.靜態(tài)存儲(chǔ)分配方式：編寫程序或由編譯系統(tǒng)產(chǎn)生的目標(biāo)程序中采用的地址空間為邏輯地址，當(dāng)連接裝入程序時(shí)對(duì)它們進(jìn)行裝入，連接時(shí)，才確定它們?cè)谥鞔嬷械南鄳?yīng)位置，從而產(chǎn)生可執(zhí)行程序，這種分配方式要求用戶在進(jìn)行裝入，連接時(shí)，系統(tǒng)必須分配其要求的全部存儲(chǔ)空間，若存儲(chǔ)空間不夠，則不能裝入該用戶程序，同時(shí)，用戶程序一旦裝入到主存空間后，它將一直占據(jù)著分配給它的存儲(chǔ)空間，直到程序結(jié)束時(shí)才釋放該空間，再者，在整個(gè)運(yùn)行過(guò)程中，用戶程序所占據(jù)的存儲(chǔ)空間是固定不變的，也不能動(dòng)態(tài)地申請(qǐng)存儲(chǔ)空間；c.動(dòng)態(tài)存儲(chǔ)分配方式：用戶程序在存儲(chǔ)空間中的位置也是在裝入時(shí)確定，但它不必一次性將整個(gè)程序裝入到主存，可根據(jù)執(zhí)行的需要，一部分一部分地動(dòng)態(tài)裝入，同時(shí)，裝入主存的程序不在執(zhí)行時(shí)，系統(tǒng)可以回收該程序所占據(jù)的主存空間，再者，用戶程序裝入主存后的位置，在運(yùn)行期間可根據(jù)系統(tǒng)需要而發(fā)生改變，此外，用戶程序在運(yùn)行期間也可動(dòng)態(tài)地申請(qǐng)存儲(chǔ)空間以滿足程序需求；重定位的定義、兩種重定位的特點(diǎn)與區(qū)別、覆蓋與交換1）重定義定義：由于用戶程序的裝入而引起地址空間中的相對(duì)地址轉(zhuǎn)換為存儲(chǔ)空間中的絕對(duì)地址的地址變換過(guò)程，稱為地址重定位，也稱地址映射；2）實(shí)現(xiàn)地址重定位的方法：靜態(tài)地址重定位，動(dòng)態(tài)地址重定位a.靜態(tài)地址重定位：用戶程序在裝入時(shí)由裝配程序一次完成，即地址變換只是在裝入時(shí)一次完成，以后不再改變；優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單；缺點(diǎn)：用戶程序必須分配一個(gè)連續(xù)的存儲(chǔ)空間；難以實(shí)現(xiàn)程序和數(shù)據(jù)的共享；b.動(dòng)態(tài)地址重定位：在程序執(zhí)行的過(guò)程中，當(dāng)CPU要對(duì)存儲(chǔ)器進(jìn)行訪問(wèn)時(shí)，通過(guò)硬件地址變換機(jī)構(gòu)（重定位寄存器BR和相對(duì)地址寄存器VR），將要訪問(wèn)的程序和數(shù)據(jù)地址轉(zhuǎn)換成主存地址；優(yōu)點(diǎn)：有利于提高主存的利用率和存儲(chǔ)空間使用的靈活性；有利于程序段的共享實(shí)現(xiàn)；為實(shí)現(xiàn)虛擬存儲(chǔ)器管理提供了基礎(chǔ)；缺點(diǎn)：實(shí)現(xiàn)存儲(chǔ)器管理的軟件比較復(fù)雜；需要附加的硬件支持；3）覆蓋與交換（從邏輯上擴(kuò)充主存,解決在較小主存空間中如何執(zhí)行大程序的問(wèn)題）a.覆蓋：把程序劃分為若干個(gè)功能相互獨(dú)立的程序段，并且讓那些不會(huì)同時(shí)被CPU執(zhí)行的程序段共享同一主存區(qū)，通常這些程序段被保存在外存中，當(dāng)CPU要求某一程序段執(zhí)行時(shí)，才將該程序段裝入主存來(lái)覆蓋以前的某一程序段；b.交換：將系統(tǒng)暫時(shí)不用的程序或數(shù)據(jù)部分部分或全部地從主存中調(diào)出，以騰出更大的存儲(chǔ)空間，同時(shí)將系統(tǒng)要求使用的程序和數(shù)據(jù)調(diào)入主存中，并將控制權(quán)轉(zhuǎn)交給它，讓其在系統(tǒng)上運(yùn)行；c.交換技術(shù)主要是在進(jìn)程或作業(yè)間進(jìn)行，覆蓋技術(shù)則主要是在同一個(gè)進(jìn)程或作業(yè)之間進(jìn)行，交換技術(shù)的運(yùn)用，可以在較小的存儲(chǔ)空間中運(yùn)行較多的作業(yè)或進(jìn)程，覆蓋技術(shù)的運(yùn)用，可以在較小的存儲(chǔ)空間中運(yùn)行比其容量大的作業(yè)或進(jìn)程；3.分區(qū)存儲(chǔ)管理、頁(yè)式存儲(chǔ)管理(各種方法采用的分配回收算法，數(shù)據(jù)結(jié)構(gòu)，地址變換過(guò)程，共享與保護(hù)，優(yōu)缺點(diǎn)比較）（1）分區(qū)存儲(chǔ)管理：將主存的用戶可用區(qū)域劃分成若干大小不等的區(qū)域，每一個(gè)進(jìn)程占據(jù)一個(gè)區(qū)域或多個(gè)區(qū)域，從而實(shí)現(xiàn)多道程序設(shè)計(jì)環(huán)境下各并發(fā)進(jìn)程共享主存空間；固定分區(qū)法：系統(tǒng)在初始化時(shí)，將主存空間劃分為若干個(gè)固定大小的區(qū)域，用戶程序在執(zhí)行過(guò)程中，不允許改變劃分區(qū)域的大小，只能夠根據(jù)各自的要求，由系統(tǒng)分配一個(gè)存儲(chǔ)區(qū)域；(P94習(xí)題3.5)數(shù)據(jù)結(jié)構(gòu)：分區(qū)說(shuō)明表動(dòng)態(tài)分區(qū)法：采用將主存的空閑區(qū)單獨(dú)構(gòu)成一個(gè)可用分區(qū)表或可用分區(qū)自由鏈表的形式來(lái)描述系統(tǒng)主存管理；(P94習(xí)題3.6)①分配方法：a.最先適應(yīng)法：將作業(yè)分配到主存的第一個(gè)足夠裝入它的可用空閑區(qū)中；b.最佳適應(yīng)法：將作業(yè)分配到主存中與它所需大小最接近的一個(gè)可用空閑區(qū)中；（要求分區(qū)表或自由鏈接表按照空閑區(qū)從小到大的次序排列）c.最壞適應(yīng)法：將作業(yè)分配到主存中最大的空閑區(qū)中； （要求分區(qū)表或自由鏈接表按照空閑區(qū)從大到小的次序排列）②回收方法：a.釋放區(qū)與上下兩個(gè)空閑區(qū)相鄰，在這種情況下，將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)；b.釋放區(qū)與上空閑區(qū)相鄰，在這種情況下，將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)；c.釋放區(qū)與下空閑區(qū)相鄰，在這種情況下，將釋放區(qū)與下空閑區(qū)合并為一個(gè)空閑區(qū)；d.釋放區(qū)與上下兩個(gè)空閑區(qū)都不相鄰，在這種情況下，釋放區(qū)作為一個(gè)新的空閑可用區(qū)插入到可用分區(qū)表或自由鏈表中；③數(shù)據(jù)結(jié)構(gòu)：可用分區(qū)表或可用分區(qū)自由鏈表；④地址變換過(guò)程：采用動(dòng)態(tài)重定位裝入作業(yè)，當(dāng)作業(yè)執(zhí)行時(shí)由硬件地址轉(zhuǎn)換機(jī)構(gòu)完成地址轉(zhuǎn)換（基址寄存器，限長(zhǎng)寄存器）；⑤分區(qū)共享：各道作業(yè)的共享存儲(chǔ)區(qū)域部分有相同的基址/限長(zhǎng)值，就可實(shí)現(xiàn)分區(qū)共享；⑥分區(qū)保護(hù)：對(duì)共享區(qū)的信息規(guī)定只能執(zhí)行或讀出，不能寫入；⑦分區(qū)存儲(chǔ)管理的優(yōu)缺點(diǎn)：a.優(yōu)點(diǎn)：實(shí)現(xiàn)了多道程序的設(shè)計(jì)，從而提高了系統(tǒng)資源的利用率；系統(tǒng)要求的硬件支持少，管理簡(jiǎn)單，實(shí)現(xiàn)容易；b.缺點(diǎn)：由于作業(yè)在裝入時(shí)的連續(xù)性，導(dǎo)致主存利用率不高；主存的擴(kuò)充只能采用覆蓋和交換技術(shù)，無(wú)法真正實(shí)現(xiàn)存儲(chǔ)器；2）頁(yè)式存儲(chǔ)管理：頁(yè)式存儲(chǔ)器管理取消了存儲(chǔ)分配的連續(xù)性，它能夠?qū)⒂脩暨M(jìn)程分配到不連續(xù)的存儲(chǔ)單元中連續(xù)執(zhí)行；（根據(jù)作業(yè)裝入主存的時(shí)機(jī)不同，一般分為：1，靜態(tài)分頁(yè)管理2，虛擬分頁(yè)管理）分頁(yè)存儲(chǔ)器的邏輯地址格式：頁(yè)號(hào) 單元號(hào)分配的考慮：將進(jìn)程的頁(yè)分配到主存的塊中?！れo態(tài)分頁(yè)管理：用戶作業(yè)在開始執(zhí)行以前，將該作業(yè)的程序和數(shù)據(jù)全部裝入到主存中，然后，操作系統(tǒng)通過(guò)頁(yè)表和硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，從而執(zhí)行用戶程序；①分配回收算法：依據(jù)存儲(chǔ)頁(yè)框表，請(qǐng)求表和頁(yè)表實(shí)現(xiàn)；②地址變換：首先用戶作業(yè)提出存儲(chǔ)分配的要求，此時(shí)操作系統(tǒng)根據(jù)主存頁(yè)框的大小將進(jìn)程要求的存儲(chǔ)空間分成相應(yīng)的頁(yè)面；根據(jù)主存的實(shí)際情況，將進(jìn)程的每個(gè)頁(yè)面分配到主存頁(yè)框中，系統(tǒng)分配并設(shè)置頁(yè)表的內(nèi)容，此時(shí)，系統(tǒng)完成用戶進(jìn)程的存儲(chǔ)器分配；當(dāng)用戶進(jìn)程開始執(zhí)行時(shí)，系統(tǒng)首先設(shè)置控制寄存器的內(nèi)容，控制寄存器包括頁(yè)表長(zhǎng)度和頁(yè)表起始地址兩項(xiàng)；為了對(duì)邏輯地址進(jìn)行變換，由硬件組成的地址變換機(jī)構(gòu)必須將其分成兩部分—頁(yè)號(hào)和頁(yè)內(nèi)偏移；根據(jù)邏輯地址中頁(yè)號(hào)在頁(yè)表中找到相應(yīng)的頁(yè)框號(hào)；將頁(yè)表中的頁(yè)框號(hào)和邏輯地址中的頁(yè)內(nèi)偏移分別寫入絕對(duì)地址中的相應(yīng)位置上；然后根絕絕對(duì)地址提供的頁(yè)框號(hào)和頁(yè)內(nèi)偏移計(jì)算出存儲(chǔ)空間的物理地址，用戶進(jìn)程可以訪問(wèn)主存中的絕對(duì)地址，取出數(shù)據(jù)或取出指令執(zhí)行；③快表：存放在高速緩沖存儲(chǔ)器中的頁(yè)表（引入快表時(shí)為了減少訪問(wèn)主存的次數(shù)提高地址變換的速度）；④加入快表后的地址轉(zhuǎn)換： CPU在給出邏輯地址后，地址變換機(jī)構(gòu)首先根據(jù)頁(yè)號(hào)在快表中進(jìn)行檢索，若存在相應(yīng)的頁(yè)號(hào)，則直接從快表中讀出該頁(yè)號(hào)對(duì)應(yīng)的頁(yè)框號(hào)，形成物理地址，否則需要訪問(wèn)主存中的頁(yè)表，從頁(yè)表中讀出相應(yīng)的頁(yè)框號(hào)，形成相應(yīng)的頁(yè)框號(hào)，形成物理地址，同時(shí)將找到的頁(yè)表登記到快表中， 當(dāng)塊表填滿后，又要在快表中登記一新的頁(yè)表項(xiàng)時(shí)，則需要一定的淘汰策略；⑤數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)頁(yè)框表，請(qǐng)求表和頁(yè)表等⑥共享：能方便地實(shí)現(xiàn)多個(gè)作業(yè)共享程序和數(shù)據(jù)，頁(yè)的共享可大大提高主存空間的利用率；在頁(yè)式存儲(chǔ)器中實(shí)現(xiàn)程序共享時(shí)，必須對(duì)共享程序給出相同的頁(yè)號(hào)；⑦保護(hù)：a.保護(hù)權(quán)限域 b. 保護(hù)鍵⑧優(yōu)點(diǎn)與缺點(diǎn)：優(yōu)點(diǎn)：解決了分區(qū)管理時(shí)的碎片問(wèn)題；缺點(diǎn)：仍受主存中可用頁(yè)框數(shù)的限制；虛擬存儲(chǔ)器基本思想，虛擬頁(yè)式存儲(chǔ)工作原理虛擬存儲(chǔ)器基本思想：當(dāng)用戶作業(yè)要求的存儲(chǔ)空間很大，不能被裝入主存時(shí)，基于局部性原理，系統(tǒng)可以把當(dāng)前要用的程序和數(shù)據(jù)裝入主存中啟動(dòng)程序運(yùn)行，而暫時(shí)不用的程序和數(shù)據(jù)駐留在外存中，在執(zhí)行中需要用到不在主存中的信息時(shí)，通過(guò)系統(tǒng)的調(diào)入調(diào)出功能和置換功能將暫時(shí)不用的程序和數(shù)據(jù)調(diào)出主存，騰出主存空間讓系統(tǒng)調(diào)入要用的程序和數(shù)據(jù)，這樣，系統(tǒng)便能很好地運(yùn)行用戶作業(yè)了，從用戶角度看，系統(tǒng)具備了比實(shí)際主存容量大得多的存儲(chǔ)器；虛擬存儲(chǔ)器的特征：多次性；對(duì)換性；離散性；虛擬性。*局部性原理：a.時(shí)間局限性：如果程序中某一條指令一旦執(zhí)行，則在不久以后還可能被繼續(xù)執(zhí)行，同樣，某一個(gè)數(shù)據(jù)被訪問(wèn)后，還可能被繼續(xù)訪問(wèn)；b.空間局限性：如果程序訪問(wèn)了某一存儲(chǔ)單元，其附近的存儲(chǔ)單元?jiǎng)t在不久也會(huì)被訪問(wèn)；虛擬存儲(chǔ)器的容量不可以大于主存容量加外存容量；（2）頁(yè)式虛擬存儲(chǔ)工作原理分頁(yè)存儲(chǔ)管理優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：1）解決主存的零頭問(wèn)題，能有效地利用主存。2）方便多道程序設(shè)計(jì)，并且程序運(yùn)行的道數(shù)增加了。3）可提供大容量的虛擬存儲(chǔ)器，作業(yè)的地址空間不再受實(shí)際主存大小的限制。4）更加方便了用戶，特別是大作業(yè)的用戶。當(dāng)某作業(yè)地址空間超過(guò)主存空間時(shí)，用戶也無(wú)需考慮覆蓋結(jié)構(gòu)。缺點(diǎn)：1）要有相應(yīng)的硬件支持，如需要?jiǎng)討B(tài)地址變換機(jī)構(gòu)、缺頁(yè)中斷處理機(jī)構(gòu)等。2）必須提供相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)管理存儲(chǔ)器，它們不僅占用了部分主存空間，同時(shí)還要花費(fèi)CPU時(shí)間。3）在分頁(yè)系統(tǒng)中頁(yè)內(nèi)的零頭問(wèn)題仍然存在。4）在請(qǐng)求分頁(yè)管理中，需要進(jìn)行缺頁(yè)中斷處理，還有可能出現(xiàn)抖動(dòng)現(xiàn)象，增加了系統(tǒng)開銷，降低系統(tǒng)效率。分頁(yè)式缺點(diǎn)（除上述的缺點(diǎn)外還有）：1）程序的邏輯地址空間是連續(xù)的，裝配好的程序段和數(shù)據(jù)塊的存儲(chǔ)空間是確定的，在執(zhí)行中是無(wú)法動(dòng)態(tài)增長(zhǎng)和收縮。2）無(wú)法做到頁(yè)與邏輯意義完整的子程序或數(shù)據(jù)段的唯一對(duì)應(yīng)，增大了其信息共享實(shí)現(xiàn)的難度。3）從連接的角度上看，分區(qū)管理和分頁(yè)管理只能采用靜態(tài)連接，不僅花費(fèi)了大量的CPU時(shí)間，而且也浪費(fèi)了許多主存空間。二級(jí)頁(yè)表的地址變換:三次訪問(wèn)主存:一次訪問(wèn)頁(yè)目錄，一次訪問(wèn)頁(yè)表，最后才訪問(wèn)數(shù)據(jù)所在的物理地址。5.常用的頁(yè)面置換算法(P95習(xí)題3.22)1）優(yōu)化算法（OPT）：這是一種理論化的算法，其所選擇的被淘汰的頁(yè)將是永不使用的頁(yè)，或者是在最長(zhǎng)時(shí)間內(nèi)不再訪問(wèn)的頁(yè)。2）先進(jìn)先出算法（FIFO）：該算法總是淘汰最先進(jìn)入主存的頁(yè)面，認(rèn)為最先調(diào)入的頁(yè)最近不被訪問(wèn)可能性最大。缺頁(yè)率=缺頁(yè)次數(shù)/總的訪問(wèn)次數(shù)*100%用FIFO算法求缺頁(yè)率：123412512345111444555555222111113333332222244FFFFFFFSSFFS缺頁(yè)率=9/12*100%=75%Belady現(xiàn)象：一般情況下，對(duì)于一個(gè)作業(yè)如果分配給它的主存頁(yè)框越多，缺頁(yè)中斷率就越低，反之就越高，但對(duì)于FIFO算法來(lái)說(shuō)，在未給作業(yè)分配足夠滿足它要求的頁(yè)面時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)框數(shù)增多，而缺頁(yè)中斷率反而增高的奇異現(xiàn)象；☆（3）最近最少用置換算法（LRU）：該算法要求淘汰的頁(yè)面是在最近一段時(shí)間里較久未被訪問(wèn)的那一頁(yè)。根據(jù)是程序執(zhí)行時(shí)所具有的局部性。為了比較準(zhǔn)確地淘汰最近最少使用的頁(yè)面，可以采用堆棧的方法來(lái)實(shí)現(xiàn)。棧中存放當(dāng)前主存中的頁(yè)號(hào)，每當(dāng)訪問(wèn)一頁(yè)時(shí)就調(diào)整一次棧。于是，發(fā)生缺頁(yè)中斷時(shí)總是淘汰棧底所指示的頁(yè)。4）最近未用置換算法（NRU）概念：該算法要求頁(yè)表中有一個(gè)訪問(wèn)位和一個(gè)修改位。當(dāng)某頁(yè)被訪問(wèn)時(shí)，訪問(wèn)位被自動(dòng)置1，若執(zhí)行的指令是寫指令，則修改位也被置1。系統(tǒng)周期性地將所有訪問(wèn)位置0。在選擇一頁(yè)淘汰時(shí)，總是選擇其訪問(wèn)位為 0且修改位也為0的頁(yè)。若無(wú)修改位為0的頁(yè)，就選訪問(wèn)位為 0且頁(yè)號(hào)最小的頁(yè)淘汰。評(píng)價(jià)：該算法不但希望淘汰的頁(yè)是最近未使用的頁(yè)，而且還希望被淘汰的頁(yè)是在主存駐留期間其頁(yè)面內(nèi)容未被修改過(guò)。系統(tǒng)對(duì)訪問(wèn)位清0的間隔時(shí)間T的確定是很關(guān)鍵的。如果間隔時(shí)間T太大，可能所有頁(yè)的訪問(wèn)位均已成為1，無(wú)法選擇淘汰的頁(yè)面。如果間隔時(shí)間T太小，則可能很多頁(yè)的訪問(wèn)位均是為0基于Clock的NRU算法過(guò)程：從指針位置開始掃描鏈表，掃描過(guò)程中不改變R位。淘汰遇到的第一個(gè)R＝0&M=0的頁(yè)面。若第1步失敗，則再次掃描，淘汰遇到的第一個(gè)R＝0&M＝1的頁(yè)面。每個(gè)頁(yè)面檢查過(guò)后將R設(shè)為0。若第2步失敗，重復(fù)1和2（如果需要）。5）最少使用置換算法（LFU）概念：要求為每一頁(yè)表項(xiàng)配置一個(gè)一定位數(shù)的計(jì)數(shù)器作為訪問(wèn)字段，開始時(shí)所有的計(jì)數(shù)器均為0。一旦某頁(yè)被訪問(wèn)時(shí)，其頁(yè)表項(xiàng)中的計(jì)數(shù)器值加1。系統(tǒng)每過(guò)一段時(shí)間T就將所有的頁(yè)表項(xiàng)計(jì)數(shù)器清0。在需要選擇一頁(yè)置換時(shí)，便比較各計(jì)數(shù)器的值，總是選擇其計(jì)數(shù)值最小的頁(yè)面淘汰。評(píng)價(jià)：該算法實(shí)現(xiàn)也較容易，但代價(jià)較高，而且合適的間隔時(shí)間T的選擇也是難題。6.段式存儲(chǔ)管理的思想，段式虛擬存儲(chǔ)管理流程1）段式存儲(chǔ)管理的思想：把程序按邏輯含義或過(guò)程分成段，每段都有自己的段名，用戶程序可用段名和入指出調(diào)用一個(gè)段的功能，程序在編譯或匯編時(shí)，再將段名定義一個(gè)段號(hào)，每段邏輯地址均是以0開始進(jìn)行順序編址，這樣用戶或進(jìn)程的地址空間就形成了一個(gè)二維線性地址空間，任意一個(gè)地址必須首先指出段號(hào)，其次指出段內(nèi)偏移地址，段式存儲(chǔ)管理程序以段為單位分配主存，然后，執(zhí)行時(shí)通過(guò)地址轉(zhuǎn)換機(jī)構(gòu)把段式邏輯地址轉(zhuǎn)換成主存物理地址；*在段式存儲(chǔ)器中實(shí)現(xiàn)程序共享時(shí)，共享段的段號(hào)不一定要相同；邏輯地址格式：段號(hào) 單元號(hào)段式管理信息共享和保護(hù) ：共享：只要用戶使用相同的共享段名，系統(tǒng)在建立段表時(shí)，只須在相應(yīng)的段表欄目上填入已在主存的段的始址和長(zhǎng)度，即可實(shí)現(xiàn)程序和數(shù)據(jù)段的共享，從而提高系統(tǒng)主存的利用率。保護(hù)：（1）在段表中增設(shè)一個(gè)存取權(quán)限域。存取權(quán)限可分為：只執(zhí)行（共享程序段）、只讀（共享數(shù)據(jù)段）和可讀/寫（私人段）。訪問(wèn)段時(shí)，核對(duì)存取權(quán)限。2）在地址轉(zhuǎn)換時(shí)，將段表中的長(zhǎng)度與段內(nèi)地址比較，實(shí)現(xiàn)地址越界保護(hù)。2）段式虛擬存儲(chǔ)管理實(shí)現(xiàn)原理基本思想 ：把作業(yè)的所有分段的副本都存放在外存上，當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，首先把當(dāng)前需要用的一段或幾段裝入主存，在執(zhí)行過(guò)程中，訪問(wèn)到不在主存的段時(shí)，再通過(guò)缺段中斷機(jī)構(gòu)把它從外存上調(diào)入。段式管理優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：嚴(yán)格按程序的邏輯結(jié)構(gòu)分配連續(xù)存儲(chǔ)空間，方便程序和數(shù)據(jù)的共享與保護(hù)，同時(shí)也便于程序及數(shù)據(jù)段的擴(kuò)充和動(dòng)態(tài)連接。缺點(diǎn)：一個(gè)段的長(zhǎng)度不能大于實(shí)際的主存容量，而且為了解決碎片問(wèn)題，提高主存的利用率，必須采用移動(dòng)技術(shù)，移動(dòng)主存信息需要較大的系統(tǒng)開銷。3）段頁(yè)式虛擬存儲(chǔ)管理基本思想：每個(gè)作業(yè)按邏輯分段，然后對(duì)每一段又分成若干頁(yè)。這樣，每一段不必占用連續(xù)的主存空間，而是按頁(yè)存放在不一定連續(xù)的主存頁(yè)框中，并且當(dāng)主存頁(yè)框不夠時(shí)只將一段的部分頁(yè)面放在主存，用到不在主存中的頁(yè)面時(shí)再將之調(diào)入。段頁(yè)式的邏輯地址格式：段號(hào) 頁(yè)號(hào) 單元號(hào)段頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：具有段式和頁(yè)式的全部?jī)?yōu)點(diǎn)缺點(diǎn)：需要更多的硬件支持和中斷處理，增加了系統(tǒng)的成本和復(fù)雜性 ?！罘侄闻c分頁(yè)比較分段是信息的邏輯單位，是用戶可見(jiàn)的，段的大小是用戶程序決定。而分頁(yè)是信息的物理單位，分頁(yè)對(duì)用戶來(lái)說(shuō)是不可見(jiàn)的，頁(yè)的大小是事先固定的。第四章 文件管理文件存取方法1）順序存取方法：嚴(yán)格按照數(shù)據(jù)記錄的排列順序依次存?。?）直接存取方法：允許用戶隨意讀寫文件的任意一個(gè)記錄，不管上次讀寫到哪個(gè)記錄；3）按鍵存取方法：根據(jù)文件中各記錄的內(nèi)容進(jìn)行存??；文件的邏輯結(jié)構(gòu)（文件邏輯組織）是指從用戶的觀點(diǎn)出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及結(jié)構(gòu)。方式有：順序文件、索引順序文件、索引文件和直接文件。選擇文件的邏輯結(jié)構(gòu)時(shí)的原則：檢索效率高、修改更正方便、維護(hù)操作簡(jiǎn)便、可靠性高、節(jié)省存儲(chǔ)空間，降低文件存儲(chǔ)費(fèi)用。目錄的組織與結(jié)構(gòu)1）目錄本身也是一種文件2）目錄包含信息：基本信息（文件名、文件類型、文件組織）文件的地址信息（卷、起始地址、文件使用大小、分配大?。┰L問(wèn)控制信息（文件的所有者、訪問(wèn)信息、許可的行為標(biāo)記）使用信息（文件建立日期、上一次讀日期、上一次讀用戶名、上一次修改日期、上一次修改用戶名、上一次備份日期、當(dāng)前文件活動(dòng)狀態(tài)）文件目錄的定義：為什么要引入：在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，都要存儲(chǔ)大量的文件。為了能對(duì)這些文件實(shí)施有效的管理，必須對(duì)它們加以妥善組織，這主要通過(guò)文件目錄實(shí)現(xiàn)。文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用。3）目錄結(jié)構(gòu)（特點(diǎn)、共享）a.一級(jí)目錄結(jié)構(gòu):這是最簡(jiǎn)單的目錄結(jié)構(gòu)。在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)，目錄項(xiàng)中含文件名、文件擴(kuò)展名、文件長(zhǎng)度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個(gè)目錄項(xiàng)是否空閑，又設(shè)置了一個(gè)狀態(tài)位。二級(jí)目錄結(jié)構(gòu)：為了克服單級(jí)目錄所存在的缺點(diǎn)，可以為每一個(gè)用戶建立一個(gè)單獨(dú)的用戶文件目錄UFD。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)再建立一個(gè)主文件目錄MFD；在主文件目錄中，每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，其目錄項(xiàng)中包括用戶名和指向該用戶目錄文件的指針。用戶名指向子目錄的Wang用戶目錄指針WangAlphaAlphaZhangTestTestGaoZhang用戶目錄ReportReportTestTestGao用戶目錄BetaBetaDeviceDeviceMisxMisx圖

4-3

兩級(jí)目錄結(jié)構(gòu)兩級(jí)目錄結(jié)構(gòu)基本上克服了單級(jí)目錄的缺點(diǎn)，不同的用戶目錄中，可以使用相同的文件名；

并具有以下優(yōu)點(diǎn)：提高了檢索目錄的速度；不同用戶還可使用不同的文件名來(lái)訪問(wèn)系統(tǒng)中

在同一個(gè)共享文件。樹形多級(jí)目錄結(jié)構(gòu)對(duì)于大型文件系統(tǒng)，通常采用三級(jí)或以上的目錄結(jié)構(gòu)，以提高對(duì)目錄的檢索速度和文件系統(tǒng)的性能。多級(jí)目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)， 主目錄在這里被稱為根目錄， 把數(shù)據(jù)文件稱為樹葉，其它的目錄均作為樹的結(jié)點(diǎn)。 圖示出了樹型目錄結(jié)構(gòu)。 圖中用方框代表目錄文件，圓圈代表數(shù)據(jù)文件。在該樹型目錄結(jié)構(gòu)中，根目錄中有三個(gè)用戶的總目錄項(xiàng) A、B和C。在B項(xiàng)所指出的 B用戶的總目錄 B中，又包括三個(gè)分目錄 F、E和D，其中每個(gè)分目錄中又包含多個(gè)文件。如B目錄中的F分目錄中，包含J和N兩個(gè)文件。為了提高文件系統(tǒng)的靈活性，應(yīng)允許在一個(gè)目錄文件中的目錄項(xiàng)既是作為目錄文件的 FCB，又是作為數(shù)據(jù)文件的 FCB，這一信息可用目錄項(xiàng)中的一位來(lái)指示。例如，在圖中，用戶 A的總目錄中，目錄項(xiàng) A是目錄文件的 FCB，而目錄項(xiàng) B和D則是數(shù)據(jù)文件的 FCB。如圖4-4所示：A B CA B D F E D G AA CJ N K J M K A H F圖4-4 樹型目錄結(jié)構(gòu)優(yōu)點(diǎn)：較好的反應(yīng)現(xiàn)實(shí)世界中具有層次關(guān)系的數(shù)據(jù)集合和較確切的反應(yīng)系統(tǒng)內(nèi)部文件的分支結(jié)構(gòu)。不同文件可以重名，只要不在同一末端的子目錄中；易于規(guī)定不同層次或子樹中文件的不同存取權(quán)限，便于文件的保護(hù)、保密和共享等文件可以重名，所以當(dāng)用戶進(jìn)程要訪問(wèn)多級(jí)目錄中的某個(gè)文件時(shí)，為了保證訪問(wèn)的唯一性，用戶在開始時(shí)必須使用該文件的“路徑名”來(lái)標(biāo)識(shí)文件。文件存儲(chǔ)空間管理(p116)（1）空閑表法（2）位示圖法（3）空閑鏈表法（4）成組鏈接法文件存儲(chǔ)空間分配(或文件分配)（p119）（1）連續(xù)分配（2）鏈接分配（隱式鏈接；顯示鏈接）（3）索引分配（一級(jí)索引鏈接分配；多級(jí)索引鏈接分配）文件共享的方法（1）基于索引節(jié)點(diǎn)的共享方式思想：對(duì)要共享的文件，引入一個(gè)索引節(jié)點(diǎn)，將文件中諸如文件的物理地址及其文件屬性等信息，不放在文件目錄表目中，而是放在索引節(jié)點(diǎn)中。在文件目錄中只設(shè)置文件名及其指向相應(yīng)索引節(jié)點(diǎn)的指針；A B CA B B B C CBC C？C C C圖4-5 包含有共享文件的文件系統(tǒng)優(yōu)點(diǎn)：文件的索引節(jié)點(diǎn)包括文件的物理地址及其他文件屬性等信息，這些內(nèi)容不放在目錄項(xiàng)中，文件目錄只設(shè)置文件名和指向索引節(jié)點(diǎn)的指針。用戶對(duì)文件的添加和修改只引起索引節(jié)點(diǎn)內(nèi)容的改變。對(duì)其他用戶是可見(jiàn)的，從而能提供給其他用戶共享缺點(diǎn)：索引節(jié)點(diǎn)中設(shè)有鏈接計(jì)數(shù)count，表示共享此文件的用戶數(shù)。當(dāng)count>1時(shí)，文件主刪除文件就會(huì)出現(xiàn)懸空指針，可能使其他用戶的操作半途而廢，若不刪除文件，文件必須為其他用戶的操作付費(fèi)（2）利用符號(hào)鏈接實(shí)現(xiàn)共享思想：為使能共享的一個(gè)文件夾，可由系統(tǒng)創(chuàng)建一個(gè)類型的新文件，也取名為，并將寫入的目錄中，以實(shí)現(xiàn)的目錄與文件的鏈接。 在新文件中只包含被鏈接文件的路徑名。 這樣的鏈接方法被稱為符號(hào)鏈接。 新文件中的路徑名， 只被看作是符號(hào)鏈， 當(dāng)要訪問(wèn)被鏈接的文件且正要讀類新文件時(shí)， 此要求將被截獲， 根據(jù)新文件中的路徑名去讀該文件， 于是就實(shí)現(xiàn)了用戶對(duì)文件的共享。在利用符號(hào)鏈方式實(shí)現(xiàn)文件共享時(shí)，只是文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其它用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。 這樣，這樣也就不會(huì)發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。 當(dāng)文件的擁有者把一個(gè)共享文件刪除后其他用戶試圖通過(guò)符號(hào)鏈去訪問(wèn)一個(gè)已被刪除的共享文件時(shí)， 會(huì)因系統(tǒng)找不到該文件而使訪問(wèn)失敗，于是再將符號(hào)鏈刪除，此時(shí)不會(huì)產(chǎn)生任何影響。優(yōu)點(diǎn)：能夠用于鏈接計(jì)算機(jī)網(wǎng)絡(luò)上的任何地點(diǎn)中的文件（

它能夠用于鏈接世界上任何地方機(jī)器中的文件）。缺點(diǎn)：訪問(wèn)共享文件時(shí)，可能需要多次訪盤，時(shí)間開銷較大，也要開銷一定磁盤空間；第五章 設(shè)備管理1、I/O設(shè)備的分類按設(shè)備的從屬關(guān)系分類：系統(tǒng)設(shè)備，用戶設(shè)備；按設(shè)備的共享關(guān)系分類：獨(dú)占設(shè)備，共享設(shè)備；按傳輸速率分類：低速設(shè)備，中速設(shè)備，高速設(shè)備；信息交換單位分類：字符設(shè)備，塊設(shè)備；2、設(shè)備控制器：I/O設(shè)備是由機(jī)械和電子兩個(gè)部分構(gòu)成的，設(shè)備控制器是設(shè)備中的電子部分，而機(jī)械部分是設(shè)備本身；設(shè)備控制器是CPU與I/O設(shè)備之間的接口，它接收從CPU發(fā)來(lái)的命令，并去控制I/O設(shè)備工作；①功能：a.接收和識(shí)別命令b.數(shù)據(jù)交換c.獲取設(shè)備的狀態(tài)d.地址識(shí)別②組成：a.設(shè)備控制器與處理機(jī)的接口b.I/O邏輯c.設(shè)備控制器與設(shè)備的接口字節(jié)多路通道數(shù)據(jù)選擇通數(shù)組多路通道3.DMA控制器與直接存儲(chǔ)器存取（1）DMA控制器道以成組方式傳送分時(shí)傳輸一個(gè)數(shù)據(jù)塊以字節(jié)為單位分時(shí)a傳.送組成：主機(jī)與DMA控制器的接口（命令/狀態(tài)寄存器，內(nèi)存地址寄存器，數(shù)據(jù)主要用于低速或 寄存器，數(shù)據(jù)計(jì)數(shù)器），DMA控制器與塊設(shè)備的接口；中速設(shè)備b.工作過(guò)程：參數(shù)準(zhǔn)備階段， DMA工作階段，結(jié)束中斷處理階段；2分）時(shí)直并接行操存作儲(chǔ)器存儲(chǔ)方式：通道一利種用率完低全由硬件執(zhí)行傳I/O輸速功率高能，的通工道作利方用率式高，引入的目的是為了實(shí)現(xiàn)高速大容量存儲(chǔ)器和主存之間的數(shù)據(jù)交換；特點(diǎn)：a.數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊；b.所傳送的數(shù)據(jù)是從設(shè)備直接送入內(nèi)存的，或者相反；c.僅在傳送一個(gè)或多個(gè)數(shù)據(jù)塊的開始和結(jié)束時(shí)，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在DMA控制器控制下完成的；優(yōu)點(diǎn)：速度快，CPU不參與傳送操作，節(jié)省了CPU時(shí)間；缺點(diǎn)：硬件線路比較復(fù)雜；通道方式：專門用來(lái)處理輸入輸出工作的處理器類型：（1）字節(jié)多路通道：以字節(jié)為傳輸單位，可以分時(shí)執(zhí)行多個(gè)通道程序。當(dāng)一個(gè)通道程序控制某臺(tái)設(shè)備傳送一個(gè)字節(jié)后，通道硬件就轉(zhuǎn)去執(zhí)行另一個(gè)通道程序，控制另一臺(tái)設(shè)備的數(shù)據(jù)傳輸。（2）數(shù)據(jù)選擇通道：一旦選中某臺(tái)設(shè)備，即由該設(shè)備獨(dú)占該通道，通道進(jìn)入忙狀態(tài)，直到該設(shè)備的數(shù)據(jù)傳輸工作全部結(jié)束，即通道程序執(zhí)行結(jié)束。（3）數(shù)組多路通道；結(jié)合了數(shù)據(jù)選擇通道傳遞速度高和字節(jié)多路通道能進(jìn)行分時(shí)并行操作的特點(diǎn)通道的類型5.DMA方式與通道方式的異同同：以內(nèi)存為中心，實(shí)現(xiàn)設(shè)備和內(nèi)存直接交換數(shù)據(jù)異：DMA中，數(shù)據(jù)傳輸方向、內(nèi)存始址、數(shù)據(jù)塊長(zhǎng)度都由CPU控制，通道方式中由通道控制；通道方式可做到一個(gè)通道控制多臺(tái)設(shè)備與內(nèi)存進(jìn)行數(shù)據(jù)交換。DMA方式時(shí)，每臺(tái)設(shè)備至少有一個(gè)DMA控制器。引入緩沖技術(shù)的原因：a.緩和CPU與I/O設(shè)備間的速度不匹配的矛盾b.提高CPU與I/O設(shè)備間的并行性c.便于進(jìn)程共享數(shù)據(jù)，減少系統(tǒng)設(shè)備輸入輸出壓力，即減少CPU的中斷頻率，放寬對(duì)中斷響應(yīng)時(shí)間的限制。緩沖技術(shù)是用來(lái)在不同速度的設(shè)備間傳送數(shù)據(jù)時(shí)平滑傳輸過(guò)程的常用手段設(shè)備的命名和獨(dú)占設(shè)備分配簡(jiǎn)單看看P152用戶進(jìn)程的I/O請(qǐng)求一般是以庫(kù)函數(shù)中的函數(shù)調(diào)用形式進(jìn)行的。磁盤結(jié)構(gòu)，性能參數(shù)，常用調(diào)度算法（FCFS,SSTF,SCAN,C-SCAN)重點(diǎn)（1）磁盤結(jié)構(gòu):磁道：磁盤每面上一系列記錄信息的同心圓。磁道間有空隙,把它們從0開始由外向內(nèi)順序編號(hào)柱面：不同盤面上具有相同編號(hào)的磁道形成柱面。扇區(qū)（物理紀(jì)錄）：每個(gè)磁道劃分出的若干個(gè)相等的扇形弧段。各扇區(qū)實(shí)際物理長(zhǎng)度不同。每個(gè)扇區(qū)存儲(chǔ)的信息量是相同的。要存儲(chǔ)信息到磁盤上，必須給出磁盤的： 柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)。（2）磁盤性能參數(shù)：（計(jì)算題）a.尋道時(shí)間:活動(dòng)磁頭將讀、寫磁頭移動(dòng)到相應(yīng)的磁道所花費(fèi)的時(shí)間。b.旋轉(zhuǎn)時(shí)間:讀、寫定位于某一磁道的扇區(qū)所需要的時(shí)間。c.傳送時(shí)間:數(shù)據(jù)寫入磁盤，或從此磁盤讀出的時(shí)間3）磁盤調(diào)度策略（P168習(xí)題5.21）a.先來(lái)先服務(wù)算法（FCFS）根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后順序進(jìn)行調(diào)度，而不管進(jìn)程的優(yōu)先級(jí)。優(yōu)點(diǎn)：公平，處理簡(jiǎn)單，每個(gè)進(jìn)程的請(qǐng)求都會(huì)得到處理。缺點(diǎn)：未對(duì)尋道進(jìn)行優(yōu)化，致使平均尋道時(shí)間可能較長(zhǎng)。b.最短尋道時(shí)間優(yōu)先算法（ SSTF）以申請(qǐng)者要求磁頭移動(dòng)距離大小作為優(yōu)先的因素，磁道距離磁頭當(dāng)前位置愈近者優(yōu)點(diǎn)：平均等待時(shí)間得到改善，可以獲得較好的尋道性能。缺點(diǎn)：對(duì)用戶進(jìn)程請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，可能導(dǎo)致某些進(jìn)程發(fā)生現(xiàn)象。

“餓死”c.掃描算法（SCAN，又稱電梯調(diào)度）不僅考慮申請(qǐng)者要求磁頭移動(dòng)方向，又考慮要求磁頭移動(dòng)距離，而且首先是方向一致，其次才是距離最短。優(yōu)點(diǎn)：避免了饑餓現(xiàn)象。缺點(diǎn)：優(yōu)待了中間磁道的請(qǐng)求（因?yàn)楸环?wù)者無(wú)方向需求） ，有“磁臂粘著”現(xiàn)象。d.循環(huán)掃描法（C-SCAN）規(guī)定磁頭單向移動(dòng)。將各磁道視作一個(gè)環(huán)形緩沖區(qū)結(jié)構(gòu)，最大磁道號(hào)和最小磁道號(hào)構(gòu)成循環(huán)。優(yōu)點(diǎn)：等待時(shí)間較均衡。缺點(diǎn)：有“磁臂粘著”現(xiàn)象虛擬設(shè)備，SPOOL系統(tǒng)組成與原理（P168習(xí)題5.22）1）在一臺(tái)共享設(shè)備上模擬若干臺(tái)獨(dú)占設(shè)備的操作，使每一臺(tái)獨(dú)占設(shè)備成為若干臺(tái)共享操作的虛擬設(shè)備，即把獨(dú)占設(shè)備變成邏輯上的共享設(shè)備，從而提高了設(shè)備利用率和系統(tǒng)的效率，這種技術(shù)稱為虛擬設(shè)備技術(shù)，實(shí)現(xiàn)這種技術(shù)的硬件和軟件系統(tǒng)被稱為SPOOL系統(tǒng)，使用SPOOL技術(shù)所提供的設(shè)備就成為虛擬設(shè)備；2）SPOOL系統(tǒng)組成：在共享設(shè)備中開辟存放輸入信息的輸入井和輸出信息的輸出井，在主存設(shè)置了兩個(gè)緩沖區(qū)，輸入緩沖區(qū)和輸出緩沖區(qū)；3）SPOOL系統(tǒng)工作原理：當(dāng)進(jìn)程有需求時(shí)，SPOOL接受它的需求，但并不立即處理，而是做兩件事，一是在共享設(shè)備的輸出井上由輸出進(jìn)程為其分配一塊存儲(chǔ)空間，并將其數(shù)據(jù)送入其中，并將該進(jìn)程的輸出數(shù)據(jù)建立一個(gè)文件，該進(jìn)程的數(shù)據(jù)實(shí)際上并未輸出，而只是以文件形式輸出，并暫時(shí)存放在SPOOL存儲(chǔ)區(qū)中，二是輸出進(jìn)程為用戶進(jìn)程申請(qǐng)一張空白的用戶請(qǐng)求表，并將用戶的需求填入其中，再將表掛到請(qǐng)求隊(duì)列中；(4)SPOOL系統(tǒng)的特點(diǎn)提高了I/O速度通過(guò)輸入井和輸出井實(shí)現(xiàn)I/O設(shè)備與主機(jī)的數(shù)據(jù)傳輸，緩和了CPU與低速I/O設(shè)備之間速度不匹配的矛盾。將獨(dú)占設(shè)備改造為共享設(shè)備并實(shí)現(xiàn)了虛擬設(shè)備的功能利用SPOOL系統(tǒng)，用戶進(jìn)程并未真正分得獨(dú)占設(shè)備，用戶進(jìn)程實(shí)際被分給的是共享設(shè)備中的一個(gè)存儲(chǔ)區(qū)（或文件），即虛擬設(shè)備。這樣，便把獨(dú)占設(shè)備改造為共享設(shè)備，獨(dú)占設(shè)備使用率提高了，從而導(dǎo)致系統(tǒng)效率提高了。第六章 進(jìn)程管理臨界區(qū)：并發(fā)進(jìn)程中與共享變量有關(guān)的程序段；對(duì)臨界區(qū)的管理應(yīng)滿足：a.互斥性：如果一個(gè)進(jìn)程在它的臨界區(qū)中執(zhí)行，其他任何進(jìn)程均不能進(jìn)入相關(guān)的臨界區(qū)執(zhí)行；b.進(jìn)展性：如果一個(gè)進(jìn)程不在它的臨界區(qū)中執(zhí)行，不應(yīng)阻止其他任何進(jìn)程進(jìn)入相關(guān)的臨界區(qū)執(zhí)行；c.有限等待性：某個(gè)進(jìn)程從申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限的時(shí)間內(nèi)得以進(jìn)入臨界區(qū)執(zhí)行；信號(hào)量：含有整形數(shù)據(jù)項(xiàng)的結(jié)構(gòu)變量物理意義：信號(hào)量整型值大于或等于零代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)；原語(yǔ)：執(zhí)行時(shí)不可中斷的過(guò)程；P操作P（s）：將信號(hào)量s的整型值減去1，若結(jié)果小于0，則將調(diào)用P（s）的進(jìn)程置成等待信號(hào)量s的狀態(tài)；V操作V（s）：將信號(hào)量s的整型值加上 1，若結(jié)果不大于0，則釋放一個(gè)等待信號(hào)量

s的進(jìn)程；4.用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥與同步 （P202習(xí)題6.9、6.10）1）用于控制進(jìn)程同步的信號(hào)量稱為私有信號(hào)量，用于控制進(jìn)程互斥的信號(hào)量稱為公有信號(hào)量；2）實(shí)現(xiàn)問(wèn)題三部曲：設(shè)置信號(hào)量；給信號(hào)量賦初值：互斥信號(hào)量初值賦為1，同步信號(hào)量初值隨題意而定；按照邏輯用P,V操作實(shí)現(xiàn)：P操作：先同步后互斥，V操作：沒(méi)有前后差別；直接通信：發(fā)送進(jìn)程直接把信件發(fā)送給接收進(jìn)程；間接通信：發(fā)送信件進(jìn)程不是把信件直接發(fā)送給接收進(jìn)程，而是把信件發(fā)送到一個(gè)共享的數(shù)據(jù)結(jié)構(gòu)—信箱中，接收進(jìn)程也到信箱去取信件，即進(jìn)程間發(fā)送或接收信件均通過(guò)信箱來(lái)進(jìn)行；死鎖的定義：一組并發(fā)進(jìn)程彼此相互等待對(duì)方所占有的資源，而且這些進(jìn)程是得到對(duì)方的資源之前不會(huì)釋放自己所占有的資源，從而造成這組進(jìn)程都不能繼續(xù)推進(jìn)的狀況；死鎖的必要條件：a.互斥條件：一個(gè)資源一次只能由一個(gè)進(jìn)程使用，如果有其他進(jìn)程申請(qǐng)使用該資源，申請(qǐng)進(jìn)程必須等待直到所申請(qǐng)的資源被釋放；b.部分分配條件：一個(gè)資源已占有一定資源后，執(zhí)行期間又再申請(qǐng)其他資源；c.不可搶占條件：一個(gè)資源僅能由一個(gè)占有它的進(jìn)程來(lái)釋放，而不能被其他進(jìn)程搶占使用；循環(huán)等待條件：在系統(tǒng)中存在一個(gè)由若干進(jìn)程申請(qǐng)使用資源而形成的循環(huán)等待鏈，其中每一個(gè)進(jìn)程占有若干資源，同時(shí)又在等待下一個(gè)進(jìn)程所占有的資源；死鎖的防止（通過(guò)破壞部分分配條件和循環(huán)等待條件）（1）資源靜態(tài)分配法（2）資源的層次分配法死鎖的避免：為申請(qǐng)者分配資源前先測(cè)試系統(tǒng)的資源狀況，若把資源分配給申請(qǐng)者會(huì)產(chǎn)生死鎖的話，則拒絕分配，否則接受申請(qǐng)并為它分配資源；銀行家算法：檢查申請(qǐng)者對(duì)各類資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源可以滿足它的最大需求量時(shí)，就滿足當(dāng)前的申請(qǐng)；P203習(xí)題6.18，6.19）銀行家算法某系統(tǒng)有R1,R2,R3共3種資源在T0時(shí)刻P1,P2,P3和P4這4個(gè)進(jìn)程對(duì)資源的占用和需求如下，系統(tǒng)的可用資源向量為（2，1，2）進(jìn)程最大需求占有量R1R2R3R1R2R3P1322100P2613411P3314211P4422002請(qǐng)回答下列問(wèn)題：1）將系統(tǒng)中各種資源的總和和此刻各進(jìn)程對(duì)資源的需求數(shù)目用向量或矩陣表示出來(lái)。2）如果此時(shí)P1和P2均發(fā)出資源請(qǐng)求向量（1，0，1），為了保持系統(tǒng)安全性，應(yīng)如何分配資源給這兩個(gè)進(jìn)程。解：1.[9,3,6]2222021034202.先分配給進(jìn)程P2,P1掛起。死鎖的檢測(cè)與恢復(fù)（資源分配圖和相應(yīng)的等待圖P200）第七章 操作系統(tǒng)的安全性美國(guó)國(guó)防部的橙皮書：D,C,B,A四個(gè)級(jí)別（細(xì)分為8個(gè)等級(jí)D1,C1,C2,B1,B2,B3,A1,A1以上），級(jí)別逐漸增強(qiáng)；保護(hù)機(jī)制P212存儲(chǔ)控制的兩種實(shí)現(xiàn)方式的差別：存取矩陣的兩種方式P215存取控制表（按列存取矩陣）、權(quán)能表（按行存取矩陣）第八章UNIX系統(tǒng)簡(jiǎn)介（聯(lián)系前面內(nèi)容，了解）1.UNIX是一個(gè)多用戶會(huì)話式分時(shí)系統(tǒng)，向用戶提供了兩種友好的用戶界面或接口：操作級(jí)界面—命令、程序級(jí)界面—系統(tǒng)調(diào)用2.UNIX進(jìn)程調(diào)度——多級(jí)反饋輪轉(zhuǎn)調(diào)度法算法思想：給進(jìn)程一個(gè)時(shí)間片時(shí)間片結(jié)束時(shí)計(jì)算進(jìn)程優(yōu)先級(jí)分析情況置狀態(tài)調(diào)度高優(yōu)先級(jí)進(jìn)程開始程序？3.UNIX存儲(chǔ)管理：請(qǐng)求頁(yè)式策略和交換策略4.UNIX文件系統(tǒng)具有樹形層次結(jié)構(gòu)UNIX文件可分為普通文件、目錄文件和設(shè)備文件。（普通文件和目錄文件都是無(wú)結(jié)構(gòu)、無(wú)記錄概念的字符流式文件）文件系統(tǒng)的存儲(chǔ)和分配：索引節(jié)點(diǎn)——索引節(jié)點(diǎn)分配法空閑磁盤塊——成組鏈接法操作系統(tǒng)重要考點(diǎn)整理考點(diǎn)一：頁(yè)面置換算法（結(jié)合存儲(chǔ)器管理中相關(guān)知識(shí)點(diǎn)考）1）優(yōu)化算法（OPT）：這是一種理論化的算法，其所選擇的被淘汰的頁(yè)將是永不使用的頁(yè)，或者是在最長(zhǎng)時(shí)間內(nèi)不再訪問(wèn)的頁(yè)。2）先進(jìn)先出算法（FIFO）：該算法總是淘汰最先進(jìn)入主存的頁(yè)面，認(rèn)為最先調(diào)入的頁(yè)最近不被訪問(wèn)可能性最大。缺頁(yè)率=缺頁(yè)次數(shù)/總的訪問(wèn)次數(shù)*100%用FIFO算法求缺頁(yè)率：123412512345111444555555222111113333332222244FFFFFFFSSFFS缺頁(yè)率=9/12*100%=75%Belady現(xiàn)象：一般情況下，對(duì)于一個(gè)作業(yè)如果分配給它的主存頁(yè)框越多，缺頁(yè)中斷率就越低，反之就越高，但對(duì)于FIFO算法來(lái)說(shuō)，在未給作業(yè)分配足夠滿足它要求的頁(yè)面時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)框數(shù)增多，而缺頁(yè)中斷率反而增高的奇異現(xiàn)象；3）最近最少用置換算法（LRU）：該算法要求淘汰的頁(yè)面是在最近一段時(shí)間里較久未被訪問(wèn)的那一頁(yè)。根據(jù)是程序執(zhí)行時(shí)所具有的局部性。為了比較準(zhǔn)確地淘汰最近最少使用的頁(yè)面，可以采用堆棧的方法來(lái)實(shí)現(xiàn)。棧中存放當(dāng)前主存中的頁(yè)號(hào)，每當(dāng)訪問(wèn)一頁(yè)時(shí)就調(diào)整一次棧。于是，發(fā)生缺頁(yè)中斷時(shí)總是淘汰棧底所指示的頁(yè)。用LRU算法求缺頁(yè)率：4）第二次機(jī)會(huì)算法：淘汰不但 “老”而（最近）“沒(méi)用”的頁(yè)面原理：用鏈表來(lái)表示各頁(yè)的建立時(shí)間先后，新來(lái)的到表尾，表頭就是最“老”的（同F(xiàn)IFO）,頁(yè)面裝入或被訪問(wèn)時(shí)設(shè)R=1。選擇淘汰頁(yè)面時(shí)，若表頭頁(yè)面的R位（訪問(wèn)位）是0，則淘汰之，否則將其R位設(shè)為0，并把它放到表尾，然后繼續(xù)從表頭搜索。5）時(shí)鐘算法：環(huán)形鏈表實(shí)現(xiàn)的第二次機(jī)會(huì)算法環(huán)形鏈表頭尾相鄰，因此只需要移動(dòng)一個(gè)指針；性能近似LRU，實(shí)現(xiàn)開銷小例：調(diào)入頁(yè)面727前后Clock與LRU、FIFO比較*號(hào)表示R=1，箭頭表示指針Clock通過(guò)設(shè)置R位保護(hù)了常用的頁(yè)面6）最近未用置換算法（NRU）概念：該算法要求頁(yè)表中有一個(gè)訪問(wèn)位和一個(gè)修改位。當(dāng)某頁(yè)被訪問(wèn)時(shí)，訪問(wèn)位被自動(dòng)置1，若執(zhí)行的指令是寫指令，則修改位也被置1。系統(tǒng)周期性地將所有訪問(wèn)位置0。在選擇一頁(yè)淘汰時(shí)，總是選擇其訪問(wèn)位為0且修改位也為0的頁(yè)。若無(wú)修改位為0的頁(yè)，就選訪問(wèn)位為0且頁(yè)號(hào)最小的頁(yè)淘汰。評(píng)價(jià)：該算法不但希望淘汰的頁(yè)是最近未使用的頁(yè)，而且還希望被淘汰的頁(yè)是在主存駐留期間其頁(yè)面內(nèi)容未被修改過(guò)。系統(tǒng)對(duì)訪問(wèn)位清0的間隔時(shí)間T的確定是很關(guān)鍵的。如果間隔時(shí)間T太大，可能所有頁(yè)的訪問(wèn)位均已成為1，無(wú)法選擇淘汰的頁(yè)面。如果間隔時(shí)間T太小，則可能很多頁(yè)的訪問(wèn)位均是為0基于Clock的NRU算法過(guò)程：從指針位置開始掃描鏈表，掃描過(guò)程中不改變R位。淘汰遇到的第一個(gè)R＝0&M=0的頁(yè)面。若第1步失敗，則再次掃描，淘汰遇到的第一個(gè)R＝0&M＝1的頁(yè)面。每個(gè)頁(yè)面檢查過(guò)后將R設(shè)為0。若第2步失敗，重復(fù)1和2（如果需要）。7）最少使用置換算法（LFU）概念：要求為每一頁(yè)表項(xiàng)配置一個(gè)一定位數(shù)的計(jì)數(shù)器作為訪問(wèn)字段，開始時(shí)所有的計(jì)數(shù)器均為0。一旦某頁(yè)被訪問(wèn)時(shí)，其頁(yè)表項(xiàng)中的計(jì)數(shù)器值加1。系統(tǒng)每過(guò)一段時(shí)間T就將所有的頁(yè)表項(xiàng)計(jì)數(shù)器清0。在需要選擇一頁(yè)置換時(shí)，便比較各計(jì)數(shù)器的值，總是選擇其計(jì)數(shù)值最小的頁(yè)面淘汰。評(píng)價(jià)：該算法實(shí)現(xiàn)也較容易，但代價(jià)較高，而且合適的間隔時(shí)間T的選擇也是難題?？键c(diǎn)三P,V操作1）桌上有一只盤子，每次只能放入一只水果。爸爸專放蘋果，媽媽專放橘子，一個(gè)兒子專等吃盤子中的橘子，一個(gè)女兒專等吃盤子中的蘋果。用PV操作實(shí)現(xiàn)。用p,v操作實(shí)現(xiàn)：empty,full1,full2:semaphore;empty:=1;full1:=0;full2:=0;CobeginRepeatfarther;Repeatmother;repeatson;repeatdaughter;Coend;Procedurefather;beginP(empty);放蘋果入盤;V(full1);end;proceduremother;beginP(empty);放橘子入盤;V(full2);end;Procedure son;beginP(full2);從盤中