计算机操作系统教程 课件第2章-进程管理

计算机操作系统ComputerOperatingSystems第二章

进程管理第二章进程管理132进程（Process）进程控制进程调度4进程的状态2.1进程(Process)Whyprocesses?

为了提高计算机系统中各种资源的利用率，现代操作系统广泛采用多道程序技术（multi-programming），使多个程序同时在系统中存在并运行。进程管理运算器控制器指令指令指令指令指令指令2.1进程(Process)进程管理运算器控制器程序A程序B程序A2.1进程(Process)进程管理2.1进程(Process)

进程是程序在一个数据集合上的一次运行活动，是操作系统进行资源分配和调度的一个基本单位。进程的概念2.1进程(Process)Aprocess＝aprograminexecution一个进程应该包括：程序的代码；程序的数据；

CPU寄存器的值，如PC，用来指示下一条将运行

的指令、通用寄存器等；

堆、栈；一组系统资源（如地址空间、打开的文件）总之，进程包含了正在运行的一个程序的所有

状态信息。什么是进程？

程序是有序代码的集合，通常对应着文件，可以复制，其本身没有任何运行的含义，是一个静态的概念。

进程是程序在处理机上的一次执行过程，它是一个动态的概念。进程与程序的区别2.1进程(Process)AprogramisCstatementsorcommands

静态的；Aprocessisprogram+runningcontext

动态的.main()

{…..}A()

{…..}

PROGRAMmain()

{…..}A()

{…..}

PROCESSheap

StackAMainRegisters,PCProcess≠Program举例有一个计算机科学家，有一天女儿过生日，想亲手给女儿做一个生日蛋糕。所以他就找了一本有关做蛋糕的食谱，买了一些原料，面粉、鸡蛋、糖、香料等，然后边看边学边做。

食谱＝算法；原料＝数据；这时小儿子哭着跑进来，说手被蜜蜂蛰了。教授只好把蛋糕先放在一边。他在食谱上做了个标记，把状态信息记录了起来。然后又去找了一本医疗手册，查到了相关的内容，按照上面的指令一步步地执行。当伤口处理完之后，又回到厨房继续做蛋糕。

CPU从一个进程（做蛋糕）切换到另一个进程（医疗

救护）。科学家＝；进程＝；CPU做蛋糕2.1进程(Process)程序＝数据结构＋算法描述进程的数据结构：进程控制块（ProcessControlBlock，PCB）。

系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。2.1进程(Process)2.2进程的状态进程控制块

进程控制块是系统描述进程信息的一套数据结构，是进程存在的标志。

操作系统管理、调度系统中的进程，进程就是操作系统程序加工的对象。针对这个加工对象需要一套清楚的、全面的数据结构描述，这套数据结构就是进程控制块（PCB）。即详细描述系统进程信息的数据结构叫做进程控制块（PCB）。进程控制块中的信息

1)进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：

(1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。

(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。2)处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。①通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有8~32个通用寄存器，在RISC结构的计算机中可超过100个；②指令计数器，其中存放了要访问的下一条指令的地址；③程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。3)进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括：①进程状态，指明进程的当前状态，作为进程调度和对换时的依据；②进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。4)进程控制信息进程控制信息包括：①程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；②进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；③资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；④链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。PCB中的主要内容逻辑寄存器应该用什么数据结构来实现PCB？structtask_struct{...volatilelongstate;pid_tpid;unsignedlonglongtimestamp;unsignedlongrt_priority;structmm_struct*mm,*active_mm;...};Linux的进程控制块进程的三种基本状态：进程在生命结束前处于且仅处于三种基本状态之一，不同系统设置的进程状态数目不同。2.2

进程的状态运行状态（Running）：进程占有CPU，并在CPU上运行。处于此状态的进程数目小于等于CPU的数目。就绪状态（Ready）：进程已经具备运行条件，但由于CPU忙暂时不能运行，只要分得CPU即可执行；阻塞状态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态（如I/O操作或进程同步）,此时，即使CPU空闲，该进程也不能运行。修理自行车…2.2

进程的状态（本图摘自AndrewS.Tanenbaum：“ModernOperatingSystems”，下同）进程的状态及其转换进程正常运行(未阻塞)时处于什么状态此PPT程序处于什么状态？是否有其他的状态转换？2.2

进程的状态进程转换运行-->阻塞等待I/O的结果等待某一进程提供输入运行-->就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态就绪-->运行调度程序选择一个新的进程运行阻塞-->就绪当所等待的事件发生时由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；不同的状态分别用不同的队列来表示（运行队列、就绪队列、各种类型的阻塞队列）；每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列。状态队列就绪队列和各种I/O设备队列（本图摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）如何实现队列？带挂起的进程状态2.2

