計(jì)算機(jī)操作系統(tǒng)期末復(fù)習(xí)筆記

朽木易折，金石可鏤。千里之行，始于足下。第頁/共頁第一章OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口：含義是：OS處于用戶和計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過OS來使用計(jì)算機(jī)系統(tǒng)。用戶可以通過以下三種方式使用計(jì)算機(jī)：命令方式；系統(tǒng)調(diào)用方式；圖形、窗口方式操作系統(tǒng)的發(fā)展過程：無操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)、單道批處理系統(tǒng)、多道批處理系統(tǒng)、分時系統(tǒng)、實(shí)時系統(tǒng)多道批處理系統(tǒng)是操作系統(tǒng)成熟的標(biāo)志。操作系統(tǒng)的定義：操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理地對各類作業(yè)舉行調(diào)度，以及方便用戶使用的程序的集合。分時系統(tǒng)--（1）人機(jī)交互的特征是邊運(yùn)行邊調(diào)試。（2）分享主機(jī)（3）便于用戶上機(jī)實(shí)時系統(tǒng)的及時性：及時響應(yīng)外部事件哀求，在規(guī)定的時光完成對該事件的處理，控制所有實(shí)時任務(wù)協(xié)調(diào)一致運(yùn)行。分時系統(tǒng)的特征：(1)多路性即同時性，宏觀上同時，微觀上輪流(2)獨(dú)占性每個用戶感覺獨(dú)占主機(jī)(3)及時性較短時光響應(yīng)(1-3秒)(4)交互性實(shí)時系統(tǒng)與分時系統(tǒng)特征的比較：分時系統(tǒng)是指在一臺主機(jī)上銜接多個帶有顯示器和鍵盤的終端，同時允許多個用戶通過自己的終端，以交互方式使用計(jì)算機(jī)，分享主機(jī)中的資源。實(shí)時系統(tǒng)（RealTimeSystem）是指系統(tǒng)能及時（或即時）響應(yīng)外部事件的哀求，在規(guī)定的時光內(nèi)完成對該事件的處理，并控制所有實(shí)時任務(wù)協(xié)調(diào)一致地運(yùn)行。實(shí)時系統(tǒng)的特點(diǎn)：多路性、獨(dú)占性、及時性、交互性、可靠性，主要是及時性。分時系統(tǒng)的特征：多路性、獨(dú)占性、及時性、交互性，其中最主要的就是交互性。操作系統(tǒng)的基本特征：并發(fā)性（最重要特征）、分享性、虛擬性、異步性并行與并發(fā)：并行性是指多個事件在同一時刻同時發(fā)生；并發(fā)性是指兩個或多個事件在同一時光間隔內(nèi)發(fā)生，宏觀上在同一時光段內(nèi)同時運(yùn)行，微觀上交替執(zhí)行。分享：指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程共同使用，相應(yīng)地把這種資源共同使用成為資源分享或稱為資源復(fù)用。臨界資源：在一段時光內(nèi)只允許一個進(jìn)程拜訪的資源稱為臨界資源或獨(dú)占資源。并發(fā)和分享是操作系統(tǒng)的二個最基本特征，他們又是互為存在的條件虛擬技術(shù):操作系統(tǒng)中的所謂“虛擬”（Virtual），是指通過某種技術(shù)把一個物理實(shí)體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。物理實(shí)體是實(shí)的，即實(shí)際存在的，后者是虛的，是用戶感覺上的東西。用于實(shí)現(xiàn)虛擬的技術(shù)稱為虛擬技術(shù)。操作系統(tǒng)的主要功能：處理機(jī)管理功能：對處理機(jī)舉行分配——進(jìn)程管理和調(diào)度存儲器管理功能：對內(nèi)存舉行分配、保護(hù)和擴(kuò)充設(shè)備管理功能：緩沖管理、設(shè)備分配、設(shè)備處理文件管理功能：文件存儲空間的管理、目錄管理、文件的讀寫管理和保護(hù)操作系統(tǒng)與用戶之間的接口用戶接口和程序接口第二章進(jìn)程管理0.程序順序執(zhí)行的特征：順序性、封閉性、可再現(xiàn)性前趨圖(PrecedenceGraph)：一個有向無循環(huán)圖、描述程序或程序段之間執(zhí)行的前后關(guān)系前趨圖是一個有向無循環(huán)圖。（必須不存在循環(huán)）按照程序畫前趨圖：朽木易折，金石可鏤。千里之行，始于足下。第頁/共頁并發(fā)執(zhí)行時的特征：間斷性——“停停走走”；失去封閉性——緣故：多個程序分享資源；不可再現(xiàn)性進(jìn)程的定義和特征：定義：進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)舉行資源分配和調(diào)度的一個自立單位。進(jìn)程是程序的一次執(zhí)行，進(jìn)程是一個程序及數(shù)據(jù)在處理機(jī)上順序執(zhí)行時所發(fā)生的活動。進(jìn)程的特征：1）結(jié)構(gòu)性：進(jìn)程由程序段、數(shù)據(jù)段及PCB三部分組成，在Linux中稱為“進(jìn)程映像”2）動態(tài)性：“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡”。是進(jìn)程的最基本特征3）自立性：進(jìn)程是一個能自立運(yùn)行、自立分配資源和自立調(diào)度的基本單位。各進(jìn)程的地址空間互相自立。4）并發(fā)性：引入進(jìn)程的目的正是為了使其程序能和其他進(jìn)程的程序并發(fā)執(zhí)行；5）異步性：進(jìn)程按各自自立的、不可預(yù)知的速度向前推進(jìn)進(jìn)程的三種基本狀態(tài)就緒狀態(tài)（Ready）：得到了除CPU以外的所有須要資源。執(zhí)行狀態(tài)（Running）：已獲得處理機(jī)，程序正在被執(zhí)行。阻塞狀態(tài)（Blocked）：因等待某事件發(fā)生而暫時無法繼續(xù)執(zhí)行，從而放棄處理機(jī)，使程序執(zhí)行處于暫停狀態(tài)。進(jìn)程控制塊PCB(ProcessControlBlock)：是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄性數(shù)據(jù)結(jié)構(gòu)。PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的所有信息。進(jìn)程控制塊的作用是使一個在多道程序環(huán)境下不能自立運(yùn)行的程序成為一個能自立運(yùn)行的基本單位，一個能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。PCB是進(jìn)程存在的惟一標(biāo)志。進(jìn)程控制塊中的信息：1）進(jìn)程標(biāo)示符2）處理機(jī)狀態(tài)—通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字PSW、用戶棧指針3）進(jìn)程調(diào)度信息4）進(jìn)程控制信息臨界區(qū)：人們把在每一個進(jìn)程中拜訪臨界資源的那段代碼稱為臨界區(qū)同步機(jī)制應(yīng)遵循的規(guī)矩：空閑讓進(jìn)。當(dāng)無進(jìn)程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個哀求進(jìn)入臨界區(qū)的進(jìn)程趕緊進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待。當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界資源正在被拜訪，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥拜訪。有限等待。對要求拜訪臨界資源的進(jìn)程，應(yīng)保證在有限時光內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)趕緊釋放處理機(jī)，以免陷入“忙等”狀態(tài)。Wait（S）操作描述：執(zhí)行一次wait操作意味著哀求分配一個單位的資源，因此描述為:s.value=s.value-1。減1后：若s.value≥0，則進(jìn)程繼續(xù)舉行；若s.value＜0，表示已無資源可用，因此哀求該資源的進(jìn)程將被阻塞，要把它排在信號量s的等待隊(duì)列中，此時，s.value的絕對值等于該信號量等待隊(duì)列上的進(jìn)程數(shù)目。Signsl(S)操作描述：執(zhí)行一次signal操作意味著釋放一個單位的資源，故s.value=s.value+1。加1后：若s.value＞0，則進(jìn)程繼續(xù)；若s.value≤0，表示信號量哀求隊(duì)列中仍有因哀求該資源而被阻塞的進(jìn)程，因此應(yīng)把隊(duì)列中的一個或幾個進(jìn)程喚醒，使之轉(zhuǎn)至就緒隊(duì)列中。進(jìn)程通信：是指進(jìn)程之間的信息交換。進(jìn)程通信的類型即高級通信機(jī)制：分享存儲器系統(tǒng)、消息傳遞系統(tǒng)、管道通信系統(tǒng)三種。第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的層次：高級調(diào)度、低級調(diào)度、中級調(diào)度高級調(diào)度（HighLevelScheduling）：又叫作業(yè)調(diào)度或長程調(diào)度（LongTermScheduling）,其主要功能是按照某種算法，把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存。也就是說它的調(diào)度對象是作業(yè)。低級調(diào)度（LowLevelScheduling）：通常也稱為進(jìn)程調(diào)度或短程調(diào)度（ShortTermScheduling）,它所調(diào)度的對象是進(jìn)程（或內(nèi)核級線程）。決定就緒隊(duì)列中的哪個進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的詳細(xì)操作。進(jìn)程調(diào)度是最基本的調(diào)度，在三種類型的OS中都必須配置低級調(diào)度的功能：保存處理機(jī)的現(xiàn)場信息；按照某種算法選取進(jìn)程；把處理機(jī)分配給進(jìn)程。進(jìn)程調(diào)度方式非搶占方式b）搶占方式先來先服務(wù)調(diào)度算法：是一種最基本的調(diào)度算法，既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度。比較有利于長作業(yè)進(jìn)程，而不利于短作業(yè)進(jìn)程。6. 短作業(yè)優(yōu)先調(diào)度算法：指對短作業(yè)或段進(jìn)程優(yōu)先調(diào)度算法可以分離用于作業(yè)調(diào)度和進(jìn)程調(diào)度。該算法對長作業(yè)不利，徹低未考慮作業(yè)的緊迫程度，不能保證緊迫性作業(yè)及時處理。該算法不一定真正做到短作業(yè)優(yōu)先調(diào)度。死鎖（Deadlock）定義：死鎖是指兩個或兩個以上的進(jìn)程在運(yùn)行過程中，因爭奪資源而造成的一種互相等待（誰也無法再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。產(chǎn)生死鎖的緣故：1、競爭資源2、進(jìn)程間推進(jìn)順序非法產(chǎn)生死鎖的須要條件：互斥條件。一個資源一次只能被一個進(jìn)程使用。哀求和保持條件（部分分配）。保留已經(jīng)得到的資源，還要求其它的資源。不可剝奪條件（不可搶占）。資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)行搶占。環(huán)路等待條件（循環(huán)等待）。系統(tǒng)中的進(jìn)程形成了環(huán)形的資源哀求鏈。預(yù)防死鎖的主意1.摒棄哀求和保持條件2.摒棄不剝奪條件3.摒棄環(huán)路等待條件安全狀態(tài)：允許進(jìn)程動態(tài)的申請資源，但在分配前，應(yīng)先計(jì)算分配的安全性。所謂“安全狀態(tài)”：指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)，來為每個進(jìn)程Pi分配其所需資源，直至最大需求，使每個進(jìn)程都可以順利完成。反之，則系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀態(tài)。安全狀態(tài)之例：第四章存儲器管理程序的裝入和鏈接：如何將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常都要經(jīng)過以下幾個步驟：首先是編譯，由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊；第二是鏈接，由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及他們所需要的庫函數(shù)鏈接在一起，形成一個殘破的裝入模塊；最后是裝入，由裝入程序?qū)⒛K裝入內(nèi)存。重定位：通常是把在裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。靜態(tài)重定位：因?yàn)榈刂纷儞Q通常是在裝入時一次完成的，以后不再改變。動態(tài)分區(qū)別配：按照進(jìn)程的實(shí)際需要，動態(tài)的分配內(nèi)存空間。分區(qū)別配算法：首次適應(yīng)算法：空閑分區(qū)按起址遞增次序羅列，從頭開始直至找到第一個滿意要求的空閑分區(qū)。特點(diǎn)：內(nèi)存低端會留下小的空閑區(qū)，高端有大的空閑區(qū)；循環(huán)首次應(yīng)算法：從上次分配的位置之后開始尋找。特點(diǎn)：使內(nèi)存的空閑分區(qū)勻稱，但缺乏大的空閑分區(qū)；最佳適應(yīng)算法：空閑分區(qū)按大小遞增的次序羅列，從頭開始找到第一個滿意要求的空閑分區(qū)。缺點(diǎn)：會留下大量小碎片。最壞適應(yīng)算法：空閑分區(qū)按大小遞減的次序羅列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。優(yōu)點(diǎn)：分配后剩下的可用空間比較大。缺點(diǎn)：一段時光后就不能滿意對于較大空閑區(qū)的分配要求。頁面和物理塊：分頁存儲管理是將一個進(jìn)程的邏輯地址控件分成若干個大小相等的片，稱為頁面或頁并為各頁加以編號。相應(yīng)的把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為物理塊或頁框，也對它們加以編號。頁表的作用：頁表的作用是實(shí)現(xiàn)從頁號到物理塊號的地址映射。地址變換機(jī)構(gòu)的基本任務(wù)：實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，借助于頁表完成的。分頁地址結(jié)構(gòu)由頁號P和位移量W組成例子：系統(tǒng)的頁面大小為1KB，設(shè)A=2017B，可以求出頁號P=2，頁內(nèi)地址/位移量d=122。段表的作用：段表是用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。定義：在系統(tǒng)中為每個進(jìn)程建立一張段映射表。地址變換機(jī)構(gòu)是為了實(shí)現(xiàn)從進(jìn)程的邏輯地址到物理地址的變換功能。分頁和分段的主要區(qū)別：相似之處：兩者都采用離散分配方式且通過地址映射機(jī)構(gòu)來實(shí)現(xiàn)地址變換。不同之處：（1）頁是信息的物理單位，段是信息的邏輯單位；頁的大小固定，段的大小動態(tài)變化；分頁系統(tǒng)中的邏輯地址空間是一維的，分段系統(tǒng)中的是二維的。虛擬存儲器的定義：虛擬存儲器是指具有哀求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。虛擬存儲器的特征:多次性。一個作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行；對換性。允許在作業(yè)的運(yùn)行過程中舉行換進(jìn)、換出；虛擬性。能從邏輯上擴(kuò)充內(nèi)存容量，使用戶“看到”的內(nèi)存容量遠(yuǎn)大于實(shí)際大小。該特征是以上兩個特征為基礎(chǔ)的。頁面置換算法：最佳置換算法（未來最長時光內(nèi)不再被拜訪的頁面淘汰。OPT）先進(jìn)先出（FIFO最早進(jìn)入頁面的淘汰）最近最久未使用的置換算法（LRU最近最久未使用的頁面淘汰）一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率第五章設(shè)備管理I/O設(shè)備分類：按設(shè)備使用特性分類：第一類存儲設(shè)備，第二類輸入/輸出設(shè)備按傳輸速率分類：按傳輸書讀的高低，可分為三類：低速設(shè)備，典型設(shè)備有鍵盤、鼠標(biāo)器、語音的輸入輸出等設(shè)備。中速設(shè)備，典型設(shè)備有行式打印機(jī)、激光打印機(jī)等。高速設(shè)備，典型的設(shè)備有磁帶機(jī)、磁盤機(jī)、光盤機(jī)等。按信息交換單位分類：第一類是塊設(shè)備（BlockDevice），用于存儲信息。例如磁盤第二類是字符設(shè)備（CharacterDevice）,用于數(shù)據(jù)的輸入和輸出。交互式終端、打印機(jī)I/O通道：I/O通道是一種異常的處理機(jī)，它具有執(zhí)行I/O指令的能力，并通過執(zhí)行通道（I/O）來控制I/O操作。I/O控制方式：程序I/O方式，數(shù)據(jù)傳輸?shù)幕締挝皇亲止?jié)中斷驅(qū)動I/O方式，數(shù)據(jù)傳輸?shù)幕締挝蝗允亲止?jié)DMA控制方式，以多個塊為單位舉行數(shù)據(jù)傳送；數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)庫I/O通道控制方式,以多個塊為單位舉行數(shù)據(jù)傳送；一次傳送多組數(shù)據(jù)到多個不同的內(nèi)存區(qū)域。緩沖技術(shù)分為：單緩沖，雙緩沖，循環(huán)緩沖、緩沖池。單緩沖和雙緩沖：單緩沖：在設(shè)備和處理機(jī)之間設(shè)置一個緩沖區(qū)。T和C是可以并行的。系統(tǒng)對每個數(shù)據(jù)的處理時光為Max(C,T)+M。雙緩沖－緩沖對換：系統(tǒng)處理每個數(shù)據(jù)的時光可粗略認(rèn)為Max(C,T)。當(dāng)T>C，可使塊設(shè)備延續(xù)輸入；反之可使CPU不必等待設(shè)備輸入。目的：加快輸入輸出的速度。循環(huán)緩沖：循環(huán)緩沖是把多個緩沖區(qū)銜接起來組成兩部分，一部分專門用于輸入，另一部分專門用于輸出的緩沖結(jié)構(gòu)。設(shè)備驅(qū)動程序：設(shè)備驅(qū)動程序通常又稱為設(shè)備處理程序，它是I/O進(jìn)程與設(shè)備控制器之間的通信程序，又因?yàn)樗Ｒ赃M(jìn)程的形式存在，故簡稱為設(shè)備驅(qū)動程序。設(shè)備分配中的數(shù)據(jù)結(jié)構(gòu)：設(shè)備控制表DCT，系統(tǒng)為每臺設(shè)備配置一張控制器控制表COCT，系統(tǒng)為每一個控制器都設(shè)置了一張控制器控制表。通道控制表CHCT，每個通道都配有一張通道控制表。系統(tǒng)設(shè)備表SDT，記錄了系統(tǒng)中所有設(shè)備的情況，每個設(shè)備占一個表目?；镜脑O(shè)備分配程序：按下述步驟舉行設(shè)備分配：分配設(shè)備分配控制器分配通道磁盤拜訪時光：尋道時光Ts：(可優(yōu)化處理)把磁臂（磁頭）移動到指定磁道上所經(jīng)歷的時光，包含啟動磁臂和磁頭移動n條磁道所花費(fèi)的時光。是優(yōu)化的基礎(chǔ)。旋轉(zhuǎn)延遲時光Tr：指定扇區(qū)移動到磁頭下面所經(jīng)歷的時光。與盤面的旋轉(zhuǎn)速度有關(guān)。5400轉(zhuǎn)—平均旋轉(zhuǎn)延遲時光5.55ms；7200轉(zhuǎn)—平均旋轉(zhuǎn)延遲時光4.16ms傳輸時光Tt：把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時光。與旋轉(zhuǎn)速度和一次讀寫的數(shù)據(jù)量有關(guān)10.磁盤調(diào)度：先來先服務(wù)FCFS：按照進(jìn)程哀求拜訪磁盤的先后次序舉行調(diào)度。優(yōu)點(diǎn)：平等、容易，每個進(jìn)程的哀求依次得到處理缺點(diǎn)：平均尋道時光可能較長，僅適用于磁盤哀求較少的場合。最短尋道時光優(yōu)先SSTF：挑選要求拜訪的磁道與當(dāng)前磁頭所在的磁道距離最近的進(jìn)程（磁盤哀求），使每次的尋道時光最短。該算法不能保證平均尋道時光最短?？赡軐?dǎo)致“饑餓”現(xiàn)象。掃描（Scan）算法：又稱為“電梯調(diào)度算法”。磁頭每次只作單方向移動，直到到達(dá)邊緣磁道為止，然后再作反向移動。下一次待拜訪的磁道只能在此磁頭移動的前方，且挑選磁頭移動距離最近的一個磁盤哀求響應(yīng)。消除了饑餓現(xiàn)象。循環(huán)掃描（CScan）算法：磁頭只作由內(nèi)向外的單方向掃描，到達(dá)外邊緣后，則返回最內(nèi)側(cè)的磁道重新舉行下一輪掃描。改進(jìn)了對于邊緣區(qū)磁道拜訪的不平等。第六章文件管理記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個對象的某些屬性。關(guān)鍵字：能夠唯一標(biāo)識一個記錄的數(shù)據(jù)項(xiàng)按文件的性質(zhì)和用途分：系統(tǒng)文件：由系統(tǒng)軟件構(gòu)成的文件，只允許調(diào)用執(zhí)行，不允許用戶讀和修改。用戶文件：只允許文件的授權(quán)者使用。庫文件：允許用戶調(diào)用不允許修改。文件系統(tǒng)模型：用戶（程序）文件系統(tǒng)模型對象及其屬性：文件管理系統(tǒng)管理的對象有：文件：文件管理的直接對象；目錄：方便用戶對文件的存取和檢索；磁盤（磁帶）存儲空間文件的邏輯結(jié)構(gòu):這是從用戶觀點(diǎn)出發(fā)所看見到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它自立于文件的物理特性，又稱為文件組織。文件的物理結(jié)構(gòu)，又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式。文件邏輯結(jié)構(gòu)的類型：文件的邏輯結(jié)構(gòu)可分為兩大類：一類是有結(jié)構(gòu)文件，這是指一個以上的記錄構(gòu)成的文件，故又把它稱為記錄式文件。二是無結(jié)構(gòu)文件，這是指由字符流構(gòu)成的文件，故又稱為流式文件。外存分配方式：常用的外存分配主意有延續(xù)分配、鏈接分配和索引分配三種。鏈接分配：將文件裝到多個離散的盤塊中，是離散的分配方式。鏈接方式又可分為：隱式鏈接、顯式鏈接兩種隱式鏈接：在文件的每個目錄項(xiàng)中，都含有指向鏈接文件第一盤塊和最后一個盤塊的指針。每個盤塊中都有指向下一個盤塊的指針。特點(diǎn)：只相宜于順序拜訪，隨機(jī)拜訪效率極低。顯式鏈接：把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張“鏈接表”中。該表在囫圇磁盤只設(shè)置一張。即文件分配表（FAT）。序號為盤塊號0..n-1目錄管理的要求：實(shí)現(xiàn)“按名存取”——是目錄管理的最基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務(wù)；提高對目錄的檢索速度；文件分享；允許文件重名。為了能對一個文件舉行準(zhǔn)確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，稱為“文件控制塊FCB”。文件管理程序可借助于文件控制塊中的信息，對文件施以各種操作。文件與文件控制塊一一對應(yīng)，而人們把文件控制塊的有序集合稱為文件目錄，即一個文件控制塊就是一個文件目錄項(xiàng)。一個文件目錄頁被看做是一個文件，稱為目錄文件。文件存儲空間的管理：分配方式：延續(xù)分配、離散分配存儲空間的基本分配單位是以磁盤塊（扇區(qū)）為單位，而非字節(jié)。文件存儲空間的管理主意1）空閑表法：延續(xù)分配方式，為外存上的所有空閑區(qū)建立一張空閑表。2）空閑鏈表法：離散分配方式，按照構(gòu)成鏈所用基本元素不同分為以下兩種形式：空閑盤塊鏈：將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈?？臻e盤區(qū)鏈：將磁盤上所有空閑盤區(qū)（每個盤區(qū)可包含若干個盤塊）拉成一條鏈。3）位示圖法：位示圖：利用二進(jìn)制的一位來表示磁盤中一個盤塊的使用情況。由所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。用mxn個位數(shù)構(gòu)成位示圖。4）成組鏈接法常用的兩種文件分享主意：1）基于索引結(jié)點(diǎn)的分享方式；2）利用符號鏈實(shí)現(xiàn)文件分享基于索引結(jié)點(diǎn)的分享方式：文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點(diǎn)的指針；文件的物理地址及其它的文件屬性等信息只存放在索引結(jié)點(diǎn)中；程序：1、利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題：Varchopsiickarrayofsemaphore:=(1,1,1,1,1);ProcessiRepeatthink;Sswait(chopsick[(i+1)mod5],chopstick[i]);eat;Ssignat(chopsick[(i+1)mod5],chopstick[i]);untilfalse;2、利用記錄型信號量解決生產(chǎn)者消費(fèi)者問題Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,···，n-1]ofitem;in,out:integer:=0,0;beginparbeginproceducer:beginrepeat··produceranitemnextp;··wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);