计算机操作系统原理第二章进程描述与控制.ppt

计算机操作系统,东华大学计算机科学与技术学院,主讲：李继云,2,本章重点,并发程序的特点进程的概念进程和程序的区别进程状态进程控制原语线程的概念进程的同步与互斥,3,2.1 进程描述2.2 进程控制2.3 线程2.4 实例：Solaris,第2章 进程描述与控制主要内容,2.5 进程同步2.6 经典进程的同步问题2.7 管程机制2.8 进程通信,4,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,5,2.1.1 程序的顺序执行,程序的顺序执行如图 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。,6,程序顺序执行的特点,顺序性：一个程序开始执行必须要等到前一个程序已执行完成。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。,前趋图,前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。结点：一个程序段或进程，乃至一条语句 有向边：偏序或前趋关系 把没有前趋的结点称为初始结点(Initial Node)没有后继的结点称为终止结点(Final Node),每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。,前趋图中必须不存在循环,前趋图,9,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,10,2.1.2 程序的并发执行,所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。,并发与并行概念的区别？Concurrency，parallel,11,并发执行实例 并发程序的时间相关性,誊抄 用卡片输入机尽快地把一个文本复写（誊抄）到行式打印机上去。由Brinch Hansen提出,12,循环顺序程序的誊抄方案,输入：f 输出：g while(f 不为空）input;output;,13,循环顺序程序的誊抄方案,设读卡机的标定速度是1000卡/分，打印机的标定速度是600行/分，那么此系统的最高传输速度为（）行/分？,14,两个并发程序方案,设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。,15,两个并发程序方案,16,两个并发程序方案,cobegin while(不为结束符）input;send;while(buffer不为空）receive;output;coend,17,两个并发程序方案,誊抄的速度可以提高到600行/分。存在的问题：读卡机和打印机速度不匹配，导致虽然提高了设备利用率，但是不能正确誊抄。a、若打印的速度高于输入的速度；b、若输入的速度高于打印的速度,18,三个并发程序方案,假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。,19,三个并发程序方案,缓冲区T,标准输入（键盘）,f,标准输出（打印机）,get,g,copy,缓冲区S,put,20,三个并发程序方案,如何实现？while(誊抄未完成)cobeginget(s,f);copy(s,t);put(t,g);coend,21,三个并发程序方案,if(f 不为空)get(s,f);while(誊抄未完成)t=s;cobegin put(t,g);get(s,f);coend,22,方案比较,方案1系统利用率最低方案2、3提高了设备利用率，但需要增设缓冲区，且方案2会因速度匹配出错。思考：试举出现实生活中的此类例子。,23,程序并发执行的特点,失去了程序的封闭性如果一个程序的执行可以改变另一个程序的变量，那么后者的输出就可能有赖于各程序执行的相对速度，即失去了程序封闭性的特点。程序与计算不再一一对应 程序静态；计算动态程序并发执行的相互制约 直接制约相互之间有逻辑关系（I,C,P）间接制约由于资源共享引起的联系（I1,I2）,24,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,25,2.1.3 进程的定义,进程的概念是60年代初首先由麻省理工学院的MULTICS系统和IBM公司的CTSS/360系统引入的。进程有很多各式各样的定义，如：行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra）一个具有一定独立功能的程序关于某个数据集合的一次运行活动。进程是一个程序与其数据一道通过处理机的执行所发生的活动,26,进程同程序的比较,程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。,27,进程同程序的比较,进程更能真实地描述并发，而程序不能进程是由程序和数据两部分组成的进程具有创建其他进程的功能，而程序没有同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程,28,思考,为什么要引入进程的概念？,29,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,30,2.1.4 进程的特征,动态性：进程是程序的执行并发性：多个进程可同存于内存中，能在一段时间内同时运行独立性：独立运行的基本单位，独立获得资源和调度的基本单位。异步性：各进程按各自独立的不可预知的速度向前推进结构特征：由用户程序、用户数据、系统栈和进程控制块四部分组成,31,进程的类型,按其任务性质分 系统进程 用户进程按其活动特点分 受CPU时间限制科学计算 受I/O限制商业联机事务处理,32,进程产生,通常有4种事件会导致新进程产生：在一个交互式环境中，当一个新用户在终端键入登录命令后，若是合法用户，系统将为该用户建立一个进程。在一个批处理环境中，为了响应一个任务的要求而产生进程。当运行中获取用户程序提出的某种请求后，OS可以代用户程序产生进程以实现某种功能，使用户不必等待。基于应用进程的需要，由已存在的进程产生另一个进程，以便使新程序以并发运行方式完成特定任务。,33,进程终止,导致进程终止的事件大致有14种：正常结束、超时限制、内存不足、超界、保护错误、算术错误、超越时限、I/O失败、非法指令、特权指令、错误使用数据、操作员或OS干预、父进程终止、父进程需要。,34,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,35,2.1.5 进程的状态及转换,进程有三种基本状态，进程在生命消亡前处于且仅处于三种基本状态之一。不同系统设置的进程状态数目不同。,36,进程的三种基本状态,就绪状态（Ready）：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。运行状态（Running）：正在运行的进程所处的状态为运行状态。拥有CPU。等待状态（Wait/Blocked）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态、阻塞、睡眠、封锁状态。,37,进程的状态变迁图,38,进程状态模型,运行：进程当前处于运行状态。就绪；进程已准备好运行。阻塞；进程等待某些事件发生（如I/O操作）后才能运行。创建：进程刚产生，但还未被操作系统提交到可运行进程池中。消失（撤销）：进程被操作系统从可运行进程池中释放。,39,进程状态模型,进程状态转换（转下表）,40,进程状态模型,41,进程挂起,处于非运行状态的进程：内存-外存 由于I/O操作比CPU计算慢得多，故常会出现内存中所有进程都等待I/O的现象。即使运行多个程序，处理器在大多数时间仍处于空闲状态。为此可采用交换方法，将内存中的一部分进程转移到磁盘中。在进程行为模式中需增加一个新的挂起状态，当内存所有进程阻塞时，操作系统可将一进程置为挂起状态并交换到磁盘，再调入另一进程执行。挂起状态与原有的阻塞和就绪状态结合为阻塞挂起状态和就绪挂起状态。,42,有挂起状态的进程转换图,(a)带有一个挂起状态,(b)带有两个挂起状态,进程挂起的原因,进程挂起,44,【思考题】,1在单处理机系统中，如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待运行；就绪等待,45,2.1 进程描述,2.1.1 程序的顺序执行2.1.2 程序的并发执行 2.1.3 进程的定义2.1.4 进程的特征 2.1.5 进程的状态及转换2.1.6 进程控制块,46,2.1.6 进程控制块（PCB）,为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（PCB）。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的,47,PCB的内容,进程标识处理器状态信息进程调度信息进程控制信息,48,PCB的内容,进程标识：本进程的标识符(process ID)，唯一，通常是一个整数创建本进程的进程（父进程）的标识符用户标识符(user ID)；进程组关系,49,PCB的内容,处理器状态信息：通用寄存器指令计数器程序状态字PSW 状态码、状态信息用户栈指针,PCB的内容,进程调度信息：进程状态进程优先级调度所需其他信息 等待时间/执行时间等与调度算法有关等待的事件,50,51,PCB的内容,进程控制信息：程序和数据地址进程同步和通信机制 信号量、消息队列指针资源清单链接指针 下一个PCB的首址,52,PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。,PCB表组织方式,53,链接结构,相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表就绪链表、阻塞链表,54,55,索引结构,对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址,56,57,进程队列,不同状态进程分别组成队列运行队列、就绪队列、等待队列,58,59,进程映像,进程映像在内存中可以连续存放或非连续存放。用户程序用户数据栈用于过程调用和参数传递进程控制块PCB在OS空间用户进程不能直接访问、修改自己的PCB,60,思考,请说说PCB的作用。,61,2.1 进程描述2.2 进程控制2.3 线程2.4 实例：Solaris,第2章 进程描述与控制主要内容,2.5 进程同步2.6 经典进程的同步问题2.7 管程机制2.8 进程通信,62,2.2 进程控制,操作系统内核负责控制和管理进程的产生、执行和消亡的整个过程，这主要通过对它们的控制操作实现。操作系统的进程控制操作主要有：创建进程、撤消进程、阻塞（挂起）进程、恢复进程、改变进程优先级、封锁进程、唤醒进程、调度进程等。,63,进程控制的实现,进程控制就是对系统中的所有进程实施管理，进程控制一般由原语来实现。所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点是原语执行时不可被中断。,64,思考,如何实现原语?,65,常用的进程控制原语,创建原语撤销原语阻塞原语唤醒原语,66,进程创建,申请空白PCB为新进程分配资源 如内存初始化进程控制块 将新进程插入就绪队列,67,进程创建,进程创建原语的形式：create(name,priority,start-addr),68,进程创建,算法 create输入：新进程的符号名，优先级，开始执行地址输出：新创建进程的内部标志pid 从pcb资源池中申请一个空闲的pcb结构；if（无空pcb结构）return（错误码）；用入口参数设置pcb内容；置进程为“就绪”态；将新进程的pcb入就绪队列；将新进程的pcb入总链队列；return（新进程的pid）；,69,思考,为什么创建进程要用原语来实现？,70,进程撤销,根据被终止进程的标识符，从PCB集合中检索出该进程的PCB将进程所拥有的资源交给父进程或系统进程释放PCB,71,进程撤销,算法:kill输入：无输出：无 由运行指针得到当前进程的pid；释放本进程占用的资源；该进程从总链队列中摘去；释放PCB；转进程调度程序；,72,进程阻塞,阻塞：当一个进程所期待的某一事件尚未出现时，该进程调用阻塞原语将自己阻塞。进程阻塞是进程的自身的一种主动行为。,73,进程阻塞,算法：susp输入：chan（进程等待的原因）输出：无 保护现进程的CPU的现场到PCB结构中；置该进程的状态为“阻塞”态；将该进程的PCB插入到chan的等待队列；转进程调度程序；,74,进程唤醒,唤醒：处于阻塞状态的进程是绝不可能叫醒它自己的，它必须由它的合作进程用唤醒原语唤醒它。,75,进程唤醒,进程唤醒原语的形式：wakeup(chan)其中：chan 唤醒进程阻塞的原因。,76,进程唤醒,算法 wakeup输入：chan等待的事件（阻塞原因）输出：无保护现行进程的CPU现场到pcb结构中；置该进程为“就绪”态；将该进程入就绪队列；找到该阻塞原因的队列指针；for（该队列上每一个等待的进程）将进程移出此等待队列；置进程状态为“就绪”；将进程入就绪队列；转进程调度；,77,思考,请设想一下进程在什么情况下会变为阻塞状态？阻塞进程在什么情况下会被唤醒？谁来唤醒它？,78,进程切换,在某时刻，一个正在运行的进程被中断，操作系统就将另一个进程置为运行状态，并对其进行控制。当操作系统掌握控制权时，切换随时会发生。可能将控制权交给操作系统的事件有：中断 对外部事件的响应陷阱 处理错误或意外情况系统调用 调用操作系统功能,79,进程切换,操作系统将进行以下步骤完成进程切换：保存处理器内容。对当前运行进程的PCB进行更新。将这个进程的PCB移入适当的队列。挑选其他进程执行。对挑选进程的PCB进行更新。对存储器管理数据结构进行更新。将被选中进程上次移出时的处理器状态进行恢复。,80,思考,OS如何进行进程切换？何时会发生进程切换？,81,2.1 进程描述2.2 进程控制2.3 线程2.4 实例：Solaris,第2章 进程描述与控制主要内容,2.5 进程同步2.6 经典进程的同步问题2.7 管程机制2.8 进程通信,82,2.3 线程,2.3.1 线程的引入 2.3.2 用户级线程和内核支持线程 2.3.3 线程与进程的比较,83,2.3.1 线程的引入,引入进程的目的是为了使多个程序并发执行，以改善资源利用率、提高系统吞吐量。引入线程则是为了减少程序并发执行时所付出的时空开销。,84,进程的两个基本属性,1.进程是一个可拥有资源的基本单位。2.进程同时又是一个可独立调度和分派的基本单位。进程作为一个资源拥有者，在创建、撤消、切换中，系统必须为之付出较大时空开销。所以系统中进程的数量不宜过多，进程切换的频率不宜过高，但这也就限制了并发程度的进一步提高。,85,为解决此问题，人们想到将进程的上述两个属性分开，即对作为调度和分派的基本单位，不同时作为独立分配资源的单位；对拥有资源的单位，不对之进行频繁切换。线程因而产生。,线程,86,线程,在引入线程的OS中，线程是进程中的一个实体，是被系统独立调度和分派的基本单位。线程自己基本不拥有系统资源，只拥有少量必不可少的资源：程序计数器、一组寄存器、栈。它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程；同一进程中的多个线程之间可以并发执行。,87,引入线程的好处,创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统,88,线程的定义及特征,线程是进程内的一个相对独立的、可独立调度和指派的执行单元。线程具有以下性质：线程是进程内的一个相对独立的可执行单元。线程是操作系统中的基本调度单元。一个进程中至少应有一个线程。线程并不拥有资源，而是共享和使用包含它的进程所拥有的所有资源。线程在需要时也可创建其他线程。,89,线程的状态和管理,线程也有一个从创建到消亡的生命过程，虽然在不同的操作系统，线程的状态设计不完全相同，但就绪、运行、阻塞3个关键的状态是共有的。线程中不具有进程中的挂起状态。对具有多线程的进程状态，若一个线程被阻塞，整个进程不被阻塞。线程使用线程控制块(TCB)来描述其数据结构。线程的状态转换是通过相关的控制原语来实现的。,90,例子,LAN中的一个文件服务器，在一段时间内需要处理几个文件请求。因此有效的方法是：为每一个请求创建一个线程。在一个SMP机器上：多个线程可以同时在不同的处理器上运行。,91,例子,一个线程显示菜单，并读入用户输入；另一个线程执行用户命令。考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分可以以线程方式实现。当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程。,92,2.3 线程,2.3.1 线程的引入 2.3.2 用户级线程和内核支持线程 2.3.3 线程与进程的比较,93,2.3.2 用户级线程和内核支持线程,对于线程可分为两类内核支持线程，它们是依赖于内核的，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤消、切换都由内核实现。用户级线程，对于这种线程的创建、撤消、和切换，都不用系统调用来实现。内核并不知道用户级线程的存在。,94,用户级线程（User Level Thread）,由应用程序完成所有线程的管理 通过线程库(用户空间)：一组管理线程的函数 线程库提供一个线程运行管理系统（运行系统）核心不知道线程的存在线程切换不需要核心态特权调度是应用特定的,95,线程库,提供线程运行管理系统：创建、撤消线程在线程之间传递消息和数据调度线程执行保护和恢复线程上下文,96,用户级线程的优点和缺点,优点：线程切换不调用核心调度是应用程序特定的：可以选择最好的算法ULT可运行在任何操作系统上（只需要线程库），可以在一个不支持线程的OS上实现,97,用户级线程的优点和缺点,缺点：大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上,98,核心级线程（KLT）,所有线程管理由核心完成没有线程库，但核心提供API核心维护进程和线程的上下文线程之间的切换需要核心支持以线程为基础进行调度例子：Windows 2000/XP,99,核心级线程的优点和缺点,优点：对多处理器，核心可以同时调度同一进程的多个线程阻塞是在线程一级完成缺点：在同一进程内的线程切换调用内核，导致速度下降,100,图：用户级和核心级线程,101,2.3 线程,2.3.1 线程的引入 2.3.2 用户级线程和内核支持线程 2.3.3 线程与进程的比较,102,2.3.3 线程与进程的比较,线程具有进程的许多特征，故又称轻型进程，传统进程称重型进程。在引入线程的OS中，每一进程都拥有多个线程，至少一个。,103,1、调度在传统OS中，拥有资源、独立调度和分派的基本单位都是进程，在引入线程的系统中，线程是调度和分派的基本单位，而进程是拥有资源的基本单位。在同一个进程内线程切换不会产生进程切换，由一个进程内的线程切换到另一个进程内的线程时，将会引起进程切换。,线程与进程的比较,104,2、并发性在引入线程的系统中，进程之间可并发，同一进程内的各线程之间也能并发执行。因而系统具有更好的并发性。,线程与进程的比较,105,3、拥有资源无论是传统OS，还是引入线程的OS，进程都是拥有资源的独立单位，线程一般不拥有系统资源，但它可以访问隶属进程的资源。即一个进程的所有资源可供进程内的所有线程共享。,线程与进程的比较,106,4、系统开销进程的创建和撤消的开销要远大于线程创建和撤消的开销，进程切换时，当前进程的CPU环境要保存，新进程的CPU环境要设置，线程切换时只须保存和设置少量寄存器，并不涉及存储管理方面的操作，可见，进程切换的开销远大于线程切换的开销。同时，同一进程内的各线程由于它们拥有相同的地址空间，它们之间的同步和通信的实现也变得比较容易。,线程与进程的比较,107,2.1 进程描述2.2 进程控制2.3 线程2.4 实例：Solaris,第2章 进程描述与控制主要内容,2.5 进程同步2.6 经典进程的同步问题2.7 管程机制2.8 进程通信,108,2.4 线程实例：Solaris,进程：用户地址空间用户栈进程控制块,109,实例：Solaris（续1）,用户级线程（线程库）：可在应用进程中建立多个ULT每个ULT需要：栈、程序计数器不受调度程序的调度，线程切换快对操作系统不可见,110,核心级线程：设置了大量KLT有一个小的数据结构和栈完成内核的所有工作处理器调度的单位,实例：Solaris（续2）,111,轻型进程（LWP）：每个ULT利用LWP与内核通信每个LWP支持一个或多个用户级线程，并映射到一个核心级线程每个LWP对应用程序可见，内核看到的是多个LWP而看不到ULT,实例：Solaris（续3）,112,113,思考,为什么要引入线程？任何两个线程切换的开销是大致相当的吗？OS如何管理和控制线程？（提示：OS如何管理和控制进程）,114,小结,概念：并发、进程、线程关系：程序的顺序执行和并发执行 进程和程序 进程和线程,115,2.1 进程描述2.2 进程控制2.3 线程2.4 实例：Solaris,第2章 进程描述与控制主要内容,2.5 进程同步2.6 经典进程的同步问题2.7 管程机制2.8 进程通信,2.5 进程同步,进程同步是指对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性；或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的互斥）。用来实现同步的机制称为同步机制。如：信号量机制；管程机制。,2.5 进程同步,2.5.1 进程同步的基本概念两种形式的制约关系临界资源、临界区同步机制应遵循的规则2.5.2 信号量机制整型信号量记录型信号量AND型信号量集、一般信号量集2.5.3 信号量的应用信号量实现进程互斥信号量描述进程间的前趋关系,2.5.1 进程同步的基本概念,1、两种形式的制约关系系统中诸进程之间在逻辑上存在着两种制约关系：直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。间接制约关系（进程互斥）：是进程共享独占型资源而必须互斥执行的间接制约关系。同步与互斥比较,一次只允许一个进程使用的资源称为临界资源，如打印机，绘图机；变量，数据等，诸进程间采取互斥方式式实现对这种临界资源的共享，从而实现并行程序的封闭性。,2、临界资源、临界区,例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改:其中R1和R2为处理机中的两个寄存器。A与B均对X+1，即X+2。若按另一顺序对变量进行修改：结果x只加了1.,A:R1=X;B:R2=X;A:R1=R1+1;X=R1;B:R2=R2+1;X=R2;,2、临界资源、临界区,为了保证临界资源的正确使用，可以把临界资源的访问过程分成以下几部分：,进入区增加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问。退出区增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。剩余区进程中除了进入区、临界区及退出区之外的其余代码。,2、临界资源、临界区,要进入临界区的若干进程必须满足：（1）一次只允许一个进程进入临界区（2）任何时候，处于临界区的进程不得多于一个（3）进入临界区的进程要在有限的时间内退出（4）如果不能进入自己的临界区，则应让出处理机资源解决临界区（互斥）问题的几类方法：（1）软件方法（2）硬件方法（3）P-V操作,同步机制,2、临界资源、临界区,3、同步机制应遵循的规则,有空让进(空闲让进）:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。互斥（忙则等待）:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态.让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。,2.5 进程同步,2.5.1 进程同步的基本概念两种形式的制约关系临界资源、临界区同步机制应遵循的规则2.5.2 信号量机制整型信号量记录型信号量AND型信号量集、一般信号量集2.5.3 信号量的应用信号量实现进程互斥信号量描述进程间的前趋关系,2.5.2 信号量机制,解决临界区（互斥）问题的几类方法 软件方法 硬件方法 加锁机制,126,软件方法解决进程互斥,现在很少用软件方法解决互斥，但通过学习软件解法能了解到，在早期进程互斥问题的解决并不是一件很简单的事。问题：假如有两个进程Pi和Pj，它们共享一个临界资源 R。如何用软件方法使进程Pi和Pj能互斥地访问R。下面介绍四个算法。,127,算法1,设整型变量turn，用于指示被允许进入临界区的进程的编号，即若turn=i，表示进程Pi可进入。turn=j表示进程Pj可进入。,128,算法1,进程Pi:Repeat While turni do no_op;Critical section turn:=j;Other codeUntil false;,129,算法1的问题,该算法可确保每次只允许一个进程进入临界区。但它强制两个进程轮流进入。如当Pi退出时将turn置为i，以便Pj能进入，但Pj暂不需要进入，而这时Pi又需要进入时，它无法进入。这不能保证准则1。,130,算法2,设var flag:array0.1 of boolean，若flagi=true，表示进程Pi正在临界区内。flagi=false表示进程Pi不在临界区内。若flagj=true，表示进程Pj正在临界区内。flagj=false表示进程Pj不在临界区内。,131,Pi进程：Repeat While flag j do no_op;flagi:=true;Critical section flagi:=false;Other codeUntil false;,算法2,132,算法2的问题,该算法可确保准则1。但又出现新问题。当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。这不能保证准则2。,133,算法2的问题,算法2的问题在于：当进程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。若在临界区的执行过程中发生了进程切换，Pi可能获得处理机而进入临界区。,134,算法3,在算法3中，设var Flag:array0.1 of boolean，若flagi=true，表示进程Pi希望进入临界区内。若flagj=true，表示进程Pj希望进入临界区。,135,Pi进程：Repeat flagi:=true;While flagj do no_op;Critical section flagi:=false;Other codeUntil false;,算法3,136,算法3的问题,该算法可确保准则2。但又出现新问题。它可能造成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true.最终谁也不能进入。这不能保证准则1。,137,一种延时解法,Pi进程：Repeat flagi:=true;While flagj do no_op;begin flagi:=false;flagi:=true;end Critical section flagi:=false;Other codeUntil false;,138,算法4（正确算法）,组合算法1、3，为每一进程设标志位flagi，当flagi=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。,139,进程为了进入先置flagi=true，并置turn为j，表示应轮到pj进入。接着再判断flagj and turn=j的条件是否满足。若不满足则可进入。或者说，当flagj=false或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。,算法4（正确算法）,140,算法4（正确算法）,Repeat flagi:=true;turn:=j;While(flag j and turn=j)do no_op;Critical section flagi:=false;Other codeUntil false,141,软件解法的缺点,1.忙等待2.实现过于复杂，需要较高的编程技巧,142,硬件方法解决进程互斥,用软件解决很难，现代计算机大多提供一些硬件指令。利用Test-and-Set指令实现互斥 利用swap指令实现进程互斥,143,Test-and-Set指令实现互斥,1、Test-and-Set指令function TS(var lock:boolean):boolean;begin if lock=0 then begin lock:=1;TS:=true;end else TS:=false end;其中，有lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。,144,2、利用TS指令实现进程互斥为每个临界资源设置一个全局布尔变量lock，并赋初值false，表示资源空闲。Repeat while TS(lock)do skip;critical section lock:=false;Other codeUntil false;,Test-and-Set指令实现互斥,145,swap指令实现进程互斥,1、swap指令又称交换指令，X86中称为XCHG指令。Procedure swap(var a,b:boolean);Var temp:boolean;Begin Temp:=a;A:=b;B:=temp;End;,146,2、利用swap实现进程互斥 为每一临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中有局部布尔变量key。Repeat key:=true;RepeatSwap(lock,key);Until key=false;Critical section lock:=false;Other codeUntil false;,swap指令实现进程互斥,147,用原语实现进程互斥,锁即操作系统中的一标志位，表示资源可用，表示资源已 被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。通常锁用w表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。,148,上锁和开锁原语,上锁原语lock(w)可描述为：L：if(w=1)goto L else w=1；开锁原语unlock(w)可描述为：w=0；,149,用原语实现进程互斥,150,改进的上锁原语,上述上锁原语中存在忙等待。,151,改进的开锁原语,2.5.2 信号量机制,信号量机制是荷兰科学家在1965年提出的一种同步机制，也称为P、V操作。由最初的整型信号量发展为记录型信号量，进而发展为信号量集。整型信号量记录型信号量信号量集（AND信号量集、一般信号量集）,1、整型信号量,整型信号量非负整数，除了初始化外，只能通过两个原子操作wait和signal（P，V）来访问。wait和signal操作描述：wait(S)：while S0 do no-op 测试有无可用资源 S:=S-1;可用资源数减一个单位 signal(S):S:=S+1;主要问题：只要S0，wait操作就不断地测试（盲等），因而，未做到“让权等待”。,2、记录型信号量,基本思想 1、设置一个代表资源数目的整型变量value（资源信号量）2、设置一链表L用于链接所有等待的进程记录型信号量的数据结构 Type semaphore=record value:integer;L:list of process;endwait和signal操作描述：wait(S)：S.value:=S.value-1;if S.value0 then block(S.L);signal(S):S.value:=S.value+1;if S.value0 then wakeup(S.L);做到“让权等待”。,3、AND型信号量、一般信号量集（了解）,AND型信号量的基本思想 将进程在整个运行过程中所需要的所有临界资源，一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程。从而可避免死锁发生。在wait操作中，增加了一个“AND”条件，故称为AND同步。一般信号集的基本思想 一次可分配多个某种临界资源，而不需执行N次的wait操作；每次分配前都测试该种资源数目是否大于测试值。,2.5 进程同步,2.5.1 进程同步的基本概念两种形式的制约关系临界资源、临界区同步机制应遵循的规则2.5.2 信号量机制整型信号量记录型信号量AND型信号量集、一般信号量集2.5.3 信号量的应用信号量实现进程互斥信号量描述进程间的前趋关系,2.5.3 信号量的应用,利用信号量实现进程互斥 利用信号量可以方便地解决临界区问题（进程互斥）。为临界资源设置一互斥信号量mutex，初值为1，则实现进程P1和P2互斥的描述：,P1进程：.wait(mutex);critical section;signal(mutex);.,P2进程：.wait(mutex);critical section;signal(mutex);.,利用信号量描述前趋关系 信号量可用来控制程序或语句间的前趋关系。Eg:设S1,S2,S3,S4为一组合作进程，其前趋图如图所示，用P、V操作实现其同步。,var a,b,c,d:semaphore:=0,0,0,0;/*表示进程是否执行完*/main()cobegin s1();s2();s3();s4();coend,练习,设P1,P2,P3,P4,P5,P6为一组合作进程，其前趋图如图所示，用P、V操作实现其同步。,160,解,设有5个信号量S2、S3、S4、S5、S6，初值均为P1：P2：P3：P(S2);P(S3);V(S2);V(S3)；V(S4);V(S5);V(S6);,P4：P5：P6：P(S4);P(S5);P(S6);P(S6);P(S6);V(S6);V(S6)