操作系統(tǒng)期末復習資料

1、操作系統(tǒng)期末復習資料一 操作系統(tǒng)引論一 操作系 導 1 操作系統(tǒng)目標: 有效性、方便性、可擴充性、開放性 2 操作系統(tǒng)作用： 為用戶和計算機之間提供接口、管理計算機系統(tǒng)資源、實現(xiàn)對計算機資源的抽象 3 操作系統(tǒng)發(fā)展： 人工操作方式、脫機輸入輸出方式、單道批處理系統(tǒng)、多道批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)。 單道批處理系統(tǒng)：自動性：順序性：單道性： 多道批處理系統(tǒng)：資源利用率高、系統(tǒng)吞吐量大、平均周轉時間長，無交互能力。 4 操作系統(tǒng)五大功能： 處理機管理、內存管理、I/O 設備管理、文件管理、作業(yè)管理 5 分時系統(tǒng)： 為了彌補多道批處理系統(tǒng)交互性問題，引入分時系統(tǒng)，可以將一臺計算機提供給多個用戶同

2、時使用，提高計算機利用率。 分時系統(tǒng)的特點：多路性： 獨立性：交互性：及時性: 6 實時系統(tǒng)： 系統(tǒng)能及時響應外部事件的請求，在規(guī)定時間內完成對該事件的處理，并控制所有實時任務協(xié)調一致的運行。 多路性：獨立性：實時信息處理系統(tǒng)中，每個終端用戶提出請求時，互不干擾。實時控制系統(tǒng)中，對信息采集和控制也是彼此互不干擾。 及時性：實時控制系統(tǒng)的及時性要求比實時信息處理系統(tǒng)，分時系統(tǒng)更加嚴格。 交互性：實時信息處理系統(tǒng)的交互性僅限于訪問系統(tǒng)中的專用服務程序。 可靠性：實時系統(tǒng)的可靠性更高 7 操作系統(tǒng)發(fā)展： 單用戶單任務、單用戶多任務、多用戶多任務 8 操作系統(tǒng)的基本特征： 1. 并發(fā)性： 并發(fā)性指的是

3、多個事件在同一時間間隔內發(fā)生。并行性是多個事件在同一時刻發(fā)生。 進程：指系統(tǒng)中能獨立運行并作為資源分配的基本單位，由機器指令，數(shù)據(jù)和堆棧組成。線程：一個進程包含若干線程，可利用進程的資源。進程是分配資源的基本單位，線程是獨立運行和獨立調度的基本單位。 2 共享性： 即資源共享，有互斥共享方式、同時訪問方式。 3 虛擬技術：分為時分復用技術、空分復用技術。 如果虛擬的實現(xiàn)是通過時分復用方式，即對物理設備進行分時使用，設 N 是謀設備所對應的邏輯設備數(shù)，則每臺虛擬設備的平均速度必然小于等于 1/N。類似，空分復用實現(xiàn)虛擬，空間利用也小于等于 1/N 。 4 異步性： 進程的推進速度不可預知。 9

4、操作系統(tǒng)五大功能 1 處理機管理 2 存儲器管理： 3 設備管理： 4 文件管理： 5 操作系統(tǒng)與用戶間的接口： 10 操作系統(tǒng)結構設計 1 傳統(tǒng)的操作系統(tǒng)結構：無結構操作系統(tǒng)：模塊化結構：將大的功能分為若干子功能，每個子功能為一個模塊，再進一步細分，使之每一個模塊只實現(xiàn)一個子功能。需要考慮模塊的獨立性，即模塊的內聚性，耦合性。分層式結構：將一個操作系統(tǒng)分為若干層，每層由若干模塊組成。各層之間只存在單向依賴關系，即高層僅依賴緊鄰它的低層。保證系統(tǒng)的正確性，易于擴展，但效率低。 2 C/S 模式 由客戶機、服務器、網(wǎng)絡系統(tǒng)構成。完成一次交互可分為，客戶發(fā)送請求信息，服務器接受信息，服務器反饋消息

5、，客戶機接受消息。此種模式實現(xiàn)了數(shù)據(jù)的分布存儲，便于集中管理，可擴展性。但可靠性差。 3 面向對象程序設計:4 微內核操作系統(tǒng)結構：將操作系統(tǒng)分為：微內核和多個服務器。有如下功能，進程線程管理、低級存儲器管理、中斷和陷入處理。 二進程管理 1 程序順序執(zhí)行的特征：順序性：每一操作必須在上一個操作完成后開始封閉性：程序運行獨占全部資源，不受外界影響可再現(xiàn)性：只要程序執(zhí)行環(huán)境和初始條件相同，當程序重復執(zhí)行時，結果相同 2 程序并發(fā)執(zhí)行的特點： 間斷性：并發(fā)執(zhí)行的程序由于共享資源，以及為了完成同一任務相互合作，相互制約。將導致并發(fā)程序具有“執(zhí)行-暫停-執(zhí)行”間斷性活動規(guī)律。 失去封閉性：多個程序共享

6、資源。 不可再現(xiàn)性：由于失去封閉性，也就失去了再現(xiàn)性。即使執(zhí)行環(huán)境和初始條件相同，結果卻各不相同。 3 進程的特征：結構特征：進程由程序段，相關數(shù)據(jù)段和 PCB 三部分組成動態(tài)性：進程的實質是進程實體的一次執(zhí)行過程。而程序只是一組有序指令集合。 并發(fā)性：多個進程同時存在于內存中，在同一時間段內同時運行。而程序不行。 獨立性：進程實體可以獨立運行，獨立分配資源和獨立接受調度（線程）。而未建立 PCB 的程序不能作為一個單獨的單位參與運行。 異步性：指進程按各自獨立的，不可預知的速度向前推進。 4 進程的三個基本狀態(tài)： 就緒狀態(tài)：進程已分配到除了 CPU 之外的所有必要資源，只要再獲得 CPU，便