进程的状态引起进程创建的三个主要事件：系统初始化时；在一个正在运行的进程当中，执行了

创建进程的系统调用；用户请求创建一个新进程。2.3

进程控制进程的创建从技术上来说，只有一种创建进程的方法，即在一个已经存在的进程（用户进程或系统进程）当中，通过系统调用来创建一个新的进程。Unix：fork函数；Windows：CreateProcess函数;进程的终止引起进程终止的事件进程终止的过程2.3

进程控制进程的创建：为该进程生成一个PCB；进程的终止：回收它的PCB；进程的组织管理：通过对PCB的组织管理来实现；系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志。PCB存放在哪？进程的状态转换：……？intmain(){while(1){fork();}}2.3

进程控制动态性：程序的运行状态在变，PC、寄存器、

堆和栈等；独立性：是一个独立的实体，是计算机系统资

源的使用单位。每个进程在一个“虚拟

计算机”上运行，每个进程都有“自己”

的PC和内部状态，运行时独立于其他

的进程（虚拟PC和物理PC）；并发性：从宏观上看各进程是同时独立运行的进程的特性单核CPU的进程运行内核运行切换到进程P1陷入到内核切换到另一个（或同一个）进程陷入到内核...P1KP2KP2KKP1P1OS内核P2P3用户模式内核模式TimeP1P2P3Kernelsystemcall(userI/O)interrupt(I/Odone)interruptexceptioninterrupt(timer)waitingreadyreadyreadyreadyreadywaitingOSProcessManagementSubsystem2.4进程调度2.4进程调度2.4进程调度2.4.1高级、中级和低级调度1.高级调度(HighScheduling)1）接纳作业数（内存驻留数）将外存作业调入内存，创建PCB，插入就绪队列。太多―――>周转时间T长太少―――>系统效率低2）接纳策略：即采用何种调度算法

2.4进程调度2.低级调度(LowLevelScheduling)①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。进程调度2.4进程调度3.中级调度(Intermediate-LevelScheduling)

中级调度又称中程调度(Medium-TermScheduling)。引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。2.4进程调度2.4.2调度算法及评价准则面向用户的准则(1)周转时间短。

可把平均周转时间描述为：2.4进程调度(2)带权的周转时间短。

作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:面向系统的评价指标（考虑系统各部分的利用率）吞吐量（Throughput）：单位时间内所完成的

作业数，与作业本身特性和调度算法有关；CPU的利用率：大中型主机的CPU较贵，所以要让它时刻不停地转着。各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配。2.4.2调度算法及评价准则2.4进程调度调度方法

1）排队

系统中就绪的进程可能有多个，就绪进程排成就绪队列可以方便调度程序调度。2）分派

按照一定的调度算法，从就绪队列中选择进程，选中进程后，分派程序把这个进程从就绪队列里取出来，做进程切换的准备。3）切换

实质就是进程上下文的切换，操作系统先保护当前运行进程的上下文，进行现场保护，然后装入分派程序指定的进程的上下文，使这个程序获得CPU控制权，并运行。不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出CPU。以上的情形1－3均可发生调度；可抢占调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形1－5均可发生调度。两种调度方式2.4.2调度算法先来先服务（FirstComeFirstServed，FCFS;FirstInFirstOut，FIFO）：

按照作业到达的先后次序进行调度；进程号提交时间运行时间1230.00.41.08.04.01.0先来先服务调度算法先来先服务调度算法先来先服务调度算法作业提交时间运行时间开始执行时间完成时间周转时间带权的周转时间作业108.00作业20.44.08.0作业31.01.012.0

平均：

先来先服务调度算法作业提交时间运行时间开始执行时间完成时间周转时间带权的周转时间作业108.00作业20.44.08.0作业31.01.012.0

平均：

8.012.013.08.011.612.01.02.912.010.535.32.4.2调度算法短作业优先（ShortestJobFirst,SJF）:

作业在开始执行时预计执行时间，对预计执行时间短的作业优先分派处理器。短作业优先调度算法短作业优先调度算法作业提交时间运行时间开始执行时间完成时间周转时间带权的周转时间作业108.00作业20.44.09.0作业31.01.08.0

平均：

短作业优先调度算法作业提交时间运行时间开始执行时间完成时间周转时间带权的周转时间作业108.008.08.01作业20.44.09.013.012.63.15作业31.01.08.09.08.08.0

