作業系統核心要點

作業系統定義：是一組控制和管理計算機硬體和軟體資源合理地對各類作業進行排程以及友善使用者使用計算機的程式集合

作業系統作用：（1）os作為使用者與計算機硬體系統之間的接口，（2）os作為計算機系統資源的管理者，（3）os實作了對計算機資源的抽象。

作業系統特征：并發（是指兩個或多個事件在同一時間間隔内發生），共享，虛拟，異步。

作業系統主要功能：處理機管理功能，存儲器管理功能（記憶體配置設定、位址映射、記憶體保護、記憶體擴充），裝置管理功能，檔案管理功能，作業系統與使用者之間的接口。

單批道處理系統（自動性、順序性、單道性）缺點：系統中的資源得不到充分利用；多批道處理系統（排程性、無序性、多道性）優點：資源使用率高，系統吞吐量大，缺點：平均周轉時間長，無互動能力；分時系統unix（多路性、獨立性、及時性、互動性）：允許使用者以互動方式使用計算機作業系統；實時系統（實時性、可靠性）。

程序和程式的差別：(1)程式是一個靜态的概念，而程序是一個動态的概念。(2)程式可以作為一種軟體資料長期存在，而程序是有一定生命期的。程式是永久的，程序是暫時的。(3)程序具有并發性，而程式具有順序性。(4)程序是資源配置設定和排程的基本機關(5)一個程式對應多個程序，一個程序為多個程式服務。

程序的實質是程序實體的運作過程，是系統進行資源配置設定和排程的一個機關；程序是程式在處理機上的一次執行過程，具有生命期。

程序的特征：動态性、并發性、獨立性、異步性。

程式并發執行的特征：間斷性，失去封閉性，不可再現性

程序的阻塞與喚醒：向系統請求共享資源失敗；等待某種操作完成；新資料尚未到達；等待新任務的到達

PCB（以隊列的形式存放）的作用（1）作為獨立運作基本機關的标志（2）能實作間斷性運作方式（3）提供程序管理所需要的資訊（4）提供程序排程所需要的資訊。（程序控制塊（PCB）+程式段+相關資料段=程序實體）

兩種形式的制約關系：間接互相制約關系：互斥（競争資源），一個信号量；直接互相制約關系：同步（程序合作），兩個信号量。

同步機制應遵循的規則：空閑讓進、忙則等待、有限等待、讓權等待。

信号量的初值表示系統中某類資源的數目；信号量<0表示該類資源已經配置設定完畢，絕對值表示在該信号量連結清單中已阻塞程序的數目；信号量初值為1，表示隻允許一個程序通路臨界資源，此時的信号量轉化為互斥信号量。   對信号量S每執行一次P操作，則信号量S的值就減1，當S的值<0時，執行P操作的程序的狀态就置為阻塞态，把相應的PCB連入該信号量隊列的末尾,并且該程序放棄處理機。

帶權周轉時間=周轉時間/服務時間

FCSF（先來先服務）算法（不利于短作業），SJF（短作業優先）算法（必須預知作業的運作時間，不利于長作業，無法實作人機互動，沒有考慮作業的緊迫度），PSA（優先級排程）算法，HRRN（高響應比優先排程）算法，輪轉（RR）算法（用于分時系統，不适合作業排程）。。

優先權（響應比）=（等待時間+要求服務時間）/要求服務時間

産生死鎖的原因：競争不可搶占性資源；競争可消耗資源；程序推進順序不當。

死鎖的定義：如果一組程序中的每一個程序都在等待僅由該組程序中的其他程序才能引發的事件，那麼該組程序就是死鎖的。

死鎖産生的必要條件：互斥條件；請求和保持條件；不可搶占條件；循環等待條件。

處理死鎖的方法：預防死鎖；避免死鎖；檢測死鎖（采用資源配置設定圖）；解除死鎖（搶占資源、終止或撤銷程序）。

預防死鎖的方法：摒棄請求和保持條件（采用靜态資源配置設定法），摒棄不可搶占條件（采用資源暫時釋放政策）摒棄循環等待條件（采用有序資源配置設定方法）

