操作系統(tǒng)理論的學(xué)習(xí)跟實(shí)際應(yīng)用還是很大的。我學(xué)了進(jìn)程線程同步互斥之后對于編程中的多線程等加鎖的還是云里霧里，總是把操作系統(tǒng)和編程串不起來，也把計(jì)算機(jī)幾門專業(yè)課串不起來，感覺計(jì)算機(jī)這個(gè)專業(yè)書讀十遍以下是不可能把四門專業(yè)課書連貫的自己串起來。人的智商和邏輯性還是差異很大的。。

壹：進(jìn)程管理

（一）?? 進(jìn)程與線程

? ? 1. 進(jìn)程概念 ： 就是一個(gè)具有獨(dú)立功能的程序的一次動(dòng)態(tài)執(zhí)行。

?

? ? 2. 進(jìn)程的狀態(tài)與轉(zhuǎn)換 ：

? ? ? ? 進(jìn)程的三個(gè)基本狀態(tài)是就緒、執(zhí)行、阻塞。就緒態(tài)到執(zhí)行態(tài)的轉(zhuǎn)換只需要cpu調(diào)度即可，阻塞態(tài)只能轉(zhuǎn)為就緒態(tài)不能直接轉(zhuǎn)為執(zhí)行態(tài)。執(zhí)行態(tài)如果時(shí)間片用完就 ? ?轉(zhuǎn)成了就緒態(tài)如果等待某事件發(fā)生就轉(zhuǎn)成阻塞態(tài)。如果在這三個(gè)基本狀態(tài)下進(jìn)程發(fā)生掛起行為則從就緒態(tài)轉(zhuǎn)為掛起或稱靜態(tài)就緒，從執(zhí)行態(tài)轉(zhuǎn)也轉(zhuǎn)為靜止就緒，從 ? ?阻塞態(tài)轉(zhuǎn)為靜止阻塞。

?

? ? ?3. 進(jìn)程控制：

? ? ? ? 進(jìn)程控制就是對系統(tǒng)中所有進(jìn)程從產(chǎn)生到消亡實(shí)施管理，由OS的內(nèi)核實(shí)現(xiàn)，內(nèi)核是通過調(diào)用各種原語來實(shí)現(xiàn)的。有進(jìn)程創(chuàng)建原語，進(jìn)程撤銷原語，阻塞原語，喚醒原語等。

?

? ? 4. 進(jìn)程組織：

? ? ? ? 一個(gè)進(jìn)程是由三部分組成的，程序、數(shù)據(jù)、進(jìn)程控制塊(PCB)。這三個(gè)合起來也稱為進(jìn)程實(shí)體。其中進(jìn)程控制塊是進(jìn)程動(dòng)態(tài)特性的集中反映，創(chuàng)建進(jìn)程則產(chǎn)生pcb撤銷進(jìn)程就要收回pcb，pcb表項(xiàng)的個(gè)數(shù)是確定的，所以一個(gè)系統(tǒng)中的進(jìn)程不是無限多的。。

進(jìn)程控制塊很重要所以詳細(xì)寫點(diǎn)，它包含的內(nèi)容很多，有

? ? ? （1）進(jìn)程描述信息：進(jìn)程標(biāo)示符（每個(gè)進(jìn)程有一個(gè)唯一的號）和用戶標(biāo)示符（每個(gè)進(jìn)程屬于某個(gè)用戶）

? ? ? （2）進(jìn)程控制信息：進(jìn)程當(dāng)前狀態(tài)，如果是阻塞的要再pcb中說明阻塞原因，進(jìn)程優(yōu)先級、代碼執(zhí)行入口地址、程序外存地址、各種計(jì)時(shí)信息(程序執(zhí)行時(shí)間，頁面調(diào)度情況)

? ? ? （3）資源管理信息：用于說明有關(guān)虛擬地址空間的現(xiàn)狀，打開文件的列表，和使用的輸入輸出的信息。

? ? ? （4）CPU現(xiàn)場保護(hù)結(jié)構(gòu)：保存各種寄存器的值。

系統(tǒng)中pcb數(shù)目眾多，他們是怎么組織起來的有鏈接方式和索引方式兩種：鏈接方式就是形成就緒隊(duì)列，阻塞隊(duì)列等，還要對就緒隊(duì)列按進(jìn)程優(yōu)先權(quán)排列。索引方式是建立幾種狀態(tài)的索引表，索引表記錄pcb的地址。

?

? ? ? 5. 進(jìn)程通信

? ? ?進(jìn)程的互斥與同步交換的信息量較少，所以稱為低級通信方式。進(jìn)程之間以較高的效率傳送大量數(shù)據(jù)的通信方式叫高級通信方式分為三大類：

? ? ?(1) 共享存儲系統(tǒng)：就是共享內(nèi)存。。其實(shí)編程沒編過我對這些都理解不深刻。

? ? ?(2) 消息傳遞系統(tǒng)：直接通信(send和receive通信命令直接發(fā)給接收進(jìn)程)間接通信(信箱通信就是把消息放信息里讓另一個(gè)進(jìn)程取)。

? ? ?(3) 管道通信。相當(dāng)于一個(gè)隊(duì)列形式的一個(gè)進(jìn)程在管道尾寫，另一個(gè)進(jìn)程在管道頭取，管道分為無名管道和有名管道。無名管道是用pipe函數(shù)創(chuàng)建的，只能用于子進(jìn)程之間的通信，有名管道用mkfifo函數(shù)創(chuàng)建用于任意兩個(gè)進(jìn)程之間通信，對管道的操作相當(dāng)于對文件的操作比如open函數(shù)打開管道close函數(shù)關(guān)閉管道等。

?

? ? ? 6. 線程概念與多線程模型

? ? ?有了線程之后，處理機(jī)調(diào)度的單位就成了線程。而資源的分配還是以進(jìn)程為單位。一個(gè)進(jìn)程的多個(gè)線程是公用代碼數(shù)據(jù)和文件資源的，但是不同的線程有不同的寄存器和棧。線程之間的通信比進(jìn)程通信方便因?yàn)橛泻枚噘Y源共用，線程的切換也比進(jìn)程的切換簡化的多。

