之后會發布基于基礎知識的大部分算法的模擬代碼合集，敬請關注。

進程基礎

進程的基本概念

程序順序執行的特征：

1）順序性：處理機嚴格按照程序所規定的順序執行，每一步操作必須在下一步操作開始前執行

2）封閉性：程序在封閉的環境下運行，程序獨占資源，資源的狀態由程序決定，程序一旦開始執行，外界環境不會影響程序的執行結果。

3）可再現性：只要程序的初始條件和環境相同，程序的執行結果就相同。
程序的并發執行的特征：（順序執行會浪費資源）

1）間斷性：程序共享系統的資源，以及為完成同一個任務共同合作，并發執行的程序之間相互制約，（不是運行完一個在運行另一個）

2）失去封閉性：各程序共享系統資源，資源的狀態由各程序所決定。

3）不可再現性：由于失去了封閉性，（即初始的環境狀態和條件相同，程序的執行結果卻可能不同），該特征超級垃圾，必須想辦法避免。
進程的概念：

具有獨立功能的程序在某一個數據集合上的執行過程，它是系統進行資源分配和調度的一個獨立單位。

進程的特征：

結構特征：

PCB（進程控制塊），與進程共存亡，用于記錄進程的基本情況和活動過程，一般常駐內存
程序段（一般為需要的時候動態調入內存），描述要完成的功能
數據段（一般為需要的時候動態調入內存），操作的對象即工作區

動態性：進程最基本的特征，進程不是靜態的，而是動態的，它由創建而產生，由調度（這里主要指進程調度，而不是作業調度）而執行，由撤銷而消亡
并發性：指多個進程實體存于內存中，且能在同一時間段內執行，（這里同操作系統的并發性）
獨立性：進程實體是一個能獨立運行，獨立獲得資源和獨立接收調度的基本單位
異步性：同操作系統的異步性

進程的三種基本狀態：
- 就緒狀態：進程已經分配到除了CPU之外的所有資源，只要獲得CPU便可以立刻執行，處于就緒狀態的進程維持一個就緒隊列。
- 執行狀態：已經獲得CPU，正在執行的進程。（單處理機系統中，同一時刻只能有一個進程處于執行狀態，多處理機系統中，可以同時有多個進程處于執行態）
- 阻塞狀態/等待狀態：在執行的過程中由于發生某些事件（I/O請求，申請緩存等），暫時無法執行的進程，是由于進程本身引起的阻塞。處于阻塞狀態的進程可以維持一個阻塞隊列。
- 進程是自己阻塞自己的，但是阻塞的進程需要其他進程將其喚醒
三種基本狀態的轉換：

? 就緒—>執行：進程調度，獲得CPU資源

? 執行—>就緒：在分時操作系統中時間片花完

? 執行—>阻塞：I/O請求，申請緩存等，自己被迫進入阻塞狀態

? 阻塞—>就緒：I/O完成，造成阻塞的原因得到解決（又變成只差CPU的狀態）

進程的創建狀態和終止狀態

創建狀態：進程成為就緒狀態之前的狀態

終止狀態：當一個進程到達了自然結束點，或者遇到無法客服的困難，或者被操作系統所終結等的時候，就進入了終止狀態。
掛起操作及引入的原因：

1）進程被掛起之后處于靜止狀態。

2）引入的原因：
- 終端用戶的需要：當終端用戶想要暫停自己程序的運行的時候
- 父進程請求：當父進程想要掛起某個子進程的時候
- 負荷調節的需要：當實時系統中的工作負荷較重，系統可以將某些不重要的進程掛起，保證程序的正常運行。
- 操作系統的需要：操作系統有事需要將某些進程掛起，已檢查運行過程中資源的使用情況
3）引入掛起操作后，進程的狀態轉換：

?

（1）阻塞態可以通過釋放變為就緒態。活動阻塞釋放變為活動就緒，靜止阻塞釋放變為靜止就緒。

（2）活動態和靜止態可以進行相互轉換，活動到靜止稱為掛起，靜止到活動可以稱為激活。活動態和靜止態最本質的區別為活動態在內存中，靜止態暫時調出內存，進入外存

（3由執行態可以直接變為靜止就緒態，即時間片用完，直接調離內存

（4）靜止態（外存）必須通過激活變為非靜止態（調入內存）才能夠參與進程的三臺轉換。

