第二讲进程的描述及处理器调度

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