操作系統(tǒng) 課件 第3、4章 進(jìn)程線程模型、進(jìn)程線程調(diào)度

第3章進(jìn)程線程模型學(xué)習(xí)目標(biāo)<2

>掌握進(jìn)程的定義和組成要素掌握應(yīng)用進(jìn)程狀態(tài)轉(zhuǎn)換關(guān)系了解進(jìn)程地址空間掌握進(jìn)程創(chuàng)建、撤銷、阻塞和喚醒的機(jī)制理解進(jìn)程控制的原語與相關(guān)系統(tǒng)調(diào)用理解資源分配單位和調(diào)度執(zhí)行單位的區(qū)別掌握線程的組成要素理解線程和進(jìn)程的關(guān)系理解線程的不同實現(xiàn)方式了解PthreadAPI，并能運(yùn)用其開發(fā)多線程應(yīng)用了解協(xié)程的概念教師導(dǎo)讀<3

>進(jìn)程是操作系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位，本章內(nèi)容是理解如何創(chuàng)建并管理進(jìn)程的重要知識單元進(jìn)程的定義與構(gòu)成進(jìn)程的狀態(tài)模型與進(jìn)程隊列父子進(jìn)程的工作模式：fork/exec、wait線程的引入原因線程的組成及其與進(jìn)程的關(guān)系線程的三種實現(xiàn)方式及每種方式的優(yōu)缺點Pthread線程包的主要函數(shù)與使用方式3.1進(jìn)程基本概念3.2進(jìn)程控制3.3線程引入及基本概念3.4

線程的實現(xiàn)和實例目錄CONTENTSPART3.1進(jìn)程基本概念3.1.1進(jìn)程定義<6

>定義：進(jìn)程是具有一定獨立功能的程序在某個數(shù)據(jù)集合上的一次運(yùn)行活動，

是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位進(jìn)程分為系統(tǒng)進(jìn)程和用戶進(jìn)程兩類系統(tǒng)進(jìn)程執(zhí)行操作系統(tǒng)程序用戶進(jìn)程運(yùn)行用戶程序系統(tǒng)進(jìn)程的優(yōu)先級通常高于一般用戶進(jìn)程的優(yōu)先級進(jìn)程定義3.1.1進(jìn)程定義<7

>1.

進(jìn)程和程序的聯(lián)系程序是構(gòu)成進(jìn)程的組成部分之一進(jìn)程是由程序、數(shù)據(jù)和進(jìn)程控制塊（PCB）三部分組成的一個進(jìn)程的運(yùn)行目標(biāo)是執(zhí)行它所對應(yīng)的程序2.

進(jìn)程和程序的區(qū)別程序是靜態(tài)的，而進(jìn)程是動態(tài)的進(jìn)程是程序的一個執(zhí)行過程程序的存在是永久的，進(jìn)程存在生命周期，一個程序可以產(chǎn)生多個進(jìn)程進(jìn)程與程序的聯(lián)系和區(qū)別可再入程序<8

>一個能夠被多個用戶同時調(diào)用的程序稱作是“可再入”的程序可再入程序在執(zhí)行中不會修改自身的代碼一個程序不是任何條件下都可以產(chǎn)生多個進(jìn)程的一個能被多個用戶同時調(diào)用的程序，在執(zhí)行中自身不能改變3.1.1進(jìn)程定義進(jìn)程的特征<9

>進(jìn)程的兩個基本屬性：進(jìn)程是一個可擁有資源的獨立單位進(jìn)程同時又是一個可以獨立調(diào)度和分派的基本單位進(jìn)程具有以下特性：

并發(fā)性：一個進(jìn)程可以同其他進(jìn)程一道向前推進(jìn)2.動態(tài)性：進(jìn)程有其生命周期，且進(jìn)程的狀態(tài)是不斷變化的3.獨立性：一個進(jìn)程是一個相對完整的資源分配單位4.交往性：一個進(jìn)程在運(yùn)行過程中可能會與其他進(jìn)程發(fā)生直接的或間接的相互作用5.

異步性：每個進(jìn)程按照各自獨立的、不可預(yù)知的速度向前推進(jìn)6.

結(jié)構(gòu)性：一個進(jìn)程由程序、數(shù)據(jù)和進(jìn)程控制塊三部分組成3.1.1進(jìn)程定義<10

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換

1．三狀態(tài)進(jìn)程模型運(yùn)行中的進(jìn)程可以處于以下三種狀態(tài)之一：運(yùn)行、就緒、等待三狀態(tài)模型狀態(tài)定義：（1）運(yùn)行狀態(tài)（Running）

進(jìn)程已獲得CPU，并且在CPU上執(zhí)行的狀態(tài)（2）就緒狀態(tài)（Ready）

進(jìn)程已經(jīng)具備運(yùn)行條件，但沒有獲得CPU的狀態(tài)（3）阻塞狀態(tài)（Blocked）

進(jìn)程因等待某種事件發(fā)生而暫時不能運(yùn)行的狀態(tài)<11

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換三狀態(tài)模型的狀態(tài)轉(zhuǎn)換條件：（1）就緒→運(yùn)行

進(jìn)程調(diào)度程序把處理機(jī)

分配給某個就緒進(jìn)程（2）運(yùn)行→就緒

規(guī)定的運(yùn)行時間片用完（3）運(yùn)行→阻塞

運(yùn)行狀態(tài)的進(jìn)程等待其他資源（4）阻塞→就緒

阻塞進(jìn)程在其被阻塞的原因獲得時解除阻塞<12

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換2．五狀態(tài)進(jìn)程模型五狀態(tài)模型狀態(tài)定義：（1）運(yùn)行狀態(tài)（Running）：

進(jìn)程正在占用CPU資源（2）就緒狀態(tài)（Ready）：

進(jìn)程等待分配CPU資源（3）阻塞狀態(tài)（Blocked）：

進(jìn)程因等待I/O操作等條件而暫停運(yùn)行（4）創(chuàng)建狀態(tài)（New）：

進(jìn)程正在創(chuàng)建過程中，還不能運(yùn)行（5）結(jié)束狀態(tài)（Exit）：

進(jìn)程已結(jié)束運(yùn)行，

回收除進(jìn)程控制塊之外的其他資源，

