第2章處理器管理(201409)

1、高等教育出版社出版2014年1月第二章 處理器管理2.1 處理器狀態(tài) 2.2 中斷技術(shù)2.3 進(jìn)程及其實(shí)現(xiàn)2.4 線程及其實(shí)現(xiàn)2.5 Linux進(jìn)程2.6 處理器調(diào)度2.7 Linux調(diào)度算法2.1.1處理器2.1.2程序狀態(tài)字l計(jì)算機(jī)系統(tǒng)的處理器包括一組寄存器，其個(gè)數(shù)根據(jù)機(jī)型的不同而不同，它們構(gòu)成了一級(jí)存儲(chǔ)，比主存容量小 ，但訪問速度快。l這組寄存器所存儲(chǔ)的信息與程序的執(zhí)行有很大關(guān)系，構(gòu)成了處理器現(xiàn)場(chǎng)。 l通用寄存器- EAX，EBX，ECX和EDXl指針及變址寄存器-ESP，EBP，ESI及EDIl段選擇符寄存器-CS、DS、SS、ES 、FS、GS l指令指針寄存器和標(biāo)志寄存器-EIP、

2、EFLAGSl控制寄存器-CR0，CR1，CR2和CR3 l外部設(shè)備使用的寄存器EAXEBXECXEDXAXBXCXDXESPEBPESIEDISPBPSIDICSDSSSESFSGSIPEFLAGSCR0CR1CR2 CR32. 特權(quán)指令與非特權(quán)指令(1) 機(jī)器指令的集合稱指令系統(tǒng) (1)數(shù)據(jù)處理類指令； (2)轉(zhuǎn)移類指令； (3)數(shù)據(jù)傳送類指令； (4)移位與字符串指令； (5)I/O類指令。l從資源管理和控制程序執(zhí)行的角度出發(fā)，把指令系統(tǒng)中的指令分作兩部分：特權(quán)指令和非特權(quán)指令。l特權(quán)指令是指只能提供給操作系統(tǒng)的核心程序使用的指令，如啟動(dòng)I/O設(shè)備、設(shè)置時(shí)鐘、控制中斷屏蔽位、清主存、建立

3、存儲(chǔ)鍵，加載PSW等。3. 內(nèi)核態(tài)和用戶態(tài) 處理器怎么知道當(dāng)前是操作系統(tǒng)還是一般用戶程序在運(yùn)行呢? 處理器狀態(tài)標(biāo)志: 管理狀態(tài)（核心狀態(tài)、特態(tài)或管態(tài)）和用戶狀態(tài)（目標(biāo)狀態(tài)、常態(tài)或目態(tài))。處理器狀態(tài)的轉(zhuǎn)換。 處理器處于管理狀態(tài)時(shí)，程序可以執(zhí)行全部指令，使用所有資源，具有改變處只能執(zhí)行非特權(quán)指令。 Intel x86的處理器狀態(tài)有四理器狀態(tài)的能力；處理器處于用戶狀態(tài)時(shí)，程序種，支持4個(gè)保護(hù)級(jí)別，0級(jí)權(quán)限最高，3級(jí)權(quán)限最低。 l導(dǎo)致處理器從用戶態(tài)向內(nèi)核態(tài)轉(zhuǎn)換，一是程序請(qǐng)求操作系統(tǒng)服務(wù)，執(zhí)行系統(tǒng)調(diào)用；二是程序運(yùn)行時(shí)，產(chǎn)生中斷或異常事件，運(yùn)行程序被中斷，轉(zhuǎn)向中斷處理或異常處理程序工作。l兩類情況都通過中

4、斷機(jī)制發(fā)生，中斷和異常是用戶態(tài)到內(nèi)核態(tài)轉(zhuǎn)換僅有的途徑。l從內(nèi)核態(tài)轉(zhuǎn)向用戶態(tài)，計(jì)算機(jī)提供一條特權(quán)指令稱作加載程序狀態(tài)字(Intel x86為iret指令)，用來實(shí)現(xiàn)從系統(tǒng)(核心態(tài))返回到用戶態(tài)，控制權(quán)交給應(yīng)用進(jìn)程。 (1) 用戶棧 (2) 核心棧 (3) 棧指針2.1.2 程序狀態(tài)字(1) 計(jì)算機(jī)如何知道當(dāng)前處于何種工作狀態(tài)？這時(shí)能否執(zhí)行特權(quán)指令？通常操作系統(tǒng)都引入程序狀態(tài)字PSW（Program Status Word）來區(qū)別不同的處理器工作狀態(tài)。 PSW用來控制指令執(zhí)行順序并保留和指示與程序有關(guān)的系統(tǒng)狀態(tài)，主要作用是實(shí)現(xiàn)程序狀態(tài)的保護(hù)和恢復(fù)。 每個(gè)程序都有一個(gè)與其執(zhí)行相關(guān)的PSW，每個(gè)處理器

5、都設(shè)置一個(gè)PSW寄存器。程序占有處理器執(zhí)行，它的PSW將占有PSW寄存器。 程序狀態(tài)字寄存器(2) PSW寄存器包括以下內(nèi)容： 程序基本狀態(tài)： (1) 程序計(jì)數(shù)器； (2) 條件碼； (3）處理器狀態(tài)位。 中斷碼。保存程序執(zhí)行時(shí)當(dāng)前發(fā)生的中斷事件。 中斷屏蔽位。指明程序執(zhí)行中發(fā)生中斷事件時(shí)，是否響應(yīng)出現(xiàn)的中斷事件。 lIntel x86中，PSW由標(biāo)志寄存器EFLAGS和指令指針寄存器EIP組成，均為32位。lEFLAGS的低16位稱FLAGS，標(biāo)志可劃分為三組：狀態(tài)標(biāo)志、控制標(biāo)志、系統(tǒng)標(biāo)志。2.2.1 中斷概念2.2.2 中斷源分類2.2.3 中斷和異常的響應(yīng)及服務(wù)2.2.4 中斷事件處理原

6、則2.2.5 中斷優(yōu)先級(jí)和多重中斷2.2.6 Linux中斷處理 請(qǐng)求系統(tǒng)服務(wù)， 實(shí)現(xiàn)并行工作， 處理突發(fā)事件， 滿足實(shí)時(shí)要求， 都需要打斷處理器正常的工作，為此，提出了中斷概念。 中斷是指程序執(zhí)行過程中，遇到急需處理的事件時(shí)，暫時(shí)中止CPU上現(xiàn)行程序的運(yùn)行，轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完成后再返回原程序被中斷處或調(diào)度其他程序執(zhí)行的過程。 外中斷(中斷或異步中斷)-是指來自處理器之外的中斷信號(hào)，包括時(shí)鐘中斷、鍵盤中斷和設(shè)備中斷等；外中斷又分可屏蔽中斷和不可屏蔽中斷，每個(gè)不同中斷具有不同的中斷優(yōu)先級(jí)，表示事件的緊急程度，在處理高一級(jí)中斷時(shí)，往往會(huì)屏蔽部分或全部低級(jí)中斷。 內(nèi)中斷(異?；蛲?/p>

7、中斷)-是指來自處理器內(nèi)部，通常由于程序執(zhí)行中，發(fā)現(xiàn)與當(dāng)前指令關(guān)聯(lián)的、不正常的、或是錯(cuò)誤的事件。 (1)中斷是由與現(xiàn)行指令無關(guān)的中斷信號(hào)觸發(fā)的(異步的)，且中斷的發(fā)生與CPU處在用戶模式或內(nèi)核模式無關(guān)，在兩條機(jī)器指令之間才可響應(yīng)中斷，一般來說，中斷處理程序提供的服務(wù)不是為當(dāng)前進(jìn)程所需的； 異常是由處理器正在執(zhí)行現(xiàn)行指令而引起的，一條指令執(zhí)行期間允許響應(yīng)異常，異常處理程序提供的服務(wù)是為當(dāng)前進(jìn)程所用的。異常包括很多方面，有出錯(cuò)(fault)，也有陷入(trap)等。 l（2）要求“中斷”被快速處理，以便及時(shí)響應(yīng)其它中斷信號(hào)，所以，中斷處理程序處理過程中是不能阻塞的?！爱惓！碧幱诒淮驍嗟漠?dāng)前進(jìn)程上下