7、可立即執(zhí)行。 執(zhí)行狀態(tài)：進程已獲得 CPU，程序正在運行阻塞狀態(tài)：進程的暫停狀態(tài)稱為阻塞狀態(tài)。 進程的掛起狀態(tài)：當發(fā)生終端用戶請求、父進程請求、負荷調節(jié)的需求、操作系統(tǒng)需求時，可以發(fā)生掛起。 進程狀態(tài)轉換： 許可 I/0完成 進程調度 時間片完 I/O請求 釋放 創(chuàng)建 就緒 執(zhí)行 終止 阻塞 進程創(chuàng)建：首先創(chuàng)建一個 PCB，將該進程轉入就緒狀態(tài)并插入就緒隊列 進程終止：首先等待操作系統(tǒng)進行善后處理，然后清空 PCB，并將 PCB 空間返還系統(tǒng)。 5 進程控制塊 PCB PCB 記錄操作系統(tǒng)所需的，用于描述進程當前情況以及控制進程運行的全部信息。使得一個在多道程序環(huán)境下不能獨立運行的程序成為一個

8、可獨立運行的基本單位。PCB 是進程存在的唯一標識。 進程控制塊信息： 1 進程標識符：用于唯一標識一個進程內部標識符：為了方便系統(tǒng)使用。 外部標識符：由創(chuàng)建者提供，由用戶進程訪問該進程時使用。 2 處理機狀態(tài)：由處理機各種寄存器內容組成。 3 進程調度信息： 進程狀態(tài)、進程優(yōu)先級、進程調度所需其他信息、事件（阻塞原因）。 4 進程控制信息： 進程控制塊的組織方式： 1 鏈式方式：把同一狀態(tài)的 PCB，用鏈接字鏈接成一個隊列，形成就緒隊列。 2 索引方式：根據(jù)進程狀態(tài)建立索引表，在每個索引表中，記錄有相應狀態(tài)的某個 PCB 在PCB 表中的地址。 5 進程控制 原語：由若干指令組成，用于完成一

9、定功能的一個過程，是原子操作。在管態(tài)（核心態(tài)）下執(zhí)行，常駐內存。 進程創(chuàng)建：可以由進程樹來描述，子進程可以繼承父進程的所擁有的資源，當子進程被撤銷時，應將其從父進程中獲取的資源歸還父進程。當父進程被撤銷時，同時撤銷子繼承。 引起進程創(chuàng)建的事件：在多道程序環(huán)境中，只有進程才能在系統(tǒng)中運行，為了能讓程序運行，需要建立進程。引起進程創(chuàng)建的事件有，用戶登錄、作業(yè)調度、提供服務、應用請求。 進程創(chuàng)建步驟： 申請空白 PCB、為新進程分配資源、初始化進程控制塊、將新進程插入就緒隊列 進程終止：引起進程終止的事件：正常結束、異常結束、外界干預（父進程請求，父進程終止，操作系統(tǒng)干預等）進程終止過程： 1根據(jù)被

10、終止進程的標識符，從 PCB 集合中檢索出該進程的 PCB，從中讀出該進程狀態(tài)。 2. 若該進程正處于執(zhí)行狀態(tài)，則立即終止其執(zhí)行，并置調度狀態(tài)為真，表示該進程被終止后應重新進行調度。 3若該進程還有子進程，則將其子進程終止。 4將被終止進程的全部資源，或歸還父進程，或歸還操作系統(tǒng) 5. 將被終止進程的 PCB 從所在隊列中移出。 進程的阻塞狀態(tài)：當正在執(zhí)行的進程，發(fā)現(xiàn)阻塞事件時，由于無法繼續(xù)執(zhí)行，于是進程調用 block 原語把自己阻塞。進程的阻塞是進程自身的一種主動行為。 進程的喚醒過程：首先將被阻塞的進程從等待隊列中移出，將其 PCB 中的現(xiàn)行狀態(tài)改為就緒，然后將該 PCB 插入就緒隊列。

11、 進程掛起與激活：進程掛起：首先檢查被掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)，改為靜止阻塞。 進程激活：將進程從外存調入內存，檢查其現(xiàn)行狀態(tài)，若是靜止就緒，便改為活動就緒；若是靜止阻塞，改為活動阻塞。 6 進程同步 1 由于資源共享和進程合作，進程間存在兩種形式的制約關系：間接相互制約關系：源于資源共享直接相互制約關系：源于進程合作 2 臨界資源：進程間應采用互斥方式，實現(xiàn)對這種資源的共享臨界資源實例- 單獨運行生產(chǎn)者或消費者函數(shù)，都不會出現(xiàn)錯誤，但當兩者并行執(zhí)行時，會因為同時訪問了同一個數(shù)據(jù)量而引起錯誤，因此，需要互斥的令生產(chǎn)者和消費者訪問變量。 3 臨界區(qū)

12、： 進程中訪問臨界資源的那段代碼稱為臨界區(qū)，臨界區(qū)前面需要增加一段用于沖突檢驗的代碼，叫做進入?yún)^(qū)。相應的，在臨界區(qū)后面加上一段退出區(qū)代碼，用于將臨界區(qū)正被訪問的標志恢復為未被訪問的標志。余下區(qū)域為剩余區(qū)。 同步機制應當遵循的原則： 空閑讓進、忙則等待、有限等待、讓權等待 4 信號量機制 整型信號量：定義一個用于表示資源數(shù)目的整型量 S，除初始化外，僅能通過兩個標準的原子操作 wait(), signal() 來訪問，即 P，V 操作記錄型信號量：當信號量 S<=0 時，就會不斷檢測，未遵循讓權等待。因此，除了需要一個用于代表資源數(shù)目的整型變量 value 外，還需增加一個進程鏈表指針 L

