进程管理知识点

《进程管理知识点》由会员分享，可在线阅读，更多相关《进程管理知识点（120页珍藏版）》请在金锄头文库上搜索。

1、进程管理知识点第二章第二章 进程管理程管理 2.1 2.1 进程的基本概念程的基本概念 2.2 2.2 进程控制程控制 2.3 2.3 进程同步程同步 2.4 2.4 经典典进程的同步程的同步问题 2.5 2.5 管程机制管程机制 2.6 2.6 进程通信程通信 2.7 2.7 线程程 22.1 进程的基本概念程的基本概念 2.1.1 程序的程序的顺序序执行及其特征行及其特征 1. 程序的程序的顺序序执行行 仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。 S1: a =x+y; S2: b =a-5; S3

2、: c =b+1;3图 2-1 程序的顺序执行 42. 程序程序顺序序执行行时的特征的特征 (1)顺序性：(2)(2) 封闭性： (3)(3) 可再现性： 52.1.2 前前趋图 前前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描描述述进程程之之间执行行的的前前后后关系关系。 图中中的的每每个个结点点可可用用于于描描述述一一个个程程序序段段或或进程程，乃乃至至一一条条语句句；结点点间的的有有向向边则用用于于表表示示两两个个结点点之之间存存在在的的偏偏序序(Partial Order)或或前前趋关系关系(Preced

3、ence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。 在前趋图中，把没有前趋的结点称为初初始始结点点(Initial Node)，把没有后继的结点称为终止止结点点(Final Node)。6 每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 IiCiPi 和和 S1S2S3 前面的前面的图2-1中，存在着前中，存在着前驱关系：关系：7图 2-2对于图 2-2所示的图， 试判断是否前趋图： 8

4、对于图 2-2(a)所示的前趋图， 存在下述前趋关系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为： 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) 应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系： S2S3, S3S2 92.1.

5、3 程序的并程序的并发执行及其特征行及其特征 1. 程序的并程序的并发执行行 图 2-3 并发执行时的前趋图 10在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+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 四条语句的前趋关系112. 程序并程序并发执行行时的特征的特征 1)间断性2)2) 失去封闭性 3)3) 不可再现性 例例如如，有有两两个个循循环程程序序A和和B，它它们共共享享一

6、一个个变量量N。程程序序A每每执行行一一次次时，都都要要做做N =N+1操操作作；程程序序B每每执行行一一次次时， 都都要要执行行Print(N)操操作作，然然后再将后再将N置成置成“0”。程序。程序A和和B以不同的速度运行。以不同的速度运行。 (1) N =N+1在在Print(N)和和N =0之前，此之前，此时得到的得到的N值分分别为n+1, n+1, 0。 (2) N =N+1在在Print(N)和和N =0之后，此之后，此时得到的得到的N值分分别为n, 0, 1。 (3) N =N+1在在Print(N)和和N =0之之间，此，此时得到的得到的N值分分别为n, n+1, 0。 122.

7、1.4 进程的特征与状程的特征与状态 1. 进程的特征和定程的特征和定义 1)结构特征2)2) 动态性 3)3) 并发性 4)4) 独立性 5)5) 异步性 13 较典型的典型的进程定程定义有：有： (1) 进程是程序的一次程是程序的一次执行。行。 (2) 进程程是是一一个个程程序序及及其其数数据据在在处理理机机上上顺序序执行行时所所发生的活生的活动。 (3) 进程程是是程程序序在在一一个个数数据据集集合合上上运运行行的的过程程，它它是是系系统进行行资源分配和源分配和调度的一个独立度的一个独立单位。位。 在在引引入入了了进程程实体体的的概概念念后后，我我们可可以以把把传统OS中中的的进程程定定

8、义为：“进程程是是进程程实体体的的运运行行过程程，是是系系统进行行资源分配和源分配和调度的一个独立度的一个独立单位位”。 142. 进程的三种基本状程的三种基本状态 1)就绪(Ready)状态 2)2) 执行状态 3)3) 阻塞状态 图 2-5 进程的三种基本状态及其转换 153. 挂起状挂起状态1)引入挂起状引入挂起状态的原因的原因 (1)终端用户的请求。 (2)(2) 父进程请求。 (3)(3) 负荷调节的需要。 (4)(4) 操作系统的需要。 162) 进程状程状态的的转换 (1)活活动就就绪静止就静止就绪。 (2)(2) 活活动阻塞阻塞静止阻塞。静止阻塞。 (3)(3) 静止就静止就绪

9、活活动就就绪。 (4)(4) 静止阻塞静止阻塞活活动阻塞。阻塞。 图 2-6 具有挂起状态的进程状态图 172.1.5 进程控制程控制块 1. 进程控制程控制块的作用的作用 进程程控控制制块的的作作用用是是使使一一个个在在多多道道程程序序环境境下下不不能能独独立立运运行行的的程程序序(含含数数据据)，成成为一一个个能能独独立立运运行行的的基基本本单位位，一一个个能能与与其其它它进程程并并发执行行的的进程程。或或者者说，OS是根据是根据PCB来来对并并发执行的行的进程程进行控制和管理的。行控制和管理的。182. 进程控制程控制块中的信息中的信息 1) 进程程标识符符 进程标识符用于惟一地标识一个