讓其他進(jìn)程從進(jìn)程控制塊中收集有關(guān)信息<13

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換五狀態(tài)狀態(tài)轉(zhuǎn)換條件：（1）創(chuàng)建新進(jìn)程：進(jìn)入創(chuàng)建狀態(tài)（2）提交（Admit）：完成一個新進(jìn)程的創(chuàng)建過程，進(jìn)入就緒狀態(tài)（3）調(diào)度運(yùn)行（Dispatch）：進(jìn)入運(yùn)行狀態(tài)（4）釋放（Release）：進(jìn)程終止運(yùn)行，進(jìn)入退出狀態(tài)（5）超時（Timeout）：用完時間片，進(jìn)程暫停運(yùn)行，、從運(yùn)行狀態(tài)進(jìn)入就緒狀態(tài)（6）事件等待（EventWait）：進(jìn)程要求的事件未出現(xiàn)而進(jìn)入阻塞狀態(tài)（7）事件出現(xiàn)（EventOccurs）：進(jìn)程等待的事件出現(xiàn)，進(jìn)程從阻塞狀態(tài)進(jìn)入就緒狀態(tài)<14

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換3．七狀態(tài)進(jìn)程模型七狀態(tài)模型引入原因：五狀態(tài)進(jìn)程模型沒有區(qū)分進(jìn)程地址空間位于內(nèi)存還是外存低優(yōu)先級進(jìn)程對換至外存，這種做法可得到的好處：（1）提高處理機(jī)效率（2）可為運(yùn)行進(jìn)程提供足夠內(nèi)存（3）有利于調(diào)試<15

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換七狀態(tài)模型狀態(tài)定義：與五狀態(tài)進(jìn)程模型相比，增加了就緒掛起和阻塞掛起兩個狀態(tài)（1）阻塞掛起狀態(tài)（Blocked,suspend）：

進(jìn)程在外存并等待某事件的出現(xiàn)（2）就緒掛起狀態(tài)（Ready,suspend）：

進(jìn)程在外存，但只要進(jìn)入內(nèi)存，即可運(yùn)行3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換七狀態(tài)模型狀態(tài)轉(zhuǎn)換條件：（1）掛起（Suspend）：

進(jìn)程從內(nèi)存轉(zhuǎn)到外存

阻塞到阻塞掛起

就緒到就緒掛起

運(yùn)行到就緒掛起（2）激活（Activate）：

進(jìn)程從外存轉(zhuǎn)到內(nèi)存

就緒掛起到就緒

阻塞掛起到阻塞<16

>3.1.2進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換<17

>七狀態(tài)模型狀態(tài)轉(zhuǎn)換條件：（3）事件出現(xiàn)（EventOccurs）：

等待的事件出現(xiàn)

阻塞到就緒

阻塞掛起到就緒掛起（4）提交（Admit）：

完成創(chuàng)建過程

進(jìn)入就緒狀態(tài)或就緒掛起狀態(tài)3.1.3進(jìn)程控制塊進(jìn)程控制塊（PCB：ProcessControlBlock）：描述進(jìn)程的基本情況以及進(jìn)程的運(yùn)行變化過程PCB是進(jìn)程存在的惟一標(biāo)志當(dāng)系統(tǒng)創(chuàng)建一個進(jìn)程時，為進(jìn)程設(shè)置一個PCB，再利用PCB對進(jìn)程進(jìn)行控制和管理撤消進(jìn)程時，系統(tǒng)收回它的PCB，進(jìn)程也隨之消亡<18

>3.1.3進(jìn)程控制塊PCB的內(nèi)容PCB的內(nèi)容可以分成調(diào)度信息和現(xiàn)場信息兩大部分調(diào)度信息：供進(jìn)程調(diào)度時使用，描述進(jìn)程當(dāng)前所處的狀況進(jìn)程名、進(jìn)程號、存儲信息、優(yōu)先級、當(dāng)前狀態(tài)、資源清單、“家族”關(guān)系、消息隊列指針、進(jìn)程隊列指針和當(dāng)前打開文件等現(xiàn)場信息：刻畫進(jìn)程的運(yùn)行情況程序狀態(tài)字、時鐘、界地址寄存器等一旦中斷進(jìn)程的運(yùn)行，必須把中斷時刻的內(nèi)容記入進(jìn)程控制塊的現(xiàn)場信息<19

>3.1.3進(jìn)程控制塊

進(jìn)程的組成進(jìn)程由程序、數(shù)據(jù)和進(jìn)程控制塊三部分組成PCB存有進(jìn)程的地址信息程序描述了進(jìn)程要實現(xiàn)的功能數(shù)據(jù)是程序操作的對象<20

>3.1.3進(jìn)程控制塊3.

PCB組織（1）線性方式：

所有PCB不分狀態(tài)組織在一個線性表（稱PCB表）中優(yōu)點：簡單，且不需要額外的開銷缺點：需要掃描整個PCB表，

才能找到需要的PCB（2）索引方式：相同狀態(tài)的進(jìn)程，分別設(shè)置PCB索引表<21

>3.1.3進(jìn)程控制塊（3）鏈接方式：對于具有相同狀態(tài)進(jìn)程的PCB，通過PCB中的鏈接字構(gòu)成一個隊列鏈接字指出本隊列下一PCB在PCB表中的編號（或地址）編號為0表示隊尾隊首由內(nèi)存固定單元中相應(yīng)的隊列指針指示<22

>3.1.3進(jìn)程控制塊

4.進(jìn)程的隊列（1）就緒隊列所有就緒狀態(tài)的進(jìn)程排在一個就緒隊列中（2）等待隊列對每一種等待事件組織一個隊列（3）運(yùn)行隊列在單CPU系統(tǒng)中，整個系統(tǒng)有一個運(yùn)行隊列<23

>3.1.3進(jìn)程控制塊5.

進(jìn)程隊列的組成單向鏈接：

同一隊列中的進(jìn)程，通過進(jìn)程控制塊中的隊列指針聯(lián)系起來

前一進(jìn)程的進(jìn)程控制塊中的指針值為它的下一個進(jìn)程的進(jìn)程控制塊的地址

隊列中最后一個進(jìn)程的進(jìn)程控制塊中的指針值置為“0”雙向鏈接：

設(shè)置兩個指針，前向指針和后向指針

分別指出它的前一個或后一個進(jìn)程的進(jìn)程控制塊地址

系統(tǒng)為每個隊列設(shè)置一個隊首指針，指出該隊列的第一個和最后一個進(jìn)程

的進(jìn)程控制塊地址，以便進(jìn)行雙向搜索<24

>背景-2：北京大學(xué)圖書館PART3.2進(jìn)程控制<26

>3.2.1進(jìn)程控制進(jìn)程控制：對進(jìn)程在整個生命周期中各種狀態(tài)之間的轉(zhuǎn)換進(jìn)行有效的控制通過進(jìn)程控制原語來實現(xiàn)原語：

若干條指令所組成的一個指令序列，用來實現(xiàn)某個特定的操作功能

連續(xù)的，具有不可分割性，在執(zhí)行時也不可間斷

必須在管態(tài)下執(zhí)行，并且常駐內(nèi)存用于進(jìn)程控制的原語：創(chuàng)建進(jìn)程、撤消進(jìn)程、掛起進(jìn)程、激活進(jìn)程、阻塞進(jìn)程、喚醒進(jìn)程以及改變進(jìn)程優(yōu)先級等<27

>3.2.1進(jìn)程控制創(chuàng)建原語創(chuàng)建一個新的進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程建立進(jìn)程控制塊PCB2.

撤消原語撤消進(jìn)程的PCB撤消屬于該進(jìn)程的一切“子孫進(jìn)程”，釋放被撤消進(jìn)程所占用的全部資源

3.