平均：

9.534.05FCFS与SJF调度算法比较作业开始时间完成时间周转时间带权周转时间1099991299100100100

平均：99.550.5作业开始时间完成时间周转时间带权周转时间20111111001001.01

平均：50.51.005进程管理进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间试做

练习题进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1练习题答案进程管理进程名ABCDE平均到达时间01234服务时间33521FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间试做

练习题进程管理进程名ABCDE平均到达时间01234服务时间33521FCFS完成时间36111314周转时间35910107.4带权周转时间11.671.85103.89SJF完成时间391456周转时间3812225.4带权周转时间12.672.4121.81练习题答案

先来先服务和短作业（进程）优先调度算法比较1.FCFS特点：简单，有利于长作业即CPU繁忙性作业2.短作业进程优先调度算法：SJ(P)F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定2.4.2调度算法优先级高者优先调度算法优先级算法（PriorityScheduling）：给每个进

程设置一个优先级，然后在所有就绪进程中选择

优先级最高的那个进程去运行；

SJF就是一个优先级算法，每个进程的优先级是

它的CPU运行时间（时间越短，优先级越高）；分为可抢占和不可抢占两种方式；各进程优先级

的确定方式可分为静态和动态两种。优先级高者优先调度算法静态优先级方式基本思路：在创建进程时确定进程的优先级，并保持不变直到进程结束；缺点：高优先级的进程一直占用CPU，低优先级的进程“饥饿”。优先级高者优先调度算法动态优先级方式基本思路：在创建进程时赋予给进程的优

先级，在进程运行过程中可以动态改变；为防“饥饿”,可根据运行时间和等待时间调整优先级。例如，进程每执行一个时间片就降低其优先级，而在就绪队列中，等待时间延长则优先级提高。响应比高者优先调度算法作业号提交时间运行时间1230.00.41.08.04.01.0响应比：问题：响应比与带权周转时间区别？响应比高者优先调度算法高响应比优先算法：特点：响应比Rp=（tw+ts）/ts（1）短作业RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。响应比高者优先调度算法等待时间要求服务时间要求服务时间优先权+=进程到达时刻运行时间/ms

P1

0

10

P2

1

1

P3

2

2

P4

3

1

P5

4

5

响应比高者优先调度算法进程到达时刻运行时间/ms

P1

0

10

P2

1

1

P3

2

2

P4

3

1

P5

4

5

0时刻:P1运行，10时刻:P1运行完，此时P2-P5的响应比分别为：P2：(1+9)/1=10P3：(2+8)/2=5P4：(1+7)/1=8P5：(5+6)/5=2.2因此执行P2响应比高者优先调度算法进程到达时刻运行时间/ms

P1

0

10

P2

1

1

P3

2

2

P4

3

1

P5

4

5

0时刻:P1运行，10时刻:P1运行完，P2运行11时刻:P2运行完，此时P3-P5的响应比分别为：P3：(2+9)/2=5.5P4：(1+8)/1=9P5：(5+7)/5=2.4因此执行P4。响应比高者优先调度算法进程到达时刻运行时间/ms

P1

0

10

P2

1

1

P3

2

2

P4

3

1

P5

4

5

0时刻:P1运行，10时刻:P1运行完，P2运行11时刻:P2运行完，P4运行12时刻:P4运行完，此时P3、P5的响应比分别为：P3：(2+10)/2=6P5：(5+8)/5=2.6因此执行P3。响应比高者优先调度算法进程到达时刻运行时间/ms

P1

0

10

P2

1

1

P3

2

2

P4

3

1

P5

4

5

0时刻:P1运行，10时刻:P1运行完，P2运行，P1周转时间10

11时刻:P2运行完，P4运行，P2周转时间1012时刻:P4运行完，P3运行，P4周转时间914时刻:P3运行完，P5运行，P3周转时间1219时刻:P5运行完，P5周转时间15平均周转时间为：(10+10+12+9+15)/5=56/5=11.2

开始时，进程B位于队列之首，因此被调度执行。当

它的时间片用完后，就把它送到就绪队列的末尾。

同时，进程F成为队首进程，被调度运行。（本图摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）轮转调度算法轮转调度算法Roundrobin,too….基于时间片的调度算法123456789101112131415161718ABtCDEABCDE(a)q=1(b)q=4

作业情况时间片进程名ABCDE平均到达时间01234

服务时间43524

RRq=1完成时间1210181117

周转时间1291681311.6带权周转时间333.243.253.29

RRq=4完成时间47181317

