第一章 作業系統概述

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策略缺點：平均等待時間長