高级操作系统 Advanced Operating System 熊 焰 Yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系 2019/5/9

第六章 分布式程序设计 分布式程序设计的特点 分布式进程 分布式进程迁移 2019/5/9

第六章 分布式程序设计 6.1 分布式程序设计的特点 在分布式计算机系统出现后，为了应用这种系统，在七十年代后期提出了分布式程序设计的概念，即设计运行于分布式计算机系统上的分布式程序。一个分布式程序由若干可以独立执行的程序模块组成，这些程序模块分布于一个分布式计算机系统中若干台计算机上同时执行。分布于各台计算机上的程序模块是相互关联的，它们在执行中需要交换数据（即通信程）。只有通过通信，各程序模块才能协调执行，以完成一个共同的计算任务。此外，进行 2019/5/9

第六章 分布式程序设计 6.1 分布式程序设计的特点 分布式程序设计时，还常常要考虑鲁棒性，当某几台计算机发生故障时，程序仍可以执行下去。因此，分布式程序设计有三个特点：分布性、通信性和鲁棒性。为了进行分布式程序设计，必须提供分布式程序设计语言。分布式程序设计语言和其它程序设计语言的主要区别：它具有程序分布和通信的功能。有时它还具有便于实现鲁棒性的一些功能。一般来说，一种顺序程序设计语言或并发程序设计语言,增加了分布和通信功能后，就可以成为分布式程序 2019/5/9

第六章 分布式程序设计 6.1 分布式程序设计的特点 设计语言了。 分布式功能可使程序分为若干个可独立执行的程序模块。这些程序模块可以在程序开始执行前就按要求分布于各台计算机上，也可以在程序执行过程中逐个产生出来，即开始执行时只有一个程序模块，它在执行中不断产生出新的程序模块，被产生的程序模块在执行中又可以产生程序模块。由于不同的程序模块是在不同的计算机上执行的，故它们之间不能有共 2019/5/9

