操作系统原理_方敏_进程管理

《操作系统、实验》第三章进程管理操作系统课程组第2页内容回顾作业调度算法的性能分析用户接口单道程序环境下作业调度算法性能分析多道程序环境下作业调度算法性能分析结论FCFSSJFHRP作业控制级接口程序级接口系统功能调用：•程序的状态•特权指令•访管指令•系统功能调用的原理第3页一、进程的定义曾经的定义进程是程序的一次执行；进程是可以和别的计算并发执行的计算；进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。……教材中的定义进程是程序的一次执行，该进程可与其它进程并发执行；它是一个动态的实体，在传统的操作系统设计中，进程既是资源的基本分配单元，也是基本的执行单元。第4页二、为什么要引入进程的概念？顺序执行程序指的是在有多个程序需要执行的情况下，处理器严格按照某一顺序按序执行，每次只执行一个程序。其实质是单道程序系统。特点顺序性资源独占性可再现性不足效率低下第5页二、为什么要引入进程的概念？多道程序设计同一时刻内存中存放了多个作业，处理器交替运行不同的作业。提高了系统的效率，尤其是资源利用率。特点多道宏观上并行微观上串行问题系统管理复杂化程序A程序BCPUI/Otime资源第6页二、为什么要引入进程的概念？程序并发执行带来的新特征资源共享性；独立性和制约性；程序执行的间断性；结果不可再现。第7页二、为什么要引入进程的概念？与时间有关的错误…a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}………a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}……因为这种错误和相对执行速度有关，因此称为与时间有关的错误。服务器售票员A售票员B第8页二、为什么要引入进程的概念？结论：程序的并发执行使得程序的执行情况不可预见，其结果不再唯一，成为一个动态的过程。而程序是一个静态的概念，不再能切实反映程序执行的各种特征（独立性、并发性、动态性）。“进程”MIT：60年代初，MULTICS系统中提出；IBM：CTSS/360系统，称为“任务”(task)。第9页内存三、进程的定义与控制进程与程序的区别和联系（1）程序是静态的，进程是动态的。程序是有序代码的集合；进程是程序的一次执行。（2）进程是暂时的，程序的永久的。进程是一个变化的过程，有生命周期，暂时存在，程序没有生命周期，可长久保存。（3）进程还是操作系统资源分配和保护的基本单位，程序没有此功能。（4）进程与程序的对应关系。通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。（5）进程与程序的结构不同。磁盘第10页三、进程的定义与控制进程的组成PCB•ProcessControlBlock灵魂，进程存在的唯一标志。数据程序•程序：描述了进程要完成的功能，是进程执行时不可修改的部分。•数据：进程执行时用到的数据（用户输入的数据、常量、静态变量）。工作区•工作区：参数传递、系统调用时使用的动态区域（堆栈区）。实体第11页三、进程的定义与控制进程控制块（PCB）定义：是操作系统用来记录进程详细状态和相关信息的基本数据结构，它和进程是一一对应的，是进程存在的唯一标识。作用：提供进程的各种信息，以便操作系统控制和管理。第12页三、进程的定义与控制类型内容作用标识信息1）进程标识2）用户标识3）父进程标识标识一个进程现场信息1）CPU通用寄存器内容2）CPU状态寄存器内容3）栈指针等记录处理机现场信息，以备恢复之用控制信息1）进程状态2）调度信息3）队列指针4）位置信息5）资源占用信息……用于进程的调度管理PCB结构第13页三、进程的定义与控制操作系统对PCB的管理：集中统一管理内存PCB表PCBPCBPCBPCB辅存非常驻信息非常驻信息非常驻信息非常驻信息第14页三、进程的定义与控制进程的创建操作系统为进程创建进程控制块和分配地址空间的过程就是进程创建的过程。创建进程标识分配内存和其它资源初始化进程控制块将创建的进程置于就绪队列PCBPCBPCBPCB就绪队列第15页三、进程的定义与控制进程的执行运行Running被调度时间片用完，中断资源释放或事件完成阻塞Blocked等待资源和事件进程占有处理机，处理机正在执行该进程的程序。进程已获得除处理机外的所需资源，等待分配处理机执行。也叫等待、挂起、睡眠态，此时进程因等待某种条件（如I/O操作或进程同步）无法运行。引起进程阻塞的原因很多，系统将根据不同的阻塞原因将进程插入某个相应的阻塞队列中。就绪Ready第16页三、进程的定义与控制进程状态转换及原因状态转换原因就绪—运行进程被调度程序选中占用CPU。运行—阻塞进程出让CPU，等待系统分配资源或某些事件的发生，如：暂时不能访问某一资源，操作系统尚未完成服务，系统正在初始化I/O设备，等待用户的输入信息等。阻塞—就绪处于等待队列中的进程，当其等待的事件已经发生，或等待的资源可用时，此进程将进入就绪队列竞争CPU。运行—就绪进程分配的时间片已用完，或者在中断机制下，有更高优先级的进程进入系统，这时进程进入就绪队列等待下一次被选中而占用CPU。第17页三、进程的定义与控制运行就绪阻塞被调度时间片用完，中断资源释放或事件完成等待资源和事件新建创建完毕结束结束执行五种进程状态转换第18页三、进程的定义与控制七种进程状态转换第19页三、进程的定义与控制进程的组织管理——队列PCBPCBPCBPCBCPUPCBPCBPCBPCB等待队列1PCBPCBPCBPCB等待队列n就绪队列时间片用完完成等待完成等待入队执行结束第20页三、进程的定义与控制进程控制进程控制的主要任务是：创建和撤销进程以及进行进程间的状态转换。这包括：创建一个进程撤销一个进程改变进程状态实现进程间的通信这些由操作系统内核通过执行各种原语完成。第21页三、进程的定义与控制原语（primitive）由若干条机器指令构成的可完成特定功能的程序段，它是一个“原子操作(atomicoperation)”过程，作为一个整体而不可分割－－要么全都完成，要么全都不做（类似数据库中的“事务”）。原语主要是通过屏蔽各种中断和固化技术保证其原子性的。分类进程控制原语进程通信原语进程管理原语其他方面的原语1、进程创建原语2、进程撤销原语3、进程阻塞原语4、进程唤醒原语5、进程挂起原语6、进程激活原语第22页三、进程的定义与控制进程的特征并发性：执行时间可以重叠；动态性：有生命周期，存在不同的状态；独立性：独立执行，是资源分配和调度的独立单位；制约性：虽然独立执行，但可能存在相互制约关系；异步性：各进程执行时间相对独立，不确定；结构性：拥有固定结构。第23页四、进程调度进程调度：就是按照一定的算法，从就绪队列中选择某个进程占用CPU的方法——对CPU资源进行合理的分配使用，以提高处理机利用率，并使各进程公平得到处理机资源。运行就绪阻塞被调度时间片用完，中断资源释放或事件完成等待资源和事件第24页四、进程调度确定进程调度算法原则进程调度的任务是：有效的选择占用CPU的进程，控制协调系统安全、高效的工作。设计者系统用户•公平性：每个进程（不论优先级）都有机会被运行。•较大的吞吐量。•及时性：响应速度要快。•较短的周转时间：不应当让用户等待时间过长。第25页四、进程调度进程调度算法先来先服务调度算法(FCFS,FirstComeFirstServed)特点：简单、可靠；容易理解、实现方便；非抢占式的。缺点：作业的平均等待时间过长，系统效率低下；不适合于分时系统。PCBPCBPCBPCB就绪队列CPU公平性吞吐量及时性周转时间第26页四、进程调度基于优先数的调度算法(PrioritySchedulingAlgorithm)思想：给每一个进程设置一个优先数(优先级)，系统在调度时优先选择具有高优先级的进程占用CPU。具有相同优先数的进程按照FCFS算法执行。优先数的确定：运行前：可根据外设的使用情况，运行时间的长短，紧急程度，重要程度等因素确定。运行中：1）静态优先数法：进程创建时就规定好它的优先数，这个数值在进程运行时不变。2）动态优先数法：进程的优先数在执行过程中可以根据情况变化而改变(UNIX中采用的方法)。第27页四、进程调度优点：灵活。通过不同的优先级设置策略，可以强调不同的性能。实现也较为方便。通过优先级的动态调整，可以平衡系统性能。问题：静态优先数法——无穷阻塞(IndefiniteBlocking)进程占用CPU的方式非抢占式(不可剥夺式)——FCFS。抢占式(可剥夺式)——会使进程频繁调度，在设计时还应考虑进程切换的时间开销。第28页四、进程调度时间片轮转法(RR,RoundRobin)特点：专门为分时系统设计。类似于FCFS算法但是增加了抢占及进程间的切换功能。思想：系统规定一个时间长度(时间片/时间量)作为允许一个进程运行的时间，如果在这段时间该进程没有执行完，则必须让出CPU等待下一次分配的时间片。原理PCBPCBPCBPCBCPUPCBPCBPCBPCB等待队列1PCBPCBPCBPCB等待队列n就绪队列时间片用完完成等待完成等待执行第29页四、进程调度时间片的选择方法固定时间片：分配给每个进程时间片相等；可变时间片：根据进程的不同要求对时间片的大小实时修改。优点：公平性，及时性。问题：时间片大小的确定？过大：退化为FCFS算法，响应时间变长。过小：一个任务需要多个时间片执行，增加了进程切换次数，响应时间变长。想法：能不能在减少进程切换次数的同时，又能保持较高的响应速度？第30页四、进程调度多级反馈队列调度算法(MultilevelFeedbackQueueScheduling)思想：引入多个就绪队列，通过对各队列的区别对待，达到一个综合的调度目标。原理：CPU降低进程优先级完成PCBPCBPCBPCB最高优先级队列PCBPCBPCBPCB次高优先级队列PCBPCBPCBPCB低优先级队列执行时间递增目前最为通用、灵活的CPU调度算法，但也是最为复杂的。第31页五、进程间的相互作用同步定义：进程之间这种相互合作、协同工作的关系称为进程的同步。简单说来就是：多个相关进程在执行次序上的协调。制约关系：直接制约。第32页五、进程间的相互作用互斥定义：当多个进程因为争夺临界资源而互斥执行称为进程的互斥。制约关系：间接制约。临界资源：也称独占资源，是指在一段时间内只允许一个进程访问的资源。例如打印机，磁带机，也可以是进程共享的数据、变量等。第33页五、进程间的相互作用临界资源处理不当带来的问题执行结果错误…a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}………a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}……服务器售票员A售票员B临界资源临界区：与临界资源操作相关的程序段。第34页五、进程间的相互作用死锁（DeadLock）在并发系统中，程序执行结果的正确性不仅取决于自身的正确性，还与其在执行过程中能否正确的与其它进程实施同步或互斥有关。必须对临界资源的访问进行控制。第35页五、进程间的相互作用互斥解决方案关中断法(开关中断指令)也称为“硬件锁”，是实现互斥最简单的方法。做法：每个进程在进入临界区后先关中断，屏蔽其它请求，在离开之前再开中断。优点：实现简单。缺点：中断被关掉后，CPU不再响应任何外部事件，此时进程将会独占CPU，直至关闭中断，如果中断关闭时间过长，会造成严重后果，因此把开关中断的权力交给用户进程是很不明智的。第36页五、进程间的相互作用锁变量法(测试和设置指令)做法：设置一个共享(锁)变量W，初值为0。当一个进程想进入其临界区时，它首先测试这把锁。如果锁的值为0，则进程将其置为1并进入临界区。若锁已经为1，则进程等待直到其变成0。于是，0就表示临界区内没有进程，1表示已经有某个进程进入了