10、进程。一个进程通常有两种标识符： (1) 内内部部标识符符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数数字字标识符符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。 (2) 外外部部标识符符。它由创建者提供，通常是由由字字母母、数数字字组成成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系， 还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。 PCB中的信息包含：中的信息包含： 进程程标识符，符，处理机状理机状态，进程程调度信息，度信息，进程控制信息。程控制信息。19 2) 处理机状理机状态 处理机状态信息主要是由处理机

11、的各种寄存器中的内容组成的。 通通用用寄寄存存器器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息， 在大多数处理机中，有 832个通用寄存器，在RISC结构的计算机中可超过100 个； 指令指令计数器数器，存放了要访问的下一条指令的地址； 程程序序状状态字字PSW，其中含有状态信息，如条件码、执行方式、 中断屏蔽标志等； 用用户栈指指针， 指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。 20 3) 进程程调度信息度信息 在PCB中还存放一些与进程调度和进程对换有关的信息，包括： 进程程状状态，指明进程的当前状态， 作

12、为进程调度和对换时的依据； 进程程优先先级，用于描述进程使用处理机的优先级别的一个整数， 优先级高的进程应优先获得处理机； 进程程调度度所所需需的的其其它它信信息息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、 进程已执行的时间总和等； 事事件件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。 21 4) 进程控制信息程控制信息 进程控制信息包括： 程序和数据的地址， 是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进程同步和通信机制，指实现进程同步和进程通信时必需的机制， 如消息队列指针、信号量等

13、，它们可能全部或部分地放在PCB中； 资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针， 它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。 223. 进程控制程控制块的的组织方式方式 1) 链接方式 图 2-7 PCB链接队列示意图 链接方式， 索引方式 232) 索引方式 图 2-8 按索引方式组织PCB 242.2 进 程程 控控 制制 2.2.1 进程的程的创建建 1. 进程图(Process Graph) 图 2-9 进程树 252. 引起引起创建建进程的事件程的事件 (1)用用户登登录。 (2)(2) 作作业调度。度。

14、 (3)(3) 提供服提供服务。 (4)(4) 应用用请求。求。 263. 进程的程的创建建(Creation of Progress) (1)申请空白PCB。 (2) 为新进程分配资源。 (3) 初始化进程控制块。 (4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。 272.2.2 进程的程的终止止 1. 引起引起进程程终止止(Termination of Process)的事件的事件 1) 正常结束 在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Ho

15、lt指令时，将产生一个中断，去通知OS本进程已经完成。 在分时系统中，用户可利用Logs off去表示进程运行完毕， 此时同样可产生一个中断，去通知OS进程已运行完毕。 28 2) 异常异常结束束 在在进程程运运行行期期间，由由于于出出现某某些些错误和和故故障障而而迫迫使使进程程终止。止。这类异常事件很多，常异常事件很多，常见的有：的有： 越界越界错误。这是指程序所是指程序所访问的存的存储区，已越出区，已越出该进程的区域；程的区域； 保保护错。进程程试图去去访问一一个个不不允允许访问的的资源源或或文文件件，或或者者以以不不适当的方式适当的方式进行行访问，例如，例如，进程程试图去写一个只去写一个

16、只读文件；文件； 非非法法指指令令。程程序序试图去去执行行一一条条不不存存在在的的指指令令。出出现该错误的的原原因因，可能是程序可能是程序错误地地转移到数据区，把数据当成了指令；移到数据区，把数据当成了指令； 特特权指令指令错。用。用户进程程试图去去执行一条只允行一条只允许OS执行的指令；行的指令； 运行超运行超时。进程的程的执行行时间超超过了指定的最大了指定的最大值； 等待超等待超时。进程等待某事件的程等待某事件的时间， 超超过了了规定的最大定的最大值； 算算术运算运算错。进程程试图去去执行一个被禁止的运算，例如，被行一个被禁止的运算，例如，被0除；除； I/O故障。故障。这是指在是指在I/

17、O过程中程中发生了生了错误等。等。 29 3) 外界干外界干预 外界干预并非指在本本进程程运运行行中中出出现了了异异常常事事件件，而是指而是指进程程应外界的外界的请求而求而终止运行。止运行。这些干预有： 操作员或操作系统干预。 由于某种原因，例如，发生了死锁， 由操作员或操作系统终止该进程； 父进程请求。 由于父进程具有终止自己的任何子孙进程的权利， 因而当父进程提出请求时，系统将终止该进程； 父进程终止。 当父进程终止时，OS也将他的所有子孙进程终止。 30 2. 进程的程的终止止过程程 (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 (2) 若被

18、终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。 (4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。 (5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。 312.2.3 进程的阻塞与程的阻塞与唤醒醒1. 引起引起进程阻塞和程阻塞和唤醒的事件醒的事件 1)请求系统服务 2)2) 启动某种操作 3)3) 新数据尚未到达 4)4) 无新工作可做 32 2. 进程阻塞程阻塞过程程 正正在在执行行的

