作業系統面試題準備

就只准備了程序執行緒之類的，再深了一時半會也搞不定了。

1.程序

現在作業系統的特點：保證安全前提下，程式併發執行，以及系統所擁有的資源被共享和使用者隨機使用系統。

程序是一個程式對某個資料集的執行過程，是分配資源的基本單位。

程序的靜態描述有：程序由三部分組成：程式，資料集合和程序控制塊(pCB)。

程式表示要完成的功能，資料集合表示程式執行時的資料部分和工作區。這二者是程序的物質基礎。

如果一個程式是多程序同時共享執行，則為不可修改的部分，表現為純碼的形式，資料集合為為一個程序獨用，為可以修改部分。

pCB程序控制塊，表示了程序的描述資訊、控制資訊和資源資訊，是程序動態特性的集中反應。是系統感知程序的唯一實體，一個程序的pCB全部或者部分常駐記憶體。

pCB包含的控制資訊中有程序的當前狀態。

程序的的狀態只有五種狀態：初始態，就緒態，執行態，等待狀態和終止狀態。

執行：程序已經分配到處理機，程式正由處理機執行。

等待：程序因為等待某一事件而暫時不能執行的狀態。

就緒：程序已具備執行條件，但是因為處理機已由其他程序佔用，所以暫時不能執行而等待分配處理機。

互斥和同步

互斥：一組併發程序中的一個或者多個程式段，因共享某一公有資源而導致它們必須以一個不允許交叉執行的單位執行。不允許兩個及以上的共享該資源的併發程序同時進入臨界區。

臨界區：不允許多個併發程序交叉執行的一段程式稱為臨界區。

1、臨界區的鎖操作方法：給每個臨界區設定一把鎖，有兩個狀態，開啟或者關閉。步驟如下：關鎖操作，如果鎖開著就關閉，如果鎖關閉則等待開啟;執行臨界區程式;開鎖操作，將鎖開啟，退出臨界區。某個程序進入臨界區會檢測鎖是否開啟，如果關閉則等待開啟。

上鎖實現互斥，缺點：影響系統可靠性和效率，比如多併發，每個程序都要測試臨界區鎖狀態，開銷很大。存在cpu浪費和不公平現象。

2、“訊號量”

訊號量，sem為與臨界區內所使用的公用資源有關的訊號量。

p表示sem-1，V則sem+1，多程序併發時，和上鎖不一樣，如果無法使用臨界區，不是再次檢測，而是進入等待佇列。sem>=0,表示可供併發程序使用的資源實體數;sem<0,等待使用臨界區的程序數。

p:(1)sem=sem-1(2)sem>=0,p返回，程序繼續執行(3)sem<0，程序被阻塞後與該訊號相對應的佇列中。

V：(1)sem=sem+1(2)sem>0，V停止執行，程序返回呼叫處，繼續執行(3)sem<=0,從該訊號的佇列中喚醒一等待程序，然後再返回原程序繼續執行或轉程序排程。

pV操作對於每一個程序來說，都只能進行一次，而且必須成對使用。在pV原語執行期間不允許有中斷的發生。

pV實現互斥：(1)sem初始值為1(2)程序p1進入臨界區，執行p操作，sem=0，程序進入臨界區執行(3)程序p2進入臨界區，執行p操作，sem=-1，p2被阻塞，進入訊號對應等待佇列(4)p1執行V操縱，sem=0，喚醒p2進入就緒佇列，進行排程，進入臨界區(5)p2執行V操作，sem=1，恢復初始狀態。

同步：把非同步環境下的一組併發程序，因直接制約而互相傳送訊息而進行互相合作、互相等待，使得各程序按一定的速度執行的過程稱為程序間的同步。

3.程序，執行緒，作業，程式。

作業：是使用者需要計算機完成的`某項任務，而要求計算機所作工作的集合。

程序：是一個程式對某個資料集的執行過程，是分配資源的基本單位。

程式：描述計算機所要完成的獨立功能，並在時間上嚴格得按照前後次序相機地進行計算機操作序列集合，是一個靜態的概念。

執行緒：是在程序內排程和佔有處理機的基本單位。由於執行緒比程序更小，基本上不擁有系統資源，故對它的排程所付出的開銷就會小得多，能更高效的提高系統內多個程式間併發執行的程度。

程序和程式：

程序是程式的一次執行活動，是動態的，程式是靜態指令;

一個程序可以執行一個或者多個程式，同一程式也可由多個程序執行;

程式作為資源長期保留，程序則是執行過程，是暫時的。

程序和執行緒：

程序是資源管理的基本單位;執行緒是處理機排程的基本單位。

以程序為單位進行處理機切換和排程，切換時間長，資源利用率低;執行緒為單位，不發生資源變化，切換實踐短，效率高。

程序和作業：

4.哲學家就餐：

有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一隻空盤子，每兩人之間放一隻筷子每個哲學家的行為是思考，感到飢餓，然後吃通心粉.為了吃通心粉，每個哲學家必須拿到兩隻筷子，並且每個人只能直接從自己的左邊或右邊去取筷子，任一哲學家在自己未拿到兩支筷子吃飯前，絕不放下手中的筷子。

(1)保證不會出現兩個鄰座同時要求吃飯

思路：鄰座使用筷子時的程序互斥，使用訊號量。設定五個訊號量，初始為1，表示對應編號的筷子，有人使用，訊號量執行p操作，鄰座需要使用筷子時，對兩側的筷子均執行p操作，進入等待佇列。吃完後，執行V操作，鄰座進入就緒狀態，可以開始就餐。

會出現問題，就是每人都拿一個筷子，誰也吃不上的死鎖。

(2)既沒有兩鄰座同時吃飯又沒人餓死

思路：奇數號的哲學家先取右手的筷子，偶數號的先取左手的。然後還是使用訊號量實現互斥。

5.死鎖

若干程序競爭使用資源，如果每個程序都佔有了一定資源，又申請使用已被另一程序佔用且不能搶佔的資源，則所有的程序將紛紛進入等待狀態，不能繼續執行。這種情況叫做死鎖。

產生死鎖的原因主要是：(1) 因為系統資源不足。(2) 程序執行推進的順序不合適。(3)資源分配不當等。根本原因在於系統提供的資源數小於併發程序所要求的該類資源數。

產生死鎖的四個必要條件：(1) 互斥條件：一個資源每次只能被一個程序使用。(2)部分分配：程序每次申請它所需要的一部分資源，在等待新資源的同時，繼續佔用已分配到的資源。(3)不剝奪條件:程序已獲得的資源，在末使用完之前，不能強行剝奪。(4)環路條件:存在程序迴圈鏈，鏈中每個程序已獲得的資源同時被下一個程序所請求。

解決死鎖：

預防：採用策略，是的四個必要條件在系統執行的任何時間均不滿足。

避免：動態分配資源，避免死鎖。

恢復：檢測死鎖的位置和原因，通過外力破壞死鎖發生的必要條件。