阻塞原語進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)中斷CPU的執(zhí)行，把CPU的當(dāng)前狀態(tài)保存在PCB的現(xiàn)場信息中當(dāng)前狀態(tài)置為等待狀態(tài)，并把它插入到該事件的等待隊列中去

4.

喚醒原語等待狀態(tài)轉(zhuǎn)換為就緒狀態(tài)從等待隊列中撤出并插入到就緒隊列中排隊，等待調(diào)度執(zhí)行<28

>3.2.2Linux操作系統(tǒng)有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用在Linux操作系統(tǒng)中，常用的有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用有：fork，exec，wait，exit，getpid，sleep和nice等下表所示為這些系統(tǒng)調(diào)用的功能說明系統(tǒng)調(diào)用功

能fork創(chuàng)建一個子進(jìn)程getpid返回當(dāng)前進(jìn)程的PIDexec更換進(jìn)程映像，即根據(jù)指定的文件名找到可執(zhí)行文件，并用它來取代調(diào)用進(jìn)程的內(nèi)容exit終止調(diào)用的程序（用于程序運(yùn)行出錯）wait等待任何要僵死的子進(jìn)程sleep使進(jìn)程掛起指定的時間nice改變進(jìn)程的優(yōu)先級<29

>3.2.2Linux操作系統(tǒng)有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用【代碼示例-fork與exec】Linux系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程，以及各自分開活動的情況#include<unistd.h>#include<sys/types.h>#include<stdio.h>#include<sys/wait.h>#include<stdlib.h>intmain(intargc,char*argv[]){intpid;pid=fork();/*創(chuàng)建一個子進(jìn)程*/if(pid<0){/*出現(xiàn)錯誤。進(jìn)程ID號不可能小于0*/fprintf(stderr,"ForkFailed");/*輸出出錯消息——ForkFailed*/exit(-1);/*程序終止，返回碼-1*/}<30

>3.2.2Linux操作系統(tǒng)有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用elseif(pid==0){/*下面是子進(jìn)程執(zhí)行*/execlp("/bin/ls","ls",NULL);/*執(zhí)行目錄/bin下面的ls命令*/}else{/*下面是父進(jìn)程執(zhí)行*/wait(NULL);/*父進(jìn)程等待子進(jìn)程完成*/printf("ChildComplete");/*輸出子進(jìn)程完成的信息*/exit(0);/*終止*/}}<31

>3.2.2Linux操作系統(tǒng)有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用【代碼示例-進(jìn)程相關(guān)操作】利用fork()創(chuàng)建子進(jìn)程，利用getpid()和getppid()分別獲得本進(jìn)程的PID和父進(jìn)程的PID，使用sleep()將相關(guān)進(jìn)程掛起幾秒/*proc1.c演示有關(guān)進(jìn)程操作*/#include<unistd.h>#include<sys/types.h>#include<stdio.h>#include<errno.h>#include<stdlib.h>#include<string.h>

intmain(intargc,char**argv){pid_tpid,old_ppid,new_ppid;pid_tchild,parent;<32

>3.2.2Linux操作系統(tǒng)有關(guān)進(jìn)程控制的系統(tǒng)調(diào)用parent=getpid(); if((child=fork())<0){fprintf(stderr,"%s:forkofchildfailed:%s\n",argv[0],strerror(errno));exit(1);} elseif(child==0){ /*此時子進(jìn)程被調(diào)度運(yùn)行*/old_ppid=getppid();sleep(2);new_ppid=getppid();}else{/*父進(jìn)程運(yùn)行*/sleep(1);exit(0);}/*下面僅子進(jìn)程運(yùn)行*/printf("Originalparent:%d\n",parent);printf("Child:%d\n",getpid());printf("Child'soldppid:%d\n",old_ppid);printf("Child'snewppid:%d\n",new_ppid);

exit(0);}程序運(yùn)行的結(jié)果如下：$./proc1Originalparent:2009Child:2010Child'soldppid:2009Child'snewppid:1需要注意的是，進(jìn)程是并發(fā)執(zhí)行的；當(dāng)子進(jìn)程被成功調(diào)度后，調(diào)度程序的返回值是0。如果父進(jìn)程先終止，則其子進(jìn)程的父進(jìn)程就被系統(tǒng)指定為init進(jìn)程（其PID為1）背景-3：西門華表線程引入及基本概念PART3.3<34

>3.3.1線程的引入為何需要線程？進(jìn)程活動存在時間和空間的資源開銷，數(shù)目不宜太多，切換頻率不宜過高使多個程序更好地并發(fā)執(zhí)行，盡量減少系統(tǒng)的開銷分離調(diào)度的基本單位和獨立分配資源的單位調(diào)度和分派的基本單位不負(fù)責(zé)分配資源擁有資源的基本單位，不頻繁地切換<35

>3.3.1線程的引入什么是線程?線程是進(jìn)程中的一個實體，是CPU調(diào)度和分派的基本單位只擁有少量在運(yùn)行中必不可少的資源同屬一個進(jìn)程的其他線程共享進(jìn)程所擁有的全部資源線程有就緒、等待和運(yùn)行三種基本狀態(tài)有的系統(tǒng)中線程還有終止?fàn)顟B(tài)等進(jìn)程執(zhí)行程序，就如同工人完成工作一個進(jìn)程內(nèi)的多個線程同時運(yùn)行，就如同多個工人共同完成一份工作<36

>3.3.1線程的引入2.線程的屬性（1）惟一的標(biāo)識符和一張線程描述表

線程描述表記錄了線程執(zhí)行的寄存器以及棧等現(xiàn)場狀態(tài)（2）不同的線程可以執(zhí)行相同的程序（3）同一個進(jìn)程中的各個線程共享該進(jìn)程的內(nèi)存地址空間（4）線程是處理器的獨立調(diào)度單位，多個線程是可以并發(fā)執(zhí)行的（5）線程在生命周期內(nèi)會經(jīng)歷等待狀態(tài)、就緒態(tài)和運(yùn)行態(tài)等各種狀態(tài)變化每個線程單獨占有CPU資源，只有在多核CPU上，多線程才可能并行執(zhí)行<37

>3.3.1線程的引入3．引入線程的好處（1）創(chuàng)建一個新線程花費(fèi)時間少

創(chuàng)建線程的速度比創(chuàng)建進(jìn)程的速度快，且系統(tǒng)的開銷也少（2）線程之間的切換花費(fèi)時間少（3）同一個進(jìn)程內(nèi)的線程共享內(nèi)存和文件，通信更簡便，信息傳送速度也快（4）線程能獨立執(zhí)行，充分利用和發(fā)揮處理器與外部設(shè)備并行工作能力<38

>3.3.2

線程的組成thread結(jié)構(gòu)，即線程控制塊，由以下四個基本部分組成：①一個唯一的線程標(biāo)識符②描述處理器工作情況的一組寄存器的內(nèi)容

如程序計數(shù)器、狀態(tài)寄存器、通用寄存器等③兩個棧指針

一個指向核心棧；另一個指向用戶棧④一個私有存儲區(qū)

