第2章进程管理ppt课件.ppt

兰州理工大学计算机与通信学院,第2章 进程管理,2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题 2.8 Windows进程管理,本章主要内容,2.1 进程的引入,2.1.1 程序的顺序执行与并发执行2.1.2 进程的概念2.1.3 进程的状态2.1.4 进程的管理,兰州理工大学计算机与通信学院,1程序的顺序执行 程序的顺序执行是指必须严格地按照某种次序逐个地执行，即只有当一个操作结束后，才能开始后继操作。,兰州理工大学计算机与通信学院,程序顺序执行的特征,执行的顺序性 环境的封闭性 结果的确定性 过程的可再现性,兰州理工大学计算机与通信学院,2程序的并发执行 操作系统中引入并发程序设计技术后，程序的执行不再是顺序的，一个程序未执行完而另一个程序已投入运行，程序外部的顺序特性消失，程序与程序的执行不再一一对应。,兰州理工大学计算机与通信学院,程序段的并发执行,兰州理工大学计算机与通信学院,程序并发执行的特征,执行的间断性 环境的不封闭性 结果的不确定性 过程的不可再现性,兰州理工大学计算机与通信学院,2.1 进程的引入,2.1.1 程序的顺序执行与并发执行2.1.2 进程的概念2.1.3 进程的状态2.1.4 进程的管理,兰州理工大学计算机与通信学院,1进程的定义 进程的多种定义中能反映进程实质的定义有：是程序的一次执行。计算机中正在运行的程序的一个实例。可以分配给处理机并由处理机执行的一个实体。是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。,兰州理工大学计算机与通信学院,2进程的类型 从操作系统角度，可将进程分为系统进程和用户进程两大类。系统进程 系统进程属于操作系统的一部分，它们运行操作系统程序，完成操作系统的某些功能，也被称作守护（daemon）进程,兰州理工大学计算机与通信学院,用户进程 用户进程运行用户程序，直接为用户服务。所谓“用户程序”，不一定是用户自己编写的程序，在操作系统之上运行的所有应用程序都被称作用户进程。,兰州理工大学计算机与通信学院,3进程的特征动态性共享性独立性并发性异步性结构性,兰州理工大学计算机与通信学院,4进程和程序的关系 进程是动态的，程序是静态的 进程是暂时的，程序是永久的 进程与程序的组成不同 一个程序可以对应多个进程，但一个进程只能对应一个程序段,兰州理工大学计算机与通信学院,2.1 进程的引入,2.1.1 程序的顺序执行与并发执行2.1.2 进程的概念2.1.3 进程的状态2.1.4 进程的管理,兰州理工大学计算机与通信学院,一个进程从产生到消亡的整个生命周期，有时占有处理机而执行，有时虽然可以运行但分不到处理机，有时虽有空闲处理机但因等待某个事件的发生而无法执行。为了便于管理进程，一般来说，按进程在执行过程中的不同情况可以构造最简单的进程状态模型。,兰州理工大学计算机与通信学院,1三状态进程模型,兰州理工大学计算机与通信学院,2五状态进程模型,兰州理工大学计算机与通信学院,3挂起状态进程模型（）,单挂起状态进程模型,兰州理工大学计算机与通信学院,3挂起状态进程模型（）,双挂起状态进程模型,兰州理工大学计算机与通信学院,2.1 进程的引入,2.1.1 程序的顺序执行与并发执行2.1.2 进程的概念2.1.3 进程的状态2.1.4 进程的管理,兰州理工大学计算机与通信学院,在操作系统中同时存在多个进程，它们又对应着不同的或相同的程序段以及进程运行所需的各种独立的、共享的系统资源。因此进程管理的功能有以下几个方面：进程的控制 进程的同步 进程的通信 进程的调度 进程的安全,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,第2章 进程管理,2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题,2.2 进程的描述与控制,2.2.1 进程的描述 2.2.2 进程的控制,兰州理工大学计算机与通信学院,进程的静态描述由三部分组成：进程控制块、有关程序段和与该程序段相关的数据结构集合。进程的程序部分描述进程所要完成的功能。是进程运行所对应的执行代码，一个进程可以对应一个完整的程序，也可以只对应一个程序中的一部分。数据结构集合是程序在执行时必不可少的工作区和操作对象。进程控制块是记录进程存在、保持进程所需数据集合、完成进程控制的重要结构。,兰州理工大学计算机与通信学院,1进程控制块PCB PCB有时也称为进程描述块（Process Descriptor Block），是系统为描述进程而设计的一种数据结构。个进程只有一个PCB，PCB是进程存在与否的唯一标记，一个进程的PCB结构都是全部或部分常驻内存的。PCB基本内容：标识信息、现场信息、控制信息,兰州理工大学计算机与通信学院,进程控制块的主要作用有：标识进程的存在。系统创建进程时，就为之创建一个PCB；进程结束时，系统又回收其PCB，进程便随之消亡。为系统控制和管理进程提供所需的一切信息。,兰州理工大学计算机与通信学院,2PCB的组织方式 在一个系统中，通常可拥有数十个、数百个甚至上千个PCB。为了有效地进行进程管理，系统必须对进程进行合理的组织。顺序表 定义一个PCB结构数组。这种方式不区分进程状态，将所有PCB连续地存放在内存区中。,兰州理工大学计算机与通信学院,索引表 系统根据进程的状态，分别为具有相同状态的PCB建立一张索引表。通常，PCB表采用静态存储分配方案，定义为PCB结构数组；各种索引表采用动态存储分配方案，索引表中存入相应PCB数组元素的下标值。,兰州理工大学计算机与通信学院,链表 系统根据PCB的状态，把相同状态的PCB链接成一个PCB链表队列，这样，可形成就绪进程队列、阻塞进程队列等。对就绪进程队列，可根据其优先级的不同，将优先级高的PCB排在前面。此外，系统也可以根据阻塞原因的不同，形成等待各种外设I/O操作完成的队列、等待各种事件发生的队列。,兰州理工大学计算机与通信学院,3进程上下文 进程上下文是进程执行活动全过程的静态描述。它包括系统中与执行该进程有关的各种寄存器的值，进程段在经过编译之后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和PCB结构。,兰州理工大学计算机与通信学院,4进程空间 每一个进程都有自己的地址空间，该空间称为进程空间或虚空间，进程空间又划分为用户空间和系统空间两部分。用户程序在用户空间执行，操作系统内核程序则在进程的系统空间内执行。,兰州理工大学计算机与通信学院,2.2 进程的描述与控制,2.2.1 进程的描述 2.2.2 进程的控制,兰州理工大学计算机与通信学院,进程控制，是指系统使用一些具有特定功能的程序段来创建进程、撤消进程以及完成进程各状态间的转换。这些程序段是机器指令的延伸，由若干条机器指令构成，用以完成特定功能，且在管态下执行，执行过程中是不可分割的，不允许被中断，并且它是顺序执行的（不允许并发），我们把这样的程序段叫作原语。,兰州理工大学计算机与通信学院,用于进程控制的原语有：创建原语撤销原语阻塞原语唤醒原语挂起原语和激活原语,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,第2章 进程管理,2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题,2.3 线程,2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程2.3.5 线程的描述与控制,兰州理工大学计算机与通信学院,线程能有效地提高系统的性能。目前，不仅在操作系统中，而且在数据库管理系统和其他应用软件中，都普遍引入了线程的概念。在引入线程的操作系统中，线程是系统调度的基本单位，而进程是独立分配资源的基本单位。因此，线程的引入是为了以小的开销来提高进程内的并发程度。,兰州理工大学计算机与通信学院,1线程的定义 线程的定义情况与进程类似，存在多种不同的提法：线程是进程内的一个执行单元。线程是进程内的一个可调度实体。线程是程序（或进程）中相对独立的一个控制流序列。,兰州理工大学计算机与通信学院,2多线程 多线程是指操作系统支持的一个进程中执行多个线程的能力，这些线程共享该进程资源，驻留在相同的地址空间中，共享数据和文件。如果一个线程修改了存储空间中的一项数据，其它线程访问该数据项时就获得了改变之后的结果。如果一个进程以只读方式打开了一个文件，同一进程中的其它线程也能从该文件中读数据。,兰州理工大学计算机与通信学院,3进程与线程的比较 线程具有许多传统进程所具有的特征，故又称为轻型进程（Light-Weight Process）或进程元；而传统的进程称为重型进程（Heavy-Weight Process），它相当于只有一个线程的任务。,兰州理工大学计算机与通信学院,可以从以下几个角度来比较进程和线程：调度切换。并发性。地址空间资源。通信关系。系统资源的拥有。系统开销,兰州理工大学计算机与通信学院,2.3 线程,2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程2.3.5 线程的描述与控制,兰州理工大学计算机与通信学院,与进程类似，线程也有生命周期，也存在各种状态。它的主要状态有运行、就绪和阻塞。正在运行的线程拥有CPU并且是活跃的，被阻塞的线程等待某个事件的发生或等待其它线程来释放它，就绪线程可被调度执行。由于线程不是资源的拥有单位，挂起状态对线程没有意义。所以，线程的状态转换类似于进程的三态模型。与线程级状态变化有关的基本操作原语主要有四个，分别是创建原语、阻塞原语、解除阻塞原语和终止原语。,兰州理工大学计算机与通信学院,2.3 线程,2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程2.3.5 线程的描述与控制,兰州理工大学计算机与通信学院,教材图2-8显示了执行两个对不同主机的远程过程调用（RPC）获得的组合结果。在单线程环境中，这两个结果是顺序获得的，故程序要依次等待每一个服务器的响应。如用各自的线程执行RPC以获得调用结果的方法重写程序，性能就获得实质性的提高。当然，如果这个程序是在单处理机的环境下执行，调用请求是串行地发出的，结果的处理也是串行地进行的。,兰州理工大学计算机与通信学院,2.3 线程,2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程2.3.5 线程的描述与控制,兰州理工大学计算机与通信学院,线程在有的系统中，实现的是用户级线程（ULT，User-Level-Threads），这种线程不依赖于内核。而另一些系统（如Mach和OS2操作系统）实现的是内核级线程（KLT，Kernel-Level-Threads），这种线程依赖于内核。也有一些系统如Solaris操作系统，则提供了混合式线程，同时支持这两种类型的线程。,兰州理工大学计算机与通信学院,1内核级线程 在纯KLT机构中，所有的线程管理工作是由内核完成的。内核专门提供了一个KLT应用程序设计接口（API），供开发者使用。KLT方法的主要优点是内核能同时调度一个进程中的多个线程在多处理机上运行。同时，如果进程中的一个线程被阻塞，内核能调度同一进程中的其它线程，也可以运行其它进程中的线程。KLT方法的另一优点是内核本身也用多线程技术实现，从而能提高系统的执行效率和速度。KLT方法的主要缺点是应用程序的线程在目态运行，而线程调度和管理又在内核实现，所以在同一进程内将控制从一个线程转换到另一个线程时需要用户态内核态用户态的切换。,兰州理工大学计算机与通信学院,2用户级线程 在纯ULT机构中，管理线程的所有工作是由应用程序来完成的，系统内核并不能感觉到这类线程的存在，所以从内核角度考虑，就是按正常的方式管理，即单线程进程，这种方法的一个明显优点是，用户级线程库可以在不支持线程的操作系统上实现。与KLT相比，ULT有以下特点：线程间的切换不需要核心态特权。调度程序是面向特定应用系统的。ULT能在任何操作系统上运行。进程中的一个线程被阻塞时，进程内的所有线程会被阻塞。,兰州理工大学计算机与通信学院,3混合式线程 在采用混合式线程的系统中，内核支持KLT多线程的建立、调度和管理。同时也提供线程库，允许应用程序建立、调度和管理ULT。混合式线程中，一个应用程序中的多个线程能同时在多处理机上并行执行，且阻塞一个线程时并不需要阻塞整个进程，若设计得当，混合式多线程机制能够结合两者的优点，舍弃它们的缺点。,兰州理工大学计算机与通信学院,2.3 线程,2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程2.3.5 线程的描述与控制,兰州理工大学计算机与通信学院,1线程的描述 支持线程的操作系统中也要为线程设计一种数据结构线程控制块（Thread Control Block，TCB）来标志线程的存在，即每当创建一个新线程时，便要为该线程分配一个TCB。不同的操作系统，线程的结构不尽相同，一般包含系统对于线程进行管理所需要的全部信息。不过TCB的内容一般较少。TCB中的主要信息有：线程标识、程序计数器及状态寄存器等寄存器组、若干堆栈、私用存储器等。TCB可能属于操作系统空间，也可能属于用户进程空间，是由线程的实现方式决定的。,兰州理工大学计算机与通信学院,2线程的控制 类似于进程控制，线程也具有线程控制模块、同步协调机构以及时钟控制等。线程控制包括了对线程执行环境的控制和状态转换的控制，也具有线程创建、调度、阻塞、唤醒及撤销。进程内各线程的并发执行由同步协调机制完成，可直接在进程局部空间内实现线程通信。线程的存在与消亡也通过线程控制块TCB体现出来。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,第2章 进程管理,2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题,2.4 进程同步,2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步2.4.4 多处理机同步,兰州理工大学计算机与通信学院,1进程间的相互关系 在多道程序环境中，同一时刻可能有多个进程在计算机中运行。它们之间存在着两种关系：竞争 系统中彼此无关的进程在运行过程中并不知道对方的存在，而且也不受其它进程执行的影响，但是一个进程的执行可能会影响到同其竞争资源的其他进程。进程互斥（mutual exclusion）是解决进程间资源竞争关系（间接制约关系）的手段，指若干个共享某一资源的进程并发执行时，任何时刻只允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。,兰州理工大学计算机与通信学院,例2-1、有两个进程P1、P2，它们都要使用打印机，如果让它们随意使用，那么就有可能出现这种情况，P1打印几行接着P2再打印几行，打印结果混在一起，很难区分，既使能够区分，也要将各自输出结果从打印纸上剪下来，再用浆糊粘接起来。解决这一问题的办法是，不允许一台打印机让两个进程同时使用，应在一个进程用完后再让另一进程使用。,兰州理工大学计算机与通信学院,合作。某些进程为了完成同一任务分工合作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互合作的进程在某些合作点上协调各自的工作。当合作进程中的一个到达合作点后，在尚未得到其它合作进程发来的消息或信号之前应阻塞自己，直到其合作进程发来协调信号或消息后才能被唤醒。进程同步（synchronization）是解决进程间合作关系（直接制约关系）的手段，指两个或两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一个合作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。,兰州理工大学计算机与通信学院,例2-2、在一辆公共汽车上，司机和售票员各行其职，独立工作。司机负责开车和到站停车，售票员负责售票和开、关车门。但两者需要密切配合、协调一致。即当司机驾驶的车辆到站并把车辆停稳后，售票员才能打开车门，让乘客上、下车，然后关好车门，这时司机继续开车行驶。,兰州理工大学计算机与通信学院,2临界资源和临界区 一次只能允许一个进程访问的共享资源称为临界资源。每个进程访问临界资源的那段程序称为临界区（Critical Section），简称CS区。只有让使用临界资源的进程互斥地进入临界区，才能保证某一进程单独地使用临界资源。并发进程进入相关临界区执行应遵循如下四个准则：一次至多只允许一个进程进入临界区。不能让一个进程无限期地在临界区内执行。不能强迫一个进程无限地等待进入它的临界区。不能假定处理机的速度和限制处理机的数量，也即公平竞争。,兰州理工大学计算机与通信学院,例2-3、某游艺场设置了一个自动计数系统，用一个计数器count指示在场的人数。当有一个人进入时，由进程Pin实现计数器加1；当有一个人退出时，由进程pout实现计数器减1。两个进程的程序段如下：,void pin(int count)int R1；R1count；R1+；count R1；,void pout(int count)int R2；R2count；R2-；count R2；,兰州理工大学计算机与通信学院,2.4 进程同步,2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步2.4.4 多处理机同步,兰州理工大学计算机与通信学院,1加锁机制 设想有一个共享变量（锁变量）W，锁有两种状态：w0表示锁已打开，此时临界区内没有进程；W1表示锁被关闭，此时已有某个进程进入临界区。用原语来实现，其中加锁原语用LOCK（W）表示，可描述为：测试W，若W1，表示资源正在使用，继续反复测试；若W0，置Wl（加锁）。开锁原语用UNLOCK（W）表示，可描述为：W=0；,兰州理工大学计算机与通信学院,2信号量机制 信号量是一种控制进程互斥和同步的变量。从物理意义上理解，信号量的值对应着相应资源的使用情况，当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，表示已无可用资源，其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的进程数，也就是说，每一个信号量有一个等待队列。对信号量的操作，只允许初始化和执行两个标准的原语P、V原语，或者称为P、V操作，没有任何其它方法可以检查和操作信号量。,兰州理工大学计算机与通信学院,信号量按其用途可分为两种：公用信号量，用来联系一组无关进程，每个进程均可在此信号量上执行P和V操作。初值常常为1，常用于实现并发进程的互斥。私有信号量，用来联系一组合作进程，仅允许此信号量的拥有进程执行P操作，而其合作进程可在其上执行V操作。初值常常为0或正整数，多用于并发进程同步。,兰州理工大学计算机与通信学院,信号量按其取值可分为两种：二元信号量，仅允许取值为0和1，主要用于解决进程互斥问题。一般信号量，允许取值为整数，主要用于解决进程同步问题。,兰州理工大学计算机与通信学院,整型信号量 设S为一个整型变量，除初始化外，仅能通过P、V原语来访问它，这时P操作原语和V操作原语定义如下：P（S）：当信号量S大于0时（有可用资源），S减1，否则调用P（S）的进程等待直到信号量S大于0。V（S）：把信号量S加1。P、V操作原语描述如下：P（S）：while(S=0)do null operation;S-；V（S）：S+；,兰州理工大学计算机与通信学院,记录型信号量,typedef struct semaphore int value;/信号量值,通常是一个具有非负初值的整型变量struct pcb*list;/信号量队列指针,初始状态为空;void P(semaphore,兰州理工大学计算机与通信学院,从信号量和P、V操作的定义可以获得如下推论：推论1：若信号量S为正值，则该值等于在阻塞进程之前对信号量S可执行的P操作数，也就是说，该值等于信号量S所代表的实际还可以使用的物理资源数。推论2：若信号量S为负值，则其绝对值等于排列在等待该信号量S的队列之中的进程个数，恰好等于对信号量S执行P操作而被阻塞并进入信号量S等待队列的进程数。推论3：通常，P操作意味着申请资源；V操作相当于释放资源。,兰州理工大学计算机与通信学院,二元信号量 设S为一个记录型数据结构，其中一个分量为整型量value，它仅能取值0和1，另一个分量为信号量队列queue。利用记录型信号量实现进程之间的互斥 引入一个公用信号量mutex，它也称为互斥信号量，其初值为1，表示无进程进入临界区。任何欲进入临界区执行的进程，必须先对互斥信号量mutex执行P操作，即使mutex值减1，若减1后mutex值为0，表示临界资源空闲，执行P操作进程可以进入临界区执行；若mutex减1后的值为负，说明已有进程占有临界资源，执行P操作进程必须等待，直到临界资源空闲为止。正在临界区执行的进程，完成临界区操作后，通过执行V操作，使mutex值加1，表示释放临界资源。,兰州理工大学计算机与通信学院,其算法描述如下：semaphore mutex1；P(mutex)；临界区；V(mutex)；其余操作；,兰州理工大学计算机与通信学院,例如，对于并发进程pin和pout中count的操作用P、V原语可描述如下：semaphore mutex1；pin：P(mutex);R1count；R1+；count R1；V(mutex);,pout：P(mutex);R2count；R2-；count R2；V(mutex);,兰州理工大学计算机与通信学院,用P、V操作实现进程互斥时应注意：在每个程序中用于实现互斥的P（mutex）和V（mutex）必须成对出现，即先执行P操作进入临界区；后执行V操作退出临界区。互斥信号量mutex的初值一般为l。,例2-4、设一民航航班售票系统有n个售票处。每个售票处通过终端访问系统中的公用数据区，假定用公共数据区中的一些单元Ak(k1，2，)分别存放某月某日某次航班的现有票数。设Pl，P2，Pn表示各售票处的处理进程，Rl，R2，Rn表示各进程执行时所用的工作单元。,兰州理工大学计算机与通信学院,利用记录型信号量实现进程之间的同步 为了解决进程的同步问题，同样也可以引入信号量机制。若用信号量实现两进程同步，通常设立与进程有关的私用信号量。,例2-5 两个进程A、B对一个单缓冲区buf进行操作，其过程是：只要单缓冲区空，A进程就向其中送数，若单缓冲区满则等待。只要单缓冲区不空，B进程就从中取数，若单缓冲区空则等待。A进程和B进程对单缓冲区的使用关系如图所示。,兰州理工大学计算机与通信学院,单缓冲区的操作,兰州理工大学计算机与通信学院,semaphore sa0，sb0；pa()do while(sa=0)(送数到缓冲区)V(sb)；P(sa)；(其他操作)while(1);,pb()do while(sb)P(sb)；(从缓冲区取数)V(sa)；(其他操作)while(1);,兰州理工大学计算机与通信学院,例如，用信号量实现司机和售票员的同步。设S1和S2分别为司机和售票员的私用信号量，初值均为0，则司机和售票员的同步过程描述如下：semaphore S1=0;S2=0；,司机进程：do正常行车；到站停车；V(S2)；P(S1)；开车；while(1);,售票员进程：do售票；P(S2)开车门；关车门；V(S1)；while(1);,兰州理工大学计算机与通信学院,例2-6 桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果，请用P、V操作实现爸爸、儿子、女儿三个“并发进程”的同步。,分析：这是一个明显的同步问题，也称为生产者和消费者问题。爸爸可以向盘子中放入两类水果：橘子、苹果；然后儿子、女儿每人可以消费其中的一种水果。爸爸是生产者，子女是消费者，也就是只有爸爸放入水果，子女才能消费水果；只有子女消费完水果，爸爸才能再次放入水果。,兰州理工大学计算机与通信学院,设empty、orange和apple分别为爸爸、儿子和女儿的私用信号量。empty表示盘子是否为空，其含义是爸爸是否可以开始放入水果，初值为1表示可以放；orange表示盘中是否有橘子，其含义是儿子是否可以开始取橘子，其初值为0表示不能取橘子；apple表示盘中是否有苹果，其含义是女儿是否可以开始取苹果，其初值为0表示不能取苹果。则爸爸、儿子和女儿的同步过程描述如下：semaphore empty=1,orange=apple=0;,兰州理工大学计算机与通信学院,父亲进程：doP(empty);将水果放入盘中；if(放入的是橘子)V(orange);else V(apple);while(1);,儿子进程：doP(orange);从盘中取出橘子；V(empty);吃橘子；while(1);,女儿进程：doP(apple);从盘中取出苹果；V(empty);吃苹果；while(1);,兰州理工大学计算机与通信学院,用P、V操作实现同步时应注意：分析进程间的制约关系，确定信号量种类。在保持进程间有正确同步关系的情况下，哪个进程应先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。同一信号量的P、V操作要“成对”出现，但它们分别在不同的进程代码中。,兰州理工大学计算机与通信学院,信号量集 信号量集是指同时需要多个资源时的信号量操作。,AND型信号量集 AND型信号量集是指同时需要多种资源且每种资源都需占用一个时的信号量操作。用一个原语申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配。我们称AND型信号量集P原语为Swait（Simultaneous Wait），V原语为Ssignal（Simultaneous Signal）。在Swait中，各个信号量的次序并不重要，虽然这会对进程归入哪个阻塞队列产生影响，但由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会出现死锁。,兰州理工大学计算机与通信学院,Swait和Ssignal函数可以描述如下：,Swait（s1,s2,，sn）while(1)if(s1=1 else 调用进程进入第一个小于1信号量的等待队列；阻塞调用进程；,Ssignal（s1,s2,，sn）for(i=1;i=n;i+)+si;从等待队列中取出进程p；if(进程p通过Swait中的测试)进程p进入就绪队列；else 进程p进入某等待队列；,兰州理工大学计算机与通信学院,一般信号量集 一般信号量集是指同时需要多种资源，每种资源被占用的数目不同，而且可分配的资源还存在一个临界值时的信号量处理。由于一次需要n个某类临界资源，如果通过n次P原语操作申请这n个临界资源，那么操作效率很低，并可能出现死锁，一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。进程多信号量si的测试值为ti（表示信号量的判断条件，要求siti，即当资源数量低于ti时，便不予分配），申请第i类资源数为di，对应的P、V原语格式为：Swait（s1,t1,d1,，sn,tn,dn）；Ssignal（s1,t1,d1,，sn,tn,dn）；,兰州理工大学计算机与通信学院,3管程机制 基本思想是把信号量及其操作原语封装在一个对象内部。也就是说，将共享资源及能够对共享资源进行的所有操作集中在一个模块中。可把“管程”定义为关于共享资源的数据结构和能为并发进程在该数据结构上执行的一组操作，这组操作能使进程同步和改变管程中的数据。,管程的结构,兰州理工大学计算机与通信学院,管程的特性：局部于管程内的数据结构只能被管程内的过程所访问；反之，局部于管程内的过程只能访问该管程内的数据结构。进程要想进入管程，必须调用管程内的某个过程；一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程可用。,管程实现进程同步时，需引入若干条件变量ci及相关的两个操作原语：Wait和Signal。Wait(ci)：若请求服务没有满足，则将进程阻塞在ci的等待队列上Signal(ci)：恢复执行前应先唤醒在条件ci上执行Wait而阻塞的那个进程。如果存在几个这样的进程，则从中挑选一个；如果没有这种进程，则什么也不做。,兰州理工大学计算机与通信学院,2.4 进程同步,2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步2.4.4 多处理机同步,兰州理工大学计算机与通信学院,一个进程中的所有线程共享相同的地址空间和其它资源，在同一个进程内，一个线程对资源的改变会影响其它线程的环境，因此必须同步各个线程的活动，使它们之间不会互相干扰或破坏数据结构。通常线程的同步技术与进程的同步技术相同，可以采用解决进程同步的技术来实现线程的同步。,兰州理工大学计算机与通信学院,2.4 进程同步,2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步2.4.4 多处理机同步,兰州理工大学计算机与通信学院,在多处理机系统中，进程和CPU之间的关系由多对一变为多对多，因此并发控制变得更为复杂。在多处理机的计算机中，都有下面一条指令：TSL RX,LOCK称为测试并加锁指令，它的功能是将一个内存中的字“锁LOCK”读到寄存器RX中，然后在该内存地址上存放一个非零值。为了在多CPU环境中实现互斥，需要硬件进一步的支持，即TSL指令必须首先锁住总线（即“锁总线”），阻止其它的CPU访问，然后进行共享内存的读写操作，再解除总线。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,第2章 进程管理,2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题,2.5 经典进程同步问题,2.5.1 生产者消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者写者问题,兰州理工大学计算机与通信学院,生产者消费者问题是用于解决一群生产者和消费者之间的进程互斥和进程同步问题。生产者进程可以是计算进程、发送进程等；而消费者进程可以是打印进程、接收进程等等。,生产者消费者问题可以描述为由些不确定数目的生产者和消费者进程及个有限的共享缓冲区所构成的系统。生产者进程不断地向共享缓冲区写入数据（即生产数据），而消费者进程从共享缓冲区中读出数据（即消费数据）。,兰州理工大学计算机与通信学院,1用记录型信号量解决生产者和消费者问题可设置三个信号量：full和empty为两个同步信号量，其中full表示有数据的缓冲块数目，初值为0；empty表示空的缓冲块数目，初值为N；mutex用于访问缓冲区时的互斥，初值为1。实际上，full和empty之间存在如下关系：full+empty=N,要求：生产者不应覆盖个满的缓冲区；消费者不应使用一个空的缓冲区；生产者消费者必须按一种互斥的方式访问缓冲区。,兰州理工大学计算机与通信学院,consumer j(j=1,2,)do P（full）;P（mutex）;从共享缓冲区读出数据;V（mutex）;V（empty）;消费数据;while(1);,producer i(i=1,2,)do 生产数据;P（empty）;P（mutex）;向共享缓冲区写入数据;V（mutex）;V（full）;while(1);,兰州理工大学计算机与通信学院,2用AND型信号量集解决生产者和消费者问题 用AND型信号量集解决生产者和消费者问题，即用Swait和Ssignal函数来代替P、V操作。,producer i(i=1,2,)do 生产数据;Swait（empty,mutex）;向共享缓冲区写入数据;Ssignal（mutex,full）;while(1);,consumer j(j=1,2,)do Swait（full,mutex）;从共享缓冲区读出数据;Ssignal（mutex,empty）;消费数据;while(1);,兰州理工大学计算机与通信学院,2.5 经典进程同步问题,2.5.1 生产者消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者写者问题,兰州理工大学计算机与通信学院,哲学家用餐问题也是一个典型的同步问题，是由Dijkstra提出并解决。该问题是描述五位哲学家围坐在一个圆桌旁，每位就餐者需要两把叉子，但桌上只提供了5把，在每个相邻座位间都放有一把。为了吃到东西，每个哲学家必须拿起他左、右两侧的叉子。他们的活动规律都是一样的，即思考、吃饭、思考。,叉子是这个问题中的临界资源，在一段时间内只允许一个哲学家使用，即每把叉子都必须互斥使用。设5个哲学家对应5个进程p0，P1，p4，5把叉子对应5个资源R0，R1，R4。进程pi左边的叉子为Ri，右边的叉子为R(i+1)，而进程P4左边的叉子为R4，右边的叉子为R0。,兰州理工大学计算机与通信学院,兰州理工大学计算机与通信学院,1用记录型信号量解决哲学家用餐问题 semaphore fork5=1,1,1,1,1;,进程pi（i=0,4）do 思考；P(forki);P(forki+1%5);用餐；V(forki);V(forki+1%5);while(1);问题？解决方案？,兰州理工大学计算机与通信学院,2用AND型信号量集解决哲学家用餐问题 在哲学家用餐问题中，由于每位哲学家要申请两个临界资源（两把叉子），故可用AND型信号量集来解决。,进程pi（i=0,4）do 思考；Swait(forki,forki+1%5);用餐；Ssignal(forki,forki+1%5);while(1);,兰州理工大学计算机与通信学院,2.5 经典进程同步问题,2.5.1 生产者消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者写者问题,兰州理工大学计算机与通信学院,一个数据对象（比如一个文件或记录）若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求修改它，我们把那些只想读的进程称之为“读者”；而把要求修改的进程称为“写者”。显然，所有读者和写者共享一个文件（或一组数据）时要协调工作，要求：读者进程只要求读该对象的内容，且多个读者可同时对文件执行读操作；写者进程则要求修改它，某一时刻只允许一个写者进程往文件中写信息；任一写者进程在完成写操作之前不允许其它读者或写者工作；写者进程执行写操作前，应让所有的写者和读者进程退出。,兰州理工大学计算机与通信学院,1用记录型信号量解决读者与写者问题 可设置两个信号量：rwmutex用于实现一个写者与其它读者写者互斥地访问共享数据；由于多个读者可同时对共享数据或文件执行读操作，所以需设置read_count计数器，用以记录正在读共享数据时的读者数，因read_count是所有读者的共享变量，对它的修改操作必须互斥进行，设r信号量用于读者互斥地访问read_count。rwmutex、r的初值均为1，read_count的初值为0，即有：semaphore rwmutex=1,r=1;int read_count=0;,兰州理工大学计算机与通信学院,读者进程read i(i=1,2,)do P(r);read_count=read_count+1;if(read_count=1)P(rwmutex);V(r);读数据；P(r);read_count=read_count-1;if(read_count=0)V(rwmutex);V(r);while(1);,写者进程write j(j=1,2,)do P(