8、文中，所提供的服務(wù)是當(dāng)前進(jìn)程所需要的，所以，異常處理程序處理過程中是可以阻塞的。l（3）中斷允許發(fā)生嵌套，但異常大多為一重；異常處理過程中可能會(huì)產(chǎn)生中斷，但中斷處理過程中決不會(huì)被異常打斷。 l發(fā)現(xiàn)中斷源：l保護(hù)現(xiàn)場(chǎng)：l轉(zhuǎn)向處理中斷/異常事件的處理程序：l恢復(fù)現(xiàn)場(chǎng)。IPCSPSW現(xiàn)行PSW寄存器新IP新CS老IP老CS老PSW新棧頂 內(nèi)存新PSW2.2.4 中斷事件處理原則1 . 硬件故障中斷2. 程序性中斷3. I/O中斷4. 訪管中斷5. 時(shí)鐘中斷 5時(shí)鐘中斷(1) 時(shí)鐘是操作系統(tǒng)進(jìn)行調(diào)度工作的重要工具，如讓分時(shí)進(jìn)程作時(shí)間片輪轉(zhuǎn)、讓實(shí)時(shí)進(jìn)程定時(shí)發(fā)出或接收控制信號(hào)、系統(tǒng)定時(shí)喚醒或阻塞一個(gè)進(jìn)程、

9、對(duì)用戶進(jìn)程進(jìn)行記賬 時(shí)鐘可分成絕對(duì)時(shí)鐘和間隔時(shí)鐘兩種 Linux系統(tǒng)運(yùn)行不同的間隔定時(shí)器，類型有三種：lreal 間隔定時(shí)器-按實(shí)際經(jīng)過時(shí)間計(jì)時(shí)，不管進(jìn)程處在何種模式下運(yùn)行，包括進(jìn)程被掛起時(shí)，計(jì)時(shí)總在進(jìn)行，定時(shí)到達(dá)時(shí)發(fā)送給進(jìn)程一個(gè)SIGALRM信號(hào)。lvirtual 間隔定時(shí)器-進(jìn)程在用戶態(tài)下執(zhí)行時(shí)才計(jì)時(shí)，定時(shí)到達(dá)時(shí)發(fā)送給進(jìn)程一個(gè)SIGVTALRM信號(hào)。lprofile 間隔定時(shí)器-進(jìn)程執(zhí)行在用戶態(tài)或核心態(tài)時(shí)都計(jì)時(shí)，當(dāng)定時(shí)到達(dá)時(shí)發(fā)送給進(jìn)程一個(gè)SIGROF信號(hào)。 2.2.5 中斷優(yōu)先級(jí)和多重中斷1. 中斷優(yōu)先級(jí)2. 中斷屏蔽3. 多重中斷事件的處理 計(jì)算機(jī)執(zhí)行的每一瞬間，可能有幾個(gè)中斷事件同時(shí)發(fā)

10、生，中斷裝置如何來響應(yīng)同時(shí)發(fā)生的中斷呢? 以不發(fā)生中斷丟失為前提，把緊迫程度相當(dāng)?shù)闹袛嘣礆w在同一級(jí)，緊迫程度差別大的中斷源歸在不同級(jí)， 級(jí)別高的有優(yōu)先獲得響應(yīng)的權(quán)力，中斷裝置預(yù)定的這個(gè)響應(yīng)順序稱為中斷優(yōu)先級(jí)。 1. 中斷優(yōu)先級(jí)2. 中斷屏蔽 可編程中斷控制器，可通過指令設(shè)置屏蔽碼。中斷屏蔽是指禁止CPU響應(yīng)中斷或禁止中斷產(chǎn)生。 前者指硬件產(chǎn)生中斷請(qǐng)求后，CPU暫時(shí)不予響應(yīng)的狀態(tài)。后者指可引起中斷的事件發(fā)生時(shí)，硬件不允許提出中斷請(qǐng)求也不通知處理器，故不可能導(dǎo)致中斷。中斷屏蔽的作用 一、是延遲或禁止某些中斷的響應(yīng)。系統(tǒng)程序執(zhí)行過程中，不希望產(chǎn)生干擾事件，以免共享數(shù)據(jù)結(jié)構(gòu)受到破壞。程序運(yùn)行過程中產(chǎn)生

11、某些事件認(rèn)為是正常的，不必加以處理。 二、是協(xié)調(diào)中斷響應(yīng)與中斷處理的關(guān)系。確保高優(yōu)先級(jí)中斷可以打斷低優(yōu)先級(jí)中斷，反之卻不能。 三、是防止同級(jí)中斷相互干擾。在處理某優(yōu)先級(jí)中斷事件時(shí)，必須屏蔽該級(jí)中斷，以免造成混亂。 中斷正在進(jìn)行處理期間，CPU又響應(yīng)新的中斷事件，于是暫時(shí)停止正在運(yùn)行的中斷處理程序，轉(zhuǎn)去執(zhí)行新的中斷處理程序，就叫多重中斷（又稱中多重中斷（又稱中斷嵌套）斷嵌套）。處理方法： (1) 串行處理， (2) 嵌套處理， (3) 即時(shí)處理。 用戶態(tài)快中斷慢中斷異常中斷用戶態(tài)核心態(tài) 上半部分處理 排隊(duì)下半部分快中斷處理 系統(tǒng)調(diào)用處理 從系統(tǒng)調(diào)用返回ret_from_sys_call( )調(diào)用

12、schedule( )調(diào)度被中斷進(jìn)程或新進(jìn)程運(yùn)行調(diào)度下半部分do_softirq( )處理積累信號(hào)do_signal( )恢復(fù)保存的部分寄存器中斷保存部分寄存器保存全部寄存器 ret_from_intr( )進(jìn)程運(yùn)行檢查TIF_NEED_RESCHED標(biāo)志Linux內(nèi)核處理流程lIntel x86機(jī)器支持256種中斷信號(hào)，從0到255編號(hào)組成“中斷向量”。l中斷信號(hào)源分2類：中斷和異常。中斷分為屏蔽中斷和非屏蔽中斷；異常分為故障（fault）、陷阱（trap）、終止（abort）和編程異常 （programmed exception。l非屏蔽中斷和異常的向量是固定的，而屏蔽中斷的向量可通過對(duì)中

13、斷控制器編程加以改變。l256個(gè)中斷向量分配如下： 1)031的向量對(duì)應(yīng)于異常和非屏蔽中斷； 2)3247的向量對(duì)應(yīng)于屏蔽中斷，被外部設(shè)備使用； 3)48255的向量分配給軟中斷，Linux僅用1個(gè)，128號(hào)、即0 x80，實(shí)現(xiàn)系統(tǒng)調(diào)用。l在Linux系統(tǒng)中，每個(gè)能發(fā)送中斷信號(hào)的硬件設(shè)備控制器都有一根輸出線，它與中斷控制器8259A的輸入引腳相連，若一個(gè)硬件設(shè)備欲向CPU發(fā)送中斷信號(hào)，必須申請(qǐng)一條可用的“中斷請(qǐng)求線”，或者說必須申請(qǐng)一個(gè)IRQ號(hào)，這就是“中斷請(qǐng)求”IRQ（Interrupt Requirement）。lIRQ號(hào)與中斷向量號(hào)的對(duì)應(yīng)關(guān)系。INTAINTRCPUIRQ15IRQ14I