用來存放現(xiàn)場保護(hù)信息和其他與該線程相關(guān)的統(tǒng)計信息等<39

>3.3.2

線程的組成一個進(jìn)程可以包含一個線程或多個線程當(dāng)一個進(jìn)程包含多個線程時，這些線程除各自私有少量資源以外，共享所屬進(jìn)程的全部資源<40

>3.3.3

線程與進(jìn)程的關(guān)系線程又稱為輕量級進(jìn)程或者進(jìn)程元傳統(tǒng)的進(jìn)程稱為重量級進(jìn)程通常一個進(jìn)程都有若干個線程調(diào)度傳統(tǒng)的操作系統(tǒng)中擁有資源的基本單位和獨立調(diào)度、分派的基本單位都是進(jìn)程引入線程的操作系統(tǒng)中線程作為調(diào)度和分派的基本單位，進(jìn)程作為資源擁有的基本單位<41

>3.3.3

線程與進(jìn)程的關(guān)系2.并發(fā)性引入線程的操作系統(tǒng)中不僅進(jìn)程之間可以并發(fā)執(zhí)行一個進(jìn)程中的多個線程之間也可以并發(fā)執(zhí)行擁有資源不論是傳統(tǒng)的操作系統(tǒng)，還有線程的操作系統(tǒng)進(jìn)程都是擁有資源的一個獨立單位<42

>3.3.3

線程與進(jìn)程的關(guān)系4.

系統(tǒng)開銷在創(chuàng)建或撤消進(jìn)程時，操作系統(tǒng)所付出的開銷將顯著地大于在創(chuàng)建或撤消線程時的開銷進(jìn)程切換的開銷遠(yuǎn)大于線程切換的開銷同一進(jìn)程中的多個線程具有相同的地址空間，同步和通信的實現(xiàn)比較容易<43

>3.3.3

線程與進(jìn)程的關(guān)系比較概念線程進(jìn)程基本功能調(diào)度的基本單位資源分配的基本單位系統(tǒng)開銷切換開銷小切換開銷大資源分配線程共享一個進(jìn)程下的資源進(jìn)程獨占資源通信方式共享內(nèi)存地址空間使用進(jìn)程通信的系統(tǒng)調(diào)用并發(fā)性更強(qiáng)更弱背景-4：未名湖PART3.4線程的實現(xiàn)和實例<45

>3.4.1

線程的實現(xiàn)方式1．用戶級線程、核心級線程和混合方式線程已在許多系統(tǒng)中實現(xiàn)，但實現(xiàn)的方式并不完全相同用戶級線程（User-LevelThreads），不依賴于內(nèi)核例如：數(shù)據(jù)庫系統(tǒng)中的線程核心級線程（Kernel-SupportedThreads)，依賴于內(nèi)核混合方式實現(xiàn)線程，即同時實現(xiàn)了以上兩種類型的線程<46

>3.4.1

線程的實現(xiàn)方式（1）用戶級線程實現(xiàn)方式創(chuàng)建、撤消和切換都不利用系統(tǒng)調(diào)用管理線程的工作全部由應(yīng)用程序完成每個進(jìn)程都有一個私有的線程表核心空間中有一個進(jìn)程表，記載系統(tǒng)中各個進(jìn)程的情況POSIXPthreadsMachC-threadsSolaris2UI-threads<47

>3.4.1

線程的實現(xiàn)方式（1）用戶級線程優(yōu)缺點

優(yōu)點：線程的切換速度快允許采用適合自己要求的不同調(diào)度算法可以運(yùn)行在任何操作系統(tǒng)上缺點：當(dāng)一個線程執(zhí)行系統(tǒng)調(diào)用時，在同一個進(jìn)程內(nèi)的所有線程都被阻塞多線程應(yīng)用程序不具有多處理器的優(yōu)點<48

>3.4.1

線程的實現(xiàn)方式（2）核心級線程實現(xiàn)方式創(chuàng)建、撤消和切換都由核心實現(xiàn)核心保留了一個線程控制塊，根據(jù)該控制塊感知線程的存在并對線程進(jìn)行控制線程表在核心空間中，記載系統(tǒng)中所有線程的情況核心空間中保存一個進(jìn)程表，記載系統(tǒng)所有進(jìn)程的信息核心進(jìn)行調(diào)度時以線程為基本單位<49

>3.4.1

線程的實現(xiàn)方式（2）核心級線程優(yōu)缺點優(yōu)點：核心可以同時調(diào)度同一進(jìn)程中的多個線程，真正實現(xiàn)并行操作如果一個進(jìn)程的某個線程阻塞了，核心可以調(diào)度同一個進(jìn)程中的另一個線程核心線程本身也可以是多線程的缺點：控制轉(zhuǎn)移開銷大應(yīng)用進(jìn)程無法影響線程的切換3.4.1

線程的實現(xiàn)方式（3）混合方式

用戶級線程和核心級線程兩種實現(xiàn)方式結(jié)合

同一個進(jìn)程內(nèi)的多個線程可在多個處理器上

并行運(yùn)行

阻塞式系統(tǒng)調(diào)用不必將整個進(jìn)程阻塞

線程創(chuàng)建在用戶空間完成

線程調(diào)度等在核心態(tài)完成<50

>3.4.1

線程的實現(xiàn)方式2．線程實現(xiàn)方式的比較（1）線程的調(diào)度與切換速度

用戶級線程的切換速度更加快（2）系統(tǒng)調(diào)用

用戶級線程調(diào)用一個系統(tǒng)調(diào)用時，把系統(tǒng)調(diào)用看作是整個進(jìn)程的行為

內(nèi)核支持線程，則調(diào)度是以線程為單位（3）線程執(zhí)行時間

用戶級線程，調(diào)度是以進(jìn)程為單位進(jìn)行的

核心級線程，調(diào)度是以線程為單位進(jìn)行的<51

>3.4.2

Pthread線程包多線程應(yīng)用程序用一組用戶級程序庫來編寫，將所有線程映射到一個單獨的內(nèi)核級進(jìn)程中其中最著名的是：Pthread（POSIXthread）庫Pthread線程共有特性：

一個標(biāo)識符

一組寄存器（包括程序計數(shù)器）

一組存儲在結(jié)構(gòu)中的屬性，包括棧大小、調(diào)度參數(shù)以及其它線程需要的項目下表中列舉了幾個主要的Pthread函數(shù)調(diào)用線程調(diào)用描述pthread_create()創(chuàng)建一個新線程pthread_join()等待一個特定的線程退出pthread_exit()結(jié)束調(diào)用的線程pthread_yield()釋放CPU來運(yùn)行另外一個線程pthread_attr_init()創(chuàng)建并初始化一個線程pthread_attr_destroy()刪除一個線程的屬性結(jié)構(gòu)<52

>3.4.2

Pthread線程包【代碼示例-Pthread庫的簡單應(yīng)用】#include<pthread.h>//引入pthread庫#include<stdio.h>#include<stdlib.h>#defineNUMBER_OF_THREADS10