19、的进程程，当当发现上上述述某某事事件件时，由由于于无无法法继续执行行，于于是是进程程便便通通过调用用阻阻塞塞原原语block把把自自己己阻阻塞塞。可可见，进程的阻塞是程的阻塞是进程自身的一种主程自身的一种主动行行为。 进入入block过程程后后，由由于于此此时该进程程还处于于执行行状状态，所所以以应先先立立即即停停止止执行行，把把进程程控控制制块中中的的现行行状状态由由“执行行”改改为阻阻塞塞，并并将将PCB插插入入阻阻塞塞队列列。如如果果系系统中中设置置了了因因不不同同事事件件而而阻阻塞塞的的多多个个阻阻塞塞队列列，则应将将本本进程程插插入入到到具具有有相相同同事事件件的的阻阻塞塞(等等待待

20、)队列列。 最最后后，转调度度程程序序进行行重重新新调度度，将将处理理机机分分配配给另另一一就就绪进程程，并并进行行切切换，亦亦即即，保保留留被被阻阻塞塞进程程的的处理理机机状状态(在在PCB中中)，再再按按新新进程程的的PCB中的中的处理机状理机状态设置置CPU的的环境。境。 33 3. 进程程唤醒醒过程程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒醒原原语wakeup( )，将等待该事件的进程唤醒。 唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就

21、绪，然后再将该PCB插入到就绪队列中。 342.2.4 进程的挂起与激活程的挂起与激活 1. 进程的挂起程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂挂起起原原语suspend( )将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。 35 2. 进程的激活程的激活过程

22、程 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原激活原语active( )将指定进程激活。 激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。 362.3 进

23、程程 同同 步步 2.3.1 进程同步的基本概念程同步的基本概念 1. 两种形式的制两种形式的制约关系关系 (1)间接相互制约关系。 (2)(2) 直接相互制约关系。 372. 临界界资源源(Critical Resouce) 生生产者者-消消费者者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有有一一群群生生产者者进程程在在生生产产品品，并并将将这些些产品品提提供供给消消费者者进程程去去消消费。为使使生生产者者进程程与与消消费者者进程程能能并并发执行行，在在两两者者之之间设置置了了一一个个具具有有n个个缓冲冲区区的的缓冲冲池池，生生产者者进程程将将它它所所生

24、生产的的产品品放放入入一一个个缓冲冲区区中中； 消消费者者进程程可可从从一一个个缓冲冲区区中中取取走走产品品去去消消费。尽尽管管所所有有的的生生产者者进程程和和消消费者者进程程都都是是以以异异步步方方式式运运行行的的，但但它它们之之间必必须保保持持同同步步，即即不不允允许消消费者者进程程到到一一个个空空缓冲冲区区去去取取产品品；也也不不允允许生生产者者进程程向向一一个个已已装装满产品品且且尚尚未被取走的未被取走的缓冲区中投放冲区中投放产品。品。 38Var n, integer;type item=;var buffer:array 0, 1, , n-1 of item;in, out: 0

25、, 1, , n-1;counter: 0, 1, , n; 指指针in和和out初始化初始化为1。 我们可利用一个数数组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。 用输入入指指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出出指指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。 由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in=(in+1)mod n；输出指针加1表示成out=(out+1) mod n。当(in+1) mod n=out时表示缓冲池满；而in=out则表示

26、缓冲池空。 此外，还引入了一个整整型型变量量counter, 其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时， 使counter减1。生产者和消费者两进程共享下面的变量： 39producer: repeat produce an item in nextp; while counter=n do no-op; bufferin =nextp; in =in+1 mod n; counter =counter+1; until false;consumer: repeat while counter=0 do no-op; n

27、extc =bufferout; out =(out+1) mod n; counter =counter-1; consumer the item in nextc; until false; 指针in和out初始化为1。在生产者和消费者进程的描述中，no-op是一条空操作指令，while condition do no-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品40 虽

28、然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两两个个进程程共共享享变量量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时， 常可用下面的形式描述： register 1 =counter; register 2 =counter; register1 =register 1+1; register 2 =register 2-1; counter =register 1; counter =register 2; 41 假假设：counter的的当当前前值是是5。

29、如如果果生生产者者进程程先先执行行左左列列的的三三条条机机器器语言言语句句，然然后后消消费者者进程程再再执行行右右列列的的三三条条语句句， 则最最后后共共享享变量量counter的的值仍仍为5；反反之之，如如果果让消消费者者进程程先先执行行右右列列的的三三条条语句句，然然后再后再让生生产者者进程程执行左列的三条行左列的三条语句，句，counter值也也还是是5。 但是，如果按下述但是，如果按下述顺序序执行：行： register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =cou

