home *** CD-ROM | disk | FTP | other *** search
/ Mega CD-ROM 1 / megacd_rom_1.zip / megacd_rom_1 / MAGAZINE / DDJMAG / DDJCSPEC.ZIP / GEHANI.LST < prev    next >
File List  |  1989-11-21  |  11KB  |  438 lines
  1. _DISCRETE EVENT SIMULATION IN CONCURRENT C_
  2. by Narain Gehani and W.D. Roome
  3.  
  4. [LISTING ONE]
  5.  
  6. File: sim-sched.h
  7.  
  8. process spec sched() {
  9.   trans long now()   /* return simulated time */
  10.   trans long reqDelay(long del);
  11.                      /* request delay */
  12.   trans long wait(long x); /* wait for delay */
  13.   trans void addUser();    /* add client */
  14.   trans void dropUser();   /* drop client */
  15.   trans void passive();    /* client is passive */
  16.   trans void active();     /* client is active */
  17. };
  18.  
  19.  
  20. [LISTING TWO]
  21.  
  22. File: sim-source.h
  23.  
  24. process spec source(
  25.   process sched s,    /* scheduler */
  26.   process queue outQ, /* output queue */
  27.   long meanIat,   /* mean inter-arrival time */
  28.   long meanServt, /* mean service time */
  29.   long nGen,      /* number to generate */
  30.   name_t name);   /* symbolic name */
  31.  
  32.  
  33. [LISTING THREE]
  34.  
  35. File: sim-server.h
  36.  
  37. process spec server (
  38.   process sched s,    /* scheduler */
  39.   process queue inQ,  /* input queue */
  40.   process queue outQ, /* output queue */
  41.   double speed,       /* speed of server */
  42.   name_t name);       /* symbolic name */
  43.  
  44.  
  45. [LISTING FOUR]
  46.  
  47. File: sim-qItem.h
  48.  
  49. typedef struct {
  50.        /* Public: */
  51.   long servt;   /* service time for job */
  52.   long arrive;  /* time job arrived */
  53.   
  54.        /* Private to queue process: */
  55.   long qEnter;  /* time entered queue */
  56.   int  ticket;  /* ticket from takeReq */
  57.   int gotItem;  /* !=0 if item was taken */
  58. } qItem;
  59.  
  60.  
  61. [LISTING FIVE]
  62.  
  63. File: sim-queue.h
  64.  
  65. process spec queue(
  66.     process sched s,       /* scheduler */
  67.     int maxSize,           /* max queue size */
  68.     name_t name)           /* symbolic name */
  69. {
  70.   trans int  itemCnt();    /* return queue size */
  71.   trans void addProd();    /* add producer */
  72.   trans void dropProd();   /* drop producer */
  73.   trans void addCons();    /* add consumer */
  74.   trans void dropCons();   /* drop consumer */
  75.   
  76.           /* start and finish put request:*/
  77.   trans int putReq(qItem);
  78.   trans void putWait(int, qItem);
  79.  
  80.           /* start and finish take request:*/
  81.   trans qItem takeReq();
  82.   trans qItem takeWait(int);
  83. };
  84.  
  85. [LISTING SIX]
  86.  
  87. File: sim-stats.h
  88.  
  89. typedef struct {
  90.   long    nv;    /* number of values */
  91.   long    maxv;  /* max value */
  92.   double  sumv;  /* sum of values */
  93.   double  sumsq; /* sum of squares */
  94. } stats;
  95.  
  96. void   stInit(); /* initialize structure */
  97. void   stVal();  /* add new value */
  98. double stMean(); /* return mean value */
  99. double stSdev(); /* return standard deviation */
  100. long   erand();  /* exponential random number */
  101.  
  102.   
  103.  
  104. [LISTING SEVEN]
  105.  
  106. File: sim-main.cc
  107.  
  108. name_t makeName(name) char *name;
  109. {  name_t ret;
  110.    strcpy(ret.str, name);
  111.    return ret;
  112. }
  113.  
  114. main()
  115. {  process sched s;
  116.    process queue q1, q2;
  117.    long nGen=100000;  /* number of jobs */
  118.    long servt=500;    /* mean service time */
  119.    long iat=1000;     /* mean inter-arrival */
  120.  
  121. /* Create virtual time scheduler. */
  122.   s = create sched(); s.addUser();
  123.  
  124. /* Create queues and servers. */
  125.   q1 = create queue(s, 100, makeName("Q1"));
  126.   q2 = create queue(s, 100, makeName("Q2"));
  127.   create source(s, q1, iat, servt, nGen,
  128.                 makeName("Src"));
  129.   create server(s, q1, q2, 0.5,
  130.                 makename("Serv1.1"));
  131.   create server(s, q1, q2, 0.5,
  132.                 makename("Serv1.2"));
  133.   create server(s, q2, c_nullpid, 1.0,
  134.                 makename("Serv2"));
  135.  
  136. /* Wait for all processes to start. */
  137.   delay 2.0;  s.dropUser();
  138. }
  139.  
  140.  
  141.  
  142. [LISTING EIGHT]
  143.  
  144. File: si-source.cc
  145.  
  146. process body source(s, outQ, meanIat,
  147.                     meanServt, nGen, name)
  148. {  stats  iat, servt;
  149.    qItem  item;
  150.    long   i, t;
  151.  
  152. /* Initialization phase */
  153.    s.addUser();
  154.    outQ.addProd();
  155.    stInit(&iat);  stInit(&servt);
  156.  
  157. /* Main processing phase: generate jobs. */
  158.     for (i=1; i <= nGen; i++) {
  159.       t = erand(meanIat);
  160.       stVal(&iat, t);
  161.       item.arrive = s.wait(s.reqDelay(t));
  162.       item.servt = erand(meanServt);
  163.       stVal(&servt, item.servt);
  164.       qPut(outQ, item);
  165.     }
  166. /* Termination phase: print stats, etc. */
  167.     print statistics;
  168.     outQ.dropProd();  s.dropUser();
  169. }
  170.  
  171.  
  172.  
  173. [LISTING NINE]
  174.  
  175. File: sim-server.cc
  176.  
  177. process body server(s, inQ, outQ, speed, name)
  178. {  stats sysTime; /* time-in-system */
  179.    qItem item;
  180.    long ts;
  181.  
  182.    s.addUser();  stInit(&sysTime);
  183.    inQ.addCons();
  184.    if (outQ != c_nullpid)
  185.      outQ.addProd();
  186.  
  187.    while (qTake(inQ, &item)) {
  188.      ts = s.wait(s.reqDelay(item.servt/speed));
  189.      stVal(&sysTime, ts - item.arrive);
  190.      if (outQ != c_nullpid)
  191.        qPut(outQ, item);
  192.    }
  193.  
  194.    print statistics;
  195.    if (outQ != c_nullpid)
  196.      outQ.dropProd();
  197.    inQ.addCons();  s.dropUser();
  198. }
  199.  
  200. [LISTING TEN]
  201.  
  202. File sim-qPut.cc
  203.  
  204. /* Put item onto queue; wait if full. */
  205. void qPut(q, item)
  206.    process queue q;  qItem item;
  207. {  int ticket = q.putReq(item);
  208.    if (ticket >= 0)
  209.       q.putWait(ticket, item);
  210. }
  211.  
  212. /* Set *itemp to next item; wait if empty. */
  213. /* Return 1 if item was taken, 0 on EOF */
  214. int qTake(q, itemp)
  215.    process queue q;  qItem *itemp;
  216. {
  217.    *itemp = q.takeReq();
  218.    if (itemp->ticket >= 0)
  219.       *itemp = q.takeWait(itemp->ticket);
  220.    return itemp->gotItem;
  221. }
  222.  
  223. [LISTING ELEVEN]
  224.  
  225. File: sim-qInfo.h
  226.  
  227. /* *tInfo: Describe outstanding tickets. */
  228. typedef struct {
  229.    int acc;    /* next ticket to accept */
  230.    int give;   /* next ticket to give out */
  231.    int nPass;  /* pending passive clients */
  232. } tInfo;
  233.  
  234. /* qInfo: Describe one queue. */
  235. typedef struct {
  236.    process sched s;  /* scheduler process */
  237.    int     max;      /* max queue size */
  238.    int     nProd;    /* number of producers */
  239.    int     nCons;    /* number of consumers */
  240.    name_t  name;     /* name of queue */
  241.    stats   qTime;    /* time-in-queue stats */
  242.    stats   qSize;    /* for queue size stats */
  243.    int     nElem;    /* items in queue */
  244.    int     head;     /* index head of queue */
  245.    int     tail;     /* index tail of queue */
  246.    qItem   *items;   /* alloc'd array of items */
  247.  
  248. /* Describe pending put, take requests: */
  249.    tInfo   pPut, pTake;
  250. } qInfo;
  251.  
  252.  
  253. [LISTING TWELVE]
  254.  
  255. File: sim-queue.cc
  256.  
  257. process body queue(s, maxSize, name)
  258. {  qInfo q;  qItem x;
  259.    initialize qInfo structure;
  260.    accept addProd()  { q.nProd++; }
  261.  
  262.    while (q.nProd+q.nCons >0) {
  263.       select {
  264.       (q.nElem<q.max && q.pPut.acc==q.pPut.give):
  265.          accept putReq(item)
  266.             { putItem(&q, &item);  treturn -1; }
  267.       or (q.nElem==q.max):
  268.          accept putReq(item)
  269.             { s.passive();  q.pPut.nPass++;
  270.               treturn incTick(&q.pPut.give); }
  271.       or (q.nElem<q.max):
  272.          accept putWait(qt, item)
  273.             suchthat (qt == q.pPut.acc)
  274.          {  putItem(&q, &item);
  275.             incTick(&q.pPut.acc); }
  276.       or (q.nElem>0 && q.pTake.acc==q.pTake.give):
  277.          accept takeReq()
  278.             {  treturn takeItem(&q); }
  279.       or (q.nElem==0):
  280.          accept takeReq()
  281.             {  x.ticket = incTick(&q.pTake.give);
  282.                s.passive();  q.pTake.nPass++;
  283.                treturn x; }
  284.       or (q.nElem>0):
  285.          accept takeWait(qt)
  286.                suchthat (qt == q.pTake.acc)
  287.             {  incTick (&q.pTake.acc);
  288.                treturn takeItem(&q); }
  289.       or (q.nProd==0 && q.nElem==0):
  290.          accept takeWait(qt)
  291.             {  x.gotItem = 0;  treturn x; }
  292.  
  293.       or accept itemCnt()  { treturn q.nElem; }
  294.       or accept addCons()  { q.nCons++; }
  295.       or accept addProd()  { q.nProd++; }
  296.       or accept dropCons() { q.nCons--; }
  297.       or accept dropProd() { q.nProd--; }
  298.       }
  299.    /* On EOF, make pending takers active. */
  300.       if (q.nProd==0 && q.nElem==0)
  301.           for (; q.pTake.nPass > 0; q.pTake.nPass--)
  302.              s.active();
  303.    }
  304.    print statistics;
  305. }
  306.  
  307. [LISTING THIRTEEN]
  308.  
  309. File: sim-qAux.cc
  310.  
  311. /* Increment ticket, return prev value. */
  312. int incTick(tp)
  313.    int *tp;
  314. {  int t = *tp;
  315.    *tp = (t+1)%10000;
  316.    return t;
  317. }
  318.  
  319. /* Remove and eturn the next item in the queue. */
  320. qItem takeItem(qp)
  321.    qInfo *qp;
  322. {
  323.    qItem item;
  324.    item = qp->items[qp->head];
  325.    item.ticket = -1;
  326.    item.gotItem = 1;
  327.    stVal(&qp->qTime, qp->s.now() - item.qEnter);
  328.    qp->nElem--;
  329.    qp->head = (qp->head+1) % qp->max;
  330.    if (qp-pPut.nPass >0)
  331.       { qp->s.active(); qp->pPut.nPass--; }
  332.    return item;
  333. }
  334.  
  335. /* Add item *itemp to queue. */
  336. void putItem(qp, itemp)
  337.    qInfo *qp; qItem *itemp;
  338. {
  339.    qp->items[qp->tail] = *itemp;
  340.    qp->items[qp->tail].qEnter = qp->s.now();
  341.    stVal(&qp->qSize, qp->nElem);
  342.    qp->nElem++;
  343.    qp->tail = (qp->tail+1) % qp->max;
  344.    if (qp->pTake.nPass > 0)
  345.       {  qp-<>s.active(); qp->pTake.nPass--; }
  346. }
  347.  
  348. [LISTING FOURTEEN]
  349.  
  350. File: sim-sched.cc
  351.  
  352. process body sched()
  353. {  int  nUser, nAct, i;
  354.    long curTime = 0;  /* Current simulated time */
  355.    ordered list of pending delay requests;
  356.  
  357.    initialize pending delay list data structures;
  358.    accept addUser() { nUser = nAct = 1; }
  359.    while (nUser >0) {
  360.       select {
  361.          accept addUser()  { ++nUser; ++nAct; }
  362.       or accept dropUser() { --nUser; --nAct; }
  363.       or accept active()   { ++nAct; }
  364.       or accept passive()  { --nAct; }
  365.       or accept now()      { treturn curTime; }
  366.       or accept reqDelay(x)
  367.          { add request for curTime+x to pending delay list;
  368.            nAct--;  treturn request-index; }
  369.       }
  370.       if (nAct == 0 && pending delay list is not empty) {
  371.          curTime = time of request at head of list;
  372.          nAct = number of processes waiting for that time;
  373.          for (i = 1; i <= nAct; i++)
  374.             accept wait(x)
  375.                suchthat (x == index-of-head-request)
  376.                   { treturn curTime; }
  377.          discard request at head of pending delay list;
  378.       }
  379.    }
  380. }
  381.  
  382. Example 1: The Server Process
  383.  
  384. while (1) {
  385.   delay for random inter-arrival time;
  386.   generate item;
  387.   call queue process to put item in queue;
  388. }
  389.  
  390. Example 2: Moving Jobs Between Queues
  391.  
  392. qItem item;
  393. process queue qFrom, qTo;
  394.  
  395. while (qTake(qFrom, &item))
  396.   qput(qTo, item);
  397.  
  398.  
  399.  
  400. Example 3: Generating Random Numbers
  401.  
  402. stats mystats;
  403. int   i;
  404.  
  405. stInit(&mystats);
  406. for (i = 1; i <= 10000; i++)
  407.   stVal(&mystats, erand(100));
  408. printf("Mean is %lf\n", stMean(&mystats));
  409.  
  410.  
  411. Example 4: Choosing Queues
  412.  
  413.  
  414. if (outQ1.itemCnt() < outQ2.itemCnt())
  415.   qPut(outQ1, item);
  416. else
  417.   qPut(outQ2, item);
  418.  
  419.  
  420. Example 5: An Example of main()
  421.  
  422. main()
  423. {
  424.    create all processes
  425.    while (1) {
  426.       s.wait(s.reqDelay(10000));
  427.       for each entity process p
  428.          entity-stats = p.giveStats();
  429.       if (statistics have been stable for long enough)
  430.          break;
  431.    }
  432.    print final statistics
  433.    for all processes p
  434.       c_abort(p);
  435. }
  436.  
  437.  
  438.