（二）處理機(jī)調(diào)度

? ? ? 1. 調(diào)度的基本概念?

? ? ?調(diào)度分為作業(yè)調(diào)度，進(jìn)程調(diào)度，和中級調(diào)度。作業(yè)調(diào)度就是將外存上選中的作用分配內(nèi)存，創(chuàng)建進(jìn)程等批處理中幾分鐘調(diào)度一次，其他系統(tǒng)基本不需要作業(yè)調(diào)度，進(jìn)程調(diào)度就是決定就緒隊(duì)列中哪個(gè)進(jìn)程獲得處理機(jī)。中級調(diào)度主要功能是對換，即將內(nèi)存中某些就緒或阻塞的進(jìn)程交換到外存對換區(qū)，主要用來進(jìn)行內(nèi)存管理和擴(kuò)充。

? ? ? 2. 調(diào)度的基本準(zhǔn)則：

? ? CPU使用率要高，周轉(zhuǎn)時(shí)間，等待時(shí)間等要小等等。周轉(zhuǎn)時(shí)間等于等待時(shí)間加響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間就是各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間取平均值。帶權(quán)周轉(zhuǎn)時(shí)間等于周轉(zhuǎn)時(shí)間除以響應(yīng)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間就是各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間的求平均。

? ? ?3. 調(diào)度方式：

? ? ?非剝奪式和剝奪式兩種。剝奪式是有搶占原則的，一般是按優(yōu)先權(quán)原則，短作業(yè)優(yōu)先原則和時(shí)間片原則這三種之一進(jìn)行搶占的。

? ? ? 4. 典型調(diào)度算法

? ? ?先來先服務(wù)調(diào)度算法；短作業(yè)（短任務(wù)、短進(jìn)程、短線程）優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法(是FCFS和SJF的折中 ? ? ?響應(yīng)比=等待時(shí)間+要求執(zhí)行時(shí)間的和然后除以要求執(zhí)行的時(shí)間)；多級反饋隊(duì)列調(diào)度算法(多個(gè)就緒隊(duì)列賦予不同的優(yōu)先級優(yōu)先級越高時(shí)間片越短，新進(jìn)程加入后 ? ? 先放第一個(gè)隊(duì)列一個(gè)時(shí)間片完成不了就往下一個(gè)優(yōu)先級的隊(duì)列末尾放以此類推)。

（三）進(jìn)程同步

? ? ? 1. 進(jìn)程同步的基本概念

? ? ?多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，必須協(xié)同工作，相互配合，以共同完成某一項(xiàng)任務(wù)。同一種進(jìn)程是互斥關(guān)系，不同的進(jìn)程是同步關(guān)系。

? ? ? 2. 實(shí)現(xiàn)臨界區(qū)互斥的基本方法

? ? ?軟件實(shí)現(xiàn)方法；硬件實(shí)現(xiàn)方法。這時(shí)候還不是信號量的那種軟件實(shí)現(xiàn)而是程序員自己定義的，比如設(shè)置一個(gè)turn讓他等于進(jìn)程編號，從而使進(jìn)程輪流進(jìn)入臨界區(qū)。還有設(shè)置一個(gè)標(biāo)志位flag為0表示其他進(jìn)程未進(jìn)入臨界區(qū)等。硬件實(shí)現(xiàn)方法不懂。同步機(jī)制只要實(shí)現(xiàn)四大準(zhǔn)則就可以實(shí)現(xiàn)互斥，這四大原則就是:空閑讓進(jìn)、忙則等待、有限等待，讓權(quán)等待。

? ? ? 3. 信號量 ?

? ? ?信號量是操作系統(tǒng)提供的管理公有資源的手段，即PV操作。對于獨(dú)享設(shè)備有驅(qū)動(dòng)程序做PV操作。

? ? ?p操作的過程是：s=s-1；if(s<0){進(jìn)入等待隊(duì)列，自己阻塞進(jìn)程}

? ? ?v操作的過程是：s=s+1；if(s<0){從等待隊(duì)列取一個(gè)進(jìn)程；取出的進(jìn)程進(jìn)入就緒隊(duì)列，當(dāng)前進(jìn)程該干嘛干嘛}

? ? ?pv原語不能次序錯(cuò)誤，而且必須成對出現(xiàn)。信號量的定義是semaphore mutex；經(jīng)典同步問題有生產(chǎn)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題。

（四）?? 死鎖

? ? ??1.死鎖的概念

? ? ? 多個(gè)進(jìn)程并發(fā)執(zhí)行共享資源時(shí)，由于獨(dú)占資源被其他進(jìn)程占用，且其他進(jìn)程遇到同樣的問題，于是導(dǎo)致出現(xiàn)環(huán)形等待資源的情況，所有每個(gè)進(jìn)程都在等待無法執(zhí)行這就是死鎖。

? ? ?2. 死鎖處理策略 ：有四種方法預(yù)防死鎖、死鎖避免、死鎖檢測、解除死鎖。

? ? ?3. 死鎖預(yù)防： 就是破壞產(chǎn)生死鎖的任何四個(gè)必要條件之一。死鎖的四個(gè)必要條件是互斥、請求和保持、不剝奪、和環(huán)路等待。

? ? ?4. 死鎖避免：

