• 1. 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题 2.6 进程通信 2.7 线程(Threads)的基本概念 2.8 线程的实现
  • 2.      2.1 前趋图和程序执行   在早期未配置OS的系统和单道批处理系统中,程序的执行方式是顺序执行,即在内存中仅装入一道用户程序,由它独占系统中的所有资源,只有在一个用户程序执行完成后,才允许装入另一个程序并执行。可见,这种方式浪费资源、系统运行效率低等缺点。
  • 3. 2.1.1 前趋图   为了能更好地描述程序的顺序和并发执行情况,我们先介绍用于描述程序执行先后顺序的前趋图。所谓前趋图(Precedence Graph),是指一个有向无循环图,可记为DAG(Directed Acyclic Graph),它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段,乃至一条语句,结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)。
  • 4.   进程(或程序)之间的前趋关系可用“→”来表示,如果进程Pi和Pj存在着前趋关系,可表示为(Pi,Pj)∈→,也可写成Pi→Pj,表示在Pj开始执行之前Pi 必须完成。此时称Pi是Pj的直接前趋,而称Pj是Pi的直接后继。在前趋图中,把没有前趋的结点称为初始结点(Initial Node),把没有后继的结点称为终止结点(Final Node)。此外,每个结点还具有一个重量(Weight),用于表示该结点所含有的程序量或程序的执行 时间。
  • 5.   在图2-1(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)}
  • 6.   应当注意,前趋图中是不允许有循环的,否则必然会产生不可能实现的前趋关系。如图2-1(b)所示的前趋关系中就存在着循环。它一方面要求在S3开始执行之前,S2必须完成,另一方面又要求在S2开始执行之前,S3必须完成。显然,这种关系是不可能实现的。          S2→S3,S3→S2
  • 7. 图2-1 前趋图
  • 8. 2.1.2 程序顺序执行   1. 程序的顺序执行   通常,一个应用程序由若干个程序段组成,每一个程序段完成特定的功能,它们在执行时,都需要按照某种先后次序顺序执行,仅当前一程序段执行完后,才运行后一程序段。例如,在进行计算时,应先运行输入程序,用于输入用户的程序和数据;然后运行计算程序,对所输入的数据进行计算;最后才是运行打印程序,打印计算结果。我们用结点(Node)代表各程序段的操作(在图2-1中用圆圈表示),其中I代表输入操作,C代表计算操作,P为打印操作,用箭头指示操作的先后次序。
  • 9.   这样,上述的三个程序段间就存在着这样的前趋关系:Ii→Ci→Pi,其执行的顺序可用前趋图2-2(a)描述。   即使是一个程序段,也可能存在着执行顺序问题,下面示出了一个包含了三条语句的程序段:   S1: a :=x+y;   S2: b :=a-5;   S3: c :=b+1; 其中,语句S2必须在语句S1后(即a被赋值)才能执行,语句S3也只能在b被赋值后才能执行,因此,三条语句存在着这样的前趋关系:S1→S2→S3,应按前趋图2-2(b)所示的顺序执行。
  • 10. 图2-2 程序顺序执行的前趋图
  • 11.   2. 程序顺序执行时的特征   由上所述可以得知,在程序顺序执行时,具有这样三个特征:① 顺序性:指处理机严格地按照程序所规定的顺序执行,即每一操作必须在下一个操作开始之前结束;② 封闭性:指程序在封闭的环境下运行,即程序运行时独占全机资源,资源的状态(除初始状态外)只有本程序才能改变它,程序一旦开始执行,其执行结果不受外界因素影响;③ 可再现性:指只要程序执行时的环境和初始条件相同,当程序重复执行时,不论它是从头到尾不停顿地执行,还是“停停走走”地执行,都可获得相同的结果。程序顺序执行时的这种特性,为程序员检测和校正程序的错误带来了很大的方便。
  • 12. 2.1.3 程序并发执行   1. 程序的并发执行   我们通过一个常见的例子来说明程序的顺序执行和并发执行。在图2-2中的输入程序、计算程序和打印程序三者之间,存在着Ii→Ci→Pi这样的前趋关系,以至对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时,每道作业的输入、计算和打印程序段的执行情况如图2-3所示。
  • 13. 图2-3 程序并发执行时的前趋图
  • 14.   由图2-3可以看出,存在前趋关系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+2   S2: b :=y+4   S3: c :=a+b   S4: d :=c+b   可画出图2-4所示的前趋关系。可以看出:S3必须在a和b被赋值后方能执行;S4必须在S3之后执行;但S1和S2则可以并发执行,因为它们彼此互不依赖。
  • 15. 图2-4 四条语句的前趋关系
  • 16.   2. 程序并发执行时的特征   在引入了程序间的并发执行功能后,虽然提高了系统的吞吐量和资源利用率,但由于它们共享系统资源,以及它们为完成同一项任务而相互合作,致使在这些并发执行的程序之间必将形成相互制约的关系,由此会给程序并发执行带来新的特征。   (1) 间断性。   (2) 失去封闭性。   (3) 不可再现性。
  • 17.        2.2 进 程 的 描 述  2.2.1 进程的定义和特征   1. 进程的定义   在多道程序环境下,程序的执行属于并发执行,此时它们将失去其封闭性,并具有间断性,以及其运行结果不可再现性的特征。由此,决定了通常的程序是不能参与并发执行的,否则,程序的运行也就失去了意义。为了能使程序并发执行,并且可以对并发执行的程序加以描述和控制,人们引入了“进程”的概念。
  • 18.   对于进程的定义,从不同的角度可以有不同的定义,其中较典型的定义有:   (1) 进程是程序的一次执行。   (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。   (3) 进程是具有独立功能的程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位。
  • 19.   2. 进程的特征   进程和程序是两个截然不同的概念,除了进程具有程序所没有的PCB结构外,还具有下面一些特征:   (1) 动态性。   (2) 并发性。   (3) 独立性。   (4) 异步性。
  • 20. 补充:进程与程序的区别: (1)程序是指令的有序集合,其本身没有任何运行的含义,是一个静态的概念。而进程是程序在处理机上的一次执行过程,它是一个动态的概念。 (2)程序可以作为一种软件资料长期存在,而进程是有一定生命期的。程序是永久的,进程是暂时的。 (3)进程更能真实地描述并发,而程序不能 (4)进程是由程序和数据两部分组成的 (5)进程具有创建其他进程的功能,而程序没有 (6)同一程序同时运行于若干个数据集合上,它将属于若干个不同的进程。也就是说同一程序可以对应多个进程
  • 21. 2.2.2 进程的基本状态及转换   1. 进程的三种基本状态   由于多个进程在并发执行时共享系统资源,致使它们在运行过程中呈现间断性的运行规律,所以进程在其生命周期内可能具有多种状态。一般而言,每一个进程至少应处于以下三种基本状态之一:   (1) 就绪(Ready)状态。(可有多个)   (2) 执行(Running)状态。(个数与处理机个数相等)   (3) 阻塞(Block)状态。(可有多个)
  • 22.   2. 三种基本状态的转换   进程在运行过程中会经常发生状态的转换。例如,处于就绪状态的进程,在调度程序为之分配了处理机之后便可执行,相应地,其状态就由就绪态转变为执行态;正在执行的进程(当前进程)如果因分配给它的时间片已完而被剥夺处理机暂停执行时,其状态便由执行转为就绪;如果因发生某事件,致使当前进程的执行受阻(例如进程访问某临界资源,而该资源正被其它进程访问时),使之无法继续执行,则该进程状态将由执行转变为阻塞。图2-5示出了进程的三种基本状态,以及各状态之间的转换关系。
  • 23. 图2-5 进程的三种基本状态及其转换状态变化: 就绪状态 → 执行状态 执行状态 → 就绪状态 执行状态 → 阻塞状态 阻塞状态 → 就绪状态
  • 24.   3. 创建状态和终止状态   1) 创建状态   如前所述,进程是由创建而产生。创建一个进程是个很复杂的过程,一般要通过多个步骤才能完成:如首先由进程申请一个空白PCB,并向PCB中填写用于控制和管理进程的信息;然后为该进程分配运行时所必须的资源;最后,把该进程转入就绪状态并插入就绪队列之中。但如果进程所需的资源尚不能得到满足,比如系统尚无足够的内存使进程无法装入其中,此时创建工作尚未完成,进程不能被调度运行,于是把此时进程所处的状态称为创建状态。
  • 25.   2) 终止状态   进程的终止也要通过两个步骤:首先,是等待操作系统进行善后处理,最后将其PCB清零,并将PCB空间返还系统。当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,它将进入终止状态。进入终止态的进程以后不能再执行,但在操作系统中依然保留一个记录,其中保存状态码和一些计时统计数据,供其他进程收集。一旦其他进程完成了对其信息的提取之后,操作系统将删除该进程,即将其PCB清零,并将该空白PCB返还系统。图2-6示出了增加了创建状态和终止状态后进程的五种状态及转换关系图。
  • 26. 图2-6 进程的五种基本状态及转换
  • 27. 2.2.3 挂起操作和进程状态的转换 1. 挂起操作的引入   引入挂起操作的原因,是基于系统和用户的如下需要:   (1) 终端用户的需要。   (2) 父进程请求。   (3) 负荷调节的需要。   (4) 操作系统的需要。
  • 28.   2. 引入挂起原语操作后三个进程状态的转换   在引入挂起原语Suspend和激活原语Active后,在它们的作用下,进程将可能发生以下几种状态的转换:   (1) 活动就绪→静止就绪。   (2) 活动阻塞→静止阻塞。   (3) 静止就绪→活动就绪。   (4) 静止阻塞→活动阻塞。
  • 29.   3. 引入挂起操作后五个进程状态的转换   如图2-8示出了增加了创建状态和终止状态后具有挂起状态的进程状态及转换图。   如图2-8所示,引进创建和终止状态后,在进程状态转换时,与图2-7所示的进程五状态转换相比较,要增加考虑下面的几种情况:   (1)  NULL→创建:   (2) 创建→活动就绪:   (3) 创建→静止就绪:   (4) 执行→终止:
  • 30. 图2-7 具有挂起状态的进程状态图 图 2-5 进程的三种基本状态及其转换
  • 31. 图 2-8 具有创建、终止和挂起状态的进程状态图 创建许可终止释放
  • 32. 2.2.4 进程管理中的数据结构   1. 操作系统中用于管理控制的数据结构   在计算机系统中,对于每个资源和每个进程都设置了一个数据结构,用于表征其实体,我们称之为资源信息表或进程信息表,其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针,可以将同类资源或进程的信息表,或者同一进程所占用的资源信息表分类链接成不同的队列,便于操作系统进行查找。
  • 33.   如图2-9所示,OS管理的这些数据结构一般分为以下四类:内存表、设备表、文件表和用于进程管理的进程表,通常进程表又被称为进程控制块PCB。
  • 34. 图2-9 操作系统控制表的一般结构
  • 35. 2. 进程控制块PCB的作用 (1) 作为独立运行基本单位的标志。 (2) 能实现间断性运行方式。 (3) 提供进程管理所需要的信息。 (4) 提供进程调度所需要的信息。 (5) 实现与其它进程的同步与通信。
  • 36.   3. 进程控制块中的信息   在进程控制块中,主要包括下述四个方面的信息。   1) 进程标识符   进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符:   (1) 外部标识符。   (2) 内部标识符。
  • 37.   2) 处理机状态   处理机状态信息也称为处理机的上下文,主要是由处理机的各种寄存器中的内容组成的。
  • 38.   3) 进程调度信息   在OS进行调度时,必须了解进程的状态及有关进程调度的信息,这些信息包括:① 进程状态,指明进程的当前状态,它是作为进程调度和对换时的依据;② 进程优先级,是用于描述进程使用处理机的优先级别的一个整数,优先级高的进程应优先获得处理机;③ 进程调度所需的其它信息,它们与所采用的进程调度算法有关,比如,进程已等待CPU的时间总和、进程已执行的时间总和等;④ 事件,是指进程由执行状态转变为阻塞状态所等待发生的事件,即阻塞原因。
  • 39.   4) 进程控制信息   是指用于进程控制所必须的信息,它包括:① 程序和数据的地址,进程实体中的程序和数据的内存或外存地(首)址,以便再调度到该进程执行时,能从PCB中找到其程序和数据;② 进程同步和通信机制,这是实现进程同步和进程通信时必需的机制,如消息队列指针、信号量等,它们可能全部或部分地放在PCB中;③ 资源清单,在该清单中列出了进程在运行期间所需的全部资源(除CPU以外),另外还有一张已分配到该进程的资源的清单;④ 链接指针,它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。
  • 40.   4. 进程控制块的组织方式   在一个系统中,通常可拥有数十个、数百个乃至数千个PCB。为了能对它们加以有效的管理,应该用适当的方式将这些PCB组织起来。目前常用的组织方式有以下三种。 (1) 线性方式,即将系统中所有的PCB都组织在一张线性表中,将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小,但每次查找时都需要扫描整张表,因此适合进程数目不多的系统。图2-10示出了线性表的PCB组织方式。
  • 41. 图2-10 PCB线性表示意图
  • 42.   (2) 链接方式,即把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。这样,可以形成就绪队列、若干个阻塞队列和空白队列等。对就绪队列而言,往往按进程的优先级将PCB从高到低进行排列,将优先级高的进程PCB排在队列的前面。同样,也可把处于阻塞状态进程的PCB根据其阻塞原因的不同,排成多个阻塞队列,如等待I/O操作完成的队列和等待分配内存的队列等。图2-11示出了一种链接队列的组织方式。
  • 43. 图2-11 PCB链接队列示意图执行指针就绪队列指针阻塞队列指针空闲队列指针...PCB1PCB2PCB3PCB4PCB6PCB7PCB8PCB9PCB543087901
  • 44.   (3) 索引方式,即系统根据所有进程状态的不同,建立几张索引表,例如,就绪索引表、阻塞索引表等,并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中,记录具有相应状态的某个PCB在PCB表中的地址。图2-12示出了索引方式的PCB组织。
  • 45. 图2-12 按索引方式组织PCB
  • 46.       2.3 进 程 控 制   进程控制是进程管理中最基本的功能,主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。如当一个正在执行的进程因等待某事件而暂时不能继续执行时,将其转变为阻塞状态,而在该进程所期待的事件出现后,又将该进程转换为就绪状态等。进程控制一般是由OS的内核中的原语来实现的。
  • 47. 2.3.1 操作系统内核   1. 支撑功能   (1) 中断处理。   (2) 时钟管理。   (3) 原语操作。
  • 48.   2. 资源管理功能   (1) 进程管理。   (2) 存储器管理。   (3) 设备管理。
  • 49. 2.3.2 进程的创建   1. 进程的层次结构   在OS中,允许一个进程创建另一个进程,通常把创建进程的进程称为父进程,而把被创建的进程称为子进程。子进程可继续创建更多的孙进程,由此便形成了一个进程的层次结构。如在UNIX中,进程与其子孙进程共同组成一个进程家族(组)。
  • 50.   2. 进程图   为了形象地描述一个进程的家族关系而引入了进程图(Process Graph)。所谓进程图就是用于描述进程间关系的一棵有向树,如图2-13所示。
  • 51. 图2-13 进程树
  • 52.   3. 引起创建进程的事件   为使程序之间能并发运行,应先为它们分别创建进程。导致一个进程去创建另一个进程的典型事件有四类:   (1) 用户登录。   (2) 作业调度。   (3) 提供服务。   (4) 应用请求。
  • 53.   4. 进程的创建(Creation of Process)   在系统中每当出现了创建新进程的请求后,OS便调用进程创建原语Creat按下述步骤创建一个新进程:   (1) 申请空白PCB,为新进程申请获得唯一的数字标识符,并从PCB集合中索取一个空白PCB。   (2) 为新进程分配其运行所需的资源,包括各种物理和逻辑资源,如内存、文件、I/O设备和CPU时间等。   (3) 初始化进程控制块(PCB)。   (4) 如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列。
  • 54. 2.3.3 进程的终止   1. 引起进程终止(Termination of Process)的事件   (1) 正常结束   (2) 异常结束   (3) 外界干预
  • 55.   2. 进程的终止过程   如果系统中发生了要求终止进程的某事件,OS便调用进程终止原语,按下述过程去终止指定的进程:   (1) 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态;   (2) 若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度;
  • 56.   (3) 若该进程还有子孙进程,还应将其所有子孙进程也都予以终止,以防它们成为不可控的进程;   (4) 将被终止进程所拥有的全部资源或者归还给其父进程,或者归还给系统;   (5) 将被终止进程(PCB)从所在队列(或链表)中移出,等待其它程序来搜集信息。
  • 57. 2.3.4 进程的阻塞与唤醒   1. 引起进程阻塞和唤醒的事件   有下述几类事件会引起进程阻塞或被唤醒:   (1) 向系统请求共享资源失败。   (2) 等待某种操作的完成。   (3) 新数据尚未到达。   (4) 等待新任务的到达。
  • 58.   2. 进程阻塞过程   正在执行的进程,如果发生了上述某事件,进程便通过调用阻塞原语block将自己阻塞。可见,阻塞是进程自身的一种主动行为。进入block过程后,由于该进程还处于执行状态,所以应先立即停止执行,把进程控制块中的现行状态由“执行”改为阻塞,并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列,则应将本进程插入到具有相同事件的阻塞队列。最后,转调度程序进行重新调度,将处理机分配给另一就绪进程,并进行切换,亦即,保留被阻塞进程的处理机状态,按新进程的PCB中的处理机状态设置CPU的环境。
  • 59.   3. 进程唤醒过程   当被阻塞进程所期待的事件发生时,比如它所启动的I/O操作已完成,或其所期待的数据已经到达,则由有关进程(比如提供数据的进程)调用唤醒原语wakeup,将等待该事件的进程唤醒。wakeup执行的过程是:首先把被阻塞的进程从等待该事件的阻塞队列中移出,将其PCB中的现行状态由阻塞改为就绪,然后再将该PCB插入到就绪队列中。
  • 60. 2.3.5 进程的挂起与激活   1. 进程的挂起   2. 进程的激活过程
  • 61.       2.4 进 程 同 步   在OS中引入进程后,一方面可以使系统中的多道程序并发执行,这不仅能有效地改善资源利用率,还可显著地提高系统的吞吐量,但另一方面却使系统变得更加复杂。如果不能采取有效的措施,对多个进程的运行进行妥善的管理,必然会因为这些进程对系统资源的无序争夺给系统造成混乱。致使每次处理的结果存在着不确定性,即显现出其不可再现性。
  • 62. 2.4.1 进程同步的基本概念   1. 两种形式的制约关系   1) 间接相互制约关系   2) 直接相互制约关系
  • 63.   2. 临界资源(Critical Resouce)   在第一章中我们曾经介绍过,许多硬件资源如打印机、 磁带机等,都属于临界资源,诸进程间应采取互斥方式,实现对这种资源的共享。
  • 64.   3. 临界区(critical section)   由前所述可知,不论是硬件临界资源还是软件临界资源,多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。
  • 65.   4. 同步机制应遵循的规则   为实现进程互斥地进入自己的临界区,可用软件方法,更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则:   (1) 空闲让进。当无进程在互斥区时,任何有权使用互斥区的进程可进入   (2) 忙则等待。不允许两个以上的进程同时进入互斥区   (3) 有限等待。任何进入互斥区的要求应在有限的时间内得到满足   (4) 让权等待。处于等待状态的进程应放弃占用CPU,以使其他进程有机会得到CPU的使用权
  • 66. 2.4.2 硬件同步机制   虽然可以利用软件方法解决诸进程互斥进入临界区的问题,但有一定难度,并且存在很大的局限性,因而现在已很少采用。相应地,目前许多计算机已提供了一些特殊的硬件指令,允许对一个字中的内容进行检测和修正,或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。
  • 67.   1. 关中断   关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。这样,进程在临界区执行期间,计算机系统不响应中断,从而不会引发调度,也就不会发生进程或线程切换。由此,保证了对锁的测试和关锁操作的连续性和完整性,有效地保证了互斥。但是,关中断的方法存在许多缺点:① 滥用关中断权力可能导致严重后果;② 关中断时间过长,会影响系统效率,限制了处理器交叉执行程序的能力;③ 关中断方法也不适用于多CPU 系统,因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。
  • 68.   2. 利用Test-and-Set指令实现互斥   这是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实现互斥的方法。在许多计算机中都提供了这种指令。
  • 69.   3. 利用Swap指令实现进程互斥   该指令称为对换指令,在Intel 80x86中又称为XCHG指令,用于交换两个字的内容。
  • 70. 2.4.3 信号量机制 一般说来,信号量的值与相应资源的使用情况有关. 对于两个并发进程,互斥信号量的值仅取1、0和-1三个值 若MUTEX=1表示没有进程进入临界区 若MUTEX=0表示有一个进程进入临界区 若MUTEX=-1表示一个进程进入临界区,另一个进程等待进入。
  • 71. 信号量S的物理含义: S>0表示有S个资源可用 S=0表示无资源可用 S<0则| S |表示S等待队列中的进程个数 信号量的初值应该大于等于0
  • 72. 1 整型信号量 是一个整型量,通过2个原子操作wait(s)和signal(s)来访问。 Wait(s):表示申请一个资源—P操作 Wait(s): while s<= 0 do no-op s:=s-1; Signal(s):表示释放一个资源—V操作 Signal(s): s:=s+1;
  • 73.   2. 记录型信号量   在整型信号量机制中的wait操作,只要是信号量S≤0,就会不断地测试。因此,该机制并未遵循“让权等待”的准则,而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后,又会出现多个进程等待访问同一临界资源的情况。为此,在信号量机制中,除了需要一个用于代表资源数目的整型变量value外,还应增加一个进程链表指针list,用于链接上述的所有等待进程。
  • 74.   3.  AND型信号量   前面所述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合,是一个进程往往需要获得两个或更多的共享资源后方能执行其任务。假定现有两个进程A和B,它们都要求访问共享数据D和E,当然,共享数据都应作为临界资源。
  • 75.   4. 信号量集   在前面所述的记录型信号量机制中,wait(S)或signal(S)操作仅能对信号量施以加1或减1操作,意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时,便要进行N次wait(S)操作,这显然是低效的,甚至会增加死锁的概率。此外,在有些情况下,为确保系统的安全性,当所申请的资源数量低于某一下限值时,还必须进行管制,不予以分配。因此,当进程申请某类临界资源时,在每次分配之前,都必须测试资源的数量,判断是否大于可分配的下限值,决定是否予以分配。
  • 76. 2.4.4 信号量的应用   1. 利用信号量实现进程互斥   为使多个进程能互斥地访问某临界资源,只需为该资源设置一互斥信号量mutex,并设其初始值为1,然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。
  • 77. 利用信号量实现互斥的说明: 为临界资源设置一个互斥信号量mutex,其初值为1 在每个进程中将临界区代码置于Wait(mutex)和Signal(mutex)原语之间 必须成对使用Wait和Signal原语:遗漏Wait原语则不能保证互斥访问,遗漏Signal原语则不能在使用临界资源之后将其释放(给其他等待的进程) Wait、Signal原语不能次序错误、重复或遗漏
  • 78.   2. 利用信号量实现前趋关系   还可利用信号量来描述程序或语句之间的前趋关系。 设有两个并发执行的进程P1和P2。P1中有语句S1;P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系,只需使进程P1和P2共享一个公用信号量S,并赋予其初值为0,将signal(S)操作放在语句S1后面,而在S2语句前面插入wait(S)操作,即   在进程P1中,用S1;signal(S);   在进程P2中,用wait(S);S2;
  • 79.   由于S被初始化为0,这样,若P2先执行必定阻塞,只有在进程P1执行完S1; signal(S);操作后使S增为1时,P2进程方能成功执行语句S2。同样,我们可以利用信号量按照语句间的前趋关系(见图2-14),写出一个更为复杂的可并发执行的程序。
  • 80. 【问题】设在公共汽车上,司机和售票员的活动分别是:司机:启动车辆,正常行车,到站停车。售票员:上乘客,关车门,售票,开车门,下乘客。用PV操作对其控制。【例子】司机-售票员问题
  • 81. 用信号量实现司机和售票员的同步司 机售票员正常行驶到站停车开 车售 票开车门关车门
  • 82. 【第一步】确定进程间的关系。司机到站停车后,售票员方可工作。同样,售票员关车门后,司机才能工作。所以司机与售票员之间是一种同步关系。 【第二步】确定信号量及其值。由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断司机能否进行工作,初值为0。售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0 . 【第三步】 确定P、V操作的位置。 司机操作中,是否关门?没关则等待,这是一个P操作,P(run); 司机操作中,设立停车标志,这是一个V操作,V(stop); 售票员操作中,是否停车?没停则等待,这是一个P操作,P(stop); 售票员操作中,设立关门标志,这是一个V 操作,V(run) ·
  • 83. 设run、stop分别为司机和售票员的私用信号量,初值均为0, run用于司机开车的信号量, stop用于售票员开门的信号量。司机: Repeat 正常行车; 到站停车; signal(stop); wait(run); 离站开车; Until false;售票员: Repeat 售票; wait(stop); 开车门; 乘客上下车; 关车门; signal(run); Until false;假设汽车正在行进中:
  • 84. 步骤: 信号量的设置; 给信号量赋初值(常用的互斥和同步信号量值的大小); P、V操作安排的位置(其中,P的顺序不能颠倒,V的顺序任意) 注意区分1)公用信号量,互斥时使用的信号量(二元信号量):它仅允许取值为“0”与“1”,用作互斥。它联系着一组共行进程,初值为1,每个进程均可对之施加P、V操作。 2)私用信号量:一般信号量(资源信号量):它联系着一组共行进程,但其初值为0,或为某个正整数n,表示资源的数目,主要用于进程同步。只允许拥有它的进程对之施加P操作。
  • 85. 2.4.5 管程机制   1.管程的定义   系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性,即用少量信息和对该资源所执行的操作来表征该资源,而忽略它们的内部结构和实现细节。
  • 86.   由上述的定义可知,管程由四部分组成:① 管程的名称;② 局部于管程的共享数据结构说明;③ 对该数据结构进行操作的一组过程;④ 对局部于管程的共享数据设置初始值的语句。图2-15是一个管程的示意图。
  • 87. 图2-15 管程的示意图
  • 88.   2. 条件变量   在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时,管程便调用wait原语使该进程等待,并将其排在等待队列上,如图2-13所示。仅当另一进程访问完成并释放该资源之后,管程才又调用signal原语,唤醒等待队列中的队首进程。
  • 89. 2.5 经典进程同步问题 2.5.1 生产者—消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者—写者问题
  • 90. 2.5.1 生产者—消费者问题问题描述 通过一个有界缓冲区可以把一群生产者P1,P2…,Pm,和一群消费者Q1,Q2,…,Qn联系起来。如下图 只要缓冲区未满,生产者就可以把产品送入缓冲区; 只要缓冲区未空,消费者就可以从缓冲区中取走物品。
  • 91. (本页无文本内容)
  • 92. 环形缓冲池
  • 93. 问题分析(利用记录型信号量解答) 为解决生产者消费者问题,应该设两个同步信号量,一个说明空缓冲区的数目,用Empty表示,初值为有界缓冲区的大小N,另一个说明已用缓冲区的数目,用Full表示,初值为0。 由于在此问题中有M个生产者和N个消费者,它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源,必须互斥使用,所以,另外还需要设置一个互斥信号量Mutex,其初值为1。
  • 94. Q: j = 0; while (1) { P(Full); P(Mutex); 从Buffer[j]取产品; j = (j+1) % n; V(Mutex); V(Empty); 消费产品; };P: i = 0; while (1) { 生产产品; P(Empty); P(Mutex); 往Buffer [i]放产品; i = (i+1) % n; V(Mutex); V(Full); };
  • 95. 【思考题】P(Empty)和P(Mutex)能否互换 答:不能! 解释:若缓冲区满,消费者进程没有在临界区中,而生产者:先执行P(Mutex),获得临界区访问权,再执行P(Empty)则被阻塞。此时,若消费者想进入临界区,取产品。由于P(Mutex)也被阻塞,生产者由于没有空缓冲,而被阻塞,消费者由于没有临界区的访问,又无法执行取数而释放空缓冲的操作,生产者,消费者就等待。
  • 96. 【思考题】如果生产者消费者问题中的缓冲区是无界的,又该如何解呢?Q: j = 0; while (1) { P(S1); P(mutex); 从Buffer[j]取产品; j = (j+1) % n; V(mutex); 消费产品; };P: i = 0; while (1) { 生产产品; P(mutex); 往Buffer [i]放产品; i = (i+1) % n; V(mutex); V(S1); };
  • 97. P.V操作讨论 P.V操作必须成对出现,有一个P操作就一定有一个V操作。 当为互斥操作时,它们同处于同一进程;当为同步操作时,则不在同一进程中出现。 如果P(S1)和P(S2)两个操作在一起,那么P操作的顺序至关重要:一个同步P操作与一个互斥P操作在一起时,同步P操作在互斥P操作前。 两个V操作无关紧要
  • 98. 利用AND信号量解答Q: j = 0; while (1) { Swait(S2,mutex); 从Buffer[j]取产品; j = (j+1) % n; Ssignal(mutex,S1); 消费产品; };P: i = 0; while (1) { 生产产品; Swait(S1,mutex); 往Buffer [i]放产品; i = (i+1) % n; Ssignal(mutex,S2); };
  • 99. 2.5.2 哲学家进餐问题思考思考思考思考思考进餐准备进餐进餐问题描述 五位哲学家围桌而坐 哲学家在思考问题时不需要任何资源,思考完问题后进入进餐态。 每人必须获得左右两支筷子才能进餐准备进餐
  • 100. 1. 利用记录型信号量解决哲学家进餐问题 放在桌子上的筷子是临界资源,在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用,用一个信号量表示一只筷子,五个信号量构成信号量数组。 Var chopstick: array [0, -, 4] of semaphore; 所有信号量均被初始化为1。
  • 101. 第i 位哲学家的活动可描述为: repeat wait(chopstick[ i ]); wait(chopstick[ ( i +1) mod 5] ); … eat; … signal(chopstick[ i ]); signal(chopstick[ ( i +1) mod 5] ); … think; until false;当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子。当哲学家进餐毕,先放下左边的筷子,再放下右边的筷子。
  • 102. 死锁思考思考思考思考思考准备进餐准备进餐准备进餐准备进餐准备进餐思考Wait(left_stick)Wait(right_stick)Signal(left_stick)eatSignal(right_stick)【问题分析】
  • 103. 解决方法: 至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕后释放出他用过的两只筷子,从而使更多的哲学家能够进餐。---限制并发执行的进程数 仅当哲学家的左右两只筷子均可用时,才允许他拿起筷子进餐。---采用信号量集 规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;偶数号哲学家则相反。---保证总会有一个哲学家能同时获得两只筷子而进餐23154方法312345
  • 104. 2.利用AND信号量解决哲学家进餐问题 在哲学家进餐问题中,要求每个哲学家先获得两个临界资源(筷子)后方能进餐。本质上是AND同步问题。 Var chopstick: array [0, …,4] of semaphore:=(1, 1, 1, 1, 1); Process i repeat think; Swait(chopstick[ ( i +1) mod 5] , chopstick[ i ] ); eat; Ssignal(chopstick[ ( i +1) mod 5] , chopstick[ i ] ); until false;
  • 105. 关于信号量的进一步说明记录型信号量可以用于两个进程,也可以用于多个进程,既可以用于互斥,也可以用于同步。当互斥与同步共存时,一般来说,用于互斥的信号量上的Wait操作总是在后执行。 如果用于互斥,常称为互斥(或公用)信号量,其初值为1。对于互斥信号量,每一进程均可对其进行Wait、Signal操作。 如果用于同步,多采用私用信号量,也称为资源信号量,其初值视资源数而定。它联系一组并发进程,只允许拥有它的进程对其实施Wait操作。
  • 106. 2.5.3 读者—写者问题一个数据文件或记录可被多个进程共享。 只要求读文件的进程称为“Reader进程”,其它进程则称为“Writer进程”。 允许多个进程同时读一个共享对象,但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。 “读者——写者问题”是保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。
  • 107. 1. 利用记录型信号量解决读者—写者问题 。 为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。设置整型变量Readcount表示正在读的进程数目。 由于只要有一个Reader进程在读,便不允许Writer进程去写。因此,仅当Readcount=0,表示尚无Reader进程在读时,Reader才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功,Reader进程便可去读,相应地,做Readcount+1操作。
  • 108. 1. 利用记录型信号量解决读者—写者问题 。 同理,仅当Reader进程在执行了Readcount减1操作后其值为0时,才需执行signal(Wmutex)操作,以便让Writer进程写。 因为Readcount是一个可被多个Reader进程访问的临界资源,因此应为它设置一个互斥信号量rmutex。
  • 109. var rmutex, wmutex: semaphore: =1,1; readcount:integer: =0; begin parbegin reader: begin repeat wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); … perform read operation设置它主要是为了改写readcount的值。
  • 110. perform read operation … wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end
  • 111. writer: begin repeat wait(wmutex) perform write operation; signal(wmutex) until false; end parend end
  • 112. 2.利用信号量集机制解决读者—写者问题 。 增加一个限制:最多只允许RN个读者同时读。 因此,引入信号量L,并赋予其初值RN,通过执行wait(L, 1, 1)操作,来控制读者的数目。每当有一个读者进入时,就要先执行wait(L, 1, 1)操作,使L的值减1。当有RN个读者进入读后,L便减为0,第RN +1个读者要进入读时,必然会因wait(L, 1, 1)操作失败而阻塞。
  • 113. Var RN integer; L, mx: semaphore :=RN, 1; begin parbegin reader : begin repeat Swait(L, 1, 1); Swait(mx, 1, 0); … perform read operation; … Ssignal(L, 1); until false; end writer : begin repeat Swait(mx, 1, 1; L, RN, 0); perform write operation; Ssignal(mx, 1); until false; end parend end
  • 114. 【思考题1】一个简化的异地售票程序,假设几乎同时两地有两个乘客要购买同一班次的车票各一张,两个终端售票程序都要访问存放该次车票的数据单元Pk,假设它们都要对Pk做如下的访问操作: “若Pk≥1 ,则将Pk的值减1,卖出一张票,返回, 否则打印‘无票’信息,返回” 如果不加任何限制让这两个程序并发执行的话 ,结果可能会导致错误,甚至两地各卖出一张重票的现象
  • 115. 1、试用P、V操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。 主要步骤是: (1)分析清楚题目涉及的进程间的制约关系。 (2)设置信号量(包括信号量的个数和初值, 对于同步问题还要写出信号量的物理含义)。 (3)给出进程相应程序的算法描述或流程控制,并把P、V操作加到程序的适当处。
  • 116. 北京售票终端进程: ①根据顾客订票要求找到公共数据单元PK; ②P(S); ③把PK的值读到工作寄存器R1中; ④根据顾客订票数修改R1; ⑤将R1的值回写到PK中; ⑥V(S); ⑦售出顾客所订的票,返回;
  • 117. 天津售票终端进程: ①根据顾客订票要求找到公共数据单元PK; ②P(S); ③把PK的值读到工作寄存器R2中; ④根据顾客订票数修改R2; ⑤将R1的值回写到PK中; ⑥V(S); ⑦售出顾客所订的票,返回;
  • 118. 【思考题2】桌上有一空盘,最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子,儿子专等吃盘中的桔子,女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示:设置一个信号量表示可否向盘中放水果,一个信号量表示可否取桔子,一个信号量表示可否取苹果。
  • 119. 解 设置三个信号量S,So,Sa ,初值分别为1,0,0。分别表示可否向盘中放水果,可否取桔子,可否取苹果。Father() { while(1) { p(S); 将水果放入盘中; if(是桔子)v(So); else v(Sa); } }Son() { while(1) { p(So) 取桔子 v(S); 吃桔子; } }Daughter() { while(1) { p(Sa) 取苹果 v(S); 吃苹果; } }
  • 120. 【思考题3】有一阅览室,读者进入时必须先在一张登记表上进行登记,该表为每一座位列一表目,包括座号和读者姓名。读者离开时要消掉登记信号,阅览室中共有100个座位,请用P, V操作写出这些进程间的同步算法。
  • 121. begin S1:=100 (有100个座位) S2:=0 (有没阅读者) mutex: =1 cobegin P1: repeat P(S1); P(mutex); 登记信息; V(muetx); V(S2) 就座,阅读; until false coend endP2: repeat P(S2) P(mutex); 消掉信息; V(muetx); V(S1); 离开阅览室; until false
  • 122. 【思考题4】理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子: 如果没有顾客,理发师便在理发椅上睡觉。 一个顾客到来时,它必须叫醒理发师 如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,就坐下来等待,否则就离开。
  • 123. var waiting : integer; /*等候理发的顾客数*/ CHAIRS:integer; /*为顾客准备的椅子数*/ customers, barbers,mutex : semaphore; customers := 0; barbers := 0; waiting := 0; mutex := 1; Procedure barber; begin while(TRUE); /*理完一人,还有顾客吗?*/ P(cutomers); /*若无顾客,理发师睡眠*/ P(mutex); /*进程互斥*/ waiting := waiting – 1; /*等候顾客数少一个*/ V(barbers); /*理发师去为一个顾客理发*/ V(mutex); /*开放临界区*/ cut-hair( ); /*正在理发*/ end;
  • 124. procedure customer Begin P(mutex); /*进程互斥*/ if waiting
  • 125. 【思考题5】某小型超级市场,可容纳50人同时购物。入口处有篮子,每个购物者可拿一只篮子入内购物。出口处结帐,并归还篮子(出、入口禁止多人同时通过)。试用信号量和P、V操作写出购物者的同步算法。 这是个典型的进程互斥问题
  • 126. 解答: ①所用信号量设置如下: Ⅰ)互斥信号量S,初值为50,用以保证最多可以有50个购物者同时进入超市。 Ⅱ)互斥信号量mutex,初值为1,用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。
  • 127. 购物者i进程 P(S); P(mutex); 从入口处进超市,并取一只篮子; 进超市内选购商品; 到出口结帐,并归还篮子; V(mutex); 从出口离开超市; V(S); ↓ 结 束.
  • 128. 【练习】a,b 两点间是一段东西向的单行车道,现要设计一个自动管理系统,管理规则如下:当ab间有车辆在行驶时同方向的车可以同时驶入ab段,但另一方向的车必须在ab段外等待;当ab之间无车时,到达a(或b)的车辆可以进入ab段,但不能从a,b点同时驶入;当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时,应让另一方向等待的车辆进入ab段行驶。请用wait,signal工具对ab段实现正确管理
  • 129. 答:Semaphore s, mutexab,mutexba Pab: Wait(mutexab) Countab++ If countab=1 then wait(s); Signal(mutexab) ….. wait(mutexab) countab- -; if countab=0 then signal(s) signal(mutexab);
  • 130. Pba: wait(mutexba) countba=countba+1; If countba=1 then wait(s) wait(mutexba) enter; …… wait(mutexba) countba--; if countba=0 then signal(s) signal(mutexba);
  • 131.      2.6 进 程 通 信   进程通信是指进程之间的信息交换。由于进程的互斥与同步,需要在进程间交换一定的信息,故不少学者将它们也归为进程通信,但只能把它们称为低级进程通信。我们以信号量机制为例来说明,它们之所以低级的原因在于:① 效率低,生产者每次只能向缓冲池投放一个产品(消息),消费者每次只能从缓冲区中取得一个消息;② 通信对用户不透明,OS只为进程之间的通信提供了共享存储器。
  • 132.   在进程之间要传送大量数据时,应当利用OS提供的高级通信工具,该工具最主要的特点是:   (1) 使用方便。OS隐藏了实现进程通信的具体细节,向用户提供了一组用于实现高级通信的命令(原语),用户可方便地直接利用它实现进程之间的通信。或者说,通信过程对用户是透明的。这样就大大减少了通信程序编制上的复杂性。   (2) 高效地传送大量数据。用户可直接利用高级通信命令(原语)高效地传送大量的数据。
  • 133. 2.6.1 进程通信的类型   1. 共享存储器系统(Shared-Memory System)   在共享存储器系统中,相互通信的进程共享某些数据结构或共享存储区,进程之间能够通过这些空间进行通信。据此,又可把它们分成以下两种类型:   (1) 基于共享数据结构的通信方式。   (2) 基于共享存储区的通信方式。
  • 134.   2. 管道(pipe)通信系统   所谓“管道”,是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件,又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道;而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的,故又称为管道通信。这种方式首创于UNIX系统,由于它能有效地传送大量数据,因而又被引入到许多其它操作系统中。
  • 135.   为了协调双方的通信,管道机制必须提供以下三方面的协调能力:① 互斥,即当一个进程正在对pipe执行读/写操作时,其它(另一)进程必须等待。② 同步,指当写(输入)进程把一定数量(如4 KB)的数据写入pipe,便去睡眠等待,直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe时,也应睡眠等待,直至写进程将数据写入管道后才将之唤醒。③ 确定对方是否存在,只有确定了对方已存在时才能进行通信。
  • 136.   3. 消息传递系统(Message passing system)   在该机制中,进程不必借助任何共享存储区或数据结构,而是以格式化的消息 (message)为单位,将通信的数据封装在消息中,并利用操作系统提供的一组通信命令(原语),在进程间进行消息传递,完成进程间的数据交换。   基于消息传递系统的通信方式属于高级通信方式,因其实现方式的不同,可进一步分成两类:   (1) 直接通信方式   (2) 间接通信方式
  • 137.   4. 客户机-服务器系统(Client-Server system)   1) 套接字(Socket)   套接字起源于20世纪70年代加州大学伯克利分校版本的UNIX(即BSD Unix),是UNIX 操作系统下的网络通信接口。一开始,套接字被设计用在同一台主机上多个应用程序之间的通信(即进程间的通信),主要是为了解决多对进程同时通信时端口和物理线路的多路复用问题。随着计算机网络技术的发展以及UNIX 操作系统的广泛使用,套接字已逐渐成为最流行的网络通信程序接口之一。
  • 138.   2) 远程过程调用和远程方法调用   远程过程(函数)调用RPC(Remote Procedure Call),是一个通信协议,用于通过网络连接的系统。该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程,而对程序员表现为常规的过程调用,无需额外地为此编程。如果涉及的软件采用面向对象编程,那么远程过程调用亦可称做远程方法调用。
  • 139.   实际上,远程过程调用的主要步骤是:   (1) 本地过程调用者以一般方式调用远程过程在本地关联的客户存根,传递相应的参数,然后将控制权转移给客户存根;   (2) 客户存根执行,完成包括过程名和调用参数等信息的消息建立,将控制权转移给本地客户进程;   (3) 本地客户进程完成与服务器的消息传递,将消息发送到远程服务器进程;   (4) 远程服务器进程接收消息后转入执行,并根据其中的远程过程名找到对应的服务器存根,将消息转给该存根;
  • 140.   (5) 该服务器存根接到消息后,由阻塞状态转入执行状态,拆开消息从中取出过程调用的参数,然后以一般方式调用服务器上关联的过程;   (6) 在服务器端的远程过程运行完毕后,将结果返回给与之关联的服务器存根;   (7) 该服务器存根获得控制权运行,将结果打包为消息,并将控制权转移给远程服务器进程;   (8) 远程服务器进程将消息发送回客户端;   (9) 本地客户进程接收到消息后,根据其中的过程名将消息存入关联的客户存根,再将控制权转移给客户存根;   (10) 客户存根从消息中取出结果,返回给本地调用者进程,并完成控制权的转移。
  • 141. 2.6.2 消息传递通信的实现方式   1. 直接消息传递系统   在直接消息传递系统中采用直接通信方式,即发送进程利用OS所提供的发送命令(原语),直接把消息发送给目标进程。
  • 142.   1) 直接通信原语   (1) 对称寻址方式。   (2) 非对称寻址方式。
  • 143.   2) 消息的格式   在消息传递系统中所传递的消息,必须具有一定的消息格式。在单机系统环境中,由于发送进程和接收进程处于同一台机器中,有着相同的环境,所以消息的格式比较简单,可采用比较短的定长消息格式,以减少对消息的处理和存储开销。该方式可用于办公自动化系统中,为用户提供快速的便笺式通信。但这种方式对于需要发送较长消息的用户是不方便的。为此,可采用变长的消息格式,即进程所发送消息的长度是可变的。对于变长消息,系统无论在处理方面还是存储方面,都可能会付出更多的开销,但其优点在于方便了用户。
  • 144.   3) 进程的同步方式   在进程之间进行通信时,同样需要有进程同步机制,以使诸进程间能协调通信。不论是发送进程还是接收进程,在完成消息的发送或接收后,都存在两种可能性,即进程或者继续发送(或接收)或者阻塞。
  • 145.   4) 通信链路   为使在发送进程和接收进程之间能进行通信,必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是:由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路,在链路使用完后拆除链路。
  • 146.   2. 信箱通信   1) 信箱的结构   信箱定义为一种数据结构。在逻辑上,可以将其分为两个部分:   (1) 信箱头   (2) 信箱体
  • 147. 图2-16 双向信箱示意图
  • 148.   2) 信箱通信原语   系统为邮箱通信提供了若干条原语,分别用于:   (1) 邮箱的创建和撤消。   (2) 消息的发送和接收。
  • 149.   3) 信箱的类型   邮箱可由操作系统创建,也可由用户进程创建,创建者是邮箱的拥有者。据此,可把邮箱分为以下三类:   (1) 私用邮箱。   (2) 公用邮箱。   (3) 共享邮箱。
  • 150. 2.6.3 直接消息传递系统实例   消息缓冲队列通信机制首先由美国的Hansan提出,并在RC 4000系统上实现,后来被广泛应用于本地进程之间的通信中。在这种通信机制中,发送进程利用Send原语将消息直接发送给接收进程;接收进程则利用Receive原语接收消息。
  • 151.   1. 消息缓冲队列通信机制中的数据结构   (1) 消息缓冲区。   (2) PCB中有关通信的数据项。
  • 152.   2. 发送原语   发送进程在利用发送原语发送消息之前,应先在自己的内存空间设置一发送区a,如图2-17所示,把待发送的消息正文、发送进程标识符、消息长度等信息填入其中,然后调用发送原语,把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i,接着,把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上,应先获得接收进程的内部标识符j,然后将i挂在j.mq上。由于该队列属于临界资源,故在执行insert操作的前后都要执行wait和signal操作。
  • 153. 图2-17 消息缓冲通信
  • 154.   3. 接收原语   接收进程调用接收原语receive(b),从自己的消息缓冲队列mq中摘下第一个消息缓冲区i,并将其中的数据复制到以b为首址的指定消息接收区内。
  • 155.     2.7 线程(Threads)的基本概念 2.7.1 线程的引入   如果说,在OS中引入进程的目的是为了使多个程序能并发执行,以提高资源利用率和系统吞吐量,那么,在操作系统中再引入线程,则是为了减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。
  • 156.   1. 进程的两个基本属性   首先让我们来回顾进程的两个基本属性:   ① 进程是一个可拥有资源的独立单位,一个进程要能独立运行,它必须拥有一定的资源,包括用于存放程序正文、数据的磁盘和内存地址空间,以及它在运行时所需要的I/O设备、已打开的文件、信号量等;
  • 157.   ② 进程同时又是一个可独立调度和分派的基本单位,一个进程要能独立运行,它还必须是一个可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB,系统可根据其PCB感知进程的存在,也可以根据其PCB中的信息,对进程进行调度,还可将断点信息保存在其PCB中。反之,再利用进程PCB中的信息来恢复进程运行的现场。正是由于进程有这两个基本属性,才使进程成为一个能独立运行的基本单位,从而也就构成了进程并发执行的基础。
  • 158.   2. 程序并发执行所需付出的时空开销   为使程序能并发执行,系统必须进行以下的一系列操作:   (1) 创建进程,系统在创建一个进程时,必须为它分配其所必需的、除处理机以外的所有资源,如内存空间、I/O设备,以及建立相应的PCB;   (2) 撤消进程,系统在撤消进程时,又必须先对其所占有的资源执行回收操作,然后再撤消PCB;   (3) 进程切换,对进程进行上下文切换时,需要保留当前进程的CPU环境,设置新选中进程的CPU环境,因而须花费不少的处理机时间。
  • 159.   3. 线程——作为调度和分派的基本单位   如何能使多个程序更好地并发执行,同时又尽量减少系统的开销,已成为近年来设计操作系统时所追求的重要目标。有不少研究操作系统的学者们想到,要设法将进程的上述两个属性分开,由OS分开处理,亦即并不把作为调度和分派的基本单位也同时作为拥有资源的单位,以做到“轻装上阵”;而对于拥有资源的基本单位,又不对之施以频繁的切换。正是在这种思想的指导下,形成了线程的概念。
  • 160. 2.7.2 线程与进程的比较   1. 调度的基本单位   2. 并发性   3. 拥有资源   4. 独立性   5. 系统开销   6. 支持多处理机系统
  • 161. 2.7.3 线程的状态和线程控制块   1. 线程运行的三个状态   与传统的进程一样,在各线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地,线程在运行时也具有下述三种基本状态:   (1) 执行状态,表示线程已获得处理机而正在运行;   (2) 就绪状态,指线程已具备了各种执行条件,只须再获得CPU便可立即执行;   (3) 阻塞状态,指线程在执行中因某事件受阻而处于暂停状态,例如,当一个线程执行从键盘读入数据的系统调用时,该线程就被阻塞。
  • 162.   2. 线程控制块TCB   如同每个进程有一个进程控制块一样,系统也为每个线程配置了一个线程控制块TCB,将所有用于控制和管理线程的信息记录在线程控制块中。
  • 163.   3. 多线程OS中的进程属性   通常在多线程OS中的进程都包含了多个线程,并为它们提供资源。OS支持在一个进程中的多个线程能并发执行,但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性:   (1) 进程是一个可拥有资源的基本单位。   (2) 多个线程可并发执行。   (3) 进程已不是可执行的实体。
  • 164.      2.8 线 程 的 实 现 2.8.1 线程的实现方式   线程已在许多系统中实现,但各系统的实现方式并不完全相同。在有的系统中,特别是一些数据库管理系统,如infomix所实现的是用户级线程; 而另一些系统(如Macintosh和OS/2操作系统)所实现的是内核支持线程;还有一些系统如Solaris操作系统,则同时实现了这两种类型的线程。
  • 165.   1. 内核支持线程KST(Kernel Supported Threads)   在OS中的所有进程,无论是系统进程还是用户进程,都是在操作系统内核的支持下运行的,是与内核紧密相关的。而内核支持线程KST同样也是在内核的支持下运行的,它们的创建、阻塞、撤消和切换等,也都是在内核空间实现的。为了对内核线程进行控制和管理,在内核空间也为每一个内核线程设置了一个线程控制块,内核根据该控制块而感知某线程的存在,并对其加以控制。当前大多数OS都支持内核支持线程。
  • 166.   这种线程实现方式主要有四个主要优点:   (1) 在多处理器系统中,内核能够同时调度同一进程中的多个线程并行执行;   (2) 如果进程中的一个线程被阻塞了,内核可以调度该进程中的其它线程占有处理器运行,也可以运行其它进程中的线程;   (3) 内核支持线程具有很小的数据结构和堆栈,线程的切换比较快,切换开销小;   (4) 内核本身也可以采用多线程技术,可以提高系统的执行速度和效率。
  • 167.   2. 用户级线程ULT(User Level Threads)   用户级线程是在用户空间中实现的。对线程的创建、 撤消、同步与通信等功能,都无需内核的支持,即用户级线程是与内核无关的。在一个系统中的用户级线程的数目可以达到数百个至数千个。由于这些线程的任务控制块都是设置在用户空间,而线程所执行的操作也无需内核的帮助,因而内核完全不知道用户级线程的存在。
  • 168.   使用用户级线程方式有许多优点:   (1) 线程切换不需要转换到内核空间。   (2) 调度算法可以是进程专用的。   (3) 用户级线程的实现与OS平台无关,因为对于线程管理的代码是属于用户程序的一部分,所有的应用程序都可以对之进行共享。
  • 169.   而用户级线程方式的主要缺点则在于:   (1) 系统调用的阻塞问题。在基于进程机制的OS中,大多数系统调用将使进程阻塞,因此,当线程执行一个系统调用时,不仅该线程被阻塞,而且,进程内的所有线程会被阻塞。而在内核支持线程方式中,则进程中的其它线程仍然可以运行。   (2) 在单纯的用户级线程实现方式中,多线程应用不能利用多处理机进行多重处理的优点,内核每次分配给一个进程的仅有一个CPU,因此,进程中仅有一个线程能执行,在该线程放弃CPU之前,其它线程只能等待。
  • 170.   3. 组合方式   有些OS把用户级线程和内核支持线程两种方式进行组合,提供了组合方式ULT/KST 线程。在组合方式线程系统中,内核支持多个内核支持线程的建立、调度和管理,同时,也允许用户应用程序建立、调度和管理用户级线程。
  • 171. 图2-18 多线程模型
  • 172. 2.8.2 线程的实现   1. 内核支持线程的实现   在仅设置了内核支持线程的OS中,一种可能的线程控制方法是,系统在创建一个新进程时,便为它分配一个任务数据区PTDA(Per Task Data Area),其中包括若干个线程控制块TCB空间,如图2-19所示。
  • 173. 图2-19 任务数据区空间
  • 174.   2. 用户级线程的实现   1) 运行时系统(Runtime System)   所谓“运行时系统”,实质上是用于管理和控制线程的函数(过程)的集合,其中包括用于创建和撤消线程的函数、线程同步和通信的函数,以及实现线程调度的函数等。正因为有这些函数,才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间,并作为用户级线程与内核之间的接口。
  • 175.   2) 内核控制线程   这种线程又称为轻型进程LWP(Light Weight Process)。每一个进程都可拥有多个LWP,同用户级线程一样,每个LWP都有自己的数据结构(如TCB),其中包括线程标识符、优先级、状态,另外还有栈和局部存储区等。LWP也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务,这样,当一个用户级线程运行时,只须将它连接到一个LWP上,此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。
  • 176. 图2-20 利用轻型进程作为中间系统
  • 177. 2.8.3 线程的创建和终止   1. 线程的创建   应用程序在启动时,通常仅有一个线程在执行,人们把线程称为“初始化线程”,它的主要功能是用于创建新线程。在创建新线程时,需要利用一个线程创建函数(或系统调用),并提供相应的参数,如指向线程主程序的入口指针、堆栈的大小,以及用于调度的优先级等。在线程的创建函数执行完后,将返回一个线程标识符供以后使用。
  • 178.   2. 线程的终止   当一个线程完成了自己的任务(工作)后,或是线程在运行中出现异常情况而须被强行终止时,由终止线程通过调用相应的函数(或系统调用)对它执行终止操作。但有些线程(主要是系统线程),它们一旦被建立起来之后,便一直运行下去而不被终止。在大多数的OS中,线程被中止后并不立即释放它所占有的资源,只有当进程中的其它线程执行了分离函数后,被终止的线程才与资源分离,此时的资源才能被其它线程利用。
  • 179.       习 题    1. 什么是前趋图? 为什么要引入前趋图?   2. 试画出下面四条语句的前趋图:     S1: a = x+y;     S2: b = z+1;     S3: c = a-b;     S4: w = c+1;   3. 为什么程序并发执行会产生间断性特征?   4. 程序并发执行时为什么会失去封闭性和可再现性?
  • 180.   5. 在操作系统中为什么要引入进程的概念? 它会产生什么样的影响?   6. 试从动态性、并发性和独立性上比较进程和程序。   7. 试说明PCB的作用具体表现在哪几个方面,为什么说PCB是进程存在的唯一标志?   8.  PCB提供了进程管理和进程调度所需要的哪些信息?   9. 进程控制块的组织方式有哪几种?   10. 何谓操作系统内核? 内核的主要功能是什么?   11. 试说明进程在三个基本状态之间转换的典型原因。   12. 为什么要引入挂起状态? 该状态有哪些性质?
  • 181.   13. 在进行进程切换时,所要保存的处理机状态信息有哪些?   14. 试说明引起进程创建的主要事件。   15. 试说明引起进程被撤消的主要事件。   16. 在创建一个进程时所要完成的主要工作是什么?   17. 在撤消一个进程时所要完成的主要工作是什么?   18. 试说明引起进程阻塞或被唤醒的主要事件是什么?   19. 为什么要在OS中引入线程?   20. 试说明线程具有哪些属性?
  • 182.   21. 试从调度性、并发性、拥有资源及系统开销方面对进程和线程进行比较。   22. 线程控制块TCB中包含了哪些内容?   23. 何谓用户级线程和内核支持线程?   24. 试说明用户级线程的实现方法。   25. 试说明内核支持线程的实现方法。   26. 多线程模型有哪几种类型? 多对一模型有何优缺点?
  • 183. 【本章基础要点】进程的并发执行是指若干个进程在执行时间上是重叠的。 进程是一个程序对某个数据集的一次运行活动。 并发进程在访问共享变量时,可能会出现与时间有关的错误。 程序并发执行与顺序执行相比产生了一些新特征,分别是:间断性、失去封闭性、不可再现 前趋图展示了语句间的一种执行顺序关系,而进程图展示的是进程之间的家族关系。 进程的基本特征是: 动态性、并发性、独立性、异步性、结构性 程序的顺序执行通常是在单道程序的工作环境中,具有运行结果可再现的特点。
  • 184. 进程的基本状态有: 执行、就绪、阻塞 进程是动态的概念,而程序是静态的概念。 进程控制块是进程存在的唯一标志。 在进程管理中,当进程等待某一事件时,将从执行状态变为阻塞状态。 当进程执行的时间片用完时,进程从: 执行状态变为就绪状态 分配到必要资源并获得处理机时的进程状态是: 执行状态。 进程从结构上讲,包括: 程序段、数据段、进程控制块。
  • 185. 在一个单处理机中,若有4个用户进程且假定当前时刻有一个进程处于执行状态,则处于就绪状态的进程最多有: 3个,最少有0个。 在操作系统中,不可中断的操作称为: 原语。 进程控制就是对系统中的进程实施有效的管理,通过使用进程创建、进程撤消、进程阻塞、进程唤醒等控制原语实现。 在操作系统中引入线程概念的主要目的是: 减少程序并发执行时所需付出的时空开销,提高程序执行的并发程度。 线程是进程内一个相对独立的、可调度的执行单元。 线程是系统进行调度的基本单位。
  • 186. 进程间的同步是指进程间在逻辑上的相互制约关系。 在进程中访问临界资源的代码称为临界区。为保证进程互斥访问临界资源,应在进程的临界区前设置进入区,在临界区后设置退出区。 进程间的相互制约关系有直接制约关系和间接制约关系。 临界区是一段程序。 并发进程之间的基本关系是合作或共享资源,其中共享资源是指进程之间的一种间接关系。 访问临界资源应遵循的准则是:空闲让进、忙则等待、有限等待、让权等待。 如果信号量的当前值为-4,则表示 系统中在该信号量上有4个等待进程。
  • 187. 用Wait、Signal原语管理临界区时: 信号量的初值应定义为1。 在操作系统中,Wait、Signal原语是一种低级进程通信原语。 除初值外,信号量的值只能通过Wait、Signal操作来改变。 对于两个并发进程,设互斥信号量为 mutex ,若mutex=0 则表示:有一个进程进入临界区。 用Wait、Signal操作管理临界区时,任何一个进程在进入临界区之前应调用Wait操作,退出临界区时应调用Signal操作。
  • 188. 信号量的物理意义是: 当信号量值大于0时表示可用资源的数目;当信号量值小于0时,其绝对值为在该信号量上等待的进程个数。 信箱通信是一种间接通信方式。 利用消息机制实现通信时,应有发送原语和接收原语。 进程通信是指进程之间的信息交换。