14、RQ13IRQ12IRQ11IRQ10IRQ9IR0 INTAIR1 INTIR2IR3 IR4IR5IR6IR7IRQ8IRQ4IRQ6IRQ5IRQ1IRQ0IRQ7IRQ3IR0 INTAIR1 INTIR2IR3IR4IR5IR6IR78259A主片8259A從片IRQ2Linux系統(tǒng)要處理3種門機(jī)制：1)中斷門(interrupt gate)-用于關(guān)中斷的中斷或異常處理；2)陷阱門(trap gate)-用于開中斷的異常處理；3)系統(tǒng)門(system gate)。用于系統(tǒng)調(diào)用。l中斷描述符表（Interrupt Descriptor Table，IDT）包含 個(gè)表項(xiàng)，每個(gè)中斷異常都對(duì)

15、應(yīng)一個(gè)，每個(gè)表項(xiàng)稱為一個(gè)門描述符(gate descriptor)，作用是把程序控制權(quán)轉(zhuǎn)交給中斷異常處理程序。中斷描述符表IDTIDTR IDT表基址 IDT表長(zhǎng)度中斷門描述符255中斷門描述符254.中斷門描述符3中斷門描述符2中斷門描述符1 IDT和IDTRl1) 中斷處理程序和中斷服務(wù)例程l硬件15條中斷線對(duì)應(yīng)15個(gè)中斷處理程序，編號(hào)為：IRQ0 x00_interrupt( )、IRQ0 x01_interrupt( )、。l例如，IRQ0 x05_interrupt( )是IRQ號(hào)為5(中斷向量號(hào)為37)的中斷處理程序，若5號(hào)中斷被網(wǎng)卡和圖形卡共享，則2種卡各有中斷服務(wù)例程。l區(qū)別中

16、斷處理程序和中斷服務(wù)例程(Interrupt Service Routine，ISR）。 lLinux系統(tǒng)為每個(gè)中斷請(qǐng)求IRQ設(shè)置一個(gè)隊(duì)列-“中斷請(qǐng)求隊(duì)列”l中斷線共享的數(shù)據(jù)結(jié)構(gòu)為irqaction，該結(jié)構(gòu)I/O設(shè)備中斷服務(wù)例程是handler。l每個(gè)中斷服務(wù)隊(duì)列開始為空，具體的中斷服務(wù)例程在設(shè)備驅(qū)動(dòng)程序初始化時(shí)，必須調(diào)用函數(shù)request_irq( )掛入，也就是進(jìn)行注冊(cè)。卸載設(shè)備驅(qū)動(dòng)程序時(shí)，調(diào)用函數(shù)free_irq( )釋放中斷線，并注銷中斷服務(wù)例程。l(1)中斷信號(hào)由外部設(shè)備發(fā)送到中斷控制器，IRQ號(hào)轉(zhuǎn)換成中斷向量號(hào)I傳送給CPU。l(2)CPU響應(yīng)和接收中斷，根據(jù)中斷向量號(hào)I查找IDT

17、表，找到門描述符，也就找到了對(duì)應(yīng)的IRQ0 x0n_interrupt( )中斷處理程序入口地址。l跳轉(zhuǎn)到common_interrupt代碼執(zhí)行，其做的工作有：中斷向量號(hào)入棧，利用宏SAVE_ALL保護(hù)寄存器到核心棧。然后，調(diào)用do_IRQ( )函數(shù)。l (3) do_IRQ( )函數(shù)對(duì)中斷進(jìn)行應(yīng)答，禁止該中斷線，確保該中斷線上有有效中斷服務(wù)例程。在關(guān)中斷條件下，do_IRQ( )調(diào)用handle_IRQ_event( ) 函數(shù)來執(zhí)行注冊(cè)到該中斷線上的所有中斷服務(wù)例程。l (4) 返回至內(nèi)核 ret_from_sys_call ( )代碼來完成一組標(biāo)準(zhǔn)任務(wù)，如調(diào)用do_softirq( )

18、函數(shù)處理軟中斷。調(diào)用do_signal( ) 函數(shù)處理信號(hào)。處理結(jié)束后跳轉(zhuǎn)到ret_from_intr( )退出中斷，使用宏RESTORE_ALL恢復(fù)現(xiàn)場(chǎng)，完成整個(gè)中斷處理，徹底從中斷返回。是(中斷向量號(hào)I)否中 斷 線 上 有中 斷 處 理 例程?do_IRQ( )中 斷 處 理 程 序IRQ0 x0n_interrupt( )產(chǎn)生中斷(IRQ號(hào))設(shè)備中斷控制器處理器ret_from_intr( )從中斷返回內(nèi)核代碼中斷服務(wù)例程執(zhí)行程序Handle_IRQ_event( )執(zhí)行中斷線上所有中斷服務(wù)例程?l異常產(chǎn)生后，轉(zhuǎn)向異常處理程序公共入口執(zhí)行，執(zhí)行下列操作：l1)將硬件錯(cuò)誤碼和異常向量號(hào)存

19、入當(dāng)前進(jìn)程PCB中；l2)判別異常產(chǎn)生于核心態(tài)還是用戶態(tài)，對(duì)于前者，轉(zhuǎn)向內(nèi)核預(yù)定義服務(wù)程序處理，沒有被處理的核心態(tài)異常是操作系統(tǒng)的致命錯(cuò)誤；l3)對(duì)于用戶態(tài)異常，終止當(dāng)前進(jìn)程運(yùn)行，調(diào)用force_sig( )函數(shù)給當(dāng)前進(jìn)程發(fā)信號(hào)；l4)從ret_from_exception處返回用戶空間時(shí)，檢查進(jìn)程是否有信號(hào)等待處理，如果有則根據(jù)信號(hào)類型調(diào)用相應(yīng)函數(shù)進(jìn)行處理。l中斷處理程序的特點(diǎn)l什么是下半部分處理?lTop halflBottom halfl以異步方式運(yùn)行，可能會(huì)打斷關(guān)鍵代碼的執(zhí)行，甚至打斷其他中斷處理程序的執(zhí)行；l在屏蔽中斷狀態(tài)下運(yùn)行，最壞的情況會(huì)禁止所有中斷；l要對(duì)硬件進(jìn)行操作，有很高的

20、時(shí)限要求；它在中斷上下文中運(yùn)行，故不能被阻塞 。ltasklet、lwork queue、lSoftirq。ltasklet能更好支持SMP，它基于軟中斷來實(shí)現(xiàn)，但比軟中斷接口簡(jiǎn)單，鎖保護(hù)要求低；softirq保留給執(zhí)行頻率及時(shí)間要求特高的下半部分使用(如網(wǎng)絡(luò)和SCSI)，多數(shù)場(chǎng)合下可使用tasklet。l使用tasklet的步驟：聲明tasklet 、編程tasklet、調(diào)度tasklet 。 lBH全局串行處理，不適應(yīng)SMP環(huán)境，而不同tasklet可同時(shí)運(yùn)行于不同CPU上，當(dāng)然，系統(tǒng)保證相同tasklet不會(huì)同時(shí)在不同CPU上運(yùn)行，在這種情形下，tasklet就不需要是可重入的。l在新版

21、Linux中，tasklet是建議的異步任務(wù)延遲執(zhí)行機(jī)制。lLinux 2.5內(nèi)核引入-工作隊(duì)列，它把一個(gè)任務(wù)延遲，并交給內(nèi)核線程去完成，且該任務(wù)總是在進(jìn)程上下文中執(zhí)行，通過工作隊(duì)列執(zhí)行的代碼能占盡進(jìn)程上下文的優(yōu)勢(shì)，最重要的是工作隊(duì)列允許重新調(diào)度及阻塞。l如果延遲執(zhí)行的任務(wù)需要阻塞，需要獲取信號(hào)量或需要獲得大量主存時(shí)，那么，可選擇工作隊(duì)列，否則可使用tasklet或softirq。lLinux沿用最早BH思想，實(shí)現(xiàn)了龐大和復(fù)雜的軟中斷子系統(tǒng)-softirq，它是一種軟中斷機(jī)制，又是一個(gè)框架，包括tasklet，及為網(wǎng)絡(luò)操作專門設(shè)計(jì)的軟中斷。l軟中斷結(jié)構(gòu)： struct softirq_acti