? ? ?就是系統(tǒng)在給某進(jìn)程分資源時(shí)要保證一個(gè)安全順序，系統(tǒng)安全狀態(tài)一般用銀行家算法。銀行家算法即系統(tǒng)試探著把資源分配給進(jìn)程pi后修改可用資源的數(shù)目，還有每個(gè)進(jìn)程已分配的資源數(shù)目跟每個(gè)進(jìn)程還需的資源數(shù)目，然后執(zhí)行安全性算法，如果此次資源分配后，系統(tǒng)處于安全狀態(tài)才正式分配給進(jìn)程資源。否則試探分配作廢，讓進(jìn)程pi等待。注安全性算法即設(shè)置兩個(gè)向量。一個(gè)work向量一個(gè)finish向量，開始時(shí)work=available，然后找到一個(gè)need小于work的進(jìn)程，給該進(jìn)程分配資源后使work=work+allocation ，finish=true。然后循環(huán)直到所有進(jìn)程的finish狀態(tài)都為true則系統(tǒng)處于安全狀態(tài)。

? ? ?5. 死鎖檢測和解除：

? ? ? 就是檢測到發(fā)生死鎖之后，再采取手段解除死鎖，有剝奪法，回退法和殺死進(jìn)程這三種解除法。

貳：內(nèi)存管理

（一）?? 內(nèi)存管理基礎(chǔ)

? ? ?1.內(nèi)存管理概念

? ? ? 程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護(hù)。內(nèi)存管理的任務(wù)是記錄內(nèi)存的使用和空閑狀態(tài)，在進(jìn)程需要時(shí)為進(jìn)程分配內(nèi)存，用完后釋放內(nèi)存，已被進(jìn)程使用的內(nèi)存區(qū)域如何保護(hù)，如何在內(nèi)存不足支持進(jìn)程運(yùn)行的情況下進(jìn)行內(nèi)外存交換。

? ? 2. 程序的裝入：指從外存裝載在內(nèi)存

? ? ? 在讀入內(nèi)存時(shí)需要對地址部分做調(diào)整，即重定位裝入，該工作有OS專門的裝載程序負(fù)責(zé)。重定位分為靜態(tài)與動(dòng)態(tài)重定位，靜態(tài)重定位指在程序裝入內(nèi)存時(shí)由OS進(jìn)行浮動(dòng)項(xiàng)的定位，以后不再變化，每個(gè)可執(zhí)行程序的頭上有浮動(dòng)項(xiàng)說明表，表示地址的浮動(dòng)項(xiàng)。動(dòng)態(tài)重定位是指在裝入內(nèi)存時(shí)不進(jìn)行裝配，直接將程序裝入內(nèi)存，定位問題由系統(tǒng)提供的硬件解決，需要借助硬件支持。

? ? ?3.交換與覆蓋?

? ? ? 交換是指進(jìn)程或作業(yè)在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度，當(dāng)內(nèi)存緊張時(shí)系統(tǒng)按某種策略將某些進(jìn)程暫時(shí)移到外存，把外存某些進(jìn)程換進(jìn)內(nèi)存占據(jù)前者的內(nèi)存區(qū)域，外存分為文件區(qū)和交換區(qū)中其對換區(qū)是連續(xù)的。

? ? ?覆蓋是把程序劃分為若干個(gè)功能相對獨(dú)立的程序段。這些程序段是不會同時(shí)執(zhí)行的因此可以共享同一塊內(nèi)存區(qū)域，若干獨(dú)立的程序段叫覆蓋段。當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后面屬于同一覆蓋段的程序段調(diào)入內(nèi)存，覆蓋前面的程序段，相當(dāng)于內(nèi)存擴(kuò)大了。但是增加了程序員的負(fù)擔(dān)。因?yàn)槌绦騿T要向系統(tǒng)指明覆蓋結(jié)構(gòu)而且要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)。

?

? ? 4.連續(xù)分配管理方式

? ? ?單一連續(xù)分配；分區(qū)分配。單一連續(xù)分配是指內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)和用戶區(qū)，應(yīng)用程序裝入到用戶區(qū)可使用用戶區(qū)的全部空間，這種只適合單用戶單任務(wù)的OS。分區(qū)分配時(shí)把內(nèi)存劃分為若干個(gè)連續(xù)分區(qū)。分區(qū)分配又分為固定分區(qū)分配和動(dòng)態(tài)分區(qū)分配，固定分區(qū)分配就是分區(qū)的大小是固定的，可以相等也可以不等。采用分區(qū)表記錄分區(qū)的大小和使用情況。分區(qū)表的數(shù)據(jù)項(xiàng)有分區(qū)號，大小，起止，和狀態(tài)。動(dòng)態(tài)分區(qū)分配說白了就是用多少分多少。一般分區(qū)都是從地址低端開始的，動(dòng)態(tài)分區(qū)按尋找空閑分區(qū)的方法的不同又分為1、首次適應(yīng)法2、下次適應(yīng)法3、最佳適應(yīng)法。

? ? 首次適應(yīng)算法是按分區(qū)的先后次序(即從低地址開始)，從頭查找，找到符合要求的第一個(gè)分區(qū)，特點(diǎn)：較大的空閑分區(qū)被保留在內(nèi)存高端，每次分配時(shí)查找時(shí)間的開銷會增大。

? ? 下次適應(yīng)算法是從上次分配的分區(qū)開始查找，按分區(qū)的先后次序找，特點(diǎn)空閑分區(qū)分布的更均勻，但較大的空閑分區(qū)不易保留。

? ? 最佳適應(yīng)算法是每次找與其容量最接近的空閑分區(qū)，為了方便將按空閑區(qū)大小鏈接起來遞增排列利用了好多外碎片。

? ? 動(dòng)態(tài)分區(qū)還有動(dòng)態(tài)重定位分區(qū)分配就是在動(dòng)態(tài)分區(qū)的情況下，當(dāng)剩余零頭分區(qū)的和超過新任務(wù)要求的分區(qū)但是連續(xù)的空閑區(qū)容量卻達(dá)不到新任務(wù)要求時(shí)進(jìn)行緊湊的行為。就是將各個(gè)占用分區(qū)向內(nèi)存一端移動(dòng)，在另一端將空閑分區(qū)合并成一個(gè)空閑分區(qū)。

?

? ? 5. 非連續(xù)分配管理方式

? ? ?包括分頁管理方式；分段管理方式；段頁式管理方式。當(dāng)然一個(gè)操作系統(tǒng)只使用其中一種管理方式。

