rc: -rc+ V(Sr) Read file F. if rc=0 then V(S) V(Sr) end process Writer j(j=1, 2,.., k) V (S) Parend 在这个程序中,当有进程在读而使一个请求写的进程阻塞时,如果仍有进程不断地请求读 则写进程将被长期地推迟运行。但在实际的系统中往往希望让写者优先,即当有进程在读文件 时,如果有进程请求写,那么新的读者被拒绝,待现有读者完成读操作后立即让写者运行,只有 当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量S,初值为1,用于读者与 写者或写者与写者之间的互斥;另一信号量Sn,初值为n,表示系统中最多有n个进程可同时进 行操作 var S, Sn: Semaphore: =l, n: process Reader i(i=1.2,., n) read file F Process Wri P(S) P(Sn) V(S) parend 其中 Process Reader i中的P(S),V(S)保证了当有写者要工作时,不让新的读者去
process Reader i(i=1,2,…,m) begin P(Sr); rc:=rc+1; if rc=1 then P(S)； V(Sr); Read file F; P(Sr); rc:=rc-1; if rc=O then V(S); V(Sr); end process Writer j(j=1,2,…,k) begin P(S); Write file F; V(S); end; Parend; 在这个程序中,当有进程在读而使一个请求写的进程阻塞时,如果仍有进程不断地请求读 则写进程将被长期地推迟运行。但在实际的系统中往往希望让写者优先,即当有进程在读文件 时,如果有进程请求写,那么新的读者被拒绝,待现有读者完成读操作后立即让写者运行,只有 当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量 S,初值为 1,用于读者与 写者或写者与写者之间的互斥;另一信号量Sn,初值为n,表示系统中最多有n个进程可同时进 行操作: var S,Sn:Semaphore:=1,n; Parbegin process Reader i(i=1.2,…,n) begin P(S); P(Sn); V(S); read file F; V(Sn); Process Writer j(j=1,2,…,k) begin P(S); For i=1 to n do P(Sn); Write file F; for i:=1 to n do V(Sn); V(S) end parend 其中 Process Reader i 中的 P(S),V(S)保证了当有写者要工作时,不让新的读者去
读。 Process Writer j中的第一循环语句保证让正在工作的读者完成读后再执行写,完成写 操作后由第二个循环语句恢复Sn的初值,最后的V(S)用于唤醒被阻塞的读、写进程 3.1.3管程 使用信号量来处理同步问题时,同步操作P(S)和V(S)分散在各个进程中,并遍布整个程 序。这不仅给系统的管理和程序的维护和修改带来了麻烦,两且还会因同步操作的使用不当造 成死锁。为了解决上述问题,又产生了一种新的进程同步工具一管程 1.管程的定义 管程机制提供了与信号量机制相同的表达能力,但它更容易控制。管程是由一组局部的变 量对局部变量进行操作的一组过程以及对局部变量进行初始化 的语句序列构成的一个软件模块,它可用来实现进程同步。取名为 monitor name的管程,其语 去如下 type momtor name=momtor variable declarations procedue entry P1(…) procedure entry Pn(.) begin…end; initialization code 而且,管程具有以下特点 (1)管程内的局部变量只能被局部于管程内的过程所访问:反之亦然,即局部于管程内的 过程只能访问管程内的变量。 (2)任何进程只能通过调用管程提供的过程入口进入管程 (3)任一时刻,最多只能有一个进程在管程中执行 保证进程互斥地进入管程是由编译器负责的。也就是说,管程是一种编程语言的构件,它 的实现需要得到编译器的支持。 2.条件变量 在任何时刻,最多只有一个进程在管程中执行,因此用管程很容易实现互斥,只要将需要 互斥访问的资源用数据结构来描述,并将该数据结构放入管程中便可。若要用管程来实现同步, 则在相应条件不满足时(如临界资源得不到时)必须能够将在管程内执行的进程阻塞。由于阻 塞的原因不同,为了将它们区分开,引入了局部于管程的条件变量。条件变量的定义格式 为: VarXJ: condition。对条件变量只能执行以下两种操作 (1)wait操作。如.wait用来将执行进程挂到与条件变量x相应的等待队列上 (2) signal操作。如X. signal用来唤醒与ⅹ相应的等待队列上的一个进程。值得注意的 是,若没有等待进程,则X. Signal不起任何作用 3.利用管程解决生产者一消费者问题 利用管程来解决生产者一消费者问题,首先必须为它们建立二个管程: type p c=momtor Var in, out, count: integer; Buffer: array [0, n-1] of iter notfull, notempty: condition
读。Process Writer j 中的第一循环语句保证让正在工作的读者完成读后再执行写,完成写 操作后由第二个循环语句恢复 Sn 的初值,最后的 V(S)用于唤醒被阻塞的读、写进程。 3.1.3 管程 使用信号量来处理同步问题时,同步操作 P(S)和 V(S)分散在各个进程中,并遍布整个程 序。这不仅给系统的管理和程序的维护和修改带来了麻烦,两且还会因同步操作的使用不当造 成死锁。为了解决上述问题,又产生了一种新的进程同步工具一管程。 1.管程的定义 管程机制提供了与信号量机制相同的表达能力,但它更容易控制。管程是由一组局部的变 量对局部变量进行操作的一组过程以及对局部变量进行初始化 的语句序列构成的一个软件模块,它可用来实现进程同步。取名为 monitor_name 的管程,其语 法如下: type momtor_name=momtor variable declarations; procedue entry P1(…); begin …end; ┆ procedure entry Pn(…); begin …end; begin initialization code; end 而且,管程具有以下特点: (1)管程内的局部变量只能被局部于管程内的过程所访问:反之亦然,即局部于管程内的 过程只能访问管程内的变量。 (2)任何进程只能通过调用管程提供的过程入口进入管程。 (3)任一时刻,最多只能有一个进程在管程中执行。 保证进程互斥地进入管程是由编译器负责的。也就是说,管程是一种编程语言的构件,它 的实现需要得到编译器的支持。 2.条件变量 在任何时刻,最多只有一个进程在管程中执行,因此用管程很容易实现互斥,只要将需要 互斥访问的资源用数据结构来描述,并将该数据结构放入管程中便可。若要用管程来实现同步, 则在相应条件不满足时(如临界资源得不到时)必须能够将在管程内执行的进程阻塞。由于阻 塞的原因不同,为了将它们区分开,引入了局部于管程的条件变量。条件变量的定义格式 为:VarXJ:condition。对条件变量只能执行以下两种操作: (1)wait 操作。如 X.Wait 用来将执行进程挂到与条件变量 x 相应的等待队列上。 (2)signal 操作。如 X.signal 用来唤醒与 x 相应的等待队列上的一个进程。值得注意的 是,若没有等待进程,则 X.Signal 不起任何作用。 3.利用管程解决生产者一消费者问题 利用管程来解决生产者一消费者问题,首先必须为它们建立二个管程: type p_c=momtor Var in,out,count:integer; Buffer:array[0,…,n-1] of item; notfull,notempty:condition;
procedure entry put(var product: item) if count≥ n then notfull.wait;/*等待缓冲池不全满条件成立*/ buffer[in]: =product n:=(in+1)mod count: =count+1 notempty. signal;/*缓冲池不全空条件成立*/ procedure entry get(Var product: item) begin f count≤ Othen notempty.wait;/*等待缓冲池不全空条件成立*/ product: =buffer [out] out: =(out+1)mod n count: =count-1 notfull signal;/*缓冲池不全满条件成立*/ begil count: =0 上述管程Pc中包括两个局部过程:过程put负责将产品投放到缓冲池中;过程get负责 从缓冲池中取出产品。另外,整型变量 count表示缓冲池中己存放的产品数目,条件变量 notfull、 notempty分别对应于缓冲池不全满、缓冲池不全空两个条件 而相应的生产者和消费者可描述为: producer: begin produce an item in nextp P c put (nextp) until false end consumer: begin repeat P c get(nextc) consume the item in next until false 3.1.4进程通信 进程间的信息交换称为进程通信。进程之间的互斥与同步就是一种进程间的通信方式 由于进程互斥与同步交换的信息量较少且效率较低,因此称这两种通信方式为低级通信方式, 相应地也可将P、V操作称为两条低级通信原语。所谓高级通信方式是指进程之间以较高的效 率传送大量数据的通信方式。 1.进程通信的类型 高级通信方式可分为三大类:共享存储器系统、消息传递系统以及管道通信系统
procedure entry put(Var product:item) begin if count≥n then notfull.wait; /*等待缓冲池不全满条件成立*/ buffer[in]:=product; in:=(in+1)mod n; count:=count+1; notempty.signal; /*缓冲池不全空条件成立*/ end procedure entry get(Var product:item) begin if count≤Othen notempty.wait; /*等待缓冲池不全空条件成立*/ product:=buffer[out]; out:=(out+1)mod n; count:=count-1; notfull.signal; /*缓冲池不全满条件成立*/ end begin in:=out:=0; count:=0; end 上述管程 P_c 中包括两个局部过程:过程 put 负责将产品投放到缓冲池中;过程 get 负责 从缓冲池中取出产品。另外,整型变量 count 表示缓冲池中己存放的产品数目,条件变量 notfull、notempty 分别对应于缓冲池不全满、缓冲池不全空两个条件。 而相应的生产者和消费者可描述为： producer:begin repeat produce an item in nextp; P_c.put(nextp); until false end consumer:begin repeat P_c.get(nextc); consume the item in nextc; until false end 3.1.4 进程通信 进程间的信息交换称为进程通信。进程之间的互斥与同步就是一种进程间的通信方式。 由于进程互斥与同步交换的信息量较少且效率较低,因此称这两种通信方式为低级通信方式, 相应地也可将 P、V 操作称为两条低级通信原语。所谓高级通信方式是指进程之间以较高的效 率传送大量数据的通信方式。 1.进程通信的类型 高级通信方式可分为三大类:共享存储器系统、消息传递系统以及管道通信系统
(1)共享存储器系统。高级通信中的共享存储器系统是指进程之间通过对共享存储区的读 写来交换数据。共享存储器系统的另一种方式是利用共享的数据结构来进行进程通信,但这种 方式对共享数据结构的设置及对进程间的同步都必须由程序员来处理,且只能进行少量的数 据交换,因此属于低级通信方式 (2)消息传递系统。消息传递系统中,进程间的数据交换以格式化的消息(网络中称作报 文)为单位。根据实现方式,它又可分为直接通信和间接通信两类。在直接通信方式中,源进程 可直接将消息发送给目标进程,此类操作系统通常提供send( recelver, message)和 receive( sender, message)两条通信命令(原语)供用户使用。在间接通信方式中,进程间需要 通过某种中间实体(即信箱)来进行通信,发送进程将消息投入信箱,而接收进程则从信箱中疆 取得消息,因此,它不仅能实现实时通信,还能实现非实时通信。此时,操作系统应提供若干条 原语分别用于信箱的创建、撤消和消息的发送、接收等。 (3)管道通信。所谓″管道"是指连接i两个进程的一个打开的共享文件,发送进程以字符 流的形式将大量的信息写入管道,接收进程则在需要时从管道中读出数据。为了协调双方的通 信,管道通信机制必须对发送进程和接收进程在利用管道进行通信时实施同步和互斥,并只有 在确定了对方存在时方能进行通信 3.1.5线程 1.线程的基本概念 引入线程的目的是为了减少程序在并发执行时所付出的时空开销,从而使0S具有更好的 并发性。在多线程os中,将拥有资源的基本单位与调度和分派的基本单位分开处理。此时 个进程中含有一个或多个相对独立的线程,进程只是拥有资源的基本单位,每个线程都是一 个可执行的实体,即CPU调度和分派的基本单位是线程。 线程可以利用线程标识符和一组状态参数来描述,并具有下述属性 (1)轻型实体。线程除了在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存 器值和堆栈)外,线程基本上不拥有系统的资源。 (2)独立调度和分派的基本单位。线程是能独立运行的基本单位,因而也是独立调度和分派 的基本单位,为此,线程中必须包含调度所必需的信息 (3)可并发执行。同一个进程中的多个线程,以及不同进程中的多个线程均可以并发地执 (4)共享进程资源。同一个进程中的各线程可以共享该进程所拥有的全部资源,如进程的地 址空间、己打开的文件、定时器和信号量机构等 由于线程基本不拥有资源,创建线程时不需另行分配资源,终止时也不需要进行资源的回 收,而切换时也大大减少了需保存和恢复的现场信息,因此,线程的创建、终止和切换都要比进 程迅速且开销小。另外,同一进程中的各线程可以共享该进程所占用的内存空间和已打开文件, 因此,线程间通信也非常简便和迅速 2.线程的控制 在多线程0S环境下,应用程序在启动时,0S将为它创建一个进程,同时为该进程创建第 个线程。以后在线程的运行过程中,它可根据需要利用线程创建函数(或系统调用)再去创建若 个线程。所以线程是由线程创建的,但线程间并不提供父子关系的支持 每个线程被创建后,便可与其他线程一起并发地运行。如同传统的进程一样,并发运行的 线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地, 线程在运行时,也具有执行、就绪、阻塞三种基本状态,并随着自身的运行和外界环境的变换 而不断地在三种状态之间转换 当线程完成了自己的工作后,它便可正常终止。线程的终止也可能是因为运行中出现错误
(1)共享存储器系统。高级通信中的共享存储器系统是指进程之间通过对共享存储区的读 写来交换数据。共享存储器系统的另一种方式是利用共享的数据结构来进行进程通信,但这种 方式对共享数据结构的设置及对进程间的同步都必须由程序员来处理,且只能进行少量的数 据交换,因此属于低级通信方式。 （2）消息传递系统。消息传递系统中,进程间的数据交换以格式化的消息(网络中称作报 文)为单位。根据实现方式,它又可分为直接通信和间接通信两类。在直接通信方式中,源进程 可直接将消息 发送给目 标进程, 此类操作 系统通常 提供 send(receiver,message)和 receive(sender,message)两条通信命令(原语)供用户使用。在间接通信方式中,进程间需要 通过某种中间实体(即信箱)来进行通信,发送进程将消息投入信箱,而接收进程则从信箱中疆 取得消息,因此,它不仅能实现实时通信,还能实现非实时通信。此时,操作系统应提供若干条 原语分别用于信箱的创建、撤消和消息的发送、接收等。 (3)管道通信。所谓"管道"是指连接 i 两个进程的一个打开的共享文件,发送进程以字符 流的形式将大量的信息写入管道,接收进程则在需要时从管道中读出数据。为了协调双方的通 信,管道通信机制必须对发送进程和接收进程在利用管道进行通信时实施同步和互斥,并只有 在确定了对方存在时方能进行通信。 3.1.5 线程 1.线程的基本概念 引入线程的目的是为了减少程序在并发执行时所付出的时空开销,从而使 OS 具有更好的 并发性。在多线程 os 中,将拥有资源的基本单位与调度和分派的基本单位分开处理。此时, 一个进程中含有一个或多个相对独立的线程,进程只是拥有资源的基本单位,每个线程都是一 个可执行的实体,即 CPU 调度和分派的基本单位是线程。 线程可以利用线程标识符和一组状态参数来描述,并具有下述属性: (1)轻型实体。线程除了在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存 器值和堆栈)外,线程基本上不拥有系统的资源。 (2)独立调度和分派的基本单位。线程是能独立运行的基本单位,因而也是独立调度和分派 的基本单位,为此,线程中必须包含调度所必需的信息。 (3)可并发执行。同一个进程中的多个线程,以及不同进程中的多个线程均可以并发地执 行。 (4)共享进程资源。同一个进程中的各线程可以共享该进程所拥有的全部资源,如进程的地 址空间、己打开的文件、定时器和信号量机构等。 由于线程基本不拥有资源,创建线程时不需另行分配资源,终止时也不需要进行资源的回 收,而切换时也大大减少了需保存和恢复的现场信息,因此,线程的创建、终止和切换都要比进 程迅速且开销小。另外,同一进程中的各线程可以共享该进程所占用的内存空间和已打开文件, 因此,线程间通信也非常简便和迅速。 2.线程的控制 在多线程 OS 环境下,应用程序在启动时,OS 将为它创建一个进程,同时为该进程创建第一 个线程。以后在线程的运行过程中,它可根据需要利用线程创建函数(或系统调用)再去创建若 干个线程。所以线程是由线程创建的,但线程间并不提供父子关系的支持。 每个线程被创建后,便可与其他线程一起并发地运行。如同传统的进程一样,并发运行的 线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地, 线程在运行时,也具有执行、就绪、阻塞三种基本状态,并随着自身的运行和外界环境的变换 而不断地在三种状态之间转换。 当线程完成了自己的工作后,它便可正常终止。线程的终止也可能是因为运行中出现错误
或某种其他原因而引起的,此时它是被强行终止的。可见,线程如同进程一样,具有一定的生命 周期。 3.线程的同步 在多线程os中通常提供多种同步机制,如互斥锁、条件变量、信号量机制以及多读、单 写锁等,它们可支持不同频率的交互操作和不同程度的并行性。 (1)互斥锁 互斥锁有开锁和关锁两种状态,并能进行关锁和开锁两种操作。当一个线程需要访问某个 临界资源时,线程首先应对为该资源所设置的互斥锁 mutex进行关锁操作 mutex enter:判别 mutex的状态,如果它已处于关锁状态,则试图访问该资源的线程将被阻塞;而如果mtex处于 开锁状态,则将mtex关上后便可访问该资源。在线程完成对共享资源的访问后,必须执行开 锁操作 mutex-exit:如果有线程阻塞在该互斥锁上,则唤醒其中的一个线程;而如果没有阻塞 的线程,则将互斥锁的状态置成开锁状态。为了降低线程被阻塞的频率,在有的系统中还提供 了一种不阻塞的关锁操作 mutex tryenter,当 mutex处于关锁状态时, mutex tryenter并不阻 塞线程,而只是返回一个指示操作失败的状态码。 互斥锁是一种比较简单的同步机制,而且是严格括入的( bracketing),一个线程去打开被 另一线程关闭的互斥锁将是错误的,因此它只适用于实现线程对资源的互斥访问。由于操作互 斥锁的时间和空间开销都较低,因而它较适合于高频度使用的关键共享数据和程序段。 (2)条件变量 条件变量必须和互斥锁配合起来使用,它用于等待,直到某一特定条件为真。对条件变量 的 cv walt操作将使线程阻塞,直到所等的条件信号成立后,才能由 cv signal操作将其中的 个阻塞线程唤醒。 cv wait操作在阻塞线程前将对相应的互斥锁执行开锁操作,并在返回前 重新对互斥锁进行关锁操作。条件变量可用来实现互斥或同步,它的典型使用方式为 mutex enter(&mutex) hile(some condition)( cv wait(&cv, &mutex) mutex exit(&mutex) 这里允许条件是一个复杂的表达式,因为它受互斥锁的保护。 (3)信号量机制 信号量机制也可用于多线程os中,实现诸线程或进程之间的同步。为了提高效率,可为线程和 进程分别设置相应的信号量。 当某线程利用信号量来实现同一进程中各线程之间的同步时,可调用创建信号量命令来创 建一私用信号量,其数据结构被存放在应用程序的地址空间中。私用信号量属于特定的进程所 有,0S并不知道私用信号量的存在,因此,一旦发生私用信号量的占用者异常结束或正常结束, 但并未释放该信号量所占用的空间时,系统无法使它恢复为0(空),也不能将它传送给下一个 请求它的线程 当要实现不同进程间或不同进程中各线程之间的同步时,则可由系统为它们创建一个公用 信号量,其数据结构存放在受保护的系统存储区中,并由os为它分配空间并进行管理,故也称 其为系统信号量。如果信号量的占有者在结束时未释放该公用信号量,则0S会自动将该信号 量空间回收,并通知下一个进程。可见,公用信号量是一种比较安全的同步机制 4.内核支持线程和用户级线程 线程己在许多系统中实现,但实现的方式并不完全相同。有些系统中,特别是一些数据库
或某种其他原因而引起的,此时它是被强行终止的。可见,线程如同进程一样,具有一定的生命 周期。 3.线程的同步 在多线程 os 中通常提供多种同步机制,如互斥锁、条件变量、信号量机制以及多读、单 写锁等,它们可支持不同频率的交互操作和不同程度的并行性。 （1)互斥锁 互斥锁有开锁和关锁两种状态,并能进行关锁和开锁两种操作。当一个线程需要访问某个 临界资源时,线程首先应对为该资源所设置的互斥锁 mutex 进行关锁操作 mutex_enter:判别 mutex的状态,如果它已处于关锁状态,则试图访问该资源的线程将被阻塞;而如果mutex处于 开锁状态,则将 mutex 关上后便可访问该资源。在线程完成对共享资源的访问后,必须执行开 锁操作 mutex-exit:如果有线程阻塞在该互斥锁上,则唤醒其中的一个线程;而如果没有阻塞 的线程,则将互斥锁的状态置成开锁状态。为了降低线程被阻塞的频率,在有的系统中还提供 了一种不阻塞的关锁操作mutex_tryenter,当mutex处于关锁状态时,mutex_tryenter并不阻 塞线程,而只是返回一个指示操作失败的状态码。 互斥锁是一种比较简单的同步机制,而且是严格括入的(bracketing),一个线程去打开被 另一线程关闭的互斥锁将是错误的,因此它只适用于实现线程对资源的互斥访问。由于操作互 斥锁的时间和空间开销都较低,因而它较适合于高频度使用的关键共享数据和程序段。 （2)条件变量 条件变量必须和互斥锁配合起来使用,它用于等待,直到某一特定条件为真。对条件变量 的 cv_wait 操作将使线程阻塞,直到所等的条件信号成立后,才能由 cv_signal 操作将其中的 一个阻塞线程唤醒。cv_wait 操作在阻塞线程前将对相应的互斥锁执行开锁操作,并在返回前 重新对互斥锁进行关锁操作。条件变量可用来实现互斥或同步,它的典型使用方式为: mutex_enter(&mutex); ┇ while(some_condition){ cv_wait(&cv,&mutex); } ┇ mutex_exit(&mutex); 这里允许条件是一个复杂的表达式,因为它受互斥锁的保护。 （3)信号量机制 信号量机制也可用于多线程 os 中,实现诸线程或进程之间的同步。为了提高效率,可为线程和 进程分别设置相应的信号量。 当某线程利用信号量来实现同一进程中各线程之间的同步时,可调用创建信号量命令来创 建一私用信号量,其数据结构被存放在应用程序的地址空间中。私用信号量属于特定的进程所 有,OS 并不知道私用信号量的存在,因此,一旦发生私用信号量的占用者异常结束或正常结束, 但并未释放该信号量所占用的空间时，系统无法使它恢复为 0(空),也不能将它传送给下一个 请求它的线程。 当要实现不同进程间或不同进程中各线程之间的同步时,则可由系统为它们创建-个公用 信号量,其数据结构存放在受保护的系统存储区中,并由 os 为它分配空间并进行管理,故也称 其为系统信号量。如果信号量的占有者在结束时未释放该公用信号量,则 OS 会自动将该信号 量空间回收,并通知下一个进程。可见,公用信号量是一种比较安全的同步机制。 4.内核支持线程和用户级线程 线程己在许多系统中实现,但实现的方式并不完全相同。有些系统中,特别是一些数据库