void*print_hello_world(void*tid){/*本函數(shù)輸出線程的標(biāo)識符，然后退出。*/printf("HelloWorld.%d0\n",*(int*)tid);pthread_exit(NULL);}引入Pthread庫，并定義線程需要執(zhí)行的函數(shù)：當(dāng)創(chuàng)建一個線程時，它打印一條發(fā)布信息，然后退出<53

>3.4.2

Pthread線程包【代碼示例-Pthread庫的簡單應(yīng)用】這里主程序循環(huán)NUMBER_OF_THREADS次，每次創(chuàng)建一個新的線程如果線程創(chuàng)建失敗，會打印出一條錯誤信息后退出。在創(chuàng)建完所有線程之后，主程序退出這些不同信息交錯的順序是不確定的，并且可能在連續(xù)運(yùn)行程序的情況下發(fā)生變化<54

>intmain(intargc,char*argv[]){/*主程序創(chuàng)建10個線程，然后退出。*/pthread_tthreads[NUMBER_OF_THREADS];intstatus,i;

for(i=1;i<NUMBER_OF_THREADS;i++){printf("Mainhere.Creatingthread%d0\n",i); status=pthread_create(&threads[i],NULL, print_hello_world,(void*)&i);

if(status!=0){printf("pthread_createreturnederrorcode%d0\n",status);exit(-1);}}exit(0);3.4.3

協(xié)程提出原因：當(dāng)線程數(shù)量非常多的時候，系統(tǒng)線程會占用非常多的內(nèi)存空間過多的線程切換會占用大量的系統(tǒng)時間解決方法：協(xié)程機(jī)制協(xié)程是運(yùn)行在線程之上的輕量級線程當(dāng)一個協(xié)程執(zhí)行完成后，讓另一個協(xié)程運(yùn)行在當(dāng)前線程之上協(xié)程并沒有增加線程數(shù)量只是在線程的基礎(chǔ)之上通過分時復(fù)用的方式運(yùn)行多個協(xié)程協(xié)程的切換在用戶態(tài)完成切換的代價比線程從用戶態(tài)到內(nèi)核態(tài)的代價小很多<55

>第4章進(jìn)程線程調(diào)度4.1進(jìn)程調(diào)度的基本概念4.2進(jìn)程調(diào)度算法的設(shè)計思路4.3經(jīng)典進(jìn)程調(diào)度算法4.4其他進(jìn)程調(diào)度算法4.5操作系統(tǒng)調(diào)度算法實例4.6多處理器調(diào)度算法4.7實時調(diào)度算法

4.8習(xí)題目錄CONTENTSPART4.1進(jìn)程調(diào)度的基本概念4.1進(jìn)程調(diào)度的基本概念<59

>進(jìn)程調(diào)度即處理機(jī)調(diào)度。進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對CPU的競爭，按照一定的調(diào)度算法，使某一就緒進(jìn)程獲得CPU的控制權(quán)，轉(zhuǎn)換成運(yùn)行狀態(tài)。進(jìn)程調(diào)度也叫低級調(diào)度進(jìn)程調(diào)度程序是操作系統(tǒng)的真正核心，它直接負(fù)責(zé)CPU的分配。系統(tǒng)中所有進(jìn)程都是在CPU上運(yùn)行的，進(jìn)程調(diào)度程序就是它們的切換開關(guān)。4.1.1進(jìn)程調(diào)度的主要功能<60

>①保存現(xiàn)場②挑選進(jìn)程③恢復(fù)現(xiàn)場4.1.2進(jìn)程調(diào)度的時機(jī)<61

>①創(chuàng)建進(jìn)程②任務(wù)完成③等待資源④中斷發(fā)生⑤運(yùn)行到時4.1.3兩級調(diào)度模型<62

>兩級調(diào)度簡化隊列圖4.1.4三級調(diào)度模型<63

>三級調(diào)度簡化隊列示意圖背景-2：北京大學(xué)圖書館PART4.2進(jìn)程調(diào)度算法的設(shè)計思路4.2.1調(diào)度策略的選擇<65

>①設(shè)計目標(biāo)②公平性③均衡性④統(tǒng)籌兼顧⑤優(yōu)先級⑥開銷4.2.2性能評價標(biāo)準(zhǔn)<66

>①CPU利用率②吞吐量③周轉(zhuǎn)時間④就緒等待時間⑤響應(yīng)時間背景-3：西門華表經(jīng)典進(jìn)程調(diào)度算法PART4.34.3.1先來先服務(wù)法<68

>先來先服務(wù)（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）法是最簡單的一種調(diào)度算法對于作業(yè)調(diào)度來說，每次調(diào)度從后備作業(yè)隊列中選擇隊頭的一個或幾個作業(yè)，把它們調(diào)入內(nèi)存，分配相應(yīng)的資源，創(chuàng)建進(jìn)程，然后把進(jìn)程放入就緒隊列對于進(jìn)程調(diào)度算法來說，即每次調(diào)度從就緒隊列中選擇一個最先進(jìn)入該隊列的進(jìn)程，把CPU分給它，直至完成或者由于某些原因而阻塞，當(dāng)新一個進(jìn)程進(jìn)入就緒隊列時，它的PCB就鏈入就緒隊列的末尾。每次進(jìn)程調(diào)度時就把隊頭進(jìn)程從該隊列中摘下，分給它CPU，使它運(yùn)行4.3.1先來先服務(wù)法<69

>設(shè)有三個作業(yè)，編號分別為1、2、3，且分別對應(yīng)一個進(jìn)程。各作業(yè)依次到達(dá)，相差一個時間單位。如圖所示為采用FCFS方式調(diào)度時這三個作業(yè)的執(zhí)行順序，其中，*表示作業(yè)到達(dá)的時間，實線表示作業(yè)執(zhí)行過程。根據(jù)圖，可算出各作業(yè)的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間等。4.3.1先來先服務(wù)法<70

>FCFS調(diào)度算法的性能如表所示。FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。因為短作業(yè)運(yùn)行時間很短，如果讓它等待較長時間才得到服務(wù)，它的帶權(quán)周轉(zhuǎn)時間就會很長。另外，F(xiàn)CFS調(diào)度算法對CPU繁忙型作業(yè)（指需要大量CPU時間進(jìn)行計算的作業(yè)）較有利，而不利于I/O繁忙型作業(yè)（指需要頻繁請求I/O的作業(yè)）。FCFS調(diào)度算法容易實現(xiàn)，但它的效率較低。作業(yè)到達(dá)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間10240242412132427268.673232730289.33平均周轉(zhuǎn)時間=26平均帶權(quán)周轉(zhuǎn)時間=6.334.3.2時間片輪轉(zhuǎn)法<71

>時間片輪轉(zhuǎn)法（Round-Robin，RR）主要用于分時系統(tǒng)中的進(jìn)程調(diào)度。當(dāng)進(jìn)程用完分給它的時間片后，系統(tǒng)的計時器發(fā)出時鐘中斷，調(diào)度程序便停止該進(jìn)程的運(yùn)行，并把它放入就緒隊列的末尾；然后，把CPU分給就緒隊列的隊首進(jìn)程，同樣也讓它運(yùn)行一個時間片，如此往復(fù)4.3.2時間片輪轉(zhuǎn)法<72

>四個進(jìn)程運(yùn)行情況4.3.2時間片輪轉(zhuǎn)法<73

>時間片輪轉(zhuǎn)法（Round-Robin，RR）主要用于分時系統(tǒng)中的進(jìn)程調(diào)度。為實現(xiàn)輪轉(zhuǎn)調(diào)度，表RR法的性能指標(biāo)到達(dá)時間進(jìn)程名到達(dá)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間時間片q=1

A012026262.17B05117173.4C03211113.67D06320203.33平均周轉(zhuǎn)時間=18.5平均帶權(quán)周轉(zhuǎn)時間=3.14時間片q=4A012026262.17B05420204C03811113.67D061122223.67平均周轉(zhuǎn)時間=19.75平均帶權(quán)周轉(zhuǎn)時間=3.384.3.2時間片輪轉(zhuǎn)法<74

>時間片的大小對輪轉(zhuǎn)法的性能有很大影響：如果時間片太長，每個進(jìn)程都在這段時間內(nèi)運(yùn)行完畢，那么時間片輪轉(zhuǎn)法就退化為先來先服務(wù)算法。很顯然，對用戶的響應(yīng)時間必然加長；如果時間片太短，CPU在進(jìn)程間的切換工作就非常頻繁，從而導(dǎo)致系統(tǒng)開銷增加4.3.2時間片輪轉(zhuǎn)法<75

>時間片的長短通常由以下四個因素來確定：①系統(tǒng)的響應(yīng)時間②就緒隊列進(jìn)程的數(shù)目③進(jìn)程的轉(zhuǎn)換時間④CPU運(yùn)行指令速度4.3.3優(yōu)先級法<76

>利用優(yōu)先級調(diào)度算法進(jìn)行進(jìn)程調(diào)度時，是從就緒隊列中選出優(yōu)先級最高的進(jìn)程，把CPU分給它使用。如果在就緒隊列中出現(xiàn)優(yōu)先級更高的進(jìn)程時，怎么辦：①非搶占式優(yōu)先級法②搶占式優(yōu)先級法4.3.3優(yōu)先級法<77

>內(nèi)部決定優(yōu)先級是利用某些可度量的量來定義一個進(jìn)程的優(yōu)先級外部優(yōu)先級是按操作系統(tǒng)以外的標(biāo)準(zhǔn)設(shè)置的4.3.3優(yōu)先級法<78

>兩種確定進(jìn)程優(yōu)先級的方式：①靜態(tài)優(yōu)先級是在創(chuàng)建進(jìn)程時就確定下來的，而且在進(jìn)程的整個運(yùn)行期間保持不變②動態(tài)優(yōu)先級是隨著進(jìn)程的推進(jìn)而不斷改變的4.3.3優(yōu)先級法<79

>進(jìn)程運(yùn)行時間優(yōu)先數(shù)P1103P211P324P415P552一組進(jìn)程列表

采用優(yōu)先級法時五個進(jìn)程的執(zhí)行順序4.3.4短作業(yè)優(yōu)先法<80

>從作業(yè)的后備隊列中挑選那些需要運(yùn)行時間最短的作業(yè)放入內(nèi)存短作業(yè)優(yōu)先法能有效地降低作業(yè)的平均等待時間和提高系統(tǒng)的吞吐量算法對長作業(yè)很不利，并且不能保證緊迫性作業(yè)會被及時處理4.3.5最短剩余時間優(yōu)先法<81

>最短剩余時間優(yōu)先（ShortestRemainingTimeFirst,SRTF）法是短作業(yè)優(yōu)先法的變形，它采用搶占式策略4.3.6多級隊列法<82

>多級隊列（MultilevelQueue）調(diào)度算法是根據(jù)作業(yè)的某些特性，如占用內(nèi)存大小和作業(yè)類型等，永久性地把各個作業(yè)分別鏈入不同的隊列，每個隊列都有自己的調(diào)度算法，在各個隊列之間也要進(jìn)行調(diào)度，通常采用固定優(yōu)先級的搶占式調(diào)度4.3.7多級反饋隊列法<83

>多級反饋隊列（MultilevelFeedbackQueue）法是在多級隊列法的基礎(chǔ)上加進(jìn)“反饋”措施。其實現(xiàn)思想是：系統(tǒng)中設(shè)置多個就緒隊列，每個隊列對應(yīng)一個優(yōu)先級，第一個隊列的優(yōu)先級最高，第二個隊列次之，以下各個隊列的優(yōu)先級逐個降低；各就緒隊列中進(jìn)程的運(yùn)行時間片不同，高優(yōu)先級隊列的時間片小，低優(yōu)先級隊列的時間片大，如從高到低依次加倍；新進(jìn)程進(jìn)入系統(tǒng)后，先放入第一隊列的末尾，各隊列按FCFS方式排隊；如某個進(jìn)程在相應(yīng)時間片內(nèi)沒有完成工作，則把它轉(zhuǎn)到下一級隊列的末尾；系統(tǒng)先運(yùn)行第一隊列中的進(jìn)程，第一隊列為空后，才運(yùn)行第二隊列中的進(jìn)程，依次類推。最后一個隊列（最低級）中的進(jìn)程采用時間片輪轉(zhuǎn)的方式進(jìn)行調(diào)度。多級反饋隊列法雖然比較復(fù)雜一些，但具有較好的性能，在UNIX系統(tǒng)，WindowsNT和OS/2中都采用了類似的調(diào)度算法。背景-4：未名湖PART4.4其他進(jìn)程調(diào)度算法4.4.1公平共享調(diào)度<85

>到此為止講述的所有調(diào)度算法都是把就緒進(jìn)程集合看做是單一的進(jìn)程池，從這個進(jìn)程池中選擇下一個要運(yùn)行的進(jìn)程。該池可以按優(yōu)先級劃分成幾個，但它們都是同構(gòu)的。但是，在多用戶系統(tǒng)中，如果單個用戶的應(yīng)用程序或作業(yè)可以組成多個進(jìn)程（或線程），就會出現(xiàn)傳統(tǒng)的調(diào)度器不認(rèn)識的進(jìn)程集合結(jié)構(gòu)。從用戶的角度看，他所關(guān)心的不是某個特定的進(jìn)程如何執(zhí)行，而是構(gòu)成應(yīng)用程序的一組進(jìn)程如何執(zhí)行。因此，基于進(jìn)程組的調(diào)度決策是非常具有吸引力的。該方法通常稱作公平共享調(diào)度（fair-sharescheduling）。此外，即使每個用戶用一個進(jìn)程表示，這個概念可以擴(kuò)展到用戶組。例如，在分時系統(tǒng)中，可能希望把某個部門的所有用戶看作是同一個組中的成員，然后進(jìn)行調(diào)度決策，并給每個組中的用戶提供類似的服務(wù)。因此，如果同一個部門中的大量用戶登錄到系統(tǒng)，則希望響應(yīng)時間效果的降低主要影響到該部門的成員，而不會影響其他部門的用戶。4.4.1公平共享調(diào)度<86

>術(shù)語“公平共享”表明了這類調(diào)度器的基本原則。每個用戶被指定了某種類型的權(quán)值，該權(quán)值定義了該用戶對系統(tǒng)資源的共享，而且是作為在所有使用的資源中所占的比例來體現(xiàn)。特別地，每個用戶被分配了處理器的共享。這種方案或多或少以線性的方式操作，如果用戶A的權(quán)值是用戶B的2倍，那么從長期運(yùn)行的結(jié)果來看，用戶A可以完成的工作應(yīng)該是用戶B的2倍。公平共享調(diào)度器的目標(biāo)是監(jiān)視使用情況，對那些相對于公平共享的用戶占有較多資源的用戶，調(diào)度器分配以較少的資源，相對于公平共享的用戶占有較少資源的用戶，調(diào)度器分配以較多的資源。4.4.2保證調(diào)度<87

>

保證調(diào)度算法的目標(biāo)是保證每個進(jìn)程享用CPU的時間完全一樣，即如果系統(tǒng)里一共有n個進(jìn)程，則每個進(jìn)程占用CPU的時間為1/n。保障調(diào)度就是保障每個進(jìn)程使用1/n的CPU時間。保障就是肯定1/n的時間運(yùn)轉(zhuǎn)，而不是大概1/n時間運(yùn)轉(zhuǎn)。那么保障調(diào)度和輪轉(zhuǎn)調(diào)度是一樣嗎？時間片輪轉(zhuǎn)能不能達(dá)到1/n的效果？關(guān)鍵就是達(dá)到1/n不一定要靠輪轉(zhuǎn)。輪轉(zhuǎn)是能夠達(dá)到1/n的，但是保障調(diào)度不一定要輪轉(zhuǎn)。每次給的時間片不一定要一樣。4.4.3彩票調(diào)度

<88

>彩票調(diào)度算法是一種概率調(diào)度算法。你買過彩票就知道，你買的越多中獎的概率越大。在該算法里，給每個進(jìn)程分發(fā)一定數(shù)量的彩票，而調(diào)度器則從所有彩票里隨機(jī)抽取一張彩票，持有該彩票的進(jìn)程就獲得CPU。這樣，如果想讓某個進(jìn)程獲得更多的CPU時間，我們可以給該進(jìn)程多發(fā)幾張彩票。彩票算法的優(yōu)越性是顯而易見的，通過給每個進(jìn)程至少一張彩票就可以防止饑餓，因為該進(jìn)程獲得CPU的概率將大于0。背景-5：翻尾石魚PART4.5操作系統(tǒng)調(diào)度算法實例4.5.1BSD多級反饋隊列法<90

>BSDUNIX系統(tǒng)主要用于分時交互環(huán)境中，調(diào)度算法設(shè)計成為交互用戶提供好的響應(yīng)時間，同時保證低優(yōu)先級的后臺作業(yè)不會餓死。BSDUNIX系統(tǒng)采用了多級反饋隊列法，在每個優(yōu)先級隊列中采用了輪轉(zhuǎn)的方法

4.5.1BSD多級反饋隊列法<91

>

CPUj(i)：進(jìn)程j在區(qū)間i中處理器使用情況的度量Pj(i)：進(jìn)程j在區(qū)間i開始處的優(yōu)先級；值越小表示的優(yōu)先級最高Basej：進(jìn)程j的基本優(yōu)先級nicej：用戶可控制的調(diào)節(jié)因子4.5.1BSD多級反饋隊列法<92

>每秒都重新計算每個進(jìn)程的優(yōu)先級，并且進(jìn)行一次新的調(diào)度決策。給每個進(jìn)程賦予基本優(yōu)先級的目的是把所有的進(jìn)程劃分成固定的優(yōu)先級區(qū)。CPU和“nice”組件是被限制的，以防止進(jìn)程遷移出指定的區(qū)4.5.2UNIXSVR4調(diào)度<93

>UNIXSVR4中使用的調(diào)度算法是對早期UNIX系統(tǒng)所使用的調(diào)度算法的全面檢查。新算法被設(shè)計成給實時進(jìn)程最高的優(yōu)先權(quán)，給內(nèi)核模式的進(jìn)程次高的優(yōu)先權(quán)，給其他用戶模式的進(jìn)程（稱作分時進(jìn)程）最低的優(yōu)先權(quán)。SVR4中實現(xiàn)的兩個重要的修改為：1．增加了可搶占的靜態(tài)優(yōu)先級調(diào)度器，引進(jìn)了160種優(yōu)先級，并劃分到三個優(yōu)先級類中。2．插入了可搶占點。由于基本內(nèi)核是不能被搶占的，它只能劃分成許多個處理步驟，每一步都必須一直運(yùn)行到完成，中間不會被中斷。在處理步驟之間，有一個稱作可搶占點的安全位置，在這里，內(nèi)核可以安全地中斷處理，并調(diào)度一個新進(jìn)程。安全位置定義成一個代碼區(qū)域，在這里所有的內(nèi)核數(shù)據(jù)結(jié)構(gòu)或者是已經(jīng)更新且一致的，或者通過一個信號量被鎖定。4.5.2UNIXSVR4調(diào)度<94

>SVR4中定義了160個優(yōu)先級，每個進(jìn)程定義成屬于這三類優(yōu)先級中的一類，并被指定為具有該類中的一個優(yōu)先級。這三類優(yōu)先級為：●實時（159~100）：具有這些優(yōu)先級的進(jìn)程可以保證在任何內(nèi)核進(jìn)程或分時進(jìn)程之前被選擇運(yùn)行。此外，實時進(jìn)程可以使用可搶占點搶占內(nèi)核進(jìn)程和用戶進(jìn)程?！駜?nèi)核（99～66）：具有這些優(yōu)先級的進(jìn)程保證在任何分時進(jìn)程之前被選擇運(yùn)行，但必須服從實時進(jìn)程?！穹謺r（59～0）：最低優(yōu)先級的進(jìn)程，通常是除了實時應(yīng)用程序以外的用戶應(yīng)用程序。每個優(yōu)先級都關(guān)聯(lián)著一個調(diào)度隊列，在某一給定優(yōu)先級的進(jìn)程按循環(huán)方式執(zhí)行。有一個位映像向量dqactmap，它的每一位對應(yīng)于各個優(yōu)先級。4.5.2UNIXSVR4調(diào)度<95