22、on void (*action)(struct softirq_action *); /待執(zhí)行的函數(shù) void *data; /傳給函數(shù)的參數(shù) l;l最多注冊(cè)32個(gè)軟中斷，目前預(yù)定義六個(gè)元素， enum HI_SOFTIRQ, /高優(yōu)先級(jí)tasklet TIMER_SOFTIRQ /定時(shí)器下半部分 NET_TX_SOFTIRQ, /發(fā)送網(wǎng)絡(luò)數(shù)據(jù)包 NET_RX_SOFTIRQ, /接收網(wǎng)絡(luò)數(shù)據(jù)包 SCSI_SOFTIRQ, /SCSI下半部分 TASKLET_SOFTIRQ, /公共tasklet ;l軟中斷使用步驟：聲明softirq 、注冊(cè)softirq 、觸發(fā)softirq 、處理so

23、ftirq 。l軟中斷執(zhí)行時(shí)機(jī) ：1)在處理完硬件中斷后；2)在 ksoftirqd 內(nèi)核線程中；3)在顯式檢查和執(zhí)行待處理的軟中斷的代碼中。2.3.1 進(jìn)程定義和屬性2.3.2 進(jìn)程狀態(tài)和轉(zhuǎn)換2.3.3 進(jìn)程描述和組成2.3.4 進(jìn)程上下文切換與處理器狀態(tài)轉(zhuǎn)換2.3.5 進(jìn)程控制和管理程序的并發(fā)執(zhí)行：程序的并發(fā)執(zhí)行： P1P2P3P4I1I2I3I4C1C2C3C4程序的并發(fā)執(zhí)行：程序的并發(fā)執(zhí)行： 四條語句的前趨關(guān)系四條語句的前趨關(guān)系S1S2S3S4對(duì)于具有下述四條語句的程序段：對(duì)于具有下述四條語句的程序段：程序程序A A：每執(zhí)行一次時(shí)，都要做：每執(zhí)行一次時(shí)，都要做N=N+1N=N+1操作；

24、操作；程序程序B B：每執(zhí)行一次時(shí)，：每執(zhí)行一次時(shí)， 都要執(zhí)行都要執(zhí)行Print(N)Print(N)操作，然后再將操作，然后再將N N置成置成“0 0”。 (1) N=N+1(1) N=N+1在在Print(N)Print(N)和和N=0N=0之前，此時(shí)得到的之前，此時(shí)得到的N N值分別為值分別為n+1, n+1, n+1, n+1, 0 0。 (2) N=N+1(2) N=N+1在在Print(N)Print(N)和和N=0N=0之后，此時(shí)得到的之后，此時(shí)得到的N N值分別為值分別為n, 0, 1n, 0, 1。 (3) N=N+1(3) N=N+1在在Print(N)Print(N)和和

25、N=0N=0之間，此時(shí)得到的之間，此時(shí)得到的N N值分別為值分別為n, n+1, 0n, n+1, 0。 程序的并發(fā)執(zhí)行時(shí)的特征：程序的并發(fā)執(zhí)行時(shí)的特征： 舉例：舉例： 進(jìn)程定義： 進(jìn)程是可并發(fā)執(zhí)行的程序在某個(gè)數(shù)據(jù)集合上的一次計(jì)算活動(dòng)，也是操作系統(tǒng)進(jìn)行資源分配和保護(hù)的基本單位。 進(jìn)程是一個(gè)既能用來共享資源，又能描述程序并發(fā)執(zhí)行過程的系統(tǒng)基本單位。 進(jìn)程是一種支持程序執(zhí)行的系統(tǒng)機(jī)制。l原因1-刻畫程序的并發(fā)性。l程序是并發(fā)執(zhí)行的，即不是連續(xù)而是走走停停的。程序的并發(fā)執(zhí)行引起資源共享和競(jìng)爭(zhēng)問題，執(zhí)行的程序不再處在封閉環(huán)境中。l“程序”自身只是計(jì)算任務(wù)的指令和數(shù)據(jù)的描述，是靜態(tài)概念無法刻畫程序的并發(fā)

26、特性，系統(tǒng)需要尋找一個(gè)能描述程序動(dòng)態(tài)執(zhí)行過程的概念，這就是進(jìn)程。l原因2-解決資源的共享性。l “可再用” 程序； “可再入” 程序； “可再入”程序具有的性質(zhì)。 運(yùn)行態(tài)就緒態(tài)等待態(tài)被調(diào)度運(yùn)行時(shí)間片用完出現(xiàn)等待事件等待事件結(jié)束運(yùn)行態(tài)就緒態(tài)等待態(tài)選中落選出現(xiàn)等待事件等待事件結(jié)束新建態(tài)終止態(tài) 進(jìn)程為什么要有“掛起”狀態(tài)? 為了讓某些進(jìn)程暫時(shí)不參與低級(jí)調(diào)度，釋放它占有的資源，以平滑系統(tǒng)負(fù)荷的目的而需引入掛起態(tài)； 進(jìn)程掛起的原因 ? 引起進(jìn)程掛起的原因多種多樣。 掛起等待事件結(jié)束出現(xiàn)等待事件解除掛起掛起落選選中運(yùn)行態(tài)就緒態(tài)等待事件結(jié)束終止態(tài)新建態(tài)掛起就緒態(tài)解除掛起掛起掛起等待態(tài)等待態(tài)提交提交 該進(jìn)程不

27、能立即被執(zhí)行。 掛起進(jìn)程可能會(huì)等待事件，但所等待事件是獨(dú)立于掛起條件的，事件結(jié)束并不能導(dǎo)致進(jìn)程具備執(zhí)行條件。 進(jìn)程進(jìn)入掛起狀態(tài)是由于操作系統(tǒng)、父進(jìn)程或進(jìn)程本身阻止它的運(yùn)行。 結(jié)束進(jìn)程掛起狀態(tài)的命令只能通過操作系統(tǒng)或父進(jìn)程發(fā)出。2.3.3 進(jìn)程描述和組成(1) 1.進(jìn)程映象 進(jìn)程控制塊 進(jìn)程程序塊 進(jìn)程核心棧 進(jìn)程數(shù)據(jù)塊 進(jìn)程描述和組成(2) 操作系統(tǒng)中把進(jìn)程物理實(shí)體和支持進(jìn)程運(yùn)行的環(huán)境合稱為進(jìn)程上下文。 當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理器時(shí)，新老進(jìn)程隨之發(fā)生上下文切換。進(jìn)程的運(yùn)行被認(rèn)為是在上下文中執(zhí)行。 進(jìn)程描述和組成(3)進(jìn)程上下文組成用戶級(jí)上下文：系統(tǒng)級(jí)上下文：寄存器上下文：進(jìn)程描述和組成(4)L

28、inux進(jìn)程上下文組成 Linux系統(tǒng)用戶級(jí)上下文包括：text、data、shared memory和user stack等。 Linux系統(tǒng)寄存器上下文包括：general register、pragram counter、EFLAGS、ESP等。 Linux系統(tǒng)系統(tǒng)級(jí)上下文包括：t a s k _ s t r u c t 、 m m _ s t r u c t 、vm_area_struct、pgd、pmd、pte和kernel stack等。l進(jìn)程控制塊P C B ，是操作系統(tǒng)用于記錄和刻劃進(jìn)程狀態(tài)及有關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。也是操作系統(tǒng)掌握進(jìn)程的唯一資料結(jié)構(gòu)，它包括進(jìn)程執(zhí)行時(shí)的情況，以及進(jìn)

