【OS】進程與線程

進程

進程實體

代碼段

PCB

進程標識符

外部標識符：
為方便用戶對進程的訪問，為每個進程設置一個外部標識符，通常由字母和數字組成
內部標識符：
為方便系統對進程的使用，在OS中又為進程設置了內部標識符，賦予每個進程唯一一個數字標識符，通常是一個進程序號

處理機狀態

通用寄存器
PC
PSW
堆棧指針寄存器SP：指向用戶自己堆棧的指針和指向內核棧的指針

進程調度信息

進程狀態：指明進程當前的狀態（阻塞、就緒、運行），作為進程調度、對換的依據
進程優先級：描述進程使用處理機的優先級別（用一個整數表示），優先級高的優先獲得處理機
進程調度所需的其他信息：部分進程調度算法需要知道進程已等待CPU時間總和、進程已執行時間總和等
事件：進程由執行轉態轉換為阻塞狀態所等待發生的事件（阻塞的原因）

進程控制信息

程序和數據的地址
即程序和數據的內存或外存起始地址，便于該進程執行時能從PCB中快速找到程序和數據
頁表的起始地址（最后放在寄存器一定是物理地址）

進程同步和通信機制
比如消息隊列指針、信號量等，它們可能會全部或部分放在PCB中

資源清單
列出了該進程在運行期間所需的全部資源（除CPU外）

鏈接指針
給出本進程所在隊列中的下一個進程的PCB起始地址

進程映像

（建立在虛擬存儲的基礎上）

操作系統內核區

將操作系統內核映射到這個區域
區域內容對進程不可見

共享庫的存儲映射區

將共享庫（如動態鏈接庫DLL）映射到進程的虛擬地址空間部分，使多個進程能共享同一個物理內存副本的庫，節省了內存資源
映射區域允許進程執行庫中的代碼，并訪問庫中的數據，就像這些代碼和數據時進程自己的一部分一樣

代碼段

程序的二進制代碼
代碼段是只讀的，可被多個進程共享

數據段

包括全局變量和靜態變量

PCB

放在內核區

堆

用來存放動態分配的變量，通過調用malloc函數動態的向高地址分配空間

棧

用來實現函數調用，從用戶空間的最大地址向低地址方向增長

為每個進程創建巨大的、私有的虛擬內存的假象，這種地址空間的抽象讓每個程序好像擁有自己的內存，而實際上操作系統秘密地讓多個地址空間復用物理內存

進程狀態

就緒態：資源充分，只差CPU
阻塞態：主動阻塞，等待輸入，將CPU讓出
執行態

進程的控制

創建

過程：
分配進程標識符，申請PCB，為進程分配資源，為程序和數據分配必要的內存，初始化PCB，若就緒隊列未滿則插入
父進程創建子進程，子進程可以繼承父進程所擁有的資源（打開的文件，分配的緩沖區）

執行：
父進程與子進程并發執行
父進程等待，直到其某個或全部子進程執行完畢

內存映像：
子進程是父進程的復制品（子進程與父進程具有相同的程序、數據、堆棧）
子進程加載另一個新程序

終止

當子進程被撤銷時，應將從父進程那里獲得的資源歸還父進程
在撤銷父進程時，也必須同時撤銷所有的子進程

阻塞

進程調用阻塞原語block將自己阻塞，是一種主動行為
OS介入，停止執行該進程，將PCB中改為阻塞態，將PCB中改為阻塞態，將PCB插入阻塞隊列，執行調度程序重新調度CPU

喚醒

將阻塞進程所期待的事件發生時，使用喚醒原語wakeup將等待該事件的進程喚醒
OS將被阻塞的進程從等待該事件的阻塞隊列中移出，將其PCB中的現行狀態改為就緒，將該PCB插入就緒隊列

進程通信

共享存儲

通信進程之間有一塊用于通信的共享空間

消息傳遞

以格式化的消息為單位，將通信的數據封裝在消息中

管道通信

“管道”指用于連接一個讀進程和一個寫進程以實現它們之間通信的一個共享文件，也叫pipe文件
管道不可以同時讀寫
管道同一時刻只能有一個方向的傳輸
管道滿時寫進程被阻塞，管道空時讀進程被阻塞