30、nter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4) 423. 临界区界区(critical section) 可把一个访问临界资源的循环进程描述如下：repeat critical section; remainder section;until false; entry sectionexit section434. 同步机制同步机制应遵循的遵循的规则 (1)空空闲让进。(2)(2) 忙忙则

31、等待。等待。 (3)(3) 有限等待。有限等待。 (4)(4) 让权等待。等待。 442.3.2 信号量机制信号量机制 1. 整型信号量整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S): while S0 do no-op S=S-1; signal(S): S =S+1; 45 2. 记录型信号量型信号量 在整型信号量机制中的wait操作，只要是信号量S0， 就会不断地测

32、试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。 记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。 为此，在信号量机制中，除了需要一个用于代代表表资源源数数目目的的整整型型变量量value外，还应增增加加一一个个进程程链表表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为： 46type semaphore=record value:integer; L:list of process; end相应地，wait(

33、S)和signal(S)操作可描述为：procedure wait(S) var S: semaphore; begin S.value =S.value-1; if S.value0 then block(S.L) end procedure signal(S) var S: semaphore; begin S.value =S.value+1; if S.value0 then wakeup(S.L); end 47 在记录型信号量机制中，S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.valu

34、e =S.value-1； 当当S.value0时，表表示示该类资源源已已分分配配完完毕，因因此此进程程应调用用block原原语，进行行自自我我阻阻塞塞，放放弃弃处理理机机，并并插插入到信号量入到信号量链表表S.L中中。 可见，该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。 若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果

35、S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。 483. AND型信号量型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作， 即process A: process B:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若进程A和B按下述次序交替执行wait操作：process A: wait(Dmutex); 于是Dmutex=0process B: wait(Emutex); 于是Emutex=0process A: wait(Emutex); 于是Emutex=-1 A阻

36、塞process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 49 AND同同步步机机制制的的基基本本思思想想是是：将将进程程在在整整个个运运行行过程程中中需需要要的的所所有有资源源，一一次次性性全全部部地地分分配配给进程程，待待进程程使使用用完完后后再再一一起起释放放。只只要要尚尚有有一一个个资源源未未能能分分配配给进程程，其其它它所所有有可可能能为之之分分配配的的资源源，也也不不分分配配给他他。亦亦即即，对若若干干个个临界界资源源的的分分配配，采采取取原原子子操操作作方方式式：要要么么全全部部分分配到配到进程，要么一个也不分配。程，要么一个也不分配。 由由死死锁理理论

37、可可知知，这样就就可可避避免免上上述述死死锁情情况况的的发生生。为此此，在在wait操操作作中中，增增加加了了一一个个“AND”条条件件，故故称称为AND同同步步，或或称称为同同时wait操操作作， 即即Swait(Simultaneous wait)定定义如下：如下： 50Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i =1 to n do Si=Si-1; endfor else place the process in the waiting queue associated with the first Si found with S

38、i1, and set the program count of this process to the beginning of Swait operation endifSsignal(S1, S2, , Sn) for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; 514. 信号量集信号量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then

39、for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation. endif signal(S1, d1, , Sn, dn) for i=1 to n do Si =Si+di;Remove all the process waiting in the queue associated with S

40、i into the ready queue endfor; 52 一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况： (1) Swait(S, d, d)。 此此时在在信信号号量量集集中中只只有有一一个个信信号号量量S， 但但允允许它它每每次次申申请d个个资源源，当当现有有资源源数数少少于于d时，不予分配。不予分配。 (2) Swait(S, 1, 1)。 此此时的的信信号号量量集集已已蜕化化为一一般般的的记录型信号量型信号量(S1时)或互斥信号量或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是是一一种种很很特特殊殊且且很很有有用用的的信信号号量量操操作作。当

41、当S1时，允允许多多个个进程程进入入某某特特定定区区；当当S变为0后后，将将阻阻止止任任何何进程程进入入特特定定区区。换言言之之，它它相相当当于于一一个个可可控控开关。开关。 532.3.3 信号量的信号量的应用用 1. 利用信号量利用信号量实现进程互斥程互斥 利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion until false; 54 end pro

42、cess 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 552. 利用信号量利用信号量实现前前趋关系关系 图 2-10 前趋图举例 56 Var a,b,c,d,e,f,g; semaphore=0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wai

43、t(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 572. 3.4 管管 程程 机机 制制 1. 管程的基本概念管程的基本概念 1)管程的定管程的定义 管程由三部分管程由三部分组成：成： 局部于管程的共享局部于管程的共享变量量说明；明； 对该数据数据结构构进行操作的一行操作的一组过程；程； 对局局部部于于管管程程的的数数据据设置置初初始始值的的语句句

44、。此此外外，还须为管程管程赋予一个名字。予一个名字。 58图 2-11 管程的示意图 59管程的管程的语法如下：法如下： type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 602) 条件条件变量量 管程中对每个条件变量，都须予以说明，其形式为：Var x, y:condition。 该变量量应

