具有优先图和不同执行时间的 M 机上的 N 个作业
N-jobs on M-machines with Precedence Graph and different execution times
假设我有 n 个作业和 m 台机器。这些作业具有优先约束（在有向无环图中给出）和不同的执行时间。
时间表不得抢占。
安排它们的最佳算法是什么？有什么建议么？我知道一般来说它是 NP 难的，所以启发式也可以。
我会考虑这里给出的 Hu Level Scheduling
http://web.cecs.pdx.edu/~mperkows/temp/0002.scheduling2.pdf
但如果我理解正确，它假定执行时间相同。
我建议采用贪心启发法。
假设您的工作有 execution_time 和 children。让叶作业的 dependency_time 为 execution_time，其他作业的 execution_time + max(dependency_time for children)。
在每一步，安排最大dependency_time的可用作业。
解决方案示例
欧洲航天局 Giotto 卫星使用它飞入深处 Space：哈雷彗星。
由 prof. C. A. R. Hoare 开创，一种新的确定性（除非存在外部 events/stimuli/ALT）调度使解决并发问题成为可能。
基于 π-演算 驱动的调度，π-代数解决了 N-jobs 对 M-resources 给定 DAG 依赖关系的依赖关系和允许可变作业持续时间和进程间通信（使用分离作业的开创性技术，使它们与便宜、快速和专用的 CSP 通道成对互连，如果需要的话，以静止的方式交换信息片段确定性和调度非破坏性方式）。
::: occam-pi executed all the N-jobs as per dependencies were specified
::: using pi-calculus algebra for deterministic
::: scheduling N-jobs over a pool of M-resources available
::: w.r.t. all dependencies
:::
job: 1 job duration: 15 timer: 545252301 START.... __
job: 11 job duration: 9 timer: 545252302 START.... __
job: 11 job duration: 9 timer: 545252317 FINISH... __
job: 21 job duration: 8 timer: 545252447 START.... __
job: 21 job duration: 8 timer: 545252489 FINISH... __
job: 20 job duration: 16 timer: 545252447 START.... __
job: 20 job duration: 16 timer: 545252538 FINISH... __
job: 19 job duration: 7 timer: 545252447 START.... __
job: 19 job duration: 7 timer: 545252614 FINISH... __
job: 12 job duration: 9 timer: 545252447 START.... __
job: 12 job duration: 9 timer: 545252659 FINISH... __
job: 13 job duration: 8 timer: 545252682 START.... __
job: 13 job duration: 8 timer: 545252704 FINISH... __
job: 14 job duration: 7 timer: 545252727 START.... __
job: 14 job duration: 7 timer: 545252752 FINISH... __
job: 15 job duration: 6 timer: 545252775 START.... __
job: 15 job duration: 6 timer: 545252798 FINISH... __
job: 16 job duration: 5 timer: 545252819 START.... __
job: 16 job duration: 5 timer: 545252840 FINISH... __
job: 17 job duration: 4 timer: 545252862 START.... __
job: 17 job duration: 4 timer: 545252886 FINISH... __
job: 18 job duration: 9 timer: 545252908 START.... __
job: 18 job duration: 9 timer: 545252930 FINISH... __
job: 8 job duration: 2 timer: 545252301 START.... __
job: 8 job duration: 2 timer: 545252976 FINISH... __
job: 9 job duration: 5 timer: 545252999 START.... __
job: 9 job duration: 5 timer: 545253022 FINISH... __
job: 10 job duration: 31 timer: 545253044 START.... __
job: 10 job duration: 31 timer: 545253093 FINISH... __
job: 1 job duration: 15 timer: 545252416 FINISH... __
job: 5 job duration: 31 timer: 545253142 START.... __
job: 5 job duration: 31 timer: 545253230 FINISH... __
job: 6 job duration: 27 timer: 545253242 START.... __
job: 6 job duration: 27 timer: 545253309 FINISH... __
job: 7 job duration: 11 timer: 545253324 START.... __
job: 7 job duration: 11 timer: 545253347 FINISH... __
job: 4 job duration: 12 timer: 545253141 START.... __
job: 4 job duration: 12 timer: 545253392 FINISH... __
job: 2 job duration: 24 timer: 545253141 START.... __
job: 2 job duration: 24 timer: 545253436 FINISH... __
job: 3 job duration: 6 timer: 545253460 START.... __
job: 3 job duration: 6 timer: 545253482 FINISH... __
此 main() 使用 DAG 定义的依赖项的示例案例 for ~ 21-jobs 具有变量持续时间并且是 运行 on-line:
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node-(sorry for naive ASCII-art)-*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------: |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------:
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------:
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
代码是 made runnable online 用于任何使用真实-[PARALLEL] 系统设计的实验 - 唯一遗憾的是，InMOS Transputers 被他们平台的 x86-CPU-core( s) 对“wilder”PAR-部分的权力有限。
享受进一步破解 π 演算驱动调度的乐趣：
#INCLUDE "course.module" -- #USE "course.lib"
-- +------+--------+----+----------+
-- | jobID|duration|time|aSTRING[] |
-- +---------------+------+--------+----+----------+
-- |messagePROTOCOL| INT; INT; INT; [10]BYTE |
PROTOCOL messagePROTOCOL IS INT; INT; INT; [10]BYTE : -- Error-occ21-.code.tio.occ(7)- array type must have dimension specified
-- +---------------+------+--------+----+----------+
PROC job ( VAL INT id, VAL INT duration, CHAN messagePROTOCOL outP )
INT t : -- declare INT
TIMER aCentralCLOCK : -- declare TIMER
[10]BYTE flag.START : -- declare [10]BYTE
[10]BYTE flag.FINISH: -- declare [10]BYTE
SEQ ------------------------------------------------------------------SEQ:
flag.START := " START...." -- .SET
flag.FINISH := " FINISH..." -- .SET
aCentralCLOCK ? t -- .read ? .SET t from timer at start
outP ! id; duration; t; flag.START -- .outP ! messagePROTOCOL{ id; duration; t; aString }
aCentralCLOCK ? AFTER ( t PLUS duration ) -- .read ? .wait till ( start PLUS duration )
-- ^^^^^
-- |||||
-- |||||
-- +++++------------------------------------------------- <this> emulates a variable <job>-duration
aCentralCLOCK ? t -- .read / .SET t from timer at finish
outP ! id; duration; t; flag.FINISH -- .outP ! messagePROTOCOL{ id; duration; t; aString }
: -- job() -------------------------------------------------------------
PROC SysPrintr(CHAN BYTE outCH, CHAN messagePROTOCOL inCH )
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
SEQ
--GET ? ----------------------------------------------------------
inCH ? iJobID; iDuration; iTimer; aString
--PRINT ---------------------------outCH--------------------------
out.string( " job: ", 5, outCH )
out.int( iJobID, 3, outCH )
out.string( " job duration: ", 20, outCH )
out.int( iDuration, 5, outCH )
out.string( " timer: ", 8, outCH )
out.int( iTimer, 10, outCH )
SEQ i = 0 FOR SIZE aString
outCH ! aString[i]
out.string( "__*n", 4, outCH )
flush( outCH ) -- .flush
: -- SysPrintr() -------------------------------------------------------
PROC SysMonMUX(CHAN messagePROTOCOL out!, []CHAN messagePROTOCOL in?)
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
ALT
in[ 0] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 1] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 2] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 3] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 4] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 5] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 6] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 7] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 8] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 9] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[10] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[11] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[12] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[13] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[14] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[15] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[16] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[17] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[18] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[19] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[20] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[21] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[22] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
: -- SysMonMUX()--------------------------------------------------------
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node ----------------------------*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------* |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------*
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------+
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
致谢：致谢 @bazza 提醒这个令人难忘的 Occam-pi space 任务。
假设我有 n 个作业和 m 台机器。这些作业具有优先约束（在有向无环图中给出）和不同的执行时间。 时间表不得抢占。 安排它们的最佳算法是什么？有什么建议么？我知道一般来说它是 NP 难的，所以启发式也可以。 我会考虑这里给出的 Hu Level Scheduling http://web.cecs.pdx.edu/~mperkows/temp/0002.scheduling2.pdf 但如果我理解正确，它假定执行时间相同。
我建议采用贪心启发法。
假设您的工作有 execution_time 和 children。让叶作业的 dependency_time 为 execution_time，其他作业的 execution_time + max(dependency_time for children)。
在每一步，安排最大dependency_time的可用作业。
解决方案示例
欧洲航天局 Giotto 卫星使用它飞入深处 Space：哈雷彗星。
由 prof. C. A. R. Hoare 开创，一种新的确定性（除非存在外部 events/stimuli/ALT）调度使解决并发问题成为可能。
基于 π-演算 驱动的调度，π-代数解决了 N-jobs 对 M-resources 给定 DAG 依赖关系的依赖关系和允许可变作业持续时间和进程间通信（使用分离作业的开创性技术，使它们与便宜、快速和专用的 CSP 通道成对互连，如果需要的话，以静止的方式交换信息片段确定性和调度非破坏性方式）。
::: occam-pi executed all the N-jobs as per dependencies were specified
::: using pi-calculus algebra for deterministic
::: scheduling N-jobs over a pool of M-resources available
::: w.r.t. all dependencies
:::
job: 1 job duration: 15 timer: 545252301 START.... __
job: 11 job duration: 9 timer: 545252302 START.... __
job: 11 job duration: 9 timer: 545252317 FINISH... __
job: 21 job duration: 8 timer: 545252447 START.... __
job: 21 job duration: 8 timer: 545252489 FINISH... __
job: 20 job duration: 16 timer: 545252447 START.... __
job: 20 job duration: 16 timer: 545252538 FINISH... __
job: 19 job duration: 7 timer: 545252447 START.... __
job: 19 job duration: 7 timer: 545252614 FINISH... __
job: 12 job duration: 9 timer: 545252447 START.... __
job: 12 job duration: 9 timer: 545252659 FINISH... __
job: 13 job duration: 8 timer: 545252682 START.... __
job: 13 job duration: 8 timer: 545252704 FINISH... __
job: 14 job duration: 7 timer: 545252727 START.... __
job: 14 job duration: 7 timer: 545252752 FINISH... __
job: 15 job duration: 6 timer: 545252775 START.... __
job: 15 job duration: 6 timer: 545252798 FINISH... __
job: 16 job duration: 5 timer: 545252819 START.... __
job: 16 job duration: 5 timer: 545252840 FINISH... __
job: 17 job duration: 4 timer: 545252862 START.... __
job: 17 job duration: 4 timer: 545252886 FINISH... __
job: 18 job duration: 9 timer: 545252908 START.... __
job: 18 job duration: 9 timer: 545252930 FINISH... __
job: 8 job duration: 2 timer: 545252301 START.... __
job: 8 job duration: 2 timer: 545252976 FINISH... __
job: 9 job duration: 5 timer: 545252999 START.... __
job: 9 job duration: 5 timer: 545253022 FINISH... __
job: 10 job duration: 31 timer: 545253044 START.... __
job: 10 job duration: 31 timer: 545253093 FINISH... __
job: 1 job duration: 15 timer: 545252416 FINISH... __
job: 5 job duration: 31 timer: 545253142 START.... __
job: 5 job duration: 31 timer: 545253230 FINISH... __
job: 6 job duration: 27 timer: 545253242 START.... __
job: 6 job duration: 27 timer: 545253309 FINISH... __
job: 7 job duration: 11 timer: 545253324 START.... __
job: 7 job duration: 11 timer: 545253347 FINISH... __
job: 4 job duration: 12 timer: 545253141 START.... __
job: 4 job duration: 12 timer: 545253392 FINISH... __
job: 2 job duration: 24 timer: 545253141 START.... __
job: 2 job duration: 24 timer: 545253436 FINISH... __
job: 3 job duration: 6 timer: 545253460 START.... __
job: 3 job duration: 6 timer: 545253482 FINISH... __
此 main() 使用 DAG 定义的依赖项的示例案例 for ~ 21-jobs 具有变量持续时间并且是 运行 on-line:
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node-(sorry for naive ASCII-art)-*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------: |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------:
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------:
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
代码是 made runnable online 用于任何使用真实-[PARALLEL] 系统设计的实验 - 唯一遗憾的是，InMOS Transputers 被他们平台的 x86-CPU-core( s) 对“wilder”PAR-部分的权力有限。
享受进一步破解 π 演算驱动调度的乐趣：
#INCLUDE "course.module" -- #USE "course.lib"
-- +------+--------+----+----------+
-- | jobID|duration|time|aSTRING[] |
-- +---------------+------+--------+----+----------+
-- |messagePROTOCOL| INT; INT; INT; [10]BYTE |
PROTOCOL messagePROTOCOL IS INT; INT; INT; [10]BYTE : -- Error-occ21-.code.tio.occ(7)- array type must have dimension specified
-- +---------------+------+--------+----+----------+
PROC job ( VAL INT id, VAL INT duration, CHAN messagePROTOCOL outP )
INT t : -- declare INT
TIMER aCentralCLOCK : -- declare TIMER
[10]BYTE flag.START : -- declare [10]BYTE
[10]BYTE flag.FINISH: -- declare [10]BYTE
SEQ ------------------------------------------------------------------SEQ:
flag.START := " START...." -- .SET
flag.FINISH := " FINISH..." -- .SET
aCentralCLOCK ? t -- .read ? .SET t from timer at start
outP ! id; duration; t; flag.START -- .outP ! messagePROTOCOL{ id; duration; t; aString }
aCentralCLOCK ? AFTER ( t PLUS duration ) -- .read ? .wait till ( start PLUS duration )
-- ^^^^^
-- |||||
-- |||||
-- +++++------------------------------------------------- <this> emulates a variable <job>-duration
aCentralCLOCK ? t -- .read / .SET t from timer at finish
outP ! id; duration; t; flag.FINISH -- .outP ! messagePROTOCOL{ id; duration; t; aString }
: -- job() -------------------------------------------------------------
PROC SysPrintr(CHAN BYTE outCH, CHAN messagePROTOCOL inCH )
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
SEQ
--GET ? ----------------------------------------------------------
inCH ? iJobID; iDuration; iTimer; aString
--PRINT ---------------------------outCH--------------------------
out.string( " job: ", 5, outCH )
out.int( iJobID, 3, outCH )
out.string( " job duration: ", 20, outCH )
out.int( iDuration, 5, outCH )
out.string( " timer: ", 8, outCH )
out.int( iTimer, 10, outCH )
SEQ i = 0 FOR SIZE aString
outCH ! aString[i]
out.string( "__*n", 4, outCH )
flush( outCH ) -- .flush
: -- SysPrintr() -------------------------------------------------------
PROC SysMonMUX(CHAN messagePROTOCOL out!, []CHAN messagePROTOCOL in?)
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
ALT
in[ 0] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 1] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 2] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 3] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 4] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 5] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 6] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 7] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 8] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 9] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[10] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[11] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[12] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[13] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[14] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[15] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[16] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[17] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[18] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[19] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[20] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[21] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[22] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
: -- SysMonMUX()--------------------------------------------------------
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node ----------------------------*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------* |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------*
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------+
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
致谢：致谢 @bazza 提醒这个令人难忘的 Occam-pi space 任务。