4）進程掛起之后不是原封不動的將進程移出內存，而是會先將一些必要的信息寫入外存。再釋放PCB
進程管理中的數據結構
- 操作系統中用于管理控制的數據結構：內存表，設備表，文件表，進程表（程序控制快PCB）
- 進程控制塊PCB的作用：
  
  1）作為獨立運行基本單位的標志
  
  2）能實現間斷性的運行方式
  
  3）提供進程管理所需要的全部信息
  
  4）提供進程調度所需要的全部信息
  
  5）實現與其他進程的同步和通信
- 進程控制塊中的信息：
  
  進程標識符：唯一表示一個進程，有兩種：
  
  1）外部標識符：方便用戶對進程的訪問，通常有數字和字母組成
  
  2）內部標識符：方便系統對進程的訪問，每一個進程有一個唯一的數字標識符。
  
  處理機狀態：（主要指的是處理機中寄存器的狀態）
  
  1）通用寄存器：又稱為用戶寄存器，用戶的程序可以訪問，用于暫存信息，一般為8~32個
  
  2）指令計數器：存放了將要訪問的下一條指令的地址。
  
  3）程序狀態字（PSW?）：含有狀態信息，條件碼，執行方式（指在系統還是用戶狀態下執行），中斷屏蔽標志（允不允許在執行的過程中被打斷）
  
  4）用戶棧指針：每個用戶進程都有系統棧，用于存放過程和系統調用參數及調用地址。
  
  進程調度信息
  
  1）進程狀態：指明了進程的當前狀態
  
  2）進程優先級：即一個整數，用于描述進程使用CPU的優先級，數字越大，優先級越高
  
  3）其他信息：與采用的進程調度算法有關
  
  4）事件：指進程由執行狀態變為阻塞狀態所等待發生的事件。
  
  進程控制信息
  
  1）程序和數據的地址：由于程序段和數據段并不是常駐內存的，而是使用的時候才調入，因此需要保存其地址
  
  2）進程同步和通信機制：
  
  3）資源清單：一張清單列出了該進程在運行期間所需的全部資源（除了CPU資源），另一張列出了分配到該進程的資源的清單。
  
  4）鏈接指針：給出了本進程（PCB）所在隊列中的下一個進程的PCB的首地址。
- 進程控制塊的組織方式：
  
  線性方式：不重要
  
  鏈接方式：類似靜態鏈表，把具有同一狀態的PCB用其中的鏈接字鏈接成一個隊列
?

?

注：進程資源的分配并不是在該進程執行之前將該進程所需的資源全部分配給他，而是在其執行的過程中進行動態的分配。

進程與程序的區別與關系

進程與程序的區別：
- 進程是一個動態的概念（有 “ 生命 ” ），程序是靜態的概念。
- 進程可以具有并行性（在多處理器的系統中），但是程序沒有
- 進程是競爭系統資源的基本單位
進程與程序的關系：
- 一個程序對應多個進程，一個進程又可以為多個程序服務。

進程控制

1.基本知識

進程控制是進程管理中最基本的功能，主要包括進程的創建，進程的終止和運行中的進程的狀態轉換等功能。進程控制一般是由OS的內核中的原語來實現的。

2.進程的創建

進程的層次結構
進程圖
引起進程創建的事件

1）用戶登錄：在分時系統中，用戶成功登錄，系統將為該用戶分配新的進程

2）作業調度：在多道批處理系統中，作業調度程序將某些作業調度內存，并且為他們創建進程

3）提供服務：運行中的用戶程序提出某種請求

4）應用請求：由用戶進程自己創建，幫助自己完成特定的任務
==進程的創建過程：==OS調用進程創建原語Create創建一個新進程

1）申請空白PCB：新進程獲得一個唯一的數字標識符（對于操作系統）

2）為新進程分配器運行所需的資源：包括物理資源和邏輯資源

3）初始化進程控制塊PCB：

（1）初始化標識符信息：系統分配的標識符信息裝入PCB

（2）初始化處理機狀態信息：主要為一些寄存器

（3）初始化處理機控制信息：一般初始化為就緒狀態

（4）如果進程就緒隊列允許，將進程插入就緒隊列

3.進程的終止

引起進程終止的事件：

1）正常結束

2）異常結束：1）越界錯誤（訪問自己范圍外的），2）保護錯誤（訪問自己無權利訪問的）3）非法指令：試圖運行不存在的指令，4）特權指令；5）運行超時；6）等待超時；7）算術運算錯；8）I/O故障

3）外界的干預：1）操作員或者操作系統干預；2）父進程的請求（父進程的權利大于子進程）3）父進程的終止：當父進程終止時，其所有子進程也應當終止。
==進程終止的過程：==OS調用進程終止原語