? ? ?頁式管理中將邏輯地址空間分成頁，物理內(nèi)存劃分為固定的同樣大小的(硬件設(shè)計(jì)時(shí)也框的大小已經(jīng)確定)頁框(塊)，程序可加載在不連續(xù)的塊中。程序中邏輯頁號和內(nèi)存中物理頁號的對應(yīng)表叫頁表，每個(gè)進(jìn)程一張。系統(tǒng)中有一張頁框使用表。系統(tǒng)中還有一張請求表里面存的是進(jìn)程id和該進(jìn)程頁表地址的對應(yīng)關(guān)系。邏輯地址像物理地址轉(zhuǎn)換的過程：邏輯地址由兩部分組成：頁號和頁內(nèi)地址。以該頁號在頁表中查找對應(yīng)的物理頁號，然后和頁內(nèi)地址拼起來就是物理地址。

? ? ?分段存儲的段表是由段號，段長，段基址組成。由邏輯地址轉(zhuǎn)換為物理地址的過程：邏輯地址由段號段內(nèi)位移組成，根據(jù)段號在段表中查找段基址然后加上位移量就是在內(nèi)存中的位置。

? ? ?段頁式存儲管理的邏輯地址由段號，段內(nèi)頁號，頁內(nèi)偏移地址組成。每個(gè)進(jìn)程一張段表。段表由段號，頁表大小(包含幾個(gè)頁表)，頁表首址組成。邏輯地址到物理地址的轉(zhuǎn)換過程：由段號在段表中查找到對應(yīng)的頁表首址再與邏輯地址的頁號相加，即是對應(yīng)頁表中該頁號的對應(yīng)項(xiàng)，將塊號和頁內(nèi)地址拼接即求的物理地址。

? ? ?分頁中控制寄存器中存的是頁表地址和長度，分段中控制寄存器中存的是段表使址和段表長度，段頁式中控制寄存器中存的是段表始址和段表長度，根據(jù)寄存器里的值才能得到頁表，段表。

（二）?? 虛擬內(nèi)存管理

? ? 1. 虛擬內(nèi)存基本概念

? ? ?借助于硬盤，一個(gè)進(jìn)程部分調(diào)入內(nèi)存即可運(yùn)行的情況下，用到哪個(gè)程序段將外存的調(diào)入內(nèi)存，對用戶來說是透明的任務(wù)內(nèi)存足夠大到可以執(zhí)行自己的程序這個(gè)思想便是虛擬內(nèi)存的思想，在虛擬存儲管理下，用戶的邏輯地址空間可遠(yuǎn)遠(yuǎn)大于物理空間。

?

? ? 2. 請求分頁管理方式

? ? ? 即在簡單頁式存儲管理的基礎(chǔ)上，增加了請求調(diào)頁和頁面置換功能。在請求分頁中的頁表比簡單頁式存儲的頁表要多一些字段，包括頁號、物理塊號、狀態(tài)位，訪問字段、修改位、保護(hù)位、外存地址。狀態(tài)位用來區(qū)分該頁是否在內(nèi)存，修改位用來表示該頁在調(diào)入內(nèi)存后有沒有被修改，保護(hù)位表示該頁是否可以修改，外存地址表示它在磁盤上現(xiàn)在存的位置，還有一個(gè)訪問字段表示最后一次訪問到現(xiàn)在的時(shí)間間隔用于頁面置換算法的。

?

? ? 3. 頁面置換算法

? ? 包括最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時(shí)鐘置換算法（CLOCK）。

? ? 最佳置換算法：選擇未來最常時(shí)間里不使用的頁，不能實(shí)現(xiàn)，因?yàn)橄到y(tǒng)不會預(yù)估未來。

? ? 先進(jìn)先出：選擇建立最早的頁面置換，但是如果這個(gè)頁經(jīng)常使用，那就會被反復(fù)調(diào)入和調(diào)出，會出現(xiàn)隨著頁框增多而中斷次數(shù)反而增加的現(xiàn)場也稱為Belady異常。

? ? 最近最久未使用LRU算法：最近最久沒有使用的頁面，相當(dāng)于訪問到一個(gè)把他排隊(duì)尾最后出，慢慢的隊(duì)頭就是最近沒使用的頁面淘汰隊(duì)頭即可。

? ? CLOCK置換算法：是LRU和FIFO的折中。也叫二次機(jī)會算法，

?

? ? 4. 頁面分配策略

? ? ?保證進(jìn)程能運(yùn)行的最小頁框，固定分配：給每個(gè)進(jìn)程分配固定數(shù)目的頁框；可變分配是預(yù)分配給進(jìn)程一定數(shù)目的頁框，OS控制一定數(shù)量的空閑頁框，在進(jìn)程執(zhí)行過程中，發(fā)生缺頁時(shí)os就分配給該進(jìn)程一個(gè)空閑的頁框。

?

? ? ? 5. 抖動(dòng)

? ? ? 抖動(dòng)現(xiàn)象和工作集。工作集指進(jìn)程在執(zhí)行過程中所訪問頁面的集合。駐留集指虛擬頁式管理中給進(jìn)程分配的物理塊數(shù)。引入工作集目的是依據(jù)進(jìn)程在過去的一段時(shí)間內(nèi)訪問的頁面來調(diào)整常駐集大小。抖動(dòng)是指內(nèi)存和外存進(jìn)行頻繁的調(diào)入調(diào)出，產(chǎn)生這種情況一是因?yàn)橄到y(tǒng)進(jìn)程數(shù)越來越多。每個(gè)的駐留集越來越少，因此缺頁中斷越來越多，這樣就會使cpu使用率越來越低，二是因?yàn)椴缓线m的調(diào)頁算法。

?

? ? ? 6. 請求分段管理方式

