Updated December 25, 2018

操作系統(tǒng)引論

多道程序設(shè)計(jì)的基本概念

在多道批處理系統(tǒng)中, 用戶所提交的作業(yè)先存放在外存上, 并且排成一個(gè)隊(duì)列, 稱為后備隊(duì)列, 由作業(yè)調(diào)度程序按一定的算法, 從后備隊(duì)列中選擇若干個(gè)作業(yè)調(diào)入內(nèi)存, 使它們共享CPU和系統(tǒng)中的各種資源. 由于同時(shí)在內(nèi)存中裝有若干道程序, 可以利用程序在I/O操作時(shí)的CPU空擋時(shí)間, 使多道程序交替地運(yùn)行, 這樣便可以保持CPU處于忙碌狀態(tài).

多道批處理系統(tǒng)的優(yōu)缺點(diǎn)

1. 資源利用率高: CPU可以保持忙碌狀態(tài), 可提高內(nèi)存的利用率, 可提高I/O設(shè)備的利用率
2. 系統(tǒng)吞吐量大: CPU和其它資源保持忙碌狀態(tài), 作業(yè)僅當(dāng)完成或運(yùn)行不下去時(shí)才進(jìn)行切換, 系統(tǒng)開銷小
3. 平均周轉(zhuǎn)時(shí)間長(zhǎng): 由于作業(yè)要排隊(duì)依次進(jìn)行處理, 因而作業(yè)的周轉(zhuǎn)時(shí)間較長(zhǎng)
4. 無交互能力: 用戶一旦把作業(yè)提交給系統(tǒng), 直至作業(yè)完成, 用戶都不能與自己的作業(yè)進(jìn)行交互

操作系統(tǒng)的基本特性

1. 并發(fā): 指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生. 這些事件宏觀上是同時(shí)發(fā)生的, 但是微觀上是交替發(fā)生的. 一個(gè)單核處理機(jī)同一時(shí)刻只能執(zhí)行一個(gè)程序, 因此操作系統(tǒng)會(huì)負(fù)責(zé)協(xié)調(diào)多個(gè)程序交替執(zhí)行
2. 共享: 是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用
   • 互斥共享方式: 系統(tǒng)中的某些資源, 雖然可以提供給多個(gè)進(jìn)程使用, 但一個(gè)時(shí)間段內(nèi)只允許一個(gè)進(jìn)程訪問該資源
   • 同時(shí)共享方式: 系統(tǒng)中的某些資源, 允許同一個(gè)時(shí)間段內(nèi)由多個(gè)進(jìn)程對(duì)它們進(jìn)行訪問
3. 虛擬: 通過某種技術(shù)將一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物
   • 時(shí)分復(fù)用技術(shù)
   • 空分復(fù)用技術(shù)
4. 異步: 在多道程序環(huán)境下, 允許多個(gè)程序并發(fā)執(zhí)行, 但由于資源有限, 進(jìn)程的執(zhí)行不是一貫到底的, 而是走走停停, 以不可預(yù)知的速度向前推進(jìn), 這就是進(jìn)程的異步性

系統(tǒng)調(diào)用

應(yīng)用程序通過系統(tǒng)調(diào)用請(qǐng)求操作系統(tǒng)的服務(wù).
系統(tǒng)調(diào)用是操作系統(tǒng)提供給應(yīng)用程序(開發(fā)人員)使用的接口, 可以理解為一種可供應(yīng)用程序調(diào)用的特殊函數(shù)

系統(tǒng)調(diào)用的過程

1. 傳遞系統(tǒng)調(diào)用參數(shù)
2. 執(zhí)行陷入指令(用戶態(tài))
3. 執(zhí)行系統(tǒng)調(diào)用相應(yīng)服務(wù)程序(核心態(tài))
4. 返回用戶程序
   注意: 陷入指令是在用戶態(tài)執(zhí)行的, 執(zhí)行陷入指令之后立即引發(fā)一個(gè)內(nèi)中斷, 從而CPU進(jìn)入核心態(tài). 發(fā)出系統(tǒng)調(diào)用請(qǐng)求是在用戶態(tài), 而對(duì)系統(tǒng)調(diào)用的相應(yīng)處理在核心態(tài)下進(jìn)行

中斷和異常

發(fā)生中斷就意味著需要操作系統(tǒng)介入, 開展管理工作. 當(dāng)中斷發(fā)生后, CPU立即進(jìn)入內(nèi)核態(tài), 當(dāng)前運(yùn)行的進(jìn)程暫停運(yùn)行, 并由操作系統(tǒng)內(nèi)核對(duì)中斷進(jìn)行處理
中斷的分類