13、，用于鏈接上述因 s<=0 而等待的進程。 /記錄型結構體 typedef struct semaphore int value;/記錄資源個數(shù) struct semaphore *L;/鏈接等待進程 semaphore; void wait(semaphore &s) /value表示系統(tǒng)中某類資源數(shù)目，每次wait操作，系統(tǒng)中可供分配的資源數(shù)減一 s.value = s.value-1; /value值可以一直減下去，為負數(shù)也可以，當為負數(shù)的時候，說明有進程自我阻塞了 if(s.value<0) block(s.L);/當沒有資源可用時，進程調用block將自己阻塞。

14、/此時，value的絕對值表示該信號量鏈中已阻塞的進程數(shù) void signal(semaphore &s) s.value = s.value+1; if(s.value<=0)/若加一后，value值還是小于等于.則說明鏈表中還有阻塞的進程，需調用喚醒 wakeup(s.L); 注：若value初值為1，表示只允許一個進程訪問臨界資源，此時的信號量化為互斥信號量 AND 信號量： 有時，一個進程需要先獲取多個共享資源后方能執(zhí)行。則這些共享資源都作為臨界資源。AND 同步機制是：將進程在整個執(zhí)行過程中所需所有資源，一次性全部分配給進程，待進程使用完后再一起釋放。則在信號量中又添

15、加一個AND條件。 typedef struct source int arrMAX;/source資源結構體，數(shù)組中存放每種資源的對應可用數(shù)目 int length;/總的資源種類數(shù) source; void signal(source &s) for(int i=0;i<s.length;i+) s.arri+;/一次性全部釋放 void wait(source &s) int flag = 0; for(int i=0;i<s.length;i+) if(s.arri>=1)/判斷所需的全部種類資源是否都能夠分配給進程 flag = 1; else fl

16、ag = 0; break; if(flag=1)/如果能，則一次性全部分配給相應的進程 for(int i=0;i<s.length;i+) s.arri-; else 信號量的應用： 1 利用信號量實現(xiàn)進程互斥為了使多個進程能互斥地訪問謀臨界資源，只需為該資源設置一互斥信號量mutex（資源個數(shù)）,并設初值為1，然后將各個進程訪問該資源的臨界區(qū)至于wait（mutex）和signal(mutex) 操作之間。在使用信號量實現(xiàn)互斥時，wait操作和signal操作需要成對出現(xiàn)。 2 利用信號量實現(xiàn)前驅關系 5 管程機制 管程：代表共享資源的數(shù)據(jù)結構，以及由對該共享數(shù)據(jù)結構實施操作的一組

17、過程所組成的資源管理程序，共同構成操作系統(tǒng)的資源管理模塊。 管程組成：管程名稱，管程內部的共享數(shù)據(jù)結構，對該數(shù)據(jù)結構進行操作的一組過程，對管程內共享數(shù)據(jù)設置初始值的語句。 public class Monitor private int local_value; private string monitor_name; private void init_value(); private void use_value(); public void public_use_value(); ; 局部與管程內的數(shù)據(jù)，僅能被管程內部的過程訪問，任何管程外的過程都不能訪問它。反之，局部于管程內部的過程也

18、僅僅能訪問管程內的數(shù)據(jù)。管程每次僅允許一個進程進入管程，實現(xiàn)了進程互斥。 管程和進程的區(qū)別： 1 進程定義的數(shù)據(jù)結構是私有數(shù)據(jù)結構PCB，而管程定義的是公有，如消息隊列。 2 進程是由順序程序執(zhí)行有關操作，管程主要進行同步操作。 3 設置進程的目的在于實現(xiàn)系統(tǒng)并發(fā)性，而管程則是解決共享資源的互斥使用問題。 4 進程是主動工作方式，管程是被動工作方式，進程通過調用管程中的過程對共享數(shù)據(jù)結構進行操作。 5 進程可并發(fā)執(zhí)行，管程不行。 6 進程具有動態(tài)性，管程是一個資源管理模塊，供進程調用。 6. 經(jīng)典的進程同步問題采用記錄型信號量解決生產(chǎn)者-消費者問題： void init(semaphore &

19、amp;s) s.empty = MAX; s.full = 0; s.mutex = 1; /這些操作都可以循環(huán)執(zhí)行，如下的只是他們的一次活動 void producer(queue &q,semaphore &s) wait(s.empty);/先執(zhí)行對資源信號量的操作 wait(s.mutex);/再執(zhí)行對互斥信號量的操作 enqueue(q,data); signal(s.mutex); signal(s.full); void customer(queue &q,semaphore &s) wait(s.full); wait(s.mutex); ou

20、tqueue(q); signal(s.mutex); signal(s.empty); 在生產(chǎn)者-消費者問題中，每個程序實現(xiàn)互斥的P,V操作必須成對出現(xiàn)。其次，對于資源信號量的P,V操作也要成對出現(xiàn)。每個程序的多個P操作順序不能顛倒。 采用AND信號量解決生產(chǎn)者-消費者問題： 原理一樣，只需將wait，signal操作換成swait(),signal()。例如，wait(s.full); wait(s.mutex); 用Swait(full,mutex);替換 哲學家進餐問題： /采用循環(huán)隊列方式，假設有N=5個哲學家， /所有信號量初始化為，第i為哲學家一次的活動方式如下，可以循環(huán)執(zhí)行如下

