进程管理--4.ppt

1操作系统进程管理操作系统进程管理张其亮张其亮 Email:2内内 容容l进程概念进程概念l进程状态和控制进程状态和控制l进程调度进程调度l进程互斥与同步进程互斥与同步l死锁死锁3概概 要要目前的计算机系统基本是多道系统，而系统中一般只有一个处理目前的计算机系统基本是多道系统，而系统中一般只有一个处理机。多机。多个程序竞争个程序竞争使用处理机，所以有效的管理分配处理机非常使用处理机，所以有效的管理分配处理机非常重要。重要。为了准确描述多道系统中多为了准确描述多道系统中多个程序的个程序的运行状况，以及资源的管理运行状况，以及资源的管理分配情况，引入了进程的概念。分配情况，引入了进程的概念。4程序的执行程序的执行l程序的执行程序的执行u程序概念程序概念 一组一组有序有序的的操作操作序列序列 有序：指操作必须按照严格的先后顺序有序：指操作必须按照严格的先后顺序 操作：指由机器指令、高级语言语句实现的某种特定功能操作：指由机器指令、高级语言语句实现的某种特定功能l程序执行方式程序执行方式顺序执行顺序执行并发执行并发执行5l程序的顺序执行程序的顺序执行早期的计算机是单道系统，每次只能执行一个用户作业，该作业早期的计算机是单道系统，每次只能执行一个用户作业，该作业独占资源。独占资源。u若有多个用户作业需要在系统中运行时，只能执行完一个作业后若有多个用户作业需要在系统中运行时，只能执行完一个作业后再运行另外一个作业。再运行另外一个作业。u当一个作业由多个程序或程序段组成，则必须执行完一个程序或当一个作业由多个程序或程序段组成，则必须执行完一个程序或程序段后在执行另外一个。程序段后在执行另外一个。6l单道系统中的顺序执行单道系统中的顺序执行程序本身操作必须按照顺序执行程序本身操作必须按照顺序执行多个程序或程序段只能使用处理机依次顺序执行，而不能同时执多个程序或程序段只能使用处理机依次顺序执行，而不能同时执行。行。I1C1P1P2I2C27l顺序程序特点：顺序程序特点：顺序性。顺序性。封闭性。封闭性。程序程序 运行时独占全部资源，只有该程序才能改变资源的状态运行时独占全部资源，只有该程序才能改变资源的状态,一旦一旦开始运行，其执行结果不受外界因素的影响。开始运行，其执行结果不受外界因素的影响。可再现性。可再现性。如果程序在不同时间重复运行，只要初始条件相同，结果就相同如果程序在不同时间重复运行，只要初始条件相同，结果就相同8l程序的并发执行程序的并发执行 出现多道系统后，处理机可以同时运行多个用户的程序，程序的执出现多道系统后，处理机可以同时运行多个用户的程序，程序的执行方式也发生了改变，从顺序执行到并发执行。行方式也发生了改变，从顺序执行到并发执行。并发执行概念并发执行概念 若干个程序或程序段可以使用处理机同时执行，它们在执行时时若干个程序或程序段可以使用处理机同时执行，它们在执行时时间可以重叠。间可以重叠。9程序1程序2程序3I1I3I2P1C1C2P2C3P3时间10l并发执行特点：并发执行特点：并发行并发行 一个程序或程序段的执行尚未结束，另一个程序或程序段的执行一个程序或程序段的执行尚未结束，另一个程序或程序段的执行已经开始已经开始开放性开放性 程序运行环境开放，运行时要受到外界的影响，因为并发程序共享程序运行环境开放，运行时要受到外界的影响，因为并发程序共享系统资源系统资源间断性间断性不可再现性不可再现性 由资源的开放性引起的由资源的开放性引起的11例如：有两个循环程序例如：有两个循环程序A和和B，它们共享一个变量，它们共享一个变量N。程序。程序A每执每执行一次时都要做行一次时都要做N：N1操作；程序操作；程序B每执行一次时，都要每执行一次时，都要做做print（N）操作，然后再将）操作，然后再将N置成置成“0”，程序，程序A和和B以不同以不同的速度运行。（假定某时刻变量的速度运行。（假定某时刻变量N的值为的值为n）l（1 1）N：N1在在print（N）和）和N：0之前，此时得到的之前，此时得到的N值分别为值分别为n1，n1，0（2）N：N1在在print（N）和）和N：0之后，此时得到的之后，此时得到的N N值分别为值分别为n，0，1（3）N：N1在在print（N）和）和N：0之间，此时得到之间，此时得到的的N N值分别为值分别为n，n1，012进进 程程l为什么要引入进程？为什么要引入进程？程序本身是一个静态的内容，不能表现其运行过程。程序本身是一个静态的内容，不能表现其运行过程。一个程序在运行时，可能有多个过程，单靠程序的概念无法对多一个程序在运行时，可能有多个过程，单靠程序的概念无法对多个过程进行描述个过程进行描述（当我们打开（当我们打开2个个qq时会看到时会看到windows进程中会存在进程中会存在2个个qq.exe进程，进程，但它们都运行的是同一个但它们都运行的是同一个qq程序，用程序如何描述呢？）程序，用程序如何描述呢？）*引入进程描述程序在执行过程中的动态行为。引入进程描述程序在执行过程中的动态行为。13进程概念进程概念 l进程的定义和特性进程的定义和特性u进程的定义进程的定义 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，它是系统进行资源分配和调度的一个独立单位动，它是系统进行资源分配和调度的一个独立单位进程是程序的一次执行过程进程是程序的一次执行过程u进程特性进程特性动态性动态性并发性并发性内存中可同时存在多个进程，能在一段时间内同时执行。内存中可同时存在多个进程，能在一段时间内同时执行。异步性：它们按照不可预知的速度各自独立的前行。异步性：它们按照不可预知的速度各自独立的前行。独立性：独立性：资源分配的独立单位，能独立运行的基本单位资源分配的独立单位，能独立运行的基本单位结构性：结构性：进程实体进程实体 （PCB）描述进程运行过程中的各种状态信息）描述进程运行过程中的各种状态信息14程序与进程的区别程序与进程的区别程序程序是一组指令的有序集合，本身无运行的含义。进程是程序执是一组指令的有序集合，本身无运行的含义。进程是程序执行的动态活动过程，随程序的执行而行的动态活动过程，随程序的执行而 诞生，随程序的结束而消亡诞生，随程序的结束而消亡独立性，是指进程是一个能独立运行、独立分配资源和独立调度独立性，是指进程是一个能独立运行、独立分配资源和独立调度的基本单位；凡未建立进程的程序，都不能作为一个独立的单位的基本单位；凡未建立进程的程序，都不能作为一个独立的单位参加运行。参加运行。程序和进程无一一对应关系。一个程序运行过程中可以产生多个程序和进程无一一对应关系。一个程序运行过程中可以产生多个进程，一个进程在运行过程中又可以顺序地执行多个程序。进程，一个进程在运行过程中又可以顺序地执行多个程序。（在分时系统中多个终端用户同时进行（在分时系统中多个终端用户同时进行c程序编译，这样一个程序编译，这样一个c编译编译程序对应多个用户进程，而对每个用户进程来说，编译过程中会程序对应多个用户进程，而对每个用户进程来说，编译过程中会用到预处理、语法分析、优化等多个进程）用到预处理、语法分析、优化等多个进程）15进程状态及转换进程状态及转换思考：进程在运行过程中会存在多种状态，为什么？思考：进程在运行过程中会存在多种状态，为什么？16进程状态及转换进程状态及转换u进程的状态进程的状态 进程是动态的概念，进程的状态也是在不断的变化。进程是动态的概念，进程的状态也是在不断的变化。就就绪绪状状态态：该该进进程程运运行行所所需需的的一一切切条条件件都都得得到到满满足足，但但因因处处理理机机资资源源个个数数少少于于进进程程个个数数，所所以以该该进进程程不不能能运运行行，而而必必须须等等待待分分配配处理机资源，一旦获得处理机就立即投入运行。处理机资源，一旦获得处理机就立即投入运行。运运行行状状态态：进进程程正正在在处处理理机机上上运运行行的的状状态态，该该进进程程已已获获得得必必要要的的资源，也获得了处理机，用户程序正在处理机上运行。资源，也获得了处理机，用户程序正在处理机上运行。阻阻塞塞状状态态：进进程程等等待待某某种种事事件件完完成成（例例如如，等等待待输输入入/输输出出操操作作的的完完成成）而而暂暂时时不不能能运运行行的的状状态态，处处于于该该状状态态的的进进程程不不能能参参加加竞竞争争处理机，此时，即使分配给它处理机，它也不能运行。处理机，此时，即使分配给它处理机，它也不能运行。*系统一般有一个就绪队列；多个阻塞队列。系统一般有一个就绪队列；多个阻塞队列。17进程的转换关系进程的转换关系18进程结构进程结构l进程实体进程实体 进程是一个实际存在的概念，是一个实际存在的实体。进程实体进程是一个实际存在的概念，是一个实际存在的实体。进程实体由由3部分组成：部分组成：程序：决定了要完成的功能程序：决定了要完成的功能数据：执行时的操作对象数据：执行时的操作对象进程控制块（进程控制块（PCB）：进程的状态和占用资源以及进程之间的关）：进程的状态和占用资源以及进程之间的关系是不断变化的，为了便于对进程进行管理，系统通过进程控制系是不断变化的，为了便于对进程进行管理，系统通过进程控制块管理这些信息块管理这些信息1920进程控制块进程控制块进程控制块是进程进程控制块是进程存在唯一的标志。当存在唯一的标志。当系统或父进程创建一个进系统或父进程创建一个进程时，实际上就是为其建立一个进程程时，实际上就是为其建立一个进程控制块，当进程执行过程中控制块，当进程执行过程中状态发生变化时修改状态发生变化时修改PCB，当进程被撤销时，系统收回，当进程被撤销时，系统收回PCB。进进程程控控制制块块既既能能标标识识进进程程的的存存在在，又又能能刻刻画画出出进进程程的的动动态态特特征征，它它是是一一个个进进程程仅仅有有的的被被系系统统真真正正感感知知的的部部分分。对对操操作作系系统统而而言言，所有进程控制块将构成并发执行控制和维护系统工作的依据。所有进程控制块将构成并发执行控制和维护系统工作的依据。21l在进程控制块中，主要包括下述在进程控制块中，主要包括下述4方面的信息。方面的信息。（1）进程描述信息）进程描述信息 进程标识符。每个进程都有惟一的进程标识符，用以识别不同的进程标识符。每个进程都有惟一的进程标识符，用以识别不同的进程。进程。用户名或用户标识号。每个进程都隶属于某个用户，有利于资源用户名或用户标识号。每个进程都隶属于某个用户，有利于资源共享与保护。共享与保护。家族关系。标识进程之间的家族关系。家族关系。标识进程之间的家族关系。22 （2）处理机状态信息）处理机状态信息 通用寄存器通用寄存器、指令计数器、程序状态字（、指令计数器、程序状态字（PSW）、）、用户栈指用户栈指 （3）进程调度信息）进程调度信息 进进程程状状态态。指指明明进进程程的的当当前前状状态态，以以作作为为进进程程调调度度和和进进程程对对换换时时的依据。的依据。23进程优先级。用于描述进程使用处理机的优先级别的一个整数，进程优先级。用于描述进程使用处理机的优先级别的一个整数，优先级别高的进程先获得处理机。优先级别高的进程先获得处理机。进程调度所需的其他信息。如进程已等待进程调度所需的其他信息。如进程已等待CPU的时间总和、进程的时间总和、进程已执行的时间总已执行的时间总 和等。和等。事件。指进程被阻塞的原因。事件。指进程被阻塞的原因。24（4）进程控制信息）进程控制信息程程 序和数据的地址。指出该进程的程序和数据所在的内存或外存序和数据的地址。指出该进程的程序和数据所在的内存或外存地址，以便再调度到该进程执行时，能从中找到其程序和数据。地址，以便再调度到该进程执行时，能从中找到其程序和数据。进程同步和通信机制。指实现进程同步和进程通信时所必须的机进程同步和通信机制。指实现进程同步和进程通信时所必须的机制，如消息队列指针、信号量等。这些数据应全部或部分地存放制，如消息队列指针、信号量等。这些数据应全部或部分地存放在在PCB中。中。25资源清单。它是一张列出了除资源清单。它是一张列出了除CPU之外的进程所需的全部资源和之外的进程所需的全部资源和已经分配给该进程的资源清单。已经分配给该进程的资源清单。链接指针。它给出了本进程（链接指针。它给出了本进程（PCB）所在队列的下一个进程的）所在队列的下一个进程的PCB首地址。首地址。在一个系统中，通常拥有数十个、数百个乃至数千个在一个系统中，通常拥有数十个、数百个乃至数千个PCB。为了。为了对对PCB进行有效地管理，系统应把所有的进行有效地管理，系统应把所有的PCB用适当的方式组织用适当的方式组织起来。起来。26进程控制进程控制 对系统中全部进程进行管理，包括创建、撤销及实现进程状态转换对系统中全部进程进行管理，包括创建、撤销及实现进程状态转换等。等。进程进程控制是由操作系统提供的一组系统调用实现的。这组系统调控制是由操作系统提供的一组系统调用实现的。这组系统调用直接控制进程，为了防止被其他进程中断，引进用直接控制进程，为了防止被其他进程中断，引进原语原语概念。概念。原语：用以完成特定功能的原语：用以完成特定功能的、执行时不可分割的或不可中断的程、执行时不可分割的或不可中断的程序或系统调用。序或系统调用。进程控制原语：创建原语、撤消原语、阻塞原语、唤醒原语进程控制原语：创建原语、撤消原语、阻塞原语、唤醒原语27进程调度进程调度l进程调度的任务进程调度的任务：为多个进程合理的分配处理机资源。为多个进程合理的分配处理机资源。l进程调度的职能：进程调度的职能：记录系统中所有进程的有关情况。（通过记录系统中所有进程的有关情况。（通过PCB来掌握进程情况）来掌握进程情况）确定分配处理机原则。确定分配处理机原则。分配处理机给进程。分配处理机给进程。从进程收回处理机。从进程收回处理机。28进程调度进程调度l进程调度方式进程调度方式 指把处理机分配给一个进程使用时，让该进程如何占用处理机，指把处理机分配给一个进程使用时，让该进程如何占用处理机，它能占用多长时间等。它能占用多长时间等。剥夺调度（抢占式调度）：u 一个进程占有处理机，这时有更紧迫的进程需要执行，则立即停止正在执行的进程，而执行更紧迫的进程u当前进程时间片用完，系统终止该进程执行，执行其他进程。非剥夺调度（不可抢占式调度）指一旦某个进程占用处理机后，则一直占用处理机运行下去。不管有没有更紧迫的进程，直到它完成或者遇到某种外部事件不能执行下去。29调度算法调度算法l进程调度算法进程调度算法 指在就绪态的进程中按照什么原则选择一个进程并把处理机指在就绪态的进程中按照什么原则选择一个进程并把处理机分给它使用。分给它使用。u几种常用调度算法几种常用调度算法先来先服务（先来先服务（FCFS）时间片轮转调度时间片轮转调度优先级法优先级法短作业优先短作业优先30先来先服务算法先来先服务算法先来先服务（先来先服务（FIFO）算法）算法按照进入就绪队列的先后顺序调度并分配处理机执行。按照进入就绪队列的先后顺序调度并分配处理机执行。FIFO算法利于长作业，算法利于长作业，不利于短作业，不利于短作业，而大多数的作业是而大多数的作业是I/O繁忙的短作业。繁忙的短作业。以以FIFO作为主调度算法是不常用的。作为主调度算法是不常用的。31作业名作业名到达次序到达次序运行时间运行时间A12B260C31D4232时间片法时间片法时间片轮转调度时间片轮转调度轮轮转转调调度度算算法法是是系系统统把把所所有有就就绪绪进进程程按按先先后后次次序序排排队队，处处理理机机总总是是优优先先分分配配给给就就绪绪队队列列中中的的第第一一个个就就绪绪进进程程，并并分分配配它它一一个个固固定定的的时时间间片片（如如100毫毫秒秒）。当当该该运运行行进进程程用用完完规规定定的的时时间间片片时时，被被迫迫释释放放处处理理机机给给下下一一个个处处于于就就绪绪队队列列中中的的第第一一个个进进程程，分分给给这这个个进进程程相相同同的的时时间间片片，每每个个运运行行完完时时间间片片的的进进程程，当当未未遇遇到到任任何何阻阻塞塞时时，就就回回到到就就绪绪队队列列的的尾尾部部，并并等等待待下下次次转转到到它它时时再再投投入入运运行。行。l时间片轮转调度关键要设置合适的时间片，太小则频繁调度，影时间片轮转调度关键要设置合适的时间片，太小则频繁调度，影响系统效率；太大则影响响应时间响系统效率；太大则影响响应时间33优先数法优先数法优先数法优先数法 按照某种原则对就绪队列中的进程赋予优先级，根据优先级确按照某种原则对就绪队列中的进程赋予优先级，根据优先级确定选择哪个进程运行。（静态优先级和动态优先级）定选择哪个进程运行。（静态优先级和动态优先级）l非抢占式优先级非抢占式优先级l抢占式优先级抢占式优先级34算法的衡量标准算法的衡量标准一般用周转时间和带权周转时间来衡量算法的优劣。一般用周转时间和带权周转时间来衡量算法的优劣。周转时间周转时间=完成时间完成时间-提交时间。提交时间。带权周转时间带权周转时间=周转时间周转时间/执行时间。执行时间。平均周转时间平均周转时间=周转时间周转时间/进程数。进程数。平均带权周转时间平均带权周转时间=带权周转时间带权周转时间/进程数。进程数。举例举例35A的周转时间的周转时间=2.0A的带权周转时间的带权周转时间=1.0B、C、D的周转时间分别为的周转时间分别为4.8 5.8 6.0平均周转时间平均周转时间=（2+4.8+5.8+6）/4进程名进程名提交时间提交时间执行时间执行时间开始时间开始时间完成时间完成时间A1.02.01.03.0B1.23.03.06.0C1.41.26.07.2D1.50.37.27.536进程的互斥与同步进程的互斥与同步l进程间关系进程间关系多个进程并发执行，共享系统资源，进程之间存在一种制约多个进程并发执行，共享系统资源，进程之间存在一种制约和依赖关系。和依赖关系。直接制约关系：直接制约关系：【同步（合作）同步（合作）】由于并发进程互相共享对方的私有由于并发进程互相共享对方的私有资源所引起的直接制约。资源所引起的直接制约。间接制约关系：间接制约关系：【互斥（资源竞争）互斥（资源竞争）】由于共享资源而引起的临界区由于共享资源而引起的临界区内不允许并发进程交叉执行的现象内不允许并发进程交叉执行的现象37进程的互斥进程的互斥 进程A进程B临界资源：一次仅允许一个进程使用的资源（硬件、软件）。临界区：进程中访问临界资源的那段代码。（critical section）。互斥定义：两个并发的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥。38进程同步进程同步系统中有多个进程共同完成一项任务，这些进程之间存在着直系统中有多个进程共同完成一项任务，这些进程之间存在着直接制约关系，每一个进程要依赖于其他进程所产生的结果才能继接制约关系，每一个进程要依赖于其他进程所产生的结果才能继续运行。共同完成一个任务的若干进程称为合作进程。续运行。共同完成一个任务的若干进程称为合作进程。缓冲区写进程A读进程B39同步与互斥的差异同步与互斥的差异互斥的进程在各自单独执行时都能得到正确结果，但在临界区交互斥的进程在各自单独执行时都能得到正确结果，但在临界区交叉执行时就会出现问题；同步的各个进程，如果单独执行将不会叉执行时就会出现问题；同步的各个进程，如果单独执行将不会完成任务，只有相互配合才能得到正确结果完成任务，只有相互配合才能得到正确结果互斥的进程要求他们不能同时进入临界区，而不需要规定进入临互斥的进程要求他们不能同时进入临界区，而不需要规定进入临界区的顺序。而同步的协调关系建立在他们的执行时序上界区的顺序。而同步的协调关系建立在他们的执行时序上互斥的进程并不要知道对方的存在，同步的进程不仅知道对方的互斥的进程并不要知道对方的存在，同步的进程不仅知道对方的存在，还要通过与其它进程的通信完成协作。存在，还要通过与其它进程的通信完成协作。40l为了实现多个进程互斥的进入临界区，在系统设立专门的同步机为了实现多个进程互斥的进入临界区，在系统设立专门的同步机制，所有同步制，所有同步机制必须遵循如下准则：机制必须遵循如下准则：1.空闲让进：没有进程在临界区时，不阻止其它进程进入临界区空闲让进：没有进程在临界区时，不阻止其它进程进入临界区2.忙则等待忙则等待3.有限等待：避免有限等待：避免死等死等（死锁）访问临界资源的进程保证在有限（死锁）访问临界资源的进程保证在有限的时间内进入临界区的时间内进入临界区4.让权等待：不能进入时或退出临界区时，立即释放处理机，让位给让权等待：不能进入时或退出临界区时，立即释放处理机，让位给等待进程。避免等待进程。避免忙等忙等。41l实现互斥实现互斥加锁法加锁法 设定一个锁变量设定一个锁变量w，w=1表示上锁，资源被占用；表示上锁，资源被占用；w=0表示开锁，资源空闲。表示开锁，资源空闲。lock w:L:if w=1 then goto L;else w=1;Unlock:w=0;42信号量机制信号量机制l信号量机制信号量机制解决多道系统中进程同步与互斥的问题。解决多道系统中进程同步与互斥的问题。信号量信号量信号量是操作系统中一种特殊变量，有如下特性：信号量是操作系统中一种特殊变量，有如下特性：一整形变量一整形变量每个信号量表示一种系统资源的状况，其值表示该资源当前可用每个信号量表示一种系统资源的状况，其值表示该资源当前可用的数量的数量每个信号量代表一个空的或非空等待队列每个信号量代表一个空的或非空等待队列对信号量只能实施对信号量只能实施P、V操作，只有操作，只有P、V操作才能改变其值操作才能改变其值43s.Value值的含义=0：表示系统当前可用的该类资源的数目0：其绝对值表示系统中因请求该类资源而被阻塞的进程数目（所以每个信号量都对应一个等待队列，即L）44P、V操作操作调度进程入等待队列转进程调度入口s.value=s.value-1s.value0入口s.value=s.value1s.value0唤醒等待队列中的一个进程返回或转进程调度返回返回s.value0是是否P原语操作功能流程图V原语操作功能流程图45信号量的应用信号量的应用 l解决互斥问题解决互斥问题用信号量解决几个进程互斥进入临界区的问题，几个进程共享一用信号量解决几个进程互斥进入临界区的问题，几个进程共享一个公用信号量个公用信号量mutex（互斥信号量）。（互斥信号量）。每个进程进入临界区必须先执行每个进程进入临界区必须先执行P（mutex），退出临界区后执行），退出临界区后执行V（mutex）。）。P（mutex）V（mutex）临界区46l 利用信号量和利用信号量和PV操作实现进程互斥的一般模型是：操作实现进程互斥的一般模型是：进程进程P1 进程进程P2 进程进程Pn P（S）；）；P（S）；）；P（S）；）；临界区；临界区；临界区；临界区；临界区；临界区；V（S）；）；V（S）；）；V（S）；）；47lPV操作实现进程互斥时应该注意操作实现进程互斥时应该注意：每个程序中用户实现互斥的每个程序中用户实现互斥的P、V操作必须成对出现，先做操作必须成对出现，先做P操作，操作，进临界区，后做进临界区，后做V操作，出临界区。若有多个分支，要认真检查其操作，出临界区。若有多个分支，要认真检查其成对性。成对性。P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。短，不能有死循环。48l解决进程同步解决进程同步设立与资源相关的私有信号量（资源信号量）。设缓冲区只有一个缓冲单元Empty=1 表示空单元个数。Full=0 表示装满信息的单元个数。缓冲区写进程A读进程B49 进程AP(empty)写V(full)进程BP(full)读V(empty)50l使用使用PV操作实现进程同步时应该注意的是：操作实现进程同步时应该注意的是：分析进程间的制约关系，确定信号量种类。在保持进程间有正分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。量。信号量的初值与相应资源的数量有关，也与信号量的初值与相应资源的数量有关，也与P、V操作在程序代操作在程序代码中出现的位置有关。码中出现的位置有关。同一信号量的同一信号量的P、V操作要成对出现，但它们分别在不同的进程操作要成对出现，但它们分别在不同的进程代码中。代码中。51练习练习l有一空盘，允许存放一只水果。爸爸可向盘中有一空盘，允许存放一只水果。爸爸可向盘中放苹果，妈妈可向盘中放桔子，儿子专等盘中放苹果，妈妈可向盘中放桔子，儿子专等盘中的桔子吃，女儿专等盘中的苹果吃。请用的桔子吃，女儿专等盘中的苹果吃。请用P、V原语实现爸爸、妈妈、儿子、女儿四个进程的原语实现爸爸、妈妈、儿子、女儿四个进程的同步。同步。52l盘子设置互斥信号量盘子设置互斥信号量 mutex=1l盘子中桔子个数盘子中桔子个数 s1=0l盘子中苹果个数盘子中苹果个数 s2=0l盘子中可容纳水果个数盘子中可容纳水果个数 empty=1;父亲：P(empty)送苹果V(s2)女儿：P(s2)吃苹果V(empty)P(mutex)V(mutex)P(mutex)V(mutex)53经典进程同步问题经典进程同步问题l生产者生产者-消费者问题消费者问题问题描述：问题描述：l环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品；环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品；l每个生产者可不断地每次往缓冲池中送一个生产产品；每个生产者可不断地每次往缓冲池中送一个生产产品；l每个消费者则可不断地每次从缓冲池中取出一个产品。每个消费者则可不断地每次从缓冲池中取出一个产品。54同步信号量：同步信号量：empty表示缓冲区空单元，初值为表示缓冲区空单元，初值为n。full表示缓冲区中非空单元数，初值为表示缓冲区中非空单元数，初值为0。互斥信号：互斥信号：mutex 缓冲区作为临界资源，需要互斥访问，初值缓冲区作为临界资源，需要互斥访问，初值=1；信号量设置信号量设置55procedureP(empty)P(mutex)放产品放产品V(mutex)V(full)consumerP(full)P(mutex)取产品取产品V(mutex)V(empty)注意事项：注意事项：u每个程序中实现互斥的每个程序中实现互斥的P(mutex),V(mutex)P(mutex),V(mutex)必须成对出现。必须成对出现。uEmptyEmpty和和fullfull的的P P，V V操作也必须成对出现，但它们处于不同的程序中。操作也必须成对出现，但它们处于不同的程序中。u每个程序中的多个每个程序中的多个P P操作不能颠倒顺序，否则可能引起死锁操作不能颠倒顺序，否则可能引起死锁。56司机司机-售票员问题售票员问题 到站停车 开 车 开 车 门 关 车 门 售 票 正常行车。售票员售票员司机司机s1s257l他们之间应互通消息；车门是否已经关好？车是否已经到站停车他们之间应互通消息；车门是否已经关好？车是否已经到站停车？l假定假定S1表示车门是否关好，当表示车门是否关好，当S1=1时表示车门已经关好，当时表示车门已经关好，当S1=0时表示车门还开着。由于初始状态为开着门，故时表示车门还开着。由于初始状态为开着门，故S1的初值应该为的初值应该为“0”。S2表示车是否驶到下一站点，当表示车是否驶到下一站点，当S2=1时表示车已经行驶时表示车已经行驶到站且停车，当到站且停车，当S2=0时表示车尚未到下一站。由于初始状态为车时表示车尚未到下一站。由于初始状态为车辆还在始发站尚未起步，因而辆还在始发站尚未起步，因而S2的初值应该为的初值应该为“0”，表示车辆尚，表示车辆尚未行驶到下一个站点。未行驶到下一个站点。58 售票员：上乘客；关车门；V(s1);售票；P(s2);开车门；下乘客；司机：司机：P(s1);启动车辆；启动车辆；正常行车；正常行车；到站停车；到站停车；V(s2);S1和S2的初值均为“0”。59l当发车时间到，售票员关车门后应调用当发车时间到，售票员关车门后应调用V（S1）把车门已关好的消）把车门已关好的消息发送出去；司机在启动车辆前应调用息发送出去；司机在启动车辆前应调用P（S1）来测试车门是否关）来测试车门是否关好，当车门关好的消息到达时就可启动车辆，然后正常行驶直到好，当车门关好的消息到达时就可启动车辆，然后正常行驶直到下一站后停车；当车辆到站后司机应调用下一站后停车；当车辆到站后司机应调用V（S2）把车已到站的消）把车已到站的消息发送出去；售票员每次开车门前都要调用息发送出去；售票员每次开车门前都要调用P（S2）来测试是否已）来测试是否已到站停车，当已到站停车的消息到达时就可开车门让乘客上、下到站停车，当已到站停车的消息到达时就可开车门让乘客上、下车；然后关好车门，再通过车；然后关好车门，再通过V（S1）把车门已关好的消息再次发送）把车门已关好的消息再次发送出去，司机得到消息后又可启动车辆行驶。用出去，司机得到消息后又可启动车辆行驶。用PV操作实现了司机操作实现了司机与售票员之间的协调工作，保证了车辆的行驶安全。与售票员之间的协调工作，保证了车辆的行驶安全。60死锁死锁死锁定义死锁定义是指多个进程因竞争资源而造成的一种僵局，若无外力作用，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都无法向前推进，死锁是计算机系统和进程所处的一种这些进程都无法向前推进，死锁是计算机系统和进程所处的一种状态。状态。616263死锁产生的原因死锁产生的原因竞争竞争资源资源 当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；推进时序不当推进时序不当 进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。64产生死锁有四个必要条件产生死锁有四个必要条件互斥条件：资源在使用上具有独占性、互斥性互斥条件：资源在使用上具有独占性、互斥性不可剥夺条件：不可剥夺条件：一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺部分分配条件（部分分配条件（请求和保持条件）：）：一个进程在请求新的资源的同时，保持对某些资源的占有环路等待条件：环路等待条件：存在一个进程的环路链，链中每一个进程占用有着某个或某些资源，又在等待链中的另一个进程占有的资源。65对付死锁的对策对付死锁的对策死锁的预防死锁的预防死锁的避免死锁的避免死锁的检测死锁的检测死锁的恢复死锁的恢复66预防死锁预防死锁（静态预防）（静态预防）破坏破坏“部分分配条件部分分配条件”破坏环路条件破坏环路条件破坏不可剥夺条件破坏不可剥夺条件67破坏部分分配条件破坏部分分配条件方方法法一一：进进程程在在运运行行中中需需要要的的全全部部资资源源，要要么么全全部部分分配配，要要么么一一个个都都不不分分配配；进进程程运运行行中中，不不能能再再申申请请资资源源；进进程程运运行行结结束束后后，其占有的所有资源一起释放其占有的所有资源一起释放.缺点：推迟执行时间缺点：推迟执行时间方方法法二二：进进程程只只能能同同时时占占有有一一个个资资源源。申申请请资资源源之之前前必必须须释释放放以以前申请得到的资源。前申请得到的资源。68破坏环路条件破坏环路条件基本思想：限制进程申请资源的顺序。基本思想：限制进程申请资源的顺序。对资源请求采取了这种限制之后，所形成的进程对资源请求采取了这种限制之后，所形成的进程资源图不可能再资源图不可能再产生环路产生环路所有的进程都只能严格地按照编号递增（或递减）的次序去请求所有的进程都只能严格地按照编号递增（或递减）的次序去请求资源，亦即，只有低编号的资源要求满足后，才能对高编号资源资源，亦即，只有低编号的资源要求满足后，才能对高编号资源提出要求；释放资源时，应按编号递减的次序进行。提出要求；释放资源时，应按编号递减的次序进行。对系统提供的每一类资源，由系统设计者将它们按类型进行线性对系统提供的每一类资源，由系统设计者将它们按类型进行线性排队，并赋予不同的序号。排队，并赋予不同的序号。例如，设卡片输入机为例如，设卡片输入机为1，打印机为，打印机为2，磁带机为，磁带机为3，磁盘机为，磁盘机为4，。69 缺点：缺点：1 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加了新设备类型的增加 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；浪费；70破坏不可剥夺条件破坏不可剥夺条件 当当一个已经保持某些资源的进程，再提出新的资源的申请而不能一个已经保持某些资源的进程，再提出新的资源的申请而不能立即得到满足时，必须释放已经保持了的所有资源立即得到满足时，必须释放已经保持了的所有资源71避免死锁（动态预防）避免死锁（动态预防）基本思想：基本思想：在资源的动态分配过程中，用某种方法防止系统进入在资源的动态分配过程中，用某种方法防止系统进入不安全状态。不安全状态。安安全全状状态态：在在某某个个时时刻刻，系系统统能能按按某某种种顺顺序序，如如P1，P2，Pn来来为为每每个个进进程程分分配配需需要要的的资资源源，直直至至最最大大需需求求，使使每每个个进进程程都都能能顺顺利利地地完完成成。则则称称此此时时的的系系统统状状态态为为安安全全状状态态。P1，P2，Pn为安全序列。为安全序列。不不安安全全状状态态：在在某某个个时时刻刻，系系统统不不存存在在这这样样一一个个安安全全序序列列，则则称称此时的系统状态为不安全状态。此时的系统状态为不安全状态。系系统统具体实现：银行家算法具体实现：银行家算法72安全状态的例子安全状态的例子例：假定系统有三个进程例：假定系统有三个进程P1、P2、P3，共有，共有12台磁带机。进程台磁带机。进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和9台。设在台。设在T0时刻，进程时刻，进程P1、P2和和P3已经获得已经获得5台、台、2台和台和2台，台，还有还有3台空闲没有分配台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列73l虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统因此，避免死锁的实质是如何使系统不进入不安全状态。不进入不安全状态。74银行家算法l银行家算法是最有代表性的避免死锁算法，是银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。l为实现银行家算法，系统中必须设置若干数据结构。为实现银行家算法，系统中必须设置若干数据结构。75l一、银行家算法中的数据结构一、银行家算法中的数据结构l1可利用资源向量可利用资源向量Available是是一一个个含含有有m个个元元素素，其其中中的的每每一一个个元元素素代代表表一一类类可可利利用用的的资资源源数数目目，其其初初值值是是系系统统中中所所配配置置的的该该类类全全部部可可用用资资源源数数目目。如如果果Availablej=k，表示系统中现有表示系统中现有Rj类资源类资源k个。个。l2最大需求矩阵最大需求矩阵Maxl是是一一个个含含有有nm的的矩矩阵阵，它它定定义义了了系系统统中中n个个进进程程中中的的