• 內(nèi)中斷(異常): 信號(hào)的來源是CPU內(nèi)部, 與當(dāng)前執(zhí)行的指令有關(guān)
  • 自愿中斷--指令中斷
  • 強(qiáng)迫中斷(如硬件故障(缺頁(yè)), 整數(shù)除以0)
• 外中斷: 信號(hào)來源是CPU外部, 與當(dāng)前執(zhí)行的指令無關(guān)
  • 外設(shè)請(qǐng)求(I/O操作完成發(fā)出的中斷信號(hào))
  • 人工干預(yù)

進(jìn)程

進(jìn)程實(shí)體: 由程序段, 數(shù)據(jù)段, PCB三部分構(gòu)成
進(jìn)程: 進(jìn)程實(shí)體的運(yùn)行過程, 是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位
創(chuàng)建撤銷進(jìn)程, 實(shí)質(zhì)上是創(chuàng)建撤銷進(jìn)程實(shí)體中的PCB

PCB(記錄型數(shù)據(jù)結(jié)構(gòu))

作為獨(dú)立運(yùn)行基本單位的標(biāo)志. 能實(shí)現(xiàn)間斷性運(yùn)行方式, 系統(tǒng)可將CPU現(xiàn)場(chǎng)信息保存在被中斷進(jìn)程的PCB中, 供該進(jìn)程再次被調(diào)度執(zhí)行時(shí)恢復(fù)CPU現(xiàn)場(chǎng)時(shí)使用

• 進(jìn)程描述信息: 進(jìn)程標(biāo)識(shí)符PID和用戶標(biāo)識(shí)符UID
• 進(jìn)程控制和管理信息: 進(jìn)程的當(dāng)前狀態(tài), 進(jìn)程優(yōu)先級(jí)
• 處理機(jī)狀態(tài): 處理機(jī)的各種寄存器的內(nèi)容
• 資源清單: 鍵盤, 鼠標(biāo)等

PCB的組織方式

在一個(gè)系統(tǒng)中, 通常有數(shù)十?dāng)?shù)百乃至更多的PCB, 為了能對(duì)它們加以有效的管理, 應(yīng)該用適當(dāng)?shù)姆绞桨堰@些PCB組織起來

1. 線性方式: 將系統(tǒng)中所有的PCB都組織在一張線性表中, 將該表的首址存放在內(nèi)存的一個(gè)專用區(qū)域中
2. 鏈接方式: 把具有相同狀態(tài)進(jìn)程的PCB分別通過PCB中的鏈接字鏈接成一個(gè)隊(duì)列. 可以形成就緒隊(duì)列, 若干個(gè)阻塞隊(duì)列和空白隊(duì)列
3. 索引方式: 系統(tǒng)根據(jù)所有進(jìn)程狀態(tài)的不同, 建立幾張索引表, 如就緒索引表, 阻塞索引表, 并把各索引表在內(nèi)存的首地址記錄在內(nèi)存的專用單元中

進(jìn)程的狀態(tài)

1. 就緒態(tài): 已經(jīng)具備運(yùn)行條件, 但是由于沒有空閑CPU, 暫時(shí)不能運(yùn)行
2. 執(zhí)行態(tài): 進(jìn)程已經(jīng)占有CPU, 并在CPU上執(zhí)行
3. 阻塞態(tài): 指正在執(zhí)行的進(jìn)程由于發(fā)生某事件暫時(shí)無法執(zhí)行時(shí)的狀態(tài)
4. 創(chuàng)建態(tài): 由進(jìn)程申請(qǐng)一個(gè)空白PCB, 并向PCB中填寫用于控制進(jìn)程的信息
5. 終止態(tài): 將PCB清零, 并將PCB返還系統(tǒng)

進(jìn)程同步

進(jìn)程同步是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào), 使并發(fā)執(zhí)行的諸進(jìn)程之間能按照一定的規(guī)則共享系統(tǒng)資源.
為了實(shí)現(xiàn)對(duì)臨界資源的互斥訪問, 需遵循以下原則:

1. 空閑讓進(jìn): 當(dāng)無進(jìn)程處于臨界區(qū)時(shí), 應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)
2. 忙則等待: 當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí), 其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待
3. 有限等待: 對(duì)請(qǐng)求訪問臨界資源的進(jìn)程, 應(yīng)保證在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)(保證不會(huì)饑餓)
4. 讓權(quán)等待: 當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí), 應(yīng)立即釋放處理機(jī), 以免進(jìn)程陷入忙等狀態(tài)

硬件方法實(shí)現(xiàn)進(jìn)程互斥:

1. 關(guān)中斷
2. Test and Set指令
3. Swap指令

