搜索
第2章进程管理(1)本章要点基础：进程的描述与控制策略:进程调度实现：互斥与同步避免：死锁与饥饿解决：几个经典问题关于：进程通信生产者消费者输入进程计算进程计算进程打印进程教学目的及要求（1）理解和掌握进程的概念、描述（2）理解和掌握进程的状态及转换（3）理解和掌握进程控制教学重点（1）进程的概念、描述、状态及转换（2）进程控制教学难点（1）进程的概念（2）进程状态的转换在传统的操作系统中，程序不能独立运行，作为资源分配和独立运行的单位是进程。操作系统所具有的四大特征也都是基于进程而形成的，并可从进程的观点来研究操作系统。显然，在操作系统中，进程是一个极其重要的概念。因此，本章专门来描述进程。2.1进程的基本概念程序的执行是顺序执行，即必须在一个程序执行完成后，才允许另一个程序执行；在多道程序环境下，则允许多个程序并发执行。程序的这两种运行方式间有着显著不同。也正是程序并发执行时的特征，才导致了在操作系统中引入进程的概念。因此，有必要先对程序的顺序和并发执行方式做简单的描述。一、程序的顺序执行及特征1程序的顺序执行程序是一个在时间上按严格次序前后相继的操作序列，是一个静态的概念。一个具有独立功能的程序独占处理机直至得到最终结果的过程称为程序的顺序执行。I1C1P1I2P2C22程序顺序执行时的特征顺序性：程序顺序执行时，其执行过程可看做一系列严格按程序规定的状态转移过程，也就是每执行一条指令，系统就从上一个执行状态转移到下一个执行状态，且上一条指令的执行结束是下一条指令执行开始的充分必要条件；输入→计算→打印的顺序性2程序顺序执行时的特征封闭性：程序是在封闭的环境下执行。即程序在运行时独占全部资源，资源的状况只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。可再现性：顺序执行的最终结果可再现是说它与执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。二、前趋图前趋图（PrecedenceGraph）是一个有向无循环图，记为DAG（DirectedAcyclicGraph），用于描述进程之间执行的前后关系。结点间的有向边用于表示两个结点之间存在的偏序（PartialOrder）或前趋关系。前趋关系用→表示。三、程序的并发执行及其特征1程序的并发执行I1C1P1I2C2P2I3C3P3I4C4P4输入进程是计算进程的前提，计算进程是打印进程的前提。I1→c1→p1：顺序执行生产者消费者输入进程计算进程计算进程打印进程2*3N*m123453333334567N+m-1时间复杂度空间复杂度2程序并发执行时的特征1）间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。从而使得有些程序在执行中出现走走停停的情况。如上例中诸进程之间极易出现这种情况。2）失去封闭性：程序并发执行时，由多个程序（进程）共享资源，因而对资源的状态由多个程序来改变，从而失去了封闭性。3）不可再现性：推进的顺序不可再现程序并发执行引发的问题协调各程序的执行顺序例如，当输入的数据还未全部输入内存时，计算必须等待多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果选择哪些、多少个程序进入内存运行：根据资源等情况决定内存中的执行程序哪个先执行：调度算法内存如何有效分配：内存资源非常宝贵，内存管理四进程的特征与状态定义：可并发执行的程序，在一个数据集合上的运行过程。申请/拥有资源-----调度单位（线程）程序：静态的概念，是指令和数据的集合，可长期存储进程和程序的对应关系：一个程序对应一个或多个进程一个进程对应一个或一段程序。1）结构特征：程序段+相关数据段+PCB2）动态性：进程是运行的程序。3）并发性4）独立性5）异步性1、进程的特征进程和线程的区别进程是程序的一次执行，拥有资源的最小实体，在传统的OS中，进程也是系统调度的最小单位。线程是程序的一次相对独立的运行过程，现代OS中，线程也是系统调度的最小单位。线程没有资源，它是依赖于进程存在的。最基本的两个特征1）结构特征进程实体：程序段+相关数据段+PCB2）动态性进程是运行的程序。它由创建而产生、由调度而执行，由撤消而消亡。3）并发性：多个进程同时存在与内存，且能在一段时间内同时运行。如分时系统中按时间片运行。相当于身份证4）独立性进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。5）异步性各进程按照各自独立的、不可预知的速度向前推进，或者说，进程按异步方式运行。引入进程产生的问题增加空间的开销：为进程建立数据结构（PCB）增加时间开销：管理、协调、跟踪进程；填写和更新数据结构、切换进程、保护现场更难控制：协调多个进程竞争和共享资源，如何预防并解决多个进程因为竞争资源而出现故障（如死锁、饥饿）处理机的竞争尤为突出2进程的三种基本状态进程执行时的间断性，决定了进程可能具有多种状态。作业的状态：提交、后备、执行、完成进程的状态：就绪（Ready）、运行、阻塞进程是运行的程序，所以不存在提交状态；作业运行的环境是批处理系统所以无阻塞状态。1）就绪(Ready)状态已经分配到除CPU之外的所有资源，可谓“万事俱备，只欠CPU”。就绪队列：在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为~~~~。2）执行状态进程获得了包括CPU在内的所需的全部资源，程序正在执行。3）阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态成为~~~~（等待状态）单处理机系统中，只有一个进程处于执行状态；多处理机系统中，多个进程处于执行状态通常把处于阻塞状态的进程排成一个队列，称为阻塞队列。进程的三种基本状态转换就绪阻塞执行I/O请求结束新状态在有些操作系统中，将进程状态分为5种，即还有新状态、终止状态。3挂起状态1）引入挂起状态的原因（1）终端用户的请求：修改程序（2）父进程请求：对子进程的修改等（3）负荷调节的需要：资源不够用（4）操作系统的需要：检查资源利用情况就绪TASK_RUNNINGfork()执行拥有CPU不可打断睡眠TASK_UNINTERRUPTIBLE可打断睡眠TASK_INTERRUPTIBLEdo_exit()时间片到schedule()等待资源schedule()sleep_on()唤醒wake_up()僵尸TASK_ZOMBIE暂停TASK_STOPPEDptrace()schedule()收到信号SIG_CONT唤醒wake_up()或收到信号等待资源schedule()interruptible_sleep_on()Linux下进程状态的转换2）进程状态的转换在引入挂起状态后，又增加了挂起状态（静止状态）到非挂起状态（活动状态）的转换；以及反转换。（1）活动就绪Readya→静止就绪Readys:suspend原语（2）活动阻塞Blockeda→静止阻塞Blockeds:suspend原语（3）静止就绪→活动就绪:active原语（4）静止阻塞→活动阻塞:active原语执行挂起活动阻塞静止阻塞活动就绪静止就绪激活挂起激活五、进程控制块1、概念进程控制块PCB：ProcessControlBlock为了描述和控制运行进程的运行，系统为每个进程定义了一个数据结构，成为进程控制块。（/include/linux/sched.h中structtask_struct）PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。进程控制块随着进程的创建而创建，即创建一个进程，就是创建一个PCB；进程控制块随着进程的撤消而撤消，即撤消一个进程，就是撤消进程PCB。因此，PCB是进程的存在的惟一标志。PCB是进程的存在的惟一标志1）进程标识符（processidentifier,PID）进程的标识符ID：系统指定该进程的父进程标识符FID：系统指定进程的用户标识符UID:如计算进程（用户命名）2）处理机状态：处理机的各种寄存器中的内容。通用寄存器指令计数器PC程序状态字PSW用户栈指针：系统栈2进程控制块中的信息进程控制块PCB的内容相当繁多（linux2.6.8中占134行），只要求做大概了解，知道有哪几类即可3）进程调度信息进程状态进程优先级进程调度所需的其它信息事件：指进程由状态转变为阻塞状态所等待发生的事件，阻塞原因。4）进程控制信息（其他信息）程序和数据的地址进程同步和通信机制：实现进程同步所需的信息，如计算进程和输入输出进程同步资源清单：进程申请的资源，得到的资源，还需要的资源，如内存链接指针：nextPCB1）链接方式Linux采用链接方式具有同一状态的PCB，组成PCB队列就绪队列、阻塞队列、空闲队列2）索引方式系统根据所有进程的状态建立几张索引表保存各索引表在内存的首地址记录在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。3进程控制块的组织方式单一队列可能造成队列太长，以及进程可能处于多个状态，从而造成效率太低。Linux进程控制块的基本成员（1）1处理机硬件资源1）用户编程可访问的寄存器对于CISC计算机通常有8---32个对于RICS计算机通常有100多个通用寄存器2）控制和状态寄存器程序计数器算术运算条件码各种状态信息3）内存指针指向进程的系统栈的栈指针指向虚存空间的段表指针指向虚存的页表指针Linux进程控制块的基本成员（2）2进程控制软件信息1）进程标识：进程的标识符ID该进程的父进程标识符FID进程的用户标识符UID2）调度和状态信息进程状态（运行、就绪、等待）进程优先级：可能由用户指定与调度算法有关的成员变量进程正在等待的时间Linux进程控制块的基本成员（3）3）数据结构：表示进程与另一个进程或具有某一特定优先级的一组进程的关系。系统为支持这些结构需要包含指向其他进程的指针。4）进程间通信：与通信有关的各种标记变量等。5）进程访问权限：6）资源的使用和所有：已打开的文件附录：1）LinuxKernal2.6.8的PCB.txt2）LinuxKernal2.4.20的PCB.txt/include/linux/sched.h中的数据结构structtask_struct（该部分内容以及部分LinuxKernal已传到网上）2.2进程控制进程控制是进程和处理机管理的一个重要任务。进程控制，系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。一般，我们把系统态下执行的某些具有持定功能的程序段称为原语。原语的种类机器指令级的：其特点是执行期间不允许中断，它是一个不可分割的基本单位。功能级：其特点是作为原语的程序段不允许并发执行。用于进程控制的原语有：创建原语，撤消原语，阻塞原语，唤醒原语等。1进程图（ProcessGraph）进程图是用于描述一个进程的家族关系的有向树。在进程Pi创建了进程Pj之后，称Pi是Pj的父进程，Pj是Pi的子进程。子进程可以继承父进程所拥有的所有资源。为了标识进程之间的家族关系，在PCB中设置了家族关系表项，以标明自己的父进程以及所有的子进程。一、进程的创建1）用户登录：合法用户进程2）作业调度：运行作业时，分配资源，创建进程3）提供服务：如打印进程4）应用请求：如输入、计算、打印三进程2引起创建进程的事件/创建进程的原因123：系统内核创建进程4：基于应用程序的请求而创建3进程的创建(CreationofProcess)1）引起创建进程的事件发生2）调用进程创建原语3）创建步骤：申请空白PCB为新进程分配资源初始化进程控制块将新进程插入就绪队列二进程的终止（TerminationofProcess）1）正常结束：进程顺利