? ? ?此時(shí)的段表比簡單分段式管理的段表多了幾項(xiàng)包括：段名，段長，段基址，存取方式，訪問字段，修改字段，存在位，增補(bǔ)位，外存地址。存取方式指的是：執(zhí)行、只讀、讀/寫；存在位跟分頁管理中的狀態(tài)位是一樣的，增補(bǔ)位指示運(yùn)行過程中是否進(jìn)行過動(dòng)態(tài)增長。

叁：文件管理

（一）?? 文件系統(tǒng)基礎(chǔ)

? ? ? ?1. 文件概念 ?

? ? ?文件是具有文件名的一組相關(guān)元素的集合.可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件,有結(jié)構(gòu)的文件被看成事由一組記錄組成(學(xué)過數(shù)據(jù)庫都知道記錄是有若干相關(guān)的數(shù)據(jù)項(xiàng) ? ? ? ?組成),無結(jié)構(gòu)的文件即流式文件,無格式.

?

? ? ?2. ?文件結(jié)構(gòu) ?

? ? 文件結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu):

文件的邏輯結(jié)構(gòu)有三種 : 順序文件；索引文件；索引順序文件。

? ? (1)順序文件，其記錄是按某種順序排列所形成的,比如按存入時(shí)間的先后或關(guān)鍵字排列.對定長記錄方便直接存取,但對變長的記錄,就得從第一條的長度一直加到第 n條才能知道記錄的首址.

? ? (2)索引文件，記錄在文件中的位置由索引表來指向，其實(shí)是按某個(gè)記錄鍵來確定位置的,而索引表本身是定長的順序文件.所以給定關(guān)鍵字后就可以在索引表中折半 查找相應(yīng)的記錄在哪.索引項(xiàng)是由記錄的首址和長度構(gòu)成的.

? ? (3)索引順序文件, 將順序文件中的記錄先分為組，為順序文件建立一張索引表，在索引表里為每組中的第一個(gè)記錄建立索引項(xiàng)，記錄在文件中的位置由索引表和順 序來決定.

文件的物理結(jié)構(gòu)也有三種 :連續(xù)分配方式,鏈接分配方式,和索引分配方式.

? ? (1)連續(xù)分配:使得訪問速度快但它要求存儲空間是連續(xù)的而且必須事先知道文件的大小才能將文件存儲到外存.

? ? (2)鏈接分配方式:將屬于一個(gè)文件的多個(gè)離散盤塊鏈接成一個(gè)鏈表這樣所形成的一個(gè)物理文件稱為鏈接文件.而鏈接分配又分為隱式鏈接和顯示鏈接.隱式鏈接就是在該文件的離散物理塊中,下一個(gè)物理塊的地址由前一個(gè)物理塊給出.而每個(gè)文件的第一個(gè)物理塊和最后一個(gè)物理塊是存儲在文件目錄項(xiàng)中的…顯示鏈接是把用于鏈接文件的各個(gè)物理塊指針全存放到一張鏈接表中,每個(gè)FAT表項(xiàng)存的是本物理號對應(yīng)的下一個(gè)物理號是什么,一個(gè)磁盤只有一張這個(gè)表.叫做FAT文件分配表. 凡是屬于某一文件的第一個(gè)盤塊號，均作為文件地址被填入相應(yīng)文件的FCB的物理地址字段中.

? ? (3)索引分配方式:鏈接分配方式需要把FAT都調(diào)入內(nèi)存才能保證一個(gè)文件完整的被找到,而且一個(gè)個(gè)像下查找效率不高,索引方式為每個(gè)文件分配一個(gè)索引塊,把分配給該文件的所有盤塊號都記錄在該索引表中,將指向該索引塊的指針存入FCB中.索引分配還分為單級多級和混合索引分配方式.

至于邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的區(qū)別. 邏輯結(jié)構(gòu)是指每個(gè)記錄在文件中的位置,而物理結(jié)構(gòu)為邏輯結(jié)構(gòu)服務(wù),指文件在外存上存儲時(shí)，分配方式要保證文件在邏輯上一致而且檢索效率還有達(dá)到最高的結(jié)構(gòu).

?

? ? ?3.目錄管理

? (1)從文件管理的角度看,文件時(shí)由文件控制塊FCB和文件體組成的,文件控制塊保存文件的屬性信息基本包括文件名,文件結(jié)構(gòu),文件物理位置,控制信息(存取權(quán)限),管理信息(建立/修改日期等等).

? (2)目錄是由文件說明即FCB的集合構(gòu)成的.還有一種目錄的組成由于每次檢索文件是按名檢索的,索引把整個(gè)由文件說明構(gòu)成的目錄調(diào)入內(nèi)存是一種浪費(fèi),因此索引結(jié)點(diǎn)方式就誕生了,即將文件名和文件描述信息分開,將文件描述信息單獨(dú)形成一個(gè)稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu),在文件目錄的目錄項(xiàng)中僅存放文件名和對應(yīng)的指向索引結(jié)點(diǎn)的指針..

? (3)目錄結(jié)構(gòu)的形式有單級目錄結(jié)構(gòu),兩級目錄結(jié)構(gòu)和多級目錄結(jié)構(gòu)(也成為樹形目錄結(jié)構(gòu))。單級目錄結(jié)構(gòu)下文件不能重名查找速度也慢,兩級目錄是按用戶建立的,即 第一級目錄中存放用戶名和該用戶目錄的指針,雖然提高了檢索速度在不同用戶目錄中可以重名,但是不同用戶文件之間的共享不方便,于是多級目錄就出現(xiàn)了..根目錄還是按用戶分的,但下面有多重目錄.當(dāng)兩個(gè)或多個(gè)用戶共享文件時(shí),不再是樹形而是有向非循環(huán)圖.

（二）?? 文件系統(tǒng)實(shí)現(xiàn)

? ? 1. 文件系統(tǒng)層次結(jié)構(gòu)