>如果某個優(yōu)先級上的隊列不為空，則相應(yīng)的位被置為1。當(dāng)一個正在運(yùn)行的進(jìn)程由于阻塞、時間片到期或搶占等原因離開運(yùn)行狀態(tài)時，調(diào)度器檢查dqactmap，并從優(yōu)先級最高的非空隊列中調(diào)度一個就緒進(jìn)程。此外，當(dāng)?shù)竭_(dá)一個定義的可搶占點時，內(nèi)核檢查一個稱作kprunrun的標(biāo)記，如果它被置位，則表明至少有一個實時進(jìn)程處于就緒狀態(tài)，如果當(dāng)前進(jìn)程的優(yōu)先級低于優(yōu)先級最高的實時就緒進(jìn)程，則內(nèi)核搶占當(dāng)前進(jìn)程。在分時類中，進(jìn)程的優(yōu)先級是可變的。每當(dāng)一個進(jìn)程用完它的時間片時，調(diào)度器降低它的優(yōu)先級；如果一個進(jìn)程在一個事件或資源上阻塞時，則調(diào)度器提高它的優(yōu)先級。分配給分時進(jìn)程的時間量取決于它的優(yōu)先級，其范圍從給優(yōu)先級0分配的100ms到給優(yōu)先級59分配的50ms。每個實時進(jìn)程都有一個固定的優(yōu)先級和固定的時間量。4.5.3Linux搶占式調(diào)度<96