線程

基本概念

每個線程類似于獨立的進程，只有一點區別：它們共享進程的地址空間，從而能夠訪問相同的數據
線程只是作為獨立調度和分派的單位，但是它們沒有獨立的地址空間，也沒有掌握資源，完全依附于進程
每個線程都有自己獨立的棧和棧指針，并且線程之間沒有做保護措施，每個線程的堆棧可以被其他線程讀寫甚至清除，由一個線程打開的文件也可以被其他線程讀寫

實現方式

ULT

把整個線程實現部分放在用戶空間中，內核看到的就是一個單線程進程

線程切換在用戶空間實現，無需模式切換
每個進程可以選擇自己專用的調度算法，對自己內部的線程進行調度和管理
ULT的實現與OS無關，因為ULT管理的代碼會顯式地出現在用戶程序中，因此ULT甚至可以在不支持線程機制的OS平臺上實現

內核只識別到一個進程，因此調度的對象是整個用戶進程，每次只能給整個進程分配CPU，進程中只有一個線程能執行，無法發揮多處理器系統優勢
進程中的某個線程發起IO系統調用，會導致進程中的所有線程全部被阻塞

KST

內核可識別到內核級線程，因此調度的對象是內核級線程，在多處理機系統中，每次可以給不同的內核級線程分配CPU，提高并行度
如果用戶進程中的一個線程被阻塞，內核可以調度該進程內的其他線程上處理機，或者調度其他進程的線程

每次線程切換都需要CPU改變狀態，開銷較大
TCB存放在內核空間中，內存占用較大

CPU調度

進程調度

原理

進程調度是CPU在內核態下完成的
進程調度基于中斷機制

方式

非搶占調度方式
正在執行的進程執行完畢或無法繼續執行
正在執行的進程因提出IO請求而暫停執行
進程通信或同步過程中執行了某種原語操作（block原語）

搶占調度方式
優先級高可搶占處理機
短進程優先原則
時間片原則，各進程按照時間片運行，正在執行的進程的一個時間片用完后，停止該進程執行并重新放回就緒隊列的末尾，然后將處理機分配給就緒隊列中的下一個進程

調度時機

主動放棄

運行完畢，正常終止
運行過程中發生異常
發生事件，請求阻塞

被動放棄

進程時間片用完
有更高優先級進程進入就緒隊列（搶占）
有更加緊急的事情需要處理

不可進程切換的情況

處理中斷時
進程處于內核臨界區時
執行原子操作時

調度目標

調度算法

先來先服務FCFS

按照作業/進程到達的先后次序進行調度
只能是非搶占式
對長作業有利，對短作業不利
有利于CPU繁忙型作業/進程，不利于IO繁忙型作業/進程

短作業優先SJF

(未說明就是非搶占式)

作業/進程越短，優先級越高，越先被調度
如果是搶占式SJF，作業/進程的剩余時間越短，優先級越高，越先被調度
平均等待時間和平均周轉時間最優
對短作業有利，對長作業不利，甚至導致長作業饑餓
默認在估計運行時間相等時按照先后順序服務

高響應比優先

響應比=（等待時間+要求服務時間）/要求服務時間
每次調度時選擇響應比最高的作業投入運行
克服了長作業饑餓問題

優先級調度

按優先級調度

時間片輪轉

所有就緒進程排成就緒隊列，OS每隔一段時間就產生一次時鐘中斷，調度進程，將CPU分配給就緒隊列首進程，令其執行一個時間片

多級隊列調度

設置多個隊列，將不同類型的進程分配到不同的就緒隊列，每個隊列實行不同的調度算法

多級反饋隊列調度

結合了時間片調度和優先級調度算法，設置多個就緒隊列，為每個隊列賦予不同優先級
賦予了各個隊列的進程運行時間片不同，優先級越高的隊列里進程的時間片越小
每個隊列采用FCFS算法
僅當1~i-1級隊列為空，才調度i級，若CPU正在執行第i級隊列中的某個進程時，有新進程進入優先級更高的隊列，立即將正在執行的進程放回本級隊列隊尾，將CPU分配給新到的進程