1）根據要終止的進程的標識符，搜索出該進程的PCB，從中獲得該進程所處的狀態

2）如果該進程正處于執行狀態，立刻終止該進程，并且置調度標志為真，表示在該進程結束后應該進行重新調度（即不要讓CPU空閑）

3）若該進程有子孫進程，讓其所有子孫進程都終止。

4）被終止進程所擁有的所有資源歸還給父進程或者操作系統

5）將終止進程的PCB從所在隊列中移除，等待其他程序來收集信息。

4.進程的阻塞與喚醒

引起進程阻塞和喚醒的事件：阻塞和喚醒是相對應的

1）向系統請求共享資源失敗

2）等待某種操作的完成

3）新數據尚未到達

4）等待新任務的到達
進程阻塞的過程：進程通過調用阻塞原語block==將自己==阻塞

1）進入block后立即停止執行

2）保存現場

3）將進程控制塊中的現行狀態改為阻塞，并將PCB插入阻塞隊列

4）轉調度程序，進行重新調度
進程喚醒的過程：當阻塞的進程所期待的事件發生時，有關進程（不是本身）調用喚醒原語wakeup，將等待該事件的進程喚醒。喚醒之后進入就緒隊列。

1）將被阻塞的進程從等待該事件的阻塞隊列中移除

2）將PCB的現行狀態由阻塞改為就緒

3）然后再將該PCB插入就緒隊列中

4）轉進程調度或者返回
block原語和wakeup原語是一對作用剛好相反的原語，必須成對使用。

5.進程的掛起與激活

進程的掛起過程：當出現了引起進程掛起的事件之后，OS利用掛起原語將指定的進程掛起（即調出內存）

首先檢查進程的狀態（不同的狀態采取不同的處理方式），若該進程正處于活動就緒狀態，將其改為靜止就緒態；若該進程處于活動阻塞狀態，將該進程改為靜止阻塞狀態；若該進程處于執行狀態，將其改為靜止就緒狀態，調度程序重新進行調度。
進程的激活過程：

1）首先將進程從外存調入內存，

2）檢查進程所處的狀態，如果進程處于靜止就緒，將其改為活動就緒，如果處于靜止阻塞，將其改為活動阻塞

3）檢查進程的優先級，如果優先級高，可以進行搶占當前運行進程的資源

4.進程同步

1.進程同步的基本概念

進程同步的目的：1）按照一定的規則共享系統資源；2）對多個相關進程在執行次序上進行協調，是程序具有可再現性。
兩種形式的制約關系：

1）間接相互制約關系：多個進程在并發執行時，由于共享系統的臨界資源而相互制約，如磁帶機，打印機，表格等。（互斥）

2）直接相互制約關系：多個進程為完成同一任務而相互合作（同步）
**臨界資源：**一次僅允許一個進程使用的共享資源。例如打印機，磁帶機，表格等。
互斥和同步的概念：

1）互斥：并發的多個進程由于競爭同一資源而產生的相互排斥的關系

2）同步：進程間共同完成一項任務時直接發生相互作用的關系
臨界區：每個進程中訪問臨界資源的那段代碼

/*一個訪問臨界資源的循環進程*/
while(true)
{進入區：//對欲訪問的臨界資源進行檢查，查看其是否正被訪問，如果此刻臨界資源未被訪問，進程便可以進入臨界區對臨界資源進行訪問，并設置它正被訪問的標志，如果此刻臨界資源正被訪問，則不能進入臨界區。即后邊的wait（）操作臨界區：//執行臨界資源的那段代碼退出區：//將臨界區正被訪問的標志恢復為未被訪問的標志，signal（）操作剩余區：//除上述三個區之外的代碼叫做剩余區
}

同步機制應遵循的原則：

1）空閑讓進

2）忙則等待

3）有限等待：不能一直等

4）讓權等待：進程不能進入臨界區，就應當釋放==處理機==，讓權指讓出處理機

2.硬件同步機制

3.信號量機制：Dijkstra提出

信號量：
- 是一種數據結構
- 值與相應資源的使用情況有關
- 僅與P，V操作有關，P，V代表兩種原子操作，P為等候原語wait（S）,V為釋放原語signal（S）。
- wait操作即在申請資源，signal操作是釋放資源
- wait操作其實就是進入臨界區之前的進入區，signal操作是從臨界區出來之后的退出區
- 原子操作的特點，操作一開始執行，半中間不可以打斷，原語即為原子操作。

整型信號量