? ? ?文件系統(tǒng)由三部分組成:與文件管理有關(guān)的軟件,被管理的文件,實(shí)施文件管理所需的數(shù)據(jù)結(jié)構(gòu).文件系統(tǒng)由四層構(gòu)成:最低層是基本輸入輸出層又叫設(shè)備驅(qū)動(dòng)層,下來依次是基本文件系統(tǒng)層,又稱物理I/O層.基本I/O管理程序?qū)?邏輯文件系統(tǒng)層.

? ? (1)基本I/O層:負(fù)責(zé)啟動(dòng)設(shè)備I/O以及對設(shè)備發(fā)來的中斷信號進(jìn)行處理.

? ? (2)物理I/O層:負(fù)責(zé)處理內(nèi)存和外存之間的數(shù)據(jù)塊交換.

? ? (3)基本I/O管理程序?qū)?選擇文件所在設(shè)備,進(jìn)行邏輯塊號到物理塊號的轉(zhuǎn)換,對文件空閑存儲空間的管理,指定I/O緩沖區(qū)等作用.

? ? (4)邏輯文件系統(tǒng)層:負(fù)責(zé)處理文件及記錄的相關(guān)操作.

? ? 這個(gè)名字起得不好,一般物理都是最底層,結(jié)果這是是第二層不好記..

?

? ? 2. 文件存儲空間的管理?

? ?(1) 空閑表法和空閑鏈表法

? ?空閑表法適用于連續(xù)分配方式.系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表,每個(gè)空閑區(qū)對應(yīng)于一個(gè)空閑表項(xiàng),其中包括表項(xiàng)序號,該空閑區(qū)的第一個(gè)盤塊號,該區(qū)的空閑盤塊數(shù)等信息,再將所有空閑區(qū)按其起始盤塊號遞增的次序排列.(對換區(qū)常用).空閑鏈表法.將空閑空間,以盤塊為單位拉成一條鏈.

? ?(2) ?位示圖法

? ? 二進(jìn)制的每一位表示磁盤中的一個(gè)盤塊,當(dāng)該位為1時(shí)表示已經(jīng)分配,為0表示空閑.注意給出的字號和位號是從0開始還是從1開始.書上是從1開始的.

? ? (3) 成組鏈接法

? ? 成組鏈接法將一個(gè)文件的所有空閑塊按每組100塊分成若干組,把每組的盤塊數(shù)目和該組的所有盤塊號計(jì)入到前一組的第一個(gè)盤塊中,第一組的盤塊數(shù)目和第一組的所有盤塊號計(jì)入到超級塊中.這樣每組的第一個(gè)盤塊就連接成了一個(gè)鏈表,而組內(nèi)的多個(gè)盤塊形成了堆棧.

? ? 成組鏈接法的分配和回收空閑塊都是所謂的頭取頭插,即分配從第一組開始分配,如果第一組只剩那個(gè)保存有下一組地址的塊,就把該塊存入超級塊,下一組變成第一組.回收的時(shí)候,如果第一組滿100個(gè),那么將第一組的盤塊數(shù)和盤塊號寫入該空閑塊中,然后將盤塊數(shù)等于1及棧頂塊號=該空閑塊號寫入超級塊中所以原來的第一組就變成了第二組…

（三）?? 磁盤組織與管理

? ? ?1. 磁盤的結(jié)構(gòu)

? ? ? ?磁盤由若干盤片組成,每個(gè)盤片有兩面.都可以記錄信息.每個(gè)盤面由若干磁道組成,不同半徑的同心圓叫磁道.每條磁道又分為若干個(gè)扇區(qū).每個(gè)扇區(qū)的大小相當(dāng)于一個(gè)盤塊.每個(gè)盤面的每一面都有一個(gè)磁頭.柱面指的是不同盤面相同半徑的磁道組成的圓柱..

? ? ? ?磁盤的類型可分為固定磁頭磁盤和移動(dòng)磁盤磁頭.磁盤的訪問時(shí)間由尋道時(shí)間,旋轉(zhuǎn)延遲時(shí)間和傳輸時(shí)間構(gòu)成.(1)尋道時(shí)間:指的是把磁頭移到指定磁道上所經(jīng)歷的時(shí)間.移動(dòng)一條磁道的時(shí)間是常數(shù).為0.2ms…

? ? (1)尋道時(shí)間等于啟動(dòng)磁臂的時(shí)間(常數(shù)2ms)+移動(dòng)n個(gè)磁道的時(shí)間..即0.2 * n? + 2

? ? (2)旋轉(zhuǎn)延遲時(shí)間為轉(zhuǎn)半轉(zhuǎn)所需的時(shí)間..一看都是平均數(shù)..

? ? (3)傳輸時(shí)間為所讀/寫的字節(jié)數(shù)b除以一條磁道上的字節(jié)數(shù)(除下來即表示b個(gè)字節(jié)需要轉(zhuǎn)幾轉(zhuǎn))再乘以一轉(zhuǎn)需要的時(shí)間..

?

? ? ?2. ?磁盤調(diào)度算法

? ? (1) ?先來先服務(wù)

? ? 沒有對尋到進(jìn)行優(yōu)化,導(dǎo)致平均尋道時(shí)間可能較長.

? ? (2) ?最短尋道優(yōu)先

? ? 只要有新的進(jìn)程要訪問的磁道與當(dāng)前磁頭所在磁道距離較近.就會滿足此進(jìn)程而可能導(dǎo)致某些離得遠(yuǎn)的一直得不到滿足.

? ? (3) ?掃描算法

? ? 又稱電梯調(diào)度算法,scan算法所考慮的下一個(gè)訪問對象是按電梯一樣的磁頭移動(dòng)方向下,距離正訪問磁道最近的對象.容易使距離兩端的進(jìn)程等待將近一來一回的掃描..

? ? (4) ?循環(huán)掃描算法

? ? CSCAN算法規(guī)定了磁頭必須單向移動(dòng).例如只允許磁頭由內(nèi)向外移動(dòng).移動(dòng)到最外磁道立即返回最里面又重新開始.

?

? ? ? 3.磁盤的存儲 ? ?

