高级操作系统AdvancedOperatingSystem

1、高级操作系统Advanced Operating System熊 焰国科学技术大学计算机学院分布式系统模型分布式处理机分配分布式进程调度分布式系统容错实时分布式系统第四章 分布式进程和处理机管理模型的作用精确地定义要建立或分析的系统的属性和特征提供检验这些属性的基础代表性的模型数学函数型有限状态自动机(FSM)图模型4.1分布式系统模型数学函数型y1,y2,yn=f(x1,x2,xn)f(x1,x2,xn)=f1(f2(f3(x1,x2,x3,xn)特点：分层分层的好处：组织大量数据检查层次间输入与输出的一致性缺点：不保存数据4.1分布式系统模型有限状态自动机 (

2、FSM)4.1分布式系统模型有限状态自动机 (FSM)优点：对于说明数据处理是非常理想的限制：固有地串行化了所有并发明确假设一个输入的所有处理在下一个输入到达之前完成4.1分布式系统模型图模型4.1分布式系统模型图模型局限性：它没有体现“状态”的概念4.1分布式系统模型分布式系统模型的分类工作站模型处理机池模型两者混合模型4.1分布式系统模型4.1.1 工作站模型工作站模型的优点清晰用户响应时间能得到保证每个用户都有很大的自主权缺点空闲工作站难以充分利用4.1.1 工作站模型方法利用伯克利UNIX中的rsh程序寻找空闲工作法的算法服务器端驱动的算法客户端驱动的算法4.1.2 空闲工作站的利用利

3、用伯克利UNIX中的rsh程序rsh machine command第一个参数指定要使用的工作站第二个参数表示在指定工作站上运行的命令Rsh程序的功能就是在指定机器上运行指定的命令4.1.2 空闲工作站的利用利用伯克利UNIX中的rsh程序较严重的问题：必须由用户来寻找一台空闲的机器运行环境可能不同远程机器可能非空闲4.1.2 空闲工作站的利用利用空闲工作站得考虑如下问题:怎样找到一个空闲工作站； 怎样透明地运行一个远程进程；如果空闲工作站的主人回来重新使用它，怎么办？ 4.1.2 空闲工作站的利用寻找一个空闲的工作站工作站空闲的标准没有用户登录？没有用户操作且没有用户进程运行4.1.2 空闲

4、工作站的利用寻找空闲工作站的算法服务器端驱动的算法客户端驱动的算法4.1.2 空闲工作站的利用服务器端驱动的算法方法1空闲工作站注册将自己的名字、网址、属性输入到一个注册用户输入命令查找remote command4.1.2 空闲工作站的利用服务器端驱动的算法方法2空闲工作站向整个网络发一条广播消息所有的工作站都保存这个消息优点寻找空闲工作站的开销更少，冗余度更高缺点所有的机器都需要维护一个私有的注册文件潜在的冲突4.1.2 空闲工作站的利用客户端驱动的算法客户端运行remote时，发送广播声明它需要运行哪个程序，需要多少内存，是否需要浮点运算等等当收到应答后，remote就从中挑选一个启动命

5、令在选中的空闲工作站上运行Trick: 服务端应答时，让应答的延迟与自己当前负载成正比4.1.2 空闲工作站的利用透明地运行一个远程进程代码移动比较容易如何设置远程运行环境？相同的文件系统，工作目录，环境变量特殊情况本地运行：读取键盘，写屏幕远程调用：SBRK（调整数据段大小）NICE（设置CPU调度优先级）PROFIL（程序计数器计数）4.1.2 空闲工作站的利用透明地运行一个远程进程代码移动比较容易如何设置远程运行环境？相同的文件系统，工作目录，环境变量特殊情况时间有关的系统调用MAKE4.1.2 空闲工作站的利用如果空闲工作站的主人回来重新使用它，怎么办？ 方案1：什么都不做方案2：强行

6、取消正在运行的非本地进程远程通知，然后关闭方案3：迁移4.1.2 空闲工作站的利用4.1.2 处理机池模型处理机池模型是无盘工作站模型的进一步发展。实际上，我们是把所有的计算能力转换成了可以动态访问的“空闲工作站”。4.1.2 处理机池模型使用排队论来描述和分析在一个排队系统中，用户随机地向服务器请求服务当服务器忙时，用户必须排队等待服务按顺序被服务4.1.2 处理机池模型4.1.2 处理机池模型排队系统的定义用来描述顾客到达、等待、被服务以及离去过程的模型排队系统的假定顾客源无限大，它意味着排队顾客非常多也不影响顾客的到达率4.1.2 处理机池模型排队系统的三大要素到达间隔时间的概率密度函数

7、服务时间的概率密度函数服务员个数4.1.2 处理机池模型排队系统表达方式：A/B/mA是到达间隔时间的概率分布B是服务时间的概率分布M-指数型概率分布D-等值型概率分布G-一般分布m是服务员个数本课讨论M/M/1模型4.1.2 处理机池模型M/M/1系统参数到达间隔时间的概率密度函数fA(t)=e-t均值为1/是平均到达率服务时间的概率密度函数fs(t)=e-t4.1.2 处理机池模型Littles Result令p= /顾客等待时间的概率密度函数fw(t)=p(1-p)e-p(1-p)t顾客响应时间的概率密度函数fT(t)= fs(t)fw(t)= (1-p)e- (1-p)t，t=0平均响

8、应时间T=fT(t)dt=1/（-）4.1.2 处理机池模型例题：假设有一个小水坑，鸟儿随机飞来就浴，平均到达率为3只/分钟。鸟儿平均洗浴时间为10秒/只，指数分布。求平均一只鸟需要等待多长时间才能洗上澡？平均到达率=3只/分钟=0.05只/秒平均服务率=1/10=0.1只/秒平均响应时间T=20秒平均等待时间为20-10=10秒/只4.1.2 处理机池模型排队论可作为延迟分析的理论工具T=fT(t)dt=1/（-）4.1.2 处理机池模型一个重要的分析结果：n个独立排队系统每一个系统都是一个请求到达速率为处理机处理速率为则，平时响应时间为T=1/（-）4.1.2 处理机池模型一个重要的分析结

9、果：将n个独立排队系统集中起来请求到达速率为n处理机处理速率为n则，平时响应时间为T1=1/n（-）=T/n4.1.2 处理机池模型这个结果具有一定普遍性并已应用到很多的系统中例：航空公司更愿意每5个小时飞一架300座的747飞机，而不愿意每10分钟飞一架10座的商业飞机。当把处理能力分配给多个小服务器，使得每一个用户拥有一个，这与随机到达的请求不相匹配。而处理机池模型可以减少这种时间的浪费，这也是它总体性能更高的原因4.1.2 处理机池模型事实上，排队论的结果正是完全否定分布式操作系统的主要理由之一。但是，响应时间并不代表一切制造成本响应时间的一致性 V.S. 平均响应时间之前结果一个前提假设所有的请求被