概念：Dijkstra把整型信號量定義為一個用于表示資源數目的整型量S。

/*等候原語*/
wait(S){while(S <= 0);  //當S<=0的時候便一直處于等待狀態，直到獲得相應的資源，不符合讓權等待的原則      S--;     //獲得資源后，資源的數目減一，S表示該類資源可用的數目      
}/*釋放原語*/
signal(S){S++;      //釋放資源后，資源的數目加一     
}

優缺點：

優點：實現簡單

缺點：違背了同步機制中的讓權等待原則，浪費資源（只要S<=0，就會等待）

**記錄型信號量：**當前用的最多的

特點：采用了記錄型的數據結構

/*記錄型數據結構*/
typedef struct{int value;      //>=0的時候，表示系統中可用資源的數量，<0的時候其絕對值表示因為該資源而阻塞的進程的數目struct process_control_block *list;    //維持阻塞隊列的指針
}semaphore;/*等待原語*/
wait(semaphopre *S){S->value--;    //一個進程過來，首先將S->value--；if(S->value < 0){     //<0表示資源已經用光，將該進程加入阻塞隊列block(S->list);}
}/*釋放原語*/
signal(semaphore *S){S->value++;      //釋放資源，S->value++；if(S->value <= 0){      //S->value++之后，還<=0，直接喚醒一個阻塞的進程，喚醒的進程擁有了該資源的使用權（不需要再次執行P操作），然后進入就緒隊列。如果>0，直接將資源釋放即可wakeup(S->list);}
}

wait操作：每次都相當于進程請求一個單位的該類資源

signal操作：每次都相當于釋放一個單位資源
當S->value的初值為1的時候，表示只允許一個進程訪問臨界資源，信號量轉化為互斥型信號量
優點：通過維持阻塞隊列的指針，使得滿足了讓權等待的原則，彌補了整型信號量的缺點
**缺點：**只適用于對單一資源的管理，如果一個進程需要請求多類資源的時候，很容易產生死鎖。

AND型信號量：解決記錄型信號量會發生的死鎖的問題
- 當一個進程需要兩個或者更多的共享資源來完成一個目標的時候，多個進程之間可能會發生阻塞（剛開始前半部分資源占有了，但是后半部分資源無法獲得，自己再阻塞自己，即發生了死鎖）
- AND的解決思想：將一個進程運行過程中所需要的全部資源一次性都分給他，待進程使用完之后，在一起進行釋放。（即一起申請，一起釋放）
```
/*等候原語：全分配*/
Swait(S1, S2, …, Sn){While(TRUE){//多類資源同時滿足的時候才進行分配，先判斷再分配。if (S1 >=1 and … and Sn>=1 ){for( i=1 ;i<=n; i++) Si - -;break;}else{Place the process in the waiting queue associated with the first Si found with Si <1,and set the progress count of this process to the beginning of Swait operation	（將即將阻塞的進程掛到第一個不能滿足他的資源的阻塞隊列，然后設置該進程的起始地址為Swait操作的開始）}}
}/*釋放原語：全釋放*/
Ssignal(S1, S2, …, Sn){while(TRUE){    for (i=1; i<=n; i++) {Si++ ;Remove all the process waiting in the queue associated with Si into the ready queue（將因為該資源得不到滿足而阻塞的所有進程都從阻塞隊列釋放進入就緒隊列，重新進行排隊）}}
}
```
注意：

1）在分配資源的時候首先判斷是否所有資源均全部滿足相應的條件，滿足才進行分配。

2）釋放的時候是將因為該資源得不到滿足而阻塞的所有進程都從阻塞隊列釋放進入就緒隊列，重新進行排隊，因為OS需要根據調度算法重新選取新的進程占據CPU
信號量集

Swait(S1, t1, d1; …; Sn, tn, dn)if (S1>= t1 and … and Sn>= tn) thenfor i:=1 to n doSi:= Si - di ;endforelsePlace the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait Operationendif

注意：

1）繼承了AND型信號量的思想，先判斷是否所有所需資源均滿足條件。滿足才進行分配。

2）引入了下限值的概念。Si表示可用的資源的數量；ti表示想要分配資源成功至少需要的該資源的數目（ti（下限值）包括兩部分，一部分是系統執行該進程所需，另一部分是該進程所請求的，因此一般大于di）；di表示該進程所請求的該類資源的數目。

4.信號量的應用

1、利用信號量實現進程互斥