45、置置于于wait和和signal之之前前，即即可可表表示示为X.wait和和X.signal。例例如如，由由于于共共享享数数据据被被占占用用而而使使调用用进程程等等待待，该条条件件变量量的的形形式式为：nonbusy:condition。此此时， wait原原语应改改为nonbusy.wait，相相应地，地，signal应改改为nonbusy.signal。 应当指出，X.signal操操作作的的作作用用，是重重新新启启动一一个个被被阻阻塞塞的的进程程，但但如如果果没没有有被被阻阻塞塞的的进程程，则X.signal操操作作不不产生生任任何何后后果果。这与信号量机制中的signal操作不同。因为

46、，后者总是要执行s =s+1操作，因而总会改变信号量的状态。 61 如果有进程程Q处于于阻阻塞塞状状态， 当当进程程P执行行了了X.signal操操作作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理： (1) P等待，直至Q离开管程或等待另一条件。 (2) Q等待，直至P离开管程或等待另一条件。 采用哪种处理方式， 当然是各执一词。 但是Hansan却采用了第一种处理方式。 622 .利用管程解决生利用管程解决生产者者-消消费者者问题 在利用管程方法来解决生产者-消费者问题时， 首先便是为它们建立一个管程，并命名为Proclucer-Consumer, 或简称为PC。其中

47、包括两个过程： (1) put(item)过程。 (2) get(item)过程。63 (1) put(item)过程程。 生生产者者利利用用该过程程将将自自己己生生产的的产品品投投放放到到缓冲冲池池中中， 并并用用整整型型变量量count来来表表示示在在缓冲冲池池中中已已有有的的产品品数数目目，当当countn时，表表示示缓冲冲池池已已满，生生产者者须等待。等待。 (2) get(item)过程程。消消费者者利利用用该过程程从从缓冲冲池池中中取取出出一一个个产品品，当当count0时，表表示示缓冲冲池池中中已已无无可可取取用用的的产品品， 消消费者者应等待。等待。 64type produc

48、er-consumer=monitor Var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in) =nextp; in =(in+1) mod n; count =count+1; if notempty.queue then notempty.signal; end65 procedure entry get(item) begin if cou

49、nt0 then notempty.wait; nextc =buffer(out); out =(out+1) mod n; count =count-1; if notfull.quene then notfull.signal; end begin in =out =0; count =0 end 66 在利用管程解决生产者-消费者问题时， 其中的生产者和消费者可描述为： producer:begin repeat produce an item in nextp; PC.put(item); until false; end consumer:begin repeat PC.get(i

50、tem); consume the item in nextc; until false; end 672.4 经典典进程的同步程的同步问题 2.4.1 生生产者者消消费者者问题 前前面面我我们已已经对生生产者者消消费者者问题(The proceducer-consumer problem)做做了了一一些些描描述述，但但未未考考虑进程程的的互互斥斥与与同同步步问题，因因而而造造成成了了数数据据Counter的的不不定定性性。由由于于生生产者者消消费者者问题是是相相互互合合作作的的进程程关关系系的的一一种种抽抽象象。例例如如， 在在输入入时，输入入进程程是是生生产者者，计算算进程程是是消消费者者

51、；而而在在输出出时，则计算算进程程是是生生产者者，而而打打印印进程程是是消消费者，者， 因此，因此，该问题有很大的代表性及有很大的代表性及实用价用价值。 68 1. 利用利用记录型信号量解决生型信号量解决生产者者消消费者者问题 假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下： 69Var mutex,

52、 empty, full:semaphore =1,n,0; buffer:array0, , n-1 of item; in, out: integer =0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in) =nextp; in =(in+1) mod n; signal(mutex); signal(full); until false; end 70consumer:begin repeat wait(full); wait(mu

53、tex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 71 在在生生产者者消消费者者问题中中应注注意意：首首先先，在在每每个个程程序序中中用用于于实现互互斥斥的的wait(mutex)和和signal(mutex)必必须成成对地地出出现； 其其次次，对资源源信信号号量量empty和和full的的wait和和signal操操作作，同同样需需要要成成对地地出出现，但但它它们分分别处于于不不同

54、同的的程程序中。序中。 例例如如，wait(empty)在在计算算进程程中中，而而signal(empty)则在在打打印印进程程中中，计算算进程程若若因因执行行wait(empty)而而阻阻塞塞， 则以以后后将将由由打打印印进程程将将它它唤醒醒；最最后后，在在每每个个程程序序中中的的多多个个wait操操作作顺序序不不能能颠倒倒。应先先执行行对资源源信信号号量量的的wait操操作作，然然后后再再执行行对互互斥斥信信号号量量的的wait操操作作，否否则可可能引起能引起进程死程死锁。722. 利用利用AND信号量解决生信号量解决生产者者消消费者者问题 ar mutex, empty, full:se

55、maphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty, mutex); buffer(in) =nextp; in =(in+1)mod n; Ssignal(mutex, full); until false; end consumer:begin repeat Swait(full, mutex); nextc =buffer(out); out =(out

56、+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end parend end 73742.4.2 哲学家哲学家进餐餐问题 1. 利用利用记录型信号量解决哲学家型信号量解决哲学家进餐餐问题 经分析可知，放在桌子上的筷筷子子是是临界界资源源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用用一一个个信信号号量量表表示示一一只只筷筷子子，由由这五五个个信信号号量量构构成成信信号号量数量数组。其描述如下： Var chopstick: array0, , 4 of semaphore

57、; 所有信号量均被初始化为1， 75第第i位哲学家的活位哲学家的活动可描述可描述为： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopsticki); signal(chopstick(i+1) mod 5); think; until false; 76 可采取以下几种解决方法：可采取以下几种解决方法： (1) 至至多多只只允允许有有四四位位哲哲学学家家同同时去去拿拿左左边的的筷筷子子，最最终能能保保证至至少少有有一一位位哲哲学学家家能能够进餐餐，并并在在用用毕时能能释放放出他用出他用过的两只筷子，从而

