1.程序的并發(fā)
1.1 順序執(zhí)行和并發(fā)執(zhí)行
程序有兩種執(zhí)行方式：① 順序執(zhí)行 ② 并發(fā)執(zhí)行
順序執(zhí)行：一個獨立功能的程序獨占cpu直到得到最終結果的過程凿宾。
并發(fā)執(zhí)行：一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中妹笆，其執(zhí)行時間在客觀上互相重疊羔飞，即一個程序段的執(zhí)行尚未結束拓瞪，另一個程序段的執(zhí)行已經開始的這種執(zhí)行方式溶锭。
（1）單道程序順序執(zhí)行的特點
① 順序性：嚴格程序結構規(guī)定的次序執(zhí)行优妙。
② 封閉性：占據了全部資源乘综，最終結果由初始條件決定，不受外界影響套硼。
③ 結果確定性：最終結果由給定的初始條件決定卡辰，不受外界因素的影響。
（2）多道程序并發(fā)執(zhí)行特點
① 結果不確定性：執(zhí)行結果與其執(zhí)行的相對速度以及并發(fā)執(zhí)行的多道程序之間的相互關系有關，導致并發(fā)程序的執(zhí)行結果是不確定的九妈。
②?資源共享性：硬件和軟件資源共享反砌，即執(zhí)行期間是相互制約的。
1.2 程序并發(fā)
（1）基本概念
一組邏輯上相互獨立的程序或者程序段在執(zhí)行時間上是互相重疊的萌朱。
① 執(zhí)行時間相互重疊的意思是一個程序或者說程序段還沒執(zhí)行結束宴树，另一個程序或者程序段就開始了。
② 為了提高計算機資源利用率而設計的嚷兔。
（2）優(yōu)缺點
優(yōu)點：提高資源利用率
缺點：① 資源共享和競爭改變程序的執(zhí)行速度森渐，同時也會失去原有的時序關系做入。
? ? ? ? ? ?② 資源共享和競爭導致失去封閉性和確定性冒晰，例如程序A寫到存儲器中的數據可能被? ? ? ? ? ? ? ? ?另程序B修改，導致A被B影響竟块，A的結果是不確定的壶运。
1.3 引入進程的概念
（1）出現的問題
如果隨意地執(zhí)行并發(fā)，不做任何約束浪秘，將會產生大量的錯誤結果蒋情。不同的執(zhí)行順序，得到的結果也是不同的耸携，即不再具有封閉性和結果的確定性棵癣。
這是為什么呢？共享公共變量引起的夺衍。
（2）如何解決問題
解決公共變量的共享問題狈谊，即滿足封閉性和確定性。
假定程序 A 和程序 B 沟沙，保證滿足一下條件：
①?程序 A?的讀變量集與程序 B?的寫變量集河劝，不能存在交集。
②程序 A?的寫變量集與程序 B?的讀變量集矛紫，也不能存在交集赎瞎。
③ 程序 A?和?程序 B?的寫變量集，更加不能存在交集颊咬。
（3）引入進程
由于程序未運行务甥，不知道并發(fā)的情況，資源是如何被爭奪的等等喳篇。因此敞临，“程序” 的靜態(tài)概念已經不能很確切的反映程序活動的特征，所以“進程” 的動態(tài)概念就出現了杭隙，用來描述系統(tǒng)以及用戶的程序活動哟绊。
2.進程的概述
2.1 什么是進程？
進程是程序的一次執(zhí)行活動，描述了程序動態(tài)執(zhí)行的過程票髓。
① 用戶角度： 進程是程序的一次動態(tài)執(zhí)行過程攀涵。
② 系統(tǒng)角度： A.進程是操作系統(tǒng)分配資源的基本單位；B.進程是一個具有獨立功能的程序對某個數據集在CPU處理器上的執(zhí)行過程洽沟。
2.2 進程和程序的區(qū)別
2.3 進程和作業(yè)的區(qū)別
進程和作業(yè)的關系如下：
2.4 進程的特點
① 動態(tài)性：進程是對應程序的執(zhí)行以故。
? ? A.進程產生：創(chuàng)建 --> 運行 --> 消亡
? ? B.進程在在內存三種基本狀態(tài)（就緒、運行裆操、阻塞）之間轉換怒详，可能被掛起到外存。
②?獨立性：各進程的地址空間相互獨立踪区，可采用進程間通信手段進行通信昆烁。
③?并發(fā)性：多個進程可以同時運行。
④?異步性：每個進程都以其相對獨立的不可預知的速度運行缎岗。
⑤?結構化：進程 = 代碼段 + 數據段 + PCB（進程控制塊）
3.進程的狀態(tài)
3.1 進程的5種基本狀態(tài)
（1）創(chuàng)建狀態(tài)
創(chuàng)建一個新的進程静尼。
① 批處理環(huán)境中，選擇一個新作業(yè)即將進去內存執(zhí)行传泊。
② 交互環(huán)境中鼠渺，新用戶登錄到系統(tǒng)。
③ 操作系統(tǒng)因提供一項服務而創(chuàng)建眷细。
（2）就緒狀態(tài)
一個進程已經具備了運行的條件拦盹，但是暫時還沒有CPU調度的狀態(tài)。
說明：當 CPU 調度的時候溪椎，線程可以馬上運行普舆。
（3）執(zhí)行狀態(tài)
進程占有了包括CPU在內的全部資源，并且在CPU上運行池磁。
（4）等待狀態(tài)
進程因為等待某件事情的發(fā)生而暫時不能運行的狀態(tài)奔害。
說明：即使CPU空閑，但是這個進程也不能運行地熄。
（5）終止狀態(tài)
一個進程結束
① 用戶結束某應用程序华临。
② 出現某些錯誤的時候，例如端考，I/O失敗雅潭，無效指令等。
③ 父進程可請求它的某個子進程終止却特。
④ 父進程終止扶供，系統(tǒng)可能會自動終止其子進程。
3.2 3種關鍵狀態(tài)的轉換及原因
注意：運行狀態(tài)和就緒狀態(tài)是可以相互轉換的裂明，而阻塞（等待）狀態(tài)不能直接轉換為運行狀態(tài)椿浓，就緒狀態(tài)也不能直接轉換為阻塞（等待）狀態(tài)。
① 就緒 --> 運行
CPU調用了一個已經準備好的進程（就緒狀態(tài)），然后就進入了運行狀態(tài)扳碍。
② 運行 --> 就緒
場景1：運行中的進程用完了時間片提岔。
場景2：優(yōu)先級更高的進程處于就緒狀態(tài)，所以當前運行進程被迫中斷笋敞。
擴展1：CPU 采用時間片輪轉調度算法碱蒙。基本思想是將CPU的處理時間劃分成一個個時間片，就緒隊列FIFO中依次出隊進程輪流運行一個時間片夯巷。當時間片結束時赛惩，就強迫運行狀態(tài)的進程讓出CPU，該進程入隊就緒隊列FIFO趁餐，等待下一次調度喷兼。同時，進程調度又去選擇就緒隊列中的一個進程澎怒，分配給它一個時間片褒搔，以投入運行阶牍。
擴展2：時間片大小的確認喷面。時間片設得太短會導致過多的進程切換，降低了CPU效率走孽，而設得太長又可能引起對短的交互請求的響應變差惧辈。
③ 運行 --> 阻塞
當一個進程等待某一件事情發(fā)生的場景，例如：請求系統(tǒng)服務磕瓷、沒有新的工作可以做盒齿、等待某一進程提供輸入（IPC）、初始化 I/O 且必須等待結果困食。
3種關鍵狀態(tài)之間的互相轉換的聯(lián)系边翁，例如：
（運行 --> 就緒）發(fā)生，則 （就緒 --> 運行）必然發(fā)生
當一個進程從運行轉到就緒狀態(tài)后硕盹，CPU 自然空閑了符匾，如果就緒狀態(tài)下仍然有別的進程，那么這個進程就會被 CPU 調用瘩例，同樣如果就緒狀態(tài)下沒有別的進程了啊胶，那么這個剛從運行轉到就緒狀態(tài)的進程就會馬上被 CPU 重新調用。
（運行 --> 阻塞）發(fā)生垛贤，則 （就緒 --> 運行）必然發(fā)生
當運行中的某個進程焰坪，進入阻塞狀態(tài)后，那么 CPU 同樣也空閑了下來聘惦，所以會調用已經在就緒狀態(tài)的進程某饰，即執(zhí)行（就緒 --> 運行）的操作
CPU 空閑且無就緒進程的時候，（阻塞 --> 運行）發(fā)生則會引起 （運行 --> 阻塞）
4.進程的控制塊（PCB）
4.1 基本介紹
① 進程控制塊PCB：記錄進程相關信息和管理進程，由 OS 維護的一個特定的數據結構黔漂，包含進程的描述信息碧浊、控制信息、資源信息以及現場保護區(qū)瘟仿。
② PCB 是進程動態(tài)特性的集中反映箱锐。系統(tǒng)通過 PCB 感知進程的存在，通過 PCB 中所包含的各項變量的變化劳较，掌握進程的狀態(tài)以達到控制進程活動的目的驹止。
③ PCB 結構的全部或部分常駐內存。
④ PCB 隨進程的創(chuàng)建而產生观蜗，隨進程的撤消而釋放臊恋。
⑤ 系統(tǒng)利用 PCB 來控制和管理進程，故?PCB 是系統(tǒng)感知進程存在的唯一標志墓捻。
⑥ 進程與 PCB 是一一對應的抖仅。
4.2 包含的內容
（1）描述信息
① 進程標識號，唯一砖第，通常是是一個整數撤卢。
②?進程名职烧，通常是可執(zhí)行文件名妻味。
③ 用戶名或者用戶標識號。
④ 進程組關系根欧。
（2）進程控制信息
①?進程狀態(tài)：初始狀態(tài)羽杰、就緒狀態(tài)渡紫、執(zhí)行狀態(tài)、等待狀態(tài)考赛、終止狀態(tài)惕澎。
②?進程優(yōu)先級：選取進程占有處理機的重要依據。
③?占有CPU時間
④?進程優(yōu)先級偏移
⑤?占據內存時間
⑥?程序開始地址
⑦?各種計時信息
⑧ 通信信息
（3）資源管理信息
①?占用內存大小及其管理用數據結構指針
②?共享程序段大小及起始地址
③?對換或覆蓋用的有關信息颜骤，如對換程序段長度唧喉，對換外存地址等
④?指向文件系統(tǒng)的指針及有關標識等
⑤?輸入輸出設備的設備號，傳送的數據長度复哆、緩沖區(qū)地址欣喧、緩沖區(qū)長度及所用設備的有關數據結構指針等
（4）CPU線程保護信息
① 存儲退出執(zhí)行時的進程現場數據（進程上下文）
② 寄存器值（通用、程序計數器 PC梯找、狀態(tài) PSW唆阿，地址包括棧指針）
說明：進程的上下文是對進程執(zhí)行活動全過程的靜態(tài)描述。
進程上下文的組成：進程的用戶地址空間內容锈锤、硬件寄存器內容及與該進程相關的核心數據結構組成（正文段驯鳖、數據集闲询、堆棧）。
5.進程的調度
5.1 先到先服務調度算法（FCFS）
非搶占式的調度算法浅辙，按照請求的順序進行調度扭弧。
從就緒隊列FIFO中出隊一個進程（最早入隊的進程），并為其分配資源记舆，使它立即執(zhí)行并一直執(zhí)行到完成或發(fā)生某事件而被阻塞放棄占用 CPU鸽捻。
應用場景：有利于長作業(yè)，但不利于短作業(yè)泽腮。因為短作業(yè)必須一直等待前面的長作業(yè)執(zhí)行完畢才能執(zhí)行御蒲，而長作業(yè)又需要執(zhí)行很長時間，導致短作業(yè)等待時間過長诊赊。
5.2 短作業(yè)優(yōu)先的調度算法（SLF）
非搶占式的調度算法厚满，按照估計運行時間最短的順序進行調度。
從就緒隊列中選出一個估計運行時間最短的進程為之分配資源碧磅，使它立即執(zhí)行并一直執(zhí)行到完成或發(fā)生某事件而被阻塞放棄占用 CPU碘箍。
應用場景：長作業(yè)可能一直無法執(zhí)行，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)鲸郊。因為如果一直有短作業(yè)到來丰榴，那么長作業(yè)永遠得不到調度。
5.3 時間片輪轉調度算法
搶占式的調度算法严望，進程根據請求順序依次執(zhí)行多艇，且每個進程只能在被允許的時間內運行。
時間片輪轉調度是一種最古老像吻，最簡單，最公平且使用最廣的算法复隆，又稱 RR(Round robin)調度拨匆。將所有就緒進程按 FCFS 的原則排成一個隊列，每次調度時挽拂，把 CPU 時間分配給隊首進程惭每，該進程可以執(zhí)行一個時間片。當時間片用完時亏栈，由計時器發(fā)出時鐘中斷台腥，調度程序便停止該進程的執(zhí)行，并將它送往就緒隊列的末尾绒北，同時繼續(xù)把 CPU 時間分配給隊首的進程黎侈。
應用場景：有大量用戶交互操作的系統(tǒng)，其目標是快速響應闷游。
時間片輪轉算法的性能取決于時間片的大芯骸：
因為進程切換都要保存進程的信息并且載入新進程的信息贴汪，如果時間片太小，會導致進程切換得太頻繁休吠，在進程切換上就會花過多時間扳埂。如果時間片過長，那么實時性就不能得到保證瘤礁。
例子1：假設 CPU 使用4ms的時間片阳懂。有一組進程在時間 0 到達，其 CPU 執(zhí)行的單位是 ms柜思，進程 P1 的執(zhí)行時間是24ms希太，進程 P2 的執(zhí)行時間是3ms，進程 P3 的執(zhí)行時間是3ms酝蜒。?
開始的時候 P1?會執(zhí)行4ms誊辉，因為 P1 還需要 20ms，所以在第一個時間片之后它會被搶占亡脑。接著 P2 獲取到 CPU 時間片 4ms堕澄，因為 P2 的執(zhí)行時間3ms少于4ms，所以在其時間片用完之前就會退出霉咨。接著 P3 獲取到 CPU 時間片 4ms蛙紫，同上P2。接著 P1?獲取到?CPU 時間片 4ms途戒，由于沒有就緒進程坑傅，P1 可以獲取時間片 4ms，反復該操作喷斋。因此唁毒，平均等待時間為?17/3 = 5.66ms。RR 調度結果如下：
計算該調度的平均等待時間：P1?等待 10-4 = 6ms星爪，P2?等待 4ms浆西，而 P3?等待 7ms 。
RR 算法的性能很大程度取決于時間片的大小顽腾。在一種極端情況下近零，如果時間片很大，那么 RR 算法與 FCFS 算法一樣抄肖。相反久信，如果時間片很小（如 1ms）漓摩，那么 RR 算法可以導致大量的上下文切換裙士。
例子2：假設有一個需要 10 個時間單元的進程。如果時間片為 12 個時間單元幌甘，那么進程在一個時間片不到就能完成潮售，而且沒有額外開銷痊项。如果時間片為 6 個時間單元，那么進程需要 2 個時間片酥诽，并且還有一個上下文切換鞍泉。如果時間片為 1 個時間單元，那么就會有 9 個上下文切換肮帐，相應地使進程執(zhí)行更慢咖驮。
5.4 優(yōu)先級調度算法
為每個流程分配優(yōu)先級，首先執(zhí)行具有最高優(yōu)先級的進程训枢，依此類推托修。相同優(yōu)先級的進程以 FCFS 方式執(zhí)行。
可以根據內存要求恒界、時間要求或任何其他資源要求來確定優(yōu)先級睦刃。為了防止低優(yōu)先級的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優(yōu)先級十酣。
5.5 多級反饋隊列調度算法
既能使高優(yōu)先級的作業(yè)得到響應又能使短作業(yè)迅速完成涩拙。目前被公認的一種較好的進程調度算法，UNIX 操作系統(tǒng)采取的便是這種調度算法耸采。
前面介紹的幾種進程調度的算法都有一定的局限性兴泥。例如，先到先服務算法不利于短作業(yè)虾宇、短作業(yè)優(yōu)先算法忽略了長進程?搓彻、當時間片大小不合適的時候時間片輪轉算法存在大量進程切換等。
多級反饋隊列算法是搶占式的調度算法嘱朽，可以解決需要執(zhí)行多次時間片進程的場景旭贬，采用多個隊列，每個隊列時間片大小都不一樣燥翅，例如1骑篙、2、4森书、8、...谎势。當進程在第一個隊列沒有執(zhí)行完凛膏，就會被移動到下一個隊列。每個隊列優(yōu)先權也不同脏榆，最上面的優(yōu)先級最高猖毫，最后一層的優(yōu)先級最低（采用時間片輪轉調度算法）。因此只有上一個隊列沒有進程在排隊须喂。多級反饋隊列算法是優(yōu)先級調度算法和時間片輪轉調度算法的結合吁断。
例子1：進程 A 需要執(zhí)行 100ms趁蕊，如果采用時間片輪轉調度算法，CPU 時間片為1ms仔役，那么進程需要切換 100 次掷伙。如果采用多級反饋隊列調度算法，依次隊列對應的時間片是1又兵、2任柜、4、8沛厨、16宙地、32、64逆皮、...等宅粥。因此，進程 A 只需要交換7次电谣。
例子2：一個多級反饋隊列的調度程序有三個隊列秽梅，從 1 到 3（如上圖所示）。調度程序首先執(zhí)行隊列 1 內的所有進程辰企。只有當隊列 1 為空時风纠，它才能執(zhí)行隊列 2 內的進程。類似地牢贸，只有隊列 1 和 2 都為空時竹观，隊列 3 的進程才能執(zhí)行。到達隊列 1 的進程會搶占隊列 2 的進程潜索，同理到達隊列 2 的進程會搶占隊列 3 的進程臭增。每個進程在進入就緒隊列后，就被添加到隊列 1 內竹习。隊列 1 內的每個進程都有 1ms 的時間片誊抛。如果一個進程不能在這一時間片內完成，那么它就被移到隊列 2 的尾部整陌。如果隊列 1 為空拗窃，隊列 2 頭部的進程會得到一個 2ms 的時間片。如果它不能完成泌辫，那么將被搶占随夸，并添加到隊列 3。只有當隊列 1 和 2 為空時震放，隊列 3 內的進程才按照RR算法?運行宾毒。
6.線程
6.1 為什么引入線程的概念
進程的創(chuàng)建、刪除和切換過程中時空代價大殿遂，限制了系統(tǒng)中的進程數目和并發(fā)活動的程度诈铛。因此乙各，現代操作系統(tǒng)中，進程作為資源的擁有者幢竹，調度和運行的屬性賦予新的實體——線程耳峦。
進程模型在處理“基于同數據區(qū)的同時多請求”時的效率局限性，例：售票系統(tǒng)：數據庫服務器軟件需同時處理來自多個用戶進程的讀盤請求妨退，這些請求都是針對同一個盤妇萄，可以有如下幾種方式：
① 進程：一個進程來順序處理。
② 多個相互獨立的進程：每個進程負責處理一個請求咬荷。
③ 用一個進程來并行處理所有請求冠句。
分析：第一種方法沒有并發(fā)，第二種方法切換的代價比較大幸乒。采用第三種方法效率更高懦底，實現一個進程有多個子任務并發(fā)執(zhí)行（線程）。
6.2 線程和進程的區(qū)別
①?擁有資源
進程是資源分配的基本單位罕扎，但是線程不擁有資源聚唐，線程可以訪問隸屬進程的資源。
②?調度
線程是獨立調度的基本單位腔召，在同一進程中杆查，線程的切換不會引起進程切換，從一個進程中的線程切換到另一個進程中的線程時臀蛛，會引起進程切換亲桦。
③?系統(tǒng)開銷
由于創(chuàng)建或撤銷進程時，系統(tǒng)都要為之分配或回收資源浊仆，如內存空間客峭、I/O 設備等，所付出的開銷遠大于創(chuàng)建或撤銷線程時的開銷抡柿。類似地舔琅，在進行進程切換時，涉及當前執(zhí)行進程 CPU 環(huán)境的保存及新調度進程 CPU 環(huán)境的設置洲劣，而線程切換時只需保存和設置少量寄存器內容备蚓，開銷很小。
④?通信方面
線程間可以通過直接讀寫同一進程中的數據進行通信囱稽，但是進程通信需要借助 IPC星著。
6.3 線程的特點
① 進程可以提高線程數來提高并發(fā)程度。
② 線程切換的代價比進程切換的少粗悯，因為進程設計虛擬地址空間的切換。
③? 由于線程間共享進程的代碼同欠、數據样傍、內存和文件資源横缔，可直接進行不通過內核進行通信；進程間的通信需要通過內核進行衫哥。