29、程讓出處理器后所處的狀態(tài)、斷點(diǎn)等信息。 l進(jìn)程控制塊包含三類信息 標(biāo)識(shí)信息 現(xiàn)場(chǎng)信息 控制信息l處于同一狀態(tài)的所有PCB鏈接在一起的數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程隊(duì)列。 l同一狀態(tài)進(jìn)程的PCB既可按先來先到的原則排成隊(duì)列;也可按優(yōu)先數(shù)或其它原則排隊(duì)。l通用隊(duì)列組織方式： 線性方式、 鏈接方式 索引方式。l進(jìn)程入隊(duì)和出隊(duì) PCB表 PCB1 0PCB2 5PCB3 0PCB4 0 PCB5 0PCB6 4運(yùn)行隊(duì)列指針 就緒隊(duì)列指針 等待隊(duì)列1指針 等待隊(duì)列2指針 PCBn 7 PCB7 0 空閑進(jìn)程隊(duì)列指針 鏈接方式運(yùn)行隊(duì)列指針 就緒表指針 等待表1指針 索引方式 PCB表 PCB1 PCB2 PCB3 PC

30、B4 PCB5 PCB6 PCBn 空閑表指針 就緒索引表 等待索引表1 等待表2指針2.3.4 進(jìn)程上下文切換與處理器狀態(tài)轉(zhuǎn)換 進(jìn)程切換是讓處于運(yùn)行態(tài)的進(jìn)程中斷運(yùn)行，讓出處理器，這時(shí)要做一次進(jìn)程上下文切換、即保存老進(jìn)程的上下文而裝入被保護(hù)了的新進(jìn)程的上下文，以便新進(jìn)程運(yùn)行。進(jìn)程上下文切換的步驟 保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息 修改被中斷進(jìn)程的進(jìn)程控制塊有關(guān)信息，如進(jìn)程狀態(tài)等 把被中斷進(jìn)程的PSW加入有關(guān)隊(duì)列 選擇下一個(gè)占有處理器運(yùn)行的進(jìn)程 修改被選中進(jìn)程的PSW的有關(guān)信息 根據(jù)被選中進(jìn)程設(shè)置操作系統(tǒng)用到的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)信息 根據(jù)被選中進(jìn)程恢復(fù)處理器現(xiàn)場(chǎng) 請(qǐng)求調(diào)度的事件發(fā)生后，就會(huì)運(yùn)行低級(jí)

31、調(diào)度程序，低級(jí)調(diào)度程序選中新的就緒進(jìn)程后，就會(huì)進(jìn)行上下文切換。實(shí)際上，由于種種原因，調(diào)度和切換并不一定能一氣呵成。 通常的做法是，由內(nèi)核置上請(qǐng)求調(diào)度標(biāo)志，延遲到上述工作完成后再進(jìn)行調(diào)度和進(jìn)程上下文切換， Linux進(jìn)程調(diào)度標(biāo)志位need-resched。 V.版中，被移至thread_info 結(jié)構(gòu)體中，用標(biāo)志TIF_NEED_RESCHED 表示 。Linux調(diào)度時(shí)機(jī)(1) (1)主動(dòng)調(diào)度:指調(diào)用schedule( )函數(shù)來釋放CPU,引起新一輪調(diào)度，通常發(fā)生在當(dāng)前進(jìn)程狀態(tài)被改變,如:執(zhí)行了read（）、write( )、exit（ ）等系統(tǒng)調(diào)用，導(dǎo)致進(jìn)程終止、進(jìn)程阻塞等。Linux調(diào)度時(shí)機(jī)

32、(2) (2)被動(dòng)調(diào)度:指發(fā)生了引起調(diào)度的條件, 這時(shí)僅置進(jìn)程TIF_NEED_RESCHED調(diào)度標(biāo)志。調(diào)度標(biāo)志設(shè)置有以下情況： 1) 時(shí)鐘中斷中調(diào)用函數(shù)scheduler_tick()，查看當(dāng)前進(jìn)程的時(shí)間片是否耗盡，如果是，則設(shè)置重調(diào)度標(biāo)志； 2) 函數(shù)try_to_wake_up( )將阻塞的進(jìn)程被喚醒，把它加入運(yùn)行隊(duì)列時(shí)，如果其優(yōu)先級(jí)比當(dāng)前正在運(yùn)行進(jìn)程的優(yōu)先級(jí)高，設(shè)置重調(diào)度標(biāo)志。Linux調(diào)度時(shí)機(jī)(3) 3)設(shè)置應(yīng)用進(jìn)程優(yōu)先級(jí)參數(shù)nice值、創(chuàng)建新進(jìn)程、SMP負(fù)載均衡時(shí)都可能使高優(yōu)先級(jí)進(jìn)程進(jìn)入就緒狀態(tài)，也可能設(shè)置重調(diào)度標(biāo)志； 4)執(zhí)行sched_setscheduler( )（設(shè)置調(diào)度策

33、略）、sched_yield( 暫時(shí)讓出處理器)、pause( )（暫停）等系統(tǒng)調(diào)用，均要設(shè)置重調(diào)度標(biāo)志。處理器狀態(tài)轉(zhuǎn)換 當(dāng)中斷/系統(tǒng) 調(diào)用發(fā)生時(shí)，暫時(shí)中斷正在執(zhí)行的用戶進(jìn)程，把進(jìn)程從用戶狀態(tài)轉(zhuǎn)換到內(nèi)核狀態(tài)，去執(zhí)行操作系統(tǒng)服務(wù)程序以獲得服務(wù)，這就是一次狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換， 內(nèi)核在被中斷了的進(jìn)程的上下文中對(duì)這個(gè)中斷事件作處理，即使該中斷可能不是此進(jìn)程引起的。處理器狀態(tài)轉(zhuǎn)換步驟1)保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息；2)處理器從用戶態(tài)轉(zhuǎn)換到核心態(tài)，以便執(zhí)行服務(wù)程序或中斷處理程序；3)如果處理中斷，可根據(jù)規(guī)定的中斷級(jí)設(shè)置中斷屏蔽位；4)根據(jù)系統(tǒng)調(diào)用號(hào)或中斷號(hào)，從系統(tǒng)調(diào)用表或中斷入口表找到服務(wù)程序或中斷處理

34、程序地址。l用戶空間中，處于進(jìn)程上下文，用戶進(jìn)程在運(yùn)行，使用用戶棧。l內(nèi)核空間中，處于進(jìn)程上下文，內(nèi)核代表某進(jìn)程在運(yùn)行，使用核心棧。l內(nèi)核空間中，處于中斷上下文，與任何進(jìn)程無關(guān)，中斷服務(wù)程序正在處理特定中斷，Intel x86未提供中斷棧，借用核心棧。l內(nèi)核空間中，內(nèi)核線程(無用戶地址空間的進(jìn)程)運(yùn)行于內(nèi)核態(tài)。 核心態(tài)運(yùn)行系統(tǒng)調(diào)用或中斷(隱含狀態(tài)轉(zhuǎn)換)狀態(tài)轉(zhuǎn)換用戶態(tài)運(yùn)行等待狀態(tài)就緒狀態(tài)等待喚醒調(diào)度進(jìn)程中斷、中斷返回允許的上下文切換切換lLinux把內(nèi)核空間中運(yùn)行的程序稱為任務(wù)，而在用戶空間中運(yùn)行的程序稱為進(jìn)程。l系統(tǒng)中存在兩種進(jìn)程(任務(wù))：系統(tǒng)進(jìn)程(任務(wù))和用戶進(jìn)程(任務(wù))，實(shí)質(zhì)上是指一個(gè)進(jìn)程