? ? ?可以按并行交叉存儲.即連續(xù)的物理塊分在不同的盤面上.一次就可以取多個(gè),也可以在一個(gè)盤面上按順序號存儲這種效率低.容易讀完1號處理完磁盤剛好旋轉(zhuǎn)的把2號錯(cuò)過去,所以還有一種是將物理號連續(xù)的間隔起來排列.

肆：輸入輸出（I/O）管理

?（一）?? I/O管理概述

? ? ? 1. I/O設(shè)備的分類

? ? ? ? (1) ? 按傳輸速率分可分為低速設(shè)備(鍵盤鼠標(biāo)等)，中速設(shè)備(激光打印機(jī)等)，高速設(shè)備(磁盤機(jī)等)。

? ? ? ? (2) ? 按信息交換的單位分可分為塊設(shè)備(有結(jié)構(gòu)例如磁盤)和字符設(shè)備(常采用中斷驅(qū)動(dòng)方式)

? ? ? ? (3) ? 按設(shè)備的共享方式可分為獨(dú)占設(shè)備(一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問:例如打印機(jī))，共享設(shè)備(一段時(shí)間內(nèi)允許多個(gè)進(jìn)程同時(shí)訪問:例如磁盤)，虛擬設(shè)備(通過虛擬技術(shù)將獨(dú)占設(shè)備變?yōu)槿舾膳_邏輯設(shè)備。)

?

? ? ? ?2. ?I/O管理目標(biāo)

? ? ? ? ? 合理分配設(shè)備、提高設(shè)備與CPU，各外部設(shè)備之間的并行性，提供使用方便且獨(dú)立與設(shè)備的界面。

?

? ? ? ?3. ?I/O管理功能

? ? ? ? (1) ? 動(dòng)態(tài)的紀(jì)錄各種設(shè)備的狀態(tài)

? ? ? ? (2) ? 設(shè)備分配與回收

? ? ? ? (3) ? 實(shí)施設(shè)備驅(qū)動(dòng)和中段處理的工作

?

? ? 4. ? ?I/O應(yīng)用接口

? ? (1) ?設(shè)備和設(shè)備控制器的接口：設(shè)備和cpu之間不是直接通信的而是夾著一個(gè)設(shè)備控制器，設(shè)備與設(shè)備控制器是靠三根線相連的，數(shù)據(jù)信號線，控制信號線和狀態(tài)信號線，數(shù)據(jù)信號線用于在設(shè)備和設(shè)備控制器之間傳送數(shù)據(jù)信號，控制信號線傳送由設(shè)備控制器向I/O設(shè)備發(fā)送控制信號，狀態(tài)信號線用于傳送設(shè)備當(dāng)前狀態(tài)的信號。

? ? (2) ?設(shè)備控制器：控制一個(gè)或多個(gè)I/O設(shè)備，其基本功能有接收和識別(cpu發(fā)的)命令，數(shù)據(jù)交換(與cpu或與設(shè)備數(shù)據(jù)交換)，標(biāo)示和報(bào)告設(shè)備的狀態(tài)(給cpu發(fā))地址識別，數(shù)據(jù)緩沖，差錯(cuò)控制。

? ? (3) ?設(shè)備控制器由三部分組成：設(shè)備控制器與處理器的接口(由數(shù)據(jù)線連接DMR和控制狀態(tài)寄存器，控制線，和地址線組成)，設(shè)備控制器與設(shè)備的接口(多個(gè)設(shè)備接口，每個(gè)設(shè)備接口由數(shù)據(jù)控制和狀態(tài)三種信號)，I/O邏輯(當(dāng)cpu啟動(dòng)一個(gè)設(shè)備時(shí)，將啟動(dòng)命令發(fā)給I/O邏輯同時(shí)通過地址線給I/O邏輯由它進(jìn)行譯碼。。譯出命令后對所選設(shè)備進(jìn)行控制。所以地址線和控制線是直接跟I/O邏輯相連的。

?

? 5. ? ?I/O通道 ?

? ? ?I/O通道是特殊的處理機(jī)。它具有執(zhí)行I/O指令的能力，并通過執(zhí)行通道程序來控制I/O操作，它的指令單一主要與I/O操作相關(guān)的指令，通道沒有自己的內(nèi)存，它和CPU共享內(nèi)存。通道又分為字節(jié)多路通道，數(shù)組選擇通道，和數(shù)組多路通道。

? ? (1) ?數(shù)組選擇通道:又稱告訴通道，在物理上可以連接多個(gè)設(shè)備，但某一段時(shí)間內(nèi)通道只能選擇一個(gè)設(shè)備進(jìn)行工作

? ? (2) ?數(shù)組多路通道:當(dāng)某設(shè)備進(jìn)行數(shù)據(jù)傳送時(shí)，通道只為該設(shè)備服務(wù)，當(dāng)設(shè)備在執(zhí)行尋址等控制性動(dòng)作時(shí)，通道掛起該設(shè)備的通道程序，去為其他設(shè)備服務(wù)。

? ? (3) ?字節(jié)多路通道:用于大量低速設(shè)備，與設(shè)備之間數(shù)據(jù)傳送的基本單位是字節(jié)，為一個(gè)設(shè)備傳送一個(gè)字節(jié)后，又可以為另個(gè)設(shè)備傳送一個(gè)字節(jié)。數(shù)組多路通道傳輸?shù)幕締挝皇菈K。而且一次只能有一個(gè)設(shè)備在傳輸數(shù)據(jù)。

?

? 6. ? I/O控制方式

? ? (1) ?程序I/O方式：忙等方式。

? ? (2) ?中段驅(qū)動(dòng)I/O方式：當(dāng)某進(jìn)程要啟動(dòng)某個(gè)I/O設(shè)備工作時(shí)，便由cpu向相應(yīng)的設(shè)備控制器發(fā)出一條I/O命令，然后立即返回繼續(xù)執(zhí)行原來的任務(wù)，此時(shí)，CPU和 I/O設(shè)備并行操作。以字節(jié)為單位進(jìn)行I/O。

