操作系統(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)系理解線程的不同實(shí)現(xiàn)方式了解PthreadAPI，并能運(yùn)用其開發(fā)多線程應(yīng)用了解協(xié)程的概念教師導(dǎo)讀<3

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

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

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

是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位進(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í)通常高于一般用戶進(jìn)程的優(yōu)先級(jí)進(jìn)程定義3.1.1進(jìn)程定義<7

>1.

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

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

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

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

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

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

結(jié)構(gòu)性：一個(gè)進(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ā)生而暫時(shí)不能運(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ī)

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

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

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

阻塞進(jìn)程在其被阻塞的原因獲得時(shí)解除阻塞<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）：完成一個(gè)新進(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）超時(shí)（Timeout）：用完時(shí)間片，進(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í)進(jìn)程對(duì)換至外存，這種做法可得到的好處：（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)程模型相比，增加了就緒掛起和阻塞掛起兩個(gè)狀態(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)建一個(gè)進(jìn)程時(shí)，為進(jìn)程設(shè)置一個(gè)PCB，再利用PCB對(duì)進(jìn)程進(jìn)行控制和管理撤消進(jìn)程時(shí)，系統(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)度時(shí)使用，描述進(jìn)程當(dāng)前所處的狀況進(jìn)程名、進(jìn)程號(hào)、存儲(chǔ)信息、優(yōu)先級(jí)、當(dāng)前狀態(tài)、資源清單、“家族”關(guān)系、消息隊(duì)列指針、進(jìn)程隊(duì)列指針和當(dāng)前打開文件等現(xiàn)場信息：刻畫進(jìn)程的運(yùn)行情況程序狀態(tài)字、時(shí)鐘、界地址寄存器等一旦中斷進(jìn)程的運(yùn)行，必須把中斷時(shí)刻的內(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)程要實(shí)現(xiàn)的功能數(shù)據(jù)是程序操作的對(duì)象<20

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

PCB組織（1）線性方式：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

必須在管態(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)先級(jí)等<27

>3.2.1進(jìn)程控制創(chuàng)建原語創(chuàng)建一個(gè)新的進(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)，并把它插入到該事件的等待隊(duì)列中去

4.

喚醒原語等待狀態(tài)轉(zhuǎn)換為就緒狀態(tài)從等待隊(duì)列中撤出并插入到就緒隊(duì)列中排隊(duì)，等待調(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)建一個(gè)子進(jìn)程getpid返回當(dāng)前進(jìn)程的PIDexec更換進(jìn)程映像，即根據(jù)指定的文件名找到可執(zhí)行文件，并用它來取代調(diào)用進(jìn)程的內(nèi)容exit終止調(diào)用的程序（用于程序運(yùn)行出錯(cuò)）wait等待任何要僵死的子進(jìn)程sleep使進(jìn)程掛起指定的時(shí)間nice改變進(jìn)程的優(yōu)先級(jí)<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)程，以及各自分開活動(dòng)的情況#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)建一個(gè)子進(jìn)程*/if(pid<0){/*出現(xiàn)錯(cuò)誤。進(jìn)程ID號(hào)不可能小于0*/fprintf(stderr,"ForkFailed");/*輸出出錯(cuò)消息——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){ /*此時(shí)子進(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)程活動(dòng)存在時(shí)間和空間的資源開銷，數(shù)目不宜太多，切換頻率不宜過高使多個(gè)程序更好地并發(fā)執(zhí)行，盡量減少系統(tǒng)的開銷分離調(diào)度的基本單位和獨(dú)立分配資源的單位調(diào)度和分派的基本單位不負(fù)責(zé)分配資源擁有資源的基本單位，不頻繁地切換<35

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

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

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

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

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

>3.3.2

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

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

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

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

>3.3.2

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

>3.3.3