>Linux系統(tǒng)中的進(jìn)程，既可以在用戶態(tài)下運(yùn)行，又可以在核心態(tài)下運(yùn)行。而核心態(tài)的權(quán)限高于用戶態(tài)的權(quán)限。進(jìn)程每次執(zhí)行系統(tǒng)調(diào)用時，其運(yùn)行方式就會發(fā)生變化，從用戶態(tài)切換到核心態(tài)4.5.3Linux搶占式調(diào)度<97

>1．調(diào)度方式Linux系統(tǒng)的調(diào)度方式基本上采用“搶占式優(yōu)先級”方式Linux系統(tǒng)中的調(diào)度基本上繼承了UNIX系統(tǒng)的以優(yōu)先級為基礎(chǔ)的調(diào)度4.5.3Linux搶占式調(diào)度<98

>2．調(diào)度策略Linux系統(tǒng)針對不同類別的進(jìn)程提供了三種不同的調(diào)度策略，即SCHED_FIFO,SCHED_RR及SCHED_OTHER4.5.3Linux搶占式調(diào)度<99

>3．調(diào)度時機(jī)①當(dāng)前進(jìn)程調(diào)用系統(tǒng)調(diào)用nanosleep()或者pause()，使自己進(jìn)入睡眠狀態(tài)，主動讓出一段時間的CPU的使用權(quán)②進(jìn)程終止，永久地放棄對CPU的使用③在時鐘中斷處理程序執(zhí)行過程中，發(fā)現(xiàn)當(dāng)前進(jìn)程連續(xù)運(yùn)行的時間過長④當(dāng)喚醒一個睡眠進(jìn)程時，發(fā)現(xiàn)被喚醒的進(jìn)程比當(dāng)前進(jìn)程更有資格運(yùn)行⑤一個進(jìn)程通過執(zhí)行系統(tǒng)調(diào)用來改變調(diào)度策略或者降低自身的優(yōu)先級（如nice命令），從而引起立即調(diào)度4.5.3Linux搶占式調(diào)度<100

