第一章 作業系統概述

1，作業系統定義：作業系統(Operating System)使計算機系統中的一個系統軟體，是一些程式模塊的集合，它能以盡量有效，合理的方式組織和管理計算機的軟硬體資源，合理組織計算機的作業流程，控制程式的執行并向用戶提供各種服務功能，使得計算機系統高效地運行，（沒有廣泛接受的標準定義）
2，作業系統中一些名詞解釋

作業系統中存在中斷，共享，并發，競爭等情況
1,中斷處理程序

第二章：行程

行程（process）定義：行程是一個具有一定獨立功能的程式或程式段在一組資料集合上的一次動態執行
行程=程式+執行
行程包括程式，資料和行程控制塊
2.1行程狀態

一次只能有一個行程在處理器上運行（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關于臨界區問題名詞解釋

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
程序

缺點：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調度準則

4.3調度演算法
4.3.1先到先服務調度
先到先服務調度（first-Come First_Served,FCFS）
先請求CPU的行程首先分配到CPU，當一個行程進入就緒佇列時，他的PCB會被鏈接到佇列尾部，當CPU空閑時，他會分配給佇列頭部的行程，并且這個運行行程從佇列中移除
FSFS策略優點：簡單，容易理解
FSFS策略缺點：平均等待時間長