第五講進(jìn)程調(diào)度與線程概念

進(jìn)程調(diào)度 CPU調(diào)度 要解決的問題WHAT 按什么原則分配CPU 進(jìn)程調(diào)度算法WHEN 何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)HOW 如何分配CPU CPU調(diào)度過程 進(jìn)程的上下文切換 處理機(jī)調(diào)度分成三個(gè)層次 處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響可把處理機(jī)調(diào)度分成三個(gè)層次 高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度 高級(jí)調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度高級(jí)調(diào)度的時(shí)間尺度通常是分鐘 小時(shí)或天中級(jí)調(diào)度涉及進(jìn)程在內(nèi)外存間的交換 從存儲(chǔ)器資源管理的角度來看 把進(jìn)程的部分或全部換出到外存上 可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)存空間 將當(dāng)前進(jìn)程所需部分換入到內(nèi)存 指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問低級(jí)調(diào)度也稱微觀調(diào)度 從處理機(jī)資源分配的角度來看 處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài) 低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的 由于低級(jí)調(diào)度算法的頻繁使用 要求在實(shí)現(xiàn)時(shí)做到高效 一 進(jìn)程調(diào)度算法 1 進(jìn)程調(diào)度進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng) 即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程 把CPU的使用權(quán)交給被選中的進(jìn)程 2 確定算法的原則 具有公平性資源利用率高 特別是CPU利用率 在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間 越短越好 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量 3 各種進(jìn)程調(diào)度算法 先進(jìn)先出進(jìn)程調(diào)度算法 FIFO 按照進(jìn)程就緒的先后次序來調(diào)度進(jìn)程優(yōu)點(diǎn) 實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn) 沒考慮進(jìn)程的優(yōu)先級(jí) 基于優(yōu)先數(shù)的調(diào)度 HPF HighestPriorityFirst 優(yōu)先選擇就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程投入運(yùn)行優(yōu)先級(jí)根據(jù)優(yōu)先數(shù)來決定 確定優(yōu)先數(shù)的方法靜態(tài)優(yōu)先數(shù)法 在進(jìn)程創(chuàng)建時(shí)指定優(yōu)先數(shù) 在進(jìn)程運(yùn)行時(shí)優(yōu)先數(shù)不變動(dòng)態(tài)優(yōu)先數(shù)法 在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù) 但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化 如等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變 兩種占用CPU的方式 可剝奪式 可搶占式Preemptive 當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí) 系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU 提供給具有更高優(yōu)先級(jí)的進(jìn)程使用不可剝奪式 不可搶占式Non preemptive 某一進(jìn)程被調(diào)度運(yùn)行后 除非由于它自身的原因不能運(yùn)行 否則一直運(yùn)行下去 時(shí)間片輪轉(zhuǎn)程序調(diào)度算法 RR RoundRobin 把CPU劃分成若干時(shí)間片 并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程 進(jìn)程輪流占有CPU 當(dāng)時(shí)間片用完時(shí) 即使進(jìn)程未執(zhí)行完畢 系統(tǒng)也剝奪該進(jìn)程的CPU 將該進(jìn)程排在就緒隊(duì)列末尾 同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行 分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法 時(shí)間片選擇問題 固定時(shí)間片可變時(shí)間片與時(shí)間片大小有關(guān)的因素 系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力 多隊(duì)列反饋調(diào)度算法 將就緒隊(duì)列分為N級(jí) 每個(gè)就緒隊(duì)列分配給不同的時(shí)間片 隊(duì)列級(jí)別越高 時(shí)間越長(zhǎng) 級(jí)別越小 時(shí)間片越小 最后一級(jí)采用時(shí)間片輪轉(zhuǎn) 其他隊(duì)列采用先進(jìn)先出 系統(tǒng)從第一級(jí)調(diào)度 當(dāng)?shù)谝患?jí)為空時(shí) 系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列 當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片 放棄CPU時(shí) 進(jìn)入下一級(jí)隊(duì)列 等待進(jìn)程被喚醒時(shí) 進(jìn)入原來的就緒隊(duì)列 當(dāng)進(jìn)程第一次就緒時(shí) 進(jìn)入第一級(jí)隊(duì)列 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列 每個(gè)就緒隊(duì)列分配給不同時(shí)間片 優(yōu)先級(jí)高的為第一級(jí)隊(duì)列 時(shí)間片最小 隨著隊(duì)列級(jí)別的降低 時(shí)間片加大 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法 一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列 進(jìn)程由于等待而放棄CPU后 進(jìn)入等待隊(duì)列 一旦等待的事件發(fā)生 則回到原來的就緒隊(duì)列 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí) 可以搶占CPU 被搶占進(jìn)程回到原來一級(jí)就緒隊(duì)列末尾 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí) 就去調(diào)度第二級(jí)隊(duì)列 如此類推 當(dāng)時(shí)間片到后 進(jìn)程放棄CPU 回到下一級(jí)隊(duì)列 二 進(jìn)程調(diào)度的時(shí)機(jī) 當(dāng)一個(gè)進(jìn)程運(yùn)行完畢 或由于某種錯(cuò)誤而終止運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài) 等待I O 分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒 可搶占式 例如 新創(chuàng)建一個(gè)進(jìn)程 一個(gè)等待進(jìn)程變成就緒在進(jìn)程通信中 執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作 P操作 阻塞原語 喚醒原語 三 進(jìn)程切換 進(jìn)程切換一個(gè)進(jìn)程讓出處理器 由另一個(gè)進(jìn)程占用處理器的過程進(jìn)程的切換使系統(tǒng)中的各進(jìn)程均有機(jī)會(huì)占用CPU進(jìn)程的切換是由進(jìn)程狀態(tài)的變化引起的 而進(jìn)程狀態(tài)的變化又與出現(xiàn)中斷事件有關(guān)當(dāng)有中斷事件發(fā)生時(shí) 當(dāng)前運(yùn)行的進(jìn)程被中斷 中斷響應(yīng)后由操作系統(tǒng)處理出現(xiàn)的中斷事件 中斷處理后 某些進(jìn)程的狀態(tài)會(huì)發(fā)生變化 也可能又創(chuàng)建了一些新的進(jìn)程 因此 要進(jìn)行隊(duì)列的調(diào)整 然后 進(jìn)程調(diào)度根據(jù)預(yù)定的調(diào)度算法從就緒隊(duì)列選一個(gè)進(jìn)程占用CPU 這個(gè)占用CPU運(yùn)行的進(jìn)程可能仍是被中斷的進(jìn)程 也可能是另一個(gè)進(jìn)程 何時(shí)切換進(jìn)程 只要OS取得對(duì)CPU的控制 進(jìn)程切換就可能發(fā)生 如 超級(jí)用戶調(diào)用來自程序的顯式請(qǐng)求 如 打開文件 該進(jìn)程通常會(huì)被阻塞陷阱最末一條指令導(dǎo)致出錯(cuò) 會(huì)引起進(jìn)程移至退出狀態(tài)中斷外部因素影響當(dāng)前指令的執(zhí)行 控制被轉(zhuǎn)移至IH 中斷處理程序 中斷的例子 時(shí)鐘進(jìn)程用完其時(shí)間片 被轉(zhuǎn)換至就緒狀態(tài)I O先前等待該事件的進(jìn)程被轉(zhuǎn)換為就緒 或就緒掛起 狀態(tài)然后重新運(yùn)行該進(jìn)程或選擇一更高優(yōu)先級(jí)的進(jìn)程存儲(chǔ)器因素內(nèi)存地址是在虛擬存儲(chǔ)器中 它必須把對(duì)應(yīng)的存儲(chǔ)塊調(diào)入主存于是相應(yīng)的進(jìn)程成為阻塞狀態(tài) 等待I O完成 四 CPU調(diào)度過程 保存現(xiàn)場(chǎng) 順序保存 最后一步保存PSW 選擇要運(yùn)行的程序 如果沒有就緒進(jìn)程 系統(tǒng)會(huì)安排一個(gè)閑逛進(jìn)程 idle 沒有其他進(jìn)程時(shí)該進(jìn)程一直運(yùn)行 在執(zhí)行過程中可接收中斷 恢復(fù)現(xiàn)場(chǎng) 最后一步恢復(fù)選中進(jìn)程的PSW 在進(jìn)程 上下文 中切換的步驟 保存處理器的上下文 包括程序計(jì)數(shù)器和其它寄存器用新狀態(tài)和其它相關(guān)信息更新正在運(yùn)行進(jìn)程的PCB把原來的進(jìn)程移至合適的隊(duì)列 就緒 阻塞選擇另一個(gè)要執(zhí)行的進(jìn)程更新被選中進(jìn)程的PCB從被選中進(jìn)程中重裝入CPU上下文 二 系統(tǒng)核心 系統(tǒng)核心 向上提供多個(gè)無中斷的虛擬機(jī)器在核心內(nèi)不允許中斷特點(diǎn) 為進(jìn)程運(yùn)行提供一個(gè)舞臺(tái) 核心常駐內(nèi)存 設(shè)計(jì)短小精焊 1 核心的組成 中斷處理進(jìn)程管理 調(diào)度控制通訊互斥同步等原語管理 在核心中提供一系列原語 同步 通信 創(chuàng)建 撤消等 隊(duì)列管理 隊(duì)列數(shù)據(jù)結(jié)構(gòu) 指向隊(duì)首的表指針三個(gè)隊(duì)列 運(yùn)行 就緒 等待隊(duì)列排隊(duì)方式 排隊(duì)首排隊(duì)尾插隊(duì)出隊(duì)方式 隊(duì)首出隊(duì) 隊(duì)中出隊(duì)隊(duì)列管理 中斷之后 進(jìn)程調(diào)度之前 現(xiàn)場(chǎng)管理 保存現(xiàn)場(chǎng) 注意順序 中斷之后第一步恢復(fù)現(xiàn)場(chǎng) 恢復(fù)時(shí)機(jī) 進(jìn)程調(diào)度最后一步時(shí)鐘管理 以固定頻率 1 1用途 進(jìn)入絕對(duì)時(shí)鐘間隔時(shí)鐘進(jìn)行分析比較 虛時(shí)鐘 每個(gè)進(jìn)程分配給一個(gè)虛時(shí)鐘來記錄CPU時(shí)間 這個(gè)時(shí)鐘稱為虛時(shí)鐘虛時(shí)鐘存放在PCB中 屬于現(xiàn)場(chǎng)的一部分 進(jìn)程運(yùn)行時(shí) 將虛時(shí)鐘放入內(nèi)存開辟的專門單元 離開CPU則放在PCB中 2 核心處理流程 進(jìn)入核心的唯一入口 中斷中斷后進(jìn)入核心 由硬件完成 3 內(nèi)核的執(zhí)行特點(diǎn) 由中斷驅(qū)動(dòng)的 中斷 內(nèi)核 退出內(nèi)核執(zhí)行是連續(xù)的內(nèi)核執(zhí)行過程中在中斷屏蔽狀態(tài)下內(nèi)核使用特權(quán)指令 三 線程的基本概念 線程的引入線程與進(jìn)程的對(duì)比線程的實(shí)現(xiàn)實(shí)例 Solaris 1 線程的引入 進(jìn)程的兩個(gè)基本屬性 資源的擁有者 給每個(gè)進(jìn)程分配一虛擬地址空間 保存進(jìn)程映像 控制一些資源 文件 I O設(shè)備 有狀態(tài) 優(yōu)先級(jí) 調(diào)度調(diào)度單位 進(jìn)程是一個(gè)執(zhí)行軌跡以上兩個(gè)屬性構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ) 線程的引入 續(xù)1 系統(tǒng)必須完成的操作 創(chuàng)建進(jìn)程撤消進(jìn)程進(jìn)程切換缺點(diǎn) 時(shí)間空間開銷大 限制并發(fā)度的提高 線程的引入 續(xù)2 在操作系統(tǒng)中 進(jìn)程的引入提高了計(jì)算機(jī)資源的利用效率 但在進(jìn)一步提高進(jìn)程的并發(fā)性時(shí) 人們發(fā)現(xiàn)進(jìn)程切換開銷占的比重越來越大 同時(shí)進(jìn)程間通信的效率也受到限制線程的引入正是為了簡(jiǎn)化線程間的通信 以小的開銷來提高進(jìn)程內(nèi)的并發(fā)程度 線程的引入 續(xù)3 線程 有時(shí)稱輕量級(jí)進(jìn)程進(jìn)程中的一個(gè)運(yùn)行實(shí)體是一個(gè)CPU調(diào)度單位資源的擁有者還是進(jìn)程或稱任務(wù)將原來進(jìn)程的兩個(gè)屬性分開處理 線程的引入 續(xù)4 線程 有執(zhí)行狀態(tài) 狀態(tài)轉(zhuǎn)換 不運(yùn)行時(shí)保存上下文有一個(gè)執(zhí)行棧有一些局部變量的靜態(tài)存儲(chǔ)可存取所在進(jìn)程的內(nèi)存和其他資源可以創(chuàng)建 撤消另一個(gè)線程 線程和進(jìn)程 單進(jìn)程 單線程單進(jìn)程 多線程多進(jìn)程 一個(gè)進(jìn)程一個(gè)線程多進(jìn)程 一個(gè)進(jìn)程多個(gè)線程 引入線程的好處 創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少 結(jié)束亦如此 兩個(gè)線程的切換花費(fèi)時(shí)間少 如果機(jī)器設(shè)有 存儲(chǔ) 恢復(fù) 所有寄存器 指令 則整個(gè)切換過程用幾條指令即可完成 因?yàn)橥贿M(jìn)程內(nèi)的線程共享內(nèi)存和文件 因此它們之間相互通信無須調(diào)用內(nèi)核適合多處理機(jī)系統(tǒng) 例子1 LAN中的一個(gè)文件服務(wù)器 在一段時(shí)間內(nèi)需要處理幾個(gè)文件請(qǐng)求因此有效的方法是 為每一個(gè)請(qǐng)求創(chuàng)建一個(gè)線程在一個(gè)SMP機(jī)器上 多個(gè)線程可以同時(shí)在不同的處理器上運(yùn)行 例子2 一個(gè)線程顯示菜單 并讀入用戶輸入 另一個(gè)線程執(zhí)行用戶命令考慮一個(gè)應(yīng)用 由幾個(gè)獨(dú)立部分組成 這幾個(gè)部分不需要順序執(zhí)行 則每個(gè)部分可以以線程方式實(shí)現(xiàn)當(dāng)一個(gè)線程因I O阻塞時(shí) 可以切換到同一應(yīng)用的另一個(gè)線程 2 線程與進(jìn)程的比較 調(diào)度并發(fā)性擁有資源系統(tǒng)開銷 3 線程的實(shí)現(xiàn)機(jī)制 用戶級(jí)線程核心級(jí)線程兩者結(jié)合方法 1 用戶級(jí)線程 UserLevelThread 由應(yīng)用程序完成所有線程的管理通過線程庫 用戶空間 一組管理線程的過程核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應(yīng)用特定的 線程庫 創(chuàng)建 撤消線程在線程之間傳遞消息和數(shù)據(jù)調(diào)度線程執(zhí)行保護(hù)和恢復(fù)線程上下文 對(duì)用戶級(jí)線程的核心活動(dòng) 核心不知道線程的活動(dòng) 但仍然管理線程的進(jìn)程的活動(dòng)當(dāng)線程調(diào)用系統(tǒng)調(diào)用時(shí) 整個(gè)進(jìn)程阻塞但對(duì)線程庫來說 線程仍然是運(yùn)行狀態(tài)即線程狀態(tài)是與進(jìn)程狀態(tài)獨(dú)立的 用戶級(jí)線程的優(yōu)點(diǎn)和缺點(diǎn) 優(yōu)點(diǎn) 線程切換不調(diào)用核心調(diào)度是應(yīng)用程序特定的 可以選擇最好的算法ULT可運(yùn)行在任何操作系統(tǒng)上 只需要線程庫 缺點(diǎn) 大多數(shù)系統(tǒng)調(diào)用是阻塞的 因此核心阻塞進(jìn)程 故進(jìn)程中所有線程將被阻塞核心只將處理器分配給進(jìn)程 同一進(jìn)程中的兩個(gè)線程不能同時(shí)運(yùn)行于兩個(gè)處理器上 2 核心級(jí)線程 KLT 所有線程管理由核心完成沒有線程庫 但對(duì)核心線程工具提供API核心維護(hù)進(jìn)程和線程的上下文線程之間的切換需要核心支持以線程為基礎(chǔ)進(jìn)行調(diào)度例子 WindowsNT OS 2 核心級(jí)線程的優(yōu)點(diǎn)和缺點(diǎn) 優(yōu)點(diǎn) 對(duì)多處理器 核心可以同時(shí)調(diào)度同一進(jìn)程的多個(gè)線程阻塞是在線程一級(jí)完成核心例程是多線程的缺點(diǎn) 在同一進(jìn)程內(nèi)的線程切換調(diào)用內(nèi)核 導(dǎo)致速度下降 3 兩者分析 針對(duì)不同的操作系統(tǒng)開銷和性能 線程的調(diào)度和切換速度 系統(tǒng)調(diào)用 阻塞 線程執(zhí)行時(shí)間靈活性可擴(kuò)充性搶占CPU共享進(jìn)程的資源 4 ULT和KLT結(jié)合方法 線程創(chuàng)建在用戶空間完成大量線程調(diào)度和同步在用戶空間完成程序員可以調(diào)整KLT的數(shù)量可以取兩者中最好的例子 Solaris 4 實(shí)例 Solaris 進(jìn)程 用戶地址空間用戶棧進(jìn)程控制塊 實(shí)例 Solaris 續(xù)1 用戶級(jí)線程 線程庫 可在應(yīng)用進(jìn)程中建立多個(gè)ULT每個(gè)ULT需要 棧 程序計(jì)數(shù)器不受調(diào)度程序的調(diào)度 線程切換快對(duì)操作系統(tǒng)不可見提供應(yīng)用程序并行性接口 實(shí)例 Solaris 續(xù)2 核心級(jí)線程 設(shè)置了大量KLT有一個(gè)小的數(shù)據(jù)結(jié)構(gòu)和棧完成內(nèi)核的所有工作調(diào)度處理器的單位 其結(jié)構(gòu)由核心維護(hù) 實(shí)例 Solaris 續(xù)3 輕型進(jìn)程 LWP 每個(gè)ULT利用LWP與內(nèi)核通信每個(gè)LWP支持一個(gè)或多個(gè)用戶級(jí)線程 并映射到一個(gè)核心級(jí)線程每個(gè)LWP