《第二讲进程的描述及处理器调度》由会员分享，可在线阅读，更多相关《第二讲进程的描述及处理器调度（40页珍藏版）》请在金锄头文库上搜索。
1、第第 二二 讲讲进进 程程 的的 描描 述述处处 理理 器器 调调 度度教教 学学 目目 标标了解进程的基本概念了解进程的基本概念熟悉进程的几种状态及转换原因熟悉进程的几种状态及转换原因掌握处理器调度的各种算法掌握处理器调度的各种算法2.1 2.1 进程进程2.1.1 2.1.1 前趋图和程序执行前趋图和程序执行 1.1.1.1.前趋图前趋图前趋图前趋图 有向无循环图有向无循环图有向无循环图有向无循环图 每个结点表示一条语句、一段程序或一个进程每个结点表示一条语句、一段程序或一个进程每个结点表示一条语句、一段程序或一个进程每个结点表示一条语句、一段程序或一个进程 结点间的有向边表示两结点的前趋
2、关系，即进结点间的有向边表示两结点的前趋关系，即进结点间的有向边表示两结点的前趋关系，即进结点间的有向边表示两结点的前趋关系，即进 程执行的先后顺序程执行的先后顺序程执行的先后顺序程执行的先后顺序1 1为初始结点，为初始结点，4 4为终止结点为终止结点例：例：1 1表示输入进程，表示输入进程，2 2、3 3分别表示乘法、分别表示乘法、 加法运算，加法运算，4 4表示输出进程表示输出进程1234并发程序设计并发程序设计/ /顺序程序设计顺序程序设计 使一个程序分成若干个可同时执行的程序模块的使一个程序分成若干个可同时执行的程序模块的程序设计方法称为并发程序设计；相应，串行运程序设计方法称为并发程
3、序设计；相应，串行运行程序方法称为顺序程序设计。行程序方法称为顺序程序设计。特点特点 间断性：共享资源导致程序间断性：共享资源导致程序“执行执行 暂停暂停 执执行行” 失去封闭性：并发执行以及共享资源可能导致结失去封闭性：并发执行以及共享资源可能导致结果变化果变化 不可再现性：不同次执行结果可能不一致不可再现性：不同次执行结果可能不一致程序并发执行的条件程序并发执行的条件 两段程序间无共享变量或对共享变量仅有读两段程序间无共享变量或对共享变量仅有读 操作操作2.1.2 2.1.2 进程的描述与特点进程的描述与特点1.进程的定义进程的定义一个具有一定独立功能的程序在一个数据集一个具有一定独立功能
4、的程序在一个数据集上的一次执行上的一次执行一段程序和它执行时处理的数据一段程序和它执行时处理的数据可与其它程序并发执行的程序的一次执行可与其它程序并发执行的程序的一次执行例如，某一算题为将一千个字符输入到缓冲区，处理后例如，某一算题为将一千个字符输入到缓冲区，处理后 输出到磁带，按并发程序设计思路将该算题分成：输出到磁带，按并发程序设计思路将该算题分成： 模块模块1 1：循环执行：读入：循环执行：读入10001000个字符到输入缓冲区；个字符到输入缓冲区； 模块模块2 2：循环执行：处理输入缓冲区中：循环执行：处理输入缓冲区中10001000个字符，个字符， 然后将然后将10001000个字符
5、送输出缓冲区；个字符送输出缓冲区； 模块模块3 3：循环执行：取出输出缓冲区中：循环执行：取出输出缓冲区中10001000个字符写个字符写 到磁带。让这三个模块同时并发进行。到磁带。让这三个模块同时并发进行。2.2.进程的形成进程的形成 例如：例如：P P为一编译程序，同时为甲、乙两程序服为一编译程序，同时为甲、乙两程序服 务，假定编译程序务，假定编译程序P P从从a a点开始工作，现在正在编点开始工作，现在正在编 译源程序甲，当工作到译源程序甲，当工作到b b点时程序点时程序P P等待磁盘传输等待磁盘传输 信息；这时利用处理器让编译程序信息；这时利用处理器让编译程序P P为源程序乙进为源程序
6、乙进 行编译，编译程序仍从行编译，编译程序仍从a a点开始。点开始。 虽然编译程序虽然编译程序P P只有一个，但是加工对象有甲、只有一个，但是加工对象有甲、乙两个源程序。如果把编译程序乙两个源程序。如果把编译程序P P与服务对象联与服务对象联系起来，则程序系起来，则程序P P为甲服务就说构成了进程为甲服务就说构成了进程P P甲，甲，程序程序P P为乙服务就说构成了进程为乙服务就说构成了进程P P乙乙程程序序甲甲程程序序乙乙编译程序编译程序ab3.3.进程进程的属性的属性结构：结构：同一程序运行在不同数据集上时，构成不同的进同一程序运行在不同数据集上时，构成不同的进程。它包含了数据集和运行在其上
7、的程序及进程控程。它包含了数据集和运行在其上的程序及进程控制块（制块（PCB）；）；并发性：并发性：多个进程可以并发执行，交替执行，走走停停，多个进程可以并发执行，交替执行，走走停停，即一个进程已开始工作但尚未结束之前，另一个进即一个进程已开始工作但尚未结束之前，另一个进程可以开始工作；程可以开始工作；交往性：交往性： 若干个进程间可以相互交往制约，表现为内部若干个进程间可以相互交往制约，表现为内部 逻辑上协调关系及共享资源的间接关系；逻辑上协调关系及共享资源的间接关系；动态性：动态性： 进程是动态的，有个生命期，由创建而产进程是动态的，有个生命期，由创建而产 生，由调度而执行，由撤销而消亡。
8、生，由调度而执行，由撤销而消亡。异步性：异步性： 各进程按独立，未知的速度发展，导致不可再各进程按独立，未知的速度发展，导致不可再 现性。现性。同一程序运行在不同数据集上时，构成不同同一程序运行在不同数据集上时，构成不同的进程。的进程。4.4.进程的进程的基本状态基本状态在单处理器系统中，并发进程轮流占用处在单处理器系统中，并发进程轮流占用处理器，理器，由于发生事件引起状态变化。由于发生事件引起状态变化。 进程的三种基本状态：进程的三种基本状态：等待等待/ /阻塞态：因某事件发生而暂停，等待该事阻塞态：因某事件发生而暂停，等待该事件完成。件完成。就绪态：所需资源均已备齐，等待系统分配中就绪态：
9、所需资源均已备齐，等待系统分配中央处理器，以便运行。央处理器，以便运行。运行态：占有中央处理器正在运行。运行态：占有中央处理器正在运行。 进程的状态变化进程的状态变化l 运行态运行态等待态等待态l 等待态等待态就绪态就绪态l 就绪态就绪态运行态运行态 注意：只有处于就绪态的进程，才有可能转换为运行态；注意：只有处于就绪态的进程，才有可能转换为运行态； 处于等待态的进程在等待结束后只能进入就绪态，处于等待态的进程在等待结束后只能进入就绪态， 不能直接进入运行态；不能直接进入运行态； 处于就绪态的进程只能转处于就绪态的进程只能转 换为运行态，而不能再进入等待态。换为运行态，而不能再进入等待态。 2
10、.1.3 2.1.3 进程控制块进程控制块PCB每一个进程都设置一个每一个进程都设置一个“进程控制块进程控制块”。操作系统。操作系统通过进程控制块来描述各进程的运行情况，并以此通过进程控制块来描述各进程的运行情况，并以此为依据决定如何管理和控制进程运行。为依据决定如何管理和控制进程运行。进程控制块是一个进程存在的唯一标志。最基本的进程控制块是一个进程存在的唯一标志。最基本的进程控制块如图所示。进程控制块如图所示。 PCB的组织方式的组织方式链接方式链接方式不同状态不同状态PCB组成相应队列组成相应队列,若链接字为若链接字为0，表示，表示链接结束，链接结束，就绪队列按进程优先权大小排列，等就绪队
11、列按进程优先权大小排列，等待进程，还可按原因再一次分成小队列待进程，还可按原因再一次分成小队列进程号进程号 下一个链接的进程号下一个链接的进程号PCB1 4PCB2PCB8PCB7PCB6PCB5PCB4PCB33010978PCB9运行态队列运行态队列等待态队列等待态队列就绪态队列就绪态队列空闲队列空闲队列索引方式索引方式各种状态建立独自的索引表，每个表目记录相各种状态建立独自的索引表，每个表目记录相应应PCB在在PCB表中地址表中地址PCB1PCB8PCB7PCB6PCB5PCB4PCB3PCB2运行指针运行指针就绪指针就绪指针等待指针等待指针就绪索引表就绪索引表等待索引表等待索引表2.1
12、.4 进程的控制进程的控制进程的创建进程的创建 每一个进程都有生命期，即从创建到消亡。每一个进程都有生命期，即从创建到消亡。当一个程序模块获得一个数据块和一个进程控当一个程序模块获得一个数据块和一个进程控 制块后就说创建了一个进程。制块后就说创建了一个进程。 进程的创建过程进程的创建过程申请申请PCB为新进程分配内存为新进程分配内存初始化初始化PCB将新进程插入就绪队列将新进程插入就绪队列 进程的终止进程的终止 当一个进程完成了特定的工作后，收回当一个进程完成了特定的工作后，收回 它所占的数据块和一个进程控制块，即它所占的数据块和一个进程控制块，即 撤销了一个进程。撤销了一个进程。 终止过程终
13、止过程 选择新进程占用处理机选择新进程占用处理机 将子孙进程终止将子孙进程终止 将所有占用资源归还给父进程或系统将所有占用资源归还给父进程或系统 将该进程从所在队列移出将该进程从所在队列移出 等待过程等待过程从运行态转为等待态，加入等待队列从运行态转为等待态，加入等待队列唤醒过程唤醒过程使用唤醒原语从等待队列中移出，将使用唤醒原语从等待队列中移出，将PCB中状态改为就绪，插入就绪队列中状态改为就绪，插入就绪队列进程的挂起与激活进程的挂起与激活 进程的挂起进程的挂起将进程静止，运行态进程暂停，就绪态进程暂不将进程静止，运行态进程暂停，就绪态进程暂不接收调度，阻塞态不急转成就绪态接收调度，阻塞态不
14、急转成就绪态例如：阻塞态进程调至外存例如：阻塞态进程调至外存系统负荷过重，将一些进程挂起系统负荷过重，将一些进程挂起操作系统或父进程挂起（子）进程，检查操作系统或父进程挂起（子）进程，检查资源使用或修改协调子进程资源使用或修改协调子进程终端用户挂起进程对程序进行修改终端用户挂起进程对程序进行修改进程的激活进程的激活从静止阻塞态变为活动阻塞态，等待转从静止阻塞态变为活动阻塞态，等待转为就绪态；为就绪态；从静止就绪态转为活动就绪态，等待从静止就绪态转为活动就绪态，等待CPU调度选中调度选中运行运行态态活动就活动就绪绪活动阻塞活动阻塞静止静止就绪就绪静止阻塞静止阻塞挂挂起起激激活活激激活活挂挂起起释
15、放释放释放释放挂起挂起进程状态转换图进程状态转换图3.1 处理机调度的基本概念处理机调度的基本概念3.1.1调度类型调度类型一、高级调度一、高级调度即作业调度或长程调度、接纳调度，从外存调度即作业调度或长程调度、接纳调度，从外存调度选中若干个作业进入内存，并建立进程，插入到选中若干个作业进入内存，并建立进程，插入到就绪队列中就绪队列中分时系统与实时系统无需作业调度分时系统与实时系统无需作业调度所做工作包括：所做工作包括：根据多道程度确定选中作业的道数根据多道程度确定选中作业的道数根据调度算法确定选中哪些作业根据调度算法确定选中哪些作业二、低级调度二、低级调度即进程调度或短程调度、处理器调度即进
16、程调度或短程调度、处理器调度调度方式有：调度方式有：抢占方式抢占方式抢占原则有抢占原则有非抢占方式非抢占方式时间片原则时间片原则短作业优先短作业优先优先权原则优先权原则三、中级调度三、中级调度又称中程调度，即存储管理中的对换又称中程调度，即存储管理中的对换将暂时不运行的进程先调至外存置为挂将暂时不运行的进程先调至外存置为挂 起，等内存空闲再把它们从外存调入改起，等内存空闲再把它们从外存调入改 为就绪态为就绪态3.1.2 选择调度方式与调度算法的若干准则选择调度方式与调度算法的若干准则一、面向用户准则一、面向用户准则1、周转时间、周转时间 带权周转时间带权周转时间W =周转时间周转时间T /系统
17、服务时间系统服务时间Ts2、响应时间响应时间3、截止时间（最迟开始时间）、截止时间（最迟开始时间）4、优先权、优先权二、面向系统的准则二、面向系统的准则1、系统吞吐量、系统吞吐量2、处理机利用率、处理机利用率3、各类资源的平衡利用、各类资源的平衡利用3.2 调度算法调度算法一、先来先服务法一、先来先服务法(FCFS)按照进程进入就绪队列的先后次序来选择进程按照进程进入就绪队列的先后次序来选择进程从后备队列选中作业进入内存从后备队列选中作业进入内存利于利于CPU繁忙的作业繁忙的作业对长作业进程有利，对短作业不利对长作业进程有利，对短作业不利周转时间完成时间到达时间周转时间完成时间到达时间带权周转
18、时间周转时间带权周转时间周转时间/服务时间服务时间二、二、时间片轮转法：时间片轮转法：规定一个时间片规定一个时间片(如如10毫秒毫秒)，每个进程轮流，每个进程轮流地运行一个这样的时间片。当这个时间片结束地运行一个这样的时间片。当这个时间片结束时，就强迫当前运行的进程退出处理器，让其时，就强迫当前运行的进程退出处理器，让其他进程运行。实现方法是使用内部间隔时钟他进程运行。实现方法是使用内部间隔时钟保证所有进程均能获得时间片保证所有进程均能获得时间片时间片的确定时间片的确定系统对时间的要求系统对时间的要求就绪进程的数目就绪进程的数目系统处理能力系统处理能力三、最高优先权法三、最高优先权法每一个进程
19、给出一个优先数，处理器调度每每一个进程给出一个优先数，处理器调度每次选择就绪进程中优先数最小者，让它占用次选择就绪进程中优先数最小者，让它占用处理器运行。处理器运行。该调度算法又分两种：该调度算法又分两种：非抢占式非抢占式适用于批处理系统或要求不严的实时系统适用于批处理系统或要求不严的实时系统抢占式抢占式适合紧迫作业需求及要求较高的实时、分时系统适合紧迫作业需求及要求较高的实时、分时系统优先权的确定优先权的确定静态优先数法静态优先数法进程创建时确定，在运行期间不变进程创建时确定，在运行期间不变例如例如:系统进程、运行时间短或内存需求小的系统进程、运行时间短或内存需求小的进程优先权高进程优先权高
20、通常优先数越高优先权越低通常优先数越高优先权越低动态优先法动态优先法创建时的优先数可随进程运行发生变化创建时的优先数可随进程运行发生变化四、短作业（进程）优先法四、短作业（进程）优先法用于作业调度与进程调度用于作业调度与进程调度降低作业平均等待时间，提高系统吞吐量降低作业平均等待时间，提高系统吞吐量短作业优先短作业优先(SJF)的调度算法，是从后备队列的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。业，将它们调入内存运行。短进程优先短进程优先(SPF)调度算法调度算法从就绪队列中选出一估计运行时间最短的进程，从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再完成，或发生某事件而被阻塞放弃处理机时，再重新调度。重新调度。