>4．調(diào)度算法首先查找所有在就緒隊列中的進(jìn)程，從中選出優(yōu)先級最高且在內(nèi)存的一個進(jìn)程。如果隊列中有實時進(jìn)程，則實時進(jìn)程將優(yōu)先運(yùn)行。如果最需要運(yùn)行的進(jìn)程不是當(dāng)前進(jìn)程，則當(dāng)前進(jìn)程就被掛起，并且保存它的現(xiàn)場——所涉及的一切機(jī)器狀態(tài)，包括程序計數(shù)器和CPU寄存器等，然后為選中的進(jìn)程恢復(fù)運(yùn)行現(xiàn)場。4.5.4Windows調(diào)度<101

>Windows實現(xiàn)了可搶占式調(diào)度器，它具有靈活的優(yōu)先級系統(tǒng)，在每一級上都包括了輪轉(zhuǎn)調(diào)度方法，在某些級上，優(yōu)先級可以基于它們當(dāng)前的線程活動而動態(tài)變化Windows中的優(yōu)先級被組織成兩段：實時和可變4.5.4Windows調(diào)度<102

>在實時優(yōu)先級類中，所有線程具有固定的優(yōu)先級，并且它們的優(yōu)先級永遠(yuǎn)不會改變，某一給定優(yōu)先級的所有活動線程在一個輪轉(zhuǎn)隊列中在可變優(yōu)先級類中，一個線程的優(yōu)先級在開始時是最初指定的值，但在它的生命周期中可能會發(fā)生變化，上升或者下降背景-1：北京大學(xué)西門PART4.6多處理器調(diào)度算法4.6多處理器調(diào)度算法<104

>●松耦合、分布式多處理器、集群●專門功能的處理器●緊耦合多處理4.6.1粒度<105

>●把進(jìn)程分配到處理器●在單個處理器上使用多道程序設(shè)計●一個進(jìn)程的實際分派4.6.2設(shè)計問題<106

>●無約束并行性●

粗粒度和非常粗粒度并行性●中等粒度并行性●細(xì)粒度的并行性4.6.2設(shè)計問題<107

>靜態(tài)分配的缺點是一個處理器可能處于空閑狀態(tài)調(diào)度進(jìn)程的開銷與它被調(diào)度到哪個處理器無關(guān)4.6.2設(shè)計問題<108

>不論是否給進(jìn)程分配專用的處理器，都需要通過某種方法把進(jìn)程分配給處理器這種方法有兩個缺點：（1）主處理器的失敗導(dǎo)致整個系統(tǒng)失?。?）主處理器可能成為性能瓶頸4.6.2設(shè)計問題<109

>1、如何能為應(yīng)用提供最好的平均性能2、選擇哪一個進(jìn)程運(yùn)行4.6.3進(jìn)程調(diào)度<110

>在大多數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進(jìn)程并不是被指定到一個專門的處理器。不是所有處理器只有一個隊列，或者使用某種類型的優(yōu)先級方案，而是有多條基于優(yōu)先級的隊列，并且都送進(jìn)相同的處理器池中。在任何情況下，都可以把系統(tǒng)看作是多服務(wù)器排隊結(jié)構(gòu)4.6.4線程調(diào)度<111

>在單處理器中，線程可以用作輔助構(gòu)造程序，并在處理過程中重疊執(zhí)行I/O。由于在進(jìn)行線程切換時的性能損失遠(yuǎn)遠(yuǎn)小于進(jìn)程切換的開銷，因此可以用很少的代價實現(xiàn)這些優(yōu)點在多處理器系統(tǒng)中，線程的全部能力得到了更好的展現(xiàn)。在這個環(huán)境中，線程可以用于開發(fā)應(yīng)用程序中真正的并行性4.6.4線程調(diào)度<112

>●加載共享●組調(diào)度●專用處理器分配●動態(tài)調(diào)度4.6.4線程調(diào)度<113

>●負(fù)載均勻●不需要集中調(diào)度器●