第 11章 分布式系统中的进程及处理器
研究分布式系统中线程
怎样组织处理器和进程
分布式系统中的处理器分配和调度
11.1 线程 (1)
例：服务器有时因等待磁盘而进入阻塞状态如果服务器有多个线程当一个线程睡眠时第二个线程就可以投入运行引入多线程为了得到更大的吞吐量和更高的效率
(a)三个各只有一个线程的进程
(b)一个拥有三个线程的进程线程 (2)
线程
一个进程的线程都在同一个地址空间中拥有自己的程序计数器和堆栈线程严格按顺序执行
在多处理器系统中,它们真正并行执行
线程可以建立子线程,因等待系统调用而阻塞
当一个线程被阻塞时,同一进程中的另一个线程可以运行线程 (3)
线程共享 CPU
可以共享相同的全局变量
共享同一个打开文件集,子进程,定时器,
信号等线程 (4)
每个线程都可以存取任何一个虚拟地址一个线程能够读,写,甚至完全破坏另一个线程的堆栈
在线程之间没有设置保护措施
（ 1） 不可能； （ 2） 没必要
进程通常来自不同的用户,可能会发生冲突
用户建立多个线程是为了协同工作,而不是冲突线程 (6)
线程包括的项程序计数器堆栈寄存器集子线程状态进程包括的项地址空间全局变量打开文件子进程定时器信号信号量计帐信息线程 (8)
线程状态：运行,阻塞,就绪,完成
运行状态,正在使用 CPU,处于活动状态
阻塞状态,等待另一线程激活它
就绪状态,已被调度,只要一轮到就运行
完成状态,已退出,但还没被父线程收回
11.1.2 线程使用进程中线程的三种组织方式
(a) 调度员／工作者模式
(b) 队列模式
(c) 管道模式
(a)调度员／工作者模式
(b)队列模式
(c)管道模式有限状态机 (1)
假定不能使用多线程单线程造成了无法接受的性能就下降可把服务器看作一个有限状态机当请求到达时,唯一的线程检查请求信息如果缓存中数据能满足要求,就接着处理如果不能满足要求,它给磁盘发送消息有限状态机 (2)
然而,这时它并不进入阻塞状态仅在表中记下请求的状态,处理下个请求如果是新的工作请求,就开始新工作若是磁盘的反馈信息则从表中取出相关信息,答复请求有限状态机 (3)
不允许发消息后因等答复而进入阻塞
调用原语也必须是非阻塞式调用
对接收和发送的消息必须在表格中保存或恢复状态
以困难的方式模拟多线程和它们的堆栈进程以有限状态机方式运行根据接收作出相应反应构造服务器的三种方式模式 特性多线程 并行，阻塞式系统调用单线程处理 非并行，阻塞式系统调用有限状态机 并行，非阻塞式系统调用
11.1.3 线程包的设计问题给用户的线程的原语集叫线程包静态线程
在程序编制或编译阶段就决定使用多少个线程
给每个线程分配固定的堆栈
方式简单,但不灵活动态线程 (1)
在运行中动态创建和注销线程
需要指定线程主程序 （ 作为指向过程的指针 ）
堆栈的大小,指定参数,如调度的优先级等
调用通常返回一个线程标识符标识符在该线程的调用中被用到
进程启动时只拥有一个 (隐含 )线程可据需要创建多个线程线程的终止
当线程完成任务时,可自行退出
或者被杀掉互斥信号量 (1)
多个线程使用同一内存块保存共享的数据要防止多个线程同时存取同一个数据经常使用得技术：互斥信号量互斥信号量 (2)
一种小型信号量
信号量在两个状态之一：关锁和开锁
二元信号量 （ 即只有 0,1两个值的信号量 ）
两种操作被定义为互斥互斥信号量的改变是一个原子动作
LOCK,试图锁住互斥信号量如果互斥信号量处于开锁状态
LOCK将成功执行互斥信号量 (3)
在多处理器系统中多个线程运行在不同的 CPU上
如果两个线程在同一个实例上试图加锁同一个互斥信号量只有一个线程能赢,别的将失败
如果线程试图加锁已被锁住的互斥信号量它将被阻塞互斥信号量 (4)
UNLOCK操作解锁一个互斥信号量
如果一个或多个线程在一个互斥信号量上等待,只有一个线程解锁,其余的线程继续等待
TRYLOCK操作
该操作试着加锁一个互斥信号量
如果该互斥信号量未被锁定
TRYLOCK返回状态码,说明操作成功
若该互斥信号量是锁着的
TRYLOCK并不阻塞该线程而返回指示失败的状态码
容易实现条件变量 (1)
一个线程锁住互斥信号量进入临界区在临界区,发现所需资源已被占用锁住第二个互斥信号量 （ 与被占资源相关的 ）
外面的互斥信号量将保持在关锁状态拥有被占资源的线程不能进入临界区释放它产生了死锁如果解锁外面的互斥信号量别的线程进入临界区,又会引起混乱
Lock mutex;
check data structures;
while(resource busy)
wait(condition variable);
mark resource as busy;
unlock mutex;
(a)
Lock mutex;
mark resource as busy;
unlock mutex;
wakeup(condition variable);
(b)
互斥信号量和条件变量的使用条件变量 (2)
解决方案：使用条件变量来申请资源
条件变量定义原子性的自动地等待和解锁互斥信号量
当使用资源的线程释放资源后它执行 wakeup操作
wakeup 定义：一次可以唤一个线程也可唤醒特定的条件变量上等待的所有线程使用 WHILE而不用 IF
防止线程被唤醒但还没运行时,别的线程抢占资源条件变量 (2)
在创建条件变量时每个条件变量常和一个互斥信号量关联
互斥信号量和条件变量的差别互斥信号量用于短期的加锁,主要用于保护临界区的入口条件变量用于长期的等待,一直到资源可用为止线程与全局变量 (1)
一个线程通常拥有多个过程过程含有局部变量,全局变量和过程参数若变量对线程来说是全局的但对整个程序来说是非全局的,会带来困难使用全局变量引起的冲突线程 1 线程 2
访问 写 errno
打开读 errno
时间 errno重 写线程与全局变量 (2)
例子,UNIX维护 errno 的变量线程 1执行系统调用 ACCESS
检查是否对特定文件有访问权返回结果在全局变量 errno中当控制权回到线程 1,而它还没有读 errno 时线程 1已用完了时间片,控制权交给线程 2
线程 2执行 OPEN调用失败,errno被改写线程 1永远丢失访问权代码线程与全局变量 (3)
方法 1,禁止使用全局变量和许多现存的软件相冲突,如 UNIX
方法 2,每个线程定义私有的全局变量每个线程都有 errno 的私有拷贝与别的全局变量,避免了冲突
分配全局性的内存块作为额外的参数传递给线程中的每个过程
方法不是很好,但可用线程与全局变量 (4)
方法 3:
引入创建 (create)
设置 (set)
读取 (read)全局变量的库函数线程与全局变量 (5)
创建 (create)：
create-global (“bufptr”)
为指针变量 bufptr分配内存从堆或特定存储区中分配只有调用线程才能存取这个全局变量如果别的线程使用同名创建全局变量将从不同的存储区中分配,这样不会冲突线程与全局变量 (5)
两个调用存取全局变量：写,读
写,设置 (set)调用：
set-global (“bufptr”,&buf);
读取 (read)：
bufptr = read-global (“bufptr”);
11.1.4 线程包的实现两种实现线程包方法：
用户空间
内核
（ a）用户层的线程包 (b)由核心管理的线程包内核
Run Time系统内核线程 线程
0 1 2 3 4 5 0 1 2 3 4 5
用户空间内核空间用户空间内核空间
（ a） (b)
用户空间中线程包的实现 (1)
内核一无所知只知正在管理一般的单线程进程
优点：在不支持线程的系统中可实现用户层线程包
例,UNIX不支持线程却有各种用户线程包运行用户空间中线程包的实现 (2)
线程运行于 run-time系统之上管理线程的过程集合当线程执行系统调用,进入睡眠状态它调用运行系统的一个过程首先确定此线程是否要挂起需要挂起,线程的寄存器存在一个表中用户空间中线程包的实现 (3)
在表中查找未被阻塞的线程查到后把此线程的寄存器的装到机器的寄存器中当栈指针程序记数器相应设置后新线程投入运行如果机器中有专门一次保存和装入所有寄存器的指令线程切换只用极少的指令就可完成用户空间中线程包的实现 (4)
好处,
线程切换比内核陷入快得多
允许进程有定制的调度算法
线程在用户层增加了可扩展性内核管理线程 (1)
对每个进程,内核用表保存线程的入口有寄存器,状态,优先级以及其他信息
能阻塞线程的调用以系统调用方法实现因而调用的费用大内核管理线程 (2)
线程阻塞两种可能
运行同一进程的另一个线程 （ 如果它已就绪 ）
或者运行其他进程的线程在用户层线程方式中运行系统总是运行同一进程的线程直到内核把 CPU交到别处为止用户层线程包与内核线程问题 (1)
问题,阻塞设线程从一空管道中读数据或执行了可引起阻塞的操作在内核式实现中内核阻塞此线程并启动另一个在用户空间实现中无法接受让线程执行系统调用因为会中止所有的线程用户层线程包与内核问题 (2)
使用线程的目的为了被阻塞的线程不影响到别的线程阻塞系统调用,不能达到这个目的可把系统调用全部转换成非阻塞的
（ 举例来说,读一个空管道时只是失败 ）
但要求改变操作系统不吸引人用户层线程的吸引力之一是可运行在已有的操作系统上用户层线程包与内核问题 (3)
改变 READ的语义会使许多用户程序要改变可选的方法,
在调用前系统告知此调用是否会引起阻塞只有不会阻塞时才使线程行动方法要改写系统调用部分函数效率不高,效果不好但除此也无别的选择用户层线程包与内核问题 (4)
用户层线程包的另一个问题是如果一个线程开始运行同一个进程中别的线程不能运行,除非运行的线程主动放弃 CPU
一种解决方案请求时钟信号 （ 中断 ） 来得到控制权但这样做,程序会很繁乱
11.2 系统模型讨论
工作站模型
处理器池模型
混合模型
11.2.1 工作站模型系统由许多工作站组成这些工作站由高速 LAN连接起来工作站或有一个用户登录,或处于空闲状态个人工作站网络，每台自带本地文件系统空闲工作站网络无盘工作站
要在网上设置文件服务器提供文件服务文件读写请求送往服务器,完成后返回结果
无盘工作站广泛使用
原因,价格,易于维护对称性和适应性好用户可登录任何一台工作站所有文件在文件服务器上所有的工作站都一样有盘工作站 (1)
盘的四种使用方式：
第一种
本地盘只用作页面交换和临时文件是非共享的
用户退出登录时,文件可被丢弃有盘工作站 (2)
第二种：第一种的变体
交换,临时文件,系统二进制文件
本地盘也用来保存二进制 （ 可执行 ） 程序如,编译器,文本编辑器,电子邮件当调用这些程序时,直接读取本地盘
无须从服务器上得到,减轻网络负载
需要管理什么机器上拥有什么程序的什么版本有盘工作站 (3)
第三种方法：本地盘作外部高速缓存
从服务器下载文件到本地盘在本地读写,再上载修改过的文件
集中保存本地长期使用的文件,减轻网络负载
缺点：要保持缓存的一致性如两个用户下载同一个文件然后做了不同的修改,会产生问题有盘工作站 (4)
第四种,每台机器有自己的文件系统有可能装载和存取别的机器的文件系统
思想：机器基本上是自给型的和外界保持有限的接触
缺点,共享困难
和网络操作系统相近,不是透明的分布式系统工作站模型的优点
容易理解
用户拥有固定的计算能力和好的响应时间
可直接访问屏幕,复杂的图形程序能高速运行
用户有大的自主权,可随意分配资源
本地盘增加了工作站的独立性
当服务器崩溃时,工作站依然可进行工作工作站上磁盘的使用磁盘使用 优点 缺点无磁盘 费用低，软硬件维护容易，对称，有灵活性网络负载重；文件服务器可能成为瓶颈页面交换，临时文件 比无盘方式的网络负载小 大量的磁盘导致费用高页面交换，临时文件，
二进制文件网络负载更小 费用高；增加了更新二进制文件的复杂性页面交换，临时文件，
二进制文件，文件高速缓存网络负载小；从文件服务器上装入的文件少高费用；缓存一致性问题完全的本地文件系统 几乎无网络负载；消除了对文件服务器的依赖失去透明性
11.2.2 空闲工作站的使用 (1)
观察显示,即使在最忙时仍有 30％ 以上工作站空闲早期试图使用空闲工作站的是 Berkeley UNIX 的 rsh 程序
rsh 程序
rsh machine command
第一个参数指定机器,第二个参数指定运行的命令程序存在严重缺陷首先,必须指定机器,跟踪空闲机器的负担压在用户身上其次,远程机器的环境和本地环境可能不同最后,如果要在运行远程进程的机器上登录,
远程进程又要继续运行用户要接受低效率,要么找别的机器空闲工作站的使用 (2)
怎样查找空闲工作站？
怎样才能透明地执行远程进程？
如果机器的主人回来,该怎么办？
怎样查找空闲工作站呢？
不同的系统,空闲,定义不同如果没有人在一段时间内使用键盘或鼠标或者没有用户进程在运行就可以说这台工作站是空闲的空闲工作站定位算法
两类：
服务器驱动和客户驱动
服务器驱动服务器主动告知可为他人服务
客户驱动客户主动 查找空闲工作站 务服务器驱动算法 (1)
工作站空闲,成为潜在计算服务器它告知别人可用性可把名字,网络地址,属性放在一个注册文件中 （ 或数据库 ）
当一户想在空闲工作站上执行命令时输入以下命令：
remote command
remote程序查找注册文件可保存注册文件的多个拷贝,增加可靠性服务器驱动算法 (2)
新空闲的工作站可在网上广播消息别的工作站记录消息每台机器维护一个私有注册表好外是寻找空闲工作站的代价小且冗余性好缺点是每台机器都要注册表的维护工作服务器驱动算法 (3)
缺点：竞争的危险二个用户同时使用 remote 命令发现同一台空闲工作站试图在该机器上同时启动他们的进程为避免这种情况
remote程序检测空闲工作站若仍然是闲着的从注册表中删去并给一个前进标志这时,调用者可传送环境并启动远程进程查找并使用空闲工作站的基于注册表的算法注册注册表空闲工作站列表注册表远程机注册表空闲工作站
1,空闲时机器注册2,请求空闲工作站得到响应
3,公告
4,撤消注册
5,设置环境
6,开始进程
7,进程运行
8,进程退出
9,修改原注册客户驱动算法激活 remote,广播请求说明要运行程序,需要内存是否要浮点协处理芯片等等回复到达,remote选出一台工作站运行让,空闲,工作站在作答复时作些轻微的延迟延迟的长短和它们的负载成正比负载轻的机器的回复到,并被先选用进程在工作站上执行 (1)
转移代码很容易困难在于使设置环境与本地环境相同要相同的文件系统相同的工作目录相同的环境变量 （ shell变量 ）
进程在工作站上执行 (2)
当执行系统调用时,内核该做什么？
答案与系统体系结构有关
无盘工作站,所有文件都在服务器中内核只要向相应的服务器请求
若有本地盘,且是完整的文件系统请求直接回送到主体工作站进程在工作站上执行 (3)
有些系统调用必须回送到主体工作站运行举例,读键盘和写屏幕永远都不能在远程机器上执行
另一些系统调用必须远程执行
不同机器的时钟可能不同步与时间有关的系统调用也会引起问题
使程序在远程机器上就象在本地机器上一样执行是可能的这是个复杂且需要技巧的工作进程在工作站上执行 (4)
问题：如果机器的主人回来怎么办？
最简单：就是什么也不做
另一个可能方法：消灭侵入的进程不预先警告就直接杀掉 。 缺点是工作丢失,文件系统混乱
较文明的方法：给进程发出明确的警告让它知道将面临的厄运,然后体面地关闭进程如果几秒钟后还没退出,就中止它当然程序要有处理信号的能力许多程序肯定没有这种能力进程在工作站上执行 (5)
另一方法：把进程转移到另一台机器上
当进程离开时应保持机器的状态和使用它之前的状态相同
不仅该进程要离开所有子孙也必须离开
邮箱,网络连接和别的系统级的数据结构也必须删除
11.2.3 处理器池模型 (1)
问题：,当可供 CPU比用户多 10倍或 100倍,
会怎样？,
每人一个私人的多处理器计算机方案不太有效
另一种方法：
构造一个处理器池 （ processor pool）
跟据用户的需要动态分配模型接近于分时模型
X终端 处理器池 文件服务器CPU
基于处理器池模型的系统
11.2.3 处理器池模型 (2)
所有的 CPU在一起降低能源和包装成本且能提供更强的计算能力易扩充,如果计算负载增加了 10％
只要再买 10％ 的处理器在可动态访问的,空闲工作站,上用户可根据需要暂时得到所需的 CPU
用完后,放回池中,以便别的用户来使用没有所有权概念：所有的处理器属于每个人
11.2.3 处理器池模型 (2)
处理器池在互联网上的版本：
目前已有在互朕网站点上提供计算能力
甚至提供应用程序而客户浏览器方连应用软件都不用配备
Web计算模式 - Browser/Server计算模式
11.2.3 处理器池模型 (3)
处理器池集中计算能力的依据是排队论
用户随机地向服务者发出工作请求如果服务者忙,用户排队等候并按顺序处理
例子,
铁路售票处机场检票柜台超市结算台等排队论 (1)
用户以每秒? 个速率输入请求服务者每秒处理? 个请求为顺利运作,必须有? >λ
排队论 (2)
如果服务器每秒处理 100个请求但每秒产生 110个请求,队列会无限增长在小的时间段中输入速率大于服务速率是可接受的只要平均输入速率小于服务速率,并提供足够的缓存基本的排队系统计算机 工作完成用户产生全部
请求 /s
进入队列系统可处理
请求 /s
排队论 (3)
可以证明 （ kleinrock,1974）
从发出请求到得到响应的平均时间
T和 λ,?有关公式如下：
1
T
排队论 (4)
举例,设服务器每秒能处理 50个请求当 λ趋近 0时 （ 无负载 ）,服务器的响应时间并不趋近 0
而是 1／ 50秒或 20毫秒原因显而易见即使没有竞争,响应时间,包括处理时间永远不会低于 20毫秒排队论 (5)
设 n台多处理机每个 CPU组成独立的队列系统请求到达率为 λ,CPU处理率为?,平均响应时间为 T
把所有的 CPU都放在同一个处理器池中只有一个大的队列系统排队论 (6)
输入速率为 nλ,服务速率为 n?
平均响应时间为 T1,我们得到把 n个小资源组成一个有 n倍能力的大资源可把平均响应时间减少 n倍
n
T
nn
T?
1
1
排队论 (7)
结果普适航空公司宁愿每 5小时飞一班 300座的 747，
也不愿意每 10分钟飞一班 10座的商业喷气机原理之一如此
11.2.3 处理器池模型特点 (1)
每个用户一台小服务器虽能提高效率对于请求随机到达的系统来说是很差的匹相配多数时间中只有很少的服务器忙,过载大多数空闲处理器池可消除浪费,
排队论是反对分布式主要依据之一
11.2.3 处理器池模型特点 (3)
可靠性和容错性也是要考虑的因素在一台大的,集中式共享计算机上编辑显示一页在 95％ 的时间里需要 5毫秒有时又需要 5秒钟用户认为性能不可接受若要运行大的 make或巨型的模拟程序大型计算机是最好的选择
11.2.3 处理器池模型特点 (4)
决定因素,工作负载的性质
如果工作只是简单的编辑并偶尔发个电子邮件使用个人工作站是最合适的
如果一个大的软件开发工程在大量的目录中经常运行 make程序或求一个大型稀疏矩阵的逆阵或大的模拟计算,求解大型人工智能问题处理器池模型富有吸引力
11.2.4 混合模型
给每个用户提供一台工作站,附加处理器池
综合了两者的优点
交互性在工作站上,以保证响应时间
非交互式的在处理器池运行
既提供快速交互,又有效使用资源,且设计简单
11.3 处理器分配
把进程赋给处理器的算法
设：所有的机器至少代码兼容不同仅是速度
设：系统是紧密互联任何一对机器间可建立联接通信处理器分配策略 (1)
二类处理器分配策略
第一类是非迁移算法进程创建时就已定好它的位置把它放在某机器上它一直在那台上运行,直到终止处理器分配策略 (2)
另一类是迁移分配算法即使进程已开始运行,也可移动
迁移策略能更好平衡负载,但也复杂
算法优化的目标：提高 CPU利用率减少平均响应时间处理器分配策略 (3)
响应比定义,进程在某机器上所用时间被该进程在基准处理器上运行时间相除
响应比更有意义
设想一个 1秒的任务响应时间为 5秒一个 1分的任务响应时间为 70秒哪个更好呢？ 用响应时间来衡量,前者较好
用响应比来衡量,后者好因为 5／ 1 >>70/60
11.3.2 处理器分配算法的设计原则 (1)
确 定 性 算 法 （ Deterministic ） 和 启 发 算 法
(heuristic)
集 中 式 处 法 (Centralized) 和分布式算法
(distributed)
最优化算法 (Optimal)和次优化算法 (sub optimal)
局部性算法 (local)和全局式算法 (global)
发送者启动算法 (Sender-initiated)和接收者启动算法 （ receiver-initiated）
请帮助我能否取走一进程?
过载了！
Help!
机器认定负载太重我无事可做！
今晚我有空真无聊！
机器找活干
(a) (b)
发送者寻找空闲工作站 接收者寻找工作
11.3.2 处理器分配算法的设计原则 (2)
对进程的行为能事先了解时采用确定性算法
没有系统能事先了解所有的信息但可做合理的估计
例,在银行,保险和机票预定系统中每天的工作大致一样可在统计上准确描述工作负载使得确定性算法成为可能
系统中不能预测工作负载有必要使用启发式算法
11.3.2 处理器分配算法的设计原则 (3)
集中式与分布式
在一地集中所有的信息容易选择一个好方案但也脆弱,中央处理机的负载会过重
常采用分布式算法在分布式算法不适应时才采用集中式算法
11.3.2 处理器分配算法的设计原则 (4)
找个最好的,还是找个可接受的？
最优化方法太困难
大多数采用启发式,分布式,次优化算法
11.3.2 处理器分配算法的设计原则 (5)
传输策略创建进程时,要决定能否在创建机器上运行可根据本地信息,也可参考全局信息
简单的算法：本地化算法如果机器负载在某界限以下,保留新进程否则就放弃
较好的方案：决定本地机是否太忙碌之前先收集有关负载的全局信息
局部性算法简单,但性能不好全局性算法能性能高但代价大
11.3.2 处理器分配算法的设计原则 (5)
定位策略当根据传输策略放弃进程要根据定位策略把它发往何处
定位策略不能是局部性的要参考别外的负载情况来做聪明的决定
两种信息传播方法由发送者开始信息交换由接收者启动交换过程
11.3.3 处理器分配算法的实现问题 (1)
负载过重还是负载过轻
简单的处理：
计算每台机器上的进程数目作为负载
但进程数和当前的负载无大关系
11.3.3 处理器分配算法的实现问题 (2)
只计算正在运行就绪的进程只要是正在运行或将要运行的进程即使是后台进程也会增加负载
许多后台进程是周期性醒来然后检查是否有它关心的事情发生如果没有,就重新睡眠 。
它们增加的负载很小
11.3.3 处理器分配算法的实现问题 (3)
用 CPU忙碌时间片表示负载一台 CPU使用率为 20％ 的比 10％ 的负载大
计算 CPU利用率的方法,
定时中断机器,每次中断,把 CPU的状态记录下
问题当内核执行临界代码时,常屏蔽所有中断会低估 CPU的利用率
11.3.3 处理器分配算法的实现问题 (4)
额外费用把新进程移到远程机器上能提高 10％ 的效率可是移动进程的开销更大,最好不动
好算法应计算算法本身耗费的 CPU时间内存使用,网络带宽
这样做不容易,很少这样做复杂性一个新算法,经过证明性能非常好但结论却是不要采用这个算法原因实现很复杂
11.3.3 处理器分配算法的实现问题 (5)
Eager算法在任何情况下每台机器检查自己并判断是否轻负载每当创建新进程创建机器检查自己是否超负载如果是寻找一台机器,在其上启动这个新进程
11.3.3 处理器分配算法的实现问题 (6)
三个定位侯选机算法
算法 1：
随机挑一台机器,把新进程发过去如果接收机超负载它也随机挑选一台机器,把进程送走一直进行到有愿意接收或者步长计数器越界
11.3.3 处理器分配算法的实现问题 (7)
算法 2：
随机挑一台机器并发信息询问是否过载如果负载不重,就接收该进程否则进行新的探测循环进行到找到合适的机器或不能再进行为止后一种情况下,进程在创建处不动
11.3.3 处理器分配算法的实现问题 (8)
算法 3：
询问 K台,进程发给负载最轻的机器直觉算法 3的性能最好实际上也是如此
算法 3和算法 2相比,性能提高不多,但复杂性很多
结论：简单算法和复杂且昂贵算法相比性能相差不大时,用简单算法
11.3.3 处理器分配算法的实现问题 (9)
稳定性问题系统可能进到一种状态
A和 B都没有新的信息两者都认为对方的负载轻会把可怜的进程在它们间多次传来传去图论确定性算法 (1)
基本思想：降低网络通信量用一个加权图来表示结点代表进程,弧代表两个进程间的信息流从数学的角度来看,问题简化为在一定限制下找把该图划分成 K分非连通子图的方法所有进程的 CPU和内存要求均低于各个子图的限制在符合要求的方案中子图内部的弧表示在机器内部通信忽略不计从一子图连到另一子图的弧代表网络通信量图论确定性算法 (2)
目标：
满足所有条件找出一种网络通信量最小的划分
寻找耦合紧密的簇 （ 簇内的流量大 ）
而这些簇与别的簇联系很少 （ 簇之间的流量小 ）
图论算法要事先了解完整的信息应用受到限制集中式算法 (1)
启发式算法,不需要预先了解信息
算法是集中式的原因在于设置有协调器,维护使用表
每个工作站在表中占一栏开始时为空当有重要的事发生时给协调器发送消息更新表分配都以该表为依据集中式算法 (2)
在有以下调度事件发生时做决定：
请求一个处理器,一个处理器已变为空闲,
或时钟中断不以最大限度地使用 CPU为目标而是给每个工作站提供公平的共享计算能力上下算法 (1)
当一台工作站主在别的机器上运行进程时它累计了罚点 （ penalty points）
点数加到使用表对应项中当有未被满足的要求时从使用表对应项减去一定数目的罚点当没有被挂起的请求也没有正在使用的处理器时从使用表对应项中减去一定数目的罚点,直到为 0
得分数或上或下,称上下算法进程 1到达进程 1被分配处理器进程 2到达进程 2被分配进程 1完成进程 2完成 时间使用表上下算法的执行上下算法 (2)
使用表对应项数值可为正,0,或负正：该工作站是一个纯系统资源用户负：表示它需要资源
0：表示中性现进行启发式处理器分配当一处理器空闲时,拥有得分最低的请求将获得该处理器没占用处理器且请求挂起时间最长的用户会击败已使用了许多处理器的用户算法的目标：公平分配资源集中式算法 (4)
集中式算法很难扩充成大的系统
它是单点失效
中央结点会变成瓶颈分层算法 (1)
分层算法保留了集中式算法简单的优点且易扩充
按照逻辑层次组织,与网络物理结构无关组织机器的方式和现实世界组织人员方式一样一些机器是工人,另一些为管理者每 K个工人,设置一个管理者分层算法 (2)
如果系统很大,会有大量部门领导要设置机器当,院长,
院长管理一定数量的部门领导如果院长很多设置一个,大头头,来管理
层次结构可无限扩展,层次数是工人数的对数值
每个处理器只和一个上级及有限的下级通信管理信息流容易分层算法 (3)
问题：,当一部门领导停工 （ 崩溃 ） 时会发生什么？,
一种回答：从直接下属中提拔一个
谁来提拔者呢？
下属,也可是头头的同事头头的老板分层算法 (4)
为避免在顶层只有一个领导 (易受伤害 )
可把层次树截断顶层设置委员会当最高领导当一个成员故障时剩下的成员从低一层中提拔一个不是真正的分布式方案,但切实可行且系统是自恢复的当工人和经理崩溃后不用多长可以恢复正常分层算法 (5)
如果需要 S个进程的作业出现系统须分配 S台处理器可在任何层次上创建作业每个经理都统计它下一层可用处理器如果认为有足够的处理器,就保留 R个这里 R ≥ S,
估计也许不准确且有机器也许崩溃了分层算法 (6)
如果接受请求的经理发现数目不够把该请求传给老板如果老板也不能满足,继续上传一直到能满足要求的层次经理把请求分成几部分把它们传给下级经理下级再进行分配,直到传到底层在底层,分配的处理器标为,忙碌,
把实际的分配数逐级汇报分层算法 (7)
R必须足够大使概率高到有足够工人处理作业否则请求将重新开始,浪费时间和计算能力
如果 R太大分配的处理器过多,浪费了计算能力分层算法 (8)
系统状态十分复杂在系统任何地方可能随机地产生请求大量请求在算法的各个阶段中对空闲处理器的估计有可能过时,可能引起竞争,死锁等等分布式启发算法 (1)
当创建进程时创建的机器随机选择机器发送探测消息询问它的负载是否低于某个阈值如果是,进程发给它如果不是,探测另一台机器如果经过 N次仍没找到合适机器中止算法并在原先机器上运行此进程该算法性能良好,并在许多情况下保持稳定竞价算法 (1)
把系统当作一个经济系统有购买者和服务销售者,并根据供求情况来调整价格关键的角色是进程和处理器为了完成工作进程须购买 CPU时间处理器把时间拍卖给出价最高的进程处理器把大致售价放在公共文件中这个价格不是保证价,只指示它服务的价值实际上表示最后一个用户的买价竞价算法 (2)
处理器的价格不一样取决于速度,主存,浮点硬件和其他特性当进程想启动一子进程时逐个检查,看谁能提供服务从能服务的处理器集中选出合格的,选出最好的
,最好,意味最便宜,最快价格性能也最好竞价算法 (3)
把出价发送给选择的处理器出价可能高于也可能低于标价处理器收集所有出价选出一个,也许是出价最高的哪一个给予赢家和输家通告赢家的进程开始运行更新服务器的发布价格竞价算法 (4)
经济模型引起了有趣的问题进程哪儿得到钱？ 有日常工资吗？
是不是月工资都一样还是院长比教授高,教授比学生高？
如果不增加资源就接受新用户会引起竞价上涨 （ 通货膨胀 ） 吗？
处理器会组成卡特尔来欺骗用户吗？
允许用户组成工会吗？
磁盘空间也要付钱吗？
激光打印机输出怎么考虑？ 等等
11.4 分布式系统中的调度 (1)
在分布式系统中每个处理器有自己的本地调度不考虑别的处理器在做什么一般,这种方法工作良好当一组相关性强,联系紧密的进程运行在不同的处理器上时,这种独立调度就是最有效的方法
11.4 分布式系统中的调度 (2)
假设进程 A和 B在一处理器上,进程 C和 D在另一台上每个处理器都是分时的,时间片为 100毫秒
A和 C偶数时间片运行,B和 D奇数时间片运行假设 A给 D发了许多消息或远程调用给 D
在时间片 0中,A起动并立即调用 D
不幸是 D没有运行,因为轮到 C运行过了 100毫秒,发生了进程切换
D接到 A的消息,完成任务后很快回答因为现在 B正运行,A只有 100毫秒后,
才接到答复,并进行处理,这样,每 200毫秒才交换信息需要保证进程可经常通信并同步运行
11.4 分布式系统中的调度 (3)
假定进程成组创建组内的通信比组间的通信得多假定有大量的,充足的处理器来处理最大的进程组每个处理器支持多道程序并配有 N个进程槽 （ N-方式多道程序处理 ）
11.4 分布式系统中的调度 (3)
Ousterlout基于协同调度的算法考虑进程间通信的方式确保一组内的所有成员同时运行要点,每个处理器都使用循环调度所有处理器首先在槽 0运行进程一段固定时间然后所有处理器在槽 1运行进程一段固定时间为保时间片同步,向广播消息,告诉切换时间把一进程组内所有成员放在不同外理器的相同槽内得到有 N个并行处理的优势它保证所有进程都在同时运行从而有了最大的通信量
研究分布式系统中线程
怎样组织处理器和进程
分布式系统中的处理器分配和调度
11.1 线程 (1)
例：服务器有时因等待磁盘而进入阻塞状态如果服务器有多个线程当一个线程睡眠时第二个线程就可以投入运行引入多线程为了得到更大的吞吐量和更高的效率
(a)三个各只有一个线程的进程
(b)一个拥有三个线程的进程线程 (2)
线程
一个进程的线程都在同一个地址空间中拥有自己的程序计数器和堆栈线程严格按顺序执行
在多处理器系统中,它们真正并行执行
线程可以建立子线程,因等待系统调用而阻塞
当一个线程被阻塞时,同一进程中的另一个线程可以运行线程 (3)
线程共享 CPU
可以共享相同的全局变量
共享同一个打开文件集,子进程,定时器,
信号等线程 (4)
每个线程都可以存取任何一个虚拟地址一个线程能够读,写,甚至完全破坏另一个线程的堆栈
在线程之间没有设置保护措施
（ 1） 不可能； （ 2） 没必要
进程通常来自不同的用户,可能会发生冲突
用户建立多个线程是为了协同工作,而不是冲突线程 (6)
线程包括的项程序计数器堆栈寄存器集子线程状态进程包括的项地址空间全局变量打开文件子进程定时器信号信号量计帐信息线程 (8)
线程状态：运行,阻塞,就绪,完成
运行状态,正在使用 CPU,处于活动状态
阻塞状态,等待另一线程激活它
就绪状态,已被调度,只要一轮到就运行
完成状态,已退出,但还没被父线程收回
11.1.2 线程使用进程中线程的三种组织方式
(a) 调度员／工作者模式
(b) 队列模式
(c) 管道模式
(a)调度员／工作者模式
(b)队列模式
(c)管道模式有限状态机 (1)
假定不能使用多线程单线程造成了无法接受的性能就下降可把服务器看作一个有限状态机当请求到达时,唯一的线程检查请求信息如果缓存中数据能满足要求,就接着处理如果不能满足要求,它给磁盘发送消息有限状态机 (2)
然而,这时它并不进入阻塞状态仅在表中记下请求的状态,处理下个请求如果是新的工作请求,就开始新工作若是磁盘的反馈信息则从表中取出相关信息,答复请求有限状态机 (3)
不允许发消息后因等答复而进入阻塞
调用原语也必须是非阻塞式调用
对接收和发送的消息必须在表格中保存或恢复状态
以困难的方式模拟多线程和它们的堆栈进程以有限状态机方式运行根据接收作出相应反应构造服务器的三种方式模式 特性多线程 并行，阻塞式系统调用单线程处理 非并行，阻塞式系统调用有限状态机 并行，非阻塞式系统调用
11.1.3 线程包的设计问题给用户的线程的原语集叫线程包静态线程
在程序编制或编译阶段就决定使用多少个线程
给每个线程分配固定的堆栈
方式简单,但不灵活动态线程 (1)
在运行中动态创建和注销线程
需要指定线程主程序 （ 作为指向过程的指针 ）
堆栈的大小,指定参数,如调度的优先级等
调用通常返回一个线程标识符标识符在该线程的调用中被用到
进程启动时只拥有一个 (隐含 )线程可据需要创建多个线程线程的终止
当线程完成任务时,可自行退出
或者被杀掉互斥信号量 (1)
多个线程使用同一内存块保存共享的数据要防止多个线程同时存取同一个数据经常使用得技术：互斥信号量互斥信号量 (2)
一种小型信号量
信号量在两个状态之一：关锁和开锁
二元信号量 （ 即只有 0,1两个值的信号量 ）
两种操作被定义为互斥互斥信号量的改变是一个原子动作
LOCK,试图锁住互斥信号量如果互斥信号量处于开锁状态
LOCK将成功执行互斥信号量 (3)
在多处理器系统中多个线程运行在不同的 CPU上
如果两个线程在同一个实例上试图加锁同一个互斥信号量只有一个线程能赢,别的将失败
如果线程试图加锁已被锁住的互斥信号量它将被阻塞互斥信号量 (4)
UNLOCK操作解锁一个互斥信号量
如果一个或多个线程在一个互斥信号量上等待,只有一个线程解锁,其余的线程继续等待
TRYLOCK操作
该操作试着加锁一个互斥信号量
如果该互斥信号量未被锁定
TRYLOCK返回状态码,说明操作成功
若该互斥信号量是锁着的
TRYLOCK并不阻塞该线程而返回指示失败的状态码
容易实现条件变量 (1)
一个线程锁住互斥信号量进入临界区在临界区,发现所需资源已被占用锁住第二个互斥信号量 （ 与被占资源相关的 ）
外面的互斥信号量将保持在关锁状态拥有被占资源的线程不能进入临界区释放它产生了死锁如果解锁外面的互斥信号量别的线程进入临界区,又会引起混乱
Lock mutex;
check data structures;
while(resource busy)
wait(condition variable);
mark resource as busy;
unlock mutex;
(a)
Lock mutex;
mark resource as busy;
unlock mutex;
wakeup(condition variable);
(b)
互斥信号量和条件变量的使用条件变量 (2)
解决方案：使用条件变量来申请资源
条件变量定义原子性的自动地等待和解锁互斥信号量
当使用资源的线程释放资源后它执行 wakeup操作
wakeup 定义：一次可以唤一个线程也可唤醒特定的条件变量上等待的所有线程使用 WHILE而不用 IF
防止线程被唤醒但还没运行时,别的线程抢占资源条件变量 (2)
在创建条件变量时每个条件变量常和一个互斥信号量关联
互斥信号量和条件变量的差别互斥信号量用于短期的加锁,主要用于保护临界区的入口条件变量用于长期的等待,一直到资源可用为止线程与全局变量 (1)
一个线程通常拥有多个过程过程含有局部变量,全局变量和过程参数若变量对线程来说是全局的但对整个程序来说是非全局的,会带来困难使用全局变量引起的冲突线程 1 线程 2
访问 写 errno
打开读 errno
时间 errno重 写线程与全局变量 (2)
例子,UNIX维护 errno 的变量线程 1执行系统调用 ACCESS
检查是否对特定文件有访问权返回结果在全局变量 errno中当控制权回到线程 1,而它还没有读 errno 时线程 1已用完了时间片,控制权交给线程 2
线程 2执行 OPEN调用失败,errno被改写线程 1永远丢失访问权代码线程与全局变量 (3)
方法 1,禁止使用全局变量和许多现存的软件相冲突,如 UNIX
方法 2,每个线程定义私有的全局变量每个线程都有 errno 的私有拷贝与别的全局变量,避免了冲突
分配全局性的内存块作为额外的参数传递给线程中的每个过程
方法不是很好,但可用线程与全局变量 (4)
方法 3:
引入创建 (create)
设置 (set)
读取 (read)全局变量的库函数线程与全局变量 (5)
创建 (create)：
create-global (“bufptr”)
为指针变量 bufptr分配内存从堆或特定存储区中分配只有调用线程才能存取这个全局变量如果别的线程使用同名创建全局变量将从不同的存储区中分配,这样不会冲突线程与全局变量 (5)
两个调用存取全局变量：写,读
写,设置 (set)调用：
set-global (“bufptr”,&buf);
读取 (read)：
bufptr = read-global (“bufptr”);
11.1.4 线程包的实现两种实现线程包方法：
用户空间
内核
（ a）用户层的线程包 (b)由核心管理的线程包内核
Run Time系统内核线程 线程
0 1 2 3 4 5 0 1 2 3 4 5
用户空间内核空间用户空间内核空间
（ a） (b)
用户空间中线程包的实现 (1)
内核一无所知只知正在管理一般的单线程进程
优点：在不支持线程的系统中可实现用户层线程包
例,UNIX不支持线程却有各种用户线程包运行用户空间中线程包的实现 (2)
线程运行于 run-time系统之上管理线程的过程集合当线程执行系统调用,进入睡眠状态它调用运行系统的一个过程首先确定此线程是否要挂起需要挂起,线程的寄存器存在一个表中用户空间中线程包的实现 (3)
在表中查找未被阻塞的线程查到后把此线程的寄存器的装到机器的寄存器中当栈指针程序记数器相应设置后新线程投入运行如果机器中有专门一次保存和装入所有寄存器的指令线程切换只用极少的指令就可完成用户空间中线程包的实现 (4)
好处,
线程切换比内核陷入快得多
允许进程有定制的调度算法
线程在用户层增加了可扩展性内核管理线程 (1)
对每个进程,内核用表保存线程的入口有寄存器,状态,优先级以及其他信息
能阻塞线程的调用以系统调用方法实现因而调用的费用大内核管理线程 (2)
线程阻塞两种可能
运行同一进程的另一个线程 （ 如果它已就绪 ）
或者运行其他进程的线程在用户层线程方式中运行系统总是运行同一进程的线程直到内核把 CPU交到别处为止用户层线程包与内核线程问题 (1)
问题,阻塞设线程从一空管道中读数据或执行了可引起阻塞的操作在内核式实现中内核阻塞此线程并启动另一个在用户空间实现中无法接受让线程执行系统调用因为会中止所有的线程用户层线程包与内核问题 (2)
使用线程的目的为了被阻塞的线程不影响到别的线程阻塞系统调用,不能达到这个目的可把系统调用全部转换成非阻塞的
（ 举例来说,读一个空管道时只是失败 ）
但要求改变操作系统不吸引人用户层线程的吸引力之一是可运行在已有的操作系统上用户层线程包与内核问题 (3)
改变 READ的语义会使许多用户程序要改变可选的方法,
在调用前系统告知此调用是否会引起阻塞只有不会阻塞时才使线程行动方法要改写系统调用部分函数效率不高,效果不好但除此也无别的选择用户层线程包与内核问题 (4)
用户层线程包的另一个问题是如果一个线程开始运行同一个进程中别的线程不能运行,除非运行的线程主动放弃 CPU
一种解决方案请求时钟信号 （ 中断 ） 来得到控制权但这样做,程序会很繁乱
11.2 系统模型讨论
工作站模型
处理器池模型
混合模型
11.2.1 工作站模型系统由许多工作站组成这些工作站由高速 LAN连接起来工作站或有一个用户登录,或处于空闲状态个人工作站网络，每台自带本地文件系统空闲工作站网络无盘工作站
要在网上设置文件服务器提供文件服务文件读写请求送往服务器,完成后返回结果
无盘工作站广泛使用
原因,价格,易于维护对称性和适应性好用户可登录任何一台工作站所有文件在文件服务器上所有的工作站都一样有盘工作站 (1)
盘的四种使用方式：
第一种
本地盘只用作页面交换和临时文件是非共享的
用户退出登录时,文件可被丢弃有盘工作站 (2)
第二种：第一种的变体
交换,临时文件,系统二进制文件
本地盘也用来保存二进制 （ 可执行 ） 程序如,编译器,文本编辑器,电子邮件当调用这些程序时,直接读取本地盘
无须从服务器上得到,减轻网络负载
需要管理什么机器上拥有什么程序的什么版本有盘工作站 (3)
第三种方法：本地盘作外部高速缓存
从服务器下载文件到本地盘在本地读写,再上载修改过的文件
集中保存本地长期使用的文件,减轻网络负载
缺点：要保持缓存的一致性如两个用户下载同一个文件然后做了不同的修改,会产生问题有盘工作站 (4)
第四种,每台机器有自己的文件系统有可能装载和存取别的机器的文件系统
思想：机器基本上是自给型的和外界保持有限的接触
缺点,共享困难
和网络操作系统相近,不是透明的分布式系统工作站模型的优点
容易理解
用户拥有固定的计算能力和好的响应时间
可直接访问屏幕,复杂的图形程序能高速运行
用户有大的自主权,可随意分配资源
本地盘增加了工作站的独立性
当服务器崩溃时,工作站依然可进行工作工作站上磁盘的使用磁盘使用 优点 缺点无磁盘 费用低，软硬件维护容易，对称，有灵活性网络负载重；文件服务器可能成为瓶颈页面交换，临时文件 比无盘方式的网络负载小 大量的磁盘导致费用高页面交换，临时文件，
二进制文件网络负载更小 费用高；增加了更新二进制文件的复杂性页面交换，临时文件，
二进制文件，文件高速缓存网络负载小；从文件服务器上装入的文件少高费用；缓存一致性问题完全的本地文件系统 几乎无网络负载；消除了对文件服务器的依赖失去透明性
11.2.2 空闲工作站的使用 (1)
观察显示,即使在最忙时仍有 30％ 以上工作站空闲早期试图使用空闲工作站的是 Berkeley UNIX 的 rsh 程序
rsh 程序
rsh machine command
第一个参数指定机器,第二个参数指定运行的命令程序存在严重缺陷首先,必须指定机器,跟踪空闲机器的负担压在用户身上其次,远程机器的环境和本地环境可能不同最后,如果要在运行远程进程的机器上登录,
远程进程又要继续运行用户要接受低效率,要么找别的机器空闲工作站的使用 (2)
怎样查找空闲工作站？
怎样才能透明地执行远程进程？
如果机器的主人回来,该怎么办？
怎样查找空闲工作站呢？
不同的系统,空闲,定义不同如果没有人在一段时间内使用键盘或鼠标或者没有用户进程在运行就可以说这台工作站是空闲的空闲工作站定位算法
两类：
服务器驱动和客户驱动
服务器驱动服务器主动告知可为他人服务
客户驱动客户主动 查找空闲工作站 务服务器驱动算法 (1)
工作站空闲,成为潜在计算服务器它告知别人可用性可把名字,网络地址,属性放在一个注册文件中 （ 或数据库 ）
当一户想在空闲工作站上执行命令时输入以下命令：
remote command
remote程序查找注册文件可保存注册文件的多个拷贝,增加可靠性服务器驱动算法 (2)
新空闲的工作站可在网上广播消息别的工作站记录消息每台机器维护一个私有注册表好外是寻找空闲工作站的代价小且冗余性好缺点是每台机器都要注册表的维护工作服务器驱动算法 (3)
缺点：竞争的危险二个用户同时使用 remote 命令发现同一台空闲工作站试图在该机器上同时启动他们的进程为避免这种情况
remote程序检测空闲工作站若仍然是闲着的从注册表中删去并给一个前进标志这时,调用者可传送环境并启动远程进程查找并使用空闲工作站的基于注册表的算法注册注册表空闲工作站列表注册表远程机注册表空闲工作站
1,空闲时机器注册2,请求空闲工作站得到响应
3,公告
4,撤消注册
5,设置环境
6,开始进程
7,进程运行
8,进程退出
9,修改原注册客户驱动算法激活 remote,广播请求说明要运行程序,需要内存是否要浮点协处理芯片等等回复到达,remote选出一台工作站运行让,空闲,工作站在作答复时作些轻微的延迟延迟的长短和它们的负载成正比负载轻的机器的回复到,并被先选用进程在工作站上执行 (1)
转移代码很容易困难在于使设置环境与本地环境相同要相同的文件系统相同的工作目录相同的环境变量 （ shell变量 ）
进程在工作站上执行 (2)
当执行系统调用时,内核该做什么？
答案与系统体系结构有关
无盘工作站,所有文件都在服务器中内核只要向相应的服务器请求
若有本地盘,且是完整的文件系统请求直接回送到主体工作站进程在工作站上执行 (3)
有些系统调用必须回送到主体工作站运行举例,读键盘和写屏幕永远都不能在远程机器上执行
另一些系统调用必须远程执行
不同机器的时钟可能不同步与时间有关的系统调用也会引起问题
使程序在远程机器上就象在本地机器上一样执行是可能的这是个复杂且需要技巧的工作进程在工作站上执行 (4)
问题：如果机器的主人回来怎么办？
最简单：就是什么也不做
另一个可能方法：消灭侵入的进程不预先警告就直接杀掉 。 缺点是工作丢失,文件系统混乱
较文明的方法：给进程发出明确的警告让它知道将面临的厄运,然后体面地关闭进程如果几秒钟后还没退出,就中止它当然程序要有处理信号的能力许多程序肯定没有这种能力进程在工作站上执行 (5)
另一方法：把进程转移到另一台机器上
当进程离开时应保持机器的状态和使用它之前的状态相同
不仅该进程要离开所有子孙也必须离开
邮箱,网络连接和别的系统级的数据结构也必须删除
11.2.3 处理器池模型 (1)
问题：,当可供 CPU比用户多 10倍或 100倍,
会怎样？,
每人一个私人的多处理器计算机方案不太有效
另一种方法：
构造一个处理器池 （ processor pool）
跟据用户的需要动态分配模型接近于分时模型
X终端 处理器池 文件服务器CPU
基于处理器池模型的系统
11.2.3 处理器池模型 (2)
所有的 CPU在一起降低能源和包装成本且能提供更强的计算能力易扩充,如果计算负载增加了 10％
只要再买 10％ 的处理器在可动态访问的,空闲工作站,上用户可根据需要暂时得到所需的 CPU
用完后,放回池中,以便别的用户来使用没有所有权概念：所有的处理器属于每个人
11.2.3 处理器池模型 (2)
处理器池在互联网上的版本：
目前已有在互朕网站点上提供计算能力
甚至提供应用程序而客户浏览器方连应用软件都不用配备
Web计算模式 - Browser/Server计算模式
11.2.3 处理器池模型 (3)
处理器池集中计算能力的依据是排队论
用户随机地向服务者发出工作请求如果服务者忙,用户排队等候并按顺序处理
例子,
铁路售票处机场检票柜台超市结算台等排队论 (1)
用户以每秒? 个速率输入请求服务者每秒处理? 个请求为顺利运作,必须有? >λ
排队论 (2)
如果服务器每秒处理 100个请求但每秒产生 110个请求,队列会无限增长在小的时间段中输入速率大于服务速率是可接受的只要平均输入速率小于服务速率,并提供足够的缓存基本的排队系统计算机 工作完成用户产生全部
请求 /s
进入队列系统可处理
请求 /s
排队论 (3)
可以证明 （ kleinrock,1974）
从发出请求到得到响应的平均时间
T和 λ,?有关公式如下：
1
T
排队论 (4)
举例,设服务器每秒能处理 50个请求当 λ趋近 0时 （ 无负载 ）,服务器的响应时间并不趋近 0
而是 1／ 50秒或 20毫秒原因显而易见即使没有竞争,响应时间,包括处理时间永远不会低于 20毫秒排队论 (5)
设 n台多处理机每个 CPU组成独立的队列系统请求到达率为 λ,CPU处理率为?,平均响应时间为 T
把所有的 CPU都放在同一个处理器池中只有一个大的队列系统排队论 (6)
输入速率为 nλ,服务速率为 n?
平均响应时间为 T1,我们得到把 n个小资源组成一个有 n倍能力的大资源可把平均响应时间减少 n倍
n
T
nn
T?
1
1
排队论 (7)
结果普适航空公司宁愿每 5小时飞一班 300座的 747，
也不愿意每 10分钟飞一班 10座的商业喷气机原理之一如此
11.2.3 处理器池模型特点 (1)
每个用户一台小服务器虽能提高效率对于请求随机到达的系统来说是很差的匹相配多数时间中只有很少的服务器忙,过载大多数空闲处理器池可消除浪费,
排队论是反对分布式主要依据之一
11.2.3 处理器池模型特点 (3)
可靠性和容错性也是要考虑的因素在一台大的,集中式共享计算机上编辑显示一页在 95％ 的时间里需要 5毫秒有时又需要 5秒钟用户认为性能不可接受若要运行大的 make或巨型的模拟程序大型计算机是最好的选择
11.2.3 处理器池模型特点 (4)
决定因素,工作负载的性质
如果工作只是简单的编辑并偶尔发个电子邮件使用个人工作站是最合适的
如果一个大的软件开发工程在大量的目录中经常运行 make程序或求一个大型稀疏矩阵的逆阵或大的模拟计算,求解大型人工智能问题处理器池模型富有吸引力
11.2.4 混合模型
给每个用户提供一台工作站,附加处理器池
综合了两者的优点
交互性在工作站上,以保证响应时间
非交互式的在处理器池运行
既提供快速交互,又有效使用资源,且设计简单
11.3 处理器分配
把进程赋给处理器的算法
设：所有的机器至少代码兼容不同仅是速度
设：系统是紧密互联任何一对机器间可建立联接通信处理器分配策略 (1)
二类处理器分配策略
第一类是非迁移算法进程创建时就已定好它的位置把它放在某机器上它一直在那台上运行,直到终止处理器分配策略 (2)
另一类是迁移分配算法即使进程已开始运行,也可移动
迁移策略能更好平衡负载,但也复杂
算法优化的目标：提高 CPU利用率减少平均响应时间处理器分配策略 (3)
响应比定义,进程在某机器上所用时间被该进程在基准处理器上运行时间相除
响应比更有意义
设想一个 1秒的任务响应时间为 5秒一个 1分的任务响应时间为 70秒哪个更好呢？ 用响应时间来衡量,前者较好
用响应比来衡量,后者好因为 5／ 1 >>70/60
11.3.2 处理器分配算法的设计原则 (1)
确 定 性 算 法 （ Deterministic ） 和 启 发 算 法
(heuristic)
集 中 式 处 法 (Centralized) 和分布式算法
(distributed)
最优化算法 (Optimal)和次优化算法 (sub optimal)
局部性算法 (local)和全局式算法 (global)
发送者启动算法 (Sender-initiated)和接收者启动算法 （ receiver-initiated）
请帮助我能否取走一进程?
过载了！
Help!
机器认定负载太重我无事可做！
今晚我有空真无聊！
机器找活干
(a) (b)
发送者寻找空闲工作站 接收者寻找工作
11.3.2 处理器分配算法的设计原则 (2)
对进程的行为能事先了解时采用确定性算法
没有系统能事先了解所有的信息但可做合理的估计
例,在银行,保险和机票预定系统中每天的工作大致一样可在统计上准确描述工作负载使得确定性算法成为可能
系统中不能预测工作负载有必要使用启发式算法
11.3.2 处理器分配算法的设计原则 (3)
集中式与分布式
在一地集中所有的信息容易选择一个好方案但也脆弱,中央处理机的负载会过重
常采用分布式算法在分布式算法不适应时才采用集中式算法
11.3.2 处理器分配算法的设计原则 (4)
找个最好的,还是找个可接受的？
最优化方法太困难
大多数采用启发式,分布式,次优化算法
11.3.2 处理器分配算法的设计原则 (5)
传输策略创建进程时,要决定能否在创建机器上运行可根据本地信息,也可参考全局信息
简单的算法：本地化算法如果机器负载在某界限以下,保留新进程否则就放弃
较好的方案：决定本地机是否太忙碌之前先收集有关负载的全局信息
局部性算法简单,但性能不好全局性算法能性能高但代价大
11.3.2 处理器分配算法的设计原则 (5)
定位策略当根据传输策略放弃进程要根据定位策略把它发往何处
定位策略不能是局部性的要参考别外的负载情况来做聪明的决定
两种信息传播方法由发送者开始信息交换由接收者启动交换过程
11.3.3 处理器分配算法的实现问题 (1)
负载过重还是负载过轻
简单的处理：
计算每台机器上的进程数目作为负载
但进程数和当前的负载无大关系
11.3.3 处理器分配算法的实现问题 (2)
只计算正在运行就绪的进程只要是正在运行或将要运行的进程即使是后台进程也会增加负载
许多后台进程是周期性醒来然后检查是否有它关心的事情发生如果没有,就重新睡眠 。
它们增加的负载很小
11.3.3 处理器分配算法的实现问题 (3)
用 CPU忙碌时间片表示负载一台 CPU使用率为 20％ 的比 10％ 的负载大
计算 CPU利用率的方法,
定时中断机器,每次中断,把 CPU的状态记录下
问题当内核执行临界代码时,常屏蔽所有中断会低估 CPU的利用率
11.3.3 处理器分配算法的实现问题 (4)
额外费用把新进程移到远程机器上能提高 10％ 的效率可是移动进程的开销更大,最好不动
好算法应计算算法本身耗费的 CPU时间内存使用,网络带宽
这样做不容易,很少这样做复杂性一个新算法,经过证明性能非常好但结论却是不要采用这个算法原因实现很复杂
11.3.3 处理器分配算法的实现问题 (5)
Eager算法在任何情况下每台机器检查自己并判断是否轻负载每当创建新进程创建机器检查自己是否超负载如果是寻找一台机器,在其上启动这个新进程
11.3.3 处理器分配算法的实现问题 (6)
三个定位侯选机算法
算法 1：
随机挑一台机器,把新进程发过去如果接收机超负载它也随机挑选一台机器,把进程送走一直进行到有愿意接收或者步长计数器越界
11.3.3 处理器分配算法的实现问题 (7)
算法 2：
随机挑一台机器并发信息询问是否过载如果负载不重,就接收该进程否则进行新的探测循环进行到找到合适的机器或不能再进行为止后一种情况下,进程在创建处不动
11.3.3 处理器分配算法的实现问题 (8)
算法 3：
询问 K台,进程发给负载最轻的机器直觉算法 3的性能最好实际上也是如此
算法 3和算法 2相比,性能提高不多,但复杂性很多
结论：简单算法和复杂且昂贵算法相比性能相差不大时,用简单算法
11.3.3 处理器分配算法的实现问题 (9)
稳定性问题系统可能进到一种状态
A和 B都没有新的信息两者都认为对方的负载轻会把可怜的进程在它们间多次传来传去图论确定性算法 (1)
基本思想：降低网络通信量用一个加权图来表示结点代表进程,弧代表两个进程间的信息流从数学的角度来看,问题简化为在一定限制下找把该图划分成 K分非连通子图的方法所有进程的 CPU和内存要求均低于各个子图的限制在符合要求的方案中子图内部的弧表示在机器内部通信忽略不计从一子图连到另一子图的弧代表网络通信量图论确定性算法 (2)
目标：
满足所有条件找出一种网络通信量最小的划分
寻找耦合紧密的簇 （ 簇内的流量大 ）
而这些簇与别的簇联系很少 （ 簇之间的流量小 ）
图论算法要事先了解完整的信息应用受到限制集中式算法 (1)
启发式算法,不需要预先了解信息
算法是集中式的原因在于设置有协调器,维护使用表
每个工作站在表中占一栏开始时为空当有重要的事发生时给协调器发送消息更新表分配都以该表为依据集中式算法 (2)
在有以下调度事件发生时做决定：
请求一个处理器,一个处理器已变为空闲,
或时钟中断不以最大限度地使用 CPU为目标而是给每个工作站提供公平的共享计算能力上下算法 (1)
当一台工作站主在别的机器上运行进程时它累计了罚点 （ penalty points）
点数加到使用表对应项中当有未被满足的要求时从使用表对应项减去一定数目的罚点当没有被挂起的请求也没有正在使用的处理器时从使用表对应项中减去一定数目的罚点,直到为 0
得分数或上或下,称上下算法进程 1到达进程 1被分配处理器进程 2到达进程 2被分配进程 1完成进程 2完成 时间使用表上下算法的执行上下算法 (2)
使用表对应项数值可为正,0,或负正：该工作站是一个纯系统资源用户负：表示它需要资源
0：表示中性现进行启发式处理器分配当一处理器空闲时,拥有得分最低的请求将获得该处理器没占用处理器且请求挂起时间最长的用户会击败已使用了许多处理器的用户算法的目标：公平分配资源集中式算法 (4)
集中式算法很难扩充成大的系统
它是单点失效
中央结点会变成瓶颈分层算法 (1)
分层算法保留了集中式算法简单的优点且易扩充
按照逻辑层次组织,与网络物理结构无关组织机器的方式和现实世界组织人员方式一样一些机器是工人,另一些为管理者每 K个工人,设置一个管理者分层算法 (2)
如果系统很大,会有大量部门领导要设置机器当,院长,
院长管理一定数量的部门领导如果院长很多设置一个,大头头,来管理
层次结构可无限扩展,层次数是工人数的对数值
每个处理器只和一个上级及有限的下级通信管理信息流容易分层算法 (3)
问题：,当一部门领导停工 （ 崩溃 ） 时会发生什么？,
一种回答：从直接下属中提拔一个
谁来提拔者呢？
下属,也可是头头的同事头头的老板分层算法 (4)
为避免在顶层只有一个领导 (易受伤害 )
可把层次树截断顶层设置委员会当最高领导当一个成员故障时剩下的成员从低一层中提拔一个不是真正的分布式方案,但切实可行且系统是自恢复的当工人和经理崩溃后不用多长可以恢复正常分层算法 (5)
如果需要 S个进程的作业出现系统须分配 S台处理器可在任何层次上创建作业每个经理都统计它下一层可用处理器如果认为有足够的处理器,就保留 R个这里 R ≥ S,
估计也许不准确且有机器也许崩溃了分层算法 (6)
如果接受请求的经理发现数目不够把该请求传给老板如果老板也不能满足,继续上传一直到能满足要求的层次经理把请求分成几部分把它们传给下级经理下级再进行分配,直到传到底层在底层,分配的处理器标为,忙碌,
把实际的分配数逐级汇报分层算法 (7)
R必须足够大使概率高到有足够工人处理作业否则请求将重新开始,浪费时间和计算能力
如果 R太大分配的处理器过多,浪费了计算能力分层算法 (8)
系统状态十分复杂在系统任何地方可能随机地产生请求大量请求在算法的各个阶段中对空闲处理器的估计有可能过时,可能引起竞争,死锁等等分布式启发算法 (1)
当创建进程时创建的机器随机选择机器发送探测消息询问它的负载是否低于某个阈值如果是,进程发给它如果不是,探测另一台机器如果经过 N次仍没找到合适机器中止算法并在原先机器上运行此进程该算法性能良好,并在许多情况下保持稳定竞价算法 (1)
把系统当作一个经济系统有购买者和服务销售者,并根据供求情况来调整价格关键的角色是进程和处理器为了完成工作进程须购买 CPU时间处理器把时间拍卖给出价最高的进程处理器把大致售价放在公共文件中这个价格不是保证价,只指示它服务的价值实际上表示最后一个用户的买价竞价算法 (2)
处理器的价格不一样取决于速度,主存,浮点硬件和其他特性当进程想启动一子进程时逐个检查,看谁能提供服务从能服务的处理器集中选出合格的,选出最好的
,最好,意味最便宜,最快价格性能也最好竞价算法 (3)
把出价发送给选择的处理器出价可能高于也可能低于标价处理器收集所有出价选出一个,也许是出价最高的哪一个给予赢家和输家通告赢家的进程开始运行更新服务器的发布价格竞价算法 (4)
经济模型引起了有趣的问题进程哪儿得到钱？ 有日常工资吗？
是不是月工资都一样还是院长比教授高,教授比学生高？
如果不增加资源就接受新用户会引起竞价上涨 （ 通货膨胀 ） 吗？
处理器会组成卡特尔来欺骗用户吗？
允许用户组成工会吗？
磁盘空间也要付钱吗？
激光打印机输出怎么考虑？ 等等
11.4 分布式系统中的调度 (1)
在分布式系统中每个处理器有自己的本地调度不考虑别的处理器在做什么一般,这种方法工作良好当一组相关性强,联系紧密的进程运行在不同的处理器上时,这种独立调度就是最有效的方法
11.4 分布式系统中的调度 (2)
假设进程 A和 B在一处理器上,进程 C和 D在另一台上每个处理器都是分时的,时间片为 100毫秒
A和 C偶数时间片运行,B和 D奇数时间片运行假设 A给 D发了许多消息或远程调用给 D
在时间片 0中,A起动并立即调用 D
不幸是 D没有运行,因为轮到 C运行过了 100毫秒,发生了进程切换
D接到 A的消息,完成任务后很快回答因为现在 B正运行,A只有 100毫秒后,
才接到答复,并进行处理,这样,每 200毫秒才交换信息需要保证进程可经常通信并同步运行
11.4 分布式系统中的调度 (3)
假定进程成组创建组内的通信比组间的通信得多假定有大量的,充足的处理器来处理最大的进程组每个处理器支持多道程序并配有 N个进程槽 （ N-方式多道程序处理 ）
11.4 分布式系统中的调度 (3)
Ousterlout基于协同调度的算法考虑进程间通信的方式确保一组内的所有成员同时运行要点,每个处理器都使用循环调度所有处理器首先在槽 0运行进程一段固定时间然后所有处理器在槽 1运行进程一段固定时间为保时间片同步,向广播消息,告诉切换时间把一进程组内所有成员放在不同外理器的相同槽内得到有 N个并行处理的优势它保证所有进程都在同时运行从而有了最大的通信量