線程與進(jìn)程的關(guān)系線程又稱為輕量級(jí)進(jìn)程或者進(jìn)程元傳統(tǒng)的進(jìn)程稱為重量級(jí)進(jìn)程通常一個(gè)進(jìn)程都有若干個(gè)線程調(diào)度傳統(tǒng)的操作系統(tǒng)中擁有資源的基本單位和獨(dú)立調(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í)行一個(gè)進(jìn)程中的多個(gè)線程之間也可以并發(fā)執(zhí)行擁有資源不論是傳統(tǒng)的操作系統(tǒng)，還有線程的操作系統(tǒng)進(jìn)程都是擁有資源的一個(gè)獨(dú)立單位<42

>3.3.3

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

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

>3.3.3

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

>3.4.1

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

>3.4.1

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

>3.4.1

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

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

>3.4.1

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

>3.4.1

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

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

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

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

并行運(yùn)行

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

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

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

>3.4.1

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

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

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

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

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

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

>3.4.2

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

一個(gè)標(biāo)識(shí)符

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

一組存儲(chǔ)在結(jié)構(gòu)中的屬性，包括棧大小、調(diào)度參數(shù)以及其它線程需要的項(xiàng)目下表中列舉了幾個(gè)主要的Pthread函數(shù)調(diào)用線程調(diào)用描述pthread_create()創(chuàng)建一個(gè)新線程pthread_join()等待一個(gè)特定的線程退出pthread_exit()結(jié)束調(diào)用的線程pthread_yield()釋放CPU來運(yùn)行另外一個(gè)線程pthread_attr_init()創(chuàng)建并初始化一個(gè)線程pthread_attr_destroy()刪除一個(gè)線程的屬性結(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)識(shí)符，然后退出。*/printf("HelloWorld.%d0\n",*(int*)tid);pthread_exit(NULL);}引入Pthread庫，并定義線程需要執(zhí)行的函數(shù)：當(dāng)創(chuàng)建一個(gè)線程時(shí)，它打印一條發(fā)布信息，然后退出<53

>3.4.2

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

>intmain(intargc,char*argv[]){/*主程序創(chuàng)建10個(gè)線程，然后退出。*/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ù)量非常多的時(shí)候，系統(tǒng)線程會(huì)占用非常多的內(nèi)存空間過多的線程切換會(huì)占用大量的系統(tǒng)時(shí)間解決方法：協(xié)程機(jī)制協(xié)程是運(yùn)行在線程之上的輕量級(jí)線程當(dāng)一個(gè)協(xié)程執(zhí)行完成后，讓另一個(gè)協(xié)程運(yùn)行在當(dāng)前線程之上協(xié)程并沒有增加線程數(shù)量只是在線程的基礎(chǔ)之上通過分時(shí)復(fù)用的方式運(yùn)行多個(gè)協(xié)程協(xié)程的切換在用戶態(tài)完成切換的代價(jià)比線程從用戶態(tài)到內(nèi)核態(tài)的代價(jià)小很多<55

>第4章進(jìn)程線程調(diào)度4.1進(jìn)程調(diào)度的基本概念4.2進(jìn)程調(diào)度算法的設(shè)計(jì)思路4.3經(jīng)典進(jìn)程調(diào)度算法4.4其他進(jìn)程調(diào)度算法4.5操作系統(tǒng)調(diào)度算法實(shí)例4.6多處理器調(diào)度算法4.7實(shí)時(shí)調(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)程對(duì)CPU的競爭，按照一定的調(diào)度算法，使某一就緒進(jìn)程獲得CPU的控制權(quán)，轉(zhuǎn)換成運(yùn)行狀態(tài)。進(jìn)程調(diào)度也叫低級(jí)調(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)度的時(shí)機(jī)<61

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

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

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

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

