第 4章 分布式进程管理东北大学信息学院于 戈
2002年 6月
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
2
主要内容
4.1 进程和线程管理
4.2 分布式处理机管理
4.3 分布式容错系统
4.4 分布式实时系统
4.5 习题
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
3
4.1 进程和线程管理
进程模型。例,4个程序组成的多道程序
– 逻辑上,4个独立的、顺序的进程的概念模型
– 物理上，任意时刻只有一个是活动的
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
4
操作系统的进程结构
调度器：处理分时中断、调度
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
5
进程的状态
1 – 进程 a等待输入而 阻塞,
2 – 调度器选择另一个就绪进程 b
3 – 启动进程 b运行
4 – 当输入完成后,进程 a
进入 就绪 队列
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
6
进程的实现 —进 程表进程管理 内存管理 文件管理
Registers
Program counter
Program status word
Stack pointer
Process state
Priority
Scheduling parameters
Pointer to text segment
Pointer to data segment
Pointer to stack segment
Root directory
Working directory
File descriptors
User ID
Group ID
Process ID
Parent process
Process group
Signals
Starting time
CPU time used
Children’s CPU time
Time of next alarm
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
7
中断处理和调度
1,将当前 程序指针 压栈（硬件）
2,从 中断向量 取出新的程序指针（硬件）
3,保存当前 寄存器 （汇编,中断处理 ）
4,设置新的 栈指针 （汇编,中断处理 ）
5,执行 中断服务程序 （ C语言,中断处理 ）
6,调度器 决定下一个运行的进程（ C语言,调度器 ）
7,加载 寄存器和内存映像 （汇编,调度器 ）
8,启动新的 进程 （汇编,调度器 ）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
8
线程的概念
进程：相关的运行资源的管理单位
– 内存空间
– 打开的文件
– 子进程、信号处理、记账信息等
资源分组
线索：在 CPU上执行的脉络
– 程序计数器、寄存器、栈
执行
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
9
线程模型
多线程进程：一个线程被阻塞时，可运行同一进程中的另一 线程（ 阻塞?就绪?运行 ）
线程?进程； 进程?处理机；
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
10
线程模型
每个线程可共享所属进程的资源
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
11
线程模型
每个线程拥有自己的栈
– 局部变量、返回地址
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
12
线程的用途
例 1：包含 3个线程的字处理器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
13
例 2:多线程的 Web服务器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
14
多线程示例代码
(a),分派者 线程（ dispatcher） 源代码
(b),工作者 线程（ worker） 源代码
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
15
多线程服务器的组织方式
（ a） 分派者 /工作者 模型 （ b）团队模型
（ c）管道模型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
16
服务器组织的比较模 式 并行 非阻塞式系统调用 性能 编程容易程度单线程进程 低 √
多线程进程 √? 高 √
有限状态机 √ √ 高?
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
17
多线程的实现方式 1
用户空间
– 切换效率高
– 专门的调度算法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
18
多线程的实现方式 2
内核空间：
– 由内核管理
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
19
多线程的实现方式 3
混合方式
– 将用户级线程多个转接到内核线程上
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
20
例,调度器激活方法
目标,
–既有用户进程的优点 (高性能、灵活 ),
又有内核进程的优点（实现简单）。
方案：
–避免不必要的“用户 /内核” 间的切换
实现：
–Upcall机制：下层内核可调用上层用户运行系统
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
21
例,调度器激活方法
算法：
– 内核为每个 进程 分配虚拟的处理机；由进程的用户运行系统为 线程 分配处理机
– 当 线程 x在内核被阻塞后，调度器 Upcall其 运行系统,重新调度其他就绪线程
– 当 线程 x可运行后，调度器 Upcall其 运行系统,重新调度
– 当产生硬件中断后，如果与 进程 A有关，则 Upcall
其 运行系统,重新调度
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
22
线程的管理
线程包：
– 为用户编程提供的线程操作原语程序库
静态线程：
– 线程的数量在编译时预先确定
动态线程：
– 在运行时随时创建或撤销线程
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
23
线程的互斥控制
小型互斥变量 mutex
lock
unlock
用于进 /出临界区
条件变量
用于对资源的长期等待
与 mutex
lock mutex;
check data structures;
while(resource busy)
wait(condition variable);
mark resource as busy
unlock;
（ a） 获得资源
lock mutex;
mark resouce as free;
unlock mutex;
wakeup(condition variable);
（ b） 释放资源，唤醒线程
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
24
全局变量的冲突
例：全局变量 error
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
25
全局变量的冲突
解决方法：
设置私有的全局变量
例,提供库函数
1,创建一个线程的全局变量
create_global( ―bufptr‖ );
2,设置一个全局变量
set_global(―bufptr‖,&buf)
3,读一个全局变量
bufptr=read_global(―bufptr‖ )
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
26
Pop-Up 式线程与 RPC
作用,负责接收消息。例,receive_msg(addr,&buf)
（ a）消息到达前 （ b）消息到达后
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
27
Unix中的线程 API调用
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
28
Windows中的进程管理
基本概念
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
29
Job,Process,Thread的相互关系
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
30
Win32的 API调用
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
31
4.2 分布式处理机管理
工作站模型
– 无盘工作站
– 有盘工作站
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
32
工作站上磁盘的作用使用情况 优点 缺点无磁盘 费用低，灵活，易于软硬件维护网络负载重，文件服务器为瓶颈换页，保存临时文件 网络负载小 磁盘成本高换页，保存临时文件和执行文件网络负载更小 磁盘成本更高，执行文件的更新复杂换页，保存临时文件和执行文件，文件缓存。
网络负载更更小，
减少文件服务器负载成本高，缓存一致性维护复杂完全的本地文件系统 几乎无网络负载，
不需要文件服务器失去透明型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
33
空闲处理机
远程执行,rsh machine command
基于注册表算法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
34
工作站管理
处理机池模型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
35
工作站管理
排队模型
平均响应时间 T= 1/(λ –μ)
n台处理机平均响应时间 T1= T/n
计算机 完成工作用户用户每秒共产生 μ 个请求系统每秒能处理 γ 个请求
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
36
工作站管理
混合模型：
– 前台交互式任务：个人工作站
– 后台任务：处理机池
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
37
处理机分配管理
分配模型
– 非迁移型
– 迁移型
分配目标
– 最大 CPU利用率
– 最快响应时间
– 响应比：实际运行时间 /实际需要时间
负载平衡
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
38
处理机分配
分配方案 1：处理机 1 运行进程 A，处理机运行进程 B，
平均响应时间 =（ 10＋ 8） /2＝ 9
分配方案 2,处理机 1 运行进程 B，处理机运行进程 A，
平均响应时间 = （ 30＋ 6） /2＝ 18
处理机 1
10MIPS 处理机 2100MIPS没有队列 5秒队列进程
A(1亿条指令 )
B(3亿条指令 )
10秒
30秒
6秒
8秒
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
39
处理机分配设计
1,确定性 vs 启发式 （ 试探性 ）
2,集中式 vs 分布式
3,最优 vs 较优
4,局部的 vs 全局的
5,发送者发起的 vs 接收者发起的
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
40
Eager的启发式算法
1,转发法,随机选择一台机器 A，向它发送新进程。如果 A已经过载,A也同样随机选择另一台机器 B，向 B发送进程。
2,查询法,随机选择一台机器 A，向它发送一个负载情况询问。如果欠载,A就会得到这个进程；否则，将重新选择一台机器。
3,比较法,询问 k台机器，确定它们的确切负载情况。将新过程传送到负载最小的那台机器上。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
41
基于图的确定性算法
例,3个处理机,9个进程
方案 A:通信量 =(3＋ 2＋ 4＋ 4)＋ (2＋ 8＋ 5＋ 2)＝ 30
方案 B:通信量 =(3＋ 2＋ 4＋ 4)＋ (3＋ 5＋ 5＋ 2)＝ 28
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
42
集中的启发式的 up-down算法
目标：工作站公平地享用系统的计算能力
使用情况表,〉 0表示使用资源； <0表示需要系统资源,0为初始值时间
P1到达
P1分配到处理器
P2到达 P2分配到处理器 P1完成
P2完成使用情况表积分
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
43
层次式的算法主任委员会部门领导工作人员
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
44
发送者 /接收者算法请求帮助请执行一个进程吧请完成一个工作吧此机器负担太重了求助机器判定它的负担太重
（ a）
今晚我空闲我无事可作机器宣告它可被使用我厌烦了需要
CPU周期？
需要帮助？
（ b）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
45
处理机的分配
协同调度（ co-scheduling）
– 将一组协同进程安排在不同处理机的同一时间片内以产生最小的时间延迟。
A C
B D
A C
B D
A C
B D
0 1
0
1
2
3
4
5
0 1
0
1
2
3
4
5
2 43 5 6 7
（ a）简单轮转 （ b）分组调度处理器 处理器时间片时间片
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
46
4.3 分布式容错系统
基本概念
– 差错（ error）：如程序 bug
– 故障（ fault）：
短暂型、间歇型、永久型
– 失效（ failure）
失效模型
– p为每秒失效概率
– 平均失效时间 = Σkp(1-p)k-1=1/p
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
47
系统失效
故障类型
– fail-stop故障
– 拜占庭故障
系统类型
– 同步系统：在规定时间内有响应
– 异步系统：设一个上限
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
48
冗余技术
冗余类型
– 信息冗余
– 时间冗余
– 物理冗余
设计问题
– 需要复制的程度
– 无故障时,平均情况和最坏情况下的系统性能
– 有故障 时，平均情况和最坏情况下的系统性能
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
49
主动复制容错技术
相同的部件
K-容错度：在有 k个部件发生故障时，系统仍能正确运行
Fail-stop型故障,k+1冗余度
拜占庭型故障,2k+1冗余度
有限状态机方法：接收请求，给出应答
– 所有的请求到达所有服务器的顺序应相同
– 原子广播问题（ atomic broadcast problem）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
50
主动复制方法
三模冗余方法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
51
主备份方法（ primary backup）
主服务器失效，则后援服务器接替其任务
接管模型客户 主系统 后援系统
1.请求 2.执行 3.更新 4.执行
6.应答 5.确认
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
52
协同一致问题
两军问题
通信可靠
3000
5000
3000
1
2
3
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
53
Lamport递归算法
拜占庭将军问题
例,3个忠诚将军,1个叛变将军
– 结果,（ 1,2，未知,4）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
54
Lamport递归算法
若三个将军中，有两个忠诚将军，一个叛变将军，则不能判断出哪个将军叛变。
若要有 m个处理机出错的系统实现协同一致，最少要有 2m＋ 1个正常处理机。处理机总数为 3m+1
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
55
4.4 实时分布式系统
实时系统：
– 当某个激励出现时，系统必须以一定的方式在限定的时间内响应它。
– 如果超时，即使结果正确，也认为是系统失效
实时系统类型
– 软实时系统：允许偶尔错过截至时间（ deadline）
– 硬实时系统：严格不允许，如飞机导航
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
56
实时事件流
事件类型
– 周期的、非周期的、突发的
例,3个事件流 +1个意外事件时间
A
B
C
A
B
C
A
B
C
A
B
C
A
B
A
C
B
A
C
B
A A
C
B
X
无法预料的事件A的周期 B的周期 C的周期工作负荷空闲
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
57
分布式实时计算机系统结构
Dev
C
Dev
C
Dev
C
Dev
C
Dev
C
Dev
CC
外部设备计算机网络执行机构 传感器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
58
分布式实时系统设计
事件触发系统
–当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的 CPU得到一个中断请求。
–通常是中断驱动的。
主要问题
–当 事件风暴（ event shower） 发生时，
在重载情况下会失效 。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
59
分布式实时系统设计
时间触发系统
– 每 ⊿ T毫秒产生一次时钟中断。在每一次时钟滴答时，对（选定的）传感器进行采样，并且驱动（特定的）执行机构。
– 中断仅在时钟滴答时发生 。
⊿ T的选择
– 必须非常小心地选择。若 ⊿ T太小，系统将产生许多时钟中断，将浪费大量的时间来响应它们
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
60
分布式实时调度
硬实时与软实时
– 保证所有时限都要满足
抢占的与非抢占的
– 允许在高优先级的任务到来时挂起当前的任务
动态的与静态的
– 在运行期间进行调度
集中的与分散的
– 各个处理机可以独立做出决定
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
61
分布式实时调度
可调度性
N个处理机
M个运行任务
任务 i所需 CPU时间 Ci,周期为 Pi
系统利用率 μ
N
p
cm
i i
i
1
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
62
动态调度
比率单调算法
– 每个任务分配一个与其执行频率相等的优先级
– 动态抢占式调度
最早时限优先法 （ earliest deadline first）
– 等待队列根据这些任务的时限排序
最小余度法 (least laxity)
– 优先调度具有最小剩余时间量的任务
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
63
静态调度
已知所有任务的列表及它们各自的运行时间
启发式方法
非抢占式静态调度
3
A
1
2
5
4
6
7 8 9 10
B
激励响应
1 2 3 4 5 6 1 3 5 2 4 6
7 8 9 10 7 8 9 10
A
B
A
B
激励 激励响应 响应时间 时间
（ a） （ b）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
64
习 题
1,假设一个文件服务器，如果所需的数据放在缓存中，对一个请求的接受、分派及其他处理需要花费 15ms;但在 1/3的情形下，还要做磁盘操作，需要 75ms,线程在这时处于睡眠状态。如果使用单线程，每秒能处理多少请求？而如果使用多线程呢？
2,假设完全在用户空间实现线程，运行系统每隔 1
秒得到 1个时钟中断。如果发生时钟中断时，某个线程正在运行系统中执行。这时会出现什么问题？给出一种解决方案。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
65
习 题
3,up-down算法是一种公平分配处理机的集中式算法。设计一种算法，虽然不公平，但能均匀地分布负载。
4,当一个分布式系统过载时，它尝试 m次去找到一个空闲的工作站。一个工作站拥有 k个工作的泊松分布概率为,P(k)=(λke- λ) / k!
这里 λ为每个工作站的平均工作个数。给出一个过载工作站找在 m次内到一个空闲工作站（即
k=0）的概率，并画出 m=3,λ=1,2,3,4时的曲线。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
66
习 题
5,一个实时系统中有如下 4个周期性进程，它们的计算要求和周期为：
P1：计算 =20ms,周期 =40ms
P2：计算 =60ms,周期 =500ms
P3：计算 =5ms,周期 =20ms
P4：计算 =15ms,周期 =100ms
该系统在一个 CPU上能调度吗？
2002年 6月
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
2
主要内容
4.1 进程和线程管理
4.2 分布式处理机管理
4.3 分布式容错系统
4.4 分布式实时系统
4.5 习题
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
3
4.1 进程和线程管理
进程模型。例,4个程序组成的多道程序
– 逻辑上,4个独立的、顺序的进程的概念模型
– 物理上，任意时刻只有一个是活动的
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
4
操作系统的进程结构
调度器：处理分时中断、调度
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
5
进程的状态
1 – 进程 a等待输入而 阻塞,
2 – 调度器选择另一个就绪进程 b
3 – 启动进程 b运行
4 – 当输入完成后,进程 a
进入 就绪 队列
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
6
进程的实现 —进 程表进程管理 内存管理 文件管理
Registers
Program counter
Program status word
Stack pointer
Process state
Priority
Scheduling parameters
Pointer to text segment
Pointer to data segment
Pointer to stack segment
Root directory
Working directory
File descriptors
User ID
Group ID
Process ID
Parent process
Process group
Signals
Starting time
CPU time used
Children’s CPU time
Time of next alarm
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
7
中断处理和调度
1,将当前 程序指针 压栈（硬件）
2,从 中断向量 取出新的程序指针（硬件）
3,保存当前 寄存器 （汇编,中断处理 ）
4,设置新的 栈指针 （汇编,中断处理 ）
5,执行 中断服务程序 （ C语言,中断处理 ）
6,调度器 决定下一个运行的进程（ C语言,调度器 ）
7,加载 寄存器和内存映像 （汇编,调度器 ）
8,启动新的 进程 （汇编,调度器 ）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
8
线程的概念
进程：相关的运行资源的管理单位
– 内存空间
– 打开的文件
– 子进程、信号处理、记账信息等
资源分组
线索：在 CPU上执行的脉络
– 程序计数器、寄存器、栈
执行
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
9
线程模型
多线程进程：一个线程被阻塞时，可运行同一进程中的另一 线程（ 阻塞?就绪?运行 ）
线程?进程； 进程?处理机；
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
10
线程模型
每个线程可共享所属进程的资源
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
11
线程模型
每个线程拥有自己的栈
– 局部变量、返回地址
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
12
线程的用途
例 1：包含 3个线程的字处理器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
13
例 2:多线程的 Web服务器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
14
多线程示例代码
(a),分派者 线程（ dispatcher） 源代码
(b),工作者 线程（ worker） 源代码
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
15
多线程服务器的组织方式
（ a） 分派者 /工作者 模型 （ b）团队模型
（ c）管道模型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
16
服务器组织的比较模 式 并行 非阻塞式系统调用 性能 编程容易程度单线程进程 低 √
多线程进程 √? 高 √
有限状态机 √ √ 高?
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
17
多线程的实现方式 1
用户空间
– 切换效率高
– 专门的调度算法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
18
多线程的实现方式 2
内核空间：
– 由内核管理
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
19
多线程的实现方式 3
混合方式
– 将用户级线程多个转接到内核线程上
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
20
例,调度器激活方法
目标,
–既有用户进程的优点 (高性能、灵活 ),
又有内核进程的优点（实现简单）。
方案：
–避免不必要的“用户 /内核” 间的切换
实现：
–Upcall机制：下层内核可调用上层用户运行系统
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
21
例,调度器激活方法
算法：
– 内核为每个 进程 分配虚拟的处理机；由进程的用户运行系统为 线程 分配处理机
– 当 线程 x在内核被阻塞后，调度器 Upcall其 运行系统,重新调度其他就绪线程
– 当 线程 x可运行后，调度器 Upcall其 运行系统,重新调度
– 当产生硬件中断后，如果与 进程 A有关，则 Upcall
其 运行系统,重新调度
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
22
线程的管理
线程包：
– 为用户编程提供的线程操作原语程序库
静态线程：
– 线程的数量在编译时预先确定
动态线程：
– 在运行时随时创建或撤销线程
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
23
线程的互斥控制
小型互斥变量 mutex
lock
unlock
用于进 /出临界区
条件变量
用于对资源的长期等待
与 mutex
lock mutex;
check data structures;
while(resource busy)
wait(condition variable);
mark resource as busy
unlock;
（ a） 获得资源
lock mutex;
mark resouce as free;
unlock mutex;
wakeup(condition variable);
（ b） 释放资源，唤醒线程
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
24
全局变量的冲突
例：全局变量 error
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
25
全局变量的冲突
解决方法：
设置私有的全局变量
例,提供库函数
1,创建一个线程的全局变量
create_global( ―bufptr‖ );
2,设置一个全局变量
set_global(―bufptr‖,&buf)
3,读一个全局变量
bufptr=read_global(―bufptr‖ )
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
26
Pop-Up 式线程与 RPC
作用,负责接收消息。例,receive_msg(addr,&buf)
（ a）消息到达前 （ b）消息到达后
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
27
Unix中的线程 API调用
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
28
Windows中的进程管理
基本概念
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
29
Job,Process,Thread的相互关系
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
30
Win32的 API调用
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
31
4.2 分布式处理机管理
工作站模型
– 无盘工作站
– 有盘工作站
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
32
工作站上磁盘的作用使用情况 优点 缺点无磁盘 费用低，灵活，易于软硬件维护网络负载重，文件服务器为瓶颈换页，保存临时文件 网络负载小 磁盘成本高换页，保存临时文件和执行文件网络负载更小 磁盘成本更高，执行文件的更新复杂换页，保存临时文件和执行文件，文件缓存。
网络负载更更小，
减少文件服务器负载成本高，缓存一致性维护复杂完全的本地文件系统 几乎无网络负载，
不需要文件服务器失去透明型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
33
空闲处理机
远程执行,rsh machine command
基于注册表算法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
34
工作站管理
处理机池模型
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
35
工作站管理
排队模型
平均响应时间 T= 1/(λ –μ)
n台处理机平均响应时间 T1= T/n
计算机 完成工作用户用户每秒共产生 μ 个请求系统每秒能处理 γ 个请求
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
36
工作站管理
混合模型：
– 前台交互式任务：个人工作站
– 后台任务：处理机池
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
37
处理机分配管理
分配模型
– 非迁移型
– 迁移型
分配目标
– 最大 CPU利用率
– 最快响应时间
– 响应比：实际运行时间 /实际需要时间
负载平衡
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
38
处理机分配
分配方案 1：处理机 1 运行进程 A，处理机运行进程 B，
平均响应时间 =（ 10＋ 8） /2＝ 9
分配方案 2,处理机 1 运行进程 B，处理机运行进程 A，
平均响应时间 = （ 30＋ 6） /2＝ 18
处理机 1
10MIPS 处理机 2100MIPS没有队列 5秒队列进程
A(1亿条指令 )
B(3亿条指令 )
10秒
30秒
6秒
8秒
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
39
处理机分配设计
1,确定性 vs 启发式 （ 试探性 ）
2,集中式 vs 分布式
3,最优 vs 较优
4,局部的 vs 全局的
5,发送者发起的 vs 接收者发起的
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
40
Eager的启发式算法
1,转发法,随机选择一台机器 A，向它发送新进程。如果 A已经过载,A也同样随机选择另一台机器 B，向 B发送进程。
2,查询法,随机选择一台机器 A，向它发送一个负载情况询问。如果欠载,A就会得到这个进程；否则，将重新选择一台机器。
3,比较法,询问 k台机器，确定它们的确切负载情况。将新过程传送到负载最小的那台机器上。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
41
基于图的确定性算法
例,3个处理机,9个进程
方案 A:通信量 =(3＋ 2＋ 4＋ 4)＋ (2＋ 8＋ 5＋ 2)＝ 30
方案 B:通信量 =(3＋ 2＋ 4＋ 4)＋ (3＋ 5＋ 5＋ 2)＝ 28
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
42
集中的启发式的 up-down算法
目标：工作站公平地享用系统的计算能力
使用情况表,〉 0表示使用资源； <0表示需要系统资源,0为初始值时间
P1到达
P1分配到处理器
P2到达 P2分配到处理器 P1完成
P2完成使用情况表积分
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
43
层次式的算法主任委员会部门领导工作人员
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
44
发送者 /接收者算法请求帮助请执行一个进程吧请完成一个工作吧此机器负担太重了求助机器判定它的负担太重
（ a）
今晚我空闲我无事可作机器宣告它可被使用我厌烦了需要
CPU周期？
需要帮助？
（ b）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
45
处理机的分配
协同调度（ co-scheduling）
– 将一组协同进程安排在不同处理机的同一时间片内以产生最小的时间延迟。
A C
B D
A C
B D
A C
B D
0 1
0
1
2
3
4
5
0 1
0
1
2
3
4
5
2 43 5 6 7
（ a）简单轮转 （ b）分组调度处理器 处理器时间片时间片
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
46
4.3 分布式容错系统
基本概念
– 差错（ error）：如程序 bug
– 故障（ fault）：
短暂型、间歇型、永久型
– 失效（ failure）
失效模型
– p为每秒失效概率
– 平均失效时间 = Σkp(1-p)k-1=1/p
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
47
系统失效
故障类型
– fail-stop故障
– 拜占庭故障
系统类型
– 同步系统：在规定时间内有响应
– 异步系统：设一个上限
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
48
冗余技术
冗余类型
– 信息冗余
– 时间冗余
– 物理冗余
设计问题
– 需要复制的程度
– 无故障时,平均情况和最坏情况下的系统性能
– 有故障 时，平均情况和最坏情况下的系统性能
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
49
主动复制容错技术
相同的部件
K-容错度：在有 k个部件发生故障时，系统仍能正确运行
Fail-stop型故障,k+1冗余度
拜占庭型故障,2k+1冗余度
有限状态机方法：接收请求，给出应答
– 所有的请求到达所有服务器的顺序应相同
– 原子广播问题（ atomic broadcast problem）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
50
主动复制方法
三模冗余方法
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
51
主备份方法（ primary backup）
主服务器失效，则后援服务器接替其任务
接管模型客户 主系统 后援系统
1.请求 2.执行 3.更新 4.执行
6.应答 5.确认
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
52
协同一致问题
两军问题
通信可靠
3000
5000
3000
1
2
3
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
53
Lamport递归算法
拜占庭将军问题
例,3个忠诚将军,1个叛变将军
– 结果,（ 1,2，未知,4）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
54
Lamport递归算法
若三个将军中，有两个忠诚将军，一个叛变将军，则不能判断出哪个将军叛变。
若要有 m个处理机出错的系统实现协同一致，最少要有 2m＋ 1个正常处理机。处理机总数为 3m+1
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
55
4.4 实时分布式系统
实时系统：
– 当某个激励出现时，系统必须以一定的方式在限定的时间内响应它。
– 如果超时，即使结果正确，也认为是系统失效
实时系统类型
– 软实时系统：允许偶尔错过截至时间（ deadline）
– 硬实时系统：严格不允许，如飞机导航
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
56
实时事件流
事件类型
– 周期的、非周期的、突发的
例,3个事件流 +1个意外事件时间
A
B
C
A
B
C
A
B
C
A
B
C
A
B
A
C
B
A
C
B
A A
C
B
X
无法预料的事件A的周期 B的周期 C的周期工作负荷空闲
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
57
分布式实时计算机系统结构
Dev
C
Dev
C
Dev
C
Dev
C
Dev
C
Dev
CC
外部设备计算机网络执行机构 传感器
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
58
分布式实时系统设计
事件触发系统
–当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的 CPU得到一个中断请求。
–通常是中断驱动的。
主要问题
–当 事件风暴（ event shower） 发生时，
在重载情况下会失效 。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
59
分布式实时系统设计
时间触发系统
– 每 ⊿ T毫秒产生一次时钟中断。在每一次时钟滴答时，对（选定的）传感器进行采样，并且驱动（特定的）执行机构。
– 中断仅在时钟滴答时发生 。
⊿ T的选择
– 必须非常小心地选择。若 ⊿ T太小，系统将产生许多时钟中断，将浪费大量的时间来响应它们
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
60
分布式实时调度
硬实时与软实时
– 保证所有时限都要满足
抢占的与非抢占的
– 允许在高优先级的任务到来时挂起当前的任务
动态的与静态的
– 在运行期间进行调度
集中的与分散的
– 各个处理机可以独立做出决定
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
61
分布式实时调度
可调度性
N个处理机
M个运行任务
任务 i所需 CPU时间 Ci,周期为 Pi
系统利用率 μ
N
p
cm
i i
i
1
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
62
动态调度
比率单调算法
– 每个任务分配一个与其执行频率相等的优先级
– 动态抢占式调度
最早时限优先法 （ earliest deadline first）
– 等待队列根据这些任务的时限排序
最小余度法 (least laxity)
– 优先调度具有最小剩余时间量的任务
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
63
静态调度
已知所有任务的列表及它们各自的运行时间
启发式方法
非抢占式静态调度
3
A
1
2
5
4
6
7 8 9 10
B
激励响应
1 2 3 4 5 6 1 3 5 2 4 6
7 8 9 10 7 8 9 10
A
B
A
B
激励 激励响应 响应时间 时间
（ a） （ b）
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
64
习 题
1,假设一个文件服务器，如果所需的数据放在缓存中，对一个请求的接受、分派及其他处理需要花费 15ms;但在 1/3的情形下，还要做磁盘操作，需要 75ms,线程在这时处于睡眠状态。如果使用单线程，每秒能处理多少请求？而如果使用多线程呢？
2,假设完全在用户空间实现线程，运行系统每隔 1
秒得到 1个时钟中断。如果发生时钟中断时，某个线程正在运行系统中执行。这时会出现什么问题？给出一种解决方案。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
65
习 题
3,up-down算法是一种公平分配处理机的集中式算法。设计一种算法，虽然不公平，但能均匀地分布负载。
4,当一个分布式系统过载时，它尝试 m次去找到一个空闲的工作站。一个工作站拥有 k个工作的泊松分布概率为,P(k)=(λke- λ) / k!
这里 λ为每个工作站的平均工作个数。给出一个过载工作站找在 m次内到一个空闲工作站（即
k=0）的概率，并画出 m=3,λ=1,2,3,4时的曲线。
2002-6-28
东北大学软件所 于戈 第四章 分布式进程管理
66
习 题
5,一个实时系统中有如下 4个周期性进程，它们的计算要求和周期为：
P1：计算 =20ms,周期 =40ms
P2：计算 =60ms,周期 =500ms
P3：计算 =5ms,周期 =20ms
P4：计算 =15ms,周期 =100ms
该系统在一个 CPU上能调度吗？