第六章 分布式程序设计 6.1 分布式程序设计的特点 享数据或公用变量。程序模块之间的数据交换只能依靠通信。分布式程序设计的通信功能就是用来实现程序模块间的数据交换的。 目前已有十几种分布式程序设计语言的建议。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 汉森于1978年提出了分布式进程的概念。它将并发PASCAL语言作了一些修改，并增加了分布式进程的概念，从而构成了一个分布式程序设计语言。 分布式进程是分布于系统的若干台计算机上的进程，它们之间没有公用变量。一个程序是由数量固定的若干分布式进程组成，它们同时被启动，并行地在各台计算机上执行。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 一个进程定义了自己的变量、公用过程和初始语句序列： Process（进程名） <变量定义> <公用过程定义> <初始语句序列> 一个进程执行两类操作：执行初始语句序列和由其它进程提出的外需求（即调用它定义的公用过程）。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 一个进程被启动后，先执行初始语句序列，直至执行完毕。在进程执行中因为等待某个条件而暂时不能执行下去时，如果有外需求，它就执行相应的公用过程。当此过程执行完毕或执行到等待某个条件而暂时不能继续执行时，它或者去执行初始语句序列，或者执行另一个外需求的过程。一个进程在执行初始语句序列或某个过程时，总是连续地执行下去，除非它因为等待某个条件而暂时不能继续执行下去，或者它向其它进程提出了过程调用。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 当一个进程由于上述原因不能执行语句序列或某个过程时，它就可以接收其它进程的需求，执行相应的一个过程。因此，一个进程从执行某一个过程转向另一个过程，这不是由时钟来控制的，而是由程序本身的执行来确定的。一个分布式进程的执行过程可用下图来表示： 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 (a)简单情况 （b) 复杂情况 2019/5/9 进程A 启动 执行初始语句序列 等待条件C 它进程调用 执行被调用过程 条件C成立 继续执行 （a) （b） 调用它进程的过程 它进程被调用过程执行完毕 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 一个进程可以定义若干个过程。一个过程定义 了它的输入输出参量、局部变量和语句序列： Proc<过程名>（<输入参量>#<输出参量>） <局部变量说明> <语句序列> 当执行一个过程时，相应的语句序列就被执行。一个进程可用call语句来调用另一个进程所定义的公共过程。例如，进程p可以用以下形式的call语句来调用进程Q定义的过程R： 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 call Q.R（<表达式>，变量） 在进程Q开始执行过程R时，call语句中表达式的值就赋给了输入参量。当过程执行完毕后，输出参量的值就赋给了call语句中的变量。实现上述过程调用时，调用进程先要将输入参量的值传给被调用者，过程执行完毕后，被调用者要将输出参量的值送回给调用者。所以，一次过程调用要两次通信才能实现。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 进程对过程的调用可以加以限制。例如，规定进程可以定义两类过程：公用过程和局部过程。一个进程只能调用其它进程所定义的公用过程。局部过程只能为它所属进程来调用。为了易于验证和实现，可规定不许递归调用。 在汉森提出的分布式程序设计语言建议中，还定义了一些称之为卫式命令和卫式区域的语句来控制进程执行的同步。这些语句是： 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 1. if语句 if B1:S1|B2:S2|……end 的意思是：当B1，B2，……中某个条件为真时，选择某个相应的语句执行之，否则停止执行程序。例如，执行语句 if B1:S1|B2:S2|B3:S3 end 时，若B1，B3为真，则执行完S1或S3后，这个语句就执行完了。究竟执行S1还是S3，语法 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 不作规定，也就是说，这是不确定的。如果执行这个语句时，B1，B2和B3均为假，那么就停止执行相应的程序。这往往意味着有错误发生了。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 do B1:S1|B2:S2|……end 的意思是：只要B1，B2，…中某个条件为真，就选择某个相应的语句执行之，直到所有条件均为假时这个语句才执行完毕。显然 do B:S end和While B do S end 是一样的。所以do语句是while语句的扩充。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 3. When语句 When B1:S1|B2:S2|……end 的意思是等到B1，B2，…中某个条件为真时，就执行某个相应的语句。如果多个条件为真，则选择某个相应的条件来执行。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 4. cycle语句 cycle B1:S1|B2:S2|……end 的意思是：不断地重复执行When语句 When B1:S1|B2:S2|……end 因此上面的cycle语句等价于 Do true: When B1:S1|B2:S2|……end end 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 5. for语句 for x in y:S end 的意思是：对数组或集合y中的每个元素x执行语句S。在这个程序设计语言中，除字符型。布尔型和整数型三种基本数据类型外，还有集合型、序列型和数组型。 集合型 set[n]T 是指n个T类数据的集合。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 序列型 seq[n]T 是指n个T类型数据的序列。 数组型 array[n]T 6. Skip语句 什么也不做的空操作。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 【例1】 信件缓冲 一个称为buffer的进程为进程间交换信息提 【例1】 信件缓冲 一个称为buffer的进程为进程间交换信息提 供缓冲。它定义了两个过程：Send和Receive。当 企图将信件存入缓冲时，调用过程Send。当企图 将信件从缓冲中取走时，调用过程Receive。 Process Buffer; B:array[1…128]char;{一封信由128个字符组成} Full:Boolean; {缓冲中有信时Full为真} Proc Send (M:array[1..128]char); 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 begin When not Full:B:=M;Full:=true end; end; Proc Receive(#M:array[1..128]char); When Full:M:=B;Full:=false end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 begin Full:=false end; 【例2】 字符串传送 【例2】 字符串传送 一个为Stream的进程从键盘输入设备读入一行字符串，经加工后送入例1所定义的Buffer进程的缓冲。 Process Stream; B:array[1..128]char;{一行最多128个字符} 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 i:int; begin do true： i:=1; Read(B[1]);{从键盘输入设备读入一个字符} do B[i]!=“换行字符”and i<128:i:=i+1;Read(B[i])|i=128:skip end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 do i<128:i:=i+1;B[i]:=“空格”；{将“换行字 符”后补上空格} call Buffer.Send(B);{将读入的一行字符送入 缓冲} end； 【例3】文件的读写 一个称为Resource的进程管理一个共享文件。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Process Resource; S:int; Proc Startread; begin 当一个进程要读（写）这个文件时，它先调用过程Startread（Startwrite）取得读（写）的权力，然后就可以不断地调用过程Read（Write）来读（写文件）。当读写完毕后，它调用过程Endread（Endwrite）以归还读（写）权。 Process Resource; S:int; Proc Startread; begin 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Proc Endread; begin if S>1:S:=S-1 end when S>=1:S:=S+1 end end; Proc Endread; begin if S>1:S:=S-1 end Proc Startwrite; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 end; Proc Endwrite begin if S=0:S:=1 end when S=1:S:=0 end end; Proc Endwrite begin if S=0:S:=1 end Proc Read(B:int;#R:array[1..256] char); 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 ReadBlock(B,R){将第B块中的256个字符读 入R} end； Proc Write(B:int;M:array[1..256] char); begin WriteBlock(B,M){将M中的256个字符写入第 B块} end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 begin S:=1 end; 变量S的值表明文件所处的状态，它的含义如下： …… S＝k（>=2）,有k－1个读文件的进程占用文件。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 显然，文件在Resource控制下可以同时为几个读文件的进程占用，而最多只可能为一个写文件的进程占有。一个进程用语 call Resource.startread 或 call Resource.startwrite 来占用文件。然后用 call Resource.Read(B,R)或 call Resource.Write(B,M) 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 来读或写文件。最后，用 call Resource.Endread 或 call Resource.Endwrite 来释放归还文件。 按上述方法编制的程序不能避免饿死。例如：当两个进程交替地读文件时，在一个进程归还文件前另一个就调用了过程Startread，而在一个进程调用了过程Startread后另一个才调用过程Endread，这时调用过程Startwrite的 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 进程就无法获得写文件的权力。为了避免饿死，上述进程可作以下的修改： Process Resouce; S:int; Proc Startread; begin When S>=1:S:=S+1 end end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Proc Startwrite begin if S>1:S:=2-S|S<=1:skip end; when S=1:S:=0 end end; Proc Endread if S>1:S:= S-1|S<1:S:=S+1 end 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Proc Endwrite begin if S=0:S:=1 end end; ……{以下程序不变} 此时，变量S除原来含义以外，S＝－k（k>0）表示有k＋1个进程在读文件，而至少有一个进程在等待写文件。S＝0表示有一个 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 进程在写文件或有一个进程在读文件，而有一个进程在等待写文件。经过上述修改后，只要有进程在等待写文件时就不再接受进程读文件了。显然，饿死现象就不会产生了。 【例4】哲学家用餐问题 5个哲学家围坐一圆桌。桌上有5把叉子，每人旁边有两把。每个哲学家不断地思考和进餐。当他要进餐时，他必须得到左边和右边的叉子才行。当他食毕，放下两叉，从而 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 他的两邻者可得到他们的左或右边的叉子。为了描述这个问题，引入一个称为数组进程的概念。一个数组进程 Process<进程名>[i:1…n] 表示n个进程。例如 Process Philosopher[i:1…5] 表示5个进程，它们是： 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Process Philosopher[1] Process Philosopher[2] …… 解决5个哲学家用餐问题的程序由6个进程组成。一个哲学家的活动由一个进程来描述。叉子由一个称为Table的进程来管理。 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Process Philosopher[i:1…5]; begin do true: thinking; call Table.Join(i);{第i个哲学家要求进餐} call Table.Leave(i);{第i个哲学家食毕} end； end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 Process Table eating:array[1…5]Boolean;{第i个哲学家在进 餐时,eating[i]=true} Proc Join(i:int); begin When eating[left(i)]=false and eating[right(i)] =false:eating[i]:=true end 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 {当左右的哲学家均不在进餐时，即左 右叉都空闲时，他就可以加入进餐} end； Proc Leave(i:int); begin eating[i]:=false end; 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 begin j:int; for j:=1 to 5 do eating[j]:=false end; 程序中函数left和right定义如下： left（i）＝ i－1 i>1 left（i）＝5 i=1 right(i)=i+1 i<5 2019/5/9