信號(hào)量機(jī)制
可以用一個(gè)信號(hào)量表示系統(tǒng)中某種資源的數(shù)量, 用戶進(jìn)程可以通過使用操作系統(tǒng)提供的一對(duì)原語(yǔ)來對(duì)信號(hào)量進(jìn)行操作.

• 整型信號(hào)量

int s = 1;
void wait(int s){
      while(s <= 0);
      s = s-1;
}
void signal(int s){
      s = s+1;
}

• 記錄型信號(hào)量

//記錄型信號(hào)量的定義
typedef struct{
       int value; // 剩余資源數(shù)
       struct process *L; // 等待隊(duì)列
}semaphore;

void wait(semaphore *s){
    s->value--;
    if(s->value < 0)block(s->list);
}
void signal(semaphore *s){
    s->value++;
    if(s->value <= 0)wakeup(s->list);
}

• 生產(chǎn)者消費(fèi)者問題

int in = 0, out = 0; item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void producer(){
    do{
        producer an item nextp;
        wait(empty); wait(mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        signal(mutex); signal(full);
    }while(True);
}
void consumer(){
    do{
        wait(full); wait(mutex);
        nextc = buffer[out];
        out = (out + 1) % n;
        signal(mutex); signal(empty);
        consumer the item in nextc;
    }while(True);
}

• 哲學(xué)家進(jìn)餐問題

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1; //互斥地取筷子
Pi(){ //i號(hào)哲學(xué)家的進(jìn)程
  while(1){
      P(mutex); P(chopstick[i]); //拿左
      P(chopstick[(i+1)%5]); //拿右
      V(mutex);
      吃飯
      V(chopstick[i]);
      V(chopstick[(i+1)%5]);
      思考
   }
}

進(jìn)程通信

指進(jìn)程之間的信息交換
高級(jí)通信機(jī)制:

1. 共享存儲(chǔ)器系統(tǒng): 相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)
2. 管道通信系統(tǒng): 管道, 是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)它們之間通信的一個(gè)共享文件, 又叫pipe文件. 寫進(jìn)程以字符流形式將大量的數(shù)據(jù)送入管道, 讀進(jìn)程則從管道中接收數(shù)據(jù).
3. 消息傳遞系統(tǒng): 不必借助任何共享存儲(chǔ)區(qū)或數(shù)據(jù)結(jié)構(gòu), 而是以格式化的消息為單位, 將通信的數(shù)據(jù)封裝在消息中, 并利用操作系統(tǒng)提供的一組通信命令原語(yǔ), 在進(jìn)程間進(jìn)行消息傳遞
4. 客戶機(jī)-服務(wù)器系統(tǒng)

線程

引入進(jìn)程的目的是為了使多個(gè)程序能并發(fā)執(zhí)行, 以提高資源利用率和系統(tǒng)吞吐量.
引入線程的目的是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷.
線程是一個(gè)基本的CPU執(zhí)行單元, 也是程序執(zhí)行流的最小單位
線程是調(diào)度的基本單位
由于進(jìn)程是一個(gè)資源的擁有者, 因而在創(chuàng)建, 撤銷和切換中, 系統(tǒng)必須為之付出較大的時(shí)空開銷. 線程間并發(fā), 如果是同一進(jìn)程內(nèi)的線程切換, 則不需要切換進(jìn)程環(huán)境, 系統(tǒng)開銷小

處理機(jī)調(diào)度與死鎖

調(diào)度的實(shí)質(zhì)是一種資源分配, 處理機(jī)調(diào)度是對(duì)處理機(jī)資源進(jìn)行分配.
饑餓: 某進(jìn)程/作業(yè)長(zhǎng)期得不到服務(wù)

• 作業(yè)調(diào)度(高級(jí)調(diào)度):
  根據(jù)某種算法, 從外存上處于后備隊(duì)列的作業(yè)中挑選一個(gè)或多個(gè)作業(yè), 給它們分配內(nèi)存等資源, 建立相應(yīng)的進(jìn)程(建立PCB).
• 內(nèi)存調(diào)度(中級(jí)調(diào)度):
  引入中級(jí)調(diào)度的目的是提高內(nèi)存利用率和系統(tǒng)吞吐量
  中級(jí)內(nèi)存實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能
  把那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存等待, 此時(shí)進(jìn)程的狀態(tài)稱為掛起狀態(tài), 當(dāng)它們已具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí), 由中級(jí)調(diào)度決定重新調(diào)入內(nèi)存.