58、使更多的哲学家能的两只筷子，从而使更多的哲学家能够进餐。餐。 (2) 仅当当哲哲学学家家的的左左、右右两两只只筷筷子子均均可可用用时，才才允允许他他拿起筷子拿起筷子进餐。餐。 (3) 规定定奇奇数数号号哲哲学学家家先先拿拿他他左左边的的筷筷子子，然然后后再再去去拿拿右右边的的筷筷子子；而而偶偶数数号号哲哲学学家家则相相反反。按按此此规定定，将将是是1、 2号号哲哲学学家家竞争争1号号筷筷子子；3、4号号哲哲学学家家竞争争3号号筷筷子子。即即五五位位哲哲学学家家都都先先竞争争奇奇数数号号筷筷子子，获得得后后，再再去去竞争争偶偶数号筷子，最后数号筷子，最后总会有一位哲学家能会有一位哲学家能获得两只

59、筷子而得两只筷子而进餐。餐。 77 2. 利用利用AND信号量机制解决哲学家信号量机制解决哲学家进餐餐问题 在哲学家进餐问题中，要要求求每每个个哲哲学学家家先先获得得两两个个临界界资源源(筷筷子子)后后方方能能进餐餐，这在在本本质上上就就是是前前面面所所介介绍的的AND同步同步问题，故用，故用AND信号量机制可信号量机制可获得最得最简洁的解法。的解法。Var chopsiick array 0, , 4 of semaphore =(1,1,1,1,1); processi repeat think; Sswait(chopstick(i+1) mod 5, chopstick i); eat

60、; Ssignat(chopstick (i+1) mod 5, chopstick i); until false; 782.4.3 读者者-写者写者问题 1. 利用利用记录型信号量解决型信号量解决读者者-写者写者问题 为实现Reader与与Writer进程程间在在读或或写写时的的互互斥斥而而设置置了了一一个个互互斥斥信信号号量量Wmutex。另另外外，再再设置置一一个个整整型型变量量Readcount表表示示正正在在读的的进程数目。程数目。 由由于于只只要要有有一一个个Reader进程程在在读，便便不不允允许Writer进程程去去写写。因因此此，仅当当Readcount=0, 表表示示尚尚

61、无无Reader进程程在在读时，Reader进程程才才需需要要执行行Wait(Wmutex)操操作作。若若wait(Wmutex)操操作作成成功功，Reader进程程便便可可去去读，相相应地地，做做Readcount+1操操作作。同同理理，仅当当Reader进程程在在执行行了了Readcount减减1操操作作后后其其值为0时，才才须执行行signal(Wmutex)操操作作，以以便便让Writer进程程写写。又又因因为Readcount是是一一个个可可被被多多个个Reader进程程访问的的临界界资源，因此，源，因此，应该为它它设置一个互斥信号量置一个互斥信号量rmutex。 79读者者-写者写

62、者问题可描述如下：可描述如下：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; wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(

63、rmutex); until false; end writer:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; end parend end 802. 利用信号量集机制解决利用信号量集机制解决读者者-写者写者问题 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(

64、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 81822.6 进 程程 通通 信信 2.6.1 进程通信的程通信的类型型 1. 共享存共享存储器系器系统(Shared-Memory System) (1)基于共享数据共享数据结构构的通信方式。 (2)(2) 基于共享存共享存储区区的通信方式。 83 2. 消息消息传递系系统(Message passing system) 不论

65、是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。 消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直直接接通通信信方方式式和间接接通通信信方方式式两种。 84 3. 管道管道(Pipe)通信通信 所谓“管道”，是指用用于于连接接一一个个读进程程和和一一个个写写进程程以以实现他他

66、们之之间通通信信的的一一个个共共享享文文件件，又又名名pipe文文件件。 向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由由于于发送送进程程和和接接收收进程程是是利利用用管管道道进行行通通信信的的，故故又又称称为管管道道通通信信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。 85 为了协调双方的通信，管道机制必须提供以下三方面的协调能力： 互互斥斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。 同同步步，指当写(输入)进

67、程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。 确确定定对方方是是否否存存在在，只有确定了对方已存在时，才能进行通信。 862.6.2 消息消息传递通信的通信的实现方法方法 1. 直接通信方式直接通信方式 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)： Send(Receiver, message); 发送一个消息给接收进程； Receive

