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

Recommended Answers

All 9 Replies

And your question is?

I am trying to get a simple round-robin scheduler working....using the fcfs..
I thought it would have been easier creating the fcfs and then make it into a round-robin since the psuedocode difference would just be adding a couple of lines:
if process on CPU used up its time slice
move that process to end of ready queue
free CPU

this is so since i am just trying to create a SIMPLE round robin scheduler not a complicated one...

thanks alot 4 replying...

I am trying to get a simple round-robin scheduler working....using the fcfs..

The correct acronym is FIFO (First-in, First-out). It's important when working with data structures and algorithms to use the correct terminology. Even though I was able to infer what you meant, a good way to develop yourself as a programmer is through discipline.

You have yet to ask a question besides "Can anyone please help me?".

You have yet to ask a question besides "Can anyone please help me?".

Which translates into, "Please do my homework for me"

Just for your info, my homework was :to write a C program that simulates round-robin process scheduling

I decided to create fifo scheduler (thanks 4 the correction).. and try to change it to a round-robin.....since this seemed easier at first...

Just for your info, my homework was :to write a C program that simulates round-robin process scheduling

I decided to create fifo scheduler (thanks 4 the correction).. and try to change it to a round-robin.....since this seemed easier at first...

Here's a tip: First figure out the algorithm, then figure out the data structure.

The algorithm for the program is pretty simple smartie.....
The processes bascially get the processor on a first come first served basis..
they run to completion as there isn't any pre-emption.

The main ds is process and it bascially contains the id of the process, the timer, the state of the process(there just 4 states) and a pointer to the next process.

another thing with the homework stuff was that the code given was for the timer....the tossing of the die
(mentioned that b4)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.