文章目錄
- 第一章 作業系統概述
- 第二章：行程
- 3行程同步
- 標題
第一章 作業系統概述
1，作業系統定義：作業系統(Operating System)使計算機系統中的一個系統軟體，是一些程式模塊的集合，它能以盡量有效，合理的方式組織和管理計算機的軟硬體資源，合理組織計算機的作業流程，控制程式的執行并向用戶提供各種服務功能，使得計算機系統高效地運行，（沒有廣泛接受的標準定義）
2，作業系統中一些名詞解釋
| 名詞 | 解釋 |
|---|---|
| ROM（Read-Only Memory） | 只讀記憶體 |
| RAM(Random Access Memory) | 隨機存取器，也叫主存，是與CPU直接交換資料的內部存盤器 |
| 行程（processs） | 加載到記憶體并執行的程式稱為行程 |
| 用戶模式（user mode） | 當系統執行用戶應用時，系統處于用戶模式 |
| 內核模式（kernel mode） | 當用戶請求作業系統服務時，系統必須從用戶模式進入內核模式，以滿足請求 |
| 程式計數器（program counter） | 指定下一個所要執行的指令 |
| 系統呼叫（system call） | 提供作業系統服務介面 |
作業系統中存在中斷，共享，并發，競爭等情況
1,中斷處理程序
| 步驟 | 內容 |
|---|---|
| （1） | 設備給處理器發出一個中斷信號 |
| （2） | 處理器處理完當前指令后回應中斷，延遲非常短 |
| （3） | 處理器處理完當前至指令后檢測到中斷，判斷出中斷來源并向發送中斷的設備發送確認中斷信號，確認信號使得該設備將中斷設備恢復到一般狀態 |
| （4） | 處理器開始為軟體處理中斷做準備：保存中斷點的執行程式背景關系環境，包括程式狀態字PSW，程式計數器PC的下一條指令位置，一些暫存器的值 |
| （5） | 處理器根據中斷源查詢中斷向量表，獲得與該中斷相聯系的處理程式入口地址，并將PC置成該地址，處理器開始一個新的指令周期，控制轉移到中斷處理程式 |
| （6） | 中斷處理程式開始作業，檢查I/O相關設備資訊 |
| （7） | 中斷處理結束，處理器檢測到中斷回傳指令，被中斷程式的背景關系環境從系統堆疊中被恢復處理器狀態恢復成原來的狀態 |
| （8） | PSW和PC被恢復成中斷前的值，處理器開始一個新的指令周期，中斷處理結束 |
第二章：行程
行程（process）定義：行程是一個具有一定獨立功能的程式或程式段在一組資料集合上的一次動態執行
行程=程式+執行
行程包括程式，資料和行程控制塊
2.1行程狀態
| 行程狀態 | 說明 |
|---|---|
| 新的（new） | 行程正在創建 |
| 運行（running） | 指令正在執行 |
| 等待（wating） | 行程等待發生某個事件 |
| 就緒（ready） | 行程等待分配處理器 |
| 終止（terminated） | 行程已經完成執行 |
一次只能有一個行程在處理器上運行（running）；
但是多個行程可以處于等待或就緒狀態，
2.1.3行程控制塊(process Control Block)
PCB包括行程控狀態，行程計數器，CPU計數器等等
2.1.4執行緒
一個行程至少有一個執行緒，一個行程可以運行多個執行緒，多個執行緒可共享資料
2.2行程調度
當有多個行程時，行程調度器（process scheduler)選擇一個可用行程到CPU上執行，剩下的需要等待CPU空閑并重新調度，
2.2.1調度佇列
行程在進入系統時，會被加入到作業佇列（job queue),這個佇列包括系統內的所有行程，
2.2.2背景關系切換
中斷（intirrput）導致CPU從執行當前任務改變到執行內核程式，
切換CPU到另一個行程需要保存當前行程狀態和恢復另一個行程的狀態為背景關系切換（context switch)
2.3行程創建
2.3.1行程運行
大多數作業系統對行程的識別采用的是唯一的行程識別符號（process identifier,pid)
3行程同步
3.1關于臨界區問題名詞解釋
| 名稱 | 解釋 |
|---|---|
| 同步（process synchronization) | 系統中多個行程中發生的事件存在某種時序關系，需要相互合作，完成一項任務 |
| 互斥 | 由于各行程共享資源，有些資源需要互斥使用，因此各行程間競爭使用這些資源，成為互斥 |
| 競爭條件（race condition) | 多個行程并發訪問和操作同一資料并執行結果與特訂訪問順序有關 |
| 進入區（rentry section） | 在進入臨界區前，每個行程請求許可，實作這一請求的代碼區稱為進入區 |
| 臨界區（critical section） | 行程執行到該區域時可能修改公共變數，特征：只允許一個行程在臨界區執行 |
| 退出區（exit entry） | 行程執行完臨界區代碼后進入退出區 |
| 剩余區（remainder section) | 行程執行其它代碼的區域 |
3.2臨界區問題解決方案要滿足的要求
①互斥（mutual exclusion）:如果行程Pi在臨界區內執行，那么其他行程都不能在臨界區內執行，
②同步（progress）：如果沒有行程在臨界區內執行，并且有行程需要進入臨界區，那么只有那些不在剩余區執行的行程可以參加選擇，以便確定誰能下一次進入臨界區，而且這種選擇不能無限推遲
③有限等待（bounded wating）：行程等待進入臨界區的時間有范圍，不會是無限大，
3.3解決臨界區問題方法
①搶占式內核（preemptive kerbel）：允許處于內核模式的行程被搶占，處于內核模式的行程會一直運行，直到退出內核模式，阻塞或自愿放棄CPU控制，
②非搶占式內核（nopreemptive kerbel）:不允許處于內核模式下的行程被搶占
3.4.1Peterson解決方案（軟體方法）
解釋：設定兩個行程共享資料項
int turn ;
boolean flag[2];
j=1-i;
兩個行程P0和P1
程序
| 我的理解 | 官方解釋 |
|---|---|
| ①初始化設定flag[i]也就是flag[0]為true，因為turn等于j等于1-i;所以turn==1；代表flag[0]想要申請進入臨界區②此時，如果flag[j]也就是flag[1]等于true的話，并且turn等于1，那么陳述句就會一直在while回圈中空轉，注意，while回圈與君判斷條件后面是分號③直到P1退出臨界區并執行flag[j]=false后，P0才能進入臨界區執行 | 考慮行程P0，一旦它設定flag[0]=true，則P1不能進入臨界區，如果P1已經進入臨界區，那么flag[1]=true，P0被阻塞不能進入臨界區，另一方面，互相阻塞也避免了，假設P0在while里被阻塞了，表示flag[1]為true且turn=1，則此時P1可以執行 |
缺點：1，只適用于兩個執行緒 2，現代計算機體系結構不支持
3.4.2硬體同步（硬體方法）
方法一 —>中斷屏蔽方法
進入臨界區前執行"關中斷"指令
離開臨界區后執行"開中斷"指令
優點：簡單有效
缺點：不適用于多處理器（耗時）
方法二–>測驗并設定指令
前提：test_and_set()時原子的（執行不可中斷）
為每個臨界資源設定一個lock，初始為false
解釋：當一個臨界資源未被使用時，lock等于false，程式可以執行while下面的陳述句，當lock等于true時，test_and_set(&lock)函式回傳值為true，程式在while中空轉
3.4.3互斥鎖（mutex lock）（軟體方法）
互斥鎖：一個行程進入臨界區時得到鎖，在它退出臨界區時釋放鎖，函式acquire()獲得鎖，函式release()釋放鎖，每個互斥鎖都有一個布爾變數available,它表示鎖是否可用
互斥鎖實作要求qcquire（）和release（）的呼叫必須是原子地執行
行程互斥訪問示例
缺點：忙等待（busy wating），一個行程在臨界區中其他任何行程都必須等待
3.6信號量（semaphore）
信號量S是一個整型變數，它的初始化通過兩個標準原子操作wait()和signal(),wait()也叫P操作，signal()也叫V操作
wait（）函式體定義
wati(S)
{
while(S<=0); //忙等待
S--；
}
signal()函式體定義
signal()
{
S++;
}
缺點：不滿足讓權等待（當行程不能進入自己的臨界區時，應立即釋放處理機，以免行程陷入“忙等”，）
3.4.5信號量的使用和實作
信號量使用改進(重新定義)
typedef struct
{
int value;
struct process *list;
}semaphore
//每一個信號量都有一個整數value和一個行程鏈表list，當一個行程必須等待信號量時，就被添加帶行程鏈表，操作signal()從等待行程鏈表上取走行程，并加以喚醒
wait(semaphore *S)
{
S->value--;
if(S->value<0)
{
add this process to S->list;
block();
}
}
signal(semaphore *S)
{
S->value++;
if(S->value<=0)
{
remove a process P from S->list;
wakeup(P);
}
}
3.4.6死鎖與饑餓
死鎖：兩個或多個行程無限等待一個事件，而該事件這些等待行程之一來完成，這些行程稱為死鎖
3.5經典同步問題
3.5.1生產者-消費者問題
3.5.2讀者-作者問題
3.5.3哲學家就餐問題
3.6管程
管程定義：指關于貢獻資源的資料及其在其上操作的一組程序或共享資料結構及其規定的所有操作（沒聽懂）
管程能夠保證在任何時候最多只有一個執行緒（行程）操作管程中的代碼
標題
4行程調度
4.1 CPU-I/O執行周期
行程執行：包括周期進行CPU執行和I/O等待，行程在這兩個狀態下不斷交替，行程執行從CPU執行開始，之后I/O執行，；接著另一個CPU執行，接著另一個I/O執行；
4.1.2 CPU調度程式
當CPU空閑時，作業系統就從佇列中選擇一個行程來執行并尾氣分配CPU，
4.1.3搶占調度
需要CPU調度的四種情況
1，一個行程從運行態到等待狀態
2，一個行程從運行狀態到就緒狀態
3，一個行程從等待狀態到就緒狀態
4，一個行程終止時
如果調度只發生在第1或4種情況，則調度是非搶占的，否則是搶占的，在非搶占調度下，一個行程在分配到CPU時，會一直運行直到終止或切換狀態
4.1.4調度程式
調度程式功能：
1，切換背景關系
2，切換到用戶模式
3，跳轉到用戶程式的合適位置，以便重新啟動程式
調度程式應盡可能快，調度程式停止一個行程而啟動另一個行程所需要的時間稱為調度延遲（dispatch latency）
4.2調度準則
| 名稱 | 解釋 |
|---|---|
| CPU 使用率 | 應使 CPU 盡可能地忙碌，從概念上講，CPU 使用率從 0% 到 100%，對于一個實際系統，它的范圍應從 40%（輕負荷系統）到 90%（重負荷系統）， |
| 吞吐量 | 如果 CPU 忙于執行行程，那么作業就在完成，一種測量作業的方法稱為吞吐量，它是在一個時間單元內行程完成的數量，對于長行程，吞吐量可能為每小時一個行程；對于短行程，吞吐量可能為每秒十個行程， |
| 周轉時間 | 從一個特定行程的角度來看，一個重要準則是運行這個行程需要多長時間，從行程提交到行程完成的時間段稱為周轉時間，周轉時間為所有時間段之和，包括等待進入記憶體、在就緒佇列中等待、在 CPU 上執行和 I/O 執行， |
| 等待時間 | CPU 調度演算法并不影響行程運行和執行 I/O 的時間，它只影響行程在就緒佇列中因等待所需的時間，等待時間為在就緒佇列中等待所花時間之和， |
| 回應時間 | 對于互動系統，周轉時間不是最佳準則，通常，行程可以相當早地產生輸出，并且繼續計算新的結果同時輸出以前的結果給用戶，因此，另一時間是從提交請求到產生第一回應的時間，這種時間稱為回應時間，是開始回應所需的時間，而非輸出回應所需的時間，周轉時間通常受輸出設備速度的限制， |
4.3調度演算法
4.3.1先到先服務調度
先到先服務調度（first-Come First_Served,FCFS）
先請求CPU的行程首先分配到CPU，當一個行程進入就緒佇列時，他的PCB會被鏈接到佇列尾部，當CPU空閑時，他會分配給佇列頭部的行程，并且這個運行行程從佇列中移除
FSFS策略優點：簡單，容易理解
FSFS策略缺點：平均等待時間長
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/186578.html
標籤：其他
上一篇：網路布線與數制轉換