第二章 进 程 管 理
第二章 进程管理
2.1 进程的基本概念
2.2 进程控制
2.3 进程同步
2.4 经典进程的同步问题
2.5 管程机制
2.6 进程通信
2.7 线程
第二章 进 程 管 理
2.1 进程的基本概念
2.1.1 程序的顺序执行及其特征
1,程序的顺序执行
仅当前一操作 (程序段 )执行完后, 才能执行后继操作 。
例如, 在进行计算时, 总须先输入用户的程序和数据, 然后
进行计算, 最后才能打印计算结果 。
S1,a ∶ =x+y;
S2,b ∶ =a-5;
S3,c ∶ =b+1;
第二章 进 程 管 理
图 2-1 程序的顺序执行
( a ) 程序的顺序执行 ( b ) 三条语句的顺序执行
I 1 C 1 P 1 I 2 C 2 P 2 S 1 S 2 S 3
第二章 进 程 管 理
2,程序顺序执行时的特征
(1) 顺序性：
(2) 封闭性：
(3) 可再现性：
第二章 进 程 管 理
2.1.2 前趋图
前趋图 (Precedence Graph)是一个有向无循环图, 记为
DAG(Directed Acyclic Graph),用于描述进程之间执行的前后
关系 。 图中的每个结点可用于描述一个程序段或进程, 乃至
一条语句；结点间的有向边则用于表示两个结点之间存在的
偏序 (Partial Order)或前趋关系 (Precedence Relation)“→,。
→ ={(Pi,Pj)|Pi must complete before Pj may start},如果 (Pi,
Pj)∈ →,可写成 Pi→P j,称 Pi是 Pj的直接前趋, 而称 Pj是 Pi的直
接后继 。 在前趋图中, 把没有前趋的结点称为初始结点
(Initial Node),把没有后继的结点称为终止结点 (Final Node)。
第二章 进 程 管 理
每个结点还具有一个重量 (Weight),用于表示该结点所
含有的程序量或结点的执行时间 。
Ii→C i→P i和 S1→S 2→S 3
图 2-2 前趋图
P
1
P
3
P
8
P
9
P
4
P
2
P
5
P
6
P
7
S
1
S
2
S
3
( a ) 具有九个结点的前趋图 ( b ) 具有循环的前趋图
第二章 进 程 管 理
对于图 2-2(a)所示的前趋图,存在下述前趋关系：
P1→P 2,P1→P 3,P1→P 4,P2→P 5,P3→P 5,P4→P 6,P4→P 7,
P5→P 8,P6→P 8,P7→P 9,P8→P 9
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)中却有着
S2→S 3,S3→S 2
第二章 进 程 管 理
2.1.3 程序的并发执行及其特征
1,程序的并发执行
图 2-3 并发执行时的前趋图
P
1
P
2
P
3
P
4
I
1
I
2
I
3
I
4
C
1
C
2
C
3
C
4
第二章 进 程 管 理
Ii→C i,Ii→I i+1,Ci→P i,Ci→C i+1,Pi→P i+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 四条语句的前趋关系
S
1
S
2
S
3
S
4
第二章 进 程 管 理
2,程序并发执行时的特征
1) 间断性
2) 失去封闭性
3) 不可再现性
例如, 有两个循环程序 A和 B,它们共享一个变量 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。
第二章 进 程 管 理
2.1.4 进程的特征与状态
1,进程的特征和定义
1) 结构特征
2) 动态性
3) 并发性
4)
5) 异步性
第二章 进 程 管 理
(1) 进程是程序的一次执行 。
(2) 进程是一个程序及其数据在处理机上顺序执行时所
发生的活动 。
(3) 进程是程序在一个数据集合上运行的过程, 它是系
统进行资源分配和调度的一个独立单位 。
在引入了进程实体的概念后, 我们可以把传统 OS中的
进程定义为：, 进程是进程实体的运行过程, 是系统进行
资源分配和调度的一个独立单位, 。
第二章 进 程 管 理
2,进程的三种基本状态
1) 就绪 (Ready)状态
2)
3) 阻塞状态
第二章 进 程 管 理
图 2-5 进程的三种基本状态及其转换
就绪
阻塞 执行
时间片完
进程调度I / O 完成
I / O 请求
第二章 进 程 管 理
3.
1) 引入挂起状态的原因
(1) 终端用户的请求。
(2) 父进程请求。
(3) 负荷调节的需要。
(4) 操作系统的需要。
第二章 进 程 管 理
2) 进程状态的转换
(1) 活动就绪 → 静止就绪。
(2) 活动阻塞 → 静止阻塞。
(3) 静止就绪 → 活动就绪。
(4) 静止阻塞 → 活动阻塞。
第二章 进 程 管 理
图 2-6 具有挂起状态的进程状态图
活动
就绪
静止
就绪
执行
挂起
激活
释放
挂起
活动
阻塞
静止
阻塞
挂起
激活
释放
请求
I
/
O
第二章 进 程 管 理
2.1.5 进程控制块
1,进程控制块的作用
进程控制块的作用是使一个在多道程序环境下不能
独立运行的程序 (含数据 ),成为一个能独立运行的基本单
位, 一个能与其它进程并发执行的进程 。 或者说, OS是
根据 PCB来对并发执行的进程进行控制和管理的 。
第二章 进 程 管 理
2,进程控制块中的信息
1)
进程标识符用于惟一地标识一个进程 。 一个进程通常
(1) 内部标识符 。 在所有的操作系统中, 都为每一个进
程赋予一个惟一的数字标识符, 它通常是一个进程的序号 。
设置内部标识符主要是为了方便系统使用 。
(2) 外部标识符 。 它由创建者提供, 通常是由字母, 数
字组成, 往往是由用户 (进程 )在访问该进程时使用 。 为了
描述进程的家族关系, 还应设置父进程标识及子进程标识 。
此外, 还可设置用户标识, 以指示拥有该进程的用户 。
第二章 进 程 管 理
2)
处理机状态信息主要是由处理机的各种寄存器中的内容
组成的 。 ① 通用寄存器, 又称为用户可视寄存器, 它们是
用户程序可以访问的, 用于暂存信息, 在大多数处理机中,
有 8~32 个通用寄存器, 在 RISC结构的计算机中可超过 100
个； ② 指令计数器, 其中存放了要访问的下一条指令的地
址； ③ 程序状态字 PSW,其中含有状态信息, 如条件码,
执行方式, 中断屏蔽标志等； ④ 用户栈指针, 指每个用户
进程都有一个或若干个与之相关的系统栈, 用于存放过程和
系统调用参数及调用地址 。 栈指针指向该栈的栈顶 。
第二章 进 程 管 理
3)
在 PCB中还存放一些与进程调度和进程对换有关的信
息, 包括,① 进程状态, 指明进程的当前状态, 作为进
程调度和对换时的依据； ② 进程优先级, 用于描述进程使
用处理机的优先级别的一个整数, 优先级高的进程应优先
获得处理机； ③ 进程调度所需的其它信息, 它们与所采
用的进程调度算法有关, 比如, 进程已等待 CPU的时间总
和, 进程已执行的时间总和等； ④ 事件, 是指进程由执
行状态转变为阻塞状态所等待发生的事件, 即阻塞原因 。
第二章 进 程 管 理
4)
进程控制信息包括,① 程序和数据的地址, 是指进
程的程序和数据所在的内存或外存地 (首 )址, 以便再调度
到该进程执行时, 能从 PCB中找到其程序和数据； ② 进程
同步和通信机制, 指实现进程同步和进程通信时必需的机
制, 如消息队列指针, 信号量等, 它们可能全部或部分地
放在 PCB中； ③ 资源清单, 是一张列出了除 CPU以外的,
进程所需的全部资源及已经分配到该进程的资源的清单；
④ 链接指针, 它给出了本进程 (PCB)所在队列中的下一个
进程的 PCB的首地址 。
第二章 进 程 管 理
3,进程控制块的组织方式
1) 链接方式
图 2-7 PCB链接队列示意图
P C B 1 4
P C B 2
P C B 3
P C B 4
P C B 5
P C B 6
P C B 7
P C B 8
P C B 9
3
0
8
7
9
0
1
执行指针
就绪队列指针
阻塞队列指针
空闲队列指针
…
第二章 进 程 管 理
2) 索引方式
图 2-8 按索引方式组织 PCB
执行指针
就绪索引表
P C B 1
P C B 2
P C B 3
P C B 4
P C B 5
P C B 6
P C B 7
阻塞索引表
就绪表指针
阻塞表指针
第二章 进 程 管 理
2.2 进 程 控 制
2.2.1 进程的创建
1,进程图 (Process Graph)
图 2-9 进程树
D E F G H
B C
I J K L M
A
第二章 进 程 管 理
2,引起创建进程的事件
(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
第二章 进 程 管 理
3,进程的创建 (Creation of Progress)
(1)申请空白 PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列，如果进程就绪队列能够
接纳新进程,便将新进程插入就绪队列。
第二章 进 程 管 理
2.2.2 进程的终止
1,引起进程终止 (Termination of Process)
1)
在任何计算机系统中, 都应有一个用于表示进程已经
运行完成的指示 。 例如, 在批处理系统中, 通常在程序的
最后安排一条 Holt指令或终止的系统调用 。 当程序运行到
Holt指令时, 将产生一个中断, 去通知 OS本进程已经完成 。
在分时系统中, 用户可利用 Logs off去表示进程运行完毕,
此时同样可产生一个中断, 去通知 OS进程已运行完毕 。
第二章 进 程 管 理
2)
在进程运行期间, 由于出现某些错误和故障而迫使进程
终止 。 这类异常事件很多, 常见的有,① 越界错误 。 这是指
程序所访问的存储区, 已越出该进程的区域； ② 保护错 。 进
程试图去访问一个不允许访问的资源或文件, 或者以不适当
的方式进行访问, 例如, 进程试图去写一个只读文件； ③ 非
法指令 。 程序试图去执行一条不存在的指令 。 出现该错误的
原因, 可能是程序错误地转移到数据区, 把数据当成了指令；
④ 特权指令错 。 用户进程试图去执行一条只允许 OS执行的指
令； ⑤ 运行超时 。 进程的执行时间超过了指定的最大值；
⑥ 等待超时 。 进程等待某事件的时间, 超过了规定的最大值；
⑦ 算术运算错 。 进程试图去执行一个被禁止的运算, 例如,
被 0除； ⑧ I/O故障 。 这是指在 I/O过程中发生了错误等 。
第二章 进 程 管 理
3)
外界干预并非指在本进程运行中出现了异常事件,
而是指进程应外界的请求而终止运行 。 这些干预有,①
操作员或操作系统干预 。 由于某种原因, 例如, 发生了
死锁, 由操作员或操作系统终止该进程； ② 父进程请
求 。 由于父进程具有终止自己的任何子孙进程的权利,
因而当父进程提出请求时, 系统将终止该进程； ③ 父进
程终止 。 当父进程终止时, OS也将他的所有子孙进程终
止 。
第二章 进 程 管 理
2.
(1) 根据被终止进程的标识符, 从 PCB集合中检索出该
进程的 PCB,从中读出该进程的状态 。
(2) 若被终止进程正处于执行状态, 应立即终止该进程
的执行, 并置调度标志为真, 用于指示该进程被终止后应
重新进行调度 。
(3) 若该进程还有子孙进程, 还应将其所有子孙进程予
以终止, 以防他们成为不可控的进程 。
(4) 将被终止进程所拥有的全部资源, 或者归还给其父
进程, 或者归还给系统 。
(5) 将被终止进程 (它的 PCB)从所在队列 (或链表 )中移出，
等待其他程序来搜集信息。
第二章 进 程 管 理
2.2.3 进程的阻塞与唤醒
1,引起进程阻塞和唤醒的事件
1) 请求系统服务
2) 启动某种操作
3)
4)
第二章 进 程 管 理
2.
正在执行的进程, 当发现上述某事件时, 由于无法继续
执行, 于是进程便通过调用阻塞原语 block把自己阻塞 。 可见,
进程的阻塞是进程自身的一种主动行为 。 进入 block过程后,
由于此时该进程还处于执行状态, 所以应先立即停止执行,
把进程控制块中的现行状态由, 执行, 改为阻塞, 并将 PCB插
入阻塞队列 。 如果系统中设置了因不同事件而阻塞的多个阻
塞队列, 则应将本进程插入到具有相同事件的阻塞 (等待 )队列 。
最后, 转调度程序进行重新调度, 将处理机分配给另一就绪
进程, 并进行切换, 亦即, 保留被阻塞进程的处理机状态 (在
PCB中 ),再按新进程的 PCB中的处理机状态设置 CPU的环境 。
第二章 进 程 管 理
3.
当被阻塞进程所期待的事件出现时, 如 I/O完成或其所
期待的数据已经到达, 则由有关进程 (比如, 用完并释放
了该 I/O设备的进程 )调用唤醒原语 wakeup( ),将等待该事
件的进程唤醒 。 唤醒原语执行的过程是：首先把被阻塞的
进程从等待该事件的阻塞队列中移出, 将其 PCB中的现行
状态由阻塞改为就绪, 然后再将该 PCB插入到就绪队列中 。
第二章 进 程 管 理
2.2.4 进程的挂起与激活
1.
当出现了引起进程挂起的事件时, 比如, 用户进程
请求将自己挂起, 或父进程请求将自己的某个子进程挂
起, 系统将利用挂起原语 suspend( )将指定进程或处于阻
塞状态的进程挂起 。 挂起原语的执行过程是：首先检查
被挂起进程的状态, 若处于活动就绪状态, 便将其改为
静止就绪；对于活动阻塞状态的进程, 则将之改为静止
阻塞 。 为了方便用户或父进程考查该进程的运行情况而
把该进程的 PCB复制到某指定的内存区域 。 最后, 若被
挂起的进程正在执行, 则转向调度程序重新调度 。
第二章 进 程 管 理
2,进程的激活过程
当发生激活进程的事件时, 例如, 父进程或用户进程请
求激活指定进程, 若该进程驻留在外存而内存中已有足够的
空间时, 则可将在外存上处于静止就绪状态的进程换入内存 。
这时, 系统将利用激活原语 active( )将指定进程激活 。 激活
原语先将进程从外存调入内存, 检查该进程的现行状态, 若
是静止就绪, 便将之改为活动就绪；若为静止阻塞便将之改
为活动阻塞 。 假如采用的是抢占调度策略, 则每当有新进程
进入就绪队列时, 应检查是否要进行重新调度, 即由调度程
序将被激活进程与当前进程进行优先级的比较, 如果被激活
进程的优先级更低, 就不必重新调度；否则, 立即剥夺当前
进程的运行, 把处理机分配给刚被激活的进程 。
第二章 进 程 管 理
2.3 进 程 同 步
2.3.1 进程同步的基本概念
1,两种形式的制约关系
(1) 间接相互制约关系。
(2) 直接相互制约关系。
第二章 进 程 管 理
2,临界资源 (Critical Resouce)
生产者 -消费者 (producer-consumer)问题是一个著名的进
程同步问题 。 它描述的是：有一群生产者进程在生产产品,
并将这些产品提供给消费者进程去消费 。 为使生产者进程与
消费者进程能并发执行, 在两者之间设置了一个具有 n个缓
冲区的缓冲池, 生产者进程将它所生产的产品放入一个缓冲
区中； 消费者进程可从一个缓冲区中取走产品去消费 。 尽
管所有的生产者进程和消费者进程都是以异步方式运行的,
但它们之间必须保持同步, 即不允许消费者进程到一个空缓
冲区去取产品；也不允许生产者进程向一个已装满产品且尚
未被取走的缓冲区中投放产品 。
第二章 进 程 管 理
我们可利用一个数组来表示上述的具有 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则表
示缓冲池空 。 此外, 还引入了一个整型变量 counter,其初始
值为 0。 每当生产者进程向缓冲池中投放一个产品后, 使
counter加 1；反之, 每当消费者进程从中取走一个产品时,
使 counter减 1。 生产者和消费者两进程共享下面的变量：
第二章 进 程 管 理
Var n,integer;
type item=…;
var buffer:array［ 0,1,…,n-1］ of item;
in,out,0,1,…,n-1;
counter:0,1,…,n;
指针 in和 out初始化为 1。 在生产者和消费者进程的描述
中, no-op是一条空操作指令, while condition do no-op语句
表示重复的测试条件 (condication),重复测试应进行到该条
件变为 false(假 ),即到该条件不成立时为止 。 在生产者进程
中使用一局部变量 nextp,用于暂时存放每次刚生产出来的
产品；而在消费者进程中, 则使用一个局部变量 nextc,用于
存放每次要消费的产品 。
第二章 进 程 管 理
producer,repeat
…
produce an item in nextp;
…
while counter=n do no-op;
buffer［ in ∶ = nextp;
in ∶ = in+1 mod n;
counter ∶ = counter+1;
until false;
consumer,repeat
while counter=0 do no-op;
nextc ∶ = buffer［ out］ ;
out ∶ = (out+1) mod n;
counter ∶ = counter-1;
consumer the item in nextc;
until false;
第二章 进 程 管 理
虽然上面的生产者程序和消费者程序, 在分别看时都是
正确的, 而且两者在顺序执行时其结果也会是正确的, 但若
并发执行时, 就会出现差错, 问题就在于这两个进程共享变
量 counter。 生产者对它做加 1操作, 消费者对它做减 1操作,
这两个操作在用机器语言实现时, 常可用下面的形式描述：
register 1 ∶ = counter; register 2∶ = counter;
register1 ∶ = register 1+1; register 2∶ = register 2-1;
counter ∶ = register 1; counter ∶ = register 2;
第二章 进 程 管 理
假设,counter的当前值是 5。 如果生产者进程先执行左列
的三条机器语言语句, 然后消费者进程再执行右列的三条语
句, 则最后共享变量 counter的值仍为 5；反之, 如果让消费者
进程先执行右列的三条语句, 然后再让生产者进程执行左列
的三条语句, counter值也还是 5,但是, 如果按下述顺序执行：
register 1 ∶ = counter; (register 1=5)
register 1 ∶ = register 1+1; (register 1=6)
register 2 ∶ = counter; (register 2=5)
register 2 ∶ = register 2-1; (register 2=4)
counter ∶ = register 1; (counter=6)
counter ∶ = register 2; (counter=4)
第二章 进 程 管 理
3,临界区 (critical section)
repeat
critical section;
remainder section;
until false;
entry section
exit section
第二章 进 程 管 理
4,同步机制应遵循的规则
(1) 空闲让进。
(2) 忙则等待。
(3) 有限等待。
(4) 让权等待。
第二章 进 程 管 理
2.3.2 信号量机制
1.
最初由 Dijkstra把整型信号量定义为一个整型量, 除初
始化外, 仅能通过两个标准的原子操作 (Atomic Operation)
wait(S)和 signal(S)来访问 。 这两个操作一直被分别称为 P,V
操作 。 wait和 signal
wait(S),while S≤0 do no-op
S ∶ =S-1;
signal(S),S ∶ =S+1;
第二章 进 程 管 理
2,记录型信号量
在整型信号量机制中的 wait操作, 只要是信号量 S≤0，
就会不断地测试 。 因此, 该机制并未遵循, 让权等待, 的
准则, 而是使进程处于, 忙等, 的状态 。 记录型信号量机
制, 则是一种不存在, 忙等, 现象的进程同步机制 。 但在
采取了, 让权等待, 的策略后, 又会出现多个进程等待访
问同一临界资源的情况 。 为此, 在信号量机制中, 除了需
要一个用于代表资源数目的整型变量 value外, 还应增加一
个进程链表 L,用于链接上述的所有等待进程 。 记录型信号
量是由于它采用了记录型的数据结构而得名的 。 它所包含
的上述两个数据项可描述为：
第二章 进 程 管 理
type semaphore=record
value:integer;
L:list of process;
end
相应地,wait(S)和 signal(S)
procedure wait(S)
var S,semaphore;
begin
S.value ∶ = S.value-1;
if S.value＜ 0 then block(S,L)
end
procedure signal(S)
var S,semaphore;
begin
S.value ∶ = S.value+1;
if S.value≤0 then wakeup(S,L);
end
第二章 进 程 管 理
在记录型信号量机制中, S.value的初值表示系统中某类
资源的数目, 因而又称为资源信号量, 对它的每次 wait操作,
意味着进程请求一个单位的该类资源, 因此描述为 S.value∶
=S.value-1； 当 S.value＜ 0时, 表示该类资源已分配完毕, 因
此进程应调用 block原语, 进行自我阻塞, 放弃处理机, 并插
入到信号量链表 S.L中 。 可见, 该机制遵循了, 让权等待, 准
则 。 此时 S.value的绝对值表示在该信号量链表中已阻塞进程
的数目 。 对信号量的每次 signal操作, 表示执行进程释放一个
单位资源, 故 S.value∶ =S.value+1操作表示资源数目加 1。
若加 1后仍是 S.value≤0,则表示在该信号量链表中, 仍有等待
该资源的进程被阻塞, 故还应调用 wakeup原语, 将 S.L链表中
的第一个等待进程唤醒 。 如果 S.value的初值为 1,表示只允许
一个进程访问临界资源, 此时的信号量转化为互斥信号量 。
第二章 进 程 管 理
3,AND型信号量
在两个进程中都要包含两个对 Dmutex和 Emutex的操作, 即
process A,process B:
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);
若进程 A和 B按下述次序交替执行 wait
process A,wait(Dmutex); 于是 Dmutex=0
process B,wait(Emutex); 于是 Emutex=0
process A,wait(Emutex); 于是 Emutex=-1 A
process B,wait(Dmutex); 于是 Dmutex=-1 B阻塞
第二章 进 程 管 理
AND同步机制的基本思想是：将进程在整个运行过程
中需要的所有资源, 一次性全部地分配给进程, 待进程使
用完后再一起释放 。 只要尚有一个资源未能分配给进程,
其它所有可能为之分配的资源, 也不分配给他 。 亦即, 对
若干个临界资源的分配, 采取原子操作方式：要么全部分
配到进程, 要么一个也不分配 。 由死锁理论可知, 这样就
可避免上述死锁情况的发生 。 为此, 在 wait操作中, 增加
了一个, AND”条件, 故称为 AND同步, 或称为同时 wait
操作, 即 Swait(Simultaneous wait)定义如下：
第二章 进 程 管 理
Swait(S1,S2,…,Sn)
if Si≥1 and … and Sn≥1 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 Si＜ 1,and set the program count of this process to the beginning of
Swait operation
endif
Ssignal(S 1,S 2,…,S n)
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;
第二章 进 程 管 理
4,信号量集
Swait(S1,t1,d1,…,Sn,tn,dn)
if Si≥t1 and … and Sn≥tn then
for i∶ =1 to n do
Si∶ =Si-di;
endfor
else
Place the executing process in the waiting queue of the first Si with Si＜ ti 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 Si into the ready
queue
endfor;
第二章 进 程 管 理
一般, 信号量集,
(1) Swait(S,d,d)。 此时在信号量集中只有一个信号量 S，
但允许它每次申请 d个资源, 当现有资源数少于 d时, 不予
分配 。
(2) Swait(S,1,1)。 此时的信号量集已蜕化为一般的记
录型信号量 (S＞ 1时 )或互斥信号量 (S=1时 )。
(3) Swait(S,1,0)。 这是一种很特殊且很有用的信号量
操作 。 当 S≥1时, 允许多个进程进入某特定区；当 S变为 0后,
将阻止任何进程进入特定区 。 换言之, 它相当于一个可控
开关 。
第二章 进 程 管 理
2.3.3 信号量的应用
1,利用信号量实现进程互斥
Var mutex:semaphore ∶ = 1;
begin
parbegin
process 1,begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder seetion
until false;
第二章 进 程 管 理
end
process 2,begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder section
until false;
end
parend
第二章 进 程 管 理
2,利用信号量实现前趋关系
图 2-10 前趋图举例
S
4
S
5
S
3
S
1
S
6
S
2
第二章 进 程 管 理
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 wait(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
第二章 进 程 管 理
2.4 经典进程的同步问题
2.4.1 生产者 —
前面我们已经对生产者 —消费者问题 (The proceducer-
consumer problem)做了一些描述, 但未考虑进程的互斥与
同步问题, 因而造成了数据 Counter的不定性 。 由于生产
者 —消费者问题是相互合作的进程关系的一种抽象, 例如,
在输入时, 输入进程是生产者, 计算进程是消费者；而
在输出时, 则计算进程是生产者, 而打印进程是消费者,
因此, 该问题有很大的代表性及实用价值 。
第二章 进 程 管 理
1,利用记录型信号量解决生产者 —消费者问题
假定在生产者和消费者之间的公用缓冲池中, 具有 n
个缓冲区, 这时可利用互斥信号量 mutex实现诸进程对缓
冲池的互斥使用；利用信号量 empty和 full分别表示缓冲池
中空缓冲区和满缓冲区的数量 。 又假定这些生产者和消
费者相互等效, 只要缓冲池未满, 生产者便可将消息送
入缓冲池；只要缓冲池未空, 消费者便可从缓冲池中取
走一个消息 。 对生产者 — 消费者问题可描述如下：
第二章 进 程 管 理
Var mutex,empty,full:semaphore ∶ = 1,n,0;
buffer:array［ 0,…,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
第二章 进 程 管 理
consumer:begin
repeat
wait(full);
wait(mutex);
nextc ∶ = buffer(out);
out ∶ = (out+1) mod n;
signal(mutex);
signal(empty);
consumer the item in nextc;
until false;
end
parend
end
第二章 进 程 管 理
在生产者 —消费者问题中应注意：首先, 在每个程序
中用于实现互斥的 wait(mutex)和 signal(mutex)必须成对地
出现； 其次, 对资源信号量 empty和 full的 wait和 signal操
作, 同样需要成对地出现, 但它们分别处于不同的程序
中 。 例如, wait(empty)在计算进程中, 而 signal(empty)则
在打印进程中, 计算进程若因执行 wait(empty)而阻塞,
则以后将由打印进程将它唤醒；最后, 在每个程序中的
多个 wait操作顺序不能颠倒 。 应先执行对资源信号量的
wait操作, 然后再执行对互斥信号量的 wait操作, 否则可
能引起进程死锁 。
第二章 进 程 管 理
2,利用 AND信号量解决生产者 — 消费者问题
ar mutex,empty,full:semaphore ∶ = 1,n,0;
buffer:array［ 0,…,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+1) mod n;
Ssignal(mutex,empty);
consumer the item in nextc;
until false;
end
parend
end
第二章 进 程 管 理
2.4.2 哲学家进餐问题
1.
经分析可知, 放在桌子上的筷子是临界资源, 在一段时
间内只允许一位哲学家使用 。 为了实现对筷子的互斥使用,
可以用一个信号量表示一只筷子, 由这五个信号量构成信号
量数组 。
Var chopstick,array［ 0,…,4］ of semaphore;
第二章 进 程 管 理
所有信号量均被初始化为 1,第 i位哲学家的活动可描述为：
repeat
wait(chopstick［ i］ );
wait(chopstick［ (i+1) mod 5］ );
…
eat;
…
signal(chopstick［ i］ );
signal(chopstick［ (i+1) mod 5］ );
…
think;
until false;
第二章 进 程 管 理
(1) 至多只允许有四位哲学家同时去拿左边的筷子,
最终能保证至少有一位哲学家能够进餐, 并在用毕时能释
放出他用过的两只筷子, 从而使更多的哲学家能够进餐 。
(2) 仅当哲学家的左, 右两只筷子均可用时, 才允许
他拿起筷子进餐 。
(3) 规定奇数号哲学家先拿他左边的筷子, 然后再去
拿右边的筷子；而偶数号哲学家则相反 。 按此规定, 将是
1,2号哲学家竞争 1号筷子； 3,4号哲学家竞争 3号筷子 。
即五位哲学家都先竞争奇数号筷子, 获得后, 再去竞争偶
数号筷子, 最后总会有一位哲学家能获得两只筷子而进餐 。
第二章 进 程 管 理
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;
Ssignat(chopstick ［ (i+1) mod 5］,chopstick ［ i］ );
until false;
第二章 进 程 管 理
2.4.3 读者 -写者问题
1,利用记录型信号量解决读者 -写者问题
为实现 Reader与 Writer进程间在读或写时的互斥而设置了
一个互斥信号量 Wmutex。 另外, 再设置一个整型变量
Readcount表示正在读的进程数目 。 由于只要有一个 Reader进
程在读, 便不允许 Writer进程去写 。 因此, 仅当 Readcount=0,
表示尚无 Reader 进程在读时, Reader 进 程 才 需 要 执 行
Wait(Wmutex)操作 。 若 wait(Wmutex)操作成功, Reader进程便
可去读, 相应地, 做 Readcount+1操作 。 同理, 仅当 Reader进
程在执行了 Readcount 减 1操作后其值为 0时, 才须执行
signal(Wmutex)操作, 以便让 Writer进程写 。 又因为 Readcount
是一个可被多个 Reader进程访问的临界资源, 因此, 应该为
它设置一个互斥信号量 rmutex。
第二章 进 程 管 理
读者 -
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(rmutex);
until false;
end
writer:begin
repeat
wait(wmutex);
perform write operation;
signal(wmutex);
until false;
end
parend
end
第二章 进 程 管 理
2,利用信号量集机制解决读者 -写者问题
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
第二章 进 程 管 理
2.5 管 程 机 制
2.5.1 管程的基本概念
1,管程的定义
管程由三部分组成,① 局部于管程的共享变量说明；
② 对该数据结构进行操作的一组过程； ③ 对局部于管程
的数据设置初始值的语句 。 此外, 还须为管程赋予一个
名字 。
第二章 进 程 管 理
图 2-11 管程的示意图
共享数据
?
一组操作过程
初始化代码
进入队列
条件( 不忙) 队列
第二章 进 程 管 理
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
第二章 进 程 管 理
2,条件变量
管程中对每个条件变量, 都须予以说明, 其形式为,Var
x,y:condition。 该变量应置于 wait和 signal之前, 即可表示为
X.wait和 X.signal。 例如, 由于共享数据被占用而使调用进程
等待, 该条件变量的形式为,nonbusy:condition。 此时,
wait 原 语 应 改 为 nonbusy.wait, 相 应 地, signal 应改为
nonbusy.signal。
应当指出, X.signal操作的作用, 是重新启动一个被阻塞
的进程, 但如果没有被阻塞的进程, 则 X.signal操作不产生任
何后果 。 这与信号量机制中的 signal操作不同 。 因为, 后者总
是要执行 s∶ =s+1操作, 因而总会改变信号量的状态 。
第二章 进 程 管 理
如果有进程 Q处于阻塞状态, 当进程 P执行了 X.signal
操作后, 怎样决定由哪个进行执行, 哪个等待, 可采用
(1) P等待, 直至 Q离开管程或等待另一条件 。
(2) Q等待, 直至 P离开管程或等待另一条件 。
采用哪种处理方式,当然是各执一词。 但是 Hansan
却采用了第一种处理方式。
第二章 进 程 管 理
2.5.2 利用管程解决生产者 -消费者问题
在利用管程方法来解决生产者 -消费者问题时, 首先
便是为它们建立一个管程, 并命名为 Proclucer-Consumer,
或简称为 PC。
(1) put(item)过程 。 生产者利用该过程将自己生产的
产品投放到缓冲池中, 并用整型变量 count来表示在缓冲
池中已有的产品数目, 当 count≥n时, 表示缓冲池已满,
生产者须等待 。
第二章 进 程 管 理
(1) put(item)过程 。 生产者利用该过程将自己生产的产
品投放到缓冲池中, 并用整型变量 count来表示在缓冲池中
已有的产品数目, 当 count≥n时, 表示缓冲池已满, 生产者
须等待 。
(2) get(item)过程 。 消费者利用该过程从缓冲池中取出
一个产品, 当 count≤0时, 表示缓冲池中已无可取用的产品,
消费者应等待 。
第二章 进 程 管 理
type producer-consumer=monitor
Var in,out,count:integer;
buffer:array［ 0,…,n-1］ of item;
notfull,notempty:condition;
procedure entry put(item)
begin
if count≥n then notfull.wait;
buffer(in) ∶ = nextp;
in ∶ = (in+1) mod n;
count ∶ = count+1;
if notempty.queue then notempty.signal;
end
第二章 进 程 管 理
procedure entry get(item)
begin
if count≤0 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
第二章 进 程 管 理
在利用管程解决生产者 -消费者问题时,其中的生
产者和消费者可描述为：
producer:begin
repeat
produce an item in nextp;
PC.put(item);
until false;
end
consumer:begin
repeat
PC.get(item);
consume the item in nextc;
until false;
end
第二章 进 程 管 理
2.6 进 程 通 信
2.6.1 进程通信的类型
1,共享存储器系统 (Shared-Memory System)
(1) 基于共享数据结构的通信方式。
(2) 基于共享存储区的通信方式。
第二章 进 程 管 理
2,消息传递系统 (Message passing system)
不论是单机系统, 多机系统, 还是计算机网络, 消息
传递机制都是用得最广泛的一种进程间通信的机制 。 在消
息传递系统中, 进程间的数据交换, 是以格式化的消息
(message)为单位的；在计算机网络中, 又把 message称为报
文 。 程序员直接利用系统提供的一组通信命令 (原语 )进行
通信 。 操作系统隐藏了通信的实现细节, 大大减化了通信
程序编制的复杂性, 而获得广泛的应用 。 消息传递系统的
通信方式属于高级通信方式 。 又因其实现方式的不同而进
一步分成直接通信方式和间接通信方式两种 。
第二章 进 程 管 理
3,管道 (Pipe)
所谓, 管道,, 是指用于连接一个读进程和一个写
进程以实现他们之间通信的一个共享文件, 又名 pipe文
件 。 向管道 (共享文件 )提供输入的发送进程 (即写进程 )，
以字符流形式将大量的数据送入管道；而接受管道输出
的接收进程 (即读进程 ),则从管道中接收 (读 )数据 。 由于
发送进程和接收进程是利用管道进行通信的, 故又称为
管道通信 。 这种方式首创于 UNIX系统, 由于它能有效地
传送大量数据, 因而又被引入到许多其它操作系统中 。
第二章 进 程 管 理
为了协调双方的通信, 管道机制必须提供以下三方面
的协调能力,① 互斥, 即当一个进程正在对 pipe执行读 /
写操作时, 其它 (另一 )进程必须等待 。 ② 同步, 指当写
(输入 )进程把一定数量 (如 4 KB)的数据写入 pipe,便去睡
眠等待, 直到读 (输出 )进程取走数据后, 再把他唤醒 。 当
读进程读一空 pipe时, 也应睡眠等待, 直至写进程将数据
写入管道后, 才将之唤醒 。 ③ 确定对方是否存在, 只有
确定了对方已存在时, 才能进行通信 。
第二章 进 程 管 理
2.6.2 消息传递通信的实现方法
1.
这是指发送进程利用 OS所提供的发送命令, 直接把消
息发送给目标进程 。 此时, 要求发送进程和接收进程都以
显式方式提供对方的标识符 。 通常, 系统提供下述两条通
信命令 (原语 )
Send(Receiver,message); 发送一个消息给接收进程；
Receive(Sender,message); 接收 Sender
例如, 原语 Send(P2,m1)表示将消息 m1发送给接收进程 P2;
而原语 Receive(P1,m1)则表示接收由 P1发来的消息 m1。
第二章 进 程 管 理
在某些情况下, 接收进程可与多个发送进程通信,
因此, 它不可能事先指定发送进程 。 例如, 用于提供打
印服务的进程, 它可以接收来自任何一个进程的, 打印
请求, 消息 。 对于这样的应用, 在接收进程接收消息的
原语中的源进程参数, 是完成通信后的返回值, 接收原
语可表示为：
Receive (id,message);
第二章 进 程 管 理
我们还可以利用直接通信原语, 来解决生产者 -消费者问题 。
当生产者生产出一个产品 (消息 )后, 便用 Send原语将消息发送
给消费者进程；而消费者进程则利用 Receive原语来得到一个消
息 。 如果消息尚未生产出来, 消费者必须等待, 直至生产者进
程将消息发送过来 。 生产者 -消费者的通信过程可分别描述如下：
repeat
…
produce an item in nextp;
…
send(consumer,nextp);
until false;
repeat
receive(producer,nextc);
…
consume the item in nextc;
until false;
第二章 进 程 管 理
2,间接通信方式
(1) 信箱的创建和撤消 。 进程可利用信箱创建原语来建立
一个新信箱 。 创建者进程应给出信箱名字, 信箱属性 (公用,
私用或共享 )；对于共享信箱, 还应给出共享者的名字 。 当进
程不再需要读信箱时, 可用信箱撤消原语将之撤消 。
(2) 消息的发送和接收 。 当进程之间要利用信箱进行通信
时, 必须使用共享信箱, 并利用系统提供的下述通信原语进
行通信 。
Send(mailbox,message);
Receive(mailbox,message); 从指定信箱中接收一个消息；
第二章 进 程 管 理
信箱可由操作系统创建, 也可由用户进程创建, 创建
者是信箱的拥有者 。 据此, 可把信箱分为以下三类 。
1)
用户进程可为自己建立一个新信箱, 并作为该进程的
一部分 。 信箱的拥有者有权从信箱中读取消息, 其他用户
则只能将自己构成的消息发送到该信箱中 。 这种私用信箱
可采用单向通信链路的信箱来实现 。 当拥有该信箱的进程
结束时, 信箱也随之消失 。
第二章 进 程 管 理
2)
它由操作系统创建, 并提供给系统中的所有核准进程
使用 。 核准进程既可把消息发送到该信箱中, 也可从信箱
中读取发送给自己的消息 。 显然, 公用信箱应采用双向通
信链路的信箱来实现 。 通常, 公用信箱在系统运行期间始
终存在 。
3)
它由某进程创建, 在创建时或创建后, 指明它是可共享
的, 同时须指出共享进程 (用户 )的名字 。 信箱的拥有者和共
享者, 都有权从信箱中取走发送给自己的消息 。
第二章 进 程 管 理
在利用信箱通信时, 在发送进程和接收进程之间, 存在以
(1) 一对一关系 。 这时可为发送进程和接收进程建立一条两
者专用的通信链路, 使两者之间的交互不受其他进程的干扰 。
(2) 多对一关系 。 允许提供服务的进程与多个用户进程之间
进行交互, 也称为客户 /服务器交互 (client/server interaction)。
(3) 一对多关系 。 允许一个发送进程与多个接收进程进行
交互, 使发送进程可用广播方式, 向接收者 (多个 )发送消息 。
(4) 多对多关系 。 允许建立一个公用信箱, 让多个进程都
能向信箱中投递消息；也可从信箱中取走属于自己的消息 。
第二章 进 程 管 理
2.6.3 消息传递系统实现中的若干问题
1,通信链路 (communication link)
为使在发送进程和接收进程之间能进行通信, 必须在两者
之间建立一条通信链路 。 有两种方式建立通信链路 。 第一种方
式是：由发送进程在通信之前, 用显式的, 建立连接, 命令
(原语 )请求系统为之建立一条通信链路；在链路使用完后, 也
用显式方式拆除链路 。
这种方式主要用于计算机网络中 。 第二种方式是发送进程
无须明确提出建立链路的请求, 只须利用系统提供的发送命令
(原语 ),系统会自动地为之建立一条链路 。 这种方式主要用于
单机系统中 。
第二章 进 程 管 理
根据通信链路的连接方法, 又可把通信链路分为两
类,① 点 —点连接通信链路, 这时的一条链路只连接两
个结点 (进程 )； ② 多点连接链路, 指用一条链路连接多
个 (n＞ 2)结点 (进程 )。 而根据通信方式的不同, 则又可把
链路分成两种,① 单向通信链路, 只允许发送进程向
接收进程发送消息； ② 双向链路, 既允许由进程 A向进
程 B发送消息, 也允许进程 B同时向进程 A发送消息 。
第二章 进 程 管 理
2,消息的格式
在某些 OS中, 消息是采用比较短的定长消息格式, 这
减少了对消息的处理和存储开销 。 这种方式可用于办公自
动化系统中, 为用户提供快速的便笺式通信；但这对要发
送较长消息的用户是不方便的 。 在有的 OS中, 采用另一种
变长的消息格式, 即进程所发送消息的长度是可变的 。 系
统在处理和存储变长消息时, 须付出更多的开销, 但方便
了用户 。 这两种消息格式各有其优缺点, 故在很多系统 (包
括计算机网络 )中, 是同时都用的 。
第二章 进 程 管 理
3,进程同步方式
(1) 发送进程阻塞,接收进程阻塞。
(2) 发送进程不阻塞,接收进程阻塞。
(3) 发送进程和接收进程均不阻塞。
第二章 进 程 管 理
2.6.4 消息缓冲队列通信机制
1,消息缓冲队列通信机制中的数据结构
(1) 消息缓冲区 。 在消息缓冲队列通信方式中, 主要利
用的数据结构是消息缓冲区 。
type message buffer=record
sender;
size;
text;
next;
end
第二章 进 程 管 理
(2) PCB中有关通信的数据项 。 在利用消息缓冲队列通
信机制时, 在设置消息缓冲队列的同时, 还应增加用于对
消息队列进行操作和实现同步的信号量, 并将它们置入进
程的 PCB中 。 在 PCB
type processcontrol block=record
…
mq;
mutex;
sm;
…
end
第二章 进 程 管 理
2.
发送进程在利用发送原语发送消息之前, 应先在自己
的内存空间, 设置一发送区 a,见图 2 - 12 所示, 把待发送
的消息正文, 发送进程标识符, 消息长度等信息填入其中,
然后调用发送原语, 把消息发送给目标 (接收 )进程 。 发送原
语首先根据发送区 a中所设置的消息长度 a.size来申请一缓冲
区 i,接着, 把发送区 a中的信息复制到缓冲区 i中 。 为了能
将 i挂在接收进程的消息队列 mq上, 应先获得接收进程的内
部标识符 j,然后将 i挂在 j.mq上 。 由于该队列属于临界资源,
故在执行 insert操作的前后, 都要执行 wait和 signal操作 。
第二章 进 程 管 理
图 2 - 12 消息缓冲通信
s e n d e r, A
s i z e, 5
t e x t, H e l l o
mq
m u t e x
sm
s e n d e r, A
s i z e, 5
t e x t, H e l l o
n e x t, 0
s e n d ( B,a )
第一消息缓冲区
s e n d e r, A
s i z e, 5
t e x t, H e l l o
r e c e i v e ( b )
a
发
送
区
a
b
接
收
区
b
进程 BP C B ( B )进程 A
第二章 进 程 管 理
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 set,receiver.j); 获得接收进程内部标识符；
wait(j.mutex);
insert(j.mq,i);
signal(j.mutex);
signal(j.sm);
end
第二章 进 程 管 理
3,接收原语
procedurereceive(b)
begin
j ∶ = internal name; j
wait(j.sm);
wait(j.mutex);
remove(j.mq,i);
signal(j.mutex);
b.sender ∶ = i.sender; 将消息缓冲区 i中的信息复制到接收区 b;
b.size ∶ = i.size;
b.text ∶ = i.text;
end
第二章 进 程 管 理
2.7 线 程
2.7.1 线程的基本概念
为使程序能并发执行, 系统还必须进行以下的一系列
操作 。
1) 创建进程
2) 撤消进程
3)
第二章 进 程 管 理
2,线程的属性
(1) 轻型实体。
(2) 独立调度和分派的基本单位。
(3) 可并发执行。
(4) 共享进程资源。
第二章 进 程 管 理
3.
(1) 状态参数 。
在 OS中的每一个线程都可以利用线程标识符和一组状
态参数进行描述 。 状态参数通常有这样几项,① 寄存器状
态, 它包括程序计数器 PC和堆栈指针中的内容； ② 堆栈,
在堆栈中通常保存有局部变量和返回地址； ③ 线程运行状
态, 用于描述线程正处于何种运行状态； ④ 优先级, 描
述线程执行的优先程度； ⑤ 线程专有存储器, 用于保存
线程自己的局部变量拷贝； ⑥ 信号屏蔽, 即对某些信号
加以屏蔽 。
第二章 进 程 管 理
(2) 线程运行状态 。
如同传统的进程一样, 在各线程之间也存在着共享资
源和相互合作的制约关系, 致使线程在运行时也具有间断
性 。 相应地, 线程在运行时, 也具有下述三种基本状态：
① 执行状态, 表示线程正获得处理机而运行； ② 就绪状态,
指线程已具备了各种执行条件, 一旦获得 CPU便可执行的
状态； ③ 阻塞状态, 指线程在执行中因某事件而受阻, 处
于暂停执行时的状态 。
第二章 进 程 管 理
4.
在多线程 OS环境下, 应用程序在启动时, 通常仅有一
个线程在执行, 该线程被人们称为, 初始化线程, 。 它可
根据需要再去创建若干个线程 。 在创建新线程时, 需要利
用一个线程创建函数 (或系统调用 ),并提供相应的参数, 如
指向线程主程序的入口指针, 堆栈的大小, 以及用于调度
的优先级等 。 在线程创建函数执行完后, 将返回一个线程
标识符供以后使用 。
终止线程的方式有两种：一种是在线程完成了自己的
工作后自愿退出；另一种是线程在运行中出现错误或由于
某种原因而被其它线程强行终止 。
第二章 进 程 管 理
5,多线程 OS中的进程
在多线程 OS中, 进程是作为拥有系统资源的基本单位,
通常的进程都包含多个线程并为它们提供资源, 但此时的进
程就不再作为一个执行的实体 。 多线程 OS中的进程有以下
属性：
(1) 作为系统资源分配的单位。
(2) 可包括多个线程。
(3) 进程不是一个可执行的实体。
第二章 进 程 管 理
2.7.2 线程间的同步和通信
1,互斥锁 (mutex)
互斥锁是一种比较简单的, 用于实现进程间对资源互
斥访问的机制 。 由于操作互斥锁的时间和空间开锁都较低,
因而较适合于高频度使用的关键共享数据和程序段 。 互斥
锁可以有两种状态, 即开锁 (unlock)和关锁 (lock)状态 。
相应地, 可用两条命令 (函数 )对互斥锁进行操作 。 其中的
关锁 lock操作用于将 mutex关上, 开锁操作 unlock则用于打
开 mutex。
第二章 进 程 管 理
2,条件变量
每一个条件变量通常都与一个互斥锁一起使用, 亦即,
在创建一个互斥锁时便联系着一个条件变量 。 单纯的互斥锁
用于短期锁定, 主要是用来保证对临界区的互斥进入 。 而条
件变量则用于线程的长期等待, 直至所等待的资源成为可
用的 。
线程首先对 mutex执行关锁操作, 若成功便进入临界区,
然后查找用于描述资源状态的数据结构, 以了解资源的情况 。
只要发现所需资源 R正处于忙碌状态, 线程便转为等待状态,
并对 mutex执行开锁操作后, 等待该资源被释放； 若资源处
于空闲状态, 表明线程可以使用该资源, 于是将该资源设置
为忙碌状态, 再对 mutex执行开锁操作 。
第二章 进 程 管 理
下面给出了对上述资源的申请 (左半部分 )和释放 (右半
部分 )操作的描述 。
Lock mutex Lock mutex
check data structures; mark resource as free;
while(resource busy); unlock mutex;
wait(condition variable); wakeup(condition variable);
mark resource as busy;
unlock mutex;
第二章 进 程 管 理
3,信号量机制
(1) 私用信号量 (private samephore)。
当某线程需利用信号量来实现同一进程中各线程之间的
同步时, 可调用创建信号量的命令来创建一私用信号量, 其
数据结构是存放在应用程序的地址空间中 。 私用信号量属于
特定的进程所有, OS并不知道私用信号量的存在, 因此, 一
旦发生私用信号量的占用者异常结束或正常结束, 但并未释
放该信号量所占有空间的情况时, 系统将无法使它恢复为
0(空 ),也不能将它传送给下一个请求它的线程 。
第二章 进 程 管 理
(2) 公用信号量 (public semaphort)。
公用信号量是为实现不同进程间或不同进程中各线程
之间的同步而设置的 。 由于它有着一个公开的名字供所有
的进程使用, 故而把它称为公用信号量 。 其数据结构是存
放在受保护的系统存储区中, 由 OS为它分配空间并进行管
理, 故也称为系统信号量 。 如果信号量的占有者在结束时
未释放该公用信号量, 则 OS会自动将该信号量空间回收,
并通知下一进程 。 可见, 公用信号量是一种比较安全的同
步机制 。
第二章 进 程 管 理
2.7.3 内核支持线程和用户级线程
1,内核支持线程
这里所谓的内核支持线程, 也都同样是在内核的支
持下运行的, 即无论是用户进程中的线程, 还是系统进
程中的线程, 他们的创建, 撤消和切换等, 也是依靠内
核实现的 。 此外, 在内核空间还为每一个内核支持线程
设置了一个线程控制块, 内核是根据该控制块而感知某
线程的存在的, 并对其加以控制 。
第二章 进 程 管 理
2.
用户级线程仅存在于用户空间中 。 对于这种线程的
创建, 撤消, 线程之间的同步与通信等功能, 都无须利
用系统调用来实现 。 对于用户级线程的切换, 通常是发
生在一个应用进程的诸多线程之间, 这时, 也同样无须
内核的支持 。 由于切换的规则远比进程调度和切换的规
则简单, 因而使线程的切换速度特别快 。 可见, 这种线
程是与内核无关的 。
第二章 进 程 管 理
2.7.4 线程控制
1,内核支持线程的实现
图 2 - 13 任务数据区空间
PTDA 进程资源
TCB # 1
TCB # 2
TCB # 3
第二章 进 程 管 理
2,用户级线程的实现
1) 运行时系统 (Runtime System)
所谓, 运行时系统,, 实质上是用于管理和控制线程
的函数 (过程 )的集合, 其中包括用于创建和撤消线程的函
数, 线程同步和通信的函数以及实现线程调度的函数等 。
正因为有这些函数, 才能使用户级线程与内核无关 。 运行
时系统中的所有函数都驻留在用户空间, 并作为用户级线
程与内核之间的接口 。
第二章 进 程 管 理
2)
这种线程又称为轻型进程 LWP(Light Weight
Process)。 每一个进程都可拥有多个 LWP,同用户级
线程一样, 每个 LWP都有自己的数据结构 (如 TCB),其
中包括线程标识符, 优先级, 状态, 另外还有栈和局
部存储区等 。 它们也可以共享进程所拥有的资源 。
LWP可通过系统调用来获得内核提供的服务, 这样,
当一个用户级线程运行时, 只要将它连接到一个 LWP
上, 此时它便具有了内核支持线程的所有属性 。
第二章 进 程 管 理
图 2 - 14 利用轻型进程作为中间系统
用户级线程
轻型进程
内 核
C P U
任务 1 任务 2 任务 3
内核线程
第二章 进程管理
2.1 进程的基本概念
2.2 进程控制
2.3 进程同步
2.4 经典进程的同步问题
2.5 管程机制
2.6 进程通信
2.7 线程
第二章 进 程 管 理
2.1 进程的基本概念
2.1.1 程序的顺序执行及其特征
1,程序的顺序执行
仅当前一操作 (程序段 )执行完后, 才能执行后继操作 。
例如, 在进行计算时, 总须先输入用户的程序和数据, 然后
进行计算, 最后才能打印计算结果 。
S1,a ∶ =x+y;
S2,b ∶ =a-5;
S3,c ∶ =b+1;
第二章 进 程 管 理
图 2-1 程序的顺序执行
( a ) 程序的顺序执行 ( b ) 三条语句的顺序执行
I 1 C 1 P 1 I 2 C 2 P 2 S 1 S 2 S 3
第二章 进 程 管 理
2,程序顺序执行时的特征
(1) 顺序性：
(2) 封闭性：
(3) 可再现性：
第二章 进 程 管 理
2.1.2 前趋图
前趋图 (Precedence Graph)是一个有向无循环图, 记为
DAG(Directed Acyclic Graph),用于描述进程之间执行的前后
关系 。 图中的每个结点可用于描述一个程序段或进程, 乃至
一条语句；结点间的有向边则用于表示两个结点之间存在的
偏序 (Partial Order)或前趋关系 (Precedence Relation)“→,。
→ ={(Pi,Pj)|Pi must complete before Pj may start},如果 (Pi,
Pj)∈ →,可写成 Pi→P j,称 Pi是 Pj的直接前趋, 而称 Pj是 Pi的直
接后继 。 在前趋图中, 把没有前趋的结点称为初始结点
(Initial Node),把没有后继的结点称为终止结点 (Final Node)。
第二章 进 程 管 理
每个结点还具有一个重量 (Weight),用于表示该结点所
含有的程序量或结点的执行时间 。
Ii→C i→P i和 S1→S 2→S 3
图 2-2 前趋图
P
1
P
3
P
8
P
9
P
4
P
2
P
5
P
6
P
7
S
1
S
2
S
3
( a ) 具有九个结点的前趋图 ( b ) 具有循环的前趋图
第二章 进 程 管 理
对于图 2-2(a)所示的前趋图,存在下述前趋关系：
P1→P 2,P1→P 3,P1→P 4,P2→P 5,P3→P 5,P4→P 6,P4→P 7,
P5→P 8,P6→P 8,P7→P 9,P8→P 9
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)中却有着
S2→S 3,S3→S 2
第二章 进 程 管 理
2.1.3 程序的并发执行及其特征
1,程序的并发执行
图 2-3 并发执行时的前趋图
P
1
P
2
P
3
P
4
I
1
I
2
I
3
I
4
C
1
C
2
C
3
C
4
第二章 进 程 管 理
Ii→C i,Ii→I i+1,Ci→P i,Ci→C i+1,Pi→P i+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 四条语句的前趋关系
S
1
S
2
S
3
S
4
第二章 进 程 管 理
2,程序并发执行时的特征
1) 间断性
2) 失去封闭性
3) 不可再现性
例如, 有两个循环程序 A和 B,它们共享一个变量 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。
第二章 进 程 管 理
2.1.4 进程的特征与状态
1,进程的特征和定义
1) 结构特征
2) 动态性
3) 并发性
4)
5) 异步性
第二章 进 程 管 理
(1) 进程是程序的一次执行 。
(2) 进程是一个程序及其数据在处理机上顺序执行时所
发生的活动 。
(3) 进程是程序在一个数据集合上运行的过程, 它是系
统进行资源分配和调度的一个独立单位 。
在引入了进程实体的概念后, 我们可以把传统 OS中的
进程定义为：, 进程是进程实体的运行过程, 是系统进行
资源分配和调度的一个独立单位, 。
第二章 进 程 管 理
2,进程的三种基本状态
1) 就绪 (Ready)状态
2)
3) 阻塞状态
第二章 进 程 管 理
图 2-5 进程的三种基本状态及其转换
就绪
阻塞 执行
时间片完
进程调度I / O 完成
I / O 请求
第二章 进 程 管 理
3.
1) 引入挂起状态的原因
(1) 终端用户的请求。
(2) 父进程请求。
(3) 负荷调节的需要。
(4) 操作系统的需要。
第二章 进 程 管 理
2) 进程状态的转换
(1) 活动就绪 → 静止就绪。
(2) 活动阻塞 → 静止阻塞。
(3) 静止就绪 → 活动就绪。
(4) 静止阻塞 → 活动阻塞。
第二章 进 程 管 理
图 2-6 具有挂起状态的进程状态图
活动
就绪
静止
就绪
执行
挂起
激活
释放
挂起
活动
阻塞
静止
阻塞
挂起
激活
释放
请求
I
/
O
第二章 进 程 管 理
2.1.5 进程控制块
1,进程控制块的作用
进程控制块的作用是使一个在多道程序环境下不能
独立运行的程序 (含数据 ),成为一个能独立运行的基本单
位, 一个能与其它进程并发执行的进程 。 或者说, OS是
根据 PCB来对并发执行的进程进行控制和管理的 。
第二章 进 程 管 理
2,进程控制块中的信息
1)
进程标识符用于惟一地标识一个进程 。 一个进程通常
(1) 内部标识符 。 在所有的操作系统中, 都为每一个进
程赋予一个惟一的数字标识符, 它通常是一个进程的序号 。
设置内部标识符主要是为了方便系统使用 。
(2) 外部标识符 。 它由创建者提供, 通常是由字母, 数
字组成, 往往是由用户 (进程 )在访问该进程时使用 。 为了
描述进程的家族关系, 还应设置父进程标识及子进程标识 。
此外, 还可设置用户标识, 以指示拥有该进程的用户 。
第二章 进 程 管 理
2)
处理机状态信息主要是由处理机的各种寄存器中的内容
组成的 。 ① 通用寄存器, 又称为用户可视寄存器, 它们是
用户程序可以访问的, 用于暂存信息, 在大多数处理机中,
有 8~32 个通用寄存器, 在 RISC结构的计算机中可超过 100
个； ② 指令计数器, 其中存放了要访问的下一条指令的地
址； ③ 程序状态字 PSW,其中含有状态信息, 如条件码,
执行方式, 中断屏蔽标志等； ④ 用户栈指针, 指每个用户
进程都有一个或若干个与之相关的系统栈, 用于存放过程和
系统调用参数及调用地址 。 栈指针指向该栈的栈顶 。
第二章 进 程 管 理
3)
在 PCB中还存放一些与进程调度和进程对换有关的信
息, 包括,① 进程状态, 指明进程的当前状态, 作为进
程调度和对换时的依据； ② 进程优先级, 用于描述进程使
用处理机的优先级别的一个整数, 优先级高的进程应优先
获得处理机； ③ 进程调度所需的其它信息, 它们与所采
用的进程调度算法有关, 比如, 进程已等待 CPU的时间总
和, 进程已执行的时间总和等； ④ 事件, 是指进程由执
行状态转变为阻塞状态所等待发生的事件, 即阻塞原因 。
第二章 进 程 管 理
4)
进程控制信息包括,① 程序和数据的地址, 是指进
程的程序和数据所在的内存或外存地 (首 )址, 以便再调度
到该进程执行时, 能从 PCB中找到其程序和数据； ② 进程
同步和通信机制, 指实现进程同步和进程通信时必需的机
制, 如消息队列指针, 信号量等, 它们可能全部或部分地
放在 PCB中； ③ 资源清单, 是一张列出了除 CPU以外的,
进程所需的全部资源及已经分配到该进程的资源的清单；
④ 链接指针, 它给出了本进程 (PCB)所在队列中的下一个
进程的 PCB的首地址 。
第二章 进 程 管 理
3,进程控制块的组织方式
1) 链接方式
图 2-7 PCB链接队列示意图
P C B 1 4
P C B 2
P C B 3
P C B 4
P C B 5
P C B 6
P C B 7
P C B 8
P C B 9
3
0
8
7
9
0
1
执行指针
就绪队列指针
阻塞队列指针
空闲队列指针
…
第二章 进 程 管 理
2) 索引方式
图 2-8 按索引方式组织 PCB
执行指针
就绪索引表
P C B 1
P C B 2
P C B 3
P C B 4
P C B 5
P C B 6
P C B 7
阻塞索引表
就绪表指针
阻塞表指针
第二章 进 程 管 理
2.2 进 程 控 制
2.2.1 进程的创建
1,进程图 (Process Graph)
图 2-9 进程树
D E F G H
B C
I J K L M
A
第二章 进 程 管 理
2,引起创建进程的事件
(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
第二章 进 程 管 理
3,进程的创建 (Creation of Progress)
(1)申请空白 PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列，如果进程就绪队列能够
接纳新进程,便将新进程插入就绪队列。
第二章 进 程 管 理
2.2.2 进程的终止
1,引起进程终止 (Termination of Process)
1)
在任何计算机系统中, 都应有一个用于表示进程已经
运行完成的指示 。 例如, 在批处理系统中, 通常在程序的
最后安排一条 Holt指令或终止的系统调用 。 当程序运行到
Holt指令时, 将产生一个中断, 去通知 OS本进程已经完成 。
在分时系统中, 用户可利用 Logs off去表示进程运行完毕,
此时同样可产生一个中断, 去通知 OS进程已运行完毕 。
第二章 进 程 管 理
2)
在进程运行期间, 由于出现某些错误和故障而迫使进程
终止 。 这类异常事件很多, 常见的有,① 越界错误 。 这是指
程序所访问的存储区, 已越出该进程的区域； ② 保护错 。 进
程试图去访问一个不允许访问的资源或文件, 或者以不适当
的方式进行访问, 例如, 进程试图去写一个只读文件； ③ 非
法指令 。 程序试图去执行一条不存在的指令 。 出现该错误的
原因, 可能是程序错误地转移到数据区, 把数据当成了指令；
④ 特权指令错 。 用户进程试图去执行一条只允许 OS执行的指
令； ⑤ 运行超时 。 进程的执行时间超过了指定的最大值；
⑥ 等待超时 。 进程等待某事件的时间, 超过了规定的最大值；
⑦ 算术运算错 。 进程试图去执行一个被禁止的运算, 例如,
被 0除； ⑧ I/O故障 。 这是指在 I/O过程中发生了错误等 。
第二章 进 程 管 理
3)
外界干预并非指在本进程运行中出现了异常事件,
而是指进程应外界的请求而终止运行 。 这些干预有,①
操作员或操作系统干预 。 由于某种原因, 例如, 发生了
死锁, 由操作员或操作系统终止该进程； ② 父进程请
求 。 由于父进程具有终止自己的任何子孙进程的权利,
因而当父进程提出请求时, 系统将终止该进程； ③ 父进
程终止 。 当父进程终止时, OS也将他的所有子孙进程终
止 。
第二章 进 程 管 理
2.
(1) 根据被终止进程的标识符, 从 PCB集合中检索出该
进程的 PCB,从中读出该进程的状态 。
(2) 若被终止进程正处于执行状态, 应立即终止该进程
的执行, 并置调度标志为真, 用于指示该进程被终止后应
重新进行调度 。
(3) 若该进程还有子孙进程, 还应将其所有子孙进程予
以终止, 以防他们成为不可控的进程 。
(4) 将被终止进程所拥有的全部资源, 或者归还给其父
进程, 或者归还给系统 。
(5) 将被终止进程 (它的 PCB)从所在队列 (或链表 )中移出，
等待其他程序来搜集信息。
第二章 进 程 管 理
2.2.3 进程的阻塞与唤醒
1,引起进程阻塞和唤醒的事件
1) 请求系统服务
2) 启动某种操作
3)
4)
第二章 进 程 管 理
2.
正在执行的进程, 当发现上述某事件时, 由于无法继续
执行, 于是进程便通过调用阻塞原语 block把自己阻塞 。 可见,
进程的阻塞是进程自身的一种主动行为 。 进入 block过程后,
由于此时该进程还处于执行状态, 所以应先立即停止执行,
把进程控制块中的现行状态由, 执行, 改为阻塞, 并将 PCB插
入阻塞队列 。 如果系统中设置了因不同事件而阻塞的多个阻
塞队列, 则应将本进程插入到具有相同事件的阻塞 (等待 )队列 。
最后, 转调度程序进行重新调度, 将处理机分配给另一就绪
进程, 并进行切换, 亦即, 保留被阻塞进程的处理机状态 (在
PCB中 ),再按新进程的 PCB中的处理机状态设置 CPU的环境 。
第二章 进 程 管 理
3.
当被阻塞进程所期待的事件出现时, 如 I/O完成或其所
期待的数据已经到达, 则由有关进程 (比如, 用完并释放
了该 I/O设备的进程 )调用唤醒原语 wakeup( ),将等待该事
件的进程唤醒 。 唤醒原语执行的过程是：首先把被阻塞的
进程从等待该事件的阻塞队列中移出, 将其 PCB中的现行
状态由阻塞改为就绪, 然后再将该 PCB插入到就绪队列中 。
第二章 进 程 管 理
2.2.4 进程的挂起与激活
1.
当出现了引起进程挂起的事件时, 比如, 用户进程
请求将自己挂起, 或父进程请求将自己的某个子进程挂
起, 系统将利用挂起原语 suspend( )将指定进程或处于阻
塞状态的进程挂起 。 挂起原语的执行过程是：首先检查
被挂起进程的状态, 若处于活动就绪状态, 便将其改为
静止就绪；对于活动阻塞状态的进程, 则将之改为静止
阻塞 。 为了方便用户或父进程考查该进程的运行情况而
把该进程的 PCB复制到某指定的内存区域 。 最后, 若被
挂起的进程正在执行, 则转向调度程序重新调度 。
第二章 进 程 管 理
2,进程的激活过程
当发生激活进程的事件时, 例如, 父进程或用户进程请
求激活指定进程, 若该进程驻留在外存而内存中已有足够的
空间时, 则可将在外存上处于静止就绪状态的进程换入内存 。
这时, 系统将利用激活原语 active( )将指定进程激活 。 激活
原语先将进程从外存调入内存, 检查该进程的现行状态, 若
是静止就绪, 便将之改为活动就绪；若为静止阻塞便将之改
为活动阻塞 。 假如采用的是抢占调度策略, 则每当有新进程
进入就绪队列时, 应检查是否要进行重新调度, 即由调度程
序将被激活进程与当前进程进行优先级的比较, 如果被激活
进程的优先级更低, 就不必重新调度；否则, 立即剥夺当前
进程的运行, 把处理机分配给刚被激活的进程 。
第二章 进 程 管 理
2.3 进 程 同 步
2.3.1 进程同步的基本概念
1,两种形式的制约关系
(1) 间接相互制约关系。
(2) 直接相互制约关系。
第二章 进 程 管 理
2,临界资源 (Critical Resouce)
生产者 -消费者 (producer-consumer)问题是一个著名的进
程同步问题 。 它描述的是：有一群生产者进程在生产产品,
并将这些产品提供给消费者进程去消费 。 为使生产者进程与
消费者进程能并发执行, 在两者之间设置了一个具有 n个缓
冲区的缓冲池, 生产者进程将它所生产的产品放入一个缓冲
区中； 消费者进程可从一个缓冲区中取走产品去消费 。 尽
管所有的生产者进程和消费者进程都是以异步方式运行的,
但它们之间必须保持同步, 即不允许消费者进程到一个空缓
冲区去取产品；也不允许生产者进程向一个已装满产品且尚
未被取走的缓冲区中投放产品 。
第二章 进 程 管 理
我们可利用一个数组来表示上述的具有 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则表
示缓冲池空 。 此外, 还引入了一个整型变量 counter,其初始
值为 0。 每当生产者进程向缓冲池中投放一个产品后, 使
counter加 1；反之, 每当消费者进程从中取走一个产品时,
使 counter减 1。 生产者和消费者两进程共享下面的变量：
第二章 进 程 管 理
Var n,integer;
type item=…;
var buffer:array［ 0,1,…,n-1］ of item;
in,out,0,1,…,n-1;
counter:0,1,…,n;
指针 in和 out初始化为 1。 在生产者和消费者进程的描述
中, no-op是一条空操作指令, while condition do no-op语句
表示重复的测试条件 (condication),重复测试应进行到该条
件变为 false(假 ),即到该条件不成立时为止 。 在生产者进程
中使用一局部变量 nextp,用于暂时存放每次刚生产出来的
产品；而在消费者进程中, 则使用一个局部变量 nextc,用于
存放每次要消费的产品 。
第二章 进 程 管 理
producer,repeat
…
produce an item in nextp;
…
while counter=n do no-op;
buffer［ in ∶ = nextp;
in ∶ = in+1 mod n;
counter ∶ = counter+1;
until false;
consumer,repeat
while counter=0 do no-op;
nextc ∶ = buffer［ out］ ;
out ∶ = (out+1) mod n;
counter ∶ = counter-1;
consumer the item in nextc;
until false;
第二章 进 程 管 理
虽然上面的生产者程序和消费者程序, 在分别看时都是
正确的, 而且两者在顺序执行时其结果也会是正确的, 但若
并发执行时, 就会出现差错, 问题就在于这两个进程共享变
量 counter。 生产者对它做加 1操作, 消费者对它做减 1操作,
这两个操作在用机器语言实现时, 常可用下面的形式描述：
register 1 ∶ = counter; register 2∶ = counter;
register1 ∶ = register 1+1; register 2∶ = register 2-1;
counter ∶ = register 1; counter ∶ = register 2;
第二章 进 程 管 理
假设,counter的当前值是 5。 如果生产者进程先执行左列
的三条机器语言语句, 然后消费者进程再执行右列的三条语
句, 则最后共享变量 counter的值仍为 5；反之, 如果让消费者
进程先执行右列的三条语句, 然后再让生产者进程执行左列
的三条语句, counter值也还是 5,但是, 如果按下述顺序执行：
register 1 ∶ = counter; (register 1=5)
register 1 ∶ = register 1+1; (register 1=6)
register 2 ∶ = counter; (register 2=5)
register 2 ∶ = register 2-1; (register 2=4)
counter ∶ = register 1; (counter=6)
counter ∶ = register 2; (counter=4)
第二章 进 程 管 理
3,临界区 (critical section)
repeat
critical section;
remainder section;
until false;
entry section
exit section
第二章 进 程 管 理
4,同步机制应遵循的规则
(1) 空闲让进。
(2) 忙则等待。
(3) 有限等待。
(4) 让权等待。
第二章 进 程 管 理
2.3.2 信号量机制
1.
最初由 Dijkstra把整型信号量定义为一个整型量, 除初
始化外, 仅能通过两个标准的原子操作 (Atomic Operation)
wait(S)和 signal(S)来访问 。 这两个操作一直被分别称为 P,V
操作 。 wait和 signal
wait(S),while S≤0 do no-op
S ∶ =S-1;
signal(S),S ∶ =S+1;
第二章 进 程 管 理
2,记录型信号量
在整型信号量机制中的 wait操作, 只要是信号量 S≤0，
就会不断地测试 。 因此, 该机制并未遵循, 让权等待, 的
准则, 而是使进程处于, 忙等, 的状态 。 记录型信号量机
制, 则是一种不存在, 忙等, 现象的进程同步机制 。 但在
采取了, 让权等待, 的策略后, 又会出现多个进程等待访
问同一临界资源的情况 。 为此, 在信号量机制中, 除了需
要一个用于代表资源数目的整型变量 value外, 还应增加一
个进程链表 L,用于链接上述的所有等待进程 。 记录型信号
量是由于它采用了记录型的数据结构而得名的 。 它所包含
的上述两个数据项可描述为：
第二章 进 程 管 理
type semaphore=record
value:integer;
L:list of process;
end
相应地,wait(S)和 signal(S)
procedure wait(S)
var S,semaphore;
begin
S.value ∶ = S.value-1;
if S.value＜ 0 then block(S,L)
end
procedure signal(S)
var S,semaphore;
begin
S.value ∶ = S.value+1;
if S.value≤0 then wakeup(S,L);
end
第二章 进 程 管 理
在记录型信号量机制中, S.value的初值表示系统中某类
资源的数目, 因而又称为资源信号量, 对它的每次 wait操作,
意味着进程请求一个单位的该类资源, 因此描述为 S.value∶
=S.value-1； 当 S.value＜ 0时, 表示该类资源已分配完毕, 因
此进程应调用 block原语, 进行自我阻塞, 放弃处理机, 并插
入到信号量链表 S.L中 。 可见, 该机制遵循了, 让权等待, 准
则 。 此时 S.value的绝对值表示在该信号量链表中已阻塞进程
的数目 。 对信号量的每次 signal操作, 表示执行进程释放一个
单位资源, 故 S.value∶ =S.value+1操作表示资源数目加 1。
若加 1后仍是 S.value≤0,则表示在该信号量链表中, 仍有等待
该资源的进程被阻塞, 故还应调用 wakeup原语, 将 S.L链表中
的第一个等待进程唤醒 。 如果 S.value的初值为 1,表示只允许
一个进程访问临界资源, 此时的信号量转化为互斥信号量 。
第二章 进 程 管 理
3,AND型信号量
在两个进程中都要包含两个对 Dmutex和 Emutex的操作, 即
process A,process B:
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);
若进程 A和 B按下述次序交替执行 wait
process A,wait(Dmutex); 于是 Dmutex=0
process B,wait(Emutex); 于是 Emutex=0
process A,wait(Emutex); 于是 Emutex=-1 A
process B,wait(Dmutex); 于是 Dmutex=-1 B阻塞
第二章 进 程 管 理
AND同步机制的基本思想是：将进程在整个运行过程
中需要的所有资源, 一次性全部地分配给进程, 待进程使
用完后再一起释放 。 只要尚有一个资源未能分配给进程,
其它所有可能为之分配的资源, 也不分配给他 。 亦即, 对
若干个临界资源的分配, 采取原子操作方式：要么全部分
配到进程, 要么一个也不分配 。 由死锁理论可知, 这样就
可避免上述死锁情况的发生 。 为此, 在 wait操作中, 增加
了一个, AND”条件, 故称为 AND同步, 或称为同时 wait
操作, 即 Swait(Simultaneous wait)定义如下：
第二章 进 程 管 理
Swait(S1,S2,…,Sn)
if Si≥1 and … and Sn≥1 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 Si＜ 1,and set the program count of this process to the beginning of
Swait operation
endif
Ssignal(S 1,S 2,…,S n)
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;
第二章 进 程 管 理
4,信号量集
Swait(S1,t1,d1,…,Sn,tn,dn)
if Si≥t1 and … and Sn≥tn then
for i∶ =1 to n do
Si∶ =Si-di;
endfor
else
Place the executing process in the waiting queue of the first Si with Si＜ ti 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 Si into the ready
queue
endfor;
第二章 进 程 管 理
一般, 信号量集,
(1) Swait(S,d,d)。 此时在信号量集中只有一个信号量 S，
但允许它每次申请 d个资源, 当现有资源数少于 d时, 不予
分配 。
(2) Swait(S,1,1)。 此时的信号量集已蜕化为一般的记
录型信号量 (S＞ 1时 )或互斥信号量 (S=1时 )。
(3) Swait(S,1,0)。 这是一种很特殊且很有用的信号量
操作 。 当 S≥1时, 允许多个进程进入某特定区；当 S变为 0后,
将阻止任何进程进入特定区 。 换言之, 它相当于一个可控
开关 。
第二章 进 程 管 理
2.3.3 信号量的应用
1,利用信号量实现进程互斥
Var mutex:semaphore ∶ = 1;
begin
parbegin
process 1,begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder seetion
until false;
第二章 进 程 管 理
end
process 2,begin
repeat
wait(mutex);
critical section
signal(mutex);
remainder section
until false;
end
parend
第二章 进 程 管 理
2,利用信号量实现前趋关系
图 2-10 前趋图举例
S
4
S
5
S
3
S
1
S
6
S
2
第二章 进 程 管 理
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 wait(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
第二章 进 程 管 理
2.4 经典进程的同步问题
2.4.1 生产者 —
前面我们已经对生产者 —消费者问题 (The proceducer-
consumer problem)做了一些描述, 但未考虑进程的互斥与
同步问题, 因而造成了数据 Counter的不定性 。 由于生产
者 —消费者问题是相互合作的进程关系的一种抽象, 例如,
在输入时, 输入进程是生产者, 计算进程是消费者；而
在输出时, 则计算进程是生产者, 而打印进程是消费者,
因此, 该问题有很大的代表性及实用价值 。
第二章 进 程 管 理
1,利用记录型信号量解决生产者 —消费者问题
假定在生产者和消费者之间的公用缓冲池中, 具有 n
个缓冲区, 这时可利用互斥信号量 mutex实现诸进程对缓
冲池的互斥使用；利用信号量 empty和 full分别表示缓冲池
中空缓冲区和满缓冲区的数量 。 又假定这些生产者和消
费者相互等效, 只要缓冲池未满, 生产者便可将消息送
入缓冲池；只要缓冲池未空, 消费者便可从缓冲池中取
走一个消息 。 对生产者 — 消费者问题可描述如下：
第二章 进 程 管 理
Var mutex,empty,full:semaphore ∶ = 1,n,0;
buffer:array［ 0,…,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
第二章 进 程 管 理
consumer:begin
repeat
wait(full);
wait(mutex);
nextc ∶ = buffer(out);
out ∶ = (out+1) mod n;
signal(mutex);
signal(empty);
consumer the item in nextc;
until false;
end
parend
end
第二章 进 程 管 理
在生产者 —消费者问题中应注意：首先, 在每个程序
中用于实现互斥的 wait(mutex)和 signal(mutex)必须成对地
出现； 其次, 对资源信号量 empty和 full的 wait和 signal操
作, 同样需要成对地出现, 但它们分别处于不同的程序
中 。 例如, wait(empty)在计算进程中, 而 signal(empty)则
在打印进程中, 计算进程若因执行 wait(empty)而阻塞,
则以后将由打印进程将它唤醒；最后, 在每个程序中的
多个 wait操作顺序不能颠倒 。 应先执行对资源信号量的
wait操作, 然后再执行对互斥信号量的 wait操作, 否则可
能引起进程死锁 。
第二章 进 程 管 理
2,利用 AND信号量解决生产者 — 消费者问题
ar mutex,empty,full:semaphore ∶ = 1,n,0;
buffer:array［ 0,…,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+1) mod n;
Ssignal(mutex,empty);
consumer the item in nextc;
until false;
end
parend
end
第二章 进 程 管 理
2.4.2 哲学家进餐问题
1.
经分析可知, 放在桌子上的筷子是临界资源, 在一段时
间内只允许一位哲学家使用 。 为了实现对筷子的互斥使用,
可以用一个信号量表示一只筷子, 由这五个信号量构成信号
量数组 。
Var chopstick,array［ 0,…,4］ of semaphore;
第二章 进 程 管 理
所有信号量均被初始化为 1,第 i位哲学家的活动可描述为：
repeat
wait(chopstick［ i］ );
wait(chopstick［ (i+1) mod 5］ );
…
eat;
…
signal(chopstick［ i］ );
signal(chopstick［ (i+1) mod 5］ );
…
think;
until false;
第二章 进 程 管 理
(1) 至多只允许有四位哲学家同时去拿左边的筷子,
最终能保证至少有一位哲学家能够进餐, 并在用毕时能释
放出他用过的两只筷子, 从而使更多的哲学家能够进餐 。
(2) 仅当哲学家的左, 右两只筷子均可用时, 才允许
他拿起筷子进餐 。
(3) 规定奇数号哲学家先拿他左边的筷子, 然后再去
拿右边的筷子；而偶数号哲学家则相反 。 按此规定, 将是
1,2号哲学家竞争 1号筷子； 3,4号哲学家竞争 3号筷子 。
即五位哲学家都先竞争奇数号筷子, 获得后, 再去竞争偶
数号筷子, 最后总会有一位哲学家能获得两只筷子而进餐 。
第二章 进 程 管 理
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;
Ssignat(chopstick ［ (i+1) mod 5］,chopstick ［ i］ );
until false;
第二章 进 程 管 理
2.4.3 读者 -写者问题
1,利用记录型信号量解决读者 -写者问题
为实现 Reader与 Writer进程间在读或写时的互斥而设置了
一个互斥信号量 Wmutex。 另外, 再设置一个整型变量
Readcount表示正在读的进程数目 。 由于只要有一个 Reader进
程在读, 便不允许 Writer进程去写 。 因此, 仅当 Readcount=0,
表示尚无 Reader 进程在读时, Reader 进 程 才 需 要 执 行
Wait(Wmutex)操作 。 若 wait(Wmutex)操作成功, Reader进程便
可去读, 相应地, 做 Readcount+1操作 。 同理, 仅当 Reader进
程在执行了 Readcount 减 1操作后其值为 0时, 才须执行
signal(Wmutex)操作, 以便让 Writer进程写 。 又因为 Readcount
是一个可被多个 Reader进程访问的临界资源, 因此, 应该为
它设置一个互斥信号量 rmutex。
第二章 进 程 管 理
读者 -
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(rmutex);
until false;
end
writer:begin
repeat
wait(wmutex);
perform write operation;
signal(wmutex);
until false;
end
parend
end
第二章 进 程 管 理
2,利用信号量集机制解决读者 -写者问题
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
第二章 进 程 管 理
2.5 管 程 机 制
2.5.1 管程的基本概念
1,管程的定义
管程由三部分组成,① 局部于管程的共享变量说明；
② 对该数据结构进行操作的一组过程； ③ 对局部于管程
的数据设置初始值的语句 。 此外, 还须为管程赋予一个
名字 。
第二章 进 程 管 理
图 2-11 管程的示意图
共享数据
?
一组操作过程
初始化代码
进入队列
条件( 不忙) 队列
第二章 进 程 管 理
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
第二章 进 程 管 理
2,条件变量
管程中对每个条件变量, 都须予以说明, 其形式为,Var
x,y:condition。 该变量应置于 wait和 signal之前, 即可表示为
X.wait和 X.signal。 例如, 由于共享数据被占用而使调用进程
等待, 该条件变量的形式为,nonbusy:condition。 此时,
wait 原 语 应 改 为 nonbusy.wait, 相 应 地, signal 应改为
nonbusy.signal。
应当指出, X.signal操作的作用, 是重新启动一个被阻塞
的进程, 但如果没有被阻塞的进程, 则 X.signal操作不产生任
何后果 。 这与信号量机制中的 signal操作不同 。 因为, 后者总
是要执行 s∶ =s+1操作, 因而总会改变信号量的状态 。
第二章 进 程 管 理
如果有进程 Q处于阻塞状态, 当进程 P执行了 X.signal
操作后, 怎样决定由哪个进行执行, 哪个等待, 可采用
(1) P等待, 直至 Q离开管程或等待另一条件 。
(2) Q等待, 直至 P离开管程或等待另一条件 。
采用哪种处理方式,当然是各执一词。 但是 Hansan
却采用了第一种处理方式。
第二章 进 程 管 理
2.5.2 利用管程解决生产者 -消费者问题
在利用管程方法来解决生产者 -消费者问题时, 首先
便是为它们建立一个管程, 并命名为 Proclucer-Consumer,
或简称为 PC。
(1) put(item)过程 。 生产者利用该过程将自己生产的
产品投放到缓冲池中, 并用整型变量 count来表示在缓冲
池中已有的产品数目, 当 count≥n时, 表示缓冲池已满,
生产者须等待 。
第二章 进 程 管 理
(1) put(item)过程 。 生产者利用该过程将自己生产的产
品投放到缓冲池中, 并用整型变量 count来表示在缓冲池中
已有的产品数目, 当 count≥n时, 表示缓冲池已满, 生产者
须等待 。
(2) get(item)过程 。 消费者利用该过程从缓冲池中取出
一个产品, 当 count≤0时, 表示缓冲池中已无可取用的产品,
消费者应等待 。
第二章 进 程 管 理
type producer-consumer=monitor
Var in,out,count:integer;
buffer:array［ 0,…,n-1］ of item;
notfull,notempty:condition;
procedure entry put(item)
begin
if count≥n then notfull.wait;
buffer(in) ∶ = nextp;
in ∶ = (in+1) mod n;
count ∶ = count+1;
if notempty.queue then notempty.signal;
end
第二章 进 程 管 理
procedure entry get(item)
begin
if count≤0 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
第二章 进 程 管 理
在利用管程解决生产者 -消费者问题时,其中的生
产者和消费者可描述为：
producer:begin
repeat
produce an item in nextp;
PC.put(item);
until false;
end
consumer:begin
repeat
PC.get(item);
consume the item in nextc;
until false;
end
第二章 进 程 管 理
2.6 进 程 通 信
2.6.1 进程通信的类型
1,共享存储器系统 (Shared-Memory System)
(1) 基于共享数据结构的通信方式。
(2) 基于共享存储区的通信方式。
第二章 进 程 管 理
2,消息传递系统 (Message passing system)
不论是单机系统, 多机系统, 还是计算机网络, 消息
传递机制都是用得最广泛的一种进程间通信的机制 。 在消
息传递系统中, 进程间的数据交换, 是以格式化的消息
(message)为单位的；在计算机网络中, 又把 message称为报
文 。 程序员直接利用系统提供的一组通信命令 (原语 )进行
通信 。 操作系统隐藏了通信的实现细节, 大大减化了通信
程序编制的复杂性, 而获得广泛的应用 。 消息传递系统的
通信方式属于高级通信方式 。 又因其实现方式的不同而进
一步分成直接通信方式和间接通信方式两种 。
第二章 进 程 管 理
3,管道 (Pipe)
所谓, 管道,, 是指用于连接一个读进程和一个写
进程以实现他们之间通信的一个共享文件, 又名 pipe文
件 。 向管道 (共享文件 )提供输入的发送进程 (即写进程 )，
以字符流形式将大量的数据送入管道；而接受管道输出
的接收进程 (即读进程 ),则从管道中接收 (读 )数据 。 由于
发送进程和接收进程是利用管道进行通信的, 故又称为
管道通信 。 这种方式首创于 UNIX系统, 由于它能有效地
传送大量数据, 因而又被引入到许多其它操作系统中 。
第二章 进 程 管 理
为了协调双方的通信, 管道机制必须提供以下三方面
的协调能力,① 互斥, 即当一个进程正在对 pipe执行读 /
写操作时, 其它 (另一 )进程必须等待 。 ② 同步, 指当写
(输入 )进程把一定数量 (如 4 KB)的数据写入 pipe,便去睡
眠等待, 直到读 (输出 )进程取走数据后, 再把他唤醒 。 当
读进程读一空 pipe时, 也应睡眠等待, 直至写进程将数据
写入管道后, 才将之唤醒 。 ③ 确定对方是否存在, 只有
确定了对方已存在时, 才能进行通信 。
第二章 进 程 管 理
2.6.2 消息传递通信的实现方法
1.
这是指发送进程利用 OS所提供的发送命令, 直接把消
息发送给目标进程 。 此时, 要求发送进程和接收进程都以
显式方式提供对方的标识符 。 通常, 系统提供下述两条通
信命令 (原语 )
Send(Receiver,message); 发送一个消息给接收进程；
Receive(Sender,message); 接收 Sender
例如, 原语 Send(P2,m1)表示将消息 m1发送给接收进程 P2;
而原语 Receive(P1,m1)则表示接收由 P1发来的消息 m1。
第二章 进 程 管 理
在某些情况下, 接收进程可与多个发送进程通信,
因此, 它不可能事先指定发送进程 。 例如, 用于提供打
印服务的进程, 它可以接收来自任何一个进程的, 打印
请求, 消息 。 对于这样的应用, 在接收进程接收消息的
原语中的源进程参数, 是完成通信后的返回值, 接收原
语可表示为：
Receive (id,message);
第二章 进 程 管 理
我们还可以利用直接通信原语, 来解决生产者 -消费者问题 。
当生产者生产出一个产品 (消息 )后, 便用 Send原语将消息发送
给消费者进程；而消费者进程则利用 Receive原语来得到一个消
息 。 如果消息尚未生产出来, 消费者必须等待, 直至生产者进
程将消息发送过来 。 生产者 -消费者的通信过程可分别描述如下：
repeat
…
produce an item in nextp;
…
send(consumer,nextp);
until false;
repeat
receive(producer,nextc);
…
consume the item in nextc;
until false;
第二章 进 程 管 理
2,间接通信方式
(1) 信箱的创建和撤消 。 进程可利用信箱创建原语来建立
一个新信箱 。 创建者进程应给出信箱名字, 信箱属性 (公用,
私用或共享 )；对于共享信箱, 还应给出共享者的名字 。 当进
程不再需要读信箱时, 可用信箱撤消原语将之撤消 。
(2) 消息的发送和接收 。 当进程之间要利用信箱进行通信
时, 必须使用共享信箱, 并利用系统提供的下述通信原语进
行通信 。
Send(mailbox,message);
Receive(mailbox,message); 从指定信箱中接收一个消息；
第二章 进 程 管 理
信箱可由操作系统创建, 也可由用户进程创建, 创建
者是信箱的拥有者 。 据此, 可把信箱分为以下三类 。
1)
用户进程可为自己建立一个新信箱, 并作为该进程的
一部分 。 信箱的拥有者有权从信箱中读取消息, 其他用户
则只能将自己构成的消息发送到该信箱中 。 这种私用信箱
可采用单向通信链路的信箱来实现 。 当拥有该信箱的进程
结束时, 信箱也随之消失 。
第二章 进 程 管 理
2)
它由操作系统创建, 并提供给系统中的所有核准进程
使用 。 核准进程既可把消息发送到该信箱中, 也可从信箱
中读取发送给自己的消息 。 显然, 公用信箱应采用双向通
信链路的信箱来实现 。 通常, 公用信箱在系统运行期间始
终存在 。
3)
它由某进程创建, 在创建时或创建后, 指明它是可共享
的, 同时须指出共享进程 (用户 )的名字 。 信箱的拥有者和共
享者, 都有权从信箱中取走发送给自己的消息 。
第二章 进 程 管 理
在利用信箱通信时, 在发送进程和接收进程之间, 存在以
(1) 一对一关系 。 这时可为发送进程和接收进程建立一条两
者专用的通信链路, 使两者之间的交互不受其他进程的干扰 。
(2) 多对一关系 。 允许提供服务的进程与多个用户进程之间
进行交互, 也称为客户 /服务器交互 (client/server interaction)。
(3) 一对多关系 。 允许一个发送进程与多个接收进程进行
交互, 使发送进程可用广播方式, 向接收者 (多个 )发送消息 。
(4) 多对多关系 。 允许建立一个公用信箱, 让多个进程都
能向信箱中投递消息；也可从信箱中取走属于自己的消息 。
第二章 进 程 管 理
2.6.3 消息传递系统实现中的若干问题
1,通信链路 (communication link)
为使在发送进程和接收进程之间能进行通信, 必须在两者
之间建立一条通信链路 。 有两种方式建立通信链路 。 第一种方
式是：由发送进程在通信之前, 用显式的, 建立连接, 命令
(原语 )请求系统为之建立一条通信链路；在链路使用完后, 也
用显式方式拆除链路 。
这种方式主要用于计算机网络中 。 第二种方式是发送进程
无须明确提出建立链路的请求, 只须利用系统提供的发送命令
(原语 ),系统会自动地为之建立一条链路 。 这种方式主要用于
单机系统中 。
第二章 进 程 管 理
根据通信链路的连接方法, 又可把通信链路分为两
类,① 点 —点连接通信链路, 这时的一条链路只连接两
个结点 (进程 )； ② 多点连接链路, 指用一条链路连接多
个 (n＞ 2)结点 (进程 )。 而根据通信方式的不同, 则又可把
链路分成两种,① 单向通信链路, 只允许发送进程向
接收进程发送消息； ② 双向链路, 既允许由进程 A向进
程 B发送消息, 也允许进程 B同时向进程 A发送消息 。
第二章 进 程 管 理
2,消息的格式
在某些 OS中, 消息是采用比较短的定长消息格式, 这
减少了对消息的处理和存储开销 。 这种方式可用于办公自
动化系统中, 为用户提供快速的便笺式通信；但这对要发
送较长消息的用户是不方便的 。 在有的 OS中, 采用另一种
变长的消息格式, 即进程所发送消息的长度是可变的 。 系
统在处理和存储变长消息时, 须付出更多的开销, 但方便
了用户 。 这两种消息格式各有其优缺点, 故在很多系统 (包
括计算机网络 )中, 是同时都用的 。
第二章 进 程 管 理
3,进程同步方式
(1) 发送进程阻塞,接收进程阻塞。
(2) 发送进程不阻塞,接收进程阻塞。
(3) 发送进程和接收进程均不阻塞。
第二章 进 程 管 理
2.6.4 消息缓冲队列通信机制
1,消息缓冲队列通信机制中的数据结构
(1) 消息缓冲区 。 在消息缓冲队列通信方式中, 主要利
用的数据结构是消息缓冲区 。
type message buffer=record
sender;
size;
text;
next;
end
第二章 进 程 管 理
(2) PCB中有关通信的数据项 。 在利用消息缓冲队列通
信机制时, 在设置消息缓冲队列的同时, 还应增加用于对
消息队列进行操作和实现同步的信号量, 并将它们置入进
程的 PCB中 。 在 PCB
type processcontrol block=record
…
mq;
mutex;
sm;
…
end
第二章 进 程 管 理
2.
发送进程在利用发送原语发送消息之前, 应先在自己
的内存空间, 设置一发送区 a,见图 2 - 12 所示, 把待发送
的消息正文, 发送进程标识符, 消息长度等信息填入其中,
然后调用发送原语, 把消息发送给目标 (接收 )进程 。 发送原
语首先根据发送区 a中所设置的消息长度 a.size来申请一缓冲
区 i,接着, 把发送区 a中的信息复制到缓冲区 i中 。 为了能
将 i挂在接收进程的消息队列 mq上, 应先获得接收进程的内
部标识符 j,然后将 i挂在 j.mq上 。 由于该队列属于临界资源,
故在执行 insert操作的前后, 都要执行 wait和 signal操作 。
第二章 进 程 管 理
图 2 - 12 消息缓冲通信
s e n d e r, A
s i z e, 5
t e x t, H e l l o
mq
m u t e x
sm
s e n d e r, A
s i z e, 5
t e x t, H e l l o
n e x t, 0
s e n d ( B,a )
第一消息缓冲区
s e n d e r, A
s i z e, 5
t e x t, H e l l o
r e c e i v e ( b )
a
发
送
区
a
b
接
收
区
b
进程 BP C B ( B )进程 A
第二章 进 程 管 理
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 set,receiver.j); 获得接收进程内部标识符；
wait(j.mutex);
insert(j.mq,i);
signal(j.mutex);
signal(j.sm);
end
第二章 进 程 管 理
3,接收原语
procedurereceive(b)
begin
j ∶ = internal name; j
wait(j.sm);
wait(j.mutex);
remove(j.mq,i);
signal(j.mutex);
b.sender ∶ = i.sender; 将消息缓冲区 i中的信息复制到接收区 b;
b.size ∶ = i.size;
b.text ∶ = i.text;
end
第二章 进 程 管 理
2.7 线 程
2.7.1 线程的基本概念
为使程序能并发执行, 系统还必须进行以下的一系列
操作 。
1) 创建进程
2) 撤消进程
3)
第二章 进 程 管 理
2,线程的属性
(1) 轻型实体。
(2) 独立调度和分派的基本单位。
(3) 可并发执行。
(4) 共享进程资源。
第二章 进 程 管 理
3.
(1) 状态参数 。
在 OS中的每一个线程都可以利用线程标识符和一组状
态参数进行描述 。 状态参数通常有这样几项,① 寄存器状
态, 它包括程序计数器 PC和堆栈指针中的内容； ② 堆栈,
在堆栈中通常保存有局部变量和返回地址； ③ 线程运行状
态, 用于描述线程正处于何种运行状态； ④ 优先级, 描
述线程执行的优先程度； ⑤ 线程专有存储器, 用于保存
线程自己的局部变量拷贝； ⑥ 信号屏蔽, 即对某些信号
加以屏蔽 。
第二章 进 程 管 理
(2) 线程运行状态 。
如同传统的进程一样, 在各线程之间也存在着共享资
源和相互合作的制约关系, 致使线程在运行时也具有间断
性 。 相应地, 线程在运行时, 也具有下述三种基本状态：
① 执行状态, 表示线程正获得处理机而运行； ② 就绪状态,
指线程已具备了各种执行条件, 一旦获得 CPU便可执行的
状态； ③ 阻塞状态, 指线程在执行中因某事件而受阻, 处
于暂停执行时的状态 。
第二章 进 程 管 理
4.
在多线程 OS环境下, 应用程序在启动时, 通常仅有一
个线程在执行, 该线程被人们称为, 初始化线程, 。 它可
根据需要再去创建若干个线程 。 在创建新线程时, 需要利
用一个线程创建函数 (或系统调用 ),并提供相应的参数, 如
指向线程主程序的入口指针, 堆栈的大小, 以及用于调度
的优先级等 。 在线程创建函数执行完后, 将返回一个线程
标识符供以后使用 。
终止线程的方式有两种：一种是在线程完成了自己的
工作后自愿退出；另一种是线程在运行中出现错误或由于
某种原因而被其它线程强行终止 。
第二章 进 程 管 理
5,多线程 OS中的进程
在多线程 OS中, 进程是作为拥有系统资源的基本单位,
通常的进程都包含多个线程并为它们提供资源, 但此时的进
程就不再作为一个执行的实体 。 多线程 OS中的进程有以下
属性：
(1) 作为系统资源分配的单位。
(2) 可包括多个线程。
(3) 进程不是一个可执行的实体。
第二章 进 程 管 理
2.7.2 线程间的同步和通信
1,互斥锁 (mutex)
互斥锁是一种比较简单的, 用于实现进程间对资源互
斥访问的机制 。 由于操作互斥锁的时间和空间开锁都较低,
因而较适合于高频度使用的关键共享数据和程序段 。 互斥
锁可以有两种状态, 即开锁 (unlock)和关锁 (lock)状态 。
相应地, 可用两条命令 (函数 )对互斥锁进行操作 。 其中的
关锁 lock操作用于将 mutex关上, 开锁操作 unlock则用于打
开 mutex。
第二章 进 程 管 理
2,条件变量
每一个条件变量通常都与一个互斥锁一起使用, 亦即,
在创建一个互斥锁时便联系着一个条件变量 。 单纯的互斥锁
用于短期锁定, 主要是用来保证对临界区的互斥进入 。 而条
件变量则用于线程的长期等待, 直至所等待的资源成为可
用的 。
线程首先对 mutex执行关锁操作, 若成功便进入临界区,
然后查找用于描述资源状态的数据结构, 以了解资源的情况 。
只要发现所需资源 R正处于忙碌状态, 线程便转为等待状态,
并对 mutex执行开锁操作后, 等待该资源被释放； 若资源处
于空闲状态, 表明线程可以使用该资源, 于是将该资源设置
为忙碌状态, 再对 mutex执行开锁操作 。
第二章 进 程 管 理
下面给出了对上述资源的申请 (左半部分 )和释放 (右半
部分 )操作的描述 。
Lock mutex Lock mutex
check data structures; mark resource as free;
while(resource busy); unlock mutex;
wait(condition variable); wakeup(condition variable);
mark resource as busy;
unlock mutex;
第二章 进 程 管 理
3,信号量机制
(1) 私用信号量 (private samephore)。
当某线程需利用信号量来实现同一进程中各线程之间的
同步时, 可调用创建信号量的命令来创建一私用信号量, 其
数据结构是存放在应用程序的地址空间中 。 私用信号量属于
特定的进程所有, OS并不知道私用信号量的存在, 因此, 一
旦发生私用信号量的占用者异常结束或正常结束, 但并未释
放该信号量所占有空间的情况时, 系统将无法使它恢复为
0(空 ),也不能将它传送给下一个请求它的线程 。
第二章 进 程 管 理
(2) 公用信号量 (public semaphort)。
公用信号量是为实现不同进程间或不同进程中各线程
之间的同步而设置的 。 由于它有着一个公开的名字供所有
的进程使用, 故而把它称为公用信号量 。 其数据结构是存
放在受保护的系统存储区中, 由 OS为它分配空间并进行管
理, 故也称为系统信号量 。 如果信号量的占有者在结束时
未释放该公用信号量, 则 OS会自动将该信号量空间回收,
并通知下一进程 。 可见, 公用信号量是一种比较安全的同
步机制 。
第二章 进 程 管 理
2.7.3 内核支持线程和用户级线程
1,内核支持线程
这里所谓的内核支持线程, 也都同样是在内核的支
持下运行的, 即无论是用户进程中的线程, 还是系统进
程中的线程, 他们的创建, 撤消和切换等, 也是依靠内
核实现的 。 此外, 在内核空间还为每一个内核支持线程
设置了一个线程控制块, 内核是根据该控制块而感知某
线程的存在的, 并对其加以控制 。
第二章 进 程 管 理
2.
用户级线程仅存在于用户空间中 。 对于这种线程的
创建, 撤消, 线程之间的同步与通信等功能, 都无须利
用系统调用来实现 。 对于用户级线程的切换, 通常是发
生在一个应用进程的诸多线程之间, 这时, 也同样无须
内核的支持 。 由于切换的规则远比进程调度和切换的规
则简单, 因而使线程的切换速度特别快 。 可见, 这种线
程是与内核无关的 。
第二章 进 程 管 理
2.7.4 线程控制
1,内核支持线程的实现
图 2 - 13 任务数据区空间
PTDA 进程资源
TCB # 1
TCB # 2
TCB # 3
第二章 进 程 管 理
2,用户级线程的实现
1) 运行时系统 (Runtime System)
所谓, 运行时系统,, 实质上是用于管理和控制线程
的函数 (过程 )的集合, 其中包括用于创建和撤消线程的函
数, 线程同步和通信的函数以及实现线程调度的函数等 。
正因为有这些函数, 才能使用户级线程与内核无关 。 运行
时系统中的所有函数都驻留在用户空间, 并作为用户级线
程与内核之间的接口 。
第二章 进 程 管 理
2)
这种线程又称为轻型进程 LWP(Light Weight
Process)。 每一个进程都可拥有多个 LWP,同用户级
线程一样, 每个 LWP都有自己的数据结构 (如 TCB),其
中包括线程标识符, 优先级, 状态, 另外还有栈和局
部存储区等 。 它们也可以共享进程所拥有的资源 。
LWP可通过系统调用来获得内核提供的服务, 这样,
当一个用户级线程运行时, 只要将它连接到一个 LWP
上, 此时它便具有了内核支持线程的所有属性 。
第二章 进 程 管 理
图 2 - 14 利用轻型进程作为中间系统
用户级线程
轻型进程
内 核
C P U
任务 1 任务 2 任务 3
内核线程
