/* following only needed for getpid() call used for srandom() */ #includeFurthermore, adding random calls to thread_relinquish() within the code does not change its correctness -- this experiment is equivalent to running it under a preemptive scheduler./* following only needed for random() and srandom() */ #include /* following needed for most of program */ #include #include "threads.h" /****************************/ /* Philosophical Activities */ /****************************/ void think() { do { thread_relinquish(); } while (random() & 7); } #define eat think /*************************************************/ /* Philosophical Code, rewritten from Tannenbaum */ /*************************************************/ #define N 5 /* number of philosophers */ #define THINKING 0 /* philosopher is thinking */ #define HUNGRY 1 /* philosopher is hungry */ #define EATING 2 /* philosopher is eating */ int left( int i ) /* return number of i's left neighbor */ { if (i <= 0) return N-1; return i-1; } int right( int i ) /* return number of i's right neighbor */ { if (i >= N-1) return 0; return i+1; } int state[N]; /* array to keep track of everyone's state */ struct thread_semaphore mutex; /* mutual exclusion for critical regions */ struct thread_semaphore s[N]; /* one semaphore per philosopher */ void initforks() { int i; thread_semaphore_init( &mutex, 1 ); for (i = 0; i < N; i++) { state[i] = THINKING; /* start all philosophers thinking */ thread_semaphore_init( &s[i], 0 ); } } void test( int i ) { if ( (state[i] == HUNGRY) && ( state[left( i )] != EATING) && ( state[right( i )] != EATING) ) { state[i] = EATING; thread_signal( &s[i] ); } } void take_forks( int i ) { thread_wait( &mutex ); state[i] = HUNGRY; test( i ); thread_signal( &mutex ); thread_wait( &s[i] ); } void put_forks( int i ) { thread_wait( &mutex ); state[i] = THINKING; test( left( i ) ); test( right( i ) ); thread_signal( &mutex ); } void philosopher( int i ) { putchar( '0'+i ); puts(" start"); for (;;) { /* philosopher starts out thinking */ take_forks(i); putchar( '0'+i ); puts(" eat"); eat(); put_forks(i); putchar( '0'+i ); puts(" think"); think(); } } /*************************************/ /* Main program, starts philosophers */ /*************************************/ int main() { srandom( (unsigned) getpid() ); /* randomize the random numbers */ thread_manager_init(); thread_startup_report(); initforks(); { int i; for (i = 0; i < N; i++) { thread_launch( 4000, philosopher, i ); } } thread_manager_start(); }
/* following only needed for getpid() call used for srandom() */ #include/* following only needed for random() and srandom() */ #include /* following needed for most of program */ #include #include "threads.h" /***************************/ /* FIFO DISK REQUEST QUEUE */ /***************************/ struct request { int cl; struct thread_semaphore * dn; struct request * next; }; struct request* head; struct request* tail; struct request* freelist; struct thread_semaphore data; void initqueue() { head = NULL; tail = NULL; freelist = NULL; thread_semaphore_init( &data, 0 ); } void enqueue( int cyl, struct thread_semaphore * done ) { /* get a new disk request record */ struct request* req; if (freelist == NULL) { req = (struct request *)malloc(sizeof(struct request)); } else { req = freelist; freelist = req->next; } /* load the disk request record with data */ req->cl = cyl; req->dn = done; req->next = NULL; /* enqueue the disk request */ if (head == NULL) { /* the queue is empty */ head = req; } else { tail->next = req; } tail = req; /* synchronize */ thread_signal( &data ); } void dequeue( int * cyl, struct thread_semaphore ** done ) { /* synchronize */ thread_wait( &data ); /* dequeue the disk request (the queue is non-empty) */ struct request * req; req = head; head = req->next; /* unload the disk request data */ *cyl = req->cl; *done = req->dn; /* dispose of the request record */ req->next = freelist; freelist = req; } /************************************/ /* DISK INTERRUPT SERVICE SIMULATOR */ /************************************/ void disk( int n ) { int cyl = 0; /* cylinder number */ int ocyl; /* old cylinder number */ int diff; /* difference cylinder numbers */ int i,j; /* loop counters */ int time = 0;/* a measure of the total time taken */ struct thread_semaphore * done; do (i = 0; i < n; i++) { ocyl = cyl; dequeue( &cyl, &done ); diff = cyl - ocyl; if (diff < 0) diff = -diff; for (j = 0; j <= diff; j++) { thread_relinquish(); time++; } thread_signal( done ); } print( "time = &d", time ); } /***********************/ /* DISK USER SIMULATOR */ /***********************/ void user( int n ) { int i; /* count of disk operations */ int cyl; /* selected cylinder */ struct thread_semaphore done; thread_semaphore_init( &done, 0 ); cyl = random(); do (i = 1; i <= n; i++) { /* do n disk operations */ while (random() & 3) thread_relinquish(); /* take some time */ if ((random() & 3) == 0)) cyl = random(); cyl = cyl & 63; enqueue( cyl, &done ); /* post one disk request */ thread_wait( &done ); } } /***********************************/ /* Main program, starts simulation */ /***********************************/ int main() { srandom( (unsigned) getpid() ); /* randomize the random numbers */ thread_manager_init(); thread_startup_report(); initqueue(); thread_launch( 4000, disk, 100 ); { int i; for (i = 0; i < 5; i++) { thread_launch( 4000, user, 20 ); } } thread_manager_start(); }
Part B: The required modifications are confined to the queue module:
/*******************************/
/* ELEVATOR DISK REQUEST QUEUE */
/*******************************/
struct request {
int cl;
struct thread_semaphore * dn;
struct request * next;
};
#define CYLS 64
struct request* heads[CYLS];
struct request* tails[CYLS];
int cylinder;
int direction;
struct request* freelist;
struct thread_semaphore data;
void initqueue()
{
int i;
for (i = 0; i < CYLS; i++) {
heads[i] = NULL;
tails[i] = NULL;
}
freelist = NULL;
cylinder = 0;
direction = 1; /* start up from the bottom */
thread_semaphore_init( &data, 0 );
}
void enqueue( int cyl, struct thread_semaphore * done )
{
/* get a new disk request record */
struct request* req;
if (freelist == NULL) {
req = (struct request *)malloc(sizeof(struct request));
} else {
req = freelist;
freelist = req->next;
}
/* load the disk request record with data */
req->cl = cyl;
req->dn = done;
req->next = NULL;
/* enqueue the disk request in queue for appropriate cylinder */
if (heads[cyl] == NULL) { /* the queue is empty */
heads[cyl] = req;
} else {
tails[cyl]->next = req;
}
tails[cyl] = req;
/* synchronize */
thread_signal( &data );
}
void dequeue( int * cyl, struct thread_semaphore ** done )
{
struct request * req;
/* synchronize */
thread_wait( &data );
/* find a cylinder where there is work to do */
while (heads[cylinder] == NULL) {
cylinder = cylinder + direction;
if ((cylinder == 0) || (cylinder == (CYLS-1))) {
direction = -direction;
}
}
/* dequeue the disk request (the queue is non-empty) */
req = heads[cylinder];
heads[cylinder] = req->next;
/* unload the disk request data */
*cyl = req->cl;
*done = req->dn;
/* dispose of the request record */
req->next = freelist;
freelist = req;
}
This gives an improvement of about 40%, on the average over a number of
experimental runs comparing it with the FIFO version.