注：R類資源共m個，n個程序互斥使用，每個程序對R類資源最大需求量為w，設M=n*（w-1）+1，n<m可能會發生死鎖，m>=M絕對不會發生死鎖。

連續配置設定存儲管理方式：單一連續配置設定（系統區放在記憶體的低址部分），固定分區配置設定（造成存儲空間的浪費），動态分區配置設定（解決碎片問題，提高記憶體使用率，涉及分區配置設定中所用的資料結構、分區配置設定算法和分區的配置設定與回收操作問題），動态可重定位分區配置設定算法（緊湊、動态重定位）。

基于順序搜素的動态分區配置設定算法：首次适應（FF）算法（傾向于優先利用記憶體中的低址部分的空閑分區），循環首次适應（NF）算法（基于ff算法從上次找到的空閑分區的下一個空閑分區開始查找），最佳适應（BF）算法（空間分區大小，從小到大），最壞适應（WF）算法（從大到小）。

動态重定位（解決位址映射問題）：位址變換過程是在程式執行期間，随着對每條指令或資料的通路自動進行的。

離散配置設定：分頁存儲管理方式（一維，頁長=塊長，邏輯位址=頁号+頁内位址，實體位址=P*L+d，頁面大小L，頁号P，頁内位址d，頁表的作用是實作從頁号到實體快号的位址映射，每一個程序一個頁表，通路兩次記憶體）分段存儲管理方式（其邏輯位址是由段号和段内位址組成二維，解決資料的共享和保護，通路兩次記憶體）、段頁式存儲管理方式（二維，通路三次記憶體，需配置一段表寄存器，用分段的方式管理使用者空間，分頁的方式管理實體記憶體空間）。

分頁和分段的主要差別：頁是資訊的實體機關段是資訊的邏輯機關、頁的大小固定且由系統決定段的大小取決于使用者程式、分頁的使用者程式位址空間是一維的，分段的作業位址空間是二維的。

虛拟存儲器定義：具有請求調入功能和置換功能，能從邏輯上對記憶體容量進行擴充的一種存儲系統（其邏輯容量由記憶體容量和外存容量之和決定的，計算機體系結構決定虛拟存儲器的位址空間）。

虛拟存儲器特征：多次性（最本質）對換性，虛拟性，離散性。

産生抖動的原因：同時在系統中運作的程序太多，由此配置設定給每一個程序的實體塊太少，不能滿足程序正常運作的基本要求，緻使每個程序在運作時，頻繁的出現缺頁，必須請求系統将所缺之頁調入記憶體。用工作集來解決抖動問題

中斷：是指cpu對I/O裝置發來的中斷信号的一種響應，與陷入的主要差別是信号的來源，即是來自cpu外部還是内部。

對I/O裝置的控制方式：使用輪詢的可程式設計I/O方式；使用中斷的可程式設計I/O方式；直接存儲器通路方式（DMA）；I/O通道控制方式。

裝置的分類：獨占裝置，共享裝置，虛拟裝置。

假脫機技術：将獨占裝置改造成共享裝置，進而提高了裝置使用率和系統效率。Spooling系統建立在通道技術和多通道程式技術上，一高速随機外存為後援存儲器

SPOOLing系統：輸入井和輸出井、輸入緩沖區和輸出緩沖區、輸入程序和輸出程序、井管理程式。特點：提高了I/O的速度；将獨占裝置改造為共享裝置；實作了虛拟裝置功能。

磁盤排程算法：先來先服務（FCFS）（優點：公平簡單不會出現饑餓現象，缺點平均尋道時間長），最短尋道時間優先（SSTF）（優點：尋道時間性能好，缺點會出現饑餓現象），掃描（SCAN）算法（能避免饑餓現象，缺點：尋道性能差），循環掃描（CSCAN）

磁盤通路時間：尋道時間，旋轉延遲時間（1/2轉速），傳輸時間（位元組數/轉速*扇區或位元組數/傳輸速率）

檔案邏輯結構類型：記錄式檔案（有結構）；流式檔案（無結構），以位元組為機關。

按檔案的組織方式分類：順序檔案（适合批量處理，增加删除難），索引檔案（容易查找），索引順序檔案。

