OS之分布式系统中的线程与调度问题

《OS之分布式系统中的线程与调度问题》由会员分享，可在线阅读，更多相关《OS之分布式系统中的线程与调度问题（135页珍藏版）》请在金锄头文库上搜索。

1、分布式系统中的进程及处理器 研究分布式系统中线程 怎样组织处理器和进程 分布式系统中的处理器分配和调度一. 线程(1)例：服务器有时因等待磁盘而进入阻塞状态如果服务器有多个线程当一个线程睡眠时第二个线程就可以投入运行 引入多线程为了得到更大的吞吐量和更高的效率(a)三个各只有一个线程的进程 (b)一个拥有三个线程的进程线程(2) 一个进程的线程都在同一个地址空间中 线程拥有自己的程序计数器和堆栈 线程严格按顺序执行在多处理器系统中，它们真正并行执行 线程可建立子线程 线程可因等待系统调用而阻塞当一个线程被阻塞时，同一进程中的另一个线 程可以运行线程(3) 线程共享CPU 可以共享相同的全局变量

2、 共享同一个打开文件集，子进程、定时器、 信号等线程(4) 每个线程都可以存取任何一个虚拟地址所以一个线程能够读、写、甚至完全破坏另 一个线程的堆栈 在线程之间没有设置保护措施（1）不可能；（2）没必要 进程通常来自不同的用户，可能会发生冲突 用户建立多个线程是为了协同工作, 而不是 冲突线程 (6)线程 (8) 线程状态：运行，阻塞，就绪，完成 运行状态，正在使用CPU，处于活动状态 阻塞状态，等待另一线程激活它 就绪状态, 已被调度，只要一轮到就运行 完成状态，已退出，但还没被父线程收回1. 线程使用进程中线程的三种组织方式 (a) 调度员工作者模式 (b) 队列模式(c) 管道模式(a)

3、调度员工作者模式(b)队列模式(c)管道模式有限状态机(1)假定不能使用多线程单线程造成无法接受的性能下降可把服务器看作一个有限状态机当请求到达时，唯一的线程检查请求信息如果缓存中数据能满足要求，就接着处理如果不能满足要求，它给磁盘发送消息有限状态机(2)然而，这时它并不进入阻塞状态仅在表中记下请求的状态，处理下个请求如果是新的工作请求，就开始新工作若是磁盘的反馈信息则从表中取出相关信息，答复请求有限状态机(3)不允许发消息后因等答复而进入阻塞调用原语也必须是非阻塞式调用对接收和发送的消息必须在表格中保存或恢复状态以困难的方式模拟多线程和它们的堆栈进程以有限状态机方式运行根据接收作出相应反应构

4、造服务器的三种方式模式 特性3. 线程包的设计问题给用户的线程的原语集叫线程包静态线程 在程序编制或编译阶段就决定使用多少个线程 给每个线程分配固定的堆栈方式简单，但不灵活动态线程(1) 在运行中动态创建和注销线程 需要指定线程主程序（作为指向过程的指针）堆栈的大小，指定参数，如调度的优先级等 调用通常返回一个线程标识符标识符在该线程的调用中被用到 进程启动时只拥有一个(隐含)线程可据需要创建多个线程线程的终止 当线程完成任务时，可自行退出 或者被杀掉互斥信号量(1) 多个线程使用同一内存块保存共享的数据要防止多个线程同时存取同一个数据 经常使用的技术：互斥信号量互斥信号量(2) 一种小型信号

5、量信号量在两个状态之一：关锁和开锁 二元信号量（即只有0, 1两个值的信号量）两种操作被定义为互斥互斥信号量的改变是一个原子动作 LOCK，试图锁住互斥信号量如果互斥信号量处于开锁状态LOCK将成功执行互斥信号量(3) 在多处理器系统中多个线程运行在不同的CPU上 如果两个线程在同一个实例上试图加锁同一个互斥信号量只有一个线程能赢，别的将失败 如果线程试图加锁已被锁住的互斥信号量它将被阻塞互斥信号量(4) UNLOCK操作解锁一个互斥信号量如果一或多个线程在一个互斥信号量上等待只有一个线程解锁，其余的线程继续等待TRYLOCK操作 该操作试着加锁一个互斥信号量 如果该互斥信号量未被锁定TRYL

