// lollypop.cpp - ESTIMATE COMMUNICATIONS TIMES // // MODULE INDEX // NAME CONTENTS // Channel::Channel Construct a channel // Channel::chEnqueue Queue a request to a channel // Channel::chTxDone Process transmission completed // drand Double random number // Simulate Simulate transmission of a single file // Average Average a sample of transmission times // main Main line // // MAINTENANCE HISTORY // DATE PROGRAMMER AND DETAILS // 11-11-02 JS Original // //----------------------------------------------------------------------------- #include // Standard input/output #include // Standard library //----------------------------------------------------------------------------- // DEFINITIONS #define SATDELAY 0.5 // Satellite delay (seconds per leg) #define FILESIZE 1024 // File size in 1k blocks #define MAXTHREAD 8 // Maximum threads #define REQLEN 64 // Request length #define RSPLEN 1088 // Response length #define BITSPERBYTE 10 // Bits per byte (asynchronous) #define RETRYTIME 5.0 // Retry time (seconds) #define SATLOSS (1.0/200.0) // Prob of satellite message loss #define SAMPSIZE 1000 // Sample size //----------------------------------------------------------------------------- // NEXT EVENT TYPE enum Event { EVENTNONE, // No event EVENTTHREAD, // Thread operation EVENTREQCH, // Request channel operation EVENTRSPCH // Response channel operation }; //----------------------------------------------------------------------------- // COMMUNICATION THREAD STATES enum ThSt { THSTTOSHORE, // Satellite, ship-to-shore THSTQTOFS, // Queued from ground station to file server THSTQTOGS, // Queued from file server to ground station THSTTOSHIP, // Satellite, shore-to-ship THSTLOST, // Lost or corrupted message THSTFINISH // Processing finished }; //----------------------------------------------------------------------------- // COMMUNICATION THREAD struct Thread { Thread *thNxt; // Next thread in the queue Thread *thPrv; // Previous thread in the queue ThSt thSt; // Thread state double thTime; // State expiry time double thRetry; // Retry time }; //----------------------------------------------------------------------------- // SERIAL COMMUNICATIONS CHANNEL class Channel { Thread *chFst; // First thread queued to the channel Thread *chLst; // Last thread queued to the channel double chTxPrd; // Channel transmission period double chTime; // Current transmission completion time public: Channel (double txPrd); // Constructor void chEnqueue (Thread *th, double t); // Enqueue a request int chActive () { return chFst != NULL; } // Test if channel active double chGetTime () { return chTime; } // Return next completion time Thread *chTxDone (); // Transmission completed }; //----------------------------------------------------------------------------- // CONSTRUCT A CHANNEL Channel::Channel ( double txPrd) // Transmission period { chFst = NULL; chLst = NULL; chTxPrd = txPrd; } //----------------------------------------------------------------------------- // QUEUE A REQUEST TO A CHANNEL void Channel::chEnqueue ( Thread *th, // Thread to enqueue double t) // Current time { // If the queue is empty, put the request in the channel queue // and initiate tramsmission. if (chFst == NULL) { th->thPrv = NULL; th->thNxt = NULL; chFst = th; chLst = th; chTime = t + chTxPrd; } // If the queue is non-empty, append the request to the queue. else { th->thPrv = chLst; th->thNxt = NULL; chLst->thNxt = th; chLst = th; } } //----------------------------------------------------------------------------- // PROCESS TRANSMISSION COMPLETED Thread * Channel::chTxDone () { Thread *th; // Thread pointer if (chFst == NULL) { fprintf (stderr, "Error: chTxDone: channel not active\n"); abort (); } // Remove the first thread from the queue. th = chFst; chFst = th->thNxt; if (chFst == NULL) chLst = NULL; else chFst->thPrv = NULL; // If there is a second thread in the queue, set the // completion time for the next thread if (chFst != NULL) chTime += chTxPrd; // Return the completed thread return th; } //----------------------------------------------------------------------------- // DOUBLE RANDOM NUMBER double drand () { return (double)rand() / 32768.0; } //----------------------------------------------------------------------------- // SIMULATE TRANSMISSION OF A SINGLE FILE double Simulate ( double baud, // Serial communications speed int thCnt) // Thread count { Thread thArr[MAXTHREAD]; // Thread array int i; // General purpose index Thread *th; // Thread pointer int blkRem; // Blocks remaining to be transmitted double nextTime; // Next event time Event nextEvent; // Next event enumerator Thread *nextTh; // Next thread pointer // Initiate the request and response channels Channel reqCh ((REQLEN*BITSPERBYTE)/baud); Channel rspCh ((RSPLEN*BITSPERBYTE)/baud); // Initialise the blocks remaining to be transmitted // and the next event time blkRem = FILESIZE; nextTime = 0; // Initialise the threads for (i = 0; i < thCnt; i++) { th = thArr + i; if (blkRem != 0) { th->thRetry = nextTime + RETRYTIME; if (drand() < SATLOSS) { th->thSt = THSTLOST; th->thTime = th->thRetry; } else { th->thSt = THSTTOSHORE; th->thTime = nextTime + SATDELAY; } blkRem -- ; } else { th->thSt = THSTFINISH; } } // Process cycles until all threads are finished do { // Figure out the next thing to happen nextEvent = EVENTNONE; if ( reqCh.chActive() && ( nextEvent == EVENTNONE || reqCh.chGetTime() < nextTime ) ) { nextEvent = EVENTREQCH; nextTime = reqCh.chGetTime(); } if ( rspCh.chActive() && ( nextEvent == EVENTNONE || rspCh.chGetTime() < nextTime ) ) { nextEvent = EVENTRSPCH; nextTime = rspCh.chGetTime(); } for (i = 0; i < thCnt; i++) { th = thArr + i; if ( ( th->thSt == THSTTOSHORE || th->thSt == THSTTOSHIP || th->thSt == THSTLOST ) && ( nextEvent == EVENTNONE || th->thTime < nextTime ) ) { nextEvent = EVENTTHREAD; nextTime = th->thTime; nextTh = th; } } // Process the event switch (nextEvent) { case EVENTREQCH: th = reqCh.chTxDone(); th->thSt = THSTQTOGS; rspCh.chEnqueue (th, nextTime); break; case EVENTRSPCH: th = rspCh.chTxDone(); if (drand() < SATLOSS) { th->thSt = THSTLOST; if (th->thRetry < nextTime) { fprintf (stderr, "Error: retry time expired\n"); abort (); } th->thTime = th->thRetry; } else { th->thSt = THSTTOSHIP; th->thTime = nextTime + SATDELAY; } break; case EVENTTHREAD: th = nextTh; switch (th->thSt) { case THSTTOSHORE: th->thSt = THSTQTOFS; reqCh.chEnqueue (th, nextTime); break; case THSTTOSHIP: if (th->thRetry < nextTime) { fprintf (stderr, "Error: retry time expired\n"); abort (); } if (blkRem != 0) { th->thRetry = nextTime + RETRYTIME; if (drand() < SATLOSS) { th->thSt = THSTLOST; th->thTime = th->thRetry; } else { th->thSt = THSTTOSHORE; th->thTime = nextTime+SATDELAY; } blkRem -- ; } else { th->thSt = THSTFINISH; } break; case THSTLOST: th->thRetry = nextTime + RETRYTIME; if (drand() < SATLOSS) { th->thSt = THSTLOST; th->thTime = th->thRetry; } else { th->thSt = THSTTOSHORE; th->thTime = nextTime+SATDELAY; } break; default: fprintf (stderr, "Error: invalid chSt\n"); abort (); } break; case EVENTNONE: break; } } while (nextEvent != EVENTNONE); // Return the completion time return nextTime; } //----------------------------------------------------------------------------- // AVERAGE A SAMPLE OF TRANSMISSION TIMES double Average ( double baud, // Serial communications speed int thCnt) // Thread count { int i; // General purpose index double total; // Total transmission times srand (2031960); total = 0; for (i = 0; i < SAMPSIZE; i++) total += Simulate (baud, thCnt); return total / SAMPSIZE; } //----------------------------------------------------------------------------- // MAIN LINE int main () { printf ("1 thread, low speed %8.2f\n", Average (42600.0, 1)); printf ("1 thread, high speed %8.2f\n", Average (256000.0, 1)); printf ("8 threads, low speed %8.2f\n", Average (42600.0, 8)); return 0; }