21、活動 void profess(semaphore &s) /采用記錄型方式 wait(s.chopsticki);/拿左邊的筷子 wait(s.chopstick(i+1)mod(s.n);/拿右邊的筷子 eat; signal(s.chopsticki); signal(s.chopstick(i+1)mod(s.n); think; void profess(semaphore &s)/采用AND信號量方式 think; Swait(s.chopsticki,s.chopstick(i+1)mod(s.n); eat; Ssignal(s.chopsticki,s.cho

22、pstick(i+1)mod(s.n); 讀者-作者問題：為實現(xiàn)讀者和作者進程在讀寫時的互斥而設置了一個互斥信號量Wmutex,另外，再設置一個整形變量Readercount表示正在讀的進程數(shù)目。只要有讀者在，就不能寫。又因為readcount 是一個可被多個讀者進程訪問的臨界資源，也應為它設置一個互斥信號量。 7 進程通信進程通信類型： 1 共享存儲器系統(tǒng)：相互通信的進程共享某些數(shù)據(jù)結構或共享存儲區(qū)，進程間通過這些空間進行通信。 2 消息傳遞系統(tǒng): 目前最流行。進程間的數(shù)據(jù)交換以格式化的信息為單位。 3 管道通信：管道，即用于連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的一個共享文件。 消息

23、傳遞通信的實現(xiàn)方法：直接通信方式：利用操作系統(tǒng)所提供的發(fā)送命令，直接把消息發(fā)送給目標進程。間接通信方式：利用共享數(shù)據(jù)結構的實體，暫存發(fā)送進程發(fā)送的消息，接受進程從該實體中取出消息。這個中間實體成為信箱。 信箱的分類：私用信箱：用戶進程可自行建立公用信箱：由操作系統(tǒng)創(chuàng)建共享信箱：由謀進程創(chuàng)建 信箱通信時，發(fā)送進程和接收進程間的關系： 一對一、一對多、多對一、多對多 8 線程 操作系統(tǒng)引入線程，是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷。一個進程擁有多個線程，線程是獨立調度的基本單位，線程一般不具有自己的資源，他們會利用進程的資源。在一個進程中的多個線程可以并發(fā)執(zhí)行。進程的系統(tǒng)開銷遠高于線程。 線程

24、的特點：輕型實體、獨立調度和分配的基本單位、可并發(fā)執(zhí)行、共享進程資源用戶線程和內核線程：用戶線程：在內核的支持上，在用戶層通過線程庫實現(xiàn)創(chuàng)建，調度和管理，且無需內核支持。 內核線程：在操作系統(tǒng)上，在其內核空間內執(zhí)行創(chuàng)建，調度和管理多線程模式：一對多：一個內核線程對應多個用戶線程。效率較高，但如果一個線程執(zhí)行阻塞，其他線程也就被阻塞。 一對一：一個內核線程對應一個用戶線程，并發(fā)性好，但開銷大。 多對多：多個內核線程對應更多用戶線程，上面兩者的折中。 三 處理機調度和死鎖 1. 高級調度： 高級調度又稱作業(yè)調度或長程調度，主要功能是依據(jù)某種算法，把外存上的處于后備隊列的作業(yè)調入內存。 作業(yè)：在批處

25、理系統(tǒng)中，是以作業(yè)為基本單位從外存調入內存的。 作業(yè)步：在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干相對獨立，又相互關聯(lián)的順序加工步驟才能得到，這些步驟叫做作業(yè)步（job step）。 一個典型的作業(yè)分三步： 編譯、連接裝配（將若干程序段裝配為可執(zhí)行程序）、運行（目標程序調入內存） 作業(yè)流：若干作業(yè)進入系統(tǒng)，被依此放在外存，形成輸入的作業(yè)流。 作業(yè)控制塊JCB： 是作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調度所需的全部信息。每當作業(yè)進入系統(tǒng)，系統(tǒng)為每個作業(yè)創(chuàng)建一個JCB。當作業(yè)完成，則系統(tǒng)回收分配給它的資源，撤銷JCB。 作業(yè)調度：根據(jù)JCB中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求

26、，按照一定算法，從外存后備隊列中選擇某些隊列調入內存，并為它們創(chuàng)建進程，分配資源。然后再將新進程插入就緒隊列。 每次作業(yè)調度需要考慮兩個問題：決定接納多少個作業(yè)，決定接納哪些作業(yè)，取決于調度算法。最簡單的FCFS算法，較常用的是短作業(yè)優(yōu)先算法，基于作業(yè)優(yōu)先級算法，較好的是響應比高者優(yōu)先算法。 2. 低級調度（進程調度）： 進程調度用于決定就緒隊列中的哪個進程應獲得處理機。 進程調度的功能：保存處理機現(xiàn)場信息、按某種調度算法選取進程、把處理器分配給進程進程調度的三個基本機制： 1 排隊器：為提高進程調度效率，應事先將系統(tǒng)中所有就緒進程按一定順序排列成隊列 2 分派器：把進程調度算法所選的進程，從

27、就緒隊列中取出，然后進行上下文切換，將處理器分配給它。 3 上下文切換機制：當對處理機切換時，會發(fā)生兩對上下文切換。在第一對切換時，系統(tǒng)保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運行。在第二對上下文切換時，將移出分派程序，而把新選進程的CPU現(xiàn)場信息裝入到處理機的相應寄存器。 進程調度方式非搶占式：一旦把處理機分配給某個進程后，會一直讓它運行下去，直至此進程完成，或發(fā)生某些事件被阻塞時，才把處理機分配給其它進程。但難以滿足緊急任務的需求。 搶占式：允許調度程序根據(jù)某種原則暫停某個正在執(zhí)行的進程，將已分配的處理機重新分配給另一個進程。但開銷比非搶占式大。 搶占式基于的原則： 1

28、優(yōu)先權原則：通常一些重要和緊急的作業(yè)賦予較高的優(yōu)先權。 2 短作業(yè)（進程）優(yōu)先原則：當新到達的作業(yè)（進程）比正在執(zhí)行的作業(yè)（進程）明顯短時，將暫停當前長作業(yè)（進程）的執(zhí)行，使短作業(yè)優(yōu)先執(zhí)行。 3 時間片原則：各個進程按時間片輪流運行。適用于分時系統(tǒng)，大多數(shù)實時系統(tǒng)，以及要求較高的批處理系統(tǒng)。 3中級調度（中程調度）： 中級調度是為了提高內存利用率和系統(tǒng)吞吐量，為此，應使那些暫時不能運行的進程讓出內存資源，將它們調至外存上去等待。 這三種調度方式中，進程調度頻率最高，作業(yè)調度所需時間最長，中級調度基于這兩者之間。 4 選擇調度方式和調度算法的若干準則：面向用戶的準則： 1 周轉時間短： 周轉時間

29、：作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成的這段時間間隔。包括四部分，作業(yè)在外存后備隊列上等待調度時間，進程進入就緒隊列上等待調度時間，進程執(zhí)行時間，以及進程等待I/O操作完成的時間。 可以把平均周轉時間描述為： T = 作業(yè)的周轉時間T與系統(tǒng)為它提供的服務時間Ts之比，即W = T/Ts,稱為帶權周轉時間，則平均帶權周轉時間為： T = 2 相應時間快： 包括三部分時間：輸入請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的相應信息送回到終端的時間。 3 截止時間的保證： 截止時間，即謀任務必須開始執(zhí)行的最晚時間，或必須完成的最晚時間 4 優(yōu)先權準則： 在批處理，分時和實時系

30、統(tǒng)中都可以遵循優(yōu)先權準則。 面向系統(tǒng)的準則： 1 系統(tǒng)吞吐量高： 用于評價批處理系統(tǒng)系能的另一個重要指標 2 處理機利用率好： 3 各類資源平衡利用： 5調度算法 先來先服務FCFS調度算法：每次調度都是從后備作業(yè)隊列中選作若干最先進入該隊列的作業(yè)，將其調入內存，為其分配資源，創(chuàng)建進程，放入就緒隊列。 FCFS算法有利于長作業(yè)（進程），而不利于短作業(yè)（進程）。有利于cpu繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)。 短作業(yè)（進程）優(yōu)先SJ(P)F調度算法：是對短作業(yè)或短進程優(yōu)先調度算法。短作業(yè)優(yōu)先SJF調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將其調入內存。短進程優(yōu)先SPF調

31、度算法是從就緒隊列中選擇一個估計時間最短的進程，將處理機分配給它。 該算法對長作業(yè)不利。未能完全考慮作業(yè)的緊迫程度。 非搶占式優(yōu)先權調度算法：系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程一直執(zhí)行下去，直至完成，或因某些事件而放棄使用權。主要用于批處理系統(tǒng)中。 搶占式優(yōu)先權調度算法：系統(tǒng)同樣把處理機分配給優(yōu)先權最高的進程，但當有更高優(yōu)先權的進程進入隊列時，進程調度就會停止當前進程，轉而將處理機分配給這個優(yōu)先權更高的進程。 優(yōu)先權類型：靜態(tài)優(yōu)先權：是在創(chuàng)建進程時確定的，且在進程的整個運行期間保存不變。 確定進程優(yōu)先權的依據(jù)有：進程類型、進程對資源的需求、用戶要求 動態(tài)優(yōu)先權：在創(chuàng)建進

32、程時所賦予的優(yōu)先權，是可以隨進程的推進或其等待時間的增加而改變的。 高響應比優(yōu)先調度算法： 優(yōu)先權=（等待時間+要求服務時間）/要求服務時間 = （響應時間）/要求服務時間這樣，優(yōu)先權可以隨動態(tài)優(yōu)先權的變動而變化，更加靈活。時間片輪轉法RR調度： 時間片輪轉法：把CPU分配給隊首進程，并令其執(zhí)行一個時間片，當執(zhí)行的時間片用完，由一個計時器發(fā)送時鐘中斷請求，調度程序便依據(jù)此信號終止此進程的執(zhí)行，并將其送至就緒隊列的隊尾，然后再把處理機分配給新的隊列頭進程，如此往復。適合分時系統(tǒng)。 多級反饋隊列調度算法：設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級，第一個隊列的優(yōu)先級最高，其余各隊列優(yōu)先級逐級遞

33、減。該算法賦予各個隊列中進程執(zhí)行時間的大小各不相同，優(yōu)先級隊列越高的，進程獲得的時間片越小。 當一個新進程進入進程后，首先將其放入第一個隊列的隊尾，按FCFS算法排隊等待調度，當輪到其執(zhí)行時，如果其能在該隊列時間片內完成，則讓其執(zhí)行完畢。若其未能完成，則調度程序將其轉到下一個隊列的隊尾，同樣按FCFS方式等待調度。如此繼續(xù)下去。當一個長進程或長作業(yè)從第一個隊列依此降至第n個隊列后，在第n個隊列中便采用按時間片輪轉方式運行。 僅當?shù)?-（i-1）隊列均空時，才會調度第i個隊列的進程運行。若處理機正在第i個隊列中為某個進程服務時，又有新進程進入優(yōu)先權較高的隊列，則此時新進程將搶占正在運行的進程的處

34、理機，即把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先級進程。 6產(chǎn)生死鎖的原因和必要條件死鎖，是指多個進程在運行過程中因爭奪資源而造成的一種僵局，使得進程無法向前推進。 產(chǎn)生死鎖的原因： 競爭資源、進程間推進順序不當 1 競爭資源 系統(tǒng)中的資源分為可剝奪性資源和非可剝奪性資源。前者指進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)剝奪。后者指當系統(tǒng)分配了這類資源后，不能夠再行剝奪。 競爭非剝奪資源：例如，系統(tǒng)中只有一個打印機和一個磁帶機，供兩個進程共享。若A進程已占用了打印機，B進程已占用了磁帶機。若此時，B繼續(xù)要求打印機，則由于產(chǎn)生I/O請求，B將阻塞；若A有要求磁帶機

35、，則A也阻塞。因而兩者都等待對方的資源，但它們又因為阻塞而不能繼續(xù)推進，從而導致不能釋放自己的資源。產(chǎn)生死鎖。 競爭臨時性資源：指由一個進程產(chǎn)生，被另一個進程使用一短暫時間后便無用的資源。 例如下述進程請求方式可能產(chǎn)生死鎖 P1 : REQUEST(S3); RELEASE(S1); P2 : REQUEST(S1); RELEASE(S2); P3 : REQUEST(S2); RELEASE(S3); 2 進程推進順序不當：進程推進順序不當會導致死鎖。 7產(chǎn)生死鎖的必要條件互斥條件：一段時間內某個資源只由一個進程占用。 請求和保持條件：指進程已經(jīng)保持了至少一個資源，但又提出新的資源請求，而

36、該資源又被其他進程所占用。 不剝奪條件：指進程已獲得的資源，在未使用完成前，不能被剝奪。環(huán)路等待條件：指發(fā)生死鎖時，必然存在一個進程-資源的環(huán)形鏈。 8處理死鎖的基本方法 預防死鎖：破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件避免死鎖：在資源動態(tài)分配過程中，用某種方式阻止系統(tǒng)進入不安全狀態(tài)檢測死鎖：不事先預防，也不檢測系統(tǒng)是否進入不安全區(qū)，而是通過檢測機制，及時檢測出死鎖的發(fā)生，然后采取適當措施消除死鎖。 解除死鎖：與檢測死鎖配套使用。常用方式是撤銷或掛起一些進程，以便回收一些資源。 系統(tǒng)的安全狀態(tài)：指系統(tǒng)能按某種進程順序，來為每個進程分配其所需的資源，直至滿足每個進程對資源的最大需求。如果系

37、統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)進入不安全狀態(tài)。 銀行家算法： 銀行家算法可以避免死鎖，其數(shù)據(jù)結構為： #define MAX 10 /* 可利用資源向量，每個元素代表一類可利用的資源數(shù)目， 初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目。如果avaliablej=k,則表示系統(tǒng)中現(xiàn)有Rj類資源K個。 最大需求矩陣MAX，定義了系統(tǒng)中n個進程中的每個進程對m類資源的最大需求。 若MAXij = k,表示進程i需要Rj類資源的最大數(shù)目為k 分配矩陣allocationij = k,表示進程i當前獲得的資源Rj有k個 需求矩陣needij = k,表示進程i當前還需要Rj類資源k個 Needij