6、OCK返回状态码，说明操作成功 若该互斥信号量是锁着的TRYLOCK并不阻塞该线程而返回指示失败的状态码 容易实现条件变量(1) 一个线程锁住互斥信号量进入临界区在临界区，发现所需资源已被占用锁住第二个互斥信号量（与被占资源相关的） 外面的互斥信号量将保持在关锁状态 拥有被占资源的线程不能进入临界区释放它产生了死锁 如果解锁外面的互斥信号量别的线程进入临界区，又会引起混乱Lock mutex;check data structures;while(resource busy)wait(condition variable);mark resource as busy;unlock mutex;

7、(a)Lock mutex;mark resource as busy;unlock mutex;wakeup(condition variable);(b)互斥信号量和条件变量的使用条件变量(2) 解决方案：使用条件变量来申请资源 条件变量定义原子性的自动地等待和解锁互斥信号量 当使用资源的线程释放资源后它执行 wakeup操作 wakeup 定义：一次可以唤一个线程也可唤醒特定的条件变量上等待的所有线程使用WHILE而不用IF防止线程被唤醒但还没运行时，别的线程抢占资源条件变量(2)在创建条件变量时每个条件变量常和一个互斥信号量关联互斥信号量和条件变量的差别 互斥信号量用于短期的加锁主要用

8、于保护临界区的入口 条件变量用于长期的等待一直到资源可用为止线程与全局变量(1) 一个线程通常拥有多个过程过程含有局部变量、全局变量和过程参数 若变量对线程来说是全局的但对整个程序来说是非全局的，会带来困难使用全局变量引起的冲突线程1线程2访问写errno打开读errno时 间errno重写线程与全局变量(2)例子，UNIX维护errno 的变量线程1执行系统调用ACCESS检查是否对特定文件有访问权 返回结果在全局变量errno中当控制权回到线程1，而它还没有读errno 时线程1已用完了时间片，控制权交给线程2线程2执行OPEN调用失败，errno被改写线程1永远丢失访问权代码线程与全局变

9、量(3) 方法1: 禁止使用全局变量和许多现存的软件相冲突，如UNIX 方法2: 每个线程定义私有的全局变量每个线程都有errno 的私有拷贝与别的全局变量，避免了冲突 分配全局性的内存块作为额外的参数传递给线程中的每个过程方法不是很好，但可用线程与全局变量(4) 方法3: 引入创建 (create)设置 (set)读取 (read)全局变量的库函数线程与全局变量(5) 创建 (create)：create-global (“bufptr”)为指针变量bufptr分配内存从堆或特定存储区中分配 只有调用线程才能存取这个全局变量 如果别的线程使用同名创建全局变量将从不同的存储区中分配，这样不会冲

