pdf南OS8-网络和分布式操作系统

1第八章网络和分布式操作系统=计算机网络概述=网络操作系统=分布式操作系统2§8.3分布式操作系统=分布式计算机系统是由一组松散的计算机系统，经互连网络连接而成的”单计算机系统映像”(SingleComputerSystemImage)。=分布式OS中的多机及资源分配、进程迁移、消息传递等对用户是透明的。用户看到的是一台“虚拟的单处理机”，用户不知道自己的程序在哪一结点上存放和运行。8.3.1分布式系统概述3=资源共享：远程站点文件的共享、分布式数据库的信息处理、共享远程硬件设备……=加快运算速度：将运算分解为子运算在不同站点并发运行、负载均衡……=可靠性：若干CPU的故障不影响整个系统运行。=通信：各站点间进行消息通信更容易。=以较低的成本获得较高的运算性能。=缺点：分布式软件的设计和实现困难；分布式系统依赖于网络通信的质量；分布式系统的数据共享导致安全问题。分布式系统的优点和缺点4位置透明性用户不了解资源的物理位置在哪里，资源名字不能隐含资源位置迁移透明性可以任意移动资源，而其名字不用变化复制透明性用户不了解文件是否有多个副本存在，n台文件服务器自己决定需要镜像哪些使用频繁的文件并发透明性多个用户可以自动共享资源，而注意不到其他用户的存在并行透明性任务被自动地并行执行（一个作业的多个进程被分配到多个节点上并行运行，但不需要程序员显式地说明）分布式系统的透明性5共享资源多位于服务器中分布式系统中各站点的资源均可共享只在操作实现上有一定的透明对象位置、并发控制、系统故障等实现细节对用户透明，系统重构能力好不进行任务分配将任务分配到多个处理单元上控制功能集中在服务器中处理和控制是分布式的用户知道多机的存在用户面对的是一台虚拟单机，用户不知道自己的程序在哪一节点上存放和运行在单机OS之上建立是一个独立的OS网络OS（理想的）分布式OS分布式分布式OSOS与网络与网络OSOS的区别的区别68.3.1分布式进程通信1、消息传递机制（1）寻找服务器地址的三种方式：a.采用两段地址：透明性不够服务器地址:服务器本地进程标识号•例：telnetdownwind.sprl.umich.edu3000,在密执根大学的这台主机上运行一个天气预报程序，且该程序在3000号端口上等待连接。一个端口支持多个连接。客户机C服务器S121：向202.116.160.243:23请求2：向202.116.160.199:15回答71、消息传递机制（1）寻找服务器地址的三种方式：b.进程选择随机地址，通过广播定位发送者广播一个特殊的定位包，其中有目标进程的地址。客户机C服务器S344：回答12网络上所有主机都接收该包，检查包内地址是否是自己本机内进程，若是，返回一个“HereIam”消息给发送者，告诉发送者它的网络地址。以后发送者内核就利用该地址发送。1：广播2：应答“HereIam”3：请求81、消息传递机制（1）寻找服务器地址的三种方式：c.在客户程序中放入ASCII字符串，通过名字服务器查询：如Internet的DNS客户机C名字服务器NS服务器S客户机第一次请求服务时，先发送一个查询消息给名字服务器，名字服务器返回目标服务器的物理地址。以后客户机就直接发请求给目标服务器。11：查找22：NS回答33：请求44：回答91、消息传递机制（2）阻塞与非阻塞的发送和接收原语：a.阻塞的发送send和接收receive原语：易于使用•当一个进程调用send时，就被阻塞，等到消息完全发送之后，才被唤醒。•当一个进程调用receive时，就被阻塞，等到消息被接收并送入缓冲区之后，才被唤醒。(常用)•时延：在阻塞发送的系统中，指定一个应答时延，在时延内没有应答，就出错。b.非阻塞的发送send和接收receive原语：•当一个进程调用send时，不被阻塞，继续执行。(常用)•当一个进程调用receive时，不被阻塞，继续执行（执行的是一个test原语，轮询内核）。101、消息传递机制（3）无缓冲和有缓冲的send、receive原语：a.无缓冲原语：•如果调用的是receive(addr,&m)，表示该调用进程正在端口addr上等待接收消息，并将放到m消息接收区中。•但如果已经send结束，但对方尚未调用receive，则发来的这个消息怎么办？解决方案可以是：•忽略该消息，这样客户端得不到应答时它会重发，（或许）服务器会在此期间调用receive。•服务器对每一个消息都保管一段时间，直到某个receive被调用。超时就丢弃该消息。b.有缓冲原语：•在服务器或客户机上，内核为每一个接收进程都创建一个“信箱”，凡是发到这个信箱地址的消息都被放到该信箱中。•但如果信箱满时，则继续发来的消息怎么办？解决方案和无缓冲时类似。111、消息传递机制（4）不可靠和可靠原语：a.不可靠：•发送的消息丢失，但发送方不知道。b.可靠：•对请求和应答都各有一个确认消息。内核客户机C341：客户机发出请求2：确认：S收到请求3：服务器发出应答结果4：确认：C收到应答12内核服务器S122、远程过程调用RPC客户机客户进程客户机存根stub服务器服务器存根stub服务器进程内核内核RPC调用利用参数构成消息，调用send让内核发送消息，然后调用receive阻塞自己1利用Receive接收消息，转换成服务器内格式，取出消息中的参数38消息到，被唤醒。取出结果9返回结果执行相应服务程序4根据参数调用相应服务Call6将结果形成响应消息，用send发送5返回执行结果2发送消息给服务器接收消息并转交服务器存根7接收消息并转交客户机存根发送消息给客户机13=客户机/服务器存根负责把参数打包到一个消息中，收到响应后解包消息。=远程服务调用是通过和本地调用一样的形式完成的，调用者并不知道被调用的过程是在另一台机器上运行的。所有的消息传递细节都被内核、send和receive函数屏蔽掉了。2、远程过程调用RPC143、套接字Socket‰套接字是一个通信的端点，＝IP地址:端口‰端口是主机上的一个进程。‰套接字146.86.5.20:1625是指主机146.86.5.20上的端口1625。主机X(202.116.160.75)套接字(202.116.160.75:1625)(202.116.160.75:1743)web服务器(202.116.160.33)套接字(202.116.160.33:23)(202.116.160.33:21)15服务器建立套接字监听端口和客户机通信客户机建立套接字连接至端口和服务器通信Java:ServerSocket(port)C:socket(),bind()Java:accept()C:listen(),accept()Java:getOutputStream()getInputStream()C:send()，recv(),Java:Socket(IP,port)C:socket()Java:Socket(IP,port)C:connect()3、套接字Socket168.3.3分布式资源管理=多个资源与多个管理者时：=集中式：一类资源由一个管理者管理。=集中分布方式：一类资源有多个管理者，但每个资源只受控于一个管理者。=完全分布方式：一类资源有多个管理者，但每个资源由多个管理者协商管理。集中式集中分布式完全分布式178.3.4分布式进程同步=分布式系统中的各个结点不共享内存和时钟。如果缺乏全局一致的同步时钟，那么依赖于时间次序的多个事件的执行将会混乱。=重要的不是所有进程有完全一致和精确的时间，而是事件发生次序要一致。=事件排序的两个基本观点：=若两个事件发生在同一进程中，则可用观察到的次序来确定它们的发生次序。=在进程间传递消息时，发送消息事件总先于接收该消息的事件。=简化假设：每个节点只有一个进程，并被统一编号。181、事件排序=事前关系(前趋关系)Î：happened-beforerelation=AÎB，表示事件A先于事件B发生。如“发送消息”(A)和“接收消息”(B)=如果AÎB，且BÎC，则AÎC。=如果A、B之间不存在Î关系，则A、B并发。¿时间进程事件消息p3和q0是并发关系.r0和q4是事前关系.192、逻辑时钟=逻辑时钟：各结点用时钟计数器为本地启动的所有事件编号（时间戳timestamp）。=用C(a)表示事件a的时间戳。„对任何事件a、b，若aÎb，应有C(a)C(b)。„对本地任何事件a和b，C(a)都不会等于C(b)。=在时间戳中附加上发生事件的节点（或进程）标识符，可以实现事件的完全排序。„设节点Pa上发生的事件a时间戳为Ta，节点Pb上发生的事件b时间戳为Tb，事件a和b的全局时间戳分别为(Ta,Pa)和(Tb,Pb)。„则全局事件a先于b发生：(Ta,Pa)(Tb,Pb)当且仅当TaTb或者Ta=Tb且PaPb。20„Cp在结点P上发生每一事件前增值：Cp=Cp+1„若事件a是P发送消息m，则m中有时间戳Cp(a)„当结点Q在时刻t收到消息m(事件b)时，若Cq(b)Cp(a)，则令Cq(b)=Cp(a)+1，并据此调整结点Q的逻辑时钟计数器。——调快慢时钟逻辑时钟的更新与传递：Lamport的解决方案2、逻辑时钟例：三个节点各有各的时钟，而且速度各不同。则传送消息C、D时，时钟混乱。P0612182430364248P1816243240485664P21020304050607080ABCDP03036426066P14051596775P25060709080CDLamport的解决方案：若消息到达时，本地时钟值小，则修改成“消息的时间戳加1”。223、分布式互斥算法以Ricart算法为例Pi要求访问某资源时,向所有其它进程发送request(Ti,i);Pj收到后：*若Pj不要求访问该资源或要求访问但其request(Tj,j)(Ti,i)，则立即回送reply(Tj,j)；*若Pj正访问该资源或要求访问且其request(Tj,j)(Ti,i)，则推迟回送reply(Tj,j)；Pi收到所有reply(Tx,x)时才可访问该资源。访问完后，向所有被推迟回送reply(Ti,i)的进程发送reply(Ti,i)。„每次进出临界区需2×(n-1)条消息。例：P1、P3要访问临界资源，P4正在访问该临界资源：request(6,3)request(9,1)⑦P1收到了所有的reply()，开始访问该资源。⑥P3退出后向P1发送一reply()；⑤P3收到了所有的reply()，开始访问该资源；④P4推迟回送P3和P1。等P4退出临界区后，P4向P3回送一reply()，P4向P1回送一reply()；②P1和P2回送给P3一reply()；③P1发送request(9,1)给P2、P3和P4；P2回送给P1一reply()；①P3发送request(6,3)给P1、P2和P4；临界资源P1P2P3P4248.3.5分布式系统中的死锁=1、死锁类型：„资源型死锁：不可剥夺资源引起的死锁。„消息型死锁：不同节点中的进程，为发送和接收消息而竞争缓冲区，以致发生既不能发送也不能接收消息的状态。=在分布式系统的实际实现中：„“忽略死锁”应用最普遍。„死锁预防虽然比单机系统时更困难，但还可能实现。„死锁避免从不被使用。因为无法预知资源需求量。„死锁检测和恢复也经常被使用。25•设置一中心结点，其中有：全网共享资源表以及用于检测分布系统中死锁的协调者进程。•任何进程在请求和释放共享资源Ri时，必须通知协调者进程和管理Ri的进程。R1P1P2P3R2R3P3释放R3,请求R1R1P1P2P3R2R3正确™死锁检测中的虚假死锁问题：资源分配图中出现环形链时可能并未死锁。这是因为进程发出请求资源、释放资源命令的时序与执行它们时的时序不一致。集中式死锁检测方法R1P1P2P3R2R3或虚假死锁26进程0要用资源x，但x已被进程1占用，则进程0向进程1发检测消息m后阻塞，若进程1由于等待资源y也被阻塞（资源y被进程2占用），