2014年華北電力大學計算機專業考研專業課複習3

　　處理機排程的基本概念 就緒佇列中只要有兩個以上的程序存在就會競爭CPU的使用權。如果只有1個CPU可用，那麼就必須選擇下一個要執行的程序。完成選擇工作的這一部分稱為排程程式（scheduler），該程式使用的演算法稱為排程演算法（scheduling algorithm）。

　　排程方式及演算法 不可搶佔排程方式：一個程序若被選中，就一直執行下去，直到它被阻塞（I/O，或正在等待其他的程序），或主動地交出CPU。可搶佔排程方式：當一個程序在執行時，排程程式可以打斷它。另外，在其他的一些情形下，如就緒佇列中有程序的優先順序高於當前執行程序的優先順序，也可能立即進行排程。

　　演算法 先來先服務（First Come First Served，FCFS； First In First Out，FIFO）：按照作業到達的先後次序進行排程；不可搶佔方式：當前程序佔用CPU，直到執行完或被阻塞，才讓出CPU給另外一個程序；在程序被喚醒後（如I/O完成），並不立即恢復執行，而是放在就緒佇列的末尾；優點：簡單，易於理解也易於實現。現實生活中應用廣泛：排隊。短作業優先（Shortest Job First，SJF），設計目標是改進FCFS演算法，減少平均週轉時間；SJF演算法要求作業在開始執行時預計執行時間，對預計執行時間短的作業優先分派處理器兩種實現方案：不可搶佔方式：當前作業在執行時不會被打斷，只有執行完畢或阻塞時，才讓出CPU；可搶佔方式：如果一個新的短作業到來，其執行時間小於當前正在執行作業的剩餘時間，則搶佔CPU執行，稱為SRTF（Shortest Remaining Time First）。一種動態優先權演算法 最高應比作業優先演算法是對FCFS方式和SJF方式的一種綜合平衡。響應比R定義為系統對作業的響應時間與作業要求執行時間的比值R＝響應時間 / 要求執行時間＝(作業等待時間＋需執行時間)/ 需執行時間＝1＋已等待時間 / 需執行時間＝1＋W/T優先順序排程演算法是從就緒佇列中選出優先級別最高的程序。讓它佔用CPU執行靜態優先順序：靜態優先順序排程演算法是指在建立 程序時就確定下來的，而且在程序的整個執行 期間其優先順序是維持不變的動態優先順序：動態優先順序是隨著程序的推進而不斷變化的 (例如HRN)在時間片輪轉演算法（Round-Robin，RR）中，將所有的就緒程序按照FCFS原則，排成一個佇列每次排程時將處理器分派給隊首程序，讓其執行一小段CPU時間（時間片time quantum）在一個時間片結束時，如果程序還沒有執行完的話，將發生時鐘中斷，在時鐘中斷中，程序排程程式將暫停當前程序的執行，並將其送到就緒佇列的末尾，然後執行當前的隊首程序如果一個程序在它的時間片用完之前就已結束或被阻塞，那麼立即讓出CPU多級佇列演算法（Multilevel Queue）引入多個就緒佇列，透過各個佇列的區別對待，達到一個綜合的排程目標。根據程序的性質或型別的不同，將就緒佇列再分為若干個子佇列，如系統程序、使用者互動程序、批處理程序等；不同的佇列可以有不同的優先順序；不同的佇列可以採用各自不同的排程演算法，如前臺式程序可採用RR演算法，後臺的批處理程序可採用FCFS演算法。在各個佇列之間也必須進行排程：固定優先順序排程：按照各種型別的程序的優先級別從高到低地進行，先執行最高優先順序的所有程序，再執行次一級所有程序，依此類推。 問題：可能導致“飢餓”；時間片方法：把CPU時間按比例分配給不同的佇列，然後再由各個佇列的排程演算法去排程，如80％給前臺的互動式程序佇列（RR演算法），20％給後臺的批處理程序佇列FCFS）。多級反饋佇列演算法 (Multilevel Feedback Queue)即根據一個程序的執行反饋資訊，動態地調整它所在的佇列。三種優先級別，3最高、1最低，三個就緒佇列。時間片長度分別為N、2N和4N；新程序進入記憶體後，優先順序為3，加入佇列3的末尾，按FCFS演算法排程；若一個時間片內未能執行完，則優先順序降為2，加入到佇列2的末尾，同樣按FCFS演算法排程；依此類推。僅當較高優先順序的佇列為空，才排程較低優先順序的佇列中的程序執先級的佇列，則搶先執行新程序。在實時系統中，對時間的要求是非常嚴格的。典型的例子是：一個或多個外部的物理裝置定期或不定期地生成激勵訊號，而計算機必須在一定的時間期限內做出恰當的反應。根據任務的開始截止時間確定任務優先順序，截止時間越早，優先順序越高。可用於搶佔和非搶佔式。最低鬆弛度優先演算法該演算法是根據任務緊急(或鬆弛)的程度，來確定任務的優先順序。任務的緊急程度愈高，為該任務所賦予的優先順序就愈高，以使之優先執行。鬆弛度＝必須完成時間－本身執行時間－當前時間