10、突线程与全局变量(5)两个调用存取全局变量：写，读 写, 设置 (set)调用：set-global (“bufptr”, 读取 (read)：bufptr = read-global (“bufptr”);4. 线程包的实现两种实现线程包方法： 用户空间 内核（a）用户层的线程包 (b)由核心管理的线程包内核Run Time系统内核线程线程 012 345012 345用 户 空 间内核空间用 户 空 间内核空间（a）(b)用户空间中线程包的实现(1) 内核一无所知只知正在管理一般的单线程进程 优点：在不支持线程的系统中可实现用户层线程包例: UNIX不支持线程却有各种用户线程包运行用户空间

11、中线程包的实现(2) 线程运行于run-time系统之上管理线程的过程集合 当线程执行系统调用，进入睡眠状态它调用运行系统的一个过程 首先确定此线程是否要挂起需要挂起，线程的寄存器存在一个表中用户空间中线程包的实现(3) 在表中查找未被阻塞的线程 查到后把此线程的寄存器的装到机器的寄存器中 当栈指针程序记数器相应设置后新线程投入运行 如果机器中有专门一次保存和装入所有寄存器的指令 线程切换只用极少的指令就可完成用户空间中线程包的实现(4)好处: 线程切换比内核陷入快得多 允许进程有定制的调度算法 线程在用户层增加了可扩展性内核管理线程(1) 对每个进程, 内核用表保存线程的入口有寄存器、状态、

12、优先级以及其他信息 能阻塞线程的调用以系统调用方法实现因而调用的费用大内核管理线程(2)线程阻塞两种可能 运行同一进程的另一个线程（如果它已就绪） 或者运行其他进程的线程在用户层线程方式中运行系统总是运行同一进程的线程直到内核把CPU交到别处为止（或没有就绪的线程了）用户层线程包与内核线程问题(1)问题: 阻塞 设线程从一空管道中读数据或执行了可引起阻塞的操作 在内核式实现中内核阻塞此线程并启动另一个 在用户空间实现中无法接受让线程执行系统调用因为会中止所有的线程用户层线程包与内核问题(2) 使用线程的目的为了被阻塞的线程不影响到别的线程 阻塞系统调用，不能达到这个目的 可把系统调用全部转换成

13、非阻塞的（举例来说，读一个空管道时只是失败） 但要求改变操作系统，办法不吸引人 用户层线程的吸引力之一是可运行在已有的操作系统上用户层线程包与内核问题(3) 改变READ的语义会使许多用户程序要改变 可选的方法: 在调用前系统告知此调用是否会引起阻塞只有不会阻塞时才使线程行动 方法要改写系统调用部分函数效率不高，效果不好 除此也无别的选择用户层线程包与内核问题(4) 用户层线程包的另一个问题如果一个线程开始运行同一个进程中别的线程不能运行除非运行的线程主动放弃CPU 一种解决方案：请求时钟信号（中断）来得到控制权这样做，程序会很繁乱二. 系统模型讨论 工作站模型 处理器池模型 混合模型1.工作

14、站模型系统由许多工作站组成这些工作站由高速LAN连接起来工作站或有一个用户登录，或处于空闲状态个人工作站网络，每台自带本地文件系统空闲工作站网络无盘工作站 要在网上设置文件服务器提供文件服务文件读写请求送往服务器，完成后返回结果 无盘工作站广泛使用原因: 价格, 易于维护对称性和适应性好用户可登录任何一台工作站所有文件在文件服务器上所有的工作站都一样有盘工作站(1)盘的四种使用方式：第一种 本地盘只用作页面交换和临时文件 是非共享的 用户退出登录时，文件可被丢弃有盘工作站(2)第二种：第一种的变体交换，临时文件，系统二进制文件 本地盘也用来保存二进制（可执行）程序如，编译器、文本编辑器、电子邮

15、件当调用这些程序时，直接读取本地盘 无须从服务器上得到，减轻网络负载 需要管理什么机器上拥有什么程序的什么版本有盘工作站(3)第三种方法：本地盘作外部高速缓存 从服务器下载文件到本地盘在本地读写，再上载修改过的文件 集中保存本地长期使用的文件，减轻网络负载 缺点：要保持缓存的一致性如两个用户下载同一个文件然后做了不同的修改，会产生问题有盘工作站(4)第四种，每台机器有自己的文件系统有可能装载和存取别的机器的文件系统 思想：机器基本上是自给型的和外界保持有限的接触 缺点: 共享困难 与网络操作系统相近，不是透明的分布式系统工作站模型的优点 容易理解 用户拥有固定的计算能力和好的响应时间 可直接访问屏幕，复杂的图形程序能高速运行 用户有大的自主权，可随意分配资源 本地盘增加了工作站的独立性 当服务器崩溃时，工作站依然可进行工作工作站上磁盘的使用磁盘使用 优点 缺点2. 空闲工作站的使用(1) 观察显示，即使在最忙时仍有30以上工作站空闲 早期试图使用空闲工作站的是Berkeley UNIX 的rsh 程序rsh 程序 rsh machine command第一个参数指定机器第二个参数指定运行的命令程序存在严重缺陷 首先，必须指定机器，跟踪空闲机器的负担 压在用户身上 其次，远程机器的环境和本地环境可能不同 最后，如果要在运行远程进程的机器上登录