35、(任務(wù))的兩個(gè)側(cè)面，。l兩個(gè)進(jìn)程(任務(wù))所執(zhí)行的程序不同，映射到不同物理地址空間、使用不同的堆棧。l處理器管理的一個(gè)主要工作是對(duì)進(jìn)程的控制，包括：創(chuàng)建進(jìn)程、阻塞進(jìn)程、喚醒進(jìn)程、掛起進(jìn)程、激活進(jìn)程、終止進(jìn)程和撤銷進(jìn)程等。這些控制和管理功能由操作系統(tǒng)中的原語實(shí)現(xiàn)。l原語是在管態(tài)下執(zhí)行、完成系統(tǒng)特定功能的過程。l原語和機(jī)器指令類似，其特點(diǎn)是執(zhí)行過程中不允許被中斷，是一個(gè)不可分割的基本單位，原語的執(zhí)行是順序的而不可能是并發(fā)的。l進(jìn)程創(chuàng)建l進(jìn)程撤銷l進(jìn)程阻塞l進(jìn)程喚醒l進(jìn)程掛起l進(jìn)程激活l步1在進(jìn)程列表中增加一項(xiàng)，從PCB池中申請(qǐng)一個(gè)空閑PCB，為新進(jìn)程分配惟一的進(jìn)程標(biāo)識(shí)符；l步2為新進(jìn)程的進(jìn)程映像分配

36、地址空間，以便容納進(jìn)程實(shí)體。進(jìn)程管理程序確定加載到進(jìn)程地址空間中的程序；l步3為新進(jìn)程分配除主存空間外的其他各種所需資源；l步4初始化PCB，如進(jìn)程標(biāo)識(shí)符、處理器初始狀態(tài)、進(jìn)程優(yōu)先級(jí)等；l步5把新進(jìn)程狀態(tài)置為就緒態(tài)，并移入就緒進(jìn)程隊(duì)列；l步6通知操作系統(tǒng)的某些模塊，如記賬程序、性能監(jiān)控程序。lfork( )-父子進(jìn)程是獨(dú)立的進(jìn)程 lclone( ) -父子進(jìn)程允許共享資源lvfork( )-子進(jìn)程租用父進(jìn)程地址空間 l步1根據(jù)撤銷進(jìn)程標(biāo)識(shí)號(hào)，從相應(yīng)隊(duì)列中找到并移出它；l步2將該進(jìn)程擁有的資源歸還給父進(jìn)程或操作系統(tǒng)；l步3若該進(jìn)程擁有子進(jìn)程，先撤銷它的所有子進(jìn)程，以防它們脫離控制；l步4回收PC

37、B，并歸還到PCB池。 進(jìn)程阻塞步驟：l步1停止進(jìn)程執(zhí)行，保存現(xiàn)場(chǎng)信息到PCB；l步2修改進(jìn)程PCB有關(guān)內(nèi)容，如進(jìn)程狀態(tài)由運(yùn)行態(tài)改為等待態(tài)等，并把修改狀態(tài)后的進(jìn)程移入相應(yīng)事件的等待隊(duì)列中；l步3轉(zhuǎn)入進(jìn)程調(diào)度程序去調(diào)度其他進(jìn)程運(yùn)行。 進(jìn)程喚醒步驟：l步1從相應(yīng)的等待隊(duì)列中移出進(jìn)程；l步2修改進(jìn)程PCB的有關(guān)信息，如進(jìn)程狀態(tài)改為就緒態(tài)，并移入就緒隊(duì)列；l步3若被喚醒進(jìn)程比當(dāng)前運(yùn)行進(jìn)程優(yōu)先級(jí)高，重新設(shè)置調(diào)度標(biāo)志。2.4.1 引入多線程的動(dòng)機(jī)2.4.2 多線程環(huán)境中的進(jìn)程和線程2.4.3 線程的實(shí)現(xiàn) 2.4.1 引入多線程的動(dòng)機(jī) 單線程(結(jié)構(gòu))進(jìn)程（Single Threaded Process） 多

38、線程（結(jié)構(gòu)）進(jìn)程（Multiple Threaded process） 多線程結(jié)構(gòu)進(jìn)程 進(jìn)程 進(jìn)程PCB資源線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程n控制塊用戶棧核心棧存儲(chǔ)區(qū)存儲(chǔ)空間全局?jǐn)?shù)據(jù)程序代碼線程1線程1線程控制塊線程2線程1線程控制塊用戶棧核心棧線程i線程n 進(jìn)程是操作系統(tǒng)中除處理器外進(jìn)行的資源分配和保護(hù)的基本單位。 它有獨(dú)立的虛擬地址空間，容納進(jìn)程映像(如與進(jìn)程關(guān)聯(lián)的程序與數(shù)據(jù))，并以進(jìn)程為單位對(duì)各種資源實(shí)施保護(hù)，如受保護(hù)地訪問處理器、文件、外部設(shè)備及其他進(jìn)程(進(jìn)程間通信)。 線程線程是操作系統(tǒng)進(jìn)程中能夠獨(dú)立執(zhí)行的實(shí)體（控制流），是處理器調(diào)度和分派的基本單位。線程是進(jìn)程的組成

39、部分，每個(gè)進(jìn)程內(nèi)允許包含多個(gè)并發(fā)執(zhí)行的實(shí)體（控制流），這就是多線程。l（）線程唯一標(biāo)識(shí)符及線程狀態(tài)信息(運(yùn)行態(tài)、就緒態(tài)、阻塞態(tài)和終止態(tài))；l（）線程是一條執(zhí)行路徑，有獨(dú)立的程序計(jì)數(shù)器；未運(yùn)行時(shí)保護(hù)線程上下文。l（）線程有執(zhí)行棧和存放局部變量的私用存儲(chǔ)空間。l（4 ）可訪問所屬進(jìn)程的內(nèi)存和資源，并與該進(jìn)程中的其他線程共享這些資源。 線程運(yùn)行在進(jìn)程的上下文中,并使用進(jìn)程的資源和環(huán)境。 系統(tǒng)調(diào)度的基本單位是線程而不是進(jìn)程,每當(dāng)創(chuàng)建一個(gè)進(jìn)程時(shí)，至少要同時(shí)為該進(jìn)程創(chuàng)建一個(gè)線程。 Linux線程做法不一樣。l線程狀態(tài)有：運(yùn)行、就緒、等待和終止，狀態(tài)轉(zhuǎn)換也類似于進(jìn)程。l掛起狀態(tài)對(duì)線程是沒有意義，如果進(jìn)程掛起

40、后被對(duì)換出主存，則它的所有線程因共享進(jìn)程的地址空間，也必須全部對(duì)換出去。 進(jìn)程中線程多種組織方式： 第一種是調(diào)度員工作者模式 第二種是組模式 第三種是流水線模式 多線程技術(shù)的應(yīng)用 前臺(tái)和后臺(tái)工作 C/S應(yīng)用模式 異步處理 加快執(zhí)行速度。 設(shè)計(jì)用戶接口。2.4.3 線程的實(shí)現(xiàn)從實(shí)現(xiàn)角度看，線程分成:用戶級(jí)線程ULT(如Java ,Informix)。內(nèi)核級(jí)線程KLT(如OS/2)。混合式線程(如Solaris)。各種線程實(shí)現(xiàn)方式的優(yōu)點(diǎn)和缺點(diǎn)。 線程調(diào)度(1)當(dāng)若干進(jìn)程都有多個(gè)線程時(shí)，就存在兩個(gè)層次的并行：進(jìn)程和線程。操作系統(tǒng)調(diào)度程序需要根據(jù)是用戶級(jí)線程還是內(nèi)核級(jí)線程來決定對(duì)進(jìn)程和線程的調(diào)度方法。