周转时间461610139.8带权周转时间123.253.252.89基于时间片的调度算法基于时间片的调度算法优点：公平性：各个就绪进程平均地分配CPU的使用时间。假设有n个就绪进程，那么每个进程将得到1/n的CPU时间；活动性：若时间片大小为q，每个进程最多等待

(n-1)q时间就能够再次得到CPU去运行。基于时间片的调度算法缺点：q的大小难以确定q太大：退化为FCFS算法，进程在一个时间片内执行完或被阻塞，响应时间长。如q=100ms；q太小：每个进程需要更多时间片才能处理完，进程切换次数增加(1ms)，增大系统开销；一般在20－50ms基于优先级的调度算法（本图摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）

可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。多级反馈队列调度算法多级队列算法（MultilevelQueue）引入多个就绪

队列，通过各个队列的区别对待，达到一个综合的

调度目标。根据进程的性质或类型的不同，将就绪队列再分

为若干个子队列，如系统进程、用户交互进程、

批处理进程等；不同的队列可以有不同的优先级；不同的队列可以采用各自不同的调度算法，如前

台的交互式进程可采用RR算法，后台的批处理进

程可采用FCFS算法。多级反馈队列调度算法多级队列算法把每个进程按照它的类型固定在一

个队列中，但问题是如何来确定进程的类型？

而且有的进程其类型可能动态变化，怎么办？

“路遥知马力，日久见人心”！

多级反馈队列算法

(MultilevelFeedbackQueue)

即根据一个进程的运行反馈信息，动态地调整它

所在的队列。

反馈（Feedback）：即进程在运行当中的表

现，例如，它是否需要整个的时间片用于计

算，或者它是否经常地执行I/O操作？多级反馈队列调度算法如何实现多级反馈队列算法？需要确定以下的一

些参数：队列的个数；每个队列所用的调度算法；用来确定何时给一个进程“升级”的方法；用来确定何时给一个进程“降级”的方法；用来确定一个进程的初始队列的方法；多级反馈队列调度算法

三种优先级别，3最高、1最低，三个就绪队列。时间片长度

分别为N、2N和4N；新进程进入内存后，优先级为3，加入队列3的末尾，按FCFS

算法调度；若一个时间片内未能执行完，则优先级降为2，加

入到队列2的末尾，同样按FCFS算法调度；依此类推。如果进程在时间片用完之前即被阻塞，则增加它的优先级；仅当较高优先级的队列为空，才调度较低优先级的队列中的进

程执行。若进程执行时有新进程进入较高优先级的队列，则抢

先执行新进程。优先级321多级反馈队列调度算法假设系统中有3个就绪队列Q1,Q2,Q3，时间片分别为2，4，8。

现在有3个作业J1,J2,J3分别在时间0，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。1、时刻0：J1到达。于是进入到队列1，运行1个时刻，时间片还未

到，此时J2到达。2、时刻1：J2到达。由于时间片仍然由J1掌控，于是等待。J1在运行

了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置

于Q2等待被调度。现在处理机分配给J2。3、时刻2：J1进入Q2等待调度，J2获得CPU开始运行。4、时刻3：J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也

在Q2等待调度。多级反馈队列调度算法假设系统中有3个就绪队列Q1,Q2,Q3，时间片分别为2，4，8。

现在有3个作业J1,J2,J3分别在时间0，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。5、时刻4：J2处理完成，由于J3，J1都在等待调度，但是J3所在的队

列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。6、时刻5：J3经过1个时间片，完成。7、时刻5：由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处

理器开始运行。8、时刻6：J1再经过一个时间片，完成了任务。于是整个调度过程结

束。多级反馈队列调度算法特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。多级反馈队列调度算法多级反馈队列算法是时间片轮转算法和优先级算法

的综合和发展。其特点是：为提高系统吞吐量和缩短平均周转时间而照顾短

进程：新进程一进来即赋予最高优先级。为获得较好的I/O设备利用率和缩短响应时间而照

顾了I/O繁忙的进程：I/O繁忙进程：让其进入最高优先级队列，以及时启动I/O操作。通常只需一个小时间片，即可处理完一次I/O请求，然后转入到阻塞队列。CPU繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。不必估计进程的执行时间，动态调节，能够适应

一个进程在不同时间段的不同运行特点。多级反馈队列调度算法优先级和时间片都会根据进程的特点而发生变化。lowhighhighprioritytimesliceI/OboundjobsCPUboundjobs2.4进程调度2.4.3实时调度

实现实时调度的基本条件1.提供必要的信息

就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。2.4.3实时调度2.系统处理能力

在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为P