Hey..
Can anyone please help me?
I am trying to write a round robin scheduler and so i decided that if i got a fcfs scheduler, then all i would have to do is change the process from completing in the processor to it just going into the processor for a variable time and then being put on the ready queue until its completed.
The fcfs program is a very very very simple program since i am not as experienced as you guys - does not have any IOinterrupts or anything.
The time is randomly generated using a die.There are 10 processes in all and the they have bascially 4 states :init, ready, running.The program initializes all the processes by putting them in the init state. Processes join the ready queue in array-index order: 0, 1, ..., MAXPROCS. As part of the initialising function, a process gets a random numer of clock ticks that specifies how many ticks after the previous process it joins the ready queue.
The following pseudocode was followed the following pseudocode:
while (time left and processes not all done) {
if a process is ready to be created (checkForQJoin)
move that process to end of ready queue
if process on CPU is done (checkForDone)
move that process to done queue
free CPU
if CPU is free
give CPU to next process on ready queue
show state of all queues, processes, CPU
Why i chose to create a fcfs and then change it to a round-robin was because the only lines of psuedocode that i would need to add would be
if process on CPU used up its time slice
move that process to end of ready queue
free CPU
Code used to generate the fcfs was:
#include <stdio.h>
#include <unistd.h>
#define MAXPROCS 10
/* process states: */
#define INIT 0 /* initial state: not yet created */
#define READY 1 /* ready to run */
#define RUNNING 2 /* on CPU */
#define DONE 3
struct process {
int ID; /* process ID, for convenience, equal to index of proc array */
int state; /* INIT -> READY -> RUNNING -> DONE */
int timer; /* INIT: time to join ready queue; READY: total CPU time needed */
//int working; /* Working time, for round-robin scheduling */
//int waiting; /* Waiting time, for round-robin scheduling */
struct process *next; /* pointer to next process on queue */
};
struct process proc[MAXPROCS];
struct process *nextToJoinQ = &proc[0];
struct process *nextInLine = NULL; /* head of ready queue */
struct process *lastInLine = NULL; /* tail of ready queue */
struct CPU {
struct process *onCPU;
int timeSlice;
};
struct CPU CPU;
void initprocs();
void checkForQJoin();
void joinReadyQ();
void checkForDone();
unsigned int getSeed();
void initRand();
int showQueue();
main() {
ticks = 80; /* 80 ticks */
msPerTick = 900; /* 900 millisecs per tick */
}
initRand(); /* seed random-number generator */
initprocs(); /* initialize procs */
/* main clock loop */
for(i=1; i<=ticks; ++i) {
system("cls");
printf("tick %d/%d (%d ms per tick)\n", i, ticks, msPerTick);
checkForQJoin(); /* next proc ready to join ready queue? */
checkForDone(); /* proc at head of ready queue done? */
if ((nDone = showQueue()) == MAXPROCS) { /* no more procs -- done */
break;
}
sleep(msPerTick);
}
if (nDone == MAXPROCS) {
printf("No more processes at tick %d\n", i);
} else {
printf("Clock ran out\n");
}
system("pause");
return 0;
}
/* Put all procs in INIT state and give them random time to join ready queue */
void initprocs() {
int i;
for(i=0; i<MAXPROCS; ++i) {
proc[i].ID = i;
proc[i].state = INIT;
proc[i].timer = getRandTimeToJoin();
proc[i].next = &proc[i+1];
}
nextToJoinQ = &proc[0];
proc[MAXPROCS-1].next = NULL;
nextInLine = NULL; /* head of ready queue */
lastInLine = NULL; /* tail of ready queue */
CPU.onCPU = NULL; /* CPU is free */
}
/*
* Show state of everything
* processes not yet in ready queue
* processes in ready queue
* process state
*/
int showQueue() {
int i, done = 0;
struct process *tmpProcP; /* tmp pointer to proc */
/* processes not yet created */
printf ("Not yet created: ");
for(tmpProcP=nextToJoinQ; tmpProcP!=NULL; tmpProcP = tmpProcP->next) {
printf ("P%d", tmpProcP->ID);
printf ("(%d) ", tmpProcP->timer);
}
printf ("\n");
/* process on CPU */
printf ("CPU: ");
if (CPU.onCPU == NULL) {
printf ("CPU idle\n");
} else {
tmpProcP = CPU.onCPU;
printf ("P%d", tmpProcP->ID);
printf ("(%d)\n", tmpProcP->timer);
}
/* processes in ready queue */
printf ("Ready: ");
for(tmpProcP=nextInLine; tmpProcP!=NULL; tmpProcP = tmpProcP->next) {
printf ("P%d", tmpProcP->ID);
printf ("(%d) ", tmpProcP->timer);
}
printf ("\n");
/* done ready queue */
printf("Done: ");
for(i=0; i<MAXPROCS; ++i) {
if (proc[i].state == DONE) {
printf ("P%d ", proc[i].ID);
++done;
}
}
printf("\n");
return done;
}
/* Decrement timer of next proc to join ready queue.
* If it goes to zero, change state: process joins ready queue,
* and get random time to finish once on CPU.
*/
void checkForQJoin() {
struct process *tmpProcP;
if (nextToJoinQ == NULL) /* no more processes -- done */
return;
tmpProcP = nextToJoinQ->next;
if(--(nextToJoinQ->timer) <= 0) { /* join ready queue */
nextToJoinQ->state = READY;
nextToJoinQ->timer = getRandCPUTime();
nextToJoinQ->next = NULL; /* will be last on ready queue, so no next proc */
if (nextInLine == NULL) { /* if nobody in ready queue: */
nextInLine = nextToJoinQ; /* make this proc first ... */
lastInLine = nextToJoinQ; /* ... and last in ready queue */
} else { /* ready queue already has processes */
if (lastInLine == NULL) /* CANNOT HAPPEN?!?! */
fprintf(stderr, "lastInLine is NULL but ready queue is not!!!");
lastInLine->next = nextToJoinQ;
lastInLine = nextToJoinQ;
}
nextToJoinQ = tmpProcP; /* second now first on not-yet-created list */
}
}
/*
* Add process p to ready queue.
*/
void joinReadyQ(struct process *p) {
struct process *tmpProcP;
if (nextInLine == NULL) { /* if nobody in ready queue: */
nextInLine = nextToJoinQ; /* make this proc first ... */
lastInLine = nextToJoinQ; /* ... and last in ready queue */
} else { /* ready queue already has processes */
if (lastInLine == NULL) /* CANNOT HAPPEN?!?! */
fprintf(stderr, "lastInLine is NULL but ready queue is not!!!");
lastInLine->next = nextToJoinQ;
lastInLine = nextToJoinQ;
}
nextToJoinQ = tmpProcP; /* second now first on not-yet-created list */
}
/* Decrement timer of proc on CPU.
* If it goes to zero, proc is finished.
* Give CPU to next proc on ready queue.
*/
void checkForDone() {
struct process *tmpProcP;
if (CPU.onCPU != NULL) { /* decrement timer of proc on CPU */
if(--((CPU.onCPU)->timer) <= 0) { /* proc on CPU is done */
(CPU.onCPU)->state = DONE;
/* move this proc to DONE queue ***********/
CPU.onCPU = NULL;
}
}
if ((CPU.onCPU == NULL) && (nextInLine != NULL)) {
/* give CPU to next ready proc */
tmpProcP = nextInLine->next;
CPU.onCPU = nextInLine;
nextInLine->state = RUNNING;
nextInLine = tmpProcP;
}
////////////////////
Please help me because i am totally stuck...
Code used to generate the time (toss of a die)
[B](this was given by the tutor)[/B]
//////////////
#include <sys/types.h>
#include <stdio.h>
unsigned int getSeed();
/* Seed random-number generator */
void initRand() {
srand(getSeed());
}
/*
* getRandTimeToJoin: ticks after previous customer joins ready queue
* for this customer to join ready queue.
*/
/* For now, toss die and divide by 2 to get time to join ready queue.
* Short times make simulation run faster. */
int getRandTimeToJoin() {
return tossDie()/2;
}
/*
* getRandCPUTime: ticks for this customer to finish transaction
* after he gets to teller.
*/
/* For now, toss two dice to get CPU time */
int getRandCPUTime() {
return tossDie() + tossDie();
}
int tossDie() {
return (rand() % 6) + 1;
}
/* Return a seed to use with srand: use time system call */
unsigned int getSeed() {
time_t now;
now = time(NULL);
now %= 0x7fff;
return (unsigned int) now;
}Code tags added. -Narue
