第二章 进 程 管 理第二章 进程管理
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
内核线程