　　死鎖的基本概念 在一組程序中，每個程序都佔用著若干個資源，同時又在等待得到該組程序中另一程序所佔用的資源，因而造成的所有程序都無法進展下去的現象，這種現象稱為死鎖，這一組程序就稱為死鎖程序。死鎖的4個必要條件：互斥條件：在任何時刻，每一個資源最多隻能被一個程序所使用；請求和保持條件：程序在佔用若干個資源的同時又可以請求新的資源；不可搶佔條件：程序已經佔用的資源，不會被強制性拿走，而必須由該程序主動釋放；環路等待條件：存在一條由兩個或多個程序所組成的環路鏈，其中每一個程序都在等待環路鏈中下一個程序所佔用的資源。

　　死鎖的處理策略 忽略死鎖，無為而治Windows、UNIX檢測並恢復動態避免 小心的進行資源分配預防 破壞死鎖的4個必要條件之一銀行家演算法在小鎮上，有一位銀行家和一些需要貸款服務的客戶。銀行家根據每一位客戶的背景情況，為之設定了相應的最高貸款限額。現在的問題是銀行家必須設計出一種演算法，以保證借貸過程的順利進行，也就是說，當某個客戶提出了一個貸款申請時，該演算法必須判斷，如果批准了這個申請，是否會導致一種不安全的狀態，如果是的話，就拒絕該申請；如果否的話，就批准該申請。求安全序列。

　　檔案和檔案系統。長期儲存資訊有三個基本要素，能夠儲存大量資訊，實用資訊的程序終止時，資訊仍舊存在，多個程序可以併發存取資訊，檔案是受作業系統管理的。有關檔案的構造、命名、存取、使用、保護、實現和管理方法都是作業系統設計的主要內容。從總體上看，作業系統中處理檔案的部分稱為檔案系統（file system）。檔案的三種結構，位元組序列記錄序列

　　檔案的邏輯結構。檔案的邏輯結構一般是位元組流；對於檔案系統而言，必須將這種位元組流（一個連續的邏輯地址空間）儲存在磁碟的某些扇區中，這種存放

　　目錄管理。通常透過檔案目錄實現檔案的組織、管理的要求，(1)實現按名存取(根據使用者給出的ASCII形式的檔名（路徑名），定位到相應的檔案控制塊。)(2)提高對目錄的檢索速度(3)檔案共享(4)允許檔案重名(5)長檔名。檔案控制塊（FCB）描述和控制檔案的資料結構，存放了為管理檔案所需的所有有關資訊。檔案控制塊是檔案存在的標誌，檔案目錄，件控制塊的有序集合稱為檔案目錄，一個檔案控制塊就是一個檔案目錄項。檔案目錄也被看成一個檔案，稱為目錄檔案，檔案控制塊的內容(1)基本資訊類；檔名，檔案物理位，檔案邏輯結構，檔案的物理結構。(2) 存取控制資訊類(3) 使用資訊類