檔案的實體結構類型：順序檔案，連結檔案，索引檔案

檔案控制塊（FCb）:用于描述和控制檔案的資料結構有三類資訊：基本資訊，存取控制，使用資訊

檔案共享：基于有向無循環圖實作檔案共享，（硬連結會改變索引節點的值）利用符号連結實作檔案

共享（軟連接配接不會改變索引結點的值）

外存的組織方式：連續組織方式；連結組織方式；索引組織方式。

檔案存儲空間的管理：空閑表法；位示圖法；成組連結法（unix系統采用）。

位示圖法：盤塊号b=n(i-j)+j，n表示每行的位數，i行，j列。盤塊回收：i=(b-1)DIV n+1，j=(b-1)MOD n+1。

事務：一緻性、-隔離性、持久性、原子性。

銀行家算法：

Need=Max-Allocation,Work=Work+Allocatiom

Process  Max    Allocation  Available

P0 0 0 4  4    0 0 3 2     1 6 2 2

P1 2 7 5  0    1 0 0 0

P2 3 6 10 10   1 3 5 4

P3 0 9 8  4    0 3 3 2

P4 0 6 6  10   0 0 1 4

1）該狀态是否安全？

2）若程序P2提出請求Request（1，2，2，2）後，系統能否将資源配置設定給它？

解：1）利用安全性算法對上面的狀态進行分析（如下表所示），找到了一個安全序列{P0，P3，P4，P1，P2}或{P0，P3，P1，P4， P2}，故系統是安全的。

資源情況：Work Need Allocation Work+Allo Finish

程序:    ABC D  ABCD  ABCD     A B C D   

P0       162 2  0012  0032     1 6 5 4   true

P3       165 4  0652  0332     1 9 8 6   true

P4       198 6  0656  0014     1 9 9 10  true

P1       199 10 1750  1000     2 9 9 10  true

P2       299 10 2356  1354     3 12 14 14 true

2) P2送出請求向量Request（1，2，2，2）後，系統按照銀行家算法進行檢查：

Request2（1，2，2，2）≤Need2（2，3，5，6）；Request2（1，2，2，2）≤Available（1，6，2，2）；系統先假定可為P2配置設定資源，并修改Available，Allocation2和Need2向量：Available=（0，4，0，0）Allocation2=（2，5，7，6）Need2=(1,1,3,4) ；進行安全性檢查：此時對所有程序，條件Needi≦ Available（0，4，0，0）都不成立，即Available不能滿足任何程序的請求，故系統進入不安全狀态。是以，當程序P2提出請求Request（1，2，2，2）後，系統不能将資源配置設定給它。

磁盤容錯技術：第一級容錯技術防止因磁盤表面的缺陷所造成的包含雙份目錄雙份檔案配置設定表，熱修重複定向，寫後讀校驗。第二級容錯技術防止磁盤驅動器和控制器的故障，包含磁盤鏡像（在同一控制器下，增加一完全相同的驅動器），磁盤雙工。第三級是基于叢集技術的容錯技術，三種工作模式：熱備份，互為備份，公用磁盤

導緻一個程序建立另一個程序的典型事件：使用者登入，作業排程，提供服務，應用請求

P、V操作：①有三個程序，程序A1：将卡片輸入到緩沖區B1，程序A2：将經過加工處理的卡片輸入到緩沖區B2，程序A3：将緩沖區B2的卡片輸出。②直接制約關系；③A1,A2,A3為程序，分别為PA1,PA2,PA3,兩個緩沖區為資源，定義信号量semaphore Space B1=1，Space B2=1，卡片也為資源，定義信号量semaphore mutex1=0,mutex2==0，

void PA1(){     void PA2(){        voidPA3(){

do{            do{             do{

wait(Space B1)     wait(mutex2)     wait(mutex1)

輸入卡片         輸入卡片         取卡片

Signal(mutex1)    signal(Space B2)  signal(Space B1)

}While(TRUE)     }While(TRUE)     wait(space B2)

}               void main()       輸入卡片

                Cobegin        signal(mutex2)

               PA1();PA2();PA3();  }while(TRUE)