68、(Sender, message); 接收Sender发来的消息；例如，原语Send(P2, m1)表示将消息m1发送给接收进程P2; 而原语Receive(P1，m1)则表示接收由P1发来的消息m1。 87 在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为： Receive (id, message); 88 我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，

69、便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下： repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive(producer, nextc); consume the item in nextc; until false; 892. 间接通信方式接通信方式 (1) 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给

70、出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱， 还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。 (2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。 Send(mailbox, message); 将一个消息发送到指定信箱； Receive(mailbox, message); 从指定信箱中接收一个消息； 90 信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。 1) 私用信箱 用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中

71、读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。 当拥有该信箱的进程结束时，信箱也随之消失。 91 2) 公用信箱 它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。 3) 共享信箱 它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。 92 在在利利用用信信箱箱通通信信时，在在发送送进程程和和接接收

72、收进程程之之间，存存在在以以下四种关系：下四种关系： (1) 一一对一一关关系系。这时可可为发送送进程程和和接接收收进程程建建立立一一条条两两者者专用的通信用的通信链路，使两者之路，使两者之间的交互不受其他的交互不受其他进程的干程的干扰。 (2) 多多对一一关关系系。允允许提提供供服服务的的进程程与与多多个个用用户进程程之之间进 行行 交交 互互 ， 也也 称称 为 客客 户 /服服 务 器器 交交 互互 (client/server interaction)。 (3) 一一对多多关关系系。允允许一一个个发送送进程程与与多多个个接接收收进程程进行行交交互，使互，使发送送进程可用广播方式，向接收

73、者程可用广播方式，向接收者(多个多个)发送消息。送消息。 (4) 多多对多多关关系系。允允许建建立立一一个个公公用用信信箱箱，让多多个个进程程都都能能向信箱中投向信箱中投递消息；也可从信箱中取走属于自己的消息。消息；也可从信箱中取走属于自己的消息。 932.6.3 消息消息传递系系统实现中的若干中的若干问题 1. 通信通信链路路(communication link) 为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。 第一种方式是：由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除

74、链路。 这种方式主要用于计算机网络中。 第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。 94 根据通通信信链路路的的连接接方方法法，又可把通信链路分为两类： 点点连接通信链路，这时的一条链路只连接两个结点(进程)； 多点连接链路，指用一条链路连接多个(n2)结点(进程)。 而根根据据通通信信方方式式的不同，则又可把链路分成两种： 单向通信链路，只允许发送进程向接收进程发送消息； 双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。 952. 消息的格式消息的格式 在某些OS中

75、，消息是采用比较短短的的定定长消消息息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，采用另一种变长的的消消息息格格式式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。 这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。 963. 进程同步方式程同步方式 (1)发送进程阻塞、 接收进程阻塞。(2)(2) 发送进程不阻塞、 接收进程阻塞。 (3)(3) 发送进程和接收进程均不阻塞。 972.6.4 消息消息缓冲冲队列通信机制

76、列通信机制 1. 消息消息缓冲冲队列通信机制中的数据列通信机制中的数据结构构 (1) 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：type message buffer=record sender; 发送者送者进程程标识符符 size; 消息消息长度度 text; 消息正文消息正文 next; 指向下一个消息指向下一个消息缓冲区的指冲区的指针 end 98 (2) PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程 的 PCB中 。 在 PCB中 应 增 加

77、 的 数 据 项 可 描 述 如 下 ： type processcontrol block=record mq; 消息消息队列列队首指首指针 mutex; 消息消息队列互斥信号量列互斥信号量 sm; 消息消息队列列资源信号量源信号量 end 99 2. 发送原送原语 发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图 2 - 12 所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将

78、i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源， 故在执行insert操作的前后，都要执行wait和signal操作。 100图 2 - 12 消息缓冲通信 101 procedure send(receiver, a) begin getbuf(a.size,i); 根据根据a.size申申请缓冲区；冲区； i.sender =a.sender; 将将发送区送区a中的信息复制到消息中的信息复制到消息缓冲区之中；冲区之中； i.size =a.size; i.text =a.text; i.next =0; getid(PCB s

79、et, receiver.j); 获得接收得接收进程内部程内部标识符；符； wait(j.mutex); insert(j.mq, i); 将消息将消息缓冲区插入消息冲区插入消息队列；列； signal(j.mutex); signal(j.sm); end 1023. 接收原接收原语 接收原接收原语描述如下：描述如下：procedure receive(b) begin j =internal name; j为接收接收进程内部的程内部的标识符；符； wait(j.sm); wait(j.mutex); remove(j.mq, i); 将消息将消息队列中第一个消息移出；列中第一个消息移出；