• 進(jìn)程調(diào)度(低級(jí)調(diào)度):
  按照某種算法, 從就緒隊(duì)列中選擇一個(gè)進(jìn)程為其分配處理機(jī)
  進(jìn)程切換是指一個(gè)進(jìn)程讓出處理機(jī), 另一個(gè)進(jìn)程占有處理機(jī)的過程, 對(duì)原來運(yùn)行的進(jìn)程保存各種數(shù)據(jù), 對(duì)新的進(jìn)程恢復(fù)各種數(shù)據(jù)

處理機(jī)的利用率
CPU的利用率=CPU有效工作時(shí)間/(CPU有效工作時(shí)間+CPU空閑等待時(shí)間)

調(diào)度算法

• 先來先服務(wù)(first-come first-served)調(diào)度算法
  該算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度, 系統(tǒng)按照作業(yè)到達(dá)的先后次序來進(jìn)行調(diào)度, 優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)
• 短作業(yè)優(yōu)先(short job first)調(diào)度算法
  該算法以作業(yè)/進(jìn)程的長(zhǎng)短來計(jì)算優(yōu)先級(jí), 作業(yè)/進(jìn)程越短, 優(yōu)先級(jí)越高.
  對(duì)短作業(yè)有利, 長(zhǎng)作業(yè)不利, 還可能造成饑餓.
• 優(yōu)先級(jí)調(diào)度算法(priority-scheduling algorithm)
  在優(yōu)先級(jí)調(diào)度算法中, 基于作業(yè)的緊迫程度, 由外部賦予作業(yè)相應(yīng)的優(yōu)先級(jí), 調(diào)度算法根據(jù)該優(yōu)先級(jí)進(jìn)行調(diào)度.
• 高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next)
  為每個(gè)作業(yè)引入一個(gè)動(dòng)態(tài)優(yōu)先級(jí), 即令優(yōu)先級(jí)隨等待時(shí)間延長(zhǎng)而增加, 避免了長(zhǎng)作業(yè)饑餓的問題. 該優(yōu)先級(jí)的變化規(guī)律可描述為: 優(yōu)先權(quán)=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間
• 基于時(shí)間片的輪轉(zhuǎn)(round robin)調(diào)度算法
  系統(tǒng)根據(jù)FCFS策略, 將所有的就緒進(jìn)程排成一個(gè)就緒隊(duì)列, 并設(shè)置每隔一定時(shí)間間隔(如30ms)產(chǎn)生一次中斷, 激活系統(tǒng)中的進(jìn)程調(diào)度程序, 如果進(jìn)程尚未運(yùn)行完畢, 調(diào)度程序把它送往就緒隊(duì)列的末尾, 將CPU分配給隊(duì)首進(jìn)程.
• 多隊(duì)列調(diào)度算法
  該算法將系統(tǒng)中的進(jìn)程就緒隊(duì)列從一個(gè)拆分為若干個(gè), 將不同類型或性質(zhì)的進(jìn)程固定分配在不同的就緒隊(duì)列, 不同的就緒隊(duì)列采用不同的調(diào)度算法
• 多級(jí)反饋隊(duì)列(multileved feedback queue)調(diào)度算法

1. 在系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列, 并為每個(gè)隊(duì)列賦予不同的優(yōu)先級(jí). 第一隊(duì)列優(yōu)先級(jí)最高, 第二個(gè)次之. 該算法為不同隊(duì)列中的進(jìn)程所賦予的執(zhí)行時(shí)間片的大小也不相同, 在優(yōu)先級(jí)越高的隊(duì)列中, 其時(shí)間片越小.
2. 新進(jìn)程進(jìn)入內(nèi)存后, 先將其放入第一隊(duì)列的末尾, 每個(gè)隊(duì)列都采用FCFS算法, 當(dāng)輪到該進(jìn)程執(zhí)行時(shí), 若用完時(shí)間片進(jìn)程還未結(jié)束, 則將該進(jìn)程放入下一級(jí)隊(duì)列隊(duì)尾
3. 只有第k級(jí)隊(duì)列為空時(shí), 才會(huì)為第k+1級(jí)隊(duì)頭的進(jìn)程分配時(shí)間片

死鎖

在并發(fā)環(huán)境下, 各進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種互相等待對(duì)方手里的資源, 導(dǎo)致各進(jìn)程都阻塞, 都無法向前推進(jìn)的現(xiàn)象

• 產(chǎn)生死鎖的必要條件
  互斥條件, 請(qǐng)求和保持條件, 不可搶占條件, 循環(huán)等待條件
• 處理策略
  1. 預(yù)防死鎖: 破壞產(chǎn)生死鎖的四個(gè)必要條件
  2. 避免死鎖: 銀行家算法
  3. 死鎖的檢測(cè)與解除