semaphore  mutex =1;beginparbeginprocess 1: beginrepeatwait(mutex);critical sectionsignal(mutex);remainder sectionuntil false;endprocess 2: beginrepeatwait(mutex);critical sectionsignal(mutex);remainder sectionuntil false; endparend        end

注意：

1）利用信號量實現進程互斥地訪問某種資源。首先應將mutex設為1

2）wait操作和signal操作必須成對地出現，如果缺少wait操作可能會造成系統的混亂；如果缺少signal操作，那么該資源永遠不會得到釋放，因該資源而被阻塞的進程也將永遠不會被喚醒。

2、利用信號量實現前驅關系圖（進程同步）

如下圖：

semaphore  a, b, c, d, e, f, g = 0, 0, 0, 0, 0, 0, 0;beginparbeginbegin  S1; signal(a); signal(b); end;begin  wait(a); S2; signal(c); signal(d); end;begin  wait(b); S3; signal(e); end;begin  wait(c); S4; signal(f); end;begin  wait(d); S5; signal(g); end;begin  wait(e); wait(f); wait(g); S6; end;parendend

注意：

1）信號量的初值必須被設置為0，必須等某個進程之前的進程完之后，釋放資源，后邊的進程才能夠執行。

經典的進程同步問題

普通版：一類進程作為生產者，生產產品，生產的產品放入一個緩沖區，消費者從緩沖區中取出產品，需要保證生產者不可以向滿的緩沖區中添加產品，消費者不可以從空的緩沖區中取出產品。同一時刻只可以有一個生產者生產產品或者消費者消費產品。

升級版可以實現同一個時刻既有生產者生產產品，又有消費者消費產品。但是絕對不可以同一時刻多個生產者生產產品或者多個消費者消費產品。同時使用count記錄緩沖區中產品的數量。

生產者消費者問題

1）生產者進程和消費者進程都以異步方式運行，但它們之間必須保持同步。

2）可利用互斥信號量$mutex$實現諸進程對緩沖池的互斥使用（不可以同時既向緩沖區中放入數據，又從緩沖區中拿出數據）；利用資源信號量empty和full分別表示緩沖池中空緩沖池和滿緩沖池的數量。假定這些生產者和消費者相互等效

