【精品】《分布式系统》第四章 并发计算（可编辑.ppt

分布式系统第四章 并发计算进程进程Process:一个运行着的程序一个运行着的程序n一个进程应该包括执行中的程序、该程序所操作的数据、所使用的资源、以及执行期间的状态。n一个进程的运行环境是一台抽象的计算机，包括分配给该进程的虚CPU、存储空间、以及其它系统资源。运行 阻塞 就绪创建消亡调度调度时钟中断时钟中断请求服务请求服务服务成功服务成功2第四章 并发计算进程创建/*UNIX 进程创建：进程创建：process_creation.c*/process_creation.c*/#include#include main()main()int pid;int pid;if(pid=fork()!=0)if(pid=fork()!=0)/*/*父进程父进程*/*/printf(“Fathern”);printf(“Fathern”);wait(0);wait(0);else if(pid=fork()!=0)else if(pid=fork()!=0)/*/*子进程子进程*/*/printf(“Sonn”);printf(“Sonn”);wait(0);wait(0);else else/*/*孙进程孙进程*/*/printf(“Grandsonn”);printf(“Grandsonn”);exit(0);exit(0);3第四章 并发计算UNIX进程创建存储空间示意每一个UNIX进程都具有完全独立的地址空间，该空间由三个区域组成：第一是一块固定的、不可修改的区域，用来存放程序代码、常数等信息；第二是一块称为堆堆(heap)的区域，用来存放所有动态分配的数据；第三是一块称为栈栈(stack)的区域，用以存放过程调用的控制信息以及从属于被调用过程的局部变量 栈堆程序常数区栈堆程序常数区栈堆程序常数区父进程父进程子进程子进程孙进程孙进程4第四章 并发计算进程内容切换 每当把CPU从一个进程分配给另一个进程时，我们都要进行进程内容切换(context switch)，包括保存旧进程的执行状态，设置新调度进程的执行状态等工作 进程内容：CPU内容(CPU context)，存储内容(Storage context)nCPU内容比较简单，包括程序计数器、通用寄存器，栈指针以及其它一些辅助信息。n而一个进程的存储内容却复杂的多，包括该进程的程序、数据、地址空间、不同区域的地址影射、磁盘交换(Swap)影射等等。5第四章 并发计算进程与线程（2）PCBPCBTCBTCBTCB PCBTCBTCBTCB 线程支持系统线程支持系统操作系统操作系统单线进程单线进程多线进程多线进程多线进程多线进程PCB代表进程控制块(Process Control Block)TCB代表线程控制块(Thread Control Block)这些控制块含有控制调度进程或线程所需的信息8第四章 并发计算线程程序包设计问题目前最著名的两个线程程序包：IEEE和OSI推荐的POSIX POSIX(Portable Operating System Interface)SUN操作系统之下的线程包LWPLWP(Light Weight Process)q如何调度线程：用户级(用户空间)线程系统级(内核空间)线程)q如何处理阻塞性的系统调用：强占式(preemptive)调度非强占式调度9第四章 并发计算用户线程和系统线程混合型策略 用户级线程用户级线程用户级线程用户级线程 LWP LWP LWP LWP重量级进程重量级进程重量级进程重量级进程操作系统内核级线程操作系统内核级线程10第四章 并发计算不同系统下的线程例子/*POSIX*/main()pthread_create(f,arg);void*f(void*arg)pthread_exit(status);/*Win32 */main()CreateThread(f,arg);_beginthread(f,arg);_xbeginthread(f,arg);DWORM f(DWORD arg)ExitThread(status);_endthread(status);_xendthread(status);/*Java*/main()MyThread t;t=new MyThread();t.start();class MyThread extends Thread public void run()return;11第四章 并发计算POSIX线程/*POSIX thread：thread_creation.c*/*compile：gcc o thread_creation thread_creation.c lpthread*/#include#include#include void*mythread(void);/*thread prototype*/*ME-lock initialization*/pthread_mutex_t mylock=PTHREAD_MUTEX_IITIALIZER;int x=0;/*shared variable*/int main()pthread_t tids10;/*identifier array*/int i;for(i=0;i 10;i+)/*create 10 threads */pthread_create(&tidsi,NULL,mythread,NULL);for(i=0;i 10;i+)/*waiting for thread termination*/pthread_join(tidsi,NULL);printf(“Thread id%ld returnedn”,tidsi);exit(0);/*thread function*/void*mythread(void)/*add 1 to shared variable*/while(x 4000)pthread_mutex_lock(&mylock);/*lock*/x+;/*critical region */printf(“Thread id%ld:x is now%dn”,pthread_self(),x);pthread_mutex_unlock(&mylock);/*unlock */pthread_exit(NULL);/*thread terminates*/*Each thread increases x by 1 in each loop,until x is greater than or equal to 4000.If we do not use lock/unlock,what happen?*/12第四章 并发计算并发计算中的同步与互斥并发计算中的同步与互斥我们把访问共享变量我们把访问共享变量x x的那组指令称为临界区的那组指令称为临界区(Critical Region)Critical Region)临界区是必须临界区是必须“原子化原子化”的的(不允许中断的不允许中断的)一组程序代码一组程序代码 线程线程 T T 线程线程 S S 可能出现的指令执行序列：可能出现的指令执行序列：(1)t1,t2,t3,s1,s2,s3(1)t1,t2,t3,s1,s2,s3(2)t1,t2,s1,t3,s2,s3(2)t1,t2,s1,t3,s2,s3(3)t1,t2,s1,s2,t3.s3(3)t1,t2,s1,s2,t3.s3(4)t1,t2,s1,s2,s3,t3(4)t1,t2,s1,s2,s3,t3(5)t1,s1,t2,t3,s2,s3(5)t1,s1,t2,t3,s2,s3(6)t1,s1,t2,s2,t3,s3(6)t1,s1,t2,s2,t3,s3(7)t1,s1,t2,s2,s3,t3(7)t1,s1,t2,s2,s3,t3(8)t1,s1,s2,t2,t3,s3(8)t1,s1,s2,t2,t3,s3(9)t1,s1,s2,t2,t3,s3(9)t1,s1,s2,t2,t3,s3 T:x+;t1:LODt1:LODR1,xR1,xt2:ADDt2:ADDR1,1R1,1 t3:STOR1,xS:x+;s1:LOD R1,xs2:ADDR1,1s3:STOR1,x13第四章 并发计算互斥算法与互斥机制互斥算法与互斥机制 三点要求:n必须保证不准多于一个的并发实体同时进入临界区n必须防止来自临界区之外的并发实体的干扰n必须防止饿死现象(即某些并发实体无穷无尽地等待着进入临界区)一些著名的互斥机制，如信号灯和P/V操作、管程、条件变量等等14第四章 并发计算共享内存互斥机制共享内存互斥机制 信号灯-一个信号灯s是一个非负整型变量，初始值为1。-仅能通过下述两个原语之一对信号灯进行操作：nP(s):while(s=0)wait;s:=s-1nV(s):s:=s+1-信号灯是一种低级互斥机制15第四章 并发计算Push(x):RepeatIftop0theny:=stacktop;top-;end栈d1d2 d3 d4dn.topk单元例子例子并发进程共享一个栈.P(s)V(s)Semaphores;使用P/V操作的例子16第四章 并发计算生产者与消费者问题(1)：一种简单算法/*POSIX：producer_consumer.c*/#include void*producer_function(void);/*prototype*/void*consumer_function(void);/*Initialize a ME lock*/pthread_mutex_t mylock=PTHREAD_MUTEX_IITIALIZER;/*shared variables among threads*/int flag=0;char buffer;struct timespec dealy;main()pthread_t consumer;delay.tv_sec=2;/*set 2 sec delay*/delay.tv_nsec=0;/*create consumer */pthread_create(&consumer,NULL,consumer_function,NULL);producer_function();/*main becomes producer*/void*producer_function(void)while(1)pthread_mutex_lock(&mylock);if(flag=0)buffer=produce();/*produce an item*/flag=1;pthread_mutex_unlock(&mylock);pthread_delay_np(&delay);/*sleep 2 sec*/void*consumer_function(void)while(1)pthread_mutex_lock(&mylock);if(flag=1)consume(buffer);/*consume an item*/flag=0;pthread_mutex_unlock(&mylock);pthread_delay_np(&delay);/*sleep 2 sec*/17第四章 并发计算生产者与消费者问题(2)：一种改进的算法/*POSIX：producer_consumer1.c*/#include/*thread prototypes*/void*producer_function(void);void*consumer_function(void);/*initialize a lock and two conditional variables*/pthread_mutex_t mylock=PTHREAD_MUTEX_IITIALIZER;pthread_cond_t w_consumer=PTHREAD_COND_IITIALIZER;pthread_cond_t w_producer=PTHREAD_COND_IITIALIZER;/*threads shared variables*/int flag=0;char buffer;struct timespec dealy;main()pthread_t consumer;delay.tv_sec=2;/*set 2 sec time delay*/delay.tv_nsec=0;/*create consumer thread*/pthread_create(&consumer,NULL,consumer_function,NULL);producer_function();/*main becomes producer thread */void*producer_function(void)char x;while(1)x=produce();pthread_mutex_lock(&mylock);while(flag=1)/*wait for consumers signal*/pthread_cond_wait(&w_consumer,&mylock);buffer=x;flag=1;pthread_mutex_unlock(&mylock);pthread_cond_signal(&w_producer);pthread_delay_np(&delay);/*sleep 2 sec*/void*consumer_function(void)char x;while(1)pthread_mutex_lock(&mylock);while(flag=0)/*wait for producers signal */pthread_cond_wait(&w_producer,&mylock);x=buffer;flag=0;pthread_mutex_unlock(&mylock);pthread_cond_signal(&w_consumer);consume(x);pthread_delay_np(&delay);/*sleep 2 sec*/18第四章 并发计算客户客户/服务器并发系统服务器并发系统 客户软件的实现涉及到两方面的因素:n客户软件所提供的用户界面n客户软件与服务器的交互客户软件所提供的用户界面都由图形用户界面(GUI）实现:了解用户了解用户简化常用服务简化常用服务为用户提供反馈为用户提供反馈保持一致性保持一致性19第四章 并发计算WS_FTPWS_FTP客户程序用户界面客户程序用户界面20第四章 并发计算服务器软件设计服务器软件设计分配器线程A线程B线程C线程D线程A线程B线程C线程D线程A线程B 线程C线程C服务请求队列 相同线程相同线程调度线程(1)中央分配结构(2)并发处理结构(3)中央调度结构(4)轮转调度结构21第四章 并发计算软件代理软件代理 n软件代理也是一个(执行中)的程序，是一个“协助人，代表人来完成某个任务的程序”。n软件代理是一个自主(autonomy)程序，能够自行适应环境，对环境做出反应，并且可能与其它代理或用户协同合作(Jennings et al.1998)。22第四章 并发计算 (1)必须能够适应运行环境。(2)必须拥有下述特征(必备特征)：n反应反应(reactive)reactive)：能够察觉环境的变化并能够根据变化做出及时反应；n自主自主(autonomous)autonomous)：能够自身决定行为控制，即自己管理自己；n目标驱动目标驱动(goal driven)goal driven):能够主动地实现目标并影响环境；n时序连续时序连续(temporally continuous)temporally continuous):能够连续(长期)地执行。(3)可以拥有下述特征(可选特征)：n通信通信(communicative)communicative):能够与其它软件代理交换信息；n移动移动(mobile)mobile):能够从一个环境(计算机)迁移到另一个环境(计 算机)；n学习学习(leaning)leaning):能够自动地吸取以前的经验并增长知识；n信任信任(believable)believable):能够代表用户的意愿，为用户所信任。软件代理的基本特征软件代理的基本特征 23第四章 并发计算四种可能的运算四种可能的运算/数据分布模型数据分布模型运算运算数据数据部分运算部分运算部分运算部分运算数据数据部分数据部分数据部分数据部分数据运算运算A A运算运算B B运算运算运算运算数据数据(1)远程文件访问模型(2)客户/服务器模型(4)移动软件代理模型(3)分布式数据库模型数据迁移数据迁移程序迁移程序迁移数据协调数据协调远程调用远程调用24第四章 并发计算为何需要移动软件代理为何需要移动软件代理?股票市场股票市场服务器服务器 客户客户 股票市场股票市场 IBM:$20 Microsoft:$21 HP:$22买进买进/售出股票售出股票消息传送消息传送顾客顾客 智能智能软件代理软件代理实现方法（实现方法（2）客户客户 消息传送消息传送买进买进/卖出卖出请求请求客客户户移动智能移动智能软件代理软件代理实现方法（实现方法（3）买进买进/卖出卖出股票股票带回结果带回结果软件代理软件代理软件代理软件代理派遣代理派遣代理实现方法（实现方法（1）25第四章 并发计算潜在应用例子n用户级应用用户级应用-信息检索和信息过滤代理信息检索和信息过滤代理-个人协助代理个人协助代理n中间件中间件-全球文件系统全球文件系统-分布式合作系统分布式合作系统n系统级系统级-网络状态监控网络状态监控-入侵检测入侵检测-自动软件分布、安装、升级自动软件分布、安装、升级26第四章 并发计算n模拟人类的并发活动n实现各种抽象：任务代理、接口代理、信息代理等n减少网络负载n动态适应环境n降低网络延迟n适用于接入/断开类型的网络（如无线电话网）移动软件代理之优点移动软件代理之优点27第四章 并发计算n分布式系统中的并发实体都要借助于某种通信机制进行交互，籍以交换信息或达成同步，软件代理亦是如此。毫无疑问，常驻软件代理之间只有通过通信才能相互协作，n传统的进程/线程间通信语言非常简单，系统提供的通信原语只定义了最基本的语法，即信件是一组给定长度的字节串，而对信件的语义没有任何定义，完全依赖于通信双方的自行解释。软件代理通信软件代理通信28第四章 并发计算n我们需要一种软件代理通信语言软件代理通信语言(ACL:Agent CommunicationLanguage)来沟通软件代理，使得它们能在不同环境下用一种彼此都理解的语言进行通信。n近年来，人们力图将软件代理之间的通信标准化，提出了若干ACL，如知识查询管理语言知识查询管理语言(KQML:Knowledge Query and Manipulation)，知识交换格式知识交换格式(KIF:Knowledge Interchange Format)，以及FIPAFIPA软件代理软件代理通信语言通信语言(FIPA-ACL)。这些语言都是陈述性陈述性(declarative)语言而非过程性过程性(procedural)语言，也就是说，是基于逻辑(类如Prolog或Lisp)而不是基于过程控制(如C或Java)的语言。软件代理通信语言软件代理通信语言29第四章 并发计算 A to B:(ask-if(classroom_201)(classroom_203)B to A:(reply true)软件代理利用软件代理利用KQMLKQML通信的例子通信的例子30第四章 并发计算 信件行为信件行为 信件内容信件内容 解释解释INFORMINFORM命题告知所给定的命题为真QUERY_IFQUERY_IF命题询问是否所给定的命题为真QUERY_REFQUERY_REF表达式询问某个给定对象的指引元PROPOSEPROPOSE建议给出一项建议ACCEPT_PROPOSALACCEPT_PROPOSAL建议标识符告知所给出的建议已被接受REJECT_PROPOSALREJECT_PROPOSAL建议标识符REQUESTREQUEST动作说明请求按说明采取动作CFPCFP建议说明请求提供一项建议SUBSCRIBESUBSCRIBE资源引用预定某个信息资源FIPA ACLFIPA ACL几种典型的行为和内容定义几种典型的行为和内容定义31第四章 并发计算 信件元素信件元素 元素类型元素类型行为行为(performative)(performative)动作类型发送者发送者(sender)(sender)通信参与者接收者接收者(receiver)(receiver)通信参与者回应送达者回应送达者(reply-to)(reply-to)通信参与者内容内容(content)(content)信件内容语言语言(language)(language)内容描述编码编码(encoding)(encoding)内容描述本体本体(ontology)(ontology)内容描述协议协议(protocol)(protocol)会话控制会话标识会话标识(conversation-id)(conversation-id)会话控制回应索引回应索引(reply-with)(reply-with)会话控制索引式回应索引式回应(in-reply-to)(in-reply-to)会话控制回应定时回应定时(reply-by)(reply-by)会话控制FIPA ACLFIPA ACL信件元素定义信件元素定义32第四章 并发计算行为行为INFORMINFORM发送者发送者B B接收者接收者A A语言语言PrologProlog内容内容truetrue行为行为QUERY_IFQUERY_IF发送者发送者A A接收者接收者B B语言语言PrologProlog内容内容greater(classroom_201,greater(classroom_201,classroom_203)classroom_203)软件代理利用软件代理利用FIPA ACLFIPA ACL通信的例子通信的例子33第四章 并发计算 一个程序可以是一个网页、一个脚本、一个Java APPLET、一个进程、或者是一个软件代理。因此，一个程序可能会含有四种成分：(1)代码代码：可以被运行环境执行的一组语句或指令。大致上，代码可以被分成三类：一，源代码源代码(source code)，即没有经过任何加工处理的源语言代码，其运行环境一般是该语言的解释系统；二，字节代码字节代码(bytecode)，即源代码通过翻译所形成的中间代码，其运行环境一般是该语言的虚机器；三，二进代码二进代码(binary code),即源代码通过编译系统产生的二进制机器指令，其运行环境是某类特定的计算机。程序迁移（程序迁移（1 1）34第四章 并发计算 (2)数据数据：代码所操作的一组对象。程序尚未执行时的数据称为初始数据初始数据，而运行期间的数据称为中间数中间数据据。当我们不需要强调执行状态时则泛称数据。(3)资源资源：程序运行时所需要使用的一组外部软硬设备，如打印机、磁盘、文件、数据库、URL、通信端口、等等。(4)执行状态执行状态：程序迁移发生时对运行环境的快照快照(snapshot)，包括程序计数器、通用寄存器、栈指针、栈中内容、等等。如果在迁移时程序尚未开始执行，则其执行状态只是该程序的启动入口。程序迁移（程序迁移（2 2）35第四章 并发计算迁移模型 迁移对象 迁移后执行方式原始迁移代码、初始数据系统从起点开始执行弱迁移代码、中间数据系统从起点开始执行，而用户程序需要通过判别转移回到继续点执行强迁移代码、中间数据、执行状态系统自动从继续点执行三种常用的程序迁移技三种常用的程序迁移技术术 36第四章 并发计算强强迁移和弱迁移程序示意迁移和弱迁移程序示意 强迁移示意强迁移示意：move_to(A);move_to(A);(从继续点恢复从继续点恢复)继续点继续点弱弱迁移示意迁移示意：(从头开始从头开始/恢复恢复)if(not moved)if(not moved)moved=true;moved=true;move_to(A);move_to(A);elseelse 继续点继续点 37第四章 并发计算n另一种程序迁移分类方法以程序移动的方向为标准，即程序被“请进来”还是“走出去”。n如果把一段程序送出去，则称为发送者引发发送者引发(sender-initiated)的程序迁移；n反之，如果把一段程序请进来，则称为接收者引发接收者引发(receiver-initiated)的程序迁移。有的文献将接收者引发的程序迁移称为按需调入代码按需调入代码(code on demand)。n结合我们前面讨论的三种程序迁移技术:由发送者引发的程序迁移囊括原始、弱、以及强迁移三种技术，而由接收者引发的程序迁移一般只涉及原始迁移技术。程序迁移（程序迁移（3 3）38第四章 并发计算客户软件代理软件代理(代码代码+数据数据)移动代理移动代理服务器1服务器3服务器2移动代理迁移39第四章 并发计算典型的移动代理系统典型的移动代理系统nTacoma-Tcl based system developed at Cornell and Tromso University(1994-95)nAgent Tcl-Tcl based system developed at Dartmouth College.(1994-95)DAgentsnAglets-Java based system from IBM.(1996)nConcordia-Java based system from Mitsubishi Research.(1997)nVoyager-Java based system from ObjectSpacenOdyssey-Java based system from General Magic40第四章 并发计算程序迁移中的资源管理程序迁移中的资源管理 nFuggetta等人提出了三种区分程序对资源的联编类型：标识联编(binding by identifier)，值联编(binding by value)，以及类型联编(binding by type)(Fuggetta et al.1998)非隶属资源非隶属资源 紧致资源紧致资源 固定资源固定资源标识联编标识联编迁移(全局)全局(迁移)全局(禁用)值联编值联编拷贝(迁移、全局)全局(拷贝)全局(禁用)类型联编类型联编重分配(全局、拷贝)重分配(全局、拷贝)重分配(全局、禁用)41第四章 并发计算