41、(2)用戶級(jí)線程的調(diào)度：(3)內(nèi)核級(jí)線程的調(diào)度；(4)用戶級(jí)線程和內(nèi)核級(jí)線程調(diào)度之間的差別：l進(jìn)程描述符task_struct中包含：進(jìn)程標(biāo)識(shí)、進(jìn)程狀態(tài)、鏈接信息、環(huán)境信息、優(yōu)先級(jí)信息、調(diào)度信息、通信信息、文件信息、虛存空間信息、信號(hào)處理信息、家族信息等。lLinux中認(rèn)為線程就是共享地址空間及其他資源的進(jìn)程，故并沒有單獨(dú)為線程定義數(shù)據(jù)結(jié)構(gòu)，有一套在用戶模式下運(yùn)行的線程庫-pthread，但每個(gè)線程都擁有惟一隸屬于自己的task_struct。 00 x080480000 x400000000 xc0000000內(nèi)核虛存用戶棧(運(yùn)行時(shí)創(chuàng)建)共享庫主存映象區(qū)運(yùn)行時(shí)堆空間堆(malloc創(chuàng)建)讀/

42、寫段只讀段從可執(zhí)行文件加載esp用戶代碼不可見未 用brk進(jìn)程核心棧棧指針espcurrenttask_struct *thread_info;棧頂thred_info thred_info *task; 包含：l進(jìn)程描述符task_struct指針、l當(dāng)前CPU號(hào)、l底層標(biāo)志、l線程同步標(biāo)志、l內(nèi)核搶占計(jì)數(shù)器等。 增加用于調(diào)度的新成員，主要有：l動(dòng)態(tài)優(yōu)先級(jí)priol靜態(tài)優(yōu)先級(jí)static_priol正常優(yōu)先級(jí)normal_priol優(yōu)先級(jí)數(shù)組prio_arrayl進(jìn)程平均等待時(shí)間sleep_avgl負(fù)載平衡權(quán)重load_weight等(1)進(jìn)程描述符分配過程(2)進(jìn)程描述符刪除過程(1)進(jìn)程

43、鏈表：反映進(jìn)程創(chuàng)建順序及其親屬關(guān)系。(2)哈希鏈表：內(nèi)核快速按pid查找進(jìn)程。(3)就緒鏈表：進(jìn)程就緒隊(duì)列或運(yùn)行隊(duì)列。(4)等待鏈表：進(jìn)程各種等待隊(duì)列 。lTASK_RUNNINGlTASK_INTERRUPTIBLElTASK_UNINTERRUPTIBLElTASK_ZOMBIElTASK_STOPPEDlTASK_SWAPPING 等待狀態(tài)current，擁有CPU運(yùn)行TASK_ZOMBLETASK_UNINTERRUPTIBLETASK_INTERRUPTIBLETASK_STOPPED創(chuàng)建進(jìn)程sys_exit()do_exit()sleep_on ()_down()wait_on()

44、interruptible_sleep_on()interruptible_sleep_on_timeout()_down_interruptble()do_fork()wake_up()wake_up_process()wake_up_interruptible()_up()wake_up()wake_up_process()_up()syscall_trace()do_signal()SIG_KILL|SIG_CONTwake_up_process()TASK_RUNNING(1) 創(chuàng)建進(jìn)程1) fork( )-創(chuàng)建一般進(jìn)程。2) vfork( )-創(chuàng)建完成特定任務(wù)的子進(jìn)程。3) clon

45、e（）-創(chuàng)建線程。4) 創(chuàng)建函數(shù)的實(shí)現(xiàn)。#include stdio.h void main(int argc,char *argv ) pid_t pid; pid=fork( ); /*創(chuàng)建子進(jìn)程*/ if(pid0) /*創(chuàng)建出錯(cuò)*/ fprint(stderr,“fork failed”); exit(-1); else if(pid=0) /*子進(jìn)程*/ execlp(“/bin/ls”,“l(fā)s”,NULL); else wait(NULL); /* 父進(jìn)程等待 子進(jìn)程 完成*/ printf(“child complete”) exit(0); vfork( )函數(shù)創(chuàng)建子進(jìn)程后，父

46、進(jìn)程被阻塞，直到子進(jìn)程執(zhí)行exec( )或exit( )。允許子進(jìn)程借用父進(jìn)程的地址空間，執(zhí)行結(jié)束后，歸還地址空間并喚醒父進(jìn)程，以減少不必要的開銷。 在Linux系統(tǒng)中，線程被認(rèn)為是一個(gè)與其他進(jìn)程共享資源的進(jìn)程，故被當(dāng)作進(jìn)程來實(shí)現(xiàn)，每個(gè)線程也用task_struct結(jié)構(gòu)體描述。在Linux系統(tǒng)中，線程僅僅是一種進(jìn)程間共享資源的方法。 clone（）用來創(chuàng)建線程。共享標(biāo)志：lCLONE_VM：父子進(jìn)程共享進(jìn)程空間。l CLONE_FS：父子進(jìn)程共享文件系統(tǒng)信息。l CLONE_FILES：父子進(jìn)程共享打開的文件。l CLONE_SIGCHLD：子進(jìn)程終結(jié)或者暫停時(shí)給父進(jìn)程發(fā)信號(hào)。l CLONE_

47、SIGHAND：父子進(jìn)程共享信號(hào)處理函數(shù)。l CLONE_PID：父子進(jìn)程共享進(jìn)程標(biāo)識(shí)符。l CLONE_VFORK：父進(jìn)程在子進(jìn)程釋放空間時(shí)被喚醒。 為子進(jìn)程分配pid。 創(chuàng)建task_struct結(jié)構(gòu)。 分配thread_info結(jié)構(gòu)和核心棧。 復(fù)制父進(jìn)程的task_struct信息和thread_info信息。 分配和初始化進(jìn)程記賬信息。 根據(jù)標(biāo)志復(fù)制并繼承父進(jìn)程的信號(hào)量、文件、信號(hào)和進(jìn)程地址空間和名字空間等信息。 初始化核心棧、狀態(tài)設(shè)置為TASK_RUNNING，并將父進(jìn)程時(shí)間片余額的一半分給它。 將子進(jìn)程插入雙向鏈表哈希鏈表 。 如果clone_flags包含CLONE_STOPPE

48、D標(biāo)志，把子進(jìn)程狀態(tài)改為TASK_STOPPED；否則調(diào)用_activate_task()將子進(jìn)程加入運(yùn)行隊(duì)列。 如果clone_flags包含CLONE_VFORK 標(biāo)志，把父進(jìn)程設(shè)置為阻塞狀態(tài)直到子進(jìn)程釋放進(jìn)程地址空間。 設(shè)置標(biāo)志。需要時(shí)從某些隊(duì)列中移出進(jìn)程。 調(diào)用_exit_mm( )、_exit_files( )、_exit_fs( )、exit_sem( )、exit_sighand( )、exit_namespace( )、exit_thread( )釋放進(jìn)程占用的各種資源。釋放資源時(shí)，先將共享計(jì)數(shù)器減1，若不為0表明有其他進(jìn)程在使用該資源，此時(shí)直接返回。否則才真正釋放資源。 設(shè)置

49、進(jìn)程退出碼，處理進(jìn)程與父進(jìn)程和子進(jìn)程的關(guān)系。在該函數(shù)中，置狀態(tài)為TASK_ZOMBIE，使其成為僵死進(jìn)程。 調(diào)用schedule( )函數(shù)調(diào)度并切換到其他進(jìn)程。 內(nèi)核線程運(yùn)行于內(nèi)核態(tài)且只訪問內(nèi)核空間中的信息，既沒有獨(dú)立地址空間，也不切換到用戶態(tài)。內(nèi)核線程和普通進(jìn)程一樣，可以被調(diào)度，可以被掄占。 內(nèi)核線程之間共享所有資源（除了各自擁有獨(dú)立的棧和硬件上下文之外），并由系統(tǒng)中的其他內(nèi)核線程通過內(nèi)核函數(shù)kernel_thread（）創(chuàng)建。 內(nèi)核線 程 周 期 性 地 被 喚 醒 和 調(diào) 用 ，用于實(shí)現(xiàn)系統(tǒng)后臺(tái)操作，如頁面對(duì)換、刷新磁盤緩存、網(wǎng)絡(luò)連接等系統(tǒng)工作 。 kswapd( )和ksoftirqd

