系统结构-并行算法FORK JOIN[通俗易懂]

2022-11-05 15:24:39 浏览数 (1)

大家好，又见面了，我是你们的朋友全栈君。

南大自考流程详解

自考-计算机应用专业

2020系统结构系列

并行算法FORK JOIN

  • 一、FORK JOIN定义
  • 二、举例
    • 题目一：
      • 题目分析：
    • 题目二：
      • 题目分析： 注意：本文全是作者胡猜，如有错误请指出，共同进步

一、FORK JOIN定义

FORK语句的形式：

代码语言：javascript复制
FORK m,其中m为新进程开始的标号。

执行FORK m语句时,派生出标号为m开始的新进程,具体为: 1、准备好这个新进程启动和执行所必需的信息; 2、如果是共享主存,则产生存储器指针、映像函数和访问权数据; 3、将空闲的处理机分配给派生的新进程,如果没有空闲处理机,则让它们排队等待; 4、继续在原处理机上执行FORK语句的原进程。

与FORK语句相配合,作为每个并发进程的终端语句JOIN的形式:

代码语言：javascript复制
JOIN n,其中n为并发进程的个数。

1、JOIN语句附有一个计数器,其初始值为0。每当执行JOIN n语句时,计数器的值加1,并与n比较。 2、若比较相等,表明这是执行中的第n个并发进程经过JOIN语句，于是允许该进程通过JOIN语句，将计数器清0，并在处理机上继续执行后续语句; 3、若比较不等,计数器的值仍小于n,表明此进程不是并发进程的最后一个可让现在执行JOIN与的这个进程先结束,把它所占用的处理机释放出来,分配给真正该排队等待的其他任务。如果没有排队等待的任务,就让该处理机空闲。

GOTO 语句的形式：

代码语言：javascript复制
GOTO m，无条件转移语句，其中m为跳转的进程标号。

举个不恰当的例子，四个小学生赛跑，全部比赛完成，一起去颁奖台执行颁奖活动。

//默认是有一个进程的，还需要克隆出3个
0 FORK 20
  FORK 30
  FORK 40
10小学生1号开始跑了
  JOIN 4
  GOTO 60
20小学生2号开始跑了
  JOIN 4
  GOTO 60
30小学生3号开始跑了
  JOIN 4
  GOTO 60
40小学生4号开始跑了
  JOIN 4
  GOTO 60 //这句可有可无，因为他的下一句就是60，即使没有跳转，也会往下执行
60执行颁奖活动

如上所示，所有的小学生都知道跑完步下一个活动就是颁奖，但是还有小学生没跑到终点，你就去参加颁奖活动合适吗？
那么怎么才知道所有小学生都跑完了呢？
每一个小学生跑完都执行JOIN 4,JOIN相当于裁判，他有一个计数器，每一个小学生跑完就 1。
比如小学生1号跑完，计数器的值 1=1，<4，那么此时就不会再继续执行下面的GOTO 60。
跑得最慢的小学生跑完时，计数器的值=4了，此时才能执行后续语句，即GOTO 60。

二、举例

题目一：

题目分析：

1、首先执行这个程序，用两台处理机。 2、假定最初的程序在cpu1上运行，cpu1首先执行标号为10的进程。 3、然后遇到FORK30语句时就分出一个cpu2去执行标号为30的进程，而cpu1接着执行标号为20的进程。 注意：这里20和30两个进程同时进行，因为除法最慢，所以标号为20的进程后一个完成。

那么标号30的进程首先完成，先执行JOIN2的语句。（此时计数器加1，等于1，和2比较，不等。那么就把这个进程先释放掉，分配给真正该排队等待的其他任务，由于此时没有任务排队，所以该处理机空闲） 3、然后标号20的进程结束，执行JOIN2(此时计数器又加1，相等，于是允许该进程通过JOIN语句，将计数器清0，并在处理机上继续执行后续语句) 4、后续语句，GO TO 40 5、Cpu1开始执行fork60,cpu2空闲状态，就开辟一个进程标号60，cpu1接着执行标号50的进程，由于减法跑得快，所以标号50的进程先执行join2（计数器=1，不等，释放） 标号60的进程执行join2(计数器=2，相等，继续执行后续语句) 6、后续语句，标号70执行。 根据分析绘图，如下所示：

题目二：

题目分析：

这是书上的一道例题，仔细看看，其实就是上面那道题，只是加大了难度，他现在给到你的是单处理机顺序执行的代码。多了一步改写程序的步骤。那么求遇到这种题目怎么做呢？ 首先要画出并行程序数据相关图，先给语句标上号

然后根据它们的相关性，画出流程图。比如s1:U=A B，它可以和下面语句并行执行吗？ 显然不行，第二句用到了U，如果第一句和第二句并行就会发生相关，从而产生错误结果。 所以S1执行完了后面的才可以执行。这时候我们看后面的语句，S2和S3显然可以并行的，S4就冲突了，当然就算S4不冲突，我们也不会S2，S3,S4一起执行。因为咱们只有两个CPU啊。 当S2，S3都执行完了，S4就可以执行了，显然他和S5没有冲突，所以也可以并行。最后是S6。

流程图画好了之后就好办了。顺序我们都知道了。 根据流程图开始改写语句：

代码语言：javascript复制
//S1进程在CPU1上跑
10 U=A B（S1）
   //为了S2和S3并行,此时派生了标号为30的新进程到CPU2上
   FORK 30 
//标号为20的进程（S2）在Cpu1上
20 V=U/B（S2）
   JOIN 2 
   //S2和S3两个进程中，慢跑完的进程，其所在的cpu继续执行后续语句，这里是S2除法慢。
   //跳转40，至于40执行什么功能到那里再讨论
   GOTO 40 
//标号为30的进程（S3）在Cpu2上
30 W=A*U（S3）
   JOIN 2 
   //S2和S3两个进程中，慢跑完的进程，其所在的cpu继续执行后续语句，这里是S2除法慢。
//下面语句，会在S2和S3汇合后执行。
//S2除法慢，所以cpu1执行后续语句。Cpu2空闲。
//为了S4和S5并行,Cpu1此时派生了标号为60的新进程到CPU2上
40 FORK 60 
//Cpu1继续执行S4
50 X=W-V（S4）
   JOIN 2 
   //S4和S5两个进程中，慢跑完的进程，其所在的cpu继续执行后续语句，这里是S5乘法慢。
   GOTO 70 
//Cpu2继续执行S5,注意S5和S4并行执行关系
60 Y=W*U（S5）
   JOIN 2
//S4和S5两个进程中，慢跑完的进程，其所在的cpu继续执行后续语句，S5慢，cpu2执行后续语句。
70 Z=X/Y（S6）

系统结构-计算机系统结构里的多级立方体网络怎么理解？

我发现，系统结构这本书总在我看懂之后才觉得写得有道理。大概不是书写得辣鸡，只是书写得不容易理解吧。就是那种高手唰唰唰在你面前舞了一通剑法，你一脸懵逼，觉得这都啥玩意啊，还不如广场舞大妈跳得好呢。然后此去经年，你终于成了剑术大家，想起当年的这个剑客，只觉得处处妙极。 嗯，大概就是这种感觉~

Java基础不好的小水怪，正在学习。有错请指出，一起加油。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/191480.html原文链接：https://javaforall.cn

unix

0 人点赞