38、 = Maxij-Allocationij; */ typedef struct bank int avaliableMAX;/可利用資源向量 int MaxMAXMAX;/最大需求矩陣 int AllocationMAXMAX;/分配矩陣 int needMAXMAX;/需求矩陣 bank; 設request_i是進程Pi的請求向量，如果request_ij = k,表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)進行如下檢測： 1） 若request_ij<=needij,轉向2，否則認為出錯。 2） 若request_ij<=avaliablej,則轉向3，否則

39、認為出錯 3） 系統(tǒng)分配資源給進程，并修改數(shù)據(jù)結構中數(shù)據(jù) Avaliablej=avaliablej-request_ij; Allocationij=allocationij+request_ij; Needij=needij-request_ij; 4) 系統(tǒng)進行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。 void allocate(bank &ba,int requestMAX,int i,int j) if(requestij<=ba.needij) if(requestij<=ba.avaliableij) /資源分配 ba.avaliableij =

40、ba.avaliableij-requestij; ba.Allocationij = ba.Allocationij+requestij; ba.needij = ba.needij-requestij; 安全性算法：工作向量work，表示系統(tǒng)可以提供給進程繼續(xù)運行所需的各類資源數(shù)目，初始，work = available。 結束向量Finish，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。初始，finishi=false;當有足夠資源分配給進程時，finishi=true; 算法如下： void check(bank &ba,int work,bool finish,int

41、i,int j) if(finishi=false&&ba.needij<=workj) /進程Pi尚未結束，其所需資源系統(tǒng)可以滿足 /說明可以獲得資源，順利執(zhí)行。之后釋放分配給它的資源。 workj = workj+ba.Allocationij; finishi=true; else if(finishi=true) /此進程終止 死鎖檢測： 1 資源分配圖： 死鎖檢測可以利用資源分配圖來描述。該圖由一組節(jié)點N和一組邊E所組成的一個對偶 G = (N,E)。把N分為兩個互斥的子集，即一組進程節(jié)點P和一組資源節(jié)點R，N=P并R。 凡是屬于E的邊，都連接著P和一個R中的節(jié)