50、( )等都是內(nèi)核線程。2.7.1 處理機(jī)調(diào)度層次2.7.2 選擇調(diào)度算法的原則2.7.3 作業(yè)管理與調(diào)度2.7.4 低級(jí)調(diào)度功能和類型2.6.5 作業(yè)調(diào)度和低級(jí)調(diào)度算法p作業(yè)作業(yè)(Job)(Job)：作業(yè)是一個(gè)比程序更為廣泛的概念，它不僅作業(yè)是一個(gè)比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系系統(tǒng)根據(jù)該說明書來對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。p作業(yè)步作業(yè)步(Job Step)(

51、Job Step)：通常，在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都通常，在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才必須經(jīng)過若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)能得到結(jié)果，我們把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個(gè)作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入。例如：步的輸出作為下一個(gè)作業(yè)步的輸入。例如： p作業(yè)流：作業(yè)流：若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作在外存上，這便形

52、成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。成了處理作業(yè)流。： 為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個(gè)作為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，業(yè)設(shè)置了一個(gè)作業(yè)控制塊，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息：其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型(CPU (CPU 繁忙型、繁忙型、I/O I/O 繁忙型、批量型、終端型繁忙型、批量型

53、、終端型) )、作業(yè)狀態(tài)、調(diào)度信息、作業(yè)狀態(tài)、調(diào)度信息( (優(yōu)優(yōu)先級(jí)、作業(yè)已運(yùn)行時(shí)間先級(jí)、作業(yè)已運(yùn)行時(shí)間) )、資源需求、資源需求( (預(yù)計(jì)運(yùn)行時(shí)間、要求預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小、要求內(nèi)存大小、要求I/OI/O設(shè)備的類型和數(shù)量等設(shè)備的類型和數(shù)量等) )、進(jìn)入系統(tǒng)時(shí)間、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。情況等。在上述三種調(diào)度中，在上述三種調(diào)度中，進(jìn)程調(diào)度進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是系統(tǒng)中通常是1010100 ms100 ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱便進(jìn)行一次進(jìn)程調(diào)度

54、，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPUCPU時(shí)間，進(jìn)程調(diào)度時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。算法不宜太復(fù)雜。作業(yè)調(diào)度作業(yè)調(diào)度往往是發(fā)生在一個(gè)往往是發(fā)生在一個(gè)( (批批) )作業(yè)運(yùn)行作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)( (批批) )作業(yè)進(jìn)入內(nèi)存時(shí)，作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘一次，因此把它稱為長(zhǎng)故作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘一次，因此把它稱為長(zhǎng)程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。多的時(shí)間。中級(jí)調(diào)度中級(jí)調(diào)度的運(yùn)

55、行頻率基本上介于上述兩種調(diào)度之的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。間，因此把它稱為中程調(diào)度。 就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)1 1面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) (1) 周轉(zhuǎn)時(shí)間短。通常把周轉(zhuǎn)時(shí)間的長(zhǎng)短作為評(píng)價(jià)批處理周轉(zhuǎn)時(shí)間短。通常把周轉(zhuǎn)時(shí)間的長(zhǎng)短作為評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一。所系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一。所謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被提交給系統(tǒng)開始

56、，到作業(yè)完成為止的這段時(shí)間間隔止的這段時(shí)間間隔( (稱為作業(yè)周轉(zhuǎn)時(shí)間稱為作業(yè)周轉(zhuǎn)時(shí)間) )。它包括四部分時(shí)間：。它包括四部分時(shí)間：作業(yè)在外存后備隊(duì)列上等待作業(yè)在外存后備隊(duì)列上等待( (作業(yè)作業(yè)) )調(diào)度的時(shí)間，進(jìn)程在就緒調(diào)度的時(shí)間，進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在CPUCPU上執(zhí)行的時(shí)間，以及上執(zhí)行的時(shí)間，以及進(jìn)程等待進(jìn)程等待I/OI/O操作完成的時(shí)間。其中的后三項(xiàng)在一個(gè)作業(yè)的整操作完成的時(shí)間。其中的后三項(xiàng)在一個(gè)作業(yè)的整個(gè)處理過程中可能會(huì)發(fā)生多次。個(gè)處理過程中可能會(huì)發(fā)生多次。 niiTnT11作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間T T與系統(tǒng)為它提供服務(wù)的時(shí)間與

57、系統(tǒng)為它提供服務(wù)的時(shí)間TsTs之比，即之比，即W = T/TsW = T/Ts，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為：權(quán)周轉(zhuǎn)時(shí)間則可表示為： niiTTnW1s1(3) (3) 截止時(shí)間的保證。這是評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指截止時(shí)間的保證。這是評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則。所謂截止時(shí)間，標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則。所謂截止時(shí)間，是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保間。對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和

58、調(diào)度算法必須能保證這一點(diǎn)，否則將可能造成難以預(yù)料的后果。證這一點(diǎn)，否則將可能造成難以預(yù)料的后果。(4) (4) 優(yōu)先權(quán)準(zhǔn)則。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)優(yōu)先權(quán)準(zhǔn)則。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)度算法時(shí)，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能度算法時(shí)，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時(shí)處理。在要求較嚴(yán)格的場(chǎng)合，往往還須選擇搶占式得到及時(shí)處理。在要求較嚴(yán)格的場(chǎng)合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)處理。調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)處理。 2 2面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則這是為了滿足系統(tǒng)要求而應(yīng)遵循的一些準(zhǔn)則。其中，這是為了滿足系統(tǒng)要求而應(yīng)遵循的

59、一些準(zhǔn)則。其中，較重要的有以下幾點(diǎn)：較重要的有以下幾點(diǎn)：(1) (1) 系統(tǒng)吞吐量高。系統(tǒng)吞吐量高。算法評(píng)價(jià)算法評(píng)價(jià)時(shí)間片時(shí)間片高響應(yīng)高響應(yīng)高優(yōu)先權(quán)高優(yōu)先權(quán)1 1提供必要的信息提供必要的信息(1) (1) 就緒時(shí)間就緒時(shí)間：是一個(gè)任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的：是一個(gè)任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它也可能是預(yù)知的。也可能是預(yù)知的。 (2) (2) 開始截止時(shí)間和完成截止時(shí)間：開始截止時(shí)間和完成截止時(shí)間：對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知對(duì)于典型的實(shí)時(shí)應(yīng)用，只

60、須知道開始截止時(shí)間，或者知道完成截止時(shí)間。道開始截止時(shí)間，或者知道完成截止時(shí)間。(3) (3) 處理時(shí)間處理時(shí)間：這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。：這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。(4) (4) 資源要求資源要求：這是指任務(wù)執(zhí)行時(shí)所需的一組資源。：這是指任務(wù)執(zhí)行時(shí)所需的一組資源。(5) (5) 優(yōu)先級(jí)：優(yōu)先級(jí)：如果某任務(wù)的開始截止時(shí)間已經(jīng)錯(cuò)過，就會(huì)引起故障，如果某任務(wù)的開始截止時(shí)間已經(jīng)錯(cuò)過，就會(huì)引起故障，則應(yīng)為該任務(wù)賦予則應(yīng)為該任務(wù)賦予“絕對(duì)絕對(duì)”優(yōu)先級(jí)；如果開始截止時(shí)間的推遲對(duì)任務(wù)的繼優(yōu)先級(jí)；如果開始截止時(shí)間的推遲對(duì)任務(wù)的繼續(xù)運(yùn)行無重大影響，則可為該任務(wù)賦予續(xù)運(yùn)行無重