>①CPU利用率②吞吐量③周轉(zhuǎn)時(shí)間④就緒等待時(shí)間⑤響應(yīng)時(shí)間背景-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)度算法對(duì)于作業(yè)調(diào)度來說，每次調(diào)度從后備作業(yè)隊(duì)列中選擇隊(duì)頭的一個(gè)或幾個(gè)作業(yè)，把它們調(diào)入內(nèi)存，分配相應(yīng)的資源，創(chuàng)建進(jìn)程，然后把進(jìn)程放入就緒隊(duì)列對(duì)于進(jìn)程調(diào)度算法來說，即每次調(diào)度從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把CPU分給它，直至完成或者由于某些原因而阻塞，當(dāng)新一個(gè)進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，它的PCB就鏈入就緒隊(duì)列的末尾。每次進(jìn)程調(diào)度時(shí)就把隊(duì)頭進(jìn)程從該隊(duì)列中摘下，分給它CPU，使它運(yùn)行4.3.1先來先服務(wù)法<69

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>多級(jí)反饋隊(duì)列（MultilevelFeedbackQueue）法是在多級(jí)隊(duì)列法的基礎(chǔ)上加進(jìn)“反饋”措施。其實(shí)現(xiàn)思想是：系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)優(yōu)先級(jí)，第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，以下各個(gè)隊(duì)列的優(yōu)先級(jí)逐個(gè)降低；各就緒隊(duì)列中進(jìn)程的運(yùn)行時(shí)間片不同，高優(yōu)先級(jí)隊(duì)列的時(shí)間片小，低優(yōu)先級(jí)隊(duì)列的時(shí)間片大，如從高到低依次加倍；新進(jìn)程進(jìn)入系統(tǒng)后，先放入第一隊(duì)列的末尾，各隊(duì)列按FCFS方式排隊(duì)；如某個(gè)進(jìn)程在相應(yīng)時(shí)間片內(nèi)沒有完成工作，則把它轉(zhuǎn)到下一級(jí)隊(duì)列的末尾；系統(tǒng)先運(yùn)行第一隊(duì)列中的進(jìn)程，第一隊(duì)列為空后，才運(yùn)行第二隊(duì)列中的進(jìn)程，依次類推。最后一個(gè)隊(duì)列（最低級(jí)）中的進(jìn)程采用時(shí)間片輪轉(zhuǎn)的方式進(jìn)行調(diào)度。多級(jí)反饋隊(duì)列法雖然比較復(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)程池，從這個(gè)進(jìn)程池中選擇下一個(gè)要運(yùn)行的進(jìn)程。該池可以按優(yōu)先級(jí)劃分成幾個(gè)，但它們都是同構(gòu)的。但是，在多用戶系統(tǒng)中，如果單個(gè)用戶的應(yīng)用程序或作業(yè)可以組成多個(gè)進(jìn)程（或線程），就會(huì)出現(xiàn)傳統(tǒng)的調(diào)度器不認(rèn)識(shí)的進(jìn)程集合結(jié)構(gòu)。從用戶的角度看，他所關(guān)心的不是某個(gè)特定的進(jìn)程如何執(zhí)行，而是構(gòu)成應(yīng)用程序的一組進(jìn)程如何執(zhí)行。因此，基于進(jìn)程組的調(diào)度決策是非常具有吸引力的。該方法通常稱作公平共享調(diào)度（fair-sharescheduling）。此外，即使每個(gè)用戶用一個(gè)進(jìn)程表示，這個(gè)概念可以擴(kuò)展到用戶組。例如，在分時(shí)系統(tǒng)中，可能希望把某個(gè)部門的所有用戶看作是同一個(gè)組中的成員，然后進(jìn)行調(diào)度決策，并給每個(gè)組中的用戶提供類似的服務(wù)。因此，如果同一個(gè)部門中的大量用戶登錄到系統(tǒng)，則希望響應(yīng)時(shí)間效果的降低主要影響到該部門的成員，而不會(huì)影響其他部門的用戶。4.4.1公平共享調(diào)度<86

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

>

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

<88

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

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

4.5.1BSD多級(jí)反饋隊(duì)列法<91

>

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

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

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

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

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

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

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

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

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

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

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

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

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

>●無約束并行性●

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

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

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

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

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

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

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

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