42、點，e = pi,Rj表示資源請求邊，由進程指向資源，表示進程申請資源。E = Rj,Pi表示資源分配圖，把資源分配給進程。如圖例： R1 R2 P1 P2 注：分配邊應始于一個資源點 2 死鎖定理 將資源圖簡化，來檢測當系統(tǒng)處于S狀態(tài)時是否為死鎖狀態(tài)。 方法為：在資源分配圖中，找一個既不阻塞又非獨立的進程節(jié)點Pi,在順利的情況下，Pi 可以獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占的所有資源，相當于消去Pi 所請求的請求邊和分配邊，使之成為孤立的節(jié)點。 如上圖，將P1兩個分配邊和一個請求邊消去，留下一個孤立的P1節(jié)點。這樣，圖中所有的資源由P2使用，當P2獲得資源并執(zhí)行完畢后，將P2

43、的邊也刪去。利用這用簡化方式，如果說，能夠消去圖中所有的邊，使所有節(jié)點都成為孤立節(jié)點，則該圖可以完全簡化。 對于較復雜的資源分配圖，可能有多個既非阻塞，又非孤立的進程節(jié)點，不同的簡化順序得到的簡化圖是相同的。 死鎖的解除：剝奪資源，撤銷進程 四 存儲器結構 1 程序的裝入和鏈接將一個用戶源程序變?yōu)橐粋€可在內存中執(zhí)行的程序，首先要編譯，由編譯程序將源程序編譯成目標模塊，之后鏈接，由鏈接程序將編譯后的目標模塊，以及所需庫函數(shù)鏈接起來，形成一個完整的裝入模塊。最后裝入，由裝入程序將裝入模塊裝入內存。 程序裝入：絕對裝入方式：在編譯時，如果知道程序將駐留在內存的什么位置，則，編譯程序將產(chǎn)生絕對地址的目