　　兩種目錄構成方法。單級目錄，兩級目錄結構，多級目錄結構，路徑名，檔案訪問過程：利用檔名查詢檔案目錄，根據FCB或i結點所記錄的檔案物理地址（盤塊號），得到檔案在磁碟上的物理地址，將檔案讀入記憶體。查詢方式線性檢索：線性檢索，慢HASH：利用檔名變換為檔案目錄索引值，不適用於萬用字元查詢

　　檔案共享。如果系統不提供檔案共享，那麼凡是需要該檔案的使用者，都須各自備有此檔案的副本，對儲存空間造成巨大浪費。——基於索引結點的共享方式——利用符號鏈實現檔案共享。引用索引結點後，除檔名外的資訊儲存在i結點上。因此不管是wang使用者還是li使用者對檔案進行修改，這種修改對i結點發生作用。因而這種改變，是其他使用者可見的。i結點中，有一個連結計數count。用於表示連結到本索引結點上的使用者目錄項的數目。利用符號鏈實現檔案共享。為使B能共享C的一個檔案F，可以由系統建立一個LINK型別的新檔案，也取名為F，並將F寫入B的目錄中，以實現B的目錄與檔案F的連結。在新檔案中只包含被連結檔案F的路徑名。這樣的連結方法被成為符號連結。新檔案的路徑名，被看作是符號鏈。當B訪問這個LINK類檔案時，OS根據檔案的路徑去讀檔案，實現使用者B對檔案F的共享。利用符號鏈實現檔案共享時，只有檔案主才擁有指向其索引結點的指標；其他使用者只有該檔案的路徑名。當檔案的擁有者刪除檔案後，LINK型檔案不再起作用。利用符號鏈實現檔案共享的優缺點。優點：連結本地和遠地的檔案。缺點：1、共享使用者沒有索引結點，讀盤次數增加。2、LINK類檔案佔用一定磁碟空間

　　檔案保護。使用檔案有潛在的不安全因素——人為因素——系統因素——自然因素。確保檔案系統安全性的措施——增加存取控制機制——磁碟容錯技術——後備系統。第一級容錯技術SFT-I：主要防止因磁碟表面缺陷所造成的資料丟失。1）雙份目錄和檔案分配表2) 熱修復重定向和寫後讀校驗。第二級容錯技術SFT-II，1 ) 磁碟映象2) 磁碟雙工。事務記錄（Transaction Record）為了實現事務的原子性修改，一般藉助事務記錄這種資料結構來實現。這些資料結構放在穩定儲存器上，用來記錄事務執行時資料項修改的全部資訊。又稱為執行記錄(Log)。記錄欄位為：事務名。用於標識該事務的惟一名字；。資料項名。它是被修改資料項的惟一名字；舊值修改前資料項的值；新值修改後資料項將具有的值。

　　程序的基本概念為了提高計算機系統中各種資源的利用率，現代作業系統廣泛採用多道程式技術（multi-programming），使多個程式同時在系統中存在並執行。描述程序的資料結構——程序控制塊（PCB）一個程序應該包括：程式的程式碼；程式的資料；PC中的值，用來指示下一條將執行的指令；一組通用的暫存器的當前值，堆、棧；一組系統資源（如開啟的檔案）程式是文字，是語句的描述（靜態）程序是執行中的程式，含有上下文資訊（動態）結構特徵：程式段、相關的資料段、PCB構成了程序實體動態性：程序是程序實體的一次執行，程序的狀態總是在變化，PCB的內容總是在變化併發性：多個程序實體，同存於記憶體中，能在一段時間內同時執行（宏觀上）獨立性：獨立執行和資源排程的基本單位。每個程序都有“自己”的PC和內部狀態，執行時獨立於其他的程序（邏輯PC和物理PC）非同步性：以各自獨立的、不可預知的速度向前推進