80、signal(j.mutex); b.sender =i.sender; 将将消消息息缓冲冲区区i中中的的信信息息复复制制到到接接收收区区b; b.size =i.size; b.text =i.text; end 1032.7 线 程程 2.7.1 线程的基本概念程的基本概念 为使程序能并发执行，系统还必须进行以下的一系列操作。 1) 创建进程 2) 撤消进程 3) 进程切换 1042. 线程的属性程的属性 (1)轻型实体。 (2)(2) 独立调度和分派的基本单位。 (3)(3) 可并发执行。 (4)(4) 共享进程资源。 105 3. 线程的状程的状态 (1) 状态参数。 在OS中的每一个

81、线程都可以利用线程程标识符符和一一组状状态参数参数进行描述。 状态参数通常有这样几项： 寄存器状态，它包括程序计数器PC和堆栈指针中的内容； 堆栈，在堆栈中通常保存有局部变量和返回地址； 线程运行状态， 用于描述线程正处于何种运行状态；优先级， 描述线程执行的优先程度； 线程专有存储器， 用于保存线程自己的局部变量拷贝； 信号屏蔽， 即对某些信号加以屏蔽。 106 (2) 线程运行状态。 如同传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。 相应地，线程在运行时，也具有下述三种基本状具有下述三种基本状态：执行状行状态，表示线程正获得处理机而运行；

82、就就绪状状态， 指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；阻阻塞塞状状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。 107 4. 线程的程的创建和建和终止止 在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初初始始化化线程程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后使用。 终止线程的方式有两种：一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出

83、现错误或由于某种原因而被其它线程强行终止。 1085. 多多线程程OS中的中的进程程 在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有以下属性： (1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。 1092.7.2 线程程间的同步和通信的同步和通信 1. 互斥互斥锁(mutex) 互斥锁是一种比较简单的的、用用于于实现进程程间对资源源互互斥斥访问的的机机制制。由于操作互斥锁的时间和空间开锁都较低， 因而较适适合合于于高高频度度使使用用的的关关键共共

84、享享数数据据和和程程序序段段。互斥锁可以有两种状态， 即开锁(unlock)和关锁(lock)状态。 相应地，可用两条命令(函数)对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。 1102. 条件条件变量量 每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着一个条件变量。单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待， 直至所等待的资源成为可用的。 线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。 只要发现所需资

85、源R正处于忙碌状态，线程便转为等待状态， 并对mutex执行开锁操作后，等待该资源被释放； 若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。111 下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。 Lock mutex Lock mutex check data structures; mark resource as free; while(resource busy); unlock mutex; wait(condition variable); wakeup(condition variable); mark re

86、source as busy; unlock mutex; 1123. 信号量机制信号量机制 (1) 私用信号量(private samephore)。 当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使它恢复为0(空)， 也不能将它传送给下一个请求它的线程。 113 (2) 公用信号量(public semaphort)。 公用信号量是为实现不同

87、进程间或不同进程中各线程之间的同步而设置的。由于它有着一个公开的名字供所有的进程使用，故而把它称为公用信号量。其数据结构是存放在受保护的系统存储区中，由OS为它分配空间并进行管理，故也称为系统信号量。如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收，并通知下一进程。可见，公用信号量是一种比较安全的同步机制。 1142.7.3 内核支持内核支持线程和用程和用户级线程程 1. 内核支持内核支持线程程 这里所谓的内核支持线程，也都同样是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。此外，在内核空间还为每

88、一个内核支持线程设置了一个线程控制块， 内核是根据该控制块而感知某线程的存在的，并对其加以控制。 115 2. 用用户级线程程 用户级线程仅存在于用户空间中。对于这种线程的创建、 撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单，因而使线程的切换速度特别快。可见，这种线程是与内核无关的。1162.7.4 线程控制程控制 1. 内核支持内核支持线程的程的实现 图 2 - 13 任务数据区空间 PTDA 进程资源TCB # 1TCB # 2TCB # 31

89、172. 用用户级线程的程的实现 1) 运行时系统(Runtime System) 所谓“运行时系统”，实质上是是用用于于管管理理和和控控制制线程程的的函函数数(过程程)的的集集合合， 其中包括用于创建和撤消线程的函数、 线程同步和通信的函数以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。 118 2) 内核控制线程 这 种 线 程 又 称 为 轻 型 进 程 LWP(Light Weight Process)。 每一个进程都可拥有多个LWP， 同用户级线程一样， 每个LWP都有自己的数据结构(如TCB)，其中包括线程标识符、优先级、 状态， 另外还有栈和局部存储区等。 它们也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务，这样，当一个用户级线程运行时，只要将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。 119图 2 - 14 利用轻型进程作为中间系统 120