44、標代碼。 可重定位裝入方式：在多道程序環(huán)境下，所得到的目標模塊的起始地址通常從0開始，程序中的其他地址也都是相對于起始地址計算的。此時可以采用可重定位方式裝入，根據(jù)內存當前情況，裝入到適當位置。采用可重定位裝入程序將裝入模塊裝入內存后，會使得裝入模塊的所有邏輯地址與實際裝入內存的物理地址不同。 動態(tài)運行時裝入方式：可重定位裝入方式不允許程序運行時在內存中移動位置，而動態(tài)方式可以。動態(tài)運行時的裝入程序在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址裝換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行才開始。這就需要重定位寄存器的支持。 程序鏈接：靜態(tài)鏈接：在程序運行前，先將各自目標模塊及

45、其所需庫函數(shù)，鏈接成一個裝入模塊，以后不再拆開。屬于事先鏈接。 裝入時動態(tài)鏈接：將目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。 運行時動態(tài)鏈接：對某些目標模塊的鏈接，是在程序執(zhí)行中需要該模塊時，才對它進行鏈接。 靜態(tài)鏈接 例如：有A,B,C三個目標模塊，長度分別為L,M,N。其中A中有CALL B語句，B中有CALL C 語句。欲將A,B,C裝配成一個裝入模塊。需要修改兩個東西： 1） 對相對地址進行修改 2） 變換外部調用符號，將調用符號換成相對地址 模塊 A CALL B 模塊 B CALL C 模塊 C 模塊A JSR L 模塊B JSR L+M 模塊C 00 L-1 L-1 L

46、 0 M-1 L+M-1 L+M 0 N-1 L+M+N-1 裝入時動態(tài)鏈接：即在裝入一個目標模塊時，若發(fā)生一個外部模塊調用事件，將引起裝入程序去找出相應的外部目標模塊，并裝入內存。便于修改和更新，便于實現(xiàn)對目標模塊的共享。 內存的連續(xù)分配方式：單一連續(xù)分配：適用于單用戶，單任務的操作系統(tǒng)。 固定分區(qū)分配：將內存用戶空間劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。允許有幾道作業(yè)并發(fā)執(zhí)行。 動態(tài)分區(qū)分配：根據(jù)進程的實際需求，動態(tài)分配空間。 動態(tài)分區(qū)分配算法： 1） 首次適應 FF 算法： FF 算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內存時，從鏈首開始順序查找，直至找到一個大小能

47、滿足要求的空閑分區(qū)為止，然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內存空間分配給請求者，剩余空閑分區(qū)仍留在空閑鏈中。 2） 循環(huán)首次適應 NF 算法：在為進程分配內存空間時，不再是每次都從鏈首開始查找，而是從上一次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到滿足要求的空閑分區(qū)，從中劃分出一塊滿足要求大小的內存空間分配給作業(yè)。 3） 最佳適應 BF 算法： 每次為作業(yè)分配內存時，總是把能滿足要求，又是最小的空閑分區(qū)分配給作業(yè)。 4） 最壞適應 WF 算法： 要掃描整個空閑分區(qū)表或鏈表，總是挑選一個最大的空閑分區(qū)分割給作業(yè)，優(yōu)點在于可使剩下的空閑分區(qū)不至于太小，產(chǎn)生碎片的幾率很小。 5） 快速適

48、應 QF 算法： 將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表。這樣，系統(tǒng)中存在多個空閑分區(qū)鏈表，同時在內存中設立一張管理索引表，該表的每一個表項對應一種空閑分區(qū)類型，并記錄該類型空閑分區(qū)鏈表頭指針。 在動態(tài)分區(qū)存儲管理方式中，主要操作是分配內存和回收內存伙伴系統(tǒng)：固定分區(qū)和動態(tài)分區(qū)都有不足之處，固定分區(qū)內存空間利用率低。動態(tài)分區(qū)系統(tǒng)開銷大。伙伴系統(tǒng)是二者的折中，規(guī)定，無論分配分區(qū)還是空閑分區(qū)，分區(qū)大小均為 2 的 k 次冪，k 為整數(shù)，1<=k<=m ; 2 的一次冪為最小分區(qū)，2 的 m 次冪為最大分區(qū)?？芍囟ㄎ环謪^(qū)分配：在內

