校园导航系统课程设计报告

第二章进程管理第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程第二章进程管理2.1进程的基本概念2.1.1程序的顺序执行及其特征1.程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;第二章进程管理图2-1程序的顺序执行(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;第二章进程管理2.程序顺序执行时的特征(1)顺序性：处理机的操作必须严格按照程序所规定的顺序执行(2)封闭性：程序在执行时独占系统的全部资源，因此机器资源状态的改变只与执行的程序有关，与外界环境无关(3)可再现性：只要初始条件相同，一个程序的多次重复执行，将得到相同的结果第二章进程管理2.1.2前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”。→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。第二章进程管理每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。Ii→Ci→Pi和S1→S2→S3图2-2前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图第二章进程管理对于图2-2(a)所示的前趋图，存在下述前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9或表示为：P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系：S2→S3,S3→S2第二章进程管理•【联48】已知一个求值公式：•若A、B已赋值，试画出该公式求值过程的前趋图。2(3)/(5)ABBA第二章进程管理2.1.3程序的并发执行及其特征1.程序的并发执行图2-3并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4第二章进程管理在该例中存在下述前趋关系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段：S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bP1P2P3P4I1I2I3I4C1C2C3C4第二章进程管理图2-4四条语句的前趋关系S1S2S3S4S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b第二章进程管理2.程序并发执行时的特征程序的并发执行是指二个或二个以上的程序或程序段可在同一时间间隔内同时执行。程序的并发执行极大提高了资源利用率和系统吞吐量，也产生了不同于顺序执行的新特征：1.间断性：由于资源共享和相互合作，并发执行的程序间形成了相互制约关系，导致程序的运行过程出现“执行-暂停-执行”的现象2.失去封闭性：程序在执行时与其他并发执行的程序共享系统的资源，因此资源状态的改变还与其他程序有关3.不可再现性：同样的初始条件，一个程序的多次重复执行，可能得到不同的结果第二章进程管理•例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N∶=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。•(1)N∶=N+1在Print(N)和N∶=0之前，此时得到的N值分别为n+1,n+1,0。•(2)N∶=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1。•(3)N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0。第二章进程管理2.1.4进程的特征与状态1.进程的特征和定义1)结构特征：从结构上说，每个进程实体中除了相应的程序段、数据段外，必须包含一个数据结构进程控制块PCB2)动态性：进程是程序的一次执行过程，因此是都动态的。动态性还表现在进程具有一定的生命期，它必须由创建而产生、由调度而执行、由撤销而消亡。3)并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行。只有为程序创建进程后，多个程序才能正确地并发运行，并发是引入进程的目的。第二章进程管理4)独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位5)异步性：进程可按各自独立、不可预知的速度向前推进第二章进程管理较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。第二章进程管理•【联1】以下对进程的描述中，错误的是•A进程是动态的概念•B进程执行需要处理机•C进程是有生命期的•D进程是指令的集合第二章进程管理•【联3】一个进程是•A有处理机执行的一个程序•B一个独立的程序+数据集•CPCB结构、程序和数据的组合•D一个独立的程序第二章进程管理•【联5】在单处理机系统中实现并发技术后，————A各进程在某一时刻并行运行，cpu与i/o设备间并行工作B各进程在一个时间段内并行运行，cpu与i/o设备间串行工作C各进程在一个时间段内并行运行，cpu与i/o设备间并行工作D各进程在某一时刻并行运行，cpu与i/o设备间串行工作第二章进程管理总结：进程与程序的区别•1.进程是程序的执行，所以进程属于动态概念，而程序是一组指令的有序集合，是静态的概念•2.进程既然是程序的执行，或者说是“一次运行活动”，因而它是有生命过程的，从投入运行到运行完成，它的存在是暂时的，而程序的存在时永久的•3.进程是程序的执行，因此进程的组成应包括程序和数据。除此之外，进程还由记录进程状态信息的PCB组成。•4.进程是竞争计算机系统有限资源的基本单位•5.一个进程能与其他进程并发地活动•6.一个程序可能对应多个进程，一个进程可以包含多个程序。进程和程序无一一对应关系第二章进程管理2.进程的三种基本状态1)就绪(Ready)状态：进程已获得除cpu以外的所有必要资源，只要得到cpu便可立即执行。可以有多个就绪状态的进程2)执行状态：进程已得到cpu，其程序正在cpu上执行3)阻塞状态：正在执行的进程因某种事件（如I/O请求）的发生而暂时无法继续执行，只有等相应事件完成后，才能去竞争cpu第二章进程管理图2-5进程的三种基本状态及其转换就绪阻塞执行时间片完进程调度I/O完成I/O请求第二章进程管理3.挂起状态不少系统中，进程只有上述三种基本状态，但另些系统中增加了挂起状态，其实质使进程不能继续执行，即挂起后的进程处于就绪状态，它也不能参加cpu的竞争，被挂起的进程处于静止状态，相反，没有被挂起的进程处于活动状态，只有通过激活才能得以实现1)引入挂起状态的原因(1)终端用户的请求。用户发现可疑问题，希望暂时使自己的程序静止下来，以便研究其执行情况或修改第二章进程管理(2)父进程请求。父进程希望挂起某个子进程，考查或修改它，或协调各子进程之间的活动(3)负荷调节的需要。当负荷较重，影响对实时任务的控制(4)操作系统的需要。检查运行中的资源使用情况等另外，挂起进程可以腾出内存空间给其它就绪进程使用第二章进程管理2)进程状态的转换(1)活动就绪→静止就绪。(2)活动阻塞→静止阻塞。(3)静止就绪→活动就绪。(4)静止阻塞→活动阻塞。第二章进程管理图2-6具有挂起状态的进程状态图活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O第二章进程管理•【联8】分配到必要的资源并获得处理机时间的进程状态是•A就绪•B运行•C阻塞•D撤销第二章进程管理•【联9】当一个进程处于这样的状态时，______，称为阻塞状态•A它正等着输入一批数据•B它正等着进程调度•C它正等着分给它一个时间片•D它正等着进入内存第二章进程管理用户作业录入提交收容完成运行就绪等待作业调度执行作业调度批处理系统中作业处理及状态第二章进程管理•【联10】某运行中的进程要申请打印机，它将变为___•A就绪态•B阻塞态•C创建态•D撤销态第二章进程管理•【联11】以下进程状态转变中，___转变时不可能发生的。•A运行----就绪•B运行----阻塞•C阻塞----运行•D阻塞----就绪第二章进程管理•【联13】一个进程的基本状态可以从其他两种基本状态转变过来，这个基本状态一定是就绪状态第二章进程管理•【联19】进程自身决定______•A从运行状态到阻塞状态•B从运行状态到就绪状态•C从就绪状态到运行状态•D从阻塞状态到就绪状态第二章进程管理•【联20】以下可能导致一个进程从运行状态变为就绪状态的事件是___•A一次I/O操作结束•B运行进程需要做I/O操作•C运行进程结束•D出现了比现在进程优先级更高的进程第二章进程管理•【联21】一个进程释放一种资源有可能导致一个或几个进程_____•A就绪变运行•B运行变就绪•C阻塞变运行•D阻塞变就绪第二章进程管理【联22】一次i/o操作的结束，有可能导致___A一个进程由阻塞变为就绪B几个进程由阻塞变为就绪C一个进程由阻塞变为运行D几个进程由阻塞变为运行第二章进程管理2.1.5进程控制块1.进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。PCB要被系统频繁访问，必须常驻内存。第二章进程管理2.进程控制块中的信息1)进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。第二章进程管理2)处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时，许多信息都存放在寄存器中，当处理机被中断时，所有这些信息都必须保持在PCB中，以便在该进程重新执行时，能从断点继续执行。第二章进程管理3)进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括：①进程状态，指明进程的当前状态，作为进程调度和对换时的依据；②进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；④事件，是指进程由执行状