? ? (3) ?DMA I/O方式：直接存儲器訪問方式數(shù)據(jù)傳輸?shù)膯挝皇菈K，數(shù)據(jù)之間在設(shè)備和內(nèi)存中進(jìn)行交換，僅塊傳輸?shù)拈_始和結(jié)束時(shí)才需要CPU干預(yù)。(替代了設(shè)備控制 器)。DMA控制器中有四類寄存器：命令寄存器(存cpu發(fā)的控制命令或設(shè)備的狀態(tài))，內(nèi)存地址寄存器，數(shù)據(jù)寄存器(緩沖數(shù)據(jù)作用)，數(shù)據(jù)計(jì)數(shù)器(存本次要讀的字節(jié)數(shù))。

? ?(4) ?I/O通道控制方式：通道是通過執(zhí)行通道程序，并與設(shè)備控制器共同實(shí)現(xiàn)對I/O設(shè)備的控制的。通道指令格式為命令

? ? ? ? ? 1）操作碼：規(guī)定了指令所執(zhí)行的操作。

? ? ? ? ? 2）內(nèi)存地址：標(biāo)明讀操作和寫操作時(shí)的內(nèi)存首址

? ? ? ? ? 3）計(jì)數(shù)：表示本條占領(lǐng)所要讀或?qū)憯?shù)據(jù)的字節(jié)數(shù)

? ? ? ? ? 4）通道程序結(jié)束位P：用于表示通道程序是否結(jié)束

? ? ? ? ? 5）記錄結(jié)束標(biāo)志R。?

（二）?? I/O核心子系統(tǒng)

? ? 1. ?高速緩存與緩沖區(qū)

? ? ? ? ? ?引入緩沖區(qū)的目的:改善CPU與外圍設(shè)備之間的速度不匹配矛盾；減少對CPU的中斷次數(shù)(一個(gè)位做緩沖和塊做緩沖的差距)，提高CPU和I/O設(shè)備的并行性。

? ? ?緩沖分為：單緩沖、雙緩沖、循環(huán)緩沖、和緩沖池

? ? ?單緩沖屬于臨界資源，而且cpu與設(shè)備無法進(jìn)行并行操作。單緩沖只允許各自進(jìn)程獨(dú)占。雙緩沖一般就有發(fā)送緩沖區(qū)和接收緩沖區(qū)。循環(huán)緩沖鏈成一個(gè)環(huán)形，不過 ? ? ?需要四個(gè)指針，比如分別指向用于讀進(jìn)程和寫進(jìn)程的已用和正在訪問的單元，循環(huán)緩沖進(jìn)程屬于專用緩沖區(qū)。不是所有的進(jìn)程都能用的。所以系統(tǒng)會有多個(gè)這種緩沖區(qū)。開銷比較大。其實(shí)單緩沖和多緩沖也是得設(shè)置多個(gè)。因?yàn)槎嗟莱绦蛞窃O(shè)一個(gè)緩沖區(qū)豈不是沒有并行性了。

? ? ?緩沖池是個(gè)好想法：里面有多個(gè)進(jìn)程可以共享的緩沖區(qū)。不過既然要使多個(gè)進(jìn)程共享肯定結(jié)構(gòu)比較復(fù)雜。有空閑緩沖區(qū)，裝滿輸入數(shù)據(jù)的緩沖區(qū)，裝滿輸出數(shù)據(jù)的緩沖區(qū)還有用于收容輸入輸出數(shù)據(jù)的緩沖區(qū)。

?

? ? ?2. ?設(shè)備分配

? ? ? ? ?設(shè)備分配中設(shè)計(jì)到4張表的數(shù)據(jù)結(jié)構(gòu)，設(shè)備控制表DCT，控制器控制表COCT，通道控制表CHCT，系統(tǒng)設(shè)備表SDT，DCT主要包括設(shè)備標(biāo)示、設(shè)備類型(塊設(shè)備還是字符設(shè)備)、設(shè)備狀態(tài)、等待該設(shè)備的進(jìn)程、指向控制器表的指針。COCT同理，包括控制器標(biāo)示符，控制器狀態(tài)，與控制器連接的通道指針，等待控制器的進(jìn)程隊(duì)列。CHCT同上，不過它包含與該通道相連的控制器表的首地址。SDT表里包含設(shè)備控制表，還包含驅(qū)動(dòng)程序入口地址等。

? ? 設(shè)備管理軟件具有層次結(jié)構(gòu)，細(xì)分為四級，設(shè)備中斷處理程序，設(shè)備驅(qū)動(dòng)程序，與設(shè)備無關(guān)的操作系統(tǒng)軟件，用戶級軟件。

? ? 邏輯設(shè)備名與物理設(shè)備是有個(gè)映射表的叫邏輯設(shè)備表，基本上一個(gè)系統(tǒng)一個(gè)。或者一個(gè)用戶一個(gè)， 數(shù)據(jù)項(xiàng)有邏輯設(shè)備名，物理設(shè)備名和驅(qū)動(dòng)程序入口地址。

?

? ? 3.假脫機(jī)技術(shù)（SPOOLing）

? ? ? ? 假脫機(jī)技術(shù)用輔存的輸入輸出井替代了以前脫機(jī)技術(shù)的外圍設(shè)備機(jī)的作用，使對I/O設(shè)備的操作變成對輸入輸出井的操作。多個(gè)進(jìn)程可以同時(shí)獨(dú)享設(shè)備實(shí)現(xiàn)了虛擬設(shè)備的功能，其實(shí)設(shè)備并沒有分給某個(gè)進(jìn)程，而是進(jìn)程將要處理的數(shù)據(jù)放到輸入輸出井中，每個(gè)進(jìn)程在輸入輸出井中分配的是一個(gè)存儲區(qū)和一張I/O請求表。

操作系統(tǒng)理論學(xué)習(xí)筆記