49、存分配時，若在系統(tǒng)中有若干小的分區(qū)，總容量足夠大，但單獨一個卻不能容下程序，這些分區(qū)也不相鄰，無法把程序裝入內存。引起了內存浪費，產(chǎn)生碎片。 通過移動內存中的作業(yè)的位置，把原來多個分散的小分區(qū)拼湊成一個大分區(qū)的方法，稱為緊湊法，提供內存利用率。但由于緊湊后的用戶程序在內存中的位置發(fā)生改變，因此，需要重定位。 請求分配分區(qū) 檢索空閑分區(qū)鏈 找到大于申請的可用區(qū) 空閑分區(qū)總和>=請求區(qū) 按動態(tài)分區(qū)方式進行分配 修改有關數(shù)據(jù)結構 進行緊湊形成連續(xù)空閑區(qū) 修改有關數(shù)據(jù)結構 無法分配 返回分區(qū)號 對換的引入：將內存中暫時不能運行的進程或暫時不用的程序和數(shù)據(jù)調出到外存，以便騰出足夠的內存空間，再把已

50、具備運行能力條件的進程或程序，數(shù)據(jù)調入內存。如果對換是以整個進程為單位的，稱之為整體對換，或進程對換。用于分時系統(tǒng)。若對換以頁或段為單位，則分別稱之為頁面對換，分段對換，用以支持虛擬存儲系統(tǒng)。 2 基本分頁存儲管理方式連續(xù)分配方式會形成許多碎片，從而離散分配方式，采用頁為分配的基本單位，可以避免產(chǎn)生碎片。若采用段為基本單位，則稱之為分段存儲管理方式。 頁面： 分頁存儲管理是將一個進程的邏輯地址空間分成若干大小相等的片，稱之為頁。并給各個頁加以編號，從 0 開始。相應的，內存也分成與頁面等大的若干存儲塊，稱為物理塊或頁框，同樣為它們加以編號。在為進程分配內存時，以塊為單位將進程的若干頁分別裝入到

51、多個可以不相鄰的物理塊中。由于進程的最后一頁通常裝不滿而形成不可利用的碎片，稱之為“頁內碎片”。頁面大小一般為 2 的冪。 頁面地址結構： 分頁地址由頁號，偏移量（頁內地址）組成。如下例： 頁號 位移量 若上圖 0 11 位為頁內地址，即每頁 4KB，12 31 為頁號，即地址空間最多允許 220 頁若給定一個邏輯地址空間中的地址為 A，頁面大小為 L，則頁號和頁內地址 D 為： D = A MOD L 頁表： 系統(tǒng)要為每一個進程都建立一個頁表。在進程地址空間內的所有頁，依此在頁表中有一頁表項，記錄了相應頁在內存中的對應的物理塊號。頁表是實現(xiàn)從頁號到物理塊號的地址映射。 地址變換機構：該機構是

52、實現(xiàn)從邏輯地址到物理地址的轉換，頁內地址和物理地址是一一對應的，地址變換機構的任務是將邏輯地址中的頁號，轉換為內存中的物理塊號。借助頁表實現(xiàn)。 基本的地址變換機構：如果頁號大于或等于頁表長度，表示本次所訪問的地址超過進程的地址空間。若未越界，則將頁表地址與頁號和頁表項長度的乘積相加（即，基地址+偏移量）得到該表項在頁表中的位置，從中得到物理塊號。 具有快表的地址變換機構：為了提高地址變換速度，在地址變換機構中增設一個具有并行查詢能力的特殊高速緩沖寄存器，稱為“快表”。在 CPU 給出有效地址后，由地址變換機構自動將頁號送入快表，并將此頁號與快表中的所有頁號做比較，若有匹配的，則表示要訪問的頁表

53、項子在快表中。這樣可以直接從快表中讀取對應的物理塊號。若，不在，則還須再訪問內存中的頁表，找到后，將物理塊號送至地址寄存器，同時將此表項加入快表的一個寄存器中，如果滿了，則替換。 兩級頁表： 以 32 位邏輯空間為例，當頁面大小為 4KB（12 位），若采用一級頁表結構，對應（32-12） 20 位的頁號。若采用二級頁表，則需要對頁表分頁，外層頁表中的頁內地址為 10 位，外層頁號也為 10 位。 在頁表中的每個表項中存放的是進程的某頁在內存中的物理塊號。而在外層頁表的每個頁表項中，所存放的是某頁表分頁的首地址。 頁表的首地址 物理塊號 在地址變換機構中同樣增設了一個外層頁表寄存器，用于存放外

54、層頁表起始地址，并利用邏輯地址中的外層頁號，作為外層頁表的索引，從中找到指定頁表的起始地址，再找到指定的頁表項，從中找到物理塊號。在采用兩級頁表結構的情況下，對于正在運行的進程，必須將其外層頁表調入內存，而對頁表則只需調入一頁或幾頁。 3 分段存儲方式：分段存儲的用途： 1） 方便編程：用戶把作業(yè)按照邏輯關系劃分為若干段，每段從 0 開始編址 2） 信息共享：分頁系統(tǒng)中的頁只存放信息的物理塊，無完整意義，而段是信息的邏輯單位 3） 信息保護 4） 動態(tài)增長：處理數(shù)據(jù)段的動態(tài)增長 5） 動態(tài)鏈接：只有當目標程序運行過程中，才將某段目標程序調入內存并鏈接分段的基本原理： 作業(yè)的地址空間被劃分為若干個段，每段定義了一組邏輯信息。每段從 0 開始編址，并采用一段連續(xù)的地址空間。段的長度由相應的邏輯信息組的長度決定，因