第六章 分布式程序设计 6.2 分布式进程 right(i)=1 i=5 不难验证，采用上述解法不会产生死锁，但是可能出现饿死现象。当一个哲学家的左右二人交替进餐时，他就可能得不到叉而“饿死”。如果修改一下，就可以既避免死锁又避免饿死。这作为作业留给同学课后自己去做。 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 在计算机网络中，允许程序或数据从一个结点迁移到另一个结点，在分布式计算机系统中，更是允许将一个进程从一个计算机迁移到另一个计算机中。 计算和数据的迁移： 数据迁移（Data Migration）：假如系统A 中的用户欲去访问系统B中文件的数据，可以采用以下两种方法来实现数据传送。第一种方法，是将系统B中的整个文件送到系统A中， 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 这样，凡是系统A中的用户要访问该文件时，都变成了本地访问。当用户不再需要此文件时，若文件拷贝已被修改，则必须把已修改过的拷贝送回系统B；若未被修改，便不必将文件回送。如果文件比较大，系统A中用户用到的文件数据又比较少，采用这种来回传送整个文件的方法，系统的效率较低。第二种方法，是仅把文件中用户当前要使用的部分从系统B传送到系统A，若以后用户又要用到 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 其它部分,再从系统B传送到系统A。当用户不再需要使用此文件时，则只需把修改过的部分传回系统B。Sun公司的网络文件系统NFS 和Microsoft 的NETBU 便使用了这种方法。 计算迁移（Computation Migration）：在有些情况下，传送计算要比传递数据效率高。例如，有一个应用，它需要访问多个驻留在不同系统中的大型文件，以获得有关数据。此时，若采用数据迁移方式，则需将驻留在 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 不同系统上的所需文件传送到用户应用所在的系统中。这样，要传送的数据量相当大，可以采计算迁移来解决这个问题。计算迁移可以有多种不同的执行方式。它可以通过RPC 调用不同系统上的例行程序来处理文件，并把处理后的结果传给自己；它也可以发送多个消息给各个驻留了文件的系统，这些机器上的操作系统将创建一个进程来处理相应文件，进程处理完毕后再把结果传递回请求进 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 程。必须注意：在第二种方式中请求进程和执行请求的进程是在不同的机器上并行执行的。上述两种方法，经过网络传输的数据相当少。如果传输数据的时间长于这段命令的执行时间，则计算迁移方式更可取；反之，数据迁移方式更有效。 进程迁移（Process Migration）：进程迁移是计算迁移的一种延伸，当一个新进程被启 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 动执行后，并不一定始终都在同一处理机上运行，也可以被迁移到另一台机器上继续运行。引入进程迁移的理由是：(1)负载均衡:分布式系统中，各个结点的负荷经常不均匀，此时，可以通过进程迁移的方法来均衡各个系统的负荷。把重负荷系统中的进程迁移到轻负荷的系统中去，以改善系统性能；(2)通信性能:对于分布在不同系统中，而彼此交互性又很强的一些进程，应将它们迁移 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 到同一系统中，以减少由于它们之间频繁地交互而加大通信开销。类似地，当某进程在执行数据分析时，如果它们所需的文件远远大于进程，则此时应该把该进程迁移到文件所在驻留的系统中去，能进一步降低通信开销；(3) 加速计算:对于一个大型应用，如果始终在一台处理机上执行，可能要化费较多时间，使作业周转时间延长。但如果能为该作业建立多个进程，并把这些进程迁移到多 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 台处理器上执行，会大大加快该作业的完成时间，从而，缩短作业的周转时间；(4)特殊功能和资源的使用:通过进程迁移来利用特殊结点上的硬件或软件功能或资源。此外，在分布式系统中，如果某个系统发生了故障，而该系统中的进程又希望继续下去，则分布式操作系统可以把这些进程迁移到其它系统中去运行，提高了系统的可用性。为了实现进程迁移，在分布式系统中必须建立相应的 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 进程迁移机制，主要负责解决(1)由谁来启动进程迁移？(2)如何进行进程迁移？(3)如何处理未完成的信号和消息等问题。 进程迁移的启动取决于进程迁移机制的目标，如果目标是平衡负载，则由系统中的监视模块负责在适当时刻进行进程迁移。在分布式系统中配置了系统负载监视模块，设定其中一个结点上的监视模块为主模块。主模块定时地与各系统的监视模块交互有关系统 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 负荷情况的信息。一旦发现有些系统忙碌，而有些系统空闲时，主模块便可启动进程迁移，向负载沉重的系统发出命令，让其把若干进程迁移到负载轻的系统中去。当然，这对用户是透明的，所有进程迁移工作都由系统完成。类似地，如果进程迁移是为了其它目标，则分布式系统中的其它相应部分成为进程迁移的启动者。 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 在进程进行迁移时，应将系统中已迁移进程撤消，在目标系统中建立一个相同的新进程，因为这是进程的迁移而不是进程的复制。进程迁移时，所迁移的是进程映象，包括进程控制块、程序、数据和栈。此外，被迁移进程与其他进程之间的关联应作相应修改。 进程迁移的过程并不复杂，但需要花费一定的通信开销，困难在于进程地址空间和已经打开的文件、进程映象、寄存器等等。 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 由于现代操作系统均采用虚拟存储技术，对于进程地址空间可使用如下两种办法：一是传送整个地址空间，把一个进程的所有映象全部从源系统传递到目标系统，这种方法简单，但当地址空间很大，且进程只需要用到一部分程序和数据时，会造成浪费；二是仅传送内存中的且已修改了的那部分地址空间，若程序运行时还需要附加的虚存空间部分信息，则可以通过请求方式予以传送。这 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 样，所传送的数据量是最少的，但源系统中仍然必须保存被迁移进程的数据及相关信息，源系统并未从对该进程的管理中解脱出来。三是预先复制，进程继续在原结点上执行，而地址空间被复制到目标结点上，由于原结点上的某些地址空间内容又被修改过，所以，需要有二次迁移，这种方法能减少进程被冻结的时间。如果被迁移的进程还打开 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 了源系统中的某些文件，可用两种方法来处理，一种方法是将已打开的文件随进程一起迁移，这里存在的问题是：进程有可能仅仅临时迁移过去，返回时才需要访问该文件；第二种方法是暂时不迁移文件，仅当迁移后的进程又提出对该文件的访问要求时，再进行迁移。如果文件被多个分布式进程所共享，则需要维护对文件的分布式访问，而不 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 必迁移。 在一个进程由源系统向目标系统迁移期间，可能会有其它进程继续向源系统中已迁移进程的进程发来消息或信号，这时应如何处理？一种可行的方法是在源系统中提供一种机构，用于暂时保存这类信息，还需保存被迁移进程所在目标系统的新地址，当被迁移进程已在目标系统中被建成新进程后，源系统便可将已收到的相关信息转发至目标系统。 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 IBM的AIX是一种分布式UNIX操作系统，它提供了一种实用的进程迁移机制。进程迁移的步骤如下： （1）当进程决定迁移自身时，它先选择一个目标机，发送一个远程执行任务的消息，该消息运载了进程映象及打开文件的部分信息； （2）在接收端，内核服务进程生成一个子进程，将这些信息交给它； 2019/5/9

第六章 分布式程序设计 6.3 分布式进程迁移 （3）这个新进程收集完成其操作所需的环境、数据、变量和栈信息。如果它是“脏”的就复制程序文件；如果是“干净”的，则请求从全局文件系统中调页。 （4）迁移完成后发消息通知源进程，源进程就发一个最后完成消息给新进程，然后删去自己。 2019/5/9