/*
in表示放入數據的地址，out表示取出數據的地址
buffer[n]：表示大小為n的緩沖池（由多個緩沖區組成） 
mutex，mutex1，mutex2：互斥型信號量，初值為1
empty，full：資源型信號量，empty表示空緩沖區的數量，full表示滿緩沖區的數量
item：表示一個數據項
*/
Int in=0,out=0;  
Item buffer[n];   
Semaphore mutex1=1,mutex2 = 1,empty=n,full=0;  //生產者
Void producer(){ do{生產一個產品放入nextp;/** 進入區* 先申請資源信號量，在申請互斥信號量* mutex1控制同一個時間段內只能有一個生產者生產產品*/wait(empty);wait(mutex1);/*臨界區*/buffer[in]=nextp;in=(in+1) % n;/*退出區*/signal(mutex1);signal(full);/*對計數器count的互斥訪問*/wait(mutex);count++;signal(mutex);}while(TRUE)
}//消費者
Void consumer(){ do{/*進入區*/wait(full);wait(mutex2);     //消費者對緩沖區的互斥訪問/*臨界區*/nextc =buffer[out];          //只有一份out =(out+1) mod n;/*退出區*/signal(mutex2);signal(empty);/*對計數器count的互斥訪問*/wait(mutex);count--;signal(mutex);消費 nextc中的產品;                        }while(TRUE)
}Void main(){cobeginproceducer();consumer();coend
}

注意：

1）每個程序的互斥操作wait（）和signal（）必須成對的出現。

2）輸入進程不可以向滿的緩沖池中輸入數據，計算進程不可以從空的緩沖池中取數據

3）在每個程序中的多個wait操作順序不能顛倒，必須先執行對資源信號量的wait操作，在進行對互斥信號量的wait操作，否則可能引起進程死鎖。

4）可以使用三個互斥信號量mutex、mutex1、mutex2實現同一時刻既有生產者生產，又有消費者消費。

讀者—寫著問題

該問題涉計兩類進程，第一類進程是讀進程Reader，另一類進程是寫進程Writer，多個讀進程可以同時讀一個文件（共享資源），多個寫的進程不可以同時寫一個文件（對寫互斥），并且讀的時候不能寫，寫的時候不能讀（對讀互斥）。

1）問題核心：保證一個Writer進程必須與其他進程互斥地訪問共享對象的同步問題。

2）只要求讀文件的進程稱為“Reader進程”，其它進程則稱為“Writer進程”。

3）允許多個進程同時讀一個共享對象，但不允許一個Writer進程和其他Reader進程或Writer進程同時訪問共享對象（共享對象并不是臨界資源，因為他允許多個進程對其訪問）

/*
記錄型信號量解決讀者—寫者問題rmutex：讀進程對Readcount的互斥
wmutex：writer對reader和writer的互斥
readcount：表示正在讀的進程數目，只有當readcount=0的時候才需要申請wmutex權限，大于0的時候不需要
*/semaphore rmutex=1, wmutex =1;
int readcount =0;
Void Reader(){do{wait(rmutex);          //防止多個reader進程對readcount的訪問if (Readcount==0){    //如果readcount不等于0，表示有進程正在進行讀操作，絕對沒有寫操作wait(wmutex);}Readcount ++;signal(rmutex);…讀;…wait(rmutex);Readcount - -;if (Readcount==0){      //只有等于0的時候才需要釋放資源，使得寫進程可以工作signal(wmutex);}signal(rmutex);}while(TRUE);
}
Void writer(){do{wait(wmutex);      //申請寫權限的資源寫;signal(wmutex);}while(TRUE);
}Void main(){cobeginreader();  writer();Coend
}

利用信號量集的機制實現讀者-寫者問題

int RN;
semaphore L = RN;             //表示讀者的數量
mx = 1；						//對寫者進行互斥的訪問void Reader(){while(true){Swait(L, 1, 1);         //申請一個讀者進程Swait(mx, 1, 0);       //判斷當前是否有寫者進程在寫，該出相當于一個開關operation...Ssignal(L, 1);}
}void Writer(){while(true){//此處首先申請一個mx，如果當前系統中無寫者進程，則該語句必定執行成功，Reader進程中的//Swait（mx, 1, 0）便處于關閉狀態，只需要等系統中的讀進程執行完畢，(L, RN，0)執行成//功，打開開關即可。Swait(mx, 1, 1; L, RN, 0);operation...；//釋放一個寫進程Ssignal(mx, 1);}
}void main(){cobeginReader();Writer();coend;
}

哲學家的進餐問題

五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在桌子上有五只碗和五只筷子，他們的生活方式是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時便試圖取用其左右最靠近他的筷子，只有在他拿到兩只筷子時才能進餐。進餐畢，放下筷子繼續思考。

/*
記錄型信號量解決問題
*/
//每一只筷子均為臨界資源
semaphore chopstick[5]={1,1,1,1,1};
//所有的信號量均被初始化為1，第i位哲學家的活動可描述為：
do{wait(chopstick[i]);          //拿左手的筷子wait(chopstick[(i+1) mod 5] );      //拿右手的筷子…eat;…signal(chopstick[i]);    //放左手signal(chopstick[(i +1)mod 5]);       //放右手…think;
}while(TRUE);

存在的問題：假如五位哲學家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0，當他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限等待。進入死鎖狀態。

解決辦法：

**1）**至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。

semaphore chopstick[5]={1，1，1，1，1};
semaphore count=4;
void philosopher(int i)
{while(true){think();wait(count); //請求進入房間進餐wait(chopstick[i]); //請求左手邊的筷子wait(chopstick[(i+1)%5]); //請求右手邊的筷子eat();signal(chopstick[(i+1)%5]); //釋放右手邊的筷子signal(chopstick[i]); //釋放左手邊的筷子signal(count); //退出房間釋放信號量}
}

**2）**僅當哲學家的左右兩只筷子均可用時，才允許他拿起筷子進餐。

/*
使用AND型信號量解決，本質當同時擁有兩只筷子的時候才允許拿起筷子進餐
*/
semaphore chopstick[5]={1,1,1,1,1};
Philosopher i
do{think;Swait(chopstick[(i+1)mod 5],chopstick[i ]);     //同時分配兩只筷子eat;Ssignal(chopstick[(i+1)mod 5], chopstick[i ] );     //同時放下兩只筷子  
}while(TRUE)

**3）**規定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數號哲學家則相反。

semaphore chopstick[5]={1,1,1,1,1};
//第i 位哲學家的活動可描述為：
do{//奇數位哲學家先拿左手的筷子if  i mod 2=1 {wait(chopstick[ i ]);wait(chopstick[ ( i +1) mod 5] )}//偶數位哲學家先拿右手邊的筷子else{wait(chopstick[ ( i +1) mod 5] );wait(chopstick[ i ])}eat;signal(chopstick[ i ]);signal(chopstick[(i +1)mod 5]);…think;
}while(TRUE)

處理機調度

調度層次
1. 高級調度（作業調度）
2. 中級調度（進程調度）
3. 低級調度
作業調度
1. FCSF先來先服務，作業等待時間得長短。比較有利于長作業（進程），而不利于短作業（進程）。
2. SJF短作業優先，作業的運行時間。
  1. 優點：能有效的降低作業的平均等待事件，提高系統吞吐量。
  2. 缺點：對長作業不利；該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業（進程）會被及時處理；由于作業（進程）的長短含主觀因素，不一定能真正做到短作業優先。

1. 高響應比優先??

優先權=等待時間+要求服務時間/要求服務時間

1. RR輪轉調度算法，時間片的確定要適中
2. 多級反饋隊列
3. EDF最早截至時間優先

下圖中有兩個周期性任務，任務A的周期時間為20ms，每個周期的處理時間為10ms；任務B的周期時間為50ms，每個周期的處理時間為25ms

1. LLF最低松弛度優先

松弛度=必須完成時間-其本身的運行時間-當前時間

進程切換條件：有任務完成；有任務松弛度降到0。

死鎖
1. 定義：是指多個進程在運行過程中因為爭奪資源而造成的一種僵局，當進程處于這種狀態時，若無外力作用，他們都將無法再向前推進
2. 原因：競爭資源（不可搶占資源，可消耗資源），進程間推進順序非法。
3. 產生死鎖得必要條件：互斥條件、請求和保持條件、不可搶占（不可剝奪）條件、環路等待條件
4. 處理死鎖的基本方法：
  1. 預防死鎖：破壞產生死鎖得必要條件，其中破壞互斥條件是最不實際的
    1. 破壞“請求和保持”條件：系統規定所有進程在開始運行之前，都必須一次性的申請其在整個運行過程所需的全部資源
    2. 破壞“不剝奪”條件
    3. 破壞“環路等待”條件：所有進程對資源的請求必須嚴格按照資源序號遞增的次序提出
  2. 預防死鎖：銀行家算法、安全性算法
  3. 檢測死鎖：資源分配圖，死鎖定理
  4. 解除死鎖：剝奪資源（從其他進程剝奪足夠數量的資源給死鎖進程以解除死鎖狀態。），撤銷進程（最簡單的是讓全部進程都死掉；溫和一點的是按照某種順序逐個撤銷進程，直至有足夠的資源可用，使死鎖狀態消除為止。）
銀行家算法
1. 安全狀態

1. 銀行家算法

T0時刻的安全性：用安全性算法對T0時刻的資源分配情況進行分析，存在著一個安全序列{P1,P3,P4,P2,P0}，故系統是安全的

P1發出資源請求向量Request1(1,0,2)，系統按銀行家算法檢查:

（1）Request1(1,0,2)<=Need1(1,2,2)

（2）Request1(1,0,2)<=Available1(3,3,2)

（3）系統先假定可為P1分配資源，并修改向量Available，Allocation1，Need1

（4）再利用安全性算法檢查此時系統是否安全。如下表:

由安全性檢查得知，能找到一個安全序列{P1,P3,P4,P0,P2}，因此，系統是安全的，可以立即將P1所申請的資源分配給它。

死鎖定理：S狀態為死鎖狀態的充分條件是當且僅當S狀態的資源分配圖是不可完全簡化的。<死鎖定理>

存儲器

重定位

程序的裝入

絕對裝入方式
可重定位的裝入方式（靜態）
動態運行時裝入方式（動態）重定位寄存器

內存的分配方式

連續的分配方式
離散的分配方式

連續的分配方式

單一連續分配：一道程序在內存中，內存浪費嚴重
固定分區分配：程序變多缺點：會產生內碎片
動態分區分配（重點）不能消除外碎片? 思想：按需分配
可重定位的分區分配
1. 在動態分區分配方式上增加一個緊湊（拼接碎片）功能
2. 以動態運行時裝入方式為前提

動態分區分配算法?

首次適應算法FF

??? FF算法要求空閑分區表以地址遞增的次序排列。在分配內存時，從表首開始順序查找，直至找到一個大小能滿足要求的空閑分區為止；然后按照作業的大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑分區表中。若從頭到尾不存在滿足要求的分區，則分配失敗。

優點：優先利用內存低址部分的內存空間

缺點：低址部分不斷劃分，產生小碎片（內存碎塊、內??? ? 存碎片、零頭）；每次查找從低址部分開始，增??? ? 加了查找的開銷

循環首次適應算法NF

在分配內存空間時，從上次找到的空閑分區的下一個空閑分區開始查找，直到找到一個能滿足要求的空閑分區，從中劃出一塊與請求大小相等的內存空間分配給作業。

優點：使內存空閑分區分布均勻，減少查找的開銷

缺點：缺乏大的空閑分區

最佳適應算法BF

所謂“最佳”是指每次為作業分配內存時，總是把能滿足要求、又是最小的空閑分區分配給作業，避免“大材小用”。要求將所有的空閑分區按其容量以從小到大的順序形成一空閑分區鏈。

??? 缺點：產生許多難以利用的小空閑區

離散的分配方式

分頁存儲管理方式

（可能在最后一頁產生內碎片）進程分頁，內存分塊（頁和塊等大小）?

頁表

頁式地址映射

（邏輯地址轉換城物理地址）

地址轉換機構（頁表在內存，頁表寄存器快表。頁表很龐大時采取兩級或多級頁表）

有快表有頁表，先查快表；沒有快表查頁表

分段存儲管理方式

（不可能有內碎片產生，外碎片不可避免）進程分段，各段在內存。段與段之間離散分配，某一段在內存中連續分配
計算：給定邏輯地址合成物理地址段表

段頁式存儲管理方式

進程分段，段內分頁，內存分塊

1. 分頁和分段的主要區別

相似點：采用離散分配方式，通過地址映射機構實現地?????? 址變換

不同點：頁是信息的物理單位，分頁是為了滿足系統的??? 需要；段是信息的邏輯單位，含有一組意義相對完??? 整的信息，分段是為了滿足用戶的需要。

頁的大小固定且由系統確定，由系統把邏輯地址分為頁號和頁內地址，由機器硬件實現；段的長度不固定，取決于用戶程序，編譯程序對源程序編譯時根據信息的性質劃分。

分頁的作業地址空間是一維的；分段的作業地址空間是二維的。

輸入輸出系統

I/O設備：輸入輸出和存儲功能的設備

I/O設備的分類

按傳輸的速度：

低速設備（如鍵盤、鼠標、語音輸入輸出設備）? 中速設備（如行式打印機、激光打印機等）

高速設備（如磁帶機、磁盤機、光盤機等）。

設備按信息交換的單位分類

塊設備：用于存儲信息。對于信息的存取總是以數據塊為單位。典型例子是磁盤。該類設備基本特征是傳輸速率較高，另一特征是可尋址。

字符設備：用于數據的輸入和輸出。基本單位是字符。如交互式終端、打印機等。其基本特征是傳輸速率較低，另一特征是不可尋址。

設備按其共享屬性分類

獨占設備：指在一段時間內只允許一個用戶、進程訪問的設備，即臨界資源。應互斥的訪問之。

共享設備：指在一段時間內允許多個進程同時訪問的設備。對每一時刻而言仍然是一個進程訪問。如磁盤。

虛擬設備：指通過虛擬技術將一臺獨占設備變換為若干臺邏輯設備，供若干個用戶（進程）同時使用。

設備按其使用特性分類：

存儲設備、輸入＼輸出設備

I/O通道

其主要目的是為了建立獨立的I/O操作，去解放CPU。在設置通道后，CPU只需向通道發送一條I/O指令。通道完成任務后向CPU發中斷信號。

控制功能：CPU與設備控制器

數據傳輸：內存與外設

I/O控制方式

程序I/O方式，使用輪詢的可編程I/O方式。CPU浪費
終端驅動I/O方式，使用中斷的可編程I/O方式。CPU用較短的時間進行中斷處理。
直接存儲器訪問方式(MDA),以數據塊為單位，高效。缺點：不連續的數據塊，不能一次處理
I/O通道控制方式，通道時硬件，配合著通道程序

設備分配

前提：大中型計算機
DS：設備控制表、控制器控制表、通道控制表、系統設備表
獨占設備分配步驟：分配設備、分配控制器、分配通道

SPOOLing技術（假脫機）

定義

為緩和CPU的高速性與I/O設備低速性間的矛盾而引入了脫機輸入、脫機輸出技術。該技術是利用專門的外圍控制機，將低速設備上的數據傳送到高速磁盤上；或者相反。這樣就可以在主機的直接控制下實現脫機輸入輸出。此時外圍操作與CPU對數據的處理同時進行，我們把這種在聯機情況下實現的同時外圍操作稱為SPOOLing（Simultaneaus Periphernal Operating On—Line），或稱為假脫機操作。

組成