　　程序的控制Running執行 Blocked阻塞 Ready就緒程序的三種基本狀態1) 就緒(Ready)狀態：程序一旦獲得CPU就可以投入執行的狀態2) 執行狀態：程序獲得CPU正在執行的狀態3) 阻塞狀態：程序由於等待資源或某個事件的發生而暫停執行的狀態執行à阻塞等待I/O的結果等待某一程序提供輸入執行à就緒執行程序用完了時間片執行程序被中斷，因為一高優先順序程序處於就緒狀態就緒 à 執行排程程式選擇一個新的程序執行阻塞 à就緒當所等待的事件發生時

　　程序同步兩個程序使用相同的一個共享一個資源（如共享檔案，印表機等）引出程序同步問題。程序在執行過程中所做的工作分為兩類：內部計算（不會導致競爭條件）對共享記憶體或共享檔案的訪問（可能導致競爭條件）我們把完成第二類工作的程式稱為“臨界區”，把需要互斥訪問的共享資源稱為“臨界資源”。如果我們能設計出某種方法，使得任何兩個程序都不會同時出現在臨界區中，就可以避免競爭條件的出現。由Dijkstra把整型訊號量定義為一個整型量，除初始化外，僅能透過兩個標準的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait(S): while S≤0 do no-op S:=S-1;signal(S): S:=S+1;

　　經典的程序同步互斥問題4.1有3個客戶在某天的日常生活中使用了某個 ATM 自動取款機。假設他們對 ATM 的使用順序是 a 到來，a 進入， b 到來， c 到來， a 離開，b 進入， b 離開， c 進入， c 離開。4.2某閱覽室，最多可容納100名讀者同時閱覽，當閱覽室中少於100名讀者時，閱覽室外等候的讀者可以立即進入，否則需要在外面等待。每個讀者可看成一個程序。semaphore seats；seats.value=100;while(閱覽時間){wait(seats);進入閱覽室；閱讀；離開閱覽室；signal(seats);}4.3司機與售票員while(上班時間){發動汽車；正常執行；到站停車；}while(上班時間){關閉車門；售票；開啟車門；}4.4兩個併發程序的讀寫設有一個緩衝區buffer，大小為一個位元組（如圖）。Compute程序不斷產生字元，送buffer，Print程序從buffer中取出字元列印。如不加控制，會出現多種列印結果，這取決於這兩個程序執行的相對速度。在這眾多的列印結果中，只有Compute和Print程序的執行剛好匹配的一種是正確的，其它均為錯誤。semaphore S_Empty； // 緩衝區是否為空，初值為1semaphore S_Full; // 是否有資料寫入，初值為0while(計算未完成){ P(S_Empty);Write_Data( )；V(S_Full);}Computewhile(列印未完成){P(S_Full)； Print_Data( )； V(S_Empty);}Print4.5有一個倉庫，可以存放A和B 兩種產品。要求：1)每次只能存入一種產品(A或B)；2)-N

　　程序通訊低階通訊：只能傳遞狀態和整數值（控制資訊），包括用來實現程序同步和互斥的訊號量和管程機制。優點是速度快。缺點是：傳送資訊量小：每次通訊傳遞的資訊量固定，若需要傳遞較多資訊，就得進行多次通訊。程式設計複雜：使用者需要直接去實現通訊的細節，程式設計複雜，容易出錯。高階通訊：能夠傳送任意數量的資料，包括三類：共享記憶體、管道、訊息。

　　執行緒定義及實現程序當中的一條執行流程叫執行緒。程序是資源分配單位，執行緒是CPU排程單位；程序擁有一個完整的資源平臺，而執行緒只獨享必不可少的資源，如暫存器和棧；執行緒同樣具有就緒、阻塞和執行三種基本狀態，同樣具有狀態之間的轉換關係；執行緒 ＝ 輕量級程序（lightweight process）使用者執行緒：在使用者空間實現，時間片分配給程序；核心執行緒：在核心中實現，時間片分配給執行緒；